2 files changed, 55 insertions, 0 deletions
diff --git a/compiler/rustc_data_structures/src/transitive_relation.rs b/compiler/rustc_data_structures/src/transitive_relation.rs
index 33ac279f3e0..31abea93819 100644
--- a/compiler/rustc_data_structures/src/transitive_relation.rs
+++ b/compiler/rustc_data_structures/src/transitive_relation.rs
@@ -354,6 +354,20 @@ impl<T: Eq + Hash + Copy> TransitiveRelation<T> {
             .collect()
     }
 
+    /// Given an element A, elements B with the lowest index such that `A R B`
+    /// and `B R A`, or `A` if no such element exists.
+    pub fn minimal_scc_representative(&self, a: T) -> T {
+        match self.index(a) {
+            Some(a_i) => self.with_closure(|closure| {
+                closure
+                    .iter(a_i.0)
+                    .find(|i| closure.contains(*i, a_i.0))
+                    .map_or(a, |i| self.elements[i])
+            }),
+            None => a,
+        }
+    }
+
     fn with_closure<OP, R>(&self, op: OP) -> R
     where
         OP: FnOnce(&BitMatrix<usize, usize>) -> R,
diff --git a/compiler/rustc_data_structures/src/transitive_relation/tests.rs b/compiler/rustc_data_structures/src/transitive_relation/tests.rs
index e756c546e41..cba14b5b64b 100644
--- a/compiler/rustc_data_structures/src/transitive_relation/tests.rs
+++ b/compiler/rustc_data_structures/src/transitive_relation/tests.rs
@@ -376,3 +376,44 @@ fn parent() {
     let p = relation.postdom_parent(3);
     assert_eq!(p, Some(0));
 }
+
+#[test]
+fn minimal_scc_representative_1() {
+    //      +---------+
+    //      v         |
+    // a -> c -> d -> e
+    //           ^    ^
+    //           |    |
+    //           b ---+
+
+    // "digraph { a -> c -> d -> e -> c; b -> d; b -> e; }",
+    let mut relation = TransitiveRelationBuilder::default();
+    relation.add("a", "c");
+    relation.add("c", "d");
+    relation.add("d", "e");
+    relation.add("e", "c");
+    relation.add("b", "d");
+    relation.add("b", "e");
+    let relation = relation.freeze();
+
+    assert_eq!(relation.minimal_scc_representative("a"), "a");
+    assert_eq!(relation.minimal_scc_representative("b"), "b");
+    assert_eq!(relation.minimal_scc_representative("c"), "c");
+    assert_eq!(relation.minimal_scc_representative("d"), "c");
+    assert_eq!(relation.minimal_scc_representative("e"), "c");
+}
+
+#[test]
+fn minimal_scc_representative_2() {
+    // "digraph { a -> b; a -> a; b -> a; c -> c}",
+    let mut relation = TransitiveRelationBuilder::default();
+    relation.add("a", "b");
+    relation.add("b", "a");
+    relation.add("a", "a");
+    relation.add("c", "c");
+    let relation = relation.freeze();
+
+    assert_eq!(relation.minimal_scc_representative("a"), "a");
+    assert_eq!(relation.minimal_scc_representative("b"), "a");
+    assert_eq!(relation.minimal_scc_representative("c"), "c");
+}