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 interface
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/ilist.h"
22#include "llvm/ADT/ilist_node.h"
23#include "llvm/IR/ValueHandle.h"
24#include <vector>
25
26namespace llvm {
27
28class AliasAnalysis;
29class LoadInst;
30class StoreInst;
31class VAArgInst;
32class AliasSetTracker;
33class AliasSet;
34
35class AliasSet : public ilist_node<AliasSet> {
36  friend class AliasSetTracker;
37
38  class PointerRec {
39    Value *Val;  // The pointer this record corresponds to.
40    PointerRec **PrevInList, *NextInList;
41    AliasSet *AS;
42    uint64_t Size;
43    const MDNode *TBAAInfo;
44  public:
45    PointerRec(Value *V)
46      : Val(V), PrevInList(nullptr), NextInList(nullptr), AS(nullptr), Size(0),
47        TBAAInfo(DenseMapInfo<const MDNode *>::getEmptyKey()) {}
48
49    Value *getValue() const { return Val; }
50
51    PointerRec *getNext() const { return NextInList; }
52    bool hasAliasSet() const { return AS != nullptr; }
53
54    PointerRec** setPrevInList(PointerRec **PIL) {
55      PrevInList = PIL;
56      return &NextInList;
57    }
58
59    void updateSizeAndTBAAInfo(uint64_t NewSize, const MDNode *NewTBAAInfo) {
60      if (NewSize > Size) Size = NewSize;
61
62      if (TBAAInfo == DenseMapInfo<const MDNode *>::getEmptyKey())
63        // We don't have a TBAAInfo yet. Set it to NewTBAAInfo.
64        TBAAInfo = NewTBAAInfo;
65      else if (TBAAInfo != NewTBAAInfo)
66        // NewTBAAInfo conflicts with TBAAInfo.
67        TBAAInfo = DenseMapInfo<const MDNode *>::getTombstoneKey();
68    }
69
70    uint64_t getSize() const { return Size; }
71
72    /// getTBAAInfo - Return the TBAAInfo, or null if there is no
73    /// information or conflicting information.
74    const MDNode *getTBAAInfo() const {
75      // If we have missing or conflicting TBAAInfo, return null.
76      if (TBAAInfo == DenseMapInfo<const MDNode *>::getEmptyKey() ||
77          TBAAInfo == DenseMapInfo<const MDNode *>::getTombstoneKey())
78        return nullptr;
79      return TBAAInfo;
80    }
81
82    AliasSet *getAliasSet(AliasSetTracker &AST) {
83      assert(AS && "No AliasSet yet!");
84      if (AS->Forward) {
85        AliasSet *OldAS = AS;
86        AS = OldAS->getForwardedTarget(AST);
87        AS->addRef();
88        OldAS->dropRef(AST);
89      }
90      return AS;
91    }
92
93    void setAliasSet(AliasSet *as) {
94      assert(!AS && "Already have an alias set!");
95      AS = as;
96    }
97
98    void eraseFromList() {
99      if (NextInList) NextInList->PrevInList = PrevInList;
100      *PrevInList = NextInList;
101      if (AS->PtrListEnd == &NextInList) {
102        AS->PtrListEnd = PrevInList;
103        assert(*AS->PtrListEnd == nullptr && "List not terminated right!");
104      }
105      delete this;
106    }
107  };
108
109  PointerRec *PtrList, **PtrListEnd;  // Doubly linked list of nodes.
110  AliasSet *Forward;             // Forwarding pointer.
111
112  // All instructions without a specific address in this alias set.
113  std::vector<AssertingVH<Instruction> > UnknownInsts;
114
115  // RefCount - Number of nodes pointing to this AliasSet plus the number of
116  // AliasSets forwarding to it.
117  unsigned RefCount : 28;
118
119  /// AccessType - Keep track of whether this alias set merely refers to the
120  /// locations of memory, whether it modifies the memory, or whether it does
121  /// both.  The lattice goes from "NoModRef" to either Refs or Mods, then to
122  /// ModRef as necessary.
123  ///
124  enum AccessType {
125    NoModRef = 0, Refs = 1,         // Ref = bit 1
126    Mods     = 2, ModRef = 3        // Mod = bit 2
127  };
128  unsigned AccessTy : 2;
129
130  /// AliasType - Keep track the relationships between the pointers in the set.
131  /// Lattice goes from MustAlias to MayAlias.
132  ///
133  enum AliasType {
134    MustAlias = 0, MayAlias = 1
135  };
136  unsigned AliasTy : 1;
137
138  // Volatile - True if this alias set contains volatile loads or stores.
139  bool Volatile : 1;
140
141  void addRef() { ++RefCount; }
142  void dropRef(AliasSetTracker &AST) {
143    assert(RefCount >= 1 && "Invalid reference count detected!");
144    if (--RefCount == 0)
145      removeFromTracker(AST);
146  }
147
148  Instruction *getUnknownInst(unsigned i) const {
149    assert(i < UnknownInsts.size());
150    return UnknownInsts[i];
151  }
152
153public:
154  /// Accessors...
155  bool isRef() const { return AccessTy & Refs; }
156  bool isMod() const { return AccessTy & Mods; }
157  bool isMustAlias() const { return AliasTy == MustAlias; }
158  bool isMayAlias()  const { return AliasTy == MayAlias; }
159
160  // isVolatile - Return true if this alias set contains volatile loads or
161  // stores.
162  bool isVolatile() const { return Volatile; }
163
164  /// isForwardingAliasSet - Return true if this alias set should be ignored as
165  /// part of the AliasSetTracker object.
166  bool isForwardingAliasSet() const { return Forward; }
167
168  /// mergeSetIn - Merge the specified alias set into this alias set...
169  ///
170  void mergeSetIn(AliasSet &AS, AliasSetTracker &AST);
171
172  // Alias Set iteration - Allow access to all of the pointer which are part of
173  // this alias set...
174  class iterator;
175  iterator begin() const { return iterator(PtrList); }
176  iterator end()   const { return iterator(); }
177  bool empty() const { return PtrList == nullptr; }
178
179  void print(raw_ostream &OS) const;
180  void dump() const;
181
182  /// Define an iterator for alias sets... this is just a forward iterator.
183  class iterator : public std::iterator<std::forward_iterator_tag,
184                                        PointerRec, ptrdiff_t> {
185    PointerRec *CurNode;
186  public:
187    explicit iterator(PointerRec *CN = nullptr) : CurNode(CN) {}
188
189    bool operator==(const iterator& x) const {
190      return CurNode == x.CurNode;
191    }
192    bool operator!=(const iterator& x) const { return !operator==(x); }
193
194    const iterator &operator=(const iterator &I) {
195      CurNode = I.CurNode;
196      return *this;
197    }
198
199    value_type &operator*() const {
200      assert(CurNode && "Dereferencing AliasSet.end()!");
201      return *CurNode;
202    }
203    value_type *operator->() const { return &operator*(); }
204
205    Value *getPointer() const { return CurNode->getValue(); }
206    uint64_t getSize() const { return CurNode->getSize(); }
207    const MDNode *getTBAAInfo() const { return CurNode->getTBAAInfo(); }
208
209    iterator& operator++() {                // Preincrement
210      assert(CurNode && "Advancing past AliasSet.end()!");
211      CurNode = CurNode->getNext();
212      return *this;
213    }
214    iterator operator++(int) { // Postincrement
215      iterator tmp = *this; ++*this; return tmp;
216    }
217  };
218
219private:
220  // Can only be created by AliasSetTracker. Also, ilist creates one
221  // to serve as a sentinel.
222  friend struct ilist_sentinel_traits<AliasSet>;
223  AliasSet()
224    : PtrList(nullptr), PtrListEnd(&PtrList), Forward(nullptr), RefCount(0),
225      AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) {
226  }
227
228  AliasSet(const AliasSet &AS) LLVM_DELETED_FUNCTION;
229  void operator=(const AliasSet &AS) LLVM_DELETED_FUNCTION;
230
231  PointerRec *getSomePointer() const {
232    return PtrList;
233  }
234
235  /// getForwardedTarget - Return the real alias set this represents.  If this
236  /// has been merged with another set and is forwarding, return the ultimate
237  /// destination set.  This also implements the union-find collapsing as well.
238  AliasSet *getForwardedTarget(AliasSetTracker &AST) {
239    if (!Forward) return this;
240
241    AliasSet *Dest = Forward->getForwardedTarget(AST);
242    if (Dest != Forward) {
243      Dest->addRef();
244      Forward->dropRef(AST);
245      Forward = Dest;
246    }
247    return Dest;
248  }
249
250  void removeFromTracker(AliasSetTracker &AST);
251
252  void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size,
253                  const MDNode *TBAAInfo,
254                  bool KnownMustAlias = false);
255  void addUnknownInst(Instruction *I, AliasAnalysis &AA);
256  void removeUnknownInst(Instruction *I) {
257    for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i)
258      if (UnknownInsts[i] == I) {
259        UnknownInsts[i] = UnknownInsts.back();
260        UnknownInsts.pop_back();
261        --i; --e;  // Revisit the moved entry.
262      }
263  }
264  void setVolatile() { Volatile = true; }
265
266public:
267  /// aliasesPointer - Return true if the specified pointer "may" (or must)
268  /// alias one of the members in the set.
269  ///
270  bool aliasesPointer(const Value *Ptr, uint64_t Size, const MDNode *TBAAInfo,
271                      AliasAnalysis &AA) const;
272  bool aliasesUnknownInst(Instruction *Inst, AliasAnalysis &AA) const;
273};
274
275inline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) {
276  AS.print(OS);
277  return OS;
278}
279
280
281class AliasSetTracker {
282  /// CallbackVH - A CallbackVH to arrange for AliasSetTracker to be
283  /// notified whenever a Value is deleted.
284  class ASTCallbackVH : public CallbackVH {
285    AliasSetTracker *AST;
286    void deleted() override;
287    void allUsesReplacedWith(Value *) override;
288  public:
289    ASTCallbackVH(Value *V, AliasSetTracker *AST = nullptr);
290    ASTCallbackVH &operator=(Value *V);
291  };
292  /// ASTCallbackVHDenseMapInfo - Traits to tell DenseMap that tell us how to
293  /// compare and hash the value handle.
294  struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {};
295
296  AliasAnalysis &AA;
297  ilist<AliasSet> AliasSets;
298
299  typedef DenseMap<ASTCallbackVH, AliasSet::PointerRec*,
300                   ASTCallbackVHDenseMapInfo>
301    PointerMapType;
302
303  // Map from pointers to their node
304  PointerMapType PointerMap;
305
306public:
307  /// AliasSetTracker ctor - Create an empty collection of AliasSets, and use
308  /// the specified alias analysis object to disambiguate load and store
309  /// addresses.
310  explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
311  ~AliasSetTracker() { clear(); }
312
313  /// add methods - These methods are used to add different types of
314  /// instructions to the alias sets.  Adding a new instruction can result in
315  /// one of three actions happening:
316  ///
317  ///   1. If the instruction doesn't alias any other sets, create a new set.
318  ///   2. If the instruction aliases exactly one set, add it to the set
319  ///   3. If the instruction aliases multiple sets, merge the sets, and add
320  ///      the instruction to the result.
321  ///
322  /// These methods return true if inserting the instruction resulted in the
323  /// addition of a new alias set (i.e., the pointer did not alias anything).
324  ///
325  bool add(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo); // Add a location
326  bool add(LoadInst *LI);
327  bool add(StoreInst *SI);
328  bool add(VAArgInst *VAAI);
329  bool add(Instruction *I);       // Dispatch to one of the other add methods...
330  void add(BasicBlock &BB);       // Add all instructions in basic block
331  void add(const AliasSetTracker &AST); // Add alias relations from another AST
332  bool addUnknown(Instruction *I);
333
334  /// remove methods - These methods are used to remove all entries that might
335  /// be aliased by the specified instruction.  These methods return true if any
336  /// alias sets were eliminated.
337  // Remove a location
338  bool remove(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo);
339  bool remove(LoadInst *LI);
340  bool remove(StoreInst *SI);
341  bool remove(VAArgInst *VAAI);
342  bool remove(Instruction *I);
343  void remove(AliasSet &AS);
344  bool removeUnknown(Instruction *I);
345
346  void clear();
347
348  /// getAliasSets - Return the alias sets that are active.
349  ///
350  const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
351
352  /// getAliasSetForPointer - Return the alias set that the specified pointer
353  /// lives in.  If the New argument is non-null, this method sets the value to
354  /// true if a new alias set is created to contain the pointer (because the
355  /// pointer didn't alias anything).
356  AliasSet &getAliasSetForPointer(Value *P, uint64_t Size,
357                                  const MDNode *TBAAInfo,
358                                  bool *New = nullptr);
359
360  /// getAliasSetForPointerIfExists - Return the alias set containing the
361  /// location specified if one exists, otherwise return null.
362  AliasSet *getAliasSetForPointerIfExists(Value *P, uint64_t Size,
363                                          const MDNode *TBAAInfo) {
364    return findAliasSetForPointer(P, Size, TBAAInfo);
365  }
366
367  /// containsPointer - Return true if the specified location is represented by
368  /// this alias set, false otherwise.  This does not modify the AST object or
369  /// alias sets.
370  bool containsPointer(Value *P, uint64_t Size, const MDNode *TBAAInfo) const;
371
372  /// getAliasAnalysis - Return the underlying alias analysis object used by
373  /// this tracker.
374  AliasAnalysis &getAliasAnalysis() const { return AA; }
375
376  /// deleteValue method - This method is used to remove a pointer value from
377  /// the AliasSetTracker entirely.  It should be used when an instruction is
378  /// deleted from the program to update the AST.  If you don't use this, you
379  /// would have dangling pointers to deleted instructions.
380  ///
381  void deleteValue(Value *PtrVal);
382
383  /// copyValue - This method should be used whenever a preexisting value in the
384  /// program is copied or cloned, introducing a new value.  Note that it is ok
385  /// for clients that use this method to introduce the same value multiple
386  /// times: if the tracker already knows about a value, it will ignore the
387  /// request.
388  ///
389  void copyValue(Value *From, Value *To);
390
391
392  typedef ilist<AliasSet>::iterator iterator;
393  typedef ilist<AliasSet>::const_iterator const_iterator;
394
395  const_iterator begin() const { return AliasSets.begin(); }
396  const_iterator end()   const { return AliasSets.end(); }
397
398  iterator begin() { return AliasSets.begin(); }
399  iterator end()   { return AliasSets.end(); }
400
401  void print(raw_ostream &OS) const;
402  void dump() const;
403
404private:
405  friend class AliasSet;
406  void removeAliasSet(AliasSet *AS);
407
408  // getEntryFor - Just like operator[] on the map, except that it creates an
409  // entry for the pointer if it doesn't already exist.
410  AliasSet::PointerRec &getEntryFor(Value *V) {
411    AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)];
412    if (!Entry)
413      Entry = new AliasSet::PointerRec(V);
414    return *Entry;
415  }
416
417  AliasSet &addPointer(Value *P, uint64_t Size, const MDNode *TBAAInfo,
418                       AliasSet::AccessType E,
419                       bool &NewSet) {
420    NewSet = false;
421    AliasSet &AS = getAliasSetForPointer(P, Size, TBAAInfo, &NewSet);
422    AS.AccessTy |= E;
423    return AS;
424  }
425  AliasSet *findAliasSetForPointer(const Value *Ptr, uint64_t Size,
426                                   const MDNode *TBAAInfo);
427
428  AliasSet *findAliasSetForUnknownInst(Instruction *Inst);
429};
430
431inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) {
432  AST.print(OS);
433  return OS;
434}
435
436} // End llvm namespace
437
438#endif
439