Allow PHI nodes in the exit block of regions

[jdoerfert]

Summary

A codegen approach

[Meinersbur]

It's basically like my solution: Ensure that TempScopInfo generates write accesses and that BlockGenerators adds the PHIs to EscapeMap.

lib/Analysis/TempScopInfo.cpp

113

What happens otherwise?

485

if (!R.getExitingBlock())

lib/CodeGen/BlockGenerators.cpp

490

assert(!OperandPHI)

494

assert(OperandPHI);

505

Is this necessary? Can't one just use the original PHI to represent the virtual memory location? It's not directly used anyway.

506

escape

1158

The last 30 lines are repetative. Refactor?

[jdoerfert]

I will push another version later.

The problematic part I encountered are PHI nodes that use values as operands. Here I tried to circumvent them by looking through the new PHI node in the exit and replacing it dynamically with the one that is now in the region [BlockGenerators.cpp:529]. However, I don't like this solution so I came up with a different one I will push here.

lib/Analysis/TempScopInfo.cpp

113

The PHI operands are not modeled, hence never stored into the escape location.

485

True.

lib/CodeGen/BlockGenerators.cpp

505

I don't think so as it is linked via the escape map to the rewiring at the end.

1158

That might be an idea for a different patch though.

[jdoerfert]

• Remove trivial condition
• Allow values to cause memory accesses
• Allow PHI nodes in the region exit block

[grosser]

Hi Johannes,

can you rebase this to get rid of the AccessVal changes?

[jdoerfert]

Rebase to upstream with only the actuall commit in the diff

[jdoerfert]

This patch fails only the pairalign lnt execution test.

@Meinersbur Does your patch pass that one? If so can you rebase your patch to the upstram I want to see the difference in the generated L__align11 function that is apperently wrong.

[jdoerfert]

Rebased and working version

include/polly/CodeGen/BlockGenerators.h

protected:
   virtual void generateScalarStores(ScopStmt &Stmt, BasicBlock *BB,
                                     ValueMapT &BBMAp, ValueMapT &GlobalMap);
 
   /// @brief Handle users of @p Inst outside the SCoP.
   ///
   /// @param R        The current SCoP region.
   /// @param Inst     The current instruction we check.
   /// @param InstCopy The copy of the instruction @p Inst in the optimized SCoP.
-  void handleOutsideUsers(const Region &R, Instruction *Inst, Value *InstCopy);
+  /// @param Address  If given it is used as the escape address for @p Inst.
+  void handleOutsideUsers(const Region &R, Instruction *Inst, Value *InstCopy,
+                          AllocaInst *Address = nullptr);
 
   /// @brief Initialize the memory of demoted scalars.
   ///
   /// If a PHI node was demoted and one of its predecessor blocks was outside
   /// the SCoP we need to initialize the memory cell we demoted the PHI into
   /// with the value corresponding to that predecessor. As a SCoP is a
   /// __single__ entry region there is at most one such predecessor.
   void createScalarInitialization(Region &R, ValueMapT &VMap);

include/polly/ScopDetection.h

private:
 
   /// @brief Check if all basic block in the region are valid.
   ///
   /// @param Context The context of scop detection.
   ///
   /// @return True if all blocks in R are valid, false otherwise.
   bool allBlocksValid(DetectionContext &Context) const;
 
-  /// @brief Check the exit block of a region is valid.
-  ///
-  /// @param Context The context of scop detection.
-  ///
-  /// @return True if the exit of R is valid, false otherwise.
-  bool isValidExit(DetectionContext &Context) const;
-
   /// @brief Check if a region is a Scop.
   ///
   /// @param Context The context of scop detection.
   ///
   /// @return True if R is a Scop, false otherwise.
   bool isValidRegion(DetectionContext &Context) const;
 
   /// @brief Check if a call instruction can be part of a Scop.

include/polly/ScopInfo.h

private:
   ScalarEvolution *SE;
 
   /// The underlying Region.
   Region &R;
 
   /// Flag to indicate that the scheduler actually optimized the SCoP.
   bool IsOptimized;
 
