X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FAliasSetTracker.cpp;h=0397af7e979fce11be064f15f8cb82d6bc21f05a;hb=1a957d563fe894c797e0eba00bf069fbe7ecba77;hp=b351874e883fae05e200ae03b860a4c50fea0d2b;hpb=07bfa52405feb99155304c1a28b71e69d046589c;p=oota-llvm.git diff --git a/lib/Analysis/AliasSetTracker.cpp b/lib/Analysis/AliasSetTracker.cpp index b351874e883..0397af7e979 100644 --- a/lib/Analysis/AliasSetTracker.cpp +++ b/lib/Analysis/AliasSetTracker.cpp @@ -1,29 +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/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!!"); @@ -31,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); @@ -38,7 +54,7 @@ void AliasSet::mergeSetIn(AliasSet &AS) { CallSites.insert(CallSites.end(), AS.CallSites.begin(), AS.CallSites.end()); AS.CallSites.clear(); } - + AS.Forward = this; // Forward across AS now... addRef(); // AS is now pointing to us... @@ -99,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; @@ -179,10 +196,10 @@ 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. } } @@ -205,10 +222,10 @@ 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. } } @@ -272,6 +289,9 @@ 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; } @@ -331,25 +351,40 @@ 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) { @@ -416,6 +451,17 @@ void AliasSetTracker::deleteValue(Value *PtrVal) { // 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 @@ -487,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"; } @@ -500,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(); @@ -521,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"); }