Skip to content

Commit 4b854f3

Browse files
borsbors
committed
Auto merge of #120268 - DianQK:otherwise_is_last_variant_switchs, r=oli-obk
Replace the default branch with an unreachable branch If it is the last variant Fixes #119520. LLVM currently has limited ability to eliminate dead branches in switches, even with the patch of llvm/llvm-project#73446. The main reasons are as follows: - Additional costs are required to calculate the range of values, and there exist many scenarios that cannot be analyzed accurately. - Matching values by bitwise calculation cannot handle odd branches, nor can it handle values like `-1, 0, 1`. See [SimplifyCFG.cpp#L5424](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/Transforms/Utils/SimplifyCFG.cpp#L5424) and https://llvm.godbolt.org/z/qYMqhvMa8 - The current range information is continuous, even if the metadata for the range is submitted. See [ConstantRange.cpp#L1869-L1870](https://github.com/llvm/llvm-project/blob/llvmorg-17.0.6/llvm/lib/IR/ConstantRange.cpp#L1869-L1870). - The metadata of the range may be lost in passes such as SROA. See https://rust.godbolt.org/z/e7f87vKMK. Although we can make improvements, I think it would be more appropriate to put this issue to rustc first. After all, we can easily know the possible values. Note that we've currently found a slow compilation problem in the presence of unreachable branches. See llvm/llvm-project#78578. r? compiler
2 parents 69db514 + d02299c commit 4b854f3

20 files changed

+690
-114
lines changed

‎compiler/rustc_middle/src/mir/terminator.rs

+11
Original file line numberDiff line numberDiff line change
@@ -74,6 +74,17 @@ impl SwitchTargets {
7474
pub fn target_for_value(&self, value: u128) -> BasicBlock {
7575
self.iter().find_map(|(v, t)| (v == value).then_some(t)).unwrap_or_else(|| self.otherwise())
7676
}
77+
78+
/// Adds a new target to the switch. But You cannot add an already present value.
79+
#[inline]
80+
pub fn add_target(&mut self, value: u128, bb: BasicBlock) {
81+
let value = Pu128(value);
82+
if self.values.contains(&value) {
83+
bug!("target value {:?} already present", value);
84+
}
85+
self.values.push(value);
86+
self.targets.insert(self.targets.len() - 1, bb);
87+
}
7788
}
7889

7990
pub struct SwitchTargetsIter<'a> {

‎compiler/rustc_mir_transform/src/uninhabited_enum_branching.rs

+22-6
Original file line numberDiff line numberDiff line change
@@ -78,6 +78,7 @@ impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
7878
trace!("UninhabitedEnumBranching starting for {:?}", body.source);
7979

8080
let mut removable_switchs = Vec::new();
81+
let mut otherwise_is_last_variant_switchs = Vec::new();
8182

8283
for (bb, bb_data) in body.basic_blocks.iter_enumerated() {
8384
trace!("processing block {:?}", bb);
@@ -92,8 +93,14 @@ impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
9293
tcx.param_env_reveal_all_normalized(body.source.def_id()).and(discriminant_ty),
9394
);
9495

