lib/Analysis/EscapeAnalysis.cpp

   1 //===------------- EscapeAnalysis.h - Pointer escape analysis -------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file provides the implementation of the pointer escape analysis.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #define DEBUG_TYPE "escape-analysis"
  15 #include "llvm/Analysis/EscapeAnalysis.h"
  16 #include "llvm/Constants.h"
  17 #include "llvm/Instructions.h"
  18 #include "llvm/Module.h"
  19 #include "llvm/Analysis/AliasAnalysis.h"
  20 #include "llvm/Support/InstIterator.h"
  21 #include "llvm/Target/TargetData.h"
  22 #include "llvm/ADT/SmallPtrSet.h"
  23 #include <vector>
  24 using namespace llvm;
  25
  26 char EscapeAnalysis::ID = 0;
  27 static RegisterPass<EscapeAnalysis> X("escape-analysis",
  28                                       "Pointer Escape Analysis", true, true);
  29
  30
  31 void EscapeAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
  32   AU.addRequiredTransitive<TargetData>();
  33   AU.addRequiredTransitive<AliasAnalysis>();
  34   AU.setPreservesAll();
  35 }
  36
  37 /// runOnFunction - Precomputation for escape analysis.  This collects all know
  38 /// "escape points" in the def-use graph of the function.  These are
  39 /// instructions which allow their inputs to escape from the current function.
  40 bool EscapeAnalysis::runOnFunction(Function& F) {
  41   EscapePoints.clear();
  42
  43   TargetData& TD = getAnalysis<TargetData>();
  44   AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
  45   Module* M = F.getParent();
  46
  47   // Walk through all instructions in the function, identifying those that
  48   // may allow their inputs to escape.
  49   for(inst_iterator II = inst_begin(F), IE = inst_end(F); II != IE; ++II) {
  50     Instruction* I = &*II;
  51
  52     // The most obvious case is stores.  Any store that may write to global
  53     // memory or to a function argument potentially allows its input to escape.
  54     if (StoreInst* S = dyn_cast<StoreInst>(I)) {
  55       const Type* StoreType = S->getOperand(0)->getType();
  56       unsigned StoreSize = TD.getTypeStoreSize(StoreType);
  57       Value* Pointer = S->getPointerOperand();
  58
  59       bool inserted = false;
  60       for (Function::arg_iterator AI = F.arg_begin(), AE = F.arg_end();
  61            AI != AE; ++AI) {
  62         if (!isa<PointerType>(AI->getType())) continue;
  63         AliasAnalysis::AliasResult R = AA.alias(Pointer, StoreSize, AI, ~0U);
  64         if (R != AliasAnalysis::NoAlias) {
  65           EscapePoints.insert(S);
  66           inserted = true;
  67           break;
  68         }
  69       }
  70
  71       if (inserted)
  72         continue;
  73
  74       for (Module::global_iterator GI = M->global_begin(), GE = M->global_end();
  75            GI != GE; ++GI) {
  76         AliasAnalysis::AliasResult R = AA.alias(Pointer, StoreSize, GI, ~0U);
  77         if (R != AliasAnalysis::NoAlias) {
  78           EscapePoints.insert(S);
  79           break;
  80         }
  81       }
  82
  83     // Calls and invokes potentially allow their parameters to escape.
  84     // FIXME: This can and should be refined.  Intrinsics have known escape
  85     // behavior, and alias analysis may be able to tell us more about callees.
  86     } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
  87       EscapePoints.insert(I);
  88
  89     // Returns allow the return value to escape.  This is mostly important
  90     // for malloc to alloca promotion.
  91     } else if (isa<ReturnInst>(I)) {
  92       EscapePoints.insert(I);
  93
  94     // Branching on the value of a pointer may allow the value to escape through
  95     // methods not discoverable via def-use chaining.
  96     } else if(isa<BranchInst>(I) || isa<SwitchInst>(I)) {
  97       EscapePoints.insert(I);
  98     }
  99
 100     // FIXME: Are there any other possible escape points?
 101   }
 102
 103   return false;
 104 }
 105
 106 /// escapes - Determines whether the passed allocation can escape from the
 107 /// current function.  It does this by using a simple worklist algorithm to
 108 /// search for a path in the def-use graph from the allocation to an
 109 /// escape point.
 110 /// FIXME: Once we've discovered a path, it would be a good idea to memoize it,
 111 /// and all of its subpaths, to amortize the cost of future queries.
 112 bool EscapeAnalysis::escapes(Value* A) {
 113   assert(isa<PointerType>(A->getType()) &&
 114          "Can't do escape analysis on non-pointer types!");
 115
 116   std::vector<Value*> worklist;
 117   worklist.push_back(A);
 118
 119   SmallPtrSet<Value*, 8> visited;
 120   visited.insert(A);
 121   while (!worklist.empty()) {
 122     Value* curr = worklist.back();
 123     worklist.pop_back();
 124
 125     if (Instruction* I = dyn_cast<Instruction>(curr))
 126       if (EscapePoints.count(I)) {
 127         BranchInst* B = dyn_cast<BranchInst>(I);
 128         if (!B) return true;
 129         Value* condition = B->getCondition();
 130         ICmpInst* C = dyn_cast<ICmpInst>(condition);
 131         if (!C) return true;
 132         Value* O1 = C->getOperand(0);
 133         Value* O2 = C->getOperand(1);
 134         if (isa<MallocInst>(O1->stripPointerCasts())) {
 135           if (!isa<ConstantPointerNull>(O2)) return true;
 136         } else if(isa<MallocInst>(O2->stripPointerCasts())) {
 137           if (!isa<ConstantPointerNull>(O1)) return true;
 138         } else
 139           return true;
 140       }
 141
 142     if (StoreInst* S = dyn_cast<StoreInst>(curr)) {
 143       // We know this must be an instruction, because constant gep's would
 144       // have been found to alias a global, so stores to them would have
 145       // been in EscapePoints.
 146       if (visited.insert(cast<Instruction>(S->getPointerOperand())))
 147         worklist.push_back(cast<Instruction>(S->getPointerOperand()));
 148     } else {
 149       for (Instruction::use_iterator UI = curr->use_begin(),
 150            UE = curr->use_end(); UI != UE; ++UI)
 151         if (Instruction* U = dyn_cast<Instruction>(UI))
 152           if (visited.insert(U))
 153             worklist.push_back(U);
 154     }
 155   }
 156
 157   return false;
 158 }