; NOTE: Assertions have been autogenerated by utils/update_test_checks.py UTC_ARGS: --check-globals
; RUN: opt < %s -passes=simplifycfg -simplifycfg-require-and-preserve-domtree=1 -switch-to-lookup -S | FileCheck %s
; RUN: opt < %s -passes='simplifycfg<switch-to-lookup>' -S | FileCheck %s

target datalayout = "e-n32"

;.
; CHECK: @switch.table.test1 = private unnamed_addr constant [4 x i32] [i32 11984, i32 1143, i32 99783, i32 99783], align 4
; CHECK: @switch.table.test3 = private unnamed_addr constant [3 x i32] [i32 11984, i32 1143, i32 99783], align 4
; CHECK: @switch.table.test6 = private unnamed_addr constant [4 x i32] [i32 99783, i32 99783, i32 1143, i32 11984], align 4
; CHECK: @switch.table.test8 = private unnamed_addr constant [5 x i32] [i32 11984, i32 1143, i32 99783, i32 8867, i32 99783], align 4
; CHECK: @switch.table.test9 = private unnamed_addr constant [28 x i32] [i32 99783, i32 8867, i32 99783, i32 8867, i32 8867, i32 8867, i32 11984, i32 8867, i32 8867, i32 8867, i32 8867, i32 8867, i32 8867, i32 8867, i32 8867, i32 8867, i32 8867, i32 1143, i32 8867, i32 8867, i32 8867, i32 8867, i32 8867, i32 8867, i32 8867, i32 8867, i32 8867, i32 99783], align 4
;.
define i32 @test1(i32 %a) !prof !0 {
; CHECK-LABEL: @test1(
; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.fshl.i32(i32 [[TMP1]], i32 [[TMP1]], i32 28)
; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i32 [[TMP2]], 4
; CHECK-NEXT:    br i1 [[TMP3]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]], !prof [[PROF1:![0-9]+]]
; CHECK:       switch.lookup:
; CHECK-NEXT:    [[TMP4:%.*]] = zext nneg i32 [[TMP2]] to i64
; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], ptr @switch.table.test1, i64 0, i64 [[TMP4]]
; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
; CHECK-NEXT:    br label [[COMMON_RET]]
; CHECK:       common.ret:
; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
;
  switch i32 %a, label %def [
  i32 97, label %one
  i32 113, label %two
  i32 129, label %three
  i32 145, label %three
  ], !prof !1

def:
  ret i32 8867

one:
  ret i32 11984
two:
  ret i32 1143
three:
  ret i32 99783
}

