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