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