[DAGCombiner] Add target hook function to decide folding (mul (add x, c1), c2)
[llvm-project.git] / llvm / test / Transforms / InstCombine / redundant-left-shift-input-masking-variant-b.ll
blobb0e23bcf607041e320b1a08ec9589935ca89b597
1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2 ; RUN: opt < %s -instcombine -S | FileCheck %s
4 ; If we have some pattern that leaves only some low bits set, and then performs
5 ; left-shift of those bits, if none of the bits that are left after the final
6 ; shift are modified by the mask, we can omit the mask.
8 ; There are many variants to this pattern:
9 ;   b)  (x & (~(-1 << maskNbits))) << shiftNbits
10 ; simplify to:
11 ;   x << shiftNbits
12 ; iff (maskNbits+shiftNbits) u>= bitwidth(x)
14 ; Simple tests. We don't care about extra uses.
16 declare void @use32(i32)
18 define i32 @t0_basic(i32 %x, i32 %nbits) {
19 ; CHECK-LABEL: @t0_basic(
20 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
21 ; CHECK-NEXT:    [[T1:%.*]] = xor i32 [[T0]], -1
22 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]
23 ; CHECK-NEXT:    [[T3:%.*]] = sub i32 32, [[NBITS]]
24 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
25 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
26 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
27 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
28 ; CHECK-NEXT:    [[T4:%.*]] = shl i32 [[X]], [[T3]]
29 ; CHECK-NEXT:    ret i32 [[T4]]
31   %t0 = shl i32 -1, %nbits
32   %t1 = xor i32 %t0, -1
33   %t2 = and i32 %t1, %x
34   %t3 = sub i32 32, %nbits
35   call void @use32(i32 %t0)
36   call void @use32(i32 %t1)
37   call void @use32(i32 %t2)
38   call void @use32(i32 %t3)
39   %t4 = shl i32 %t2, %t3
40   ret i32 %t4
43 define i32 @t1_bigger_shift(i32 %x, i32 %nbits) {
44 ; CHECK-LABEL: @t1_bigger_shift(
45 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
46 ; CHECK-NEXT:    [[T1:%.*]] = xor i32 [[T0]], -1
47 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]
48 ; CHECK-NEXT:    [[T3:%.*]] = sub i32 33, [[NBITS]]
49 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
50 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
51 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
52 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
53 ; CHECK-NEXT:    [[T4:%.*]] = shl i32 [[X]], [[T3]]
54 ; CHECK-NEXT:    ret i32 [[T4]]
56   %t0 = shl i32 -1, %nbits
57   %t1 = xor i32 %t0, -1
58   %t2 = and i32 %t1, %x
59   %t3 = sub i32 33, %nbits ; subtracting from bitwidth+1
60   call void @use32(i32 %t0)
61   call void @use32(i32 %t1)
62   call void @use32(i32 %t2)
63   call void @use32(i32 %t3)
64   %t4 = shl i32 %t2, %t3
65   ret i32 %t4
68 define i32 @t2_bigger_mask(i32 %x, i32 %nbits) {
69 ; CHECK-LABEL: @t2_bigger_mask(
70 ; CHECK-NEXT:    [[T0:%.*]] = add i32 [[NBITS:%.*]], 1
71 ; CHECK-NEXT:    [[T1:%.*]] = shl i32 -1, [[T0]]
72 ; CHECK-NEXT:    [[T2:%.*]] = xor i32 [[T1]], -1
73 ; CHECK-NEXT:    [[T3:%.*]] = and i32 [[T2]], [[X:%.*]]
74 ; CHECK-NEXT:    [[T4:%.*]] = sub i32 32, [[NBITS]]
75 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
76 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
77 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
78 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
79 ; CHECK-NEXT:    call void @use32(i32 [[T4]])
80 ; CHECK-NEXT:    [[T5:%.*]] = shl i32 [[X]], [[T4]]
81 ; CHECK-NEXT:    ret i32 [[T5]]
83   %t0 = add i32 %nbits, 1
84   %t1 = shl i32 -1, %t0 ; shifting by nbits+1
85   %t2 = xor i32 %t1, -1
86   %t3 = and i32 %t2, %x
87   %t4 = sub i32 32, %nbits
88   call void @use32(i32 %t0)
89   call void @use32(i32 %t1)
90   call void @use32(i32 %t2)
91   call void @use32(i32 %t3)
92   call void @use32(i32 %t4)
93   %t5 = shl i32 %t3, %t4
94   ret i32 %t5
97 ; Vectors
99 declare void @use3xi32(<3 x i32>)
101 define <3 x i32> @t3_vec_splat(<3 x i32> %x, <3 x i32> %nbits) {
102 ; CHECK-LABEL: @t3_vec_splat(
103 ; CHECK-NEXT:    [[T1:%.*]] = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, [[NBITS:%.*]]
104 ; CHECK-NEXT:    [[T2:%.*]] = xor <3 x i32> [[T1]], <i32 -1, i32 -1, i32 -1>
105 ; CHECK-NEXT:    [[T3:%.*]] = and <3 x i32> [[T2]], [[X:%.*]]
106 ; CHECK-NEXT:    [[T4:%.*]] = sub <3 x i32> <i32 32, i32 32, i32 32>, [[NBITS]]
107 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[NBITS]])
108 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T1]])
109 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T2]])
110 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T3]])
111 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T4]])
112 ; CHECK-NEXT:    [[T5:%.*]] = shl <3 x i32> [[X]], [[T4]]
113 ; CHECK-NEXT:    ret <3 x i32> [[T5]]
115   %t0 = add <3 x i32> %nbits, <i32 0, i32 0, i32 0>
116   %t1 = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, %t0
117   %t2 = xor <3 x i32> %t1, <i32 -1, i32 -1, i32 -1>
118   %t3 = and <3 x i32> %t2, %x
119   %t4 = sub <3 x i32> <i32 32, i32 32, i32 32>, %nbits
120   call void @use3xi32(<3 x i32> %t0)
121   call void @use3xi32(<3 x i32> %t1)
122   call void @use3xi32(<3 x i32> %t2)
123   call void @use3xi32(<3 x i32> %t3)
124   call void @use3xi32(<3 x i32> %t4)
125   %t5 = shl <3 x i32> %t3, %t4
126   ret <3 x i32> %t5
129 define <3 x i32> @t4_vec_nonsplat(<3 x i32> %x, <3 x i32> %nbits) {
130 ; CHECK-LABEL: @t4_vec_nonsplat(
131 ; CHECK-NEXT:    [[T0:%.*]] = add <3 x i32> [[NBITS:%.*]], <i32 -1, i32 0, i32 1>
132 ; CHECK-NEXT:    [[T1:%.*]] = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, [[T0]]
133 ; CHECK-NEXT:    [[T2:%.*]] = xor <3 x i32> [[T1]], <i32 -1, i32 -1, i32 -1>
134 ; CHECK-NEXT:    [[T3:%.*]] = and <3 x i32> [[T2]], [[X:%.*]]
135 ; CHECK-NEXT:    [[T4:%.*]] = sub <3 x i32> <i32 33, i32 32, i32 32>, [[NBITS]]
136 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T0]])
137 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T1]])
138 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T2]])
139 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T3]])
140 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T4]])
141 ; CHECK-NEXT:    [[T5:%.*]] = shl <3 x i32> [[X]], [[T4]]
142 ; CHECK-NEXT:    ret <3 x i32> [[T5]]
144   %t0 = add <3 x i32> %nbits, <i32 -1, i32 0, i32 1>
145   %t1 = shl <3 x i32> <i32 -1, i32 -1, i32 -1>, %t0
146   %t2 = xor <3 x i32> %t1, <i32 -1, i32 -1, i32 -1>
147   %t3 = and <3 x i32> %t2, %x
148   %t4 = sub <3 x i32> <i32 33, i32 32, i32 32>, %nbits
149   call void @use3xi32(<3 x i32> %t0)
150   call void @use3xi32(<3 x i32> %t1)
151   call void @use3xi32(<3 x i32> %t2)
152   call void @use3xi32(<3 x i32> %t3)
153   call void @use3xi32(<3 x i32> %t4)
154   %t5 = shl <3 x i32> %t3, %t4
155   ret <3 x i32> %t5
158 define <3 x i32> @t5_vec_undef(<3 x i32> %x, <3 x i32> %nbits) {
159 ; CHECK-LABEL: @t5_vec_undef(
160 ; CHECK-NEXT:    [[T1:%.*]] = shl <3 x i32> <i32 -1, i32 undef, i32 -1>, [[NBITS:%.*]]
161 ; CHECK-NEXT:    [[T2:%.*]] = xor <3 x i32> [[T1]], <i32 -1, i32 undef, i32 -1>
162 ; CHECK-NEXT:    [[T3:%.*]] = and <3 x i32> [[T2]], [[X:%.*]]
163 ; CHECK-NEXT:    [[T4:%.*]] = sub <3 x i32> <i32 32, i32 undef, i32 32>, [[NBITS]]
164 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[NBITS]])
165 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T1]])
166 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T2]])
167 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T3]])
168 ; CHECK-NEXT:    call void @use3xi32(<3 x i32> [[T4]])
169 ; CHECK-NEXT:    [[T5:%.*]] = shl <3 x i32> [[X]], [[T4]]
170 ; CHECK-NEXT:    ret <3 x i32> [[T5]]
172   %t0 = add <3 x i32> %nbits, <i32 0, i32 undef, i32 0>
173   %t1 = shl <3 x i32> <i32 -1, i32 undef, i32 -1>, %t0
174   %t2 = xor <3 x i32> %t1, <i32 -1, i32 undef, i32 -1>
175   %t3 = and <3 x i32> %t2, %x
176   %t4 = sub <3 x i32> <i32 32, i32 undef, i32 32>, %nbits
177   call void @use3xi32(<3 x i32> %t0)
178   call void @use3xi32(<3 x i32> %t1)
179   call void @use3xi32(<3 x i32> %t2)
180   call void @use3xi32(<3 x i32> %t3)
181   call void @use3xi32(<3 x i32> %t4)
182   %t5 = shl <3 x i32> %t3, %t4
183   ret <3 x i32> %t5
186 ; Commutativity
188 declare i32 @gen32()
190 define i32 @t6_commutativity0(i32 %nbits) {
191 ; CHECK-LABEL: @t6_commutativity0(
192 ; CHECK-NEXT:    [[X:%.*]] = call i32 @gen32()
193 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
194 ; CHECK-NEXT:    [[T1:%.*]] = xor i32 [[T0]], -1
195 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[X]], [[T1]]
196 ; CHECK-NEXT:    [[T3:%.*]] = sub i32 32, [[NBITS]]
197 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
198 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
199 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
200 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
201 ; CHECK-NEXT:    [[T4:%.*]] = shl i32 [[X]], [[T3]]
202 ; CHECK-NEXT:    ret i32 [[T4]]
204   %x = call i32 @gen32()
205   %t0 = shl i32 -1, %nbits
206   %t1 = xor i32 %t0, -1
207   %t2 = and i32 %x, %t1 ; swapped
208   %t3 = sub i32 32, %nbits
209   call void @use32(i32 %t0)
210   call void @use32(i32 %t1)
211   call void @use32(i32 %t2)
212   call void @use32(i32 %t3)
213   %t4 = shl i32 %t2, %t3
214   ret i32 %t4
217 define i32 @t7_commutativity1(i32 %nbits0, i32 %nbits1) {
218 ; CHECK-LABEL: @t7_commutativity1(
219 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS0:%.*]]
220 ; CHECK-NEXT:    [[T1:%.*]] = xor i32 [[T0]], -1
221 ; CHECK-NEXT:    [[T2:%.*]] = shl i32 -1, [[NBITS1:%.*]]
222 ; CHECK-NEXT:    [[T3:%.*]] = xor i32 [[T2]], -1
223 ; CHECK-NEXT:    [[T4:%.*]] = and i32 [[T3]], [[T1]]
224 ; CHECK-NEXT:    [[T5:%.*]] = sub i32 32, [[NBITS0]]
225 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
226 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
227 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
228 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
229 ; CHECK-NEXT:    call void @use32(i32 [[T4]])
230 ; CHECK-NEXT:    call void @use32(i32 [[T5]])
231 ; CHECK-NEXT:    [[T6:%.*]] = shl i32 [[T4]], [[T5]]
232 ; CHECK-NEXT:    ret i32 [[T6]]
234   %t0 = shl i32 -1, %nbits0
235   %t1 = xor i32 %t0, -1
236   %t2 = shl i32 -1, %nbits1
237   %t3 = xor i32 %t2, -1
238   %t4 = and i32 %t3, %t1 ; both hands of 'and' could be mask..
239   %t5 = sub i32 32, %nbits0
240   call void @use32(i32 %t0)
241   call void @use32(i32 %t1)
242   call void @use32(i32 %t2)
243   call void @use32(i32 %t3)
244   call void @use32(i32 %t4)
245   call void @use32(i32 %t5)
246   %t6 = shl i32 %t4, %t5
247   ret i32 %t6
249 define i32 @t8_commutativity2(i32 %nbits0, i32 %nbits1) {
250 ; CHECK-LABEL: @t8_commutativity2(
251 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS0:%.*]]
252 ; CHECK-NEXT:    [[T1:%.*]] = xor i32 [[T0]], -1
253 ; CHECK-NEXT:    [[T2:%.*]] = shl i32 -1, [[NBITS1:%.*]]
254 ; CHECK-NEXT:    [[T3:%.*]] = xor i32 [[T2]], -1
255 ; CHECK-NEXT:    [[T4:%.*]] = and i32 [[T3]], [[T1]]
256 ; CHECK-NEXT:    [[T5:%.*]] = sub i32 32, [[NBITS1]]
257 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
258 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
259 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
260 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
261 ; CHECK-NEXT:    call void @use32(i32 [[T4]])
262 ; CHECK-NEXT:    call void @use32(i32 [[T5]])
263 ; CHECK-NEXT:    [[T6:%.*]] = shl i32 [[T1]], [[T5]]
264 ; CHECK-NEXT:    ret i32 [[T6]]
266   %t0 = shl i32 -1, %nbits0
267   %t1 = xor i32 %t0, -1
268   %t2 = shl i32 -1, %nbits1
269   %t3 = xor i32 %t2, -1
270   %t4 = and i32 %t3, %t1 ; both hands of 'and' could be mask..
271   %t5 = sub i32 32, %nbits1
272   call void @use32(i32 %t0)
273   call void @use32(i32 %t1)
274   call void @use32(i32 %t2)
275   call void @use32(i32 %t3)
276   call void @use32(i32 %t4)
277   call void @use32(i32 %t5)
278   %t6 = shl i32 %t4, %t5
279   ret i32 %t6
282 ; Fast-math flags. We must not preserve them!
284 define i32 @t9_nuw(i32 %x, i32 %nbits) {
285 ; CHECK-LABEL: @t9_nuw(
286 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
287 ; CHECK-NEXT:    [[T1:%.*]] = xor i32 [[T0]], -1
288 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]
289 ; CHECK-NEXT:    [[T3:%.*]] = sub i32 32, [[NBITS]]
290 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
291 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
292 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
293 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
294 ; CHECK-NEXT:    [[T4:%.*]] = shl i32 [[X]], [[T3]]
295 ; CHECK-NEXT:    ret i32 [[T4]]
297   %t0 = shl i32 -1, %nbits
298   %t1 = xor i32 %t0, -1
299   %t2 = and i32 %t1, %x
300   %t3 = sub i32 32, %nbits
301   call void @use32(i32 %t0)
302   call void @use32(i32 %t1)
303   call void @use32(i32 %t2)
304   call void @use32(i32 %t3)
305   %t4 = shl nuw i32 %t2, %t3
306   ret i32 %t4
309 define i32 @t10_nsw(i32 %x, i32 %nbits) {
310 ; CHECK-LABEL: @t10_nsw(
311 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
312 ; CHECK-NEXT:    [[T1:%.*]] = xor i32 [[T0]], -1
313 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]
314 ; CHECK-NEXT:    [[T3:%.*]] = sub i32 32, [[NBITS]]
315 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
316 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
317 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
318 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
319 ; CHECK-NEXT:    [[T4:%.*]] = shl i32 [[X]], [[T3]]
320 ; CHECK-NEXT:    ret i32 [[T4]]
322   %t0 = shl i32 -1, %nbits
323   %t1 = xor i32 %t0, -1
324   %t2 = and i32 %t1, %x
325   %t3 = sub i32 32, %nbits
326   call void @use32(i32 %t0)
327   call void @use32(i32 %t1)
328   call void @use32(i32 %t2)
329   call void @use32(i32 %t3)
330   %t4 = shl nsw i32 %t2, %t3
331   ret i32 %t4
334 define i32 @t11_nuw_nsw(i32 %x, i32 %nbits) {
335 ; CHECK-LABEL: @t11_nuw_nsw(
336 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -1, [[NBITS:%.*]]
337 ; CHECK-NEXT:    [[T1:%.*]] = xor i32 [[T0]], -1
338 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]
339 ; CHECK-NEXT:    [[T3:%.*]] = sub i32 32, [[NBITS]]
340 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
341 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
342 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
343 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
344 ; CHECK-NEXT:    [[T4:%.*]] = shl i32 [[X]], [[T3]]
345 ; CHECK-NEXT:    ret i32 [[T4]]
347   %t0 = shl i32 -1, %nbits
348   %t1 = xor i32 %t0, -1
349   %t2 = and i32 %t1, %x
350   %t3 = sub i32 32, %nbits
351   call void @use32(i32 %t0)
352   call void @use32(i32 %t1)
353   call void @use32(i32 %t2)
354   call void @use32(i32 %t3)
355   %t4 = shl nuw nsw i32 %t2, %t3
356   ret i32 %t4
359 ; Negative tests
361 define i32 @n12_not_minus_one(i32 %x, i32 %nbits) {
362 ; CHECK-LABEL: @n12_not_minus_one(
363 ; CHECK-NEXT:    [[T0:%.*]] = shl i32 -2, [[NBITS:%.*]]
364 ; CHECK-NEXT:    [[T1:%.*]] = xor i32 [[T0]], -1
365 ; CHECK-NEXT:    [[T2:%.*]] = and i32 [[T1]], [[X:%.*]]
366 ; CHECK-NEXT:    [[T3:%.*]] = sub i32 32, [[NBITS]]
367 ; CHECK-NEXT:    call void @use32(i32 [[T0]])
368 ; CHECK-NEXT:    call void @use32(i32 [[T1]])
369 ; CHECK-NEXT:    call void @use32(i32 [[T2]])
370 ; CHECK-NEXT:    call void @use32(i32 [[T3]])
371 ; CHECK-NEXT:    [[T4:%.*]] = shl i32 [[T2]], [[T3]]
372 ; CHECK-NEXT:    ret i32 [[T4]]
374   %t0 = shl i32 -2, %nbits ; shifting not '-1'
375   %t1 = xor i32 %t0, -1
376   %t2 = and i32 %t1, %x
377   %t3 = sub i32 32, %nbits
378   call void @use32(i32 %t0)
379   call void @use32(i32 %t1)
380   call void @use32(i32 %t2)
381   call void @use32(i32 %t3)
382   %t4 = shl i32 %t2, %t3
383   ret i32 %t4