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