[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

elsewhere

1000

... or unexisting.

1935

statement

1942

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

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 intruction 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 elsewehere 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:
   /// @brief Return the __first__ (scalar) memory access for @p Inst if any.
   MemoryAccess *lookupAccessFor(const Instruction *Inst) const {
     auto It = InstructionToAccess.find(Inst);
     if (It == InstructionToAccess.end())
       return nullptr;
     return It->getSecond()->empty() ? nullptr : It->getSecond()->front();
   }
 
+  /// @brief Return the MemoryAccess that reloads a value, or nullptr if not
+  ///        (yet) added.
+  MemoryAccess *lookupValueReadOf(Value *Inst) const {
+    return ValueReads.lookup(Inst);
+  }
+
   /// @brief Return the MemoryAccess that writes the value of an instruction
   ///        defined in this statement, or nullptr if not (yet) added.
   MemoryAccess *lookupValueWriteOf(Instruction *Inst) const {
     assert((isRegionStmt() && R->contains(Inst)) ||
            (!isRegionStmt() && Inst->getParent() == BB));
     return ValueWrites.lookup(Inst);
   }
 
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 ensureValueReload()
   /// @see ScopArrayInfo::MemoryKind
   void ensureValueStore(Instruction *Value);
 
-  /// @brief Create a MemoryAccess for reloading an llvm::Value.
+  /// @brief Ensure an llvm::Value is available in the BB's statment, 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 addValueWriteAccess()
-  /// @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()
+  /// @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 ensureValueReload(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.

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()))

 void ScopStmt::addAccess(MemoryAccess *Access) {
   Instruction *AccessInst = Access->getAccessInstruction();
 
   if (Access->isArrayKind()) {
     MemoryAccessList *&MAL = InstructionToAccess[AccessInst];
     if (!MAL)
       MAL = new MemoryAccessList();
     MAL->emplace_front(Access);
+  } else if (Access->isValueKind() && Access->isRead()) {
+    Value *AccessVal = Access->getAccessValue();
+    assert(!ValueReads.lookup(AccessVal));
+
+    ValueReads[AccessVal] = 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;
   }
 
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);
+        ensureValueReload(OpI, OpBB);
         ensureValueStore(OpI);
       }
     } else if (ModelReadOnlyScalars && !isa<Constant>(Op)) {
-      addValueReadAccess(Op, PHI, OpBB);
+      ensureValueReload(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);
+    ensureValueReload(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);
+      ensureValueReload(Op, Inst->getParent());
     }
   }
 
   return AnyCrossStmtUse;
 }
 
 extern MapInsnToMemAcc InsnToMemAcc;
 
void ScopInfo::ensureValueStore(Instruction *Value) {
   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::ensureValueReload(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 *>(),