95-
let allowed_variants = if let Ok(layout) = layout {
96+
let mut allowed_variants = if let Ok(layout) = layout {
9697
variant_discriminants(&layout, discriminant_ty, tcx)
98+
} else if let Some(variant_range) = discriminant_ty.variant_range(tcx) {
99+
variant_range
100+
.map(|variant| {
101+
discriminant_ty.discriminant_for_variant(tcx, variant).unwrap().val
102+
})
103+
.collect()
97104
} else {
98105
continue;
99106
};
@@ -103,20 +110,29 @@ impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
103110
let terminator = bb_data.terminator();
104111
let TerminatorKind::SwitchInt { targets, .. } = &terminator.kind else { bug!() };
105112

106-
let mut reachable_count = 0;
107113
for (index, (val, _)) in targets.iter().enumerate() {
108-
if allowed_variants.contains(&val) {
109-
reachable_count += 1;
110-
} else {
114+
if !allowed_variants.remove(&val) {
111115
removable_switchs.push((bb, index));
112116
}
113117
}
114118

115-
if reachable_count == allowed_variants.len() {
119+
if allowed_variants.is_empty() {
116120
removable_switchs.push((bb, targets.iter().count()));
121+
} else if allowed_variants.len() == 1 {
122+
#[allow(rustc::potential_query_instability)]
123+
let last_variant = *allowed_variants.iter().next().unwrap();
124+
otherwise_is_last_variant_switchs.push((bb, last_variant));
117125
}
118126
}
119127

128+
for (bb, last_variant) in otherwise_is_last_variant_switchs {
129+
let bb_data = &mut body.basic_blocks.as_mut()[bb];
130+
let terminator = bb_data.terminator_mut();
131+
let TerminatorKind::SwitchInt { targets, .. } = &mut terminator.kind else { bug!() };
132+
targets.add_target(last_variant, targets.otherwise());
133+
removable_switchs.push((bb, targets.iter().count()));
134+
}
135+
120136
if removable_switchs.is_empty() {
121137
return;
122138
}

‎src/bootstrap/src/core/build_steps/test.rs

+1-2
Original file line numberDiff line numberDiff line change
@@ -1525,13 +1525,12 @@ You can add that mapping by changing MIR_OPT_BLESS_TARGET_MAPPING in src/bootstr
15251525
});
15261526

15271527
for target in targets {
1528-
run(target);
1529-
15301528
let panic_abort_target = builder.ensure(MirOptPanicAbortSyntheticTarget {
15311529
compiler: self.compiler,
15321530
base: target,
15331531
});
15341532
run(panic_abort_target);
1533+
run(target);
15351534
}
15361535
} else {
15371536
run(self.target);

‎tests/codegen/enum/uninhabited_enum_default_branch.rs

+24
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,24 @@
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+
// CHECK-LABEL: @foo
13+
// CHECK-SAME: [[TMP0:%.*]])
14+
// CHECK-NEXT: start:
15+
// CHECK-NEXT: [[TMP1:%.*]] = add i32 [[TMP0]], -201
16+
// CHECK-NEXT: [[OR_COND:%.*]] = icmp ult i32 [[TMP1]], 70
17+
// CHECK-NEXT: [[TMP2:%.*]] = icmp eq i32 [[TMP0]], 153
18+
// CHECK-NEXT: [[SPEC_SELECT:%.*]] = or i1 [[OR_COND]], [[TMP2]]
19+
// CHECK-NEXT: ret i1 [[SPEC_SELECT]]
20+
#[no_mangle]
21+
pub fn foo(x: Int) -> bool {
22+
(x >= A && x <= B)
23+
|| x == C
24+
}

‎tests/mir-opt/funky_arms.float_to_exponential_common.GVN.panic-abort.diff

+5-1
Original file line numberDiff line numberDiff line change
@@ -69,7 +69,7 @@
6969
StorageLive(_6);
7070
_6 = ((*_1).4: std::option::Option<usize>);
7171
_7 = discriminant(_6);
72-
switchInt(move _7) -> [1: bb4, otherwise: bb6];
72+
switchInt(move _7) -> [1: bb4, 0: bb6, otherwise: bb9];
7373
}
7474

7575
bb4: {
@@ -135,5 +135,9 @@
135135
StorageDead(_6);
136136
return;
137137
}
138+
139+
bb9: {
140+
unreachable;
141+
}
138142
}
139143

‎tests/mir-opt/funky_arms.float_to_exponential_common.GVN.panic-unwind.diff

+5-1
Original file line numberDiff line numberDiff line change
@@ -69,7 +69,7 @@
6969
StorageLive(_6);
7070
_6 = ((*_1).4: std::option::Option<usize>);
7171
_7 = discriminant(_6);
72-
switchInt(move _7) -> [1: bb4, otherwise: bb6];
72+
switchInt(move _7) -> [1: bb4, 0: bb6, otherwise: bb9];
7373
}
7474

