[Polly] Unique value write accesses

[Meinersbur]

Summary

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.

This is was originally part of D13762.

[Meinersbur]

Rebase to D13676

[grosser]

Hi Michael,

again a small self-contained patch with minimal test-case noise. Nice!

From my side this patch looks good. Not only does it remove the redundant loads, but it also adds a mapping that will allow us to retrieve the scalar value writes of a scop statement, in case this functionality is needed later. This addresses Johannes concerns of us loosing parts of the Instruction->MemAccess mapping for value writes (and assuming we add such maps for other scalar accesses also in general).

Let's discuss this at the phone call tonight, but from my side this is commit ready.

include/polly/ScopInfo.h

995 ↗

(On Diff #42752)

... or not existing.

lib/Analysis/ScopInfo.cpp

3948 ↗

(On Diff #42752)

Unrelated. Please commit ahead of time.

[grosser]

One more comment:

lib/Analysis/ScopInfo.cpp

3933 ↗

(On Diff #42752)

I would prefer the name 'ensureValueWrite' as this corresponds better with the WRITE/READ naming scheme used in the surrounding code.

[grosser]

Accepted if my comments are addressed.

[Meinersbur]

Addressed Tobias' comments

polly/trunk/include/polly/ScopInfo.h

private:
   ///
   /// The only side effects of a statement are its memory accesses.
   typedef SmallVector<MemoryAccess *, 8> MemoryAccessVec;
   MemoryAccessVec MemAccs;
 
   /// @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
   ///        case) or a whole region (non-affine case). Only one of the
   ///        following two members will therefore be set and indicate which
   ///        kind of statement this is.
   ///
   ///{
public:
   /// @returns The unique array memory access related to Inst.
   MemoryAccess &getArrayAccessFor(const Instruction *Inst) const {
     MemoryAccess *ArrayAccess = getArrayAccessOrNULLFor(Inst);
 
     assert(ArrayAccess && "No array access found for instruction!");
     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.
     assert(BB && "Cannot set a block for a region statement");
     BB = Block;
   }
 
   /// @brief Add @p Access to this statement's list of accesses.
class ScopInfo : public RegionPass {
 
   /// @brief Create a MemoryAccess for writing an llvm::Value.
   ///
   /// The access will be created at the @p Value's definition.
   ///
   /// @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.
   ///
   /// Use this overload only for non-PHI instructions.
   ///
   /// @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);
 
   /// @brief Create a MemoryAccess for reloading an llvm::Value.
   ///
   /// This is for PHINodes using the scalar. As we model it, the used value must
   /// be available at the incoming block instead of when hitting the
   /// instruction.
   ///
   /// @param Value  The scalar expected to be loaded.
   /// @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);
 
   /// @brief Create a write MemoryAccess for the incoming block of a phi node.
   ///
   /// Each of the incoming blocks write their incoming value to be picked in the
   /// phi's block.
   ///

polly/trunk/lib/Analysis/ScopInfo.cpp

 }
 
 void ScopStmt::addAccess(MemoryAccess *Access) {
   Instruction *AccessInst = Access->getAccessInstruction();
 
   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);
 }
 
 void ScopStmt::realignParams() {
   for (MemoryAccess *MA : *this)
     MA->realignParams();
for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
     if (OpI) {
       BasicBlock *OpIBB = OpI->getParent();
       // As we pretend there is a use (or more precise a write) of OpI in OpBB
       // we have to insert a scalar dependence from the definition of OpI to
       // OpBB if the definition is not in OpBB.
       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);
     }
 
     addPHIWriteAccess(PHI, OpBB, Op, IsExitBlock);
   }
 
for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
 
     // Do not build scalar dependences for required invariant loads as we will
     // hoist them later on anyway or drop the SCoP if we cannot.
     if (ScopRIL.count(dyn_cast<LoadInst>(Inst)))
       continue;
 
     if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
       if (!isa<StoreInst>(Inst))
-        addValueWriteAccess(Inst);
+        ensureValueWrite(Inst);
     }
   }
 }
 
 void ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
                                MemoryAccess::AccessType Type,
                                Value *BaseAddress, unsigned ElemBytes,
                                bool Affine, Value *AccessValue,
void ScopInfo::addArrayAccess(Instruction *MemAccInst,
                               ArrayRef<const SCEV *> Sizes,
                               Value *AccessValue) {
   assert(isa<LoadInst>(MemAccInst) || isa<StoreInst>(MemAccInst));
   assert(isa<LoadInst>(MemAccInst) == (Type == MemoryAccess::READ));
   addMemoryAccess(MemAccInst->getParent(), MemAccInst, Type, BaseAddress,
                   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);
 }
 void ScopInfo::addValueReadAccess(Value *Value, Instruction *User) {
   assert(!isa<PHINode>(User));
   addMemoryAccess(User->getParent(), User, MemoryAccess::READ, Value, 1, true,
                   Value, ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),

polly/trunk/test/ScopInfo/phi_scalar_simple_1.ll

 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             [N] -> { Stmt_for_cond[i0] : N >= 2 and 0 <= i0 < N; Stmt_for_cond[0] : N <= 1 };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             [N] -> { Stmt_for_cond[i0] -> [i0, 0, 0, 0] : N >= 2 and i0 < N; Stmt_for_cond[0] -> [0, 0, 0, 0] : N <= 1 };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; 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 };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             [N] -> { Stmt_for_body[i0] -> [i0, 1, 0, 0] };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             [N] -> { Stmt_for_body[i0] -> MemRef_x_addr_0[] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]

polly/trunk/test/ScopInfo/phi_scalar_simple_2.ll

 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_cond[i0] -> [i0, 0, 0, 0] : i0 <= N; Stmt_for_cond[0] -> [0, 0, 0, 0] : N < 0 };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_cond[i0] -> MemRef_x_addr_0__phi[] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; 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 };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_body[i0] -> [i0, 1, 0, 0] };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_body[i0] -> MemRef_x_addr_0[] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_body[i0] -> MemRef_x_addr_1__phi[] };
 ; CHECK-NEXT:     Stmt_for_cond1
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_cond1[i0, i1] : 0 <= i0 < N and 0 <= i1 <= N };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_cond1[i0, i1] -> [i0, 2, i1, 0] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; 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 };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_body3[i0, i1] -> [i0, 2, i1, 1] };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             [N, c] -> { Stmt_for_body3[i0, i1] -> MemRef_x_addr_1[] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]