1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt -passes=simplifycfg --switch-to-lookup -S < %s | FileCheck %s 3 4target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128" 5 6declare i1 @foo() 7 8; https://alive2.llvm.org/ce/z/tuxLhJ 9define i1 @switch_lookup_with_small_i1(i64 %x) { 10; CHECK-LABEL: @switch_lookup_with_small_i1( 11; CHECK-NEXT: entry: 12; CHECK-NEXT: [[AND:%.*]] = and i64 [[X:%.*]], 15 13; CHECK-NEXT: [[SWITCH_CAST:%.*]] = trunc i64 [[AND]] to i16 14; CHECK-NEXT: [[SWITCH_SHIFTAMT:%.*]] = mul nuw nsw i16 [[SWITCH_CAST]], 1 15; CHECK-NEXT: [[SWITCH_DOWNSHIFT:%.*]] = lshr i16 1030, [[SWITCH_SHIFTAMT]] 16; CHECK-NEXT: [[SWITCH_MASKED:%.*]] = trunc i16 [[SWITCH_DOWNSHIFT]] to i1 17; CHECK-NEXT: ret i1 [[SWITCH_MASKED]] 18; 19entry: 20 %and = and i64 %x, 15 21 switch i64 %and, label %default [ 22 i64 10, label %lor.end 23 i64 1, label %lor.end 24 i64 2, label %lor.end 25 ] 26 27default: ; preds = %entry 28 br label %lor.end 29 30lor.end: ; preds = %entry, %entry, %entry, %default 31 %0 = phi i1 [ true, %entry ], [ false, %default ], [ true, %entry ], [ true, %entry ] 32 ret i1 %0 33} 34 35; https://godbolt.org/z/sjbjorKon 36define i8 @switch_lookup_with_small_i8(i64 %x) { 37; CHECK-LABEL: @switch_lookup_with_small_i8( 38; CHECK-NEXT: entry: 39; CHECK-NEXT: [[REM:%.*]] = urem i64 [[X:%.*]], 5 40; CHECK-NEXT: [[SWITCH_CAST:%.*]] = trunc i64 [[REM]] to i40 41; CHECK-NEXT: [[SWITCH_SHIFTAMT:%.*]] = mul nuw nsw i40 [[SWITCH_CAST]], 8 42; CHECK-NEXT: [[SWITCH_DOWNSHIFT:%.*]] = lshr i40 460303, [[SWITCH_SHIFTAMT]] 43; CHECK-NEXT: [[SWITCH_MASKED:%.*]] = trunc i40 [[SWITCH_DOWNSHIFT]] to i8 44; CHECK-NEXT: ret i8 [[SWITCH_MASKED]] 45; 46entry: 47 %rem = urem i64 %x, 5 48 switch i64 %rem, label %default [ 49 i64 0, label %sw.bb0 50 i64 1, label %sw.bb1 51 i64 2, label %sw.bb2 52 ] 53 54sw.bb0: ; preds = %entry 55 br label %lor.end 56 57sw.bb1: ; preds = %entry 58 br label %lor.end 59 60sw.bb2: ; preds = %entry 61 br label %lor.end 62 63default: ; preds = %entry 64 br label %lor.end 65 66lor.end: 67 %0 = phi i8 [ 15, %sw.bb0 ], [ 6, %sw.bb1 ], [ 7, %sw.bb2 ], [ 0, %default ] 68 ret i8 %0 69} 70 71; Negative test: Table size would not fit the register. 72define i8 @switch_lookup_with_small_i8_negative(i64 %x) { 73; CHECK-LABEL: @switch_lookup_with_small_i8_negative( 74; CHECK-NEXT: entry: 75; CHECK-NEXT: [[REM:%.*]] = urem i64 [[X:%.*]], 9 76; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i64 [[REM]], 3 77; CHECK-NEXT: [[SWITCH_CAST:%.*]] = trunc i64 [[REM]] to i24 78; CHECK-NEXT: [[SWITCH_SHIFTAMT:%.*]] = mul nuw nsw i24 [[SWITCH_CAST]], 8 79; CHECK-NEXT: [[SWITCH_DOWNSHIFT:%.*]] = lshr i24 460303, [[SWITCH_SHIFTAMT]] 80; CHECK-NEXT: [[SWITCH_MASKED:%.*]] = trunc i24 [[SWITCH_DOWNSHIFT]] to i8 81; CHECK-NEXT: [[TMP1:%.*]] = select i1 [[TMP0]], i8 [[SWITCH_MASKED]], i8 0 82; CHECK-NEXT: ret i8 [[TMP1]] 83; 84entry: 85 %rem = urem i64 %x, 9 ; 9 * 8 = 72 > 64, not fit the register 86 switch i64 %rem, label %default [ 87 i64 0, label %sw.bb0 88 i64 1, label %sw.bb1 89 i64 2, label %sw.bb2 90 ] 91 92sw.bb0: ; preds = %entry 93 br label %lor.end 94 95sw.bb1: ; preds = %entry 96 br label %lor.end 97 98sw.bb2: ; preds = %entry 99 br label %lor.end 100 101default: ; preds = %entry 102 br label %lor.end 103 104lor.end: 105 %0 = phi i8 [ 15, %sw.bb0 ], [ 6, %sw.bb1 ], [ 7, %sw.bb2 ], [ 0, %default ] 106 ret i8 %0 107} 108 109; Negative test: The default branch is unreachable, also it has no result. 110define i1 @switch_lookup_with_small_i1_default_unreachable(i32 %x) { 111; CHECK-LABEL: @switch_lookup_with_small_i1_default_unreachable( 112; CHECK-NEXT: entry: 113; CHECK-NEXT: [[AND:%.*]] = and i32 [[X:%.*]], 15 114; CHECK-NEXT: ret i1 false 115; 116entry: 117 %and = and i32 %x, 15 118 switch i32 %and, label %default [ 119 i32 4, label %phi.end 120 i32 2, label %phi.end 121 i32 10, label %phi.end 122 i32 9, label %phi.end 123 i32 1, label %sw.bb1.i 124 i32 3, label %sw.bb1.i 125 i32 5, label %sw.bb1.i 126 i32 0, label %sw.bb1.i 127 i32 6, label %sw.bb1.i 128 i32 7, label %sw.bb1.i 129 i32 8, label %sw.bb1.i 130 ] 131 132sw.bb1.i: ; preds = %entry, %entry, %entry, %entry, %entry, %entry, %entry 133 br label %phi.end 134 135default: ; preds = %entry 136 unreachable 137 138phi.end: ; preds = %sw.bb1.i, %entry, %entry, %entry, %entry 139 %retval = phi i1 [ false, %sw.bb1.i ], [ false, %entry ], [ false, %entry ], [ false, %entry ], [ false, %entry ] 140 ret i1 %retval 141} 142 143; Negative test: The result in default reachable, but its value is not const. 144define i1 @switch_lookup_with_small_i1_default_nonconst(i64 %x) { 145; CHECK-LABEL: @switch_lookup_with_small_i1_default_nonconst( 146; CHECK-NEXT: entry: 147; CHECK-NEXT: [[AND:%.*]] = and i64 [[X:%.*]], 15 148; CHECK-NEXT: switch i64 [[AND]], label [[DEFAULT:%.*]] [ 149; CHECK-NEXT: i64 10, label [[LOR_END:%.*]] 150; CHECK-NEXT: i64 1, label [[LOR_END]] 151; CHECK-NEXT: i64 2, label [[LOR_END]] 152; CHECK-NEXT: ] 153; CHECK: default: 154; CHECK-NEXT: [[CALL:%.*]] = tail call i1 @foo() 155; CHECK-NEXT: br label [[LOR_END]] 156; CHECK: lor.end: 157; CHECK-NEXT: [[TMP0:%.*]] = phi i1 [ true, [[ENTRY:%.*]] ], [ [[CALL]], [[DEFAULT]] ], [ true, [[ENTRY]] ], [ true, [[ENTRY]] ] 158; CHECK-NEXT: ret i1 [[TMP0]] 159; 160entry: 161 %and = and i64 %x, 15 162 switch i64 %and, label %default [ 163 i64 10, label %lor.end 164 i64 1, label %lor.end 165 i64 2, label %lor.end 166 ] 167 168default: ; preds = %entry 169 %call = tail call i1 @foo() 170 br label %lor.end 171 172lor.end: ; preds = %entry, %entry, %entry, %default 173 %0 = phi i1 [ true, %entry ], [ %call, %default ], [ true, %entry ], [ true, %entry ] 174 ret i1 %0 175} 176 177; Negative test: The upper bound index of switch is swapped. 178define void @switch_lookup_with_nonconst_range(i32 %x, i1 %cond) { 179; CHECK-LABEL: @switch_lookup_with_nonconst_range( 180; CHECK-NEXT: entry: 181; CHECK-NEXT: br label [[FOR_PREHEADER:%.*]] 182; CHECK: for.preheader: 183; CHECK-NEXT: [[ADD:%.*]] = add nuw i32 [[X:%.*]], 1 184; CHECK-NEXT: br i1 [[COND:%.*]], label [[FOR_PREHEADER]], label [[FOR_END:%.*]] 185; CHECK: for.end: 186; CHECK-NEXT: [[TMP0:%.*]] = icmp ult i32 [[ADD]], 6 187; CHECK-NEXT: br i1 [[TMP0]], label [[SWITCH_LOOKUP:%.*]], label [[LOR_END:%.*]] 188; CHECK: switch.lookup: 189; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [6 x i32], ptr @switch.table.switch_lookup_with_nonconst_range, i32 0, i32 [[ADD]] 190; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4 191; CHECK-NEXT: br label [[LOR_END]] 192; CHECK: lor.end: 193; CHECK-NEXT: [[RETVAL_0_I_I:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 1, [[FOR_END]] ] 194; CHECK-NEXT: ret void 195; 196entry: 197 br label %for.preheader 198 199for.preheader: ; preds = %for.preheader, %entry 200 %add = add nuw i32 %x, 1 ; the UpperBound is unconfirmed 201 br i1 %cond, label %for.preheader, label %for.end 202 203for.end: ; preds = %for.preheader 204 switch i32 %add, label %default [ 205 i32 0, label %lor.end 206 i32 1, label %lor.end 207 i32 5, label %lor.end 208 ] 209 210default: ; preds = %for.end 211 br label %lor.end 212 213lor.end: ; preds = %default, %for.end, %for.end, %for.end 214 %retval.0.i.i = phi i32 [ 1, %default ], [ 0, %for.end ], [ 0, %for.end ], [ 0, %for.end ] 215 ret void 216} 217 218define i1 @pr88607() { 219; CHECK-LABEL: @pr88607( 220; CHECK-NEXT: entry: 221; CHECK-NEXT: [[COND:%.*]] = select i1 false, i32 4, i32 1 222; CHECK-NEXT: [[SPEC_SELECT:%.*]] = select i1 false, i32 2, i32 [[COND]] 223; CHECK-NEXT: ret i1 false 224; 225entry: 226 %cond = select i1 false, i32 4, i32 1 227 %spec.select = select i1 false, i32 2, i32 %cond 228 switch i32 %spec.select, label %lor.rhs [ 229 i32 0, label %exit 230 i32 5, label %exit ; unreachable large case index 231 i32 1, label %exit 232 ] 233 234lor.rhs: ; preds = %entry 235 br label %exit 236 237exit: ; preds = %lor.rhs, %entry, %entry, %entry, %entry 238 %res.ph = phi i1 [ false, %entry ], [ false, %lor.rhs ], [ false, %entry ], [ false, %entry ] 239 ret i1 %res.ph 240} 241 242