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