[Polly][ScopBuilder] Prefer PHI Write accesses in the statement the incoming value is defined.

[Meinersbur]

Summary

Theoretically, a PHI write can be added to any statement that represents the incoming basic block. We previously always chose the last because the incoming value's definition is guaranteed to be defined.

With this patch the PHI write is added to the statement that defines the incoming value. It avoids the requirement for a scalar dependency between the defining statement and the statement containing the write. As such the logic for -polly-stmt-granularity=scalar-indep that ensures that there is such scalar dependencies can be removed.

[grosser]

Hi Michael,

this looks generally good. However, did you find an actual use case where this improves the code?

Best,
Tobias

[Meinersbur]

• Rebase

[Meinersbur]

Program                                                                        leone_F30_statementnaming_indep  leone_G30_epilogue_indep diff

 MultiSource/Benchmarks/DOE-ProxyApps-C++/HACCKernels/HACCKernels              0.812                            0.329                     -59.5%
 Performance/Polybench-32/linear-algebra/kernels/symm/Pb32-perf_symm           5.931                            2.813                     -52.6%
 Polybench/Polybench-421/linear-algebra/blas/symm/P421_symm                    1.792                            1.115                     -37.8%
 SingleSource/Benchmarks/Misc/flops                                            6.308                            4.300                     -31.8%
 Performance/Polybench-421/linear-algebra/blas/symm/Pb421-perf_symm            1.545                            1.111                     -28.1%
 Polybench/Polybench-32/linear-algebra/kernels/symm/P32_symm                   6.030                            4.560                     -24.4%
 SingleSource/Benchmarks/Polybench/linear-algebra/kernels/symm/symm           12.032                            9.293                     -22.8%
 SingleSource/Benchmarks/Polybench/stencils/fdtd-apml/fdtd-apml                0.464                            0.540                      16.4%
 MultiSource/Benchmarks/TSVC/Symbolics-flt/Symbolics-flt                       0.867                            0.785                      -9.5%
 MultiSource/Benchmarks/TSVC/Symbolics-dbl/Symbolics-dbl                       2.209                            2.392                       8.3%
 SingleSource/Benchmarks/CoyoteBench/almabench                                 9.829                            9.170                      -6.7%
 Polybench/Polybench-421/linear-algebra/blas/symm/P421r_symm                   1.659                            1.559                      -6.0%

I am somewhat suprised by this positive result. I made the patch primarily because it simplifies the equivalence class code and estimated that too many coincidences had to occur before it had an effect on the rescheduler. Since improvement it consistent, I assume it is not just caused by different statement names.

[grosser]

Nice!

polly/trunk/include/polly/ScopInfo.h

public:
   std::string getAssumedContextStr() const;
 
   /// Get an isl string representing the invalid context.
   std::string getInvalidContextStr() const;
 
   /// Return the list of ScopStmts that represent the given @p BB.
   ArrayRef<ScopStmt *> getStmtListFor(BasicBlock *BB) const;
 
+  /// Get the statement to put a PHI WRITE into.
+  ///
+  /// @param U The operand of a PHINode.
+  ScopStmt *getIncomingStmtFor(const Use &U) const;
+
   /// Return the last statement representing @p BB.
   ///
   /// Of the sequence of statements that represent a @p BB, this is the last one
   /// to be executed. It is typically used to determine which instruction to add
   /// a MemoryKind::PHI WRITE to. For this purpose, it is not strictly required
   /// to be executed last, only that the incoming value is available in it.
   ScopStmt *getLastStmtFor(BasicBlock *BB) const;
 

polly/trunk/lib/Analysis/ScopBuilder.cpp

