1 //===- LazyCallGraph.cpp - Analysis of a Module's call graph --------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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/IR/CallSite.h"
20 #include "llvm/IR/Function.h"
21 #include "llvm/IR/GlobalVariable.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"
40 #define DEBUG_TYPE "lcg"
42 void LazyCallGraph::EdgeSequence::insertEdgeInternal(Node &TargetN,
44 EdgeIndexMap.insert({&TargetN, Edges.size()});
45 Edges.emplace_back(TargetN, EK);
48 void LazyCallGraph::EdgeSequence::setEdgeKind(Node &TargetN, Edge::Kind EK) {
49 Edges[EdgeIndexMap.find(&TargetN)->second].setKind(EK);
52 bool LazyCallGraph::EdgeSequence::removeEdgeInternal(Node &TargetN) {
53 auto IndexMapI = EdgeIndexMap.find(&TargetN);
54 if (IndexMapI == EdgeIndexMap.end())
57 Edges[IndexMapI->second] = Edge();
58 EdgeIndexMap.erase(IndexMapI);
62 static void addEdge(SmallVectorImpl<LazyCallGraph::Edge> &Edges,
63 DenseMap<LazyCallGraph::Node *, int> &EdgeIndexMap,
64 LazyCallGraph::Node &N, LazyCallGraph::Edge::Kind EK) {
65 if (!EdgeIndexMap.insert({&N, Edges.size()}).second)
68 DEBUG(dbgs() << " Added callable function: " << N.getName() << "\n");
69 Edges.emplace_back(LazyCallGraph::Edge(N, EK));
72 LazyCallGraph::EdgeSequence &LazyCallGraph::Node::populateSlow() {
73 assert(!Edges && "Must not have already populated the edges for this node!");
75 DEBUG(dbgs() << " Adding functions called by '" << getName()
76 << "' to the graph.\n");
78 Edges = EdgeSequence();
80 SmallVector<Constant *, 16> Worklist;
81 SmallPtrSet<Function *, 4> Callees;
82 SmallPtrSet<Constant *, 16> Visited;
84 // Find all the potential call graph edges in this function. We track both
85 // actual call edges and indirect references to functions. The direct calls
86 // are trivially added, but to accumulate the latter we walk the instructions
87 // and add every operand which is a constant to the worklist to process
90 // Note that we consider *any* function with a definition to be a viable
91 // edge. Even if the function's definition is subject to replacement by
92 // some other module (say, a weak definition) there may still be
93 // optimizations which essentially speculate based on the definition and
94 // a way to check that the specific definition is in fact the one being
95 // used. For example, this could be done by moving the weak definition to
96 // a strong (internal) definition and making the weak definition be an
97 // alias. Then a test of the address of the weak function against the new
98 // strong definition's address would be an effective way to determine the
99 // safety of optimizing a direct call edge.
100 for (BasicBlock &BB : *F)
101 for (Instruction &I : BB) {
102 if (auto CS = CallSite(&I))
103 if (Function *Callee = CS.getCalledFunction())
104 if (!Callee->isDeclaration())
105 if (Callees.insert(Callee).second) {
106 Visited.insert(Callee);
107 addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(*Callee),
108 LazyCallGraph::Edge::Call);
111 for (Value *Op : I.operand_values())
112 if (Constant *C = dyn_cast<Constant>(Op))
113 if (Visited.insert(C).second)
114 Worklist.push_back(C);
117 // We've collected all the constant (and thus potentially function or
118 // function containing) operands to all of the instructions in the function.
119 // Process them (recursively) collecting every function found.
120 visitReferences(Worklist, Visited, [&](Function &F) {
121 addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(F),
122 LazyCallGraph::Edge::Ref);
125 // Add implicit reference edges to any defined libcall functions (if we
126 // haven't found an explicit edge).
127 for (auto *F : G->LibFunctions)
128 if (!Visited.count(F))
129 addEdge(Edges->Edges, Edges->EdgeIndexMap, G->get(*F),
130 LazyCallGraph::Edge::Ref);
135 void LazyCallGraph::Node::replaceFunction(Function &NewF) {
136 assert(F != &NewF && "Must not replace a function with itself!");
140 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
141 LLVM_DUMP_METHOD void LazyCallGraph::Node::dump() const {
142 dbgs() << *this << '\n';
146 static bool isKnownLibFunction(Function &F, TargetLibraryInfo &TLI) {
149 // Either this is a normal library function or a "vectorizable" function.
150 return TLI.getLibFunc(F, LF) || TLI.isFunctionVectorizable(F.getName());
153 LazyCallGraph::LazyCallGraph(Module &M, TargetLibraryInfo &TLI) {
154 DEBUG(dbgs() << "Building CG for module: " << M.getModuleIdentifier()
156 for (Function &F : M) {
157 if (F.isDeclaration())
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))
163 LibFunctions.insert(&F);
165 if (F.hasLocalLinkage())
168 // External linkage defined functions have edges to them from other
170 DEBUG(dbgs() << " Adding '" << F.getName()
171 << "' to entry set of the graph.\n");
172 addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F), Edge::Ref);
175 // Now add entry nodes for functions reachable via initializers to globals.
176 SmallVector<Constant *, 16> Worklist;
177 SmallPtrSet<Constant *, 16> Visited;
178 for (GlobalVariable &GV : M.globals())
179 if (GV.hasInitializer())
180 if (Visited.insert(GV.getInitializer()).second)
181 Worklist.push_back(GV.getInitializer());
183 DEBUG(dbgs() << " Adding functions referenced by global initializers to the "
185 visitReferences(Worklist, Visited, [&](Function &F) {
186 addEdge(EntryEdges.Edges, EntryEdges.EdgeIndexMap, get(F),
187 LazyCallGraph::Edge::Ref);
191 LazyCallGraph::LazyCallGraph(LazyCallGraph &&G)
192 : BPA(std::move(G.BPA)), NodeMap(std::move(G.NodeMap)),
193 EntryEdges(std::move(G.EntryEdges)), SCCBPA(std::move(G.SCCBPA)),
194 SCCMap(std::move(G.SCCMap)),
195 LibFunctions(std::move(G.LibFunctions)) {
199 LazyCallGraph &LazyCallGraph::operator=(LazyCallGraph &&G) {
200 BPA = std::move(G.BPA);
201 NodeMap = std::move(G.NodeMap);
202 EntryEdges = std::move(G.EntryEdges);
203 SCCBPA = std::move(G.SCCBPA);
204 SCCMap = std::move(G.SCCMap);
205 LibFunctions = std::move(G.LibFunctions);
210 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
211 LLVM_DUMP_METHOD void LazyCallGraph::SCC::dump() const {
212 dbgs() << *this << '\n';
217 void LazyCallGraph::SCC::verify() {
218 assert(OuterRefSCC && "Can't have a null RefSCC!");
219 assert(!Nodes.empty() && "Can't have an empty SCC!");
221 for (Node *N : Nodes) {
222 assert(N && "Can't have a null node!");
223 assert(OuterRefSCC->G->lookupSCC(*N) == this &&
224 "Node does not map to this SCC!");
225 assert(N->DFSNumber == -1 &&
226 "Must set DFS numbers to -1 when adding a node to an SCC!");
227 assert(N->LowLink == -1 &&
228 "Must set low link to -1 when adding a node to an SCC!");
230 assert(E.getNode().isPopulated() && "Can't have an unpopulated node!");
235 bool LazyCallGraph::SCC::isParentOf(const SCC &C) const {
239 for (Node &N : *this)
240 for (Edge &E : N->calls())
241 if (OuterRefSCC->G->lookupSCC(E.getNode()) == &C)
248 bool LazyCallGraph::SCC::isAncestorOf(const SCC &TargetC) const {
249 if (this == &TargetC)
252 LazyCallGraph &G = *OuterRefSCC->G;
254 // Start with this SCC.
255 SmallPtrSet<const SCC *, 16> Visited = {this};
256 SmallVector<const SCC *, 16> Worklist = {this};
258 // Walk down the graph until we run out of edges or find a path to TargetC.
260 const SCC &C = *Worklist.pop_back_val();
262 for (Edge &E : N->calls()) {
263 SCC *CalleeC = G.lookupSCC(E.getNode());
267 // If the callee's SCC is the TargetC, we're done.
268 if (CalleeC == &TargetC)
271 // If this is the first time we've reached this SCC, put it on the
272 // worklist to recurse through.
273 if (Visited.insert(CalleeC).second)
274 Worklist.push_back(CalleeC);
276 } while (!Worklist.empty());
282 LazyCallGraph::RefSCC::RefSCC(LazyCallGraph &G) : G(&G) {}
284 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
285 LLVM_DUMP_METHOD void LazyCallGraph::RefSCC::dump() const {
286 dbgs() << *this << '\n';
291 void LazyCallGraph::RefSCC::verify() {
292 assert(G && "Can't have a null graph!");
293 assert(!SCCs.empty() && "Can't have an empty SCC!");
295 // Verify basic properties of the SCCs.
296 SmallPtrSet<SCC *, 4> SCCSet;
297 for (SCC *C : SCCs) {
298 assert(C && "Can't have a null SCC!");
300 assert(&C->getOuterRefSCC() == this &&
301 "SCC doesn't think it is inside this RefSCC!");
302 bool Inserted = SCCSet.insert(C).second;
303 assert(Inserted && "Found a duplicate SCC!");
304 auto IndexIt = SCCIndices.find(C);
305 assert(IndexIt != SCCIndices.end() &&
306 "Found an SCC that doesn't have an index!");
309 // Check that our indices map correctly.
310 for (auto &SCCIndexPair : SCCIndices) {
311 SCC *C = SCCIndexPair.first;
312 int i = SCCIndexPair.second;
313 assert(C && "Can't have a null SCC in the indices!");
314 assert(SCCSet.count(C) && "Found an index for an SCC not in the RefSCC!");
315 assert(SCCs[i] == C && "Index doesn't point to SCC!");
318 // Check that the SCCs are in fact in post-order.
319 for (int i = 0, Size = SCCs.size(); i < Size; ++i) {
320 SCC &SourceSCC = *SCCs[i];
321 for (Node &N : SourceSCC)
325 SCC &TargetSCC = *G->lookupSCC(E.getNode());
326 if (&TargetSCC.getOuterRefSCC() == this) {
327 assert(SCCIndices.find(&TargetSCC)->second <= i &&
328 "Edge between SCCs violates post-order relationship.");
336 bool LazyCallGraph::RefSCC::isParentOf(const RefSCC &RC) const {
340 // Search all edges to see if this is a parent.
344 if (G->lookupRefSCC(E.getNode()) == &RC)
350 bool LazyCallGraph::RefSCC::isAncestorOf(const RefSCC &RC) const {
354 // For each descendant of this RefSCC, see if one of its children is the
355 // argument. If not, add that descendant to the worklist and continue
357 SmallVector<const RefSCC *, 4> Worklist;
358 SmallPtrSet<const RefSCC *, 4> Visited;
359 Worklist.push_back(this);
360 Visited.insert(this);
362 const RefSCC &DescendantRC = *Worklist.pop_back_val();
363 for (SCC &C : DescendantRC)
366 auto *ChildRC = G->lookupRefSCC(E.getNode());
369 if (!ChildRC || !Visited.insert(ChildRC).second)
371 Worklist.push_back(ChildRC);
373 } while (!Worklist.empty());
378 /// Generic helper that updates a postorder sequence of SCCs for a potentially
379 /// cycle-introducing edge insertion.
381 /// A postorder sequence of SCCs of a directed graph has one fundamental
382 /// property: all deges in the DAG of SCCs point "up" the sequence. That is,
383 /// all edges in the SCC DAG point to prior SCCs in the sequence.
385 /// This routine both updates a postorder sequence and uses that sequence to
386 /// compute the set of SCCs connected into a cycle. It should only be called to
387 /// insert a "downward" edge which will require changing the sequence to
388 /// restore it to a postorder.
390 /// When inserting an edge from an earlier SCC to a later SCC in some postorder
391 /// sequence, all of the SCCs which may be impacted are in the closed range of
392 /// those two within the postorder sequence. The algorithm used here to restore
393 /// the state is as follows:
395 /// 1) Starting from the source SCC, construct a set of SCCs which reach the
396 /// source SCC consisting of just the source SCC. Then scan toward the
397 /// target SCC in postorder and for each SCC, if it has an edge to an SCC
398 /// in the set, add it to the set. Otherwise, the source SCC is not
399 /// a successor, move it in the postorder sequence to immediately before
400 /// the source SCC, shifting the source SCC and all SCCs in the set one
401 /// position toward the target SCC. Stop scanning after processing the
403 /// 2) If the source SCC is now past the target SCC in the postorder sequence,
404 /// and thus the new edge will flow toward the start, we are done.
405 /// 3) Otherwise, starting from the target SCC, walk all edges which reach an
406 /// SCC between the source and the target, and add them to the set of
407 /// connected SCCs, then recurse through them. Once a complete set of the
408 /// SCCs the target connects to is known, hoist the remaining SCCs between
409 /// the source and the target to be above the target. Note that there is no
410 /// need to process the source SCC, it is already known to connect.
411 /// 4) At this point, all of the SCCs in the closed range between the source
412 /// SCC and the target SCC in the postorder sequence are connected,
413 /// including the target SCC and the source SCC. Inserting the edge from
414 /// the source SCC to the target SCC will form a cycle out of precisely
415 /// these SCCs. Thus we can merge all of the SCCs in this closed range into
418 /// This process has various important properties:
419 /// - Only mutates the SCCs when adding the edge actually changes the SCC
421 /// - Never mutates SCCs which are unaffected by the change.
422 /// - Updates the postorder sequence to correctly satisfy the postorder
423 /// constraint after the edge is inserted.
424 /// - Only reorders SCCs in the closed postorder sequence from the source to
425 /// the target, so easy to bound how much has changed even in the ordering.
426 /// - Big-O is the number of edges in the closed postorder range of SCCs from
427 /// source to target.
429 /// This helper routine, in addition to updating the postorder sequence itself
430 /// will also update a map from SCCs to indices within that sequecne.
432 /// The sequence and the map must operate on pointers to the SCC type.
434 /// Two callbacks must be provided. The first computes the subset of SCCs in
435 /// the postorder closed range from the source to the target which connect to
436 /// the source SCC via some (transitive) set of edges. The second computes the
437 /// subset of the same range which the target SCC connects to via some
438 /// (transitive) set of edges. Both callbacks should populate the set argument
440 template <typename SCCT, typename PostorderSequenceT, typename SCCIndexMapT,
441 typename ComputeSourceConnectedSetCallableT,
442 typename ComputeTargetConnectedSetCallableT>
443 static iterator_range<typename PostorderSequenceT::iterator>
444 updatePostorderSequenceForEdgeInsertion(
445 SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs,
446 SCCIndexMapT &SCCIndices,
447 ComputeSourceConnectedSetCallableT ComputeSourceConnectedSet,
448 ComputeTargetConnectedSetCallableT ComputeTargetConnectedSet) {
449 int SourceIdx = SCCIndices[&SourceSCC];
450 int TargetIdx = SCCIndices[&TargetSCC];
451 assert(SourceIdx < TargetIdx && "Cannot have equal indices here!");
453 SmallPtrSet<SCCT *, 4> ConnectedSet;
455 // Compute the SCCs which (transitively) reach the source.
456 ComputeSourceConnectedSet(ConnectedSet);
458 // Partition the SCCs in this part of the port-order sequence so only SCCs
459 // connecting to the source remain between it and the target. This is
460 // a benign partition as it preserves postorder.
461 auto SourceI = std::stable_partition(
462 SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1,
463 [&ConnectedSet](SCCT *C) { return !ConnectedSet.count(C); });
464 for (int i = SourceIdx, e = TargetIdx + 1; i < e; ++i)
465 SCCIndices.find(SCCs[i])->second = i;
467 // If the target doesn't connect to the source, then we've corrected the
468 // post-order and there are no cycles formed.
469 if (!ConnectedSet.count(&TargetSCC)) {
470 assert(SourceI > (SCCs.begin() + SourceIdx) &&
471 "Must have moved the source to fix the post-order.");
472 assert(*std::prev(SourceI) == &TargetSCC &&
473 "Last SCC to move should have bene the target.");
475 // Return an empty range at the target SCC indicating there is nothing to
477 return make_range(std::prev(SourceI), std::prev(SourceI));
480 assert(SCCs[TargetIdx] == &TargetSCC &&
481 "Should not have moved target if connected!");
482 SourceIdx = SourceI - SCCs.begin();
483 assert(SCCs[SourceIdx] == &SourceSCC &&
484 "Bad updated index computation for the source SCC!");
487 // See whether there are any remaining intervening SCCs between the source
488 // and target. If so we need to make sure they all are reachable form the
490 if (SourceIdx + 1 < TargetIdx) {
491 ConnectedSet.clear();
492 ComputeTargetConnectedSet(ConnectedSet);
494 // Partition SCCs so that only SCCs reached from the target remain between
495 // the source and the target. This preserves postorder.
496 auto TargetI = std::stable_partition(
497 SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1,
498 [&ConnectedSet](SCCT *C) { return ConnectedSet.count(C); });
499 for (int i = SourceIdx + 1, e = TargetIdx + 1; i < e; ++i)
500 SCCIndices.find(SCCs[i])->second = i;
501 TargetIdx = std::prev(TargetI) - SCCs.begin();
502 assert(SCCs[TargetIdx] == &TargetSCC &&
503 "Should always end with the target!");
506 // At this point, we know that connecting source to target forms a cycle
507 // because target connects back to source, and we know that all of the SCCs
508 // between the source and target in the postorder sequence participate in that
510 return make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx);
514 LazyCallGraph::RefSCC::switchInternalEdgeToCall(
515 Node &SourceN, Node &TargetN,
516 function_ref<void(ArrayRef<SCC *> MergeSCCs)> MergeCB) {
517 assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");
518 SmallVector<SCC *, 1> DeletedSCCs;
521 // In a debug build, verify the RefSCC is valid to start with and when this
524 auto VerifyOnExit = make_scope_exit([&]() { verify(); });
527 SCC &SourceSCC = *G->lookupSCC(SourceN);
528 SCC &TargetSCC = *G->lookupSCC(TargetN);
530 // If the two nodes are already part of the same SCC, we're also done as
531 // we've just added more connectivity.
532 if (&SourceSCC == &TargetSCC) {
533 SourceN->setEdgeKind(TargetN, Edge::Call);
534 return false; // No new cycle.
537 // At this point we leverage the postorder list of SCCs to detect when the
538 // insertion of an edge changes the SCC structure in any way.
540 // First and foremost, we can eliminate the need for any changes when the
541 // edge is toward the beginning of the postorder sequence because all edges
542 // flow in that direction already. Thus adding a new one cannot form a cycle.
543 int SourceIdx = SCCIndices[&SourceSCC];
544 int TargetIdx = SCCIndices[&TargetSCC];
545 if (TargetIdx < SourceIdx) {
546 SourceN->setEdgeKind(TargetN, Edge::Call);
547 return false; // No new cycle.
550 // Compute the SCCs which (transitively) reach the source.
551 auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {
553 // Check that the RefSCC is still valid before computing this as the
554 // results will be nonsensical of we've broken its invariants.
557 ConnectedSet.insert(&SourceSCC);
558 auto IsConnected = [&](SCC &C) {
560 for (Edge &E : N->calls())
561 if (ConnectedSet.count(G->lookupSCC(E.getNode())))
568 make_range(SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1))
570 ConnectedSet.insert(C);
573 // Use a normal worklist to find which SCCs the target connects to. We still
574 // bound the search based on the range in the postorder list we care about,
575 // but because this is forward connectivity we just "recurse" through the
577 auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {
579 // Check that the RefSCC is still valid before computing this as the
580 // results will be nonsensical of we've broken its invariants.
583 ConnectedSet.insert(&TargetSCC);
584 SmallVector<SCC *, 4> Worklist;
585 Worklist.push_back(&TargetSCC);
587 SCC &C = *Worklist.pop_back_val();
592 SCC &EdgeC = *G->lookupSCC(E.getNode());
593 if (&EdgeC.getOuterRefSCC() != this)
594 // Not in this RefSCC...
596 if (SCCIndices.find(&EdgeC)->second <= SourceIdx)
597 // Not in the postorder sequence between source and target.
600 if (ConnectedSet.insert(&EdgeC).second)
601 Worklist.push_back(&EdgeC);
603 } while (!Worklist.empty());
606 // Use a generic helper to update the postorder sequence of SCCs and return
607 // a range of any SCCs connected into a cycle by inserting this edge. This
608 // routine will also take care of updating the indices into the postorder
610 auto MergeRange = updatePostorderSequenceForEdgeInsertion(
611 SourceSCC, TargetSCC, SCCs, SCCIndices, ComputeSourceConnectedSet,
612 ComputeTargetConnectedSet);
614 // Run the user's callback on the merged SCCs before we actually merge them.
616 MergeCB(makeArrayRef(MergeRange.begin(), MergeRange.end()));
618 // If the merge range is empty, then adding the edge didn't actually form any
619 // new cycles. We're done.
620 if (MergeRange.begin() == MergeRange.end()) {
621 // Now that the SCC structure is finalized, flip the kind to call.
622 SourceN->setEdgeKind(TargetN, Edge::Call);
623 return false; // No new cycle.
627 // Before merging, check that the RefSCC remains valid after all the
628 // postorder updates.
632 // Otherwise we need to merge all of the SCCs in the cycle into a single
635 // NB: We merge into the target because all of these functions were already
636 // reachable from the target, meaning any SCC-wide properties deduced about it
637 // other than the set of functions within it will not have changed.
638 for (SCC *C : MergeRange) {
639 assert(C != &TargetSCC &&
640 "We merge *into* the target and shouldn't process it here!");
642 TargetSCC.Nodes.append(C->Nodes.begin(), C->Nodes.end());
643 for (Node *N : C->Nodes)
644 G->SCCMap[N] = &TargetSCC;
646 DeletedSCCs.push_back(C);
649 // Erase the merged SCCs from the list and update the indices of the
651 int IndexOffset = MergeRange.end() - MergeRange.begin();
652 auto EraseEnd = SCCs.erase(MergeRange.begin(), MergeRange.end());
653 for (SCC *C : make_range(EraseEnd, SCCs.end()))
654 SCCIndices[C] -= IndexOffset;
656 // Now that the SCC structure is finalized, flip the kind to call.
657 SourceN->setEdgeKind(TargetN, Edge::Call);
659 // And we're done, but we did form a new cycle.
663 void LazyCallGraph::RefSCC::switchTrivialInternalEdgeToRef(Node &SourceN,
665 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
668 // In a debug build, verify the RefSCC is valid to start with and when this
671 auto VerifyOnExit = make_scope_exit([&]() { verify(); });
674 assert(G->lookupRefSCC(SourceN) == this &&
675 "Source must be in this RefSCC.");
676 assert(G->lookupRefSCC(TargetN) == this &&
677 "Target must be in this RefSCC.");
678 assert(G->lookupSCC(SourceN) != G->lookupSCC(TargetN) &&
679 "Source and Target must be in separate SCCs for this to be trivial!");
681 // Set the edge kind.
682 SourceN->setEdgeKind(TargetN, Edge::Ref);
685 iterator_range<LazyCallGraph::RefSCC::iterator>
686 LazyCallGraph::RefSCC::switchInternalEdgeToRef(Node &SourceN, Node &TargetN) {
687 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
690 // In a debug build, verify the RefSCC is valid to start with and when this
693 auto VerifyOnExit = make_scope_exit([&]() { verify(); });
696 assert(G->lookupRefSCC(SourceN) == this &&
697 "Source must be in this RefSCC.");
698 assert(G->lookupRefSCC(TargetN) == this &&
699 "Target must be in this RefSCC.");
701 SCC &TargetSCC = *G->lookupSCC(TargetN);
702 assert(G->lookupSCC(SourceN) == &TargetSCC && "Source and Target must be in "
703 "the same SCC to require the "
706 // Set the edge kind.
707 SourceN->setEdgeKind(TargetN, Edge::Ref);
709 // Otherwise we are removing a call edge from a single SCC. This may break
710 // the cycle. In order to compute the new set of SCCs, we need to do a small
711 // DFS over the nodes within the SCC to form any sub-cycles that remain as
712 // distinct SCCs and compute a postorder over the resulting SCCs.
714 // However, we specially handle the target node. The target node is known to
715 // reach all other nodes in the original SCC by definition. This means that
716 // we want the old SCC to be replaced with an SCC contaning that node as it
717 // will be the root of whatever SCC DAG results from the DFS. Assumptions
718 // about an SCC such as the set of functions called will continue to hold,
721 SCC &OldSCC = TargetSCC;
722 SmallVector<std::pair<Node *, EdgeSequence::call_iterator>, 16> DFSStack;
723 SmallVector<Node *, 16> PendingSCCStack;
724 SmallVector<SCC *, 4> NewSCCs;
726 // Prepare the nodes for a fresh DFS.
727 SmallVector<Node *, 16> Worklist;
728 Worklist.swap(OldSCC.Nodes);
729 for (Node *N : Worklist) {
730 N->DFSNumber = N->LowLink = 0;
734 // Force the target node to be in the old SCC. This also enables us to take
735 // a very significant short-cut in the standard Tarjan walk to re-form SCCs
736 // below: whenever we build an edge that reaches the target node, we know
737 // that the target node eventually connects back to all other nodes in our
738 // walk. As a consequence, we can detect and handle participants in that
739 // cycle without walking all the edges that form this connection, and instead
740 // by relying on the fundamental guarantee coming into this operation (all
741 // nodes are reachable from the target due to previously forming an SCC).
742 TargetN.DFSNumber = TargetN.LowLink = -1;
743 OldSCC.Nodes.push_back(&TargetN);
744 G->SCCMap[&TargetN] = &OldSCC;
746 // Scan down the stack and DFS across the call edges.
747 for (Node *RootN : Worklist) {
748 assert(DFSStack.empty() &&
749 "Cannot begin a new root with a non-empty DFS stack!");
750 assert(PendingSCCStack.empty() &&
751 "Cannot begin a new root with pending nodes for an SCC!");
753 // Skip any nodes we've already reached in the DFS.
754 if (RootN->DFSNumber != 0) {
755 assert(RootN->DFSNumber == -1 &&
756 "Shouldn't have any mid-DFS root nodes!");
760 RootN->DFSNumber = RootN->LowLink = 1;
761 int NextDFSNumber = 2;
763 DFSStack.push_back({RootN, (*RootN)->call_begin()});
766 EdgeSequence::call_iterator I;
767 std::tie(N, I) = DFSStack.pop_back_val();
768 auto E = (*N)->call_end();
770 Node &ChildN = I->getNode();
771 if (ChildN.DFSNumber == 0) {
772 // We haven't yet visited this child, so descend, pushing the current
773 // node onto the stack.
774 DFSStack.push_back({N, I});
776 assert(!G->SCCMap.count(&ChildN) &&
777 "Found a node with 0 DFS number but already in an SCC!");
778 ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
780 I = (*N)->call_begin();
781 E = (*N)->call_end();
785 // Check for the child already being part of some component.
786 if (ChildN.DFSNumber == -1) {
787 if (G->lookupSCC(ChildN) == &OldSCC) {
788 // If the child is part of the old SCC, we know that it can reach
789 // every other node, so we have formed a cycle. Pull the entire DFS
790 // and pending stacks into it. See the comment above about setting
791 // up the old SCC for why we do this.
792 int OldSize = OldSCC.size();
793 OldSCC.Nodes.push_back(N);
794 OldSCC.Nodes.append(PendingSCCStack.begin(), PendingSCCStack.end());
795 PendingSCCStack.clear();
796 while (!DFSStack.empty())
797 OldSCC.Nodes.push_back(DFSStack.pop_back_val().first);
798 for (Node &N : make_range(OldSCC.begin() + OldSize, OldSCC.end())) {
799 N.DFSNumber = N.LowLink = -1;
800 G->SCCMap[&N] = &OldSCC;
806 // If the child has already been added to some child component, it
807 // couldn't impact the low-link of this parent because it isn't
808 // connected, and thus its low-link isn't relevant so skip it.
813 // Track the lowest linked child as the lowest link for this node.
814 assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
815 if (ChildN.LowLink < N->LowLink)
816 N->LowLink = ChildN.LowLink;
818 // Move to the next edge.
822 // Cleared the DFS early, start another round.
825 // We've finished processing N and its descendents, put it on our pending
826 // SCC stack to eventually get merged into an SCC of nodes.
827 PendingSCCStack.push_back(N);
829 // If this node is linked to some lower entry, continue walking up the
831 if (N->LowLink != N->DFSNumber)
834 // Otherwise, we've completed an SCC. Append it to our post order list of
836 int RootDFSNumber = N->DFSNumber;
837 // Find the range of the node stack by walking down until we pass the
839 auto SCCNodes = make_range(
840 PendingSCCStack.rbegin(),
841 find_if(reverse(PendingSCCStack), [RootDFSNumber](const Node *N) {
842 return N->DFSNumber < RootDFSNumber;
845 // Form a new SCC out of these nodes and then clear them off our pending
847 NewSCCs.push_back(G->createSCC(*this, SCCNodes));
848 for (Node &N : *NewSCCs.back()) {
849 N.DFSNumber = N.LowLink = -1;
850 G->SCCMap[&N] = NewSCCs.back();
852 PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
853 } while (!DFSStack.empty());
856 // Insert the remaining SCCs before the old one. The old SCC can reach all
857 // other SCCs we form because it contains the target node of the removed edge
858 // of the old SCC. This means that we will have edges into all of the new
859 // SCCs, which means the old one must come last for postorder.
860 int OldIdx = SCCIndices[&OldSCC];
861 SCCs.insert(SCCs.begin() + OldIdx, NewSCCs.begin(), NewSCCs.end());
863 // Update the mapping from SCC* to index to use the new SCC*s, and remove the
864 // old SCC from the mapping.
865 for (int Idx = OldIdx, Size = SCCs.size(); Idx < Size; ++Idx)
866 SCCIndices[SCCs[Idx]] = Idx;
868 return make_range(SCCs.begin() + OldIdx,
869 SCCs.begin() + OldIdx + NewSCCs.size());
872 void LazyCallGraph::RefSCC::switchOutgoingEdgeToCall(Node &SourceN,
874 assert(!(*SourceN)[TargetN].isCall() && "Must start with a ref edge!");
876 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
877 assert(G->lookupRefSCC(TargetN) != this &&
878 "Target must not be in this RefSCC.");
879 #ifdef EXPENSIVE_CHECKS
880 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
881 "Target must be a descendant of the Source.");
884 // Edges between RefSCCs are the same regardless of call or ref, so we can
885 // just flip the edge here.
886 SourceN->setEdgeKind(TargetN, Edge::Call);
889 // Check that the RefSCC is still valid.
894 void LazyCallGraph::RefSCC::switchOutgoingEdgeToRef(Node &SourceN,
896 assert((*SourceN)[TargetN].isCall() && "Must start with a call edge!");
898 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
899 assert(G->lookupRefSCC(TargetN) != this &&
900 "Target must not be in this RefSCC.");
901 #ifdef EXPENSIVE_CHECKS
902 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
903 "Target must be a descendant of the Source.");
906 // Edges between RefSCCs are the same regardless of call or ref, so we can
907 // just flip the edge here.
908 SourceN->setEdgeKind(TargetN, Edge::Ref);
911 // Check that the RefSCC is still valid.
916 void LazyCallGraph::RefSCC::insertInternalRefEdge(Node &SourceN,
918 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
919 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
921 SourceN->insertEdgeInternal(TargetN, Edge::Ref);
924 // Check that the RefSCC is still valid.
929 void LazyCallGraph::RefSCC::insertOutgoingEdge(Node &SourceN, Node &TargetN,
931 // First insert it into the caller.
932 SourceN->insertEdgeInternal(TargetN, EK);
934 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
936 assert(G->lookupRefSCC(TargetN) != this &&
937 "Target must not be in this RefSCC.");
938 #ifdef EXPENSIVE_CHECKS
939 assert(G->lookupRefSCC(TargetN)->isDescendantOf(*this) &&
940 "Target must be a descendant of the Source.");
944 // Check that the RefSCC is still valid.
949 SmallVector<LazyCallGraph::RefSCC *, 1>
950 LazyCallGraph::RefSCC::insertIncomingRefEdge(Node &SourceN, Node &TargetN) {
951 assert(G->lookupRefSCC(TargetN) == this && "Target must be in this RefSCC.");
952 RefSCC &SourceC = *G->lookupRefSCC(SourceN);
953 assert(&SourceC != this && "Source must not be in this RefSCC.");
954 #ifdef EXPENSIVE_CHECKS
955 assert(SourceC.isDescendantOf(*this) &&
956 "Source must be a descendant of the Target.");
959 SmallVector<RefSCC *, 1> DeletedRefSCCs;
962 // In a debug build, verify the RefSCC is valid to start with and when this
965 auto VerifyOnExit = make_scope_exit([&]() { verify(); });
968 int SourceIdx = G->RefSCCIndices[&SourceC];
969 int TargetIdx = G->RefSCCIndices[this];
970 assert(SourceIdx < TargetIdx &&
971 "Postorder list doesn't see edge as incoming!");
973 // Compute the RefSCCs which (transitively) reach the source. We do this by
974 // working backwards from the source using the parent set in each RefSCC,
975 // skipping any RefSCCs that don't fall in the postorder range. This has the
976 // advantage of walking the sparser parent edge (in high fan-out graphs) but
977 // more importantly this removes examining all forward edges in all RefSCCs
978 // within the postorder range which aren't in fact connected. Only connected
979 // RefSCCs (and their edges) are visited here.
980 auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
981 Set.insert(&SourceC);
982 auto IsConnected = [&](RefSCC &RC) {
986 if (Set.count(G->lookupRefSCC(E.getNode())))
992 for (RefSCC *C : make_range(G->PostOrderRefSCCs.begin() + SourceIdx + 1,
993 G->PostOrderRefSCCs.begin() + TargetIdx + 1))
998 // Use a normal worklist to find which SCCs the target connects to. We still
999 // bound the search based on the range in the postorder list we care about,
1000 // but because this is forward connectivity we just "recurse" through the
1002 auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<RefSCC *> &Set) {
1004 SmallVector<RefSCC *, 4> Worklist;
1005 Worklist.push_back(this);
1007 RefSCC &RC = *Worklist.pop_back_val();
1010 for (Edge &E : *N) {
1011 RefSCC &EdgeRC = *G->lookupRefSCC(E.getNode());
1012 if (G->getRefSCCIndex(EdgeRC) <= SourceIdx)
1013 // Not in the postorder sequence between source and target.
1016 if (Set.insert(&EdgeRC).second)
1017 Worklist.push_back(&EdgeRC);
1019 } while (!Worklist.empty());
1022 // Use a generic helper to update the postorder sequence of RefSCCs and return
1023 // a range of any RefSCCs connected into a cycle by inserting this edge. This
1024 // routine will also take care of updating the indices into the postorder
1026 iterator_range<SmallVectorImpl<RefSCC *>::iterator> MergeRange =
1027 updatePostorderSequenceForEdgeInsertion(
1028 SourceC, *this, G->PostOrderRefSCCs, G->RefSCCIndices,
1029 ComputeSourceConnectedSet, ComputeTargetConnectedSet);
1031 // Build a set so we can do fast tests for whether a RefSCC will end up as
1032 // part of the merged RefSCC.
1033 SmallPtrSet<RefSCC *, 16> MergeSet(MergeRange.begin(), MergeRange.end());
1035 // This RefSCC will always be part of that set, so just insert it here.
1036 MergeSet.insert(this);
1038 // Now that we have identified all of the SCCs which need to be merged into
1039 // a connected set with the inserted edge, merge all of them into this SCC.
1040 SmallVector<SCC *, 16> MergedSCCs;
1042 for (RefSCC *RC : MergeRange) {
1043 assert(RC != this && "We're merging into the target RefSCC, so it "
1044 "shouldn't be in the range.");
1046 // Walk the inner SCCs to update their up-pointer and walk all the edges to
1047 // update any parent sets.
1048 // FIXME: We should try to find a way to avoid this (rather expensive) edge
1049 // walk by updating the parent sets in some other manner.
1050 for (SCC &InnerC : *RC) {
1051 InnerC.OuterRefSCC = this;
1052 SCCIndices[&InnerC] = SCCIndex++;
1053 for (Node &N : InnerC)
1054 G->SCCMap[&N] = &InnerC;
1057 // Now merge in the SCCs. We can actually move here so try to reuse storage
1058 // the first time through.
1059 if (MergedSCCs.empty())
1060 MergedSCCs = std::move(RC->SCCs);
1062 MergedSCCs.append(RC->SCCs.begin(), RC->SCCs.end());
1064 DeletedRefSCCs.push_back(RC);
1067 // Append our original SCCs to the merged list and move it into place.
1068 for (SCC &InnerC : *this)
1069 SCCIndices[&InnerC] = SCCIndex++;
1070 MergedSCCs.append(SCCs.begin(), SCCs.end());
1071 SCCs = std::move(MergedSCCs);
1073 // Remove the merged away RefSCCs from the post order sequence.
1074 for (RefSCC *RC : MergeRange)
1075 G->RefSCCIndices.erase(RC);
1076 int IndexOffset = MergeRange.end() - MergeRange.begin();
1078 G->PostOrderRefSCCs.erase(MergeRange.begin(), MergeRange.end());
1079 for (RefSCC *RC : make_range(EraseEnd, G->PostOrderRefSCCs.end()))
1080 G->RefSCCIndices[RC] -= IndexOffset;
1082 // At this point we have a merged RefSCC with a post-order SCCs list, just
1083 // connect the nodes to form the new edge.
1084 SourceN->insertEdgeInternal(TargetN, Edge::Ref);
1086 // We return the list of SCCs which were merged so that callers can
1087 // invalidate any data they have associated with those SCCs. Note that these
1088 // SCCs are no longer in an interesting state (they are totally empty) but
1089 // the pointers will remain stable for the life of the graph itself.
1090 return DeletedRefSCCs;
1093 void LazyCallGraph::RefSCC::removeOutgoingEdge(Node &SourceN, Node &TargetN) {
1094 assert(G->lookupRefSCC(SourceN) == this &&
1095 "The source must be a member of this RefSCC.");
1096 assert(G->lookupRefSCC(TargetN) != this &&
1097 "The target must not be a member of this RefSCC");
1100 // In a debug build, verify the RefSCC is valid to start with and when this
1101 // routine finishes.
1103 auto VerifyOnExit = make_scope_exit([&]() { verify(); });
1106 // First remove it from the node.
1107 bool Removed = SourceN->removeEdgeInternal(TargetN);
1109 assert(Removed && "Target not in the edge set for this caller?");
1112 SmallVector<LazyCallGraph::RefSCC *, 1>
1113 LazyCallGraph::RefSCC::removeInternalRefEdge(Node &SourceN,
1114 ArrayRef<Node *> TargetNs) {
1115 // We return a list of the resulting *new* RefSCCs in post-order.
1116 SmallVector<RefSCC *, 1> Result;
1119 // In a debug build, verify the RefSCC is valid to start with and that either
1120 // we return an empty list of result RefSCCs and this RefSCC remains valid,
1121 // or we return new RefSCCs and this RefSCC is dead.
1123 auto VerifyOnExit = make_scope_exit([&]() {
1124 // If we didn't replace our RefSCC with new ones, check that this one
1131 // First remove the actual edges.
1132 for (Node *TargetN : TargetNs) {
1133 assert(!(*SourceN)[*TargetN].isCall() &&
1134 "Cannot remove a call edge, it must first be made a ref edge");
1136 bool Removed = SourceN->removeEdgeInternal(*TargetN);
1138 assert(Removed && "Target not in the edge set for this caller?");
1141 // Direct self references don't impact the ref graph at all.
1142 if (llvm::all_of(TargetNs,
1143 [&](Node *TargetN) { return &SourceN == TargetN; }))
1146 // If all targets are in the same SCC as the source, because no call edges
1147 // were removed there is no RefSCC structure change.
1148 SCC &SourceC = *G->lookupSCC(SourceN);
1149 if (llvm::all_of(TargetNs, [&](Node *TargetN) {
1150 return G->lookupSCC(*TargetN) == &SourceC;
1154 // We build somewhat synthetic new RefSCCs by providing a postorder mapping
1155 // for each inner SCC. We store these inside the low-link field of the nodes
1156 // rather than associated with SCCs because this saves a round-trip through
1157 // the node->SCC map and in the common case, SCCs are small. We will verify
1158 // that we always give the same number to every node in the SCC such that
1159 // these are equivalent.
1160 int PostOrderNumber = 0;
1162 // Reset all the other nodes to prepare for a DFS over them, and add them to
1164 SmallVector<Node *, 8> Worklist;
1165 for (SCC *C : SCCs) {
1167 N.DFSNumber = N.LowLink = 0;
1169 Worklist.append(C->Nodes.begin(), C->Nodes.end());
1172 // Track the number of nodes in this RefSCC so that we can quickly recognize
1173 // an important special case of the edge removal not breaking the cycle of
1175 const int NumRefSCCNodes = Worklist.size();
1177 SmallVector<std::pair<Node *, EdgeSequence::iterator>, 4> DFSStack;
1178 SmallVector<Node *, 4> PendingRefSCCStack;
1180 assert(DFSStack.empty() &&
1181 "Cannot begin a new root with a non-empty DFS stack!");
1182 assert(PendingRefSCCStack.empty() &&
1183 "Cannot begin a new root with pending nodes for an SCC!");
1185 Node *RootN = Worklist.pop_back_val();
1186 // Skip any nodes we've already reached in the DFS.
1187 if (RootN->DFSNumber != 0) {
1188 assert(RootN->DFSNumber == -1 &&
1189 "Shouldn't have any mid-DFS root nodes!");
1193 RootN->DFSNumber = RootN->LowLink = 1;
1194 int NextDFSNumber = 2;
1196 DFSStack.push_back({RootN, (*RootN)->begin()});
1199 EdgeSequence::iterator I;
1200 std::tie(N, I) = DFSStack.pop_back_val();
1201 auto E = (*N)->end();
1203 assert(N->DFSNumber != 0 && "We should always assign a DFS number "
1204 "before processing a node.");
1207 Node &ChildN = I->getNode();
1208 if (ChildN.DFSNumber == 0) {
1209 // Mark that we should start at this child when next this node is the
1210 // top of the stack. We don't start at the next child to ensure this
1211 // child's lowlink is reflected.
1212 DFSStack.push_back({N, I});
1214 // Continue, resetting to the child node.
1215 ChildN.LowLink = ChildN.DFSNumber = NextDFSNumber++;
1217 I = ChildN->begin();
1221 if (ChildN.DFSNumber == -1) {
1222 // If this child isn't currently in this RefSCC, no need to process
1228 // Track the lowest link of the children, if any are still in the stack.
1229 // Any child not on the stack will have a LowLink of -1.
1230 assert(ChildN.LowLink != 0 &&
1231 "Low-link must not be zero with a non-zero DFS number.");
1232 if (ChildN.LowLink >= 0 && ChildN.LowLink < N->LowLink)
1233 N->LowLink = ChildN.LowLink;
1237 // We've finished processing N and its descendents, put it on our pending
1238 // stack to eventually get merged into a RefSCC.
1239 PendingRefSCCStack.push_back(N);
1241 // If this node is linked to some lower entry, continue walking up the
1243 if (N->LowLink != N->DFSNumber) {
1244 assert(!DFSStack.empty() &&
1245 "We never found a viable root for a RefSCC to pop off!");
1249 // Otherwise, form a new RefSCC from the top of the pending node stack.
1250 int RefSCCNumber = PostOrderNumber++;
1251 int RootDFSNumber = N->DFSNumber;
1253 // Find the range of the node stack by walking down until we pass the
1254 // root DFS number. Update the DFS numbers and low link numbers in the
1255 // process to avoid re-walking this list where possible.
1256 auto StackRI = find_if(reverse(PendingRefSCCStack), [&](Node *N) {
1257 if (N->DFSNumber < RootDFSNumber)
1258 // We've found the bottom.
1261 // Update this node and keep scanning.
1263 // Save the post-order number in the lowlink field so that we can use
1264 // it to map SCCs into new RefSCCs after we finish the DFS.
1265 N->LowLink = RefSCCNumber;
1268 auto RefSCCNodes = make_range(StackRI.base(), PendingRefSCCStack.end());
1270 // If we find a cycle containing all nodes originally in this RefSCC then
1271 // the removal hasn't changed the structure at all. This is an important
1272 // special case and we can directly exit the entire routine more
1273 // efficiently as soon as we discover it.
1274 if (std::distance(RefSCCNodes.begin(), RefSCCNodes.end()) ==
1276 // Clear out the low link field as we won't need it.
1277 for (Node *N : RefSCCNodes)
1279 // Return the empty result immediately.
1283 // We've already marked the nodes internally with the RefSCC number so
1284 // just clear them off the stack and continue.
1285 PendingRefSCCStack.erase(RefSCCNodes.begin(), PendingRefSCCStack.end());
1286 } while (!DFSStack.empty());
1288 assert(DFSStack.empty() && "Didn't flush the entire DFS stack!");
1289 assert(PendingRefSCCStack.empty() && "Didn't flush all pending nodes!");
1290 } while (!Worklist.empty());
1292 assert(PostOrderNumber > 1 &&
1293 "Should never finish the DFS when the existing RefSCC remains valid!");
1295 // Otherwise we create a collection of new RefSCC nodes and build
1296 // a radix-sort style map from postorder number to these new RefSCCs. We then
1297 // append SCCs to each of these RefSCCs in the order they occured in the
1298 // original SCCs container.
1299 for (int i = 0; i < PostOrderNumber; ++i)
1300 Result.push_back(G->createRefSCC(*G));
1302 // Insert the resulting postorder sequence into the global graph postorder
1303 // sequence before the current RefSCC in that sequence, and then remove the
1306 // FIXME: It'd be nice to change the APIs so that we returned an iterator
1307 // range over the global postorder sequence and generally use that sequence
1308 // rather than building a separate result vector here.
1309 int Idx = G->getRefSCCIndex(*this);
1310 G->PostOrderRefSCCs.erase(G->PostOrderRefSCCs.begin() + Idx);
1311 G->PostOrderRefSCCs.insert(G->PostOrderRefSCCs.begin() + Idx, Result.begin(),
1313 for (int i : seq<int>(Idx, G->PostOrderRefSCCs.size()))
1314 G->RefSCCIndices[G->PostOrderRefSCCs[i]] = i;
1316 for (SCC *C : SCCs) {
1317 // We store the SCC number in the node's low-link field above.
1318 int SCCNumber = C->begin()->LowLink;
1319 // Clear out all of the SCC's node's low-link fields now that we're done
1320 // using them as side-storage.
1321 for (Node &N : *C) {
1322 assert(N.LowLink == SCCNumber &&
1323 "Cannot have different numbers for nodes in the same SCC!");
1327 RefSCC &RC = *Result[SCCNumber];
1328 int SCCIndex = RC.SCCs.size();
1329 RC.SCCs.push_back(C);
1330 RC.SCCIndices[C] = SCCIndex;
1331 C->OuterRefSCC = &RC;
1334 // Now that we've moved things into the new RefSCCs, clear out our current
1341 // Verify the new RefSCCs we've built.
1342 for (RefSCC *RC : Result)
1346 // Return the new list of SCCs.
1350 void LazyCallGraph::RefSCC::handleTrivialEdgeInsertion(Node &SourceN,
1352 // The only trivial case that requires any graph updates is when we add new
1353 // ref edge and may connect different RefSCCs along that path. This is only
1354 // because of the parents set. Every other part of the graph remains constant
1355 // after this edge insertion.
1356 assert(G->lookupRefSCC(SourceN) == this && "Source must be in this RefSCC.");
1357 RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
1358 if (&TargetRC == this)
1361 #ifdef EXPENSIVE_CHECKS
1362 assert(TargetRC.isDescendantOf(*this) &&
1363 "Target must be a descendant of the Source.");
1367 void LazyCallGraph::RefSCC::insertTrivialCallEdge(Node &SourceN,
1370 // Check that the RefSCC is still valid when we finish.
1371 auto ExitVerifier = make_scope_exit([this] { verify(); });
1373 #ifdef EXPENSIVE_CHECKS
1374 // Check that we aren't breaking some invariants of the SCC graph. Note that
1375 // this is quadratic in the number of edges in the call graph!
1376 SCC &SourceC = *G->lookupSCC(SourceN);
1377 SCC &TargetC = *G->lookupSCC(TargetN);
1378 if (&SourceC != &TargetC)
1379 assert(SourceC.isAncestorOf(TargetC) &&
1380 "Call edge is not trivial in the SCC graph!");
1381 #endif // EXPENSIVE_CHECKS
1384 // First insert it into the source or find the existing edge.
1386 SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()});
1387 if (!InsertResult.second) {
1388 // Already an edge, just update it.
1389 Edge &E = SourceN->Edges[InsertResult.first->second];
1391 return; // Nothing to do!
1392 E.setKind(Edge::Call);
1394 // Create the new edge.
1395 SourceN->Edges.emplace_back(TargetN, Edge::Call);
1398 // Now that we have the edge, handle the graph fallout.
1399 handleTrivialEdgeInsertion(SourceN, TargetN);
1402 void LazyCallGraph::RefSCC::insertTrivialRefEdge(Node &SourceN, Node &TargetN) {
1404 // Check that the RefSCC is still valid when we finish.
1405 auto ExitVerifier = make_scope_exit([this] { verify(); });
1407 #ifdef EXPENSIVE_CHECKS
1408 // Check that we aren't breaking some invariants of the RefSCC graph.
1409 RefSCC &SourceRC = *G->lookupRefSCC(SourceN);
1410 RefSCC &TargetRC = *G->lookupRefSCC(TargetN);
1411 if (&SourceRC != &TargetRC)
1412 assert(SourceRC.isAncestorOf(TargetRC) &&
1413 "Ref edge is not trivial in the RefSCC graph!");
1414 #endif // EXPENSIVE_CHECKS
1417 // First insert it into the source or find the existing edge.
1419 SourceN->EdgeIndexMap.insert({&TargetN, SourceN->Edges.size()});
1420 if (!InsertResult.second)
1421 // Already an edge, we're done.
1424 // Create the new edge.
1425 SourceN->Edges.emplace_back(TargetN, Edge::Ref);
1427 // Now that we have the edge, handle the graph fallout.
1428 handleTrivialEdgeInsertion(SourceN, TargetN);
1431 void LazyCallGraph::RefSCC::replaceNodeFunction(Node &N, Function &NewF) {
1432 Function &OldF = N.getFunction();
1435 // Check that the RefSCC is still valid when we finish.
1436 auto ExitVerifier = make_scope_exit([this] { verify(); });
1438 assert(G->lookupRefSCC(N) == this &&
1439 "Cannot replace the function of a node outside this RefSCC.");
1441 assert(G->NodeMap.find(&NewF) == G->NodeMap.end() &&
1442 "Must not have already walked the new function!'");
1444 // It is important that this replacement not introduce graph changes so we
1445 // insist that the caller has already removed every use of the original
1446 // function and that all uses of the new function correspond to existing
1447 // edges in the graph. The common and expected way to use this is when
1448 // replacing the function itself in the IR without changing the call graph
1449 // shape and just updating the analysis based on that.
1450 assert(&OldF != &NewF && "Cannot replace a function with itself!");
1451 assert(OldF.use_empty() &&
1452 "Must have moved all uses from the old function to the new!");
1455 N.replaceFunction(NewF);
1457 // Update various call graph maps.
1458 G->NodeMap.erase(&OldF);
1459 G->NodeMap[&NewF] = &N;
1462 void LazyCallGraph::insertEdge(Node &SourceN, Node &TargetN, Edge::Kind EK) {
1463 assert(SCCMap.empty() &&
1464 "This method cannot be called after SCCs have been formed!");
1466 return SourceN->insertEdgeInternal(TargetN, EK);
1469 void LazyCallGraph::removeEdge(Node &SourceN, Node &TargetN) {
1470 assert(SCCMap.empty() &&
1471 "This method cannot be called after SCCs have been formed!");
1473 bool Removed = SourceN->removeEdgeInternal(TargetN);
1475 assert(Removed && "Target not in the edge set for this caller?");
1478 void LazyCallGraph::removeDeadFunction(Function &F) {
1479 // FIXME: This is unnecessarily restrictive. We should be able to remove
1480 // functions which recursively call themselves.
1481 assert(F.use_empty() &&
1482 "This routine should only be called on trivially dead functions!");
1484 // We shouldn't remove library functions as they are never really dead while
1485 // the call graph is in use -- every function definition refers to them.
1486 assert(!isLibFunction(F) &&
1487 "Must not remove lib functions from the call graph!");
1489 auto NI = NodeMap.find(&F);
1490 if (NI == NodeMap.end())
1491 // Not in the graph at all!
1494 Node &N = *NI->second;
1497 // Remove this from the entry edges if present.
1498 EntryEdges.removeEdgeInternal(N);
1500 if (SCCMap.empty()) {
1501 // No SCCs have been formed, so removing this is fine and there is nothing
1502 // else necessary at this point but clearing out the node.
1507 // Cannot remove a function which has yet to be visited in the DFS walk, so
1508 // if we have a node at all then we must have an SCC and RefSCC.
1509 auto CI = SCCMap.find(&N);
1510 assert(CI != SCCMap.end() &&
1511 "Tried to remove a node without an SCC after DFS walk started!");
1512 SCC &C = *CI->second;
1514 RefSCC &RC = C.getOuterRefSCC();
1516 // This node must be the only member of its SCC as it has no callers, and
1517 // that SCC must be the only member of a RefSCC as it has no references.
1518 // Validate these properties first.
1519 assert(C.size() == 1 && "Dead functions must be in a singular SCC");
1520 assert(RC.size() == 1 && "Dead functions must be in a singular RefSCC");
1522 auto RCIndexI = RefSCCIndices.find(&RC);
1523 int RCIndex = RCIndexI->second;
1524 PostOrderRefSCCs.erase(PostOrderRefSCCs.begin() + RCIndex);
1525 RefSCCIndices.erase(RCIndexI);
1526 for (int i = RCIndex, Size = PostOrderRefSCCs.size(); i < Size; ++i)
1527 RefSCCIndices[PostOrderRefSCCs[i]] = i;
1529 // Finally clear out all the data structures from the node down through the
1538 // Nothing to delete as all the objects are allocated in stable bump pointer
1542 LazyCallGraph::Node &LazyCallGraph::insertInto(Function &F, Node *&MappedN) {
1543 return *new (MappedN = BPA.Allocate()) Node(*this, F);
1546 void LazyCallGraph::updateGraphPtrs() {
1547 // Walk the node map to update their graph pointers. While this iterates in
1548 // an unstable order, the order has no effect so it remains correct.
1549 for (auto &FunctionNodePair : NodeMap)
1550 FunctionNodePair.second->G = this;
1552 for (auto *RC : PostOrderRefSCCs)
1556 template <typename RootsT, typename GetBeginT, typename GetEndT,
1557 typename GetNodeT, typename FormSCCCallbackT>
1558 void LazyCallGraph::buildGenericSCCs(RootsT &&Roots, GetBeginT &&GetBegin,
1559 GetEndT &&GetEnd, GetNodeT &&GetNode,
1560 FormSCCCallbackT &&FormSCC) {
1561 using EdgeItT = decltype(GetBegin(std::declval<Node &>()));
1563 SmallVector<std::pair<Node *, EdgeItT>, 16> DFSStack;
1564 SmallVector<Node *, 16> PendingSCCStack;
1566 // Scan down the stack and DFS across the call edges.
1567 for (Node *RootN : Roots) {
1568 assert(DFSStack.empty() &&
1569 "Cannot begin a new root with a non-empty DFS stack!");
1570 assert(PendingSCCStack.empty() &&
1571 "Cannot begin a new root with pending nodes for an SCC!");
1573 // Skip any nodes we've already reached in the DFS.
1574 if (RootN->DFSNumber != 0) {
1575 assert(RootN->DFSNumber == -1 &&
1576 "Shouldn't have any mid-DFS root nodes!");
1580 RootN->DFSNumber = RootN->LowLink = 1;
1581 int NextDFSNumber = 2;
1583 DFSStack.push_back({RootN, GetBegin(*RootN)});
1587 std::tie(N, I) = DFSStack.pop_back_val();
1588 auto E = GetEnd(*N);
1590 Node &ChildN = GetNode(I);
1591 if (ChildN.DFSNumber == 0) {
1592 // We haven't yet visited this child, so descend, pushing the current
1593 // node onto the stack.
1594 DFSStack.push_back({N, I});
1596 ChildN.DFSNumber = ChildN.LowLink = NextDFSNumber++;
1603 // If the child has already been added to some child component, it
1604 // couldn't impact the low-link of this parent because it isn't
1605 // connected, and thus its low-link isn't relevant so skip it.
1606 if (ChildN.DFSNumber == -1) {
1611 // Track the lowest linked child as the lowest link for this node.
1612 assert(ChildN.LowLink > 0 && "Must have a positive low-link number!");
1613 if (ChildN.LowLink < N->LowLink)
1614 N->LowLink = ChildN.LowLink;
1616 // Move to the next edge.
1620 // We've finished processing N and its descendents, put it on our pending
1621 // SCC stack to eventually get merged into an SCC of nodes.
1622 PendingSCCStack.push_back(N);
1624 // If this node is linked to some lower entry, continue walking up the
1626 if (N->LowLink != N->DFSNumber)
1629 // Otherwise, we've completed an SCC. Append it to our post order list of
1631 int RootDFSNumber = N->DFSNumber;
1632 // Find the range of the node stack by walking down until we pass the
1634 auto SCCNodes = make_range(
1635 PendingSCCStack.rbegin(),
1636 find_if(reverse(PendingSCCStack), [RootDFSNumber](const Node *N) {
1637 return N->DFSNumber < RootDFSNumber;
1639 // Form a new SCC out of these nodes and then clear them off our pending
1642 PendingSCCStack.erase(SCCNodes.end().base(), PendingSCCStack.end());
1643 } while (!DFSStack.empty());
1647 /// Build the internal SCCs for a RefSCC from a sequence of nodes.
1649 /// Appends the SCCs to the provided vector and updates the map with their
1650 /// indices. Both the vector and map must be empty when passed into this
1652 void LazyCallGraph::buildSCCs(RefSCC &RC, node_stack_range Nodes) {
1653 assert(RC.SCCs.empty() && "Already built SCCs!");
1654 assert(RC.SCCIndices.empty() && "Already mapped SCC indices!");
1656 for (Node *N : Nodes) {
1657 assert(N->LowLink >= (*Nodes.begin())->LowLink &&
1658 "We cannot have a low link in an SCC lower than its root on the "
1661 // This node will go into the next RefSCC, clear out its DFS and low link
1663 N->DFSNumber = N->LowLink = 0;
1666 // Each RefSCC contains a DAG of the call SCCs. To build these, we do
1667 // a direct walk of the call edges using Tarjan's algorithm. We reuse the
1668 // internal storage as we won't need it for the outer graph's DFS any longer.
1670 Nodes, [](Node &N) { return N->call_begin(); },
1671 [](Node &N) { return N->call_end(); },
1672 [](EdgeSequence::call_iterator I) -> Node & { return I->getNode(); },
1673 [this, &RC](node_stack_range Nodes) {
1674 RC.SCCs.push_back(createSCC(RC, Nodes));
1675 for (Node &N : *RC.SCCs.back()) {
1676 N.DFSNumber = N.LowLink = -1;
1677 SCCMap[&N] = RC.SCCs.back();
1681 // Wire up the SCC indices.
1682 for (int i = 0, Size = RC.SCCs.size(); i < Size; ++i)
1683 RC.SCCIndices[RC.SCCs[i]] = i;
1686 void LazyCallGraph::buildRefSCCs() {
1687 if (EntryEdges.empty() || !PostOrderRefSCCs.empty())
1688 // RefSCCs are either non-existent or already built!
1691 assert(RefSCCIndices.empty() && "Already mapped RefSCC indices!");
1693 SmallVector<Node *, 16> Roots;
1694 for (Edge &E : *this)
1695 Roots.push_back(&E.getNode());
1697 // The roots will be popped of a stack, so use reverse to get a less
1698 // surprising order. This doesn't change any of the semantics anywhere.
1699 std::reverse(Roots.begin(), Roots.end());
1704 // We need to populate each node as we begin to walk its edges.
1708 [](Node &N) { return N->end(); },
1709 [](EdgeSequence::iterator I) -> Node & { return I->getNode(); },
1710 [this](node_stack_range Nodes) {
1711 RefSCC *NewRC = createRefSCC(*this);
1712 buildSCCs(*NewRC, Nodes);
1714 // Push the new node into the postorder list and remember its position
1715 // in the index map.
1717 RefSCCIndices.insert({NewRC, PostOrderRefSCCs.size()}).second;
1719 assert(Inserted && "Cannot already have this RefSCC in the index map!");
1720 PostOrderRefSCCs.push_back(NewRC);
1727 AnalysisKey LazyCallGraphAnalysis::Key;
1729 LazyCallGraphPrinterPass::LazyCallGraphPrinterPass(raw_ostream &OS) : OS(OS) {}
1731 static void printNode(raw_ostream &OS, LazyCallGraph::Node &N) {
1732 OS << " Edges in function: " << N.getFunction().getName() << "\n";
1733 for (LazyCallGraph::Edge &E : N.populate())
1734 OS << " " << (E.isCall() ? "call" : "ref ") << " -> "
1735 << E.getFunction().getName() << "\n";
1740 static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &C) {
1741 ptrdiff_t Size = std::distance(C.begin(), C.end());
1742 OS << " SCC with " << Size << " functions:\n";
1744 for (LazyCallGraph::Node &N : C)
1745 OS << " " << N.getFunction().getName() << "\n";
1748 static void printRefSCC(raw_ostream &OS, LazyCallGraph::RefSCC &C) {
1749 ptrdiff_t Size = std::distance(C.begin(), C.end());
1750 OS << " RefSCC with " << Size << " call SCCs:\n";
1752 for (LazyCallGraph::SCC &InnerC : C)
1753 printSCC(OS, InnerC);
1758 PreservedAnalyses LazyCallGraphPrinterPass::run(Module &M,
1759 ModuleAnalysisManager &AM) {
1760 LazyCallGraph &G = AM.getResult<LazyCallGraphAnalysis>(M);
1762 OS << "Printing the call graph for module: " << M.getModuleIdentifier()
1765 for (Function &F : M)
1766 printNode(OS, G.get(F));
1769 for (LazyCallGraph::RefSCC &C : G.postorder_ref_sccs())
1772 return PreservedAnalyses::all();
1775 LazyCallGraphDOTPrinterPass::LazyCallGraphDOTPrinterPass(raw_ostream &OS)
1778 static void printNodeDOT(raw_ostream &OS, LazyCallGraph::Node &N) {
1779 std::string Name = "\"" + DOT::EscapeString(N.getFunction().getName()) + "\"";
1781 for (LazyCallGraph::Edge &E : N.populate()) {
1782 OS << " " << Name << " -> \""
1783 << DOT::EscapeString(E.getFunction().getName()) << "\"";
1784 if (!E.isCall()) // It is a ref edge.
1785 OS << " [style=dashed,label=\"ref\"]";
1792 PreservedAnalyses LazyCallGraphDOTPrinterPass::run(Module &M,
1793 ModuleAnalysisManager &AM) {
1794 LazyCallGraph &G = AM.getResult<LazyCallGraphAnalysis>(M);
1796 OS << "digraph \"" << DOT::EscapeString(M.getModuleIdentifier()) << "\" {\n";
1798 for (Function &F : M)
1799 printNodeDOT(OS, G.get(F));
1803 return PreservedAnalyses::all();