Line data Source code
1 : //===- CallGraphSCCPass.cpp - Pass that operates BU on call graph ---------===//
2 : //
3 : // The LLVM Compiler Infrastructure
4 : //
5 : // This file is distributed under the University of Illinois Open Source
6 : // License. See LICENSE.TXT for details.
7 : //
8 : //===----------------------------------------------------------------------===//
9 : //
10 : // This file implements the CallGraphSCCPass class, which is used for passes
11 : // which are implemented as bottom-up traversals on the call graph. Because
12 : // there may be cycles in the call graph, passes of this type operate on the
13 : // call-graph in SCC order: that is, they process function bottom-up, except for
14 : // recursive functions, which they process all at once.
15 : //
16 : //===----------------------------------------------------------------------===//
17 :
18 : #include "llvm/Analysis/CallGraphSCCPass.h"
19 : #include "llvm/ADT/SCCIterator.h"
20 : #include "llvm/ADT/Statistic.h"
21 : #include "llvm/Analysis/CallGraph.h"
22 : #include "llvm/IR/Function.h"
23 : #include "llvm/IR/IntrinsicInst.h"
24 : #include "llvm/IR/LLVMContext.h"
25 : #include "llvm/IR/LegacyPassManagers.h"
26 : #include "llvm/Support/CommandLine.h"
27 : #include "llvm/Support/Debug.h"
28 : #include "llvm/Support/Timer.h"
29 : #include "llvm/Support/raw_ostream.h"
30 : using namespace llvm;
31 :
32 : #define DEBUG_TYPE "cgscc-passmgr"
33 :
34 : static cl::opt<unsigned>
35 38830 : MaxIterations("max-cg-scc-iterations", cl::ReallyHidden, cl::init(4));
36 :
37 : STATISTIC(MaxSCCIterations, "Maximum CGSCCPassMgr iterations on one SCC");
38 :
39 : //===----------------------------------------------------------------------===//
40 : // CGPassManager
41 : //
42 : /// CGPassManager manages FPPassManagers and CallGraphSCCPasses.
43 :
44 : namespace {
45 :
46 4610 : class CGPassManager : public ModulePass, public PMDataManager {
47 : public:
48 : static char ID;
49 : explicit CGPassManager()
50 9248 : : ModulePass(ID), PMDataManager() { }
51 :
52 : /// Execute all of the passes scheduled for execution. Keep track of
53 : /// whether any of the passes modifies the module, and if so, return true.
54 : bool runOnModule(Module &M) override;
55 :
56 : using ModulePass::doInitialization;
57 : using ModulePass::doFinalization;
58 :
59 : bool doInitialization(CallGraph &CG);
60 : bool doFinalization(CallGraph &CG);
61 :
62 : /// Pass Manager itself does not invalidate any analysis info.
63 4624 : void getAnalysisUsage(AnalysisUsage &Info) const override {
64 : // CGPassManager walks SCC and it needs CallGraph.
65 : Info.addRequired<CallGraphWrapperPass>();
66 4624 : Info.setPreservesAll();
67 4624 : }
68 :
69 0 : const char *getPassName() const override {
70 0 : return "CallGraph Pass Manager";
71 : }
72 :
73 4629 : PMDataManager *getAsPMDataManager() override { return this; }
74 59782 : Pass *getAsPass() override { return this; }
75 :
76 : // Print passes managed by this manager
77 0 : void dumpPassStructure(unsigned Offset) override {
78 0 : errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n";
79 0 : for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) {
80 0 : Pass *P = getContainedPass(Index);
81 0 : P->dumpPassStructure(Offset + 1);
82 0 : dumpLastUses(P, Offset+1);
83 : }
84 0 : }
85 :
86 : Pass *getContainedPass(unsigned N) {
87 : assert(N < PassVector.size() && "Pass number out of range!");
88 516022 : return static_cast<Pass *>(PassVector[N]);
89 : }
90 :
91 19950 : PassManagerType getPassManagerType() const override {
92 19950 : return PMT_CallGraphPassManager;
93 : }
94 :
95 : private:
96 : bool RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
97 : bool &DevirtualizedCall);
98 :
99 : bool RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
100 : CallGraph &CG, bool &CallGraphUpToDate,
101 : bool &DevirtualizedCall);
102 : bool RefreshCallGraph(CallGraphSCC &CurSCC, CallGraph &CG,
103 : bool IsCheckingMode);
104 : };
105 :
106 : } // end anonymous namespace.
107 :
108 : char CGPassManager::ID = 0;
109 :
110 :
111 213547 : bool CGPassManager::RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC,
112 : CallGraph &CG, bool &CallGraphUpToDate,
113 : bool &DevirtualizedCall) {
114 213547 : bool Changed = false;
115 213547 : PMDataManager *PM = P->getAsPMDataManager();
116 :
117 213547 : if (!PM) {
118 196111 : CallGraphSCCPass *CGSP = (CallGraphSCCPass*)P;
119 196111 : if (!CallGraphUpToDate) {
120 0 : DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
121 0 : CallGraphUpToDate = true;
122 : }
123 :
124 : {
125 196111 : TimeRegion PassTimer(getPassTimer(CGSP));
126 196111 : Changed = CGSP->runOnSCC(CurSCC);
127 : }
128 :
129 : // After the CGSCCPass is done, when assertions are enabled, use
130 : // RefreshCallGraph to verify that the callgraph was correctly updated.
131 : #ifndef NDEBUG
132 : if (Changed)
133 : RefreshCallGraph(CurSCC, CG, true);
134 : #endif
135 :
136 : return Changed;
137 : }
138 :
139 :
140 : assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
141 : "Invalid CGPassManager member");
142 17436 : FPPassManager *FPP = (FPPassManager*)P;
143 :
144 : // Run pass P on all functions in the current SCC.
145 87194 : for (CallGraphNode *CGN : CurSCC) {
146 17450 : if (Function *F = CGN->getFunction()) {
147 16369 : dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName());
148 : {
149 16369 : TimeRegion PassTimer(getPassTimer(FPP));
150 16369 : Changed |= FPP->runOnFunction(*F);
151 : }
152 16369 : F->getContext().yield();
153 : }
154 : }
155 :
156 : // The function pass(es) modified the IR, they may have clobbered the
157 : // callgraph.
158 17436 : if (Changed && CallGraphUpToDate) {
159 : DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: "
160 : << P->getPassName() << '\n');
161 7779 : CallGraphUpToDate = false;
162 : }
163 : return Changed;
164 : }
165 :
166 :
167 : /// Scan the functions in the specified CFG and resync the
168 : /// callgraph with the call sites found in it. This is used after
169 : /// FunctionPasses have potentially munged the callgraph, and can be used after
170 : /// CallGraphSCC passes to verify that they correctly updated the callgraph.
171 : ///
172 : /// This function returns true if it devirtualized an existing function call,
173 : /// meaning it turned an indirect call into a direct call. This happens when
174 : /// a function pass like GVN optimizes away stuff feeding the indirect call.
175 : /// This never happens in checking mode.
176 : ///
177 7779 : bool CGPassManager::RefreshCallGraph(CallGraphSCC &CurSCC,
178 : CallGraph &CG, bool CheckingMode) {
179 : DenseMap<Value*, CallGraphNode*> CallSites;
180 :
181 : DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size()
182 : << " nodes:\n";
183 : for (CallGraphNode *CGN : CurSCC)
184 : CGN->dump();
185 : );
186 :
187 7779 : bool MadeChange = false;
188 7779 : bool DevirtualizedCall = false;
189 :
190 : // Scan all functions in the SCC.
191 7779 : unsigned FunctionNo = 0;
192 38895 : for (CallGraphSCC::iterator SCCIdx = CurSCC.begin(), E = CurSCC.end();
193 : SCCIdx != E; ++SCCIdx, ++FunctionNo) {
194 7779 : CallGraphNode *CGN = *SCCIdx;
195 7779 : Function *F = CGN->getFunction();
196 7779 : if (!F || F->isDeclaration()) continue;
197 :
198 : // Walk the function body looking for call sites. Sync up the call sites in
199 : // CGN with those actually in the function.
200 :
201 : // Keep track of the number of direct and indirect calls that were
202 : // invalidated and removed.
203 7779 : unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0;
204 :
205 : // Get the set of call sites currently in the function.
206 24631 : for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); I != E; ) {
207 : // If this call site is null, then the function pass deleted the call
208 : // entirely and the WeakVH nulled it out.
209 5376 : if (!I->first ||
210 : // If we've already seen this call site, then the FunctionPass RAUW'd
211 : // one call with another, which resulted in two "uses" in the edge
212 : // list of the same call.
213 7992 : CallSites.count(I->first) ||
214 :
215 : // If the call edge is not from a call or invoke, or it is a
216 : // instrinsic call, then the function pass RAUW'd a call with
217 : // another value. This can happen when constant folding happens
218 : // of well known functions etc.
219 7810 : !CallSite(I->first) ||
220 4722 : (CallSite(I->first).getCalledFunction() &&
221 3407 : CallSite(I->first).getCalledFunction()->isIntrinsic() &&
222 12 : Intrinsic::isLeaf(
223 : CallSite(I->first).getCalledFunction()->getIntrinsicID()))) {
224 : assert(!CheckingMode &&
225 : "CallGraphSCCPass did not update the CallGraph correctly!");
226 :
227 : // If this was an indirect call site, count it.
228 246 : if (!I->second->getFunction())
229 26 : ++NumIndirectRemoved;
230 : else
231 97 : ++NumDirectRemoved;
232 :
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 246 : bool WasLast = I + 1 == E;
236 123 : 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 123 : if (WasLast)
242 : break;
243 68 : E = CGN->end();
244 68 : continue;
245 : }
246 :
247 : assert(!CallSites.count(I->first) &&
248 : "Call site occurs in node multiple times");
249 :
250 3678 : CallSite CS(I->first);
251 1226 : if (CS) {
252 1226 : Function *Callee = CS.getCalledFunction();
253 : // Ignore intrinsics because they're not really function calls.
254 1226 : if (!Callee || !(Callee->isIntrinsic()))
255 4896 : CallSites.insert(std::make_pair(I->first, I->second));
256 : }
257 : ++I;
258 : }
259 :
260 : // Loop over all of the instructions in the function, getting the callsites.
261 : // Keep track of the number of direct/indirect calls added.
262 7779 : unsigned NumDirectAdded = 0, NumIndirectAdded = 0;
263 :
264 15558 : for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB)
265 30186 : for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) {
266 102902 : CallSite CS(cast<Value>(I));
267 102777 : if (!CS) continue;
268 8635 : Function *Callee = CS.getCalledFunction();
269 8635 : if (Callee && Callee->isIntrinsic()) continue;
270 :
271 : // If this call site already existed in the callgraph, just verify it
272 : // matches up to expectations and remove it from CallSites.
273 : DenseMap<Value*, CallGraphNode*>::iterator ExistingIt =
274 1349 : CallSites.find(CS.getInstruction());
275 2698 : if (ExistingIt != CallSites.end()) {
276 1224 : CallGraphNode *ExistingNode = ExistingIt->second;
277 :
278 : // Remove from CallSites since we have now seen it.
279 2448 : CallSites.erase(ExistingIt);
280 :
281 : // Verify that the callee is right.
282 2448 : if (ExistingNode->getFunction() == CS.getCalledFunction())
283 : continue;
284 :
285 : // If we are in checking mode, we are not allowed to actually mutate
286 : // the callgraph. If this is a case where we can infer that the
287 : // callgraph is less precise than it could be (e.g. an indirect call
288 : // site could be turned direct), don't reject it in checking mode, and
289 : // don't tweak it to be more precise.
290 7 : if (CheckingMode && CS.getCalledFunction() &&
291 : ExistingNode->getFunction() == nullptr)
292 : continue;
293 :
294 : assert(!CheckingMode &&
295 : "CallGraphSCCPass did not update the CallGraph correctly!");
296 :
297 : // If not, we either went from a direct call to indirect, indirect to
298 : // direct, or direct to different direct.
299 : CallGraphNode *CalleeNode;
300 7 : if (Function *Callee = CS.getCalledFunction()) {
301 7 : CalleeNode = CG.getOrInsertFunction(Callee);
302 : // Keep track of whether we turned an indirect call into a direct
303 : // one.
304 7 : if (!ExistingNode->getFunction()) {
305 7 : DevirtualizedCall = true;
306 : DEBUG(dbgs() << " CGSCCPASSMGR: Devirtualized call to '"
307 : << Callee->getName() << "'\n");
308 : }
309 : } else {
310 0 : CalleeNode = CG.getCallsExternalNode();
311 : }
312 :
313 : // Update the edge target in CGN.
314 7 : CGN->replaceCallEdge(CS, CS, CalleeNode);
315 7 : MadeChange = true;
316 7 : continue;
317 : }
318 :
319 : assert(!CheckingMode &&
320 : "CallGraphSCCPass did not update the CallGraph correctly!");
321 :
322 : // If the call site didn't exist in the CGN yet, add it.
323 : CallGraphNode *CalleeNode;
324 125 : if (Function *Callee = CS.getCalledFunction()) {
325 103 : CalleeNode = CG.getOrInsertFunction(Callee);
326 103 : ++NumDirectAdded;
327 : } else {
328 22 : CalleeNode = CG.getCallsExternalNode();
329 22 : ++NumIndirectAdded;
330 : }
331 :
332 : CGN->addCalledFunction(CS, CalleeNode);
333 125 : MadeChange = true;
334 : }
335 :
336 : // We scanned the old callgraph node, removing invalidated call sites and
337 : // then added back newly found call sites. One thing that can happen is
338 : // that an old indirect call site was deleted and replaced with a new direct
339 : // call. In this case, we have devirtualized a call, and CGSCCPM would like
340 : // to iteratively optimize the new code. Unfortunately, we don't really
341 : // have a great way to detect when this happens. As an approximation, we
342 : // just look at whether the number of indirect calls is reduced and the
343 : // number of direct calls is increased. There are tons of ways to fool this
344 : // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a
345 : // direct call) but this is close enough.
346 15558 : if (NumIndirectRemoved > NumIndirectAdded &&
347 7779 : NumDirectRemoved < NumDirectAdded)
348 1 : DevirtualizedCall = true;
349 :
350 : // After scanning this function, if we still have entries in callsites, then
351 : // they are dangling pointers. WeakVH should save us for this, so abort if
352 : // this happens.
353 : assert(CallSites.empty() && "Dangling pointers found in call sites map");
354 :
355 : // Periodically do an explicit clear to remove tombstones when processing
356 : // large scc's.
357 7779 : if ((FunctionNo & 15) == 15)
358 0 : CallSites.clear();
359 : }
360 :
361 : DEBUG(if (MadeChange) {
362 : dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n";
363 : for (CallGraphNode *CGN : CurSCC)
364 : CGN->dump();
365 : if (DevirtualizedCall)
366 : dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n";
367 :
368 : } else {
369 : dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n";
370 : }
371 : );
372 : (void)MadeChange;
373 :
374 15558 : return DevirtualizedCall;
375 : }
376 :
377 : /// Execute the body of the entire pass manager on the specified SCC.
378 : /// This keeps track of whether a function pass devirtualizes
379 : /// any calls and returns it in DevirtualizedCall.
380 76794 : bool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG,
381 : bool &DevirtualizedCall) {
382 76794 : bool Changed = false;
383 :
384 : // Keep track of whether the callgraph is known to be up-to-date or not.
385 : // The CGSSC pass manager runs two types of passes:
386 : // CallGraphSCC Passes and other random function passes. Because other
387 : // random function passes are not CallGraph aware, they may clobber the
388 : // call graph by introducing new calls or deleting other ones. This flag
389 : // is set to false when we run a function pass so that we know to clean up
390 : // the callgraph when we need to run a CGSCCPass again.
391 76794 : bool CallGraphUpToDate = true;
392 :
393 : // Run all passes on current SCC.
394 367135 : for (unsigned PassNo = 0, e = getNumContainedPasses();
395 290341 : PassNo != e; ++PassNo) {
396 213547 : Pass *P = getContainedPass(PassNo);
397 :
398 : // If we're in -debug-pass=Executions mode, construct the SCC node list,
399 : // otherwise avoid constructing this string as it is expensive.
400 213547 : if (isPassDebuggingExecutionsOrMore()) {
401 0 : std::string Functions;
402 : #ifndef NDEBUG
403 : raw_string_ostream OS(Functions);
404 : for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end();
405 : I != E; ++I) {
406 : if (I != CurSCC.begin()) OS << ", ";
407 : (*I)->print(OS);
408 : }
409 : OS.flush();
410 : #endif
411 0 : dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions);
412 : }
413 213547 : dumpRequiredSet(P);
414 :
415 213547 : initializeAnalysisImpl(P);
416 :
417 : // Actually run this pass on the current SCC.
418 : Changed |= RunPassOnSCC(P, CurSCC, CG,
419 213547 : CallGraphUpToDate, DevirtualizedCall);
420 :
421 213547 : if (Changed)
422 86956 : dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, "");
423 213547 : dumpPreservedSet(P);
424 :
425 213547 : verifyPreservedAnalysis(P);
426 213547 : removeNotPreservedAnalysis(P);
427 213547 : recordAvailableAnalysis(P);
428 213547 : removeDeadPasses(P, "", ON_CG_MSG);
429 : }
430 :
431 : // If the callgraph was left out of date (because the last pass run was a
432 : // functionpass), refresh it before we move on to the next SCC.
433 76794 : if (!CallGraphUpToDate)
434 7779 : DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false);
435 76794 : return Changed;
436 : }
437 :
438 : /// Execute all of the passes scheduled for execution. Keep track of
439 : /// whether any of the passes modifies the module, and if so, return true.
440 4624 : bool CGPassManager::runOnModule(Module &M) {
441 13872 : CallGraph &CG = getAnalysis<CallGraphWrapperPass>().getCallGraph();
442 4624 : bool Changed = doInitialization(CG);
443 :
444 : // Walk the callgraph in bottom-up SCC order.
445 13872 : scc_iterator<CallGraph*> CGI = scc_begin(&CG);
446 :
447 : CallGraphSCC CurSCC(&CGI);
448 158196 : while (!CGI.isAtEnd()) {
449 : // Copy the current SCC and increment past it so that the pass can hack
450 : // on the SCC if it wants to without invalidating our iterator.
451 76786 : const std::vector<CallGraphNode *> &NodeVec = *CGI;
452 153572 : CurSCC.initialize(NodeVec.data(), NodeVec.data() + NodeVec.size());
453 : ++CGI;
454 :
455 : // At the top level, we run all the passes in this pass manager on the
456 : // functions in this SCC. However, we support iterative compilation in the
457 : // case where a function pass devirtualizes a call to a function. For
458 : // example, it is very common for a function pass (often GVN or instcombine)
459 : // to eliminate the addressing that feeds into a call. With that improved
460 : // information, we would like the call to be an inline candidate, infer
461 : // mod-ref information etc.
462 : //
463 : // Because of this, we allow iteration up to a specified iteration count.
464 : // This only happens in the case of a devirtualized call, so we only burn
465 : // compile time in the case that we're making progress. We also have a hard
466 : // iteration count limit in case there is crazy code.
467 76786 : unsigned Iteration = 0;
468 76786 : bool DevirtualizedCall = false;
469 76794 : do {
470 : DEBUG(if (Iteration)
471 : dbgs() << " SCCPASSMGR: Re-visiting SCC, iteration #"
472 : << Iteration << '\n');
473 76794 : DevirtualizedCall = false;
474 76794 : Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall);
475 153588 : } while (Iteration++ < MaxIterations && DevirtualizedCall);
476 :
477 76786 : if (DevirtualizedCall)
478 : DEBUG(dbgs() << " CGSCCPASSMGR: Stopped iteration after " << Iteration
479 : << " times, due to -max-cg-scc-iterations\n");
480 :
481 : if (Iteration > MaxSCCIterations)
482 : MaxSCCIterations = Iteration;
483 :
484 : }
485 4624 : Changed |= doFinalization(CG);
486 9248 : return Changed;
487 : }
488 :
489 :
490 : /// Initialize CG
491 4624 : bool CGPassManager::doInitialization(CallGraph &CG) {
492 4624 : bool Changed = false;
493 20758 : for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
494 11510 : if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
495 : assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
496 : "Invalid CGPassManager member");
497 788 : Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule());
498 : } else {
499 10722 : Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG);
500 : }
501 : }
502 4624 : return Changed;
503 : }
504 :
505 : /// Finalize CG
506 4624 : bool CGPassManager::doFinalization(CallGraph &CG) {
507 4624 : bool Changed = false;
508 20758 : for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) {
509 11510 : if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) {
510 : assert(PM->getPassManagerType() == PMT_FunctionPassManager &&
511 : "Invalid CGPassManager member");
512 788 : Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule());
513 : } else {
514 10722 : Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG);
515 : }
516 : }
517 4624 : return Changed;
518 : }
519 :
520 : //===----------------------------------------------------------------------===//
521 : // CallGraphSCC Implementation
522 : //===----------------------------------------------------------------------===//
523 :
524 : /// This informs the SCC and the pass manager that the specified
525 : /// Old node has been deleted, and New is to be used in its place.
526 38 : void CallGraphSCC::ReplaceNode(CallGraphNode *Old, CallGraphNode *New) {
527 : assert(Old != New && "Should not replace node with self");
528 38 : for (unsigned i = 0; ; ++i) {
529 : assert(i != Nodes.size() && "Node not in SCC");
530 76 : if (Nodes[i] != Old) continue;
531 38 : Nodes[i] = New;
532 : break;
533 : }
534 :
535 : // Update the active scc_iterator so that it doesn't contain dangling
536 : // pointers to the old CallGraphNode.
537 38 : scc_iterator<CallGraph*> *CGI = (scc_iterator<CallGraph*>*)Context;
538 38 : CGI->ReplaceNode(Old, New);
539 38 : }
540 :
541 :
542 : //===----------------------------------------------------------------------===//
543 : // CallGraphSCCPass Implementation
544 : //===----------------------------------------------------------------------===//
545 :
546 : /// Assign pass manager to manage this pass.
547 10722 : void CallGraphSCCPass::assignPassManager(PMStack &PMS,
548 : PassManagerType PreferredType) {
549 : // Find CGPassManager
550 21444 : while (!PMS.empty() &&
551 10722 : PMS.top()->getPassManagerType() > PMT_CallGraphPassManager)
552 0 : PMS.pop();
553 :
554 : assert(!PMS.empty() && "Unable to handle Call Graph Pass");
555 : CGPassManager *CGP;
556 :
557 10722 : if (PMS.top()->getPassManagerType() == PMT_CallGraphPassManager)
558 6098 : CGP = (CGPassManager*)PMS.top();
559 : else {
560 : // Create new Call Graph SCC Pass Manager if it does not exist.
561 : assert(!PMS.empty() && "Unable to create Call Graph Pass Manager");
562 4624 : PMDataManager *PMD = PMS.top();
563 :
564 : // [1] Create new Call Graph Pass Manager
565 9248 : CGP = new CGPassManager();
566 :
567 : // [2] Set up new manager's top level manager
568 4624 : PMTopLevelManager *TPM = PMD->getTopLevelManager();
569 4624 : TPM->addIndirectPassManager(CGP);
570 :
571 : // [3] Assign manager to manage this new manager. This may create
572 : // and push new managers into PMS
573 4624 : Pass *P = CGP;
574 4624 : TPM->schedulePass(P);
575 :
576 : // [4] Push new manager into PMS
577 4624 : PMS.push(CGP);
578 : }
579 :
580 10722 : CGP->add(this);
581 10722 : }
582 :
583 : /// For this class, we declare that we require and preserve the call graph.
584 : /// If the derived class implements this method, it should
585 : /// always explicitly call the implementation here.
586 10720 : void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const {
587 10720 : AU.addRequired<CallGraphWrapperPass>();
588 : AU.addPreserved<CallGraphWrapperPass>();
589 10720 : }
590 :
591 :
592 : //===----------------------------------------------------------------------===//
593 : // PrintCallGraphPass Implementation
594 : //===----------------------------------------------------------------------===//
595 :
596 : namespace {
597 : /// PrintCallGraphPass - Print a Module corresponding to a call graph.
598 : ///
599 4 : class PrintCallGraphPass : public CallGraphSCCPass {
600 : std::string Banner;
601 : raw_ostream &Out; // raw_ostream to print on.
602 :
603 : public:
604 : static char ID;
605 : PrintCallGraphPass(const std::string &B, raw_ostream &o)
606 3 : : CallGraphSCCPass(ID), Banner(B), Out(o) {}
607 :
608 1 : void getAnalysisUsage(AnalysisUsage &AU) const override {
609 1 : AU.setPreservesAll();
610 1 : }
611 :
612 2 : bool runOnSCC(CallGraphSCC &SCC) override {
613 2 : Out << Banner;
614 10 : for (CallGraphNode *CGN : SCC) {
615 2 : if (CGN->getFunction())
616 2 : CGN->getFunction()->print(Out);
617 : else
618 1 : Out << "\nPrinting <null> Function\n";
619 : }
620 2 : return false;
621 : }
622 : };
623 :
624 : } // end anonymous namespace.
625 :
626 : char PrintCallGraphPass::ID = 0;
627 :
628 1 : Pass *CallGraphSCCPass::createPrinterPass(raw_ostream &O,
629 : const std::string &Banner) const {
630 2 : return new PrintCallGraphPass(Banner, O);
631 116490 : }
632 :
|