From 6dfe9bce94358dd603b1e5e1e38d9942b8c6b220 Mon Sep 17 00:00:00 2001 From: Michael Kruse Date: Sat, 22 Jul 2017 20:33:09 +0000 Subject: [PATCH] [Simplify] Remove partial write accesses with empty domain. If the access relation's domain is empty, the access will never be executed. We can just remove it. We only remove write accesses. Partial read accesses are not yet supported and instructions in the statement might require the llvm::Value holding the read's result to be defined. git-svn-id: https://llvm.org/svn/llvm-project/polly/trunk@308830 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transform/Simplify.cpp | 42 ++++++++++++++++++++-- test/Simplify/emptyaccessdomain.ll | 38 ++++++++++++++++++++ .../emptyaccessdomain___%for---%return.jscop | 24 +++++++++++++ ...accessdomain___%for---%return.jscop.transformed | 24 +++++++++++++ 4 files changed, 126 insertions(+), 2 deletions(-) create mode 100644 test/Simplify/emptyaccessdomain.ll create mode 100644 test/Simplify/emptyaccessdomain___%for---%return.jscop create mode 100644 test/Simplify/emptyaccessdomain___%for---%return.jscop.transformed diff --git a/lib/Transform/Simplify.cpp b/lib/Transform/Simplify.cpp index a97fcef9..008503bd 100644 --- a/lib/Transform/Simplify.cpp +++ b/lib/Transform/Simplify.cpp @@ -36,6 +36,8 @@ STATISTIC(InBetweenStore, "Number of Load-Store pairs NOT removed because " STATISTIC(TotalOverwritesRemoved, "Number of removed overwritten writes"); STATISTIC(TotalRedundantWritesRemoved, "Number of writes of same value removed in any SCoP"); +STATISTIC(TotalEmptyPartialAccessesRemoved, + "Number of empty partial accesses removed"); STATISTIC(TotalDeadAccessesRemoved, "Number of dead accesses removed"); STATISTIC(TotalDeadInstructionsRemoved, "Number of unused instructions removed"); @@ -97,6 +99,9 @@ private: /// Number of redundant writes removed from this SCoP. int RedundantWritesRemoved = 0; + /// Number of writes with empty access domain removed. + int EmptyPartialAccessesRemoved = 0; + /// Number of unused accesses removed from this SCoP. int DeadAccessesRemoved = 0; @@ -109,8 +114,8 @@ private: /// Return whether at least one simplification has been applied. bool isModified() const { return OverwritesRemoved > 0 || RedundantWritesRemoved > 0 || - DeadAccessesRemoved > 0 || DeadInstructionsRemoved > 0 || - StmtsRemoved > 0; + EmptyPartialAccessesRemoved > 0 || DeadAccessesRemoved > 0 || + DeadInstructionsRemoved > 0 || StmtsRemoved > 0; } MemoryAccess *getReadAccessForValue(ScopStmt *Stmt, llvm::Value *Val) { @@ -319,6 +324,33 @@ private: TotalStmtsRemoved += StmtsRemoved; } + /// Remove accesses that have an empty domain. + void removeEmptyPartialAccesses() { + for (ScopStmt &Stmt : *S) { + // Defer the actual removal to not invalidate iterators. + SmallVector DeferredRemove; + + for (MemoryAccess *MA : Stmt) { + if (!MA->isWrite()) + continue; + + isl::map AccRel = give(MA->getAccessRelation()); + if (!AccRel.is_empty().is_true()) + continue; + + DEBUG(dbgs() << "Removing " << MA + << " because it's a partial access that never occurs\n"); + DeferredRemove.push_back(MA); + } + + for (MemoryAccess *MA : DeferredRemove) { + Stmt.removeSingleMemoryAccess(MA); + EmptyPartialAccessesRemoved++; + TotalEmptyPartialAccessesRemoved++; + } + } + } + /// Mark all reachable instructions and access, and sweep those that are not /// reachable. void markAndSweep(LoopInfo *LI) { @@ -380,6 +412,8 @@ private: << '\n'; OS.indent(Indent + 4) << "Redundant writes removed: " << RedundantWritesRemoved << "\n"; + OS.indent(Indent + 4) << "Access with empty domains removed: " + << EmptyPartialAccessesRemoved << "\n"; OS.indent(Indent + 4) << "Dead accesses removed: " << DeadAccessesRemoved << '\n'; OS.indent(Indent + 4) << "Dead instructions removed: " @@ -424,6 +458,9 @@ public: DEBUG(dbgs() << "Removing redundant writes...\n"); removeRedundantWrites(); + DEBUG(dbgs() << "Removing partial writes that never happen...\n"); + removeEmptyPartialAccesses(); + DEBUG(dbgs() << "Cleanup unused accesses...\n"); LoopInfo *LI = &getAnalysis().getLoopInfo(); markAndSweep(LI); @@ -456,6 +493,7 @@ public: OverwritesRemoved = 0; RedundantWritesRemoved = 0; + EmptyPartialAccessesRemoved = 0; DeadAccessesRemoved = 0; DeadInstructionsRemoved = 0; StmtsRemoved = 0; diff --git a/test/Simplify/emptyaccessdomain.ll b/test/Simplify/emptyaccessdomain.ll new file mode 100644 index 00000000..641d34e9 --- /dev/null +++ b/test/Simplify/emptyaccessdomain.ll @@ -0,0 +1,38 @@ +; RUN: opt %loadPolly -polly-import-jscop -polly-import-jscop-postfix=transformed -polly-simplify -analyze < %s | FileCheck %s -match-full-lines +; +; for (int j = 0; j < n; j += 1) { +; A[0] = 42.0; +; } +; +define void @emptyaccessdomain(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: + store double 42.0, 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: Overwrites removed: 1 +; CHECK: Stmts removed: 1 +; CHECK: } + +; CHECK: After accesses { +; CHECK-NEXT: } diff --git a/test/Simplify/emptyaccessdomain___%for---%return.jscop b/test/Simplify/emptyaccessdomain___%for---%return.jscop new file mode 100644 index 00000000..a0472bc1 --- /dev/null +++ b/test/Simplify/emptyaccessdomain___%for---%return.jscop @@ -0,0 +1,24 @@ +{ + "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[0] }" + } + ], + "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }", + "name" : "Stmt_body", + "schedule" : "[n] -> { Stmt_body[i0] -> [i0] }" + } + ] +} diff --git a/test/Simplify/emptyaccessdomain___%for---%return.jscop.transformed b/test/Simplify/emptyaccessdomain___%for---%return.jscop.transformed new file mode 100644 index 00000000..e881f7e1 --- /dev/null +++ b/test/Simplify/emptyaccessdomain___%for---%return.jscop.transformed @@ -0,0 +1,24 @@ +{ + "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[0] : 1 = 0 }" + } + ], + "domain" : "[n] -> { Stmt_body[i0] : 0 <= i0 < n }", + "name" : "Stmt_body", + "schedule" : "[n] -> { Stmt_body[i0] -> [i0] }" + } + ] +} -- 2.11.4.GIT