317 lines · plain
1; NOTE: Assertions have been autogenerated by utils/update_analyze_test_checks.py UTC_ARGS: --version 52; RUN: opt < %s -disable-output "-passes=print<da>" -aa-pipeline=basic-aa 2>&1 \3; RUN: | FileCheck %s4 5; Check that dependence analysis correctly handles flip-flop of base addresses.6; Bug 41488 - https://github.com/llvm/llvm-project/issues/414887 8define float @bug41488_test1(float %f) {9; CHECK-LABEL: 'bug41488_test1'10; CHECK-NEXT: Src: %0 = load float, ptr %p, align 4 --> Dst: %0 = load float, ptr %p, align 411; CHECK-NEXT: da analyze - confused!12; CHECK-NEXT: Src: %0 = load float, ptr %p, align 4 --> Dst: store float %f, ptr %q, align 413; CHECK-NEXT: da analyze - confused!14; CHECK-NEXT: Src: store float %f, ptr %q, align 4 --> Dst: store float %f, ptr %q, align 415; CHECK-NEXT: da analyze - confused!16;17entry:18 %g = alloca float, align 419 %h = alloca float, align 420 br label %for.body21 22for.body:23 %p = phi float* [ %g, %entry ], [ %q, %for.body ]24 %q = phi float* [ %h, %entry ], [ %p, %for.body ]25 %0 = load float, float* %p, align 426 store float %f, float* %q, align 427 %branch_cond = fcmp ugt float %0, 0.028 br i1 %branch_cond, label %for.cond.cleanup, label %for.body29 30for.cond.cleanup:31 ret float %f32}33 34define void @bug41488_test2(i32 %n) {35; CHECK-LABEL: 'bug41488_test2'36; CHECK-NEXT: Src: %0 = load float, ptr %p, align 4 --> Dst: %0 = load float, ptr %p, align 437; CHECK-NEXT: da analyze - confused!38; CHECK-NEXT: Src: %0 = load float, ptr %p, align 4 --> Dst: store float 0.000000e+00, ptr %q, align 439; CHECK-NEXT: da analyze - confused!40; CHECK-NEXT: Src: store float 0.000000e+00, ptr %q, align 4 --> Dst: store float 0.000000e+00, ptr %q, align 441; CHECK-NEXT: da analyze - confused!42;43entry:44 %g = alloca float, align 445 %h = alloca float, align 446 br label %for.body47 48for.body:49 %i = phi i32 [0, %entry ], [ %inc, %for.body ]50 %p = phi float* [ %g, %entry ], [ %q, %for.body ]51 %q = phi float* [ %h, %entry ], [ %p, %for.body ]52 %0 = load float, float* %p, align 453 store float 0.0, float* %q, align 454 %inc = add nuw i32 %i, 155 %branch_cond = icmp ult i32 %i, %n56 br i1 %branch_cond, label %for.body, label %for.cond.cleanup57 58for.cond.cleanup:59 ret void60}61 62; Bug 53942 - https://github.com/llvm/llvm-project/issues/5394263 64define void @bug53942_foo(i32 noundef %n, ptr noalias nocapture noundef writeonly %A, ptr noalias nocapture noundef %B) {65; CHECK-LABEL: 'bug53942_foo'66; CHECK-NEXT: Src: %.pre = load double, ptr %B, align 8 --> Dst: %.pre = load double, ptr %B, align 867; CHECK-NEXT: da analyze - consistent input [S]!68; CHECK-NEXT: Src: %.pre = load double, ptr %B, align 8 --> Dst: store double %.pre, ptr %arrayidx2, align 869; CHECK-NEXT: da analyze - confused!70; CHECK-NEXT: Src: store double %.pre, ptr %arrayidx2, align 8 --> Dst: store double %.pre, ptr %arrayidx2, align 871; CHECK-NEXT: da analyze - confused!72;73entry:74 %cmp8 = icmp sgt i32 %n, 175 br i1 %cmp8, label %for.body.preheader, label %for.cond.cleanup76 77for.body.preheader: ; preds = %entry78 %wide.trip.count = zext nneg i32 %n to i6479 br label %for.body80 81for.cond.cleanup: ; preds = %for.body, %entry82 ret void83 84for.body: ; preds = %for.body.preheader, %for.body85 %indvars.iv = phi i64 [ 1, %for.body.preheader ], [ %indvars.iv.next, %for.body ]86 %ptr1.011 = phi ptr [ %A, %for.body.preheader ], [ %ptr2.09, %for.body ]87 %ptr2.09 = phi ptr [ %B, %for.body.preheader ], [ %ptr1.011, %for.body ]88 %.pre = load double, ptr %B, align 889 %arrayidx2 = getelementptr inbounds double, ptr %ptr1.011, i64 %indvars.iv90 store double %.pre, ptr %arrayidx2, align 891 %indvars.iv.next = add nuw nsw i64 %indvars.iv, 192 %exitcond.not = icmp eq i64 %indvars.iv.next, %wide.trip.count93 br i1 %exitcond.not, label %for.cond.cleanup, label %for.body94}95 96 97; Bug 53942 - https://github.com/llvm/llvm-project/issues/5394298 99define void @bug53942_bar(i32 noundef %n, ptr noalias noundef %A, ptr noalias noundef %B) {100; CHECK-LABEL: 'bug53942_bar'101; CHECK-NEXT: Src: %0 = load double, ptr %arrayidx, align 8 --> Dst: %0 = load double, ptr %arrayidx, align 8102; CHECK-NEXT: da analyze - confused!103; CHECK-NEXT: Src: %0 = load double, ptr %arrayidx, align 8 --> Dst: store double %0, ptr %arrayidx8, align 8104; CHECK-NEXT: da analyze - confused!105; CHECK-NEXT: Src: store double %0, ptr %arrayidx8, align 8 --> Dst: store double %0, ptr %arrayidx8, align 8106; CHECK-NEXT: da analyze - confused!107;108entry:109 br label %for.cond110 111for.cond: ; preds = %for.inc, %entry112 %i.0 = phi i32 [ 1, %entry ], [ %inc, %for.inc ]113 %cmp = icmp slt i32 %i.0, %n114 br i1 %cmp, label %for.body, label %for.cond.cleanup115 116for.cond.cleanup: ; preds = %for.cond117 br label %for.end118 119for.body: ; preds = %for.cond120 %and = and i32 %i.0, 2121 %tobool.not = icmp eq i32 %and, 0122 br i1 %tobool.not, label %cond.false, label %cond.true123 124cond.true: ; preds = %for.body125 br label %cond.end126 127cond.false: ; preds = %for.body128 br label %cond.end129 130cond.end: ; preds = %cond.false, %cond.true131 %cond = phi ptr [ %A, %cond.true ], [ %B, %cond.false ]132 %and1 = and i32 %i.0, 2133 %tobool2.not = icmp eq i32 %and1, 0134 br i1 %tobool2.not, label %cond.false4, label %cond.true3135 136cond.true3: ; preds = %cond.end137 br label %cond.end5138 139cond.false4: ; preds = %cond.end140 br label %cond.end5141 142cond.end5: ; preds = %cond.false4, %cond.true3143 %cond6 = phi ptr [ %B, %cond.true3 ], [ %A, %cond.false4 ]144 %sub = add nsw i32 %i.0, -1145 %idxprom = sext i32 %sub to i64146 %arrayidx = getelementptr inbounds double, ptr %cond6, i64 %idxprom147 %0 = load double, ptr %arrayidx, align 8148 %idxprom7 = zext nneg i32 %i.0 to i64149 %arrayidx8 = getelementptr inbounds double, ptr %cond, i64 %idxprom7150 store double %0, ptr %arrayidx8, align 8151 br label %for.inc152 153for.inc: ; preds = %cond.end5154 %inc = add nuw nsw i32 %i.0, 1155 br label %for.cond156 157for.end: ; preds = %for.cond.cleanup158 ret void159}160 161; Pseudo-code for the following IR:162;163; void f(int A[][42]) {164; for (int i = 0; i < 100; i++)165; for (int j = 0; j < 41; j++)166; (j % 2 == 0 ? A[i][j] : A[i][j+1]) = 1;167; }168;169; There are loop-carried dependencies between the store instruction. For170; example, the value of %ptr0 when (i, j) = (0, 1) is %A+8, which is the same171; as when (i, j) = (0, 2).172 173define void @non_invariant_baseptr_with_identical_obj(ptr %A) {174; CHECK-LABEL: 'non_invariant_baseptr_with_identical_obj'175; CHECK-NEXT: Src: store i32 1, ptr %idx, align 4 --> Dst: store i32 1, ptr %idx, align 4176; CHECK-NEXT: da analyze - confused!177;178entry:179 br label %loop.i.header180 181loop.i.header:182 %i = phi i32 [ 0, %entry ], [ %i.inc, %loop.i.latch ]183 %A1 = getelementptr i32, ptr %A, i32 1184 br label %loop.j185 186loop.j:187 %j = phi i32 [ 0, %loop.i.header ], [ %j.inc, %loop.j ]188 %ptr0 = phi ptr [ %A, %loop.i.header ], [ %ptr1, %loop.j ]189 %ptr1 = phi ptr [ %A1, %loop.i.header ], [ %ptr0, %loop.j ]190 %idx = getelementptr [42 x i32], ptr %ptr0, i32 %i, i32 %j191 store i32 1, ptr %idx192 %j.inc = add i32 %j, 1193 %cmp.j = icmp slt i32 %j.inc, 41194 br i1 %cmp.j, label %loop.j, label %loop.i.latch195 196loop.i.latch:197 %i.inc = add i32 %i, 1198 %cmp.i = icmp slt i32 %i.inc, 100199 br i1 %cmp.i, label %loop.i.header, label %exit200 201exit:202 ret void203}204 205; Pseudo-code for the following IR:206;207; void f(int A[][42][42]) {208; for (int i = 0; i < 100; i++)209; for (int j = 0; j < 41; j++) {210; int *ptr0 = (j % 2 == 0 ? A[i][j] : A[i][j+1]);211; for (int k = 0; k < 42; k++)212; ptr0[k] = 1;213; }214; }215;216; Similar to the above case, but ptr0 is loop-invariant with respsect to the217; k-loop.218;219; Same as the above case, there are loop-carried dependencies between the220; store.221 222define void @non_invariant_baseptr_with_identical_obj2(ptr %A) {223; CHECK-LABEL: 'non_invariant_baseptr_with_identical_obj2'224; CHECK-NEXT: Src: store i32 1, ptr %idx, align 4 --> Dst: store i32 1, ptr %idx, align 4225; CHECK-NEXT: da analyze - confused!226;227entry:228 br label %loop.i.header229 230loop.i.header:231 %i = phi i32 [ 0, %entry ], [ %i.inc, %loop.i.latch ]232 %A1 = getelementptr i32, ptr %A, i32 1233 br label %loop.j.header234 235loop.j.header:236 %j = phi i32 [ 0, %loop.i.header ], [ %j.inc, %loop.j.latch ]237 %ptr0 = phi ptr [ %A, %loop.i.header ], [ %ptr1, %loop.j.latch ]238 %ptr1 = phi ptr [ %A1, %loop.i.header ], [ %ptr0, %loop.j.latch ]239 br label %loop.k240 241loop.k:242 %k = phi i32 [ 0, %loop.j.header ], [ %k.inc, %loop.k ]243 %idx = getelementptr [42 x [42 x i32]], ptr %ptr0, i32 %i, i32 %k, i32 %j244 store i32 1, ptr %idx245 %k.inc = add i32 %k, 1246 %cmp.k = icmp slt i32 %k.inc, 42247 br i1 %cmp.k, label %loop.k, label %loop.j.latch248 249loop.j.latch:250 %j.inc = add i32 %j, 1251 %cmp.j = icmp slt i32 %j.inc, 41252 br i1 %cmp.j, label %loop.j.header, label %loop.i.latch253 254loop.i.latch:255 %i.inc = add i32 %i, 1256 %cmp.i = icmp slt i32 %i.inc, 100257 br i1 %cmp.i, label %loop.i.header, label %exit258 259exit:260 ret void261}262 263; Pseudo-code that is approximately semantically equivalent to the below IR:264;265; void f(int A[][32]) {266; for (int i = 0; i < 100; i++)267; for (int j = 0; j < 15; j++) {268; int offset = (j % 2 == 0) ? 1 : 0;269; A[i][2 * j + offset + 0] = 1;270; A[i][2 * j + offset + 1] = 1;271; }272; }273;274; There are loop-carried dependencies between the two stores. For example,275; A[0][2] is accessed from both the former one when (i, j) = (0, 1) and the276; latter one when (i, j) = (0, 0).277;278define void @non_invariant_baseptr_with_identical_obj3(ptr %A) {279; CHECK-LABEL: 'non_invariant_baseptr_with_identical_obj3'280; CHECK-NEXT: Src: store i32 1, ptr %idx0, align 4 --> Dst: store i32 1, ptr %idx0, align 4281; CHECK-NEXT: da analyze - confused!282; CHECK-NEXT: Src: store i32 1, ptr %idx0, align 4 --> Dst: store i32 1, ptr %idx1, align 4283; CHECK-NEXT: da analyze - confused!284; CHECK-NEXT: Src: store i32 1, ptr %idx1, align 4 --> Dst: store i32 1, ptr %idx1, align 4285; CHECK-NEXT: da analyze - confused!286;287entry:288 br label %loop.i.header289 290loop.i.header:291 %i = phi i32 [ 0, %entry ], [ %i.inc, %loop.i.latch ]292 %A1 = getelementptr i32, ptr %A, i32 1293 br label %loop.j294 295loop.j:296 %j = phi i32 [ 0, %loop.i.header ], [ %j.inc, %loop.j ]297 %ptr0 = phi ptr [ %A1, %loop.i.header ], [ %ptr1, %loop.j ]298 %ptr1 = phi ptr [ %A, %loop.i.header ], [ %ptr0, %loop.j ]299 %j2_0 = shl i32 %j, 1300 %j2_1 = add i32 %j2_0, 1301 %idx0 = getelementptr [32 x i32], ptr %ptr0, i32 %i, i32 %j2_0302 %idx1 = getelementptr [32 x i32], ptr %ptr0, i32 %i, i32 %j2_1303 store i32 1, ptr %idx0304 store i32 1, ptr %idx1305 %j.inc = add i32 %j, 1306 %cmp.j = icmp slt i32 %j.inc, 15307 br i1 %cmp.j, label %loop.j, label %loop.i.latch308 309loop.i.latch:310 %i.inc = add i32 %i, 1311 %cmp.i = icmp slt i32 %i.inc, 100312 br i1 %cmp.i, label %loop.i.header, label %exit313 314exit:315 ret void316}317