1 //===- PassManager.h - Pass management infrastructure -----------*- C++ -*-===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 /// \file 9 /// 10 /// This header defines various interfaces for pass management in LLVM. There 11 /// is no "pass" interface in LLVM per se. Instead, an instance of any class 12 /// which supports a method to 'run' it over a unit of IR can be used as 13 /// a pass. A pass manager is generally a tool to collect a sequence of passes 14 /// which run over a particular IR construct, and run each of them in sequence 15 /// over each such construct in the containing IR construct. As there is no 16 /// containing IR construct for a Module, a manager for passes over modules 17 /// forms the base case which runs its managed passes in sequence over the 18 /// single module provided. 19 /// 20 /// The core IR library provides managers for running passes over 21 /// modules and functions. 22 /// 23 /// * FunctionPassManager can run over a Module, runs each pass over 24 /// a Function. 25 /// * ModulePassManager must be directly run, runs each pass over the Module. 26 /// 27 /// Note that the implementations of the pass managers use concept-based 28 /// polymorphism as outlined in the "Value Semantics and Concept-based 29 /// Polymorphism" talk (or its abbreviated sibling "Inheritance Is The Base 30 /// Class of Evil") by Sean Parent: 31 /// * http://github.com/sean-parent/sean-parent.github.com/wiki/Papers-and-Presentations 32 /// * http://www.youtube.com/watch?v=_BpMYeUFXv8 33 /// * http://channel9.msdn.com/Events/GoingNative/2013/Inheritance-Is-The-Base-Class-of-Evil 34 /// 35 //===----------------------------------------------------------------------===// 36 37 #ifndef LLVM_IR_PASSMANAGER_H 38 #define LLVM_IR_PASSMANAGER_H 39 40 #include "llvm/ADT/DenseMap.h" 41 #include "llvm/ADT/SmallPtrSet.h" 42 #include "llvm/ADT/StringRef.h" 43 #include "llvm/ADT/TinyPtrVector.h" 44 #include "llvm/IR/Function.h" 45 #include "llvm/IR/Module.h" 46 #include "llvm/IR/PassInstrumentation.h" 47 #include "llvm/IR/PassManagerInternal.h" 48 #include "llvm/Pass.h" 49 #include "llvm/Support/Debug.h" 50 #include "llvm/Support/TimeProfiler.h" 51 #include "llvm/Support/TypeName.h" 52 #include <algorithm> 53 #include <cassert> 54 #include <cstring> 55 #include <iterator> 56 #include <list> 57 #include <memory> 58 #include <tuple> 59 #include <type_traits> 60 #include <utility> 61 #include <vector> 62 63 namespace llvm { 64 65 /// A special type used by analysis passes to provide an address that 66 /// identifies that particular analysis pass type. 67 /// 68 /// Analysis passes should have a static data member of this type and derive 69 /// from the \c AnalysisInfoMixin to get a static ID method used to identify 70 /// the analysis in the pass management infrastructure. 71 struct alignas(8) AnalysisKey {}; 72 73 /// A special type used to provide an address that identifies a set of related 74 /// analyses. These sets are primarily used below to mark sets of analyses as 75 /// preserved. 76 /// 77 /// For example, a transformation can indicate that it preserves the CFG of a 78 /// function by preserving the appropriate AnalysisSetKey. An analysis that 79 /// depends only on the CFG can then check if that AnalysisSetKey is preserved; 80 /// if it is, the analysis knows that it itself is preserved. 81 struct alignas(8) AnalysisSetKey {}; 82 83 /// This templated class represents "all analyses that operate over \<a 84 /// particular IR unit\>" (e.g. a Function or a Module) in instances of 85 /// PreservedAnalysis. 86 /// 87 /// This lets a transformation say e.g. "I preserved all function analyses". 88 /// 89 /// Note that you must provide an explicit instantiation declaration and 90 /// definition for this template in order to get the correct behavior on 91 /// Windows. Otherwise, the address of SetKey will not be stable. 92 template <typename IRUnitT> class AllAnalysesOn { 93 public: 94 static AnalysisSetKey *ID() { return &SetKey; } 95 96 private: 97 static AnalysisSetKey SetKey; 98 }; 99 100 template <typename IRUnitT> AnalysisSetKey AllAnalysesOn<IRUnitT>::SetKey; 101 102 extern template class AllAnalysesOn<Module>; 103 extern template class AllAnalysesOn<Function>; 104 105 /// Represents analyses that only rely on functions' control flow. 106 /// 107 /// This can be used with \c PreservedAnalyses to mark the CFG as preserved and 108 /// to query whether it has been preserved. 109 /// 110 /// The CFG of a function is defined as the set of basic blocks and the edges 111 /// between them. Changing the set of basic blocks in a function is enough to 112 /// mutate the CFG. Mutating the condition of a branch or argument of an 113 /// invoked function does not mutate the CFG, but changing the successor labels 114 /// of those instructions does. 115 class CFGAnalyses { 116 public: 117 static AnalysisSetKey *ID() { return &SetKey; } 118 119 private: 120 static AnalysisSetKey SetKey; 121 }; 122 123 /// A set of analyses that are preserved following a run of a transformation 124 /// pass. 125 /// 126 /// Transformation passes build and return these objects to communicate which 127 /// analyses are still valid after the transformation. For most passes this is 128 /// fairly simple: if they don't change anything all analyses are preserved, 129 /// otherwise only a short list of analyses that have been explicitly updated 130 /// are preserved. 131 /// 132 /// This class also lets transformation passes mark abstract *sets* of analyses 133 /// as preserved. A transformation that (say) does not alter the CFG can 134 /// indicate such by marking a particular AnalysisSetKey as preserved, and 135 /// then analyses can query whether that AnalysisSetKey is preserved. 136 /// 137 /// Finally, this class can represent an "abandoned" analysis, which is 138 /// not preserved even if it would be covered by some abstract set of analyses. 139 /// 140 /// Given a `PreservedAnalyses` object, an analysis will typically want to 141 /// figure out whether it is preserved. In the example below, MyAnalysisType is 142 /// preserved if it's not abandoned, and (a) it's explicitly marked as 143 /// preserved, (b), the set AllAnalysesOn<MyIRUnit> is preserved, or (c) both 144 /// AnalysisSetA and AnalysisSetB are preserved. 145 /// 146 /// ``` 147 /// auto PAC = PA.getChecker<MyAnalysisType>(); 148 /// if (PAC.preserved() || PAC.preservedSet<AllAnalysesOn<MyIRUnit>>() || 149 /// (PAC.preservedSet<AnalysisSetA>() && 150 /// PAC.preservedSet<AnalysisSetB>())) { 151 /// // The analysis has been successfully preserved ... 152 /// } 153 /// ``` 154 class PreservedAnalyses { 155 public: 156 /// Convenience factory function for the empty preserved set. 157 static PreservedAnalyses none() { return PreservedAnalyses(); } 158 159 /// Construct a special preserved set that preserves all passes. 160 static PreservedAnalyses all() { 161 PreservedAnalyses PA; 162 PA.PreservedIDs.insert(&AllAnalysesKey); 163 return PA; 164 } 165 166 /// Construct a preserved analyses object with a single preserved set. 167 template <typename AnalysisSetT> 168 static PreservedAnalyses allInSet() { 169 PreservedAnalyses PA; 170 PA.preserveSet<AnalysisSetT>(); 171 return PA; 172 } 173 174 /// Mark an analysis as preserved. 175 template <typename AnalysisT> void preserve() { preserve(AnalysisT::ID()); } 176 177 /// Given an analysis's ID, mark the analysis as preserved, adding it 178 /// to the set. 179 void preserve(AnalysisKey *ID) { 180 // Clear this ID from the explicit not-preserved set if present. 181 NotPreservedAnalysisIDs.erase(ID); 182 183 // If we're not already preserving all analyses (other than those in 184 // NotPreservedAnalysisIDs). 185 if (!areAllPreserved()) 186 PreservedIDs.insert(ID); 187 } 188 189 /// Mark an analysis set as preserved. 190 template <typename AnalysisSetT> void preserveSet() { 191 preserveSet(AnalysisSetT::ID()); 192 } 193 194 /// Mark an analysis set as preserved using its ID. 195 void preserveSet(AnalysisSetKey *ID) { 196 // If we're not already in the saturated 'all' state, add this set. 197 if (!areAllPreserved()) 198 PreservedIDs.insert(ID); 199 } 200 201 /// Mark an analysis as abandoned. 202 /// 203 /// An abandoned analysis is not preserved, even if it is nominally covered 204 /// by some other set or was previously explicitly marked as preserved. 205 /// 206 /// Note that you can only abandon a specific analysis, not a *set* of 207 /// analyses. 208 template <typename AnalysisT> void abandon() { abandon(AnalysisT::ID()); } 209 210 /// Mark an analysis as abandoned using its ID. 211 /// 212 /// An abandoned analysis is not preserved, even if it is nominally covered 213 /// by some other set or was previously explicitly marked as preserved. 214 /// 215 /// Note that you can only abandon a specific analysis, not a *set* of 216 /// analyses. 217 void abandon(AnalysisKey *ID) { 218 PreservedIDs.erase(ID); 219 NotPreservedAnalysisIDs.insert(ID); 220 } 221 222 /// Intersect this set with another in place. 223 /// 224 /// This is a mutating operation on this preserved set, removing all 225 /// preserved passes which are not also preserved in the argument. 226 void intersect(const PreservedAnalyses &Arg) { 227 if (Arg.areAllPreserved()) 228 return; 229 if (areAllPreserved()) { 230 *this = Arg; 231 return; 232 } 233 // The intersection requires the *union* of the explicitly not-preserved 234 // IDs and the *intersection* of the preserved IDs. 235 for (auto ID : Arg.NotPreservedAnalysisIDs) { 236 PreservedIDs.erase(ID); 237 NotPreservedAnalysisIDs.insert(ID); 238 } 239 for (auto ID : PreservedIDs) 240 if (!Arg.PreservedIDs.count(ID)) 241 PreservedIDs.erase(ID); 242 } 243 244 /// Intersect this set with a temporary other set in place. 245 /// 246 /// This is a mutating operation on this preserved set, removing all 247 /// preserved passes which are not also preserved in the argument. 248 void intersect(PreservedAnalyses &&Arg) { 249 if (Arg.areAllPreserved()) 250 return; 251 if (areAllPreserved()) { 252 *this = std::move(Arg); 253 return; 254 } 255 // The intersection requires the *union* of the explicitly not-preserved 256 // IDs and the *intersection* of the preserved IDs. 257 for (auto ID : Arg.NotPreservedAnalysisIDs) { 258 PreservedIDs.erase(ID); 259 NotPreservedAnalysisIDs.insert(ID); 260 } 261 for (auto ID : PreservedIDs) 262 if (!Arg.PreservedIDs.count(ID)) 263 PreservedIDs.erase(ID); 264 } 265 266 /// A checker object that makes it easy to query for whether an analysis or 267 /// some set covering it is preserved. 268 class PreservedAnalysisChecker { 269 friend class PreservedAnalyses; 270 271 const PreservedAnalyses &PA; 272 AnalysisKey *const ID; 273 const bool IsAbandoned; 274 275 /// A PreservedAnalysisChecker is tied to a particular Analysis because 276 /// `preserved()` and `preservedSet()` both return false if the Analysis 277 /// was abandoned. 278 PreservedAnalysisChecker(const PreservedAnalyses &PA, AnalysisKey *ID) 279 : PA(PA), ID(ID), IsAbandoned(PA.NotPreservedAnalysisIDs.count(ID)) {} 280 281 public: 282 /// Returns true if the checker's analysis was not abandoned and either 283 /// - the analysis is explicitly preserved or 284 /// - all analyses are preserved. 285 bool preserved() { 286 return !IsAbandoned && (PA.PreservedIDs.count(&AllAnalysesKey) || 287 PA.PreservedIDs.count(ID)); 288 } 289 290 /// Return true if the checker's analysis was not abandoned, i.e. it was not 291 /// explicitly invalidated. Even if the analysis is not explicitly 292 /// preserved, if the analysis is known stateless, then it is preserved. 293 bool preservedWhenStateless() { 294 return !IsAbandoned; 295 } 296 297 /// Returns true if the checker's analysis was not abandoned and either 298 /// - \p AnalysisSetT is explicitly preserved or 299 /// - all analyses are preserved. 300 template <typename AnalysisSetT> bool preservedSet() { 301 AnalysisSetKey *SetID = AnalysisSetT::ID(); 302 return !IsAbandoned && (PA.PreservedIDs.count(&AllAnalysesKey) || 303 PA.PreservedIDs.count(SetID)); 304 } 305 }; 306 307 /// Build a checker for this `PreservedAnalyses` and the specified analysis 308 /// type. 309 /// 310 /// You can use the returned object to query whether an analysis was 311 /// preserved. See the example in the comment on `PreservedAnalysis`. 312 template <typename AnalysisT> PreservedAnalysisChecker getChecker() const { 313 return PreservedAnalysisChecker(*this, AnalysisT::ID()); 314 } 315 316 /// Build a checker for this `PreservedAnalyses` and the specified analysis 317 /// ID. 318 /// 319 /// You can use the returned object to query whether an analysis was 320 /// preserved. See the example in the comment on `PreservedAnalysis`. 321 PreservedAnalysisChecker getChecker(AnalysisKey *ID) const { 322 return PreservedAnalysisChecker(*this, ID); 323 } 324 325 /// Test whether all analyses are preserved (and none are abandoned). 326 /// 327 /// This is used primarily to optimize for the common case of a transformation 328 /// which makes no changes to the IR. 329 bool areAllPreserved() const { 330 return NotPreservedAnalysisIDs.empty() && 331 PreservedIDs.count(&AllAnalysesKey); 332 } 333 334 /// Directly test whether a set of analyses is preserved. 335 /// 336 /// This is only true when no analyses have been explicitly abandoned. 337 template <typename AnalysisSetT> bool allAnalysesInSetPreserved() const { 338 return allAnalysesInSetPreserved(AnalysisSetT::ID()); 339 } 340 341 /// Directly test whether a set of analyses is preserved. 342 /// 343 /// This is only true when no analyses have been explicitly abandoned. 344 bool allAnalysesInSetPreserved(AnalysisSetKey *SetID) const { 345 return NotPreservedAnalysisIDs.empty() && 346 (PreservedIDs.count(&AllAnalysesKey) || PreservedIDs.count(SetID)); 347 } 348 349 private: 350 /// A special key used to indicate all analyses. 351 static AnalysisSetKey AllAnalysesKey; 352 353 /// The IDs of analyses and analysis sets that are preserved. 354 SmallPtrSet<void *, 2> PreservedIDs; 355 356 /// The IDs of explicitly not-preserved analyses. 357 /// 358 /// If an analysis in this set is covered by a set in `PreservedIDs`, we 359 /// consider it not-preserved. That is, `NotPreservedAnalysisIDs` always 360 /// "wins" over analysis sets in `PreservedIDs`. 361 /// 362 /// Also, a given ID should never occur both here and in `PreservedIDs`. 363 SmallPtrSet<AnalysisKey *, 2> NotPreservedAnalysisIDs; 364 }; 365 366 // Forward declare the analysis manager template. 367 template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager; 368 369 /// A CRTP mix-in to automatically provide informational APIs needed for 370 /// passes. 371 /// 372 /// This provides some boilerplate for types that are passes. 373 template <typename DerivedT> struct PassInfoMixin { 374 /// Gets the name of the pass we are mixed into. 375 static StringRef name() { 376 static_assert(std::is_base_of<PassInfoMixin, DerivedT>::value, 377 "Must pass the derived type as the template argument!"); 378 StringRef Name = getTypeName<DerivedT>(); 379 if (Name.startswith("llvm::")) 380 Name = Name.drop_front(strlen("llvm::")); 381 return Name; 382 } 383 }; 384 385 /// A CRTP mix-in that provides informational APIs needed for analysis passes. 386 /// 387 /// This provides some boilerplate for types that are analysis passes. It 388 /// automatically mixes in \c PassInfoMixin. 389 template <typename DerivedT> 390 struct AnalysisInfoMixin : PassInfoMixin<DerivedT> { 391 /// Returns an opaque, unique ID for this analysis type. 392 /// 393 /// This ID is a pointer type that is guaranteed to be 8-byte aligned and thus 394 /// suitable for use in sets, maps, and other data structures that use the low 395 /// bits of pointers. 396 /// 397 /// Note that this requires the derived type provide a static \c AnalysisKey 398 /// member called \c Key. 399 /// 400 /// FIXME: The only reason the mixin type itself can't declare the Key value 401 /// is that some compilers cannot correctly unique a templated static variable 402 /// so it has the same addresses in each instantiation. The only currently 403 /// known platform with this limitation is Windows DLL builds, specifically 404 /// building each part of LLVM as a DLL. If we ever remove that build 405 /// configuration, this mixin can provide the static key as well. 406 static AnalysisKey *ID() { 407 static_assert(std::is_base_of<AnalysisInfoMixin, DerivedT>::value, 408 "Must pass the derived type as the template argument!"); 409 return &DerivedT::Key; 410 } 411 }; 412 413 namespace detail { 414 415 /// Actual unpacker of extra arguments in getAnalysisResult, 416 /// passes only those tuple arguments that are mentioned in index_sequence. 417 template <typename PassT, typename IRUnitT, typename AnalysisManagerT, 418 typename... ArgTs, size_t... Ns> 419 typename PassT::Result 420 getAnalysisResultUnpackTuple(AnalysisManagerT &AM, IRUnitT &IR, 421 std::tuple<ArgTs...> Args, 422 std::index_sequence<Ns...>) { 423 (void)Args; 424 return AM.template getResult<PassT>(IR, std::get<Ns>(Args)...); 425 } 426 427 /// Helper for *partial* unpacking of extra arguments in getAnalysisResult. 428 /// 429 /// Arguments passed in tuple come from PassManager, so they might have extra 430 /// arguments after those AnalysisManager's ExtraArgTs ones that we need to 431 /// pass to getResult. 432 template <typename PassT, typename IRUnitT, typename... AnalysisArgTs, 433 typename... MainArgTs> 434 typename PassT::Result 435 getAnalysisResult(AnalysisManager<IRUnitT, AnalysisArgTs...> &AM, IRUnitT &IR, 436 std::tuple<MainArgTs...> Args) { 437 return (getAnalysisResultUnpackTuple< 438 PassT, IRUnitT>)(AM, IR, Args, 439 std::index_sequence_for<AnalysisArgTs...>{}); 440 } 441 442 } // namespace detail 443 444 // Forward declare the pass instrumentation analysis explicitly queried in 445 // generic PassManager code. 446 // FIXME: figure out a way to move PassInstrumentationAnalysis into its own 447 // header. 448 class PassInstrumentationAnalysis; 449 450 /// Manages a sequence of passes over a particular unit of IR. 451 /// 452 /// A pass manager contains a sequence of passes to run over a particular unit 453 /// of IR (e.g. Functions, Modules). It is itself a valid pass over that unit of 454 /// IR, and when run over some given IR will run each of its contained passes in 455 /// sequence. Pass managers are the primary and most basic building block of a 456 /// pass pipeline. 457 /// 458 /// When you run a pass manager, you provide an \c AnalysisManager<IRUnitT> 459 /// argument. The pass manager will propagate that analysis manager to each 460 /// pass it runs, and will call the analysis manager's invalidation routine with 461 /// the PreservedAnalyses of each pass it runs. 462 template <typename IRUnitT, 463 typename AnalysisManagerT = AnalysisManager<IRUnitT>, 464 typename... ExtraArgTs> 465 class PassManager : public PassInfoMixin< 466 PassManager<IRUnitT, AnalysisManagerT, ExtraArgTs...>> { 467 public: 468 /// Construct a pass manager. 469 /// 470 /// If \p DebugLogging is true, we'll log our progress to llvm::dbgs(). 471 explicit PassManager(bool DebugLogging = false) : DebugLogging(DebugLogging) {} 472 473 // FIXME: These are equivalent to the default move constructor/move 474 // assignment. However, using = default triggers linker errors due to the 475 // explicit instantiations below. Find away to use the default and remove the 476 // duplicated code here. 477 PassManager(PassManager &&Arg) 478 : Passes(std::move(Arg.Passes)), 479 DebugLogging(std::move(Arg.DebugLogging)) {} 480 481 PassManager &operator=(PassManager &&RHS) { 482 Passes = std::move(RHS.Passes); 483 DebugLogging = std::move(RHS.DebugLogging); 484 return *this; 485 } 486 487 /// Run all of the passes in this manager over the given unit of IR. 488 /// ExtraArgs are passed to each pass. 489 PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM, 490 ExtraArgTs... ExtraArgs) { 491 PreservedAnalyses PA = PreservedAnalyses::all(); 492 493 // Request PassInstrumentation from analysis manager, will use it to run 494 // instrumenting callbacks for the passes later. 495 // Here we use std::tuple wrapper over getResult which helps to extract 496 // AnalysisManager's arguments out of the whole ExtraArgs set. 497 PassInstrumentation PI = 498 detail::getAnalysisResult<PassInstrumentationAnalysis>( 499 AM, IR, std::tuple<ExtraArgTs...>(ExtraArgs...)); 500 501 if (DebugLogging) 502 dbgs() << "Starting " << getTypeName<IRUnitT>() << " pass manager run.\n"; 503 504 for (unsigned Idx = 0, Size = Passes.size(); Idx != Size; ++Idx) { 505 auto *P = Passes[Idx].get(); 506 507 // Check the PassInstrumentation's BeforePass callbacks before running the 508 // pass, skip its execution completely if asked to (callback returns 509 // false). 510 if (!PI.runBeforePass<IRUnitT>(*P, IR)) 511 continue; 512 513 if (DebugLogging) 514 dbgs() << "Running pass: " << P->name() << " on " << IR.getName() 515 << "\n"; 516 517 PreservedAnalyses PassPA; 518 { 519 TimeTraceScope TimeScope(P->name(), IR.getName()); 520 PassPA = P->run(IR, AM, ExtraArgs...); 521 } 522 523 // Call onto PassInstrumentation's AfterPass callbacks immediately after 524 // running the pass. 525 PI.runAfterPass<IRUnitT>(*P, IR); 526 527 // Update the analysis manager as each pass runs and potentially 528 // invalidates analyses. 529 AM.invalidate(IR, PassPA); 530 531 // Finally, intersect the preserved analyses to compute the aggregate 532 // preserved set for this pass manager. 533 PA.intersect(std::move(PassPA)); 534 535 // FIXME: Historically, the pass managers all called the LLVM context's 536 // yield function here. We don't have a generic way to acquire the 537 // context and it isn't yet clear what the right pattern is for yielding 538 // in the new pass manager so it is currently omitted. 539 //IR.getContext().yield(); 540 } 541 542 // Invalidation was handled after each pass in the above loop for the 543 // current unit of IR. Therefore, the remaining analysis results in the 544 // AnalysisManager are preserved. We mark this with a set so that we don't 545 // need to inspect each one individually. 546 PA.preserveSet<AllAnalysesOn<IRUnitT>>(); 547 548 if (DebugLogging) 549 dbgs() << "Finished " << getTypeName<IRUnitT>() << " pass manager run.\n"; 550 551 return PA; 552 } 553 554 template <typename PassT> void addPass(PassT Pass) { 555 using PassModelT = 556 detail::PassModel<IRUnitT, PassT, PreservedAnalyses, AnalysisManagerT, 557 ExtraArgTs...>; 558 559 Passes.emplace_back(new PassModelT(std::move(Pass))); 560 } 561 562 private: 563 using PassConceptT = 564 detail::PassConcept<IRUnitT, AnalysisManagerT, ExtraArgTs...>; 565 566 std::vector<std::unique_ptr<PassConceptT>> Passes; 567 568 /// Flag indicating whether we should do debug logging. 569 bool DebugLogging; 570 }; 571 572 extern template class PassManager<Module>; 573 574 /// Convenience typedef for a pass manager over modules. 575 using ModulePassManager = PassManager<Module>; 576 577 extern template class PassManager<Function>; 578 579 /// Convenience typedef for a pass manager over functions. 580 using FunctionPassManager = PassManager<Function>; 581 582 /// Pseudo-analysis pass that exposes the \c PassInstrumentation to pass 583 /// managers. Goes before AnalysisManager definition to provide its 584 /// internals (e.g PassInstrumentationAnalysis::ID) for use there if needed. 585 /// FIXME: figure out a way to move PassInstrumentationAnalysis into its own 586 /// header. 587 class PassInstrumentationAnalysis 588 : public AnalysisInfoMixin<PassInstrumentationAnalysis> { 589 friend AnalysisInfoMixin<PassInstrumentationAnalysis>; 590 static AnalysisKey Key; 591 592 PassInstrumentationCallbacks *Callbacks; 593 594 public: 595 /// PassInstrumentationCallbacks object is shared, owned by something else, 596 /// not this analysis. 597 PassInstrumentationAnalysis(PassInstrumentationCallbacks *Callbacks = nullptr) 598 : Callbacks(Callbacks) {} 599 600 using Result = PassInstrumentation; 601 602 template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs> 603 Result run(IRUnitT &, AnalysisManagerT &, ExtraArgTs &&...) { 604 return PassInstrumentation(Callbacks); 605 } 606 }; 607 608 /// A container for analyses that lazily runs them and caches their 609 /// results. 610 /// 611 /// This class can manage analyses for any IR unit where the address of the IR 612 /// unit sufficies as its identity. 613 template <typename IRUnitT, typename... ExtraArgTs> class AnalysisManager { 614 public: 615 class Invalidator; 616 617 private: 618 // Now that we've defined our invalidator, we can define the concept types. 619 using ResultConceptT = 620 detail::AnalysisResultConcept<IRUnitT, PreservedAnalyses, Invalidator>; 621 using PassConceptT = 622 detail::AnalysisPassConcept<IRUnitT, PreservedAnalyses, Invalidator, 623 ExtraArgTs...>; 624 625 /// List of analysis pass IDs and associated concept pointers. 626 /// 627 /// Requires iterators to be valid across appending new entries and arbitrary 628 /// erases. Provides the analysis ID to enable finding iterators to a given 629 /// entry in maps below, and provides the storage for the actual result 630 /// concept. 631 using AnalysisResultListT = 632 std::list<std::pair<AnalysisKey *, std::unique_ptr<ResultConceptT>>>; 633 634 /// Map type from IRUnitT pointer to our custom list type. 635 using AnalysisResultListMapT = DenseMap<IRUnitT *, AnalysisResultListT>; 636 637 /// Map type from a pair of analysis ID and IRUnitT pointer to an 638 /// iterator into a particular result list (which is where the actual analysis 639 /// result is stored). 640 using AnalysisResultMapT = 641 DenseMap<std::pair<AnalysisKey *, IRUnitT *>, 642 typename AnalysisResultListT::iterator>; 643 644 public: 645 /// API to communicate dependencies between analyses during invalidation. 646 /// 647 /// When an analysis result embeds handles to other analysis results, it 648 /// needs to be invalidated both when its own information isn't preserved and 649 /// when any of its embedded analysis results end up invalidated. We pass an 650 /// \c Invalidator object as an argument to \c invalidate() in order to let 651 /// the analysis results themselves define the dependency graph on the fly. 652 /// This lets us avoid building building an explicit representation of the 653 /// dependencies between analysis results. 654 class Invalidator { 655 public: 656 /// Trigger the invalidation of some other analysis pass if not already 657 /// handled and return whether it was in fact invalidated. 658 /// 659 /// This is expected to be called from within a given analysis result's \c 660 /// invalidate method to trigger a depth-first walk of all inter-analysis 661 /// dependencies. The same \p IR unit and \p PA passed to that result's \c 662 /// invalidate method should in turn be provided to this routine. 663 /// 664 /// The first time this is called for a given analysis pass, it will call 665 /// the corresponding result's \c invalidate method. Subsequent calls will 666 /// use a cache of the results of that initial call. It is an error to form 667 /// cyclic dependencies between analysis results. 668 /// 669 /// This returns true if the given analysis's result is invalid. Any 670 /// dependecies on it will become invalid as a result. 671 template <typename PassT> 672 bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA) { 673 using ResultModelT = 674 detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result, 675 PreservedAnalyses, Invalidator>; 676 677 return invalidateImpl<ResultModelT>(PassT::ID(), IR, PA); 678 } 679 680 /// A type-erased variant of the above invalidate method with the same core 681 /// API other than passing an analysis ID rather than an analysis type 682 /// parameter. 683 /// 684 /// This is sadly less efficient than the above routine, which leverages 685 /// the type parameter to avoid the type erasure overhead. 686 bool invalidate(AnalysisKey *ID, IRUnitT &IR, const PreservedAnalyses &PA) { 687 return invalidateImpl<>(ID, IR, PA); 688 } 689 690 private: 691 friend class AnalysisManager; 692 693 template <typename ResultT = ResultConceptT> 694 bool invalidateImpl(AnalysisKey *ID, IRUnitT &IR, 695 const PreservedAnalyses &PA) { 696 // If we've already visited this pass, return true if it was invalidated 697 // and false otherwise. 698 auto IMapI = IsResultInvalidated.find(ID); 699 if (IMapI != IsResultInvalidated.end()) 700 return IMapI->second; 701 702 // Otherwise look up the result object. 703 auto RI = Results.find({ID, &IR}); 704 assert(RI != Results.end() && 705 "Trying to invalidate a dependent result that isn't in the " 706 "manager's cache is always an error, likely due to a stale result " 707 "handle!"); 708 709 auto &Result = static_cast<ResultT &>(*RI->second->second); 710 711 // Insert into the map whether the result should be invalidated and return 712 // that. Note that we cannot reuse IMapI and must do a fresh insert here, 713 // as calling invalidate could (recursively) insert things into the map, 714 // making any iterator or reference invalid. 715 bool Inserted; 716 std::tie(IMapI, Inserted) = 717 IsResultInvalidated.insert({ID, Result.invalidate(IR, PA, *this)}); 718 (void)Inserted; 719 assert(Inserted && "Should not have already inserted this ID, likely " 720 "indicates a dependency cycle!"); 721 return IMapI->second; 722 } 723 724 Invalidator(SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated, 725 const AnalysisResultMapT &Results) 726 : IsResultInvalidated(IsResultInvalidated), Results(Results) {} 727 728 SmallDenseMap<AnalysisKey *, bool, 8> &IsResultInvalidated; 729 const AnalysisResultMapT &Results; 730 }; 731 732 /// Construct an empty analysis manager. 733 /// 734 /// If \p DebugLogging is true, we'll log our progress to llvm::dbgs(). 735 AnalysisManager(bool DebugLogging = false); 736 AnalysisManager(AnalysisManager &&); 737 AnalysisManager &operator=(AnalysisManager &&); 738 739 /// Returns true if the analysis manager has an empty results cache. 740 bool empty() const { 741 assert(AnalysisResults.empty() == AnalysisResultLists.empty() && 742 "The storage and index of analysis results disagree on how many " 743 "there are!"); 744 return AnalysisResults.empty(); 745 } 746 747 /// Clear any cached analysis results for a single unit of IR. 748 /// 749 /// This doesn't invalidate, but instead simply deletes, the relevant results. 750 /// It is useful when the IR is being removed and we want to clear out all the 751 /// memory pinned for it. 752 void clear(IRUnitT &IR, llvm::StringRef Name); 753 754 /// Clear all analysis results cached by this AnalysisManager. 755 /// 756 /// Like \c clear(IRUnitT&), this doesn't invalidate the results; it simply 757 /// deletes them. This lets you clean up the AnalysisManager when the set of 758 /// IR units itself has potentially changed, and thus we can't even look up a 759 /// a result and invalidate/clear it directly. 760 void clear() { 761 AnalysisResults.clear(); 762 AnalysisResultLists.clear(); 763 } 764 765 /// Get the result of an analysis pass for a given IR unit. 766 /// 767 /// Runs the analysis if a cached result is not available. 768 template <typename PassT> 769 typename PassT::Result &getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs) { 770 assert(AnalysisPasses.count(PassT::ID()) && 771 "This analysis pass was not registered prior to being queried"); 772 ResultConceptT &ResultConcept = 773 getResultImpl(PassT::ID(), IR, ExtraArgs...); 774 775 using ResultModelT = 776 detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result, 777 PreservedAnalyses, Invalidator>; 778 779 return static_cast<ResultModelT &>(ResultConcept).Result; 780 } 781 782 /// Get the cached result of an analysis pass for a given IR unit. 783 /// 784 /// This method never runs the analysis. 785 /// 786 /// \returns null if there is no cached result. 787 template <typename PassT> 788 typename PassT::Result *getCachedResult(IRUnitT &IR) const { 789 assert(AnalysisPasses.count(PassT::ID()) && 790 "This analysis pass was not registered prior to being queried"); 791 792 ResultConceptT *ResultConcept = getCachedResultImpl(PassT::ID(), IR); 793 if (!ResultConcept) 794 return nullptr; 795 796 using ResultModelT = 797 detail::AnalysisResultModel<IRUnitT, PassT, typename PassT::Result, 798 PreservedAnalyses, Invalidator>; 799 800 return &static_cast<ResultModelT *>(ResultConcept)->Result; 801 } 802 803 /// Verify that the given Result cannot be invalidated, assert otherwise. 804 template <typename PassT> 805 void verifyNotInvalidated(IRUnitT &IR, typename PassT::Result *Result) const { 806 PreservedAnalyses PA = PreservedAnalyses::none(); 807 SmallDenseMap<AnalysisKey *, bool, 8> IsResultInvalidated; 808 Invalidator Inv(IsResultInvalidated, AnalysisResults); 809 assert(!Result->invalidate(IR, PA, Inv) && 810 "Cached result cannot be invalidated"); 811 } 812 813 /// Register an analysis pass with the manager. 814 /// 815 /// The parameter is a callable whose result is an analysis pass. This allows 816 /// passing in a lambda to construct the analysis. 817 /// 818 /// The analysis type to register is the type returned by calling the \c 819 /// PassBuilder argument. If that type has already been registered, then the 820 /// argument will not be called and this function will return false. 821 /// Otherwise, we register the analysis returned by calling \c PassBuilder(), 822 /// and this function returns true. 823 /// 824 /// (Note: Although the return value of this function indicates whether or not 825 /// an analysis was previously registered, there intentionally isn't a way to 826 /// query this directly. Instead, you should just register all the analyses 827 /// you might want and let this class run them lazily. This idiom lets us 828 /// minimize the number of times we have to look up analyses in our 829 /// hashtable.) 830 template <typename PassBuilderT> 831 bool registerPass(PassBuilderT &&PassBuilder) { 832 using PassT = decltype(PassBuilder()); 833 using PassModelT = 834 detail::AnalysisPassModel<IRUnitT, PassT, PreservedAnalyses, 835 Invalidator, ExtraArgTs...>; 836 837 auto &PassPtr = AnalysisPasses[PassT::ID()]; 838 if (PassPtr) 839 // Already registered this pass type! 840 return false; 841 842 // Construct a new model around the instance returned by the builder. 843 PassPtr.reset(new PassModelT(PassBuilder())); 844 return true; 845 } 846 847 /// Invalidate a specific analysis pass for an IR module. 848 /// 849 /// Note that the analysis result can disregard invalidation, if it determines 850 /// it is in fact still valid. 851 template <typename PassT> void invalidate(IRUnitT &IR) { 852 assert(AnalysisPasses.count(PassT::ID()) && 853 "This analysis pass was not registered prior to being invalidated"); 854 invalidateImpl(PassT::ID(), IR); 855 } 856 857 /// Invalidate cached analyses for an IR unit. 858 /// 859 /// Walk through all of the analyses pertaining to this unit of IR and 860 /// invalidate them, unless they are preserved by the PreservedAnalyses set. 861 void invalidate(IRUnitT &IR, const PreservedAnalyses &PA); 862 863 private: 864 /// Look up a registered analysis pass. 865 PassConceptT &lookUpPass(AnalysisKey *ID) { 866 typename AnalysisPassMapT::iterator PI = AnalysisPasses.find(ID); 867 assert(PI != AnalysisPasses.end() && 868 "Analysis passes must be registered prior to being queried!"); 869 return *PI->second; 870 } 871 872 /// Look up a registered analysis pass. 873 const PassConceptT &lookUpPass(AnalysisKey *ID) const { 874 typename AnalysisPassMapT::const_iterator PI = AnalysisPasses.find(ID); 875 assert(PI != AnalysisPasses.end() && 876 "Analysis passes must be registered prior to being queried!"); 877 return *PI->second; 878 } 879 880 /// Get an analysis result, running the pass if necessary. 881 ResultConceptT &getResultImpl(AnalysisKey *ID, IRUnitT &IR, 882 ExtraArgTs... ExtraArgs); 883 884 /// Get a cached analysis result or return null. 885 ResultConceptT *getCachedResultImpl(AnalysisKey *ID, IRUnitT &IR) const { 886 typename AnalysisResultMapT::const_iterator RI = 887 AnalysisResults.find({ID, &IR}); 888 return RI == AnalysisResults.end() ? nullptr : &*RI->second->second; 889 } 890 891 /// Invalidate a function pass result. 892 void invalidateImpl(AnalysisKey *ID, IRUnitT &IR) { 893 typename AnalysisResultMapT::iterator RI = 894 AnalysisResults.find({ID, &IR}); 895 if (RI == AnalysisResults.end()) 896 return; 897 898 if (DebugLogging) 899 dbgs() << "Invalidating analysis: " << this->lookUpPass(ID).name() 900 << " on " << IR.getName() << "\n"; 901 AnalysisResultLists[&IR].erase(RI->second); 902 AnalysisResults.erase(RI); 903 } 904 905 /// Map type from module analysis pass ID to pass concept pointer. 906 using AnalysisPassMapT = 907 DenseMap<AnalysisKey *, std::unique_ptr<PassConceptT>>; 908 909 /// Collection of module analysis passes, indexed by ID. 910 AnalysisPassMapT AnalysisPasses; 911 912 /// Map from function to a list of function analysis results. 913 /// 914 /// Provides linear time removal of all analysis results for a function and 915 /// the ultimate storage for a particular cached analysis result. 916 AnalysisResultListMapT AnalysisResultLists; 917 918 /// Map from an analysis ID and function to a particular cached 919 /// analysis result. 920 AnalysisResultMapT AnalysisResults; 921 922 /// Indicates whether we log to \c llvm::dbgs(). 923 bool DebugLogging; 924 }; 925 926 extern template class AnalysisManager<Module>; 927 928 /// Convenience typedef for the Module analysis manager. 929 using ModuleAnalysisManager = AnalysisManager<Module>; 930 931 extern template class AnalysisManager<Function>; 932 933 /// Convenience typedef for the Function analysis manager. 934 using FunctionAnalysisManager = AnalysisManager<Function>; 935 936 /// An analysis over an "outer" IR unit that provides access to an 937 /// analysis manager over an "inner" IR unit. The inner unit must be contained 938 /// in the outer unit. 939 /// 940 /// For example, InnerAnalysisManagerProxy<FunctionAnalysisManager, Module> is 941 /// an analysis over Modules (the "outer" unit) that provides access to a 942 /// Function analysis manager. The FunctionAnalysisManager is the "inner" 943 /// manager being proxied, and Functions are the "inner" unit. The inner/outer 944 /// relationship is valid because each Function is contained in one Module. 945 /// 946 /// If you're (transitively) within a pass manager for an IR unit U that 947 /// contains IR unit V, you should never use an analysis manager over V, except 948 /// via one of these proxies. 949 /// 950 /// Note that the proxy's result is a move-only RAII object. The validity of 951 /// the analyses in the inner analysis manager is tied to its lifetime. 952 template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs> 953 class InnerAnalysisManagerProxy 954 : public AnalysisInfoMixin< 955 InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>> { 956 public: 957 class Result { 958 public: 959 explicit Result(AnalysisManagerT &InnerAM) : InnerAM(&InnerAM) {} 960 961 Result(Result &&Arg) : InnerAM(std::move(Arg.InnerAM)) { 962 // We have to null out the analysis manager in the moved-from state 963 // because we are taking ownership of the responsibilty to clear the 964 // analysis state. 965 Arg.InnerAM = nullptr; 966 } 967 968 ~Result() { 969 // InnerAM is cleared in a moved from state where there is nothing to do. 970 if (!InnerAM) 971 return; 972 973 // Clear out the analysis manager if we're being destroyed -- it means we 974 // didn't even see an invalidate call when we got invalidated. 975 InnerAM->clear(); 976 } 977 978 Result &operator=(Result &&RHS) { 979 InnerAM = RHS.InnerAM; 980 // We have to null out the analysis manager in the moved-from state 981 // because we are taking ownership of the responsibilty to clear the 982 // analysis state. 983 RHS.InnerAM = nullptr; 984 return *this; 985 } 986 987 /// Accessor for the analysis manager. 988 AnalysisManagerT &getManager() { return *InnerAM; } 989 990 /// Handler for invalidation of the outer IR unit, \c IRUnitT. 991 /// 992 /// If the proxy analysis itself is not preserved, we assume that the set of 993 /// inner IR objects contained in IRUnit may have changed. In this case, 994 /// we have to call \c clear() on the inner analysis manager, as it may now 995 /// have stale pointers to its inner IR objects. 996 /// 997 /// Regardless of whether the proxy analysis is marked as preserved, all of 998 /// the analyses in the inner analysis manager are potentially invalidated 999 /// based on the set of preserved analyses. 1000 bool invalidate( 1001 IRUnitT &IR, const PreservedAnalyses &PA, 1002 typename AnalysisManager<IRUnitT, ExtraArgTs...>::Invalidator &Inv); 1003 1004 private: 1005 AnalysisManagerT *InnerAM; 1006 }; 1007 1008 explicit InnerAnalysisManagerProxy(AnalysisManagerT &InnerAM) 1009 : InnerAM(&InnerAM) {} 1010 1011 /// Run the analysis pass and create our proxy result object. 1012 /// 1013 /// This doesn't do any interesting work; it is primarily used to insert our 1014 /// proxy result object into the outer analysis cache so that we can proxy 1015 /// invalidation to the inner analysis manager. 1016 Result run(IRUnitT &IR, AnalysisManager<IRUnitT, ExtraArgTs...> &AM, 1017 ExtraArgTs...) { 1018 return Result(*InnerAM); 1019 } 1020 1021 private: 1022 friend AnalysisInfoMixin< 1023 InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT>>; 1024 1025 static AnalysisKey Key; 1026 1027 AnalysisManagerT *InnerAM; 1028 }; 1029 1030 template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs> 1031 AnalysisKey 1032 InnerAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>::Key; 1033 1034 /// Provide the \c FunctionAnalysisManager to \c Module proxy. 1035 using FunctionAnalysisManagerModuleProxy = 1036 InnerAnalysisManagerProxy<FunctionAnalysisManager, Module>; 1037 1038 /// Specialization of the invalidate method for the \c 1039 /// FunctionAnalysisManagerModuleProxy's result. 1040 template <> 1041 bool FunctionAnalysisManagerModuleProxy::Result::invalidate( 1042 Module &M, const PreservedAnalyses &PA, 1043 ModuleAnalysisManager::Invalidator &Inv); 1044 1045 // Ensure the \c FunctionAnalysisManagerModuleProxy is provided as an extern 1046 // template. 1047 extern template class InnerAnalysisManagerProxy<FunctionAnalysisManager, 1048 Module>; 1049 1050 /// An analysis over an "inner" IR unit that provides access to an 1051 /// analysis manager over a "outer" IR unit. The inner unit must be contained 1052 /// in the outer unit. 1053 /// 1054 /// For example OuterAnalysisManagerProxy<ModuleAnalysisManager, Function> is an 1055 /// analysis over Functions (the "inner" unit) which provides access to a Module 1056 /// analysis manager. The ModuleAnalysisManager is the "outer" manager being 1057 /// proxied, and Modules are the "outer" IR unit. The inner/outer relationship 1058 /// is valid because each Function is contained in one Module. 1059 /// 1060 /// This proxy only exposes the const interface of the outer analysis manager, 1061 /// to indicate that you cannot cause an outer analysis to run from within an 1062 /// inner pass. Instead, you must rely on the \c getCachedResult API. 1063 /// 1064 /// This proxy doesn't manage invalidation in any way -- that is handled by the 1065 /// recursive return path of each layer of the pass manager. A consequence of 1066 /// this is the outer analyses may be stale. We invalidate the outer analyses 1067 /// only when we're done running passes over the inner IR units. 1068 template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs> 1069 class OuterAnalysisManagerProxy 1070 : public AnalysisInfoMixin< 1071 OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>> { 1072 public: 1073 /// Result proxy object for \c OuterAnalysisManagerProxy. 1074 class Result { 1075 public: 1076 explicit Result(const AnalysisManagerT &OuterAM) : OuterAM(&OuterAM) {} 1077 1078 /// Get a cached analysis. If the analysis can be invalidated, this will 1079 /// assert. 1080 template <typename PassT, typename IRUnitTParam> 1081 typename PassT::Result *getCachedResult(IRUnitTParam &IR) const { 1082 typename PassT::Result *Res = 1083 OuterAM->template getCachedResult<PassT>(IR); 1084 if (Res) 1085 OuterAM->template verifyNotInvalidated<PassT>(IR, Res); 1086 return Res; 1087 } 1088 1089 /// Method provided for unit testing, not intended for general use. 1090 template <typename PassT, typename IRUnitTParam> 1091 bool cachedResultExists(IRUnitTParam &IR) const { 1092 typename PassT::Result *Res = 1093 OuterAM->template getCachedResult<PassT>(IR); 1094 return Res != nullptr; 1095 } 1096 1097 /// When invalidation occurs, remove any registered invalidation events. 1098 bool invalidate( 1099 IRUnitT &IRUnit, const PreservedAnalyses &PA, 1100 typename AnalysisManager<IRUnitT, ExtraArgTs...>::Invalidator &Inv) { 1101 // Loop over the set of registered outer invalidation mappings and if any 1102 // of them map to an analysis that is now invalid, clear it out. 1103 SmallVector<AnalysisKey *, 4> DeadKeys; 1104 for (auto &KeyValuePair : OuterAnalysisInvalidationMap) { 1105 AnalysisKey *OuterID = KeyValuePair.first; 1106 auto &InnerIDs = KeyValuePair.second; 1107 InnerIDs.erase(llvm::remove_if(InnerIDs, [&](AnalysisKey *InnerID) { 1108 return Inv.invalidate(InnerID, IRUnit, PA); }), 1109 InnerIDs.end()); 1110 if (InnerIDs.empty()) 1111 DeadKeys.push_back(OuterID); 1112 } 1113 1114 for (auto OuterID : DeadKeys) 1115 OuterAnalysisInvalidationMap.erase(OuterID); 1116 1117 // The proxy itself remains valid regardless of anything else. 1118 return false; 1119 } 1120 1121 /// Register a deferred invalidation event for when the outer analysis 1122 /// manager processes its invalidations. 1123 template <typename OuterAnalysisT, typename InvalidatedAnalysisT> 1124 void registerOuterAnalysisInvalidation() { 1125 AnalysisKey *OuterID = OuterAnalysisT::ID(); 1126 AnalysisKey *InvalidatedID = InvalidatedAnalysisT::ID(); 1127 1128 auto &InvalidatedIDList = OuterAnalysisInvalidationMap[OuterID]; 1129 // Note, this is a linear scan. If we end up with large numbers of 1130 // analyses that all trigger invalidation on the same outer analysis, 1131 // this entire system should be changed to some other deterministic 1132 // data structure such as a `SetVector` of a pair of pointers. 1133 auto InvalidatedIt = std::find(InvalidatedIDList.begin(), 1134 InvalidatedIDList.end(), InvalidatedID); 1135 if (InvalidatedIt == InvalidatedIDList.end()) 1136 InvalidatedIDList.push_back(InvalidatedID); 1137 } 1138 1139 /// Access the map from outer analyses to deferred invalidation requiring 1140 /// analyses. 1141 const SmallDenseMap<AnalysisKey *, TinyPtrVector<AnalysisKey *>, 2> & 1142 getOuterInvalidations() const { 1143 return OuterAnalysisInvalidationMap; 1144 } 1145 1146 private: 1147 const AnalysisManagerT *OuterAM; 1148 1149 /// A map from an outer analysis ID to the set of this IR-unit's analyses 1150 /// which need to be invalidated. 1151 SmallDenseMap<AnalysisKey *, TinyPtrVector<AnalysisKey *>, 2> 1152 OuterAnalysisInvalidationMap; 1153 }; 1154 1155 OuterAnalysisManagerProxy(const AnalysisManagerT &OuterAM) 1156 : OuterAM(&OuterAM) {} 1157 1158 /// Run the analysis pass and create our proxy result object. 1159 /// Nothing to see here, it just forwards the \c OuterAM reference into the 1160 /// result. 1161 Result run(IRUnitT &, AnalysisManager<IRUnitT, ExtraArgTs...> &, 1162 ExtraArgTs...) { 1163 return Result(*OuterAM); 1164 } 1165 1166 private: 1167 friend AnalysisInfoMixin< 1168 OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>>; 1169 1170 static AnalysisKey Key; 1171 1172 const AnalysisManagerT *OuterAM; 1173 }; 1174 1175 template <typename AnalysisManagerT, typename IRUnitT, typename... ExtraArgTs> 1176 AnalysisKey 1177 OuterAnalysisManagerProxy<AnalysisManagerT, IRUnitT, ExtraArgTs...>::Key; 1178 1179 extern template class OuterAnalysisManagerProxy<ModuleAnalysisManager, 1180 Function>; 1181 /// Provide the \c ModuleAnalysisManager to \c Function proxy. 1182 using ModuleAnalysisManagerFunctionProxy = 1183 OuterAnalysisManagerProxy<ModuleAnalysisManager, Function>; 1184 1185 /// Trivial adaptor that maps from a module to its functions. 1186 /// 1187 /// Designed to allow composition of a FunctionPass(Manager) and 1188 /// a ModulePassManager, by running the FunctionPass(Manager) over every 1189 /// function in the module. 1190 /// 1191 /// Function passes run within this adaptor can rely on having exclusive access 1192 /// to the function they are run over. They should not read or modify any other 1193 /// functions! Other threads or systems may be manipulating other functions in 1194 /// the module, and so their state should never be relied on. 1195 /// FIXME: Make the above true for all of LLVM's actual passes, some still 1196 /// violate this principle. 1197 /// 1198 /// Function passes can also read the module containing the function, but they 1199 /// should not modify that module outside of the use lists of various globals. 1200 /// For example, a function pass is not permitted to add functions to the 1201 /// module. 1202 /// FIXME: Make the above true for all of LLVM's actual passes, some still 1203 /// violate this principle. 1204 /// 1205 /// Note that although function passes can access module analyses, module 1206 /// analyses are not invalidated while the function passes are running, so they 1207 /// may be stale. Function analyses will not be stale. 1208 template <typename FunctionPassT> 1209 class ModuleToFunctionPassAdaptor 1210 : public PassInfoMixin<ModuleToFunctionPassAdaptor<FunctionPassT>> { 1211 public: 1212 explicit ModuleToFunctionPassAdaptor(FunctionPassT Pass) 1213 : Pass(std::move(Pass)) {} 1214 1215 /// Runs the function pass across every function in the module. 1216 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM) { 1217 FunctionAnalysisManager &FAM = 1218 AM.getResult<FunctionAnalysisManagerModuleProxy>(M).getManager(); 1219 1220 // Request PassInstrumentation from analysis manager, will use it to run 1221 // instrumenting callbacks for the passes later. 1222 PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M); 1223 1224 PreservedAnalyses PA = PreservedAnalyses::all(); 1225 for (Function &F : M) { 1226 if (F.isDeclaration()) 1227 continue; 1228 1229 // Check the PassInstrumentation's BeforePass callbacks before running the 1230 // pass, skip its execution completely if asked to (callback returns 1231 // false). 1232 if (!PI.runBeforePass<Function>(Pass, F)) 1233 continue; 1234 1235 PreservedAnalyses PassPA; 1236 { 1237 TimeTraceScope TimeScope(Pass.name(), F.getName()); 1238 PassPA = Pass.run(F, FAM); 1239 } 1240 1241 PI.runAfterPass(Pass, F); 1242 1243 // We know that the function pass couldn't have invalidated any other 1244 // function's analyses (that's the contract of a function pass), so 1245 // directly handle the function analysis manager's invalidation here. 1246 FAM.invalidate(F, PassPA); 1247 1248 // Then intersect the preserved set so that invalidation of module 1249 // analyses will eventually occur when the module pass completes. 1250 PA.intersect(std::move(PassPA)); 1251 } 1252 1253 // The FunctionAnalysisManagerModuleProxy is preserved because (we assume) 1254 // the function passes we ran didn't add or remove any functions. 1255 // 1256 // We also preserve all analyses on Functions, because we did all the 1257 // invalidation we needed to do above. 1258 PA.preserveSet<AllAnalysesOn<Function>>(); 1259 PA.preserve<FunctionAnalysisManagerModuleProxy>(); 1260 return PA; 1261 } 1262 1263 private: 1264 FunctionPassT Pass; 1265 }; 1266 1267 /// A function to deduce a function pass type and wrap it in the 1268 /// templated adaptor. 1269 template <typename FunctionPassT> 1270 ModuleToFunctionPassAdaptor<FunctionPassT> 1271 createModuleToFunctionPassAdaptor(FunctionPassT Pass) { 1272 return ModuleToFunctionPassAdaptor<FunctionPassT>(std::move(Pass)); 1273 } 1274 1275 /// A utility pass template to force an analysis result to be available. 1276 /// 1277 /// If there are extra arguments at the pass's run level there may also be 1278 /// extra arguments to the analysis manager's \c getResult routine. We can't 1279 /// guess how to effectively map the arguments from one to the other, and so 1280 /// this specialization just ignores them. 1281 /// 1282 /// Specific patterns of run-method extra arguments and analysis manager extra 1283 /// arguments will have to be defined as appropriate specializations. 1284 template <typename AnalysisT, typename IRUnitT, 1285 typename AnalysisManagerT = AnalysisManager<IRUnitT>, 1286 typename... ExtraArgTs> 1287 struct RequireAnalysisPass 1288 : PassInfoMixin<RequireAnalysisPass<AnalysisT, IRUnitT, AnalysisManagerT, 1289 ExtraArgTs...>> { 1290 /// Run this pass over some unit of IR. 1291 /// 1292 /// This pass can be run over any unit of IR and use any analysis manager 1293 /// provided they satisfy the basic API requirements. When this pass is 1294 /// created, these methods can be instantiated to satisfy whatever the 1295 /// context requires. 1296 PreservedAnalyses run(IRUnitT &Arg, AnalysisManagerT &AM, 1297 ExtraArgTs &&... Args) { 1298 (void)AM.template getResult<AnalysisT>(Arg, 1299 std::forward<ExtraArgTs>(Args)...); 1300 1301 return PreservedAnalyses::all(); 1302 } 1303 }; 1304 1305 /// A no-op pass template which simply forces a specific analysis result 1306 /// to be invalidated. 1307 template <typename AnalysisT> 1308 struct InvalidateAnalysisPass 1309 : PassInfoMixin<InvalidateAnalysisPass<AnalysisT>> { 1310 /// Run this pass over some unit of IR. 1311 /// 1312 /// This pass can be run over any unit of IR and use any analysis manager, 1313 /// provided they satisfy the basic API requirements. When this pass is 1314 /// created, these methods can be instantiated to satisfy whatever the 1315 /// context requires. 1316 template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs> 1317 PreservedAnalyses run(IRUnitT &Arg, AnalysisManagerT &AM, ExtraArgTs &&...) { 1318 auto PA = PreservedAnalyses::all(); 1319 PA.abandon<AnalysisT>(); 1320 return PA; 1321 } 1322 }; 1323 1324 /// A utility pass that does nothing, but preserves no analyses. 1325 /// 1326 /// Because this preserves no analyses, any analysis passes queried after this 1327 /// pass runs will recompute fresh results. 1328 struct InvalidateAllAnalysesPass : PassInfoMixin<InvalidateAllAnalysesPass> { 1329 /// Run this pass over some unit of IR. 1330 template <typename IRUnitT, typename AnalysisManagerT, typename... ExtraArgTs> 1331 PreservedAnalyses run(IRUnitT &, AnalysisManagerT &, ExtraArgTs &&...) { 1332 return PreservedAnalyses::none(); 1333 } 1334 }; 1335 1336 /// A utility pass template that simply runs another pass multiple times. 1337 /// 1338 /// This can be useful when debugging or testing passes. It also serves as an 1339 /// example of how to extend the pass manager in ways beyond composition. 1340 template <typename PassT> 1341 class RepeatedPass : public PassInfoMixin<RepeatedPass<PassT>> { 1342 public: 1343 RepeatedPass(int Count, PassT P) : Count(Count), P(std::move(P)) {} 1344 1345 template <typename IRUnitT, typename AnalysisManagerT, typename... Ts> 1346 PreservedAnalyses run(IRUnitT &IR, AnalysisManagerT &AM, Ts &&... Args) { 1347 1348 // Request PassInstrumentation from analysis manager, will use it to run 1349 // instrumenting callbacks for the passes later. 1350 // Here we use std::tuple wrapper over getResult which helps to extract 1351 // AnalysisManager's arguments out of the whole Args set. 1352 PassInstrumentation PI = 1353 detail::getAnalysisResult<PassInstrumentationAnalysis>( 1354 AM, IR, std::tuple<Ts...>(Args...)); 1355 1356 auto PA = PreservedAnalyses::all(); 1357 for (int i = 0; i < Count; ++i) { 1358 // Check the PassInstrumentation's BeforePass callbacks before running the 1359 // pass, skip its execution completely if asked to (callback returns 1360 // false). 1361 if (!PI.runBeforePass<IRUnitT>(P, IR)) 1362 continue; 1363 PA.intersect(P.run(IR, AM, std::forward<Ts>(Args)...)); 1364 PI.runAfterPass(P, IR); 1365 } 1366 return PA; 1367 } 1368 1369 private: 1370 int Count; 1371 PassT P; 1372 }; 1373 1374 template <typename PassT> 1375 RepeatedPass<PassT> createRepeatedPass(int Count, PassT P) { 1376 return RepeatedPass<PassT>(Count, std::move(P)); 1377 } 1378 1379 } // end namespace llvm 1380 1381 #endif // LLVM_IR_PASSMANAGER_H 1382