1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py 2; RUN: opt < %s -passes=lower-switch -S | FileCheck %s 3 4; Check that we do not generate redundant comparisons that would have results 5; known at compile time due to limited range of the value being switch'ed over. 6define i32 @test1(i32 %val) { 7; CHECK-LABEL: @test1( 8; CHECK-NEXT: entry: 9; CHECK-NEXT: [[TRUNC:%.*]] = trunc i32 [[VAL:%.*]] to i2 10; CHECK-NEXT: br label [[NODEBLOCK:%.*]] 11; CHECK: NodeBlock: 12; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i2 [[TRUNC]], 1 13; CHECK-NEXT: br i1 [[PIVOT]], label [[LEAFBLOCK:%.*]], label [[CASE_1:%.*]] 14; CHECK: LeafBlock: 15; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i2 [[TRUNC]], -2 16; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[CASE_D:%.*]] 17; CHECK: case.1: 18; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1() 19; CHECK-NEXT: br label [[EXIT:%.*]] 20; CHECK: case.2: 21; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2() 22; CHECK-NEXT: br label [[EXIT]] 23; CHECK: case.D: 24; CHECK-NEXT: [[RESD:%.*]] = call i32 @caseD() 25; CHECK-NEXT: br label [[EXIT]] 26; CHECK: exit: 27; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ] 28; CHECK-NEXT: ret i32 [[RES]] 29; 30entry: 31 %trunc = trunc i32 %val to i2 32 switch i2 %trunc, label %case.D [ 33 i2 1, label %case.1 ; i2 1 34 i2 2, label %case.2 ; i2 -2 35 ] 36 ; It's known that %val can not be less than -2 or greater than 1 37 38case.1: 39 %res1 = call i32 @case1() 40 br label %exit 41 42case.2: 43 %res2 = call i32 @case2() 44 br label %exit 45 46case.D: 47 %resD = call i32 @caseD() 48 br label %exit 49 50exit: 51 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ] 52 ret i32 %res 53} 54 55; Check that we do not generate redundant comparisons that would have results 56; known at compile time due to limited range of the value being switch'ed over. 57define i32 @test2() { 58; CHECK-LABEL: @test2( 59; CHECK-NEXT: entry: 60; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal(), !range [[RNG0:![0-9]+]] 61; CHECK-NEXT: br label [[NODEBLOCK:%.*]] 62; CHECK: NodeBlock: 63; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 2 64; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]] 65; CHECK: LeafBlock: 66; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2 67; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[CASE_D:%.*]] 68; CHECK: case.1: 69; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1() 70; CHECK-NEXT: br label [[EXIT:%.*]] 71; CHECK: case.2: 72; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2() 73; CHECK-NEXT: br label [[EXIT]] 74; CHECK: case.D: 75; CHECK-NEXT: [[RESD:%.*]] = call i32 @caseD() 76; CHECK-NEXT: br label [[EXIT]] 77; CHECK: exit: 78; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ] 79; CHECK-NEXT: ret i32 [[RES]] 80; 81entry: 82 %val = call i32 @getVal(), !range !0 83 switch i32 %val, label %case.D [ 84 i32 1, label %case.1 85 i32 2, label %case.2 86 ] 87 ; It's known that %val can not be less than 1 88 89case.1: 90 %res1 = call i32 @case1() 91 br label %exit 92 93case.2: 94 %res2 = call i32 @case2() 95 br label %exit 96 97case.D: 98 %resD = call i32 @caseD() 99 br label %exit 100 101exit: 102 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ] 103 ret i32 %res 104} 105 106; Corner case: 107; 1) some of the non-default cases are unreachable due to the !range constraint, 108; 2) the default case is unreachable as non-default cases cover the range fully. 109define i32 @test3() { 110; CHECK-LABEL: @test3( 111; CHECK-NEXT: entry: 112; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal(), !range [[RNG1:![0-9]+]] 113; CHECK-NEXT: br label [[LEAFBLOCK:%.*]] 114; CHECK: LeafBlock: 115; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2 116; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[CASE_1:%.*]] 117; CHECK: case.1: 118; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1() 119; CHECK-NEXT: br label [[EXIT:%.*]] 120; CHECK: case.2: 121; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2() 122; CHECK-NEXT: br label [[EXIT]] 123; CHECK: exit: 124; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ] 125; CHECK-NEXT: ret i32 [[RES]] 126; 127entry: 128 %val = call i32 @getVal(), !range !1 129 switch i32 %val, label %case.D [ 130 i32 1, label %case.1 131 i32 2, label %case.2 132 i32 3, label %case.1 133 ] 134 135case.1: 136 %res1 = call i32 @case1() 137 br label %exit 138 139case.2: 140 %res2 = call i32 @case2() 141 br label %exit 142 143case.D: 144 %resD = call i32 @caseD() 145 br label %exit 146 147exit: 148 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ] 149 ret i32 %res 150} 151 152; Corner case: 153; 1) some of the non-default cases are unreachable due to the !range constraint, 154; 2) the default case is still reachable as non-default cases do not cover the 155; range fully. 156define i32 @test4() { 157; CHECK-LABEL: @test4( 158; CHECK-NEXT: entry: 159; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal(), !range [[RNG2:![0-9]+]] 160; CHECK-NEXT: br label [[NODEBLOCK:%.*]] 161; CHECK: NodeBlock: 162; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 2 163; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]] 164; CHECK: LeafBlock: 165; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2 166; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[CASE_D:%.*]] 167; CHECK: case.1: 168; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1() 169; CHECK-NEXT: br label [[EXIT:%.*]] 170; CHECK: case.2: 171; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2() 172; CHECK-NEXT: br label [[EXIT]] 173; CHECK: case.D: 174; CHECK-NEXT: [[RESD:%.*]] = call i32 @caseD() 175; CHECK-NEXT: br label [[EXIT]] 176; CHECK: exit: 177; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ] 178; CHECK-NEXT: ret i32 [[RES]] 179; 180entry: 181 %val = call i32 @getVal(), !range !2 182 switch i32 %val, label %case.D [ 183 i32 1, label %case.1 184 i32 2, label %case.2 185 ] 186 187case.1: 188 %res1 = call i32 @case1() 189 br label %exit 190 191case.2: 192 %res2 = call i32 @case2() 193 br label %exit 194 195case.D: 196 %resD = call i32 @caseD() 197 br label %exit 198 199exit: 200 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ] 201 ret i32 %res 202} 203 204; Corner case: 205; 1) some of the non-default cases are unreachable due to the !range constraint, 206; 2) the default case appears to be unreachable as non-default cases cover the 207; range fully, but its basic block actually is reachable from the switch via 208; one of the non-default cases. 209define i32 @test5(i1 %cond) { 210; CHECK-LABEL: @test5( 211; CHECK-NEXT: entry: 212; CHECK-NEXT: br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]] 213; CHECK: switch: 214; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal(), !range [[RNG1]] 215; CHECK-NEXT: br label [[NODEBLOCK:%.*]] 216; CHECK: NodeBlock: 217; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 3 218; CHECK-NEXT: br i1 [[PIVOT]], label [[LEAFBLOCK:%.*]], label [[CASE_1:%.*]] 219; CHECK: LeafBlock: 220; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1 221; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_1]], label [[CASE_D]] 222; CHECK: case.1: 223; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1() 224; CHECK-NEXT: br label [[EXIT:%.*]] 225; CHECK: case.D: 226; CHECK-NEXT: [[DELTA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 20, [[LEAFBLOCK]] ] 227; CHECK-NEXT: [[RESD_TMP:%.*]] = call i32 @caseD() 228; CHECK-NEXT: [[RESD:%.*]] = add i32 [[RESD_TMP]], [[DELTA]] 229; CHECK-NEXT: br label [[EXIT]] 230; CHECK: exit: 231; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RESD]], [[CASE_D]] ] 232; CHECK-NEXT: ret i32 [[RES]] 233; 234entry: 235 br i1 %cond, label %switch, label %case.D 236 237switch: 238 %val = call i32 @getVal(), !range !1 239 switch i32 %val, label %case.D [ 240 i32 1, label %case.1 241 i32 2, label %case.D 242 i32 3, label %case.1 243 ] 244 245case.1: 246 %res1 = call i32 @case1() 247 br label %exit 248 249case.D: 250 %delta = phi i32 [ 0, %entry ], [ 20, %switch ], [ 20, %switch ] 251 %resD.tmp = call i32 @caseD() 252 %resD = add i32 %resD.tmp, %delta 253 br label %exit 254 255exit: 256 %res = phi i32 [ %res1, %case.1 ], [ %resD, %case.D ] 257 ret i32 %res 258} 259 260; Corner case: 261; 1) some of the non-default cases are unreachable due to the !range constraint, 262; 2) the default case appears to be unreachable as non-default cases cover the 263; range fully, but its basic block actually is reachable, though, from a 264; different basic block, not the switch itself. 265define i32 @test6(i1 %cond) { 266; CHECK-LABEL: @test6( 267; CHECK-NEXT: entry: 268; CHECK-NEXT: br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]] 269; CHECK: switch: 270; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal(), !range [[RNG1]] 271; CHECK-NEXT: br label [[LEAFBLOCK:%.*]] 272; CHECK: LeafBlock: 273; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2 274; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[CASE_1:%.*]] 275; CHECK: case.1: 276; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1() 277; CHECK-NEXT: br label [[EXIT:%.*]] 278; CHECK: case.2: 279; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2() 280; CHECK-NEXT: br label [[EXIT]] 281; CHECK: case.D: 282; CHECK-NEXT: [[RESD_TMP:%.*]] = call i32 @caseD() 283; CHECK-NEXT: [[RESD:%.*]] = add i32 [[RESD_TMP]], 0 284; CHECK-NEXT: br label [[EXIT]] 285; CHECK: exit: 286; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ] 287; CHECK-NEXT: ret i32 [[RES]] 288; 289entry: 290 br i1 %cond, label %switch, label %case.D 291 292switch: 293 %val = call i32 @getVal(), !range !1 294 switch i32 %val, label %case.D [ 295 i32 1, label %case.1 296 i32 2, label %case.2 297 i32 3, label %case.1 298 ] 299 300case.1: 301 %res1 = call i32 @case1() 302 br label %exit 303 304case.2: 305 %res2 = call i32 @case2() 306 br label %exit 307 308case.D: 309 %delta = phi i32 [ 0, %entry ], [ 20, %switch ] 310 %resD.tmp = call i32 @caseD() 311 %resD = add i32 %resD.tmp, %delta 312 br label %exit 313 314exit: 315 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ] 316 ret i32 %res 317} 318 319; Corner case: 320; 1) switch appears to have a non-empty set of non-default cases, but all of 321; them reference the default case basic block. 322define i32 @test7(i1 %cond) { 323; CHECK-LABEL: @test7( 324; CHECK-NEXT: entry: 325; CHECK-NEXT: br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]] 326; CHECK: switch: 327; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal(), !range [[RNG1]] 328; CHECK-NEXT: br label [[CASE_D]] 329; CHECK: case.D: 330; CHECK-NEXT: [[DELTA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 20, [[SWITCH]] ] 331; CHECK-NEXT: [[RESD_TMP:%.*]] = call i32 @caseD() 332; CHECK-NEXT: [[RESD:%.*]] = add i32 [[RESD_TMP]], [[DELTA]] 333; CHECK-NEXT: br label [[EXIT:%.*]] 334; CHECK: exit: 335; CHECK-NEXT: ret i32 [[RESD]] 336; 337entry: 338 br i1 %cond, label %switch, label %case.D 339 340switch: 341 %val = call i32 @getVal(), !range !1 342 switch i32 %val, label %case.D [ 343 i32 2, label %case.D 344 ] 345 346case.D: 347 %delta = phi i32 [ 0, %entry ], [ 20, %switch ], [ 20, %switch ] 348 %resD.tmp = call i32 @caseD() 349 %resD = add i32 %resD.tmp, %delta 350 br label %exit 351 352exit: 353 ret i32 %resD 354} 355 356; Corner case: 357; 1) some of the non-default cases are unreachable due to the !range constraint, 358; 2) the default case appears to be unreachable as non-default cases cover the 359; range fully, but its basic block actually is reachable from the switch via 360; one of the non-default cases, 361; 3) such cases lie at the boundary of the range of values covered by 362; non-default cases, and if removed, do not change the fact that the rest of 363; the cases fully covers the value range. 364define i32 @test8(i1 %cond) { 365; CHECK-LABEL: @test8( 366; CHECK-NEXT: entry: 367; CHECK-NEXT: br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]] 368; CHECK: switch: 369; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal(), !range [[RNG3:![0-9]+]] 370; CHECK-NEXT: br label [[LEAFBLOCK:%.*]] 371; CHECK: LeafBlock: 372; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2 373; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[CASE_1:%.*]] 374; CHECK: case.1: 375; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1() 376; CHECK-NEXT: br label [[EXIT:%.*]] 377; CHECK: case.2: 378; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2() 379; CHECK-NEXT: br label [[EXIT]] 380; CHECK: case.D: 381; CHECK-NEXT: [[RESD_TMP:%.*]] = call i32 @caseD() 382; CHECK-NEXT: [[RESD:%.*]] = add i32 [[RESD_TMP]], 0 383; CHECK-NEXT: br label [[EXIT]] 384; CHECK: exit: 385; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ] 386; CHECK-NEXT: ret i32 [[RES]] 387; 388entry: 389 br i1 %cond, label %switch, label %case.D 390 391switch: 392 %val = call i32 @getVal(), !range !3 393 switch i32 %val, label %case.D [ 394 i32 1, label %case.1 395 i32 2, label %case.2 396 i32 3, label %case.D 397 ] 398 399case.1: 400 %res1 = call i32 @case1() 401 br label %exit 402 403case.2: 404 %res2 = call i32 @case2() 405 br label %exit 406 407case.D: 408 %delta = phi i32 [ 0, %entry ], [ 20, %switch ], [ 20, %switch ] 409 %resD.tmp = call i32 @caseD() 410 %resD = add i32 %resD.tmp, %delta 411 br label %exit 412 413exit: 414 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ] 415 ret i32 %res 416} 417 418; Corner case: 419; 1) the default case appears to be unreachable as non-default cases cover the 420; range fully, but its basic block actually is reachable from the switch via 421; more than one non-default case. 422define i32 @test9(i1 %cond, i2 %val) { 423; CHECK-LABEL: @test9( 424; CHECK-NEXT: entry: 425; CHECK-NEXT: br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]] 426; CHECK: switch: 427; CHECK-NEXT: br label [[LEAFBLOCK:%.*]] 428; CHECK: LeafBlock: 429; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp sge i2 [[VAL:%.*]], 0 430; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_1:%.*]], label [[CASE_D]] 431; CHECK: case.1: 432; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1() 433; CHECK-NEXT: br label [[EXIT:%.*]] 434; CHECK: case.D: 435; CHECK-NEXT: [[DELTA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 20, [[LEAFBLOCK]] ] 436; CHECK-NEXT: [[RESD_TMP:%.*]] = call i32 @caseD() 437; CHECK-NEXT: [[RESD:%.*]] = add i32 [[RESD_TMP]], [[DELTA]] 438; CHECK-NEXT: br label [[EXIT]] 439; CHECK: exit: 440; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RESD]], [[CASE_D]] ] 441; CHECK-NEXT: ret i32 [[RES]] 442; 443entry: 444 br i1 %cond, label %switch, label %case.D 445 446switch: 447 switch i2 %val, label %case.D [ 448 i2 0, label %case.1 449 i2 1, label %case.1 450 i2 2, label %case.D 451 i2 3, label %case.D 452 ] 453 454case.1: 455 %res1 = call i32 @case1() 456 br label %exit 457 458case.D: 459 %delta = phi i32 [20, %switch ], [ 20, %switch ], [ 20, %switch ], [ 0, %entry ] 460 %resD.tmp = call i32 @caseD() 461 %resD = add i32 %resD.tmp, %delta 462 br label %exit 463 464exit: 465 %res = phi i32 [ %res1, %case.1 ], [ %resD, %case.D ] 466 ret i32 %res 467} 468 469; Check that we do not generate redundant comparisons that would have results 470; known at compile time due to limited range of the value being switch'ed over. 471define i32 @test10() { 472; CHECK-LABEL: @test10( 473; CHECK-NEXT: entry: 474; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal() 475; CHECK-NEXT: [[COND_LEFT:%.*]] = icmp sge i32 [[VAL]], 1 476; CHECK-NEXT: [[COND_RIGHT:%.*]] = icmp sle i32 [[VAL]], 6 477; CHECK-NEXT: [[COND:%.*]] = and i1 [[COND_LEFT]], [[COND_RIGHT]] 478; CHECK-NEXT: br i1 [[COND]], label [[SWITCH:%.*]], label [[CASE_D:%.*]] 479; CHECK: switch: 480; CHECK-NEXT: br label [[LEAFBLOCK:%.*]] 481; CHECK: LeafBlock: 482; CHECK-NEXT: [[VAL_OFF:%.*]] = add i32 [[VAL]], -3 483; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp ule i32 [[VAL_OFF]], 1 484; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[CASE_1:%.*]] 485; CHECK: case.1: 486; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1() 487; CHECK-NEXT: br label [[EXIT:%.*]] 488; CHECK: case.2: 489; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2() 490; CHECK-NEXT: br label [[EXIT]] 491; CHECK: case.D: 492; CHECK-NEXT: br label [[EXIT]] 493; CHECK: exit: 494; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ 0, [[CASE_D]] ] 495; CHECK-NEXT: ret i32 [[RES]] 496; 497entry: 498 %val = call i32 @getVal() 499 %cond.left = icmp sge i32 %val, 1 500 %cond.right = icmp sle i32 %val, 6 501 %cond = and i1 %cond.left, %cond.right 502 br i1 %cond, label %switch, label %case.D 503 504switch: 505 switch i32 %val, label %case.D [ 506 i32 1, label %case.1 507 i32 2, label %case.1 508 i32 3, label %case.2 509 i32 4, label %case.2 510 i32 5, label %case.1 511 i32 6, label %case.1 512 ] 513 ; It's known that %val <- [1, 6] 514 515case.1: 516 %res1 = call i32 @case1() 517 br label %exit 518 519case.2: 520 %res2 = call i32 @case2() 521 br label %exit 522 523case.D: 524 %resD = phi i32 [ 20, %switch ], [ 0, %entry ] 525 br label %exit 526 527exit: 528 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ] 529 ret i32 %res 530} 531 532; Check that we do not generate redundant comparisons that would have results 533; known at compile time due to limited range of the value being switch'ed over. 534define i32 @test11() { 535; CHECK-LABEL: @test11( 536; CHECK-NEXT: entry: 537; CHECK-NEXT: [[VAL:%.*]] = call i32 @getVal() 538; CHECK-NEXT: [[VAL_ZEXT:%.*]] = zext i32 [[VAL]] to i64 539; CHECK-NEXT: br label [[NODEBLOCK:%.*]] 540; CHECK: NodeBlock: 541; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i64 [[VAL_ZEXT]], 1 542; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]] 543; CHECK: LeafBlock: 544; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i64 [[VAL_ZEXT]], 1 545; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[CASE_D:%.*]] 546; CHECK: case.1: 547; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1() 548; CHECK-NEXT: br label [[EXIT:%.*]] 549; CHECK: case.2: 550; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2() 551; CHECK-NEXT: br label [[EXIT]] 552; CHECK: case.D: 553; CHECK-NEXT: [[RESD:%.*]] = call i32 @caseD() 554; CHECK-NEXT: br label [[EXIT]] 555; CHECK: exit: 556; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ] 557; CHECK-NEXT: ret i32 [[RES]] 558; 559entry: 560 %val = call i32 @getVal() 561 %val.zext = zext i32 %val to i64 562 switch i64 %val.zext, label %case.D [ 563 i64 0, label %case.1 564 i64 1, label %case.2 565 ] 566 ; It's known that %val can not be less than 0 567 568case.1: 569 %res1 = call i32 @case1() 570 br label %exit 571 572case.2: 573 %res2 = call i32 @case2() 574 br label %exit 575 576case.D: 577 %resD = call i32 @caseD() 578 br label %exit 579 580exit: 581 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ] 582 ret i32 %res 583} 584 585; Check that we do not generate redundant comparisons that would have results 586; known at compile time due to limited range of the value being switch'ed over. 587define void @test12(i1 %arg) { 588; CHECK-LABEL: @test12( 589; CHECK-NEXT: entry: 590; CHECK-NEXT: br label [[FOR_BODY:%.*]] 591; CHECK: for.body: 592; CHECK-NEXT: [[INDVAR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[LATCH:%.*]] ] 593; CHECK-NEXT: br label [[NODEBLOCK:%.*]] 594; CHECK: NodeBlock: 595; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[INDVAR]], 1 596; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]] 597; CHECK: LeafBlock: 598; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[INDVAR]], 1 599; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[LATCH]] 600; CHECK: case.1: 601; CHECK-NEXT: br label [[LATCH]] 602; CHECK: case.2: 603; CHECK-NEXT: br label [[LATCH]] 604; CHECK: latch: 605; CHECK-NEXT: [[INC]] = add nuw nsw i32 [[INDVAR]], 1 606; CHECK-NEXT: br i1 %arg, label [[EXIT:%.*]], label [[FOR_BODY]] 607; CHECK: exit: 608; CHECK-NEXT: ret void 609; 610entry: 611 br label %for.body 612 613for.body: 614 %indvar = phi i32 [ 0, %entry ], [ %inc, %latch ] 615 switch i32 %indvar, label %latch [ 616 i32 0, label %case.1 617 i32 1, label %case.2 618 ] 619 ; It's known that %indvar can not be less than 0 620 621case.1: 622 br label %latch 623 624case.2: 625 br label %latch 626 627latch: 628 %inc = add nuw nsw i32 %indvar, 1 629 br i1 %arg, label %exit, label %for.body 630 631exit: 632 ret void 633} 634 635; Check that we do not generate redundant comparisons that would have results 636; known at compile time due to limited range of the value being switch'ed over. 637define void @test13(i32 %val) { 638; CHECK-LABEL: @test13( 639; CHECK-NEXT: entry: 640; CHECK-NEXT: [[TMP:%.*]] = and i32 [[VAL:%.*]], 7 641; CHECK-NEXT: br label [[BB33:%.*]] 642; CHECK: bb33: 643; CHECK-NEXT: br label [[LEAFBLOCK:%.*]] 644; CHECK: LeafBlock: 645; CHECK-NEXT: [[TMP_OFF:%.*]] = add i32 [[TMP]], -2 646; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp ule i32 [[TMP_OFF]], 1 647; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[BB34:%.*]], label [[BB35:%.*]] 648; CHECK: bb34: 649; CHECK-NEXT: br label [[BB38:%.*]] 650; CHECK: bb35: 651; CHECK-NEXT: br label [[NODEBLOCK:%.*]] 652; CHECK: NodeBlock: 653; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[TMP]], 6 654; CHECK-NEXT: br i1 [[PIVOT]], label [[LEAFBLOCK1:%.*]], label [[BB37:%.*]] 655; CHECK: LeafBlock1: 656; CHECK-NEXT: [[SWITCHLEAF2:%.*]] = icmp sle i32 [[TMP]], 1 657; CHECK-NEXT: br i1 [[SWITCHLEAF2]], label [[BB37]], label [[BB38]] 658; CHECK: bb37: 659; CHECK-NEXT: br label [[BB38]] 660; CHECK: bb38: 661; CHECK-NEXT: br label [[BB33]] 662; 663entry: 664 %tmp = and i32 %val, 7 665 br label %bb33 666 667bb33: 668 switch i32 %tmp, label %bb35 [ 669 i32 2, label %bb34 670 i32 3, label %bb34 671 ] 672 673bb34: 674 br label %bb38 675 676bb35: 677 switch i32 %tmp, label %bb38 [ 678 i32 0, label %bb37 679 i32 1, label %bb37 680 i32 6, label %bb37 681 i32 7, label %bb37 682 ] 683 ; It's known that %tmp <- [0, 1] U [4, 7] 684 685bb37: 686 br label %bb38 687 688bb38: 689 br label %bb33 690} 691 692; Check that we do not generate redundant comparisons that would have results 693; known at compile time due to limited range of the value being switch'ed over. 694define i32 @test14() { 695; CHECK-LABEL: @test14( 696; CHECK-NEXT: entry: 697; CHECK-NEXT: [[TMP:%.*]] = call i32 @getVal(), !range [[RNG4:![0-9]+]] 698; CHECK-NEXT: [[VAL:%.*]] = call i32 @llvm.ctpop.i32(i32 [[TMP]]) 699; CHECK-NEXT: br label [[NODEBLOCK:%.*]] 700; CHECK: NodeBlock: 701; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 1 702; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]] 703; CHECK: LeafBlock: 704; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1 705; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[CASE_D:%.*]] 706; CHECK: case.1: 707; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1() 708; CHECK-NEXT: br label [[EXIT:%.*]] 709; CHECK: case.2: 710; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2() 711; CHECK-NEXT: br label [[EXIT]] 712; CHECK: case.D: 713; CHECK-NEXT: [[RESD:%.*]] = call i32 @caseD() 714; CHECK-NEXT: br label [[EXIT]] 715; CHECK: exit: 716; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ] 717; CHECK-NEXT: ret i32 [[RES]] 718; 719entry: 720 %tmp = call i32 @getVal(), !range !4 721 %val = call i32 @llvm.ctpop.i32(i32 %tmp) 722 switch i32 %val, label %case.D [ 723 i32 0, label %case.1 724 i32 1, label %case.2 725 ] 726 ; It's known that %val <- [0, 2] 727 728case.1: 729 %res1 = call i32 @case1() 730 br label %exit 731 732case.2: 733 %res2 = call i32 @case2() 734 br label %exit 735 736case.D: 737 %resD = call i32 @caseD() 738 br label %exit 739 740exit: 741 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ] 742 ret i32 %res 743} 744 745; Check that we do not generate redundant comparisons that would have results 746; known at compile time due to limited range of the value being switch'ed over. 747define i32 @test15() { 748; CHECK-LABEL: @test15( 749; CHECK-NEXT: entry: 750; CHECK-NEXT: [[TMP:%.*]] = call i32 @getVal() 751; CHECK-NEXT: [[VAL:%.*]] = urem i32 [[TMP]], 3 752; CHECK-NEXT: br label [[NODEBLOCK:%.*]] 753; CHECK: NodeBlock: 754; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 1 755; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]] 756; CHECK: LeafBlock: 757; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1 758; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[CASE_D:%.*]] 759; CHECK: case.1: 760; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1() 761; CHECK-NEXT: br label [[EXIT:%.*]] 762; CHECK: case.2: 763; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2() 764; CHECK-NEXT: br label [[EXIT]] 765; CHECK: case.D: 766; CHECK-NEXT: [[RESD:%.*]] = call i32 @caseD() 767; CHECK-NEXT: br label [[EXIT]] 768; CHECK: exit: 769; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ] 770; CHECK-NEXT: ret i32 [[RES]] 771; 772entry: 773 %tmp = call i32 @getVal() 774 %val = urem i32 %tmp, 3 775 switch i32 %val, label %case.D [ 776 i32 0, label %case.1 777 i32 1, label %case.2 778 ] 779 ; It's known that %val <- [0, 2] 780 781case.1: 782 %res1 = call i32 @case1() 783 br label %exit 784 785case.2: 786 %res2 = call i32 @case2() 787 br label %exit 788 789case.D: 790 %resD = call i32 @caseD() 791 br label %exit 792 793exit: 794 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ] 795 ret i32 %res 796} 797 798; Check that we do not generate redundant comparisons that would have results 799; known at compile time due to limited range of the value being switch'ed over. 800define i32 @test16(float %f) { 801; CHECK-LABEL: @test16( 802; CHECK-NEXT: entry: 803; CHECK-NEXT: [[I:%.*]] = fptosi float [[F:%.*]] to i64 804; CHECK-NEXT: [[COND_LEFT:%.*]] = icmp slt i64 [[I]], 0 805; CHECK-NEXT: [[CLAMP_LEFT:%.*]] = select i1 [[COND_LEFT]], i64 0, i64 [[I]] 806; CHECK-NEXT: [[COND_RIGHT:%.*]] = icmp sgt i64 [[I]], 3 807; CHECK-NEXT: [[CLAMP:%.*]] = select i1 [[COND_RIGHT]], i64 3, i64 [[CLAMP_LEFT]] 808; CHECK-NEXT: br label [[LEAFBLOCK:%.*]] 809; CHECK: LeafBlock: 810; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp sge i64 [[CLAMP]], 2 811; CHECK-NEXT: br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[CASE_1:%.*]] 812; CHECK: case.1: 813; CHECK-NEXT: [[RES1:%.*]] = call i32 @case1() 814; CHECK-NEXT: br label [[EXIT:%.*]] 815; CHECK: case.2: 816; CHECK-NEXT: [[RES2:%.*]] = call i32 @case2() 817; CHECK-NEXT: br label [[EXIT]] 818; CHECK: exit: 819; CHECK-NEXT: [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ] 820; CHECK-NEXT: ret i32 [[RES]] 821; 822entry: 823 %i = fptosi float %f to i64 824 %cond.left = icmp slt i64 %i, 0 825 %clamp.left = select i1 %cond.left, i64 0, i64 %i 826 %cond.right = icmp sgt i64 %i, 3 827 %clamp = select i1 %cond.right, i64 3, i64 %clamp.left 828 switch i64 %clamp, label %case.D [ 829 i64 0, label %case.1 830 i64 1, label %case.1 831 i64 2, label %case.2 832 i64 3, label %case.2 833 ] 834 ; It's known that %val <- [0, 3] 835 836case.1: 837 %res1 = call i32 @case1() 838 br label %exit 839 840case.2: 841 %res2 = call i32 @case2() 842 br label %exit 843 844case.D: 845 %resD = call i32 @caseD() 846 br label %exit 847 848exit: 849 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ] 850 ret i32 %res 851} 852 853declare i32 @case1() 854declare i32 @case2() 855declare i32 @caseD() 856declare i32 @getVal() 857declare i32 @llvm.ctpop.i32(i32) 858 859!0 = !{i32 1, i32 257} 860!1 = !{i32 2, i32 3} 861!2 = !{i32 2, i32 257} 862!3 = !{i32 1, i32 3} 863!4 = !{i32 0, i32 4} 864