[Polly] Unique phi write accesses

[Meinersbur]

Summary

Ensure that there is at most one phi write access per PHINode and ScopStmt. In particular, this would be possible for non-affine subregions with multiple exiting blocks. We replace multiple MAY_WRITE accesses by one MUST_WRITE access. The written value is constructed using a PHINode of all exiting blocks. The interpretation of the PHI WRITE's "accessed value" changed from the incoming value to the PHI like for PHI READs since there is no unique incoming value.

Because region simplification shuffles around PHI nodes -- particularly with exit node PHIs -- the PHINodes at analysis time does not always exist anymore in the code generation pass. We instead remember the incoming block/value pair in the MemoryAccess.

[grosser]

Hi Michael,

this patch looks good to me. I only had two minor comments specific to this patch and one comment regarding all test case changes in this as well as the read/write uniqueing patches.

LGTM, assuming comments are addressed.

Best
Tobias

include/polly/ScopInfo.h

612 ↗

(On Diff #43340)

reaching

lib/CodeGen/BlockGenerators.cpp

1248 ↗

(On Diff #43340)

It might be worth to move the "Create a PHI of all possible outgoing values of this subregion" functionality into its own function.

test/Isl/CodeGen/non-affine-phi-node-expansion-2.ll

13 ↗

(On Diff #43340)

It would be nice to convert this test case in an earlier commit to the 'CHECK-NEXT' style,
such that by removing the CHECK lines we actually know that the store won't be created any more. Some of the other test cases you modify already use the CHECK-NEXT style. For those just dropping the lines already ensures the lines never occur. If the CHECK-NEXT style would add a lot of code, you might want to add a CHECK-NOT line that verifies the store is not added any more. (Thought I prefer CHECK-NEXT style).

This comment holds for all test cases (where it applies) and possibly also for some of the earlier unique load/store patches.

20 ↗

(On Diff #43340)

CHECK-NEXT?

test/Isl/CodeGen/non-affine-phi-node-expansion-3.ll

34 ↗

(On Diff #43340)

CHECK-NEXT?

test/Isl/CodeGen/non-affine-phi-node-expansion-4.ll

38 ↗

(On Diff #43340)

CHECK-NEXT?

test/ScopInfo/NonAffine/non_affine_loop_used_later.ll

42 ↗

(On Diff #43340)

These test cases would also benefit from an (ahead-of-time) CHECK-NEXT conversion.

[grosser]

Hi Michael,

this commit as well as D15510 and D15483 seem to be ready to commit after your isl-0.16.1 test-case reformatting has taken place. Did you just not get to this or does anything block these commits? I am asking as the more patches we keep in flight the more likely we will run into conflicts or cause conflicts with other (newer patches). So if something is OK to go, I would suggest to push it out as soon as possible. If something is blocking these commits, it would be interesting to understand what it is.

Best,
Tobias

[Meinersbur]

D16522 was blocking this.

polly/trunk/include/polly/CodeGen/BlockGenerators.h

private:
   /// @param PHI        The original PHI we copy.
   /// @param PHICopy    The copy of @p PHI.
   /// @param IncomingBB An incoming block of @p PHI.
   /// @param LTS        A map from old loops to new induction variables as
   /// SCEVs.
   void addOperandToPHI(ScopStmt &Stmt, const PHINode *PHI, PHINode *PHICopy,
                        BasicBlock *IncomingBB, LoopToScevMapT &LTS);
 
+  /// @brief Create a PHI that combines the incoming values from all incoming
+  ///        blocks that are in the subregion.
+  ///
+  /// PHIs in the subregion's exit block can have incoming edges from within and
+  /// outside the subregion. This function combines the incoming values from
+  /// within the subregion to appear as if there is only one incoming edge from
+  /// the subregion (an additional exit block is created by RegionGenerator).
+  /// This is to avoid that a value is written to the .phiops location without
+  /// leaving the subregion because the exiting block as an edge back into the
+  /// subregion.
+  ///
+  /// @param MA    The WRITE of MK_PHI/MK_ExitPHI for a PHI in the subregion's
+  ///              exit block.
+  /// @param LTS   Virtual induction variable mapping.
+  /// @param BBMap A mapping from old values to their new values in this block.
+  /// @param L     Loop surrounding this region statement.
+  ///
+  /// @returns The constructed PHI node.
+  PHINode *buildExitPHI(MemoryAccess *MA, LoopToScevMapT &LTS, ValueMapT &BBMap,
+                        Loop *L);
+
+  /// @param Return the new value of a scalar write, creating a PHINode if
+  ///        necessary.
+  ///
+  /// @param MA    A scalar WRITE MemoryAccess.
+  /// @param LTS   Virtual induction variable mapping.
+  /// @param BBMap A mapping from old values to their new values in this block.
+  ///
+  /// @returns The effective value of @p MA's written value when leaving the
+  ///          subregion.
+  /// @see buildExitPHI
+  Value *getExitScalar(MemoryAccess *MA, LoopToScevMapT &LTS, ValueMapT &BBMap);
+
   /// @brief Generate the scalar stores for the given statement.
   ///
   /// After the statement @p Stmt was copied all inner-SCoP scalar dependences
   /// starting in @p Stmt (hence all scalar write accesses in @p Stmt) need to
   /// be demoted to memory.
   ///
   /// @param Stmt  The statement we generate code for.
   /// @param LTS   A mapping from loops virtual canonical induction variable to

polly/trunk/include/polly/ScopInfo.h

private:
   /// intruction.
   ///
   /// For memory accesses of kind MK_Value the access instruction of a load
   /// 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 Incoming block and value of a PHINode.
+  SmallVector<std::pair<BasicBlock *, Value *>, 4> Incoming;
+
   /// @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
-  ///    of the PHI node.
+  ///  - For accesses of kind MK_PHI or MK_ExitPHI it is the PHI node itself
+  ///    (for both, READ and WRITE accesses).
   ///
   AssertingVH<Value> AccessValue;
 
   /// @brief Are all the subscripts affine expression?
   bool IsAffine;
 
   /// @brief Subscript expression for each dimension.
   SmallVector<const SCEV *, 4> Subscripts;
public:
   /// @param BaseName   Name of the acessed array.
   MemoryAccess(ScopStmt *Stmt, Instruction *AccessInst, AccessType Type,
                Value *BaseAddress, unsigned ElemBytes, bool Affine,
                ArrayRef<const SCEV *> Subscripts, ArrayRef<const SCEV *> Sizes,
                Value *AccessValue, ScopArrayInfo::MemoryKind Kind,
                StringRef BaseName);
   ~MemoryAccess();
 
+  /// @brief Add a new incoming block/value pairs for this PHI/ExitPHI access.
+  ///
+  /// @param IncomingBlock The PHI's incoming block.
+  /// @param IncomingValue The value when reacing the PHI from the @p
+  ///                      IncomingBlock.
+  void addIncoming(BasicBlock *IncomingBlock, Value *IncomingValue) {
+    assert(isAnyPHIKind());
+    Incoming.emplace_back(std::make_pair(IncomingBlock, IncomingValue));
+  }
+
+  /// @brief Return the list of possible PHI/ExitPHI values.
+  ///
+  /// After code generation moves some PHIs around during region simplification,
+  /// we cannot reliably locate the original PHI node and its incoming values
+  /// anymore. For this reason we remember these explicitely for all PHI-kind
+  /// accesses.
+  ArrayRef<std::pair<BasicBlock *, Value *>> getIncoming() const {
+    assert(isAnyPHIKind());
+    return Incoming;
+  }
+
   /// @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; }
 
   /// @brief Is this a read memory access?
   bool isRead() const { return AccType == MemoryAccess::READ; }
public:
 
   /// @brief Is this MemoryAccess modeling special PHI node accesses?
   bool isPHIKind() const { return Kind == ScopArrayInfo::MK_PHI; }
 
   /// @brief Is this MemoryAccess modeling the accesses of a PHI node in the
   /// SCoP's exit block?
   bool isExitPHIKind() const { return Kind == ScopArrayInfo::MK_ExitPHI; }
 
+  /// @brief Does this access orginate from one of the two PHI types?
+  bool isAnyPHIKind() const { return isPHIKind() || isExitPHIKind(); }
+
   /// @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);
private:
   /// @brief The set of values defined elsewhere 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 Map from PHI nodes to its incoming value when coming from this
+  ///        statement.
+  ///
+  /// Non-affine subregions can have multiple exiting blocks that are incoming
+  /// blocks of the PHI nodes. This map ensures that there is only one write
+  /// operation for the complete subregion. A PHI selecting the relevant value
+  /// will be inserted.
+  DenseMap<PHINode *, MemoryAccess *> PHIWrites;
+
   //@}
 
   /// @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:
   }
 
   /// @brief Return the MemoryAccess that reloads a value, or nullptr if not
   ///        existing, respectively not yet added.
   MemoryAccess *lookupValueReadOf(Value *Inst) const {
     return ValueReads.lookup(Inst);
   }
 
+  /// @brief Return the PHI write MemoryAccess for the incoming values from any
+  ///        basic block in this ScopStmt, or nullptr if not existing,
+  ///        respectively not yet added.
+  MemoryAccess *lookupPHIWriteOf(PHINode *PHI) const {
+    assert(isBlockStmt() || R->getExit() == PHI->getParent());
+    return PHIWrites.lookup(PHI);
+  }
+
   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;
   }
 
   /// @brief Add @p Access to this statement's list of accesses.
class ScopInfo : public RegionPass {
   /// @param Type        The kind of access.
   /// @param BaseAddress The accessed array's base address.
   /// @param ElemBytes   Size of accessed array element.
   /// @param Affine      Whether all subscripts are affine expressions.
   /// @param AccessValue Value read or written.
   /// @param Subscripts  Access subscripts per dimension.
   /// @param Sizes       The array diminsion's sizes.
   /// @param Kind        The kind of memory accessed.
-  void addMemoryAccess(BasicBlock *BB, Instruction *Inst,
-                       MemoryAccess::AccessType Type, Value *BaseAddress,
-                       unsigned ElemBytes, bool Affine, Value *AccessValue,
+  ///
+  /// @return The created MemoryAccess, or nullptr if the access is not within
+  ///         the SCoP.
+  MemoryAccess *addMemoryAccess(BasicBlock *BB, Instruction *Inst,
+                                MemoryAccess::AccessType Type,
+                                Value *BaseAddress, unsigned ElemBytes,
+                                bool Affine, Value *AccessValue,
                                 ArrayRef<const SCEV *> Subscripts,
                                 ArrayRef<const SCEV *> Sizes,
                                 ScopArrayInfo::MemoryKind Kind);
 
   /// @brief Create a MemoryAccess that represents either a LoadInst or
   /// StoreInst.
   ///
   /// @param MemAccInst  The LoadInst or StoreInst.
   /// @param Type        The kind of access.
   /// @param BaseAddress The accessed array's base address.
   /// @param ElemBytes   Size of accessed array element.
class ScopInfo : public RegionPass {
   /// @param PHI           PHINode under consideration.
   /// @param IncomingBlock Some predecessor block.
   /// @param IncomingValue @p PHI's value when coming from @p IncomingBlock.
   /// @param IsExitBlock   When true, uses the .s2a alloca instead of the
   ///                      .phiops one. Required for values escaping through a
   ///                      PHINode in the SCoP region's exit block.
   /// @see addPHIReadAccess()
   /// @see ScopArrayInfo::MemoryKind
-  void addPHIWriteAccess(PHINode *PHI, BasicBlock *IncomingBlock,
-                         Value *IncomingValue, bool IsExitBlock);
+  void ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
 
   /// @brief Create a MemoryAccess for reading the value of a phi.
   ///
   /// The modeling assumes that all incoming blocks write their incoming value
   /// to the same location. Thus, this access will read the incoming block's
   /// value as instructed by this @p PHI.
   ///
   /// @param PHI PHINode under consideration; the READ access will be added
   /// here.
-  /// @see addPHIWriteAccess()
+  /// @see ensurePHIWrite()
   /// @see ScopArrayInfo::MemoryKind
   void addPHIReadAccess(PHINode *PHI);
 
 public:
   static char ID;
   explicit ScopInfo();
   ~ScopInfo();
 

polly/trunk/lib/Analysis/ScopInfo.cpp

if (Access->isArrayKind()) {
     assert(!ValueWrites.lookup(AccessVal));
 
     ValueWrites[AccessVal] = Access;
   } else if (Access->isValueKind() && Access->isRead()) {
     Value *AccessVal = Access->getAccessValue();
     assert(!ValueReads.lookup(AccessVal));
 
     ValueReads[AccessVal] = Access;
+  } else if (Access->isAnyPHIKind() && Access->isWrite()) {
+    PHINode *PHI = cast<PHINode>(Access->getBaseAddr());
+    assert(!PHIWrites.lookup(PHI));
+
+    PHIWrites[PHI] = Access;
   }
 
   MemAccs.push_back(Access);
 }
 
 void ScopStmt::realignParams() {
   for (MemoryAccess *MA : *this)
     MA->realignParams();
if (OpI) {
           scop->getStmtForBasicBlock(OpBB)) {
         ensureValueRead(OpI, OpBB);
         ensureValueWrite(OpI);
       }
     } else if (ModelReadOnlyScalars && !isa<Constant>(Op)) {
       ensureValueRead(Op, OpBB);
     }
 
-    addPHIWriteAccess(PHI, OpBB, Op, IsExitBlock);
+    ensurePHIWrite(PHI, OpBB, Op, IsExitBlock);
   }
 
   if (!OnlyNonAffineSubRegionOperands && !IsExitBlock) {
     addPHIReadAccess(PHI);
   }
 }
 
 bool ScopInfo::buildScalarDependences(Instruction *Inst, Region *R,
for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
 
     if (buildScalarDependences(Inst, &R, NonAffineSubRegion)) {
       if (!isa<StoreInst>(Inst))
         ensureValueWrite(Inst);
     }
   }
 }
 
-void ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
+MemoryAccess *ScopInfo::addMemoryAccess(BasicBlock *BB, Instruction *Inst,
                                         MemoryAccess::AccessType Type,
                                         Value *BaseAddress, unsigned ElemBytes,
                                         bool Affine, Value *AccessValue,
                                         ArrayRef<const SCEV *> Subscripts,
                                         ArrayRef<const SCEV *> Sizes,
                                         ScopArrayInfo::MemoryKind Kind) {
   ScopStmt *Stmt = scop->getStmtForBasicBlock(BB);
 
   // Do not create a memory access for anything not in the SCoP. It would be
   // ignored anyway.
   if (!Stmt)
-    return;
+    return nullptr;
 
   AccFuncSetType &AccList = AccFuncMap[BB];
   Value *BaseAddr = BaseAddress;
   std::string BaseName = getIslCompatibleName("MemRef_", BaseAddr, "");
 
   bool isKnownMustAccess = false;
 
   // Accesses in single-basic block statements are always excuted.
   if (Stmt->isBlockStmt())
     isKnownMustAccess = true;
 
   if (Stmt->isRegionStmt()) {
     // Accesses that dominate the exit block of a non-affine region are always
     // executed. In non-affine regions there may exist MK_Values that do not
     // dominate the exit. MK_Values will always dominate the exit and MK_PHIs
     // only if there is at most one PHI_WRITE in the non-affine region.
     if (DT->dominates(BB, Stmt->getRegion()->getExit()))
       isKnownMustAccess = true;
   }
 
+  // Non-affine PHI writes do not "happen" at a particular instruction, but
+  // after exiting the statement. Therefore they are guaranteed execute and
+  // overwrite the old value.
+  if (Kind == ScopArrayInfo::MK_PHI || Kind == ScopArrayInfo::MK_ExitPHI)
+    isKnownMustAccess = true;
+
   if (!isKnownMustAccess && Type == MemoryAccess::MUST_WRITE)
     Type = MemoryAccess::MAY_WRITE;
 
   AccList.emplace_back(Stmt, Inst, Type, BaseAddress, ElemBytes, Affine,
                        Subscripts, Sizes, AccessValue, Kind, BaseName);
   Stmt->addAccess(&AccList.back());
+  return &AccList.back();
 }
 
 void ScopInfo::addArrayAccess(Instruction *MemAccInst,
                               MemoryAccess::AccessType Type, Value *BaseAddress,
                               unsigned ElemBytes, bool IsAffine,
                               ArrayRef<const SCEV *> Subscripts,
                               ArrayRef<const SCEV *> Sizes,
                               Value *AccessValue) {
void ScopInfo::ensureValueRead(Value *Value, BasicBlock *UserBB) {
   // 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 *>(),
-                  IsExitBlock ? ScopArrayInfo::MK_ExitPHI
-                              : ScopArrayInfo::MK_PHI);
+void ScopInfo::ensurePHIWrite(PHINode *PHI, BasicBlock *IncomingBlock,
+  ScopStmt *IncomingStmt = scop->getStmtForBasicBlock(IncomingBlock);
+
+  // Do not add more than one MemoryAccess per PHINode and ScopStmt.
+  if (MemoryAccess *Acc = IncomingStmt->lookupPHIWriteOf(PHI)) {
+    assert(Acc->getAccessInstruction() == PHI);
+    Acc->addIncoming(IncomingBlock, IncomingValue);
+    return;
+  }
+
+  MemoryAccess *Acc = addMemoryAccess(
+      IncomingStmt->isBlockStmt() ? IncomingBlock
+                                  : IncomingStmt->getRegion()->getEntry(),
+      PHI, MemoryAccess::MUST_WRITE, PHI, 1, true, PHI,
+      IsExitBlock ? ScopArrayInfo::MK_ExitPHI : ScopArrayInfo::MK_PHI);
+  assert(Acc);
+  Acc->addIncoming(IncomingBlock, IncomingValue);
 }
 void ScopInfo::addPHIReadAccess(PHINode *PHI) {
   addMemoryAccess(PHI->getParent(), PHI, MemoryAccess::READ, PHI, 1, true, PHI,
                   ArrayRef<const SCEV *>(), ArrayRef<const SCEV *>(),
                   ScopArrayInfo::MK_PHI);
 }
 
 void ScopInfo::buildScop(Region &R, AssumptionCache &AC) {

polly/trunk/lib/CodeGen/BlockGenerators.cpp

assert(Stmt.isBlockStmt() && "Region statements need to use the "
                                "generateScalarStores() function in the "
                                "RegionGenerator");
 
   for (MemoryAccess *MA : Stmt) {
     if (MA->isArrayKind() || MA->isRead())
       continue;
 
     Value *Val = MA->getAccessValue();
+    if (MA->isAnyPHIKind()) {
+      assert(MA->getIncoming().size() >= 1 &&
+             "Block statements have exactly one exiting block, or multiple but "
+             "with same incoming block and value");
+      assert(std::all_of(MA->getIncoming().begin(), MA->getIncoming().end(),
+                         [&](std::pair<BasicBlock *, Value *> p) -> bool {
+                           return p.first == Stmt.getBasicBlock();
+                         }) &&
+             "Incoming block must be statement's block");
+      Val = MA->getIncoming()[0].second;
+    }
     auto *Address = getOrCreateAlloca(*MA);
 
     Val = getNewValue(Stmt, Val, BBMap, LTS, L);
     Builder.CreateStore(Val, Address);
   }
 }
 
 void BlockGenerator::createScalarInitialization(Scop &S) {
void RegionGenerator::copyStmt(ScopStmt &Stmt, LoopToScevMapT &LTS,
 
   // Write values visible to other statements.
   generateScalarStores(Stmt, LTS, ValueMap);
   BlockMap.clear();
   RegionMaps.clear();
   IncompletePHINodeMap.clear();
 }
 
-void RegionGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
-                                           ValueMapT &BBMap) {
-  assert(Stmt.getRegion() &&
-         "Block statements need to use the generateScalarStores() "
-         "function in the BlockGenerator");
+PHINode *RegionGenerator::buildExitPHI(MemoryAccess *MA, LoopToScevMapT &LTS,
+                                       ValueMapT &BBMap, Loop *L) {
+  ScopStmt *Stmt = MA->getStatement();
+  Region *SubR = Stmt->getRegion();
+  auto Incoming = MA->getIncoming();
+
+  PollyIRBuilder::InsertPointGuard IPGuard(Builder);
+  PHINode *OrigPHI = cast<PHINode>(MA->getAccessInstruction());
+  BasicBlock *NewSubregionExit = Builder.GetInsertBlock();
+
+  // This can happen if the subregion is simplified after the ScopStmts
+  // have been created; simplification happens as part of CodeGeneration.
+  if (OrigPHI->getParent() != SubR->getExit()) {
+    BasicBlock *FormerExit = SubR->getExitingBlock();
+    if (FormerExit)
+      NewSubregionExit = BlockMap.lookup(FormerExit);
+  }
+
+  PHINode *NewPHI = PHINode::Create(OrigPHI->getType(), Incoming.size(),
+                                    "polly." + OrigPHI->getName(),
+                                    NewSubregionExit->getFirstNonPHI());
+
+  // Add the incoming values to the PHI.
+  for (auto &Pair : Incoming) {
+    BasicBlock *OrigIncomingBlock = Pair.first;
+    BasicBlock *NewIncomingBlock = BlockMap.lookup(OrigIncomingBlock);
+    Builder.SetInsertPoint(NewIncomingBlock->getTerminator());
+    assert(RegionMaps.count(NewIncomingBlock));
+    ValueMapT *LocalBBMap = &RegionMaps[NewIncomingBlock];
+
+    Value *OrigIncomingValue = Pair.second;
+    Value *NewIncomingValue =
+        getNewValue(*Stmt, OrigIncomingValue, *LocalBBMap, LTS, L);
+    NewPHI->addIncoming(NewIncomingValue, NewIncomingBlock);
+  }
+
+  return NewPHI;
+}
+
+Value *RegionGenerator::getExitScalar(MemoryAccess *MA, LoopToScevMapT &LTS,
+  ScopStmt *Stmt = MA->getStatement();
 
   // TODO: Add some test cases that ensure this is really the right choice.
-  Loop *L = LI.getLoopFor(Stmt.getRegion()->getExit());
+  Loop *L = LI.getLoopFor(Stmt->getRegion()->getExit());
 
-  for (MemoryAccess *MA : Stmt) {
-    if (MA->isArrayKind() || MA->isRead())
-      continue;
+  if (MA->isAnyPHIKind()) {
+    auto Incoming = MA->getIncoming();
+    assert(!Incoming.empty() &&
+           "PHI WRITEs must have originate from at least one incoming block");
 
-    Instruction *ScalarInst = MA->getAccessInstruction();
-    Value *Val = MA->getAccessValue();
+    // If there is only one incoming value, we do not need to create a PHI.
+    if (Incoming.size() == 1) {
+      Value *OldVal = Incoming[0].second;
+      return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
+    }
 
-    // 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;
-
-    // Scalar writes induced by PHIs must be written in the incoming blocks.
-    if (MA->isPHIKind() || MA->isExitPHIKind()) {
-      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];
-    }
+    return buildExitPHI(MA, LTS, BBMap, L);
 
-    auto Address = getOrCreateAlloca(*MA);
+  // MK_Value accesses leaving the subregion must dominate the exit block; just
+  // pass the copied value
+  Value *OldVal = MA->getAccessValue();
+  return getNewValue(*Stmt, OldVal, BBMap, LTS, L);
+}
 
-    Val = getNewValue(Stmt, Val, *LocalBBMap, LTS, L);
-    Builder.CreateStore(Val, Address);
+void RegionGenerator::generateScalarStores(ScopStmt &Stmt, LoopToScevMapT &LTS,
+                                           ValueMapT &BBMap) {
+  assert(Stmt.getRegion() &&
+         "Block statements need to use the generateScalarStores() "
+         "function in the BlockGenerator");
+
+  for (MemoryAccess *MA : Stmt) {
+    if (MA->isArrayKind() || MA->isRead())
+      continue;
 
-    // Restore the insertion point if necessary.
-    if (MA->isPHIKind() || MA->isExitPHIKind())
-      Builder.SetInsertPoint(SavedInsertBB, SavedInsertionPoint);
+    Value *NewVal = getExitScalar(MA, LTS, BBMap);
+    Value *Address = getOrCreateAlloca(*MA);
+    Builder.CreateStore(NewVal, Address);
   }
 }
 
 void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, const PHINode *PHI,
                                       PHINode *PHICopy, BasicBlock *IncomingBB,
                                       LoopToScevMapT &LTS) {
   Region *StmtR = Stmt.getRegion();
 

polly/trunk/test/Isl/CodeGen/non-affine-phi-node-expansion-2.ll

 ; RUN: opt %loadPolly -polly-codegen \
 ; RUN:     -S < %s | FileCheck %s
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 
 ; CHECK: polly.stmt.bb3:                                   ; preds = %polly.stmt.bb3.entry
 ; CHECK:   %tmp6_p_scalar_ = load double, double* %arg1{{[0-9]*}}, !alias.scope !0, !noalias !2
 ; CHECK:   %p_tmp7 = fadd double 1.000000e+00, %tmp6_p_scalar_
 ; CHECK:   %p_tmp8 = fcmp olt double 1.400000e+01, %p_tmp7
 ; CHECK:   br i1 %p_tmp8, label %polly.stmt.bb9, label %polly.stmt.bb10
 
 ; CHECK: polly.stmt.bb9:                                   ; preds = %polly.stmt.bb3
-; CHECK:   store double 1.000000e+00, double* %tmp12.phiops
 ; CHECK:   br label %polly.stmt.bb11.exit
 
 ; CHECK: polly.stmt.bb10:                                  ; preds = %polly.stmt.bb3
-; CHECK:   store double 2.000000e+00, double* %tmp12.phiops
 ; CHECK:   br label %polly.stmt.bb11.exit
 
+; CHECK: polly.stmt.bb11.exit:                             ; preds = %polly.stmt.bb10, %polly.stmt.bb9
+; CHECK:   %polly.tmp12 = phi double [ 1.000000e+00, %polly.stmt.bb9 ], [ 2.000000e+00, %polly.stmt.bb10 ]
+; CHECK:   store double %polly.tmp12, double* %tmp12.phiops
 
 define void @hoge(i32 %arg, [1024 x double]* %arg1) {
 bb:
   br label %bb2
 
 bb2:                                              ; preds = %bb
   br label %bb3
 

polly/trunk/test/Isl/CodeGen/non-affine-phi-node-expansion-3.ll

loop:
   %val1 = fadd float 1.0, 2.0
   %val2 = fadd float 1.0, 2.0
   br i1 %cond0, label %branch1, label %backedge
 
 ; CHECK-LABEL: polly.stmt.loop:
 ; CHECK-NEXT: %p_val0 = fadd float 1.000000e+00, 2.000000e+00
 ; CHECK-NEXT: %p_val1 = fadd float 1.000000e+00, 2.000000e+00
 ; CHECK-NEXT: %p_val2 = fadd float 1.000000e+00, 2.000000e+00
-; CHECK-NEXT: store float %p_val0, float* %merge.phiops
 ; CHECK-NEXT: br i1
 
 branch1:
   br i1 %cond1, label %branch2, label %backedge
 
 ; CHECK-LABEL: polly.stmt.branch1:
-; CHECK-NEXT:    store float %p_val1, float* %merge.phiops
 ; CHECK-NEXT: br i1
 
 branch2:
   br label %backedge
 
 ; CHECK-LABEL: polly.stmt.branch2:
-; CHECK-NEXT:    store float %p_val2, float* %merge.phiops
 ; CHECK-NEXT:    br label
 
+; CHECK-LABEL: polly.stmt.backedge.exit:
+; CHECK:         %polly.merge = phi float [ %p_val0, %polly.stmt.loop ], [ %p_val1, %polly.stmt.branch1 ], [ %p_val2, %polly.stmt.branch2 ]
+
 backedge:
   %merge = phi float [%val0, %loop], [%val1, %branch1], [%val2, %branch2]
   %indvar.next = add i64 %indvar, 1
   store float %merge, float* %A
   %cmp = icmp sle i64 %indvar.next, 100
   br i1 %cmp, label %loop, label %exit
 
 exit:
   ret void
 }

polly/trunk/test/Isl/CodeGen/non-affine-phi-node-expansion-4.ll

 ; RUN: opt %loadPolly -polly-codegen \
 ; RUN:     -S < %s | FileCheck %s
 
 define void @foo(float* %A, i1 %cond0, i1 %cond1) {
 entry:
   br label %loop
 
 loop:
   %indvar = phi i64 [0, %entry], [%indvar.next, %backedge]
   %val0 = fadd float 1.0, 2.0
   %val1 = fadd float 1.0, 2.0
   br i1 %cond0, label %branch1, label %backedge
 
 ; CHECK-LABEL: polly.stmt.loop:
 ; CHECK-NEXT:    %p_val0 = fadd float 1.000000e+00, 2.000000e+00
 ; CHECK-NEXT:    %p_val1 = fadd float 1.000000e+00, 2.000000e+00
-; CHECK-NEXT:    store float %p_val0, float* %merge.phiops
 ; CHECK-NEXT:    br i1
 
 ; The interesting instruction here is %val2, which does not dominate the exit of
 ; the non-affine region. Care needs to be taken when code-generating this write.
 ; Specifically, at some point we modeled this scalar write, which we tried to
 ; code generate in the exit block of the non-affine region.
 branch1:
   %val2 = fadd float 1.0, 2.0
   br i1 %cond1, label %branch2, label %backedge
 
 ; CHECK-LABEL: polly.stmt.branch1:
 ; CHECK-NEXT:    %p_val2 = fadd float 1.000000e+00, 2.000000e+00
-; CHECK-NEXT:    store float %p_val1, float* %merge.phiops
 ; CHECK-NEXT:    br i1
 
 branch2:
   br label %backedge
 
 ; CHECK-LABEL: polly.stmt.branch2:
-; CHECK-NEXT:    store float %p_val2, float* %merge.phiops
 ; CHECK-NEXT:    br label
 
+; CHECK-LABEL: polly.stmt.backedge.exit:
+; CHECK:         %polly.merge = phi float [ %p_val0, %polly.stmt.loop ], [ %p_val1, %polly.stmt.branch1 ], [ %p_val2, %polly.stmt.branch2 ]
+
 backedge:
   %merge = phi float [%val0, %loop], [%val1, %branch1], [%val2, %branch2]
   %indvar.next = add i64 %indvar, 1
   store float %merge, float* %A
   %cmp = icmp sle i64 %indvar.next, 100
   br i1 %cmp, label %loop, label %exit
 
 exit:
   ret void
 }

polly/trunk/test/Isl/CodeGen/non-affine-region-exit-phi-incoming-synthesize.ll

 ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
 ;
 ; This caused the code generation to generate invalid code as the same BBMap was
 ; used for the whole non-affine region. When %add is synthesized for the
 ; incoming value of subregion_if first, the code for it was generated into
 ; subregion_if, but reused for the incoming value of subregion_exit, although it
 ; is not dominated by subregion_if.
 ;
 ; CHECK-LABEL: polly.stmt.subregion_entry:
 ; CHECK:         %[[R0:[0-9]*]] = add i32 %n, -2
-; CHECK:         store i32 %[[R0]], i32* %retval.s2a
 ;
 ; CHECK-LABEL: polly.stmt.subregion_if:
 ; CHECK:         %[[R1:[0-9]*]] = add i32 %n, -2
-; CHECK:         store i32 %[[R1]], i32* %retval.s2a
 ;
-; CHECK-LABEL: polly.stmt.polly.merge_new_and_old.exit:
-; CHECK:         load i32, i32* %retval.s2a
+; CHECK-LABEL: polly.stmt.subregion_exit.region_exiting:
+; CHECK:         %polly.retval = phi i32 [ %[[R1]], %polly.stmt.subregion_if ], [ %[[R0]], %polly.stmt.subregion_entry ]
 
 define i32 @func(i32 %n){
 entry:
   br label %subregion_entry
 
 subregion_entry:
   %add = add nsw i32 %n, -2
   %cmp = fcmp ogt float undef, undef

polly/trunk/test/Isl/CodeGen/pr25241.ll

 ; RUN: opt %loadPolly -polly-codegen -S < %s | FileCheck %s
 
 ; PR25241 (https://llvm.org/bugs/show_bug.cgi?id=25241)
 ; Ensure that synthesized values of a PHI node argument are generated in the
 ; incoming block, not in the PHI's block.
 
 ; CHECK-LABEL: polly.stmt.if.then.862:
 ; CHECK:         %[[R1:[0-9]+]] = add i32 %tmp, 1
-; CHECK:         store i32 %0, i32* %curr.3.s2a
 ; CHECK:         br label
 
+; CHECK-LABEL: polly.stmt.while.body.740.region_exiting:
+; CHECK:         %polly.curr.3 = phi i32 [ %[[R1]], %polly.stmt.if.then.862 ], [ undef, %polly.stmt.if.else.864 ]
+; CHECK:         br label %polly.stmt.polly.merge_new_and_old.exit
+
 ; CHECK-LABEL: polly.stmt.polly.merge_new_and_old.exit:
+; CHECK:         store i32 %polly.curr.3, i32* %curr.3.s2a
+; CHECK:         br label %polly.exiting
+
+; CHECK-LABEL: polly.exiting:
 ; CHECK:         %curr.3.ph.final_reload = load i32, i32* %curr.3.s2a
 ; CHECK:         br label
 
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Function Attrs: nounwind uwtable

polly/trunk/test/ScopInfo/NonAffine/non_affine_loop_used_later.ll

 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_A[i0] };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_A[i0] };
 ; CHECK-NEXT:         MayWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:             [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_A[i0] };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_smax[] };
-; CHECK-NEXT:         MayWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_j_2__phi[] };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_j_0[] };
-; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             [N] -> { Stmt_bb4__TO__bb18[i0] -> MemRef_j_2__phi[] };
 ; CHECK-NEXT:     Stmt_bb18
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             [N] -> { Stmt_bb18[i0] : 0 <= i0 < N };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             [N] -> { Stmt_bb18[i0] -> [i0, 2] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             [N] -> { Stmt_bb18[i0] -> MemRef_j_2[] };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]

polly/trunk/test/ScopInfo/intra-non-affine-stmt-phi-node.ll

 ; RUN: opt %loadPolly -polly-scops -analyze \
 ; RUN:     -S < %s | FileCheck %s
 
 ; CHECK:      Statements {
 ; CHECK-NEXT:     Stmt_loop__TO__backedge
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             { Stmt_loop__TO__backedge[i0] : 0 <= i0 <= 100 };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             { Stmt_loop__TO__backedge[i0] -> [i0, 0] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             { Stmt_loop__TO__backedge[i0] -> MemRef_merge__phi[] };
-; CHECK-NEXT:         MayWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             { Stmt_loop__TO__backedge[i0] -> MemRef_merge__phi[] };
-; CHECK-NEXT:         MayWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:             { Stmt_loop__TO__backedge[i0] -> MemRef_merge__phi[] };
 ; CHECK-NEXT:     Stmt_backedge
 ; CHECK-NEXT:         Domain :=
 ; CHECK-NEXT:             { Stmt_backedge[i0] : 0 <= i0 <= 100 };
 ; CHECK-NEXT:         Schedule :=
 ; CHECK-NEXT:             { Stmt_backedge[i0] -> [i0, 1] };
 ; CHECK-NEXT:         ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:             { Stmt_backedge[i0] -> MemRef_merge__phi[] };
 ; CHECK-NEXT:         MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]

polly/trunk/test/ScopInfo/non_affine_region_2.ll

 ; CHECK:       Statements {
 ; CHECK-NEXT:      Stmt_bb3__TO__bb18
 ; CHECK-NEXT:          Domain :=
 ; CHECK-NEXT:              { Stmt_bb3__TO__bb18[i0] : 0 <= i0 <= 1023 };
 ; CHECK-NEXT:          Schedule :=
 ; CHECK-NEXT:              { Stmt_bb3__TO__bb18[i0] -> [i0, 0] };
 ; CHECK-NEXT:          ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:              { Stmt_bb3__TO__bb18[i0] -> MemRef_A[i0] };
-; CHECK-NEXT:          MayWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:              { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK-NEXT:          MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:              { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK-NEXT:      Stmt_bb18
 ; CHECK-NEXT:          Domain :=
 ; CHECK-NEXT:              { Stmt_bb18[i0] : 0 <= i0 <= 1023 };
 ; CHECK-NEXT:          Schedule :=
 ; CHECK-NEXT:              { Stmt_bb18[i0] -> [i0, 1] };
 ; CHECK-NEXT:          ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]

polly/trunk/test/ScopInfo/non_affine_region_3.ll

 ; CHECK:       Statements {
 ; CHECK-NEXT:      Stmt_bb3__TO__bb18
 ; CHECK-NEXT:          Domain :=
 ; CHECK-NEXT:              { Stmt_bb3__TO__bb18[i0] : 0 <= i0 <= 1023 };
 ; CHECK-NEXT:          Schedule :=
 ; CHECK-NEXT:              { Stmt_bb3__TO__bb18[i0] -> [i0, 0] };
 ; CHECK-NEXT:          ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:              { Stmt_bb3__TO__bb18[i0] -> MemRef_A[i0] };
-; CHECK-NEXT:          MayWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:              { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
-; CHECK-NEXT:          MayWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
+; CHECK-NEXT:          MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:              { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK-NEXT:          ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:              { Stmt_bb3__TO__bb18[i0] -> MemRef_b[] };
-; CHECK-NEXT:          MayWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:              { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
-; CHECK-NEXT:          MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:              { Stmt_bb3__TO__bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK-NEXT:      Stmt_bb18
 ; CHECK-NEXT:          Domain :=
 ; CHECK-NEXT:              { Stmt_bb18[i0] : 0 <= i0 <= 1023 };
 ; CHECK-NEXT:          Schedule :=
 ; CHECK-NEXT:              { Stmt_bb18[i0] -> [i0, 1] };
 ; CHECK-NEXT:          ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:              { Stmt_bb18[i0] -> MemRef_x_2__phi[] };
 ; CHECK-NEXT:          MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 0]

polly/trunk/test/ScopInfo/non_affine_region_4.ll

 ; CHECK-NEXT:          Domain :=
 ; CHECK-NEXT:              { Stmt_bb2__TO__bb7[i0] : 0 <= i0 <= 1023 };
 ; CHECK-NEXT:          Schedule :=
 ; CHECK-NEXT:              { Stmt_bb2__TO__bb7[i0] -> [i0, 0] };
 ; CHECK-NEXT:          ReadAccess :=    [Reduction Type: NONE] [Scalar: 0]
 ; CHECK-NEXT:              { Stmt_bb2__TO__bb7[i0] -> MemRef_A[i0] };
 ; CHECK-NEXT:          MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:              { Stmt_bb2__TO__bb7[i0] -> MemRef_x[] };
-; CHECK-NEXT:          MayWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
-; CHECK-NEXT:              { Stmt_bb2__TO__bb7[i0] -> MemRef_y__phi[] };
 ; CHECK-NEXT:          MustWriteAccess :=    [Reduction Type: NONE] [Scalar: 1]
 ; CHECK-NEXT:              { Stmt_bb2__TO__bb7[i0] -> MemRef_y__phi[] };
 ; CHECK-NEXT:      Stmt_bb7
 ; CHECK-NEXT:          Domain :=
 ; CHECK-NEXT:              { Stmt_bb7[i0] : 0 <= i0 <= 1023 };
 ; CHECK-NEXT:          Schedule :=
 ; CHECK-NEXT:              { Stmt_bb7[i0] -> [i0, 1] };
 ; CHECK-NEXT:          ReadAccess :=    [Reduction Type: NONE] [Scalar: 1]