Skip to content

Commit f893d88

Browse files
borsbors
committed
Auto merge of #120268 - DianQK:otherwise_is_last_variant_switchs, r=<try>
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 0e42435 + 5617d16 commit f893d88

14 files changed

+419
-11
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

+16-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,7 +93,7 @@ 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)
9798
} else {
9899
continue;
@@ -103,20 +104,29 @@ impl<'tcx> MirPass<'tcx> for UninhabitedEnumBranching {
103104
let terminator = bb_data.terminator();
104105
let TerminatorKind::SwitchInt { targets, .. } = &terminator.kind else { bug!() };
105106

106-
let mut reachable_count = 0;
107107
for (index, (val, _)) in targets.iter().enumerate() {
108-
if allowed_variants.contains(&val) {
109-
reachable_count += 1;
110-
} else {
108+
if !allowed_variants.remove(&val) {
111109
removable_switchs.push((bb, index));
112110
}
113111
}
114112

115-
if reachable_count == allowed_variants.len() {
113+
if allowed_variants.is_empty() {
116114
removable_switchs.push((bb, targets.iter().count()));
115+
} else if allowed_variants.len() == 1 {
116+
#[allow(rustc::potential_query_instability)]
117+
let last_variant = *allowed_variants.iter().next().unwrap();
118+
otherwise_is_last_variant_switchs.push((bb, last_variant));
117119
}
118120
}
119121

122+
for (bb, last_variant) in otherwise_is_last_variant_switchs {
123+
let bb_data = &mut body.basic_blocks.as_mut()[bb];
124+
let terminator = bb_data.terminator_mut();
125+
let TerminatorKind::SwitchInt { targets, .. } = &mut terminator.kind else { bug!() };
126+
targets.add_target(last_variant, targets.otherwise());
127+
removable_switchs.push((bb, targets.iter().count()));
128+
}
129+
120130
if removable_switchs.is_empty() {
121131
return;
122132
}

‎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/simplify_locals_fixedpoint.foo.SimplifyLocals-final.panic-abort.diff

+5-1
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,7 @@
2323
StorageDead(_3);
2424
StorageDead(_2);
2525
_5 = discriminant((_1.0: std::option::Option<u8>));
26-
switchInt(move _5) -> [1: bb1, otherwise: bb3];
26+
switchInt(move _5) -> [1: bb1, 0: bb3, otherwise: bb5];
2727
}
2828

2929
bb1: {
@@ -46,5 +46,9 @@
4646
StorageDead(_1);
4747
return;
4848
}
49+
50+
bb5: {
51+
unreachable;
52+
}
4953
}
5054

‎tests/mir-opt/simplify_locals_fixedpoint.foo.SimplifyLocals-final.panic-unwind.diff

+5-1
Original file line numberDiff line numberDiff line change
@@ -23,7 +23,7 @@
2323
StorageDead(_3);
2424
StorageDead(_2);
2525
_5 = discriminant((_1.0: std::option::Option<u8>));
26-
switchInt(move _5) -> [1: bb1, otherwise: bb3];
26+
switchInt(move _5) -> [1: bb1, 0: bb3, otherwise: bb5];
2727
}
2828

2929
bb1: {
@@ -46,5 +46,9 @@
4646
StorageDead(_1);
4747
return;
4848
}
49+
50+
bb5: {
51+
unreachable;
52+
}
4953
}
5054

‎tests/mir-opt/uninhabited_enum_branching.otherwise_t1.UninhabitedEnumBranching.diff

+53
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
- // MIR for `otherwise_t1` before UninhabitedEnumBranching
2+
+ // MIR for `otherwise_t1` after UninhabitedEnumBranching
3+
4+
fn otherwise_t1() -> () {
5+
let mut _0: ();
6+
let _1: &str;
7+
let mut _2: Test1;
8+
let mut _3: isize;
9+
let _4: &str;
10+
let _5: &str;
11+
12+
bb0: {
13+
StorageLive(_1);
14+
StorageLive(_2);
15+
_2 = Test1::C;
16+
_3 = discriminant(_2);
17+
- switchInt(move _3) -> [0: bb2, 1: bb3, otherwise: bb1];
18+
+ switchInt(move _3) -> [0: bb5, 1: bb5, 2: bb1, otherwise: bb5];
19+
}
20+
21+
bb1: {
22+
StorageLive(_5);
23+
_5 = const "C";
24+
_1 = &(*_5);
25+
StorageDead(_5);
26+
goto -> bb4;
27+
}
28+
29+
bb2: {
30+
_1 = const "A(Empty)";
31+
goto -> bb4;
32+
}
33+
34+
bb3: {
35+
StorageLive(_4);
36+
_4 = const "B(Empty)";
37+
_1 = &(*_4);
38+
StorageDead(_4);
39+
goto -> bb4;
40+
}
41+
42+
bb4: {
43+
StorageDead(_2);
44+
StorageDead(_1);
45+
_0 = const ();
46+
return;
47+
+ }
48+
+
49+
+ bb5: {
50+
+ unreachable;
51+
}
52+
}
53+

