+/// nonLocalHelper - Private helper used to calculate non-local dependencies
+/// by doing DFS on the predecessors of a block to find its dependencies
+void MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
+ BasicBlock* block,
+ DenseMap<BasicBlock*, Value*>& resp) {
+ // Set of blocks that we've already visited in our DFS
+ SmallPtrSet<BasicBlock*, 4> visited;
+ // If we're updating a dirtied cache entry, we don't need to reprocess
+ // already computed entries.
+ for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(),
+ E = resp.end(); I != E; ++I)
+ if (I->second != Dirty)
+ visited.insert(I->first);
+
+ // Current stack of the DFS
+ SmallVector<BasicBlock*, 4> stack;
+ 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()) {
+ BasicBlock* BB = stack.back();
+
+ // If we've already visited this block, no need to revist
+ if (visited.count(BB)) {
+ stack.pop_back();
+ continue;
+ }
+
+ // If we find a new block with a local dependency for query,
+ // then we insert the new dependency and backtrack.
+ if (BB != block) {
+ visited.insert(BB);
+
+ Instruction* localDep = getDependency(query, 0, BB);
+ if (localDep != NonLocal) {
+ resp.insert(std::make_pair(BB, localDep));
+ stack.pop_back();
+
+ continue;
+ }
+ // 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) {
+ visited.insert(BB);
+
+ Instruction* localDep = getDependency(query, 0, BB);
+ if (localDep != query)
+ resp.insert(std::make_pair(BB, localDep));
+
+ stack.pop_back();
+
+ continue;
+ }
+
+ // 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;
+ 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)
+ continue;
+ // If we didn't insert because we have no predecessors, then this
+ // query has no dependency at all.
+ else if (!inserted && !predOnStack) {
+ resp.insert(std::make_pair(BB, None));
+ // If we didn't insert because our predecessors are already on the stack,
+ // then we might still have a dependency, but it will be discovered during
+ // backtracking.
+ } else if (!inserted && predOnStack){
+ resp.insert(std::make_pair(BB, NonLocal));
+ }
+
+ stack.pop_back();
+ }
+}
+
+/// getNonLocalDependency - Fills the passed-in map with the non-local
+/// dependencies of the queries. The map will contain NonLocal for
+/// blocks between the query and its dependencies.
+void MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
+ DenseMap<BasicBlock*, Value*>& resp) {
+ if (depGraphNonLocal.count(query)) {
+ DenseMap<BasicBlock*, Value*>& cached = depGraphNonLocal[query];
+ NumCacheNonlocal++;
+
+ SmallVector<BasicBlock*, 4> dirtied;
+ for (DenseMap<BasicBlock*, Value*>::iterator I = cached.begin(),
+ E = cached.end(); I != E; ++I)
+ if (I->second == Dirty)
+ dirtied.push_back(I->first);
+
+ for (SmallVector<BasicBlock*, 4>::iterator I = dirtied.begin(),
+ E = dirtied.end(); I != E; ++I) {
+ Instruction* localDep = getDependency(query, 0, *I);
+ if (localDep != NonLocal)
+ cached[*I] = localDep;
+ else {
+ cached.erase(*I);
+ nonLocalHelper(query, *I, cached);
+ }
+ }
+
+ resp = cached;
+
+ // Update the reverse non-local dependency cache
+ for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(), E = resp.end();
+ I != E; ++I)
+ reverseDepNonLocal[I->second].insert(query);
+
+ return;
+ } else
+ NumUncacheNonlocal++;
+
+ // If not, go ahead and search for non-local deps.
+ nonLocalHelper(query, query->getParent(), resp);
+
+ // Update the non-local dependency cache
+ for (DenseMap<BasicBlock*, Value*>::iterator I = resp.begin(), E = resp.end();
+ I != E; ++I) {
+ depGraphNonLocal[query].insert(*I);
+ reverseDepNonLocal[I->second].insert(query);
+ }
+}
+