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: jb 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: ja 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 } 708