; Optimization shouldn't trigger; bitwidth > 64
define i128 @test2(i128 %a) {
; CHECK-LABEL: @test2(
; CHECK-NEXT:    switch i128 [[A:%.*]], label [[COMMON_RET:%.*]] [
; CHECK-NEXT:      i128 97, label [[ONE:%.*]]
; CHECK-NEXT:      i128 113, label [[TWO:%.*]]
; CHECK-NEXT:      i128 129, label [[THREE:%.*]]
; CHECK-NEXT:      i128 145, label [[THREE]]
; CHECK-NEXT:    ]
; CHECK:       common.ret:
; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i128 [ 99783, [[THREE]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 8867, [[TMP0:%.*]] ]
; CHECK-NEXT:    ret i128 [[COMMON_RET_OP]]
; CHECK:       one:
; CHECK-NEXT:    br label [[COMMON_RET]]
; CHECK:       two:
; CHECK-NEXT:    br label [[COMMON_RET]]
; CHECK:       three:
; CHECK-NEXT:    br label [[COMMON_RET]]
;
  switch i128 %a, label %def [
  i128 97, label %one
  i128 113, label %two
  i128 129, label %three
  i128 145, label %three
  ]

def:
  ret i128 8867

one:
  ret i128 11984
two:
  ret i128 1143
three:
  ret i128 99783
}

; Optimization shouldn't trigger; no holes present
define i32 @test3(i32 %a) {
; CHECK-LABEL: @test3(
; CHECK-NEXT:    [[SWITCH_TABLEIDX:%.*]] = sub i32 [[A:%.*]], 97
; CHECK-NEXT:    [[TMP1:%.*]] = icmp ult i32 [[SWITCH_TABLEIDX]], 3
; CHECK-NEXT:    br i1 [[TMP1]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
; CHECK:       switch.lookup:
; CHECK-NEXT:    [[TMP2:%.*]] = zext nneg i32 [[SWITCH_TABLEIDX]] to i64
; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [3 x i32], ptr @switch.table.test3, i64 0, i64 [[TMP2]]
; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
; CHECK-NEXT:    br label [[COMMON_RET]]
; CHECK:       common.ret:
; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
;
  switch i32 %a, label %def [
  i32 97, label %one
  i32 98, label %two
  i32 99, label %three
  ]

def:
  ret i32 8867

one:
  ret i32 11984
two:
  ret i32 1143
three:
  ret i32 99783
}

; Optimization shouldn't trigger; not an arithmetic progression
define i32 @test4(i32 %a) {
; CHECK-LABEL: @test4(
; CHECK-NEXT:    switch i32 [[A:%.*]], label [[COMMON_RET:%.*]] [
; CHECK-NEXT:      i32 97, label [[ONE:%.*]]
; CHECK-NEXT:      i32 114, label [[TWO:%.*]]
; CHECK-NEXT:      i32 129, label [[THREE:%.*]]
; CHECK-NEXT:      i32 145, label [[THREE]]
; CHECK-NEXT:    ]
; CHECK:       common.ret:
; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 99783, [[THREE]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 8867, [[TMP0:%.*]] ]
; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
; CHECK:       one:
; CHECK-NEXT:    br label [[COMMON_RET]]
; CHECK:       two:
; CHECK-NEXT:    br label [[COMMON_RET]]
; CHECK:       three:
; CHECK-NEXT:    br label [[COMMON_RET]]
;
  switch i32 %a, label %def [
  i32 97, label %one
  i32 114, label %two
  i32 129, label %three
  i32 145, label %three
  ]

def:
  ret i32 8867

one:
  ret i32 11984
two:
  ret i32 1143
three:
  ret i32 99783
}

; Optimization shouldn't trigger; not a power of two
define i32 @test5(i32 %a) {
; CHECK-LABEL: @test5(
; CHECK-NEXT:    switch i32 [[A:%.*]], label [[COMMON_RET:%.*]] [
; CHECK-NEXT:      i32 97, label [[ONE:%.*]]
; CHECK-NEXT:      i32 112, label [[TWO:%.*]]
; CHECK-NEXT:      i32 127, label [[THREE:%.*]]
; CHECK-NEXT:      i32 142, label [[THREE]]
; CHECK-NEXT:    ]
; CHECK:       common.ret:
; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ 99783, [[THREE]] ], [ 11984, [[ONE]] ], [ 1143, [[TWO]] ], [ 8867, [[TMP0:%.*]] ]
; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
; CHECK:       one:
; CHECK-NEXT:    br label [[COMMON_RET]]
; CHECK:       two:
; CHECK-NEXT:    br label [[COMMON_RET]]
; CHECK:       three:
; CHECK-NEXT:    br label [[COMMON_RET]]
;
  switch i32 %a, label %def [
  i32 97, label %one
  i32 112, label %two
  i32 127, label %three
  i32 142, label %three
  ]

def:
  ret i32 8867

one:
  ret i32 11984
two:
  ret i32 1143
three:
  ret i32 99783
}

define i32 @test6(i32 %a) optsize {
; CHECK-LABEL: @test6(
; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], -109
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.fshl.i32(i32 [[TMP1]], i32 [[TMP1]], i32 30)
; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i32 [[TMP2]], 4
; CHECK-NEXT:    br i1 [[TMP3]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
; CHECK:       switch.lookup:
; CHECK-NEXT:    [[TMP4:%.*]] = zext nneg i32 [[TMP2]] to i64
; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [4 x i32], ptr @switch.table.test6, i64 0, i64 [[TMP4]]
; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
; CHECK-NEXT:    br label [[COMMON_RET]]
; CHECK:       common.ret:
; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
;
  switch i32 %a, label %def [
  i32 -97, label %one
  i32 -101, label %two
  i32 -105, label %three
  i32 -109, label %three
  ]

def:
  ret i32 8867

one:
  ret i32 11984
two:
  ret i32 1143
three:
  ret i32 99783
}

define i8 @test7(i8 %a) optsize {
; CHECK-LABEL: @test7(
; CHECK-NEXT:  common.ret:
; CHECK-NEXT:    [[TMP0:%.*]] = sub i8 [[A:%.*]], -36
; CHECK-NEXT:    [[TMP1:%.*]] = call i8 @llvm.fshl.i8(i8 [[TMP0]], i8 [[TMP0]], i8 6)
; CHECK-NEXT:    [[TMP2:%.*]] = icmp ult i8 [[TMP1]], 4
; CHECK-NEXT:    [[SWITCH_CAST:%.*]] = zext i8 [[TMP1]] to i32
; CHECK-NEXT:    [[SWITCH_SHIFTAMT:%.*]] = mul nuw nsw i32 [[SWITCH_CAST]], 8
; CHECK-NEXT:    [[SWITCH_DOWNSHIFT:%.*]] = lshr i32 -943228976, [[SWITCH_SHIFTAMT]]
; CHECK-NEXT:    [[SWITCH_MASKED:%.*]] = trunc i32 [[SWITCH_DOWNSHIFT]] to i8
; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = select i1 [[TMP2]], i8 [[SWITCH_MASKED]], i8 -93
; CHECK-NEXT:    ret i8 [[COMMON_RET_OP]]
;
  switch i8 %a, label %def [
  i8 220, label %one
  i8 224, label %two
  i8 228, label %three
  i8 232, label %three
  ]

def:
  ret i8 8867

one:
  ret i8 11984
two:
  ret i8 1143
three:
  ret i8 99783
}

define i32 @test8(i32 %a) optsize {
; CHECK-LABEL: @test8(
; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 97
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.fshl.i32(i32 [[TMP1]], i32 [[TMP1]], i32 30)
; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i32 [[TMP2]], 5
; CHECK-NEXT:    br i1 [[TMP3]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
; CHECK:       switch.lookup:
; CHECK-NEXT:    [[TMP4:%.*]] = zext nneg i32 [[TMP2]] to i64
; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [5 x i32], ptr @switch.table.test8, i64 0, i64 [[TMP4]]
; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
; CHECK-NEXT:    br label [[COMMON_RET]]
; CHECK:       common.ret:
; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
;
  switch i32 %a, label %def [
  i32 97, label %one
  i32 101, label %two
  i32 105, label %three
  i32 113, label %three
  ]

def:
  ret i32 8867

one:
  ret i32 11984
two:
  ret i32 1143
three:
  ret i32 99783
}

define i32 @test9(i32 %a) {
; CHECK-LABEL: @test9(
; CHECK-NEXT:    [[TMP1:%.*]] = sub i32 [[A:%.*]], 6
; CHECK-NEXT:    [[TMP2:%.*]] = call i32 @llvm.fshl.i32(i32 [[TMP1]], i32 [[TMP1]], i32 31)
; CHECK-NEXT:    [[TMP3:%.*]] = icmp ult i32 [[TMP2]], 28
; CHECK-NEXT:    br i1 [[TMP3]], label [[SWITCH_LOOKUP:%.*]], label [[COMMON_RET:%.*]]
; CHECK:       switch.lookup:
; CHECK-NEXT:    [[TMP4:%.*]] = zext nneg i32 [[TMP2]] to i64
; CHECK-NEXT:    [[SWITCH_GEP:%.*]] = getelementptr inbounds [28 x i32], ptr @switch.table.test9, i64 0, i64 [[TMP4]]
; CHECK-NEXT:    [[SWITCH_LOAD:%.*]] = load i32, ptr [[SWITCH_GEP]], align 4
; CHECK-NEXT:    br label [[COMMON_RET]]
; CHECK:       common.ret:
; CHECK-NEXT:    [[COMMON_RET_OP:%.*]] = phi i32 [ [[SWITCH_LOAD]], [[SWITCH_LOOKUP]] ], [ 8867, [[TMP0:%.*]] ]
; CHECK-NEXT:    ret i32 [[COMMON_RET_OP]]
;
  switch i32 %a, label %def [
  i32 18, label %one
  i32 40, label %two
  i32 6, label %three
  i32 10, label %three
  i32 60, label %three
  ]

def:
  ret i32 8867

one:
  ret i32 11984
two:
  ret i32 1143
three:
  ret i32 99783
}

!0 = !{!"function_entry_count", i32 100}
!1 = !{!"branch_weights", i32 5, i32 7, i32 11, i32 13, i32 17}
;.
; CHECK: attributes #[[ATTR0:[0-9]+]] = { optsize }
; CHECK: attributes #[[ATTR1:[0-9]+]] = { nocallback nocreateundeforpoison nofree nosync nounwind speculatable willreturn memory(none) }
;.
; CHECK: [[META0:![0-9]+]] = !{!"function_entry_count", i32 100}
; CHECK: [[PROF1]] = !{!"branch_weights", i32 48, i32 5}
;.