[ZoneAlgo] Allow two writes that write identical values into same array slot

[grosser]

Summary

Two write statements which write into the very same array slot generally are
conflicting. However, in case the value that is written is identical, this
does not cause any problem. Hence, allow such write pairs in this specific
situation.

[grosser]

Improve style

[grosser]

Update formatting II

[grosser]

Update formatting III

[Meinersbur]

lib/CodeGen/PPCGCodeGeneration.cpp

199–200

[Nit] unrelated?

228

[Nit] unrelated?

237

[Nit] unrelated?

lib/Transform/ZoneAlgo.cpp

291

[Suggestion] This will reject as soon as there is a third store that writes a different value somewhere unrelated. Maybe add a TODO comment and/or add a FAIL: * test case to improve this some day?

292–293

[Suggestion] Does either isLatestArrayKind() or MA->isOriginalArrayKind() suffice?
(I think we only implemented changing scalar to array access, not the other way around; scalar accesses are assumed to either at the beginning or end of the statement, never associated with a LoadInst/StoreInst)

test/ForwardOpTree/forward_load_double_write.ll

3

• Update the comment what's tested here.

[etherzhhb]

test/ForwardOpTree/forward_load_double_write.ll

21–22

Isn't this could be "canonicalized" by gvn?

[etherzhhb]

test/ForwardOpTree/forward_load_double_write.ll

21–22

or dead store elimination

[grosser]

test/ForwardOpTree/forward_load_double_write.ll

21–22

Maybe then this is a non-optimal test case. In case there are other memory accesses between these two stores, gvn and dead store elimination is often not effective. Clearly, this is not very visible in this simple test case.

[etherzhhb]

test/ForwardOpTree/forward_load_double_write.ll

21–22

Ok

[Meinersbur]

test/ForwardOpTree/forward_load_double_write.ll

21–22

This covers a special situation occurring in Polybench's covariance/correlation (and typical in algorithms that cover symmetric matrices):

for (int i = 0; i < n; i+=1)
  for (int j = 0; j <= i; j+=1) {
    double x = ...;
    C[i][j] = x;
    C[j][i] = x;
  }

For i==j, the same value is written twice to the same element. Double writes to the same element are not allowed in DeLICM because its algorithm does not see which of the writes is effective. But if its the same value anyway, it doesn't matter.

LLVM passes, however, cannot simplify this because the write is necessary for i != j (unless it would add a condition for one of the writes to occur only if i != j)

[etherzhhb]

test/ForwardOpTree/forward_load_double_write.ll

21–22

Maybe we could also add a reduced case from this, and put your comments to the reduced case?

[Meinersbur]

test/ForwardOpTree/forward_load_double_write.ll

21–22

Isn't forward_load_double_write.ll such a test case?

[Meinersbur]

test/ForwardOpTree/forward_load_double_write.ll

21–22

I added the motivation for onlySameValueWrites() into its comment.

[singam-sanjay]

Could you suggest a paper I could read to get to know this Zone Algorithm ?

[grosser]

I think this is not needed any more!

lib/CodeGen/PPCGCodeGeneration.cpp

