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
6 define void @basic(i32 %x) {
8 switch i32 %x, label %return [
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
19 ; Should be lowered as straight compares in -O0 mode.
21 ; NOOPT: subl $1, %eax
23 ; NOOPT: subl $3, %eax
25 ; NOOPT: subl $4, %eax
27 ; NOOPT: subl $5, %eax
30 ; Jump table otherwise.
39 define void @simple_ranges(i32 %x) {
41 switch i32 %x, label %return [
51 bb0: tail call void @g(i32 0) br label %return
52 bb1: tail call void @g(i32 1) br label %return
55 ; Should be lowered to two range checks.
56 ; CHECK-LABEL: simple_ranges
63 ; We do this even at -O0, because it's cheap and makes codegen faster.
64 ; NOOPT-LABEL: simple_ranges
73 define void @jt_is_better(i32 %x) {
75 switch i32 %x, label %return [
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
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
103 define void @bt_is_better(i32 %x) {
105 switch i32 %x, label %return [
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
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
127 ; 146 = 2^1 + 2^4 + 2^7
130 ; 292 = 2^2 + 2^5 + 2^8
136 define void @optimal_pivot1(i32 %x) {
138 switch i32 %x, label %return [
147 bb0: tail call void @g(i32 0) br label %return
148 bb1: tail call void @g(i32 1) br label %return
151 ; Should pivot around 400 for two subtrees of equal size.
152 ; CHECK-LABEL: optimal_pivot1
158 define void @optimal_pivot2(i32 %x) {
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
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
173 ; Should pivot around 300 for two subtrees with two jump tables each.
174 ; CHECK-LABEL: optimal_pivot2
184 define void @optimal_jump_table1(i32 %x) {
186 switch i32 %x, label %return [
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
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
211 define void @optimal_jump_table2(i32 %x) {
213 switch i32 %x, label %return [
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
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
238 define void @optimal_jump_table3(i32 %x) {
240 switch i32 %x, label %return [
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
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
261 ; CHECK-LABEL: optimal_jump_table3
267 %struct.S = type { %struct.S*, i32 }
268 define void @phi_node_trouble(%struct.S* %s) {
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
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 [
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]]
300 define void @default_only(i32 %x) {
306 switch i32 %x, label %return [
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_]+]]:
318 define void @int_max_table_cluster(i8 %x) {
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
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
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
381 define void @bt_order_by_weight(i32 %x) {
383 switch i32 %x, label %return [
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
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.
404 ; CHECK-LABEL: bt_order_by_weight
405 ; 146 = 2^1 + 2^4 + 2^7
408 ; 292 = 2^2 + 2^5 + 2^8 + 2^9
411 ; 73 = 2^0 + 2^3 + 2^6
416 !1 = !{!"branch_weights",
422 i32 4294967295, i32 2, i32 4294967295,
424 i32 3, i32 3, i32 3, i32 3}
426 define void @order_by_weight_and_fallthrough(i32 %x) {
428 switch i32 %x, label %return [
433 bb0: tail call void @g(i32 0) br label %return
434 bb1: tail call void @g(i32 1) br label %return
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
445 !2 = !{!"branch_weights",
456 define void @zero_weight_tree(i32 %x) {
458 switch i32 %x, label %return [
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
474 ; Make sure to pick a pivot in the middle also with zero-weight cases.
475 ; CHECK-LABEL: zero_weight_tree
480 !3 = !{!"branch_weights", i32 1, i32 10, i32 0, i32 0, i32 0, i32 0, i32 10}
483 define void @left_leaning_weight_balanced_tree(i32 %x) {
485 switch i32 %x, label %return [
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
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
508 !4 = !{!"branch_weights", i32 1, i32 10, i32 1, i32 1, i32 1, i32 10, i32 10}
511 define void @jump_table_affects_balance(i32 %x) {
513 switch i32 %x, label %return [
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
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.
539 define void @pr23738(i4 %x) {
541 switch i4 %x, label %bb0 [
546 bb0: tail call void @g(i32 0) br label %return
547 bb1: tail call void @g(i32 1) br label %return
549 ; Don't assert due to truncating the bitwidth (64) to i4 when checking
550 ; that the bit-test range fits in a word.