X-Git-Url: http://plrg.eecs.uci.edu/git/?a=blobdiff_plain;f=lib%2FAnalysis%2FMemoryDependenceAnalysis.cpp;h=e260b271641e45d05412e233cb1a66bea088b83a;hb=3dfcf33cf897b04c95e252bbd645e9930f608701;hp=fa4395492577c768fdc3ebf2f0455ff273d20fa3;hpb=1cb960a4bb97336be1339fd5bc2eb28f125f099a;p=oota-llvm.git

diff --git a/lib/Analysis/MemoryDependenceAnalysis.cpp b/lib/Analysis/MemoryDependenceAnalysis.cpp
index fa439549257..e260b271641 100644
--- a/lib/Analysis/MemoryDependenceAnalysis.cpp
+++ b/lib/Analysis/MemoryDependenceAnalysis.cpp
@@ -19,14 +19,15 @@
 #include "llvm/Instructions.h"
 #include "llvm/Function.h"
 #include "llvm/Analysis/AliasAnalysis.h"
+#include "llvm/Support/CFG.h"
 #include "llvm/Target/TargetData.h"
 
 using namespace llvm;
 
 char MemoryDependenceAnalysis::ID = 0;
   
-Instruction* MemoryDependenceAnalysis::NonLocal = (Instruction*)0;
-Instruction* MemoryDependenceAnalysis::None = (Instruction*)~0;
+Instruction* MemoryDependenceAnalysis::NonLocal = (Instruction*)-2;
+Instruction* MemoryDependenceAnalysis::None = (Instruction*)-3;
   
 // Register this pass...
 static RegisterPass<MemoryDependenceAnalysis> X("memdep",
@@ -41,7 +42,8 @@ void MemoryDependenceAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
 }
 
 // Find the dependency of a CallSite
-Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, bool local) {
+Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, Instruction* start,
+                                                             bool local) {
   assert(local && "Non-local memory dependence analysis not yet implemented");
   
   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
@@ -99,14 +101,66 @@ Instruction* MemoryDependenceAnalysis::getCallSiteDependency(CallSite C, bool lo
   return NonLocal;
 }
 
+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;
+}
+
 /// getDependency - Return the instruction on which a memory operation
 /// depends.  The local paramter indicates if the query should only
 /// evaluate dependencies within the same basic block.
 Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
-                                                     bool local) {
-  if (!local)
-    assert(0 && "Non-local memory dependence is not yet supported.");
-  
+                                                     Instruction* start,
+                                                     BasicBlock* block) {
   // Start looking for dependencies with the queried inst
   BasicBlock::iterator QI = query;
   
@@ -115,10 +169,15 @@ Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
   // If we have a _confirmed_ cached entry, return it
   if (cachedResult.second)
     return cachedResult.first;
-  else if (cachedResult.first != NonLocal)
+  else if (cachedResult.first && cachedResult.first != NonLocal)
   // If we have an unconfirmed cached entry, we can start our search from there
     QI = cachedResult.first;
   
+  if (start)
+    QI = start;
+  else if (!start && block)
+    QI = block->end();
+  
   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
   TargetData& TD = getAnalysis<TargetData>();
   
@@ -126,30 +185,31 @@ Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
   Value* dependee = 0;
   uint64_t dependeeSize = 0;
   bool queryIsVolatile = false;
-  if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
+  if (StoreInst* S = dyn_cast<StoreInst>(query)) {
     dependee = S->getPointerOperand();
     dependeeSize = TD.getTypeSize(S->getOperand(0)->getType());
     queryIsVolatile = S->isVolatile();
-  } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
+  } else if (LoadInst* L = dyn_cast<LoadInst>(query)) {
     dependee = L->getPointerOperand();
     dependeeSize = TD.getTypeSize(L->getType());
     queryIsVolatile = L->isVolatile();
-  } else if (VAArgInst* V = dyn_cast<VAArgInst>(QI)) {
+  } else if (VAArgInst* V = dyn_cast<VAArgInst>(query)) {
     dependee = V->getOperand(0);
     dependeeSize = TD.getTypeSize(V->getType());
-  } else if (FreeInst* F = dyn_cast<FreeInst>(QI)) {
+  } else if (FreeInst* F = dyn_cast<FreeInst>(query)) {
     dependee = F->getPointerOperand();
     
     // FreeInsts erase the entire structure, not just a field
     dependeeSize = ~0UL;
-  } else if (CallSite::get(QI).getInstruction() != 0)
-    return getCallSiteDependency(CallSite::get(QI));
+  } else if (CallSite::get(query).getInstruction() != 0)
+    return getCallSiteDependency(CallSite::get(query), start);
   else if (isa<AllocationInst>(query))
     return None;
   else
     return None;
   
