[Polly] Make CodeGeneration handle PHI nodes in exit block

[Meinersbur]

Summary

PHI nodes are moved into the region. This node has the identity of the previous exit node so the references in Scop/ScopStmt do not need to be updated.

Such PHI nodes cannot yet occur without changes upstream (ScopInfo, TempScopInfo, ScopDetection) which will follow.

[jdoerfert]

I do not understand the commit message, could you explain it to me or make it more verbose? Additionally I somehow missed the intention.

lib/CodeGen/CodeGeneration.cpp

105

There is a new range style loop for this pattern.

122

I'm not a fan of blocks only to enforce indention.

123

space missing and ExitBB instead of BB?

129

if there are multiple regions should we call setregionfor multiple times? Isn't only the first or the last call the right/important one?

133

I do not understand this part.

135

I thought there is a predessors function or something that hides the make range?

[Meinersbur]

This comment was removed by Meinersbur.

[Meinersbur]

Uploaded wrong diff previously

[Meinersbur]

Actually found the predecessors function

[jdoerfert]

Some more comments but I still do not understand the part starting at line 131 in lib/CodeGen/CodeGeneration.cpp.

lib/CodeGen/CodeGeneration.cpp

97

typo and format of the comment.

99

What does "keeps its identity" mean?

[Meinersbur]

Add splitBlockNonPredecessors that was once in D11867.
Style changes and incorporated comments.

[Meinersbur]

Merged into D11870

lib/CodeGen/CodeGeneration.cpp

99

memory address

135

There are not or at least I haven't seen them.

include/polly/Support/ScopHelper.h

 //===------ Support/ScopHelper.h -- Some Helper Functions for Scop. -------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Small functions that help with LLVM-IR.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_SUPPORT_IRHELPER_H
 #define POLLY_SUPPORT_IRHELPER_H
 
+#include "llvm/ADT/ArrayRef.h"
+
 namespace llvm {
 class Type;
 class Instruction;
 class LoopInfo;
 class Loop;
 class ScalarEvolution;
 class SCEV;
 class Value;

 
 /// @brief Split the entry block of a function to store the newly inserted
 ///        allocations outside of all Scops.
 ///
 /// @param EntryBlock The entry block of the current function.
 /// @param P          The pass that currently running.
 ///
 void splitEntryBlockForAlloca(llvm::BasicBlock *EntryBlock, llvm::Pass *P);
+
+/// @brief Move a set of incoming edges to a new successor.
+///
+/// Similar to llvm::SplitPredecessors, but instead of creating a new
+/// predecessor, this creates a new successor.
+/// Preserves LCSSA since it all PHIs will exist in both BasicBlocks. A PHI node
+/// is created for every PHI in the original block in the successor, even if
+/// there is only one incoming edge. PHI nodes in the orginal block are never
+/// removed, even of they it has fewer than two incoming edges left.
+/// We generally cannot update RegionInfo since it could make them invalid,
+/// depending on the list of edges.
+///
+/// Before:                After:
+///
+///            NonPred[0]                   NonPred[0]
+///        \   /               \             /
+///  /---->Entry           /-->Entry        /
+///  |       |             |       \       /
+///  \--BlockInRegion      |       Entry.split
+///                        |            |
+///                        \-------BlockInRegion
+///
+/// If Entry is split. neither "Entry" nor "Entry.split" can be made the
+/// region's entry node. "Entry" cannot because there is en edge from an
+/// ouside-of-region block NonPred[0] to another region block, violating the
+/// single entry requirement of a region. The new block "Entry.split" cannot be
+/// the entry block because there is an exiting edge to "Entry", which would
+/// then be an alternative to the region's other exit block.
+/// There is a similar situation with the exit block conflicting with other
+/// regions.
+/// Hence, the caller of this function should make sure such cases do not happen
+/// and update RegionInfo accordingly.
+///
+/// @param BB Block to split.
+/// @param NonPreds Set of incoming edges to move to the new successor.
+/// @param Suffix Suffix to append to the name of the new block.
+/// @param DT DominatorTree to update.
+/// @param LI LoopInfo to update.
+/// @param SE ScalarEvolution to update.
+///
+/// @return The newly created successor of BB or null if the block could not be
+/// split.
+llvm::BasicBlock *
+splitBlockNonPredecessors(llvm::BasicBlock *BB,
+                          llvm::ArrayRef<llvm::BasicBlock *> NonPreds,
+                          llvm::StringRef Suffix, llvm::DominatorTree *DT,
+                          llvm::LoopInfo *LI, llvm::ScalarEvolution *SE);
 }
 #endif

