66a739c8470c43f3e4e5e54d9fedaedb281aca89
[oota-llvm.git] / 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 }