133965Sjdp//===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===// 278828Sobrien// 3218822Sdim// The LLVM Compiler Infrastructure 438889Sjdp// 533965Sjdp// This file is distributed under the University of Illinois Open Source 633965Sjdp// License. See LICENSE.TXT for details. 733965Sjdp// 833965Sjdp//===----------------------------------------------------------------------===// 933965Sjdp// 1033965Sjdp// This file implements the AliasSetTracker and AliasSet classes. 1133965Sjdp// 1233965Sjdp//===----------------------------------------------------------------------===// 1333965Sjdp 1433965Sjdp#include "llvm/Analysis/AliasSetTracker.h" 1533965Sjdp#include "llvm/Analysis/AliasAnalysis.h" 1633965Sjdp#include "llvm/Assembly/Writer.h" 1733965Sjdp#include "llvm/IR/DataLayout.h" 1833965Sjdp#include "llvm/IR/Instructions.h" 1933965Sjdp#include "llvm/IR/IntrinsicInst.h" 20218822Sdim#include "llvm/IR/LLVMContext.h" 21218822Sdim#include "llvm/IR/Type.h" 2233965Sjdp#include "llvm/Pass.h" 23218822Sdim#include "llvm/Support/Debug.h" 2433965Sjdp#include "llvm/Support/ErrorHandling.h" 2533965Sjdp#include "llvm/Support/InstIterator.h" 2633965Sjdp#include "llvm/Support/raw_ostream.h" 2733965Sjdpusing namespace llvm; 28218822Sdim 2933965Sjdp/// mergeSetIn - Merge the specified alias set into this alias set. 3061843Sobrien/// 31130561Sobrienvoid AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) { 32130561Sobrien assert(!AS.Forward && "Alias set is already forwarding!"); 3333965Sjdp assert(!Forward && "This set is a forwarding set!!"); 34218822Sdim 3533965Sjdp // Update the alias and access types of this set... 3638889Sjdp AccessTy |= AS.AccessTy; 3738889Sjdp AliasTy |= AS.AliasTy; 3838889Sjdp Volatile |= AS.Volatile; 39104834Sobrien 4038889Sjdp if (AliasTy == MustAlias) { 4138889Sjdp // Check that these two merged sets really are must aliases. Since both 4238889Sjdp // used to be must-alias sets, we can just check any pointer from each set 4338889Sjdp // for aliasing. 4438889Sjdp AliasAnalysis &AA = AST.getAliasAnalysis(); 4538889Sjdp PointerRec *L = getSomePointer(); 4638889Sjdp PointerRec *R = AS.getSomePointer(); 4760484Sobrien 4860484Sobrien // If the pointers are not a must-alias pair, this set becomes a may alias. 4960484Sobrien if (AA.alias(AliasAnalysis::Location(L->getValue(), 5060484Sobrien L->getSize(), 5160484Sobrien L->getTBAAInfo()), 5260484Sobrien AliasAnalysis::Location(R->getValue(), 5360484Sobrien R->getSize(), 5460484Sobrien R->getTBAAInfo())) 5589857Sobrien != AliasAnalysis::MustAlias) 5689857Sobrien AliasTy = MayAlias; 5789857Sobrien } 5889857Sobrien 5989857Sobrien if (UnknownInsts.empty()) { // Merge call sites... 6089857Sobrien if (!AS.UnknownInsts.empty()) 6189857Sobrien std::swap(UnknownInsts, AS.UnknownInsts); 6289857Sobrien } else if (!AS.UnknownInsts.empty()) { 6389857Sobrien UnknownInsts.insert(UnknownInsts.end(), AS.UnknownInsts.begin(), AS.UnknownInsts.end()); 6489857Sobrien AS.UnknownInsts.clear(); 65130561Sobrien } 6689857Sobrien 6760484Sobrien AS.Forward = this; // Forward across AS now... 6833965Sjdp addRef(); // AS is now pointing to us... 69130561Sobrien 70130561Sobrien // Merge the list of constituent pointers... 7133965Sjdp if (AS.PtrList) { 7233965Sjdp *PtrListEnd = AS.PtrList; 7333965Sjdp AS.PtrList->setPrevInList(PtrListEnd); 7433965Sjdp PtrListEnd = AS.PtrListEnd; 7533965Sjdp 76130561Sobrien AS.PtrList = 0; 77130561Sobrien AS.PtrListEnd = &AS.PtrList; 7833965Sjdp assert(*AS.PtrListEnd == 0 && "End of list is not null?"); 7933965Sjdp } 8033965Sjdp} 8133965Sjdp 8260484Sobrienvoid AliasSetTracker::removeAliasSet(AliasSet *AS) { 83130561Sobrien if (AliasSet *Fwd = AS->Forward) { 84130561Sobrien Fwd->dropRef(*this); 85130561Sobrien AS->Forward = 0; 86130561Sobrien } 87130561Sobrien AliasSets.erase(AS); 8833965Sjdp} 8933965Sjdp 90104834Sobrienvoid AliasSet::removeFromTracker(AliasSetTracker &AST) { 9133965Sjdp assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!"); 9233965Sjdp AST.removeAliasSet(this); 9333965Sjdp} 9433965Sjdp 9560484Sobrienvoid AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry, 96130561Sobrien uint64_t Size, const MDNode *TBAAInfo, 97130561Sobrien bool KnownMustAlias) { 9833965Sjdp assert(!Entry.hasAliasSet() && "Entry already in set!"); 9933965Sjdp 10060484Sobrien // Check to see if we have to downgrade to _may_ alias. 10133965Sjdp if (isMustAlias() && !KnownMustAlias) 10233965Sjdp if (PointerRec *P = getSomePointer()) { 10360484Sobrien AliasAnalysis &AA = AST.getAliasAnalysis(); 10460484Sobrien AliasAnalysis::AliasResult Result = 10560484Sobrien AA.alias(AliasAnalysis::Location(P->getValue(), P->getSize(), 10660484Sobrien P->getTBAAInfo()), 10760484Sobrien AliasAnalysis::Location(Entry.getValue(), Size, TBAAInfo)); 10860484Sobrien if (Result != AliasAnalysis::MustAlias) 10960484Sobrien AliasTy = MayAlias; 11060484Sobrien else // First entry of must alias must have maximum size! 11133965Sjdp P->updateSizeAndTBAAInfo(Size, TBAAInfo); 11233965Sjdp assert(Result != AliasAnalysis::NoAlias && "Cannot be part of must set!"); 11333965Sjdp } 114130561Sobrien 115130561Sobrien Entry.setAliasSet(this); 116130561Sobrien Entry.updateSizeAndTBAAInfo(Size, TBAAInfo); 117130561Sobrien 118130561Sobrien // Add it to the end of the list... 119130561Sobrien assert(*PtrListEnd == 0 && "End of list is not null?"); 120130561Sobrien *PtrListEnd = &Entry; 121130561Sobrien PtrListEnd = Entry.setPrevInList(PtrListEnd); 122130561Sobrien assert(*PtrListEnd == 0 && "End of list is not null?"); 123130561Sobrien addRef(); // Entry points to alias set. 124130561Sobrien} 12533965Sjdp 12633965Sjdpvoid AliasSet::addUnknownInst(Instruction *I, AliasAnalysis &AA) { 12760484Sobrien UnknownInsts.push_back(I); 12889857Sobrien 129130561Sobrien if (!I->mayWriteToMemory()) { 130130561Sobrien AliasTy = MayAlias; 13189857Sobrien AccessTy |= Refs; 132130561Sobrien return; 133130561Sobrien } 13433965Sjdp 13560484Sobrien // FIXME: This should use mod/ref information to make this not suck so bad 13660484Sobrien AliasTy = MayAlias; 137130561Sobrien AccessTy = ModRef; 13833965Sjdp} 13933965Sjdp 14060484Sobrien/// aliasesPointer - Return true if the specified pointer "may" (or must) 14160484Sobrien/// alias one of the members in the set. 14233965Sjdp/// 14333965Sjdpbool AliasSet::aliasesPointer(const Value *Ptr, uint64_t Size, 144130561Sobrien const MDNode *TBAAInfo, 14533965Sjdp AliasAnalysis &AA) const { 14633965Sjdp if (AliasTy == MustAlias) { 14733965Sjdp assert(UnknownInsts.empty() && "Illegal must alias set!"); 148130561Sobrien 14933965Sjdp // If this is a set of MustAliases, only check to see if the pointer aliases 15033965Sjdp // SOME value in the set. 151218822Sdim PointerRec *SomePtr = getSomePointer(); 152218822Sdim assert(SomePtr && "Empty must-alias set??"); 15389857Sobrien return AA.alias(AliasAnalysis::Location(SomePtr->getValue(), 154130561Sobrien SomePtr->getSize(), 155130561Sobrien SomePtr->getTBAAInfo()), 156130561Sobrien AliasAnalysis::Location(Ptr, Size, TBAAInfo)); 157130561Sobrien } 15833965Sjdp 15933965Sjdp // If this is a may-alias set, we have to check all of the pointers in the set 16033965Sjdp // to be sure it doesn't alias the set... 16133965Sjdp for (iterator I = begin(), E = end(); I != E; ++I) 16233965Sjdp if (AA.alias(AliasAnalysis::Location(Ptr, Size, TBAAInfo), 16333965Sjdp AliasAnalysis::Location(I.getPointer(), I.getSize(), 16433965Sjdp I.getTBAAInfo()))) 16533965Sjdp return true; 16633965Sjdp 16733965Sjdp // Check the unknown instructions... 16833965Sjdp if (!UnknownInsts.empty()) { 16933965Sjdp for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) 17033965Sjdp if (AA.getModRefInfo(UnknownInsts[i], 17133965Sjdp AliasAnalysis::Location(Ptr, Size, TBAAInfo)) != 17233965Sjdp AliasAnalysis::NoModRef) 17333965Sjdp return true; 17433965Sjdp } 17589857Sobrien 17633965Sjdp return false; 17733965Sjdp} 178130561Sobrien 179130561Sobrienbool AliasSet::aliasesUnknownInst(Instruction *Inst, AliasAnalysis &AA) const { 180130561Sobrien if (!Inst->mayReadOrWriteMemory()) 181130561Sobrien return false; 18233965Sjdp 183130561Sobrien for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) { 18433965Sjdp CallSite C1 = getUnknownInst(i), C2 = Inst; 18533965Sjdp if (!C1 || !C2 || 186130561Sobrien AA.getModRefInfo(C1, C2) != AliasAnalysis::NoModRef || 18733965Sjdp AA.getModRefInfo(C2, C1) != AliasAnalysis::NoModRef) 18833965Sjdp return true; 189130561Sobrien } 19033965Sjdp 191130561Sobrien for (iterator I = begin(), E = end(); I != E; ++I) 192130561Sobrien if (AA.getModRefInfo(Inst, AliasAnalysis::Location(I.getPointer(), 193130561Sobrien I.getSize(), 194218822Sdim I.getTBAAInfo())) != 195218822Sdim AliasAnalysis::NoModRef) 196218822Sdim return true; 19778828Sobrien 19878828Sobrien return false; 19938889Sjdp} 200218822Sdim 20138889Sjdpvoid AliasSetTracker::clear() { 20238889Sjdp // Delete all the PointerRec entries. 203218822Sdim for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end(); 20478828Sobrien I != E; ++I) 20538889Sjdp I->second->eraseFromList(); 20660484Sobrien 20738889Sjdp PointerMap.clear(); 208130561Sobrien 209130561Sobrien // The alias sets should all be clear now. 21038889Sjdp AliasSets.clear(); 211218822Sdim} 212218822Sdim 213218822Sdim 214130561Sobrien/// findAliasSetForPointer - Given a pointer, find the one alias set to put the 215130561Sobrien/// instruction referring to the pointer into. If there are multiple alias sets 216130561Sobrien/// that may alias the pointer, merge them together and return the unified set. 217130561Sobrien/// 218130561SobrienAliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr, 219218822Sdim uint64_t Size, 220218822Sdim const MDNode *TBAAInfo) { 221218822Sdim AliasSet *FoundSet = 0; 222218822Sdim for (iterator I = begin(), E = end(); I != E; ++I) { 223218822Sdim if (I->Forward || !I->aliasesPointer(Ptr, Size, TBAAInfo, AA)) continue; 224218822Sdim 225218822Sdim if (FoundSet == 0) { // If this is the first alias set ptr can go into. 226218822Sdim FoundSet = I; // Remember it. 22733965Sjdp } else { // Otherwise, we must merge the sets. 228130561Sobrien FoundSet->mergeSetIn(*I, *this); // Merge in contents. 229130561Sobrien } 230130561Sobrien } 231130561Sobrien 232130561Sobrien return FoundSet; 233130561Sobrien} 234130561Sobrien 235130561Sobrien/// containsPointer - Return true if the specified location is represented by 236130561Sobrien/// this alias set, false otherwise. This does not modify the AST object or 237130561Sobrien/// alias sets. 238130561Sobrienbool AliasSetTracker::containsPointer(Value *Ptr, uint64_t Size, 239130561Sobrien const MDNode *TBAAInfo) const { 240130561Sobrien for (const_iterator I = begin(), E = end(); I != E; ++I) 241130561Sobrien if (!I->Forward && I->aliasesPointer(Ptr, Size, TBAAInfo, AA)) 242130561Sobrien return true; 243130561Sobrien return false; 244130561Sobrien} 245130561Sobrien 246130561Sobrien 247130561Sobrien 248130561SobrienAliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) { 249130561Sobrien AliasSet *FoundSet = 0; 250130561Sobrien for (iterator I = begin(), E = end(); I != E; ++I) { 251130561Sobrien if (I->Forward || !I->aliasesUnknownInst(Inst, AA)) 252218822Sdim continue; 253218822Sdim 254130561Sobrien if (FoundSet == 0) // If this is the first alias set ptr can go into. 255218822Sdim FoundSet = I; // Remember it. 256130561Sobrien else if (!I->Forward) // Otherwise, we must merge the sets. 257218822Sdim FoundSet->mergeSetIn(*I, *this); // Merge in contents. 258218822Sdim } 259130561Sobrien return FoundSet; 260130561Sobrien} 261130561Sobrien 262130561Sobrien 263130561Sobrien 264130561Sobrien 265130561Sobrien/// getAliasSetForPointer - Return the alias set that the specified pointer 266130561Sobrien/// lives in. 267130561SobrienAliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, uint64_t Size, 268130561Sobrien const MDNode *TBAAInfo, 269218822Sdim bool *New) { 270130561Sobrien AliasSet::PointerRec &Entry = getEntryFor(Pointer); 271130561Sobrien 272130561Sobrien // Check to see if the pointer is already known. 273218822Sdim if (Entry.hasAliasSet()) { 274218822Sdim Entry.updateSizeAndTBAAInfo(Size, TBAAInfo); 275218822Sdim // Return the set! 276130561Sobrien return *Entry.getAliasSet(*this)->getForwardedTarget(*this); 27733965Sjdp } 27833965Sjdp 27933965Sjdp if (AliasSet *AS = findAliasSetForPointer(Pointer, Size, TBAAInfo)) { 28033965Sjdp // Add it to the alias set it aliases. 28133965Sjdp AS->addPointer(*this, Entry, Size, TBAAInfo); 28233965Sjdp return *AS; 28333965Sjdp } 28433965Sjdp 28533965Sjdp if (New) *New = true; 286130561Sobrien // Otherwise create a new alias set to hold the loaded pointer. 28733965Sjdp AliasSets.push_back(new AliasSet()); 28833965Sjdp AliasSets.back().addPointer(*this, Entry, Size, TBAAInfo); 289218822Sdim return AliasSets.back(); 29033965Sjdp} 291130561Sobrien 29233965Sjdpbool AliasSetTracker::add(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo) { 29333965Sjdp bool NewPtr; 29480016Sobrien addPointer(Ptr, Size, TBAAInfo, AliasSet::NoModRef, NewPtr); 29533965Sjdp return NewPtr; 29633965Sjdp} 29733965Sjdp 29833965Sjdp 29933965Sjdpbool AliasSetTracker::add(LoadInst *LI) { 30033965Sjdp if (LI->getOrdering() > Monotonic) return addUnknown(LI); 30133965Sjdp AliasSet::AccessType ATy = AliasSet::Refs; 30233965Sjdp bool NewPtr; 30333965Sjdp AliasSet &AS = addPointer(LI->getOperand(0), 304130561Sobrien AA.getTypeStoreSize(LI->getType()), 30533965Sjdp LI->getMetadata(LLVMContext::MD_tbaa), 30633965Sjdp ATy, NewPtr); 30733965Sjdp if (LI->isVolatile()) AS.setVolatile(); 30833965Sjdp return NewPtr; 30933965Sjdp} 31033965Sjdp 31133965Sjdpbool AliasSetTracker::add(StoreInst *SI) { 312130561Sobrien if (SI->getOrdering() > Monotonic) return addUnknown(SI); 31333965Sjdp AliasSet::AccessType ATy = AliasSet::Mods; 31460484Sobrien bool NewPtr; 31560484Sobrien Value *Val = SI->getOperand(0); 31660484Sobrien AliasSet &AS = addPointer(SI->getOperand(1), 31760484Sobrien AA.getTypeStoreSize(Val->getType()), 318130561Sobrien SI->getMetadata(LLVMContext::MD_tbaa), 31989857Sobrien ATy, NewPtr); 32033965Sjdp if (SI->isVolatile()) AS.setVolatile(); 32160484Sobrien return NewPtr; 32233965Sjdp} 32360484Sobrien 32460484Sobrienbool AliasSetTracker::add(VAArgInst *VAAI) { 32560484Sobrien bool NewPtr; 32660484Sobrien addPointer(VAAI->getOperand(0), AliasAnalysis::UnknownSize, 32760484Sobrien VAAI->getMetadata(LLVMContext::MD_tbaa), 32833965Sjdp AliasSet::ModRef, NewPtr); 32933965Sjdp return NewPtr; 33033965Sjdp} 331218822Sdim 33233965Sjdp 33333965Sjdpbool AliasSetTracker::addUnknown(Instruction *Inst) { 334218822Sdim if (isa<DbgInfoIntrinsic>(Inst)) 335218822Sdim return true; // Ignore DbgInfo Intrinsics. 33633965Sjdp if (!Inst->mayReadOrWriteMemory()) 337130561Sobrien return true; // doesn't alias anything 338130561Sobrien 33933965Sjdp AliasSet *AS = findAliasSetForUnknownInst(Inst); 34033965Sjdp if (AS) { 34133965Sjdp AS->addUnknownInst(Inst, AA); 342218822Sdim return false; 343130561Sobrien } 344130561Sobrien AliasSets.push_back(new AliasSet()); 34533965Sjdp AS = &AliasSets.back(); 346130561Sobrien AS->addUnknownInst(Inst, AA); 347218822Sdim return true; 348130561Sobrien} 349130561Sobrien 35060484Sobrienbool AliasSetTracker::add(Instruction *I) { 35160484Sobrien // Dispatch to one of the other add methods. 352130561Sobrien if (LoadInst *LI = dyn_cast<LoadInst>(I)) 353130561Sobrien return add(LI); 35433965Sjdp if (StoreInst *SI = dyn_cast<StoreInst>(I)) 35533965Sjdp return add(SI); 35633965Sjdp if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I)) 357130561Sobrien return add(VAAI); 358130561Sobrien return addUnknown(I); 359130561Sobrien} 36033965Sjdp 361130561Sobrienvoid AliasSetTracker::add(BasicBlock &BB) { 362130561Sobrien for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 363130561Sobrien add(I); 364130561Sobrien} 36533965Sjdp 36633965Sjdpvoid AliasSetTracker::add(const AliasSetTracker &AST) { 36789857Sobrien assert(&AA == &AST.AA && 368218822Sdim "Merging AliasSetTracker objects with different Alias Analyses!"); 36933965Sjdp 37033965Sjdp // Loop over all of the alias sets in AST, adding the pointers contained 371130561Sobrien // therein into the current alias sets. This can cause alias sets to be 372130561Sobrien // merged together in the current AST. 37333965Sjdp for (const_iterator I = AST.begin(), E = AST.end(); I != E; ++I) { 37433965Sjdp if (I->Forward) continue; // Ignore forwarding alias sets 37533965Sjdp 376218822Sdim AliasSet &AS = const_cast<AliasSet&>(*I); 377218822Sdim 37833965Sjdp // If there are any call sites in the alias set, add them to this AST. 379130561Sobrien for (unsigned i = 0, e = AS.UnknownInsts.size(); i != e; ++i) 38033965Sjdp add(AS.UnknownInsts[i]); 38133965Sjdp 38233965Sjdp // Loop over all of the pointers in this alias set. 38333965Sjdp bool X; 38438889Sjdp for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) { 38578828Sobrien AliasSet &NewAS = addPointer(ASI.getPointer(), ASI.getSize(), 386130561Sobrien ASI.getTBAAInfo(), 387130561Sobrien (AliasSet::AccessType)AS.AccessTy, X); 38833965Sjdp if (AS.isVolatile()) NewAS.setVolatile(); 38933965Sjdp } 39033965Sjdp } 39133965Sjdp} 39233965Sjdp 39333965Sjdp/// remove - Remove the specified (potentially non-empty) alias set from the 39433965Sjdp/// tracker. 39533965Sjdpvoid AliasSetTracker::remove(AliasSet &AS) { 396104834Sobrien // Drop all call sites. 39733965Sjdp AS.UnknownInsts.clear(); 39833965Sjdp 39977298Sobrien // Clear the alias set. 40077298Sobrien unsigned NumRefs = 0; 40177298Sobrien while (!AS.empty()) { 40233965Sjdp AliasSet::PointerRec *P = AS.PtrList; 40377298Sobrien 40477298Sobrien Value *ValToRemove = P->getValue(); 40577298Sobrien 406130561Sobrien // Unlink and delete entry from the list of values. 40777298Sobrien P->eraseFromList(); 408130561Sobrien 409130561Sobrien // Remember how many references need to be dropped. 410130561Sobrien ++NumRefs; 411130561Sobrien 41289857Sobrien // Finally, remove the entry. 413130561Sobrien PointerMap.erase(ValToRemove); 414130561Sobrien } 415218822Sdim 416130561Sobrien // Stop using the alias set, removing it. 417130561Sobrien AS.RefCount -= NumRefs; 418130561Sobrien if (AS.RefCount == 0) 419130561Sobrien AS.removeFromTracker(*this); 420130561Sobrien} 421130561Sobrien 42289857Sobrienbool 42333965SjdpAliasSetTracker::remove(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo) { 424130561Sobrien AliasSet *AS = findAliasSetForPointer(Ptr, Size, TBAAInfo); 42533965Sjdp if (!AS) return false; 42689857Sobrien remove(*AS); 42789857Sobrien return true; 42889857Sobrien} 42960484Sobrien 43060484Sobrienbool AliasSetTracker::remove(LoadInst *LI) { 43160484Sobrien uint64_t Size = AA.getTypeStoreSize(LI->getType()); 43289857Sobrien const MDNode *TBAAInfo = LI->getMetadata(LLVMContext::MD_tbaa); 43360484Sobrien AliasSet *AS = findAliasSetForPointer(LI->getOperand(0), Size, TBAAInfo); 43460484Sobrien if (!AS) return false; 43560484Sobrien remove(*AS); 43660484Sobrien return true; 437130561Sobrien} 43860484Sobrien 43960484Sobrienbool AliasSetTracker::remove(StoreInst *SI) { 440130561Sobrien uint64_t Size = AA.getTypeStoreSize(SI->getOperand(0)->getType()); 44160484Sobrien const MDNode *TBAAInfo = SI->getMetadata(LLVMContext::MD_tbaa); 44260484Sobrien AliasSet *AS = findAliasSetForPointer(SI->getOperand(1), Size, TBAAInfo); 443218822Sdim if (!AS) return false; 444218822Sdim remove(*AS); 445218822Sdim return true; 446130561Sobrien} 447218822Sdim 448218822Sdimbool AliasSetTracker::remove(VAArgInst *VAAI) { 449218822Sdim AliasSet *AS = findAliasSetForPointer(VAAI->getOperand(0), 450218822Sdim AliasAnalysis::UnknownSize, 45160484Sobrien VAAI->getMetadata(LLVMContext::MD_tbaa)); 452218822Sdim if (!AS) return false; 45378828Sobrien remove(*AS); 45460484Sobrien return true; 45560484Sobrien} 456218822Sdim 45760484Sobrienbool AliasSetTracker::removeUnknown(Instruction *I) { 45860484Sobrien if (!I->mayReadOrWriteMemory()) 45960484Sobrien return false; // doesn't alias anything 46060484Sobrien 46160484Sobrien AliasSet *AS = findAliasSetForUnknownInst(I); 46260484Sobrien if (!AS) return false; 46360484Sobrien remove(*AS); 46460484Sobrien return true; 46560484Sobrien} 46660484Sobrien 46760484Sobrienbool AliasSetTracker::remove(Instruction *I) { 46860484Sobrien // Dispatch to one of the other remove methods... 46960484Sobrien if (LoadInst *LI = dyn_cast<LoadInst>(I)) 47060484Sobrien return remove(LI); 47160484Sobrien if (StoreInst *SI = dyn_cast<StoreInst>(I)) 47260484Sobrien return remove(SI); 47360484Sobrien if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I)) 47460484Sobrien return remove(VAAI); 47560484Sobrien return removeUnknown(I); 47660484Sobrien} 47760484Sobrien 47860484Sobrien 47989857Sobrien// deleteValue method - This method is used to remove a pointer value from the 48060484Sobrien// AliasSetTracker entirely. It should be used when an instruction is deleted 48160484Sobrien// from the program to update the AST. If you don't use this, you would have 482218822Sdim// dangling pointers to deleted instructions. 48360484Sobrien// 484130561Sobrienvoid AliasSetTracker::deleteValue(Value *PtrVal) { 485130561Sobrien // Notify the alias analysis implementation that this value is gone. 48677298Sobrien AA.deleteValue(PtrVal); 48777298Sobrien 48878828Sobrien // If this is a call instruction, remove the callsite from the appropriate 489218822Sdim // AliasSet (if present). 490218822Sdim if (Instruction *Inst = dyn_cast<Instruction>(PtrVal)) { 491218822Sdim if (Inst->mayReadOrWriteMemory()) { 49278828Sobrien // Scan all the alias sets to see if this call site is contained. 49378828Sobrien for (iterator I = begin(), E = end(); I != E; ++I) { 494218822Sdim if (I->Forward) continue; 49578828Sobrien 49678828Sobrien I->removeUnknownInst(Inst); 497218822Sdim } 498130561Sobrien } 499130561Sobrien } 500130561Sobrien 501130561Sobrien // First, look up the PointerRec for this pointer. 502130561Sobrien PointerMapType::iterator I = PointerMap.find_as(PtrVal); 503130561Sobrien if (I == PointerMap.end()) return; // Noop 504130561Sobrien 505130561Sobrien // If we found one, remove the pointer from the alias set it is in. 506130561Sobrien AliasSet::PointerRec *PtrValEnt = I->second; 50760484Sobrien AliasSet *AS = PtrValEnt->getAliasSet(*this); 508218822Sdim 50960484Sobrien // Unlink and delete from the list of values. 51060484Sobrien PtrValEnt->eraseFromList(); 511130561Sobrien 51260484Sobrien // Stop using the alias set. 51333965Sjdp AS->dropRef(*this); 514218822Sdim 51560484Sobrien PointerMap.erase(I); 51633965Sjdp} 51733965Sjdp 51833965Sjdp// copyValue - This method should be used whenever a preexisting value in the 51933965Sjdp// program is copied or cloned, introducing a new value. Note that it is ok for 520130561Sobrien// clients that use this method to introduce the same value multiple times: if 52133965Sjdp// the tracker already knows about a value, it will ignore the request. 52289857Sobrien// 52389857Sobrienvoid AliasSetTracker::copyValue(Value *From, Value *To) { 52489857Sobrien // Notify the alias analysis implementation that this value is copied. 52560484Sobrien AA.copyValue(From, To); 52689857Sobrien 52789857Sobrien // First, look up the PointerRec for this pointer. 52889857Sobrien PointerMapType::iterator I = PointerMap.find_as(From); 52960484Sobrien if (I == PointerMap.end()) 53089857Sobrien return; // Noop 53160484Sobrien assert(I->second->hasAliasSet() && "Dead entry?"); 532130561Sobrien 53360484Sobrien AliasSet::PointerRec &Entry = getEntryFor(To); 534130561Sobrien if (Entry.hasAliasSet()) return; // Already in the tracker! 53589857Sobrien 536218822Sdim // Add it to the alias set it aliases... 537218822Sdim I = PointerMap.find_as(From); 538218822Sdim AliasSet *AS = I->second->getAliasSet(*this); 53960484Sobrien AS->addPointer(*this, Entry, I->second->getSize(), 54060484Sobrien I->second->getTBAAInfo(), 54160484Sobrien true); 54260484Sobrien} 54360484Sobrien 544130561Sobrien 54560484Sobrien 54660484Sobrien//===----------------------------------------------------------------------===// 54760484Sobrien// AliasSet/AliasSetTracker Printing Support 54833965Sjdp//===----------------------------------------------------------------------===// 549218822Sdim 55060484Sobrienvoid AliasSet::print(raw_ostream &OS) const { 55133965Sjdp OS << " AliasSet[" << (const void*)this << ", " << RefCount << "] "; 55233965Sjdp OS << (AliasTy == MustAlias ? "must" : "may") << " alias, "; 55333965Sjdp switch (AccessTy) { 55433965Sjdp case NoModRef: OS << "No access "; break; 55533965Sjdp case Refs : OS << "Ref "; break; 55633965Sjdp case Mods : OS << "Mod "; break; 55733965Sjdp case ModRef : OS << "Mod/Ref "; break; 558130561Sobrien default: llvm_unreachable("Bad value for AccessTy!"); 55933965Sjdp } 56033965Sjdp if (isVolatile()) OS << "[volatile] "; 56133965Sjdp if (Forward) 56233965Sjdp OS << " forwarding to " << (void*)Forward; 56333965Sjdp 56433965Sjdp 56533965Sjdp if (!empty()) { 56633965Sjdp OS << "Pointers: "; 56733965Sjdp for (iterator I = begin(), E = end(); I != E; ++I) { 56833965Sjdp if (I != begin()) OS << ", "; 56933965Sjdp WriteAsOperand(OS << "(", I.getPointer()); 57033965Sjdp OS << ", " << I.getSize() << ")"; 57133965Sjdp } 57233965Sjdp } 57333965Sjdp if (!UnknownInsts.empty()) { 57433965Sjdp OS << "\n " << UnknownInsts.size() << " Unknown instructions: "; 57533965Sjdp for (unsigned i = 0, e = UnknownInsts.size(); i != e; ++i) { 57633965Sjdp if (i) OS << ", "; 57738889Sjdp WriteAsOperand(OS, UnknownInsts[i]); 57838889Sjdp } 57938889Sjdp } 58033965Sjdp OS << "\n"; 58133965Sjdp} 58260484Sobrien 58333965Sjdpvoid AliasSetTracker::print(raw_ostream &OS) const { 58460484Sobrien OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for " 58533965Sjdp << PointerMap.size() << " pointer values.\n"; 58633965Sjdp for (const_iterator I = begin(), E = end(); I != E; ++I) 58733965Sjdp I->print(OS); 588218822Sdim OS << "\n"; 58938889Sjdp} 59033965Sjdp 59138889Sjdp#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 59238889Sjdpvoid AliasSet::dump() const { print(dbgs()); } 59338889Sjdpvoid AliasSetTracker::dump() const { print(dbgs()); } 59433965Sjdp#endif 59538889Sjdp 59638889Sjdp//===----------------------------------------------------------------------===// 59738889Sjdp// ASTCallbackVH Class Implementation 59860484Sobrien//===----------------------------------------------------------------------===// 59960484Sobrien 60060484Sobrienvoid AliasSetTracker::ASTCallbackVH::deleted() { 60138889Sjdp assert(AST && "ASTCallbackVH called with a null AliasSetTracker!"); 60238889Sjdp AST->deleteValue(getValPtr()); 60333965Sjdp // this now dangles! 60433965Sjdp} 60533965Sjdp 60633965Sjdpvoid AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) { 60733965Sjdp AST->copyValue(getValPtr(), V); 60833965Sjdp} 60933965Sjdp 61060484SobrienAliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast) 61133965Sjdp : CallbackVH(V), AST(ast) {} 61233965Sjdp 613130561SobrienAliasSetTracker::ASTCallbackVH & 61433965SjdpAliasSetTracker::ASTCallbackVH::operator=(Value *V) { 615130561Sobrien return *this = ASTCallbackVH(V, AST); 61633965Sjdp} 61760484Sobrien 61833965Sjdp//===----------------------------------------------------------------------===// 61933965Sjdp// AliasSetPrinter Pass 62033965Sjdp//===----------------------------------------------------------------------===// 62133965Sjdp 62233965Sjdpnamespace { 62333965Sjdp class AliasSetPrinter : public FunctionPass { 624130561Sobrien AliasSetTracker *Tracker; 62533965Sjdp public: 626130561Sobrien static char ID; // Pass identification, replacement for typeid 627130561Sobrien AliasSetPrinter() : FunctionPass(ID) { 628130561Sobrien initializeAliasSetPrinterPass(*PassRegistry::getPassRegistry()); 62960484Sobrien } 63060484Sobrien 63160484Sobrien virtual void getAnalysisUsage(AnalysisUsage &AU) const { 63260484Sobrien AU.setPreservesAll(); 633130561Sobrien AU.addRequired<AliasAnalysis>(); 63433965Sjdp } 63533965Sjdp 63660484Sobrien virtual bool runOnFunction(Function &F) { 63760484Sobrien Tracker = new AliasSetTracker(getAnalysis<AliasAnalysis>()); 63833965Sjdp 63933965Sjdp for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 64033965Sjdp Tracker->add(&*I); 64133965Sjdp Tracker->print(errs()); 64233965Sjdp delete Tracker; 64333965Sjdp return false; 64460484Sobrien } 645130561Sobrien }; 64633965Sjdp} 64733965Sjdp 64833965Sjdpchar AliasSetPrinter::ID = 0; 649130561SobrienINITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets", 65033965Sjdp "Alias Set Printer", false, true) 65138889SjdpINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 65238889SjdpINITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets", 65333965Sjdp "Alias Set Printer", false, true) 65433965Sjdp