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