Auto merge of #122459 - Nadrieril:sort-eq, r=oli-obk

match lowering: sort `Eq` candidates in the failure case too

This is a slight tweak to MIR gen of matches. Take a match like:
```rust
match (s, flag) {
    ("a", _) if foo() => 1,
    ("b", true) => 2,
    ("a", false) => 3,
    (_, true) => 4,
    _ => 5,
}
```
If we switch on `s == "a"`, the first candidate matches, and we learn almost nothing about the second candidate. So there's a choice:
1. (what we do today) stop sorting candidates, keep the "b" case grouped with everything below. This could allow us to be clever here and test on `flag == true` next.
2. (what this PR does) sort "b" into the failure case. The "b" will be alone (fewer opportunities for picking a good test), but that means the two "a" cases require a single test.

Today, we aren't clever in which tests we pick, so this is an unambiguous win. In a future where we pick tests better, idk. Grouping tests as much as possible feels like a generally good strategy.

This was proposed in https://github.com/rust-lang/rust/issues/29623 (9 years ago :D)

16 files changed, 255 insertions, 131 deletions

diff --git a/compiler/rustc_mir_build/src/build/matches/test.rs b/compiler/rustc_mir_build/src/build/matches/test.rs
index b66dd83b7ec..690879b9488 100644
--- a/compiler/rustc_mir_build/src/build/matches/test.rs
+++ b/compiler/rustc_mir_build/src/build/matches/test.rs
@@ -650,12 +650,14 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                 }
             }
 
