Skip to content

Commit 76cf07d

Browse files
borsbors
committed
Auto merge of #122225 - DianQK:nits-120268, r=cjgillot
 Rename `UninhabitedEnumBranching` to `UnreachableEnumBranching` Per [#120268](#120268 (comment)), 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
2 parents 8938f88 + ec313d1 commit 76cf07d

File tree

33 files changed

+256
-166
lines changed

33 files changed

+256
-166
lines changed

‎compiler/rustc_mir_transform/src/lib.rs

+4-3
Original file line numberDiff line numberDiff line change
@@ -110,7 +110,7 @@ pub mod simplify;
110110
mod simplify_branches;
111111
mod simplify_comparison_integral;
112112
mod sroa;
113-
mod uninhabited_enum_branching;
113+
mod unreachable_enum_branching;
114114
mod unreachable_prop;
115115

116116
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>) {
580580
&remove_zsts::RemoveZsts,
581581
&remove_unneeded_drops::RemoveUnneededDrops,
582582
// Type instantiation may create uninhabited enums.
583-
&uninhabited_enum_branching::UninhabitedEnumBranching,
583+
// Also eliminates some unreachable branches based on variants of enums.
584+
&unreachable_enum_branching::UnreachableEnumBranching,
584585
&unreachable_prop::UnreachablePropagation,
585-
&o1(simplify::SimplifyCfg::AfterUninhabitedEnumBranching),
586+
&o1(simplify::SimplifyCfg::AfterUnreachableEnumBranching),
586587
// Inlining may have introduced a lot of redundant code and a large move pattern.
587588
// Now, we need to shrink the generated MIR.
588589

‎compiler/rustc_mir_transform/src/simplify.rs

+3-3
Original file line numberDiff line numberDiff line change
@@ -44,7 +44,7 @@ pub enum SimplifyCfg {
4444
PreOptimizations,
4545
Final,
4646
MakeShim,
47-
AfterUninhabitedEnumBranching,
47+
AfterUnreachableEnumBranching,
4848
}
4949

5050
impl SimplifyCfg {
@@ -57,8 +57,8 @@ impl SimplifyCfg {
5757
SimplifyCfg::PreOptimizations => "SimplifyCfg-pre-optimizations",
5858
SimplifyCfg::Final => "SimplifyCfg-final",
5959
SimplifyCfg::MakeShim => "SimplifyCfg-make_shim",
60-
SimplifyCfg::AfterUninhabitedEnumBranching => {
61-
"SimplifyCfg-after-uninhabited-enum-branching"
60+
SimplifyCfg::AfterUnreachableEnumBranching => {
61+
"SimplifyCfg-after-unreachable-enum-branching"
6262
}
6363
}
6464
}

‎compiler/rustc_mir_transform/src/uninhabited_enum_branching.rs ‎compiler/rustc_mir_transform/src/unreachable_enum_branching.rs

+49-8
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,4 @@
1-
//! A pass that eliminates branches on uninhabited enum variants.
1+
//! A pass that eliminates branches on uninhabited or unreachable enum variants.
22
33
use crate::MirPass;
44
use rustc_data_structures::fx::FxHashSet;
@@ -11,7 +11,7 @@ use rustc_middle::ty::layout::TyAndLayout;
1111
use rustc_middle::ty::{Ty, TyCtxt};
1212
use rustc_target::abi::{Abi, Variants};
1313

14-
pub struct UninhabitedEnumBranching;
14+
pub struct UnreachableEnumBranching;
1515

1616
fn get_discriminant_local(terminator: &TerminatorKind<'_>) -> Option<Local> {
1717
if let TerminatorKind::SwitchInt { discr: Operand::Move(p), .. } = terminator {
@@ -71,13 +71,13 @@ fn variant_discriminants<'tcx>(
7171
}
7272
}
7373

74-
impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
74+
impl<'tcx> MirPass<'tcx> for UnreachableEnumBranching {
7575
fn is_enabled(&self, sess: &rustc_session::Session) -> bool {
7676
sess.mir_opt_level() > 0
7777
}
7878

7979
fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>) {
80-
trace!("UninhabitedEnumBranching starting for {:?}", body.source);
80+
trace!("UnreachableEnumBranching starting for {:?}", body.source);
8181

8282
let mut unreachable_targets = Vec::new();
8383
let mut patch = MirPatch::new(body);
@@ -96,8 +96,10 @@ impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
9696
);
9797

9898
let mut allowed_variants = if let Ok(layout) = layout {
99+
// Find allowed variants based on uninhabited.
99100
variant_discriminants(&layout, discriminant_ty, tcx)
100101
} else if let Some(variant_range) = discriminant_ty.variant_range(tcx) {
102+
// If there are some generics, we can still get the allowed variants.
101103
variant_range
102104
.map(|variant| {
103105
discriminant_ty.discriminant_for_variant(tcx, variant).unwrap().val
@@ -121,9 +123,26 @@ impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
121123
}
122124
let otherwise_is_empty_unreachable =
123125
body.basic_blocks[targets.otherwise()].is_empty_unreachable();
124-
// After resolving https://github.com/llvm/llvm-project/issues/78578,
125-
// we can remove the limit on the number of successors.
126126
fn check_successors(basic_blocks: &BasicBlocks<'_>, bb: BasicBlock) -> bool {
127+
// After resolving https://github.com/llvm/llvm-project/issues/78578,
128+
// We can remove this check.
129+
// The main issue here is that `early-tailduplication` causes compile time overhead
130+
// and potential performance problems.
131+
// Simply put, when encounter a switch (indirect branch) statement,
132+
// `early-tailduplication` tries to duplicate the switch branch statement with BB
133+
// into (each) predecessors. This makes CFG very complex.
134+
// We can understand it as it transforms the following code
135+
// ```rust
136+
// match a { ... many cases };
137+
// match b { ... many cases };
138+
// ```
139+
// into
140+
// ```rust
141+
// match a { ... many match b { goto BB cases } }
142+
// ... BB cases
143+
// ```
144+
// Abandon this transformation when it is possible (the best effort)
145+
// to encounter the problem.
127146
let mut successors = basic_blocks[bb].terminator().successors();
128147
let Some(first_successor) = successors.next() else { return true };
129148
if successors.next().is_some() {
@@ -136,11 +155,32 @@ impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
136155
};
137156
true
138157
}
158+
// If and only if there is a variant that does not have a branch set,
159+
// change the current of otherwise as the variant branch and set otherwise to unreachable.
160+
// It transforms following code
161+
// ```rust
162+
// match c {
163+
// Ordering::Less => 1,
164+
// Ordering::Equal => 2,
165+
// _ => 3,
166+
// }
167+
// ```
168+
// to
169+
// ```rust
170+
// match c {
171+
// Ordering::Less => 1,
172+
// Ordering::Equal => 2,
173+
// Ordering::Greater => 3,
174+
// }
175+
// ```
139176
let otherwise_is_last_variant = !otherwise_is_empty_unreachable
140177
&& allowed_variants.len() == 1
141-
&& check_successors(&body.basic_blocks, targets.otherwise());
178+
// Despite the LLVM issue, we hope that small enum can still be transformed.
179+
// This is valuable for both `a <= b` and `if let Some/Ok(v)`.
180+
&& (targets.all_targets().len() <= 3
181+
|| check_successors(&body.basic_blocks, targets.otherwise()));
142182
let replace_otherwise_to_unreachable = otherwise_is_last_variant
143-
|| !otherwise_is_empty_unreachable && allowed_variants.is_empty();
183+
|| (!otherwise_is_empty_unreachable && allowed_variants.is_empty());
144184

145185
if unreachable_targets.is_empty() && !replace_otherwise_to_unreachable {
146186
continue;
@@ -150,6 +190,7 @@ impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
150190
let mut targets = targets.clone();
151191
if replace_otherwise_to_unreachable {
152192
if otherwise_is_last_variant {
193+
// We have checked that `allowed_variants` has only one element.
153194
#[allow(rustc::potential_query_instability)]
154195
let last_variant = *allowed_variants.iter().next().unwrap();
155196
targets.add_target(last_variant, targets.otherwise());

‎tests/codegen/enum/uninhabited_enum_default_branch.rs

-24
This file was deleted.

‎tests/codegen/enum/unreachable_enum_default_branch.rs

+43
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
//@ compile-flags: -O
2+
3+
#![crate_type = "lib"]
4+
5+
#[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord)]
6+
pub struct Int(u32);
7+
8+
const A: Int = Int(201);
9+
const B: Int = Int(270);
10+
const C: Int = Int(153);
11+
12+
// The code is from https://github.com/rust-lang/rust/issues/119520.
13+
// This code will basically turn into `matches!(x.partial_cmp(&A), Some(Greater | Equal))`.
14+
// The otherwise branch must be `Less`.
15+
// CHECK-LABEL: @implicit_match(
16+
// CHECK-SAME: [[TMP0:%.*]])
17+
// CHECK-NEXT: start:
18+
// CHECK-NEXT: [[TMP1:%.*]] = add i32 [[TMP0]], -201
19+
// CHECK-NEXT: icmp ult i32 [[TMP1]], 70
20+
// CHECK-NEXT: icmp eq i32 [[TMP0]], 153
21+
// CHECK-NEXT: [[SPEC_SELECT:%.*]] = or i1
22+
// CHECK-NEXT: ret i1 [[SPEC_SELECT]]
23+
#[no_mangle]
24+
pub fn implicit_match(x: Int) -> bool {
25+
(x >= A && x <= B)
26+
|| x == C
27+
}
28+
29+
// The code is from https://github.com/rust-lang/rust/issues/110097.
30+
// We expect it to generate the same optimized code as a full match.
31+
// CHECK-LABEL: @if_let(
32+
// CHECK-NEXT: start:
33+
// CHECK-NEXT: insertvalue
34+
// CHECK-NEXT: insertvalue
35+
// CHECK-NEXT: ret
36+
#[no_mangle]
37+
pub fn if_let(val: Result<i32, ()>) -> Result<i32, ()> {
38+
if let Ok(x) = val {
39+
Ok(x)
40+
} else {
41+
Err(())
42+
}
43+
}

‎tests/mir-opt/simplify_dead_blocks.assert_nonzero_nonmax.SimplifyCfg-after-unreachable-enum-branching.diff

+33
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
- // MIR for `assert_nonzero_nonmax` before SimplifyCfg-after-unreachable-enum-branching
2+
+ // MIR for `assert_nonzero_nonmax` after SimplifyCfg-after-unreachable-enum-branching
3+
4+
fn assert_nonzero_nonmax(_1: u8) -> u8 {
5+
let mut _0: u8;
6+
7+
bb0: {
8+
- switchInt(_1) -> [0: bb3, 1: bb2, 255: bb3, otherwise: bb4];
9+
+ switchInt(_1) -> [0: bb2, 1: bb1, 255: bb2, otherwise: bb3];
10+
}
11+
12+
bb1: {
13+
- _0 = const 1_u8;
14+
- return;
15+
- }
16+
-
17+
- bb2: {
18+
_0 = const 2_u8;
19+
return;
20+
}
21+
22+
- bb3: {
23+
+ bb2: {
24+
unreachable;
25+
}
26+
27+
- bb4: {
28+
+ bb3: {
29+
_0 = _1;
30+
return;
31+
}
32+
}
33+

‎tests/mir-opt/simplify_dead_blocks.rs

+52
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,52 @@
1+
//@ unit-test: SimplifyCfg-after-unreachable-enum-branching
2+
#![feature(custom_mir, core_intrinsics)]
3+
#![crate_type = "lib"]
4+
5+
use std::intrinsics::mir::*;
6+
7+
// Check that we correctly cleaned up the dead BB.
8+
// EMIT_MIR simplify_dead_blocks.assert_nonzero_nonmax.SimplifyCfg-after-unreachable-enum-branching.diff
9+
#[custom_mir(dialect = "runtime", phase = "post-cleanup")]
10+
pub unsafe fn assert_nonzero_nonmax(x: u8) -> u8 {
11+
// CHECK-LABEL: fn assert_nonzero_nonmax(
12+
// CHECK: bb0: {
13+
// CHECK-NEXT: switchInt({{.*}}) -> [0: [[unreachable:bb.*]], 1: [[retblock2:bb.*]], 255: [[unreachable:bb.*]], otherwise: [[retblock:bb.*]]];
14+
// CHECK-NEXT: }
15+
// CHECK-NOT: _0 = const 1_u8;
16+
// CHECK: [[retblock2]]: {
17+
// CHECK-NEXT: _0 = const 2_u8;
18+
// CHECK-NEXT: return;
19+
// CHECK-NEXT: }
20+
// CHECK: [[unreachable]]: {
21+
// CHECK-NEXT: unreachable;
22+
// CHECK-NEXT: }
23+
// CHECK: [[retblock]]: {
24+
// CHECK-NEXT: _0 = _1;
25+
// CHECK-NEXT: return;
26+
// CHECK-NEXT: }
27+
mir!(
28+
{
29+
match x {
30+
0 => unreachable,
31+
1 => retblock2,
32+
u8::MAX => unreachable,
33+
_ => retblock,
34+
}
35+
}
36+
deadRetblock1 = {
37+
RET = 1;
38+
Return()
39+
}
40+
retblock2 = {
41+
RET = 2;
42+
Return()
43+
}
44+
unreachable = {
45+
Unreachable()
46+
}
47+
retblock = {
48+
RET = x;
49+
Return()
50+
}
51+
)
52+
}

‎tests/mir-opt/simplify_duplicate_unreachable_blocks.assert_nonzero_nonmax.SimplifyCfg-after-uninhabited-enum-branching.diff

-25
This file was deleted.

‎tests/mir-opt/simplify_duplicate_unreachable_blocks.rs

-31
This file was deleted.

‎tests/mir-opt/uninhabited_fallthrough_elimination.eliminate_fallthrough.UninhabitedEnumBranching.diff ‎tests/mir-opt/uninhabited_fallthrough_elimination.eliminate_fallthrough.UnreachableEnumBranching.diff

+2-2
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
1-
- // MIR for `eliminate_fallthrough` before UninhabitedEnumBranching
2-
+ // MIR for `eliminate_fallthrough` after UninhabitedEnumBranching
1+
- // MIR for `eliminate_fallthrough` before UnreachableEnumBranching
2+
+ // MIR for `eliminate_fallthrough` after UnreachableEnumBranching
33

44
fn eliminate_fallthrough(_1: S) -> u32 {
55
debug s => _1;

‎tests/mir-opt/uninhabited_fallthrough_elimination.keep_fallthrough.UninhabitedEnumBranching.diff ‎tests/mir-opt/uninhabited_fallthrough_elimination.keep_fallthrough.UnreachableEnumBranching.diff

+2-2
Original file line numberDiff line numberDiff line change
@@ -1,5 +1,5 @@
1-
- // MIR for `keep_fallthrough` before UninhabitedEnumBranching
2-
+ // MIR for `keep_fallthrough` after UninhabitedEnumBranching
1+
- // MIR for `keep_fallthrough` before UnreachableEnumBranching
2+
+ // MIR for `keep_fallthrough` after UnreachableEnumBranching
33

44
fn keep_fallthrough(_1: S) -> u32 {
55
debug s => _1;

0 commit comments

Comments
 (0)