1 ; RUN: opt -disable-output < %s -disable-basicaa -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, -basicaa 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 10 target 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 17 define void @loop(double* nocapture %p, i64 %n) nounwind { 18 entry: 19 %j = icmp sgt i64 %n, 0 20 br i1 %j, label %bb, label %return 21 22 bb: 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 34 return: 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 45 define void @nestedloop(double* nocapture %p, i64 %m) nounwind { 46 entry: 47 %k = icmp sgt i64 %m, 0 48 br i1 %k, label %guard, label %return 49 50 guard: 51 %l = icmp sgt i64 91, 0 52 br i1 %l, label %outer.loop, label %return 53 54 outer.loop: 55 %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ] 56 br label %bb 57 58 bb: 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 81 outer.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 86 return: 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 102 define void @nestedloop_more(double* nocapture %p, i64 %n, i64 %m) nounwind { 103 entry: 104 %k = icmp sgt i64 %m, 0 105 br i1 %k, label %guard, label %return 106 107 guard: 108 %l = icmp sgt i64 %n, 0 109 br i1 %l, label %outer.loop, label %return 110 111 outer.loop: 112 %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ] 113 br label %bb 114 115 bb: 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 138 outer.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 143 return: 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 163 define void @foo() { 164 entry: 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 184 define 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 198 define void @nonnegative(i64* %p) nounwind { 199 entry: 200 br label %for.body 201 202 for.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 211 for.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
