// While we have blocks to analyze, get their values.
SmallPtrSet<BasicBlock*, 64> Visited;
-
- for (BasicBlock **PI = PredCache->GetPreds(FromBB); *PI; ++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) {
+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);
// 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 (BasicBlock **PI = PredCache->GetPreds(BB); *PI; ++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
projects / oota-llvm.git / blobdiff