1 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2 ; RUN: opt < %s -passes=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
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 nsw i32 -1, [[NBITS:%.*]]
21 ; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1
22 ; CHECK-NEXT: [[T2:%.*]] = and i32 [[X:%.*]], [[T1]]
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
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
43 define i32 @t1_bigger_shift(i32 %x, i32 %nbits) {
44 ; CHECK-LABEL: @t1_bigger_shift(
45 ; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
46 ; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1
47 ; CHECK-NEXT: [[T2:%.*]] = and i32 [[X:%.*]], [[T1]]
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
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
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 nsw i32 -1, [[T0]]
72 ; CHECK-NEXT: [[T2:%.*]] = xor i32 [[T1]], -1
73 ; CHECK-NEXT: [[T3:%.*]] = and i32 [[X:%.*]], [[T2]]
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
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
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 nsw <3 x i32> splat (i32 -1), [[NBITS:%.*]]
104 ; CHECK-NEXT: [[T2:%.*]] = xor <3 x i32> [[T1]], splat (i32 -1)
105 ; CHECK-NEXT: [[T3:%.*]] = and <3 x i32> [[X:%.*]], [[T2]]
106 ; CHECK-NEXT: [[T4:%.*]] = sub <3 x i32> splat (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
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 nsw <3 x i32> splat (i32 -1), [[T0]]
133 ; CHECK-NEXT: [[T2:%.*]] = xor <3 x i32> [[T1]], splat (i32 -1)
134 ; CHECK-NEXT: [[T3:%.*]] = and <3 x i32> [[X:%.*]], [[T2]]
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
158 define <3 x i32> @t5_vec_poison(<3 x i32> %x, <3 x i32> %nbits) {
159 ; CHECK-LABEL: @t5_vec_poison(
160 ; CHECK-NEXT: [[T1:%.*]] = shl nsw <3 x i32> <i32 -1, i32 poison, i32 -1>, [[NBITS:%.*]]
161 ; CHECK-NEXT: [[T2:%.*]] = xor <3 x i32> [[T1]], <i32 -1, i32 poison, i32 -1>
162 ; CHECK-NEXT: [[T3:%.*]] = and <3 x i32> [[X:%.*]], [[T2]]
163 ; CHECK-NEXT: [[T4:%.*]] = sub <3 x i32> <i32 32, i32 poison, 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 poison, i32 0>
173 %t1 = shl <3 x i32> <i32 -1, i32 poison, i32 -1>, %t0
174 %t2 = xor <3 x i32> %t1, <i32 -1, i32 poison, i32 -1>
175 %t3 = and <3 x i32> %t2, %x
176 %t4 = sub <3 x i32> <i32 32, i32 poison, 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
190 define i32 @t6_commutativity0(i32 %nbits) {
191 ; CHECK-LABEL: @t6_commutativity0(
192 ; CHECK-NEXT: [[X:%.*]] = call i32 @gen32()
193 ; CHECK-NEXT: [[T0:%.*]] = shl nsw 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
217 define i32 @t7_commutativity1(i32 %nbits0, i32 %nbits1) {
218 ; CHECK-LABEL: @t7_commutativity1(
219 ; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS0:%.*]]
220 ; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1
221 ; CHECK-NEXT: [[T2:%.*]] = shl nsw 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
249 define i32 @t8_commutativity2(i32 %nbits0, i32 %nbits1) {
250 ; CHECK-LABEL: @t8_commutativity2(
251 ; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS0:%.*]]
252 ; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1
253 ; CHECK-NEXT: [[T2:%.*]] = shl nsw 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
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 nsw i32 -1, [[NBITS:%.*]]
287 ; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1
288 ; CHECK-NEXT: [[T2:%.*]] = and i32 [[X:%.*]], [[T1]]
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
309 define i32 @t10_nsw(i32 %x, i32 %nbits) {
310 ; CHECK-LABEL: @t10_nsw(
311 ; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
312 ; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1
313 ; CHECK-NEXT: [[T2:%.*]] = and i32 [[X:%.*]], [[T1]]
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
334 define i32 @t11_nuw_nsw(i32 %x, i32 %nbits) {
335 ; CHECK-LABEL: @t11_nuw_nsw(
336 ; CHECK-NEXT: [[T0:%.*]] = shl nsw i32 -1, [[NBITS:%.*]]
337 ; CHECK-NEXT: [[T1:%.*]] = xor i32 [[T0]], -1
338 ; CHECK-NEXT: [[T2:%.*]] = and i32 [[X:%.*]], [[T1]]
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
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 [[X:%.*]], [[T1]]
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