static MustKillsInfo computeMustKillsInfo(const Scop &S) {
   //      1.2 scalars that are only used within the scop
   SmallVector<isl::id, 4> KillMemIds;
   for (ScopArrayInfo *SAI : S.arrays()) {
     if (SAI->isPHIKind() ||
         (SAI->isValueKind() && isScalarUsesContainedInScop(S, SAI)))
       KillMemIds.push_back(isl::manage(SAI->getBasePtrId().release()));
   }
 
-  Info.TaggedMustKills = isl::union_map::empty(isl::space(ParamSpace));
-  Info.MustKills = isl::union_map::empty(isl::space(ParamSpace));
+  Info.TaggedMustKills = isl::union_map::empty(ParamSpace);
+  Info.MustKills = isl::union_map::empty(ParamSpace);
 
   // Initialising KillsSchedule to `isl_set_empty` creates an empty node in the
   // schedule:
   //     - filter: "[control] -> { }"
   // So, we choose to not create this to keep the output a little nicer,
   // at the cost of some code complexity.
   Info.KillsSchedule = nullptr;
 
for (isl::id &ToKillId : KillMemIds) {
     // 2b. PhantomRefToScalar:
     //         [param] -> { ref_phantom[] -> scalar_to_kill[] }
     //
     // Combining these with `isl_map_domain_product` gives us
     // TaggedMustKill:
     //     [param] -> { [Stmt[] -> phantom_ref[]] -> scalar_to_kill[] }
 
     // 2a. [param] -> { Stmt[] -> scalar_to_kill[] }
-    isl::map StmtToScalar = isl::map::universe(isl::space(ParamSpace));
+    isl::map StmtToScalar = isl::map::universe(ParamSpace);
     StmtToScalar = StmtToScalar.set_tuple_id(isl::dim::in, isl::id(KillStmtId));
     StmtToScalar = StmtToScalar.set_tuple_id(isl::dim::out, isl::id(ToKillId));
 
     isl::id PhantomRefId = isl::id::alloc(
         S.getIslCtx(), std::string("ref_phantom") + ToKillId.get_name(),
         nullptr);
 
     // 2b. [param] -> { phantom_ref[] -> scalar_to_kill[] }
-    isl::map PhantomRefToScalar = isl::map::universe(isl::space(ParamSpace));
+    isl::map PhantomRefToScalar = isl::map::universe(ParamSpace);
     PhantomRefToScalar =
         PhantomRefToScalar.set_tuple_id(isl::dim::in, PhantomRefId);
     PhantomRefToScalar =
         PhantomRefToScalar.set_tuple_id(isl::dim::out, ToKillId);
 
     // 2. [param] -> { [Stmt[] -> phantom_ref[]] -> scalar_to_kill[] }
     isl::map TaggedMustKill = StmtToScalar.domain_product(PhantomRefToScalar);
     Info.TaggedMustKills = Info.TaggedMustKills.unite(TaggedMustKill);

lib/Transform/ZoneAlgo.cpp

ZoneAlgorithm::ZoneAlgorithm(const char *PassName, Scop *S, LoopInfo *LI)
   auto Domains = S->getDomains();
 
   Schedule =
       give(isl_union_map_intersect_domain(Schedule.take(), Domains.take()));
   ParamSpace = give(isl_union_map_get_space(Schedule.keep()));
   ScatterSpace = getScatterSpace(Schedule);
 }
 
+/// Check if all stores in @p Stmt store the very same value.
+static bool onlySameValueWrites(ScopStmt *Stmt) {
+  Value *V = nullptr;
+
+  for (auto *MA : *Stmt) {
+    if (!MA->isLatestArrayKind() || !MA->isMustWrite() ||
+        !MA->isOriginalArrayKind())
+      continue;
+
+    if (!V) {
+      V = MA->getAccessValue();
+      continue;
+    }
+
+    if (V != MA->getAccessValue())
+      return false;
+  }
+  return true;
+}
+
 bool ZoneAlgorithm::isCompatibleStmt(ScopStmt *Stmt) {
   auto Stores = makeEmptyUnionMap();
   auto Loads = makeEmptyUnionMap();
 
   // This assumes that the MemoryKind::Array MemoryAccesses are iterated in
   // order.
   for (auto *MA : *Stmt) {
     if (!MA->isLatestArrayKind())
if (Stmt->isRegionStmt() &&
       S->getFunction().getContext().diagnose(R);
       return false;
     }
 
     // Do not allow more than one store to the same location.
     if (!isl_union_map_is_disjoint(Stores.keep(), AccRel.keep())) {
       OptimizationRemarkMissed R(PassName, "StoreAfterStore",
                                  MA->getAccessInstruction());
+      if (!onlySameValueWrites(Stmt)) {
         R << "store after store of same element in same statement";
         R << " (previous stores: " << Stores;
         R << ", storing: " << AccRel << ")";
         S->getFunction().getContext().diagnose(R);
         return false;
       }
+    }
 
     Stores = give(isl_union_map_union(Stores.take(), AccRel.take()));
   }
 
   return true;
 }
 
 void ZoneAlgorithm::addArrayReadAccess(MemoryAccess *MA) {

test/ForwardOpTree/forward_load_double_write.ll

+; RUN: opt %loadPolly -polly-optree -analyze < %s | FileCheck %s -match-full-lines
+;
+; Rematerialize a load.
+;
+define void @func(i32 %n, double* noalias nonnull %A, double* noalias nonnull %B) {
+entry:
+  br label %for
+
+for:
+  %j = phi i32 [0, %entry], [%j.inc, %inc]
+  %j.cmp = icmp slt i32 %j, %n
+  br i1 %j.cmp, label %bodyA, label %exit
+
+    bodyA:
+      %B_idx = getelementptr inbounds double, double* %B, i32 %j
+      %val = load double, double* %B_idx
+      br label %bodyB
+
+    bodyB:
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      store double %val, double* %A_idx
+      store double %val, double* %A_idx
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK: Statistics {
+; CHECK:     Known loads forwarded: 1
+; CHECK:     Operand trees forwarded: 1
+; CHECK:     Statements with forwarded operand trees: 1
+; CHECK: }
+
+; CHECK:      Stmt_bodyB
+; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             null;
+; CHECK-NEXT:        new: [n] -> { Stmt_bodyB[i0] -> MemRef_B[i0] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_bodyB[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_bodyB[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:         Instructions {
+; CHECK-NEXT:               %val = load double, double* %B_idx
+; CHECK-NEXT:               store double %val, double* %A_idx
+; CHECK-NEXT:               store double %val, double* %A_idx
+; CHECK-NEXT:         }