; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -jump-table-density=40 -switch-peel-threshold=101 -verify-machineinstrs | FileCheck %s
; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -O0 -jump-table-density=40 -verify-machineinstrs | FileCheck --check-prefix=NOOPT %s
declare void @g(i32)
; Should be lowered as a jump table, both with and without optimization.
define void @basic(i32 %x) {
; CHECK-LABEL: basic:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: # kill: def $edi killed $edi def $rdi
; CHECK-NEXT: decl %edi
; CHECK-NEXT: cmpl $4, %edi
; CHECK-NEXT: ja .LBB0_4
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: jmpq *.LJTI0_0(,%rdi,8)
; CHECK-NEXT: .LBB0_3: # %bb2
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB0_4: # %return
; CHECK-NEXT: retq
; CHECK-NEXT: .LBB0_2: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
;
; NOOPT-LABEL: basic:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, %eax
; NOOPT-NEXT: decl %eax
; NOOPT-NEXT: movl %eax, %ecx
; NOOPT-NEXT: movq %rcx, (%rsp) # 8-byte Spill
; NOOPT-NEXT: subl $4, %eax
; NOOPT-NEXT: ja .LBB0_4
; NOOPT-NEXT: # %bb.5: # %entry
; NOOPT-NEXT: movq (%rsp), %rax # 8-byte Reload
; NOOPT-NEXT: movq .LJTI0_0(,%rax,8), %rax
; NOOPT-NEXT: jmpq *%rax
; NOOPT-NEXT: .LBB0_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB0_4
; NOOPT-NEXT: .LBB0_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB0_4
; NOOPT-NEXT: .LBB0_3: # %bb2
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB0_4: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 3, label %bb0
i32 1, label %bb1
i32 4, label %bb1
i32 5, label %bb2
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 1) br label %return
return: ret void
}
; Should never be lowered as a jump table because of the attribute
define void @basic_nojumptable(i32 %x) "no-jump-tables"="true" {
; CHECK-LABEL: basic_nojumptable:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: cmpl $3, %edi
; CHECK-NEXT: jg .LBB1_4
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: cmpl $1, %edi
; CHECK-NEXT: je .LBB1_7
; CHECK-NEXT: # %bb.2: # %entry
; CHECK-NEXT: cmpl $3, %edi
; CHECK-NEXT: jne .LBB1_6
; CHECK-NEXT: # %bb.3: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB1_4: # %entry
; CHECK-NEXT: cmpl $4, %edi
; CHECK-NEXT: je .LBB1_7
; CHECK-NEXT: # %bb.5: # %entry
; CHECK-NEXT: cmpl $5, %edi
; CHECK-NEXT: jne .LBB1_6
; CHECK-NEXT: .LBB1_7: # %bb2
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB1_6: # %return
; CHECK-NEXT: retq
;
; NOOPT-LABEL: basic_nojumptable:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: subl $1, %edi
; NOOPT-NEXT: je .LBB1_2
; NOOPT-NEXT: jmp .LBB1_5
; NOOPT-NEXT: .LBB1_5: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $3, %eax
; NOOPT-NEXT: je .LBB1_1
; NOOPT-NEXT: jmp .LBB1_6
; NOOPT-NEXT: .LBB1_6: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $4, %eax
; NOOPT-NEXT: je .LBB1_2
; NOOPT-NEXT: jmp .LBB1_7
; NOOPT-NEXT: .LBB1_7: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $5, %eax
; NOOPT-NEXT: je .LBB1_3
; NOOPT-NEXT: jmp .LBB1_4
; NOOPT-NEXT: .LBB1_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB1_4
; NOOPT-NEXT: .LBB1_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB1_4
; NOOPT-NEXT: .LBB1_3: # %bb2
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB1_4: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 3, label %bb0
i32 1, label %bb1
i32 4, label %bb1
i32 5, label %bb2
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 1) br label %return
return: ret void
}
; Should be lowered as a jump table because of the attribute
define void @basic_nojumptable_false(i32 %x) "no-jump-tables"="false" {
; CHECK-LABEL: basic_nojumptable_false:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: # kill: def $edi killed $edi def $rdi
; CHECK-NEXT: decl %edi
; CHECK-NEXT: cmpl $4, %edi
; CHECK-NEXT: ja .LBB2_4
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: jmpq *.LJTI2_0(,%rdi,8)
; CHECK-NEXT: .LBB2_3: # %bb2
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB2_4: # %return
; CHECK-NEXT: retq
; CHECK-NEXT: .LBB2_2: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
;
; NOOPT-LABEL: basic_nojumptable_false:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, %eax
; NOOPT-NEXT: decl %eax
; NOOPT-NEXT: movl %eax, %ecx
; NOOPT-NEXT: movq %rcx, (%rsp) # 8-byte Spill
; NOOPT-NEXT: subl $4, %eax
; NOOPT-NEXT: ja .LBB2_4
; NOOPT-NEXT: # %bb.5: # %entry
; NOOPT-NEXT: movq (%rsp), %rax # 8-byte Reload
; NOOPT-NEXT: movq .LJTI2_0(,%rax,8), %rax
; NOOPT-NEXT: jmpq *%rax
; NOOPT-NEXT: .LBB2_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB2_4
; NOOPT-NEXT: .LBB2_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB2_4
; NOOPT-NEXT: .LBB2_3: # %bb2
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB2_4: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 3, label %bb0
i32 1, label %bb1
i32 4, label %bb1
i32 5, label %bb2
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 1) br label %return
return: ret void
}
; Should be lowered to two range checks.
; We do this even at -O0, because it's cheap and makes codegen faster.
define void @simple_ranges(i32 %x) {
; CHECK-LABEL: simple_ranges:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: # kill: def $edi killed $edi def $rdi
; CHECK-NEXT: leal -100(%rdi), %eax
; CHECK-NEXT: cmpl $4, %eax
; CHECK-NEXT: jb .LBB3_3
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: cmpl $3, %edi
; CHECK-NEXT: ja .LBB3_4
; CHECK-NEXT: # %bb.2: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB3_3: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB3_4: # %return
; CHECK-NEXT: retq
;
; NOOPT-LABEL: simple_ranges:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: subl $4, %edi
; NOOPT-NEXT: jb .LBB3_1
; NOOPT-NEXT: jmp .LBB3_4
; NOOPT-NEXT: .LBB3_4: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: addl $-100, %eax
; NOOPT-NEXT: subl $4, %eax
; NOOPT-NEXT: jb .LBB3_2
; NOOPT-NEXT: jmp .LBB3_3
; NOOPT-NEXT: .LBB3_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB3_3
; NOOPT-NEXT: .LBB3_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB3_3: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 0, label %bb0
i32 1, label %bb0
i32 2, label %bb0
i32 3, label %bb0
i32 100, label %bb1
i32 101, label %bb1
i32 102, label %bb1
i32 103, label %bb1
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
return: ret void
}
; Cases 0-5 could be lowered with two bit tests,
; but with 6-8, the whole switch is suitable for a jump table.
define void @jt_is_better(i32 %x) {
; CHECK-LABEL: jt_is_better:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: cmpl $8, %edi
; CHECK-NEXT: ja .LBB4_7
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: movl %edi, %eax
; CHECK-NEXT: jmpq *.LJTI4_0(,%rax,8)
; CHECK-NEXT: .LBB4_2: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB4_3: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB4_7: # %return
; CHECK-NEXT: retq
; CHECK-NEXT: .LBB4_4: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB4_5: # %bb3
; CHECK-NEXT: movl $3, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB4_6: # %bb4
; CHECK-NEXT: movl $4, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
;
; NOOPT-LABEL: jt_is_better:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, %eax
; NOOPT-NEXT: # kill: def $rax killed $eax
; NOOPT-NEXT: movq %rax, (%rsp) # 8-byte Spill
; NOOPT-NEXT: subl $8, %edi
; NOOPT-NEXT: ja .LBB4_6
; NOOPT-NEXT: # %bb.7: # %entry
; NOOPT-NEXT: movq (%rsp), %rax # 8-byte Reload
; NOOPT-NEXT: movq .LJTI4_0(,%rax,8), %rax
; NOOPT-NEXT: jmpq *%rax
; NOOPT-NEXT: .LBB4_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB4_6
; NOOPT-NEXT: .LBB4_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB4_6
; NOOPT-NEXT: .LBB4_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB4_6
; NOOPT-NEXT: .LBB4_4: # %bb3
; NOOPT-NEXT: movl $3, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB4_6
; NOOPT-NEXT: .LBB4_5: # %bb4
; NOOPT-NEXT: movl $4, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB4_6: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 0, label %bb0
i32 2, label %bb0
i32 4, label %bb0
i32 1, label %bb1
i32 3, label %bb1
i32 5, label %bb1
i32 6, label %bb2
i32 7, label %bb3
i32 8, label %bb4
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
bb3: tail call void @g(i32 3) br label %return
bb4: tail call void @g(i32 4) br label %return
return: ret void
}
; This could be lowered as a jump table, but bit tests is more efficient.
; The bit test on 2,5,8 is unnecessary as all cases cover the rage [0, 8].
; The range check guarantees that cases other than 0,3,6 and 1,4,7 must be
; in 2,5,8.
define void @bt_is_better(i32 %x) {
; CHECK-LABEL: bt_is_better:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: cmpl $8, %edi
; CHECK-NEXT: ja .LBB5_4
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: movl $73, %eax
; CHECK-NEXT: btl %edi, %eax
; CHECK-NEXT: jb .LBB5_5
; CHECK-NEXT: # %bb.2: # %entry
; CHECK-NEXT: movl $146, %eax
; CHECK-NEXT: btl %edi, %eax
; CHECK-NEXT: jae .LBB5_3
; CHECK-NEXT: # %bb.6: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB5_5: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB5_3: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB5_4: # %return
; CHECK-NEXT: retq
;
; NOOPT-LABEL: bt_is_better:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: testl %edi, %edi
; NOOPT-NEXT: je .LBB5_1
; NOOPT-NEXT: jmp .LBB5_5
; NOOPT-NEXT: .LBB5_5: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $1, %eax
; NOOPT-NEXT: je .LBB5_2
; NOOPT-NEXT: jmp .LBB5_6
; NOOPT-NEXT: .LBB5_6: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $2, %eax
; NOOPT-NEXT: je .LBB5_3
; NOOPT-NEXT: jmp .LBB5_7
; NOOPT-NEXT: .LBB5_7: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $3, %eax
; NOOPT-NEXT: je .LBB5_1
; NOOPT-NEXT: jmp .LBB5_8
; NOOPT-NEXT: .LBB5_8: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $4, %eax
; NOOPT-NEXT: je .LBB5_2
; NOOPT-NEXT: jmp .LBB5_9
; NOOPT-NEXT: .LBB5_9: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $5, %eax
; NOOPT-NEXT: je .LBB5_3
; NOOPT-NEXT: jmp .LBB5_10
; NOOPT-NEXT: .LBB5_10: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $6, %eax
; NOOPT-NEXT: je .LBB5_1
; NOOPT-NEXT: jmp .LBB5_11
; NOOPT-NEXT: .LBB5_11: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $7, %eax
; NOOPT-NEXT: je .LBB5_2
; NOOPT-NEXT: jmp .LBB5_12
; NOOPT-NEXT: .LBB5_12: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $8, %eax
; NOOPT-NEXT: je .LBB5_3
; NOOPT-NEXT: jmp .LBB5_4
; NOOPT-NEXT: .LBB5_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB5_4
; NOOPT-NEXT: .LBB5_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB5_4
; NOOPT-NEXT: .LBB5_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB5_4: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 0, label %bb0
i32 3, label %bb0
i32 6, label %bb0
i32 1, label %bb1
i32 4, label %bb1
i32 7, label %bb1
i32 2, label %bb2
i32 5, label %bb2
i32 8, label %bb2
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
return: ret void
}
; This will also be lowered as bit test, but as the range [0,8] is not fully
; covered (5 missing), the default statement can be jumped to and we end up
; with one more branch.
define void @bt_is_better2(i32 %x) {
; CHECK-LABEL: bt_is_better2:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: cmpl $8, %edi
; CHECK-NEXT: ja .LBB6_7
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: movl $73, %eax
; CHECK-NEXT: btl %edi, %eax
; CHECK-NEXT: jb .LBB6_5
; CHECK-NEXT: # %bb.2: # %entry
; CHECK-NEXT: movl $146, %eax
; CHECK-NEXT: btl %edi, %eax
; CHECK-NEXT: jae .LBB6_3
; CHECK-NEXT: # %bb.6: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB6_5: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB6_3: # %entry
; CHECK-NEXT: movl $260, %eax # imm = 0x104
; CHECK-NEXT: btl %edi, %eax
; CHECK-NEXT: jae .LBB6_7
; CHECK-NEXT: # %bb.4: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB6_7: # %return
; CHECK-NEXT: retq
;
; NOOPT-LABEL: bt_is_better2:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: testl %edi, %edi
; NOOPT-NEXT: je .LBB6_1
; NOOPT-NEXT: jmp .LBB6_5
; NOOPT-NEXT: .LBB6_5: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $1, %eax
; NOOPT-NEXT: je .LBB6_2
; NOOPT-NEXT: jmp .LBB6_6
; NOOPT-NEXT: .LBB6_6: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $2, %eax
; NOOPT-NEXT: je .LBB6_3
; NOOPT-NEXT: jmp .LBB6_7
; NOOPT-NEXT: .LBB6_7: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $3, %eax
; NOOPT-NEXT: je .LBB6_1
; NOOPT-NEXT: jmp .LBB6_8
; NOOPT-NEXT: .LBB6_8: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $4, %eax
; NOOPT-NEXT: je .LBB6_2
; NOOPT-NEXT: jmp .LBB6_9
; NOOPT-NEXT: .LBB6_9: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $6, %eax
; NOOPT-NEXT: je .LBB6_1
; NOOPT-NEXT: jmp .LBB6_10
; NOOPT-NEXT: .LBB6_10: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $7, %eax
; NOOPT-NEXT: je .LBB6_2
; NOOPT-NEXT: jmp .LBB6_11
; NOOPT-NEXT: .LBB6_11: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $8, %eax
; NOOPT-NEXT: je .LBB6_3
; NOOPT-NEXT: jmp .LBB6_4
; NOOPT-NEXT: .LBB6_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB6_4
; NOOPT-NEXT: .LBB6_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB6_4
; NOOPT-NEXT: .LBB6_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB6_4: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 0, label %bb0
i32 3, label %bb0
i32 6, label %bb0
i32 1, label %bb1
i32 4, label %bb1
i32 7, label %bb1
i32 2, label %bb2
i32 8, label %bb2
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
return: ret void
}
define void @bt_is_better3(i32 %x) {
; CHECK-LABEL: bt_is_better3:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: cmpl $18, %edi
; CHECK-NEXT: ja .LBB7_7
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: movl $74752, %eax # imm = 0x12400
; CHECK-NEXT: btl %edi, %eax
; CHECK-NEXT: jb .LBB7_5
; CHECK-NEXT: # %bb.2: # %entry
; CHECK-NEXT: movl $149504, %eax # imm = 0x24800
; CHECK-NEXT: btl %edi, %eax
; CHECK-NEXT: jae .LBB7_3
; CHECK-NEXT: # %bb.6: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB7_5: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB7_3: # %entry
; CHECK-NEXT: movl $266240, %eax # imm = 0x41000
; CHECK-NEXT: btl %edi, %eax
; CHECK-NEXT: jae .LBB7_7
; CHECK-NEXT: # %bb.4: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB7_7: # %return
; CHECK-NEXT: retq
;
; NOOPT-LABEL: bt_is_better3:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: subl $10, %edi
; NOOPT-NEXT: je .LBB7_1
; NOOPT-NEXT: jmp .LBB7_5
; NOOPT-NEXT: .LBB7_5: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $11, %eax
; NOOPT-NEXT: je .LBB7_2
; NOOPT-NEXT: jmp .LBB7_6
; NOOPT-NEXT: .LBB7_6: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $12, %eax
; NOOPT-NEXT: je .LBB7_3
; NOOPT-NEXT: jmp .LBB7_7
; NOOPT-NEXT: .LBB7_7: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $13, %eax
; NOOPT-NEXT: je .LBB7_1
; NOOPT-NEXT: jmp .LBB7_8
; NOOPT-NEXT: .LBB7_8: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $14, %eax
; NOOPT-NEXT: je .LBB7_2
; NOOPT-NEXT: jmp .LBB7_9
; NOOPT-NEXT: .LBB7_9: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $16, %eax
; NOOPT-NEXT: je .LBB7_1
; NOOPT-NEXT: jmp .LBB7_10
; NOOPT-NEXT: .LBB7_10: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $17, %eax
; NOOPT-NEXT: je .LBB7_2
; NOOPT-NEXT: jmp .LBB7_11
; NOOPT-NEXT: .LBB7_11: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $18, %eax
; NOOPT-NEXT: je .LBB7_3
; NOOPT-NEXT: jmp .LBB7_4
; NOOPT-NEXT: .LBB7_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB7_4
; NOOPT-NEXT: .LBB7_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB7_4
; NOOPT-NEXT: .LBB7_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB7_4: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 10, label %bb0
i32 13, label %bb0
i32 16, label %bb0
i32 11, label %bb1
i32 14, label %bb1
i32 17, label %bb1
i32 12, label %bb2
i32 18, label %bb2
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
return: ret void
; We don't have to subtract 10 from the case value to let the range become
; [0, 8], as each value in the range [10, 18] can be represented by bits in a
; word. Then we still need a branch to jump to the default statement for the
; range [0, 10).
; 74752 = 2^10 + 2^13 + 2^16
; 149504 = 2^11 + 2^14 + 2^17
; 266240 = 2^12 + 2^15 + 2^18
}
; Should pivot around 400 for two subtrees of equal size.
define void @optimal_pivot1(i32 %x) {
; CHECK-LABEL: optimal_pivot1:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: cmpl $399, %edi # imm = 0x18F
; CHECK-NEXT: jg .LBB8_5
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: cmpl $100, %edi
; CHECK-NEXT: je .LBB8_8
; CHECK-NEXT: # %bb.2: # %entry
; CHECK-NEXT: cmpl $200, %edi
; CHECK-NEXT: je .LBB8_9
; CHECK-NEXT: # %bb.3: # %entry
; CHECK-NEXT: cmpl $300, %edi # imm = 0x12C
; CHECK-NEXT: je .LBB8_8
; CHECK-NEXT: .LBB8_4: # %return
; CHECK-NEXT: retq
; CHECK-NEXT: .LBB8_5: # %entry
; CHECK-NEXT: cmpl $400, %edi # imm = 0x190
; CHECK-NEXT: je .LBB8_9
; CHECK-NEXT: # %bb.6: # %entry
; CHECK-NEXT: cmpl $600, %edi # imm = 0x258
; CHECK-NEXT: je .LBB8_9
; CHECK-NEXT: # %bb.7: # %entry
; CHECK-NEXT: cmpl $500, %edi # imm = 0x1F4
; CHECK-NEXT: jne .LBB8_4
; CHECK-NEXT: .LBB8_8: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB8_9: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
;
; NOOPT-LABEL: optimal_pivot1:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: subl $100, %edi
; NOOPT-NEXT: je .LBB8_1
; NOOPT-NEXT: jmp .LBB8_4
; NOOPT-NEXT: .LBB8_4: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $200, %eax
; NOOPT-NEXT: je .LBB8_2
; NOOPT-NEXT: jmp .LBB8_5
; NOOPT-NEXT: .LBB8_5: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $300, %eax # imm = 0x12C
; NOOPT-NEXT: je .LBB8_1
; NOOPT-NEXT: jmp .LBB8_6
; NOOPT-NEXT: .LBB8_6: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $400, %eax # imm = 0x190
; NOOPT-NEXT: je .LBB8_2
; NOOPT-NEXT: jmp .LBB8_7
; NOOPT-NEXT: .LBB8_7: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $500, %eax # imm = 0x1F4
; NOOPT-NEXT: je .LBB8_1
; NOOPT-NEXT: jmp .LBB8_8
; NOOPT-NEXT: .LBB8_8: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $600, %eax # imm = 0x258
; NOOPT-NEXT: je .LBB8_2
; NOOPT-NEXT: jmp .LBB8_3
; NOOPT-NEXT: .LBB8_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB8_3
; NOOPT-NEXT: .LBB8_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB8_3: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 100, label %bb0
i32 200, label %bb1
i32 300, label %bb0
i32 400, label %bb1
i32 500, label %bb0
i32 600, label %bb1
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
return: ret void
}
; Should pivot around 300 for two subtrees with two jump tables each.
define void @optimal_pivot2(i32 %x) {
; CHECK-LABEL: optimal_pivot2:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: # kill: def $edi killed $edi def $rdi
; CHECK-NEXT: cmpl $299, %edi # imm = 0x12B
; CHECK-NEXT: jg .LBB9_4
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: leal -100(%rdi), %eax
; CHECK-NEXT: cmpl $3, %eax
; CHECK-NEXT: jbe .LBB9_12
; CHECK-NEXT: # %bb.2: # %entry
; CHECK-NEXT: addl $-200, %edi
; CHECK-NEXT: cmpl $3, %edi
; CHECK-NEXT: ja .LBB9_11
; CHECK-NEXT: # %bb.3: # %entry
; CHECK-NEXT: jmpq *.LJTI9_1(,%rdi,8)
; CHECK-NEXT: .LBB9_4: # %entry
; CHECK-NEXT: leal -300(%rdi), %eax
; CHECK-NEXT: cmpl $3, %eax
; CHECK-NEXT: jbe .LBB9_13
; CHECK-NEXT: # %bb.5: # %entry
; CHECK-NEXT: addl $-400, %edi # imm = 0xFE70
; CHECK-NEXT: cmpl $3, %edi
; CHECK-NEXT: ja .LBB9_11
; CHECK-NEXT: # %bb.6: # %entry
; CHECK-NEXT: jmpq *.LJTI9_3(,%rdi,8)
; CHECK-NEXT: .LBB9_12: # %entry
; CHECK-NEXT: jmpq *.LJTI9_0(,%rax,8)
; CHECK-NEXT: .LBB9_13: # %entry
; CHECK-NEXT: jmpq *.LJTI9_2(,%rax,8)
; CHECK-NEXT: .LBB9_7: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB9_8: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB9_9: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB9_10: # %bb3
; CHECK-NEXT: movl $3, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB9_11: # %return
; CHECK-NEXT: retq
;
; NOOPT-LABEL: optimal_pivot2:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: subl $100, %edi
; NOOPT-NEXT: je .LBB9_1
; NOOPT-NEXT: jmp .LBB9_6
; NOOPT-NEXT: .LBB9_6: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $101, %eax
; NOOPT-NEXT: je .LBB9_2
; NOOPT-NEXT: jmp .LBB9_7
; NOOPT-NEXT: .LBB9_7: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $102, %eax
; NOOPT-NEXT: je .LBB9_3
; NOOPT-NEXT: jmp .LBB9_8
; NOOPT-NEXT: .LBB9_8: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $103, %eax
; NOOPT-NEXT: je .LBB9_4
; NOOPT-NEXT: jmp .LBB9_9
; NOOPT-NEXT: .LBB9_9: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $200, %eax
; NOOPT-NEXT: je .LBB9_1
; NOOPT-NEXT: jmp .LBB9_10
; NOOPT-NEXT: .LBB9_10: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $201, %eax
; NOOPT-NEXT: je .LBB9_2
; NOOPT-NEXT: jmp .LBB9_11
; NOOPT-NEXT: .LBB9_11: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $202, %eax
; NOOPT-NEXT: je .LBB9_3
; NOOPT-NEXT: jmp .LBB9_12
; NOOPT-NEXT: .LBB9_12: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $203, %eax
; NOOPT-NEXT: je .LBB9_4
; NOOPT-NEXT: jmp .LBB9_13
; NOOPT-NEXT: .LBB9_13: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $300, %eax # imm = 0x12C
; NOOPT-NEXT: je .LBB9_1
; NOOPT-NEXT: jmp .LBB9_14
; NOOPT-NEXT: .LBB9_14: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $301, %eax # imm = 0x12D
; NOOPT-NEXT: je .LBB9_2
; NOOPT-NEXT: jmp .LBB9_15
; NOOPT-NEXT: .LBB9_15: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $302, %eax # imm = 0x12E
; NOOPT-NEXT: je .LBB9_3
; NOOPT-NEXT: jmp .LBB9_16
; NOOPT-NEXT: .LBB9_16: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $303, %eax # imm = 0x12F
; NOOPT-NEXT: je .LBB9_4
; NOOPT-NEXT: jmp .LBB9_17
; NOOPT-NEXT: .LBB9_17: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $400, %eax # imm = 0x190
; NOOPT-NEXT: je .LBB9_1
; NOOPT-NEXT: jmp .LBB9_18
; NOOPT-NEXT: .LBB9_18: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $401, %eax # imm = 0x191
; NOOPT-NEXT: je .LBB9_2
; NOOPT-NEXT: jmp .LBB9_19
; NOOPT-NEXT: .LBB9_19: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $402, %eax # imm = 0x192
; NOOPT-NEXT: je .LBB9_3
; NOOPT-NEXT: jmp .LBB9_20
; NOOPT-NEXT: .LBB9_20: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $403, %eax # imm = 0x193
; NOOPT-NEXT: je .LBB9_4
; NOOPT-NEXT: jmp .LBB9_5
; NOOPT-NEXT: .LBB9_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB9_5
; NOOPT-NEXT: .LBB9_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB9_5
; NOOPT-NEXT: .LBB9_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB9_5
; NOOPT-NEXT: .LBB9_4: # %bb3
; NOOPT-NEXT: movl $3, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB9_5: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 100, label %bb0 i32 101, label %bb1 i32 102, label %bb2 i32 103, label %bb3
i32 200, label %bb0 i32 201, label %bb1 i32 202, label %bb2 i32 203, label %bb3
i32 300, label %bb0 i32 301, label %bb1 i32 302, label %bb2 i32 303, label %bb3
i32 400, label %bb0 i32 401, label %bb1 i32 402, label %bb2 i32 403, label %bb3
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
bb3: tail call void @g(i32 3) br label %return
return: ret void
}
; Splitting in the largest gap (between 6 and 12) would yield suboptimal result.
; Expecting a jump table from 5 to 15.
; At -O0, we don't build jump tables for only parts of a switch.
define void @optimal_jump_table1(i32 %x) {
; CHECK-LABEL: optimal_jump_table1:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: # kill: def $edi killed $edi def $rdi
; CHECK-NEXT: leal -5(%rdi), %eax
; CHECK-NEXT: cmpl $10, %eax
; CHECK-NEXT: ja .LBB10_1
; CHECK-NEXT: # %bb.9: # %entry
; CHECK-NEXT: jmpq *.LJTI10_0(,%rax,8)
; CHECK-NEXT: .LBB10_3: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB10_1: # %entry
; CHECK-NEXT: testl %edi, %edi
; CHECK-NEXT: jne .LBB10_8
; CHECK-NEXT: # %bb.2: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB10_8: # %return
; CHECK-NEXT: retq
; CHECK-NEXT: .LBB10_4: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB10_5: # %bb3
; CHECK-NEXT: movl $3, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB10_6: # %bb4
; CHECK-NEXT: movl $4, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB10_7: # %bb5
; CHECK-NEXT: movl $5, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
;
; NOOPT-LABEL: optimal_jump_table1:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: testl %edi, %edi
; NOOPT-NEXT: je .LBB10_1
; NOOPT-NEXT: jmp .LBB10_8
; NOOPT-NEXT: .LBB10_8: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $5, %eax
; NOOPT-NEXT: je .LBB10_2
; NOOPT-NEXT: jmp .LBB10_9
; NOOPT-NEXT: .LBB10_9: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $6, %eax
; NOOPT-NEXT: je .LBB10_3
; NOOPT-NEXT: jmp .LBB10_10
; NOOPT-NEXT: .LBB10_10: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $12, %eax
; NOOPT-NEXT: je .LBB10_4
; NOOPT-NEXT: jmp .LBB10_11
; NOOPT-NEXT: .LBB10_11: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $13, %eax
; NOOPT-NEXT: je .LBB10_5
; NOOPT-NEXT: jmp .LBB10_12
; NOOPT-NEXT: .LBB10_12: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $15, %eax
; NOOPT-NEXT: je .LBB10_6
; NOOPT-NEXT: jmp .LBB10_7
; NOOPT-NEXT: .LBB10_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB10_7
; NOOPT-NEXT: .LBB10_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB10_7
; NOOPT-NEXT: .LBB10_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB10_7
; NOOPT-NEXT: .LBB10_4: # %bb3
; NOOPT-NEXT: movl $3, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB10_7
; NOOPT-NEXT: .LBB10_5: # %bb4
; NOOPT-NEXT: movl $4, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB10_7
; NOOPT-NEXT: .LBB10_6: # %bb5
; NOOPT-NEXT: movl $5, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB10_7: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 0, label %bb0
i32 5, label %bb1
i32 6, label %bb2
i32 12, label %bb3
i32 13, label %bb4
i32 15, label %bb5
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
bb3: tail call void @g(i32 3) br label %return
bb4: tail call void @g(i32 4) br label %return
bb5: tail call void @g(i32 5) br label %return
return: ret void
}
; Partitioning the cases to the minimum number of dense sets is not good enough.
; This can be partitioned as {0,1,2,9},{14,15} or {0,1,2},{9,14,15}. The former
; should be preferred. Expecting a table from 0-9.
define void @optimal_jump_table2(i32 %x) {
; CHECK-LABEL: optimal_jump_table2:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: cmpl $9, %edi
; CHECK-NEXT: ja .LBB11_1
; CHECK-NEXT: # %bb.10: # %entry
; CHECK-NEXT: movl %edi, %eax
; CHECK-NEXT: jmpq *.LJTI11_0(,%rax,8)
; CHECK-NEXT: .LBB11_4: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB11_1: # %entry
; CHECK-NEXT: cmpl $14, %edi
; CHECK-NEXT: je .LBB11_8
; CHECK-NEXT: # %bb.2: # %entry
; CHECK-NEXT: cmpl $15, %edi
; CHECK-NEXT: jne .LBB11_9
; CHECK-NEXT: # %bb.3: # %bb5
; CHECK-NEXT: movl $5, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB11_9: # %return
; CHECK-NEXT: retq
; CHECK-NEXT: .LBB11_5: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB11_6: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB11_7: # %bb3
; CHECK-NEXT: movl $3, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB11_8: # %bb4
; CHECK-NEXT: movl $4, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
;
; NOOPT-LABEL: optimal_jump_table2:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: testl %edi, %edi
; NOOPT-NEXT: je .LBB11_1
; NOOPT-NEXT: jmp .LBB11_8
; NOOPT-NEXT: .LBB11_8: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $1, %eax
; NOOPT-NEXT: je .LBB11_2
; NOOPT-NEXT: jmp .LBB11_9
; NOOPT-NEXT: .LBB11_9: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $2, %eax
; NOOPT-NEXT: je .LBB11_3
; NOOPT-NEXT: jmp .LBB11_10
; NOOPT-NEXT: .LBB11_10: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $9, %eax
; NOOPT-NEXT: je .LBB11_4
; NOOPT-NEXT: jmp .LBB11_11
; NOOPT-NEXT: .LBB11_11: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $14, %eax
; NOOPT-NEXT: je .LBB11_5
; NOOPT-NEXT: jmp .LBB11_12
; NOOPT-NEXT: .LBB11_12: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $15, %eax
; NOOPT-NEXT: je .LBB11_6
; NOOPT-NEXT: jmp .LBB11_7
; NOOPT-NEXT: .LBB11_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB11_7
; NOOPT-NEXT: .LBB11_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB11_7
; NOOPT-NEXT: .LBB11_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB11_7
; NOOPT-NEXT: .LBB11_4: # %bb3
; NOOPT-NEXT: movl $3, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB11_7
; NOOPT-NEXT: .LBB11_5: # %bb4
; NOOPT-NEXT: movl $4, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB11_7
; NOOPT-NEXT: .LBB11_6: # %bb5
; NOOPT-NEXT: movl $5, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB11_7: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 0, label %bb0
i32 1, label %bb1
i32 2, label %bb2
i32 9, label %bb3
i32 14, label %bb4
i32 15, label %bb5
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
bb3: tail call void @g(i32 3) br label %return
bb4: tail call void @g(i32 4) br label %return
bb5: tail call void @g(i32 5) br label %return
return: ret void
}
; Splitting to maximize left-right density sum and gap size would split this
; between 3 and 10, and then between 20 and 25. It's better to build a table
; from 1-20.
define void @optimal_jump_table3(i32 %x) {
; CHECK-LABEL: optimal_jump_table3:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: # kill: def $edi killed $edi def $rdi
; CHECK-NEXT: leal -1(%rdi), %eax
; CHECK-NEXT: cmpl $19, %eax
; CHECK-NEXT: ja .LBB12_1
; CHECK-NEXT: # %bb.3: # %entry
; CHECK-NEXT: jmpq *.LJTI12_0(,%rax,8)
; CHECK-NEXT: .LBB12_4: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB12_5: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB12_6: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB12_7: # %bb3
; CHECK-NEXT: movl $3, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB12_1: # %entry
; CHECK-NEXT: cmpl $25, %edi
; CHECK-NEXT: jne .LBB12_8
; CHECK-NEXT: # %bb.2: # %bb4
; CHECK-NEXT: movl $4, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB12_8: # %return
; CHECK-NEXT: retq
;
; NOOPT-LABEL: optimal_jump_table3:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: subl $1, %edi
; NOOPT-NEXT: je .LBB12_1
; NOOPT-NEXT: jmp .LBB12_7
; NOOPT-NEXT: .LBB12_7: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $2, %eax
; NOOPT-NEXT: je .LBB12_2
; NOOPT-NEXT: jmp .LBB12_8
; NOOPT-NEXT: .LBB12_8: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $3, %eax
; NOOPT-NEXT: je .LBB12_3
; NOOPT-NEXT: jmp .LBB12_9
; NOOPT-NEXT: .LBB12_9: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $10, %eax
; NOOPT-NEXT: je .LBB12_4
; NOOPT-NEXT: jmp .LBB12_10
; NOOPT-NEXT: .LBB12_10: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $13, %eax
; NOOPT-NEXT: je .LBB12_1
; NOOPT-NEXT: jmp .LBB12_11
; NOOPT-NEXT: .LBB12_11: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $14, %eax
; NOOPT-NEXT: je .LBB12_2
; NOOPT-NEXT: jmp .LBB12_12
; NOOPT-NEXT: .LBB12_12: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $15, %eax
; NOOPT-NEXT: je .LBB12_3
; NOOPT-NEXT: jmp .LBB12_13
; NOOPT-NEXT: .LBB12_13: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $20, %eax
; NOOPT-NEXT: je .LBB12_4
; NOOPT-NEXT: jmp .LBB12_14
; NOOPT-NEXT: .LBB12_14: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $25, %eax
; NOOPT-NEXT: je .LBB12_5
; NOOPT-NEXT: jmp .LBB12_6
; NOOPT-NEXT: .LBB12_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB12_6
; NOOPT-NEXT: .LBB12_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB12_6
; NOOPT-NEXT: .LBB12_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB12_6
; NOOPT-NEXT: .LBB12_4: # %bb3
; NOOPT-NEXT: movl $3, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB12_6
; NOOPT-NEXT: .LBB12_5: # %bb4
; NOOPT-NEXT: movl $4, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB12_6: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 1, label %bb0
i32 2, label %bb1
i32 3, label %bb2
i32 10, label %bb3
i32 13, label %bb0
i32 14, label %bb1
i32 15, label %bb2
i32 20, label %bb3
i32 25, label %bb4
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
bb3: tail call void @g(i32 3) br label %return
bb4: tail call void @g(i32 4) br label %return
return: ret void
}
%struct.S = type { ptr, i32 }
; This will be lowered to a comparison with 4 and then bit tests. Make sure
; that the phi node in %header gets a value from the comparison block.
define void @phi_node_trouble(ptr %s) {
; CHECK-LABEL: phi_node_trouble:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: .p2align 4, 0x90
; CHECK-NEXT: .LBB13_1: # %header
; CHECK-NEXT: # =>This Inner Loop Header: Depth=1
; CHECK-NEXT: testq %rdi, %rdi
; CHECK-NEXT: je .LBB13_5
; CHECK-NEXT: # %bb.2: # %loop
; CHECK-NEXT: # in Loop: Header=BB13_1 Depth=1
; CHECK-NEXT: movq (%rdi), %rdi
; CHECK-NEXT: movl 8(%rdi), %eax
; CHECK-NEXT: cmpl $4, %eax
; CHECK-NEXT: je .LBB13_1
; CHECK-NEXT: # %bb.3: # %loop
; CHECK-NEXT: addl $-25, %eax
; CHECK-NEXT: cmpl $44, %eax
; CHECK-NEXT: ja .LBB13_5
; CHECK-NEXT: # %bb.4: # %loop
; CHECK-NEXT: movabsq $17592186046465, %rcx # imm = 0x100000000801
; CHECK-NEXT: btq %rax, %rcx
; CHECK-NEXT: .LBB13_5: # %exit2
; CHECK-NEXT: retq
;
; NOOPT-LABEL: phi_node_trouble:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: movq %rdi, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill
; NOOPT-NEXT: jmp .LBB13_1
; NOOPT-NEXT: .LBB13_1: # %header
; NOOPT-NEXT: # =>This Inner Loop Header: Depth=1
; NOOPT-NEXT: movq {{[-0-9]+}}(%r{{[sb]}}p), %rax # 8-byte Reload
; NOOPT-NEXT: movq %rax, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill
; NOOPT-NEXT: cmpq $0, %rax
; NOOPT-NEXT: je .LBB13_3
; NOOPT-NEXT: # %bb.2: # %loop
; NOOPT-NEXT: # in Loop: Header=BB13_1 Depth=1
; NOOPT-NEXT: movq {{[-0-9]+}}(%r{{[sb]}}p), %rax # 8-byte Reload
; NOOPT-NEXT: movq (%rax), %rax
; NOOPT-NEXT: movl 8(%rax), %ecx
; NOOPT-NEXT: movl %ecx, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: subl $4, %ecx
; NOOPT-NEXT: movq %rax, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill
; NOOPT-NEXT: je .LBB13_1
; NOOPT-NEXT: jmp .LBB13_5
; NOOPT-NEXT: .LBB13_5: # %loop
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $25, %eax
; NOOPT-NEXT: je .LBB13_4
; NOOPT-NEXT: jmp .LBB13_6
; NOOPT-NEXT: .LBB13_6: # %loop
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $36, %eax
; NOOPT-NEXT: je .LBB13_4
; NOOPT-NEXT: jmp .LBB13_7
; NOOPT-NEXT: .LBB13_7: # %loop
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $69, %eax
; NOOPT-NEXT: je .LBB13_4
; NOOPT-NEXT: jmp .LBB13_3
; NOOPT-NEXT: .LBB13_3: # %exit
; NOOPT-NEXT: retq
; NOOPT-NEXT: .LBB13_4: # %exit2
; NOOPT-NEXT: retq
entry:
br label %header
header:
%ptr = phi ptr [ %s, %entry ], [ %next, %loop ]
%bool = icmp eq ptr %ptr, null
br i1 %bool, label %exit, label %loop
loop:
%next = load ptr, ptr %ptr
%xptr = getelementptr inbounds %struct.S, ptr %next, i64 0, i32 1
%x = load i32, ptr %xptr
switch i32 %x, label %exit [
i32 4, label %header
i32 36, label %exit2
i32 69, label %exit2
i32 25, label %exit2
]
exit:
ret void
exit2:
ret void
}
; Branch directly to the default.
; (In optimized builds the switch is removed earlier.)
define void @default_only(i32 %x) {
; CHECK-LABEL: default_only:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: retq
;
; NOOPT-LABEL: default_only:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: jmp .LBB14_2
; NOOPT-NEXT: .LBB14_1: # %return
; NOOPT-NEXT: retq
; NOOPT-NEXT: .LBB14_2: # %sw
; NOOPT-NEXT: jmp .LBB14_1
entry:
br label %sw
return:
ret void
sw:
switch i32 %x, label %return [
]
}
; Don't infloop on jump tables where the upper bound is the max value of the
; input type (in this case 127).
define void @int_max_table_cluster(i8 %x) {
; CHECK-LABEL: int_max_table_cluster:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: # kill: def $edi killed $edi def $rdi
; CHECK-NEXT: cmpb $-9, %dil
; CHECK-NEXT: ja .LBB15_4
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: movzbl %dil, %eax
; CHECK-NEXT: jmpq *.LJTI15_0(,%rax,8)
; CHECK-NEXT: .LBB15_2: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB15_3: # %bb3
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB15_4: # %return
; CHECK-NEXT: retq
;
; NOOPT-LABEL: int_max_table_cluster:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movb %dil, %al
; NOOPT-NEXT: addb $64, %al
; NOOPT-NEXT: movzbl %al, %ecx
; NOOPT-NEXT: # kill: def $rcx killed $ecx
; NOOPT-NEXT: movq %rcx, (%rsp) # 8-byte Spill
; NOOPT-NEXT: subb $-65, %al
; NOOPT-NEXT: ja .LBB15_5
; NOOPT-NEXT: # %bb.6: # %entry
; NOOPT-NEXT: movq (%rsp), %rax # 8-byte Reload
; NOOPT-NEXT: movq .LJTI15_0(,%rax,8), %rax
; NOOPT-NEXT: jmpq *%rax
; NOOPT-NEXT: .LBB15_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB15_5
; NOOPT-NEXT: .LBB15_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB15_5
; NOOPT-NEXT: .LBB15_3: # %bb2
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB15_5
; NOOPT-NEXT: .LBB15_4: # %bb3
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB15_5: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i8 %x, label %return [
i8 0, label %bb0 i8 1, label %bb0 i8 2, label %bb0 i8 3, label %bb0
i8 4, label %bb0 i8 5, label %bb0 i8 6, label %bb0 i8 7, label %bb0
i8 8, label %bb0 i8 9, label %bb0 i8 10, label %bb0 i8 11, label %bb0
i8 12, label %bb0 i8 13, label %bb0 i8 14, label %bb0 i8 15, label %bb0
i8 16, label %bb0 i8 17, label %bb0 i8 18, label %bb0 i8 19, label %bb0
i8 20, label %bb0 i8 21, label %bb0 i8 22, label %bb0 i8 23, label %bb0
i8 24, label %bb0 i8 25, label %bb0 i8 26, label %bb0 i8 27, label %bb0
i8 28, label %bb0 i8 29, label %bb0 i8 30, label %bb0 i8 31, label %bb0
i8 32, label %bb0 i8 33, label %bb0 i8 34, label %bb0 i8 35, label %bb0
i8 36, label %bb0 i8 37, label %bb0 i8 38, label %bb0 i8 39, label %bb0
i8 40, label %bb0 i8 41, label %bb0 i8 42, label %bb0 i8 43, label %bb0
i8 44, label %bb0 i8 45, label %bb0 i8 46, label %bb0 i8 47, label %bb0
i8 48, label %bb0 i8 49, label %bb0 i8 50, label %bb0 i8 51, label %bb0
i8 52, label %bb0 i8 53, label %bb0 i8 54, label %bb0 i8 55, label %bb0
i8 56, label %bb0 i8 57, label %bb0 i8 58, label %bb0 i8 59, label %bb0
i8 60, label %bb0 i8 61, label %bb0 i8 62, label %bb0 i8 63, label %bb0
i8 64, label %bb0 i8 65, label %bb0 i8 66, label %bb0 i8 67, label %bb0
i8 68, label %bb0 i8 69, label %bb0 i8 70, label %bb0 i8 71, label %bb0
i8 72, label %bb0 i8 73, label %bb0 i8 74, label %bb0 i8 75, label %bb0
i8 76, label %bb0 i8 77, label %bb0 i8 78, label %bb0 i8 79, label %bb0
i8 80, label %bb0 i8 81, label %bb0 i8 82, label %bb0 i8 83, label %bb0
i8 84, label %bb0 i8 85, label %bb0 i8 86, label %bb0 i8 87, label %bb0
i8 88, label %bb0 i8 89, label %bb0 i8 90, label %bb0 i8 91, label %bb0
i8 92, label %bb0 i8 93, label %bb0 i8 94, label %bb0 i8 95, label %bb0
i8 96, label %bb0 i8 97, label %bb0 i8 98, label %bb0 i8 99, label %bb0
i8 100, label %bb0 i8 101, label %bb0 i8 102, label %bb0 i8 103, label %bb0
i8 104, label %bb0 i8 105, label %bb0 i8 106, label %bb0 i8 107, label %bb0
i8 108, label %bb0 i8 109, label %bb0 i8 110, label %bb0 i8 111, label %bb0
i8 112, label %bb0 i8 113, label %bb0 i8 114, label %bb0 i8 115, label %bb0
i8 116, label %bb0 i8 117, label %bb0 i8 118, label %bb0 i8 119, label %bb0
i8 120, label %bb0 i8 121, label %bb0 i8 122, label %bb0 i8 123, label %bb0
i8 124, label %bb0 i8 125, label %bb0 i8 126, label %bb0 i8 127, label %bb0
i8 -64, label %bb1 i8 -63, label %bb1 i8 -62, label %bb1 i8 -61, label %bb1
i8 -60, label %bb1 i8 -59, label %bb1 i8 -58, label %bb1 i8 -57, label %bb1
i8 -56, label %bb1 i8 -55, label %bb1 i8 -54, label %bb1 i8 -53, label %bb1
i8 -52, label %bb1 i8 -51, label %bb1 i8 -50, label %bb1 i8 -49, label %bb1
i8 -48, label %bb1 i8 -47, label %bb1 i8 -46, label %bb1 i8 -45, label %bb1
i8 -44, label %bb1 i8 -43, label %bb1 i8 -42, label %bb1 i8 -41, label %bb1
i8 -40, label %bb1 i8 -39, label %bb1 i8 -38, label %bb1 i8 -37, label %bb1
i8 -36, label %bb1 i8 -35, label %bb1 i8 -34, label %bb1 i8 -33, label %bb1
i8 -32, label %bb2 i8 -31, label %bb2 i8 -30, label %bb2 i8 -29, label %bb2
i8 -28, label %bb2 i8 -27, label %bb2 i8 -26, label %bb2 i8 -25, label %bb2
i8 -24, label %bb2 i8 -23, label %bb2 i8 -22, label %bb2 i8 -21, label %bb2
i8 -20, label %bb2 i8 -19, label %bb2 i8 -18, label %bb2 i8 -17, label %bb2
i8 -16, label %bb3 i8 -15, label %bb3 i8 -14, label %bb3 i8 -13, label %bb3
i8 -12, label %bb3 i8 -11, label %bb3 i8 -10, label %bb3 i8 -9, label %bb3
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 1) br label %return
bb3: tail call void @g(i32 1) br label %return
return: ret void
}
; Cases 1,4,7 have a very large branch weight (which shouldn't overflow), so
; their bit test should come first. 0,3,6 and 2,5,8,9 both have a weight of 20,
; but the latter set has more cases, so should be tested for earlier. The bit
; test on 0,3,6 is unnecessary as all cases cover the range [0, 9]. The range
; check guarantees that cases other than 1,4,7 and 2,5,8,9 must be in 0,3,6.
define void @bt_order_by_weight(i32 %x) {
; CHECK-LABEL: bt_order_by_weight:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: cmpl $9, %edi
; CHECK-NEXT: ja .LBB16_6
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: movl $146, %eax
; CHECK-NEXT: btl %edi, %eax
; CHECK-NEXT: jae .LBB16_2
; CHECK-NEXT: # %bb.4: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB16_2: # %entry
; CHECK-NEXT: movl $804, %eax # imm = 0x324
; CHECK-NEXT: btl %edi, %eax
; CHECK-NEXT: jae .LBB16_3
; CHECK-NEXT: # %bb.5: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB16_3: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB16_6: # %return
; CHECK-NEXT: retq
;
; NOOPT-LABEL: bt_order_by_weight:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: testl %edi, %edi
; NOOPT-NEXT: je .LBB16_1
; NOOPT-NEXT: jmp .LBB16_5
; NOOPT-NEXT: .LBB16_5: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $1, %eax
; NOOPT-NEXT: je .LBB16_2
; NOOPT-NEXT: jmp .LBB16_6
; NOOPT-NEXT: .LBB16_6: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $2, %eax
; NOOPT-NEXT: je .LBB16_3
; NOOPT-NEXT: jmp .LBB16_7
; NOOPT-NEXT: .LBB16_7: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $3, %eax
; NOOPT-NEXT: je .LBB16_1
; NOOPT-NEXT: jmp .LBB16_8
; NOOPT-NEXT: .LBB16_8: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $4, %eax
; NOOPT-NEXT: je .LBB16_2
; NOOPT-NEXT: jmp .LBB16_9
; NOOPT-NEXT: .LBB16_9: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $5, %eax
; NOOPT-NEXT: je .LBB16_3
; NOOPT-NEXT: jmp .LBB16_10
; NOOPT-NEXT: .LBB16_10: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $6, %eax
; NOOPT-NEXT: je .LBB16_1
; NOOPT-NEXT: jmp .LBB16_11
; NOOPT-NEXT: .LBB16_11: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $7, %eax
; NOOPT-NEXT: je .LBB16_2
; NOOPT-NEXT: jmp .LBB16_12
; NOOPT-NEXT: .LBB16_12: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: addl $-8, %eax
; NOOPT-NEXT: subl $2, %eax
; NOOPT-NEXT: jb .LBB16_3
; NOOPT-NEXT: jmp .LBB16_4
; NOOPT-NEXT: .LBB16_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB16_4
; NOOPT-NEXT: .LBB16_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB16_4
; NOOPT-NEXT: .LBB16_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB16_4: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 0, label %bb0
i32 3, label %bb0
i32 6, label %bb0
i32 1, label %bb1
i32 4, label %bb1
i32 7, label %bb1
i32 2, label %bb2
i32 5, label %bb2
i32 8, label %bb2
i32 9, label %bb2
], !prof !1
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
return: ret void
}
!1 = !{!"branch_weights",
; Default:
i32 1,
; Cases 0,3,6:
i32 0, i32 0, i32 20,
; Cases 1,4,7:
i32 4294967295, i32 2, i32 4294967295,
; Cases 2,5,8,9:
i32 0, i32 0, i32 0, i32 20}
; Case 200 has the highest weight and should come first. 100 and 300 have the
; same weight, but 300 goes to the 'next' block, so should be last.
define void @order_by_weight_and_fallthrough(i32 %x) {
; CHECK-LABEL: order_by_weight_and_fallthrough:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: cmpl $200, %edi
; CHECK-NEXT: jne .LBB17_1
; CHECK-NEXT: .LBB17_3: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB17_1: # %entry
; CHECK-NEXT: cmpl $100, %edi
; CHECK-NEXT: je .LBB17_4
; CHECK-NEXT: # %bb.2: # %entry
; CHECK-NEXT: cmpl $300, %edi # imm = 0x12C
; CHECK-NEXT: je .LBB17_3
; CHECK-NEXT: # %bb.5: # %return
; CHECK-NEXT: retq
; CHECK-NEXT: .LBB17_4: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
;
; NOOPT-LABEL: order_by_weight_and_fallthrough:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: subl $100, %edi
; NOOPT-NEXT: je .LBB17_2
; NOOPT-NEXT: jmp .LBB17_4
; NOOPT-NEXT: .LBB17_4: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $200, %eax
; NOOPT-NEXT: je .LBB17_1
; NOOPT-NEXT: jmp .LBB17_5
; NOOPT-NEXT: .LBB17_5: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $300, %eax # imm = 0x12C
; NOOPT-NEXT: jne .LBB17_3
; NOOPT-NEXT: jmp .LBB17_1
; NOOPT-NEXT: .LBB17_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB17_3
; NOOPT-NEXT: .LBB17_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB17_3: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 100, label %bb1
i32 200, label %bb0
i32 300, label %bb0
], !prof !2
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
return: ret void
}
!2 = !{!"branch_weights",
; Default:
i32 1,
; Case 100:
i32 10,
; Case 200:
i32 1000,
; Case 300:
i32 10}
; Make sure to pick a pivot in the middle also with zero-weight cases.
define void @zero_weight_tree(i32 %x) {
; CHECK-LABEL: zero_weight_tree:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: cmpl $29, %edi
; CHECK-NEXT: jg .LBB18_5
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: testl %edi, %edi
; CHECK-NEXT: jne .LBB18_2
; CHECK-NEXT: # %bb.9: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB18_5: # %entry
; CHECK-NEXT: cmpl $50, %edi
; CHECK-NEXT: jne .LBB18_6
; CHECK-NEXT: # %bb.12: # %bb5
; CHECK-NEXT: movl $5, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB18_2: # %entry
; CHECK-NEXT: cmpl $10, %edi
; CHECK-NEXT: je .LBB18_10
; CHECK-NEXT: # %bb.3: # %entry
; CHECK-NEXT: cmpl $20, %edi
; CHECK-NEXT: jne .LBB18_13
; CHECK-NEXT: # %bb.4: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB18_6: # %entry
; CHECK-NEXT: cmpl $30, %edi
; CHECK-NEXT: je .LBB18_11
; CHECK-NEXT: # %bb.7: # %entry
; CHECK-NEXT: cmpl $40, %edi
; CHECK-NEXT: je .LBB18_8
; CHECK-NEXT: .LBB18_13: # %return
; CHECK-NEXT: retq
; CHECK-NEXT: .LBB18_10: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB18_11: # %bb3
; CHECK-NEXT: movl $3, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB18_8: # %bb4
; CHECK-NEXT: movl $4, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
;
; NOOPT-LABEL: zero_weight_tree:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: testl %edi, %edi
; NOOPT-NEXT: je .LBB18_1
; NOOPT-NEXT: jmp .LBB18_8
; NOOPT-NEXT: .LBB18_8: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $10, %eax
; NOOPT-NEXT: je .LBB18_2
; NOOPT-NEXT: jmp .LBB18_9
; NOOPT-NEXT: .LBB18_9: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $20, %eax
; NOOPT-NEXT: je .LBB18_3
; NOOPT-NEXT: jmp .LBB18_10
; NOOPT-NEXT: .LBB18_10: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $30, %eax
; NOOPT-NEXT: je .LBB18_4
; NOOPT-NEXT: jmp .LBB18_11
; NOOPT-NEXT: .LBB18_11: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $40, %eax
; NOOPT-NEXT: je .LBB18_5
; NOOPT-NEXT: jmp .LBB18_12
; NOOPT-NEXT: .LBB18_12: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $50, %eax
; NOOPT-NEXT: je .LBB18_6
; NOOPT-NEXT: jmp .LBB18_7
; NOOPT-NEXT: .LBB18_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB18_7
; NOOPT-NEXT: .LBB18_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB18_7
; NOOPT-NEXT: .LBB18_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB18_7
; NOOPT-NEXT: .LBB18_4: # %bb3
; NOOPT-NEXT: movl $3, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB18_7
; NOOPT-NEXT: .LBB18_5: # %bb4
; NOOPT-NEXT: movl $4, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB18_7
; NOOPT-NEXT: .LBB18_6: # %bb5
; NOOPT-NEXT: movl $5, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB18_7: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 0, label %bb0
i32 10, label %bb1
i32 20, label %bb2
i32 30, label %bb3
i32 40, label %bb4
i32 50, label %bb5
], !prof !3
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
bb3: tail call void @g(i32 3) br label %return
bb4: tail call void @g(i32 4) br label %return
bb5: tail call void @g(i32 5) br label %return
return: ret void
}
!3 = !{!"branch_weights", i32 1, i32 10, i32 0, i32 0, i32 0, i32 0, i32 10}
; Without branch probabilities, the pivot would be 40, since that would yield
; equal-sized sub-trees. When taking weights into account, case 70 becomes the
; pivot. Since there is room for 3 cases in a leaf, cases 50 and 60 are also
; included in the right-hand side because that doesn't reduce their rank.
define void @left_leaning_weight_balanced_tree(i32 %x) {
; CHECK-LABEL: left_leaning_weight_balanced_tree:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: cmpl $49, %edi
; CHECK-NEXT: jle .LBB19_1
; CHECK-NEXT: # %bb.11: # %entry
; CHECK-NEXT: cmpl $70, %edi
; CHECK-NEXT: jne .LBB19_12
; CHECK-NEXT: .LBB19_14: # %bb6
; CHECK-NEXT: movl $6, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB19_1: # %entry
; CHECK-NEXT: cmpl $9, %edi
; CHECK-NEXT: jg .LBB19_4
; CHECK-NEXT: # %bb.2: # %entry
; CHECK-NEXT: testl %edi, %edi
; CHECK-NEXT: jne .LBB19_18
; CHECK-NEXT: # %bb.3: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB19_4: # %entry
; CHECK-NEXT: cmpl $29, %edi
; CHECK-NEXT: jg .LBB19_8
; CHECK-NEXT: # %bb.5: # %entry
; CHECK-NEXT: cmpl $10, %edi
; CHECK-NEXT: je .LBB19_15
; CHECK-NEXT: # %bb.6: # %entry
; CHECK-NEXT: cmpl $20, %edi
; CHECK-NEXT: jne .LBB19_18
; CHECK-NEXT: # %bb.7: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB19_12: # %entry
; CHECK-NEXT: cmpl $50, %edi
; CHECK-NEXT: je .LBB19_17
; CHECK-NEXT: # %bb.13: # %entry
; CHECK-NEXT: cmpl $60, %edi
; CHECK-NEXT: je .LBB19_14
; CHECK-NEXT: jmp .LBB19_18
; CHECK-NEXT: .LBB19_8: # %entry
; CHECK-NEXT: cmpl $30, %edi
; CHECK-NEXT: je .LBB19_16
; CHECK-NEXT: # %bb.9: # %entry
; CHECK-NEXT: cmpl $40, %edi
; CHECK-NEXT: jne .LBB19_18
; CHECK-NEXT: # %bb.10: # %bb4
; CHECK-NEXT: movl $4, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB19_15: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB19_16: # %bb3
; CHECK-NEXT: movl $3, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB19_17: # %bb5
; CHECK-NEXT: movl $5, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB19_18: # %return
; CHECK-NEXT: retq
;
; NOOPT-LABEL: left_leaning_weight_balanced_tree:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: testl %edi, %edi
; NOOPT-NEXT: je .LBB19_1
; NOOPT-NEXT: jmp .LBB19_9
; NOOPT-NEXT: .LBB19_9: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $10, %eax
; NOOPT-NEXT: je .LBB19_2
; NOOPT-NEXT: jmp .LBB19_10
; NOOPT-NEXT: .LBB19_10: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $20, %eax
; NOOPT-NEXT: je .LBB19_3
; NOOPT-NEXT: jmp .LBB19_11
; NOOPT-NEXT: .LBB19_11: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $30, %eax
; NOOPT-NEXT: je .LBB19_4
; NOOPT-NEXT: jmp .LBB19_12
; NOOPT-NEXT: .LBB19_12: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $40, %eax
; NOOPT-NEXT: je .LBB19_5
; NOOPT-NEXT: jmp .LBB19_13
; NOOPT-NEXT: .LBB19_13: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $50, %eax
; NOOPT-NEXT: je .LBB19_6
; NOOPT-NEXT: jmp .LBB19_14
; NOOPT-NEXT: .LBB19_14: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $60, %eax
; NOOPT-NEXT: je .LBB19_7
; NOOPT-NEXT: jmp .LBB19_15
; NOOPT-NEXT: .LBB19_15: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $70, %eax
; NOOPT-NEXT: je .LBB19_7
; NOOPT-NEXT: jmp .LBB19_8
; NOOPT-NEXT: .LBB19_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB19_8
; NOOPT-NEXT: .LBB19_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB19_8
; NOOPT-NEXT: .LBB19_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB19_8
; NOOPT-NEXT: .LBB19_4: # %bb3
; NOOPT-NEXT: movl $3, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB19_8
; NOOPT-NEXT: .LBB19_5: # %bb4
; NOOPT-NEXT: movl $4, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB19_8
; NOOPT-NEXT: .LBB19_6: # %bb5
; NOOPT-NEXT: movl $5, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB19_8
; NOOPT-NEXT: .LBB19_7: # %bb6
; NOOPT-NEXT: movl $6, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB19_8: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 0, label %bb0
i32 10, label %bb1
i32 20, label %bb2
i32 30, label %bb3
i32 40, label %bb4
i32 50, label %bb5
i32 60, label %bb6
i32 70, label %bb6
], !prof !4
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
bb3: tail call void @g(i32 3) br label %return
bb4: tail call void @g(i32 4) br label %return
bb5: tail call void @g(i32 5) br label %return
bb6: tail call void @g(i32 6) br label %return
bb7: tail call void @g(i32 7) br label %return
return: ret void
}
!4 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1000}
; Same as the previous test, except case 50 has higher rank to the left than it
; would have on the right. Case 60 would have the same rank on both sides, so is
; moved into the leaf.
define void @left_leaning_weight_balanced_tree2(i32 %x) {
; CHECK-LABEL: left_leaning_weight_balanced_tree2:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: cmpl $59, %edi
; CHECK-NEXT: jle .LBB20_1
; CHECK-NEXT: # %bb.10: # %entry
; CHECK-NEXT: cmpl $70, %edi
; CHECK-NEXT: jne .LBB20_11
; CHECK-NEXT: .LBB20_12: # %bb6
; CHECK-NEXT: movl $6, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB20_1: # %entry
; CHECK-NEXT: cmpl $29, %edi
; CHECK-NEXT: jle .LBB20_2
; CHECK-NEXT: # %bb.6: # %entry
; CHECK-NEXT: cmpl $50, %edi
; CHECK-NEXT: jne .LBB20_7
; CHECK-NEXT: # %bb.16: # %bb5
; CHECK-NEXT: movl $5, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB20_11: # %entry
; CHECK-NEXT: cmpl $60, %edi
; CHECK-NEXT: je .LBB20_12
; CHECK-NEXT: jmp .LBB20_17
; CHECK-NEXT: .LBB20_2: # %entry
; CHECK-NEXT: testl %edi, %edi
; CHECK-NEXT: jne .LBB20_3
; CHECK-NEXT: # %bb.13: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB20_3: # %entry
; CHECK-NEXT: cmpl $10, %edi
; CHECK-NEXT: je .LBB20_14
; CHECK-NEXT: # %bb.4: # %entry
; CHECK-NEXT: cmpl $20, %edi
; CHECK-NEXT: jne .LBB20_17
; CHECK-NEXT: # %bb.5: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB20_7: # %entry
; CHECK-NEXT: cmpl $30, %edi
; CHECK-NEXT: je .LBB20_15
; CHECK-NEXT: # %bb.8: # %entry
; CHECK-NEXT: cmpl $40, %edi
; CHECK-NEXT: jne .LBB20_17
; CHECK-NEXT: # %bb.9: # %bb4
; CHECK-NEXT: movl $4, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB20_14: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB20_15: # %bb3
; CHECK-NEXT: movl $3, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB20_17: # %return
; CHECK-NEXT: retq
;
; NOOPT-LABEL: left_leaning_weight_balanced_tree2:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: testl %edi, %edi
; NOOPT-NEXT: je .LBB20_1
; NOOPT-NEXT: jmp .LBB20_9
; NOOPT-NEXT: .LBB20_9: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $10, %eax
; NOOPT-NEXT: je .LBB20_2
; NOOPT-NEXT: jmp .LBB20_10
; NOOPT-NEXT: .LBB20_10: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $20, %eax
; NOOPT-NEXT: je .LBB20_3
; NOOPT-NEXT: jmp .LBB20_11
; NOOPT-NEXT: .LBB20_11: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $30, %eax
; NOOPT-NEXT: je .LBB20_4
; NOOPT-NEXT: jmp .LBB20_12
; NOOPT-NEXT: .LBB20_12: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $40, %eax
; NOOPT-NEXT: je .LBB20_5
; NOOPT-NEXT: jmp .LBB20_13
; NOOPT-NEXT: .LBB20_13: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $50, %eax
; NOOPT-NEXT: je .LBB20_6
; NOOPT-NEXT: jmp .LBB20_14
; NOOPT-NEXT: .LBB20_14: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $60, %eax
; NOOPT-NEXT: je .LBB20_7
; NOOPT-NEXT: jmp .LBB20_15
; NOOPT-NEXT: .LBB20_15: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $70, %eax
; NOOPT-NEXT: je .LBB20_7
; NOOPT-NEXT: jmp .LBB20_8
; NOOPT-NEXT: .LBB20_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB20_8
; NOOPT-NEXT: .LBB20_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB20_8
; NOOPT-NEXT: .LBB20_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB20_8
; NOOPT-NEXT: .LBB20_4: # %bb3
; NOOPT-NEXT: movl $3, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB20_8
; NOOPT-NEXT: .LBB20_5: # %bb4
; NOOPT-NEXT: movl $4, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB20_8
; NOOPT-NEXT: .LBB20_6: # %bb5
; NOOPT-NEXT: movl $5, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB20_8
; NOOPT-NEXT: .LBB20_7: # %bb6
; NOOPT-NEXT: movl $6, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB20_8: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 0, label %bb0
i32 10, label %bb1
i32 20, label %bb2
i32 30, label %bb3
i32 40, label %bb4
i32 50, label %bb5
i32 60, label %bb6
i32 70, label %bb6
], !prof !5
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
bb3: tail call void @g(i32 3) br label %return
bb4: tail call void @g(i32 4) br label %return
bb5: tail call void @g(i32 5) br label %return
bb6: tail call void @g(i32 6) br label %return
bb7: tail call void @g(i32 7) br label %return
return: ret void
}
!5 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 1, i32 90, i32 70, i32 1000}
; Analogous to left_leaning_weight_balanced_tree.
define void @right_leaning_weight_balanced_tree(i32 %x) {
; CHECK-LABEL: right_leaning_weight_balanced_tree:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: cmpl $19, %edi
; CHECK-NEXT: jg .LBB21_4
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: testl %edi, %edi
; CHECK-NEXT: jne .LBB21_2
; CHECK-NEXT: # %bb.13: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB21_4: # %entry
; CHECK-NEXT: cmpl $49, %edi
; CHECK-NEXT: jle .LBB21_5
; CHECK-NEXT: # %bb.9: # %entry
; CHECK-NEXT: cmpl $70, %edi
; CHECK-NEXT: jne .LBB21_10
; CHECK-NEXT: .LBB21_12: # %bb6
; CHECK-NEXT: movl $6, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB21_5: # %entry
; CHECK-NEXT: cmpl $20, %edi
; CHECK-NEXT: je .LBB21_14
; CHECK-NEXT: # %bb.6: # %entry
; CHECK-NEXT: cmpl $30, %edi
; CHECK-NEXT: je .LBB21_15
; CHECK-NEXT: # %bb.7: # %entry
; CHECK-NEXT: cmpl $40, %edi
; CHECK-NEXT: jne .LBB21_17
; CHECK-NEXT: # %bb.8: # %bb4
; CHECK-NEXT: movl $4, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB21_10: # %entry
; CHECK-NEXT: cmpl $50, %edi
; CHECK-NEXT: je .LBB21_16
; CHECK-NEXT: # %bb.11: # %entry
; CHECK-NEXT: cmpl $60, %edi
; CHECK-NEXT: je .LBB21_12
; CHECK-NEXT: jmp .LBB21_17
; CHECK-NEXT: .LBB21_14: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB21_15: # %bb3
; CHECK-NEXT: movl $3, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB21_2: # %entry
; CHECK-NEXT: cmpl $10, %edi
; CHECK-NEXT: jne .LBB21_17
; CHECK-NEXT: # %bb.3: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB21_17: # %return
; CHECK-NEXT: retq
; CHECK-NEXT: .LBB21_16: # %bb5
; CHECK-NEXT: movl $5, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
;
; NOOPT-LABEL: right_leaning_weight_balanced_tree:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: testl %edi, %edi
; NOOPT-NEXT: je .LBB21_1
; NOOPT-NEXT: jmp .LBB21_9
; NOOPT-NEXT: .LBB21_9: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $10, %eax
; NOOPT-NEXT: je .LBB21_2
; NOOPT-NEXT: jmp .LBB21_10
; NOOPT-NEXT: .LBB21_10: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $20, %eax
; NOOPT-NEXT: je .LBB21_3
; NOOPT-NEXT: jmp .LBB21_11
; NOOPT-NEXT: .LBB21_11: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $30, %eax
; NOOPT-NEXT: je .LBB21_4
; NOOPT-NEXT: jmp .LBB21_12
; NOOPT-NEXT: .LBB21_12: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $40, %eax
; NOOPT-NEXT: je .LBB21_5
; NOOPT-NEXT: jmp .LBB21_13
; NOOPT-NEXT: .LBB21_13: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $50, %eax
; NOOPT-NEXT: je .LBB21_6
; NOOPT-NEXT: jmp .LBB21_14
; NOOPT-NEXT: .LBB21_14: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $60, %eax
; NOOPT-NEXT: je .LBB21_7
; NOOPT-NEXT: jmp .LBB21_15
; NOOPT-NEXT: .LBB21_15: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $70, %eax
; NOOPT-NEXT: je .LBB21_7
; NOOPT-NEXT: jmp .LBB21_8
; NOOPT-NEXT: .LBB21_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB21_8
; NOOPT-NEXT: .LBB21_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB21_8
; NOOPT-NEXT: .LBB21_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB21_8
; NOOPT-NEXT: .LBB21_4: # %bb3
; NOOPT-NEXT: movl $3, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB21_8
; NOOPT-NEXT: .LBB21_5: # %bb4
; NOOPT-NEXT: movl $4, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB21_8
; NOOPT-NEXT: .LBB21_6: # %bb5
; NOOPT-NEXT: movl $5, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB21_8
; NOOPT-NEXT: .LBB21_7: # %bb6
; NOOPT-NEXT: movl $6, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB21_8: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
i32 0, label %bb0
i32 10, label %bb1
i32 20, label %bb2
i32 30, label %bb3
i32 40, label %bb4
i32 50, label %bb5
i32 60, label %bb6
i32 70, label %bb6
], !prof !6
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
bb3: tail call void @g(i32 3) br label %return
bb4: tail call void @g(i32 4) br label %return
bb5: tail call void @g(i32 5) br label %return
bb6: tail call void @g(i32 6) br label %return
bb7: tail call void @g(i32 7) br label %return
return: ret void
}
!6 = !{!"branch_weights", i32 1, i32 1000, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 10}
; If the tree were balanced based on number of clusters, {0-3,100} would go on
; the left and {200,300} on the right. However, the jump table weights as much
; as its components, so 100 is selected as the pivot.
define void @jump_table_affects_balance(i32 %x) {
; CHECK-LABEL: jump_table_affects_balance:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: cmpl $99, %edi
; CHECK-NEXT: jg .LBB22_3
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: cmpl $3, %edi
; CHECK-NEXT: ja .LBB22_10
; CHECK-NEXT: # %bb.2: # %entry
; CHECK-NEXT: movl %edi, %eax
; CHECK-NEXT: jmpq *.LJTI22_0(,%rax,8)
; CHECK-NEXT: .LBB22_9: # %bb3
; CHECK-NEXT: movl $3, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB22_3: # %entry
; CHECK-NEXT: cmpl $300, %edi # imm = 0x12C
; CHECK-NEXT: je .LBB22_8
; CHECK-NEXT: # %bb.4: # %entry
; CHECK-NEXT: cmpl $200, %edi
; CHECK-NEXT: je .LBB22_7
; CHECK-NEXT: # %bb.5: # %entry
; CHECK-NEXT: cmpl $100, %edi
; CHECK-NEXT: jne .LBB22_10
; CHECK-NEXT: .LBB22_6: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB22_8: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB22_7: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB22_10: # %return
; CHECK-NEXT: retq
;
; NOOPT-LABEL: jump_table_affects_balance:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: testl %edi, %edi
; NOOPT-NEXT: je .LBB22_1
; NOOPT-NEXT: jmp .LBB22_6
; NOOPT-NEXT: .LBB22_6: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $1, %eax
; NOOPT-NEXT: je .LBB22_2
; NOOPT-NEXT: jmp .LBB22_7
; NOOPT-NEXT: .LBB22_7: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $2, %eax
; NOOPT-NEXT: je .LBB22_3
; NOOPT-NEXT: jmp .LBB22_8
; NOOPT-NEXT: .LBB22_8: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $3, %eax
; NOOPT-NEXT: je .LBB22_4
; NOOPT-NEXT: jmp .LBB22_9
; NOOPT-NEXT: .LBB22_9: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $100, %eax
; NOOPT-NEXT: je .LBB22_1
; NOOPT-NEXT: jmp .LBB22_10
; NOOPT-NEXT: .LBB22_10: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $200, %eax
; NOOPT-NEXT: je .LBB22_2
; NOOPT-NEXT: jmp .LBB22_11
; NOOPT-NEXT: .LBB22_11: # %entry
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $300, %eax # imm = 0x12C
; NOOPT-NEXT: je .LBB22_3
; NOOPT-NEXT: jmp .LBB22_5
; NOOPT-NEXT: .LBB22_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB22_5
; NOOPT-NEXT: .LBB22_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB22_5
; NOOPT-NEXT: .LBB22_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB22_5
; NOOPT-NEXT: .LBB22_4: # %bb3
; NOOPT-NEXT: movl $3, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB22_5: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %x, label %return [
; Jump table:
i32 0, label %bb0
i32 1, label %bb1
i32 2, label %bb2
i32 3, label %bb3
i32 100, label %bb0
i32 200, label %bb1
i32 300, label %bb2
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
bb3: tail call void @g(i32 3) br label %return
return: ret void
}
; Don't assert due to truncating the bitwidth (64) to i4 when checking
; that the bit-test range fits in a word.
define void @pr23738(i4 %x) {
; CHECK-LABEL: pr23738:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: movl %edi, %eax
; CHECK-NEXT: andb $15, %al
; CHECK-NEXT: cmpb $11, %al
; CHECK-NEXT: ja .LBB23_2
; CHECK-NEXT: # %bb.1: # %entry
; CHECK-NEXT: andl $15, %edi
; CHECK-NEXT: movl $2051, %eax # imm = 0x803
; CHECK-NEXT: btl %edi, %eax
; CHECK-NEXT: jae .LBB23_2
; CHECK-NEXT: # %bb.3: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB23_2: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
;
; NOOPT-LABEL: pr23738:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movb %dil, %al
; NOOPT-NEXT: movb %al, {{[-0-9]+}}(%r{{[sb]}}p) # 1-byte Spill
; NOOPT-NEXT: andb $15, %al
; NOOPT-NEXT: subb $11, %al
; NOOPT-NEXT: je .LBB23_2
; NOOPT-NEXT: jmp .LBB23_4
; NOOPT-NEXT: .LBB23_4: # %entry
; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload
; NOOPT-NEXT: andb $15, %al
; NOOPT-NEXT: subb $2, %al
; NOOPT-NEXT: jb .LBB23_2
; NOOPT-NEXT: jmp .LBB23_1
; NOOPT-NEXT: .LBB23_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB23_3
; NOOPT-NEXT: .LBB23_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB23_3: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i4 %x, label %bb0 [
i4 0, label %bb1
i4 1, label %bb1
i4 -5, label %bb1
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
return: ret void
}
; The switch is lowered with bit tests. Since the case range is contiguous, the
; second bit test is redundant and can be skipped. Check that we don't update
; the phi node with an incoming value from the MBB of the skipped bit test
; (-verify-machine-instrs cathces this).
define i32 @pr27135(i32 %i) {
; CHECK-LABEL: pr27135:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: xorl %eax, %eax
; CHECK-NEXT: testb %al, %al
; CHECK-NEXT: jne .LBB24_5
; CHECK-NEXT: # %bb.1: # %sw
; CHECK-NEXT: movl $1, %eax
; CHECK-NEXT: addl $-96, %edi
; CHECK-NEXT: cmpl $5, %edi
; CHECK-NEXT: jbe .LBB24_2
; CHECK-NEXT: .LBB24_5: # %end
; CHECK-NEXT: retq
; CHECK-NEXT: .LBB24_2: # %sw
; CHECK-NEXT: movl $19, %eax
; CHECK-NEXT: btl %edi, %eax
; CHECK-NEXT: jae .LBB24_3
; CHECK-NEXT: # %bb.4: # %sw.bb2
; CHECK-NEXT: .LBB24_3: # %sw.bb
;
; NOOPT-LABEL: pr27135:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: xorl %eax, %eax
; NOOPT-NEXT: # implicit-def: $cl
; NOOPT-NEXT: testb $1, %cl
; NOOPT-NEXT: movl %eax, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: jne .LBB24_1
; NOOPT-NEXT: jmp .LBB24_4
; NOOPT-NEXT: .LBB24_1: # %sw
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: movl $1, %ecx
; NOOPT-NEXT: movl %ecx, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: addl $-96, %eax
; NOOPT-NEXT: subl $2, %eax
; NOOPT-NEXT: jb .LBB24_3
; NOOPT-NEXT: jmp .LBB24_5
; NOOPT-NEXT: .LBB24_5: # %sw
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: addl $-98, %eax
; NOOPT-NEXT: subl $2, %eax
; NOOPT-NEXT: jb .LBB24_2
; NOOPT-NEXT: jmp .LBB24_6
; NOOPT-NEXT: .LBB24_6: # %sw
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: subl $100, %eax
; NOOPT-NEXT: je .LBB24_3
; NOOPT-NEXT: jmp .LBB24_7
; NOOPT-NEXT: .LBB24_7: # %sw
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %ecx # 4-byte Reload
; NOOPT-NEXT: subl $101, %ecx
; NOOPT-NEXT: movl %eax, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
; NOOPT-NEXT: jne .LBB24_4
; NOOPT-NEXT: jmp .LBB24_2
; NOOPT-NEXT: .LBB24_2: # %sw.bb
; NOOPT-NEXT: .LBB24_3: # %sw.bb2
; NOOPT-NEXT: .LBB24_4: # %end
; NOOPT-NEXT: movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
; NOOPT-NEXT: retq
entry:
br i1 undef, label %sw, label %end
sw:
switch i32 %i, label %end [
i32 99, label %sw.bb
i32 98, label %sw.bb
i32 101, label %sw.bb
i32 97, label %sw.bb2
i32 96, label %sw.bb2
i32 100, label %sw.bb2
]
sw.bb:
unreachable
sw.bb2:
unreachable
end:
%p = phi i32 [ 1, %sw ], [ 0, %entry ]
ret i32 %p
}
; Since the default is unreachable, either cluster will be reached.
; Only one comparison should be emitted.
define void @range_with_unreachable_fallthrough(i32 %i) {
; CHECK-LABEL: range_with_unreachable_fallthrough:
; CHECK: # %bb.0: # %entry
; CHECK-NEXT: addl $-4, %edi
; CHECK-NEXT: cmpl $3, %edi
; CHECK-NEXT: jae .LBB25_1
; CHECK-NEXT: # %bb.2: # %bb2
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB25_1: # %bb1
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
;
; NOOPT-LABEL: range_with_unreachable_fallthrough:
; NOOPT: # %bb.0: # %entry
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movl %edi, %eax
; NOOPT-NEXT: decl %eax
; NOOPT-NEXT: subl $3, %eax
; NOOPT-NEXT: jb .LBB25_1
; NOOPT-NEXT: jmp .LBB25_5
; NOOPT-NEXT: .LBB25_5: # %entry
; NOOPT-NEXT: jmp .LBB25_2
; NOOPT-NEXT: .LBB25_1: # %bb1
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB25_4
; NOOPT-NEXT: .LBB25_2: # %bb2
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB25_4
; NOOPT-NEXT: # %bb.3: # %default
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: .LBB25_4: # %return
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
entry:
switch i32 %i, label %default [
i32 1, label %bb1
i32 2, label %bb1
i32 3, label %bb1
i32 4, label %bb2
i32 5, label %bb2
i32 6, label %bb2
]
bb1: tail call void @g(i32 0) br label %return
bb2: tail call void @g(i32 1) br label %return
default: unreachable
return:
ret void
}
; A switch over a small type (i8) should be extended to avoid truncation
; instructions.
define void @switch_i8(i32 %a) {
; CHECK-LABEL: switch_i8:
; CHECK: # %bb.0:
; CHECK-NEXT: # kill: def $edi killed $edi def $rdi
; CHECK-NEXT: andl $127, %edi
; CHECK-NEXT: leal -1(%rdi), %eax
; CHECK-NEXT: cmpl $8, %eax
; CHECK-NEXT: ja .LBB26_1
; CHECK-NEXT: # %bb.10:
; CHECK-NEXT: jmpq *.LJTI26_0(,%rax,8)
; CHECK-NEXT: .LBB26_4: # %bb0
; CHECK-NEXT: xorl %edi, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB26_1:
; CHECK-NEXT: cmpl $13, %edi
; CHECK-NEXT: je .LBB26_8
; CHECK-NEXT: # %bb.2:
; CHECK-NEXT: cmpl $42, %edi
; CHECK-NEXT: jne .LBB26_9
; CHECK-NEXT: # %bb.3: # %bb5
; CHECK-NEXT: movl $5, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB26_9: # %return
; CHECK-NEXT: retq
; CHECK-NEXT: .LBB26_5: # %bb1
; CHECK-NEXT: movl $1, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB26_6: # %bb2
; CHECK-NEXT: movl $2, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB26_7: # %bb3
; CHECK-NEXT: movl $3, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
; CHECK-NEXT: .LBB26_8: # %bb4
; CHECK-NEXT: movl $4, %edi
; CHECK-NEXT: jmp g@PLT # TAILCALL
;
; NOOPT-LABEL: switch_i8:
; NOOPT: # %bb.0:
; NOOPT-NEXT: pushq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 16
; NOOPT-NEXT: movb %dil, %al
; NOOPT-NEXT: andb $127, %al
; NOOPT-NEXT: movb %al, {{[-0-9]+}}(%r{{[sb]}}p) # 1-byte Spill
; NOOPT-NEXT: subb $1, %al
; NOOPT-NEXT: je .LBB26_1
; NOOPT-NEXT: jmp .LBB26_8
; NOOPT-NEXT: .LBB26_8:
; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload
; NOOPT-NEXT: subb $3, %al
; NOOPT-NEXT: je .LBB26_2
; NOOPT-NEXT: jmp .LBB26_9
; NOOPT-NEXT: .LBB26_9:
; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload
; NOOPT-NEXT: subb $7, %al
; NOOPT-NEXT: je .LBB26_3
; NOOPT-NEXT: jmp .LBB26_10
; NOOPT-NEXT: .LBB26_10:
; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload
; NOOPT-NEXT: subb $9, %al
; NOOPT-NEXT: je .LBB26_4
; NOOPT-NEXT: jmp .LBB26_11
; NOOPT-NEXT: .LBB26_11:
; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload
; NOOPT-NEXT: subb $13, %al
; NOOPT-NEXT: je .LBB26_5
; NOOPT-NEXT: jmp .LBB26_12
; NOOPT-NEXT: .LBB26_12:
; NOOPT-NEXT: movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload
; NOOPT-NEXT: subb $42, %al
; NOOPT-NEXT: je .LBB26_6
; NOOPT-NEXT: jmp .LBB26_7
; NOOPT-NEXT: .LBB26_1: # %bb0
; NOOPT-NEXT: xorl %edi, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB26_7
; NOOPT-NEXT: .LBB26_2: # %bb1
; NOOPT-NEXT: movl $1, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB26_7
; NOOPT-NEXT: .LBB26_3: # %bb2
; NOOPT-NEXT: movl $2, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB26_7
; NOOPT-NEXT: .LBB26_4: # %bb3
; NOOPT-NEXT: movl $3, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB26_7
; NOOPT-NEXT: .LBB26_5: # %bb4
; NOOPT-NEXT: movl $4, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: jmp .LBB26_7
; NOOPT-NEXT: .LBB26_6: # %bb5
; NOOPT-NEXT: movl $5, %edi
; NOOPT-NEXT: callq g@PLT
; NOOPT-NEXT: .LBB26_7: # %return
; NOOPT-NEXT: popq %rax
; NOOPT-NEXT: .cfi_def_cfa_offset 8
; NOOPT-NEXT: retq
%and = and i32 %a, 127
%trunc = trunc i32 %and to i8
switch i8 %trunc, label %return [
i8 1, label %bb0
i8 3, label %bb1
i8 7, label %bb2
i8 9, label %bb3
i8 13, label %bb4
i8 42, label %bb5
]
bb0: tail call void @g(i32 0) br label %return
bb1: tail call void @g(i32 1) br label %return
bb2: tail call void @g(i32 2) br label %return
bb3: tail call void @g(i32 3) br label %return
bb4: tail call void @g(i32 4) br label %return
bb5: tail call void @g(i32 5) br label %return
return:
ret void
}