; This tests the advanced lowering of switch statements. The advanced lowering
; uses jump tables, range tests and binary search.

; RUN: %p2i -i %s --target=x8632 --filetype=obj --disassemble --args -O2 \
; RUN:   | FileCheck %s --check-prefix=CHECK --check-prefix=X8632
; RUN: %p2i -i %s --target=x8664 --filetype=obj --disassemble --args -O2 \
; RUN:   | FileCheck %s --check-prefix=CHECK --check-prefix=X8664

; RUN: %if --need=target_MIPS32 --need=allow_dump \
; RUN:   --command %p2i --filetype=asm --assemble --disassemble --target \
; RUN:   mips32 -i %s --args -O2 -allow-externally-defined-symbols \
; RUN:   | %if --need=target_MIPS32 --need=allow_dump \
; RUN:   --command FileCheck --check-prefix MIPS32 %s

; Dense but non-continuous ranges should be converted into a jump table.
define internal i32 @testJumpTable(i32 %a) {
entry:
  switch i32 %a, label %sw.default [
    i32 91, label %sw.default
    i32 92, label %sw.bb1
    i32 93, label %sw.default
    i32 99, label %sw.bb1
    i32 98, label %sw.default
    i32 96, label %sw.bb1
    i32 97, label %sw.epilog
  ]

sw.default:
  %add = add i32 %a, 27
  br label %sw.epilog

sw.bb1:
  %tmp = add i32 %a, 16
  br label %sw.epilog

sw.epilog:
  %result.1 = phi i32 [ %add, %sw.default ], [ %tmp, %sw.bb1 ], [ 17, %entry ]
  ret i32 %result.1
}
; CHECK-LABEL: testJumpTable
; CHECK: sub [[IND:[^,]+]],0x5b
; CHECK-NEXT: cmp [[IND]],0x8
; CHECK-NEXT: ja
; X8632-NEXT: mov [[TARGET:.*]],DWORD PTR {{\[}}[[IND]]*4+0x0] {{[0-9a-f]+}}: R_386_32 .{{.*}}testJumpTable$jumptable
; X8632-NEXT: jmp [[TARGET]]
; X8664-NEXT: mov {{.}}[[TARGET:.*]],DWORD PTR {{\[}}[[IND]]*4+0x0] {{[0-9a-f]+}}: R_X86_64_32S .{{.*}}testJumpTable$jumptable
; X8664-NEXT: jmp {{.}}[[TARGET]]
; Note: x86-32 may do "mov eax, [...]; jmp eax", whereas x86-64 may do
; "mov eax, [...]; jmp rax", so we assume the all characters except the first
; one in the register name will match.

; MIPS32-LABEL: testJumpTable
; MIPS32: 	move	[[REG1:.*]],{{.*}}
; MIPS32: 	li	[[REG2:.*]],91
; MIPS32: 	beq	[[REG1]],[[REG2]],6c <.LtestJumpTable$sw.default>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],92
; MIPS32: 	beq	[[REG1]],[[REG2]],78 <.LtestJumpTable$sw.bb1>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],93
; MIPS32: 	beq	[[REG1]],[[REG2]],6c <.LtestJumpTable$sw.default>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],99
; MIPS32: 	beq	[[REG1]],[[REG2]],78 <.LtestJumpTable$sw.bb1>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],98
; MIPS32: 	beq	[[REG1]],[[REG2]],6c <.LtestJumpTable$sw.default>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],96
; MIPS32: 	beq	[[REG1]],[[REG2]],78 <.LtestJumpTable$sw.bb1>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],97
; MIPS32: 	beq	[[REG1]],[[REG2]],60 <.LtestJumpTable$split_entry_sw.epilog_0>
; MIPS32: 	nop
; MIPS32: 	b	6c <.LtestJumpTable$sw.default>
; MIPS32: 	nop

