1 //===- PassManager.h - Pass management 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 /// \file 10 /// 11 /// This header defines various interfaces for pass management in LLVM. There 12 /// is no "pass" interface in LLVM per se. Instead, an instance of any class 13 /// which supports a method to 'run' it over a unit of IR can be used as 14 /// a pass. A pass manager is generally a tool to collect a sequence of passes 15 /// which run over a particular IR construct, and run each of them in sequence 16 /// over each such construct in the containing IR construct. As there is no 17 /// containing IR construct for a Module, a manager for passes over modules 18 /// forms the base case which runs its managed passes in sequence over the 19 /// single module provided. 20 /// 21 /// The core IR library provides managers for running passes over 22 /// modules and functions. 23 /// 24 /// * FunctionPassManager can run over a Module, runs each pass over 25 /// a Function. 26 /// * ModulePassManager must be directly run, runs each pass over the Module. 27 /// 28 /// Note that the implementations of the pass managers use concept-based 29 /// polymorphism as outlined in the "Value Semantics and Concept-based 30 /// Polymorphism" talk (or its abbreviated sibling "Inheritance Is The Base 31 /// Class of Evil") by Sean Parent: 32 /// * http://github.com/sean-parent/sean-parent.github.com/wiki/Papers-and-Presentations 33 /// * http://www.youtube.com/watch?v=_BpMYeUFXv8 34 /// * http://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil 35 /// 36 //===----------------------------------------------------------------------===// 37 38 #ifndef LLVM_IR_PASSMANAGER_H 39 #define LLVM_IR_PASSMANAGER_H 40 41 #include "llvm/ADT/DenseMap.h" 42 #include "llvm/ADT/STLExtras.h" 43 #include "llvm/ADT/SmallPtrSet.h" 44 #include "llvm/IR/Function.h" 45 #include "llvm/IR/Module.h" 46 #include "llvm/IR/PassManagerInternal.h" 47 #include "llvm/Support/CommandLine.h" 48 #include "llvm/Support/Debug.h" 49 #include "llvm/Support/raw_ostream.h" 50 #include "llvm/Support/type_traits.h" 51 #include <list> 52 #include <memory> 53 #include <vector> 54 55 namespace llvm { 56 57 class Module; 58 class Function; 59 60 /// \brief An abstract set of preserved analyses following a transformation pass 61 /// run. 62 /// 63 /// When a transformation pass is run, it can return a set of analyses whose 64 /// results were preserved by that transformation. The default set is "none", 65 /// and preserving analyses must be done explicitly. 66 /// 67 /// There is also an explicit all state which can be used (for example) when 68 /// the IR is not mutated at all. 69 class PreservedAnalyses { 70 public: 71 // We have to explicitly define all the special member functions because MSVC 72 // refuses to generate them. 73 PreservedAnalyses() {} 74 PreservedAnalyses(const PreservedAnalyses &Arg) 75 : PreservedPassIDs(Arg.PreservedPassIDs) {} 76 PreservedAnalyses(PreservedAnalyses &&Arg) 77 : PreservedPassIDs(std::move(Arg.PreservedPassIDs)) {} 78 friend void swap(PreservedAnalyses &LHS, PreservedAnalyses &RHS) { 79 using std::swap; 80 swap(LHS.PreservedPassIDs, RHS.PreservedPassIDs); 81 } 82 PreservedAnalyses &operator=(PreservedAnalyses RHS) { 83 swap(*this, RHS); 84 return *this; 85 } 86 87 /// \brief Convenience factory function for the empty preserved set. 88 static PreservedAnalyses none() { return PreservedAnalyses(); } 89 90 /// \brief Construct a special preserved set that preserves all passes. 91 static PreservedAnalyses all() { 92 PreservedAnalyses PA; 93 PA.PreservedPassIDs.insert((void *)AllPassesID); 94 return PA; 95 } 96 97 /// \brief Mark a particular pass as preserved, adding it to the set. 98 template <typename PassT> void preserve() { preserve(PassT::ID()); } 99 100 /// \brief Mark an abstract PassID as preserved, adding it to the set. 101 void preserve(void *PassID) { 102 if (!areAllPreserved()) 103 PreservedPassIDs.insert(PassID); 104 } 105 106 /// \brief Intersect this set with another in place. 107 /// 108 /// This is a mutating operation on this preserved set, removing all 109 /// preserved passes which are not also preserved in the argument. 110 void intersect(const PreservedAnalyses &Arg) { 111 if (Arg.areAllPreserved()) 112 return; 113 if (areAllPreserved()) { 114 PreservedPassIDs = Arg.PreservedPassIDs; 115 return; 116 } 117 for (void *P : PreservedPassIDs) 118 if (!Arg.PreservedPassIDs.count(P)) 119 PreservedPassIDs.erase(P); 120 } 121 122 /// \brief Intersect this set with a temporary other set in place. 123 /// 124 /// This is a mutating operation on this preserved set, removing all 125 /// preserved passes which are not also preserved in the argument. 126 void intersect(PreservedAnalyses &&Arg) { 127 if (Arg.areAllPreserved()) 128 return; 129 if (areAllPreserved()) { 130 PreservedPassIDs = std::move(Arg.PreservedPassIDs); 131 return; 132 } 133 for (void *P : PreservedPassIDs) 134 if (!Arg.PreservedPassIDs.count(P)) 135 PreservedPassIDs.erase(P); 136 } 137 138 /// \brief Query whether a pass is marked as preserved by this set. 139 template <typename PassT> bool preserved() const { 140 return preserved(PassT::ID()); 141 } 142 143 /// \brief Query whether an abstract pass ID is marked as preserved by this 144 /// set. 145 bool preserved(void *PassID) const { 146 return PreservedPassIDs.count((void *)AllPassesID) || 147 PreservedPassIDs.count(PassID); 148 } 149 150 /// \brief Test whether all passes are preserved. 151 /// 152 /// This is used primarily to optimize for the case of no changes which will 153 /// common in many scenarios. 154 bool areAllPreserved() const { 155 return PreservedPassIDs.count((void *)AllPassesID); 156 } 157 158 private: 159 // Note that this must not be -1 or -2 as those are already used by the 160 // SmallPtrSet. 161 static const uintptr_t AllPassesID = (intptr_t)(-3); 162 163 SmallPtrSet<void *, 2> PreservedPassIDs; 164 }; 165 166 // Forward declare the analysis manager template. 167 template <typename IRUnitT> class AnalysisManager; 168 169 /// \brief Manages a sequence of passes over units of IR. 170 /// 171 /// A pass manager contains a sequence of passes to run over units of IR. It is 172 /// itself a valid pass over that unit of IR, and when over some given IR will 173 /// run each pass in sequence. This is the primary and most basic building 174 /// block of a pass pipeline. 175 /// 176 /// If it is run with an \c AnalysisManager<IRUnitT> argument, it will propagate 177 /// that analysis manager to each pass it runs, as well as calling the analysis 178 /// manager's invalidation routine with the PreservedAnalyses of each pass it 179 /// runs. 180 template <typename IRUnitT> class PassManager { 181 public: 182 /// \brief Construct a pass manager. 183 /// 184 /// It can be passed a flag to get debug logging as the passes are run. 185 PassManager(bool DebugLogging = false) : DebugLogging(DebugLogging) {} 186 // We have to explicitly define all the special member functions because MSVC 187 // refuses to generate them. 188 PassManager(PassManager &&Arg) 189 : Passes(std::move(Arg.Passes)), 190 DebugLogging(std::move(Arg.DebugLogging)) {} 191 PassManager &operator=(PassManager &&RHS) { 192 Passes = std::move(RHS.Passes); 193 DebugLogging = std::move(RHS.DebugLogging); 194 return *this; 195 } 196 197 /// \brief Run all of the passes in this manager over the IR. 198 PreservedAnalyses run(IRUnitT &IR, AnalysisManager<IRUnitT> *AM = nullptr) { 199 PreservedAnalyses PA = PreservedAnalyses::all(); 200 201 if (DebugLogging) 202 dbgs() << "Starting pass manager run.\n"; 203 204 for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) { 205 if (DebugLogging) 206 dbgs() << "Running pass: " << Passes[Idx]->name() << "\n"; 207 208 PreservedAnalyses PassPA = Passes[Idx]->run(IR, AM); 209 210 // If we have an active analysis manager at this level we want to ensure 211 // we update it as each pass runs and potentially invalidates analyses. 212 // We also update the preserved set of analyses based on what analyses we 213 // have already handled the invalidation for here and don't need to 214 // invalidate when finished. 215 if (AM) 216 PassPA = AM->invalidate(IR, std::move(PassPA)); 217 218 // Finally, we intersect the final preserved analyses to compute the 219 // aggregate preserved set for this pass manager. 220 PA.intersect(std::move(PassPA)); 221 222 // FIXME: Historically, the pass managers all called the LLVM context's 223 // yield function here. We don't have a generic way to acquire the 224 // context and it isn't yet clear what the right pattern is for yielding 225 // in the new pass manager so it is currently omitted. 226 //IR.getContext().yield(); 227 } 228 229 if (DebugLogging) 230 dbgs() << "Finished pass manager run.\n"; 231 232 return PA; 233 } 234 235 template <typename PassT> void addPass(PassT Pass) { 236 typedef detail::PassModel<IRUnitT, PassT> PassModelT; 237 Passes.emplace_back(new PassModelT(std::move(Pass))); 238 } 239 240 static StringRef name() { return "PassManager"; } 241 242 private: 243 typedef detail::PassConcept<IRUnitT> PassConceptT; 244 245 PassManager(const PassManager &) = delete; 246 PassManager &operator=(const PassManager &) = delete; 247 248 std::vector<std::unique_ptr<PassConceptT>> Passes; 249 250 /// \brief Flag indicating whether we should do debug logging. 251 bool DebugLogging; 252 }; 253 254 /// \brief Convenience typedef for a pass manager over modules. 255 typedef PassManager<Module> ModulePassManager; 256 257 /// \brief Convenience typedef for a pass manager over functions. 258 typedef PassManager<Function> FunctionPassManager; 259 260 namespace detail { 261 262 /// \brief A CRTP base used to implement analysis managers. 263 /// 264 /// This class template serves as the boiler plate of an analysis manager. Any 265 /// analysis manager can be implemented on top of this base class. Any 266 /// implementation will be required to provide specific hooks: 267 /// 268 /// - getResultImpl 269 /// - getCachedResultImpl 270 /// - invalidateImpl 271 /// 272 /// The details of the call pattern are within. 273 /// 274 /// Note that there is also a generic analysis manager template which implements 275 /// the above required functions along with common datastructures used for 276 /// managing analyses. This base class is factored so that if you need to 277 /// customize the handling of a specific IR unit, you can do so without 278 /// replicating *all* of the boilerplate. 279 template <typename DerivedT, typename IRUnitT> class AnalysisManagerBase { 280 DerivedT *derived_this() { return static_cast<DerivedT *>(this); } 281 const DerivedT *derived_this() const { 282 return static_cast<const DerivedT *>(this); 283 } 284 285 AnalysisManagerBase(const AnalysisManagerBase &) = delete; 286 AnalysisManagerBase & 287 operator=(const AnalysisManagerBase &) = delete; 288 289 protected: 290 typedef detail::AnalysisResultConcept<IRUnitT> ResultConceptT; 291 typedef detail::AnalysisPassConcept<IRUnitT> PassConceptT; 292 293 // FIXME: Provide template aliases for the models when we're using C++11 in 294 // a mode supporting them. 295 296 // We have to explicitly define all the special member functions because MSVC 297 // refuses to generate them. 298 AnalysisManagerBase() {} 299 AnalysisManagerBase(AnalysisManagerBase &&Arg) 300 : AnalysisPasses(std::move(Arg.AnalysisPasses)) {} 301 AnalysisManagerBase &operator=(AnalysisManagerBase &&RHS) { 302 AnalysisPasses = std::move(RHS.AnalysisPasses); 303 return *this; 304 } 305 306 public: 307 /// \brief Get the result of an analysis pass for this module. 308 /// 309 /// If there is not a valid cached result in the manager already, this will 310 /// re-run the analysis to produce a valid result. 311 template <typename PassT> typename PassT::Result &getResult(IRUnitT &IR) { 312 assert(AnalysisPasses.count(PassT::ID()) && 313 "This analysis pass was not registered prior to being queried"); 314 315 ResultConceptT &ResultConcept = 316 derived_this()->getResultImpl(PassT::ID(), IR); 317 typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result> 318 ResultModelT; 319 return static_cast<ResultModelT &>(ResultConcept).Result; 320 } 321 322 /// \brief Get the cached result of an analysis pass for this module. 323 /// 324 /// This method never runs the analysis. 325 /// 326 /// \returns null if there is no cached result. 327 template <typename PassT> 328 typename PassT::Result *getCachedResult(IRUnitT &IR) const { 329 assert(AnalysisPasses.count(PassT::ID()) && 330 "This analysis pass was not registered prior to being queried"); 331 332 ResultConceptT *ResultConcept = 333 derived_this()->getCachedResultImpl(PassT::ID(), IR); 334 if (!ResultConcept) 335 return nullptr; 336 337 typedef detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result> 338 ResultModelT; 339 return &static_cast<ResultModelT *>(ResultConcept)->Result; 340 } 341 342 /// \brief Register an analysis pass with the manager. 343 /// 344 /// This provides an initialized and set-up analysis pass to the analysis 345 /// manager. Whomever is setting up analysis passes must use this to populate 346 /// the manager with all of the analysis passes available. 347 template <typename PassT> void registerPass(PassT Pass) { 348 assert(!AnalysisPasses.count(PassT::ID()) && 349 "Registered the same analysis pass twice!"); 350 typedef detail::AnalysisPassModel<IRUnitT, PassT> PassModelT; 351 AnalysisPasses[PassT::ID()].reset(new PassModelT(std::move(Pass))); 352 } 353 354 /// \brief Invalidate a specific analysis pass for an IR module. 355 /// 356 /// Note that the analysis result can disregard invalidation. 357 template <typename PassT> void invalidate(IRUnitT &IR) { 358 assert(AnalysisPasses.count(PassT::ID()) && 359 "This analysis pass was not registered prior to being invalidated"); 360 derived_this()->invalidateImpl(PassT::ID(), IR); 361 } 362 363 /// \brief Invalidate analyses cached for an IR unit. 364 /// 365 /// Walk through all of the analyses pertaining to this unit of IR and 366 /// invalidate them unless they are preserved by the PreservedAnalyses set. 367 /// We accept the PreservedAnalyses set by value and update it with each 368 /// analyis pass which has been successfully invalidated and thus can be 369 /// preserved going forward. The updated set is returned. 370 PreservedAnalyses invalidate(IRUnitT &IR, PreservedAnalyses PA) { 371 return derived_this()->invalidateImpl(IR, std::move(PA)); 372 } 373 374 protected: 375 /// \brief Lookup a registered analysis pass. 376 PassConceptT &lookupPass(void *PassID) { 377 typename AnalysisPassMapT::iterator PI = AnalysisPasses.find(PassID); 378 assert(PI != AnalysisPasses.end() && 379 "Analysis passes must be registered prior to being queried!"); 380 return *PI->second; 381 } 382 383 /// \brief Lookup a registered analysis pass. 384 const PassConceptT &lookupPass(void *PassID) const { 385 typename AnalysisPassMapT::const_iterator PI = AnalysisPasses.find(PassID); 386 assert(PI != AnalysisPasses.end() && 387 "Analysis passes must be registered prior to being queried!"); 388 return *PI->second; 389 } 390 391 private: 392 /// \brief Map type from module analysis pass ID to pass concept pointer. 393 typedef DenseMap<void *, std::unique_ptr<PassConceptT>> AnalysisPassMapT; 394 395 /// \brief Collection of module analysis passes, indexed by ID. 396 AnalysisPassMapT AnalysisPasses; 397 }; 398 399 } // End namespace detail 400 401 /// \brief A generic analysis pass manager with lazy running and caching of 402 /// results. 403 /// 404 /// This analysis manager can be used for any IR unit where the address of the 405 /// IR unit sufficies as its identity. It manages the cache for a unit of IR via 406 /// the address of each unit of IR cached. 407 template <typename IRUnitT> 408 class AnalysisManager 409 : public detail::AnalysisManagerBase<AnalysisManager<IRUnitT>, IRUnitT> { 410 friend class detail::AnalysisManagerBase<AnalysisManager<IRUnitT>, IRUnitT>; 411 typedef detail::AnalysisManagerBase<AnalysisManager<IRUnitT>, IRUnitT> BaseT; 412 typedef typename BaseT::ResultConceptT ResultConceptT; 413 typedef typename BaseT::PassConceptT PassConceptT; 414 415 public: 416 // Most public APIs are inherited from the CRTP base class. 417 418 /// \brief Construct an empty analysis manager. 419 /// 420 /// A flag can be passed to indicate that the manager should perform debug 421 /// logging. 422 AnalysisManager(bool DebugLogging = false) : DebugLogging(DebugLogging) {} 423 424 // We have to explicitly define all the special member functions because MSVC 425 // refuses to generate them. 426 AnalysisManager(AnalysisManager &&Arg) 427 : BaseT(std::move(static_cast<BaseT &>(Arg))), 428 AnalysisResults(std::move(Arg.AnalysisResults)), 429 DebugLogging(std::move(Arg.DebugLogging)) {} 430 AnalysisManager &operator=(AnalysisManager &&RHS) { 431 BaseT::operator=(std::move(static_cast<BaseT &>(RHS))); 432 AnalysisResults = std::move(RHS.AnalysisResults); 433 DebugLogging = std::move(RHS.DebugLogging); 434 return *this; 435 } 436 437 /// \brief Returns true if the analysis manager has an empty results cache. 438 bool empty() const { 439 assert(AnalysisResults.empty() == AnalysisResultLists.empty() && 440 "The storage and index of analysis results disagree on how many " 441 "there are!"); 442 return AnalysisResults.empty(); 443 } 444 445 /// \brief Clear the analysis result cache. 446 /// 447 /// This routine allows cleaning up when the set of IR units itself has 448 /// potentially changed, and thus we can't even look up a a result and 449 /// invalidate it directly. Notably, this does *not* call invalidate functions 450 /// as there is nothing to be done for them. 451 void clear() { 452 AnalysisResults.clear(); 453 AnalysisResultLists.clear(); 454 } 455 456 private: 457 AnalysisManager(const AnalysisManager &) = delete; 458 AnalysisManager &operator=(const AnalysisManager &) = delete; 459 460 /// \brief Get an analysis result, running the pass if necessary. 461 ResultConceptT &getResultImpl(void *PassID, IRUnitT &IR) { 462 typename AnalysisResultMapT::iterator RI; 463 bool Inserted; 464 std::tie(RI, Inserted) = AnalysisResults.insert(std::make_pair( 465 std::make_pair(PassID, &IR), typename AnalysisResultListT::iterator())); 466 467 // If we don't have a cached result for this function, look up the pass and 468 // run it to produce a result, which we then add to the cache. 469 if (Inserted) { 470 auto &P = this->lookupPass(PassID); 471 if (DebugLogging) 472 dbgs() << "Running analysis: " << P.name() << "\n"; 473 AnalysisResultListT &ResultList = AnalysisResultLists[&IR]; 474 ResultList.emplace_back(PassID, P.run(IR, this)); 475 476 // P.run may have inserted elements into AnalysisResults and invalidated 477 // RI. 478 RI = AnalysisResults.find(std::make_pair(PassID, &IR)); 479 assert(RI != AnalysisResults.end() && "we just inserted it!"); 480 481 RI->second = std::prev(ResultList.end()); 482 } 483 484 return *RI->second->second; 485 } 486 487 /// \brief Get a cached analysis result or return null. 488 ResultConceptT *getCachedResultImpl(void *PassID, IRUnitT &IR) const { 489 typename AnalysisResultMapT::const_iterator RI = 490 AnalysisResults.find(std::make_pair(PassID, &IR)); 491 return RI == AnalysisResults.end() ? nullptr : &*RI->second->second; 492 } 493 494 /// \brief Invalidate a function pass result. 495 void invalidateImpl(void *PassID, IRUnitT &IR) { 496 typename AnalysisResultMapT::iterator RI = 497 AnalysisResults.find(std::make_pair(PassID, &IR)); 498 if (RI == AnalysisResults.end()) 499 return; 500 501 if (DebugLogging) 502 dbgs() << "Invalidating analysis: " << this->lookupPass(PassID).name() 503 << "\n"; 504 AnalysisResultLists[&IR].erase(RI->second); 505 AnalysisResults.erase(RI); 506 } 507 508 /// \brief Invalidate the results for a function.. 509 PreservedAnalyses invalidateImpl(IRUnitT &IR, PreservedAnalyses PA) { 510 // Short circuit for a common case of all analyses being preserved. 511 if (PA.areAllPreserved()) 512 return std::move(PA); 513 514 if (DebugLogging) 515 dbgs() << "Invalidating all non-preserved analyses for: " 516 << IR.getName() << "\n"; 517 518 // Clear all the invalidated results associated specifically with this 519 // function. 520 SmallVector<void *, 8> InvalidatedPassIDs; 521 AnalysisResultListT &ResultsList = AnalysisResultLists[&IR]; 522 for (typename AnalysisResultListT::iterator I = ResultsList.begin(), 523 E = ResultsList.end(); 524 I != E;) { 525 void *PassID = I->first; 526 527 // Pass the invalidation down to the pass itself to see if it thinks it is 528 // necessary. The analysis pass can return false if no action on the part 529 // of the analysis manager is required for this invalidation event. 530 if (I->second->invalidate(IR, PA)) { 531 if (DebugLogging) 532 dbgs() << "Invalidating analysis: " << this->lookupPass(PassID).name() 533 << "\n"; 534 535 InvalidatedPassIDs.push_back(I->first); 536 I = ResultsList.erase(I); 537 } else { 538 ++I; 539 } 540 541 // After handling each pass, we mark it as preserved. Once we've 542 // invalidated any stale results, the rest of the system is allowed to 543 // start preserving this analysis again. 544 PA.preserve(PassID); 545 } 546 while (!InvalidatedPassIDs.empty()) 547 AnalysisResults.erase( 548 std::make_pair(InvalidatedPassIDs.pop_back_val(), &IR)); 549 if (ResultsList.empty()) 550 AnalysisResultLists.erase(&IR); 551 552 return std::move(PA); 553 } 554 555 /// \brief List of function analysis pass IDs and associated concept pointers. 556 /// 557 /// Requires iterators to be valid across appending new entries and arbitrary 558 /// erases. Provides both the pass ID and concept pointer such that it is 559 /// half of a bijection and provides storage for the actual result concept. 560 typedef std::list<std::pair< 561 void *, std::unique_ptr<detail::AnalysisResultConcept<IRUnitT>>>> 562 AnalysisResultListT; 563 564 /// \brief Map type from function pointer to our custom list type. 565 typedef DenseMap<IRUnitT *, AnalysisResultListT> AnalysisResultListMapT; 566 567 /// \brief Map from function to a list of function analysis results. 568 /// 569 /// Provides linear time removal of all analysis results for a function and 570 /// the ultimate storage for a particular cached analysis result. 571 AnalysisResultListMapT AnalysisResultLists; 572 573 /// \brief Map type from a pair of analysis ID and function pointer to an 574 /// iterator into a particular result list. 575 typedef DenseMap<std::pair<void *, IRUnitT *>, 576 typename AnalysisResultListT::iterator> AnalysisResultMapT; 577 578 /// \brief Map from an analysis ID and function to a particular cached 579 /// analysis result. 580 AnalysisResultMapT AnalysisResults; 581 582 /// \brief A flag indicating whether debug logging is enabled. 583 bool DebugLogging; 584 }; 585 586 /// \brief Convenience typedef for the Module analysis manager. 587 typedef AnalysisManager<Module> ModuleAnalysisManager; 588 589 /// \brief Convenience typedef for the Function analysis manager. 590 typedef AnalysisManager<Function> FunctionAnalysisManager; 591 592 /// \brief A module analysis which acts as a proxy for a function analysis 593 /// manager. 594 /// 595 /// This primarily proxies invalidation information from the module analysis 596 /// manager and module pass manager to a function analysis manager. You should 597 /// never use a function analysis manager from within (transitively) a module 598 /// pass manager unless your parent module pass has received a proxy result 599 /// object for it. 600 class FunctionAnalysisManagerModuleProxy { 601 public: 602 class Result; 603 604 static void *ID() { return (void *)&PassID; } 605 606 static StringRef name() { return "FunctionAnalysisManagerModuleProxy"; } 607 608 explicit FunctionAnalysisManagerModuleProxy(FunctionAnalysisManager &FAM) 609 : FAM(&FAM) {} 610 // We have to explicitly define all the special member functions because MSVC 611 // refuses to generate them. 612 FunctionAnalysisManagerModuleProxy( 613 const FunctionAnalysisManagerModuleProxy &Arg) 614 : FAM(Arg.FAM) {} 615 FunctionAnalysisManagerModuleProxy(FunctionAnalysisManagerModuleProxy &&Arg) 616 : FAM(std::move(Arg.FAM)) {} 617 FunctionAnalysisManagerModuleProxy & 618 operator=(FunctionAnalysisManagerModuleProxy RHS) { 619 std::swap(FAM, RHS.FAM); 620 return *this; 621 } 622 623 /// \brief Run the analysis pass and create our proxy result object. 624 /// 625 /// This doesn't do any interesting work, it is primarily used to insert our 626 /// proxy result object into the module analysis cache so that we can proxy 627 /// invalidation to the function analysis manager. 628 /// 629 /// In debug builds, it will also assert that the analysis manager is empty 630 /// as no queries should arrive at the function analysis manager prior to 631 /// this analysis being requested. 632 Result run(Module &M); 633 634 private: 635 static char PassID; 636 637 FunctionAnalysisManager *FAM; 638 }; 639 640 /// \brief The result proxy object for the 641 /// \c FunctionAnalysisManagerModuleProxy. 642 /// 643 /// See its documentation for more information. 644 class FunctionAnalysisManagerModuleProxy::Result { 645 public: 646 explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {} 647 // We have to explicitly define all the special member functions because MSVC 648 // refuses to generate them. 649 Result(const Result &Arg) : FAM(Arg.FAM) {} 650 Result(Result &&Arg) : FAM(std::move(Arg.FAM)) {} 651 Result &operator=(Result RHS) { 652 std::swap(FAM, RHS.FAM); 653 return *this; 654 } 655 ~Result(); 656 657 /// \brief Accessor for the \c FunctionAnalysisManager. 658 FunctionAnalysisManager &getManager() { return *FAM; } 659 660 /// \brief Handler for invalidation of the module. 661 /// 662 /// If this analysis itself is preserved, then we assume that the set of \c 663 /// Function objects in the \c Module hasn't changed and thus we don't need 664 /// to invalidate *all* cached data associated with a \c Function* in the \c 665 /// FunctionAnalysisManager. 666 /// 667 /// Regardless of whether this analysis is marked as preserved, all of the 668 /// analyses in the \c FunctionAnalysisManager are potentially invalidated 669 /// based on the set of preserved analyses. 670 bool invalidate(Module &M, const PreservedAnalyses &PA); 671 672 private: 673 FunctionAnalysisManager *FAM; 674 }; 675 676 /// \brief A function analysis which acts as a proxy for a module analysis 677 /// manager. 678 /// 679 /// This primarily provides an accessor to a parent module analysis manager to 680 /// function passes. Only the const interface of the module analysis manager is 681 /// provided to indicate that once inside of a function analysis pass you 682 /// cannot request a module analysis to actually run. Instead, the user must 683 /// rely on the \c getCachedResult API. 684 /// 685 /// This proxy *doesn't* manage the invalidation in any way. That is handled by 686 /// the recursive return path of each layer of the pass manager and the 687 /// returned PreservedAnalysis set. 688 class ModuleAnalysisManagerFunctionProxy { 689 public: 690 /// \brief Result proxy object for \c ModuleAnalysisManagerFunctionProxy. 691 class Result { 692 public: 693 explicit Result(const ModuleAnalysisManager &MAM) : MAM(&MAM) {} 694 // We have to explicitly define all the special member functions because 695 // MSVC refuses to generate them. 696 Result(const Result &Arg) : MAM(Arg.MAM) {} 697 Result(Result &&Arg) : MAM(std::move(Arg.MAM)) {} 698 Result &operator=(Result RHS) { 699 std::swap(MAM, RHS.MAM); 700 return *this; 701 } 702 703 const ModuleAnalysisManager &getManager() const { return *MAM; } 704 705 /// \brief Handle invalidation by ignoring it, this pass is immutable. 706 bool invalidate(Function &) { return false; } 707 708 private: 709 const ModuleAnalysisManager *MAM; 710 }; 711 712 static void *ID() { return (void *)&PassID; } 713 714 static StringRef name() { return "ModuleAnalysisManagerFunctionProxy"; } 715 716 ModuleAnalysisManagerFunctionProxy(const ModuleAnalysisManager &MAM) 717 : MAM(&MAM) {} 718 // We have to explicitly define all the special member functions because MSVC 719 // refuses to generate them. 720 ModuleAnalysisManagerFunctionProxy( 721 const ModuleAnalysisManagerFunctionProxy &Arg) 722 : MAM(Arg.MAM) {} 723 ModuleAnalysisManagerFunctionProxy(ModuleAnalysisManagerFunctionProxy &&Arg) 724 : MAM(std::move(Arg.MAM)) {} 725 ModuleAnalysisManagerFunctionProxy & 726 operator=(ModuleAnalysisManagerFunctionProxy RHS) { 727 std::swap(MAM, RHS.MAM); 728 return *this; 729 } 730 731 /// \brief Run the analysis pass and create our proxy result object. 732 /// Nothing to see here, it just forwards the \c MAM reference into the 733 /// result. 734 Result run(Function &) { return Result(*MAM); } 735 736 private: 737 static char PassID; 738 739 const ModuleAnalysisManager *MAM; 740 }; 741 742 /// \brief Trivial adaptor that maps from a module to its functions. 743 /// 744 /// Designed to allow composition of a FunctionPass(Manager) and 745 /// a ModulePassManager. Note that if this pass is constructed with a pointer 746 /// to a \c ModuleAnalysisManager it will run the 747 /// \c FunctionAnalysisManagerModuleProxy analysis prior to running the function 748 /// pass over the module to enable a \c FunctionAnalysisManager to be used 749 /// within this run safely. 750 /// 751 /// Function passes run within this adaptor can rely on having exclusive access 752 /// to the function they are run over. They should not read or modify any other 753 /// functions! Other threads or systems may be manipulating other functions in 754 /// the module, and so their state should never be relied on. 755 /// FIXME: Make the above true for all of LLVM's actual passes, some still 756 /// violate this principle. 757 /// 758 /// Function passes can also read the module containing the function, but they 759 /// should not modify that module outside of the use lists of various globals. 760 /// For example, a function pass is not permitted to add functions to the 761 /// module. 762 /// FIXME: Make the above true for all of LLVM's actual passes, some still 763 /// violate this principle. 764 template <typename FunctionPassT> class ModuleToFunctionPassAdaptor { 765 public: 766 explicit ModuleToFunctionPassAdaptor(FunctionPassT Pass) 767 : Pass(std::move(Pass)) {} 768 // We have to explicitly define all the special member functions because MSVC 769 // refuses to generate them. 770 ModuleToFunctionPassAdaptor(const ModuleToFunctionPassAdaptor &Arg) 771 : Pass(Arg.Pass) {} 772 ModuleToFunctionPassAdaptor(ModuleToFunctionPassAdaptor &&Arg) 773 : Pass(std::move(Arg.Pass)) {} 774 friend void swap(ModuleToFunctionPassAdaptor &LHS, 775 ModuleToFunctionPassAdaptor &RHS) { 776 using std::swap; 777 swap(LHS.Pass, RHS.Pass); 778 } 779 ModuleToFunctionPassAdaptor &operator=(ModuleToFunctionPassAdaptor RHS) { 780 swap(*this, RHS); 781 return *this; 782 } 783 784 /// \brief Runs the function pass across every function in the module. 785 PreservedAnalyses run(Module &M, ModuleAnalysisManager *AM) { 786 FunctionAnalysisManager *FAM = nullptr; 787 if (AM) 788 // Setup the function analysis manager from its proxy. 789 FAM = &AM->getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 790 791 PreservedAnalyses PA = PreservedAnalyses::all(); 792 for (Function &F : M) { 793 if (F.isDeclaration()) 794 continue; 795 796 PreservedAnalyses PassPA = Pass.run(F, FAM); 797 798 // We know that the function pass couldn't have invalidated any other 799 // function's analyses (that's the contract of a function pass), so 800 // directly handle the function analysis manager's invalidation here and 801 // update our preserved set to reflect that these have already been 802 // handled. 803 if (FAM) 804 PassPA = FAM->invalidate(F, std::move(PassPA)); 805 806 // Then intersect the preserved set so that invalidation of module 807 // analyses will eventually occur when the module pass completes. 808 PA.intersect(std::move(PassPA)); 809 } 810 811 // By definition we preserve the proxy. This precludes *any* invalidation 812 // of function analyses by the proxy, but that's OK because we've taken 813 // care to invalidate analyses in the function analysis manager 814 // incrementally above. 815 PA.preserve<FunctionAnalysisManagerModuleProxy>(); 816 return PA; 817 } 818 819 static StringRef name() { return "ModuleToFunctionPassAdaptor"; } 820 821 private: 822 FunctionPassT Pass; 823 }; 824 825 /// \brief A function to deduce a function pass type and wrap it in the 826 /// templated adaptor. 827 template <typename FunctionPassT> 828 ModuleToFunctionPassAdaptor<FunctionPassT> 829 createModuleToFunctionPassAdaptor(FunctionPassT Pass) { 830 return std::move(ModuleToFunctionPassAdaptor<FunctionPassT>(std::move(Pass))); 831 } 832 833 /// \brief A template utility pass to force an analysis result to be available. 834 /// 835 /// This is a no-op pass which simply forces a specific analysis pass's result 836 /// to be available when it is run. 837 template <typename AnalysisT> struct RequireAnalysisPass { 838 /// \brief Run this pass over some unit of IR. 839 /// 840 /// This pass can be run over any unit of IR and use any analysis manager 841 /// provided they satisfy the basic API requirements. When this pass is 842 /// created, these methods can be instantiated to satisfy whatever the 843 /// context requires. 844 template <typename IRUnitT> 845 PreservedAnalyses run(IRUnitT &Arg, AnalysisManager<IRUnitT> *AM) { 846 if (AM) 847 (void)AM->template getResult<AnalysisT>(Arg); 848 849 return PreservedAnalyses::all(); 850 } 851 852 static StringRef name() { return "RequireAnalysisPass"; } 853 }; 854 855 /// \brief A template utility pass to force an analysis result to be 856 /// invalidated. 857 /// 858 /// This is a no-op pass which simply forces a specific analysis result to be 859 /// invalidated when it is run. 860 template <typename AnalysisT> struct InvalidateAnalysisPass { 861 /// \brief Run this pass over some unit of IR. 862 /// 863 /// This pass can be run over any unit of IR and use any analysis manager 864 /// provided they satisfy the basic API requirements. When this pass is 865 /// created, these methods can be instantiated to satisfy whatever the 866 /// context requires. 867 template <typename IRUnitT> 868 PreservedAnalyses run(IRUnitT &Arg, AnalysisManager<IRUnitT> *AM) { 869 if (AM) 870 // We have to directly invalidate the analysis result as we can't 871 // enumerate all other analyses and use the preserved set to control it. 872 (void)AM->template invalidate<AnalysisT>(Arg); 873 874 return PreservedAnalyses::all(); 875 } 876 877 static StringRef name() { return "InvalidateAnalysisPass"; } 878 }; 879 880 /// \brief A utility pass that does nothing but preserves no analyses. 881 /// 882 /// As a consequence fo not preserving any analyses, this pass will force all 883 /// analysis passes to be re-run to produce fresh results if any are needed. 884 struct InvalidateAllAnalysesPass { 885 /// \brief Run this pass over some unit of IR. 886 template <typename IRUnitT> PreservedAnalyses run(IRUnitT &Arg) { 887 return PreservedAnalyses::none(); 888 } 889 890 static StringRef name() { return "InvalidateAllAnalysesPass"; } 891 }; 892 893 } 894 895 #endif 896