summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/lib/Transform/Simplify.cpp108
-rw-r--r--polly/test/Simplify/identical.ll56
-rw-r--r--polly/test/Simplify/identical_3phi.ll61
-rw-r--r--polly/test/Simplify/identical_3phi___%for---%return.jscop55
-rw-r--r--polly/test/Simplify/identical_3phi___%for---%return.jscop.transformed55
-rw-r--r--polly/test/Simplify/identical___%for---%return.jscop47
-rw-r--r--polly/test/Simplify/identical___%for---%return.jscop.transformed47
7 files changed, 428 insertions, 1 deletions
diff --git a/polly/lib/Transform/Simplify.cpp b/polly/lib/Transform/Simplify.cpp
index 11d7b2f8dae..7a9df5cc4ca 100644
--- a/polly/lib/Transform/Simplify.cpp
+++ b/polly/lib/Transform/Simplify.cpp
@@ -31,15 +31,46 @@ STATISTIC(PairUnequalAccRels, "Number of Load-Store pairs NOT removed because "
"of different access relations");
STATISTIC(InBetweenStore, "Number of Load-Store pairs NOT removed because "
"there is another store between them");
+STATISTIC(TotalIdenticalWritesRemoved,
+ "Number of double writes removed in any SCoP");
STATISTIC(TotalRedundantWritesRemoved,
"Number of writes of same value removed in any SCoP");
STATISTIC(TotalStmtsRemoved, "Number of statements removed in any SCoP");
+/// Find the llvm::Value that is written by a MemoryAccess. Return nullptr if
+/// there is no such unique value.
+static Value *getWrittenScalar(MemoryAccess *WA) {
+ assert(WA->isWrite());
+
+ if (WA->isOriginalAnyPHIKind()) {
+ Value *Result = nullptr;
+ for (auto Incoming : WA->getIncoming()) {
+ assert(Incoming.second);
+
+ if (!Result) {
+ Result = Incoming.second;
+ continue;
+ }
+
+ if (Result == Incoming.second)
+ continue;
+
+ return nullptr;
+ }
+ return Result;
+ }
+
+ return WA->getAccessInstruction();
+}
+
class Simplify : public ScopPass {
private:
/// The last/current SCoP that is/has been processed.
Scop *S;
+ /// Number of double writes removed from this SCoP.
+ int IdenticalWritesRemoved = 0;
+
/// Number of redundant writes removed from this SCoP.
int RedundantWritesRemoved = 0;
@@ -48,7 +79,8 @@ private:
/// Return whether at least one simplification has been applied.
bool isModified() const {
- return RedundantWritesRemoved > 0 || StmtsRemoved > 0;
+ return IdenticalWritesRemoved > 0 || RedundantWritesRemoved > 0 ||
+ StmtsRemoved > 0;
}
MemoryAccess *getReadAccessForValue(ScopStmt *Stmt, llvm::Value *Val) {
@@ -122,6 +154,75 @@ private:
return nullptr;
}
+ /// If there are two writes in the same statement that write the same value to
+ /// the same location, remove one of them.
+ ///
+ /// This currently handles only implicit writes (writes which logically occur
+ /// at the end of a statement when all StoreInst and LoadInst have been
+ /// executed), to avoid interference with other memory accesses.
+ ///
+ /// Two implicit writes have no defined order. It can be produced by DeLICM
+ /// when it determined that both write the same value.
+ void removeIdenticalWrites() {
+ for (auto &Stmt : *S) {
+ // Delay actual removal to not invalidate iterators.
+ SmallPtrSet<MemoryAccess *, 4> StoresToRemove;
+
+ auto Domain = give(Stmt.getDomain());
+
+ // TODO: This has quadratic runtime. Accesses could be grouped by
+ // getAccessValue() to avoid.
+ for (auto *WA1 : Stmt) {
+ if (!WA1->isMustWrite())
+ continue;
+ if (!WA1->isOriginalScalarKind())
+ continue;
+ if (StoresToRemove.count(WA1))
+ continue;
+
+ auto *WrittenScalar1 = getWrittenScalar(WA1);
+ if (!WrittenScalar1)
+ continue;
+
+ for (auto *WA2 : Stmt) {
+ if (WA1 == WA2)
+ continue;
+ if (!WA2->isMustWrite())
+ continue;
+ if (!WA2->isOriginalScalarKind())
+ continue;
+ if (StoresToRemove.count(WA2))
+ continue;
+
+ auto *WrittenScalar2 = getWrittenScalar(WA2);
+ if (WrittenScalar1 != WrittenScalar2)
+ continue;
+
+ auto AccRel1 = give(isl_map_intersect_domain(WA1->getAccessRelation(),
+ Domain.copy()));
+ auto AccRel2 = give(isl_map_intersect_domain(WA2->getAccessRelation(),
+ Domain.copy()));
+ if (isl_map_is_equal(AccRel1.keep(), AccRel2.keep()) != isl_bool_true)
+ continue;
+
+ DEBUG(dbgs() << "Remove identical writes:\n");
+ DEBUG(dbgs() << " First write (kept) : " << WA1 << '\n');
+ DEBUG(dbgs() << " Second write (removed): " << WA2 << '\n');
+ StoresToRemove.insert(WA2);
+ }
+ }
+
+ for (auto *WA : StoresToRemove) {
+ auto *Stmt = WA->getStatement();
+
+ Stmt->removeSingleMemoryAccess(WA);
+
+ IdenticalWritesRemoved++;
+ TotalIdenticalWritesRemoved++;
+ }
+ }
+ }
+
/// Remove writes that just write the same value already stored in the
/// element.
void removeRedundantWrites() {
@@ -211,6 +312,8 @@ private:
/// Print simplification statistics to @p OS.
void printStatistics(llvm::raw_ostream &OS, int Indent = 0) const {
OS.indent(Indent) << "Statistics {\n";
+ OS.indent(Indent + 4) << "Identical writes removed: "
+ << IdenticalWritesRemoved << '\n';
OS.indent(Indent + 4) << "Redundant writes removed: "
<< RedundantWritesRemoved << "\n";
OS.indent(Indent + 4) << "Stmts removed: " << StmtsRemoved << "\n";
@@ -245,6 +348,9 @@ public:
this->S = &S;
ScopsProcessed++;
+ DEBUG(dbgs() << "Removing identical writes...\n");
+ removeIdenticalWrites();
+
DEBUG(dbgs() << "Removing redundant writes...\n");
removeRedundantWrites();
diff --git a/polly/test/Simplify/identical.ll b/polly/test/Simplify/identical.ll
new file mode 100644
index 00000000000..df4a4cdf9bf
--- /dev/null
+++ b/polly/test/Simplify/identical.ll
@@ -0,0 +1,56 @@
+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed -polly-simplify -analyze < %s | FileCheck -match-full-lines %s
+;
+; Remove identical writes
+; (two stores in the same statement that write the same value to the same
+; destination)
+;
+; for (int j = 0; j < n; j += 1) {
+; body:
+; val = 21.0 + 21.0;
+; A[1] = val;
+; A[1] = val;
+;
+; user:
+; A[0] = A[1];
+; }
+;
+define void @identical(i32 %n, double* noalias nonnull %A) {
+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 %body, label %exit
+
+ body:
+ %val = fadd double 21.0, 21.0
+ br label %user
+
+ user:
+ %phi = phi double [%val, %body]
+ %add = fadd double %val, %phi
+ store double %add, double* %A
+ 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: Identical writes removed: 1
+; CHECK: }
+
+; CHECK: Stmt_body
+; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT: [n] -> { Stmt_body[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT: new: [n] -> { Stmt_body[i0] -> MemRef_A[1] };
+; CHECK-NEXT: Stmt_user
diff --git a/polly/test/Simplify/identical_3phi.ll b/polly/test/Simplify/identical_3phi.ll
new file mode 100644
index 00000000000..3a7a61dee8d
--- /dev/null
+++ b/polly/test/Simplify/identical_3phi.ll
@@ -0,0 +1,61 @@
+; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-dir=%S -polly-import-jscop-postfix=transformed -polly-simplify -analyze < %s | FileCheck -match-full-lines %s
+;
+; Remove identical writes
+; (two stores in the same statement that write the same value to the same
+; destination)
+;
+; for (int j = 0; j < n; j += 1) {
+; body:
+; val = 21.0 + 21.0;
+; A[1] = val;
+; A[1] = val;
+; A[1] = val;
+;
+; user:
+; A[0] = A[1];
+; }
+;
+define void @identical_3phi(i32 %n, double* noalias nonnull %A) {
+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 %body, label %exit
+
+ body:
+ %val = fadd double 21.0, 21.0
+ br label %user
+
+ user:
+ %phi1 = phi double [%val, %body]
+ %phi2 = phi double [%val, %body]
+ %phi3 = phi double [%val, %body]
+ %add1 = fadd double %phi1, %phi2
+ %add2 = fadd double %add1, %phi3
+ store double %add2, double* %A
+ 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: Identical writes removed: 2
+; CHECK: }
+
+; CHECK: Stmt_body
+; CHECK-NEXT: MustWriteAccess := [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT: [n] -> { Stmt_body[i0] -> MemRef_phi1__phi[] };
+; CHECK-NEXT: new: [n] -> { Stmt_body[i0] -> MemRef_A[1] };
+; CHECK-NEXT: Stmt_user
diff --git a/polly/test/Simplify/identical_3phi___%for---%return.jscop b/polly/test/Simplify/identical_3phi___%for---%return.jscop
new file mode 100644
index 00000000000..af26b0ad698
--- /dev/null
+++ b/polly/test/Simplify/identical_3phi___%for---%return.jscop
@@ -0,0 +1,55 @@
+{
+ "arrays" : [
+ {
+ "name" : "MemRef_A",
+ "sizes" : [ "*" ],
+ "type" : "double"
+ }
+ ],
+ "context" : "[n] -> { : -2147483648 <= n <= 2147483647 }",
+ "name" : "%for---%return",
+ "statements" : [
+ {
+ "accesses" : [
+ {
+ "kind" : "write",
+ "relation" : "[n] -> { Stmt_body[i0] -> MemRef_phi1__phi[] }"
+ },
+ {
+ "kind" : "write",
+ "relation" : "[n] -> { Stmt_body[i0] -> MemRef_phi2__phi[] }"
+ },
+ {
+ "kind" : "write",
+ "relation" : "[n] -> { Stmt_body[i0] -> MemRef_phi3__phi[] }"
+ }
+ ],
+ "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+ "name" : "Stmt_body",
+ "schedule" : "[n] -> { Stmt_body[i0] -> [i0, 0] }"
+ },
+ {
+ "accesses" : [
+ {
+ "kind" : "read",
+ "relation" : "[n] -> { Stmt_user[i0] -> MemRef_phi1__phi[] }"
+ },
+ {
+ "kind" : "read",
+ "relation" : "[n] -> { Stmt_user[i0] -> MemRef_phi2__phi[] }"
+ },
+ {
+ "kind" : "read",
+ "relation" : "[n] -> { Stmt_user[i0] -> MemRef_phi3__phi[] }"
+ },
+ {
+ "kind" : "write",
+ "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[0] }"
+ }
+ ],
+ "domain" : "[n] -> { Stmt_user[i0] : 0 <= i0 < n }",
+ "name" : "Stmt_user",
+ "schedule" : "[n] -> { Stmt_user[i0] -> [i0, 1] }"
+ }
+ ]
+}
diff --git a/polly/test/Simplify/identical_3phi___%for---%return.jscop.transformed b/polly/test/Simplify/identical_3phi___%for---%return.jscop.transformed
new file mode 100644
index 00000000000..ddd927958a1
--- /dev/null
+++ b/polly/test/Simplify/identical_3phi___%for---%return.jscop.transformed
@@ -0,0 +1,55 @@
+{
+ "arrays" : [
+ {
+ "name" : "MemRef_A",
+ "sizes" : [ "*" ],
+ "type" : "double"
+ }
+ ],
+ "context" : "[n] -> { : -2147483648 <= n <= 2147483647 }",
+ "name" : "%for---%return",
+ "statements" : [
+ {
+ "accesses" : [
+ {
+ "kind" : "write",
+ "relation" : "[n] -> { Stmt_body[i0] -> MemRef_A[1] }"
+ },
+ {
+ "kind" : "write",
+ "relation" : "[n] -> { Stmt_body[i0] -> MemRef_A[1] }"
+ },
+ {
+ "kind" : "write",
+ "relation" : "[n] -> { Stmt_body[i0] -> MemRef_A[1] }"
+ }
+ ],
+ "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+ "name" : "Stmt_body",
+ "schedule" : "[n] -> { Stmt_body[i0] -> [i0, 0] }"
+ },
+ {
+ "accesses" : [
+ {
+ "kind" : "read",
+ "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[1] }"
+ },
+ {
+ "kind" : "read",
+ "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[1] }"
+ },
+ {
+ "kind" : "read",
+ "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[1] }"
+ },
+ {
+ "kind" : "write",
+ "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[0] }"
+ }
+ ],
+ "domain" : "[n] -> { Stmt_user[i0] : 0 <= i0 < n }",
+ "name" : "Stmt_user",
+ "schedule" : "[n] -> { Stmt_user[i0] -> [i0, 1] }"
+ }
+ ]
+}
diff --git a/polly/test/Simplify/identical___%for---%return.jscop b/polly/test/Simplify/identical___%for---%return.jscop
new file mode 100644
index 00000000000..248afa83478
--- /dev/null
+++ b/polly/test/Simplify/identical___%for---%return.jscop
@@ -0,0 +1,47 @@
+{
+ "arrays" : [
+ {
+ "name" : "MemRef_A",
+ "sizes" : [ "*" ],
+ "type" : "double"
+ }
+ ],
+ "context" : "[n] -> { : -2147483648 <= n <= 2147483647 }",
+ "name" : "%for---%return",
+ "statements" : [
+ {
+ "accesses" : [
+ {
+ "kind" : "write",
+ "relation" : "[n] -> { Stmt_body[i0] -> MemRef_phi__phi[] }"
+ },
+ {
+ "kind" : "write",
+ "relation" : "[n] -> { Stmt_body[i0] -> MemRef_val[] }"
+ }
+ ],
+ "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+ "name" : "Stmt_body",
+ "schedule" : "[n] -> { Stmt_body[i0] -> [i0, 0] }"
+ },
+ {
+ "accesses" : [
+ {
+ "kind" : "read",
+ "relation" : "[n] -> { Stmt_user[i0] -> MemRef_phi__phi[] }"
+ },
+ {
+ "kind" : "read",
+ "relation" : "[n] -> { Stmt_user[i0] -> MemRef_val[] }"
+ },
+ {
+ "kind" : "write",
+ "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[0] }"
+ }
+ ],
+ "domain" : "[n] -> { Stmt_user[i0] : 0 <= i0 < n }",
+ "name" : "Stmt_user",
+ "schedule" : "[n] -> { Stmt_user[i0] -> [i0, 1] }"
+ }
+ ]
+}
diff --git a/polly/test/Simplify/identical___%for---%return.jscop.transformed b/polly/test/Simplify/identical___%for---%return.jscop.transformed
new file mode 100644
index 00000000000..25beb614584
--- /dev/null
+++ b/polly/test/Simplify/identical___%for---%return.jscop.transformed
@@ -0,0 +1,47 @@
+{
+ "arrays" : [
+ {
+ "name" : "MemRef_A",
+ "sizes" : [ "*" ],
+ "type" : "double"
+ }
+ ],
+ "context" : "[n] -> { : -2147483648 <= n <= 2147483647 }",
+ "name" : "%for---%return",
+ "statements" : [
+ {
+ "accesses" : [
+ {
+ "kind" : "write",
+ "relation" : "[n] -> { Stmt_body[i0] -> MemRef_A[1] }"
+ },
+ {
+ "kind" : "write",
+ "relation" : "[n] -> { Stmt_body[i0] -> MemRef_A[1] }"
+ }
+ ],
+ "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }",
+ "name" : "Stmt_body",
+ "schedule" : "[n] -> { Stmt_body[i0] -> [i0, 0] }"
+ },
+ {
+ "accesses" : [
+ {
+ "kind" : "read",
+ "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[1] }"
+ },
+ {
+ "kind" : "read",
+ "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[1] }"
+ },
+ {
+ "kind" : "write",
+ "relation" : "[n] -> { Stmt_user[i0] -> MemRef_A[0] }"
+ }
+ ],
+ "domain" : "[n] -> { Stmt_user[i0] : 0 <= i0 < n }",
+ "name" : "Stmt_user",
+ "schedule" : "[n] -> { Stmt_user[i0] -> [i0, 1] }"
+ }
+ ]
+}
OpenPOWER on IntegriCloud