LLVM  10.0.0svn
AliasSetTracker.h
Go to the documentation of this file.
1 //===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file defines two classes: AliasSetTracker and AliasSet. These interfaces
10 // are used to classify a collection of pointer references into a maximal number
11 // of disjoint sets. Each AliasSet object constructed by the AliasSetTracker
12 // object refers to memory disjoint from the other sets.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H
17 #define LLVM_ANALYSIS_ALIASSETTRACKER_H
18 
19 #include "llvm/ADT/DenseMap.h"
20 #include "llvm/ADT/DenseMapInfo.h"
21 #include "llvm/ADT/ilist.h"
22 #include "llvm/ADT/ilist_node.h"
24 #include "llvm/IR/Instruction.h"
25 #include "llvm/IR/Metadata.h"
26 #include "llvm/IR/ValueHandle.h"
27 #include "llvm/Support/Casting.h"
28 #include <cassert>
29 #include <cstddef>
30 #include <cstdint>
31 #include <iterator>
32 #include <vector>
33 
34 namespace llvm {
35 
36 class AliasSetTracker;
37 class BasicBlock;
38 class LoadInst;
39 class Loop;
40 class MemorySSA;
41 class AnyMemSetInst;
42 class AnyMemTransferInst;
43 class raw_ostream;
44 class StoreInst;
45 class VAArgInst;
46 class Value;
47 
48 class AliasSet : public ilist_node<AliasSet> {
49  friend class AliasSetTracker;
50 
51  class PointerRec {
52  Value *Val; // The pointer this record corresponds to.
53  PointerRec **PrevInList = nullptr;
54  PointerRec *NextInList = nullptr;
55  AliasSet *AS = nullptr;
57  AAMDNodes AAInfo;
58 
59  // Whether the size for this record has been set at all. This makes no
60  // guarantees about the size being known.
61  bool isSizeSet() const { return Size != LocationSize::mapEmpty(); }
62 
63  public:
64  PointerRec(Value *V)
65  : Val(V), AAInfo(DenseMapInfo<AAMDNodes>::getEmptyKey()) {}
66 
67  Value *getValue() const { return Val; }
68 
69  PointerRec *getNext() const { return NextInList; }
70  bool hasAliasSet() const { return AS != nullptr; }
71 
72  PointerRec** setPrevInList(PointerRec **PIL) {
73  PrevInList = PIL;
74  return &NextInList;
75  }
76 
77  bool updateSizeAndAAInfo(LocationSize NewSize, const AAMDNodes &NewAAInfo) {
78  bool SizeChanged = false;
79  if (NewSize != Size) {
80  LocationSize OldSize = Size;
81  Size = isSizeSet() ? Size.unionWith(NewSize) : NewSize;
82  SizeChanged = OldSize != Size;
83  }
84 
86  // We don't have a AAInfo yet. Set it to NewAAInfo.
87  AAInfo = NewAAInfo;
88  else {
89  AAMDNodes Intersection(AAInfo.intersect(NewAAInfo));
90  if (!Intersection) {
91  // NewAAInfo conflicts with AAInfo.
93  return SizeChanged;
94  }
95  AAInfo = Intersection;
96  }
97  return SizeChanged;
98  }
99 
100  LocationSize getSize() const {
101  assert(isSizeSet() && "Getting an unset size!");
102  return Size;
103  }
104 
105  /// Return the AAInfo, or null if there is no information or conflicting
106  /// information.
107  AAMDNodes getAAInfo() const {
108  // If we have missing or conflicting AAInfo, return null.
109  if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() ||
111  return AAMDNodes();
112  return AAInfo;
113  }
114 
115  AliasSet *getAliasSet(AliasSetTracker &AST) {
116  assert(AS && "No AliasSet yet!");
117  if (AS->Forward) {
118  AliasSet *OldAS = AS;
119  AS = OldAS->getForwardedTarget(AST);
120  AS->addRef();
121  OldAS->dropRef(AST);
122  }
123  return AS;
124  }
125 
126  void setAliasSet(AliasSet *as) {
127  assert(!AS && "Already have an alias set!");
128  AS = as;
129  }
130 
131  void eraseFromList() {
132  if (NextInList) NextInList->PrevInList = PrevInList;
133  *PrevInList = NextInList;
134  if (AS->PtrListEnd == &NextInList) {
135  AS->PtrListEnd = PrevInList;
136  assert(*AS->PtrListEnd == nullptr && "List not terminated right!");
137  }
138  delete this;
139  }
140  };
141 
142  // Doubly linked list of nodes.
143  PointerRec *PtrList = nullptr;
144  PointerRec **PtrListEnd;
145  // Forwarding pointer.
146  AliasSet *Forward = nullptr;
147 
148  /// All instructions without a specific address in this alias set.
149  /// In rare cases this vector can have a null'ed out WeakVH
150  /// instances (can happen if some other loop pass deletes an
151  /// instruction in this list).
152  std::vector<WeakVH> UnknownInsts;
153 
154  /// Number of nodes pointing to this AliasSet plus the number of AliasSets
155  /// forwarding to it.
156  unsigned RefCount : 27;
157 
158  // Signifies that this set should be considered to alias any pointer.
159  // Use when the tracker holding this set is saturated.
160  unsigned AliasAny : 1;
161 
162  /// The kinds of access this alias set models.
163  ///
164  /// We keep track of whether this alias set merely refers to the locations of
165  /// memory (and not any particular access), whether it modifies or references
166  /// the memory, or whether it does both. The lattice goes from "NoAccess" to
167  /// either RefAccess or ModAccess, then to ModRefAccess as necessary.
168  enum AccessLattice {
169  NoAccess = 0,
170  RefAccess = 1,
171  ModAccess = 2,
172  ModRefAccess = RefAccess | ModAccess
173  };
174  unsigned Access : 2;
175 
176  /// The kind of alias relationship between pointers of the set.
177  ///
178  /// These represent conservatively correct alias results between any members
179  /// of the set. We represent these independently of the values of alias
180  /// results in order to pack it into a single bit. Lattice goes from
181  /// MustAlias to MayAlias.
182  enum AliasLattice {
183  SetMustAlias = 0, SetMayAlias = 1
184  };
185  unsigned Alias : 1;
186 
187  unsigned SetSize = 0;
188 
189  void addRef() { ++RefCount; }
190 
191  void dropRef(AliasSetTracker &AST) {
192  assert(RefCount >= 1 && "Invalid reference count detected!");
193  if (--RefCount == 0)
194  removeFromTracker(AST);
195  }
196 
197  Instruction *getUnknownInst(unsigned i) const {
198  assert(i < UnknownInsts.size());
199  return cast_or_null<Instruction>(UnknownInsts[i]);
200  }
201 
202 public:
203  AliasSet(const AliasSet &) = delete;
204  AliasSet &operator=(const AliasSet &) = delete;
205 
206  /// Accessors...
207  bool isRef() const { return Access & RefAccess; }
208  bool isMod() const { return Access & ModAccess; }
209  bool isMustAlias() const { return Alias == SetMustAlias; }
210  bool isMayAlias() const { return Alias == SetMayAlias; }
211 
212  /// Return true if this alias set should be ignored as part of the
213  /// AliasSetTracker object.
214  bool isForwardingAliasSet() const { return Forward; }
215 
216  /// Merge the specified alias set into this alias set.
217  void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);
218 
219  // Alias Set iteration - Allow access to all of the pointers which are part of
220  // this alias set.
221  class iterator;
222  iterator begin() const { return iterator(PtrList); }
223  iterator end() const { return iterator(); }
224  bool empty() const { return PtrList == nullptr; }
225 
226  // Unfortunately, ilist::size() is linear, so we have to add code to keep
227  // track of the list's exact size.
228  unsigned size() { return SetSize; }
229 
230  /// If this alias set is known to contain a single instruction and *only* a
231  /// single unique instruction, return it. Otherwise, return nullptr.
233 
234  void print(raw_ostream &OS) const;
235  void dump() const;
236 
237  /// Define an iterator for alias sets... this is just a forward iterator.
238  class iterator : public std::iterator<std::forward_iterator_tag,
239  PointerRec, ptrdiff_t> {
240  PointerRec *CurNode;
241 
242  public:
243  explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {}
244 
245  bool operator==(const iterator& x) const {
246  return CurNode == x.CurNode;
247  }
248  bool operator!=(const iterator& x) const { return !operator==(x); }
249 
250  value_type &operator*() const {
251  assert(CurNode && "Dereferencing AliasSet.end()!");
252  return *CurNode;
253  }
254  value_type *operator->() const { return &operator*(); }
255 
256  Value *getPointer() const { return CurNode->getValue(); }
257  LocationSize getSize() const { return CurNode->getSize(); }
258  AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); }
259 
260  iterator& operator++() { // Preincrement
261  assert(CurNode && "Advancing past AliasSet.end()!");
262  CurNode = CurNode->getNext();
263  return *this;
264  }
265  iterator operator++(int) { // Postincrement
266  iterator tmp = *this; ++*this; return tmp;
267  }
268  };
269 
270 private:
271  // Can only be created by AliasSetTracker.
272  AliasSet()
273  : PtrListEnd(&PtrList), RefCount(0), AliasAny(false), Access(NoAccess),
274  Alias(SetMustAlias) {}
275 
276  PointerRec *getSomePointer() const {
277  return PtrList;
278  }
279 
280  /// Return the real alias set this represents. If this has been merged with
281  /// another set and is forwarding, return the ultimate destination set. This
282  /// also implements the union-find collapsing as well.
283  AliasSet *getForwardedTarget(AliasSetTracker &AST) {
284  if (!Forward) return this;
285 
286  AliasSet *Dest = Forward->getForwardedTarget(AST);
287  if (Dest != Forward) {
288  Dest->addRef();
289  Forward->dropRef(AST);
290  Forward = Dest;
291  }
292  return Dest;
293  }
294 
295  void removeFromTracker(AliasSetTracker &AST);
296 
297  void addPointer(AliasSetTracker &AST, PointerRec &Entry, LocationSize Size,
298  const AAMDNodes &AAInfo, bool KnownMustAlias = false,
299  bool SkipSizeUpdate = false);
300  void addUnknownInst(Instruction *I, AliasAnalysis &AA);
301 
302  void removeUnknownInst(AliasSetTracker &AST, Instruction *I) {
303  bool WasEmpty = UnknownInsts.empty();
304  for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
305  if (UnknownInsts[i] == I) {
306  UnknownInsts[i] = UnknownInsts.back();
307  UnknownInsts.pop_back();
308  --i; --e; // Revisit the moved entry.
309  }
310  if (!WasEmpty && UnknownInsts.empty())
311  dropRef(AST);
312  }
313 
314 public:
315  /// If the specified pointer "may" (or must) alias one of the members in the
316  /// set return the appropriate AliasResult. Otherwise return NoAlias.
317  AliasResult aliasesPointer(const Value *Ptr, LocationSize Size,
318  const AAMDNodes &AAInfo, AliasAnalysis &AA) const;
319  bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const;
320 };
321 
322 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
323  AS.print(OS);
324  return OS;
325 }
326 
328  /// A CallbackVH to arrange for AliasSetTracker to be notified whenever a
329  /// Value is deleted.
330  class ASTCallbackVH final : public CallbackVH {
331  AliasSetTracker *AST;
332 
333  void deleted() override;
334  void allUsesReplacedWith(Value *) override;
335 
336  public:
337  ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr);
338 
339  ASTCallbackVH &operator=(Value *V);
340  };
341  /// Traits to tell DenseMap that tell us how to compare and hash the value
342  /// handle.
343  struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {};
344 
345  AliasAnalysis &AA;
346  MemorySSA *MSSA;
347  Loop *L;
348  ilist<AliasSet> AliasSets;
349 
350  using PointerMapType = DenseMap<ASTCallbackVH, AliasSet::PointerRec *,
351  ASTCallbackVHDenseMapInfo>;
352 
353  // Map from pointers to their node
354  PointerMapType PointerMap;
355 
356 public:
357  /// Create an empty collection of AliasSets, and use the specified alias
358  /// analysis object to disambiguate load and store addresses.
359  explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
361  : AA(aa), MSSA(mssa), L(l) {}
363 
364  /// These methods are used to add different types of instructions to the alias
365  /// sets. Adding a new instruction can result in one of three actions
366  /// happening:
367  ///
368  /// 1. If the instruction doesn't alias any other sets, create a new set.
369  /// 2. If the instruction aliases exactly one set, add it to the set
370  /// 3. If the instruction aliases multiple sets, merge the sets, and add
371  /// the instruction to the result.
372  ///
373  /// These methods return true if inserting the instruction resulted in the
374  /// addition of a new alias set (i.e., the pointer did not alias anything).
375  ///
376  void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo); // Add a loc
377  void add(LoadInst *LI);
378  void add(StoreInst *SI);
379  void add(VAArgInst *VAAI);
380  void add(AnyMemSetInst *MSI);
381  void add(AnyMemTransferInst *MTI);
382  void add(Instruction *I); // Dispatch to one of the other add methods...
383  void add(BasicBlock &BB); // Add all instructions in basic block
384  void add(const AliasSetTracker &AST); // Add alias relations from another AST
385  void addUnknown(Instruction *I);
386  void addAllInstructionsInLoopUsingMSSA();
387 
388  void clear();
389 
390  /// Return the alias sets that are active.
391  const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
392 
393  /// Return the alias set which contains the specified memory location. If
394  /// the memory location aliases two or more existing alias sets, will have
395  /// the effect of merging those alias sets before the single resulting alias
396  /// set is returned.
397  AliasSet &getAliasSetFor(const MemoryLocation &MemLoc);
398 
399  /// Return the underlying alias analysis object used by this tracker.
400  AliasAnalysis &getAliasAnalysis() const { return AA; }
401 
402  /// This method is used to remove a pointer value from the AliasSetTracker
403  /// entirely. It should be used when an instruction is deleted from the
404  /// program to update the AST. If you don't use this, you would have dangling
405  /// pointers to deleted instructions.
406  void deleteValue(Value *PtrVal);
407 
408  /// This method should be used whenever a preexisting value in the program is
409  /// copied or cloned, introducing a new value. Note that it is ok for clients
410  /// that use this method to introduce the same value multiple times: if the
411  /// tracker already knows about a value, it will ignore the request.
412  void copyValue(Value *From, Value *To);
413 
416 
417  const_iterator begin() const { return AliasSets.begin(); }
418  const_iterator end() const { return AliasSets.end(); }
419 
420  iterator begin() { return AliasSets.begin(); }
421  iterator end() { return AliasSets.end(); }
422 
423  void print(raw_ostream &OS) const;
424  void dump() const;
425 
426 private:
427  friend class AliasSet;
428 
429  // The total number of pointers contained in all "may" alias sets.
430  unsigned TotalMayAliasSetSize = 0;
431 
432  // A non-null value signifies this AST is saturated. A saturated AST lumps
433  // all pointers into a single "May" set.
434  AliasSet *AliasAnyAS = nullptr;
435 
436  void removeAliasSet(AliasSet *AS);
437 
438  /// Just like operator[] on the map, except that it creates an entry for the
439  /// pointer if it doesn't already exist.
440  AliasSet::PointerRec &getEntryFor(Value *V) {
441  AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
442  if (!Entry)
443  Entry = new AliasSet::PointerRec(V);
444  return *Entry;
445  }
446 
447  AliasSet &addPointer(MemoryLocation Loc, AliasSet::AccessLattice E);
448  AliasSet *mergeAliasSetsForPointer(const Value *Ptr, LocationSize Size,
449  const AAMDNodes &AAInfo,
450  bool &MustAliasAll);
451 
452  /// Merge all alias sets into a single set that is considered to alias any
453  /// pointer.
454  AliasSet &mergeAllAliasSets();
455 
456  AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
457 };
458 
460  AST.print(OS);
461  return OS;
462 }
463 
464 } // end namespace llvm
465 
466 #endif // LLVM_ANALYSIS_ALIASSETTRACKER_H
void mergeSetIn(AliasSet &AS, AliasSetTracker &AST)
Merge the specified alias set into this alias set.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
Various leaf nodes.
Definition: ISDOpcodes.h:59
bool isMayAlias() const
const_iterator end() const
Define an iterator for alias sets... this is just a forward iterator.
void dump() const
bool operator!=(const iterator &x) const
This file contains the declarations for metadata subclasses.
An instruction for reading from memory.
Definition: Instructions.h:167
AAMDNodes getAAInfo() const
value_type & operator*() const
LocationSize getSize() const
Encapsulates MemorySSA, including all data associated with memory accesses.
Definition: MemorySSA.h:703
bool isMustAlias() const
Value * getPointer() const
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2097
iterator begin() const
bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const
Instruction * getUniqueInstruction()
If this alias set is known to contain a single instruction and only a single unique instruction...
An instruction for storing to memory.
Definition: Instructions.h:320
AliasResult
The possible results of an alias query.
Definition: AliasAnalysis.h:78
void print(raw_ostream &OS) const
LLVM Basic Block Representation.
Definition: BasicBlock.h:57
AliasAnalysis & getAliasAnalysis() const
Return the underlying alias analysis object used by this tracker.
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
LocationSize unionWith(LocationSize Other) const
early cse Early CSE w MemorySSA
Definition: EarlyCSE.cpp:1424
AliasSetTracker(AliasAnalysis &aa)
Create an empty collection of AliasSets, and use the specified alias analysis object to disambiguate ...
static constexpr LocationSize mapEmpty()
This class represents any memset intrinsic.
bool isMod() const
This class represents the va_arg llvm instruction, which returns an argument of the specified type gi...
bool operator==(const iterator &x) const
An intrusive list with ownership and callbacks specified/controlled by ilist_traits, only with API safe for polymorphic types.
Definition: ilist.h:388
Representation for a specific memory location.
AliasResult aliasesPointer(const Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo, AliasAnalysis &AA) const
If the specified pointer "may" (or must) alias one of the members in the set return the appropriate A...
Iterator for intrusive lists based on ilist_node.
BlockVerifier::State From
void print(raw_ostream &OS) const
static uint64_t add(uint64_t LeftOp, uint64_t RightOp)
Definition: FileCheck.cpp:243
A collection of metadata nodes that might be associated with a memory access used by the alias-analys...
Definition: Metadata.h:643
bool isRef() const
Accessors...
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:225
iterator end() const
const ilist< AliasSet > & getAliasSets() const
Return the alias sets that are active.
Represents a single loop in the control flow graph.
Definition: LoopInfo.h:509
#define I(x, y, z)
Definition: MD5.cpp:58
value_type * operator->() const
uint32_t Size
Definition: Profile.cpp:46
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2045
const_iterator begin() const
iterator(PointerRec *CN=nullptr)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:73
AAMDNodes intersect(const AAMDNodes &Other)
Given two sets of AAMDNodes that apply to the same pointer, give the best AAMDNodes that are compatib...
Definition: Metadata.h:670
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
bool empty() const
AliasSetTracker(AliasAnalysis &aa, MemorySSA *mssa, Loop *l)
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:379
AliasSet & operator=(const AliasSet &)=delete
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1973
bool isForwardingAliasSet() const
Return true if this alias set should be ignored as part of the AliasSetTracker object.