X-Git-Url: http://demsky.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FMemoryDependenceAnalysis.cpp;h=2012ab473c98a697650a37a94129bc67a0c1f347;hb=ebb5a971d903aa4479bb2a21472597319a9b0086;hp=eea0615ce31bfa6105e23d7c6e06106c1419bf7e;hpb=4ee451de366474b9c228b4e5fa573795a715216d;p=oota-llvm.git diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp index eea0615ce31..2012ab473c9 100644 --- a/lib/Analysis/MemoryDependenceAnalysis.cpp +++ b/lib/Analysis/MemoryDependenceAnalysis.cpp @@ -20,6 +20,7 @@ #include "llvm/Function.h" #include "llvm/Analysis/AliasAnalysis.h" #include "llvm/Support/CFG.h" +#include "llvm/Support/CommandLine.h" #include "llvm/Target/TargetData.h" #include "llvm/ADT/Statistic.h" @@ -27,6 +28,13 @@ using namespace llvm; +// Control the calculation of non-local dependencies by only examining the +// predecessors if the basic block has less than X amount (50 by default). +static cl::opt +PredLimit("nonlocaldep-threshold", cl::Hidden, cl::init(50), + cl::desc("Control the calculation of non-local" + "dependencies (default = 50)")); + STATISTIC(NumCacheNonlocal, "Number of cached non-local responses"); STATISTIC(NumUncacheNonlocal, "Number of uncached non-local responses"); @@ -38,7 +46,7 @@ Instruction* const MemoryDependenceAnalysis::Dirty = (Instruction*)-5; // Register this pass... static RegisterPass X("memdep", - "Memory Dependence Analysis"); + "Memory Dependence Analysis", false, true); void MemoryDependenceAnalysis::ping(Instruction *D) { for (depMapType::iterator I = depGraphLocal.begin(), E = depGraphLocal.end(); @@ -50,6 +58,9 @@ void MemoryDependenceAnalysis::ping(Instruction *D) { for (nonLocalDepMapType::iterator I = depGraphNonLocal.begin(), E = depGraphNonLocal.end(); I != E; ++I) { assert(I->first != D); + for (DenseMap::iterator II = I->second.begin(), + EE = I->second.end(); II != EE; ++II) + assert(II->second != D); } for (reverseDepMapType::iterator I = reverseDep.begin(), E = reverseDep.end(); @@ -89,11 +100,11 @@ Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, // If the starting point was specifiy, use it if (start) { QI = start; - blockBegin = start->getParent()->end(); + blockBegin = start->getParent()->begin(); // If the starting point wasn't specified, but the block was, use it } else if (!start && block) { QI = block->end(); - blockBegin = block->end(); + blockBegin = block->begin(); } // Walk backwards through the block, looking for dependencies @@ -121,11 +132,10 @@ Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, // FreeInsts erase the entire structure pointerSize = ~0UL; - } else if (isa(QI)) { + } else if (CallSite::get(QI).getInstruction() != 0) { AliasAnalysis::ModRefBehavior result = AA.getModRefBehavior(CallSite::get(QI)); - if (result != AliasAnalysis::DoesNotAccessMemory && - result != AliasAnalysis::OnlyReadsMemory) { + if (result != AliasAnalysis::DoesNotAccessMemory) { if (!start && !block) { cachedResult.first = QI; cachedResult.second = true; @@ -171,7 +181,9 @@ void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query, // Current stack of the DFS SmallVector stack; - stack.push_back(block); + for (pred_iterator PI = pred_begin(block), PE = pred_end(block); + PI != PE; ++PI) + stack.push_back(*PI); // Do a basic DFS while (!stack.empty()) { @@ -198,7 +210,7 @@ void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query, // If we re-encounter the starting block, we still need to search it // because there might be a dependency in the starting block AFTER // the position of the query. This is necessary to get loops right. - } else if (BB == block && stack.size() > 1) { + } else if (BB == block) { visited.insert(BB); Instruction* localDep = getDependency(query, 0, BB); @@ -211,15 +223,18 @@ void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query, } // If we didn't find anything, recurse on the precessors of this block + // Only do this for blocks with a small number of predecessors. bool predOnStack = false; bool inserted = false; - for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); - PI != PE; ++PI) - if (!visited.count(*PI)) { - stack.push_back(*PI); - inserted = true; - } else - predOnStack = true; + if (std::distance(pred_begin(BB), pred_end(BB)) <= PredLimit) { + for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); + PI != PE; ++PI) + if (!visited.count(*PI)) { + stack.push_back(*PI); + inserted = true; + } else + predOnStack = true; + } // If we inserted a new predecessor, then we'll come back to this block if (inserted) @@ -267,6 +282,11 @@ void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query, resp = cached; + // Update the reverse non-local dependency cache + for (DenseMap::iterator I = resp.begin(), E = resp.end(); + I != E; ++I) + reverseDepNonLocal[I->second].insert(query); + return; } else NumUncacheNonlocal++; @@ -283,7 +303,7 @@ void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query, } /// getDependency - Return the instruction on which a memory operation -/// depends. The local paramter indicates if the query should only +/// depends. The local parameter indicates if the query should only /// evaluate dependencies within the same basic block. Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query, Instruction* start, @@ -444,6 +464,46 @@ Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query, return NonLocal; } +/// dropInstruction - Remove an instruction from the analysis, making +/// absolutely conservative assumptions when updating the cache. This is +/// useful, for example when an instruction is changed rather than removed. +void MemoryDependenceAnalysis::dropInstruction(Instruction* drop) { + depMapType::iterator depGraphEntry = depGraphLocal.find(drop); + if (depGraphEntry != depGraphLocal.end()) + reverseDep[depGraphEntry->second.first].erase(drop); + + // Drop dependency information for things that depended on this instr + SmallPtrSet& set = reverseDep[drop]; + for (SmallPtrSet::iterator I = set.begin(), E = set.end(); + I != E; ++I) + depGraphLocal.erase(*I); + + depGraphLocal.erase(drop); + reverseDep.erase(drop); + + for (DenseMap::iterator DI = + depGraphNonLocal[drop].begin(), DE = depGraphNonLocal[drop].end(); + DI != DE; ++DI) + if (DI->second != None) + reverseDepNonLocal[DI->second].erase(drop); + + if (reverseDepNonLocal.count(drop)) { + SmallPtrSet& set = reverseDepNonLocal[drop]; + for (SmallPtrSet::iterator I = set.begin(), E = set.end(); + I != E; ++I) + for (DenseMap::iterator DI = + depGraphNonLocal[*I].begin(), DE = depGraphNonLocal[*I].end(); + DI != DE; ++DI) + if (DI->second == drop) + DI->second = Dirty; + } + + reverseDepNonLocal.erase(drop); + nonLocalDepMapType::iterator I = depGraphNonLocal.find(drop); + if (I != depGraphNonLocal.end()) + depGraphNonLocal.erase(I); +} + /// removeInstruction - Remove an instruction from the dependence analysis, /// updating the dependence of instructions that previously depended on it. /// This method attempts to keep the cache coherent using the reverse map. @@ -451,8 +511,6 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) { // Figure out the new dep for things that currently depend on rem Instruction* newDep = NonLocal; - reverseDep[depGraphLocal[rem].first].erase(rem); - for (DenseMap::iterator DI = depGraphNonLocal[rem].begin(), DE = depGraphNonLocal[rem].end(); DI != DE; ++DI) @@ -462,16 +520,20 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) { depMapType::iterator depGraphEntry = depGraphLocal.find(rem); if (depGraphEntry != depGraphLocal.end()) { + reverseDep[depGraphEntry->second.first].erase(rem); + if (depGraphEntry->second.first != NonLocal && + depGraphEntry->second.first != None && depGraphEntry->second.second) { // If we have dep info for rem, set them to it BasicBlock::iterator RI = depGraphEntry->second.first; RI++; newDep = RI; - } else if (depGraphEntry->second.first == NonLocal && + } else if ( (depGraphEntry->second.first == NonLocal || + depGraphEntry->second.first == None ) && depGraphEntry->second.second ) { // If we have a confirmed non-local flag, use it - newDep = NonLocal; + newDep = depGraphEntry->second.first; } else { // Otherwise, use the immediate successor of rem // NOTE: This is because, when getDependence is called, it will first @@ -480,14 +542,22 @@ void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) { RI++; newDep = RI; } - - SmallPtrSet& set = reverseDep[rem]; - for (SmallPtrSet::iterator I = set.begin(), E = set.end(); - I != E; ++I) { - // Insert the new dependencies - // Mark it as unconfirmed as long as it is not the non-local flag - depGraphLocal[*I] = std::make_pair(newDep, !newDep); - } + } else { + // Otherwise, use the immediate successor of rem + // NOTE: This is because, when getDependence is called, it will first + // check the immediate predecessor of what is in the cache. + BasicBlock::iterator RI = rem; + RI++; + newDep = RI; + } + + SmallPtrSet& set = reverseDep[rem]; + for (SmallPtrSet::iterator I = set.begin(), E = set.end(); + I != E; ++I) { + // Insert the new dependencies + // Mark it as unconfirmed as long as it is not the non-local flag + depGraphLocal[*I] = std::make_pair(newDep, (newDep == NonLocal || + newDep == None)); } depGraphLocal.erase(rem);