void ScopBuilder::buildPHIAccesses(ScopStmt *PHIStmt, PHINode *PHI,
 
   // PHI nodes are modeled as if they had been demoted prior to the SCoP
   // detection. Hence, the PHI is a load of a new memory location in which the
   // incoming value was written at the end of the incoming basic block.
   bool OnlyNonAffineSubRegionOperands = true;
   for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
     Value *Op = PHI->getIncomingValue(u);
     BasicBlock *OpBB = PHI->getIncomingBlock(u);
-    ScopStmt *OpStmt = scop->getLastStmtFor(OpBB);
+    ScopStmt *OpStmt = scop->getIncomingStmtFor(PHI->getOperandUse(u));
 
     // Do not build PHI dependences inside a non-affine subregion, but make
     // sure that the necessary scalar values are still made available.
     if (NonAffineSubRegion && NonAffineSubRegion->contains(OpBB)) {
       auto *OpInst = dyn_cast<Instruction>(Op);
       if (!OpInst || !NonAffineSubRegion->contains(OpInst))
         ensureValueRead(Op, OpStmt);
       continue;

 
 /// Generate a name for a statement.
 ///
 /// @param BB     The basic block the statement will represent.
 /// @param BBIdx  The index of the @p BB relative to other BBs/regions.
 /// @param Count  The index of the created statement in @p BB.
 /// @param IsMain Whether this is the main of all statement for @p BB. If true,
 ///               no suffix will be added.
+/// @param IsLast Uses a special indicator for the last statement of a BB.
 static std::string makeStmtName(BasicBlock *BB, long BBIdx, int Count,
-                                bool IsMain) {
+                                bool IsMain, bool IsLast = false) {
   std::string Suffix;
   if (!IsMain) {
     if (UseInstructionNames)
       Suffix = '_';
-    if (Count < 26)
+    if (IsLast)
+      Suffix += "last";
+    else if (Count < 26)
       Suffix += 'a' + Count;
     else
       Suffix += std::to_string(Count);
   }
   return getIslCompatibleName("Stmt", BB, BBIdx, Suffix, UseInstructionNames);
 }
 
 /// Generate a name for a statement that represents a non-affine subregion.
for (Use &Op : Inst->operands()) {
       if (OpVal == UnionFind.end())
         continue;
 
       UnionFind.unionSets(Inst, OpInst);
     }
   }
 }
 
-/// Join instructions that are used as incoming value in successor PHIs into the
-/// epilogue.
-static void
-joinIncomingPHIValuesIntoEpilogue(EquivalenceClasses<Instruction *> &UnionFind,
-                                  ArrayRef<Instruction *> ModeledInsts,
-                                  BasicBlock *BB) {
-  for (BasicBlock *Succ : successors(BB)) {
-    for (Instruction &SuccInst : *Succ) {
-      PHINode *SuccPHI = dyn_cast<PHINode>(&SuccInst);
-      if (!SuccPHI)
-        break;
-
-      Value *IncomingVal = SuccPHI->getIncomingValueForBlock(BB);
-      Instruction *IncomingInst = dyn_cast<Instruction>(IncomingVal);
-      if (!IncomingInst)
-        continue;
-      if (IncomingInst->getParent() != BB)
-        continue;
-      if (UnionFind.findValue(IncomingInst) == UnionFind.end())
-        continue;
-
-      UnionFind.unionSets(nullptr, IncomingInst);
-    }
-  }
-}
-
 /// Ensure that the order of ordered instructions does not change.
 ///
 /// If we encounter an ordered instruction enclosed in instructions belonging to
 /// a different statement (which might as well contain ordered instructions, but
 /// this is not tested here), join them.
 static void
 joinOrderedInstructions(EquivalenceClasses<Instruction *> &UnionFind,
                         ArrayRef<Instruction *> ModeledInsts) {
for (Instruction *Prev : reverse(SeenLeaders)) {
       Instruction *PrevLeader = UnionFind.getLeaderValue(SeenLeaders.back());
       if (PrevLeader == Leader)
         break;
       UnionFind.unionSets(Prev, Leader);
     }
   }
 }
 
