include/llvm/Analysis/CGSCCPassManager.h

   1 //===- CGSCCPassManager.h - Call graph pass management ----------*- 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 /// \file
  10 ///
  11 /// This header provides classes for managing passes over SCCs of the call
  12 /// graph. These passes form an important component of LLVM's interprocedural
  13 /// optimizations. Because they operate on the SCCs of the call graph, and they
  14 /// wtraverse the graph in post order, they can effectively do pair-wise
  15 /// interprocedural optimizations for all call edges in the program. At each
  16 /// call site edge, the callee has already been optimized as much as is
  17 /// possible. This in turn allows very accurate analysis of it for IPO.
  18 ///
  19 //===----------------------------------------------------------------------===//
  20
  21 #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H
  22 #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H
  23
  24 #include "llvm/IR/PassManager.h"
  25 #include "llvm/Analysis/LazyCallGraph.h"
  26
  27 namespace llvm {
  28
  29 /// \brief The CGSCC analysis manager.
  30 ///
  31 /// See the documentation for the AnalysisManager template for detail
  32 /// documentation. This typedef serves as a convenient way to refer to this
  33 /// construct in the adaptors and proxies used to integrate this into the larger
  34 /// pass manager infrastructure.
  35 typedef AnalysisManager<LazyCallGraph::SCC> CGSCCAnalysisManager;
  36
  37 class CGSCCPassManager {
  38 public:
  39   // We have to explicitly define all the special member functions because MSVC
  40   // refuses to generate them.
  41   CGSCCPassManager() {}
  42   CGSCCPassManager(CGSCCPassManager &&Arg) : Passes(std::move(Arg.Passes)) {}
  43   CGSCCPassManager &operator=(CGSCCPassManager &&RHS) {
  44     Passes = std::move(RHS.Passes);
  45     return *this;
  46   }
  47
  48   /// \brief Run all of the CGSCC passes in this pass manager over a SCC.
  49   PreservedAnalyses run(LazyCallGraph::SCC &C,
  50                         CGSCCAnalysisManager *AM = nullptr);
  51
  52   template <typename CGSCCPassT> void addPass(CGSCCPassT Pass) {
  53     Passes.emplace_back(new CGSCCPassModel<CGSCCPassT>(std::move(Pass)));
  54   }
  55
  56   static StringRef name() { return "CGSCCPassManager"; }
  57
  58 private:
  59   // Pull in the concept type and model template specialized for SCCs.
  60   typedef detail::PassConcept<LazyCallGraph::SCC, CGSCCAnalysisManager>
  61       CGSCCPassConcept;
  62   template <typename PassT>
  63   struct CGSCCPassModel
  64       : detail::PassModel<LazyCallGraph::SCC, CGSCCAnalysisManager, PassT> {
  65     CGSCCPassModel(PassT Pass)
  66         : detail::PassModel<LazyCallGraph::SCC, CGSCCAnalysisManager, PassT>(
  67               std::move(Pass)) {}
  68   };
  69
  70   CGSCCPassManager(const CGSCCPassManager &) LLVM_DELETED_FUNCTION;
  71   CGSCCPassManager &operator=(const CGSCCPassManager &) LLVM_DELETED_FUNCTION;
  72
  73   std::vector<std::unique_ptr<CGSCCPassConcept>> Passes;
  74 };
  75
  76 /// \brief A module analysis which acts as a proxy for a CGSCC analysis
  77 /// manager.
  78 ///
  79 /// This primarily proxies invalidation information from the module analysis
  80 /// manager and module pass manager to a CGSCC analysis manager. You should
  81 /// never use a CGSCC analysis manager from within (transitively) a module
  82 /// pass manager unless your parent module pass has received a proxy result
  83 /// object for it.
  84 class CGSCCAnalysisManagerModuleProxy {
  85 public:
  86   class Result {
  87   public:
  88     explicit Result(CGSCCAnalysisManager &CGAM) : CGAM(&CGAM) {}
  89     // We have to explicitly define all the special member functions because
  90     // MSVC refuses to generate them.
  91     Result(const Result &Arg) : CGAM(Arg.CGAM) {}
  92     Result(Result &&Arg) : CGAM(std::move(Arg.CGAM)) {}
  93     Result &operator=(Result RHS) {
  94       std::swap(CGAM, RHS.CGAM);
  95       return *this;
  96     }
  97     ~Result();
  98
  99     /// \brief Accessor for the \c CGSCCAnalysisManager.
 100     CGSCCAnalysisManager &getManager() { return *CGAM; }
 101
 102     /// \brief Handler for invalidation of the module.
 103     ///
 104     /// If this analysis itself is preserved, then we assume that the call
 105     /// graph of the module hasn't changed and thus we don't need to invalidate
 106     /// *all* cached data associated with a \c SCC* in the \c
 107     /// CGSCCAnalysisManager.
 108     ///
 109     /// Regardless of whether this analysis is marked as preserved, all of the
 110     /// analyses in the \c CGSCCAnalysisManager are potentially invalidated
 111     /// based on the set of preserved analyses.
 112     bool invalidate(Module &M, const PreservedAnalyses &PA);
 113
 114   private:
 115     CGSCCAnalysisManager *CGAM;
 116   };
 117
 118   static void *ID() { return (void *)&PassID; }
 119
 120   static StringRef name() { return "CGSCCAnalysisManagerModuleProxy"; }
 121
 122   explicit CGSCCAnalysisManagerModuleProxy(CGSCCAnalysisManager &CGAM)
 123       : CGAM(&CGAM) {}
 124   // We have to explicitly define all the special member functions because MSVC
 125   // refuses to generate them.
 126   CGSCCAnalysisManagerModuleProxy(const CGSCCAnalysisManagerModuleProxy &Arg)
 127       : CGAM(Arg.CGAM) {}
 128   CGSCCAnalysisManagerModuleProxy(CGSCCAnalysisManagerModuleProxy &&Arg)
 129       : CGAM(std::move(Arg.CGAM)) {}
 130   CGSCCAnalysisManagerModuleProxy &
 131   operator=(CGSCCAnalysisManagerModuleProxy RHS) {
 132     std::swap(CGAM, RHS.CGAM);
 133     return *this;
 134   }
 135
 136   /// \brief Run the analysis pass and create our proxy result object.
 137   ///
 138   /// This doesn't do any interesting work, it is primarily used to insert our
 139   /// proxy result object into the module analysis cache so that we can proxy
 140   /// invalidation to the CGSCC analysis manager.
 141   ///
 142   /// In debug builds, it will also assert that the analysis manager is empty
 143   /// as no queries should arrive at the CGSCC analysis manager prior to
 144   /// this analysis being requested.
 145   Result run(Module &M);
 146
 147 private:
 148   static char PassID;
 149
 150   CGSCCAnalysisManager *CGAM;
 151 };
 152
 153 /// \brief A CGSCC analysis which acts as a proxy for a module analysis
 154 /// manager.
 155 ///
 156 /// This primarily provides an accessor to a parent module analysis manager to
 157 /// CGSCC passes. Only the const interface of the module analysis manager is
 158 /// provided to indicate that once inside of a CGSCC analysis pass you
 159 /// cannot request a module analysis to actually run. Instead, the user must
 160 /// rely on the \c getCachedResult API.
 161 ///
 162 /// This proxy *doesn't* manage the invalidation in any way. That is handled by
 163 /// the recursive return path of each layer of the pass manager and the
 164 /// returned PreservedAnalysis set.
 165 class ModuleAnalysisManagerCGSCCProxy {
 166 public:
 167   /// \brief Result proxy object for \c ModuleAnalysisManagerCGSCCProxy.
 168   class Result {
 169   public:
 170     explicit Result(const ModuleAnalysisManager &MAM) : MAM(&MAM) {}
 171     // We have to explicitly define all the special member functions because
 172     // MSVC refuses to generate them.
 173     Result(const Result &Arg) : MAM(Arg.MAM) {}
 174     Result(Result &&Arg) : MAM(std::move(Arg.MAM)) {}
 175     Result &operator=(Result RHS) {
 176       std::swap(MAM, RHS.MAM);
 177       return *this;
 178     }
 179
 180     const ModuleAnalysisManager &getManager() const { return *MAM; }
 181
 182     /// \brief Handle invalidation by ignoring it, this pass is immutable.
 183     bool invalidate(LazyCallGraph::SCC &) { return false; }
 184
 185   private:
 186     const ModuleAnalysisManager *MAM;
 187   };
 188
 189   static void *ID() { return (void *)&PassID; }
 190
 191   static StringRef name() { return "ModuleAnalysisManagerCGSCCProxy"; }
 192
 193   ModuleAnalysisManagerCGSCCProxy(const ModuleAnalysisManager &MAM)
 194       : MAM(&MAM) {}
 195   // We have to explicitly define all the special member functions because MSVC
 196   // refuses to generate them.
 197   ModuleAnalysisManagerCGSCCProxy(const ModuleAnalysisManagerCGSCCProxy &Arg)
 198       : MAM(Arg.MAM) {}
 199   ModuleAnalysisManagerCGSCCProxy(ModuleAnalysisManagerCGSCCProxy &&Arg)
 200       : MAM(std::move(Arg.MAM)) {}
 201   ModuleAnalysisManagerCGSCCProxy &
 202   operator=(ModuleAnalysisManagerCGSCCProxy RHS) {
 203     std::swap(MAM, RHS.MAM);
 204     return *this;
 205   }
 206
 207   /// \brief Run the analysis pass and create our proxy result object.
 208   /// Nothing to see here, it just forwards the \c MAM reference into the
 209   /// result.
 210   Result run(LazyCallGraph::SCC &) { return Result(*MAM); }
 211
 212 private:
 213   static char PassID;
 214
 215   const ModuleAnalysisManager *MAM;
 216 };
 217
 218 /// \brief The core module pass which does a post-order walk of the SCCs and
 219 /// runs a CGSCC pass over each one.
 220 ///
 221 /// Designed to allow composition of a CGSCCPass(Manager) and
 222 /// a ModulePassManager. Note that this pass must be run with a module analysis
 223 /// manager as it uses the LazyCallGraph analysis. It will also run the
 224 /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC
 225 /// pass over the module to enable a \c FunctionAnalysisManager to be used
 226 /// within this run safely.
 227 template <typename CGSCCPassT> class ModuleToPostOrderCGSCCPassAdaptor {
 228 public:
 229   explicit ModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass)
 230       : Pass(std::move(Pass)) {}
 231   // We have to explicitly define all the special member functions because MSVC
 232   // refuses to generate them.
 233   ModuleToPostOrderCGSCCPassAdaptor(
 234       const ModuleToPostOrderCGSCCPassAdaptor &Arg)
 235       : Pass(Arg.Pass) {}
 236   ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg)
 237       : Pass(std::move(Arg.Pass)) {}
 238   friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS,
 239                    ModuleToPostOrderCGSCCPassAdaptor &RHS) {
 240     using std::swap;
 241     swap(LHS.Pass, RHS.Pass);
 242   }
 243   ModuleToPostOrderCGSCCPassAdaptor &
 244   operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) {
 245     swap(*this, RHS);
 246     return *this;
 247   }
 248
 249   /// \brief Runs the CGSCC pass across every SCC in the module.
 250   PreservedAnalyses run(Module &M, ModuleAnalysisManager *AM) {
 251     assert(AM && "We need analyses to compute the call graph!");
 252
 253     // Setup the CGSCC analysis manager from its proxy.
 254     CGSCCAnalysisManager &CGAM =
 255         AM->getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
 256
 257     // Get the call graph for this module.
 258     LazyCallGraph &CG = AM->getResult<LazyCallGraphAnalysis>(M);
 259
 260     PreservedAnalyses PA = PreservedAnalyses::all();
 261     for (LazyCallGraph::SCC &C : CG.postorder_sccs()) {
 262       PreservedAnalyses PassPA = Pass.run(C, &CGAM);
 263
 264       // We know that the CGSCC pass couldn't have invalidated any other
 265       // SCC's analyses (that's the contract of a CGSCC pass), so
 266       // directly handle the CGSCC analysis manager's invalidation here. We
 267       // also update the preserved set of analyses to reflect that invalidated
 268       // analyses are now safe to preserve.
 269       // FIXME: This isn't quite correct. We need to handle the case where the
 270       // pass updated the CG, particularly some child of the current SCC, and
 271       // invalidate its analyses.
 272       PassPA = CGAM.invalidate(C, std::move(PassPA));
 273
 274       // Then intersect the preserved set so that invalidation of module
 275       // analyses will eventually occur when the module pass completes.
 276       PA.intersect(std::move(PassPA));
 277     }
 278
 279     // By definition we preserve the proxy. This precludes *any* invalidation
 280     // of CGSCC analyses by the proxy, but that's OK because we've taken
 281     // care to invalidate analyses in the CGSCC analysis manager
 282     // incrementally above.
 283     PA.preserve<CGSCCAnalysisManagerModuleProxy>();
 284     return PA;
 285   }
 286
 287   static StringRef name() { return "ModuleToPostOrderCGSCCPassAdaptor"; }
 288
 289 private:
 290   CGSCCPassT Pass;
 291 };
 292
 293 /// \brief A function to deduce a function pass type and wrap it in the
 294 /// templated adaptor.
 295 template <typename CGSCCPassT>
 296 ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>
 297 createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT Pass) {
 298   return std::move(
 299       ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass)));
 300 }
 301
 302 /// \brief A CGSCC analysis which acts as a proxy for a function analysis
 303 /// manager.
 304 ///
 305 /// This primarily proxies invalidation information from the CGSCC analysis
 306 /// manager and CGSCC pass manager to a function analysis manager. You should
 307 /// never use a function analysis manager from within (transitively) a CGSCC
 308 /// pass manager unless your parent CGSCC pass has received a proxy result
 309 /// object for it.
 310 class FunctionAnalysisManagerCGSCCProxy {
 311 public:
 312   class Result {
 313   public:
 314     explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
 315     // We have to explicitly define all the special member functions because
 316     // MSVC refuses to generate them.
 317     Result(const Result &Arg) : FAM(Arg.FAM) {}
 318     Result(Result &&Arg) : FAM(std::move(Arg.FAM)) {}
 319     Result &operator=(Result RHS) {
 320       std::swap(FAM, RHS.FAM);
 321       return *this;
 322     }
 323     ~Result();
 324
 325     /// \brief Accessor for the \c FunctionAnalysisManager.
 326     FunctionAnalysisManager &getManager() { return *FAM; }
 327
 328     /// \brief Handler for invalidation of the SCC.
 329     ///
 330     /// If this analysis itself is preserved, then we assume that the set of \c
 331     /// Function objects in the \c SCC hasn't changed and thus we don't need
 332     /// to invalidate *all* cached data associated with a \c Function* in the \c
 333     /// FunctionAnalysisManager.
 334     ///
 335     /// Regardless of whether this analysis is marked as preserved, all of the
 336     /// analyses in the \c FunctionAnalysisManager are potentially invalidated
 337     /// based on the set of preserved analyses.
 338     bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA);
 339
 340   private:
 341     FunctionAnalysisManager *FAM;
 342   };
 343
 344   static void *ID() { return (void *)&PassID; }
 345
 346   static StringRef name() { return "FunctionAnalysisManagerCGSCCProxy"; }
 347
 348   explicit FunctionAnalysisManagerCGSCCProxy(FunctionAnalysisManager &FAM)
 349       : FAM(&FAM) {}
 350   // We have to explicitly define all the special member functions because MSVC
 351   // refuses to generate them.
 352   FunctionAnalysisManagerCGSCCProxy(
 353       const FunctionAnalysisManagerCGSCCProxy &Arg)
 354       : FAM(Arg.FAM) {}
 355   FunctionAnalysisManagerCGSCCProxy(FunctionAnalysisManagerCGSCCProxy &&Arg)
 356       : FAM(std::move(Arg.FAM)) {}
 357   FunctionAnalysisManagerCGSCCProxy &
 358   operator=(FunctionAnalysisManagerCGSCCProxy RHS) {
 359     std::swap(FAM, RHS.FAM);
 360     return *this;
 361   }
 362
 363   /// \brief Run the analysis pass and create our proxy result object.
 364   ///
 365   /// This doesn't do any interesting work, it is primarily used to insert our
 366   /// proxy result object into the module analysis cache so that we can proxy
 367   /// invalidation to the function analysis manager.
 368   ///
 369   /// In debug builds, it will also assert that the analysis manager is empty
 370   /// as no queries should arrive at the function analysis manager prior to
 371   /// this analysis being requested.
 372   Result run(LazyCallGraph::SCC &C);
 373
 374 private:
 375   static char PassID;
 376
 377   FunctionAnalysisManager *FAM;
 378 };
 379
 380 /// \brief A function analysis which acts as a proxy for a CGSCC analysis
 381 /// manager.
 382 ///
 383 /// This primarily provides an accessor to a parent CGSCC analysis manager to
 384 /// function passes. Only the const interface of the CGSCC analysis manager is
 385 /// provided to indicate that once inside of a function analysis pass you
 386 /// cannot request a CGSCC analysis to actually run. Instead, the user must
 387 /// rely on the \c getCachedResult API.
 388 ///
 389 /// This proxy *doesn't* manage the invalidation in any way. That is handled by
 390 /// the recursive return path of each layer of the pass manager and the
 391 /// returned PreservedAnalysis set.
 392 class CGSCCAnalysisManagerFunctionProxy {
 393 public:
 394   /// \brief Result proxy object for \c ModuleAnalysisManagerFunctionProxy.
 395   class Result {
 396   public:
 397     explicit Result(const CGSCCAnalysisManager &CGAM) : CGAM(&CGAM) {}
 398     // We have to explicitly define all the special member functions because
 399     // MSVC refuses to generate them.
 400     Result(const Result &Arg) : CGAM(Arg.CGAM) {}
 401     Result(Result &&Arg) : CGAM(std::move(Arg.CGAM)) {}
 402     Result &operator=(Result RHS) {
 403       std::swap(CGAM, RHS.CGAM);
 404       return *this;
 405     }
 406
 407     const CGSCCAnalysisManager &getManager() const { return *CGAM; }
 408
 409     /// \brief Handle invalidation by ignoring it, this pass is immutable.
 410     bool invalidate(Function &) { return false; }
 411
 412   private:
 413     const CGSCCAnalysisManager *CGAM;
 414   };
 415
 416   static void *ID() { return (void *)&PassID; }
 417
 418   static StringRef name() { return "CGSCCAnalysisManagerFunctionProxy"; }
 419
 420   CGSCCAnalysisManagerFunctionProxy(const CGSCCAnalysisManager &CGAM)
 421       : CGAM(&CGAM) {}
 422   // We have to explicitly define all the special member functions because MSVC
 423   // refuses to generate them.
 424   CGSCCAnalysisManagerFunctionProxy(
 425       const CGSCCAnalysisManagerFunctionProxy &Arg)
 426       : CGAM(Arg.CGAM) {}
 427   CGSCCAnalysisManagerFunctionProxy(CGSCCAnalysisManagerFunctionProxy &&Arg)
 428       : CGAM(std::move(Arg.CGAM)) {}
 429   CGSCCAnalysisManagerFunctionProxy &
 430   operator=(CGSCCAnalysisManagerFunctionProxy RHS) {
 431     std::swap(CGAM, RHS.CGAM);
 432     return *this;
 433   }
 434
 435   /// \brief Run the analysis pass and create our proxy result object.
 436   /// Nothing to see here, it just forwards the \c CGAM reference into the
 437   /// result.
 438   Result run(Function &) { return Result(*CGAM); }
 439
 440 private:
 441   static char PassID;
 442
 443   const CGSCCAnalysisManager *CGAM;
 444 };
 445
 446 /// \brief Adaptor that maps from a SCC to its functions.
 447 ///
 448 /// Designed to allow composition of a FunctionPass(Manager) and
 449 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
 450 /// to a \c CGSCCAnalysisManager it will run the
 451 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
 452 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
 453 /// within this run safely.
 454 template <typename FunctionPassT> class CGSCCToFunctionPassAdaptor {
 455 public:
 456   explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
 457       : Pass(std::move(Pass)) {}
 458   // We have to explicitly define all the special member functions because MSVC
 459   // refuses to generate them.
 460   CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
 461       : Pass(Arg.Pass) {}
 462   CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
 463       : Pass(std::move(Arg.Pass)) {}
 464   friend void swap(CGSCCToFunctionPassAdaptor &LHS,
 465                    CGSCCToFunctionPassAdaptor &RHS) {
 466     using std::swap;
 467     swap(LHS.Pass, RHS.Pass);
 468   }
 469   CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
 470     swap(*this, RHS);
 471     return *this;
 472   }
 473
 474   /// \brief Runs the function pass across every function in the module.
 475   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager *AM) {
 476     FunctionAnalysisManager *FAM = nullptr;
 477     if (AM)
 478       // Setup the function analysis manager from its proxy.
 479       FAM = &AM->getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager();
 480
 481     PreservedAnalyses PA = PreservedAnalyses::all();
 482     for (LazyCallGraph::Node *N : C) {
 483       PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM);
 484
 485       // We know that the function pass couldn't have invalidated any other
 486       // function's analyses (that's the contract of a function pass), so
 487       // directly handle the function analysis manager's invalidation here.
 488       // Also, update the preserved analyses to reflect that once invalidated
 489       // these can again be preserved.
 490       if (FAM)
 491         PassPA = FAM->invalidate(N->getFunction(), std::move(PassPA));
 492
 493       // Then intersect the preserved set so that invalidation of module
 494       // analyses will eventually occur when the module pass completes.
 495       PA.intersect(std::move(PassPA));
 496     }
 497
 498     // By definition we preserve the proxy. This precludes *any* invalidation
 499     // of function analyses by the proxy, but that's OK because we've taken
 500     // care to invalidate analyses in the function analysis manager
 501     // incrementally above.
 502     // FIXME: We need to update the call graph here to account for any deleted
 503     // edges!
 504     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
 505     return PA;
 506   }
 507
 508   static StringRef name() { return "CGSCCToFunctionPassAdaptor"; }
 509
 510 private:
 511   FunctionPassT Pass;
 512 };
 513
 514 /// \brief A function to deduce a function pass type and wrap it in the
 515 /// templated adaptor.
 516 template <typename FunctionPassT>
 517 CGSCCToFunctionPassAdaptor<FunctionPassT>
 518 createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
 519   return std::move(CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass)));
 520 }
 521 }
 522
 523 #endif