include/llvm/PassManagers.h

   1 //===- llvm/PassManager.h - Pass Inftrastructre classes  --------*- C++ -*-===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file was developed by Devang Patel and is distributed under
   6 // the University of Illinois Open Source License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9 //
  10 // This file declares the LLVM Pass Manager infrastructure.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #include "llvm/PassManager.h"
  15 #include "llvm/ADT/SmallVector.h"
  16 using namespace llvm;
  17 class llvm::PMDataManager;
  18 class llvm::PMStack;
  19
  20 //===----------------------------------------------------------------------===//
  21 // Overview:
  22 // The Pass Manager Infrastructure manages passes. It's responsibilities are:
  23 //
  24 //   o Manage optimization pass execution order
  25 //   o Make required Analysis information available before pass P is run
  26 //   o Release memory occupied by dead passes
  27 //   o If Analysis information is dirtied by a pass then regenerate Analysis
  28 //     information before it is consumed by another pass.
  29 //
  30 // Pass Manager Infrastructure uses multiple pass managers.  They are
  31 // PassManager, FunctionPassManager, MPPassManager, FPPassManager, BBPassManager.
  32 // This class hierarcy uses multiple inheritance but pass managers do not derive
  33 // from another pass manager.
  34 //
  35 // PassManager and FunctionPassManager are two top-level pass manager that
  36 // represents the external interface of this entire pass manager infrastucture.
  37 //
  38 // Important classes :
  39 //
  40 // [o] class PMTopLevelManager;
  41 //
  42 // Two top level managers, PassManager and FunctionPassManager, derive from
  43 // PMTopLevelManager. PMTopLevelManager manages information used by top level
  44 // managers such as last user info.
  45 //
  46 // [o] class PMDataManager;
  47 //
  48 // PMDataManager manages information, e.g. list of available analysis info,
  49 // used by a pass manager to manage execution order of passes. It also provides
  50 // a place to implement common pass manager APIs. All pass managers derive from
  51 // PMDataManager.
  52 //
  53 // [o] class BBPassManager : public FunctionPass, public PMDataManager;
  54 //
  55 // BBPassManager manages BasicBlockPasses.
  56 //
  57 // [o] class FunctionPassManager;
  58 //
  59 // This is a external interface used by JIT to manage FunctionPasses. This
  60 // interface relies on FunctionPassManagerImpl to do all the tasks.
  61 //
  62 // [o] class FunctionPassManagerImpl : public ModulePass, PMDataManager,
  63 //                                     public PMTopLevelManager;
  64 //
  65 // FunctionPassManagerImpl is a top level manager. It manages FPPassManagers
  66 //
  67 // [o] class FPPassManager : public ModulePass, public PMDataManager;
  68 //
  69 // FPPassManager manages FunctionPasses and BBPassManagers
  70 //
  71 // [o] class MPPassManager : public Pass, public PMDataManager;
  72 //
  73 // MPPassManager manages ModulePasses and FPPassManagers
  74 //
  75 // [o] class PassManager;
  76 //
  77 // This is a external interface used by various tools to manages passes. It
  78 // relies on PassManagerImpl to do all the tasks.
  79 //
  80 // [o] class PassManagerImpl : public Pass, public PMDataManager,
  81 //                             public PMDTopLevelManager
  82 //
  83 // PassManagerImpl is a top level pass manager responsible for managing
  84 // MPPassManagers.
  85 //===----------------------------------------------------------------------===//
  86
  87 namespace llvm {
  88
  89 /// FunctionPassManager and PassManager, two top level managers, serve
  90 /// as the public interface of pass manager infrastructure.
  91 enum TopLevelManagerType {
  92   TLM_Function,  // FunctionPassManager
  93   TLM_Pass       // PassManager
  94 };
  95
  96 // enums for debugging strings
  97 enum PassDebuggingString {
  98   EXECUTION_MSG, // "Executing Pass '"
  99   MODIFICATION_MSG, // "' Made Modification '"
 100   FREEING_MSG, // " Freeing Pass '"
 101   ON_BASICBLOCK_MSG, // "'  on BasicBlock '" + PassName + "'...\n"
 102   ON_FUNCTION_MSG, // "' on Function '" + FunctionName + "'...\n"
 103   ON_MODULE_MSG, // "' on Module '" + ModuleName + "'...\n"
 104   ON_LOOP_MSG, // " 'on Loop ...\n'"
 105   ON_CG_MSG // "' on Call Graph ...\n'"
 106 };
 107
 108 //===----------------------------------------------------------------------===//
 109 // PMTopLevelManager
 110 //
 111 /// PMTopLevelManager manages LastUser info and collects common APIs used by
 112 /// top level pass managers.
 113 class PMTopLevelManager {
 114 public:
 115
 116   virtual unsigned getNumContainedManagers() {
 117     return PassManagers.size();
 118   }
 119
 120   /// Schedule pass P for execution. Make sure that passes required by
 121   /// P are run before P is run. Update analysis info maintained by
 122   /// the manager. Remove dead passes. This is a recursive function.
 123   void schedulePass(Pass *P);
 124
 125   /// This is implemented by top level pass manager and used by
 126   /// schedulePass() to add analysis info passes that are not available.
 127   virtual void addTopLevelPass(Pass  *P) = 0;
 128
 129   /// Set pass P as the last user of the given analysis passes.
 130   void setLastUser(std::vector<Pass *> &AnalysisPasses, Pass *P);
 131
 132   /// Collect passes whose last user is P
 133   void collectLastUses(std::vector<Pass *> &LastUses, Pass *P);
 134
 135   /// Find the pass that implements Analysis AID. Search immutable
 136   /// passes and all pass managers. If desired pass is not found
 137   /// then return NULL.
 138   Pass *findAnalysisPass(AnalysisID AID);
 139
 140   explicit PMTopLevelManager(enum TopLevelManagerType t);
 141   virtual ~PMTopLevelManager();
 142
 143   /// Add immutable pass and initialize it.
 144   inline void addImmutablePass(ImmutablePass *P) {
 145     P->initializePass();
 146     ImmutablePasses.push_back(P);
 147   }
 148
 149   inline std::vector<ImmutablePass *>& getImmutablePasses() {
 150     return ImmutablePasses;
 151   }
 152
 153   void addPassManager(Pass *Manager) {
 154     PassManagers.push_back(Manager);
 155   }
 156
 157   // Add Manager into the list of managers that are not directly
 158   // maintained by this top level pass manager
 159   inline void addIndirectPassManager(PMDataManager *Manager) {
 160     IndirectPassManagers.push_back(Manager);
 161   }
 162
 163   // Print passes managed by this top level manager.
 164   void dumpPasses() const;
 165   void dumpArguments() const;
 166
 167   void initializeAllAnalysisInfo();
 168
 169   // Active Pass Managers
 170   PMStack activeStack;
 171
 172 protected:
 173
 174   /// Collection of pass managers
 175   std::vector<Pass *> PassManagers;
 176
 177 private:
 178
 179   /// Collection of pass managers that are not directly maintained
 180   /// by this pass manager
 181   std::vector<PMDataManager *> IndirectPassManagers;
 182
 183   // Map to keep track of last user of the analysis pass.
 184   // LastUser->second is the last user of Lastuser->first.
 185   std::map<Pass *, Pass *> LastUser;
 186
 187   /// Immutable passes are managed by top level manager.
 188   std::vector<ImmutablePass *> ImmutablePasses;
 189 };
 190
 191
 192
 193 //===----------------------------------------------------------------------===//
 194 // PMDataManager
 195
 196 /// PMDataManager provides the common place to manage the analysis data
 197 /// used by pass managers.
 198 class PMDataManager {
 199 public:
 200
 201   explicit PMDataManager(int Depth) : TPM(NULL), Depth(Depth) {
 202     initializeAnalysisInfo();
 203   }
 204
 205   virtual ~PMDataManager();
 206
 207   /// Return true IFF pass P's required analysis set does not required new
 208   /// manager.
 209   bool manageablePass(Pass *P);
 210
 211   /// Augment AvailableAnalysis by adding analysis made available by pass P.
 212   void recordAvailableAnalysis(Pass *P);
 213
 214   /// verifyPreservedAnalysis -- Verify analysis presreved by pass P.
 215   void verifyPreservedAnalysis(Pass *P);
 216
 217   /// Remove Analysis that is not preserved by the pass
 218   void removeNotPreservedAnalysis(Pass *P);
 219
 220   /// Remove dead passes
 221   void removeDeadPasses(Pass *P, std::string Msg, enum PassDebuggingString);
 222
 223   /// Add pass P into the PassVector. Update
 224   /// AvailableAnalysis appropriately if ProcessAnalysis is true.
 225   void add(Pass *P, bool ProcessAnalysis = true);
 226
 227   /// Add RequiredPass into list of lower level passes required by pass P.
 228   /// RequiredPass is run on the fly by Pass Manager when P requests it
 229   /// through getAnalysis interface.
 230   virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass) {
 231     assert (0 &&
 232             "Unable to handle Pass that requires lower level Analysis pass");
 233   }
 234
 235   virtual Pass * getOnTheFlyPass(Pass *P, const PassInfo *PI, Function &F) {
 236     assert (0 && "Unable to find on the fly pass");
 237     return NULL;
 238   }
 239
 240   /// Initialize available analysis information.
 241   void initializeAnalysisInfo() {
 242     AvailableAnalysis.clear();
 243     for (unsigned i = 0; i < PMT_Last; ++i)
 244       InheritedAnalysis[i] = NULL;
 245   }
 246
 247   // Return true if P preserves high level analysis used by other
 248   // passes that are managed by this manager.
 249   bool preserveHigherLevelAnalysis(Pass *P);
 250
 251
 252   /// Populate RequiredPasses with analysis pass that are required by
 253   /// pass P and are available. Populate ReqPassNotAvailable with analysis
 254   /// pass that are required by pass P but are not available.
 255   void collectRequiredAnalysis(SmallVector<Pass *, 8> &RequiredPasses,
 256                                SmallVector<AnalysisID, 8> &ReqPassNotAvailable,
 257                                Pass *P);
 258
 259   /// All Required analyses should be available to the pass as it runs!  Here
 260   /// we fill in the AnalysisImpls member of the pass so that it can
 261   /// successfully use the getAnalysis() method to retrieve the
 262   /// implementations it needs.
 263   void initializeAnalysisImpl(Pass *P);
 264
 265   /// Find the pass that implements Analysis AID. If desired pass is not found
 266   /// then return NULL.
 267   Pass *findAnalysisPass(AnalysisID AID, bool Direction);
 268
 269   // Access toplevel manager
 270   PMTopLevelManager *getTopLevelManager() { return TPM; }
 271   void setTopLevelManager(PMTopLevelManager *T) { TPM = T; }
 272
 273   unsigned getDepth() const { return Depth; }
 274
 275   // Print routines used by debug-pass
 276   void dumpLastUses(Pass *P, unsigned Offset) const;
 277   void dumpPassArguments() const;
 278   void dumpPassInfo(Pass *P, enum PassDebuggingString S1,
 279                     enum PassDebuggingString S2, std::string Msg);
 280   void dumpAnalysisSetInfo(const char *Msg, Pass *P,
 281                            const std::vector<AnalysisID> &Set) const;
 282
 283   virtual unsigned getNumContainedPasses() {
 284     return PassVector.size();
 285   }
 286
 287   virtual PassManagerType getPassManagerType() const {
 288     assert ( 0 && "Invalid use of getPassManagerType");
 289     return PMT_Unknown;
 290   }
 291
 292   std::map<AnalysisID, Pass*> *getAvailableAnalysis() {
 293     return &AvailableAnalysis;
 294   }
 295
 296   // Collect AvailableAnalysis from all the active Pass Managers.
 297   void populateInheritedAnalysis(PMStack &PMS) {
 298     unsigned Index = 0;
 299     for (PMStack::iterator I = PMS.begin(), E = PMS.end();
 300          I != E; ++I)
 301       InheritedAnalysis[Index++] = (*I)->getAvailableAnalysis();
 302   }
 303
 304 protected:
 305
 306   // Top level manager.
 307   PMTopLevelManager *TPM;
 308
 309   // Collection of pass that are managed by this manager
 310   std::vector<Pass *> PassVector;
 311
 312   // Collection of Analysis provided by Parent pass manager and
 313   // used by current pass manager. At at time there can not be more
 314   // then PMT_Last active pass mangers.
 315   std::map<AnalysisID, Pass *> *InheritedAnalysis[PMT_Last];
 316
 317 private:
 318   // Set of available Analysis. This information is used while scheduling
 319   // pass. If a pass requires an analysis which is not not available then
 320   // equired analysis pass is scheduled to run before the pass itself is
 321   // scheduled to run.
 322   std::map<AnalysisID, Pass*> AvailableAnalysis;
 323
 324   // Collection of higher level analysis used by the pass managed by
 325   // this manager.
 326   std::vector<Pass *> HigherLevelAnalysis;
 327
 328   unsigned Depth;
 329 };
 330
 331 //===----------------------------------------------------------------------===//
 332 // FPPassManager
 333 //
 334 /// FPPassManager manages BBPassManagers and FunctionPasses.
 335 /// It batches all function passes and basic block pass managers together and
 336 /// sequence them to process one function at a time before processing next
 337 /// function.
 338
 339 class FPPassManager : public ModulePass, public PMDataManager {
 340
 341 public:
 342   static char ID;
 343   explicit FPPassManager(int Depth)
 344   : ModulePass((intptr_t)&ID), PMDataManager(Depth) { }
 345
 346   /// run - Execute all of the passes scheduled for execution.  Keep track of
 347   /// whether any of the passes modifies the module, and if so, return true.
 348   bool runOnFunction(Function &F);
 349   bool runOnModule(Module &M);
 350
 351   /// doInitialization - Run all of the initializers for the function passes.
 352   ///
 353   bool doInitialization(Module &M);
 354
 355   /// doFinalization - Run all of the initializers for the function passes.
 356   ///
 357   bool doFinalization(Module &M);
 358
 359   /// Pass Manager itself does not invalidate any analysis info.
 360   void getAnalysisUsage(AnalysisUsage &Info) const {
 361     Info.setPreservesAll();
 362   }
 363
 364   // Print passes managed by this manager
 365   void dumpPassStructure(unsigned Offset);
 366
 367   virtual const char *getPassName() const {
 368     return "Function Pass Manager";
 369   }
 370
 371   FunctionPass *getContainedPass(unsigned N) {
 372     assert ( N < PassVector.size() && "Pass number out of range!");
 373     FunctionPass *FP = static_cast<FunctionPass *>(PassVector[N]);
 374     return FP;
 375   }
 376
 377   virtual PassManagerType getPassManagerType() const {
 378     return PMT_FunctionPassManager;
 379   }
 380 };
 381
 382 }
 383
 384 extern void StartPassTimer(Pass *);
 385 extern void StopPassTimer(Pass *);