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