1//===- LazyCallGraph.cpp - Analysis of a Module's call graph --------------===//
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
9#include "llvm/Analysis/LazyCallGraph.h"
10
11#include "llvm/ADT/ArrayRef.h"
12#include "llvm/ADT/STLExtras.h"
13#include "llvm/ADT/Sequence.h"
14#include "llvm/ADT/SmallPtrSet.h"
15#include "llvm/ADT/SmallVector.h"
16#include "llvm/ADT/iterator_range.h"
17#include "llvm/Analysis/TargetLibraryInfo.h"
18#include "llvm/IR/Constants.h"
19#include "llvm/IR/Function.h"
20#include "llvm/IR/GlobalVariable.h"
21#include "llvm/IR/InstIterator.h"
22#include "llvm/IR/Instruction.h"
23#include "llvm/IR/Module.h"
24#include "llvm/IR/PassManager.h"
25#include "llvm/Support/Casting.h"
26#include "llvm/Support/Compiler.h"
27#include "llvm/Support/Debug.h"
28#include "llvm/Support/GraphWriter.h"
29#include "llvm/Support/raw_ostream.h"
30#include <algorithm>
31
32#ifdef EXPENSIVE_CHECKS
33#include "llvm/ADT/ScopeExit.h"
34#endif
35
36using namespace llvm;
37
38#define DEBUG_TYPE "lcg"
39
40void LazyCallGraph::EdgeSequence::insertEdgeInternal(Node &TargetN,
41 Edge::Kind EK) {
42 EdgeIndexMap.try_emplace(Key: &TargetN, Args: Edges.size());
43 Edges.emplace_back(Args&: TargetN, Args&: EK);
44}
45
46void LazyCallGraph::EdgeSequence::setEdgeKind(Node &TargetN, Edge::Kind EK) {
47 Edges[EdgeIndexMap.find(Val: &TargetN)->second].setKind(EK);
48}
49
50bool LazyCallGraph::EdgeSequence::removeEdgeInternal(Node &TargetN) {
51 auto IndexMapI = EdgeIndexMap.find(Val: &TargetN);
52 if (IndexMapI == EdgeIndexMap.end())
53 return false;
54
55 Edges[IndexMapI->second] = Edge();
56 EdgeIndexMap.erase(I: IndexMapI);
57 return true;
58}
59
60static void addEdge(SmallVectorImpl<LazyCallGraph::Edge> &Edges,
61 DenseMap<LazyCallGraph::Node *, int> &EdgeIndexMap,
62 LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK) {
63 if (!EdgeIndexMap.try_emplace(Key: &N, Args: Edges.size()).second)
64 return;
65
66 LLVM_DEBUG(dbgs() << " Added callable function: " << N.getName() << "\n");
67 Edges.emplace_back(Args: LazyCallGraph::Edge(N, EK));
68}
69
70LazyCallGraph::EdgeSequence &LazyCallGraph::Node::populateSlow() {
71 assert(!Edges && "Must not have already populated the edges for this node!");
72
73 LLVM_DEBUG(dbgs() << " Adding functions called by '" << getName()
74 << "' to the graph.\n");
75
76 Edges = EdgeSequence();
77
78 SmallVector<Constant *, 16> Worklist;
79 SmallPtrSet<Function *, 4> Callees;
80 SmallPtrSet<Constant *, 16> Visited;
81
82 // Find all the potential call graph edges in this function. We track both
83 // actual call edges and indirect references to functions. The direct calls
84 // are trivially added, but to accumulate the latter we walk the instructions
85 // and add every operand which is a constant to the worklist to process
86 // afterward.
87 //
88 // Note that we consider *any* function with a definition to be a viable
89 // edge. Even if the function's definition is subject to replacement by
90 // some other module (say, a weak definition) there may still be
91 // optimizations which essentially speculate based on the definition and
92 // a way to check that the specific definition is in fact the one being
93 // used. For example, this could be done by moving the weak definition to
94 // a strong (internal) definition and making the weak definition be an
95 // alias. Then a test of the address of the weak function against the new
96 // strong definition's address would be an effective way to determine the
97 // safety of optimizing a direct call edge.
98 for (BasicBlock &BB : *F)
99 for (Instruction &I : BB) {
100 if (auto *CB = dyn_cast<CallBase>(Val: &I))
101 if (Function *Callee = CB->getCalledFunction())
102 if (!Callee->isDeclaration())
103 if (Callees.insert(Ptr: Callee).second) {
104 Visited.insert(Ptr: Callee);
105 addEdge(Edges&: Edges->Edges, EdgeIndexMap&: Edges->EdgeIndexMap, N&: G->get(F&: *Callee),
106 EK: LazyCallGraph::Edge::Call);
107 }
108
109 for (Value *Op : I.operand_values())
110 if (Constant *C = dyn_cast<Constant>(Val: Op))
111 if (Visited.insert(Ptr: C).second)
112 Worklist.push_back(Elt: C);
113 }
114
115 // We've collected all the constant (and thus potentially function or
116 // function containing) operands to all the instructions in the function.
117 // Process them (recursively) collecting every function found.
118 visitReferences(Worklist, Visited, Callback: [&](Function &F) {
119 addEdge(Edges&: Edges->Edges, EdgeIndexMap&: Edges->EdgeIndexMap, N&: G->get(F),
120 EK: LazyCallGraph::Edge::Ref);
121 });
122
123 // Add implicit reference edges to any defined libcall functions (if we
124 // haven't found an explicit edge).
125 for (auto *F : G->LibFunctions)
126 if (!Visited.count(Ptr: F))
127 addEdge(Edges&: Edges->Edges, EdgeIndexMap&: Edges->EdgeIndexMap, N&: G->get(F&: *F),
128 EK: LazyCallGraph::Edge::Ref);
129
130 return *Edges;
131}
132
133void LazyCallGraph::Node::replaceFunction(Function &NewF) {
134 assert(F != &NewF && "Must not replace a function with itself!");
135 F = &NewF;
136}
137
138#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
139LLVM_DUMP_METHOD void LazyCallGraph::Node::dump() const {
140 dbgs() << *this << '\n';
141}
142#endif
143
144static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI) {
145 // Either this is a normal library function or a "vectorizable"
146 // function. Not using the VFDatabase here because this query
147 // is related only to libraries handled via the TLI.
148 return TLI.getLibFunc(FDecl: F) != NotLibFunc ||
149 TLI.isKnownVectorFunctionInLibrary(F: F.getName());
150}
151
152LazyCallGraph::LazyCallGraph(
153 Module &M, function_ref<TargetLibraryInfo &(Function &)> GetTLI) {
154 LLVM_DEBUG(dbgs() << "Building CG for module: " << M.getModuleIdentifier()
155 << "\n");
156 for (Function &F : M) {
157 if (F.isDeclaration())
158 continue;
159 // If this function is a known lib function to LLVM then we want to
160 // synthesize reference edges to it to model the fact that LLVM can turn
161 // arbitrary code into a library function call.
162 if (isKnownLibFunction(F, TLI&: GetTLI(F)))
163 LibFunctions.insert(X: &F);
164
165 if (F.hasLocalLinkage())
166 continue;
167
168 // External linkage defined functions have edges to them from other
169 // modules.
170 LLVM_DEBUG(dbgs() << " Adding '" << F.getName()
171 << "' to entry set of the graph.\n");
172 addEdge(Edges&: EntryEdges.Edges, EdgeIndexMap&: EntryEdges.EdgeIndexMap, N&: get(F), EK: Edge::Ref);
173 }
174
175 // Externally visible aliases of internal functions are also viable entry
176 // edges to the module.
177 for (auto &A : M.aliases()) {
178 if (A.hasLocalLinkage())
179 continue;
180 if (Function* F = dyn_cast<Function>(Val: A.getAliasee())) {
181 LLVM_DEBUG(dbgs() << " Adding '" << F->getName()
182 << "' with alias '" << A.getName()
183 << "' to entry set of the graph.\n");
184 addEdge(Edges&: EntryEdges.Edges, EdgeIndexMap&: EntryEdges.EdgeIndexMap, N&: get(F&: *F), EK: Edge::Ref);
185 }
186 }
187
188 // Now add entry nodes for functions reachable via initializers to globals.
189 SmallVector<Constant *, 16> Worklist;
190 SmallPtrSet<Constant *, 16> Visited;
191 for (GlobalVariable &GV : M.globals())
192 if (GV.hasInitializer())
193 if (Visited.insert(Ptr: GV.getInitializer()).second)
194 Worklist.push_back(Elt: GV.getInitializer());
195
196 LLVM_DEBUG(
197 dbgs() << " Adding functions referenced by global initializers to the "
198 "entry set.\n");
199 visitReferences(Worklist, Visited, Callback: [&](Function &F) {
200 addEdge(Edges&: EntryEdges.Edges, EdgeIndexMap&: EntryEdges.EdgeIndexMap, N&: get(F),
201 EK: LazyCallGraph::Edge::Ref);
202 });
203}
204
205LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)
206 : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)),
207 EntryEdges(std::move(G.EntryEdges)), SCCBPA(std::move(G.SCCBPA)),
208 SCCMap(std::move(G.SCCMap)), LibFunctions(std::move(G.LibFunctions)) {
209 updateGraphPtrs();
210}
211
212#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
213void LazyCallGraph::verify() {
214 for (RefSCC &RC : postorder_ref_sccs()) {
215 RC.verify();
216 }
217}
218#endif
219
220bool LazyCallGraph::invalidate(Module &, const PreservedAnalyses &PA,
221 ModuleAnalysisManager::Invalidator &) {
222 // Check whether the analysis, all analyses on functions, or the function's
223 // CFG have been preserved.
224 auto PAC = PA.getChecker<llvm::LazyCallGraphAnalysis>();
225 return !(PAC.preserved() || PAC.preservedSet<AllAnalysesOn<Module>>());
226}
227
228LazyCallGraph &LazyCallGraph::operator=(LazyCallGraph &&G) {
229 BPA = std::move(G.BPA);
230 NodeMap = std::move(G.NodeMap);
231 EntryEdges = std::move(G.EntryEdges);
232 SCCBPA = std::move(G.SCCBPA);
233 SCCMap = std::move(G.SCCMap);
234 LibFunctions = std::move(G.LibFunctions);
235 updateGraphPtrs();
236 return *this;
237}
238
239#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
240LLVM_DUMP_METHOD void LazyCallGraph::SCC::dump() const {
241 dbgs() << *this << '\n';
242}
243#endif
244
245#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
246void LazyCallGraph::SCC::verify() {
247 assert(OuterRefSCC && "Can't have a null RefSCC!");
248 assert(!Nodes.empty() && "Can't have an empty SCC!");
249
250 for (Node *N : Nodes) {
251 assert(N && "Can't have a null node!");
252 assert(OuterRefSCC->G->lookupSCC(*N) == this &&
253 "Node does not map to this SCC!");
254 assert(N->DFSNumber == -1 &&
255 "Must set DFS numbers to -1 when adding a node to an SCC!");
256 assert(N->LowLink == -1 &&
257 "Must set low link to -1 when adding a node to an SCC!");
258 for (Edge &E : **N)
259 assert(E.getNode().isPopulated() && "Can't have an unpopulated node!");
260
261#ifdef EXPENSIVE_CHECKS
262 // Verify that all nodes in this SCC can reach all other nodes.
263 SmallVector<Node *, 4> Worklist;
264 SmallPtrSet<Node *, 4> Visited;
265 Worklist.push_back(N);
266 while (!Worklist.empty()) {
267 Node *VisitingNode = Worklist.pop_back_val();
268 if (!Visited.insert(VisitingNode).second)
269 continue;
270 for (Edge &E : (*VisitingNode)->calls())
271 Worklist.push_back(&E.getNode());
272 }
273 for (Node *NodeToVisit : Nodes) {
274 assert(Visited.contains(NodeToVisit) &&
275 "Cannot reach all nodes within SCC");
276 }
277#endif
278 }
279}
280#endif
281
282bool LazyCallGraph::SCC::isParentOf(const SCC &C) const {
283 if (this == &C)
284 return false;
285
286 for (Node &N : *this)
287 for (Edge &E : N->calls())
288 if (OuterRefSCC->G->lookupSCC(N&: E.getNode()) == &C)
289 return true;
290
291 // No edges found.
292 return false;
293}
294
295bool LazyCallGraph::SCC::isAncestorOf(const SCC &TargetC) const {
296 if (this == &TargetC)
297 return false;
298
299 LazyCallGraph &G = *OuterRefSCC->G;
300
301 // Start with this SCC.
302 SmallPtrSet<const SCC *, 16> Visited = {this};
303 SmallVector<const SCC *, 16> Worklist = {this};
304
305 // Walk down the graph until we run out of edges or find a path to TargetC.
306 do {
307 const SCC &C = *Worklist.pop_back_val();
308 for (Node &N : C)
309 for (Edge &E : N->calls()) {
310 SCC *CalleeC = G.lookupSCC(N&: E.getNode());
311 if (!CalleeC)
312 continue;
313
314 // If the callee's SCC is the TargetC, we're done.
315 if (CalleeC == &TargetC)
316 return true;
317
318 // If this is the first time we've reached this SCC, put it on the
319 // worklist to recurse through.
320 if (Visited.insert(Ptr: CalleeC).second)
321 Worklist.push_back(Elt: CalleeC);
322 }
323 } while (!Worklist.empty());
324
325 // No paths found.
326 return false;
327}
328
329LazyCallGraph::RefSCC::RefSCC(LazyCallGraph &G) : G(&G) {}
330
331#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
332LLVM_DUMP_METHOD void LazyCallGraph::RefSCC::dump() const {
333 dbgs() << *this << '\n';
334}
335#endif
336
337#if !defined(NDEBUG) || defined(EXPENSIVE_CHECKS)
338void LazyCallGraph::RefSCC::verify() {
339 assert(G && "Can't have a null graph!");
340 assert(!SCCs.empty() && "Can't have an empty SCC!");
341
342 // Verify basic properties of the SCCs.
343 SmallPtrSet<SCC *, 4> SCCSet;
344 for (SCC *C : SCCs) {
345 assert(C && "Can't have a null SCC!");
346 C->verify();
347 assert(&C->getOuterRefSCC() == this &&
348 "SCC doesn't think it is inside this RefSCC!");
349 bool Inserted = SCCSet.insert(C).second;
350 assert(Inserted && "Found a duplicate SCC!");
351 auto IndexIt = SCCIndices.find(C);
352 assert(IndexIt != SCCIndices.end() &&
353 "Found an SCC that doesn't have an index!");
354 }
355
356 // Check that our indices map correctly.
357 for (auto [C, I] : SCCIndices) {
358 assert(C && "Can't have a null SCC in the indices!");
359 assert(SCCSet.count(C) && "Found an index for an SCC not in the RefSCC!");
360 assert(SCCs[I] == C && "Index doesn't point to SCC!");
361 }
362
363 // Check that the SCCs are in fact in post-order.
364 for (int I = 0, Size = SCCs.size(); I < Size; ++I) {
365 SCC &SourceSCC = *SCCs[I];
366 for (Node &N : SourceSCC)
367 for (Edge &E : *N) {
368 if (!E.isCall())
369 continue;
370 SCC &TargetSCC = *G->lookupSCC(E.getNode());
371 if (&TargetSCC.getOuterRefSCC() == this) {
372 assert(SCCIndices.find(&TargetSCC)->second <= I &&
373 "Edge between SCCs violates post-order relationship.");
374 continue;
375 }
376 }
377 }
378
379#ifdef EXPENSIVE_CHECKS
380 // Verify that all nodes in this RefSCC can reach all other nodes.
381 SmallVector<Node *> Nodes;
382 for (SCC *C : SCCs) {
383 for (Node &N : *C)
384 Nodes.push_back(&N);
385 }
386 for (Node *N : Nodes) {
387 SmallVector<Node *, 4> Worklist;
388 SmallPtrSet<Node *, 4> Visited;
389 Worklist.push_back(N);
390 while (!Worklist.empty()) {
391 Node *VisitingNode = Worklist.pop_back_val();
392 if (!Visited.insert(VisitingNode).second)
393 continue;
394 for (Edge &E : **VisitingNode)
395 Worklist.push_back(&E.getNode());
396 }
397 for (Node *NodeToVisit : Nodes) {
398 assert(Visited.contains(NodeToVisit) &&
399 "Cannot reach all nodes within RefSCC");
400 }
401 }
402#endif
403}
404#endif
405
406bool LazyCallGraph::RefSCC::isParentOf(const RefSCC &RC) const {
407 if (&RC == this)
408 return false;
409
410 // Search all edges to see if this is a parent.
411 for (SCC &C : *this)
412 for (Node &N : C)
413 for (Edge &E : *N)
414 if (G->lookupRefSCC(N&: E.getNode()) == &RC)
415 return true;
416
417 return false;
418}
419
420bool LazyCallGraph::RefSCC::isAncestorOf(const RefSCC &RC) const {
421 if (&RC == this)
422 return false;
423
424 // For each descendant of this RefSCC, see if one of its children is the
425 // argument. If not, add that descendant to the worklist and continue
426 // searching.
427 SmallVector<const RefSCC *, 4> Worklist;
428 SmallPtrSet<const RefSCC *, 4> Visited;
429 Worklist.push_back(Elt: this);
430 Visited.insert(Ptr: this);
431 do {
432 const RefSCC &DescendantRC = *Worklist.pop_back_val();
433 for (SCC &C : DescendantRC)
434 for (Node &N : C)
435 for (Edge &E : *N) {
436 auto *ChildRC = G->lookupRefSCC(N&: E.getNode());
437 if (ChildRC == &RC)
438 return true;
439 if (!ChildRC || !Visited.insert(Ptr: ChildRC).second)
440 continue;
441 Worklist.push_back(Elt: ChildRC);
442 }
443 } while (!Worklist.empty());
444
445 return false;
446}
447
448/// Generic helper that updates a postorder sequence of SCCs for a potentially
449/// cycle-introducing edge insertion.
450///
451/// A postorder sequence of SCCs of a directed graph has one fundamental
452/// property: all deges in the DAG of SCCs point "up" the sequence. That is,
453/// all edges in the SCC DAG point to prior SCCs in the sequence.
454///
455/// This routine both updates a postorder sequence and uses that sequence to
456/// compute the set of SCCs connected into a cycle. It should only be called to
457/// insert a "downward" edge which will require changing the sequence to
458/// restore it to a postorder.
459///
460/// When inserting an edge from an earlier SCC to a later SCC in some postorder
461/// sequence, all of the SCCs which may be impacted are in the closed range of
462/// those two within the postorder sequence. The algorithm used here to restore
463/// the state is as follows:
464///
465/// 1) Starting from the source SCC, construct a set of SCCs which reach the
466/// source SCC consisting of just the source SCC. Then scan toward the
467/// target SCC in postorder and for each SCC, if it has an edge to an SCC
468/// in the set, add it to the set. Otherwise, the source SCC is not
469/// a successor, move it in the postorder sequence to immediately before
470/// the source SCC, shifting the source SCC and all SCCs in the set one
471/// position toward the target SCC. Stop scanning after processing the
472/// target SCC.
473/// 2) If the source SCC is now past the target SCC in the postorder sequence,
474/// and thus the new edge will flow toward the start, we are done.
475/// 3) Otherwise, starting from the target SCC, walk all edges which reach an
476/// SCC between the source and the target, and add them to the set of
477/// connected SCCs, then recurse through them. Once a complete set of the
478/// SCCs the target connects to is known, hoist the remaining SCCs between
479/// the source and the target to be above the target. Note that there is no
480/// need to process the source SCC, it is already known to connect.
481/// 4) At this point, all of the SCCs in the closed range between the source
482/// SCC and the target SCC in the postorder sequence are connected,
483/// including the target SCC and the source SCC. Inserting the edge from
484/// the source SCC to the target SCC will form a cycle out of precisely
485/// these SCCs. Thus we can merge all of the SCCs in this closed range into
486/// a single SCC.
487///
488/// This process has various important properties:
489/// - Only mutates the SCCs when adding the edge actually changes the SCC
490/// structure.
491/// - Never mutates SCCs which are unaffected by the change.
492/// - Updates the postorder sequence to correctly satisfy the postorder
493/// constraint after the edge is inserted.
494/// - Only reorders SCCs in the closed postorder sequence from the source to
495/// the target, so easy to bound how much has changed even in the ordering.
496/// - Big-O is the number of edges in the closed postorder range of SCCs from
497/// source to target.
498///
499/// This helper routine, in addition to updating the postorder sequence itself
500/// will also update a map from SCCs to indices within that sequence.
501///
502/// The sequence and the map must operate on pointers to the SCC type.
503///
504/// Two callbacks must be provided. The first computes the subset of SCCs in
505/// the postorder closed range from the source to the target which connect to
506/// the source SCC via some (transitive) set of edges. The second computes the
507/// subset of the same range which the target SCC connects to via some
508/// (transitive) set of edges. Both callbacks should populate the set argument
509/// provided.
510template <typename SCCT, typename PostorderSequenceT, typename SCCIndexMapT,
511 typename ComputeSourceConnectedSetCallableT,
512 typename ComputeTargetConnectedSetCallableT>
513static iterator_range<typename PostorderSequenceT::iterator>
514updatePostorderSequenceForEdgeInsertion(
515 SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs,
516 SCCIndexMapT &SCCIndices,
517 ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet,
518 ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet) {
519 int SourceIdx = SCCIndices[&SourceSCC];
520 int TargetIdx = SCCIndices[&TargetSCC];
521 assert(SourceIdx < TargetIdx && "Cannot have equal indices here!");
522
523 SmallPtrSet<SCCT *, 4> ConnectedSet;
524
525 // Compute the SCCs which (transitively) reach the source.
526 ComputeSourceConnectedSet(ConnectedSet);
527
528 // Partition the SCCs in this part of the port-order sequence so only SCCs
529 // connecting to the source remain between it and the target. This is
530 // a benign partition as it preserves postorder.
531 auto SourceI = std::stable_partition(
532 SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1,
533 [&ConnectedSet](SCCT *C) { return !ConnectedSet.count(C); });
534 for (int I = SourceIdx, E = TargetIdx + 1; I < E; ++I)
535 SCCIndices.find(SCCs[I])->second = I;
536
537 // If the target doesn't connect to the source, then we've corrected the
538 // post-order and there are no cycles formed.
539 if (!ConnectedSet.count(&TargetSCC)) {
540 assert(SourceI > (SCCs.begin() + SourceIdx) &&
541 "Must have moved the source to fix the post-order.");
542 assert(*std::prev(SourceI) == &TargetSCC &&
543 "Last SCC to move should have bene the target.");
544
545 // Return an empty range at the target SCC indicating there is nothing to
546 // merge.
547 return make_range(std::prev(SourceI), std::prev(SourceI));
548 }
549
550 assert(SCCs[TargetIdx] == &TargetSCC &&
551 "Should not have moved target if connected!");
552 SourceIdx = SourceI - SCCs.begin();
553 assert(SCCs[SourceIdx] == &SourceSCC &&
554 "Bad updated index computation for the source SCC!");
555
556 // See whether there are any remaining intervening SCCs between the source
557 // and target. If so we need to make sure they all are reachable form the
558 // target.
559 if (SourceIdx + 1 < TargetIdx) {
560 ConnectedSet.clear();
561 ComputeTargetConnectedSet(ConnectedSet);
562
563 // Partition SCCs so that only SCCs reached from the target remain between
564 // the source and the target. This preserves postorder.
565 auto TargetI = std::stable_partition(
566 SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1,
567 [&ConnectedSet](SCCT *C) { return ConnectedSet.count(C); });
568 for (int I = SourceIdx + 1, E = TargetIdx + 1; I < E; ++I)
569 SCCIndices.find(SCCs[I])->second = I;
570 TargetIdx = std::prev(TargetI) - SCCs.begin();
571 assert(SCCs[TargetIdx] == &TargetSCC &&
572 "Should always end with the target!");
573 }
574
575 // At this point, we know that connecting source to target forms a cycle
576 // because target connects back to source, and we know that all the SCCs
577 // between the source and target in the postorder sequence participate in that
578 // cycle.
579 return make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx);
580}
581
582bool LazyCallGraph::RefSCC::switchInternalEdgeToCall(
583 Node &SourceN, Node &TargetN,
584 function_ref<void(ArrayRef<SCC *> MergeSCCs)> MergeCB) {
585 assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");
586 SmallVector<SCC *, 1> DeletedSCCs;
587
588#ifdef EXPENSIVE_CHECKS
589 verify();
590 llvm::scope_exit VerifyOnExit([&]() { verify(); });
591#endif
592
593 SCC &SourceSCC = *G->lookupSCC(N&: SourceN);
594 SCC &TargetSCC = *G->lookupSCC(N&: TargetN);
595
596 // If the two nodes are already part of the same SCC, we're also done as
597 // we've just added more connectivity.
598 if (&SourceSCC == &TargetSCC) {
599 SourceN->setEdgeKind(TargetN, EK: Edge::Call);
600 return false; // No new cycle.
601 }
602
603 // At this point we leverage the postorder list of SCCs to detect when the
604 // insertion of an edge changes the SCC structure in any way.
605 //
606 // First and foremost, we can eliminate the need for any changes when the
607 // edge is toward the beginning of the postorder sequence because all edges
608 // flow in that direction already. Thus adding a new one cannot form a cycle.
609 int SourceIdx = SCCIndices[&SourceSCC];
610 int TargetIdx = SCCIndices[&TargetSCC];
611 if (TargetIdx < SourceIdx) {
612 SourceN->setEdgeKind(TargetN, EK: Edge::Call);
613 return false; // No new cycle.
614 }
615
616 // Compute the SCCs which (transitively) reach the source.
617 auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {
618#ifdef EXPENSIVE_CHECKS
619 // Check that the RefSCC is still valid before computing this as the
620 // results will be nonsensical of we've broken its invariants.
621 verify();
622#endif
623 ConnectedSet.insert(Ptr: &SourceSCC);
624 auto IsConnected = [&](SCC &C) {
625 for (Node &N : C)
626 for (Edge &E : N->calls())
627 if (ConnectedSet.count(Ptr: G->lookupSCC(N&: E.getNode())))
628 return true;
629
630 return false;
631 };
632
633 for (SCC *C :
634 make_range(x: SCCs.begin() + SourceIdx + 1, y: SCCs.begin() + TargetIdx + 1))
635 if (IsConnected(*C))
636 ConnectedSet.insert(Ptr: C);
637 };
638
639 // Use a normal worklist to find which SCCs the target connects to. We still
640 // bound the search based on the range in the postorder list we care about,
641 // but because this is forward connectivity we just "recurse" through the
642 // edges.
643 auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {
644#ifdef EXPENSIVE_CHECKS
645 // Check that the RefSCC is still valid before computing this as the
646 // results will be nonsensical of we've broken its invariants.
647 verify();
648#endif
649 ConnectedSet.insert(Ptr: &TargetSCC);
650 SmallVector<SCC *, 4> Worklist;
651 Worklist.push_back(Elt: &TargetSCC);
652 do {
653 SCC &C = *Worklist.pop_back_val();
654 for (Node &N : C)
655 for (Edge &E : *N) {
656 if (!E.isCall())
657 continue;
658 SCC &EdgeC = *G->lookupSCC(N&: E.getNode());
659 if (&EdgeC.getOuterRefSCC() != this)
660 // Not in this RefSCC...
661 continue;
662 if (SCCIndices.find(Val: &EdgeC)->second <= SourceIdx)
663 // Not in the postorder sequence between source and target.
664 continue;
665
666 if (ConnectedSet.insert(Ptr: &EdgeC).second)
667 Worklist.push_back(Elt: &EdgeC);
668 }
669 } while (!Worklist.empty());
670 };
671
672 // Use a generic helper to update the postorder sequence of SCCs and return
673 // a range of any SCCs connected into a cycle by inserting this edge. This
674 // routine will also take care of updating the indices into the postorder
675 // sequence.
676 auto MergeRange = updatePostorderSequenceForEdgeInsertion(
677 SourceSCC, TargetSCC, SCCs, SCCIndices, ComputeSourceConnectedSet,
678 ComputeTargetConnectedSet);
679
680 // Run the user's callback on the merged SCCs before we actually merge them.
681 if (MergeCB)
682 MergeCB(ArrayRef(MergeRange.begin(), MergeRange.end()));
683
684 // If the merge range is empty, then adding the edge didn't actually form any
685 // new cycles. We're done.
686 if (MergeRange.empty()) {
687 // Now that the SCC structure is finalized, flip the kind to call.
688 SourceN->setEdgeKind(TargetN, EK: Edge::Call);
689 return false; // No new cycle.
690 }
691
692#ifdef EXPENSIVE_CHECKS
693 // Before merging, check that the RefSCC remains valid after all the
694 // postorder updates.
695 verify();
696#endif
697
698 // Otherwise we need to merge all the SCCs in the cycle into a single result
699 // SCC.
700 //
701 // NB: We merge into the target because all of these functions were already
702 // reachable from the target, meaning any SCC-wide properties deduced about it
703 // other than the set of functions within it will not have changed.
704 for (SCC *C : MergeRange) {
705 assert(C != &TargetSCC &&
706 "We merge *into* the target and shouldn't process it here!");
707 SCCIndices.erase(Val: C);
708 TargetSCC.Nodes.append(in_start: C->Nodes.begin(), in_end: C->Nodes.end());
709 for (Node *N : C->Nodes)
710 G->SCCMap[N] = &TargetSCC;
711 C->clear();
712 DeletedSCCs.push_back(Elt: C);
713 }
714
715 // Erase the merged SCCs from the list and update the indices of the
716 // remaining SCCs.
717 int IndexOffset = MergeRange.end() - MergeRange.begin();
718 auto EraseEnd = SCCs.erase(CS: MergeRange.begin(), CE: MergeRange.end());
719 for (SCC *C : make_range(x: EraseEnd, y: SCCs.end()))
720 SCCIndices[C] -= IndexOffset;
721
722 // Now that the SCC structure is finalized, flip the kind to call.
723 SourceN->setEdgeKind(TargetN, EK: Edge::Call);
724
725 // And we're done, but we did form a new cycle.
726 return true;
727}
728
729void LazyCallGraph::RefSCC::switchTrivialInternalEdgeToRef(Node &SourceN,
730 Node &TargetN) {
731 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
732
733#ifdef EXPENSIVE_CHECKS
734 verify();
735 llvm::scope_exit VerifyOnExit([&]() { verify(); });
736#endif
737
738 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
739 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
740 assert(G->lookupSCC(SourceN) != G->lookupSCC(TargetN) &&
741 "Source and Target must be in separate SCCs for this to be trivial!");
742
743 // Set the edge kind.
744 SourceN->setEdgeKind(TargetN, EK: Edge::Ref);
745}
746
747iterator_range<LazyCallGraph::RefSCC::iterator>
748LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, Node &TargetN) {
749 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
750
751#ifdef EXPENSIVE_CHECKS
752 verify();
753 llvm::scope_exit VerifyOnExit([&]() { verify(); });
754#endif
755
756 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
757 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
758
759 SCC &TargetSCC = *G->lookupSCC(N&: TargetN);
760 assert(G->lookupSCC(SourceN) == &TargetSCC && "Source and Target must be in "
761 "the same SCC to require the "
762 "full CG update.");
763
764 // Set the edge kind.
765 SourceN->setEdgeKind(TargetN, EK: Edge::Ref);
766
767 // Otherwise we are removing a call edge from a single SCC. This may break
768 // the cycle. In order to compute the new set of SCCs, we need to do a small
769 // DFS over the nodes within the SCC to form any sub-cycles that remain as
770 // distinct SCCs and compute a postorder over the resulting SCCs.
771 //
772 // However, we specially handle the target node. The target node is known to
773 // reach all other nodes in the original SCC by definition. This means that
774 // we want the old SCC to be replaced with an SCC containing that node as it
775 // will be the root of whatever SCC DAG results from the DFS. Assumptions
776 // about an SCC such as the set of functions called will continue to hold,
777 // etc.
778
779 SCC &OldSCC = TargetSCC;
780 SmallVector<std::pair<Node *, EdgeSequence::call_iterator>, 16> DFSStack;
781 SmallVector<Node *, 16> PendingSCCStack;
782 SmallVector<SCC *, 4> NewSCCs;
783
784 // Prepare the nodes for a fresh DFS.
785 SmallVector<Node *, 16> Worklist;
786 Worklist.swap(RHS&: OldSCC.Nodes);
787 for (Node *N : Worklist) {
788 N->DFSNumber = N->LowLink = 0;
789 G->SCCMap.erase(Val: N);
790 }
791
792 // Force the target node to be in the old SCC. This also enables us to take
793 // a very significant short-cut in the standard Tarjan walk to re-form SCCs
794 // below: whenever we build an edge that reaches the target node, we know
795 // that the target node eventually connects back to all other nodes in our
796 // walk. As a consequence, we can detect and handle participants in that
797 // cycle without walking all the edges that form this connection, and instead
798 // by relying on the fundamental guarantee coming into this operation (all
799 // nodes are reachable from the target due to previously forming an SCC).
800 TargetN.DFSNumber = TargetN.LowLink = -1;
801 OldSCC.Nodes.push_back(Elt: &TargetN);
802 G->SCCMap[&TargetN] = &OldSCC;
803
804 // Scan down the stack and DFS across the call edges.
805 for (Node *RootN : Worklist) {
806 assert(DFSStack.empty() &&
807 "Cannot begin a new root with a non-empty DFS stack!");
808 assert(PendingSCCStack.empty() &&
809 "Cannot begin a new root with pending nodes for an SCC!");
810
811 // Skip any nodes we've already reached in the DFS.
812 if (RootN->DFSNumber != 0) {
813 assert(RootN->DFSNumber == -1 &&
814 "Shouldn't have any mid-DFS root nodes!");
815 continue;
816 }
817
818 RootN->DFSNumber = RootN->LowLink = 1;
819 int NextDFSNumber = 2;
820
821 DFSStack.emplace_back(Args&: RootN, Args: (*RootN)->call_begin());
822 do {
823 auto [N, I] = DFSStack.pop_back_val();
824 auto E = (*N)->call_end();
825 while (I != E) {
826 Node &ChildN = I->getNode();
827 if (ChildN.DFSNumber == 0) {
828 // We haven't yet visited this child, so descend, pushing the current
829 // node onto the stack.
830 DFSStack.emplace_back(Args&: N, Args&: I);
831
832 assert(!G->SCCMap.count(&ChildN) &&
833 "Found a node with 0 DFS number but already in an SCC!");
834 ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
835 N = &ChildN;
836 I = (*N)->call_begin();
837 E = (*N)->call_end();
838 continue;
839 }
840
841 // Check for the child already being part of some component.
842 if (ChildN.DFSNumber == -1) {
843 if (G->lookupSCC(N&: ChildN) == &OldSCC) {
844 // If the child is part of the old SCC, we know that it can reach
845 // every other node, so we have formed a cycle. Pull the entire DFS
846 // and pending stacks into it. See the comment above about setting
847 // up the old SCC for why we do this.
848 int OldSize = OldSCC.size();
849 OldSCC.Nodes.push_back(Elt: N);
850 OldSCC.Nodes.append(in_start: PendingSCCStack.begin(), in_end: PendingSCCStack.end());
851 PendingSCCStack.clear();
852 while (!DFSStack.empty())
853 OldSCC.Nodes.push_back(Elt: DFSStack.pop_back_val().first);
854 for (Node &N : drop_begin(RangeOrContainer&: OldSCC, N: OldSize)) {
855 N.DFSNumber = N.LowLink = -1;
856 G->SCCMap[&N] = &OldSCC;
857 }
858 N = nullptr;
859 break;
860 }
861
862 // If the child has already been added to some child component, it
863 // couldn't impact the low-link of this parent because it isn't
864 // connected, and thus its low-link isn't relevant so skip it.
865 ++I;
866 continue;
867 }
868
869 // Track the lowest linked child as the lowest link for this node.
870 assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
871 if (ChildN.LowLink < N->LowLink)
872 N->LowLink = ChildN.LowLink;
873
874 // Move to the next edge.
875 ++I;
876 }
877 if (!N)
878 // Cleared the DFS early, start another round.
879 break;
880
881 // We've finished processing N and its descendants, put it on our pending
882 // SCC stack to eventually get merged into an SCC of nodes.
883 PendingSCCStack.push_back(Elt: N);
884
885 // If this node is linked to some lower entry, continue walking up the
886 // stack.
887 if (N->LowLink != N->DFSNumber)
888 continue;
889
890 // Otherwise, we've completed an SCC. Append it to our post order list of
891 // SCCs.
892 int RootDFSNumber = N->DFSNumber;
893 // Find the range of the node stack by walking down until we pass the
894 // root DFS number.
895 auto SCCNodes = make_range(
896 x: PendingSCCStack.rbegin(),
897 y: find_if(Range: reverse(C&: PendingSCCStack), P: [RootDFSNumber](const Node *N) {
898 return N->DFSNumber < RootDFSNumber;
899 }));
900
901 // Form a new SCC out of these nodes and then clear them off our pending
902 // stack.
903 NewSCCs.push_back(Elt: G->createSCC(Args&: *this, Args&: SCCNodes));
904 for (Node &N : *NewSCCs.back()) {
905 N.DFSNumber = N.LowLink = -1;
906 G->SCCMap[&N] = NewSCCs.back();
907 }
908 PendingSCCStack.erase(CS: SCCNodes.end().base(), CE: PendingSCCStack.end());
909 } while (!DFSStack.empty());
910 }
911
912 // Insert the remaining SCCs before the old one. The old SCC can reach all
913 // other SCCs we form because it contains the target node of the removed edge
914 // of the old SCC. This means that we will have edges into all the new SCCs,
915 // which means the old one must come last for postorder.
916 int OldIdx = SCCIndices[&OldSCC];
917 SCCs.insert(I: SCCs.begin() + OldIdx, From: NewSCCs.begin(), To: NewSCCs.end());
918
919 // Update the mapping from SCC* to index to use the new SCC*s, and remove the
920 // old SCC from the mapping.
921 for (int Idx = OldIdx, Size = SCCs.size(); Idx < Size; ++Idx)
922 SCCIndices[SCCs[Idx]] = Idx;
923
924 return make_range(x: SCCs.begin() + OldIdx,
925 y: SCCs.begin() + OldIdx + NewSCCs.size());
926}
927
928void LazyCallGraph::RefSCC::switchOutgoingEdgeToCall(Node &SourceN,
929 Node &TargetN) {
930 assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");
931
932 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
933 assert(G->lookupRefSCC(TargetN) != this &&
934 "Target must not be in this RefSCC.");
935#ifdef EXPENSIVE_CHECKS
936 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
937 "Target must be a descendant of the Source.");
938#endif
939
940 // Edges between RefSCCs are the same regardless of call or ref, so we can
941 // just flip the edge here.
942 SourceN->setEdgeKind(TargetN, EK: Edge::Call);
943
944#ifdef EXPENSIVE_CHECKS
945 verify();
946#endif
947}
948
949void LazyCallGraph::RefSCC::switchOutgoingEdgeToRef(Node &SourceN,
950 Node &TargetN) {
951 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
952
953 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
954 assert(G->lookupRefSCC(TargetN) != this &&
955 "Target must not be in this RefSCC.");
956#ifdef EXPENSIVE_CHECKS
957 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
958 "Target must be a descendant of the Source.");
959#endif
960
961 // Edges between RefSCCs are the same regardless of call or ref, so we can
962 // just flip the edge here.
963 SourceN->setEdgeKind(TargetN, EK: Edge::Ref);
964
965#ifdef EXPENSIVE_CHECKS
966 verify();
967#endif
968}
969
970void LazyCallGraph::RefSCC::insertInternalRefEdge(Node &SourceN,
971 Node &TargetN) {
972 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
973 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
974
975 SourceN->insertEdgeInternal(TargetN, EK: Edge::Ref);
976
977#ifdef EXPENSIVE_CHECKS
978 verify();
979#endif
980}
981
982void LazyCallGraph::RefSCC::insertOutgoingEdge(Node &SourceN, Node &TargetN,
983 Edge::Kind EK) {
984 // First insert it into the caller.
985 SourceN->insertEdgeInternal(TargetN, EK);
986
987 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
988
989 assert(G->lookupRefSCC(TargetN) != this &&
990 "Target must not be in this RefSCC.");
991#ifdef EXPENSIVE_CHECKS
992 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
993 "Target must be a descendant of the Source.");
994#endif
995
996#ifdef EXPENSIVE_CHECKS
997 verify();
998#endif
999}
1000
1001SmallVector<LazyCallGraph::RefSCC *, 1>
1002LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) {
1003 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
1004 RefSCC &SourceC = *G->lookupRefSCC(N&: SourceN);
1005 assert(&SourceC != this && "Source must not be in this RefSCC.");
1006#ifdef EXPENSIVE_CHECKS
1007 assert(SourceC.isDescendantOf(*this) &&
1008 "Source must be a descendant of the Target.");
1009#endif
1010
1011 SmallVector<RefSCC *, 1> DeletedRefSCCs;
1012
1013#ifdef EXPENSIVE_CHECKS
1014 verify();
1015 llvm::scope_exit VerifyOnExit([&]() { verify(); });
1016#endif
1017
1018 int SourceIdx = G->RefSCCIndices[&SourceC];
1019 int TargetIdx = G->RefSCCIndices[this];
1020 assert(SourceIdx < TargetIdx &&
1021 "Postorder list doesn't see edge as incoming!");
1022
1023 // Compute the RefSCCs which (transitively) reach the source. We do this by
1024 // working backwards from the source using the parent set in each RefSCC,
1025 // skipping any RefSCCs that don't fall in the postorder range. This has the
1026 // advantage of walking the sparser parent edge (in high fan-out graphs) but
1027 // more importantly this removes examining all forward edges in all RefSCCs
1028 // within the postorder range which aren't in fact connected. Only connected
1029 // RefSCCs (and their edges) are visited here.
1030 auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
1031 Set.insert(Ptr: &SourceC);
1032 auto IsConnected = [&](RefSCC &RC) {
1033 for (SCC &C : RC)
1034 for (Node &N : C)
1035 for (Edge &E : *N)
1036 if (Set.count(Ptr: G->lookupRefSCC(N&: E.getNode())))
1037 return true;
1038
1039 return false;
1040 };
1041
1042 for (RefSCC *C : make_range(x: G->PostOrderRefSCCs.begin() + SourceIdx + 1,
1043 y: G->PostOrderRefSCCs.begin() + TargetIdx + 1))
1044 if (IsConnected(*C))
1045 Set.insert(Ptr: C);
1046 };
1047
1048 // Use a normal worklist to find which SCCs the target connects to. We still
1049 // bound the search based on the range in the postorder list we care about,
1050 // but because this is forward connectivity we just "recurse" through the
1051 // edges.
1052 auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
1053 Set.insert(Ptr: this);
1054 SmallVector<RefSCC *, 4> Worklist;
1055 Worklist.push_back(Elt: this);
1056 do {
1057 RefSCC &RC = *Worklist.pop_back_val();
1058 for (SCC &C : RC)
1059 for (Node &N : C)
1060 for (Edge &E : *N) {
1061 RefSCC &EdgeRC = *G->lookupRefSCC(N&: E.getNode());
1062 if (G->getRefSCCIndex(RC&: EdgeRC) <= SourceIdx)
1063 // Not in the postorder sequence between source and target.
1064 continue;
1065
1066 if (Set.insert(Ptr: &EdgeRC).second)
1067 Worklist.push_back(Elt: &EdgeRC);
1068 }
1069 } while (!Worklist.empty());
1070 };
1071
1072 // Use a generic helper to update the postorder sequence of RefSCCs and return
1073 // a range of any RefSCCs connected into a cycle by inserting this edge. This
1074 // routine will also take care of updating the indices into the postorder
1075 // sequence.
1076 iterator_range<SmallVectorImpl<RefSCC *>::iterator> MergeRange =
1077 updatePostorderSequenceForEdgeInsertion(
1078 SourceSCC&: SourceC, TargetSCC&: *this, SCCs&: G->PostOrderRefSCCs, SCCIndices&: G->RefSCCIndices,
1079 ComputeSourceConnectedSet, ComputeTargetConnectedSet);
1080
1081 // Build a set, so we can do fast tests for whether a RefSCC will end up as
1082 // part of the merged RefSCC.
1083 SmallPtrSet<RefSCC *, 16> MergeSet(llvm::from_range, MergeRange);
1084
1085 // This RefSCC will always be part of that set, so just insert it here.
1086 MergeSet.insert(Ptr: this);
1087
1088 // Now that we have identified all the SCCs which need to be merged into
1089 // a connected set with the inserted edge, merge all of them into this SCC.
1090 SmallVector<SCC *, 16> MergedSCCs;
1091 int SCCIndex = 0;
1092 for (RefSCC *RC : MergeRange) {
1093 assert(RC != this && "We're merging into the target RefSCC, so it "
1094 "shouldn't be in the range.");
1095
1096 // Walk the inner SCCs to update their up-pointer and walk all the edges to
1097 // update any parent sets.
1098 // FIXME: We should try to find a way to avoid this (rather expensive) edge
1099 // walk by updating the parent sets in some other manner.
1100 for (SCC &InnerC : *RC) {
1101 InnerC.OuterRefSCC = this;
1102 SCCIndices[&InnerC] = SCCIndex++;
1103 for (Node &N : InnerC)
1104 G->SCCMap[&N] = &InnerC;
1105 }
1106
1107 // Now merge in the SCCs. We can actually move here so try to reuse storage
1108 // the first time through.
1109 if (MergedSCCs.empty())
1110 MergedSCCs = std::move(RC->SCCs);
1111 else
1112 MergedSCCs.append(in_start: RC->SCCs.begin(), in_end: RC->SCCs.end());
1113 RC->SCCs.clear();
1114 DeletedRefSCCs.push_back(Elt: RC);
1115 }
1116
1117 // Append our original SCCs to the merged list and move it into place.
1118 for (SCC &InnerC : *this)
1119 SCCIndices[&InnerC] = SCCIndex++;
1120 MergedSCCs.append(in_start: SCCs.begin(), in_end: SCCs.end());
1121 SCCs = std::move(MergedSCCs);
1122
1123 // Remove the merged away RefSCCs from the post order sequence.
1124 for (RefSCC *RC : MergeRange)
1125 G->RefSCCIndices.erase(Val: RC);
1126 int IndexOffset = MergeRange.end() - MergeRange.begin();
1127 auto EraseEnd =
1128 G->PostOrderRefSCCs.erase(CS: MergeRange.begin(), CE: MergeRange.end());
1129 for (RefSCC *RC : make_range(x: EraseEnd, y: G->PostOrderRefSCCs.end()))
1130 G->RefSCCIndices[RC] -= IndexOffset;
1131
1132 // At this point we have a merged RefSCC with a post-order SCCs list, just
1133 // connect the nodes to form the new edge.
1134 SourceN->insertEdgeInternal(TargetN, EK: Edge::Ref);
1135
1136 // We return the list of SCCs which were merged so that callers can
1137 // invalidate any data they have associated with those SCCs. Note that these
1138 // SCCs are no longer in an interesting state (they are totally empty) but
1139 // the pointers will remain stable for the life of the graph itself.
1140 return DeletedRefSCCs;
1141}
1142
1143void LazyCallGraph::RefSCC::removeOutgoingEdge(Node &SourceN, Node &TargetN) {
1144 assert(G->lookupRefSCC(SourceN) == this &&
1145 "The source must be a member of this RefSCC.");
1146 assert(G->lookupRefSCC(TargetN) != this &&
1147 "The target must not be a member of this RefSCC");
1148
1149#ifdef EXPENSIVE_CHECKS
1150 verify();
1151 llvm::scope_exit VerifyOnExit([&]() { verify(); });
1152#endif
1153
1154 // First remove it from the node.
1155 bool Removed = SourceN->removeEdgeInternal(TargetN);
1156 (void)Removed;
1157 assert(Removed && "Target not in the edge set for this caller?");
1158}
1159
1160SmallVector<LazyCallGraph::RefSCC *, 1>
1161LazyCallGraph::RefSCC::removeInternalRefEdges(
1162 ArrayRef<std::pair<Node *, Node *>> Edges) {
1163 // We return a list of the resulting *new* RefSCCs in post-order.
1164 SmallVector<RefSCC *, 1> Result;
1165
1166#ifdef EXPENSIVE_CHECKS
1167 // Verify the RefSCC is valid to start with and that either we return an empty
1168 // list of result RefSCCs and this RefSCC remains valid, or we return new
1169 // RefSCCs and this RefSCC is dead.
1170 verify();
1171 llvm::scope_exit VerifyOnExit([&]() {
1172 // If we didn't replace our RefSCC with new ones, check that this one
1173 // remains valid.
1174 if (G)
1175 verify();
1176 });
1177#endif
1178
1179 // First remove the actual edges.
1180 for (auto [SourceN, TargetN] : Edges) {
1181 assert(!(**SourceN)[*TargetN].isCall() &&
1182 "Cannot remove a call edge, it must first be made a ref edge");
1183
1184 bool Removed = (*SourceN)->removeEdgeInternal(TargetN&: *TargetN);
1185 (void)Removed;
1186 assert(Removed && "Target not in the edge set for this caller?");
1187 }
1188
1189 // Direct self references don't impact the ref graph at all.
1190 // If all targets are in the same SCC as the source, because no call edges
1191 // were removed there is no RefSCC structure change.
1192 if (llvm::all_of(Range&: Edges, P: [&](std::pair<Node *, Node *> E) {
1193 return E.first == E.second ||
1194 G->lookupSCC(N&: *E.first) == G->lookupSCC(N&: *E.second);
1195 }))
1196 return Result;
1197
1198 // We build somewhat synthetic new RefSCCs by providing a postorder mapping
1199 // for each inner SCC. We store these inside the low-link field of the nodes
1200 // rather than associated with SCCs because this saves a round-trip through
1201 // the node->SCC map and in the common case, SCCs are small. We will verify
1202 // that we always give the same number to every node in the SCC such that
1203 // these are equivalent.
1204 int PostOrderNumber = 0;
1205
1206 // Reset all the other nodes to prepare for a DFS over them, and add them to
1207 // our worklist.
1208 SmallVector<Node *, 8> Worklist;
1209 for (SCC *C : SCCs) {
1210 for (Node &N : *C)
1211 N.DFSNumber = N.LowLink = 0;
1212
1213 Worklist.append(in_start: C->Nodes.begin(), in_end: C->Nodes.end());
1214 }
1215
1216 // Track the number of nodes in this RefSCC so that we can quickly recognize
1217 // an important special case of the edge removal not breaking the cycle of
1218 // this RefSCC.
1219 const int NumRefSCCNodes = Worklist.size();
1220
1221 SmallVector<std::pair<Node *, EdgeSequence::iterator>, 4> DFSStack;
1222 SmallVector<Node *, 4> PendingRefSCCStack;
1223 do {
1224 assert(DFSStack.empty() &&
1225 "Cannot begin a new root with a non-empty DFS stack!");
1226 assert(PendingRefSCCStack.empty() &&
1227 "Cannot begin a new root with pending nodes for an SCC!");
1228
1229 Node *RootN = Worklist.pop_back_val();
1230 // Skip any nodes we've already reached in the DFS.
1231 if (RootN->DFSNumber != 0) {
1232 assert(RootN->DFSNumber == -1 &&
1233 "Shouldn't have any mid-DFS root nodes!");
1234 continue;
1235 }
1236
1237 RootN->DFSNumber = RootN->LowLink = 1;
1238 int NextDFSNumber = 2;
1239
1240 DFSStack.emplace_back(Args&: RootN, Args: (*RootN)->begin());
1241 do {
1242 auto [N, I] = DFSStack.pop_back_val();
1243 auto E = (*N)->end();
1244
1245 assert(N->DFSNumber != 0 && "We should always assign a DFS number "
1246 "before processing a node.");
1247
1248 while (I != E) {
1249 Node &ChildN = I->getNode();
1250 if (ChildN.DFSNumber == 0) {
1251 // Mark that we should start at this child when next this node is the
1252 // top of the stack. We don't start at the next child to ensure this
1253 // child's lowlink is reflected.
1254 DFSStack.emplace_back(Args&: N, Args&: I);
1255
1256 // Continue, resetting to the child node.
1257 ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
1258 N = &ChildN;
1259 I = ChildN->begin();
1260 E = ChildN->end();
1261 continue;
1262 }
1263 if (ChildN.DFSNumber == -1) {
1264 // If this child isn't currently in this RefSCC, no need to process
1265 // it.
1266 ++I;
1267 continue;
1268 }
1269
1270 // Track the lowest link of the children, if any are still in the stack.
1271 // Any child not on the stack will have a LowLink of -1.
1272 assert(ChildN.LowLink != 0 &&
1273 "Low-link must not be zero with a non-zero DFS number.");
1274 if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink)
1275 N->LowLink = ChildN.LowLink;
1276 ++I;
1277 }
1278
1279 // We've finished processing N and its descendants, put it on our pending
1280 // stack to eventually get merged into a RefSCC.
1281 PendingRefSCCStack.push_back(Elt: N);
1282
1283 // If this node is linked to some lower entry, continue walking up the
1284 // stack.
1285 if (N->LowLink != N->DFSNumber) {
1286 assert(!DFSStack.empty() &&
1287 "We never found a viable root for a RefSCC to pop off!");
1288 continue;
1289 }
1290
1291 // Otherwise, form a new RefSCC from the top of the pending node stack.
1292 int RefSCCNumber = PostOrderNumber++;
1293 int RootDFSNumber = N->DFSNumber;
1294
1295 // Find the range of the node stack by walking down until we pass the
1296 // root DFS number. Update the DFS numbers and low link numbers in the
1297 // process to avoid re-walking this list where possible.
1298 auto StackRI = find_if(Range: reverse(C&: PendingRefSCCStack), P: [&](Node *N) {
1299 if (N->DFSNumber < RootDFSNumber)
1300 // We've found the bottom.
1301 return true;
1302
1303 // Update this node and keep scanning.
1304 N->DFSNumber = -1;
1305 // Save the post-order number in the lowlink field so that we can use
1306 // it to map SCCs into new RefSCCs after we finish the DFS.
1307 N->LowLink = RefSCCNumber;
1308 return false;
1309 });
1310 auto RefSCCNodes = make_range(x: StackRI.base(), y: PendingRefSCCStack.end());
1311
1312 // If we find a cycle containing all nodes originally in this RefSCC then
1313 // the removal hasn't changed the structure at all. This is an important
1314 // special case, and we can directly exit the entire routine more
1315 // efficiently as soon as we discover it.
1316 if (llvm::size(Range&: RefSCCNodes) == NumRefSCCNodes) {
1317 // Clear out the low link field as we won't need it.
1318 for (Node *N : RefSCCNodes)
1319 N->LowLink = -1;
1320 // Return the empty result immediately.
1321 return Result;
1322 }
1323
1324 // We've already marked the nodes internally with the RefSCC number so
1325 // just clear them off the stack and continue.
1326 PendingRefSCCStack.erase(CS: RefSCCNodes.begin(), CE: PendingRefSCCStack.end());
1327 } while (!DFSStack.empty());
1328
1329 assert(DFSStack.empty() && "Didn't flush the entire DFS stack!");
1330 assert(PendingRefSCCStack.empty() && "Didn't flush all pending nodes!");
1331 } while (!Worklist.empty());
1332
1333 assert(PostOrderNumber > 1 &&
1334 "Should never finish the DFS when the existing RefSCC remains valid!");
1335
1336 // Otherwise we create a collection of new RefSCC nodes and build
1337 // a radix-sort style map from postorder number to these new RefSCCs. We then
1338 // append SCCs to each of these RefSCCs in the order they occurred in the
1339 // original SCCs container.
1340 for (int I = 0; I < PostOrderNumber; ++I)
1341 Result.push_back(Elt: G->createRefSCC(Args&: *G));
1342
1343 // Insert the resulting postorder sequence into the global graph postorder
1344 // sequence before the current RefSCC in that sequence, and then remove the
1345 // current one.
1346 //
1347 // FIXME: It'd be nice to change the APIs so that we returned an iterator
1348 // range over the global postorder sequence and generally use that sequence
1349 // rather than building a separate result vector here.
1350 int Idx = G->getRefSCCIndex(RC&: *this);
1351 G->PostOrderRefSCCs.erase(CI: G->PostOrderRefSCCs.begin() + Idx);
1352 G->PostOrderRefSCCs.insert(I: G->PostOrderRefSCCs.begin() + Idx, From: Result.begin(),
1353 To: Result.end());
1354 for (int I : seq<int>(Begin: Idx, End: G->PostOrderRefSCCs.size()))
1355 G->RefSCCIndices[G->PostOrderRefSCCs[I]] = I;
1356
1357 for (SCC *C : SCCs) {
1358 // We store the SCC number in the node's low-link field above.
1359 int SCCNumber = C->begin()->LowLink;
1360 // Clear out all the SCC's node's low-link fields now that we're done
1361 // using them as side-storage.
1362 for (Node &N : *C) {
1363 assert(N.LowLink == SCCNumber &&
1364 "Cannot have different numbers for nodes in the same SCC!");
1365 N.LowLink = -1;
1366 }
1367
1368 RefSCC &RC = *Result[SCCNumber];
1369 int SCCIndex = RC.SCCs.size();
1370 RC.SCCs.push_back(Elt: C);
1371 RC.SCCIndices[C] = SCCIndex;
1372 C->OuterRefSCC = &RC;
1373 }
1374
1375 // Now that we've moved things into the new RefSCCs, clear out our current
1376 // one.
1377 G = nullptr;
1378 SCCs.clear();
1379 SCCIndices.clear();
1380
1381#ifdef EXPENSIVE_CHECKS
1382 // Verify the new RefSCCs we've built.
1383 for (RefSCC *RC : Result)
1384 RC->verify();
1385#endif
1386
1387 // Return the new list of SCCs.
1388 return Result;
1389}
1390
1391void LazyCallGraph::RefSCC::insertTrivialCallEdge(Node &SourceN,
1392 Node &TargetN) {
1393#ifdef EXPENSIVE_CHECKS
1394 llvm::scope_exit ExitVerifier([this] { verify(); });
1395
1396 // Check that we aren't breaking some invariants of the SCC graph. Note that
1397 // this is quadratic in the number of edges in the call graph!
1398 SCC &SourceC = *G->lookupSCC(SourceN);
1399 SCC &TargetC = *G->lookupSCC(TargetN);
1400 if (&SourceC != &TargetC)
1401 assert(SourceC.isAncestorOf(TargetC) &&
1402 "Call edge is not trivial in the SCC graph!");
1403#endif
1404
1405 // First insert it into the source or find the existing edge.
1406 auto [Iterator, Inserted] =
1407 SourceN->EdgeIndexMap.try_emplace(Key: &TargetN, Args: SourceN->Edges.size());
1408 if (!Inserted) {
1409 // Already an edge, just update it.
1410 Edge &E = SourceN->Edges[Iterator->second];
1411 if (E.isCall())
1412 return; // Nothing to do!
1413 E.setKind(Edge::Call);
1414 } else {
1415 // Create the new edge.
1416 SourceN->Edges.emplace_back(Args&: TargetN, Args: Edge::Call);
1417 }
1418}
1419
1420void LazyCallGraph::RefSCC::insertTrivialRefEdge(Node &SourceN, Node &TargetN) {
1421#ifdef EXPENSIVE_CHECKS
1422 llvm::scope_exit ExitVerifier([this] { verify(); });
1423
1424 // Check that we aren't breaking some invariants of the RefSCC graph.
1425 RefSCC &SourceRC = *G->lookupRefSCC(SourceN);
1426 RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
1427 if (&SourceRC != &TargetRC)
1428 assert(SourceRC.isAncestorOf(TargetRC) &&
1429 "Ref edge is not trivial in the RefSCC graph!");
1430#endif
1431
1432 // First insert it into the source or find the existing edge.
1433 auto [Iterator, Inserted] =
1434 SourceN->EdgeIndexMap.try_emplace(Key: &TargetN, Args: SourceN->Edges.size());
1435 (void)Iterator;
1436 if (!Inserted)
1437 // Already an edge, we're done.
1438 return;
1439
1440 // Create the new edge.
1441 SourceN->Edges.emplace_back(Args&: TargetN, Args: Edge::Ref);
1442}
1443
1444void LazyCallGraph::RefSCC::replaceNodeFunction(Node &N, Function &NewF) {
1445 Function &OldF = N.getFunction();
1446
1447#ifdef EXPENSIVE_CHECKS
1448 llvm::scope_exit ExitVerifier([this] { verify(); });
1449
1450 assert(G->lookupRefSCC(N) == this &&
1451 "Cannot replace the function of a node outside this RefSCC.");
1452
1453 assert(G->NodeMap.find(&NewF) == G->NodeMap.end() &&
1454 "Must not have already walked the new function!'");
1455
1456 // It is important that this replacement not introduce graph changes so we
1457 // insist that the caller has already removed every use of the original
1458 // function and that all uses of the new function correspond to existing
1459 // edges in the graph. The common and expected way to use this is when
1460 // replacing the function itself in the IR without changing the call graph
1461 // shape and just updating the analysis based on that.
1462 assert(&OldF != &NewF && "Cannot replace a function with itself!");
1463 assert(OldF.use_empty() &&
1464 "Must have moved all uses from the old function to the new!");
1465#endif
1466
1467 N.replaceFunction(NewF);
1468
1469 // Update various call graph maps.
1470 G->NodeMap.erase(Val: &OldF);
1471 G->NodeMap[&NewF] = &N;
1472
1473 // Update lib functions.
1474 if (G->isLibFunction(F&: OldF)) {
1475 G->LibFunctions.remove(X: &OldF);
1476 G->LibFunctions.insert(X: &NewF);
1477 }
1478}
1479
1480void LazyCallGraph::insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK) {
1481 assert(SCCMap.empty() &&
1482 "This method cannot be called after SCCs have been formed!");
1483
1484 return SourceN->insertEdgeInternal(TargetN, EK);
1485}
1486
1487void LazyCallGraph::removeEdge(Node &SourceN, Node &TargetN) {
1488 assert(SCCMap.empty() &&
1489 "This method cannot be called after SCCs have been formed!");
1490
1491 bool Removed = SourceN->removeEdgeInternal(TargetN);
1492 (void)Removed;
1493 assert(Removed && "Target not in the edge set for this caller?");
1494}
1495
1496void LazyCallGraph::markDeadFunction(Function &F) {
1497 // FIXME: This is unnecessarily restrictive. We should be able to remove
1498 // functions which recursively call themselves.
1499 assert(F.hasZeroLiveUses() &&
1500 "This routine should only be called on trivially dead functions!");
1501
1502 // We shouldn't remove library functions as they are never really dead while
1503 // the call graph is in use -- every function definition refers to them.
1504 assert(!isLibFunction(F) &&
1505 "Must not remove lib functions from the call graph!");
1506
1507 auto NI = NodeMap.find(Val: &F);
1508 assert(NI != NodeMap.end() && "Removed function should be known!");
1509
1510 Node &N = *NI->second;
1511
1512 // Remove all call edges out of dead function.
1513 for (Edge E : *N) {
1514 if (E.isCall())
1515 N->setEdgeKind(TargetN&: E.getNode(), EK: Edge::Ref);
1516 }
1517}
1518
1519void LazyCallGraph::removeDeadFunctions(ArrayRef<Function *> DeadFs) {
1520 if (DeadFs.empty())
1521 return;
1522
1523 // Group dead functions by the RefSCC they're in.
1524 DenseMap<RefSCC *, SmallVector<Node *, 1>> RCs;
1525 for (Function *DeadF : DeadFs) {
1526 Node *N = lookup(F: *DeadF);
1527#ifndef NDEBUG
1528 for (Edge &E : **N) {
1529 assert(!E.isCall() &&
1530 "dead function shouldn't have any outgoing call edges");
1531 }
1532#endif
1533 RefSCC *RC = lookupRefSCC(N&: *N);
1534 RCs[RC].push_back(Elt: N);
1535 }
1536 // Remove outgoing edges from all dead functions. Dead functions should
1537 // already have had their call edges removed in markDeadFunction(), so we only
1538 // need to worry about spurious ref edges.
1539 for (auto [RC, DeadNs] : RCs) {
1540 SmallVector<std::pair<Node *, Node *>> InternalEdgesToRemove;
1541 for (Node *DeadN : DeadNs) {
1542 for (Edge &E : **DeadN) {
1543 if (lookupRefSCC(N&: E.getNode()) == RC)
1544 InternalEdgesToRemove.push_back(Elt: {DeadN, &E.getNode()});
1545 else
1546 RC->removeOutgoingEdge(SourceN&: *DeadN, TargetN&: E.getNode());
1547 }
1548 }
1549 // We ignore the returned RefSCCs since at this point we're done with CGSCC
1550 // iteration and don't need to add it to any worklists.
1551 (void)RC->removeInternalRefEdges(Edges: InternalEdgesToRemove);
1552 for (Node *DeadN : DeadNs) {
1553 RefSCC *DeadRC = lookupRefSCC(N&: *DeadN);
1554 assert(DeadRC->size() == 1);
1555 assert(DeadRC->begin()->size() == 1);
1556 DeadRC->clear();
1557 DeadRC->G = nullptr;
1558 }
1559 }
1560 // Clean up data structures.
1561 for (Function *DeadF : DeadFs) {
1562 Node &N = *lookup(F: *DeadF);
1563
1564 EntryEdges.removeEdgeInternal(TargetN&: N);
1565 SCCMap.erase(I: SCCMap.find(Val: &N));
1566 NodeMap.erase(I: NodeMap.find(Val: DeadF));
1567
1568 N.clear();
1569 N.G = nullptr;
1570 N.F = nullptr;
1571 }
1572}
1573
1574// Gets the Edge::Kind from one function to another by looking at the function's
1575// instructions. Asserts if there is no edge.
1576// Useful for determining what type of edge should exist between functions when
1577// the edge hasn't been created yet.
1578static LazyCallGraph::Edge::Kind getEdgeKind(Function &OriginalFunction,
1579 Function &NewFunction) {
1580 // In release builds, assume that if there are no direct calls to the new
1581 // function, then there is a ref edge. In debug builds, keep track of
1582 // references to assert that there is actually a ref edge if there is no call
1583 // edge.
1584#ifndef NDEBUG
1585 SmallVector<Constant *, 16> Worklist;
1586 SmallPtrSet<Constant *, 16> Visited;
1587#endif
1588
1589 for (Instruction &I : instructions(F&: OriginalFunction)) {
1590 if (auto *CB = dyn_cast<CallBase>(Val: &I)) {
1591 if (Function *Callee = CB->getCalledFunction()) {
1592 if (Callee == &NewFunction)
1593 return LazyCallGraph::Edge::Kind::Call;
1594 }
1595 }
1596#ifndef NDEBUG
1597 for (Value *Op : I.operand_values()) {
1598 if (Constant *C = dyn_cast<Constant>(Op)) {
1599 if (Visited.insert(C).second)
1600 Worklist.push_back(C);
1601 }
1602 }
1603#endif
1604 }
1605
1606#ifndef NDEBUG
1607 bool FoundNewFunction = false;
1608 LazyCallGraph::visitReferences(Worklist, Visited, [&](Function &F) {
1609 if (&F == &NewFunction)
1610 FoundNewFunction = true;
1611 });
1612 assert(FoundNewFunction && "No edge from original function to new function");
1613#endif
1614
1615 return LazyCallGraph::Edge::Kind::Ref;
1616}
1617
1618void LazyCallGraph::addSplitFunction(Function &OriginalFunction,
1619 Function &NewFunction) {
1620 assert(lookup(OriginalFunction) &&
1621 "Original function's node should already exist");
1622 Node &OriginalN = get(F&: OriginalFunction);
1623 SCC *OriginalC = lookupSCC(N&: OriginalN);
1624 RefSCC *OriginalRC = lookupRefSCC(N&: OriginalN);
1625
1626#ifdef EXPENSIVE_CHECKS
1627 OriginalRC->verify();
1628 llvm::scope_exit VerifyOnExit([&]() { OriginalRC->verify(); });
1629#endif
1630
1631 assert(!lookup(NewFunction) &&
1632 "New function's node should not already exist");
1633 Node &NewN = initNode(F&: NewFunction);
1634
1635 Edge::Kind EK = getEdgeKind(OriginalFunction, NewFunction);
1636
1637 SCC *NewC = nullptr;
1638 for (Edge &E : *NewN) {
1639 Node &EN = E.getNode();
1640 if (EK == Edge::Kind::Call && E.isCall() && lookupSCC(N&: EN) == OriginalC) {
1641 // If the edge to the new function is a call edge and there is a call edge
1642 // from the new function to any function in the original function's SCC,
1643 // it is in the same SCC (and RefSCC) as the original function.
1644 NewC = OriginalC;
1645 NewC->Nodes.push_back(Elt: &NewN);
1646 break;
1647 }
1648 }
1649
1650 if (!NewC) {
1651 for (Edge &E : *NewN) {
1652 Node &EN = E.getNode();
1653 if (lookupRefSCC(N&: EN) == OriginalRC) {
1654 // If there is any edge from the new function to any function in the
1655 // original function's RefSCC, it is in the same RefSCC as the original
1656 // function but a new SCC.
1657 RefSCC *NewRC = OriginalRC;
1658 NewC = createSCC(Args&: *NewRC, Args: SmallVector<Node *, 1>({&NewN}));
1659
1660 // The new function's SCC is not the same as the original function's
1661 // SCC, since that case was handled earlier. If the edge from the
1662 // original function to the new function was a call edge, then we need
1663 // to insert the newly created function's SCC before the original
1664 // function's SCC. Otherwise, either the new SCC comes after the
1665 // original function's SCC, or it doesn't matter, and in both cases we
1666 // can add it to the very end.
1667 int InsertIndex = EK == Edge::Kind::Call ? NewRC->SCCIndices[OriginalC]
1668 : NewRC->SCCIndices.size();
1669 NewRC->SCCs.insert(I: NewRC->SCCs.begin() + InsertIndex, Elt: NewC);
1670 for (int I = InsertIndex, Size = NewRC->SCCs.size(); I < Size; ++I)
1671 NewRC->SCCIndices[NewRC->SCCs[I]] = I;
1672
1673 break;
1674 }
1675 }
1676 }
1677
1678 if (!NewC) {
1679 // We didn't find any edges back to the original function's RefSCC, so the
1680 // new function belongs in a new RefSCC. The new RefSCC goes before the
1681 // original function's RefSCC.
1682 RefSCC *NewRC = createRefSCC(Args&: *this);
1683 NewC = createSCC(Args&: *NewRC, Args: SmallVector<Node *, 1>({&NewN}));
1684 NewRC->SCCIndices[NewC] = 0;
1685 NewRC->SCCs.push_back(Elt: NewC);
1686 auto OriginalRCIndex = RefSCCIndices.find(Val: OriginalRC)->second;
1687 PostOrderRefSCCs.insert(I: PostOrderRefSCCs.begin() + OriginalRCIndex, Elt: NewRC);
1688 for (int I = OriginalRCIndex, Size = PostOrderRefSCCs.size(); I < Size; ++I)
1689 RefSCCIndices[PostOrderRefSCCs[I]] = I;
1690 }
1691
1692 SCCMap[&NewN] = NewC;
1693
1694 OriginalN->insertEdgeInternal(TargetN&: NewN, EK);
1695}
1696
1697void LazyCallGraph::addSplitRefRecursiveFunctions(
1698 Function &OriginalFunction, ArrayRef<Function *> NewFunctions) {
1699 assert(!NewFunctions.empty() && "Can't add zero functions");
1700 assert(lookup(OriginalFunction) &&
1701 "Original function's node should already exist");
1702 Node &OriginalN = get(F&: OriginalFunction);
1703 RefSCC *OriginalRC = lookupRefSCC(N&: OriginalN);
1704
1705#ifdef EXPENSIVE_CHECKS
1706 OriginalRC->verify();
1707 llvm::scope_exit VerifyOnExit([&]() {
1708 OriginalRC->verify();
1709 for (Function *NewFunction : NewFunctions)
1710 lookupRefSCC(get(*NewFunction))->verify();
1711 });
1712#endif
1713
1714 bool ExistsRefToOriginalRefSCC = false;
1715
1716 for (Function *NewFunction : NewFunctions) {
1717 Node &NewN = initNode(F&: *NewFunction);
1718
1719 OriginalN->insertEdgeInternal(TargetN&: NewN, EK: Edge::Kind::Ref);
1720
1721 // Check if there is any edge from any new function back to any function in
1722 // the original function's RefSCC.
1723 for (Edge &E : *NewN) {
1724 if (lookupRefSCC(N&: E.getNode()) == OriginalRC) {
1725 ExistsRefToOriginalRefSCC = true;
1726 break;
1727 }
1728 }
1729 }
1730
1731 RefSCC *NewRC;
1732 if (ExistsRefToOriginalRefSCC) {
1733 // If there is any edge from any new function to any function in the
1734 // original function's RefSCC, all new functions will be in the same RefSCC
1735 // as the original function.
1736 NewRC = OriginalRC;
1737 } else {
1738 // Otherwise the new functions are in their own RefSCC.
1739 NewRC = createRefSCC(Args&: *this);
1740 // The new RefSCC goes before the original function's RefSCC in postorder
1741 // since there are only edges from the original function's RefSCC to the new
1742 // RefSCC.
1743 auto OriginalRCIndex = RefSCCIndices.find(Val: OriginalRC)->second;
1744 PostOrderRefSCCs.insert(I: PostOrderRefSCCs.begin() + OriginalRCIndex, Elt: NewRC);
1745 for (int I = OriginalRCIndex, Size = PostOrderRefSCCs.size(); I < Size; ++I)
1746 RefSCCIndices[PostOrderRefSCCs[I]] = I;
1747 }
1748
1749 for (Function *NewFunction : NewFunctions) {
1750 Node &NewN = get(F&: *NewFunction);
1751 // Each new function is in its own new SCC. The original function can only
1752 // have a ref edge to new functions, and no other existing functions can
1753 // have references to new functions. Each new function only has a ref edge
1754 // to the other new functions.
1755 SCC *NewC = createSCC(Args&: *NewRC, Args: SmallVector<Node *, 1>({&NewN}));
1756 // The new SCCs are either sibling SCCs or parent SCCs to all other existing
1757 // SCCs in the RefSCC. Either way, they can go at the back of the postorder
1758 // SCC list.
1759 auto Index = NewRC->SCCIndices.size();
1760 NewRC->SCCIndices[NewC] = Index;
1761 NewRC->SCCs.push_back(Elt: NewC);
1762 SCCMap[&NewN] = NewC;
1763 }
1764
1765#ifndef NDEBUG
1766 for (Function *F1 : NewFunctions) {
1767 assert(getEdgeKind(OriginalFunction, *F1) == Edge::Kind::Ref &&
1768 "Expected ref edges from original function to every new function");
1769 Node &N1 = get(*F1);
1770 for (Function *F2 : NewFunctions) {
1771 if (F1 == F2)
1772 continue;
1773 Node &N2 = get(*F2);
1774 assert(!N1->lookup(N2)->isCall() &&
1775 "Edges between new functions must be ref edges");
1776 }
1777 }
1778#endif
1779}
1780
1781LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) {
1782 return *new (MappedN = BPA.Allocate()) Node(*this, F);
1783}
1784
1785void LazyCallGraph::updateGraphPtrs() {
1786 // Walk the node map to update their graph pointers. While this iterates in
1787 // an unstable order, the order has no effect, so it remains correct.
1788 for (auto &FunctionNodePair : NodeMap)
1789 FunctionNodePair.second->G = this;
1790
1791 for (auto *RC : PostOrderRefSCCs)
1792 RC->G = this;
1793}
1794
1795LazyCallGraph::Node &LazyCallGraph::initNode(Function &F) {
1796 Node &N = get(F);
1797 N.DFSNumber = N.LowLink = -1;
1798 N.populate();
1799 NodeMap[&F] = &N;
1800 return N;
1801}
1802
1803template <typename RootsT, typename GetBeginT, typename GetEndT,
1804 typename GetNodeT, typename FormSCCCallbackT>
1805void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
1806 GetEndT &&GetEnd, GetNodeT &&GetNode,
1807 FormSCCCallbackT &&FormSCC) {
1808 using EdgeItT = decltype(GetBegin(std::declval<Node &>()));
1809
1810 SmallVector<std::pair<Node *, EdgeItT>, 16> DFSStack;
1811 SmallVector<Node *, 16> PendingSCCStack;
1812
1813 // Scan down the stack and DFS across the call edges.
1814 for (Node *RootN : Roots) {
1815 assert(DFSStack.empty() &&
1816 "Cannot begin a new root with a non-empty DFS stack!");
1817 assert(PendingSCCStack.empty() &&
1818 "Cannot begin a new root with pending nodes for an SCC!");
1819
1820 // Skip any nodes we've already reached in the DFS.
1821 if (RootN->DFSNumber != 0) {
1822 assert(RootN->DFSNumber == -1 &&
1823 "Shouldn't have any mid-DFS root nodes!");
1824 continue;
1825 }
1826
1827 RootN->DFSNumber = RootN->LowLink = 1;
1828 int NextDFSNumber = 2;
1829
1830 DFSStack.emplace_back(RootN, GetBegin(*RootN));
1831 do {
1832 auto [N, I] = DFSStack.pop_back_val();
1833 auto E = GetEnd(*N);
1834 while (I != E) {
1835 Node &ChildN = GetNode(I);
1836 if (ChildN.DFSNumber == 0) {
1837 // We haven't yet visited this child, so descend, pushing the current
1838 // node onto the stack.
1839 DFSStack.emplace_back(N, I);
1840
1841 ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
1842 N = &ChildN;
1843 I = GetBegin(*N);
1844 E = GetEnd(*N);
1845 continue;
1846 }
1847
1848 // If the child has already been added to some child component, it
1849 // couldn't impact the low-link of this parent because it isn't
1850 // connected, and thus its low-link isn't relevant so skip it.
1851 if (ChildN.DFSNumber == -1) {
1852 ++I;
1853 continue;
1854 }
1855
1856 // Track the lowest linked child as the lowest link for this node.
1857 assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
1858 if (ChildN.LowLink < N->LowLink)
1859 N->LowLink = ChildN.LowLink;
1860
1861 // Move to the next edge.
1862 ++I;
1863 }
1864
1865 // We've finished processing N and its descendants, put it on our pending
1866 // SCC stack to eventually get merged into an SCC of nodes.
1867 PendingSCCStack.push_back(Elt: N);
1868
1869 // If this node is linked to some lower entry, continue walking up the
1870 // stack.
1871 if (N->LowLink != N->DFSNumber)
1872 continue;
1873
1874 // Otherwise, we've completed an SCC. Append it to our post order list of
1875 // SCCs.
1876 int RootDFSNumber = N->DFSNumber;
1877 // Find the range of the node stack by walking down until we pass the
1878 // root DFS number.
1879 auto SCCNodes = make_range(
1880 PendingSCCStack.rbegin(),
1881 find_if(reverse(C&: PendingSCCStack), [RootDFSNumber](const Node *N) {
1882 return N->DFSNumber < RootDFSNumber;
1883 }));
1884 // Form a new SCC out of these nodes and then clear them off our pending
1885 // stack.
1886 FormSCC(SCCNodes);
1887 PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
1888 } while (!DFSStack.empty());
1889 }
1890}
1891
1892/// Build the internal SCCs for a RefSCC from a sequence of nodes.
1893///
1894/// Appends the SCCs to the provided vector and updates the map with their
1895/// indices. Both the vector and map must be empty when passed into this
1896/// routine.
1897void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {
1898 assert(RC.SCCs.empty() && "Already built SCCs!");
1899 assert(RC.SCCIndices.empty() && "Already mapped SCC indices!");
1900
1901 for (Node *N : Nodes) {
1902 assert(N->LowLink >= (*Nodes.begin())->LowLink &&
1903 "We cannot have a low link in an SCC lower than its root on the "
1904 "stack!");
1905
1906 // This node will go into the next RefSCC, clear out its DFS and low link
1907 // as we scan.
1908 N->DFSNumber = N->LowLink = 0;
1909 }
1910
1911 // Each RefSCC contains a DAG of the call SCCs. To build these, we do
1912 // a direct walk of the call edges using Tarjan's algorithm. We reuse the
1913 // internal storage as we won't need it for the outer graph's DFS any longer.
1914 buildGenericSCCs(
1915 Roots&: Nodes, GetBegin: [](Node &N) { return N->call_begin(); },
1916 GetEnd: [](Node &N) { return N->call_end(); },
1917 GetNode: [](EdgeSequence::call_iterator I) -> Node & { return I->getNode(); },
1918 FormSCC: [this, &RC](node_stack_range Nodes) {
1919 RC.SCCs.push_back(Elt: createSCC(Args&: RC, Args&: Nodes));
1920 for (Node &N : *RC.SCCs.back()) {
1921 N.DFSNumber = N.LowLink = -1;
1922 SCCMap[&N] = RC.SCCs.back();
1923 }
1924 });
1925
1926 // Wire up the SCC indices.
1927 for (int I = 0, Size = RC.SCCs.size(); I < Size; ++I)
1928 RC.SCCIndices[RC.SCCs[I]] = I;
1929}
1930
1931void LazyCallGraph::buildRefSCCs() {
1932 if (EntryEdges.empty() || !PostOrderRefSCCs.empty())
1933 // RefSCCs are either non-existent or already built!
1934 return;
1935
1936 assert(RefSCCIndices.empty() && "Already mapped RefSCC indices!");
1937
1938 SmallVector<Node *, 16> Roots;
1939 for (Edge &E : *this)
1940 Roots.push_back(Elt: &E.getNode());
1941
1942 // The roots will be iterated in order.
1943 buildGenericSCCs(
1944 Roots,
1945 GetBegin: [](Node &N) {
1946 // We need to populate each node as we begin to walk its edges.
1947 N.populate();
1948 return N->begin();
1949 },
1950 GetEnd: [](Node &N) { return N->end(); },
1951 GetNode: [](EdgeSequence::iterator I) -> Node & { return I->getNode(); },
1952 FormSCC: [this](node_stack_range Nodes) {
1953 RefSCC *NewRC = createRefSCC(Args&: *this);
1954 buildSCCs(RC&: *NewRC, Nodes);
1955
1956 // Push the new node into the postorder list and remember its position
1957 // in the index map.
1958 bool Inserted =
1959 RefSCCIndices.try_emplace(Key: NewRC, Args: PostOrderRefSCCs.size()).second;
1960 (void)Inserted;
1961 assert(Inserted && "Cannot already have this RefSCC in the index map!");
1962 PostOrderRefSCCs.push_back(Elt: NewRC);
1963#ifdef EXPENSIVE_CHECKS
1964 NewRC->verify();
1965#endif
1966 });
1967}
1968
1969void LazyCallGraph::visitReferences(SmallVectorImpl<Constant *> &Worklist,
1970 SmallPtrSetImpl<Constant *> &Visited,
1971 function_ref<void(Function &)> Callback) {
1972 while (!Worklist.empty()) {
1973 Constant *C = Worklist.pop_back_val();
1974
1975 if (Function *F = dyn_cast<Function>(Val: C)) {
1976 if (!F->isDeclaration())
1977 Callback(*F);
1978 continue;
1979 }
1980
1981 // blockaddresses are weird and don't participate in the call graph anyway,
1982 // skip them.
1983 if (isa<BlockAddress>(Val: C))
1984 continue;
1985
1986 for (Value *Op : C->operand_values())
1987 if (Visited.insert(Ptr: cast<Constant>(Val: Op)).second)
1988 Worklist.push_back(Elt: cast<Constant>(Val: Op));
1989 }
1990}
1991
1992AnalysisKey LazyCallGraphAnalysis::Key;
1993
1994LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
1995
1996static void printNode(raw_ostream &OS, LazyCallGraph::Node &N) {
1997 OS << " Edges in function: " << N.getFunction().getName() << "\n";
1998 for (LazyCallGraph::Edge &E : N.populate())
1999 OS << " " << (E.isCall() ? "call" : "ref ") << " -> "
2000 << E.getFunction().getName() << "\n";
2001
2002 OS << "\n";
2003}
2004
2005static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &C) {
2006 OS << " SCC with " << C.size() << " functions:\n";
2007
2008 for (LazyCallGraph::Node &N : C)
2009 OS << " " << N.getFunction().getName() << "\n";
2010}
2011
2012static void printRefSCC(raw_ostream &OS, LazyCallGraph::RefSCC &C) {
2013 OS << " RefSCC with " << C.size() << " call SCCs:\n";
2014
2015 for (LazyCallGraph::SCC &InnerC : C)
2016 printSCC(OS, C&: InnerC);
2017
2018 OS << "\n";
2019}
2020
2021PreservedAnalyses LazyCallGraphPrinterPass::run(Module &M,
2022 ModuleAnalysisManager &AM) {
2023 LazyCallGraph &G = AM.getResult<LazyCallGraphAnalysis>(IR&: M);
2024
2025 OS << "Printing the call graph for module: " << M.getModuleIdentifier()
2026 << "\n\n";
2027
2028 for (Function &F : M)
2029 printNode(OS, N&: G.get(F));
2030
2031 G.buildRefSCCs();
2032 for (LazyCallGraph::RefSCC &C : G.postorder_ref_sccs())
2033 printRefSCC(OS, C);
2034
2035 return PreservedAnalyses::all();
2036}
2037
2038LazyCallGraphDOTPrinterPass::LazyCallGraphDOTPrinterPass(raw_ostream &OS)
2039 : OS(OS) {}
2040
2041static void printNodeDOT(raw_ostream &OS, LazyCallGraph::Node &N) {
2042 std::string Name =
2043 "\"" + DOT::EscapeString(Label: std::string(N.getFunction().getName())) + "\"";
2044
2045 for (LazyCallGraph::Edge &E : N.populate()) {
2046 OS << " " << Name << " -> \""
2047 << DOT::EscapeString(Label: std::string(E.getFunction().getName())) << "\"";
2048 if (!E.isCall()) // It is a ref edge.
2049 OS << " [style=dashed,label=\"ref\"]";
2050 OS << ";\n";
2051 }
2052
2053 OS << "\n";
2054}
2055
2056PreservedAnalyses LazyCallGraphDOTPrinterPass::run(Module &M,
2057 ModuleAnalysisManager &AM) {
2058 LazyCallGraph &G = AM.getResult<LazyCallGraphAnalysis>(IR&: M);
2059
2060 OS << "digraph \"" << DOT::EscapeString(Label: M.getModuleIdentifier()) << "\" {\n";
2061
2062 for (Function &F : M)
2063 printNodeDOT(OS, N&: G.get(F));
2064
2065 OS << "}\n";
2066
2067 return PreservedAnalyses::all();
2068}
2069