Lines Matching defs:SCCs
342 assert(!SCCs.empty() && "Can't have an empty SCC!");
344 // Verify basic properties of the SCCs.
346 for (SCC *C : SCCs) {
362 assert(SCCs[I] == C && "Index doesn't point to SCC!");
365 // Check that the SCCs are in fact in post-order.
366 for (int I = 0, Size = SCCs.size(); I < Size; ++I) {
367 SCC &SourceSCC = *SCCs[I];
375 "Edge between SCCs violates post-order relationship.");
384 for (SCC *C : SCCs) {
450 /// Generic helper that updates a postorder sequence of SCCs for a potentially
453 /// A postorder sequence of SCCs of a directed graph has one fundamental
454 /// property: all deges in the DAG of SCCs point "up" the sequence. That is,
455 /// all edges in the SCC DAG point to prior SCCs in the sequence.
458 /// compute the set of SCCs connected into a cycle. It should only be called to
463 /// sequence, all of the SCCs which may be impacted are in the closed range of
467 /// 1) Starting from the source SCC, construct a set of SCCs which reach the
472 /// the source SCC, shifting the source SCC and all SCCs in the set one
479 /// connected SCCs, then recurse through them. Once a complete set of the
480 /// SCCs the target connects to is known, hoist the remaining SCCs between
483 /// 4) At this point, all of the SCCs in the closed range between the source
487 /// these SCCs. Thus we can merge all of the SCCs in this closed range into
491 /// - Only mutates the SCCs when adding the edge actually changes the SCC
493 /// - Never mutates SCCs which are unaffected by the change.
496 /// - Only reorders SCCs in the closed postorder sequence from the source to
498 /// - Big-O is the number of edges in the closed postorder range of SCCs from
502 /// will also update a map from SCCs to indices within that sequence.
506 /// Two callbacks must be provided. The first computes the subset of SCCs in
517 SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs,
527 // Compute the SCCs which (transitively) reach the source.
530 // Partition the SCCs in this part of the port-order sequence so only SCCs
534 SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1,
537 SCCIndices.find(SCCs[I])->second = I;
542 assert(SourceI > (SCCs.begin() + SourceIdx) &&
552 assert(SCCs[TargetIdx] == &TargetSCC &&
554 SourceIdx = SourceI - SCCs.begin();
555 assert(SCCs[SourceIdx] == &SourceSCC &&
558 // See whether there are any remaining intervening SCCs between the source
565 // Partition SCCs so that only SCCs reached from the target remain between
568 SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1,
571 SCCIndices.find(SCCs[I])->second = I;
572 TargetIdx = std::prev(TargetI) - SCCs.begin();
573 assert(SCCs[TargetIdx] == &TargetSCC &&
578 // because target connects back to source, and we know that all the SCCs
581 return make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx);
605 // At this point we leverage the postorder list of SCCs to detect when the
618 // Compute the SCCs which (transitively) reach the source.
636 make_range(SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1))
641 // Use a normal worklist to find which SCCs the target connects to. We still
674 // Use a generic helper to update the postorder sequence of SCCs and return
675 // a range of any SCCs connected into a cycle by inserting this edge. This
679 SourceSCC, TargetSCC, SCCs, SCCIndices, ComputeSourceConnectedSet,
682 // Run the user's callback on the merged SCCs before we actually merge them.
700 // Otherwise we need to merge all the SCCs in the cycle into a single result
717 // Erase the merged SCCs from the list and update the indices of the
718 // remaining SCCs.
720 auto EraseEnd = SCCs.erase(MergeRange.begin(), MergeRange.end());
721 for (SCC *C : make_range(EraseEnd, SCCs.end()))
743 "Source and Target must be in separate SCCs for this to be trivial!");
770 // the cycle. In order to compute the new set of SCCs, we need to do a small
772 // distinct SCCs and compute a postorder over the resulting SCCs.
795 // a very significant short-cut in the standard Tarjan walk to re-form SCCs
893 // SCCs.
914 // Insert the remaining SCCs before the old one. The old SCC can reach all
915 // other SCCs we form because it contains the target node of the removed edge
916 // of the old SCC. This means that we will have edges into all the new SCCs,
919 SCCs.insert(SCCs.begin() + OldIdx, NewSCCs.begin(), NewSCCs.end());
923 for (int Idx = OldIdx, Size = SCCs.size(); Idx < Size; ++Idx)
924 SCCIndices[SCCs[Idx]] = Idx;
926 return make_range(SCCs.begin() + OldIdx,
927 SCCs.begin() + OldIdx + NewSCCs.size());
1050 // Use a normal worklist to find which SCCs the target connects to. We still
1090 // Now that we have identified all the SCCs which need to be merged into
1098 // Walk the inner SCCs to update their up-pointer and walk all the edges to
1109 // Now merge in the SCCs. We can actually move here so try to reuse storage
1112 MergedSCCs = std::move(RC->SCCs);
1114 MergedSCCs.append(RC->SCCs.begin(), RC->SCCs.end());
1115 RC->SCCs.clear();
1119 // Append our original SCCs to the merged list and move it into place.
1122 MergedSCCs.append(SCCs.begin(), SCCs.end());
1123 SCCs = std::move(MergedSCCs);
1134 // At this point we have a merged RefSCC with a post-order SCCs list, just
1138 // We return the list of SCCs which were merged so that callers can
1139 // invalidate any data they have associated with those SCCs. Note that these
1140 // SCCs are no longer in an interesting state (they are totally empty) but
1202 // rather than associated with SCCs because this saves a round-trip through
1203 // the node->SCC map and in the common case, SCCs are small. We will verify
1211 for (SCC *C : SCCs) {
1308 // it to map SCCs into new RefSCCs after we finish the DFS.
1340 // append SCCs to each of these RefSCCs in the order they occurred in the
1341 // original SCCs container.
1359 for (SCC *C : SCCs) {
1371 int SCCIndex = RC.SCCs.size();
1372 RC.SCCs.push_back(C);
1380 SCCs.clear();
1389 // Return the new list of SCCs.
1484 "This method cannot be called after SCCs have been formed!");
1491 "This method cannot be called after SCCs have been formed!");
1671 NewRC->SCCs.insert(NewRC->SCCs.begin() + InsertIndex, NewC);
1672 for (int I = InsertIndex, Size = NewRC->SCCs.size(); I < Size; ++I)
1673 NewRC->SCCIndices[NewRC->SCCs[I]] = I;
1687 NewRC->SCCs.push_back(NewC);
1758 // The new SCCs are either sibling SCCs or parent SCCs to all other existing
1759 // SCCs in the RefSCC. Either way, they can go at the back of the postorder
1763 NewRC->SCCs.push_back(NewC);
1877 // SCCs.
1894 /// Build the internal SCCs for a RefSCC from a sequence of nodes.
1896 /// Appends the SCCs to the provided vector and updates the map with their
1900 assert(RC.SCCs.empty() && "Already built SCCs!");
1913 // Each RefSCC contains a DAG of the call SCCs. To build these, we do
1921 RC.SCCs.push_back(createSCC(RC, Nodes));
1922 for (Node &N : *RC.SCCs.back()) {
1924 SCCMap[&N] = RC.SCCs.back();
1929 for (int I = 0, Size = RC.SCCs.size(); I < Size; ++I)
1930 RC.SCCIndices[RC.SCCs[I]] = I;
2015 OS << " RefSCC with " << C.size() << " call SCCs:\n";