5bacd90793081451b33d0a5f7af89bd7949e101c
[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 %bb0
13   ]
14 bb0: tail call void @g(i32 0) br label %return
15 bb1: tail call void @g(i32 1) br label %return
16 return: 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
38 define void @simple_ranges(i32 %x) {
39 entry:
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   ]
50 bb0: tail call void @g(i32 0) br label %return
51 bb1: tail call void @g(i32 1) br label %return
52 return: 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
64 define void @jt_is_better(i32 %x) {
65 entry:
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   ]
78 bb0: tail call void @g(i32 0) br label %return
79 bb1: tail call void @g(i32 1) br label %return
80 bb2: tail call void @g(i32 2) br label %return
81 bb3: tail call void @g(i32 3) br label %return
82 bb4: tail call void @g(i32 4) br label %return
83 return: 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
94 define void @bt_is_better(i32 %x) {
95 entry:
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   ]
108 bb0: tail call void @g(i32 0) br label %return
109 bb1: tail call void @g(i32 1) br label %return
110 bb2: tail call void @g(i32 2) br label %return
111 return: 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
127 define void @optimal_pivot1(i32 %x) {
128 entry:
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   ]
138 bb0: tail call void @g(i32 0) br label %return
139 bb1: tail call void @g(i32 1) br label %return
140 return: 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
149 define void @optimal_pivot2(i32 %x) {
150 entry:
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   ]
158 bb0: tail call void @g(i32 0) br label %return
159 bb1: tail call void @g(i32 1) br label %return
160 bb2: tail call void @g(i32 2) br label %return
161 bb3: tail call void @g(i32 3) br label %return
162 return: 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
175 define void @optimal_jump_table1(i32 %x) {
176 entry:
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   ]
185 bb0: tail call void @g(i32 0) br label %return
186 bb1: tail call void @g(i32 1) br label %return
187 bb2: tail call void @g(i32 2) br label %return
188 bb3: tail call void @g(i32 3) br label %return
189 bb4: tail call void @g(i32 4) br label %return
190 bb5: tail call void @g(i32 5) br label %return
191 return: 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
202 define void @optimal_jump_table2(i32 %x) {
203 entry:
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   ]
212 bb0: tail call void @g(i32 0) br label %return
213 bb1: tail call void @g(i32 1) br label %return
214 bb2: tail call void @g(i32 2) br label %return
215 bb3: tail call void @g(i32 3) br label %return
216 bb4: tail call void @g(i32 4) br label %return
217 bb5: tail call void @g(i32 5) br label %return
218 return: 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
229 define void @optimal_jump_table3(i32 %x) {
230 entry:
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   ]
242 bb0: tail call void @g(i32 0) br label %return
243 bb1: tail call void @g(i32 1) br label %return
244 bb2: tail call void @g(i32 2) br label %return
245 bb3: tail call void @g(i32 3) br label %return
246 bb4: tail call void @g(i32 4) br label %return
247 return: 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 }
259 define void @phi_node_trouble(%struct.S* %s) {
260 entry:
261   br label %header
262 header:
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
266 loop:
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   ]
277 exit:
278   ret void
279 exit2:
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 }