[Polly] Unique value read accesses

[Meinersbur]

Summary

Keep at most one value read MemoryAccess per value and statement; multiple generated loads do not have any additional effect. As one such MemoryAccess can cater multiple uses within the statement, the AccessInstruction property is not unique any more and set to nullptr.

[grosser]

This looks generally good to me (besides some minor comments), but let's wait for the phone call tonight.

include/polly/ScopInfo.h

833 ↗

(On Diff #42792)

elsewhere

1000 ↗

(On Diff #42792)

... or unexisting.

1935 ↗

(On Diff #42792)

statement

1942 ↗

(On Diff #42792)

I would prefer to call this ensureValueRead() as this corresponds better with the surrounding code (the map is called ValueReads).

[grosser]

Accepted if my minor comments have been addressed.

[Meinersbur]

Addressed Tobias' comments

polly/trunk/include/polly/ScopInfo.h

private:
   /// Load or Store instruction performing the access.
   ///
   /// For memory accesses of kind MK_PHI or MK_ExitPHI the access
   /// instruction of a load access is the PHI instruction. The access
   /// instruction of a PHI-store is the incoming's block's terminator
   /// intruction.
   ///
   /// For memory accesses of kind MK_Value the access instruction of a load
-  /// access is the instruction that uses the load. The access instruction of
-  /// a write access is the instruction that defines the llvm::Value.
+  /// access is nullptr because generally there can be multiple instructions in
+  /// the statement using the same llvm::Value. The access instruction of a
+  /// write access is the instruction that defines the llvm::Value.
   Instruction *AccessInstruction;
 
   /// @brief The value associated with this memory access.
   ///
   ///  - For array memory accesses (MK_Array) it is the loaded result or the
   ///    stored value.
   ///  - For accesses of kind MK_Value it is the access instruction itself.
   ///  - For accesses of kind MK_PHI or MK_ExitPHI it is the operand value
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 elsewhere required in this ScopStmt and
+  ///        their MK_Value READ MemoryAccesses.
+  DenseMap<Value *, MemoryAccess *> ValueReads;
+
   /// @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
public:
   ///        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);
   }
 
+  /// @brief Return the MemoryAccess that reloads a value, or nullptr if not
+  ///        existing, respectively not yet added.
+  MemoryAccess *lookupValueReadOf(Value *Inst) const {
+    return ValueReads.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.
void addArrayAccess(Instruction *MemAccInst, MemoryAccess::AccessType Type,
                       ArrayRef<const SCEV *> Subscripts,
                       ArrayRef<const SCEV *> Sizes, Value *AccessValue);
 
   /// @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 ensureValueRead()
   /// @see ScopArrayInfo::MemoryKind
   void ensureValueWrite(Instruction *Value);
 
-  /// @brief Create a MemoryAccess for reloading an llvm::Value.
+  /// @brief Ensure an llvm::Value is available in the BB's statement, creating
+  ///        a MemoryAccess for reloading it if necessary.
   ///
-  /// 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 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 ensureValueWrite()
+  /// @param Value  The value expected to be loaded.
+  /// @param UserBB Where to reload the value.
+  /// @see ensureValueStore()
   /// @see ScopArrayInfo::MemoryKind
-  void addValueReadAccess(Value *Value, PHINode *User, BasicBlock *UserBB);
+  void ensureValueRead(Value *Value, 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.
   ///
   /// @param PHI           PHINode under consideration.
   /// @param IncomingBlock Some predecessor block.

polly/trunk/lib/Analysis/ScopInfo.cpp

void MemoryAccess::assumeNoOutOfBound() {
   Outside = isl_set_params(Outside);
 
   // Remove divs to avoid the construction of overly complicated assumptions.
   // Doing so increases the set of parameter combinations that are assumed to
   // not appear. This is always save, but may make the resulting run-time check
   // bail out more often than strictly necessary.
   Outside = isl_set_remove_divs(Outside);
   Outside = isl_set_complement(Outside);
-  Statement->getParent()->addAssumption(INBOUNDS, Outside,
-                                        getAccessInstruction()->getDebugLoc());
+  Statement->getParent()->addAssumption(
+      INBOUNDS, Outside,
+      getAccessInstruction() ? getAccessInstruction()->getDebugLoc() : nullptr);
   isl_space_free(Space);
 }
 
 void MemoryAccess::computeBoundsOnAccessRelation(unsigned ElementSize) {
   ScalarEvolution *SE = Statement->getParent()->getSE();
 
   Value *Ptr = getPointerOperand(*getAccessInstruction());
   if (!Ptr || !SE->isSCEVable(Ptr->getType()))
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;
+  } else if (Access->isValueKind() && Access->isRead()) {
+    Value *AccessVal = Access->getAccessValue();
+    assert(!ValueReads.lookup(AccessVal));
+
+    ValueReads[AccessVal] = Access;
   }
 
   MemAccs.push_back(Access);
 }
 
 void ScopStmt::realignParams() {
   for (MemoryAccess *MA : *this)
     MA->realignParams();
for (MemoryAccess *Access : MemAccs)
     Access->print(OS);
 }
 
 void ScopStmt::dump() const { print(dbgs()); }
 
 void ScopStmt::removeMemoryAccesses(MemoryAccessList &InvMAs) {
   // Remove all memory accesses in @p InvMAs from this statement
   // together with all scalar accesses that were caused by them.
+  // MK_Value READs have no access instruction, hence would not be removed by
+  // this function. However, it is only used for invariant LoadInst accesses,
+  // its arguments are always affine, hence synthesizable, and therefore there
+  // are no MK_Value READ accesses to be removed.
   for (MemoryAccess *MA : InvMAs) {
     auto Predicate = [&](MemoryAccess *Acc) {
       return Acc->getAccessInstruction() == MA->getAccessInstruction();
     };
     MemAccs.erase(std::remove_if(MemAccs.begin(), MemAccs.end(), Predicate),
                   MemAccs.end());
     InstructionToAccess.erase(MA->getAccessInstruction());
   }
for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
     Instruction *OpI = dyn_cast<Instruction>(Op);
     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);
+        ensureValueRead(OpI, OpBB);
         ensureValueWrite(OpI);
       }
     } else if (ModelReadOnlyScalars && !isa<Constant>(Op)) {
-      addValueReadAccess(Op, PHI, OpBB);
+      ensureValueRead(Op, OpBB);
     }
 
     addPHIWriteAccess(PHI, OpBB, Op, IsExitBlock);
   }
 
   if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {
     addPHIReadAccess(PHI);
   }
if (isa<PHINode>(UI))
       continue;
 
     // Now U is used in another statement.
     AnyCrossStmtUse = true;
 
     // Do not build a read access that is not in the current SCoP
     // Use the def instruction as base address of the MemoryAccess, so that it
     // will become the name of the scalar access in the polyhedral form.
-    addValueReadAccess(Inst, UI);
+    ensureValueRead(Inst, UI->getParent());
   }
 
   if (ModelReadOnlyScalars && !isa<PHINode>(Inst)) {
     for (Value *Op : Inst->operands()) {
       if (canSynthesize(Op, LI, SE, R))
         continue;
 
       if (Instruction *OpInst = dyn_cast<Instruction>(Op))
         if (R->contains(OpInst))
           continue;
 
       if (isa<Constant>(Op))
         continue;
 
-      addValueReadAccess(Op, Inst);
+      ensureValueRead(Op, Inst->getParent());
     }
   }
 
   return AnyCrossStmtUse;
 }
 
 extern MapInsnToMemAcc InsnToMemAcc;
 
void ScopInfo::ensureValueWrite(Instruction *Value) {
   // 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 *>(),
-                  ScopArrayInfo::MK_Value);
-}
-void ScopInfo::addValueReadAccess(Value *Value, PHINode *User,
-                                  BasicBlock *UserBB) {
-  addMemoryAccess(UserBB, User, MemoryAccess::READ, Value, 1, true, Value,
+void ScopInfo::ensureValueRead(Value *Value, BasicBlock *UserBB) {
+  ScopStmt *UserStmt = scop->getStmtForBasicBlock(UserBB);
+
+  // We do not model uses outside the scop.
+  if (!UserStmt)
+    return;
+
+  // Do not create another MemoryAccess for reloading the value if one already
+  // exists.
+  if (UserStmt->lookupValueReadOf(Value))
+    return;
+
+  addMemoryAccess(UserBB, nullptr, MemoryAccess::READ, Value, 1, true, Value,
                   ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                   ScopArrayInfo::MK_Value);
 }
 void ScopInfo::addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock,
                                  Value *IncomingValue, bool IsExitBlock) {
   addMemoryAccess(IncomingBlock, IncomingBlock->getTerminator(),
                   MemoryAccess::MUST_WRITE, PHI, 1, true, IncomingValue,
                   ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),