]>
Commit | Line | Data |
---|---|---|
223e47cc LB |
1 | //===--- CaptureTracking.cpp - Determine whether a pointer is captured ----===// |
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 contains routines that help determine which pointers are captured. | |
11 | // A pointer value is captured if the function makes a copy of any part of the | |
12 | // pointer that outlives the call. Not being captured means, more or less, that | |
13 | // the pointer is only dereferenced and not stored in a global. Returning part | |
14 | // of the pointer as the function return value may or may not count as capturing | |
15 | // the pointer, depending on the context. | |
16 | // | |
17 | //===----------------------------------------------------------------------===// | |
18 | ||
19 | #include "llvm/ADT/SmallSet.h" | |
20 | #include "llvm/ADT/SmallVector.h" | |
970d7e83 | 21 | #include "llvm/Analysis/AliasAnalysis.h" |
1a4d82fc | 22 | #include "llvm/Analysis/CFG.h" |
85aaf69f | 23 | #include "llvm/Analysis/CaptureTracking.h" |
1a4d82fc | 24 | #include "llvm/IR/CallSite.h" |
970d7e83 | 25 | #include "llvm/IR/Constants.h" |
1a4d82fc | 26 | #include "llvm/IR/Dominators.h" |
970d7e83 | 27 | #include "llvm/IR/Instructions.h" |
970d7e83 | 28 | |
223e47cc LB |
29 | using namespace llvm; |
30 | ||
31 | CaptureTracker::~CaptureTracker() {} | |
32 | ||
1a4d82fc | 33 | bool CaptureTracker::shouldExplore(const Use *U) { return true; } |
970d7e83 | 34 | |
223e47cc LB |
35 | namespace { |
36 | struct SimpleCaptureTracker : public CaptureTracker { | |
37 | explicit SimpleCaptureTracker(bool ReturnCaptures) | |
38 | : ReturnCaptures(ReturnCaptures), Captured(false) {} | |
39 | ||
1a4d82fc | 40 | void tooManyUses() override { Captured = true; } |
223e47cc | 41 | |
1a4d82fc | 42 | bool captured(const Use *U) override { |
223e47cc LB |
43 | if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures) |
44 | return false; | |
45 | ||
46 | Captured = true; | |
47 | return true; | |
48 | } | |
49 | ||
50 | bool ReturnCaptures; | |
51 | ||
52 | bool Captured; | |
53 | }; | |
1a4d82fc JJ |
54 | |
55 | /// Only find pointer captures which happen before the given instruction. Uses | |
56 | /// the dominator tree to determine whether one instruction is before another. | |
57 | /// Only support the case where the Value is defined in the same basic block | |
58 | /// as the given instruction and the use. | |
59 | struct CapturesBefore : public CaptureTracker { | |
60 | CapturesBefore(bool ReturnCaptures, const Instruction *I, DominatorTree *DT, | |
61 | bool IncludeI) | |
62 | : BeforeHere(I), DT(DT), ReturnCaptures(ReturnCaptures), | |
63 | IncludeI(IncludeI), Captured(false) {} | |
64 | ||
65 | void tooManyUses() override { Captured = true; } | |
66 | ||
67 | bool shouldExplore(const Use *U) override { | |
68 | Instruction *I = cast<Instruction>(U->getUser()); | |
69 | if (BeforeHere == I && !IncludeI) | |
70 | return false; | |
71 | ||
72 | BasicBlock *BB = I->getParent(); | |
73 | // We explore this usage only if the usage can reach "BeforeHere". | |
74 | // If use is not reachable from entry, there is no need to explore. | |
75 | if (BeforeHere != I && !DT->isReachableFromEntry(BB)) | |
76 | return false; | |
77 | // If the value is defined in the same basic block as use and BeforeHere, | |
78 | // there is no need to explore the use if BeforeHere dominates use. | |
79 | // Check whether there is a path from I to BeforeHere. | |
80 | if (BeforeHere != I && DT->dominates(BeforeHere, I) && | |
81 | !isPotentiallyReachable(I, BeforeHere, DT)) | |
82 | return false; | |
83 | return true; | |
84 | } | |
85 | ||
86 | bool captured(const Use *U) override { | |
87 | if (isa<ReturnInst>(U->getUser()) && !ReturnCaptures) | |
88 | return false; | |
89 | ||
90 | Instruction *I = cast<Instruction>(U->getUser()); | |
91 | if (BeforeHere == I && !IncludeI) | |
92 | return false; | |
93 | ||
94 | BasicBlock *BB = I->getParent(); | |
95 | // Same logic as in shouldExplore. | |
96 | if (BeforeHere != I && !DT->isReachableFromEntry(BB)) | |
97 | return false; | |
98 | if (BeforeHere != I && DT->dominates(BeforeHere, I) && | |
99 | !isPotentiallyReachable(I, BeforeHere, DT)) | |
100 | return false; | |
101 | Captured = true; | |
102 | return true; | |
103 | } | |
104 | ||
105 | const Instruction *BeforeHere; | |
106 | DominatorTree *DT; | |
107 | ||
108 | bool ReturnCaptures; | |
109 | bool IncludeI; | |
110 | ||
111 | bool Captured; | |
112 | }; | |
223e47cc LB |
113 | } |
114 | ||
115 | /// PointerMayBeCaptured - Return true if this pointer value may be captured | |
116 | /// by the enclosing function (which is required to exist). This routine can | |
117 | /// be expensive, so consider caching the results. The boolean ReturnCaptures | |
118 | /// specifies whether returning the value (or part of it) from the function | |
119 | /// counts as capturing it or not. The boolean StoreCaptures specified whether | |
120 | /// storing the value (or part of it) into memory anywhere automatically | |
121 | /// counts as capturing it or not. | |
122 | bool llvm::PointerMayBeCaptured(const Value *V, | |
123 | bool ReturnCaptures, bool StoreCaptures) { | |
124 | assert(!isa<GlobalValue>(V) && | |
125 | "It doesn't make sense to ask whether a global is captured."); | |
126 | ||
127 | // TODO: If StoreCaptures is not true, we could do Fancy analysis | |
128 | // to determine whether this store is not actually an escape point. | |
129 | // In that case, BasicAliasAnalysis should be updated as well to | |
130 | // take advantage of this. | |
131 | (void)StoreCaptures; | |
132 | ||
133 | SimpleCaptureTracker SCT(ReturnCaptures); | |
134 | PointerMayBeCaptured(V, &SCT); | |
135 | return SCT.Captured; | |
136 | } | |
137 | ||
1a4d82fc JJ |
138 | /// PointerMayBeCapturedBefore - Return true if this pointer value may be |
139 | /// captured by the enclosing function (which is required to exist). If a | |
140 | /// DominatorTree is provided, only captures which happen before the given | |
141 | /// instruction are considered. This routine can be expensive, so consider | |
142 | /// caching the results. The boolean ReturnCaptures specifies whether | |
143 | /// returning the value (or part of it) from the function counts as capturing | |
144 | /// it or not. The boolean StoreCaptures specified whether storing the value | |
145 | /// (or part of it) into memory anywhere automatically counts as capturing it | |
146 | /// or not. | |
147 | bool llvm::PointerMayBeCapturedBefore(const Value *V, bool ReturnCaptures, | |
148 | bool StoreCaptures, const Instruction *I, | |
149 | DominatorTree *DT, bool IncludeI) { | |
150 | assert(!isa<GlobalValue>(V) && | |
151 | "It doesn't make sense to ask whether a global is captured."); | |
152 | ||
153 | if (!DT) | |
154 | return PointerMayBeCaptured(V, ReturnCaptures, StoreCaptures); | |
155 | ||
156 | // TODO: See comment in PointerMayBeCaptured regarding what could be done | |
157 | // with StoreCaptures. | |
158 | ||
159 | CapturesBefore CB(ReturnCaptures, I, DT, IncludeI); | |
160 | PointerMayBeCaptured(V, &CB); | |
161 | return CB.Captured; | |
162 | } | |
163 | ||
223e47cc LB |
164 | /// TODO: Write a new FunctionPass AliasAnalysis so that it can keep |
165 | /// a cache. Then we can move the code from BasicAliasAnalysis into | |
166 | /// that path, and remove this threshold. | |
167 | static int const Threshold = 20; | |
168 | ||
169 | void llvm::PointerMayBeCaptured(const Value *V, CaptureTracker *Tracker) { | |
170 | assert(V->getType()->isPointerTy() && "Capture is for pointers only!"); | |
1a4d82fc JJ |
171 | SmallVector<const Use *, Threshold> Worklist; |
172 | SmallSet<const Use *, Threshold> Visited; | |
223e47cc LB |
173 | int Count = 0; |
174 | ||
1a4d82fc | 175 | for (const Use &U : V->uses()) { |
223e47cc LB |
176 | // If there are lots of uses, conservatively say that the value |
177 | // is captured to avoid taking too much compile time. | |
178 | if (Count++ >= Threshold) | |
179 | return Tracker->tooManyUses(); | |
180 | ||
1a4d82fc JJ |
181 | if (!Tracker->shouldExplore(&U)) continue; |
182 | Visited.insert(&U); | |
183 | Worklist.push_back(&U); | |
223e47cc LB |
184 | } |
185 | ||
186 | while (!Worklist.empty()) { | |
1a4d82fc | 187 | const Use *U = Worklist.pop_back_val(); |
223e47cc LB |
188 | Instruction *I = cast<Instruction>(U->getUser()); |
189 | V = U->get(); | |
190 | ||
191 | switch (I->getOpcode()) { | |
192 | case Instruction::Call: | |
193 | case Instruction::Invoke: { | |
194 | CallSite CS(I); | |
195 | // Not captured if the callee is readonly, doesn't return a copy through | |
196 | // its return value and doesn't unwind (a readonly function can leak bits | |
197 | // by throwing an exception or not depending on the input value). | |
198 | if (CS.onlyReadsMemory() && CS.doesNotThrow() && I->getType()->isVoidTy()) | |
199 | break; | |
200 | ||
201 | // Not captured if only passed via 'nocapture' arguments. Note that | |
202 | // calling a function pointer does not in itself cause the pointer to | |
203 | // be captured. This is a subtle point considering that (for example) | |
204 | // the callee might return its own address. It is analogous to saying | |
205 | // that loading a value from a pointer does not cause the pointer to be | |
206 | // captured, even though the loaded value might be the pointer itself | |
207 | // (think of self-referential objects). | |
208 | CallSite::arg_iterator B = CS.arg_begin(), E = CS.arg_end(); | |
209 | for (CallSite::arg_iterator A = B; A != E; ++A) | |
210 | if (A->get() == V && !CS.doesNotCapture(A - B)) | |
211 | // The parameter is not marked 'nocapture' - captured. | |
212 | if (Tracker->captured(U)) | |
213 | return; | |
214 | break; | |
215 | } | |
216 | case Instruction::Load: | |
217 | // Loading from a pointer does not cause it to be captured. | |
218 | break; | |
219 | case Instruction::VAArg: | |
220 | // "va-arg" from a pointer does not cause it to be captured. | |
221 | break; | |
222 | case Instruction::Store: | |
223 | if (V == I->getOperand(0)) | |
224 | // Stored the pointer - conservatively assume it may be captured. | |
225 | if (Tracker->captured(U)) | |
226 | return; | |
227 | // Storing to the pointee does not cause the pointer to be captured. | |
228 | break; | |
229 | case Instruction::BitCast: | |
230 | case Instruction::GetElementPtr: | |
231 | case Instruction::PHI: | |
232 | case Instruction::Select: | |
1a4d82fc | 233 | case Instruction::AddrSpaceCast: |
223e47cc | 234 | // The original value is not captured via this if the new value isn't. |
1a4d82fc JJ |
235 | Count = 0; |
236 | for (Use &UU : I->uses()) { | |
237 | // If there are lots of uses, conservatively say that the value | |
238 | // is captured to avoid taking too much compile time. | |
239 | if (Count++ >= Threshold) | |
240 | return Tracker->tooManyUses(); | |
241 | ||
85aaf69f | 242 | if (Visited.insert(&UU).second) |
1a4d82fc JJ |
243 | if (Tracker->shouldExplore(&UU)) |
244 | Worklist.push_back(&UU); | |
223e47cc LB |
245 | } |
246 | break; | |
247 | case Instruction::ICmp: | |
248 | // Don't count comparisons of a no-alias return value against null as | |
249 | // captures. This allows us to ignore comparisons of malloc results | |
250 | // with null, for example. | |
1a4d82fc JJ |
251 | if (ConstantPointerNull *CPN = |
252 | dyn_cast<ConstantPointerNull>(I->getOperand(1))) | |
253 | if (CPN->getType()->getAddressSpace() == 0) | |
254 | if (isNoAliasCall(V->stripPointerCasts())) | |
223e47cc LB |
255 | break; |
256 | // Otherwise, be conservative. There are crazy ways to capture pointers | |
257 | // using comparisons. | |
258 | if (Tracker->captured(U)) | |
259 | return; | |
260 | break; | |
261 | default: | |
262 | // Something else - be conservative and say it is captured. | |
263 | if (Tracker->captured(U)) | |
264 | return; | |
265 | break; | |
266 | } | |
267 | } | |
268 | ||
269 | // All uses examined. | |
270 | } |