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
18 ; Should be lowered as straight compares in -O0 mode.
20 ; NOOPT: subl $3, %eax
22 ; NOOPT: subl $1, %eax
24 ; NOOPT: subl $4, %eax
26 ; NOOPT: subl $5, %eax
29 ; Jump table otherwise.
38 define void @simple_ranges(i32 %x) {
40 switch i32 %x, label %return [
50 bb0: tail call void @g(i32 0) br label %return
51 bb1: tail call void @g(i32 1) br label %return
54 ; Should be lowered to two range checks.
55 ; CHECK-LABEL: simple_ranges
64 define void @jt_is_better(i32 %x) {
66 switch i32 %x, label %return [
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
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
94 define void @bt_is_better(i32 %x) {
96 switch i32 %x, label %return [
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
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
118 ; 146 = 2^1 + 2^4 + 2^7
121 ; 292 = 2^2 + 2^5 + 2^8
127 define void @optimal_pivot1(i32 %x) {
129 switch i32 %x, label %return [
138 bb0: tail call void @g(i32 0) br label %return
139 bb1: tail call void @g(i32 1) br label %return
142 ; Should pivot around 400 for two subtrees of equal size.
143 ; CHECK-LABEL: optimal_pivot1
149 define void @optimal_pivot2(i32 %x) {
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
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
164 ; Should pivot around 300 for two subtrees with two jump tables each.
165 ; CHECK-LABEL: optimal_pivot2
175 define void @optimal_jump_table1(i32 %x) {
177 switch i32 %x, label %return [
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
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
202 define void @optimal_jump_table2(i32 %x) {
204 switch i32 %x, label %return [
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
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
229 define void @optimal_jump_table3(i32 %x) {
231 switch i32 %x, label %return [
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
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
252 ; CHECK-LABEL: optimal_jump_table3
258 %struct.S = type { %struct.S*, i32 }
259 define void @phi_node_trouble(%struct.S* %s) {
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
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 [
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]]
291 define void @default_only(i32 %x) {
297 switch i32 %x, label %return [
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_]+]]: