Rollup merge of #121908 - Nadrieril:dynamic-variant-collection, r=matthewjasper

match lowering: don't collect test alternatives ahead of time

I'm very happy with this one. Before this, when sorting candidates into the possible test branches, we manually computed `usize` indices to determine in which branch each candidate goes. To make this work we had a first pass that collected the possible alternatives we'd have to deal with, and a second pass that actually sorts the candidates.

In this PR, I replace `usize` indices with a dedicated enum. This makes `sort_candidates` easier to follow, and we don't need the first pass anymore.

r? ``@matthewjasper``

9 files changed, 206 insertions, 274 deletions

diff --git a/compiler/rustc_mir_build/src/build/matches/mod.rs b/compiler/rustc_mir_build/src/build/matches/mod.rs
index 48c3ee1ba0f..4d5ed65c841 100644
--- a/compiler/rustc_mir_build/src/build/matches/mod.rs
+++ b/compiler/rustc_mir_build/src/build/matches/mod.rs
@@ -14,7 +14,6 @@ use rustc_data_structures::{
     fx::{FxHashSet, FxIndexMap, FxIndexSet},
     stack::ensure_sufficient_stack,
 };
-use rustc_index::bit_set::BitSet;
 use rustc_middle::middle::region;
 use rustc_middle::mir::{self, *};
 use rustc_middle::thir::{self, *};
@@ -1084,6 +1083,12 @@ enum TestCase<'pat, 'tcx> {
     Or { pats: Box<[FlatPat<'pat, 'tcx>]> },
 }
 
+impl<'pat, 'tcx> TestCase<'pat, 'tcx> {
+    fn as_range(&self) -> Option<&'pat PatRange<'tcx>> {
+        if let Self::Range(v) = self { Some(*v) } else { None }
+    }
+}
+
 #[derive(Debug, Clone)]
 pub(crate) struct MatchPair<'pat, 'tcx> {
     /// This place...
@@ -1108,19 +1113,10 @@ enum TestKind<'tcx> {
     Switch {
         /// The enum type being tested.
         adt_def: ty::AdtDef<'tcx>,
-        /// The set of variants that we should create a branch for. We also
-        /// create an additional "otherwise" case.
-        variants: BitSet<VariantIdx>,
     },
 
     /// Test what value an integer or `char` has.
-    SwitchInt {
-        /// The (ordered) set of values that we test for.
-        ///
-        /// We create a branch to each of the values in `options`, as well as an "otherwise" branch
-        /// for all other values, even in the (rare) case that `options` is exhaustive.
-        options: FxIndexMap<Const<'tcx>, u128>,
-    },
+    SwitchInt,
 
     /// Test what value a `bool` has.
     If,
@@ -1152,6 +1148,25 @@ pub(crate) struct Test<'tcx> {
     kind: TestKind<'tcx>,
 }
 
+/// The branch to be taken after a test.
+#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
+enum TestBranch<'tcx> {
+    /// Success branch, used for tests with two possible outcomes.
+    Success,
+    /// Branch corresponding to this constant.
+    Constant(Const<'tcx>, u128),
+    /// Branch corresponding to this variant.
+    Variant(VariantIdx),
+    /// Failure branch for tests with two possible outcomes, and "otherwise" branch for other tests.
+    Failure,
+}
+
+impl<'tcx> TestBranch<'tcx> {
+    fn as_constant(&self) -> Option<&Const<'tcx>> {
+        if let Self::Constant(v, _) = self { Some(v) } else { None }
+    }
+}
+
 /// `ArmHasGuard` is a wrapper around a boolean flag. It indicates whether
 /// a match arm has a guard expression attached to it.
 #[derive(Copy, Clone, Debug)]
@@ -1561,30 +1576,9 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
     ) -> (PlaceBuilder<'tcx>, Test<'tcx>) {
         // Extract the match-pair from the highest priority candidate
         let match_pair = &candidates.first().unwrap().match_pairs[0];
-        let mut test = self.test(match_pair);
+        let test = self.test(match_pair);
         let match_place = match_pair.place.clone();
-
         debug!(?test, ?match_pair);
-        // Most of the time, the test to perform is simply a function of the main candidate; but for
-        // a test like SwitchInt, we may want to add cases based on the candidates that are
-        // available
-        match test.kind {
-            TestKind::SwitchInt { ref mut options } => {
-                for candidate in candidates.iter() {
-                    if !self.add_cases_to_switch(&match_place, candidate, options) {
-                        break;
-                    }
-                }
-            }
-            TestKind::Switch { adt_def: _, ref mut variants } => {
-                for candidate in candidates.iter() {
-                    if !self.add_variants_to_switch(&match_place, candidate, variants) {
-                        break;
-                    }
-                }
-            }
-            _ => {}
-        }
 
         (match_place, test)
     }
@@ -1627,11 +1621,13 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
         match_place: &PlaceBuilder<'tcx>,
         test: &Test<'tcx>,
         mut candidates: &'b mut [&'c mut Candidate<'pat, 'tcx>],
