+bool MemoryDependenceAnalysis::nonLocalHelper(Instruction* query,
+ BasicBlock* block,
+ DenseMap<BasicBlock*, Value*>& resp,
+ SmallPtrSet<BasicBlock*, 4>& visited) {
+ if (resp.count(block))
+ return resp[block] != None;
+
+ Instruction* localDep = getDependency(query, 0, block);
+ if (localDep != NonLocal) {
+ resp.insert(std::make_pair(block, localDep));
+ return true;
+ }
+
+ visited.insert(block);
+
+ bool inserted = false;
+ for (pred_iterator PI = pred_begin(block), PE = pred_end(block);
+ PI != PE; ++PI)
+ if (!visited.count(*PI))
+ inserted |= nonLocalHelper(query, *PI, resp, visited);
+
+ visited.erase(block);
+
+ if (!inserted)
+ resp.insert(std::make_pair(block, None));
+
+ return inserted;
+}
+
+bool MemoryDependenceAnalysis::getNonLocalDependency(Instruction* query,
+ DenseMap<BasicBlock*, Value*>& resp) {
+ Instruction* localDep = getDependency(query);
+ if (localDep != NonLocal) {
+ resp.insert(std::make_pair(query->getParent(), localDep));
+ return true;
+ }
+
+ bool inserted = false;
+ SmallPtrSet<BasicBlock*, 4> visited;
+ visited.insert(query->getParent());
+
+ BasicBlock* parent = query->getParent();
+ for (pred_iterator PI = pred_begin(parent), PE = pred_end(parent);
+ PI != PE; ++PI) {
+ if (!visited.count(*PI))
+ inserted |= nonLocalHelper(query, *PI, resp, visited);
+ }
+
+ if (!inserted)
+ resp.insert(std::make_pair(query->getParent(), None));
+
+ return inserted;
+}
+