#include "llvm/Function.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/ADT/Statistic.h"
-#include "llvm/Support/CFG.h"
+#include "llvm/Support/PredIteratorCache.h"
#include "llvm/Support/Debug.h"
#include "llvm/Target/TargetData.h"
using namespace llvm;
"Number of cached, but dirty, non-local ptr responses");
STATISTIC(NumUncacheNonLocalPtr,
"Number of uncached non-local ptr responses");
+STATISTIC(NumCacheCompleteNonLocalPtr,
+ "Number of block queries that were completely cached");
char MemoryDependenceAnalysis::ID = 0;
static RegisterPass<MemoryDependenceAnalysis> X("memdep",
"Memory Dependence Analysis", false, true);
+MemoryDependenceAnalysis::MemoryDependenceAnalysis()
+: FunctionPass(&ID), PredCache(0) {
+}
+MemoryDependenceAnalysis::~MemoryDependenceAnalysis() {
+}
+
+/// Clean up memory in between runs
+void MemoryDependenceAnalysis::releaseMemory() {
+ LocalDeps.clear();
+ NonLocalDeps.clear();
+ NonLocalPointerDeps.clear();
+ ReverseLocalDeps.clear();
+ ReverseNonLocalDeps.clear();
+ ReverseNonLocalPtrDeps.clear();
+ PredCache->clear();
+}
+
+
+
/// getAnalysisUsage - Does not modify anything. It uses Alias Analysis.
///
void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
bool MemoryDependenceAnalysis::runOnFunction(Function &) {
AA = &getAnalysis<AliasAnalysis>();
TD = &getAnalysis<TargetData>();
+ if (PredCache == 0)
+ PredCache.reset(new PredIteratorCache());
return false;
}
+/// RemoveFromReverseMap - This is a helper function that removes Val from
+/// 'Inst's set in ReverseMap. If the set becomes empty, remove Inst's entry.
+template <typename KeyTy>
+static void RemoveFromReverseMap(DenseMap<Instruction*,
+ SmallPtrSet<KeyTy*, 4> > &ReverseMap,
+ Instruction *Inst, KeyTy *Val) {
+ typename DenseMap<Instruction*, SmallPtrSet<KeyTy*, 4> >::iterator
+ InstIt = ReverseMap.find(Inst);
+ assert(InstIt != ReverseMap.end() && "Reverse map out of sync?");
+ bool Found = InstIt->second.erase(Val);
+ assert(Found && "Invalid reverse map!"); Found=Found;
+ if (InstIt->second.empty())
+ ReverseMap.erase(InstIt);
+}
+
/// getCallSiteDependencyFrom - Private helper for finding the local
/// dependencies of a call site.
if (Instruction *Inst = LocalCache.getInst()) {
ScanPos = Inst;
- SmallPtrSet<Instruction*, 4> &InstMap = ReverseLocalDeps[Inst];
- bool Found = InstMap.erase(QueryInst);
- assert(Found && "Invalid reverse map!"); Found=Found;
- if (InstMap.empty())
- // FIXME: use an iterator to avoid looking up inst again.
- ReverseLocalDeps.erase(Inst);
+ RemoveFromReverseMap(ReverseLocalDeps, Inst, QueryInst);
}
BasicBlock *QueryParent = QueryInst->getParent();
} else {
// Seed DirtyBlocks with each of the preds of QueryInst's block.
BasicBlock *QueryBB = QueryInst->getParent();
- DirtyBlocks.append(pred_begin(QueryBB), pred_end(QueryBB));
+ for (BasicBlock **PI = PredCache->GetPreds(QueryBB); *PI; ++PI)
+ DirtyBlocks.push_back(*PI);
NumUncacheNonLocal++;
}
if (ExistingResult) {
if (Instruction *Inst = ExistingResult->getInst()) {
ScanPos = Inst;
-
// We're removing QueryInst's use of Inst.
- SmallPtrSet<Instruction*, 4> &InstMap = ReverseNonLocalDeps[Inst];
- bool Found = InstMap.erase(QueryInst);
- assert(Found && "Invalid reverse map!"); Found=Found;
- // FIXME: Use an iterator to avoid looking up inst again.
- if (InstMap.empty()) ReverseNonLocalDeps.erase(Inst);
+ RemoveFromReverseMap(ReverseNonLocalDeps, Inst, QueryInst);
}
}
// If the block *is* completely transparent to the load, we need to check
// the predecessors of this block. Add them to our worklist.
- DirtyBlocks.append(pred_begin(DirtyBB), pred_end(DirtyBB));
+ for (BasicBlock **PI = PredCache->GetPreds(DirtyBB); *PI; ++PI)
+ DirtyBlocks.push_back(*PI);
}
}
void MemoryDependenceAnalysis::
getNonLocalPointerDependency(Value *Pointer, bool isLoad, BasicBlock *FromBB,
SmallVectorImpl<NonLocalDepEntry> &Result) {
+ assert(isa<PointerType>(Pointer->getType()) &&
+ "Can't get pointer deps of a non-pointer!");
Result.clear();
// We know that the pointer value is live into FromBB find the def/clobbers
// While we have blocks to analyze, get their values.
SmallPtrSet<BasicBlock*, 64> Visited;
-
- for (pred_iterator PI = pred_begin(FromBB), E = pred_end(FromBB); PI != E;
- ++PI) {
- // TODO: PHI TRANSLATE.
- getNonLocalPointerDepInternal(Pointer, PointeeSize, isLoad, *PI,
- Result, Visited);
+ getNonLocalPointerDepFromBB(Pointer, PointeeSize, isLoad, FromBB,
+ Result, Visited);
+}
+
+/// GetNonLocalInfoForBlock - Compute the memdep value for BB with
+/// Pointer/PointeeSize using either cached information in Cache or by doing a
+/// lookup (which may use dirty cache info if available). If we do a lookup,
+/// add the result to the cache.
+MemDepResult MemoryDependenceAnalysis::
+GetNonLocalInfoForBlock(Value *Pointer, uint64_t PointeeSize,
+ bool isLoad, BasicBlock *BB,
+ NonLocalDepInfo *Cache, unsigned NumSortedEntries) {
+
+ // Do a binary search to see if we already have an entry for this block in
+ // the cache set. If so, find it.
+ NonLocalDepInfo::iterator Entry =
+ std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries,
+ std::make_pair(BB, MemDepResult()));
+ if (Entry != Cache->begin() && (&*Entry)[-1].first == BB)
+ --Entry;
+
+ MemDepResult *ExistingResult = 0;
+ if (Entry != Cache->begin()+NumSortedEntries && Entry->first == BB)
+ ExistingResult = &Entry->second;
+
+ // If we have a cached entry, and it is non-dirty, use it as the value for
+ // this dependency.
+ if (ExistingResult && !ExistingResult->isDirty()) {
+ ++NumCacheNonLocalPtr;
+ return *ExistingResult;
+ }
+
+ // Otherwise, we have to scan for the value. If we have a dirty cache
+ // entry, start scanning from its position, otherwise we scan from the end
+ // of the block.
+ BasicBlock::iterator ScanPos = BB->end();
+ if (ExistingResult && ExistingResult->getInst()) {
+ assert(ExistingResult->getInst()->getParent() == BB &&
+ "Instruction invalidated?");
+ ++NumCacheDirtyNonLocalPtr;
+ ScanPos = ExistingResult->getInst();
+
+ // Eliminating the dirty entry from 'Cache', so update the reverse info.
+ ValueIsLoadPair CacheKey(Pointer, isLoad);
+ RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos,
+ CacheKey.getOpaqueValue());
+ } else {
+ ++NumUncacheNonLocalPtr;
}
+
+ // Scan the block for the dependency.
+ MemDepResult Dep = getPointerDependencyFrom(Pointer, PointeeSize, isLoad,
+ ScanPos, BB);
+
+ // If we had a dirty entry for the block, update it. Otherwise, just add
+ // a new entry.
+ if (ExistingResult)
+ *ExistingResult = Dep;
+ else
+ Cache->push_back(std::make_pair(BB, Dep));
+
+ // If the block has a dependency (i.e. it isn't completely transparent to
+ // the value), remember the reverse association because we just added it
+ // to Cache!
+ if (Dep.isNonLocal())
+ return Dep;
+
+ // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
+ // update MemDep when we remove instructions.
+ Instruction *Inst = Dep.getInst();
+ assert(Inst && "Didn't depend on anything?");
+ ValueIsLoadPair CacheKey(Pointer, isLoad);
+ ReverseNonLocalPtrDeps[Inst].insert(CacheKey.getOpaqueValue());
+ return Dep;
}
+
+/// getNonLocalPointerDepFromBB -
void MemoryDependenceAnalysis::
-getNonLocalPointerDepInternal(Value *Pointer, uint64_t PointeeSize,
- bool isLoad, BasicBlock *StartBB,
- SmallVectorImpl<NonLocalDepEntry> &Result,
- SmallPtrSet<BasicBlock*, 64> &Visited) {
- SmallVector<BasicBlock*, 32> Worklist;
- Worklist.push_back(StartBB);
-
+getNonLocalPointerDepFromBB(Value *Pointer, uint64_t PointeeSize,
+ bool isLoad, BasicBlock *StartBB,
+ SmallVectorImpl<NonLocalDepEntry> &Result,
+ SmallPtrSet<BasicBlock*, 64> &Visited) {
// Look up the cached info for Pointer.
ValueIsLoadPair CacheKey(Pointer, isLoad);
- NonLocalDepInfo *Cache = &NonLocalPointerDeps[CacheKey];
+
+ std::pair<BasicBlock*, NonLocalDepInfo> &CacheInfo =
+ NonLocalPointerDeps[CacheKey];
+ NonLocalDepInfo *Cache = &CacheInfo.second;
+
+ // If we have valid cached information for exactly the block we are
+ // investigating, just return it with no recomputation.
+ if (CacheInfo.first == StartBB) {
+ for (NonLocalDepInfo::iterator I = Cache->begin(), E = Cache->end();
+ I != E; ++I)
+ if (!I->second.isNonLocal())
+ Result.push_back(*I);
+ ++NumCacheCompleteNonLocalPtr;
+ return;
+ }
+
+ // Otherwise, either this is a new block, a block with an invalid cache
+ // pointer or one that we're about to invalidate by putting more info into it
+ // than its valid cache info. If empty, the result will be valid cache info,
+ // otherwise it isn't.
+ CacheInfo.first = Cache->empty() ? StartBB : 0;
+
+ SmallVector<BasicBlock*, 32> Worklist;
+ Worklist.push_back(StartBB);
// Keep track of the entries that we know are sorted. Previously cached
// entries will all be sorted. The entries we add we only sort on demand (we
// revisit blocks after we insert info for them.
unsigned NumSortedEntries = Cache->size();
+ // SkipFirstBlock - If this is the very first block that we're processing, we
+ // don't want to scan or think about its body, because the client was supposed
+ // to do a local dependence query. Instead, just start processing it by
+ // adding its predecessors to the worklist and iterating.
+ bool SkipFirstBlock = Visited.empty();
+
while (!Worklist.empty()) {
BasicBlock *BB = Worklist.pop_back_val();
- // Analyze the dependency of *Pointer in FromBB. See if we already have
- // been here.
- if (!Visited.insert(BB))
- continue;
-
- // Get the dependency info for Pointer in BB. If we have cached
- // information, we will use it, otherwise we compute it.
-
- // Do a binary search to see if we already have an entry for this block in
- // the cache set. If so, find it.
- NonLocalDepInfo::iterator Entry =
- std::upper_bound(Cache->begin(), Cache->begin()+NumSortedEntries,
- std::make_pair(BB, MemDepResult()));
- if (Entry != Cache->begin() && (&*Entry)[-1].first == BB)
- --Entry;
-
- MemDepResult *ExistingResult = 0;
- if (Entry != Cache->begin()+NumSortedEntries && Entry->first == BB)
- ExistingResult = &Entry->second;
-
- // If we have a cached entry, and it is non-dirty, use it as the value for
- // this dependency.
- MemDepResult Dep;
- if (ExistingResult && !ExistingResult->isDirty()) {
- Dep = *ExistingResult;
- ++NumCacheNonLocalPtr;
+ // Skip the first block if we have it.
+ if (SkipFirstBlock) {
+ SkipFirstBlock = false;
} else {
- // Otherwise, we have to scan for the value. If we have a dirty cache
- // entry, start scanning from its position, otherwise we scan from the end
- // of the block.
- BasicBlock::iterator ScanPos = BB->end();
- if (ExistingResult && ExistingResult->getInst()) {
- assert(ExistingResult->getInst()->getParent() == BB &&
- "Instruction invalidated?");
- ++NumCacheDirtyNonLocalPtr;
- ScanPos = ExistingResult->getInst();
-
- // Eliminating the dirty entry from 'Cache', so update the reverse info.
- SmallPtrSet<void *, 4> &InstMap = ReverseNonLocalPtrDeps[ScanPos];
- bool Contained = InstMap.erase(CacheKey.getOpaqueValue());
- assert(Contained && "Invalid cache entry"); Contained=Contained;
- // FIXME: Use an iterator to avoid a repeated lookup in ".erase".
- if (InstMap.empty()) ReverseNonLocalPtrDeps.erase(ScanPos);
- } else {
- ++NumUncacheNonLocalPtr;
- }
-
- // Scan the block for the dependency.
- Dep = getPointerDependencyFrom(Pointer, PointeeSize, isLoad, ScanPos, BB);
-
- // If we had a dirty entry for the block, update it. Otherwise, just add
- // a new entry.
- if (ExistingResult)
- *ExistingResult = Dep;
- else
- Cache->push_back(std::make_pair(BB, Dep));
+ // Analyze the dependency of *Pointer in FromBB. See if we already have
+ // been here.
+ if (!Visited.insert(BB))
+ continue;
+
+ // Get the dependency info for Pointer in BB. If we have cached
+ // information, we will use it, otherwise we compute it.
+ MemDepResult Dep = GetNonLocalInfoForBlock(Pointer, PointeeSize, isLoad,
+ BB, Cache, NumSortedEntries);
- // If the block has a dependency (i.e. it isn't completely transparent to
- // the value), remember the reverse association because we just added it
- // to Cache!
+ // If we got a Def or Clobber, add this to the list of results.
if (!Dep.isNonLocal()) {
- // Keep the ReverseNonLocalPtrDeps map up to date so we can efficiently
- // update MemDep when we remove instructions.
- Instruction *Inst = Dep.getInst();
- assert(Inst && "Didn't depend on anything?");
- ReverseNonLocalPtrDeps[Inst].insert(CacheKey.getOpaqueValue());
+ Result.push_back(NonLocalDepEntry(BB, Dep));
+ continue;
}
}
- // If we got a Def or Clobber, add this to the list of results.
- if (!Dep.isNonLocal()) {
- Result.push_back(NonLocalDepEntry(BB, Dep));
- continue;
- }
-
// Otherwise, we have to process all the predecessors of this block to scan
// them as well.
- for (pred_iterator PI = pred_begin(BB), E = pred_end(BB); PI != E; ++PI) {
+ for (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++PI) {
// TODO: PHI TRANSLATE.
Worklist.push_back(*PI);
}
}
- // If we computed new values, re-sort Cache.
- if (NumSortedEntries != Cache->size())
+ // Okay, we're done now. If we added new values to the cache, re-sort it.
+ switch (Cache->size()-NumSortedEntries) {
+ case 0:
+ // done, no new entries.
+ break;
+ case 2: {
+ // Two new entries, insert the last one into place.
+ NonLocalDepEntry Val = Cache->back();
+ Cache->pop_back();
+ NonLocalDepInfo::iterator Entry =
+ std::upper_bound(Cache->begin(), Cache->end()-1, Val);
+ Cache->insert(Entry, Val);
+ // FALL THROUGH.
+ }
+ case 1: {
+ // One new entry, Just insert the new value at the appropriate position.
+ NonLocalDepEntry Val = Cache->back();
+ Cache->pop_back();
+ NonLocalDepInfo::iterator Entry =
+ std::upper_bound(Cache->begin(), Cache->end(), Val);
+ Cache->insert(Entry, Val);
+ break;
+ }
+ default:
+ // Added many values, do a full scale sort.
std::sort(Cache->begin(), Cache->end());
+ }
}
/// RemoveCachedNonLocalPointerDependencies - If P exists in
// Remove all of the entries in the BB->val map. This involves removing
// instructions from the reverse map.
- NonLocalDepInfo &PInfo = It->second;
+ NonLocalDepInfo &PInfo = It->second.second;
for (unsigned i = 0, e = PInfo.size(); i != e; ++i) {
Instruction *Target = PInfo[i].second.getInst();
assert(Target->getParent() == PInfo[i].first && Target != P.getPointer());
// Eliminating the dirty entry from 'Cache', so update the reverse info.
- SmallPtrSet<void *, 4> &InstMap = ReverseNonLocalPtrDeps[Target];
- bool Contained = InstMap.erase(P.getOpaqueValue());
- assert(Contained && "Invalid cache entry"); Contained=Contained;
-
- // FIXME: Use an iterator to avoid a repeated lookup in ".erase".
- if (InstMap.empty()) ReverseNonLocalPtrDeps.erase(Target);
+ RemoveFromReverseMap(ReverseNonLocalPtrDeps, Target, P.getOpaqueValue());
}
// Remove P from NonLocalPointerDeps (which deletes NonLocalDepInfo).
for (NonLocalDepInfo::iterator DI = BlockMap.begin(), DE = BlockMap.end();
DI != DE; ++DI)
if (Instruction *Inst = DI->second.getInst())
- ReverseNonLocalDeps[Inst].erase(RemInst);
+ RemoveFromReverseMap(ReverseNonLocalDeps, Inst, RemInst);
NonLocalDeps.erase(NLDI);
}
LocalDepMapType::iterator LocalDepEntry = LocalDeps.find(RemInst);
if (LocalDepEntry != LocalDeps.end()) {
// Remove us from DepInst's reverse set now that the local dep info is gone.
- if (Instruction *Inst = LocalDepEntry->second.getInst()) {
- SmallPtrSet<Instruction*, 4> &RLD = ReverseLocalDeps[Inst];
- bool Found = RLD.erase(RemInst);
- assert(Found && "Invalid reverse map!"); Found=Found;
- // FIXME: Use an iterator to avoid looking up Inst again.
- if (RLD.empty())
- ReverseLocalDeps.erase(Inst);
- }
+ if (Instruction *Inst = LocalDepEntry->second.getInst())
+ RemoveFromReverseMap(ReverseLocalDeps, Inst, RemInst);
// Remove this local dependency info.
LocalDeps.erase(LocalDepEntry);
// Loop over all of the things that depend on the instruction we're removing.
//
SmallVector<std::pair<Instruction*, Instruction*>, 8> ReverseDepsToAdd;
+
+ // If we find RemInst as a clobber or Def in any of the maps for other values,
+ // we need to replace its entry with a dirty version of the instruction after
+ // it. If RemInst is a terminator, we use a null dirty value.
+ //
+ // Using a dirty version of the instruction after RemInst saves having to scan
+ // the entire block to get to this point.
+ MemDepResult NewDirtyVal;
+ if (!RemInst->isTerminator())
+ NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst));
ReverseDepMapType::iterator ReverseDepIt = ReverseLocalDeps.find(RemInst);
if (ReverseDepIt != ReverseLocalDeps.end()) {
assert(!ReverseDeps.empty() && !isa<TerminatorInst>(RemInst) &&
"Nothing can locally depend on a terminator");
- // Anything that was locally dependent on RemInst is now going to be
- // dependent on the instruction after RemInst. It will have the dirty flag
- // set so it will rescan. This saves having to scan the entire block to get
- // to this point.
- Instruction *NewDepInst = ++BasicBlock::iterator(RemInst);
-
for (SmallPtrSet<Instruction*, 4>::iterator I = ReverseDeps.begin(),
E = ReverseDeps.end(); I != E; ++I) {
Instruction *InstDependingOnRemInst = *I;
assert(InstDependingOnRemInst != RemInst &&
"Already removed our local dep info");
- LocalDeps[InstDependingOnRemInst] = MemDepResult::getDirty(NewDepInst);
+ LocalDeps[InstDependingOnRemInst] = NewDirtyVal;
// Make sure to remember that new things depend on NewDepInst.
- ReverseDepsToAdd.push_back(std::make_pair(NewDepInst,
+ assert(NewDirtyVal.getInst() && "There is no way something else can have "
+ "a local dep on this if it is a terminator!");
+ ReverseDepsToAdd.push_back(std::make_pair(NewDirtyVal.getInst(),
InstDependingOnRemInst));
}
if (DI->second.getInst() != RemInst) continue;
// Convert to a dirty entry for the subsequent instruction.
- Instruction *NextI = 0;
- if (!RemInst->isTerminator()) {
- NextI = ++BasicBlock::iterator(RemInst);
+ DI->second = NewDirtyVal;
+
+ if (Instruction *NextI = NewDirtyVal.getInst())
ReverseDepsToAdd.push_back(std::make_pair(NextI, *I));
- }
- DI->second = MemDepResult::getDirty(NextI);
}
}
assert(P.getPointer() != RemInst &&
"Already removed NonLocalPointerDeps info for RemInst");
- NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P];
+ NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].second;
- MemDepResult NewDirtyVal;
- if (!RemInst->isTerminator())
- NewDirtyVal = MemDepResult::getDirty(++BasicBlock::iterator(RemInst));
+ // The cache is not valid for any specific block anymore.
+ NonLocalPointerDeps[P].first = 0;
// Update any entries for RemInst to use the instruction after it.
for (NonLocalDepInfo::iterator DI = NLPDI.begin(), DE = NLPDI.end();
for (CachedNonLocalPointerInfo::const_iterator I =NonLocalPointerDeps.begin(),
E = NonLocalPointerDeps.end(); I != E; ++I) {
assert(I->first.getPointer() != D && "Inst occurs in NLPD map key");
- const NonLocalDepInfo &Val = I->second;
+ const NonLocalDepInfo &Val = I->second.second;
for (NonLocalDepInfo::const_iterator II = Val.begin(), E = Val.end();
II != E; ++II)
assert(II->second.getInst() != D && "Inst occurs as NLPD value");
projects / oota-llvm.git / blobdiff