864 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py2; RUN: opt < %s -passes=lower-switch -S | FileCheck %s3 4; Check that we do not generate redundant comparisons that would have results5; 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 i210; CHECK-NEXT: br label [[NODEBLOCK:%.*]]11; CHECK: NodeBlock:12; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i2 [[TRUNC]], 113; CHECK-NEXT: br i1 [[PIVOT]], label [[LEAFBLOCK:%.*]], label [[CASE_1:%.*]]14; CHECK: LeafBlock:15; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i2 [[TRUNC]], -216; 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 i232 switch i2 %trunc, label %case.D [33 i2 1, label %case.1 ; i2 134 i2 2, label %case.2 ; i2 -235 ]36 ; It's known that %val can not be less than -2 or greater than 137 38case.1:39 %res1 = call i32 @case1()40 br label %exit41 42case.2:43 %res2 = call i32 @case2()44 br label %exit45 46case.D:47 %resD = call i32 @caseD()48 br label %exit49 50exit:51 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]52 ret i32 %res53}54 55; Check that we do not generate redundant comparisons that would have results56; 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]], 264; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]65; CHECK: LeafBlock:66; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 267; 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 !083 switch i32 %val, label %case.D [84 i32 1, label %case.185 i32 2, label %case.286 ]87 ; It's known that %val can not be less than 188 89case.1:90 %res1 = call i32 @case1()91 br label %exit92 93case.2:94 %res2 = call i32 @case2()95 br label %exit96 97case.D:98 %resD = call i32 @caseD()99 br label %exit100 101exit:102 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]103 ret i32 %res104}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]], 2116; 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 !1129 switch i32 %val, label %case.D [130 i32 1, label %case.1131 i32 2, label %case.2132 i32 3, label %case.1133 ]134 135case.1:136 %res1 = call i32 @case1()137 br label %exit138 139case.2:140 %res2 = call i32 @case2()141 br label %exit142 143case.D:144 %resD = call i32 @caseD()145 br label %exit146 147exit:148 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]149 ret i32 %res150}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 the155; 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]], 2163; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]164; CHECK: LeafBlock:165; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2166; 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 !2182 switch i32 %val, label %case.D [183 i32 1, label %case.1184 i32 2, label %case.2185 ]186 187case.1:188 %res1 = call i32 @case1()189 br label %exit190 191case.2:192 %res2 = call i32 @case2()193 br label %exit194 195case.D:196 %resD = call i32 @caseD()197 br label %exit198 199exit:200 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]201 ret i32 %res202}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 the207; range fully, but its basic block actually is reachable from the switch via208; 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]], 3218; CHECK-NEXT: br i1 [[PIVOT]], label [[LEAFBLOCK:%.*]], label [[CASE_1:%.*]]219; CHECK: LeafBlock:220; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1221; 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.D236 237switch:238 %val = call i32 @getVal(), !range !1239 switch i32 %val, label %case.D [240 i32 1, label %case.1241 i32 2, label %case.D242 i32 3, label %case.1243 ]244 245case.1:246 %res1 = call i32 @case1()247 br label %exit248 249case.D:250 %delta = phi i32 [ 0, %entry ], [ 20, %switch ], [ 20, %switch ]251 %resD.tmp = call i32 @caseD()252 %resD = add i32 %resD.tmp, %delta253 br label %exit254 255exit:256 %res = phi i32 [ %res1, %case.1 ], [ %resD, %case.D ]257 ret i32 %res258}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 the263; range fully, but its basic block actually is reachable, though, from a264; 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]], 2274; 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]], 0284; 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.D291 292switch:293 %val = call i32 @getVal(), !range !1294 switch i32 %val, label %case.D [295 i32 1, label %case.1296 i32 2, label %case.2297 i32 3, label %case.1298 ]299 300case.1:301 %res1 = call i32 @case1()302 br label %exit303 304case.2:305 %res2 = call i32 @case2()306 br label %exit307 308case.D:309 %delta = phi i32 [ 0, %entry ], [ 20, %switch ]310 %resD.tmp = call i32 @caseD()311 %resD = add i32 %resD.tmp, %delta312 br label %exit313 314exit:315 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]316 ret i32 %res317}318 319; Corner case:320; 1) switch appears to have a non-empty set of non-default cases, but all of321; 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.D339 340switch:341 %val = call i32 @getVal(), !range !1342 switch i32 %val, label %case.D [343 i32 2, label %case.D344 ]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, %delta350 br label %exit351 352exit:353 ret i32 %resD354}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 the359; range fully, but its basic block actually is reachable from the switch via360; one of the non-default cases,361; 3) such cases lie at the boundary of the range of values covered by362; non-default cases, and if removed, do not change the fact that the rest of363; 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]], 2373; 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]], 0383; 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.D390 391switch:392 %val = call i32 @getVal(), !range !3393 switch i32 %val, label %case.D [394 i32 1, label %case.1395 i32 2, label %case.2396 i32 3, label %case.D397 ]398 399case.1:400 %res1 = call i32 @case1()401 br label %exit402 403case.2:404 %res2 = call i32 @case2()405 br label %exit406 407case.D:408 %delta = phi i32 [ 0, %entry ], [ 20, %switch ], [ 20, %switch ]409 %resD.tmp = call i32 @caseD()410 %resD = add i32 %resD.tmp, %delta411 br label %exit412 413exit:414 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]415 ret i32 %res416}417 418; Corner case:419; 1) the default case appears to be unreachable as non-default cases cover the420; range fully, but its basic block actually is reachable from the switch via421; 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:%.*]], 0430; 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.D445 446switch:447 switch i2 %val, label %case.D [448 i2 0, label %case.1449 i2 1, label %case.1450 i2 2, label %case.D451 i2 3, label %case.D452 ]453 454case.1:455 %res1 = call i32 @case1()456 br label %exit457 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, %delta462 br label %exit463 464exit:465 %res = phi i32 [ %res1, %case.1 ], [ %resD, %case.D ]466 ret i32 %res467}468 469; Check that we do not generate redundant comparisons that would have results470; 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]], 1476; CHECK-NEXT: [[COND_RIGHT:%.*]] = icmp sle i32 [[VAL]], 6477; 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]], -3483; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp ule i32 [[VAL_OFF]], 1484; 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, 1500 %cond.right = icmp sle i32 %val, 6501 %cond = and i1 %cond.left, %cond.right502 br i1 %cond, label %switch, label %case.D503 504switch:505 switch i32 %val, label %case.D [506 i32 1, label %case.1507 i32 2, label %case.1508 i32 3, label %case.2509 i32 4, label %case.2510 i32 5, label %case.1511 i32 6, label %case.1512 ]513 ; It's known that %val <- [1, 6]514 515case.1:516 %res1 = call i32 @case1()517 br label %exit518 519case.2:520 %res2 = call i32 @case2()521 br label %exit522 523case.D:524 %resD = phi i32 [ 20, %switch ], [ 0, %entry ]525 br label %exit526 527exit:528 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]529 ret i32 %res530}531 532; Check that we do not generate redundant comparisons that would have results533; 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 i64539; CHECK-NEXT: br label [[NODEBLOCK:%.*]]540; CHECK: NodeBlock:541; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i64 [[VAL_ZEXT]], 1542; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]543; CHECK: LeafBlock:544; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i64 [[VAL_ZEXT]], 1545; 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 i64562 switch i64 %val.zext, label %case.D [563 i64 0, label %case.1564 i64 1, label %case.2565 ]566 ; It's known that %val can not be less than 0567 568case.1:569 %res1 = call i32 @case1()570 br label %exit571 572case.2:573 %res2 = call i32 @case2()574 br label %exit575 576case.D:577 %resD = call i32 @caseD()578 br label %exit579 580exit:581 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]582 ret i32 %res583}584 585; Check that we do not generate redundant comparisons that would have results586; 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]], 1596; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]597; CHECK: LeafBlock:598; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[INDVAR]], 1599; 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]], 1606; CHECK-NEXT: br i1 %arg, label [[EXIT:%.*]], label [[FOR_BODY]]607; CHECK: exit:608; CHECK-NEXT: ret void609;610entry:611 br label %for.body612 613for.body:614 %indvar = phi i32 [ 0, %entry ], [ %inc, %latch ]615 switch i32 %indvar, label %latch [616 i32 0, label %case.1617 i32 1, label %case.2618 ]619 ; It's known that %indvar can not be less than 0620 621case.1:622 br label %latch623 624case.2:625 br label %latch626 627latch:628 %inc = add nuw nsw i32 %indvar, 1629 br i1 %arg, label %exit, label %for.body630 631exit:632 ret void633}634 635; Check that we do not generate redundant comparisons that would have results636; 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:%.*]], 7641; 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]], -2646; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp ule i32 [[TMP_OFF]], 1647; 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]], 6654; CHECK-NEXT: br i1 [[PIVOT]], label [[LEAFBLOCK1:%.*]], label [[BB37:%.*]]655; CHECK: LeafBlock1:656; CHECK-NEXT: [[SWITCHLEAF2:%.*]] = icmp sle i32 [[TMP]], 1657; 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, 7665 br label %bb33666 667bb33:668 switch i32 %tmp, label %bb35 [669 i32 2, label %bb34670 i32 3, label %bb34671 ]672 673bb34:674 br label %bb38675 676bb35:677 switch i32 %tmp, label %bb38 [678 i32 0, label %bb37679 i32 1, label %bb37680 i32 6, label %bb37681 i32 7, label %bb37682 ]683 ; It's known that %tmp <- [0, 1] U [4, 7]684 685bb37:686 br label %bb38687 688bb38:689 br label %bb33690}691 692; Check that we do not generate redundant comparisons that would have results693; 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]], 1702; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]703; CHECK: LeafBlock:704; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1705; 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 !4721 %val = call i32 @llvm.ctpop.i32(i32 %tmp)722 switch i32 %val, label %case.D [723 i32 0, label %case.1724 i32 1, label %case.2725 ]726 ; It's known that %val <- [0, 2]727 728case.1:729 %res1 = call i32 @case1()730 br label %exit731 732case.2:733 %res2 = call i32 @case2()734 br label %exit735 736case.D:737 %resD = call i32 @caseD()738 br label %exit739 740exit:741 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]742 ret i32 %res743}744 745; Check that we do not generate redundant comparisons that would have results746; 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]], 3752; CHECK-NEXT: br label [[NODEBLOCK:%.*]]753; CHECK: NodeBlock:754; CHECK-NEXT: [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 1755; CHECK-NEXT: br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]756; CHECK: LeafBlock:757; CHECK-NEXT: [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1758; 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, 3775 switch i32 %val, label %case.D [776 i32 0, label %case.1777 i32 1, label %case.2778 ]779 ; It's known that %val <- [0, 2]780 781case.1:782 %res1 = call i32 @case1()783 br label %exit784 785case.2:786 %res2 = call i32 @case2()787 br label %exit788 789case.D:790 %resD = call i32 @caseD()791 br label %exit792 793exit:794 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]795 ret i32 %res796}797 798; Check that we do not generate redundant comparisons that would have results799; 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 i64804; CHECK-NEXT: [[COND_LEFT:%.*]] = icmp slt i64 [[I]], 0805; CHECK-NEXT: [[CLAMP_LEFT:%.*]] = select i1 [[COND_LEFT]], i64 0, i64 [[I]]806; CHECK-NEXT: [[COND_RIGHT:%.*]] = icmp sgt i64 [[I]], 3807; 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]], 2811; 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 i64824 %cond.left = icmp slt i64 %i, 0825 %clamp.left = select i1 %cond.left, i64 0, i64 %i826 %cond.right = icmp sgt i64 %i, 3827 %clamp = select i1 %cond.right, i64 3, i64 %clamp.left828 switch i64 %clamp, label %case.D [829 i64 0, label %case.1830 i64 1, label %case.1831 i64 2, label %case.2832 i64 3, label %case.2833 ]834 ; It's known that %val <- [0, 3]835 836case.1:837 %res1 = call i32 @case1()838 br label %exit839 840case.2:841 %res2 = call i32 @case2()842 br label %exit843 844case.D:845 %resD = call i32 @caseD()846 br label %exit847 848exit:849 %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]850 ret i32 %res851}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