File: | src/gnu/usr.bin/clang/libLLVM/../../../llvm/llvm/lib/Analysis/CallGraphSCCPass.cpp |
Warning: | line 155, column 11 Value stored to 'InstrCount' is never read |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
1 | //===- CallGraphSCCPass.cpp - Pass that operates BU on call graph ---------===// |
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 implements the CallGraphSCCPass class, which is used for passes |
10 | // which are implemented as bottom-up traversals on the call graph. Because |
11 | // there may be cycles in the call graph, passes of this type operate on the |
12 | // call-graph in SCC order: that is, they process function bottom-up, except for |
13 | // recursive functions, which they process all at once. |
14 | // |
15 | //===----------------------------------------------------------------------===// |
16 | |
17 | #include "llvm/Analysis/CallGraphSCCPass.h" |
18 | #include "llvm/ADT/DenseMap.h" |
19 | #include "llvm/ADT/SCCIterator.h" |
20 | #include "llvm/ADT/Statistic.h" |
21 | #include "llvm/Analysis/CallGraph.h" |
22 | #include "llvm/IR/AbstractCallSite.h" |
23 | #include "llvm/IR/Function.h" |
24 | #include "llvm/IR/Intrinsics.h" |
25 | #include "llvm/IR/LLVMContext.h" |
26 | #include "llvm/IR/LegacyPassManagers.h" |
27 | #include "llvm/IR/Module.h" |
28 | #include "llvm/IR/OptBisect.h" |
29 | #include "llvm/IR/PassTimingInfo.h" |
30 | #include "llvm/IR/PrintPasses.h" |
31 | #include "llvm/IR/StructuralHash.h" |
32 | #include "llvm/Pass.h" |
33 | #include "llvm/Support/CommandLine.h" |
34 | #include "llvm/Support/Debug.h" |
35 | #include "llvm/Support/Timer.h" |
36 | #include "llvm/Support/raw_ostream.h" |
37 | #include <cassert> |
38 | #include <string> |
39 | #include <utility> |
40 | #include <vector> |
41 | |
42 | using namespace llvm; |
43 | |
44 | #define DEBUG_TYPE"cgscc-passmgr" "cgscc-passmgr" |
45 | |
46 | namespace llvm { |
47 | cl::opt<unsigned> MaxDevirtIterations("max-devirt-iterations", cl::ReallyHidden, |
48 | cl::init(4)); |
49 | } |
50 | |
51 | STATISTIC(MaxSCCIterations, "Maximum CGSCCPassMgr iterations on one SCC")static llvm::Statistic MaxSCCIterations = {"cgscc-passmgr", "MaxSCCIterations" , "Maximum CGSCCPassMgr iterations on one SCC"}; |
52 | |
53 | //===----------------------------------------------------------------------===// |
54 | // CGPassManager |
55 | // |
56 | /// CGPassManager manages FPPassManagers and CallGraphSCCPasses. |
57 | |
58 | namespace { |
59 | |
60 | class CGPassManager : public ModulePass, public PMDataManager { |
61 | public: |
62 | static char ID; |
63 | |
64 | explicit CGPassManager() : ModulePass(ID), PMDataManager() {} |
65 | |
66 | /// Execute all of the passes scheduled for execution. Keep track of |
67 | /// whether any of the passes modifies the module, and if so, return true. |
68 | bool runOnModule(Module &M) override; |
69 | |
70 | using ModulePass::doInitialization; |
71 | using ModulePass::doFinalization; |
72 | |
73 | bool doInitialization(CallGraph &CG); |
74 | bool doFinalization(CallGraph &CG); |
75 | |
76 | /// Pass Manager itself does not invalidate any analysis info. |
77 | void getAnalysisUsage(AnalysisUsage &Info) const override { |
78 | // CGPassManager walks SCC and it needs CallGraph. |
79 | Info.addRequired<CallGraphWrapperPass>(); |
80 | Info.setPreservesAll(); |
81 | } |
82 | |
83 | StringRef getPassName() const override { return "CallGraph Pass Manager"; } |
84 | |
85 | PMDataManager *getAsPMDataManager() override { return this; } |
86 | Pass *getAsPass() override { return this; } |
87 | |
88 | // Print passes managed by this manager |
89 | void dumpPassStructure(unsigned Offset) override { |
90 | errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n"; |
91 | for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { |
92 | Pass *P = getContainedPass(Index); |
93 | P->dumpPassStructure(Offset + 1); |
94 | dumpLastUses(P, Offset+1); |
95 | } |
96 | } |
97 | |
98 | Pass *getContainedPass(unsigned N) { |
99 | assert(N < PassVector.size() && "Pass number out of range!")((void)0); |
100 | return static_cast<Pass *>(PassVector[N]); |
101 | } |
102 | |
103 | PassManagerType getPassManagerType() const override { |
104 | return PMT_CallGraphPassManager; |
105 | } |
106 | |
107 | private: |
108 | bool RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG, |
109 | bool &DevirtualizedCall); |
110 | |
111 | bool RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC, |
112 | CallGraph &CG, bool &CallGraphUpToDate, |
113 | bool &DevirtualizedCall); |
114 | bool RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG, |
115 | bool IsCheckingMode); |
116 | }; |
117 | |
118 | } // end anonymous namespace. |
119 | |
120 | char CGPassManager::ID = 0; |
121 | |
122 | bool CGPassManager::RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC, |
123 | CallGraph &CG, bool &CallGraphUpToDate, |
124 | bool &DevirtualizedCall) { |
125 | bool Changed = false; |
126 | PMDataManager *PM = P->getAsPMDataManager(); |
127 | Module &M = CG.getModule(); |
128 | |
129 | if (!PM) { |
130 | CallGraphSCCPass *CGSP = (CallGraphSCCPass *)P; |
131 | if (!CallGraphUpToDate) { |
132 | DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false); |
133 | CallGraphUpToDate = true; |
134 | } |
135 | |
136 | { |
137 | unsigned InstrCount, SCCCount = 0; |
138 | StringMap<std::pair<unsigned, unsigned>> FunctionToInstrCount; |
139 | bool EmitICRemark = M.shouldEmitInstrCountChangedRemark(); |
140 | TimeRegion PassTimer(getPassTimer(CGSP)); |
141 | if (EmitICRemark) |
142 | InstrCount = initSizeRemarkInfo(M, FunctionToInstrCount); |
143 | Changed = CGSP->runOnSCC(CurSCC); |
144 | |
145 | if (EmitICRemark) { |
146 | // FIXME: Add getInstructionCount to CallGraphSCC. |
147 | SCCCount = M.getInstructionCount(); |
148 | // Is there a difference in the number of instructions in the module? |
149 | if (SCCCount != InstrCount) { |
150 | // Yep. Emit a remark and update InstrCount. |
151 | int64_t Delta = |
152 | static_cast<int64_t>(SCCCount) - static_cast<int64_t>(InstrCount); |
153 | emitInstrCountChangedRemark(P, M, Delta, InstrCount, |
154 | FunctionToInstrCount); |
155 | InstrCount = SCCCount; |
Value stored to 'InstrCount' is never read | |
156 | } |
157 | } |
158 | } |
159 | |
160 | // After the CGSCCPass is done, when assertions are enabled, use |
161 | // RefreshCallGraph to verify that the callgraph was correctly updated. |
162 | #ifndef NDEBUG1 |
163 | if (Changed) |
164 | RefreshCallGraph(CurSCC, CG, true); |
165 | #endif |
166 | |
167 | return Changed; |
168 | } |
169 | |
170 | assert(PM->getPassManagerType() == PMT_FunctionPassManager &&((void)0) |
171 | "Invalid CGPassManager member")((void)0); |
172 | FPPassManager *FPP = (FPPassManager*)P; |
173 | |
174 | // Run pass P on all functions in the current SCC. |
175 | for (CallGraphNode *CGN : CurSCC) { |
176 | if (Function *F = CGN->getFunction()) { |
177 | dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName()); |
178 | { |
179 | TimeRegion PassTimer(getPassTimer(FPP)); |
180 | Changed |= FPP->runOnFunction(*F); |
181 | } |
182 | F->getContext().yield(); |
183 | } |
184 | } |
185 | |
186 | // The function pass(es) modified the IR, they may have clobbered the |
187 | // callgraph. |
188 | if (Changed && CallGraphUpToDate) { |
189 | LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: " << P->getPassName()do { } while (false) |
190 | << '\n')do { } while (false); |
191 | CallGraphUpToDate = false; |
192 | } |
193 | return Changed; |
194 | } |
195 | |
196 | /// Scan the functions in the specified CFG and resync the |
197 | /// callgraph with the call sites found in it. This is used after |
198 | /// FunctionPasses have potentially munged the callgraph, and can be used after |
199 | /// CallGraphSCC passes to verify that they correctly updated the callgraph. |
200 | /// |
201 | /// This function returns true if it devirtualized an existing function call, |
202 | /// meaning it turned an indirect call into a direct call. This happens when |
203 | /// a function pass like GVN optimizes away stuff feeding the indirect call. |
204 | /// This never happens in checking mode. |
205 | bool CGPassManager::RefreshCallGraph(const CallGraphSCC &CurSCC, CallGraph &CG, |
206 | bool CheckingMode) { |
207 | DenseMap<Value *, CallGraphNode *> Calls; |
208 | |
209 | LLVM_DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()do { } while (false) |
210 | << " nodes:\n";do { } while (false) |
211 | for (CallGraphNode *CGNdo { } while (false) |
212 | : CurSCC) CGN->dump();)do { } while (false); |
213 | |
214 | bool MadeChange = false; |
215 | bool DevirtualizedCall = false; |
216 | |
217 | // Scan all functions in the SCC. |
218 | unsigned FunctionNo = 0; |
219 | for (CallGraphSCC::iterator SCCIdx = CurSCC.begin(), E = CurSCC.end(); |
220 | SCCIdx != E; ++SCCIdx, ++FunctionNo) { |
221 | CallGraphNode *CGN = *SCCIdx; |
222 | Function *F = CGN->getFunction(); |
223 | if (!F || F->isDeclaration()) continue; |
224 | |
225 | // Walk the function body looking for call sites. Sync up the call sites in |
226 | // CGN with those actually in the function. |
227 | |
228 | // Keep track of the number of direct and indirect calls that were |
229 | // invalidated and removed. |
230 | unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0; |
231 | |
232 | CallGraphNode::iterator CGNEnd = CGN->end(); |
233 | |
234 | auto RemoveAndCheckForDone = [&](CallGraphNode::iterator I) { |
235 | // Just remove the edge from the set of callees, keep track of whether |
236 | // I points to the last element of the vector. |
237 | bool WasLast = I + 1 == CGNEnd; |
238 | CGN->removeCallEdge(I); |
239 | |
240 | // If I pointed to the last element of the vector, we have to bail out: |
241 | // iterator checking rejects comparisons of the resultant pointer with |
242 | // end. |
243 | if (WasLast) |
244 | return true; |
245 | |
246 | CGNEnd = CGN->end(); |
247 | return false; |
248 | }; |
249 | |
250 | // Get the set of call sites currently in the function. |
251 | for (CallGraphNode::iterator I = CGN->begin(); I != CGNEnd;) { |
252 | // Delete "reference" call records that do not have call instruction. We |
253 | // reinsert them as needed later. However, keep them in checking mode. |
254 | if (!I->first) { |
255 | if (CheckingMode) { |
256 | ++I; |
257 | continue; |
258 | } |
259 | if (RemoveAndCheckForDone(I)) |
260 | break; |
261 | continue; |
262 | } |
263 | |
264 | // If this call site is null, then the function pass deleted the call |
265 | // entirely and the WeakTrackingVH nulled it out. |
266 | auto *Call = dyn_cast_or_null<CallBase>(*I->first); |
267 | if (!Call || |
268 | // If we've already seen this call site, then the FunctionPass RAUW'd |
269 | // one call with another, which resulted in two "uses" in the edge |
270 | // list of the same call. |
271 | Calls.count(Call) || |
272 | |
273 | // If the call edge is not from a call or invoke, or it is a |
274 | // instrinsic call, then the function pass RAUW'd a call with |
275 | // another value. This can happen when constant folding happens |
276 | // of well known functions etc. |
277 | (Call->getCalledFunction() && |
278 | Call->getCalledFunction()->isIntrinsic() && |
279 | Intrinsic::isLeaf(Call->getCalledFunction()->getIntrinsicID()))) { |
280 | assert(!CheckingMode &&((void)0) |
281 | "CallGraphSCCPass did not update the CallGraph correctly!")((void)0); |
282 | |
283 | // If this was an indirect call site, count it. |
284 | if (!I->second->getFunction()) |
285 | ++NumIndirectRemoved; |
286 | else |
287 | ++NumDirectRemoved; |
288 | |
289 | if (RemoveAndCheckForDone(I)) |
290 | break; |
291 | continue; |
292 | } |
293 | |
294 | assert(!Calls.count(Call) && "Call site occurs in node multiple times")((void)0); |
295 | |
296 | if (Call) { |
297 | Function *Callee = Call->getCalledFunction(); |
298 | // Ignore intrinsics because they're not really function calls. |
299 | if (!Callee || !(Callee->isIntrinsic())) |
300 | Calls.insert(std::make_pair(Call, I->second)); |
301 | } |
302 | ++I; |
303 | } |
304 | |
305 | // Loop over all of the instructions in the function, getting the callsites. |
306 | // Keep track of the number of direct/indirect calls added. |
307 | unsigned NumDirectAdded = 0, NumIndirectAdded = 0; |
308 | |
309 | for (BasicBlock &BB : *F) |
310 | for (Instruction &I : BB) { |
311 | auto *Call = dyn_cast<CallBase>(&I); |
312 | if (!Call) |
313 | continue; |
314 | Function *Callee = Call->getCalledFunction(); |
315 | if (Callee && Callee->isIntrinsic()) |
316 | continue; |
317 | |
318 | // If we are not in checking mode, insert potential callback calls as |
319 | // references. This is not a requirement but helps to iterate over the |
320 | // functions in the right order. |
321 | if (!CheckingMode) { |
322 | forEachCallbackFunction(*Call, [&](Function *CB) { |
323 | CGN->addCalledFunction(nullptr, CG.getOrInsertFunction(CB)); |
324 | }); |
325 | } |
326 | |
327 | // If this call site already existed in the callgraph, just verify it |
328 | // matches up to expectations and remove it from Calls. |
329 | DenseMap<Value *, CallGraphNode *>::iterator ExistingIt = |
330 | Calls.find(Call); |
331 | if (ExistingIt != Calls.end()) { |
332 | CallGraphNode *ExistingNode = ExistingIt->second; |
333 | |
334 | // Remove from Calls since we have now seen it. |
335 | Calls.erase(ExistingIt); |
336 | |
337 | // Verify that the callee is right. |
338 | if (ExistingNode->getFunction() == Call->getCalledFunction()) |
339 | continue; |
340 | |
341 | // If we are in checking mode, we are not allowed to actually mutate |
342 | // the callgraph. If this is a case where we can infer that the |
343 | // callgraph is less precise than it could be (e.g. an indirect call |
344 | // site could be turned direct), don't reject it in checking mode, and |
345 | // don't tweak it to be more precise. |
346 | if (CheckingMode && Call->getCalledFunction() && |
347 | ExistingNode->getFunction() == nullptr) |
348 | continue; |
349 | |
350 | assert(!CheckingMode &&((void)0) |
351 | "CallGraphSCCPass did not update the CallGraph correctly!")((void)0); |
352 | |
353 | // If not, we either went from a direct call to indirect, indirect to |
354 | // direct, or direct to different direct. |
355 | CallGraphNode *CalleeNode; |
356 | if (Function *Callee = Call->getCalledFunction()) { |
357 | CalleeNode = CG.getOrInsertFunction(Callee); |
358 | // Keep track of whether we turned an indirect call into a direct |
359 | // one. |
360 | if (!ExistingNode->getFunction()) { |
361 | DevirtualizedCall = true; |
362 | LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Devirtualized call to '"do { } while (false) |
363 | << Callee->getName() << "'\n")do { } while (false); |
364 | } |
365 | } else { |
366 | CalleeNode = CG.getCallsExternalNode(); |
367 | } |
368 | |
369 | // Update the edge target in CGN. |
370 | CGN->replaceCallEdge(*Call, *Call, CalleeNode); |
371 | MadeChange = true; |
372 | continue; |
373 | } |
374 | |
375 | assert(!CheckingMode &&((void)0) |
376 | "CallGraphSCCPass did not update the CallGraph correctly!")((void)0); |
377 | |
378 | // If the call site didn't exist in the CGN yet, add it. |
379 | CallGraphNode *CalleeNode; |
380 | if (Function *Callee = Call->getCalledFunction()) { |
381 | CalleeNode = CG.getOrInsertFunction(Callee); |
382 | ++NumDirectAdded; |
383 | } else { |
384 | CalleeNode = CG.getCallsExternalNode(); |
385 | ++NumIndirectAdded; |
386 | } |
387 | |
388 | CGN->addCalledFunction(Call, CalleeNode); |
389 | MadeChange = true; |
390 | } |
391 | |
392 | // We scanned the old callgraph node, removing invalidated call sites and |
393 | // then added back newly found call sites. One thing that can happen is |
394 | // that an old indirect call site was deleted and replaced with a new direct |
395 | // call. In this case, we have devirtualized a call, and CGSCCPM would like |
396 | // to iteratively optimize the new code. Unfortunately, we don't really |
397 | // have a great way to detect when this happens. As an approximation, we |
398 | // just look at whether the number of indirect calls is reduced and the |
399 | // number of direct calls is increased. There are tons of ways to fool this |
400 | // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a |
401 | // direct call) but this is close enough. |
402 | if (NumIndirectRemoved > NumIndirectAdded && |
403 | NumDirectRemoved < NumDirectAdded) |
404 | DevirtualizedCall = true; |
405 | |
406 | // After scanning this function, if we still have entries in callsites, then |
407 | // they are dangling pointers. WeakTrackingVH should save us for this, so |
408 | // abort if |
409 | // this happens. |
410 | assert(Calls.empty() && "Dangling pointers found in call sites map")((void)0); |
411 | |
412 | // Periodically do an explicit clear to remove tombstones when processing |
413 | // large scc's. |
414 | if ((FunctionNo & 15) == 15) |
415 | Calls.clear(); |
416 | } |
417 | |
418 | LLVM_DEBUG(if (MadeChange) {do { } while (false) |
419 | dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";do { } while (false) |
420 | for (CallGraphNode *CGN : CurSCC)do { } while (false) |
421 | CGN->dump();do { } while (false) |
422 | if (DevirtualizedCall)do { } while (false) |
423 | dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";do { } while (false) |
424 | } else {do { } while (false) |
425 | dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";do { } while (false) |
426 | })do { } while (false); |
427 | (void)MadeChange; |
428 | |
429 | return DevirtualizedCall; |
430 | } |
431 | |
432 | /// Execute the body of the entire pass manager on the specified SCC. |
433 | /// This keeps track of whether a function pass devirtualizes |
434 | /// any calls and returns it in DevirtualizedCall. |
435 | bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG, |
436 | bool &DevirtualizedCall) { |
437 | bool Changed = false; |
438 | |
439 | // Keep track of whether the callgraph is known to be up-to-date or not. |
440 | // The CGSSC pass manager runs two types of passes: |
441 | // CallGraphSCC Passes and other random function passes. Because other |
442 | // random function passes are not CallGraph aware, they may clobber the |
443 | // call graph by introducing new calls or deleting other ones. This flag |
444 | // is set to false when we run a function pass so that we know to clean up |
445 | // the callgraph when we need to run a CGSCCPass again. |
446 | bool CallGraphUpToDate = true; |
447 | |
448 | // Run all passes on current SCC. |
449 | for (unsigned PassNo = 0, e = getNumContainedPasses(); |
450 | PassNo != e; ++PassNo) { |
451 | Pass *P = getContainedPass(PassNo); |
452 | |
453 | // If we're in -debug-pass=Executions mode, construct the SCC node list, |
454 | // otherwise avoid constructing this string as it is expensive. |
455 | if (isPassDebuggingExecutionsOrMore()) { |
456 | std::string Functions; |
457 | #ifndef NDEBUG1 |
458 | raw_string_ostream OS(Functions); |
459 | ListSeparator LS; |
460 | for (const CallGraphNode *CGN : CurSCC) { |
461 | OS << LS; |
462 | CGN->print(OS); |
463 | } |
464 | OS.flush(); |
465 | #endif |
466 | dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions); |
467 | } |
468 | dumpRequiredSet(P); |
469 | |
470 | initializeAnalysisImpl(P); |
471 | |
472 | #ifdef EXPENSIVE_CHECKS |
473 | uint64_t RefHash = StructuralHash(CG.getModule()); |
474 | #endif |
475 | |
476 | // Actually run this pass on the current SCC. |
477 | bool LocalChanged = |
478 | RunPassOnSCC(P, CurSCC, CG, CallGraphUpToDate, DevirtualizedCall); |
479 | |
480 | Changed |= LocalChanged; |
481 | |
482 | #ifdef EXPENSIVE_CHECKS |
483 | if (!LocalChanged && (RefHash != StructuralHash(CG.getModule()))) { |
484 | llvm::errs() << "Pass modifies its input and doesn't report it: " |
485 | << P->getPassName() << "\n"; |
486 | llvm_unreachable("Pass modifies its input and doesn't report it")__builtin_unreachable(); |
487 | } |
488 | #endif |
489 | if (LocalChanged) |
490 | dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, ""); |
491 | dumpPreservedSet(P); |
492 | |
493 | verifyPreservedAnalysis(P); |
494 | if (LocalChanged) |
495 | removeNotPreservedAnalysis(P); |
496 | recordAvailableAnalysis(P); |
497 | removeDeadPasses(P, "", ON_CG_MSG); |
498 | } |
499 | |
500 | // If the callgraph was left out of date (because the last pass run was a |
501 | // functionpass), refresh it before we move on to the next SCC. |
502 | if (!CallGraphUpToDate) |
503 | DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false); |
504 | return Changed; |
505 | } |
506 | |
507 | /// Execute all of the passes scheduled for execution. Keep track of |
508 | /// whether any of the passes modifies the module, and if so, return true. |
509 | bool CGPassManager::runOnModule(Module &M) { |
510 | CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph(); |
511 | bool Changed = doInitialization(CG); |
512 | |
513 | // Walk the callgraph in bottom-up SCC order. |
514 | scc_iterator<CallGraph*> CGI = scc_begin(&CG); |
515 | |
516 | CallGraphSCC CurSCC(CG, &CGI); |
517 | while (!CGI.isAtEnd()) { |
518 | // Copy the current SCC and increment past it so that the pass can hack |
519 | // on the SCC if it wants to without invalidating our iterator. |
520 | const std::vector<CallGraphNode *> &NodeVec = *CGI; |
521 | CurSCC.initialize(NodeVec); |
522 | ++CGI; |
523 | |
524 | // At the top level, we run all the passes in this pass manager on the |
525 | // functions in this SCC. However, we support iterative compilation in the |
526 | // case where a function pass devirtualizes a call to a function. For |
527 | // example, it is very common for a function pass (often GVN or instcombine) |
528 | // to eliminate the addressing that feeds into a call. With that improved |
529 | // information, we would like the call to be an inline candidate, infer |
530 | // mod-ref information etc. |
531 | // |
532 | // Because of this, we allow iteration up to a specified iteration count. |
533 | // This only happens in the case of a devirtualized call, so we only burn |
534 | // compile time in the case that we're making progress. We also have a hard |
535 | // iteration count limit in case there is crazy code. |
536 | unsigned Iteration = 0; |
537 | bool DevirtualizedCall = false; |
538 | do { |
539 | LLVM_DEBUG(if (Iteration) dbgs()do { } while (false) |
540 | << " SCCPASSMGR: Re-visiting SCC, iteration #" << Iterationdo { } while (false) |
541 | << '\n')do { } while (false); |
542 | DevirtualizedCall = false; |
543 | Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall); |
544 | } while (Iteration++ < MaxDevirtIterations && DevirtualizedCall); |
545 | |
546 | if (DevirtualizedCall) |
547 | LLVM_DEBUG(dbgs() << " CGSCCPASSMGR: Stopped iteration after "do { } while (false) |
548 | << Iterationdo { } while (false) |
549 | << " times, due to -max-devirt-iterations\n")do { } while (false); |
550 | |
551 | MaxSCCIterations.updateMax(Iteration); |
552 | } |
553 | Changed |= doFinalization(CG); |
554 | return Changed; |
555 | } |
556 | |
557 | /// Initialize CG |
558 | bool CGPassManager::doInitialization(CallGraph &CG) { |
559 | bool Changed = false; |
560 | for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) { |
561 | if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) { |
562 | assert(PM->getPassManagerType() == PMT_FunctionPassManager &&((void)0) |
563 | "Invalid CGPassManager member")((void)0); |
564 | Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule()); |
565 | } else { |
566 | Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG); |
567 | } |
568 | } |
569 | return Changed; |
570 | } |
571 | |
572 | /// Finalize CG |
573 | bool CGPassManager::doFinalization(CallGraph &CG) { |
574 | bool Changed = false; |
575 | for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) { |
576 | if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) { |
577 | assert(PM->getPassManagerType() == PMT_FunctionPassManager &&((void)0) |
578 | "Invalid CGPassManager member")((void)0); |
579 | Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule()); |
580 | } else { |
581 | Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG); |
582 | } |
583 | } |
584 | return Changed; |
585 | } |
586 | |
587 | //===----------------------------------------------------------------------===// |
588 | // CallGraphSCC Implementation |
589 | //===----------------------------------------------------------------------===// |
590 | |
591 | /// This informs the SCC and the pass manager that the specified |
592 | /// Old node has been deleted, and New is to be used in its place. |
593 | void CallGraphSCC::ReplaceNode(CallGraphNode *Old, CallGraphNode *New) { |
594 | assert(Old != New && "Should not replace node with self")((void)0); |
595 | for (unsigned i = 0; ; ++i) { |
596 | assert(i != Nodes.size() && "Node not in SCC")((void)0); |
597 | if (Nodes[i] != Old) continue; |
598 | if (New) |
599 | Nodes[i] = New; |
600 | else |
601 | Nodes.erase(Nodes.begin() + i); |
602 | break; |
603 | } |
604 | |
605 | // Update the active scc_iterator so that it doesn't contain dangling |
606 | // pointers to the old CallGraphNode. |
607 | scc_iterator<CallGraph*> *CGI = (scc_iterator<CallGraph*>*)Context; |
608 | CGI->ReplaceNode(Old, New); |
609 | } |
610 | |
611 | void CallGraphSCC::DeleteNode(CallGraphNode *Old) { |
612 | ReplaceNode(Old, /*New=*/nullptr); |
613 | } |
614 | |
615 | //===----------------------------------------------------------------------===// |
616 | // CallGraphSCCPass Implementation |
617 | //===----------------------------------------------------------------------===// |
618 | |
619 | /// Assign pass manager to manage this pass. |
620 | void CallGraphSCCPass::assignPassManager(PMStack &PMS, |
621 | PassManagerType PreferredType) { |
622 | // Find CGPassManager |
623 | while (!PMS.empty() && |
624 | PMS.top()->getPassManagerType() > PMT_CallGraphPassManager) |
625 | PMS.pop(); |
626 | |
627 | assert(!PMS.empty() && "Unable to handle Call Graph Pass")((void)0); |
628 | CGPassManager *CGP; |
629 | |
630 | if (PMS.top()->getPassManagerType() == PMT_CallGraphPassManager) |
631 | CGP = (CGPassManager*)PMS.top(); |
632 | else { |
633 | // Create new Call Graph SCC Pass Manager if it does not exist. |
634 | assert(!PMS.empty() && "Unable to create Call Graph Pass Manager")((void)0); |
635 | PMDataManager *PMD = PMS.top(); |
636 | |
637 | // [1] Create new Call Graph Pass Manager |
638 | CGP = new CGPassManager(); |
639 | |
640 | // [2] Set up new manager's top level manager |
641 | PMTopLevelManager *TPM = PMD->getTopLevelManager(); |
642 | TPM->addIndirectPassManager(CGP); |
643 | |
644 | // [3] Assign manager to manage this new manager. This may create |
645 | // and push new managers into PMS |
646 | Pass *P = CGP; |
647 | TPM->schedulePass(P); |
648 | |
649 | // [4] Push new manager into PMS |
650 | PMS.push(CGP); |
651 | } |
652 | |
653 | CGP->add(this); |
654 | } |
655 | |
656 | /// For this class, we declare that we require and preserve the call graph. |
657 | /// If the derived class implements this method, it should |
658 | /// always explicitly call the implementation here. |
659 | void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const { |
660 | AU.addRequired<CallGraphWrapperPass>(); |
661 | AU.addPreserved<CallGraphWrapperPass>(); |
662 | } |
663 | |
664 | //===----------------------------------------------------------------------===// |
665 | // PrintCallGraphPass Implementation |
666 | //===----------------------------------------------------------------------===// |
667 | |
668 | namespace { |
669 | |
670 | /// PrintCallGraphPass - Print a Module corresponding to a call graph. |
671 | /// |
672 | class PrintCallGraphPass : public CallGraphSCCPass { |
673 | std::string Banner; |
674 | raw_ostream &OS; // raw_ostream to print on. |
675 | |
676 | public: |
677 | static char ID; |
678 | |
679 | PrintCallGraphPass(const std::string &B, raw_ostream &OS) |
680 | : CallGraphSCCPass(ID), Banner(B), OS(OS) {} |
681 | |
682 | void getAnalysisUsage(AnalysisUsage &AU) const override { |
683 | AU.setPreservesAll(); |
684 | } |
685 | |
686 | bool runOnSCC(CallGraphSCC &SCC) override { |
687 | bool BannerPrinted = false; |
688 | auto PrintBannerOnce = [&]() { |
689 | if (BannerPrinted) |
690 | return; |
691 | OS << Banner; |
692 | BannerPrinted = true; |
693 | }; |
694 | |
695 | bool NeedModule = llvm::forcePrintModuleIR(); |
696 | if (isFunctionInPrintList("*") && NeedModule) { |
697 | PrintBannerOnce(); |
698 | OS << "\n"; |
699 | SCC.getCallGraph().getModule().print(OS, nullptr); |
700 | return false; |
701 | } |
702 | bool FoundFunction = false; |
703 | for (CallGraphNode *CGN : SCC) { |
704 | if (Function *F = CGN->getFunction()) { |
705 | if (!F->isDeclaration() && isFunctionInPrintList(F->getName())) { |
706 | FoundFunction = true; |
707 | if (!NeedModule) { |
708 | PrintBannerOnce(); |
709 | F->print(OS); |
710 | } |
711 | } |
712 | } else if (isFunctionInPrintList("*")) { |
713 | PrintBannerOnce(); |
714 | OS << "\nPrinting <null> Function\n"; |
715 | } |
716 | } |
717 | if (NeedModule && FoundFunction) { |
718 | PrintBannerOnce(); |
719 | OS << "\n"; |
720 | SCC.getCallGraph().getModule().print(OS, nullptr); |
721 | } |
722 | return false; |
723 | } |
724 | |
725 | StringRef getPassName() const override { return "Print CallGraph IR"; } |
726 | }; |
727 | |
728 | } // end anonymous namespace. |
729 | |
730 | char PrintCallGraphPass::ID = 0; |
731 | |
732 | Pass *CallGraphSCCPass::createPrinterPass(raw_ostream &OS, |
733 | const std::string &Banner) const { |
734 | return new PrintCallGraphPass(Banner, OS); |
735 | } |
736 | |
737 | static std::string getDescription(const CallGraphSCC &SCC) { |
738 | std::string Desc = "SCC ("; |
739 | ListSeparator LS; |
740 | for (CallGraphNode *CGN : SCC) { |
741 | Desc += LS; |
742 | Function *F = CGN->getFunction(); |
743 | if (F) |
744 | Desc += F->getName(); |
745 | else |
746 | Desc += "<<null function>>"; |
747 | } |
748 | Desc += ")"; |
749 | return Desc; |
750 | } |
751 | |
752 | bool CallGraphSCCPass::skipSCC(CallGraphSCC &SCC) const { |
753 | OptPassGate &Gate = |
754 | SCC.getCallGraph().getModule().getContext().getOptPassGate(); |
755 | return Gate.isEnabled() && !Gate.shouldRunPass(this, getDescription(SCC)); |
756 | } |
757 | |
758 | char DummyCGSCCPass::ID = 0; |
759 | |
760 | INITIALIZE_PASS(DummyCGSCCPass, "DummyCGSCCPass", "DummyCGSCCPass", false,static void *initializeDummyCGSCCPassPassOnce(PassRegistry & Registry) { PassInfo *PI = new PassInfo( "DummyCGSCCPass", "DummyCGSCCPass" , &DummyCGSCCPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <DummyCGSCCPass>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeDummyCGSCCPassPassFlag ; void llvm::initializeDummyCGSCCPassPass(PassRegistry &Registry ) { llvm::call_once(InitializeDummyCGSCCPassPassFlag, initializeDummyCGSCCPassPassOnce , std::ref(Registry)); } |
761 | false)static void *initializeDummyCGSCCPassPassOnce(PassRegistry & Registry) { PassInfo *PI = new PassInfo( "DummyCGSCCPass", "DummyCGSCCPass" , &DummyCGSCCPass::ID, PassInfo::NormalCtor_t(callDefaultCtor <DummyCGSCCPass>), false, false); Registry.registerPass (*PI, true); return PI; } static llvm::once_flag InitializeDummyCGSCCPassPassFlag ; void llvm::initializeDummyCGSCCPassPass(PassRegistry &Registry ) { llvm::call_once(InitializeDummyCGSCCPassPassFlag, initializeDummyCGSCCPassPassOnce , std::ref(Registry)); } |