1; RUN: opt -analyze -enable-new-pm=0 -scalar-evolution < %s | FileCheck %s
2; RUN: opt -disable-output "-passes=print<scalar-evolution>" < %s 2>&1 | FileCheck %s
3
4target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
5target triple = "x86_64-unknown-linux-gnu"
6
7define void @f_sadd_0(i8* %a) {
8; CHECK-LABEL: Classifying expressions for: @f_sadd_0
9entry:
10  br label %for.body
11
12for.cond.cleanup:                                 ; preds = %cont
13  ret void
14
15for.body:                                         ; preds = %entry, %cont
16; CHECK:  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
17; CHECK-NEXT:  -->  {0,+,1}<nuw><nsw><%for.body> U: [0,16) S: [0,16)
18
19  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
20  %idxprom = sext i32 %i.04 to i64
21  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
22  store i8 0, i8* %arrayidx, align 1
23  %tmp0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %i.04, i32 1)
24  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
25  br i1 %tmp1, label %trap, label %cont, !nosanitize !{}
26
27trap:                                             ; preds = %for.body
28  tail call void @llvm.trap() #2, !nosanitize !{}
29  unreachable, !nosanitize !{}
30
31cont:                                             ; preds = %for.body
32  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
33  %cmp = icmp slt i32 %tmp2, 16
34  br i1 %cmp, label %for.body, label %for.cond.cleanup
35; CHECK: Loop %for.body: max backedge-taken count is 15
36}
37
38define void @f_sadd_1(i8* %a) {
39; CHECK-LABEL: Classifying expressions for: @f_sadd_1
40entry:
41  br label %for.body
42
43for.cond.cleanup:                                 ; preds = %cont
44  ret void
45
46for.body:                                         ; preds = %entry, %cont
47; CHECK:  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
48; CHECK-NEXT:  -->  {0,+,1}<%for.body> U: [0,16) S: [0,16)
49
50; SCEV can prove <nsw> for the above induction variable; but it does
51; not bother so before it sees the sext below since it is not a 100%
52; obvious.
53
54  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
55  %idxprom = sext i32 %i.04 to i64
56  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
57  store i8 0, i8* %arrayidx, align 1
58  %tmp0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %i.04, i32 1)
59  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
60  br i1 %tmp1, label %trap, label %cont, !nosanitize !{}
61
62trap:                                             ; preds = %for.body
63
64  br label %cont
65
66cont:                                             ; preds = %for.body
67  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
68  %cmp = icmp slt i32 %tmp2, 16
69  br i1 %cmp, label %for.body, label %for.cond.cleanup
70; CHECK: Loop %for.body: max backedge-taken count is 15
71}
72
73define void @f_sadd_2(i8* %a, i1* %c) {
74; CHECK-LABEL: Classifying expressions for: @f_sadd_2
75entry:
76  br label %for.body
77
78for.cond.cleanup:                                 ; preds = %cont
79  ret void
80
81for.body:                                         ; preds = %entry, %cont
82; CHECK:  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
83; CHECK-NEXT:  -->  {0,+,1}<%for.body>
84
85  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
86  %idxprom = sext i32 %i.04 to i64
87  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
88  store i8 0, i8* %arrayidx, align 1
89  %tmp0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %i.04, i32 1)
90  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
91  br i1 %tmp1, label %trap, label %cont, !nosanitize !{}
92
93trap:                                             ; preds = %for.body
94
95  br label %cont
96
97cont:                                             ; preds = %for.body
98  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
99  %cond = load volatile i1, i1* %c
100  br i1 %cond, label %for.body, label %for.cond.cleanup
101}
102
103define void @f_sadd_3(i8* %a, i1* %c) {
104; CHECK-LABEL: Classifying expressions for: @f_sadd_3
105entry:
106  br label %for.body
107
108for.cond.cleanup:                                 ; preds = %cont
109  ret void
110
111for.body:                                         ; preds = %entry, %cont
112; CHECK:  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %for.body ]
113; CHECK-NEXT:  -->  {0,+,1}<nuw><nsw><%for.body>
114
115  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %for.body ]
116  %idxprom = sext i32 %i.04 to i64
117  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
118  store i8 0, i8* %arrayidx, align 1
119  %tmp0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %i.04, i32 1)
120  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
121  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
122  br i1 %tmp1, label %trap, label %for.body, !nosanitize !{}
123
124trap:                                             ; preds = %for.body
125  tail call void @llvm.trap() #2, !nosanitize !{}
126  unreachable, !nosanitize !{}
127}
128
129define void @f_sadd_4(i8* %a, i1* %c) {
130; CHECK-LABEL: Classifying expressions for: @f_sadd_4
131entry:
132  br label %for.body
133
134for.cond.cleanup:                                 ; preds = %cont
135  ret void
136
137for.body:                                         ; preds = %entry, %cont
138; CHECK:  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %merge ]
139; CHECK-NEXT:  -->  {0,+,1}<nuw><nsw><%for.body>
140
141  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %merge ]
142  %idxprom = sext i32 %i.04 to i64
143  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
144  store i8 0, i8* %arrayidx, align 1
145  %tmp0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %i.04, i32 1)
146  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
147  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
148  br i1 %tmp1, label %notrap, label %merge
149
150notrap:
151  br label %merge
152
153merge:
154  %tmp3 = extractvalue { i32, i1 } %tmp0, 1
155  br i1 %tmp3, label %trap, label %for.body, !nosanitize !{}
156
157trap:                                             ; preds = %for.body
158  tail call void @llvm.trap() #2, !nosanitize !{}
159  unreachable, !nosanitize !{}
160}
161
162define void @f_sadd_may_overflow(i8* %a, i1* %c) {
163; CHECK-LABEL: Classifying expressions for: @f_sadd_may_overflow
164entry:
165  br label %for.body
166
167for.cond.cleanup:                                 ; preds = %cont
168  ret void
169
170for.body:                                         ; preds = %entry, %cont
171; CHECK:  %i.04 = phi i32 [ 0, %entry ], [ %tmp1, %cont ]
172; CHECK-NEXT:  -->  {0,+,1}<%for.body> U: full-set S: full-set
173
174  %i.04 = phi i32 [ 0, %entry ], [ %tmp1, %cont ]
175  %idxprom = sext i32 %i.04 to i64
176  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
177  store i8 0, i8* %arrayidx, align 1
178  %tmp0 = tail call { i32, i1 } @llvm.sadd.with.overflow.i32(i32 %i.04, i32 1)
179  %cond1 = load volatile i1, i1* %c
180  br i1 %cond1, label %trap, label %cont, !nosanitize !{}
181
182trap:                                             ; preds = %for.body
183  tail call void @llvm.trap() #2, !nosanitize !{}
184  unreachable, !nosanitize !{}
185
186cont:                                             ; preds = %for.body
187  %tmp1 = extractvalue { i32, i1 } %tmp0, 0
188  %cond = load volatile i1, i1* %c
189  br i1 %cond, label %for.body, label %for.cond.cleanup
190}
191
192define void @f_uadd(i8* %a) {
193; CHECK-LABEL: Classifying expressions for: @f_uadd
194entry:
195  br label %for.body
196
197for.cond.cleanup:                                 ; preds = %cont
198  ret void
199
200for.body:                                         ; preds = %entry, %cont
201; CHECK:  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
202; CHECK-NEXT:  -->  {0,+,1}<nuw><%for.body> U: [0,16) S: [0,16)
203
204  %i.04 = phi i32 [ 0, %entry ], [ %tmp2, %cont ]
205  %idxprom = sext i32 %i.04 to i64
206  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
207  store i8 0, i8* %arrayidx, align 1
208  %tmp0 = tail call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 %i.04, i32 1)
209  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
210  br i1 %tmp1, label %trap, label %cont, !nosanitize !{}
211
212trap:                                             ; preds = %for.body
213  tail call void @llvm.trap(), !nosanitize !{}
214  unreachable, !nosanitize !{}
215
216cont:                                             ; preds = %for.body
217  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
218  %cmp = icmp slt i32 %tmp2, 16
219  br i1 %cmp, label %for.body, label %for.cond.cleanup
220; CHECK: Loop %for.body: max backedge-taken count is 15
221}
222
223define void @f_ssub(i8* nocapture %a) {
224; CHECK-LABEL: Classifying expressions for: @f_ssub
225entry:
226  br label %for.body
227
228for.cond.cleanup:                                 ; preds = %cont
229  ret void
230
231for.body:                                         ; preds = %entry, %cont
232; CHECK:  %i.04 = phi i32 [ 15, %entry ], [ %tmp2, %cont ]
233; CHECK-NEXT:  -->  {15,+,-1}<%for.body> U: [0,16) S: [0,16)
234
235  %i.04 = phi i32 [ 15, %entry ], [ %tmp2, %cont ]
236  %idxprom = sext i32 %i.04 to i64
237  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
238  store i8 0, i8* %arrayidx, align 1
239  %tmp0 = tail call { i32, i1 } @llvm.ssub.with.overflow.i32(i32 %i.04, i32 1)
240  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
241  br i1 %tmp1, label %trap, label %cont, !nosanitize !{}
242
243trap:                                             ; preds = %for.body
244  tail call void @llvm.trap(), !nosanitize !{}
245  unreachable, !nosanitize !{}
246
247cont:                                             ; preds = %for.body
248  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
249  %cmp = icmp sgt i32 %tmp2, -1
250  br i1 %cmp, label %for.body, label %for.cond.cleanup
251; CHECK: Loop %for.body: max backedge-taken count is 15
252}
253
254define void @f_usub(i8* nocapture %a) {
255; CHECK-LABEL: Classifying expressions for: @f_usub
256entry:
257  br label %for.body
258
259for.cond.cleanup:                                 ; preds = %cont
260  ret void
261
262for.body:                                         ; preds = %entry, %cont
263; CHECK:  %i.04 = phi i32 [ 15, %entry ], [ %tmp2, %cont ]
264; CHECK-NEXT:  -->  {15,+,-1}<%for.body> U: [0,16) S: [0,16)
265
266  %i.04 = phi i32 [ 15, %entry ], [ %tmp2, %cont ]
267  %idxprom = sext i32 %i.04 to i64
268  %arrayidx = getelementptr inbounds i8, i8* %a, i64 %idxprom
269  store i8 0, i8* %arrayidx, align 1
270  %tmp0 = tail call { i32, i1 } @llvm.usub.with.overflow.i32(i32 %i.04, i32 1)
271  %tmp1 = extractvalue { i32, i1 } %tmp0, 1
272  br i1 %tmp1, label %trap, label %cont, !nosanitize !{}
273
274trap:                                             ; preds = %for.body
275  tail call void @llvm.trap(), !nosanitize !{}
276  unreachable, !nosanitize !{}
277
278cont:                                             ; preds = %for.body
279  %tmp2 = extractvalue { i32, i1 } %tmp0, 0
280  %cmp = icmp sgt i32 %tmp2, -1
281  br i1 %cmp, label %for.body, label %for.cond.cleanup
282; CHECK: Loop %for.body: max backedge-taken count is 15
283}
284
285define i32 @f_smul(i32 %val_a, i32 %val_b) {
286; CHECK-LABEL: Classifying expressions for: @f_smul
287  %agg = tail call { i32, i1 } @llvm.smul.with.overflow.i32(i32 %val_a, i32 %val_b)
288; CHECK:   %mul = extractvalue { i32, i1 } %agg, 0
289; CHECK-NEXT:  -->  (%val_a * %val_b) U: full-set S: full-set
290  %mul = extractvalue { i32, i1 } %agg, 0
291  ret i32 %mul
292}
293
294define i32 @f_umul(i32 %val_a, i32 %val_b) {
295; CHECK-LABEL: Classifying expressions for: @f_umul
296  %agg = tail call { i32, i1 } @llvm.umul.with.overflow.i32(i32 %val_a, i32 %val_b)
297; CHECK:   %mul = extractvalue { i32, i1 } %agg, 0
298; CHECK-NEXT:  -->  (%val_a * %val_b) U: full-set S: full-set
299  %mul = extractvalue { i32, i1 } %agg, 0
300  ret i32 %mul
301}
302
303declare { i32, i1 } @llvm.sadd.with.overflow.i32(i32, i32) nounwind readnone
304declare { i32, i1 } @llvm.uadd.with.overflow.i32(i32, i32) nounwind readnone
305declare { i32, i1 } @llvm.ssub.with.overflow.i32(i32, i32) nounwind readnone
306declare { i32, i1 } @llvm.usub.with.overflow.i32(i32, i32) nounwind readnone
307declare { i32, i1 } @llvm.smul.with.overflow.i32(i32, i32) nounwind readnone
308declare { i32, i1 } @llvm.umul.with.overflow.i32(i32, i32) nounwind readnone
309
310declare void @llvm.trap() #2
311