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         AliasAnalysis::AliasResult R = AA.alias(Pointer, StoreSize, AI, ~0UL);
  52         if (R != AliasAnalysis::NoAlias) {
  53           EscapePoints.insert(S);
  54           inserted = true;
  55           break;
  56         }
  57       }
  58
  59       if (inserted)
  60         continue;
  61
  62       for (Module::global_iterator GI = M->global_begin(), GE = M->global_end();
  63            GI != GE; ++GI) {
  64         AliasAnalysis::AliasResult R = AA.alias(Pointer, StoreSize, GI, ~0UL);
  65         if (R != AliasAnalysis::NoAlias) {
  66           EscapePoints.insert(S);
  67           break;
  68         }
  69       }
  70
  71     // Calls and invokes potentially allow their parameters to escape.
  72     // FIXME: This can and should be refined.  Intrinsics have known escape
  73     // behavior, and alias analysis may be able to tell us more about callees.
  74     } else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
  75       EscapePoints.insert(I);
  76
  77     // Returns allow the return value to escape.  This is mostly important
  78     // for malloc to alloca promotion.
  79     } else if (isa<ReturnInst>(I)) {
  80       EscapePoints.insert(I);
  81     }
  82
  83     // FIXME: Are there any other possible escape points?
  84   }
  85
  86   return false;
  87 }
  88
  89 /// escapes - Determines whether the passed allocation can escape from the
  90 /// current function.  It does this by using a simple worklist algorithm to
  91 /// search for a path in the def-use graph from the allocation to an
  92 /// escape point.
  93 /// FIXME: Once we've discovered a path, it would be a good idea to memoize it,
  94 /// and all of its subpaths, to amortize the cost of future queries.
  95 bool EscapeAnalysis::escapes(AllocationInst* A) {
  96   std::vector<Value*> worklist;
  97   worklist.push_back(A);
  98
  99   SmallPtrSet<Value*, 8> visited;
 100   while (!worklist.empty()) {
 101     Value* curr = worklist.back();
 102     worklist.pop_back();
 103
 104     visited.insert(curr);
 105
 106     if (Instruction* CurrInst = dyn_cast<Instruction>(curr))
 107       if (EscapePoints.count(CurrInst))
 108         return true;
 109
 110     for (Instruction::use_iterator UI = curr->use_begin(), UE = curr->use_end();
 111          UI != UE; ++UI)
 112       if (Instruction* U = dyn_cast<Instruction>(UI))
 113         if (!visited.count(U))
 114           if (StoreInst* S = dyn_cast<StoreInst>(U)) {
 115             // We know this must be an instruction, because constant gep's would
 116             // have been found to alias a global, so stores to them would have
 117             // been in EscapePoints.
 118             worklist.push_back(cast<Instruction>(S->getPointerOperand()));
 119           } else if (isa<BranchInst>(U) || isa<SwitchInst>(U)) {
 120             // Because branches on the pointer value can hide data dependencies,
 121             // we need to track values that were generated by branching on the
 122             // pointer (or some derived value).  To do that, we push the block,
 123             // whose uses will be the PHINodes that generate information based
 124             // one it.
 125             worklist.push_back(U->getParent());
 126           } else
 127             worklist.push_back(U);
 128   }
 129
 130   return false;
 131 }