Lines Matching refs:SCC
238 LLVM_DUMP_METHOD void LazyCallGraph::SCC::dump() const {
244 void LazyCallGraph::SCC::verify() {
246 assert(!Nodes.empty() && "Can't have an empty SCC!");
251 "Node does not map to this SCC!");
253 "Must set DFS numbers to -1 when adding a node to an SCC!");
255 "Must set low link to -1 when adding a node to an SCC!");
262 bool LazyCallGraph::SCC::isParentOf(const SCC &C) const {
275 bool LazyCallGraph::SCC::isAncestorOf(const SCC &TargetC) const {
281 // Start with this SCC.
282 SmallPtrSet<const SCC *, 16> Visited = {this};
283 SmallVector<const SCC *, 16> Worklist = {this};
287 const SCC &C = *Worklist.pop_back_val();
290 SCC *CalleeC = G.lookupSCC(E.getNode());
294 // If the callee's SCC is the TargetC, we're done.
298 // If this is the first time we've reached this SCC, put it on the
320 assert(!SCCs.empty() && "Can't have an empty SCC!");
323 SmallPtrSet<SCC *, 4> SCCSet;
324 for (SCC *C : SCCs) {
325 assert(C && "Can't have a null SCC!");
328 "SCC doesn't think it is inside this RefSCC!");
330 assert(Inserted && "Found a duplicate SCC!");
333 "Found an SCC that doesn't have an index!");
338 SCC *C = SCCIndexPair.first;
340 assert(C && "Can't have a null SCC in the indices!");
341 assert(SCCSet.count(C) && "Found an index for an SCC not in the RefSCC!");
342 assert(SCCs[i] == C && "Index doesn't point to SCC!");
347 SCC &SourceSCC = *SCCs[i];
352 SCC &TargetSCC = *G->lookupSCC(E.getNode());
368 for (SCC &C : *this)
390 for (SCC &C : DescendantRC)
410 /// all edges in the SCC DAG point to prior SCCs in the sequence.
417 /// When inserting an edge from an earlier SCC to a later SCC in some postorder
422 /// 1) Starting from the source SCC, construct a set of SCCs which reach the
423 /// source SCC consisting of just the source SCC. Then scan toward the
424 /// target SCC in postorder and for each SCC, if it has an edge to an SCC
425 /// in the set, add it to the set. Otherwise, the source SCC is not
427 /// the source SCC, shifting the source SCC and all SCCs in the set one
428 /// position toward the target SCC. Stop scanning after processing the
429 /// target SCC.
430 /// 2) If the source SCC is now past the target SCC in the postorder sequence,
432 /// 3) Otherwise, starting from the target SCC, walk all edges which reach an
433 /// SCC between the source and the target, and add them to the set of
437 /// need to process the source SCC, it is already known to connect.
439 /// SCC and the target SCC in the postorder sequence are connected,
440 /// including the target SCC and the source SCC. Inserting the edge from
441 /// the source SCC to the target SCC will form a cycle out of precisely
443 /// a single SCC.
446 /// - Only mutates the SCCs when adding the edge actually changes the SCC
459 /// The sequence and the map must operate on pointers to the SCC type.
463 /// the source SCC via some (transitive) set of edges. The second computes the
464 /// subset of the same range which the target SCC connects to via some
500 "Last SCC to move should have bene the target.");
502 // Return an empty range at the target SCC indicating there is nothing to
511 "Bad updated index computation for the source SCC!");
543 function_ref<void(ArrayRef<SCC *> MergeSCCs)> MergeCB) {
545 SmallVector<SCC *, 1> DeletedSCCs;
554 SCC &SourceSCC = *G->lookupSCC(SourceN);
555 SCC &TargetSCC = *G->lookupSCC(TargetN);
557 // If the two nodes are already part of the same SCC, we're also done as
565 // insertion of an edge changes the SCC structure in any way.
578 auto ComputeSourceConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {
585 auto IsConnected = [&](SCC &C) {
594 for (SCC *C :
604 auto ComputeTargetConnectedSet = [&](SmallPtrSetImpl<SCC *> &ConnectedSet) {
611 SmallVector<SCC *, 4> Worklist;
614 SCC &C = *Worklist.pop_back_val();
619 SCC &EdgeC = *G->lookupSCC(E.getNode());
648 // Now that the SCC structure is finalized, flip the kind to call.
660 // result SCC.
663 // reachable from the target, meaning any SCC-wide properties deduced about it
665 for (SCC *C : MergeRange) {
680 for (SCC *C : make_range(EraseEnd, SCCs.end()))
683 // Now that the SCC structure is finalized, flip the kind to call.
728 SCC &TargetSCC = *G->lookupSCC(TargetN);
730 "the same SCC to require the "
736 // Otherwise we are removing a call edge from a single SCC. This may break
738 // DFS over the nodes within the SCC to form any sub-cycles that remain as
742 // reach all other nodes in the original SCC by definition. This means that
743 // we want the old SCC to be replaced with an SCC containing that node as it
744 // will be the root of whatever SCC DAG results from the DFS. Assumptions
745 // about an SCC such as the set of functions called will continue to hold,
748 SCC &OldSCC = TargetSCC;
751 SmallVector<SCC *, 4> NewSCCs;
761 // Force the target node to be in the old SCC. This also enables us to take
768 // nodes are reachable from the target due to previously forming an SCC).
778 "Cannot begin a new root with pending nodes for an SCC!");
804 "Found a node with 0 DFS number but already in an SCC!");
815 // If the child is part of the old SCC, we know that it can reach
818 // up the old SCC for why we do this.
853 // SCC stack to eventually get merged into an SCC of nodes.
861 // Otherwise, we've completed an SCC. Append it to our post order list of
872 // Form a new SCC out of these nodes and then clear them off our pending
883 // Insert the remaining SCCs before the old one. The old SCC can reach all
885 // of the old SCC. This means that we will have edges into all of the new
890 // Update the mapping from SCC* to index to use the new SCC*s, and remove the
891 // old SCC from the mapping.
1010 for (SCC &C : RC)
1035 for (SCC &C : RC)
1066 // a connected set with the inserted edge, merge all of them into this SCC.
1067 SmallVector<SCC *, 16> MergedSCCs;
1077 for (SCC &InnerC : *RC) {
1095 for (SCC &InnerC : *this)
1173 // If all targets are in the same SCC as the source, because no call edges
1175 SCC &SourceC = *G->lookupSCC(SourceN);
1182 // for each inner SCC. We store these inside the low-link field of the nodes
1184 // the node->SCC map and in the common case, SCCs are small. We will verify
1185 // that we always give the same number to every node in the SCC such that
1192 for (SCC *C : SCCs) {
1210 "Cannot begin a new root with pending nodes for an SCC!");
1342 for (SCC *C : SCCs) {
1343 // We store the SCC number in the node's low-link field above.
1345 // Clear out all of the SCC's node's low-link fields now that we're done
1349 "Cannot have different numbers for nodes in the same SCC!");
1400 // Check that we aren't breaking some invariants of the SCC graph. Note that
1402 SCC &SourceC = *G->lookupSCC(SourceN);
1403 SCC &TargetC = *G->lookupSCC(TargetN);
1406 "Call edge is not trivial in the SCC graph!");
1534 // if we have a node at all then we must have an SCC and RefSCC.
1537 "Tried to remove a node without an SCC after DFS walk started!");
1538 SCC &C = *CI->second;
1542 // This node must be the only member of its SCC as it has no callers, and
1543 // that SCC must be the only member of a RefSCC as it has no references.
1545 assert(C.size() == 1 && "Dead functions must be in a singular SCC");
1568 void LazyCallGraph::addNewFunctionIntoSCC(Function &NewF, SCC &C) {
1607 void LazyCallGraph::addNodeToSCC(LazyCallGraph::SCC &C, Node &N) {
1627 "Cannot begin a new root with pending nodes for an SCC!");
1677 // SCC stack to eventually get merged into an SCC of nodes.
1685 // Otherwise, we've completed an SCC. Append it to our post order list of
1695 // Form a new SCC out of these nodes and then clear them off our pending
1710 assert(RC.SCCIndices.empty() && "Already mapped SCC indices!");
1714 "We cannot have a low link in an SCC lower than its root on the "
1737 // Wire up the SCC indices.
1796 static void printSCC(raw_ostream &OS, LazyCallGraph::SCC &C) {
1797 OS << " SCC with " << C.size() << " functions:\n";
1806 for (LazyCallGraph::SCC &InnerC : C)