LLVM API Documentation
00001 //===- llvm/PassManagers.h - Pass Infrastructure classes -------*- C++ -*-===// 00002 // 00003 // The LLVM Compiler Infrastructure 00004 // 00005 // This file is distributed under the University of Illinois Open Source 00006 // License. See LICENSE.TXT for details. 00007 // 00008 //===----------------------------------------------------------------------===// 00009 // 00010 // This file declares the LLVM Pass Manager infrastructure. 00011 // 00012 //===----------------------------------------------------------------------===// 00013 00014 #ifndef LLVM_PASSMANAGERS_H 00015 #define LLVM_PASSMANAGERS_H 00016 00017 #include "llvm/PassManager.h" 00018 #include "llvm/ADT/SmallVector.h" 00019 #include "llvm/ADT/SmallPtrSet.h" 00020 #include "llvm/ADT/DenseMap.h" 00021 #include <deque> 00022 #include <map> 00023 00024 //===----------------------------------------------------------------------===// 00025 // Overview: 00026 // The Pass Manager Infrastructure manages passes. It's responsibilities are: 00027 // 00028 // o Manage optimization pass execution order 00029 // o Make required Analysis information available before pass P is run 00030 // o Release memory occupied by dead passes 00031 // o If Analysis information is dirtied by a pass then regenerate Analysis 00032 // information before it is consumed by another pass. 00033 // 00034 // Pass Manager Infrastructure uses multiple pass managers. They are 00035 // PassManager, FunctionPassManager, MPPassManager, FPPassManager, BBPassManager. 00036 // This class hierarchy uses multiple inheritance but pass managers do not 00037 // derive from another pass manager. 00038 // 00039 // PassManager and FunctionPassManager are two top-level pass manager that 00040 // represents the external interface of this entire pass manager infrastucture. 00041 // 00042 // Important classes : 00043 // 00044 // [o] class PMTopLevelManager; 00045 // 00046 // Two top level managers, PassManager and FunctionPassManager, derive from 00047 // PMTopLevelManager. PMTopLevelManager manages information used by top level 00048 // managers such as last user info. 00049 // 00050 // [o] class PMDataManager; 00051 // 00052 // PMDataManager manages information, e.g. list of available analysis info, 00053 // used by a pass manager to manage execution order of passes. It also provides 00054 // a place to implement common pass manager APIs. All pass managers derive from 00055 // PMDataManager. 00056 // 00057 // [o] class BBPassManager : public FunctionPass, public PMDataManager; 00058 // 00059 // BBPassManager manages BasicBlockPasses. 00060 // 00061 // [o] class FunctionPassManager; 00062 // 00063 // This is a external interface used by JIT to manage FunctionPasses. This 00064 // interface relies on FunctionPassManagerImpl to do all the tasks. 00065 // 00066 // [o] class FunctionPassManagerImpl : public ModulePass, PMDataManager, 00067 // public PMTopLevelManager; 00068 // 00069 // FunctionPassManagerImpl is a top level manager. It manages FPPassManagers 00070 // 00071 // [o] class FPPassManager : public ModulePass, public PMDataManager; 00072 // 00073 // FPPassManager manages FunctionPasses and BBPassManagers 00074 // 00075 // [o] class MPPassManager : public Pass, public PMDataManager; 00076 // 00077 // MPPassManager manages ModulePasses and FPPassManagers 00078 // 00079 // [o] class PassManager; 00080 // 00081 // This is a external interface used by various tools to manages passes. It 00082 // relies on PassManagerImpl to do all the tasks. 00083 // 00084 // [o] class PassManagerImpl : public Pass, public PMDataManager, 00085 // public PMDTopLevelManager 00086 // 00087 // PassManagerImpl is a top level pass manager responsible for managing 00088 // MPPassManagers. 00089 //===----------------------------------------------------------------------===// 00090 00091 #include "llvm/Support/PrettyStackTrace.h" 00092 00093 namespace llvm { 00094 class Module; 00095 class Pass; 00096 class StringRef; 00097 class Value; 00098 00099 /// FunctionPassManager and PassManager, two top level managers, serve 00100 /// as the public interface of pass manager infrastructure. 00101 enum TopLevelManagerType { 00102 TLM_Function, // FunctionPassManager 00103 TLM_Pass // PassManager 00104 }; 00105 00106 // enums for debugging strings 00107 enum PassDebuggingString { 00108 EXECUTION_MSG, // "Executing Pass '" 00109 MODIFICATION_MSG, // "' Made Modification '" 00110 FREEING_MSG, // " Freeing Pass '" 00111 ON_BASICBLOCK_MSG, // "' on BasicBlock '" + PassName + "'...\n" 00112 ON_FUNCTION_MSG, // "' on Function '" + FunctionName + "'...\n" 00113 ON_MODULE_MSG, // "' on Module '" + ModuleName + "'...\n" 00114 ON_LOOP_MSG, // " 'on Loop ...\n'" 00115 ON_CG_MSG // "' on Call Graph ...\n'" 00116 }; 00117 00118 /// PassManagerPrettyStackEntry - This is used to print informative information 00119 /// about what pass is running when/if a stack trace is generated. 00120 class PassManagerPrettyStackEntry : public PrettyStackTraceEntry { 00121 Pass *P; 00122 Value *V; 00123 Module *M; 00124 public: 00125 explicit PassManagerPrettyStackEntry(Pass *p) 00126 : P(p), V(0), M(0) {} // When P is releaseMemory'd. 00127 PassManagerPrettyStackEntry(Pass *p, Value &v) 00128 : P(p), V(&v), M(0) {} // When P is run on V 00129 PassManagerPrettyStackEntry(Pass *p, Module &m) 00130 : P(p), V(0), M(&m) {} // When P is run on M 00131 00132 /// print - Emit information about this stack frame to OS. 00133 virtual void print(raw_ostream &OS) const; 00134 }; 00135 00136 00137 //===----------------------------------------------------------------------===// 00138 // PMStack 00139 // 00140 /// PMStack 00141 /// Top level pass managers (see PassManager.cpp) maintain active Pass Managers 00142 /// using PMStack. Each Pass implements assignPassManager() to connect itself 00143 /// with appropriate manager. assignPassManager() walks PMStack to find 00144 /// suitable manager. 00145 /// 00146 /// PMStack is just a wrapper around standard deque that overrides pop() and 00147 /// push() methods. 00148 class PMStack { 00149 public: 00150 typedef std::deque<PMDataManager *>::reverse_iterator iterator; 00151 iterator begin() { return S.rbegin(); } 00152 iterator end() { return S.rend(); } 00153 00154 void handleLastUserOverflow(); 00155 00156 void pop(); 00157 inline PMDataManager *top() { return S.back(); } 00158 void push(PMDataManager *PM); 00159 inline bool empty() { return S.empty(); } 00160 00161 void dump(); 00162 private: 00163 std::deque<PMDataManager *> S; 00164 }; 00165 00166 00167 //===----------------------------------------------------------------------===// 00168 // PMTopLevelManager 00169 // 00170 /// PMTopLevelManager manages LastUser info and collects common APIs used by 00171 /// top level pass managers. 00172 class PMTopLevelManager { 00173 public: 00174 00175 virtual unsigned getNumContainedManagers() const { 00176 return (unsigned)PassManagers.size(); 00177 } 00178 00179 /// Schedule pass P for execution. Make sure that passes required by 00180 /// P are run before P is run. Update analysis info maintained by 00181 /// the manager. Remove dead passes. This is a recursive function. 00182 void schedulePass(Pass *P); 00183 00184 /// This is implemented by top level pass manager and used by 00185 /// schedulePass() to add analysis info passes that are not available. 00186 virtual void addTopLevelPass(Pass *P) = 0; 00187 00188 /// Set pass P as the last user of the given analysis passes. 00189 void setLastUser(SmallVector<Pass *, 12> &AnalysisPasses, Pass *P); 00190 00191 /// Collect passes whose last user is P 00192 void collectLastUses(SmallVector<Pass *, 12> &LastUses, Pass *P); 00193 00194 /// Find the pass that implements Analysis AID. Search immutable 00195 /// passes and all pass managers. If desired pass is not found 00196 /// then return NULL. 00197 Pass *findAnalysisPass(AnalysisID AID); 00198 00199 /// Find analysis usage information for the pass P. 00200 AnalysisUsage *findAnalysisUsage(Pass *P); 00201 00202 explicit PMTopLevelManager(enum TopLevelManagerType t); 00203 virtual ~PMTopLevelManager(); 00204 00205 /// Add immutable pass and initialize it. 00206 inline void addImmutablePass(ImmutablePass *P) { 00207 P->initializePass(); 00208 ImmutablePasses.push_back(P); 00209 } 00210 00211 inline SmallVector<ImmutablePass *, 8>& getImmutablePasses() { 00212 return ImmutablePasses; 00213 } 00214 00215 void addPassManager(PMDataManager *Manager) { 00216 PassManagers.push_back(Manager); 00217 } 00218 00219 // Add Manager into the list of managers that are not directly 00220 // maintained by this top level pass manager 00221 inline void addIndirectPassManager(PMDataManager *Manager) { 00222 IndirectPassManagers.push_back(Manager); 00223 } 00224 00225 // Print passes managed by this top level manager. 00226 void dumpPasses() const; 00227 void dumpArguments() const; 00228 00229 void initializeAllAnalysisInfo(); 00230 00231 // Active Pass Managers 00232 PMStack activeStack; 00233 00234 protected: 00235 00236 /// Collection of pass managers 00237 SmallVector<PMDataManager *, 8> PassManagers; 00238 00239 private: 00240 00241 /// Collection of pass managers that are not directly maintained 00242 /// by this pass manager 00243 SmallVector<PMDataManager *, 8> IndirectPassManagers; 00244 00245 // Map to keep track of last user of the analysis pass. 00246 // LastUser->second is the last user of Lastuser->first. 00247 DenseMap<Pass *, Pass *> LastUser; 00248 00249 // Map to keep track of passes that are last used by a pass. 00250 // This inverse map is initialized at PM->run() based on 00251 // LastUser map. 00252 DenseMap<Pass *, SmallPtrSet<Pass *, 8> > InversedLastUser; 00253 00254 /// Immutable passes are managed by top level manager. 00255 SmallVector<ImmutablePass *, 8> ImmutablePasses; 00256 00257 DenseMap<Pass *, AnalysisUsage *> AnUsageMap; 00258 }; 00259 00260 00261 00262 //===----------------------------------------------------------------------===// 00263 // PMDataManager 00264 00265 /// PMDataManager provides the common place to manage the analysis data 00266 /// used by pass managers. 00267 class PMDataManager { 00268 public: 00269 00270 explicit PMDataManager(int Depth) : TPM(NULL), Depth(Depth) { 00271 initializeAnalysisInfo(); 00272 } 00273 00274 virtual ~PMDataManager(); 00275 00276 /// Augment AvailableAnalysis by adding analysis made available by pass P. 00277 void recordAvailableAnalysis(Pass *P); 00278 00279 /// verifyPreservedAnalysis -- Verify analysis presreved by pass P. 00280 void verifyPreservedAnalysis(Pass *P); 00281 00282 /// verifyDomInfo -- Verify dominator information if it is available. 00283 void verifyDomInfo(Pass &P, Function &F); 00284 00285 /// Remove Analysis that is not preserved by the pass 00286 void removeNotPreservedAnalysis(Pass *P); 00287 00288 /// Remove dead passes 00289 void removeDeadPasses(Pass *P, const StringRef &Msg, 00290 enum PassDebuggingString); 00291 00292 /// Add pass P into the PassVector. Update 00293 /// AvailableAnalysis appropriately if ProcessAnalysis is true. 00294 void add(Pass *P, bool ProcessAnalysis = true); 00295 00296 /// Add RequiredPass into list of lower level passes required by pass P. 00297 /// RequiredPass is run on the fly by Pass Manager when P requests it 00298 /// through getAnalysis interface. 00299 virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass); 00300 00301 virtual Pass * getOnTheFlyPass(Pass *P, const PassInfo *PI, Function &F) { 00302 assert (0 && "Unable to find on the fly pass"); 00303 return NULL; 00304 } 00305 00306 /// Initialize available analysis information. 00307 void initializeAnalysisInfo() { 00308 AvailableAnalysis.clear(); 00309 for (unsigned i = 0; i < PMT_Last; ++i) 00310 InheritedAnalysis[i] = NULL; 00311 } 00312 00313 // Return true if P preserves high level analysis used by other 00314 // passes that are managed by this manager. 00315 bool preserveHigherLevelAnalysis(Pass *P); 00316 00317 00318 /// Populate RequiredPasses with analysis pass that are required by 00319 /// pass P and are available. Populate ReqPassNotAvailable with analysis 00320 /// pass that are required by pass P but are not available. 00321 void collectRequiredAnalysis(SmallVector<Pass *, 8> &RequiredPasses, 00322 SmallVector<AnalysisID, 8> &ReqPassNotAvailable, 00323 Pass *P); 00324 00325 /// All Required analyses should be available to the pass as it runs! Here 00326 /// we fill in the AnalysisImpls member of the pass so that it can 00327 /// successfully use the getAnalysis() method to retrieve the 00328 /// implementations it needs. 00329 void initializeAnalysisImpl(Pass *P); 00330 00331 /// Find the pass that implements Analysis AID. If desired pass is not found 00332 /// then return NULL. 00333 Pass *findAnalysisPass(AnalysisID AID, bool Direction); 00334 00335 // Access toplevel manager 00336 PMTopLevelManager *getTopLevelManager() { return TPM; } 00337 void setTopLevelManager(PMTopLevelManager *T) { TPM = T; } 00338 00339 unsigned getDepth() const { return Depth; } 00340 00341 // Print routines used by debug-pass 00342 void dumpLastUses(Pass *P, unsigned Offset) const; 00343 void dumpPassArguments() const; 00344 void dumpPassInfo(Pass *P, enum PassDebuggingString S1, 00345 enum PassDebuggingString S2, const StringRef &Msg); 00346 void dumpRequiredSet(const Pass *P) const; 00347 void dumpPreservedSet(const Pass *P) const; 00348 00349 virtual unsigned getNumContainedPasses() const { 00350 return (unsigned)PassVector.size(); 00351 } 00352 00353 virtual PassManagerType getPassManagerType() const { 00354 assert ( 0 && "Invalid use of getPassManagerType"); 00355 return PMT_Unknown; 00356 } 00357 00358 std::map<AnalysisID, Pass*> *getAvailableAnalysis() { 00359 return &AvailableAnalysis; 00360 } 00361 00362 // Collect AvailableAnalysis from all the active Pass Managers. 00363 void populateInheritedAnalysis(PMStack &PMS) { 00364 unsigned Index = 0; 00365 for (PMStack::iterator I = PMS.begin(), E = PMS.end(); 00366 I != E; ++I) 00367 InheritedAnalysis[Index++] = (*I)->getAvailableAnalysis(); 00368 } 00369 00370 protected: 00371 00372 // Top level manager. 00373 PMTopLevelManager *TPM; 00374 00375 // Collection of pass that are managed by this manager 00376 SmallVector<Pass *, 16> PassVector; 00377 00378 // Collection of Analysis provided by Parent pass manager and 00379 // used by current pass manager. At at time there can not be more 00380 // then PMT_Last active pass mangers. 00381 std::map<AnalysisID, Pass *> *InheritedAnalysis[PMT_Last]; 00382 00383 private: 00384 void dumpAnalysisUsage(const StringRef &Msg, const Pass *P, 00385 const AnalysisUsage::VectorType &Set) const; 00386 00387 // Set of available Analysis. This information is used while scheduling 00388 // pass. If a pass requires an analysis which is not not available then 00389 // equired analysis pass is scheduled to run before the pass itself is 00390 // scheduled to run. 00391 std::map<AnalysisID, Pass*> AvailableAnalysis; 00392 00393 // Collection of higher level analysis used by the pass managed by 00394 // this manager. 00395 SmallVector<Pass *, 8> HigherLevelAnalysis; 00396 00397 unsigned Depth; 00398 }; 00399 00400 //===----------------------------------------------------------------------===// 00401 // FPPassManager 00402 // 00403 /// FPPassManager manages BBPassManagers and FunctionPasses. 00404 /// It batches all function passes and basic block pass managers together and 00405 /// sequence them to process one function at a time before processing next 00406 /// function. 00407 00408 class FPPassManager : public ModulePass, public PMDataManager { 00409 00410 public: 00411 static char ID; 00412 explicit FPPassManager(int Depth) 00413 : ModulePass(&ID), PMDataManager(Depth) { } 00414 00415 /// run - Execute all of the passes scheduled for execution. Keep track of 00416 /// whether any of the passes modifies the module, and if so, return true. 00417 bool runOnFunction(Function &F); 00418 bool runOnModule(Module &M); 00419 00420 /// cleanup - After running all passes, clean up pass manager cache. 00421 void cleanup(); 00422 00423 /// doInitialization - Run all of the initializers for the function passes. 00424 /// 00425 bool doInitialization(Module &M); 00426 00427 /// doFinalization - Run all of the finalizers for the function passes. 00428 /// 00429 bool doFinalization(Module &M); 00430 00431 /// Pass Manager itself does not invalidate any analysis info. 00432 void getAnalysisUsage(AnalysisUsage &Info) const { 00433 Info.setPreservesAll(); 00434 } 00435 00436 // Print passes managed by this manager 00437 void dumpPassStructure(unsigned Offset); 00438 00439 virtual const char *getPassName() const { 00440 return "Function Pass Manager"; 00441 } 00442 00443 FunctionPass *getContainedPass(unsigned N) { 00444 assert ( N < PassVector.size() && "Pass number out of range!"); 00445 FunctionPass *FP = static_cast<FunctionPass *>(PassVector[N]); 00446 return FP; 00447 } 00448 00449 virtual PassManagerType getPassManagerType() const { 00450 return PMT_FunctionPassManager; 00451 } 00452 }; 00453 00454 extern void StartPassTimer(llvm::Pass *); 00455 extern void StopPassTimer(llvm::Pass *); 00456 00457 } 00458 00459 #endif