xref: /llvm-project/llvm/test/Analysis/ValueTracking/recurrence-knownbits.ll (revision fef6613e9fc05bca8e315c65e8f8da796860a3cf) 
1; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
2; RUN: opt < %s -passes=instcombine -S | FileCheck %s
3
4define i64 @test_lshr(i1 %c) {
5; CHECK-LABEL: @test_lshr(
6; CHECK-NEXT:  entry:
7; CHECK-NEXT:    br label [[LOOP:%.*]]
8; CHECK:       loop:
9; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
10; CHECK:       exit:
11; CHECK-NEXT:    ret i64 1023
12;
13entry:
14  br label %loop
15loop:
16  %iv.lshr = phi i64 [1023, %entry], [%iv.lshr.next, %loop]
17  %iv.lshr.next = lshr i64 %iv.lshr, 1
18  br i1 %c, label %exit, label %loop
19exit:
20  %res = or i64 %iv.lshr, 1023
21  ret i64 %res
22}
23
24define i64 @test_add(i1 %c) {
25; CHECK-LABEL: @test_add(
26; CHECK-NEXT:  entry:
27; CHECK-NEXT:    br label [[LOOP:%.*]]
28; CHECK:       loop:
29; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
30; CHECK:       exit:
31; CHECK-NEXT:    ret i64 0
32;
33entry:
34  br label %loop
35loop:
36  %iv = phi i64 [8, %entry], [%iv.next, %loop]
37  %iv.next = add nuw i64 %iv, 4
38  br i1 %c, label %exit, label %loop
39exit:
40  %res = and i64 %iv, 1
41  ret i64 %res
42}
43
44define i64 @test_sub(i1 %c) {
45; CHECK-LABEL: @test_sub(
46; CHECK-NEXT:  entry:
47; CHECK-NEXT:    br label [[LOOP:%.*]]
48; CHECK:       loop:
49; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
50; CHECK:       exit:
51; CHECK-NEXT:    ret i64 0
52;
53entry:
54  br label %loop
55loop:
56  %iv = phi i64 [8, %entry], [%iv.next, %loop]
57  %iv.next = sub nuw i64 %iv, 4
58  br i1 %c, label %exit, label %loop
59exit:
60  %res = and i64 %iv, 1
61  ret i64 %res
62}
63
64define i64 @test_mul(i1 %c) {
65; CHECK-LABEL: @test_mul(
66; CHECK-NEXT:  entry:
67; CHECK-NEXT:    br label [[LOOP:%.*]]
68; CHECK:       loop:
69; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
70; CHECK:       exit:
71; CHECK-NEXT:    ret i64 0
72;
73entry:
74  br label %loop
75loop:
76  %iv = phi i64 [8, %entry], [%iv.next, %loop]
77  %iv.next = mul i64 %iv, 2
78  br i1 %c, label %exit, label %loop
79exit:
80  %res = and i64 %iv, 2
81  ret i64 %res
82}
83
84define i64 @test_udiv(i1 %c) {
85; CHECK-LABEL: @test_udiv(
86; CHECK-NEXT:  entry:
87; CHECK-NEXT:    br label [[LOOP:%.*]]
88; CHECK:       loop:
89; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
90; CHECK:       exit:
91; CHECK-NEXT:    ret i64 0
92;
93entry:
94  br label %loop
95loop:
96  %iv = phi i64 [9, %entry], [%iv.next, %loop]
97  %iv.next = udiv i64 %iv, 3
98  br i1 %c, label %exit, label %loop
99exit:
100  %res = and i64 %iv, 16
101  ret i64 %res
102}
103
104define i64 @test_udiv_neg(i1 %c) {
105; CHECK-LABEL: @test_udiv_neg(
106; CHECK-NEXT:  entry:
107; CHECK-NEXT:    br label [[LOOP:%.*]]
108; CHECK:       loop:
109; CHECK-NEXT:    [[IV:%.*]] = phi i64 [ 2, [[ENTRY:%.*]] ], [ [[IV_NEXT:%.*]], [[LOOP]] ]
110; CHECK-NEXT:    [[IV_NEXT]] = udiv i64 9, [[IV]]
111; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
112; CHECK:       exit:
113; CHECK-NEXT:    [[RES:%.*]] = and i64 [[IV]], 4
114; CHECK-NEXT:    ret i64 [[RES]]
115;
116entry:
117  br label %loop
118loop:
119  %iv = phi i64 [2, %entry], [%iv.next, %loop]
120  %iv.next = udiv i64 9, %iv
121  br i1 %c, label %exit, label %loop
122exit:
123  %res = and i64 %iv, 4
124  ret i64 %res
125}
126
127define i64 @test_urem(i1 %c) {
128; CHECK-LABEL: @test_urem(
129; CHECK-NEXT:  entry:
130; CHECK-NEXT:    br label [[LOOP:%.*]]
131; CHECK:       loop:
132; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
133; CHECK:       exit:
134; CHECK-NEXT:    ret i64 0
135;
136entry:
137  br label %loop
138loop:
139  %iv = phi i64 [3, %entry], [%iv.next, %loop]
140  %iv.next = urem i64 9, %iv
141  br i1 %c, label %exit, label %loop
142exit:
143  %res = and i64 %iv, 4
144  ret i64 %res
145}
146
147define i64 @test_and(i1 %c) {
148; CHECK-LABEL: @test_and(
149; CHECK-NEXT:  entry:
150; CHECK-NEXT:    br label [[LOOP:%.*]]
151; CHECK:       loop:
152; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
153; CHECK:       exit:
154; CHECK-NEXT:    ret i64 2047
155;
156entry:
157  br label %loop
158loop:
159  %iv = phi i64 [1025, %entry], [%iv.next, %loop]
160  %iv.next = and i64 %iv, 1024
161  br i1 %c, label %exit, label %loop
162exit:
163  %res = or i64 %iv, 1023
164  ret i64 %res
165}
166
167define i64 @test_or(i1 %c) {
168; CHECK-LABEL: @test_or(
169; CHECK-NEXT:  entry:
170; CHECK-NEXT:    br label [[LOOP:%.*]]
171; CHECK:       loop:
172; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
173; CHECK:       exit:
174; CHECK-NEXT:    ret i64 2047
175;
176entry:
177  br label %loop
178loop:
179  %iv = phi i64 [1025, %entry], [%iv.next, %loop]
180  %iv.next = or i64 %iv, 1024
181  br i1 %c, label %exit, label %loop
182exit:
183  %res = or i64 %iv, 1023
184  ret i64 %res
185}
186
187define i64 @test_ashr_zeros(i1 %c) {
188; CHECK-LABEL: @test_ashr_zeros(
189; CHECK-NEXT:  entry:
190; CHECK-NEXT:    br label [[LOOP:%.*]]
191; CHECK:       loop:
192; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
193; CHECK:       exit:
194; CHECK-NEXT:    ret i64 1023
195;
196entry:
197  br label %loop
198loop:
199  %iv.ashr = phi i64 [1023, %entry], [%iv.ashr.next, %loop]
200  %iv.ashr.next = ashr i64 %iv.ashr, 1
201  br i1 %c, label %exit, label %loop
202exit:
203  %res = or i64 %iv.ashr, 1023
204  ret i64 %res
205}
206
207define i64 @test_ashr_ones(i1 %c) {
208; CHECK-LABEL: @test_ashr_ones(
209; CHECK-NEXT:  entry:
210; CHECK-NEXT:    br label [[LOOP:%.*]]
211; CHECK:       loop:
212; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
213; CHECK:       exit:
214; CHECK-NEXT:    ret i64 -1
215;
216entry:
217  br label %loop
218loop:
219  %iv.ashr = phi i64 [-1023, %entry], [%iv.ashr.next, %loop]
220  %iv.ashr.next = ashr i64 %iv.ashr, 1
221  br i1 %c, label %exit, label %loop
222exit:
223  %res = or i64 %iv.ashr, 1023
224  ret i64 %res
225}
226
227; Same as previous, but swapped operands to phi
228define i64 @test_ashr_ones2(i1 %c) {
229; CHECK-LABEL: @test_ashr_ones2(
230; CHECK-NEXT:  entry:
231; CHECK-NEXT:    br label [[LOOP:%.*]]
232; CHECK:       loop:
233; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
234; CHECK:       exit:
235; CHECK-NEXT:    ret i64 -1
236;
237entry:
238  br label %loop
239loop:
240  %iv.ashr = phi i64 [%iv.ashr.next, %loop], [-1023, %entry]
241  %iv.ashr.next = ashr i64 %iv.ashr, 1
242  br i1 %c, label %exit, label %loop
243exit:
244  %res = or i64 %iv.ashr, 1023
245  ret i64 %res
246}
247
248
249; negative case for when start is unknown
250define i64 @test_ashr_unknown(i1 %c, i64 %start) {
251; CHECK-LABEL: @test_ashr_unknown(
252; CHECK-NEXT:  entry:
253; CHECK-NEXT:    br label [[LOOP:%.*]]
254; CHECK:       loop:
255; CHECK-NEXT:    [[IV_ASHR:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_ASHR_NEXT:%.*]], [[LOOP]] ]
256; CHECK-NEXT:    [[IV_ASHR_NEXT]] = ashr i64 [[IV_ASHR]], 1
257; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
258; CHECK:       exit:
259; CHECK-NEXT:    [[RES:%.*]] = or i64 [[IV_ASHR]], 1023
260; CHECK-NEXT:    ret i64 [[RES]]
261;
262entry:
263  br label %loop
264loop:
265  %iv.ashr = phi i64 [%start, %entry], [%iv.ashr.next, %loop]
266  %iv.ashr.next = ashr i64 %iv.ashr, 1
267  br i1 %c, label %exit, label %loop
268exit:
269  %res = or i64 %iv.ashr, 1023
270  ret i64 %res
271}
272
273; Negative case where we don't have a (shift) recurrence because the operands
274; of the ashr are swapped.  (This does end up being a divide recurrence.)
275define i64 @test_ashr_wrong_op(i1 %c, i64 %start) {
276; CHECK-LABEL: @test_ashr_wrong_op(
277; CHECK-NEXT:  entry:
278; CHECK-NEXT:    br label [[LOOP:%.*]]
279; CHECK:       loop:
280; CHECK-NEXT:    [[IV_ASHR:%.*]] = phi i64 [ [[START:%.*]], [[ENTRY:%.*]] ], [ [[IV_ASHR_NEXT:%.*]], [[LOOP]] ]
281; CHECK-NEXT:    [[IV_ASHR_NEXT]] = lshr i64 1, [[IV_ASHR]]
282; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
283; CHECK:       exit:
284; CHECK-NEXT:    [[RES:%.*]] = or i64 [[IV_ASHR]], 1023
285; CHECK-NEXT:    ret i64 [[RES]]
286;
287entry:
288  br label %loop
289loop:
290  %iv.ashr = phi i64 [%start, %entry], [%iv.ashr.next, %loop]
291  %iv.ashr.next = ashr i64 1, %iv.ashr
292  br i1 %c, label %exit, label %loop
293exit:
294  %res = or i64 %iv.ashr, 1023
295  ret i64 %res
296}
297
298
299define i64 @test_shl(i1 %c) {
300; CHECK-LABEL: @test_shl(
301; CHECK-NEXT:  entry:
302; CHECK-NEXT:    br label [[LOOP:%.*]]
303; CHECK:       loop:
304; CHECK-NEXT:    br i1 [[C:%.*]], label [[EXIT:%.*]], label [[LOOP]]
305; CHECK:       exit:
306; CHECK-NEXT:    ret i64 0
307;
308entry:
309  br label %loop
310loop:
311  %iv.shl = phi i64 [8, %entry], [%iv.shl.next, %loop]
312  %iv.shl.next = shl i64 %iv.shl, 1
313  br i1 %c, label %exit, label %loop
314exit:
315  %res = and i64 %iv.shl, 7
316  ret i64 %res
317}
318