-  BasicBlock::iterator blockBegin = query->getParent()->begin();
+  BasicBlock::iterator blockBegin = block ? block->begin()
+                                          : query->getParent()->begin();
   
   while (QI != blockBegin) {
     --QI;
@@ -160,8 +220,11 @@ Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
     if (StoreInst* S = dyn_cast<StoreInst>(QI)) {
       // All volatile loads/stores depend on each other
       if (queryIsVolatile && S->isVolatile()) {
-        depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
-        reverseDep.insert(std::make_pair(S, query));
+        if (!start || block) {
+          depGraphLocal.insert(std::make_pair(query, std::make_pair(S, true)));
+          reverseDep.insert(std::make_pair(S, query));
+        }
+        
         return S;
       }
       
@@ -170,8 +233,11 @@ Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
     } else if (LoadInst* L = dyn_cast<LoadInst>(QI)) {
       // All volatile loads/stores depend on each other
       if (queryIsVolatile && L->isVolatile()) {
-        depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
-        reverseDep.insert(std::make_pair(L, query));
+        if (!start || block) {
+          depGraphLocal.insert(std::make_pair(query, std::make_pair(L, true)));
+          reverseDep.insert(std::make_pair(L, query));
+        }
+        
         return L;
       }
       
@@ -195,8 +261,11 @@ Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
       // Call insts need special handling.  Check is they can modify our pointer
       if (AA.getModRefInfo(CallSite::get(QI), dependee, dependeeSize) !=
           AliasAnalysis::NoModRef) {
-        depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
-        reverseDep.insert(std::make_pair(QI, query));
+        if (!start || block) {
+          depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
+          reverseDep.insert(std::make_pair(QI, query));
+        }
+        
         return QI;
       } else {
         continue;
@@ -209,17 +278,22 @@ Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
                                               dependee, dependeeSize);
       
       if (R != AliasAnalysis::NoAlias) {
-        depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
-        reverseDep.insert(std::make_pair(QI, query));
+        if (!start || block) {
+          depGraphLocal.insert(std::make_pair(query, std::make_pair(QI, true)));
+          reverseDep.insert(std::make_pair(QI, query));
+        }
+        
         return QI;
       }
     }
   }
   
   // If we found nothing, return the non-local flag
-  depGraphLocal.insert(std::make_pair(query,
-                                      std::make_pair(NonLocal, true)));
-  reverseDep.insert(std::make_pair(NonLocal, query));
+  if (!start || block) {
+    depGraphLocal.insert(std::make_pair(query,
+                                        std::make_pair(NonLocal, true)));
+    reverseDep.insert(std::make_pair(NonLocal, query));
+  }
   
   return NonLocal;
 }
@@ -229,7 +303,8 @@ Instruction* MemoryDependenceAnalysis::getDependency(Instruction* query,
 void MemoryDependenceAnalysis::removeInstruction(Instruction* rem) {
   // Figure out the new dep for things that currently depend on rem
   Instruction* newDep = NonLocal;
-  if (depGraphLocal[rem].first != NonLocal) {
+  if (depGraphLocal[rem].first != NonLocal &&
+      depGraphLocal[rem].second) {
     // If we have dep info for rem, set them to it
     BasicBlock::iterator RI = depGraphLocal[rem].first;
     RI++;