; 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}