1193323Sed//===- CallGraphSCCPass.cpp - Pass that operates BU on call graph ---------===// 2193323Sed// 3193323Sed// The LLVM Compiler Infrastructure 4193323Sed// 5193323Sed// This file is distributed under the University of Illinois Open Source 6193323Sed// License. See LICENSE.TXT for details. 7193323Sed// 8193323Sed//===----------------------------------------------------------------------===// 9193323Sed// 10193323Sed// This file implements the CallGraphSCCPass class, which is used for passes 11193323Sed// which are implemented as bottom-up traversals on the call graph. Because 12193323Sed// there may be cycles in the call graph, passes of this type operate on the 13193323Sed// call-graph in SCC order: that is, they process function bottom-up, except for 14193323Sed// recursive functions, which they process all at once. 15193323Sed// 16193323Sed//===----------------------------------------------------------------------===// 17193323Sed 18198090Srdivacky#define DEBUG_TYPE "cgscc-passmgr" 19249423Sdim#include "llvm/Analysis/CallGraphSCCPass.h" 20193323Sed#include "llvm/ADT/SCCIterator.h" 21207618Srdivacky#include "llvm/ADT/Statistic.h" 22249423Sdim#include "llvm/Analysis/CallGraph.h" 23249423Sdim#include "llvm/IR/Function.h" 24249423Sdim#include "llvm/IR/IntrinsicInst.h" 25263508Sdim#include "llvm/IR/LegacyPassManagers.h" 26207618Srdivacky#include "llvm/Support/CommandLine.h" 27198090Srdivacky#include "llvm/Support/Debug.h" 28206083Srdivacky#include "llvm/Support/Timer.h" 29198090Srdivacky#include "llvm/Support/raw_ostream.h" 30193323Sedusing namespace llvm; 31193323Sed 32207618Srdivackystatic cl::opt<unsigned> 33207618SrdivackyMaxIterations("max-cg-scc-iterations", cl::ReallyHidden, cl::init(4)); 34207618Srdivacky 35207618SrdivackySTATISTIC(MaxSCCIterations, "Maximum CGSCCPassMgr iterations on one SCC"); 36207618Srdivacky 37193323Sed//===----------------------------------------------------------------------===// 38193323Sed// CGPassManager 39193323Sed// 40198090Srdivacky/// CGPassManager manages FPPassManagers and CallGraphSCCPasses. 41193323Sed 42193323Sednamespace { 43193323Sed 44193323Sedclass CGPassManager : public ModulePass, public PMDataManager { 45193323Sedpublic: 46193323Sed static char ID; 47226633Sdim explicit CGPassManager() 48226633Sdim : ModulePass(ID), PMDataManager() { } 49193323Sed 50193323Sed /// run - Execute all of the passes scheduled for execution. Keep track of 51193323Sed /// whether any of the passes modifies the module, and if so, return true. 52193323Sed bool runOnModule(Module &M); 53193323Sed 54249423Sdim using ModulePass::doInitialization; 55249423Sdim using ModulePass::doFinalization; 56249423Sdim 57193323Sed bool doInitialization(CallGraph &CG); 58193323Sed bool doFinalization(CallGraph &CG); 59193323Sed 60193323Sed /// Pass Manager itself does not invalidate any analysis info. 61193323Sed void getAnalysisUsage(AnalysisUsage &Info) const { 62193323Sed // CGPassManager walks SCC and it needs CallGraph. 63193323Sed Info.addRequired<CallGraph>(); 64193323Sed Info.setPreservesAll(); 65193323Sed } 66193323Sed 67193323Sed virtual const char *getPassName() const { 68193323Sed return "CallGraph Pass Manager"; 69193323Sed } 70193323Sed 71202878Srdivacky virtual PMDataManager *getAsPMDataManager() { return this; } 72202878Srdivacky virtual Pass *getAsPass() { return this; } 73202878Srdivacky 74193323Sed // Print passes managed by this manager 75193323Sed void dumpPassStructure(unsigned Offset) { 76198090Srdivacky errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n"; 77193323Sed for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 78193323Sed Pass *P = getContainedPass(Index); 79193323Sed P->dumpPassStructure(Offset + 1); 80193323Sed dumpLastUses(P, Offset+1); 81193323Sed } 82193323Sed } 83193323Sed 84193323Sed Pass *getContainedPass(unsigned N) { 85198090Srdivacky assert(N < PassVector.size() && "Pass number out of range!"); 86198090Srdivacky return static_cast<Pass *>(PassVector[N]); 87193323Sed } 88193323Sed 89193323Sed virtual PassManagerType getPassManagerType() const { 90193323Sed return PMT_CallGraphPassManager; 91193323Sed } 92198090Srdivacky 93198090Srdivackyprivate: 94207618Srdivacky bool RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG, 95207618Srdivacky bool &DevirtualizedCall); 96207618Srdivacky 97207618Srdivacky bool RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC, 98207618Srdivacky CallGraph &CG, bool &CallGraphUpToDate, 99207618Srdivacky bool &DevirtualizedCall); 100207618Srdivacky bool RefreshCallGraph(CallGraphSCC &CurSCC, CallGraph &CG, 101198090Srdivacky bool IsCheckingMode); 102193323Sed}; 103193323Sed 104198090Srdivacky} // end anonymous namespace. 105198090Srdivacky 106198090Srdivackychar CGPassManager::ID = 0; 107198090Srdivacky 108206124Srdivacky 109207618Srdivackybool CGPassManager::RunPassOnSCC(Pass *P, CallGraphSCC &CurSCC, 110207618Srdivacky CallGraph &CG, bool &CallGraphUpToDate, 111207618Srdivacky bool &DevirtualizedCall) { 112198090Srdivacky bool Changed = false; 113202878Srdivacky PMDataManager *PM = P->getAsPMDataManager(); 114202878Srdivacky 115202878Srdivacky if (PM == 0) { 116202878Srdivacky CallGraphSCCPass *CGSP = (CallGraphSCCPass*)P; 117198090Srdivacky if (!CallGraphUpToDate) { 118207618Srdivacky DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false); 119198090Srdivacky CallGraphUpToDate = true; 120198090Srdivacky } 121198090Srdivacky 122206083Srdivacky { 123206083Srdivacky TimeRegion PassTimer(getPassTimer(CGSP)); 124206083Srdivacky Changed = CGSP->runOnSCC(CurSCC); 125206083Srdivacky } 126198090Srdivacky 127198090Srdivacky // After the CGSCCPass is done, when assertions are enabled, use 128198090Srdivacky // RefreshCallGraph to verify that the callgraph was correctly updated. 129198090Srdivacky#ifndef NDEBUG 130198090Srdivacky if (Changed) 131198090Srdivacky RefreshCallGraph(CurSCC, CG, true); 132198090Srdivacky#endif 133198090Srdivacky 134198090Srdivacky return Changed; 135198090Srdivacky } 136198090Srdivacky 137198090Srdivacky 138202878Srdivacky assert(PM->getPassManagerType() == PMT_FunctionPassManager && 139202878Srdivacky "Invalid CGPassManager member"); 140202878Srdivacky FPPassManager *FPP = (FPPassManager*)P; 141202878Srdivacky 142198090Srdivacky // Run pass P on all functions in the current SCC. 143207618Srdivacky for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end(); 144207618Srdivacky I != E; ++I) { 145207618Srdivacky if (Function *F = (*I)->getFunction()) { 146198090Srdivacky dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName()); 147206083Srdivacky TimeRegion PassTimer(getPassTimer(FPP)); 148198090Srdivacky Changed |= FPP->runOnFunction(*F); 149198090Srdivacky } 150198090Srdivacky } 151198090Srdivacky 152198090Srdivacky // The function pass(es) modified the IR, they may have clobbered the 153198090Srdivacky // callgraph. 154198090Srdivacky if (Changed && CallGraphUpToDate) { 155201360Srdivacky DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: " 156198090Srdivacky << P->getPassName() << '\n'); 157198090Srdivacky CallGraphUpToDate = false; 158198090Srdivacky } 159198090Srdivacky return Changed; 160193323Sed} 161193323Sed 162198090Srdivacky 163198090Srdivacky/// RefreshCallGraph - Scan the functions in the specified CFG and resync the 164198090Srdivacky/// callgraph with the call sites found in it. This is used after 165198090Srdivacky/// FunctionPasses have potentially munged the callgraph, and can be used after 166198090Srdivacky/// CallGraphSCC passes to verify that they correctly updated the callgraph. 167198090Srdivacky/// 168207618Srdivacky/// This function returns true if it devirtualized an existing function call, 169207618Srdivacky/// meaning it turned an indirect call into a direct call. This happens when 170207618Srdivacky/// a function pass like GVN optimizes away stuff feeding the indirect call. 171207618Srdivacky/// This never happens in checking mode. 172207618Srdivacky/// 173207618Srdivackybool CGPassManager::RefreshCallGraph(CallGraphSCC &CurSCC, 174198090Srdivacky CallGraph &CG, bool CheckingMode) { 175198090Srdivacky DenseMap<Value*, CallGraphNode*> CallSites; 176198090Srdivacky 177201360Srdivacky DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size() 178198090Srdivacky << " nodes:\n"; 179207618Srdivacky for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end(); 180207618Srdivacky I != E; ++I) 181207618Srdivacky (*I)->dump(); 182198090Srdivacky ); 183198090Srdivacky 184198090Srdivacky bool MadeChange = false; 185207618Srdivacky bool DevirtualizedCall = false; 186198090Srdivacky 187198090Srdivacky // Scan all functions in the SCC. 188207618Srdivacky unsigned FunctionNo = 0; 189207618Srdivacky for (CallGraphSCC::iterator SCCIdx = CurSCC.begin(), E = CurSCC.end(); 190207618Srdivacky SCCIdx != E; ++SCCIdx, ++FunctionNo) { 191207618Srdivacky CallGraphNode *CGN = *SCCIdx; 192198090Srdivacky Function *F = CGN->getFunction(); 193198090Srdivacky if (F == 0 || F->isDeclaration()) continue; 194198090Srdivacky 195198090Srdivacky // Walk the function body looking for call sites. Sync up the call sites in 196198090Srdivacky // CGN with those actually in the function. 197207618Srdivacky 198207618Srdivacky // Keep track of the number of direct and indirect calls that were 199207618Srdivacky // invalidated and removed. 200207618Srdivacky unsigned NumDirectRemoved = 0, NumIndirectRemoved = 0; 201198090Srdivacky 202198090Srdivacky // Get the set of call sites currently in the function. 203198090Srdivacky for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); I != E; ) { 204198090Srdivacky // If this call site is null, then the function pass deleted the call 205198090Srdivacky // entirely and the WeakVH nulled it out. 206198090Srdivacky if (I->first == 0 || 207198090Srdivacky // If we've already seen this call site, then the FunctionPass RAUW'd 208198090Srdivacky // one call with another, which resulted in two "uses" in the edge 209198090Srdivacky // list of the same call. 210198090Srdivacky CallSites.count(I->first) || 211198090Srdivacky 212198090Srdivacky // If the call edge is not from a call or invoke, then the function 213198090Srdivacky // pass RAUW'd a call with another value. This can happen when 214198090Srdivacky // constant folding happens of well known functions etc. 215212904Sdim !CallSite(I->first)) { 216198090Srdivacky assert(!CheckingMode && 217198090Srdivacky "CallGraphSCCPass did not update the CallGraph correctly!"); 218198090Srdivacky 219207618Srdivacky // If this was an indirect call site, count it. 220207618Srdivacky if (I->second->getFunction() == 0) 221207618Srdivacky ++NumIndirectRemoved; 222207618Srdivacky else 223207618Srdivacky ++NumDirectRemoved; 224207618Srdivacky 225198090Srdivacky // Just remove the edge from the set of callees, keep track of whether 226198090Srdivacky // I points to the last element of the vector. 227198090Srdivacky bool WasLast = I + 1 == E; 228198090Srdivacky CGN->removeCallEdge(I); 229198090Srdivacky 230198090Srdivacky // If I pointed to the last element of the vector, we have to bail out: 231198090Srdivacky // iterator checking rejects comparisons of the resultant pointer with 232198090Srdivacky // end. 233198090Srdivacky if (WasLast) 234198090Srdivacky break; 235198090Srdivacky E = CGN->end(); 236198090Srdivacky continue; 237198090Srdivacky } 238198090Srdivacky 239198090Srdivacky assert(!CallSites.count(I->first) && 240198090Srdivacky "Call site occurs in node multiple times"); 241198090Srdivacky CallSites.insert(std::make_pair(I->first, I->second)); 242198090Srdivacky ++I; 243198090Srdivacky } 244198090Srdivacky 245198090Srdivacky // Loop over all of the instructions in the function, getting the callsites. 246207618Srdivacky // Keep track of the number of direct/indirect calls added. 247207618Srdivacky unsigned NumDirectAdded = 0, NumIndirectAdded = 0; 248207618Srdivacky 249198090Srdivacky for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 250198090Srdivacky for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 251223017Sdim CallSite CS(cast<Value>(I)); 252239462Sdim if (!CS) continue; 253239462Sdim Function *Callee = CS.getCalledFunction(); 254239462Sdim if (Callee && Callee->isIntrinsic()) continue; 255198090Srdivacky 256198090Srdivacky // If this call site already existed in the callgraph, just verify it 257198090Srdivacky // matches up to expectations and remove it from CallSites. 258198090Srdivacky DenseMap<Value*, CallGraphNode*>::iterator ExistingIt = 259198090Srdivacky CallSites.find(CS.getInstruction()); 260198090Srdivacky if (ExistingIt != CallSites.end()) { 261198090Srdivacky CallGraphNode *ExistingNode = ExistingIt->second; 262198090Srdivacky 263198090Srdivacky // Remove from CallSites since we have now seen it. 264198090Srdivacky CallSites.erase(ExistingIt); 265198090Srdivacky 266198090Srdivacky // Verify that the callee is right. 267198090Srdivacky if (ExistingNode->getFunction() == CS.getCalledFunction()) 268198090Srdivacky continue; 269198090Srdivacky 270198090Srdivacky // If we are in checking mode, we are not allowed to actually mutate 271198090Srdivacky // the callgraph. If this is a case where we can infer that the 272198090Srdivacky // callgraph is less precise than it could be (e.g. an indirect call 273198090Srdivacky // site could be turned direct), don't reject it in checking mode, and 274198090Srdivacky // don't tweak it to be more precise. 275198090Srdivacky if (CheckingMode && CS.getCalledFunction() && 276198090Srdivacky ExistingNode->getFunction() == 0) 277198090Srdivacky continue; 278198090Srdivacky 279198090Srdivacky assert(!CheckingMode && 280198090Srdivacky "CallGraphSCCPass did not update the CallGraph correctly!"); 281198090Srdivacky 282198090Srdivacky // If not, we either went from a direct call to indirect, indirect to 283198090Srdivacky // direct, or direct to different direct. 284198090Srdivacky CallGraphNode *CalleeNode; 285207618Srdivacky if (Function *Callee = CS.getCalledFunction()) { 286198090Srdivacky CalleeNode = CG.getOrInsertFunction(Callee); 287207618Srdivacky // Keep track of whether we turned an indirect call into a direct 288207618Srdivacky // one. 289207618Srdivacky if (ExistingNode->getFunction() == 0) { 290207618Srdivacky DevirtualizedCall = true; 291207618Srdivacky DEBUG(dbgs() << " CGSCCPASSMGR: Devirtualized call to '" 292207618Srdivacky << Callee->getName() << "'\n"); 293207618Srdivacky } 294207618Srdivacky } else { 295198090Srdivacky CalleeNode = CG.getCallsExternalNode(); 296207618Srdivacky } 297198090Srdivacky 298198090Srdivacky // Update the edge target in CGN. 299207618Srdivacky CGN->replaceCallEdge(CS, CS, CalleeNode); 300198090Srdivacky MadeChange = true; 301198090Srdivacky continue; 302198090Srdivacky } 303198090Srdivacky 304198090Srdivacky assert(!CheckingMode && 305198090Srdivacky "CallGraphSCCPass did not update the CallGraph correctly!"); 306198090Srdivacky 307207618Srdivacky // If the call site didn't exist in the CGN yet, add it. 308198090Srdivacky CallGraphNode *CalleeNode; 309207618Srdivacky if (Function *Callee = CS.getCalledFunction()) { 310198090Srdivacky CalleeNode = CG.getOrInsertFunction(Callee); 311207618Srdivacky ++NumDirectAdded; 312207618Srdivacky } else { 313198090Srdivacky CalleeNode = CG.getCallsExternalNode(); 314207618Srdivacky ++NumIndirectAdded; 315207618Srdivacky } 316198090Srdivacky 317198090Srdivacky CGN->addCalledFunction(CS, CalleeNode); 318198090Srdivacky MadeChange = true; 319198090Srdivacky } 320198090Srdivacky 321207618Srdivacky // We scanned the old callgraph node, removing invalidated call sites and 322207618Srdivacky // then added back newly found call sites. One thing that can happen is 323207618Srdivacky // that an old indirect call site was deleted and replaced with a new direct 324207618Srdivacky // call. In this case, we have devirtualized a call, and CGSCCPM would like 325207618Srdivacky // to iteratively optimize the new code. Unfortunately, we don't really 326207618Srdivacky // have a great way to detect when this happens. As an approximation, we 327207618Srdivacky // just look at whether the number of indirect calls is reduced and the 328207618Srdivacky // number of direct calls is increased. There are tons of ways to fool this 329207618Srdivacky // (e.g. DCE'ing an indirect call and duplicating an unrelated block with a 330207618Srdivacky // direct call) but this is close enough. 331207618Srdivacky if (NumIndirectRemoved > NumIndirectAdded && 332207618Srdivacky NumDirectRemoved < NumDirectAdded) 333207618Srdivacky DevirtualizedCall = true; 334207618Srdivacky 335198090Srdivacky // After scanning this function, if we still have entries in callsites, then 336198090Srdivacky // they are dangling pointers. WeakVH should save us for this, so abort if 337198090Srdivacky // this happens. 338198090Srdivacky assert(CallSites.empty() && "Dangling pointers found in call sites map"); 339198090Srdivacky 340198090Srdivacky // Periodically do an explicit clear to remove tombstones when processing 341198090Srdivacky // large scc's. 342207618Srdivacky if ((FunctionNo & 15) == 15) 343198090Srdivacky CallSites.clear(); 344198090Srdivacky } 345198090Srdivacky 346198090Srdivacky DEBUG(if (MadeChange) { 347201360Srdivacky dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n"; 348207618Srdivacky for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end(); 349207618Srdivacky I != E; ++I) 350207618Srdivacky (*I)->dump(); 351207618Srdivacky if (DevirtualizedCall) 352207618Srdivacky dbgs() << "CGSCCPASSMGR: Refresh devirtualized a call!\n"; 353207618Srdivacky 354198090Srdivacky } else { 355201360Srdivacky dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n"; 356198090Srdivacky } 357198090Srdivacky ); 358226633Sdim (void)MadeChange; 359207618Srdivacky 360207618Srdivacky return DevirtualizedCall; 361198090Srdivacky} 362198090Srdivacky 363207618Srdivacky/// RunAllPassesOnSCC - Execute the body of the entire pass manager on the 364207618Srdivacky/// specified SCC. This keeps track of whether a function pass devirtualizes 365207618Srdivacky/// any calls and returns it in DevirtualizedCall. 366207618Srdivackybool CGPassManager::RunAllPassesOnSCC(CallGraphSCC &CurSCC, CallGraph &CG, 367207618Srdivacky bool &DevirtualizedCall) { 368207618Srdivacky bool Changed = false; 369207618Srdivacky 370207618Srdivacky // CallGraphUpToDate - Keep track of whether the callgraph is known to be 371207618Srdivacky // up-to-date or not. The CGSSC pass manager runs two types of passes: 372207618Srdivacky // CallGraphSCC Passes and other random function passes. Because other 373207618Srdivacky // random function passes are not CallGraph aware, they may clobber the 374207618Srdivacky // call graph by introducing new calls or deleting other ones. This flag 375207618Srdivacky // is set to false when we run a function pass so that we know to clean up 376207618Srdivacky // the callgraph when we need to run a CGSCCPass again. 377207618Srdivacky bool CallGraphUpToDate = true; 378207618Srdivacky 379207618Srdivacky // Run all passes on current SCC. 380207618Srdivacky for (unsigned PassNo = 0, e = getNumContainedPasses(); 381207618Srdivacky PassNo != e; ++PassNo) { 382207618Srdivacky Pass *P = getContainedPass(PassNo); 383207618Srdivacky 384207618Srdivacky // If we're in -debug-pass=Executions mode, construct the SCC node list, 385207618Srdivacky // otherwise avoid constructing this string as it is expensive. 386207618Srdivacky if (isPassDebuggingExecutionsOrMore()) { 387207618Srdivacky std::string Functions; 388207618Srdivacky #ifndef NDEBUG 389207618Srdivacky raw_string_ostream OS(Functions); 390207618Srdivacky for (CallGraphSCC::iterator I = CurSCC.begin(), E = CurSCC.end(); 391207618Srdivacky I != E; ++I) { 392207618Srdivacky if (I != CurSCC.begin()) OS << ", "; 393207618Srdivacky (*I)->print(OS); 394207618Srdivacky } 395207618Srdivacky OS.flush(); 396207618Srdivacky #endif 397207618Srdivacky dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions); 398207618Srdivacky } 399207618Srdivacky dumpRequiredSet(P); 400207618Srdivacky 401207618Srdivacky initializeAnalysisImpl(P); 402207618Srdivacky 403207618Srdivacky // Actually run this pass on the current SCC. 404207618Srdivacky Changed |= RunPassOnSCC(P, CurSCC, CG, 405207618Srdivacky CallGraphUpToDate, DevirtualizedCall); 406207618Srdivacky 407207618Srdivacky if (Changed) 408207618Srdivacky dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, ""); 409207618Srdivacky dumpPreservedSet(P); 410207618Srdivacky 411207618Srdivacky verifyPreservedAnalysis(P); 412207618Srdivacky removeNotPreservedAnalysis(P); 413207618Srdivacky recordAvailableAnalysis(P); 414207618Srdivacky removeDeadPasses(P, "", ON_CG_MSG); 415207618Srdivacky } 416207618Srdivacky 417207618Srdivacky // If the callgraph was left out of date (because the last pass run was a 418207618Srdivacky // functionpass), refresh it before we move on to the next SCC. 419207618Srdivacky if (!CallGraphUpToDate) 420207618Srdivacky DevirtualizedCall |= RefreshCallGraph(CurSCC, CG, false); 421207618Srdivacky return Changed; 422207618Srdivacky} 423207618Srdivacky 424193323Sed/// run - Execute all of the passes scheduled for execution. Keep track of 425193323Sed/// whether any of the passes modifies the module, and if so, return true. 426193323Sedbool CGPassManager::runOnModule(Module &M) { 427193323Sed CallGraph &CG = getAnalysis<CallGraph>(); 428193323Sed bool Changed = doInitialization(CG); 429198090Srdivacky 430198090Srdivacky // Walk the callgraph in bottom-up SCC order. 431207618Srdivacky scc_iterator<CallGraph*> CGI = scc_begin(&CG); 432207618Srdivacky 433207618Srdivacky CallGraphSCC CurSCC(&CGI); 434207618Srdivacky while (!CGI.isAtEnd()) { 435198090Srdivacky // Copy the current SCC and increment past it so that the pass can hack 436198090Srdivacky // on the SCC if it wants to without invalidating our iterator. 437207618Srdivacky std::vector<CallGraphNode*> &NodeVec = *CGI; 438207618Srdivacky CurSCC.initialize(&NodeVec[0], &NodeVec[0]+NodeVec.size()); 439198090Srdivacky ++CGI; 440198090Srdivacky 441207618Srdivacky // At the top level, we run all the passes in this pass manager on the 442207618Srdivacky // functions in this SCC. However, we support iterative compilation in the 443207618Srdivacky // case where a function pass devirtualizes a call to a function. For 444207618Srdivacky // example, it is very common for a function pass (often GVN or instcombine) 445207618Srdivacky // to eliminate the addressing that feeds into a call. With that improved 446207618Srdivacky // information, we would like the call to be an inline candidate, infer 447207618Srdivacky // mod-ref information etc. 448207618Srdivacky // 449207618Srdivacky // Because of this, we allow iteration up to a specified iteration count. 450207618Srdivacky // This only happens in the case of a devirtualized call, so we only burn 451207618Srdivacky // compile time in the case that we're making progress. We also have a hard 452207618Srdivacky // iteration count limit in case there is crazy code. 453207618Srdivacky unsigned Iteration = 0; 454207618Srdivacky bool DevirtualizedCall = false; 455207618Srdivacky do { 456207618Srdivacky DEBUG(if (Iteration) 457207618Srdivacky dbgs() << " SCCPASSMGR: Re-visiting SCC, iteration #" 458207618Srdivacky << Iteration << '\n'); 459207618Srdivacky DevirtualizedCall = false; 460207618Srdivacky Changed |= RunAllPassesOnSCC(CurSCC, CG, DevirtualizedCall); 461207618Srdivacky } while (Iteration++ < MaxIterations && DevirtualizedCall); 462198090Srdivacky 463207618Srdivacky if (DevirtualizedCall) 464207618Srdivacky DEBUG(dbgs() << " CGSCCPASSMGR: Stopped iteration after " << Iteration 465207618Srdivacky << " times, due to -max-cg-scc-iterations\n"); 466198090Srdivacky 467207618Srdivacky if (Iteration > MaxSCCIterations) 468207618Srdivacky MaxSCCIterations = Iteration; 469198090Srdivacky 470193323Sed } 471193323Sed Changed |= doFinalization(CG); 472193323Sed return Changed; 473193323Sed} 474193323Sed 475207618Srdivacky 476193323Sed/// Initialize CG 477193323Sedbool CGPassManager::doInitialization(CallGraph &CG) { 478193323Sed bool Changed = false; 479202878Srdivacky for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) { 480202878Srdivacky if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) { 481202878Srdivacky assert(PM->getPassManagerType() == PMT_FunctionPassManager && 482202878Srdivacky "Invalid CGPassManager member"); 483202878Srdivacky Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule()); 484193323Sed } else { 485202878Srdivacky Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG); 486193323Sed } 487193323Sed } 488193323Sed return Changed; 489193323Sed} 490193323Sed 491193323Sed/// Finalize CG 492193323Sedbool CGPassManager::doFinalization(CallGraph &CG) { 493193323Sed bool Changed = false; 494202878Srdivacky for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) { 495202878Srdivacky if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) { 496202878Srdivacky assert(PM->getPassManagerType() == PMT_FunctionPassManager && 497202878Srdivacky "Invalid CGPassManager member"); 498202878Srdivacky Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule()); 499193323Sed } else { 500202878Srdivacky Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG); 501193323Sed } 502193323Sed } 503193323Sed return Changed; 504193323Sed} 505193323Sed 506207618Srdivacky//===----------------------------------------------------------------------===// 507207618Srdivacky// CallGraphSCC Implementation 508207618Srdivacky//===----------------------------------------------------------------------===// 509207618Srdivacky 510207618Srdivacky/// ReplaceNode - This informs the SCC and the pass manager that the specified 511207618Srdivacky/// Old node has been deleted, and New is to be used in its place. 512207618Srdivackyvoid CallGraphSCC::ReplaceNode(CallGraphNode *Old, CallGraphNode *New) { 513207618Srdivacky assert(Old != New && "Should not replace node with self"); 514207618Srdivacky for (unsigned i = 0; ; ++i) { 515207618Srdivacky assert(i != Nodes.size() && "Node not in SCC"); 516207618Srdivacky if (Nodes[i] != Old) continue; 517207618Srdivacky Nodes[i] = New; 518207618Srdivacky break; 519207618Srdivacky } 520207618Srdivacky 521207618Srdivacky // Update the active scc_iterator so that it doesn't contain dangling 522207618Srdivacky // pointers to the old CallGraphNode. 523207618Srdivacky scc_iterator<CallGraph*> *CGI = (scc_iterator<CallGraph*>*)Context; 524207618Srdivacky CGI->ReplaceNode(Old, New); 525206124Srdivacky} 526206124Srdivacky 527207618Srdivacky 528207618Srdivacky//===----------------------------------------------------------------------===// 529207618Srdivacky// CallGraphSCCPass Implementation 530207618Srdivacky//===----------------------------------------------------------------------===// 531207618Srdivacky 532193323Sed/// Assign pass manager to manage this pass. 533193323Sedvoid CallGraphSCCPass::assignPassManager(PMStack &PMS, 534193323Sed PassManagerType PreferredType) { 535193323Sed // Find CGPassManager 536193323Sed while (!PMS.empty() && 537193323Sed PMS.top()->getPassManagerType() > PMT_CallGraphPassManager) 538193323Sed PMS.pop(); 539193323Sed 540202878Srdivacky assert(!PMS.empty() && "Unable to handle Call Graph Pass"); 541202878Srdivacky CGPassManager *CGP; 542202878Srdivacky 543202878Srdivacky if (PMS.top()->getPassManagerType() == PMT_CallGraphPassManager) 544202878Srdivacky CGP = (CGPassManager*)PMS.top(); 545202878Srdivacky else { 546202878Srdivacky // Create new Call Graph SCC Pass Manager if it does not exist. 547202878Srdivacky assert(!PMS.empty() && "Unable to create Call Graph Pass Manager"); 548193323Sed PMDataManager *PMD = PMS.top(); 549193323Sed 550193323Sed // [1] Create new Call Graph Pass Manager 551226633Sdim CGP = new CGPassManager(); 552193323Sed 553193323Sed // [2] Set up new manager's top level manager 554193323Sed PMTopLevelManager *TPM = PMD->getTopLevelManager(); 555193323Sed TPM->addIndirectPassManager(CGP); 556193323Sed 557193323Sed // [3] Assign manager to manage this new manager. This may create 558193323Sed // and push new managers into PMS 559202878Srdivacky Pass *P = CGP; 560193323Sed TPM->schedulePass(P); 561193323Sed 562193323Sed // [4] Push new manager into PMS 563193323Sed PMS.push(CGP); 564193323Sed } 565193323Sed 566193323Sed CGP->add(this); 567193323Sed} 568193323Sed 569193323Sed/// getAnalysisUsage - For this class, we declare that we require and preserve 570193323Sed/// the call graph. If the derived class implements this method, it should 571193323Sed/// always explicitly call the implementation here. 572193323Sedvoid CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const { 573193323Sed AU.addRequired<CallGraph>(); 574193323Sed AU.addPreserved<CallGraph>(); 575193323Sed} 576207618Srdivacky 577207618Srdivacky 578207618Srdivacky//===----------------------------------------------------------------------===// 579207618Srdivacky// PrintCallGraphPass Implementation 580207618Srdivacky//===----------------------------------------------------------------------===// 581207618Srdivacky 582207618Srdivackynamespace { 583207618Srdivacky /// PrintCallGraphPass - Print a Module corresponding to a call graph. 584207618Srdivacky /// 585207618Srdivacky class PrintCallGraphPass : public CallGraphSCCPass { 586207618Srdivacky std::string Banner; 587207618Srdivacky raw_ostream &Out; // raw_ostream to print on. 588207618Srdivacky 589207618Srdivacky public: 590207618Srdivacky static char ID; 591207618Srdivacky PrintCallGraphPass(const std::string &B, raw_ostream &o) 592212904Sdim : CallGraphSCCPass(ID), Banner(B), Out(o) {} 593207618Srdivacky 594207618Srdivacky virtual void getAnalysisUsage(AnalysisUsage &AU) const { 595207618Srdivacky AU.setPreservesAll(); 596207618Srdivacky } 597207618Srdivacky 598207618Srdivacky bool runOnSCC(CallGraphSCC &SCC) { 599207618Srdivacky Out << Banner; 600207618Srdivacky for (CallGraphSCC::iterator I = SCC.begin(), E = SCC.end(); I != E; ++I) 601207618Srdivacky (*I)->getFunction()->print(Out); 602207618Srdivacky return false; 603207618Srdivacky } 604207618Srdivacky }; 605207618Srdivacky 606207618Srdivacky} // end anonymous namespace. 607207618Srdivacky 608207618Srdivackychar PrintCallGraphPass::ID = 0; 609207618Srdivacky 610207618SrdivackyPass *CallGraphSCCPass::createPrinterPass(raw_ostream &O, 611207618Srdivacky const std::string &Banner) const { 612207618Srdivacky return new PrintCallGraphPass(Banner, O); 613207618Srdivacky} 614207618Srdivacky 615