Add a value field to memory accesses for a related value

[jdoerfert]

Summary

Add a value field to memory accesses for a related value.
 
  A new field in the memory accesses allows us to track a value related
  to that access.
    - For real memory accesses the value is the loaded result or the
      stored value.
    - For straigt line scalar accesses it is the access instruction
      itself.
    - For PHI operand accesses it is the operand value.
  
  We use this value to simplify code which deduced information about the value
  later in the Polly pipeline and was known to be error prone.

[Meinersbur]

Can you please explain what "hacks" you are referring to?

include/polly/ScopInfo.h

246–247

llvm::Value (e.g. a constant) cannot "cause" accesses.

I think this is bad modelling. A memory access is an effect that happens at some point. Non-instructions do not have such a property. there're passive.

lib/Analysis/ScopInfo.cpp

974

Why is this suddenly necessary?

lib/Analysis/TempScopInfo.cpp

148

I don't see how removing this can work. The .phiops location needs to be written somewhere in the incoming block. If not the terminator, who is it?

lib/CodeGen/BlockGenerators.cpp

1135

Why did PHIIdx < 0 become possible here, but not in the non-NonAffine case?

[jdoerfert]

In D12062#225288, @Meinersbur wrote:

Can you please explain what "hacks" you are referring to?

The fact that a terminator is the cause of an access and the type of the branch condition as some kind of access type.

lib/Analysis/ScopInfo.cpp

974

Because getAccessInstruction in line 910 can become null now.

lib/Analysis/TempScopInfo.cpp

148

This works because the codegen doesn't work the way you think it does. Except for non-affine regions (which are different as explained below) the codegen will not look at the original instruction for scalar write operations but simply insert them at the end of a basic block if they were part of the corresponding ScopStmt.

lib/CodeGen/BlockGenerators.cpp

1135

Because this is a non-affine region and we do not reschedule it. Here all scalar accesses are summarized in one ScopStmt and we have to figure out where to actually put them while iterating over the actual basic blocks.

But we can actually remove the PHIIdx stuff from the affine case now. Thanks, I'll update the patch.

[jdoerfert]

Remove the PHIIdx stuff from the codegen in case of affine regions

[jdoerfert]

Btw. this passes all lnt tests and I think this removes a lot of complicated code in exchange for some simple conditions.

[grosser]

Hi Johannes,

I looked through this patch and saw a couple of the code simplifications you mention in the commit message, but also got the feeling that several changes introduced change behaviour in a way that is somehow confusing to me. Overall, I am not convinced this patch is an improvement as it is.

Best,
Tobias

include/polly/ScopInfo.h

246–247

Similar to Michael, the idea of an "AccessValue" is not understandable to me. The idea of an access instruction was that the access happend at the given instruction. Obviously, a llvm::Value does not have a location and consequently does not trigger a memory access.

You probably have some ideas in mind, but without an explanation of what the AccessValue is meant to be this is unfortunately not understandable to me.

649

My feeling is that this function now changes behavior.

Bevor, for a given instruction the memory accesses we model for this instruction were returned.

Now, look at this example:

bb1:
  sum = add i64 ...  
  br bb2

bb2:
  br bb3             

bb3
  merge = phi [%sum, %bb2], ...

If I now call getAccessFor("%sum"), it will also return the write of %sum into "merge.phiops", even though this memory access is not really performed by the instruction %sum, but it just uses the value %sum.

Besides being unintuitive, I am afraid this change has a risk of breaking other (unrelated parts) of Polly. Specifically, if a value
loaded by a "load" instruction is used in a PHI node, Stmt.getAccessFor("load") will return only one out of two memory accesses. As the PHI access is likely to be constructed later
and will be inserted at the front, the first access is most likely the wrong one.

