[LowerSwitch][AMDGPU] Do not handle impossible values

This patch adds LazyValueInfo to LowerSwitch to compute the range of the
value being switched over and reduce the size of the tree LowerSwitch
builds to lower a switch.

Reviewed By: arsenm

Differential Revision: https://reviews.llvm.org/D58096

llvm-svn: 354670

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}