Index: polly/trunk/lib/Transform/DeLICM.cpp =================================================================== --- polly/trunk/lib/Transform/DeLICM.cpp +++ polly/trunk/lib/Transform/DeLICM.cpp @@ -180,6 +180,11 @@ "Do more PHI writes than necessary in order to avoid partial accesses"), cl::init(false), cl::Hidden, cl::cat(PollyCategory)); +cl::opt DelicmPartialWrites("polly-delicm-partial-writes", + cl::desc("Allow partial writes"), + cl::init(false), cl::Hidden, + cl::cat(PollyCategory)); + cl::opt DelicmComputeKnown("polly-delicm-compute-known", cl::desc("Compute known content of array elements"), @@ -1793,7 +1798,8 @@ 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"); Index: polly/trunk/test/DeLICM/reduction.ll =================================================================== --- polly/trunk/test/DeLICM/reduction.ll +++ polly/trunk/test/DeLICM/reduction.ll @@ -0,0 +1,91 @@ +; 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: } Index: polly/trunk/test/DeLICM/reduction_looprotate_gvnpre.ll =================================================================== --- polly/trunk/test/DeLICM/reduction_looprotate_gvnpre.ll +++ polly/trunk/test/DeLICM/reduction_looprotate_gvnpre.ll @@ -1,4 +1,5 @@ ; 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 */ @@ -92,3 +93,34 @@ ; 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: } Index: polly/trunk/test/DeLICM/reduction_overapproximate.ll =================================================================== --- polly/trunk/test/DeLICM/reduction_overapproximate.ll +++ polly/trunk/test/DeLICM/reduction_overapproximate.ll @@ -1,5 +1,6 @@ ; 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 */ @@ -113,3 +114,45 @@ ; 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: }