X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FAliasSetTracker.cpp;h=0397af7e979fce11be064f15f8cb82d6bc21f05a;hb=e79bad66e0b265cdac2dc90e5e6727a5fa2cbcae;hp=efb3184bd536b9621cb2b38f5179163d65eb9876;hpb=b8a31ace2c49af703cf7b1f1bda408a361f53447;p=oota-llvm.git diff --git a/lib/Analysis/AliasSetTracker.cpp b/lib/Analysis/AliasSetTracker.cpp index efb3184bd53..0397af7e979 100644 --- a/lib/Analysis/AliasSetTracker.cpp +++ b/lib/Analysis/AliasSetTracker.cpp @@ -1,31 +1,31 @@ //===- AliasSetTracker.cpp - Alias Sets Tracker implementation-------------===// -// +// // The LLVM Compiler Infrastructure // // This file was developed by the LLVM research group and is distributed under // the University of Illinois Open Source License. See LICENSE.TXT for details. -// +// //===----------------------------------------------------------------------===// // // This file implements the AliasSetTracker and AliasSet classes. -// +// //===----------------------------------------------------------------------===// #include "llvm/Analysis/AliasSetTracker.h" #include "llvm/Analysis/AliasAnalysis.h" -#include "llvm/iMemory.h" -#include "llvm/iOther.h" -#include "llvm/iTerminators.h" +#include "llvm/Instructions.h" #include "llvm/Pass.h" +#include "llvm/Type.h" #include "llvm/Target/TargetData.h" #include "llvm/Assembly/Writer.h" +#include "llvm/Support/Compiler.h" #include "llvm/Support/InstIterator.h" -#include +#include "llvm/Support/Streams.h" using namespace llvm; -/// mergeSetIn - Merge the specified alias set into this alias set... +/// mergeSetIn - Merge the specified alias set into this alias set. /// -void AliasSet::mergeSetIn(AliasSet &AS) { +void AliasSet::mergeSetIn(AliasSet &AS, AliasSetTracker &AST) { assert(!AS.Forward && "Alias set is already forwarding!"); assert(!Forward && "This set is a forwarding set!!"); @@ -33,6 +33,20 @@ void AliasSet::mergeSetIn(AliasSet &AS) { AccessTy |= AS.AccessTy; AliasTy |= AS.AliasTy; + if (AliasTy == MustAlias) { + // Check that these two merged sets really are must aliases. Since both + // used to be must-alias sets, we can just check any pointer from each set + // for aliasing. + AliasAnalysis &AA = AST.getAliasAnalysis(); + HashNodePair *L = getSomePointer(); + HashNodePair *R = AS.getSomePointer(); + + // If the pointers are not a must-alias pair, this set becomes a may alias. + if (AA.alias(L->first, L->second.getSize(), R->first, R->second.getSize()) + != AliasAnalysis::MustAlias) + AliasTy = MayAlias; + } + if (CallSites.empty()) { // Merge call sites... if (!AS.CallSites.empty()) std::swap(CallSites, AS.CallSites); @@ -40,9 +54,6 @@ void AliasSet::mergeSetIn(AliasSet &AS) { 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... addRef(); // AS is now pointing to us... @@ -55,6 +66,7 @@ void AliasSet::mergeSetIn(AliasSet &AS) { AS.PtrList = 0; AS.PtrListEnd = &AS.PtrList; + assert(*AS.PtrListEnd == 0 && "End of list is not null?"); } } @@ -72,13 +84,13 @@ void AliasSet::removeFromTracker(AliasSetTracker &AST) { } void AliasSet::addPointer(AliasSetTracker &AST, HashNodePair &Entry, - unsigned Size) { + unsigned Size, bool KnownMustAlias) { 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 + // Check to see if we have to downgrade to _may_ alias. + if (isMustAlias() && !KnownMustAlias) if (HashNodePair *P = getSomePointer()) { + AliasAnalysis &AA = AST.getAliasAnalysis(); AliasAnalysis::AliasResult Result = AA.alias(P->first, P->second.getSize(), Entry.first, Size); if (Result == AliasAnalysis::MayAlias) @@ -95,6 +107,7 @@ void AliasSet::addPointer(AliasSetTracker &AST, HashNodePair &Entry, assert(*PtrListEnd == 0 && "End of list is not null?"); *PtrListEnd = &Entry; PtrListEnd = Entry.second.setPrevInList(PtrListEnd); + assert(*PtrListEnd == 0 && "End of list is not null?"); addRef(); // Entry points to alias set... } @@ -102,9 +115,10 @@ void AliasSet::addCallSite(CallSite CS, AliasAnalysis &AA) { CallSites.push_back(CS); if (Function *F = CS.getCalledFunction()) { - if (AA.doesNotAccessMemory(F)) + AliasAnalysis::ModRefBehavior Behavior = AA.getModRefBehavior(F, CS); + if (Behavior == AliasAnalysis::DoesNotAccessMemory) return; - else if (AA.onlyReadsMemory(F)) { + else if (Behavior == AliasAnalysis::OnlyReadsMemory) { AliasTy = MayAlias; AccessTy |= Refs; return; @@ -138,20 +152,38 @@ bool AliasSet::aliasesPointer(const Value *Ptr, unsigned Size, return true; // Check the call sites list and invoke list... - if (!CallSites.empty()) - // FIXME: this is pessimistic! - return true; + if (!CallSites.empty()) { + if (AA.hasNoModRefInfoForCalls()) + return true; + + for (unsigned i = 0, e = CallSites.size(); i != e; ++i) + if (AA.getModRefInfo(CallSites[i], const_cast(Ptr), Size) + != AliasAnalysis::NoModRef) + return true; + } return false; } bool AliasSet::aliasesCallSite(CallSite CS, AliasAnalysis &AA) const { - // FIXME: Use mod/ref information to prune this better! if (Function *F = CS.getCalledFunction()) if (AA.doesNotAccessMemory(F)) return false; - return true; + if (AA.hasNoModRefInfoForCalls()) + return true; + + for (unsigned i = 0, e = CallSites.size(); i != e; ++i) + if (AA.getModRefInfo(CallSites[i], CS) != AliasAnalysis::NoModRef || + AA.getModRefInfo(CS, CallSites[i]) != AliasAnalysis::NoModRef) + return true; + + for (iterator I = begin(), E = end(); I != E; ++I) + if (AA.getModRefInfo(CS, I.getPointer(), I.getSize()) != + AliasAnalysis::NoModRef) + return true; + + return false; } @@ -164,24 +196,36 @@ AliasSet *AliasSetTracker::findAliasSetForPointer(const Value *Ptr, AliasSet *FoundSet = 0; 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... + if (FoundSet == 0) { // If this is the first alias set ptr can go into. FoundSet = I; // Remember it. - } else { // Otherwise, we must merge the sets... - FoundSet->mergeSetIn(*I); // Merge in contents... + } else { // Otherwise, we must merge the sets. + FoundSet->mergeSetIn(*I, *this); // Merge in contents. } } return FoundSet; } +/// containsPointer - Return true if the specified location is represented by +/// this alias set, false otherwise. This does not modify the AST object or +/// alias sets. +bool AliasSetTracker::containsPointer(Value *Ptr, unsigned Size) const { + for (const_iterator I = begin(), E = end(); I != E; ++I) + if (!I->Forward && I->aliasesPointer(Ptr, Size, AA)) + return true; + return false; +} + + + 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... + 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... + } else if (!I->Forward) { // Otherwise, we must merge the sets. + FoundSet->mergeSetIn(*I, *this); // Merge in contents. } } @@ -198,7 +242,8 @@ 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()) { + if (Entry.second.hasAliasSet()) { + Entry.second.updateSize(Size); // Return the set! return *Entry.second.getAliasSet(*this)->getForwardedTarget(*this); } else if (AliasSet *AS = findAliasSetForPointer(Pointer, Size)) { @@ -214,6 +259,13 @@ AliasSet &AliasSetTracker::getAliasSetForPointer(Value *Pointer, unsigned Size, } } +bool AliasSetTracker::add(Value *Ptr, unsigned Size) { + bool NewPtr; + addPointer(Ptr, Size, AliasSet::NoModRef, NewPtr); + return NewPtr; +} + + bool AliasSetTracker::add(LoadInst *LI) { bool NewPtr; AliasSet &AS = addPointer(LI->getOperand(0), @@ -233,9 +285,18 @@ bool AliasSetTracker::add(StoreInst *SI) { return NewPtr; } +bool AliasSetTracker::add(FreeInst *FI) { + bool NewPtr; + AliasSet &AS = addPointer(FI->getOperand(0), ~0, + AliasSet::Mods, NewPtr); + + // Free operations are volatile ops (cannot be moved). + AS.setVolatile(); + return NewPtr; +} + bool AliasSetTracker::add(CallSite CS) { - bool NewPtr; if (Function *F = CS.getCalledFunction()) if (AA.doesNotAccessMemory(F)) return true; // doesn't alias anything @@ -262,6 +323,8 @@ bool AliasSetTracker::add(Instruction *I) { return add(CI); else if (InvokeInst *II = dyn_cast(I)) return add(II); + else if (FreeInst *FI = dyn_cast(I)) + return add(FI); return true; } @@ -288,27 +351,48 @@ void AliasSetTracker::add(const AliasSetTracker &AST) { // Loop over all of the pointers in this alias set... AliasSet::iterator I = AS.begin(), E = AS.end(); bool X; - for (; I != E; ++I) - addPointer(I.getPointer(), I.getSize(), - (AliasSet::AccessType)AS.AccessTy, X); + for (; I != E; ++I) { + AliasSet &NewAS = addPointer(I.getPointer(), I.getSize(), + (AliasSet::AccessType)AS.AccessTy, X); + if (AS.isVolatile()) NewAS.setVolatile(); + } } } /// remove - Remove the specified (potentially non-empty) alias set from the /// tracker. void AliasSetTracker::remove(AliasSet &AS) { - bool SetDead; - do { - AliasSet::iterator I = AS.begin(); - Value *Ptr = I.getPointer(); ++I; - - // deleteValue will delete the set automatically when the last pointer - // reference is destroyed. "Predict" when this will happen. - SetDead = I == AS.end(); - deleteValue(Ptr); // Delete all of the pointers from the set - } while (!SetDead); + // Drop all call sites. + AS.CallSites.clear(); + + // Clear the alias set. + unsigned NumRefs = 0; + while (!AS.empty()) { + AliasSet::HashNodePair *P = AS.PtrList; + + // Unlink from the list of values. + P->second.removeFromList(); + + // Remember how many references need to be dropped. + ++NumRefs; + + // Finally, remove the entry. + Value *Remove = P->first; // Take a copy because it is invalid to pass + PointerMap.erase(Remove); // a reference to the data being erased. + } + + // Stop using the alias set, removing it. + AS.RefCount -= NumRefs; + if (AS.RefCount == 0) + AS.removeFromTracker(*this); } +bool AliasSetTracker::remove(Value *Ptr, unsigned Size) { + AliasSet *AS = findAliasSetForPointer(Ptr, Size); + if (!AS) return false; + remove(*AS); + return true; +} bool AliasSetTracker::remove(LoadInst *LI) { unsigned Size = AA.getTargetData().getTypeSize(LI->getType()); @@ -326,6 +410,13 @@ bool AliasSetTracker::remove(StoreInst *SI) { return true; } +bool AliasSetTracker::remove(FreeInst *FI) { + AliasSet *AS = findAliasSetForPointer(FI->getOperand(0), ~0); + if (!AS) return false; + remove(*AS); + return true; +} + bool AliasSetTracker::remove(CallSite CS) { if (Function *F = CS.getCalledFunction()) if (AA.doesNotAccessMemory(F)) @@ -345,8 +436,8 @@ bool AliasSetTracker::remove(Instruction *I) { return remove(SI); else if (CallInst *CI = dyn_cast(I)) return remove(CI); - else if (InvokeInst *II = dyn_cast(I)) - return remove(II); + else if (FreeInst *FI = dyn_cast(I)) + return remove(FI); return true; } @@ -357,7 +448,21 @@ bool AliasSetTracker::remove(Instruction *I) { // dangling pointers to deleted instructions. // void AliasSetTracker::deleteValue(Value *PtrVal) { - // First, look up the PointerRec for this pointer... + // Notify the alias analysis implementation that this value is gone. + AA.deleteValue(PtrVal); + + // If this is a call instruction, remove the callsite from the appropriate + // AliasSet. + CallSite CS = CallSite::get(PtrVal); + if (CS.getInstruction()) { + Function *F = CS.getCalledFunction(); + if (!F || !AA.doesNotAccessMemory(F)) { + if (AliasSet *AS = findAliasSetForCallSite(CS)) + AS->removeCallSite(CS); + } + } + + // First, look up the PointerRec for this pointer. hash_map::iterator I = PointerMap.find(PtrVal); if (I == PointerMap.end()) return; // Noop @@ -372,6 +477,29 @@ void AliasSetTracker::deleteValue(Value *PtrVal) { PointerMap.erase(I); } +// copyValue - This method should be used whenever a preexisting value in the +// program is copied or cloned, introducing a new value. Note that it is ok for +// clients that use this method to introduce the same value multiple times: if +// the tracker already knows about a value, it will ignore the request. +// +void AliasSetTracker::copyValue(Value *From, Value *To) { + // Notify the alias analysis implementation that this value is copied. + AA.copyValue(From, To); + + // First, look up the PointerRec for this pointer. + hash_map::iterator I = PointerMap.find(From); + if (I == PointerMap.end() || !I->second.hasAliasSet()) + return; // Noop + + AliasSet::HashNodePair &Entry = getEntryFor(To); + if (Entry.second.hasAliasSet()) return; // Already in the tracker! + + // Add it to the alias set it aliases... + AliasSet *AS = I->second.getAliasSet(*this); + AS->addPointer(*this, Entry, I->second.getSize(), true); +} + + //===----------------------------------------------------------------------===// // AliasSet/AliasSetTracker Printing Support @@ -405,7 +533,7 @@ void AliasSet::print(std::ostream &OS) const { for (unsigned i = 0, e = CallSites.size(); i != e; ++i) { if (i) OS << ", "; WriteAsOperand(OS, CallSites[i].getCalledValue()); - } + } } OS << "\n"; } @@ -418,17 +546,20 @@ void AliasSetTracker::print(std::ostream &OS) const { OS << "\n"; } -void AliasSet::dump() const { print (std::cerr); } -void AliasSetTracker::dump() const { print(std::cerr); } +void AliasSet::dump() const { print (cerr); } +void AliasSetTracker::dump() const { print(cerr); } //===----------------------------------------------------------------------===// // AliasSetPrinter Pass //===----------------------------------------------------------------------===// namespace { - class AliasSetPrinter : public FunctionPass { + class VISIBILITY_HIDDEN AliasSetPrinter : public FunctionPass { AliasSetTracker *Tracker; public: + static char ID; // Pass identification, replacement for typeid + AliasSetPrinter() : FunctionPass((intptr_t)&ID) {} + virtual void getAnalysisUsage(AnalysisUsage &AU) const { AU.setPreservesAll(); AU.addRequired(); @@ -439,18 +570,11 @@ namespace { 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() { + Tracker->print(cerr); delete Tracker; + return false; } }; - RegisterPass X("print-alias-sets", "Alias Set Printer", - PassInfo::Analysis | PassInfo::Optimization); + char AliasSetPrinter::ID = 0; + RegisterPass X("print-alias-sets", "Alias Set Printer"); }