LLVM  14.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"
12 #include "llvm/ADT/STLExtras.h"
13 #include "llvm/ADT/SetVector.h"
14 #include "llvm/ADT/SmallPtrSet.h"
15 #include "llvm/ADT/SmallVector.h"
18 #include "llvm/IR/Constant.h"
19 #include "llvm/IR/InstIterator.h"
20 #include "llvm/IR/Instruction.h"
21 #include "llvm/IR/PassManager.h"
23 #include "llvm/IR/ValueHandle.h"
24 #include "llvm/Support/Casting.h"
26 #include "llvm/Support/Debug.h"
30 #include <algorithm>
31 #include <cassert>
32 #include <iterator>
33 
34 #define DEBUG_TYPE "cgscc"
35 
36 using namespace llvm;
37 
38 // Explicit template instantiations and specialization definitions for core
39 // template typedefs.
40 namespace llvm {
41 
43  "abort-on-max-devirt-iterations-reached",
44  cl::desc("Abort when the max iterations for devirtualization CGSCC repeat "
45  "pass is reached"));
46 
47 // Explicit instantiations for the core proxy templates.
56 
57 /// Explicitly specialize the pass manager run method to handle call graph
58 /// updates.
59 template <>
65  // Request PassInstrumentation from analysis manager, will use it to run
66  // instrumenting callbacks for the passes later.
69 
71 
72  // The SCC may be refined while we are running passes over it, so set up
73  // a pointer that we can update.
74  LazyCallGraph::SCC *C = &InitialC;
75 
76  // Get Function analysis manager from its proxy.
79 
80  for (auto &Pass : Passes) {
81  // Check the PassInstrumentation's BeforePass callbacks before running the
82  // pass, skip its execution completely if asked to (callback returns false).
83  if (!PI.runBeforePass(*Pass, *C))
84  continue;
85 
86  PreservedAnalyses PassPA;
87  {
88  TimeTraceScope TimeScope(Pass->name());
89  PassPA = Pass->run(*C, AM, G, UR);
90  }
91 
92  if (UR.InvalidatedSCCs.count(C))
94  else
95  PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
96 
97  // Update the SCC if necessary.
98  C = UR.UpdatedC ? UR.UpdatedC : C;
99  if (UR.UpdatedC) {
100  // If C is updated, also create a proxy and update FAM inside the result.
101  auto *ResultFAMCP =
103  ResultFAMCP->updateFAM(FAM);
104  }
105 
106  // If the CGSCC pass wasn't able to provide a valid updated SCC, the
107  // current SCC may simply need to be skipped if invalid.
108  if (UR.InvalidatedSCCs.count(C)) {
109  LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
110  break;
111  }
112  // Check that we didn't miss any update scenario.
113  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
114 
115  // Update the analysis manager as each pass runs and potentially
116  // invalidates analyses.
117  AM.invalidate(*C, PassPA);
118 
119  // Finally, we intersect the final preserved analyses to compute the
120  // aggregate preserved set for this pass manager.
121  PA.intersect(std::move(PassPA));
122  }
123 
124  // Before we mark all of *this* SCC's analyses as preserved below, intersect
125  // this with the cross-SCC preserved analysis set. This is used to allow
126  // CGSCC passes to mutate ancestor SCCs and still trigger proper invalidation
127  // for them.
128  UR.CrossSCCPA.intersect(PA);
129 
130  // Invalidation was handled after each pass in the above loop for the current
131  // SCC. Therefore, the remaining analysis results in the AnalysisManager are
132  // preserved. We mark this with a set so that we don't need to inspect each
133  // one individually.
134  PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
135 
136  return PA;
137 }
138 
141  // Setup the CGSCC analysis manager from its proxy.
143  AM.getResult<CGSCCAnalysisManagerModuleProxy>(M).getManager();
144 
145  // Get the call graph for this module.
147 
148  // Get Function analysis manager from its proxy.
151 
152  // We keep worklists to allow us to push more work onto the pass manager as
153  // the passes are run.
156 
157  // Keep sets for invalidated SCCs and RefSCCs that should be skipped when
158  // iterating off the worklists.
161 
163  InlinedInternalEdges;
164 
165  CGSCCUpdateResult UR = {
166  RCWorklist, CWorklist, InvalidRefSCCSet, InvalidSCCSet,
167  nullptr, nullptr, PreservedAnalyses::all(), InlinedInternalEdges,
168  {}};
169 
170  // Request PassInstrumentation from analysis manager, will use it to run
171  // instrumenting callbacks for the passes later.
173 
175  CG.buildRefSCCs();
176  for (auto RCI = CG.postorder_ref_scc_begin(),
177  RCE = CG.postorder_ref_scc_end();
178  RCI != RCE;) {
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(&*RCI++);
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  if (&C->getOuterRefSCC() != RC) {
233  LLVM_DEBUG(dbgs() << "Skipping an SCC that is now part of some other "
234  "RefSCC...\n");
235  continue;
236  }
237 
238  // Ensure we can proxy analysis updates from the CGSCC analysis manager
239  // into the the Function analysis manager by getting a proxy here.
240  // This also needs to update the FunctionAnalysisManager, as this may be
241  // the first time we see this SCC.
243  FAM);
244 
245  // Each time we visit a new SCC pulled off the worklist,
246  // a transformation of a child SCC may have also modified this parent
247  // and invalidated analyses. So we invalidate using the update record's
248  // cross-SCC preserved set. This preserved set is intersected by any
249  // CGSCC pass that handles invalidation (primarily pass managers) prior
250  // to marking its SCC as preserved. That lets us track everything that
251  // might need invalidation across SCCs without excessive invalidations
252  // on a single SCC.
253  //
254  // This essentially allows SCC passes to freely invalidate analyses
255  // of any ancestor SCC. If this becomes detrimental to successfully
256  // caching analyses, we could force each SCC pass to manually
257  // invalidate the analyses for any SCCs other than themselves which
258  // are mutated. However, that seems to lose the robustness of the
259  // pass-manager driven invalidation scheme.
260  CGAM.invalidate(*C, UR.CrossSCCPA);
261 
262  do {
263  // Check that we didn't miss any update scenario.
264  assert(!InvalidSCCSet.count(C) && "Processing an invalid SCC!");
265  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
266  assert(&C->getOuterRefSCC() == RC &&
267  "Processing an SCC in a different RefSCC!");
268 
269  LastUpdatedC = UR.UpdatedC;
270  UR.UpdatedRC = nullptr;
271  UR.UpdatedC = nullptr;
272 
273  // Check the PassInstrumentation's BeforePass callbacks before
274  // running the pass, skip its execution completely if asked to
275  // (callback returns false).
276  if (!PI.runBeforePass<LazyCallGraph::SCC>(*Pass, *C))
277  continue;
278 
279  PreservedAnalyses PassPA;
280  {
281  TimeTraceScope TimeScope(Pass->name());
282  PassPA = Pass->run(*C, CGAM, CG, UR);
283  }
284 
285  if (UR.InvalidatedSCCs.count(C))
287  else
288  PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C, PassPA);
289 
290  // Update the SCC and RefSCC if necessary.
291  C = UR.UpdatedC ? UR.UpdatedC : C;
292  RC = UR.UpdatedRC ? UR.UpdatedRC : RC;
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 
515 PreservedAnalyses CGSCCToFunctionPassAdaptor::run(LazyCallGraph::SCC &C,
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  if (!PI.runBeforePass<Function>(*Pass, F))
546  continue;
547 
548  PreservedAnalyses PassPA;
549  {
550  TimeTraceScope TimeScope(Pass->name());
551  PassPA = Pass->run(F, FAM);
552  }
553 
554  PI.runAfterPass<Function>(*Pass, F, PassPA);
555 
556  // We know that the function pass couldn't have invalidated any other
557  // function's analyses (that's the contract of a function pass), so
558  // directly handle the function analysis manager's invalidation here.
559  FAM.invalidate(F, PassPA);
560 
561  // Then intersect the preserved set so that invalidation of module
562  // analyses will eventually occur when the module pass completes.
563  PA.intersect(std::move(PassPA));
564 
565  // If the call graph hasn't been preserved, update it based on this
566  // function pass. This may also update the current SCC to point to
567  // a smaller, more refined SCC.
568  auto PAC = PA.getChecker<LazyCallGraphAnalysis>();
569  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<Module>>()) {
570  CurrentC = &updateCGAndAnalysisManagerForFunctionPass(CG, *CurrentC, *N,
571  AM, UR, FAM);
572  assert(CG.lookupSCC(*N) == CurrentC &&
573  "Current SCC not updated to the SCC containing the current node!");
574  }
575  }
576 
577  // By definition we preserve the proxy. And we preserve all analyses on
578  // Functions. This precludes *any* invalidation of function analyses by the
579  // proxy, but that's OK because we've taken care to invalidate analyses in
580  // the function analysis manager incrementally above.
583 
584  // We've also ensured that we updated the call graph along the way.
586 
587  return PA;
588 }
589 
591  Module &M, const PreservedAnalyses &PA,
593  // If literally everything is preserved, we're done.
594  if (PA.areAllPreserved())
595  return false; // This is still a valid proxy.
596 
597  // If this proxy or the call graph is going to be invalidated, we also need
598  // to clear all the keys coming from that analysis.
599  //
600  // We also directly invalidate the FAM's module proxy if necessary, and if
601  // that proxy isn't preserved we can't preserve this proxy either. We rely on
602  // it to handle module -> function analysis invalidation in the face of
603  // structural changes and so if it's unavailable we conservatively clear the
604  // entire SCC layer as well rather than trying to do invalidation ourselves.
606  if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>()) ||
607  Inv.invalidate<LazyCallGraphAnalysis>(M, PA) ||
609  InnerAM->clear();
610 
611  // And the proxy itself should be marked as invalid so that we can observe
612  // the new call graph. This isn't strictly necessary because we cheat
613  // above, but is still useful.
614  return true;
615  }
616 
617  // Directly check if the relevant set is preserved so we can short circuit
618  // invalidating SCCs below.
619  bool AreSCCAnalysesPreserved =
621 
622  // Ok, we have a graph, so we can propagate the invalidation down into it.
623  G->buildRefSCCs();
624  for (auto &RC : G->postorder_ref_sccs())
625  for (auto &C : RC) {
627 
628  // Check to see whether the preserved set needs to be adjusted based on
629  // module-level analysis invalidation triggering deferred invalidation
630  // for this SCC.
631  if (auto *OuterProxy =
632  InnerAM->getCachedResult<ModuleAnalysisManagerCGSCCProxy>(C))
633  for (const auto &OuterInvalidationPair :
634  OuterProxy->getOuterInvalidations()) {
635  AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
636  const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
637  if (Inv.invalidate(OuterAnalysisID, M, PA)) {
638  if (!InnerPA)
639  InnerPA = PA;
640  for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
641  InnerPA->abandon(InnerAnalysisID);
642  }
643  }
644 
645  // Check if we needed a custom PA set. If so we'll need to run the inner
646  // invalidation.
647  if (InnerPA) {
648  InnerAM->invalidate(C, *InnerPA);
649  continue;
650  }
651 
652  // Otherwise we only need to do invalidation if the original PA set didn't
653  // preserve all SCC analyses.
654  if (!AreSCCAnalysesPreserved)
655  InnerAM->invalidate(C, PA);
656  }
657 
658  // Return false to indicate that this result is still a valid proxy.
659  return false;
660 }
661 
662 template <>
665  // Force the Function analysis manager to also be available so that it can
666  // be accessed in an SCC analysis and proxied onward to function passes.
667  // FIXME: It is pretty awkward to just drop the result here and assert that
668  // we can find it again later.
670 
671  return Result(*InnerAM, AM.getResult<LazyCallGraphAnalysis>(M));
672 }
673 
674 AnalysisKey FunctionAnalysisManagerCGSCCProxy::Key;
675 
679  LazyCallGraph &CG) {
680  // Note: unconditionally getting checking that the proxy exists may get it at
681  // this point. There are cases when this is being run unnecessarily, but
682  // it is cheap and having the assertion in place is more valuable.
683  auto &MAMProxy = AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG);
684  Module &M = *C.begin()->getFunction().getParent();
685  bool ProxyExists =
686  MAMProxy.cachedResultExists<FunctionAnalysisManagerModuleProxy>(M);
687  assert(ProxyExists &&
688  "The CGSCC pass manager requires that the FAM module proxy is run "
689  "on the module prior to entering the CGSCC walk");
690  (void)ProxyExists;
691 
692  // We just return an empty result. The caller will use the updateFAM interface
693  // to correctly register the relevant FunctionAnalysisManager based on the
694  // context in which this proxy is run.
695  return Result();
696 }
697 
701  // If literally everything is preserved, we're done.
702  if (PA.areAllPreserved())
703  return false; // This is still a valid proxy.
704 
705  // All updates to preserve valid results are done below, so we don't need to
706  // invalidate this proxy.
707  //
708  // Note that in order to preserve this proxy, a module pass must ensure that
709  // the FAM has been completely updated to handle the deletion of functions.
710  // Specifically, any FAM-cached results for those functions need to have been
711  // forcibly cleared. When preserved, this proxy will only invalidate results
712  // cached on functions *still in the module* at the end of the module pass.
714  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>()) {
715  for (LazyCallGraph::Node &N : C)
716  FAM->invalidate(N.getFunction(), PA);
717 
718  return false;
719  }
720 
721  // Directly check if the relevant set is preserved.
722  bool AreFunctionAnalysesPreserved =
724 
725  // Now walk all the functions to see if any inner analysis invalidation is
726  // necessary.
727  for (LazyCallGraph::Node &N : C) {
728  Function &F = N.getFunction();
729  Optional<PreservedAnalyses> FunctionPA;
730 
731  // Check to see whether the preserved set needs to be pruned based on
732  // SCC-level analysis invalidation that triggers deferred invalidation
733  // registered with the outer analysis manager proxy for this function.
734  if (auto *OuterProxy =
736  for (const auto &OuterInvalidationPair :
737  OuterProxy->getOuterInvalidations()) {
738  AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
739  const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
740  if (Inv.invalidate(OuterAnalysisID, C, PA)) {
741  if (!FunctionPA)
742  FunctionPA = PA;
743  for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
744  FunctionPA->abandon(InnerAnalysisID);
745  }
746  }
747 
748  // Check if we needed a custom PA set, and if so we'll need to run the
749  // inner invalidation.
750  if (FunctionPA) {
751  FAM->invalidate(F, *FunctionPA);
752  continue;
753  }
754 
755  // Otherwise we only need to do invalidation if the original PA set didn't
756  // preserve all function analyses.
757  if (!AreFunctionAnalysesPreserved)
758  FAM->invalidate(F, PA);
759  }
760 
761  // Return false to indicate that this result is still a valid proxy.
762  return false;
763 }
764 
765 } // end namespace llvm
766 
767 /// When a new SCC is created for the graph we first update the
768 /// FunctionAnalysisManager in the Proxy's result.
769 /// As there might be function analysis results cached for the functions now in
770 /// that SCC, two forms of updates are required.
771 ///
772 /// First, a proxy from the SCC to the FunctionAnalysisManager needs to be
773 /// created so that any subsequent invalidation events to the SCC are
774 /// propagated to the function analysis results cached for functions within it.
775 ///
776 /// Second, if any of the functions within the SCC have analysis results with
777 /// outer analysis dependencies, then those dependencies would point to the
778 /// *wrong* SCC's analysis result. We forcibly invalidate the necessary
779 /// function analyses so that they don't retain stale handles.
781  LazyCallGraph &G,
785 
786  // Now walk the functions in this SCC and invalidate any function analysis
787  // results that might have outer dependencies on an SCC analysis.
788  for (LazyCallGraph::Node &N : C) {
789  Function &F = N.getFunction();
790 
791  auto *OuterProxy =
793  if (!OuterProxy)
794  // No outer analyses were queried, nothing to do.
795  continue;
796 
797  // Forcibly abandon all the inner analyses with dependencies, but
798  // invalidate nothing else.
799  auto PA = PreservedAnalyses::all();
800  for (const auto &OuterInvalidationPair :
801  OuterProxy->getOuterInvalidations()) {
802  const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
803  for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
804  PA.abandon(InnerAnalysisID);
805  }
806 
807  // Now invalidate anything we found.
808  FAM.invalidate(F, PA);
809  }
810 }
811 
812 /// Helper function to update both the \c CGSCCAnalysisManager \p AM and the \c
813 /// CGSCCPassManager's \c CGSCCUpdateResult \p UR based on a range of newly
814 /// added SCCs.
815 ///
816 /// The range of new SCCs must be in postorder already. The SCC they were split
817 /// out of must be provided as \p C. The current node being mutated and
818 /// triggering updates must be passed as \p N.
819 ///
820 /// This function returns the SCC containing \p N. This will be either \p C if
821 /// no new SCCs have been split out, or it will be the new SCC containing \p N.
822 template <typename SCCRangeT>
823 static LazyCallGraph::SCC *
824 incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G,
827  using SCC = LazyCallGraph::SCC;
828 
829  if (NewSCCRange.empty())
830  return C;
831 
832  // Add the current SCC to the worklist as its shape has changed.
833  UR.CWorklist.insert(C);
834  LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist:" << *C
835  << "\n");
836 
837  SCC *OldC = C;
838 
839  // Update the current SCC. Note that if we have new SCCs, this must actually
840  // change the SCC.
841  assert(C != &*NewSCCRange.begin() &&
842  "Cannot insert new SCCs without changing current SCC!");
843  C = &*NewSCCRange.begin();
844  assert(G.lookupSCC(N) == C && "Failed to update current SCC!");
845 
846  // If we had a cached FAM proxy originally, we will want to create more of
847  // them for each SCC that was split off.
848  FunctionAnalysisManager *FAM = nullptr;
849  if (auto *FAMProxy =
851  FAM = &FAMProxy->getManager();
852 
853  // We need to propagate an invalidation call to all but the newly current SCC
854  // because the outer pass manager won't do that for us after splitting them.
855  // FIXME: We should accept a PreservedAnalysis from the CG updater so that if
856  // there are preserved analysis we can avoid invalidating them here for
857  // split-off SCCs.
858  // We know however that this will preserve any FAM proxy so go ahead and mark
859  // that.
862  AM.invalidate(*OldC, PA);
863 
864  // Ensure the now-current SCC's function analyses are updated.
865  if (FAM)
867 
868  for (SCC &NewC : llvm::reverse(llvm::drop_begin(NewSCCRange))) {
869  assert(C != &NewC && "No need to re-visit the current SCC!");
870  assert(OldC != &NewC && "Already handled the original SCC!");
871  UR.CWorklist.insert(&NewC);
872  LLVM_DEBUG(dbgs() << "Enqueuing a newly formed SCC:" << NewC << "\n");
873 
874  // Ensure new SCCs' function analyses are updated.
875  if (FAM)
876  updateNewSCCFunctionAnalyses(NewC, G, AM, *FAM);
877 
878  // Also propagate a normal invalidation to the new SCC as only the current
879  // will get one from the pass manager infrastructure.
880  AM.invalidate(NewC, PA);
881  }
882  return C;
883 }
884 
889  using Node = LazyCallGraph::Node;
890  using Edge = LazyCallGraph::Edge;
891  using SCC = LazyCallGraph::SCC;
892  using RefSCC = LazyCallGraph::RefSCC;
893 
894  RefSCC &InitialRC = InitialC.getOuterRefSCC();
895  SCC *C = &InitialC;
896  RefSCC *RC = &InitialRC;
897  Function &F = N.getFunction();
898 
899  // Walk the function body and build up the set of retained, promoted, and
900  // demoted edges.
903  SmallPtrSet<Node *, 16> RetainedEdges;
904  SmallSetVector<Node *, 4> PromotedRefTargets;
905  SmallSetVector<Node *, 4> DemotedCallTargets;
906  SmallSetVector<Node *, 4> NewCallEdges;
907  SmallSetVector<Node *, 4> NewRefEdges;
908 
909  // First walk the function and handle all called functions. We do this first
910  // because if there is a single call edge, whether there are ref edges is
911  // irrelevant.
912  for (Instruction &I : instructions(F)) {
913  if (auto *CB = dyn_cast<CallBase>(&I)) {
914  if (Function *Callee = CB->getCalledFunction()) {
915  if (Visited.insert(Callee).second && !Callee->isDeclaration()) {
916  Node *CalleeN = G.lookup(*Callee);
917  assert(CalleeN &&
918  "Visited function should already have an associated node");
919  Edge *E = N->lookup(*CalleeN);
920  assert((E || !FunctionPass) &&
921  "No function transformations should introduce *new* "
922  "call edges! Any new calls should be modeled as "
923  "promoted existing ref edges!");
924  bool Inserted = RetainedEdges.insert(CalleeN).second;
925  (void)Inserted;
926  assert(Inserted && "We should never visit a function twice.");
927  if (!E)
928  NewCallEdges.insert(CalleeN);
929  else if (!E->isCall())
930  PromotedRefTargets.insert(CalleeN);
931  }
932  } else {
933  // We can miss devirtualization if an indirect call is created then
934  // promoted before updateCGAndAnalysisManagerForPass runs.
935  auto *Entry = UR.IndirectVHs.find(CB);
936  if (Entry == UR.IndirectVHs.end())
937  UR.IndirectVHs.insert({CB, WeakTrackingVH(CB)});
938  else if (!Entry->second)
939  Entry->second = WeakTrackingVH(CB);
940  }
941  }
942  }
943 
944  // Now walk all references.
945  for (Instruction &I : instructions(F))
946  for (Value *Op : I.operand_values())
947  if (auto *OpC = dyn_cast<Constant>(Op))
948  if (Visited.insert(OpC).second)
949  Worklist.push_back(OpC);
950 
951  auto VisitRef = [&](Function &Referee) {
952  Node *RefereeN = G.lookup(Referee);
953  assert(RefereeN &&
954  "Visited function should already have an associated node");
955  Edge *E = N->lookup(*RefereeN);
956  assert((E || !FunctionPass) &&
957  "No function transformations should introduce *new* ref "
958  "edges! Any new ref edges would require IPO which "
959  "function passes aren't allowed to do!");
960  bool Inserted = RetainedEdges.insert(RefereeN).second;
961  (void)Inserted;
962  assert(Inserted && "We should never visit a function twice.");
963  if (!E)
964  NewRefEdges.insert(RefereeN);
965  else if (E->isCall())
966  DemotedCallTargets.insert(RefereeN);
967  };
968  LazyCallGraph::visitReferences(Worklist, Visited, VisitRef);
969 
970  // Handle new ref edges.
971  for (Node *RefTarget : NewRefEdges) {
972  SCC &TargetC = *G.lookupSCC(*RefTarget);
973  RefSCC &TargetRC = TargetC.getOuterRefSCC();
974  (void)TargetRC;
975  // TODO: This only allows trivial edges to be added for now.
976 #ifdef EXPENSIVE_CHECKS
977  assert((RC == &TargetRC ||
978  RC->isAncestorOf(TargetRC)) && "New ref edge is not trivial!");
979 #endif
980  RC->insertTrivialRefEdge(N, *RefTarget);
981  }
982 
983  // Handle new call edges.
984  for (Node *CallTarget : NewCallEdges) {
985  SCC &TargetC = *G.lookupSCC(*CallTarget);
986  RefSCC &TargetRC = TargetC.getOuterRefSCC();
987  (void)TargetRC;
988  // TODO: This only allows trivial edges to be added for now.
989 #ifdef EXPENSIVE_CHECKS
990  assert((RC == &TargetRC ||
991  RC->isAncestorOf(TargetRC)) && "New call edge is not trivial!");
992 #endif
993  // Add a trivial ref edge to be promoted later on alongside
994  // PromotedRefTargets.
995  RC->insertTrivialRefEdge(N, *CallTarget);
996  }
997 
998  // Include synthetic reference edges to known, defined lib functions.
999  for (auto *LibFn : G.getLibFunctions())
1000  // While the list of lib functions doesn't have repeats, don't re-visit
1001  // anything handled above.
1002  if (!Visited.count(LibFn))
1003  VisitRef(*LibFn);
1004 
1005  // First remove all of the edges that are no longer present in this function.
1006  // The first step makes these edges uniformly ref edges and accumulates them
1007  // into a separate data structure so removal doesn't invalidate anything.
1008  SmallVector<Node *, 4> DeadTargets;
1009  for (Edge &E : *N) {
1010  if (RetainedEdges.count(&E.getNode()))
1011  continue;
1012 
1013  SCC &TargetC = *G.lookupSCC(E.getNode());
1014  RefSCC &TargetRC = TargetC.getOuterRefSCC();
1015  if (&TargetRC == RC && E.isCall()) {
1016  if (C != &TargetC) {
1017  // For separate SCCs this is trivial.
1018  RC->switchTrivialInternalEdgeToRef(N, E.getNode());
1019  } else {
1020  // Now update the call graph.
1021  C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, E.getNode()),
1022  G, N, C, AM, UR);
1023  }
1024  }
1025 
1026  // Now that this is ready for actual removal, put it into our list.
1027  DeadTargets.push_back(&E.getNode());
1028  }
1029  // Remove the easy cases quickly and actually pull them out of our list.
1030  llvm::erase_if(DeadTargets, [&](Node *TargetN) {
1031  SCC &TargetC = *G.lookupSCC(*TargetN);
1032  RefSCC &TargetRC = TargetC.getOuterRefSCC();
1033 
1034  // We can't trivially remove internal targets, so skip
1035  // those.
1036  if (&TargetRC == RC)
1037  return false;
1038 
1039  LLVM_DEBUG(dbgs() << "Deleting outgoing edge from '" << N << "' to '"
1040  << *TargetN << "'\n");
1041  RC->removeOutgoingEdge(N, *TargetN);
1042  return true;
1043  });
1044 
1045  // Now do a batch removal of the internal ref edges left.
1046  auto NewRefSCCs = RC->removeInternalRefEdge(N, DeadTargets);
1047  if (!NewRefSCCs.empty()) {
1048  // The old RefSCC is dead, mark it as such.
1049  UR.InvalidatedRefSCCs.insert(RC);
1050 
1051  // Note that we don't bother to invalidate analyses as ref-edge
1052  // connectivity is not really observable in any way and is intended
1053  // exclusively to be used for ordering of transforms rather than for
1054  // analysis conclusions.
1055 
1056  // Update RC to the "bottom".
1057  assert(G.lookupSCC(N) == C && "Changed the SCC when splitting RefSCCs!");
1058  RC = &C->getOuterRefSCC();
1059  assert(G.lookupRefSCC(N) == RC && "Failed to update current RefSCC!");
1060 
1061  // The RC worklist is in reverse postorder, so we enqueue the new ones in
1062  // RPO except for the one which contains the source node as that is the
1063  // "bottom" we will continue processing in the bottom-up walk.
1064  assert(NewRefSCCs.front() == RC &&
1065  "New current RefSCC not first in the returned list!");
1066  for (RefSCC *NewRC : llvm::reverse(llvm::drop_begin(NewRefSCCs))) {
1067  assert(NewRC != RC && "Should not encounter the current RefSCC further "
1068  "in the postorder list of new RefSCCs.");
1069  UR.RCWorklist.insert(NewRC);
1070  LLVM_DEBUG(dbgs() << "Enqueuing a new RefSCC in the update worklist: "
1071  << *NewRC << "\n");
1072  }
1073  }
1074 
1075  // Next demote all the call edges that are now ref edges. This helps make
1076  // the SCCs small which should minimize the work below as we don't want to
1077  // form cycles that this would break.
1078  for (Node *RefTarget : DemotedCallTargets) {
1079  SCC &TargetC = *G.lookupSCC(*RefTarget);
1080  RefSCC &TargetRC = TargetC.getOuterRefSCC();
1081 
1082  // The easy case is when the target RefSCC is not this RefSCC. This is
1083  // only supported when the target RefSCC is a child of this RefSCC.
1084  if (&TargetRC != RC) {
1085 #ifdef EXPENSIVE_CHECKS
1086  assert(RC->isAncestorOf(TargetRC) &&
1087  "Cannot potentially form RefSCC cycles here!");
1088 #endif
1089  RC->switchOutgoingEdgeToRef(N, *RefTarget);
1090  LLVM_DEBUG(dbgs() << "Switch outgoing call edge to a ref edge from '" << N
1091  << "' to '" << *RefTarget << "'\n");
1092  continue;
1093  }
1094 
1095  // We are switching an internal call edge to a ref edge. This may split up
1096  // some SCCs.
1097  if (C != &TargetC) {
1098  // For separate SCCs this is trivial.
1099  RC->switchTrivialInternalEdgeToRef(N, *RefTarget);
1100  continue;
1101  }
1102 
1103  // Now update the call graph.
1104  C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, *RefTarget), G, N,
1105  C, AM, UR);
1106  }
1107 
1108  // We added a ref edge earlier for new call edges, promote those to call edges
1109  // alongside PromotedRefTargets.
1110  for (Node *E : NewCallEdges)
1111  PromotedRefTargets.insert(E);
1112 
1113  // Now promote ref edges into call edges.
1114  for (Node *CallTarget : PromotedRefTargets) {
1115  SCC &TargetC = *G.lookupSCC(*CallTarget);
1116  RefSCC &TargetRC = TargetC.getOuterRefSCC();
1117 
1118  // The easy case is when the target RefSCC is not this RefSCC. This is
1119  // only supported when the target RefSCC is a child of this RefSCC.
1120  if (&TargetRC != RC) {
1121 #ifdef EXPENSIVE_CHECKS
1122  assert(RC->isAncestorOf(TargetRC) &&
1123  "Cannot potentially form RefSCC cycles here!");
1124 #endif
1125  RC->switchOutgoingEdgeToCall(N, *CallTarget);
1126  LLVM_DEBUG(dbgs() << "Switch outgoing ref edge to a call edge from '" << N
1127  << "' to '" << *CallTarget << "'\n");
1128  continue;
1129  }
1130  LLVM_DEBUG(dbgs() << "Switch an internal ref edge to a call edge from '"
1131  << N << "' to '" << *CallTarget << "'\n");
1132 
1133  // Otherwise we are switching an internal ref edge to a call edge. This
1134  // may merge away some SCCs, and we add those to the UpdateResult. We also
1135  // need to make sure to update the worklist in the event SCCs have moved
1136  // before the current one in the post-order sequence
1137  bool HasFunctionAnalysisProxy = false;
1138  auto InitialSCCIndex = RC->find(*C) - RC->begin();
1139  bool FormedCycle = RC->switchInternalEdgeToCall(
1140  N, *CallTarget, [&](ArrayRef<SCC *> MergedSCCs) {
1141  for (SCC *MergedC : MergedSCCs) {
1142  assert(MergedC != &TargetC && "Cannot merge away the target SCC!");
1143 
1144  HasFunctionAnalysisProxy |=
1146  *MergedC) != nullptr;
1147 
1148  // Mark that this SCC will no longer be valid.
1149  UR.InvalidatedSCCs.insert(MergedC);
1150 
1151  // FIXME: We should really do a 'clear' here to forcibly release
1152  // memory, but we don't have a good way of doing that and
1153  // preserving the function analyses.
1154  auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
1155  PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1156  AM.invalidate(*MergedC, PA);
1157  }
1158  });
1159 
1160  // If we formed a cycle by creating this call, we need to update more data
1161  // structures.
1162  if (FormedCycle) {
1163  C = &TargetC;
1164  assert(G.lookupSCC(N) == C && "Failed to update current SCC!");
1165 
1166  // If one of the invalidated SCCs had a cached proxy to a function
1167  // analysis manager, we need to create a proxy in the new current SCC as
1168  // the invalidated SCCs had their functions moved.
1169  if (HasFunctionAnalysisProxy)
1171 
1172  // Any analyses cached for this SCC are no longer precise as the shape
1173  // has changed by introducing this cycle. However, we have taken care to
1174  // update the proxies so it remains valide.
1175  auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
1176  PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
1177  AM.invalidate(*C, PA);
1178  }
1179  auto NewSCCIndex = RC->find(*C) - RC->begin();
1180  // If we have actually moved an SCC to be topologically "below" the current
1181  // one due to merging, we will need to revisit the current SCC after
1182  // visiting those moved SCCs.
1183  //
1184  // It is critical that we *do not* revisit the current SCC unless we
1185  // actually move SCCs in the process of merging because otherwise we may
1186  // form a cycle where an SCC is split apart, merged, split, merged and so
1187  // on infinitely.
1188  if (InitialSCCIndex < NewSCCIndex) {
1189  // Put our current SCC back onto the worklist as we'll visit other SCCs
1190  // that are now definitively ordered prior to the current one in the
1191  // post-order sequence, and may end up observing more precise context to
1192  // optimize the current SCC.
1193  UR.CWorklist.insert(C);
1194  LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist: " << *C
1195  << "\n");
1196  // Enqueue in reverse order as we pop off the back of the worklist.
1197  for (SCC &MovedC : llvm::reverse(make_range(RC->begin() + InitialSCCIndex,
1198  RC->begin() + NewSCCIndex))) {
1199  UR.CWorklist.insert(&MovedC);
1200  LLVM_DEBUG(dbgs() << "Enqueuing a newly earlier in post-order SCC: "
1201  << MovedC << "\n");
1202  }
1203  }
1204  }
1205 
1206  assert(!UR.InvalidatedSCCs.count(C) && "Invalidated the current SCC!");
1207  assert(!UR.InvalidatedRefSCCs.count(RC) && "Invalidated the current RefSCC!");
1208  assert(&C->getOuterRefSCC() == RC && "Current SCC not in current RefSCC!");
1209 
1210  // Record the current RefSCC and SCC for higher layers of the CGSCC pass
1211  // manager now that all the updates have been applied.
1212  if (RC != &InitialRC)
1213  UR.UpdatedRC = RC;
1214  if (C != &InitialC)
1215  UR.UpdatedC = C;
1216 
1217  return *C;
1218 }
1219 
1224  return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR, FAM,
1225  /* FunctionPass */ true);
1226 }
1231  return updateCGAndAnalysisManagerForPass(G, InitialC, N, AM, UR, FAM,
1232  /* FunctionPass */ false);
1233 }
llvm::PreservedAnalyses
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:155
llvm::OuterAnalysisManagerProxy
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1061
llvm
---------------------— PointerInfo ------------------------------------—
Definition: AllocatorList.h:23
llvm::LazyCallGraph::buildRefSCCs
void buildRefSCCs()
Definition: LazyCallGraph.cpp:1927
llvm::LazyCallGraph::visitReferences
static void visitReferences(SmallVectorImpl< Constant * > &Worklist, SmallPtrSetImpl< Constant * > &Visited, CallbackT Callback)
Recursively visits the defined functions whose address is reachable from every constant in the Workli...
Definition: LazyCallGraph.h:1089
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:1966
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:266
llvm::TimeTraceScope
The TimeTraceScope is a helper class to call the begin and end functions of the time trace profiler.
Definition: TimeProfiler.h:65
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:279
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:779
InstIterator.h
llvm::Function
Definition: Function.h:61
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:684
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:91
llvm::SmallVector
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1168
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:940
llvm::AllAnalysesOn
This templated class represents "all analyses that operate over <a particular IR unit>" (e....
Definition: PassManager.h:93
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:1728
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:677
llvm::PreservedAnalyses::abandon
void abandon()
Mark an analysis as abandoned.
Definition: PassManager.h:209
FAM
FunctionAnalysisManager FAM
Definition: PassBuilderBindings.cpp:59
Passes
const char * Passes
Definition: PassBuilderBindings.cpp:46
llvm::ModuleAnalysisManager
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
Definition: PassManager.h:912
llvm::reverse
auto reverse(ContainerTy &&C, std::enable_if_t< has_rbegin< ContainerTy >::value > *=nullptr)
Definition: STLExtras.h:329
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:449
STLExtras.h
llvm::LazyCallGraph::postorder_ref_scc_begin
postorder_ref_scc_iterator postorder_ref_scc_begin()
Definition: LazyCallGraph.h:935
LLVM_DEBUG
#define LLVM_DEBUG(X)
Definition: Debug.h:101
F
#define F(x, y, z)
Definition: MD5.cpp:56
llvm::FunctionAnalysisManagerCGSCCProxy::Result
Definition: CGSCCPassManager.h:408
llvm::PreservedAnalyses::intersect
void intersect(const PreservedAnalyses &Arg)
Intersect this set with another in place.
Definition: PassManager.h:227
llvm::dbgs
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
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:333
llvm::LazyCallGraph::SCC
An SCC of the call graph.
Definition: LazyCallGraph.h:422
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:154
llvm::Instruction
Definition: Instruction.h:45
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:140
llvm::LazyCallGraph::RefSCC
A RefSCC of the call graph.
Definition: LazyCallGraph.h:538
SmallPtrSet.h
llvm::LazyCallGraph::lookupSCC
SCC * lookupSCC(Node &N) const
Lookup a function's SCC in the graph.
Definition: LazyCallGraph.h:960
llvm::AnalysisManager::Invalidator
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:666
LazyCallGraph.h
llvm::FunctionAnalysisManagerCGSCCProxy::Result::invalidate
bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA, CGSCCAnalysisManager::Invalidator &Inv)
Definition: CGSCCPassManager.cpp:698
G
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
llvm::SmallMapVector
A MapVector that performs no allocations if smaller than a certain size.
Definition: MapVector.h:232
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:299
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:1220
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:176
llvm::SmallPriorityWorklist
A version of PriorityWorklist that selects small size optimized data structures for the vector and ma...
Definition: PriorityWorklist.h:256
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:72
I
#define I(x, y, z)
Definition: MD5.cpp:59
llvm::CGSCCUpdateResult::CWorklist
SmallPriorityWorklist< LazyCallGraph::SCC *, 1 > & CWorklist
Worklist of the SCCs queued for processing.
Definition: CGSCCPassManager.h:263
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:68
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:129
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:338
llvm::Module
A Module instance is used to store all the information related to an LLVM module.
Definition: Module.h:67
llvm::LazyCallGraph::Node
A node in the call graph.
Definition: LazyCallGraph.h:318
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:382
updateCGAndAnalysisManagerForPass
static LazyCallGraph::SCC & updateCGAndAnalysisManagerForPass(LazyCallGraph &G, LazyCallGraph::SCC &InitialC, LazyCallGraph::Node &N, CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR, FunctionAnalysisManager &FAM, bool FunctionPass)
Definition: CGSCCPassManager.cpp:885
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:292
llvm::LazyCallGraph::Edge
A class used to represent edges in the call graph.
Definition: LazyCallGraph.h:134
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:314
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:1554
llvm::PreservedAnalyses::areAllPreserved
bool areAllPreserved() const
Test whether all analyses are preserved (and none are abandoned).
Definition: PassManager.h:330
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:824
llvm::LazyCallGraph::postorder_ref_scc_end
postorder_ref_scc_iterator postorder_ref_scc_end()
Definition: LazyCallGraph.h:941
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:472
Callee
amdgpu Simplify well known AMD library false FunctionCallee Callee
Definition: AMDGPULibCalls.cpp:206
Constant.h
llvm::CGSCCUpdateResult
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
Definition: CGSCCPassManager.h:238
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:321
llvm::PreservedAnalyses::all
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:161
llvm::LazyCallGraphAnalysis
An analysis pass which computes the call graph for a module.
Definition: LazyCallGraph.h:1276
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:798
Casting.h
llvm::ModuleToPostOrderCGSCCPassAdaptor::run
PreservedAnalyses run(Module &M, ModuleAnalysisManager &AM)
Runs the CGSCC pass across every SCC in the module.
Definition: CGSCCPassManager.cpp:140
PassManager.h
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:1227
llvm::CGSCCAnalysisManagerModuleProxy::Result
We need a specialized result for the CGSCCAnalysisManagerModuleProxy so it can have access to the cal...
Definition: CGSCCPassManager.h:179
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:191
SmallVector.h
N
#define N
llvm::CGSCCUpdateResult::UpdatedRC
LazyCallGraph::RefSCC * UpdatedRC
If non-null, the updated current RefSCC being processed.
Definition: CGSCCPassManager.h:289
llvm::LazyCallGraph::SCC::getOuterRefSCC
RefSCC & getOuterRefSCC() const
Definition: LazyCallGraph.h:484
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:780
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:313
llvm::AnalysisManager
A container for analyses that lazily runs them and caches their results.
Definition: InstructionSimplify.h:44
llvm::PassInstrumentationAnalysis
Pseudo-analysis pass that exposes the PassInstrumentation to pass managers.
Definition: PassManager.h:599
llvm::InnerAnalysisManagerProxy
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:936
llvm::FunctionPass
FunctionPass class - This class is used to implement most global optimizations.
Definition: Pass.h:298
llvm::cl::desc
Definition: CommandLine.h:414
llvm::LazyCallGraph
A lazily constructed view of the call graph of a module.
Definition: LazyCallGraph.h:113
raw_ostream.h
llvm::FunctionAnalysisManagerCGSCCProxy
A proxy from a FunctionAnalysisManager to an SCC.
Definition: CGSCCPassManager.h:405
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:271
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:999
CGAM
CGSCCAnalysisManager CGAM
Definition: PassBuilderBindings.cpp:60
llvm::Value
LLVM Value Representation.
Definition: Value.h:75
TimeProfiler.h
Debug.h
SetVector.h
llvm::CGSCCUpdateResult::RCWorklist
SmallPriorityWorklist< LazyCallGraph::RefSCC *, 1 > & RCWorklist
Worklist of the RefSCCs queued for processing.
Definition: CGSCCPassManager.h:248
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:364