X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FAliasSetTracker.cpp;h=f00e5c8b311ecb7923b7b46c9e0e88e77bda4c5d;hb=c53544af06acf3fba1788613a364f1f40317869e;hp=1413660d92e83c2af8712d2284b3b8d4f17b1c7f;hpb=009cc3d2e85674f01f70d915e0c802d89d0b672f;p=oota-llvm.git diff --git a/lib/Analysis/AliasSetTracker.cpp b/lib/Analysis/AliasSetTracker.cpp index 1413660d92e..f00e5c8b311 100644 --- a/lib/Analysis/AliasSetTracker.cpp +++ b/lib/Analysis/AliasSetTracker.cpp @@ -9,164 +9,315 @@ #include "llvm/iMemory.h" #include "llvm/iOther.h" #include "llvm/iTerminators.h" +#include "llvm/Pass.h" +#include "llvm/Target/TargetData.h" +#include "llvm/Assembly/Writer.h" +#include "llvm/Support/InstIterator.h" -/// updateAccessTypes - Depending on what type of accesses are in this set, -/// decide whether the set contains just references, just modifications, or a -/// mix. +/// mergeSetIn - Merge the specified alias set into this alias set... /// -void AliasSet::updateAccessType() { - if (!Calls.empty() || !Invokes.empty()) { - AccessTy = ModRef; - } else if (!Loads.empty()) { - if (Stores.empty()) - AccessTy = Refs; - else - AccessTy = ModRef; - } else { - AccessTy = Mods; +void AliasSet::mergeSetIn(AliasSet &AS) { + assert(!AS.Forward && "Alias set is already forwarding!"); + assert(!Forward && "This set is a forwarding set!!"); + + // Update the alias and access types of this set... + AccessTy |= AS.AccessTy; + AliasTy |= AS.AliasTy; + + if (CallSites.empty()) { // Merge call sites... + if (!AS.CallSites.empty()) + std::swap(CallSites, AS.CallSites); + } else if (!AS.CallSites.empty()) { + CallSites.insert(CallSites.end(), AS.CallSites.begin(), AS.CallSites.end()); + AS.CallSites.clear(); } + + // FIXME: If AS's refcount is zero, nuke it now... + assert(RefCount != 0); + + AS.Forward = this; // Forward across AS now... + RefCount++; // AS is now pointing to us... + + // Merge the list of constituent pointers... + PtrListTail->second.setTail(AS.PtrListHead); + PtrListTail = AS.PtrListTail; + AS.PtrListHead = AS.PtrListTail = 0; } -/// mergeSetIn - Merge the specified alias set into this alias set... -/// -void AliasSet::mergeSetIn(const AliasSet &AS) { - // Merge instruction sets... - Loads.insert( Loads.end(), AS.Loads.begin() , AS.Loads.end()); - Stores.insert( Stores.end(), AS.Stores.begin() , AS.Stores.end()); - Calls.insert( Calls.end(), AS.Calls.begin() , AS.Calls.end()); - Invokes.insert(Invokes.end(), AS.Invokes.begin(), AS.Invokes.end()); +void AliasSetTracker::removeAliasSet(AliasSet *AS) { + AliasSets.erase(AS); +} - // Update the alias and access types of this set... - if (AS.getAliasType() == MayAlias) - AliasTy = MayAlias; - updateAccessType(); +void AliasSet::removeFromTracker(AliasSetTracker &AST) { + assert(RefCount == 0 && "Cannot remove non-dead alias set from tracker!"); + AST.removeAliasSet(this); } -/// pointerAliasesSet - Return true if the specified pointer "may" (or must) +void AliasSet::addPointer(AliasSetTracker &AST, HashNodePair &Entry, + unsigned Size) { + assert(!Entry.second.hasAliasSet() && "Entry already in set!"); + + AliasAnalysis &AA = AST.getAliasAnalysis(); + + if (isMustAlias()) // Check to see if we have to downgrade to _may_ alias + if (HashNodePair *P = getSomePointer()) { + AliasAnalysis::AliasResult Result = + AA.alias(P->first, P->second.getSize(), Entry.first, Size); + if (Result == AliasAnalysis::MayAlias) + AliasTy = MayAlias; + else // First entry of must alias must have maximum size! + P->second.updateSize(Size); + assert(Result != AliasAnalysis::NoAlias && "Cannot be part of must set!"); + } + + Entry.second.setAliasSet(this); + Entry.second.updateSize(Size); + + // Add it to the end of the list... + if (PtrListTail) + PtrListTail->second.setTail(&Entry); + else + PtrListHead = &Entry; + PtrListTail = &Entry; + RefCount++; // Entry points to alias set... +} + +void AliasSet::addCallSite(CallSite CS) { + CallSites.push_back(CS); + AliasTy = MayAlias; // FIXME: Too conservative? + AccessTy = ModRef; +} + +/// aliasesPointer - Return true if the specified pointer "may" (or must) /// alias one of the members in the set. /// -bool AliasSet::pointerAliasesSet(const Value *Ptr, AliasAnalysis &AA) const { - if (!Calls.empty() || !Invokes.empty()) - return true; - for (unsigned i = 0, e = Loads.size(); i != e; ++i) - if (AA.alias(Ptr, Loads[i]->getOperand(0))) - return true; - for (unsigned i = 0, e = Stores.size(); i != e; ++i) - if (AA.alias(Ptr, Stores[i]->getOperand(1))) +bool AliasSet::aliasesPointer(const Value *Ptr, unsigned Size, + AliasAnalysis &AA) const { + if (AliasTy == MustAlias) { + assert(CallSites.empty() && "Illegal must alias set!"); + + // If this is a set of MustAliases, only check to see if the pointer aliases + // SOME value in the set... + HashNodePair *SomePtr = getSomePointer(); + assert(SomePtr && "Empty must-alias set??"); + return AA.alias(SomePtr->first, SomePtr->second.getSize(), Ptr, Size); + } + + // If this is a may-alias set, we have to check all of the pointers in the set + // to be sure it doesn't alias the set... + for (iterator I = begin(), E = end(); I != E; ++I) + if (AA.alias(Ptr, Size, I->first, I->second.getSize())) return true; - return false; -} -/// getSomePointer - This method may only be called when the AliasType of the -/// set is MustAlias. This is used to return any old pointer (which must alias -/// all other pointers in the set) so that the caller can decide whether to turn -/// this set into a may alias set or not. -/// -Value *AliasSet::getSomePointer() const { - assert(getAliasType() == MustAlias && - "Cannot call getSomePointer on a 'MayAlias' set!"); - assert(Calls.empty() && Invokes.empty() && "Call/invokes mean may alias!"); + // Check the call sites list and invoke list... + if (!CallSites.empty()) + // FIXME: this is pessimistic! + return true; - if (!Loads.empty()) - return Loads[0]->getOperand(0); - assert(!Stores.empty() && "There are no instructions in this set!"); - return Stores[0]->getOperand(1); + return false; } +bool AliasSet::aliasesCallSite(CallSite CS, AliasAnalysis &AA) const { + // FIXME: Too conservative! + return true; +} /// findAliasSetForPointer - Given a pointer, find the one alias set to put the /// instruction referring to the pointer into. If there are multiple alias sets /// that may alias the pointer, merge them together and return the unified set. /// -AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr) { +AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr, + unsigned Size) { AliasSet *FoundSet = 0; - for (unsigned i = 0; i != AliasSets.size(); ++i) { - if (AliasSets[i].pointerAliasesSet(Ptr, AA)) { + for (iterator I = begin(), E = end(); I != E; ++I) + if (!I->Forward && I->aliasesPointer(Ptr, Size, AA)) { if (FoundSet == 0) { // If this is the first alias set ptr can go into... - FoundSet = &AliasSets[i]; // Remember it. + FoundSet = I; // Remember it. } else { // Otherwise, we must merge the sets... - FoundSet->mergeSetIn(AliasSets[i]); // Merge in contents... - AliasSets.erase(AliasSets.begin()+i); // Remove the set... - --i; // Don't skip the next set + FoundSet->mergeSetIn(*I); // Merge in contents... } } - } return FoundSet; } +AliasSet *AliasSetTracker::findAliasSetForCallSite(CallSite CS) { + AliasSet *FoundSet = 0; + for (iterator I = begin(), E = end(); I != E; ++I) + if (!I->Forward && I->aliasesCallSite(CS, AA)) { + if (FoundSet == 0) { // If this is the first alias set ptr can go into... + FoundSet = I; // Remember it. + } else if (!I->Forward) { // Otherwise, we must merge the sets... + FoundSet->mergeSetIn(*I); // Merge in contents... + } + } -void AliasSetTracker::add(LoadInst *LI) { - Value *Pointer = LI->getOperand(0); - - // Check to see if the loaded pointer aliases any sets... - AliasSet *AS = findAliasSetForPointer(Pointer); - if (AS) { - AS->Loads.push_back(LI); - // Check to see if we need to change this into a MayAlias set now... - if (AS->getAliasType() == AliasSet::MustAlias) - if (AA.alias(AS->getSomePointer(), Pointer) != AliasAnalysis::MustAlias) - AS->AliasTy = AliasSet::MayAlias; - AS->updateAccessType(); + return FoundSet; +} + + + + +/// getAliasSetForPointer - Return the alias set that the specified pointer +/// lives in... +AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, unsigned Size){ + AliasSet::HashNodePair &Entry = getEntryFor(Pointer); + + // Check to see if the pointer is already known... + if (Entry.second.hasAliasSet() && Size <= Entry.second.getSize()) { + // Return the set! + return *Entry.second.getAliasSet(*this)->getForwardedTarget(*this); + } else if (AliasSet *AS = findAliasSetForPointer(Pointer, Size)) { + // Add it to the alias set it aliases... + AS->addPointer(*this, Entry, Size); + return *AS; } else { - // Otherwise create a new alias set to hold the load... + // Otherwise create a new alias set to hold the loaded pointer... AliasSets.push_back(AliasSet()); - AliasSets.back().Loads.push_back(LI); - AliasSets.back().AccessTy = AliasSet::Refs; + AliasSets.back().addPointer(*this, Entry, Size); + return AliasSets.back(); } } +void AliasSetTracker::add(LoadInst *LI) { + addPointer(LI->getOperand(0), + AA.getTargetData().getTypeSize(LI->getType()), AliasSet::Refs); +} + void AliasSetTracker::add(StoreInst *SI) { - Value *Pointer = SI->getOperand(1); - - // Check to see if the loaded pointer aliases any sets... - AliasSet *AS = findAliasSetForPointer(Pointer); - if (AS) { - AS->Stores.push_back(SI); - // Check to see if we need to change this into a MayAlias set now... - if (AS->getAliasType() == AliasSet::MustAlias) - if (AA.alias(AS->getSomePointer(), Pointer) != AliasAnalysis::MustAlias) - AS->AliasTy = AliasSet::MayAlias; - AS->updateAccessType(); - } else { - // Otherwise create a new alias set to hold the load... + addPointer(SI->getOperand(1), + AA.getTargetData().getTypeSize(SI->getOperand(0)->getType()), + AliasSet::Mods); +} + +void AliasSetTracker::add(CallSite CS) { + AliasSet *AS = findAliasSetForCallSite(CS); + if (!AS) { AliasSets.push_back(AliasSet()); - AliasSets.back().Stores.push_back(SI); - AliasSets.back().AccessTy = AliasSet::Mods; + AS = &AliasSets.back(); } + AS->addCallSite(CS); } +void AliasSetTracker::add(Instruction *I) { + // Dispatch to one of the other add methods... + if (LoadInst *LI = dyn_cast(I)) + add(LI); + else if (StoreInst *SI = dyn_cast(I)) + add(SI); + else if (CallInst *CI = dyn_cast(I)) + add(CI); + else if (InvokeInst *II = dyn_cast(I)) + add(II); +} + +void AliasSetTracker::add(BasicBlock &BB) { + for (BasicBlock::iterator I = BB.begin(), E = BB.end(); I != E; ++I) + add(I); +} -void AliasSetTracker::mergeAllSets() { - if (AliasSets.size() < 2) return; // Noop +void AliasSetTracker::add(const AliasSetTracker &AST) { + assert(&AA == &AST.AA && + "Merging AliasSetTracker objects with different Alias Analyses!"); - // Merge all of the sets into set #0 - for (unsigned i = 1, e = AliasSets.size(); i != e; ++i) - AliasSets[0].mergeSetIn(AliasSets[i]); + // Loop over all of the alias sets in AST, adding the pointers contained + // therein into the current alias sets. This can cause alias sets to be + // merged together in the current AST. + for (const_iterator I = AST.begin(), E = AST.end(); I != E; ++I) + if (!I->Forward) { // Ignore forwarding alias sets + AliasSet &AS = const_cast(*I); - // Delete extraneous sets... - AliasSets.erase(AliasSets.begin()+1, AliasSets.end()); + // If there are any call sites in the alias set, add them to this AST. + for (unsigned i = 0, e = AS.CallSites.size(); i != e; ++i) + add(AS.CallSites[i]); + + // Loop over all of the pointers in this alias set... + AliasSet::iterator I = AS.begin(), E = AS.end(); + for (; I != E; ++I) + addPointer(I->first, I->second.getSize(), + (AliasSet::AccessType)AS.AccessTy); + } } -void AliasSetTracker::add(CallInst *CI) { - if (!AliasSets.empty()) { - mergeAllSets(); - } else { - AliasSets.push_back(AliasSet()); +//===----------------------------------------------------------------------===// +// AliasSet/AliasSetTracker Printing Support +//===----------------------------------------------------------------------===// + +void AliasSet::print(std::ostream &OS) const { + OS << " AliasSet[" << (void*)this << "," << RefCount << "] "; + OS << (AliasTy == MustAlias ? "must" : "may ") << " alias, "; + switch (AccessTy) { + case NoModRef: OS << "No access "; break; + case Refs : OS << "Ref "; break; + case Mods : OS << "Mod "; break; + case ModRef : OS << "Mod/Ref "; break; + default: assert(0 && "Bad value for AccessTy!"); } - AliasSets[0].AccessTy = AliasSet::ModRef; - AliasSets[0].AliasTy = AliasSet::MayAlias; - AliasSets[0].Calls.push_back(CI); -} + if (Forward) + OS << " forwarding to " << (void*)Forward; -void AliasSetTracker::add(InvokeInst *II) { - if (!AliasSets.empty()) { - mergeAllSets(); - } else { - AliasSets.push_back(AliasSet()); + + if (begin() != end()) { + OS << "Pointers: "; + for (iterator I = begin(), E = end(); I != E; ++I) { + if (I != begin()) OS << ", "; + WriteAsOperand(OS << "(", I->first); + OS << ", " << I->second.getSize() << ")"; + } + } + if (!CallSites.empty()) { + OS << "\n " << CallSites.size() << " Call Sites: "; + for (unsigned i = 0, e = CallSites.size(); i != e; ++i) { + if (i) OS << ", "; + WriteAsOperand(OS, CallSites[i].getCalledValue()); + } } - AliasSets[0].AccessTy = AliasSet::ModRef; - AliasSets[0].AliasTy = AliasSet::MayAlias; - AliasSets[0].Invokes.push_back(II); + OS << "\n"; +} + +void AliasSetTracker::print(std::ostream &OS) const { + OS << "Alias Set Tracker: " << AliasSets.size() << " alias sets for " + << PointerMap.size() << " pointer values.\n"; + for (const_iterator I = begin(), E = end(); I != E; ++I) + I->print(OS); + OS << "\n"; +} + +void AliasSet::dump() const { print (std::cerr); } +void AliasSetTracker::dump() const { print(std::cerr); } + + +//===----------------------------------------------------------------------===// +// AliasSetPrinter Pass +//===----------------------------------------------------------------------===// + +namespace { + class AliasSetPrinter : public FunctionPass { + AliasSetTracker *Tracker; + public: + virtual void getAnalysisUsage(AnalysisUsage &AU) const { + AU.setPreservesAll(); + AU.addRequired(); + } + + virtual bool runOnFunction(Function &F) { + Tracker = new AliasSetTracker(getAnalysis()); + + for (inst_iterator I = inst_begin(F), E = inst_end(F); I != E; ++I) + Tracker->add(*I); + return false; + } + + /// print - Convert to human readable form + virtual void print(std::ostream &OS) const { + Tracker->print(OS); + } + + virtual void releaseMemory() { + delete Tracker; + } + }; + RegisterPass X("print-alias-sets", "Alias Set Printer", + PassInfo::Analysis | PassInfo::Optimization); }