Auto merge of #122225 - DianQK:nits-120268, r=cjgillot

 Rename `UninhabitedEnumBranching` to `UnreachableEnumBranching`

Per [#120268](https://github.com/rust-lang/rust/pull/120268#discussion_r1517492060), I rename `UninhabitedEnumBranching` to `UnreachableEnumBranching` .

I solved some nits to add some comments.

I adjusted the workaround restrictions. This should be useful for `a <= b` and `if let Some/Ok(v)`. For enum with few variants, `early-tailduplication` should not cause compile time overhead.

r? RalfJung

3 files changed, 56 insertions, 14 deletions

diff --git a/compiler/rustc_mir_transform/src/lib.rs b/compiler/rustc_mir_transform/src/lib.rs
index 15988c0ea6b..a684f9bdff1 100644
--- a/compiler/rustc_mir_transform/src/lib.rs
+++ b/compiler/rustc_mir_transform/src/lib.rs
@@ -110,7 +110,7 @@ pub mod simplify;
 mod simplify_branches;
 mod simplify_comparison_integral;
 mod sroa;
-mod uninhabited_enum_branching;
+mod unreachable_enum_branching;
 mod unreachable_prop;
 
 use rustc_const_eval::transform::check_consts::{self, ConstCx};
@@ -580,9 +580,10 @@ fn run_optimization_passes<'tcx>(tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
             &remove_zsts::RemoveZsts,
             &remove_unneeded_drops::RemoveUnneededDrops,
             // Type instantiation may create uninhabited enums.
-            &uninhabited_enum_branching::UninhabitedEnumBranching,
+            // Also eliminates some unreachable branches based on variants of enums.
+            &unreachable_enum_branching::UnreachableEnumBranching,
             &unreachable_prop::UnreachablePropagation,
-            &o1(simplify::SimplifyCfg::AfterUninhabitedEnumBranching),
+            &o1(simplify::SimplifyCfg::AfterUnreachableEnumBranching),
             // Inlining may have introduced a lot of redundant code and a large move pattern.
             // Now, we need to shrink the generated MIR.
 
diff --git a/compiler/rustc_mir_transform/src/simplify.rs b/compiler/rustc_mir_transform/src/simplify.rs
index 574330cc355..14772080ce5 100644
--- a/compiler/rustc_mir_transform/src/simplify.rs
+++ b/compiler/rustc_mir_transform/src/simplify.rs
@@ -44,7 +44,7 @@ pub enum SimplifyCfg {
     PreOptimizations,
     Final,
     MakeShim,
-    AfterUninhabitedEnumBranching,
+    AfterUnreachableEnumBranching,
 }
 
 impl SimplifyCfg {
@@ -57,8 +57,8 @@ impl SimplifyCfg {
             SimplifyCfg::PreOptimizations => "SimplifyCfg-pre-optimizations",
             SimplifyCfg::Final => "SimplifyCfg-final",
             SimplifyCfg::MakeShim => "SimplifyCfg-make_shim",
-            SimplifyCfg::AfterUninhabitedEnumBranching => {
-                "SimplifyCfg-after-uninhabited-enum-branching"
+            SimplifyCfg::AfterUnreachableEnumBranching => {
+                "SimplifyCfg-after-unreachable-enum-branching"
             }
         }
     }
diff --git a/compiler/rustc_mir_transform/src/uninhabited_enum_branching.rs b/compiler/rustc_mir_transform/src/unreachable_enum_branching.rs
index 57fe46ad75a..66b6235eb93 100644
--- a/compiler/rustc_mir_transform/src/uninhabited_enum_branching.rs
+++ b/compiler/rustc_mir_transform/src/unreachable_enum_branching.rs
@@ -1,4 +1,4 @@
-//! A pass that eliminates branches on uninhabited enum variants.
+//! A pass that eliminates branches on uninhabited or unreachable enum variants.
 
 use crate::MirPass;
 use rustc_data_structures::fx::FxHashSet;
@@ -11,7 +11,7 @@ use rustc_middle::ty::layout::TyAndLayout;
 use rustc_middle::ty::{Ty, TyCtxt};
 use rustc_target::abi::{Abi, Variants};
 
-pub struct UninhabitedEnumBranching;
+pub struct UnreachableEnumBranching;
 
 fn get_discriminant_local(terminator: &TerminatorKind<'_>) -> Option<Local> {
     if let TerminatorKind::SwitchInt { discr: Operand::Move(p), .. } = terminator {
@@ -71,13 +71,13 @@ fn variant_discriminants<'tcx>(
     }
 }
 
-impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
+impl<'tcx> MirPass<'tcx> for UnreachableEnumBranching {
     fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
         sess.mir_opt_level() > 0
     }
 
     fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
-        trace!("UninhabitedEnumBranching starting for {:?}", body.source);
+        trace!("UnreachableEnumBranching starting for {:?}", body.source);
 
         let mut unreachable_targets = Vec::new();
         let mut patch = MirPatch::new(body);
@@ -96,8 +96,10 @@ impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
             );
 
             let mut allowed_variants = if let Ok(layout) = layout {
+                // Find allowed variants based on uninhabited.
                 variant_discriminants(&layout, discriminant_ty, tcx)
             } else if let Some(variant_range) = discriminant_ty.variant_range(tcx) {
+                // If there are some generics, we can still get the allowed variants.
                 variant_range
                     .map(|variant| {
                         discriminant_ty.discriminant_for_variant(tcx, variant).unwrap().val
@@ -121,9 +123,26 @@ impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
             }
             let otherwise_is_empty_unreachable =
                 body.basic_blocks[targets.otherwise()].is_empty_unreachable();
-            // After resolving https://github.com/llvm/llvm-project/issues/78578,
-            // we can remove the limit on the number of successors.
             fn check_successors(basic_blocks: &BasicBlocks<'_>, bb: BasicBlock) -> bool {
+                // After resolving https://github.com/llvm/llvm-project/issues/78578,
+                // We can remove this check.
+                // The main issue here is that `early-tailduplication` causes compile time overhead
+                // and potential performance problems.
+                // Simply put, when encounter a switch (indirect branch) statement,
+                // `early-tailduplication` tries to duplicate the switch branch statement with BB
+                // into (each) predecessors. This makes CFG very complex.
+                // We can understand it as it transforms the following code
+                // ```rust
+                // match a { ... many cases };
+                // match b { ... many cases };
+                // ```
+                // into
+                // ```rust
+                // match a { ... many match b { goto BB cases } }
+                // ... BB cases
+                // ```
+                // Abandon this transformation when it is possible (the best effort)
+                // to encounter the problem.
                 let mut successors = basic_blocks[bb].terminator().successors();
                 let Some(first_successor) = successors.next() else { return true };
                 if successors.next().is_some() {
@@ -136,11 +155,32 @@ impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
                 };
                 true
             }
+            // If and only if there is a variant that does not have a branch set,
+            // change the current of otherwise as the variant branch and set otherwise to unreachable.
+            // It transforms following code
+            // ```rust
+            // match c {
+            //     Ordering::Less => 1,
+            //     Ordering::Equal => 2,
+            //     _ => 3,
+            // }
+            // ```
+            // to
+            // ```rust
+            // match c {
+            //     Ordering::Less => 1,
+            //     Ordering::Equal => 2,
+            //     Ordering::Greater => 3,
+            // }
+            // ```
             let otherwise_is_last_variant = !otherwise_is_empty_unreachable
                 && allowed_variants.len() == 1
-                && check_successors(&body.basic_blocks, targets.otherwise());
+                // Despite the LLVM issue, we hope that small enum can still be transformed.
+                // This is valuable for both `a <= b` and `if let Some/Ok(v)`.
+                && (targets.all_targets().len() <= 3
+                    || check_successors(&body.basic_blocks, targets.otherwise()));
             let replace_otherwise_to_unreachable = otherwise_is_last_variant
-                || !otherwise_is_empty_unreachable && allowed_variants.is_empty();
+                || (!otherwise_is_empty_unreachable && allowed_variants.is_empty());
 
             if unreachable_targets.is_empty() && !replace_otherwise_to_unreachable {
                 continue;
@@ -150,6 +190,7 @@ impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
             let mut targets = targets.clone();
             if replace_otherwise_to_unreachable {
                 if otherwise_is_last_variant {
+                    // We have checked that `allowed_variants` has only one element.
                     #[allow(rustc::potential_query_instability)]
                     let last_variant = *allowed_variants.iter().next().unwrap();
                     targets.add_target(last_variant, targets.otherwise());