Lines Matching defs:SCCs
344 assert(!SCCs.empty() && "Can't have an empty SCC!");
346 // Verify basic properties of the SCCs.
348 for (SCC *C : SCCs) {
364 assert(SCCs[I] == C && "Index doesn't point to SCC!");
367 // Check that the SCCs are in fact in post-order.
368 for (int I = 0, Size = SCCs.size(); I < Size; ++I) {
369 SCC &SourceSCC = *SCCs[I];
377 "Edge between SCCs violates post-order relationship.");
386 for (SCC *C : SCCs) {
452 /// Generic helper that updates a postorder sequence of SCCs for a potentially
455 /// A postorder sequence of SCCs of a directed graph has one fundamental
456 /// property: all deges in the DAG of SCCs point "up" the sequence. That is,
457 /// all edges in the SCC DAG point to prior SCCs in the sequence.
460 /// compute the set of SCCs connected into a cycle. It should only be called to
465 /// sequence, all of the SCCs which may be impacted are in the closed range of
469 /// 1) Starting from the source SCC, construct a set of SCCs which reach the
474 /// the source SCC, shifting the source SCC and all SCCs in the set one
481 /// connected SCCs, then recurse through them. Once a complete set of the
482 /// SCCs the target connects to is known, hoist the remaining SCCs between
485 /// 4) At this point, all of the SCCs in the closed range between the source
489 /// these SCCs. Thus we can merge all of the SCCs in this closed range into
493 /// - Only mutates the SCCs when adding the edge actually changes the SCC
495 /// - Never mutates SCCs which are unaffected by the change.
498 /// - Only reorders SCCs in the closed postorder sequence from the source to
500 /// - Big-O is the number of edges in the closed postorder range of SCCs from
504 /// will also update a map from SCCs to indices within that sequence.
508 /// Two callbacks must be provided. The first computes the subset of SCCs in
519 SCCT &SourceSCC, SCCT &TargetSCC, PostorderSequenceT &SCCs,
529 // Compute the SCCs which (transitively) reach the source.
532 // Partition the SCCs in this part of the port-order sequence so only SCCs
536 SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx + 1,
539 SCCIndices.find(SCCs[I])->second = I;
544 assert(SourceI > (SCCs.begin() + SourceIdx) &&
554 assert(SCCs[TargetIdx] == &TargetSCC &&
556 SourceIdx = SourceI - SCCs.begin();
557 assert(SCCs[SourceIdx] == &SourceSCC &&
560 // See whether there are any remaining intervening SCCs between the source
567 // Partition SCCs so that only SCCs reached from the target remain between
570 SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1,
573 SCCIndices.find(SCCs[I])->second = I;
574 TargetIdx = std::prev(TargetI) - SCCs.begin();
575 assert(SCCs[TargetIdx] == &TargetSCC &&
580 // because target connects back to source, and we know that all the SCCs
583 return make_range(SCCs.begin() + SourceIdx, SCCs.begin() + TargetIdx);
607 // At this point we leverage the postorder list of SCCs to detect when the
620 // Compute the SCCs which (transitively) reach the source.
638 make_range(SCCs.begin() + SourceIdx + 1, SCCs.begin() + TargetIdx + 1))
643 // Use a normal worklist to find which SCCs the target connects to. We still
676 // Use a generic helper to update the postorder sequence of SCCs and return
677 // a range of any SCCs connected into a cycle by inserting this edge. This
681 SourceSCC, TargetSCC, SCCs, SCCIndices, ComputeSourceConnectedSet,
684 // Run the user's callback on the merged SCCs before we actually merge them.
702 // Otherwise we need to merge all the SCCs in the cycle into a single result
719 // Erase the merged SCCs from the list and update the indices of the
720 // remaining SCCs.
722 auto EraseEnd = SCCs.erase(MergeRange.begin(), MergeRange.end());
723 for (SCC *C : make_range(EraseEnd, SCCs.end()))
745 "Source and Target must be in separate SCCs for this to be trivial!");
772 // the cycle. In order to compute the new set of SCCs, we need to do a small
774 // distinct SCCs and compute a postorder over the resulting SCCs.
797 // a very significant short-cut in the standard Tarjan walk to re-form SCCs
895 // SCCs.
916 // Insert the remaining SCCs before the old one. The old SCC can reach all
917 // other SCCs we form because it contains the target node of the removed edge
918 // of the old SCC. This means that we will have edges into all the new SCCs,
921 SCCs.insert(SCCs.begin() + OldIdx, NewSCCs.begin(), NewSCCs.end());
925 for (int Idx = OldIdx, Size = SCCs.size(); Idx < Size; ++Idx)
926 SCCIndices[SCCs[Idx]] = Idx;
928 return make_range(SCCs.begin() + OldIdx,
929 SCCs.begin() + OldIdx + NewSCCs.size());
1052 // Use a normal worklist to find which SCCs the target connects to. We still
1092 // Now that we have identified all the SCCs which need to be merged into
1100 // Walk the inner SCCs to update their up-pointer and walk all the edges to
1111 // Now merge in the SCCs. We can actually move here so try to reuse storage
1114 MergedSCCs = std::move(RC->SCCs);
1116 MergedSCCs.append(RC->SCCs.begin(), RC->SCCs.end());
1117 RC->SCCs.clear();
1121 // Append our original SCCs to the merged list and move it into place.
1124 MergedSCCs.append(SCCs.begin(), SCCs.end());
1125 SCCs = std::move(MergedSCCs);
1136 // At this point we have a merged RefSCC with a post-order SCCs list, just
1140 // We return the list of SCCs which were merged so that callers can
1141 // invalidate any data they have associated with those SCCs. Note that these
1142 // SCCs are no longer in an interesting state (they are totally empty) but
1204 // rather than associated with SCCs because this saves a round-trip through
1205 // the node->SCC map and in the common case, SCCs are small. We will verify
1213 for (SCC *C : SCCs) {
1310 // it to map SCCs into new RefSCCs after we finish the DFS.
1342 // append SCCs to each of these RefSCCs in the order they occurred in the
1343 // original SCCs container.
1361 for (SCC *C : SCCs) {
1373 int SCCIndex = RC.SCCs.size();
1374 RC.SCCs.push_back(C);
1382 SCCs.clear();
1391 // Return the new list of SCCs.
1486 "This method cannot be called after SCCs have been formed!");
1493 "This method cannot be called after SCCs have been formed!");
1673 NewRC->SCCs.insert(NewRC->SCCs.begin() + InsertIndex, NewC);
1674 for (int I = InsertIndex, Size = NewRC->SCCs.size(); I < Size; ++I)
1675 NewRC->SCCIndices[NewRC->SCCs[I]] = I;
1689 NewRC->SCCs.push_back(NewC);
1760 // The new SCCs are either sibling SCCs or parent SCCs to all other existing
1761 // SCCs in the RefSCC. Either way, they can go at the back of the postorder
1765 NewRC->SCCs.push_back(NewC);
1879 // SCCs.
1896 /// Build the internal SCCs for a RefSCC from a sequence of nodes.
1898 /// Appends the SCCs to the provided vector and updates the map with their
1902 assert(RC.SCCs.empty() && "Already built SCCs!");
1915 // Each RefSCC contains a DAG of the call SCCs. To build these, we do
1923 RC.SCCs.push_back(createSCC(RC, Nodes));
1924 for (Node &N : *RC.SCCs.back()) {
1926 SCCMap[&N] = RC.SCCs.back();
1931 for (int I = 0, Size = RC.SCCs.size(); I < Size; ++I)
1932 RC.SCCIndices[RC.SCCs[I]] = I;
2017 OS << " RefSCC with " << C.size() << " call SCCs:\n";