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) {} 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