1 //===- CGSCCPassManager.h - Call graph pass management ----------*- 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 provides classes for managing passes over SCCs of the call 11 /// graph. These passes form an important component of LLVM's interprocedural 12 /// optimizations. Because they operate on the SCCs of the call graph, and they 13 /// traverse the graph in post-order, they can effectively do pair-wise 14 /// interprocedural optimizations for all call edges in the program while 15 /// incrementally refining it and improving the context of these pair-wise 16 /// optimizations. At each call site edge, the callee has already been 17 /// optimized as much as is possible. This in turn allows very accurate 18 /// analysis of it for IPO. 19 /// 20 /// A secondary more general goal is to be able to isolate optimization on 21 /// unrelated parts of the IR module. This is useful to ensure our 22 /// optimizations are principled and don't miss oportunities where refinement 23 /// of one part of the module influences transformations in another part of the 24 /// module. But this is also useful if we want to parallelize the optimizations 25 /// across common large module graph shapes which tend to be very wide and have 26 /// large regions of unrelated cliques. 27 /// 28 /// To satisfy these goals, we use the LazyCallGraph which provides two graphs 29 /// nested inside each other (and built lazily from the bottom-up): the call 30 /// graph proper, and a reference graph. The reference graph is super set of 31 /// the call graph and is a conservative approximation of what could through 32 /// scalar or CGSCC transforms *become* the call graph. Using this allows us to 33 /// ensure we optimize functions prior to them being introduced into the call 34 /// graph by devirtualization or other technique, and thus ensures that 35 /// subsequent pair-wise interprocedural optimizations observe the optimized 36 /// form of these functions. The (potentially transitive) reference 37 /// reachability used by the reference graph is a conservative approximation 38 /// that still allows us to have independent regions of the graph. 39 /// 40 /// FIXME: There is one major drawback of the reference graph: in its naive 41 /// form it is quadratic because it contains a distinct edge for each 42 /// (potentially indirect) reference, even if are all through some common 43 /// global table of function pointers. This can be fixed in a number of ways 44 /// that essentially preserve enough of the normalization. While it isn't 45 /// expected to completely preclude the usability of this, it will need to be 46 /// addressed. 47 /// 48 /// 49 /// All of these issues are made substantially more complex in the face of 50 /// mutations to the call graph while optimization passes are being run. When 51 /// mutations to the call graph occur we want to achieve two different things: 52 /// 53 /// - We need to update the call graph in-flight and invalidate analyses 54 /// cached on entities in the graph. Because of the cache-based analysis 55 /// design of the pass manager, it is essential to have stable identities for 56 /// the elements of the IR that passes traverse, and to invalidate any 57 /// analyses cached on these elements as the mutations take place. 58 /// 59 /// - We want to preserve the incremental and post-order traversal of the 60 /// graph even as it is refined and mutated. This means we want optimization 61 /// to observe the most refined form of the call graph and to do so in 62 /// post-order. 63 /// 64 /// To address this, the CGSCC manager uses both worklists that can be expanded 65 /// by passes which transform the IR, and provides invalidation tests to skip 66 /// entries that become dead. This extra data is provided to every SCC pass so 67 /// that it can carefully update the manager's traversal as the call graph 68 /// mutates. 69 /// 70 /// We also provide support for running function passes within the CGSCC walk, 71 /// and there we provide automatic update of the call graph including of the 72 /// pass manager to reflect call graph changes that fall out naturally as part 73 /// of scalar transformations. 74 /// 75 /// The patterns used to ensure the goals of post-order visitation of the fully 76 /// refined graph: 77 /// 78 /// 1) Sink toward the "bottom" as the graph is refined. This means that any 79 /// iteration continues in some valid post-order sequence after the mutation 80 /// has altered the structure. 81 /// 82 /// 2) Enqueue in post-order, including the current entity. If the current 83 /// entity's shape changes, it and everything after it in post-order needs 84 /// to be visited to observe that shape. 85 /// 86 //===----------------------------------------------------------------------===// 87 88 #ifndef LLVM_ANALYSIS_CGSCCPASSMANAGER_H 89 #define LLVM_ANALYSIS_CGSCCPASSMANAGER_H 90 91 #include "llvm/ADT/DenseMap.h" 92 #include "llvm/ADT/DenseSet.h" 93 #include "llvm/ADT/MapVector.h" 94 #include "llvm/ADT/PriorityWorklist.h" 95 #include "llvm/ADT/STLExtras.h" 96 #include "llvm/ADT/SmallPtrSet.h" 97 #include "llvm/ADT/SmallVector.h" 98 #include "llvm/Analysis/LazyCallGraph.h" 99 #include "llvm/IR/Function.h" 100 #include "llvm/IR/InstIterator.h" 101 #include "llvm/IR/PassManager.h" 102 #include "llvm/IR/ValueHandle.h" 103 #include "llvm/Support/Debug.h" 104 #include "llvm/Support/raw_ostream.h" 105 #include <algorithm> 106 #include <cassert> 107 #include <utility> 108 109 namespace llvm { 110 111 struct CGSCCUpdateResult; 112 class Module; 113 114 // Allow debug logging in this inline function. 115 #define DEBUG_TYPE "cgscc" 116 117 /// Extern template declaration for the analysis set for this IR unit. 118 extern template class AllAnalysesOn<LazyCallGraph::SCC>; 119 120 extern template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>; 121 122 /// The CGSCC analysis manager. 123 /// 124 /// See the documentation for the AnalysisManager template for detail 125 /// documentation. This type serves as a convenient way to refer to this 126 /// construct in the adaptors and proxies used to integrate this into the larger 127 /// pass manager infrastructure. 128 using CGSCCAnalysisManager = 129 AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>; 130 131 // Explicit specialization and instantiation declarations for the pass manager. 132 // See the comments on the definition of the specialization for details on how 133 // it differs from the primary template. 134 template <> 135 PreservedAnalyses 136 PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &, 137 CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC, 138 CGSCCAnalysisManager &AM, 139 LazyCallGraph &G, CGSCCUpdateResult &UR); 140 extern template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, 141 LazyCallGraph &, CGSCCUpdateResult &>; 142 143 /// The CGSCC pass manager. 144 /// 145 /// See the documentation for the PassManager template for details. It runs 146 /// a sequence of SCC passes over each SCC that the manager is run over. This 147 /// type serves as a convenient way to refer to this construct. 148 using CGSCCPassManager = 149 PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &, 150 CGSCCUpdateResult &>; 151 152 /// An explicit specialization of the require analysis template pass. 153 template <typename AnalysisT> 154 struct RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC, CGSCCAnalysisManager, 155 LazyCallGraph &, CGSCCUpdateResult &> 156 : PassInfoMixin<RequireAnalysisPass<AnalysisT, LazyCallGraph::SCC, 157 CGSCCAnalysisManager, LazyCallGraph &, 158 CGSCCUpdateResult &>> { 159 PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, 160 LazyCallGraph &CG, CGSCCUpdateResult &) { 161 (void)AM.template getResult<AnalysisT>(C, CG); 162 return PreservedAnalyses::all(); 163 } 164 void printPipeline(raw_ostream &OS, 165 function_ref<StringRef(StringRef)> MapClassName2PassName) { 166 auto ClassName = AnalysisT::name(); 167 auto PassName = MapClassName2PassName(ClassName); 168 OS << "require<" << PassName << ">"; 169 } 170 }; 171 172 /// A proxy from a \c CGSCCAnalysisManager to a \c Module. 173 using CGSCCAnalysisManagerModuleProxy = 174 InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>; 175 176 /// We need a specialized result for the \c CGSCCAnalysisManagerModuleProxy so 177 /// it can have access to the call graph in order to walk all the SCCs when 178 /// invalidating things. 179 template <> class CGSCCAnalysisManagerModuleProxy::Result { 180 public: 181 explicit Result(CGSCCAnalysisManager &InnerAM, LazyCallGraph &G) 182 : InnerAM(&InnerAM), G(&G) {} 183 184 /// Accessor for the analysis manager. 185 CGSCCAnalysisManager &getManager() { return *InnerAM; } 186 187 /// Handler for invalidation of the Module. 188 /// 189 /// If the proxy analysis itself is preserved, then we assume that the set of 190 /// SCCs in the Module hasn't changed. Thus any pointers to SCCs in the 191 /// CGSCCAnalysisManager are still valid, and we don't need to call \c clear 192 /// on the CGSCCAnalysisManager. 193 /// 194 /// Regardless of whether this analysis is marked as preserved, all of the 195 /// analyses in the \c CGSCCAnalysisManager are potentially invalidated based 196 /// on the set of preserved analyses. 197 bool invalidate(Module &M, const PreservedAnalyses &PA, 198 ModuleAnalysisManager::Invalidator &Inv); 199 200 private: 201 CGSCCAnalysisManager *InnerAM; 202 LazyCallGraph *G; 203 }; 204 205 /// Provide a specialized run method for the \c CGSCCAnalysisManagerModuleProxy 206 /// so it can pass the lazy call graph to the result. 207 template <> 208 CGSCCAnalysisManagerModuleProxy::Result 209 CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM); 210 211 // Ensure the \c CGSCCAnalysisManagerModuleProxy is provided as an extern 212 // template. 213 extern template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>; 214 215 extern template class OuterAnalysisManagerProxy< 216 ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>; 217 218 /// A proxy from a \c ModuleAnalysisManager to an \c SCC. 219 using ModuleAnalysisManagerCGSCCProxy = 220 OuterAnalysisManagerProxy<ModuleAnalysisManager, LazyCallGraph::SCC, 221 LazyCallGraph &>; 222 223 /// Support structure for SCC passes to communicate updates the call graph back 224 /// to the CGSCC pass manager infrastructure. 225 /// 226 /// The CGSCC pass manager runs SCC passes which are allowed to update the call 227 /// graph and SCC structures. This means the structure the pass manager works 228 /// on is mutating underneath it. In order to support that, there needs to be 229 /// careful communication about the precise nature and ramifications of these 230 /// updates to the pass management infrastructure. 231 /// 232 /// All SCC passes will have to accept a reference to the management layer's 233 /// update result struct and use it to reflect the results of any CG updates 234 /// performed. 235 /// 236 /// Passes which do not change the call graph structure in any way can just 237 /// ignore this argument to their run method. 238 struct CGSCCUpdateResult { 239 /// Worklist of the RefSCCs queued for processing. 240 /// 241 /// When a pass refines the graph and creates new RefSCCs or causes them to 242 /// have a different shape or set of component SCCs it should add the RefSCCs 243 /// to this worklist so that we visit them in the refined form. 244 /// 245 /// This worklist is in reverse post-order, as we pop off the back in order 246 /// to observe RefSCCs in post-order. When adding RefSCCs, clients should add 247 /// them in reverse post-order. 248 SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> &RCWorklist; 249 250 /// Worklist of the SCCs queued for processing. 251 /// 252 /// When a pass refines the graph and creates new SCCs or causes them to have 253 /// a different shape or set of component functions it should add the SCCs to 254 /// this worklist so that we visit them in the refined form. 255 /// 256 /// Note that if the SCCs are part of a RefSCC that is added to the \c 257 /// RCWorklist, they don't need to be added here as visiting the RefSCC will 258 /// be sufficient to re-visit the SCCs within it. 259 /// 260 /// This worklist is in reverse post-order, as we pop off the back in order 261 /// to observe SCCs in post-order. When adding SCCs, clients should add them 262 /// in reverse post-order. 263 SmallPriorityWorklist<LazyCallGraph::SCC *, 1> &CWorklist; 264 265 /// The set of invalidated RefSCCs which should be skipped if they are found 266 /// in \c RCWorklist. 267 /// 268 /// This is used to quickly prune out RefSCCs when they get deleted and 269 /// happen to already be on the worklist. We use this primarily to avoid 270 /// scanning the list and removing entries from it. 271 SmallPtrSetImpl<LazyCallGraph::RefSCC *> &InvalidatedRefSCCs; 272 273 /// The set of invalidated SCCs which should be skipped if they are found 274 /// in \c CWorklist. 275 /// 276 /// This is used to quickly prune out SCCs when they get deleted and happen 277 /// to already be on the worklist. We use this primarily to avoid scanning 278 /// the list and removing entries from it. 279 SmallPtrSetImpl<LazyCallGraph::SCC *> &InvalidatedSCCs; 280 281 /// If non-null, the updated current \c RefSCC being processed. 282 /// 283 /// This is set when a graph refinement takes place and the "current" point 284 /// in the graph moves "down" or earlier in the post-order walk. This will 285 /// often cause the "current" RefSCC to be a newly created RefSCC object and 286 /// the old one to be added to the above worklist. When that happens, this 287 /// pointer is non-null and can be used to continue processing the "top" of 288 /// the post-order walk. 289 LazyCallGraph::RefSCC *UpdatedRC; 290 291 /// If non-null, the updated current \c SCC being processed. 292 /// 293 /// This is set when a graph refinement takes place and the "current" point 294 /// in the graph moves "down" or earlier in the post-order walk. This will 295 /// often cause the "current" SCC to be a newly created SCC object and the 296 /// old one to be added to the above worklist. When that happens, this 297 /// pointer is non-null and can be used to continue processing the "top" of 298 /// the post-order walk. 299 LazyCallGraph::SCC *UpdatedC; 300 301 /// Preserved analyses across SCCs. 302 /// 303 /// We specifically want to allow CGSCC passes to mutate ancestor IR 304 /// (changing both the CG structure and the function IR itself). However, 305 /// this means we need to take special care to correctly mark what analyses 306 /// are preserved *across* SCCs. We have to track this out-of-band here 307 /// because within the main `PassManager` infrastructure we need to mark 308 /// everything within an SCC as preserved in order to avoid repeatedly 309 /// invalidating the same analyses as we unnest pass managers and adaptors. 310 /// So we track the cross-SCC version of the preserved analyses here from any 311 /// code that does direct invalidation of SCC analyses, and then use it 312 /// whenever we move forward in the post-order walk of SCCs before running 313 /// passes over the new SCC. 314 PreservedAnalyses CrossSCCPA; 315 316 /// A hacky area where the inliner can retain history about inlining 317 /// decisions that mutated the call graph's SCC structure in order to avoid 318 /// infinite inlining. See the comments in the inliner's CG update logic. 319 /// 320 /// FIXME: Keeping this here seems like a big layering issue, we should look 321 /// for a better technique. 322 SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4> 323 &InlinedInternalEdges; 324 325 /// Weak VHs to keep track of indirect calls for the purposes of detecting 326 /// devirtualization. 327 /// 328 /// This is a map to avoid having duplicate entries. If a Value is 329 /// deallocated, its corresponding WeakTrackingVH will be nulled out. When 330 /// checking if a Value is in the map or not, also check if the corresponding 331 /// WeakTrackingVH is null to avoid issues with a new Value sharing the same 332 /// address as a deallocated one. 333 SmallMapVector<Value *, WeakTrackingVH, 16> IndirectVHs; 334 }; 335 336 /// The core module pass which does a post-order walk of the SCCs and 337 /// runs a CGSCC pass over each one. 338 /// 339 /// Designed to allow composition of a CGSCCPass(Manager) and 340 /// a ModulePassManager. Note that this pass must be run with a module analysis 341 /// manager as it uses the LazyCallGraph analysis. It will also run the 342 /// \c CGSCCAnalysisManagerModuleProxy analysis prior to running the CGSCC 343 /// pass over the module to enable a \c FunctionAnalysisManager to be used 344 /// within this run safely. 345 class ModuleToPostOrderCGSCCPassAdaptor 346 : public PassInfoMixin<ModuleToPostOrderCGSCCPassAdaptor> { 347 public: 348 using PassConceptT = 349 detail::PassConcept<LazyCallGraph::SCC, CGSCCAnalysisManager, 350 LazyCallGraph &, CGSCCUpdateResult &>; 351 352 explicit ModuleToPostOrderCGSCCPassAdaptor(std::unique_ptr<PassConceptT> Pass) 353 : Pass(std::move(Pass)) {} 354 355 ModuleToPostOrderCGSCCPassAdaptor(ModuleToPostOrderCGSCCPassAdaptor &&Arg) 356 : Pass(std::move(Arg.Pass)) {} 357 358 friend void swap(ModuleToPostOrderCGSCCPassAdaptor &LHS, 359 ModuleToPostOrderCGSCCPassAdaptor &RHS) { 360 std::swap(LHS.Pass, RHS.Pass); 361 } 362 363 ModuleToPostOrderCGSCCPassAdaptor & 364 operator=(ModuleToPostOrderCGSCCPassAdaptor RHS) { 365 swap(*this, RHS); 366 return *this; 367 } 368 369 /// Runs the CGSCC pass across every SCC in the module. 370 PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM); 371 372 void printPipeline(raw_ostream &OS, 373 function_ref<StringRef(StringRef)> MapClassName2PassName) { 374 OS << "cgscc("; 375 Pass->printPipeline(OS, MapClassName2PassName); 376 OS << ")"; 377 } 378 379 static bool isRequired() { return true; } 380 381 private: 382 std::unique_ptr<PassConceptT> Pass; 383 }; 384 385 /// A function to deduce a function pass type and wrap it in the 386 /// templated adaptor. 387 template <typename CGSCCPassT> 388 ModuleToPostOrderCGSCCPassAdaptor 389 createModuleToPostOrderCGSCCPassAdaptor(CGSCCPassT &&Pass) { 390 using PassModelT = detail::PassModel<LazyCallGraph::SCC, CGSCCPassT, 391 PreservedAnalyses, CGSCCAnalysisManager, 392 LazyCallGraph &, CGSCCUpdateResult &>; 393 // Do not use make_unique, it causes too many template instantiations, 394 // causing terrible compile times. 395 return ModuleToPostOrderCGSCCPassAdaptor( 396 std::unique_ptr<ModuleToPostOrderCGSCCPassAdaptor::PassConceptT>( 397 new PassModelT(std::forward<CGSCCPassT>(Pass)))); 398 } 399 400 /// A proxy from a \c FunctionAnalysisManager to an \c SCC. 401 /// 402 /// When a module pass runs and triggers invalidation, both the CGSCC and 403 /// Function analysis manager proxies on the module get an invalidation event. 404 /// We don't want to fully duplicate responsibility for most of the 405 /// invalidation logic. Instead, this layer is only responsible for SCC-local 406 /// invalidation events. We work with the module's FunctionAnalysisManager to 407 /// invalidate function analyses. 408 class FunctionAnalysisManagerCGSCCProxy 409 : public AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy> { 410 public: 411 class Result { 412 public: 413 explicit Result() : FAM(nullptr) {} 414 explicit Result(FunctionAnalysisManager &FAM) : FAM(&FAM) {} 415 416 void updateFAM(FunctionAnalysisManager &FAM) { this->FAM = &FAM; } 417 /// Accessor for the analysis manager. 418 FunctionAnalysisManager &getManager() { 419 assert(FAM); 420 return *FAM; 421 } 422 423 bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA, 424 CGSCCAnalysisManager::Invalidator &Inv); 425 426 private: 427 FunctionAnalysisManager *FAM; 428 }; 429 430 /// Computes the \c FunctionAnalysisManager and stores it in the result proxy. 431 Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &); 432 433 private: 434 friend AnalysisInfoMixin<FunctionAnalysisManagerCGSCCProxy>; 435 436 static AnalysisKey Key; 437 }; 438 439 extern template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>; 440 441 /// A proxy from a \c CGSCCAnalysisManager to a \c Function. 442 using CGSCCAnalysisManagerFunctionProxy = 443 OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>; 444 445 /// Helper to update the call graph after running a function pass. 446 /// 447 /// Function passes can only mutate the call graph in specific ways. This 448 /// routine provides a helper that updates the call graph in those ways 449 /// including returning whether any changes were made and populating a CG 450 /// update result struct for the overall CGSCC walk. 451 LazyCallGraph::SCC &updateCGAndAnalysisManagerForFunctionPass( 452 LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, 453 CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, 454 FunctionAnalysisManager &FAM); 455 456 /// Helper to update the call graph after running a CGSCC pass. 457 /// 458 /// CGSCC passes can only mutate the call graph in specific ways. This 459 /// routine provides a helper that updates the call graph in those ways 460 /// including returning whether any changes were made and populating a CG 461 /// update result struct for the overall CGSCC walk. 462 LazyCallGraph::SCC &updateCGAndAnalysisManagerForCGSCCPass( 463 LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, 464 CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, 465 FunctionAnalysisManager &FAM); 466 467 /// Adaptor that maps from a SCC to its functions. 468 /// 469 /// Designed to allow composition of a FunctionPass(Manager) and 470 /// a CGSCCPassManager. Note that if this pass is constructed with a pointer 471 /// to a \c CGSCCAnalysisManager it will run the 472 /// \c FunctionAnalysisManagerCGSCCProxy analysis prior to running the function 473 /// pass over the SCC to enable a \c FunctionAnalysisManager to be used 474 /// within this run safely. 475 class CGSCCToFunctionPassAdaptor 476 : public PassInfoMixin<CGSCCToFunctionPassAdaptor> { 477 public: 478 using PassConceptT = detail::PassConcept<Function, FunctionAnalysisManager>; 479 480 explicit CGSCCToFunctionPassAdaptor(std::unique_ptr<PassConceptT> Pass, 481 bool EagerlyInvalidate, bool NoRerun) 482 : Pass(std::move(Pass)), EagerlyInvalidate(EagerlyInvalidate), 483 NoRerun(NoRerun) {} 484 485 CGSCCToFunctionPassAdaptor(CGSCCToFunctionPassAdaptor &&Arg) 486 : Pass(std::move(Arg.Pass)), EagerlyInvalidate(Arg.EagerlyInvalidate), 487 NoRerun(Arg.NoRerun) {} 488 489 friend void swap(CGSCCToFunctionPassAdaptor &LHS, 490 CGSCCToFunctionPassAdaptor &RHS) { 491 std::swap(LHS.Pass, RHS.Pass); 492 } 493 494 CGSCCToFunctionPassAdaptor &operator=(CGSCCToFunctionPassAdaptor RHS) { 495 swap(*this, RHS); 496 return *this; 497 } 498 499 /// Runs the function pass across every function in the module. 500 PreservedAnalyses run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, 501 LazyCallGraph &CG, CGSCCUpdateResult &UR); 502 503 void printPipeline(raw_ostream &OS, 504 function_ref<StringRef(StringRef)> MapClassName2PassName) { 505 OS << "function"; 506 if (EagerlyInvalidate) 507 OS << "<eager-inv>"; 508 OS << "("; 509 Pass->printPipeline(OS, MapClassName2PassName); 510 OS << ")"; 511 } 512 513 static bool isRequired() { return true; } 514 515 private: 516 std::unique_ptr<PassConceptT> Pass; 517 bool EagerlyInvalidate; 518 bool NoRerun; 519 }; 520 521 /// A function to deduce a function pass type and wrap it in the 522 /// templated adaptor. 523 template <typename FunctionPassT> 524 CGSCCToFunctionPassAdaptor 525 createCGSCCToFunctionPassAdaptor(FunctionPassT &&Pass, 526 bool EagerlyInvalidate = false, 527 bool NoRerun = false) { 528 using PassModelT = 529 detail::PassModel<Function, FunctionPassT, PreservedAnalyses, 530 FunctionAnalysisManager>; 531 // Do not use make_unique, it causes too many template instantiations, 532 // causing terrible compile times. 533 return CGSCCToFunctionPassAdaptor( 534 std::unique_ptr<CGSCCToFunctionPassAdaptor::PassConceptT>( 535 new PassModelT(std::forward<FunctionPassT>(Pass))), 536 EagerlyInvalidate, NoRerun); 537 } 538 539 // A marker to determine if function passes should be run on a function within a 540 // CGSCCToFunctionPassAdaptor. This is used to prevent running an expensive 541 // function pass (manager) on a function multiple times if SCC mutations cause a 542 // function to be visited multiple times and the function is not modified by 543 // other SCC passes. 544 class ShouldNotRunFunctionPassesAnalysis 545 : public AnalysisInfoMixin<ShouldNotRunFunctionPassesAnalysis> { 546 public: 547 static AnalysisKey Key; 548 struct Result {}; 549 550 Result run(Function &F, FunctionAnalysisManager &FAM) { return Result(); } 551 }; 552 553 /// A helper that repeats an SCC pass each time an indirect call is refined to 554 /// a direct call by that pass. 555 /// 556 /// While the CGSCC pass manager works to re-visit SCCs and RefSCCs as they 557 /// change shape, we may also want to repeat an SCC pass if it simply refines 558 /// an indirect call to a direct call, even if doing so does not alter the 559 /// shape of the graph. Note that this only pertains to direct calls to 560 /// functions where IPO across the SCC may be able to compute more precise 561 /// results. For intrinsics, we assume scalar optimizations already can fully 562 /// reason about them. 563 /// 564 /// This repetition has the potential to be very large however, as each one 565 /// might refine a single call site. As a consequence, in practice we use an 566 /// upper bound on the number of repetitions to limit things. 567 class DevirtSCCRepeatedPass : public PassInfoMixin<DevirtSCCRepeatedPass> { 568 public: 569 using PassConceptT = 570 detail::PassConcept<LazyCallGraph::SCC, CGSCCAnalysisManager, 571 LazyCallGraph &, CGSCCUpdateResult &>; 572 573 explicit DevirtSCCRepeatedPass(std::unique_ptr<PassConceptT> Pass, 574 int MaxIterations) 575 : Pass(std::move(Pass)), MaxIterations(MaxIterations) {} 576 577 /// Runs the wrapped pass up to \c MaxIterations on the SCC, iterating 578 /// whenever an indirect call is refined. 579 PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM, 580 LazyCallGraph &CG, CGSCCUpdateResult &UR); 581 582 void printPipeline(raw_ostream &OS, 583 function_ref<StringRef(StringRef)> MapClassName2PassName) { 584 OS << "devirt<" << MaxIterations << ">("; 585 Pass->printPipeline(OS, MapClassName2PassName); 586 OS << ")"; 587 } 588 589 private: 590 std::unique_ptr<PassConceptT> Pass; 591 int MaxIterations; 592 }; 593 594 /// A function to deduce a function pass type and wrap it in the 595 /// templated adaptor. 596 template <typename CGSCCPassT> 597 DevirtSCCRepeatedPass createDevirtSCCRepeatedPass(CGSCCPassT &&Pass, 598 int MaxIterations) { 599 using PassModelT = detail::PassModel<LazyCallGraph::SCC, CGSCCPassT, 600 PreservedAnalyses, CGSCCAnalysisManager, 601 LazyCallGraph &, CGSCCUpdateResult &>; 602 // Do not use make_unique, it causes too many template instantiations, 603 // causing terrible compile times. 604 return DevirtSCCRepeatedPass( 605 std::unique_ptr<DevirtSCCRepeatedPass::PassConceptT>( 606 new PassModelT(std::forward<CGSCCPassT>(Pass))), 607 MaxIterations); 608 } 609 610 // Clear out the debug logging macro. 611 #undef DEBUG_TYPE 612 613 } // end namespace llvm 614 615 #endif // LLVM_ANALYSIS_CGSCCPASSMANAGER_H 616