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