1; RUN: opt < %s -scev-aa -aa-eval -print-all-alias-modref-info \
2; RUN:   2>&1 | FileCheck %s
3
4; At the time of this writing, -basicaa 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.
7
8target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64"
9
10; p[i] and p[i+1] don't alias.
11
12; CHECK: Function: loop: 3 pointers, 0 call sites
13; CHECK: NoAlias: double* %pi, double* %pi.next
14
15define void @loop(double* nocapture %p, i64 %n) nounwind {
16entry:
17  %j = icmp sgt i64 %n, 0
18  br i1 %j, label %bb, label %return
19
20bb:
21  %i = phi i64 [ 0, %entry ], [ %i.next, %bb ]
22  %pi = getelementptr double* %p, i64 %i
23  %i.next = add i64 %i, 1
24  %pi.next = getelementptr double* %p, i64 %i.next
25  %x = load double* %pi
26  %y = load double* %pi.next
27  %z = fmul double %x, %y
28  store double %z, double* %pi
29  %exitcond = icmp eq i64 %i.next, %n
30  br i1 %exitcond, label %return, label %bb
31
32return:
33  ret void
34}
35
36; Slightly more involved: p[j][i], p[j][i+1], and p[j+1][i] don't alias.
37
38; CHECK: Function: nestedloop: 4 pointers, 0 call sites
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
42
43define void @nestedloop(double* nocapture %p, i64 %m) nounwind {
44entry:
45  %k = icmp sgt i64 %m, 0
46  br i1 %k, label %guard, label %return
47
48guard:
49  %l = icmp sgt i64 91, 0
50  br i1 %l, label %outer.loop, label %return
51
52outer.loop:
53  %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ]
54  br label %bb
55
56bb:
57  %i = phi i64 [ 0, %outer.loop ], [ %i.next, %bb ]
58  %i.next = add i64 %i, 1
59
60  %e = add i64 %i, %j
61  %pi.j = getelementptr double* %p, i64 %e
62  %f = add i64 %i.next, %j
63  %pi.next.j = getelementptr double* %p, i64 %f
64  %x = load double* %pi.j
65  %y = load double* %pi.next.j
66  %z = fmul double %x, %y
67  store double %z, double* %pi.j
68
69  %o = add i64 %j, 91
70  %g = add i64 %i, %o
71  %pi.j.next = getelementptr double* %p, i64 %g
72  %a = load double* %pi.j.next
73  %b = fmul double %x, %a
74  store double %b, double* %pi.j.next
75
76  %exitcond = icmp eq i64 %i.next, 91
77  br i1 %exitcond, label %outer.latch, label %bb
78
79outer.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
83
84return:
85  ret void
86}
87
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.
95
96; CHECK: Function: nestedloop_more: 4 pointers, 0 call sites
97; CHECK: NoAlias: double* %pi.j, double* %pi.next.j
98; CHECK: MayAlias: double* %pi.j, double* %pi.j.next
99
100define void @nestedloop_more(double* nocapture %p, i64 %n, i64 %m) nounwind {
101entry:
102  %k = icmp sgt i64 %m, 0
103  br i1 %k, label %guard, label %return
104
105guard:
106  %l = icmp sgt i64 %n, 0
107  br i1 %l, label %outer.loop, label %return
108
109outer.loop:
110  %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ]
111  br label %bb
112
113bb:
114  %i = phi i64 [ 0, %outer.loop ], [ %i.next, %bb ]
115  %i.next = add i64 %i, 1
116
117  %e = add i64 %i, %j
118  %pi.j = getelementptr double* %p, i64 %e
119  %f = add i64 %i.next, %j
120  %pi.next.j = getelementptr double* %p, i64 %f
121  %x = load double* %pi.j
122  %y = load double* %pi.next.j
123  %z = fmul double %x, %y
124  store double %z, double* %pi.j
125
126  %o = add i64 %j, %n
127  %g = add i64 %i, %o
128  %pi.j.next = getelementptr double* %p, i64 %g
129  %a = load double* %pi.j.next
130  %b = fmul double %x, %a
131  store double %b, double* %pi.j.next
132
133  %exitcond = icmp eq i64 %i.next, %n
134  br i1 %exitcond, label %outer.latch, label %bb
135
136outer.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
140
141return:
142  ret void
143}
144
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.
148
149%struct.A = type { %struct.B, i32, i32 }
150%struct.B = type { double }
151
152; CHECK: Function: foo: 7 pointers, 0 call sites
153; CHECK: NoAlias: %struct.B* %B, i32* %Z
154; CHECK: NoAlias: %struct.B* %B, %struct.B* %C
155; CHECK: MustAlias: %struct.B* %C, i32* %Z
156; CHECK: NoAlias: %struct.B* %B, i32* %X
157; CHECK: MustAlias: i32* %X, i32* %Z
158; CHECK: MustAlias: %struct.B* %C, i32* %Y
159; CHECK: MustAlias: i32* %X, i32* %Y
160
161define void @foo() {
162entry:
163  %A = alloca %struct.A
164  %B = getelementptr %struct.A* %A, i32 0, i32 0
165  %Q = bitcast %struct.B* %B to %struct.A*
166  %Z = getelementptr %struct.A* %Q, i32 0, i32 1
167  %C = getelementptr %struct.B* %B, i32 1
168  %X = bitcast %struct.B* %C to i32*
169  %Y = getelementptr %struct.A* %A, i32 0, i32 1
170  ret void
171}
172
173; CHECK: Function: bar: 7 pointers, 0 call sites
174; CHECK: NoAlias: %struct.B* %N, i32* %P
175; CHECK: NoAlias: %struct.B* %N, %struct.B* %R
176; CHECK: MustAlias: %struct.B* %R, i32* %P
177; CHECK: NoAlias: %struct.B* %N, i32* %W
178; CHECK: MustAlias: i32* %P, i32* %W
179; CHECK: MustAlias: %struct.B* %R, i32* %V
180; CHECK: MustAlias: i32* %V, i32* %W
181
182define void @bar() {
183  %M = alloca %struct.A
184  %N = getelementptr %struct.A* %M, i32 0, i32 0
185  %O = bitcast %struct.B* %N to %struct.A*
186  %P = getelementptr %struct.A* %O, i32 0, i32 1
187  %R = getelementptr %struct.B* %N, i32 1
188  %W = bitcast %struct.B* %R to i32*
189  %V = getelementptr %struct.A* %M, i32 0, i32 1
190  ret void
191}
192
193; CHECK: Function: nonnegative: 2 pointers, 0 call sites
194; CHECK: NoAlias:  i64* %arrayidx, i64* %p
195
196define void @nonnegative(i64* %p) nounwind {
197entry:
198  br label %for.body
199
200for.body:                                         ; preds = %entry, %for.body
201  %i = phi i64 [ %inc, %for.body ], [ 0, %entry ] ; <i64> [#uses=2]
202  %inc = add nsw i64 %i, 1                         ; <i64> [#uses=2]
203  %arrayidx = getelementptr inbounds i64* %p, i64 %inc
204  store i64 0, i64* %arrayidx
205  %tmp6 = load i64* %p                            ; <i64> [#uses=1]
206  %cmp = icmp slt i64 %inc, %tmp6                 ; <i1> [#uses=1]
207  br i1 %cmp, label %for.body, label %for.end
208
209for.end:                                          ; preds = %for.body, %entry
210  ret void
211}
212
213; CHECK: 14 no alias responses
214; CHECK: 26 may alias responses
215; CHECK: 18 must alias responses
216