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