-    ) -> (&'b mut [&'c mut Candidate<'pat, 'tcx>], Vec<Vec<&'b mut Candidate<'pat, 'tcx>>>) {
-        // For each of the N possible outcomes, create a (initially empty) vector of candidates.
-        // Those are the candidates that apply if the test has that particular outcome.
-        let mut target_candidates: Vec<Vec<&mut Candidate<'pat, 'tcx>>> = vec![];
-        target_candidates.resize_with(test.targets(), Default::default);
+    ) -> (
+        &'b mut [&'c mut Candidate<'pat, 'tcx>],
+        FxIndexMap<TestBranch<'tcx>, Vec<&'b mut Candidate<'pat, 'tcx>>>,
+    ) {
+        // For each of the possible outcomes, collect vector of candidates that apply if the test
+        // has that particular outcome.
+        let mut target_candidates: FxIndexMap<_, Vec<&mut Candidate<'_, '_>>> = Default::default();
 
         let total_candidate_count = candidates.len();
 
@@ -1639,11 +1635,13 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
         // point we may encounter a candidate where the test is not relevant; at that point, we stop
         // sorting.
         while let Some(candidate) = candidates.first_mut() {
-            let Some(idx) = self.sort_candidate(&match_place, &test, candidate) else {
+            let Some(branch) =
+                self.sort_candidate(&match_place, test, candidate, &target_candidates)
+            else {
                 break;
             };
             let (candidate, rest) = candidates.split_first_mut().unwrap();
-            target_candidates[idx].push(candidate);
+            target_candidates.entry(branch).or_insert_with(Vec::new).push(candidate);
             candidates = rest;
         }
 
@@ -1784,31 +1782,32 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
             otherwise_block
         };
 
-        // For each outcome of test, process the candidates that still
-        // apply. Collect a list of blocks where control flow will
-        // branch if one of the `target_candidate` sets is not
-        // exhaustive.
-        let target_blocks: Vec<_> = target_candidates
+        // For each outcome of test, process the candidates that still apply.
+        let target_blocks: FxIndexMap<_, _> = target_candidates
             .into_iter()
-            .map(|mut candidates| {
-                if !candidates.is_empty() {
-                    let candidate_start = self.cfg.start_new_block();
-                    self.match_candidates(
-                        span,
-                        scrutinee_span,
-                        candidate_start,
-                        remainder_start,
-                        &mut *candidates,
-                    );
-                    candidate_start
-                } else {
-                    remainder_start
-                }
+            .map(|(branch, mut candidates)| {
+                let candidate_start = self.cfg.start_new_block();
+                self.match_candidates(
+                    span,
+                    scrutinee_span,
+                    candidate_start,
+                    remainder_start,
+                    &mut *candidates,
+                );
+                (branch, candidate_start)
             })
             .collect();
 
         // Perform the test, branching to one of N blocks.
-        self.perform_test(span, scrutinee_span, start_block, &match_place, &test, target_blocks);
+        self.perform_test(
+            span,
+            scrutinee_span,
+            start_block,
+            remainder_start,
+            &match_place,
+            &test,
+            target_blocks,
+        );
     }
 
     /// Determine the fake borrows that are needed from a set of places that
diff --git a/compiler/rustc_mir_build/src/build/matches/test.rs b/compiler/rustc_mir_build/src/build/matches/test.rs
index 8ce7461747b..9d77bd063e1 100644
--- a/compiler/rustc_mir_build/src/build/matches/test.rs
+++ b/compiler/rustc_mir_build/src/build/matches/test.rs
@@ -6,13 +6,11 @@
 // the candidates based on the result.
 
 use crate::build::expr::as_place::PlaceBuilder;
-use crate::build::matches::{Candidate, MatchPair, Test, TestCase, TestKind};
+use crate::build::matches::{Candidate, MatchPair, Test, TestBranch, TestCase, TestKind};
 use crate::build::Builder;
 use rustc_data_structures::fx::FxIndexMap;
 use rustc_hir::{LangItem, RangeEnd};
-use rustc_index::bit_set::BitSet;
 use rustc_middle::mir::*;
-use rustc_middle::thir::*;
 use rustc_middle::ty::util::IntTypeExt;
 use rustc_middle::ty::GenericArg;
 use rustc_middle::ty::{self, adjustment::PointerCoercion, Ty, TyCtxt};
@@ -20,7 +18,6 @@ use rustc_span::def_id::DefId;
 use rustc_span::source_map::Spanned;
 use rustc_span::symbol::{sym, Symbol};
 use rustc_span::{Span, DUMMY_SP};
-use rustc_target::abi::VariantIdx;
 
 use std::cmp::Ordering;
 
@@ -30,22 +27,10 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
     /// It is a bug to call this with a not-fully-simplified pattern.
     pub(super) fn test<'pat>(&mut self, match_pair: &MatchPair<'pat, 'tcx>) -> Test<'tcx> {
         let kind = match match_pair.test_case {
-            TestCase::Variant { adt_def, variant_index: _ } => {
-                TestKind::Switch { adt_def, variants: BitSet::new_empty(adt_def.variants().len()) }
-            }
+            TestCase::Variant { adt_def, variant_index: _ } => TestKind::Switch { adt_def },
 
             TestCase::Constant { .. } if match_pair.pattern.ty.is_bool() => TestKind::If,
-
-            TestCase::Constant { .. } if is_switch_ty(match_pair.pattern.ty) => {
-                // For integers, we use a `SwitchInt` match, which allows
-                // us to handle more cases.
-                TestKind::SwitchInt {
-                    // these maps are empty to start; cases are
-                    // added below in add_cases_to_switch
-                    options: Default::default(),
-                }
-            }
-
+            TestCase::Constant { .. } if is_switch_ty(match_pair.pattern.ty) => TestKind::SwitchInt,
             TestCase::Constant { value } => TestKind::Eq { value, ty: match_pair.pattern.ty },
 
             TestCase::Range(range) => {
@@ -70,101 +55,38 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
         Test { span: match_pair.pattern.span, kind }
     }
 
-    pub(super) fn add_cases_to_switch<'pat>(
-        &mut self,
-        test_place: &PlaceBuilder<'tcx>,
-        candidate: &Candidate<'pat, 'tcx>,
-        options: &mut FxIndexMap<Const<'tcx>, u128>,
-    ) -> bool {
-        let Some(match_pair) = candidate.match_pairs.iter().find(|mp| mp.place == *test_place)
-        else {
-            return false;
-        };
-
-        match match_pair.test_case {
-            TestCase::Constant { value } => {
-                options.entry(value).or_insert_with(|| value.eval_bits(self.tcx, self.param_env));
-                true
-            }
-            TestCase::Variant { .. } => {
-                panic!("you should have called add_variants_to_switch instead!");
-            }
-            TestCase::Range(ref range) => {
-                // Check that none of the switch values are in the range.
-                self.values_not_contained_in_range(&*range, options).unwrap_or(false)
-            }
-            // don't know how to add these patterns to a switch
-            _ => false,
-        }
-    }
-
-    pub(super) fn add_variants_to_switch<'pat>(
-        &mut self,
-        test_place: &PlaceBuilder<'tcx>,
-        candidate: &Candidate<'pat, 'tcx>,
-        variants: &mut BitSet<VariantIdx>,
-    ) -> bool {
-        let Some(match_pair) = candidate.match_pairs.iter().find(|mp| mp.place == *test_place)
-        else {
-            return false;
-        };
-
-        match match_pair.test_case {
-            TestCase::Variant { variant_index, .. } => {
-                // We have a pattern testing for variant `variant_index`
-                // set the corresponding index to true
-                variants.insert(variant_index);
-                true
-            }
-            // don't know how to add these patterns to a switch
-            _ => false,
-        }
-    }
-
     #[instrument(skip(self, target_blocks, place_builder), level = "debug")]
     pub(super) fn perform_test(
         &mut self,
         match_start_span: Span,
         scrutinee_span: Span,
         block: BasicBlock,
+        otherwise_block: BasicBlock,
         place_builder: &PlaceBuilder<'tcx>,
         test: &Test<'tcx>,
-        target_blocks: Vec<BasicBlock>,
+        target_blocks: FxIndexMap<TestBranch<'tcx>, BasicBlock>,
     ) {
         let place = place_builder.to_place(self);
         let place_ty = place.ty(&self.local_decls, self.tcx);
-        debug!(?place, ?place_ty,);
+        debug!(?place, ?place_ty);
+        let target_block = |branch| target_blocks.get(&branch).copied().unwrap_or(otherwise_block);
 
         let source_info = self.source_info(test.span);
         match test.kind {
-            TestKind::Switch { adt_def, ref variants } => {
-                // Variants is a BitVec of indexes into adt_def.variants.
-                let num_enum_variants = adt_def.variants().len();
-                debug_assert_eq!(target_blocks.len(), num_enum_variants + 1);
-                let otherwise_block = *target_blocks.last().unwrap();
-                let tcx = self.tcx;
+            TestKind::Switch { adt_def } => {
+                let otherwise_block = target_block(TestBranch::Failure);
                 let switch_targets = SwitchTargets::new(
-                    adt_def.discriminants(tcx).filter_map(|(idx, discr)| {
-                        if variants.contains(idx) {
-                            debug_assert_ne!(
-                                target_blocks[idx.index()],
-                                otherwise_block,
-                                "no candidates for tested discriminant: {discr:?}",
-                            );
-                            Some((discr.val, target_blocks[idx.index()]))
+                    adt_def.discriminants(self.tcx).filter_map(|(idx, discr)| {
+                        if let Some(&block) = target_blocks.get(&TestBranch::Variant(idx)) {
+                            Some((discr.val, block))
                         } else {
-                            debug_assert_eq!(
-                                target_blocks[idx.index()],
-                                otherwise_block,
-                                "found candidates for untested discriminant: {discr:?}",
-                            );
                             None
                         }
                     }),
                     otherwise_block,
                 );
-                debug!("num_enum_variants: {}, variants: {:?}", num_enum_variants, variants);
-                let discr_ty = adt_def.repr().discr_type().to_ty(tcx);
+                debug!("num_enum_variants: {}", adt_def.variants().len());
+                let discr_ty = adt_def.repr().discr_type().to_ty(self.tcx);
                 let discr = self.temp(discr_ty, test.span);
                 self.cfg.push_assign(
                     block,
@@ -182,12 +104,17 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                 );
             }
 
-            TestKind::SwitchInt { ref options } => {
+            TestKind::SwitchInt => {
                 // The switch may be inexhaustive so we have a catch-all block
-                debug_assert_eq!(options.len() + 1, target_blocks.len());
-                let otherwise_block = *target_blocks.last().unwrap();
+                let otherwise_block = target_block(TestBranch::Failure);
                 let switch_targets = SwitchTargets::new(
-                    options.values().copied().zip(target_blocks),
+                    target_blocks.iter().filter_map(|(&branch, &block)| {
+                        if let TestBranch::Constant(_, bits) = branch {
+                            Some((bits, block))
+                        } else {
+                            None
+                        }
+                    }),
                     otherwise_block,
                 );
                 let terminator = TerminatorKind::SwitchInt {
@@ -198,18 +125,17 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
             }
 
             TestKind::If => {
-                let [false_bb, true_bb] = *target_blocks else {
-                    bug!("`TestKind::If` should have two targets")
-                };
-                let terminator = TerminatorKind::if_(Operand::Copy(place), true_bb, false_bb);
+                let success_block = target_block(TestBranch::Success);
+                let fail_block = target_block(TestBranch::Failure);
+                let terminator =
+                    TerminatorKind::if_(Operand::Copy(place), success_block, fail_block);
                 self.cfg.terminate(block, self.source_info(match_start_span), terminator);
             }
 
             TestKind::Eq { value, ty } => {
                 let tcx = self.tcx;
-                let [success_block, fail_block] = *target_blocks else {
-                    bug!("`TestKind::Eq` should have two target blocks")
-                };
+                let success_block = target_block(TestBranch::Success);
+                let fail_block = target_block(TestBranch::Failure);
                 if let ty::Adt(def, _) = ty.kind()
                     && Some(def.did()) == tcx.lang_items().string()
                 {
@@ -286,9 +212,8 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
             }
 
             TestKind::Range(ref range) => {
-                let [success, fail] = *target_blocks else {
-                    bug!("`TestKind::Range` should have two target blocks");
-                };
+                let success = target_block(TestBranch::Success);
+                let fail = target_block(TestBranch::Failure);
                 // Test `val` by computing `lo <= val && val <= hi`, using primitive comparisons.
                 let val = Operand::Copy(place);
 
@@ -333,15 +258,14 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                 // expected = <N>
                 let expected = self.push_usize(block, source_info, len);
 
-                let [true_bb, false_bb] = *target_blocks else {
-                    bug!("`TestKind::Len` should have two target blocks");
-                };
+                let success_block = target_block(TestBranch::Success);
+                let fail_block = target_block(TestBranch::Failure);
                 // result = actual == expected OR result = actual < expected
                 // branch based on result
                 self.compare(
                     block,
-                    true_bb,
-                    false_bb,
+                    success_block,
+                    fail_block,
                     source_info,
                     op,
                     Operand::Move(actual),
@@ -526,10 +450,8 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
 
     /// Given that we are performing `test` against `test_place`, this job
     /// sorts out what the status of `candidate` will be after the test. See
-    /// `test_candidates` for the usage of this function. The returned index is
-    /// the index that this candidate should be placed in the
-    /// `target_candidates` vec. The candidate may be modified to update its
-    /// `match_pairs`.
+    /// `test_candidates` for the usage of this function. The candidate may
+    /// be modified to update its `match_pairs`.
     ///
     /// So, for example, if this candidate is `x @ Some(P0)` and the `Test` is
     /// a variant test, then we would modify the candidate to be `(x as
@@ -551,12 +473,13 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
     /// that it *doesn't* apply. For now, we return false, indicate that the
     /// test does not apply to this candidate, but it might be we can get
     /// tighter match code if we do something a bit different.
-    pub(super) fn sort_candidate<'pat>(
+    pub(super) fn sort_candidate(
         &mut self,
         test_place: &PlaceBuilder<'tcx>,
         test: &Test<'tcx>,
-        candidate: &mut Candidate<'pat, 'tcx>,
-    ) -> Option<usize> {
+        candidate: &mut Candidate<'_, 'tcx>,
+        sorted_candidates: &FxIndexMap<TestBranch<'tcx>, Vec<&mut Candidate<'_, 'tcx>>>,
+    ) -> Option<TestBranch<'tcx>> {
         // Find the match_pair for this place (if any). At present,
         // afaik, there can be at most one. (In the future, if we
         // adopted a more general `@` operator, there might be more
@@ -571,12 +494,12 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
             // If we are performing a variant switch, then this
             // informs variant patterns, but nothing else.
             (
-                &TestKind::Switch { adt_def: tested_adt_def, .. },
+                &TestKind::Switch { adt_def: tested_adt_def },
                 &TestCase::Variant { adt_def, variant_index },
             ) => {
                 assert_eq!(adt_def, tested_adt_def);
                 fully_matched = true;
-                Some(variant_index.as_usize())
+                Some(TestBranch::Variant(variant_index))
             }
 
             // If we are performing a switch over integers, then this informs integer
@@ -584,35 +507,54 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
             //
             // FIXME(#29623) we could use PatKind::Range to rule
             // things out here, in some cases.
-            (TestKind::SwitchInt { options }, TestCase::Constant { value })
+            (TestKind::SwitchInt, &TestCase::Constant { value })
                 if is_switch_ty(match_pair.pattern.ty) =>
             {
-                fully_matched = true;
-                let index = options.get_index_of(value).unwrap();
-                Some(index)
+                // Beware: there might be some ranges sorted into the failure case; we must not add
+                // a success case that could be matched by one of these ranges.
+                let is_covering_range = |test_case: &TestCase<'_, 'tcx>| {
+                    test_case.as_range().is_some_and(|range| {
+                        matches!(range.contains(value, self.tcx, self.param_env), None | Some(true))
+                    })
+                };
+                let is_conflicting_candidate = |candidate: &&mut Candidate<'_, 'tcx>| {
+                    candidate
+                        .match_pairs
+                        .iter()
+                        .any(|mp| mp.place == *test_place && is_covering_range(&mp.test_case))
+                };
+                if sorted_candidates
+                    .get(&TestBranch::Failure)
+                    .is_some_and(|candidates| candidates.iter().any(is_conflicting_candidate))
+                {
+                    fully_matched = false;
+                    None
+                } else {
+                    fully_matched = true;
+                    let bits = value.eval_bits(self.tcx, self.param_env);
+                    Some(TestBranch::Constant(value, bits))
+                }
             }
-            (TestKind::SwitchInt { options }, TestCase::Range(range)) => {
+            (TestKind::SwitchInt, TestCase::Range(range)) => {
                 fully_matched = false;
                 let not_contained =
-                    self.values_not_contained_in_range(&*range, options).unwrap_or(false);
+                    sorted_candidates.keys().filter_map(|br| br.as_constant()).copied().all(
+                        |val| matches!(range.contains(val, self.tcx, self.param_env), Some(false)),
+                    );
 
                 not_contained.then(|| {
                     // No switch values are contained in the pattern range,
                     // so the pattern can be matched only if this test fails.
-                    options.len()
+                    TestBranch::Failure
                 })
             }
 
-            (&TestKind::If, TestCase::Constant { value }) => {
+            (TestKind::If, TestCase::Constant { value }) => {
                 fully_matched = true;
                 let value = value.try_eval_bool(self.tcx, self.param_env).unwrap_or_else(|| {
                     span_bug!(test.span, "expected boolean value but got {value:?}")
                 });
-                Some(value as usize)
-            }
-            (&TestKind::If, _) => {
-                fully_matched = false;
-                None
+                Some(if value { TestBranch::Success } else { TestBranch::Failure })
             }
 
             (
@@ -624,14 +566,14 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                         // on true, min_len = len = $actual_length,
                         // on false, len != $actual_length
                         fully_matched = true;
-                        Some(0)
+                        Some(TestBranch::Success)
                     }
                     (Ordering::Less, _) => {
                         // test_len < pat_len. If $actual_len = test_len,
                         // then $actual_len < pat_len and we don't have
                         // enough elements.
                         fully_matched = false;
-                        Some(1)
+                        Some(TestBranch::Failure)
                     }
                     (Ordering::Equal | Ordering::Greater, true) => {
                         // This can match both if $actual_len = test_len >= pat_len,
@@ -643,7 +585,7 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                         // test_len != pat_len, so if $actual_len = test_len, then
                         // $actual_len != pat_len.
                         fully_matched = false;
-                        Some(1)
+                        Some(TestBranch::Failure)
                     }
                 }
             }
@@ -657,20 +599,20 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                         // $actual_len >= test_len = pat_len,
                         // so we can match.
                         fully_matched = true;
-                        Some(0)
+                        Some(TestBranch::Success)
                     }
                     (Ordering::Less, _) | (Ordering::Equal, false) => {
                         // test_len <= pat_len. If $actual_len < test_len,
                         // then it is also < pat_len, so the test passing is
                         // necessary (but insufficient).
                         fully_matched = false;
-                        Some(0)
+                        Some(TestBranch::Success)
                     }
                     (Ordering::Greater, false) => {
                         // test_len > pat_len. If $actual_len >= test_len > pat_len,
                         // then we know we won't have a match.
                         fully_matched = false;
-                        Some(1)
+                        Some(TestBranch::Failure)
                     }
                     (Ordering::Greater, true) => {
                         // test_len < pat_len, and is therefore less
@@ -684,12 +626,16 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
             (TestKind::Range(test), &TestCase::Range(pat)) => {
                 if test.as_ref() == pat {
                     fully_matched = true;
-                    Some(0)
+                    Some(TestBranch::Success)
                 } else {
                     fully_matched = false;
                     // If the testing range does not overlap with pattern range,
                     // the pattern can be matched only if this test fails.
-                    if !test.overlaps(pat, self.tcx, self.param_env)? { Some(1) } else { None }
+                    if !test.overlaps(pat, self.tcx, self.param_env)? {
+                        Some(TestBranch::Failure)
+                    } else {
+                        None
+                    }
                 }
             }
             (TestKind::Range(range), &TestCase::Constant { value }) => {
@@ -697,7 +643,7 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                 if !range.contains(value, self.tcx, self.param_env)? {
                     // `value` is not contained in the testing range,
                     // so `value` can be matched only if this test fails.
-                    Some(1)
+                    Some(TestBranch::Failure)
                 } else {
                     None
                 }
@@ -708,12 +654,13 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
                 if test_val == case_val =>
             {
                 fully_matched = true;
-                Some(0)
+                Some(TestBranch::Success)
             }
 
             (
                 TestKind::Switch { .. }
                 | TestKind::SwitchInt { .. }
+                | TestKind::If
                 | TestKind::Len { .. }
                 | TestKind::Range { .. }
                 | TestKind::Eq { .. },
@@ -734,36 +681,6 @@ impl<'a, 'tcx> Builder<'a, 'tcx> {
 
         ret
     }
-
-    fn values_not_contained_in_range(
-        &self,
-        range: &PatRange<'tcx>,
-        options: &FxIndexMap<Const<'tcx>, u128>,
-    ) -> Option<bool> {
-        for &val in options.keys() {
-            if range.contains(val, self.tcx, self.param_env)? {
-                return Some(false);
-            }
-        }
-
-        Some(true)
-    }
-}
-
-impl Test<'_> {
-    pub(super) fn targets(&self) -> usize {
-        match self.kind {
-            TestKind::Eq { .. } | TestKind::Range(_) | TestKind::Len { .. } | TestKind::If => 2,
-            TestKind::Switch { adt_def, .. } => {
-                // While the switch that we generate doesn't test for all
-                // variants, we have a target for each variant and the
-                // otherwise case, and we make sure that all of the cases not
-                // specified have the same block.
-                adt_def.variants().len() + 1
-            }
-            TestKind::SwitchInt { ref options } => options.len() + 1,
-        }
-    }
 }
 
 fn is_switch_ty(ty: Ty<'_>) -> bool {
diff --git a/tests/mir-opt/building/match_false_edges.full_tested_match.built.after.mir b/tests/mir-opt/building/match_false_edges.full_tested_match.built.after.mir
index 4e91eb6f76f..194afdf7dd8 100644
--- a/tests/mir-opt/building/match_false_edges.full_tested_match.built.after.mir
+++ b/tests/mir-opt/building/match_false_edges.full_tested_match.built.after.mir
@@ -28,7 +28,7 @@ fn full_tested_match() -> () {
         _2 = Option::<i32>::Some(const 42_i32);
         PlaceMention(_2);
         _3 = discriminant(_2);
-        switchInt(move _3) -> [0: bb2, 1: bb4, otherwise: bb1];
+        switchInt(move _3) -> [0: bb5, 1: bb2, otherwise: bb1];
     }
 
     bb1: {
@@ -37,20 +37,20 @@ fn full_tested_match() -> () {
     }
 
     bb2: {
-        _1 = (const 3_i32, const 3_i32);
-        goto -> bb13;
+        falseEdge -> [real: bb7, imaginary: bb3];
     }
 
     bb3: {
-        goto -> bb1;
+        falseEdge -> [real: bb12, imaginary: bb5];
     }
 
     bb4: {
-        falseEdge -> [real: bb7, imaginary: bb5];
+        goto -> bb1;
     }
 
     bb5: {
-        falseEdge -> [real: bb12, imaginary: bb2];
+        _1 = (const 3_i32, const 3_i32);
+        goto -> bb13;
     }
 
     bb6: {
@@ -91,7 +91,7 @@ fn full_tested_match() -> () {
     bb11: {
         StorageDead(_7);
         StorageDead(_6);
-        goto -> bb5;
+        goto -> bb3;
     }
 
     bb12: {
diff --git a/tests/mir-opt/building/match_false_edges.full_tested_match2.built.after.mir b/tests/mir-opt/building/match_false_edges.full_tested_match2.built.after.mir
index 0c67cc9f71e..ae83075434f 100644
--- a/tests/mir-opt/building/match_false_edges.full_tested_match2.built.after.mir
+++ b/tests/mir-opt/building/match_false_edges.full_tested_match2.built.after.mir
@@ -28,7 +28,7 @@ fn full_tested_match2() -> () {
         _2 = Option::<i32>::Some(const 42_i32);
         PlaceMention(_2);
         _3 = discriminant(_2);
-        switchInt(move _3) -> [0: bb2, 1: bb4, otherwise: bb1];
+        switchInt(move _3) -> [0: bb5, 1: bb2, otherwise: bb1];
     }
 
     bb1: {
@@ -37,18 +37,10 @@ fn full_tested_match2() -> () {
     }
 
     bb2: {
-        falseEdge -> [real: bb12, imaginary: bb5];
+        falseEdge -> [real: bb7, imaginary: bb5];
     }
 
     bb3: {
-        goto -> bb1;
-    }
-
-    bb4: {
-        falseEdge -> [real: bb7, imaginary: bb2];
-    }
-
-    bb5: {
         StorageLive(_9);
         _9 = ((_2 as Some).0: i32);
         StorageLive(_10);
@@ -59,6 +51,14 @@ fn full_tested_match2() -> () {
         goto -> bb13;
     }
 
+    bb4: {
+        goto -> bb1;
+    }
+
+    bb5: {
+        falseEdge -> [real: bb12, imaginary: bb3];
+    }
+
     bb6: {
         goto -> bb1;
     }
@@ -97,7 +97,7 @@ fn full_tested_match2() -> () {
     bb11: {
         StorageDead(_7);
         StorageDead(_6);
-        falseEdge -> [real: bb5, imaginary: bb2];
+        falseEdge -> [real: bb3, imaginary: bb5];
     }
 
     bb12: {
diff --git a/tests/mir-opt/early_otherwise_branch.opt2.EarlyOtherwiseBranch.diff b/tests/mir-opt/early_otherwise_branch.opt2.EarlyOtherwiseBranch.diff
index 95bcfe71792..1348bdd739a 100644
--- a/tests/mir-opt/early_otherwise_branch.opt2.EarlyOtherwiseBranch.diff
+++ b/tests/mir-opt/early_otherwise_branch.opt2.EarlyOtherwiseBranch.diff
@@ -30,7 +30,7 @@
           StorageDead(_5);
           StorageDead(_4);
           _8 = discriminant((_3.0: std::option::Option<u32>));
--         switchInt(move _8) -> [0: bb2, 1: bb3, otherwise: bb1];
+-         switchInt(move _8) -> [0: bb3, 1: bb2, otherwise: bb1];
 +         StorageLive(_11);
 +         _11 = discriminant((_3.1: std::option::Option<u32>));
 +         StorageLive(_12);
@@ -48,12 +48,12 @@
   
       bb2: {
 -         _6 = discriminant((_3.1: std::option::Option<u32>));
--         switchInt(move _6) -> [0: bb5, otherwise: bb1];
+-         switchInt(move _6) -> [1: bb4, otherwise: bb1];
 -     }
 - 
 -     bb3: {
 -         _7 = discriminant((_3.1: std::option::Option<u32>));
--         switchInt(move _7) -> [1: bb4, otherwise: bb1];
+-         switchInt(move _7) -> [0: bb5, otherwise: bb1];
 -     }
 - 
 -     bb4: {
diff --git a/tests/mir-opt/early_otherwise_branch_noopt.noopt1.EarlyOtherwiseBranch.diff b/tests/mir-opt/early_otherwise_branch_noopt.noopt1.EarlyOtherwiseBranch.diff
index 7fdd8554e38..350e5fe6db5 100644
--- a/tests/mir-opt/early_otherwise_branch_noopt.noopt1.EarlyOtherwiseBranch.diff
+++ b/tests/mir-opt/early_otherwise_branch_noopt.noopt1.EarlyOtherwiseBranch.diff
@@ -36,7 +36,7 @@
           StorageDead(_5);
           StorageDead(_4);
           _8 = discriminant((_3.0: std::option::Option<u32>));
-          switchInt(move _8) -> [0: bb2, 1: bb4, otherwise: bb1];
+          switchInt(move _8) -> [0: bb3, 1: bb2, otherwise: bb1];
       }
   
       bb1: {
@@ -45,17 +45,17 @@
   
       bb2: {
           _6 = discriminant((_3.1: std::option::Option<u32>));
-          switchInt(move _6) -> [0: bb3, 1: bb7, otherwise: bb1];
+          switchInt(move _6) -> [0: bb6, 1: bb5, otherwise: bb1];
       }
   
       bb3: {
-          _0 = const 3_u32;
-          goto -> bb8;
+          _7 = discriminant((_3.1: std::option::Option<u32>));
+          switchInt(move _7) -> [0: bb4, 1: bb7, otherwise: bb1];
       }
   
       bb4: {
-          _7 = discriminant((_3.1: std::option::Option<u32>));
-          switchInt(move _7) -> [0: bb6, 1: bb5, otherwise: bb1];
+          _0 = const 3_u32;
+          goto -> bb8;
       }
   
       bb5: {
diff --git a/tests/mir-opt/match_arm_scopes.complicated_match.panic-abort.SimplifyCfg-initial.after-ElaborateDrops.after.diff b/tests/mir-opt/match_arm_scopes.complicated_match.panic-abort.SimplifyCfg-initial.after-ElaborateDrops.after.diff
index 619fda339a6..307f7105dd2 100644
--- a/tests/mir-opt/match_arm_scopes.complicated_match.panic-abort.SimplifyCfg-initial.after-ElaborateDrops.after.diff
+++ b/tests/mir-opt/match_arm_scopes.complicated_match.panic-abort.SimplifyCfg-initial.after-ElaborateDrops.after.diff
@@ -42,11 +42,15 @@
       }
   
       bb2: {
--         switchInt((_2.0: bool)) -> [0: bb3, otherwise: bb4];
+-         switchInt((_2.0: bool)) -> [0: bb4, otherwise: bb3];
 +         switchInt((_2.0: bool)) -> [0: bb3, otherwise: bb17];
       }
   
       bb3: {
+-         falseEdge -> [real: bb20, imaginary: bb4];
+-     }
+- 
+-     bb4: {
           StorageLive(_15);
           _15 = (_2.1: bool);
           StorageLive(_16);
@@ -55,12 +59,8 @@
 +         goto -> bb16;
       }
   
-      bb4: {
--         falseEdge -> [real: bb20, imaginary: bb3];
--     }
-- 
 -     bb5: {
--         falseEdge -> [real: bb13, imaginary: bb4];
+-         falseEdge -> [real: bb13, imaginary: bb3];
 -     }
 - 
 -     bb6: {
@@ -68,6 +68,7 @@
 -     }
 - 
 -     bb7: {
++     bb4: {
           _0 = const 1_i32;
 -         drop(_7) -> [return: bb18, unwind: bb25];
 +         drop(_7) -> [return: bb15, unwind: bb22];
@@ -183,7 +184,7 @@
           StorageDead(_12);
           StorageDead(_8);
           StorageDead(_6);
--         falseEdge -> [real: bb2, imaginary: bb4];
+-         falseEdge -> [real: bb2, imaginary: bb3];
 +         goto -> bb2;
       }
   
diff --git a/tests/mir-opt/match_arm_scopes.complicated_match.panic-unwind.SimplifyCfg-initial.after-ElaborateDrops.after.diff b/tests/mir-opt/match_arm_scopes.complicated_match.panic-unwind.SimplifyCfg-initial.after-ElaborateDrops.after.diff
index 619fda339a6..307f7105dd2 100644
--- a/tests/mir-opt/match_arm_scopes.complicated_match.panic-unwind.SimplifyCfg-initial.after-ElaborateDrops.after.diff
+++ b/tests/mir-opt/match_arm_scopes.complicated_match.panic-unwind.SimplifyCfg-initial.after-ElaborateDrops.after.diff
@@ -42,11 +42,15 @@
       }
   
       bb2: {
--         switchInt((_2.0: bool)) -> [0: bb3, otherwise: bb4];
+-         switchInt((_2.0: bool)) -> [0: bb4, otherwise: bb3];
 +         switchInt((_2.0: bool)) -> [0: bb3, otherwise: bb17];
       }
   
       bb3: {
+-         falseEdge -> [real: bb20, imaginary: bb4];
+-     }
+- 
+-     bb4: {
           StorageLive(_15);
           _15 = (_2.1: bool);
           StorageLive(_16);
@@ -55,12 +59,8 @@
 +         goto -> bb16;
       }
   
-      bb4: {
--         falseEdge -> [real: bb20, imaginary: bb3];
--     }
-- 
 -     bb5: {
--         falseEdge -> [real: bb13, imaginary: bb4];
+-         falseEdge -> [real: bb13, imaginary: bb3];
 -     }
 - 
 -     bb6: {
@@ -68,6 +68,7 @@
 -     }
 - 
 -     bb7: {
++     bb4: {
           _0 = const 1_i32;
 -         drop(_7) -> [return: bb18, unwind: bb25];
 +         drop(_7) -> [return: bb15, unwind: bb22];
@@ -183,7 +184,7 @@
           StorageDead(_12);
           StorageDead(_8);
           StorageDead(_6);
--         falseEdge -> [real: bb2, imaginary: bb4];
+-         falseEdge -> [real: bb2, imaginary: bb3];
 +         goto -> bb2;
       }
   
diff --git a/tests/ui/pattern/usefulness/integer-ranges/regression-switchint-sorting-with-ranges.rs b/tests/ui/pattern/usefulness/integer-ranges/regression-switchint-sorting-with-ranges.rs
new file mode 100644
index 00000000000..bacb60a108b
--- /dev/null
+++ b/tests/ui/pattern/usefulness/integer-ranges/regression-switchint-sorting-with-ranges.rs
@@ -0,0 +1,14 @@
+//@ run-pass
+//
+// Regression test for match lowering to MIR: when gathering candidates, by the time we get to the
+// range we know the range will only match on the failure case of the switchint. Hence we mustn't
+// add the `1` to the switchint or the range would be incorrectly sorted.
+#![allow(unreachable_patterns)]
+fn main() {
+    match 1 {
+        10 => unreachable!(),
+        0..=5 => {}
+        1 => unreachable!(),
+        _ => unreachable!(),
+    }
+}