LLVM API Documentation

AliasSetTracker.cpp

Go to the documentation of this file.
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   bool SetDead;
00363   do {
00364     AliasSet::iterator I = AS.begin();
00365     Value *Ptr = I.getPointer(); ++I;
00366 
00367     // deleteValue will delete the set automatically when the last pointer
00368     // reference is destroyed.  "Predict" when this will happen.
00369     SetDead = I == AS.end();
00370     deleteValue(Ptr);  // Delete all of the pointers from the set
00371   } while (!SetDead);
00372 }
00373 
00374 bool AliasSetTracker::remove(Value *Ptr, unsigned Size) {
00375   AliasSet *AS = findAliasSetForPointer(Ptr, Size);
00376   if (!AS) return false;
00377   remove(*AS);
00378   return true;
00379 }
00380 
00381 bool AliasSetTracker::remove(LoadInst *LI) {
00382   unsigned Size = AA.getTargetData().getTypeSize(LI->getType());
00383   AliasSet *AS = findAliasSetForPointer(LI->getOperand(0), Size);
00384   if (!AS) return false;
00385   remove(*AS);
00386   return true;
00387 }
00388 
00389 bool AliasSetTracker::remove(StoreInst *SI) {
00390   unsigned Size = AA.getTargetData().getTypeSize(SI->getOperand(0)->getType());
00391   AliasSet *AS = findAliasSetForPointer(SI->getOperand(1), Size);
00392   if (!AS) return false;
00393   remove(*AS);
00394   return true;
00395 }
00396 
00397 bool AliasSetTracker::remove(FreeInst *FI) {
00398   AliasSet *AS = findAliasSetForPointer(FI->getOperand(0), ~0);
00399   if (!AS) return false;
00400   remove(*AS);
00401   return true;
00402 }
00403 
00404 bool AliasSetTracker::remove(CallSite CS) {
00405   if (Function *F = CS.getCalledFunction())
00406     if (AA.doesNotAccessMemory(F))
00407       return false; // doesn't alias anything
00408 
00409   AliasSet *AS = findAliasSetForCallSite(CS);
00410   if (!AS) return false;
00411   remove(*AS);
00412   return true;
00413 }
00414 
00415 bool AliasSetTracker::remove(Instruction *I) {
00416   // Dispatch to one of the other remove methods...
00417   if (LoadInst *LI = dyn_cast<LoadInst>(I))
00418     return remove(LI);
00419   else if (StoreInst *SI = dyn_cast<StoreInst>(I))
00420     return remove(SI);
00421   else if (CallInst *CI = dyn_cast<CallInst>(I))
00422     return remove(CI);
00423   else if (FreeInst *FI = dyn_cast<FreeInst>(I))
00424     return remove(FI);
00425   return true;
00426 }
00427 
00428 
00429 // deleteValue method - This method is used to remove a pointer value from the
00430 // AliasSetTracker entirely.  It should be used when an instruction is deleted
00431 // from the program to update the AST.  If you don't use this, you would have
00432 // dangling pointers to deleted instructions.
00433 //
00434 void AliasSetTracker::deleteValue(Value *PtrVal) {
00435   // Notify the alias analysis implementation that this value is gone.
00436   AA.deleteValue(PtrVal);
00437 
00438   // First, look up the PointerRec for this pointer.
00439   hash_map<Value*, AliasSet::PointerRec>::iterator I = PointerMap.find(PtrVal);
00440   if (I == PointerMap.end()) return;  // Noop
00441 
00442   // If we found one, remove the pointer from the alias set it is in.
00443   AliasSet::HashNodePair &PtrValEnt = *I;
00444   AliasSet *AS = PtrValEnt.second.getAliasSet(*this);
00445 
00446   // Unlink from the list of values...
00447   PtrValEnt.second.removeFromList();
00448   // Stop using the alias set
00449   AS->dropRef(*this);
00450   PointerMap.erase(I);
00451 }
00452 
00453 // copyValue - This method should be used whenever a preexisting value in the
00454 // program is copied or cloned, introducing a new value.  Note that it is ok for
00455 // clients that use this method to introduce the same value multiple times: if
00456 // the tracker already knows about a value, it will ignore the request.
00457 //
00458 void AliasSetTracker::copyValue(Value *From, Value *To) {
00459   // Notify the alias analysis implementation that this value is copied.
00460   AA.copyValue(From, To);
00461 
00462   // First, look up the PointerRec for this pointer.
00463   hash_map<Value*, AliasSet::PointerRec>::iterator I = PointerMap.find(From);
00464   if (I == PointerMap.end() || !I->second.hasAliasSet())
00465     return;  // Noop
00466 
00467   AliasSet::HashNodePair &Entry = getEntryFor(To);
00468   if (Entry.second.hasAliasSet()) return;    // Already in the tracker!
00469 
00470   // Add it to the alias set it aliases...
00471   AliasSet *AS = I->second.getAliasSet(*this);
00472   AS->addPointer(*this, Entry, I->second.getSize(), true);
00473 }
00474 
00475 
00476 
00477 //===----------------------------------------------------------------------===//
00478 //               AliasSet/AliasSetTracker Printing Support
00479 //===----------------------------------------------------------------------===//
00480 
00481 void AliasSet::print(std::ostream &OS) const {
00482   OS << "  AliasSet[" << (void*)this << "," << RefCount << "] ";
00483   OS << (AliasTy == MustAlias ? "must" : "may ") << " alias, ";
00484   switch (AccessTy) {
00485   case NoModRef: OS << "No access "; break;
00486   case Refs    : OS << "Ref       "; break;
00487   case Mods    : OS << "Mod       "; break;
00488   case ModRef  : OS << "Mod/Ref   "; break;
00489   default: assert(0 && "Bad value for AccessTy!");
00490   }
00491   if (isVolatile()) OS << "[volatile] ";
00492   if (Forward)
00493     OS << " forwarding to " << (void*)Forward;
00494 
00495 
00496   if (begin() != end()) {
00497     OS << "Pointers: ";
00498     for (iterator I = begin(), E = end(); I != E; ++I) {
00499       if (I != begin()) OS << ", ";
00500       WriteAsOperand(OS << "(", I.getPointer());
00501       OS << ", " << I.getSize() << ")";
00502     }
00503   }
00504   if (!CallSites.empty()) {
00505     OS << "\n    " << CallSites.size() << " Call Sites: ";
00506     for (unsigned i = 0, e = CallSites.size(); i != e; ++i) {
00507       if (i) OS << ", ";
00508       WriteAsOperand(OS, CallSites[i].getCalledValue());
00509     }
00510   }
00511   OS << "\n";
00512 }
00513 
00514 void AliasSetTracker::print(std::ostream &OS) const {
00515   OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for "
00516      << PointerMap.size() << " pointer values.\n";
00517   for (const_iterator I = begin(), E = end(); I != E; ++I)
00518     I->print(OS);
00519   OS << "\n";
00520 }
00521 
00522 void AliasSet::dump() const { print (std::cerr); }
00523 void AliasSetTracker::dump() const { print(std::cerr); }
00524 
00525 //===----------------------------------------------------------------------===//
00526 //                            AliasSetPrinter Pass
00527 //===----------------------------------------------------------------------===//
00528 
00529 namespace {
00530   class AliasSetPrinter : public FunctionPass {
00531     AliasSetTracker *Tracker;
00532   public:
00533     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
00534       AU.setPreservesAll();
00535       AU.addRequired<AliasAnalysis>();
00536     }
00537 
00538     virtual bool runOnFunction(Function &F) {
00539       Tracker = new AliasSetTracker(getAnalysis<AliasAnalysis>());
00540 
00541       for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I)
00542         Tracker->add(&*I);
00543       Tracker->print(std::cerr);
00544       delete Tracker;
00545       return false;
00546     }
00547   };
00548   RegisterOpt<AliasSetPrinter> X("print-alias-sets", "Alias Set Printer");
00549 }