By min, I mean max.

[oota-llvm.git] / lib / Analysis / EscapeAnalysis.cpp

diff --git a/lib/Analysis/EscapeAnalysis.cpp b/lib/Analysis/EscapeAnalysis.cpp
index 07f4761fd5f2861b830ccdf001e4f6a6e54833d4..67cc6009e39767d416ea66c345c6d0fb5f38d918 100644 (file)
--- a/lib/Analysis/EscapeAnalysis.cpp
+++ b/lib/Analysis/EscapeAnalysis.cpp
@@ -13,9 +13,11 @@
 
 #define DEBUG_TYPE "escape-analysis"
 #include "llvm/Analysis/EscapeAnalysis.h"
+#include "llvm/Constants.h"
 #include "llvm/Module.h"
 #include "llvm/Support/InstIterator.h"
 #include "llvm/ADT/SmallPtrSet.h"
+#include <vector>
 using namespace llvm;
 
 char EscapeAnalysis::ID = 0;
@@ -48,7 +50,8 @@ bool EscapeAnalysis::runOnFunction(Function& F) {
       bool inserted = false;
       for (Function::arg_iterator AI = F.arg_begin(), AE = F.arg_end();
            AI != AE; ++AI) {
-        AliasAnalysis::AliasResult R = AA.alias(Pointer, StoreSize, AI, ~0UL);
+        if (!isa<PointerType>(AI->getType())) continue;
+        AliasAnalysis::AliasResult R = AA.alias(Pointer, StoreSize, AI, ~0U);
         if (R != AliasAnalysis::NoAlias) {
           EscapePoints.insert(S);
           inserted = true;
@@ -61,7 +64,7 @@ bool EscapeAnalysis::runOnFunction(Function& F) {
       
       for (Module::global_iterator GI = M->global_begin(), GE = M->global_end();
            GI != GE; ++GI) {
-        AliasAnalysis::AliasResult R = AA.alias(Pointer, StoreSize, GI, ~0UL);
+        AliasAnalysis::AliasResult R = AA.alias(Pointer, StoreSize, GI, ~0U);
         if (R != AliasAnalysis::NoAlias) {
           EscapePoints.insert(S);
           break;
@@ -78,6 +81,11 @@ bool EscapeAnalysis::runOnFunction(Function& F) {
     // for malloc to alloca promotion.
     } else if (isa<ReturnInst>(I)) {
       EscapePoints.insert(I);
+    
+    // Branching on the value of a pointer may allow the value to escape through
+    // methods not discoverable via def-use chaining.
+    } else if(isa<BranchInst>(I) || isa<SwitchInst>(I)) {
+      EscapePoints.insert(I);
     }
     
     // FIXME: Are there any other possible escape points?
@@ -92,40 +100,50 @@ bool EscapeAnalysis::runOnFunction(Function& F) {
 /// escape point.
 /// FIXME: Once we've discovered a path, it would be a good idea to memoize it,
 /// and all of its subpaths, to amortize the cost of future queries.
-bool EscapeAnalysis::escapes(AllocationInst* A) {
+bool EscapeAnalysis::escapes(Value* A) {
+  assert(isa<PointerType>(A->getType()) && 
+         "Can't do escape analysis on non-pointer types!");
+  
   std::vector<Value*> worklist;
   worklist.push_back(A);
   
   SmallPtrSet<Value*, 8> visited;
+  visited.insert(A);
   while (!worklist.empty()) {
     Value* curr = worklist.back();
     worklist.pop_back();
     
-    visited.insert(curr);
-    
-    if (Instruction* CurrInst = dyn_cast<Instruction>(curr))
-      if (EscapePoints.count(CurrInst))
-        return true;
+    if (Instruction* I = dyn_cast<Instruction>(curr))
+      if (EscapePoints.count(I)) {
+        BranchInst* B = dyn_cast<BranchInst>(I);
+        if (!B) return true;
+        Value* condition = B->getCondition();
+        ICmpInst* C = dyn_cast<ICmpInst>(condition);
+        if (!C) return true;
+        Value* O1 = C->getOperand(0);
+        Value* O2 = C->getOperand(1);
+        if (isa<MallocInst>(O1->stripPointerCasts())) {
+          if (!isa<ConstantPointerNull>(O2)) return true;
+        } else if(isa<MallocInst>(O2->stripPointerCasts())) {
+          if (!isa<ConstantPointerNull>(O1)) return true;
+        } else
+          return true;
+      }
     
-    for (Instruction::use_iterator UI = curr->use_begin(), UE = curr->use_end();
-         UI != UE; ++UI)
-      if (Instruction* U = dyn_cast<Instruction>(UI))
-        if (!visited.count(U))
-          if (StoreInst* S = dyn_cast<StoreInst>(U)) {
-            // We know this must be an instruction, because constant gep's would
-            // have been found to alias a global, so stores to them would have
-            // been in EscapePoints.
-            worklist.push_back(cast<Instruction>(S->getPointerOperand()));
-          } else if (isa<BranchInst>(U) || isa<SwitchInst>(U)) {
-            // Because branches on the pointer value can hide data dependencies,
-            // we need to track values that were generated by branching on the
-            // pointer (or some derived value).  To do that, we push the block,
-            // whose uses will be the PHINodes that generate information based
-            // one it.
-            worklist.push_back(U->getParent());
-          } else
+    if (StoreInst* S = dyn_cast<StoreInst>(curr)) {
+      // We know this must be an instruction, because constant gep's would
+      // have been found to alias a global, so stores to them would have
+      // been in EscapePoints.
+      if (visited.insert(cast<Instruction>(S->getPointerOperand())))
+        worklist.push_back(cast<Instruction>(S->getPointerOperand()));
+    } else {
+      for (Instruction::use_iterator UI = curr->use_begin(),
+           UE = curr->use_end(); UI != UE; ++UI)
+        if (Instruction* U = dyn_cast<Instruction>(UI))
+          if (visited.insert(U))
             worklist.push_back(U);
+    }
   }
   
   return false;
-}
\ No newline at end of file
+}