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