-/// Also ensure that the epilogue is the last statement relative to all ordered
-/// instructions.
-///
-/// This is basically joinOrderedInstructions() but using the epilogue as
-/// 'ordered instruction'.
-static void joinAllAfterEpilogue(EquivalenceClasses<Instruction *> &UnionFind,
-                                 ArrayRef<Instruction *> ModeledInsts) {
-  bool EpilogueSeen = false;
-  for (Instruction *Inst : ModeledInsts) {
-    auto PHIWritesLeader = UnionFind.findLeader(nullptr);
-    auto InstLeader = UnionFind.findLeader(Inst);
-
-    if (PHIWritesLeader == InstLeader)
-      EpilogueSeen = true;
-
-    if (!isOrderedInstruction(Inst))
-      continue;
-
-    if (EpilogueSeen)
-      UnionFind.unionSets(PHIWritesLeader, InstLeader);
-  }
-}
-
 void ScopBuilder::buildEqivClassBlockStmts(BasicBlock *BB) {
   Loop *L = LI.getLoopFor(BB);
 
   // Extracting out modeled instructions saves us from checking
   // shouldModelInst() repeatedly.
   SmallVector<Instruction *, 32> ModeledInsts;
   EquivalenceClasses<Instruction *> UnionFind;
   Instruction *MainInst = nullptr;
   for (Instruction &Inst : *BB) {
     if (!shouldModelInst(&Inst, L))
       continue;
     ModeledInsts.push_back(&Inst);
     UnionFind.insert(&Inst);
 
     // When a BB is split into multiple statements, the main statement is the
     // one containing the 'main' instruction. We select the first instruction
     // that is unlikely to be removed (because it has side-effects) as the main
     // one. It is used to ensure that at least one statement from the bb has the
     // same name as with -polly-stmt-granularity=bb.
     if (!MainInst && (isa<StoreInst>(Inst) ||
                       (isa<CallInst>(Inst) && !isa<IntrinsicInst>(Inst))))
       MainInst = &Inst;
   }
 
-  // 'nullptr' represents the last statement for a basic block. It contains no
-  // instructions, but holds the PHI write accesses for successor basic blocks.
-  // If a PHI has an incoming value defined in this BB, it can also be merged
-  // with other statements.
-  // TODO: We wouldn't need this if we would add PHIWrites into the statement
-  // that defines the incoming value (if in the BB) instead of always the last,
-  // so we could unconditionally always add a last statement.
-  UnionFind.insert(nullptr);
-
   joinOperandTree(UnionFind, ModeledInsts);
-  joinIncomingPHIValuesIntoEpilogue(UnionFind, ModeledInsts, BB);
   joinOrderedInstructions(UnionFind, ModeledInsts);
-  joinAllAfterEpilogue(UnionFind, ModeledInsts);
 
   // The list of instructions for statement (statement represented by the leader
   // instruction). The order of statements instructions is reversed such that
   // the epilogue is first. This makes it easier to ensure that the epilogue is
   // the last statement.
   MapVector<Instruction *, std::vector<Instruction *>> LeaderToInstList;
 
-  // Ensure that the epilogue is last.
-  LeaderToInstList[nullptr];
-
   // Collect the instructions of all leaders. UnionFind's member iterator
   // unfortunately are not in any specific order.
   for (Instruction &Inst : reverse(*BB)) {
     auto LeaderIt = UnionFind.findLeader(&Inst);
     if (LeaderIt == UnionFind.member_end())
       continue;
 
     std::vector<Instruction *> &InstList = LeaderToInstList[*LeaderIt];
for (auto &Instructions : reverse(LeaderToInstList)) {
     else
       IsMain = (Count == 0);
 
     std::reverse(InstList.begin(), InstList.end());
     std::string Name = makeStmtName(BB, BBIdx, Count, IsMain);
     scop->addScopStmt(BB, Name, L, std::move(InstList));
     Count += 1;
   }
+
+  // Unconditionally add an epilogue (last statement). It contains no
+  // instructions, but holds the PHI write accesses for successor basic blocks,
+  // if the incoming value is not defined in another statement if the same BB.
+  // The epilogue will be removed if no PHIWrite is added to it.
+  std::string EpilogueName = makeStmtName(BB, BBIdx, Count, false, true);
+  scop->addScopStmt(BB, EpilogueName, L, {});
 }
 
 void ScopBuilder::buildStmts(Region &SR) {
   if (scop->isNonAffineSubRegion(&SR)) {
     std::vector<Instruction *> Instructions;
     Loop *SurroundingLoop =
         getFirstNonBoxedLoopFor(SR.getEntry(), LI, scop->getBoxedLoops());
     for (Instruction &Inst : *SR.getEntry())

polly/trunk/lib/Analysis/ScopInfo.cpp

 
 ArrayRef<ScopStmt *> Scop::getStmtListFor(BasicBlock *BB) const {
   auto StmtMapIt = StmtMap.find(BB);
   if (StmtMapIt == StmtMap.end())
     return {};
   return StmtMapIt->second;
 }
 
+ScopStmt *Scop::getIncomingStmtFor(const Use &U) const {
+  auto *PHI = cast<PHINode>(U.getUser());
+  BasicBlock *IncomingBB = PHI->getIncomingBlock(U);
+
+  // If the value is a non-synthesizable from the incoming block, use the
+  // statement that contains it as user statement.
+  if (auto *IncomingInst = dyn_cast<Instruction>(U.get())) {
+    if (IncomingInst->getParent() == IncomingBB) {
+      if (ScopStmt *IncomingStmt = getStmtFor(IncomingInst))
+        return IncomingStmt;
+    }
+  }
+
+  // Otherwise, use the epilogue/last statement.
+  return getLastStmtFor(IncomingBB);
+}
+
 ScopStmt *Scop::getLastStmtFor(BasicBlock *BB) const {
   ArrayRef<ScopStmt *> StmtList = getStmtListFor(BB);
   if (!StmtList.empty())
     return StmtList.back();
   return nullptr;
 }
 
 ArrayRef<ScopStmt *> Scop::getStmtListFor(RegionNode *RN) const {

polly/trunk/test/ScopInfo/granularity_scalar-indep_epilogue.ll

 ; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_A[0] };
 ; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_A[0] };
 ; CHECK-NEXT:         Instructions {
 ; CHECK-NEXT:             %valA = load double, double* %A
 ; CHECK-NEXT:             store double %valA, double* %A
 ; CHECK-NEXT:         }
-; CHECK-NEXT:     Stmt_bodyA_b
+; CHECK-NEXT:     Stmt_bodyA_last
 ; CHECK-NEXT:         Domain :=
-; CHECK-NEXT:             [n] -> { Stmt_bodyA_b[i0] : 0 <= i0 < n };
+; CHECK-NEXT:             [n] -> { Stmt_bodyA_last[i0] : 0 <= i0 < n };
 ; CHECK-NEXT:         Schedule :=
-; CHECK-NEXT:             [n] -> { Stmt_bodyA_b[i0] -> [i0, 1] };
+; CHECK-NEXT:             [n] -> { Stmt_bodyA_last[i0] -> [i0, 1] };
 ; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             [n] -> { Stmt_bodyA_b[i0] -> MemRef_phi__phi[] };
+; CHECK-NEXT:             [n] -> { Stmt_bodyA_last[i0] -> MemRef_phi__phi[] };
 ; CHECK-NEXT:         Instructions {
 ; CHECK-NEXT:         }
 ; CHECK-NEXT: }

polly/trunk/test/ScopInfo/granularity_scalar-indep_epilogue_last.ll

 ; RUN: opt %loadPolly -polly-stmt-granularity=scalar-indep -polly-print-instructions -polly-scops -analyze < %s | FileCheck %s -match-full-lines
 ;
-; Check that the statement where the PHI writes are in always comes last.
-; Otherwise we'd need to introduce a scalar dependency from the statement
-; defining a value to the last statement of a basic block.
+; Check that the PHI Write of value that is defined in the same basic
+; block is in the statement where it is defined.
 ;
 ; for (int j = 0; j < n; j += 1) {
 ; bodyA:
 ;   double valA = A[0];
 ;   A[0] = valA;
 ;   double valB = B[0];
 ;   B[0] = valB;
 ;

 }
 
 
 ; CHECK:      Statements {
 ; CHECK-NEXT:     Stmt_bodyA
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] : 0 <= i0 < n };
 ; CHECK-NEXT:         Schedule :=
-; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> [i0] };
+; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> [i0, 0] };
 ; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_A[0] };
 ; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_A[0] };
-; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
-; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_B[0] };
-; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
-; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_B[0] };
 ; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             [n] -> { Stmt_bodyA[i0] -> MemRef_phi__phi[] };
 ; CHECK-NEXT:         Instructions {
 ; CHECK-NEXT:               %valA = load double, double* %A
 ; CHECK-NEXT:               store double %valA, double* %A
+; CHECK-NEXT:         }
+; CHECK-NEXT:     Stmt_bodyA_b
+; CHECK-NEXT:         Domain :=
+; CHECK-NEXT:             [n] -> { Stmt_bodyA_b[i0] : 0 <= i0 < n };
+; CHECK-NEXT:         Schedule :=
+; CHECK-NEXT:             [n] -> { Stmt_bodyA_b[i0] -> [i0, 1] };
+; CHECK-NEXT:         ReadAccess :=       [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_bodyA_b[i0] -> MemRef_B[0] };
+; CHECK-NEXT:         MustWriteAccess :=  [Reduction Type: NONE] [Scalar: 0]
+; CHECK-NEXT:             [n] -> { Stmt_bodyA_b[i0] -> MemRef_B[0] };
+; CHECK-NEXT:         Instructions {
 ; CHECK-NEXT:               %valB = load double, double* %B
 ; CHECK-NEXT:               store double %valB, double* %B
 ; CHECK-NEXT:         }
 ; CHECK-NEXT: }