1 files changed, 895 insertions, 0 deletions
diff --git a/llvm/test/Transforms/LowerSwitch/do-not-handle-impossible-values.ll b/llvm/test/Transforms/LowerSwitch/do-not-handle-impossible-values.ll
new file mode 100644
index 00000000000..71c1ec7ee29
--- /dev/null
+++ b/llvm/test/Transforms/LowerSwitch/do-not-handle-impossible-values.ll
@@ -0,0 +1,895 @@
+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt < %s -lowerswitch -S | FileCheck %s
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define i32 @test1(i32 %val) {
+; CHECK-LABEL: @test1(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TRUNC:%.*]] = trunc i32 [[VAL:%.*]] to i2
+; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
+; CHECK:       NodeBlock:
+; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i2 [[TRUNC]], 1
+; CHECK-NEXT:    br i1 [[PIVOT]], label [[LEAFBLOCK:%.*]], label [[CASE_1:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i2 [[TRUNC]], -2
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK:       case.1:
+; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       case.2:
+; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[CASE_D:%.*]]
+; CHECK:       case.D:
+; CHECK-NEXT:    [[RESD:%.*]] = call i32 @caseD()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+entry:
+  %trunc = trunc i32 %val to i2
+  switch i2 %trunc, label %case.D [
+  i2 1, label %case.1  ; i2  1
+  i2 2, label %case.2  ; i2 -2
+  ]
+  ; It's known that %val can not be less than -2 or greater than 1
+
+case.1:
+  %res1 = call i32 @case1()
+  br label %exit
+
+case.2:
+  %res2 = call i32 @case2()
+  br label %exit
+
+case.D:
+  %resD = call i32 @caseD()
+  br label %exit
+
+exit:
+  %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+  ret i32 %res
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define i32 @test2() {
+; CHECK-LABEL: @test2(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal(), !range !0
+; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
+; CHECK:       NodeBlock:
+; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 2
+; CHECK-NEXT:    br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK:       case.1:
+; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       case.2:
+; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[CASE_D:%.*]]
+; CHECK:       case.D:
+; CHECK-NEXT:    [[RESD:%.*]] = call i32 @caseD()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+entry:
+  %val = call i32 @getVal(), !range !0
+  switch i32 %val, label %case.D [
+  i32 1, label %case.1
+  i32 2, label %case.2
+  ]
+  ; It's known that %val can not be less than 1
+
+case.1:
+  %res1 = call i32 @case1()
+  br label %exit
+
+case.2:
+  %res2 = call i32 @case2()
+  br label %exit
+
+case.D:
+  %resD = call i32 @caseD()
+  br label %exit
+
+exit:
+  %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+  ret i32 %res
+}
+
+; Corner case:
+; 1) some of the non-default cases are unreachable due to the !range constraint,
+; 2) the default case is unreachable as non-default cases cover the range fully.
+define i32 @test3() {
+; CHECK-LABEL: @test3(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal(), !range !1
+; CHECK-NEXT:    br label [[LEAFBLOCK:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[CASE_1:%.*]]
+; CHECK:       case.1:
+; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       case.2:
+; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+entry:
+  %val = call i32 @getVal(), !range !1
+  switch i32 %val, label %case.D [
+  i32 1, label %case.1
+  i32 2, label %case.2
+  i32 3, label %case.1
+  ]
+
+case.1:
+  %res1 = call i32 @case1()
+  br label %exit
+
+case.2:
+  %res2 = call i32 @case2()
+  br label %exit
+
+case.D:
+  %resD = call i32 @caseD()
+  br label %exit
+
+exit:
+  %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+  ret i32 %res
+}
+
+; Corner case:
+; 1) some of the non-default cases are unreachable due to the !range constraint,
+; 2) the default case is still reachable as non-default cases do not cover the
+;    range fully.
+define i32 @test4() {
+; CHECK-LABEL: @test4(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal(), !range !2
+; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
+; CHECK:       NodeBlock:
+; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 2
+; CHECK-NEXT:    br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK:       case.1:
+; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       case.2:
+; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[CASE_D:%.*]]
+; CHECK:       case.D:
+; CHECK-NEXT:    [[RESD:%.*]] = call i32 @caseD()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+entry:
+  %val = call i32 @getVal(), !range !2
+  switch i32 %val, label %case.D [
+  i32 1, label %case.1
+  i32 2, label %case.2
+  ]
+
+case.1:
+  %res1 = call i32 @case1()
+  br label %exit
+
+case.2:
+  %res2 = call i32 @case2()
+  br label %exit
+
+case.D:
+  %resD = call i32 @caseD()
+  br label %exit
+
+exit:
+  %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+  ret i32 %res
+}
+
+; Corner case:
+; 1) some of the non-default cases are unreachable due to the !range constraint,
+; 2) the default case appears to be unreachable as non-default cases cover the
+;    range fully, but its basic block actually is reachable from the switch via
+;    one of the non-default cases.
+define i32 @test5(i1 %cond) {
+; CHECK-LABEL: @test5(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
+; CHECK:       switch:
+; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal(), !range !1
+; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
+; CHECK:       NodeBlock:
+; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 3
+; CHECK-NEXT:    br i1 [[PIVOT]], label [[LEAFBLOCK:%.*]], label [[CASE_1:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_1]], label [[NEWDEFAULT:%.*]]
+; CHECK:       case.1:
+; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[CASE_D]]
+; CHECK:       case.D:
+; CHECK-NEXT:    [[DELTA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 20, [[NEWDEFAULT]] ]
+; CHECK-NEXT:    [[RESD_TMP:%.*]] = call i32 @caseD()
+; CHECK-NEXT:    [[RESD:%.*]] = add i32 [[RESD_TMP]], [[DELTA]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+entry:
+  br i1 %cond, label %switch, label %case.D
+
+switch:
+  %val = call i32 @getVal(), !range !1
+  switch i32 %val, label %case.D [
+  i32 1, label %case.1
+  i32 2, label %case.D
+  i32 3, label %case.1
+  ]
+
+case.1:
+  %res1 = call i32 @case1()
+  br label %exit
+
+case.D:
+  %delta = phi i32 [ 0, %entry ], [ 20, %switch ], [ 20, %switch ]
+  %resD.tmp = call i32 @caseD()
+  %resD = add i32 %resD.tmp, %delta
+  br label %exit
+
+exit:
+  %res = phi i32 [ %res1, %case.1 ], [ %resD, %case.D ]
+  ret i32 %res
+}
+
+; Corner case:
+; 1) some of the non-default cases are unreachable due to the !range constraint,
+; 2) the default case appears to be unreachable as non-default cases cover the
+;    range fully, but its basic block actually is reachable, though, from a
+;    different basic block, not the switch itself.
+define i32 @test6(i1 %cond) {
+; CHECK-LABEL: @test6(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
+; CHECK:       switch:
+; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal(), !range !1
+; CHECK-NEXT:    br label [[LEAFBLOCK:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[CASE_1:%.*]]
+; CHECK:       case.1:
+; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       case.2:
+; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       case.D:
+; CHECK-NEXT:    [[RESD_TMP:%.*]] = call i32 @caseD()
+; CHECK-NEXT:    [[RESD:%.*]] = add i32 [[RESD_TMP]], 0
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+entry:
+  br i1 %cond, label %switch, label %case.D
+
+switch:
+  %val = call i32 @getVal(), !range !1
+  switch i32 %val, label %case.D [
+  i32 1, label %case.1
+  i32 2, label %case.2
+  i32 3, label %case.1
+  ]
+
+case.1:
+  %res1 = call i32 @case1()
+  br label %exit
+
+case.2:
+  %res2 = call i32 @case2()
+  br label %exit
+
+case.D:
+  %delta = phi i32 [ 0, %entry ], [ 20, %switch ]
+  %resD.tmp = call i32 @caseD()
+  %resD = add i32 %resD.tmp, %delta
+  br label %exit
+
+exit:
+  %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+  ret i32 %res
+}
+
+; Corner case:
+; 1) switch appears to have a non-empty set of non-default cases, but all of
+;    them reference the default case basic block.
+define i32 @test7(i1 %cond) {
+; CHECK-LABEL: @test7(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
+; CHECK:       switch:
+; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal(), !range !1
+; CHECK-NEXT:    br label [[CASE_D]]
+; CHECK:       case.D:
+; CHECK-NEXT:    [[DELTA:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ 20, [[SWITCH]] ]
+; CHECK-NEXT:    [[RESD_TMP:%.*]] = call i32 @caseD()
+; CHECK-NEXT:    [[RESD:%.*]] = add i32 [[RESD_TMP]], [[DELTA]]
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret i32 [[RESD]]
+;
+entry:
+  br i1 %cond, label %switch, label %case.D
+
+switch:
+  %val = call i32 @getVal(), !range !1
+  switch i32 %val, label %case.D [
+  i32 2, label %case.D
+  ]
+
+case.D:
+  %delta = phi i32 [ 0, %entry ], [ 20, %switch ], [ 20, %switch ]
+  %resD.tmp = call i32 @caseD()
+  %resD = add i32 %resD.tmp, %delta
+  br label %exit
+
+exit:
+  ret i32 %resD
+}
+
+; Corner case:
+; 1) some of the non-default cases are unreachable due to the !range constraint,
+; 2) the default case appears to be unreachable as non-default cases cover the
+;    range fully, but its basic block actually is reachable from the switch via
+;    one of the non-default cases,
+; 3) such cases lie at the boundary of the range of values covered by
+;    non-default cases, and if removed, do not change the fact that the rest of
+;    the cases fully covers the value range.
+define i32 @test8(i1 %cond) {
+; CHECK-LABEL: @test8(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
+; CHECK:       switch:
+; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal(), !range !3
+; CHECK-NEXT:    br label [[LEAFBLOCK:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 2
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[CASE_1:%.*]]
+; CHECK:       case.1:
+; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       case.2:
+; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       case.D:
+; CHECK-NEXT:    [[RESD_TMP:%.*]] = call i32 @caseD()
+; CHECK-NEXT:    [[RESD:%.*]] = add i32 [[RESD_TMP]], 0
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+entry:
+  br i1 %cond, label %switch, label %case.D
+
+switch:
+  %val = call i32 @getVal(), !range !3
+  switch i32 %val, label %case.D [
+  i32 1, label %case.1
+  i32 2, label %case.2
+  i32 3, label %case.D
+  ]
+
+case.1:
+  %res1 = call i32 @case1()
+  br label %exit
+
+case.2:
+  %res2 = call i32 @case2()
+  br label %exit
+
+case.D:
+  %delta = phi i32 [ 0, %entry ], [ 20, %switch ], [ 20, %switch ]
+  %resD.tmp = call i32 @caseD()
+  %resD = add i32 %resD.tmp, %delta
+  br label %exit
+
+exit:
+  %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+  ret i32 %res
+}
+
+; Corner case:
+; 1) the default case appears to be unreachable as non-default cases cover the
+;    range fully, but its basic block actually is reachable from the switch via
+;    more than one non-default case.
+define i32 @test9(i1 %cond, i2 %val) {
+; CHECK-LABEL: @test9(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br i1 [[COND:%.*]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
+; CHECK:       switch:
+; CHECK-NEXT:    br label [[LEAFBLOCK:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp sge i2 [[VAL:%.*]], 0
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_1:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK:       case.1:
+; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[CASE_D]]
+; CHECK:       case.D:
+; CHECK-NEXT:    [[DELTA:%.*]] = phi i32 [ 20, [[NEWDEFAULT]] ], [ 0, [[ENTRY:%.*]] ]
+; CHECK-NEXT:    [[RESD_TMP:%.*]] = call i32 @caseD()
+; CHECK-NEXT:    [[RESD:%.*]] = add i32 [[RESD_TMP]], [[DELTA]]
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+entry:
+  br i1 %cond, label %switch, label %case.D
+
+switch:
+  switch i2 %val, label %case.D [
+  i2 0, label %case.1
+  i2 1, label %case.1
+  i2 2, label %case.D
+  i2 3, label %case.D
+  ]
+
+case.1:
+  %res1 = call i32 @case1()
+  br label %exit
+
+case.D:
+  %delta = phi i32 [20, %switch ], [ 20, %switch ], [ 20, %switch ], [ 0, %entry ]
+  %resD.tmp = call i32 @caseD()
+  %resD = add i32 %resD.tmp, %delta
+  br label %exit
+
+exit:
+  %res = phi i32 [ %res1, %case.1 ], [ %resD, %case.D ]
+  ret i32 %res
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define i32 @test10() {
+; CHECK-LABEL: @test10(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal()
+; CHECK-NEXT:    [[COND_LEFT:%.*]] = icmp sge i32 [[VAL]], 1
+; CHECK-NEXT:    [[COND_RIGHT:%.*]] = icmp sle i32 [[VAL]], 6
+; CHECK-NEXT:    [[COND:%.*]] = and i1 [[COND_LEFT]], [[COND_RIGHT]]
+; CHECK-NEXT:    br i1 [[COND]], label [[SWITCH:%.*]], label [[CASE_D:%.*]]
+; CHECK:       switch:
+; CHECK-NEXT:    br label [[LEAFBLOCK:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[VAL_OFF:%.*]] = add i32 [[VAL]], -3
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp ule i32 [[VAL_OFF]], 1
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[CASE_1:%.*]]
+; CHECK:       case.1:
+; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       case.2:
+; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       case.D:
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ 0, [[CASE_D]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+entry:
+  %val = call i32 @getVal()
+  %cond.left = icmp sge i32 %val, 1
+  %cond.right = icmp sle i32 %val, 6
+  %cond = and i1 %cond.left, %cond.right
+  br i1 %cond, label %switch, label %case.D
+
+switch:
+  switch i32 %val, label %case.D [
+  i32 1, label %case.1
+  i32 2, label %case.1
+  i32 3, label %case.2
+  i32 4, label %case.2
+  i32 5, label %case.1
+  i32 6, label %case.1
+  ]
+  ; It's known that %val <- [1, 6]
+
+case.1:
+  %res1 = call i32 @case1()
+  br label %exit
+
+case.2:
+  %res2 = call i32 @case2()
+  br label %exit
+
+case.D:
+  %resD = phi i32 [ 20, %switch ], [ 0, %entry ]
+  br label %exit
+
+exit:
+  %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+  ret i32 %res
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define i32 @test11() {
+; CHECK-LABEL: @test11(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[VAL:%.*]] = call i32 @getVal()
+; CHECK-NEXT:    [[VAL_ZEXT:%.*]] = zext i32 [[VAL]] to i64
+; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
+; CHECK:       NodeBlock:
+; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i64 [[VAL_ZEXT]], 1
+; CHECK-NEXT:    br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i64 [[VAL_ZEXT]], 1
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK:       case.1:
+; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       case.2:
+; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[CASE_D:%.*]]
+; CHECK:       case.D:
+; CHECK-NEXT:    [[RESD:%.*]] = call i32 @caseD()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+entry:
+  %val = call i32 @getVal()
+  %val.zext = zext i32 %val to i64
+  switch i64 %val.zext, label %case.D [
+  i64 0, label %case.1
+  i64 1, label %case.2
+  ]
+  ; It's known that %val can not be less than 0
+
+case.1:
+  %res1 = call i32 @case1()
+  br label %exit
+
+case.2:
+  %res2 = call i32 @case2()
+  br label %exit
+
+case.D:
+  %resD = call i32 @caseD()
+  br label %exit
+
+exit:
+  %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+  ret i32 %res
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define void @test12() {
+; CHECK-LABEL: @test12(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    br label [[FOR_BODY:%.*]]
+; CHECK:       for.body:
+; CHECK-NEXT:    [[INDVAR:%.*]] = phi i32 [ 0, [[ENTRY:%.*]] ], [ [[INC:%.*]], [[LATCH:%.*]] ]
+; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
+; CHECK:       NodeBlock:
+; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[INDVAR]], 1
+; CHECK-NEXT:    br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[INDVAR]], 1
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK:       case.1:
+; CHECK-NEXT:    br label [[LATCH]]
+; CHECK:       case.2:
+; CHECK-NEXT:    br label [[LATCH]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[LATCH]]
+; CHECK:       latch:
+; CHECK-NEXT:    [[INC]] = add nuw nsw i32 [[INDVAR]], 1
+; CHECK-NEXT:    br i1 undef, label [[EXIT:%.*]], label [[FOR_BODY]]
+; CHECK:       exit:
+; CHECK-NEXT:    ret void
+;
+entry:
+  br label %for.body
+
+for.body:
+  %indvar = phi i32 [ 0, %entry ], [ %inc, %latch ]
+  switch i32 %indvar, label %latch [
+  i32 0, label %case.1
+  i32 1, label %case.2
+  ]
+  ; It's known that %indvar can not be less than 0
+
+case.1:
+  br label %latch
+
+case.2:
+  br label %latch
+
+latch:
+  %inc = add nuw nsw i32 %indvar, 1
+  br i1 undef, label %exit, label %for.body
+
+exit:
+  ret void
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define void @test13(i32 %val) {
+; CHECK-LABEL: @test13(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP:%.*]] = and i32 [[VAL:%.*]], 7
+; CHECK-NEXT:    br label [[BB33:%.*]]
+; CHECK:       bb33:
+; CHECK-NEXT:    br label [[LEAFBLOCK:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[TMP_OFF:%.*]] = add i32 [[TMP]], -2
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp ule i32 [[TMP_OFF]], 1
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[BB34:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK:       bb34:
+; CHECK-NEXT:    br label [[BB38:%.*]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[BB35:%.*]]
+; CHECK:       bb35:
+; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
+; CHECK:       NodeBlock:
+; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[TMP]], 6
+; CHECK-NEXT:    br i1 [[PIVOT]], label [[LEAFBLOCK2:%.*]], label [[BB37:%.*]]
+; CHECK:       LeafBlock2:
+; CHECK-NEXT:    [[SWITCHLEAF3:%.*]] = icmp sle i32 [[TMP]], 1
+; CHECK-NEXT:    br i1 [[SWITCHLEAF3]], label [[BB37]], label [[NEWDEFAULT1:%.*]]
+; CHECK:       bb37:
+; CHECK-NEXT:    br label [[BB38]]
+; CHECK:       NewDefault1:
+; CHECK-NEXT:    br label [[BB38]]
+; CHECK:       bb38:
+; CHECK-NEXT:    br label [[BB33]]
+;
+entry:
+  %tmp = and i32 %val, 7
+  br label %bb33
+
+bb33:
+  switch i32 %tmp, label %bb35 [
+  i32 2, label %bb34
+  i32 3, label %bb34
+  ]
+
+bb34:
+  br label %bb38
+
+bb35:
+  switch i32 %tmp, label %bb38 [
+  i32 0, label %bb37
+  i32 1, label %bb37
+  i32 6, label %bb37
+  i32 7, label %bb37
+  ]
+  ; It's known that %tmp <- [0, 1] U [4, 7]
+
+bb37:
+  br label %bb38
+
+bb38:
+  br label %bb33
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define i32 @test14() {
+; CHECK-LABEL: @test14(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP:%.*]] = call i32 @getVal(), !range !4
+; CHECK-NEXT:    [[VAL:%.*]] = call i32 @llvm.ctpop.i32(i32 [[TMP]])
+; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
+; CHECK:       NodeBlock:
+; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 1
+; CHECK-NEXT:    br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK:       case.1:
+; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       case.2:
+; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[CASE_D:%.*]]
+; CHECK:       case.D:
+; CHECK-NEXT:    [[RESD:%.*]] = call i32 @caseD()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+entry:
+  %tmp = call i32 @getVal(), !range !4
+  %val = call i32 @llvm.ctpop.i32(i32 %tmp)
+  switch i32 %val, label %case.D [
+  i32 0, label %case.1
+  i32 1, label %case.2
+  ]
+  ; It's known that %val <- [0, 2]
+
+case.1:
+  %res1 = call i32 @case1()
+  br label %exit
+
+case.2:
+  %res2 = call i32 @case2()
+  br label %exit
+
+case.D:
+  %resD = call i32 @caseD()
+  br label %exit
+
+exit:
+  %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+  ret i32 %res
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define i32 @test15() {
+; CHECK-LABEL: @test15(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[TMP:%.*]] = call i32 @getVal()
+; CHECK-NEXT:    [[VAL:%.*]] = urem i32 [[TMP]], 3
+; CHECK-NEXT:    br label [[NODEBLOCK:%.*]]
+; CHECK:       NodeBlock:
+; CHECK-NEXT:    [[PIVOT:%.*]] = icmp slt i32 [[VAL]], 1
+; CHECK-NEXT:    br i1 [[PIVOT]], label [[CASE_1:%.*]], label [[LEAFBLOCK:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp eq i32 [[VAL]], 1
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK:       case.1:
+; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       case.2:
+; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[CASE_D:%.*]]
+; CHECK:       case.D:
+; CHECK-NEXT:    [[RESD:%.*]] = call i32 @caseD()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ], [ [[RESD]], [[CASE_D]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+entry:
+  %tmp = call i32 @getVal()
+  %val = urem i32 %tmp, 3
+  switch i32 %val, label %case.D [
+  i32 0, label %case.1
+  i32 1, label %case.2
+  ]
+  ; It's known that %val <- [0, 2]
+
+case.1:
+  %res1 = call i32 @case1()
+  br label %exit
+
+case.2:
+  %res2 = call i32 @case2()
+  br label %exit
+
+case.D:
+  %resD = call i32 @caseD()
+  br label %exit
+
+exit:
+  %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+  ret i32 %res
+}
+
+; Check that we do not generate redundant comparisons that would have results
+; known at compile time due to limited range of the value being switch'ed over.
+define i32 @test16(float %f) {
+; CHECK-LABEL: @test16(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[I:%.*]] = fptosi float [[F:%.*]] to i64
+; CHECK-NEXT:    [[COND_LEFT:%.*]] = icmp slt i64 [[I]], 0
+; CHECK-NEXT:    [[CLAMP_LEFT:%.*]] = select i1 [[COND_LEFT]], i64 0, i64 [[I]]
+; CHECK-NEXT:    [[COND_RIGHT:%.*]] = icmp sgt i64 [[I]], 3
+; CHECK-NEXT:    [[CLAMP:%.*]] = select i1 [[COND_RIGHT]], i64 3, i64 [[CLAMP_LEFT]]
+; CHECK-NEXT:    br label [[LEAFBLOCK:%.*]]
+; CHECK:       LeafBlock:
+; CHECK-NEXT:    [[SWITCHLEAF:%.*]] = icmp sge i64 [[CLAMP]], 2
+; CHECK-NEXT:    br i1 [[SWITCHLEAF]], label [[CASE_2:%.*]], label [[NEWDEFAULT:%.*]]
+; CHECK:       NewDefault:
+; CHECK-NEXT:    br label [[CASE_1:%.*]]
+; CHECK:       case.1:
+; CHECK-NEXT:    [[RES1:%.*]] = call i32 @case1()
+; CHECK-NEXT:    br label [[EXIT:%.*]]
+; CHECK:       case.2:
+; CHECK-NEXT:    [[RES2:%.*]] = call i32 @case2()
+; CHECK-NEXT:    br label [[EXIT]]
+; CHECK:       exit:
+; CHECK-NEXT:    [[RES:%.*]] = phi i32 [ [[RES1]], [[CASE_1]] ], [ [[RES2]], [[CASE_2]] ]
+; CHECK-NEXT:    ret i32 [[RES]]
+;
+entry:
+  %i = fptosi float %f to i64
+  %cond.left = icmp slt i64 %i, 0
+  %clamp.left = select i1 %cond.left, i64 0, i64 %i
+  %cond.right = icmp sgt i64 %i, 3
+  %clamp = select i1 %cond.right, i64 3, i64 %clamp.left
+  switch i64 %clamp, label %case.D [
+  i64 0, label %case.1
+  i64 1, label %case.1
+  i64 2, label %case.2
+  i64 3, label %case.2
+  ]
+  ; It's known that %val <- [0, 3]
+
+case.1:
+  %res1 = call i32 @case1()
+  br label %exit
+
+case.2:
+  %res2 = call i32 @case2()
+  br label %exit
+
+case.D:
+  %resD = call i32 @caseD()
+  br label %exit
+
+exit:
+  %res = phi i32 [ %res1, %case.1 ], [ %res2, %case.2 ], [ %resD, %case.D ]
+  ret i32 %res
+}
+
+declare i32 @case1()
+declare i32 @case2()
+declare i32 @caseD()
+declare i32 @getVal()
+declare i32 @llvm.ctpop.i32(i32)
+
+!0 = !{i32 1, i32 257}
+!1 = !{i32 2, i32 3}
+!2 = !{i32 2, i32 257}
+!3 = !{i32 1, i32 3}
+!4 = !{i32 0, i32 4}