LLVM API Documentation
00001 //===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file defines two classes: AliasSetTracker and AliasSet. These interface 00011 // are used to classify a collection of pointer references into a maximal number 00012 // of disjoint sets. Each AliasSet object constructed by the AliasSetTracker 00013 // object refers to memory disjoint from the other sets. 00014 // 00015 //===----------------------------------------------------------------------===// 00016 00017 #ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H 00018 #define LLVM_ANALYSIS_ALIASSETTRACKER_H 00019 00020 #include "llvm/Support/CallSite.h" 00021 #include "llvm/ADT/iterator" 00022 #include "llvm/ADT/hash_map" 00023 #include "llvm/ADT/ilist" 00024 00025 namespace llvm { 00026 00027 class AliasAnalysis; 00028 class LoadInst; 00029 class StoreInst; 00030 class FreeInst; 00031 class AliasSetTracker; 00032 class AliasSet; 00033 00034 class AliasSet { 00035 friend class AliasSetTracker; 00036 00037 class PointerRec; 00038 typedef std::pair<Value* const, PointerRec> HashNodePair; 00039 00040 class PointerRec { 00041 HashNodePair **PrevInList, *NextInList; 00042 AliasSet *AS; 00043 unsigned Size; 00044 public: 00045 PointerRec() : PrevInList(0), NextInList(0), AS(0), Size(0) {} 00046 00047 HashNodePair *getNext() const { return NextInList; } 00048 bool hasAliasSet() const { return AS != 0; } 00049 00050 HashNodePair** setPrevInList(HashNodePair **PIL) { 00051 PrevInList = PIL; 00052 return &NextInList; 00053 } 00054 00055 void updateSize(unsigned NewSize) { 00056 if (NewSize > Size) Size = NewSize; 00057 } 00058 00059 unsigned getSize() const { return Size; } 00060 00061 AliasSet *getAliasSet(AliasSetTracker &AST) { 00062 assert(AS && "No AliasSet yet!"); 00063 if (AS->Forward) { 00064 AliasSet *OldAS = AS; 00065 AS = OldAS->getForwardedTarget(AST); 00066 AS->addRef(); 00067 OldAS->dropRef(AST); 00068 } 00069 return AS; 00070 } 00071 00072 void setAliasSet(AliasSet *as) { 00073 assert(AS == 0 && "Already have an alias set!"); 00074 AS = as; 00075 } 00076 00077 void removeFromList() { 00078 if (NextInList) NextInList->second.PrevInList = PrevInList; 00079 *PrevInList = NextInList; 00080 if (AS->PtrListEnd == &NextInList) { 00081 AS->PtrListEnd = PrevInList; 00082 assert(*AS->PtrListEnd == 0 && "List not terminated right!"); 00083 } 00084 } 00085 }; 00086 00087 HashNodePair *PtrList, **PtrListEnd; // Doubly linked list of nodes 00088 AliasSet *Forward; // Forwarding pointer 00089 AliasSet *Next, *Prev; // Doubly linked list of AliasSets 00090 00091 std::vector<CallSite> CallSites; // All calls & invokes in this node 00092 00093 // RefCount - Number of nodes pointing to this AliasSet plus the number of 00094 // AliasSets forwarding to it. 00095 unsigned RefCount : 28; 00096 00097 /// AccessType - Keep track of whether this alias set merely refers to the 00098 /// locations of memory, whether it modifies the memory, or whether it does 00099 /// both. The lattice goes from "NoModRef" to either Refs or Mods, then to 00100 /// ModRef as necessary. 00101 /// 00102 enum AccessType { 00103 NoModRef = 0, Refs = 1, // Ref = bit 1 00104 Mods = 2, ModRef = 3 // Mod = bit 2 00105 }; 00106 unsigned AccessTy : 2; 00107 00108 /// AliasType - Keep track the relationships between the pointers in the set. 00109 /// Lattice goes from MustAlias to MayAlias. 00110 /// 00111 enum AliasType { 00112 MustAlias = 0, MayAlias = 1 00113 }; 00114 unsigned AliasTy : 1; 00115 00116 // Volatile - True if this alias set contains volatile loads or stores. 00117 bool Volatile : 1; 00118 00119 friend struct ilist_traits<AliasSet>; 00120 AliasSet *getPrev() const { return Prev; } 00121 AliasSet *getNext() const { return Next; } 00122 void setPrev(AliasSet *P) { Prev = P; } 00123 void setNext(AliasSet *N) { Next = N; } 00124 00125 void addRef() { ++RefCount; } 00126 void dropRef(AliasSetTracker &AST) { 00127 assert(RefCount >= 1 && "Invalid reference count detected!"); 00128 if (--RefCount == 0) 00129 removeFromTracker(AST); 00130 } 00131 00132 public: 00133 /// Accessors... 00134 bool isRef() const { return AccessTy & Refs; } 00135 bool isMod() const { return AccessTy & Mods; } 00136 bool isMustAlias() const { return AliasTy == MustAlias; } 00137 bool isMayAlias() const { return AliasTy == MayAlias; } 00138 00139 // isVolatile - Return true if this alias set contains volatile loads or 00140 // stores. 00141 bool isVolatile() const { return Volatile; } 00142 00143 /// isForwardingAliasSet - Return true if this alias set should be ignored as 00144 /// part of the AliasSetTracker object. 00145 bool isForwardingAliasSet() const { return Forward; } 00146 00147 /// mergeSetIn - Merge the specified alias set into this alias set... 00148 /// 00149 void mergeSetIn(AliasSet &AS, AliasSetTracker &AST); 00150 00151 // Alias Set iteration - Allow access to all of the pointer which are part of 00152 // this alias set... 00153 class iterator; 00154 iterator begin() const { return iterator(PtrList); } 00155 iterator end() const { return iterator(); } 00156 bool empty() const { return PtrList == 0; } 00157 00158 void print(std::ostream &OS) const; 00159 void dump() const; 00160 00161 /// Define an iterator for alias sets... this is just a forward iterator. 00162 class iterator : public forward_iterator<HashNodePair, ptrdiff_t> { 00163 HashNodePair *CurNode; 00164 public: 00165 iterator(HashNodePair *CN = 0) : CurNode(CN) {} 00166 00167 bool operator==(const iterator& x) const { 00168 return CurNode == x.CurNode; 00169 } 00170 bool operator!=(const iterator& x) const { return !operator==(x); } 00171 00172 const iterator &operator=(const iterator &I) { 00173 CurNode = I.CurNode; 00174 return *this; 00175 } 00176 00177 value_type &operator*() const { 00178 assert(CurNode && "Dereferencing AliasSet.end()!"); 00179 return *CurNode; 00180 } 00181 value_type *operator->() const { return &operator*(); } 00182 00183 Value *getPointer() const { return CurNode->first; } 00184 unsigned getSize() const { return CurNode->second.getSize(); } 00185 00186 iterator& operator++() { // Preincrement 00187 assert(CurNode && "Advancing past AliasSet.end()!"); 00188 CurNode = CurNode->second.getNext(); 00189 return *this; 00190 } 00191 iterator operator++(int) { // Postincrement 00192 iterator tmp = *this; ++*this; return tmp; 00193 } 00194 }; 00195 00196 private: 00197 // Can only be created by AliasSetTracker 00198 AliasSet() : PtrList(0), PtrListEnd(&PtrList), Forward(0), RefCount(0), 00199 AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) { 00200 } 00201 00202 AliasSet(const AliasSet &AS) { 00203 assert(0 && "Copy ctor called!?!?!"); 00204 abort(); 00205 } 00206 00207 HashNodePair *getSomePointer() const { 00208 return PtrList; 00209 } 00210 00211 /// getForwardedTarget - Return the real alias set this represents. If this 00212 /// has been merged with another set and is forwarding, return the ultimate 00213 /// destination set. This also implements the union-find collapsing as well. 00214 AliasSet *getForwardedTarget(AliasSetTracker &AST) { 00215 if (!Forward) return this; 00216 00217 AliasSet *Dest = Forward->getForwardedTarget(AST); 00218 if (Dest != Forward) { 00219 Dest->addRef(); 00220 Forward->dropRef(AST); 00221 Forward = Dest; 00222 } 00223 return Dest; 00224 } 00225 00226 void removeFromTracker(AliasSetTracker &AST); 00227 00228 void addPointer(AliasSetTracker &AST, HashNodePair &Entry, unsigned Size, 00229 bool KnownMustAlias = false); 00230 void addCallSite(CallSite CS, AliasAnalysis &AA); 00231 void removeCallSite(CallSite CS) { 00232 for (unsigned i = 0, e = CallSites.size(); i != e; ++i) 00233 if (CallSites[i].getInstruction() == CS.getInstruction()) { 00234 CallSites[i] = CallSites.back(); 00235 CallSites.pop_back(); 00236 } 00237 } 00238 void setVolatile() { Volatile = true; } 00239 00240 /// aliasesPointer - Return true if the specified pointer "may" (or must) 00241 /// alias one of the members in the set. 00242 /// 00243 bool aliasesPointer(const Value *Ptr, unsigned Size, AliasAnalysis &AA) const; 00244 bool aliasesCallSite(CallSite CS, AliasAnalysis &AA) const; 00245 }; 00246 00247 inline std::ostream& operator<<(std::ostream &OS, const AliasSet &AS) { 00248 AS.print(OS); 00249 return OS; 00250 } 00251 00252 00253 class AliasSetTracker { 00254 AliasAnalysis &AA; 00255 ilist<AliasSet> AliasSets; 00256 00257 // Map from pointers to their node 00258 hash_map<Value*, AliasSet::PointerRec> PointerMap; 00259 public: 00260 /// AliasSetTracker ctor - Create an empty collection of AliasSets, and use 00261 /// the specified alias analysis object to disambiguate load and store 00262 /// addresses. 00263 AliasSetTracker(AliasAnalysis &aa) : AA(aa) {} 00264 00265 /// add methods - These methods are used to add different types of 00266 /// instructions to the alias sets. Adding a new instruction can result in 00267 /// one of three actions happening: 00268 /// 00269 /// 1. If the instruction doesn't alias any other sets, create a new set. 00270 /// 2. If the instruction aliases exactly one set, add it to the set 00271 /// 3. If the instruction aliases multiple sets, merge the sets, and add 00272 /// the instruction to the result. 00273 /// 00274 /// These methods return true if inserting the instruction resulted in the 00275 /// addition of a new alias set (i.e., the pointer did not alias anything). 00276 /// 00277 bool add(Value *Ptr, unsigned Size); // Add a location 00278 bool add(LoadInst *LI); 00279 bool add(StoreInst *SI); 00280 bool add(FreeInst *FI); 00281 bool add(CallSite CS); // Call/Invoke instructions 00282 bool add(CallInst *CI) { return add(CallSite(CI)); } 00283 bool add(InvokeInst *II) { return add(CallSite(II)); } 00284 bool add(Instruction *I); // Dispatch to one of the other add methods... 00285 void add(BasicBlock &BB); // Add all instructions in basic block 00286 void add(const AliasSetTracker &AST); // Add alias relations from another AST 00287 00288 /// remove methods - These methods are used to remove all entries that might 00289 /// be aliased by the specified instruction. These methods return true if any 00290 /// alias sets were eliminated. 00291 bool remove(Value *Ptr, unsigned Size); // Remove a location 00292 bool remove(LoadInst *LI); 00293 bool remove(StoreInst *SI); 00294 bool remove(FreeInst *FI); 00295 bool remove(CallSite CS); 00296 bool remove(CallInst *CI) { return remove(CallSite(CI)); } 00297 bool remove(InvokeInst *II) { return remove(CallSite(II)); } 00298 bool remove(Instruction *I); 00299 void remove(AliasSet &AS); 00300 00301 void clear() { 00302 PointerMap.clear(); 00303 AliasSets.clear(); 00304 } 00305 00306 /// getAliasSets - Return the alias sets that are active. 00307 /// 00308 const ilist<AliasSet> &getAliasSets() const { return AliasSets; } 00309 00310 /// getAliasSetForPointer - Return the alias set that the specified pointer 00311 /// lives in. If the New argument is non-null, this method sets the value to 00312 /// true if a new alias set is created to contain the pointer (because the 00313 /// pointer didn't alias anything). 00314 AliasSet &getAliasSetForPointer(Value *P, unsigned Size, bool *New = 0); 00315 00316 /// getAliasSetForPointerIfExists - Return the alias set containing the 00317 /// location specified if one exists, otherwise return null. 00318 AliasSet *getAliasSetForPointerIfExists(Value *P, unsigned Size) { 00319 return findAliasSetForPointer(P, Size); 00320 } 00321 00322 /// containsPointer - Return true if the specified location is represented by 00323 /// this alias set, false otherwise. This does not modify the AST object or 00324 /// alias sets. 00325 bool containsPointer(Value *P, unsigned Size) const; 00326 00327 /// getAliasAnalysis - Return the underlying alias analysis object used by 00328 /// this tracker. 00329 AliasAnalysis &getAliasAnalysis() const { return AA; } 00330 00331 /// deleteValue method - This method is used to remove a pointer value from 00332 /// the AliasSetTracker entirely. It should be used when an instruction is 00333 /// deleted from the program to update the AST. If you don't use this, you 00334 /// would have dangling pointers to deleted instructions. 00335 /// 00336 void deleteValue(Value *PtrVal); 00337 00338 /// copyValue - This method should be used whenever a preexisting value in the 00339 /// program is copied or cloned, introducing a new value. Note that it is ok 00340 /// for clients that use this method to introduce the same value multiple 00341 /// times: if the tracker already knows about a value, it will ignore the 00342 /// request. 00343 /// 00344 void copyValue(Value *From, Value *To); 00345 00346 00347 typedef ilist<AliasSet>::iterator iterator; 00348 typedef ilist<AliasSet>::const_iterator const_iterator; 00349 00350 const_iterator begin() const { return AliasSets.begin(); } 00351 const_iterator end() const { return AliasSets.end(); } 00352 00353 iterator begin() { return AliasSets.begin(); } 00354 iterator end() { return AliasSets.end(); } 00355 00356 void print(std::ostream &OS) const; 00357 void dump() const; 00358 00359 private: 00360 friend class AliasSet; 00361 void removeAliasSet(AliasSet *AS); 00362 00363 AliasSet::HashNodePair &getEntryFor(Value *V) { 00364 // Standard operator[], except that it returns the whole pair, not just 00365 // ->second. 00366 return *PointerMap.insert(AliasSet::HashNodePair(V, 00367 AliasSet::PointerRec())).first; 00368 } 00369 00370 AliasSet &addPointer(Value *P, unsigned Size, AliasSet::AccessType E, 00371 bool &NewSet) { 00372 NewSet = false; 00373 AliasSet &AS = getAliasSetForPointer(P, Size, &NewSet); 00374 AS.AccessTy |= E; 00375 return AS; 00376 } 00377 AliasSet *findAliasSetForPointer(const Value *Ptr, unsigned Size); 00378 00379 AliasSet *findAliasSetForCallSite(CallSite CS); 00380 }; 00381 00382 inline std::ostream& operator<<(std::ostream &OS, const AliasSetTracker &AST) { 00383 AST.print(OS); 00384 return OS; 00385 } 00386 00387 } // End llvm namespace 00388 00389 #endif