369 lines · plain
1; RUN: opt -disable-output < %s -aa-pipeline=scev-aa -passes=aa-eval -print-all-alias-modref-info \2; RUN: 2>&1 | FileCheck %s3 4; At the time of this writing, misses the example of the form5; 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-LABEL: Function: loop13; CHECK: NoAlias: double* %pi, double* %pi.next14 15define void @loop(ptr nocapture %p, i64 %n) nounwind {16entry:17 %j = icmp sgt i64 %n, 018 br i1 %j, label %bb, label %return19 20bb:21 %i = phi i64 [ 0, %entry ], [ %i.next, %bb ]22 %pi = getelementptr double, ptr %p, i64 %i23 %i.next = add i64 %i, 124 %pi.next = getelementptr double, ptr %p, i64 %i.next25 %x = load double, ptr %pi26 %y = load double, ptr %pi.next27 %z = fmul double %x, %y28 store double %z, ptr %pi29 %exitcond = icmp eq i64 %i.next, %n30 br i1 %exitcond, label %return, label %bb31 32return:33 ret void34}35 36; Slightly more involved: p[j][i], p[j][i+1], and p[j+1][i] don't alias.37 38; CHECK-LABEL: Function: nestedloop39; CHECK: NoAlias: double* %pi.j, double* %pi.next.j40; CHECK: NoAlias: double* %pi.j, double* %pi.j.next41; CHECK: NoAlias: double* %pi.j.next, double* %pi.next.j42 43define void @nestedloop(ptr nocapture %p, i64 %m) nounwind {44entry:45 %k = icmp sgt i64 %m, 046 br i1 %k, label %guard, label %return47 48guard:49 %l = icmp sgt i64 91, 050 br i1 %l, label %outer.loop, label %return51 52outer.loop:53 %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ]54 br label %bb55 56bb:57 %i = phi i64 [ 0, %outer.loop ], [ %i.next, %bb ]58 %i.next = add i64 %i, 159 60 %e = add i64 %i, %j61 %pi.j = getelementptr double, ptr %p, i64 %e62 %f = add i64 %i.next, %j63 %pi.next.j = getelementptr double, ptr %p, i64 %f64 %x = load double, ptr %pi.j65 %y = load double, ptr %pi.next.j66 %z = fmul double %x, %y67 store double %z, ptr %pi.j68 69 %o = add i64 %j, 9170 %g = add i64 %i, %o71 %pi.j.next = getelementptr double, ptr %p, i64 %g72 %a = load double, ptr %pi.j.next73 %b = fmul double %x, %a74 store double %b, ptr %pi.j.next75 76 %exitcond = icmp eq i64 %i.next, 9177 br i1 %exitcond, label %outer.latch, label %bb78 79outer.latch:80 %j.next = add i64 %j, 9181 %h = icmp eq i64 %j.next, %m82 br i1 %h, label %return, label %outer.loop83 84return:85 ret void86}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 to90; prove whether n will be greater than 1, so that relation will always91; by MayAlias. The loop is guarded by a n > 0 test though, so92; 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-LABEL: Function: nestedloop_more97; CHECK: NoAlias: double* %pi.j, double* %pi.next.j98; CHECK: MayAlias: double* %pi.j, double* %pi.j.next99 100define void @nestedloop_more(ptr nocapture %p, i64 %n, i64 %m) nounwind {101entry:102 %k = icmp sgt i64 %m, 0103 br i1 %k, label %guard, label %return104 105guard:106 %l = icmp sgt i64 %n, 0107 br i1 %l, label %outer.loop, label %return108 109outer.loop:110 %j = phi i64 [ 0, %guard ], [ %j.next, %outer.latch ]111 br label %bb112 113bb:114 %i = phi i64 [ 0, %outer.loop ], [ %i.next, %bb ]115 %i.next = add i64 %i, 1116 117 %e = add i64 %i, %j118 %pi.j = getelementptr double, ptr %p, i64 %e119 %f = add i64 %i.next, %j120 %pi.next.j = getelementptr double, ptr %p, i64 %f121 %x = load double, ptr %pi.j122 %y = load double, ptr %pi.next.j123 %z = fmul double %x, %y124 store double %z, ptr %pi.j125 126 %o = add i64 %j, %n127 %g = add i64 %i, %o128 %pi.j.next = getelementptr double, ptr %p, i64 %g129 %a = load double, ptr %pi.j.next130 %b = fmul double %x, %a131 store double %b, ptr %pi.j.next132 133 %exitcond = icmp eq i64 %i.next, %n134 br i1 %exitcond, label %outer.latch, label %bb135 136outer.latch:137 %j.next = add i64 %j, %n138 %h = icmp eq i64 %j.next, %m139 br i1 %h, label %return, label %outer.loop140 141return:142 ret void143}144 145; ScalarEvolution expands field offsets into constants, which allows it to146; do aggressive analysis. Contrast this with BasicAA, which works by147; recognizing GEP idioms.148 149%struct.A = type { %struct.B, i32, i32 }150%struct.B = type { double }151 152; CHECK-LABEL: Function: foo153; CHECK-DAG: NoAlias: %struct.B* %A, i32* %Z154; CHECK-DAG: NoAlias: %struct.B* %A, %struct.B* %C155; CHECK-DAG: MustAlias: %struct.B* %C, i32* %Z156; CHECK-DAG: NoAlias: %struct.B* %A, i32* %C157; CHECK-DAG: MustAlias: i32* %C, i32* %Z158; CHECK-DAG: MustAlias: %struct.B* %C, i32* %Y159; CHECK-DAG: MustAlias: i32* %C, i32* %Y160 161define void @foo() {162entry:163 %A = alloca %struct.A164 %Z = getelementptr %struct.A, ptr %A, i32 0, i32 1165 %C = getelementptr %struct.B, ptr %A, i32 1166 %Y = getelementptr %struct.A, ptr %A, i32 0, i32 1167 load %struct.B, ptr %A168 load %struct.B, ptr %C169 load i32, ptr %C170 load i32, ptr %Y171 load i32, ptr %Z172 ret void173}174 175; CHECK-LABEL: Function: bar176; CHECK-DAG: NoAlias: %struct.B* %M, i32* %P177; CHECK-DAG: NoAlias: %struct.B* %M, %struct.B* %R178; CHECK-DAG: MustAlias: i32* %P, %struct.B* %R179; CHECK-DAG: NoAlias: %struct.B* %M, i32* %R180; CHECK-DAG: MustAlias: i32* %P, i32* %R181; CHECK-DAG: MustAlias: %struct.B* %R, i32* %V182; CHECK-DAG: MustAlias: i32* %R, i32* %V183 184define void @bar() {185 %M = alloca %struct.A186 %P = getelementptr %struct.A, ptr %M, i32 0, i32 1187 %R = getelementptr %struct.B, ptr %M, i32 1188 %V = getelementptr %struct.A, ptr %M, i32 0, i32 1189 load %struct.B, ptr %M190 load %struct.B, ptr %R191 load i32, ptr %P192 load i32, ptr %V193 load i32, ptr %R194 ret void195}196 197; CHECK: Function: nonnegative: 2 pointers, 0 call sites198; CHECK: NoAlias: i64* %arrayidx, i64* %p199 200define void @nonnegative(ptr %p) nounwind {201entry:202 br label %for.body203 204for.body: ; preds = %entry, %for.body205 %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 %inc208 store i64 0, ptr %arrayidx209 %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.end212 213for.end: ; preds = %for.body, %entry214 ret void215}216 217; CHECK-LABEL: Function: test_no_dom: 3 pointers, 0 call sites218; CHECK: MayAlias: double* %addr1, double* %data219; CHECK: NoAlias: double* %addr2, double* %data220; CHECK: MayAlias: double* %addr1, double* %addr2221 222; In this case, checking %addr1 and %add2 involves two addrecs in two223; different loops where neither dominates the other. This used to crash224; because we expected the arguments to an AddExpr to have a strict225; dominance order.226define void @test_no_dom(ptr %data, i1 %arg) {227entry:228 load double, ptr %data229 br label %for.body230 231for.body:232 %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.latch ]233 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1234 br i1 %arg, label %subloop1, label %subloop2235 236subloop1:237 %iv1 = phi i32 [0, %for.body], [%iv1.next, %subloop1]238 %iv1.next = add i32 %iv1, 1239 %addr1 = getelementptr double, ptr %data, i32 %iv1240 store double 0.0, ptr %addr1241 %cmp1 = icmp slt i32 %iv1, 200242 br i1 %cmp1, label %subloop1, label %for.latch243 244subloop2:245 %iv2 = phi i32 [400, %for.body], [%iv2.next, %subloop2]246 %iv2.next = add i32 %iv2, 1247 %addr2 = getelementptr double, ptr %data, i32 %iv2248 store double 0.0, ptr %addr2249 %cmp2 = icmp slt i32 %iv2, 600250 br i1 %cmp2, label %subloop2, label %for.latch251 252for.latch:253 br label %for.body254 255for.end:256 ret void257}258 259declare ptr @get_addr(i32 %i)260 261; CHECK-LABEL: Function: test_no_dom2: 3 pointers, 2 call sites262; CHECK: MayAlias: double* %addr1, double* %data263; CHECK: MayAlias: double* %addr2, double* %data264; CHECK: MayAlias: double* %addr1, double* %addr2265 266; In this case, checking %addr1 and %add2 involves two addrecs in two267; different loops where neither dominates the other. This is analogous268; to test_no_dom, but involves SCEVUnknown as opposed to SCEVAddRecExpr.269define void @test_no_dom2(ptr %data, i1 %arg) {270entry:271 load double, ptr %data272 br label %for.body273 274for.body:275 %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.latch ]276 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1277 br i1 %arg, label %subloop1, label %subloop2278 279subloop1:280 %iv1 = phi i32 [0, %for.body], [%iv1.next, %subloop1]281 %iv1.next = add i32 %iv1, 1282 %addr1 = call ptr @get_addr(i32 %iv1)283 store double 0.0, ptr %addr1284 %cmp1 = icmp slt i32 %iv1, 200285 br i1 %cmp1, label %subloop1, label %for.latch286 287subloop2:288 %iv2 = phi i32 [400, %for.body], [%iv2.next, %subloop2]289 %iv2.next = add i32 %iv2, 1290 %addr2 = call ptr @get_addr(i32 %iv2)291 store double 0.0, ptr %addr2292 %cmp2 = icmp slt i32 %iv2, 600293 br i1 %cmp2, label %subloop2, label %for.latch294 295for.latch:296 br label %for.body297 298for.end:299 ret void300}301 302 303; CHECK-LABEL: Function: test_dom: 3 pointers, 0 call sites304; CHECK: MayAlias: double* %addr1, double* %data305; CHECK: NoAlias: double* %addr2, double* %data306; CHECK: NoAlias: double* %addr1, double* %addr2307 308; This is a variant of test_non_dom where the second subloop is309; dominated by the first. As a result of that, we can nest the310; addrecs and cancel out the %data base pointer.311define void @test_dom(ptr %data) {312entry:313 load double, ptr %data314 br label %for.body315 316for.body:317 %indvars.iv = phi i64 [ 0, %entry ], [ %indvars.iv.next, %for.latch ]318 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1319 br label %subloop1320 321subloop1:322 %iv1 = phi i32 [0, %for.body], [%iv1.next, %subloop1]323 %iv1.next = add i32 %iv1, 1324 %addr1 = getelementptr double, ptr %data, i32 %iv1325 store double 0.0, ptr %addr1326 %cmp1 = icmp slt i32 %iv1, 200327 br i1 %cmp1, label %subloop1, label %subloop2328 329subloop2:330 %iv2 = phi i32 [400, %subloop1], [%iv2.next, %subloop2]331 %iv2.next = add i32 %iv2, 1332 %addr2 = getelementptr double, ptr %data, i32 %iv2333 store double 0.0, ptr %addr2334 %cmp2 = icmp slt i32 %iv2, 600335 br i1 %cmp2, label %subloop2, label %for.latch336 337for.latch:338 br label %for.body339 340for.end:341 ret void342}343 344; CHECK-LABEL: Function: test_different_pointer_bases_of_inttoptr: 2 pointers, 0 call sites345; CHECK: NoAlias: <16 x i8>* %tmp5, <16 x i8>* %tmp7346 347define void @test_different_pointer_bases_of_inttoptr() {348entry:349 br label %for.body350 351for.body:352 %tmp = phi i32 [ %next, %for.body ], [ 1, %entry ]353 %tmp1 = shl nsw i32 %tmp, 1354 %tmp2 = add nuw nsw i32 %tmp1, %tmp1355 %tmp3 = mul nsw i32 %tmp2, 1408356 %tmp4 = add nsw i32 %tmp3, 1408357 %tmp5 = getelementptr inbounds i8, ptr inttoptr (i32 1024 to ptr), i32 %tmp1358 %tmp6 = load <16 x i8>, ptr %tmp5, align 1359 %tmp7 = getelementptr inbounds i8, ptr inttoptr (i32 4096 to ptr), i32 %tmp4360 store <16 x i8> %tmp6, ptr %tmp7, align 1361 362 %next = add i32 %tmp, 2363 %exitcond = icmp slt i32 %next, 10364 br i1 %exitcond, label %for.body, label %for.end365 366for.end:367 ret void368}369