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