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.TBAA || !Intersection.Scope ||
91  !Intersection.NoAlias) {
92  // NewAAInfo conflicts with AAInfo.
94  SizeChanged = true;
95  }
96  AAInfo = Intersection;
97  }
98  return SizeChanged;
99  }
100 
101  LocationSize getSize() const {
102  assert(isSizeSet() && "Getting an unset size!");
103  return Size;
104  }
105 
106  /// Return the AAInfo, or null if there is no information or conflicting
107  /// information.
108  AAMDNodes getAAInfo() const {
109  // If we have missing or conflicting AAInfo, return null.
110  if (AAInfo == DenseMapInfo<AAMDNodes>::getEmptyKey() ||
112  return AAMDNodes();
113  return AAInfo;
114  }
115 
116  AliasSet *getAliasSet(AliasSetTracker &AST) {
117  assert(AS && "No AliasSet yet!");
118  if (AS->Forward) {
119  AliasSet *OldAS = AS;
120  AS = OldAS->getForwardedTarget(AST);
121  AS->addRef();
122  OldAS->dropRef(AST);
123  }
124  return AS;
125  }
126 
127  void setAliasSet(AliasSet *as) {
128  assert(!AS && "Already have an alias set!");
129  AS = as;
130  }
131 
132  void eraseFromList() {
133  if (NextInList) NextInList->PrevInList = PrevInList;
134  *PrevInList = NextInList;
135  if (AS->PtrListEnd == &NextInList) {
136  AS->PtrListEnd = PrevInList;
137  assert(*AS->PtrListEnd == nullptr && "List not terminated right!");
138  }
139  delete this;
140  }
141  };
142 
143  // Doubly linked list of nodes.
144  PointerRec *PtrList = nullptr;
145  PointerRec **PtrListEnd;
146  // Forwarding pointer.
147  AliasSet *Forward = nullptr;
148 
149  /// All instructions without a specific address in this alias set.
150  /// In rare cases this vector can have a null'ed out WeakVH
151  /// instances (can happen if some other loop pass deletes an
152  /// instruction in this list).
153  std::vector<WeakVH> UnknownInsts;
154 
155  /// Number of nodes pointing to this AliasSet plus the number of AliasSets
156  /// forwarding to it.
157  unsigned RefCount : 27;
158 
159  // Signifies that this set should be considered to alias any pointer.
160  // Use when the tracker holding this set is saturated.
161  unsigned AliasAny : 1;
162 
163  /// The kinds of access this alias set models.
164  ///
165  /// We keep track of whether this alias set merely refers to the locations of
166  /// memory (and not any particular access), whether it modifies or references
167  /// the memory, or whether it does both. The lattice goes from "NoAccess" to
168  /// either RefAccess or ModAccess, then to ModRefAccess as necessary.
169  enum AccessLattice {
170  NoAccess = 0,
171  RefAccess = 1,
172  ModAccess = 2,
173  ModRefAccess = RefAccess | ModAccess
174  };
175  unsigned Access : 2;
176 
177  /// The kind of alias relationship between pointers of the set.
178  ///
179  /// These represent conservatively correct alias results between any members
180  /// of the set. We represent these independently of the values of alias
181  /// results in order to pack it into a single bit. Lattice goes from
182  /// MustAlias to MayAlias.
183  enum AliasLattice {
184  SetMustAlias = 0, SetMayAlias = 1
185  };
186  unsigned Alias : 1;
187 
188  unsigned SetSize = 0;
189 
190  void addRef() { ++RefCount; }
191 
192  void dropRef(AliasSetTracker &AST) {
193  assert(RefCount >= 1 && "Invalid reference count detected!");
194  if (--RefCount == 0)
195  removeFromTracker(AST);
196  }
197 
198  Instruction *getUnknownInst(unsigned i) const {
199  assert(i < UnknownInsts.size());
200  return cast_or_null<Instruction>(UnknownInsts[i]);
201  }
202 
203 public:
204  AliasSet(const AliasSet &) = delete;
205  AliasSet &operator=(const AliasSet &) = delete;
206 
207  /// Accessors...
208  bool isRef() const { return Access & RefAccess; }
209  bool isMod() const { return Access & ModAccess; }
210  bool isMustAlias() const { return Alias == SetMustAlias; }
211  bool isMayAlias() const { return Alias == SetMayAlias; }
212 
213  /// Return true if this alias set should be ignored as part of the
214  /// AliasSetTracker object.
215  bool isForwardingAliasSet() const { return Forward; }
216 
217  /// Merge the specified alias set into this alias set.
218  void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);
219 
220  // Alias Set iteration - Allow access to all of the pointers which are part of
221  // this alias set.
222  class iterator;
223  iterator begin() const { return iterator(PtrList); }
224  iterator end() const { return iterator(); }
225  bool empty() const { return PtrList == nullptr; }
226 
227  // Unfortunately, ilist::size() is linear, so we have to add code to keep
228  // track of the list's exact size.
229  unsigned size() { return SetSize; }
230 
231  /// If this alias set is known to contain a single instruction and *only* a
232  /// single unique instruction, return it. Otherwise, return nullptr.
234 
235  void print(raw_ostream &OS) const;
236  void dump() const;
237 
238  /// Define an iterator for alias sets... this is just a forward iterator.
239  class iterator : public std::iterator<std::forward_iterator_tag,
240  PointerRec, ptrdiff_t> {
241  PointerRec *CurNode;
242 
243  public:
244  explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {}
245 
246  bool operator==(const iterator& x) const {
247  return CurNode == x.CurNode;
248  }
249  bool operator!=(const iterator& x) const { return !operator==(x); }
250 
251  value_type &operator*() const {
252  assert(CurNode && "Dereferencing AliasSet.end()!");
253  return *CurNode;
254  }
255  value_type *operator->() const { return &operator*(); }
256 
257  Value *getPointer() const { return CurNode->getValue(); }
258  LocationSize getSize() const { return CurNode->getSize(); }
259  AAMDNodes getAAInfo() const { return CurNode->getAAInfo(); }
260 
261  iterator& operator++() { // Preincrement
262  assert(CurNode && "Advancing past AliasSet.end()!");
263  CurNode = CurNode->getNext();
264  return *this;
265  }
266  iterator operator++(int) { // Postincrement
267  iterator tmp = *this; ++*this; return tmp;
268  }
269  };
270 
271 private:
272  // Can only be created by AliasSetTracker.
273  AliasSet()
274  : PtrListEnd(&PtrList), RefCount(0), AliasAny(false), Access(NoAccess),
275  Alias(SetMustAlias) {}
276 
277  PointerRec *getSomePointer() const {
278  return PtrList;
279  }
280 
281  /// Return the real alias set this represents. If this has been merged with
282  /// another set and is forwarding, return the ultimate destination set. This
283  /// also implements the union-find collapsing as well.
284  AliasSet *getForwardedTarget(AliasSetTracker &AST) {
285  if (!Forward) return this;
286 
287  AliasSet *Dest = Forward->getForwardedTarget(AST);
288  if (Dest != Forward) {
289  Dest->addRef();
290  Forward->dropRef(AST);
291  Forward = Dest;
292  }
293  return Dest;
294  }
295 
296  void removeFromTracker(AliasSetTracker &AST);
297 
298  void addPointer(AliasSetTracker &AST, PointerRec &Entry, LocationSize Size,
299  const AAMDNodes &AAInfo, bool KnownMustAlias = false,
300  bool SkipSizeUpdate = false);
301  void addUnknownInst(Instruction *I, AliasAnalysis &AA);
302 
303  void removeUnknownInst(AliasSetTracker &AST, Instruction *I) {
304  bool WasEmpty = UnknownInsts.empty();
305  for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
306  if (UnknownInsts[i] == I) {
307  UnknownInsts[i] = UnknownInsts.back();
308  UnknownInsts.pop_back();
309  --i; --e; // Revisit the moved entry.
310  }
311  if (!WasEmpty && UnknownInsts.empty())
312  dropRef(AST);
313  }
314 
315 public:
316  /// If the specified pointer "may" (or must) alias one of the members in the
317  /// set return the appropriate AliasResult. Otherwise return NoAlias.
318  AliasResult aliasesPointer(const Value *Ptr, LocationSize Size,
319  const AAMDNodes &AAInfo, AliasAnalysis &AA) const;
320  bool aliasesUnknownInst(const Instruction *Inst, AliasAnalysis &AA) const;
321 };
322 
323 inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
324  AS.print(OS);
325  return OS;
326 }
327 
329  /// A CallbackVH to arrange for AliasSetTracker to be notified whenever a
330  /// Value is deleted.
331  class ASTCallbackVH final : public CallbackVH {
332  AliasSetTracker *AST;
333 
334  void deleted() override;
335  void allUsesReplacedWith(Value *) override;
336 
337  public:
338  ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr);
339 
340  ASTCallbackVH &operator=(Value *V);
341  };
342  /// Traits to tell DenseMap that tell us how to compare and hash the value
343  /// handle.
344  struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {};
345 
346  AliasAnalysis &AA;
347  MemorySSA *MSSA;
348  Loop *L;
349  ilist<AliasSet> AliasSets;
350 
351  using PointerMapType = DenseMap<ASTCallbackVH, AliasSet::PointerRec *,
352  ASTCallbackVHDenseMapInfo>;
353 
354  // Map from pointers to their node
355  PointerMapType PointerMap;
356 
357 public:
358  /// Create an empty collection of AliasSets, and use the specified alias
359  /// analysis object to disambiguate load and store addresses.
360  explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
362  : AA(aa), MSSA(mssa), L(l) {}
364 
365  /// These methods are used to add different types of instructions to the alias
366  /// sets. Adding a new instruction can result in one of three actions
367  /// happening:
368  ///
369  /// 1. If the instruction doesn't alias any other sets, create a new set.
370  /// 2. If the instruction aliases exactly one set, add it to the set
371  /// 3. If the instruction aliases multiple sets, merge the sets, and add
372  /// the instruction to the result.
373  ///
374  /// These methods return true if inserting the instruction resulted in the
375  /// addition of a new alias set (i.e., the pointer did not alias anything).
376  ///
377  void add(Value *Ptr, LocationSize Size, const AAMDNodes &AAInfo); // Add a loc
378  void add(LoadInst *LI);
379  void add(StoreInst *SI);
380  void add(VAArgInst *VAAI);
381  void add(AnyMemSetInst *MSI);
382  void add(AnyMemTransferInst *MTI);
383  void add(Instruction *I); // Dispatch to one of the other add methods...
384  void add(BasicBlock &BB); // Add all instructions in basic block
385  void add(const AliasSetTracker &AST); // Add alias relations from another AST
386  void addUnknown(Instruction *I);
387  void addAllInstructionsInLoopUsingMSSA();
388 
389  void clear();
390 
391  /// Return the alias sets that are active.
392  const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
393 
394  /// Return the alias set which contains the specified memory location. If
395  /// the memory location aliases two or more existing alias sets, will have
396  /// the effect of merging those alias sets before the single resulting alias
397  /// set is returned.
398  AliasSet &getAliasSetFor(const MemoryLocation &MemLoc);
399 
400  /// Return the underlying alias analysis object used by this tracker.
401  AliasAnalysis &getAliasAnalysis() const { return AA; }
402 
403  /// This method is used to remove a pointer value from the AliasSetTracker
404  /// entirely. It should be used when an instruction is deleted from the
405  /// program to update the AST. If you don't use this, you would have dangling
406  /// pointers to deleted instructions.
407  void deleteValue(Value *PtrVal);
408 
409  /// This method should be used whenever a preexisting value in the program is
410  /// copied or cloned, introducing a new value. Note that it is ok for clients
411  /// that use this method to introduce the same value multiple times: if the
412  /// tracker already knows about a value, it will ignore the request.
413  void copyValue(Value *From, Value *To);
414 
417 
418  const_iterator begin() const { return AliasSets.begin(); }
419  const_iterator end() const { return AliasSets.end(); }
420 
421  iterator begin() { return AliasSets.begin(); }
422  iterator end() { return AliasSets.end(); }
423 
424  void print(raw_ostream &OS) const;
425  void dump() const;
426 
427 private:
428  friend class AliasSet;
429 
430  // The total number of pointers contained in all "may" alias sets.
431  unsigned TotalMayAliasSetSize = 0;
432 
433  // A non-null value signifies this AST is saturated. A saturated AST lumps
434  // all pointers into a single "May" set.
435  AliasSet *AliasAnyAS = nullptr;
436 
437  void removeAliasSet(AliasSet *AS);
438 
439  /// Just like operator[] on the map, except that it creates an entry for the
440  /// pointer if it doesn't already exist.
441  AliasSet::PointerRec &getEntryFor(Value *V) {
442  AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
443  if (!Entry)
444  Entry = new AliasSet::PointerRec(V);
445  return *Entry;
446  }
447 
448  AliasSet &addPointer(MemoryLocation Loc, AliasSet::AccessLattice E);
449  AliasSet *mergeAliasSetsForPointer(const Value *Ptr, LocationSize Size,
450  const AAMDNodes &AAInfo,
451  bool &MustAliasAll);
452 
453  /// Merge all alias sets into a single set that is considered to alias any
454  /// pointer.
455  AliasSet &mergeAllAliasSets();
456 
457  AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
458 };
459 
461  AST.print(OS);
462  return OS;
463 }
464 
465 } // end namespace llvm
466 
467 #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:169
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:2099
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:325
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:1425
AliasSetTracker(AliasAnalysis &aa)
Create an empty collection of AliasSets, and use the specified alias analysis object to disambiguate ...
constexpr double e
Definition: MathExtras.h:57
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:215
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:2047
const_iterator begin() const
iterator(PointerRec *CN=nullptr)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
LLVM Value Representation.
Definition: Value.h:74
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:1975
bool isForwardingAliasSet() const
Return true if this alias set should be ignored as part of the AliasSetTracker object.