AliasSetTracker.h revision 3889a2cb05c36f30050941679d5fd55d45e6a3ed 
1//===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===//
2//
3// This file defines two classes: AliasSetTracker and AliasSet.  These interface
4// are used to classify a collection of pointer references into a maximal number
5// of disjoint sets.  Each AliasSet object constructed by the AliasSetTracker
6// object refers to memory disjoint from the other sets.
7//
8//===----------------------------------------------------------------------===//
9
10#ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H
11#define LLVM_ANALYSIS_ALIASSETTRACKER_H
12
13#include "llvm/Support/CallSite.h"
14#include "Support/iterator"
15#include "Support/hash_map"
16#include "Support/ilist"
17class AliasAnalysis;
18class LoadInst;
19class StoreInst;
20class AliasSetTracker;
21class AliasSet;
22
23class AliasSet {
24  friend class AliasSetTracker;
25
26  struct PointerRec;
27  typedef std::pair<Value* const, PointerRec> HashNodePair;
28
29  class PointerRec {
30    HashNodePair *NextInList;
31    AliasSet *AS;
32    unsigned Size;
33  public:
34    PointerRec() : NextInList(0), AS(0), Size(0) {}
35
36    HashNodePair *getNext() const { return NextInList; }
37    bool hasAliasSet() const { return AS != 0; }
38
39    void updateSize(unsigned NewSize) {
40      if (NewSize > Size) Size = NewSize;
41    }
42
43    unsigned getSize() const { return Size; }
44
45    AliasSet *getAliasSet(AliasSetTracker &AST) {
46      assert(AS && "No AliasSet yet!");
47      if (AS->Forward) {
48        AliasSet *OldAS = AS;
49        AS = OldAS->getForwardedTarget(AST);
50        if (--OldAS->RefCount == 0)
51          OldAS->removeFromTracker(AST);
52        AS->RefCount++;
53      }
54      return AS;
55    }
56
57    void setAliasSet(AliasSet *as) {
58      assert(AS == 0 && "Already have an alias set!");
59      AS = as;
60    }
61    void setTail(HashNodePair *T) {
62      assert(NextInList == 0 && "Already have tail!");
63      NextInList = T;
64    }
65  };
66
67  HashNodePair *PtrListHead, *PtrListTail; // Singly linked list of nodes
68  AliasSet *Forward;             // Forwarding pointer
69  AliasSet *Next, *Prev;         // Doubly linked list of AliasSets
70
71  std::vector<CallSite> CallSites; // All calls & invokes in this node
72
73  // RefCount - Number of nodes pointing to this AliasSet plus the number of
74  // AliasSets forwarding to it.
75  unsigned RefCount : 29;
76
77  /// AccessType - Keep track of whether this alias set merely refers to the
78  /// locations of memory, whether it modifies the memory, or whether it does
79  /// both.  The lattice goes from "NoModRef" to either Refs or Mods, then to
80  /// ModRef as neccesary.
81  ///
82  enum AccessType {
83    NoModRef = 0, Refs = 1,         // Ref = bit 1
84    Mods     = 2, ModRef = 3        // Mod = bit 2
85  };
86  unsigned AccessTy : 2;
87
88  /// AliasType - Keep track the relationships between the pointers in the set.
89  /// Lattice goes from MustAlias to MayAlias.
90  ///
91  enum AliasType {
92    MustAlias = 0, MayAlias = 1
93  };
94  unsigned AliasTy : 1;
95
96  friend class ilist_traits<AliasSet>;
97  AliasSet *getPrev() const { return Prev; }
98  AliasSet *getNext() const { return Next; }
99  void setPrev(AliasSet *P) { Prev = P; }
100  void setNext(AliasSet *N) { Next = N; }
101
102public:
103  /// Accessors...
104  bool isRef() const { return AccessTy & Refs; }
105  bool isMod() const { return AccessTy & Mods; }
106  bool isMustAlias() const { return AliasTy == MustAlias; }
107  bool isMayAlias()  const { return AliasTy == MayAlias; }
108
109  /// isForwardingAliasSet - Return true if this alias set should be ignored as
110  /// part of the AliasSetTracker object.
111  bool isForwardingAliasSet() const { return Forward; }
112
113  /// mergeSetIn - Merge the specified alias set into this alias set...
114  ///
115  void mergeSetIn(AliasSet &AS);
116
117  // Alias Set iteration - Allow access to all of the pointer which are part of
118  // this alias set...
119  class iterator;
120  iterator begin() const { return iterator(PtrListHead); }
121  iterator end()   const { return iterator(); }
122
123  void print(std::ostream &OS) const;
124  void dump() const;
125
126  /// Define an iterator for alias sets... this is just a forward iterator.
127  class iterator : public forward_iterator<HashNodePair, ptrdiff_t> {
128    HashNodePair *CurNode;
129  public:
130    iterator(HashNodePair *CN = 0) : CurNode(CN) {}
131
132    bool operator==(const iterator& x) const {
133      return CurNode == x.CurNode;
134    }
135    bool operator!=(const iterator& x) const { return !operator==(x); }
136
137    const iterator &operator=(const iterator &I) {
138      CurNode = I.CurNode;
139      return *this;
140    }
141
142    value_type &operator*() const {
143      assert(CurNode && "Dereferencing AliasSet.end()!");
144      return *CurNode;
145    }
146    value_type *operator->() const { return &operator*(); }
147
148    iterator& operator++() {                // Preincrement
149      assert(CurNode && "Advancing past AliasSet.end()!");
150      CurNode = CurNode->second.getNext();
151      return *this;
152    }
153    iterator operator++(int) { // Postincrement
154      iterator tmp = *this; ++*this; return tmp;
155    }
156  };
157
158private:
159  // Can only be created by AliasSetTracker
160  AliasSet() : PtrListHead(0), PtrListTail(0), Forward(0), RefCount(0),
161               AccessTy(NoModRef), AliasTy(MustAlias) {
162  }
163  HashNodePair *getSomePointer() const {
164    return PtrListHead ? PtrListHead : 0;
165  }
166
167  /// getForwardedTarget - Return the real alias set this represents.  If this
168  /// has been merged with another set and is forwarding, return the ultimate
169  /// destination set.  This also implements the union-find collapsing as well.
170  AliasSet *getForwardedTarget(AliasSetTracker &AST) {
171    if (!Forward) return this;
172
173    AliasSet *Dest = Forward->getForwardedTarget(AST);
174    if (Dest != Forward) {
175      Dest->RefCount++;
176      if (--Forward->RefCount == 0)
177        Forward->removeFromTracker(AST);
178      Forward = Dest;
179    }
180    return Dest;
181  }
182
183  void removeFromTracker(AliasSetTracker &AST);
184
185  void addPointer(AliasSetTracker &AST, HashNodePair &Entry, unsigned Size);
186  void addCallSite(CallSite CS);
187
188  /// aliasesPointer - Return true if the specified pointer "may" (or must)
189  /// alias one of the members in the set.
190  ///
191  bool aliasesPointer(const Value *Ptr, unsigned Size, AliasAnalysis &AA) const;
192  bool aliasesCallSite(CallSite CS, AliasAnalysis &AA) const;
193};
194
195inline std::ostream& operator<<(std::ostream &OS, const AliasSet &AS) {
196  AS.print(OS);
197  return OS;
198}
199
200
201class AliasSetTracker {
202  AliasAnalysis &AA;
203  ilist<AliasSet> AliasSets;
204
205  // Map from pointers to their node
206  hash_map<Value*, AliasSet::PointerRec> PointerMap;
207public:
208  /// AliasSetTracker ctor - Create an empty collection of AliasSets, and use
209  /// the specified alias analysis object to disambiguate load and store
210  /// addresses.
211  AliasSetTracker(AliasAnalysis &aa) : AA(aa) {}
212
213  /// add methods - These methods are used to add different types of
214  /// instructions to the alias sets.  Adding a new instruction can result in
215  /// one of three actions happening:
216  ///
217  ///   1. If the instruction doesn't alias any other sets, create a new set.
218  ///   2. If the instruction aliases exactly one set, add it to the set
219  ///   3. If the instruction aliases multiple sets, merge the sets, and add
220  ///      the instruction to the result.
221  ///
222  void add(LoadInst *LI);
223  void add(StoreInst *SI);
224  void add(CallSite CS);          // Call/Invoke instructions
225  void add(CallInst *CI)   { add(CallSite(CI)); }
226  void add(InvokeInst *II) { add(CallSite(II)); }
227  void add(Instruction *I);       // Dispatch to one of the other add methods...
228  void add(BasicBlock &BB);       // Add all instructions in basic block
229  void add(const AliasSetTracker &AST); // Add alias relations from another AST
230
231  /// getAliasSets - Return the alias sets that are active.
232  const ilist<AliasSet> &getAliasSets() const { return AliasSets; }
233
234  /// getAliasSetForPointer - Return the alias set that the specified pointer
235  /// lives in...
236  AliasSet &getAliasSetForPointer(Value *P, unsigned Size);
237
238  /// getAliasAnalysis - Return the underlying alias analysis object used by
239  /// this tracker.
240  AliasAnalysis &getAliasAnalysis() const { return AA; }
241
242  typedef ilist<AliasSet>::iterator iterator;
243  typedef ilist<AliasSet>::const_iterator const_iterator;
244
245  const_iterator begin() const { return AliasSets.begin(); }
246  const_iterator end()   const { return AliasSets.end(); }
247
248  iterator begin() { return AliasSets.begin(); }
249  iterator end()   { return AliasSets.end(); }
250
251  void print(std::ostream &OS) const;
252  void dump() const;
253
254private:
255  friend class AliasSet;
256  void removeAliasSet(AliasSet *AS);
257
258  AliasSet::HashNodePair &getEntryFor(Value *V) {
259    // Standard operator[], except that it returns the whole pair, not just
260    // ->second.
261    return *PointerMap.insert(AliasSet::HashNodePair(V,
262                                            AliasSet::PointerRec())).first;
263  }
264
265  void addPointer(Value *P, unsigned Size, AliasSet::AccessType E) {
266    AliasSet &AS = getAliasSetForPointer(P, Size);
267    AS.AccessTy |= E;
268  }
269  AliasSet *findAliasSetForPointer(const Value *Ptr, unsigned Size);
270
271  AliasSet *findAliasSetForCallSite(CallSite CS);
272};
273
274inline std::ostream& operator<<(std::ostream &OS, const AliasSetTracker &AST) {
275  AST.print(OS);
276  return OS;
277}
278
279#endif
280