1; RUN: opt -disable-output < %s -disable-basic-aa -scev-aa -aa-eval -print-all-alias-modref-info \
2; RUN:   2>&1 | FileCheck %s
3; RUN: opt -disable-output < %s -aa-pipeline=scev-aa -passes=aa-eval -print-all-alias-modref-info \
4; RUN:   2>&1 | FileCheck %s
5
6; At the time of this writing, -basic-aa misses the example of the form
7; A[i+(j+1)] != A[i+j], which can arise from multi-dimensional array references,
8; and the example of the form A[0] != A[i+1], where i+1 is known to be positive.
9
10target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64"
11
12; p[i] and p[i+1] don't alias.
13
14; CHECK: Function: loop: 3 pointers, 0 call sites
15; CHECK: NoAlias: double* %pi, double* %pi.next
16
17define void @loop(double* nocapture %p, i64 %n) nounwind {
18entry:
19  %j = icmp sgt i64 %n, 0
20  br i1 %j, label %bb, label %return
21
22bb:
23  %i = phi i64 [ 0, %entry ], [ %i.next, %bb ]
24  %pi = getelementptr double, double* %p, i64 %i
25  %i.next = add i64 %i, 1
26  %pi.next = getelementptr double, double* %p, i64 %i.next
27  %x = load double, double* %pi
28  %y = load double, double* %pi.next
29  %z = fmul double %x, %y
30  store double %z, double* %pi
31  %exitcond = icmp eq i64 %i.next, %n
32  br i1 %exitcond, label %return, label %bb
33
34return:
35  ret void
36}
37
38; Slightly more involved: p[j][i], p[j][i+1], and p[j+1][i] don't alias.
39
40; CHECK: Function: nestedloop: 4 pointers, 0 call sites
41; CHECK: NoAlias: double* %pi.j, double* %pi.next.j
42; CHECK: NoAlias: double* %pi.j, double* %pi.j.next
43; CHECK: NoAlias: double* %pi.j.next, double* %pi.next.j
44
45define void @nestedloop(double* nocapture %p, i64 %m) nounwind {
46entry:
47  %k = icmp sgt i64 %m, 0
48  br i1 %k, label %guard, label %return
49
50guard:
51  %l = icmp sgt i64 91, 0
52  br i1 %l, label %outer.loop, label %return
53
54outer.loop:
55  %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ]
56  br label %bb
57
58bb:
59  %i = phi i64 [ 0, %outer.loop ], [ %i.next, %bb ]
60  %i.next = add i64 %i, 1
61
62  %e = add i64 %i, %j
63  %pi.j = getelementptr double, double* %p, i64 %e
64  %f = add i64 %i.next, %j
65  %pi.next.j = getelementptr double, double* %p, i64 %f
66  %x = load double, double* %pi.j
67  %y = load double, double* %pi.next.j
68  %z = fmul double %x, %y
69  store double %z, double* %pi.j
70
71  %o = add i64 %j, 91
72  %g = add i64 %i, %o
73  %pi.j.next = getelementptr double, double* %p, i64 %g
74  %a = load double, double* %pi.j.next
75  %b = fmul double %x, %a
76  store double %b, double* %pi.j.next
77
78  %exitcond = icmp eq i64 %i.next, 91
79  br i1 %exitcond, label %outer.latch, label %bb
80
81outer.latch:
82  %j.next = add i64 %j, 91
83  %h = icmp eq i64 %j.next, %m
84  br i1 %h, label %return, label %outer.loop
85
86return:
87  ret void
88}
89
90; Even more involved: same as nestedloop, but with a variable extent.
91; When n is 1, p[j+1][i] does alias p[j][i+1], and there's no way to
92; prove whether n will be greater than 1, so that relation will always
93; by MayAlias. The loop is guarded by a n > 0 test though, so
94; p[j+1][i] and p[j][i] can theoretically be determined to be NoAlias,
95; however the analysis currently doesn't do that.
96; TODO: Make the analysis smarter and turn that MayAlias into a NoAlias.
97
98; CHECK: Function: nestedloop_more: 4 pointers, 0 call sites
99; CHECK: NoAlias: double* %pi.j, double* %pi.next.j
100; CHECK: MayAlias: double* %pi.j, double* %pi.j.next
101
102define void @nestedloop_more(double* nocapture %p, i64 %n, i64 %m) nounwind {
103entry:
104  %k = icmp sgt i64 %m, 0
105  br i1 %k, label %guard, label %return
106
107guard:
108  %l = icmp sgt i64 %n, 0
109  br i1 %l, label %outer.loop, label %return
110
111outer.loop:
112  %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ]
113  br label %bb
114
115bb:
116  %i = phi i64 [ 0, %outer.loop ], [ %i.next, %bb ]
117  %i.next = add i64 %i, 1
118
119  %e = add i64 %i, %j
120  %pi.j = getelementptr double, double* %p, i64 %e
121  %f = add i64 %i.next, %j
122  %pi.next.j = getelementptr double, double* %p, i64 %f
123  %x = load double, double* %pi.j
124  %y = load double, double* %pi.next.j
125  %z = fmul double %x, %y
126  store double %z, double* %pi.j
127
128  %o = add i64 %j, %n
129  %g = add i64 %i, %o
130  %pi.j.next = getelementptr double, double* %p, i64 %g
131  %a = load double, double* %pi.j.next
132  %b = fmul double %x, %a
133  store double %b, double* %pi.j.next
134
135  %exitcond = icmp eq i64 %i.next, %n
136  br i1 %exitcond, label %outer.latch, label %bb
137
138outer.latch:
139  %j.next = add i64 %j, %n
140  %h = icmp eq i64 %j.next, %m
141  br i1 %h, label %return, label %outer.loop
142
143return:
144  ret void
145}
146
147; ScalarEvolution expands field offsets into constants, which allows it to
148; do aggressive analysis. Contrast this with BasicAA, which works by
149; recognizing GEP idioms.
150
151%struct.A = type { %struct.B, i32, i32 }
152%struct.B = type { double }
153
154; CHECK: Function: foo: 7 pointers, 0 call sites
155; CHECK: NoAlias: %struct.B* %B, i32* %Z
156; CHECK: NoAlias: %struct.B* %B, %struct.B* %C
157; CHECK: MustAlias: %struct.B* %C, i32* %Z
158; CHECK: NoAlias: %struct.B* %B, i32* %X
159; CHECK: MustAlias: i32* %X, i32* %Z
160; CHECK: MustAlias: %struct.B* %C, i32* %Y
161; CHECK: MustAlias: i32* %X, i32* %Y
162
163define void @foo() {
164entry:
165  %A = alloca %struct.A
166  %B = getelementptr %struct.A, %struct.A* %A, i32 0, i32 0
167  %Q = bitcast %struct.B* %B to %struct.A*
168  %Z = getelementptr %struct.A, %struct.A* %Q, i32 0, i32 1
169  %C = getelementptr %struct.B, %struct.B* %B, i32 1
170  %X = bitcast %struct.B* %C to i32*
171  %Y = getelementptr %struct.A, %struct.A* %A, i32 0, i32 1
172  ret void
173}
174
175; CHECK: Function: bar: 7 pointers, 0 call sites
176; CHECK: NoAlias: %struct.B* %N, i32* %P
177; CHECK: NoAlias: %struct.B* %N, %struct.B* %R
178; CHECK: MustAlias: %struct.B* %R, i32* %P
179; CHECK: NoAlias: %struct.B* %N, i32* %W
180; CHECK: MustAlias: i32* %P, i32* %W
181; CHECK: MustAlias: %struct.B* %R, i32* %V
182; CHECK: MustAlias: i32* %V, i32* %W
183
184define void @bar() {
185  %M = alloca %struct.A
186  %N = getelementptr %struct.A, %struct.A* %M, i32 0, i32 0
187  %O = bitcast %struct.B* %N to %struct.A*
188  %P = getelementptr %struct.A, %struct.A* %O, i32 0, i32 1
189  %R = getelementptr %struct.B, %struct.B* %N, i32 1
190  %W = bitcast %struct.B* %R to i32*
191  %V = getelementptr %struct.A, %struct.A* %M, i32 0, i32 1
192  ret void
193}
194
195; CHECK: Function: nonnegative: 2 pointers, 0 call sites
196; CHECK: NoAlias:  i64* %arrayidx, i64* %p
197
198define void @nonnegative(i64* %p) nounwind {
199entry:
200  br label %for.body
201
202for.body:                                         ; preds = %entry, %for.body
203  %i = phi i64 [ %inc, %for.body ], [ 0, %entry ] ; <i64> [#uses=2]
204  %inc = add nsw i64 %i, 1                         ; <i64> [#uses=2]
205  %arrayidx = getelementptr inbounds i64, i64* %p, i64 %inc
206  store i64 0, i64* %arrayidx
207  %tmp6 = load i64, i64* %p                            ; <i64> [#uses=1]
208  %cmp = icmp slt i64 %inc, %tmp6                 ; <i1> [#uses=1]
209  br i1 %cmp, label %for.body, label %for.end
210
211for.end:                                          ; preds = %for.body, %entry
212  ret void
213}
214
215; CHECK: 14 no alias responses
216; CHECK: 26 may alias responses
217; CHECK: 18 must alias responses
218