[Polly][DeLICM] Partial writes for PHIs.

[Meinersbur]

Summary

Enable the use for partial writes for PHI write accesses with a switch. This simply skips the test for whether a PHI write would be partial.

The analog test for partial value writes also protects for partial reads which we do not support (yet). It is possible to test for partial reads separately such that we could skip the partial write check as well. In case this shows up to be useful, I can implement it as well.

[grosser]

This LGTM, in terms of implementation. So we can commit it to experiment with it. However, performance wise this seems to not work well. My gemm kernel regresses from 0.8 seconds in the optimal case (without pattern matching opts) to 4.4 seconds with partial writes.

polly/trunk/lib/Transform/DeLICM.cpp

DelicmMaxOps("polly-delicm-max-ops",
                  cl::init(1000000), cl::cat(PollyCategory));
 
 cl::opt<bool> DelicmOverapproximateWrites(
     "polly-delicm-overapproximate-writes",
     cl::desc(
         "Do more PHI writes than necessary in order to avoid partial accesses"),
     cl::init(false), cl::Hidden, cl::cat(PollyCategory));
 
+cl::opt<bool> DelicmPartialWrites("polly-delicm-partial-writes",
+                                  cl::desc("Allow partial writes"),
+                                  cl::init(false), cl::Hidden,
+                                  cl::cat(PollyCategory));
+
 cl::opt<bool>
     DelicmComputeKnown("polly-delicm-compute-known",
                        cl::desc("Compute known content of array elements"),
                        cl::init(true), cl::Hidden, cl::cat(PollyCategory));
 
 STATISTIC(DeLICMAnalyzed, "Number of successfully analyzed SCoPs");
 STATISTIC(DeLICMOutOfQuota,
           "Analyses aborted because max_operations was reached");
for (auto *MA : DefUse.getPHIIncomings(SAI))
       UniverseWritesDom = give(isl_union_set_add_set(UniverseWritesDom.take(),
                                                      getDomainFor(MA).take()));
 
     auto RelevantWritesTarget = WritesTarget;
     if (DelicmOverapproximateWrites)
       WritesTarget = expandMapping(WritesTarget, UniverseWritesDom);
 
     auto ExpandedWritesDom = give(isl_union_map_domain(WritesTarget.copy()));
