1; RUN: opt -S -basicaa -licm < %s | FileCheck %s
2; RUN: opt -aa-pipeline=basic-aa -passes='require<opt-remark-emit>,loop(licm)' -S %s | FileCheck %s
3target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
4target triple = "x86_64-unknown-linux-gnu"
5
6declare void @f() nounwind
7
8; constant fold on first ieration
9define i32 @test1(i32* noalias nocapture readonly %a) nounwind uwtable {
10; CHECK-LABEL: @test1(
11entry:
12; CHECK: %i1 = load i32, i32* %a, align 4
13; CHECK-NEXT: br label %for.body
14  br label %for.body
15
16for.body:
17  %iv = phi i32 [ 0, %entry ], [ %inc, %continue ]
18  %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
19  %r.chk = icmp ult i32 %iv, 2000
20  br i1 %r.chk, label %continue, label %fail
21continue:
22  %i1 = load i32, i32* %a, align 4
23  %add = add nsw i32 %i1, %acc
24  %inc = add nuw nsw i32 %iv, 1
25  %exitcond = icmp eq i32 %inc, 1000
26  br i1 %exitcond, label %for.cond.cleanup, label %for.body
27
28for.cond.cleanup:
29  ret i32 %add
30
31fail:
32  call void @f()
33  ret i32 -1
34}
35
36; Same as test1, but with a floating point IR and fcmp
37define i32 @test_fcmp(i32* noalias nocapture readonly %a) nounwind uwtable {
38; CHECK-LABEL: @test_fcmp(
39entry:
40; CHECK: %i1 = load i32, i32* %a, align 4
41; CHECK-NEXT: br label %for.body
42  br label %for.body
43
44for.body:
45  %iv = phi float [ 0.0, %entry ], [ %inc, %continue ]
46  %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
47  %r.chk = fcmp olt float %iv, 2000.0
48  br i1 %r.chk, label %continue, label %fail
49continue:
50  %i1 = load i32, i32* %a, align 4
51  %add = add nsw i32 %i1, %acc
52  %inc = fadd float %iv, 1.0
53  %exitcond = fcmp ogt float %inc, 1000.0
54  br i1 %exitcond, label %for.cond.cleanup, label %for.body
55
56for.cond.cleanup:
57  ret i32 %add
58
59fail:
60  call void @f()
61  ret i32 -1
62}
63
64; Count down from a.length w/entry guard
65; TODO: currently unable to prove the following:
66; ule i32 (add nsw i32 %len, -1), %len where len is [0, 512]
67define i32 @test2(i32* noalias nocapture readonly %a) nounwind uwtable {
68; CHECK-LABEL: @test2(
69entry:
70  %len = load i32, i32* %a, align 4, !range !{i32 0, i32 512}
71  %is.non.pos = icmp eq i32 %len, 0
72  br i1 %is.non.pos, label %fail, label %preheader
73preheader:
74  %lenminusone = add nsw i32 %len, -1
75  br label %for.body
76for.body:
77  %iv = phi i32 [ %lenminusone, %preheader ], [ %dec, %continue ]
78  %acc = phi i32 [ 0, %preheader ], [ %add, %continue ]
79  %r.chk = icmp ule i32 %iv, %len
80  br i1 %r.chk, label %continue, label %fail
81continue:
82; CHECK-LABEL: continue
83; CHECK: %i1 = load i32, i32* %a, align 4
84  %i1 = load i32, i32* %a, align 4
85  %add = add nsw i32 %i1, %acc
86  %dec = add nsw i32 %iv, -1
87  %exitcond = icmp eq i32 %dec, 0
88  br i1 %exitcond, label %for.cond.cleanup, label %for.body
89
90for.cond.cleanup:
91  ret i32 %add
92
93fail:
94  call void @f()
95  ret i32 -1
96}
97
98; trivially true for zero
99define i32 @test3(i32* noalias nocapture readonly %a) nounwind uwtable {
100; CHECK-LABEL: @test3(
101entry:
102  %len = load i32, i32* %a, align 4, !range !{i32 0, i32 512}
103  %is.zero = icmp eq i32 %len, 0
104  br i1 %is.zero, label %fail, label %preheader
105preheader:
106; CHECK: %i1 = load i32, i32* %a, align 4
107; CHECK-NEXT: br label %for.body
108  br label %for.body
109for.body:
110  %iv = phi i32 [ 0, %preheader ], [ %inc, %continue ]
111  %acc = phi i32 [ 0, %preheader ], [ %add, %continue ]
112  %r.chk = icmp ule i32 %iv, %len
113  br i1 %r.chk, label %continue, label %fail
114continue:
115  %i1 = load i32, i32* %a, align 4
116  %add = add nsw i32 %i1, %acc
117  %inc = add nuw nsw i32 %iv, 1
118  %exitcond = icmp eq i32 %inc, 1000
119  br i1 %exitcond, label %for.cond.cleanup, label %for.body
120
121for.cond.cleanup:
122  ret i32 %add
123
124fail:
125  call void @f()
126  ret i32 -1
127}
128
129; requires fact length is non-zero
130; TODO: IsKnownNonNullFromDominatingConditions is currently only be done for
131; pointers; should handle integers too
132define i32 @test4(i32* noalias nocapture readonly %a) nounwind uwtable {
133; CHECK-LABEL: @test4(
134entry:
135  %len = load i32, i32* %a, align 4, !range !{i32 0, i32 512}
136  %is.zero = icmp eq i32 %len, 0
137  br i1 %is.zero, label %fail, label %preheader
138preheader:
139  br label %for.body
140for.body:
141  %iv = phi i32 [ 0, %preheader ], [ %inc, %continue ]
142  %acc = phi i32 [ 0, %preheader ], [ %add, %continue ]
143  %r.chk = icmp ult i32 %iv, %len
144  br i1 %r.chk, label %continue, label %fail
145continue:
146; CHECK-LABEL: continue
147; CHECK: %i1 = load i32, i32* %a, align 4
148  %i1 = load i32, i32* %a, align 4
149  %add = add nsw i32 %i1, %acc
150  %inc = add nuw nsw i32 %iv, 1
151  %exitcond = icmp eq i32 %inc, 1000
152  br i1 %exitcond, label %for.cond.cleanup, label %for.body
153
154for.cond.cleanup:
155  ret i32 %add
156
157fail:
158  call void @f()
159  ret i32 -1
160}
161
162; variation on test1 with branch swapped
163define i32 @test-brswap(i32* noalias nocapture readonly %a) nounwind uwtable {
164; CHECK-LABEL: @test-brswap(
165entry:
166; CHECK: %i1 = load i32, i32* %a, align 4
167; CHECK-NEXT: br label %for.body
168  br label %for.body
169
170for.body:
171  %iv = phi i32 [ 0, %entry ], [ %inc, %continue ]
172  %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
173  %r.chk = icmp ugt i32 %iv, 2000
174  br i1 %r.chk, label %fail, label %continue
175continue:
176  %i1 = load i32, i32* %a, align 4
177  %add = add nsw i32 %i1, %acc
178  %inc = add nuw nsw i32 %iv, 1
179  %exitcond = icmp eq i32 %inc, 1000
180  br i1 %exitcond, label %for.cond.cleanup, label %for.body
181
182for.cond.cleanup:
183  ret i32 %add
184
185fail:
186  call void @f()
187  ret i32 -1
188}
189
190define i32 @test-nonphi(i32* noalias nocapture readonly %a) nounwind uwtable {
191; CHECK-LABEL: @test-nonphi(
192entry:
193  br label %for.body
194
195for.body:
196; CHECK-LABEL: continue
197; CHECK: %i1 = load i32, i32* %a, align 4
198  %iv = phi i32 [ 0, %entry ], [ %inc, %continue ]
199  %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
200  %xor = xor i32 %iv, 72
201  %r.chk = icmp ugt i32 %xor, 2000
202  br i1 %r.chk, label %fail, label %continue
203continue:
204  %i1 = load i32, i32* %a, align 4
205  %add = add nsw i32 %i1, %acc
206  %inc = add nuw nsw i32 %iv, 1
207  %exitcond = icmp eq i32 %inc, 1000
208  br i1 %exitcond, label %for.cond.cleanup, label %for.body
209
210for.cond.cleanup:
211  ret i32 %add
212
213fail:
214  call void @f()
215  ret i32 -1
216}
217
218define i32 @test-wrongphi(i32* noalias nocapture readonly %a) nounwind uwtable {
219; CHECK-LABEL: @test-wrongphi(
220entry:
221  br label %for.body
222
223for.body:
224  %iv = phi i32 [ 0, %entry ], [ %inc, %continue ]
225  %acc = phi i32 [ 0, %entry ], [ %add, %continue ]
226  %cond = icmp ult i32 %iv, 500
227  br i1 %cond, label %dummy_block1, label %dummy_block2
228
229dummy_block1:
230  br label %dummy_block2
231
232dummy_block2:
233  %wrongphi = phi i32 [11, %for.body], [12, %dummy_block1]
234  %r.chk = icmp ugt i32 %wrongphi, 2000
235  br i1 %r.chk, label %fail, label %continue
236continue:
237; CHECK-LABEL: continue
238; CHECK: %i1 = load i32, i32* %a, align 4
239  %i1 = load i32, i32* %a, align 4
240  %add = add nsw i32 %i1, %acc
241  %inc = add nuw nsw i32 %iv, 1
242  %exitcond = icmp eq i32 %inc, 1000
243  br i1 %exitcond, label %for.cond.cleanup, label %for.body
244
245for.cond.cleanup:
246  ret i32 %add
247
248fail:
249  call void @f()
250  ret i32 -1
251}
252
253; This works because loop-simplify is run implicitly, but test for it anyways
254define i32 @test-multiple-latch(i32* noalias nocapture readonly %a) nounwind uwtable {
255; CHECK-LABEL: @test-multiple-latch(
256entry:
257; CHECK: %i1 = load i32, i32* %a, align 4
258; CHECK-NEXT: br label %for.body
259  br label %for.body
260
261for.body:
262  %iv = phi i32 [ 0, %entry ], [ %inc, %continue1 ], [ %inc, %continue2 ]
263  %acc = phi i32 [ 0, %entry ], [ %add, %continue1 ], [ %add, %continue2 ]
264  %r.chk = icmp ult i32 %iv, 2000
265  br i1 %r.chk, label %continue1, label %fail
266continue1:
267  %i1 = load i32, i32* %a, align 4
268  %add = add nsw i32 %i1, %acc
269  %inc = add nuw nsw i32 %iv, 1
270  %cmp = icmp eq i32 %add, 0
271  br i1 %cmp, label %continue2, label %for.body
272continue2:
273  %exitcond = icmp eq i32 %inc, 1000
274  br i1 %exitcond, label %for.cond.cleanup, label %for.body
275
276for.cond.cleanup:
277  ret i32 %add
278
279fail:
280  call void @f()
281  ret i32 -1
282}
283