xref: /freebsd/contrib/llvm-project/llvm/lib/Analysis/CGSCCPassManager.cpp (revision 0d8fe2373503aeac48492f28073049a8bfa4feb5)
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-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "llvm/Analysis/CGSCCPassManager.h"
10 #include "llvm/ADT/ArrayRef.h"
11 #include "llvm/ADT/Optional.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/iterator_range.h"
17 #include "llvm/Analysis/LazyCallGraph.h"
18 #include "llvm/IR/Constant.h"
19 #include "llvm/IR/InstIterator.h"
20 #include "llvm/IR/Instruction.h"
21 #include "llvm/IR/PassManager.h"
22 #include "llvm/IR/PassManagerImpl.h"
23 #include "llvm/IR/ValueHandle.h"
24 #include "llvm/Support/Casting.h"
25 #include "llvm/Support/CommandLine.h"
26 #include "llvm/Support/Debug.h"
27 #include "llvm/Support/ErrorHandling.h"
28 #include "llvm/Support/TimeProfiler.h"
29 #include "llvm/Support/raw_ostream.h"
30 #include <algorithm>
31 #include <cassert>
32 #include <iterator>
33 
34 #define DEBUG_TYPE "cgscc"
35 
36 using namespace llvm;
37 
38 // Explicit template instantiations and specialization definitions for core
39 // template typedefs.
40 namespace llvm {
41 
42 static cl::opt<bool> AbortOnMaxDevirtIterationsReached(
43     "abort-on-max-devirt-iterations-reached",
44     cl::desc("Abort when the max iterations for devirtualization CGSCC repeat "
45              "pass is reached"));
46 
47 // Explicit instantiations for the core proxy templates.
48 template class AllAnalysesOn<LazyCallGraph::SCC>;
49 template class AnalysisManager<LazyCallGraph::SCC, LazyCallGraph &>;
50 template class PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager,
51                            LazyCallGraph &, CGSCCUpdateResult &>;
52 template class InnerAnalysisManagerProxy<CGSCCAnalysisManager, Module>;
53 template class OuterAnalysisManagerProxy<ModuleAnalysisManager,
54                                          LazyCallGraph::SCC, LazyCallGraph &>;
55 template class OuterAnalysisManagerProxy<CGSCCAnalysisManager, Function>;
56 
57 /// Explicitly specialize the pass manager run method to handle call graph
58 /// updates.
59 template <>
60 PreservedAnalyses
61 PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
62             CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC,
63                                       CGSCCAnalysisManager &AM,
64                                       LazyCallGraph &G, CGSCCUpdateResult &UR) {
65   // Request PassInstrumentation from analysis manager, will use it to run
66   // instrumenting callbacks for the passes later.
67   PassInstrumentation PI =
68       AM.getResult<PassInstrumentationAnalysis>(InitialC, G);
69 
70   PreservedAnalyses PA = PreservedAnalyses::all();
71 
72   if (DebugLogging)
73     dbgs() << "Starting CGSCC pass manager run.\n";
74 
75   // The SCC may be refined while we are running passes over it, so set up
76   // a pointer that we can update.
77   LazyCallGraph::SCC *C = &InitialC;
78 
79   // Get Function analysis manager from its proxy.
80   FunctionAnalysisManager &FAM =
81       AM.getCachedResult<FunctionAnalysisManagerCGSCCProxy>(*C)->getManager();
82 
83   for (auto &Pass : Passes) {
84     // Check the PassInstrumentation's BeforePass callbacks before running the
85     // pass, skip its execution completely if asked to (callback returns false).
86     if (!PI.runBeforePass(*Pass, *C))
87       continue;
88 
89     PreservedAnalyses PassPA;
90     {
91       TimeTraceScope TimeScope(Pass->name());
92       PassPA = Pass->run(*C, AM, G, UR);
93     }
94 
95     if (UR.InvalidatedSCCs.count(C))
96       PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass, PassPA);
97     else
98       PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
99 
100     // Update the SCC if necessary.
101     C = UR.UpdatedC ? UR.UpdatedC : C;
102     if (UR.UpdatedC) {
103       // If C is updated, also create a proxy and update FAM inside the result.
104       auto *ResultFAMCP =
105           &AM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, G);
106       ResultFAMCP->updateFAM(FAM);
107     }
108 
109     // If the CGSCC pass wasn't able to provide a valid updated SCC, the
110     // current SCC may simply need to be skipped if invalid.
111     if (UR.InvalidatedSCCs.count(C)) {
112       LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
113       break;
114     }
115     // Check that we didn't miss any update scenario.
116     assert(C->begin() != C->end() && "Cannot have an empty SCC!");
117 
118     // Update the analysis manager as each pass runs and potentially
119     // invalidates analyses.
120     AM.invalidate(*C, PassPA);
121 
122     // Finally, we intersect the final preserved analyses to compute the
123     // aggregate preserved set for this pass manager.
124     PA.intersect(std::move(PassPA));
125 
126     // FIXME: Historically, the pass managers all called the LLVM context's
127     // yield function here. We don't have a generic way to acquire the
128     // context and it isn't yet clear what the right pattern is for yielding
129     // in the new pass manager so it is currently omitted.
130     // ...getContext().yield();
131   }
132 
133   // Before we mark all of *this* SCC's analyses as preserved below, intersect
134   // this with the cross-SCC preserved analysis set. This is used to allow
135   // CGSCC passes to mutate ancestor SCCs and still trigger proper invalidation
136   // for them.
137   UR.CrossSCCPA.intersect(PA);
138 
139   // Invalidation was handled after each pass in the above loop for the current
140   // SCC. Therefore, the remaining analysis results in the AnalysisManager are
141   // preserved. We mark this with a set so that we don't need to inspect each
142   // one individually.
143   PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
144 
145   if (DebugLogging)
146     dbgs() << "Finished CGSCC pass manager run.\n";
147 
148   return PA;
149 }
150 
151 PreservedAnalyses
152 ModuleToPostOrderCGSCCPassAdaptor::run(Module &M, ModuleAnalysisManager &AM) {
153   // Setup the CGSCC analysis manager from its proxy.
154   CGSCCAnalysisManager &CGAM =
155       AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
156 
157   // Get the call graph for this module.
158   LazyCallGraph &CG = AM.getResult<LazyCallGraphAnalysis>(M);
159 
160   // Get Function analysis manager from its proxy.
161   FunctionAnalysisManager &FAM =
162       AM.getCachedResult<FunctionAnalysisManagerModuleProxy>(M)->getManager();
163 
164   // We keep worklists to allow us to push more work onto the pass manager as
165   // the passes are run.
166   SmallPriorityWorklist<LazyCallGraph::RefSCC *, 1> RCWorklist;
167   SmallPriorityWorklist<LazyCallGraph::SCC *, 1> CWorklist;
168 
169   // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
170   // iterating off the worklists.
171   SmallPtrSet<LazyCallGraph::RefSCC *, 4> InvalidRefSCCSet;
172   SmallPtrSet<LazyCallGraph::SCC *, 4> InvalidSCCSet;
173 
174   SmallDenseSet<std::pair<LazyCallGraph::Node *, LazyCallGraph::SCC *>, 4>
175       InlinedInternalEdges;
176 
177   CGSCCUpdateResult UR = {
178       RCWorklist, CWorklist, InvalidRefSCCSet,         InvalidSCCSet,
179       nullptr,    nullptr,   PreservedAnalyses::all(), InlinedInternalEdges,
180       {}};
181 
182   // Request PassInstrumentation from analysis manager, will use it to run
183   // instrumenting callbacks for the passes later.
184   PassInstrumentation PI = AM.getResult<PassInstrumentationAnalysis>(M);
185 
186   PreservedAnalyses PA = PreservedAnalyses::all();
187   CG.buildRefSCCs();
188   for (auto RCI = CG.postorder_ref_scc_begin(),
189             RCE = CG.postorder_ref_scc_end();
190        RCI != RCE;) {
191     assert(RCWorklist.empty() &&
192            "Should always start with an empty RefSCC worklist");
193     // The postorder_ref_sccs range we are walking is lazily constructed, so
194     // we only push the first one onto the worklist. The worklist allows us
195     // to capture *new* RefSCCs created during transformations.
196     //
197     // We really want to form RefSCCs lazily because that makes them cheaper
198     // to update as the program is simplified and allows us to have greater
199     // cache locality as forming a RefSCC touches all the parts of all the
200     // functions within that RefSCC.
201     //
202     // We also eagerly increment the iterator to the next position because
203     // the CGSCC passes below may delete the current RefSCC.
204     RCWorklist.insert(&*RCI++);
205 
206     do {
207       LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
208       if (InvalidRefSCCSet.count(RC)) {
209         LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
210         continue;
211       }
212 
213       assert(CWorklist.empty() &&
214              "Should always start with an empty SCC worklist");
215 
216       LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
217                         << "\n");
218 
219       // The top of the worklist may *also* be the same SCC we just ran over
220       // (and invalidated for). Keep track of that last SCC we processed due
221       // to SCC update to avoid redundant processing when an SCC is both just
222       // updated itself and at the top of the worklist.
223       LazyCallGraph::SCC *LastUpdatedC = nullptr;
224 
225       // Push the initial SCCs in reverse post-order as we'll pop off the
226       // back and so see this in post-order.
227       for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
228         CWorklist.insert(&C);
229 
230       do {
231         LazyCallGraph::SCC *C = CWorklist.pop_back_val();
232         // Due to call graph mutations, we may have invalid SCCs or SCCs from
233         // other RefSCCs in the worklist. The invalid ones are dead and the
234         // other RefSCCs should be queued above, so we just need to skip both
235         // scenarios here.
236         if (InvalidSCCSet.count(C)) {
237           LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
238           continue;
239         }
240         if (LastUpdatedC == C) {
241           LLVM_DEBUG(dbgs() << "Skipping redundant run on SCC: " << *C << "\n");
242           continue;
243         }
244         if (&C->getOuterRefSCC() != RC) {
245           LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
246                                "RefSCC...\n");
247           continue;
248         }
249 
250         // Ensure we can proxy analysis updates from the CGSCC analysis manager
251         // into the the Function analysis manager by getting a proxy here.
252         // This also needs to update the FunctionAnalysisManager, as this may be
253         // the first time we see this SCC.
254         CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(
255             FAM);
256 
257         // Each time we visit a new SCC pulled off the worklist,
258         // a transformation of a child SCC may have also modified this parent
259         // and invalidated analyses. So we invalidate using the update record's
260         // cross-SCC preserved set. This preserved set is intersected by any
261         // CGSCC pass that handles invalidation (primarily pass managers) prior
262         // to marking its SCC as preserved. That lets us track everything that
263         // might need invalidation across SCCs without excessive invalidations
264         // on a single SCC.
265         //
266         // This essentially allows SCC passes to freely invalidate analyses
267         // of any ancestor SCC. If this becomes detrimental to successfully
268         // caching analyses, we could force each SCC pass to manually
269         // invalidate the analyses for any SCCs other than themselves which
270         // are mutated. However, that seems to lose the robustness of the
271         // pass-manager driven invalidation scheme.
272         CGAM.invalidate(*C, UR.CrossSCCPA);
273 
274         do {
275           // Check that we didn't miss any update scenario.
276           assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
277           assert(C->begin() != C->end() && "Cannot have an empty SCC!");
278           assert(&C->getOuterRefSCC() == RC &&
279                  "Processing an SCC in a different RefSCC!");
280 
281           LastUpdatedC = UR.UpdatedC;
282           UR.UpdatedRC = nullptr;
283           UR.UpdatedC = nullptr;
284 
285           // Check the PassInstrumentation's BeforePass callbacks before
286           // running the pass, skip its execution completely if asked to
287           // (callback returns false).
288           if (!PI.runBeforePass<LazyCallGraph::SCC>(*Pass, *C))
289             continue;
290 
291           PreservedAnalyses PassPA;
292           {
293             TimeTraceScope TimeScope(Pass->name());
294             PassPA = Pass->run(*C, CGAM, CG, UR);
295           }
296 
297           if (UR.InvalidatedSCCs.count(C))
298             PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass, PassPA);
299           else
300             PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
301 
302           // Update the SCC and RefSCC if necessary.
303           C = UR.UpdatedC ? UR.UpdatedC : C;
304           RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
305 
306           if (UR.UpdatedC) {
307             // If we're updating the SCC, also update the FAM inside the proxy's
308             // result.
309             CGAM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, CG).updateFAM(
310                 FAM);
311           }
312 
313           // If the CGSCC pass wasn't able to provide a valid updated SCC,
314           // the current SCC may simply need to be skipped if invalid.
315           if (UR.InvalidatedSCCs.count(C)) {
316             LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
317             break;
318           }
319           // Check that we didn't miss any update scenario.
320           assert(C->begin() != C->end() && "Cannot have an empty SCC!");
321 
322           // We handle invalidating the CGSCC analysis manager's information
323           // for the (potentially updated) SCC here. Note that any other SCCs
324           // whose structure has changed should have been invalidated by
325           // whatever was updating the call graph. This SCC gets invalidated
326           // late as it contains the nodes that were actively being
327           // processed.
328           CGAM.invalidate(*C, PassPA);
329 
330           // Then intersect the preserved set so that invalidation of module
331           // analyses will eventually occur when the module pass completes.
332           // Also intersect with the cross-SCC preserved set to capture any
333           // cross-SCC invalidation.
334           UR.CrossSCCPA.intersect(PassPA);
335           PA.intersect(std::move(PassPA));
336 
337           // The pass may have restructured the call graph and refined the
338           // current SCC and/or RefSCC. We need to update our current SCC and
339           // RefSCC pointers to follow these. Also, when the current SCC is
340           // refined, re-run the SCC pass over the newly refined SCC in order
341           // to observe the most precise SCC model available. This inherently
342           // cannot cycle excessively as it only happens when we split SCCs
343           // apart, at most converging on a DAG of single nodes.
344           // FIXME: If we ever start having RefSCC passes, we'll want to
345           // iterate there too.
346           if (UR.UpdatedC)
347             LLVM_DEBUG(dbgs()
348                        << "Re-running SCC passes after a refinement of the "
349                           "current SCC: "
350                        << *UR.UpdatedC << "\n");
351 
352           // Note that both `C` and `RC` may at this point refer to deleted,
353           // invalid SCC and RefSCCs respectively. But we will short circuit
354           // the processing when we check them in the loop above.
355         } while (UR.UpdatedC);
356       } while (!CWorklist.empty());
357 
358       // We only need to keep internal inlined edge information within
359       // a RefSCC, clear it to save on space and let the next time we visit
360       // any of these functions have a fresh start.
361       InlinedInternalEdges.clear();
362     } while (!RCWorklist.empty());
363   }
364 
365   // By definition we preserve the call garph, all SCC analyses, and the
366   // analysis proxies by handling them above and in any nested pass managers.
367   PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
368   PA.preserve<LazyCallGraphAnalysis>();
369   PA.preserve<CGSCCAnalysisManagerModuleProxy>();
370   PA.preserve<FunctionAnalysisManagerModuleProxy>();
371   return PA;
372 }
373 
374 PreservedAnalyses DevirtSCCRepeatedPass::run(LazyCallGraph::SCC &InitialC,
375                                              CGSCCAnalysisManager &AM,
376                                              LazyCallGraph &CG,
377                                              CGSCCUpdateResult &UR) {
378   PreservedAnalyses PA = PreservedAnalyses::all();
379   PassInstrumentation PI =
380       AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
381 
382   // The SCC may be refined while we are running passes over it, so set up
383   // a pointer that we can update.
384   LazyCallGraph::SCC *C = &InitialC;
385 
386   // Struct to track the counts of direct and indirect calls in each function
387   // of the SCC.
388   struct CallCount {
389     int Direct;
390     int Indirect;
391   };
392 
393   // Put value handles on all of the indirect calls and return the number of
394   // direct calls for each function in the SCC.
395   auto ScanSCC = [](LazyCallGraph::SCC &C,
396                     SmallMapVector<Value *, WeakTrackingVH, 16> &CallHandles) {
397     assert(CallHandles.empty() && "Must start with a clear set of handles.");
398 
399     SmallDenseMap<Function *, CallCount> CallCounts;
400     CallCount CountLocal = {0, 0};
401     for (LazyCallGraph::Node &N : C) {
402       CallCount &Count =
403           CallCounts.insert(std::make_pair(&N.getFunction(), CountLocal))
404               .first->second;
405       for (Instruction &I : instructions(N.getFunction()))
406         if (auto *CB = dyn_cast<CallBase>(&I)) {
407           if (CB->getCalledFunction()) {
408             ++Count.Direct;
409           } else {
410             ++Count.Indirect;
411             CallHandles.insert({CB, WeakTrackingVH(CB)});
412           }
413         }
414     }
415 
416     return CallCounts;
417   };
418 
419   UR.IndirectVHs.clear();
420   // Populate the initial call handles and get the initial call counts.
421   auto CallCounts = ScanSCC(*C, UR.IndirectVHs);
422 
423   for (int Iteration = 0;; ++Iteration) {
424     if (!PI.runBeforePass<LazyCallGraph::SCC>(*Pass, *C))
425       continue;
426 
427     PreservedAnalyses PassPA = Pass->run(*C, AM, CG, UR);
428 
429     if (UR.InvalidatedSCCs.count(C))
430       PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass, PassPA);
431     else
432       PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
433 
434     // If the SCC structure has changed, bail immediately and let the outer
435     // CGSCC layer handle any iteration to reflect the refined structure.
436     if (UR.UpdatedC && UR.UpdatedC != C) {
437       PA.intersect(std::move(PassPA));
438       break;
439     }
440 
441     // Check that we didn't miss any update scenario.
442     assert(!UR.InvalidatedSCCs.count(C) && "Processing an invalid SCC!");
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 direct
459     // calls remain. If we decide to iterate, this also sets up the input to
460     // 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 we
465     // have decreased the number of indirect calls and increased the number
466     // of direct calls for any function in the SCC. This can be fooled by all
467     // manner of transformations such as DCE and other things, but seems to
468     // work well in practice.
469     if (!Devirt)
470       // Iterate over the keys in NewCallCounts, if Function also exists in
471       // 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       PA.intersect(std::move(PassPA));
487       break;
488     }
489 
490     // Otherwise, if we've already hit our max, we're done.
491     if (Iteration >= MaxIterations) {
492       if (AbortOnMaxDevirtIterationsReached)
493         report_fatal_error("Max devirtualization iterations reached");
494       LLVM_DEBUG(
495           dbgs() << "Found another devirtualization after hitting the max "
496                     "number of repetitions ("
497                  << MaxIterations << ") on SCC: " << *C << "\n");
498       PA.intersect(std::move(PassPA));
499       break;
500     }
501 
502     LLVM_DEBUG(
503         dbgs() << "Repeating an SCC pass after finding a devirtualization in: "
504                << *C << "\n");
505 
506     // Move over the new call counts in preparation for iterating.
507     CallCounts = std::move(NewCallCounts);
508 
509     // Update the analysis manager with each run and intersect the total set
510     // of preserved analyses so we're ready to iterate.
511     AM.invalidate(*C, PassPA);
512 
513     PA.intersect(std::move(PassPA));
514   }
515 
516   // Note that we don't add any preserved entries here unlike a more normal
517   // "pass manager" because we only handle invalidation *between* iterations,
518   // not after the last iteration.
519   return PA;
520 }
521 
522 PreservedAnalyses CGSCCToFunctionPassAdaptor::run(LazyCallGraph::SCC &C,
523                                                   CGSCCAnalysisManager &AM,
524                                                   LazyCallGraph &CG,
525                                                   CGSCCUpdateResult &UR) {
526   // Setup the function analysis manager from its proxy.
527   FunctionAnalysisManager &FAM =
528       AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
529 
530   SmallVector<LazyCallGraph::Node *, 4> Nodes;
531   for (LazyCallGraph::Node &N : C)
532     Nodes.push_back(&N);
533 
534   // The SCC may get split while we are optimizing functions due to deleting
535   // edges. If this happens, the current SCC can shift, so keep track of
536   // a pointer we can overwrite.
537   LazyCallGraph::SCC *CurrentC = &C;
538 
539   LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C << "\n");
540 
541   PreservedAnalyses PA = PreservedAnalyses::all();
542   for (LazyCallGraph::Node *N : Nodes) {
543     // Skip nodes from other SCCs. These may have been split out during
544     // processing. We'll eventually visit those SCCs and pick up the nodes
545     // there.
546     if (CG.lookupSCC(*N) != CurrentC)
547       continue;
548 
549     Function &F = N->getFunction();
550 
551     PassInstrumentation PI = FAM.getResult<PassInstrumentationAnalysis>(F);
552     if (!PI.runBeforePass<Function>(*Pass, F))
553       continue;
554 
555     PreservedAnalyses PassPA;
556     {
557       TimeTraceScope TimeScope(Pass->name());
558       PassPA = Pass->run(F, FAM);
559     }
560 
561     PI.runAfterPass<Function>(*Pass, F, PassPA);
562 
563     // We know that the function pass couldn't have invalidated any other
564     // function's analyses (that's the contract of a function pass), so
565     // directly handle the function analysis manager's invalidation here.
566     FAM.invalidate(F, PassPA);
567 
568     // Then intersect the preserved set so that invalidation of module
569     // analyses will eventually occur when the module pass completes.
570     PA.intersect(std::move(PassPA));
571 
572     // If the call graph hasn't been preserved, update it based on this
573     // function pass. This may also update the current SCC to point to
574     // a smaller, more refined SCC.
575     auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
576     if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
577       CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
578                                                             AM, UR, FAM);
579       assert(CG.lookupSCC(*N) == CurrentC &&
580              "Current SCC not updated to the SCC containing the current node!");
581     }
582   }
583 
584   // By definition we preserve the proxy. And we preserve all analyses on
585   // Functions. This precludes *any* invalidation of function analyses by the
586   // proxy, but that's OK because we've taken care to invalidate analyses in
587   // the function analysis manager incrementally above.
588   PA.preserveSet<AllAnalysesOn<Function>>();
589   PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
590 
591   // We've also ensured that we updated the call graph along the way.
592   PA.preserve<LazyCallGraphAnalysis>();
593 
594   return PA;
595 }
596 
597 bool CGSCCAnalysisManagerModuleProxy::Result::invalidate(
598     Module &M, const PreservedAnalyses &PA,
599     ModuleAnalysisManager::Invalidator &Inv) {
600   // If literally everything is preserved, we're done.
601   if (PA.areAllPreserved())
602     return false; // This is still a valid proxy.
603 
604   // If this proxy or the call graph is going to be invalidated, we also need
605   // to clear all the keys coming from that analysis.
606   //
607   // We also directly invalidate the FAM's module proxy if necessary, and if
608   // that proxy isn't preserved we can't preserve this proxy either. We rely on
609   // it to handle module -> function analysis invalidation in the face of
610   // structural changes and so if it's unavailable we conservatively clear the
611   // entire SCC layer as well rather than trying to do invalidation ourselves.
612   auto PAC = PA.getChecker<CGSCCAnalysisManagerModuleProxy>();
613   if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>()) ||
614       Inv.invalidate<LazyCallGraphAnalysis>(M, PA) ||
615       Inv.invalidate<FunctionAnalysisManagerModuleProxy>(M, PA)) {
616     InnerAM->clear();
617 
618     // And the proxy itself should be marked as invalid so that we can observe
619     // the new call graph. This isn't strictly necessary because we cheat
620     // above, but is still useful.
621     return true;
622   }
623 
624   // Directly check if the relevant set is preserved so we can short circuit
625   // invalidating SCCs below.
626   bool AreSCCAnalysesPreserved =
627       PA.allAnalysesInSetPreserved<AllAnalysesOn<LazyCallGraph::SCC>>();
628 
629   // Ok, we have a graph, so we can propagate the invalidation down into it.
630   G->buildRefSCCs();
631   for (auto &RC : G->postorder_ref_sccs())
632     for (auto &C : RC) {
633       Optional<PreservedAnalyses> InnerPA;
634 
635       // Check to see whether the preserved set needs to be adjusted based on
636       // module-level analysis invalidation triggering deferred invalidation
637       // for this SCC.
638       if (auto *OuterProxy =
639               InnerAM->getCachedResult<ModuleAnalysisManagerCGSCCProxy>(C))
640         for (const auto &OuterInvalidationPair :
641              OuterProxy->getOuterInvalidations()) {
642           AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
643           const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
644           if (Inv.invalidate(OuterAnalysisID, M, PA)) {
645             if (!InnerPA)
646               InnerPA = PA;
647             for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
648               InnerPA->abandon(InnerAnalysisID);
649           }
650         }
651 
652       // Check if we needed a custom PA set. If so we'll need to run the inner
653       // invalidation.
654       if (InnerPA) {
655         InnerAM->invalidate(C, *InnerPA);
656         continue;
657       }
658 
659       // Otherwise we only need to do invalidation if the original PA set didn't
660       // preserve all SCC analyses.
661       if (!AreSCCAnalysesPreserved)
662         InnerAM->invalidate(C, PA);
663     }
664 
665   // Return false to indicate that this result is still a valid proxy.
666   return false;
667 }
668 
669 template <>
670 CGSCCAnalysisManagerModuleProxy::Result
671 CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM) {
672   // Force the Function analysis manager to also be available so that it can
673   // be accessed in an SCC analysis and proxied onward to function passes.
674   // FIXME: It is pretty awkward to just drop the result here and assert that
675   // we can find it again later.
676   (void)AM.getResult<FunctionAnalysisManagerModuleProxy>(M);
677 
678   return Result(*InnerAM, AM.getResult<LazyCallGraphAnalysis>(M));
679 }
680 
681 AnalysisKey FunctionAnalysisManagerCGSCCProxy::Key;
682 
683 FunctionAnalysisManagerCGSCCProxy::Result
684 FunctionAnalysisManagerCGSCCProxy::run(LazyCallGraph::SCC &C,
685                                        CGSCCAnalysisManager &AM,
686                                        LazyCallGraph &CG) {
687   // Note: unconditionally getting checking that the proxy exists may get it at
688   // this point. There are cases when this is being run unnecessarily, but
689   // it is cheap and having the assertion in place is more valuable.
690   auto &MAMProxy = AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG);
691   Module &M = *C.begin()->getFunction().getParent();
692   bool ProxyExists =
693       MAMProxy.cachedResultExists<FunctionAnalysisManagerModuleProxy>(M);
694   assert(ProxyExists &&
695          "The CGSCC pass manager requires that the FAM module proxy is run "
696          "on the module prior to entering the CGSCC walk");
697   (void)ProxyExists;
698 
699   // We just return an empty result. The caller will use the updateFAM interface
700   // to correctly register the relevant FunctionAnalysisManager based on the
701   // context in which this proxy is run.
702   return Result();
703 }
704 
705 bool FunctionAnalysisManagerCGSCCProxy::Result::invalidate(
706     LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
707     CGSCCAnalysisManager::Invalidator &Inv) {
708   // If literally everything is preserved, we're done.
709   if (PA.areAllPreserved())
710     return false; // This is still a valid proxy.
711 
712   // All updates to preserve valid results are done below, so we don't need to
713   // invalidate this proxy.
714   //
715   // Note that in order to preserve this proxy, a module pass must ensure that
716   // the FAM has been completely updated to handle the deletion of functions.
717   // Specifically, any FAM-cached results for those functions need to have been
718   // forcibly cleared. When preserved, this proxy will only invalidate results
719   // cached on functions *still in the module* at the end of the module pass.
720   auto PAC = PA.getChecker<FunctionAnalysisManagerCGSCCProxy>();
721   if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>()) {
722     for (LazyCallGraph::Node &N : C)
723       FAM->clear(N.getFunction(), N.getFunction().getName());
724 
725     return false;
726   }
727 
728   // Directly check if the relevant set is preserved.
729   bool AreFunctionAnalysesPreserved =
730       PA.allAnalysesInSetPreserved<AllAnalysesOn<Function>>();
731 
732   // Now walk all the functions to see if any inner analysis invalidation is
733   // necessary.
734   for (LazyCallGraph::Node &N : C) {
735     Function &F = N.getFunction();
736     Optional<PreservedAnalyses> FunctionPA;
737 
738     // Check to see whether the preserved set needs to be pruned based on
739     // SCC-level analysis invalidation that triggers deferred invalidation
740     // registered with the outer analysis manager proxy for this function.
741     if (auto *OuterProxy =
742             FAM->getCachedResult<CGSCCAnalysisManagerFunctionProxy>(F))
743       for (const auto &OuterInvalidationPair :
744            OuterProxy->getOuterInvalidations()) {
745         AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
746         const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
747         if (Inv.invalidate(OuterAnalysisID, C, PA)) {
748           if (!FunctionPA)
749             FunctionPA = PA;
750           for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
751             FunctionPA->abandon(InnerAnalysisID);
752         }
753       }
754 
755     // Check if we needed a custom PA set, and if so we'll need to run the
756     // inner invalidation.
757     if (FunctionPA) {
758       FAM->invalidate(F, *FunctionPA);
759       continue;
760     }
761 
762     // Otherwise we only need to do invalidation if the original PA set didn't
763     // preserve all function analyses.
764     if (!AreFunctionAnalysesPreserved)
765       FAM->invalidate(F, PA);
766   }
767 
768   // Return false to indicate that this result is still a valid proxy.
769   return false;
770 }
771 
772 } // end namespace llvm
773 
774 /// When a new SCC is created for the graph we first update the
775 /// FunctionAnalysisManager in the Proxy's result.
776 /// As there might be function analysis results cached for the functions now in
777 /// that SCC, two forms of  updates are required.
778 ///
779 /// First, a proxy from the SCC to the FunctionAnalysisManager needs to be
780 /// created so that any subsequent invalidation events to the SCC are
781 /// propagated to the function analysis results cached for functions within it.
782 ///
783 /// Second, if any of the functions within the SCC have analysis results with
784 /// outer analysis dependencies, then those dependencies would point to the
785 /// *wrong* SCC's analysis result. We forcibly invalidate the necessary
786 /// function analyses so that they don't retain stale handles.
787 static void updateNewSCCFunctionAnalyses(LazyCallGraph::SCC &C,
788                                          LazyCallGraph &G,
789                                          CGSCCAnalysisManager &AM,
790                                          FunctionAnalysisManager &FAM) {
791   AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, G).updateFAM(FAM);
792 
793   // Now walk the functions in this SCC and invalidate any function analysis
794   // results that might have outer dependencies on an SCC analysis.
795   for (LazyCallGraph::Node &N : C) {
796     Function &F = N.getFunction();
797 
798     auto *OuterProxy =
799         FAM.getCachedResult<CGSCCAnalysisManagerFunctionProxy>(F);
800     if (!OuterProxy)
801       // No outer analyses were queried, nothing to do.
802       continue;
803 
804     // Forcibly abandon all the inner analyses with dependencies, but
805     // invalidate nothing else.
806     auto PA = PreservedAnalyses::all();
807     for (const auto &OuterInvalidationPair :
808          OuterProxy->getOuterInvalidations()) {
809       const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
810       for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
811         PA.abandon(InnerAnalysisID);
812     }
813 
814     // Now invalidate anything we found.
815     FAM.invalidate(F, PA);
816   }
817 }
818 
819 /// Helper function to update both the \c CGSCCAnalysisManager \p AM and the \c
820 /// CGSCCPassManager's \c CGSCCUpdateResult \p UR based on a range of newly
821 /// added SCCs.
822 ///
823 /// The range of new SCCs must be in postorder already. The SCC they were split
824 /// out of must be provided as \p C. The current node being mutated and
825 /// triggering updates must be passed as \p N.
826 ///
827 /// This function returns the SCC containing \p N. This will be either \p C if
828 /// no new SCCs have been split out, or it will be the new SCC containing \p N.
829 template <typename SCCRangeT>
830 static LazyCallGraph::SCC *
831 incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G,
832                        LazyCallGraph::Node &N, LazyCallGraph::SCC *C,
833                        CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR) {
834   using SCC = LazyCallGraph::SCC;
835 
836   if (NewSCCRange.empty())
837     return C;
838 
839   // Add the current SCC to the worklist as its shape has changed.
840   UR.CWorklist.insert(C);
841   LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist:" << *C
842                     << "\n");
843 
844   SCC *OldC = C;
845 
846   // Update the current SCC. Note that if we have new SCCs, this must actually
847   // change the SCC.
848   assert(C != &*NewSCCRange.begin() &&
849          "Cannot insert new SCCs without changing current SCC!");
850   C = &*NewSCCRange.begin();
851   assert(G.lookupSCC(N) == C && "Failed to update current SCC!");
852 
853   // If we had a cached FAM proxy originally, we will want to create more of
854   // them for each SCC that was split off.
855   FunctionAnalysisManager *FAM = nullptr;
856   if (auto *FAMProxy =
857           AM.getCachedResult<FunctionAnalysisManagerCGSCCProxy>(*OldC))
858     FAM = &FAMProxy->getManager();
859 
860   // We need to propagate an invalidation call to all but the newly current SCC
861   // because the outer pass manager won't do that for us after splitting them.
862   // FIXME: We should accept a PreservedAnalysis from the CG updater so that if
863   // there are preserved analysis we can avoid invalidating them here for
864   // split-off SCCs.
865   // We know however that this will preserve any FAM proxy so go ahead and mark
866   // that.
867   PreservedAnalyses PA;
868   PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
869   AM.invalidate(*OldC, PA);
870 
871   // Ensure the now-current SCC's function analyses are updated.
872   if (FAM)
873     updateNewSCCFunctionAnalyses(*C, G, AM, *FAM);
874 
875   for (SCC &NewC : llvm::reverse(make_range(std::next(NewSCCRange.begin()),
876                                             NewSCCRange.end()))) {
877     assert(C != &NewC && "No need to re-visit the current SCC!");
878     assert(OldC != &NewC && "Already handled the original SCC!");
879     UR.CWorklist.insert(&NewC);
880     LLVM_DEBUG(dbgs() << "Enqueuing a newly formed SCC:" << NewC << "\n");
881 
882     // Ensure new SCCs' function analyses are updated.
883     if (FAM)
884       updateNewSCCFunctionAnalyses(NewC, G, AM, *FAM);
885 
886     // Also propagate a normal invalidation to the new SCC as only the current
887     // will get one from the pass manager infrastructure.
888     AM.invalidate(NewC, PA);
889   }
890   return C;
891 }
892 
893 static LazyCallGraph::SCC &updateCGAndAnalysisManagerForPass(
894     LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,
895     CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR,
896     FunctionAnalysisManager &FAM, bool FunctionPass) {
897   using Node = LazyCallGraph::Node;
898   using Edge = LazyCallGraph::Edge;
899   using SCC = LazyCallGraph::SCC;
900   using RefSCC = LazyCallGraph::RefSCC;
901 
902   RefSCC &InitialRC = InitialC.getOuterRefSCC();
903   SCC *C = &InitialC;
904   RefSCC *RC = &InitialRC;
905   Function &F = N.getFunction();
906 
907   // Walk the function body and build up the set of retained, promoted, and
908   // demoted edges.
909   SmallVector<Constant *, 16> Worklist;
910   SmallPtrSet<Constant *, 16> Visited;
911   SmallPtrSet<Node *, 16> RetainedEdges;
912   SmallSetVector<Node *, 4> PromotedRefTargets;
913   SmallSetVector<Node *, 4> DemotedCallTargets;
914   SmallSetVector<Node *, 4> NewCallEdges;
915   SmallSetVector<Node *, 4> NewRefEdges;
916 
917   // First walk the function and handle all called functions. We do this first
918   // because if there is a single call edge, whether there are ref edges is
919   // irrelevant.
920   for (Instruction &I : instructions(F)) {
921     if (auto *CB = dyn_cast<CallBase>(&I)) {
922       if (Function *Callee = CB->getCalledFunction()) {
923         if (Visited.insert(Callee).second && !Callee->isDeclaration()) {
924           Node *CalleeN = G.lookup(*Callee);
925           assert(CalleeN &&
926                  "Visited function should already have an associated node");
927           Edge *E = N->lookup(*CalleeN);
928           assert((E || !FunctionPass) &&
929                  "No function transformations should introduce *new* "
930                  "call edges! Any new calls should be modeled as "
931                  "promoted existing ref edges!");
932           bool Inserted = RetainedEdges.insert(CalleeN).second;
933           (void)Inserted;
934           assert(Inserted && "We should never visit a function twice.");
935           if (!E)
936             NewCallEdges.insert(CalleeN);
937           else if (!E->isCall())
938             PromotedRefTargets.insert(CalleeN);
939         }
940       } else {
941         // We can miss devirtualization if an indirect call is created then
942         // promoted before updateCGAndAnalysisManagerForPass runs.
943         auto *Entry = UR.IndirectVHs.find(CB);
944         if (Entry == UR.IndirectVHs.end())
945           UR.IndirectVHs.insert({CB, WeakTrackingVH(CB)});
946         else if (!Entry->second)
947           Entry->second = WeakTrackingVH(CB);
948       }
949     }
950   }
951 
952   // Now walk all references.
953   for (Instruction &I : instructions(F))
954     for (Value *Op : I.operand_values())
955       if (auto *OpC = dyn_cast<Constant>(Op))
956         if (Visited.insert(OpC).second)
957           Worklist.push_back(OpC);
958 
959   auto VisitRef = [&](Function &Referee) {
960     Node *RefereeN = G.lookup(Referee);
961     assert(RefereeN &&
962            "Visited function should already have an associated node");
963     Edge *E = N->lookup(*RefereeN);
964     assert((E || !FunctionPass) &&
965            "No function transformations should introduce *new* ref "
966            "edges! Any new ref edges would require IPO which "
967            "function passes aren't allowed to do!");
968     bool Inserted = RetainedEdges.insert(RefereeN).second;
969     (void)Inserted;
970     assert(Inserted && "We should never visit a function twice.");
971     if (!E)
972       NewRefEdges.insert(RefereeN);
973     else if (E->isCall())
974       DemotedCallTargets.insert(RefereeN);
975   };
976   LazyCallGraph::visitReferences(Worklist, Visited, VisitRef);
977 
978   // Handle new ref edges.
979   for (Node *RefTarget : NewRefEdges) {
980     SCC &TargetC = *G.lookupSCC(*RefTarget);
981     RefSCC &TargetRC = TargetC.getOuterRefSCC();
982     (void)TargetRC;
983     // TODO: This only allows trivial edges to be added for now.
984     assert((RC == &TargetRC ||
985            RC->isAncestorOf(TargetRC)) && "New ref edge is not trivial!");
986     RC->insertTrivialRefEdge(N, *RefTarget);
987   }
988 
989   // Handle new call edges.
990   for (Node *CallTarget : NewCallEdges) {
991     SCC &TargetC = *G.lookupSCC(*CallTarget);
992     RefSCC &TargetRC = TargetC.getOuterRefSCC();
993     (void)TargetRC;
994     // TODO: This only allows trivial edges to be added for now.
995     assert((RC == &TargetRC ||
996            RC->isAncestorOf(TargetRC)) && "New call edge is not trivial!");
997     // Add a trivial ref edge to be promoted later on alongside
998     // PromotedRefTargets.
999     RC->insertTrivialRefEdge(N, *CallTarget);
1000   }
1001 
1002   // Include synthetic reference edges to known, defined lib functions.
1003   for (auto *LibFn : G.getLibFunctions())
1004     // While the list of lib functions doesn't have repeats, don't re-visit
1005     // anything handled above.
1006     if (!Visited.count(LibFn))
1007       VisitRef(*LibFn);
1008 
1009   // First remove all of the edges that are no longer present in this function.
1010   // The first step makes these edges uniformly ref edges and accumulates them
1011   // into a separate data structure so removal doesn't invalidate anything.
1012   SmallVector<Node *, 4> DeadTargets;
1013   for (Edge &E : *N) {
1014     if (RetainedEdges.count(&E.getNode()))
1015       continue;
1016 
1017     SCC &TargetC = *G.lookupSCC(E.getNode());
1018     RefSCC &TargetRC = TargetC.getOuterRefSCC();
1019     if (&TargetRC == RC && E.isCall()) {
1020       if (C != &TargetC) {
1021         // For separate SCCs this is trivial.
1022         RC->switchTrivialInternalEdgeToRef(N, E.getNode());
1023       } else {
1024         // Now update the call graph.
1025         C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, E.getNode()),
1026                                    G, N, C, AM, UR);
1027       }
1028     }
1029 
1030     // Now that this is ready for actual removal, put it into our list.
1031     DeadTargets.push_back(&E.getNode());
1032   }
1033   // Remove the easy cases quickly and actually pull them out of our list.
1034   llvm::erase_if(DeadTargets, [&](Node *TargetN) {
1035     SCC &TargetC = *G.lookupSCC(*TargetN);
1036     RefSCC &TargetRC = TargetC.getOuterRefSCC();
1037 
1038     // We can't trivially remove internal targets, so skip
1039     // those.
1040     if (&TargetRC == RC)
1041       return false;
1042 
1043     RC->removeOutgoingEdge(N, *TargetN);
1044     LLVM_DEBUG(dbgs() << "Deleting outgoing edge from '" << N << "' to '"
1045                       << TargetN << "'\n");
1046     return true;
1047   });
1048 
1049   // Now do a batch removal of the internal ref edges left.
1050   auto NewRefSCCs = RC->removeInternalRefEdge(N, DeadTargets);
1051   if (!NewRefSCCs.empty()) {
1052     // The old RefSCC is dead, mark it as such.
1053     UR.InvalidatedRefSCCs.insert(RC);
1054 
1055     // Note that we don't bother to invalidate analyses as ref-edge
1056     // connectivity is not really observable in any way and is intended
1057     // exclusively to be used for ordering of transforms rather than for
1058     // analysis conclusions.
1059 
1060     // Update RC to the "bottom".
1061     assert(G.lookupSCC(N) == C && "Changed the SCC when splitting RefSCCs!");
1062     RC = &C->getOuterRefSCC();
1063     assert(G.lookupRefSCC(N) == RC && "Failed to update current RefSCC!");
1064 
1065     // The RC worklist is in reverse postorder, so we enqueue the new ones in
1066     // RPO except for the one which contains the source node as that is the
1067     // "bottom" we will continue processing in the bottom-up walk.
1068     assert(NewRefSCCs.front() == RC &&
1069            "New current RefSCC not first in the returned list!");
1070     for (RefSCC *NewRC : llvm::reverse(make_range(std::next(NewRefSCCs.begin()),
1071                                                   NewRefSCCs.end()))) {
1072       assert(NewRC != RC && "Should not encounter the current RefSCC further "
1073                             "in the postorder list of new RefSCCs.");
1074       UR.RCWorklist.insert(NewRC);
1075       LLVM_DEBUG(dbgs() << "Enqueuing a new RefSCC in the update worklist: "
1076                         << *NewRC << "\n");
1077     }
1078   }
1079 
1080   // Next demote all the call edges that are now ref edges. This helps make
1081   // the SCCs small which should minimize the work below as we don't want to
1082   // form cycles that this would break.
1083   for (Node *RefTarget : DemotedCallTargets) {
1084     SCC &TargetC = *G.lookupSCC(*RefTarget);
1085     RefSCC &TargetRC = TargetC.getOuterRefSCC();
1086 
1087     // The easy case is when the target RefSCC is not this RefSCC. This is
1088     // only supported when the target RefSCC is a child of this RefSCC.
1089     if (&TargetRC != RC) {
1090       assert(RC->isAncestorOf(TargetRC) &&
1091              "Cannot potentially form RefSCC cycles here!");
1092       RC->switchOutgoingEdgeToRef(N, *RefTarget);
1093       LLVM_DEBUG(dbgs() << "Switch outgoing call edge to a ref edge from '" << N
1094                         << "' to '" << *RefTarget << "'\n");
1095       continue;
1096     }
1097 
1098     // We are switching an internal call edge to a ref edge. This may split up
1099     // some SCCs.
1100     if (C != &TargetC) {
1101       // For separate SCCs this is trivial.
1102       RC->switchTrivialInternalEdgeToRef(N, *RefTarget);
1103       continue;
1104     }
1105 
1106     // Now update the call graph.
1107     C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, *RefTarget), G, N,
1108                                C, AM, UR);
1109   }
1110 
1111   // We added a ref edge earlier for new call edges, promote those to call edges
1112   // alongside PromotedRefTargets.
1113   for (Node *E : NewCallEdges)
1114     PromotedRefTargets.insert(E);
1115 
1116   // Now promote ref edges into call edges.
1117   for (Node *CallTarget : PromotedRefTargets) {
1118     SCC &TargetC = *G.lookupSCC(*CallTarget);
1119     RefSCC &TargetRC = TargetC.getOuterRefSCC();
1120 
1121     // The easy case is when the target RefSCC is not this RefSCC. This is
1122     // only supported when the target RefSCC is a child of this RefSCC.
1123     if (&TargetRC != RC) {
1124       assert(RC->isAncestorOf(TargetRC) &&
1125              "Cannot potentially form RefSCC cycles here!");
1126       RC->switchOutgoingEdgeToCall(N, *CallTarget);
1127       LLVM_DEBUG(dbgs() << "Switch outgoing ref edge to a call edge from '" << N
1128                         << "' to '" << *CallTarget << "'\n");
1129       continue;
1130     }
1131     LLVM_DEBUG(dbgs() << "Switch an internal ref edge to a call edge from '"
1132                       << N << "' to '" << *CallTarget << "'\n");
1133 
1134     // Otherwise we are switching an internal ref edge to a call edge. This
1135     // may merge away some SCCs, and we add those to the UpdateResult. We also
1136     // need to make sure to update the worklist in the event SCCs have moved
1137     // before the current one in the post-order sequence
1138     bool HasFunctionAnalysisProxy = false;
1139     auto InitialSCCIndex = RC->find(*C) - RC->begin();
1140     bool FormedCycle = RC->switchInternalEdgeToCall(
1141         N, *CallTarget, [&](ArrayRef<SCC *> MergedSCCs) {
1142           for (SCC *MergedC : MergedSCCs) {
1143             assert(MergedC != &TargetC && "Cannot merge away the target SCC!");
1144 
1145             HasFunctionAnalysisProxy |=
1146                 AM.getCachedResult<FunctionAnalysisManagerCGSCCProxy>(
1147                     *MergedC) != nullptr;
1148 
1149             // Mark that this SCC will no longer be valid.
1150             UR.InvalidatedSCCs.insert(MergedC);
1151 
1152             // FIXME: We should really do a 'clear' here to forcibly release
1153             // memory, but we don't have a good way of doing that and
1154             // preserving the function analyses.
1155             auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
1156             PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1157             AM.invalidate(*MergedC, PA);
1158           }
1159         });
1160 
1161     // If we formed a cycle by creating this call, we need to update more data
1162     // structures.
1163     if (FormedCycle) {
1164       C = &TargetC;
1165       assert(G.lookupSCC(N) == C && "Failed to update current SCC!");
1166 
1167       // If one of the invalidated SCCs had a cached proxy to a function
1168       // analysis manager, we need to create a proxy in the new current SCC as
1169       // the invalidated SCCs had their functions moved.
1170       if (HasFunctionAnalysisProxy)
1171         AM.getResult<FunctionAnalysisManagerCGSCCProxy>(*C, G).updateFAM(FAM);
1172 
1173       // Any analyses cached for this SCC are no longer precise as the shape
1174       // has changed by introducing this cycle. However, we have taken care to
1175       // update the proxies so it remains valide.
1176       auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
1177       PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1178       AM.invalidate(*C, PA);
1179     }
1180     auto NewSCCIndex = RC->find(*C) - RC->begin();
1181     // If we have actually moved an SCC to be topologically "below" the current
1182     // one due to merging, we will need to revisit the current SCC after
1183     // visiting those moved SCCs.
1184     //
1185     // It is critical that we *do not* revisit the current SCC unless we
1186     // actually move SCCs in the process of merging because otherwise we may
1187     // form a cycle where an SCC is split apart, merged, split, merged and so
1188     // on infinitely.
1189     if (InitialSCCIndex < NewSCCIndex) {
1190       // Put our current SCC back onto the worklist as we'll visit other SCCs
1191       // that are now definitively ordered prior to the current one in the
1192       // post-order sequence, and may end up observing more precise context to
1193       // optimize the current SCC.
1194       UR.CWorklist.insert(C);
1195       LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist: " << *C
1196                         << "\n");
1197       // Enqueue in reverse order as we pop off the back of the worklist.
1198       for (SCC &MovedC : llvm::reverse(make_range(RC->begin() + InitialSCCIndex,
1199                                                   RC->begin() + NewSCCIndex))) {
1200         UR.CWorklist.insert(&MovedC);
1201         LLVM_DEBUG(dbgs() << "Enqueuing a newly earlier in post-order SCC: "
1202                           << MovedC << "\n");
1203       }
1204     }
1205   }
1206 
1207   assert(!UR.InvalidatedSCCs.count(C) && "Invalidated the current SCC!");
1208   assert(!UR.InvalidatedRefSCCs.count(RC) && "Invalidated the current RefSCC!");
1209   assert(&C->getOuterRefSCC() == RC && "Current SCC not in current RefSCC!");
1210 
1211   // Record the current RefSCC and SCC for higher layers of the CGSCC pass
1212   // manager now that all the updates have been applied.
1213   if (RC != &InitialRC)
1214     UR.UpdatedRC = RC;
1215   if (C != &InitialC)
1216     UR.UpdatedC = C;
1217 
1218   return *C;
1219 }
1220 
1221 LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForFunctionPass(
1222     LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,
1223     CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR,
1224     FunctionAnalysisManager &FAM) {
1225   return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR, FAM,
1226                                            /* FunctionPass */ true);
1227 }
1228 LazyCallGraph::SCC &llvm::updateCGAndAnalysisManagerForCGSCCPass(
1229     LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N,
1230     CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR,
1231     FunctionAnalysisManager &FAM) {
1232   return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR, FAM,
1233                                            /* FunctionPass */ false);
1234 }
1235