-    if (!isl_union_set_is_subset(UniverseWritesDom.keep(),
+    if (!DelicmPartialWrites &&
+        !isl_union_set_is_subset(UniverseWritesDom.keep(),
                                  ExpandedWritesDom.keep())) {
       DEBUG(dbgs() << "    Reject because did not find PHI write mapping for "
                       "all instances\n");
       if (DelicmOverapproximateWrites)
         DEBUG(dbgs() << "      Relevant Mapping:    " << RelevantWritesTarget
                      << '\n');
       DEBUG(dbgs() << "      Deduced Mapping:     " << WritesTarget << '\n');
       DEBUG(dbgs() << "      Missing instances:    "

polly/trunk/test/DeLICM/reduction.ll

+; RUN: opt %loadPolly -polly-delicm-partial-writes=true -polly-delicm -analyze < %s | FileCheck -match-full-lines %s
+;
+;    void func(double *A) {
+;      for (int j = 0; j < 2; j += 1) { /* outer */
+;        double phi = 0.0;
+;        for (int i = 0; i < 4; i += 1) /* reduction */
+;          phi += 4.2;
+;        A[j] = phi;
+;      }
+;    }
+;
+define void @func(double* noalias nonnull %A) {
+entry:
+  br label %outer.for
+
+outer.for:
+  %j = phi i32 [0, %entry], [%j.inc, %outer.inc]
+  %j.cmp = icmp slt i32 %j, 2
+  br i1 %j.cmp, label %reduction.for, label %outer.exit
+
+
+    reduction.for:
+      %i = phi i32 [0, %outer.for], [%i.inc, %reduction.inc]
+      %phi = phi double [0.0, %outer.for], [%add, %reduction.inc]
+      %i.cmp = icmp slt i32 %i, 4
+      br i1 %i.cmp, label %body, label %reduction.exit
+
+
+
+        body:
+          %add = fadd double %phi, 4.2
+          br label %reduction.inc
+
+
+
+    reduction.inc:
+      %i.inc = add nuw nsw i32 %i, 1
+      br label %reduction.for
+
+    reduction.exit:
+      %A_idx = getelementptr inbounds double, double* %A, i32 %j
+      store double %phi, double* %A_idx
+      br label %outer.inc
+
+
+
+outer.inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %outer.for
+
+outer.exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; CHECK:      After accesses {
+; CHECK-NEXT:     Stmt_outer_for
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_outer_for[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_outer_for[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT:     Stmt_reduction_for
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 4 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 4 };
+; CHECK-NEXT:     Stmt_body
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_body[i0, i1] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_reduction_inc
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; CHECK-NEXT:     Stmt_reduction_exit
+; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_A[i0] };
+; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_phi[] };
+; CHECK-NEXT:            new: { Stmt_reduction_exit[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; CHECK-NEXT: }

polly/trunk/test/DeLICM/reduction_looprotate_gvnpre.ll

 ; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-overapproximate-writes=true -polly-delicm-compute-known=true -polly-delicm -analyze < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-partial-writes=true -polly-delicm-compute-known=true -polly-delicm -analyze < %s | FileCheck -check-prefix=PARTIAL %s
 ;
 ;    void func(double *A) {
 ;      for (int j = 0; j < 2; j += 1) { /* outer */
 ;        double phi = 0.0;
 ;        for (int i = 0; i < 4; i += 1) { /* reduction */
 ;          phi += 4.2;
 ;          A[j] = phi;
 ;        }

 ; CHECK-NEXT:     Stmt_reduction_inc
 ; CHECK-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
 ; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : i0 >= 0 and 0 <= i1 <= 3 and 3i1 <= 21 - 13i0; Stmt_reduction_inc[1, 3] -> MemRef_A[1] };
 ; CHECK-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
 ; CHECK-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
 ; CHECK-NEXT: }
+
+
+; PARTIAL:      After accesses {
+; PARTIAL-NEXT:     Stmt_reduction_preheader
+; PARTIAL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
+; PARTIAL-NEXT:            new: { Stmt_reduction_preheader[i0] -> MemRef_A[i0] : 0 <= i0 <= 1 };
+; PARTIAL-NEXT:     Stmt_reduction_for
+; PARTIAL-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; PARTIAL-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; PARTIAL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
+; PARTIAL-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 };
+; PARTIAL-NEXT:     Stmt_body
+; PARTIAL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_body[i0, i1] -> MemRef_add[] };
+; PARTIAL-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 3 and 3i1 <= 22 - 13i0 };
+; PARTIAL-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_body[i0, i1] -> MemRef_phi[] };
+; PARTIAL-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[i0] : i0 >= 0 and 0 <= i1 <= 3 and 3i1 <= 21 - 13i0; Stmt_body[1, 3] -> MemRef_A[1] };
+; PARTIAL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; PARTIAL-NEXT:                 { Stmt_body[i0, i1] -> MemRef_A[i0] };
+; PARTIAL-NEXT:     Stmt_reduction_inc
+; PARTIAL-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
+; PARTIAL-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : i0 >= 0 and 0 <= i1 <= 3 and 3i1 <= 21 - 13i0; Stmt_reduction_inc[1, 3] -> MemRef_A[1] };
+; PARTIAL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; PARTIAL-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[i0] : 0 <= i0 <= 1 and 0 <= i1 <= 2 and 3i1 >= -13i0 };
+; PARTIAL-NEXT: }

polly/trunk/test/DeLICM/reduction_overapproximate.ll

 ; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-compute-known=true -polly-delicm-overapproximate-writes=true -polly-delicm -analyze < %s | FileCheck %s --check-prefix=APPROX
 ; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-compute-known=true -polly-delicm-overapproximate-writes=false -polly-delicm -analyze < %s | FileCheck %s --check-prefix=EXACT
