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=37603
5
6; Pattern:
7;   x << y >> y
8; Should be transformed into:
9;   x & (-1 >> y)
10
11; ============================================================================ ;
12; Basic positive tests
13; ============================================================================ ;
14
15define i32 @positive_samevar(i32 %x, i32 %y) {
16; CHECK-LABEL: @positive_samevar(
17; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 -1, [[Y:%.*]]
18; CHECK-NEXT:    [[RET:%.*]] = and i32 [[TMP1]], [[X:%.*]]
19; CHECK-NEXT:    ret i32 [[RET]]
20;
21  %tmp0 = shl i32 %x, %y
22  %ret = lshr i32 %tmp0, %y
23  ret i32 %ret
24}
25
26define i32 @positive_sameconst(i32 %x) {
27; CHECK-LABEL: @positive_sameconst(
28; CHECK-NEXT:    [[TMP0:%.*]] = and i32 [[X:%.*]], 134217727
29; CHECK-NEXT:    ret i32 [[TMP0]]
30;
31  %tmp0 = shl i32 %x, 5
32  %ret = lshr i32 %tmp0, 5
33  ret i32 %ret
34}
35
36define i32 @positive_biggerShl(i32 %x) {
37; CHECK-LABEL: @positive_biggerShl(
38; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X:%.*]], 5
39; CHECK-NEXT:    [[RET:%.*]] = and i32 [[TMP1]], 134217696
40; CHECK-NEXT:    ret i32 [[RET]]
41;
42  %tmp0 = shl i32 %x, 10
43  %ret = lshr i32 %tmp0, 5
44  ret i32 %ret
45}
46
47define i32 @positive_biggerLshr(i32 %x) {
48; CHECK-LABEL: @positive_biggerLshr(
49; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 5
50; CHECK-NEXT:    [[RET:%.*]] = and i32 [[TMP1]], 4194303
51; CHECK-NEXT:    ret i32 [[RET]]
52;
53  %tmp0 = shl i32 %x, 5
54  %ret = lshr i32 %tmp0, 10
55  ret i32 %ret
56}
57
58define i32 @positive_biggerLshr_lshrexact(i32 %x) {
59; CHECK-LABEL: @positive_biggerLshr_lshrexact(
60; CHECK-NEXT:    [[TMP1:%.*]] = lshr exact i32 [[X:%.*]], 5
61; CHECK-NEXT:    [[RET:%.*]] = and i32 [[TMP1]], 4194303
62; CHECK-NEXT:    ret i32 [[RET]]
63;
64  %tmp0 = shl i32 %x, 5
65  %ret = lshr exact i32 %tmp0, 10
66  ret i32 %ret
67}
68
69; ============================================================================ ;
70; NUW on the first shift
71; ============================================================================ ;
72
73define i32 @positive_samevar_shlnuw(i32 %x, i32 %y) {
74; CHECK-LABEL: @positive_samevar_shlnuw(
75; CHECK-NEXT:    ret i32 [[X:%.*]]
76;
77  %tmp0 = shl nuw i32 %x, %y
78  %ret = lshr i32 %tmp0, %y ; this one is obviously 'exact'.
79  ret i32 %ret
80}
81
82define i32 @positive_sameconst_shlnuw(i32 %x) {
83; CHECK-LABEL: @positive_sameconst_shlnuw(
84; CHECK-NEXT:    ret i32 [[X:%.*]]
85;
86  %tmp0 = shl nuw i32 %x, 5
87  %ret = lshr i32 %tmp0, 5 ; this one is obviously 'exact'.
88  ret i32 %ret
89}
90
91define i32 @positive_biggerShl_shlnuw(i32 %x) {
92; CHECK-LABEL: @positive_biggerShl_shlnuw(
93; CHECK-NEXT:    [[RET:%.*]] = shl nuw i32 [[X:%.*]], 5
94; CHECK-NEXT:    ret i32 [[RET]]
95;
96  %tmp0 = shl nuw i32 %x, 10
97  %ret = lshr i32 %tmp0, 5 ; this one is obviously 'exact'.
98  ret i32 %ret
99}
100
101define i32 @positive_biggerLshr_shlnuw(i32 %x) {
102; CHECK-LABEL: @positive_biggerLshr_shlnuw(
103; CHECK-NEXT:    [[RET:%.*]] = lshr i32 [[X:%.*]], 5
104; CHECK-NEXT:    ret i32 [[RET]]
105;
106  %tmp0 = shl nuw i32 %x, 5
107  %ret = lshr i32 %tmp0, 10
108  ret i32 %ret
109}
110
111define i32 @positive_biggerLshr_shlnuw_lshrexact(i32 %x) {
112; CHECK-LABEL: @positive_biggerLshr_shlnuw_lshrexact(
113; CHECK-NEXT:    [[RET:%.*]] = lshr exact i32 [[X:%.*]], 5
114; CHECK-NEXT:    ret i32 [[RET]]
115;
116  %tmp0 = shl nuw i32 %x, 5
117  %ret = lshr exact i32 %tmp0, 10
118  ret i32 %ret
119}
120
121; ============================================================================ ;
122; Vector
123; ============================================================================ ;
124
125define <2 x i32> @positive_samevar_vec(<2 x i32> %x, <2 x i32> %y) {
126; CHECK-LABEL: @positive_samevar_vec(
127; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i32> <i32 -1, i32 -1>, [[Y:%.*]]
128; CHECK-NEXT:    [[RET:%.*]] = and <2 x i32> [[TMP1]], [[X:%.*]]
129; CHECK-NEXT:    ret <2 x i32> [[RET]]
130;
131  %tmp0 = shl <2 x i32> %x, %y
132  %ret = lshr <2 x i32> %tmp0, %y
133  ret <2 x i32> %ret
134}
135
136; ============================================================================ ;
137; Constant Vectors
138; ============================================================================ ;
139
140define <2 x i32> @positive_sameconst_vec(<2 x i32> %x) {
141; CHECK-LABEL: @positive_sameconst_vec(
142; CHECK-NEXT:    [[TMP0:%.*]] = and <2 x i32> [[X:%.*]], <i32 134217727, i32 134217727>
143; CHECK-NEXT:    ret <2 x i32> [[TMP0]]
144;
145  %tmp0 = shl <2 x i32> %x, <i32 5, i32 5>
146  %ret = lshr <2 x i32> %tmp0, <i32 5, i32 5>
147  ret <2 x i32> %ret
148}
149
150define <3 x i32> @positive_sameconst_vec_undef0(<3 x i32> %x) {
151; CHECK-LABEL: @positive_sameconst_vec_undef0(
152; CHECK-NEXT:    [[TMP0:%.*]] = shl <3 x i32> [[X:%.*]], <i32 5, i32 undef, i32 5>
153; CHECK-NEXT:    [[RET:%.*]] = lshr <3 x i32> [[TMP0]], <i32 5, i32 5, i32 5>
154; CHECK-NEXT:    ret <3 x i32> [[RET]]
155;
156  %tmp0 = shl <3 x i32> %x, <i32 5, i32 undef, i32 5>
157  %ret = lshr <3 x i32> %tmp0, <i32 5, i32 5, i32 5>
158  ret <3 x i32> %ret
159}
160
161define <3 x i32> @positive_sameconst_vec_undef1(<3 x i32> %x) {
162; CHECK-LABEL: @positive_sameconst_vec_undef1(
163; CHECK-NEXT:    [[TMP0:%.*]] = shl <3 x i32> [[X:%.*]], <i32 5, i32 5, i32 5>
164; CHECK-NEXT:    [[RET:%.*]] = lshr <3 x i32> [[TMP0]], <i32 5, i32 undef, i32 5>
165; CHECK-NEXT:    ret <3 x i32> [[RET]]
166;
167  %tmp0 = shl <3 x i32> %x, <i32 5, i32 5, i32 5>
168  %ret = lshr <3 x i32> %tmp0, <i32 5, i32 undef, i32 5>
169  ret <3 x i32> %ret
170}
171
172define <3 x i32> @positive_sameconst_vec_undef2(<3 x i32> %x) {
173; CHECK-LABEL: @positive_sameconst_vec_undef2(
174; CHECK-NEXT:    [[RET:%.*]] = and <3 x i32> [[X:%.*]], <i32 134217727, i32 poison, i32 134217727>
175; CHECK-NEXT:    ret <3 x i32> [[RET]]
176;
177  %tmp0 = shl <3 x i32> %x, <i32 5, i32 undef, i32 5>
178  %ret = lshr <3 x i32> %tmp0, <i32 5, i32 undef, i32 5>
179  ret <3 x i32> %ret
180}
181
182define <2 x i32> @positive_biggerShl_vec(<2 x i32> %x) {
183; CHECK-LABEL: @positive_biggerShl_vec(
184; CHECK-NEXT:    [[TMP1:%.*]] = shl <2 x i32> [[X:%.*]], <i32 5, i32 5>
185; CHECK-NEXT:    [[RET:%.*]] = and <2 x i32> [[TMP1]], <i32 134217696, i32 134217696>
186; CHECK-NEXT:    ret <2 x i32> [[RET]]
187;
188  %tmp0 = shl <2 x i32> %x, <i32 10, i32 10>
189  %ret = lshr <2 x i32> %tmp0, <i32 5, i32 5>
190  ret <2 x i32> %ret
191}
192
193define <3 x i32> @positive_biggerShl_vec_undef0(<3 x i32> %x) {
194; CHECK-LABEL: @positive_biggerShl_vec_undef0(
195; CHECK-NEXT:    [[TMP0:%.*]] = shl <3 x i32> [[X:%.*]], <i32 10, i32 undef, i32 10>
196; CHECK-NEXT:    [[RET:%.*]] = lshr <3 x i32> [[TMP0]], <i32 5, i32 5, i32 5>
197; CHECK-NEXT:    ret <3 x i32> [[RET]]
198;
199  %tmp0 = shl <3 x i32> %x, <i32 10, i32 undef, i32 10>
200  %ret = lshr <3 x i32> %tmp0, <i32 5, i32 5, i32 5>
201  ret <3 x i32> %ret
202}
203
204define <3 x i32> @positive_biggerShl_vec_undef1(<3 x i32> %x) {
205; CHECK-LABEL: @positive_biggerShl_vec_undef1(
206; CHECK-NEXT:    [[TMP0:%.*]] = shl <3 x i32> [[X:%.*]], <i32 10, i32 10, i32 10>
207; CHECK-NEXT:    [[RET:%.*]] = lshr <3 x i32> [[TMP0]], <i32 5, i32 undef, i32 5>
208; CHECK-NEXT:    ret <3 x i32> [[RET]]
209;
210  %tmp0 = shl <3 x i32> %x, <i32 10, i32 10, i32 10>
211  %ret = lshr <3 x i32> %tmp0, <i32 5, i32 undef, i32 5>
212  ret <3 x i32> %ret
213}
214
215define <3 x i32> @positive_biggerShl_vec_undef2(<3 x i32> %x) {
216; CHECK-LABEL: @positive_biggerShl_vec_undef2(
217; CHECK-NEXT:    [[TMP0:%.*]] = shl <3 x i32> [[X:%.*]], <i32 10, i32 undef, i32 10>
218; CHECK-NEXT:    [[RET:%.*]] = lshr <3 x i32> [[TMP0]], <i32 5, i32 undef, i32 5>
219; CHECK-NEXT:    ret <3 x i32> [[RET]]
220;
221  %tmp0 = shl <3 x i32> %x, <i32 10, i32 undef, i32 10>
222  %ret = lshr <3 x i32> %tmp0, <i32 5, i32 undef, i32 5>
223  ret <3 x i32> %ret
224}
225
226define <2 x i32> @positive_biggerLshr_vec(<2 x i32> %x) {
227; CHECK-LABEL: @positive_biggerLshr_vec(
228; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i32> [[X:%.*]], <i32 5, i32 5>
229; CHECK-NEXT:    [[RET:%.*]] = and <2 x i32> [[TMP1]], <i32 4194303, i32 4194303>
230; CHECK-NEXT:    ret <2 x i32> [[RET]]
231;
232  %tmp0 = shl <2 x i32> %x, <i32 5, i32 5>
233  %ret = lshr <2 x i32> %tmp0, <i32 10, i32 10>
234  ret <2 x i32> %ret
235}
236
237define <3 x i32> @positive_biggerLshr_vec_undef0(<3 x i32> %x) {
238; CHECK-LABEL: @positive_biggerLshr_vec_undef0(
239; CHECK-NEXT:    [[TMP0:%.*]] = shl <3 x i32> [[X:%.*]], <i32 5, i32 undef, i32 5>
240; CHECK-NEXT:    [[RET:%.*]] = lshr <3 x i32> [[TMP0]], <i32 10, i32 10, i32 10>
241; CHECK-NEXT:    ret <3 x i32> [[RET]]
242;
243  %tmp0 = shl <3 x i32> %x, <i32 5, i32 undef, i32 5>
244  %ret = lshr <3 x i32> %tmp0, <i32 10, i32 10, i32 10>
245  ret <3 x i32> %ret
246}
247
248define <3 x i32> @positive_biggerLshr_vec_undef1(<3 x i32> %x) {
249; CHECK-LABEL: @positive_biggerLshr_vec_undef1(
250; CHECK-NEXT:    [[TMP0:%.*]] = shl <3 x i32> [[X:%.*]], <i32 5, i32 5, i32 5>
251; CHECK-NEXT:    [[RET:%.*]] = lshr <3 x i32> [[TMP0]], <i32 10, i32 undef, i32 10>
252; CHECK-NEXT:    ret <3 x i32> [[RET]]
253;
254  %tmp0 = shl <3 x i32> %x, <i32 5, i32 5, i32 5>
255  %ret = lshr <3 x i32> %tmp0, <i32 10, i32 undef, i32 10>
256  ret <3 x i32> %ret
257}
258
259define <3 x i32> @positive_biggerLshr_vec_undef2(<3 x i32> %x) {
260; CHECK-LABEL: @positive_biggerLshr_vec_undef2(
261; CHECK-NEXT:    [[TMP0:%.*]] = shl <3 x i32> [[X:%.*]], <i32 5, i32 undef, i32 5>
262; CHECK-NEXT:    [[RET:%.*]] = lshr <3 x i32> [[TMP0]], <i32 10, i32 undef, i32 10>
263; CHECK-NEXT:    ret <3 x i32> [[RET]]
264;
265  %tmp0 = shl <3 x i32> %x, <i32 5, i32 undef, i32 5>
266  %ret = lshr <3 x i32> %tmp0, <i32 10, i32 undef, i32 10>
267  ret <3 x i32> %ret
268}
269
270; ============================================================================ ;
271; Positive multi-use tests with constant
272; ============================================================================ ;
273
274define i32 @positive_sameconst_multiuse(i32 %x) {
275; CHECK-LABEL: @positive_sameconst_multiuse(
276; CHECK-NEXT:    [[TMP0:%.*]] = shl i32 [[X:%.*]], 5
277; CHECK-NEXT:    call void @use32(i32 [[TMP0]])
278; CHECK-NEXT:    [[RET:%.*]] = and i32 [[X]], 134217727
279; CHECK-NEXT:    ret i32 [[RET]]
280;
281  %tmp0 = shl i32 %x, 5
282  call void @use32(i32 %tmp0)
283  %ret = lshr i32 %tmp0, 5
284  ret i32 %ret
285}
286
287define i32 @positive_biggerShl_shlnuw_multiuse(i32 %x) {
288; CHECK-LABEL: @positive_biggerShl_shlnuw_multiuse(
289; CHECK-NEXT:    [[TMP0:%.*]] = shl nuw i32 [[X:%.*]], 10
290; CHECK-NEXT:    call void @use32(i32 [[TMP0]])
291; CHECK-NEXT:    [[RET:%.*]] = shl nuw i32 [[X]], 5
292; CHECK-NEXT:    ret i32 [[RET]]
293;
294  %tmp0 = shl nuw i32 %x, 10
295  call void @use32(i32 %tmp0)
296  %ret = lshr i32 %tmp0, 5
297  ret i32 %ret
298}
299
300define i32 @positive_biggerLshr_shlnuw_multiuse(i32 %x) {
301; CHECK-LABEL: @positive_biggerLshr_shlnuw_multiuse(
302; CHECK-NEXT:    [[TMP0:%.*]] = shl nuw i32 [[X:%.*]], 5
303; CHECK-NEXT:    call void @use32(i32 [[TMP0]])
304; CHECK-NEXT:    [[RET:%.*]] = lshr i32 [[X]], 5
305; CHECK-NEXT:    ret i32 [[RET]]
306;
307  %tmp0 = shl nuw i32 %x, 5
308  call void @use32(i32 %tmp0)
309  %ret = lshr i32 %tmp0, 10
310  ret i32 %ret
311}
312
313; NOTE: creates one extra instruction, but this seems intentional.
314define i32 @positive_biggerShl_multiuse_extrainstr(i32 %x) {
315; CHECK-LABEL: @positive_biggerShl_multiuse_extrainstr(
316; CHECK-NEXT:    [[TMP0:%.*]] = shl i32 [[X:%.*]], 10
317; CHECK-NEXT:    call void @use32(i32 [[TMP0]])
318; CHECK-NEXT:    [[TMP1:%.*]] = shl i32 [[X]], 5
319; CHECK-NEXT:    [[RET:%.*]] = and i32 [[TMP1]], 134217696
320; CHECK-NEXT:    ret i32 [[RET]]
321;
322  %tmp0 = shl i32 %x, 10
323  call void @use32(i32 %tmp0)
324  %ret = lshr i32 %tmp0, 5
325  ret i32 %ret
326}
327
328; NOTE: creates one extra instruction, but this seems intentional.
329define i32 @positive_biggerLshr_multiuse_extrainstr(i32 %x) {
330; CHECK-LABEL: @positive_biggerLshr_multiuse_extrainstr(
331; CHECK-NEXT:    [[TMP0:%.*]] = shl i32 [[X:%.*]], 5
332; CHECK-NEXT:    call void @use32(i32 [[TMP0]])
333; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X]], 5
334; CHECK-NEXT:    [[RET:%.*]] = and i32 [[TMP1]], 4194303
335; CHECK-NEXT:    ret i32 [[RET]]
336;
337  %tmp0 = shl i32 %x, 5
338  call void @use32(i32 %tmp0)
339  %ret = lshr i32 %tmp0, 10
340  ret i32 %ret
341}
342
343; ============================================================================ ;
344; Constant Non-Splat Vectors
345; ============================================================================ ;
346
347define <2 x i32> @positive_biggerShl_vec_nonsplat(<2 x i32> %x) {
348; CHECK-LABEL: @positive_biggerShl_vec_nonsplat(
349; CHECK-NEXT:    [[TMP0:%.*]] = shl <2 x i32> [[X:%.*]], <i32 5, i32 5>
350; CHECK-NEXT:    [[RET:%.*]] = lshr <2 x i32> [[TMP0]], <i32 5, i32 10>
351; CHECK-NEXT:    ret <2 x i32> [[RET]]
352;
353  %tmp0 = shl <2 x i32> %x, <i32 5, i32 5>
354  %ret = lshr <2 x i32> %tmp0, <i32 5, i32 10>
355  ret <2 x i32> %ret
356}
357
358define <2 x i32> @positive_biggerLshl_vec_nonsplat(<2 x i32> %x) {
359; CHECK-LABEL: @positive_biggerLshl_vec_nonsplat(
360; CHECK-NEXT:    [[TMP0:%.*]] = shl <2 x i32> [[X:%.*]], <i32 5, i32 10>
361; CHECK-NEXT:    [[RET:%.*]] = lshr <2 x i32> [[TMP0]], <i32 5, i32 5>
362; CHECK-NEXT:    ret <2 x i32> [[RET]]
363;
364  %tmp0 = shl <2 x i32> %x, <i32 5, i32 10>
365  %ret = lshr <2 x i32> %tmp0, <i32 5, i32 5>
366  ret <2 x i32> %ret
367}
368
369; ============================================================================ ;
370; Negative tests. Should not be folded.
371; ============================================================================ ;
372
373define i32 @negative_twovars(i32 %x, i32 %y, i32 %z) {
374; CHECK-LABEL: @negative_twovars(
375; CHECK-NEXT:    [[TMP0:%.*]] = shl i32 [[X:%.*]], [[Y:%.*]]
376; CHECK-NEXT:    [[RET:%.*]] = lshr i32 [[TMP0]], [[Z:%.*]]
377; CHECK-NEXT:    ret i32 [[RET]]
378;
379  %tmp0 = shl i32 %x, %y
380  %ret = lshr i32 %tmp0, %z ; $z, not %y
381  ret i32 %ret
382}
383
384declare void @use32(i32)
385
386; One use only.
387define i32 @negative_oneuse(i32 %x, i32 %y) {
388; CHECK-LABEL: @negative_oneuse(
389; CHECK-NEXT:    [[TMP0:%.*]] = shl i32 [[X:%.*]], [[Y:%.*]]
390; CHECK-NEXT:    call void @use32(i32 [[TMP0]])
391; CHECK-NEXT:    [[RET:%.*]] = lshr i32 [[TMP0]], [[Y]]
392; CHECK-NEXT:    ret i32 [[RET]]
393;
394  %tmp0 = shl i32 %x, %y
395  call void @use32(i32 %tmp0)
396  %ret = lshr i32 %tmp0, %y
397  ret i32 %ret
398}
399