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