[Polly] Introduce origin/kind for exit PHI node accesses

[Meinersbur]

Summary

Previously, accesses that originate from PHI nodes in the exit block were registered as SCALAR. In some context they are treated as scalars, but it makes a difference in others. We used to check whether the AccessInstruction is a terminator to differentiate the cases.

This patch introduces an MemoryAccess origin EXIT_PHI and a ScopArrayInfo kind KIND_EXIT_PHI to make this case more explicit. No behavioural change intended.

[jdoerfert]

If this is not too pressing I'd like till Wednesday to formulate a real
response.

• signature.asc219 BDownload

[Meinersbur]

Grammar corrections. Thanks Tobias for the hints.

[Meinersbur]

In D14688#289785, @jdoerfert wrote:

If this is not too pressing I'd like till Wednesday to formulate a real
response.

kk,

On Wednesday I am on my way to Poland. No guarantee that I can react before next week.

[grosser]

Hi Johannes,

you are likely busy this week, but in case you happen to have a free minute I would be interested in your comments here.

polly/trunk/include/polly/ScopInfo.h

public:
   /// @brief The type of a memory access.
   enum ARRAYKIND {
     // Scalar references to SSA values.
     KIND_SCALAR,
 
     // Scalar references used to model PHI nodes
     KIND_PHI,
 
+    // Like KIND_PHI, but for PHIs in the exit node. Depending on context, these
+    // are handled like KIND_SCALAR.
+    KIND_EXIT_PHI,
+
     // References to (multi-dimensional) arrays
     KIND_ARRAY,
   };
 
   /// @brief Construct a ScopArrayInfo object.
   ///
   /// @param BasePtr        The array base pointer.
   /// @param ElementType    The type of the elements stored in the array.
public:
   /// ------------------------------------  ------------------------------------
   ///
   /// #AccessInst is either the llvm::Value for WRITEs or the value's user for
   /// READS. The #BaseAddr is represented by the value's definition (i.e. the
   /// llvm::Value itself) as no such alloca yet exists before CodeGeneration.
   /// #AccessValue is also the llvm::Value itself.
   ///
   ///
-  /// * Accesses to emulate PHI nodes
+  /// * Accesses to emulate PHI nodes within the SCoP
   ///
   /// PHIInst instructions such as
   ///
   /// %PHI = phi float [ %Val1, %IncomingBlock1 ], [ %Val2, %IncomingBlock2 ]
   ///
   /// are modeled as if the accesses occured this way:
   ///
   ///                    _______________________________
public:
   /// #AccessInst of a load is the PHIInst and a incoming block's terminator for
   /// stores. The #BaseAddr is represented through the PHINode because there
   /// also such alloca in the analyzed code. The #AccessValue is represented by
   /// the PHIInst itself.
   ///
   /// Note that there can also be a scalar write access for %PHI if used in a
   /// different BasicBlock, i.e. there can be a %PHI.phiops as well as a
   /// %PHI.s2a.
-  enum AccessOrigin { EXPLICIT, SCALAR, PHI };
+  ///
+  ///
+  /// * Accesses to emulate PHI nodes that are in the SCoP's exit block
+  ///
+  /// Like the previous, but the PHI itself is not located in the SCoP itself.
+  /// There will be no READ type MemoryAccess for such values. The PHINode's
+  /// llvm::Value is treated as a value escaping the SCoP. WRITE accesses write
+  /// directly to the escaping value's ".s2a" alloca.
+  enum AccessOrigin { EXPLICIT, SCALAR, PHI, EXIT_PHI };
 
   /// @brief The access type of a memory access
   ///
   /// There are three kind of access types:
   ///
   /// * A read access
   ///
   /// A certain set of memory locations are read and may be used for internal
public:
 
   /// @brief Whether this access represents a register access or models PHI
   /// nodes.
   bool isImplicit() const { return !isExplicit(); }
 
   /// @brief Is this MemoryAccess modeling special PHI node accesses?
   bool isPHI() const { return Origin == PHI; }
 
