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