Auto merge of #113970 - cjgillot:assume-all-the-things, r=nikic

Replace switch to unreachable by assume statements

`UnreachablePropagation` currently keeps some switch terminators alive in order to ensure codegen can infer the inequalities on the discriminants.

This PR proposes to encode those inequalities as `Assume` statements.

This allows to simplify MIR further by removing some useless terminators.

4 files changed, 183 insertions, 146 deletions

diff --git a/compiler/rustc_mir_transform/src/lib.rs b/compiler/rustc_mir_transform/src/lib.rs
index dc35381fe22..bf5f0ca7cbd 100644
--- a/compiler/rustc_mir_transform/src/lib.rs
+++ b/compiler/rustc_mir_transform/src/lib.rs
@@ -568,10 +568,11 @@ fn run_optimization_passes<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
         &[
             &check_alignment::CheckAlignment,
             &lower_slice_len::LowerSliceLenCalls, // has to be done before inlining, otherwise actual call will be almost always inlined. Also simple, so can just do first
-            &unreachable_prop::UnreachablePropagation,
+            &inline::Inline,
+            // Substitutions during inlining may introduce switch on enums with uninhabited branches.
             &uninhabited_enum_branching::UninhabitedEnumBranching,
+            &unreachable_prop::UnreachablePropagation,
             &o1(simplify::SimplifyCfg::AfterUninhabitedEnumBranching),
-            &inline::Inline,
             &remove_storage_markers::RemoveStorageMarkers,
             &remove_zsts::RemoveZsts,
             &normalize_array_len::NormalizeArrayLen, // has to run after `slice::len` lowering
diff --git a/compiler/rustc_mir_transform/src/simplify_branches.rs b/compiler/rustc_mir_transform/src/simplify_branches.rs
index b508cd1c9cc..1f0e605c3b8 100644
--- a/compiler/rustc_mir_transform/src/simplify_branches.rs
+++ b/compiler/rustc_mir_transform/src/simplify_branches.rs
@@ -16,8 +16,25 @@ impl<'tcx> MirPass<'tcx> for SimplifyConstCondition {
     }
 
     fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
+        trace!("Running SimplifyConstCondition on {:?}", body.source);
         let param_env = tcx.param_env_reveal_all_normalized(body.source.def_id());
-        for block in body.basic_blocks_mut() {
+        'blocks: for block in body.basic_blocks_mut() {
+            for stmt in block.statements.iter_mut() {
+                if let StatementKind::Intrinsic(box ref intrinsic) = stmt.kind
+                    && let NonDivergingIntrinsic::Assume(discr) = intrinsic
+                    && let Operand::Constant(ref c) = discr
+                    && let Some(constant) = c.const_.try_eval_bool(tcx, param_env)
+                {
+                    if constant {
+                        stmt.make_nop();
+                    } else {
+                        block.statements.clear();
+                        block.terminator_mut().kind = TerminatorKind::Unreachable;
+                        continue 'blocks;
+                    }
+                }
+            }
+
             let terminator = block.terminator_mut();
             terminator.kind = match terminator.kind {
                 TerminatorKind::SwitchInt {
diff --git a/compiler/rustc_mir_transform/src/uninhabited_enum_branching.rs b/compiler/rustc_mir_transform/src/uninhabited_enum_branching.rs
index cb028a92d49..98f67e18a8d 100644
--- a/compiler/rustc_mir_transform/src/uninhabited_enum_branching.rs
+++ b/compiler/rustc_mir_transform/src/uninhabited_enum_branching.rs
@@ -3,8 +3,7 @@
 use crate::MirPass;
 use rustc_data_structures::fx::FxHashSet;
 use rustc_middle::mir::{
-    BasicBlockData, Body, Local, Operand, Rvalue, StatementKind, SwitchTargets, Terminator,
-    TerminatorKind,
+    BasicBlockData, Body, Local, Operand, Rvalue, StatementKind, Terminator, TerminatorKind,
 };
 use rustc_middle::ty::layout::TyAndLayout;
 use rustc_middle::ty::{Ty, TyCtxt};
@@ -30,17 +29,20 @@ fn get_switched_on_type<'tcx>(
     let terminator = block_data.terminator();
 
     // Only bother checking blocks which terminate by switching on a local.
-    if let Some(local) = get_discriminant_local(&terminator.kind)
-        && let [.., stmt_before_term] = &block_data.statements[..]
-        && let StatementKind::Assign(box (l, Rvalue::Discriminant(place))) = stmt_before_term.kind
+    let local = get_discriminant_local(&terminator.kind)?;
+
+    let stmt_before_term = block_data.statements.last()?;
+
+    if let StatementKind::Assign(box (l, Rvalue::Discriminant(place))) = stmt_before_term.kind
         && l.as_local() == Some(local)
-        && let ty = place.ty(body, tcx).ty
-        && ty.is_enum()
     {
-        Some(ty)
-    } else {
-        None
+        let ty = place.ty(body, tcx).ty;
+        if ty.is_enum() {
+            return Some(ty);
+        }
     }
+
+    None
 }
 
 fn variant_discriminants<'tcx>(
@@ -67,28 +69,6 @@ fn variant_discriminants<'tcx>(
     }
 }
 
-/// Ensures that the `otherwise` branch leads to an unreachable bb, returning `None` if so and a new
-/// bb to use as the new target if not.
-fn ensure_otherwise_unreachable<'tcx>(
-    body: &Body<'tcx>,
-    targets: &SwitchTargets,
-) -> Option<BasicBlockData<'tcx>> {
-    let otherwise = targets.otherwise();
-    let bb = &body.basic_blocks[otherwise];
-    if bb.terminator().kind == TerminatorKind::Unreachable
-        && bb.statements.iter().all(|s| matches!(&s.kind, StatementKind::StorageDead(_)))
-    {
-        return None;
-    }
-
-    let mut new_block = BasicBlockData::new(Some(Terminator {
-        source_info: bb.terminator().source_info,
-        kind: TerminatorKind::Unreachable,
-    }));
-    new_block.is_cleanup = bb.is_cleanup;
-    Some(new_block)
-}
-
 impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
     fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
         sess.mir_opt_level() > 0
