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" 16249423Sdim#include "llvm/Assembly/Writer.h" 17249423Sdim#include "llvm/IR/DataLayout.h" 18249423Sdim#include "llvm/IR/Instructions.h" 19249423Sdim#include "llvm/IR/IntrinsicInst.h" 20249423Sdim#include "llvm/IR/LLVMContext.h" 21249423Sdim#include "llvm/IR/Type.h" 22193323Sed#include "llvm/Pass.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) 192234353Sdim if (AA.getModRefInfo(Inst, AliasAnalysis::Location(I.getPointer(), 193234353Sdim I.getSize(), 194234353Sdim I.getTBAAInfo())) != 195193323Sed AliasAnalysis::NoModRef) 196193323Sed return true; 197193323Sed 198193323Sed return false; 199193323Sed} 200193323Sed 201193323Sedvoid AliasSetTracker::clear() { 202193323Sed // Delete all the PointerRec entries. 203198090Srdivacky for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end(); 204198090Srdivacky I != E; ++I) 205193323Sed I->second->eraseFromList(); 206193323Sed 207193323Sed PointerMap.clear(); 208193323Sed 209193323Sed // The alias sets should all be clear now. 210193323Sed AliasSets.clear(); 211193323Sed} 212193323Sed 213193323Sed 214193323Sed/// findAliasSetForPointer - Given a pointer, find the one alias set to put the 215193323Sed/// instruction referring to the pointer into. If there are multiple alias sets 216193323Sed/// that may alias the pointer, merge them together and return the unified set. 217193323Sed/// 218193323SedAliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr, 219218893Sdim uint64_t Size, 220218893Sdim const MDNode *TBAAInfo) { 221193323Sed AliasSet *FoundSet = 0; 222212904Sdim for (iterator I = begin(), E = end(); I != E; ++I) { 223218893Sdim if (I->Forward || !I->aliasesPointer(Ptr, Size, TBAAInfo, AA)) continue; 224212904Sdim 225212904Sdim if (FoundSet == 0) { // If this is the first alias set ptr can go into. 226212904Sdim FoundSet = I; // Remember it. 227212904Sdim } else { // Otherwise, we must merge the sets. 228212904Sdim FoundSet->mergeSetIn(*I, *this); // Merge in contents. 229193323Sed } 230212904Sdim } 231193323Sed 232193323Sed return FoundSet; 233193323Sed} 234193323Sed 235193323Sed/// containsPointer - Return true if the specified location is represented by 236193323Sed/// this alias set, false otherwise. This does not modify the AST object or 237193323Sed/// alias sets. 238218893Sdimbool AliasSetTracker::containsPointer(Value *Ptr, uint64_t Size, 239218893Sdim const MDNode *TBAAInfo) const { 240193323Sed for (const_iterator I = begin(), E = end(); I != E; ++I) 241218893Sdim if (!I->Forward && I->aliasesPointer(Ptr, Size, TBAAInfo, AA)) 242193323Sed return true; 243193323Sed return false; 244193323Sed} 245193323Sed 246193323Sed 247193323Sed 248226633SdimAliasSet *AliasSetTracker::findAliasSetForUnknownInst(Instruction *Inst) { 249193323Sed AliasSet *FoundSet = 0; 250212904Sdim for (iterator I = begin(), E = end(); I != E; ++I) { 251226633Sdim if (I->Forward || !I->aliasesUnknownInst(Inst, AA)) 252212904Sdim continue; 253212904Sdim 254212904Sdim if (FoundSet == 0) // If this is the first alias set ptr can go into. 255212904Sdim FoundSet = I; // Remember it. 256212904Sdim else if (!I->Forward) // Otherwise, we must merge the sets. 257212904Sdim FoundSet->mergeSetIn(*I, *this); // Merge in contents. 258212904Sdim } 259193323Sed return FoundSet; 260193323Sed} 261193323Sed 262193323Sed 263193323Sed 264193323Sed 265193323Sed/// getAliasSetForPointer - Return the alias set that the specified pointer 266193323Sed/// lives in. 267218893SdimAliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, uint64_t Size, 268218893Sdim const MDNode *TBAAInfo, 269193323Sed bool *New) { 270193323Sed AliasSet::PointerRec &Entry = getEntryFor(Pointer); 271193323Sed 272212904Sdim // Check to see if the pointer is already known. 273193323Sed if (Entry.hasAliasSet()) { 274218893Sdim Entry.updateSizeAndTBAAInfo(Size, TBAAInfo); 275193323Sed // Return the set! 276193323Sed return *Entry.getAliasSet(*this)->getForwardedTarget(*this); 277212904Sdim } 278212904Sdim 279218893Sdim if (AliasSet *AS = findAliasSetForPointer(Pointer, Size, TBAAInfo)) { 280212904Sdim // Add it to the alias set it aliases. 281218893Sdim AS->addPointer(*this, Entry, Size, TBAAInfo); 282193323Sed return *AS; 283193323Sed } 284212904Sdim 285212904Sdim if (New) *New = true; 286212904Sdim // Otherwise create a new alias set to hold the loaded pointer. 287212904Sdim AliasSets.push_back(new AliasSet()); 288218893Sdim AliasSets.back().addPointer(*this, Entry, Size, TBAAInfo); 289212904Sdim return AliasSets.back(); 290193323Sed} 291193323Sed 292218893Sdimbool AliasSetTracker::add(Value *Ptr, uint64_t Size, const MDNode *TBAAInfo) { 293193323Sed bool NewPtr; 294218893Sdim addPointer(Ptr, Size, TBAAInfo, AliasSet::NoModRef, NewPtr); 295193323Sed return NewPtr; 296193323Sed} 297193323Sed 298193323Sed 299193323Sedbool AliasSetTracker::add(LoadInst *LI) { 300226633Sdim if (LI->getOrdering() > Monotonic) return addUnknown(LI); 301226633Sdim AliasSet::AccessType ATy = AliasSet::Refs; 302193323Sed bool NewPtr; 303193323Sed AliasSet &AS = addPointer(LI->getOperand(0), 304198090Srdivacky AA.getTypeStoreSize(LI->getType()), 305218893Sdim LI->getMetadata(LLVMContext::MD_tbaa), 306226633Sdim ATy, NewPtr); 307193323Sed if (LI->isVolatile()) AS.setVolatile(); 308193323Sed return NewPtr; 309193323Sed} 310193323Sed 311193323Sedbool AliasSetTracker::add(StoreInst *SI) { 312226633Sdim if (SI->getOrdering() > Monotonic) return addUnknown(SI); 313226633Sdim AliasSet::AccessType ATy = AliasSet::Mods; 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. 502239462Sdim PointerMapType::iterator I = PointerMap.find_as(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. 528239462Sdim PointerMapType::iterator I = PointerMap.find_as(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... 537239462Sdim I = PointerMap.find_as(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 { 551243830Sdim OS << " AliasSet[" << (const 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 591243830Sdim#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 592201360Srdivackyvoid AliasSet::dump() const { print(dbgs()); } 593201360Srdivackyvoid AliasSetTracker::dump() const { print(dbgs()); } 594243830Sdim#endif 595193323Sed 596193323Sed//===----------------------------------------------------------------------===// 597198090Srdivacky// ASTCallbackVH Class Implementation 598198090Srdivacky//===----------------------------------------------------------------------===// 599198090Srdivacky 600198090Srdivackyvoid AliasSetTracker::ASTCallbackVH::deleted() { 601198090Srdivacky assert(AST && "ASTCallbackVH called with a null AliasSetTracker!"); 602198090Srdivacky AST->deleteValue(getValPtr()); 603198090Srdivacky // this now dangles! 604198090Srdivacky} 605198090Srdivacky 606221345Sdimvoid AliasSetTracker::ASTCallbackVH::allUsesReplacedWith(Value *V) { 607221345Sdim AST->copyValue(getValPtr(), V); 608221345Sdim} 609221345Sdim 610198090SrdivackyAliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast) 611198090Srdivacky : CallbackVH(V), AST(ast) {} 612198090Srdivacky 613198090SrdivackyAliasSetTracker::ASTCallbackVH & 614198090SrdivackyAliasSetTracker::ASTCallbackVH::operator=(Value *V) { 615198090Srdivacky return *this = ASTCallbackVH(V, AST); 616198090Srdivacky} 617198090Srdivacky 618198090Srdivacky//===----------------------------------------------------------------------===// 619193323Sed// AliasSetPrinter Pass 620193323Sed//===----------------------------------------------------------------------===// 621193323Sed 622193323Sednamespace { 623198892Srdivacky class AliasSetPrinter : public FunctionPass { 624193323Sed AliasSetTracker *Tracker; 625193323Sed public: 626193323Sed static char ID; // Pass identification, replacement for typeid 627218893Sdim AliasSetPrinter() : FunctionPass(ID) { 628218893Sdim initializeAliasSetPrinterPass(*PassRegistry::getPassRegistry()); 629218893Sdim } 630193323Sed 631193323Sed virtual void getAnalysisUsage(AnalysisUsage &AU) const { 632193323Sed AU.setPreservesAll(); 633193323Sed AU.addRequired<AliasAnalysis>(); 634193323Sed } 635193323Sed 636193323Sed virtual bool runOnFunction(Function &F) { 637193323Sed Tracker = new AliasSetTracker(getAnalysis<AliasAnalysis>()); 638193323Sed 639193323Sed for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 640193323Sed Tracker->add(&*I); 641198090Srdivacky Tracker->print(errs()); 642193323Sed delete Tracker; 643193323Sed return false; 644193323Sed } 645193323Sed }; 646193323Sed} 647193323Sed 648193323Sedchar AliasSetPrinter::ID = 0; 649218893SdimINITIALIZE_PASS_BEGIN(AliasSetPrinter, "print-alias-sets", 650218893Sdim "Alias Set Printer", false, true) 651218893SdimINITIALIZE_AG_DEPENDENCY(AliasAnalysis) 652218893SdimINITIALIZE_PASS_END(AliasSetPrinter, "print-alias-sets", 653218893Sdim "Alias Set Printer", false, true) 654