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;   (1 << NBits) - 1
8; Should be transformed into:
9;   ~(-(1 << NBits))
10; The `not` may end up being folded into `and`
11
12; ============================================================================ ;
13; Most basic positive tests
14; ============================================================================ ;
15
16; No no-wrap tags on shl
17
18define i32 @shl_add(i32 %NBits) {
19; CHECK-LABEL: @shl_add(
20; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
21; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
22; CHECK-NEXT:    ret i32 [[RET]]
23;
24  %setbit = shl i32 1, %NBits
25  %ret = add i32 %setbit, -1
26  ret i32 %ret
27}
28
29define i32 @shl_add_nsw(i32 %NBits) {
30; CHECK-LABEL: @shl_add_nsw(
31; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
32; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
33; CHECK-NEXT:    ret i32 [[RET]]
34;
35  %setbit = shl i32 1, %NBits
36  %ret = add nsw i32 %setbit, -1
37  ret i32 %ret
38}
39
40define i32 @shl_add_nuw(i32 %NBits) {
41; CHECK-LABEL: @shl_add_nuw(
42; CHECK-NEXT:    ret i32 -1
43;
44  %setbit = shl i32 1, %NBits
45  %ret = add nuw i32 %setbit, -1
46  ret i32 %ret
47}
48
49define i32 @shl_add_nsw_nuw(i32 %NBits) {
50; CHECK-LABEL: @shl_add_nsw_nuw(
51; CHECK-NEXT:    ret i32 -1
52;
53  %setbit = shl i32 1, %NBits
54  %ret = add nuw nsw i32 %setbit, -1
55  ret i32 %ret
56}
57
58; shl is nsw
59
60define i32 @shl_nsw_add(i32 %NBits) {
61; CHECK-LABEL: @shl_nsw_add(
62; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
63; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
64; CHECK-NEXT:    ret i32 [[RET]]
65;
66  %setbit = shl nsw i32 1, %NBits
67  %ret = add i32 %setbit, -1
68  ret i32 %ret
69}
70
71define i32 @shl_nsw_add_nsw(i32 %NBits) {
72; CHECK-LABEL: @shl_nsw_add_nsw(
73; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
74; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
75; CHECK-NEXT:    ret i32 [[RET]]
76;
77  %setbit = shl nsw i32 1, %NBits
78  %ret = add nsw i32 %setbit, -1
79  ret i32 %ret
80}
81
82define i32 @shl_nsw_add_nuw(i32 %NBits) {
83; CHECK-LABEL: @shl_nsw_add_nuw(
84; CHECK-NEXT:    ret i32 -1
85;
86  %setbit = shl nsw i32 1, %NBits
87  %ret = add nuw i32 %setbit, -1
88  ret i32 %ret
89}
90
91define i32 @shl_nsw_add_nsw_nuw(i32 %NBits) {
92; CHECK-LABEL: @shl_nsw_add_nsw_nuw(
93; CHECK-NEXT:    ret i32 -1
94;
95  %setbit = shl nsw i32 1, %NBits
96  %ret = add nuw nsw i32 %setbit, -1
97  ret i32 %ret
98}
99
100; shl is nuw
101
102define i32 @shl_nuw_add(i32 %NBits) {
103; CHECK-LABEL: @shl_nuw_add(
104; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
105; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
106; CHECK-NEXT:    ret i32 [[RET]]
107;
108  %setbit = shl nuw i32 1, %NBits
109  %ret = add i32 %setbit, -1
110  ret i32 %ret
111}
112
113define i32 @shl_nuw_add_nsw(i32 %NBits) {
114; CHECK-LABEL: @shl_nuw_add_nsw(
115; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
116; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
117; CHECK-NEXT:    ret i32 [[RET]]
118;
119  %setbit = shl nuw i32 1, %NBits
120  %ret = add nsw i32 %setbit, -1
121  ret i32 %ret
122}
123
124define i32 @shl_nuw_add_nuw(i32 %NBits) {
125; CHECK-LABEL: @shl_nuw_add_nuw(
126; CHECK-NEXT:    ret i32 -1
127;
128  %setbit = shl nuw i32 1, %NBits
129  %ret = add nuw i32 %setbit, -1
130  ret i32 %ret
131}
132
133define i32 @shl_nuw_add_nsw_nuw(i32 %NBits) {
134; CHECK-LABEL: @shl_nuw_add_nsw_nuw(
135; CHECK-NEXT:    ret i32 -1
136;
137  %setbit = shl nuw i32 1, %NBits
138  %ret = add nuw nsw i32 %setbit, -1
139  ret i32 %ret
140}
141
142; shl is nuw nsw
143
144define i32 @shl_nsw_nuw_add(i32 %NBits) {
145; CHECK-LABEL: @shl_nsw_nuw_add(
146; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
147; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
148; CHECK-NEXT:    ret i32 [[RET]]
149;
150  %setbit = shl nuw nsw i32 1, %NBits
151  %ret = add i32 %setbit, -1
152  ret i32 %ret
153}
154
155define i32 @shl_nsw_nuw_add_nsw(i32 %NBits) {
156; CHECK-LABEL: @shl_nsw_nuw_add_nsw(
157; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
158; CHECK-NEXT:    [[RET:%.*]] = xor i32 [[NOTMASK]], -1
159; CHECK-NEXT:    ret i32 [[RET]]
160;
161  %setbit = shl nuw nsw i32 1, %NBits
162  %ret = add nsw i32 %setbit, -1
163  ret i32 %ret
164}
165
166define i32 @shl_nsw_nuw_add_nuw(i32 %NBits) {
167; CHECK-LABEL: @shl_nsw_nuw_add_nuw(
168; CHECK-NEXT:    ret i32 -1
169;
170  %setbit = shl nuw nsw i32 1, %NBits
171  %ret = add nuw i32 %setbit, -1
172  ret i32 %ret
173}
174
175define i32 @shl_nsw_nuw_add_nsw_nuw(i32 %NBits) {
176; CHECK-LABEL: @shl_nsw_nuw_add_nsw_nuw(
177; CHECK-NEXT:    ret i32 -1
178;
179  %setbit = shl nuw nsw i32 1, %NBits
180  %ret = add nuw nsw i32 %setbit, -1
181  ret i32 %ret
182}
183
184; ============================================================================ ;
185; Vectors
186; ============================================================================ ;
187
188define <2 x i32> @shl_add_vec(<2 x i32> %NBits) {
189; CHECK-LABEL: @shl_add_vec(
190; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw <2 x i32> <i32 -1, i32 -1>, [[NBITS:%.*]]
191; CHECK-NEXT:    [[RET:%.*]] = xor <2 x i32> [[NOTMASK]], <i32 -1, i32 -1>
192; CHECK-NEXT:    ret <2 x i32> [[RET]]
193;
194  %setbit = shl <2 x i32> <i32 1, i32 1>, %NBits
195  %ret = add <2 x i32> %setbit, <i32 -1, i32 -1>
196  ret <2 x i32> %ret
197}
198
199define <3 x i32> @shl_add_vec_undef0(<3 x i32> %NBits) {
200; CHECK-LABEL: @shl_add_vec_undef0(
201; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw <3 x i32> <i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]]
202; CHECK-NEXT:    [[RET:%.*]] = xor <3 x i32> [[NOTMASK]], <i32 -1, i32 -1, i32 -1>
203; CHECK-NEXT:    ret <3 x i32> [[RET]]
204;
205  %setbit = shl <3 x i32> <i32 1, i32 undef, i32 1>, %NBits
206  %ret = add <3 x i32> %setbit, <i32 -1, i32 -1, i32 -1>
207  ret <3 x i32> %ret
208}
209
210define <3 x i32> @shl_add_vec_undef1(<3 x i32> %NBits) {
211; CHECK-LABEL: @shl_add_vec_undef1(
212; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw <3 x i32> <i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]]
213; CHECK-NEXT:    [[RET:%.*]] = xor <3 x i32> [[NOTMASK]], <i32 -1, i32 -1, i32 -1>
214; CHECK-NEXT:    ret <3 x i32> [[RET]]
215;
216  %setbit = shl <3 x i32> <i32 1, i32 1, i32 1>, %NBits
217  %ret = add <3 x i32> %setbit, <i32 -1, i32 undef, i32 -1>
218  ret <3 x i32> %ret
219}
220
221define <3 x i32> @shl_add_vec_undef2(<3 x i32> %NBits) {
222; CHECK-LABEL: @shl_add_vec_undef2(
223; CHECK-NEXT:    [[NOTMASK:%.*]] = shl nsw <3 x i32> <i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]]
224; CHECK-NEXT:    [[RET:%.*]] = xor <3 x i32> [[NOTMASK]], <i32 -1, i32 -1, i32 -1>
225; CHECK-NEXT:    ret <3 x i32> [[RET]]
226;
227  %setbit = shl <3 x i32> <i32 1, i32 undef, i32 1>, %NBits
228  %ret = add <3 x i32> %setbit, <i32 -1, i32 undef, i32 -1>
229  ret <3 x i32> %ret
230}
231
232; ============================================================================ ;
233; Negative tests. Should not be folded.
234; ============================================================================ ;
235
236declare void @use32(i32)
237
238; One use only.
239define i32 @bad_oneuse0(i32 %NBits) {
240; CHECK-LABEL: @bad_oneuse0(
241; CHECK-NEXT:    [[SETBIT:%.*]] = shl i32 1, [[NBITS:%.*]]
242; CHECK-NEXT:    call void @use32(i32 [[SETBIT]])
243; CHECK-NEXT:    [[RET:%.*]] = add i32 [[SETBIT]], -1
244; CHECK-NEXT:    ret i32 [[RET]]
245;
246  %setbit = shl i32 1, %NBits
247  call void @use32(i32 %setbit)
248  %ret = add i32 %setbit, -1
249  ret i32 %ret
250}
251
252; shift base is not `1` constant
253
254define i32 @bad_shl(i32 %base, i32 %NBits) {
255; CHECK-LABEL: @bad_shl(
256; CHECK-NEXT:    [[SETBIT:%.*]] = shl i32 [[BASE:%.*]], [[NBITS:%.*]]
257; CHECK-NEXT:    [[RET:%.*]] = add i32 [[SETBIT]], -1
258; CHECK-NEXT:    ret i32 [[RET]]
259;
260  %setbit = shl i32 %base, %NBits ; %base instead of 1
261  %ret = add i32 %setbit, -1
262  ret i32 %ret
263}
264
265; Second `add` operand is not `-1` constant
266
267define i32 @bad_add0(i32 %NBits, i32 %addop2) {
268; CHECK-LABEL: @bad_add0(
269; CHECK-NEXT:    [[SETBIT:%.*]] = shl i32 1, [[NBITS:%.*]]
270; CHECK-NEXT:    [[RET:%.*]] = add i32 [[SETBIT]], [[ADDOP2:%.*]]
271; CHECK-NEXT:    ret i32 [[RET]]
272;
273  %setbit = shl i32 1, %NBits
274  %ret = add i32 %setbit, %addop2
275  ret i32 %ret
276}
277
278; Bad add constant
279
280define i32 @bad_add1(i32 %NBits) {
281; CHECK-LABEL: @bad_add1(
282; CHECK-NEXT:    [[SETBIT:%.*]] = shl i32 1, [[NBITS:%.*]]
283; CHECK-NEXT:    [[RET:%.*]] = add i32 [[SETBIT]], 1
284; CHECK-NEXT:    ret i32 [[RET]]
285;
286  %setbit = shl i32 1, %NBits
287  %ret = add i32 %setbit, 1 ; not -1
288  ret i32 %ret
289}
290
291define i32 @bad_add2(i32 %NBits) {
292; CHECK-LABEL: @bad_add2(
293; CHECK-NEXT:    [[SETBIT:%.*]] = shl i32 1, [[NBITS:%.*]]
294; CHECK-NEXT:    [[RET:%.*]] = add i32 [[SETBIT]], -2
295; CHECK-NEXT:    ret i32 [[RET]]
296;
297  %setbit = shl i32 1, %NBits
298  %ret = add i32 %setbit, -2 ; not -1
299  ret i32 %ret
300}
301