308 lines · plain
1; RUN: opt -da-disable-delinearization-checks -passes=loop-unroll-and-jam -allow-unroll-and-jam -unroll-and-jam-count=4 < %s -S | FileCheck %s2; RUN: opt -da-disable-delinearization-checks -aa-pipeline=basic-aa -passes='loop-unroll-and-jam' -allow-unroll-and-jam -unroll-and-jam-count=4 < %s -S | FileCheck %s3 4; CHECK-LABEL: sub_sub_less5; CHECK: %j = phi6; CHECK-NOT: %j.1 = phi7;8; sub_sub_less should NOT be unroll-and-jammed due to a loop-carried dependency.9; Memory accesses:10; - A[i][j] = 1 (write to current iteration)11; - A[i+1][j-1] = add (write to next i iteration, previous j iteration)12; The dependency: A[i+1][j-1] from iteration (i,j) may conflict with A[i'][j']13; from a later iteration when i'=i+1 and j'=j-1, creating a backward dependency14; in the j dimension that prevents safe unroll-and-jam.15define void @sub_sub_less(ptr noalias nocapture %A, i32 %N, ptr noalias nocapture readonly %B) {16entry:17 %cmp = icmp sgt i32 %N, 018 br i1 %cmp, label %for.outer, label %cleanup19 20for.outer:21 %i = phi i32 [ %add7, %for.latch ], [ 0, %entry ]22 br label %for.inner23 24for.inner:25 %j = phi i32 [ %add6, %for.inner ], [ 1, %for.outer ]26 %sum = phi i32 [ %add, %for.inner ], [ 0, %for.outer ]27 %arrayidx5 = getelementptr inbounds i32, ptr %B, i32 %j28 %0 = load i32, ptr %arrayidx5, align 429 %mul = mul nsw i32 %0, %i30 %add = add nsw i32 %mul, %sum31 %add6 = add nuw nsw i32 %j, 132 %arrayidx = getelementptr inbounds [100 x i32], ptr %A, i32 %i, i32 %j33 store i32 1, ptr %arrayidx, align 434 %add72 = add nuw nsw i32 %i, 135 %add73 = add nuw nsw i32 %j, -136 %arrayidx8 = getelementptr inbounds [100 x i32], ptr %A, i32 %add72, i32 %add7337 store i32 %add, ptr %arrayidx8, align 438 %exitcond = icmp eq i32 %add6, %N39 br i1 %exitcond, label %for.latch, label %for.inner40 41for.latch:42 %add7 = add nuw nsw i32 %i, 143 %exitcond29 = icmp eq i32 %add7, %N44 br i1 %exitcond29, label %cleanup, label %for.outer45 46cleanup:47 ret void48}49 50 51; CHECK-LABEL: sub_sub_eq52; CHECK: %j = phi53; CHECK: %j.1 = phi54; CHECK: %j.2 = phi55; CHECK: %j.3 = phi56;57; sub_sub_eq SHOULD be unroll-and-jammed (count=4) as it's safe.58; Memory accesses:59; - A[i][j] = 1 (write to current iteration)60; - A[i+1][j] = add (write to next i iteration, same j iteration)61; No dependency conflict: When unroll-and-jamming with count=4, the i loop62; iterations (i, i+1, i+2, i+3) are unrolled and their j loops are jammed63; together. Unroll-and-jam factor 4:64;65; for (int i = 0; i < N; i += 4)66; for (int j = 0; j < N; ++j) {67; // i iteration68; A[i][j] = 1; A[i+1][j] = sum_i;69; // i+1 iteration70; A[i+1][j] = 1; A[i+2][j] = sum_i1;71; // i+2 iteration72; A[i+2][j] = 1; A[i+3][j] = sum_i2;73; // i+3 iteration74; A[i+3][j] = 1; A[i+4][j] = sum_i3;75; }76;77; A[i+1][j] from iteration i doesn't conflict with A[i'][j'] from unrolled78; iterations since each unrolled i iteration accesses its own row i+1, i+2, i+3.79; j' values are identical, but accesses happen to different rows in the same j80; iteration before moving to the next j value.81define void @sub_sub_eq(ptr noalias nocapture %A, i32 %N, ptr noalias nocapture readonly %B) {82entry:83 %cmp = icmp sgt i32 %N, 084 br i1 %cmp, label %for.outer, label %cleanup85 86for.outer:87 %i = phi i32 [ %add7, %for.latch ], [ 0, %entry ]88 br label %for.inner89 90for.inner:91 %j = phi i32 [ %add6, %for.inner ], [ 0, %for.outer ]92 %sum = phi i32 [ %add, %for.inner ], [ 0, %for.outer ]93 %arrayidx5 = getelementptr inbounds i32, ptr %B, i32 %j94 %0 = load i32, ptr %arrayidx5, align 495 %mul = mul nsw i32 %0, %i96 %add = add nsw i32 %mul, %sum97 %add6 = add nuw nsw i32 %j, 198 %arrayidx = getelementptr inbounds [100 x i32], ptr %A, i32 %i, i32 %j99 store i32 1, ptr %arrayidx, align 4100 %add72 = add nuw nsw i32 %i, 1101 %add73 = add nuw nsw i32 %j, 0102 %arrayidx8 = getelementptr inbounds [100 x i32], ptr %A, i32 %add72, i32 %add73103 store i32 %add, ptr %arrayidx8, align 4104 %exitcond = icmp eq i32 %add6, %N105 br i1 %exitcond, label %for.latch, label %for.inner106 107for.latch:108 %add7 = add nuw nsw i32 %i, 1109 %exitcond29 = icmp eq i32 %add7, %N110 br i1 %exitcond29, label %cleanup, label %for.outer111 112cleanup:113 ret void114}115 116 117; CHECK-LABEL: sub_sub_more118; CHECK: %j = phi119; CHECK: %j.1 = phi120; CHECK: %j.2 = phi121; CHECK: %j.3 = phi122;123; sub_sub_more SHOULD be unroll-and-jammed (count=4) as it's safe.124; Memory accesses:125; - A[i][j] = 1 (write to current iteration)126; - A[i+1][j+1] = add (write to next i iteration, next j iteration)127; No dependency conflict: The forward dependency pattern (j+1 in i dimension)128; is safe. Unroll-and-jam factor 4:129;130; for (int i = 0; i < N; i += 4)131; for (int j = 0; j < N; ++j) {132; // i iteration133; A[i][j] = 1; A[i+1][j+1] = sum_i;134; // i+1 iteration135; A[i+1][j] = 1; A[i+2][j+1] = sum_i1;136; // i+2 iteration137; A[i+2][j] = 1; A[i+3][j+1] = sum_i2;138; // i+3 iteration139; A[i+3][j] = 1; A[i+4][j+1] = sum_i3;140; }141;142; A[i+1][j+1] from iteration i accesses row i+1 and column j+1, which is143; disjoint from the accesses in the same iteration. The forward dependency144; pattern doesn't create conflicts between unrolled i iterations.145define void @sub_sub_more(ptr noalias nocapture %A, i32 %N, ptr noalias nocapture readonly %B) {146entry:147 %cmp = icmp sgt i32 %N, 0148 br i1 %cmp, label %for.outer, label %cleanup149 150for.outer:151 %i = phi i32 [ %add7, %for.latch ], [ 0, %entry ]152 br label %for.inner153 154for.inner:155 %j = phi i32 [ %add6, %for.inner ], [ 0, %for.outer ]156 %sum = phi i32 [ %add, %for.inner ], [ 0, %for.outer ]157 %arrayidx5 = getelementptr inbounds i32, ptr %B, i32 %j158 %0 = load i32, ptr %arrayidx5, align 4159 %mul = mul nsw i32 %0, %i160 %add = add nsw i32 %mul, %sum161 %add6 = add nuw nsw i32 %j, 1162 %arrayidx = getelementptr inbounds [100 x i32], ptr %A, i32 %i, i32 %j163 store i32 1, ptr %arrayidx, align 4164 %add72 = add nuw nsw i32 %i, 1165 %add73 = add nuw nsw i32 %j, 1166 %arrayidx8 = getelementptr inbounds [100 x i32], ptr %A, i32 %add72, i32 %add73167 store i32 %add, ptr %arrayidx8, align 4168 %exitcond = icmp eq i32 %add6, %N169 br i1 %exitcond, label %for.latch, label %for.inner170 171for.latch:172 %add7 = add nuw nsw i32 %i, 1173 %exitcond29 = icmp eq i32 %add7, %N174 br i1 %exitcond29, label %cleanup, label %for.outer175 176cleanup:177 ret void178}179 180; CHECK-LABEL: sub_sub_less_3d181; CHECK: %k = phi182; CHECK-NOT: %k.1 = phi183;184; sub_sub_less_3d should NOT be unroll-and-jammed due to a loop-carried dependency.185; Memory accesses:186; - A3d[i][j][k] = 0 (write to current iteration)187; - A3d[i+1][j][k-1] = 0 (write to next i iteration, previous k iteration)188; The dependency: A[i+1][j][k-1] from iteration (i,j,k) may conflict with189; A[i'][j'][k'] from a later iteration when i'=i+1 and k'=k-1, creating a190; backward dependency in the k dimension that prevents safe unroll-and-jam.191; This is a 3D version of the same pattern as sub_sub_less.192;193; for (long i = 0; i < 100; ++i)194; for (long j = 0; j < 100; ++j)195; for (long k = 1; k < 100; ++k) {196; A[i][j][k] = 5;197; A[i+1][j][k-1] = 10;198; }199 200define void @sub_sub_less_3d(ptr noalias %A) {201entry:202 br label %for.i203 204for.i:205 %i = phi i32 [ 0, %entry ], [ %inc.i, %for.i.latch ]206 br label %for.j207 208for.j:209 %j = phi i32 [ 0, %for.i ], [ %inc.j, %for.j.latch ]210 br label %for.k211 212for.k:213 %k = phi i32 [ 1, %for.j ], [ %inc.k, %for.k ]214 %arrayidx = getelementptr inbounds [100 x [100 x i32]], ptr %A, i32 %i, i32 %j, i32 %k215 store i32 5, ptr %arrayidx, align 4216 %add.i = add nsw i32 %i, 1217 %sub.k = add nsw i32 %k, -1218 %arrayidx2 = getelementptr inbounds [100 x [100 x i32]], ptr %A, i32 %add.i, i32 %j, i32 %sub.k219 store i32 10, ptr %arrayidx2, align 4220 %inc.k = add nsw i32 %k, 1221 %cmp.k = icmp slt i32 %inc.k, 100222 br i1 %cmp.k, label %for.k, label %for.j.latch223 224for.j.latch:225 %inc.j = add nsw i32 %j, 1226 %cmp.j = icmp slt i32 %inc.j, 100227 br i1 %cmp.j, label %for.j, label %for.i.latch, !llvm.loop !1228 229for.i.latch:230 %inc.i = add nsw i32 %i, 1231 %cmp.i = icmp slt i32 %inc.i, 100232 br i1 %cmp.i, label %for.i, label %for.end233 234for.end:235 ret void236}237 238; CHECK-LABEL: sub_sub_outer_scalar239; CHECK: %k = phi240; CHECK: %k.1 = phi241; CHECK: %k.2 = phi242; CHECK: %k.3 = phi243;244; sub_sub_outer_scalar SHOULD be unroll-and-jammed (count=4) as it's safe.245; Memory accesses:246; - load from A[j][k] (read from current j iteration)247; - store to A[j-1][k] (write to previous j iteration)248; The dependency: reading A[j][k] and writing A[j-1][k] creates a backward249; dependency, but execution order is preserved. Unroll-and-jam factor 4:250;251; for (int i = 0; i < 100; i++)252; for (int j = 1; j < 100; j += 4)253; for (int k = 0; k < 100; k++) {254; // j iteration255; temp0 = A[j][k]; A[j-1][k] = temp0;256; // j+1 iteration257; temp1 = A[j+1][k]; A[j][k] = temp1;258; // j+2 iteration259; temp2 = A[j+2][k]; A[j+1][k] = temp2;260; // j+3 iteration261; temp3 = A[j+3][k]; A[j+2][k] = temp3;262; }263;264; All k iterations for each j iteration (including j+1, j+2, j+3) are completed265; before moving to the next j group, so j+1's store to A[j][k] doesn't conflict266; with j's load from A[j][k] because they happen in different k loop invocations.267define void @sub_sub_outer_scalar(ptr %A) {268entry:269 br label %for.i270 271for.i:272 %i = phi i64 [ 0, %entry ], [ %inc.i, %for.i.latch ]273 br label %for.j274 275for.j:276 %j = phi i64 [ 1, %for.i ], [ %inc.j, %for.j.latch ]277 br label %for.k278 279for.k:280 %k = phi i64 [ 0, %for.j ], [ %inc.k, %for.k ]281 %arrayidx = getelementptr inbounds [100 x i32], ptr %A, i64 %j282 %arrayidx7 = getelementptr inbounds [100 x i32], ptr %arrayidx, i64 0, i64 %k283 %0 = load i32, ptr %arrayidx7, align 4284 %sub.j = sub nsw i64 %j, 1285 %arrayidx8 = getelementptr inbounds [100 x i32], ptr %A, i64 %sub.j286 %arrayidx9 = getelementptr inbounds [100 x i32], ptr %arrayidx8, i64 0, i64 %k287 store i32 %0, ptr %arrayidx9, align 4288 %inc.k = add nsw i64 %k, 1289 %cmp.k = icmp slt i64 %inc.k, 100290 br i1 %cmp.k, label %for.k, label %for.j.latch291 292for.j.latch:293 %inc.j = add nsw i64 %j, 1294 %cmp.j = icmp slt i64 %inc.j, 100295 br i1 %cmp.j, label %for.j, label %for.i.latch296 297for.i.latch:298 %inc.i = add nsw i64 %i, 1299 %cmp.i = icmp slt i64 %inc.i, 100300 br i1 %cmp.i, label %for.i, label %for.end301 302for.end:303 ret void304}305 306!1 = distinct !{!1, !2}307!2 = !{!"llvm.loop.unroll_and_jam.disable"}308