LLVM  16.0.0git
CGSCCPassManager.cpp
Go to the documentation of this file.
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 
10 #include "llvm/ADT/ArrayRef.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"
18 #include "llvm/IR/Constant.h"
19 #include "llvm/IR/InstIterator.h"
20 #include "llvm/IR/Instruction.h"
21 #include "llvm/IR/PassManager.h"
23 #include "llvm/IR/ValueHandle.h"
24 #include "llvm/Support/Casting.h"
26 #include "llvm/Support/Debug.h"
30 #include <cassert>
31 #include <iterator>
32 #include <optional>
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 {
42  "abort-on-max-devirt-iterations-reached",
43  cl::desc("Abort when the max iterations for devirtualization CGSCC repeat "
44  "pass is reached"));
45 
47 
48 // Explicit instantiations for the core proxy templates.
57 
58 /// Explicitly specialize the pass manager run method to handle call graph
59 /// updates.
60 template <>
66  // Request PassInstrumentation from analysis manager, will use it to run
67  // instrumenting callbacks for the passes later.
70 
72 
73  // The SCC may be refined while we are running passes over it, so set up
74  // a pointer that we can update.
75  LazyCallGraph::SCC *C = &InitialC;
76 
77  // Get Function analysis manager from its proxy.
80 
81  for (auto &Pass : Passes) {
82  // Check the PassInstrumentation's BeforePass callbacks before running the
83  // pass, skip its execution completely if asked to (callback returns false).
84  if (!PI.runBeforePass(*Pass, *C))
85  continue;
86 
87  PreservedAnalyses PassPA = Pass->run(*C, AM, G, UR);
88 
89  if (UR.InvalidatedSCCs.count(C))
91  else
92  PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
93 
94  // Update the SCC if necessary.
95  C = UR.UpdatedC ? UR.UpdatedC : C;
96  if (UR.UpdatedC) {
97  // If C is updated, also create a proxy and update FAM inside the result.
98  auto *ResultFAMCP =
100  ResultFAMCP->updateFAM(FAM);
101  }
102 
103  // Intersect the final preserved analyses to compute the aggregate
104  // preserved set for this pass manager.
105  PA.intersect(PassPA);
106 
107  // If the CGSCC pass wasn't able to provide a valid updated SCC, the
108  // current SCC may simply need to be skipped if invalid.
109  if (UR.InvalidatedSCCs.count(C)) {
110  LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
111  break;
112  }
113 
114  // Check that we didn't miss any update scenario.
115  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
116 
117  // Update the analysis manager as each pass runs and potentially
118  // invalidates analyses.
119  AM.invalidate(*C, PassPA);
120  }
121 
122  // Before we mark all of *this* SCC's analyses as preserved below, intersect
123  // this with the cross-SCC preserved analysis set. This is used to allow
124  // CGSCC passes to mutate ancestor SCCs and still trigger proper invalidation
125  // for them.
126  UR.CrossSCCPA.intersect(PA);
127 
128  // Invalidation was handled after each pass in the above loop for the current
129  // SCC. Therefore, the remaining analysis results in the AnalysisManager are
130  // preserved. We mark this with a set so that we don't need to inspect each
131  // one individually.
132  PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
133 
134  return PA;
135 }
136 
139  // Setup the CGSCC analysis manager from its proxy.
141  AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
142 
143  // Get the call graph for this module.
145 
146  // Get Function analysis manager from its proxy.
149 
150  // We keep worklists to allow us to push more work onto the pass manager as
151  // the passes are run.
154 
155  // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
156  // iterating off the worklists.
159 
161  InlinedInternalEdges;
162 
163  CGSCCUpdateResult UR = {
164  RCWorklist, CWorklist, InvalidRefSCCSet,
165  InvalidSCCSet, nullptr, PreservedAnalyses::all(),
166  InlinedInternalEdges, {}};
167 
168  // Request PassInstrumentation from analysis manager, will use it to run
169  // instrumenting callbacks for the passes later.
171 
173  CG.buildRefSCCs();
174  for (LazyCallGraph::RefSCC &RC :
176  assert(RCWorklist.empty() &&
177  "Should always start with an empty RefSCC worklist");
178  // The postorder_ref_sccs range we are walking is lazily constructed, so
179  // we only push the first one onto the worklist. The worklist allows us
180  // to capture *new* RefSCCs created during transformations.
181  //
182  // We really want to form RefSCCs lazily because that makes them cheaper
183  // to update as the program is simplified and allows us to have greater
184  // cache locality as forming a RefSCC touches all the parts of all the
185  // functions within that RefSCC.
186  //
187  // We also eagerly increment the iterator to the next position because
188  // the CGSCC passes below may delete the current RefSCC.
189  RCWorklist.insert(&RC);
190 
191  do {
192  LazyCallGraph::RefSCC *RC = RCWorklist.pop_back_val();
193  if (InvalidRefSCCSet.count(RC)) {
194  LLVM_DEBUG(dbgs() << "Skipping an invalid RefSCC...\n");
195  continue;
196  }
197 
198  assert(CWorklist.empty() &&
199  "Should always start with an empty SCC worklist");
200 
201  LLVM_DEBUG(dbgs() << "Running an SCC pass across the RefSCC: " << *RC
202  << "\n");
203 
204  // The top of the worklist may *also* be the same SCC we just ran over
205  // (and invalidated for). Keep track of that last SCC we processed due
206  // to SCC update to avoid redundant processing when an SCC is both just
207  // updated itself and at the top of the worklist.
208  LazyCallGraph::SCC *LastUpdatedC = nullptr;
209 
210  // Push the initial SCCs in reverse post-order as we'll pop off the
211  // back and so see this in post-order.
212  for (LazyCallGraph::SCC &C : llvm::reverse(*RC))
213  CWorklist.insert(&C);
214 
215  do {
216  LazyCallGraph::SCC *C = CWorklist.pop_back_val();
217  // Due to call graph mutations, we may have invalid SCCs or SCCs from
218  // other RefSCCs in the worklist. The invalid ones are dead and the
219  // other RefSCCs should be queued above, so we just need to skip both
220  // scenarios here.
221  if (InvalidSCCSet.count(C)) {
222  LLVM_DEBUG(dbgs() << "Skipping an invalid SCC...\n");
223  continue;
224  }
225  if (LastUpdatedC == C) {
226  LLVM_DEBUG(dbgs() << "Skipping redundant run on SCC: " << *C << "\n");
227  continue;
228  }
229  // We used to also check if the current SCC is part of the current
230  // RefSCC and bail if it wasn't, since it should be in RCWorklist.
231  // However, this can cause compile time explosions in some cases on
232  // modules with a huge RefSCC. If a non-trivial amount of SCCs in the
233  // huge RefSCC can become their own child RefSCC, we create one child
234  // RefSCC, bail on the current RefSCC, visit the child RefSCC, revisit
235  // the huge RefSCC, and repeat. By visiting all SCCs in the original
236  // RefSCC we create all the child RefSCCs in one pass of the RefSCC,
237  // rather one pass of the RefSCC creating one child RefSCC at a time.
238 
239  // Ensure we can proxy analysis updates from the CGSCC analysis manager
240  // into the the Function analysis manager by getting a proxy here.
241  // This also needs to update the FunctionAnalysisManager, as this may be
242  // the first time we see this SCC.
244  FAM);
245 
246  // Each time we visit a new SCC pulled off the worklist,
247  // a transformation of a child SCC may have also modified this parent
248  // and invalidated analyses. So we invalidate using the update record's
249  // cross-SCC preserved set. This preserved set is intersected by any
250  // CGSCC pass that handles invalidation (primarily pass managers) prior
251  // to marking its SCC as preserved. That lets us track everything that
252  // might need invalidation across SCCs without excessive invalidations
253  // on a single SCC.
254  //
255  // This essentially allows SCC passes to freely invalidate analyses
256  // of any ancestor SCC. If this becomes detrimental to successfully
257  // caching analyses, we could force each SCC pass to manually
258  // invalidate the analyses for any SCCs other than themselves which
259  // are mutated. However, that seems to lose the robustness of the
260  // pass-manager driven invalidation scheme.
261  CGAM.invalidate(*C, UR.CrossSCCPA);
262 
263  do {
264  // Check that we didn't miss any update scenario.
265  assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
266  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
267 
268  LastUpdatedC = UR.UpdatedC;
269  UR.UpdatedC = nullptr;
270 
271  // Check the PassInstrumentation's BeforePass callbacks before
272  // running the pass, skip its execution completely if asked to
273  // (callback returns false).
274  if (!PI.runBeforePass<LazyCallGraph::SCC>(*Pass, *C))
275  continue;
276 
277  PreservedAnalyses PassPA = Pass->run(*C, CGAM, CG, UR);
278 
279  if (UR.InvalidatedSCCs.count(C))
281  else
282  PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
283 
284  // Update the SCC and RefSCC if necessary.
285  C = UR.UpdatedC ? UR.UpdatedC : C;
286 
287  if (UR.UpdatedC) {
288  // If we're updating the SCC, also update the FAM inside the proxy's
289  // result.
291  FAM);
292  }
293 
294  // Intersect with the cross-SCC preserved set to capture any
295  // cross-SCC invalidation.
296  UR.CrossSCCPA.intersect(PassPA);
297  // Intersect the preserved set so that invalidation of module
298  // analyses will eventually occur when the module pass completes.
299  PA.intersect(PassPA);
300 
301  // If the CGSCC pass wasn't able to provide a valid updated SCC,
302  // the current SCC may simply need to be skipped if invalid.
303  if (UR.InvalidatedSCCs.count(C)) {
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 information
312  // for the (potentially updated) SCC here. Note that any other SCCs
313  // whose structure has changed should have been invalidated by
314  // whatever was updating the call graph. This SCC gets invalidated
315  // late as it contains the nodes that were actively being
316  // processed.
317  CGAM.invalidate(*C, PassPA);
318 
319  // The pass may have restructured the call graph and refined the
320  // current SCC and/or RefSCC. We need to update our current SCC and
321  // RefSCC pointers to follow these. Also, when the current SCC is
322  // refined, re-run the SCC pass over the newly refined SCC in order
323  // to observe the most precise SCC model available. This inherently
324  // cannot cycle excessively as it only happens when we split SCCs
325  // apart, at most converging on a DAG of single nodes.
326  // FIXME: If we ever start having RefSCC passes, we'll want to
327  // iterate there too.
328  if (UR.UpdatedC)
329  LLVM_DEBUG(dbgs()
330  << "Re-running SCC passes after a refinement of the "
331  "current SCC: "
332  << *UR.UpdatedC << "\n");
333 
334  // Note that both `C` and `RC` may at this point refer to deleted,
335  // invalid SCC and RefSCCs respectively. But we will short circuit
336  // the processing when we check them in the loop above.
337  } while (UR.UpdatedC);
338  } while (!CWorklist.empty());
339 
340  // We only need to keep internal inlined edge information within
341  // a RefSCC, clear it to save on space and let the next time we visit
342  // any of these functions have a fresh start.
343  InlinedInternalEdges.clear();
344  } while (!RCWorklist.empty());
345  }
346 
347  // By definition we preserve the call garph, all SCC analyses, and the
348  // analysis proxies by handling them above and in any nested pass managers.
349  PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
350  PA.preserve<LazyCallGraphAnalysis>();
351  PA.preserve<CGSCCAnalysisManagerModuleProxy>();
352  PA.preserve<FunctionAnalysisManagerModuleProxy>();
353  return PA;
354 }
355 
358  LazyCallGraph &CG,
359  CGSCCUpdateResult &UR) {
362  AM.getResult<PassInstrumentationAnalysis>(InitialC, CG);
363 
364  // The SCC may be refined while we are running passes over it, so set up
365  // a pointer that we can update.
366  LazyCallGraph::SCC *C = &InitialC;
367 
368  // Struct to track the counts of direct and indirect calls in each function
369  // of the SCC.
370  struct CallCount {
371  int Direct;
372  int Indirect;
373  };
374 
375  // Put value handles on all of the indirect calls and return the number of
376  // direct calls for each function in the SCC.
377  auto ScanSCC = [](LazyCallGraph::SCC &C,
379  assert(CallHandles.empty() && "Must start with a clear set of handles.");
380 
382  CallCount CountLocal = {0, 0};
383  for (LazyCallGraph::Node &N : C) {
384  CallCount &Count =
385  CallCounts.insert(std::make_pair(&N.getFunction(), CountLocal))
386  .first->second;
387  for (Instruction &I : instructions(N.getFunction()))
388  if (auto *CB = dyn_cast<CallBase>(&I)) {
389  if (CB->getCalledFunction()) {
390  ++Count.Direct;
391  } else {
392  ++Count.Indirect;
393  CallHandles.insert({CB, WeakTrackingVH(CB)});
394  }
395  }
396  }
397 
398  return CallCounts;
399  };
400 
401  UR.IndirectVHs.clear();
402  // Populate the initial call handles and get the initial call counts.
403  auto CallCounts = ScanSCC(*C, UR.IndirectVHs);
404 
405  for (int Iteration = 0;; ++Iteration) {
406  if (!PI.runBeforePass<LazyCallGraph::SCC>(*Pass, *C))
407  continue;
408 
409  PreservedAnalyses PassPA = Pass->run(*C, AM, CG, UR);
410 
411  if (UR.InvalidatedSCCs.count(C))
413  else
414  PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
415 
416  PA.intersect(PassPA);
417 
418  // If the SCC structure has changed, bail immediately and let the outer
419  // CGSCC layer handle any iteration to reflect the refined structure.
420  if (UR.UpdatedC && UR.UpdatedC != C)
421  break;
422 
423  // If the CGSCC pass wasn't able to provide a valid updated SCC, the
424  // current SCC may simply need to be skipped if invalid.
425  if (UR.InvalidatedSCCs.count(C)) {
426  LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
427  break;
428  }
429 
430  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
431 
432  // Check whether any of the handles were devirtualized.
433  bool Devirt = llvm::any_of(UR.IndirectVHs, [](auto &P) -> bool {
434  if (P.second) {
435  if (CallBase *CB = dyn_cast<CallBase>(P.second)) {
436  if (CB->getCalledFunction()) {
437  LLVM_DEBUG(dbgs() << "Found devirtualized call: " << *CB << "\n");
438  return true;
439  }
440  }
441  }
442  return false;
443  });
444 
445  // Rescan to build up a new set of handles and count how many direct
446  // calls remain. If we decide to iterate, this also sets up the input to
447  // the next iteration.
448  UR.IndirectVHs.clear();
449  auto NewCallCounts = ScanSCC(*C, UR.IndirectVHs);
450 
451  // If we haven't found an explicit devirtualization already see if we
452  // have decreased the number of indirect calls and increased the number
453  // of direct calls for any function in the SCC. This can be fooled by all
454  // manner of transformations such as DCE and other things, but seems to
455  // work well in practice.
456  if (!Devirt)
457  // Iterate over the keys in NewCallCounts, if Function also exists in
458  // CallCounts, make the check below.
459  for (auto &Pair : NewCallCounts) {
460  auto &CallCountNew = Pair.second;
461  auto CountIt = CallCounts.find(Pair.first);
462  if (CountIt != CallCounts.end()) {
463  const auto &CallCountOld = CountIt->second;
464  if (CallCountOld.Indirect > CallCountNew.Indirect &&
465  CallCountOld.Direct < CallCountNew.Direct) {
466  Devirt = true;
467  break;
468  }
469  }
470  }
471 
472  if (!Devirt) {
473  break;
474  }
475 
476  // Otherwise, if we've already hit our max, we're done.
477  if (Iteration >= MaxIterations) {
479  report_fatal_error("Max devirtualization iterations reached");
480  LLVM_DEBUG(
481  dbgs() << "Found another devirtualization after hitting the max "
482  "number of repetitions ("
483  << MaxIterations << ") on SCC: " << *C << "\n");
484  break;
485  }
486 
487  LLVM_DEBUG(
488  dbgs() << "Repeating an SCC pass after finding a devirtualization in: "
489  << *C << "\n");
490 
491  // Move over the new call counts in preparation for iterating.
492  CallCounts = std::move(NewCallCounts);
493 
494  // Update the analysis manager with each run and intersect the total set
495  // of preserved analyses so we're ready to iterate.
496  AM.invalidate(*C, PassPA);
497  }
498 
499  // Note that we don't add any preserved entries here unlike a more normal
500  // "pass manager" because we only handle invalidation *between* iterations,
501  // not after the last iteration.
502  return PA;
503 }
504 
507  LazyCallGraph &CG,
508  CGSCCUpdateResult &UR) {
509  // Setup the function analysis manager from its proxy.
511  AM.getResult<FunctionAnalysisManagerCGSCCProxy>(C, CG).getManager();
512 
514  for (LazyCallGraph::Node &N : C)
515  Nodes.push_back(&N);
516 
517  // The SCC may get split while we are optimizing functions due to deleting
518  // edges. If this happens, the current SCC can shift, so keep track of
519  // a pointer we can overwrite.
520  LazyCallGraph::SCC *CurrentC = &C;
521 
522  LLVM_DEBUG(dbgs() << "Running function passes across an SCC: " << C << "\n");
523 
525  for (LazyCallGraph::Node *N : Nodes) {
526  // Skip nodes from other SCCs. These may have been split out during
527  // processing. We'll eventually visit those SCCs and pick up the nodes
528  // there.
529  if (CG.lookupSCC(*N) != CurrentC)
530  continue;
531 
532  Function &F = N->getFunction();
533 
535  continue;
536 
538  if (!PI.runBeforePass<Function>(*Pass, F))
539  continue;
540 
541  PreservedAnalyses PassPA = Pass->run(F, FAM);
542  PI.runAfterPass<Function>(*Pass, F, PassPA);
543 
544  // We know that the function pass couldn't have invalidated any other
545  // function's analyses (that's the contract of a function pass), so
546  // directly handle the function analysis manager's invalidation here.
547  FAM.invalidate(F, EagerlyInvalidate ? PreservedAnalyses::none() : PassPA);
548  if (NoRerun)
550 
551  // Then intersect the preserved set so that invalidation of module
552  // analyses will eventually occur when the module pass completes.
553  PA.intersect(std::move(PassPA));
554 
555  // If the call graph hasn't been preserved, update it based on this
556  // function pass. This may also update the current SCC to point to
557  // a smaller, more refined SCC.
558  auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
559  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
560  CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
561  AM, UR, FAM);
562  assert(CG.lookupSCC(*N) == CurrentC &&
563  "Current SCC not updated to the SCC containing the current node!");
564  }
565  }
566 
567  // By definition we preserve the proxy. And we preserve all analyses on
568  // Functions. This precludes *any* invalidation of function analyses by the
569  // proxy, but that's OK because we've taken care to invalidate analyses in
570  // the function analysis manager incrementally above.
573 
574  // We've also ensured that we updated the call graph along the way.
576 
577  return PA;
578 }
579 
581  Module &M, const PreservedAnalyses &PA,
583  // If literally everything is preserved, we're done.
584  if (PA.areAllPreserved())
585  return false; // This is still a valid proxy.
586 
587  // If this proxy or the call graph is going to be invalidated, we also need
588  // to clear all the keys coming from that analysis.
589  //
590  // We also directly invalidate the FAM's module proxy if necessary, and if
591  // that proxy isn't preserved we can't preserve this proxy either. We rely on
592  // it to handle module -> function analysis invalidation in the face of
593  // structural changes and so if it's unavailable we conservatively clear the
594  // entire SCC layer as well rather than trying to do invalidation ourselves.
596  if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>()) ||
597  Inv.invalidate<LazyCallGraphAnalysis>(M, PA) ||
599  InnerAM->clear();
600 
601  // And the proxy itself should be marked as invalid so that we can observe
602  // the new call graph. This isn't strictly necessary because we cheat
603  // above, but is still useful.
604  return true;
605  }
606 
607  // Directly check if the relevant set is preserved so we can short circuit
608  // invalidating SCCs below.
609  bool AreSCCAnalysesPreserved =
611 
612  // Ok, we have a graph, so we can propagate the invalidation down into it.
613  G->buildRefSCCs();
614  for (auto &RC : G->postorder_ref_sccs())
615  for (auto &C : RC) {
616  std::optional<PreservedAnalyses> InnerPA;
617 
618  // Check to see whether the preserved set needs to be adjusted based on
619  // module-level analysis invalidation triggering deferred invalidation
620  // for this SCC.
621  if (auto *OuterProxy =
622  InnerAM->getCachedResult<ModuleAnalysisManagerCGSCCProxy>(C))
623  for (const auto &OuterInvalidationPair :
624  OuterProxy->getOuterInvalidations()) {
625  AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
626  const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
627  if (Inv.invalidate(OuterAnalysisID, M, PA)) {
628  if (!InnerPA)
629  InnerPA = PA;
630  for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
631  InnerPA->abandon(InnerAnalysisID);
632  }
633  }
634 
635  // Check if we needed a custom PA set. If so we'll need to run the inner
636  // invalidation.
637  if (InnerPA) {
638  InnerAM->invalidate(C, *InnerPA);
639  continue;
640  }
641 
642  // Otherwise we only need to do invalidation if the original PA set didn't
643  // preserve all SCC analyses.
644  if (!AreSCCAnalysesPreserved)
645  InnerAM->invalidate(C, PA);
646  }
647 
648  // Return false to indicate that this result is still a valid proxy.
649  return false;
650 }
651 
652 template <>
655  // Force the Function analysis manager to also be available so that it can
656  // be accessed in an SCC analysis and proxied onward to function passes.
657  // FIXME: It is pretty awkward to just drop the result here and assert that
658  // we can find it again later.
660 
661  return Result(*InnerAM, AM.getResult<LazyCallGraphAnalysis>(M));
662 }
663 
664 AnalysisKey FunctionAnalysisManagerCGSCCProxy::Key;
665 
669  LazyCallGraph &CG) {
670  // Note: unconditionally getting checking that the proxy exists may get it at
671  // this point. There are cases when this is being run unnecessarily, but
672  // it is cheap and having the assertion in place is more valuable.
673  auto &MAMProxy = AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG);
674  Module &M = *C.begin()->getFunction().getParent();
675  bool ProxyExists =
676  MAMProxy.cachedResultExists<FunctionAnalysisManagerModuleProxy>(M);
677  assert(ProxyExists &&
678  "The CGSCC pass manager requires that the FAM module proxy is run "
679  "on the module prior to entering the CGSCC walk");
680  (void)ProxyExists;
681 
682  // We just return an empty result. The caller will use the updateFAM interface
683  // to correctly register the relevant FunctionAnalysisManager based on the
684  // context in which this proxy is run.
685  return Result();
686 }
687 
691  // If literally everything is preserved, we're done.
692  if (PA.areAllPreserved())
693  return false; // This is still a valid proxy.
694 
695  // All updates to preserve valid results are done below, so we don't need to
696  // invalidate this proxy.
697  //
698  // Note that in order to preserve this proxy, a module pass must ensure that
699  // the FAM has been completely updated to handle the deletion of functions.
700  // Specifically, any FAM-cached results for those functions need to have been
701  // forcibly cleared. When preserved, this proxy will only invalidate results
702  // cached on functions *still in the module* at the end of the module pass.
704  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>()) {
705  for (LazyCallGraph::Node &N : C)
706  FAM->invalidate(N.getFunction(), PA);
707 
708  return false;
709  }
710 
711  // Directly check if the relevant set is preserved.
712  bool AreFunctionAnalysesPreserved =
714 
715  // Now walk all the functions to see if any inner analysis invalidation is
716  // necessary.
717  for (LazyCallGraph::Node &N : C) {
718  Function &F = N.getFunction();
719  std::optional<PreservedAnalyses> FunctionPA;
720 
721  // Check to see whether the preserved set needs to be pruned based on
722  // SCC-level analysis invalidation that triggers deferred invalidation
723  // registered with the outer analysis manager proxy for this function.
724  if (auto *OuterProxy =
726  for (const auto &OuterInvalidationPair :
727  OuterProxy->getOuterInvalidations()) {
728  AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
729  const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
730  if (Inv.invalidate(OuterAnalysisID, C, PA)) {
731  if (!FunctionPA)
732  FunctionPA = PA;
733  for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
734  FunctionPA->abandon(InnerAnalysisID);
735  }
736  }
737 
738  // Check if we needed a custom PA set, and if so we'll need to run the
739  // inner invalidation.
740  if (FunctionPA) {
741  FAM->invalidate(F, *FunctionPA);
742  continue;
743  }
744 
745  // Otherwise we only need to do invalidation if the original PA set didn't
746  // preserve all function analyses.
747  if (!AreFunctionAnalysesPreserved)
748  FAM->invalidate(F, PA);
749  }
750 
751  // Return false to indicate that this result is still a valid proxy.
752  return false;
753 }
754 
755 } // end namespace llvm
756 
757 /// When a new SCC is created for the graph we first update the
758 /// FunctionAnalysisManager in the Proxy's result.
759 /// As there might be function analysis results cached for the functions now in
760 /// that SCC, two forms of updates are required.
761 ///
762 /// First, a proxy from the SCC to the FunctionAnalysisManager needs to be
763 /// created so that any subsequent invalidation events to the SCC are
764 /// propagated to the function analysis results cached for functions within it.
765 ///
766 /// Second, if any of the functions within the SCC have analysis results with
767 /// outer analysis dependencies, then those dependencies would point to the
768 /// *wrong* SCC's analysis result. We forcibly invalidate the necessary
769 /// function analyses so that they don't retain stale handles.
771  LazyCallGraph &G,
775 
776  // Now walk the functions in this SCC and invalidate any function analysis
777  // results that might have outer dependencies on an SCC analysis.
778  for (LazyCallGraph::Node &N : C) {
779  Function &F = N.getFunction();
780 
781  auto *OuterProxy =
783  if (!OuterProxy)
784  // No outer analyses were queried, nothing to do.
785  continue;
786 
787  // Forcibly abandon all the inner analyses with dependencies, but
788  // invalidate nothing else.
789  auto PA = PreservedAnalyses::all();
790  for (const auto &OuterInvalidationPair :
791  OuterProxy->getOuterInvalidations()) {
792  const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
793  for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
794  PA.abandon(InnerAnalysisID);
795  }
796 
797  // Now invalidate anything we found.
798  FAM.invalidate(F, PA);
799  }
800 }
801 
802 /// Helper function to update both the \c CGSCCAnalysisManager \p AM and the \c
803 /// CGSCCPassManager's \c CGSCCUpdateResult \p UR based on a range of newly
804 /// added SCCs.
805 ///
806 /// The range of new SCCs must be in postorder already. The SCC they were split
807 /// out of must be provided as \p C. The current node being mutated and
808 /// triggering updates must be passed as \p N.
809 ///
810 /// This function returns the SCC containing \p N. This will be either \p C if
811 /// no new SCCs have been split out, or it will be the new SCC containing \p N.
812 template <typename SCCRangeT>
813 static LazyCallGraph::SCC *
814 incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G,
817  using SCC = LazyCallGraph::SCC;
818 
819  if (NewSCCRange.empty())
820  return C;
821 
822  // Add the current SCC to the worklist as its shape has changed.
823  UR.CWorklist.insert(C);
824  LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist:" << *C
825  << "\n");
826 
827  SCC *OldC = C;
828 
829  // Update the current SCC. Note that if we have new SCCs, this must actually
830  // change the SCC.
831  assert(C != &*NewSCCRange.begin() &&
832  "Cannot insert new SCCs without changing current SCC!");
833  C = &*NewSCCRange.begin();
834  assert(G.lookupSCC(N) == C && "Failed to update current SCC!");
835 
836  // If we had a cached FAM proxy originally, we will want to create more of
837  // them for each SCC that was split off.
838  FunctionAnalysisManager *FAM = nullptr;
839  if (auto *FAMProxy =
841  FAM = &FAMProxy->getManager();
842 
843  // We need to propagate an invalidation call to all but the newly current SCC
844  // because the outer pass manager won't do that for us after splitting them.
845  // FIXME: We should accept a PreservedAnalysis from the CG updater so that if
846  // there are preserved analysis we can avoid invalidating them here for
847  // split-off SCCs.
848  // We know however that this will preserve any FAM proxy so go ahead and mark
849  // that.
850  auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
851  PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
852  AM.invalidate(*OldC, PA);
853 
854  // Ensure the now-current SCC's function analyses are updated.
855  if (FAM)
857 
858  for (SCC &NewC : llvm::reverse(llvm::drop_begin(NewSCCRange))) {
859  assert(C != &NewC && "No need to re-visit the current SCC!");
860  assert(OldC != &NewC && "Already handled the original SCC!");
861  UR.CWorklist.insert(&NewC);
862  LLVM_DEBUG(dbgs() << "Enqueuing a newly formed SCC:" << NewC << "\n");
863 
864  // Ensure new SCCs' function analyses are updated.
865  if (FAM)
866  updateNewSCCFunctionAnalyses(NewC, G, AM, *FAM);
867 
868  // Also propagate a normal invalidation to the new SCC as only the current
869  // will get one from the pass manager infrastructure.
870  AM.invalidate(NewC, PA);
871  }
872  return C;
873 }
874 
879  using Node = LazyCallGraph::Node;
880  using Edge = LazyCallGraph::Edge;
881  using SCC = LazyCallGraph::SCC;
882  using RefSCC = LazyCallGraph::RefSCC;
883 
884  RefSCC &InitialRC = InitialC.getOuterRefSCC();
885  SCC *C = &InitialC;
886  RefSCC *RC = &InitialRC;
887  Function &F = N.getFunction();
888 
889  // Walk the function body and build up the set of retained, promoted, and
890  // demoted edges.
893  SmallPtrSet<Node *, 16> RetainedEdges;
894  SmallSetVector<Node *, 4> PromotedRefTargets;
895  SmallSetVector<Node *, 4> DemotedCallTargets;
896  SmallSetVector<Node *, 4> NewCallEdges;
897  SmallSetVector<Node *, 4> NewRefEdges;
898 
899  // First walk the function and handle all called functions. We do this first
900  // because if there is a single call edge, whether there are ref edges is
901  // irrelevant.
902  for (Instruction &I : instructions(F)) {
903  if (auto *CB = dyn_cast<CallBase>(&I)) {
904  if (Function *Callee = CB->getCalledFunction()) {
905  if (Visited.insert(Callee).second && !Callee->isDeclaration()) {
906  Node *CalleeN = G.lookup(*Callee);
907  assert(CalleeN &&
908  "Visited function should already have an associated node");
909  Edge *E = N->lookup(*CalleeN);
910  assert((E || !FunctionPass) &&
911  "No function transformations should introduce *new* "
912  "call edges! Any new calls should be modeled as "
913  "promoted existing ref edges!");
914  bool Inserted = RetainedEdges.insert(CalleeN).second;
915  (void)Inserted;
916  assert(Inserted && "We should never visit a function twice.");
917  if (!E)
918  NewCallEdges.insert(CalleeN);
919  else if (!E->isCall())
920  PromotedRefTargets.insert(CalleeN);
921  }
922  } else {
923  // We can miss devirtualization if an indirect call is created then
924  // promoted before updateCGAndAnalysisManagerForPass runs.
925  auto *Entry = UR.IndirectVHs.find(CB);
926  if (Entry == UR.IndirectVHs.end())
927  UR.IndirectVHs.insert({CB, WeakTrackingVH(CB)});
928  else if (!Entry->second)
929  Entry->second = WeakTrackingVH(CB);
930  }
931  }
932  }
933 
934  // Now walk all references.
935  for (Instruction &I : instructions(F))
936  for (Value *Op : I.operand_values())
937  if (auto *OpC = dyn_cast<Constant>(Op))
938  if (Visited.insert(OpC).second)
939  Worklist.push_back(OpC);
940 
941  auto VisitRef = [&](Function &Referee) {
942  Node *RefereeN = G.lookup(Referee);
943  assert(RefereeN &&
944  "Visited function should already have an associated node");
945  Edge *E = N->lookup(*RefereeN);
946  assert((E || !FunctionPass) &&
947  "No function transformations should introduce *new* ref "
948  "edges! Any new ref edges would require IPO which "
949  "function passes aren't allowed to do!");
950  bool Inserted = RetainedEdges.insert(RefereeN).second;
951  (void)Inserted;
952  assert(Inserted && "We should never visit a function twice.");
953  if (!E)
954  NewRefEdges.insert(RefereeN);
955  else if (E->isCall())
956  DemotedCallTargets.insert(RefereeN);
957  };
958  LazyCallGraph::visitReferences(Worklist, Visited, VisitRef);
959 
960  // Handle new ref edges.
961  for (Node *RefTarget : NewRefEdges) {
962  SCC &TargetC = *G.lookupSCC(*RefTarget);
963  RefSCC &TargetRC = TargetC.getOuterRefSCC();
964  (void)TargetRC;
965  // TODO: This only allows trivial edges to be added for now.
966 #ifdef EXPENSIVE_CHECKS
967  assert((RC == &TargetRC ||
968  RC->isAncestorOf(TargetRC)) && "New ref edge is not trivial!");
969 #endif
970  RC->insertTrivialRefEdge(N, *RefTarget);
971  }
972 
973  // Handle new call edges.
974  for (Node *CallTarget : NewCallEdges) {
975  SCC &TargetC = *G.lookupSCC(*CallTarget);
976  RefSCC &TargetRC = TargetC.getOuterRefSCC();
977  (void)TargetRC;
978  // TODO: This only allows trivial edges to be added for now.
979 #ifdef EXPENSIVE_CHECKS
980  assert((RC == &TargetRC ||
981  RC->isAncestorOf(TargetRC)) && "New call edge is not trivial!");
982 #endif
983  // Add a trivial ref edge to be promoted later on alongside
984  // PromotedRefTargets.
985  RC->insertTrivialRefEdge(N, *CallTarget);
986  }
987 
988  // Include synthetic reference edges to known, defined lib functions.
989  for (auto *LibFn : G.getLibFunctions())
990  // While the list of lib functions doesn't have repeats, don't re-visit
991  // anything handled above.
992  if (!Visited.count(LibFn))
993  VisitRef(*LibFn);
994 
995  // First remove all of the edges that are no longer present in this function.
996  // The first step makes these edges uniformly ref edges and accumulates them
997  // into a separate data structure so removal doesn't invalidate anything.
998  SmallVector<Node *, 4> DeadTargets;
999  for (Edge &E : *N) {
1000  if (RetainedEdges.count(&E.getNode()))
1001  continue;
1002 
1003  SCC &TargetC = *G.lookupSCC(E.getNode());
1004  RefSCC &TargetRC = TargetC.getOuterRefSCC();
1005  if (&TargetRC == RC && E.isCall()) {
1006  if (C != &TargetC) {
1007  // For separate SCCs this is trivial.
1008  RC->switchTrivialInternalEdgeToRef(N, E.getNode());
1009  } else {
1010  // Now update the call graph.
1011  C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, E.getNode()),
1012  G, N, C, AM, UR);
1013  }
1014  }
1015 
1016  // Now that this is ready for actual removal, put it into our list.
1017  DeadTargets.push_back(&E.getNode());
1018  }
1019  // Remove the easy cases quickly and actually pull them out of our list.
1020  llvm::erase_if(DeadTargets, [&](Node *TargetN) {
1021  SCC &TargetC = *G.lookupSCC(*TargetN);
1022  RefSCC &TargetRC = TargetC.getOuterRefSCC();
1023 
1024  // We can't trivially remove internal targets, so skip
1025  // those.
1026  if (&TargetRC == RC)
1027  return false;
1028 
1029  LLVM_DEBUG(dbgs() << "Deleting outgoing edge from '" << N << "' to '"
1030  << *TargetN << "'\n");
1031  RC->removeOutgoingEdge(N, *TargetN);
1032  return true;
1033  });
1034 
1035  // Now do a batch removal of the internal ref edges left.
1036  auto NewRefSCCs = RC->removeInternalRefEdge(N, DeadTargets);
1037  if (!NewRefSCCs.empty()) {
1038  // The old RefSCC is dead, mark it as such.
1039  UR.InvalidatedRefSCCs.insert(RC);
1040 
1041  // Note that we don't bother to invalidate analyses as ref-edge
1042  // connectivity is not really observable in any way and is intended
1043  // exclusively to be used for ordering of transforms rather than for
1044  // analysis conclusions.
1045 
1046  // Update RC to the "bottom".
1047  assert(G.lookupSCC(N) == C && "Changed the SCC when splitting RefSCCs!");
1048  RC = &C->getOuterRefSCC();
1049  assert(G.lookupRefSCC(N) == RC && "Failed to update current RefSCC!");
1050 
1051  // The RC worklist is in reverse postorder, so we enqueue the new ones in
1052  // RPO except for the one which contains the source node as that is the
1053  // "bottom" we will continue processing in the bottom-up walk.
1054  assert(NewRefSCCs.front() == RC &&
1055  "New current RefSCC not first in the returned list!");
1056  for (RefSCC *NewRC : llvm::reverse(llvm::drop_begin(NewRefSCCs))) {
1057  assert(NewRC != RC && "Should not encounter the current RefSCC further "
1058  "in the postorder list of new RefSCCs.");
1059  UR.RCWorklist.insert(NewRC);
1060  LLVM_DEBUG(dbgs() << "Enqueuing a new RefSCC in the update worklist: "
1061  << *NewRC << "\n");
1062  }
1063  }
1064 
1065  // Next demote all the call edges that are now ref edges. This helps make
1066  // the SCCs small which should minimize the work below as we don't want to
1067  // form cycles that this would break.
1068  for (Node *RefTarget : DemotedCallTargets) {
1069  SCC &TargetC = *G.lookupSCC(*RefTarget);
1070  RefSCC &TargetRC = TargetC.getOuterRefSCC();
1071 
1072  // The easy case is when the target RefSCC is not this RefSCC. This is
1073  // only supported when the target RefSCC is a child of this RefSCC.
1074  if (&TargetRC != RC) {
1075 #ifdef EXPENSIVE_CHECKS
1076  assert(RC->isAncestorOf(TargetRC) &&
1077  "Cannot potentially form RefSCC cycles here!");
1078 #endif
1079  RC->switchOutgoingEdgeToRef(N, *RefTarget);
1080  LLVM_DEBUG(dbgs() << "Switch outgoing call edge to a ref edge from '" << N
1081  << "' to '" << *RefTarget << "'\n");
1082  continue;
1083  }
1084 
1085  // We are switching an internal call edge to a ref edge. This may split up
1086  // some SCCs.
1087  if (C != &TargetC) {
1088  // For separate SCCs this is trivial.
1089  RC->switchTrivialInternalEdgeToRef(N, *RefTarget);
1090  continue;
1091  }
1092 
1093  // Now update the call graph.
1094  C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, *RefTarget), G, N,
1095  C, AM, UR);
1096  }
1097 
1098  // We added a ref edge earlier for new call edges, promote those to call edges
1099  // alongside PromotedRefTargets.
1100  for (Node *E : NewCallEdges)
1101  PromotedRefTargets.insert(E);
1102 
1103  // Now promote ref edges into call edges.
1104  for (Node *CallTarget : PromotedRefTargets) {
1105  SCC &TargetC = *G.lookupSCC(*CallTarget);
1106  RefSCC &TargetRC = TargetC.getOuterRefSCC();
1107 
1108  // The easy case is when the target RefSCC is not this RefSCC. This is
1109  // only supported when the target RefSCC is a child of this RefSCC.
1110  if (&TargetRC != RC) {
1111 #ifdef EXPENSIVE_CHECKS
1112  assert(RC->isAncestorOf(TargetRC) &&
1113  "Cannot potentially form RefSCC cycles here!");
1114 #endif
1115  RC->switchOutgoingEdgeToCall(N, *CallTarget);
1116  LLVM_DEBUG(dbgs() << "Switch outgoing ref edge to a call edge from '" << N
1117  << "' to '" << *CallTarget << "'\n");
1118  continue;
1119  }
1120  LLVM_DEBUG(dbgs() << "Switch an internal ref edge to a call edge from '"
1121  << N << "' to '" << *CallTarget << "'\n");
1122 
1123  // Otherwise we are switching an internal ref edge to a call edge. This
1124  // may merge away some SCCs, and we add those to the UpdateResult. We also
1125  // need to make sure to update the worklist in the event SCCs have moved
1126  // before the current one in the post-order sequence
1127  bool HasFunctionAnalysisProxy = false;
1128  auto InitialSCCIndex = RC->find(*C) - RC->begin();
1129  bool FormedCycle = RC->switchInternalEdgeToCall(
1130  N, *CallTarget, [&](ArrayRef<SCC *> MergedSCCs) {
1131  for (SCC *MergedC : MergedSCCs) {
1132  assert(MergedC != &TargetC && "Cannot merge away the target SCC!");
1133 
1134  HasFunctionAnalysisProxy |=
1136  *MergedC) != nullptr;
1137 
1138  // Mark that this SCC will no longer be valid.
1139  UR.InvalidatedSCCs.insert(MergedC);
1140 
1141  // FIXME: We should really do a 'clear' here to forcibly release
1142  // memory, but we don't have a good way of doing that and
1143  // preserving the function analyses.
1144  auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
1145  PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1146  AM.invalidate(*MergedC, PA);
1147  }
1148  });
1149 
1150  // If we formed a cycle by creating this call, we need to update more data
1151  // structures.
1152  if (FormedCycle) {
1153  C = &TargetC;
1154  assert(G.lookupSCC(N) == C && "Failed to update current SCC!");
1155 
1156  // If one of the invalidated SCCs had a cached proxy to a function
1157  // analysis manager, we need to create a proxy in the new current SCC as
1158  // the invalidated SCCs had their functions moved.
1159  if (HasFunctionAnalysisProxy)
1161 
1162  // Any analyses cached for this SCC are no longer precise as the shape
1163  // has changed by introducing this cycle. However, we have taken care to
1164  // update the proxies so it remains valide.
1165  auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
1166  PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1167  AM.invalidate(*C, PA);
1168  }
1169  auto NewSCCIndex = RC->find(*C) - RC->begin();
1170  // If we have actually moved an SCC to be topologically "below" the current
1171  // one due to merging, we will need to revisit the current SCC after
1172  // visiting those moved SCCs.
1173  //
1174  // It is critical that we *do not* revisit the current SCC unless we
1175  // actually move SCCs in the process of merging because otherwise we may
1176  // form a cycle where an SCC is split apart, merged, split, merged and so
1177  // on infinitely.
1178  if (InitialSCCIndex < NewSCCIndex) {
1179  // Put our current SCC back onto the worklist as we'll visit other SCCs
1180  // that are now definitively ordered prior to the current one in the
1181  // post-order sequence, and may end up observing more precise context to
1182  // optimize the current SCC.
1183  UR.CWorklist.insert(C);
1184  LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist: " << *C
1185  << "\n");
1186  // Enqueue in reverse order as we pop off the back of the worklist.
1187  for (SCC &MovedC : llvm::reverse(make_range(RC->begin() + InitialSCCIndex,
1188  RC->begin() + NewSCCIndex))) {
1189  UR.CWorklist.insert(&MovedC);
1190  LLVM_DEBUG(dbgs() << "Enqueuing a newly earlier in post-order SCC: "
1191  << MovedC << "\n");
1192  }
1193  }
1194  }
1195 
1196  assert(!UR.InvalidatedSCCs.count(C) && "Invalidated the current SCC!");
1197  assert(!UR.InvalidatedRefSCCs.count(RC) && "Invalidated the current RefSCC!");
1198  assert(&C->getOuterRefSCC() == RC && "Current SCC not in current RefSCC!");
1199 
1200  // Record the current SCC for higher layers of the CGSCC pass manager now that
1201  // all the updates have been applied.
1202  if (C != &InitialC)
1203  UR.UpdatedC = C;
1204 
1205  return *C;
1206 }
1207 
1212  return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR, FAM,
1213  /* FunctionPass */ true);
1214 }
1219  return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR, FAM,
1220  /* FunctionPass */ false);
1221 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:152
llvm::OuterAnalysisManagerProxy
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1056
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::LazyCallGraph::buildRefSCCs
void buildRefSCCs()
Definition: LazyCallGraph.cpp:1922
M
We currently emits eax Perhaps this is what we really should generate is Is imull three or four cycles eax eax The current instruction priority is based on pattern complexity The former is more complex because it folds a load so the latter will not be emitted Perhaps we should use AddedComplexity to give LEA32r a higher priority We should always try to match LEA first since the LEA matching code does some estimate to determine whether the match is profitable if we care more about code then imull is better It s two bytes shorter than movl leal On a Pentium M
Definition: README.txt:252
Pass
print lazy value Lazy Value Info Printer Pass
Definition: LazyValueInfo.cpp:1999
llvm::make_range
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
Definition: iterator_range.h:53
llvm::drop_begin
auto drop_begin(T &&RangeOrContainer, size_t N=1)
Return a range covering RangeOrContainer with the first N elements excluded.
Definition: STLExtras.h:387
llvm::WeakTrackingVH
Value handle that is nullable, but tries to track the Value.
Definition: ValueHandle.h:204
llvm::CGSCCUpdateResult::InvalidatedSCCs
SmallPtrSetImpl< LazyCallGraph::SCC * > & InvalidatedSCCs
The set of invalidated SCCs which should be skipped if they are found in CWorklist.
Definition: CGSCCPassManager.h:273
llvm::AnalysisManager::getResult
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:774
InstIterator.h
llvm::Function
Definition: Function.h:60
llvm::AnalysisManager::Invalidator::invalidate
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Trigger the invalidation of some other analysis pass if not already handled and return whether it was...
Definition: PassManager.h:679
llvm::AnalysisManager::invalidate
void invalidate(IRUnitT &IR, const PreservedAnalyses &PA)
Invalidate cached analyses for an IR unit.
Definition: PassManagerImpl.h:89
P
This currently compiles esp xmm0 movsd esp eax eax esp ret We should use not the dag combiner This is because dagcombine2 needs to be able to see through the X86ISD::Wrapper which DAGCombine can t really do The code for turning x load into a single vector load is target independent and should be moved to the dag combiner The code for turning x load into a vector load can only handle a direct load from a global or a direct load from the stack It should be generalized to handle any load from P
Definition: README-SSE.txt:411
llvm::AbortOnMaxDevirtIterationsReached
static cl::opt< bool > AbortOnMaxDevirtIterationsReached("abort-on-max-devirt-iterations-reached", cl::desc("Abort when the max iterations for devirtualization CGSCC repeat " "pass is reached"))
llvm::PriorityWorklist< T, SmallVector< T, N >, SmallDenseMap< T, ptrdiff_t > >::insert
bool insert(const T &X)
Insert a new element into the PriorityWorklist.
Definition: PriorityWorklist.h:90
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1199
ErrorHandling.h
llvm::SmallDenseSet
Implements a dense probed hash-table based set with some number of buckets stored inline.
Definition: DenseSet.h:286
llvm::InnerAnalysisManagerProxy::Result
Definition: PassManager.h:935
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:90
llvm::erase_if
void erase_if(Container &C, UnaryPredicate P)
Provide a container algorithm similar to C++ Library Fundamentals v2's erase_if which is equivalent t...
Definition: STLExtras.h:1997
llvm::SmallDenseMap
Definition: DenseMap.h:880
llvm::FunctionAnalysisManagerCGSCCProxy::run
Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &)
Computes the FunctionAnalysisManager and stores it in the result proxy.
Definition: CGSCCPassManager.cpp:667
llvm::PreservedAnalyses::abandon
void abandon()
Mark an analysis as abandoned.
Definition: PassManager.h:206
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
Passes
const char * Passes
Definition: PassBuilderBindings.cpp:46
llvm::ShouldNotRunFunctionPassesAnalysis
Definition: CGSCCPassManager.h:528
llvm::PreservedAnalyses::none
static PreservedAnalyses none()
Convenience factory function for the empty preserved set.
Definition: PassManager.h:155
llvm::ModuleAnalysisManager
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
Definition: PassManager.h:907
llvm::SmallPtrSet
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements.
Definition: SmallPtrSet.h:450
STLExtras.h
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:55
llvm::FunctionAnalysisManagerCGSCCProxy::Result
Definition: CGSCCPassManager.h:395
llvm::PreservedAnalyses::intersect
void intersect(const PreservedAnalyses &Arg)
Intersect this set with another in place.
Definition: PassManager.h:224
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
PriorityWorklist.h
Instruction.h
CommandLine.h
llvm::CGSCCUpdateResult::IndirectVHs
SmallMapVector< Value *, WeakTrackingVH, 16 > IndirectVHs
Weak VHs to keep track of indirect calls for the purposes of detecting devirtualization.
Definition: CGSCCPassManager.h:317
llvm::LazyCallGraph::SCC
An SCC of the call graph.
Definition: LazyCallGraph.h:419
PassManagerImpl.h
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
C
(vector float) vec_cmpeq(*A, *B) C
Definition: README_ALTIVEC.txt:86
llvm::Instruction
Definition: Instruction.h:42
llvm::report_fatal_error
void report_fatal_error(Error Err, bool gen_crash_diag=true)
Report a serious error, calling any installed error handler.
Definition: Error.cpp:145
llvm::LazyCallGraph::RefSCC
A RefSCC of the call graph.
Definition: LazyCallGraph.h:544
SmallPtrSet.h
llvm::LazyCallGraph::lookupSCC
SCC * lookupSCC(Node &N) const
Lookup a function's SCC in the graph.
Definition: LazyCallGraph.h:979
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:661
LazyCallGraph.h
llvm::dxil::PointerTypeAnalysis::run
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
Definition: PointerTypeAnalysis.cpp:189
llvm::FunctionAnalysisManagerCGSCCProxy::Result::invalidate
bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA, CGSCCAnalysisManager::Invalidator &Inv)
Definition: CGSCCPassManager.cpp:688
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:200
llvm::SmallMapVector
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:233
llvm::cl::opt< bool >
llvm::instructions
inst_range instructions(Function *F)
Definition: InstIterator.h:133
llvm::CGSCCUpdateResult::UpdatedC
LazyCallGraph::SCC * UpdatedC
If non-null, the updated current SCC being processed.
Definition: CGSCCPassManager.h:283
llvm::updateCGAndAnalysisManagerForFunctionPass
LazyCallGraph::SCC & updateCGAndAnalysisManagerForFunctionPass(LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, FunctionAnalysisManager &FAM)
Helper to update the call graph after running a function pass.
Definition: CGSCCPassManager.cpp:1208
llvm::PassInstrumentation::runAfterPass
void runAfterPass(const PassT &Pass, const IRUnitT &IR, const PreservedAnalyses &PA) const
AfterPass instrumentation point - takes Pass instance that has just been executed and constant refere...
Definition: PassInstrumentation.h:254
llvm::PreservedAnalyses::preserve
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:173
llvm::SmallPriorityWorklist
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
Definition: PriorityWorklist.h:255
move
compiles ldr LCPI1_0 ldr ldr mov lsr tst moveq r1 ldr LCPI1_1 and r0 bx lr It would be better to do something like to fold the shift into the conditional move
Definition: README.txt:546
CGSCCPassManager.h
llvm::AnalysisKey
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:69
I
#define I(x, y, z)
Definition: MD5.cpp:58
llvm::CGSCCUpdateResult::CWorklist
SmallPriorityWorklist< LazyCallGraph::SCC *, 1 > & CWorklist
Worklist of the SCCs queued for processing.
Definition: CGSCCPassManager.h:257
llvm::make_early_inc_range
iterator_range< early_inc_iterator_impl< detail::IterOfRange< RangeT > > > make_early_inc_range(RangeT &&Range)
Make a range that does early increment to allow mutation of the underlying range without disrupting i...
Definition: STLExtras.h:716
llvm::PassInstrumentation::runAfterPassInvalidated
void runAfterPassInvalidated(const PassT &Pass, const PreservedAnalyses &PA) const
AfterPassInvalidated instrumentation point - takes Pass instance that has just been executed.
Definition: PassInstrumentation.h:265
ArrayRef.h
llvm::PriorityWorklist< T, SmallVector< T, N >, SmallDenseMap< T, ptrdiff_t > >::empty
bool empty() const
Determine if the PriorityWorklist is empty or not.
Definition: PriorityWorklist.h:67
llvm::InnerAnalysisManagerProxy::Result::invalidate
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA, typename AnalysisManager< IRUnitT, ExtraArgTs... >::Invalidator &Inv)
Handler for invalidation of the outer IR unit, IRUnitT.
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::CGSCCAnalysisManager
AnalysisManager< LazyCallGraph::SCC, LazyCallGraph & > CGSCCAnalysisManager
The CGSCC analysis manager.
Definition: CGSCCPassManager.h:123
llvm::PassInstrumentation
This class provides instrumentation entry points for the Pass Manager, doing calls to callbacks regis...
Definition: PassInstrumentation.h:192
iterator_range.h
llvm::PreservedAnalyses::allAnalysesInSetPreserved
bool allAnalysesInSetPreserved() const
Directly test whether a set of analyses is preserved.
Definition: PassManager.h:335
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:65
llvm::LazyCallGraph::Node
A node in the call graph.
Definition: LazyCallGraph.h:315
llvm::SmallPtrSetImpl::count
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:383
updateCGAndAnalysisManagerForPass
static LazyCallGraph::SCC & updateCGAndAnalysisManagerForPass(LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N, CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, FunctionAnalysisManager &FAM, bool FunctionPass)
Definition: CGSCCPassManager.cpp:875
llvm::SetVector< T, SmallVector< T, N >, SmallDenseSet< T, N > >::insert
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
llvm::detail::DenseSetImpl< ValueT, SmallDenseMap< ValueT, detail::DenseSetEmpty, 4, DenseMapInfo< ValueT >, detail::DenseSetPair< ValueT > >, DenseMapInfo< ValueT > >::clear
void clear()
Definition: DenseSet.h:92
llvm::AMDGPU::CPol::SCC
@ SCC
Definition: SIDefines.h:310
llvm::LazyCallGraph::Edge
A class used to represent edges in the call graph.
Definition: LazyCallGraph.h:131
llvm::ArrayRef
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: APInt.h:32
llvm::CGSCCUpdateResult::CrossSCCPA
PreservedAnalyses CrossSCCPA
Preserved analyses across SCCs.
Definition: CGSCCPassManager.h:298
llvm::any_of
bool any_of(R &&range, UnaryPredicate P)
Provide wrappers to std::any_of which take ranges instead of having to pass begin/end explicitly.
Definition: STLExtras.h:1741
llvm::PreservedAnalyses::areAllPreserved
bool areAllPreserved() const
Test whether all analyses are preserved (and none are abandoned).
Definition: PassManager.h:327
llvm::DevirtSCCRepeatedPass::run
PreservedAnalyses run(LazyCallGraph::SCC &InitialC, CGSCCAnalysisManager &AM, LazyCallGraph &CG, CGSCCUpdateResult &UR)
Runs the wrapped pass up to MaxIterations on the SCC, iterating whenever an indirect call is refined.
Definition: CGSCCPassManager.cpp:356
incorporateNewSCCRange
static LazyCallGraph::SCC * incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G, LazyCallGraph::Node &N, LazyCallGraph::SCC *C, CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR)
Helper function to update both the CGSCCAnalysisManager AM and the CGSCCPassManager's CGSCCUpdateResu...
Definition: CGSCCPassManager.cpp:814
ValueHandle.h
llvm::DenseMapBase< SmallDenseMap< KeyT, ValueT, 4, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >, KeyT, ValueT, DenseMapInfo< KeyT >, llvm::detail::DenseMapPair< KeyT, ValueT > >::insert
std::pair< iterator, bool > insert(const std::pair< KeyT, ValueT > &KV)
Definition: DenseMap.h:207
llvm::PassManager
Manages a sequence of passes over a particular unit of IR.
Definition: PassManager.h:469
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:187
Constant.h
llvm::CGSCCUpdateResult
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
Definition: CGSCCPassManager.h:232
llvm::PassInstrumentation::runBeforePass
bool runBeforePass(const PassT &Pass, const IRUnitT &IR) const
BeforePass instrumentation point - takes Pass instance to be executed and constant reference to IR it...
Definition: PassInstrumentation.h:229
llvm::AMDGPU::SendMsg::Op
Op
Definition: SIDefines.h:351
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:158
llvm::LazyCallGraphAnalysis
An analysis pass which computes the call graph for a module.
Definition: LazyCallGraph.h:1257
llvm::AnalysisManager::getCachedResult
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:793
Casting.h
llvm::ModuleToPostOrderCGSCCPassAdaptor::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Runs the CGSCC pass across every SCC in the module.
Definition: CGSCCPassManager.cpp:138
PassManager.h
llvm::ShouldNotRunFunctionPassesAnalysis::Key
static AnalysisKey Key
Definition: CGSCCPassManager.h:531
llvm::updateCGAndAnalysisManagerForCGSCCPass
LazyCallGraph::SCC & updateCGAndAnalysisManagerForCGSCCPass(LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, FunctionAnalysisManager &FAM)
Helper to update the call graph after running a CGSCC pass.
Definition: CGSCCPassManager.cpp:1215
llvm::PriorityWorklist< T, SmallVector< T, N >, SmallDenseMap< T, ptrdiff_t > >::pop_back_val
T pop_back_val()
Definition: PriorityWorklist.h:153
llvm::CGSCCAnalysisManagerModuleProxy::Result
We need a specialized result for the CGSCCAnalysisManagerModuleProxy so it can have access to the cal...
Definition: CGSCCPassManager.h:173
llvm::Pass
Pass interface - Implemented by all 'passes'.
Definition: Pass.h:91
llvm::PreservedAnalyses::preserveSet
void preserveSet()
Mark an analysis set as preserved.
Definition: PassManager.h:188
SmallVector.h
N
#define N
llvm::LazyCallGraph::SCC::getOuterRefSCC
RefSCC & getOuterRefSCC() const
Definition: LazyCallGraph.h:482
llvm::LazyCallGraph::postorder_ref_sccs
iterator_range< postorder_ref_scc_iterator > postorder_ref_sccs()
Definition: LazyCallGraph.h:968
llvm::reverse
auto reverse(ContainerTy &&C)
Definition: STLExtras.h:485
updateNewSCCFunctionAnalyses
static void updateNewSCCFunctionAnalyses(LazyCallGraph::SCC &C, LazyCallGraph &G, CGSCCAnalysisManager &AM, FunctionAnalysisManager &FAM)
When a new SCC is created for the graph we first update the FunctionAnalysisManager in the Proxy's re...
Definition: CGSCCPassManager.cpp:770
llvm::SmallSetVector
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:307
llvm::PreservedAnalyses::getChecker
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:310
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:42
llvm::PassInstrumentationAnalysis
Pseudo-analysis pass that exposes the PassInstrumentation to pass managers.
Definition: PassManager.h:594
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:931
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:308
llvm::cl::desc
Definition: CommandLine.h:412
llvm::LazyCallGraph
A lazily constructed view of the call graph of a module.
Definition: LazyCallGraph.h:110
raw_ostream.h
llvm::LazyCallGraph::visitReferences
static void visitReferences(SmallVectorImpl< Constant * > &Worklist, SmallPtrSetImpl< Constant * > &Visited, function_ref< void(Function &)> Callback)
Recursively visits the defined functions whose address is reachable from every constant in the Workli...
Definition: LazyCallGraph.cpp:1960
llvm::FunctionAnalysisManagerCGSCCProxy
A proxy from a FunctionAnalysisManager to an SCC.
Definition: CGSCCPassManager.h:392
llvm::CGSCCUpdateResult::InvalidatedRefSCCs
SmallPtrSetImpl< LazyCallGraph::RefSCC * > & InvalidatedRefSCCs
The set of invalidated RefSCCs which should be skipped if they are found in RCWorklist.
Definition: CGSCCPassManager.h:265
llvm::InnerAnalysisManagerProxy::run
Result run(IRUnitT &IR, AnalysisManager< IRUnitT, ExtraArgTs... > &AM, ExtraArgTs...)
Run the analysis pass and create our proxy result object.
Definition: PassManager.h:994
CGAM
CGSCCAnalysisManager CGAM
Definition: PassBuilderBindings.cpp:60
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
TimeProfiler.h
Debug.h
SetVector.h
llvm::CGSCCUpdateResult::RCWorklist
SmallPriorityWorklist< LazyCallGraph::RefSCC *, 1 > & RCWorklist
Worklist of the RefSCCs queued for processing.
Definition: CGSCCPassManager.h:242
llvm::SmallPtrSetImpl::insert
std::pair< iterator, bool > insert(PtrType Ptr)
Inserts Ptr if and only if there is no element in the container equal to Ptr.
Definition: SmallPtrSet.h:365