CallGraphSCCPass.cpp revision cf5862d8ac9562e633e6ef7cb55e67c2b7ca9c0a
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/Support/Debug.h" 26#include "llvm/Support/Timer.h" 27#include "llvm/Support/raw_ostream.h" 28using namespace llvm; 29 30//===----------------------------------------------------------------------===// 31// CGPassManager 32// 33/// CGPassManager manages FPPassManagers and CallGraphSCCPasses. 34 35namespace { 36 37class CGPassManager : public ModulePass, public PMDataManager { 38public: 39 static char ID; 40 explicit CGPassManager(int Depth) 41 : ModulePass(&ID), PMDataManager(Depth) { } 42 43 /// run - Execute all of the passes scheduled for execution. Keep track of 44 /// whether any of the passes modifies the module, and if so, return true. 45 bool runOnModule(Module &M); 46 47 bool doInitialization(CallGraph &CG); 48 bool doFinalization(CallGraph &CG); 49 50 /// Pass Manager itself does not invalidate any analysis info. 51 void getAnalysisUsage(AnalysisUsage &Info) const { 52 // CGPassManager walks SCC and it needs CallGraph. 53 Info.addRequired<CallGraph>(); 54 Info.setPreservesAll(); 55 } 56 57 virtual const char *getPassName() const { 58 return "CallGraph Pass Manager"; 59 } 60 61 virtual PMDataManager *getAsPMDataManager() { return this; } 62 virtual Pass *getAsPass() { return this; } 63 64 // Print passes managed by this manager 65 void dumpPassStructure(unsigned Offset) { 66 errs().indent(Offset*2) << "Call Graph SCC Pass Manager\n"; 67 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 68 Pass *P = getContainedPass(Index); 69 P->dumpPassStructure(Offset + 1); 70 dumpLastUses(P, Offset+1); 71 } 72 } 73 74 Pass *getContainedPass(unsigned N) { 75 assert(N < PassVector.size() && "Pass number out of range!"); 76 return static_cast<Pass *>(PassVector[N]); 77 } 78 79 virtual PassManagerType getPassManagerType() const { 80 return PMT_CallGraphPassManager; 81 } 82 83private: 84 bool RunPassOnSCC(Pass *P, std::vector<CallGraphNode*> &CurSCC, 85 CallGraph &CG, bool &CallGraphUpToDate); 86 void RefreshCallGraph(std::vector<CallGraphNode*> &CurSCC, CallGraph &CG, 87 bool IsCheckingMode); 88}; 89 90} // end anonymous namespace. 91 92char CGPassManager::ID = 0; 93 94bool CGPassManager::RunPassOnSCC(Pass *P, std::vector<CallGraphNode*> &CurSCC, 95 CallGraph &CG, bool &CallGraphUpToDate) { 96 bool Changed = false; 97 PMDataManager *PM = P->getAsPMDataManager(); 98 99 if (PM == 0) { 100 CallGraphSCCPass *CGSP = (CallGraphSCCPass*)P; 101 if (!CallGraphUpToDate) { 102 RefreshCallGraph(CurSCC, CG, false); 103 CallGraphUpToDate = true; 104 } 105 106 { 107 TimeRegion PassTimer(getPassTimer(CGSP)); 108 Changed = CGSP->runOnSCC(CurSCC); 109 } 110 111 // After the CGSCCPass is done, when assertions are enabled, use 112 // RefreshCallGraph to verify that the callgraph was correctly updated. 113#ifndef NDEBUG 114 if (Changed) 115 RefreshCallGraph(CurSCC, CG, true); 116#endif 117 118 return Changed; 119 } 120 121 122 assert(PM->getPassManagerType() == PMT_FunctionPassManager && 123 "Invalid CGPassManager member"); 124 FPPassManager *FPP = (FPPassManager*)P; 125 126 // Run pass P on all functions in the current SCC. 127 for (unsigned i = 0, e = CurSCC.size(); i != e; ++i) { 128 if (Function *F = CurSCC[i]->getFunction()) { 129 dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getName()); 130 TimeRegion PassTimer(getPassTimer(FPP)); 131 Changed |= FPP->runOnFunction(*F); 132 } 133 } 134 135 // The function pass(es) modified the IR, they may have clobbered the 136 // callgraph. 137 if (Changed && CallGraphUpToDate) { 138 DEBUG(dbgs() << "CGSCCPASSMGR: Pass Dirtied SCC: " 139 << P->getPassName() << '\n'); 140 CallGraphUpToDate = false; 141 } 142 return Changed; 143} 144 145 146/// RefreshCallGraph - Scan the functions in the specified CFG and resync the 147/// callgraph with the call sites found in it. This is used after 148/// FunctionPasses have potentially munged the callgraph, and can be used after 149/// CallGraphSCC passes to verify that they correctly updated the callgraph. 150/// 151void CGPassManager::RefreshCallGraph(std::vector<CallGraphNode*> &CurSCC, 152 CallGraph &CG, bool CheckingMode) { 153 DenseMap<Value*, CallGraphNode*> CallSites; 154 155 DEBUG(dbgs() << "CGSCCPASSMGR: Refreshing SCC with " << CurSCC.size() 156 << " nodes:\n"; 157 for (unsigned i = 0, e = CurSCC.size(); i != e; ++i) 158 CurSCC[i]->dump(); 159 ); 160 161 bool MadeChange = false; 162 163 // Scan all functions in the SCC. 164 for (unsigned sccidx = 0, e = CurSCC.size(); sccidx != e; ++sccidx) { 165 CallGraphNode *CGN = CurSCC[sccidx]; 166 Function *F = CGN->getFunction(); 167 if (F == 0 || F->isDeclaration()) continue; 168 169 // Walk the function body looking for call sites. Sync up the call sites in 170 // CGN with those actually in the function. 171 172 // Get the set of call sites currently in the function. 173 for (CallGraphNode::iterator I = CGN->begin(), E = CGN->end(); I != E; ) { 174 // If this call site is null, then the function pass deleted the call 175 // entirely and the WeakVH nulled it out. 176 if (I->first == 0 || 177 // If we've already seen this call site, then the FunctionPass RAUW'd 178 // one call with another, which resulted in two "uses" in the edge 179 // list of the same call. 180 CallSites.count(I->first) || 181 182 // If the call edge is not from a call or invoke, then the function 183 // pass RAUW'd a call with another value. This can happen when 184 // constant folding happens of well known functions etc. 185 CallSite::get(I->first).getInstruction() == 0) { 186 assert(!CheckingMode && 187 "CallGraphSCCPass did not update the CallGraph correctly!"); 188 189 // Just remove the edge from the set of callees, keep track of whether 190 // I points to the last element of the vector. 191 bool WasLast = I + 1 == E; 192 CGN->removeCallEdge(I); 193 194 // If I pointed to the last element of the vector, we have to bail out: 195 // iterator checking rejects comparisons of the resultant pointer with 196 // end. 197 if (WasLast) 198 break; 199 E = CGN->end(); 200 continue; 201 } 202 203 assert(!CallSites.count(I->first) && 204 "Call site occurs in node multiple times"); 205 CallSites.insert(std::make_pair(I->first, I->second)); 206 ++I; 207 } 208 209 // Loop over all of the instructions in the function, getting the callsites. 210 for (Function::iterator BB = F->begin(), E = F->end(); BB != E; ++BB) 211 for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 212 CallSite CS = CallSite::get(I); 213 if (!CS.getInstruction() || isa<DbgInfoIntrinsic>(I)) continue; 214 215 // If this call site already existed in the callgraph, just verify it 216 // matches up to expectations and remove it from CallSites. 217 DenseMap<Value*, CallGraphNode*>::iterator ExistingIt = 218 CallSites.find(CS.getInstruction()); 219 if (ExistingIt != CallSites.end()) { 220 CallGraphNode *ExistingNode = ExistingIt->second; 221 222 // Remove from CallSites since we have now seen it. 223 CallSites.erase(ExistingIt); 224 225 // Verify that the callee is right. 226 if (ExistingNode->getFunction() == CS.getCalledFunction()) 227 continue; 228 229 // If we are in checking mode, we are not allowed to actually mutate 230 // the callgraph. If this is a case where we can infer that the 231 // callgraph is less precise than it could be (e.g. an indirect call 232 // site could be turned direct), don't reject it in checking mode, and 233 // don't tweak it to be more precise. 234 if (CheckingMode && CS.getCalledFunction() && 235 ExistingNode->getFunction() == 0) 236 continue; 237 238 assert(!CheckingMode && 239 "CallGraphSCCPass did not update the CallGraph correctly!"); 240 241 // If not, we either went from a direct call to indirect, indirect to 242 // direct, or direct to different direct. 243 CallGraphNode *CalleeNode; 244 if (Function *Callee = CS.getCalledFunction()) 245 CalleeNode = CG.getOrInsertFunction(Callee); 246 else 247 CalleeNode = CG.getCallsExternalNode(); 248 249 // Update the edge target in CGN. 250 for (CallGraphNode::iterator I = CGN->begin(); ; ++I) { 251 assert(I != CGN->end() && "Didn't find call entry"); 252 if (I->first == CS.getInstruction()) { 253 I->second = CalleeNode; 254 break; 255 } 256 } 257 MadeChange = true; 258 continue; 259 } 260 261 assert(!CheckingMode && 262 "CallGraphSCCPass did not update the CallGraph correctly!"); 263 264 // If the call site didn't exist in the CGN yet, add it. We assume that 265 // newly introduced call sites won't be indirect. This could be fixed 266 // in the future. 267 CallGraphNode *CalleeNode; 268 if (Function *Callee = CS.getCalledFunction()) 269 CalleeNode = CG.getOrInsertFunction(Callee); 270 else 271 CalleeNode = CG.getCallsExternalNode(); 272 273 CGN->addCalledFunction(CS, CalleeNode); 274 MadeChange = true; 275 } 276 277 // After scanning this function, if we still have entries in callsites, then 278 // they are dangling pointers. WeakVH should save us for this, so abort if 279 // this happens. 280 assert(CallSites.empty() && "Dangling pointers found in call sites map"); 281 282 // Periodically do an explicit clear to remove tombstones when processing 283 // large scc's. 284 if ((sccidx & 15) == 0) 285 CallSites.clear(); 286 } 287 288 DEBUG(if (MadeChange) { 289 dbgs() << "CGSCCPASSMGR: Refreshed SCC is now:\n"; 290 for (unsigned i = 0, e = CurSCC.size(); i != e; ++i) 291 CurSCC[i]->dump(); 292 } else { 293 dbgs() << "CGSCCPASSMGR: SCC Refresh didn't change call graph.\n"; 294 } 295 ); 296} 297 298/// run - Execute all of the passes scheduled for execution. Keep track of 299/// whether any of the passes modifies the module, and if so, return true. 300bool CGPassManager::runOnModule(Module &M) { 301 CallGraph &CG = getAnalysis<CallGraph>(); 302 bool Changed = doInitialization(CG); 303 304 std::vector<CallGraphNode*> CurSCC; 305 306 // Walk the callgraph in bottom-up SCC order. 307 for (scc_iterator<CallGraph*> CGI = scc_begin(&CG), E = scc_end(&CG); 308 CGI != E;) { 309 // Copy the current SCC and increment past it so that the pass can hack 310 // on the SCC if it wants to without invalidating our iterator. 311 CurSCC = *CGI; 312 ++CGI; 313 314 315 // CallGraphUpToDate - Keep track of whether the callgraph is known to be 316 // up-to-date or not. The CGSSC pass manager runs two types of passes: 317 // CallGraphSCC Passes and other random function passes. Because other 318 // random function passes are not CallGraph aware, they may clobber the 319 // call graph by introducing new calls or deleting other ones. This flag 320 // is set to false when we run a function pass so that we know to clean up 321 // the callgraph when we need to run a CGSCCPass again. 322 bool CallGraphUpToDate = true; 323 324 // Run all passes on current SCC. 325 for (unsigned PassNo = 0, e = getNumContainedPasses(); 326 PassNo != e; ++PassNo) { 327 Pass *P = getContainedPass(PassNo); 328 329 // If we're in -debug-pass=Executions mode, construct the SCC node list, 330 // otherwise avoid constructing this string as it is expensive. 331 if (isPassDebuggingExecutionsOrMore()) { 332 std::string Functions; 333#ifndef NDEBUG 334 raw_string_ostream OS(Functions); 335 for (unsigned i = 0, e = CurSCC.size(); i != e; ++i) { 336 if (i) OS << ", "; 337 CurSCC[i]->print(OS); 338 } 339 OS.flush(); 340#endif 341 dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, Functions); 342 } 343 dumpRequiredSet(P); 344 345 initializeAnalysisImpl(P); 346 347 // Actually run this pass on the current SCC. 348 Changed |= RunPassOnSCC(P, CurSCC, CG, CallGraphUpToDate); 349 350 if (Changed) 351 dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, ""); 352 dumpPreservedSet(P); 353 354 verifyPreservedAnalysis(P); 355 removeNotPreservedAnalysis(P); 356 recordAvailableAnalysis(P); 357 removeDeadPasses(P, "", ON_CG_MSG); 358 } 359 360 // If the callgraph was left out of date (because the last pass run was a 361 // functionpass), refresh it before we move on to the next SCC. 362 if (!CallGraphUpToDate) 363 RefreshCallGraph(CurSCC, CG, false); 364 } 365 Changed |= doFinalization(CG); 366 return Changed; 367} 368 369/// Initialize CG 370bool CGPassManager::doInitialization(CallGraph &CG) { 371 bool Changed = false; 372 for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) { 373 if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) { 374 assert(PM->getPassManagerType() == PMT_FunctionPassManager && 375 "Invalid CGPassManager member"); 376 Changed |= ((FPPassManager*)PM)->doInitialization(CG.getModule()); 377 } else { 378 Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doInitialization(CG); 379 } 380 } 381 return Changed; 382} 383 384/// Finalize CG 385bool CGPassManager::doFinalization(CallGraph &CG) { 386 bool Changed = false; 387 for (unsigned i = 0, e = getNumContainedPasses(); i != e; ++i) { 388 if (PMDataManager *PM = getContainedPass(i)->getAsPMDataManager()) { 389 assert(PM->getPassManagerType() == PMT_FunctionPassManager && 390 "Invalid CGPassManager member"); 391 Changed |= ((FPPassManager*)PM)->doFinalization(CG.getModule()); 392 } else { 393 Changed |= ((CallGraphSCCPass*)getContainedPass(i))->doFinalization(CG); 394 } 395 } 396 return Changed; 397} 398 399/// Assign pass manager to manage this pass. 400void CallGraphSCCPass::assignPassManager(PMStack &PMS, 401 PassManagerType PreferredType) { 402 // Find CGPassManager 403 while (!PMS.empty() && 404 PMS.top()->getPassManagerType() > PMT_CallGraphPassManager) 405 PMS.pop(); 406 407 assert(!PMS.empty() && "Unable to handle Call Graph Pass"); 408 CGPassManager *CGP; 409 410 if (PMS.top()->getPassManagerType() == PMT_CallGraphPassManager) 411 CGP = (CGPassManager*)PMS.top(); 412 else { 413 // Create new Call Graph SCC Pass Manager if it does not exist. 414 assert(!PMS.empty() && "Unable to create Call Graph Pass Manager"); 415 PMDataManager *PMD = PMS.top(); 416 417 // [1] Create new Call Graph Pass Manager 418 CGP = new CGPassManager(PMD->getDepth() + 1); 419 420 // [2] Set up new manager's top level manager 421 PMTopLevelManager *TPM = PMD->getTopLevelManager(); 422 TPM->addIndirectPassManager(CGP); 423 424 // [3] Assign manager to manage this new manager. This may create 425 // and push new managers into PMS 426 Pass *P = CGP; 427 TPM->schedulePass(P); 428 429 // [4] Push new manager into PMS 430 PMS.push(CGP); 431 } 432 433 CGP->add(this); 434} 435 436/// getAnalysisUsage - For this class, we declare that we require and preserve 437/// the call graph. If the derived class implements this method, it should 438/// always explicitly call the implementation here. 439void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const { 440 AU.addRequired<CallGraph>(); 441 AU.addPreserved<CallGraph>(); 442} 443