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