CallGraphSCCPass.cpp revision af068750a71780a2f1780f056af0c21208a408dd
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#include "llvm/CallGraphSCCPass.h" 19#include "llvm/Analysis/CallGraph.h" 20#include "llvm/ADT/SCCIterator.h" 21#include "llvm/PassManagers.h" 22#include "llvm/Function.h" 23using namespace llvm; 24 25//===----------------------------------------------------------------------===// 26// CGPassManager 27// 28/// CGPassManager manages FPPassManagers and CalLGraphSCCPasses. 29 30namespace { 31 32class CGPassManager : public ModulePass, public PMDataManager { 33 34public: 35 static char ID; 36 explicit CGPassManager(int Depth) 37 : ModulePass(&ID), PMDataManager(Depth) { } 38 39 /// run - Execute all of the passes scheduled for execution. Keep track of 40 /// whether any of the passes modifies the module, and if so, return true. 41 bool runOnModule(Module &M); 42 43 bool doInitialization(CallGraph &CG, Module &M); 44 bool doFinalization(CallGraph &CG, Module &M); 45 46 /// Pass Manager itself does not invalidate any analysis info. 47 void getAnalysisUsage(AnalysisUsage &Info) const { 48 // CGPassManager walks SCC and it needs CallGraph. 49 Info.addRequired<CallGraph>(); 50 Info.setPreservesAll(); 51 } 52 53 virtual const char *getPassName() const { 54 return "CallGraph Pass Manager"; 55 } 56 57 // Print passes managed by this manager 58 void dumpPassStructure(unsigned Offset) { 59 llvm::cerr << std::string(Offset*2, ' ') << "Call Graph SCC Pass Manager\n"; 60 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 61 Pass *P = getContainedPass(Index); 62 P->dumpPassStructure(Offset + 1); 63 dumpLastUses(P, Offset+1); 64 } 65 } 66 67 Pass *getContainedPass(unsigned N) { 68 assert ( N < PassVector.size() && "Pass number out of range!"); 69 Pass *FP = static_cast<Pass *>(PassVector[N]); 70 return FP; 71 } 72 73 virtual PassManagerType getPassManagerType() const { 74 return PMT_CallGraphPassManager; 75 } 76}; 77 78} 79 80char CGPassManager::ID = 0; 81/// run - Execute all of the passes scheduled for execution. Keep track of 82/// whether any of the passes modifies the module, and if so, return true. 83bool CGPassManager::runOnModule(Module &M) { 84 CallGraph &CG = getAnalysis<CallGraph>(); 85 bool Changed = doInitialization(CG, M); 86 87 // Walk SCC 88 for (scc_iterator<CallGraph*> I = scc_begin(&CG), E = scc_end(&CG); 89 I != E; ++I) { 90 91 // Run all passes on current SCC 92 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 93 Pass *P = getContainedPass(Index); 94 95 dumpPassInfo(P, EXECUTION_MSG, ON_CG_MSG, ""); 96 dumpRequiredSet(P); 97 98 initializeAnalysisImpl(P); 99 100 StartPassTimer(P); 101 if (CallGraphSCCPass *CGSP = dynamic_cast<CallGraphSCCPass *>(P)) 102 Changed |= CGSP->runOnSCC(*I); // TODO : What if CG is changed ? 103 else { 104 FPPassManager *FPP = dynamic_cast<FPPassManager *>(P); 105 assert (FPP && "Invalid CGPassManager member"); 106 107 // Run pass P on all functions current SCC 108 std::vector<CallGraphNode*> &SCC = *I; 109 for (unsigned i = 0, e = SCC.size(); i != e; ++i) { 110 Function *F = SCC[i]->getFunction(); 111 if (F) { 112 dumpPassInfo(P, EXECUTION_MSG, ON_FUNCTION_MSG, F->getNameStart()); 113 Changed |= FPP->runOnFunction(*F); 114 } 115 } 116 } 117 StopPassTimer(P); 118 119 if (Changed) 120 dumpPassInfo(P, MODIFICATION_MSG, ON_CG_MSG, ""); 121 dumpPreservedSet(P); 122 123 verifyPreservedAnalysis(P); 124 removeNotPreservedAnalysis(P); 125 recordAvailableAnalysis(P); 126 removeDeadPasses(P, "", ON_CG_MSG); 127 } 128 } 129 Changed |= doFinalization(CG, M); 130 return Changed; 131} 132 133/// Initialize CG 134bool CGPassManager::doInitialization(CallGraph &CG, Module &M) { 135 bool Changed = false; 136 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 137 Pass *P = getContainedPass(Index); 138 if (CallGraphSCCPass *CGSP = dynamic_cast<CallGraphSCCPass *>(P)) { 139 Changed |= CGSP->doInitialization(CG); 140 } else { 141 FPPassManager *FP = dynamic_cast<FPPassManager *>(P); 142 assert (FP && "Invalid CGPassManager member"); 143 Changed |= FP->doInitialization(M); 144 } 145 } 146 return Changed; 147} 148 149/// Finalize CG 150bool CGPassManager::doFinalization(CallGraph &CG, Module &M) { 151 bool Changed = false; 152 for (unsigned Index = 0; Index < getNumContainedPasses(); ++Index) { 153 Pass *P = getContainedPass(Index); 154 if (CallGraphSCCPass *CGSP = dynamic_cast<CallGraphSCCPass *>(P)) { 155 Changed |= CGSP->doFinalization(CG); 156 } else { 157 FPPassManager *FP = dynamic_cast<FPPassManager *>(P); 158 assert (FP && "Invalid CGPassManager member"); 159 Changed |= FP->doFinalization(M); 160 } 161 } 162 return Changed; 163} 164 165/// Assign pass manager to manage this pass. 166void CallGraphSCCPass::assignPassManager(PMStack &PMS, 167 PassManagerType PreferredType) { 168 // Find CGPassManager 169 while (!PMS.empty() && 170 PMS.top()->getPassManagerType() > PMT_CallGraphPassManager) 171 PMS.pop(); 172 173 assert (!PMS.empty() && "Unable to handle Call Graph Pass"); 174 CGPassManager *CGP = dynamic_cast<CGPassManager *>(PMS.top()); 175 176 // Create new Call Graph SCC Pass Manager if it does not exist. 177 if (!CGP) { 178 179 assert (!PMS.empty() && "Unable to create Call Graph Pass Manager"); 180 PMDataManager *PMD = PMS.top(); 181 182 // [1] Create new Call Graph Pass Manager 183 CGP = new CGPassManager(PMD->getDepth() + 1); 184 185 // [2] Set up new manager's top level manager 186 PMTopLevelManager *TPM = PMD->getTopLevelManager(); 187 TPM->addIndirectPassManager(CGP); 188 189 // [3] Assign manager to manage this new manager. This may create 190 // and push new managers into PMS 191 Pass *P = dynamic_cast<Pass *>(CGP); 192 TPM->schedulePass(P); 193 194 // [4] Push new manager into PMS 195 PMS.push(CGP); 196 } 197 198 CGP->add(this); 199} 200 201/// getAnalysisUsage - For this class, we declare that we require and preserve 202/// the call graph. If the derived class implements this method, it should 203/// always explicitly call the implementation here. 204void CallGraphSCCPass::getAnalysisUsage(AnalysisUsage &AU) const { 205 AU.addRequired<CallGraph>(); 206 AU.addPreserved<CallGraph>(); 207} 208