#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;
}
} 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 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.
- RemoveFromReverseMap(ReverseNonLocalPtrDeps, ScanPos,
- CacheKey.getOpaqueValue());
- } 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(P.getPointer() != RemInst &&
"Already removed NonLocalPointerDeps info for RemInst");
- NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P];
+ NonLocalDepInfo &NLPDI = NonLocalPointerDeps[P].second;
+
+ // 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