7575
bb4: {
@@ -135,5 +135,9 @@
135135
StorageDead(_6);
136136
return;
137137
}
138+
139+
bb9: {
140+
unreachable;
141+
}
138142
}
139143

‎tests/mir-opt/issues/issue_59352.num_to_digit.PreCodegen.after.panic-abort.mir

+38-22
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,8 @@
33
fn num_to_digit(_1: char) -> u32 {
44
debug num => _1;
55
let mut _0: u32;
6-
let mut _5: std::option::Option<u32>;
6+
let mut _5: bool;
7+
let mut _6: std::option::Option<u32>;
78
scope 1 (inlined char::methods::<impl char>::is_digit) {
89
debug self => _1;
910
debug radix => const 8_u32;
@@ -15,15 +16,16 @@ fn num_to_digit(_1: char) -> u32 {
1516
}
1617
}
1718
scope 3 (inlined #[track_caller] Option::<u32>::unwrap) {
18-
debug self => _5;
19-
let mut _6: isize;
20-
let mut _7: !;
19+
debug self => _6;
20+
let mut _7: isize;
21+
let mut _8: !;
2122
scope 4 {
2223
debug val => _0;
2324
}
2425
}
2526

2627
bb0: {
28+
StorageLive(_5);
2729
StorageLive(_3);
2830
StorageLive(_2);
2931
_2 = char::methods::<impl char>::to_digit(_1, const 8_u32) -> [return: bb1, unwind unreachable];
@@ -33,45 +35,59 @@ fn num_to_digit(_1: char) -> u32 {
3335
_3 = &_2;
3436
StorageLive(_4);
3537
_4 = discriminant(_2);
36-
StorageDead(_3);
37-
StorageDead(_2);
38-
switchInt(move _4) -> [1: bb2, otherwise: bb7];
38+
switchInt(move _4) -> [1: bb2, 0: bb3, otherwise: bb11];
3939
}
4040

4141
bb2: {
42-
StorageDead(_4);
43-
StorageLive(_5);
44-
_5 = char::methods::<impl char>::to_digit(move _1, const 8_u32) -> [return: bb3, unwind unreachable];
42+
_5 = const true;
43+
goto -> bb4;
4544
}
4645

4746
bb3: {
48-
StorageLive(_6);
49-
_6 = discriminant(_5);
50-
switchInt(move _6) -> [0: bb4, 1: bb5, otherwise: bb6];
47+
_5 = const false;
48+
goto -> bb4;
5149
}
5250

5351
bb4: {
54-
_7 = option::unwrap_failed() -> unwind unreachable;
52+
StorageDead(_4);
53+
StorageDead(_3);
54+
StorageDead(_2);
55+
switchInt(move _5) -> [0: bb5, otherwise: bb6];
5556
}
5657

5758
bb5: {
58-
_0 = move ((_5 as Some).0: u32);
59-
StorageDead(_6);
60-
StorageDead(_5);
61-
goto -> bb8;
59+
_0 = const 0_u32;
60+
goto -> bb10;
6261
}
6362

6463
bb6: {
65-
unreachable;
64+
StorageLive(_6);
65+
_6 = char::methods::<impl char>::to_digit(move _1, const 8_u32) -> [return: bb7, unwind unreachable];
6666
}
6767

6868
bb7: {
69-
StorageDead(_4);
70-
_0 = const 0_u32;
71-
goto -> bb8;
69+
StorageLive(_7);
70+
_7 = discriminant(_6);
71+
switchInt(move _7) -> [0: bb8, 1: bb9, otherwise: bb11];
7272
}
7373

7474
bb8: {
75+
_8 = option::unwrap_failed() -> unwind unreachable;
76+
}
77+
78+
bb9: {
79+
_0 = move ((_6 as Some).0: u32);
80+
StorageDead(_7);
81+
StorageDead(_6);
82+
goto -> bb10;
83+
}
84+
85+
bb10: {
86+
StorageDead(_5);
7587
return;
7688
}
89+
90+
bb11: {
91+
unreachable;
92+
}
7793
}

‎tests/mir-opt/issues/issue_59352.num_to_digit.PreCodegen.after.panic-unwind.mir

+38-22
Original file line numberDiff line numberDiff line change
@@ -3,7 +3,8 @@
33
fn num_to_digit(_1: char) -> u32 {
44
debug num => _1;
55
let mut _0: u32;
6-
let mut _5: std::option::Option<u32>;
6+
let mut _5: bool;
7+
let mut _6: std::option::Option<u32>;
78
scope 1 (inlined char::methods::<impl char>::is_digit) {
89
debug self => _1;
910
debug radix => const 8_u32;
@@ -15,15 +16,16 @@ fn num_to_digit(_1: char) -> u32 {
1516
}
1617
}
1718
scope 3 (inlined #[track_caller] Option::<u32>::unwrap) {
18-
debug self => _5;
19-
let mut _6: isize;
20-
let mut _7: !;
19+
debug self => _6;
20+
let mut _7: isize;
21+
let mut _8: !;
2122
scope 4 {
2223
debug val => _0;
2324
}
2425
}
2526

2627
bb0: {
28+
StorageLive(_5);
2729
StorageLive(_3);
2830
StorageLive(_2);
2931
_2 = char::methods::<impl char>::to_digit(_1, const 8_u32) -> [return: bb1, unwind continue];
@@ -33,45 +35,59 @@ fn num_to_digit(_1: char) -> u32 {
3335
_3 = &_2;
3436
StorageLive(_4);
3537
_4 = discriminant(_2);
36-
StorageDead(_3);
37-
StorageDead(_2);
38-
switchInt(move _4) -> [1: bb2, otherwise: bb7];
38+
switchInt(move _4) -> [1: bb2, 0: bb3, otherwise: bb11];
3939
}
4040

4141
bb2: {
42-
StorageDead(_4);
43-
StorageLive(_5);
44-
_5 = char::methods::<impl char>::to_digit(move _1, const 8_u32) -> [return: bb3, unwind continue];
42+
_5 = const true;
43+
goto -> bb4;
4544
}
4645

4746
bb3: {
48-
StorageLive(_6);
49-
_6 = discriminant(_5);
50-
switchInt(move _6) -> [0: bb4, 1: bb5, otherwise: bb6];
47+
_5 = const false;
48+
goto -> bb4;
5149
}
5250

5351
bb4: {
54-
_7 = option::unwrap_failed() -> unwind continue;
52+
StorageDead(_4);
53+
StorageDead(_3);
54+
StorageDead(_2);
55+
switchInt(move _5) -> [0: bb5, otherwise: bb6];
5556
}
5657

5758
bb5: {
58-
_0 = move ((_5 as Some).0: u32);
59-
StorageDead(_6);
60-
StorageDead(_5);
61-
goto -> bb8;
59+
_0 = const 0_u32;
60+
goto -> bb10;
6261
}
6362

6463
bb6: {
65-
unreachable;
64+
StorageLive(_6);
65+
_6 = char::methods::<impl char>::to_digit(move _1, const 8_u32) -> [return: bb7, unwind continue];
6666
}
6767

6868
bb7: {
69-
StorageDead(_4);
70-
_0 = const 0_u32;
71-
goto -> bb8;
69+
StorageLive(_7);
70+
_7 = discriminant(_6);
71+
switchInt(move _7) -> [0: bb8, 1: bb9, otherwise: bb11];
7272
}
7373

7474
bb8: {
75+
_8 = option::unwrap_failed() -> unwind continue;
76+
}
77+
78+
bb9: {
79+
_0 = move ((_6 as Some).0: u32);
80+
StorageDead(_7);
81+
StorageDead(_6);
82+
goto -> bb10;
83+
}
84+
85+
bb10: {
86+
StorageDead(_5);
7587
return;
7688
}
89+
90+
bb11: {
91+
unreachable;
92+
}
7793
}

0 commit comments

Comments
 (0)