1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
|
//===------------- EscapeAnalysis.h - Pointer escape analysis -------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file provides the implementation of the pointer escape analysis.
//
//===----------------------------------------------------------------------===//
#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;
static RegisterPass<EscapeAnalysis> X("escape-analysis",
"Pointer Escape Analysis", true, true);
/// runOnFunction - Precomputation for escape analysis. This collects all know
/// "escape points" in the def-use graph of the function. These are
/// instructions which allow their inputs to escape from the current function.
bool EscapeAnalysis::runOnFunction(Function& F) {
EscapePoints.clear();
TargetData& TD = getAnalysis<TargetData>();
AliasAnalysis& AA = getAnalysis<AliasAnalysis>();
Module* M = F.getParent();
// Walk through all instructions in the function, identifying those that
// may allow their inputs to escape.
for(inst_iterator II = inst_begin(F), IE = inst_end(F); II != IE; ++II) {
Instruction* I = &*II;
// The most obvious case is stores. Any store that may write to global
// memory or to a function argument potentially allows its input to escape.
if (StoreInst* S = dyn_cast<StoreInst>(I)) {
const Type* StoreType = S->getOperand(0)->getType();
unsigned StoreSize = TD.getTypeStoreSize(StoreType);
Value* Pointer = S->getPointerOperand();
bool inserted = false;
for (Function::arg_iterator AI = F.arg_begin(), AE = F.arg_end();
AI != AE; ++AI) {
if (!isa<PointerType>(AI->getType())) continue;
AliasAnalysis::AliasResult R = AA.alias(Pointer, StoreSize, AI, ~0U);
if (R != AliasAnalysis::NoAlias) {
EscapePoints.insert(S);
inserted = true;
break;
}
}
if (inserted)
continue;
for (Module::global_iterator GI = M->global_begin(), GE = M->global_end();
GI != GE; ++GI) {
AliasAnalysis::AliasResult R = AA.alias(Pointer, StoreSize, GI, ~0U);
if (R != AliasAnalysis::NoAlias) {
EscapePoints.insert(S);
break;
}
}
// Calls and invokes potentially allow their parameters to escape.
// FIXME: This can and should be refined. Intrinsics have known escape
// behavior, and alias analysis may be able to tell us more about callees.
} else if (isa<CallInst>(I) || isa<InvokeInst>(I)) {
EscapePoints.insert(I);
// Returns allow the return value to escape. This is mostly important
// 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?
}
return false;
}
/// escapes - Determines whether the passed allocation can escape from the
/// current function. It does this by using a simple worklist algorithm to
/// search for a path in the def-use graph from the allocation to an
/// 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(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();
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;
}
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;
}
|
