1223637Sbz//===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===// 2171169Smlaier// 3171169Smlaier// The LLVM Compiler Infrastructure 4171169Smlaier// 5171169Smlaier// This file is distributed under the University of Illinois Open Source 6171169Smlaier// License. See LICENSE.TXT for details. 7171169Smlaier// 8171169Smlaier//===----------------------------------------------------------------------===// 9171169Smlaier// 10171169Smlaier// This file defines two classes: AliasSetTracker and AliasSet. These interface 11171169Smlaier// are used to classify a collection of pointer references into a maximal number 12171169Smlaier// of disjoint sets. Each AliasSet object constructed by the AliasSetTracker 13171169Smlaier// object refers to memory disjoint from the other sets. 14171169Smlaier// 15171169Smlaier//===----------------------------------------------------------------------===// 16171169Smlaier 17171169Smlaier#ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H 18171169Smlaier#define LLVM_ANALYSIS_ALIASSETTRACKER_H 19171169Smlaier 20171169Smlaier#include "llvm/ADT/DenseMap.h" 21171169Smlaier#include "llvm/ADT/ilist.h" 22171169Smlaier#include "llvm/ADT/ilist_node.h" 23171169Smlaier#include "llvm/Support/ValueHandle.h" 24171169Smlaier#include <vector> 25171169Smlaier 26171169Smlaiernamespace llvm { 27171169Smlaier 28171169Smlaierclass AliasAnalysis; 29171169Smlaierclass LoadInst; 30171169Smlaierclass StoreInst; 31171169Smlaierclass VAArgInst; 32171169Smlaierclass AliasSetTracker; 33171169Smlaierclass AliasSet; 34171169Smlaier 35171169Smlaierclass AliasSet : public ilist_node<AliasSet> { 36171169Smlaier friend class AliasSetTracker; 37171169Smlaier 38171169Smlaier class PointerRec { 39171169Smlaier Value *Val; // The pointer this record corresponds to. 40171169Smlaier PointerRec **PrevInList, *NextInList; 41171169Smlaier AliasSet *AS; 42171169Smlaier uint64_t Size; 43171169Smlaier const MDNode *TBAAInfo; 44171169Smlaier public: 45171169Smlaier PointerRec(Value *V) 46171169Smlaier : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0), 47171169Smlaier TBAAInfo(DenseMapInfo<const MDNode *>::getEmptyKey()) {} 48171169Smlaier 49171169Smlaier Value *getValue() const { return Val; } 50171169Smlaier 51171169Smlaier PointerRec *getNext() const { return NextInList; } 52171169Smlaier bool hasAliasSet() const { return AS != 0; } 53171169Smlaier 54171169Smlaier PointerRec** setPrevInList(PointerRec **PIL) { 55171169Smlaier PrevInList = PIL; 56223637Sbz return &NextInList; 57171169Smlaier } 58171169Smlaier 59171169Smlaier void updateSizeAndTBAAInfo(uint64_t NewSize, const MDNode *NewTBAAInfo) { 60171169Smlaier if (NewSize > Size) Size = NewSize; 61171169Smlaier 62171169Smlaier if (TBAAInfo == DenseMapInfo<const MDNode *>::getEmptyKey()) 63171169Smlaier // We don't have a TBAAInfo yet. Set it to NewTBAAInfo. 64171169Smlaier TBAAInfo = NewTBAAInfo; 65171169Smlaier else if (TBAAInfo != NewTBAAInfo) 66171169Smlaier // NewTBAAInfo conflicts with TBAAInfo. 67171169Smlaier TBAAInfo = DenseMapInfo<const MDNode *>::getTombstoneKey(); 68171169Smlaier } 69171169Smlaier 70171169Smlaier uint64_t getSize() const { return Size; } 71171169Smlaier 72171169Smlaier /// getTBAAInfo - Return the TBAAInfo, or null if there is no 73171169Smlaier /// information or conflicting information. 74171169Smlaier const MDNode *getTBAAInfo() const { 75171169Smlaier // If we have missing or conflicting TBAAInfo, return null. 76171169Smlaier if (TBAAInfo == DenseMapInfo<const MDNode *>::getEmptyKey() || 77171169Smlaier TBAAInfo == DenseMapInfo<const MDNode *>::getTombstoneKey()) 78171169Smlaier return 0; 79171169Smlaier return TBAAInfo; 80171169Smlaier } 81171169Smlaier 82171169Smlaier AliasSet *getAliasSet(AliasSetTracker &AST) { 83171169Smlaier assert(AS && "No AliasSet yet!"); 84171169Smlaier if (AS->Forward) { 85171169Smlaier AliasSet *OldAS = AS; 86171169Smlaier AS = OldAS->getForwardedTarget(AST); 87171169Smlaier AS->addRef(); 88171169Smlaier OldAS->dropRef(AST); 89171169Smlaier } 90171169Smlaier return AS; 91171169Smlaier } 92171169Smlaier 93171169Smlaier void setAliasSet(AliasSet *as) { 94171169Smlaier assert(AS == 0 && "Already have an alias set!"); 95171169Smlaier AS = as; 96171169Smlaier } 97171169Smlaier 98171169Smlaier void eraseFromList() { 99171169Smlaier if (NextInList) NextInList->PrevInList = PrevInList; 100171169Smlaier *PrevInList = NextInList; 101171169Smlaier if (AS->PtrListEnd == &NextInList) { 102171169Smlaier AS->PtrListEnd = PrevInList; 103171169Smlaier assert(*AS->PtrListEnd == 0 && "List not terminated right!"); 104171169Smlaier } 105171169Smlaier delete this; 106171169Smlaier } 107171169Smlaier }; 108171169Smlaier 109171169Smlaier PointerRec *PtrList, **PtrListEnd; // Doubly linked list of nodes. 110171169Smlaier AliasSet *Forward; // Forwarding pointer. 111171169Smlaier 112171169Smlaier // All instructions without a specific address in this alias set. 113171169Smlaier std::vector<AssertingVH<Instruction> > UnknownInsts; 114171169Smlaier 115171169Smlaier // RefCount - Number of nodes pointing to this AliasSet plus the number of 116171169Smlaier // AliasSets forwarding to it. 117171169Smlaier unsigned RefCount : 28; 118171169Smlaier 119171169Smlaier /// AccessType - Keep track of whether this alias set merely refers to the 120171169Smlaier /// locations of memory, whether it modifies the memory, or whether it does 121171169Smlaier /// both. The lattice goes from "NoModRef" to either Refs or Mods, then to 122171169Smlaier /// ModRef as necessary. 123171169Smlaier /// 124171169Smlaier enum AccessType { 125171169Smlaier NoModRef = 0, Refs = 1, // Ref = bit 1 126171169Smlaier Mods = 2, ModRef = 3 // Mod = bit 2 127171169Smlaier }; 128171169Smlaier unsigned AccessTy : 2; 129171169Smlaier 130171169Smlaier /// AliasType - Keep track the relationships between the pointers in the set. 131171169Smlaier /// Lattice goes from MustAlias to MayAlias. 132171169Smlaier /// 133171169Smlaier enum AliasType { 134171169Smlaier MustAlias = 0, MayAlias = 1 135171169Smlaier }; 136171169Smlaier unsigned AliasTy : 1; 137171169Smlaier 138171169Smlaier // Volatile - True if this alias set contains volatile loads or stores. 139171169Smlaier bool Volatile : 1; 140171169Smlaier 141171169Smlaier void addRef() { ++RefCount; } 142171169Smlaier void dropRef(AliasSetTracker &AST) { 143171169Smlaier assert(RefCount >= 1 && "Invalid reference count detected!"); 144171169Smlaier if (--RefCount == 0) 145171169Smlaier removeFromTracker(AST); 146171169Smlaier } 147171169Smlaier 148171169Smlaier Instruction *getUnknownInst(unsigned i) const { 149171169Smlaier assert(i < UnknownInsts.size()); 150171169Smlaier return UnknownInsts[i]; 151171169Smlaier } 152171169Smlaier 153171169Smlaierpublic: 154171169Smlaier /// Accessors... 155171169Smlaier bool isRef() const { return AccessTy & Refs; } 156171169Smlaier bool isMod() const { return AccessTy & Mods; } 157171169Smlaier bool isMustAlias() const { return AliasTy == MustAlias; } 158171169Smlaier bool isMayAlias() const { return AliasTy == MayAlias; } 159171169Smlaier 160171169Smlaier // isVolatile - Return true if this alias set contains volatile loads or 161171169Smlaier // stores. 162223637Sbz bool isVolatile() const { return Volatile; } 163171169Smlaier 164171169Smlaier /// isForwardingAliasSet - Return true if this alias set should be ignored as 165171169Smlaier /// part of the AliasSetTracker object. 166171169Smlaier bool isForwardingAliasSet() const { return Forward; } 167223637Sbz 168171169Smlaier /// mergeSetIn - Merge the specified alias set into this alias set... 169171169Smlaier /// 170171169Smlaier void mergeSetIn(AliasSet &AS, AliasSetTracker &AST); 171171169Smlaier 172171169Smlaier // Alias Set iteration - Allow access to all of the pointer which are part of 173171169Smlaier // this alias set... 174171169Smlaier class iterator; 175171169Smlaier iterator begin() const { return iterator(PtrList); } 176223637Sbz iterator end() const { return iterator(); } 177171169Smlaier bool empty() const { return PtrList == 0; } 178171169Smlaier 179171169Smlaier void print(raw_ostream &OS) const; 180171169Smlaier void dump() const; 181171169Smlaier 182171169Smlaier /// Define an iterator for alias sets... this is just a forward iterator. 183171169Smlaier class iterator : public std::iterator<std::forward_iterator_tag, 184171169Smlaier PointerRec, ptrdiff_t> { 185171169Smlaier PointerRec *CurNode; 186171169Smlaier public: 187171169Smlaier explicit iterator(PointerRec *CN = 0) : CurNode(CN) {} 188171169Smlaier 189171169Smlaier bool operator==(const iterator& x) const { 190171169Smlaier return CurNode == x.CurNode; 191171169Smlaier } 192171169Smlaier bool operator!=(const iterator& x) const { return !operator==(x); } 193171169Smlaier 194171169Smlaier const iterator &operator=(const iterator &I) { 195171169Smlaier CurNode = I.CurNode; 196171169Smlaier return *this; 197171169Smlaier } 198171169Smlaier 199171169Smlaier value_type &operator*() const { 200171169Smlaier assert(CurNode && "Dereferencing AliasSet.end()!"); 201171169Smlaier return *CurNode; 202171169Smlaier } 203171169Smlaier value_type *operator->() const { return &operator*(); } 204171169Smlaier 205171169Smlaier Value *getPointer() const { return CurNode->getValue(); } 206171169Smlaier uint64_t getSize() const { return CurNode->getSize(); } 207171169Smlaier const MDNode *getTBAAInfo() const { return CurNode->getTBAAInfo(); } 208171169Smlaier 209171169Smlaier iterator& operator++() { // Preincrement 210171169Smlaier assert(CurNode && "Advancing past AliasSet.end()!"); 211171169Smlaier CurNode = CurNode->getNext(); 212171169Smlaier return *this; 213171169Smlaier } 214171169Smlaier iterator operator++(int) { // Postincrement 215171169Smlaier iterator tmp = *this; ++*this; return tmp; 216171169Smlaier } 217171169Smlaier }; 218171169Smlaier 219171169Smlaierprivate: 220171169Smlaier // Can only be created by AliasSetTracker. Also, ilist creates one 221171169Smlaier // to serve as a sentinel. 222171169Smlaier friend struct ilist_sentinel_traits<AliasSet>; 223171169Smlaier AliasSet() : PtrList(0), PtrListEnd(&PtrList), Forward(0), RefCount(0), 224171169Smlaier AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) { 225171169Smlaier } 226171169Smlaier 227171169Smlaier AliasSet(const AliasSet &AS) LLVM_DELETED_FUNCTION; 228171169Smlaier void operator=(const AliasSet &AS) LLVM_DELETED_FUNCTION; 229171169Smlaier 230171169Smlaier PointerRec *getSomePointer() const { 231171169Smlaier return PtrList; 232171169Smlaier } 233171169Smlaier 234171169Smlaier /// getForwardedTarget - Return the real alias set this represents. If this 235171169Smlaier /// has been merged with another set and is forwarding, return the ultimate 236171169Smlaier /// destination set. This also implements the union-find collapsing as well. 237171169Smlaier AliasSet *getForwardedTarget(AliasSetTracker &AST) { 238171169Smlaier if (!Forward) return this; 239171169Smlaier 240171169Smlaier AliasSet *Dest = Forward->getForwardedTarget(AST); 241171169Smlaier if (Dest != Forward) { 242171169Smlaier Dest->addRef(); 243171169Smlaier Forward->dropRef(AST); 244171169Smlaier Forward = Dest; 245171169Smlaier } 246171169Smlaier return Dest; 247171169Smlaier } 248171169Smlaier 249171169Smlaier void removeFromTracker(AliasSetTracker &AST); 250171169Smlaier 251171169Smlaier void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size, 252171169Smlaier const MDNode *TBAAInfo, 253171169Smlaier bool KnownMustAlias = false); 254171169Smlaier void addUnknownInst(Instruction *I, AliasAnalysis &AA); 255171169Smlaier void removeUnknownInst(Instruction *I) { 256171169Smlaier for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i) 257171169Smlaier if (UnknownInsts[i] == I) { 258171169Smlaier UnknownInsts[i] = UnknownInsts.back(); 259171169Smlaier UnknownInsts.pop_back(); 260171169Smlaier --i; --e; // Revisit the moved entry. 261171169Smlaier } 262171169Smlaier } 263171169Smlaier void setVolatile() { Volatile = true; } 264171169Smlaier 265171169Smlaierpublic: 266171169Smlaier /// aliasesPointer - Return true if the specified pointer "may" (or must) 267171169Smlaier /// alias one of the members in the set. 268171169Smlaier /// 269171169Smlaier bool aliasesPointer(const Value *Ptr, uint64_t Size, const MDNode *TBAAInfo, 270171169Smlaier AliasAnalysis &AA) const; 271171169Smlaier bool aliasesUnknownInst(Instruction *Inst, AliasAnalysis &AA) const; 272171169Smlaier}; 273171169Smlaier 274171169Smlaierinline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) { 275171169Smlaier AS.print(OS); 276171169Smlaier return OS; 277171169Smlaier} 278171169Smlaier 279171169Smlaier 280171169Smlaierclass AliasSetTracker { 281171169Smlaier /// CallbackVH - A CallbackVH to arrange for AliasSetTracker to be 282171169Smlaier /// notified whenever a Value is deleted. 283171169Smlaier class ASTCallbackVH : public CallbackVH { 284223637Sbz AliasSetTracker *AST; 285171169Smlaier virtual void deleted(); 286223637Sbz virtual void allUsesReplacedWith(Value *); 287171169Smlaier public: 288171169Smlaier ASTCallbackVH(Value *V, AliasSetTracker *AST = 0); 289171169Smlaier ASTCallbackVH &operator=(Value *V); 290171169Smlaier }; 291171169Smlaier /// ASTCallbackVHDenseMapInfo - Traits to tell DenseMap that tell us how to 292171169Smlaier /// compare and hash the value handle. 293171169Smlaier struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {}; 294171169Smlaier 295171169Smlaier AliasAnalysis &AA; 296171169Smlaier ilist<AliasSet> AliasSets; 297223637Sbz 298223637Sbz typedef DenseMap<ASTCallbackVH, AliasSet::PointerRec*, 299223637Sbz ASTCallbackVHDenseMapInfo> 300223637Sbz PointerMapType; 301223637Sbz 302171169Smlaier // Map from pointers to their node 303171169Smlaier PointerMapType PointerMap; 304171169Smlaier 305171169Smlaierpublic: 306171169Smlaier /// AliasSetTracker ctor - Create an empty collection of AliasSets, and use 307171169Smlaier /// the specified alias analysis object to disambiguate load and store 308171169Smlaier /// addresses. 309171169Smlaier explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {} 310171169Smlaier ~AliasSetTracker() { clear(); } 311171169Smlaier 312171169Smlaier /// add methods - These methods are used to add different types of 313171169Smlaier /// instructions to the alias sets. Adding a new instruction can result in 314171169Smlaier /// one of three actions happening: 315171169Smlaier /// 316171169Smlaier /// 1. If the instruction doesn't alias any other sets, create a new set. 317171169Smlaier /// 2. If the instruction aliases exactly one set, add it to the set 318171169Smlaier /// 3. If the instruction aliases multiple sets, merge the sets, and add 319171169Smlaier /// the instruction to the result. 320171169Smlaier /// 321171169Smlaier /// These methods return true if inserting the instruction resulted in the 322171169Smlaier /// addition of a new alias set (i.e., the pointer did not alias anything). 323171169Smlaier /// 324171169Smlaier bool add(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo); // Add a location 325171169Smlaier bool add(LoadInst *LI); 326171169Smlaier bool add(StoreInst *SI); 327171169Smlaier bool add(VAArgInst *VAAI); 328171169Smlaier bool add(Instruction *I); // Dispatch to one of the other add methods... 329171169Smlaier void add(BasicBlock &BB); // Add all instructions in basic block 330171169Smlaier void add(const AliasSetTracker &AST); // Add alias relations from another AST 331171169Smlaier bool addUnknown(Instruction *I); 332171169Smlaier 333171169Smlaier /// remove methods - These methods are used to remove all entries that might 334171169Smlaier /// be aliased by the specified instruction. These methods return true if any 335171169Smlaier /// alias sets were eliminated. 336171169Smlaier // Remove a location 337171169Smlaier bool remove(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo); 338171169Smlaier bool remove(LoadInst *LI); 339171169Smlaier bool remove(StoreInst *SI); 340171169Smlaier bool remove(VAArgInst *VAAI); 341171169Smlaier bool remove(Instruction *I); 342171169Smlaier void remove(AliasSet &AS); 343171169Smlaier bool removeUnknown(Instruction *I); 344171169Smlaier 345171169Smlaier void clear(); 346171169Smlaier 347171169Smlaier /// getAliasSets - Return the alias sets that are active. 348171169Smlaier /// 349171169Smlaier const ilist<AliasSet> &getAliasSets() const { return AliasSets; } 350171169Smlaier 351171169Smlaier /// getAliasSetForPointer - Return the alias set that the specified pointer 352171169Smlaier /// lives in. If the New argument is non-null, this method sets the value to 353171169Smlaier /// true if a new alias set is created to contain the pointer (because the 354171169Smlaier /// pointer didn't alias anything). 355171169Smlaier AliasSet &getAliasSetForPointer(Value *P, uint64_t Size, 356171169Smlaier const MDNode *TBAAInfo, 357171169Smlaier bool *New = 0); 358171169Smlaier 359171169Smlaier /// getAliasSetForPointerIfExists - Return the alias set containing the 360171169Smlaier /// location specified if one exists, otherwise return null. 361171169Smlaier AliasSet *getAliasSetForPointerIfExists(Value *P, uint64_t Size, 362171169Smlaier const MDNode *TBAAInfo) { 363171169Smlaier return findAliasSetForPointer(P, Size, TBAAInfo); 364171169Smlaier } 365171169Smlaier 366171169Smlaier /// containsPointer - Return true if the specified location is represented by 367171169Smlaier /// this alias set, false otherwise. This does not modify the AST object or 368171169Smlaier /// alias sets. 369171169Smlaier bool containsPointer(Value *P, uint64_t Size, const MDNode *TBAAInfo) const; 370171169Smlaier 371171169Smlaier /// getAliasAnalysis - Return the underlying alias analysis object used by 372171169Smlaier /// this tracker. 373171169Smlaier AliasAnalysis &getAliasAnalysis() const { return AA; } 374171169Smlaier 375171169Smlaier /// deleteValue method - This method is used to remove a pointer value from 376171169Smlaier /// the AliasSetTracker entirely. It should be used when an instruction is 377171169Smlaier /// deleted from the program to update the AST. If you don't use this, you 378171169Smlaier /// would have dangling pointers to deleted instructions. 379171169Smlaier /// 380171169Smlaier void deleteValue(Value *PtrVal); 381171169Smlaier 382171169Smlaier /// copyValue - This method should be used whenever a preexisting value in the 383171169Smlaier /// program is copied or cloned, introducing a new value. Note that it is ok 384171169Smlaier /// for clients that use this method to introduce the same value multiple 385171169Smlaier /// times: if the tracker already knows about a value, it will ignore the 386171169Smlaier /// request. 387171169Smlaier /// 388171169Smlaier void copyValue(Value *From, Value *To); 389171169Smlaier 390171169Smlaier 391171169Smlaier typedef ilist<AliasSet>::iterator iterator; 392171169Smlaier typedef ilist<AliasSet>::const_iterator const_iterator; 393171169Smlaier 394 const_iterator begin() const { return AliasSets.begin(); } 395 const_iterator end() const { return AliasSets.end(); } 396 397 iterator begin() { return AliasSets.begin(); } 398 iterator end() { return AliasSets.end(); } 399 400 void print(raw_ostream &OS) const; 401 void dump() const; 402 403private: 404 friend class AliasSet; 405 void removeAliasSet(AliasSet *AS); 406 407 // getEntryFor - Just like operator[] on the map, except that it creates an 408 // entry for the pointer if it doesn't already exist. 409 AliasSet::PointerRec &getEntryFor(Value *V) { 410 AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)]; 411 if (Entry == 0) 412 Entry = new AliasSet::PointerRec(V); 413 return *Entry; 414 } 415 416 AliasSet &addPointer(Value *P, uint64_t Size, const MDNode *TBAAInfo, 417 AliasSet::AccessType E, 418 bool &NewSet) { 419 NewSet = false; 420 AliasSet &AS = getAliasSetForPointer(P, Size, TBAAInfo, &NewSet); 421 AS.AccessTy |= E; 422 return AS; 423 } 424 AliasSet *findAliasSetForPointer(const Value *Ptr, uint64_t Size, 425 const MDNode *TBAAInfo); 426 427 AliasSet *findAliasSetForUnknownInst(Instruction *Inst); 428}; 429 430inline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) { 431 AST.print(OS); 432 return OS; 433} 434 435} // End llvm namespace 436 437#endif 438