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