‎tests/mir-opt/uninhabited_enum_branching.otherwise_t2.UninhabitedEnumBranching.diff

+44
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,44 @@
1+
- // MIR for `otherwise_t2` before UninhabitedEnumBranching
2+
+ // MIR for `otherwise_t2` after UninhabitedEnumBranching
3+
4+
fn otherwise_t2() -> () {
5+
let mut _0: ();
6+
let _1: &str;
7+
let mut _2: Test2;
8+
let mut _3: isize;
9+
let _4: &str;
10+
11+
bb0: {
12+
StorageLive(_1);
13+
StorageLive(_2);
14+
_2 = Test2::D;
15+
_3 = discriminant(_2);
16+
- switchInt(move _3) -> [4: bb2, otherwise: bb1];
17+
+ switchInt(move _3) -> [4: bb2, 5: bb1, otherwise: bb4];
18+
}
19+
20+
bb1: {
21+
StorageLive(_4);
22+
_4 = const "E";
23+
_1 = &(*_4);
24+
StorageDead(_4);
25+
goto -> bb3;
26+
}
27+
28+
bb2: {
29+
_1 = const "D";
30+
goto -> bb3;
31+
}
32+
33+
bb3: {
34+
StorageDead(_2);
35+
StorageDead(_1);
36+
_0 = const ();
37+
return;
38+
+ }
39+
+
40+
+ bb4: {
41+
+ unreachable;
42+
}
43+
}
44+

‎tests/mir-opt/uninhabited_enum_branching.otherwise_t3.UninhabitedEnumBranching.diff

+53
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,53 @@
1+
- // MIR for `otherwise_t3` before UninhabitedEnumBranching
2+
+ // MIR for `otherwise_t3` after UninhabitedEnumBranching
3+
4+
fn otherwise_t3() -> () {
5+
let mut _0: ();
6+
let _1: &str;
7+
let mut _2: Test3;
8+
let mut _3: isize;
9+
let _4: &str;
10+
let _5: &str;
11+
12+
bb0: {
13+
StorageLive(_1);
14+
StorageLive(_2);
15+
_2 = Test3::C;
16+
_3 = discriminant(_2);
17+
- switchInt(move _3) -> [0: bb2, 1: bb3, otherwise: bb1];
18+
+ switchInt(move _3) -> [0: bb5, 1: bb5, otherwise: bb1];
19+
}
20+
21+
bb1: {
22+
StorageLive(_5);
23+
_5 = const "C";
24+
_1 = &(*_5);
25+
StorageDead(_5);
26+
goto -> bb4;
27+
}
28+
29+
bb2: {
30+
_1 = const "A(Empty)";
31+
goto -> bb4;
32+
}
33+
34+
bb3: {
35+
StorageLive(_4);
36+
_4 = const "B(Empty)";
37+
_1 = &(*_4);
38+
StorageDead(_4);
39+
goto -> bb4;
40+
}
41+
42+
bb4: {
43+
StorageDead(_2);
44+
StorageDead(_1);
45+
_0 = const ();
46+
return;
47+
+ }
48+
+
49+
+ bb5: {
50+
+ unreachable;
51+
}
52+
}
53+

‎tests/mir-opt/uninhabited_enum_branching.otherwise_t4.UninhabitedEnumBranching.diff

+48
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,48 @@
1+
- // MIR for `otherwise_t4` before UninhabitedEnumBranching
2+
+ // MIR for `otherwise_t4` after UninhabitedEnumBranching
3+
4+
fn otherwise_t4() -> () {
5+
let mut _0: ();
6+
let _1: &str;
7+
let mut _2: Test4;
8+
let mut _3: isize;
9+
let _4: &str;
10+
let _5: &str;
11+
12+
bb0: {
13+
StorageLive(_1);
14+
StorageLive(_2);
15+
_2 = Test4::C;
16+
_3 = discriminant(_2);
17+
switchInt(move _3) -> [0: bb2, 1: bb3, otherwise: bb1];
18+
}
19+
20+
bb1: {
21+
StorageLive(_5);
22+
_5 = const "CD";
23+
_1 = &(*_5);
24+
StorageDead(_5);
25+
goto -> bb4;
26+
}
27+
28+
bb2: {
29+
_1 = const "A(i32)";
30+
goto -> bb4;
31+
}
32+
33+
bb3: {
34+
StorageLive(_4);
35+
_4 = const "B(i32)";
36+
_1 = &(*_4);
37+
StorageDead(_4);
38+
goto -> bb4;
39+
}
40+
41+
bb4: {
42+
StorageDead(_2);
43+
StorageDead(_1);
44+
_0 = const ();
45+
return;
46+
}
47+
}
48+

0 commit comments

Comments
 (0)