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