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