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 ; Should be lowered as straight compares in -O0 mode.
  20 ; NOOPT-LABEL: basic
  21 ; NOOPT: subl $1, %eax
  22 ; NOOPT: je
  23 ; NOOPT: subl $3, %eax
  24 ; NOOPT: je
  25 ; NOOPT: subl $4, %eax
  26 ; NOOPT: je
  27 ; NOOPT: subl $5, %eax
  28 ; NOOPT: je
  29
  30 ; Jump table otherwise.
  31 ; CHECK-LABEL: basic
  32 ; CHECK: decl
  33 ; CHECK: cmpl $4
  34 ; CHECK: ja
  35 ; CHECK: jmpq *.LJTI
  36 }
  37
  38
  39 define void @simple_ranges(i32 %x) {
  40 entry:
  41   switch i32 %x, label %return [
  42     i32 0, label %bb0
  43     i32 1, label %bb0
  44     i32 2, label %bb0
  45     i32 3, label %bb0
  46     i32 100, label %bb1
  47     i32 101, label %bb1
  48     i32 102, label %bb1
  49     i32 103, label %bb1
  50   ]
  51 bb0: tail call void @g(i32 0) br label %return
  52 bb1: tail call void @g(i32 1) br label %return
  53 return: ret void
  54
  55 ; Should be lowered to two range checks.
  56 ; CHECK-LABEL: simple_ranges
  57 ; CHECK: leal -100
  58 ; CHECK: cmpl $4
  59 ; CHECK: jae
  60 ; CHECK: cmpl $3
  61 ; CHECK: ja
  62
  63 ; We do this even at -O0, because it's cheap and makes codegen faster.
  64 ; NOOPT-LABEL: simple_ranges
  65 ; NOOPT: subl $4
  66 ; NOOPT: jb
  67 ; NOOPT: addl $-100
  68 ; NOOPT: subl $4
  69 ; NOOPT: jb
  70 }
  71
  72
  73 define void @jt_is_better(i32 %x) {
  74 entry:
  75   switch i32 %x, label %return [
  76     i32 0, label %bb0
  77     i32 2, label %bb0
  78     i32 4, label %bb0
  79     i32 1, label %bb1
  80     i32 3, label %bb1
  81     i32 5, label %bb1
  82
  83     i32 6, label %bb2
  84     i32 7, label %bb3
  85     i32 8, label %bb4
  86   ]
  87 bb0: tail call void @g(i32 0) br label %return
  88 bb1: tail call void @g(i32 1) br label %return
  89 bb2: tail call void @g(i32 2) br label %return
  90 bb3: tail call void @g(i32 3) br label %return
  91 bb4: tail call void @g(i32 4) br label %return
  92 return: ret void
  93
  94 ; Cases 0-5 could be lowered with two bit tests,
  95 ; but with 6-8, the whole switch is suitable for a jump table.
  96 ; CHECK-LABEL: jt_is_better
  97 ; CHECK: cmpl $8
  98 ; CHECK: jbe
  99 ; CHECK: jmpq *.LJTI
 100 }
 101
 102
 103 define void @bt_is_better(i32 %x) {
 104 entry:
 105   switch i32 %x, label %return [
 106     i32 0, label %bb0
 107     i32 3, label %bb0
 108     i32 6, label %bb0
 109     i32 1, label %bb1
 110     i32 4, label %bb1
 111     i32 7, label %bb1
 112     i32 2, label %bb2
 113     i32 5, label %bb2
 114     i32 8, label %bb2
 115
 116   ]
 117 bb0: tail call void @g(i32 0) br label %return
 118 bb1: tail call void @g(i32 1) br label %return
 119 bb2: tail call void @g(i32 2) br label %return
 120 return: ret void
 121
 122 ; This could be lowered as a jump table, but bit tests is more efficient.
 123 ; CHECK-LABEL: bt_is_better
 124 ; 73 = 2^0 + 2^3 + 2^6
 125 ; CHECK: movl $73
 126 ; CHECK: btl
 127 ; 146 = 2^1 + 2^4 + 2^7
 128 ; CHECK: movl $146
 129 ; CHECK: btl
 130 ; 292 = 2^2 + 2^5 + 2^8
 131 ; CHECK: movl $292
 132 ; CHECK: btl
 133 }
 134
 135
 136 define void @optimal_pivot1(i32 %x) {
 137 entry:
 138   switch i32 %x, label %return [
 139     i32 100, label %bb0
 140     i32 200, label %bb1
 141     i32 300, label %bb0
 142     i32 400, label %bb1
 143     i32 500, label %bb0
 144     i32 600, label %bb1
 145
 146   ]
 147 bb0: tail call void @g(i32 0) br label %return
 148 bb1: tail call void @g(i32 1) br label %return
 149 return: ret void
 150
 151 ; Should pivot around 400 for two subtrees of equal size.
 152 ; CHECK-LABEL: optimal_pivot1
 153 ; CHECK-NOT: cmpl
 154 ; CHECK: cmpl $399
 155 }
 156
 157
 158 define void @optimal_pivot2(i32 %x) {
 159 entry:
 160   switch i32 %x, label %return [
 161     i32 100, label %bb0   i32 101, label %bb1   i32 102, label %bb2   i32 103, label %bb3
 162     i32 200, label %bb0   i32 201, label %bb1   i32 202, label %bb2   i32 203, label %bb3
 163     i32 300, label %bb0   i32 301, label %bb1   i32 302, label %bb2   i32 303, label %bb3
 164     i32 400, label %bb0   i32 401, label %bb1   i32 402, label %bb2   i32 403, label %bb3
 165
 166   ]
 167 bb0: tail call void @g(i32 0) br label %return
 168 bb1: tail call void @g(i32 1) br label %return
 169 bb2: tail call void @g(i32 2) br label %return
 170 bb3: tail call void @g(i32 3) br label %return
 171 return: ret void
 172
 173 ; Should pivot around 300 for two subtrees with two jump tables each.
 174 ; CHECK-LABEL: optimal_pivot2
 175 ; CHECK-NOT: cmpl
 176 ; CHECK: cmpl $299
 177 ; CHECK: jmpq *.LJTI
 178 ; CHECK: jmpq *.LJTI
 179 ; CHECK: jmpq *.LJTI
 180 ; CHECK: jmpq *.LJTI
 181 }
 182
 183
 184 define void @optimal_jump_table1(i32 %x) {
 185 entry:
 186   switch i32 %x, label %return [
 187     i32 0,  label %bb0
 188     i32 5,  label %bb1
 189     i32 6,  label %bb2
 190     i32 12, label %bb3
 191     i32 13, label %bb4
 192     i32 15, label %bb5
 193   ]
 194 bb0: tail call void @g(i32 0) br label %return
 195 bb1: tail call void @g(i32 1) br label %return
 196 bb2: tail call void @g(i32 2) br label %return
 197 bb3: tail call void @g(i32 3) br label %return
 198 bb4: tail call void @g(i32 4) br label %return
 199 bb5: tail call void @g(i32 5) br label %return
 200 return: ret void
 201
 202 ; Splitting in the largest gap (between 6 and 12) would yield suboptimal result.
 203 ; Expecting a jump table from 5 to 15.
 204 ; CHECK-LABEL: optimal_jump_table1
 205 ; CHECK: leal -5
 206 ; CHECK: cmpl $10
 207 ; CHECK: jmpq *.LJTI
 208 }
 209
 210
 211 define void @optimal_jump_table2(i32 %x) {
 212 entry:
 213   switch i32 %x, label %return [
 214     i32 0,  label %bb0
 215     i32 1,  label %bb1
 216     i32 2,  label %bb2
 217     i32 9,  label %bb3
 218     i32 14, label %bb4
 219     i32 15, label %bb5
 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 bb3: tail call void @g(i32 3) br label %return
 225 bb4: tail call void @g(i32 4) br label %return
 226 bb5: tail call void @g(i32 5) br label %return
 227 return: ret void
 228
 229 ; Partitioning the cases to the minimum number of dense sets is not good enough.
 230 ; This can be partitioned as {0,1,2,9},{14,15} or {0,1,2},{9,14,15}. The former
 231 ; should be preferred. Expecting a table from 0-9.
 232 ; CHECK-LABEL: optimal_jump_table2
 233 ; CHECK: cmpl $9
 234 ; CHECK: jmpq *.LJTI
 235 }
 236
 237
 238 define void @optimal_jump_table3(i32 %x) {
 239 entry:
 240   switch i32 %x, label %return [
 241     i32 1,  label %bb0
 242     i32 2,  label %bb1
 243     i32 3,  label %bb2
 244     i32 10, label %bb3
 245     i32 13, label %bb0
 246     i32 14, label %bb1
 247     i32 15, label %bb2
 248     i32 20, label %bb3
 249     i32 25, label %bb4
 250   ]
 251 bb0: tail call void @g(i32 0) br label %return
 252 bb1: tail call void @g(i32 1) br label %return
 253 bb2: tail call void @g(i32 2) br label %return
 254 bb3: tail call void @g(i32 3) br label %return
 255 bb4: tail call void @g(i32 4) br label %return
 256 return: ret void
 257
 258 ; Splitting to maximize left-right density sum and gap size would split this
 259 ; between 3 and 10, and then between 20 and 25. It's better to build a table
 260 ; from 1-20.
 261 ; CHECK-LABEL: optimal_jump_table3
 262 ; CHECK: leal -1
 263 ; CHECK: cmpl $19
 264 ; CHECK: jmpq *.LJTI
 265 }
 266
 267 %struct.S = type { %struct.S*, i32 }
 268 define void @phi_node_trouble(%struct.S* %s) {
 269 entry:
 270   br label %header
 271 header:
 272   %ptr = phi %struct.S* [ %s, %entry ], [ %next, %loop ]
 273   %bool = icmp eq %struct.S* %ptr, null
 274   br i1 %bool, label %exit, label %loop
 275 loop:
 276   %nextptr = getelementptr inbounds %struct.S, %struct.S* %ptr, i64 0, i32 0
 277   %next = load %struct.S*, %struct.S** %nextptr
 278   %xptr = getelementptr inbounds %struct.S, %struct.S* %next, i64 0, i32 1
 279   %x = load i32, i32* %xptr
 280   switch i32 %x, label %exit [
 281     i32 4, label %header
 282     i32 36, label %exit2
 283     i32 69, label %exit2
 284     i32 25, label %exit2
 285   ]
 286 exit:
 287   ret void
 288 exit2:
 289   ret void
 290
 291 ; This will be lowered to a comparison with 4 and then bit tests. Make sure
 292 ; that the phi node in %header gets a value from the comparison block.
 293 ; CHECK-LABEL: phi_node_trouble
 294 ; CHECK: movq (%[[REG1:[a-z]+]]), %[[REG1]]
 295 ; CHECK: movl 8(%[[REG1]]), %[[REG2:[a-z]+]]
 296 ; CHECK: cmpl $4, %[[REG2]]
 297 }
 298
 299
 300 define void @default_only(i32 %x) {
 301 entry:
 302   br label %sw
 303 return:
 304   ret void
 305 sw:
 306   switch i32 %x, label %return [
 307   ]
 308
 309 ; Branch directly to the default.
 310 ; (In optimized builds the switch is removed earlier.)
 311 ; NOOPT-LABEL: default_only
 312 ; NOOPT: .[[L:[A-Z0-9_]+]]:
 313 ; NOOPT-NEXT: retq
 314 ; NOOPT: jmp .[[L]]
 315 }
 316
 317
 318 define void @int_max_table_cluster(i8 %x) {
 319 entry:
 320   switch i8 %x, label %return [
 321     i8 0, label %bb0 i8 1, label %bb0 i8 2, label %bb0 i8 3, label %bb0
 322     i8 4, label %bb0 i8 5, label %bb0 i8 6, label %bb0 i8 7, label %bb0
 323     i8 8, label %bb0 i8 9, label %bb0 i8 10, label %bb0 i8 11, label %bb0
 324     i8 12, label %bb0 i8 13, label %bb0 i8 14, label %bb0 i8 15, label %bb0
 325     i8 16, label %bb0 i8 17, label %bb0 i8 18, label %bb0 i8 19, label %bb0
 326     i8 20, label %bb0 i8 21, label %bb0 i8 22, label %bb0 i8 23, label %bb0
 327     i8 24, label %bb0 i8 25, label %bb0 i8 26, label %bb0 i8 27, label %bb0
 328     i8 28, label %bb0 i8 29, label %bb0 i8 30, label %bb0 i8 31, label %bb0
 329     i8 32, label %bb0 i8 33, label %bb0 i8 34, label %bb0 i8 35, label %bb0
 330     i8 36, label %bb0 i8 37, label %bb0 i8 38, label %bb0 i8 39, label %bb0
 331     i8 40, label %bb0 i8 41, label %bb0 i8 42, label %bb0 i8 43, label %bb0
 332     i8 44, label %bb0 i8 45, label %bb0 i8 46, label %bb0 i8 47, label %bb0
 333     i8 48, label %bb0 i8 49, label %bb0 i8 50, label %bb0 i8 51, label %bb0
 334     i8 52, label %bb0 i8 53, label %bb0 i8 54, label %bb0 i8 55, label %bb0
 335     i8 56, label %bb0 i8 57, label %bb0 i8 58, label %bb0 i8 59, label %bb0
 336     i8 60, label %bb0 i8 61, label %bb0 i8 62, label %bb0 i8 63, label %bb0
 337     i8 64, label %bb0 i8 65, label %bb0 i8 66, label %bb0 i8 67, label %bb0
 338     i8 68, label %bb0 i8 69, label %bb0 i8 70, label %bb0 i8 71, label %bb0
 339     i8 72, label %bb0 i8 73, label %bb0 i8 74, label %bb0 i8 75, label %bb0
 340     i8 76, label %bb0 i8 77, label %bb0 i8 78, label %bb0 i8 79, label %bb0
 341     i8 80, label %bb0 i8 81, label %bb0 i8 82, label %bb0 i8 83, label %bb0
 342     i8 84, label %bb0 i8 85, label %bb0 i8 86, label %bb0 i8 87, label %bb0
 343     i8 88, label %bb0 i8 89, label %bb0 i8 90, label %bb0 i8 91, label %bb0
 344     i8 92, label %bb0 i8 93, label %bb0 i8 94, label %bb0 i8 95, label %bb0
 345     i8 96, label %bb0 i8 97, label %bb0 i8 98, label %bb0 i8 99, label %bb0
 346     i8 100, label %bb0 i8 101, label %bb0 i8 102, label %bb0 i8 103, label %bb0
 347     i8 104, label %bb0 i8 105, label %bb0 i8 106, label %bb0 i8 107, label %bb0
 348     i8 108, label %bb0 i8 109, label %bb0 i8 110, label %bb0 i8 111, label %bb0
 349     i8 112, label %bb0 i8 113, label %bb0 i8 114, label %bb0 i8 115, label %bb0
 350     i8 116, label %bb0 i8 117, label %bb0 i8 118, label %bb0 i8 119, label %bb0
 351     i8 120, label %bb0 i8 121, label %bb0 i8 122, label %bb0 i8 123, label %bb0
 352     i8 124, label %bb0 i8 125, label %bb0 i8 126, label %bb0 i8 127, label %bb0
 353     i8 -64, label %bb1 i8 -63, label %bb1 i8 -62, label %bb1 i8 -61, label %bb1
 354     i8 -60, label %bb1 i8 -59, label %bb1 i8 -58, label %bb1 i8 -57, label %bb1
 355     i8 -56, label %bb1 i8 -55, label %bb1 i8 -54, label %bb1 i8 -53, label %bb1
 356     i8 -52, label %bb1 i8 -51, label %bb1 i8 -50, label %bb1 i8 -49, label %bb1
 357     i8 -48, label %bb1 i8 -47, label %bb1 i8 -46, label %bb1 i8 -45, label %bb1
 358     i8 -44, label %bb1 i8 -43, label %bb1 i8 -42, label %bb1 i8 -41, label %bb1
 359     i8 -40, label %bb1 i8 -39, label %bb1 i8 -38, label %bb1 i8 -37, label %bb1
 360     i8 -36, label %bb1 i8 -35, label %bb1 i8 -34, label %bb1 i8 -33, label %bb1
 361     i8 -32, label %bb2 i8 -31, label %bb2 i8 -30, label %bb2 i8 -29, label %bb2
 362     i8 -28, label %bb2 i8 -27, label %bb2 i8 -26, label %bb2 i8 -25, label %bb2
 363     i8 -24, label %bb2 i8 -23, label %bb2 i8 -22, label %bb2 i8 -21, label %bb2
 364     i8 -20, label %bb2 i8 -19, label %bb2 i8 -18, label %bb2 i8 -17, label %bb2
 365     i8 -16, label %bb3 i8 -15, label %bb3 i8 -14, label %bb3 i8 -13, label %bb3
 366     i8 -12, label %bb3 i8 -11, label %bb3 i8 -10, label %bb3 i8 -9, label %bb3
 367   ]
 368 bb0: tail call void @g(i32 0) br label %return
 369 bb1: tail call void @g(i32 1) br label %return
 370 bb2: tail call void @g(i32 1) br label %return
 371 bb3: tail call void @g(i32 1) br label %return
 372 return: ret void
 373
 374 ; Don't infloop on jump tables where the upper bound is the max value of the
 375 ; input type (in this case 127).
 376 ; CHECK-LABEL: int_max_table_cluster
 377 ; CHECK: jmpq *.LJTI
 378 }
 379
 380
 381 define void @bt_order_by_weight(i32 %x) {
 382 entry:
 383   switch i32 %x, label %return [
 384     i32 0, label %bb0
 385     i32 3, label %bb0
 386     i32 6, label %bb0
 387     i32 1, label %bb1
 388     i32 4, label %bb1
 389     i32 7, label %bb1
 390     i32 2, label %bb2
 391     i32 5, label %bb2
 392     i32 8, label %bb2
 393     i32 9, label %bb2
 394   ], !prof !1
 395 bb0: tail call void @g(i32 0) br label %return
 396 bb1: tail call void @g(i32 1) br label %return
 397 bb2: tail call void @g(i32 2) br label %return
 398 return: ret void
 399
 400 ; Cases 1,4,7 have a very large branch weight (which shouldn't overflow), so
 401 ; their bit test should come first. 0,3,6 and 2,5,8,9 both have a weight of 12,
 402 ; but the latter set has more cases, so should be tested for earlier.
 403
 404 ; CHECK-LABEL: bt_order_by_weight
 405 ; 146 = 2^1 + 2^4 + 2^7
 406 ; CHECK: movl $146
 407 ; CHECK: btl
 408 ; 292 = 2^2 + 2^5 + 2^8 + 2^9
 409 ; CHECK: movl $804
 410 ; CHECK: btl
 411 ; 73 = 2^0 + 2^3 + 2^6
 412 ; CHECK: movl $73
 413 ; CHECK: btl
 414 }
 415
 416 !1 = !{!"branch_weights",
 417        ; Default:
 418        i32 1,
 419        ; Cases 0,3,6:
 420        i32 4, i32 4, i32 4,
 421        ; Cases 1,4,7:
 422        i32 4294967295, i32 2, i32 4294967295,
 423        ; Cases 2,5,8,9:
 424        i32 3, i32 3, i32 3, i32 3}
 425
 426 define void @order_by_weight_and_fallthrough(i32 %x) {
 427 entry:
 428   switch i32 %x, label %return [
 429     i32 100, label %bb1
 430     i32 200, label %bb0
 431     i32 300, label %bb0
 432   ], !prof !2
 433 bb0: tail call void @g(i32 0) br label %return
 434 bb1: tail call void @g(i32 1) br label %return
 435 return: ret void
 436
 437 ; Case 200 has the highest weight and should come first. 100 and 300 have the
 438 ; same weight, but 300 goes to the 'next' block, so should be last.
 439 ; CHECK-LABEL: order_by_weight_and_fallthrough
 440 ; CHECK: cmpl $200
 441 ; CHECK: cmpl $100
 442 ; CHECK: cmpl $300
 443 }
 444
 445 !2 = !{!"branch_weights",
 446        ; Default:
 447        i32 1,
 448        ; Case 100:
 449        i32 10,
 450        ; Case 200:
 451        i32 1000,
 452        ; Case 300:
 453        i32 10}
 454
 455
 456 define void @zero_weight_tree(i32 %x) {
 457 entry:
 458   switch i32 %x, label %return [
 459     i32 0,  label %bb0
 460     i32 10, label %bb1
 461     i32 20, label %bb2
 462     i32 30, label %bb3
 463     i32 40, label %bb4
 464     i32 50, label %bb5
 465   ], !prof !3
 466 bb0: tail call void @g(i32 0) br label %return
 467 bb1: tail call void @g(i32 1) br label %return
 468 bb2: tail call void @g(i32 2) br label %return
 469 bb3: tail call void @g(i32 3) br label %return
 470 bb4: tail call void @g(i32 4) br label %return
 471 bb5: tail call void @g(i32 5) br label %return
 472 return: ret void
 473
 474 ; Make sure to pick a pivot in the middle also with zero-weight cases.
 475 ; CHECK-LABEL: zero_weight_tree
 476 ; CHECK-NOT: cmpl
 477 ; CHECK: cmpl $29
 478 }
 479
 480 !3 = !{!"branch_weights", i32 1, i32 10, i32 0, i32 0, i32 0, i32 0, i32 10}
 481
 482
 483 define void @left_leaning_weight_balanced_tree(i32 %x) {
 484 entry:
 485   switch i32 %x, label %return [
 486     i32 0,  label %bb0
 487     i32 10, label %bb1
 488     i32 20, label %bb2
 489     i32 30, label %bb3
 490     i32 40, label %bb4
 491     i32 50, label %bb5
 492   ], !prof !4
 493 bb0: tail call void @g(i32 0) br label %return
 494 bb1: tail call void @g(i32 1) br label %return
 495 bb2: tail call void @g(i32 2) br label %return
 496 bb3: tail call void @g(i32 3) br label %return
 497 bb4: tail call void @g(i32 4) br label %return
 498 bb5: tail call void @g(i32 5) br label %return
 499 return: ret void
 500
 501 ; To balance the tree by weight, the pivot is shifted to the right, moving hot
 502 ; cases closer to the root.
 503 ; CHECK-LABEL: left_leaning_weight_balanced_tree
 504 ; CHECK-NOT: cmpl
 505 ; CHECK: cmpl $39
 506 }
 507
 508 !4 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 10, i32 10}
 509
 510
 511 define void @jump_table_affects_balance(i32 %x) {
 512 entry:
 513   switch i32 %x, label %return [
 514     ; Jump table:
 515     i32 0,  label %bb0
 516     i32 1,  label %bb1
 517     i32 2,  label %bb2
 518     i32 3,  label %bb3
 519
 520     i32 100, label %bb0
 521     i32 200, label %bb1
 522     i32 300, label %bb2
 523   ]
 524 bb0: tail call void @g(i32 0) br label %return
 525 bb1: tail call void @g(i32 1) br label %return
 526 bb2: tail call void @g(i32 2) br label %return
 527 bb3: tail call void @g(i32 3) br label %return
 528 return: ret void
 529
 530 ; CHECK-LABEL: jump_table_affects_balance
 531 ; If the tree were balanced based on number of clusters, {0-3,100} would go on
 532 ; the left and {200,300} on the right. However, the jump table weights as much
 533 ; as its components, so 100 is selected as the pivot.
 534 ; CHECK-NOT: cmpl
 535 ; CHECK: cmpl $99
 536 }