Bump version to 19.1.0-rc3
[llvm-project.git] / llvm / test / Analysis / ScalarEvolution / scev-aa.ll
blob5610833e9c474527775cba48d05f8575de240305
1 ; RUN: opt -disable-output < %s -aa-pipeline=scev-aa -passes=aa-eval -print-all-alias-modref-info \
2 ; RUN:   2>&1 | FileCheck %s
4 ; At the time of this writing, misses the example of the form
5 ; A[i+(j+1)] != A[i+j], which can arise from multi-dimensional array references,
6 ; and the example of the form A[0] != A[i+1], where i+1 is known to be positive.
8 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64"
10 ; p[i] and p[i+1] don't alias.
12 ; CHECK-LABEL: Function: loop
13 ; CHECK: NoAlias: double* %pi, double* %pi.next
15 define void @loop(ptr nocapture %p, i64 %n) nounwind {
16 entry:
17   %j = icmp sgt i64 %n, 0
18   br i1 %j, label %bb, label %return
20 bb:
21   %i = phi i64 [ 0, %entry ], [ %i.next, %bb ]
22   %pi = getelementptr double, ptr %p, i64 %i
23   %i.next = add i64 %i, 1
24   %pi.next = getelementptr double, ptr %p, i64 %i.next
25   %x = load double, ptr %pi
26   %y = load double, ptr %pi.next
27   %z = fmul double %x, %y
28   store double %z, ptr %pi
29   %exitcond = icmp eq i64 %i.next, %n
30   br i1 %exitcond, label %return, label %bb
32 return:
33   ret void
36 ; Slightly more involved: p[j][i], p[j][i+1], and p[j+1][i] don't alias.
38 ; CHECK-LABEL: Function: nestedloop
39 ; CHECK: NoAlias: double* %pi.j, double* %pi.next.j
40 ; CHECK: NoAlias: double* %pi.j, double* %pi.j.next
41 ; CHECK: NoAlias: double* %pi.j.next, double* %pi.next.j
43 define void @nestedloop(ptr nocapture %p, i64 %m) nounwind {
44 entry:
45   %k = icmp sgt i64 %m, 0
46   br i1 %k, label %guard, label %return
48 guard:
49   %l = icmp sgt i64 91, 0
50   br i1 %l, label %outer.loop, label %return
52 outer.loop:
53   %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ]
54   br label %bb
56 bb:
57   %i = phi i64 [ 0, %outer.loop ], [ %i.next, %bb ]
58   %i.next = add i64 %i, 1
60   %e = add i64 %i, %j
61   %pi.j = getelementptr double, ptr %p, i64 %e
62   %f = add i64 %i.next, %j
63   %pi.next.j = getelementptr double, ptr %p, i64 %f
64   %x = load double, ptr %pi.j
65   %y = load double, ptr %pi.next.j
66   %z = fmul double %x, %y
67   store double %z, ptr %pi.j
69   %o = add i64 %j, 91
70   %g = add i64 %i, %o
71   %pi.j.next = getelementptr double, ptr %p, i64 %g
72   %a = load double, ptr %pi.j.next
73   %b = fmul double %x, %a
74   store double %b, ptr %pi.j.next
76   %exitcond = icmp eq i64 %i.next, 91
77   br i1 %exitcond, label %outer.latch, label %bb
79 outer.latch:
80   %j.next = add i64 %j, 91
81   %h = icmp eq i64 %j.next, %m
82   br i1 %h, label %return, label %outer.loop
84 return:
85   ret void
88 ; Even more involved: same as nestedloop, but with a variable extent.
89 ; When n is 1, p[j+1][i] does alias p[j][i+1], and there's no way to
90 ; prove whether n will be greater than 1, so that relation will always
91 ; by MayAlias. The loop is guarded by a n > 0 test though, so
92 ; p[j+1][i] and p[j][i] can theoretically be determined to be NoAlias,
93 ; however the analysis currently doesn't do that.
94 ; TODO: Make the analysis smarter and turn that MayAlias into a NoAlias.
96 ; CHECK-LABEL: Function: nestedloop_more
97 ; CHECK: NoAlias: double* %pi.j, double* %pi.next.j
98 ; CHECK: MayAlias: double* %pi.j, double* %pi.j.next
100 define void @nestedloop_more(ptr nocapture %p, i64 %n, i64 %m) nounwind {
101 entry:
102   %k = icmp sgt i64 %m, 0
103   br i1 %k, label %guard, label %return
105 guard:
106   %l = icmp sgt i64 %n, 0
107   br i1 %l, label %outer.loop, label %return
109 outer.loop:
110   %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ]
111   br label %bb
114   %i = phi i64 [ 0, %outer.loop ], [ %i.next, %bb ]
115   %i.next = add i64 %i, 1
117   %e = add i64 %i, %j
118   %pi.j = getelementptr double, ptr %p, i64 %e
119   %f = add i64 %i.next, %j
120   %pi.next.j = getelementptr double, ptr %p, i64 %f
121   %x = load double, ptr %pi.j
122   %y = load double, ptr %pi.next.j
123   %z = fmul double %x, %y
124   store double %z, ptr %pi.j
126   %o = add i64 %j, %n
127   %g = add i64 %i, %o
128   %pi.j.next = getelementptr double, ptr %p, i64 %g
129   %a = load double, ptr %pi.j.next
130   %b = fmul double %x, %a
131   store double %b, ptr %pi.j.next
133   %exitcond = icmp eq i64 %i.next, %n
134   br i1 %exitcond, label %outer.latch, label %bb
136 outer.latch:
137   %j.next = add i64 %j, %n
138   %h = icmp eq i64 %j.next, %m
139   br i1 %h, label %return, label %outer.loop
141 return:
142   ret void
145 ; ScalarEvolution expands field offsets into constants, which allows it to
146 ; do aggressive analysis. Contrast this with BasicAA, which works by
147 ; recognizing GEP idioms.
149 %struct.A = type { %struct.B, i32, i32 }
150 %struct.B = type { double }
152 ; CHECK-LABEL: Function: foo
153 ; CHECK-DAG: NoAlias: %struct.B* %A, i32* %Z
154 ; CHECK-DAG: NoAlias: %struct.B* %A, %struct.B* %C
155 ; CHECK-DAG: MustAlias: %struct.B* %C, i32* %Z
156 ; CHECK-DAG: NoAlias: %struct.B* %A, i32* %C
157 ; CHECK-DAG: MustAlias: i32* %C, i32* %Z
158 ; CHECK-DAG: MustAlias: %struct.B* %C, i32* %Y
159 ; CHECK-DAG: MustAlias: i32* %C, i32* %Y
161 define void @foo() {
162 entry:
163   %A = alloca %struct.A
164   %Z = getelementptr %struct.A, ptr %A, i32 0, i32 1
165   %C = getelementptr %struct.B, ptr %A, i32 1
166   %Y = getelementptr %struct.A, ptr %A, i32 0, i32 1
167   load %struct.B, ptr %A
168   load %struct.B, ptr %C
169   load i32, ptr %C
170   load i32, ptr %Y
171   load i32, ptr %Z
172   ret void
175 ; CHECK-LABEL: Function: bar
176 ; CHECK-DAG: NoAlias: %struct.B* %M, i32* %P
177 ; CHECK-DAG: NoAlias: %struct.B* %M, %struct.B* %R
178 ; CHECK-DAG: MustAlias: i32* %P, %struct.B* %R
179 ; CHECK-DAG: NoAlias: %struct.B* %M, i32* %R
180 ; CHECK-DAG: MustAlias: i32* %P, i32* %R
181 ; CHECK-DAG: MustAlias: %struct.B* %R, i32* %V
182 ; CHECK-DAG: MustAlias: i32* %R, i32* %V
184 define void @bar() {
185   %M = alloca %struct.A
186   %P = getelementptr %struct.A, ptr %M, i32 0, i32 1
187   %R = getelementptr %struct.B, ptr %M, i32 1
188   %V = getelementptr %struct.A, ptr %M, i32 0, i32 1
189   load %struct.B, ptr %M
190   load %struct.B, ptr %R
191   load i32, ptr %P
192   load i32, ptr %V
193   load i32, ptr %R
194   ret void
197 ; CHECK: Function: nonnegative: 2 pointers, 0 call sites
198 ; CHECK: NoAlias:  i64* %arrayidx, i64* %p
200 define void @nonnegative(ptr %p) nounwind {
201 entry:
202   br label %for.body
204 for.body:                                         ; preds = %entry, %for.body
205   %i = phi i64 [ %inc, %for.body ], [ 0, %entry ] ; <i64> [#uses=2]
206   %inc = add nsw i64 %i, 1                         ; <i64> [#uses=2]
207   %arrayidx = getelementptr inbounds i64, ptr %p, i64 %inc
208   store i64 0, ptr %arrayidx
209   %tmp6 = load i64, ptr %p                            ; <i64> [#uses=1]
210   %cmp = icmp slt i64 %inc, %tmp6                 ; <i1> [#uses=1]
211   br i1 %cmp, label %for.body, label %for.end
213 for.end:                                          ; preds = %for.body, %entry
214   ret void
217 ; CHECK-LABEL: Function: test_no_dom: 3 pointers, 0 call sites
218 ; CHECK: MayAlias:      double* %addr1, double* %data
219 ; CHECK: NoAlias:       double* %addr2, double* %data
220 ; CHECK: MayAlias:      double* %addr1, double* %addr2
222 ; In this case, checking %addr1 and %add2 involves two addrecs in two
223 ; different loops where neither dominates the other.  This used to crash
224 ; because we expected the arguments to an AddExpr to have a strict
225 ; dominance order.
226 define void @test_no_dom(ptr %data) {
227 entry:
228   load double, ptr %data
229   br label %for.body
230   
231 for.body:
232   %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.latch ]
233   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
234   br i1 undef, label %subloop1, label %subloop2
236 subloop1:
237   %iv1 = phi i32 [0, %for.body], [%iv1.next, %subloop1]
238   %iv1.next = add i32 %iv1, 1
239   %addr1 = getelementptr double, ptr %data, i32 %iv1
240   store double 0.0, ptr %addr1
241   %cmp1 = icmp slt i32 %iv1, 200
242   br i1 %cmp1, label %subloop1, label %for.latch
244 subloop2:
245   %iv2 = phi i32 [400, %for.body], [%iv2.next, %subloop2]
246   %iv2.next = add i32 %iv2, 1
247   %addr2 = getelementptr double, ptr %data, i32 %iv2
248   store double 0.0, ptr %addr2
249   %cmp2 = icmp slt i32 %iv2, 600
250   br i1 %cmp2, label %subloop2, label %for.latch
252 for.latch:
253   br label %for.body
255 for.end:
256   ret void
259 declare ptr @get_addr(i32 %i)
261 ; CHECK-LABEL: Function: test_no_dom2: 3 pointers, 2 call sites
262 ; CHECK: MayAlias:      double* %addr1, double* %data
263 ; CHECK: MayAlias:      double* %addr2, double* %data
264 ; CHECK: MayAlias:      double* %addr1, double* %addr2
266 ; In this case, checking %addr1 and %add2 involves two addrecs in two
267 ; different loops where neither dominates the other.  This is analogous
268 ; to test_no_dom, but involves SCEVUnknown as opposed to SCEVAddRecExpr.
269 define void @test_no_dom2(ptr %data) {
270 entry:
271   load double, ptr %data
272   br label %for.body
273   
274 for.body:
275   %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.latch ]
276   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
277   br i1 undef, label %subloop1, label %subloop2
279 subloop1:
280   %iv1 = phi i32 [0, %for.body], [%iv1.next, %subloop1]
281   %iv1.next = add i32 %iv1, 1
282   %addr1 = call ptr @get_addr(i32 %iv1)
283   store double 0.0, ptr %addr1
284   %cmp1 = icmp slt i32 %iv1, 200
285   br i1 %cmp1, label %subloop1, label %for.latch
287 subloop2:
288   %iv2 = phi i32 [400, %for.body], [%iv2.next, %subloop2]
289   %iv2.next = add i32 %iv2, 1
290   %addr2 = call ptr @get_addr(i32 %iv2)
291   store double 0.0, ptr %addr2
292   %cmp2 = icmp slt i32 %iv2, 600
293   br i1 %cmp2, label %subloop2, label %for.latch
295 for.latch:
296   br label %for.body
298 for.end:
299   ret void
303 ; CHECK-LABEL: Function: test_dom: 3 pointers, 0 call sites
304 ; CHECK: MayAlias:      double* %addr1, double* %data
305 ; CHECK: NoAlias:       double* %addr2, double* %data
306 ; CHECK: NoAlias:       double* %addr1, double* %addr2
308 ; This is a variant of test_non_dom where the second subloop is
309 ; dominated by the first.  As a result of that, we can nest the
310 ; addrecs and cancel out the %data base pointer.
311 define void @test_dom(ptr %data) {
312 entry:
313   load double, ptr %data
314   br label %for.body
315   
316 for.body:
317   %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.latch ]
318   %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
319   br label %subloop1
321 subloop1:
322   %iv1 = phi i32 [0, %for.body], [%iv1.next, %subloop1]
323   %iv1.next = add i32 %iv1, 1
324   %addr1 = getelementptr double, ptr %data, i32 %iv1
325   store double 0.0, ptr %addr1
326   %cmp1 = icmp slt i32 %iv1, 200
327   br i1 %cmp1, label %subloop1, label %subloop2
329 subloop2:
330   %iv2 = phi i32 [400, %subloop1], [%iv2.next, %subloop2]
331   %iv2.next = add i32 %iv2, 1
332   %addr2 = getelementptr double, ptr %data, i32 %iv2
333   store double 0.0, ptr %addr2
334   %cmp2 = icmp slt i32 %iv2, 600
335   br i1 %cmp2, label %subloop2, label %for.latch
337 for.latch:
338   br label %for.body
340 for.end:
341   ret void
344 ; CHECK-LABEL: Function: test_different_pointer_bases_of_inttoptr: 2 pointers, 0 call sites
345 ; CHECK:   NoAlias:     <16 x i8>* %tmp5, <16 x i8>* %tmp7
347 define void @test_different_pointer_bases_of_inttoptr() {
348 entry:
349   br label %for.body
351 for.body:
352   %tmp = phi i32 [ %next, %for.body ], [ 1, %entry ]
353   %tmp1 = shl nsw i32 %tmp, 1
354   %tmp2 = add nuw nsw i32 %tmp1, %tmp1
355   %tmp3 = mul nsw i32 %tmp2, 1408
356   %tmp4 = add nsw i32 %tmp3, 1408
357   %tmp5 = getelementptr inbounds i8, ptr inttoptr (i32 1024 to ptr), i32 %tmp1
358   %tmp6 = load <16 x i8>, ptr %tmp5, align 1
359   %tmp7 = getelementptr inbounds i8, ptr inttoptr (i32 4096 to ptr), i32 %tmp4
360   store <16 x i8> %tmp6, ptr %tmp7, align 1
362   %next = add i32 %tmp, 2
363   %exitcond = icmp slt i32 %next, 10
364   br i1 %exitcond, label %for.body, label %for.end
366 for.end:
367   ret void