+  /// @brief True if the underlying region has a single exiting block.
+  bool HasSingleExitEdge;
+
   /// Max loop depth.
   unsigned MaxLoopDepth;
 
   typedef std::deque<ScopStmt> StmtSet;
   /// The statements in this Scop.
   StmtSet Stmts;
 
   /// Parameters of this Scop
public:
   /// @param IsPHI   Are we looking for special PHI storage.
   const ScopArrayInfo *getScopArrayInfo(Value *BasePtr, bool IsPHI = false);
 
   void setContext(isl_set *NewContext);
 
   /// @brief Align the parameters in the statement to the scop context
   void realignParams();
 
+  /// @brief Return true if the underlying region has a single exiting block.
+  bool hasSingleExitEdge() const { return HasSingleExitEdge; }
+
   /// @brief Print the static control part.
   ///
   /// @param OS The output stream the static control part is printed to.
   void print(raw_ostream &OS) const;
 
   /// @brief Print the ScopStmt to stderr.
   void dump() const;
 

include/polly/TempScopInfo.h

bool buildScalarDependences(Instruction *Inst, Region *R,
                               Region *NonAffineSubRegio);
 
   /// @brief Create IRAccesses for the given PHI node in the given region.
   ///
   /// @param PHI                The PHI node to be handled
   /// @param R                  The SCoP region
   /// @param Functions          The access functions of the current BB
   /// @param NonAffineSubRegion The non affine sub-region @p PHI is in.
+  /// @param IsExitBlock        Flag to indicate that @p PHI is in the exit BB.
   void buildPHIAccesses(PHINode *PHI, Region &R, AccFuncSetType &Functions,
-                        Region *NonAffineSubRegion);
+                        Region *NonAffineSubRegion, bool IsExitBlock = false);
 
   /// @brief Build the access functions for the subregion @p SR.
   ///
   /// @param R  The SCoP region.
   /// @param SR A subregion of @p R.
   void buildAccessFunctions(Region &R, Region &SR);
 
   /// @brief Build the access functions for the basic block @p BB
   ///
   /// @param R                  The SCoP region.
   /// @param BB                 A basic block in @p R.
   /// @param NonAffineSubRegion The non affine sub-region @p BB is in.
+  /// @param IsExitBlock        Flag to indicate that @p BB is in the exit BB.
   void buildAccessFunctions(Region &R, BasicBlock &BB,
-                            Region *NonAffineSubRegion = nullptr);
+                            Region *NonAffineSubRegion = nullptr,
+                            bool IsExitBlock = false);
 
 public:
   static char ID;
   explicit TempScopInfo() : RegionPass(ID), TempScopOfRegion(nullptr) {}
   ~TempScopInfo();
 
   /// @brief Get the temporay Scop information in LLVM IR for this region.
   ///

lib/Analysis/ScopDetection.cpp

