LLVM  9.0.0svn
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/CallSite.h"
19 #include "llvm/IR/Constant.h"
20 #include "llvm/IR/InstIterator.h"
21 #include "llvm/IR/Instruction.h"
22 #include "llvm/IR/PassManager.h"
23 #include "llvm/Support/Casting.h"
24 #include "llvm/Support/Debug.h"
26 #include <algorithm>
27 #include <cassert>
28 #include <iterator>
29 
30 #define DEBUG_TYPE "cgscc"
31 
32 using namespace llvm;
33 
34 // Explicit template instantiations and specialization definitions for core
35 // template typedefs.
36 namespace llvm {
37 
38 // Explicit instantiations for the core proxy templates.
45  LazyCallGraph::SCC, LazyCallGraph &>;
47 
48 /// Explicitly specialize the pass manager run method to handle call graph
49 /// updates.
50 template <>
52 PassManager<LazyCallGraph::SCC, CGSCCAnalysisManager, LazyCallGraph &,
53  CGSCCUpdateResult &>::run(LazyCallGraph::SCC &InitialC,
54  CGSCCAnalysisManager &AM,
55  LazyCallGraph &G, CGSCCUpdateResult &UR) {
56  // Request PassInstrumentation from analysis manager, will use it to run
57  // instrumenting callbacks for the passes later.
60 
62 
63  if (DebugLogging)
64  dbgs() << "Starting CGSCC pass manager run.\n";
65 
66  // The SCC may be refined while we are running passes over it, so set up
67  // a pointer that we can update.
68  LazyCallGraph::SCC *C = &InitialC;
69 
70  for (auto &Pass : Passes) {
71  if (DebugLogging)
72  dbgs() << "Running pass: " << Pass->name() << " on " << *C << "\n";
73 
74  // Check the PassInstrumentation's BeforePass callbacks before running the
75  // pass, skip its execution completely if asked to (callback returns false).
76  if (!PI.runBeforePass(*Pass, *C))
77  continue;
78 
79  PreservedAnalyses PassPA = Pass->run(*C, AM, G, UR);
80 
81  if (UR.InvalidatedSCCs.count(C))
82  PI.runAfterPassInvalidated<LazyCallGraph::SCC>(*Pass);
83  else
84  PI.runAfterPass<LazyCallGraph::SCC>(*Pass, *C);
85 
86  // Update the SCC if necessary.
87  C = UR.UpdatedC ? UR.UpdatedC : C;
88 
89  // If the CGSCC pass wasn't able to provide a valid updated SCC, the
90  // current SCC may simply need to be skipped if invalid.
91  if (UR.InvalidatedSCCs.count(C)) {
92  LLVM_DEBUG(dbgs() << "Skipping invalidated root or island SCC!\n");
93  break;
94  }
95  // Check that we didn't miss any update scenario.
96  assert(C->begin() != C->end() && "Cannot have an empty SCC!");
97 
98  // Update the analysis manager as each pass runs and potentially
99  // invalidates analyses.
100  AM.invalidate(*C, PassPA);
101 
102  // Finally, we intersect the final preserved analyses to compute the
103  // aggregate preserved set for this pass manager.
104  PA.intersect(std::move(PassPA));
105 
106  // FIXME: Historically, the pass managers all called the LLVM context's
107  // yield function here. We don't have a generic way to acquire the
108  // context and it isn't yet clear what the right pattern is for yielding
109  // in the new pass manager so it is currently omitted.
110  // ...getContext().yield();
111  }
112 
113  // Before we mark all of *this* SCC's analyses as preserved below, intersect
114  // this with the cross-SCC preserved analysis set. This is used to allow
115  // CGSCC passes to mutate ancestor SCCs and still trigger proper invalidation
116  // for them.
117  UR.CrossSCCPA.intersect(PA);
118 
119  // Invalidation was handled after each pass in the above loop for the current
120  // SCC. Therefore, the remaining analysis results in the AnalysisManager are
121  // preserved. We mark this with a set so that we don't need to inspect each
122  // one individually.
123  PA.preserveSet<AllAnalysesOn<LazyCallGraph::SCC>>();
124 
125  if (DebugLogging)
126  dbgs() << "Finished CGSCC pass manager run.\n";
127 
128  return PA;
129 }
130 
132  Module &M, const PreservedAnalyses &PA,
134  // If literally everything is preserved, we're done.
135  if (PA.areAllPreserved())
136  return false; // This is still a valid proxy.
137 
138  // If this proxy or the call graph is going to be invalidated, we also need
139  // to clear all the keys coming from that analysis.
140  //
141  // We also directly invalidate the FAM's module proxy if necessary, and if
142  // that proxy isn't preserved we can't preserve this proxy either. We rely on
143  // it to handle module -> function analysis invalidation in the face of
144  // structural changes and so if it's unavailable we conservatively clear the
145  // entire SCC layer as well rather than trying to do invalidation ourselves.
147  if (!(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>()) ||
148  Inv.invalidate<LazyCallGraphAnalysis>(M, PA) ||
150  InnerAM->clear();
151 
152  // And the proxy itself should be marked as invalid so that we can observe
153  // the new call graph. This isn't strictly necessary because we cheat
154  // above, but is still useful.
155  return true;
156  }
157 
158  // Directly check if the relevant set is preserved so we can short circuit
159  // invalidating SCCs below.
160  bool AreSCCAnalysesPreserved =
162 
163  // Ok, we have a graph, so we can propagate the invalidation down into it.
164  G->buildRefSCCs();
165  for (auto &RC : G->postorder_ref_sccs())
166  for (auto &C : RC) {
168 
169  // Check to see whether the preserved set needs to be adjusted based on
170  // module-level analysis invalidation triggering deferred invalidation
171  // for this SCC.
172  if (auto *OuterProxy =
173  InnerAM->getCachedResult<ModuleAnalysisManagerCGSCCProxy>(C))
174  for (const auto &OuterInvalidationPair :
175  OuterProxy->getOuterInvalidations()) {
176  AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
177  const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
178  if (Inv.invalidate(OuterAnalysisID, M, PA)) {
179  if (!InnerPA)
180  InnerPA = PA;
181  for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
182  InnerPA->abandon(InnerAnalysisID);
183  }
184  }
185 
186  // Check if we needed a custom PA set. If so we'll need to run the inner
187  // invalidation.
188  if (InnerPA) {
189  InnerAM->invalidate(C, *InnerPA);
190  continue;
191  }
192 
193  // Otherwise we only need to do invalidation if the original PA set didn't
194  // preserve all SCC analyses.
195  if (!AreSCCAnalysesPreserved)
196  InnerAM->invalidate(C, PA);
197  }
198 
199  // Return false to indicate that this result is still a valid proxy.
200  return false;
201 }
202 
203 template <>
205 CGSCCAnalysisManagerModuleProxy::run(Module &M, ModuleAnalysisManager &AM) {
206  // Force the Function analysis manager to also be available so that it can
207  // be accessed in an SCC analysis and proxied onward to function passes.
208  // FIXME: It is pretty awkward to just drop the result here and assert that
209  // we can find it again later.
211 
212  return Result(*InnerAM, AM.getResult<LazyCallGraphAnalysis>(M));
213 }
214 
215 AnalysisKey FunctionAnalysisManagerCGSCCProxy::Key;
216 
219  CGSCCAnalysisManager &AM,
220  LazyCallGraph &CG) {
221  // Collect the FunctionAnalysisManager from the Module layer and use that to
222  // build the proxy result.
223  //
224  // This allows us to rely on the FunctionAnalysisMangaerModuleProxy to
225  // invalidate the function analyses.
226  auto &MAM = AM.getResult<ModuleAnalysisManagerCGSCCProxy>(C, CG).getManager();
227  Module &M = *C.begin()->getFunction().getParent();
228  auto *FAMProxy = MAM.getCachedResult<FunctionAnalysisManagerModuleProxy>(M);
229  assert(FAMProxy && "The CGSCC pass manager requires that the FAM module "
230  "proxy is run on the module prior to entering the CGSCC "
231  "walk.");
232 
233  // Note that we special-case invalidation handling of this proxy in the CGSCC
234  // analysis manager's Module proxy. This avoids the need to do anything
235  // special here to recompute all of this if ever the FAM's module proxy goes
236  // away.
237  return Result(FAMProxy->getManager());
238 }
239 
241  LazyCallGraph::SCC &C, const PreservedAnalyses &PA,
243  // If literally everything is preserved, we're done.
244  if (PA.areAllPreserved())
245  return false; // This is still a valid proxy.
246 
247  // If this proxy isn't marked as preserved, then even if the result remains
248  // valid, the key itself may no longer be valid, so we clear everything.
249  //
250  // Note that in order to preserve this proxy, a module pass must ensure that
251  // the FAM has been completely updated to handle the deletion of functions.
252  // Specifically, any FAM-cached results for those functions need to have been
253  // forcibly cleared. When preserved, this proxy will only invalidate results
254  // cached on functions *still in the module* at the end of the module pass.
256  if (!PAC.preserved() && !PAC.preservedSet<AllAnalysesOn<LazyCallGraph::SCC>>()) {
257  for (LazyCallGraph::Node &N : C)
258  FAM->clear(N.getFunction(), N.getFunction().getName());
259 
260  return true;
261  }
262 
263  // Directly check if the relevant set is preserved.
264  bool AreFunctionAnalysesPreserved =
266 
267  // Now walk all the functions to see if any inner analysis invalidation is
268  // necessary.
269  for (LazyCallGraph::Node &N : C) {
270  Function &F = N.getFunction();
271  Optional<PreservedAnalyses> FunctionPA;
272 
273  // Check to see whether the preserved set needs to be pruned based on
274  // SCC-level analysis invalidation that triggers deferred invalidation
275  // registered with the outer analysis manager proxy for this function.
276  if (auto *OuterProxy =
277  FAM->getCachedResult<CGSCCAnalysisManagerFunctionProxy>(F))
278  for (const auto &OuterInvalidationPair :
279  OuterProxy->getOuterInvalidations()) {
280  AnalysisKey *OuterAnalysisID = OuterInvalidationPair.first;
281  const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
282  if (Inv.invalidate(OuterAnalysisID, C, PA)) {
283  if (!FunctionPA)
284  FunctionPA = PA;
285  for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
286  FunctionPA->abandon(InnerAnalysisID);
287  }
288  }
289 
290  // Check if we needed a custom PA set, and if so we'll need to run the
291  // inner invalidation.
292  if (FunctionPA) {
293  FAM->invalidate(F, *FunctionPA);
294  continue;
295  }
296 
297  // Otherwise we only need to do invalidation if the original PA set didn't
298  // preserve all function analyses.
299  if (!AreFunctionAnalysesPreserved)
300  FAM->invalidate(F, PA);
301  }
302 
303  // Return false to indicate that this result is still a valid proxy.
304  return false;
305 }
306 
307 } // end namespace llvm
308 
309 /// When a new SCC is created for the graph and there might be function
310 /// analysis results cached for the functions now in that SCC two forms of
311 /// updates are required.
312 ///
313 /// First, a proxy from the SCC to the FunctionAnalysisManager needs to be
314 /// created so that any subsequent invalidation events to the SCC are
315 /// propagated to the function analysis results cached for functions within it.
316 ///
317 /// Second, if any of the functions within the SCC have analysis results with
318 /// outer analysis dependencies, then those dependencies would point to the
319 /// *wrong* SCC's analysis result. We forcibly invalidate the necessary
320 /// function analyses so that they don't retain stale handles.
322  LazyCallGraph &G,
323  CGSCCAnalysisManager &AM) {
324  // Get the relevant function analysis manager.
325  auto &FAM =
327 
328  // Now walk the functions in this SCC and invalidate any function analysis
329  // results that might have outer dependencies on an SCC analysis.
330  for (LazyCallGraph::Node &N : C) {
331  Function &F = N.getFunction();
332 
333  auto *OuterProxy =
334  FAM.getCachedResult<CGSCCAnalysisManagerFunctionProxy>(F);
335  if (!OuterProxy)
336  // No outer analyses were queried, nothing to do.
337  continue;
338 
339  // Forcibly abandon all the inner analyses with dependencies, but
340  // invalidate nothing else.
341  auto PA = PreservedAnalyses::all();
342  for (const auto &OuterInvalidationPair :
343  OuterProxy->getOuterInvalidations()) {
344  const auto &InnerAnalysisIDs = OuterInvalidationPair.second;
345  for (AnalysisKey *InnerAnalysisID : InnerAnalysisIDs)
346  PA.abandon(InnerAnalysisID);
347  }
348 
349  // Now invalidate anything we found.
350  FAM.invalidate(F, PA);
351  }
352 }
353 
354 /// Helper function to update both the \c CGSCCAnalysisManager \p AM and the \c
355 /// CGSCCPassManager's \c CGSCCUpdateResult \p UR based on a range of newly
356 /// added SCCs.
357 ///
358 /// The range of new SCCs must be in postorder already. The SCC they were split
359 /// out of must be provided as \p C. The current node being mutated and
360 /// triggering updates must be passed as \p N.
361 ///
362 /// This function returns the SCC containing \p N. This will be either \p C if
363 /// no new SCCs have been split out, or it will be the new SCC containing \p N.
364 template <typename SCCRangeT>
365 static LazyCallGraph::SCC *
366 incorporateNewSCCRange(const SCCRangeT &NewSCCRange, LazyCallGraph &G,
369  using SCC = LazyCallGraph::SCC;
370 
371  if (NewSCCRange.begin() == NewSCCRange.end())
372  return C;
373 
374  // Add the current SCC to the worklist as its shape has changed.
375  UR.CWorklist.insert(C);
376  LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist:" << *C
377  << "\n");
378 
379  SCC *OldC = C;
380 
381  // Update the current SCC. Note that if we have new SCCs, this must actually
382  // change the SCC.
383  assert(C != &*NewSCCRange.begin() &&
384  "Cannot insert new SCCs without changing current SCC!");
385  C = &*NewSCCRange.begin();
386  assert(G.lookupSCC(N) == C && "Failed to update current SCC!");
387 
388  // If we had a cached FAM proxy originally, we will want to create more of
389  // them for each SCC that was split off.
390  bool NeedFAMProxy =
392 
393  // We need to propagate an invalidation call to all but the newly current SCC
394  // because the outer pass manager won't do that for us after splitting them.
395  // FIXME: We should accept a PreservedAnalysis from the CG updater so that if
396  // there are preserved analysis we can avoid invalidating them here for
397  // split-off SCCs.
398  // We know however that this will preserve any FAM proxy so go ahead and mark
399  // that.
402  AM.invalidate(*OldC, PA);
403 
404  // Ensure the now-current SCC's function analyses are updated.
405  if (NeedFAMProxy)
406  updateNewSCCFunctionAnalyses(*C, G, AM);
407 
408  for (SCC &NewC : llvm::reverse(make_range(std::next(NewSCCRange.begin()),
409  NewSCCRange.end()))) {
410  assert(C != &NewC && "No need to re-visit the current SCC!");
411  assert(OldC != &NewC && "Already handled the original SCC!");
412  UR.CWorklist.insert(&NewC);
413  LLVM_DEBUG(dbgs() << "Enqueuing a newly formed SCC:" << NewC << "\n");
414 
415  // Ensure new SCCs' function analyses are updated.
416  if (NeedFAMProxy)
417  updateNewSCCFunctionAnalyses(NewC, G, AM);
418 
419  // Also propagate a normal invalidation to the new SCC as only the current
420  // will get one from the pass manager infrastructure.
421  AM.invalidate(NewC, PA);
422  }
423  return C;
424 }
425 
429  using Node = LazyCallGraph::Node;
430  using Edge = LazyCallGraph::Edge;
431  using SCC = LazyCallGraph::SCC;
432  using RefSCC = LazyCallGraph::RefSCC;
433 
434  RefSCC &InitialRC = InitialC.getOuterRefSCC();
435  SCC *C = &InitialC;
436  RefSCC *RC = &InitialRC;
437  Function &F = N.getFunction();
438 
439  // Walk the function body and build up the set of retained, promoted, and
440  // demoted edges.
443  SmallPtrSet<Node *, 16> RetainedEdges;
444  SmallSetVector<Node *, 4> PromotedRefTargets;
445  SmallSetVector<Node *, 4> DemotedCallTargets;
446 
447  // First walk the function and handle all called functions. We do this first
448  // because if there is a single call edge, whether there are ref edges is
449  // irrelevant.
450  for (Instruction &I : instructions(F))
451  if (auto CS = CallSite(&I))
452  if (Function *Callee = CS.getCalledFunction())
453  if (Visited.insert(Callee).second && !Callee->isDeclaration()) {
454  Node &CalleeN = *G.lookup(*Callee);
455  Edge *E = N->lookup(CalleeN);
456  // FIXME: We should really handle adding new calls. While it will
457  // make downstream usage more complex, there is no fundamental
458  // limitation and it will allow passes within the CGSCC to be a bit
459  // more flexible in what transforms they can do. Until then, we
460  // verify that new calls haven't been introduced.
461  assert(E && "No function transformations should introduce *new* "
462  "call edges! Any new calls should be modeled as "
463  "promoted existing ref edges!");
464  bool Inserted = RetainedEdges.insert(&CalleeN).second;
465  (void)Inserted;
466  assert(Inserted && "We should never visit a function twice.");
467  if (!E->isCall())
468  PromotedRefTargets.insert(&CalleeN);
469  }
470 
471  // Now walk all references.
472  for (Instruction &I : instructions(F))
473  for (Value *Op : I.operand_values())
474  if (auto *C = dyn_cast<Constant>(Op))
475  if (Visited.insert(C).second)
476  Worklist.push_back(C);
477 
478  auto VisitRef = [&](Function &Referee) {
479  Node &RefereeN = *G.lookup(Referee);
480  Edge *E = N->lookup(RefereeN);
481  // FIXME: Similarly to new calls, we also currently preclude
482  // introducing new references. See above for details.
483  assert(E && "No function transformations should introduce *new* ref "
484  "edges! Any new ref edges would require IPO which "
485  "function passes aren't allowed to do!");
486  bool Inserted = RetainedEdges.insert(&RefereeN).second;
487  (void)Inserted;
488  assert(Inserted && "We should never visit a function twice.");
489  if (E->isCall())
490  DemotedCallTargets.insert(&RefereeN);
491  };
492  LazyCallGraph::visitReferences(Worklist, Visited, VisitRef);
493 
494  // Include synthetic reference edges to known, defined lib functions.
495  for (auto *F : G.getLibFunctions())
496  // While the list of lib functions doesn't have repeats, don't re-visit
497  // anything handled above.
498  if (!Visited.count(F))
499  VisitRef(*F);
500 
501  // First remove all of the edges that are no longer present in this function.
502  // The first step makes these edges uniformly ref edges and accumulates them
503  // into a separate data structure so removal doesn't invalidate anything.
504  SmallVector<Node *, 4> DeadTargets;
505  for (Edge &E : *N) {
506  if (RetainedEdges.count(&E.getNode()))
507  continue;
508 
509  SCC &TargetC = *G.lookupSCC(E.getNode());
510  RefSCC &TargetRC = TargetC.getOuterRefSCC();
511  if (&TargetRC == RC && E.isCall()) {
512  if (C != &TargetC) {
513  // For separate SCCs this is trivial.
514  RC->switchTrivialInternalEdgeToRef(N, E.getNode());
515  } else {
516  // Now update the call graph.
517  C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, E.getNode()),
518  G, N, C, AM, UR);
519  }
520  }
521 
522  // Now that this is ready for actual removal, put it into our list.
523  DeadTargets.push_back(&E.getNode());
524  }
525  // Remove the easy cases quickly and actually pull them out of our list.
526  DeadTargets.erase(
527  llvm::remove_if(DeadTargets,
528  [&](Node *TargetN) {
529  SCC &TargetC = *G.lookupSCC(*TargetN);
530  RefSCC &TargetRC = TargetC.getOuterRefSCC();
531 
532  // We can't trivially remove internal targets, so skip
533  // those.
534  if (&TargetRC == RC)
535  return false;
536 
537  RC->removeOutgoingEdge(N, *TargetN);
538  LLVM_DEBUG(dbgs() << "Deleting outgoing edge from '"
539  << N << "' to '" << TargetN << "'\n");
540  return true;
541  }),
542  DeadTargets.end());
543 
544  // Now do a batch removal of the internal ref edges left.
545  auto NewRefSCCs = RC->removeInternalRefEdge(N, DeadTargets);
546  if (!NewRefSCCs.empty()) {
547  // The old RefSCC is dead, mark it as such.
548  UR.InvalidatedRefSCCs.insert(RC);
549 
550  // Note that we don't bother to invalidate analyses as ref-edge
551  // connectivity is not really observable in any way and is intended
552  // exclusively to be used for ordering of transforms rather than for
553  // analysis conclusions.
554 
555  // Update RC to the "bottom".
556  assert(G.lookupSCC(N) == C && "Changed the SCC when splitting RefSCCs!");
557  RC = &C->getOuterRefSCC();
558  assert(G.lookupRefSCC(N) == RC && "Failed to update current RefSCC!");
559 
560  // The RC worklist is in reverse postorder, so we enqueue the new ones in
561  // RPO except for the one which contains the source node as that is the
562  // "bottom" we will continue processing in the bottom-up walk.
563  assert(NewRefSCCs.front() == RC &&
564  "New current RefSCC not first in the returned list!");
565  for (RefSCC *NewRC : llvm::reverse(make_range(std::next(NewRefSCCs.begin()),
566  NewRefSCCs.end()))) {
567  assert(NewRC != RC && "Should not encounter the current RefSCC further "
568  "in the postorder list of new RefSCCs.");
569  UR.RCWorklist.insert(NewRC);
570  LLVM_DEBUG(dbgs() << "Enqueuing a new RefSCC in the update worklist: "
571  << *NewRC << "\n");
572  }
573  }
574 
575  // Next demote all the call edges that are now ref edges. This helps make
576  // the SCCs small which should minimize the work below as we don't want to
577  // form cycles that this would break.
578  for (Node *RefTarget : DemotedCallTargets) {
579  SCC &TargetC = *G.lookupSCC(*RefTarget);
580  RefSCC &TargetRC = TargetC.getOuterRefSCC();
581 
582  // The easy case is when the target RefSCC is not this RefSCC. This is
583  // only supported when the target RefSCC is a child of this RefSCC.
584  if (&TargetRC != RC) {
585  assert(RC->isAncestorOf(TargetRC) &&
586  "Cannot potentially form RefSCC cycles here!");
587  RC->switchOutgoingEdgeToRef(N, *RefTarget);
588  LLVM_DEBUG(dbgs() << "Switch outgoing call edge to a ref edge from '" << N
589  << "' to '" << *RefTarget << "'\n");
590  continue;
591  }
592 
593  // We are switching an internal call edge to a ref edge. This may split up
594  // some SCCs.
595  if (C != &TargetC) {
596  // For separate SCCs this is trivial.
597  RC->switchTrivialInternalEdgeToRef(N, *RefTarget);
598  continue;
599  }
600 
601  // Now update the call graph.
602  C = incorporateNewSCCRange(RC->switchInternalEdgeToRef(N, *RefTarget), G, N,
603  C, AM, UR);
604  }
605 
606  // Now promote ref edges into call edges.
607  for (Node *CallTarget : PromotedRefTargets) {
608  SCC &TargetC = *G.lookupSCC(*CallTarget);
609  RefSCC &TargetRC = TargetC.getOuterRefSCC();
610 
611  // The easy case is when the target RefSCC is not this RefSCC. This is
612  // only supported when the target RefSCC is a child of this RefSCC.
613  if (&TargetRC != RC) {
614  assert(RC->isAncestorOf(TargetRC) &&
615  "Cannot potentially form RefSCC cycles here!");
616  RC->switchOutgoingEdgeToCall(N, *CallTarget);
617  LLVM_DEBUG(dbgs() << "Switch outgoing ref edge to a call edge from '" << N
618  << "' to '" << *CallTarget << "'\n");
619  continue;
620  }
621  LLVM_DEBUG(dbgs() << "Switch an internal ref edge to a call edge from '"
622  << N << "' to '" << *CallTarget << "'\n");
623 
624  // Otherwise we are switching an internal ref edge to a call edge. This
625  // may merge away some SCCs, and we add those to the UpdateResult. We also
626  // need to make sure to update the worklist in the event SCCs have moved
627  // before the current one in the post-order sequence
628  bool HasFunctionAnalysisProxy = false;
629  auto InitialSCCIndex = RC->find(*C) - RC->begin();
630  bool FormedCycle = RC->switchInternalEdgeToCall(
631  N, *CallTarget, [&](ArrayRef<SCC *> MergedSCCs) {
632  for (SCC *MergedC : MergedSCCs) {
633  assert(MergedC != &TargetC && "Cannot merge away the target SCC!");
634 
635  HasFunctionAnalysisProxy |=
637  *MergedC) != nullptr;
638 
639  // Mark that this SCC will no longer be valid.
640  UR.InvalidatedSCCs.insert(MergedC);
641 
642  // FIXME: We should really do a 'clear' here to forcibly release
643  // memory, but we don't have a good way of doing that and
644  // preserving the function analyses.
645  auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
646  PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
647  AM.invalidate(*MergedC, PA);
648  }
649  });
650 
651  // If we formed a cycle by creating this call, we need to update more data
652  // structures.
653  if (FormedCycle) {
654  C = &TargetC;
655  assert(G.lookupSCC(N) == C && "Failed to update current SCC!");
656 
657  // If one of the invalidated SCCs had a cached proxy to a function
658  // analysis manager, we need to create a proxy in the new current SCC as
659  // the invalidated SCCs had their functions moved.
660  if (HasFunctionAnalysisProxy)
662 
663  // Any analyses cached for this SCC are no longer precise as the shape
664  // has changed by introducing this cycle. However, we have taken care to
665  // update the proxies so it remains valide.
666  auto PA = PreservedAnalyses::allInSet<AllAnalysesOn<Function>>();
667  PA.preserve<FunctionAnalysisManagerCGSCCProxy>();
668  AM.invalidate(*C, PA);
669  }
670  auto NewSCCIndex = RC->find(*C) - RC->begin();
671  // If we have actually moved an SCC to be topologically "below" the current
672  // one due to merging, we will need to revisit the current SCC after
673  // visiting those moved SCCs.
674  //
675  // It is critical that we *do not* revisit the current SCC unless we
676  // actually move SCCs in the process of merging because otherwise we may
677  // form a cycle where an SCC is split apart, merged, split, merged and so
678  // on infinitely.
679  if (InitialSCCIndex < NewSCCIndex) {
680  // Put our current SCC back onto the worklist as we'll visit other SCCs
681  // that are now definitively ordered prior to the current one in the
682  // post-order sequence, and may end up observing more precise context to
683  // optimize the current SCC.
684  UR.CWorklist.insert(C);
685  LLVM_DEBUG(dbgs() << "Enqueuing the existing SCC in the worklist: " << *C
686  << "\n");
687  // Enqueue in reverse order as we pop off the back of the worklist.
688  for (SCC &MovedC : llvm::reverse(make_range(RC->begin() + InitialSCCIndex,
689  RC->begin() + NewSCCIndex))) {
690  UR.CWorklist.insert(&MovedC);
691  LLVM_DEBUG(dbgs() << "Enqueuing a newly earlier in post-order SCC: "
692  << MovedC << "\n");
693  }
694  }
695  }
696 
697  assert(!UR.InvalidatedSCCs.count(C) && "Invalidated the current SCC!");
698  assert(!UR.InvalidatedRefSCCs.count(RC) && "Invalidated the current RefSCC!");
699  assert(&C->getOuterRefSCC() == RC && "Current SCC not in current RefSCC!");
700 
701  // Record the current RefSCC and SCC for higher layers of the CGSCC pass
702  // manager now that all the updates have been applied.
703  if (RC != &InitialRC)
704  UR.UpdatedRC = RC;
705  if (C != &InitialC)
706  UR.UpdatedC = C;
707 
708  return *C;
709 }
Pass interface - Implemented by all &#39;passes&#39;.
Definition: Pass.h:80
void abandon()
Mark an analysis as abandoned.
Definition: PassManager.h:207
uint64_t CallInst * C
Result run(LazyCallGraph::SCC &C, CGSCCAnalysisManager &AM, LazyCallGraph &)
Computes the FunctionAnalysisManager and stores it in the result proxy.
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:666
void removeOutgoingEdge(Node &SourceN, Node &TargetN)
Remove an edge whose source is in this RefSCC and target is not.
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
Definition: PassManager.h:776
This class represents lattice values for constants.
Definition: AllocatorList.h:23
SmallPriorityWorklist< LazyCallGraph::RefSCC *, 1 > & RCWorklist
Worklist of the RefSCCs queued for processing.
void intersect(const PreservedAnalyses &Arg)
Intersect this set with another in place.
Definition: PassManager.h:225
A Module instance is used to store all the information related to an LLVM module. ...
Definition: Module.h:65
LazyCallGraph::SCC & updateCGAndAnalysisManagerForFunctionPass(LazyCallGraph &G, LazyCallGraph::SCC &C, LazyCallGraph::Node &N, CGSCCAnalysisManager &AM, CGSCCUpdateResult &UR)
Helper to update the call graph after running a function pass.
This provides a very simple, boring adaptor for a begin and end iterator into a range type...
SCC * lookupSCC(Node &N) const
Lookup a function&#39;s SCC in the graph.
bool invalidate(IRUnitT &IR, const PreservedAnalyses &PA, typename AnalysisManager< IRUnitT, ExtraArgTs... >::Invalidator &Inv)
Handler for invalidation of the outer IR unit, IRUnitT.
Implements a lazy call graph analysis and related passes for the new pass manager.
Function & getFunction() const
F(f)
A proxy from a FunctionAnalysisManager to an SCC.
Support structure for SCC passes to communicate updates the call graph back to the CGSCC pass manager...
RefSCC * lookupRefSCC(Node &N) const
Lookup a function&#39;s RefSCC in the graph.
PreservedAnalysisChecker getChecker() const
Build a checker for this PreservedAnalyses and the specified analysis type.
Definition: PassManager.h:311
RefSCC & getOuterRefSCC() const
LazyCallGraph::SCC * UpdatedC
If non-null, the updated current SCC being processed.
iterator begin() const
AnalysisManagerT & getManager()
Accessor for the analysis manager.
Definition: PassManager.h:1079
auto reverse(ContainerTy &&C, typename std::enable_if< has_rbegin< ContainerTy >::value >::type *=nullptr) -> decltype(make_range(C.rbegin(), C.rend()))
Definition: STLExtras.h:273
A RefSCC of the call graph.
bool insert(const value_type &X)
Insert a new element into the SetVector.
Definition: SetVector.h:141
AnalysisManager< LazyCallGraph::SCC, LazyCallGraph & > CGSCCAnalysisManager
The CGSCC analysis manager.
static void updateNewSCCFunctionAnalyses(LazyCallGraph::SCC &C, LazyCallGraph &G, CGSCCAnalysisManager &AM)
When a new SCC is created for the graph and there might be function analysis results cached for the f...
A lazily constructed view of the call graph of a module.
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory)...
Definition: APInt.h:32
bool runBeforePass(const PassT &Pass, const IRUnitT &IR) const
BeforePass instrumentation point - takes Pass instance to be executed and constant reference to IR it...
A set of analyses that are preserved following a run of a transformation pass.
Definition: PassManager.h:153
bool areAllPreserved() const
Test whether all analyses are preserved (and none are abandoned).
Definition: PassManager.h:328
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
SmallPtrSetImpl< LazyCallGraph::RefSCC * > & InvalidatedRefSCCs
The set of invalidated RefSCCs which should be skipped if they are found in RCWorklist.
SmallPtrSetImpl< LazyCallGraph::SCC * > & InvalidatedSCCs
The set of invalidated SCCs which should be skipped if they are found in CWorklist.
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:370
LazyCallGraph::RefSCC * UpdatedRC
If non-null, the updated current RefSCC being processed.
iterator end() const
A node in the call graph.
size_type count(ConstPtrType Ptr) const
count - Return 1 if the specified pointer is in the set, 0 otherwise.
Definition: SmallPtrSet.h:381
A class used to represent edges in the call graph.
auto remove_if(R &&Range, UnaryPredicate P) -> decltype(adl_begin(Range))
Provide wrappers to std::remove_if which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1232
iterator erase(const_iterator CI)
Definition: SmallVector.h:434
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
Definition: PassManager.h:159
SmallPriorityWorklist< LazyCallGraph::SCC *, 1 > & CWorklist
Worklist of the SCCs queued for processing.
Pseudo-analysis pass that exposes the PassInstrumentation to pass managers.
Definition: PassManager.h:581
AnalysisManager< Module > ModuleAnalysisManager
Convenience typedef for the Module analysis manager.
Definition: PassManager.h:1020
iterator_range< T > make_range(T x, T y)
Convenience function for iterating over sub-ranges.
A SetVector that performs no allocations if smaller than a certain size.
Definition: SetVector.h:297
print lazy value Lazy Value Info Printer Pass
SmallPtrSet - This class implements a set which is optimized for holding SmallSize or less elements...
Definition: SmallPtrSet.h:417
void runAfterPass(const PassT &Pass, const IRUnitT &IR) const
AfterPass instrumentation point - takes Pass instance that has just been executed and constant refere...
An analysis over an "inner" IR unit that provides access to an analysis manager over a "outer" IR uni...
Definition: PassManager.h:1160
This is a &#39;vector&#39; (really, a variable-sized array), optimized for the case when the array is small...
Definition: SmallVector.h:837
void runAfterPassInvalidated(const PassT &Pass) const
AfterPassInvalidated instrumentation point - takes Pass instance that has just been executed...
Result run(IRUnitT &IR, AnalysisManager< IRUnitT, ExtraArgTs... > &AM, ExtraArgTs...)
Run the analysis pass and create our proxy result object.
Definition: PassManager.h:1107
ArrayRef< Function * > getLibFunctions() const
Get the sequence of known and defined library functions.
const DataFlowGraph & G
Definition: RDFGraph.cpp:202
void invalidate(IRUnitT &IR)
Invalidate a specific analysis pass for an IR module.
Definition: PassManager.h:848
Node * lookup(const Function &F) const
Lookup a function in the graph which has already been scanned and added.
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:132
Result(AnalysisManagerT &InnerAM)
Definition: PassManager.h:1050
amdgpu Simplify well known AMD library false FunctionCallee Callee
void switchTrivialInternalEdgeToRef(Node &SourceN, Node &TargetN)
Make an existing internal call edge between separate SCCs into a ref edge.
Manages a sequence of passes over a particular unit of IR.
Definition: PassManager.h:464
#define I(x, y, z)
Definition: MD5.cpp:58
#define N
PreservedAnalyses CrossSCCPA
Preserved analyses across SCCs.
PassT::Result * getCachedResult(IRUnitT &IR) const
Get the cached result of an analysis pass for a given IR unit.
Definition: PassManager.h:795
void preserve()
Mark an analysis as preserved.
Definition: PassManager.h:174
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&#39;s CGSCCUpdateResu...
An analysis pass which computes the call graph for a module.
This header provides classes for managing passes over SCCs of the call graph.
API to communicate dependencies between analyses during invalidation.
Definition: PassManager.h:648
bool invalidate(LazyCallGraph::SCC &C, const PreservedAnalyses &PA, CGSCCAnalysisManager::Invalidator &Inv)
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This templated class represents "all analyses that operate over <a particular IR unit>" (e...
Definition: PassManager.h:91
LLVM Value Representation.
Definition: Value.h:72
An SCC of the call graph.
inst_range instructions(Function *F)
Definition: InstIterator.h:133
A container for analyses that lazily runs them and caches their results.
This class provides instrumentation entry points for the Pass Manager, doing calls to callbacks regis...
This header defines various interfaces for pass management in LLVM.
#define LLVM_DEBUG(X)
Definition: Debug.h:122
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...
A special type used by analysis passes to provide an address that identifies that particular analysis...
Definition: PassManager.h:70
bool allAnalysesInSetPreserved() const
Directly test whether a set of analyses is preserved.
Definition: PassManager.h:336
An analysis over an "outer" IR unit that provides access to an analysis manager over an "inner" IR un...
Definition: PassManager.h:1044