Unique value write accesses

Ensure there is at most one write access per definition of an
llvm::Value. Keep track of already created value write access by using
a (dense) map.

Replace addValueWriteAccess by ensureValueStore which can be uses more
liberally without worrying to add redundant accesses. It will be used,
e.g. in a logical correspondant for value reads -- ensureValueReload --
to ensure that the expected definition has been written when loading it.

Differential Revision: http://reviews.llvm.org/D15483

llvm-svn: 258807

4 files changed, 35 insertions, 14 deletions

diff --git a/polly/include/polly/ScopInfo.h b/polly/include/polly/ScopInfo.h
index 16d4d7e7fc0..ae99631bbb5 100644
--- a/polly/include/polly/ScopInfo.h
+++ b/polly/include/polly/ScopInfo.h
@@ -830,6 +830,10 @@ private:
   /// @brief Mapping from instructions to (scalar) memory accesses.
   DenseMap<const Instruction *, MemoryAccessList> InstructionToAccess;
 
+  /// @brief The set of values defined in this ScopStmt that are required
+  ///        elsewhere, mapped to their MK_Value WRITE MemoryAccesses.
+  DenseMap<Instruction *, MemoryAccess *> ValueWrites;
+
   //@}
 
   /// @brief A SCoP statement represents either a basic block (affine/precise
@@ -993,6 +997,15 @@ public:
     return *ArrayAccess;
   }
 
+  /// @brief Return the MemoryAccess that writes the value of an instruction
+  ///        defined in this statement, or nullptr if not existing, respectively
+  ///        not yet added.
+  MemoryAccess *lookupValueWriteOf(Instruction *Inst) const {
+    assert((isRegionStmt() && R->contains(Inst)) ||
+           (!isRegionStmt() && Inst->getParent() == BB));
+    return ValueWrites.lookup(Inst);
+  }
+
   void setBasicBlock(BasicBlock *Block) {
     // TODO: Handle the case where the statement is a region statement, thus
     //       the entry block was split and needs to be changed in the region R.
@@ -1917,7 +1930,7 @@ class ScopInfo : public RegionPass {
   /// @param Value The value to be written.
   /// @see addValueReadAccess()
   /// @see ScopArrayInfo::MemoryKind
-  void addValueWriteAccess(Instruction *Value);
+  void ensureValueWrite(Instruction *Value);
 
   /// @brief Create a MemoryAccess for reloading an llvm::Value.
   ///
@@ -1925,7 +1938,7 @@ class ScopInfo : public RegionPass {
   ///
   /// @param Value The scalar expected to be loaded.
   /// @param User  User of the scalar; this is where the access is added.
-  /// @see addValueWriteAccess()
+  /// @see ensureValueWrite()
   /// @see ScopArrayInfo::MemoryKind
   void addValueReadAccess(Value *Value, Instruction *User);
 
@@ -1939,7 +1952,7 @@ class ScopInfo : public RegionPass {
   /// @param User   The PHI node referencing @p Value.
   /// @param UserBB Incoming block for the incoming @p Value.
   /// @see addPHIWriteAccess()
-  /// @see addValueWriteAccess()
+  /// @see ensureValueWrite()
   /// @see ScopArrayInfo::MemoryKind
   void addValueReadAccess(Value *Value, PHINode *User, BasicBlock *UserBB);
 
diff --git a/polly/lib/Analysis/ScopInfo.cpp b/polly/lib/Analysis/ScopInfo.cpp
index 00055a055a1..4be92227c97 100644
--- a/polly/lib/Analysis/ScopInfo.cpp
+++ b/polly/lib/Analysis/ScopInfo.cpp
@@ -905,6 +905,12 @@ void ScopStmt::addAccess(MemoryAccess *Access) {
   if (Access->isArrayKind()) {
     MemoryAccessList &MAL = InstructionToAccess[AccessInst];
     MAL.emplace_front(Access);
+  } else if (Access->isValueKind() && Access->isWrite()) {
+    Instruction *AccessVal = cast<Instruction>(Access->getAccessValue());
+    assert(Parent.getStmtForBasicBlock(AccessVal->getParent()) == this);
+    assert(!ValueWrites.lookup(AccessVal));
+
+    ValueWrites[AccessVal] = Access;
   }
 
   MemAccs.push_back(Access);
@@ -3554,7 +3560,7 @@ void ScopInfo::buildPHIAccesses(PHINode *PHI, Region &R,
       if (scop->getStmtForBasicBlock(OpIBB) !=
           scop->getStmtForBasicBlock(OpBB)) {
         addValueReadAccess(OpI, PHI, OpBB);
-        addValueWriteAccess(OpI);
+        ensureValueWrite(OpI);
       }
     } else if (ModelReadOnlyScalars && !isa<Constant>(Op)) {
       addValueReadAccess(Op, PHI, OpBB);
@@ -3873,7 +3879,7 @@ void ScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
 
     if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
       if (!isa<StoreInst>(Inst))
-        addValueWriteAccess(Inst);
+        ensureValueWrite(Inst);
     }
   }
 }
@@ -3931,7 +3937,17 @@ void ScopInfo::addArrayAccess(Instruction *MemAccInst,
                   ElemBytes, IsAffine, AccessValue, Subscripts, Sizes,
                   ScopArrayInfo::MK_Array);
 }
-void ScopInfo::addValueWriteAccess(Instruction *Value) {
+void ScopInfo::ensureValueWrite(Instruction *Value) {
+  ScopStmt *Stmt = scop->getStmtForBasicBlock(Value->getParent());
+
+  // Value not defined within this SCoP.
+  if (!Stmt)
+    return;
+
+  // Do not process further if the value is already written.
+  if (Stmt->lookupValueWriteOf(Value))
+    return;
+
   addMemoryAccess(Value->getParent(), Value, MemoryAccess::MUST_WRITE, Value, 1,
                   true, Value, ArrayRef<const SCEV *>(),
                   ArrayRef<const SCEV *>(), ScopArrayInfo::MK_Value);
diff --git a/polly/test/ScopInfo/phi_scalar_simple_1.ll b/polly/test/ScopInfo/phi_scalar_simple_1.ll
index 0d13a218c42..170421b48ea 100644
--- a/polly/test/ScopInfo/phi_scalar_simple_1.ll
+++ b/polly/test/ScopInfo/phi_scalar_simple_1.ll
@@ -24,8 +24,6 @@
 ; CHECK-NEXT:             [N] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0__phi[] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             [N] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] };
-; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             [N] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] };
 ; CHECK-NEXT:     Stmt_for_body
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             [N] -> { Stmt_for_body[i0] : N >= 2 and 0 <= i0 <= -2 + N };
diff --git a/polly/test/ScopInfo/phi_scalar_simple_2.ll b/polly/test/ScopInfo/phi_scalar_simple_2.ll
index e4445df5294..89eaa2cfb69 100644
--- a/polly/test/ScopInfo/phi_scalar_simple_2.ll
+++ b/polly/test/ScopInfo/phi_scalar_simple_2.ll
@@ -20,8 +20,6 @@
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_cond[i0] -> MemRef_A[i0] };
-; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             [N, c] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0[] };
 ; CHECK-NEXT:     Stmt_for_body
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_body[i0] : 0 <= i0 < N };
@@ -40,10 +38,6 @@
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1__phi[] };
-; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] };
-; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             [N, c] -> { Stmt_for_cond1[i0, i1] -> MemRef_x_addr_1[] };
 ; CHECK-NEXT:     Stmt_for_body3
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_body3[i0, i1] : 0 <= i0 < N and 0 <= i1 < N };