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       auto ProfileVec = [&](const SmallVectorImpl<AnalysisID>& Vec) {
 268         ID.AddInteger(Vec.size());
 269         for(AnalysisID AID : Vec)
 270           ID.AddPointer(AID);
 271       };
 272       ProfileVec(AU.getRequiredSet());
 273       ProfileVec(AU.getRequiredTransitiveSet());
 274       ProfileVec(AU.getPreservedSet());
 275       ProfileVec(AU.getUsedSet());
 276     }
 277   };
 278
 279   // Contains all of the unique combinations of AnalysisUsage.  This is helpful
 280   // when we have multiple instances of the same pass since they'll usually
 281   // have the same analysis usage and can share storage.
 282   FoldingSet<AUFoldingSetNode> UniqueAnalysisUsages;
 283
 284   // Allocator used for allocating UAFoldingSetNodes.  This handles deletion of
 285   // all allocated nodes in one fell swoop.
 286   SpecificBumpPtrAllocator<AUFoldingSetNode> AUFoldingSetNodeAllocator;
 287
 288   // Maps from a pass to it's associated entry in UniqueAnalysisUsages.  Does
 289   // not own the storage associated with either key or value..
 290   DenseMap<Pass *, AnalysisUsage*> AnUsageMap;
 291
 292   /// Collection of PassInfo objects found via analysis IDs and in this top
 293   /// level manager. This is used to memoize queries to the pass registry.
 294   /// FIXME: This is an egregious hack because querying the pass registry is
 295   /// either slow or racy.
 296   mutable DenseMap<AnalysisID, const PassInfo *> AnalysisPassInfos;
 297 };
 298
 299 //===----------------------------------------------------------------------===//
 300 // PMDataManager
 301
 302 /// PMDataManager provides the common place to manage the analysis data
 303 /// used by pass managers.
 304 class PMDataManager {
 305 public:
 306   explicit PMDataManager() : TPM(nullptr), Depth(0) {
 307     initializeAnalysisInfo();
 308   }
 309
 310   virtual ~PMDataManager();
 311
 312   virtual Pass *getAsPass() = 0;
 313
 314   /// Augment AvailableAnalysis by adding analysis made available by pass P.
 315   void recordAvailableAnalysis(Pass *P);
 316
 317   /// verifyPreservedAnalysis -- Verify analysis presreved by pass P.
 318   void verifyPreservedAnalysis(Pass *P);
 319
 320   /// Remove Analysis that is not preserved by the pass
 321   void removeNotPreservedAnalysis(Pass *P);
 322
 323   /// Remove dead passes used by P.
 324   void removeDeadPasses(Pass *P, StringRef Msg,
 325                         enum PassDebuggingString);
 326
 327   /// Remove P.
 328   void freePass(Pass *P, StringRef Msg,
 329                 enum PassDebuggingString);
 330
 331   /// Add pass P into the PassVector. Update
 332   /// AvailableAnalysis appropriately if ProcessAnalysis is true.
 333   void add(Pass *P, bool ProcessAnalysis = true);
 334
 335   /// Add RequiredPass into list of lower level passes required by pass P.
 336   /// RequiredPass is run on the fly by Pass Manager when P requests it
 337   /// through getAnalysis interface.
 338   virtual void addLowerLevelRequiredPass(Pass *P, Pass *RequiredPass);
 339
 340   virtual Pass *getOnTheFlyPass(Pass *P, AnalysisID PI, Function &F);
 341
 342   /// Initialize available analysis information.
 343   void initializeAnalysisInfo() {
 344     AvailableAnalysis.clear();
 345     for (unsigned i = 0; i < PMT_Last; ++i)
 346       InheritedAnalysis[i] = nullptr;
 347   }
 348
 349   // Return true if P preserves high level analysis used by other
 350   // passes that are managed by this manager.
 351   bool preserveHigherLevelAnalysis(Pass *P);
 352
 353   /// Populate UsedPasses with analysis pass that are used or required by pass
 354   /// P and are available. Populate ReqPassNotAvailable with analysis pass that
 355   /// are required by pass P but are not available.
 356   void collectRequiredAndUsedAnalyses(
 357       SmallVectorImpl<Pass *> &UsedPasses,
 358       SmallVectorImpl<AnalysisID> &ReqPassNotAvailable, Pass *P);
 359
 360   /// All Required analyses should be available to the pass as it runs!  Here
 361   /// we fill in the AnalysisImpls member of the pass so that it can
 362   /// successfully use the getAnalysis() method to retrieve the
 363   /// implementations it needs.
 364   void initializeAnalysisImpl(Pass *P);
 365
 366   /// Find the pass that implements Analysis AID. If desired pass is not found
 367   /// then return NULL.
 368   Pass *findAnalysisPass(AnalysisID AID, bool Direction);
 369
 370   // Access toplevel manager
 371   PMTopLevelManager *getTopLevelManager() { return TPM; }
 372   void setTopLevelManager(PMTopLevelManager *T) { TPM = T; }
 373
 374   unsigned getDepth() const { return Depth; }
 375   void setDepth(unsigned newDepth) { Depth = newDepth; }
 376
 377   // Print routines used by debug-pass
 378   void dumpLastUses(Pass *P, unsigned Offset) const;
 379   void dumpPassArguments() const;
 380   void dumpPassInfo(Pass *P, enum PassDebuggingString S1,
 381                     enum PassDebuggingString S2, StringRef Msg);
 382   void dumpRequiredSet(const Pass *P) const;
 383   void dumpPreservedSet(const Pass *P) const;
 384   void dumpUsedSet(const Pass *P) const;
 385
 386   unsigned getNumContainedPasses() const {
 387     return (unsigned)PassVector.size();
 388   }
 389
 390   virtual PassManagerType getPassManagerType() const {
 391     assert ( 0 && "Invalid use of getPassManagerType");
 392     return PMT_Unknown;
 393   }
 394
 395   DenseMap<AnalysisID, Pass*> *getAvailableAnalysis() {
 396     return &AvailableAnalysis;
 397   }
 398
 399   // Collect AvailableAnalysis from all the active Pass Managers.
 400   void populateInheritedAnalysis(PMStack &PMS) {
 401     unsigned Index = 0;
 402     for (PMStack::iterator I = PMS.begin(), E = PMS.end();
 403          I != E; ++I)
 404       InheritedAnalysis[Index++] = (*I)->getAvailableAnalysis();
 405   }
 406
 407 protected:
 408   // Top level manager.
 409   PMTopLevelManager *TPM;
 410
 411   // Collection of pass that are managed by this manager
 412   SmallVector<Pass *, 16> PassVector;
 413
 414   // Collection of Analysis provided by Parent pass manager and
 415   // used by current pass manager. At at time there can not be more
 416   // then PMT_Last active pass mangers.
 417   DenseMap<AnalysisID, Pass *> *InheritedAnalysis[PMT_Last];
 418
 419   /// isPassDebuggingExecutionsOrMore - Return true if -debug-pass=Executions
 420   /// or higher is specified.
 421   bool isPassDebuggingExecutionsOrMore() const;
 422
 423 private:
 424   void dumpAnalysisUsage(StringRef Msg, const Pass *P,
 425                          const AnalysisUsage::VectorType &Set) const;
 426
 427   // Set of available Analysis. This information is used while scheduling
 428   // pass. If a pass requires an analysis which is not available then
 429   // the required analysis pass is scheduled to run before the pass itself is
 430   // scheduled to run.
 431   DenseMap<AnalysisID, Pass*> AvailableAnalysis;
 432
 433   // Collection of higher level analysis used by the pass managed by
 434   // this manager.
 435   SmallVector<Pass *, 16> HigherLevelAnalysis;
 436
 437   unsigned Depth;
 438 };
 439
 440 //===----------------------------------------------------------------------===//
 441 // FPPassManager
 442 //
 443 /// FPPassManager manages BBPassManagers and FunctionPasses.
 444 /// It batches all function passes and basic block pass managers together and
 445 /// sequence them to process one function at a time before processing next
 446 /// function.
 447 class FPPassManager : public ModulePass, public PMDataManager {
 448 public:
 449   static char ID;
 450   explicit FPPassManager()
 451   : ModulePass(ID), PMDataManager() { }
 452
 453   /// run - Execute all of the passes scheduled for execution.  Keep track of
 454   /// whether any of the passes modifies the module, and if so, return true.
 455   bool runOnFunction(Function &F);
 456   bool runOnModule(Module &M) override;
 457
 458   /// cleanup - After running all passes, clean up pass manager cache.
 459   void cleanup();
 460
 461   /// doInitialization - Overrides ModulePass doInitialization for global
 462   /// initialization tasks
 463   ///
 464   using ModulePass::doInitialization;
 465
 466   /// doInitialization - Run all of the initializers for the function passes.
 467   ///
 468   bool doInitialization(Module &M) override;
 469
 470   /// doFinalization - Overrides ModulePass doFinalization for global
 471   /// finalization tasks
 472   ///
 473   using ModulePass::doFinalization;
 474
 475   /// doFinalization - Run all of the finalizers for the function passes.
 476   ///
 477   bool doFinalization(Module &M) override;
 478
 479   PMDataManager *getAsPMDataManager() override { return this; }
 480   Pass *getAsPass() override { return this; }
 481
 482   /// Pass Manager itself does not invalidate any analysis info.
 483   void getAnalysisUsage(AnalysisUsage &Info) const override {
 484     Info.setPreservesAll();
 485   }
 486
 487   // Print passes managed by this manager
 488   void dumpPassStructure(unsigned Offset) override;
 489
 490   const char *getPassName() const override {
 491     return "Function Pass Manager";
 492   }
 493
 494   FunctionPass *getContainedPass(unsigned N) {
 495     assert ( N < PassVector.size() && "Pass number out of range!");
 496     FunctionPass *FP = static_cast<FunctionPass *>(PassVector[N]);
 497     return FP;
 498   }
 499
 500   PassManagerType getPassManagerType() const override {
 501     return PMT_FunctionPassManager;
 502   }
 503 };
 504
 505 Timer *getPassTimer(Pass *);
 506 }
 507
 508 #endif