llvm/test/CodeGen/X86/switch.ll

   1 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
   2 ; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -jump-table-density=40 -switch-peel-threshold=101 -verify-machineinstrs | FileCheck %s
   3 ; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -O0 -jump-table-density=40 -verify-machineinstrs | FileCheck --check-prefix=NOOPT %s
   4
   5 declare void @g(i32)
   6
   7 ; Should be lowered as a jump table, both with and without optimization.
   8 define void @basic(i32 %x) {
   9 ; CHECK-LABEL: basic:
  10 ; CHECK:       # %bb.0: # %entry
  11 ; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
  12 ; CHECK-NEXT:    decl %edi
  13 ; CHECK-NEXT:    cmpl $4, %edi
  14 ; CHECK-NEXT:    ja .LBB0_4
  15 ; CHECK-NEXT:  # %bb.1: # %entry
  16 ; CHECK-NEXT:    jmpq *.LJTI0_0(,%rdi,8)
  17 ; CHECK-NEXT:  .LBB0_3: # %bb2
  18 ; CHECK-NEXT:    movl $1, %edi
  19 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
  20 ; CHECK-NEXT:  .LBB0_2: # %bb0
  21 ; CHECK-NEXT:    xorl %edi, %edi
  22 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
  23 ; CHECK-NEXT:  .LBB0_4: # %return
  24 ; CHECK-NEXT:    retq
  25 ;
  26 ; NOOPT-LABEL: basic:
  27 ; NOOPT:       # %bb.0: # %entry
  28 ; NOOPT-NEXT:    pushq %rax
  29 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
  30 ; NOOPT-NEXT:    movl %edi, %eax
  31 ; NOOPT-NEXT:    decl %eax
  32 ; NOOPT-NEXT:    movl %eax, %ecx
  33 ; NOOPT-NEXT:    movq %rcx, (%rsp) # 8-byte Spill
  34 ; NOOPT-NEXT:    subl $4, %eax
  35 ; NOOPT-NEXT:    ja .LBB0_4
  36 ; NOOPT-NEXT:  # %bb.5: # %entry
  37 ; NOOPT-NEXT:    movq (%rsp), %rax # 8-byte Reload
  38 ; NOOPT-NEXT:    movq .LJTI0_0(,%rax,8), %rax
  39 ; NOOPT-NEXT:    jmpq *%rax
  40 ; NOOPT-NEXT:  .LBB0_1: # %bb0
  41 ; NOOPT-NEXT:    xorl %edi, %edi
  42 ; NOOPT-NEXT:    callq g@PLT
  43 ; NOOPT-NEXT:    jmp .LBB0_4
  44 ; NOOPT-NEXT:  .LBB0_2: # %bb1
  45 ; NOOPT-NEXT:    movl $1, %edi
  46 ; NOOPT-NEXT:    callq g@PLT
  47 ; NOOPT-NEXT:    jmp .LBB0_4
  48 ; NOOPT-NEXT:  .LBB0_3: # %bb2
  49 ; NOOPT-NEXT:    movl $1, %edi
  50 ; NOOPT-NEXT:    callq g@PLT
  51 ; NOOPT-NEXT:  .LBB0_4: # %return
  52 ; NOOPT-NEXT:    popq %rax
  53 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
  54 ; NOOPT-NEXT:    retq
  55 entry:
  56   switch i32 %x, label %return [
  57     i32 3, label %bb0
  58     i32 1, label %bb1
  59     i32 4, label %bb1
  60     i32 5, label %bb2
  61   ]
  62 bb0: tail call void @g(i32 0) br label %return
  63 bb1: tail call void @g(i32 1) br label %return
  64 bb2: tail call void @g(i32 1) br label %return
  65 return: ret void
  66 }
  67
  68 ; Should never be lowered as a jump table because of the attribute
  69 define void @basic_nojumptable(i32 %x) "no-jump-tables"="true" {
  70 ; CHECK-LABEL: basic_nojumptable:
  71 ; CHECK:       # %bb.0: # %entry
  72 ; CHECK-NEXT:    cmpl $3, %edi
  73 ; CHECK-NEXT:    jg .LBB1_4
  74 ; CHECK-NEXT:  # %bb.1: # %entry
  75 ; CHECK-NEXT:    cmpl $1, %edi
  76 ; CHECK-NEXT:    je .LBB1_7
  77 ; CHECK-NEXT:  # %bb.2: # %entry
  78 ; CHECK-NEXT:    cmpl $3, %edi
  79 ; CHECK-NEXT:    jne .LBB1_6
  80 ; CHECK-NEXT:  # %bb.3: # %bb0
  81 ; CHECK-NEXT:    xorl %edi, %edi
  82 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
  83 ; CHECK-NEXT:  .LBB1_4: # %entry
  84 ; CHECK-NEXT:    cmpl $4, %edi
  85 ; CHECK-NEXT:    je .LBB1_7
  86 ; CHECK-NEXT:  # %bb.5: # %entry
  87 ; CHECK-NEXT:    cmpl $5, %edi
  88 ; CHECK-NEXT:    jne .LBB1_6
  89 ; CHECK-NEXT:  .LBB1_7: # %bb2
  90 ; CHECK-NEXT:    movl $1, %edi
  91 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
  92 ; CHECK-NEXT:  .LBB1_6: # %return
  93 ; CHECK-NEXT:    retq
  94 ;
  95 ; NOOPT-LABEL: basic_nojumptable:
  96 ; NOOPT:       # %bb.0: # %entry
  97 ; NOOPT-NEXT:    pushq %rax
  98 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
  99 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
 100 ; NOOPT-NEXT:    subl $1, %edi
 101 ; NOOPT-NEXT:    je .LBB1_2
 102 ; NOOPT-NEXT:    jmp .LBB1_5
 103 ; NOOPT-NEXT:  .LBB1_5: # %entry
 104 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 105 ; NOOPT-NEXT:    subl $3, %eax
 106 ; NOOPT-NEXT:    je .LBB1_1
 107 ; NOOPT-NEXT:    jmp .LBB1_6
 108 ; NOOPT-NEXT:  .LBB1_6: # %entry
 109 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 110 ; NOOPT-NEXT:    subl $4, %eax
 111 ; NOOPT-NEXT:    je .LBB1_2
 112 ; NOOPT-NEXT:    jmp .LBB1_7
 113 ; NOOPT-NEXT:  .LBB1_7: # %entry
 114 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 115 ; NOOPT-NEXT:    subl $5, %eax
 116 ; NOOPT-NEXT:    je .LBB1_3
 117 ; NOOPT-NEXT:    jmp .LBB1_4
 118 ; NOOPT-NEXT:  .LBB1_1: # %bb0
 119 ; NOOPT-NEXT:    xorl %edi, %edi
 120 ; NOOPT-NEXT:    callq g@PLT
 121 ; NOOPT-NEXT:    jmp .LBB1_4
 122 ; NOOPT-NEXT:  .LBB1_2: # %bb1
 123 ; NOOPT-NEXT:    movl $1, %edi
 124 ; NOOPT-NEXT:    callq g@PLT
 125 ; NOOPT-NEXT:    jmp .LBB1_4
 126 ; NOOPT-NEXT:  .LBB1_3: # %bb2
 127 ; NOOPT-NEXT:    movl $1, %edi
 128 ; NOOPT-NEXT:    callq g@PLT
 129 ; NOOPT-NEXT:  .LBB1_4: # %return
 130 ; NOOPT-NEXT:    popq %rax
 131 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
 132 ; NOOPT-NEXT:    retq
 133 entry:
 134   switch i32 %x, label %return [
 135     i32 3, label %bb0
 136     i32 1, label %bb1
 137     i32 4, label %bb1
 138     i32 5, label %bb2
 139   ]
 140 bb0: tail call void @g(i32 0) br label %return
 141 bb1: tail call void @g(i32 1) br label %return
 142 bb2: tail call void @g(i32 1) br label %return
 143 return: ret void
 144 }
 145
 146 ; Should be lowered as a jump table because of the attribute
 147 define void @basic_nojumptable_false(i32 %x) "no-jump-tables"="false" {
 148 ; CHECK-LABEL: basic_nojumptable_false:
 149 ; CHECK:       # %bb.0: # %entry
 150 ; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
 151 ; CHECK-NEXT:    decl %edi
 152 ; CHECK-NEXT:    cmpl $4, %edi
 153 ; CHECK-NEXT:    ja .LBB2_4
 154 ; CHECK-NEXT:  # %bb.1: # %entry
 155 ; CHECK-NEXT:    jmpq *.LJTI2_0(,%rdi,8)
 156 ; CHECK-NEXT:  .LBB2_3: # %bb2
 157 ; CHECK-NEXT:    movl $1, %edi
 158 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 159 ; CHECK-NEXT:  .LBB2_2: # %bb0
 160 ; CHECK-NEXT:    xorl %edi, %edi
 161 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 162 ; CHECK-NEXT:  .LBB2_4: # %return
 163 ; CHECK-NEXT:    retq
 164 ;
 165 ; NOOPT-LABEL: basic_nojumptable_false:
 166 ; NOOPT:       # %bb.0: # %entry
 167 ; NOOPT-NEXT:    pushq %rax
 168 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
 169 ; NOOPT-NEXT:    movl %edi, %eax
 170 ; NOOPT-NEXT:    decl %eax
 171 ; NOOPT-NEXT:    movl %eax, %ecx
 172 ; NOOPT-NEXT:    movq %rcx, (%rsp) # 8-byte Spill
 173 ; NOOPT-NEXT:    subl $4, %eax
 174 ; NOOPT-NEXT:    ja .LBB2_4
 175 ; NOOPT-NEXT:  # %bb.5: # %entry
 176 ; NOOPT-NEXT:    movq (%rsp), %rax # 8-byte Reload
 177 ; NOOPT-NEXT:    movq .LJTI2_0(,%rax,8), %rax
 178 ; NOOPT-NEXT:    jmpq *%rax
 179 ; NOOPT-NEXT:  .LBB2_1: # %bb0
 180 ; NOOPT-NEXT:    xorl %edi, %edi
 181 ; NOOPT-NEXT:    callq g@PLT
 182 ; NOOPT-NEXT:    jmp .LBB2_4
 183 ; NOOPT-NEXT:  .LBB2_2: # %bb1
 184 ; NOOPT-NEXT:    movl $1, %edi
 185 ; NOOPT-NEXT:    callq g@PLT
 186 ; NOOPT-NEXT:    jmp .LBB2_4
 187 ; NOOPT-NEXT:  .LBB2_3: # %bb2
 188 ; NOOPT-NEXT:    movl $1, %edi
 189 ; NOOPT-NEXT:    callq g@PLT
 190 ; NOOPT-NEXT:  .LBB2_4: # %return
 191 ; NOOPT-NEXT:    popq %rax
 192 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
 193 ; NOOPT-NEXT:    retq
 194 entry:
 195   switch i32 %x, label %return [
 196     i32 3, label %bb0
 197     i32 1, label %bb1
 198     i32 4, label %bb1
 199     i32 5, label %bb2
 200   ]
 201 bb0: tail call void @g(i32 0) br label %return
 202 bb1: tail call void @g(i32 1) br label %return
 203 bb2: tail call void @g(i32 1) br label %return
 204 return: ret void
 205 }
 206
 207
 208 ; Should be lowered to two range checks.
 209 ; We do this even at -O0, because it's cheap and makes codegen faster.
 210 define void @simple_ranges(i32 %x) {
 211 ; CHECK-LABEL: simple_ranges:
 212 ; CHECK:       # %bb.0: # %entry
 213 ; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
 214 ; CHECK-NEXT:    leal -100(%rdi), %eax
 215 ; CHECK-NEXT:    cmpl $4, %eax
 216 ; CHECK-NEXT:    jb .LBB3_3
 217 ; CHECK-NEXT:  # %bb.1: # %entry
 218 ; CHECK-NEXT:    cmpl $3, %edi
 219 ; CHECK-NEXT:    ja .LBB3_4
 220 ; CHECK-NEXT:  # %bb.2: # %bb0
 221 ; CHECK-NEXT:    xorl %edi, %edi
 222 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 223 ; CHECK-NEXT:  .LBB3_3: # %bb1
 224 ; CHECK-NEXT:    movl $1, %edi
 225 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 226 ; CHECK-NEXT:  .LBB3_4: # %return
 227 ; CHECK-NEXT:    retq
 228 ;
 229 ; NOOPT-LABEL: simple_ranges:
 230 ; NOOPT:       # %bb.0: # %entry
 231 ; NOOPT-NEXT:    pushq %rax
 232 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
 233 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
 234 ; NOOPT-NEXT:    subl $4, %edi
 235 ; NOOPT-NEXT:    jb .LBB3_1
 236 ; NOOPT-NEXT:    jmp .LBB3_4
 237 ; NOOPT-NEXT:  .LBB3_4: # %entry
 238 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 239 ; NOOPT-NEXT:    addl $-100, %eax
 240 ; NOOPT-NEXT:    subl $4, %eax
 241 ; NOOPT-NEXT:    jb .LBB3_2
 242 ; NOOPT-NEXT:    jmp .LBB3_3
 243 ; NOOPT-NEXT:  .LBB3_1: # %bb0
 244 ; NOOPT-NEXT:    xorl %edi, %edi
 245 ; NOOPT-NEXT:    callq g@PLT
 246 ; NOOPT-NEXT:    jmp .LBB3_3
 247 ; NOOPT-NEXT:  .LBB3_2: # %bb1
 248 ; NOOPT-NEXT:    movl $1, %edi
 249 ; NOOPT-NEXT:    callq g@PLT
 250 ; NOOPT-NEXT:  .LBB3_3: # %return
 251 ; NOOPT-NEXT:    popq %rax
 252 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
 253 ; NOOPT-NEXT:    retq
 254 entry:
 255   switch i32 %x, label %return [
 256     i32 0, label %bb0
 257     i32 1, label %bb0
 258     i32 2, label %bb0
 259     i32 3, label %bb0
 260     i32 100, label %bb1
 261     i32 101, label %bb1
 262     i32 102, label %bb1
 263     i32 103, label %bb1
 264   ]
 265 bb0: tail call void @g(i32 0) br label %return
 266 bb1: tail call void @g(i32 1) br label %return
 267 return: ret void
 268 }
 269
 270
 271 ; Cases 0-5 could be lowered with two bit tests,
 272 ; but with 6-8, the whole switch is suitable for a jump table.
 273 define void @jt_is_better(i32 %x) {
 274 ; CHECK-LABEL: jt_is_better:
 275 ; CHECK:       # %bb.0: # %entry
 276 ; CHECK-NEXT:    cmpl $8, %edi
 277 ; CHECK-NEXT:    ja .LBB4_7
 278 ; CHECK-NEXT:  # %bb.1: # %entry
 279 ; CHECK-NEXT:    movl %edi, %eax
 280 ; CHECK-NEXT:    jmpq *.LJTI4_0(,%rax,8)
 281 ; CHECK-NEXT:  .LBB4_2: # %bb0
 282 ; CHECK-NEXT:    xorl %edi, %edi
 283 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 284 ; CHECK-NEXT:  .LBB4_3: # %bb1
 285 ; CHECK-NEXT:    movl $1, %edi
 286 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 287 ; CHECK-NEXT:  .LBB4_5: # %bb3
 288 ; CHECK-NEXT:    movl $3, %edi
 289 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 290 ; CHECK-NEXT:  .LBB4_4: # %bb2
 291 ; CHECK-NEXT:    movl $2, %edi
 292 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 293 ; CHECK-NEXT:  .LBB4_6: # %bb4
 294 ; CHECK-NEXT:    movl $4, %edi
 295 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 296 ; CHECK-NEXT:  .LBB4_7: # %return
 297 ; CHECK-NEXT:    retq
 298 ;
 299 ; NOOPT-LABEL: jt_is_better:
 300 ; NOOPT:       # %bb.0: # %entry
 301 ; NOOPT-NEXT:    pushq %rax
 302 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
 303 ; NOOPT-NEXT:    movl %edi, %eax
 304 ; NOOPT-NEXT:    # kill: def $rax killed $eax
 305 ; NOOPT-NEXT:    movq %rax, (%rsp) # 8-byte Spill
 306 ; NOOPT-NEXT:    subl $8, %edi
 307 ; NOOPT-NEXT:    ja .LBB4_6
 308 ; NOOPT-NEXT:  # %bb.7: # %entry
 309 ; NOOPT-NEXT:    movq (%rsp), %rax # 8-byte Reload
 310 ; NOOPT-NEXT:    movq .LJTI4_0(,%rax,8), %rax
 311 ; NOOPT-NEXT:    jmpq *%rax
 312 ; NOOPT-NEXT:  .LBB4_1: # %bb0
 313 ; NOOPT-NEXT:    xorl %edi, %edi
 314 ; NOOPT-NEXT:    callq g@PLT
 315 ; NOOPT-NEXT:    jmp .LBB4_6
 316 ; NOOPT-NEXT:  .LBB4_2: # %bb1
 317 ; NOOPT-NEXT:    movl $1, %edi
 318 ; NOOPT-NEXT:    callq g@PLT
 319 ; NOOPT-NEXT:    jmp .LBB4_6
 320 ; NOOPT-NEXT:  .LBB4_3: # %bb2
 321 ; NOOPT-NEXT:    movl $2, %edi
 322 ; NOOPT-NEXT:    callq g@PLT
 323 ; NOOPT-NEXT:    jmp .LBB4_6
 324 ; NOOPT-NEXT:  .LBB4_4: # %bb3
 325 ; NOOPT-NEXT:    movl $3, %edi
 326 ; NOOPT-NEXT:    callq g@PLT
 327 ; NOOPT-NEXT:    jmp .LBB4_6
 328 ; NOOPT-NEXT:  .LBB4_5: # %bb4
 329 ; NOOPT-NEXT:    movl $4, %edi
 330 ; NOOPT-NEXT:    callq g@PLT
 331 ; NOOPT-NEXT:  .LBB4_6: # %return
 332 ; NOOPT-NEXT:    popq %rax
 333 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
 334 ; NOOPT-NEXT:    retq
 335 entry:
 336   switch i32 %x, label %return [
 337     i32 0, label %bb0
 338     i32 2, label %bb0
 339     i32 4, label %bb0
 340     i32 1, label %bb1
 341     i32 3, label %bb1
 342     i32 5, label %bb1
 343
 344     i32 6, label %bb2
 345     i32 7, label %bb3
 346     i32 8, label %bb4
 347   ]
 348 bb0: tail call void @g(i32 0) br label %return
 349 bb1: tail call void @g(i32 1) br label %return
 350 bb2: tail call void @g(i32 2) br label %return
 351 bb3: tail call void @g(i32 3) br label %return
 352 bb4: tail call void @g(i32 4) br label %return
 353 return: ret void
 354 }
 355
 356
 357 ; This could be lowered as a jump table, but bit tests is more efficient.
 358 ; The bit test on 2,5,8 is unnecessary as all cases cover the rage [0, 8].
 359 ; The range check guarantees that cases other than 0,3,6 and 1,4,7 must be
 360 ; in 2,5,8.
 361 define void @bt_is_better(i32 %x) {
 362 ; CHECK-LABEL: bt_is_better:
 363 ; CHECK:       # %bb.0: # %entry
 364 ; CHECK-NEXT:    cmpl $8, %edi
 365 ; CHECK-NEXT:    ja .LBB5_4
 366 ; CHECK-NEXT:  # %bb.1: # %entry
 367 ; CHECK-NEXT:    movl $73, %eax
 368 ; CHECK-NEXT:    btl %edi, %eax
 369 ; CHECK-NEXT:    jb .LBB5_5
 370 ; CHECK-NEXT:  # %bb.2: # %entry
 371 ; CHECK-NEXT:    movl $146, %eax
 372 ; CHECK-NEXT:    btl %edi, %eax
 373 ; CHECK-NEXT:    jae .LBB5_3
 374 ; CHECK-NEXT:  # %bb.6: # %bb1
 375 ; CHECK-NEXT:    movl $1, %edi
 376 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 377 ; CHECK-NEXT:  .LBB5_5: # %bb0
 378 ; CHECK-NEXT:    xorl %edi, %edi
 379 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 380 ; CHECK-NEXT:  .LBB5_3: # %bb2
 381 ; CHECK-NEXT:    movl $2, %edi
 382 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 383 ; CHECK-NEXT:  .LBB5_4: # %return
 384 ; CHECK-NEXT:    retq
 385 ;
 386 ; NOOPT-LABEL: bt_is_better:
 387 ; NOOPT:       # %bb.0: # %entry
 388 ; NOOPT-NEXT:    pushq %rax
 389 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
 390 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
 391 ; NOOPT-NEXT:    testl %edi, %edi
 392 ; NOOPT-NEXT:    je .LBB5_1
 393 ; NOOPT-NEXT:    jmp .LBB5_5
 394 ; NOOPT-NEXT:  .LBB5_5: # %entry
 395 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 396 ; NOOPT-NEXT:    subl $1, %eax
 397 ; NOOPT-NEXT:    je .LBB5_2
 398 ; NOOPT-NEXT:    jmp .LBB5_6
 399 ; NOOPT-NEXT:  .LBB5_6: # %entry
 400 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 401 ; NOOPT-NEXT:    subl $2, %eax
 402 ; NOOPT-NEXT:    je .LBB5_3
 403 ; NOOPT-NEXT:    jmp .LBB5_7
 404 ; NOOPT-NEXT:  .LBB5_7: # %entry
 405 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 406 ; NOOPT-NEXT:    subl $3, %eax
 407 ; NOOPT-NEXT:    je .LBB5_1
 408 ; NOOPT-NEXT:    jmp .LBB5_8
 409 ; NOOPT-NEXT:  .LBB5_8: # %entry
 410 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 411 ; NOOPT-NEXT:    subl $4, %eax
 412 ; NOOPT-NEXT:    je .LBB5_2
 413 ; NOOPT-NEXT:    jmp .LBB5_9
 414 ; NOOPT-NEXT:  .LBB5_9: # %entry
 415 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 416 ; NOOPT-NEXT:    subl $5, %eax
 417 ; NOOPT-NEXT:    je .LBB5_3
 418 ; NOOPT-NEXT:    jmp .LBB5_10
 419 ; NOOPT-NEXT:  .LBB5_10: # %entry
 420 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 421 ; NOOPT-NEXT:    subl $6, %eax
 422 ; NOOPT-NEXT:    je .LBB5_1
 423 ; NOOPT-NEXT:    jmp .LBB5_11
 424 ; NOOPT-NEXT:  .LBB5_11: # %entry
 425 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 426 ; NOOPT-NEXT:    subl $7, %eax
 427 ; NOOPT-NEXT:    je .LBB5_2
 428 ; NOOPT-NEXT:    jmp .LBB5_12
 429 ; NOOPT-NEXT:  .LBB5_12: # %entry
 430 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 431 ; NOOPT-NEXT:    subl $8, %eax
 432 ; NOOPT-NEXT:    je .LBB5_3
 433 ; NOOPT-NEXT:    jmp .LBB5_4
 434 ; NOOPT-NEXT:  .LBB5_1: # %bb0
 435 ; NOOPT-NEXT:    xorl %edi, %edi
 436 ; NOOPT-NEXT:    callq g@PLT
 437 ; NOOPT-NEXT:    jmp .LBB5_4
 438 ; NOOPT-NEXT:  .LBB5_2: # %bb1
 439 ; NOOPT-NEXT:    movl $1, %edi
 440 ; NOOPT-NEXT:    callq g@PLT
 441 ; NOOPT-NEXT:    jmp .LBB5_4
 442 ; NOOPT-NEXT:  .LBB5_3: # %bb2
 443 ; NOOPT-NEXT:    movl $2, %edi
 444 ; NOOPT-NEXT:    callq g@PLT
 445 ; NOOPT-NEXT:  .LBB5_4: # %return
 446 ; NOOPT-NEXT:    popq %rax
 447 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
 448 ; NOOPT-NEXT:    retq
 449 entry:
 450   switch i32 %x, label %return [
 451     i32 0, label %bb0
 452     i32 3, label %bb0
 453     i32 6, label %bb0
 454     i32 1, label %bb1
 455     i32 4, label %bb1
 456     i32 7, label %bb1
 457     i32 2, label %bb2
 458     i32 5, label %bb2
 459     i32 8, label %bb2
 460   ]
 461 bb0: tail call void @g(i32 0) br label %return
 462 bb1: tail call void @g(i32 1) br label %return
 463 bb2: tail call void @g(i32 2) br label %return
 464 return: ret void
 465 }
 466
 467 ; This will also be lowered as bit test, but as the range [0,8] is not fully
 468 ; covered (5 missing), the default statement can be jumped to and we end up
 469 ; with one more branch.
 470 define void @bt_is_better2(i32 %x) {
 471 ; CHECK-LABEL: bt_is_better2:
 472 ; CHECK:       # %bb.0: # %entry
 473 ; CHECK-NEXT:    cmpl $8, %edi
 474 ; CHECK-NEXT:    ja .LBB6_7
 475 ; CHECK-NEXT:  # %bb.1: # %entry
 476 ; CHECK-NEXT:    movl $73, %eax
 477 ; CHECK-NEXT:    btl %edi, %eax
 478 ; CHECK-NEXT:    jb .LBB6_5
 479 ; CHECK-NEXT:  # %bb.2: # %entry
 480 ; CHECK-NEXT:    movl $146, %eax
 481 ; CHECK-NEXT:    btl %edi, %eax
 482 ; CHECK-NEXT:    jae .LBB6_3
 483 ; CHECK-NEXT:  # %bb.6: # %bb1
 484 ; CHECK-NEXT:    movl $1, %edi
 485 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 486 ; CHECK-NEXT:  .LBB6_5: # %bb0
 487 ; CHECK-NEXT:    xorl %edi, %edi
 488 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 489 ; CHECK-NEXT:  .LBB6_3: # %entry
 490 ; CHECK-NEXT:    movl $260, %eax # imm = 0x104
 491 ; CHECK-NEXT:    btl %edi, %eax
 492 ; CHECK-NEXT:    jae .LBB6_7
 493 ; CHECK-NEXT:  # %bb.4: # %bb2
 494 ; CHECK-NEXT:    movl $2, %edi
 495 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 496 ; CHECK-NEXT:  .LBB6_7: # %return
 497 ; CHECK-NEXT:    retq
 498 ;
 499 ; NOOPT-LABEL: bt_is_better2:
 500 ; NOOPT:       # %bb.0: # %entry
 501 ; NOOPT-NEXT:    pushq %rax
 502 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
 503 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
 504 ; NOOPT-NEXT:    testl %edi, %edi
 505 ; NOOPT-NEXT:    je .LBB6_1
 506 ; NOOPT-NEXT:    jmp .LBB6_5
 507 ; NOOPT-NEXT:  .LBB6_5: # %entry
 508 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 509 ; NOOPT-NEXT:    subl $1, %eax
 510 ; NOOPT-NEXT:    je .LBB6_2
 511 ; NOOPT-NEXT:    jmp .LBB6_6
 512 ; NOOPT-NEXT:  .LBB6_6: # %entry
 513 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 514 ; NOOPT-NEXT:    subl $2, %eax
 515 ; NOOPT-NEXT:    je .LBB6_3
 516 ; NOOPT-NEXT:    jmp .LBB6_7
 517 ; NOOPT-NEXT:  .LBB6_7: # %entry
 518 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 519 ; NOOPT-NEXT:    subl $3, %eax
 520 ; NOOPT-NEXT:    je .LBB6_1
 521 ; NOOPT-NEXT:    jmp .LBB6_8
 522 ; NOOPT-NEXT:  .LBB6_8: # %entry
 523 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 524 ; NOOPT-NEXT:    subl $4, %eax
 525 ; NOOPT-NEXT:    je .LBB6_2
 526 ; NOOPT-NEXT:    jmp .LBB6_9
 527 ; NOOPT-NEXT:  .LBB6_9: # %entry
 528 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 529 ; NOOPT-NEXT:    subl $6, %eax
 530 ; NOOPT-NEXT:    je .LBB6_1
 531 ; NOOPT-NEXT:    jmp .LBB6_10
 532 ; NOOPT-NEXT:  .LBB6_10: # %entry
 533 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 534 ; NOOPT-NEXT:    subl $7, %eax
 535 ; NOOPT-NEXT:    je .LBB6_2
 536 ; NOOPT-NEXT:    jmp .LBB6_11
 537 ; NOOPT-NEXT:  .LBB6_11: # %entry
 538 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 539 ; NOOPT-NEXT:    subl $8, %eax
 540 ; NOOPT-NEXT:    je .LBB6_3
 541 ; NOOPT-NEXT:    jmp .LBB6_4
 542 ; NOOPT-NEXT:  .LBB6_1: # %bb0
 543 ; NOOPT-NEXT:    xorl %edi, %edi
 544 ; NOOPT-NEXT:    callq g@PLT
 545 ; NOOPT-NEXT:    jmp .LBB6_4
 546 ; NOOPT-NEXT:  .LBB6_2: # %bb1
 547 ; NOOPT-NEXT:    movl $1, %edi
 548 ; NOOPT-NEXT:    callq g@PLT
 549 ; NOOPT-NEXT:    jmp .LBB6_4
 550 ; NOOPT-NEXT:  .LBB6_3: # %bb2
 551 ; NOOPT-NEXT:    movl $2, %edi
 552 ; NOOPT-NEXT:    callq g@PLT
 553 ; NOOPT-NEXT:  .LBB6_4: # %return
 554 ; NOOPT-NEXT:    popq %rax
 555 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
 556 ; NOOPT-NEXT:    retq
 557 entry:
 558   switch i32 %x, label %return [
 559     i32 0, label %bb0
 560     i32 3, label %bb0
 561     i32 6, label %bb0
 562     i32 1, label %bb1
 563     i32 4, label %bb1
 564     i32 7, label %bb1
 565     i32 2, label %bb2
 566     i32 8, label %bb2
 567   ]
 568 bb0: tail call void @g(i32 0) br label %return
 569 bb1: tail call void @g(i32 1) br label %return
 570 bb2: tail call void @g(i32 2) br label %return
 571 return: ret void
 572 }
 573
 574 define void @bt_is_better3(i32 %x) {
 575 ; CHECK-LABEL: bt_is_better3:
 576 ; CHECK:       # %bb.0: # %entry
 577 ; CHECK-NEXT:    cmpl $18, %edi
 578 ; CHECK-NEXT:    ja .LBB7_7
 579 ; CHECK-NEXT:  # %bb.1: # %entry
 580 ; CHECK-NEXT:    movl $74752, %eax # imm = 0x12400
 581 ; CHECK-NEXT:    btl %edi, %eax
 582 ; CHECK-NEXT:    jb .LBB7_5
 583 ; CHECK-NEXT:  # %bb.2: # %entry
 584 ; CHECK-NEXT:    movl $149504, %eax # imm = 0x24800
 585 ; CHECK-NEXT:    btl %edi, %eax
 586 ; CHECK-NEXT:    jae .LBB7_3
 587 ; CHECK-NEXT:  # %bb.6: # %bb1
 588 ; CHECK-NEXT:    movl $1, %edi
 589 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 590 ; CHECK-NEXT:  .LBB7_5: # %bb0
 591 ; CHECK-NEXT:    xorl %edi, %edi
 592 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 593 ; CHECK-NEXT:  .LBB7_3: # %entry
 594 ; CHECK-NEXT:    movl $266240, %eax # imm = 0x41000
 595 ; CHECK-NEXT:    btl %edi, %eax
 596 ; CHECK-NEXT:    jae .LBB7_7
 597 ; CHECK-NEXT:  # %bb.4: # %bb2
 598 ; CHECK-NEXT:    movl $2, %edi
 599 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 600 ; CHECK-NEXT:  .LBB7_7: # %return
 601 ; CHECK-NEXT:    retq
 602 ;
 603 ; NOOPT-LABEL: bt_is_better3:
 604 ; NOOPT:       # %bb.0: # %entry
 605 ; NOOPT-NEXT:    pushq %rax
 606 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
 607 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
 608 ; NOOPT-NEXT:    subl $10, %edi
 609 ; NOOPT-NEXT:    je .LBB7_1
 610 ; NOOPT-NEXT:    jmp .LBB7_5
 611 ; NOOPT-NEXT:  .LBB7_5: # %entry
 612 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 613 ; NOOPT-NEXT:    subl $11, %eax
 614 ; NOOPT-NEXT:    je .LBB7_2
 615 ; NOOPT-NEXT:    jmp .LBB7_6
 616 ; NOOPT-NEXT:  .LBB7_6: # %entry
 617 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 618 ; NOOPT-NEXT:    subl $12, %eax
 619 ; NOOPT-NEXT:    je .LBB7_3
 620 ; NOOPT-NEXT:    jmp .LBB7_7
 621 ; NOOPT-NEXT:  .LBB7_7: # %entry
 622 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 623 ; NOOPT-NEXT:    subl $13, %eax
 624 ; NOOPT-NEXT:    je .LBB7_1
 625 ; NOOPT-NEXT:    jmp .LBB7_8
 626 ; NOOPT-NEXT:  .LBB7_8: # %entry
 627 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 628 ; NOOPT-NEXT:    subl $14, %eax
 629 ; NOOPT-NEXT:    je .LBB7_2
 630 ; NOOPT-NEXT:    jmp .LBB7_9
 631 ; NOOPT-NEXT:  .LBB7_9: # %entry
 632 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 633 ; NOOPT-NEXT:    subl $16, %eax
 634 ; NOOPT-NEXT:    je .LBB7_1
 635 ; NOOPT-NEXT:    jmp .LBB7_10
 636 ; NOOPT-NEXT:  .LBB7_10: # %entry
 637 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 638 ; NOOPT-NEXT:    subl $17, %eax
 639 ; NOOPT-NEXT:    je .LBB7_2
 640 ; NOOPT-NEXT:    jmp .LBB7_11
 641 ; NOOPT-NEXT:  .LBB7_11: # %entry
 642 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 643 ; NOOPT-NEXT:    subl $18, %eax
 644 ; NOOPT-NEXT:    je .LBB7_3
 645 ; NOOPT-NEXT:    jmp .LBB7_4
 646 ; NOOPT-NEXT:  .LBB7_1: # %bb0
 647 ; NOOPT-NEXT:    xorl %edi, %edi
 648 ; NOOPT-NEXT:    callq g@PLT
 649 ; NOOPT-NEXT:    jmp .LBB7_4
 650 ; NOOPT-NEXT:  .LBB7_2: # %bb1
 651 ; NOOPT-NEXT:    movl $1, %edi
 652 ; NOOPT-NEXT:    callq g@PLT
 653 ; NOOPT-NEXT:    jmp .LBB7_4
 654 ; NOOPT-NEXT:  .LBB7_3: # %bb2
 655 ; NOOPT-NEXT:    movl $2, %edi
 656 ; NOOPT-NEXT:    callq g@PLT
 657 ; NOOPT-NEXT:  .LBB7_4: # %return
 658 ; NOOPT-NEXT:    popq %rax
 659 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
 660 ; NOOPT-NEXT:    retq
 661 entry:
 662   switch i32 %x, label %return [
 663     i32 10, label %bb0
 664     i32 13, label %bb0
 665     i32 16, label %bb0
 666     i32 11, label %bb1
 667     i32 14, label %bb1
 668     i32 17, label %bb1
 669     i32 12, label %bb2
 670     i32 18, label %bb2
 671   ]
 672 bb0: tail call void @g(i32 0) br label %return
 673 bb1: tail call void @g(i32 1) br label %return
 674 bb2: tail call void @g(i32 2) br label %return
 675 return: ret void
 676
 677 ; We don't have to subtract 10 from the case value to let the range become
 678 ; [0, 8], as each value in the range [10, 18] can be represented by bits in a
 679 ; word. Then we still need a branch to jump to the default statement for the
 680 ; range [0, 10).
 681 ; 74752 = 2^10 + 2^13 + 2^16
 682 ; 149504 = 2^11 + 2^14 + 2^17
 683 ; 266240 = 2^12 + 2^15 + 2^18
 684 }
 685
 686
 687 ; Should pivot around 400 for two subtrees of equal size.
 688 define void @optimal_pivot1(i32 %x) {
 689 ; CHECK-LABEL: optimal_pivot1:
 690 ; CHECK:       # %bb.0: # %entry
 691 ; CHECK-NEXT:    cmpl $399, %edi # imm = 0x18F
 692 ; CHECK-NEXT:    jg .LBB8_5
 693 ; CHECK-NEXT:  # %bb.1: # %entry
 694 ; CHECK-NEXT:    cmpl $100, %edi
 695 ; CHECK-NEXT:    je .LBB8_8
 696 ; CHECK-NEXT:  # %bb.2: # %entry
 697 ; CHECK-NEXT:    cmpl $200, %edi
 698 ; CHECK-NEXT:    je .LBB8_9
 699 ; CHECK-NEXT:  # %bb.3: # %entry
 700 ; CHECK-NEXT:    cmpl $300, %edi # imm = 0x12C
 701 ; CHECK-NEXT:    je .LBB8_8
 702 ; CHECK-NEXT:  .LBB8_4: # %return
 703 ; CHECK-NEXT:    retq
 704 ; CHECK-NEXT:  .LBB8_5: # %entry
 705 ; CHECK-NEXT:    cmpl $400, %edi # imm = 0x190
 706 ; CHECK-NEXT:    je .LBB8_9
 707 ; CHECK-NEXT:  # %bb.6: # %entry
 708 ; CHECK-NEXT:    cmpl $600, %edi # imm = 0x258
 709 ; CHECK-NEXT:    je .LBB8_9
 710 ; CHECK-NEXT:  # %bb.7: # %entry
 711 ; CHECK-NEXT:    cmpl $500, %edi # imm = 0x1F4
 712 ; CHECK-NEXT:    jne .LBB8_4
 713 ; CHECK-NEXT:  .LBB8_8: # %bb0
 714 ; CHECK-NEXT:    xorl %edi, %edi
 715 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 716 ; CHECK-NEXT:  .LBB8_9: # %bb1
 717 ; CHECK-NEXT:    movl $1, %edi
 718 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 719 ;
 720 ; NOOPT-LABEL: optimal_pivot1:
 721 ; NOOPT:       # %bb.0: # %entry
 722 ; NOOPT-NEXT:    pushq %rax
 723 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
 724 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
 725 ; NOOPT-NEXT:    subl $100, %edi
 726 ; NOOPT-NEXT:    je .LBB8_1
 727 ; NOOPT-NEXT:    jmp .LBB8_4
 728 ; NOOPT-NEXT:  .LBB8_4: # %entry
 729 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 730 ; NOOPT-NEXT:    subl $200, %eax
 731 ; NOOPT-NEXT:    je .LBB8_2
 732 ; NOOPT-NEXT:    jmp .LBB8_5
 733 ; NOOPT-NEXT:  .LBB8_5: # %entry
 734 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 735 ; NOOPT-NEXT:    subl $300, %eax # imm = 0x12C
 736 ; NOOPT-NEXT:    je .LBB8_1
 737 ; NOOPT-NEXT:    jmp .LBB8_6
 738 ; NOOPT-NEXT:  .LBB8_6: # %entry
 739 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 740 ; NOOPT-NEXT:    subl $400, %eax # imm = 0x190
 741 ; NOOPT-NEXT:    je .LBB8_2
 742 ; NOOPT-NEXT:    jmp .LBB8_7
 743 ; NOOPT-NEXT:  .LBB8_7: # %entry
 744 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 745 ; NOOPT-NEXT:    subl $500, %eax # imm = 0x1F4
 746 ; NOOPT-NEXT:    je .LBB8_1
 747 ; NOOPT-NEXT:    jmp .LBB8_8
 748 ; NOOPT-NEXT:  .LBB8_8: # %entry
 749 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 750 ; NOOPT-NEXT:    subl $600, %eax # imm = 0x258
 751 ; NOOPT-NEXT:    je .LBB8_2
 752 ; NOOPT-NEXT:    jmp .LBB8_3
 753 ; NOOPT-NEXT:  .LBB8_1: # %bb0
 754 ; NOOPT-NEXT:    xorl %edi, %edi
 755 ; NOOPT-NEXT:    callq g@PLT
 756 ; NOOPT-NEXT:    jmp .LBB8_3
 757 ; NOOPT-NEXT:  .LBB8_2: # %bb1
 758 ; NOOPT-NEXT:    movl $1, %edi
 759 ; NOOPT-NEXT:    callq g@PLT
 760 ; NOOPT-NEXT:  .LBB8_3: # %return
 761 ; NOOPT-NEXT:    popq %rax
 762 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
 763 ; NOOPT-NEXT:    retq
 764 entry:
 765   switch i32 %x, label %return [
 766     i32 100, label %bb0
 767     i32 200, label %bb1
 768     i32 300, label %bb0
 769     i32 400, label %bb1
 770     i32 500, label %bb0
 771     i32 600, label %bb1
 772
 773   ]
 774 bb0: tail call void @g(i32 0) br label %return
 775 bb1: tail call void @g(i32 1) br label %return
 776 return: ret void
 777 }
 778
 779
 780 ; Should pivot around 300 for two subtrees with two jump tables each.
 781 define void @optimal_pivot2(i32 %x) {
 782 ; CHECK-LABEL: optimal_pivot2:
 783 ; CHECK:       # %bb.0: # %entry
 784 ; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
 785 ; CHECK-NEXT:    cmpl $299, %edi # imm = 0x12B
 786 ; CHECK-NEXT:    jg .LBB9_4
 787 ; CHECK-NEXT:  # %bb.1: # %entry
 788 ; CHECK-NEXT:    leal -100(%rdi), %eax
 789 ; CHECK-NEXT:    cmpl $3, %eax
 790 ; CHECK-NEXT:    jbe .LBB9_12
 791 ; CHECK-NEXT:  # %bb.2: # %entry
 792 ; CHECK-NEXT:    addl $-200, %edi
 793 ; CHECK-NEXT:    cmpl $3, %edi
 794 ; CHECK-NEXT:    ja .LBB9_11
 795 ; CHECK-NEXT:  # %bb.3: # %entry
 796 ; CHECK-NEXT:    jmpq *.LJTI9_1(,%rdi,8)
 797 ; CHECK-NEXT:  .LBB9_4: # %entry
 798 ; CHECK-NEXT:    leal -300(%rdi), %eax
 799 ; CHECK-NEXT:    cmpl $3, %eax
 800 ; CHECK-NEXT:    jbe .LBB9_13
 801 ; CHECK-NEXT:  # %bb.5: # %entry
 802 ; CHECK-NEXT:    addl $-400, %edi # imm = 0xFE70
 803 ; CHECK-NEXT:    cmpl $3, %edi
 804 ; CHECK-NEXT:    ja .LBB9_11
 805 ; CHECK-NEXT:  # %bb.6: # %entry
 806 ; CHECK-NEXT:    jmpq *.LJTI9_3(,%rdi,8)
 807 ; CHECK-NEXT:  .LBB9_12: # %entry
 808 ; CHECK-NEXT:    jmpq *.LJTI9_0(,%rax,8)
 809 ; CHECK-NEXT:  .LBB9_13: # %entry
 810 ; CHECK-NEXT:    jmpq *.LJTI9_2(,%rax,8)
 811 ; CHECK-NEXT:  .LBB9_7: # %bb0
 812 ; CHECK-NEXT:    xorl %edi, %edi
 813 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 814 ; CHECK-NEXT:  .LBB9_9: # %bb2
 815 ; CHECK-NEXT:    movl $2, %edi
 816 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 817 ; CHECK-NEXT:  .LBB9_10: # %bb3
 818 ; CHECK-NEXT:    movl $3, %edi
 819 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 820 ; CHECK-NEXT:  .LBB9_8: # %bb1
 821 ; CHECK-NEXT:    movl $1, %edi
 822 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 823 ; CHECK-NEXT:  .LBB9_11: # %return
 824 ; CHECK-NEXT:    retq
 825 ;
 826 ; NOOPT-LABEL: optimal_pivot2:
 827 ; NOOPT:       # %bb.0: # %entry
 828 ; NOOPT-NEXT:    pushq %rax
 829 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
 830 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
 831 ; NOOPT-NEXT:    subl $100, %edi
 832 ; NOOPT-NEXT:    je .LBB9_1
 833 ; NOOPT-NEXT:    jmp .LBB9_6
 834 ; NOOPT-NEXT:  .LBB9_6: # %entry
 835 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 836 ; NOOPT-NEXT:    subl $101, %eax
 837 ; NOOPT-NEXT:    je .LBB9_2
 838 ; NOOPT-NEXT:    jmp .LBB9_7
 839 ; NOOPT-NEXT:  .LBB9_7: # %entry
 840 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 841 ; NOOPT-NEXT:    subl $102, %eax
 842 ; NOOPT-NEXT:    je .LBB9_3
 843 ; NOOPT-NEXT:    jmp .LBB9_8
 844 ; NOOPT-NEXT:  .LBB9_8: # %entry
 845 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 846 ; NOOPT-NEXT:    subl $103, %eax
 847 ; NOOPT-NEXT:    je .LBB9_4
 848 ; NOOPT-NEXT:    jmp .LBB9_9
 849 ; NOOPT-NEXT:  .LBB9_9: # %entry
 850 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 851 ; NOOPT-NEXT:    subl $200, %eax
 852 ; NOOPT-NEXT:    je .LBB9_1
 853 ; NOOPT-NEXT:    jmp .LBB9_10
 854 ; NOOPT-NEXT:  .LBB9_10: # %entry
 855 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 856 ; NOOPT-NEXT:    subl $201, %eax
 857 ; NOOPT-NEXT:    je .LBB9_2
 858 ; NOOPT-NEXT:    jmp .LBB9_11
 859 ; NOOPT-NEXT:  .LBB9_11: # %entry
 860 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 861 ; NOOPT-NEXT:    subl $202, %eax
 862 ; NOOPT-NEXT:    je .LBB9_3
 863 ; NOOPT-NEXT:    jmp .LBB9_12
 864 ; NOOPT-NEXT:  .LBB9_12: # %entry
 865 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 866 ; NOOPT-NEXT:    subl $203, %eax
 867 ; NOOPT-NEXT:    je .LBB9_4
 868 ; NOOPT-NEXT:    jmp .LBB9_13
 869 ; NOOPT-NEXT:  .LBB9_13: # %entry
 870 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 871 ; NOOPT-NEXT:    subl $300, %eax # imm = 0x12C
 872 ; NOOPT-NEXT:    je .LBB9_1
 873 ; NOOPT-NEXT:    jmp .LBB9_14
 874 ; NOOPT-NEXT:  .LBB9_14: # %entry
 875 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 876 ; NOOPT-NEXT:    subl $301, %eax # imm = 0x12D
 877 ; NOOPT-NEXT:    je .LBB9_2
 878 ; NOOPT-NEXT:    jmp .LBB9_15
 879 ; NOOPT-NEXT:  .LBB9_15: # %entry
 880 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 881 ; NOOPT-NEXT:    subl $302, %eax # imm = 0x12E
 882 ; NOOPT-NEXT:    je .LBB9_3
 883 ; NOOPT-NEXT:    jmp .LBB9_16
 884 ; NOOPT-NEXT:  .LBB9_16: # %entry
 885 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 886 ; NOOPT-NEXT:    subl $303, %eax # imm = 0x12F
 887 ; NOOPT-NEXT:    je .LBB9_4
 888 ; NOOPT-NEXT:    jmp .LBB9_17
 889 ; NOOPT-NEXT:  .LBB9_17: # %entry
 890 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 891 ; NOOPT-NEXT:    subl $400, %eax # imm = 0x190
 892 ; NOOPT-NEXT:    je .LBB9_1
 893 ; NOOPT-NEXT:    jmp .LBB9_18
 894 ; NOOPT-NEXT:  .LBB9_18: # %entry
 895 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 896 ; NOOPT-NEXT:    subl $401, %eax # imm = 0x191
 897 ; NOOPT-NEXT:    je .LBB9_2
 898 ; NOOPT-NEXT:    jmp .LBB9_19
 899 ; NOOPT-NEXT:  .LBB9_19: # %entry
 900 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 901 ; NOOPT-NEXT:    subl $402, %eax # imm = 0x192
 902 ; NOOPT-NEXT:    je .LBB9_3
 903 ; NOOPT-NEXT:    jmp .LBB9_20
 904 ; NOOPT-NEXT:  .LBB9_20: # %entry
 905 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 906 ; NOOPT-NEXT:    subl $403, %eax # imm = 0x193
 907 ; NOOPT-NEXT:    je .LBB9_4
 908 ; NOOPT-NEXT:    jmp .LBB9_5
 909 ; NOOPT-NEXT:  .LBB9_1: # %bb0
 910 ; NOOPT-NEXT:    xorl %edi, %edi
 911 ; NOOPT-NEXT:    callq g@PLT
 912 ; NOOPT-NEXT:    jmp .LBB9_5
 913 ; NOOPT-NEXT:  .LBB9_2: # %bb1
 914 ; NOOPT-NEXT:    movl $1, %edi
 915 ; NOOPT-NEXT:    callq g@PLT
 916 ; NOOPT-NEXT:    jmp .LBB9_5
 917 ; NOOPT-NEXT:  .LBB9_3: # %bb2
 918 ; NOOPT-NEXT:    movl $2, %edi
 919 ; NOOPT-NEXT:    callq g@PLT
 920 ; NOOPT-NEXT:    jmp .LBB9_5
 921 ; NOOPT-NEXT:  .LBB9_4: # %bb3
 922 ; NOOPT-NEXT:    movl $3, %edi
 923 ; NOOPT-NEXT:    callq g@PLT
 924 ; NOOPT-NEXT:  .LBB9_5: # %return
 925 ; NOOPT-NEXT:    popq %rax
 926 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
 927 ; NOOPT-NEXT:    retq
 928 entry:
 929   switch i32 %x, label %return [
 930     i32 100, label %bb0   i32 101, label %bb1   i32 102, label %bb2   i32 103, label %bb3
 931     i32 200, label %bb0   i32 201, label %bb1   i32 202, label %bb2   i32 203, label %bb3
 932     i32 300, label %bb0   i32 301, label %bb1   i32 302, label %bb2   i32 303, label %bb3
 933     i32 400, label %bb0   i32 401, label %bb1   i32 402, label %bb2   i32 403, label %bb3
 934
 935   ]
 936 bb0: tail call void @g(i32 0) br label %return
 937 bb1: tail call void @g(i32 1) br label %return
 938 bb2: tail call void @g(i32 2) br label %return
 939 bb3: tail call void @g(i32 3) br label %return
 940 return: ret void
 941 }
 942
 943
 944 ; Splitting in the largest gap (between 6 and 12) would yield suboptimal result.
 945 ; Expecting a jump table from 5 to 15.
 946 ; At -O0, we don't build jump tables for only parts of a switch.
 947 define void @optimal_jump_table1(i32 %x) {
 948 ; CHECK-LABEL: optimal_jump_table1:
 949 ; CHECK:       # %bb.0: # %entry
 950 ; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
 951 ; CHECK-NEXT:    leal -5(%rdi), %eax
 952 ; CHECK-NEXT:    cmpl $10, %eax
 953 ; CHECK-NEXT:    ja .LBB10_1
 954 ; CHECK-NEXT:  # %bb.9: # %entry
 955 ; CHECK-NEXT:    jmpq *.LJTI10_0(,%rax,8)
 956 ; CHECK-NEXT:  .LBB10_3: # %bb1
 957 ; CHECK-NEXT:    movl $1, %edi
 958 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 959 ; CHECK-NEXT:  .LBB10_1: # %entry
 960 ; CHECK-NEXT:    testl %edi, %edi
 961 ; CHECK-NEXT:    jne .LBB10_8
 962 ; CHECK-NEXT:  # %bb.2: # %bb0
 963 ; CHECK-NEXT:    xorl %edi, %edi
 964 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 965 ; CHECK-NEXT:  .LBB10_8: # %return
 966 ; CHECK-NEXT:    retq
 967 ; CHECK-NEXT:  .LBB10_7: # %bb5
 968 ; CHECK-NEXT:    movl $5, %edi
 969 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 970 ; CHECK-NEXT:  .LBB10_5: # %bb3
 971 ; CHECK-NEXT:    movl $3, %edi
 972 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 973 ; CHECK-NEXT:  .LBB10_4: # %bb2
 974 ; CHECK-NEXT:    movl $2, %edi
 975 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 976 ; CHECK-NEXT:  .LBB10_6: # %bb4
 977 ; CHECK-NEXT:    movl $4, %edi
 978 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
 979 ;
 980 ; NOOPT-LABEL: optimal_jump_table1:
 981 ; NOOPT:       # %bb.0: # %entry
 982 ; NOOPT-NEXT:    pushq %rax
 983 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
 984 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
 985 ; NOOPT-NEXT:    testl %edi, %edi
 986 ; NOOPT-NEXT:    je .LBB10_1
 987 ; NOOPT-NEXT:    jmp .LBB10_8
 988 ; NOOPT-NEXT:  .LBB10_8: # %entry
 989 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 990 ; NOOPT-NEXT:    subl $5, %eax
 991 ; NOOPT-NEXT:    je .LBB10_2
 992 ; NOOPT-NEXT:    jmp .LBB10_9
 993 ; NOOPT-NEXT:  .LBB10_9: # %entry
 994 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
 995 ; NOOPT-NEXT:    subl $6, %eax
 996 ; NOOPT-NEXT:    je .LBB10_3
 997 ; NOOPT-NEXT:    jmp .LBB10_10
 998 ; NOOPT-NEXT:  .LBB10_10: # %entry
 999 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1000 ; NOOPT-NEXT:    subl $12, %eax
1001 ; NOOPT-NEXT:    je .LBB10_4
1002 ; NOOPT-NEXT:    jmp .LBB10_11
1003 ; NOOPT-NEXT:  .LBB10_11: # %entry
1004 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1005 ; NOOPT-NEXT:    subl $13, %eax
1006 ; NOOPT-NEXT:    je .LBB10_5
1007 ; NOOPT-NEXT:    jmp .LBB10_12
1008 ; NOOPT-NEXT:  .LBB10_12: # %entry
1009 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1010 ; NOOPT-NEXT:    subl $15, %eax
1011 ; NOOPT-NEXT:    je .LBB10_6
1012 ; NOOPT-NEXT:    jmp .LBB10_7
1013 ; NOOPT-NEXT:  .LBB10_1: # %bb0
1014 ; NOOPT-NEXT:    xorl %edi, %edi
1015 ; NOOPT-NEXT:    callq g@PLT
1016 ; NOOPT-NEXT:    jmp .LBB10_7
1017 ; NOOPT-NEXT:  .LBB10_2: # %bb1
1018 ; NOOPT-NEXT:    movl $1, %edi
1019 ; NOOPT-NEXT:    callq g@PLT
1020 ; NOOPT-NEXT:    jmp .LBB10_7
1021 ; NOOPT-NEXT:  .LBB10_3: # %bb2
1022 ; NOOPT-NEXT:    movl $2, %edi
1023 ; NOOPT-NEXT:    callq g@PLT
1024 ; NOOPT-NEXT:    jmp .LBB10_7
1025 ; NOOPT-NEXT:  .LBB10_4: # %bb3
1026 ; NOOPT-NEXT:    movl $3, %edi
1027 ; NOOPT-NEXT:    callq g@PLT
1028 ; NOOPT-NEXT:    jmp .LBB10_7
1029 ; NOOPT-NEXT:  .LBB10_5: # %bb4
1030 ; NOOPT-NEXT:    movl $4, %edi
1031 ; NOOPT-NEXT:    callq g@PLT
1032 ; NOOPT-NEXT:    jmp .LBB10_7
1033 ; NOOPT-NEXT:  .LBB10_6: # %bb5
1034 ; NOOPT-NEXT:    movl $5, %edi
1035 ; NOOPT-NEXT:    callq g@PLT
1036 ; NOOPT-NEXT:  .LBB10_7: # %return
1037 ; NOOPT-NEXT:    popq %rax
1038 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
1039 ; NOOPT-NEXT:    retq
1040 entry:
1041   switch i32 %x, label %return [
1042     i32 0,  label %bb0
1043     i32 5,  label %bb1
1044     i32 6,  label %bb2
1045     i32 12, label %bb3
1046     i32 13, label %bb4
1047     i32 15, label %bb5
1048   ]
1049 bb0: tail call void @g(i32 0) br label %return
1050 bb1: tail call void @g(i32 1) br label %return
1051 bb2: tail call void @g(i32 2) br label %return
1052 bb3: tail call void @g(i32 3) br label %return
1053 bb4: tail call void @g(i32 4) br label %return
1054 bb5: tail call void @g(i32 5) br label %return
1055 return: ret void
1056 }
1057
1058
1059 ; Partitioning the cases to the minimum number of dense sets is not good enough.
1060 ; This can be partitioned as {0,1,2,9},{14,15} or {0,1,2},{9,14,15}. The former
1061 ; should be preferred. Expecting a table from 0-9.
1062 define void @optimal_jump_table2(i32 %x) {
1063 ; CHECK-LABEL: optimal_jump_table2:
1064 ; CHECK:       # %bb.0: # %entry
1065 ; CHECK-NEXT:    cmpl $9, %edi
1066 ; CHECK-NEXT:    ja .LBB11_1
1067 ; CHECK-NEXT:  # %bb.10: # %entry
1068 ; CHECK-NEXT:    movl %edi, %eax
1069 ; CHECK-NEXT:    jmpq *.LJTI11_0(,%rax,8)
1070 ; CHECK-NEXT:  .LBB11_4: # %bb0
1071 ; CHECK-NEXT:    xorl %edi, %edi
1072 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1073 ; CHECK-NEXT:  .LBB11_1: # %entry
1074 ; CHECK-NEXT:    cmpl $14, %edi
1075 ; CHECK-NEXT:    je .LBB11_8
1076 ; CHECK-NEXT:  # %bb.2: # %entry
1077 ; CHECK-NEXT:    cmpl $15, %edi
1078 ; CHECK-NEXT:    jne .LBB11_9
1079 ; CHECK-NEXT:  # %bb.3: # %bb5
1080 ; CHECK-NEXT:    movl $5, %edi
1081 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1082 ; CHECK-NEXT:  .LBB11_9: # %return
1083 ; CHECK-NEXT:    retq
1084 ; CHECK-NEXT:  .LBB11_7: # %bb3
1085 ; CHECK-NEXT:    movl $3, %edi
1086 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1087 ; CHECK-NEXT:  .LBB11_5: # %bb1
1088 ; CHECK-NEXT:    movl $1, %edi
1089 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1090 ; CHECK-NEXT:  .LBB11_6: # %bb2
1091 ; CHECK-NEXT:    movl $2, %edi
1092 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1093 ; CHECK-NEXT:  .LBB11_8: # %bb4
1094 ; CHECK-NEXT:    movl $4, %edi
1095 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1096 ;
1097 ; NOOPT-LABEL: optimal_jump_table2:
1098 ; NOOPT:       # %bb.0: # %entry
1099 ; NOOPT-NEXT:    pushq %rax
1100 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
1101 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
1102 ; NOOPT-NEXT:    testl %edi, %edi
1103 ; NOOPT-NEXT:    je .LBB11_1
1104 ; NOOPT-NEXT:    jmp .LBB11_8
1105 ; NOOPT-NEXT:  .LBB11_8: # %entry
1106 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1107 ; NOOPT-NEXT:    subl $1, %eax
1108 ; NOOPT-NEXT:    je .LBB11_2
1109 ; NOOPT-NEXT:    jmp .LBB11_9
1110 ; NOOPT-NEXT:  .LBB11_9: # %entry
1111 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1112 ; NOOPT-NEXT:    subl $2, %eax
1113 ; NOOPT-NEXT:    je .LBB11_3
1114 ; NOOPT-NEXT:    jmp .LBB11_10
1115 ; NOOPT-NEXT:  .LBB11_10: # %entry
1116 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1117 ; NOOPT-NEXT:    subl $9, %eax
1118 ; NOOPT-NEXT:    je .LBB11_4
1119 ; NOOPT-NEXT:    jmp .LBB11_11
1120 ; NOOPT-NEXT:  .LBB11_11: # %entry
1121 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1122 ; NOOPT-NEXT:    subl $14, %eax
1123 ; NOOPT-NEXT:    je .LBB11_5
1124 ; NOOPT-NEXT:    jmp .LBB11_12
1125 ; NOOPT-NEXT:  .LBB11_12: # %entry
1126 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1127 ; NOOPT-NEXT:    subl $15, %eax
1128 ; NOOPT-NEXT:    je .LBB11_6
1129 ; NOOPT-NEXT:    jmp .LBB11_7
1130 ; NOOPT-NEXT:  .LBB11_1: # %bb0
1131 ; NOOPT-NEXT:    xorl %edi, %edi
1132 ; NOOPT-NEXT:    callq g@PLT
1133 ; NOOPT-NEXT:    jmp .LBB11_7
1134 ; NOOPT-NEXT:  .LBB11_2: # %bb1
1135 ; NOOPT-NEXT:    movl $1, %edi
1136 ; NOOPT-NEXT:    callq g@PLT
1137 ; NOOPT-NEXT:    jmp .LBB11_7
1138 ; NOOPT-NEXT:  .LBB11_3: # %bb2
1139 ; NOOPT-NEXT:    movl $2, %edi
1140 ; NOOPT-NEXT:    callq g@PLT
1141 ; NOOPT-NEXT:    jmp .LBB11_7
1142 ; NOOPT-NEXT:  .LBB11_4: # %bb3
1143 ; NOOPT-NEXT:    movl $3, %edi
1144 ; NOOPT-NEXT:    callq g@PLT
1145 ; NOOPT-NEXT:    jmp .LBB11_7
1146 ; NOOPT-NEXT:  .LBB11_5: # %bb4
1147 ; NOOPT-NEXT:    movl $4, %edi
1148 ; NOOPT-NEXT:    callq g@PLT
1149 ; NOOPT-NEXT:    jmp .LBB11_7
1150 ; NOOPT-NEXT:  .LBB11_6: # %bb5
1151 ; NOOPT-NEXT:    movl $5, %edi
1152 ; NOOPT-NEXT:    callq g@PLT
1153 ; NOOPT-NEXT:  .LBB11_7: # %return
1154 ; NOOPT-NEXT:    popq %rax
1155 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
1156 ; NOOPT-NEXT:    retq
1157 entry:
1158   switch i32 %x, label %return [
1159     i32 0,  label %bb0
1160     i32 1,  label %bb1
1161     i32 2,  label %bb2
1162     i32 9,  label %bb3
1163     i32 14, label %bb4
1164     i32 15, label %bb5
1165   ]
1166 bb0: tail call void @g(i32 0) br label %return
1167 bb1: tail call void @g(i32 1) br label %return
1168 bb2: tail call void @g(i32 2) br label %return
1169 bb3: tail call void @g(i32 3) br label %return
1170 bb4: tail call void @g(i32 4) br label %return
1171 bb5: tail call void @g(i32 5) br label %return
1172 return: ret void
1173 }
1174
1175
1176 ; Splitting to maximize left-right density sum and gap size would split this
1177 ; between 3 and 10, and then between 20 and 25. It's better to build a table
1178 ; from 1-20.
1179 define void @optimal_jump_table3(i32 %x) {
1180 ; CHECK-LABEL: optimal_jump_table3:
1181 ; CHECK:       # %bb.0: # %entry
1182 ; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
1183 ; CHECK-NEXT:    leal -1(%rdi), %eax
1184 ; CHECK-NEXT:    cmpl $19, %eax
1185 ; CHECK-NEXT:    ja .LBB12_1
1186 ; CHECK-NEXT:  # %bb.3: # %entry
1187 ; CHECK-NEXT:    jmpq *.LJTI12_0(,%rax,8)
1188 ; CHECK-NEXT:  .LBB12_4: # %bb0
1189 ; CHECK-NEXT:    xorl %edi, %edi
1190 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1191 ; CHECK-NEXT:  .LBB12_6: # %bb2
1192 ; CHECK-NEXT:    movl $2, %edi
1193 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1194 ; CHECK-NEXT:  .LBB12_5: # %bb1
1195 ; CHECK-NEXT:    movl $1, %edi
1196 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1197 ; CHECK-NEXT:  .LBB12_7: # %bb3
1198 ; CHECK-NEXT:    movl $3, %edi
1199 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1200 ; CHECK-NEXT:  .LBB12_1: # %entry
1201 ; CHECK-NEXT:    cmpl $25, %edi
1202 ; CHECK-NEXT:    jne .LBB12_8
1203 ; CHECK-NEXT:  # %bb.2: # %bb4
1204 ; CHECK-NEXT:    movl $4, %edi
1205 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1206 ; CHECK-NEXT:  .LBB12_8: # %return
1207 ; CHECK-NEXT:    retq
1208 ;
1209 ; NOOPT-LABEL: optimal_jump_table3:
1210 ; NOOPT:       # %bb.0: # %entry
1211 ; NOOPT-NEXT:    pushq %rax
1212 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
1213 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
1214 ; NOOPT-NEXT:    subl $1, %edi
1215 ; NOOPT-NEXT:    je .LBB12_1
1216 ; NOOPT-NEXT:    jmp .LBB12_7
1217 ; NOOPT-NEXT:  .LBB12_7: # %entry
1218 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1219 ; NOOPT-NEXT:    subl $2, %eax
1220 ; NOOPT-NEXT:    je .LBB12_2
1221 ; NOOPT-NEXT:    jmp .LBB12_8
1222 ; NOOPT-NEXT:  .LBB12_8: # %entry
1223 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1224 ; NOOPT-NEXT:    subl $3, %eax
1225 ; NOOPT-NEXT:    je .LBB12_3
1226 ; NOOPT-NEXT:    jmp .LBB12_9
1227 ; NOOPT-NEXT:  .LBB12_9: # %entry
1228 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1229 ; NOOPT-NEXT:    subl $10, %eax
1230 ; NOOPT-NEXT:    je .LBB12_4
1231 ; NOOPT-NEXT:    jmp .LBB12_10
1232 ; NOOPT-NEXT:  .LBB12_10: # %entry
1233 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1234 ; NOOPT-NEXT:    subl $13, %eax
1235 ; NOOPT-NEXT:    je .LBB12_1
1236 ; NOOPT-NEXT:    jmp .LBB12_11
1237 ; NOOPT-NEXT:  .LBB12_11: # %entry
1238 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1239 ; NOOPT-NEXT:    subl $14, %eax
1240 ; NOOPT-NEXT:    je .LBB12_2
1241 ; NOOPT-NEXT:    jmp .LBB12_12
1242 ; NOOPT-NEXT:  .LBB12_12: # %entry
1243 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1244 ; NOOPT-NEXT:    subl $15, %eax
1245 ; NOOPT-NEXT:    je .LBB12_3
1246 ; NOOPT-NEXT:    jmp .LBB12_13
1247 ; NOOPT-NEXT:  .LBB12_13: # %entry
1248 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1249 ; NOOPT-NEXT:    subl $20, %eax
1250 ; NOOPT-NEXT:    je .LBB12_4
1251 ; NOOPT-NEXT:    jmp .LBB12_14
1252 ; NOOPT-NEXT:  .LBB12_14: # %entry
1253 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1254 ; NOOPT-NEXT:    subl $25, %eax
1255 ; NOOPT-NEXT:    je .LBB12_5
1256 ; NOOPT-NEXT:    jmp .LBB12_6
1257 ; NOOPT-NEXT:  .LBB12_1: # %bb0
1258 ; NOOPT-NEXT:    xorl %edi, %edi
1259 ; NOOPT-NEXT:    callq g@PLT
1260 ; NOOPT-NEXT:    jmp .LBB12_6
1261 ; NOOPT-NEXT:  .LBB12_2: # %bb1
1262 ; NOOPT-NEXT:    movl $1, %edi
1263 ; NOOPT-NEXT:    callq g@PLT
1264 ; NOOPT-NEXT:    jmp .LBB12_6
1265 ; NOOPT-NEXT:  .LBB12_3: # %bb2
1266 ; NOOPT-NEXT:    movl $2, %edi
1267 ; NOOPT-NEXT:    callq g@PLT
1268 ; NOOPT-NEXT:    jmp .LBB12_6
1269 ; NOOPT-NEXT:  .LBB12_4: # %bb3
1270 ; NOOPT-NEXT:    movl $3, %edi
1271 ; NOOPT-NEXT:    callq g@PLT
1272 ; NOOPT-NEXT:    jmp .LBB12_6
1273 ; NOOPT-NEXT:  .LBB12_5: # %bb4
1274 ; NOOPT-NEXT:    movl $4, %edi
1275 ; NOOPT-NEXT:    callq g@PLT
1276 ; NOOPT-NEXT:  .LBB12_6: # %return
1277 ; NOOPT-NEXT:    popq %rax
1278 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
1279 ; NOOPT-NEXT:    retq
1280 entry:
1281   switch i32 %x, label %return [
1282     i32 1,  label %bb0
1283     i32 2,  label %bb1
1284     i32 3,  label %bb2
1285     i32 10, label %bb3
1286     i32 13, label %bb0
1287     i32 14, label %bb1
1288     i32 15, label %bb2
1289     i32 20, label %bb3
1290     i32 25, label %bb4
1291   ]
1292 bb0: tail call void @g(i32 0) br label %return
1293 bb1: tail call void @g(i32 1) br label %return
1294 bb2: tail call void @g(i32 2) br label %return
1295 bb3: tail call void @g(i32 3) br label %return
1296 bb4: tail call void @g(i32 4) br label %return
1297 return: ret void
1298 }
1299
1300 %struct.S = type { ptr, i32 }
1301
1302 ; This will be lowered to a comparison with 4 and then bit tests. Make sure
1303 ; that the phi node in %header gets a value from the comparison block.
1304 define void @phi_node_trouble(ptr %s) {
1305 ; CHECK-LABEL: phi_node_trouble:
1306 ; CHECK:       # %bb.0: # %entry
1307 ; CHECK-NEXT:    .p2align 4, 0x90
1308 ; CHECK-NEXT:  .LBB13_1: # %header
1309 ; CHECK-NEXT:    # =>This Inner Loop Header: Depth=1
1310 ; CHECK-NEXT:    testq %rdi, %rdi
1311 ; CHECK-NEXT:    je .LBB13_5
1312 ; CHECK-NEXT:  # %bb.2: # %loop
1313 ; CHECK-NEXT:    # in Loop: Header=BB13_1 Depth=1
1314 ; CHECK-NEXT:    movq (%rdi), %rdi
1315 ; CHECK-NEXT:    movl 8(%rdi), %eax
1316 ; CHECK-NEXT:    cmpl $4, %eax
1317 ; CHECK-NEXT:    je .LBB13_1
1318 ; CHECK-NEXT:  # %bb.3: # %loop
1319 ; CHECK-NEXT:    addl $-25, %eax
1320 ; CHECK-NEXT:    cmpl $44, %eax
1321 ; CHECK-NEXT:    ja .LBB13_5
1322 ; CHECK-NEXT:  # %bb.4: # %loop
1323 ; CHECK-NEXT:    movabsq $17592186046465, %rcx # imm = 0x100000000801
1324 ; CHECK-NEXT:    btq %rax, %rcx
1325 ; CHECK-NEXT:  .LBB13_5: # %exit2
1326 ; CHECK-NEXT:    retq
1327 ;
1328 ; NOOPT-LABEL: phi_node_trouble:
1329 ; NOOPT:       # %bb.0: # %entry
1330 ; NOOPT-NEXT:    movq %rdi, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill
1331 ; NOOPT-NEXT:    jmp .LBB13_1
1332 ; NOOPT-NEXT:  .LBB13_1: # %header
1333 ; NOOPT-NEXT:    # =>This Inner Loop Header: Depth=1
1334 ; NOOPT-NEXT:    movq {{[-0-9]+}}(%r{{[sb]}}p), %rax # 8-byte Reload
1335 ; NOOPT-NEXT:    movq %rax, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill
1336 ; NOOPT-NEXT:    cmpq $0, %rax
1337 ; NOOPT-NEXT:    je .LBB13_3
1338 ; NOOPT-NEXT:  # %bb.2: # %loop
1339 ; NOOPT-NEXT:    # in Loop: Header=BB13_1 Depth=1
1340 ; NOOPT-NEXT:    movq {{[-0-9]+}}(%r{{[sb]}}p), %rax # 8-byte Reload
1341 ; NOOPT-NEXT:    movq (%rax), %rax
1342 ; NOOPT-NEXT:    movl 8(%rax), %ecx
1343 ; NOOPT-NEXT:    movl %ecx, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
1344 ; NOOPT-NEXT:    subl $4, %ecx
1345 ; NOOPT-NEXT:    movq %rax, {{[-0-9]+}}(%r{{[sb]}}p) # 8-byte Spill
1346 ; NOOPT-NEXT:    je .LBB13_1
1347 ; NOOPT-NEXT:    jmp .LBB13_5
1348 ; NOOPT-NEXT:  .LBB13_5: # %loop
1349 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1350 ; NOOPT-NEXT:    subl $25, %eax
1351 ; NOOPT-NEXT:    je .LBB13_4
1352 ; NOOPT-NEXT:    jmp .LBB13_6
1353 ; NOOPT-NEXT:  .LBB13_6: # %loop
1354 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1355 ; NOOPT-NEXT:    subl $36, %eax
1356 ; NOOPT-NEXT:    je .LBB13_4
1357 ; NOOPT-NEXT:    jmp .LBB13_7
1358 ; NOOPT-NEXT:  .LBB13_7: # %loop
1359 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1360 ; NOOPT-NEXT:    subl $69, %eax
1361 ; NOOPT-NEXT:    je .LBB13_4
1362 ; NOOPT-NEXT:    jmp .LBB13_3
1363 ; NOOPT-NEXT:  .LBB13_3: # %exit
1364 ; NOOPT-NEXT:    retq
1365 ; NOOPT-NEXT:  .LBB13_4: # %exit2
1366 ; NOOPT-NEXT:    retq
1367 entry:
1368   br label %header
1369 header:
1370   %ptr = phi ptr [ %s, %entry ], [ %next, %loop ]
1371   %bool = icmp eq ptr %ptr, null
1372   br i1 %bool, label %exit, label %loop
1373 loop:
1374   %next = load ptr, ptr %ptr
1375   %xptr = getelementptr inbounds %struct.S, ptr %next, i64 0, i32 1
1376   %x = load i32, ptr %xptr
1377   switch i32 %x, label %exit [
1378     i32 4, label %header
1379     i32 36, label %exit2
1380     i32 69, label %exit2
1381     i32 25, label %exit2
1382   ]
1383 exit:
1384   ret void
1385 exit2:
1386   ret void
1387 }
1388
1389
1390 ; Branch directly to the default.
1391 ; (In optimized builds the switch is removed earlier.)
1392 define void @default_only(i32 %x) {
1393 ; CHECK-LABEL: default_only:
1394 ; CHECK:       # %bb.0: # %entry
1395 ; CHECK-NEXT:    retq
1396 ;
1397 ; NOOPT-LABEL: default_only:
1398 ; NOOPT:       # %bb.0: # %entry
1399 ; NOOPT-NEXT:    jmp .LBB14_2
1400 ; NOOPT-NEXT:  .LBB14_1: # %return
1401 ; NOOPT-NEXT:    retq
1402 ; NOOPT-NEXT:  .LBB14_2: # %sw
1403 ; NOOPT-NEXT:    jmp .LBB14_1
1404 entry:
1405   br label %sw
1406 return:
1407   ret void
1408 sw:
1409   switch i32 %x, label %return [
1410   ]
1411 }
1412
1413
1414 ; Don't infloop on jump tables where the upper bound is the max value of the
1415 ; input type (in this case 127).
1416 define void @int_max_table_cluster(i8 %x) {
1417 ; CHECK-LABEL: int_max_table_cluster:
1418 ; CHECK:       # %bb.0: # %entry
1419 ; CHECK-NEXT:    cmpb $-9, %dil
1420 ; CHECK-NEXT:    ja .LBB15_4
1421 ; CHECK-NEXT:  # %bb.1: # %entry
1422 ; CHECK-NEXT:    movzbl %dil, %eax
1423 ; CHECK-NEXT:    jmpq *.LJTI15_0(,%rax,8)
1424 ; CHECK-NEXT:  .LBB15_2: # %bb0
1425 ; CHECK-NEXT:    xorl %edi, %edi
1426 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1427 ; CHECK-NEXT:  .LBB15_3: # %bb3
1428 ; CHECK-NEXT:    movl $1, %edi
1429 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1430 ; CHECK-NEXT:  .LBB15_4: # %return
1431 ; CHECK-NEXT:    retq
1432 ;
1433 ; NOOPT-LABEL: int_max_table_cluster:
1434 ; NOOPT:       # %bb.0: # %entry
1435 ; NOOPT-NEXT:    pushq %rax
1436 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
1437 ; NOOPT-NEXT:    movb %dil, %al
1438 ; NOOPT-NEXT:    addb $64, %al
1439 ; NOOPT-NEXT:    movzbl %al, %ecx
1440 ; NOOPT-NEXT:    # kill: def $rcx killed $ecx
1441 ; NOOPT-NEXT:    movq %rcx, (%rsp) # 8-byte Spill
1442 ; NOOPT-NEXT:    subb $-65, %al
1443 ; NOOPT-NEXT:    ja .LBB15_5
1444 ; NOOPT-NEXT:  # %bb.6: # %entry
1445 ; NOOPT-NEXT:    movq (%rsp), %rax # 8-byte Reload
1446 ; NOOPT-NEXT:    movq .LJTI15_0(,%rax,8), %rax
1447 ; NOOPT-NEXT:    jmpq *%rax
1448 ; NOOPT-NEXT:  .LBB15_1: # %bb0
1449 ; NOOPT-NEXT:    xorl %edi, %edi
1450 ; NOOPT-NEXT:    callq g@PLT
1451 ; NOOPT-NEXT:    jmp .LBB15_5
1452 ; NOOPT-NEXT:  .LBB15_2: # %bb1
1453 ; NOOPT-NEXT:    movl $1, %edi
1454 ; NOOPT-NEXT:    callq g@PLT
1455 ; NOOPT-NEXT:    jmp .LBB15_5
1456 ; NOOPT-NEXT:  .LBB15_3: # %bb2
1457 ; NOOPT-NEXT:    movl $1, %edi
1458 ; NOOPT-NEXT:    callq g@PLT
1459 ; NOOPT-NEXT:    jmp .LBB15_5
1460 ; NOOPT-NEXT:  .LBB15_4: # %bb3
1461 ; NOOPT-NEXT:    movl $1, %edi
1462 ; NOOPT-NEXT:    callq g@PLT
1463 ; NOOPT-NEXT:  .LBB15_5: # %return
1464 ; NOOPT-NEXT:    popq %rax
1465 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
1466 ; NOOPT-NEXT:    retq
1467 entry:
1468   switch i8 %x, label %return [
1469     i8 0, label %bb0 i8 1, label %bb0 i8 2, label %bb0 i8 3, label %bb0
1470     i8 4, label %bb0 i8 5, label %bb0 i8 6, label %bb0 i8 7, label %bb0
1471     i8 8, label %bb0 i8 9, label %bb0 i8 10, label %bb0 i8 11, label %bb0
1472     i8 12, label %bb0 i8 13, label %bb0 i8 14, label %bb0 i8 15, label %bb0
1473     i8 16, label %bb0 i8 17, label %bb0 i8 18, label %bb0 i8 19, label %bb0
1474     i8 20, label %bb0 i8 21, label %bb0 i8 22, label %bb0 i8 23, label %bb0
1475     i8 24, label %bb0 i8 25, label %bb0 i8 26, label %bb0 i8 27, label %bb0
1476     i8 28, label %bb0 i8 29, label %bb0 i8 30, label %bb0 i8 31, label %bb0
1477     i8 32, label %bb0 i8 33, label %bb0 i8 34, label %bb0 i8 35, label %bb0
1478     i8 36, label %bb0 i8 37, label %bb0 i8 38, label %bb0 i8 39, label %bb0
1479     i8 40, label %bb0 i8 41, label %bb0 i8 42, label %bb0 i8 43, label %bb0
1480     i8 44, label %bb0 i8 45, label %bb0 i8 46, label %bb0 i8 47, label %bb0
1481     i8 48, label %bb0 i8 49, label %bb0 i8 50, label %bb0 i8 51, label %bb0
1482     i8 52, label %bb0 i8 53, label %bb0 i8 54, label %bb0 i8 55, label %bb0
1483     i8 56, label %bb0 i8 57, label %bb0 i8 58, label %bb0 i8 59, label %bb0
1484     i8 60, label %bb0 i8 61, label %bb0 i8 62, label %bb0 i8 63, label %bb0
1485     i8 64, label %bb0 i8 65, label %bb0 i8 66, label %bb0 i8 67, label %bb0
1486     i8 68, label %bb0 i8 69, label %bb0 i8 70, label %bb0 i8 71, label %bb0
1487     i8 72, label %bb0 i8 73, label %bb0 i8 74, label %bb0 i8 75, label %bb0
1488     i8 76, label %bb0 i8 77, label %bb0 i8 78, label %bb0 i8 79, label %bb0
1489     i8 80, label %bb0 i8 81, label %bb0 i8 82, label %bb0 i8 83, label %bb0
1490     i8 84, label %bb0 i8 85, label %bb0 i8 86, label %bb0 i8 87, label %bb0
1491     i8 88, label %bb0 i8 89, label %bb0 i8 90, label %bb0 i8 91, label %bb0
1492     i8 92, label %bb0 i8 93, label %bb0 i8 94, label %bb0 i8 95, label %bb0
1493     i8 96, label %bb0 i8 97, label %bb0 i8 98, label %bb0 i8 99, label %bb0
1494     i8 100, label %bb0 i8 101, label %bb0 i8 102, label %bb0 i8 103, label %bb0
1495     i8 104, label %bb0 i8 105, label %bb0 i8 106, label %bb0 i8 107, label %bb0
1496     i8 108, label %bb0 i8 109, label %bb0 i8 110, label %bb0 i8 111, label %bb0
1497     i8 112, label %bb0 i8 113, label %bb0 i8 114, label %bb0 i8 115, label %bb0
1498     i8 116, label %bb0 i8 117, label %bb0 i8 118, label %bb0 i8 119, label %bb0
1499     i8 120, label %bb0 i8 121, label %bb0 i8 122, label %bb0 i8 123, label %bb0
1500     i8 124, label %bb0 i8 125, label %bb0 i8 126, label %bb0 i8 127, label %bb0
1501     i8 -64, label %bb1 i8 -63, label %bb1 i8 -62, label %bb1 i8 -61, label %bb1
1502     i8 -60, label %bb1 i8 -59, label %bb1 i8 -58, label %bb1 i8 -57, label %bb1
1503     i8 -56, label %bb1 i8 -55, label %bb1 i8 -54, label %bb1 i8 -53, label %bb1
1504     i8 -52, label %bb1 i8 -51, label %bb1 i8 -50, label %bb1 i8 -49, label %bb1
1505     i8 -48, label %bb1 i8 -47, label %bb1 i8 -46, label %bb1 i8 -45, label %bb1
1506     i8 -44, label %bb1 i8 -43, label %bb1 i8 -42, label %bb1 i8 -41, label %bb1
1507     i8 -40, label %bb1 i8 -39, label %bb1 i8 -38, label %bb1 i8 -37, label %bb1
1508     i8 -36, label %bb1 i8 -35, label %bb1 i8 -34, label %bb1 i8 -33, label %bb1
1509     i8 -32, label %bb2 i8 -31, label %bb2 i8 -30, label %bb2 i8 -29, label %bb2
1510     i8 -28, label %bb2 i8 -27, label %bb2 i8 -26, label %bb2 i8 -25, label %bb2
1511     i8 -24, label %bb2 i8 -23, label %bb2 i8 -22, label %bb2 i8 -21, label %bb2
1512     i8 -20, label %bb2 i8 -19, label %bb2 i8 -18, label %bb2 i8 -17, label %bb2
1513     i8 -16, label %bb3 i8 -15, label %bb3 i8 -14, label %bb3 i8 -13, label %bb3
1514     i8 -12, label %bb3 i8 -11, label %bb3 i8 -10, label %bb3 i8 -9, label %bb3
1515   ]
1516 bb0: tail call void @g(i32 0) br label %return
1517 bb1: tail call void @g(i32 1) br label %return
1518 bb2: tail call void @g(i32 1) br label %return
1519 bb3: tail call void @g(i32 1) br label %return
1520 return: ret void
1521 }
1522
1523
1524 ; Cases 1,4,7 have a very large branch weight (which shouldn't overflow), so
1525 ; their bit test should come first. 0,3,6 and 2,5,8,9 both have a weight of 20,
1526 ; but the latter set has more cases, so should be tested for earlier. The bit
1527 ; test on 0,3,6 is unnecessary as all cases cover the range [0, 9]. The range
1528 ; check guarantees that cases other than 1,4,7 and 2,5,8,9 must be in 0,3,6.
1529 define void @bt_order_by_weight(i32 %x) {
1530 ; CHECK-LABEL: bt_order_by_weight:
1531 ; CHECK:       # %bb.0: # %entry
1532 ; CHECK-NEXT:    cmpl $9, %edi
1533 ; CHECK-NEXT:    ja .LBB16_6
1534 ; CHECK-NEXT:  # %bb.1: # %entry
1535 ; CHECK-NEXT:    movl $146, %eax
1536 ; CHECK-NEXT:    btl %edi, %eax
1537 ; CHECK-NEXT:    jae .LBB16_2
1538 ; CHECK-NEXT:  # %bb.4: # %bb1
1539 ; CHECK-NEXT:    movl $1, %edi
1540 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1541 ; CHECK-NEXT:  .LBB16_2: # %entry
1542 ; CHECK-NEXT:    movl $804, %eax # imm = 0x324
1543 ; CHECK-NEXT:    btl %edi, %eax
1544 ; CHECK-NEXT:    jae .LBB16_3
1545 ; CHECK-NEXT:  # %bb.5: # %bb2
1546 ; CHECK-NEXT:    movl $2, %edi
1547 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1548 ; CHECK-NEXT:  .LBB16_3: # %bb0
1549 ; CHECK-NEXT:    xorl %edi, %edi
1550 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1551 ; CHECK-NEXT:  .LBB16_6: # %return
1552 ; CHECK-NEXT:    retq
1553 ;
1554 ; NOOPT-LABEL: bt_order_by_weight:
1555 ; NOOPT:       # %bb.0: # %entry
1556 ; NOOPT-NEXT:    pushq %rax
1557 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
1558 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
1559 ; NOOPT-NEXT:    testl %edi, %edi
1560 ; NOOPT-NEXT:    je .LBB16_1
1561 ; NOOPT-NEXT:    jmp .LBB16_5
1562 ; NOOPT-NEXT:  .LBB16_5: # %entry
1563 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1564 ; NOOPT-NEXT:    subl $1, %eax
1565 ; NOOPT-NEXT:    je .LBB16_2
1566 ; NOOPT-NEXT:    jmp .LBB16_6
1567 ; NOOPT-NEXT:  .LBB16_6: # %entry
1568 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1569 ; NOOPT-NEXT:    subl $2, %eax
1570 ; NOOPT-NEXT:    je .LBB16_3
1571 ; NOOPT-NEXT:    jmp .LBB16_7
1572 ; NOOPT-NEXT:  .LBB16_7: # %entry
1573 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1574 ; NOOPT-NEXT:    subl $3, %eax
1575 ; NOOPT-NEXT:    je .LBB16_1
1576 ; NOOPT-NEXT:    jmp .LBB16_8
1577 ; NOOPT-NEXT:  .LBB16_8: # %entry
1578 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1579 ; NOOPT-NEXT:    subl $4, %eax
1580 ; NOOPT-NEXT:    je .LBB16_2
1581 ; NOOPT-NEXT:    jmp .LBB16_9
1582 ; NOOPT-NEXT:  .LBB16_9: # %entry
1583 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1584 ; NOOPT-NEXT:    subl $5, %eax
1585 ; NOOPT-NEXT:    je .LBB16_3
1586 ; NOOPT-NEXT:    jmp .LBB16_10
1587 ; NOOPT-NEXT:  .LBB16_10: # %entry
1588 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1589 ; NOOPT-NEXT:    subl $6, %eax
1590 ; NOOPT-NEXT:    je .LBB16_1
1591 ; NOOPT-NEXT:    jmp .LBB16_11
1592 ; NOOPT-NEXT:  .LBB16_11: # %entry
1593 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1594 ; NOOPT-NEXT:    subl $7, %eax
1595 ; NOOPT-NEXT:    je .LBB16_2
1596 ; NOOPT-NEXT:    jmp .LBB16_12
1597 ; NOOPT-NEXT:  .LBB16_12: # %entry
1598 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1599 ; NOOPT-NEXT:    addl $-8, %eax
1600 ; NOOPT-NEXT:    subl $2, %eax
1601 ; NOOPT-NEXT:    jb .LBB16_3
1602 ; NOOPT-NEXT:    jmp .LBB16_4
1603 ; NOOPT-NEXT:  .LBB16_1: # %bb0
1604 ; NOOPT-NEXT:    xorl %edi, %edi
1605 ; NOOPT-NEXT:    callq g@PLT
1606 ; NOOPT-NEXT:    jmp .LBB16_4
1607 ; NOOPT-NEXT:  .LBB16_2: # %bb1
1608 ; NOOPT-NEXT:    movl $1, %edi
1609 ; NOOPT-NEXT:    callq g@PLT
1610 ; NOOPT-NEXT:    jmp .LBB16_4
1611 ; NOOPT-NEXT:  .LBB16_3: # %bb2
1612 ; NOOPT-NEXT:    movl $2, %edi
1613 ; NOOPT-NEXT:    callq g@PLT
1614 ; NOOPT-NEXT:  .LBB16_4: # %return
1615 ; NOOPT-NEXT:    popq %rax
1616 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
1617 ; NOOPT-NEXT:    retq
1618 entry:
1619   switch i32 %x, label %return [
1620     i32 0, label %bb0
1621     i32 3, label %bb0
1622     i32 6, label %bb0
1623     i32 1, label %bb1
1624     i32 4, label %bb1
1625     i32 7, label %bb1
1626     i32 2, label %bb2
1627     i32 5, label %bb2
1628     i32 8, label %bb2
1629     i32 9, label %bb2
1630   ], !prof !1
1631 bb0: tail call void @g(i32 0) br label %return
1632 bb1: tail call void @g(i32 1) br label %return
1633 bb2: tail call void @g(i32 2) br label %return
1634 return: ret void
1635 }
1636
1637 !1 = !{!"branch_weights",
1638        ; Default:
1639        i32 1,
1640        ; Cases 0,3,6:
1641        i32 0, i32 0, i32 20,
1642        ; Cases 1,4,7:
1643        i32 4294967295, i32 2, i32 4294967295,
1644        ; Cases 2,5,8,9:
1645        i32 0, i32 0, i32 0, i32 20}
1646
1647
1648 ; Case 200 has the highest weight and should come first. 100 and 300 have the
1649 ; same weight, but 300 goes to the 'next' block, so should be last.
1650 define void @order_by_weight_and_fallthrough(i32 %x) {
1651 ; CHECK-LABEL: order_by_weight_and_fallthrough:
1652 ; CHECK:       # %bb.0: # %entry
1653 ; CHECK-NEXT:    cmpl $200, %edi
1654 ; CHECK-NEXT:    jne .LBB17_1
1655 ; CHECK-NEXT:  .LBB17_3: # %bb0
1656 ; CHECK-NEXT:    xorl %edi, %edi
1657 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1658 ; CHECK-NEXT:  .LBB17_1: # %entry
1659 ; CHECK-NEXT:    cmpl $100, %edi
1660 ; CHECK-NEXT:    je .LBB17_4
1661 ; CHECK-NEXT:  # %bb.2: # %entry
1662 ; CHECK-NEXT:    cmpl $300, %edi # imm = 0x12C
1663 ; CHECK-NEXT:    je .LBB17_3
1664 ; CHECK-NEXT:  # %bb.5: # %return
1665 ; CHECK-NEXT:    retq
1666 ; CHECK-NEXT:  .LBB17_4: # %bb1
1667 ; CHECK-NEXT:    movl $1, %edi
1668 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1669 ;
1670 ; NOOPT-LABEL: order_by_weight_and_fallthrough:
1671 ; NOOPT:       # %bb.0: # %entry
1672 ; NOOPT-NEXT:    pushq %rax
1673 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
1674 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
1675 ; NOOPT-NEXT:    subl $100, %edi
1676 ; NOOPT-NEXT:    je .LBB17_2
1677 ; NOOPT-NEXT:    jmp .LBB17_4
1678 ; NOOPT-NEXT:  .LBB17_4: # %entry
1679 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1680 ; NOOPT-NEXT:    subl $200, %eax
1681 ; NOOPT-NEXT:    je .LBB17_1
1682 ; NOOPT-NEXT:    jmp .LBB17_5
1683 ; NOOPT-NEXT:  .LBB17_5: # %entry
1684 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1685 ; NOOPT-NEXT:    subl $300, %eax # imm = 0x12C
1686 ; NOOPT-NEXT:    jne .LBB17_3
1687 ; NOOPT-NEXT:    jmp .LBB17_1
1688 ; NOOPT-NEXT:  .LBB17_1: # %bb0
1689 ; NOOPT-NEXT:    xorl %edi, %edi
1690 ; NOOPT-NEXT:    callq g@PLT
1691 ; NOOPT-NEXT:    jmp .LBB17_3
1692 ; NOOPT-NEXT:  .LBB17_2: # %bb1
1693 ; NOOPT-NEXT:    movl $1, %edi
1694 ; NOOPT-NEXT:    callq g@PLT
1695 ; NOOPT-NEXT:  .LBB17_3: # %return
1696 ; NOOPT-NEXT:    popq %rax
1697 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
1698 ; NOOPT-NEXT:    retq
1699 entry:
1700   switch i32 %x, label %return [
1701     i32 100, label %bb1
1702     i32 200, label %bb0
1703     i32 300, label %bb0
1704   ], !prof !2
1705 bb0: tail call void @g(i32 0) br label %return
1706 bb1: tail call void @g(i32 1) br label %return
1707 return: ret void
1708 }
1709
1710 !2 = !{!"branch_weights",
1711        ; Default:
1712        i32 1,
1713        ; Case 100:
1714        i32 10,
1715        ; Case 200:
1716        i32 1000,
1717        ; Case 300:
1718        i32 10}
1719
1720
1721 ; Make sure to pick a pivot in the middle also with zero-weight cases.
1722 define void @zero_weight_tree(i32 %x) {
1723 ; CHECK-LABEL: zero_weight_tree:
1724 ; CHECK:       # %bb.0: # %entry
1725 ; CHECK-NEXT:    cmpl $29, %edi
1726 ; CHECK-NEXT:    jg .LBB18_5
1727 ; CHECK-NEXT:  # %bb.1: # %entry
1728 ; CHECK-NEXT:    testl %edi, %edi
1729 ; CHECK-NEXT:    jne .LBB18_2
1730 ; CHECK-NEXT:  # %bb.9: # %bb0
1731 ; CHECK-NEXT:    xorl %edi, %edi
1732 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1733 ; CHECK-NEXT:  .LBB18_5: # %entry
1734 ; CHECK-NEXT:    cmpl $50, %edi
1735 ; CHECK-NEXT:    jne .LBB18_6
1736 ; CHECK-NEXT:  # %bb.12: # %bb5
1737 ; CHECK-NEXT:    movl $5, %edi
1738 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1739 ; CHECK-NEXT:  .LBB18_2: # %entry
1740 ; CHECK-NEXT:    cmpl $10, %edi
1741 ; CHECK-NEXT:    je .LBB18_10
1742 ; CHECK-NEXT:  # %bb.3: # %entry
1743 ; CHECK-NEXT:    cmpl $20, %edi
1744 ; CHECK-NEXT:    jne .LBB18_13
1745 ; CHECK-NEXT:  # %bb.4: # %bb2
1746 ; CHECK-NEXT:    movl $2, %edi
1747 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1748 ; CHECK-NEXT:  .LBB18_6: # %entry
1749 ; CHECK-NEXT:    cmpl $30, %edi
1750 ; CHECK-NEXT:    je .LBB18_11
1751 ; CHECK-NEXT:  # %bb.7: # %entry
1752 ; CHECK-NEXT:    cmpl $40, %edi
1753 ; CHECK-NEXT:    je .LBB18_8
1754 ; CHECK-NEXT:  .LBB18_13: # %return
1755 ; CHECK-NEXT:    retq
1756 ; CHECK-NEXT:  .LBB18_10: # %bb1
1757 ; CHECK-NEXT:    movl $1, %edi
1758 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1759 ; CHECK-NEXT:  .LBB18_11: # %bb3
1760 ; CHECK-NEXT:    movl $3, %edi
1761 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1762 ; CHECK-NEXT:  .LBB18_8: # %bb4
1763 ; CHECK-NEXT:    movl $4, %edi
1764 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1765 ;
1766 ; NOOPT-LABEL: zero_weight_tree:
1767 ; NOOPT:       # %bb.0: # %entry
1768 ; NOOPT-NEXT:    pushq %rax
1769 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
1770 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
1771 ; NOOPT-NEXT:    testl %edi, %edi
1772 ; NOOPT-NEXT:    je .LBB18_1
1773 ; NOOPT-NEXT:    jmp .LBB18_8
1774 ; NOOPT-NEXT:  .LBB18_8: # %entry
1775 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1776 ; NOOPT-NEXT:    subl $10, %eax
1777 ; NOOPT-NEXT:    je .LBB18_2
1778 ; NOOPT-NEXT:    jmp .LBB18_9
1779 ; NOOPT-NEXT:  .LBB18_9: # %entry
1780 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1781 ; NOOPT-NEXT:    subl $20, %eax
1782 ; NOOPT-NEXT:    je .LBB18_3
1783 ; NOOPT-NEXT:    jmp .LBB18_10
1784 ; NOOPT-NEXT:  .LBB18_10: # %entry
1785 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1786 ; NOOPT-NEXT:    subl $30, %eax
1787 ; NOOPT-NEXT:    je .LBB18_4
1788 ; NOOPT-NEXT:    jmp .LBB18_11
1789 ; NOOPT-NEXT:  .LBB18_11: # %entry
1790 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1791 ; NOOPT-NEXT:    subl $40, %eax
1792 ; NOOPT-NEXT:    je .LBB18_5
1793 ; NOOPT-NEXT:    jmp .LBB18_12
1794 ; NOOPT-NEXT:  .LBB18_12: # %entry
1795 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1796 ; NOOPT-NEXT:    subl $50, %eax
1797 ; NOOPT-NEXT:    je .LBB18_6
1798 ; NOOPT-NEXT:    jmp .LBB18_7
1799 ; NOOPT-NEXT:  .LBB18_1: # %bb0
1800 ; NOOPT-NEXT:    xorl %edi, %edi
1801 ; NOOPT-NEXT:    callq g@PLT
1802 ; NOOPT-NEXT:    jmp .LBB18_7
1803 ; NOOPT-NEXT:  .LBB18_2: # %bb1
1804 ; NOOPT-NEXT:    movl $1, %edi
1805 ; NOOPT-NEXT:    callq g@PLT
1806 ; NOOPT-NEXT:    jmp .LBB18_7
1807 ; NOOPT-NEXT:  .LBB18_3: # %bb2
1808 ; NOOPT-NEXT:    movl $2, %edi
1809 ; NOOPT-NEXT:    callq g@PLT
1810 ; NOOPT-NEXT:    jmp .LBB18_7
1811 ; NOOPT-NEXT:  .LBB18_4: # %bb3
1812 ; NOOPT-NEXT:    movl $3, %edi
1813 ; NOOPT-NEXT:    callq g@PLT
1814 ; NOOPT-NEXT:    jmp .LBB18_7
1815 ; NOOPT-NEXT:  .LBB18_5: # %bb4
1816 ; NOOPT-NEXT:    movl $4, %edi
1817 ; NOOPT-NEXT:    callq g@PLT
1818 ; NOOPT-NEXT:    jmp .LBB18_7
1819 ; NOOPT-NEXT:  .LBB18_6: # %bb5
1820 ; NOOPT-NEXT:    movl $5, %edi
1821 ; NOOPT-NEXT:    callq g@PLT
1822 ; NOOPT-NEXT:  .LBB18_7: # %return
1823 ; NOOPT-NEXT:    popq %rax
1824 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
1825 ; NOOPT-NEXT:    retq
1826 entry:
1827   switch i32 %x, label %return [
1828     i32 0,  label %bb0
1829     i32 10, label %bb1
1830     i32 20, label %bb2
1831     i32 30, label %bb3
1832     i32 40, label %bb4
1833     i32 50, label %bb5
1834   ], !prof !3
1835 bb0: tail call void @g(i32 0) br label %return
1836 bb1: tail call void @g(i32 1) br label %return
1837 bb2: tail call void @g(i32 2) br label %return
1838 bb3: tail call void @g(i32 3) br label %return
1839 bb4: tail call void @g(i32 4) br label %return
1840 bb5: tail call void @g(i32 5) br label %return
1841 return: ret void
1842 }
1843
1844 !3 = !{!"branch_weights", i32 1, i32 10, i32 0, i32 0, i32 0, i32 0, i32 10}
1845
1846
1847 ; Without branch probabilities, the pivot would be 40, since that would yield
1848 ; equal-sized sub-trees. When taking weights into account, case 70 becomes the
1849 ; pivot. Since there is room for 3 cases in a leaf, cases 50 and 60 are also
1850 ; included in the right-hand side because that doesn't reduce their rank.
1851 define void @left_leaning_weight_balanced_tree(i32 %x) {
1852 ; CHECK-LABEL: left_leaning_weight_balanced_tree:
1853 ; CHECK:       # %bb.0: # %entry
1854 ; CHECK-NEXT:    cmpl $49, %edi
1855 ; CHECK-NEXT:    jle .LBB19_1
1856 ; CHECK-NEXT:  # %bb.11: # %entry
1857 ; CHECK-NEXT:    cmpl $70, %edi
1858 ; CHECK-NEXT:    jne .LBB19_12
1859 ; CHECK-NEXT:  .LBB19_14: # %bb6
1860 ; CHECK-NEXT:    movl $6, %edi
1861 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1862 ; CHECK-NEXT:  .LBB19_1: # %entry
1863 ; CHECK-NEXT:    cmpl $9, %edi
1864 ; CHECK-NEXT:    jg .LBB19_4
1865 ; CHECK-NEXT:  # %bb.2: # %entry
1866 ; CHECK-NEXT:    testl %edi, %edi
1867 ; CHECK-NEXT:    jne .LBB19_18
1868 ; CHECK-NEXT:  # %bb.3: # %bb0
1869 ; CHECK-NEXT:    xorl %edi, %edi
1870 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1871 ; CHECK-NEXT:  .LBB19_4: # %entry
1872 ; CHECK-NEXT:    cmpl $29, %edi
1873 ; CHECK-NEXT:    jg .LBB19_8
1874 ; CHECK-NEXT:  # %bb.5: # %entry
1875 ; CHECK-NEXT:    cmpl $10, %edi
1876 ; CHECK-NEXT:    je .LBB19_15
1877 ; CHECK-NEXT:  # %bb.6: # %entry
1878 ; CHECK-NEXT:    cmpl $20, %edi
1879 ; CHECK-NEXT:    jne .LBB19_18
1880 ; CHECK-NEXT:  # %bb.7: # %bb2
1881 ; CHECK-NEXT:    movl $2, %edi
1882 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1883 ; CHECK-NEXT:  .LBB19_12: # %entry
1884 ; CHECK-NEXT:    cmpl $50, %edi
1885 ; CHECK-NEXT:    je .LBB19_17
1886 ; CHECK-NEXT:  # %bb.13: # %entry
1887 ; CHECK-NEXT:    cmpl $60, %edi
1888 ; CHECK-NEXT:    je .LBB19_14
1889 ; CHECK-NEXT:    jmp .LBB19_18
1890 ; CHECK-NEXT:  .LBB19_8: # %entry
1891 ; CHECK-NEXT:    cmpl $30, %edi
1892 ; CHECK-NEXT:    je .LBB19_16
1893 ; CHECK-NEXT:  # %bb.9: # %entry
1894 ; CHECK-NEXT:    cmpl $40, %edi
1895 ; CHECK-NEXT:    jne .LBB19_18
1896 ; CHECK-NEXT:  # %bb.10: # %bb4
1897 ; CHECK-NEXT:    movl $4, %edi
1898 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1899 ; CHECK-NEXT:  .LBB19_15: # %bb1
1900 ; CHECK-NEXT:    movl $1, %edi
1901 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1902 ; CHECK-NEXT:  .LBB19_16: # %bb3
1903 ; CHECK-NEXT:    movl $3, %edi
1904 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1905 ; CHECK-NEXT:  .LBB19_18: # %return
1906 ; CHECK-NEXT:    retq
1907 ; CHECK-NEXT:  .LBB19_17: # %bb5
1908 ; CHECK-NEXT:    movl $5, %edi
1909 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
1910 ;
1911 ; NOOPT-LABEL: left_leaning_weight_balanced_tree:
1912 ; NOOPT:       # %bb.0: # %entry
1913 ; NOOPT-NEXT:    pushq %rax
1914 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
1915 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
1916 ; NOOPT-NEXT:    testl %edi, %edi
1917 ; NOOPT-NEXT:    je .LBB19_1
1918 ; NOOPT-NEXT:    jmp .LBB19_9
1919 ; NOOPT-NEXT:  .LBB19_9: # %entry
1920 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1921 ; NOOPT-NEXT:    subl $10, %eax
1922 ; NOOPT-NEXT:    je .LBB19_2
1923 ; NOOPT-NEXT:    jmp .LBB19_10
1924 ; NOOPT-NEXT:  .LBB19_10: # %entry
1925 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1926 ; NOOPT-NEXT:    subl $20, %eax
1927 ; NOOPT-NEXT:    je .LBB19_3
1928 ; NOOPT-NEXT:    jmp .LBB19_11
1929 ; NOOPT-NEXT:  .LBB19_11: # %entry
1930 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1931 ; NOOPT-NEXT:    subl $30, %eax
1932 ; NOOPT-NEXT:    je .LBB19_4
1933 ; NOOPT-NEXT:    jmp .LBB19_12
1934 ; NOOPT-NEXT:  .LBB19_12: # %entry
1935 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1936 ; NOOPT-NEXT:    subl $40, %eax
1937 ; NOOPT-NEXT:    je .LBB19_5
1938 ; NOOPT-NEXT:    jmp .LBB19_13
1939 ; NOOPT-NEXT:  .LBB19_13: # %entry
1940 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1941 ; NOOPT-NEXT:    subl $50, %eax
1942 ; NOOPT-NEXT:    je .LBB19_6
1943 ; NOOPT-NEXT:    jmp .LBB19_14
1944 ; NOOPT-NEXT:  .LBB19_14: # %entry
1945 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1946 ; NOOPT-NEXT:    subl $60, %eax
1947 ; NOOPT-NEXT:    je .LBB19_7
1948 ; NOOPT-NEXT:    jmp .LBB19_15
1949 ; NOOPT-NEXT:  .LBB19_15: # %entry
1950 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
1951 ; NOOPT-NEXT:    subl $70, %eax
1952 ; NOOPT-NEXT:    je .LBB19_7
1953 ; NOOPT-NEXT:    jmp .LBB19_8
1954 ; NOOPT-NEXT:  .LBB19_1: # %bb0
1955 ; NOOPT-NEXT:    xorl %edi, %edi
1956 ; NOOPT-NEXT:    callq g@PLT
1957 ; NOOPT-NEXT:    jmp .LBB19_8
1958 ; NOOPT-NEXT:  .LBB19_2: # %bb1
1959 ; NOOPT-NEXT:    movl $1, %edi
1960 ; NOOPT-NEXT:    callq g@PLT
1961 ; NOOPT-NEXT:    jmp .LBB19_8
1962 ; NOOPT-NEXT:  .LBB19_3: # %bb2
1963 ; NOOPT-NEXT:    movl $2, %edi
1964 ; NOOPT-NEXT:    callq g@PLT
1965 ; NOOPT-NEXT:    jmp .LBB19_8
1966 ; NOOPT-NEXT:  .LBB19_4: # %bb3
1967 ; NOOPT-NEXT:    movl $3, %edi
1968 ; NOOPT-NEXT:    callq g@PLT
1969 ; NOOPT-NEXT:    jmp .LBB19_8
1970 ; NOOPT-NEXT:  .LBB19_5: # %bb4
1971 ; NOOPT-NEXT:    movl $4, %edi
1972 ; NOOPT-NEXT:    callq g@PLT
1973 ; NOOPT-NEXT:    jmp .LBB19_8
1974 ; NOOPT-NEXT:  .LBB19_6: # %bb5
1975 ; NOOPT-NEXT:    movl $5, %edi
1976 ; NOOPT-NEXT:    callq g@PLT
1977 ; NOOPT-NEXT:    jmp .LBB19_8
1978 ; NOOPT-NEXT:  .LBB19_7: # %bb6
1979 ; NOOPT-NEXT:    movl $6, %edi
1980 ; NOOPT-NEXT:    callq g@PLT
1981 ; NOOPT-NEXT:  .LBB19_8: # %return
1982 ; NOOPT-NEXT:    popq %rax
1983 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
1984 ; NOOPT-NEXT:    retq
1985 entry:
1986   switch i32 %x, label %return [
1987     i32 0,  label %bb0
1988     i32 10, label %bb1
1989     i32 20, label %bb2
1990     i32 30, label %bb3
1991     i32 40, label %bb4
1992     i32 50, label %bb5
1993     i32 60, label %bb6
1994     i32 70, label %bb6
1995   ], !prof !4
1996 bb0: tail call void @g(i32 0) br label %return
1997 bb1: tail call void @g(i32 1) br label %return
1998 bb2: tail call void @g(i32 2) br label %return
1999 bb3: tail call void @g(i32 3) br label %return
2000 bb4: tail call void @g(i32 4) br label %return
2001 bb5: tail call void @g(i32 5) br label %return
2002 bb6: tail call void @g(i32 6) br label %return
2003 bb7: tail call void @g(i32 7) br label %return
2004 return: ret void
2005 }
2006
2007 !4 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1000}
2008
2009
2010 ; Same as the previous test, except case 50 has higher rank to the left than it
2011 ; would have on the right. Case 60 would have the same rank on both sides, so is
2012 ; moved into the leaf.
2013 define void @left_leaning_weight_balanced_tree2(i32 %x) {
2014 ; CHECK-LABEL: left_leaning_weight_balanced_tree2:
2015 ; CHECK:       # %bb.0: # %entry
2016 ; CHECK-NEXT:    cmpl $59, %edi
2017 ; CHECK-NEXT:    jle .LBB20_1
2018 ; CHECK-NEXT:  # %bb.10: # %entry
2019 ; CHECK-NEXT:    cmpl $70, %edi
2020 ; CHECK-NEXT:    jne .LBB20_11
2021 ; CHECK-NEXT:  .LBB20_12: # %bb6
2022 ; CHECK-NEXT:    movl $6, %edi
2023 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2024 ; CHECK-NEXT:  .LBB20_1: # %entry
2025 ; CHECK-NEXT:    cmpl $29, %edi
2026 ; CHECK-NEXT:    jle .LBB20_2
2027 ; CHECK-NEXT:  # %bb.6: # %entry
2028 ; CHECK-NEXT:    cmpl $50, %edi
2029 ; CHECK-NEXT:    jne .LBB20_7
2030 ; CHECK-NEXT:  # %bb.16: # %bb5
2031 ; CHECK-NEXT:    movl $5, %edi
2032 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2033 ; CHECK-NEXT:  .LBB20_11: # %entry
2034 ; CHECK-NEXT:    cmpl $60, %edi
2035 ; CHECK-NEXT:    je .LBB20_12
2036 ; CHECK-NEXT:    jmp .LBB20_17
2037 ; CHECK-NEXT:  .LBB20_2: # %entry
2038 ; CHECK-NEXT:    testl %edi, %edi
2039 ; CHECK-NEXT:    jne .LBB20_3
2040 ; CHECK-NEXT:  # %bb.13: # %bb0
2041 ; CHECK-NEXT:    xorl %edi, %edi
2042 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2043 ; CHECK-NEXT:  .LBB20_3: # %entry
2044 ; CHECK-NEXT:    cmpl $10, %edi
2045 ; CHECK-NEXT:    je .LBB20_14
2046 ; CHECK-NEXT:  # %bb.4: # %entry
2047 ; CHECK-NEXT:    cmpl $20, %edi
2048 ; CHECK-NEXT:    jne .LBB20_17
2049 ; CHECK-NEXT:  # %bb.5: # %bb2
2050 ; CHECK-NEXT:    movl $2, %edi
2051 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2052 ; CHECK-NEXT:  .LBB20_7: # %entry
2053 ; CHECK-NEXT:    cmpl $30, %edi
2054 ; CHECK-NEXT:    je .LBB20_15
2055 ; CHECK-NEXT:  # %bb.8: # %entry
2056 ; CHECK-NEXT:    cmpl $40, %edi
2057 ; CHECK-NEXT:    jne .LBB20_17
2058 ; CHECK-NEXT:  # %bb.9: # %bb4
2059 ; CHECK-NEXT:    movl $4, %edi
2060 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2061 ; CHECK-NEXT:  .LBB20_14: # %bb1
2062 ; CHECK-NEXT:    movl $1, %edi
2063 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2064 ; CHECK-NEXT:  .LBB20_15: # %bb3
2065 ; CHECK-NEXT:    movl $3, %edi
2066 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2067 ; CHECK-NEXT:  .LBB20_17: # %return
2068 ; CHECK-NEXT:    retq
2069 ;
2070 ; NOOPT-LABEL: left_leaning_weight_balanced_tree2:
2071 ; NOOPT:       # %bb.0: # %entry
2072 ; NOOPT-NEXT:    pushq %rax
2073 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
2074 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
2075 ; NOOPT-NEXT:    testl %edi, %edi
2076 ; NOOPT-NEXT:    je .LBB20_1
2077 ; NOOPT-NEXT:    jmp .LBB20_9
2078 ; NOOPT-NEXT:  .LBB20_9: # %entry
2079 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2080 ; NOOPT-NEXT:    subl $10, %eax
2081 ; NOOPT-NEXT:    je .LBB20_2
2082 ; NOOPT-NEXT:    jmp .LBB20_10
2083 ; NOOPT-NEXT:  .LBB20_10: # %entry
2084 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2085 ; NOOPT-NEXT:    subl $20, %eax
2086 ; NOOPT-NEXT:    je .LBB20_3
2087 ; NOOPT-NEXT:    jmp .LBB20_11
2088 ; NOOPT-NEXT:  .LBB20_11: # %entry
2089 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2090 ; NOOPT-NEXT:    subl $30, %eax
2091 ; NOOPT-NEXT:    je .LBB20_4
2092 ; NOOPT-NEXT:    jmp .LBB20_12
2093 ; NOOPT-NEXT:  .LBB20_12: # %entry
2094 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2095 ; NOOPT-NEXT:    subl $40, %eax
2096 ; NOOPT-NEXT:    je .LBB20_5
2097 ; NOOPT-NEXT:    jmp .LBB20_13
2098 ; NOOPT-NEXT:  .LBB20_13: # %entry
2099 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2100 ; NOOPT-NEXT:    subl $50, %eax
2101 ; NOOPT-NEXT:    je .LBB20_6
2102 ; NOOPT-NEXT:    jmp .LBB20_14
2103 ; NOOPT-NEXT:  .LBB20_14: # %entry
2104 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2105 ; NOOPT-NEXT:    subl $60, %eax
2106 ; NOOPT-NEXT:    je .LBB20_7
2107 ; NOOPT-NEXT:    jmp .LBB20_15
2108 ; NOOPT-NEXT:  .LBB20_15: # %entry
2109 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2110 ; NOOPT-NEXT:    subl $70, %eax
2111 ; NOOPT-NEXT:    je .LBB20_7
2112 ; NOOPT-NEXT:    jmp .LBB20_8
2113 ; NOOPT-NEXT:  .LBB20_1: # %bb0
2114 ; NOOPT-NEXT:    xorl %edi, %edi
2115 ; NOOPT-NEXT:    callq g@PLT
2116 ; NOOPT-NEXT:    jmp .LBB20_8
2117 ; NOOPT-NEXT:  .LBB20_2: # %bb1
2118 ; NOOPT-NEXT:    movl $1, %edi
2119 ; NOOPT-NEXT:    callq g@PLT
2120 ; NOOPT-NEXT:    jmp .LBB20_8
2121 ; NOOPT-NEXT:  .LBB20_3: # %bb2
2122 ; NOOPT-NEXT:    movl $2, %edi
2123 ; NOOPT-NEXT:    callq g@PLT
2124 ; NOOPT-NEXT:    jmp .LBB20_8
2125 ; NOOPT-NEXT:  .LBB20_4: # %bb3
2126 ; NOOPT-NEXT:    movl $3, %edi
2127 ; NOOPT-NEXT:    callq g@PLT
2128 ; NOOPT-NEXT:    jmp .LBB20_8
2129 ; NOOPT-NEXT:  .LBB20_5: # %bb4
2130 ; NOOPT-NEXT:    movl $4, %edi
2131 ; NOOPT-NEXT:    callq g@PLT
2132 ; NOOPT-NEXT:    jmp .LBB20_8
2133 ; NOOPT-NEXT:  .LBB20_6: # %bb5
2134 ; NOOPT-NEXT:    movl $5, %edi
2135 ; NOOPT-NEXT:    callq g@PLT
2136 ; NOOPT-NEXT:    jmp .LBB20_8
2137 ; NOOPT-NEXT:  .LBB20_7: # %bb6
2138 ; NOOPT-NEXT:    movl $6, %edi
2139 ; NOOPT-NEXT:    callq g@PLT
2140 ; NOOPT-NEXT:  .LBB20_8: # %return
2141 ; NOOPT-NEXT:    popq %rax
2142 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
2143 ; NOOPT-NEXT:    retq
2144 entry:
2145   switch i32 %x, label %return [
2146     i32 0,  label %bb0
2147     i32 10, label %bb1
2148     i32 20, label %bb2
2149     i32 30, label %bb3
2150     i32 40, label %bb4
2151     i32 50, label %bb5
2152     i32 60, label %bb6
2153     i32 70, label %bb6
2154   ], !prof !5
2155 bb0: tail call void @g(i32 0) br label %return
2156 bb1: tail call void @g(i32 1) br label %return
2157 bb2: tail call void @g(i32 2) br label %return
2158 bb3: tail call void @g(i32 3) br label %return
2159 bb4: tail call void @g(i32 4) br label %return
2160 bb5: tail call void @g(i32 5) br label %return
2161 bb6: tail call void @g(i32 6) br label %return
2162 bb7: tail call void @g(i32 7) br label %return
2163 return: ret void
2164 }
2165
2166 !5 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 1, i32 90, i32 70, i32 1000}
2167
2168
2169 ; Analogous to left_leaning_weight_balanced_tree.
2170 define void @right_leaning_weight_balanced_tree(i32 %x) {
2171 ; CHECK-LABEL: right_leaning_weight_balanced_tree:
2172 ; CHECK:       # %bb.0: # %entry
2173 ; CHECK-NEXT:    cmpl $19, %edi
2174 ; CHECK-NEXT:    jg .LBB21_4
2175 ; CHECK-NEXT:  # %bb.1: # %entry
2176 ; CHECK-NEXT:    testl %edi, %edi
2177 ; CHECK-NEXT:    jne .LBB21_2
2178 ; CHECK-NEXT:  # %bb.13: # %bb0
2179 ; CHECK-NEXT:    xorl %edi, %edi
2180 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2181 ; CHECK-NEXT:  .LBB21_4: # %entry
2182 ; CHECK-NEXT:    cmpl $49, %edi
2183 ; CHECK-NEXT:    jle .LBB21_5
2184 ; CHECK-NEXT:  # %bb.9: # %entry
2185 ; CHECK-NEXT:    cmpl $70, %edi
2186 ; CHECK-NEXT:    jne .LBB21_10
2187 ; CHECK-NEXT:  .LBB21_12: # %bb6
2188 ; CHECK-NEXT:    movl $6, %edi
2189 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2190 ; CHECK-NEXT:  .LBB21_5: # %entry
2191 ; CHECK-NEXT:    cmpl $20, %edi
2192 ; CHECK-NEXT:    je .LBB21_14
2193 ; CHECK-NEXT:  # %bb.6: # %entry
2194 ; CHECK-NEXT:    cmpl $30, %edi
2195 ; CHECK-NEXT:    je .LBB21_15
2196 ; CHECK-NEXT:  # %bb.7: # %entry
2197 ; CHECK-NEXT:    cmpl $40, %edi
2198 ; CHECK-NEXT:    jne .LBB21_17
2199 ; CHECK-NEXT:  # %bb.8: # %bb4
2200 ; CHECK-NEXT:    movl $4, %edi
2201 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2202 ; CHECK-NEXT:  .LBB21_10: # %entry
2203 ; CHECK-NEXT:    cmpl $50, %edi
2204 ; CHECK-NEXT:    je .LBB21_16
2205 ; CHECK-NEXT:  # %bb.11: # %entry
2206 ; CHECK-NEXT:    cmpl $60, %edi
2207 ; CHECK-NEXT:    je .LBB21_12
2208 ; CHECK-NEXT:    jmp .LBB21_17
2209 ; CHECK-NEXT:  .LBB21_14: # %bb2
2210 ; CHECK-NEXT:    movl $2, %edi
2211 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2212 ; CHECK-NEXT:  .LBB21_15: # %bb3
2213 ; CHECK-NEXT:    movl $3, %edi
2214 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2215 ; CHECK-NEXT:  .LBB21_2: # %entry
2216 ; CHECK-NEXT:    cmpl $10, %edi
2217 ; CHECK-NEXT:    jne .LBB21_17
2218 ; CHECK-NEXT:  # %bb.3: # %bb1
2219 ; CHECK-NEXT:    movl $1, %edi
2220 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2221 ; CHECK-NEXT:  .LBB21_17: # %return
2222 ; CHECK-NEXT:    retq
2223 ; CHECK-NEXT:  .LBB21_16: # %bb5
2224 ; CHECK-NEXT:    movl $5, %edi
2225 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2226 ;
2227 ; NOOPT-LABEL: right_leaning_weight_balanced_tree:
2228 ; NOOPT:       # %bb.0: # %entry
2229 ; NOOPT-NEXT:    pushq %rax
2230 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
2231 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
2232 ; NOOPT-NEXT:    testl %edi, %edi
2233 ; NOOPT-NEXT:    je .LBB21_1
2234 ; NOOPT-NEXT:    jmp .LBB21_9
2235 ; NOOPT-NEXT:  .LBB21_9: # %entry
2236 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2237 ; NOOPT-NEXT:    subl $10, %eax
2238 ; NOOPT-NEXT:    je .LBB21_2
2239 ; NOOPT-NEXT:    jmp .LBB21_10
2240 ; NOOPT-NEXT:  .LBB21_10: # %entry
2241 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2242 ; NOOPT-NEXT:    subl $20, %eax
2243 ; NOOPT-NEXT:    je .LBB21_3
2244 ; NOOPT-NEXT:    jmp .LBB21_11
2245 ; NOOPT-NEXT:  .LBB21_11: # %entry
2246 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2247 ; NOOPT-NEXT:    subl $30, %eax
2248 ; NOOPT-NEXT:    je .LBB21_4
2249 ; NOOPT-NEXT:    jmp .LBB21_12
2250 ; NOOPT-NEXT:  .LBB21_12: # %entry
2251 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2252 ; NOOPT-NEXT:    subl $40, %eax
2253 ; NOOPT-NEXT:    je .LBB21_5
2254 ; NOOPT-NEXT:    jmp .LBB21_13
2255 ; NOOPT-NEXT:  .LBB21_13: # %entry
2256 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2257 ; NOOPT-NEXT:    subl $50, %eax
2258 ; NOOPT-NEXT:    je .LBB21_6
2259 ; NOOPT-NEXT:    jmp .LBB21_14
2260 ; NOOPT-NEXT:  .LBB21_14: # %entry
2261 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2262 ; NOOPT-NEXT:    subl $60, %eax
2263 ; NOOPT-NEXT:    je .LBB21_7
2264 ; NOOPT-NEXT:    jmp .LBB21_15
2265 ; NOOPT-NEXT:  .LBB21_15: # %entry
2266 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2267 ; NOOPT-NEXT:    subl $70, %eax
2268 ; NOOPT-NEXT:    je .LBB21_7
2269 ; NOOPT-NEXT:    jmp .LBB21_8
2270 ; NOOPT-NEXT:  .LBB21_1: # %bb0
2271 ; NOOPT-NEXT:    xorl %edi, %edi
2272 ; NOOPT-NEXT:    callq g@PLT
2273 ; NOOPT-NEXT:    jmp .LBB21_8
2274 ; NOOPT-NEXT:  .LBB21_2: # %bb1
2275 ; NOOPT-NEXT:    movl $1, %edi
2276 ; NOOPT-NEXT:    callq g@PLT
2277 ; NOOPT-NEXT:    jmp .LBB21_8
2278 ; NOOPT-NEXT:  .LBB21_3: # %bb2
2279 ; NOOPT-NEXT:    movl $2, %edi
2280 ; NOOPT-NEXT:    callq g@PLT
2281 ; NOOPT-NEXT:    jmp .LBB21_8
2282 ; NOOPT-NEXT:  .LBB21_4: # %bb3
2283 ; NOOPT-NEXT:    movl $3, %edi
2284 ; NOOPT-NEXT:    callq g@PLT
2285 ; NOOPT-NEXT:    jmp .LBB21_8
2286 ; NOOPT-NEXT:  .LBB21_5: # %bb4
2287 ; NOOPT-NEXT:    movl $4, %edi
2288 ; NOOPT-NEXT:    callq g@PLT
2289 ; NOOPT-NEXT:    jmp .LBB21_8
2290 ; NOOPT-NEXT:  .LBB21_6: # %bb5
2291 ; NOOPT-NEXT:    movl $5, %edi
2292 ; NOOPT-NEXT:    callq g@PLT
2293 ; NOOPT-NEXT:    jmp .LBB21_8
2294 ; NOOPT-NEXT:  .LBB21_7: # %bb6
2295 ; NOOPT-NEXT:    movl $6, %edi
2296 ; NOOPT-NEXT:    callq g@PLT
2297 ; NOOPT-NEXT:  .LBB21_8: # %return
2298 ; NOOPT-NEXT:    popq %rax
2299 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
2300 ; NOOPT-NEXT:    retq
2301 entry:
2302   switch i32 %x, label %return [
2303     i32 0,  label %bb0
2304     i32 10, label %bb1
2305     i32 20, label %bb2
2306     i32 30, label %bb3
2307     i32 40, label %bb4
2308     i32 50, label %bb5
2309     i32 60, label %bb6
2310     i32 70, label %bb6
2311   ], !prof !6
2312 bb0: tail call void @g(i32 0) br label %return
2313 bb1: tail call void @g(i32 1) br label %return
2314 bb2: tail call void @g(i32 2) br label %return
2315 bb3: tail call void @g(i32 3) br label %return
2316 bb4: tail call void @g(i32 4) br label %return
2317 bb5: tail call void @g(i32 5) br label %return
2318 bb6: tail call void @g(i32 6) br label %return
2319 bb7: tail call void @g(i32 7) br label %return
2320 return: ret void
2321 }
2322
2323 !6 = !{!"branch_weights", i32 1, i32 1000, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 10}
2324
2325
2326 ; If the tree were balanced based on number of clusters, {0-3,100} would go on
2327 ; the left and {200,300} on the right. However, the jump table weights as much
2328 ; as its components, so 100 is selected as the pivot.
2329 define void @jump_table_affects_balance(i32 %x) {
2330 ; CHECK-LABEL: jump_table_affects_balance:
2331 ; CHECK:       # %bb.0: # %entry
2332 ; CHECK-NEXT:    cmpl $99, %edi
2333 ; CHECK-NEXT:    jg .LBB22_3
2334 ; CHECK-NEXT:  # %bb.1: # %entry
2335 ; CHECK-NEXT:    cmpl $3, %edi
2336 ; CHECK-NEXT:    ja .LBB22_10
2337 ; CHECK-NEXT:  # %bb.2: # %entry
2338 ; CHECK-NEXT:    movl %edi, %eax
2339 ; CHECK-NEXT:    jmpq *.LJTI22_0(,%rax,8)
2340 ; CHECK-NEXT:  .LBB22_9: # %bb3
2341 ; CHECK-NEXT:    movl $3, %edi
2342 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2343 ; CHECK-NEXT:  .LBB22_3: # %entry
2344 ; CHECK-NEXT:    cmpl $300, %edi # imm = 0x12C
2345 ; CHECK-NEXT:    je .LBB22_8
2346 ; CHECK-NEXT:  # %bb.4: # %entry
2347 ; CHECK-NEXT:    cmpl $200, %edi
2348 ; CHECK-NEXT:    je .LBB22_7
2349 ; CHECK-NEXT:  # %bb.5: # %entry
2350 ; CHECK-NEXT:    cmpl $100, %edi
2351 ; CHECK-NEXT:    jne .LBB22_10
2352 ; CHECK-NEXT:  .LBB22_6: # %bb0
2353 ; CHECK-NEXT:    xorl %edi, %edi
2354 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2355 ; CHECK-NEXT:  .LBB22_8: # %bb2
2356 ; CHECK-NEXT:    movl $2, %edi
2357 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2358 ; CHECK-NEXT:  .LBB22_7: # %bb1
2359 ; CHECK-NEXT:    movl $1, %edi
2360 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2361 ; CHECK-NEXT:  .LBB22_10: # %return
2362 ; CHECK-NEXT:    retq
2363 ;
2364 ; NOOPT-LABEL: jump_table_affects_balance:
2365 ; NOOPT:       # %bb.0: # %entry
2366 ; NOOPT-NEXT:    pushq %rax
2367 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
2368 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
2369 ; NOOPT-NEXT:    testl %edi, %edi
2370 ; NOOPT-NEXT:    je .LBB22_1
2371 ; NOOPT-NEXT:    jmp .LBB22_6
2372 ; NOOPT-NEXT:  .LBB22_6: # %entry
2373 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2374 ; NOOPT-NEXT:    subl $1, %eax
2375 ; NOOPT-NEXT:    je .LBB22_2
2376 ; NOOPT-NEXT:    jmp .LBB22_7
2377 ; NOOPT-NEXT:  .LBB22_7: # %entry
2378 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2379 ; NOOPT-NEXT:    subl $2, %eax
2380 ; NOOPT-NEXT:    je .LBB22_3
2381 ; NOOPT-NEXT:    jmp .LBB22_8
2382 ; NOOPT-NEXT:  .LBB22_8: # %entry
2383 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2384 ; NOOPT-NEXT:    subl $3, %eax
2385 ; NOOPT-NEXT:    je .LBB22_4
2386 ; NOOPT-NEXT:    jmp .LBB22_9
2387 ; NOOPT-NEXT:  .LBB22_9: # %entry
2388 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2389 ; NOOPT-NEXT:    subl $100, %eax
2390 ; NOOPT-NEXT:    je .LBB22_1
2391 ; NOOPT-NEXT:    jmp .LBB22_10
2392 ; NOOPT-NEXT:  .LBB22_10: # %entry
2393 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2394 ; NOOPT-NEXT:    subl $200, %eax
2395 ; NOOPT-NEXT:    je .LBB22_2
2396 ; NOOPT-NEXT:    jmp .LBB22_11
2397 ; NOOPT-NEXT:  .LBB22_11: # %entry
2398 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2399 ; NOOPT-NEXT:    subl $300, %eax # imm = 0x12C
2400 ; NOOPT-NEXT:    je .LBB22_3
2401 ; NOOPT-NEXT:    jmp .LBB22_5
2402 ; NOOPT-NEXT:  .LBB22_1: # %bb0
2403 ; NOOPT-NEXT:    xorl %edi, %edi
2404 ; NOOPT-NEXT:    callq g@PLT
2405 ; NOOPT-NEXT:    jmp .LBB22_5
2406 ; NOOPT-NEXT:  .LBB22_2: # %bb1
2407 ; NOOPT-NEXT:    movl $1, %edi
2408 ; NOOPT-NEXT:    callq g@PLT
2409 ; NOOPT-NEXT:    jmp .LBB22_5
2410 ; NOOPT-NEXT:  .LBB22_3: # %bb2
2411 ; NOOPT-NEXT:    movl $2, %edi
2412 ; NOOPT-NEXT:    callq g@PLT
2413 ; NOOPT-NEXT:    jmp .LBB22_5
2414 ; NOOPT-NEXT:  .LBB22_4: # %bb3
2415 ; NOOPT-NEXT:    movl $3, %edi
2416 ; NOOPT-NEXT:    callq g@PLT
2417 ; NOOPT-NEXT:  .LBB22_5: # %return
2418 ; NOOPT-NEXT:    popq %rax
2419 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
2420 ; NOOPT-NEXT:    retq
2421 entry:
2422   switch i32 %x, label %return [
2423     ; Jump table:
2424     i32 0,  label %bb0
2425     i32 1,  label %bb1
2426     i32 2,  label %bb2
2427     i32 3,  label %bb3
2428
2429     i32 100, label %bb0
2430     i32 200, label %bb1
2431     i32 300, label %bb2
2432   ]
2433 bb0: tail call void @g(i32 0) br label %return
2434 bb1: tail call void @g(i32 1) br label %return
2435 bb2: tail call void @g(i32 2) br label %return
2436 bb3: tail call void @g(i32 3) br label %return
2437 return: ret void
2438 }
2439
2440
2441 ; Don't assert due to truncating the bitwidth (64) to i4 when checking
2442 ; that the bit-test range fits in a word.
2443 define void @pr23738(i4 %x) {
2444 ; CHECK-LABEL: pr23738:
2445 ; CHECK:       # %bb.0: # %entry
2446 ; CHECK-NEXT:    movl %edi, %eax
2447 ; CHECK-NEXT:    andb $15, %al
2448 ; CHECK-NEXT:    cmpb $11, %al
2449 ; CHECK-NEXT:    ja .LBB23_2
2450 ; CHECK-NEXT:  # %bb.1: # %entry
2451 ; CHECK-NEXT:    andl $15, %edi
2452 ; CHECK-NEXT:    movl $2051, %eax # imm = 0x803
2453 ; CHECK-NEXT:    btl %edi, %eax
2454 ; CHECK-NEXT:    jae .LBB23_2
2455 ; CHECK-NEXT:  # %bb.3: # %bb1
2456 ; CHECK-NEXT:    movl $1, %edi
2457 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2458 ; CHECK-NEXT:  .LBB23_2: # %bb0
2459 ; CHECK-NEXT:    xorl %edi, %edi
2460 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2461 ;
2462 ; NOOPT-LABEL: pr23738:
2463 ; NOOPT:       # %bb.0: # %entry
2464 ; NOOPT-NEXT:    pushq %rax
2465 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
2466 ; NOOPT-NEXT:    movb %dil, %al
2467 ; NOOPT-NEXT:    movb %al, {{[-0-9]+}}(%r{{[sb]}}p) # 1-byte Spill
2468 ; NOOPT-NEXT:    andb $15, %al
2469 ; NOOPT-NEXT:    subb $11, %al
2470 ; NOOPT-NEXT:    je .LBB23_2
2471 ; NOOPT-NEXT:    jmp .LBB23_4
2472 ; NOOPT-NEXT:  .LBB23_4: # %entry
2473 ; NOOPT-NEXT:    movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload
2474 ; NOOPT-NEXT:    andb $15, %al
2475 ; NOOPT-NEXT:    subb $2, %al
2476 ; NOOPT-NEXT:    jb .LBB23_2
2477 ; NOOPT-NEXT:    jmp .LBB23_1
2478 ; NOOPT-NEXT:  .LBB23_1: # %bb0
2479 ; NOOPT-NEXT:    xorl %edi, %edi
2480 ; NOOPT-NEXT:    callq g@PLT
2481 ; NOOPT-NEXT:    jmp .LBB23_3
2482 ; NOOPT-NEXT:  .LBB23_2: # %bb1
2483 ; NOOPT-NEXT:    movl $1, %edi
2484 ; NOOPT-NEXT:    callq g@PLT
2485 ; NOOPT-NEXT:  .LBB23_3: # %return
2486 ; NOOPT-NEXT:    popq %rax
2487 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
2488 ; NOOPT-NEXT:    retq
2489 entry:
2490   switch i4 %x, label %bb0 [
2491     i4 0, label %bb1
2492     i4 1, label %bb1
2493     i4 -5, label %bb1
2494   ]
2495 bb0: tail call void @g(i32 0) br label %return
2496 bb1: tail call void @g(i32 1) br label %return
2497 return: ret void
2498 }
2499
2500
2501 ; The switch is lowered with bit tests. Since the case range is contiguous, the
2502 ; second bit test is redundant and can be skipped. Check that we don't update
2503 ; the phi node with an incoming value from the MBB of the skipped bit test
2504 ; (-verify-machine-instrs cathces this).
2505 define i32 @pr27135(i32 %i) {
2506 ; CHECK-LABEL: pr27135:
2507 ; CHECK:       # %bb.0: # %entry
2508 ; CHECK-NEXT:    xorl %eax, %eax
2509 ; CHECK-NEXT:    testb %al, %al
2510 ; CHECK-NEXT:    jne .LBB24_5
2511 ; CHECK-NEXT:  # %bb.1: # %sw
2512 ; CHECK-NEXT:    movl $1, %eax
2513 ; CHECK-NEXT:    addl $-96, %edi
2514 ; CHECK-NEXT:    cmpl $5, %edi
2515 ; CHECK-NEXT:    jbe .LBB24_2
2516 ; CHECK-NEXT:  .LBB24_5: # %end
2517 ; CHECK-NEXT:    retq
2518 ; CHECK-NEXT:  .LBB24_2: # %sw
2519 ; CHECK-NEXT:    movl $19, %eax
2520 ; CHECK-NEXT:    btl %edi, %eax
2521 ; CHECK-NEXT:    jae .LBB24_3
2522 ; CHECK-NEXT:  # %bb.4: # %sw.bb2
2523 ; CHECK-NEXT:  .LBB24_3: # %sw.bb
2524 ;
2525 ; NOOPT-LABEL: pr27135:
2526 ; NOOPT:       # %bb.0: # %entry
2527 ; NOOPT-NEXT:    movl %edi, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
2528 ; NOOPT-NEXT:    xorl %eax, %eax
2529 ; NOOPT-NEXT:    # implicit-def: $cl
2530 ; NOOPT-NEXT:    testb $1, %cl
2531 ; NOOPT-NEXT:    movl %eax, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
2532 ; NOOPT-NEXT:    jne .LBB24_1
2533 ; NOOPT-NEXT:    jmp .LBB24_4
2534 ; NOOPT-NEXT:  .LBB24_1: # %sw
2535 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2536 ; NOOPT-NEXT:    movl $1, %ecx
2537 ; NOOPT-NEXT:    movl %ecx, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
2538 ; NOOPT-NEXT:    addl $-96, %eax
2539 ; NOOPT-NEXT:    subl $2, %eax
2540 ; NOOPT-NEXT:    jb .LBB24_3
2541 ; NOOPT-NEXT:    jmp .LBB24_5
2542 ; NOOPT-NEXT:  .LBB24_5: # %sw
2543 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2544 ; NOOPT-NEXT:    addl $-98, %eax
2545 ; NOOPT-NEXT:    subl $2, %eax
2546 ; NOOPT-NEXT:    jb .LBB24_2
2547 ; NOOPT-NEXT:    jmp .LBB24_6
2548 ; NOOPT-NEXT:  .LBB24_6: # %sw
2549 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2550 ; NOOPT-NEXT:    subl $100, %eax
2551 ; NOOPT-NEXT:    je .LBB24_3
2552 ; NOOPT-NEXT:    jmp .LBB24_7
2553 ; NOOPT-NEXT:  .LBB24_7: # %sw
2554 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2555 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %ecx # 4-byte Reload
2556 ; NOOPT-NEXT:    subl $101, %ecx
2557 ; NOOPT-NEXT:    movl %eax, {{[-0-9]+}}(%r{{[sb]}}p) # 4-byte Spill
2558 ; NOOPT-NEXT:    jne .LBB24_4
2559 ; NOOPT-NEXT:    jmp .LBB24_2
2560 ; NOOPT-NEXT:  .LBB24_2: # %sw.bb
2561 ; NOOPT-NEXT:  .LBB24_3: # %sw.bb2
2562 ; NOOPT-NEXT:  .LBB24_4: # %end
2563 ; NOOPT-NEXT:    movl {{[-0-9]+}}(%r{{[sb]}}p), %eax # 4-byte Reload
2564 ; NOOPT-NEXT:    retq
2565 entry:
2566   br i1 undef, label %sw, label %end
2567 sw:
2568   switch i32 %i, label %end [
2569     i32 99,  label %sw.bb
2570     i32 98,  label %sw.bb
2571     i32 101, label %sw.bb
2572     i32 97,  label %sw.bb2
2573     i32 96,  label %sw.bb2
2574     i32 100, label %sw.bb2
2575   ]
2576 sw.bb:
2577   unreachable
2578 sw.bb2:
2579   unreachable
2580 end:
2581   %p = phi i32 [ 1, %sw ], [ 0, %entry ]
2582   ret i32 %p
2583 }
2584
2585
2586 ; Since the default is unreachable, either cluster will be reached.
2587 ; Only one comparison should be emitted.
2588 define void @range_with_unreachable_fallthrough(i32 %i) {
2589 ; CHECK-LABEL: range_with_unreachable_fallthrough:
2590 ; CHECK:       # %bb.0: # %entry
2591 ; CHECK-NEXT:    addl $-4, %edi
2592 ; CHECK-NEXT:    cmpl $3, %edi
2593 ; CHECK-NEXT:    jae .LBB25_1
2594 ; CHECK-NEXT:  # %bb.2: # %bb2
2595 ; CHECK-NEXT:    movl $1, %edi
2596 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2597 ; CHECK-NEXT:  .LBB25_1: # %bb1
2598 ; CHECK-NEXT:    xorl %edi, %edi
2599 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2600 ;
2601 ; NOOPT-LABEL: range_with_unreachable_fallthrough:
2602 ; NOOPT:       # %bb.0: # %entry
2603 ; NOOPT-NEXT:    pushq %rax
2604 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
2605 ; NOOPT-NEXT:    movl %edi, %eax
2606 ; NOOPT-NEXT:    decl %eax
2607 ; NOOPT-NEXT:    subl $3, %eax
2608 ; NOOPT-NEXT:    jb .LBB25_1
2609 ; NOOPT-NEXT:    jmp .LBB25_5
2610 ; NOOPT-NEXT:  .LBB25_5: # %entry
2611 ; NOOPT-NEXT:    jmp .LBB25_2
2612 ; NOOPT-NEXT:  .LBB25_1: # %bb1
2613 ; NOOPT-NEXT:    xorl %edi, %edi
2614 ; NOOPT-NEXT:    callq g@PLT
2615 ; NOOPT-NEXT:    jmp .LBB25_4
2616 ; NOOPT-NEXT:  .LBB25_2: # %bb2
2617 ; NOOPT-NEXT:    movl $1, %edi
2618 ; NOOPT-NEXT:    callq g@PLT
2619 ; NOOPT-NEXT:    jmp .LBB25_4
2620 ; NOOPT-NEXT:  # %bb.3: # %default
2621 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
2622 ; NOOPT-NEXT:  .LBB25_4: # %return
2623 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
2624 ; NOOPT-NEXT:    popq %rax
2625 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
2626 ; NOOPT-NEXT:    retq
2627 entry:
2628   switch i32 %i, label %default [
2629     i32 1, label %bb1
2630     i32 2, label %bb1
2631     i32 3, label %bb1
2632     i32 4, label %bb2
2633     i32 5, label %bb2
2634     i32 6, label %bb2
2635   ]
2636 bb1: tail call void @g(i32 0) br label %return
2637 bb2: tail call void @g(i32 1) br label %return
2638 default: unreachable
2639
2640 return:
2641   ret void
2642 }
2643
2644
2645 ; A switch over a small type (i8) should be extended to avoid truncation
2646 ; instructions.
2647 define void @switch_i8(i32 %a) {
2648 ; CHECK-LABEL: switch_i8:
2649 ; CHECK:       # %bb.0:
2650 ; CHECK-NEXT:    # kill: def $edi killed $edi def $rdi
2651 ; CHECK-NEXT:    andl $127, %edi
2652 ; CHECK-NEXT:    leal -1(%rdi), %eax
2653 ; CHECK-NEXT:    cmpl $8, %eax
2654 ; CHECK-NEXT:    ja .LBB26_1
2655 ; CHECK-NEXT:  # %bb.10:
2656 ; CHECK-NEXT:    jmpq *.LJTI26_0(,%rax,8)
2657 ; CHECK-NEXT:  .LBB26_4: # %bb0
2658 ; CHECK-NEXT:    xorl %edi, %edi
2659 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2660 ; CHECK-NEXT:  .LBB26_1:
2661 ; CHECK-NEXT:    cmpl $13, %edi
2662 ; CHECK-NEXT:    je .LBB26_8
2663 ; CHECK-NEXT:  # %bb.2:
2664 ; CHECK-NEXT:    cmpl $42, %edi
2665 ; CHECK-NEXT:    jne .LBB26_9
2666 ; CHECK-NEXT:  # %bb.3: # %bb5
2667 ; CHECK-NEXT:    movl $5, %edi
2668 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2669 ; CHECK-NEXT:  .LBB26_9: # %return
2670 ; CHECK-NEXT:    retq
2671 ; CHECK-NEXT:  .LBB26_7: # %bb3
2672 ; CHECK-NEXT:    movl $3, %edi
2673 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2674 ; CHECK-NEXT:  .LBB26_5: # %bb1
2675 ; CHECK-NEXT:    movl $1, %edi
2676 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2677 ; CHECK-NEXT:  .LBB26_6: # %bb2
2678 ; CHECK-NEXT:    movl $2, %edi
2679 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2680 ; CHECK-NEXT:  .LBB26_8: # %bb4
2681 ; CHECK-NEXT:    movl $4, %edi
2682 ; CHECK-NEXT:    jmp g@PLT # TAILCALL
2683 ;
2684 ; NOOPT-LABEL: switch_i8:
2685 ; NOOPT:       # %bb.0:
2686 ; NOOPT-NEXT:    pushq %rax
2687 ; NOOPT-NEXT:    .cfi_def_cfa_offset 16
2688 ; NOOPT-NEXT:    movb %dil, %al
2689 ; NOOPT-NEXT:    andb $127, %al
2690 ; NOOPT-NEXT:    movb %al, {{[-0-9]+}}(%r{{[sb]}}p) # 1-byte Spill
2691 ; NOOPT-NEXT:    subb $1, %al
2692 ; NOOPT-NEXT:    je .LBB26_1
2693 ; NOOPT-NEXT:    jmp .LBB26_8
2694 ; NOOPT-NEXT:  .LBB26_8:
2695 ; NOOPT-NEXT:    movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload
2696 ; NOOPT-NEXT:    subb $3, %al
2697 ; NOOPT-NEXT:    je .LBB26_2
2698 ; NOOPT-NEXT:    jmp .LBB26_9
2699 ; NOOPT-NEXT:  .LBB26_9:
2700 ; NOOPT-NEXT:    movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload
2701 ; NOOPT-NEXT:    subb $7, %al
2702 ; NOOPT-NEXT:    je .LBB26_3
2703 ; NOOPT-NEXT:    jmp .LBB26_10
2704 ; NOOPT-NEXT:  .LBB26_10:
2705 ; NOOPT-NEXT:    movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload
2706 ; NOOPT-NEXT:    subb $9, %al
2707 ; NOOPT-NEXT:    je .LBB26_4
2708 ; NOOPT-NEXT:    jmp .LBB26_11
2709 ; NOOPT-NEXT:  .LBB26_11:
2710 ; NOOPT-NEXT:    movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload
2711 ; NOOPT-NEXT:    subb $13, %al
2712 ; NOOPT-NEXT:    je .LBB26_5
2713 ; NOOPT-NEXT:    jmp .LBB26_12
2714 ; NOOPT-NEXT:  .LBB26_12:
2715 ; NOOPT-NEXT:    movb {{[-0-9]+}}(%r{{[sb]}}p), %al # 1-byte Reload
2716 ; NOOPT-NEXT:    subb $42, %al
2717 ; NOOPT-NEXT:    je .LBB26_6
2718 ; NOOPT-NEXT:    jmp .LBB26_7
2719 ; NOOPT-NEXT:  .LBB26_1: # %bb0
2720 ; NOOPT-NEXT:    xorl %edi, %edi
2721 ; NOOPT-NEXT:    callq g@PLT
2722 ; NOOPT-NEXT:    jmp .LBB26_7
2723 ; NOOPT-NEXT:  .LBB26_2: # %bb1
2724 ; NOOPT-NEXT:    movl $1, %edi
2725 ; NOOPT-NEXT:    callq g@PLT
2726 ; NOOPT-NEXT:    jmp .LBB26_7
2727 ; NOOPT-NEXT:  .LBB26_3: # %bb2
2728 ; NOOPT-NEXT:    movl $2, %edi
2729 ; NOOPT-NEXT:    callq g@PLT
2730 ; NOOPT-NEXT:    jmp .LBB26_7
2731 ; NOOPT-NEXT:  .LBB26_4: # %bb3
2732 ; NOOPT-NEXT:    movl $3, %edi
2733 ; NOOPT-NEXT:    callq g@PLT
2734 ; NOOPT-NEXT:    jmp .LBB26_7
2735 ; NOOPT-NEXT:  .LBB26_5: # %bb4
2736 ; NOOPT-NEXT:    movl $4, %edi
2737 ; NOOPT-NEXT:    callq g@PLT
2738 ; NOOPT-NEXT:    jmp .LBB26_7
2739 ; NOOPT-NEXT:  .LBB26_6: # %bb5
2740 ; NOOPT-NEXT:    movl $5, %edi
2741 ; NOOPT-NEXT:    callq g@PLT
2742 ; NOOPT-NEXT:  .LBB26_7: # %return
2743 ; NOOPT-NEXT:    popq %rax
2744 ; NOOPT-NEXT:    .cfi_def_cfa_offset 8
2745 ; NOOPT-NEXT:    retq
2746   %and = and i32 %a, 127
2747   %trunc = trunc i32 %and to i8
2748   switch i8 %trunc, label %return [
2749     i8 1, label %bb0
2750     i8 3, label %bb1
2751     i8 7, label %bb2
2752     i8 9, label %bb3
2753     i8 13, label %bb4
2754     i8 42, label %bb5
2755   ]
2756 bb0: tail call void @g(i32 0) br label %return
2757 bb1: tail call void @g(i32 1) br label %return
2758 bb2: tail call void @g(i32 2) br label %return
2759 bb3: tail call void @g(i32 3) br label %return
2760 bb4: tail call void @g(i32 4) br label %return
2761 bb5: tail call void @g(i32 5) br label %return
2762 return:
2763   ret void
2764 }