; Continuous ranges which map to the same target should be grouped and
; efficiently tested.
define internal i32 @testRangeTest() {
entry:
  switch i32 10, label %sw.default [
    i32 0, label %sw.epilog
    i32 1, label %sw.epilog
    i32 2, label %sw.epilog
    i32 3, label %sw.epilog
    i32 10, label %sw.bb1
    i32 11, label %sw.bb1
    i32 12, label %sw.bb1
    i32 13, label %sw.bb1
  ]

sw.default:
  br label %sw.epilog

sw.bb1:
  br label %sw.epilog

sw.epilog:
  %result.1 = phi i32 [ 23, %sw.default ], [ 42, %sw.bb1 ], [ 17, %entry ], [ 17, %entry ], [ 17, %entry ], [ 17, %entry ]
  ret i32 %result.1
}
; CHECK-LABEL: testRangeTest
; CHECK: cmp {{.*}},0x3
; CHECK-NEXT: jbe
; CHECK: sub [[REG:[^,]*]],0xa
; CHECK-NEXT: cmp [[REG]],0x3
; CHECK-NEXT: jbe
; CHECK-NEXT: jmp

; MIPS32-LABEL: testRangeTest
; MIPS32: 	li	[[REG1:.*]],10
; MIPS32: 	li	[[REG2:.*]],0
; MIPS32: 	beq	[[REG1]],[[REG2]],114 <.LtestRangeTest$split_entry_sw.epilog_0>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],1
; MIPS32: 	beq	[[REG1]],[[REG2]],114 <.LtestRangeTest$split_entry_sw.epilog_0>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],2
; MIPS32: 	beq	[[REG1]],[[REG2]],114 <.LtestRangeTest$split_entry_sw.epilog_0>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],3
; MIPS32: 	beq	[[REG1]],[[REG2]],114 <.LtestRangeTest$split_entry_sw.epilog_0>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],10
; MIPS32: 	beq	[[REG1]],[[REG2]],fc <.LtestRangeTest$split_sw.bb1_sw.epilog_2>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],11
; MIPS32: 	beq	[[REG1]],[[REG2]],fc <.LtestRangeTest$split_sw.bb1_sw.epilog_2>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],12
; MIPS32: 	beq	[[REG1]],[[REG2]],fc <.LtestRangeTest$split_sw.bb1_sw.epilog_2>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],13
; MIPS32: 	beq	[[REG1]],[[REG2]],fc <.LtestRangeTest$split_sw.bb1_sw.epilog_2>
; MIPS32: 	nop
; MIPS32: 	b	108 <.LtestRangeTest$split_sw.default_sw.epilog_1>
; MIPS32: 	nop

; Sparse cases should be searched with a binary search.
define internal i32 @testBinarySearch() {
entry:
  switch i32 10, label %sw.default [
    i32 0, label %sw.epilog
    i32 10, label %sw.epilog
    i32 20, label %sw.bb1
    i32 30, label %sw.bb1
  ]

sw.default:
  br label %sw.epilog

sw.bb1:
  br label %sw.epilog

sw.epilog:
  %result.1 = phi i32 [ 23, %sw.default ], [ 42, %sw.bb1 ], [ 17, %entry ], [ 17, %entry ]
  ret i32 %result.1
}
; CHECK-LABEL: testBinarySearch
; CHECK: cmp {{.*}},0x14
; CHECK-NEXT: jb
; CHECK-NEXT: je
; CHECK-NEXT: cmp {{.*}},0x1e
; CHECK-NEXT: je
; CHECK-NEXT: jmp
; CHECK-NEXT: cmp {{.*}},0x0
; CHECK-NEXT: je
; CHECK-NEXT: cmp {{.*}},0xa
; CHECK-NEXT: je
; CHECK-NEXT: jmp

; MIPS32-LABEL: testBinarySearch
; MIPS32: 	li	[[REG1:.*]],10
; MIPS32: 	li	[[REG2:.*]],0
; MIPS32: 	beq	[[REG1]],[[REG2]],174 <.LtestBinarySearch$split_entry_sw.epilog_0>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],10
; MIPS32: 	beq	[[REG1]],[[REG2]],174 <.LtestBinarySearch$split_entry_sw.epilog_0>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],20
; MIPS32: 	beq	[[REG1]],[[REG2]],15c <.LtestBinarySearch$split_sw.bb1_sw.epilog_2>
; MIPS32: 	nop
; MIPS32: 	li	[[REG2:.*]],30
; MIPS32: 	beq	[[REG1]],[[REG2]],15c <.LtestBinarySearch$split_sw.bb1_sw.epilog_2>
; MIPS32: 	nop
; MIPS32: 	b	168 <.LtestBinarySearch$split_sw.default_sw.epilog_1>
; MIPS32: 	nop

