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