1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 -switch-to-lookup -S | FileCheck %s 3; RUN: opt < %s -passes='simplifycfg<switch-to-lookup>' -S | FileCheck %s 4 5target datalayout = "e-n32" 6 7define i32 @test1(i32 %a) { 8; CHECK-LABEL: @test1( 9; CHECK-NEXT: [[TMP1:%.*]] = sub i32 [[A:%.*]], 97 10; CHECK-NEXT: [[TMP2:%.*]] = call i32 @llvm.fshl.i32(i32 [[TMP1]], i32 [[TMP1]], i32 30) 11; CHECK-NEXT: [[TMP3:%.*]] = icmp ult i32 [[TMP2]], 4 12; CHECK-NEXT: br i1 [[TMP3]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]] 13; CHECK: switch.lookup: 14; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], ptr @switch.table.test1, i32 0, i32 [[TMP2]] 15; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4 16; CHECK-NEXT: br label [[COMMON_RET]] 17; CHECK: common.ret: 18; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ] 19; CHECK-NEXT: ret i32 [[COMMON_RET_OP]] 20; 21 switch i32 %a, label %def [ 22 i32 97, label %one 23 i32 101, label %two 24 i32 105, label %three 25 i32 109, label %three 26 ] 27 28def: 29 ret i32 8867 30 31one: 32 ret i32 11984 33two: 34 ret i32 1143 35three: 36 ret i32 99783 37} 38 39; Optimization shouldn't trigger; bitwidth > 64 40define i128 @test2(i128 %a) { 41; CHECK-LABEL: @test2( 42; CHECK-NEXT: switch i128 [[A:%.*]], label [[COMMON_RET:%.*]] [ 43; CHECK-NEXT: i128 97, label [[ONE:%.*]] 44; CHECK-NEXT: i128 101, label [[TWO:%.*]] 45; CHECK-NEXT: i128 105, label [[THREE:%.*]] 46; CHECK-NEXT: i128 109, label [[THREE]] 47; CHECK-NEXT: ] 48; CHECK: common.ret: 49; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i128 [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ], [ 8867, [[TMP0:%.*]] ] 50; CHECK-NEXT: ret i128 [[COMMON_RET_OP]] 51; CHECK: one: 52; CHECK-NEXT: br label [[COMMON_RET]] 53; CHECK: two: 54; CHECK-NEXT: br label [[COMMON_RET]] 55; CHECK: three: 56; CHECK-NEXT: br label [[COMMON_RET]] 57; 58 switch i128 %a, label %def [ 59 i128 97, label %one 60 i128 101, label %two 61 i128 105, label %three 62 i128 109, label %three 63 ] 64 65def: 66 ret i128 8867 67 68one: 69 ret i128 11984 70two: 71 ret i128 1143 72three: 73 ret i128 99783 74} 75 76; Optimization shouldn't trigger; no holes present 77define i32 @test3(i32 %a) { 78; CHECK-LABEL: @test3( 79; CHECK-NEXT: [[SWITCH_TABLEIDX:%.*]] = sub i32 [[A:%.*]], 97 80; CHECK-NEXT: [[TMP1:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 3 81; CHECK-NEXT: br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]] 82; CHECK: switch.lookup: 83; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32], ptr @switch.table.test3, i32 0, i32 [[SWITCH_TABLEIDX]] 84; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4 85; CHECK-NEXT: br label [[COMMON_RET]] 86; CHECK: common.ret: 87; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ] 88; CHECK-NEXT: ret i32 [[COMMON_RET_OP]] 89; 90 switch i32 %a, label %def [ 91 i32 97, label %one 92 i32 98, label %two 93 i32 99, label %three 94 ] 95 96def: 97 ret i32 8867 98 99one: 100 ret i32 11984 101two: 102 ret i32 1143 103three: 104 ret i32 99783 105} 106 107; Optimization shouldn't trigger; not an arithmetic progression 108define i32 @test4(i32 %a) { 109; CHECK-LABEL: @test4( 110; CHECK-NEXT: switch i32 [[A:%.*]], label [[COMMON_RET:%.*]] [ 111; CHECK-NEXT: i32 97, label [[ONE:%.*]] 112; CHECK-NEXT: i32 102, label [[TWO:%.*]] 113; CHECK-NEXT: i32 105, label [[THREE:%.*]] 114; CHECK-NEXT: i32 109, label [[THREE]] 115; CHECK-NEXT: ] 116; CHECK: common.ret: 117; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i32 [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ], [ 8867, [[TMP0:%.*]] ] 118; CHECK-NEXT: ret i32 [[COMMON_RET_OP]] 119; CHECK: one: 120; CHECK-NEXT: br label [[COMMON_RET]] 121; CHECK: two: 122; CHECK-NEXT: br label [[COMMON_RET]] 123; CHECK: three: 124; CHECK-NEXT: br label [[COMMON_RET]] 125; 126 switch i32 %a, label %def [ 127 i32 97, label %one 128 i32 102, label %two 129 i32 105, label %three 130 i32 109, label %three 131 ] 132 133def: 134 ret i32 8867 135 136one: 137 ret i32 11984 138two: 139 ret i32 1143 140three: 141 ret i32 99783 142} 143 144; Optimization shouldn't trigger; not a power of two 145define i32 @test5(i32 %a) { 146; CHECK-LABEL: @test5( 147; CHECK-NEXT: switch i32 [[A:%.*]], label [[COMMON_RET:%.*]] [ 148; CHECK-NEXT: i32 97, label [[ONE:%.*]] 149; CHECK-NEXT: i32 102, label [[TWO:%.*]] 150; CHECK-NEXT: i32 107, label [[THREE:%.*]] 151; CHECK-NEXT: i32 112, label [[THREE]] 152; CHECK-NEXT: ] 153; CHECK: common.ret: 154; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i32 [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 99783, [[THREE]] ], [ 8867, [[TMP0:%.*]] ] 155; CHECK-NEXT: ret i32 [[COMMON_RET_OP]] 156; CHECK: one: 157; CHECK-NEXT: br label [[COMMON_RET]] 158; CHECK: two: 159; CHECK-NEXT: br label [[COMMON_RET]] 160; CHECK: three: 161; CHECK-NEXT: br label [[COMMON_RET]] 162; 163 switch i32 %a, label %def [ 164 i32 97, label %one 165 i32 102, label %two 166 i32 107, label %three 167 i32 112, label %three 168 ] 169 170def: 171 ret i32 8867 172 173one: 174 ret i32 11984 175two: 176 ret i32 1143 177three: 178 ret i32 99783 179} 180 181define i32 @test6(i32 %a) optsize { 182; CHECK-LABEL: @test6( 183; CHECK-NEXT: [[TMP1:%.*]] = sub i32 [[A:%.*]], -109 184; CHECK-NEXT: [[TMP2:%.*]] = call i32 @llvm.fshl.i32(i32 [[TMP1]], i32 [[TMP1]], i32 30) 185; CHECK-NEXT: [[TMP3:%.*]] = icmp ult i32 [[TMP2]], 4 186; CHECK-NEXT: br i1 [[TMP3]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]] 187; CHECK: switch.lookup: 188; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], ptr @switch.table.test6, i32 0, i32 [[TMP2]] 189; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4 190; CHECK-NEXT: br label [[COMMON_RET]] 191; CHECK: common.ret: 192; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ] 193; CHECK-NEXT: ret i32 [[COMMON_RET_OP]] 194; 195 switch i32 %a, label %def [ 196 i32 -97, label %one 197 i32 -101, label %two 198 i32 -105, label %three 199 i32 -109, label %three 200 ] 201 202def: 203 ret i32 8867 204 205one: 206 ret i32 11984 207two: 208 ret i32 1143 209three: 210 ret i32 99783 211} 212 213define i8 @test7(i8 %a) optsize { 214; CHECK-LABEL: @test7( 215; CHECK-NEXT: common.ret: 216; CHECK-NEXT: [[TMP0:%.*]] = sub i8 [[A:%.*]], -36 217; CHECK-NEXT: [[TMP1:%.*]] = call i8 @llvm.fshl.i8(i8 [[TMP0]], i8 [[TMP0]], i8 6) 218; CHECK-NEXT: [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 4 219; CHECK-NEXT: [[SWITCH_CAST:%.*]] = zext i8 [[TMP1]] to i32 220; CHECK-NEXT: [[SWITCH_SHIFTAMT:%.*]] = mul nuw nsw i32 [[SWITCH_CAST]], 8 221; CHECK-NEXT: [[SWITCH_DOWNSHIFT:%.*]] = lshr i32 -943228976, [[SWITCH_SHIFTAMT]] 222; CHECK-NEXT: [[SWITCH_MASKED:%.*]] = trunc i32 [[SWITCH_DOWNSHIFT]] to i8 223; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = select i1 [[TMP2]], i8 [[SWITCH_MASKED]], i8 -93 224; CHECK-NEXT: ret i8 [[COMMON_RET_OP]] 225; 226 switch i8 %a, label %def [ 227 i8 220, label %one 228 i8 224, label %two 229 i8 228, label %three 230 i8 232, label %three 231 ] 232 233def: 234 ret i8 8867 235 236one: 237 ret i8 11984 238two: 239 ret i8 1143 240three: 241 ret i8 99783 242} 243 244define i32 @test8(i32 %a) optsize { 245; CHECK-LABEL: @test8( 246; CHECK-NEXT: [[TMP1:%.*]] = sub i32 [[A:%.*]], 97 247; CHECK-NEXT: [[TMP2:%.*]] = call i32 @llvm.fshl.i32(i32 [[TMP1]], i32 [[TMP1]], i32 30) 248; CHECK-NEXT: [[TMP3:%.*]] = icmp ult i32 [[TMP2]], 5 249; CHECK-NEXT: br i1 [[TMP3]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]] 250; CHECK: switch.lookup: 251; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [5 x i32], ptr @switch.table.test8, i32 0, i32 [[TMP2]] 252; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4 253; CHECK-NEXT: br label [[COMMON_RET]] 254; CHECK: common.ret: 255; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ] 256; CHECK-NEXT: ret i32 [[COMMON_RET_OP]] 257; 258 switch i32 %a, label %def [ 259 i32 97, label %one 260 i32 101, label %two 261 i32 105, label %three 262 i32 113, label %three 263 ] 264 265def: 266 ret i32 8867 267 268one: 269 ret i32 11984 270two: 271 ret i32 1143 272three: 273 ret i32 99783 274} 275 276define i32 @test9(i32 %a) { 277; CHECK-LABEL: @test9( 278; CHECK-NEXT: [[TMP1:%.*]] = sub i32 [[A:%.*]], 6 279; CHECK-NEXT: [[TMP2:%.*]] = call i32 @llvm.fshl.i32(i32 [[TMP1]], i32 [[TMP1]], i32 31) 280; CHECK-NEXT: [[TMP3:%.*]] = icmp ult i32 [[TMP2]], 8 281; CHECK-NEXT: br i1 [[TMP3]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]] 282; CHECK: switch.lookup: 283; CHECK-NEXT: [[SWITCH_GEP:%.*]] = getelementptr inbounds [8 x i32], ptr @switch.table.test9, i32 0, i32 [[TMP2]] 284; CHECK-NEXT: [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4 285; CHECK-NEXT: br label [[COMMON_RET]] 286; CHECK: common.ret: 287; CHECK-NEXT: [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ] 288; CHECK-NEXT: ret i32 [[COMMON_RET_OP]] 289; 290 switch i32 %a, label %def [ 291 i32 18, label %one 292 i32 20, label %two 293 i32 6, label %three 294 i32 10, label %three 295 ] 296 297def: 298 ret i32 8867 299 300one: 301 ret i32 11984 302two: 303 ret i32 1143 304three: 305 ret i32 99783 306} 307 308