@@ -97,13 +77,16 @@ impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
     fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
         trace!("UninhabitedEnumBranching starting for {:?}", body.source);
 
-        for bb in body.basic_blocks.indices() {
+        let mut removable_switchs = Vec::new();
+
+        for (bb, bb_data) in body.basic_blocks.iter_enumerated() {
             trace!("processing block {:?}", bb);
 
-            let Some(discriminant_ty) = get_switched_on_type(&body.basic_blocks[bb], tcx, body)
-            else {
+            if bb_data.is_cleanup {
                 continue;
-            };
+            }
+
+            let Some(discriminant_ty) = get_switched_on_type(&bb_data, tcx, body) else { continue };
 
             let layout = tcx.layout_of(
                 tcx.param_env_reveal_all_normalized(body.source.def_id()).and(discriminant_ty),
@@ -117,31 +100,38 @@ impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
 
             trace!("allowed_variants = {:?}", allowed_variants);
 
-            if let TerminatorKind::SwitchInt { targets, .. } =
-                &mut body.basic_blocks_mut()[bb].terminator_mut().kind
-            {
-                let mut new_targets = SwitchTargets::new(
-                    targets.iter().filter(|(val, _)| allowed_variants.contains(val)),
-                    targets.otherwise(),
-                );
-
-                if new_targets.iter().count() == allowed_variants.len() {
-                    if let Some(updated) = ensure_otherwise_unreachable(body, &new_targets) {
-                        let new_otherwise = body.basic_blocks_mut().push(updated);
-                        *new_targets.all_targets_mut().last_mut().unwrap() = new_otherwise;
-                    }
-                }
+            let terminator = bb_data.terminator();
+            let TerminatorKind::SwitchInt { targets, .. } = &terminator.kind else { bug!() };
 
-                if let TerminatorKind::SwitchInt { targets, .. } =
-                    &mut body.basic_blocks_mut()[bb].terminator_mut().kind
-                {
-                    *targets = new_targets;
+            let mut reachable_count = 0;
+            for (index, (val, _)) in targets.iter().enumerate() {
+                if allowed_variants.contains(&val) {
+                    reachable_count += 1;
                 } else {
-                    unreachable!()
+                    removable_switchs.push((bb, index));
                 }
-            } else {
-                unreachable!()
             }
+
+            if reachable_count == allowed_variants.len() {
+                removable_switchs.push((bb, targets.iter().count()));
+            }
+        }
+
+        if removable_switchs.is_empty() {
+            return;
+        }
+
+        let new_block = BasicBlockData::new(Some(Terminator {
+            source_info: body.basic_blocks[removable_switchs[0].0].terminator().source_info,
+            kind: TerminatorKind::Unreachable,
+        }));
+        let unreachable_block = body.basic_blocks.as_mut().push(new_block);
+
+        for (bb, index) in removable_switchs {
+            let bb = &mut body.basic_blocks.as_mut()[bb];
+            let terminator = bb.terminator_mut();
+            let TerminatorKind::SwitchInt { targets, .. } = &mut terminator.kind else { bug!() };
+            targets.all_targets_mut()[index] = unreachable_block;
         }
     }
 }
diff --git a/compiler/rustc_mir_transform/src/unreachable_prop.rs b/compiler/rustc_mir_transform/src/unreachable_prop.rs
index ea7aafd866b..919e8d6a234 100644
--- a/compiler/rustc_mir_transform/src/unreachable_prop.rs
+++ b/compiler/rustc_mir_transform/src/unreachable_prop.rs
@@ -2,11 +2,13 @@
 //! when all of their successors are unreachable. This is achieved through a
 //! post-order traversal of the blocks.
 
-use crate::simplify;
 use crate::MirPass;
-use rustc_data_structures::fx::{FxHashMap, FxHashSet};
+use rustc_data_structures::fx::FxHashSet;
+use rustc_middle::mir::interpret::Scalar;
+use rustc_middle::mir::patch::MirPatch;
 use rustc_middle::mir::*;
-use rustc_middle::ty::TyCtxt;
+use rustc_middle::ty::{self, TyCtxt};
+use rustc_target::abi::Size;
 
 pub struct UnreachablePropagation;
 
@@ -21,106 +23,133 @@ impl MirPass<'_> for UnreachablePropagation {
     }
 
     fn run_pass<'tcx>(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
+        let mut patch = MirPatch::new(body);
         let mut unreachable_blocks = FxHashSet::default();
-        let mut replacements = FxHashMap::default();
 
         for (bb, bb_data) in traversal::postorder(body) {
             let terminator = bb_data.terminator();
-            if terminator.kind == TerminatorKind::Unreachable {
-                unreachable_blocks.insert(bb);
-            } else {
-                let is_unreachable = |succ: BasicBlock| unreachable_blocks.contains(&succ);
-                let terminator_kind_opt = remove_successors(&terminator.kind, is_unreachable);
-
-                if let Some(terminator_kind) = terminator_kind_opt {
-                    if terminator_kind == TerminatorKind::Unreachable {
-                        unreachable_blocks.insert(bb);
-                    }
-                    replacements.insert(bb, terminator_kind);
+            let is_unreachable = match &terminator.kind {
+                TerminatorKind::Unreachable => true,
+                // This will unconditionally run into an unreachable and is therefore unreachable as well.
+                TerminatorKind::Goto { target } if unreachable_blocks.contains(target) => {
+                    patch.patch_terminator(bb, TerminatorKind::Unreachable);
+                    true
+                }
+                // Try to remove unreachable targets from the switch.
+                TerminatorKind::SwitchInt { .. } => {
+                    remove_successors_from_switch(tcx, bb, &unreachable_blocks, body, &mut patch)
                 }
+                _ => false,
+            };
+            if is_unreachable {
+                unreachable_blocks.insert(bb);
             }
         }
 
+        if !tcx
+            .consider_optimizing(|| format!("UnreachablePropagation {:?} ", body.source.def_id()))
+        {
+            return;
+        }
+
+        patch.apply(body);
+
         // We do want do keep some unreachable blocks, but make them empty.
         for bb in unreachable_blocks {
-            if !tcx.consider_optimizing(|| {
-                format!("UnreachablePropagation {:?} ", body.source.def_id())
-            }) {
-                break;
-            }
-
             body.basic_blocks_mut()[bb].statements.clear();
         }
+    }
+}
 
-        let replaced = !replacements.is_empty();
+/// Return whether the current terminator is fully unreachable.
+fn remove_successors_from_switch<'tcx>(
+    tcx: TyCtxt<'tcx>,
+    bb: BasicBlock,
+    unreachable_blocks: &FxHashSet<BasicBlock>,
+    body: &Body<'tcx>,
+    patch: &mut MirPatch<'tcx>,
+) -> bool {
+    let terminator = body.basic_blocks[bb].terminator();
+    let TerminatorKind::SwitchInt { discr, targets } = &terminator.kind else { bug!() };
+    let source_info = terminator.source_info;
+    let location = body.terminator_loc(bb);
+
+    let is_unreachable = |bb| unreachable_blocks.contains(&bb);
+
+    // If there are multiple targets, we want to keep information about reachability for codegen.
+    // For example (see tests/codegen/match-optimizes-away.rs)
+    //
+    // pub enum Two { A, B }
+    // pub fn identity(x: Two) -> Two {
+    //     match x {
+    //         Two::A => Two::A,
+    //         Two::B => Two::B,
+    //     }
+    // }
+    //
+    // This generates a `switchInt() -> [0: 0, 1: 1, otherwise: unreachable]`, which allows us or LLVM to
+    // turn it into just `x` later. Without the unreachable, such a transformation would be illegal.
+    //
+    // In order to preserve this information, we record reachable and unreachable targets as
+    // `Assume` statements in MIR.
+
+    let discr_ty = discr.ty(body, tcx);
+    let discr_size = Size::from_bits(match discr_ty.kind() {
+        ty::Uint(uint) => uint.normalize(tcx.sess.target.pointer_width).bit_width().unwrap(),
+        ty::Int(int) => int.normalize(tcx.sess.target.pointer_width).bit_width().unwrap(),
+        ty::Char => 32,
+        ty::Bool => 1,
+        other => bug!("unhandled type: {:?}", other),
+    });
+
+    let mut add_assumption = |binop, value| {
+        let local = patch.new_temp(tcx.types.bool, source_info.span);
+        let value = Operand::Constant(Box::new(ConstOperand {
+            span: source_info.span,
+            user_ty: None,
+            const_: Const::from_scalar(tcx, Scalar::from_uint(value, discr_size), discr_ty),
+        }));
+        let cmp = Rvalue::BinaryOp(binop, Box::new((discr.to_copy(), value)));
+        patch.add_assign(location, local.into(), cmp);
+
+        let assume = NonDivergingIntrinsic::Assume(Operand::Move(local.into()));
+        patch.add_statement(location, StatementKind::Intrinsic(Box::new(assume)));
+    };
 
-        for (bb, terminator_kind) in replacements {
-            if !tcx.consider_optimizing(|| {
-                format!("UnreachablePropagation {:?} ", body.source.def_id())
-            }) {
-                break;
-            }
+    let otherwise = targets.otherwise();
+    let otherwise_unreachable = is_unreachable(otherwise);
 
-            body.basic_blocks_mut()[bb].terminator_mut().kind = terminator_kind;
+    let reachable_iter = targets.iter().filter(|&(value, bb)| {
+        let is_unreachable = is_unreachable(bb);
+        // We remove this target from the switch, so record the inequality using `Assume`.
+        if is_unreachable && !otherwise_unreachable {
+            add_assumption(BinOp::Ne, value);
         }
-
-        if replaced {
-            simplify::remove_dead_blocks(body);
+        !is_unreachable
+    });
+
+    let new_targets = SwitchTargets::new(reachable_iter, otherwise);
+
+    let num_targets = new_targets.all_targets().len();
+    let fully_unreachable = num_targets == 1 && otherwise_unreachable;
+
+    let terminator = match (num_targets, otherwise_unreachable) {
+        // If all targets are unreachable, we can be unreachable as well.
+        (1, true) => TerminatorKind::Unreachable,
+        (1, false) => TerminatorKind::Goto { target: otherwise },
+        (2, true) => {
+            // All targets are unreachable except one. Record the equality, and make it a goto.
+            let (value, target) = new_targets.iter().next().unwrap();
+            add_assumption(BinOp::Eq, value);
+            TerminatorKind::Goto { target }
         }
-    }
-}
-
-fn remove_successors<'tcx, F>(
-    terminator_kind: &TerminatorKind<'tcx>,
-    is_unreachable: F,
-) -> Option<TerminatorKind<'tcx>>
-where
-    F: Fn(BasicBlock) -> bool,
-{
-    let terminator = match terminator_kind {
-        // This will unconditionally run into an unreachable and is therefore unreachable as well.
-        TerminatorKind::Goto { target } if is_unreachable(*target) => TerminatorKind::Unreachable,
-        TerminatorKind::SwitchInt { targets, discr } => {
-            let otherwise = targets.otherwise();
-
-            // If all targets are unreachable, we can be unreachable as well.
-            if targets.all_targets().iter().all(|bb| is_unreachable(*bb)) {
-                TerminatorKind::Unreachable
-            } else if is_unreachable(otherwise) {
-                // If there are multiple targets, don't delete unreachable branches (like an unreachable otherwise)
-                // unless otherwise is unreachable, in which case deleting a normal branch causes it to be merged with
-                // the otherwise, keeping its unreachable.
-                // This looses information about reachability causing worse codegen.
-                // For example (see tests/codegen/match-optimizes-away.rs)
-                //
-                // pub enum Two { A, B }
-                // pub fn identity(x: Two) -> Two {
-                //     match x {
-                //         Two::A => Two::A,
-                //         Two::B => Two::B,
-                //     }
-                // }
-                //
-                // This generates a `switchInt() -> [0: 0, 1: 1, otherwise: unreachable]`, which allows us or LLVM to
-                // turn it into just `x` later. Without the unreachable, such a transformation would be illegal.
-                // If the otherwise branch is unreachable, we can delete all other unreachable targets, as they will
-                // still point to the unreachable and therefore not lose reachability information.
-                let reachable_iter = targets.iter().filter(|(_, bb)| !is_unreachable(*bb));
-
-                let new_targets = SwitchTargets::new(reachable_iter, otherwise);
-
-                // No unreachable branches were removed.
-                if new_targets.all_targets().len() == targets.all_targets().len() {
-                    return None;
-                }
-
-                TerminatorKind::SwitchInt { discr: discr.clone(), targets: new_targets }
-            } else {
-                // If the otherwise branch is reachable, we don't want to delete any unreachable branches.
-                return None;
-            }
+        _ if num_targets == targets.all_targets().len() => {
+            // Nothing has changed.
+            return false;
         }
-        _ => return None,
+        _ => TerminatorKind::SwitchInt { discr: discr.clone(), targets: new_targets },
     };
-    Some(terminator)
+
+    patch.patch_terminator(bb, terminator);
+    fully_unreachable
 }