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