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