-            // FIXME(#29623): return `Some(1)` when the values are different.
-            (TestKind::Eq { value: test_val, .. }, TestCase::Constant { value: case_val })
-                if test_val == case_val =>
-            {
-                fully_matched = true;
-                Some(TestBranch::Success)
+            (TestKind::Eq { value: test_val, .. }, TestCase::Constant { value: case_val }) => {
+                if test_val == case_val {
+                    fully_matched = true;
+                    Some(TestBranch::Success)
+                } else {
+                    fully_matched = false;
+                    Some(TestBranch::Failure)
+                }
             }
 
             (
diff --git a/tests/mir-opt/deref-patterns/string.foo.PreCodegen.after.mir b/tests/mir-opt/building/match/deref-patterns/string.foo.PreCodegen.after.mir
index 1e4f7485089..1e4f7485089 100644
--- a/tests/mir-opt/deref-patterns/string.foo.PreCodegen.after.mir
+++ b/tests/mir-opt/building/match/deref-patterns/string.foo.PreCodegen.after.mir
diff --git a/tests/mir-opt/deref-patterns/string.rs b/tests/mir-opt/building/match/deref-patterns/string.rs
index bb4b5379b27..bb4b5379b27 100644
--- a/tests/mir-opt/deref-patterns/string.rs
+++ b/tests/mir-opt/building/match/deref-patterns/string.rs
diff --git a/tests/mir-opt/exponential_or.match_tuple.SimplifyCfg-initial.after.mir b/tests/mir-opt/building/match/exponential_or.match_tuple.SimplifyCfg-initial.after.mir
index 596dcef85fd..596dcef85fd 100644
--- a/tests/mir-opt/exponential_or.match_tuple.SimplifyCfg-initial.after.mir
+++ b/tests/mir-opt/building/match/exponential_or.match_tuple.SimplifyCfg-initial.after.mir
diff --git a/tests/mir-opt/exponential_or.rs b/tests/mir-opt/building/match/exponential_or.rs
index 89963b9bdf4..89963b9bdf4 100644
--- a/tests/mir-opt/exponential_or.rs
+++ b/tests/mir-opt/building/match/exponential_or.rs
diff --git a/tests/mir-opt/building/match_false_edges.full_tested_match.built.after.mir b/tests/mir-opt/building/match/match_false_edges.full_tested_match.built.after.mir
index 194afdf7dd8..194afdf7dd8 100644
--- a/tests/mir-opt/building/match_false_edges.full_tested_match.built.after.mir
+++ b/tests/mir-opt/building/match/match_false_edges.full_tested_match.built.after.mir
diff --git a/tests/mir-opt/building/match_false_edges.full_tested_match2.built.after.mir b/tests/mir-opt/building/match/match_false_edges.full_tested_match2.built.after.mir
index ae83075434f..ae83075434f 100644
--- a/tests/mir-opt/building/match_false_edges.full_tested_match2.built.after.mir
+++ b/tests/mir-opt/building/match/match_false_edges.full_tested_match2.built.after.mir
diff --git a/tests/mir-opt/building/match_false_edges.main.built.after.mir b/tests/mir-opt/building/match/match_false_edges.main.built.after.mir
index b71b2412cdf..b71b2412cdf 100644
--- a/tests/mir-opt/building/match_false_edges.main.built.after.mir
+++ b/tests/mir-opt/building/match/match_false_edges.main.built.after.mir
diff --git a/tests/mir-opt/building/match_false_edges.rs b/tests/mir-opt/building/match/match_false_edges.rs
index 839eda40c85..839eda40c85 100644
--- a/tests/mir-opt/building/match_false_edges.rs
+++ b/tests/mir-opt/building/match/match_false_edges.rs
diff --git a/tests/mir-opt/building/simple_match.match_bool.built.after.mir b/tests/mir-opt/building/match/simple_match.match_bool.built.after.mir
index faa2456fd10..faa2456fd10 100644
--- a/tests/mir-opt/building/simple_match.match_bool.built.after.mir
+++ b/tests/mir-opt/building/match/simple_match.match_bool.built.after.mir
diff --git a/tests/mir-opt/building/simple_match.rs b/tests/mir-opt/building/match/simple_match.rs
index 4f0a3046a06..4f0a3046a06 100644
--- a/tests/mir-opt/building/simple_match.rs
+++ b/tests/mir-opt/building/match/simple_match.rs
diff --git a/tests/mir-opt/building/match/sort_candidates.constant_eq.SimplifyCfg-initial.after.mir b/tests/mir-opt/building/match/sort_candidates.constant_eq.SimplifyCfg-initial.after.mir
new file mode 100644
index 00000000000..e95a97b5b87
--- /dev/null
+++ b/tests/mir-opt/building/match/sort_candidates.constant_eq.SimplifyCfg-initial.after.mir
@@ -0,0 +1,118 @@
+// MIR for `constant_eq` after SimplifyCfg-initial
+
+fn constant_eq(_1: &str, _2: bool) -> u32 {
+    debug s => _1;
+    debug b => _2;
+    let mut _0: u32;
+    let mut _3: (&str, bool);
+    let mut _4: &str;
+    let mut _5: bool;
+    let mut _6: bool;
+    let mut _7: bool;
+    let mut _8: &&str;
+    let mut _9: &bool;
+    let mut _10: bool;
+
+    bb0: {
+        StorageLive(_3);
+        StorageLive(_4);
+        _4 = _1;
+        StorageLive(_5);
+        _5 = _2;
+        _3 = (move _4, move _5);
+        StorageDead(_5);
+        StorageDead(_4);
+        PlaceMention(_3);
+        _7 = <str as PartialEq>::eq((_3.0: &str), const "a") -> [return: bb11, unwind: bb19];
+    }
+
+    bb1: {
+        switchInt((_3.1: bool)) -> [0: bb2, otherwise: bb3];
+    }
+
+    bb2: {
+        _0 = const 5_u32;
+        goto -> bb18;
+    }
+
+    bb3: {
+        falseEdge -> [real: bb17, imaginary: bb2];
+    }
+
+    bb4: {
+        falseEdge -> [real: bb12, imaginary: bb9];
+    }
+
+    bb5: {
+        switchInt((_3.1: bool)) -> [0: bb1, otherwise: bb6];
+    }
+
+    bb6: {
+        falseEdge -> [real: bb16, imaginary: bb3];
+    }
+
+    bb7: {
+        _6 = <str as PartialEq>::eq((_3.0: &str), const "b") -> [return: bb10, unwind: bb19];
+    }
+
+    bb8: {
+        switchInt((_3.1: bool)) -> [0: bb1, otherwise: bb9];
+    }
+
+    bb9: {
+        falseEdge -> [real: bb15, imaginary: bb6];
+    }
+
+    bb10: {
+        switchInt(move _6) -> [0: bb1, otherwise: bb8];
+    }
+
+    bb11: {
+        switchInt(move _7) -> [0: bb7, otherwise: bb4];
+    }
+
+    bb12: {
+        _8 = &fake (_3.0: &str);
+        _9 = &fake (_3.1: bool);
+        StorageLive(_10);
+        _10 = const true;
+        switchInt(move _10) -> [0: bb14, otherwise: bb13];
+    }
+
+    bb13: {
+        StorageDead(_10);
+        FakeRead(ForMatchGuard, _8);
+        FakeRead(ForMatchGuard, _9);
+        _0 = const 1_u32;
+        goto -> bb18;
+    }
+
+    bb14: {
+        StorageDead(_10);
+        falseEdge -> [real: bb5, imaginary: bb9];
+    }
+
+    bb15: {
+        _0 = const 2_u32;
+        goto -> bb18;
+    }
+
+    bb16: {
+        _0 = const 3_u32;
+        goto -> bb18;
+    }
+
+    bb17: {
+        _0 = const 4_u32;
+        goto -> bb18;
+    }
+
+    bb18: {
+        StorageDead(_3);
+        return;
+    }
+
+    bb19 (cleanup): {
+        resume;
+    }
+}
diff --git a/tests/mir-opt/building/match/sort_candidates.disjoint_ranges.SimplifyCfg-initial.after.mir b/tests/mir-opt/building/match/sort_candidates.disjoint_ranges.SimplifyCfg-initial.after.mir
new file mode 100644
index 00000000000..80d3c2e5c23
--- /dev/null
+++ b/tests/mir-opt/building/match/sort_candidates.disjoint_ranges.SimplifyCfg-initial.after.mir
@@ -0,0 +1,88 @@
+// MIR for `disjoint_ranges` after SimplifyCfg-initial
+
+fn disjoint_ranges(_1: i32, _2: bool) -> u32 {
+    debug x => _1;
+    debug b => _2;
+    let mut _0: u32;
+    let mut _3: bool;
+    let mut _4: bool;
+    let mut _5: bool;
+    let mut _6: bool;
+    let mut _7: &i32;
+    let mut _8: bool;
+
+    bb0: {
+        PlaceMention(_1);
+        _5 = Le(const 0_i32, _1);
+        switchInt(move _5) -> [0: bb3, otherwise: bb8];
+    }
+
+    bb1: {
+        _0 = const 3_u32;
+        goto -> bb14;
+    }
+
+    bb2: {
+        falseEdge -> [real: bb9, imaginary: bb4];
+    }
+
+    bb3: {
+        _3 = Le(const 10_i32, _1);
+        switchInt(move _3) -> [0: bb5, otherwise: bb7];
+    }
+
+    bb4: {
+        falseEdge -> [real: bb12, imaginary: bb6];
+    }
+
+    bb5: {
+        switchInt(_1) -> [4294967295: bb6, otherwise: bb1];
+    }
+
+    bb6: {
+        falseEdge -> [real: bb13, imaginary: bb1];
+    }
+
+    bb7: {
+        _4 = Le(_1, const 20_i32);
+        switchInt(move _4) -> [0: bb5, otherwise: bb4];
+    }
+
+    bb8: {
+        _6 = Lt(_1, const 10_i32);
+        switchInt(move _6) -> [0: bb3, otherwise: bb2];
+    }
+
+    bb9: {
+        _7 = &fake _1;
+        StorageLive(_8);
+        _8 = _2;
+        switchInt(move _8) -> [0: bb11, otherwise: bb10];
+    }
+
+    bb10: {
+        StorageDead(_8);
+        FakeRead(ForMatchGuard, _7);
+        _0 = const 0_u32;
+        goto -> bb14;
+    }
+
+    bb11: {
+        StorageDead(_8);
+        falseEdge -> [real: bb1, imaginary: bb4];
+    }
+
+    bb12: {
+        _0 = const 1_u32;
+        goto -> bb14;
+    }
+
+    bb13: {
+        _0 = const 2_u32;
+        goto -> bb14;
+    }
+
+    bb14: {
+        return;
+    }
+}
diff --git a/tests/mir-opt/building/match/sort_candidates.rs b/tests/mir-opt/building/match/sort_candidates.rs
new file mode 100644
index 00000000000..a2583ff8284
--- /dev/null
+++ b/tests/mir-opt/building/match/sort_candidates.rs
@@ -0,0 +1,41 @@
+// Check specific cases of sorting candidates in match lowering.
+#![feature(exclusive_range_pattern)]
+
+// EMIT_MIR sort_candidates.constant_eq.SimplifyCfg-initial.after.mir
+fn constant_eq(s: &str, b: bool) -> u32 {
+    // Check that we only test "a" once
+
+    // CHECK-LABEL: fn constant_eq(
+    // CHECK: bb0: {
+    // CHECK: [[a:_.*]] = const "a";
+    // CHECK-NOT: {{_.*}} = const "a";
+    match (s, b) {
+        ("a", _) if true => 1,
+        ("b", true) => 2,
+        ("a", true) => 3,
+        (_, true) => 4,
+        _ => 5,
+    }
+}
+
+// EMIT_MIR sort_candidates.disjoint_ranges.SimplifyCfg-initial.after.mir
+fn disjoint_ranges(x: i32, b: bool) -> u32 {
+    // When `(0..=10).contains(x) && !b`, we should jump to the last arm without testing the two
+    // other candidates.
+
+    // CHECK-LABEL: fn disjoint_ranges(
+    // CHECK: debug b => _2;
+    // CHECK: bb0: {
+    // CHECK: switchInt(_2) -> [0: [[jump:bb.*]], otherwise: {{bb.*}}];
+    // CHECK: [[jump]]: {
+    // CHECK-NEXT: _0 = const 3_u32;
+    // CHECK-NEXT: return;
+    match x {
+        0..10 if b => 0,
+        10..=20 => 1,
+        -1 => 2,
+        _ => 3,
+    }
+}
+
+fn main() {}
diff --git a/tests/mir-opt/match_test.main.SimplifyCfg-initial.after.mir b/tests/mir-opt/match_test.main.SimplifyCfg-initial.after.mir
deleted file mode 100644
index 107f56f7f69..00000000000
--- a/tests/mir-opt/match_test.main.SimplifyCfg-initial.after.mir
+++ /dev/null
@@ -1,106 +0,0 @@
-// MIR for `main` after SimplifyCfg-initial
-
-fn main() -> () {
-    let mut _0: ();
-    let _1: i32;
-    let _3: i32;
-    let mut _4: bool;
-    let mut _5: bool;
-    let mut _6: bool;
-    let mut _7: bool;
-    let mut _8: &i32;
-    let mut _9: bool;
-    scope 1 {
-        debug x => _1;
-        let _2: bool;
-        scope 2 {
-            debug b => _2;
-        }
-    }
-
-    bb0: {
-        StorageLive(_1);
-        _1 = const 3_i32;
-        FakeRead(ForLet(None), _1);
-        StorageLive(_2);
-        _2 = const true;
-        FakeRead(ForLet(None), _2);
-        StorageLive(_3);
-        PlaceMention(_1);
-        _6 = Le(const 0_i32, _1);
-        switchInt(move _6) -> [0: bb3, otherwise: bb8];
-    }
-
-    bb1: {
-        _3 = const 3_i32;
-        goto -> bb14;
-    }
-
-    bb2: {
-        falseEdge -> [real: bb9, imaginary: bb4];
-    }
-
-    bb3: {
-        _4 = Le(const 10_i32, _1);
-        switchInt(move _4) -> [0: bb5, otherwise: bb7];
-    }
-
-    bb4: {
-        falseEdge -> [real: bb12, imaginary: bb6];
-    }
-
-    bb5: {
-        switchInt(_1) -> [4294967295: bb6, otherwise: bb1];
-    }
-
-    bb6: {
-        falseEdge -> [real: bb13, imaginary: bb1];
-    }
-
-    bb7: {
-        _5 = Le(_1, const 20_i32);
-        switchInt(move _5) -> [0: bb5, otherwise: bb4];
-    }
-
-    bb8: {
-        _7 = Lt(_1, const 10_i32);
-        switchInt(move _7) -> [0: bb3, otherwise: bb2];
-    }
-
-    bb9: {
-        _8 = &fake _1;
-        StorageLive(_9);
-        _9 = _2;
-        switchInt(move _9) -> [0: bb11, otherwise: bb10];
-    }
-
-    bb10: {
-        StorageDead(_9);
-        FakeRead(ForMatchGuard, _8);
-        _3 = const 0_i32;
-        goto -> bb14;
-    }
-
-    bb11: {
-        StorageDead(_9);
-        falseEdge -> [real: bb1, imaginary: bb4];
-    }
-
-    bb12: {
-        _3 = const 1_i32;
-        goto -> bb14;
-    }
-
-    bb13: {
-        _3 = const 2_i32;
-        goto -> bb14;
-    }
-
-    bb14: {
-        StorageDead(_3);
-        _0 = const ();
-        StorageDead(_2);
-        StorageDead(_1);
-        return;
-    }
-}
diff --git a/tests/mir-opt/match_test.rs b/tests/mir-opt/match_test.rs
deleted file mode 100644
index e465289e427..00000000000
--- a/tests/mir-opt/match_test.rs
+++ /dev/null
@@ -1,19 +0,0 @@
-// skip-filecheck
-// Make sure redundant testing paths in `match` expressions are sorted out.
-
-#![feature(exclusive_range_pattern)]
-
-// EMIT_MIR match_test.main.SimplifyCfg-initial.after.mir
-fn main() {
-    let x = 3;
-    let b = true;
-
-    // When `(0..=10).contains(x) && !b`, we should jump to the last arm
-    // without testing two other candidates.
-    match x {
-        0..10 if b => 0,
-        10..=20 => 1,
-        -1 => 2,
-        _ => 3,
-    };
-}