[ForwardOpTree] Support read-only value uses.

Read-only values (values defined before the SCoP) require special
handing with -polly-analyze-read-only-scalars=true (which is the
default). If active, each use of a value requires a read access.
When a copied value uses a read-only value, we must also ensure that
such a MemoryAccess is available or is created.

Differential Revision: https://reviews.llvm.org/D35764

llvm-svn: 308876

6 files changed, 149 insertions, 7 deletions

diff --git a/polly/include/polly/ScopBuilder.h b/polly/include/polly/ScopBuilder.h
index 67a287ff3d7..0b6fa795bc2 100644
--- a/polly/include/polly/ScopBuilder.h
+++ b/polly/include/polly/ScopBuilder.h
@@ -21,6 +21,9 @@
 
 namespace polly {
 
+/// Command line switch whether to model read-only accesses.
+extern bool ModelReadOnlyScalars;
+
 /// Build the Polly IR (Scop and ScopStmt) on a Region.
 class ScopBuilder {
   //===-------------------------------------------------------------------===//
diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index e504444a4c5..8b56b668361 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -1628,6 +1628,18 @@ public:
   ///
   void printInstructions(raw_ostream &OS) const;
 
+  /// Check whether there is a value read access for @p V in this statement, and
+  /// if not, create one.
+  ///
+  /// This allows to add MemoryAccesses after the initial creation of the Scop
+  /// by ScopBuilder.
+  ///
+  /// @return The already existing or newly created MemoryKind::Value READ
+  /// MemoryAccess.
+  ///
+  /// @see ScopBuilder::ensureValueRead(Value*,ScopStmt*)
+  MemoryAccess *ensureValueRead(Value *V);
+
 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
   /// Print the ScopStmt to stderr.
   void dump() const;
diff --git a/polly/lib/Analysis/ScopBuilder.cpp b/polly/lib/Analysis/ScopBuilder.cpp
index f6b929ab73e..cf253bfa8cc 100644
--- a/polly/lib/Analysis/ScopBuilder.cpp
+++ b/polly/lib/Analysis/ScopBuilder.cpp
@@ -32,10 +32,12 @@ STATISTIC(RichScopFound, "Number of Scops containing a loop");
 STATISTIC(InfeasibleScops,
           "Number of SCoPs with statically infeasible context.");
 
-static cl::opt<bool> ModelReadOnlyScalars(
+bool polly::ModelReadOnlyScalars;
+static cl::opt<bool, true> XModelReadOnlyScalars(
     "polly-analyze-read-only-scalars",
     cl::desc("Model read-only scalar values in the scop description"),
-    cl::Hidden, cl::ZeroOrMore, cl::init(true), cl::cat(PollyCategory));
+    cl::location(ModelReadOnlyScalars), cl::Hidden, cl::ZeroOrMore,
+    cl::init(true), cl::cat(PollyCategory));
 
 static cl::opt<bool> UnprofitableScalarAccs(
     "polly-unprofitable-scalar-accs",
@@ -778,6 +780,15 @@ void ScopBuilder::ensureValueWrite(Instruction *Inst) {
 }
 
 void ScopBuilder::ensureValueRead(Value *V, ScopStmt *UserStmt) {
+  // TODO: Make ScopStmt::ensureValueRead(Value*) offer the same functionality
+  // to be able to replace this one. Currently, there is a split responsibility.
+  // In a first step, the MemoryAccess is created, but without the
+  // AccessRelation. In the second step by ScopStmt::buildAccessRelations(), the
+  // AccessRelation is created. At least for scalar accesses, there is no new
+  // information available at ScopStmt::buildAccessRelations(), so we could
+  // create the AccessRelation right away. This is what
+  // ScopStmt::ensureValueRead(Value*) does.
+
   auto *Scope = UserStmt->getSurroundingLoop();
   auto VUse = VirtualUse::create(scop.get(), UserStmt, Scope, V, false);
   switch (VUse.getKind()) {
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 6defb4f1bb9..c1a30b9bad4 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -2042,6 +2042,22 @@ void ScopStmt::removeSingleMemoryAccess(MemoryAccess *MA) {
   }
 }
 
+MemoryAccess *ScopStmt::ensureValueRead(Value *V) {
+  MemoryAccess *Access = lookupInputAccessOf(V);
+  if (Access)
+    return Access;
+
+  ScopArrayInfo *SAI =
+      Parent.getOrCreateScopArrayInfo(V, V->getType(), {}, MemoryKind::Value);
+  Access = new MemoryAccess(this, nullptr, MemoryAccess::READ, V, V->getType(),
+                            true, {}, {}, V, MemoryKind::Value);
+  Parent.addAccessFunction(Access);
+  Access->buildAccessRelation(SAI);
+  addAccess(Access);
+  Parent.addAccessData(Access);
+  return Access;
+}
+
 raw_ostream &polly::operator<<(raw_ostream &O, const ScopStmt &S) {
   S.print(O, PollyPrintInstructions);
   return O;
diff --git a/polly/lib/Transform/ForwardOpTree.cpp b/polly/lib/Transform/ForwardOpTree.cpp
index e0fd57814c7..fe5a6311af8 100644
--- a/polly/lib/Transform/ForwardOpTree.cpp
+++ b/polly/lib/Transform/ForwardOpTree.cpp
@@ -13,6 +13,7 @@
 
 #include "polly/ForwardOpTree.h"
 
+#include "polly/ScopBuilder.h"
 #include "polly/ScopInfo.h"
 #include "polly/ScopPass.h"
 #include "polly/Support/GICHelper.h"
@@ -25,6 +26,7 @@ using namespace polly;
 using namespace llvm;
 
 STATISTIC(TotalInstructionsCopied, "Number of copied instructions");
+STATISTIC(TotalReadOnlyCopied, "Number of copied read-only accesses");
 STATISTIC(TotalForwardedTrees, "Number of forwarded operand trees");
 STATISTIC(TotalModifiedStmts,
           "Number of statements with at least one forwarded tree");
@@ -37,6 +39,7 @@ namespace {
 enum ForwardingDecision {
   FD_CannotForward,
   FD_CanForward,
+  FD_CanForwardTree,
   FD_DidForward,
 };
 
@@ -58,6 +61,9 @@ private:
   /// How many instructions have been copied to other statements.
   int NumInstructionsCopied = 0;
 
+  /// How many read-only accesses have been copied.
+  int NumReadOnlyCopied = 0;
+
   /// How many operand trees have been forwarded.
   int NumForwardedTrees = 0;
 
@@ -71,6 +77,8 @@ private:
     OS.indent(Indent) << "Statistics {\n";
     OS.indent(Indent + 4) << "Instructions copied: " << NumInstructionsCopied
                           << '\n';
+    OS.indent(Indent + 4) << "Read-only accesses copied: " << NumReadOnlyCopied
+                          << '\n';
     OS.indent(Indent + 4) << "Operand trees forwarded: " << NumForwardedTrees
                           << '\n';
     OS.indent(Indent + 4) << "Statements with forwarded operand trees: "
@@ -132,9 +140,16 @@ private:
       return FD_CannotForward;
 
     case VirtualUse::ReadOnly:
-      // Not supported yet.
-      DEBUG(dbgs() << "    Cannot forward read-only val: " << *UseVal << "\n");
-      return FD_CannotForward;
+      if (!DoIt)
+        return FD_CanForward;
+
+      // If we model read-only scalars, we need to create a MemoryAccess for it.
+      if (ModelReadOnlyScalars)
+        TargetStmt->ensureValueRead(UseVal);
+
+      NumReadOnlyCopied++;
+      TotalReadOnlyCopied++;
+      return FD_DidForward;
 
     case VirtualUse::Intra:
     case VirtualUse::Inter:
@@ -183,6 +198,7 @@ private:
           return FD_CannotForward;
 
         case FD_CanForward:
+        case FD_CanForwardTree:
           assert(!DoIt);
           break;
 
@@ -194,7 +210,7 @@ private:
 
       if (DoIt)
         return FD_DidForward;
-      return FD_CanForward;
+      return FD_CanForwardTree;
     }
 
     llvm_unreachable("Case unhandled");
@@ -211,7 +227,7 @@ private:
     ForwardingDecision Assessment =
         canForwardTree(Stmt, RA->getAccessValue(), Stmt, InLoop, false);
     assert(Assessment != FD_DidForward);
-    if (Assessment == FD_CannotForward)
+    if (Assessment != FD_CanForwardTree)
       return false;
 
     ForwardingDecision Execution =
diff --git a/polly/test/ForwardOpTree/forward_readonly.ll b/polly/test/ForwardOpTree/forward_readonly.ll
new file mode 100644
index 00000000000..ca514cfc606
--- /dev/null
+++ b/polly/test/ForwardOpTree/forward_readonly.ll
@@ -0,0 +1,84 @@
+; RUN: opt %loadPolly -polly-analyze-read-only-scalars=true  -polly-optree -analyze < %s | FileCheck %s -match-full-lines -check-prefixes=STATS,MODEL
+; RUN: opt %loadPolly -polly-analyze-read-only-scalars=false -polly-optree -analyze < %s | FileCheck %s -match-full-lines -check-prefixes=STATS,NOMODEL
+;
+; Move %val to %bodyB, so %bodyA can be removed (by -polly-simplify)
+;
+; for (int j = 0; j < n; j += 1) {
+; bodyA:
+;   double val = arg + 21.0;
+;
+; bodyB:
+;   A[0] = val;
+; }
+;
+define void @func(i32 %n, double* noalias nonnull %A, double %arg) {
+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:
+      %val = fadd double %arg, 21.0
+      br label %bodyB
+
+    bodyB:
+      store double %val, double* %A
+      br label %inc
+
+inc:
+  %j.inc = add nuw nsw i32 %j, 1
+  br label %for
+
+exit:
+  br label %return
+
+return:
+  ret void
+}
+
+
+; STATS: Statistics {
+; STATS:     Instructions copied: 1
+; STATS:     Read-only accesses copied: 1
+; STATS:     Operand trees forwarded: 1
+; STATS:     Statements with forwarded operand trees: 1
+; STATS: }
+
+; MODEL:      After statements {
+; MODEL-NEXT:     Stmt_bodyA
+; MODEL-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; MODEL-NEXT:                 [n] -> { Stmt_bodyA[i0] -> MemRef_arg[] };
+; MODEL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; MODEL-NEXT:                 [n] -> { Stmt_bodyA[i0] -> MemRef_val[] };
+; MODEL-NEXT:             Instructions {
+; MODEL-NEXT:                   %val = fadd double %arg, 2.100000e+01
+; MODEL-NEXT:                 }
+; MODEL-NEXT:     Stmt_bodyB
+; MODEL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; MODEL-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_A[0] };
+; MODEL-NEXT:             ReadAccess :=       [Reduction Type: NONE] [Scalar: 1]
+; MODEL-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_arg[] };
+; MODEL-NEXT:             Instructions {
+; MODEL-NEXT:                   %val = fadd double %arg, 2.100000e+01
+; MODEL-NEXT:                   store double %val, double* %A
+; MODEL-NEXT:                 }
+; MODEL-NEXT: }
+
+; NOMODEL:      After statements {
+; NOMODEL-NEXT:     Stmt_bodyA
+; NOMODEL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
+; NOMODEL-NEXT:                 [n] -> { Stmt_bodyA[i0] -> MemRef_val[] };
+; NOMODEL-NEXT:             Instructions {
+; NOMODEL-NEXT:                   %val = fadd double %arg, 2.100000e+01
+; NOMODEL-NEXT:                 }
+; NOMODEL-NEXT:     Stmt_bodyB
+; NOMODEL-NEXT:             MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; NOMODEL-NEXT:                 [n] -> { Stmt_bodyB[i0] -> MemRef_A[0] };
+; NOMODEL-NEXT:             Instructions {
+; NOMODEL-NEXT:                   %val = fadd double %arg, 2.100000e+01
+; NOMODEL-NEXT:                   store double %val, double* %A
+; NOMODEL-NEXT:                 }
+; NOMODEL-NEXT: }