File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/include/llvm/PassAnalysisSupport.h |
Warning: | line 242, column 22 Called C++ object pointer is null |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===-- SafepointIRVerifier.cpp - Verify gc.statepoint invariants ---------===// | |||
2 | // | |||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
4 | // See https://llvm.org/LICENSE.txt for license information. | |||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
6 | // | |||
7 | //===----------------------------------------------------------------------===// | |||
8 | // | |||
9 | // Run a sanity check on the IR to ensure that Safepoints - if they've been | |||
10 | // inserted - were inserted correctly. In particular, look for use of | |||
11 | // non-relocated values after a safepoint. It's primary use is to check the | |||
12 | // correctness of safepoint insertion immediately after insertion, but it can | |||
13 | // also be used to verify that later transforms have not found a way to break | |||
14 | // safepoint semenatics. | |||
15 | // | |||
16 | // In its current form, this verify checks a property which is sufficient, but | |||
17 | // not neccessary for correctness. There are some cases where an unrelocated | |||
18 | // pointer can be used after the safepoint. Consider this example: | |||
19 | // | |||
20 | // a = ... | |||
21 | // b = ... | |||
22 | // (a',b') = safepoint(a,b) | |||
23 | // c = cmp eq a b | |||
24 | // br c, ..., .... | |||
25 | // | |||
26 | // Because it is valid to reorder 'c' above the safepoint, this is legal. In | |||
27 | // practice, this is a somewhat uncommon transform, but CodeGenPrep does create | |||
28 | // idioms like this. The verifier knows about these cases and avoids reporting | |||
29 | // false positives. | |||
30 | // | |||
31 | //===----------------------------------------------------------------------===// | |||
32 | ||||
33 | #include "llvm/IR/SafepointIRVerifier.h" | |||
34 | #include "llvm/ADT/DenseSet.h" | |||
35 | #include "llvm/ADT/PostOrderIterator.h" | |||
36 | #include "llvm/ADT/SetOperations.h" | |||
37 | #include "llvm/ADT/SetVector.h" | |||
38 | #include "llvm/IR/BasicBlock.h" | |||
39 | #include "llvm/IR/Dominators.h" | |||
40 | #include "llvm/IR/Function.h" | |||
41 | #include "llvm/IR/Instructions.h" | |||
42 | #include "llvm/IR/IntrinsicInst.h" | |||
43 | #include "llvm/IR/Intrinsics.h" | |||
44 | #include "llvm/IR/Module.h" | |||
45 | #include "llvm/IR/Statepoint.h" | |||
46 | #include "llvm/IR/Value.h" | |||
47 | #include "llvm/InitializePasses.h" | |||
48 | #include "llvm/Support/Allocator.h" | |||
49 | #include "llvm/Support/CommandLine.h" | |||
50 | #include "llvm/Support/Debug.h" | |||
51 | #include "llvm/Support/raw_ostream.h" | |||
52 | ||||
53 | #define DEBUG_TYPE"safepoint-ir-verifier" "safepoint-ir-verifier" | |||
54 | ||||
55 | using namespace llvm; | |||
56 | ||||
57 | /// This option is used for writing test cases. Instead of crashing the program | |||
58 | /// when verification fails, report a message to the console (for FileCheck | |||
59 | /// usage) and continue execution as if nothing happened. | |||
60 | static cl::opt<bool> PrintOnly("safepoint-ir-verifier-print-only", | |||
61 | cl::init(false)); | |||
62 | ||||
63 | namespace { | |||
64 | ||||
65 | /// This CFG Deadness finds dead blocks and edges. Algorithm starts with a set | |||
66 | /// of blocks unreachable from entry then propagates deadness using foldable | |||
67 | /// conditional branches without modifying CFG. So GVN does but it changes CFG | |||
68 | /// by splitting critical edges. In most cases passes rely on SimplifyCFG to | |||
69 | /// clean up dead blocks, but in some cases, like verification or loop passes | |||
70 | /// it's not possible. | |||
71 | class CFGDeadness { | |||
72 | const DominatorTree *DT = nullptr; | |||
73 | SetVector<const BasicBlock *> DeadBlocks; | |||
74 | SetVector<const Use *> DeadEdges; // Contains all dead edges from live blocks. | |||
75 | ||||
76 | public: | |||
77 | /// Return the edge that coresponds to the predecessor. | |||
78 | static const Use& getEdge(const_pred_iterator &PredIt) { | |||
79 | auto &PU = PredIt.getUse(); | |||
80 | return PU.getUser()->getOperandUse(PU.getOperandNo()); | |||
81 | } | |||
82 | ||||
83 | /// Return true if there is at least one live edge that corresponds to the | |||
84 | /// basic block InBB listed in the phi node. | |||
85 | bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const { | |||
86 | assert(!isDeadBlock(InBB) && "block must be live")((void)0); | |||
87 | const BasicBlock* BB = PN->getParent(); | |||
88 | bool Listed = false; | |||
89 | for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) { | |||
90 | if (InBB == *PredIt) { | |||
91 | if (!isDeadEdge(&getEdge(PredIt))) | |||
92 | return true; | |||
93 | Listed = true; | |||
94 | } | |||
95 | } | |||
96 | (void)Listed; | |||
97 | assert(Listed && "basic block is not found among incoming blocks")((void)0); | |||
98 | return false; | |||
99 | } | |||
100 | ||||
101 | ||||
102 | bool isDeadBlock(const BasicBlock *BB) const { | |||
103 | return DeadBlocks.count(BB); | |||
104 | } | |||
105 | ||||
106 | bool isDeadEdge(const Use *U) const { | |||
107 | assert(cast<Instruction>(U->getUser())->isTerminator() &&((void)0) | |||
108 | "edge must be operand of terminator")((void)0); | |||
109 | assert(cast_or_null<BasicBlock>(U->get()) &&((void)0) | |||
110 | "edge must refer to basic block")((void)0); | |||
111 | assert(!isDeadBlock(cast<Instruction>(U->getUser())->getParent()) &&((void)0) | |||
112 | "isDeadEdge() must be applied to edge from live block")((void)0); | |||
113 | return DeadEdges.count(U); | |||
114 | } | |||
115 | ||||
116 | bool hasLiveIncomingEdges(const BasicBlock *BB) const { | |||
117 | // Check if all incoming edges are dead. | |||
118 | for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) { | |||
119 | auto &PU = PredIt.getUse(); | |||
120 | const Use &U = PU.getUser()->getOperandUse(PU.getOperandNo()); | |||
121 | if (!isDeadBlock(*PredIt) && !isDeadEdge(&U)) | |||
122 | return true; // Found a live edge. | |||
123 | } | |||
124 | return false; | |||
125 | } | |||
126 | ||||
127 | void processFunction(const Function &F, const DominatorTree &DT) { | |||
128 | this->DT = &DT; | |||
129 | ||||
130 | // Start with all blocks unreachable from entry. | |||
131 | for (const BasicBlock &BB : F) | |||
132 | if (!DT.isReachableFromEntry(&BB)) | |||
133 | DeadBlocks.insert(&BB); | |||
134 | ||||
135 | // Top-down walk of the dominator tree | |||
136 | ReversePostOrderTraversal<const Function *> RPOT(&F); | |||
137 | for (const BasicBlock *BB : RPOT) { | |||
138 | const Instruction *TI = BB->getTerminator(); | |||
139 | assert(TI && "blocks must be well formed")((void)0); | |||
140 | ||||
141 | // For conditional branches, we can perform simple conditional propagation on | |||
142 | // the condition value itself. | |||
143 | const BranchInst *BI = dyn_cast<BranchInst>(TI); | |||
144 | if (!BI || !BI->isConditional() || !isa<Constant>(BI->getCondition())) | |||
145 | continue; | |||
146 | ||||
147 | // If a branch has two identical successors, we cannot declare either dead. | |||
148 | if (BI->getSuccessor(0) == BI->getSuccessor(1)) | |||
149 | continue; | |||
150 | ||||
151 | ConstantInt *Cond = dyn_cast<ConstantInt>(BI->getCondition()); | |||
152 | if (!Cond) | |||
153 | continue; | |||
154 | ||||
155 | addDeadEdge(BI->getOperandUse(Cond->getZExtValue() ? 1 : 2)); | |||
156 | } | |||
157 | } | |||
158 | ||||
159 | protected: | |||
160 | void addDeadBlock(const BasicBlock *BB) { | |||
161 | SmallVector<const BasicBlock *, 4> NewDead; | |||
162 | SmallSetVector<const BasicBlock *, 4> DF; | |||
163 | ||||
164 | NewDead.push_back(BB); | |||
165 | while (!NewDead.empty()) { | |||
166 | const BasicBlock *D = NewDead.pop_back_val(); | |||
167 | if (isDeadBlock(D)) | |||
168 | continue; | |||
169 | ||||
170 | // All blocks dominated by D are dead. | |||
171 | SmallVector<BasicBlock *, 8> Dom; | |||
172 | DT->getDescendants(const_cast<BasicBlock*>(D), Dom); | |||
173 | // Do not need to mark all in and out edges dead | |||
174 | // because BB is marked dead and this is enough | |||
175 | // to run further. | |||
176 | DeadBlocks.insert(Dom.begin(), Dom.end()); | |||
177 | ||||
178 | // Figure out the dominance-frontier(D). | |||
179 | for (BasicBlock *B : Dom) | |||
180 | for (BasicBlock *S : successors(B)) | |||
181 | if (!isDeadBlock(S) && !hasLiveIncomingEdges(S)) | |||
182 | NewDead.push_back(S); | |||
183 | } | |||
184 | } | |||
185 | ||||
186 | void addDeadEdge(const Use &DeadEdge) { | |||
187 | if (!DeadEdges.insert(&DeadEdge)) | |||
188 | return; | |||
189 | ||||
190 | BasicBlock *BB = cast_or_null<BasicBlock>(DeadEdge.get()); | |||
191 | if (hasLiveIncomingEdges(BB)) | |||
192 | return; | |||
193 | ||||
194 | addDeadBlock(BB); | |||
195 | } | |||
196 | }; | |||
197 | } // namespace | |||
198 | ||||
199 | static void Verify(const Function &F, const DominatorTree &DT, | |||
200 | const CFGDeadness &CD); | |||
201 | ||||
202 | namespace llvm { | |||
203 | PreservedAnalyses SafepointIRVerifierPass::run(Function &F, | |||
204 | FunctionAnalysisManager &AM) { | |||
205 | const auto &DT = AM.getResult<DominatorTreeAnalysis>(F); | |||
206 | CFGDeadness CD; | |||
207 | CD.processFunction(F, DT); | |||
208 | Verify(F, DT, CD); | |||
209 | return PreservedAnalyses::all(); | |||
210 | } | |||
211 | } // namespace llvm | |||
212 | ||||
213 | namespace { | |||
214 | ||||
215 | struct SafepointIRVerifier : public FunctionPass { | |||
216 | static char ID; // Pass identification, replacement for typeid | |||
217 | SafepointIRVerifier() : FunctionPass(ID) { | |||
218 | initializeSafepointIRVerifierPass(*PassRegistry::getPassRegistry()); | |||
219 | } | |||
220 | ||||
221 | bool runOnFunction(Function &F) override { | |||
222 | auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree(); | |||
223 | CFGDeadness CD; | |||
224 | CD.processFunction(F, DT); | |||
225 | Verify(F, DT, CD); | |||
226 | return false; // no modifications | |||
227 | } | |||
228 | ||||
229 | void getAnalysisUsage(AnalysisUsage &AU) const override { | |||
230 | AU.addRequiredID(DominatorTreeWrapperPass::ID); | |||
231 | AU.setPreservesAll(); | |||
232 | } | |||
233 | ||||
234 | StringRef getPassName() const override { return "safepoint verifier"; } | |||
235 | }; | |||
236 | } // namespace | |||
237 | ||||
238 | void llvm::verifySafepointIR(Function &F) { | |||
239 | SafepointIRVerifier pass; | |||
| ||||
240 | pass.runOnFunction(F); | |||
241 | } | |||
242 | ||||
243 | char SafepointIRVerifier::ID = 0; | |||
244 | ||||
245 | FunctionPass *llvm::createSafepointIRVerifierPass() { | |||
246 | return new SafepointIRVerifier(); | |||
247 | } | |||
248 | ||||
249 | INITIALIZE_PASS_BEGIN(SafepointIRVerifier, "verify-safepoint-ir",static void *initializeSafepointIRVerifierPassOnce(PassRegistry &Registry) { | |||
250 | "Safepoint IR Verifier", false, false)static void *initializeSafepointIRVerifierPassOnce(PassRegistry &Registry) { | |||
251 | INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)initializeDominatorTreeWrapperPassPass(Registry); | |||
252 | INITIALIZE_PASS_END(SafepointIRVerifier, "verify-safepoint-ir",PassInfo *PI = new PassInfo( "Safepoint IR Verifier", "verify-safepoint-ir" , &SafepointIRVerifier::ID, PassInfo::NormalCtor_t(callDefaultCtor <SafepointIRVerifier>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeSafepointIRVerifierPassFlag ; void llvm::initializeSafepointIRVerifierPass(PassRegistry & Registry) { llvm::call_once(InitializeSafepointIRVerifierPassFlag , initializeSafepointIRVerifierPassOnce, std::ref(Registry)); } | |||
253 | "Safepoint IR Verifier", false, false)PassInfo *PI = new PassInfo( "Safepoint IR Verifier", "verify-safepoint-ir" , &SafepointIRVerifier::ID, PassInfo::NormalCtor_t(callDefaultCtor <SafepointIRVerifier>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeSafepointIRVerifierPassFlag ; void llvm::initializeSafepointIRVerifierPass(PassRegistry & Registry) { llvm::call_once(InitializeSafepointIRVerifierPassFlag , initializeSafepointIRVerifierPassOnce, std::ref(Registry)); } | |||
254 | ||||
255 | static bool isGCPointerType(Type *T) { | |||
256 | if (auto *PT = dyn_cast<PointerType>(T)) | |||
257 | // For the sake of this example GC, we arbitrarily pick addrspace(1) as our | |||
258 | // GC managed heap. We know that a pointer into this heap needs to be | |||
259 | // updated and that no other pointer does. | |||
260 | return (1 == PT->getAddressSpace()); | |||
261 | return false; | |||
262 | } | |||
263 | ||||
264 | static bool containsGCPtrType(Type *Ty) { | |||
265 | if (isGCPointerType(Ty)) | |||
266 | return true; | |||
267 | if (VectorType *VT = dyn_cast<VectorType>(Ty)) | |||
268 | return isGCPointerType(VT->getScalarType()); | |||
269 | if (ArrayType *AT = dyn_cast<ArrayType>(Ty)) | |||
270 | return containsGCPtrType(AT->getElementType()); | |||
271 | if (StructType *ST = dyn_cast<StructType>(Ty)) | |||
272 | return llvm::any_of(ST->elements(), containsGCPtrType); | |||
273 | return false; | |||
274 | } | |||
275 | ||||
276 | // Debugging aid -- prints a [Begin, End) range of values. | |||
277 | template<typename IteratorTy> | |||
278 | static void PrintValueSet(raw_ostream &OS, IteratorTy Begin, IteratorTy End) { | |||
279 | OS << "[ "; | |||
280 | while (Begin != End) { | |||
281 | OS << **Begin << " "; | |||
282 | ++Begin; | |||
283 | } | |||
284 | OS << "]"; | |||
285 | } | |||
286 | ||||
287 | /// The verifier algorithm is phrased in terms of availability. The set of | |||
288 | /// values "available" at a given point in the control flow graph is the set of | |||
289 | /// correctly relocated value at that point, and is a subset of the set of | |||
290 | /// definitions dominating that point. | |||
291 | ||||
292 | using AvailableValueSet = DenseSet<const Value *>; | |||
293 | ||||
294 | /// State we compute and track per basic block. | |||
295 | struct BasicBlockState { | |||
296 | // Set of values available coming in, before the phi nodes | |||
297 | AvailableValueSet AvailableIn; | |||
298 | ||||
299 | // Set of values available going out | |||
300 | AvailableValueSet AvailableOut; | |||
301 | ||||
302 | // AvailableOut minus AvailableIn. | |||
303 | // All elements are Instructions | |||
304 | AvailableValueSet Contribution; | |||
305 | ||||
306 | // True if this block contains a safepoint and thus AvailableIn does not | |||
307 | // contribute to AvailableOut. | |||
308 | bool Cleared = false; | |||
309 | }; | |||
310 | ||||
311 | /// A given derived pointer can have multiple base pointers through phi/selects. | |||
312 | /// This type indicates when the base pointer is exclusively constant | |||
313 | /// (ExclusivelySomeConstant), and if that constant is proven to be exclusively | |||
314 | /// null, we record that as ExclusivelyNull. In all other cases, the BaseType is | |||
315 | /// NonConstant. | |||
316 | enum BaseType { | |||
317 | NonConstant = 1, // Base pointers is not exclusively constant. | |||
318 | ExclusivelyNull, | |||
319 | ExclusivelySomeConstant // Base pointers for a given derived pointer is from a | |||
320 | // set of constants, but they are not exclusively | |||
321 | // null. | |||
322 | }; | |||
323 | ||||
324 | /// Return the baseType for Val which states whether Val is exclusively | |||
325 | /// derived from constant/null, or not exclusively derived from constant. | |||
326 | /// Val is exclusively derived off a constant base when all operands of phi and | |||
327 | /// selects are derived off a constant base. | |||
328 | static enum BaseType getBaseType(const Value *Val) { | |||
329 | ||||
330 | SmallVector<const Value *, 32> Worklist; | |||
331 | DenseSet<const Value *> Visited; | |||
332 | bool isExclusivelyDerivedFromNull = true; | |||
333 | Worklist.push_back(Val); | |||
334 | // Strip through all the bitcasts and geps to get base pointer. Also check for | |||
335 | // the exclusive value when there can be multiple base pointers (through phis | |||
336 | // or selects). | |||
337 | while(!Worklist.empty()) { | |||
338 | const Value *V = Worklist.pop_back_val(); | |||
339 | if (!Visited.insert(V).second) | |||
340 | continue; | |||
341 | ||||
342 | if (const auto *CI = dyn_cast<CastInst>(V)) { | |||
343 | Worklist.push_back(CI->stripPointerCasts()); | |||
344 | continue; | |||
345 | } | |||
346 | if (const auto *GEP = dyn_cast<GetElementPtrInst>(V)) { | |||
347 | Worklist.push_back(GEP->getPointerOperand()); | |||
348 | continue; | |||
349 | } | |||
350 | // Push all the incoming values of phi node into the worklist for | |||
351 | // processing. | |||
352 | if (const auto *PN = dyn_cast<PHINode>(V)) { | |||
353 | append_range(Worklist, PN->incoming_values()); | |||
354 | continue; | |||
355 | } | |||
356 | if (const auto *SI = dyn_cast<SelectInst>(V)) { | |||
357 | // Push in the true and false values | |||
358 | Worklist.push_back(SI->getTrueValue()); | |||
359 | Worklist.push_back(SI->getFalseValue()); | |||
360 | continue; | |||
361 | } | |||
362 | if (isa<Constant>(V)) { | |||
363 | // We found at least one base pointer which is non-null, so this derived | |||
364 | // pointer is not exclusively derived from null. | |||
365 | if (V != Constant::getNullValue(V->getType())) | |||
366 | isExclusivelyDerivedFromNull = false; | |||
367 | // Continue processing the remaining values to make sure it's exclusively | |||
368 | // constant. | |||
369 | continue; | |||
370 | } | |||
371 | // At this point, we know that the base pointer is not exclusively | |||
372 | // constant. | |||
373 | return BaseType::NonConstant; | |||
374 | } | |||
375 | // Now, we know that the base pointer is exclusively constant, but we need to | |||
376 | // differentiate between exclusive null constant and non-null constant. | |||
377 | return isExclusivelyDerivedFromNull ? BaseType::ExclusivelyNull | |||
378 | : BaseType::ExclusivelySomeConstant; | |||
379 | } | |||
380 | ||||
381 | static bool isNotExclusivelyConstantDerived(const Value *V) { | |||
382 | return getBaseType(V) == BaseType::NonConstant; | |||
383 | } | |||
384 | ||||
385 | namespace { | |||
386 | class InstructionVerifier; | |||
387 | ||||
388 | /// Builds BasicBlockState for each BB of the function. | |||
389 | /// It can traverse function for verification and provides all required | |||
390 | /// information. | |||
391 | /// | |||
392 | /// GC pointer may be in one of three states: relocated, unrelocated and | |||
393 | /// poisoned. | |||
394 | /// Relocated pointer may be used without any restrictions. | |||
395 | /// Unrelocated pointer cannot be dereferenced, passed as argument to any call | |||
396 | /// or returned. Unrelocated pointer may be safely compared against another | |||
397 | /// unrelocated pointer or against a pointer exclusively derived from null. | |||
398 | /// Poisoned pointers are produced when we somehow derive pointer from relocated | |||
399 | /// and unrelocated pointers (e.g. phi, select). This pointers may be safely | |||
400 | /// used in a very limited number of situations. Currently the only way to use | |||
401 | /// it is comparison against constant exclusively derived from null. All | |||
402 | /// limitations arise due to their undefined state: this pointers should be | |||
403 | /// treated as relocated and unrelocated simultaneously. | |||
404 | /// Rules of deriving: | |||
405 | /// R + U = P - that's where the poisoned pointers come from | |||
406 | /// P + X = P | |||
407 | /// U + U = U | |||
408 | /// R + R = R | |||
409 | /// X + C = X | |||
410 | /// Where "+" - any operation that somehow derive pointer, U - unrelocated, | |||
411 | /// R - relocated and P - poisoned, C - constant, X - U or R or P or C or | |||
412 | /// nothing (in case when "+" is unary operation). | |||
413 | /// Deriving of pointers by itself is always safe. | |||
414 | /// NOTE: when we are making decision on the status of instruction's result: | |||
415 | /// a) for phi we need to check status of each input *at the end of | |||
416 | /// corresponding predecessor BB*. | |||
417 | /// b) for other instructions we need to check status of each input *at the | |||
418 | /// current point*. | |||
419 | /// | |||
420 | /// FIXME: This works fairly well except one case | |||
421 | /// bb1: | |||
422 | /// p = *some GC-ptr def* | |||
423 | /// p1 = gep p, offset | |||
424 | /// / | | |||
425 | /// / | | |||
426 | /// bb2: | | |||
427 | /// safepoint | | |||
428 | /// \ | | |||
429 | /// \ | | |||
430 | /// bb3: | |||
431 | /// p2 = phi [p, bb2] [p1, bb1] | |||
432 | /// p3 = phi [p, bb2] [p, bb1] | |||
433 | /// here p and p1 is unrelocated | |||
434 | /// p2 and p3 is poisoned (though they shouldn't be) | |||
435 | /// | |||
436 | /// This leads to some weird results: | |||
437 | /// cmp eq p, p2 - illegal instruction (false-positive) | |||
438 | /// cmp eq p1, p2 - illegal instruction (false-positive) | |||
439 | /// cmp eq p, p3 - illegal instruction (false-positive) | |||
440 | /// cmp eq p, p1 - ok | |||
441 | /// To fix this we need to introduce conception of generations and be able to | |||
442 | /// check if two values belong to one generation or not. This way p2 will be | |||
443 | /// considered to be unrelocated and no false alarm will happen. | |||
444 | class GCPtrTracker { | |||
445 | const Function &F; | |||
446 | const CFGDeadness &CD; | |||
447 | SpecificBumpPtrAllocator<BasicBlockState> BSAllocator; | |||
448 | DenseMap<const BasicBlock *, BasicBlockState *> BlockMap; | |||
449 | // This set contains defs of unrelocated pointers that are proved to be legal | |||
450 | // and don't need verification. | |||
451 | DenseSet<const Instruction *> ValidUnrelocatedDefs; | |||
452 | // This set contains poisoned defs. They can be safely ignored during | |||
453 | // verification too. | |||
454 | DenseSet<const Value *> PoisonedDefs; | |||
455 | ||||
456 | public: | |||
457 | GCPtrTracker(const Function &F, const DominatorTree &DT, | |||
458 | const CFGDeadness &CD); | |||
459 | ||||
460 | bool hasLiveIncomingEdge(const PHINode *PN, const BasicBlock *InBB) const { | |||
461 | return CD.hasLiveIncomingEdge(PN, InBB); | |||
462 | } | |||
463 | ||||
464 | BasicBlockState *getBasicBlockState(const BasicBlock *BB); | |||
465 | const BasicBlockState *getBasicBlockState(const BasicBlock *BB) const; | |||
466 | ||||
467 | bool isValuePoisoned(const Value *V) const { return PoisonedDefs.count(V); } | |||
468 | ||||
469 | /// Traverse each BB of the function and call | |||
470 | /// InstructionVerifier::verifyInstruction for each possibly invalid | |||
471 | /// instruction. | |||
472 | /// It destructively modifies GCPtrTracker so it's passed via rvalue reference | |||
473 | /// in order to prohibit further usages of GCPtrTracker as it'll be in | |||
474 | /// inconsistent state. | |||
475 | static void verifyFunction(GCPtrTracker &&Tracker, | |||
476 | InstructionVerifier &Verifier); | |||
477 | ||||
478 | /// Returns true for reachable and live blocks. | |||
479 | bool isMapped(const BasicBlock *BB) const { | |||
480 | return BlockMap.find(BB) != BlockMap.end(); | |||
481 | } | |||
482 | ||||
483 | private: | |||
484 | /// Returns true if the instruction may be safely skipped during verification. | |||
485 | bool instructionMayBeSkipped(const Instruction *I) const; | |||
486 | ||||
487 | /// Iterates over all BBs from BlockMap and recalculates AvailableIn/Out for | |||
488 | /// each of them until it converges. | |||
489 | void recalculateBBsStates(); | |||
490 | ||||
491 | /// Remove from Contribution all defs that legally produce unrelocated | |||
492 | /// pointers and saves them to ValidUnrelocatedDefs. | |||
493 | /// Though Contribution should belong to BBS it is passed separately with | |||
494 | /// different const-modifier in order to emphasize (and guarantee) that only | |||
495 | /// Contribution will be changed. | |||
496 | /// Returns true if Contribution was changed otherwise false. | |||
497 | bool removeValidUnrelocatedDefs(const BasicBlock *BB, | |||
498 | const BasicBlockState *BBS, | |||
499 | AvailableValueSet &Contribution); | |||
500 | ||||
501 | /// Gather all the definitions dominating the start of BB into Result. This is | |||
502 | /// simply the defs introduced by every dominating basic block and the | |||
503 | /// function arguments. | |||
504 | void gatherDominatingDefs(const BasicBlock *BB, AvailableValueSet &Result, | |||
505 | const DominatorTree &DT); | |||
506 | ||||
507 | /// Compute the AvailableOut set for BB, based on the BasicBlockState BBS, | |||
508 | /// which is the BasicBlockState for BB. | |||
509 | /// ContributionChanged is set when the verifier runs for the first time | |||
510 | /// (in this case Contribution was changed from 'empty' to its initial state) | |||
511 | /// or when Contribution of this BB was changed since last computation. | |||
512 | static void transferBlock(const BasicBlock *BB, BasicBlockState &BBS, | |||
513 | bool ContributionChanged); | |||
514 | ||||
515 | /// Model the effect of an instruction on the set of available values. | |||
516 | static void transferInstruction(const Instruction &I, bool &Cleared, | |||
517 | AvailableValueSet &Available); | |||
518 | }; | |||
519 | ||||
520 | /// It is a visitor for GCPtrTracker::verifyFunction. It decides if the | |||
521 | /// instruction (which uses heap reference) is legal or not, given our safepoint | |||
522 | /// semantics. | |||
523 | class InstructionVerifier { | |||
524 | bool AnyInvalidUses = false; | |||
525 | ||||
526 | public: | |||
527 | void verifyInstruction(const GCPtrTracker *Tracker, const Instruction &I, | |||
528 | const AvailableValueSet &AvailableSet); | |||
529 | ||||
530 | bool hasAnyInvalidUses() const { return AnyInvalidUses; } | |||
531 | ||||
532 | private: | |||
533 | void reportInvalidUse(const Value &V, const Instruction &I); | |||
534 | }; | |||
535 | } // end anonymous namespace | |||
536 | ||||
537 | GCPtrTracker::GCPtrTracker(const Function &F, const DominatorTree &DT, | |||
538 | const CFGDeadness &CD) : F(F), CD(CD) { | |||
539 | // Calculate Contribution of each live BB. | |||
540 | // Allocate BB states for live blocks. | |||
541 | for (const BasicBlock &BB : F) | |||
542 | if (!CD.isDeadBlock(&BB)) { | |||
543 | BasicBlockState *BBS = new (BSAllocator.Allocate()) BasicBlockState; | |||
544 | for (const auto &I : BB) | |||
545 | transferInstruction(I, BBS->Cleared, BBS->Contribution); | |||
546 | BlockMap[&BB] = BBS; | |||
547 | } | |||
548 | ||||
549 | // Initialize AvailableIn/Out sets of each BB using only information about | |||
550 | // dominating BBs. | |||
551 | for (auto &BBI : BlockMap) { | |||
552 | gatherDominatingDefs(BBI.first, BBI.second->AvailableIn, DT); | |||
553 | transferBlock(BBI.first, *BBI.second, true); | |||
554 | } | |||
555 | ||||
556 | // Simulate the flow of defs through the CFG and recalculate AvailableIn/Out | |||
557 | // sets of each BB until it converges. If any def is proved to be an | |||
558 | // unrelocated pointer, it will be removed from all BBSs. | |||
559 | recalculateBBsStates(); | |||
560 | } | |||
561 | ||||
562 | BasicBlockState *GCPtrTracker::getBasicBlockState(const BasicBlock *BB) { | |||
563 | return BlockMap.lookup(BB); | |||
564 | } | |||
565 | ||||
566 | const BasicBlockState *GCPtrTracker::getBasicBlockState( | |||
567 | const BasicBlock *BB) const { | |||
568 | return const_cast<GCPtrTracker *>(this)->getBasicBlockState(BB); | |||
569 | } | |||
570 | ||||
571 | bool GCPtrTracker::instructionMayBeSkipped(const Instruction *I) const { | |||
572 | // Poisoned defs are skipped since they are always safe by itself by | |||
573 | // definition (for details see comment to this class). | |||
574 | return ValidUnrelocatedDefs.count(I) || PoisonedDefs.count(I); | |||
575 | } | |||
576 | ||||
577 | void GCPtrTracker::verifyFunction(GCPtrTracker &&Tracker, | |||
578 | InstructionVerifier &Verifier) { | |||
579 | // We need RPO here to a) report always the first error b) report errors in | |||
580 | // same order from run to run. | |||
581 | ReversePostOrderTraversal<const Function *> RPOT(&Tracker.F); | |||
582 | for (const BasicBlock *BB : RPOT) { | |||
583 | BasicBlockState *BBS = Tracker.getBasicBlockState(BB); | |||
584 | if (!BBS) | |||
585 | continue; | |||
586 | ||||
587 | // We destructively modify AvailableIn as we traverse the block instruction | |||
588 | // by instruction. | |||
589 | AvailableValueSet &AvailableSet = BBS->AvailableIn; | |||
590 | for (const Instruction &I : *BB) { | |||
591 | if (Tracker.instructionMayBeSkipped(&I)) | |||
592 | continue; // This instruction shouldn't be added to AvailableSet. | |||
593 | ||||
594 | Verifier.verifyInstruction(&Tracker, I, AvailableSet); | |||
595 | ||||
596 | // Model the effect of current instruction on AvailableSet to keep the set | |||
597 | // relevant at each point of BB. | |||
598 | bool Cleared = false; | |||
599 | transferInstruction(I, Cleared, AvailableSet); | |||
600 | (void)Cleared; | |||
601 | } | |||
602 | } | |||
603 | } | |||
604 | ||||
605 | void GCPtrTracker::recalculateBBsStates() { | |||
606 | SetVector<const BasicBlock *> Worklist; | |||
607 | // TODO: This order is suboptimal, it's better to replace it with priority | |||
608 | // queue where priority is RPO number of BB. | |||
609 | for (auto &BBI : BlockMap) | |||
610 | Worklist.insert(BBI.first); | |||
611 | ||||
612 | // This loop iterates the AvailableIn/Out sets until it converges. | |||
613 | // The AvailableIn and AvailableOut sets decrease as we iterate. | |||
614 | while (!Worklist.empty()) { | |||
615 | const BasicBlock *BB = Worklist.pop_back_val(); | |||
616 | BasicBlockState *BBS = getBasicBlockState(BB); | |||
617 | if (!BBS) | |||
618 | continue; // Ignore dead successors. | |||
619 | ||||
620 | size_t OldInCount = BBS->AvailableIn.size(); | |||
621 | for (const_pred_iterator PredIt(BB), End(BB, true); PredIt != End; ++PredIt) { | |||
622 | const BasicBlock *PBB = *PredIt; | |||
623 | BasicBlockState *PBBS = getBasicBlockState(PBB); | |||
624 | if (PBBS && !CD.isDeadEdge(&CFGDeadness::getEdge(PredIt))) | |||
625 | set_intersect(BBS->AvailableIn, PBBS->AvailableOut); | |||
626 | } | |||
627 | ||||
628 | assert(OldInCount >= BBS->AvailableIn.size() && "invariant!")((void)0); | |||
629 | ||||
630 | bool InputsChanged = OldInCount != BBS->AvailableIn.size(); | |||
631 | bool ContributionChanged = | |||
632 | removeValidUnrelocatedDefs(BB, BBS, BBS->Contribution); | |||
633 | if (!InputsChanged && !ContributionChanged) | |||
634 | continue; | |||
635 | ||||
636 | size_t OldOutCount = BBS->AvailableOut.size(); | |||
637 | transferBlock(BB, *BBS, ContributionChanged); | |||
638 | if (OldOutCount != BBS->AvailableOut.size()) { | |||
639 | assert(OldOutCount > BBS->AvailableOut.size() && "invariant!")((void)0); | |||
640 | Worklist.insert(succ_begin(BB), succ_end(BB)); | |||
641 | } | |||
642 | } | |||
643 | } | |||
644 | ||||
645 | bool GCPtrTracker::removeValidUnrelocatedDefs(const BasicBlock *BB, | |||
646 | const BasicBlockState *BBS, | |||
647 | AvailableValueSet &Contribution) { | |||
648 | assert(&BBS->Contribution == &Contribution &&((void)0) | |||
649 | "Passed Contribution should be from the passed BasicBlockState!")((void)0); | |||
650 | AvailableValueSet AvailableSet = BBS->AvailableIn; | |||
651 | bool ContributionChanged = false; | |||
652 | // For explanation why instructions are processed this way see | |||
653 | // "Rules of deriving" in the comment to this class. | |||
654 | for (const Instruction &I : *BB) { | |||
655 | bool ValidUnrelocatedPointerDef = false; | |||
656 | bool PoisonedPointerDef = false; | |||
657 | // TODO: `select` instructions should be handled here too. | |||
658 | if (const PHINode *PN = dyn_cast<PHINode>(&I)) { | |||
659 | if (containsGCPtrType(PN->getType())) { | |||
660 | // If both is true, output is poisoned. | |||
661 | bool HasRelocatedInputs = false; | |||
662 | bool HasUnrelocatedInputs = false; | |||
663 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { | |||
664 | const BasicBlock *InBB = PN->getIncomingBlock(i); | |||
665 | if (!isMapped(InBB) || | |||
666 | !CD.hasLiveIncomingEdge(PN, InBB)) | |||
667 | continue; // Skip dead block or dead edge. | |||
668 | ||||
669 | const Value *InValue = PN->getIncomingValue(i); | |||
670 | ||||
671 | if (isNotExclusivelyConstantDerived(InValue)) { | |||
672 | if (isValuePoisoned(InValue)) { | |||
673 | // If any of inputs is poisoned, output is always poisoned too. | |||
674 | HasRelocatedInputs = true; | |||
675 | HasUnrelocatedInputs = true; | |||
676 | break; | |||
677 | } | |||
678 | if (BlockMap[InBB]->AvailableOut.count(InValue)) | |||
679 | HasRelocatedInputs = true; | |||
680 | else | |||
681 | HasUnrelocatedInputs = true; | |||
682 | } | |||
683 | } | |||
684 | if (HasUnrelocatedInputs) { | |||
685 | if (HasRelocatedInputs) | |||
686 | PoisonedPointerDef = true; | |||
687 | else | |||
688 | ValidUnrelocatedPointerDef = true; | |||
689 | } | |||
690 | } | |||
691 | } else if ((isa<GetElementPtrInst>(I) || isa<BitCastInst>(I)) && | |||
692 | containsGCPtrType(I.getType())) { | |||
693 | // GEP/bitcast of unrelocated pointer is legal by itself but this def | |||
694 | // shouldn't appear in any AvailableSet. | |||
695 | for (const Value *V : I.operands()) | |||
696 | if (containsGCPtrType(V->getType()) && | |||
697 | isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) { | |||
698 | if (isValuePoisoned(V)) | |||
699 | PoisonedPointerDef = true; | |||
700 | else | |||
701 | ValidUnrelocatedPointerDef = true; | |||
702 | break; | |||
703 | } | |||
704 | } | |||
705 | assert(!(ValidUnrelocatedPointerDef && PoisonedPointerDef) &&((void)0) | |||
706 | "Value cannot be both unrelocated and poisoned!")((void)0); | |||
707 | if (ValidUnrelocatedPointerDef) { | |||
708 | // Remove def of unrelocated pointer from Contribution of this BB and | |||
709 | // trigger update of all its successors. | |||
710 | Contribution.erase(&I); | |||
711 | PoisonedDefs.erase(&I); | |||
712 | ValidUnrelocatedDefs.insert(&I); | |||
713 | LLVM_DEBUG(dbgs() << "Removing urelocated " << Ido { } while (false) | |||
714 | << " from Contribution of " << BB->getName() << "\n")do { } while (false); | |||
715 | ContributionChanged = true; | |||
716 | } else if (PoisonedPointerDef) { | |||
717 | // Mark pointer as poisoned, remove its def from Contribution and trigger | |||
718 | // update of all successors. | |||
719 | Contribution.erase(&I); | |||
720 | PoisonedDefs.insert(&I); | |||
721 | LLVM_DEBUG(dbgs() << "Removing poisoned " << I << " from Contribution of "do { } while (false) | |||
722 | << BB->getName() << "\n")do { } while (false); | |||
723 | ContributionChanged = true; | |||
724 | } else { | |||
725 | bool Cleared = false; | |||
726 | transferInstruction(I, Cleared, AvailableSet); | |||
727 | (void)Cleared; | |||
728 | } | |||
729 | } | |||
730 | return ContributionChanged; | |||
731 | } | |||
732 | ||||
733 | void GCPtrTracker::gatherDominatingDefs(const BasicBlock *BB, | |||
734 | AvailableValueSet &Result, | |||
735 | const DominatorTree &DT) { | |||
736 | DomTreeNode *DTN = DT[const_cast<BasicBlock *>(BB)]; | |||
737 | ||||
738 | assert(DTN && "Unreachable blocks are ignored")((void)0); | |||
739 | while (DTN->getIDom()) { | |||
740 | DTN = DTN->getIDom(); | |||
741 | auto BBS = getBasicBlockState(DTN->getBlock()); | |||
742 | assert(BBS && "immediate dominator cannot be dead for a live block")((void)0); | |||
743 | const auto &Defs = BBS->Contribution; | |||
744 | Result.insert(Defs.begin(), Defs.end()); | |||
745 | // If this block is 'Cleared', then nothing LiveIn to this block can be | |||
746 | // available after this block completes. Note: This turns out to be | |||
747 | // really important for reducing memory consuption of the initial available | |||
748 | // sets and thus peak memory usage by this verifier. | |||
749 | if (BBS->Cleared) | |||
750 | return; | |||
751 | } | |||
752 | ||||
753 | for (const Argument &A : BB->getParent()->args()) | |||
754 | if (containsGCPtrType(A.getType())) | |||
755 | Result.insert(&A); | |||
756 | } | |||
757 | ||||
758 | void GCPtrTracker::transferBlock(const BasicBlock *BB, BasicBlockState &BBS, | |||
759 | bool ContributionChanged) { | |||
760 | const AvailableValueSet &AvailableIn = BBS.AvailableIn; | |||
761 | AvailableValueSet &AvailableOut = BBS.AvailableOut; | |||
762 | ||||
763 | if (BBS.Cleared) { | |||
764 | // AvailableOut will change only when Contribution changed. | |||
765 | if (ContributionChanged) | |||
766 | AvailableOut = BBS.Contribution; | |||
767 | } else { | |||
768 | // Otherwise, we need to reduce the AvailableOut set by things which are no | |||
769 | // longer in our AvailableIn | |||
770 | AvailableValueSet Temp = BBS.Contribution; | |||
771 | set_union(Temp, AvailableIn); | |||
772 | AvailableOut = std::move(Temp); | |||
773 | } | |||
774 | ||||
775 | LLVM_DEBUG(dbgs() << "Transfered block " << BB->getName() << " from ";do { } while (false) | |||
776 | PrintValueSet(dbgs(), AvailableIn.begin(), AvailableIn.end());do { } while (false) | |||
777 | dbgs() << " to ";do { } while (false) | |||
778 | PrintValueSet(dbgs(), AvailableOut.begin(), AvailableOut.end());do { } while (false) | |||
779 | dbgs() << "\n";)do { } while (false); | |||
780 | } | |||
781 | ||||
782 | void GCPtrTracker::transferInstruction(const Instruction &I, bool &Cleared, | |||
783 | AvailableValueSet &Available) { | |||
784 | if (isa<GCStatepointInst>(I)) { | |||
785 | Cleared = true; | |||
786 | Available.clear(); | |||
787 | } else if (containsGCPtrType(I.getType())) | |||
788 | Available.insert(&I); | |||
789 | } | |||
790 | ||||
791 | void InstructionVerifier::verifyInstruction( | |||
792 | const GCPtrTracker *Tracker, const Instruction &I, | |||
793 | const AvailableValueSet &AvailableSet) { | |||
794 | if (const PHINode *PN = dyn_cast<PHINode>(&I)) { | |||
795 | if (containsGCPtrType(PN->getType())) | |||
796 | for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i) { | |||
797 | const BasicBlock *InBB = PN->getIncomingBlock(i); | |||
798 | const BasicBlockState *InBBS = Tracker->getBasicBlockState(InBB); | |||
799 | if (!InBBS || | |||
800 | !Tracker->hasLiveIncomingEdge(PN, InBB)) | |||
801 | continue; // Skip dead block or dead edge. | |||
802 | ||||
803 | const Value *InValue = PN->getIncomingValue(i); | |||
804 | ||||
805 | if (isNotExclusivelyConstantDerived(InValue) && | |||
806 | !InBBS->AvailableOut.count(InValue)) | |||
807 | reportInvalidUse(*InValue, *PN); | |||
808 | } | |||
809 | } else if (isa<CmpInst>(I) && | |||
810 | containsGCPtrType(I.getOperand(0)->getType())) { | |||
811 | Value *LHS = I.getOperand(0), *RHS = I.getOperand(1); | |||
812 | enum BaseType baseTyLHS = getBaseType(LHS), | |||
813 | baseTyRHS = getBaseType(RHS); | |||
814 | ||||
815 | // Returns true if LHS and RHS are unrelocated pointers and they are | |||
816 | // valid unrelocated uses. | |||
817 | auto hasValidUnrelocatedUse = [&AvailableSet, Tracker, baseTyLHS, baseTyRHS, | |||
818 | &LHS, &RHS] () { | |||
819 | // A cmp instruction has valid unrelocated pointer operands only if | |||
820 | // both operands are unrelocated pointers. | |||
821 | // In the comparison between two pointers, if one is an unrelocated | |||
822 | // use, the other *should be* an unrelocated use, for this | |||
823 | // instruction to contain valid unrelocated uses. This unrelocated | |||
824 | // use can be a null constant as well, or another unrelocated | |||
825 | // pointer. | |||
826 | if (AvailableSet.count(LHS) || AvailableSet.count(RHS)) | |||
827 | return false; | |||
828 | // Constant pointers (that are not exclusively null) may have | |||
829 | // meaning in different VMs, so we cannot reorder the compare | |||
830 | // against constant pointers before the safepoint. In other words, | |||
831 | // comparison of an unrelocated use against a non-null constant | |||
832 | // maybe invalid. | |||
833 | if ((baseTyLHS == BaseType::ExclusivelySomeConstant && | |||
834 | baseTyRHS == BaseType::NonConstant) || | |||
835 | (baseTyLHS == BaseType::NonConstant && | |||
836 | baseTyRHS == BaseType::ExclusivelySomeConstant)) | |||
837 | return false; | |||
838 | ||||
839 | // If one of pointers is poisoned and other is not exclusively derived | |||
840 | // from null it is an invalid expression: it produces poisoned result | |||
841 | // and unless we want to track all defs (not only gc pointers) the only | |||
842 | // option is to prohibit such instructions. | |||
843 | if ((Tracker->isValuePoisoned(LHS) && baseTyRHS != ExclusivelyNull) || | |||
844 | (Tracker->isValuePoisoned(RHS) && baseTyLHS != ExclusivelyNull)) | |||
845 | return false; | |||
846 | ||||
847 | // All other cases are valid cases enumerated below: | |||
848 | // 1. Comparison between an exclusively derived null pointer and a | |||
849 | // constant base pointer. | |||
850 | // 2. Comparison between an exclusively derived null pointer and a | |||
851 | // non-constant unrelocated base pointer. | |||
852 | // 3. Comparison between 2 unrelocated pointers. | |||
853 | // 4. Comparison between a pointer exclusively derived from null and a | |||
854 | // non-constant poisoned pointer. | |||
855 | return true; | |||
856 | }; | |||
857 | if (!hasValidUnrelocatedUse()) { | |||
858 | // Print out all non-constant derived pointers that are unrelocated | |||
859 | // uses, which are invalid. | |||
860 | if (baseTyLHS == BaseType::NonConstant && !AvailableSet.count(LHS)) | |||
861 | reportInvalidUse(*LHS, I); | |||
862 | if (baseTyRHS == BaseType::NonConstant && !AvailableSet.count(RHS)) | |||
863 | reportInvalidUse(*RHS, I); | |||
864 | } | |||
865 | } else { | |||
866 | for (const Value *V : I.operands()) | |||
867 | if (containsGCPtrType(V->getType()) && | |||
868 | isNotExclusivelyConstantDerived(V) && !AvailableSet.count(V)) | |||
869 | reportInvalidUse(*V, I); | |||
870 | } | |||
871 | } | |||
872 | ||||
873 | void InstructionVerifier::reportInvalidUse(const Value &V, | |||
874 | const Instruction &I) { | |||
875 | errs() << "Illegal use of unrelocated value found!\n"; | |||
876 | errs() << "Def: " << V << "\n"; | |||
877 | errs() << "Use: " << I << "\n"; | |||
878 | if (!PrintOnly) | |||
879 | abort(); | |||
880 | AnyInvalidUses = true; | |||
881 | } | |||
882 | ||||
883 | static void Verify(const Function &F, const DominatorTree &DT, | |||
884 | const CFGDeadness &CD) { | |||
885 | LLVM_DEBUG(dbgs() << "Verifying gc pointers in function: " << F.getName()do { } while (false) | |||
886 | << "\n")do { } while (false); | |||
887 | if (PrintOnly) | |||
888 | dbgs() << "Verifying gc pointers in function: " << F.getName() << "\n"; | |||
889 | ||||
890 | GCPtrTracker Tracker(F, DT, CD); | |||
891 | ||||
892 | // We now have all the information we need to decide if the use of a heap | |||
893 | // reference is legal or not, given our safepoint semantics. | |||
894 | ||||
895 | InstructionVerifier Verifier; | |||
896 | GCPtrTracker::verifyFunction(std::move(Tracker), Verifier); | |||
897 | ||||
898 | if (PrintOnly && !Verifier.hasAnyInvalidUses()) { | |||
899 | dbgs() << "No illegal uses found by SafepointIRVerifier in: " << F.getName() | |||
900 | << "\n"; | |||
901 | } | |||
902 | } |
1 | //===- llvm/Pass.h - Base class for Passes ----------------------*- C++ -*-===// |
2 | // |
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
4 | // See https://llvm.org/LICENSE.txt for license information. |
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
6 | // |
7 | //===----------------------------------------------------------------------===// |
8 | // |
9 | // This file defines a base class that indicates that a specified class is a |
10 | // transformation pass implementation. |
11 | // |
12 | // Passes are designed this way so that it is possible to run passes in a cache |
13 | // and organizationally optimal order without having to specify it at the front |
14 | // end. This allows arbitrary passes to be strung together and have them |
15 | // executed as efficiently as possible. |
16 | // |
17 | // Passes should extend one of the classes below, depending on the guarantees |
18 | // that it can make about what will be modified as it is run. For example, most |
19 | // global optimizations should derive from FunctionPass, because they do not add |
20 | // or delete functions, they operate on the internals of the function. |
21 | // |
22 | // Note that this file #includes PassSupport.h and PassAnalysisSupport.h (at the |
23 | // bottom), so the APIs exposed by these files are also automatically available |
24 | // to all users of this file. |
25 | // |
26 | //===----------------------------------------------------------------------===// |
27 | |
28 | #ifndef LLVM_PASS_H |
29 | #define LLVM_PASS_H |
30 | |
31 | #include <string> |
32 | |
33 | namespace llvm { |
34 | |
35 | class AnalysisResolver; |
36 | class AnalysisUsage; |
37 | class Function; |
38 | class ImmutablePass; |
39 | class Module; |
40 | class PassInfo; |
41 | class PMDataManager; |
42 | class PMStack; |
43 | class raw_ostream; |
44 | class StringRef; |
45 | |
46 | // AnalysisID - Use the PassInfo to identify a pass... |
47 | using AnalysisID = const void *; |
48 | |
49 | /// Different types of internal pass managers. External pass managers |
50 | /// (PassManager and FunctionPassManager) are not represented here. |
51 | /// Ordering of pass manager types is important here. |
52 | enum PassManagerType { |
53 | PMT_Unknown = 0, |
54 | PMT_ModulePassManager = 1, ///< MPPassManager |
55 | PMT_CallGraphPassManager, ///< CGPassManager |
56 | PMT_FunctionPassManager, ///< FPPassManager |
57 | PMT_LoopPassManager, ///< LPPassManager |
58 | PMT_RegionPassManager, ///< RGPassManager |
59 | PMT_Last |
60 | }; |
61 | |
62 | // Different types of passes. |
63 | enum PassKind { |
64 | PT_Region, |
65 | PT_Loop, |
66 | PT_Function, |
67 | PT_CallGraphSCC, |
68 | PT_Module, |
69 | PT_PassManager |
70 | }; |
71 | |
72 | /// This enumerates the LLVM full LTO or ThinLTO optimization phases. |
73 | enum class ThinOrFullLTOPhase { |
74 | /// No LTO/ThinLTO behavior needed. |
75 | None, |
76 | /// ThinLTO prelink (summary) phase. |
77 | ThinLTOPreLink, |
78 | /// ThinLTO postlink (backend compile) phase. |
79 | ThinLTOPostLink, |
80 | /// Full LTO prelink phase. |
81 | FullLTOPreLink, |
82 | /// Full LTO postlink (backend compile) phase. |
83 | FullLTOPostLink |
84 | }; |
85 | |
86 | //===----------------------------------------------------------------------===// |
87 | /// Pass interface - Implemented by all 'passes'. Subclass this if you are an |
88 | /// interprocedural optimization or you do not fit into any of the more |
89 | /// constrained passes described below. |
90 | /// |
91 | class Pass { |
92 | AnalysisResolver *Resolver = nullptr; // Used to resolve analysis |
93 | const void *PassID; |
94 | PassKind Kind; |
95 | |
96 | public: |
97 | explicit Pass(PassKind K, char &pid) : PassID(&pid), Kind(K) {} |
98 | Pass(const Pass &) = delete; |
99 | Pass &operator=(const Pass &) = delete; |
100 | virtual ~Pass(); |
101 | |
102 | PassKind getPassKind() const { return Kind; } |
103 | |
104 | /// getPassName - Return a nice clean name for a pass. This usually |
105 | /// implemented in terms of the name that is registered by one of the |
106 | /// Registration templates, but can be overloaded directly. |
107 | virtual StringRef getPassName() const; |
108 | |
109 | /// getPassID - Return the PassID number that corresponds to this pass. |
110 | AnalysisID getPassID() const { |
111 | return PassID; |
112 | } |
113 | |
114 | /// doInitialization - Virtual method overridden by subclasses to do |
115 | /// any necessary initialization before any pass is run. |
116 | virtual bool doInitialization(Module &) { return false; } |
117 | |
118 | /// doFinalization - Virtual method overriden by subclasses to do any |
119 | /// necessary clean up after all passes have run. |
120 | virtual bool doFinalization(Module &) { return false; } |
121 | |
122 | /// print - Print out the internal state of the pass. This is called by |
123 | /// Analyze to print out the contents of an analysis. Otherwise it is not |
124 | /// necessary to implement this method. Beware that the module pointer MAY be |
125 | /// null. This automatically forwards to a virtual function that does not |
126 | /// provide the Module* in case the analysis doesn't need it it can just be |
127 | /// ignored. |
128 | virtual void print(raw_ostream &OS, const Module *M) const; |
129 | |
130 | void dump() const; // dump - Print to stderr. |
131 | |
132 | /// createPrinterPass - Get a Pass appropriate to print the IR this |
133 | /// pass operates on (Module, Function or MachineFunction). |
134 | virtual Pass *createPrinterPass(raw_ostream &OS, |
135 | const std::string &Banner) const = 0; |
136 | |
137 | /// Each pass is responsible for assigning a pass manager to itself. |
138 | /// PMS is the stack of available pass manager. |
139 | virtual void assignPassManager(PMStack &, |
140 | PassManagerType) {} |
141 | |
142 | /// Check if available pass managers are suitable for this pass or not. |
143 | virtual void preparePassManager(PMStack &); |
144 | |
145 | /// Return what kind of Pass Manager can manage this pass. |
146 | virtual PassManagerType getPotentialPassManagerType() const; |
147 | |
148 | // Access AnalysisResolver |
149 | void setResolver(AnalysisResolver *AR); |
150 | AnalysisResolver *getResolver() const { return Resolver; } |
151 | |
152 | /// getAnalysisUsage - This function should be overriden by passes that need |
153 | /// analysis information to do their job. If a pass specifies that it uses a |
154 | /// particular analysis result to this function, it can then use the |
155 | /// getAnalysis<AnalysisType>() function, below. |
156 | virtual void getAnalysisUsage(AnalysisUsage &) const; |
157 | |
158 | /// releaseMemory() - This member can be implemented by a pass if it wants to |
159 | /// be able to release its memory when it is no longer needed. The default |
160 | /// behavior of passes is to hold onto memory for the entire duration of their |
161 | /// lifetime (which is the entire compile time). For pipelined passes, this |
162 | /// is not a big deal because that memory gets recycled every time the pass is |
163 | /// invoked on another program unit. For IP passes, it is more important to |
164 | /// free memory when it is unused. |
165 | /// |
166 | /// Optionally implement this function to release pass memory when it is no |
167 | /// longer used. |
168 | virtual void releaseMemory(); |
169 | |
170 | /// getAdjustedAnalysisPointer - This method is used when a pass implements |
171 | /// an analysis interface through multiple inheritance. If needed, it should |
172 | /// override this to adjust the this pointer as needed for the specified pass |
173 | /// info. |
174 | virtual void *getAdjustedAnalysisPointer(AnalysisID ID); |
175 | virtual ImmutablePass *getAsImmutablePass(); |
176 | virtual PMDataManager *getAsPMDataManager(); |
177 | |
178 | /// verifyAnalysis() - This member can be implemented by a analysis pass to |
179 | /// check state of analysis information. |
180 | virtual void verifyAnalysis() const; |
181 | |
182 | // dumpPassStructure - Implement the -debug-passes=PassStructure option |
183 | virtual void dumpPassStructure(unsigned Offset = 0); |
184 | |
185 | // lookupPassInfo - Return the pass info object for the specified pass class, |
186 | // or null if it is not known. |
187 | static const PassInfo *lookupPassInfo(const void *TI); |
188 | |
189 | // lookupPassInfo - Return the pass info object for the pass with the given |
190 | // argument string, or null if it is not known. |
191 | static const PassInfo *lookupPassInfo(StringRef Arg); |
192 | |
193 | // createPass - Create a object for the specified pass class, |
194 | // or null if it is not known. |
195 | static Pass *createPass(AnalysisID ID); |
196 | |
197 | /// getAnalysisIfAvailable<AnalysisType>() - Subclasses use this function to |
198 | /// get analysis information that might be around, for example to update it. |
199 | /// This is different than getAnalysis in that it can fail (if the analysis |
200 | /// results haven't been computed), so should only be used if you can handle |
201 | /// the case when the analysis is not available. This method is often used by |
202 | /// transformation APIs to update analysis results for a pass automatically as |
203 | /// the transform is performed. |
204 | template<typename AnalysisType> AnalysisType * |
205 | getAnalysisIfAvailable() const; // Defined in PassAnalysisSupport.h |
206 | |
207 | /// mustPreserveAnalysisID - This method serves the same function as |
208 | /// getAnalysisIfAvailable, but works if you just have an AnalysisID. This |
209 | /// obviously cannot give you a properly typed instance of the class if you |
210 | /// don't have the class name available (use getAnalysisIfAvailable if you |
211 | /// do), but it can tell you if you need to preserve the pass at least. |
212 | bool mustPreserveAnalysisID(char &AID) const; |
213 | |
214 | /// getAnalysis<AnalysisType>() - This function is used by subclasses to get |
215 | /// to the analysis information that they claim to use by overriding the |
216 | /// getAnalysisUsage function. |
217 | template<typename AnalysisType> |
218 | AnalysisType &getAnalysis() const; // Defined in PassAnalysisSupport.h |
219 | |
220 | template <typename AnalysisType> |
221 | AnalysisType & |
222 | getAnalysis(Function &F, |
223 | bool *Changed = nullptr); // Defined in PassAnalysisSupport.h |
224 | |
225 | template<typename AnalysisType> |
226 | AnalysisType &getAnalysisID(AnalysisID PI) const; |
227 | |
228 | template <typename AnalysisType> |
229 | AnalysisType &getAnalysisID(AnalysisID PI, Function &F, |
230 | bool *Changed = nullptr); |
231 | }; |
232 | |
233 | //===----------------------------------------------------------------------===// |
234 | /// ModulePass class - This class is used to implement unstructured |
235 | /// interprocedural optimizations and analyses. ModulePasses may do anything |
236 | /// they want to the program. |
237 | /// |
238 | class ModulePass : public Pass { |
239 | public: |
240 | explicit ModulePass(char &pid) : Pass(PT_Module, pid) {} |
241 | |
242 | // Force out-of-line virtual method. |
243 | ~ModulePass() override; |
244 | |
245 | /// createPrinterPass - Get a module printer pass. |
246 | Pass *createPrinterPass(raw_ostream &OS, |
247 | const std::string &Banner) const override; |
248 | |
249 | /// runOnModule - Virtual method overriden by subclasses to process the module |
250 | /// being operated on. |
251 | virtual bool runOnModule(Module &M) = 0; |
252 | |
253 | void assignPassManager(PMStack &PMS, PassManagerType T) override; |
254 | |
255 | /// Return what kind of Pass Manager can manage this pass. |
256 | PassManagerType getPotentialPassManagerType() const override; |
257 | |
258 | protected: |
259 | /// Optional passes call this function to check whether the pass should be |
260 | /// skipped. This is the case when optimization bisect is over the limit. |
261 | bool skipModule(Module &M) const; |
262 | }; |
263 | |
264 | //===----------------------------------------------------------------------===// |
265 | /// ImmutablePass class - This class is used to provide information that does |
266 | /// not need to be run. This is useful for things like target information and |
267 | /// "basic" versions of AnalysisGroups. |
268 | /// |
269 | class ImmutablePass : public ModulePass { |
270 | public: |
271 | explicit ImmutablePass(char &pid) : ModulePass(pid) {} |
272 | |
273 | // Force out-of-line virtual method. |
274 | ~ImmutablePass() override; |
275 | |
276 | /// initializePass - This method may be overriden by immutable passes to allow |
277 | /// them to perform various initialization actions they require. This is |
278 | /// primarily because an ImmutablePass can "require" another ImmutablePass, |
279 | /// and if it does, the overloaded version of initializePass may get access to |
280 | /// these passes with getAnalysis<>. |
281 | virtual void initializePass(); |
282 | |
283 | ImmutablePass *getAsImmutablePass() override { return this; } |
284 | |
285 | /// ImmutablePasses are never run. |
286 | bool runOnModule(Module &) override { return false; } |
287 | }; |
288 | |
289 | //===----------------------------------------------------------------------===// |
290 | /// FunctionPass class - This class is used to implement most global |
291 | /// optimizations. Optimizations should subclass this class if they meet the |
292 | /// following constraints: |
293 | /// |
294 | /// 1. Optimizations are organized globally, i.e., a function at a time |
295 | /// 2. Optimizing a function does not cause the addition or removal of any |
296 | /// functions in the module |
297 | /// |
298 | class FunctionPass : public Pass { |
299 | public: |
300 | explicit FunctionPass(char &pid) : Pass(PT_Function, pid) {} |
301 | |
302 | /// createPrinterPass - Get a function printer pass. |
303 | Pass *createPrinterPass(raw_ostream &OS, |
304 | const std::string &Banner) const override; |
305 | |
306 | /// runOnFunction - Virtual method overriden by subclasses to do the |
307 | /// per-function processing of the pass. |
308 | virtual bool runOnFunction(Function &F) = 0; |
309 | |
310 | void assignPassManager(PMStack &PMS, PassManagerType T) override; |
311 | |
312 | /// Return what kind of Pass Manager can manage this pass. |
313 | PassManagerType getPotentialPassManagerType() const override; |
314 | |
315 | protected: |
316 | /// Optional passes call this function to check whether the pass should be |
317 | /// skipped. This is the case when Attribute::OptimizeNone is set or when |
318 | /// optimization bisect is over the limit. |
319 | bool skipFunction(const Function &F) const; |
320 | }; |
321 | |
322 | /// If the user specifies the -time-passes argument on an LLVM tool command line |
323 | /// then the value of this boolean will be true, otherwise false. |
324 | /// This is the storage for the -time-passes option. |
325 | extern bool TimePassesIsEnabled; |
326 | /// If TimePassesPerRun is true, there would be one line of report for |
327 | /// each pass invocation. |
328 | /// If TimePassesPerRun is false, there would be only one line of |
329 | /// report for each pass (even there are more than one pass objects). |
330 | /// (For new pass manager only) |
331 | extern bool TimePassesPerRun; |
332 | |
333 | } // end namespace llvm |
334 | |
335 | // Include support files that contain important APIs commonly used by Passes, |
336 | // but that we want to separate out to make it easier to read the header files. |
337 | #include "llvm/PassAnalysisSupport.h" |
338 | #include "llvm/PassSupport.h" |
339 | |
340 | #endif // LLVM_PASS_H |
1 | //===- llvm/PassAnalysisSupport.h - Analysis Pass Support code --*- C++ -*-===// | |||
2 | // | |||
3 | // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. | |||
4 | // See https://llvm.org/LICENSE.txt for license information. | |||
5 | // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception | |||
6 | // | |||
7 | //===----------------------------------------------------------------------===// | |||
8 | // | |||
9 | // This file defines stuff that is used to define and "use" Analysis Passes. | |||
10 | // This file is automatically #included by Pass.h, so: | |||
11 | // | |||
12 | // NO .CPP FILES SHOULD INCLUDE THIS FILE DIRECTLY | |||
13 | // | |||
14 | // Instead, #include Pass.h | |||
15 | // | |||
16 | //===----------------------------------------------------------------------===// | |||
17 | ||||
18 | #if !defined(LLVM_PASS_H) || defined(LLVM_PASSANALYSISSUPPORT_H) | |||
19 | #error "Do not include <PassAnalysisSupport.h>; include <Pass.h> instead" | |||
20 | #endif | |||
21 | ||||
22 | #ifndef LLVM_PASSANALYSISSUPPORT_H | |||
23 | #define LLVM_PASSANALYSISSUPPORT_H | |||
24 | ||||
25 | #include "llvm/ADT/STLExtras.h" | |||
26 | #include "llvm/ADT/SmallVector.h" | |||
27 | #include <cassert> | |||
28 | #include <tuple> | |||
29 | #include <utility> | |||
30 | #include <vector> | |||
31 | ||||
32 | namespace llvm { | |||
33 | ||||
34 | class Function; | |||
35 | class Pass; | |||
36 | class PMDataManager; | |||
37 | class StringRef; | |||
38 | ||||
39 | //===----------------------------------------------------------------------===// | |||
40 | /// Represent the analysis usage information of a pass. This tracks analyses | |||
41 | /// that the pass REQUIRES (must be available when the pass runs), REQUIRES | |||
42 | /// TRANSITIVE (must be available throughout the lifetime of the pass), and | |||
43 | /// analyses that the pass PRESERVES (the pass does not invalidate the results | |||
44 | /// of these analyses). This information is provided by a pass to the Pass | |||
45 | /// infrastructure through the getAnalysisUsage virtual function. | |||
46 | /// | |||
47 | class AnalysisUsage { | |||
48 | public: | |||
49 | using VectorType = SmallVectorImpl<AnalysisID>; | |||
50 | ||||
51 | private: | |||
52 | /// Sets of analyses required and preserved by a pass | |||
53 | // TODO: It's not clear that SmallVector is an appropriate data structure for | |||
54 | // this usecase. The sizes were picked to minimize wasted space, but are | |||
55 | // otherwise fairly meaningless. | |||
56 | SmallVector<AnalysisID, 8> Required; | |||
57 | SmallVector<AnalysisID, 2> RequiredTransitive; | |||
58 | SmallVector<AnalysisID, 2> Preserved; | |||
59 | SmallVector<AnalysisID, 0> Used; | |||
60 | bool PreservesAll = false; | |||
61 | ||||
62 | void pushUnique(VectorType &Set, AnalysisID ID) { | |||
63 | if (!llvm::is_contained(Set, ID)) | |||
64 | Set.push_back(ID); | |||
65 | } | |||
66 | ||||
67 | public: | |||
68 | AnalysisUsage() = default; | |||
69 | ||||
70 | ///@{ | |||
71 | /// Add the specified ID to the required set of the usage info for a pass. | |||
72 | AnalysisUsage &addRequiredID(const void *ID); | |||
73 | AnalysisUsage &addRequiredID(char &ID); | |||
74 | template<class PassClass> | |||
75 | AnalysisUsage &addRequired() { | |||
76 | return addRequiredID(PassClass::ID); | |||
77 | } | |||
78 | ||||
79 | AnalysisUsage &addRequiredTransitiveID(char &ID); | |||
80 | template<class PassClass> | |||
81 | AnalysisUsage &addRequiredTransitive() { | |||
82 | return addRequiredTransitiveID(PassClass::ID); | |||
83 | } | |||
84 | ///@} | |||
85 | ||||
86 | ///@{ | |||
87 | /// Add the specified ID to the set of analyses preserved by this pass. | |||
88 | AnalysisUsage &addPreservedID(const void *ID) { | |||
89 | pushUnique(Preserved, ID); | |||
90 | return *this; | |||
91 | } | |||
92 | AnalysisUsage &addPreservedID(char &ID) { | |||
93 | pushUnique(Preserved, &ID); | |||
94 | return *this; | |||
95 | } | |||
96 | /// Add the specified Pass class to the set of analyses preserved by this pass. | |||
97 | template<class PassClass> | |||
98 | AnalysisUsage &addPreserved() { | |||
99 | pushUnique(Preserved, &PassClass::ID); | |||
100 | return *this; | |||
101 | } | |||
102 | ///@} | |||
103 | ||||
104 | ///@{ | |||
105 | /// Add the specified ID to the set of analyses used by this pass if they are | |||
106 | /// available.. | |||
107 | AnalysisUsage &addUsedIfAvailableID(const void *ID) { | |||
108 | pushUnique(Used, ID); | |||
109 | return *this; | |||
110 | } | |||
111 | AnalysisUsage &addUsedIfAvailableID(char &ID) { | |||
112 | pushUnique(Used, &ID); | |||
113 | return *this; | |||
114 | } | |||
115 | /// Add the specified Pass class to the set of analyses used by this pass. | |||
116 | template<class PassClass> | |||
117 | AnalysisUsage &addUsedIfAvailable() { | |||
118 | pushUnique(Used, &PassClass::ID); | |||
119 | return *this; | |||
120 | } | |||
121 | ///@} | |||
122 | ||||
123 | /// Add the Pass with the specified argument string to the set of analyses | |||
124 | /// preserved by this pass. If no such Pass exists, do nothing. This can be | |||
125 | /// useful when a pass is trivially preserved, but may not be linked in. Be | |||
126 | /// careful about spelling! | |||
127 | AnalysisUsage &addPreserved(StringRef Arg); | |||
128 | ||||
129 | /// Set by analyses that do not transform their input at all | |||
130 | void setPreservesAll() { PreservesAll = true; } | |||
131 | ||||
132 | /// Determine whether a pass said it does not transform its input at all | |||
133 | bool getPreservesAll() const { return PreservesAll; } | |||
134 | ||||
135 | /// This function should be called by the pass, iff they do not: | |||
136 | /// | |||
137 | /// 1. Add or remove basic blocks from the function | |||
138 | /// 2. Modify terminator instructions in any way. | |||
139 | /// | |||
140 | /// This function annotates the AnalysisUsage info object to say that analyses | |||
141 | /// that only depend on the CFG are preserved by this pass. | |||
142 | void setPreservesCFG(); | |||
143 | ||||
144 | const VectorType &getRequiredSet() const { return Required; } | |||
145 | const VectorType &getRequiredTransitiveSet() const { | |||
146 | return RequiredTransitive; | |||
147 | } | |||
148 | const VectorType &getPreservedSet() const { return Preserved; } | |||
149 | const VectorType &getUsedSet() const { return Used; } | |||
150 | }; | |||
151 | ||||
152 | //===----------------------------------------------------------------------===// | |||
153 | /// AnalysisResolver - Simple interface used by Pass objects to pull all | |||
154 | /// analysis information out of pass manager that is responsible to manage | |||
155 | /// the pass. | |||
156 | /// | |||
157 | class AnalysisResolver { | |||
158 | public: | |||
159 | AnalysisResolver() = delete; | |||
160 | explicit AnalysisResolver(PMDataManager &P) : PM(P) {} | |||
161 | ||||
162 | PMDataManager &getPMDataManager() { return PM; } | |||
163 | ||||
164 | /// Find pass that is implementing PI. | |||
165 | Pass *findImplPass(AnalysisID PI) { | |||
166 | Pass *ResultPass = nullptr; | |||
167 | for (const auto &AnalysisImpl : AnalysisImpls) { | |||
168 | if (AnalysisImpl.first == PI) { | |||
169 | ResultPass = AnalysisImpl.second; | |||
170 | break; | |||
171 | } | |||
172 | } | |||
173 | return ResultPass; | |||
174 | } | |||
175 | ||||
176 | /// Find pass that is implementing PI. Initialize pass for Function F. | |||
177 | std::tuple<Pass *, bool> findImplPass(Pass *P, AnalysisID PI, Function &F); | |||
178 | ||||
179 | void addAnalysisImplsPair(AnalysisID PI, Pass *P) { | |||
180 | if (findImplPass(PI) == P) | |||
181 | return; | |||
182 | std::pair<AnalysisID, Pass*> pir = std::make_pair(PI,P); | |||
183 | AnalysisImpls.push_back(pir); | |||
184 | } | |||
185 | ||||
186 | /// Clear cache that is used to connect a pass to the analysis (PassInfo). | |||
187 | void clearAnalysisImpls() { | |||
188 | AnalysisImpls.clear(); | |||
189 | } | |||
190 | ||||
191 | /// Return analysis result or null if it doesn't exist. | |||
192 | Pass *getAnalysisIfAvailable(AnalysisID ID) const; | |||
193 | ||||
194 | private: | |||
195 | /// This keeps track of which passes implements the interfaces that are | |||
196 | /// required by the current pass (to implement getAnalysis()). | |||
197 | std::vector<std::pair<AnalysisID, Pass *>> AnalysisImpls; | |||
198 | ||||
199 | /// PassManager that is used to resolve analysis info | |||
200 | PMDataManager &PM; | |||
201 | }; | |||
202 | ||||
203 | /// getAnalysisIfAvailable<AnalysisType>() - Subclasses use this function to | |||
204 | /// get analysis information that might be around, for example to update it. | |||
205 | /// This is different than getAnalysis in that it can fail (if the analysis | |||
206 | /// results haven't been computed), so should only be used if you can handle | |||
207 | /// the case when the analysis is not available. This method is often used by | |||
208 | /// transformation APIs to update analysis results for a pass automatically as | |||
209 | /// the transform is performed. | |||
210 | template<typename AnalysisType> | |||
211 | AnalysisType *Pass::getAnalysisIfAvailable() const { | |||
212 | assert(Resolver && "Pass not resident in a PassManager object!")((void)0); | |||
213 | ||||
214 | const void *PI = &AnalysisType::ID; | |||
215 | ||||
216 | Pass *ResultPass = Resolver->getAnalysisIfAvailable(PI); | |||
217 | if (!ResultPass) return nullptr; | |||
218 | ||||
219 | // Because the AnalysisType may not be a subclass of pass (for | |||
220 | // AnalysisGroups), we use getAdjustedAnalysisPointer here to potentially | |||
221 | // adjust the return pointer (because the class may multiply inherit, once | |||
222 | // from pass, once from AnalysisType). | |||
223 | return (AnalysisType*)ResultPass->getAdjustedAnalysisPointer(PI); | |||
224 | } | |||
225 | ||||
226 | /// getAnalysis<AnalysisType>() - This function is used by subclasses to get | |||
227 | /// to the analysis information that they claim to use by overriding the | |||
228 | /// getAnalysisUsage function. | |||
229 | template<typename AnalysisType> | |||
230 | AnalysisType &Pass::getAnalysis() const { | |||
231 | assert(Resolver && "Pass has not been inserted into a PassManager object!")((void)0); | |||
232 | return getAnalysisID<AnalysisType>(&AnalysisType::ID); | |||
233 | } | |||
234 | ||||
235 | template<typename AnalysisType> | |||
236 | AnalysisType &Pass::getAnalysisID(AnalysisID PI) const { | |||
237 | assert(PI && "getAnalysis for unregistered pass!")((void)0); | |||
238 | assert(Resolver&&"Pass has not been inserted into a PassManager object!")((void)0); | |||
239 | // PI *must* appear in AnalysisImpls. Because the number of passes used | |||
240 | // should be a small number, we just do a linear search over a (dense) | |||
241 | // vector. | |||
242 | Pass *ResultPass = Resolver->findImplPass(PI); | |||
| ||||
243 | assert(ResultPass &&((void)0) | |||
244 | "getAnalysis*() called on an analysis that was not "((void)0) | |||
245 | "'required' by pass!")((void)0); | |||
246 | ||||
247 | // Because the AnalysisType may not be a subclass of pass (for | |||
248 | // AnalysisGroups), we use getAdjustedAnalysisPointer here to potentially | |||
249 | // adjust the return pointer (because the class may multiply inherit, once | |||
250 | // from pass, once from AnalysisType). | |||
251 | return *(AnalysisType*)ResultPass->getAdjustedAnalysisPointer(PI); | |||
252 | } | |||
253 | ||||
254 | /// getAnalysis<AnalysisType>() - This function is used by subclasses to get | |||
255 | /// to the analysis information that they claim to use by overriding the | |||
256 | /// getAnalysisUsage function. If as part of the dependencies, an IR | |||
257 | /// transformation is triggered (e.g. because the analysis requires | |||
258 | /// BreakCriticalEdges), and Changed is non null, *Changed is updated. | |||
259 | template <typename AnalysisType> | |||
260 | AnalysisType &Pass::getAnalysis(Function &F, bool *Changed) { | |||
261 | assert(Resolver &&"Pass has not been inserted into a PassManager object!")((void)0); | |||
262 | ||||
263 | return getAnalysisID<AnalysisType>(&AnalysisType::ID, F, Changed); | |||
264 | } | |||
265 | ||||
266 | template <typename AnalysisType> | |||
267 | AnalysisType &Pass::getAnalysisID(AnalysisID PI, Function &F, bool *Changed) { | |||
268 | assert(PI && "getAnalysis for unregistered pass!")((void)0); | |||
269 | assert(Resolver && "Pass has not been inserted into a PassManager object!")((void)0); | |||
270 | // PI *must* appear in AnalysisImpls. Because the number of passes used | |||
271 | // should be a small number, we just do a linear search over a (dense) | |||
272 | // vector. | |||
273 | Pass *ResultPass; | |||
274 | bool LocalChanged; | |||
275 | std::tie(ResultPass, LocalChanged) = Resolver->findImplPass(this, PI, F); | |||
276 | ||||
277 | assert(ResultPass && "Unable to find requested analysis info")((void)0); | |||
278 | if (Changed) | |||
279 | *Changed |= LocalChanged; | |||
280 | else | |||
281 | assert(!LocalChanged &&((void)0) | |||
282 | "A pass trigged a code update but the update status is lost")((void)0); | |||
283 | ||||
284 | // Because the AnalysisType may not be a subclass of pass (for | |||
285 | // AnalysisGroups), we use getAdjustedAnalysisPointer here to potentially | |||
286 | // adjust the return pointer (because the class may multiply inherit, once | |||
287 | // from pass, once from AnalysisType). | |||
288 | return *(AnalysisType*)ResultPass->getAdjustedAnalysisPointer(PI); | |||
289 | } | |||
290 | ||||
291 | } // end namespace llvm | |||
292 | ||||
293 | #endif // LLVM_PASSANALYSISSUPPORT_H |