test/CodeGen/X86/switch.ll

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