AliasSetTracker.cpp revision 033927408e7a37815402d8748dd424be437c00d0
1//===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===// 2// 3// The LLVM Compiler Infrastructure 4// 5// This file is distributed under the University of Illinois Open Source 6// License. See LICENSE.TXT for details. 7// 8//===----------------------------------------------------------------------===// 9// 10// This file implements the AliasSetTracker and AliasSet classes. 11// 12//===----------------------------------------------------------------------===// 13 14#include "llvm/Analysis/AliasSetTracker.h" 15#include "llvm/Analysis/AliasAnalysis.h" 16#include "llvm/Instructions.h" 17#include "llvm/IntrinsicInst.h" 18#include "llvm/Pass.h" 19#include "llvm/Type.h" 20#include "llvm/Target/TargetData.h" 21#include "llvm/Assembly/Writer.h" 22#include "llvm/Support/Debug.h" 23#include "llvm/Support/ErrorHandling.h" 24#include "llvm/Support/InstIterator.h" 25#include "llvm/Support/raw_ostream.h" 26using namespace llvm; 27 28/// mergeSetIn - Merge the specified alias set into this alias set. 29/// 30void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) { 31 assert(!AS.Forward && "Alias set is already forwarding!"); 32 assert(!Forward && "This set is a forwarding set!!"); 33 34 // Update the alias and access types of this set... 35 AccessTy |= AS.AccessTy; 36 AliasTy |= AS.AliasTy; 37 Volatile |= AS.Volatile; 38 39 if (AliasTy == MustAlias) { 40 // Check that these two merged sets really are must aliases. Since both 41 // used to be must-alias sets, we can just check any pointer from each set 42 // for aliasing. 43 AliasAnalysis &AA = AST.getAliasAnalysis(); 44 PointerRec *L = getSomePointer(); 45 PointerRec *R = AS.getSomePointer(); 46 47 // If the pointers are not a must-alias pair, this set becomes a may alias. 48 if (AA.alias(L->getValue(), L->getSize(), R->getValue(), R->getSize()) 49 != AliasAnalysis::MustAlias) 50 AliasTy = MayAlias; 51 } 52 53 if (CallSites.empty()) { // Merge call sites... 54 if (!AS.CallSites.empty()) 55 std::swap(CallSites, AS.CallSites); 56 } else if (!AS.CallSites.empty()) { 57 CallSites.insert(CallSites.end(), AS.CallSites.begin(), AS.CallSites.end()); 58 AS.CallSites.clear(); 59 } 60 61 AS.Forward = this; // Forward across AS now... 62 addRef(); // AS is now pointing to us... 63 64 // Merge the list of constituent pointers... 65 if (AS.PtrList) { 66 *PtrListEnd = AS.PtrList; 67 AS.PtrList->setPrevInList(PtrListEnd); 68 PtrListEnd = AS.PtrListEnd; 69 70 AS.PtrList = 0; 71 AS.PtrListEnd = &AS.PtrList; 72 assert(*AS.PtrListEnd == 0 && "End of list is not null?"); 73 } 74} 75 76void AliasSetTracker::removeAliasSet(AliasSet *AS) { 77 if (AliasSet *Fwd = AS->Forward) { 78 Fwd->dropRef(*this); 79 AS->Forward = 0; 80 } 81 AliasSets.erase(AS); 82} 83 84void AliasSet::removeFromTracker(AliasSetTracker &AST) { 85 assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!"); 86 AST.removeAliasSet(this); 87} 88 89void AliasSet::addPointer(AliasSetTracker &AST, PointerRec &Entry, 90 unsigned Size, bool KnownMustAlias) { 91 assert(!Entry.hasAliasSet() && "Entry already in set!"); 92 93 // Check to see if we have to downgrade to _may_ alias. 94 if (isMustAlias() && !KnownMustAlias) 95 if (PointerRec *P = getSomePointer()) { 96 AliasAnalysis &AA = AST.getAliasAnalysis(); 97 AliasAnalysis::AliasResult Result = 98 AA.alias(P->getValue(), P->getSize(), Entry.getValue(), Size); 99 if (Result == AliasAnalysis::MayAlias) 100 AliasTy = MayAlias; 101 else // First entry of must alias must have maximum size! 102 P->updateSize(Size); 103 assert(Result != AliasAnalysis::NoAlias && "Cannot be part of must set!"); 104 } 105 106 Entry.setAliasSet(this); 107 Entry.updateSize(Size); 108 109 // Add it to the end of the list... 110 assert(*PtrListEnd == 0 && "End of list is not null?"); 111 *PtrListEnd = &Entry; 112 PtrListEnd = Entry.setPrevInList(PtrListEnd); 113 assert(*PtrListEnd == 0 && "End of list is not null?"); 114 addRef(); // Entry points to alias set. 115} 116 117void AliasSet::addCallSite(CallSite CS, AliasAnalysis &AA) { 118 CallSites.push_back(CS.getInstruction()); 119 120 AliasAnalysis::ModRefBehavior Behavior = AA.getModRefBehavior(CS); 121 if (Behavior == AliasAnalysis::DoesNotAccessMemory) 122 return; 123 else if (Behavior == AliasAnalysis::OnlyReadsMemory) { 124 AliasTy = MayAlias; 125 AccessTy |= Refs; 126 return; 127 } 128 129 // FIXME: This should use mod/ref information to make this not suck so bad 130 AliasTy = MayAlias; 131 AccessTy = ModRef; 132} 133 134/// aliasesPointer - Return true if the specified pointer "may" (or must) 135/// alias one of the members in the set. 136/// 137bool AliasSet::aliasesPointer(const Value *Ptr, unsigned Size, 138 AliasAnalysis &AA) const { 139 if (AliasTy == MustAlias) { 140 assert(CallSites.empty() && "Illegal must alias set!"); 141 142 // If this is a set of MustAliases, only check to see if the pointer aliases 143 // SOME value in the set. 144 PointerRec *SomePtr = getSomePointer(); 145 assert(SomePtr && "Empty must-alias set??"); 146 return AA.alias(SomePtr->getValue(), SomePtr->getSize(), Ptr, Size); 147 } 148 149 // If this is a may-alias set, we have to check all of the pointers in the set 150 // to be sure it doesn't alias the set... 151 for (iterator I = begin(), E = end(); I != E; ++I) 152 if (AA.alias(Ptr, Size, I.getPointer(), I.getSize())) 153 return true; 154 155 // Check the call sites list and invoke list... 156 if (!CallSites.empty()) { 157 for (unsigned i = 0, e = CallSites.size(); i != e; ++i) 158 if (AA.getModRefInfo(CallSites[i], Ptr, Size) != AliasAnalysis::NoModRef) 159 return true; 160 } 161 162 return false; 163} 164 165bool AliasSet::aliasesCallSite(CallSite CS, AliasAnalysis &AA) const { 166 if (AA.doesNotAccessMemory(CS)) 167 return false; 168 169 for (unsigned i = 0, e = CallSites.size(); i != e; ++i) { 170 if (AA.getModRefInfo(getCallSite(i), CS) != AliasAnalysis::NoModRef || 171 AA.getModRefInfo(CS, getCallSite(i)) != AliasAnalysis::NoModRef) 172 return true; 173 } 174 175 for (iterator I = begin(), E = end(); I != E; ++I) 176 if (AA.getModRefInfo(CS, I.getPointer(), I.getSize()) != 177 AliasAnalysis::NoModRef) 178 return true; 179 180 return false; 181} 182 183void AliasSetTracker::clear() { 184 // Delete all the PointerRec entries. 185 for (PointerMapType::iterator I = PointerMap.begin(), E = PointerMap.end(); 186 I != E; ++I) 187 I->second->eraseFromList(); 188 189 PointerMap.clear(); 190 191 // The alias sets should all be clear now. 192 AliasSets.clear(); 193} 194 195 196/// findAliasSetForPointer - Given a pointer, find the one alias set to put the 197/// instruction referring to the pointer into. If there are multiple alias sets 198/// that may alias the pointer, merge them together and return the unified set. 199/// 200AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr, 201 unsigned Size) { 202 AliasSet *FoundSet = 0; 203 for (iterator I = begin(), E = end(); I != E; ++I) { 204 if (I->Forward || !I->aliasesPointer(Ptr, Size, AA)) continue; 205 206 if (FoundSet == 0) { // If this is the first alias set ptr can go into. 207 FoundSet = I; // Remember it. 208 } else { // Otherwise, we must merge the sets. 209 FoundSet->mergeSetIn(*I, *this); // Merge in contents. 210 } 211 } 212 213 return FoundSet; 214} 215 216/// containsPointer - Return true if the specified location is represented by 217/// this alias set, false otherwise. This does not modify the AST object or 218/// alias sets. 219bool AliasSetTracker::containsPointer(Value *Ptr, unsigned Size) const { 220 for (const_iterator I = begin(), E = end(); I != E; ++I) 221 if (!I->Forward && I->aliasesPointer(Ptr, Size, AA)) 222 return true; 223 return false; 224} 225 226 227 228AliasSet *AliasSetTracker::findAliasSetForCallSite(CallSite CS) { 229 AliasSet *FoundSet = 0; 230 for (iterator I = begin(), E = end(); I != E; ++I) { 231 if (I->Forward || !I->aliasesCallSite(CS, AA)) 232 continue; 233 234 if (FoundSet == 0) // If this is the first alias set ptr can go into. 235 FoundSet = I; // Remember it. 236 else if (!I->Forward) // Otherwise, we must merge the sets. 237 FoundSet->mergeSetIn(*I, *this); // Merge in contents. 238 } 239 return FoundSet; 240} 241 242 243 244 245/// getAliasSetForPointer - Return the alias set that the specified pointer 246/// lives in. 247AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, unsigned Size, 248 bool *New) { 249 AliasSet::PointerRec &Entry = getEntryFor(Pointer); 250 251 // Check to see if the pointer is already known. 252 if (Entry.hasAliasSet()) { 253 Entry.updateSize(Size); 254 // Return the set! 255 return *Entry.getAliasSet(*this)->getForwardedTarget(*this); 256 } 257 258 if (AliasSet *AS = findAliasSetForPointer(Pointer, Size)) { 259 // Add it to the alias set it aliases. 260 AS->addPointer(*this, Entry, Size); 261 return *AS; 262 } 263 264 if (New) *New = true; 265 // Otherwise create a new alias set to hold the loaded pointer. 266 AliasSets.push_back(new AliasSet()); 267 AliasSets.back().addPointer(*this, Entry, Size); 268 return AliasSets.back(); 269} 270 271bool AliasSetTracker::add(Value *Ptr, unsigned Size) { 272 bool NewPtr; 273 addPointer(Ptr, Size, AliasSet::NoModRef, NewPtr); 274 return NewPtr; 275} 276 277 278bool AliasSetTracker::add(LoadInst *LI) { 279 bool NewPtr; 280 AliasSet &AS = addPointer(LI->getOperand(0), 281 AA.getTypeStoreSize(LI->getType()), 282 AliasSet::Refs, NewPtr); 283 if (LI->isVolatile()) AS.setVolatile(); 284 return NewPtr; 285} 286 287bool AliasSetTracker::add(StoreInst *SI) { 288 bool NewPtr; 289 Value *Val = SI->getOperand(0); 290 AliasSet &AS = addPointer(SI->getOperand(1), 291 AA.getTypeStoreSize(Val->getType()), 292 AliasSet::Mods, NewPtr); 293 if (SI->isVolatile()) AS.setVolatile(); 294 return NewPtr; 295} 296 297bool AliasSetTracker::add(VAArgInst *VAAI) { 298 bool NewPtr; 299 addPointer(VAAI->getOperand(0), ~0, AliasSet::ModRef, NewPtr); 300 return NewPtr; 301} 302 303 304bool AliasSetTracker::add(CallSite CS) { 305 if (isa<DbgInfoIntrinsic>(CS.getInstruction())) 306 return true; // Ignore DbgInfo Intrinsics. 307 if (AA.doesNotAccessMemory(CS)) 308 return true; // doesn't alias anything 309 310 AliasSet *AS = findAliasSetForCallSite(CS); 311 if (AS) { 312 AS->addCallSite(CS, AA); 313 return false; 314 } 315 AliasSets.push_back(new AliasSet()); 316 AS = &AliasSets.back(); 317 AS->addCallSite(CS, AA); 318 return true; 319} 320 321bool AliasSetTracker::add(Instruction *I) { 322 // Dispatch to one of the other add methods. 323 if (LoadInst *LI = dyn_cast<LoadInst>(I)) 324 return add(LI); 325 if (StoreInst *SI = dyn_cast<StoreInst>(I)) 326 return add(SI); 327 if (CallInst *CI = dyn_cast<CallInst>(I)) 328 return add(CI); 329 if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 330 return add(II); 331 if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I)) 332 return add(VAAI); 333 return true; 334} 335 336void AliasSetTracker::add(BasicBlock &BB) { 337 for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 338 add(I); 339} 340 341void AliasSetTracker::add(const AliasSetTracker &AST) { 342 assert(&AA == &AST.AA && 343 "Merging AliasSetTracker objects with different Alias Analyses!"); 344 345 // Loop over all of the alias sets in AST, adding the pointers contained 346 // therein into the current alias sets. This can cause alias sets to be 347 // merged together in the current AST. 348 for (const_iterator I = AST.begin(), E = AST.end(); I != E; ++I) { 349 if (I->Forward) continue; // Ignore forwarding alias sets 350 351 AliasSet &AS = const_cast<AliasSet&>(*I); 352 353 // If there are any call sites in the alias set, add them to this AST. 354 for (unsigned i = 0, e = AS.CallSites.size(); i != e; ++i) 355 add(AS.CallSites[i]); 356 357 // Loop over all of the pointers in this alias set. 358 bool X; 359 for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) { 360 AliasSet &NewAS = addPointer(ASI.getPointer(), ASI.getSize(), 361 (AliasSet::AccessType)AS.AccessTy, X); 362 if (AS.isVolatile()) NewAS.setVolatile(); 363 } 364 } 365} 366 367/// remove - Remove the specified (potentially non-empty) alias set from the 368/// tracker. 369void AliasSetTracker::remove(AliasSet &AS) { 370 // Drop all call sites. 371 AS.CallSites.clear(); 372 373 // Clear the alias set. 374 unsigned NumRefs = 0; 375 while (!AS.empty()) { 376 AliasSet::PointerRec *P = AS.PtrList; 377 378 Value *ValToRemove = P->getValue(); 379 380 // Unlink and delete entry from the list of values. 381 P->eraseFromList(); 382 383 // Remember how many references need to be dropped. 384 ++NumRefs; 385 386 // Finally, remove the entry. 387 PointerMap.erase(ValToRemove); 388 } 389 390 // Stop using the alias set, removing it. 391 AS.RefCount -= NumRefs; 392 if (AS.RefCount == 0) 393 AS.removeFromTracker(*this); 394} 395 396bool AliasSetTracker::remove(Value *Ptr, unsigned Size) { 397 AliasSet *AS = findAliasSetForPointer(Ptr, Size); 398 if (!AS) return false; 399 remove(*AS); 400 return true; 401} 402 403bool AliasSetTracker::remove(LoadInst *LI) { 404 unsigned Size = AA.getTypeStoreSize(LI->getType()); 405 AliasSet *AS = findAliasSetForPointer(LI->getOperand(0), Size); 406 if (!AS) return false; 407 remove(*AS); 408 return true; 409} 410 411bool AliasSetTracker::remove(StoreInst *SI) { 412 unsigned Size = AA.getTypeStoreSize(SI->getOperand(0)->getType()); 413 AliasSet *AS = findAliasSetForPointer(SI->getOperand(1), Size); 414 if (!AS) return false; 415 remove(*AS); 416 return true; 417} 418 419bool AliasSetTracker::remove(VAArgInst *VAAI) { 420 AliasSet *AS = findAliasSetForPointer(VAAI->getOperand(0), ~0); 421 if (!AS) return false; 422 remove(*AS); 423 return true; 424} 425 426bool AliasSetTracker::remove(CallSite CS) { 427 if (AA.doesNotAccessMemory(CS)) 428 return false; // doesn't alias anything 429 430 AliasSet *AS = findAliasSetForCallSite(CS); 431 if (!AS) return false; 432 remove(*AS); 433 return true; 434} 435 436bool AliasSetTracker::remove(Instruction *I) { 437 // Dispatch to one of the other remove methods... 438 if (LoadInst *LI = dyn_cast<LoadInst>(I)) 439 return remove(LI); 440 if (StoreInst *SI = dyn_cast<StoreInst>(I)) 441 return remove(SI); 442 if (CallInst *CI = dyn_cast<CallInst>(I)) 443 return remove(CI); 444 if (VAArgInst *VAAI = dyn_cast<VAArgInst>(I)) 445 return remove(VAAI); 446 return true; 447} 448 449 450// deleteValue method - This method is used to remove a pointer value from the 451// AliasSetTracker entirely. It should be used when an instruction is deleted 452// from the program to update the AST. If you don't use this, you would have 453// dangling pointers to deleted instructions. 454// 455void AliasSetTracker::deleteValue(Value *PtrVal) { 456 // Notify the alias analysis implementation that this value is gone. 457 AA.deleteValue(PtrVal); 458 459 // If this is a call instruction, remove the callsite from the appropriate 460 // AliasSet (if present). 461 if (CallSite CS = PtrVal) { 462 if (!AA.doesNotAccessMemory(CS)) { 463 // Scan all the alias sets to see if this call site is contained. 464 for (iterator I = begin(), E = end(); I != E; ++I) { 465 if (I->Forward) continue; 466 467 I->removeCallSite(CS); 468 } 469 } 470 } 471 472 // First, look up the PointerRec for this pointer. 473 PointerMapType::iterator I = PointerMap.find(PtrVal); 474 if (I == PointerMap.end()) return; // Noop 475 476 // If we found one, remove the pointer from the alias set it is in. 477 AliasSet::PointerRec *PtrValEnt = I->second; 478 AliasSet *AS = PtrValEnt->getAliasSet(*this); 479 480 // Unlink and delete from the list of values. 481 PtrValEnt->eraseFromList(); 482 483 // Stop using the alias set. 484 AS->dropRef(*this); 485 486 PointerMap.erase(I); 487} 488 489// copyValue - This method should be used whenever a preexisting value in the 490// program is copied or cloned, introducing a new value. Note that it is ok for 491// clients that use this method to introduce the same value multiple times: if 492// the tracker already knows about a value, it will ignore the request. 493// 494void AliasSetTracker::copyValue(Value *From, Value *To) { 495 // Notify the alias analysis implementation that this value is copied. 496 AA.copyValue(From, To); 497 498 // First, look up the PointerRec for this pointer. 499 PointerMapType::iterator I = PointerMap.find(From); 500 if (I == PointerMap.end()) 501 return; // Noop 502 assert(I->second->hasAliasSet() && "Dead entry?"); 503 504 AliasSet::PointerRec &Entry = getEntryFor(To); 505 if (Entry.hasAliasSet()) return; // Already in the tracker! 506 507 // Add it to the alias set it aliases... 508 I = PointerMap.find(From); 509 AliasSet *AS = I->second->getAliasSet(*this); 510 AS->addPointer(*this, Entry, I->second->getSize(), true); 511} 512 513 514 515//===----------------------------------------------------------------------===// 516// AliasSet/AliasSetTracker Printing Support 517//===----------------------------------------------------------------------===// 518 519void AliasSet::print(raw_ostream &OS) const { 520 OS << " AliasSet[" << (void*)this << ", " << RefCount << "] "; 521 OS << (AliasTy == MustAlias ? "must" : "may") << " alias, "; 522 switch (AccessTy) { 523 case NoModRef: OS << "No access "; break; 524 case Refs : OS << "Ref "; break; 525 case Mods : OS << "Mod "; break; 526 case ModRef : OS << "Mod/Ref "; break; 527 default: llvm_unreachable("Bad value for AccessTy!"); 528 } 529 if (isVolatile()) OS << "[volatile] "; 530 if (Forward) 531 OS << " forwarding to " << (void*)Forward; 532 533 534 if (!empty()) { 535 OS << "Pointers: "; 536 for (iterator I = begin(), E = end(); I != E; ++I) { 537 if (I != begin()) OS << ", "; 538 WriteAsOperand(OS << "(", I.getPointer()); 539 OS << ", " << I.getSize() << ")"; 540 } 541 } 542 if (!CallSites.empty()) { 543 OS << "\n " << CallSites.size() << " Call Sites: "; 544 for (unsigned i = 0, e = CallSites.size(); i != e; ++i) { 545 if (i) OS << ", "; 546 WriteAsOperand(OS, CallSites[i]); 547 } 548 } 549 OS << "\n"; 550} 551 552void AliasSetTracker::print(raw_ostream &OS) const { 553 OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for " 554 << PointerMap.size() << " pointer values.\n"; 555 for (const_iterator I = begin(), E = end(); I != E; ++I) 556 I->print(OS); 557 OS << "\n"; 558} 559 560void AliasSet::dump() const { print(dbgs()); } 561void AliasSetTracker::dump() const { print(dbgs()); } 562 563//===----------------------------------------------------------------------===// 564// ASTCallbackVH Class Implementation 565//===----------------------------------------------------------------------===// 566 567void AliasSetTracker::ASTCallbackVH::deleted() { 568 assert(AST && "ASTCallbackVH called with a null AliasSetTracker!"); 569 AST->deleteValue(getValPtr()); 570 // this now dangles! 571} 572 573AliasSetTracker::ASTCallbackVH::ASTCallbackVH(Value *V, AliasSetTracker *ast) 574 : CallbackVH(V), AST(ast) {} 575 576AliasSetTracker::ASTCallbackVH & 577AliasSetTracker::ASTCallbackVH::operator=(Value *V) { 578 return *this = ASTCallbackVH(V, AST); 579} 580 581//===----------------------------------------------------------------------===// 582// AliasSetPrinter Pass 583//===----------------------------------------------------------------------===// 584 585namespace { 586 class AliasSetPrinter : public FunctionPass { 587 AliasSetTracker *Tracker; 588 public: 589 static char ID; // Pass identification, replacement for typeid 590 AliasSetPrinter() : FunctionPass(ID) {} 591 592 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 593 AU.setPreservesAll(); 594 AU.addRequired<AliasAnalysis>(); 595 } 596 597 virtual bool runOnFunction(Function &F) { 598 Tracker = new AliasSetTracker(getAnalysis<AliasAnalysis>()); 599 600 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 601 Tracker->add(&*I); 602 Tracker->print(errs()); 603 delete Tracker; 604 return false; 605 } 606 }; 607} 608 609char AliasSetPrinter::ID = 0; 610INITIALIZE_PASS(AliasSetPrinter, "print-alias-sets", 611 "Alias Set Printer", false, true); 612