+; RUN: opt %loadPolly -polly-flatten-schedule -polly-delicm-compute-known=true -polly-delicm-partial-writes=true -polly-delicm -analyze < %s | FileCheck %s --check-prefix=PARTIAL
 ;
 ;    void func(double *A {
 ;      for (int j = -1; j < 3; j += 1) { /* outer */
 ;        double phi = 0.0;
 ;        if (0 < j)
 ;          for (int i = 0; i < j; i += 1) /* reduction */
 ;            phi += 4.2;
 ;        A[j] = phi;

 ; APPROX-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_val__phi[] };
 ; APPROX-NEXT:            new: { Stmt_reduction_exit[i0] -> MemRef_A[-1 + i0] : 0 <= i0 <= 3 };
 ; APPROX-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; APPROX-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_A[-1 + i0] };
 ; APPROX-NEXT: }
 
 
 ; EXACT: No modification has been made
+
+
+; PARTIAL:      After accesses {
+; PARTIAL-NEXT:     Stmt_reduction_checkloop
+; PARTIAL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_reduction_checkloop[i0] -> MemRef_val__phi[] };
+; PARTIAL-NEXT:            new: { Stmt_reduction_checkloop[i0] -> MemRef_A[-1 + i0] : 0 <= i0 <= 1 };
+; PARTIAL-NEXT:     Stmt_reduction_preheader
+; PARTIAL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_reduction_preheader[i0] -> MemRef_phi__phi[] };
+; PARTIAL-NEXT:            new: { Stmt_reduction_preheader[i0] -> MemRef_A[-1 + i0] : 2 <= i0 <= 3 };
+; PARTIAL-NEXT:     Stmt_reduction_for
+; PARTIAL-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi__phi[] };
+; PARTIAL-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and i1 >= 0 and 2 - 3i0 <= i1 <= 11 - 3i0 and i1 <= 2 and i1 <= -2 + i0 };
+; PARTIAL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_reduction_for[i0, i1] -> MemRef_phi[] };
+; PARTIAL-NEXT:            new: { Stmt_reduction_for[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and i1 >= 0 and 2 - 3i0 <= i1 <= 11 - 3i0 and i1 <= 2 and i1 <= -2 + i0 };
+; PARTIAL-NEXT:     Stmt_body
+; PARTIAL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_body[i0, i1] -> MemRef_add[] };
+; PARTIAL-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and i1 >= 0 and 2 - 3i0 <= i1 <= 10 - 3i0 and i1 <= 1 and i1 <= -2 + i0 };
+; PARTIAL-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_body[i0, i1] -> MemRef_phi[] };
+; PARTIAL-NEXT:            new: { Stmt_body[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and 0 <= i1 <= -2 + i0 };
+; PARTIAL-NEXT:     Stmt_reduction_inc
+; PARTIAL-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_add[] };
+; PARTIAL-NEXT:            new: { Stmt_reduction_inc[i0, i1] -> MemRef_A[-1 + i0] : i0 <= 3 and 0 <= i1 <= -2 + i0 };
+; PARTIAL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_phi__phi[] };
+; PARTIAL-NEXT:            new: { Stmt_reduction_inc[3, 0] -> MemRef_A[2] };
+; PARTIAL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_reduction_inc[i0, i1] -> MemRef_val__phi[] };
+; PARTIAL-NEXT:            new: { Stmt_reduction_inc[i0, -2 + i0] -> MemRef_A[-1 + i0] : 2 <= i0 <= 3 };
+; PARTIAL-NEXT:     Stmt_reduction_exit
+; PARTIAL-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; PARTIAL-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_val__phi[] };
+; PARTIAL-NEXT:            new: { Stmt_reduction_exit[i0] -> MemRef_A[-1 + i0] : 0 <= i0 <= 3 };
+; PARTIAL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; PARTIAL-NEXT:                 { Stmt_reduction_exit[i0] -> MemRef_A[-1 + i0] };
+; PARTIAL-NEXT: }