1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt < %s -instcombine -S | FileCheck %s
3
4; https://bugs.llvm.org/show_bug.cgi?id=38123
5
6; Pattern:
7;   x & ~(-1 << y) == x
8; Should be transformed into:
9;   x u<= ~(-1 << y)
10; That is then later transformed into:
11;   (x >> y) == 0
12
13; ============================================================================ ;
14; Basic positive tests
15; ============================================================================ ;
16
17define i1 @p0(i8 %x, i8 %y) {
18; CHECK-LABEL: @p0(
19; CHECK-NEXT:    [[X_HIGHBITS:%.*]] = lshr i8 [[X:%.*]], [[Y:%.*]]
20; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i8 [[X_HIGHBITS]], 0
21; CHECK-NEXT:    ret i1 [[TMP1]]
22;
23  %t0 = shl i8 -1, %y
24  %t1 = xor i8 %t0, -1
25  %t2 = and i8 %t1, %x
26  %ret = icmp eq i8 %t2, %x
27  ret i1 %ret
28}
29
30; ============================================================================ ;
31; Vector tests
32; ============================================================================ ;
33
34define <2 x i1> @p1_vec(<2 x i8> %x, <2 x i8> %y) {
35; CHECK-LABEL: @p1_vec(
36; CHECK-NEXT:    [[X_HIGHBITS:%.*]] = lshr <2 x i8> [[X:%.*]], [[Y:%.*]]
37; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <2 x i8> [[X_HIGHBITS]], zeroinitializer
38; CHECK-NEXT:    ret <2 x i1> [[TMP1]]
39;
40  %t0 = shl <2 x i8> <i8 -1, i8 -1>, %y
41  %t1 = xor <2 x i8> %t0, <i8 -1, i8 -1>
42  %t2 = and <2 x i8> %t1, %x
43  %ret = icmp eq <2 x i8> %t2, %x
44  ret <2 x i1> %ret
45}
46
47define <3 x i1> @p2_vec_undef0(<3 x i8> %x, <3 x i8> %y) {
48; CHECK-LABEL: @p2_vec_undef0(
49; CHECK-NEXT:    [[X_HIGHBITS:%.*]] = lshr <3 x i8> [[X:%.*]], [[Y:%.*]]
50; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <3 x i8> [[X_HIGHBITS]], zeroinitializer
51; CHECK-NEXT:    ret <3 x i1> [[TMP1]]
52;
53  %t0 = shl <3 x i8> <i8 -1, i8 undef, i8 -1>, %y
54  %t1 = xor <3 x i8> %t0, <i8 -1, i8 -1, i8 -1>
55  %t2 = and <3 x i8> %t1, %x
56  %ret = icmp eq <3 x i8> %t2, %x
57  ret <3 x i1> %ret
58}
59
60define <3 x i1> @p3_vec_undef0(<3 x i8> %x, <3 x i8> %y) {
61; CHECK-LABEL: @p3_vec_undef0(
62; CHECK-NEXT:    [[X_HIGHBITS:%.*]] = lshr <3 x i8> [[X:%.*]], [[Y:%.*]]
63; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <3 x i8> [[X_HIGHBITS]], zeroinitializer
64; CHECK-NEXT:    ret <3 x i1> [[TMP1]]
65;
66  %t0 = shl <3 x i8> <i8 -1, i8 -1, i8 -1>, %y
67  %t1 = xor <3 x i8> %t0, <i8 -1, i8 undef, i8 -1>
68  %t2 = and <3 x i8> %t1, %x
69  %ret = icmp eq <3 x i8> %t2, %x
70  ret <3 x i1> %ret
71}
72
73define <3 x i1> @p4_vec_undef2(<3 x i8> %x, <3 x i8> %y) {
74; CHECK-LABEL: @p4_vec_undef2(
75; CHECK-NEXT:    [[X_HIGHBITS:%.*]] = lshr <3 x i8> [[X:%.*]], [[Y:%.*]]
76; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <3 x i8> [[X_HIGHBITS]], zeroinitializer
77; CHECK-NEXT:    ret <3 x i1> [[TMP1]]
78;
79  %t0 = shl <3 x i8> <i8 -1, i8 undef, i8 -1>, %y
80  %t1 = xor <3 x i8> %t0, <i8 -1, i8 undef, i8 -1>
81  %t2 = and <3 x i8> %t1, %x
82  %ret = icmp eq <3 x i8> %t2, %x
83  ret <3 x i1> %ret
84}
85
86; ============================================================================ ;
87; Commutativity tests.
88; ============================================================================ ;
89
90declare i8 @gen8()
91
92define i1 @c0(i8 %y) {
93; CHECK-LABEL: @c0(
94; CHECK-NEXT:    [[X:%.*]] = call i8 @gen8()
95; CHECK-NEXT:    [[X_HIGHBITS:%.*]] = lshr i8 [[X]], [[Y:%.*]]
96; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i8 [[X_HIGHBITS]], 0
97; CHECK-NEXT:    ret i1 [[TMP1]]
98;
99  %t0 = shl i8 -1, %y
100  %t1 = xor i8 %t0, -1
101  %x = call i8 @gen8()
102  %t2 = and i8 %x, %t1 ; swapped order
103  %ret = icmp eq i8 %t2, %x
104  ret i1 %ret
105}
106
107define i1 @c1(i8 %y) {
108; CHECK-LABEL: @c1(
109; CHECK-NEXT:    [[X:%.*]] = call i8 @gen8()
110; CHECK-NEXT:    [[X_HIGHBITS:%.*]] = lshr i8 [[X]], [[Y:%.*]]
111; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i8 [[X_HIGHBITS]], 0
112; CHECK-NEXT:    ret i1 [[TMP1]]
113;
114  %t0 = shl i8 -1, %y
115  %t1 = xor i8 %t0, -1
116  %x = call i8 @gen8()
117  %t2 = and i8 %t1, %x
118  %ret = icmp eq i8 %x, %t2 ; swapped order
119  ret i1 %ret
120}
121
122define i1 @c2(i8 %y) {
123; CHECK-LABEL: @c2(
124; CHECK-NEXT:    [[X:%.*]] = call i8 @gen8()
125; CHECK-NEXT:    [[X_HIGHBITS:%.*]] = lshr i8 [[X]], [[Y:%.*]]
126; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i8 [[X_HIGHBITS]], 0
127; CHECK-NEXT:    ret i1 [[TMP1]]
128;
129  %t0 = shl i8 -1, %y
130  %t1 = xor i8 %t0, -1
131  %x = call i8 @gen8()
132  %t2 = and i8 %x, %t1 ; swapped order
133  %ret = icmp eq i8 %x, %t2 ; swapped order
134  ret i1 %ret
135}
136
137; ============================================================================ ;
138; One-use tests. We don't care about multi-uses here.
139; ============================================================================ ;
140
141declare void @use8(i8)
142
143define i1 @oneuse0(i8 %x, i8 %y) {
144; CHECK-LABEL: @oneuse0(
145; CHECK-NEXT:    [[T0:%.*]] = shl i8 -1, [[Y:%.*]]
146; CHECK-NEXT:    call void @use8(i8 [[T0]])
147; CHECK-NEXT:    [[X_HIGHBITS:%.*]] = lshr i8 [[X:%.*]], [[Y]]
148; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i8 [[X_HIGHBITS]], 0
149; CHECK-NEXT:    ret i1 [[TMP1]]
150;
151  %t0 = shl i8 -1, %y
152  call void @use8(i8 %t0)
153  %t1 = xor i8 %t0, -1
154  %t2 = and i8 %t1, %x
155  %ret = icmp eq i8 %t2, %x
156  ret i1 %ret
157}
158
159define i1 @oneuse1(i8 %x, i8 %y) {
160; CHECK-LABEL: @oneuse1(
161; CHECK-NEXT:    [[T0:%.*]] = shl i8 -1, [[Y:%.*]]
162; CHECK-NEXT:    [[T1:%.*]] = xor i8 [[T0]], -1
163; CHECK-NEXT:    call void @use8(i8 [[T1]])
164; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge i8 [[T1]], [[X:%.*]]
165; CHECK-NEXT:    ret i1 [[TMP1]]
166;
167  %t0 = shl i8 -1, %y
168  %t1 = xor i8 %t0, -1
169  call void @use8(i8 %t1)
170  %t2 = and i8 %t1, %x
171  %ret = icmp eq i8 %t2, %x
172  ret i1 %ret
173}
174
175define i1 @oneuse2(i8 %x, i8 %y) {
176; CHECK-LABEL: @oneuse2(
177; CHECK-NEXT:    [[T0:%.*]] = shl i8 -1, [[Y:%.*]]
178; CHECK-NEXT:    [[T1:%.*]] = xor i8 [[T0]], -1
179; CHECK-NEXT:    [[T2:%.*]] = and i8 [[T1]], [[X:%.*]]
180; CHECK-NEXT:    call void @use8(i8 [[T2]])
181; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge i8 [[T1]], [[X]]
182; CHECK-NEXT:    ret i1 [[TMP1]]
183;
184  %t0 = shl i8 -1, %y
185  %t1 = xor i8 %t0, -1
186  %t2 = and i8 %t1, %x
187  call void @use8(i8 %t2)
188  %ret = icmp eq i8 %t2, %x
189  ret i1 %ret
190}
191
192define i1 @oneuse3(i8 %x, i8 %y) {
193; CHECK-LABEL: @oneuse3(
194; CHECK-NEXT:    [[T0:%.*]] = shl i8 -1, [[Y:%.*]]
195; CHECK-NEXT:    call void @use8(i8 [[T0]])
196; CHECK-NEXT:    [[T1:%.*]] = xor i8 [[T0]], -1
197; CHECK-NEXT:    call void @use8(i8 [[T1]])
198; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge i8 [[T1]], [[X:%.*]]
199; CHECK-NEXT:    ret i1 [[TMP1]]
200;
201  %t0 = shl i8 -1, %y
202  call void @use8(i8 %t0)
203  %t1 = xor i8 %t0, -1
204  call void @use8(i8 %t1)
205  %t2 = and i8 %t1, %x
206  %ret = icmp eq i8 %t2, %x
207  ret i1 %ret
208}
209
210define i1 @oneuse4(i8 %x, i8 %y) {
211; CHECK-LABEL: @oneuse4(
212; CHECK-NEXT:    [[T0:%.*]] = shl i8 -1, [[Y:%.*]]
213; CHECK-NEXT:    call void @use8(i8 [[T0]])
214; CHECK-NEXT:    [[T1:%.*]] = xor i8 [[T0]], -1
215; CHECK-NEXT:    [[T2:%.*]] = and i8 [[T1]], [[X:%.*]]
216; CHECK-NEXT:    call void @use8(i8 [[T2]])
217; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge i8 [[T1]], [[X]]
218; CHECK-NEXT:    ret i1 [[TMP1]]
219;
220  %t0 = shl i8 -1, %y
221  call void @use8(i8 %t0)
222  %t1 = xor i8 %t0, -1
223  %t2 = and i8 %t1, %x
224  call void @use8(i8 %t2)
225  %ret = icmp eq i8 %t2, %x
226  ret i1 %ret
227}
228
229define i1 @oneuse5(i8 %x, i8 %y) {
230; CHECK-LABEL: @oneuse5(
231; CHECK-NEXT:    [[T0:%.*]] = shl i8 -1, [[Y:%.*]]
232; CHECK-NEXT:    call void @use8(i8 [[T0]])
233; CHECK-NEXT:    [[T1:%.*]] = xor i8 [[T0]], -1
234; CHECK-NEXT:    call void @use8(i8 [[T1]])
235; CHECK-NEXT:    [[T2:%.*]] = and i8 [[T1]], [[X:%.*]]
236; CHECK-NEXT:    call void @use8(i8 [[T2]])
237; CHECK-NEXT:    [[TMP1:%.*]] = icmp uge i8 [[T1]], [[X]]
238; CHECK-NEXT:    ret i1 [[TMP1]]
239;
240  %t0 = shl i8 -1, %y
241  call void @use8(i8 %t0)
242  %t1 = xor i8 %t0, -1
243  call void @use8(i8 %t1)
244  %t2 = and i8 %t1, %x
245  call void @use8(i8 %t2)
246  %ret = icmp eq i8 %t2, %x
247  ret i1 %ret
248}
249
250; ============================================================================ ;
251; Negative tests
252; ============================================================================ ;
253
254define i1 @n0(i8 %x, i8 %y, i8 %notx) {
255; CHECK-LABEL: @n0(
256; CHECK-NEXT:    [[T0:%.*]] = shl i8 -1, [[Y:%.*]]
257; CHECK-NEXT:    [[T1:%.*]] = xor i8 [[T0]], -1
258; CHECK-NEXT:    [[T2:%.*]] = and i8 [[T1]], [[X:%.*]]
259; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[T2]], [[NOTX:%.*]]
260; CHECK-NEXT:    ret i1 [[RET]]
261;
262  %t0 = shl i8 -1, %y
263  %t1 = xor i8 %t0, -1
264  %t2 = and i8 %t1, %x
265  %ret = icmp eq i8 %t2, %notx ; not %x
266  ret i1 %ret
267}
268
269define i1 @n1(i8 %x, i8 %y) {
270; CHECK-LABEL: @n1(
271; CHECK-NEXT:    [[T0:%.*]] = shl i8 1, [[Y:%.*]]
272; CHECK-NEXT:    [[T1:%.*]] = xor i8 [[T0]], -1
273; CHECK-NEXT:    [[T2:%.*]] = and i8 [[T1]], [[X:%.*]]
274; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[T2]], [[X]]
275; CHECK-NEXT:    ret i1 [[RET]]
276;
277  %t0 = shl i8 1, %y ; not -1
278  %t1 = xor i8 %t0, -1
279  %t2 = and i8 %t1, %x
280  %ret = icmp eq i8 %t2, %x
281  ret i1 %ret
282}
283
284define i1 @n2(i8 %x, i8 %y) {
285; CHECK-LABEL: @n2(
286; CHECK-NEXT:    [[T0:%.*]] = shl i8 -1, [[Y:%.*]]
287; CHECK-NEXT:    [[T1:%.*]] = xor i8 [[T0]], 1
288; CHECK-NEXT:    [[T2:%.*]] = and i8 [[T1]], [[X:%.*]]
289; CHECK-NEXT:    [[RET:%.*]] = icmp eq i8 [[T2]], [[X]]
290; CHECK-NEXT:    ret i1 [[RET]]
291;
292  %t0 = shl i8 -1, %y
293  %t1 = xor i8 %t0, 1 ; not -1
294  %t2 = and i8 %t1, %x
295  %ret = icmp eq i8 %t2, %x
296  ret i1 %ret
297}
298