+  /// @brief Is this MemoryAccess modeling the accesses of a PHI node in the
+  /// SCoP's exit block?
+  bool isExitPHI() const { return Origin == EXIT_PHI; }
+
   /// @brief Get the statement that contains this memory access.
   ScopStmt *getStatement() const { return Statement; }
 
   /// @brief Get the reduction type of this access
   ReductionType getReductionType() const { return RedType; }
 
   /// @brief Set the updated access relation read from JSCOP file.
   void setNewAccessRelation(__isl_take isl_map *NewAccessRelation);

polly/trunk/lib/Analysis/ScopInfo.cpp

 
 void ScopStmt::buildAccessRelations() {
   for (MemoryAccess *Access : MemAccs) {
     Type *ElementType = Access->getAccessValue()->getType();
 
     ScopArrayInfo::ARRAYKIND Ty;
     if (Access->isPHI())
       Ty = ScopArrayInfo::KIND_PHI;
+    else if (Access->isExitPHI())
+      Ty = ScopArrayInfo::KIND_EXIT_PHI;
     else if (Access->isImplicit())
       Ty = ScopArrayInfo::KIND_SCALAR;
     else
       Ty = ScopArrayInfo::KIND_ARRAY;
 
     const ScopArrayInfo *SAI = getParent()->getOrCreateScopArrayInfo(
         Access->getBaseAddr(), ElementType, Access->Sizes, Ty);
 
addMemoryAccess(UserBB, User, MemoryAccess::READ, Value, 1, true, Value,
                   ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                   MemoryAccess::SCALAR);
 }
 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 *>(),
-                  IsExitBlock ? MemoryAccess::SCALAR : MemoryAccess::PHI);
+                  IsExitBlock ? MemoryAccess::EXIT_PHI : MemoryAccess::PHI);
 }
 void ScopInfo::addPHIReadAccess(PHINode *PHI) {
   addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
                   ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                   MemoryAccess::PHI);
 }
 
 void ScopInfo::buildScop(Region &R, DominatorTree &DT, AssumptionCache &AC) {

polly/trunk/lib/CodeGen/BlockGenerators.cpp

for (MemoryAccess *MA : Stmt) {
 
     // In case we add the store into an exiting block, we need to restore the
     // position for stores in the exit node.
     BasicBlock *SavedInsertBB = Builder.GetInsertBlock();
     auto SavedInsertionPoint = Builder.GetInsertPoint();
     ValueMapT *LocalBBMap = &BBMap;
 
     // Implicit writes induced by PHIs must be written in the incoming blocks.
-    if (isa<TerminatorInst>(ScalarInst)) {
+    if (MA->isPHI() || MA->isExitPHI()) {
       BasicBlock *ExitingBB = ScalarInst->getParent();
       BasicBlock *ExitingBBCopy = BlockMap[ExitingBB];
       Builder.SetInsertPoint(ExitingBBCopy->getTerminator());
 
       // For the incoming blocks, use the block's BBMap instead of the one for
       // the entire region.
       LocalBBMap = &RegionMaps[ExitingBBCopy];
     }
 
     auto Address = getOrCreateAlloca(*MA);
 
     Val = getNewScalarValue(Val, R, Stmt, LTS, *LocalBBMap);
     Builder.CreateStore(Val, Address);
 
     // Restore the insertion point if necessary.
-    if (isa<TerminatorInst>(ScalarInst))
+    if (MA->isPHI() || MA->isExitPHI())
       Builder.SetInsertPoint(SavedInsertBB, SavedInsertionPoint);
   }
 }
 
 void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, const PHINode *PHI,
                                       PHINode *PHICopy, BasicBlock *IncomingBB,
                                       LoopToScevMapT &LTS) {
   Region *StmtR = Stmt.getRegion();