1196 lines · cpp
1//===- CGSCCPassManager.cpp - Managing & running CGSCC passes -------------===//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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/Analysis/CGSCCPassManager.h"10#include "llvm/ADT/ArrayRef.h"11#include "llvm/ADT/PriorityWorklist.h"12#include "llvm/ADT/STLExtras.h"13#include "llvm/ADT/SetVector.h"14#include "llvm/ADT/SmallPtrSet.h"15#include "llvm/ADT/SmallVector.h"16#include "llvm/ADT/Statistic.h"17#include "llvm/ADT/iterator_range.h"18#include "llvm/Analysis/LazyCallGraph.h"19#include "llvm/IR/Constant.h"20#include "llvm/IR/InstIterator.h"21#include "llvm/IR/Instruction.h"22#include "llvm/IR/PassManager.h"23#include "llvm/IR/PassManagerImpl.h"24#include "llvm/IR/ValueHandle.h"25#include "llvm/Support/Casting.h"26#include "llvm/Support/CommandLine.h"27#include "llvm/Support/Compiler.h"28#include "llvm/Support/Debug.h"29#include "llvm/Support/ErrorHandling.h"30#include "llvm/Support/raw_ostream.h"31#include <cassert>32#include <optional>33 34#define DEBUG_TYPE "cgscc"35 36using namespace llvm;37 38STATISTIC(LargestCGSCC, "Number of functions in the largest SCC");39 40// Explicit template instantiations and specialization definitions for core41// template typedefs.42namespace llvm {43static cl::opt<bool> AbortOnMaxDevirtIterationsReached(44 "abort-on-max-devirt-iterations-reached",45 cl::desc("Abort when the max iterations for devirtualization CGSCC repeat "46 "pass is reached"));47 48AnalysisKey ShouldNotRunFunctionPassesAnalysis::Key;49 50// Explicit instantiations for the core proxy templates.51template class LLVM_EXPORT_TEMPLATE AllAnalysesOn<LazyCallGraph::SCC>;52template class LLVM_EXPORT_TEMPLATE53 AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;54template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,55 LazyCallGraph &, CGSCCUpdateResult &>;56template class LLVM_EXPORT_TEMPLATE57 InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;58template class LLVM_EXPORT_TEMPLATE OuterAnalysisManagerProxy<59 ModuleAnalysisManager, LazyCallGraph::SCC, LazyCallGraph &>;60template class LLVM_EXPORT_TEMPLATE61 OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;62 63/// Explicitly specialize the pass manager run method to handle call graph64/// updates.65template <>66PreservedAnalyses67PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,68 CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC,69 CGSCCAnalysisManager &AM,70 LazyCallGraph &G, CGSCCUpdateResult &UR) {71 // Request PassInstrumentation from analysis manager, will use it to run72 // instrumenting callbacks for the passes later.73 PassInstrumentation PI =74 AM.getResult<PassInstrumentationAnalysis>(InitialC, G);75 76 PreservedAnalyses PA = PreservedAnalyses::all();77 78 // The SCC may be refined while we are running passes over it, so set up79 // a pointer that we can update.80 LazyCallGraph::SCC *C = &InitialC;81 82 // Get Function analysis manager from its proxy.83 FunctionAnalysisManager &FAM =84 AM.getCachedResult<FunctionAnalysisManagerCGSCCProxy>(*C)->getManager();85 86 for (auto &Pass : Passes) {87 // Check the PassInstrumentation's BeforePass callbacks before running the88 // pass, skip its execution completely if asked to (callback returns false).89 if (!PI.runBeforePass(*Pass, *C))90 continue;91 92 LargestCGSCC.updateMax(C->size());93 94 PreservedAnalyses PassPA = Pass->run(*C, AM, G, UR);95 96 // Update the SCC if necessary.97 C = UR.UpdatedC ? UR.UpdatedC : C;98 if (UR.UpdatedC) {99 // If C is updated, also create a proxy and update FAM inside the result.100 auto *ResultFAMCP =101 &AM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, G);102 ResultFAMCP->updateFAM(FAM);103 }104 105 // Intersect the final preserved analyses to compute the aggregate106 // preserved set for this pass manager.107 PA.intersect(PassPA);108 109 // If the CGSCC pass wasn't able to provide a valid updated SCC, the110 // current SCC may simply need to be skipped if invalid.111 if (UR.InvalidatedSCCs.count(C)) {112 PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass, PassPA);113 LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");114 break;115 }116 117 // Check that we didn't miss any update scenario.118 assert(C->begin() != C->end() && "Cannot have an empty SCC!");119 120 // Update the analysis manager as each pass runs and potentially121 // invalidates analyses.122 AM.invalidate(*C, PassPA);123 124 PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);125 }126 127 // Before we mark all of *this* SCC's analyses as preserved below, intersect128 // this with the cross-SCC preserved analysis set. This is used to allow129 // CGSCC passes to mutate ancestor SCCs and still trigger proper invalidation130 // for them.131 UR.CrossSCCPA.intersect(PA);132 133 // Invalidation was handled after each pass in the above loop for the current134 // SCC. Therefore, the remaining analysis results in the AnalysisManager are135 // preserved. We mark this with a set so that we don't need to inspect each136 // one individually.137 PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();138 139 return PA;140}141 142PreservedAnalyses143ModuleToPostOrderCGSCCPassAdaptor::run(Module &M, ModuleAnalysisManager &AM) {144 // Setup the CGSCC analysis manager from its proxy.145 CGSCCAnalysisManager &CGAM =146 AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();147 148 // Get the call graph for this module.149 LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);150 151 // Get Function analysis manager from its proxy.152 FunctionAnalysisManager &FAM =153 AM.getCachedResult<FunctionAnalysisManagerModuleProxy>(M)->getManager();154 155 // We keep worklists to allow us to push more work onto the pass manager as156 // the passes are run.157 SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;158 SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;159 160 // Keep sets for invalidated SCCs that should be skipped when161 // iterating off the worklists.162 SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;163 164 SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>165 InlinedInternalEdges;166 167 SmallVector<Function *, 4> DeadFunctions;168 169 CGSCCUpdateResult UR = {CWorklist,170 InvalidSCCSet,171 nullptr,172 PreservedAnalyses::all(),173 InlinedInternalEdges,174 DeadFunctions,175 {}};176 177 // Request PassInstrumentation from analysis manager, will use it to run178 // instrumenting callbacks for the passes later.179 PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);180 181 PreservedAnalyses PA = PreservedAnalyses::all();182 CG.buildRefSCCs();183 for (LazyCallGraph::RefSCC &RC :184 llvm::make_early_inc_range(CG.postorder_ref_sccs())) {185 assert(RCWorklist.empty() &&186 "Should always start with an empty RefSCC worklist");187 // The postorder_ref_sccs range we are walking is lazily constructed, so188 // we only push the first one onto the worklist. The worklist allows us189 // to capture *new* RefSCCs created during transformations.190 //191 // We really want to form RefSCCs lazily because that makes them cheaper192 // to update as the program is simplified and allows us to have greater193 // cache locality as forming a RefSCC touches all the parts of all the194 // functions within that RefSCC.195 //196 // We also eagerly increment the iterator to the next position because197 // the CGSCC passes below may delete the current RefSCC.198 RCWorklist.insert(&RC);199 200 do {201 LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();202 assert(CWorklist.empty() &&203 "Should always start with an empty SCC worklist");204 205 LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC206 << "\n");207 208 // The top of the worklist may *also* be the same SCC we just ran over209 // (and invalidated for). Keep track of that last SCC we processed due210 // to SCC update to avoid redundant processing when an SCC is both just211 // updated itself and at the top of the worklist.212 LazyCallGraph::SCC *LastUpdatedC = nullptr;213 214 // Push the initial SCCs in reverse post-order as we'll pop off the215 // back and so see this in post-order.216 for (LazyCallGraph::SCC &C : llvm::reverse(*RC))217 CWorklist.insert(&C);218 219 do {220 LazyCallGraph::SCC *C = CWorklist.pop_back_val();221 // Due to call graph mutations, we may have invalid SCCs or SCCs from222 // other RefSCCs in the worklist. The invalid ones are dead and the223 // other RefSCCs should be queued above, so we just need to skip both224 // scenarios here.225 if (InvalidSCCSet.count(C)) {226 LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");227 continue;228 }229 if (LastUpdatedC == C) {230 LLVM_DEBUG(dbgs() << "Skipping redundant run on SCC: " << *C << "\n");231 continue;232 }233 // We used to also check if the current SCC is part of the current234 // RefSCC and bail if it wasn't, since it should be in RCWorklist.235 // However, this can cause compile time explosions in some cases on236 // modules with a huge RefSCC. If a non-trivial amount of SCCs in the237 // huge RefSCC can become their own child RefSCC, we create one child238 // RefSCC, bail on the current RefSCC, visit the child RefSCC, revisit239 // the huge RefSCC, and repeat. By visiting all SCCs in the original240 // RefSCC we create all the child RefSCCs in one pass of the RefSCC,241 // rather one pass of the RefSCC creating one child RefSCC at a time.242 243 // Ensure we can proxy analysis updates from the CGSCC analysis manager244 // into the Function analysis manager by getting a proxy here.245 // This also needs to update the FunctionAnalysisManager, as this may be246 // the first time we see this SCC.247 CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(248 FAM);249 250 // Each time we visit a new SCC pulled off the worklist,251 // a transformation of a child SCC may have also modified this parent252 // and invalidated analyses. So we invalidate using the update record's253 // cross-SCC preserved set. This preserved set is intersected by any254 // CGSCC pass that handles invalidation (primarily pass managers) prior255 // to marking its SCC as preserved. That lets us track everything that256 // might need invalidation across SCCs without excessive invalidations257 // on a single SCC.258 //259 // This essentially allows SCC passes to freely invalidate analyses260 // of any ancestor SCC. If this becomes detrimental to successfully261 // caching analyses, we could force each SCC pass to manually262 // invalidate the analyses for any SCCs other than themselves which263 // are mutated. However, that seems to lose the robustness of the264 // pass-manager driven invalidation scheme.265 CGAM.invalidate(*C, UR.CrossSCCPA);266 267 do {268 // Check that we didn't miss any update scenario.269 assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");270 assert(C->begin() != C->end() && "Cannot have an empty SCC!");271 272 LastUpdatedC = UR.UpdatedC;273 UR.UpdatedC = nullptr;274 275 // Check the PassInstrumentation's BeforePass callbacks before276 // running the pass, skip its execution completely if asked to277 // (callback returns false).278 if (!PI.runBeforePass<LazyCallGraph::SCC>(*Pass, *C))279 continue;280 281 PreservedAnalyses PassPA = Pass->run(*C, CGAM, CG, UR);282 283 // Update the SCC and RefSCC if necessary.284 C = UR.UpdatedC ? UR.UpdatedC : C;285 286 if (UR.UpdatedC) {287 // If we're updating the SCC, also update the FAM inside the proxy's288 // result.289 CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(290 FAM);291 }292 293 // Intersect with the cross-SCC preserved set to capture any294 // cross-SCC invalidation.295 UR.CrossSCCPA.intersect(PassPA);296 // Intersect the preserved set so that invalidation of module297 // analyses will eventually occur when the module pass completes.298 PA.intersect(PassPA);299 300 // If the CGSCC pass wasn't able to provide a valid updated SCC,301 // the current SCC may simply need to be skipped if invalid.302 if (UR.InvalidatedSCCs.count(C)) {303 PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass, PassPA);304 LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");305 break;306 }307 308 // Check that we didn't miss any update scenario.309 assert(C->begin() != C->end() && "Cannot have an empty SCC!");310 311 // We handle invalidating the CGSCC analysis manager's information312 // for the (potentially updated) SCC here. Note that any other SCCs313 // whose structure has changed should have been invalidated by314 // whatever was updating the call graph. This SCC gets invalidated315 // late as it contains the nodes that were actively being316 // processed.317 CGAM.invalidate(*C, PassPA);318 319 PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);320 321 // The pass may have restructured the call graph and refined the322 // current SCC and/or RefSCC. We need to update our current SCC and323 // RefSCC pointers to follow these. Also, when the current SCC is324 // refined, re-run the SCC pass over the newly refined SCC in order325 // to observe the most precise SCC model available. This inherently326 // cannot cycle excessively as it only happens when we split SCCs327 // apart, at most converging on a DAG of single nodes.328 // FIXME: If we ever start having RefSCC passes, we'll want to329 // iterate there too.330 if (UR.UpdatedC)331 LLVM_DEBUG(dbgs()332 << "Re-running SCC passes after a refinement of the "333 "current SCC: "334 << *UR.UpdatedC << "\n");335 336 // Note that both `C` and `RC` may at this point refer to deleted,337 // invalid SCC and RefSCCs respectively. But we will short circuit338 // the processing when we check them in the loop above.339 } while (UR.UpdatedC);340 } while (!CWorklist.empty());341 342 // We only need to keep internal inlined edge information within343 // a RefSCC, clear it to save on space and let the next time we visit344 // any of these functions have a fresh start.345 InlinedInternalEdges.clear();346 } while (!RCWorklist.empty());347 }348 349 CG.removeDeadFunctions(DeadFunctions);350 for (Function *DeadF : DeadFunctions)351 DeadF->eraseFromParent();352 353#if defined(EXPENSIVE_CHECKS)354 // Verify that the call graph is still valid.355 CG.verify();356#endif357 358 // By definition we preserve the call garph, all SCC analyses, and the359 // analysis proxies by handling them above and in any nested pass managers.360 PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();361 PA.preserve<LazyCallGraphAnalysis>();362 PA.preserve<CGSCCAnalysisManagerModuleProxy>();363 PA.preserve<FunctionAnalysisManagerModuleProxy>();364 return PA;365}366 367PreservedAnalyses DevirtSCCRepeatedPass::run(LazyCallGraph::SCC &InitialC,368 CGSCCAnalysisManager &AM,369 LazyCallGraph &CG,370 CGSCCUpdateResult &UR) {371 PreservedAnalyses PA = PreservedAnalyses::all();372 PassInstrumentation PI =373 AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);374 375 // The SCC may be refined while we are running passes over it, so set up376 // a pointer that we can update.377 LazyCallGraph::SCC *C = &InitialC;378 379 // Struct to track the counts of direct and indirect calls in each function380 // of the SCC.381 struct CallCount {382 int Direct;383 int Indirect;384 };385 386 // Put value handles on all of the indirect calls and return the number of387 // direct calls for each function in the SCC.388 auto ScanSCC = [](LazyCallGraph::SCC &C,389 SmallMapVector<Value *, WeakTrackingVH, 16> &CallHandles) {390 assert(CallHandles.empty() && "Must start with a clear set of handles.");391 392 SmallDenseMap<Function *, CallCount> CallCounts;393 CallCount CountLocal = {0, 0};394 for (LazyCallGraph::Node &N : C) {395 CallCount &Count =396 CallCounts.insert(std::make_pair(&N.getFunction(), CountLocal))397 .first->second;398 for (Instruction &I : instructions(N.getFunction()))399 if (auto *CB = dyn_cast<CallBase>(&I)) {400 if (CB->getCalledFunction()) {401 ++Count.Direct;402 } else {403 ++Count.Indirect;404 CallHandles.insert({CB, WeakTrackingVH(CB)});405 }406 }407 }408 409 return CallCounts;410 };411 412 UR.IndirectVHs.clear();413 // Populate the initial call handles and get the initial call counts.414 auto CallCounts = ScanSCC(*C, UR.IndirectVHs);415 416 for (int Iteration = 0;; ++Iteration) {417 if (!PI.runBeforePass<LazyCallGraph::SCC>(*Pass, *C))418 continue;419 420 PreservedAnalyses PassPA = Pass->run(*C, AM, CG, UR);421 422 PA.intersect(PassPA);423 424 // If the CGSCC pass wasn't able to provide a valid updated SCC, the425 // current SCC may simply need to be skipped if invalid.426 if (UR.InvalidatedSCCs.count(C)) {427 PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass, PassPA);428 LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");429 break;430 }431 432 // Update the analysis manager with each run and intersect the total set433 // of preserved analyses so we're ready to iterate.434 AM.invalidate(*C, PassPA);435 436 PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);437 438 // If the SCC structure has changed, bail immediately and let the outer439 // CGSCC layer handle any iteration to reflect the refined structure.440 if (UR.UpdatedC && UR.UpdatedC != C)441 break;442 443 assert(C->begin() != C->end() && "Cannot have an empty SCC!");444 445 // Check whether any of the handles were devirtualized.446 bool Devirt = llvm::any_of(UR.IndirectVHs, [](auto &P) -> bool {447 if (P.second) {448 if (CallBase *CB = dyn_cast<CallBase>(P.second)) {449 if (CB->getCalledFunction()) {450 LLVM_DEBUG(dbgs() << "Found devirtualized call: " << *CB << "\n");451 return true;452 }453 }454 }455 return false;456 });457 458 // Rescan to build up a new set of handles and count how many direct459 // calls remain. If we decide to iterate, this also sets up the input to460 // the next iteration.461 UR.IndirectVHs.clear();462 auto NewCallCounts = ScanSCC(*C, UR.IndirectVHs);463 464 // If we haven't found an explicit devirtualization already see if we465 // have decreased the number of indirect calls and increased the number466 // of direct calls for any function in the SCC. This can be fooled by all467 // manner of transformations such as DCE and other things, but seems to468 // work well in practice.469 if (!Devirt)470 // Iterate over the keys in NewCallCounts, if Function also exists in471 // CallCounts, make the check below.472 for (auto &Pair : NewCallCounts) {473 auto &CallCountNew = Pair.second;474 auto CountIt = CallCounts.find(Pair.first);475 if (CountIt != CallCounts.end()) {476 const auto &CallCountOld = CountIt->second;477 if (CallCountOld.Indirect > CallCountNew.Indirect &&478 CallCountOld.Direct < CallCountNew.Direct) {479 Devirt = true;480 break;481 }482 }483 }484 485 if (!Devirt) {486 break;487 }488 489 // Otherwise, if we've already hit our max, we're done.490 if (Iteration >= MaxIterations) {491 if (AbortOnMaxDevirtIterationsReached)492 report_fatal_error("Max devirtualization iterations reached");493 LLVM_DEBUG(494 dbgs() << "Found another devirtualization after hitting the max "495 "number of repetitions ("496 << MaxIterations << ") on SCC: " << *C << "\n");497 break;498 }499 500 LLVM_DEBUG(501 dbgs() << "Repeating an SCC pass after finding a devirtualization in: "502 << *C << "\n");503 504 // Move over the new call counts in preparation for iterating.505 CallCounts = std::move(NewCallCounts);506 }507 508 // Note that we don't add any preserved entries here unlike a more normal509 // "pass manager" because we only handle invalidation *between* iterations,510 // not after the last iteration.511 return PA;512}513 514PreservedAnalyses CGSCCToFunctionPassAdaptor::run(LazyCallGraph::SCC &C,515 CGSCCAnalysisManager &AM,516 LazyCallGraph &CG,517 CGSCCUpdateResult &UR) {518 // Setup the function analysis manager from its proxy.519 FunctionAnalysisManager &FAM =520 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();521 522 SmallVector<LazyCallGraph::Node *, 4> Nodes(llvm::make_pointer_range(C));523 524 // The SCC may get split while we are optimizing functions due to deleting525 // edges. If this happens, the current SCC can shift, so keep track of526 // a pointer we can overwrite.527 LazyCallGraph::SCC *CurrentC = &C;528 529 LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C << "\n");530 531 PreservedAnalyses PA = PreservedAnalyses::all();532 for (LazyCallGraph::Node *N : Nodes) {533 // Skip nodes from other SCCs. These may have been split out during534 // processing. We'll eventually visit those SCCs and pick up the nodes535 // there.536 if (CG.lookupSCC(*N) != CurrentC)537 continue;538 539 Function &F = N->getFunction();540 541 if (NoRerun && FAM.getCachedResult<ShouldNotRunFunctionPassesAnalysis>(F))542 continue;543 544 PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F);545 if (!PI.runBeforePass<Function>(*Pass, F))546 continue;547 548 PreservedAnalyses PassPA = Pass->run(F, FAM);549 550 // We know that the function pass couldn't have invalidated any other551 // function's analyses (that's the contract of a function pass), so552 // directly handle the function analysis manager's invalidation here.553 FAM.invalidate(F, EagerlyInvalidate ? PreservedAnalyses::none() : PassPA);554 555 PI.runAfterPass<Function>(*Pass, F, PassPA);556 557 // Then intersect the preserved set so that invalidation of module558 // analyses will eventually occur when the module pass completes.559 PA.intersect(std::move(PassPA));560 561 // If the call graph hasn't been preserved, update it based on this562 // function pass. This may also update the current SCC to point to563 // a smaller, more refined SCC.564 auto PAC = PA.getChecker<LazyCallGraphAnalysis>();565 if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {566 CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,567 AM, UR, FAM);568 assert(CG.lookupSCC(*N) == CurrentC &&569 "Current SCC not updated to the SCC containing the current node!");570 }571 }572 573 // By definition we preserve the proxy. And we preserve all analyses on574 // Functions. This precludes *any* invalidation of function analyses by the575 // proxy, but that's OK because we've taken care to invalidate analyses in576 // the function analysis manager incrementally above.577 PA.preserveSet<AllAnalysesOn<Function>>();578 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();579 580 // We've also ensured that we updated the call graph along the way.581 PA.preserve<LazyCallGraphAnalysis>();582 583 return PA;584}585 586bool CGSCCAnalysisManagerModuleProxy::Result::invalidate(587 Module &M, const PreservedAnalyses &PA,588 ModuleAnalysisManager::Invalidator &Inv) {589 // If literally everything is preserved, we're done.590 if (PA.areAllPreserved())591 return false; // This is still a valid proxy.592 593 // If this proxy or the call graph is going to be invalidated, we also need594 // to clear all the keys coming from that analysis.595 //596 // We also directly invalidate the FAM's module proxy if necessary, and if597 // that proxy isn't preserved we can't preserve this proxy either. We rely on598 // it to handle module -> function analysis invalidation in the face of599 // structural changes and so if it's unavailable we conservatively clear the600 // entire SCC layer as well rather than trying to do invalidation ourselves.601 auto PAC = PA.getChecker<CGSCCAnalysisManagerModuleProxy>();602 if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>()) ||603 Inv.invalidate<LazyCallGraphAnalysis>(M, PA) ||604 Inv.invalidate<FunctionAnalysisManagerModuleProxy>(M, PA)) {605 InnerAM->clear();606 607 // And the proxy itself should be marked as invalid so that we can observe608 // the new call graph. This isn't strictly necessary because we cheat609 // above, but is still useful.610 return true;611 }612 613 // Directly check if the relevant set is preserved so we can short circuit614 // invalidating SCCs below.615 bool AreSCCAnalysesPreserved =616 PA.allAnalysesInSetPreserved<AllAnalysesOn<LazyCallGraph::SCC>>();617 618 // Ok, we have a graph, so we can propagate the invalidation down into it.619 G->buildRefSCCs();620 for (auto &RC : G->postorder_ref_sccs())621 for (auto &C : RC) {622 std::optional<PreservedAnalyses> InnerPA;623 624 // Check to see whether the preserved set needs to be adjusted based on625 // module-level analysis invalidation triggering deferred invalidation626 // for this SCC.627 if (auto *OuterProxy =628 InnerAM->getCachedResult<ModuleAnalysisManagerCGSCCProxy>(C))629 for (const auto &OuterInvalidationPair :630 OuterProxy->getOuterInvalidations()) {631 AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;632 const auto &InnerAnalysisIDs = OuterInvalidationPair.second;633 if (Inv.invalidate(OuterAnalysisID, M, PA)) {634 if (!InnerPA)635 InnerPA = PA;636 for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)637 InnerPA->abandon(InnerAnalysisID);638 }639 }640 641 // Check if we needed a custom PA set. If so we'll need to run the inner642 // invalidation.643 if (InnerPA) {644 InnerAM->invalidate(C, *InnerPA);645 continue;646 }647 648 // Otherwise we only need to do invalidation if the original PA set didn't649 // preserve all SCC analyses.650 if (!AreSCCAnalysesPreserved)651 InnerAM->invalidate(C, PA);652 }653 654 // Return false to indicate that this result is still a valid proxy.655 return false;656}657 658template <>659CGSCCAnalysisManagerModuleProxy::Result660CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM) {661 // Force the Function analysis manager to also be available so that it can662 // be accessed in an SCC analysis and proxied onward to function passes.663 // FIXME: It is pretty awkward to just drop the result here and assert that664 // we can find it again later.665 (void)AM.getResult<FunctionAnalysisManagerModuleProxy>(M);666 667 return Result(*InnerAM, AM.getResult<LazyCallGraphAnalysis>(M));668}669 670AnalysisKey FunctionAnalysisManagerCGSCCProxy::Key;671 672FunctionAnalysisManagerCGSCCProxy::Result673FunctionAnalysisManagerCGSCCProxy::run(LazyCallGraph::SCC &C,674 CGSCCAnalysisManager &AM,675 LazyCallGraph &CG) {676 // Note: unconditionally getting checking that the proxy exists may get it at677 // this point. There are cases when this is being run unnecessarily, but678 // it is cheap and having the assertion in place is more valuable.679 auto &MAMProxy = AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG);680 Module &M = *C.begin()->getFunction().getParent();681 bool ProxyExists =682 MAMProxy.cachedResultExists<FunctionAnalysisManagerModuleProxy>(M);683 assert(ProxyExists &&684 "The CGSCC pass manager requires that the FAM module proxy is run "685 "on the module prior to entering the CGSCC walk");686 (void)ProxyExists;687 688 // We just return an empty result. The caller will use the updateFAM interface689 // to correctly register the relevant FunctionAnalysisManager based on the690 // context in which this proxy is run.691 return Result();692}693 694bool FunctionAnalysisManagerCGSCCProxy::Result::invalidate(695 LazyCallGraph::SCC &C, const PreservedAnalyses &PA,696 CGSCCAnalysisManager::Invalidator &Inv) {697 // If literally everything is preserved, we're done.698 if (PA.areAllPreserved())699 return false; // This is still a valid proxy.700 701 // All updates to preserve valid results are done below, so we don't need to702 // invalidate this proxy.703 //704 // Note that in order to preserve this proxy, a module pass must ensure that705 // the FAM has been completely updated to handle the deletion of functions.706 // Specifically, any FAM-cached results for those functions need to have been707 // forcibly cleared. When preserved, this proxy will only invalidate results708 // cached on functions *still in the module* at the end of the module pass.709 auto PAC = PA.getChecker<FunctionAnalysisManagerCGSCCProxy>();710 if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>()) {711 for (LazyCallGraph::Node &N : C)712 FAM->invalidate(N.getFunction(), PA);713 714 return false;715 }716 717 // Directly check if the relevant set is preserved.718 bool AreFunctionAnalysesPreserved =719 PA.allAnalysesInSetPreserved<AllAnalysesOn<Function>>();720 721 // Now walk all the functions to see if any inner analysis invalidation is722 // necessary.723 for (LazyCallGraph::Node &N : C) {724 Function &F = N.getFunction();725 std::optional<PreservedAnalyses> FunctionPA;726 727 // Check to see whether the preserved set needs to be pruned based on728 // SCC-level analysis invalidation that triggers deferred invalidation729 // registered with the outer analysis manager proxy for this function.730 if (auto *OuterProxy =731 FAM->getCachedResult<CGSCCAnalysisManagerFunctionProxy>(F))732 for (const auto &OuterInvalidationPair :733 OuterProxy->getOuterInvalidations()) {734 AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;735 const auto &InnerAnalysisIDs = OuterInvalidationPair.second;736 if (Inv.invalidate(OuterAnalysisID, C, PA)) {737 if (!FunctionPA)738 FunctionPA = PA;739 for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)740 FunctionPA->abandon(InnerAnalysisID);741 }742 }743 744 // Check if we needed a custom PA set, and if so we'll need to run the745 // inner invalidation.746 if (FunctionPA) {747 FAM->invalidate(F, *FunctionPA);748 continue;749 }750 751 // Otherwise we only need to do invalidation if the original PA set didn't752 // preserve all function analyses.753 if (!AreFunctionAnalysesPreserved)754 FAM->invalidate(F, PA);755 }756 757 // Return false to indicate that this result is still a valid proxy.758 return false;759}760 761} // end namespace llvm762 763/// When a new SCC is created for the graph we first update the764/// FunctionAnalysisManager in the Proxy's result.765/// As there might be function analysis results cached for the functions now in766/// that SCC, two forms of updates are required.767///768/// First, a proxy from the SCC to the FunctionAnalysisManager needs to be769/// created so that any subsequent invalidation events to the SCC are770/// propagated to the function analysis results cached for functions within it.771///772/// Second, if any of the functions within the SCC have analysis results with773/// outer analysis dependencies, then those dependencies would point to the774/// *wrong* SCC's analysis result. We forcibly invalidate the necessary775/// function analyses so that they don't retain stale handles.776static void updateNewSCCFunctionAnalyses(LazyCallGraph::SCC &C,777 LazyCallGraph &G,778 CGSCCAnalysisManager &AM,779 FunctionAnalysisManager &FAM) {780 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, G).updateFAM(FAM);781 782 // Now walk the functions in this SCC and invalidate any function analysis783 // results that might have outer dependencies on an SCC analysis.784 for (LazyCallGraph::Node &N : C) {785 Function &F = N.getFunction();786 787 auto *OuterProxy =788 FAM.getCachedResult<CGSCCAnalysisManagerFunctionProxy>(F);789 if (!OuterProxy)790 // No outer analyses were queried, nothing to do.791 continue;792 793 // Forcibly abandon all the inner analyses with dependencies, but794 // invalidate nothing else.795 auto PA = PreservedAnalyses::all();796 for (const auto &OuterInvalidationPair :797 OuterProxy->getOuterInvalidations()) {798 const auto &InnerAnalysisIDs = OuterInvalidationPair.second;799 for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)800 PA.abandon(InnerAnalysisID);801 }802 803 // Now invalidate anything we found.804 FAM.invalidate(F, PA);805 }806}807 808/// Helper function to update both the \c CGSCCAnalysisManager \p AM and the \c809/// CGSCCPassManager's \c CGSCCUpdateResult \p UR based on a range of newly810/// added SCCs.811///812/// The range of new SCCs must be in postorder already. The SCC they were split813/// out of must be provided as \p C. The current node being mutated and814/// triggering updates must be passed as \p N.815///816/// This function returns the SCC containing \p N. This will be either \p C if817/// no new SCCs have been split out, or it will be the new SCC containing \p N.818template <typename SCCRangeT>819static LazyCallGraph::SCC *820incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G,821 LazyCallGraph::Node &N, LazyCallGraph::SCC *C,822 CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR) {823 using SCC = LazyCallGraph::SCC;824 825 if (NewSCCRange.empty())826 return C;827 828 // Add the current SCC to the worklist as its shape has changed.829 UR.CWorklist.insert(C);830 LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist:" << *C831 << "\n");832 833 SCC *OldC = C;834 835 // Update the current SCC. Note that if we have new SCCs, this must actually836 // change the SCC.837 assert(C != &*NewSCCRange.begin() &&838 "Cannot insert new SCCs without changing current SCC!");839 C = &*NewSCCRange.begin();840 assert(G.lookupSCC(N) == C && "Failed to update current SCC!");841 842 // If we had a cached FAM proxy originally, we will want to create more of843 // them for each SCC that was split off.844 FunctionAnalysisManager *FAM = nullptr;845 if (auto *FAMProxy =846 AM.getCachedResult<FunctionAnalysisManagerCGSCCProxy>(*OldC))847 FAM = &FAMProxy->getManager();848 849 // We need to propagate an invalidation call to all but the newly current SCC850 // because the outer pass manager won't do that for us after splitting them.851 // FIXME: We should accept a PreservedAnalysis from the CG updater so that if852 // there are preserved analysis we can avoid invalidating them here for853 // split-off SCCs.854 // We know however that this will preserve any FAM proxy so go ahead and mark855 // that.856 auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();857 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();858 AM.invalidate(*OldC, PA);859 860 // Ensure the now-current SCC's function analyses are updated.861 if (FAM)862 updateNewSCCFunctionAnalyses(*C, G, AM, *FAM);863 864 for (SCC &NewC : llvm::reverse(llvm::drop_begin(NewSCCRange))) {865 assert(C != &NewC && "No need to re-visit the current SCC!");866 assert(OldC != &NewC && "Already handled the original SCC!");867 UR.CWorklist.insert(&NewC);868 LLVM_DEBUG(dbgs() << "Enqueuing a newly formed SCC:" << NewC << "\n");869 870 // Ensure new SCCs' function analyses are updated.871 if (FAM)872 updateNewSCCFunctionAnalyses(NewC, G, AM, *FAM);873 874 // Also propagate a normal invalidation to the new SCC as only the current875 // will get one from the pass manager infrastructure.876 AM.invalidate(NewC, PA);877 }878 return C;879}880 881static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass(882 LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,883 CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR,884 FunctionAnalysisManager &FAM, bool FunctionPass) {885 using Node = LazyCallGraph::Node;886 using Edge = LazyCallGraph::Edge;887 using SCC = LazyCallGraph::SCC;888 using RefSCC = LazyCallGraph::RefSCC;889 890 RefSCC &InitialRC = InitialC.getOuterRefSCC();891 SCC *C = &InitialC;892 RefSCC *RC = &InitialRC;893 Function &F = N.getFunction();894 895 // Walk the function body and build up the set of retained, promoted, and896 // demoted edges.897 SmallVector<Constant *, 16> Worklist;898 SmallPtrSet<Constant *, 16> Visited;899 SmallPtrSet<Node *, 16> RetainedEdges;900 SmallSetVector<Node *, 4> PromotedRefTargets;901 SmallSetVector<Node *, 4> DemotedCallTargets;902 SmallSetVector<Node *, 4> NewCallEdges;903 SmallSetVector<Node *, 4> NewRefEdges;904 905 // First walk the function and handle all called functions. We do this first906 // because if there is a single call edge, whether there are ref edges is907 // irrelevant.908 for (Instruction &I : instructions(F)) {909 if (auto *CB = dyn_cast<CallBase>(&I)) {910 if (Function *Callee = CB->getCalledFunction()) {911 if (Visited.insert(Callee).second && !Callee->isDeclaration()) {912 Node *CalleeN = G.lookup(*Callee);913 assert(CalleeN &&914 "Visited function should already have an associated node");915 Edge *E = N->lookup(*CalleeN);916 assert((E || !FunctionPass) &&917 "No function transformations should introduce *new* "918 "call edges! Any new calls should be modeled as "919 "promoted existing ref edges!");920 bool Inserted = RetainedEdges.insert(CalleeN).second;921 (void)Inserted;922 assert(Inserted && "We should never visit a function twice.");923 if (!E)924 NewCallEdges.insert(CalleeN);925 else if (!E->isCall())926 PromotedRefTargets.insert(CalleeN);927 }928 } else {929 // We can miss devirtualization if an indirect call is created then930 // promoted before updateCGAndAnalysisManagerForPass runs.931 auto *Entry = UR.IndirectVHs.find(CB);932 if (Entry == UR.IndirectVHs.end())933 UR.IndirectVHs.insert({CB, WeakTrackingVH(CB)});934 else if (!Entry->second)935 Entry->second = WeakTrackingVH(CB);936 }937 }938 }939 940 // Now walk all references.941 for (Instruction &I : instructions(F))942 for (Value *Op : I.operand_values())943 if (auto *OpC = dyn_cast<Constant>(Op))944 if (Visited.insert(OpC).second)945 Worklist.push_back(OpC);946 947 auto VisitRef = [&](Function &Referee) {948 Node *RefereeN = G.lookup(Referee);949 assert(RefereeN &&950 "Visited function should already have an associated node");951 Edge *E = N->lookup(*RefereeN);952 assert((E || !FunctionPass) &&953 "No function transformations should introduce *new* ref "954 "edges! Any new ref edges would require IPO which "955 "function passes aren't allowed to do!");956 bool Inserted = RetainedEdges.insert(RefereeN).second;957 (void)Inserted;958 assert(Inserted && "We should never visit a function twice.");959 if (!E)960 NewRefEdges.insert(RefereeN);961 else if (E->isCall())962 DemotedCallTargets.insert(RefereeN);963 };964 LazyCallGraph::visitReferences(Worklist, Visited, VisitRef);965 966 // Handle new ref edges.967 for (Node *RefTarget : NewRefEdges) {968 SCC &TargetC = *G.lookupSCC(*RefTarget);969 RefSCC &TargetRC = TargetC.getOuterRefSCC();970 (void)TargetRC;971 // TODO: This only allows trivial edges to be added for now.972#ifdef EXPENSIVE_CHECKS973 assert((RC == &TargetRC ||974 RC->isAncestorOf(TargetRC)) && "New ref edge is not trivial!");975#endif976 RC->insertTrivialRefEdge(N, *RefTarget);977 }978 979 // Handle new call edges.980 for (Node *CallTarget : NewCallEdges) {981 SCC &TargetC = *G.lookupSCC(*CallTarget);982 RefSCC &TargetRC = TargetC.getOuterRefSCC();983 (void)TargetRC;984 // TODO: This only allows trivial edges to be added for now.985#ifdef EXPENSIVE_CHECKS986 assert((RC == &TargetRC ||987 RC->isAncestorOf(TargetRC)) && "New call edge is not trivial!");988#endif989 // Add a trivial ref edge to be promoted later on alongside990 // PromotedRefTargets.991 RC->insertTrivialRefEdge(N, *CallTarget);992 }993 994 // Include synthetic reference edges to known, defined lib functions.995 for (auto *LibFn : G.getLibFunctions())996 // While the list of lib functions doesn't have repeats, don't re-visit997 // anything handled above.998 if (!Visited.count(LibFn))999 VisitRef(*LibFn);1000 1001 // First remove all of the edges that are no longer present in this function.1002 // The first step makes these edges uniformly ref edges and accumulates them1003 // into a separate data structure so removal doesn't invalidate anything.1004 SmallVector<Node *, 4> DeadTargets;1005 for (Edge &E : *N) {1006 if (RetainedEdges.count(&E.getNode()))1007 continue;1008 1009 SCC &TargetC = *G.lookupSCC(E.getNode());1010 RefSCC &TargetRC = TargetC.getOuterRefSCC();1011 if (&TargetRC == RC && E.isCall()) {1012 if (C != &TargetC) {1013 // For separate SCCs this is trivial.1014 RC->switchTrivialInternalEdgeToRef(N, E.getNode());1015 } else {1016 // Now update the call graph.1017 C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, E.getNode()),1018 G, N, C, AM, UR);1019 }1020 }1021 1022 // Now that this is ready for actual removal, put it into our list.1023 DeadTargets.push_back(&E.getNode());1024 }1025 // Remove the easy cases quickly and actually pull them out of our list.1026 llvm::erase_if(DeadTargets, [&](Node *TargetN) {1027 SCC &TargetC = *G.lookupSCC(*TargetN);1028 RefSCC &TargetRC = TargetC.getOuterRefSCC();1029 1030 // We can't trivially remove internal targets, so skip1031 // those.1032 if (&TargetRC == RC)1033 return false;1034 1035 LLVM_DEBUG(dbgs() << "Deleting outgoing edge from '" << N << "' to '"1036 << *TargetN << "'\n");1037 RC->removeOutgoingEdge(N, *TargetN);1038 return true;1039 });1040 1041 // Next demote all the call edges that are now ref edges. This helps make1042 // the SCCs small which should minimize the work below as we don't want to1043 // form cycles that this would break.1044 for (Node *RefTarget : DemotedCallTargets) {1045 SCC &TargetC = *G.lookupSCC(*RefTarget);1046 RefSCC &TargetRC = TargetC.getOuterRefSCC();1047 1048 // The easy case is when the target RefSCC is not this RefSCC. This is1049 // only supported when the target RefSCC is a child of this RefSCC.1050 if (&TargetRC != RC) {1051#ifdef EXPENSIVE_CHECKS1052 assert(RC->isAncestorOf(TargetRC) &&1053 "Cannot potentially form RefSCC cycles here!");1054#endif1055 RC->switchOutgoingEdgeToRef(N, *RefTarget);1056 LLVM_DEBUG(dbgs() << "Switch outgoing call edge to a ref edge from '" << N1057 << "' to '" << *RefTarget << "'\n");1058 continue;1059 }1060 1061 // We are switching an internal call edge to a ref edge. This may split up1062 // some SCCs.1063 if (C != &TargetC) {1064 // For separate SCCs this is trivial.1065 RC->switchTrivialInternalEdgeToRef(N, *RefTarget);1066 continue;1067 }1068 1069 // Now update the call graph.1070 C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, *RefTarget), G, N,1071 C, AM, UR);1072 }1073 1074 // We added a ref edge earlier for new call edges, promote those to call edges1075 // alongside PromotedRefTargets.1076 PromotedRefTargets.insert_range(NewCallEdges);1077 1078 // Now promote ref edges into call edges.1079 for (Node *CallTarget : PromotedRefTargets) {1080 SCC &TargetC = *G.lookupSCC(*CallTarget);1081 RefSCC &TargetRC = TargetC.getOuterRefSCC();1082 1083 // The easy case is when the target RefSCC is not this RefSCC. This is1084 // only supported when the target RefSCC is a child of this RefSCC.1085 if (&TargetRC != RC) {1086#ifdef EXPENSIVE_CHECKS1087 assert(RC->isAncestorOf(TargetRC) &&1088 "Cannot potentially form RefSCC cycles here!");1089#endif1090 RC->switchOutgoingEdgeToCall(N, *CallTarget);1091 LLVM_DEBUG(dbgs() << "Switch outgoing ref edge to a call edge from '" << N1092 << "' to '" << *CallTarget << "'\n");1093 continue;1094 }1095 LLVM_DEBUG(dbgs() << "Switch an internal ref edge to a call edge from '"1096 << N << "' to '" << *CallTarget << "'\n");1097 1098 // Otherwise we are switching an internal ref edge to a call edge. This1099 // may merge away some SCCs, and we add those to the UpdateResult. We also1100 // need to make sure to update the worklist in the event SCCs have moved1101 // before the current one in the post-order sequence1102 bool HasFunctionAnalysisProxy = false;1103 auto InitialSCCIndex = RC->find(*C) - RC->begin();1104 bool FormedCycle = RC->switchInternalEdgeToCall(1105 N, *CallTarget, [&](ArrayRef<SCC *> MergedSCCs) {1106 for (SCC *MergedC : MergedSCCs) {1107 assert(MergedC != &TargetC && "Cannot merge away the target SCC!");1108 1109 HasFunctionAnalysisProxy |=1110 AM.getCachedResult<FunctionAnalysisManagerCGSCCProxy>(1111 *MergedC) != nullptr;1112 1113 // Mark that this SCC will no longer be valid.1114 UR.InvalidatedSCCs.insert(MergedC);1115 1116 // FIXME: We should really do a 'clear' here to forcibly release1117 // memory, but we don't have a good way of doing that and1118 // preserving the function analyses.1119 auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();1120 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();1121 AM.invalidate(*MergedC, PA);1122 }1123 });1124 1125 // If we formed a cycle by creating this call, we need to update more data1126 // structures.1127 if (FormedCycle) {1128 C = &TargetC;1129 assert(G.lookupSCC(N) == C && "Failed to update current SCC!");1130 1131 // If one of the invalidated SCCs had a cached proxy to a function1132 // analysis manager, we need to create a proxy in the new current SCC as1133 // the invalidated SCCs had their functions moved.1134 if (HasFunctionAnalysisProxy)1135 AM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, G).updateFAM(FAM);1136 1137 // Any analyses cached for this SCC are no longer precise as the shape1138 // has changed by introducing this cycle. However, we have taken care to1139 // update the proxies so it remains valide.1140 auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();1141 PA.preserve<FunctionAnalysisManagerCGSCCProxy>();1142 AM.invalidate(*C, PA);1143 }1144 auto NewSCCIndex = RC->find(*C) - RC->begin();1145 // If we have actually moved an SCC to be topologically "below" the current1146 // one due to merging, we will need to revisit the current SCC after1147 // visiting those moved SCCs.1148 //1149 // It is critical that we *do not* revisit the current SCC unless we1150 // actually move SCCs in the process of merging because otherwise we may1151 // form a cycle where an SCC is split apart, merged, split, merged and so1152 // on infinitely.1153 if (InitialSCCIndex < NewSCCIndex) {1154 // Put our current SCC back onto the worklist as we'll visit other SCCs1155 // that are now definitively ordered prior to the current one in the1156 // post-order sequence, and may end up observing more precise context to1157 // optimize the current SCC.1158 UR.CWorklist.insert(C);1159 LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist: " << *C1160 << "\n");1161 // Enqueue in reverse order as we pop off the back of the worklist.1162 for (SCC &MovedC : llvm::reverse(make_range(RC->begin() + InitialSCCIndex,1163 RC->begin() + NewSCCIndex))) {1164 UR.CWorklist.insert(&MovedC);1165 LLVM_DEBUG(dbgs() << "Enqueuing a newly earlier in post-order SCC: "1166 << MovedC << "\n");1167 }1168 }1169 }1170 1171 assert(!UR.InvalidatedSCCs.count(C) && "Invalidated the current SCC!");1172 assert(&C->getOuterRefSCC() == RC && "Current SCC not in current RefSCC!");1173 1174 // Record the current SCC for higher layers of the CGSCC pass manager now that1175 // all the updates have been applied.1176 if (C != &InitialC)1177 UR.UpdatedC = C;1178 1179 return *C;1180}1181 1182LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass(1183 LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,1184 CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR,1185 FunctionAnalysisManager &FAM) {1186 return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR, FAM,1187 /* FunctionPass */ true);1188}1189LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForCGSCCPass(1190 LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,1191 CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR,1192 FunctionAnalysisManager &FAM) {1193 return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR, FAM,1194 /* FunctionPass */ false);1195}1196