1; RUN: llc -mtriple=x86_64-- -asm-verbose=false < %s -jump-table-density=40 -switch-peel-threshold=101 | FileCheck %s
2
3; This switch should use bit tests, and the third bit test case is just
4; testing for one possible value, so it doesn't need a bt.
5
6;      CHECK: movabsq $2305843009482129440, %r
7; CHECK-NEXT: btq %rax, %r
8; CHECK-NEXT: jb
9;     CHECK: movl  $671088640, %e
10; CHECK-NEXT: btq %rax, %r
11; CHECK-NEXT: jae
12;      CHECK: testq %rax, %r
13; CHECK-NEXT: j
14
15define void @test(ptr %l) nounwind {
16entry:
17  %l.addr = alloca ptr, align 8                   ; <ptr> [#uses=2]
18  store ptr %l, ptr %l.addr
19  %tmp = load ptr, ptr %l.addr                        ; <ptr> [#uses=1]
20  %tmp1 = load i8, ptr %tmp                           ; <i8> [#uses=1]
21  %conv = sext i8 %tmp1 to i32                    ; <i32> [#uses=1]
22  switch i32 %conv, label %sw.default [
23    i32 62, label %sw.bb
24    i32 60, label %sw.bb
25    i32 38, label %sw.bb2
26    i32 94, label %sw.bb2
27    i32 61, label %sw.bb2
28    i32 33, label %sw.bb4
29  ]
30
31sw.bb:                                            ; preds = %entry, %entry
32  call void @foo(i32 0)
33  br label %sw.epilog
34
35sw.bb2:                                           ; preds = %entry, %entry, %entry
36  call void @foo(i32 1)
37  br label %sw.epilog
38
39sw.bb4:                                           ; preds = %entry
40  call void @foo(i32 3)
41  br label %sw.epilog
42
43sw.default:                                       ; preds = %entry
44  call void @foo(i32 97)
45  br label %sw.epilog
46
47sw.epilog:                                        ; preds = %sw.default, %sw.bb4, %sw.bb2, %sw.bb
48  ret void
49}
50
51declare void @foo(i32)
52
53; Don't zero extend the test operands to pointer type if it can be avoided.
54; rdar://8781238
55define void @test2(i32 %x) nounwind ssp {
56; CHECK-LABEL: test2:
57; CHECK: cmpl $6
58; CHECK: ja
59
60; CHECK-NEXT: movl $91
61; CHECK-NOT: movl
62; CHECK-NEXT: btl
63; CHECK-NEXT: jae
64entry:
65  switch i32 %x, label %if.end [
66    i32 6, label %if.then
67    i32 4, label %if.then
68    i32 3, label %if.then
69    i32 1, label %if.then
70    i32 0, label %if.then
71  ]
72
73if.then:                                          ; preds = %entry, %entry, %entry, %entry, %entry
74  tail call void @bar() nounwind
75  ret void
76
77if.end:                                           ; preds = %entry
78  ret void
79}
80
81declare void @bar()
82
83define void @test3(i32 %x) nounwind {
84; CHECK-LABEL: test3:
85; CHECK: cmpl $5
86; CHECK: ja
87; CHECK: cmpl $4
88; CHECK: je
89  switch i32 %x, label %if.end [
90    i32 0, label %if.then
91    i32 1, label %if.then
92    i32 2, label %if.then
93    i32 3, label %if.then
94    i32 5, label %if.then
95  ]
96if.then:
97  tail call void @bar() nounwind
98  ret void
99if.end:
100  ret void
101}
102
103; Ensure that optimizing for jump tables doesn't needlessly deteriorate the
104; created binary tree search. See PR22262.
105define void @test4(i32 %x, ptr %y) {
106; CHECK-LABEL: test4:
107
108entry:
109  switch i32 %x, label %sw.default [
110    i32 10, label %sw.bb
111    i32 20, label %sw.bb1
112    i32 30, label %sw.bb2
113    i32 40, label %sw.bb3
114    i32 50, label %sw.bb4
115    i32 60, label %sw.bb5
116  ]
117sw.bb:
118  store i32 1, ptr %y
119  br label %sw.epilog
120sw.bb1:
121  store i32 2, ptr %y
122  br label %sw.epilog
123sw.bb2:
124  store i32 3, ptr %y
125  br label %sw.epilog
126sw.bb3:
127  store i32 4, ptr %y
128  br label %sw.epilog
129sw.bb4:
130  store i32 5, ptr %y
131  br label %sw.epilog
132sw.bb5:
133  store i32 6, ptr %y
134  br label %sw.epilog
135sw.default:
136  store i32 7, ptr %y
137  br label %sw.epilog
138sw.epilog:
139  ret void
140
141; The balanced binary switch here would start with a comparison against 39, but
142; it is currently starting with 29 because of the density-sum heuristic.
143; CHECK: cmpl $39
144; CHECK: jg
145; CHECK: cmpl $10
146; CHECK: je
147; CHECK: cmpl $20
148; CHECK: je
149; CHECK: cmpl $30
150; CHECK: jne
151; CHECK: cmpl $40
152; CHECK: je
153; CHECK: cmpl $50
154; CHECK: je
155; CHECK: cmpl $60
156; CHECK: jne
157}
158
159
160; Omit the range check when the default case is unreachable, see PR43129.
161declare void @g(i32)
162define void @test5(i32 %x) {
163
164; CHECK-LABEL: test5
165; CHECK-NOT: cmp
166
167; 73 = 2^0 + 2^3 + 2^6
168; CHECK:      movl $73
169; CHECK-NEXT: btl
170; CHECK-NEXT: jb
171
172; 146 = 2^1 + 2^4 + 2^7
173; CHECK-NEXT: movl $146
174; CHECK-NEXT: btl
175; CHECK-NEXT: jae
176
177
178entry:
179  switch i32 %x, label %return [
180    i32 0, label %bb0
181    i32 3, label %bb0
182    i32 6, label %bb0
183
184    i32 1, label %bb1
185    i32 4, label %bb1
186    i32 7, label %bb1
187
188    i32 2, label %bb2
189    i32 5, label %bb2
190    i32 8, label %bb2
191  ]
192bb0: tail call void @g(i32 0) br label %return
193bb1: tail call void @g(i32 1) br label %return
194bb2: tail call void @g(i32 2) br label %return
195return: unreachable
196}
197