1193323Sed//===- llvm/Analysis/AliasSetTracker.h - Build Alias Sets -------*- C++ -*-===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file defines two classes: AliasSetTracker and AliasSet. These interface 11193323Sed// are used to classify a collection of pointer references into a maximal number 12193323Sed// of disjoint sets. Each AliasSet object constructed by the AliasSetTracker 13193323Sed// object refers to memory disjoint from the other sets. 14193323Sed// 15193323Sed//===----------------------------------------------------------------------===// 16193323Sed 17193323Sed#ifndef LLVM_ANALYSIS_ALIASSETTRACKER_H 18193323Sed#define LLVM_ANALYSIS_ALIASSETTRACKER_H 19193323Sed 20193323Sed#include "llvm/ADT/DenseMap.h" 21193323Sed#include "llvm/ADT/ilist.h" 22193323Sed#include "llvm/ADT/ilist_node.h" 23249423Sdim#include "llvm/Support/ValueHandle.h" 24193323Sed#include <vector> 25193323Sed 26193323Sednamespace llvm { 27193323Sed 28193323Sedclass AliasAnalysis; 29193323Sedclass LoadInst; 30193323Sedclass StoreInst; 31193323Sedclass VAArgInst; 32193323Sedclass AliasSetTracker; 33193323Sedclass AliasSet; 34193323Sed 35193323Sedclass AliasSet : public ilist_node<AliasSet> { 36193323Sed friend class AliasSetTracker; 37193323Sed 38193323Sed class PointerRec { 39193323Sed Value *Val; // The pointer this record corresponds to. 40193323Sed PointerRec **PrevInList, *NextInList; 41193323Sed AliasSet *AS; 42218893Sdim uint64_t Size; 43218893Sdim const MDNode *TBAAInfo; 44193323Sed public: 45193323Sed PointerRec(Value *V) 46218893Sdim : Val(V), PrevInList(0), NextInList(0), AS(0), Size(0), 47218893Sdim TBAAInfo(DenseMapInfo<const MDNode *>::getEmptyKey()) {} 48193323Sed 49193323Sed Value *getValue() const { return Val; } 50193323Sed 51193323Sed PointerRec *getNext() const { return NextInList; } 52193323Sed bool hasAliasSet() const { return AS != 0; } 53193323Sed 54193323Sed PointerRec** setPrevInList(PointerRec **PIL) { 55193323Sed PrevInList = PIL; 56193323Sed return &NextInList; 57193323Sed } 58193323Sed 59218893Sdim void updateSizeAndTBAAInfo(uint64_t NewSize, const MDNode *NewTBAAInfo) { 60193323Sed if (NewSize > Size) Size = NewSize; 61218893Sdim 62218893Sdim if (TBAAInfo == DenseMapInfo<const MDNode *>::getEmptyKey()) 63218893Sdim // We don't have a TBAAInfo yet. Set it to NewTBAAInfo. 64218893Sdim TBAAInfo = NewTBAAInfo; 65218893Sdim else if (TBAAInfo != NewTBAAInfo) 66218893Sdim // NewTBAAInfo conflicts with TBAAInfo. 67218893Sdim TBAAInfo = DenseMapInfo<const MDNode *>::getTombstoneKey(); 68193323Sed } 69193323Sed 70218893Sdim uint64_t getSize() const { return Size; } 71193323Sed 72218893Sdim /// getTBAAInfo - Return the TBAAInfo, or null if there is no 73218893Sdim /// information or conflicting information. 74218893Sdim const MDNode *getTBAAInfo() const { 75218893Sdim // If we have missing or conflicting TBAAInfo, return null. 76218893Sdim if (TBAAInfo == DenseMapInfo<const MDNode *>::getEmptyKey() || 77218893Sdim TBAAInfo == DenseMapInfo<const MDNode *>::getTombstoneKey()) 78218893Sdim return 0; 79218893Sdim return TBAAInfo; 80218893Sdim } 81218893Sdim 82193323Sed AliasSet *getAliasSet(AliasSetTracker &AST) { 83193323Sed assert(AS && "No AliasSet yet!"); 84193323Sed if (AS->Forward) { 85193323Sed AliasSet *OldAS = AS; 86193323Sed AS = OldAS->getForwardedTarget(AST); 87193323Sed AS->addRef(); 88193323Sed OldAS->dropRef(AST); 89193323Sed } 90193323Sed return AS; 91193323Sed } 92193323Sed 93193323Sed void setAliasSet(AliasSet *as) { 94193323Sed assert(AS == 0 && "Already have an alias set!"); 95193323Sed AS = as; 96193323Sed } 97193323Sed 98193323Sed void eraseFromList() { 99193323Sed if (NextInList) NextInList->PrevInList = PrevInList; 100193323Sed *PrevInList = NextInList; 101193323Sed if (AS->PtrListEnd == &NextInList) { 102193323Sed AS->PtrListEnd = PrevInList; 103193323Sed assert(*AS->PtrListEnd == 0 && "List not terminated right!"); 104193323Sed } 105193323Sed delete this; 106193323Sed } 107193323Sed }; 108193323Sed 109193323Sed PointerRec *PtrList, **PtrListEnd; // Doubly linked list of nodes. 110193323Sed AliasSet *Forward; // Forwarding pointer. 111193323Sed 112226633Sdim // All instructions without a specific address in this alias set. 113226633Sdim std::vector<AssertingVH<Instruction> > UnknownInsts; 114193323Sed 115193323Sed // RefCount - Number of nodes pointing to this AliasSet plus the number of 116193323Sed // AliasSets forwarding to it. 117193323Sed unsigned RefCount : 28; 118193323Sed 119193323Sed /// AccessType - Keep track of whether this alias set merely refers to the 120193323Sed /// locations of memory, whether it modifies the memory, or whether it does 121193323Sed /// both. The lattice goes from "NoModRef" to either Refs or Mods, then to 122193323Sed /// ModRef as necessary. 123193323Sed /// 124193323Sed enum AccessType { 125193323Sed NoModRef = 0, Refs = 1, // Ref = bit 1 126193323Sed Mods = 2, ModRef = 3 // Mod = bit 2 127193323Sed }; 128193323Sed unsigned AccessTy : 2; 129193323Sed 130193323Sed /// AliasType - Keep track the relationships between the pointers in the set. 131193323Sed /// Lattice goes from MustAlias to MayAlias. 132193323Sed /// 133193323Sed enum AliasType { 134193323Sed MustAlias = 0, MayAlias = 1 135193323Sed }; 136193323Sed unsigned AliasTy : 1; 137193323Sed 138193323Sed // Volatile - True if this alias set contains volatile loads or stores. 139193323Sed bool Volatile : 1; 140193323Sed 141193323Sed void addRef() { ++RefCount; } 142193323Sed void dropRef(AliasSetTracker &AST) { 143193323Sed assert(RefCount >= 1 && "Invalid reference count detected!"); 144193323Sed if (--RefCount == 0) 145193323Sed removeFromTracker(AST); 146193323Sed } 147193323Sed 148226633Sdim Instruction *getUnknownInst(unsigned i) const { 149226633Sdim assert(i < UnknownInsts.size()); 150226633Sdim return UnknownInsts[i]; 151212904Sdim } 152212904Sdim 153193323Sedpublic: 154193323Sed /// Accessors... 155193323Sed bool isRef() const { return AccessTy & Refs; } 156193323Sed bool isMod() const { return AccessTy & Mods; } 157193323Sed bool isMustAlias() const { return AliasTy == MustAlias; } 158193323Sed bool isMayAlias() const { return AliasTy == MayAlias; } 159193323Sed 160193323Sed // isVolatile - Return true if this alias set contains volatile loads or 161193323Sed // stores. 162193323Sed bool isVolatile() const { return Volatile; } 163193323Sed 164193323Sed /// isForwardingAliasSet - Return true if this alias set should be ignored as 165193323Sed /// part of the AliasSetTracker object. 166193323Sed bool isForwardingAliasSet() const { return Forward; } 167193323Sed 168193323Sed /// mergeSetIn - Merge the specified alias set into this alias set... 169193323Sed /// 170193323Sed void mergeSetIn(AliasSet &AS, AliasSetTracker &AST); 171193323Sed 172193323Sed // Alias Set iteration - Allow access to all of the pointer which are part of 173193323Sed // this alias set... 174193323Sed class iterator; 175193323Sed iterator begin() const { return iterator(PtrList); } 176193323Sed iterator end() const { return iterator(); } 177193323Sed bool empty() const { return PtrList == 0; } 178193323Sed 179198090Srdivacky void print(raw_ostream &OS) const; 180193323Sed void dump() const; 181193323Sed 182193323Sed /// Define an iterator for alias sets... this is just a forward iterator. 183198090Srdivacky class iterator : public std::iterator<std::forward_iterator_tag, 184198090Srdivacky PointerRec, ptrdiff_t> { 185193323Sed PointerRec *CurNode; 186193323Sed public: 187193323Sed explicit iterator(PointerRec *CN = 0) : CurNode(CN) {} 188193323Sed 189193323Sed bool operator==(const iterator& x) const { 190193323Sed return CurNode == x.CurNode; 191193323Sed } 192193323Sed bool operator!=(const iterator& x) const { return !operator==(x); } 193193323Sed 194193323Sed const iterator &operator=(const iterator &I) { 195193323Sed CurNode = I.CurNode; 196193323Sed return *this; 197193323Sed } 198193323Sed 199193323Sed value_type &operator*() const { 200193323Sed assert(CurNode && "Dereferencing AliasSet.end()!"); 201193323Sed return *CurNode; 202193323Sed } 203193323Sed value_type *operator->() const { return &operator*(); } 204193323Sed 205193323Sed Value *getPointer() const { return CurNode->getValue(); } 206218893Sdim uint64_t getSize() const { return CurNode->getSize(); } 207218893Sdim const MDNode *getTBAAInfo() const { return CurNode->getTBAAInfo(); } 208193323Sed 209193323Sed iterator& operator++() { // Preincrement 210193323Sed assert(CurNode && "Advancing past AliasSet.end()!"); 211193323Sed CurNode = CurNode->getNext(); 212193323Sed return *this; 213193323Sed } 214193323Sed iterator operator++(int) { // Postincrement 215193323Sed iterator tmp = *this; ++*this; return tmp; 216193323Sed } 217193323Sed }; 218193323Sed 219193323Sedprivate: 220193323Sed // Can only be created by AliasSetTracker. Also, ilist creates one 221193323Sed // to serve as a sentinel. 222193323Sed friend struct ilist_sentinel_traits<AliasSet>; 223193323Sed AliasSet() : PtrList(0), PtrListEnd(&PtrList), Forward(0), RefCount(0), 224193323Sed AccessTy(NoModRef), AliasTy(MustAlias), Volatile(false) { 225193323Sed } 226193323Sed 227243830Sdim AliasSet(const AliasSet &AS) LLVM_DELETED_FUNCTION; 228243830Sdim void operator=(const AliasSet &AS) LLVM_DELETED_FUNCTION; 229193323Sed 230193323Sed PointerRec *getSomePointer() const { 231193323Sed return PtrList; 232193323Sed } 233193323Sed 234193323Sed /// getForwardedTarget - Return the real alias set this represents. If this 235193323Sed /// has been merged with another set and is forwarding, return the ultimate 236193323Sed /// destination set. This also implements the union-find collapsing as well. 237193323Sed AliasSet *getForwardedTarget(AliasSetTracker &AST) { 238193323Sed if (!Forward) return this; 239193323Sed 240193323Sed AliasSet *Dest = Forward->getForwardedTarget(AST); 241193323Sed if (Dest != Forward) { 242193323Sed Dest->addRef(); 243193323Sed Forward->dropRef(AST); 244193323Sed Forward = Dest; 245193323Sed } 246193323Sed return Dest; 247193323Sed } 248193323Sed 249193323Sed void removeFromTracker(AliasSetTracker &AST); 250193323Sed 251218893Sdim void addPointer(AliasSetTracker &AST, PointerRec &Entry, uint64_t Size, 252218893Sdim const MDNode *TBAAInfo, 253193323Sed bool KnownMustAlias = false); 254226633Sdim void addUnknownInst(Instruction *I, AliasAnalysis &AA); 255226633Sdim void removeUnknownInst(Instruction *I) { 256226633Sdim for (size_t i = 0, e = UnknownInsts.size(); i != e; ++i) 257226633Sdim if (UnknownInsts[i] == I) { 258226633Sdim UnknownInsts[i] = UnknownInsts.back(); 259226633Sdim UnknownInsts.pop_back(); 260221345Sdim --i; --e; // Revisit the moved entry. 261193323Sed } 262193323Sed } 263193323Sed void setVolatile() { Volatile = true; } 264193323Sed 265234353Sdimpublic: 266193323Sed /// aliasesPointer - Return true if the specified pointer "may" (or must) 267193323Sed /// alias one of the members in the set. 268193323Sed /// 269218893Sdim bool aliasesPointer(const Value *Ptr, uint64_t Size, const MDNode *TBAAInfo, 270218893Sdim AliasAnalysis &AA) const; 271226633Sdim bool aliasesUnknownInst(Instruction *Inst, AliasAnalysis &AA) const; 272193323Sed}; 273193323Sed 274198090Srdivackyinline raw_ostream& operator<<(raw_ostream &OS, const AliasSet &AS) { 275193323Sed AS.print(OS); 276193323Sed return OS; 277193323Sed} 278193323Sed 279193323Sed 280193323Sedclass AliasSetTracker { 281198090Srdivacky /// CallbackVH - A CallbackVH to arrange for AliasSetTracker to be 282198090Srdivacky /// notified whenever a Value is deleted. 283198090Srdivacky class ASTCallbackVH : public CallbackVH { 284198090Srdivacky AliasSetTracker *AST; 285198090Srdivacky virtual void deleted(); 286221345Sdim virtual void allUsesReplacedWith(Value *); 287198090Srdivacky public: 288198090Srdivacky ASTCallbackVH(Value *V, AliasSetTracker *AST = 0); 289198090Srdivacky ASTCallbackVH &operator=(Value *V); 290198090Srdivacky }; 291200581Srdivacky /// ASTCallbackVHDenseMapInfo - Traits to tell DenseMap that tell us how to 292200581Srdivacky /// compare and hash the value handle. 293200581Srdivacky struct ASTCallbackVHDenseMapInfo : public DenseMapInfo<Value *> {}; 294198090Srdivacky 295193323Sed AliasAnalysis &AA; 296193323Sed ilist<AliasSet> AliasSets; 297193323Sed 298198090Srdivacky typedef DenseMap<ASTCallbackVH, AliasSet::PointerRec*, 299198090Srdivacky ASTCallbackVHDenseMapInfo> 300198090Srdivacky PointerMapType; 301198090Srdivacky 302193323Sed // Map from pointers to their node 303198090Srdivacky PointerMapType PointerMap; 304198090Srdivacky 305193323Sedpublic: 306193323Sed /// AliasSetTracker ctor - Create an empty collection of AliasSets, and use 307193323Sed /// the specified alias analysis object to disambiguate load and store 308193323Sed /// addresses. 309193323Sed explicit AliasSetTracker(AliasAnalysis &aa) : AA(aa) {} 310193323Sed ~AliasSetTracker() { clear(); } 311193323Sed 312193323Sed /// add methods - These methods are used to add different types of 313193323Sed /// instructions to the alias sets. Adding a new instruction can result in 314193323Sed /// one of three actions happening: 315193323Sed /// 316193323Sed /// 1. If the instruction doesn't alias any other sets, create a new set. 317193323Sed /// 2. If the instruction aliases exactly one set, add it to the set 318193323Sed /// 3. If the instruction aliases multiple sets, merge the sets, and add 319193323Sed /// the instruction to the result. 320193323Sed /// 321193323Sed /// These methods return true if inserting the instruction resulted in the 322193323Sed /// addition of a new alias set (i.e., the pointer did not alias anything). 323193323Sed /// 324218893Sdim bool add(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo); // Add a location 325193323Sed bool add(LoadInst *LI); 326193323Sed bool add(StoreInst *SI); 327193323Sed bool add(VAArgInst *VAAI); 328193323Sed bool add(Instruction *I); // Dispatch to one of the other add methods... 329193323Sed void add(BasicBlock &BB); // Add all instructions in basic block 330193323Sed void add(const AliasSetTracker &AST); // Add alias relations from another AST 331226633Sdim bool addUnknown(Instruction *I); 332193323Sed 333193323Sed /// remove methods - These methods are used to remove all entries that might 334193323Sed /// be aliased by the specified instruction. These methods return true if any 335193323Sed /// alias sets were eliminated. 336218893Sdim // Remove a location 337218893Sdim bool remove(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo); 338193323Sed bool remove(LoadInst *LI); 339193323Sed bool remove(StoreInst *SI); 340193323Sed bool remove(VAArgInst *VAAI); 341193323Sed bool remove(Instruction *I); 342193323Sed void remove(AliasSet &AS); 343226633Sdim bool removeUnknown(Instruction *I); 344193323Sed 345193323Sed void clear(); 346193323Sed 347193323Sed /// getAliasSets - Return the alias sets that are active. 348193323Sed /// 349193323Sed const ilist<AliasSet> &getAliasSets() const { return AliasSets; } 350193323Sed 351193323Sed /// getAliasSetForPointer - Return the alias set that the specified pointer 352193323Sed /// lives in. If the New argument is non-null, this method sets the value to 353193323Sed /// true if a new alias set is created to contain the pointer (because the 354193323Sed /// pointer didn't alias anything). 355218893Sdim AliasSet &getAliasSetForPointer(Value *P, uint64_t Size, 356218893Sdim const MDNode *TBAAInfo, 357218893Sdim bool *New = 0); 358193323Sed 359193323Sed /// getAliasSetForPointerIfExists - Return the alias set containing the 360193323Sed /// location specified if one exists, otherwise return null. 361218893Sdim AliasSet *getAliasSetForPointerIfExists(Value *P, uint64_t Size, 362218893Sdim const MDNode *TBAAInfo) { 363218893Sdim return findAliasSetForPointer(P, Size, TBAAInfo); 364193323Sed } 365193323Sed 366193323Sed /// containsPointer - Return true if the specified location is represented by 367193323Sed /// this alias set, false otherwise. This does not modify the AST object or 368193323Sed /// alias sets. 369218893Sdim bool containsPointer(Value *P, uint64_t Size, const MDNode *TBAAInfo) const; 370193323Sed 371193323Sed /// getAliasAnalysis - Return the underlying alias analysis object used by 372193323Sed /// this tracker. 373193323Sed AliasAnalysis &getAliasAnalysis() const { return AA; } 374193323Sed 375193323Sed /// deleteValue method - This method is used to remove a pointer value from 376193323Sed /// the AliasSetTracker entirely. It should be used when an instruction is 377193323Sed /// deleted from the program to update the AST. If you don't use this, you 378193323Sed /// would have dangling pointers to deleted instructions. 379193323Sed /// 380193323Sed void deleteValue(Value *PtrVal); 381193323Sed 382193323Sed /// copyValue - This method should be used whenever a preexisting value in the 383193323Sed /// program is copied or cloned, introducing a new value. Note that it is ok 384193323Sed /// for clients that use this method to introduce the same value multiple 385193323Sed /// times: if the tracker already knows about a value, it will ignore the 386193323Sed /// request. 387193323Sed /// 388193323Sed void copyValue(Value *From, Value *To); 389193323Sed 390193323Sed 391193323Sed typedef ilist<AliasSet>::iterator iterator; 392193323Sed typedef ilist<AliasSet>::const_iterator const_iterator; 393193323Sed 394193323Sed const_iterator begin() const { return AliasSets.begin(); } 395193323Sed const_iterator end() const { return AliasSets.end(); } 396193323Sed 397193323Sed iterator begin() { return AliasSets.begin(); } 398193323Sed iterator end() { return AliasSets.end(); } 399193323Sed 400198090Srdivacky void print(raw_ostream &OS) const; 401193323Sed void dump() const; 402193323Sed 403193323Sedprivate: 404193323Sed friend class AliasSet; 405193323Sed void removeAliasSet(AliasSet *AS); 406193323Sed 407193323Sed // getEntryFor - Just like operator[] on the map, except that it creates an 408193323Sed // entry for the pointer if it doesn't already exist. 409193323Sed AliasSet::PointerRec &getEntryFor(Value *V) { 410198090Srdivacky AliasSet::PointerRec *&Entry = PointerMap[ASTCallbackVH(V, this)]; 411193323Sed if (Entry == 0) 412193323Sed Entry = new AliasSet::PointerRec(V); 413193323Sed return *Entry; 414193323Sed } 415193323Sed 416218893Sdim AliasSet &addPointer(Value *P, uint64_t Size, const MDNode *TBAAInfo, 417218893Sdim AliasSet::AccessType E, 418193323Sed bool &NewSet) { 419193323Sed NewSet = false; 420218893Sdim AliasSet &AS = getAliasSetForPointer(P, Size, TBAAInfo, &NewSet); 421193323Sed AS.AccessTy |= E; 422193323Sed return AS; 423193323Sed } 424218893Sdim AliasSet *findAliasSetForPointer(const Value *Ptr, uint64_t Size, 425218893Sdim const MDNode *TBAAInfo); 426193323Sed 427226633Sdim AliasSet *findAliasSetForUnknownInst(Instruction *Inst); 428193323Sed}; 429193323Sed 430198090Srdivackyinline raw_ostream& operator<<(raw_ostream &OS, const AliasSetTracker &AST) { 431193323Sed AST.print(OS); 432193323Sed return OS; 433193323Sed} 434193323Sed 435193323Sed} // End llvm namespace 436193323Sed 437193323Sed#endif 438