xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/CallGraphSCCPass.cpp (revision ec0ea6efa1ad229d75c394c1a9b9cac33af2b1d3)
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"
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");
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!");
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;
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 NDEBUG
163     if (Changed)
164       RefreshCallGraph(CurSCC, CG, true);
165 #endif
166 
167     return Changed;
168   }
169 
170   assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
171          "Invalid CGPassManager member");
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()
190                       << '\n');
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()
210                     << " nodes:\n";
211              for (CallGraphNode *CGN
212                   : CurSCC) CGN->dump(););
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 &&
281                "CallGraphSCCPass did not update the CallGraph correctly!");
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");
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 &&
351                  "CallGraphSCCPass did not update the CallGraph correctly!");
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 '"
363                                 << Callee->getName() << "'\n");
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 &&
376                "CallGraphSCCPass did not update the CallGraph correctly!");
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");
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) {
419     dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
420     for (CallGraphNode *CGN : CurSCC)
421       CGN->dump();
422     if (DevirtualizedCall)
423       dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
424   } else {
425     dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
426   });
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 NDEBUG
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");
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()
540                  << "  SCCPASSMGR: Re-visiting SCC, iteration #" << Iteration
541                  << '\n');
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 "
548                         << Iteration
549                         << " times, due to -max-devirt-iterations\n");
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 &&
563              "Invalid CGPassManager member");
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 &&
578              "Invalid CGPassManager member");
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");
595   for (unsigned i = 0; ; ++i) {
596     assert(i != Nodes.size() && "Node not in SCC");
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");
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");
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,
761                 false)
762