test/CodeGen/X86/switch.ll

   1 ; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -jump-table-density=40 -switch-peel-threshold=101 -verify-machineinstrs | FileCheck %s
   2 ; RUN: llc -mtriple=x86_64-linux-gnu %s -o - -O0 -jump-table-density=40 -verify-machineinstrs | FileCheck --check-prefix=NOOPT %s
   3
   4 declare void @g(i32)
   5
   6 define void @basic(i32 %x) {
   7 entry:
   8   switch i32 %x, label %return [
   9     i32 3, label %bb0
  10     i32 1, label %bb1
  11     i32 4, label %bb1
  12     i32 5, label %bb2
  13   ]
  14 bb0: tail call void @g(i32 0) br label %return
  15 bb1: tail call void @g(i32 1) br label %return
  16 bb2: tail call void @g(i32 1) br label %return
  17 return: ret void
  18
  19 ; Lowered as a jump table, both with and without optimization.
  20 ; CHECK-LABEL: basic
  21 ; CHECK: decl
  22 ; CHECK: cmpl $4
  23 ; CHECK: ja
  24 ; CHECK: jmpq *.LJTI
  25 ; NOOPT-LABEL: basic
  26 ; NOOPT: decl
  27 ; NOOPT: subl $4
  28 ; NOOPT: ja
  29 ; NOOPT: movq .LJTI
  30 ; NOOPT: jmpq
  31 }
  32
  33 ; Should never be lowered as a jump table because of the attribute
  34 define void @basic_nojumptable(i32 %x) "no-jump-tables"="true" {
  35 entry:
  36   switch i32 %x, label %return [
  37     i32 3, label %bb0
  38     i32 1, label %bb1
  39     i32 4, label %bb1
  40     i32 5, label %bb2
  41   ]
  42 bb0: tail call void @g(i32 0) br label %return
  43 bb1: tail call void @g(i32 1) br label %return
  44 bb2: tail call void @g(i32 1) br label %return
  45 return: ret void
  46
  47 ; Lowered as a jump table, both with and without optimization.
  48 ; CHECK-LABEL: basic_nojumptable
  49 ; CHECK-NOT: jmpq *.LJTI
  50 }
  51
  52 ; Should be lowered as a jump table because of the attribute
  53 define void @basic_nojumptable_false(i32 %x) "no-jump-tables"="false" {
  54 entry:
  55   switch i32 %x, label %return [
  56     i32 3, label %bb0
  57     i32 1, label %bb1
  58     i32 4, label %bb1
  59     i32 5, label %bb2
  60   ]
  61 bb0: tail call void @g(i32 0) br label %return
  62 bb1: tail call void @g(i32 1) br label %return
  63 bb2: tail call void @g(i32 1) br label %return
  64 return: ret void
  65
  66 ; Lowered as a jump table, both with and without optimization.
  67 ; CHECK-LABEL: basic_nojumptable_false
  68 ; CHECK: decl
  69 ; CHECK: cmpl $4
  70 ; CHECK: ja
  71 ; CHECK: jmpq *.LJTI
  72 }
  73
  74
  75 define void @simple_ranges(i32 %x) {
  76 entry:
  77   switch i32 %x, label %return [
  78     i32 0, label %bb0
  79     i32 1, label %bb0
  80     i32 2, label %bb0
  81     i32 3, label %bb0
  82     i32 100, label %bb1
  83     i32 101, label %bb1
  84     i32 102, label %bb1
  85     i32 103, label %bb1
  86   ]
  87 bb0: tail call void @g(i32 0) br label %return
  88 bb1: tail call void @g(i32 1) br label %return
  89 return: ret void
  90
  91
  92
  93 ; Should be lowered to two range checks.
  94 ; CHECK-LABEL: simple_ranges
  95 ; CHECK: leal -100
  96 ; CHECK: cmpl $4
  97 ; CHECK: jb
  98 ; CHECK: cmpl $3
  99 ; CHECK: ja
 100
 101 ; We do this even at -O0, because it's cheap and makes codegen faster.
 102 ; NOOPT-LABEL: simple_ranges
 103 ; NOOPT: subl $4
 104 ; NOOPT: jb
 105 ; NOOPT: addl $-100
 106 ; NOOPT: subl $4
 107 ; NOOPT: jb
 108 }
 109
 110
 111 define void @jt_is_better(i32 %x) {
 112 entry:
 113   switch i32 %x, label %return [
 114     i32 0, label %bb0
 115     i32 2, label %bb0
 116     i32 4, label %bb0
 117     i32 1, label %bb1
 118     i32 3, label %bb1
 119     i32 5, label %bb1
 120
 121     i32 6, label %bb2
 122     i32 7, label %bb3
 123     i32 8, label %bb4
 124   ]
 125 bb0: tail call void @g(i32 0) br label %return
 126 bb1: tail call void @g(i32 1) br label %return
 127 bb2: tail call void @g(i32 2) br label %return
 128 bb3: tail call void @g(i32 3) br label %return
 129 bb4: tail call void @g(i32 4) br label %return
 130 return: ret void
 131
 132 ; Cases 0-5 could be lowered with two bit tests,
 133 ; but with 6-8, the whole switch is suitable for a jump table.
 134 ; CHECK-LABEL: jt_is_better
 135 ; CHECK: cmpl $8
 136 ; CHECK: ja
 137 ; CHECK: jmpq *.LJTI
 138 }
 139
 140
 141 define void @bt_is_better(i32 %x) {
 142 entry:
 143   switch i32 %x, label %return [
 144     i32 0, label %bb0
 145     i32 3, label %bb0
 146     i32 6, label %bb0
 147     i32 1, label %bb1
 148     i32 4, label %bb1
 149     i32 7, label %bb1
 150     i32 2, label %bb2
 151     i32 5, label %bb2
 152     i32 8, label %bb2
 153   ]
 154 bb0: tail call void @g(i32 0) br label %return
 155 bb1: tail call void @g(i32 1) br label %return
 156 bb2: tail call void @g(i32 2) br label %return
 157 return: ret void
 158
 159 ; This could be lowered as a jump table, but bit tests is more efficient.
 160 ; CHECK-LABEL: bt_is_better
 161 ; The bit test on 2,5,8 is unnecessary as all cases cover the rage [0, 8].
 162 ; The range check guarantees that cases other than 0,3,6 and 1,4,7 must be
 163 ; in 2,5,8.
 164 ;
 165 ; 73 = 2^0 + 2^3 + 2^6
 166 ; CHECK: movl $73
 167 ; CHECK: btl
 168 ; 146 = 2^1 + 2^4 + 2^7
 169 ; CHECK: movl $146
 170 ; CHECK: btl
 171 ; 292 = 2^2 + 2^5 + 2^8
 172 ; CHECK-NOT: movl $292
 173 ; CHECK-NOT: btl
 174 }
 175
 176 define void @bt_is_better2(i32 %x) {
 177 entry:
 178   switch i32 %x, label %return [
 179     i32 0, label %bb0
 180     i32 3, label %bb0
 181     i32 6, label %bb0
 182     i32 1, label %bb1
 183     i32 4, label %bb1
 184     i32 7, label %bb1
 185     i32 2, label %bb2
 186     i32 8, label %bb2
 187   ]
 188 bb0: tail call void @g(i32 0) br label %return
 189 bb1: tail call void @g(i32 1) br label %return
 190 bb2: tail call void @g(i32 2) br label %return
 191 return: ret void
 192
 193 ; This will also be lowered as bit test, but as the range [0,8] is not fully
 194 ; covered (5 missing), the default statement can be jumped to and we end up
 195 ; with one more branch.
 196 ; CHECK-LABEL: bt_is_better2
 197 ;
 198 ; 73 = 2^0 + 2^3 + 2^6
 199 ; CHECK: movl $73
 200 ; CHECK: btl
 201 ; 146 = 2^1 + 2^4 + 2^7
 202 ; CHECK: movl $146
 203 ; CHECK: btl
 204 ; 260 = 2^2 + 2^8
 205 ; CHECK: movl $260
 206 ; CHECK: btl
 207 }
 208
 209 define void @bt_is_better3(i32 %x) {
 210 entry:
 211   switch i32 %x, label %return [
 212     i32 10, label %bb0
 213     i32 13, label %bb0
 214     i32 16, label %bb0
 215     i32 11, label %bb1
 216     i32 14, label %bb1
 217     i32 17, label %bb1
 218     i32 12, label %bb2
 219     i32 18, label %bb2
 220   ]
 221 bb0: tail call void @g(i32 0) br label %return
 222 bb1: tail call void @g(i32 1) br label %return
 223 bb2: tail call void @g(i32 2) br label %return
 224 return: ret void
 225
 226 ; We don't have to subtract 10 from the case value to let the range become
 227 ; [0, 8], as each value in the range [10, 18] can be represented by bits in a
 228 ; word. Then we still need a branch to jump to the default statement for the
 229 ; range [0, 10).
 230 ; CHECK-LABEL: bt_is_better3
 231 ;
 232 ; 74752 = 2^10 + 2^13 + 2^16
 233 ; CHECK: movl $74752
 234 ; CHECK: btl
 235 ; 149504 = 2^11 + 2^14 + 2^17
 236 ; CHECK: movl $149504
 237 ; CHECK: btl
 238 ; 266240 = 2^12 + 2^15 + 2^18
 239 ; CHECK: movl $266240
 240 ; CHECK: btl
 241 }
 242
 243
 244 define void @optimal_pivot1(i32 %x) {
 245 entry:
 246   switch i32 %x, label %return [
 247     i32 100, label %bb0
 248     i32 200, label %bb1
 249     i32 300, label %bb0
 250     i32 400, label %bb1
 251     i32 500, label %bb0
 252     i32 600, label %bb1
 253
 254   ]
 255 bb0: tail call void @g(i32 0) br label %return
 256 bb1: tail call void @g(i32 1) br label %return
 257 return: ret void
 258
 259 ; Should pivot around 400 for two subtrees of equal size.
 260 ; CHECK-LABEL: optimal_pivot1
 261 ; CHECK-NOT: cmpl
 262 ; CHECK: cmpl $399
 263 }
 264
 265
 266 define void @optimal_pivot2(i32 %x) {
 267 entry:
 268   switch i32 %x, label %return [
 269     i32 100, label %bb0   i32 101, label %bb1   i32 102, label %bb2   i32 103, label %bb3
 270     i32 200, label %bb0   i32 201, label %bb1   i32 202, label %bb2   i32 203, label %bb3
 271     i32 300, label %bb0   i32 301, label %bb1   i32 302, label %bb2   i32 303, label %bb3
 272     i32 400, label %bb0   i32 401, label %bb1   i32 402, label %bb2   i32 403, label %bb3
 273
 274   ]
 275 bb0: tail call void @g(i32 0) br label %return
 276 bb1: tail call void @g(i32 1) br label %return
 277 bb2: tail call void @g(i32 2) br label %return
 278 bb3: tail call void @g(i32 3) br label %return
 279 return: ret void
 280
 281 ; Should pivot around 300 for two subtrees with two jump tables each.
 282 ; CHECK-LABEL: optimal_pivot2
 283 ; CHECK-NOT: cmpl
 284 ; CHECK: cmpl $299
 285 ; CHECK: jmpq *.LJTI
 286 ; CHECK: jmpq *.LJTI
 287 ; CHECK: jmpq *.LJTI
 288 ; CHECK: jmpq *.LJTI
 289 }
 290
 291
 292 define void @optimal_jump_table1(i32 %x) {
 293 entry:
 294   switch i32 %x, label %return [
 295     i32 0,  label %bb0
 296     i32 5,  label %bb1
 297     i32 6,  label %bb2
 298     i32 12, label %bb3
 299     i32 13, label %bb4
 300     i32 15, label %bb5
 301   ]
 302 bb0: tail call void @g(i32 0) br label %return
 303 bb1: tail call void @g(i32 1) br label %return
 304 bb2: tail call void @g(i32 2) br label %return
 305 bb3: tail call void @g(i32 3) br label %return
 306 bb4: tail call void @g(i32 4) br label %return
 307 bb5: tail call void @g(i32 5) br label %return
 308 return: ret void
 309
 310 ; Splitting in the largest gap (between 6 and 12) would yield suboptimal result.
 311 ; Expecting a jump table from 5 to 15.
 312 ; CHECK-LABEL: optimal_jump_table1
 313 ; CHECK: leal -5
 314 ; CHECK: cmpl $10
 315 ; CHECK: jmpq *.LJTI
 316
 317 ; At -O0, we don't build jump tables for only parts of a switch.
 318 ; NOOPT-LABEL: optimal_jump_table1
 319 ; NOOPT: testl %edi, %edi
 320 ; NOOPT: je
 321 ; NOOPT: subl $5, [[REG:%e[abcd][xi]]]
 322 ; NOOPT: je
 323 ; NOOPT: subl $6, [[REG]]
 324 ; NOOPT: je
 325 ; NOOPT: subl $12, [[REG]]
 326 ; NOOPT: je
 327 ; NOOPT: subl $13, [[REG]]
 328 ; NOOPT: je
 329 ; NOOPT: subl $15, [[REG]]
 330 ; NOOPT: je
 331 }
 332
 333
 334 define void @optimal_jump_table2(i32 %x) {
 335 entry:
 336   switch i32 %x, label %return [
 337     i32 0,  label %bb0
 338     i32 1,  label %bb1
 339     i32 2,  label %bb2
 340     i32 9,  label %bb3
 341     i32 14, label %bb4
 342     i32 15, label %bb5
 343   ]
 344 bb0: tail call void @g(i32 0) br label %return
 345 bb1: tail call void @g(i32 1) br label %return
 346 bb2: tail call void @g(i32 2) br label %return
 347 bb3: tail call void @g(i32 3) br label %return
 348 bb4: tail call void @g(i32 4) br label %return
 349 bb5: tail call void @g(i32 5) br label %return
 350 return: ret void
 351
 352 ; Partitioning the cases to the minimum number of dense sets is not good enough.
 353 ; This can be partitioned as {0,1,2,9},{14,15} or {0,1,2},{9,14,15}. The former
 354 ; should be preferred. Expecting a table from 0-9.
 355 ; CHECK-LABEL: optimal_jump_table2
 356 ; CHECK: cmpl $9
 357 ; CHECK: jmpq *.LJTI
 358 }
 359
 360
 361 define void @optimal_jump_table3(i32 %x) {
 362 entry:
 363   switch i32 %x, label %return [
 364     i32 1,  label %bb0
 365     i32 2,  label %bb1
 366     i32 3,  label %bb2
 367     i32 10, label %bb3
 368     i32 13, label %bb0
 369     i32 14, label %bb1
 370     i32 15, label %bb2
 371     i32 20, label %bb3
 372     i32 25, label %bb4
 373   ]
 374 bb0: tail call void @g(i32 0) br label %return
 375 bb1: tail call void @g(i32 1) br label %return
 376 bb2: tail call void @g(i32 2) br label %return
 377 bb3: tail call void @g(i32 3) br label %return
 378 bb4: tail call void @g(i32 4) br label %return
 379 return: ret void
 380
 381 ; Splitting to maximize left-right density sum and gap size would split this
 382 ; between 3 and 10, and then between 20 and 25. It's better to build a table
 383 ; from 1-20.
 384 ; CHECK-LABEL: optimal_jump_table3
 385 ; CHECK: leal -1
 386 ; CHECK: cmpl $19
 387 ; CHECK: jmpq *.LJTI
 388 }
 389
 390 %struct.S = type { %struct.S*, i32 }
 391 define void @phi_node_trouble(%struct.S* %s) {
 392 entry:
 393   br label %header
 394 header:
 395   %ptr = phi %struct.S* [ %s, %entry ], [ %next, %loop ]
 396   %bool = icmp eq %struct.S* %ptr, null
 397   br i1 %bool, label %exit, label %loop
 398 loop:
 399   %nextptr = getelementptr inbounds %struct.S, %struct.S* %ptr, i64 0, i32 0
 400   %next = load %struct.S*, %struct.S** %nextptr
 401   %xptr = getelementptr inbounds %struct.S, %struct.S* %next, i64 0, i32 1
 402   %x = load i32, i32* %xptr
 403   switch i32 %x, label %exit [
 404     i32 4, label %header
 405     i32 36, label %exit2
 406     i32 69, label %exit2
 407     i32 25, label %exit2
 408   ]
 409 exit:
 410   ret void
 411 exit2:
 412   ret void
 413
 414 ; This will be lowered to a comparison with 4 and then bit tests. Make sure
 415 ; that the phi node in %header gets a value from the comparison block.
 416 ; CHECK-LABEL: phi_node_trouble
 417 ; CHECK: movq (%[[REG1:[a-z]+]]), %[[REG1]]
 418 ; CHECK: movl 8(%[[REG1]]), %[[REG2:[a-z]+]]
 419 ; CHECK: cmpl $4, %[[REG2]]
 420 }
 421
 422
 423 define void @default_only(i32 %x) {
 424 entry:
 425   br label %sw
 426 return:
 427   ret void
 428 sw:
 429   switch i32 %x, label %return [
 430   ]
 431
 432 ; Branch directly to the default.
 433 ; (In optimized builds the switch is removed earlier.)
 434 ; NOOPT-LABEL: default_only
 435 ; NOOPT: .LBB[[L:[A-Z0-9_]+]]:
 436 ; NOOPT-NEXT: retq
 437 ; NOOPT: jmp .LBB[[L]]
 438 }
 439
 440
 441 define void @int_max_table_cluster(i8 %x) {
 442 entry:
 443   switch i8 %x, label %return [
 444     i8 0, label %bb0 i8 1, label %bb0 i8 2, label %bb0 i8 3, label %bb0
 445     i8 4, label %bb0 i8 5, label %bb0 i8 6, label %bb0 i8 7, label %bb0
 446     i8 8, label %bb0 i8 9, label %bb0 i8 10, label %bb0 i8 11, label %bb0
 447     i8 12, label %bb0 i8 13, label %bb0 i8 14, label %bb0 i8 15, label %bb0
 448     i8 16, label %bb0 i8 17, label %bb0 i8 18, label %bb0 i8 19, label %bb0
 449     i8 20, label %bb0 i8 21, label %bb0 i8 22, label %bb0 i8 23, label %bb0
 450     i8 24, label %bb0 i8 25, label %bb0 i8 26, label %bb0 i8 27, label %bb0
 451     i8 28, label %bb0 i8 29, label %bb0 i8 30, label %bb0 i8 31, label %bb0
 452     i8 32, label %bb0 i8 33, label %bb0 i8 34, label %bb0 i8 35, label %bb0
 453     i8 36, label %bb0 i8 37, label %bb0 i8 38, label %bb0 i8 39, label %bb0
 454     i8 40, label %bb0 i8 41, label %bb0 i8 42, label %bb0 i8 43, label %bb0
 455     i8 44, label %bb0 i8 45, label %bb0 i8 46, label %bb0 i8 47, label %bb0
 456     i8 48, label %bb0 i8 49, label %bb0 i8 50, label %bb0 i8 51, label %bb0
 457     i8 52, label %bb0 i8 53, label %bb0 i8 54, label %bb0 i8 55, label %bb0
 458     i8 56, label %bb0 i8 57, label %bb0 i8 58, label %bb0 i8 59, label %bb0
 459     i8 60, label %bb0 i8 61, label %bb0 i8 62, label %bb0 i8 63, label %bb0
 460     i8 64, label %bb0 i8 65, label %bb0 i8 66, label %bb0 i8 67, label %bb0
 461     i8 68, label %bb0 i8 69, label %bb0 i8 70, label %bb0 i8 71, label %bb0
 462     i8 72, label %bb0 i8 73, label %bb0 i8 74, label %bb0 i8 75, label %bb0
 463     i8 76, label %bb0 i8 77, label %bb0 i8 78, label %bb0 i8 79, label %bb0
 464     i8 80, label %bb0 i8 81, label %bb0 i8 82, label %bb0 i8 83, label %bb0
 465     i8 84, label %bb0 i8 85, label %bb0 i8 86, label %bb0 i8 87, label %bb0
 466     i8 88, label %bb0 i8 89, label %bb0 i8 90, label %bb0 i8 91, label %bb0
 467     i8 92, label %bb0 i8 93, label %bb0 i8 94, label %bb0 i8 95, label %bb0
 468     i8 96, label %bb0 i8 97, label %bb0 i8 98, label %bb0 i8 99, label %bb0
 469     i8 100, label %bb0 i8 101, label %bb0 i8 102, label %bb0 i8 103, label %bb0
 470     i8 104, label %bb0 i8 105, label %bb0 i8 106, label %bb0 i8 107, label %bb0
 471     i8 108, label %bb0 i8 109, label %bb0 i8 110, label %bb0 i8 111, label %bb0
 472     i8 112, label %bb0 i8 113, label %bb0 i8 114, label %bb0 i8 115, label %bb0
 473     i8 116, label %bb0 i8 117, label %bb0 i8 118, label %bb0 i8 119, label %bb0
 474     i8 120, label %bb0 i8 121, label %bb0 i8 122, label %bb0 i8 123, label %bb0
 475     i8 124, label %bb0 i8 125, label %bb0 i8 126, label %bb0 i8 127, label %bb0
 476     i8 -64, label %bb1 i8 -63, label %bb1 i8 -62, label %bb1 i8 -61, label %bb1
 477     i8 -60, label %bb1 i8 -59, label %bb1 i8 -58, label %bb1 i8 -57, label %bb1
 478     i8 -56, label %bb1 i8 -55, label %bb1 i8 -54, label %bb1 i8 -53, label %bb1
 479     i8 -52, label %bb1 i8 -51, label %bb1 i8 -50, label %bb1 i8 -49, label %bb1
 480     i8 -48, label %bb1 i8 -47, label %bb1 i8 -46, label %bb1 i8 -45, label %bb1
 481     i8 -44, label %bb1 i8 -43, label %bb1 i8 -42, label %bb1 i8 -41, label %bb1
 482     i8 -40, label %bb1 i8 -39, label %bb1 i8 -38, label %bb1 i8 -37, label %bb1
 483     i8 -36, label %bb1 i8 -35, label %bb1 i8 -34, label %bb1 i8 -33, label %bb1
 484     i8 -32, label %bb2 i8 -31, label %bb2 i8 -30, label %bb2 i8 -29, label %bb2
 485     i8 -28, label %bb2 i8 -27, label %bb2 i8 -26, label %bb2 i8 -25, label %bb2
 486     i8 -24, label %bb2 i8 -23, label %bb2 i8 -22, label %bb2 i8 -21, label %bb2
 487     i8 -20, label %bb2 i8 -19, label %bb2 i8 -18, label %bb2 i8 -17, label %bb2
 488     i8 -16, label %bb3 i8 -15, label %bb3 i8 -14, label %bb3 i8 -13, label %bb3
 489     i8 -12, label %bb3 i8 -11, label %bb3 i8 -10, label %bb3 i8 -9, label %bb3
 490   ]
 491 bb0: tail call void @g(i32 0) br label %return
 492 bb1: tail call void @g(i32 1) br label %return
 493 bb2: tail call void @g(i32 1) br label %return
 494 bb3: tail call void @g(i32 1) br label %return
 495 return: ret void
 496
 497 ; Don't infloop on jump tables where the upper bound is the max value of the
 498 ; input type (in this case 127).
 499 ; CHECK-LABEL: int_max_table_cluster
 500 ; CHECK: jmpq *.LJTI
 501 }
 502
 503
 504 define void @bt_order_by_weight(i32 %x) {
 505 entry:
 506   switch i32 %x, label %return [
 507     i32 0, label %bb0
 508     i32 3, label %bb0
 509     i32 6, label %bb0
 510     i32 1, label %bb1
 511     i32 4, label %bb1
 512     i32 7, label %bb1
 513     i32 2, label %bb2
 514     i32 5, label %bb2
 515     i32 8, label %bb2
 516     i32 9, label %bb2
 517   ], !prof !1
 518 bb0: tail call void @g(i32 0) br label %return
 519 bb1: tail call void @g(i32 1) br label %return
 520 bb2: tail call void @g(i32 2) br label %return
 521 return: ret void
 522
 523 ; Cases 1,4,7 have a very large branch weight (which shouldn't overflow), so
 524 ; their bit test should come first. 0,3,6 and 2,5,8,9 both have a weight of 12,
 525 ; but the latter set has more cases, so should be tested for earlier.
 526 ; The bit test on 0,3,6 is unnecessary as all cases cover the rage [0, 9].
 527 ; The range check guarantees that cases other than 1,4,7 and 2,5,8,9 must be
 528 ; in 0,3,6.
 529
 530 ; CHECK-LABEL: bt_order_by_weight
 531 ; 146 = 2^1 + 2^4 + 2^7
 532 ; CHECK: movl $146
 533 ; CHECK: btl
 534 ; 292 = 2^2 + 2^5 + 2^8 + 2^9
 535 ; CHECK: movl $804
 536 ; CHECK: btl
 537 ; 73 = 2^0 + 2^3 + 2^6
 538 ; CHECK-NOT: movl $73
 539 ; CHECK-NOT: btl
 540 }
 541
 542 !1 = !{!"branch_weights",
 543        ; Default:
 544        i32 1,
 545        ; Cases 0,3,6:
 546        i32 4, i32 4, i32 4,
 547        ; Cases 1,4,7:
 548        i32 4294967295, i32 2, i32 4294967295,
 549        ; Cases 2,5,8,9:
 550        i32 3, i32 3, i32 3, i32 3}
 551
 552 define void @order_by_weight_and_fallthrough(i32 %x) {
 553 entry:
 554   switch i32 %x, label %return [
 555     i32 100, label %bb1
 556     i32 200, label %bb0
 557     i32 300, label %bb0
 558   ], !prof !2
 559 bb0: tail call void @g(i32 0) br label %return
 560 bb1: tail call void @g(i32 1) br label %return
 561 return: ret void
 562
 563 ; Case 200 has the highest weight and should come first. 100 and 300 have the
 564 ; same weight, but 300 goes to the 'next' block, so should be last.
 565 ; CHECK-LABEL: order_by_weight_and_fallthrough
 566 ; CHECK: cmpl $200
 567 ; CHECK: cmpl $100
 568 ; CHECK: cmpl $300
 569 }
 570
 571 !2 = !{!"branch_weights",
 572        ; Default:
 573        i32 1,
 574        ; Case 100:
 575        i32 10,
 576        ; Case 200:
 577        i32 1000,
 578        ; Case 300:
 579        i32 10}
 580
 581
 582 define void @zero_weight_tree(i32 %x) {
 583 entry:
 584   switch i32 %x, label %return [
 585     i32 0,  label %bb0
 586     i32 10, label %bb1
 587     i32 20, label %bb2
 588     i32 30, label %bb3
 589     i32 40, label %bb4
 590     i32 50, label %bb5
 591   ], !prof !3
 592 bb0: tail call void @g(i32 0) br label %return
 593 bb1: tail call void @g(i32 1) br label %return
 594 bb2: tail call void @g(i32 2) br label %return
 595 bb3: tail call void @g(i32 3) br label %return
 596 bb4: tail call void @g(i32 4) br label %return
 597 bb5: tail call void @g(i32 5) br label %return
 598 return: ret void
 599
 600 ; Make sure to pick a pivot in the middle also with zero-weight cases.
 601 ; CHECK-LABEL: zero_weight_tree
 602 ; CHECK-NOT: cmpl
 603 ; CHECK: cmpl $29
 604 }
 605
 606 !3 = !{!"branch_weights", i32 1, i32 10, i32 0, i32 0, i32 0, i32 0, i32 10}
 607
 608
 609 define void @left_leaning_weight_balanced_tree(i32 %x) {
 610 entry:
 611   switch i32 %x, label %return [
 612     i32 0,  label %bb0
 613     i32 10, label %bb1
 614     i32 20, label %bb2
 615     i32 30, label %bb3
 616     i32 40, label %bb4
 617     i32 50, label %bb5
 618     i32 60, label %bb6
 619     i32 70, label %bb6
 620   ], !prof !4
 621 bb0: tail call void @g(i32 0) br label %return
 622 bb1: tail call void @g(i32 1) br label %return
 623 bb2: tail call void @g(i32 2) br label %return
 624 bb3: tail call void @g(i32 3) br label %return
 625 bb4: tail call void @g(i32 4) br label %return
 626 bb5: tail call void @g(i32 5) br label %return
 627 bb6: tail call void @g(i32 6) br label %return
 628 bb7: tail call void @g(i32 7) br label %return
 629 return: ret void
 630
 631 ; Without branch probabilities, the pivot would be 40, since that would yield
 632 ; equal-sized sub-trees. When taking weights into account, case 70 becomes the
 633 ; pivot. Since there is room for 3 cases in a leaf, cases 50 and 60 are also
 634 ; included in the right-hand side because that doesn't reduce their rank.
 635
 636 ; CHECK-LABEL: left_leaning_weight_balanced_tree
 637 ; CHECK-NOT: cmpl
 638 ; CHECK: cmpl $49
 639 }
 640
 641 !4 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1000}
 642
 643
 644 define void @left_leaning_weight_balanced_tree2(i32 %x) {
 645 entry:
 646   switch i32 %x, label %return [
 647     i32 0,  label %bb0
 648     i32 10, label %bb1
 649     i32 20, label %bb2
 650     i32 30, label %bb3
 651     i32 40, label %bb4
 652     i32 50, label %bb5
 653     i32 60, label %bb6
 654     i32 70, label %bb6
 655   ], !prof !5
 656 bb0: tail call void @g(i32 0) br label %return
 657 bb1: tail call void @g(i32 1) br label %return
 658 bb2: tail call void @g(i32 2) br label %return
 659 bb3: tail call void @g(i32 3) br label %return
 660 bb4: tail call void @g(i32 4) br label %return
 661 bb5: tail call void @g(i32 5) br label %return
 662 bb6: tail call void @g(i32 6) br label %return
 663 bb7: tail call void @g(i32 7) br label %return
 664 return: ret void
 665
 666 ; Same as the previous test, except case 50 has higher rank to the left than it
 667 ; would have on the right. Case 60 would have the same rank on both sides, so is
 668 ; moved into the leaf.
 669
 670 ; CHECK-LABEL: left_leaning_weight_balanced_tree2
 671 ; CHECK-NOT: cmpl
 672 ; CHECK: cmpl $59
 673 }
 674
 675 !5 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 1, i32 90, i32 70, i32 1000}
 676
 677
 678 define void @right_leaning_weight_balanced_tree(i32 %x) {
 679 entry:
 680   switch i32 %x, label %return [
 681     i32 0,  label %bb0
 682     i32 10, label %bb1
 683     i32 20, label %bb2
 684     i32 30, label %bb3
 685     i32 40, label %bb4
 686     i32 50, label %bb5
 687     i32 60, label %bb6
 688     i32 70, label %bb6
 689   ], !prof !6
 690 bb0: tail call void @g(i32 0) br label %return
 691 bb1: tail call void @g(i32 1) br label %return
 692 bb2: tail call void @g(i32 2) br label %return
 693 bb3: tail call void @g(i32 3) br label %return
 694 bb4: tail call void @g(i32 4) br label %return
 695 bb5: tail call void @g(i32 5) br label %return
 696 bb6: tail call void @g(i32 6) br label %return
 697 bb7: tail call void @g(i32 7) br label %return
 698 return: ret void
 699
 700 ; Analogous to left_leaning_weight_balanced_tree.
 701
 702 ; CHECK-LABEL: right_leaning_weight_balanced_tree
 703 ; CHECK-NOT: cmpl
 704 ; CHECK: cmpl $19
 705 }
 706
 707 !6 = !{!"branch_weights", i32 1, i32 1000, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 10}
 708
 709
 710 define void @jump_table_affects_balance(i32 %x) {
 711 entry:
 712   switch i32 %x, label %return [
 713     ; Jump table:
 714     i32 0,  label %bb0
 715     i32 1,  label %bb1
 716     i32 2,  label %bb2
 717     i32 3,  label %bb3
 718
 719     i32 100, label %bb0
 720     i32 200, label %bb1
 721     i32 300, label %bb2
 722   ]
 723 bb0: tail call void @g(i32 0) br label %return
 724 bb1: tail call void @g(i32 1) br label %return
 725 bb2: tail call void @g(i32 2) br label %return
 726 bb3: tail call void @g(i32 3) br label %return
 727 return: ret void
 728
 729 ; CHECK-LABEL: jump_table_affects_balance
 730 ; If the tree were balanced based on number of clusters, {0-3,100} would go on
 731 ; the left and {200,300} on the right. However, the jump table weights as much
 732 ; as its components, so 100 is selected as the pivot.
 733 ; CHECK-NOT: cmpl
 734 ; CHECK: cmpl $99
 735 }
 736
 737
 738 define void @pr23738(i4 %x) {
 739 entry:
 740   switch i4 %x, label %bb0 [
 741     i4 0, label %bb1
 742     i4 1, label %bb1
 743     i4 -5, label %bb1
 744   ]
 745 bb0: tail call void @g(i32 0) br label %return
 746 bb1: tail call void @g(i32 1) br label %return
 747 return: ret void
 748 ; Don't assert due to truncating the bitwidth (64) to i4 when checking
 749 ; that the bit-test range fits in a word.
 750 }
 751
 752
 753 define i32 @pr27135(i32 %i) {
 754 entry:
 755   br i1 undef, label %sw, label %end
 756 sw:
 757   switch i32 %i, label %end [
 758     i32 99,  label %sw.bb
 759     i32 98,  label %sw.bb
 760     i32 101, label %sw.bb
 761     i32 97,  label %sw.bb2
 762     i32 96,  label %sw.bb2
 763     i32 100, label %sw.bb2
 764   ]
 765 sw.bb:
 766   unreachable
 767 sw.bb2:
 768   unreachable
 769 end:
 770   %p = phi i32 [ 1, %sw ], [ 0, %entry ]
 771   ret i32 %p
 772
 773 ; CHECK-LABEL: pr27135:
 774 ; The switch is lowered with bit tests. Since the case range is contiguous, the
 775 ; second bit test is redundant and can be skipped. Check that we don't update
 776 ; the phi node with an incoming value from the MBB of the skipped bit test
 777 ; (-verify-machine-instrs cathces this).
 778 ; CHECK: btl
 779 ; CHECK-NOT: btl
 780 }
 781
 782
 783 define void @range_with_unreachable_fallthrough(i32 %i) {
 784 entry:
 785   switch i32 %i, label %default [
 786     i32 1, label %bb1
 787     i32 2, label %bb1
 788     i32 3, label %bb1
 789     i32 4, label %bb2
 790     i32 5, label %bb2
 791     i32 6, label %bb2
 792   ]
 793 bb1: tail call void @g(i32 0) br label %return
 794 bb2: tail call void @g(i32 1) br label %return
 795 default: unreachable
 796
 797 return:
 798   ret void
 799
 800 ; CHECK-LABEL: range_with_unreachable_fallthrough:
 801 ; Since the default is unreachable, either cluster will be reached.
 802 ; Only one comparison should be emitted.
 803 ; CHECK: cmpl
 804 ; CHECK-NOT: cmpl
 805 ; CHECK: jmp g
 806 ; CHECK: jmp g
 807 }