1 //===------------- EscapeAnalysis.h - Pointer escape analysis -------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file provides the implementation of the pointer escape analysis.
12 //===----------------------------------------------------------------------===//
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"
26 char EscapeAnalysis::ID = 0;
27 static RegisterPass<EscapeAnalysis> X("escape-analysis",
28 "Pointer Escape Analysis", true, true);
31 void EscapeAnalysis::getAnalysisUsage(AnalysisUsage &AU) const {
32 AU.addRequiredTransitive<TargetData>();
33 AU.addRequiredTransitive<AliasAnalysis>();
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) {
43 TargetData& TD = getAnalysis<TargetData>();
44 AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
45 Module* M = F.getParent();
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;
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();
59 bool inserted = false;
60 for (Function::arg_iterator AI = F.arg_begin(), AE = F.arg_end();
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);
74 for (Module::global_iterator GI = M->global_begin(), GE = M->global_end();
76 AliasAnalysis::AliasResult R = AA.alias(Pointer, StoreSize, GI, ~0U);
77 if (R != AliasAnalysis::NoAlias) {
78 EscapePoints.insert(S);
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);
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);
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);
100 // FIXME: Are there any other possible escape points?
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
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!");
116 std::vector<Value*> worklist;
117 worklist.push_back(A);
119 SmallPtrSet<Value*, 8> visited;
121 while (!worklist.empty()) {
122 Value* curr = worklist.back();
125 if (Instruction* I = dyn_cast<Instruction>(curr))
126 if (EscapePoints.count(I)) {
127 BranchInst* B = dyn_cast<BranchInst>(I);
129 Value* condition = B->getCondition();
130 ICmpInst* C = dyn_cast<ICmpInst>(condition);
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;
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()));
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);