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 std::move(
 267       ModuleToPostOrderCGSCCPassAdaptor<CGSCCPassT>(std::move(Pass)));
 268 }
 269
 270 /// \brief A CGSCC analysis which acts as a proxy for a function analysis
 271 /// manager.
 272 ///
 273 /// This primarily proxies invalidation information from the CGSCC analysis
 274 /// manager and CGSCC pass manager to a function analysis manager. You should
 275 /// never use a function analysis manager from within (transitively) a CGSCC
 276 /// pass manager unless your parent CGSCC pass has received a proxy result
 277 /// object for it.
 278 class FunctionAnalysisManagerCGSCCProxy {
 279 public:
 280   class Result {
 281   public:
 282     explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {}
 283     // We have to explicitly define all the special member functions because
 284     // MSVC refuses to generate them.
 285     Result(const Result &Arg) : FAM(Arg.FAM) {}
 286     Result(Result &&Arg) : FAM(std::move(Arg.FAM)) {}
 287     Result &operator=(Result RHS) {
 288       std::swap(FAM, RHS.FAM);
 289       return *this;
 290     }
 291     ~Result();
 292
 293     /// \brief Accessor for the \c FunctionAnalysisManager.
 294     FunctionAnalysisManager &getManager() { return *FAM; }
 295
 296     /// \brief Handler for invalidation of the SCC.
 297     ///
 298     /// If this analysis itself is preserved, then we assume that the set of \c
 299     /// Function objects in the \c SCC hasn't changed and thus we don't need
 300     /// to invalidate *all* cached data associated with a \c Function* in the \c
 301     /// FunctionAnalysisManager.
 302     ///
 303     /// Regardless of whether this analysis is marked as preserved, all of the
 304     /// analyses in the \c FunctionAnalysisManager are potentially invalidated
 305     /// based on the set of preserved analyses.
 306     bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA);
 307
 308   private:
 309     FunctionAnalysisManager *FAM;
 310   };
 311
 312   static void *ID() { return (void *)&PassID; }
 313
 314   static StringRef name() { return "FunctionAnalysisManagerCGSCCProxy"; }
 315
 316   explicit FunctionAnalysisManagerCGSCCProxy(FunctionAnalysisManager &FAM)
 317       : FAM(&FAM) {}
 318   // We have to explicitly define all the special member functions because MSVC
 319   // refuses to generate them.
 320   FunctionAnalysisManagerCGSCCProxy(
 321       const FunctionAnalysisManagerCGSCCProxy &Arg)
 322       : FAM(Arg.FAM) {}
 323   FunctionAnalysisManagerCGSCCProxy(FunctionAnalysisManagerCGSCCProxy &&Arg)
 324       : FAM(std::move(Arg.FAM)) {}
 325   FunctionAnalysisManagerCGSCCProxy &
 326   operator=(FunctionAnalysisManagerCGSCCProxy RHS) {
 327     std::swap(FAM, RHS.FAM);
 328     return *this;
 329   }
 330
 331   /// \brief Run the analysis pass and create our proxy result object.
 332   ///
 333   /// This doesn't do any interesting work, it is primarily used to insert our
 334   /// proxy result object into the module analysis cache so that we can proxy
 335   /// invalidation to the function analysis manager.
 336   ///
 337   /// In debug builds, it will also assert that the analysis manager is empty
 338   /// as no queries should arrive at the function analysis manager prior to
 339   /// this analysis being requested.
 340   Result run(LazyCallGraph::SCC &C);
 341
 342 private:
 343   static char PassID;
 344
 345   FunctionAnalysisManager *FAM;
 346 };
 347
 348 /// \brief A function analysis which acts as a proxy for a CGSCC analysis
 349 /// manager.
 350 ///
 351 /// This primarily provides an accessor to a parent CGSCC analysis manager to
 352 /// function passes. Only the const interface of the CGSCC analysis manager is
 353 /// provided to indicate that once inside of a function analysis pass you
 354 /// cannot request a CGSCC analysis to actually run. Instead, the user must
 355 /// rely on the \c getCachedResult API.
 356 ///
 357 /// This proxy *doesn't* manage the invalidation in any way. That is handled by
 358 /// the recursive return path of each layer of the pass manager and the
 359 /// returned PreservedAnalysis set.
 360 class CGSCCAnalysisManagerFunctionProxy {
 361 public:
 362   /// \brief Result proxy object for \c ModuleAnalysisManagerFunctionProxy.
 363   class Result {
 364   public:
 365     explicit Result(const CGSCCAnalysisManager &CGAM) : CGAM(&CGAM) {}
 366     // We have to explicitly define all the special member functions because
 367     // MSVC refuses to generate them.
 368     Result(const Result &Arg) : CGAM(Arg.CGAM) {}
 369     Result(Result &&Arg) : CGAM(std::move(Arg.CGAM)) {}
 370     Result &operator=(Result RHS) {
 371       std::swap(CGAM, RHS.CGAM);
 372       return *this;
 373     }
 374
 375     const CGSCCAnalysisManager &getManager() const { return *CGAM; }
 376
 377     /// \brief Handle invalidation by ignoring it, this pass is immutable.
 378     bool invalidate(Function &) { return false; }
 379
 380   private:
 381     const CGSCCAnalysisManager *CGAM;
 382   };
 383
 384   static void *ID() { return (void *)&PassID; }
 385
 386   static StringRef name() { return "CGSCCAnalysisManagerFunctionProxy"; }
 387
 388   CGSCCAnalysisManagerFunctionProxy(const CGSCCAnalysisManager &CGAM)
 389       : CGAM(&CGAM) {}
 390   // We have to explicitly define all the special member functions because MSVC
 391   // refuses to generate them.
 392   CGSCCAnalysisManagerFunctionProxy(
 393       const CGSCCAnalysisManagerFunctionProxy &Arg)
 394       : CGAM(Arg.CGAM) {}
 395   CGSCCAnalysisManagerFunctionProxy(CGSCCAnalysisManagerFunctionProxy &&Arg)
 396       : CGAM(std::move(Arg.CGAM)) {}
 397   CGSCCAnalysisManagerFunctionProxy &
 398   operator=(CGSCCAnalysisManagerFunctionProxy RHS) {
 399     std::swap(CGAM, RHS.CGAM);
 400     return *this;
 401   }
 402
 403   /// \brief Run the analysis pass and create our proxy result object.
 404   /// Nothing to see here, it just forwards the \c CGAM reference into the
 405   /// result.
 406   Result run(Function &) { return Result(*CGAM); }
 407
 408 private:
 409   static char PassID;
 410
 411   const CGSCCAnalysisManager *CGAM;
 412 };
 413
 414 /// \brief Adaptor that maps from a SCC to its functions.
 415 ///
 416 /// Designed to allow composition of a FunctionPass(Manager) and
 417 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer
 418 /// to a \c CGSCCAnalysisManager it will run the
 419 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function
 420 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used
 421 /// within this run safely.
 422 template <typename FunctionPassT> class CGSCCToFunctionPassAdaptor {
 423 public:
 424   explicit CGSCCToFunctionPassAdaptor(FunctionPassT Pass)
 425       : Pass(std::move(Pass)) {}
 426   // We have to explicitly define all the special member functions because MSVC
 427   // refuses to generate them.
 428   CGSCCToFunctionPassAdaptor(const CGSCCToFunctionPassAdaptor &Arg)
 429       : Pass(Arg.Pass) {}
 430   CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg)
 431       : Pass(std::move(Arg.Pass)) {}
 432   friend void swap(CGSCCToFunctionPassAdaptor &LHS,
 433                    CGSCCToFunctionPassAdaptor &RHS) {
 434     using std::swap;
 435     swap(LHS.Pass, RHS.Pass);
 436   }
 437   CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) {
 438     swap(*this, RHS);
 439     return *this;
 440   }
 441
 442   /// \brief Runs the function pass across every function in the module.
 443   PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager *AM) {
 444     FunctionAnalysisManager *FAM = nullptr;
 445     if (AM)
 446       // Setup the function analysis manager from its proxy.
 447       FAM = &AM->getResult<FunctionAnalysisManagerCGSCCProxy>(C).getManager();
 448
 449     PreservedAnalyses PA = PreservedAnalyses::all();
 450     for (LazyCallGraph::Node *N : C) {
 451       PreservedAnalyses PassPA = Pass.run(N->getFunction(), FAM);
 452
 453       // We know that the function pass couldn't have invalidated any other
 454       // function's analyses (that's the contract of a function pass), so
 455       // directly handle the function analysis manager's invalidation here.
 456       // Also, update the preserved analyses to reflect that once invalidated
 457       // these can again be preserved.
 458       if (FAM)
 459         PassPA = FAM->invalidate(N->getFunction(), std::move(PassPA));
 460
 461       // Then intersect the preserved set so that invalidation of module
 462       // analyses will eventually occur when the module pass completes.
 463       PA.intersect(std::move(PassPA));
 464     }
 465
 466     // By definition we preserve the proxy. This precludes *any* invalidation
 467     // of function analyses by the proxy, but that's OK because we've taken
 468     // care to invalidate analyses in the function analysis manager
 469     // incrementally above.
 470     // FIXME: We need to update the call graph here to account for any deleted
 471     // edges!
 472     PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
 473     return PA;
 474   }
 475
 476   static StringRef name() { return "CGSCCToFunctionPassAdaptor"; }
 477
 478 private:
 479   FunctionPassT Pass;
 480 };
 481
 482 /// \brief A function to deduce a function pass type and wrap it in the
 483 /// templated adaptor.
 484 template <typename FunctionPassT>
 485 CGSCCToFunctionPassAdaptor<FunctionPassT>
 486 createCGSCCToFunctionPassAdaptor(FunctionPassT Pass) {
 487   return std::move(CGSCCToFunctionPassAdaptor<FunctionPassT>(std::move(Pass)));
 488 }
 489 }
 490
 491 #endif