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 8 target 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 15 define void @loop(double* nocapture %p, i64 %n) nounwind { 16 entry: 17 %j = icmp sgt i64 %n, 0 18 br i1 %j, label %bb, label %return 19 20 bb: 21 %i = phi i64 [ 0, %entry ], [ %i.next, %bb ] 22 %pi = getelementptr double, double* %p, i64 %i 23 %i.next = add i64 %i, 1 24 %pi.next = getelementptr double, double* %p, i64 %i.next 25 %x = load double, double* %pi 26 %y = load double, 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 32 return: 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 43 define void @nestedloop(double* nocapture %p, i64 %m) nounwind { 44 entry: 45 %k = icmp sgt i64 %m, 0 46 br i1 %k, label %guard, label %return 47 48 guard: 49 %l = icmp sgt i64 91, 0 50 br i1 %l, label %outer.loop, label %return 51 52 outer.loop: 53 %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ] 54 br label %bb 55 56 bb: 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, double* %p, i64 %e 62 %f = add i64 %i.next, %j 63 %pi.next.j = getelementptr double, double* %p, i64 %f 64 %x = load double, double* %pi.j 65 %y = load double, 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, double* %p, i64 %g 72 %a = load double, 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 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 83 84 return: 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 100 define void @nestedloop_more(double* nocapture %p, i64 %n, i64 %m) nounwind { 101 entry: 102 %k = icmp sgt i64 %m, 0 103 br i1 %k, label %guard, label %return 104 105 guard: 106 %l = icmp sgt i64 %n, 0 107 br i1 %l, label %outer.loop, label %return 108 109 outer.loop: 110 %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ] 111 br label %bb 112 113 bb: 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, double* %p, i64 %e 119 %f = add i64 %i.next, %j 120 %pi.next.j = getelementptr double, double* %p, i64 %f 121 %x = load double, double* %pi.j 122 %y = load double, 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, double* %p, i64 %g 129 %a = load double, 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 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 140 141 return: 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 161 define void @foo() { 162 entry: 163 %A = alloca %struct.A 164 %B = getelementptr %struct.A, %struct.A* %A, i32 0, i32 0 165 %Q = bitcast %struct.B* %B to %struct.A* 166 %Z = getelementptr %struct.A, %struct.A* %Q, i32 0, i32 1 167 %C = getelementptr %struct.B, %struct.B* %B, i32 1 168 %X = bitcast %struct.B* %C to i32* 169 %Y = getelementptr %struct.A, %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 182 define void @bar() { 183 %M = alloca %struct.A 184 %N = getelementptr %struct.A, %struct.A* %M, i32 0, i32 0 185 %O = bitcast %struct.B* %N to %struct.A* 186 %P = getelementptr %struct.A, %struct.A* %O, i32 0, i32 1 187 %R = getelementptr %struct.B, %struct.B* %N, i32 1 188 %W = bitcast %struct.B* %R to i32* 189 %V = getelementptr %struct.A, %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 196 define void @nonnegative(i64* %p) nounwind { 197 entry: 198 br label %for.body 199 200 for.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, i64* %p, i64 %inc 204 store i64 0, i64* %arrayidx 205 %tmp6 = load i64, 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 209 for.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
