xref: /llvm-project/llvm/test/Transforms/InstCombine/lshr.ll (revision 295d6b18f77fc67c186c031204a82ff82cf59daa) 
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt -passes=instcombine -S < %s | FileCheck %s
3
4target datalayout = "e-m:e-i64:64-n8:16:32:64"
5
6declare i32 @llvm.bswap.i32(i32)
7declare i128 @llvm.bswap.i128(i128)
8declare <2 x i64> @llvm.bswap.v2i64(<2 x i64>)
9declare i32 @llvm.cttz.i32(i32, i1) nounwind readnone
10declare i32 @llvm.ctlz.i32(i32, i1) nounwind readnone
11declare i32 @llvm.ctpop.i32(i32) nounwind readnone
12declare <2 x i8> @llvm.cttz.v2i8(<2 x i8>, i1) nounwind readnone
13declare <2 x i8> @llvm.ctlz.v2i8(<2 x i8>, i1) nounwind readnone
14declare <2 x i8> @llvm.ctpop.v2i8(<2 x i8>) nounwind readnone
15
16declare void @use(i32)
17declare void @usevec(<3 x i14>)
18
19define i32 @lshr_ctlz_zero_is_not_undef(i32 %x) {
20; CHECK-LABEL: @lshr_ctlz_zero_is_not_undef(
21; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[X:%.*]], 0
22; CHECK-NEXT:    [[SH:%.*]] = zext i1 [[TMP1]] to i32
23; CHECK-NEXT:    ret i32 [[SH]]
24;
25  %ct = call i32 @llvm.ctlz.i32(i32 %x, i1 false)
26  %sh = lshr i32 %ct, 5
27  ret i32 %sh
28}
29
30define i32 @lshr_cttz_zero_is_not_undef(i32 %x) {
31; CHECK-LABEL: @lshr_cttz_zero_is_not_undef(
32; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[X:%.*]], 0
33; CHECK-NEXT:    [[SH:%.*]] = zext i1 [[TMP1]] to i32
34; CHECK-NEXT:    ret i32 [[SH]]
35;
36  %ct = call i32 @llvm.cttz.i32(i32 %x, i1 false)
37  %sh = lshr i32 %ct, 5
38  ret i32 %sh
39}
40
41define i32 @lshr_ctpop(i32 %x) {
42; CHECK-LABEL: @lshr_ctpop(
43; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq i32 [[X:%.*]], -1
44; CHECK-NEXT:    [[SH:%.*]] = zext i1 [[TMP1]] to i32
45; CHECK-NEXT:    ret i32 [[SH]]
46;
47  %ct = call i32 @llvm.ctpop.i32(i32 %x)
48  %sh = lshr i32 %ct, 5
49  ret i32 %sh
50}
51
52define <2 x i8> @lshr_ctlz_zero_is_not_undef_splat_vec(<2 x i8> %x) {
53; CHECK-LABEL: @lshr_ctlz_zero_is_not_undef_splat_vec(
54; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <2 x i8> [[X:%.*]], zeroinitializer
55; CHECK-NEXT:    [[SH:%.*]] = zext <2 x i1> [[TMP1]] to <2 x i8>
56; CHECK-NEXT:    ret <2 x i8> [[SH]]
57;
58  %ct = call <2 x i8> @llvm.ctlz.v2i8(<2 x i8> %x, i1 false)
59  %sh = lshr <2 x i8> %ct, <i8 3, i8 3>
60  ret <2 x i8> %sh
61}
62
63define <2 x i8> @lshr_cttz_zero_is_not_undef_splat_vec(<2 x i8> %x) {
64; CHECK-LABEL: @lshr_cttz_zero_is_not_undef_splat_vec(
65; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <2 x i8> [[X:%.*]], zeroinitializer
66; CHECK-NEXT:    [[SH:%.*]] = zext <2 x i1> [[TMP1]] to <2 x i8>
67; CHECK-NEXT:    ret <2 x i8> [[SH]]
68;
69  %ct = call <2 x i8> @llvm.cttz.v2i8(<2 x i8> %x, i1 false)
70  %sh = lshr <2 x i8> %ct, <i8 3, i8 3>
71  ret <2 x i8> %sh
72}
73
74define <2 x i8> @lshr_ctpop_splat_vec(<2 x i8> %x) {
75; CHECK-LABEL: @lshr_ctpop_splat_vec(
76; CHECK-NEXT:    [[TMP1:%.*]] = icmp eq <2 x i8> [[X:%.*]], splat (i8 -1)
77; CHECK-NEXT:    [[SH:%.*]] = zext <2 x i1> [[TMP1]] to <2 x i8>
78; CHECK-NEXT:    ret <2 x i8> [[SH]]
79;
80  %ct = call <2 x i8> @llvm.ctpop.v2i8(<2 x i8> %x)
81  %sh = lshr <2 x i8> %ct, <i8 3, i8 3>
82  ret <2 x i8> %sh
83}
84
85define i32 @lshr_ctlz_zero_is_undef(i32 %x) {
86; CHECK-LABEL: @lshr_ctlz_zero_is_undef(
87; CHECK-NEXT:    ret i32 0
88;
89  %ct = call i32 @llvm.ctlz.i32(i32 %x, i1 true)
90  %sh = lshr i32 %ct, 5
91  ret i32 %sh
92}
93
94define i32 @lshr_cttz_zero_is_undef(i32 %x) {
95; CHECK-LABEL: @lshr_cttz_zero_is_undef(
96; CHECK-NEXT:    ret i32 0
97;
98  %ct = call i32 @llvm.cttz.i32(i32 %x, i1 true)
99  %sh = lshr i32 %ct, 5
100  ret i32 %sh
101}
102
103define <2 x i8> @lshr_ctlz_zero_is_undef_splat_vec(<2 x i8> %x) {
104; CHECK-LABEL: @lshr_ctlz_zero_is_undef_splat_vec(
105; CHECK-NEXT:    ret <2 x i8> zeroinitializer
106;
107  %ct = call <2 x i8> @llvm.ctlz.v2i8(<2 x i8> %x, i1 true)
108  %sh = lshr <2 x i8> %ct, <i8 3, i8 3>
109  ret <2 x i8> %sh
110}
111
112define i8 @lshr_ctlz_zero_is_undef_vec(<2 x i8> %x) {
113; CHECK-LABEL: @lshr_ctlz_zero_is_undef_vec(
114; CHECK-NEXT:    ret i8 0
115;
116  %ct = call <2 x i8> @llvm.ctlz.v2i8(<2 x i8> %x, i1 true)
117  %sh = lshr <2 x i8> %ct, <i8 3, i8 0>
118  %ex = extractelement <2 x i8> %sh, i32 0
119  ret i8 %ex
120}
121
122define <2 x i8> @lshr_cttz_zero_is_undef_splat_vec(<2 x i8> %x) {
123; CHECK-LABEL: @lshr_cttz_zero_is_undef_splat_vec(
124; CHECK-NEXT:    ret <2 x i8> zeroinitializer
125;
126  %ct = call <2 x i8> @llvm.cttz.v2i8(<2 x i8> %x, i1 true)
127  %sh = lshr <2 x i8> %ct, <i8 3, i8 3>
128  ret <2 x i8> %sh
129}
130
131define i8 @lshr_cttz_zero_is_undef_vec(<2 x i8> %x) {
132; CHECK-LABEL: @lshr_cttz_zero_is_undef_vec(
133; CHECK-NEXT:    ret i8 0
134;
135  %ct = call <2 x i8> @llvm.cttz.v2i8(<2 x i8> %x, i1 true)
136  %sh = lshr <2 x i8> %ct, <i8 3, i8 0>
137  %ex = extractelement <2 x i8> %sh, i32 0
138  ret i8 %ex
139}
140
141
142define i8 @lshr_exact(i8 %x) {
143; CHECK-LABEL: @lshr_exact(
144; CHECK-NEXT:    [[TMP1:%.*]] = add i8 [[X:%.*]], 1
145; CHECK-NEXT:    [[LSHR:%.*]] = and i8 [[TMP1]], 63
146; CHECK-NEXT:    ret i8 [[LSHR]]
147;
148  %shl = shl i8 %x, 2
149  %add = add i8 %shl, 4
150  %lshr = lshr i8 %add, 2
151  ret i8 %lshr
152}
153
154define <2 x i8> @lshr_exact_splat_vec(<2 x i8> %x) {
155; CHECK-LABEL: @lshr_exact_splat_vec(
156; CHECK-NEXT:    [[TMP1:%.*]] = add <2 x i8> [[X:%.*]], splat (i8 1)
157; CHECK-NEXT:    [[LSHR:%.*]] = and <2 x i8> [[TMP1]], splat (i8 63)
158; CHECK-NEXT:    ret <2 x i8> [[LSHR]]
159;
160  %shl = shl <2 x i8> %x, <i8 2, i8 2>
161  %add = add <2 x i8> %shl, <i8 4, i8 4>
162  %lshr = lshr <2 x i8> %add, <i8 2, i8 2>
163  ret <2 x i8> %lshr
164}
165
166define <2 x i8> @lshr_exact_splat_vec_nuw(<2 x i8> %x) {
167; CHECK-LABEL: @lshr_exact_splat_vec_nuw(
168; CHECK-NEXT:    [[LSHR:%.*]] = add nuw <2 x i8> [[X:%.*]], splat (i8 1)
169; CHECK-NEXT:    ret <2 x i8> [[LSHR]]
170;
171  %shl = shl nuw <2 x i8> %x, <i8 2, i8 2>
172  %add = add nuw <2 x i8> %shl, <i8 4, i8 4>
173  %lshr = lshr <2 x i8> %add, <i8 2, i8 2>
174  ret <2 x i8> %lshr
175}
176
177define i8 @shl_add(i8 %x, i8 %y) {
178; CHECK-LABEL: @shl_add(
179; CHECK-NEXT:    [[TMP1:%.*]] = lshr i8 [[Y:%.*]], 2
180; CHECK-NEXT:    [[TMP2:%.*]] = add i8 [[TMP1]], [[X:%.*]]
181; CHECK-NEXT:    [[R:%.*]] = and i8 [[TMP2]], 63
182; CHECK-NEXT:    ret i8 [[R]]
183;
184  %l = shl i8 %x, 2
185  %a = add i8 %l, %y
186  %r = lshr i8 %a, 2
187  ret i8 %r
188}
189
190define <2 x i8> @shl_add_commute_vec(<2 x i8> %x, <2 x i8> %py) {
191; CHECK-LABEL: @shl_add_commute_vec(
192; CHECK-NEXT:    [[Y:%.*]] = mul <2 x i8> [[PY:%.*]], [[PY]]
193; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i8> [[Y]], splat (i8 3)
194; CHECK-NEXT:    [[TMP2:%.*]] = add <2 x i8> [[TMP1]], [[X:%.*]]
195; CHECK-NEXT:    [[R:%.*]] = and <2 x i8> [[TMP2]], splat (i8 31)
196; CHECK-NEXT:    ret <2 x i8> [[R]]
197;
198  %y = mul <2 x i8> %py, %py ; thwart complexity-based canonicalization
199  %l = shl <2 x i8> %x, <i8 3, i8 3>
200  %a = add <2 x i8> %y, %l
201  %r = lshr <2 x i8> %a, <i8 3, i8 3>
202  ret <2 x i8> %r
203}
204
205define i32 @shl_add_use1(i32 %x, i32 %y) {
206; CHECK-LABEL: @shl_add_use1(
207; CHECK-NEXT:    [[L:%.*]] = shl i32 [[X:%.*]], 2
208; CHECK-NEXT:    call void @use(i32 [[L]])
209; CHECK-NEXT:    [[A:%.*]] = add i32 [[L]], [[Y:%.*]]
210; CHECK-NEXT:    [[R:%.*]] = lshr i32 [[A]], 2
211; CHECK-NEXT:    ret i32 [[R]]
212;
213  %l = shl i32 %x, 2
214  call void @use(i32 %l)
215  %a = add i32 %l, %y
216  %r = lshr i32 %a, 2
217  ret i32 %r
218}
219
220define i32 @shl_add_use2(i32 %x, i32 %y) {
221; CHECK-LABEL: @shl_add_use2(
222; CHECK-NEXT:    [[L:%.*]] = shl i32 [[X:%.*]], 2
223; CHECK-NEXT:    [[A:%.*]] = add i32 [[L]], [[Y:%.*]]
224; CHECK-NEXT:    call void @use(i32 [[A]])
225; CHECK-NEXT:    [[R:%.*]] = lshr i32 [[A]], 2
226; CHECK-NEXT:    ret i32 [[R]]
227;
228  %l = shl i32 %x, 2
229  %a = add i32 %l, %y
230  call void @use(i32 %a)
231  %r = lshr i32 %a, 2
232  ret i32 %r
233}
234
235define i16 @bool_zext(i1 %x) {
236; CHECK-LABEL: @bool_zext(
237; CHECK-NEXT:    [[HIBIT:%.*]] = zext i1 [[X:%.*]] to i16
238; CHECK-NEXT:    ret i16 [[HIBIT]]
239;
240  %sext = sext i1 %x to i16
241  %hibit = lshr i16 %sext, 15
242  ret i16 %hibit
243}
244
245define i32 @bool_zext_use(i1 %x) {
246; CHECK-LABEL: @bool_zext_use(
247; CHECK-NEXT:    [[SEXT:%.*]] = sext i1 [[X:%.*]] to i32
248; CHECK-NEXT:    call void @use(i32 [[SEXT]])
249; CHECK-NEXT:    [[HIBIT:%.*]] = zext i1 [[X]] to i32
250; CHECK-NEXT:    ret i32 [[HIBIT]]
251;
252  %sext = sext i1 %x to i32
253  call void @use(i32 %sext)
254  %hibit = lshr i32 %sext, 31
255  ret i32 %hibit
256}
257
258define <2 x i8> @bool_zext_splat(<2 x i1> %x) {
259; CHECK-LABEL: @bool_zext_splat(
260; CHECK-NEXT:    [[HIBIT:%.*]] = zext <2 x i1> [[X:%.*]] to <2 x i8>
261; CHECK-NEXT:    ret <2 x i8> [[HIBIT]]
262;
263  %sext = sext <2 x i1> %x to <2 x i8>
264  %hibit = lshr <2 x i8> %sext, <i8 7, i8 7>
265  ret <2 x i8> %hibit
266}
267
268define i32 @smear_sign_and_widen(i8 %x) {
269; CHECK-LABEL: @smear_sign_and_widen(
270; CHECK-NEXT:    [[TMP1:%.*]] = ashr i8 [[X:%.*]], 7
271; CHECK-NEXT:    [[HIBIT:%.*]] = zext i8 [[TMP1]] to i32
272; CHECK-NEXT:    ret i32 [[HIBIT]]
273;
274  %sext = sext i8 %x to i32
275  %hibit = lshr i32 %sext, 24
276  ret i32 %hibit
277}
278
279define i16 @smear_sign_and_widen_should_not_change_type(i4 %x) {
280; CHECK-LABEL: @smear_sign_and_widen_should_not_change_type(
281; CHECK-NEXT:    [[SEXT:%.*]] = sext i4 [[X:%.*]] to i16
282; CHECK-NEXT:    [[HIBIT:%.*]] = lshr i16 [[SEXT]], 12
283; CHECK-NEXT:    ret i16 [[HIBIT]]
284;
285  %sext = sext i4 %x to i16
286  %hibit = lshr i16 %sext, 12
287  ret i16 %hibit
288}
289
290define <2 x i8> @smear_sign_and_widen_splat(<2 x i6> %x) {
291; CHECK-LABEL: @smear_sign_and_widen_splat(
292; CHECK-NEXT:    [[TMP1:%.*]] = ashr <2 x i6> [[X:%.*]], splat (i6 2)
293; CHECK-NEXT:    [[HIBIT:%.*]] = zext <2 x i6> [[TMP1]] to <2 x i8>
294; CHECK-NEXT:    ret <2 x i8> [[HIBIT]]
295;
296  %sext = sext <2 x i6> %x to <2 x i8>
297  %hibit = lshr <2 x i8> %sext, <i8 2, i8 2>
298  ret <2 x i8> %hibit
299}
300
301define i18 @fake_sext(i3 %x) {
302; CHECK-LABEL: @fake_sext(
303; CHECK-NEXT:    [[TMP1:%.*]] = lshr i3 [[X:%.*]], 2
304; CHECK-NEXT:    [[SH:%.*]] = zext nneg i3 [[TMP1]] to i18
305; CHECK-NEXT:    ret i18 [[SH]]
306;
307  %sext = sext i3 %x to i18
308  %sh = lshr i18 %sext, 17
309  ret i18 %sh
310}
311
312; Avoid the transform if it would change the shift from a legal to illegal type.
313
314define i32 @fake_sext_but_should_not_change_type(i3 %x) {
315; CHECK-LABEL: @fake_sext_but_should_not_change_type(
316; CHECK-NEXT:    [[SEXT:%.*]] = sext i3 [[X:%.*]] to i32
317; CHECK-NEXT:    [[SH:%.*]] = lshr i32 [[SEXT]], 31
318; CHECK-NEXT:    ret i32 [[SH]]
319;
320  %sext = sext i3 %x to i32
321  %sh = lshr i32 %sext, 31
322  ret i32 %sh
323}
324
325define <2 x i8> @fake_sext_splat(<2 x i3> %x) {
326; CHECK-LABEL: @fake_sext_splat(
327; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i3> [[X:%.*]], splat (i3 2)
328; CHECK-NEXT:    [[SH:%.*]] = zext nneg <2 x i3> [[TMP1]] to <2 x i8>
329; CHECK-NEXT:    ret <2 x i8> [[SH]]
330;
331  %sext = sext <2 x i3> %x to <2 x i8>
332  %sh = lshr <2 x i8> %sext, <i8 7, i8 7>
333  ret <2 x i8> %sh
334}
335
336; Use a narrow shift: lshr (zext iM X to iN), C --> zext (lshr X, C) to iN
337
338define <2 x i32> @narrow_lshr_constant(<2 x i8> %x, <2 x i8> %y) {
339; CHECK-LABEL: @narrow_lshr_constant(
340; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i8> [[X:%.*]], splat (i8 3)
341; CHECK-NEXT:    [[SH:%.*]] = zext nneg <2 x i8> [[TMP1]] to <2 x i32>
342; CHECK-NEXT:    ret <2 x i32> [[SH]]
343;
344  %zx = zext <2 x i8> %x to <2 x i32>
345  %sh = lshr <2 x i32> %zx, <i32 3, i32 3>
346  ret <2 x i32> %sh
347}
348
349define i32 @mul_splat_fold(i32 %x) {
350; CHECK-LABEL: @mul_splat_fold(
351; CHECK-NEXT:    ret i32 [[X:%.*]]
352;
353  %m = mul nuw i32 %x, 65537
354  %t = lshr i32 %m, 16
355  ret i32 %t
356}
357
358; Vector type, extra use, weird types are all ok.
359
360define <3 x i14> @mul_splat_fold_vec(<3 x i14> %x) {
361; CHECK-LABEL: @mul_splat_fold_vec(
362; CHECK-NEXT:    [[M:%.*]] = mul nuw <3 x i14> [[X:%.*]], splat (i14 129)
363; CHECK-NEXT:    call void @usevec(<3 x i14> [[M]])
364; CHECK-NEXT:    ret <3 x i14> [[X]]
365;
366  %m = mul nuw <3 x i14> %x, <i14 129, i14 129, i14 129>
367  call void @usevec(<3 x i14> %m)
368  %t = lshr <3 x i14> %m, <i14 7, i14 7, i14 7>
369  ret <3 x i14> %t
370}
371
372define i32 @shl_add_lshr_flag_preservation(i32 %x, i32 %c, i32 %y) {
373; CHECK-LABEL: @shl_add_lshr_flag_preservation(
374; CHECK-NEXT:    [[TMP1:%.*]] = lshr exact i32 [[Y:%.*]], [[C:%.*]]
375; CHECK-NEXT:    [[LSHR:%.*]] = add nuw nsw i32 [[TMP1]], [[X:%.*]]
376; CHECK-NEXT:    ret i32 [[LSHR]]
377;
378  %shl = shl nuw i32 %x, %c
379  %add = add nuw nsw i32 %shl, %y
380  %lshr = lshr exact i32 %add, %c
381  ret i32 %lshr
382}
383
384define i32 @shl_add_lshr(i32 %x, i32 %c, i32 %y) {
385; CHECK-LABEL: @shl_add_lshr(
386; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[Y:%.*]], [[C:%.*]]
387; CHECK-NEXT:    [[LSHR:%.*]] = add nuw i32 [[TMP1]], [[X:%.*]]
388; CHECK-NEXT:    ret i32 [[LSHR]]
389;
390  %shl = shl nuw i32 %x, %c
391  %add = add nuw i32 %shl, %y
392  %lshr = lshr i32 %add, %c
393  ret i32 %lshr
394}
395
396define i32 @shl_add_lshr_comm(i32 %x, i32 %c, i32 %y) {
397; CHECK-LABEL: @shl_add_lshr_comm(
398; CHECK-NEXT:    [[Y2:%.*]] = mul i32 [[Y:%.*]], [[Y]]
399; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[Y2]], [[C:%.*]]
400; CHECK-NEXT:    [[LSHR:%.*]] = add nuw i32 [[TMP1]], [[X:%.*]]
401; CHECK-NEXT:    ret i32 [[LSHR]]
402;
403  %shl = shl nuw i32 %x, %c
404  %y2 = mul i32 %y, %y ; thwart complexity-based canonicalization
405  %add = add nuw i32 %y2, %shl
406  %lshr = lshr i32 %add, %c
407  ret i32 %lshr
408}
409
410; Negative test
411
412define i32 @shl_add_lshr_no_nuw(i32 %x, i32 %c, i32 %y) {
413; CHECK-LABEL: @shl_add_lshr_no_nuw(
414; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i32 [[X:%.*]], [[C:%.*]]
415; CHECK-NEXT:    [[ADD:%.*]] = add i32 [[SHL]], [[Y:%.*]]
416; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[ADD]], [[C]]
417; CHECK-NEXT:    ret i32 [[LSHR]]
418;
419  %shl = shl nuw i32 %x, %c
420  %add = add i32 %shl, %y
421  %lshr = lshr i32 %add, %c
422  ret i32 %lshr
423}
424
425; Negative test
426
427define i32 @shl_sub_lshr_not_exact(i32 %x, i32 %c, i32 %y) {
428; CHECK-LABEL: @shl_sub_lshr_not_exact(
429; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i32 [[X:%.*]], [[C:%.*]]
430; CHECK-NEXT:    [[SUB:%.*]] = sub nuw i32 [[SHL]], [[Y:%.*]]
431; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[SUB]], [[C]]
432; CHECK-NEXT:    ret i32 [[LSHR]]
433;
434  %shl = shl nuw i32 %x, %c
435  %sub = sub nuw i32 %shl, %y
436  %lshr = lshr i32 %sub, %c
437  ret i32 %lshr
438}
439
440; Negative test
441
442define i32 @shl_sub_lshr_no_nuw(i32 %x, i32 %c, i32 %y) {
443; CHECK-LABEL: @shl_sub_lshr_no_nuw(
444; CHECK-NEXT:    [[SHL:%.*]] = shl nsw i32 [[X:%.*]], [[C:%.*]]
445; CHECK-NEXT:    [[SUB:%.*]] = sub nsw i32 [[SHL]], [[Y:%.*]]
446; CHECK-NEXT:    [[LSHR:%.*]] = lshr exact i32 [[SUB]], [[C]]
447; CHECK-NEXT:    ret i32 [[LSHR]]
448;
449  %shl = shl nsw i32 %x, %c
450  %sub = sub nsw i32 %shl, %y
451  %lshr = lshr exact i32 %sub, %c
452  ret i32 %lshr
453}
454
455define i32 @shl_sub_lshr(i32 %x, i32 %c, i32 %y) {
456; CHECK-LABEL: @shl_sub_lshr(
457; CHECK-NEXT:    [[TMP1:%.*]] = lshr exact i32 [[Y:%.*]], [[C:%.*]]
458; CHECK-NEXT:    [[LSHR:%.*]] = sub nuw nsw i32 [[X:%.*]], [[TMP1]]
459; CHECK-NEXT:    ret i32 [[LSHR]]
460;
461  %shl = shl nuw i32 %x, %c
462  %sub = sub nuw nsw i32 %shl, %y
463  %lshr = lshr exact i32 %sub, %c
464  ret i32 %lshr
465}
466
467define i32 @shl_sub_lshr_reverse(i32 %x, i32 %c, i32 %y) {
468; CHECK-LABEL: @shl_sub_lshr_reverse(
469; CHECK-NEXT:    [[TMP1:%.*]] = lshr exact i32 [[Y:%.*]], [[C:%.*]]
470; CHECK-NEXT:    [[LSHR:%.*]] = sub nuw nsw i32 [[TMP1]], [[X:%.*]]
471; CHECK-NEXT:    ret i32 [[LSHR]]
472;
473  %shl = shl nuw i32 %x, %c
474  %sub = sub nuw nsw i32 %y, %shl
475  %lshr = lshr exact i32 %sub, %c
476  ret i32 %lshr
477}
478
479define i32 @shl_sub_lshr_reverse_no_nsw(i32 %x, i32 %c, i32 %y) {
480; CHECK-LABEL: @shl_sub_lshr_reverse_no_nsw(
481; CHECK-NEXT:    [[TMP1:%.*]] = lshr exact i32 [[Y:%.*]], [[C:%.*]]
482; CHECK-NEXT:    [[LSHR:%.*]] = sub nuw i32 [[TMP1]], [[X:%.*]]
483; CHECK-NEXT:    ret i32 [[LSHR]]
484;
485  %shl = shl nuw i32 %x, %c
486  %sub = sub nuw i32 %y, %shl
487  %lshr = lshr exact i32 %sub, %c
488  ret i32 %lshr
489}
490
491define i32 @shl_sub_lshr_reverse_nsw_on_op1(i32 %x, i32 %c, i32 %y) {
492; CHECK-LABEL: @shl_sub_lshr_reverse_nsw_on_op1(
493; CHECK-NEXT:    [[TMP1:%.*]] = lshr exact i32 [[Y:%.*]], [[C:%.*]]
494; CHECK-NEXT:    [[LSHR:%.*]] = sub nuw i32 [[TMP1]], [[X:%.*]]
495; CHECK-NEXT:    ret i32 [[LSHR]]
496;
497  %shl = shl nuw nsw i32 %x, %c
498  %sub = sub nuw i32 %y, %shl
499  %lshr = lshr exact i32 %sub, %c
500  ret i32 %lshr
501}
502
503; Negative test
504
505define i32 @shl_sub_lshr_reverse_no_exact(i32 %x, i32 %c, i32 %y) {
506; CHECK-LABEL: @shl_sub_lshr_reverse_no_exact(
507; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i32 [[X:%.*]], [[C:%.*]]
508; CHECK-NEXT:    [[SUB:%.*]] = sub nuw nsw i32 [[Y:%.*]], [[SHL]]
509; CHECK-NEXT:    [[LSHR:%.*]] = lshr i32 [[SUB]], [[C]]
510; CHECK-NEXT:    ret i32 [[LSHR]]
511;
512  %shl = shl nuw i32 %x, %c
513  %sub = sub nuw nsw i32 %y, %shl
514  %lshr = lshr i32 %sub, %c
515  ret i32 %lshr
516}
517
518; Negative test
519
520define i32 @shl_sub_lshr_reverse_multiuse(i32 %x, i32 %c, i32 %y) {
521; CHECK-LABEL: @shl_sub_lshr_reverse_multiuse(
522; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i32 [[X:%.*]], [[C:%.*]]
523; CHECK-NEXT:    [[SUB:%.*]] = sub nuw i32 [[Y:%.*]], [[SHL]]
524; CHECK-NEXT:    call void @use(i32 [[SUB]])
525; CHECK-NEXT:    [[LSHR:%.*]] = lshr exact i32 [[SUB]], [[C]]
526; CHECK-NEXT:    ret i32 [[LSHR]]
527;
528  %shl = shl nuw i32 %x, %c
529  %sub = sub nuw i32 %y, %shl
530  call void @use(i32 %sub)
531  %lshr = lshr exact i32 %sub, %c
532  ret i32 %lshr
533}
534
535define i32 @shl_sub_lshr_reverse_multiuse2(i32 %x, i32 %c, i32 %y) {
536; CHECK-LABEL: @shl_sub_lshr_reverse_multiuse2(
537; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i32 [[X:%.*]], [[C:%.*]]
538; CHECK-NEXT:    call void @use(i32 [[SHL]])
539; CHECK-NEXT:    [[TMP1:%.*]] = lshr exact i32 [[Y:%.*]], [[C]]
540; CHECK-NEXT:    [[LSHR:%.*]] = sub nuw i32 [[TMP1]], [[X]]
541; CHECK-NEXT:    ret i32 [[LSHR]]
542;
543  %shl = shl nuw i32 %x, %c
544  call void @use(i32 %shl)
545  %sub = sub nuw i32 %y, %shl
546  %lshr = lshr exact i32 %sub, %c
547  ret i32 %lshr
548}
549
550; Negative test
551
552define i32 @shl_sub_lshr_reverse_no_nuw(i32 %x, i32 %c, i32 %y) {
553; CHECK-LABEL: @shl_sub_lshr_reverse_no_nuw(
554; CHECK-NEXT:    [[SHL:%.*]] = shl i32 [[X:%.*]], [[C:%.*]]
555; CHECK-NEXT:    [[SUB:%.*]] = sub nuw i32 [[Y:%.*]], [[SHL]]
556; CHECK-NEXT:    [[LSHR:%.*]] = lshr exact i32 [[SUB]], [[C]]
557; CHECK-NEXT:    ret i32 [[LSHR]]
558;
559  %shl = shl i32 %x, %c
560  %sub = sub nuw i32 %y, %shl
561  %lshr = lshr exact i32 %sub, %c
562  ret i32 %lshr
563}
564
565; Negative test
566
567define i32 @shl_sub_lshr_reverse_no_nsw_2(i32 %x, i32 %c, i32 %y) {
568; CHECK-LABEL: @shl_sub_lshr_reverse_no_nsw_2(
569; CHECK-NEXT:    [[SHL:%.*]] = shl nuw nsw i32 [[X:%.*]], [[C:%.*]]
570; CHECK-NEXT:    [[SUB:%.*]] = sub i32 [[Y:%.*]], [[SHL]]
571; CHECK-NEXT:    [[LSHR:%.*]] = lshr exact i32 [[SUB]], [[C]]
572; CHECK-NEXT:    ret i32 [[LSHR]]
573;
574  %shl = shl nuw nsw i32 %x, %c
575  %sub = sub i32 %y, %shl
576  %lshr = lshr exact i32 %sub, %c
577  ret i32 %lshr
578}
579
580define i32 @shl_or_lshr(i32 %x, i32 %c, i32 %y) {
581; CHECK-LABEL: @shl_or_lshr(
582; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[Y:%.*]], [[C:%.*]]
583; CHECK-NEXT:    [[LSHR:%.*]] = or i32 [[TMP1]], [[X:%.*]]
584; CHECK-NEXT:    ret i32 [[LSHR]]
585;
586  %shl = shl nuw i32 %x, %c
587  %or = or i32 %shl, %y
588  %lshr = lshr i32 %or, %c
589  ret i32 %lshr
590}
591
592define i32 @shl_or_disjoint_lshr(i32 %x, i32 %c, i32 %y) {
593; CHECK-LABEL: @shl_or_disjoint_lshr(
594; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[Y:%.*]], [[C:%.*]]
595; CHECK-NEXT:    [[LSHR:%.*]] = or disjoint i32 [[TMP1]], [[X:%.*]]
596; CHECK-NEXT:    ret i32 [[LSHR]]
597;
598  %shl = shl nuw i32 %x, %c
599  %or = or disjoint i32 %shl, %y
600  %lshr = lshr i32 %or, %c
601  ret i32 %lshr
602}
603
604define i32 @shl_or_lshr_comm(i32 %x, i32 %c, i32 %y) {
605; CHECK-LABEL: @shl_or_lshr_comm(
606; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[Y:%.*]], [[C:%.*]]
607; CHECK-NEXT:    [[LSHR:%.*]] = or i32 [[TMP1]], [[X:%.*]]
608; CHECK-NEXT:    ret i32 [[LSHR]]
609;
610  %shl = shl nuw i32 %x, %c
611  %or = or i32 %y, %shl
612  %lshr = lshr i32 %or, %c
613  ret i32 %lshr
614}
615
616define i32 @shl_or_disjoint_lshr_comm(i32 %x, i32 %c, i32 %y) {
617; CHECK-LABEL: @shl_or_disjoint_lshr_comm(
618; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[Y:%.*]], [[C:%.*]]
619; CHECK-NEXT:    [[LSHR:%.*]] = or disjoint i32 [[TMP1]], [[X:%.*]]
620; CHECK-NEXT:    ret i32 [[LSHR]]
621;
622  %shl = shl nuw i32 %x, %c
623  %or = or disjoint i32 %y, %shl
624  %lshr = lshr i32 %or, %c
625  ret i32 %lshr
626}
627
628define i32 @shl_xor_lshr(i32 %x, i32 %c, i32 %y) {
629; CHECK-LABEL: @shl_xor_lshr(
630; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[Y:%.*]], [[C:%.*]]
631; CHECK-NEXT:    [[LSHR:%.*]] = xor i32 [[TMP1]], [[X:%.*]]
632; CHECK-NEXT:    ret i32 [[LSHR]]
633;
634  %shl = shl nuw i32 %x, %c
635  %xor = xor i32 %shl, %y
636  %lshr = lshr i32 %xor, %c
637  ret i32 %lshr
638}
639
640define i32 @shl_xor_lshr_comm(i32 %x, i32 %c, i32 %y) {
641; CHECK-LABEL: @shl_xor_lshr_comm(
642; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[Y:%.*]], [[C:%.*]]
643; CHECK-NEXT:    [[LSHR:%.*]] = xor i32 [[TMP1]], [[X:%.*]]
644; CHECK-NEXT:    ret i32 [[LSHR]]
645;
646  %shl = shl nuw i32 %x, %c
647  %xor = xor i32 %y, %shl
648  %lshr = lshr i32 %xor, %c
649  ret i32 %lshr
650}
651
652define i32 @shl_and_lshr(i32 %x, i32 %c, i32 %y) {
653; CHECK-LABEL: @shl_and_lshr(
654; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[Y:%.*]], [[C:%.*]]
655; CHECK-NEXT:    [[LSHR:%.*]] = and i32 [[TMP1]], [[X:%.*]]
656; CHECK-NEXT:    ret i32 [[LSHR]]
657;
658  %shl = shl nuw i32 %x, %c
659  %and = and i32 %shl, %y
660  %lshr = lshr i32 %and, %c
661  ret i32 %lshr
662}
663
664define i32 @shl_and_lshr_comm(i32 %x, i32 %c, i32 %y) {
665; CHECK-LABEL: @shl_and_lshr_comm(
666; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[Y:%.*]], [[C:%.*]]
667; CHECK-NEXT:    [[LSHR:%.*]] = and i32 [[TMP1]], [[X:%.*]]
668; CHECK-NEXT:    ret i32 [[LSHR]]
669;
670  %shl = shl nuw i32 %x, %c
671  %and = and i32 %y, %shl
672  %lshr = lshr i32 %and, %c
673  ret i32 %lshr
674}
675
676define i32 @shl_lshr_and_exact(i32 %x, i32 %c, i32 %y) {
677; CHECK-LABEL: @shl_lshr_and_exact(
678; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[Y:%.*]], [[C:%.*]]
679; CHECK-NEXT:    [[TMP2:%.*]] = and i32 [[TMP1]], [[X:%.*]]
680; CHECK-NEXT:    ret i32 [[TMP2]]
681;
682  %2 = shl nuw i32 %x, %c
683  %3 = and i32 %2, %y
684  %4 = lshr exact i32 %3, %c
685  ret i32 %4
686}
687
688; Negative test
689
690define i32 @shl_add_lshr_neg(i32 %x, i32 %y, i32 %z) {
691; CHECK-LABEL: @shl_add_lshr_neg(
692; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i32 [[X:%.*]], [[Y:%.*]]
693; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i32 [[SHL]], [[Z:%.*]]
694; CHECK-NEXT:    [[RES:%.*]] = lshr exact i32 [[ADD]], [[Z]]
695; CHECK-NEXT:    ret i32 [[RES]]
696;
697  %shl = shl nuw i32 %x, %y
698  %add = add nuw nsw i32 %shl, %z
699  %res = lshr exact i32 %add, %z
700  ret i32 %res
701}
702
703define i32 @mul_splat_fold_wrong_mul_const(i32 %x) {
704; CHECK-LABEL: @mul_splat_fold_wrong_mul_const(
705; CHECK-NEXT:    [[M:%.*]] = mul nuw i32 [[X:%.*]], 65538
706; CHECK-NEXT:    [[T:%.*]] = lshr i32 [[M]], 16
707; CHECK-NEXT:    ret i32 [[T]]
708;
709  %m = mul nuw i32 %x, 65538
710  %t = lshr i32 %m, 16
711  ret i32 %t
712}
713
714; Negative test
715
716define i32 @shl_add_lshr_multiuse(i32 %x, i32 %y, i32 %z) {
717; CHECK-LABEL: @shl_add_lshr_multiuse(
718; CHECK-NEXT:    [[SHL:%.*]] = shl nuw i32 [[X:%.*]], [[Y:%.*]]
719; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i32 [[SHL]], [[Z:%.*]]
720; CHECK-NEXT:    call void @use(i32 [[ADD]])
721; CHECK-NEXT:    [[RES:%.*]] = lshr exact i32 [[ADD]], [[Z]]
722; CHECK-NEXT:    ret i32 [[RES]]
723;
724  %shl = shl nuw i32 %x, %y
725  %add = add nuw nsw i32 %shl, %z
726  call void @use (i32 %add)
727  %res = lshr exact i32 %add, %z
728  ret i32 %res
729}
730
731define i32 @mul_splat_fold_wrong_lshr_const(i32 %x) {
732; CHECK-LABEL: @mul_splat_fold_wrong_lshr_const(
733; CHECK-NEXT:    [[M:%.*]] = mul nuw i32 [[X:%.*]], 65537
734; CHECK-NEXT:    [[T:%.*]] = lshr i32 [[M]], 15
735; CHECK-NEXT:    ret i32 [[T]]
736;
737  %m = mul nuw i32 %x, 65537
738  %t = lshr i32 %m, 15
739  ret i32 %t
740}
741
742define i32 @mul_splat_fold_no_nuw(i32 %x) {
743; CHECK-LABEL: @mul_splat_fold_no_nuw(
744; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 16
745; CHECK-NEXT:    [[T:%.*]] = add nsw i32 [[X]], [[TMP1]]
746; CHECK-NEXT:    ret i32 [[T]]
747;
748  %m = mul nsw i32 %x, 65537
749  %t = lshr i32 %m, 16
750  ret i32 %t
751}
752
753; Negative test
754
755define i32 @mul_splat_fold_no_flags(i32 %x) {
756; CHECK-LABEL: @mul_splat_fold_no_flags(
757; CHECK-NEXT:    [[M:%.*]] = mul i32 [[X:%.*]], 65537
758; CHECK-NEXT:    [[T:%.*]] = lshr i32 [[M]], 16
759; CHECK-NEXT:    ret i32 [[T]]
760;
761  %m = mul i32 %x, 65537
762  %t = lshr i32 %m, 16
763  ret i32 %t
764}
765
766; Negative test (but simplifies before we reach the mul_splat transform)- need more than 2 bits
767
768define i2 @mul_splat_fold_too_narrow(i2 %x) {
769; CHECK-LABEL: @mul_splat_fold_too_narrow(
770; CHECK-NEXT:    ret i2 [[X:%.*]]
771;
772  %m = mul nuw i2 %x, 2
773  %t = lshr i2 %m, 1
774  ret i2 %t
775}
776
777define i32 @negative_and_odd(i32 %x) {
778; CHECK-LABEL: @negative_and_odd(
779; CHECK-NEXT:    [[TMP1:%.*]] = lshr i32 [[X:%.*]], 31
780; CHECK-NEXT:    [[R:%.*]] = and i32 [[TMP1]], [[X]]
781; CHECK-NEXT:    ret i32 [[R]]
782;
783  %s = srem i32 %x, 2
784  %r = lshr i32 %s, 31
785  ret i32 %r
786}
787
788define <2 x i7> @negative_and_odd_vec(<2 x i7> %x) {
789; CHECK-LABEL: @negative_and_odd_vec(
790; CHECK-NEXT:    [[TMP1:%.*]] = lshr <2 x i7> [[X:%.*]], splat (i7 6)
791; CHECK-NEXT:    [[R:%.*]] = and <2 x i7> [[TMP1]], [[X]]
792; CHECK-NEXT:    ret <2 x i7> [[R]]
793;
794  %s = srem <2 x i7> %x, <i7 2, i7 2>
795  %r = lshr <2 x i7> %s, <i7 6, i7 6>
796  ret <2 x i7> %r
797}
798
799; Negative test - this is still worth trying to avoid srem?
800
801define i32 @negative_and_odd_uses(i32 %x, ptr %p) {
802; CHECK-LABEL: @negative_and_odd_uses(
803; CHECK-NEXT:    [[S:%.*]] = srem i32 [[X:%.*]], 2
804; CHECK-NEXT:    store i32 [[S]], ptr [[P:%.*]], align 4
805; CHECK-NEXT:    [[R:%.*]] = lshr i32 [[S]], 31
806; CHECK-NEXT:    ret i32 [[R]]
807;
808  %s = srem i32 %x, 2
809  store i32 %s, ptr %p
810  %r = lshr i32 %s, 31
811  ret i32 %r
812}
813
814; Negative test - wrong divisor
815
816define i32 @srem3(i32 %x) {
817; CHECK-LABEL: @srem3(
818; CHECK-NEXT:    [[S:%.*]] = srem i32 [[X:%.*]], 3
819; CHECK-NEXT:    [[R:%.*]] = lshr i32 [[S]], 31
820; CHECK-NEXT:    ret i32 [[R]]
821;
822  %s = srem i32 %x, 3
823  %r = lshr i32 %s, 31
824  ret i32 %r
825}
826
827; Negative test - wrong shift amount
828
829define i32 @srem2_lshr30(i32 %x) {
830; CHECK-LABEL: @srem2_lshr30(
831; CHECK-NEXT:    [[S:%.*]] = srem i32 [[X:%.*]], 2
832; CHECK-NEXT:    [[R:%.*]] = lshr i32 [[S]], 30
833; CHECK-NEXT:    ret i32 [[R]]
834;
835  %s = srem i32 %x, 2
836  %r = lshr i32 %s, 30
837  ret i32 %r
838}
839
840define i12 @trunc_sandwich(i32 %x) {
841; CHECK-LABEL: @trunc_sandwich(
842; CHECK-NEXT:    [[SUM_SHIFT:%.*]] = lshr i32 [[X:%.*]], 30
843; CHECK-NEXT:    [[R1:%.*]] = trunc nuw nsw i32 [[SUM_SHIFT]] to i12
844; CHECK-NEXT:    ret i12 [[R1]]
845;
846  %sh = lshr i32 %x, 28
847  %tr = trunc i32 %sh to i12
848  %r = lshr i12 %tr, 2
849  ret i12 %r
850}
851
852define <2 x i12> @trunc_sandwich_splat_vec(<2 x i32> %x) {
853; CHECK-LABEL: @trunc_sandwich_splat_vec(
854; CHECK-NEXT:    [[SUM_SHIFT:%.*]] = lshr <2 x i32> [[X:%.*]], splat (i32 30)
855; CHECK-NEXT:    [[R1:%.*]] = trunc nuw nsw <2 x i32> [[SUM_SHIFT]] to <2 x i12>
856; CHECK-NEXT:    ret <2 x i12> [[R1]]
857;
858  %sh = lshr <2 x i32> %x, <i32 22, i32 22>
859  %tr = trunc <2 x i32> %sh to <2 x i12>
860  %r = lshr <2 x i12> %tr, <i12 8, i12 8>
861  ret <2 x i12> %r
862}
863
864define i12 @trunc_sandwich_min_shift1(i32 %x) {
865; CHECK-LABEL: @trunc_sandwich_min_shift1(
866; CHECK-NEXT:    [[SUM_SHIFT:%.*]] = lshr i32 [[X:%.*]], 21
867; CHECK-NEXT:    [[R1:%.*]] = trunc nuw nsw i32 [[SUM_SHIFT]] to i12
868; CHECK-NEXT:    ret i12 [[R1]]
869;
870  %sh = lshr i32 %x, 20
871  %tr = trunc i32 %sh to i12
872  %r = lshr i12 %tr, 1
873  ret i12 %r
874}
875
876define i12 @trunc_sandwich_small_shift1(i32 %x) {
877; CHECK-LABEL: @trunc_sandwich_small_shift1(
878; CHECK-NEXT:    [[SUM_SHIFT:%.*]] = lshr i32 [[X:%.*]], 20
879; CHECK-NEXT:    [[R1:%.*]] = trunc nuw i32 [[SUM_SHIFT]] to i12
880; CHECK-NEXT:    [[R:%.*]] = and i12 [[R1]], 2047
881; CHECK-NEXT:    ret i12 [[R]]
882;
883  %sh = lshr i32 %x, 19
884  %tr = trunc i32 %sh to i12
885  %r = lshr i12 %tr, 1
886  ret i12 %r
887}
888
889define i12 @trunc_sandwich_max_sum_shift(i32 %x) {
890; CHECK-LABEL: @trunc_sandwich_max_sum_shift(
891; CHECK-NEXT:    [[SUM_SHIFT:%.*]] = lshr i32 [[X:%.*]], 31
892; CHECK-NEXT:    [[R1:%.*]] = trunc nuw nsw i32 [[SUM_SHIFT]] to i12
893; CHECK-NEXT:    ret i12 [[R1]]
894;
895  %sh = lshr i32 %x, 20
896  %tr = trunc i32 %sh to i12
897  %r = lshr i12 %tr, 11
898  ret i12 %r
899}
900
901define i12 @trunc_sandwich_max_sum_shift2(i32 %x) {
902; CHECK-LABEL: @trunc_sandwich_max_sum_shift2(
903; CHECK-NEXT:    [[SUM_SHIFT:%.*]] = lshr i32 [[X:%.*]], 31
904; CHECK-NEXT:    [[R1:%.*]] = trunc nuw nsw i32 [[SUM_SHIFT]] to i12
905; CHECK-NEXT:    ret i12 [[R1]]
906;
907  %sh = lshr i32 %x, 30
908  %tr = trunc i32 %sh to i12
909  %r = lshr i12 %tr, 1
910  ret i12 %r
911}
912
913define i12 @trunc_sandwich_big_sum_shift1(i32 %x) {
914; CHECK-LABEL: @trunc_sandwich_big_sum_shift1(
915; CHECK-NEXT:    ret i12 0
916;
917  %sh = lshr i32 %x, 21
918  %tr = trunc i32 %sh to i12
919  %r = lshr i12 %tr, 11
920  ret i12 %r
921}
922
923define i12 @trunc_sandwich_big_sum_shift2(i32 %x) {
924; CHECK-LABEL: @trunc_sandwich_big_sum_shift2(
925; CHECK-NEXT:    ret i12 0
926;
927  %sh = lshr i32 %x, 31
928  %tr = trunc i32 %sh to i12
929  %r = lshr i12 %tr, 1
930  ret i12 %r
931}
932
933define i12 @trunc_sandwich_use1(i32 %x) {
934; CHECK-LABEL: @trunc_sandwich_use1(
935; CHECK-NEXT:    [[SH:%.*]] = lshr i32 [[X:%.*]], 28
936; CHECK-NEXT:    call void @use(i32 [[SH]])
937; CHECK-NEXT:    [[SUM_SHIFT:%.*]] = lshr i32 [[X]], 30
938; CHECK-NEXT:    [[R1:%.*]] = trunc nuw nsw i32 [[SUM_SHIFT]] to i12
939; CHECK-NEXT:    ret i12 [[R1]]
940;
941  %sh = lshr i32 %x, 28
942  call void @use(i32 %sh)
943  %tr = trunc i32 %sh to i12
944  %r = lshr i12 %tr, 2
945  ret i12 %r
946}
947
948define <3 x i9> @trunc_sandwich_splat_vec_use1(<3 x i14> %x) {
949; CHECK-LABEL: @trunc_sandwich_splat_vec_use1(
950; CHECK-NEXT:    [[SH:%.*]] = lshr <3 x i14> [[X:%.*]], splat (i14 6)
951; CHECK-NEXT:    call void @usevec(<3 x i14> [[SH]])
952; CHECK-NEXT:    [[SUM_SHIFT:%.*]] = lshr <3 x i14> [[X]], splat (i14 11)
953; CHECK-NEXT:    [[R1:%.*]] = trunc nuw nsw <3 x i14> [[SUM_SHIFT]] to <3 x i9>
954; CHECK-NEXT:    ret <3 x i9> [[R1]]
955;
956  %sh = lshr <3 x i14> %x, <i14 6, i14 6, i14 6>
957  call void @usevec(<3 x i14> %sh)
958  %tr = trunc <3 x i14> %sh to <3 x i9>
959  %r = lshr <3 x i9> %tr, <i9 5, i9 5, i9 5>
960  ret <3 x i9> %r
961}
962
963define i12 @trunc_sandwich_min_shift1_use1(i32 %x) {
964; CHECK-LABEL: @trunc_sandwich_min_shift1_use1(
965; CHECK-NEXT:    [[SH:%.*]] = lshr i32 [[X:%.*]], 20
966; CHECK-NEXT:    call void @use(i32 [[SH]])
967; CHECK-NEXT:    [[SUM_SHIFT:%.*]] = lshr i32 [[X]], 21
968; CHECK-NEXT:    [[R1:%.*]] = trunc nuw nsw i32 [[SUM_SHIFT]] to i12
969; CHECK-NEXT:    ret i12 [[R1]]
970;
971  %sh = lshr i32 %x, 20
972  call void @use(i32 %sh)
973  %tr = trunc i32 %sh to i12
974  %r = lshr i12 %tr, 1
975  ret i12 %r
976}
977
978; negative test - trunc is bigger than first shift
979
980define i12 @trunc_sandwich_small_shift1_use1(i32 %x) {
981; CHECK-LABEL: @trunc_sandwich_small_shift1_use1(
982; CHECK-NEXT:    [[SH:%.*]] = lshr i32 [[X:%.*]], 19
983; CHECK-NEXT:    call void @use(i32 [[SH]])
984; CHECK-NEXT:    [[TR:%.*]] = trunc i32 [[SH]] to i12
985; CHECK-NEXT:    [[R:%.*]] = lshr i12 [[TR]], 1
986; CHECK-NEXT:    ret i12 [[R]]
987;
988  %sh = lshr i32 %x, 19
989  call void @use(i32 %sh)
990  %tr = trunc i32 %sh to i12
991  %r = lshr i12 %tr, 1
992  ret i12 %r
993}
994
995define i12 @trunc_sandwich_max_sum_shift_use1(i32 %x) {
996; CHECK-LABEL: @trunc_sandwich_max_sum_shift_use1(
997; CHECK-NEXT:    [[SH:%.*]] = lshr i32 [[X:%.*]], 20
998; CHECK-NEXT:    call void @use(i32 [[SH]])
999; CHECK-NEXT:    [[SUM_SHIFT:%.*]] = lshr i32 [[X]], 31
1000; CHECK-NEXT:    [[R1:%.*]] = trunc nuw nsw i32 [[SUM_SHIFT]] to i12
1001; CHECK-NEXT:    ret i12 [[R1]]
1002;
1003  %sh = lshr i32 %x, 20
1004  call void @use(i32 %sh)
1005  %tr = trunc i32 %sh to i12
1006  %r = lshr i12 %tr, 11
1007  ret i12 %r
1008}
1009
1010define i12 @trunc_sandwich_max_sum_shift2_use1(i32 %x) {
1011; CHECK-LABEL: @trunc_sandwich_max_sum_shift2_use1(
1012; CHECK-NEXT:    [[SH:%.*]] = lshr i32 [[X:%.*]], 30
1013; CHECK-NEXT:    call void @use(i32 [[SH]])
1014; CHECK-NEXT:    [[SUM_SHIFT:%.*]] = lshr i32 [[X]], 31
1015; CHECK-NEXT:    [[R1:%.*]] = trunc nuw nsw i32 [[SUM_SHIFT]] to i12
1016; CHECK-NEXT:    ret i12 [[R1]]
1017;
1018  %sh = lshr i32 %x, 30
1019  call void @use(i32 %sh)
1020  %tr = trunc i32 %sh to i12
1021  %r = lshr i12 %tr, 1
1022  ret i12 %r
1023}
1024
1025; negative test - but overshift is simplified to zero by another fold
1026
1027define i12 @trunc_sandwich_big_sum_shift1_use1(i32 %x) {
1028; CHECK-LABEL: @trunc_sandwich_big_sum_shift1_use1(
1029; CHECK-NEXT:    [[SH:%.*]] = lshr i32 [[X:%.*]], 21
1030; CHECK-NEXT:    call void @use(i32 [[SH]])
1031; CHECK-NEXT:    ret i12 0
1032;
1033  %sh = lshr i32 %x, 21
1034  call void @use(i32 %sh)
1035  %tr = trunc i32 %sh to i12
1036  %r = lshr i12 %tr, 11
1037  ret i12 %r
1038}
1039
1040; negative test - but overshift is simplified to zero by another fold
1041
1042define i12 @trunc_sandwich_big_sum_shift2_use1(i32 %x) {
1043; CHECK-LABEL: @trunc_sandwich_big_sum_shift2_use1(
1044; CHECK-NEXT:    [[SH:%.*]] = lshr i32 [[X:%.*]], 31
1045; CHECK-NEXT:    call void @use(i32 [[SH]])
1046; CHECK-NEXT:    ret i12 0
1047;
1048  %sh = lshr i32 %x, 31
1049  call void @use(i32 %sh)
1050  %tr = trunc i32 %sh to i12
1051  %r = lshr i12 %tr, 1
1052  ret i12 %r
1053}
1054
1055define i16 @lshr_sext_i1_to_i16(i1 %a) {
1056; CHECK-LABEL: @lshr_sext_i1_to_i16(
1057; CHECK-NEXT:    [[LSHR:%.*]] = select i1 [[A:%.*]], i16 4095, i16 0
1058; CHECK-NEXT:    ret i16 [[LSHR]]
1059;
1060  %sext = sext i1 %a to i16
1061  %lshr = lshr i16 %sext, 4
1062  ret i16 %lshr
1063}
1064
1065define i128 @lshr_sext_i1_to_i128(i1 %a) {
1066; CHECK-LABEL: @lshr_sext_i1_to_i128(
1067; CHECK-NEXT:    [[LSHR:%.*]] = select i1 [[A:%.*]], i128 77371252455336267181195263, i128 0
1068; CHECK-NEXT:    ret i128 [[LSHR]]
1069;
1070  %sext = sext i1 %a to i128
1071  %lshr = lshr i128 %sext, 42
1072  ret i128 %lshr
1073}
1074
1075define i32 @lshr_sext_i1_to_i32_use(i1 %a) {
1076; CHECK-LABEL: @lshr_sext_i1_to_i32_use(
1077; CHECK-NEXT:    [[SEXT:%.*]] = sext i1 [[A:%.*]] to i32
1078; CHECK-NEXT:    call void @use(i32 [[SEXT]])
1079; CHECK-NEXT:    [[LSHR:%.*]] = select i1 [[A]], i32 262143, i32 0
1080; CHECK-NEXT:    ret i32 [[LSHR]]
1081;
1082  %sext = sext i1 %a to i32
1083  call void @use(i32 %sext)
1084  %lshr = lshr i32 %sext, 14
1085  ret i32 %lshr
1086}
1087
1088define <3 x i14> @lshr_sext_i1_to_i14_splat_vec_use1(<3 x i1> %a) {
1089; CHECK-LABEL: @lshr_sext_i1_to_i14_splat_vec_use1(
1090; CHECK-NEXT:    [[SEXT:%.*]] = sext <3 x i1> [[A:%.*]] to <3 x i14>
1091; CHECK-NEXT:    call void @usevec(<3 x i14> [[SEXT]])
1092; CHECK-NEXT:    [[LSHR:%.*]] = select <3 x i1> [[A]], <3 x i14> splat (i14 1023), <3 x i14> zeroinitializer
1093; CHECK-NEXT:    ret <3 x i14> [[LSHR]]
1094;
1095  %sext = sext <3 x i1> %a to <3 x i14>
1096  call void @usevec(<3 x i14> %sext)
1097  %lshr = lshr <3 x i14> %sext, <i14 4, i14 4, i14 4>
1098  ret <3 x i14> %lshr
1099}
1100
1101define i1 @icmp_ule(i32 %x, i32 %y) {
1102; CHECK-LABEL: @icmp_ule(
1103; CHECK-NEXT:    ret i1 true
1104;
1105  %x.shifted = lshr i32 %x, %y
1106  %cmp = icmp ule i32 %x.shifted, %x
1107  ret i1 %cmp
1108}
1109
1110define i1 @icmp_ult(i32 %x, i32 %y) {
1111; CHECK-LABEL: @icmp_ult(
1112; CHECK-NEXT:    [[X_SHIFTED:%.*]] = lshr i32 [[X:%.*]], [[Y:%.*]]
1113; CHECK-NEXT:    [[CMP:%.*]] = icmp ult i32 [[X_SHIFTED]], [[X]]
1114; CHECK-NEXT:    ret i1 [[CMP]]
1115;
1116  %x.shifted = lshr i32 %x, %y
1117  %cmp = icmp ult i32 %x.shifted, %x
1118  ret i1 %cmp
1119}
1120
1121define i1 @icmp_eq(i32 %x, i32 %y) {
1122; CHECK-LABEL: @icmp_eq(
1123; CHECK-NEXT:    [[X_SHIFTED:%.*]] = lshr i32 [[X:%.*]], [[Y:%.*]]
1124; CHECK-NEXT:    [[CMP:%.*]] = icmp eq i32 [[X_SHIFTED]], [[X]]
1125; CHECK-NEXT:    ret i1 [[CMP]]
1126;
1127  %x.shifted = lshr i32 %x, %y
1128  %cmp = icmp eq i32 %x.shifted, %x
1129  ret i1 %cmp
1130}
1131
1132define i1 @icmp_ne(i32 %x, i32 %y) {
1133; CHECK-LABEL: @icmp_ne(
1134; CHECK-NEXT:    [[X_SHIFTED:%.*]] = lshr i32 [[X:%.*]], [[Y:%.*]]
1135; CHECK-NEXT:    [[CMP:%.*]] = icmp ne i32 [[X_SHIFTED]], [[X]]
1136; CHECK-NEXT:    ret i1 [[CMP]]
1137;
1138  %x.shifted = lshr i32 %x, %y
1139  %cmp = icmp ne i32 %x.shifted, %x
1140  ret i1 %cmp
1141}
1142
1143define i1 @icmp_ugt(i32 %x, i32 %y) {
1144; CHECK-LABEL: @icmp_ugt(
1145; CHECK-NEXT:    ret i1 false
1146;
1147  %x.shifted = lshr i32 %x, %y
1148  %cmp = icmp ugt i32 %x.shifted, %x
1149  ret i1 %cmp
1150}
1151
1152define i1 @icmp_uge(i32 %x, i32 %y) {
1153; CHECK-LABEL: @icmp_uge(
1154; CHECK-NEXT:    [[X_SHIFTED:%.*]] = lshr i32 [[X:%.*]], [[Y:%.*]]
1155; CHECK-NEXT:    [[CMP:%.*]] = icmp uge i32 [[X_SHIFTED]], [[X]]
1156; CHECK-NEXT:    ret i1 [[CMP]]
1157;
1158  %x.shifted = lshr i32 %x, %y
1159  %cmp = icmp uge i32 %x.shifted, %x
1160  ret i1 %cmp
1161}
1162
1163define i1 @icmp_sle(i32 %x, i32 %y) {
1164; CHECK-LABEL: @icmp_sle(
1165; CHECK-NEXT:    [[X_SHIFTED:%.*]] = lshr i32 [[X:%.*]], [[Y:%.*]]
1166; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 [[X_SHIFTED]], [[X]]
1167; CHECK-NEXT:    ret i1 [[CMP]]
1168;
1169  %x.shifted = lshr i32 %x, %y
1170  %cmp = icmp sle i32 %x.shifted, %x
1171  ret i1 %cmp
1172}
1173
1174define i1 @icmp_slt(i32 %x, i32 %y) {
1175; CHECK-LABEL: @icmp_slt(
1176; CHECK-NEXT:    [[X_SHIFTED:%.*]] = lshr i32 [[X:%.*]], [[Y:%.*]]
1177; CHECK-NEXT:    [[CMP:%.*]] = icmp slt i32 [[X_SHIFTED]], [[X]]
1178; CHECK-NEXT:    ret i1 [[CMP]]
1179;
1180  %x.shifted = lshr i32 %x, %y
1181  %cmp = icmp slt i32 %x.shifted, %x
1182  ret i1 %cmp
1183}
1184
1185define i1 @icmp_sgt(i32 %x, i32 %y) {
1186; CHECK-LABEL: @icmp_sgt(
1187; CHECK-NEXT:    [[X_SHIFTED:%.*]] = lshr i32 [[X:%.*]], [[Y:%.*]]
1188; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[X_SHIFTED]], [[X]]
1189; CHECK-NEXT:    ret i1 [[CMP]]
1190;
1191  %x.shifted = lshr i32 %x, %y
1192  %cmp = icmp sgt i32 %x.shifted, %x
1193  ret i1 %cmp
1194}
1195
1196define i1 @icmp_sge(i32 %x, i32 %y) {
1197; CHECK-LABEL: @icmp_sge(
1198; CHECK-NEXT:    [[X_SHIFTED:%.*]] = lshr i32 [[X:%.*]], [[Y:%.*]]
1199; CHECK-NEXT:    [[CMP:%.*]] = icmp sge i32 [[X_SHIFTED]], [[X]]
1200; CHECK-NEXT:    ret i1 [[CMP]]
1201;
1202  %x.shifted = lshr i32 %x, %y
1203  %cmp = icmp sge i32 %x.shifted, %x
1204  ret i1 %cmp
1205}
1206
1207define i32 @narrow_bswap(i16 %x) {
1208; CHECK-LABEL: @narrow_bswap(
1209; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.bswap.i16(i16 [[X:%.*]])
1210; CHECK-NEXT:    [[S:%.*]] = zext i16 [[TMP1]] to i32
1211; CHECK-NEXT:    ret i32 [[S]]
1212;
1213  %z = zext i16 %x to i32
1214  %b = call i32 @llvm.bswap.i32(i32 %z)
1215  %s = lshr i32 %b, 16
1216  ret i32 %s
1217}
1218
1219define i128 @narrow_bswap_extra_wide(i16 %x) {
1220; CHECK-LABEL: @narrow_bswap_extra_wide(
1221; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.bswap.i16(i16 [[X:%.*]])
1222; CHECK-NEXT:    [[S:%.*]] = zext i16 [[TMP1]] to i128
1223; CHECK-NEXT:    ret i128 [[S]]
1224;
1225  %z = zext i16 %x to i128
1226  %b = call i128 @llvm.bswap.i128(i128 %z)
1227  %s = lshr i128 %b, 112
1228  ret i128 %s
1229}
1230
1231define i32 @narrow_bswap_undershift(i16 %x) {
1232; CHECK-LABEL: @narrow_bswap_undershift(
1233; CHECK-NEXT:    [[TMP1:%.*]] = call i16 @llvm.bswap.i16(i16 [[X:%.*]])
1234; CHECK-NEXT:    [[TMP2:%.*]] = zext i16 [[TMP1]] to i32
1235; CHECK-NEXT:    [[S:%.*]] = shl nuw nsw i32 [[TMP2]], 7
1236; CHECK-NEXT:    ret i32 [[S]]
1237;
1238  %z = zext i16 %x to i32
1239  %b = call i32 @llvm.bswap.i32(i32 %z)
1240  %s = lshr i32 %b, 9
1241  ret i32 %s
1242}
1243
1244define <2 x i64> @narrow_bswap_splat(<2 x i16> %x) {
1245; CHECK-LABEL: @narrow_bswap_splat(
1246; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i16> @llvm.bswap.v2i16(<2 x i16> [[X:%.*]])
1247; CHECK-NEXT:    [[S:%.*]] = zext <2 x i16> [[TMP1]] to <2 x i64>
1248; CHECK-NEXT:    ret <2 x i64> [[S]]
1249;
1250  %z = zext <2 x i16> %x to <2 x i64>
1251  %b = call <2 x i64> @llvm.bswap.v2i64(<2 x i64> %z)
1252  %s = lshr <2 x i64> %b, <i64 48, i64 48>
1253  ret <2 x i64> %s
1254}
1255
1256define <2 x i64> @narrow_bswap_splat_poison_elt(<2 x i16> %x) {
1257; CHECK-LABEL: @narrow_bswap_splat_poison_elt(
1258; CHECK-NEXT:    [[Z:%.*]] = zext <2 x i16> [[X:%.*]] to <2 x i64>
1259; CHECK-NEXT:    [[B:%.*]] = call <2 x i64> @llvm.bswap.v2i64(<2 x i64> [[Z]])
1260; CHECK-NEXT:    [[S:%.*]] = lshr exact <2 x i64> [[B]], <i64 48, i64 poison>
1261; CHECK-NEXT:    ret <2 x i64> [[S]]
1262;
1263  %z = zext <2 x i16> %x to <2 x i64>
1264  %b = call <2 x i64> @llvm.bswap.v2i64(<2 x i64> %z)
1265  %s = lshr <2 x i64> %b, <i64 48, i64 poison>
1266  ret <2 x i64> %s
1267}
1268
1269define <2 x i64> @narrow_bswap_overshift(<2 x i32> %x) {
1270; CHECK-LABEL: @narrow_bswap_overshift(
1271; CHECK-NEXT:    [[TMP1:%.*]] = call <2 x i32> @llvm.bswap.v2i32(<2 x i32> [[X:%.*]])
1272; CHECK-NEXT:    [[TMP2:%.*]] = lshr <2 x i32> [[TMP1]], splat (i32 16)
1273; CHECK-NEXT:    [[S:%.*]] = zext nneg <2 x i32> [[TMP2]] to <2 x i64>
1274; CHECK-NEXT:    ret <2 x i64> [[S]]
1275;
1276  %z = zext <2 x i32> %x to <2 x i64>
1277  %b = call <2 x i64> @llvm.bswap.v2i64(<2 x i64> %z)
1278  %s = lshr <2 x i64> %b, <i64 48, i64 48>
1279  ret <2 x i64> %s
1280}
1281
1282define i128 @narrow_bswap_overshift2(i96 %x) {
1283; CHECK-LABEL: @narrow_bswap_overshift2(
1284; CHECK-NEXT:    [[TMP1:%.*]] = call i96 @llvm.bswap.i96(i96 [[X:%.*]])
1285; CHECK-NEXT:    [[TMP2:%.*]] = lshr i96 [[TMP1]], 29
1286; CHECK-NEXT:    [[S:%.*]] = zext nneg i96 [[TMP2]] to i128
1287; CHECK-NEXT:    ret i128 [[S]]
1288;
1289  %z = zext i96 %x to i128
1290  %b = call i128 @llvm.bswap.i128(i128 %z)
1291  %s = lshr i128 %b, 61
1292  ret i128 %s
1293}
1294
1295; negative test - can't make a bswap with an odd number of bytes
1296
1297define i32 @not_narrow_bswap(i24 %x) {
1298; CHECK-LABEL: @not_narrow_bswap(
1299; CHECK-NEXT:    [[Z:%.*]] = zext i24 [[X:%.*]] to i32
1300; CHECK-NEXT:    [[B:%.*]] = call i32 @llvm.bswap.i32(i32 [[Z]])
1301; CHECK-NEXT:    [[R:%.*]] = lshr exact i32 [[B]], 8
1302; CHECK-NEXT:    ret i32 [[R]]
1303;
1304  %z = zext i24 %x to i32
1305  %b = call i32 @llvm.bswap.i32(i32 %z)
1306  %r = lshr i32 %b, 8
1307  ret i32 %r
1308}
1309
1310define i8 @not_signbit(i8 %x) {
1311; CHECK-LABEL: @not_signbit(
1312; CHECK-NEXT:    [[ISNOTNEG:%.*]] = icmp sgt i8 [[X:%.*]], -1
1313; CHECK-NEXT:    [[R:%.*]] = zext i1 [[ISNOTNEG]] to i8
1314; CHECK-NEXT:    ret i8 [[R]]
1315;
1316  %a = xor i8 %x, -1
1317  %r = lshr i8 %a, 7
1318  ret i8 %r
1319}
1320
1321define <2 x i6> @not_signbit_vec(<2 x i6> %x) {
1322; CHECK-LABEL: @not_signbit_vec(
1323; CHECK-NEXT:    [[ISNOTNEG:%.*]] = icmp sgt <2 x i6> [[X:%.*]], splat (i6 -1)
1324; CHECK-NEXT:    [[R:%.*]] = zext <2 x i1> [[ISNOTNEG]] to <2 x i6>
1325; CHECK-NEXT:    ret <2 x i6> [[R]]
1326;
1327  %a = xor <2 x i6> %x, <i6 -1, i6 poison>
1328  %r = lshr <2 x i6> %a, <i6 5, i6 poison>
1329  ret <2 x i6> %r
1330}
1331
1332define i8 @not_signbit_alt_xor(i8 %x) {
1333; CHECK-LABEL: @not_signbit_alt_xor(
1334; CHECK-NEXT:    [[ISNOTNEG:%.*]] = icmp sgt i8 [[X:%.*]], -1
1335; CHECK-NEXT:    [[R:%.*]] = zext i1 [[ISNOTNEG]] to i8
1336; CHECK-NEXT:    ret i8 [[R]]
1337;
1338  %a = xor i8 %x, -2
1339  %r = lshr i8 %a, 7
1340  ret i8 %r
1341}
1342
1343define i8 @not_not_signbit(i8 %x) {
1344; CHECK-LABEL: @not_not_signbit(
1345; CHECK-NEXT:    [[A:%.*]] = xor i8 [[X:%.*]], -1
1346; CHECK-NEXT:    [[R:%.*]] = lshr i8 [[A]], 6
1347; CHECK-NEXT:    ret i8 [[R]]
1348;
1349  %a = xor i8 %x, -1
1350  %r = lshr i8 %a, 6
1351  ret i8 %r
1352}
1353
1354define i32 @not_signbit_use(i32 %x) {
1355; CHECK-LABEL: @not_signbit_use(
1356; CHECK-NEXT:    [[A:%.*]] = xor i32 [[X:%.*]], -1
1357; CHECK-NEXT:    call void @use(i32 [[A]])
1358; CHECK-NEXT:    [[R:%.*]] = lshr i32 [[A]], 31
1359; CHECK-NEXT:    ret i32 [[R]]
1360;
1361  %a = xor i32 %x, -1
1362  call void @use(i32 %a)
1363  %r = lshr i32 %a, 31
1364  ret i32 %r
1365}
1366
1367define i32 @not_signbit_zext(i16 %x) {
1368; CHECK-LABEL: @not_signbit_zext(
1369; CHECK-NEXT:    [[ISNOTNEG:%.*]] = icmp sgt i16 [[X:%.*]], -1
1370; CHECK-NEXT:    [[R2:%.*]] = zext i1 [[ISNOTNEG]] to i32
1371; CHECK-NEXT:    ret i32 [[R2]]
1372;
1373  %a = xor i16 %x, -1
1374  %r = lshr i16 %a, 15
1375  %r2 = zext i16 %r to i32
1376  ret i32 %r2
1377}
1378
1379define i8 @not_signbit_trunc(i16 %x) {
1380; CHECK-LABEL: @not_signbit_trunc(
1381; CHECK-NEXT:    [[ISNOTNEG:%.*]] = icmp sgt i16 [[X:%.*]], -1
1382; CHECK-NEXT:    [[R2:%.*]] = zext i1 [[ISNOTNEG]] to i8
1383; CHECK-NEXT:    ret i8 [[R2]]
1384;
1385  %a = xor i16 %x, -1
1386  %r = lshr i16 %a, 15
1387  %r2 = trunc i16 %r to i8
1388  ret i8 %r2
1389}
1390
1391define i2 @bool_add_lshr(i1 %a, i1 %b) {
1392; CHECK-LABEL: @bool_add_lshr(
1393; CHECK-NEXT:    [[LSHR1:%.*]] = and i1 [[A:%.*]], [[B:%.*]]
1394; CHECK-NEXT:    [[LSHR:%.*]] = zext i1 [[LSHR1]] to i2
1395; CHECK-NEXT:    ret i2 [[LSHR]]
1396;
1397  %zext.a = zext i1 %a to i2
1398  %zext.b = zext i1 %b to i2
1399  %add = add i2 %zext.a, %zext.b
1400  %lshr = lshr i2 %add, 1
1401  ret i2 %lshr
1402}
1403
1404; negative test - need bools
1405
1406define i4 @not_bool_add_lshr(i2 %a, i2 %b) {
1407; CHECK-LABEL: @not_bool_add_lshr(
1408; CHECK-NEXT:    [[TMP1:%.*]] = xor i2 [[A:%.*]], -1
1409; CHECK-NEXT:    [[ADD_NARROWED_OVERFLOW:%.*]] = icmp ugt i2 [[B:%.*]], [[TMP1]]
1410; CHECK-NEXT:    [[LSHR:%.*]] = zext i1 [[ADD_NARROWED_OVERFLOW]] to i4
1411; CHECK-NEXT:    ret i4 [[LSHR]]
1412;
1413  %zext.a = zext i2 %a to i4
1414  %zext.b = zext i2 %b to i4
1415  %add = add i4 %zext.a, %zext.b
1416  %lshr = lshr i4 %add, 2
1417  ret i4 %lshr
1418}
1419
1420; TODO: This could be sext(and a, b).
1421
1422define i2 @bool_add_ashr(i1 %a, i1 %b) {
1423; CHECK-LABEL: @bool_add_ashr(
1424; CHECK-NEXT:    [[ZEXT_A:%.*]] = zext i1 [[A:%.*]] to i2
1425; CHECK-NEXT:    [[ZEXT_B:%.*]] = zext i1 [[B:%.*]] to i2
1426; CHECK-NEXT:    [[ADD:%.*]] = add nuw i2 [[ZEXT_A]], [[ZEXT_B]]
1427; CHECK-NEXT:    [[ASHR:%.*]] = ashr i2 [[ADD]], 1
1428; CHECK-NEXT:    ret i2 [[ASHR]]
1429;
1430  %zext.a = zext i1 %a to i2
1431  %zext.b = zext i1 %b to i2
1432  %add = add i2 %zext.a, %zext.b
1433  %ashr = ashr i2 %add, 1
1434  ret i2 %ashr
1435}
1436
1437define <2 x i8> @bool_add_lshr_vec(<2 x i1> %a, <2 x i1> %b) {
1438; CHECK-LABEL: @bool_add_lshr_vec(
1439; CHECK-NEXT:    [[LSHR1:%.*]] = and <2 x i1> [[A:%.*]], [[B:%.*]]
1440; CHECK-NEXT:    [[LSHR:%.*]] = zext <2 x i1> [[LSHR1]] to <2 x i8>
1441; CHECK-NEXT:    ret <2 x i8> [[LSHR]]
1442;
1443  %zext.a = zext <2 x i1> %a to <2 x i8>
1444  %zext.b = zext <2 x i1> %b to <2 x i8>
1445  %add = add <2 x i8> %zext.a, %zext.b
1446  %lshr = lshr <2 x i8> %add, <i8 1, i8 1>
1447  ret <2 x i8> %lshr
1448}
1449
1450define i32 @bool_add_lshr_uses(i1 %a, i1 %b) {
1451; CHECK-LABEL: @bool_add_lshr_uses(
1452; CHECK-NEXT:    [[ZEXT_A:%.*]] = zext i1 [[A:%.*]] to i32
1453; CHECK-NEXT:    call void @use(i32 [[ZEXT_A]])
1454; CHECK-NEXT:    [[ZEXT_B:%.*]] = zext i1 [[B:%.*]] to i32
1455; CHECK-NEXT:    call void @use(i32 [[ZEXT_B]])
1456; CHECK-NEXT:    [[LSHR:%.*]] = and i32 [[ZEXT_A]], [[ZEXT_B]]
1457; CHECK-NEXT:    ret i32 [[LSHR]]
1458;
1459  %zext.a = zext i1 %a to i32
1460  call void @use(i32 %zext.a)
1461  %zext.b = zext i1 %b to i32
1462  call void @use(i32 %zext.b)
1463  %add = add i32 %zext.a, %zext.b
1464  %lshr = lshr i32 %add, 1
1465  ret i32 %lshr
1466}
1467
1468define i32 @bool_add_lshr_uses2(i1 %a, i1 %b) {
1469; CHECK-LABEL: @bool_add_lshr_uses2(
1470; CHECK-NEXT:    [[ZEXT_A:%.*]] = zext i1 [[A:%.*]] to i32
1471; CHECK-NEXT:    [[ZEXT_B:%.*]] = zext i1 [[B:%.*]] to i32
1472; CHECK-NEXT:    call void @use(i32 [[ZEXT_B]])
1473; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i32 [[ZEXT_A]], [[ZEXT_B]]
1474; CHECK-NEXT:    call void @use(i32 [[ADD]])
1475; CHECK-NEXT:    [[LSHR:%.*]] = and i32 [[ZEXT_A]], [[ZEXT_B]]
1476; CHECK-NEXT:    ret i32 [[LSHR]]
1477;
1478  %zext.a = zext i1 %a to i32
1479  %zext.b = zext i1 %b to i32
1480  call void @use(i32 %zext.b)
1481  %add = add i32 %zext.a, %zext.b
1482  call void @use(i32 %add)
1483  %lshr = lshr i32 %add, 1
1484  ret i32 %lshr
1485}
1486
1487; negative test - too many extra uses
1488
1489define i32 @bool_add_lshr_uses3(i1 %a, i1 %b) {
1490; CHECK-LABEL: @bool_add_lshr_uses3(
1491; CHECK-NEXT:    [[ZEXT_A:%.*]] = zext i1 [[A:%.*]] to i32
1492; CHECK-NEXT:    call void @use(i32 [[ZEXT_A]])
1493; CHECK-NEXT:    [[ZEXT_B:%.*]] = zext i1 [[B:%.*]] to i32
1494; CHECK-NEXT:    call void @use(i32 [[ZEXT_B]])
1495; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw i32 [[ZEXT_A]], [[ZEXT_B]]
1496; CHECK-NEXT:    call void @use(i32 [[ADD]])
1497; CHECK-NEXT:    [[LSHR:%.*]] = and i32 [[ZEXT_A]], [[ZEXT_B]]
1498; CHECK-NEXT:    ret i32 [[LSHR]]
1499;
1500  %zext.a = zext i1 %a to i32
1501  call void @use(i32 %zext.a)
1502  %zext.b = zext i1 %b to i32
1503  call void @use(i32 %zext.b)
1504  %add = add i32 %zext.a, %zext.b
1505  call void @use(i32 %add)
1506  %lshr = lshr i32 %add, 1
1507  ret i32 %lshr
1508}
1509
1510; negative test
1511
1512define <2 x i8> @bool_add_lshr_vec_wrong_shift_amt(<2 x i1> %a, <2 x i1> %b) {
1513; CHECK-LABEL: @bool_add_lshr_vec_wrong_shift_amt(
1514; CHECK-NEXT:    [[ZEXT_A:%.*]] = zext <2 x i1> [[A:%.*]] to <2 x i8>
1515; CHECK-NEXT:    [[ZEXT_B:%.*]] = zext <2 x i1> [[B:%.*]] to <2 x i8>
1516; CHECK-NEXT:    [[ADD:%.*]] = add nuw nsw <2 x i8> [[ZEXT_A]], [[ZEXT_B]]
1517; CHECK-NEXT:    [[LSHR:%.*]] = lshr <2 x i8> [[ADD]], <i8 1, i8 2>
1518; CHECK-NEXT:    ret <2 x i8> [[LSHR]]
1519;
1520  %zext.a = zext <2 x i1> %a to <2 x i8>
1521  %zext.b = zext <2 x i1> %b to <2 x i8>
1522  %add = add <2 x i8> %zext.a, %zext.b
1523  %lshr = lshr <2 x i8> %add, <i8 1, i8 2>
1524  ret <2 x i8> %lshr
1525}
1526
1527define i32 @lowbits_of_lshr_mul(i64 %x) {
1528; CHECK-LABEL: @lowbits_of_lshr_mul(
1529; CHECK-NEXT:  entry:
1530; CHECK-NEXT:    [[TMP0:%.*]] = trunc i64 [[X:%.*]] to i32
1531; CHECK-NEXT:    [[CONV:%.*]] = mul i32 [[TMP0]], 15
1532; CHECK-NEXT:    ret i32 [[CONV]]
1533;
1534entry:
1535  %mul = mul i64 %x, 64424509440
1536  %shift = lshr i64 %mul, 32
1537  %conv = trunc i64 %shift to i32
1538  ret i32 %conv
1539}
1540
1541define i32 @lowbits_of_lshr_mul_mask(i32 %x) {
1542; CHECK-LABEL: @lowbits_of_lshr_mul_mask(
1543; CHECK-NEXT:  entry:
1544; CHECK-NEXT:    [[TMP0:%.*]] = mul i32 [[X:%.*]], 1600
1545; CHECK-NEXT:    [[CONV:%.*]] = and i32 [[TMP0]], 32704
1546; CHECK-NEXT:    ret i32 [[CONV]]
1547;
1548entry:
1549  %mul = mul i32 %x, 104857600
1550  %shift = lshr i32 %mul, 16
1551  %conv = and i32 %shift, 32767
1552  ret i32 %conv
1553}
1554
1555; Negative tests
1556
1557define i32 @lowbits_of_lshr_mul_mask_multiuse(i32 %x) {
1558; CHECK-LABEL: @lowbits_of_lshr_mul_mask_multiuse(
1559; CHECK-NEXT:  entry:
1560; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[X:%.*]], 104857600
1561; CHECK-NEXT:    call void @use(i32 [[MUL]])
1562; CHECK-NEXT:    [[SHIFT:%.*]] = lshr exact i32 [[MUL]], 16
1563; CHECK-NEXT:    [[CONV:%.*]] = and i32 [[SHIFT]], 32704
1564; CHECK-NEXT:    ret i32 [[CONV]]
1565;
1566entry:
1567  %mul = mul i32 %x, 104857600
1568  call void @use(i32 %mul)
1569  %shift = lshr i32 %mul, 16
1570  %conv = and i32 %shift, 32767
1571  ret i32 %conv
1572}
1573
1574define i32 @lowbits_of_lshr_mul_mask_indivisible(i32 %x) {
1575; CHECK-LABEL: @lowbits_of_lshr_mul_mask_indivisible(
1576; CHECK-NEXT:  entry:
1577; CHECK-NEXT:    [[MUL:%.*]] = mul i32 [[X:%.*]], 25600
1578; CHECK-NEXT:    [[SHIFT:%.*]] = lshr i32 [[MUL]], 16
1579; CHECK-NEXT:    [[CONV:%.*]] = and i32 [[SHIFT]], 32767
1580; CHECK-NEXT:    ret i32 [[CONV]]
1581;
1582entry:
1583  %mul = mul i32 %x, 25600
1584  %shift = lshr i32 %mul, 16
1585  %conv = and i32 %shift, 32767
1586  ret i32 %conv
1587}
1588