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 ↗

(On Diff #32235)

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

970 ↗

(On Diff #32235)

Why is this suddenly necessary?

lib/Analysis/TempScopInfo.cpp

148 ↗

(On Diff #32235)

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

1141 ↗

(On Diff #32235)

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

970 ↗

(On Diff #32235)

Because getAccessInstruction in line 910 can become null now.

lib/Analysis/TempScopInfo.cpp

148 ↗

(On Diff #32235)

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

1141 ↗

(On Diff #32235)

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 ↗

(On Diff #32243)

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 ↗

(On Diff #32243)

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 ↗

(On Diff #32243)

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 ↗

(On Diff #32243)

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

250 ↗

(On Diff #32285)

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

polly/trunk/include/polly/ScopInfo.h

private:
   /// 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;
+  Instruction *AccessInstruction;
+
+  /// @brief The value associated with this memory access.
+  ///
+  ///  - For real memory accesses it 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.
+  ///
+  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.
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; }
+  Instruction *getAccessInstruction() const { return AccessInstruction; }
 
   /// 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

polly/trunk/include/polly/TempScopInfo.h

 
 namespace polly {
 
 //===---------------------------------------------------------------------===//
 /// @brief A memory access described by a SCEV expression and the access type.
 class IRAccess {
 public:
   Value *BaseAddress;
+  Value *AccessValue;
 
   const SCEV *Offset;
 
   // The type of the scev affine function
   enum TypeKind {
     READ = 0x1,
     MUST_WRITE = 0x2,
     MAY_WRITE = 0x3,

 
 public:
   SmallVector<const SCEV *, 4> Subscripts, Sizes;
 
   /// @brief Create a new IRAccess
   ///
   /// @param IsPHI Are we modeling special PHI node accesses?
   explicit IRAccess(TypeKind Type, Value *BaseAddress, const SCEV *Offset,
-                    unsigned elemBytes, bool Affine, bool IsPHI = false)
-      : BaseAddress(BaseAddress), Offset(Offset), ElemBytes(elemBytes),
-        Type(Type), IsAffine(Affine), IsPHI(IsPHI) {}
+                    unsigned elemBytes, bool Affine, Value *AccessValue,
+                    bool IsPHI = false)
+      : BaseAddress(BaseAddress), AccessValue(AccessValue), Offset(Offset),
+        ElemBytes(elemBytes), Type(Type), IsAffine(Affine), IsPHI(IsPHI) {}
 
   explicit IRAccess(TypeKind Type, Value *BaseAddress, const SCEV *Offset,
                     unsigned elemBytes, bool Affine,
                     SmallVector<const SCEV *, 4> Subscripts,
-                    SmallVector<const SCEV *, 4> Sizes)
-      : BaseAddress(BaseAddress), Offset(Offset), ElemBytes(elemBytes),
-        Type(Type), IsAffine(Affine), IsPHI(false), Subscripts(Subscripts),
-        Sizes(Sizes) {}
+                    SmallVector<const SCEV *, 4> Sizes, Value *AccessValue)
+      : BaseAddress(BaseAddress), AccessValue(AccessValue), Offset(Offset),
+        ElemBytes(elemBytes), Type(Type), IsAffine(Affine), IsPHI(false),
+        Subscripts(Subscripts), Sizes(Sizes) {}
 
   enum TypeKind getType() const { return Type; }
 
   Value *getBase() const { return BaseAddress; }
 
+  Value *getAccessValue() const { return AccessValue; }
+
   const SCEV *getOffset() const { return Offset; }
 
   unsigned getElemSizeInBytes() const { return ElemBytes; }
 
   bool isAffine() const { return IsAffine; }
 
   bool isRead() const { return Type == READ; }
 

polly/trunk/lib/Analysis/ScopInfo.cpp

for (int i = Size - 2; i >= 0; --i) {
     AccessRelation = isl_map_apply_range(AccessRelation, MapOne);
   }
   return AccessRelation;
 }
 
 MemoryAccess::MemoryAccess(const IRAccess &Access, Instruction *AccInst,
                            ScopStmt *Statement, const ScopArrayInfo *SAI,
                            int Identifier)
-    : AccType(getMemoryAccessType(Access)), Statement(Statement), Inst(AccInst),
+    : AccType(getMemoryAccessType(Access)), Statement(Statement),
+      AccessInstruction(AccInst), AccessValue(Access.getAccessValue()),
       newAccessRelation(nullptr) {
 
   isl_ctx *Ctx = Statement->getIslCtx();
   BaseAddr = Access.getBase();
   BaseName = getIslCompatibleName("MemRef_", getBaseAddr(), "");
 
   isl_id *BaseAddrId = SAI->getBasePtrId();
 

 
 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))
-    return Store->getValueOperand()->getType();
-  if (BranchInst *Branch = dyn_cast<BranchInst>(AccessInst))
-    return Branch->getCondition()->getType();
-  return AccessInst->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);
+    Type *ElementType = Access.getAccessValue()->getType();
 
     const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
         Access.getBase(), ElementType, Access.Sizes, Access.isPHI());
 
     if (isApproximated && Access.isWrite())
       Access.setMayWrite();
 
     MemoryAccessList *&MAL = InstructionToAccess[AccessInst];

polly/trunk/lib/Analysis/TempScopInfo.cpp

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 (OpIBB != OpBB) {
-        IRAccess ScalarRead(IRAccess::READ, OpI, ZeroOffset, 1, true);
+        IRAccess ScalarRead(IRAccess::READ, OpI, ZeroOffset, 1, true, OpI);
         AccFuncMap[OpBB].push_back(std::make_pair(ScalarRead, PHI));
-        IRAccess ScalarWrite(IRAccess::MUST_WRITE, OpI, ZeroOffset, 1, true);
+        IRAccess ScalarWrite(IRAccess::MUST_WRITE, OpI, ZeroOffset, 1, true,
+                             OpI);
         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,
+    IRAccess ScalarAccess(IRAccess::MUST_WRITE, PHI, ZeroOffset, 1, true, Op,
                           /* IsPHI */ true);
     AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, OpI));
   }
 
   if (!OnlyNonAffineSubRegionOperands) {
-    IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true,
+    IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true, PHI,
                           /* IsPHI */ true);
     Functions.push_back(std::make_pair(ScalarAccess, PHI));
   }
 }
 
 bool TempScopInfo::buildScalarDependences(Instruction *Inst, Region *R,
                                           Region *NonAffineSubRegion) {
   bool canSynthesizeInst = canSynthesize(Inst, LI, SE, R);
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 IRAccess, so that it will
     // become the name of the scalar access in the polyhedral form.
-    IRAccess ScalarAccess(IRAccess::READ, Inst, ZeroOffset, 1, true);
+    IRAccess ScalarAccess(IRAccess::READ, Inst, ZeroOffset, 1, true, Inst);
     AccFuncMap[UseParent].push_back(std::make_pair(ScalarAccess, UI));
   }
 
   if (ModelReadOnlyScalars) {
     for (Value *Op : Inst->operands()) {
       if (canSynthesize(Op, LI, SE, R))
         continue;
 
       if (Instruction *OpInst = dyn_cast<Instruction>(Op))
         if (R->contains(OpInst))
           continue;
 
-      IRAccess ScalarAccess(IRAccess::READ, Op, ZeroOffset, 1, true);
+      IRAccess ScalarAccess(IRAccess::READ, Op, ZeroOffset, 1, true, Op);
       AccFuncMap[Inst->getParent()].push_back(
           std::make_pair(ScalarAccess, Inst));
     }
   }
 
   return AnyCrossStmtUse;
 }
 
 extern MapInsnToMemAcc InsnToMemAcc;
 
 IRAccess
 TempScopInfo::buildIRAccess(Instruction *Inst, Loop *L, Region *R,
                             const ScopDetection::BoxedLoopsSetTy *BoxedLoops) {
   unsigned Size;
   Type *SizeType;
+  Value *Val;
   enum IRAccess::TypeKind Type;
 
   if (LoadInst *Load = dyn_cast<LoadInst>(Inst)) {
     SizeType = Load->getType();
     Size = TD->getTypeStoreSize(SizeType);
     Type = IRAccess::READ;
+    Val = Load;
   } else {
     StoreInst *Store = cast<StoreInst>(Inst);
     SizeType = Store->getValueOperand()->getType();
     Size = TD->getTypeStoreSize(SizeType);
     Type = IRAccess::MUST_WRITE;
+    Val = Store->getValueOperand();
   }
 
   const SCEV *AccessFunction = SE->getSCEVAtScope(getPointerOperand(*Inst), L);
   const SCEVUnknown *BasePointer =
       dyn_cast<SCEVUnknown>(SE->getPointerBase(AccessFunction));
 
   assert(BasePointer && "Could not find base pointer");
   AccessFunction = SE->getMinusSCEV(AccessFunction, BasePointer);
 
   auto AccItr = InsnToMemAcc.find(Inst);
   if (PollyDelinearize && AccItr != InsnToMemAcc.end())
     return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, true,
                     AccItr->second.DelinearizedSubscripts,
-                    AccItr->second.Shape->DelinearizedSizes);
+                    AccItr->second.Shape->DelinearizedSizes, Val);
 
   // Check if the access depends on a loop contained in a non-affine subregion.
   bool isVariantInNonAffineLoop = false;
   if (BoxedLoops) {
     SetVector<const Loop *> Loops;
     findLoops(AccessFunction, Loops);
     for (const Loop *L : Loops)
       if (BoxedLoops->count(L))
         isVariantInNonAffineLoop = true;
   }
 
   bool IsAffine = !isVariantInNonAffineLoop &&
                   isAffineExpr(R, AccessFunction, *SE, BasePointer->getValue());
 
   SmallVector<const SCEV *, 4> Subscripts, Sizes;
   Subscripts.push_back(AccessFunction);
   Sizes.push_back(SE->getConstant(ZeroOffset->getType(), Size));
 
   if (!IsAffine && Type == IRAccess::MUST_WRITE)
     Type = IRAccess::MAY_WRITE;
 
   return IRAccess(Type, BasePointer->getValue(), AccessFunction, Size, IsAffine,
-                  Subscripts, Sizes);
+                  Subscripts, Sizes, Val);
 }
 
 void TempScopInfo::buildAccessFunctions(Region &R, Region &SR) {
 
   if (SD->isNonAffineSubRegion(&SR, &R)) {
     for (BasicBlock *BB : SR.blocks())
       buildAccessFunctions(R, *BB, &SR);
     return;
for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
 
     if (PHINode *PHI = dyn_cast<PHINode>(Inst))
       buildPHIAccesses(PHI, R, Functions, NonAffineSubRegion);
 
     if (!isa<StoreInst>(Inst) &&
         buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
       // If the Instruction is used outside the statement, we need to build the
       // write access.
-      IRAccess ScalarAccess(IRAccess::MUST_WRITE, Inst, ZeroOffset, 1, true);
+      IRAccess ScalarAccess(IRAccess::MUST_WRITE, Inst, ZeroOffset, 1, true,
+                            Inst);
       Functions.push_back(std::make_pair(ScalarAccess, Inst));
     }
   }
 
   if (Functions.empty())
     return;
 
   AccFuncSetType &Accs = AccFuncMap[&BB];

polly/trunk/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.
void RegionGenerator::generateScalarStores(ScopStmt &Stmt, BasicBlock *BB,
 
   for (MemoryAccess *MA : Stmt) {
 
     if (!MA->isScalar() || MA->isRead())
       continue;
 
     Instruction *ScalarBase = cast<Instruction>(MA->getBaseAddr());
     Instruction *ScalarInst = MA->getAccessInstruction();
-    PHINode *ScalarBasePHI = dyn_cast<PHINode>(ScalarBase);
 
     // Only generate accesses that belong to this basic block.
     if (ScalarInst->getParent() != BB)
       continue;
 
-    Value *Val = nullptr;
+    Value *Val = MA->getAccessValue();
     AllocaInst *ScalarAddr = nullptr;
 
-    if (MA->getScopArrayInfo()->isPHI()) {
-      int PHIIdx = ScalarBasePHI->getBasicBlockIndex(BB);
+    if (MA->getScopArrayInfo()->isPHI())
       ScalarAddr = getOrCreateAlloca(ScalarBase, PHIOpMap, ".phiops");
-      Val = ScalarBasePHI->getIncomingValue(PHIIdx);
-    } else {
+    else
       ScalarAddr = getOrCreateAlloca(ScalarBase, ScalarMap, ".s2a");
-      Val = ScalarInst;
-    }
 
     Val = getNewScalarValue(Val, R, ScalarMap, BBMap, GlobalMap);
     Builder.CreateStore(Val, ScalarAddr);
   }
 }
 
 void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, const PHINode *PHI,
                                       PHINode *PHICopy, BasicBlock *IncomingBB,