LLVM  6.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 MemSetInst;
41 class MemTransferInst;
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  uint64_t 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(uint64_t 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  uint64_t 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  /// True if this alias set contains volatile loads or stores.
179  unsigned Volatile : 1;
180 
181  unsigned SetSize = 0;
182 
183  void addRef() { ++RefCount; }
184 
185  void dropRef(AliasSetTracker &AST) {
186  assert(RefCount >= 1 && "Invalid reference count detected!");
187  if (--RefCount == 0)
188  removeFromTracker(AST);
189  }
190 
191  Instruction *getUnknownInst(unsigned i) const {
192  assert(i < UnknownInsts.size());
193  return cast_or_null<Instruction>(UnknownInsts[i]);
194  }
195 
196 public:
197  AliasSet(const AliasSet &) = delete;
198  AliasSet &operator=(const AliasSet &) = delete;
199 
200  /// Accessors...
201  bool isRef() const { return Access & RefAccess; }
202  bool isMod() const { return Access & ModAccess; }
203  bool isMustAlias() const { return Alias == SetMustAlias; }
204  bool isMayAlias() const { return Alias == SetMayAlias; }
205 
206  /// Return true if this alias set contains volatile loads or stores.
207  bool isVolatile() const { return Volatile; }
208 
209  /// Return true if this alias set should be ignored as part of the
210  /// AliasSetTracker object.
211  bool isForwardingAliasSet() const { return Forward; }
212 
213  /// Merge the specified alias set into this alias set.
214  void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);
215 
216  // Alias Set iteration - Allow access to all of the pointers which are part of
217  // this alias set.
218  class iterator;
219  iterator begin() const { return iterator(PtrList); }
220  iterator end() const { return iterator(); }
221  bool empty() const { return PtrList == nullptr; }
222 
223  // Unfortunately, ilist::size() is linear, so we have to add code to keep
224  // track of the list's exact size.
225  unsigned size() { return SetSize; }
226 
227  void print(raw_ostream &OS) const;
228  void dump() const;
229 
230  /// Define an iterator for alias sets... this is just a forward iterator.
231  class iterator : public std::iterator<std::forward_iterator_tag,
232  PointerRec, ptrdiff_t> {
233  PointerRec *CurNode;
234 
235  public:
236  explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {}
237 
238  bool operator==(const iterator& x) const {
239  return CurNode == x.CurNode;
240  }
241  bool operator!=(const iterator& x) const { return !operator==(x); }
242 
243  value_type &operator*() const {
244  assert(CurNode && "Dereferencing AliasSet.end()!");
245  return *CurNode;
246  }
247  value_type *operator->() const { return &operator*(); }
248 
249  Value *getPointer() const { return CurNode->getValue(); }
250  uint64_t getSize() const { return CurNode->getSize(); }
251  AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); }
252 
253  iterator& operator++() { // Preincrement
254  assert(CurNode && "Advancing past AliasSet.end()!");
255  CurNode = CurNode->getNext();
256  return *this;
257  }
258  iterator operator++(int) { // Postincrement
259  iterator tmp = *this; ++*this; return tmp;
260  }
261  };
262 
263 private:
264  // Can only be created by AliasSetTracker.
265  AliasSet()
266  : PtrListEnd(&PtrList), RefCount(0), AliasAny(false), Access(NoAccess),
267  Alias(SetMustAlias), Volatile(false) {}
268 
269  PointerRec *getSomePointer() const {
270  return PtrList;
271  }
272 
273  /// Return the real alias set this represents. If this has been merged with
274  /// another set and is forwarding, return the ultimate destination set. This
275  /// also implements the union-find collapsing as well.
276  AliasSet *getForwardedTarget(AliasSetTracker &AST) {
277  if (!Forward) return this;
278 
279  AliasSet *Dest = Forward->getForwardedTarget(AST);
280  if (Dest != Forward) {
281  Dest->addRef();
282  Forward->dropRef(AST);
283  Forward = Dest;
284  }
285  return Dest;
286  }
287 
288  void removeFromTracker(AliasSetTracker &AST);
289 
290  void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size,
291  const AAMDNodes &AAInfo,
292  bool KnownMustAlias = false);
293  void addUnknownInst(Instruction *I, AliasAnalysis &AA);
294 
295  void removeUnknownInst(AliasSetTracker &AST, Instruction *I) {
296  bool WasEmpty = UnknownInsts.empty();
297  for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
298  if (UnknownInsts[i] == I) {
299  UnknownInsts[i] = UnknownInsts.back();
300  UnknownInsts.pop_back();
301  --i; --e; // Revisit the moved entry.
302  }
303  if (!WasEmpty && UnknownInsts.empty())
304  dropRef(AST);
305  }
306 
307  void setVolatile() { Volatile = true; }
308 
309 public:
310  /// Return true if the specified pointer "may" (or must) alias one of the
311  /// members in the set.
312  bool aliasesPointer(const Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo,
313  AliasAnalysis &AA) const;
314  bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const;
315 };
316 
317 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
318  AS.print(OS);
319  return OS;
320 }
321 
323  /// A CallbackVH to arrange for AliasSetTracker to be notified whenever a
324  /// Value is deleted.
325  class ASTCallbackVH final : public CallbackVH {
326  AliasSetTracker *AST;
327 
328  void deleted() override;
329  void allUsesReplacedWith(Value *) override;
330 
331  public:
332  ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr);
333 
334  ASTCallbackVH &operator=(Value *V);
335  };
336  /// Traits to tell DenseMap that tell us how to compare and hash the value
337  /// handle.
338  struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {};
339 
340  AliasAnalysis &AA;
341  ilist<AliasSet> AliasSets;
342 
343  using PointerMapType = DenseMap<ASTCallbackVH, AliasSet::PointerRec *,
344  ASTCallbackVHDenseMapInfo>;
345 
346  // Map from pointers to their node
347  PointerMapType PointerMap;
348 
349 public:
350  /// Create an empty collection of AliasSets, and use the specified alias
351  /// analysis object to disambiguate load and store addresses.
352  explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
354 
355  /// These methods are used to add different types of instructions to the alias
356  /// sets. Adding a new instruction can result in one of three actions
357  /// happening:
358  ///
359  /// 1. If the instruction doesn't alias any other sets, create a new set.
360  /// 2. If the instruction aliases exactly one set, add it to the set
361  /// 3. If the instruction aliases multiple sets, merge the sets, and add
362  /// the instruction to the result.
363  ///
364  /// These methods return true if inserting the instruction resulted in the
365  /// addition of a new alias set (i.e., the pointer did not alias anything).
366  ///
367  void add(Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo); // Add a loc.
368  void add(LoadInst *LI);
369  void add(StoreInst *SI);
370  void add(VAArgInst *VAAI);
371  void add(MemSetInst *MSI);
372  void add(MemTransferInst *MTI);
373  void add(Instruction *I); // Dispatch to one of the other add methods...
374  void add(BasicBlock &BB); // Add all instructions in basic block
375  void add(const AliasSetTracker &AST); // Add alias relations from another AST
376  void addUnknown(Instruction *I);
377 
378  void clear();
379 
380  /// Return the alias sets that are active.
381  const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
382 
383  /// Return the alias set that the specified pointer lives in. If the New
384  /// argument is non-null, this method sets the value to true if a new alias
385  /// set is created to contain the pointer (because the pointer didn't alias
386  /// anything).
387  AliasSet &getAliasSetForPointer(Value *P, uint64_t Size,
388  const AAMDNodes &AAInfo);
389 
390  /// Return the alias set containing the location specified if one exists,
391  /// otherwise return null.
392  AliasSet *getAliasSetForPointerIfExists(const Value *P, uint64_t Size,
393  const AAMDNodes &AAInfo) {
394  return mergeAliasSetsForPointer(P, Size, AAInfo);
395  }
396 
397  /// Return true if the specified instruction "may" (or must) alias one of the
398  /// members in any of the sets.
399  bool containsUnknown(const Instruction *I) const;
400 
401  /// Return the underlying alias analysis object used by this tracker.
402  AliasAnalysis &getAliasAnalysis() const { return AA; }
403 
404  /// This method is used to remove a pointer value from the AliasSetTracker
405  /// entirely. It should be used when an instruction is deleted from the
406  /// program to update the AST. If you don't use this, you would have dangling
407  /// pointers to deleted instructions.
408  void deleteValue(Value *PtrVal);
409 
410  /// This method should be used whenever a preexisting value in the program is
411  /// copied or cloned, introducing a new value. Note that it is ok for clients
412  /// that use this method to introduce the same value multiple times: if the
413  /// tracker already knows about a value, it will ignore the request.
414  void copyValue(Value *From, Value *To);
415 
418 
419  const_iterator begin() const { return AliasSets.begin(); }
420  const_iterator end() const { return AliasSets.end(); }
421 
422  iterator begin() { return AliasSets.begin(); }
423  iterator end() { return AliasSets.end(); }
424 
425  void print(raw_ostream &OS) const;
426  void dump() const;
427 
428 private:
429  friend class AliasSet;
430 
431  // The total number of pointers contained in all "may" alias sets.
432  unsigned TotalMayAliasSetSize = 0;
433 
434  // A non-null value signifies this AST is saturated. A saturated AST lumps
435  // all pointers into a single "May" set.
436  AliasSet *AliasAnyAS = nullptr;
437 
438  void removeAliasSet(AliasSet *AS);
439 
440  /// Just like operator[] on the map, except that it creates an entry for the
441  /// pointer if it doesn't already exist.
442  AliasSet::PointerRec &getEntryFor(Value *V) {
443  AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
444  if (!Entry)
445  Entry = new AliasSet::PointerRec(V);
446  return *Entry;
447  }
448 
449  AliasSet &addPointer(Value *P, uint64_t Size, const AAMDNodes &AAInfo,
450  AliasSet::AccessLattice E);
451  AliasSet *mergeAliasSetsForPointer(const Value *Ptr, uint64_t Size,
452  const AAMDNodes &AAInfo);
453 
454  /// Merge all alias sets into a single set that is considered to alias any
455  /// pointer.
456  AliasSet &mergeAllAliasSets();
457 
458  AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
459 };
460 
462  AST.print(OS);
463  return OS;
464 }
465 
466 } // end namespace llvm
467 
468 #endif // LLVM_ANALYSIS_ALIASSETTRACKER_H
void mergeSetIn(AliasSet &AS, AliasSetTracker &AST)
Merge the specified alias set into this alias set.
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.
This class wraps the llvm.memset intrinsic.
An instruction for reading from memory.
Definition: Instructions.h:164
AAMDNodes getAAInfo() const
value_type & operator*() const
bool isMustAlias() const
Value * getPointer() const
APInt operator*(APInt a, uint64_t RHS)
Definition: APInt.h:2070
iterator begin() const
bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const
An instruction for storing to memory.
Definition: Instructions.h:306
#define P(N)
uint64_t getSize() const
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 ...
bool isMod() const
const AMDGPUAS & AS
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:403
AliasSet * getAliasSetForPointerIfExists(const Value *P, uint64_t Size, const AAMDNodes &AAInfo)
Return the alias set containing the location specified if one exists, otherwise return null...
Iterator for intrusive lists based on ilist_node.
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:642
bool isRef() const
Accessors...
static void clear(coro::Shape &Shape)
Definition: Coroutines.cpp:210
iterator end() const
const ilist< AliasSet > & getAliasSets() const
Return the alias sets that are active.
This class wraps the llvm.memcpy/memmove intrinsics.
#define I(x, y, z)
Definition: MD5.cpp:58
bool isVolatile() const
Return true if this alias set contains volatile loads or stores.
value_type * operator->() const
raw_ostream & operator<<(raw_ostream &OS, const APInt &I)
Definition: APInt.h:2018
const_iterator begin() const
iterator(PointerRec *CN=nullptr)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
bool aliasesPointer(const Value *Ptr, uint64_t Size, const AAMDNodes &AAInfo, AliasAnalysis &AA) const
Return true if the specified pointer "may" (or must) alias one of the members in the set...
LLVM Value Representation.
Definition: Value.h:73
constexpr char Size[]
Key for Kernel::Arg::Metadata::mSize.
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:669
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:44
bool empty() const
Value handle with callbacks on RAUW and destruction.
Definition: ValueHandle.h:389
AliasSet & operator=(const AliasSet &)=delete
bool operator==(uint64_t V1, const APInt &V2)
Definition: APInt.h:1946
bool isForwardingAliasSet() const
Return true if this alias set should be ignored as part of the AliasSetTracker object.