Region *ScopDetection::expandRegion(Region &R) {
 
   while (ExpandedRegion) {
     DetectionContext Context(
         *ExpandedRegion, *AA, NonAffineSubRegionMap[ExpandedRegion.get()],
         BoxedLoopsMap[ExpandedRegion.get()], false /* verifying */);
     DEBUG(dbgs() << "\t\tTrying " << ExpandedRegion->getNameStr() << "\n");
     // Only expand when we did not collect errors.
 
-    // Check the exit first (cheap)
-    if (isValidExit(Context) && !Context.Log.hasErrors()) {
+    if (!Context.Log.hasErrors()) {
       // If the exit is valid check all blocks
       //  - if true, a valid region was found => store it + keep expanding
       //  - if false, .tbd. => stop  (should this really end the loop?)
       if (!allBlocksValid(Context) || Context.Log.hasErrors())
         break;
 
       // Store this region, because it is the greatest valid (encountered so
       // far).
for (BasicBlock::iterator I = BB->begin(), E = --BB->end(); I != E; ++I)
         return false;
 
   if (!hasAffineMemoryAccesses(Context))
     return false;
 
   return true;
 }
 
-bool ScopDetection::isValidExit(DetectionContext &Context) const {
-
-  // PHI nodes are not allowed in the exit basic block.
-  if (BasicBlock *Exit = Context.CurRegion.getExit()) {
-    BasicBlock::iterator I = Exit->begin();
-    if (I != Exit->end() && isa<PHINode>(*I))
-      return invalid<ReportPHIinExit>(Context, /*Assert=*/true, I);
-  }
-
-  return true;
-}
-
 bool ScopDetection::isValidRegion(DetectionContext &Context) const {
   Region &CurRegion = Context.CurRegion;
 
   DEBUG(dbgs() << "Checking region: " << CurRegion.getNameStr() << "\n\t");
 
   if (CurRegion.isTopLevelRegion()) {
     DEBUG(dbgs() << "Top level region is invalid\n");
     return false;
bool ScopDetection::isValidRegion(DetectionContext &Context) const {
   }
 
   // SCoP cannot contain the entry block of the function, because we need
   // to insert alloca instruction there when translate scalar to array.
   if (CurRegion.getEntry() ==
       &(CurRegion.getEntry()->getParent()->getEntryBlock()))
     return invalid<ReportEntry>(Context, /*Assert=*/true, CurRegion.getEntry());
 
-  if (!isValidExit(Context))
-    return false;
-
   if (!allBlocksValid(Context))
     return false;
 
   // We can probably not do a lot on scops that only write or only read
   // data.
   if (!DetectUnprofitable && (!Context.hasStores || !Context.hasLoads))
     invalid<ReportUnprofitable>(Context, /*Assert=*/true, &CurRegion);
 

lib/Analysis/ScopInfo.cpp

static unsigned getMaxLoopDepthInRegion(const Region &R, LoopInfo &LI,
   assert(MaxLD >= MinLD &&
          "Maximal loop depth was smaller than mininaml loop depth?");
   return MaxLD - MinLD + 1;
 }
 
 Scop::Scop(Region &R, ScalarEvolution &ScalarEvolution, isl_ctx *Context,
            unsigned MaxLoopDepth)
     : SE(&ScalarEvolution), R(R), IsOptimized(false),
-      MaxLoopDepth(MaxLoopDepth), IslCtx(Context), Affinator(this) {}
+      HasSingleExitEdge(R.getExitingBlock()), MaxLoopDepth(MaxLoopDepth),
+      IslCtx(Context), Affinator(this) {}
 
 void Scop::initFromTempScop(TempScop &TempScop, LoopInfo &LI,
                             ScopDetection &SD) {
   buildContext();
 
   SmallVector<Loop *, 8> NestLoops;
 
   // Build the iteration domain, access functions and schedule functions

lib/Analysis/TempScopInfo.cpp

for (const auto &CurBlock : CurR->blocks()) {
     for (access_iterator AI = AccFuncs.begin(), AE = AccFuncs.end(); AI != AE;
          ++AI)
       AI->first.print(OS.indent(ind + 2));
   }
 }
 
 void TempScopInfo::buildPHIAccesses(PHINode *PHI, Region &R,
                                     AccFuncSetType &Functions,
-                                    Region *NonAffineSubRegion) {
-  if (canSynthesize(PHI, LI, SE, &R))
+                                    Region *NonAffineSubRegion,
+                                    bool IsExitBlock) {
+
+  // PHI nodes that are in the ExitBlock of the region, hence if IsExitBlock is
+  // true, are not modelt as ordinary PHI nodes as they are not part of the
+  // region. However, we model the operands in the predecessor blocks that are
+  // part of the region as regular scalar accesses.
+
+  // If we can synthesize a PHI we can skip it, however only if it is in
+  // the region. If it is not it can only be in the exit block of the region.
+  // In this case we model the operands but not the PHI itself.
+  if (PHI->getParent() != R.getExit() && canSynthesize(PHI, LI, SE, &R))
     return;
 
   // 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);
for (unsigned u = 0; u < PHI->getNumIncomingValues(); u++) {
     }
 
     // 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, Op,
-                          /* IsPHI */ true);
+                          /* IsPHI */ !IsExitBlock);
     AccFuncMap[OpBB].push_back(std::make_pair(ScalarAccess, OpI));
   }
 
   if (!OnlyNonAffineSubRegionOperands) {
     IRAccess ScalarAccess(IRAccess::READ, PHI, ZeroOffset, 1, true, PHI,
-                          /* IsPHI */ true);
+                          /* IsPHI */ !IsExitBlock);
     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 (isIgnoredIntrinsic(Inst))
void TempScopInfo::buildAccessFunctions(Region &R, Region &SR) {
   for (auto I = SR.element_begin(), E = SR.element_end(); I != E; ++I)
     if (I->isSubRegion())
       buildAccessFunctions(R, *I->getNodeAs<Region>());
     else
       buildAccessFunctions(R, *I->getNodeAs<BasicBlock>());
 }
 
 void TempScopInfo::buildAccessFunctions(Region &R, BasicBlock &BB,
-                                        Region *NonAffineSubRegion) {
+                                        Region *NonAffineSubRegion,
+                                        bool IsExitBlock) {
   AccFuncSetType Functions;
   Loop *L = LI->getLoopFor(&BB);
 
   // The set of loops contained in non-affine subregions that are part of R.
   const ScopDetection::BoxedLoopsSetTy *BoxedLoops = SD->getBoxedLoops(&R);
 
   for (BasicBlock::iterator I = BB.begin(), E = --BB.end(); I != E; ++I) {
     Instruction *Inst = I;
+
+    PHINode *PHI = dyn_cast<PHINode>(Inst);
+    if (PHI)
+      buildPHIAccesses(PHI, R, Functions, NonAffineSubRegion, IsExitBlock);
+
+    // For the exit block we stop modeling after the last PHI node.
+    if (!PHI && IsExitBlock)
+      break;
+
     if (isa<LoadInst>(Inst) || isa<StoreInst>(Inst))
       Functions.push_back(
           std::make_pair(buildIRAccess(Inst, L, &R, BoxedLoops), Inst));
 
-    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,
                             Inst);
       Functions.push_back(std::make_pair(ScalarAccess, Inst));
     }
if (!Cond.empty())
     BBConds[BB] = Cond;
 }
 
 TempScop *TempScopInfo::buildTempScop(Region &R) {
   TempScop *TScop = new TempScop(R, BBConds, AccFuncMap);
 
   buildAccessFunctions(R, R);
 
+  // In case the region does not have an exiting block we will later (during
+  // code generation) split the exit block. This will move potential PHI nodes
+  // in the exit block into the region that are at this point not part of it.
+  // To handle these PHI nodes later on we will model their operands as scalar
+  // accesses. Note that we do not model anything in the exit block if we have
+  // a exiting block in the region, hence there will not be any splitting later.
+  if (!R.getExitingBlock())
+    buildAccessFunctions(R, *R.getExit(), nullptr, /* IsExitBlock */ true);
+
   for (const auto &BB : R.blocks())
     buildCondition(BB, R);
 
   return TScop;
 }
 
 TempScop *TempScopInfo::getTempScop() const { return TempScopOfRegion; }
 

lib/CodeGen/BlockGenerators.cpp

if (!Addr) {
     Addr = new AllocaInst(Ty, ScalarBase->getName() + NameExt);
     Addr->insertBefore(EntryBB->getFirstInsertionPt());
   }
 
   return Addr;
 }
 
 void BlockGenerator::handleOutsideUsers(const Region &R, Instruction *Inst,
-                                        Value *InstCopy) {
+                                        Value *InstCopy, AllocaInst *Address) {
 
   EscapeUserVectorTy EscapeUsers;
   for (User *U : Inst->users()) {
 
     // Non-instruction user will never escape.
     Instruction *UI = dyn_cast<Instruction>(U);
     if (!UI)
       continue;
void BlockGenerator::handleOutsideUsers(const Region &R, Instruction *Inst,
   // it in the EscapeMap for later finalization. However, if the alloca was not
   // created by an already handled scalar dependence we have to initialize it
   // also. Lastly, if the instruction was copied multiple times we already did
   // this and can exit.
   if (EscapeMap.count(Inst))
     return;
 
   // Get or create an escape alloca for this instruction.
-  bool IsNew;
-  AllocaInst *ScalarAddr =
-      getOrCreateAlloca(Inst, ScalarMap, ".escape", &IsNew);
+  bool IsNew = false;
+  if (!Address)
+    Address = getOrCreateAlloca(Inst, ScalarMap, ".escape", &IsNew);
 
   // Remember that this instruction has escape uses and the escape alloca.
-  EscapeMap[Inst] = std::make_pair(ScalarAddr, std::move(EscapeUsers));
+  EscapeMap[Inst] = std::make_pair(Address, std::move(EscapeUsers));
 
   // If the escape alloca was just created store the instruction in there,
   // otherwise that happened already.
   if (IsNew) {
     assert(InstCopy && "Except PHIs every instruction should have a copy!");
-    Builder.CreateStore(InstCopy, ScalarAddr);
+    Builder.CreateStore(InstCopy, Address);
   }
 }
 
 void BlockGenerator::generateScalarLoads(ScopStmt &Stmt,
                                          const Instruction *Inst,
                                          ValueMapT &BBMap) {
   auto *MAL = Stmt.lookupAccessesFor(Inst);
 

 
 void BlockGenerator::generateScalarStores(ScopStmt &Stmt, BasicBlock *BB,
                                           ValueMapT &BBMap,
                                           ValueMapT &GlobalMap) {
   const Region &R = Stmt.getParent()->getRegion();
 
   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());
     Value *Val = MA->getAccessValue();
 
     AllocaInst *Address = nullptr;
     if (MA->getScopArrayInfo()->isPHI())
       Address = getOrCreateAlloca(Base, PHIOpMap, ".phiops");
     else
       Address = getOrCreateAlloca(Base, ScalarMap, ".s2a");
 
     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.
   BasicBlock *SplitBB = R.getEnteringBlock();
   BranchInst *SplitBBTerm = cast<BranchInst>(SplitBB->getTerminator());
for (const auto &EscapeMapping : EscapeMap) {
 
     // Replace all uses of the demoted instruction with the merge PHI.
     for (Instruction *EUser : EscapeUsers)
       EUser->replaceUsesOfWith(EscapeInst, MergePHI);
   }
 }
 
 void BlockGenerator::finalizeSCoP(Scop &S, ValueMapT &GlobalMap) {
+
+  // Handle PHI nodes that were in the original exit and are now
+  // moved into the region exiting block.
+  if (!S.hasSingleExitEdge()) {
+    for (Instruction &I : *S.getRegion().getExitingBlock()) {
+      PHINode *PHI = dyn_cast<PHINode>(&I);
+      if (!PHI)
+        break;
+
+      assert(PHI->getNumUses() == 1);
+      assert(ScalarMap.count(PHI->user_back()));
+
+      AllocaInst *Address = ScalarMap[PHI->user_back()];
+      handleOutsideUsers(S.getRegion(), PHI, nullptr, Address);
+    }
+  }
+
   createScalarInitialization(S.getRegion(), GlobalMap);
   createScalarFinalization(S.getRegion());
 }
 
 VectorBlockGenerator::VectorBlockGenerator(BlockGenerator &BlockGen,
                                            VectorValueMapT &GlobalMaps,
                                            std::vector<LoopToScevMapT> &VLTS,
                                            isl_map *Schedule)
for (MemoryAccess *MA : Stmt) {
     Builder.CreateStore(Val, ScalarAddr);
   }
 }
 
 void RegionGenerator::addOperandToPHI(ScopStmt &Stmt, const PHINode *PHI,
                                       PHINode *PHICopy, BasicBlock *IncomingBB,
                                       ValueMapT &GlobalMap,
                                       LoopToScevMapT &LTS) {
   Region *StmtR = Stmt.getRegion();
 
   // If the incoming block was not yet copied mark this PHI as incomplete.
   // Once the block will be copied the incoming value will be added.
   BasicBlock *BBCopy = BlockMap[IncomingBB];
   if (!BBCopy) {
     assert(StmtR->contains(IncomingBB) &&
            "Bad incoming block for PHI in non-affine region");
     IncompletePHINodeMap[IncomingBB].push_back(std::make_pair(PHI, PHICopy));