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