LLVM API Documentation
00001 //===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file was developed by the LLVM research group and is distributed under 00006 // the University of Illinois Open Source License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file implements the AliasSetTracker and AliasSet classes. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #include "llvm/Analysis/AliasSetTracker.h" 00015 #include "llvm/Analysis/AliasAnalysis.h" 00016 #include "llvm/Instructions.h" 00017 #include "llvm/Pass.h" 00018 #include "llvm/Type.h" 00019 #include "llvm/Target/TargetData.h" 00020 #include "llvm/Assembly/Writer.h" 00021 #include "llvm/Support/InstIterator.h" 00022 #include <iostream> 00023 using namespace llvm; 00024 00025 /// mergeSetIn - Merge the specified alias set into this alias set. 00026 /// 00027 void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) { 00028 assert(!AS.Forward && "Alias set is already forwarding!"); 00029 assert(!Forward && "This set is a forwarding set!!"); 00030 00031 // Update the alias and access types of this set... 00032 AccessTy |= AS.AccessTy; 00033 AliasTy |= AS.AliasTy; 00034 00035 if (AliasTy == MustAlias) { 00036 // Check that these two merged sets really are must aliases. Since both 00037 // used to be must-alias sets, we can just check any pointer from each set 00038 // for aliasing. 00039 AliasAnalysis &AA = AST.getAliasAnalysis(); 00040 HashNodePair *L = getSomePointer(); 00041 HashNodePair *R = AS.getSomePointer(); 00042 00043 // If the pointers are not a must-alias pair, this set becomes a may alias. 00044 if (AA.alias(L->first, L->second.getSize(), R->first, R->second.getSize()) 00045 != AliasAnalysis::MustAlias) 00046 AliasTy = MayAlias; 00047 } 00048 00049 if (CallSites.empty()) { // Merge call sites... 00050 if (!AS.CallSites.empty()) 00051 std::swap(CallSites, AS.CallSites); 00052 } else if (!AS.CallSites.empty()) { 00053 CallSites.insert(CallSites.end(), AS.CallSites.begin(), AS.CallSites.end()); 00054 AS.CallSites.clear(); 00055 } 00056 00057 AS.Forward = this; // Forward across AS now... 00058 addRef(); // AS is now pointing to us... 00059 00060 // Merge the list of constituent pointers... 00061 if (AS.PtrList) { 00062 *PtrListEnd = AS.PtrList; 00063 AS.PtrList->second.setPrevInList(PtrListEnd); 00064 PtrListEnd = AS.PtrListEnd; 00065 00066 AS.PtrList = 0; 00067 AS.PtrListEnd = &AS.PtrList; 00068 assert(*AS.PtrListEnd == 0 && "End of list is not null?"); 00069 } 00070 } 00071 00072 void AliasSetTracker::removeAliasSet(AliasSet *AS) { 00073 if (AliasSet *Fwd = AS->Forward) { 00074 Fwd->dropRef(*this); 00075 AS->Forward = 0; 00076 } 00077 AliasSets.erase(AS); 00078 } 00079 00080 void AliasSet::removeFromTracker(AliasSetTracker &AST) { 00081 assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!"); 00082 AST.removeAliasSet(this); 00083 } 00084 00085 void AliasSet::addPointer(AliasSetTracker &AST, HashNodePair &Entry, 00086 unsigned Size, bool KnownMustAlias) { 00087 assert(!Entry.second.hasAliasSet() && "Entry already in set!"); 00088 00089 // Check to see if we have to downgrade to _may_ alias. 00090 if (isMustAlias() && !KnownMustAlias) 00091 if (HashNodePair *P = getSomePointer()) { 00092 AliasAnalysis &AA = AST.getAliasAnalysis(); 00093 AliasAnalysis::AliasResult Result = 00094 AA.alias(P->first, P->second.getSize(), Entry.first, Size); 00095 if (Result == AliasAnalysis::MayAlias) 00096 AliasTy = MayAlias; 00097 else // First entry of must alias must have maximum size! 00098 P->second.updateSize(Size); 00099 assert(Result != AliasAnalysis::NoAlias && "Cannot be part of must set!"); 00100 } 00101 00102 Entry.second.setAliasSet(this); 00103 Entry.second.updateSize(Size); 00104 00105 // Add it to the end of the list... 00106 assert(*PtrListEnd == 0 && "End of list is not null?"); 00107 *PtrListEnd = &Entry; 00108 PtrListEnd = Entry.second.setPrevInList(PtrListEnd); 00109 assert(*PtrListEnd == 0 && "End of list is not null?"); 00110 addRef(); // Entry points to alias set... 00111 } 00112 00113 void AliasSet::addCallSite(CallSite CS, AliasAnalysis &AA) { 00114 CallSites.push_back(CS); 00115 00116 if (Function *F = CS.getCalledFunction()) { 00117 AliasAnalysis::ModRefBehavior Behavior = AA.getModRefBehavior(F, CS); 00118 if (Behavior == AliasAnalysis::DoesNotAccessMemory) 00119 return; 00120 else if (Behavior == AliasAnalysis::OnlyReadsMemory) { 00121 AliasTy = MayAlias; 00122 AccessTy |= Refs; 00123 return; 00124 } 00125 } 00126 00127 // FIXME: This should use mod/ref information to make this not suck so bad 00128 AliasTy = MayAlias; 00129 AccessTy = ModRef; 00130 } 00131 00132 /// aliasesPointer - Return true if the specified pointer "may" (or must) 00133 /// alias one of the members in the set. 00134 /// 00135 bool AliasSet::aliasesPointer(const Value *Ptr, unsigned Size, 00136 AliasAnalysis &AA) const { 00137 if (AliasTy == MustAlias) { 00138 assert(CallSites.empty() && "Illegal must alias set!"); 00139 00140 // If this is a set of MustAliases, only check to see if the pointer aliases 00141 // SOME value in the set... 00142 HashNodePair *SomePtr = getSomePointer(); 00143 assert(SomePtr && "Empty must-alias set??"); 00144 return AA.alias(SomePtr->first, SomePtr->second.getSize(), Ptr, Size); 00145 } 00146 00147 // If this is a may-alias set, we have to check all of the pointers in the set 00148 // to be sure it doesn't alias the set... 00149 for (iterator I = begin(), E = end(); I != E; ++I) 00150 if (AA.alias(Ptr, Size, I.getPointer(), I.getSize())) 00151 return true; 00152 00153 // Check the call sites list and invoke list... 00154 if (!CallSites.empty()) { 00155 if (AA.hasNoModRefInfoForCalls()) 00156 return true; 00157 00158 for (unsigned i = 0, e = CallSites.size(); i != e; ++i) 00159 if (AA.getModRefInfo(CallSites[i], const_cast<Value*>(Ptr), Size) 00160 != AliasAnalysis::NoModRef) 00161 return true; 00162 } 00163 00164 return false; 00165 } 00166 00167 bool AliasSet::aliasesCallSite(CallSite CS, AliasAnalysis &AA) const { 00168 if (Function *F = CS.getCalledFunction()) 00169 if (AA.doesNotAccessMemory(F)) 00170 return false; 00171 00172 if (AA.hasNoModRefInfoForCalls()) 00173 return true; 00174 00175 for (unsigned i = 0, e = CallSites.size(); i != e; ++i) 00176 if (AA.getModRefInfo(CallSites[i], CS) != AliasAnalysis::NoModRef || 00177 AA.getModRefInfo(CS, CallSites[i]) != AliasAnalysis::NoModRef) 00178 return true; 00179 00180 for (iterator I = begin(), E = end(); I != E; ++I) 00181 if (AA.getModRefInfo(CS, I.getPointer(), I.getSize()) != 00182 AliasAnalysis::NoModRef) 00183 return true; 00184 00185 return false; 00186 } 00187 00188 00189 /// findAliasSetForPointer - Given a pointer, find the one alias set to put the 00190 /// instruction referring to the pointer into. If there are multiple alias sets 00191 /// that may alias the pointer, merge them together and return the unified set. 00192 /// 00193 AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr, 00194 unsigned Size) { 00195 AliasSet *FoundSet = 0; 00196 for (iterator I = begin(), E = end(); I != E; ++I) 00197 if (!I->Forward && I->aliasesPointer(Ptr, Size, AA)) { 00198 if (FoundSet == 0) { // If this is the first alias set ptr can go into. 00199 FoundSet = I; // Remember it. 00200 } else { // Otherwise, we must merge the sets. 00201 FoundSet->mergeSetIn(*I, *this); // Merge in contents. 00202 } 00203 } 00204 00205 return FoundSet; 00206 } 00207 00208 /// containsPointer - Return true if the specified location is represented by 00209 /// this alias set, false otherwise. This does not modify the AST object or 00210 /// alias sets. 00211 bool AliasSetTracker::containsPointer(Value *Ptr, unsigned Size) const { 00212 for (const_iterator I = begin(), E = end(); I != E; ++I) 00213 if (!I->Forward && I->aliasesPointer(Ptr, Size, AA)) 00214 return true; 00215 return false; 00216 } 00217 00218 00219 00220 AliasSet *AliasSetTracker::findAliasSetForCallSite(CallSite CS) { 00221 AliasSet *FoundSet = 0; 00222 for (iterator I = begin(), E = end(); I != E; ++I) 00223 if (!I->Forward && I->aliasesCallSite(CS, AA)) { 00224 if (FoundSet == 0) { // If this is the first alias set ptr can go into. 00225 FoundSet = I; // Remember it. 00226 } else if (!I->Forward) { // Otherwise, we must merge the sets. 00227 FoundSet->mergeSetIn(*I, *this); // Merge in contents. 00228 } 00229 } 00230 00231 return FoundSet; 00232 } 00233 00234 00235 00236 00237 /// getAliasSetForPointer - Return the alias set that the specified pointer 00238 /// lives in... 00239 AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, unsigned Size, 00240 bool *New) { 00241 AliasSet::HashNodePair &Entry = getEntryFor(Pointer); 00242 00243 // Check to see if the pointer is already known... 00244 if (Entry.second.hasAliasSet()) { 00245 Entry.second.updateSize(Size); 00246 // Return the set! 00247 return *Entry.second.getAliasSet(*this)->getForwardedTarget(*this); 00248 } else if (AliasSet *AS = findAliasSetForPointer(Pointer, Size)) { 00249 // Add it to the alias set it aliases... 00250 AS->addPointer(*this, Entry, Size); 00251 return *AS; 00252 } else { 00253 if (New) *New = true; 00254 // Otherwise create a new alias set to hold the loaded pointer... 00255 AliasSets.push_back(new AliasSet()); 00256 AliasSets.back().addPointer(*this, Entry, Size); 00257 return AliasSets.back(); 00258 } 00259 } 00260 00261 bool AliasSetTracker::add(Value *Ptr, unsigned Size) { 00262 bool NewPtr; 00263 addPointer(Ptr, Size, AliasSet::NoModRef, NewPtr); 00264 return NewPtr; 00265 } 00266 00267 00268 bool AliasSetTracker::add(LoadInst *LI) { 00269 bool NewPtr; 00270 AliasSet &AS = addPointer(LI->getOperand(0), 00271 AA.getTargetData().getTypeSize(LI->getType()), 00272 AliasSet::Refs, NewPtr); 00273 if (LI->isVolatile()) AS.setVolatile(); 00274 return NewPtr; 00275 } 00276 00277 bool AliasSetTracker::add(StoreInst *SI) { 00278 bool NewPtr; 00279 Value *Val = SI->getOperand(0); 00280 AliasSet &AS = addPointer(SI->getOperand(1), 00281 AA.getTargetData().getTypeSize(Val->getType()), 00282 AliasSet::Mods, NewPtr); 00283 if (SI->isVolatile()) AS.setVolatile(); 00284 return NewPtr; 00285 } 00286 00287 bool AliasSetTracker::add(FreeInst *FI) { 00288 bool NewPtr; 00289 AliasSet &AS = addPointer(FI->getOperand(0), ~0, 00290 AliasSet::Mods, NewPtr); 00291 00292 // Free operations are volatile ops (cannot be moved). 00293 AS.setVolatile(); 00294 return NewPtr; 00295 } 00296 00297 00298 bool AliasSetTracker::add(CallSite CS) { 00299 if (Function *F = CS.getCalledFunction()) 00300 if (AA.doesNotAccessMemory(F)) 00301 return true; // doesn't alias anything 00302 00303 AliasSet *AS = findAliasSetForCallSite(CS); 00304 if (!AS) { 00305 AliasSets.push_back(new AliasSet()); 00306 AS = &AliasSets.back(); 00307 AS->addCallSite(CS, AA); 00308 return true; 00309 } else { 00310 AS->addCallSite(CS, AA); 00311 return false; 00312 } 00313 } 00314 00315 bool AliasSetTracker::add(Instruction *I) { 00316 // Dispatch to one of the other add methods... 00317 if (LoadInst *LI = dyn_cast<LoadInst>(I)) 00318 return add(LI); 00319 else if (StoreInst *SI = dyn_cast<StoreInst>(I)) 00320 return add(SI); 00321 else if (CallInst *CI = dyn_cast<CallInst>(I)) 00322 return add(CI); 00323 else if (InvokeInst *II = dyn_cast<InvokeInst>(I)) 00324 return add(II); 00325 else if (FreeInst *FI = dyn_cast<FreeInst>(I)) 00326 return add(FI); 00327 return true; 00328 } 00329 00330 void AliasSetTracker::add(BasicBlock &BB) { 00331 for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) 00332 add(I); 00333 } 00334 00335 void AliasSetTracker::add(const AliasSetTracker &AST) { 00336 assert(&AA == &AST.AA && 00337 "Merging AliasSetTracker objects with different Alias Analyses!"); 00338 00339 // Loop over all of the alias sets in AST, adding the pointers contained 00340 // therein into the current alias sets. This can cause alias sets to be 00341 // merged together in the current AST. 00342 for (const_iterator I = AST.begin(), E = AST.end(); I != E; ++I) 00343 if (!I->Forward) { // Ignore forwarding alias sets 00344 AliasSet &AS = const_cast<AliasSet&>(*I); 00345 00346 // If there are any call sites in the alias set, add them to this AST. 00347 for (unsigned i = 0, e = AS.CallSites.size(); i != e; ++i) 00348 add(AS.CallSites[i]); 00349 00350 // Loop over all of the pointers in this alias set... 00351 AliasSet::iterator I = AS.begin(), E = AS.end(); 00352 bool X; 00353 for (; I != E; ++I) 00354 addPointer(I.getPointer(), I.getSize(), 00355 (AliasSet::AccessType)AS.AccessTy, X); 00356 } 00357 } 00358 00359 /// remove - Remove the specified (potentially non-empty) alias set from the 00360 /// tracker. 00361 void AliasSetTracker::remove(AliasSet &AS) { 00362 // Drop all call sites. 00363 AS.CallSites.clear(); 00364 00365 // Clear the alias set. 00366 unsigned NumRefs = 0; 00367 while (!AS.empty()) { 00368 AliasSet::HashNodePair *P = AS.PtrList; 00369 00370 // Unlink from the list of values. 00371 P->second.removeFromList(); 00372 00373 // Remember how many references need to be dropped. 00374 ++NumRefs; 00375 00376 // Finally, remove the entry. 00377 PointerMap.erase(P->first); 00378 } 00379 00380 // Stop using the alias set, removing it. 00381 AS.RefCount -= NumRefs; 00382 if (AS.RefCount == 0) 00383 AS.removeFromTracker(*this); 00384 } 00385 00386 bool AliasSetTracker::remove(Value *Ptr, unsigned Size) { 00387 AliasSet *AS = findAliasSetForPointer(Ptr, Size); 00388 if (!AS) return false; 00389 remove(*AS); 00390 return true; 00391 } 00392 00393 bool AliasSetTracker::remove(LoadInst *LI) { 00394 unsigned Size = AA.getTargetData().getTypeSize(LI->getType()); 00395 AliasSet *AS = findAliasSetForPointer(LI->getOperand(0), Size); 00396 if (!AS) return false; 00397 remove(*AS); 00398 return true; 00399 } 00400 00401 bool AliasSetTracker::remove(StoreInst *SI) { 00402 unsigned Size = AA.getTargetData().getTypeSize(SI->getOperand(0)->getType()); 00403 AliasSet *AS = findAliasSetForPointer(SI->getOperand(1), Size); 00404 if (!AS) return false; 00405 remove(*AS); 00406 return true; 00407 } 00408 00409 bool AliasSetTracker::remove(FreeInst *FI) { 00410 AliasSet *AS = findAliasSetForPointer(FI->getOperand(0), ~0); 00411 if (!AS) return false; 00412 remove(*AS); 00413 return true; 00414 } 00415 00416 bool AliasSetTracker::remove(CallSite CS) { 00417 if (Function *F = CS.getCalledFunction()) 00418 if (AA.doesNotAccessMemory(F)) 00419 return false; // doesn't alias anything 00420 00421 AliasSet *AS = findAliasSetForCallSite(CS); 00422 if (!AS) return false; 00423 remove(*AS); 00424 return true; 00425 } 00426 00427 bool AliasSetTracker::remove(Instruction *I) { 00428 // Dispatch to one of the other remove methods... 00429 if (LoadInst *LI = dyn_cast<LoadInst>(I)) 00430 return remove(LI); 00431 else if (StoreInst *SI = dyn_cast<StoreInst>(I)) 00432 return remove(SI); 00433 else if (CallInst *CI = dyn_cast<CallInst>(I)) 00434 return remove(CI); 00435 else if (FreeInst *FI = dyn_cast<FreeInst>(I)) 00436 return remove(FI); 00437 return true; 00438 } 00439 00440 00441 // deleteValue method - This method is used to remove a pointer value from the 00442 // AliasSetTracker entirely. It should be used when an instruction is deleted 00443 // from the program to update the AST. If you don't use this, you would have 00444 // dangling pointers to deleted instructions. 00445 // 00446 void AliasSetTracker::deleteValue(Value *PtrVal) { 00447 // Notify the alias analysis implementation that this value is gone. 00448 AA.deleteValue(PtrVal); 00449 00450 // If this is a call instruction, remove the callsite from the appropriate 00451 // AliasSet. 00452 CallSite CS = CallSite::get(PtrVal); 00453 if (CS.getInstruction()) { 00454 Function *F = CS.getCalledFunction(); 00455 if (!F || !AA.doesNotAccessMemory(F)) { 00456 if (AliasSet *AS = findAliasSetForCallSite(CS)) 00457 AS->removeCallSite(CS); 00458 } 00459 } 00460 00461 // First, look up the PointerRec for this pointer. 00462 hash_map<Value*, AliasSet::PointerRec>::iterator I = PointerMap.find(PtrVal); 00463 if (I == PointerMap.end()) return; // Noop 00464 00465 // If we found one, remove the pointer from the alias set it is in. 00466 AliasSet::HashNodePair &PtrValEnt = *I; 00467 AliasSet *AS = PtrValEnt.second.getAliasSet(*this); 00468 00469 // Unlink from the list of values... 00470 PtrValEnt.second.removeFromList(); 00471 // Stop using the alias set 00472 AS->dropRef(*this); 00473 PointerMap.erase(I); 00474 } 00475 00476 // copyValue - This method should be used whenever a preexisting value in the 00477 // program is copied or cloned, introducing a new value. Note that it is ok for 00478 // clients that use this method to introduce the same value multiple times: if 00479 // the tracker already knows about a value, it will ignore the request. 00480 // 00481 void AliasSetTracker::copyValue(Value *From, Value *To) { 00482 // Notify the alias analysis implementation that this value is copied. 00483 AA.copyValue(From, To); 00484 00485 // First, look up the PointerRec for this pointer. 00486 hash_map<Value*, AliasSet::PointerRec>::iterator I = PointerMap.find(From); 00487 if (I == PointerMap.end() || !I->second.hasAliasSet()) 00488 return; // Noop 00489 00490 AliasSet::HashNodePair &Entry = getEntryFor(To); 00491 if (Entry.second.hasAliasSet()) return; // Already in the tracker! 00492 00493 // Add it to the alias set it aliases... 00494 AliasSet *AS = I->second.getAliasSet(*this); 00495 AS->addPointer(*this, Entry, I->second.getSize(), true); 00496 } 00497 00498 00499 00500 //===----------------------------------------------------------------------===// 00501 // AliasSet/AliasSetTracker Printing Support 00502 //===----------------------------------------------------------------------===// 00503 00504 void AliasSet::print(std::ostream &OS) const { 00505 OS << " AliasSet[" << (void*)this << "," << RefCount << "] "; 00506 OS << (AliasTy == MustAlias ? "must" : "may ") << " alias, "; 00507 switch (AccessTy) { 00508 case NoModRef: OS << "No access "; break; 00509 case Refs : OS << "Ref "; break; 00510 case Mods : OS << "Mod "; break; 00511 case ModRef : OS << "Mod/Ref "; break; 00512 default: assert(0 && "Bad value for AccessTy!"); 00513 } 00514 if (isVolatile()) OS << "[volatile] "; 00515 if (Forward) 00516 OS << " forwarding to " << (void*)Forward; 00517 00518 00519 if (begin() != end()) { 00520 OS << "Pointers: "; 00521 for (iterator I = begin(), E = end(); I != E; ++I) { 00522 if (I != begin()) OS << ", "; 00523 WriteAsOperand(OS << "(", I.getPointer()); 00524 OS << ", " << I.getSize() << ")"; 00525 } 00526 } 00527 if (!CallSites.empty()) { 00528 OS << "\n " << CallSites.size() << " Call Sites: "; 00529 for (unsigned i = 0, e = CallSites.size(); i != e; ++i) { 00530 if (i) OS << ", "; 00531 WriteAsOperand(OS, CallSites[i].getCalledValue()); 00532 } 00533 } 00534 OS << "\n"; 00535 } 00536 00537 void AliasSetTracker::print(std::ostream &OS) const { 00538 OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for " 00539 << PointerMap.size() << " pointer values.\n"; 00540 for (const_iterator I = begin(), E = end(); I != E; ++I) 00541 I->print(OS); 00542 OS << "\n"; 00543 } 00544 00545 void AliasSet::dump() const { print (std::cerr); } 00546 void AliasSetTracker::dump() const { print(std::cerr); } 00547 00548 //===----------------------------------------------------------------------===// 00549 // AliasSetPrinter Pass 00550 //===----------------------------------------------------------------------===// 00551 00552 namespace { 00553 class AliasSetPrinter : public FunctionPass { 00554 AliasSetTracker *Tracker; 00555 public: 00556 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 00557 AU.setPreservesAll(); 00558 AU.addRequired<AliasAnalysis>(); 00559 } 00560 00561 virtual bool runOnFunction(Function &F) { 00562 Tracker = new AliasSetTracker(getAnalysis<AliasAnalysis>()); 00563 00564 for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) 00565 Tracker->add(&*I); 00566 Tracker->print(std::cerr); 00567 delete Tracker; 00568 return false; 00569 } 00570 }; 00571 RegisterOpt<AliasSetPrinter> X("print-alias-sets", "Alias Set Printer"); 00572 }