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
  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 //===----------------------------------------------------------------------===//
  97 // PMTopLevelManager
  98 //
  99 /// PMTopLevelManager manages LastUser info and collects common APIs used by
 100 /// top level pass managers.
 101 class PMTopLevelManager {
 102 public:
 103
 104   virtual unsigned getNumContainedManagers() {
 105     return PassManagers.size();
 106   }
 107
 108   /// Schedule pass P for execution. Make sure that passes required by
 109   /// P are run before P is run. Update analysis info maintained by
 110   /// the manager. Remove dead passes. This is a recursive function.
 111   void schedulePass(Pass *P);
 112
 113   /// This is implemented by top level pass manager and used by
 114   /// schedulePass() to add analysis info passes that are not available.
 115   virtual void addTopLevelPass(Pass  *P) = 0;
 116
 117   /// Set pass P as the last user of the given analysis passes.
 118   void setLastUser(std::vector<Pass *> &AnalysisPasses, Pass *P);
 119
 120   /// Collect passes whose last user is P
 121   void collectLastUses(std::vector<Pass *> &LastUses, Pass *P);
 122
 123   /// Find the pass that implements Analysis AID. Search immutable
 124   /// passes and all pass managers. If desired pass is not found
 125   /// then return NULL.
 126   Pass *findAnalysisPass(AnalysisID AID);
 127
 128   PMTopLevelManager(enum TopLevelManagerType t);
 129   virtual ~PMTopLevelManager();
 130
 131   /// Add immutable pass and initialize it.
 132   inline void addImmutablePass(ImmutablePass *P) {
 133     P->initializePass();
 134     ImmutablePasses.push_back(P);
 135   }
 136
 137   inline std::vector<ImmutablePass *>& getImmutablePasses() {
 138     return ImmutablePasses;
 139   }
 140
 141   void addPassManager(Pass *Manager) {
 142     PassManagers.push_back(Manager);
 143   }
 144
 145   // Add Manager into the list of managers that are not directly
 146   // maintained by this top level pass manager
 147   inline void addIndirectPassManager(PMDataManager *Manager) {
 148     IndirectPassManagers.push_back(Manager);
 149   }
 150
 151   // Print passes managed by this top level manager.
 152   void dumpPasses() const;
 153   void dumpArguments() const;
 154
 155   void initializeAllAnalysisInfo();
 156
 157   // Active Pass Managers
 158   PMStack activeStack;
 159
 160 protected:
 161
 162   /// Collection of pass managers
 163   std::vector<Pass *> PassManagers;
 164
 165 private:
 166
 167   /// Collection of pass managers that are not directly maintained
 168   /// by this pass manager
 169   std::vector<PMDataManager *> IndirectPassManagers;
 170
 171   // Map to keep track of last user of the analysis pass.
 172   // LastUser->second is the last user of Lastuser->first.
 173   std::map<Pass *, Pass *> LastUser;
 174
 175   /// Immutable passes are managed by top level manager.
 176   std::vector<ImmutablePass *> ImmutablePasses;
 177 };
 178
 179
 180
 181 //===----------------------------------------------------------------------===//
 182 // PMDataManager
 183
 184 /// PMDataManager provides the common place to manage the analysis data
 185 /// used by pass managers.
 186 class PMDataManager {
 187 public:
 188   PMDataManager(int Depth) : TPM(NULL), Depth(Depth) {
 189     initializeAnalysisInfo();
 190   }
 191
 192   virtual ~PMDataManager();
 193
 194   /// Return true IFF pass P's required analysis set does not required new
 195   /// manager.
 196   bool manageablePass(Pass *P);
 197
 198   /// Augment AvailableAnalysis by adding analysis made available by pass P.
 199   void recordAvailableAnalysis(Pass *P);
 200
 201   /// Remove Analysis that is not preserved by the pass
 202   void removeNotPreservedAnalysis(Pass *P);
 203
 204   /// Remove dead passes
 205   void removeDeadPasses(Pass *P, std::string &Msg);
 206
 207   /// Add pass P into the PassVector. Update
 208   /// AvailableAnalysis appropriately if ProcessAnalysis is true.
 209   void add(Pass *P, bool ProcessAnalysis = true);
 210
 211   /// Initialize available analysis information.
 212   void initializeAnalysisInfo() {
 213     TransferLastUses.clear();
 214     AvailableAnalysis.clear();
 215   }
 216
 217   /// Populate RequiredPasses with the analysis pass that are required by
 218   /// pass P.
 219   void collectRequiredAnalysisPasses(std::vector<Pass *> &RequiredPasses,
 220                                      Pass *P);
 221
 222   /// All Required analyses should be available to the pass as it runs!  Here
 223   /// we fill in the AnalysisImpls member of the pass so that it can
 224   /// successfully use the getAnalysis() method to retrieve the
 225   /// implementations it needs.
 226   void initializeAnalysisImpl(Pass *P);
 227
 228   /// Find the pass that implements Analysis AID. If desired pass is not found
 229   /// then return NULL.
 230   Pass *findAnalysisPass(AnalysisID AID, bool Direction);
 231
 232   // Access toplevel manager
 233   PMTopLevelManager *getTopLevelManager() { return TPM; }
 234   void setTopLevelManager(PMTopLevelManager *T) { TPM = T; }
 235
 236   unsigned getDepth() const { return Depth; }
 237
 238   // Print routines used by debug-pass
 239   void dumpLastUses(Pass *P, unsigned Offset) const;
 240   void dumpPassArguments() const;
 241   void dumpPassInfo(Pass *P,  std::string &Msg1, std::string &Msg2) const;
 242   void dumpAnalysisSetInfo(const char *Msg, Pass *P,
 243                            const std::vector<AnalysisID> &Set) const;
 244
 245   std::vector<Pass *>& getTransferredLastUses() {
 246     return TransferLastUses;
 247   }
 248
 249   virtual unsigned getNumContainedPasses() {
 250     return PassVector.size();
 251   }
 252
 253   virtual PassManagerType getPassManagerType() const {
 254     assert ( 0 && "Invalid use of getPassManagerType");
 255     return PMT_Unknown;
 256   }
 257 protected:
 258
 259   // If a FunctionPass F is the last user of ModulePass info M
 260   // then the F's manager, not F, records itself as a last user of M.
 261   // Current pass manage is requesting parent manager to record parent
 262   // manager as the last user of these TrransferLastUses passes.
 263   std::vector<Pass *> TransferLastUses;
 264
 265   // Top level manager.
 266   PMTopLevelManager *TPM;
 267
 268   // Collection of pass that are managed by this manager
 269   std::vector<Pass *> PassVector;
 270
 271 private:
 272   // Set of available Analysis. This information is used while scheduling
 273   // pass. If a pass requires an analysis which is not not available then
 274   // equired analysis pass is scheduled to run before the pass itself is
 275   // scheduled to run.
 276   std::map<AnalysisID, Pass*> AvailableAnalysis;
 277
 278   unsigned Depth;
 279 };
 280
 281 //===----------------------------------------------------------------------===//
 282 // FPPassManager
 283 //
 284 /// FPPassManager manages BBPassManagers and FunctionPasses.
 285 /// It batches all function passes and basic block pass managers together and
 286 /// sequence them to process one function at a time before processing next
 287 /// function.
 288
 289 class FPPassManager : public ModulePass, public PMDataManager {
 290
 291 public:
 292   FPPassManager(int Depth) : PMDataManager(Depth) { }
 293
 294   /// run - Execute all of the passes scheduled for execution.  Keep track of
 295   /// whether any of the passes modifies the module, and if so, return true.
 296   bool runOnFunction(Function &F);
 297   bool runOnModule(Module &M);
 298
 299   /// doInitialization - Run all of the initializers for the function passes.
 300   ///
 301   bool doInitialization(Module &M);
 302
 303   /// doFinalization - Run all of the initializers for the function passes.
 304   ///
 305   bool doFinalization(Module &M);
 306
 307   /// Pass Manager itself does not invalidate any analysis info.
 308   void getAnalysisUsage(AnalysisUsage &Info) const {
 309     Info.setPreservesAll();
 310   }
 311
 312   // Print passes managed by this manager
 313   void dumpPassStructure(unsigned Offset);
 314
 315   virtual const char *getPassName() const {
 316     return "Function Pass Manager";
 317   }
 318
 319   FunctionPass *getContainedPass(unsigned N) {
 320     assert ( N < PassVector.size() && "Pass number out of range!");
 321     FunctionPass *FP = static_cast<FunctionPass *>(PassVector[N]);
 322     return FP;
 323   }
 324
 325   virtual PassManagerType getPassManagerType() const {
 326     return PMT_FunctionPassManager;
 327   }
 328 };
 329
 330 }
 331
 332 extern void StartPassTimer(Pass *);
 333 extern void StopPassTimer(Pass *);