include/llvm/IR/LegacyPassManagers.h

   1 //===- LegacyPassManagers.h - Legacy Pass Infrastructure --------*- C++ -*-===//
   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 declares the LLVM Pass Manager infrastructure.
  11 //
  12 //===----------------------------------------------------------------------===//
  13
  14 #ifndef LLVM_IR_LEGACYPASSMANAGERS_H
  15 #define LLVM_IR_LEGACYPASSMANAGERS_H
  16
  17 #include "llvm/ADT/ArrayRef.h"
  18 #include "llvm/ADT/DenseMap.h"
  19 #include "llvm/ADT/FoldingSet.h"
  20 #include "llvm/ADT/SmallPtrSet.h"
  21 #include "llvm/ADT/SmallVector.h"
  22 #include "llvm/Pass.h"
  23 #include <map>
  24 #include <vector>
  25
  26 //===----------------------------------------------------------------------===//
  27 // Overview:
  28 // The Pass Manager Infrastructure manages passes. It's responsibilities are:
  29 //
  30 //   o Manage optimization pass execution order
  31 //   o Make required Analysis information available before pass P is run
  32 //   o Release memory occupied by dead passes
  33 //   o If Analysis information is dirtied by a pass then regenerate Analysis
  34 //     information before it is consumed by another pass.
  35 //
  36 // Pass Manager Infrastructure uses multiple pass managers.  They are
  37 // PassManager, FunctionPassManager, MPPassManager, FPPassManager, BBPassManager.
  38 // This class hierarchy uses multiple inheritance but pass managers do not
  39 // derive from another pass manager.
  40 //
  41 // PassManager and FunctionPassManager are two top-level pass manager that
  42 // represents the external interface of this entire pass manager infrastucture.
  43 //
  44 // Important classes :
  45 //
  46 // [o] class PMTopLevelManager;
  47 //
  48 // Two top level managers, PassManager and FunctionPassManager, derive from
  49 // PMTopLevelManager. PMTopLevelManager manages information used by top level
  50 // managers such as last user info.
  51 //
  52 // [o] class PMDataManager;
  53 //
  54 // PMDataManager manages information, e.g. list of available analysis info,
  55 // used by a pass manager to manage execution order of passes. It also provides
  56 // a place to implement common pass manager APIs. All pass managers derive from
  57 // PMDataManager.
  58 //
  59 // [o] class BBPassManager : public FunctionPass, public PMDataManager;
  60 //
  61 // BBPassManager manages BasicBlockPasses.
  62 //
  63 // [o] class FunctionPassManager;
  64 //
  65 // This is a external interface used to manage FunctionPasses. This
  66 // interface relies on FunctionPassManagerImpl to do all the tasks.
  67 //
  68 // [o] class FunctionPassManagerImpl : public ModulePass, PMDataManager,
  69 //                                     public PMTopLevelManager;
  70 //
  71 // FunctionPassManagerImpl is a top level manager. It manages FPPassManagers
  72 //
  73 // [o] class FPPassManager : public ModulePass, public PMDataManager;
  74 //
  75 // FPPassManager manages FunctionPasses and BBPassManagers
  76 //
  77 // [o] class MPPassManager : public Pass, public PMDataManager;
  78 //
  79 // MPPassManager manages ModulePasses and FPPassManagers
  80 //
  81 // [o] class PassManager;
  82 //
  83 // This is a external interface used by various tools to manages passes. It
  84 // relies on PassManagerImpl to do all the tasks.
  85 //
  86 // [o] class PassManagerImpl : public Pass, public PMDataManager,
  87 //                             public PMTopLevelManager
  88 //
  89 // PassManagerImpl is a top level pass manager responsible for managing
  90 // MPPassManagers.
  91 //===----------------------------------------------------------------------===//
  92
  93 #include "llvm/Support/PrettyStackTrace.h"
  94
  95 namespace llvm {
  96   class Module;
  97   class Pass;
  98   class StringRef;
  99   class Value;
 100   class Timer;
 101   class PMDataManager;
 102
 103 // enums for debugging strings
 104 enum PassDebuggingString {
 105   EXECUTION_MSG, // "Executing Pass '" + PassName
 106   MODIFICATION_MSG, // "Made Modification '" + PassName
 107   FREEING_MSG, // " Freeing Pass '" + PassName
 108   ON_BASICBLOCK_MSG, // "' on BasicBlock '" + InstructionName + "'...\n"
 109   ON_FUNCTION_MSG, // "' on Function '" + FunctionName + "'...\n"
 110   ON_MODULE_MSG, // "' on Module '" + ModuleName + "'...\n"
 111   ON_REGION_MSG, // "' on Region '" + Msg + "'...\n'"
 112   ON_LOOP_MSG, // "' on Loop '" + Msg + "'...\n'"
 113   ON_CG_MSG // "' on Call Graph Nodes '" + Msg + "'...\n'"
 114 };
 115
 116 /// PassManagerPrettyStackEntry - This is used to print informative information
 117 /// about what pass is running when/if a stack trace is generated.
 118 class PassManagerPrettyStackEntry : public PrettyStackTraceEntry {
 119   Pass *P;
 120   Value *V;
 121   Module *M;
 122
 123 public:
 124   explicit PassManagerPrettyStackEntry(Pass *p)
 125     : P(p), V(nullptr), M(nullptr) {}  // When P is releaseMemory'd.
 126   PassManagerPrettyStackEntry(Pass *p, Value &v)
 127     : P(p), V(&v), M(nullptr) {} // When P is run on V
 128   PassManagerPrettyStackEntry(Pass *p, Module &m)
 129     : P(p), V(nullptr), M(&m) {} // When P is run on M
 130
 131   /// print - Emit information about this stack frame to OS.
 132   void print(raw_ostream &OS) const override;
 133 };
 134
 135 //===----------------------------------------------------------------------===//
 136 // PMStack
 137 //
 138 /// PMStack - This class implements a stack data structure of PMDataManager
 139 /// pointers.
 140 ///
 141 /// Top level pass managers (see PassManager.cpp) maintain active Pass Managers
 142 /// using PMStack. Each Pass implements assignPassManager() to connect itself
 143 /// with appropriate manager. assignPassManager() walks PMStack to find
 144 /// suitable manager.
 145 class PMStack {
 146 public:
 147   typedef std::vector<PMDataManager *>::const_reverse_iterator iterator;
 148   iterator begin() const { return S.rbegin(); }
 149   iterator end() const { return S.rend(); }
 150
 151   void pop();
 152   PMDataManager *top() const { return S.back(); }
 153   void push(PMDataManager *PM);
 154   bool empty() const { return S.empty(); }
 155
 156   void dump() const;
 157
 158 private:
 159   std::vector<PMDataManager *> S;
 160 };
 161
 162 //===----------------------------------------------------------------------===//
 163 // PMTopLevelManager
 164 //
 165 /// PMTopLevelManager manages LastUser info and collects common APIs used by
 166 /// top level pass managers.
 167 class PMTopLevelManager {
 168 protected:
 169   explicit PMTopLevelManager(PMDataManager *PMDM);
 170
 171   unsigned getNumContainedManagers() const {
 172     return (unsigned)PassManagers.size();
 173   }
 174
 175   void initializeAllAnalysisInfo();
 176
 177 private:
 178   virtual PMDataManager *getAsPMDataManager() = 0;
 179   virtual PassManagerType getTopLevelPassManagerType() = 0;
 180
 181 public:
 182   /// Schedule pass P for execution. Make sure that passes required by
 183   /// P are run before P is run. Update analysis info maintained by
 184   /// the manager. Remove dead passes. This is a recursive function.
 185   void schedulePass(Pass *P);
 186
 187   /// Set pass P as the last user of the given analysis passes.
 188   void setLastUser(ArrayRef<Pass*> AnalysisPasses, Pass *P);
 189
 190   /// Collect passes whose last user is P
 191   void collectLastUses(SmallVectorImpl<Pass *> &LastUses, Pass *P);
 192
 193   /// Find the pass that implements Analysis AID. Search immutable
 194   /// passes and all pass managers. If desired pass is not found
 195   /// then return NULL.
 196   Pass *findAnalysisPass(AnalysisID AID);
 197
 198   /// Retrieve the PassInfo for an analysis.
 199   const PassInfo *findAnalysisPassInfo(AnalysisID AID) const;
 200
 201   /// Find analysis usage information for the pass P.
 202   AnalysisUsage *findAnalysisUsage(Pass *P);
 203
 204   virtual ~PMTopLevelManager();
 205
 206   /// Add immutable pass and initialize it.
 207   void addImmutablePass(ImmutablePass *P);
 208
 209   inline SmallVectorImpl<ImmutablePass *>& getImmutablePasses() {
 210     return ImmutablePasses;
 211   }
 212
 213   void addPassManager(PMDataManager *Manager) {
 214     PassManagers.push_back(Manager);
 215   }
 216
 217   // Add Manager into the list of managers that are not directly
 218   // maintained by this top level pass manager
 219   inline void addIndirectPassManager(PMDataManager *Manager) {
 220     IndirectPassManagers.push_back(Manager);
 221   }
 222
 223   // Print passes managed by this top level manager.
 224   void dumpPasses() const;
 225   void dumpArguments() const;
 226
 227   // Active Pass Managers
 228   PMStack activeStack;
 229
 230 protected:
 231   /// Collection of pass managers
 232   SmallVector<PMDataManager *, 8> PassManagers;
 233
 234 private:
 235   /// Collection of pass managers that are not directly maintained
 236   /// by this pass manager
 237   SmallVector<PMDataManager *, 8> IndirectPassManagers;
 238
 239   // Map to keep track of last user of the analysis pass.
 240   // LastUser->second is the last user of Lastuser->first.
 241   DenseMap<Pass *, Pass *> LastUser;
 242
 243   // Map to keep track of passes that are last used by a pass.
 244   // This inverse map is initialized at PM->run() based on
 245   // LastUser map.
 246   DenseMap<Pass *, SmallPtrSet<Pass *, 8> > InversedLastUser;
 247
 248   /// Immutable passes are managed by top level manager.
 249   SmallVector<ImmutablePass *, 16> ImmutablePasses;
 250
 251   /// Map from ID to immutable passes.
 252   SmallDenseMap<AnalysisID, ImmutablePass *, 8> ImmutablePassMap;
 253
 254
 255   /// A wrapper around AnalysisUsage for the purpose of uniqueing.  The wrapper
 256   /// is used to avoid needing to make AnalysisUsage itself a folding set node.
 257   struct AUFoldingSetNode : public FoldingSetNode {
 258     AnalysisUsage AU;
 259     AUFoldingSetNode(const AnalysisUsage &AU) : AU(AU) {}
 260     void Profile(FoldingSetNodeID &ID) const {
 261       Profile(ID, AU);
 262     }
 263     static void Profile(FoldingSetNodeID &ID, const AnalysisUsage &AU) {
 264       // TODO: We could consider sorting the dependency arrays within the
 265       // AnalysisUsage (since they are conceptually unordered).
 266       ID.AddBoolean(AU.getPreservesAll());
 267       for (auto &Vec : {AU.getRequiredSet(), AU.getRequiredTransitiveSet(),
 268             AU.getPreservedSet(), AU.getUsedSet()}) {
 269         ID.AddInteger(Vec.size());
 270         for(AnalysisID AID : Vec)
 271           ID.AddPointer(AID);
 272       }
 273     }
 274   };
 275
 276   // Contains all of the unique combinations of AnalysisUsage.  This is helpful
 277   // when we have multiple instances of the same pass since they'll usually
 278   // have the same analysis usage and can share storage.
 279   FoldingSet<AUFoldingSetNode> UniqueAnalysisUsages;
 280
 281   // Allocator used for allocating UAFoldingSetNodes.  This handles deletion of
 282   // all allocated nodes in one fell swoop.
 283   BumpPtrAllocator AUFoldingSetNodeAllocator;
 284
 285   // Maps from a pass to it's associated entry in UniqueAnalysisUsages.  Does
 286   // not own the storage associated with either key or value..
 287   DenseMap<Pass *, AnalysisUsage*> AnUsageMap;
 288
 289   /// Collection of PassInfo objects found via analysis IDs and in this top
 290   /// level manager. This is used to memoize queries to the pass registry.
 291   /// FIXME: This is an egregious hack because querying the pass registry is
 292   /// either slow or racy.
 293   mutable DenseMap<AnalysisID, const PassInfo *> AnalysisPassInfos;
 294 };
 295
 296 //===----------------------------------------------------------------------===//
 297 // PMDataManager
 298
 299 /// PMDataManager provides the common place to manage the analysis data
 300 /// used by pass managers.
 301 class PMDataManager {
 302 public:
 303   explicit PMDataManager() : TPM(nullptr), Depth(0) {
 304     initializeAnalysisInfo();
 305   }
 306
 307   virtual ~PMDataManager();
 308
 309   virtual Pass *getAsPass() = 0;
 310
 311   /// Augment AvailableAnalysis by adding analysis made available by pass P.
 312   void recordAvailableAnalysis(Pass *P);
 313
 314   /// verifyPreservedAnalysis -- Verify analysis presreved by pass P.
 315   void verifyPreservedAnalysis(Pass *P);
 316
 317   /// Remove Analysis that is not preserved by the pass
 318   void removeNotPreservedAnalysis(Pass *P);
 319
 320   /// Remove dead passes used by P.
 321   void removeDeadPasses(Pass *P, StringRef Msg,
 322                         enum PassDebuggingString);
 323
 324   /// Remove P.
 325   void freePass(Pass *P, StringRef Msg,
 326                 enum PassDebuggingString);
 327
 328   /// Add pass P into the PassVector. Update
 329   /// AvailableAnalysis appropriately if ProcessAnalysis is true.
 330   void add(Pass *P, bool ProcessAnalysis = true);
 331
 332   /// Add RequiredPass into list of lower level passes required by pass P.
 333   /// RequiredPass is run on the fly by Pass Manager when P requests it
 334   /// through getAnalysis interface.
 335   virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass);
 336
 337   virtual Pass *getOnTheFlyPass(Pass *P, AnalysisID PI, Function &F);
 338
 339   /// Initialize available analysis information.
 340   void initializeAnalysisInfo() {
 341     AvailableAnalysis.clear();
 342     for (unsigned i = 0; i < PMT_Last; ++i)
 343       InheritedAnalysis[i] = nullptr;
 344   }
 345
 346   // Return true if P preserves high level analysis used by other
 347   // passes that are managed by this manager.
 348   bool preserveHigherLevelAnalysis(Pass *P);
 349
 350   /// Populate UsedPasses with analysis pass that are used or required by pass
 351   /// P and are available. Populate ReqPassNotAvailable with analysis pass that
 352   /// are required by pass P but are not available.
 353   void collectRequiredAndUsedAnalyses(
 354       SmallVectorImpl<Pass *> &UsedPasses,
 355       SmallVectorImpl<AnalysisID> &ReqPassNotAvailable, Pass *P);
 356
 357   /// All Required analyses should be available to the pass as it runs!  Here
 358   /// we fill in the AnalysisImpls member of the pass so that it can
 359   /// successfully use the getAnalysis() method to retrieve the
 360   /// implementations it needs.
 361   void initializeAnalysisImpl(Pass *P);
 362
 363   /// Find the pass that implements Analysis AID. If desired pass is not found
 364   /// then return NULL.
 365   Pass *findAnalysisPass(AnalysisID AID, bool Direction);
 366
 367   // Access toplevel manager
 368   PMTopLevelManager *getTopLevelManager() { return TPM; }
 369   void setTopLevelManager(PMTopLevelManager *T) { TPM = T; }
 370
 371   unsigned getDepth() const { return Depth; }
 372   void setDepth(unsigned newDepth) { Depth = newDepth; }
 373
 374   // Print routines used by debug-pass
 375   void dumpLastUses(Pass *P, unsigned Offset) const;
 376   void dumpPassArguments() const;
 377   void dumpPassInfo(Pass *P, enum PassDebuggingString S1,
 378                     enum PassDebuggingString S2, StringRef Msg);
 379   void dumpRequiredSet(const Pass *P) const;
 380   void dumpPreservedSet(const Pass *P) const;
 381   void dumpUsedSet(const Pass *P) const;
 382
 383   unsigned getNumContainedPasses() const {
 384     return (unsigned)PassVector.size();
 385   }
 386
 387   virtual PassManagerType getPassManagerType() const {
 388     assert ( 0 && "Invalid use of getPassManagerType");
 389     return PMT_Unknown;
 390   }
 391
 392   DenseMap<AnalysisID, Pass*> *getAvailableAnalysis() {
 393     return &AvailableAnalysis;
 394   }
 395
 396   // Collect AvailableAnalysis from all the active Pass Managers.
 397   void populateInheritedAnalysis(PMStack &PMS) {
 398     unsigned Index = 0;
 399     for (PMStack::iterator I = PMS.begin(), E = PMS.end();
 400          I != E; ++I)
 401       InheritedAnalysis[Index++] = (*I)->getAvailableAnalysis();
 402   }
 403
 404 protected:
 405   // Top level manager.
 406   PMTopLevelManager *TPM;
 407
 408   // Collection of pass that are managed by this manager
 409   SmallVector<Pass *, 16> PassVector;
 410
 411   // Collection of Analysis provided by Parent pass manager and
 412   // used by current pass manager. At at time there can not be more
 413   // then PMT_Last active pass mangers.
 414   DenseMap<AnalysisID, Pass *> *InheritedAnalysis[PMT_Last];
 415
 416   /// isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions
 417   /// or higher is specified.
 418   bool isPassDebuggingExecutionsOrMore() const;
 419
 420 private:
 421   void dumpAnalysisUsage(StringRef Msg, const Pass *P,
 422                          const AnalysisUsage::VectorType &Set) const;
 423
 424   // Set of available Analysis. This information is used while scheduling
 425   // pass. If a pass requires an analysis which is not available then
 426   // the required analysis pass is scheduled to run before the pass itself is
 427   // scheduled to run.
 428   DenseMap<AnalysisID, Pass*> AvailableAnalysis;
 429
 430   // Collection of higher level analysis used by the pass managed by
 431   // this manager.
 432   SmallVector<Pass *, 16> HigherLevelAnalysis;
 433
 434   unsigned Depth;
 435 };
 436
 437 //===----------------------------------------------------------------------===//
 438 // FPPassManager
 439 //
 440 /// FPPassManager manages BBPassManagers and FunctionPasses.
 441 /// It batches all function passes and basic block pass managers together and
 442 /// sequence them to process one function at a time before processing next
 443 /// function.
 444 class FPPassManager : public ModulePass, public PMDataManager {
 445 public:
 446   static char ID;
 447   explicit FPPassManager()
 448   : ModulePass(ID), PMDataManager() { }
 449
 450   /// run - Execute all of the passes scheduled for execution.  Keep track of
 451   /// whether any of the passes modifies the module, and if so, return true.
 452   bool runOnFunction(Function &F);
 453   bool runOnModule(Module &M) override;
 454
 455   /// cleanup - After running all passes, clean up pass manager cache.
 456   void cleanup();
 457
 458   /// doInitialization - Overrides ModulePass doInitialization for global
 459   /// initialization tasks
 460   ///
 461   using ModulePass::doInitialization;
 462
 463   /// doInitialization - Run all of the initializers for the function passes.
 464   ///
 465   bool doInitialization(Module &M) override;
 466
 467   /// doFinalization - Overrides ModulePass doFinalization for global
 468   /// finalization tasks
 469   ///
 470   using ModulePass::doFinalization;
 471
 472   /// doFinalization - Run all of the finalizers for the function passes.
 473   ///
 474   bool doFinalization(Module &M) override;
 475
 476   PMDataManager *getAsPMDataManager() override { return this; }
 477   Pass *getAsPass() override { return this; }
 478
 479   /// Pass Manager itself does not invalidate any analysis info.
 480   void getAnalysisUsage(AnalysisUsage &Info) const override {
 481     Info.setPreservesAll();
 482   }
 483
 484   // Print passes managed by this manager
 485   void dumpPassStructure(unsigned Offset) override;
 486
 487   const char *getPassName() const override {
 488     return "Function Pass Manager";
 489   }
 490
 491   FunctionPass *getContainedPass(unsigned N) {
 492     assert ( N < PassVector.size() && "Pass number out of range!");
 493     FunctionPass *FP = static_cast<FunctionPass *>(PassVector[N]);
 494     return FP;
 495   }
 496
 497   PassManagerType getPassManagerType() const override {
 498     return PMT_FunctionPassManager;
 499   }
 500 };
 501
 502 Timer *getPassTimer(Pass *);
 503 }
 504
 505 #endif