void VectorBlockGenerator::generateLoad(ScopStmt &Stmt, const LoadInst *Load,    
                                        ValueMapT &VectorMap,                    
                                        VectorValueMapT &ScalarMaps) {           
  if (!VectorType::isValidElementType(Load->getType())) {                        
    for (int i = 0; i < getVectorWidth(); i++)                                   
      ScalarMaps[i][Load] =                                                      
          generateScalarLoad(Stmt, Load, ScalarMaps[i], GlobalMaps[i], VLTS[i]); 
    return;                                                                      
  }                                                                              
                                                                                 
  const MemoryAccess &Access = Stmt.getAccessFor(Load);

lib/Analysis/ScopInfo.cpp

974

This change is also confusing. Does this mean we will not support scalar reductions any more?

[jdoerfert]

We could have both, an access instruction as well as an access value, that way we keep the best of both worlds. I will update the patch as I think it might be worth it.

lib/Analysis/ScopInfo.cpp

974

We never did in upstream Polly.

[jdoerfert]

Introduce a value additionally to the access instruction

[jdoerfert]

I updated the patch and marked the outdated comments as done.

This version just adds a value field in order to simplify some stuff later on.

[grosser]

LGTM.

include/polly/ScopInfo.h

249

Maybe expand the comment a little (add some info from the commit message?).

include/polly/ScopInfo.h

private:
   /// for which j = 0 holds do. After lifing the equality check in ScopInfo,
   /// subsequent transformations do not only need check if a statement is
   /// reduction like, but they also need to verify that that the reduction
   /// property is only exploited for statement instances that load from and
   /// store to the same data location. Doing so at dependence analysis time
   /// could allow us to handle the above example.
   ReductionType RedType = RT_NONE;
 
-  /// @brief The access instruction of this memory access.
-  Instruction *Inst;
+  /// @brief The access value that caused this memory access.
+  Value *AccessValue;
 
   /// Updated access relation read from JSCOP file.
   isl_map *newAccessRelation;
 
   /// @brief A unique identifier for this memory access.
   ///
   /// The identifier is unique between all memory accesses belonging to the same
   /// scop statement.
   isl_id *Id;
 
private:
   __isl_give isl_map *foldAccess(const IRAccess &Access,
                                  __isl_take isl_map *AccessRelation,
                                  ScopStmt *Statement);
 
 public:
   /// @brief Create a memory access from an access in LLVM-IR.
   ///
   /// @param Access     The memory access.
-  /// @param AccInst    The access instruction.
+  /// @param AccessVal  The access value that caused this memory access.
   /// @param Statement  The statement that contains the access.
   /// @param SAI        The ScopArrayInfo object for this base pointer.
   /// @param Identifier An identifier that is unique for all memory accesses
   ///                   belonging to the same scop statement.
-  MemoryAccess(const IRAccess &Access, Instruction *AccInst,
-               ScopStmt *Statement, const ScopArrayInfo *SAI, int Identifier);
+  MemoryAccess(const IRAccess &Access, Value *AccessVale, ScopStmt *Statement,
+               const ScopArrayInfo *SAI, int Identifier);
 
   ~MemoryAccess();
 
   /// @brief Get the type of a memory access.
   enum AccessType getType() { return AccType; }
 
   /// @brief Is this a reduction like access?
   bool isReductionLike() const { return RedType != RT_NONE; }
public:
   /// @brief Return a string representation of the accesse's reduction type.
   const std::string getReductionOperatorStr() const;
 
   /// @brief Return a string representation of the reduction type @p RT.
   static const std::string getReductionOperatorStr(ReductionType RT);
 
   const std::string &getBaseName() const { return BaseName; }
 
+  /// @brief Return the access value of this memory access.
+  Value *getAccessValue() const { return AccessValue; }
+
   /// @brief Return the access instruction of this memory access.
-  Instruction *getAccessInstruction() const { return Inst; }
+  ///
+  /// This can be a nullptr if and only if this memory access is a scalar write
+  /// access that was created for a non-instruction (Constant, Argument,...) as
+  /// it is a PHI operand.
+  ///
+  Instruction *getAccessInstruction() const {
+    return dyn_cast<Instruction>(AccessValue);
+  }
 
   /// Get the stride of this memory access in the specified Schedule. Schedule
   /// is a map from the statement to a schedule where the innermost dimension is
   /// the dimension of the innermost loop containing the statement.
   __isl_give isl_set *getStride(__isl_take const isl_map *Schedule) const;
 
   /// Is the stride of the access equal to a certain width? Schedule is a map
   /// from the statement to a schedule where the innermost dimension is the
private:
   isl_set *Domain;
 
   /// The memory accesses of this statement.
   ///
   /// 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 Mapping from values to (scalar) memory accesses they induced.
+  DenseMap<const Value *, MemoryAccessList *> ValueToAccess;
 
   //@}
 
   /// @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:
   ///
   /// @return The region represented by this ScopStmt, or null if the statement
   ///         represents a basic block.
   Region *getRegion() const { return R; }
 
   /// @brief Return true if this statement represents a whole region.
   bool isRegionStmt() const { return R != nullptr; }
 
-  /// @brief Return the (scalar) memory accesses for @p Inst.
-  const MemoryAccessList &getAccessesFor(const Instruction *Inst) const {
-    MemoryAccessList *MAL = lookupAccessesFor(Inst);
+  /// @brief Return the (scalar) memory accesses for @p Val.
+  const MemoryAccessList &getAccessesFor(const Value *Val) const {
+    MemoryAccessList *MAL = lookupAccessesFor(Val);
     assert(MAL && "Cannot get memory accesses because they do not exist!");
     return *MAL;
   }
 
-  /// @brief Return the (scalar) memory accesses for @p Inst if any.
-  MemoryAccessList *lookupAccessesFor(const Instruction *Inst) const {
-    auto It = InstructionToAccess.find(Inst);
-    return It == InstructionToAccess.end() ? nullptr : It->getSecond();
+  /// @brief Return the (scalar) memory accesses for @p Val if any.
+  MemoryAccessList *lookupAccessesFor(const Value *Val) const {
+    auto It = ValueToAccess.find(Val);
+    return It == ValueToAccess.end() ? nullptr : It->getSecond();
   }
 
-  /// @brief Return the __first__ (scalar) memory access for @p Inst.
-  const MemoryAccess &getAccessFor(const Instruction *Inst) const {
-    MemoryAccess *MA = lookupAccessFor(Inst);
+  /// @brief Return the __first__ (scalar) memory access for @p Val.
+  const MemoryAccess &getAccessFor(const Value *Val) const {
+    MemoryAccess *MA = lookupAccessFor(Val);
     assert(MA && "Cannot get memory access because it does not exist!");
     return *MA;
   }
 
-  /// @brief Return the __first__ (scalar) memory access for @p Inst if any.
-  MemoryAccess *lookupAccessFor(const Instruction *Inst) const {
-    auto It = InstructionToAccess.find(Inst);
-    return It == InstructionToAccess.end() ? nullptr
-                                           : &It->getSecond()->front();
+  /// @brief Return the __first__ (scalar) memory access for @p Val if any.
+  MemoryAccess *lookupAccessFor(const Value *Val) const {
+    auto It = ValueToAccess.find(Val);
+    return It == ValueToAccess.end() ? nullptr : &It->getSecond()->front();
   }
 
   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;
   }

include/polly/TempScopInfo.h

 /// A canonical induction variable is:
 /// an integer recurrence that starts at 0 and increments by one each time
 /// through the loop.
 typedef std::map<const Loop *, const SCEV *> LoopBoundMapType;
 
 /// Mapping BBs to its condition constrains
 typedef std::map<const BasicBlock *, BBCond> BBCondMapType;
 
-typedef std::vector<std::pair<IRAccess, Instruction *>> AccFuncSetType;
+typedef std::vector<std::pair<IRAccess, Value *>> AccFuncSetType;
 typedef std::map<const BasicBlock *, AccFuncSetType> AccFuncMapType;
 
 //===---------------------------------------------------------------------===//
 /// @brief Scop represent with llvm objects.
 ///
 /// A helper class for remembering the parameter number and the max depth in
 /// this Scop, and others context.
 class TempScop {

lib/Analysis/ScopInfo.cpp

for (int i = Size - 2; i >= 0; --i) {
     MapTwo = isl_map_upper_bound_si(MapTwo, isl_dim_in, i + 1, -1);
 
     MapOne = isl_map_union(MapOne, MapTwo);
     AccessRelation = isl_map_apply_range(AccessRelation, MapOne);
   }
   return AccessRelation;
 }
 
-MemoryAccess::MemoryAccess(const IRAccess &Access, Instruction *AccInst,
+MemoryAccess::MemoryAccess(const IRAccess &Access, Value *AccessVal,
                            ScopStmt *Statement, const ScopArrayInfo *SAI,
                            int Identifier)
-    : AccType(getMemoryAccessType(Access)), Statement(Statement), Inst(AccInst),
-      newAccessRelation(nullptr) {
+    : AccType(getMemoryAccessType(Access)), Statement(Statement),
+      AccessValue(AccessVal), newAccessRelation(nullptr) {
 
   isl_ctx *Ctx = Statement->getIslCtx();
   BaseAddr = Access.getBase();
   BaseName = getIslCompatibleName("MemRef_", getBaseAddr(), "");
 
   isl_id *BaseAddrId = SAI->getBasePtrId();
 
   auto IdName = "__polly_array_ref_" + std::to_string(Identifier);

 void ScopStmt::restrictDomain(__isl_take isl_set *NewDomain) {
   assert(isl_set_is_subset(NewDomain, Domain) &&
          "New domain is not a subset of old domain!");
   isl_set_free(Domain);
   Domain = NewDomain;
 }
 
 // @brief Get the data-type of the elements accessed
-static Type *getAccessType(IRAccess &Access, Instruction *AccessInst) {
-  if (Access.isPHI())
-    return Access.getBase()->getType();
-
-  if (StoreInst *Store = dyn_cast<StoreInst>(AccessInst))
+static Type *getAccessType(IRAccess &Access, Value *AccessValue) {
+  if (StoreInst *Store = dyn_cast<StoreInst>(AccessValue))
     return Store->getValueOperand()->getType();
-  if (BranchInst *Branch = dyn_cast<BranchInst>(AccessInst))
-    return Branch->getCondition()->getType();
-  return AccessInst->getType();
+  return AccessValue->getType();
 }
 
 void ScopStmt::buildAccesses(TempScop &tempScop, BasicBlock *Block,
                              bool isApproximated) {
   AccFuncSetType *AFS = tempScop.getAccessFunctions(Block);
   if (!AFS)
     return;
 
   for (auto &AccessPair : *AFS) {
     IRAccess &Access = AccessPair.first;
-    Instruction *AccessInst = AccessPair.second;
-    Type *ElementType = getAccessType(Access, AccessInst);
+    Value *AccessValue = AccessPair.second;
+    Type *ElementType = getAccessType(Access, AccessValue);
 
     const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
         Access.getBase(), ElementType, Access.Sizes, Access.isPHI());
 
     if (isApproximated && Access.isWrite())
       Access.setMayWrite();
 
-    MemoryAccessList *&MAL = InstructionToAccess[AccessInst];
+    MemoryAccessList *&MAL = ValueToAccess[AccessValue];
     if (!MAL)
       MAL = new MemoryAccessList();
-    MAL->emplace_front(Access, AccessInst, this, SAI, MemAccs.size());
+    MAL->emplace_front(Access, AccessValue, this, SAI, MemAccs.size());
     MemAccs.push_back(&MAL->front());
   }
 }
 
 void ScopStmt::realignParams() {
   for (MemoryAccess *MA : *this)
     MA->realignParams();
 

 /// access can access the same memory as the potential reduction.
 void ScopStmt::checkForReductions() {
   SmallVector<MemoryAccess *, 2> Loads;
   SmallVector<std::pair<MemoryAccess *, MemoryAccess *>, 4> Candidates;
 
   // First collect candidate load-store reduction chains by iterating over all
   // stores and collecting possible reduction loads.
   for (MemoryAccess *StoreMA : MemAccs) {
+    if (StoreMA->isScalar())
+      continue;
     if (StoreMA->isRead())
       continue;
 
     Loads.clear();
     collectCandiateReductionLoads(StoreMA, Loads);
     for (MemoryAccess *LoadMA : Loads)
       Candidates.push_back(std::make_pair(LoadMA, StoreMA));
   }
__isl_give isl_space *ScopStmt::getDomainSpace() const {
   return isl_set_get_space(Domain);
 }
 
 __isl_give isl_id *ScopStmt::getDomainId() const {
   return isl_set_get_tuple_id(Domain);
 }
 
 ScopStmt::~ScopStmt() {
-  DeleteContainerSeconds(InstructionToAccess);
+  DeleteContainerSeconds(ValueToAccess);
   isl_set_free(Domain);
 }
 
 void ScopStmt::print(raw_ostream &OS) const {
   OS << "\t" << getBaseName() << "\n";
   OS.indent(12) << "Domain :=\n";
 
   if (Domain) {

lib/Analysis/TempScopInfo.cpp

if (OpI) {
       if (OpIBB != OpBB) {
         IRAccess ScalarRead(IRAccess::READ, OpI, ZeroOffset, 1, true);
         AccFuncMap[OpBB].push_back(std::make_pair(ScalarRead, PHI));
         IRAccess ScalarWrite(IRAccess::MUST_WRITE, OpI, ZeroOffset, 1, true);
         AccFuncMap[OpIBB].push_back(std::make_pair(ScalarWrite, OpI));
       }
     }
 
-    // If the operand is a constant, global or argument we use the terminator
-    // of the incoming basic block as the access instruction.
-    if (!OpI)
-      OpI = OpBB->getTerminator();
-
     IRAccess ScalarAccess(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true,
                           /* IsPHI */ true);
-    AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, OpI));
+    AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, Op));
   }
 
   if (!OnlyNonAffineSubRegionOperands) {
     IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true,
                           /* IsPHI */ true);
     Functions.push_back(std::make_pair(ScalarAccess, PHI));
   }
 }

lib/CodeGen/BlockGenerators.cpp

assert(Stmt.isBlockStmt() && BB == Stmt.getBasicBlock() &&
          "Region statements need to use the generateScalarStores() "
          "function in the RegionGenerator");
 
   for (MemoryAccess *MA : Stmt) {
     if (!MA->isScalar() || MA->isRead())
       continue;
 
     Instruction *Base = cast<Instruction>(MA->getBaseAddr());
-    Instruction *Inst = MA->getAccessInstruction();
+    Value *Val = MA->getAccessValue();
 
-    Value *Val = nullptr;
     AllocaInst *Address = nullptr;
-
-    if (MA->getScopArrayInfo()->isPHI()) {
-      PHINode *BasePHI = dyn_cast<PHINode>(Base);
-      int PHIIdx = BasePHI->getBasicBlockIndex(BB);
-      assert(PHIIdx >= 0);
+    if (MA->getScopArrayInfo()->isPHI())
       Address = getOrCreateAlloca(Base, PHIOpMap, ".phiops");
-      Val = BasePHI->getIncomingValue(PHIIdx);
-    } else {
+    else
       Address = getOrCreateAlloca(Base, ScalarMap, ".s2a");
-      Val = Inst;
-    }
+
     Val = getNewScalarValue(Val, R, ScalarMap, BBMap, GlobalMap);
     Builder.CreateStore(Val, Address);
   }
 }
 
 void BlockGenerator::createScalarInitialization(Region &R,
                                                 ValueMapT &GlobalMap) {
   // The split block __just before__ the region and optimized region.
assert(StmtR && "Block statements need to use the generateScalarStores() "
                   "function in the BlockGenerator");
 
   for (MemoryAccess *MA : Stmt) {
 
     if (!MA->isScalar() || MA->isRead())
       continue;
 
     Instruction *ScalarBase = cast<Instruction>(MA->getBaseAddr());
-    Instruction *ScalarInst = MA->getAccessInstruction();
+    Value *ScalarVal = MA->getAccessValue();
+    Instruction *ScalarInst = dyn_cast<Instruction>(ScalarVal);
     PHINode *ScalarBasePHI = dyn_cast<PHINode>(ScalarBase);
 
     // Only generate accesses that belong to this basic block.
-    if (ScalarInst->getParent() != BB)
+    if (ScalarInst && ScalarInst->getParent() != BB)
       continue;
 
     Value *Val = nullptr;
     AllocaInst *ScalarAddr = nullptr;
 
     if (MA->getScopArrayInfo()->isPHI()) {
       int PHIIdx = ScalarBasePHI->getBasicBlockIndex(BB);
+      if (PHIIdx < 0)
+        continue;
       ScalarAddr = getOrCreateAlloca(ScalarBase, PHIOpMap, ".phiops");
       Val = ScalarBasePHI->getIncomingValue(PHIIdx);
     } else {
       ScalarAddr = getOrCreateAlloca(ScalarBase, ScalarMap, ".s2a");
-      Val = ScalarInst;
+      Val = ScalarVal;
     }
 
     Val = getNewScalarValue(Val, R, ScalarMap, BBMap, GlobalMap);
     Builder.CreateStore(Val, ScalarAddr);
   }
 }
 
 void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, const PHINode *PHI,