llvm/test/CodeGen/X86/switch-bt.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
   2 ; RUN: llc -mtriple=x86_64-- < %s -jump-table-density=40 -switch-peel-threshold=101 | FileCheck %s
   3
   4 ; This switch should use bit tests, and the third bit test case is just
   5 ; testing for one possible value, so it doesn't need a bt.
   6
   7 define void @test(ptr %l) nounwind {
   8 ; CHECK-LABEL: test:
   9 ; CHECK:       # %bb.0: # %entry
  10 ; CHECK-NEXT:    pushq %rax
  11 ; CHECK-NEXT:    movq %rdi, (%rsp)
  12 ; CHECK-NEXT:    movsbl (%rdi), %eax
  13 ; CHECK-NEXT:    addl $-33, %eax
  14 ; CHECK-NEXT:    cmpl $61, %eax
  15 ; CHECK-NEXT:    ja .LBB0_7
  16 ; CHECK-NEXT:  # %bb.1: # %entry
  17 ; CHECK-NEXT:    movabsq $2305843009482129440, %rcx # imm = 0x2000000010000020
  18 ; CHECK-NEXT:    btq %rax, %rcx
  19 ; CHECK-NEXT:    jb .LBB0_6
  20 ; CHECK-NEXT:  # %bb.2: # %entry
  21 ; CHECK-NEXT:    movl $671088640, %ecx # imm = 0x28000000
  22 ; CHECK-NEXT:    btq %rax, %rcx
  23 ; CHECK-NEXT:    jae .LBB0_3
  24 ; CHECK-NEXT:  # %bb.5: # %sw.bb
  25 ; CHECK-NEXT:    xorl %edi, %edi
  26 ; CHECK-NEXT:    jmp .LBB0_8
  27 ; CHECK-NEXT:  .LBB0_6: # %sw.bb2
  28 ; CHECK-NEXT:    movl $1, %edi
  29 ; CHECK-NEXT:    jmp .LBB0_8
  30 ; CHECK-NEXT:  .LBB0_3: # %entry
  31 ; CHECK-NEXT:    testq %rax, %rax
  32 ; CHECK-NEXT:    jne .LBB0_7
  33 ; CHECK-NEXT:  # %bb.4: # %sw.bb4
  34 ; CHECK-NEXT:    movl $3, %edi
  35 ; CHECK-NEXT:    jmp .LBB0_8
  36 ; CHECK-NEXT:  .LBB0_7: # %sw.default
  37 ; CHECK-NEXT:    movl $97, %edi
  38 ; CHECK-NEXT:  .LBB0_8: # %sw.epilog
  39 ; CHECK-NEXT:    callq foo@PLT
  40 ; CHECK-NEXT:    popq %rax
  41 ; CHECK-NEXT:    retq
  42 entry:
  43   %l.addr = alloca ptr, align 8                   ; <ptr> [#uses=2]
  44   store ptr %l, ptr %l.addr
  45   %tmp = load ptr, ptr %l.addr                        ; <ptr> [#uses=1]
  46   %tmp1 = load i8, ptr %tmp                           ; <i8> [#uses=1]
  47   %conv = sext i8 %tmp1 to i32                    ; <i32> [#uses=1]
  48   switch i32 %conv, label %sw.default [
  49     i32 62, label %sw.bb
  50     i32 60, label %sw.bb
  51     i32 38, label %sw.bb2
  52     i32 94, label %sw.bb2
  53     i32 61, label %sw.bb2
  54     i32 33, label %sw.bb4
  55   ]
  56
  57 sw.bb:                                            ; preds = %entry, %entry
  58   call void @foo(i32 0)
  59   br label %sw.epilog
  60
  61 sw.bb2:                                           ; preds = %entry, %entry, %entry
  62   call void @foo(i32 1)
  63   br label %sw.epilog
  64
  65 sw.bb4:                                           ; preds = %entry
  66   call void @foo(i32 3)
  67   br label %sw.epilog
  68
  69 sw.default:                                       ; preds = %entry
  70   call void @foo(i32 97)
  71   br label %sw.epilog
  72
  73 sw.epilog:                                        ; preds = %sw.default, %sw.bb4, %sw.bb2, %sw.bb
  74   ret void
  75 }
  76
  77 declare void @foo(i32)
  78
  79 ; Don't zero extend the test operands to pointer type if it can be avoided.
  80 ; rdar://8781238
  81 define void @test2(i32 %x) nounwind ssp {
  82 ; CHECK-LABEL: test2:
  83 ; CHECK:       # %bb.0: # %entry
  84 ; CHECK-NEXT:    cmpl $6, %edi
  85 ; CHECK-NEXT:    ja .LBB1_2
  86 ; CHECK-NEXT:  # %bb.1: # %entry
  87 ; CHECK-NEXT:    movl $91, %eax
  88 ; CHECK-NEXT:    btl %edi, %eax
  89 ; CHECK-NEXT:    jb bar@PLT # TAILCALL
  90 ; CHECK-NEXT:  .LBB1_2: # %if.end
  91 ; CHECK-NEXT:    retq
  92
  93 entry:
  94   switch i32 %x, label %if.end [
  95     i32 6, label %if.then
  96     i32 4, label %if.then
  97     i32 3, label %if.then
  98     i32 1, label %if.then
  99     i32 0, label %if.then
 100   ]
 101
 102 if.then:                                          ; preds = %entry, %entry, %entry, %entry, %entry
 103   tail call void @bar() nounwind
 104   ret void
 105
 106 if.end:                                           ; preds = %entry
 107   ret void
 108 }
 109
 110 declare void @bar()
 111
 112 define void @test3(i32 %x) nounwind {
 113 ; CHECK-LABEL: test3:
 114 ; CHECK:       # %bb.0:
 115 ; CHECK-NEXT:    cmpl $5, %edi
 116 ; CHECK-NEXT:    ja .LBB2_2
 117 ; CHECK-NEXT:  # %bb.1:
 118 ; CHECK-NEXT:    cmpl $4, %edi
 119 ; CHECK-NEXT:    jne bar@PLT # TAILCALL
 120 ; CHECK-NEXT:  .LBB2_2: # %if.end
 121 ; CHECK-NEXT:    retq
 122   switch i32 %x, label %if.end [
 123     i32 0, label %if.then
 124     i32 1, label %if.then
 125     i32 2, label %if.then
 126     i32 3, label %if.then
 127     i32 5, label %if.then
 128   ]
 129 if.then:
 130   tail call void @bar() nounwind
 131   ret void
 132 if.end:
 133   ret void
 134 }
 135
 136 ; Ensure that optimizing for jump tables doesn't needlessly deteriorate the
 137 ; created binary tree search. See PR22262.
 138 define void @test4(i32 %x, ptr %y) {
 139 ; CHECK-LABEL: test4:
 140 ; CHECK:       # %bb.0: # %entry
 141 ; CHECK-NEXT:    cmpl $39, %edi
 142 ; CHECK-NEXT:    jg .LBB3_5
 143 ; CHECK-NEXT:  # %bb.1: # %entry
 144 ; CHECK-NEXT:    cmpl $10, %edi
 145 ; CHECK-NEXT:    je .LBB3_9
 146 ; CHECK-NEXT:  # %bb.2: # %entry
 147 ; CHECK-NEXT:    cmpl $20, %edi
 148 ; CHECK-NEXT:    je .LBB3_10
 149 ; CHECK-NEXT:  # %bb.3: # %entry
 150 ; CHECK-NEXT:    cmpl $30, %edi
 151 ; CHECK-NEXT:    jne .LBB3_13
 152 ; CHECK-NEXT:  # %bb.4: # %sw.bb2
 153 ; CHECK-NEXT:    movl $3, (%rsi)
 154 ; CHECK-NEXT:    retq
 155 ; CHECK-NEXT:  .LBB3_5: # %entry
 156 ; CHECK-NEXT:    cmpl $40, %edi
 157 ; CHECK-NEXT:    je .LBB3_11
 158 ; CHECK-NEXT:  # %bb.6: # %entry
 159 ; CHECK-NEXT:    cmpl $50, %edi
 160 ; CHECK-NEXT:    je .LBB3_12
 161 ; CHECK-NEXT:  # %bb.7: # %entry
 162 ; CHECK-NEXT:    cmpl $60, %edi
 163 ; CHECK-NEXT:    jne .LBB3_13
 164 ; CHECK-NEXT:  # %bb.8: # %sw.bb5
 165 ; CHECK-NEXT:    movl $6, (%rsi)
 166 ; CHECK-NEXT:    retq
 167 ; CHECK-NEXT:  .LBB3_9: # %sw.bb
 168 ; CHECK-NEXT:    movl $1, (%rsi)
 169 ; CHECK-NEXT:    retq
 170 ; CHECK-NEXT:  .LBB3_11: # %sw.bb3
 171 ; CHECK-NEXT:    movl $4, (%rsi)
 172 ; CHECK-NEXT:    retq
 173 ; CHECK-NEXT:  .LBB3_13: # %sw.default
 174 ; CHECK-NEXT:    movl $7, (%rsi)
 175 ; CHECK-NEXT:    retq
 176 ; CHECK-NEXT:  .LBB3_10: # %sw.bb1
 177 ; CHECK-NEXT:    movl $2, (%rsi)
 178 ; CHECK-NEXT:    retq
 179 ; CHECK-NEXT:  .LBB3_12: # %sw.bb4
 180 ; CHECK-NEXT:    movl $5, (%rsi)
 181 ; CHECK-NEXT:    retq
 182
 183 entry:
 184   switch i32 %x, label %sw.default [
 185     i32 10, label %sw.bb
 186     i32 20, label %sw.bb1
 187     i32 30, label %sw.bb2
 188     i32 40, label %sw.bb3
 189     i32 50, label %sw.bb4
 190     i32 60, label %sw.bb5
 191   ]
 192 sw.bb:
 193   store i32 1, ptr %y
 194   br label %sw.epilog
 195 sw.bb1:
 196   store i32 2, ptr %y
 197   br label %sw.epilog
 198 sw.bb2:
 199   store i32 3, ptr %y
 200   br label %sw.epilog
 201 sw.bb3:
 202   store i32 4, ptr %y
 203   br label %sw.epilog
 204 sw.bb4:
 205   store i32 5, ptr %y
 206   br label %sw.epilog
 207 sw.bb5:
 208   store i32 6, ptr %y
 209   br label %sw.epilog
 210 sw.default:
 211   store i32 7, ptr %y
 212   br label %sw.epilog
 213 sw.epilog:
 214   ret void
 215
 216 ; The balanced binary switch here would start with a comparison against 39, but
 217 ; it is currently starting with 29 because of the density-sum heuristic.
 218 }
 219
 220
 221 ; Omit the range check when the default case is unreachable, see PR43129.
 222 declare void @g(i32)
 223 define void @test5(i32 %x) {
 224 ; CHECK-LABEL: test5:
 225 ; CHECK:       # %bb.0: # %entry
 226 ; CHECK-NEXT:    pushq %rax
 227 ; CHECK-NEXT:    .cfi_def_cfa_offset 16
 228 ; CHECK-NEXT:    movl $73, %eax
 229 ; CHECK-NEXT:    btl %edi, %eax
 230 ; CHECK-NEXT:    jb .LBB4_3
 231 ; CHECK-NEXT:  # %bb.1: # %entry
 232 ; CHECK-NEXT:    movl $146, %eax
 233 ; CHECK-NEXT:    btl %edi, %eax
 234 ; CHECK-NEXT:    jae .LBB4_2
 235 ; CHECK-NEXT:  # %bb.4: # %bb1
 236 ; CHECK-NEXT:    movl $1, %edi
 237 ; CHECK-NEXT:    callq g@PLT
 238 ; CHECK-NEXT:  .LBB4_3: # %bb0
 239 ; CHECK-NEXT:    xorl %edi, %edi
 240 ; CHECK-NEXT:    callq g@PLT
 241 ; CHECK-NEXT:  .LBB4_2: # %bb2
 242 ; CHECK-NEXT:    movl $2, %edi
 243 ; CHECK-NEXT:    callq g@PLT
 244
 245 entry:
 246   switch i32 %x, label %return [
 247     ; 73 = 2^0 + 2^3 + 2^6
 248     i32 0, label %bb0
 249     i32 3, label %bb0
 250     i32 6, label %bb0
 251
 252     ; 146 = 2^1 + 2^4 + 2^7
 253     i32 1, label %bb1
 254     i32 4, label %bb1
 255     i32 7, label %bb1
 256
 257     i32 2, label %bb2
 258     i32 5, label %bb2
 259     i32 8, label %bb2
 260   ]
 261 bb0: tail call void @g(i32 0) br label %return
 262 bb1: tail call void @g(i32 1) br label %return
 263 bb2: tail call void @g(i32 2) br label %return
 264 return: unreachable
 265 }