AliasSetTracker.cpp revision 226633
1193323Sed//===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===// 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 implements the AliasSetTracker and AliasSet classes. 11193323Sed// 12193323Sed//===----------------------------------------------------------------------===// 13193323Sed 14193323Sed#include "llvm/Analysis/AliasSetTracker.h" 15193323Sed#include "llvm/Analysis/AliasAnalysis.h" 16193323Sed#include "llvm/Instructions.h" 17193323Sed#include "llvm/IntrinsicInst.h" 18218893Sdim#include "llvm/LLVMContext.h" 19193323Sed#include "llvm/Pass.h" 20193323Sed#include "llvm/Type.h" 21193323Sed#include "llvm/Target/TargetData.h" 22193323Sed#include "llvm/Assembly/Writer.h" 23201360Srdivacky#include "llvm/Support/Debug.h" 24198090Srdivacky#include "llvm/Support/ErrorHandling.h" 25193323Sed#include "llvm/Support/InstIterator.h" 26198090Srdivacky#include "llvm/Support/raw_ostream.h" 27193323Sedusing namespace llvm; 28193323Sed 29193323Sed/// mergeSetIn - Merge the specified alias set into this alias set. 30193323Sed/// 31193323Sedvoid AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) { 32193323Sed assert(!AS.Forward && "Alias set is already forwarding!"); 33193323Sed assert(!Forward && "This set is a forwarding set!!"); 34193323Sed 35193323Sed // Update the alias and access types of this set... 36193323Sed AccessTy |= AS.AccessTy; 37193323Sed AliasTy |= AS.AliasTy; 38212904Sdim Volatile |= AS.Volatile; 39193323Sed 40193323Sed if (AliasTy == MustAlias) { 41193323Sed // Check that these two merged sets really are must aliases. Since both 42193323Sed // used to be must-alias sets, we can just check any pointer from each set 43193323Sed // for aliasing. 44193323Sed AliasAnalysis &AA = AST.getAliasAnalysis(); 45193323Sed PointerRec *L = getSomePointer(); 46193323Sed PointerRec *R = AS.getSomePointer(); 47193323Sed 48193323Sed // If the pointers are not a must-alias pair, this set becomes a may alias. 49218893Sdim if (AA.alias(AliasAnalysis::Location(L->getValue(), 50218893Sdim L->getSize(), 51218893Sdim L->getTBAAInfo()), 52218893Sdim AliasAnalysis::Location(R->getValue(), 53218893Sdim R->getSize(), 54218893Sdim R->getTBAAInfo())) 55193323Sed != AliasAnalysis::MustAlias) 56193323Sed AliasTy = MayAlias; 57193323Sed } 58193323Sed 59226633Sdim if (UnknownInsts.empty()) { // Merge call sites... 60226633Sdim if (!AS.UnknownInsts.empty()) 61226633Sdim std::swap(UnknownInsts, AS.UnknownInsts); 62226633Sdim } else if (!AS.UnknownInsts.empty()) { 63226633Sdim UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(), AS.UnknownInsts.end()); 64226633Sdim AS.UnknownInsts.clear(); 65193323Sed } 66193323Sed 67193323Sed AS.Forward = this; // Forward across AS now... 68193323Sed addRef(); // AS is now pointing to us... 69193323Sed 70193323Sed // Merge the list of constituent pointers... 71193323Sed if (AS.PtrList) { 72193323Sed *PtrListEnd = AS.PtrList; 73193323Sed AS.PtrList->setPrevInList(PtrListEnd); 74193323Sed PtrListEnd = AS.PtrListEnd; 75193323Sed 76193323Sed AS.PtrList = 0; 77193323Sed AS.PtrListEnd = &AS.PtrList; 78193323Sed assert(*AS.PtrListEnd == 0 && "End of list is not null?"); 79193323Sed } 80193323Sed} 81193323Sed 82193323Sedvoid AliasSetTracker::removeAliasSet(AliasSet *AS) { 83193323Sed if (AliasSet *Fwd = AS->Forward) { 84193323Sed Fwd->dropRef(*this); 85193323Sed AS->Forward = 0; 86193323Sed } 87193323Sed AliasSets.erase(AS); 88193323Sed} 89193323Sed 90193323Sedvoid AliasSet::removeFromTracker(AliasSetTracker &AST) { 91193323Sed assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!"); 92193323Sed AST.removeAliasSet(this); 93193323Sed} 94193323Sed 95193323Sedvoid AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry, 96218893Sdim uint64_t Size, const MDNode *TBAAInfo, 97218893Sdim bool KnownMustAlias) { 98193323Sed assert(!Entry.hasAliasSet() && "Entry already in set!"); 99193323Sed 100193323Sed // Check to see if we have to downgrade to _may_ alias. 101193323Sed if (isMustAlias() && !KnownMustAlias) 102193323Sed if (PointerRec *P = getSomePointer()) { 103193323Sed AliasAnalysis &AA = AST.getAliasAnalysis(); 104193323Sed AliasAnalysis::AliasResult Result = 105218893Sdim AA.alias(AliasAnalysis::Location(P->getValue(), P->getSize(), 106218893Sdim P->getTBAAInfo()), 107218893Sdim AliasAnalysis::Location(Entry.getValue(), Size, TBAAInfo)); 108218893Sdim if (Result != AliasAnalysis::MustAlias) 109193323Sed AliasTy = MayAlias; 110193323Sed else // First entry of must alias must have maximum size! 111218893Sdim P->updateSizeAndTBAAInfo(Size, TBAAInfo); 112193323Sed assert(Result != AliasAnalysis::NoAlias && "Cannot be part of must set!"); 113193323Sed } 114193323Sed 115193323Sed Entry.setAliasSet(this); 116218893Sdim Entry.updateSizeAndTBAAInfo(Size, TBAAInfo); 117193323Sed 118193323Sed // Add it to the end of the list... 119193323Sed assert(*PtrListEnd == 0 && "End of list is not null?"); 120193323Sed *PtrListEnd = &Entry; 121193323Sed PtrListEnd = Entry.setPrevInList(PtrListEnd); 122193323Sed assert(*PtrListEnd == 0 && "End of list is not null?"); 123212904Sdim addRef(); // Entry points to alias set. 124193323Sed} 125193323Sed 126226633Sdimvoid AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) { 127226633Sdim UnknownInsts.push_back(I); 128193323Sed 129226633Sdim if (!I->mayWriteToMemory()) { 130193323Sed AliasTy = MayAlias; 131193323Sed AccessTy |= Refs; 132193323Sed return; 133193323Sed } 134193323Sed 135193323Sed // FIXME: This should use mod/ref information to make this not suck so bad 136193323Sed AliasTy = MayAlias; 137193323Sed AccessTy = ModRef; 138193323Sed} 139193323Sed 140193323Sed/// aliasesPointer - Return true if the specified pointer "may" (or must) 141193323Sed/// alias one of the members in the set. 142193323Sed/// 143218893Sdimbool AliasSet::aliasesPointer(const Value *Ptr, uint64_t Size, 144218893Sdim const MDNode *TBAAInfo, 145193323Sed AliasAnalysis &AA) const { 146193323Sed if (AliasTy == MustAlias) { 147226633Sdim assert(UnknownInsts.empty() && "Illegal must alias set!"); 148193323Sed 149193323Sed // If this is a set of MustAliases, only check to see if the pointer aliases 150212904Sdim // SOME value in the set. 151193323Sed PointerRec *SomePtr = getSomePointer(); 152193323Sed assert(SomePtr && "Empty must-alias set??"); 153218893Sdim return AA.alias(AliasAnalysis::Location(SomePtr->getValue(), 154218893Sdim SomePtr->getSize(), 155218893Sdim SomePtr->getTBAAInfo()), 156218893Sdim AliasAnalysis::Location(Ptr, Size, TBAAInfo)); 157193323Sed } 158193323Sed 159193323Sed // If this is a may-alias set, we have to check all of the pointers in the set 160193323Sed // to be sure it doesn't alias the set... 161193323Sed for (iterator I = begin(), E = end(); I != E; ++I) 162218893Sdim if (AA.alias(AliasAnalysis::Location(Ptr, Size, TBAAInfo), 163218893Sdim AliasAnalysis::Location(I.getPointer(), I.getSize(), 164218893Sdim I.getTBAAInfo()))) 165193323Sed return true; 166193323Sed 167226633Sdim // Check the unknown instructions... 168226633Sdim if (!UnknownInsts.empty()) { 169226633Sdim for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) 170226633Sdim if (AA.getModRefInfo(UnknownInsts[i], 171218893Sdim AliasAnalysis::Location(Ptr, Size, TBAAInfo)) != 172218893Sdim AliasAnalysis::NoModRef) 173193323Sed return true; 174193323Sed } 175193323Sed 176193323Sed return false; 177193323Sed} 178193323Sed 179226633Sdimbool AliasSet::aliasesUnknownInst(Instruction *Inst, AliasAnalysis &AA) const { 180226633Sdim if (!Inst->mayReadOrWriteMemory()) 181193323Sed return false; 182193323Sed 183226633Sdim for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) { 184226633Sdim CallSite C1 = getUnknownInst(i), C2 = Inst; 185226633Sdim if (!C1 || !C2 || 186226633Sdim AA.getModRefInfo(C1, C2) != AliasAnalysis::NoModRef || 187226633Sdim AA.getModRefInfo(C2, C1) != AliasAnalysis::NoModRef) 188193323Sed return true; 189212904Sdim } 190193323Sed 191193323Sed for (iterator I = begin(), E = end(); I != E; ++I) 192226633Sdim if (AA.getModRefInfo(Inst, I.getPointer(), I.getSize()) != 193193323Sed AliasAnalysis::NoModRef) 194193323Sed return true; 195193323Sed 196193323Sed return false; 197193323Sed} 198193323Sed 199193323Sedvoid AliasSetTracker::clear() { 200193323Sed // Delete all the PointerRec entries. 201198090Srdivacky for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end(); 202198090Srdivacky I != E; ++I) 203193323Sed I->second->eraseFromList(); 204193323Sed 205193323Sed PointerMap.clear(); 206193323Sed 207193323Sed // The alias sets should all be clear now. 208193323Sed AliasSets.clear(); 209193323Sed} 210193323Sed 211193323Sed 212193323Sed/// findAliasSetForPointer - Given a pointer, find the one alias set to put the 213193323Sed/// instruction referring to the pointer into. If there are multiple alias sets 214193323Sed/// that may alias the pointer, merge them together and return the unified set. 215193323Sed/// 216193323SedAliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr, 217218893Sdim uint64_t Size, 218218893Sdim const MDNode *TBAAInfo) { 219193323Sed AliasSet *FoundSet = 0; 220212904Sdim for (iterator I = begin(), E = end(); I != E; ++I) { 221218893Sdim if (I->Forward || !I->aliasesPointer(Ptr, Size, TBAAInfo, AA)) continue; 222212904Sdim 223212904Sdim if (FoundSet == 0) { // If this is the first alias set ptr can go into. 224212904Sdim FoundSet = I; // Remember it. 225212904Sdim } else { // Otherwise, we must merge the sets. 226212904Sdim FoundSet->mergeSetIn(*I, *this); // Merge in contents. 227193323Sed } 228212904Sdim } 229193323Sed 230193323Sed return FoundSet; 231193323Sed} 232193323Sed 233193323Sed/// containsPointer - Return true if the specified location is represented by 234193323Sed/// this alias set, false otherwise. This does not modify the AST object or 235193323Sed/// alias sets. 236218893Sdimbool AliasSetTracker::containsPointer(Value *Ptr, uint64_t Size, 237218893Sdim const MDNode *TBAAInfo) const { 238193323Sed for (const_iterator I = begin(), E = end(); I != E; ++I) 239218893Sdim if (!I->Forward && I->aliasesPointer(Ptr, Size, TBAAInfo, AA)) 240193323Sed return true; 241193323Sed return false; 242193323Sed} 243193323Sed 244193323Sed 245193323Sed 246226633SdimAliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) { 247193323Sed AliasSet *FoundSet = 0; 248212904Sdim for (iterator I = begin(), E = end(); I != E; ++I) { 249226633Sdim if (I->Forward || !I->aliasesUnknownInst(Inst, AA)) 250212904Sdim continue; 251212904Sdim 252212904Sdim if (FoundSet == 0) // If this is the first alias set ptr can go into. 253212904Sdim FoundSet = I; // Remember it. 254212904Sdim else if (!I->Forward) // Otherwise, we must merge the sets. 255212904Sdim FoundSet->mergeSetIn(*I, *this); // Merge in contents. 256212904Sdim } 257193323Sed return FoundSet; 258193323Sed} 259193323Sed 260193323Sed 261193323Sed 262193323Sed 263193323Sed/// getAliasSetForPointer - Return the alias set that the specified pointer 264193323Sed/// lives in. 265218893SdimAliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, uint64_t Size, 266218893Sdim const MDNode *TBAAInfo, 267193323Sed bool *New) { 268193323Sed AliasSet::PointerRec &Entry = getEntryFor(Pointer); 269193323Sed 270212904Sdim // Check to see if the pointer is already known. 271193323Sed if (Entry.hasAliasSet()) { 272218893Sdim Entry.updateSizeAndTBAAInfo(Size, TBAAInfo); 273193323Sed // Return the set! 274193323Sed return *Entry.getAliasSet(*this)->getForwardedTarget(*this); 275212904Sdim } 276212904Sdim 277218893Sdim if (AliasSet *AS = findAliasSetForPointer(Pointer, Size, TBAAInfo)) { 278212904Sdim // Add it to the alias set it aliases. 279218893Sdim AS->addPointer(*this, Entry, Size, TBAAInfo); 280193323Sed return *AS; 281193323Sed } 282212904Sdim 283212904Sdim if (New) *New = true; 284212904Sdim // Otherwise create a new alias set to hold the loaded pointer. 285212904Sdim AliasSets.push_back(new AliasSet()); 286218893Sdim AliasSets.back().addPointer(*this, Entry, Size, TBAAInfo); 287212904Sdim return AliasSets.back(); 288193323Sed} 289193323Sed 290218893Sdimbool AliasSetTracker::add(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo) { 291193323Sed bool NewPtr; 292218893Sdim addPointer(Ptr, Size, TBAAInfo, AliasSet::NoModRef, NewPtr); 293193323Sed return NewPtr; 294193323Sed} 295193323Sed 296193323Sed 297193323Sedbool AliasSetTracker::add(LoadInst *LI) { 298226633Sdim if (LI->getOrdering() > Monotonic) return addUnknown(LI); 299226633Sdim AliasSet::AccessType ATy = AliasSet::Refs; 300226633Sdim if (!LI->isUnordered()) ATy = AliasSet::ModRef; 301193323Sed bool NewPtr; 302193323Sed AliasSet &AS = addPointer(LI->getOperand(0), 303198090Srdivacky AA.getTypeStoreSize(LI->getType()), 304218893Sdim LI->getMetadata(LLVMContext::MD_tbaa), 305226633Sdim ATy, NewPtr); 306193323Sed if (LI->isVolatile()) AS.setVolatile(); 307193323Sed return NewPtr; 308193323Sed} 309193323Sed 310193323Sedbool AliasSetTracker::add(StoreInst *SI) { 311226633Sdim if (SI->getOrdering() > Monotonic) return addUnknown(SI); 312226633Sdim AliasSet::AccessType ATy = AliasSet::Mods; 313226633Sdim if (!SI->isUnordered()) ATy = AliasSet::ModRef; 314193323Sed bool NewPtr; 315193323Sed Value *Val = SI->getOperand(0); 316193323Sed AliasSet &AS = addPointer(SI->getOperand(1), 317198090Srdivacky AA.getTypeStoreSize(Val->getType()), 318218893Sdim SI->getMetadata(LLVMContext::MD_tbaa), 319226633Sdim ATy, NewPtr); 320193323Sed if (SI->isVolatile()) AS.setVolatile(); 321193323Sed return NewPtr; 322193323Sed} 323193323Sed 324193323Sedbool AliasSetTracker::add(VAArgInst *VAAI) { 325193323Sed bool NewPtr; 326218893Sdim addPointer(VAAI->getOperand(0), AliasAnalysis::UnknownSize, 327218893Sdim VAAI->getMetadata(LLVMContext::MD_tbaa), 328218893Sdim AliasSet::ModRef, NewPtr); 329193323Sed return NewPtr; 330193323Sed} 331193323Sed 332193323Sed 333226633Sdimbool AliasSetTracker::addUnknown(Instruction *Inst) { 334226633Sdim if (isa<DbgInfoIntrinsic>(Inst)) 335193323Sed return true; // Ignore DbgInfo Intrinsics. 336226633Sdim if (!Inst->mayReadOrWriteMemory()) 337193323Sed return true; // doesn't alias anything 338193323Sed 339226633Sdim AliasSet *AS = findAliasSetForUnknownInst(Inst); 340212904Sdim if (AS) { 341226633Sdim AS->addUnknownInst(Inst, AA); 342193323Sed return false; 343193323Sed } 344212904Sdim AliasSets.push_back(new AliasSet()); 345212904Sdim AS = &AliasSets.back(); 346226633Sdim AS->addUnknownInst(Inst, AA); 347212904Sdim return true; 348193323Sed} 349193323Sed 350193323Sedbool AliasSetTracker::add(Instruction *I) { 351212904Sdim // Dispatch to one of the other add methods. 352193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(I)) 353193323Sed return add(LI); 354212904Sdim if (StoreInst *SI = dyn_cast<StoreInst>(I)) 355193323Sed return add(SI); 356212904Sdim if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I)) 357193323Sed return add(VAAI); 358226633Sdim return addUnknown(I); 359193323Sed} 360193323Sed 361193323Sedvoid AliasSetTracker::add(BasicBlock &BB) { 362193323Sed for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 363193323Sed add(I); 364193323Sed} 365193323Sed 366193323Sedvoid AliasSetTracker::add(const AliasSetTracker &AST) { 367193323Sed assert(&AA == &AST.AA && 368193323Sed "Merging AliasSetTracker objects with different Alias Analyses!"); 369193323Sed 370193323Sed // Loop over all of the alias sets in AST, adding the pointers contained 371193323Sed // therein into the current alias sets. This can cause alias sets to be 372193323Sed // merged together in the current AST. 373212904Sdim for (const_iterator I = AST.begin(), E = AST.end(); I != E; ++I) { 374212904Sdim if (I->Forward) continue; // Ignore forwarding alias sets 375212904Sdim 376212904Sdim AliasSet &AS = const_cast<AliasSet&>(*I); 377193323Sed 378212904Sdim // If there are any call sites in the alias set, add them to this AST. 379226633Sdim for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i) 380226633Sdim add(AS.UnknownInsts[i]); 381193323Sed 382212904Sdim // Loop over all of the pointers in this alias set. 383212904Sdim bool X; 384212904Sdim for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) { 385212904Sdim AliasSet &NewAS = addPointer(ASI.getPointer(), ASI.getSize(), 386218893Sdim ASI.getTBAAInfo(), 387212904Sdim (AliasSet::AccessType)AS.AccessTy, X); 388212904Sdim if (AS.isVolatile()) NewAS.setVolatile(); 389193323Sed } 390212904Sdim } 391193323Sed} 392193323Sed 393193323Sed/// remove - Remove the specified (potentially non-empty) alias set from the 394193323Sed/// tracker. 395193323Sedvoid AliasSetTracker::remove(AliasSet &AS) { 396193323Sed // Drop all call sites. 397226633Sdim AS.UnknownInsts.clear(); 398193323Sed 399193323Sed // Clear the alias set. 400193323Sed unsigned NumRefs = 0; 401193323Sed while (!AS.empty()) { 402193323Sed AliasSet::PointerRec *P = AS.PtrList; 403193323Sed 404193323Sed Value *ValToRemove = P->getValue(); 405193323Sed 406193323Sed // Unlink and delete entry from the list of values. 407193323Sed P->eraseFromList(); 408193323Sed 409193323Sed // Remember how many references need to be dropped. 410193323Sed ++NumRefs; 411193323Sed 412193323Sed // Finally, remove the entry. 413193323Sed PointerMap.erase(ValToRemove); 414193323Sed } 415193323Sed 416193323Sed // Stop using the alias set, removing it. 417193323Sed AS.RefCount -= NumRefs; 418193323Sed if (AS.RefCount == 0) 419193323Sed AS.removeFromTracker(*this); 420193323Sed} 421193323Sed 422218893Sdimbool 423218893SdimAliasSetTracker::remove(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo) { 424218893Sdim AliasSet *AS = findAliasSetForPointer(Ptr, Size, TBAAInfo); 425193323Sed if (!AS) return false; 426193323Sed remove(*AS); 427193323Sed return true; 428193323Sed} 429193323Sed 430193323Sedbool AliasSetTracker::remove(LoadInst *LI) { 431218893Sdim uint64_t Size = AA.getTypeStoreSize(LI->getType()); 432218893Sdim const MDNode *TBAAInfo = LI->getMetadata(LLVMContext::MD_tbaa); 433218893Sdim AliasSet *AS = findAliasSetForPointer(LI->getOperand(0), Size, TBAAInfo); 434193323Sed if (!AS) return false; 435193323Sed remove(*AS); 436193323Sed return true; 437193323Sed} 438193323Sed 439193323Sedbool AliasSetTracker::remove(StoreInst *SI) { 440218893Sdim uint64_t Size = AA.getTypeStoreSize(SI->getOperand(0)->getType()); 441218893Sdim const MDNode *TBAAInfo = SI->getMetadata(LLVMContext::MD_tbaa); 442218893Sdim AliasSet *AS = findAliasSetForPointer(SI->getOperand(1), Size, TBAAInfo); 443193323Sed if (!AS) return false; 444193323Sed remove(*AS); 445193323Sed return true; 446193323Sed} 447193323Sed 448193323Sedbool AliasSetTracker::remove(VAArgInst *VAAI) { 449218893Sdim AliasSet *AS = findAliasSetForPointer(VAAI->getOperand(0), 450218893Sdim AliasAnalysis::UnknownSize, 451218893Sdim VAAI->getMetadata(LLVMContext::MD_tbaa)); 452193323Sed if (!AS) return false; 453193323Sed remove(*AS); 454193323Sed return true; 455193323Sed} 456193323Sed 457226633Sdimbool AliasSetTracker::removeUnknown(Instruction *I) { 458226633Sdim if (!I->mayReadOrWriteMemory()) 459193323Sed return false; // doesn't alias anything 460193323Sed 461226633Sdim AliasSet *AS = findAliasSetForUnknownInst(I); 462193323Sed if (!AS) return false; 463193323Sed remove(*AS); 464193323Sed return true; 465193323Sed} 466193323Sed 467193323Sedbool AliasSetTracker::remove(Instruction *I) { 468193323Sed // Dispatch to one of the other remove methods... 469193323Sed if (LoadInst *LI = dyn_cast<LoadInst>(I)) 470193323Sed return remove(LI); 471212904Sdim if (StoreInst *SI = dyn_cast<StoreInst>(I)) 472193323Sed return remove(SI); 473212904Sdim if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I)) 474193323Sed return remove(VAAI); 475226633Sdim return removeUnknown(I); 476193323Sed} 477193323Sed 478193323Sed 479193323Sed// deleteValue method - This method is used to remove a pointer value from the 480193323Sed// AliasSetTracker entirely. It should be used when an instruction is deleted 481193323Sed// from the program to update the AST. If you don't use this, you would have 482193323Sed// dangling pointers to deleted instructions. 483193323Sed// 484193323Sedvoid AliasSetTracker::deleteValue(Value *PtrVal) { 485193323Sed // Notify the alias analysis implementation that this value is gone. 486193323Sed AA.deleteValue(PtrVal); 487193323Sed 488193323Sed // If this is a call instruction, remove the callsite from the appropriate 489212904Sdim // AliasSet (if present). 490226633Sdim if (Instruction *Inst = dyn_cast<Instruction>(PtrVal)) { 491226633Sdim if (Inst->mayReadOrWriteMemory()) { 492212904Sdim // Scan all the alias sets to see if this call site is contained. 493212904Sdim for (iterator I = begin(), E = end(); I != E; ++I) { 494212904Sdim if (I->Forward) continue; 495212904Sdim 496226633Sdim I->removeUnknownInst(Inst); 497212904Sdim } 498212904Sdim } 499212904Sdim } 500193323Sed 501193323Sed // First, look up the PointerRec for this pointer. 502198090Srdivacky PointerMapType::iterator I = PointerMap.find(PtrVal); 503193323Sed if (I == PointerMap.end()) return; // Noop 504193323Sed 505193323Sed // If we found one, remove the pointer from the alias set it is in. 506193323Sed AliasSet::PointerRec *PtrValEnt = I->second; 507193323Sed AliasSet *AS = PtrValEnt->getAliasSet(*this); 508193323Sed 509193323Sed // Unlink and delete from the list of values. 510193323Sed PtrValEnt->eraseFromList(); 511193323Sed 512193323Sed // Stop using the alias set. 513193323Sed AS->dropRef(*this); 514193323Sed 515193323Sed PointerMap.erase(I); 516193323Sed} 517193323Sed 518193323Sed// copyValue - This method should be used whenever a preexisting value in the 519193323Sed// program is copied or cloned, introducing a new value. Note that it is ok for 520193323Sed// clients that use this method to introduce the same value multiple times: if 521193323Sed// the tracker already knows about a value, it will ignore the request. 522193323Sed// 523193323Sedvoid AliasSetTracker::copyValue(Value *From, Value *To) { 524193323Sed // Notify the alias analysis implementation that this value is copied. 525193323Sed AA.copyValue(From, To); 526193323Sed 527193323Sed // First, look up the PointerRec for this pointer. 528198090Srdivacky PointerMapType::iterator I = PointerMap.find(From); 529193323Sed if (I == PointerMap.end()) 530193323Sed return; // Noop 531193323Sed assert(I->second->hasAliasSet() && "Dead entry?"); 532193323Sed 533193323Sed AliasSet::PointerRec &Entry = getEntryFor(To); 534193323Sed if (Entry.hasAliasSet()) return; // Already in the tracker! 535193323Sed 536193323Sed // Add it to the alias set it aliases... 537193323Sed I = PointerMap.find(From); 538193323Sed AliasSet *AS = I->second->getAliasSet(*this); 539218893Sdim AS->addPointer(*this, Entry, I->second->getSize(), 540218893Sdim I->second->getTBAAInfo(), 541218893Sdim true); 542193323Sed} 543193323Sed 544193323Sed 545193323Sed 546193323Sed//===----------------------------------------------------------------------===// 547193323Sed// AliasSet/AliasSetTracker Printing Support 548193323Sed//===----------------------------------------------------------------------===// 549193323Sed 550198090Srdivackyvoid AliasSet::print(raw_ostream &OS) const { 551212904Sdim OS << " AliasSet[" << (void*)this << ", " << RefCount << "] "; 552193323Sed OS << (AliasTy == MustAlias ? "must" : "may") << " alias, "; 553193323Sed switch (AccessTy) { 554193323Sed case NoModRef: OS << "No access "; break; 555193323Sed case Refs : OS << "Ref "; break; 556193323Sed case Mods : OS << "Mod "; break; 557193323Sed case ModRef : OS << "Mod/Ref "; break; 558198090Srdivacky default: llvm_unreachable("Bad value for AccessTy!"); 559193323Sed } 560193323Sed if (isVolatile()) OS << "[volatile] "; 561193323Sed if (Forward) 562193323Sed OS << " forwarding to " << (void*)Forward; 563193323Sed 564193323Sed 565193323Sed if (!empty()) { 566193323Sed OS << "Pointers: "; 567193323Sed for (iterator I = begin(), E = end(); I != E; ++I) { 568193323Sed if (I != begin()) OS << ", "; 569193323Sed WriteAsOperand(OS << "(", I.getPointer()); 570193323Sed OS << ", " << I.getSize() << ")"; 571193323Sed } 572193323Sed } 573226633Sdim if (!UnknownInsts.empty()) { 574226633Sdim OS << "\n " << UnknownInsts.size() << " Unknown instructions: "; 575226633Sdim for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) { 576193323Sed if (i) OS << ", "; 577226633Sdim WriteAsOperand(OS, UnknownInsts[i]); 578193323Sed } 579193323Sed } 580193323Sed OS << "\n"; 581193323Sed} 582193323Sed 583198090Srdivackyvoid AliasSetTracker::print(raw_ostream &OS) const { 584193323Sed OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for " 585193323Sed << PointerMap.size() << " pointer values.\n"; 586193323Sed for (const_iterator I = begin(), E = end(); I != E; ++I) 587193323Sed I->print(OS); 588193323Sed OS << "\n"; 589193323Sed} 590193323Sed 591201360Srdivackyvoid AliasSet::dump() const { print(dbgs()); } 592201360Srdivackyvoid AliasSetTracker::dump() const { print(dbgs()); } 593193323Sed 594193323Sed//===----------------------------------------------------------------------===// 595198090Srdivacky// ASTCallbackVH Class Implementation 596198090Srdivacky//===----------------------------------------------------------------------===// 597198090Srdivacky 598198090Srdivackyvoid AliasSetTracker::ASTCallbackVH::deleted() { 599198090Srdivacky assert(AST && "ASTCallbackVH called with a null AliasSetTracker!"); 600198090Srdivacky AST->deleteValue(getValPtr()); 601198090Srdivacky // this now dangles! 602198090Srdivacky} 603198090Srdivacky 604221345Sdimvoid AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) { 605221345Sdim AST->copyValue(getValPtr(), V); 606221345Sdim} 607221345Sdim 608198090SrdivackyAliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast) 609198090Srdivacky : CallbackVH(V), AST(ast) {} 610198090Srdivacky 611198090SrdivackyAliasSetTracker::ASTCallbackVH & 612198090SrdivackyAliasSetTracker::ASTCallbackVH::operator=(Value *V) { 613198090Srdivacky return *this = ASTCallbackVH(V, AST); 614198090Srdivacky} 615198090Srdivacky 616198090Srdivacky//===----------------------------------------------------------------------===// 617193323Sed// AliasSetPrinter Pass 618193323Sed//===----------------------------------------------------------------------===// 619193323Sed 620193323Sednamespace { 621198892Srdivacky class AliasSetPrinter : public FunctionPass { 622193323Sed AliasSetTracker *Tracker; 623193323Sed public: 624193323Sed static char ID; // Pass identification, replacement for typeid 625218893Sdim AliasSetPrinter() : FunctionPass(ID) { 626218893Sdim initializeAliasSetPrinterPass(*PassRegistry::getPassRegistry()); 627218893Sdim } 628193323Sed 629193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 630193323Sed AU.setPreservesAll(); 631193323Sed AU.addRequired<AliasAnalysis>(); 632193323Sed } 633193323Sed 634193323Sed virtual bool runOnFunction(Function &F) { 635193323Sed Tracker = new AliasSetTracker(getAnalysis<AliasAnalysis>()); 636193323Sed 637193323Sed for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 638193323Sed Tracker->add(&*I); 639198090Srdivacky Tracker->print(errs()); 640193323Sed delete Tracker; 641193323Sed return false; 642193323Sed } 643193323Sed }; 644193323Sed} 645193323Sed 646193323Sedchar AliasSetPrinter::ID = 0; 647218893SdimINITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets", 648218893Sdim "Alias Set Printer", false, true) 649218893SdimINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 650218893SdimINITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets", 651218893Sdim "Alias Set Printer", false, true) 652