242 LLVM_DUMP_METHOD void LazyCallGraph::SCC::dump() const {  in dump()
248 void LazyCallGraph::SCC::verify() {  in verify()
250   assert(!Nodes.empty() && "Can't have an empty SCC!");  in verify()
255            "Node does not map to this SCC!");  in verify()
257            "Must set DFS numbers to -1 when adding a node to an SCC!");  in verify()
259            "Must set low link to -1 when adding a node to an SCC!");  in verify()
264     // Verify that all nodes in this SCC can reach all other nodes.  in verify()
277              "Cannot reach all nodes within SCC");  in verify()
284 bool LazyCallGraph::SCC::isParentOf(const SCC &C) const {  in isParentOf()
297 bool LazyCallGraph::SCC::isAncestorOf(const SCC &TargetC) const {  in isAncestorOf()
303   // Start with this SCC.  in isAncestorOf()
304   SmallPtrSet<const SCC *, 16> Visited = {this};  in isAncestorOf()
305   SmallVector<const SCC *, 16> Worklist = {this};  in isAncestorOf()
309     const SCC &C = *Worklist.pop_back_val();  in isAncestorOf()
312         SCC *CalleeC = G.lookupSCC(E.getNode());  in isAncestorOf()
316         // If the callee's SCC is the TargetC, we're done.  in isAncestorOf()
320         // If this is the first time we've reached this SCC, put it on the  in isAncestorOf()
342   assert(!SCCs.empty() && "Can't have an empty SCC!");  in verify()
345   SmallPtrSet<SCC *, 4> SCCSet;  in verify()
346   for (SCC *C : SCCs) {  in verify()
347     assert(C && "Can't have a null SCC!");  in verify()
350            "SCC doesn't think it is inside this RefSCC!");  in verify()
352     assert(Inserted && "Found a duplicate SCC!");  in verify()
355            "Found an SCC that doesn't have an index!");  in verify()
360     assert(C && "Can't have a null SCC in the indices!");  in verify()
361     assert(SCCSet.count(C) && "Found an index for an SCC not in the RefSCC!");  in verify()
362     assert(SCCs[I] == C && "Index doesn't point to SCC!");  in verify()
367     SCC &SourceSCC = *SCCs[I];  in verify()
372         SCC &TargetSCC = *G->lookupSCC(E.getNode());  in verify()
384   for (SCC *C : SCCs) {  in verify()
413   for (SCC &C : *this)  in isParentOf()
435     for (SCC &C : DescendantRC)  in isAncestorOf()
455 /// all edges in the SCC DAG point to prior SCCs in the sequence.
462 /// When inserting an edge from an earlier SCC to a later SCC in some postorder
467 /// 1) Starting from the source SCC, construct a set of SCCs which reach the
468 ///    source SCC consisting of just the source SCC. Then scan toward the
469 ///    target SCC in postorder and for each SCC, if it has an edge to an SCC
470 ///    in the set, add it to the set. Otherwise, the source SCC is not
472 ///    the source SCC, shifting the source SCC and all SCCs in the set one
473 ///    position toward the target SCC. Stop scanning after processing the
474 ///    target SCC.
475 /// 2) If the source SCC is now past the target SCC in the postorder sequence,
477 /// 3) Otherwise, starting from the target SCC, walk all edges which reach an
478 ///    SCC between the source and the target, and add them to the set of
482 ///    need to process the source SCC, it is already known to connect.
484 ///    SCC and the target SCC in the postorder sequence are connected,
485 ///    including the target SCC and the source SCC. Inserting the edge from
486 ///    the source SCC to the target SCC will form a cycle out of precisely
488 ///    a single SCC.
491 /// - Only mutates the SCCs when adding the edge actually changes the SCC
504 /// The sequence and the map must operate on pointers to the SCC type.
508 /// the source SCC via some (transitive) set of edges. The second computes the
509 /// subset of the same range which the target SCC connects to via some
545            "Last SCC to move should have bene the target.");  in updatePostorderSequenceForEdgeInsertion()
547     // Return an empty range at the target SCC indicating there is nothing to  in updatePostorderSequenceForEdgeInsertion()
556          "Bad updated index computation for the source SCC!");  in updatePostorderSequenceForEdgeInsertion()
586     function_ref<void(ArrayRef<SCC *> MergeSCCs)> MergeCB) {  in switchInternalEdgeToCall()
588   SmallVector<SCC *, 1> DeletedSCCs;  in switchInternalEdgeToCall()
595   SCC &SourceSCC = *G->lookupSCC(SourceN);  in switchInternalEdgeToCall()
596   SCC &TargetSCC = *G->lookupSCC(TargetN);  in switchInternalEdgeToCall()
598   // If the two nodes are already part of the same SCC, we're also done as  in switchInternalEdgeToCall()
606   // insertion of an edge changes the SCC structure in any way.  in switchInternalEdgeToCall()
619   auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {  in switchInternalEdgeToCall()
626     auto IsConnected = [&](SCC &C) {  in switchInternalEdgeToCall()
635     for (SCC *C :  in switchInternalEdgeToCall()
645   auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {  in switchInternalEdgeToCall()
652     SmallVector<SCC *, 4> Worklist;  in switchInternalEdgeToCall()
655       SCC &C = *Worklist.pop_back_val();  in switchInternalEdgeToCall()
660           SCC &EdgeC = *G->lookupSCC(E.getNode());  in switchInternalEdgeToCall()
689     // Now that the SCC structure is finalized, flip the kind to call.  in switchInternalEdgeToCall()
701   // SCC.  in switchInternalEdgeToCall()
704   // reachable from the target, meaning any SCC-wide properties deduced about it  in switchInternalEdgeToCall()
706   for (SCC *C : MergeRange) {  in switchInternalEdgeToCall()
721   for (SCC *C : make_range(EraseEnd, SCCs.end()))  in switchInternalEdgeToCall()
724   // Now that the SCC structure is finalized, flip the kind to call.  in switchInternalEdgeToCall()
761   SCC &TargetSCC = *G->lookupSCC(TargetN);  in switchInternalEdgeToRef()
763                                                 "the same SCC to require the "  in switchInternalEdgeToRef()
769   // Otherwise we are removing a call edge from a single SCC. This may break  in switchInternalEdgeToRef()
771   // DFS over the nodes within the SCC to form any sub-cycles that remain as  in switchInternalEdgeToRef()
775   // reach all other nodes in the original SCC by definition. This means that  in switchInternalEdgeToRef()
776   // we want the old SCC to be replaced with an SCC containing that node as it  in switchInternalEdgeToRef()
777   // will be the root of whatever SCC DAG results from the DFS. Assumptions  in switchInternalEdgeToRef()
778   // about an SCC such as the set of functions called will continue to hold,  in switchInternalEdgeToRef()
781   SCC &OldSCC = TargetSCC;  in switchInternalEdgeToRef()
784   SmallVector<SCC *, 4> NewSCCs;  in switchInternalEdgeToRef()
794   // Force the target node to be in the old SCC. This also enables us to take  in switchInternalEdgeToRef()
801   // nodes are reachable from the target due to previously forming an SCC).  in switchInternalEdgeToRef()
811            "Cannot begin a new root with pending nodes for an SCC!");  in switchInternalEdgeToRef()
835                  "Found a node with 0 DFS number but already in an SCC!");  in switchInternalEdgeToRef()
846             // If the child is part of the old SCC, we know that it can reach  in switchInternalEdgeToRef()
849             // up the old SCC for why we do this.  in switchInternalEdgeToRef()
884       // SCC stack to eventually get merged into an SCC of nodes.  in switchInternalEdgeToRef()
892       // Otherwise, we've completed an SCC. Append it to our post order list of  in switchInternalEdgeToRef()
903       // Form a new SCC out of these nodes and then clear them off our pending  in switchInternalEdgeToRef()
914   // Insert the remaining SCCs before the old one. The old SCC can reach all  in switchInternalEdgeToRef()
916   // of the old SCC. This means that we will have edges into all the new SCCs,  in switchInternalEdgeToRef()
921   // Update the mapping from SCC* to index to use the new SCC*s, and remove the  in switchInternalEdgeToRef()
922   // old SCC from the mapping.  in switchInternalEdgeToRef()
1035       for (SCC &C : RC)  in insertIncomingRefEdge()
1060       for (SCC &C : RC)  in insertIncomingRefEdge()
1091   // a connected set with the inserted edge, merge all of them into this SCC.  in insertIncomingRefEdge()
1092   SmallVector<SCC *, 16> MergedSCCs;  in insertIncomingRefEdge()
1102     for (SCC &InnerC : *RC) {  in insertIncomingRefEdge()
1120   for (SCC &InnerC : *this)  in insertIncomingRefEdge()
1192   // If all targets are in the same SCC as the source, because no call edges  in removeInternalRefEdges()
1201   // for each inner SCC. We store these inside the low-link field of the nodes  in removeInternalRefEdges()
1203   // the node->SCC map and in the common case, SCCs are small. We will verify  in removeInternalRefEdges()
1204   // that we always give the same number to every node in the SCC such that  in removeInternalRefEdges()
1211   for (SCC *C : SCCs) {  in removeInternalRefEdges()
1229            "Cannot begin a new root with pending nodes for an SCC!");  in removeInternalRefEdges()
1359   for (SCC *C : SCCs) {  in removeInternalRefEdges()
1360     // We store the SCC number in the node's low-link field above.  in removeInternalRefEdges()
1362     // Clear out all the SCC's node's low-link fields now that we're done  in removeInternalRefEdges()
1366              "Cannot have different numbers for nodes in the same SCC!");  in removeInternalRefEdges()
1398   // Check that we aren't breaking some invariants of the SCC graph. Note that  in insertTrivialCallEdge()
1400   SCC &SourceC = *G->lookupSCC(SourceN);  in insertTrivialCallEdge()
1401   SCC &TargetC = *G->lookupSCC(TargetN);  in insertTrivialCallEdge()
1404            "Call edge is not trivial in the SCC graph!");  in insertTrivialCallEdge()
1625   SCC *OriginalC = lookupSCC(OriginalN);  in addSplitFunction()
1639   SCC *NewC = nullptr;  in addSplitFunction()
1644       // from the new function to any function in the original function's SCC,  in addSplitFunction()
1645       // it is in the same SCC (and RefSCC) as the original function.  in addSplitFunction()
1658         // function but a new SCC.  in addSplitFunction()
1662         // The new function's SCC is not the same as the original function's  in addSplitFunction()
1663         // SCC, since that case was handled earlier. If the edge from the  in addSplitFunction()
1665         // to insert the newly created function's SCC before the original  in addSplitFunction()
1666         // function's SCC. Otherwise, either the new SCC comes after the  in addSplitFunction()
1667         // original function's SCC, or it doesn't matter, and in both cases we  in addSplitFunction()
1753     // Each new function is in its own new SCC. The original function can only  in addSplitRefRecursiveFunctions()
1757     SCC *NewC = createSCC(*NewRC, SmallVector<Node *, 1>({&NewN}));  in addSplitRefRecursiveFunctions()
1760     // SCC list.  in addSplitRefRecursiveFunctions()
1820            "Cannot begin a new root with pending nodes for an SCC!");  in buildGenericSCCs()
1868       // SCC stack to eventually get merged into an SCC of nodes.  in buildGenericSCCs()
1876       // Otherwise, we've completed an SCC. Append it to our post order list of  in buildGenericSCCs()
1886       // Form a new SCC out of these nodes and then clear them off our pending  in buildGenericSCCs()
1901   assert(RC.SCCIndices.empty() && "Already mapped SCC indices!");  in buildSCCs()
1905            "We cannot have a low link in an SCC lower than its root on the "  in buildSCCs()
1928   // Wire up the SCC indices.  in buildSCCs()
2007 static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &C) {  in printSCC()
2008   OS << "    SCC with " << C.size() << " functions:\n";  in printSCC()
2017   for (LazyCallGraph::SCC &InnerC : C)  in printRefSCC()