1; RUN: opt -analyze -scalar-evolution < %s | FileCheck %s
2
3define void @f0(i1 %c) {
4; CHECK-LABEL: Classifying expressions for: @f0
5entry:
6  %start = select i1 %c, i32 127, i32 0
7  %step  = select i1 %c, i32 -1,  i32 1
8  br label %loop
9
10loop:
11  %loop.iv = phi i32 [ 0, %entry ], [ %loop.iv.inc, %loop ]
12  %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
13; CHECK: %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
14; CHECK-NEXT:  -->  {%start,+,%step}<%loop> U: [0,128) S: [0,128)
15  %iv.next = add i32 %iv, %step
16  %loop.iv.inc = add i32 %loop.iv, 1
17  %be.cond = icmp ne i32 %loop.iv.inc, 128
18  br i1 %be.cond, label %loop, label %leave
19
20leave:
21  ret void
22}
23
24define void @f1(i1 %c) {
25; CHECK-LABEL: Classifying expressions for: @f1
26entry:
27  %start = select i1 %c, i32 120, i32 0
28  %step  = select i1 %c, i32 -8,  i32 8
29  br label %loop
30
31loop:
32  %loop.iv = phi i32 [ 0, %entry ], [ %loop.iv.inc, %loop ]
33  %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
34
35; CHECK:  %iv.1 = add i32 %iv, 1
36; CHECK-NEXT:  -->  {(1 + %start)<nuw><nsw>,+,%step}<%loop> U: [1,122) S: [1,122)
37; CHECK:  %iv.2 = add i32 %iv, 2
38; CHECK-NEXT:  -->  {(2 + %start)<nuw><nsw>,+,%step}<%loop> U: [2,123) S: [2,123)
39; CHECK:  %iv.3 = add i32 %iv, 3
40; CHECK-NEXT:  -->  {(3 + %start)<nuw><nsw>,+,%step}<%loop> U: [3,124) S: [3,124)
41; CHECK:  %iv.4 = add i32 %iv, 4
42; CHECK-NEXT:  -->  {(4 + %start)<nuw><nsw>,+,%step}<%loop> U: [4,125) S: [4,125)
43; CHECK:  %iv.5 = add i32 %iv, 5
44; CHECK-NEXT:  -->  {(5 + %start)<nuw><nsw>,+,%step}<%loop> U: [5,126) S: [5,126)
45; CHECK:  %iv.6 = add i32 %iv, 6
46; CHECK-NEXT:  -->  {(6 + %start)<nuw><nsw>,+,%step}<%loop> U: [6,127) S: [6,127)
47; CHECK:  %iv.7 = add i32 %iv, 7
48; CHECK-NEXT:  -->  {(7 + %start)<nuw><nsw>,+,%step}<%loop> U: [7,128) S: [7,128)
49
50  %iv.1 = add i32 %iv, 1
51  %iv.2 = add i32 %iv, 2
52  %iv.3 = add i32 %iv, 3
53  %iv.4 = add i32 %iv, 4
54  %iv.5 = add i32 %iv, 5
55  %iv.6 = add i32 %iv, 6
56  %iv.7 = add i32 %iv, 7
57
58; CHECK:  %iv.m1 = sub i32 %iv, 1
59; CHECK-NEXT:  -->  {(-1 + %start)<nsw>,+,%step}<%loop> U: [-1,120) S: [-1,120)
60; CHECK:  %iv.m2 = sub i32 %iv, 2
61; CHECK-NEXT:  -->  {(-2 + %start)<nsw>,+,%step}<%loop> U: [-2,119) S: [-2,119)
62; CHECK:  %iv.m3 = sub i32 %iv, 3
63; CHECK-NEXT:  -->  {(-3 + %start)<nsw>,+,%step}<%loop> U: [-3,118) S: [-3,118)
64; CHECK:  %iv.m4 = sub i32 %iv, 4
65; CHECK-NEXT:  -->  {(-4 + %start)<nsw>,+,%step}<%loop> U: [-4,117) S: [-4,117)
66; CHECK:  %iv.m5 = sub i32 %iv, 5
67; CHECK-NEXT:  -->  {(-5 + %start)<nsw>,+,%step}<%loop> U: [-5,116) S: [-5,116)
68; CHECK:  %iv.m6 = sub i32 %iv, 6
69; CHECK-NEXT:  -->  {(-6 + %start)<nsw>,+,%step}<%loop> U: [-6,115) S: [-6,115)
70; CHECK:  %iv.m7 = sub i32 %iv, 7
71; CHECK-NEXT:  -->  {(-7 + %start)<nsw>,+,%step}<%loop> U: [-7,114) S: [-7,114)
72
73  %iv.m1 = sub i32 %iv, 1
74  %iv.m2 = sub i32 %iv, 2
75  %iv.m3 = sub i32 %iv, 3
76  %iv.m4 = sub i32 %iv, 4
77  %iv.m5 = sub i32 %iv, 5
78  %iv.m6 = sub i32 %iv, 6
79  %iv.m7 = sub i32 %iv, 7
80
81  %iv.next = add i32 %iv, %step
82  %loop.iv.inc = add i32 %loop.iv, 1
83  %be.cond = icmp sgt i32 %loop.iv, 14
84  br i1 %be.cond, label %leave, label %loop
85
86leave:
87  ret void
88}
89
90define void @f2(i1 %c) {
91; CHECK-LABEL: Classifying expressions for: @f2
92entry:
93  %start = select i1 %c, i32 127, i32 0
94  %step  = select i1 %c, i32 -1,  i32 1
95  br label %loop
96
97loop:
98  %loop.iv = phi i32 [ 0, %entry ], [ %loop.iv.inc, %loop ]
99  %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
100  %iv.sext = sext i32 %iv to i64
101  %iv.next = add i32 %iv, %step
102; CHECK:  %iv.sext = sext i32 %iv to i64
103; CHECK-NEXT:   -->  {(sext i32 %start to i64),+,(sext i32 %step to i64)}<nsw><%loop> U: [0,128) S: [0,128)
104  %loop.iv.inc = add i32 %loop.iv, 1
105  %be.cond = icmp ne i32 %loop.iv.inc, 128
106  br i1 %be.cond, label %loop, label %leave
107
108leave:
109  ret void
110}
111
112define void @f3(i1 %c) {
113; CHECK-LABEL: Classifying expressions for: @f3
114entry:
115
116; NB! the i16 type (as opposed to i32), the choice of the constant 509
117; and the trip count are all related and not arbitrary.  We want an
118; add recurrence that will look like it can unsign-overflow *unless*
119; SCEV is able to see the correlation between the two selects feeding
120; into the initial value and the step increment.
121
122  %start = select i1 %c, i16 1000, i16 0
123  %step  = select i1 %c, i16 1,  i16 509
124  br label %loop
125
126loop:
127  %loop.iv = phi i16 [ 0, %entry ], [ %loop.iv.inc, %loop ]
128  %iv = phi i16 [ %start, %entry ], [ %iv.next, %loop ]
129  %iv.zext = zext i16 %iv to i64
130; CHECK:  %iv.zext = zext i16 %iv to i64
131; CHECK-NEXT:  -->  {(zext i16 %start to i64),+,(zext i16 %step to i64)}<nuw><%loop> U: [0,64644) S: [0,64644)
132  %iv.next = add i16 %iv, %step
133  %loop.iv.inc = add i16 %loop.iv, 1
134  %be.cond = icmp ne i16 %loop.iv.inc, 128
135  br i1 %be.cond, label %loop, label %leave
136
137leave:
138  ret void
139}
140
141define void @f4(i1 %c) {
142; CHECK-LABEL: Classifying expressions for: @f4
143
144; @f4() demonstrates a case where SCEV is not able to compute a
145; precise range for %iv.trunc, though it should be able to, in theory.
146; This is because SCEV looks into affine add recurrences only when the
147; backedge taken count of the loop has the same bitwidth as the
148; induction variable.
149entry:
150  %start = select i1 %c, i32 127, i32 0
151  %step  = select i1 %c, i32 -1,  i32 1
152  br label %loop
153
154loop:
155  %loop.iv = phi i32 [ 0, %entry ], [ %loop.iv.inc, %loop ]
156  %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
157  %iv.trunc = trunc i32 %iv to i16
158; CHECK:  %iv.trunc = trunc i32 %iv to i16
159; CHECK-NEXT:   -->  {(trunc i32 %start to i16),+,(trunc i32 %step to i16)}<%loop> U: full-set S: full-set
160  %iv.next = add i32 %iv, %step
161  %loop.iv.inc = add i32 %loop.iv, 1
162  %be.cond = icmp ne i32 %loop.iv.inc, 128
163  br i1 %be.cond, label %loop, label %leave
164
165leave:
166  ret void
167}
168
169define void @f5(i1 %c) {
170; CHECK-LABEL: Classifying expressions for: @f5
171entry:
172  %start = select i1 %c, i32 127, i32 0
173  %step  = select i1 %c, i32 -1,  i32 1
174  br label %loop
175
176loop:
177  %loop.iv = phi i16 [ 0, %entry ], [ %loop.iv.inc, %loop ]
178  %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
179  %iv.trunc = trunc i32 %iv to i16
180; CHECK:  %iv.trunc = trunc i32 %iv to i16
181; CHECK-NEXT:  -->  {(trunc i32 %start to i16),+,(trunc i32 %step to i16)}<%loop> U: [0,128) S: [0,128)
182  %iv.next = add i32 %iv, %step
183
184  %loop.iv.inc = add i16 %loop.iv, 1
185  %be.cond = icmp ne i16 %loop.iv.inc, 128
186  br i1 %be.cond, label %loop, label %leave
187
188leave:
189  ret void
190}
191
192define void @f6(i1 %c) {
193; CHECK-LABEL: Classifying expressions for: @f6
194entry:
195  %start = select i1 %c, i32 127, i32 0
196  %step  = select i1 %c, i32 -2,  i32 0
197  br label %loop
198
199loop:
200  %loop.iv = phi i16 [ 0, %entry ], [ %loop.iv.inc, %loop ]
201  %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
202; CHECK:   %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
203; CHECK-NEXT:  -->  {%start,+,(1 + %step)<nuw><nsw>}<%loop> U: [0,128) S: [0,128)
204
205  %step.plus.one = add i32 %step, 1
206  %iv.next = add i32 %iv, %step.plus.one
207  %iv.sext = sext i32 %iv to i64
208; CHECK:   %iv.sext = sext i32 %iv to i64
209; CHECK-NEXT:  -->  {(sext i32 %start to i64),+,(1 + (sext i32 %step to i64))<nsw>}<nsw><%loop> U: [0,128) S: [0,128)
210  %loop.iv.inc = add i16 %loop.iv, 1
211  %be.cond = icmp ne i16 %loop.iv.inc, 128
212  br i1 %be.cond, label %loop, label %leave
213
214leave:
215  ret void
216}
217
218define void @f7(i1 %c) {
219; CHECK-LABEL: Classifying expressions for: @f7
220entry:
221  %start = select i1 %c, i32 127, i32 0
222  %step  = select i1 %c, i32 -1,  i32 1
223  br label %loop
224
225loop:
226  %loop.iv = phi i16 [ 0, %entry ], [ %loop.iv.inc, %loop ]
227  %iv = phi i32 [ %start, %entry ], [ %iv.next, %loop ]
228  %iv.trunc = trunc i32 %iv to i16
229; CHECK:  %iv.trunc = trunc i32 %iv to i16
230; CHECK-NEXT:  -->  {(trunc i32 %start to i16),+,(trunc i32 %step to i16)}<%loop> U: [0,128) S: [0,128)
231  %iv.next = add i32 %iv, %step
232
233  %iv.trunc.plus.one = add i16 %iv.trunc, 1
234; CHECK:  %iv.trunc.plus.one = add i16 %iv.trunc, 1
235; CHECK-NEXT:  -->  {(1 + (trunc i32 %start to i16))<nuw><nsw>,+,(trunc i32 %step to i16)}<%loop> U: [1,129) S: [1,129)
236
237  %iv.trunc.plus.two = add i16 %iv.trunc, 2
238; CHECK:  %iv.trunc.plus.two = add i16 %iv.trunc, 2
239; CHECK-NEXT:  -->  {(2 + (trunc i32 %start to i16))<nuw><nsw>,+,(trunc i32 %step to i16)}<%loop> U: [2,130) S: [2,130)
240
241  %loop.iv.inc = add i16 %loop.iv, 1
242  %be.cond = icmp ne i16 %loop.iv.inc, 128
243  br i1 %be.cond, label %loop, label %leave
244
245leave:
246  ret void
247}
248