lib/CodeGen/CodeGeneration.cpp

DEBUG({
       F.print(errs());
       errs() << "\n== The errors ==\n";
       verifyFunction(F, &errs());
     });
 
     return true;
   }
 
+  // Create a dedicated block for exit node PHIs.
+  // This special block is made the exiting block so the PHIs become included
+  // into the region.
+  // The exit block itself keeps its identity.
+  BasicBlock *createExitingBlockForExitNodePHIs(Region *R) {
+    BasicBlock *ExitBB = R->getExit();
+
+    SmallVector<BasicBlock *, 4> NonPreds;
+    for (BasicBlock *P : predecessors(ExitBB))
+      if (!R->contains(P))
+        NonPreds.push_back(P);
+
+    /*  Preds[0] Preds[1]     otherBB */
+    /*         \  |  ________/        */
+    /*          \ | /                 */
+    /*         ExitBB                 */
+    BasicBlock *NewExitBlock = splitBlockNonPredecessors(
+        ExitBB, NonPreds, ".exit", DT, LI, /*RI,*/ SE);
+    /* Preds[0] Preds[1]  otherBB     */
+    /*        \  /       /            */
+    /*       ExitBB     /             */
+    /*            \    /              */
+    /*          NewExitBlock          */
+
+    // If there was a region with ExitBB as entry block, change it to
+    // NewExitBlock
+    Region *RegionOfExit = RI->getRegionFor(ExitBB);
+    RI->setRegionFor(NewExitBlock, RegionOfExit);
+    while (RegionOfExit && !RegionOfExit->isTopLevelRegion() &&
+           RegionOfExit->getEntry() == ExitBB) {
+      RegionOfExit->replaceEntry(NewExitBlock);
+      RegionOfExit = RegionOfExit->getParent();
+    }
+    RI->setRegionFor(ExitBB, RegionOfExit);
+
+    // Make NewExitBlock the new exit block
+    for (BasicBlock *PotentialExiting : predecessors(ExitBB)) {
+      assert(PotentialExiting != NewExitBlock);
+      Region *OtherR = RI->getRegionFor(PotentialExiting);
+      while (OtherR && !OtherR->isTopLevelRegion() &&
+             OtherR->getExit() == ExitBB) {
+        // Do not change exit nodes of subregions as they can keep ExitBB as
+        // their exit block
+        if (R == OtherR || !R->contains(OtherR)) {
+          OtherR->replaceExit(NewExitBlock);
+        }
+        OtherR = OtherR->getParent();
+      }
+    }
+    assert(R->contains(ExitBB));
+    assert(!R->contains(NewExitBlock));
+    assert(R->getExit() == NewExitBlock);
+    RI->setRegionFor(ExitBB, R);
+
+    return ExitBB; // The block containing the PHIs
+  }
+
   // CodeGeneration adds a lot of BBs without updating the RegionInfo
   // We make all created BBs belong to the scop's parent region without any
   // nested structure to keep the RegionInfo verifier happy.
   void fixRegionInfo(Function *F, Region *ParentRegion) {
     for (BasicBlock &BB : *F) {
       if (RI->getRegionFor(&BB))
         continue;
 
bool runOnScop(Scop &S) override {
     RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
     Region *R = &S.getRegion();
     assert(!R->isTopLevelRegion() && "Top level regions are not supported");
 
     Annotator.buildAliasScopes(S);
 
     simplifyRegion(R, DT, LI, RI);
     assert(R->isSimple());
+    createExitingBlockForExitNodePHIs(R);
+
     BasicBlock *EnteringBB = S.getRegion().getEnteringBlock();
     assert(EnteringBB);
     PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
 
     IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S);
 
     // Only build the run-time condition and parameters _after_ having
     // introduced the conditional branch. This is important as the conditional

lib/Support/ScopHelper.cpp

void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
   auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
   RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>();
   RegionInfo *RI = RIP ? &RIP->getRegionInfo() : nullptr;
 
   // splitBlock updates DT, LI and RI.
   splitBlock(EntryBlock, I, DT, LI, RI);
 }
+
+BasicBlock *polly::splitBlockNonPredecessors(BasicBlock *BB,
+                                             ArrayRef<BasicBlock *> NonPreds,
+                                             llvm::StringRef Suffix,
+                                             DominatorTree *DT, LoopInfo *LI,
+                                             ScalarEvolution *SE) {
+  assert(BB);
+
+  // Do not attempt to split blocks that cannot be split.
+  if (!BB->canSplitPredecessors())
+    return nullptr;
+
+  // Currently we cannot handle landing pads.
+  if (BB->isLandingPad())
+    return nullptr;
+
+  // Before:
+  //
+  //          NonPreds[0]  //
+  //      \  /             //
+  //       BB              //
+  //      /  \             //
+
+  // Create new basic block, insert right after the original block.
+  auto OldName = BB->getName();
+  BasicBlock *NewBB =
+      splitBlock(BB, BB->getFirstInsertionPt(), DT, LI, nullptr);
+  NewBB->setName(OldName + Suffix);
+
+  // Create new PHIs into the new block.
+  for (auto I = BB->begin(); isa<PHINode>(I); ++I) {
+    PHINode *OldPHI = cast<PHINode>(&*I);
+    PHINode *NewPHI = PHINode::Create(OldPHI->getType(), NonPreds.size() + 1,
+                                      OldPHI->getName() + ".np",
+                                      NewBB->getFirstInsertionPt());
+
+    // Replaces uses of the original PHI by the new ones.
+    OldPHI->replaceAllUsesWith(NewPHI);
+
+    // Add an edge from the original block (this adds a use)
+    NewPHI->addIncoming(OldPHI, BB);
+
+    // Move the incoming block's values.
+    for (BasicBlock *Edge : NonPreds) {
+      BasicBlock *RedirectedEdge = Edge == BB ? NewBB : Edge;
+      auto i = OldPHI->getBasicBlockIndex(RedirectedEdge);
+      assert(i >= 0);
+      Value *Val = OldPHI->getIncomingValue(i);
+      NewPHI->addIncoming(Val, RedirectedEdge);
+      OldPHI->removeIncomingValue(i, false);
+
+      if (SE)
+        SE->forgetValue(OldPHI);
+    }
+  }
+
+  // If there were no edges to move, there is nothing more to do.
+  if (NonPreds.empty())
+    return NewBB;
+
+  // Move all non-pred edges to the new BB.
+  for (BasicBlock *Edge : NonPreds) {
+    BasicBlock *RedirectedEdge = Edge == BB ? NewBB : Edge;
+    assert(!isa<IndirectBrInst>(RedirectedEdge->getTerminator()) &&
+           "Cannot split an edge from an IndirectBrInst");
+    RedirectedEdge->getTerminator()->replaceUsesOfWith(BB, NewBB);
+  }
+
+  if (DT) {
+    // DominatorTree::splitBlock assumes that it is the predecessor which is
+    // new. In order to reuse that function, we recreate the situation as if it
+    // was.
+    auto BBNode = DT->getNode(BB);
+    auto NewBBNode = DT->getNode(NewBB);
+    DT->changeImmediateDominator(NewBBNode, BBNode->getIDom());
+    DT->eraseNode(BB);
+
+    DT->splitBlock(BB);
+  }
+
+  if (LI) {
+    BasicBlock *OldBB = BB;
+    Loop *L = LI->getLoopFor(OldBB);
+    while (L) {
+      assert(L->contains(OldBB));
+
+      bool OldBBReachableFromInside = false;
+      for (BasicBlock *Pred : predecessors(OldBB)) {
+        if (Pred == NewBB || L->contains(Pred)) {
+          OldBBReachableFromInside = true;
+          break;
+        }
+      }
+
+      bool NewBBReachableFromOutside = false;
+      for (auto Pred : make_range(pred_begin(NewBB), pred_end(NewBB))) {
+        if (Pred == OldBB)
+          continue;
+
+        if (Pred != NewBB && !L->contains(Pred)) {
+          NewBBReachableFromOutside = true;
+          break;
+        }
+      }
+
+      if (NewBBReachableFromOutside || !OldBBReachableFromInside) {
+        // Remove BB from the loop and make the NewBB the next loop header.
+        // Since NewBB dominates OldBB, it can be the new header.
+        if (L->getHeader() == OldBB)
+          L->moveToHeader(NewBB);
+      }
+
+      if (!OldBBReachableFromInside) {
+        // OldBB cannot be reached from the loop header anymore, i.e. it has
+        // been excluded from the loop.
+        L->removeBlockFromLoop(BB);
+        LI->changeLoopFor(BB, L->getParentLoop());
+      }
+
+      L = L->getParentLoop();
+    }
+  }
+
+  // After:
+  //
+  //               NonPreds[0]  //
+  //      \         /           //
+  //       BB      /            //
+  //         \    /             //
+  //          NewBB             //
+  //          /  \              //
+
+  return NewBB;
+}
 No newline at end of file

test/Isl/CodeGen/loop_with_conditional_entry_edge_split_hard_case.ll

 ;    }
 ;
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @jd(i32 %b, i32* %A) {
 entry:
   br label %while.begin
 
-; CHECK-LABEL: while.begin.region_exiting:
-; CHECK:         br label %polly.merge_new_and_old
+; CHECK-LABEL: while.begin:
+; CHECK:   br label %polly.merge_new_and_old
 
-; CHECK-LABEL: while.begin:
+; CHECK-LABEL: while.begin.exit:
 while.begin:
 ; CHECK:  %call = call i32 @f()
   %call = call i32 @f()
 ; CHECK:  %tobool = icmp eq i32 %call, 0
   %tobool = icmp eq i32 %call, 0
 ; CHECK:  br i1 %tobool, label %while.end, label %polly.split_new_and_old
   br i1 %tobool, label %while.end, label %if
 

test/Isl/CodeGen/phi_loop_carried_float.ll

 ; RUN: opt %loadPolly -S -polly-no-early-exit -polly-detect-unprofitable  -polly-codegen < %s | FileCheck %s
 ;
 ;    float f(float *A, int N) {
 ;      float tmp = 0;
 ;      for (int i = 0; i < N; i++)
 ;        tmp += A[i];
 ;    }
 ;
 ; CHECK:      bb:
 ; CHECK-NOT:    %tmp7{{[.*]}} = alloca float
 ; CHECK-DAG:    %tmp.0.s2a = alloca float
 ; CHECK-NOT:    %tmp7{{[.*]}} = alloca float
 ; CHECK-DAG:    %tmp.0.phiops = alloca float
 ; CHECK-NOT:    %tmp7{{[.*]}} = alloca float
+;
+; CHECK-LABEL: polly.merge_new_and_old:
+; CHECK-NEXT:     br label %exit.exit
 
-; CHECK-LABEL: exit:
+; CHECK-LABEL: exit.exit:
 ; CHECK-NEXT:    ret
-
+;
 ; CHECK-LABEL: polly.start:
 ; CHECK-NEXT:    store float 0.000000e+00, float* %tmp.0.phiops
 
 ; CHECK-LABEL: polly.merge:
 ; CHECK-NEXT:    br label %polly.merge_new_and_old
 
 ; CHECK-LABEL: polly.stmt.bb1{{[0-9]*}}:
 ; CHECK-NEXT:    %tmp.0.phiops.reload[[R1:[0-9]*]] = load float, float* %tmp.0.phiops

test/Isl/CodeGen/phi_loop_carried_float_escape.ll

 ; RUN: opt %loadPolly -S -polly-no-early-exit -polly-detect-unprofitable  -polly-codegen < %s | FileCheck %s
 ;
 ;    float f(float *A, int N) {
 ;      float tmp = 0;
 ;      for (int i = 0; i < N; i++)
 ;        tmp += A[i];
 ;      return tmp;
 ;    }
 
 ; CHECK-LABEL: polly.merge_new_and_old:
-; CHECK-NEXT:    %tmp.0.merge = phi float [ %tmp.0.final_reload, %polly.merge ], [ %tmp.0, %bb8 ]
-; CHECK-NEXT:    br label %exit
+; CHECK-NEXT:    %tmp.0.merge = phi float [ %tmp.0.final_reload, %polly.merge ], [ %tmp.0, %exit ]
+; CHECK-NEXT:    br label %exit.exit
+
+; CHECK-LABEL: exit.exit:
+; CHECK-NEXT:    ret float %tmp.0.merge
 
 ; CHECK-LABEL: polly.start:
 ; CHECK-NEXT:    store float 0.000000e+00, float* %tmp.0.phiops
 
 ; CHECK-LABEL: polly.merge:
 ; CHECK-NEXT:    %tmp.0.final_reload = load float, float* %tmp.0.s2a
 ; CHECK-NEXT:    br label %polly.merge_new_and_old
 

test/Isl/CodeGen/phi_scalar_simple_1.ll

 ; CHECK-DAG:     %x.addr.1.s2a = alloca i32
 ; CHECK-DAG:     %x.addr.1.phiops = alloca i32
 ; CHECK-DAG:     %x.addr.0.s2a = alloca i32
 ; CHECK-DAG:     %x.addr.0.phiops = alloca i32
   %tmp = sext i32 %N to i64
   br label %for.cond
 
 ; CHECK-LABEL: polly.merge_new_and_old:
-; CHECK:         %x.addr.0.merge = phi i32 [ %x.addr.0.final_reload, %polly.merge ], [ %x.addr.0, %for.cond ]
+; CHECK:         %x.addr.0.merge = phi i32 [ %x.addr.0.final_reload, %polly.merge ], [ %x.addr.0, %for.end6 ]
 ; CHECK:         ret i32 %x.addr.0.merge
 
 ; CHECK-LABEL: polly.start:
 ; CHECK-NEXT:    store i32 %x, i32* %x.addr.0.phiops
 
 ; CHECK-LABEL: polly.merge:
 ; CHECK:         %x.addr.0.final_reload = load i32, i32* %x.addr.0.s2a
 

test/Isl/CodeGen/phi_scalar_simple_2.ll

 ; CHECK-DAG:     %x.addr.1.phiops = alloca i32
 ; CHECK-DAG:     %x.addr.0.s2a = alloca i32
 ; CHECK-DAG:     %x.addr.0.phiops = alloca i32
   %tmp = sext i32 %N to i64
   %tmp1 = sext i32 %c to i64
   br label %for.cond
 
 ; CHECK-LABEL: polly.merge_new_and_old:
-; CHECK:         %x.addr.0.merge = phi i32 [ %x.addr.0.final_reload, %polly.merge ], [ %x.addr.0, %for.cond ]
+; CHECK:         %x.addr.0.merge = phi i32 [ %x.addr.0.final_reload, %polly.merge ], [ %x.addr.0, %for.end7 ]
 ; CHECK:         ret i32 %x.addr.0.merge
 
 ; CHECK-LABEL: polly.start:
 ; CHECK-NEXT:    store i32 %x, i32* %x.addr.0.phiops
 
 ; CHECK-LABEL: polly.merge:
 ; CHECK:         %x.addr.0.final_reload = load i32, i32* %x.addr.0.s2a