; 64-bit switches where the cases are all 32-bit values should be reduced to a
; 32-bit switch after checking the top byte is 0.
define internal i32 @testSwitchSmall64(i64 %a) {
entry:
  switch i64 %a, label %sw.default [
    i64 123, label %return
    i64 234, label %sw.bb1
    i64 345, label %sw.bb2
    i64 456, label %sw.bb3
  ]

sw.bb1:
  br label %return

sw.bb2:
  br label %return

sw.bb3:
  br label %return

sw.default:
  br label %return

return:
  %retval.0 = phi i32 [ 5, %sw.default ], [ 4, %sw.bb3 ], [ 3, %sw.bb2 ], [ 2, %sw.bb1 ], [ 1, %entry ]
  ret i32 %retval.0
}
; CHECK-LABEL: testSwitchSmall64
; X8632: cmp {{.*}},0x0
; X8632-NEXT: jne
; X8632-NEXT: cmp {{.*}},0x159
; X8632-NEXT: jb
; X8632-NEXT: je
; X8632-NEXT: cmp {{.*}},0x1c8
; X8632-NEXT: je
; X8632-NEXT: jmp
; X8632-NEXT: cmp {{.*}},0x7b
; X8632-NEXT: je
; X8632-NEXT: cmp {{.*}},0xea
; X8632-NEXT: je

; MIPS32-LABEL: testSwitchSmall64
; MIPS32: 	li	[[REG:.*]],0
; MIPS32: 	bne	{{.*}},[[REG]],198 <.LtestSwitchSmall64$local$__0>
; MIPS32: 	nop
; MIPS32: 	li	[[REG:.*]],123
; MIPS32: 	beq	{{.*}},[[REG]],210 <.LtestSwitchSmall64$split_entry_return_0>
; MIPS32: 	nop

; Test for correct 64-bit lowering.
; TODO(ascull): this should generate better code like the 32-bit version
define internal i32 @testSwitch64(i64 %a) {
entry:
  switch i64 %a, label %sw.default [
    i64 123, label %return
    i64 234, label %sw.bb1
    i64 345, label %sw.bb2
    i64 78187493520, label %sw.bb3
  ]

sw.bb1:
  br label %return

sw.bb2:
  br label %return

sw.bb3:
  br label %return

sw.default:
  br label %return

return:
  %retval.0 = phi i32 [ 5, %sw.default ], [ 4, %sw.bb3 ], [ 3, %sw.bb2 ], [ 2, %sw.bb1 ], [ 1, %entry ]
  ret i32 %retval.0
}
; CHECK-LABEL: testSwitch64
; X8632: cmp {{.*}},0x7b
; X8632-NEXT: jne
; X8632-NEXT: cmp {{.*}},0x0
; X8632-NEXT: je
; X8632: cmp {{.*}},0xea
; X8632-NEXT: jne
; X8632-NEXT: cmp {{.*}},0x0
; X8632-NEXT: je
; X8632: cmp {{.*}},0x159
; X8632-NEXT: jne
; X8632-NEXT: cmp {{.*}},0x0
; X8632-NEXT: je
; X8632: cmp {{.*}},0x34567890
; X8632-NEXT: jne
; X8632-NEXT: cmp {{.*}},0x12
; X8632-NEXT: je

; MIPS32-LABEL: testSwitch64
; MIPS32: 	li	[[REG:.*]],0
; MIPS32: 	bne	{{.*}},[[REG]],238 <.LtestSwitch64$local$__0>
; MIPS32: 	nop
; MIPS32: 	li	[[REG:.*]],123
; MIPS32: 	beq	{{.*}},[[REG]],2b4 <.LtestSwitch64$split_entry_return_0>
; MIPS32: 	nop

; Test for correct 64-bit jump table with UINT64_MAX as one of the values.
define internal i32 @testJumpTable64(i64 %a) {
entry:
  switch i64 %a, label %sw.default [
    i64 -6, label %return
    i64 -4, label %sw.bb1
    i64 -3, label %sw.bb2
    i64 -1, label %sw.bb3
  ]

sw.bb1:
  br label %return

sw.bb2:
  br label %return

sw.bb3:
  br label %return

sw.default:
  br label %return

return:
  %retval.0 = phi i32 [ 5, %sw.default ], [ 4, %sw.bb3 ], [ 3, %sw.bb2 ], [ 2, %sw.bb1 ], [ 1, %entry ]
  ret i32 %retval.0
}

; TODO(ascull): this should generate a jump table. For now, just make sure it
; doesn't crash the compiler.
; CHECK-LABEL: testJumpTable64