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 4declare void @g(i32) 5 6define void @basic(i32 %x) { 7entry: 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 ] 14bb0: tail call void @g(i32 0) br label %return 15bb1: tail call void @g(i32 1) br label %return 16bb2: tail call void @g(i32 1) br label %return 17return: 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 34define void @basic_nojumptable(i32 %x) "no-jump-tables"="true" { 35entry: 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 ] 42bb0: tail call void @g(i32 0) br label %return 43bb1: tail call void @g(i32 1) br label %return 44bb2: tail call void @g(i32 1) br label %return 45return: 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 53define void @basic_nojumptable_false(i32 %x) "no-jump-tables"="false" { 54entry: 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 ] 61bb0: tail call void @g(i32 0) br label %return 62bb1: tail call void @g(i32 1) br label %return 63bb2: tail call void @g(i32 1) br label %return 64return: 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 75define void @simple_ranges(i32 %x) { 76entry: 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 ] 87bb0: tail call void @g(i32 0) br label %return 88bb1: tail call void @g(i32 1) br label %return 89return: 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 111define void @jt_is_better(i32 %x) { 112entry: 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 ] 125bb0: tail call void @g(i32 0) br label %return 126bb1: tail call void @g(i32 1) br label %return 127bb2: tail call void @g(i32 2) br label %return 128bb3: tail call void @g(i32 3) br label %return 129bb4: tail call void @g(i32 4) br label %return 130return: 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 141define void @bt_is_better(i32 %x) { 142entry: 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 ] 154bb0: tail call void @g(i32 0) br label %return 155bb1: tail call void @g(i32 1) br label %return 156bb2: tail call void @g(i32 2) br label %return 157return: 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 176define void @bt_is_better2(i32 %x) { 177entry: 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 ] 188bb0: tail call void @g(i32 0) br label %return 189bb1: tail call void @g(i32 1) br label %return 190bb2: tail call void @g(i32 2) br label %return 191return: 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 209define void @bt_is_better3(i32 %x) { 210entry: 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 ] 221bb0: tail call void @g(i32 0) br label %return 222bb1: tail call void @g(i32 1) br label %return 223bb2: tail call void @g(i32 2) br label %return 224return: 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 244define void @optimal_pivot1(i32 %x) { 245entry: 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 ] 255bb0: tail call void @g(i32 0) br label %return 256bb1: tail call void @g(i32 1) br label %return 257return: 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 266define void @optimal_pivot2(i32 %x) { 267entry: 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 ] 275bb0: tail call void @g(i32 0) br label %return 276bb1: tail call void @g(i32 1) br label %return 277bb2: tail call void @g(i32 2) br label %return 278bb3: tail call void @g(i32 3) br label %return 279return: 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 292define void @optimal_jump_table1(i32 %x) { 293entry: 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 ] 302bb0: tail call void @g(i32 0) br label %return 303bb1: tail call void @g(i32 1) br label %return 304bb2: tail call void @g(i32 2) br label %return 305bb3: tail call void @g(i32 3) br label %return 306bb4: tail call void @g(i32 4) br label %return 307bb5: tail call void @g(i32 5) br label %return 308return: 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 334define void @optimal_jump_table2(i32 %x) { 335entry: 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 ] 344bb0: tail call void @g(i32 0) br label %return 345bb1: tail call void @g(i32 1) br label %return 346bb2: tail call void @g(i32 2) br label %return 347bb3: tail call void @g(i32 3) br label %return 348bb4: tail call void @g(i32 4) br label %return 349bb5: tail call void @g(i32 5) br label %return 350return: 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 361define void @optimal_jump_table3(i32 %x) { 362entry: 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 ] 374bb0: tail call void @g(i32 0) br label %return 375bb1: tail call void @g(i32 1) br label %return 376bb2: tail call void @g(i32 2) br label %return 377bb3: tail call void @g(i32 3) br label %return 378bb4: tail call void @g(i32 4) br label %return 379return: 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 } 391define void @phi_node_trouble(%struct.S* %s) { 392entry: 393 br label %header 394header: 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 398loop: 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 ] 409exit: 410 ret void 411exit2: 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 423define void @default_only(i32 %x) { 424entry: 425 br label %sw 426return: 427 ret void 428sw: 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 441define void @int_max_table_cluster(i8 %x) { 442entry: 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 ] 491bb0: tail call void @g(i32 0) br label %return 492bb1: tail call void @g(i32 1) br label %return 493bb2: tail call void @g(i32 1) br label %return 494bb3: tail call void @g(i32 1) br label %return 495return: 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 504define void @bt_order_by_weight(i32 %x) { 505entry: 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 518bb0: tail call void @g(i32 0) br label %return 519bb1: tail call void @g(i32 1) br label %return 520bb2: tail call void @g(i32 2) br label %return 521return: 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 20, 525; but the latter set has more cases, so should be tested for earlier. The bit 526; test on 0,3,6 is unnecessary as all cases cover the range [0, 9]. The range 527; check guarantees that cases other than 1,4,7 and 2,5,8,9 must be in 0,3,6. 528 529; CHECK-LABEL: bt_order_by_weight 530; 146 = 2^1 + 2^4 + 2^7 531; CHECK: movl $146 532; CHECK: btl 533; 292 = 2^2 + 2^5 + 2^8 + 2^9 534; CHECK: movl $804 535; CHECK: btl 536; 73 = 2^0 + 2^3 + 2^6 537; CHECK-NOT: movl $73 538; CHECK-NOT: btl 539} 540 541!1 = !{!"branch_weights", 542 ; Default: 543 i32 1, 544 ; Cases 0,3,6: 545 i32 0, i32 0, i32 20, 546 ; Cases 1,4,7: 547 i32 4294967295, i32 2, i32 4294967295, 548 ; Cases 2,5,8,9: 549 i32 0, i32 0, i32 0, i32 20} 550 551define void @order_by_weight_and_fallthrough(i32 %x) { 552entry: 553 switch i32 %x, label %return [ 554 i32 100, label %bb1 555 i32 200, label %bb0 556 i32 300, label %bb0 557 ], !prof !2 558bb0: tail call void @g(i32 0) br label %return 559bb1: tail call void @g(i32 1) br label %return 560return: ret void 561 562; Case 200 has the highest weight and should come first. 100 and 300 have the 563; same weight, but 300 goes to the 'next' block, so should be last. 564; CHECK-LABEL: order_by_weight_and_fallthrough 565; CHECK: cmpl $200 566; CHECK: cmpl $100 567; CHECK: cmpl $300 568} 569 570!2 = !{!"branch_weights", 571 ; Default: 572 i32 1, 573 ; Case 100: 574 i32 10, 575 ; Case 200: 576 i32 1000, 577 ; Case 300: 578 i32 10} 579 580 581define void @zero_weight_tree(i32 %x) { 582entry: 583 switch i32 %x, label %return [ 584 i32 0, label %bb0 585 i32 10, label %bb1 586 i32 20, label %bb2 587 i32 30, label %bb3 588 i32 40, label %bb4 589 i32 50, label %bb5 590 ], !prof !3 591bb0: tail call void @g(i32 0) br label %return 592bb1: tail call void @g(i32 1) br label %return 593bb2: tail call void @g(i32 2) br label %return 594bb3: tail call void @g(i32 3) br label %return 595bb4: tail call void @g(i32 4) br label %return 596bb5: tail call void @g(i32 5) br label %return 597return: ret void 598 599; Make sure to pick a pivot in the middle also with zero-weight cases. 600; CHECK-LABEL: zero_weight_tree 601; CHECK-NOT: cmpl 602; CHECK: cmpl $29 603} 604 605!3 = !{!"branch_weights", i32 1, i32 10, i32 0, i32 0, i32 0, i32 0, i32 10} 606 607 608define void @left_leaning_weight_balanced_tree(i32 %x) { 609entry: 610 switch i32 %x, label %return [ 611 i32 0, label %bb0 612 i32 10, label %bb1 613 i32 20, label %bb2 614 i32 30, label %bb3 615 i32 40, label %bb4 616 i32 50, label %bb5 617 i32 60, label %bb6 618 i32 70, label %bb6 619 ], !prof !4 620bb0: tail call void @g(i32 0) br label %return 621bb1: tail call void @g(i32 1) br label %return 622bb2: tail call void @g(i32 2) br label %return 623bb3: tail call void @g(i32 3) br label %return 624bb4: tail call void @g(i32 4) br label %return 625bb5: tail call void @g(i32 5) br label %return 626bb6: tail call void @g(i32 6) br label %return 627bb7: tail call void @g(i32 7) br label %return 628return: ret void 629 630; Without branch probabilities, the pivot would be 40, since that would yield 631; equal-sized sub-trees. When taking weights into account, case 70 becomes the 632; pivot. Since there is room for 3 cases in a leaf, cases 50 and 60 are also 633; included in the right-hand side because that doesn't reduce their rank. 634 635; CHECK-LABEL: left_leaning_weight_balanced_tree 636; CHECK-NOT: cmpl 637; CHECK: cmpl $49 638} 639 640!4 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1000} 641 642 643define void @left_leaning_weight_balanced_tree2(i32 %x) { 644entry: 645 switch i32 %x, label %return [ 646 i32 0, label %bb0 647 i32 10, label %bb1 648 i32 20, label %bb2 649 i32 30, label %bb3 650 i32 40, label %bb4 651 i32 50, label %bb5 652 i32 60, label %bb6 653 i32 70, label %bb6 654 ], !prof !5 655bb0: tail call void @g(i32 0) br label %return 656bb1: tail call void @g(i32 1) br label %return 657bb2: tail call void @g(i32 2) br label %return 658bb3: tail call void @g(i32 3) br label %return 659bb4: tail call void @g(i32 4) br label %return 660bb5: tail call void @g(i32 5) br label %return 661bb6: tail call void @g(i32 6) br label %return 662bb7: tail call void @g(i32 7) br label %return 663return: ret void 664 665; Same as the previous test, except case 50 has higher rank to the left than it 666; would have on the right. Case 60 would have the same rank on both sides, so is 667; moved into the leaf. 668 669; CHECK-LABEL: left_leaning_weight_balanced_tree2 670; CHECK-NOT: cmpl 671; CHECK: cmpl $59 672} 673 674!5 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 1, i32 90, i32 70, i32 1000} 675 676 677define void @right_leaning_weight_balanced_tree(i32 %x) { 678entry: 679 switch i32 %x, label %return [ 680 i32 0, label %bb0 681 i32 10, label %bb1 682 i32 20, label %bb2 683 i32 30, label %bb3 684 i32 40, label %bb4 685 i32 50, label %bb5 686 i32 60, label %bb6 687 i32 70, label %bb6 688 ], !prof !6 689bb0: tail call void @g(i32 0) br label %return 690bb1: tail call void @g(i32 1) br label %return 691bb2: tail call void @g(i32 2) br label %return 692bb3: tail call void @g(i32 3) br label %return 693bb4: tail call void @g(i32 4) br label %return 694bb5: tail call void @g(i32 5) br label %return 695bb6: tail call void @g(i32 6) br label %return 696bb7: tail call void @g(i32 7) br label %return 697return: ret void 698 699; Analogous to left_leaning_weight_balanced_tree. 700 701; CHECK-LABEL: right_leaning_weight_balanced_tree 702; CHECK-NOT: cmpl 703; CHECK: cmpl $19 704} 705 706!6 = !{!"branch_weights", i32 1, i32 1000, i32 1, i32 1, i32 1, i32 1, i32 1, i32 1, i32 10} 707 708 709define void @jump_table_affects_balance(i32 %x) { 710entry: 711 switch i32 %x, label %return [ 712 ; Jump table: 713 i32 0, label %bb0 714 i32 1, label %bb1 715 i32 2, label %bb2 716 i32 3, label %bb3 717 718 i32 100, label %bb0 719 i32 200, label %bb1 720 i32 300, label %bb2 721 ] 722bb0: tail call void @g(i32 0) br label %return 723bb1: tail call void @g(i32 1) br label %return 724bb2: tail call void @g(i32 2) br label %return 725bb3: tail call void @g(i32 3) br label %return 726return: ret void 727 728; CHECK-LABEL: jump_table_affects_balance 729; If the tree were balanced based on number of clusters, {0-3,100} would go on 730; the left and {200,300} on the right. However, the jump table weights as much 731; as its components, so 100 is selected as the pivot. 732; CHECK-NOT: cmpl 733; CHECK: cmpl $99 734} 735 736 737define void @pr23738(i4 %x) { 738entry: 739 switch i4 %x, label %bb0 [ 740 i4 0, label %bb1 741 i4 1, label %bb1 742 i4 -5, label %bb1 743 ] 744bb0: tail call void @g(i32 0) br label %return 745bb1: tail call void @g(i32 1) br label %return 746return: ret void 747; Don't assert due to truncating the bitwidth (64) to i4 when checking 748; that the bit-test range fits in a word. 749} 750 751 752define i32 @pr27135(i32 %i) { 753entry: 754 br i1 undef, label %sw, label %end 755sw: 756 switch i32 %i, label %end [ 757 i32 99, label %sw.bb 758 i32 98, label %sw.bb 759 i32 101, label %sw.bb 760 i32 97, label %sw.bb2 761 i32 96, label %sw.bb2 762 i32 100, label %sw.bb2 763 ] 764sw.bb: 765 unreachable 766sw.bb2: 767 unreachable 768end: 769 %p = phi i32 [ 1, %sw ], [ 0, %entry ] 770 ret i32 %p 771 772; CHECK-LABEL: pr27135: 773; The switch is lowered with bit tests. Since the case range is contiguous, the 774; second bit test is redundant and can be skipped. Check that we don't update 775; the phi node with an incoming value from the MBB of the skipped bit test 776; (-verify-machine-instrs cathces this). 777; CHECK: btl 778; CHECK-NOT: btl 779} 780 781 782define void @range_with_unreachable_fallthrough(i32 %i) { 783entry: 784 switch i32 %i, label %default [ 785 i32 1, label %bb1 786 i32 2, label %bb1 787 i32 3, label %bb1 788 i32 4, label %bb2 789 i32 5, label %bb2 790 i32 6, label %bb2 791 ] 792bb1: tail call void @g(i32 0) br label %return 793bb2: tail call void @g(i32 1) br label %return 794default: unreachable 795 796return: 797 ret void 798 799; CHECK-LABEL: range_with_unreachable_fallthrough: 800; Since the default is unreachable, either cluster will be reached. 801; Only one comparison should be emitted. 802; CHECK: cmpl 803; CHECK-NOT: cmpl 804; CHECK: jmp g 805; CHECK: jmp g 806} 807