[Polly] Revise the simplification of regions

[Meinersbur]

Summary

The previous code had several problems:

For newly created BasicBlocks it did not (always) call RegionInfo::setRegionFor in order to update its analysis. At the moment RegionInfo does not verify its BBMap, but will in the future. This is fixed by determining the region new BBs belong to and set it accordingly.

Which block is created by SplitEdge depends on the incoming and outgoing edges of the blocks it connects, which makes handling its output more difficult than it needs to be. Especially for finding which block has been created an to assign a region to it for the setRegionFor problem above. This patch uses an implementation for splitEdge that always creates a block between the predecessor and successor. simplifyRegion has also been simplified by using SplitBlockPredecessors instead of SplitEdge. Isolating the entries and exits have been refectored into individual functions.

Previously simplifyRegion did more than just ensuring that there is only one entering and one exiting edge. It ensured that the entering block had no other outgoing edge which was necessary for executeScopConditionally(). Now the latter uses the alternative splitEdge implementation which can handle this situation so simplifyRegion really only needs to simplify the region.

Also, executeScopConditionally assumed that there can be no PHI nodes in blocks with one incoming edge. This is wrong and LCSSA deliberately produces such edges. However, previous passes ensured that there can be no such PHIs in exit nodes, but which will no longer hold in the future.

In some cases the old code assigned the wrong entry/exit node to function. This happened in some circumstances if there were other edges from other regions to the exit node (could be a sibling or ancestor node) or edges from nested regions to the entry node. RegionInfo::splitBlock() made the latter mistake.

The new code that the property that it preserves the identity of region block (the property that the memory address of the BasicBlock containing the instructions remains the same; new blocks only contain PHI nodes and a terminator), especially the entry block. As a result, there is no need to update the reference to the BasicBlock of ScopStmt that contain its instructions because they have been moved to other basic blocks.

[grosser]

Hi Michael,

Ensure that RegionInfo (setRegionFor) is updated, make the location of block creation stable (not dependent on unrelated edges) so there are fewer cases to consider and keep the identity of the region's entry block (ScopStmts do not need to be updated anymore).

This is a preparation to allow PHI nodes in exit blocks.

for such a large patch (500 new lines), the commit message is really short. Would it be possible to summarize the changes in this commit in a bit more detail (or give some context) and give some motivation on why they are needed?

Some questions I asked myself:

1. Was the RegionInfo correct before and only the BB <-> Region was lacking or were there other issues with the RegionInfo that have been addressed. If only the BB <-> Region mapping was lacking, I would mention that only your recent changes to LLVM allow us to check and verify this mapping.
   
   (If this is indeed the only fix to the RegionInfo, than this part of the patch seems to be independent of the rest and should be submitted and discussed separately)

2. "make the location of block creation stable (not dependent on unrelated edges) so there are fewer cases to consider"

Some context explaining the current problem, would help the reader to understand what the issue
is at the moment.

3. "keep the identity of the region's entry block (ScopStmts do not need to be updated anymore)"

This seems a real improvement, but the readers likely lacks context to understand what exactly why ScopStms
had to be updated before and why the new approach does not require this any more.

I started to lock at the actual semantically complicated parts of the patch, but did not yet finish. It would probably help if you could add 2-3 sentences on how the way we split regions differs to what was done before and how this affects (or does not affect other ScoPs). This would make it easier to understand if this patch may invalidate assumptions that may have been taken in other parts of Polly.

Best,
Tobias

P.S: Thank you for the nice illustrative graphics and the extended documentation.

include/polly/Support/ScopHelper.h

86

The second part of the sentence seems incomplete.

108

grammar?

112

Suffix

114

LoopInfo

lib/CodeGen/Utils.cpp

27

Please drop the 'splitEdge -' part.

Also, I lack a comment that explains how the edge is actually spitted.

72

Why is there an if 0 section?

lib/Support/ScopHelper.cpp

249

Very nice illustrations

255

Why did you move around this function? This (unnecessarily?) bloats the diff.

268

LLVM suggests to use C++ style // comments. See http://llvm.org/docs/CodingStandards.html#comment-formatting.

I understand that just dropping the */ at the end of the line will cause a warning about multi-line comments due to the trailing '\', but you can probably just use another character between the '\' and the line ending to avoid this (not a space, as this gives trailing space warnings).

276

Too many spaces?

289

Why is RegionInfo commented out?

I can not find any use of this function. Is this code actually needed?

292

Grammar?

[Meinersbur]

Addressed comments
Remove conditional preprocessor blocks, fix some whitespace.

[Meinersbur]

In D11867#220072, @grosser wrote:

I started to lock at the actual semantically complicated parts of the patch, but did not yet finish. It would probably help if you could add 2-3 sentences on how the way we split regions differs to what was done before and how this affects (or does not affect other ScoPs). This would make it easier to understand if this patch may invalidate assumptions that may have been taken in other parts of Polly.

Sorry, but you have to understand the code by yourself. The illustrations should make it relatively easy to understand what it does and is relatively straigtforward. Regarding the way it was done before you have to to ask its author, as I found it too complicated.

What remains complicated is updating the RegionInfo. I tried to find an abstraction which would handle all cases (this is because there war a commented RegionInfo *RI in one parameter list), but did not find one.

lib/Support/ScopHelper.cpp

255

It tried to match the functions I rewrote with the order in the header (where I placed the new function splitBlock and splitBlockNonPredecessors at the end).

splitEntryBlockForAlloca only appears to have moved because this diff did not match it correctly.

268

As said, the standard is no absolute requirement and here I have reason to diverge from it.

Having stray characters in such lines look really awful and someone would probably wonder what they mean.

This comment style also has the benefit to be more stable in code editors and formatters (clang-format, Visual Studio).

289

Mmmh, at some intermediate point executeScopConditionally used it but it looks like simplified that function such that a call to this function wasn't necessary anymore.

In any case, the function is still needed for createExitingBlockForExitNodePHIs, but not yet in this patch.

[Meinersbur]

Remove some outdated comments, add some new
Add some ASCII-graphs
Use llvm::predecessors where possible

[grosser]

Hi Michael,

I went through the patch. Overall, it looks very good. Indeed, while reading the code, it seems it became
a lot more readable. I still found a couple of issues, but most of them are minor (often stylistic).

Now, while looking through the patch, it seems there are four independent changes:

1. Introduce splitBlock and use it in splitEntryBlockForAlloca

2. Introduce splitEdge and use it to simplify executeScopConditionally

3. Rework simplifyRegion

4. fixRegionInfo

Committing them separately might make each patch easier to understand and also makes clear which part of the commit message belongs to which changes.

lib/CodeGen/CodeGeneration.cpp

126

Was this not asserted three lines earlier already?

lib/CodeGen/Utils.cpp

47

The grammar of this comment and as a result the comment itself is unclear. Are you suggesting the use of SplitBlockPredecessors is not the best choice? It looks pretty reasonable to me. Unfortunately, I do not understand the other options.

80–81

OK, I now went through this function and it looks indeed a lot cleaner. Thank you again for restructuring this.

154

Uppercase, point.

159

Point

161

Originally, the blocks were saved in variables "SplitBlock" and "MergeBlock" and were named "split_new_and_old" and "merge_new_and_old".

The new code leaves the basic block names unchanged, but uses variable names JunctionBlock and MergeBlock and refers in the comments to these basic blocks with "fork" and "join". This seems inconsistent.

172

Point?

lib/Support/ScopHelper.cpp

79–80

Why is this change needed? The ternary condition you introduce seems redundant.

80

Why is this change needed? The ternary condition you introduce seems redundant.

85

Make this an assert?

107

'entry' does not belong here

206

assert?

208

Why is this change needed? The ternary condition you introduce seems redundant.

210

Why is this change needed? The ternary condition you introduce seems redundant.

223

Early return?

247

Why is this change needed? The ternary condition you introduce seems redundant.

249

Why is this change needed? The ternary condition you introduce seems redundant.

251

Why is this change needed? The ternary condition you introduce seems redundant.

268

I think LLVM is very consistent in avoiding these kind of comments. The only use I can find is to comment parameters in function calls.

If you look for the kind of graphics you add, the following have been used e.g.:

grep -R '\\ ' lib/

​ //    \ /    |
​ //    Old    |
​ //    / \    |

​ //    \ /    //
​ //    Old    //
​ //    / \    //

test/Isl/CodeGen/loop_with_conditional_entry_edge_splitted_hard_case.ll

1 ↗

(On Diff #31701)

Why is this file executable (mode 755)?

[Meinersbur]

Rebased to trunk.
Addressed comments.
Made simplifyRegion parameters for each updated analysis
Privatized splitBlock since only used by splitEntryBlockForAlloca

Since this already got accepted, I will go on to commit it in 4 individual commits as suggested.

[Meinersbur]

lib/Support/ScopHelper.cpp

80

It's not required in the strict sense, but I like to keep it general, allowing for not passing the pass.

IMHO this function fits much better into RegionInfo.cpp. The RegionInfo comments mention the definition of a simple region, that it can be made simple, but there is no function there which does this.

Alternatively, we may pass DT, LI, RI as arguments as the other functions do.

223

I prefer this style here, which shows which conditions are valid at the end whatever case is taken, including the ASCII-graphs.

test/Isl/CodeGen/loop_with_conditional_entry_edge_splitted_hard_case.ll

1 ↗

(On Diff #31701)

This comes from a Windows file system.

I renamed the file separately, so no issue anymore.

[grosser]

Hi Michael,

looking forward to see this change in. (Some replies to your final comments)

Best,
Tobias

lib/Support/ScopHelper.cpp

80

It's not required in the strict sense, but I like to keep it general, allowing for not passing the pass.

OK, so you want to generalize this. It probably helps if you explain this intention in the commit message.

IMHO this function fits much better into RegionInfo.cpp. The RegionInfo comments mention the definition of a simple region, that it can be made simple, but there is no function there which does this.

The problem is that RegionInfo.cpp is an analysis, not a transformation. If there is a need, we can at some point create some RegionUtils in LLVM and possibly also provide a pass that does region-simplification.

Alternatively, we may pass DT, LI, RI as arguments as the other functions do.

I have no strong opinion. I just dislike such kind of "cleanups" being mixed with larger refactorings as they just cause diff-noise which makes it hard to see the important changes. As separate changes, such things are trivial to review and easy to explain in the commit message. As you anyway factor out the cleanup of splitEntryBlockForAlloc, that should not be an issue any more.

223

OK.

[Meinersbur]

I can't separate 2. and 3.

The new executeScopConditionally assumes that RegionInfo::getRegionFor is up-to-date that the old simplifyRegion does not do.

The new simplifyRegion does not make sure that the EnteringBB has just one exiting edge, a requirement for the old executeScopConditionally.

[Meinersbur]

Committed as r244600, r244606 and r244608

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;
 class PHINode;
 class Region;
 class Pass;
 class BasicBlock;
+class StringRef;
+class DominatorTree;
+class RegionInfo;
+class ScalarEvolution;
 }
 
 namespace polly {
 class Scop;
 /// Temporary Hack for extended regiontree.
 ///
 /// @brief Cast the region to loop.
 ///

 /// @param PN The PHINode to check.
 ///
 /// @return If the PHINode has an incoming BB that jumps to the parent BB
 ///         of the PHINode with an invoke instruction, return true,
 ///         otherwise, return false.
 bool hasInvokeEdge(const llvm::PHINode *PN);
 
 llvm::Value *getPointerOperand(llvm::Instruction &Inst);
-llvm::BasicBlock *createSingleExitEdge(llvm::Region *R, llvm::Pass *P);
 
-/// @brief Simplify the region in a SCoP to have a single unconditional entry
-///        edge and a single exit edge.
-///
-/// @param S  The SCoP that is simplified.
-/// @param P  The pass that is currently running.
+/// @brief Simplify the region to have a single unconditional entry edge and a
+/// single exit edge.
 ///
-/// @return The unique entering block for the region.
-llvm::BasicBlock *simplifyRegion(polly::Scop *S, llvm::Pass *P);
+/// Although this function allows DT and RI to be null, regions only work
+/// properly if the DominatorTree (for Region::contains) and RegionInfo are kept
+/// up-to-date.
+///
+/// @param R  The region to be simplified
+/// @param DT DominatorTree to be updated.
+/// @param LI LoopInfo to be updated.
+/// @param RI RegionInfo to be updated.
+void simplifyRegion(llvm::Region *R, llvm::DominatorTree *DT,
+                    llvm::LoopInfo *LI, llvm::RegionInfo *RI);
 
 /// @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);
 }
 #endif

lib/CodeGen/CodeGeneration.cpp

public:
 
   /// @name The analysis passes we need to generate code.
   ///
   ///{
   LoopInfo *LI;
   IslAstInfo *AI;
   DominatorTree *DT;
   ScalarEvolution *SE;
+  RegionInfo *RI;
   ///}
 
   /// @brief The loop annotator to generate llvm.loop metadata.
   ScopAnnotator Annotator;
 
   /// @brief Build the runtime condition.
   ///
   /// Build the condition that evaluates at run-time to true iff all
DEBUG({
       F.print(errs());
       errs() << "\n== The errors ==\n";
       verifyFunction(F, &errs());
     });
 
     return true;
   }
 
+  // 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;
+
+      RI->setRegionFor(&BB, ParentRegion);
+    }
+  }
+
   bool runOnScop(Scop &S) override {
     AI = &getAnalysis<IslAstInfo>();
 
     // Check if we created an isl_ast root node, otherwise exit.
     isl_ast_node *AstRoot = AI->getAst();
     if (!AstRoot)
       return false;
 
     LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
     DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
     SE = &getAnalysis<ScalarEvolution>();
     DL = &S.getRegion().getEntry()->getParent()->getParent()->getDataLayout();
-
-    assert(!S.getRegion().isTopLevelRegion() &&
-           "Top level regions are not supported");
+    RI = &getAnalysis<RegionInfoPass>().getRegionInfo();
+    Region *R = &S.getRegion();
+    assert(!R->isTopLevelRegion() && "Top level regions are not supported");
 
     Annotator.buildAliasScopes(S);
 
-    BasicBlock *EnteringBB = simplifyRegion(&S, this);
+    simplifyRegion(R, DT, LI, RI);
+    assert(R->isSimple());
+    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
     // branch will guard the original scop from new induction variables that
     // the SCEVExpander may introduce while code generating the parameters and
     // which may introduce scalar dependences that prevent us from correctly
     // code generating this scop.
     BasicBlock *StartBlock =
         executeScopConditionally(S, this, Builder.getTrue());
     auto SplitBlock = StartBlock->getSinglePredecessor();
     Builder.SetInsertPoint(SplitBlock->getTerminator());
     NodeBuilder.addParameters(S.getContext());
     Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder());
     SplitBlock->getTerminator()->setOperand(0, RTC);
     Builder.SetInsertPoint(StartBlock->begin());
 
     NodeBuilder.create(AstRoot);
 
     NodeBuilder.finalizeSCoP(S);
+    fixRegionInfo(EnteringBB->getParent(), R->getParent());
 
     assert(!verifyGeneratedFunction(S, *EnteringBB->getParent()) &&
            "Verification of generated function failed");
     return true;
   }
 
   void printScop(raw_ostream &, Scop &) const override {}
 

lib/CodeGen/Utils.cpp

 
 #include "polly/CodeGen/Utils.h"
 #include "polly/CodeGen/IRBuilder.h"
 #include "polly/ScopInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
+#include "polly/Support/ScopHelper.h"
 
 using namespace llvm;
 
+// Alternative to llvm::SplitCriticalEdge.
+//
+// Creates a new block which branches to Succ. The edge to split is redirected
+// to the new block.
+//
+// The issue with llvm::SplitCriticalEdge is that it does nothing if the edge is
+// not critical.
+// The issue with llvm::SplitEdge is that it does not always create the middle
+// block, but reuses Prev/Succ if it can. We always want a new middle block.
+static BasicBlock *splitEdge(BasicBlock *Prev, BasicBlock *Succ,
+                             const char *Suffix, DominatorTree *DT,
+                             LoopInfo *LI, RegionInfo *RI) {
+  assert(Prev && Succ);
+
+  // Before:
+  //   \    /     /   //
+  //    Prev     /    //
+  //     |  \___/     //
+  //     |   ___      //
+  //     |  /   \     //
+  //    Succ     \    //
+  //   /    \     \   //
+
+  // The algorithm to update DominatorTree and LoopInfo of
+  // llvm::SplitCriticalEdge is more efficient than
+  // llvm::SplitBlockPredecessors, which is more general. In the future we might
+  // either modify llvm::SplitCriticalEdge to allow skipping the critical edge
+  // check; or Copy&Pase it here.
+  BasicBlock *MiddleBlock = SplitBlockPredecessors(
+      Succ, ArrayRef<BasicBlock *>(Prev), Suffix, DT, LI);
+
+  if (RI) {
+    Region *PrevRegion = RI->getRegionFor(Prev);
+    Region *SuccRegion = RI->getRegionFor(Succ);
+    if (PrevRegion->contains(MiddleBlock)) {
+      RI->setRegionFor(MiddleBlock, PrevRegion);
+    } else {
+      RI->setRegionFor(MiddleBlock, SuccRegion);
+    }
+  }
+
+  // After:
+  //   \    /     /   //
+  //    Prev     /    //
+  //     |  \___/     //
+  //     |            //
+  // MiddleBlock      //
+  //     |   ___      //
+  //     |  /   \     //
+  //    Succ     \    //
+  //   /    \     \   //
+
+  return MiddleBlock;
+}
+
 BasicBlock *polly::executeScopConditionally(Scop &S, Pass *P, Value *RTC) {
-  BasicBlock *StartBlock, *SplitBlock, *NewBlock;
   Region &R = S.getRegion();
   PollyIRBuilder Builder(R.getEntry());
   DominatorTree &DT = P->getAnalysis<DominatorTreeWrapperPass>().getDomTree();
   RegionInfo &RI = P->getAnalysis<RegionInfoPass>().getRegionInfo();
   LoopInfo &LI = P->getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 
-  // Split the entry edge of the region and generate a new basic block on this
-  // edge. This function also updates ScopInfo and RegionInfo.
-  NewBlock = SplitEdge(R.getEnteringBlock(), R.getEntry(), &DT, &LI);
-  if (DT.dominates(R.getEntry(), NewBlock)) {
-    BasicBlock *OldBlock = R.getEntry();
-    std::string OldName = OldBlock->getName();
-
-    // Update ScopInfo.
-    for (ScopStmt &Stmt : S)
-      if (Stmt.getBasicBlock() == OldBlock) {
-        Stmt.setBasicBlock(NewBlock);
-        break;
-      }
+  // Before:
+  //
+  //      \   /      //
+  //    EnteringBB   //
+  //   _____|_____   //
+  //  /  EntryBB  \  //
+  //  |  (region) |  //
+  //  \_ExitingBB_/  //
+  //        |        //
+  //      ExitBB     //
+  //      /    \     //
+
+  // Create a fork block.
+  BasicBlock *EnteringBB = R.getEnteringBlock();
+  BasicBlock *EntryBB = R.getEntry();
+  assert(EnteringBB && "Must be a simple region");
+  BasicBlock *SplitBlock =
+      splitEdge(EnteringBB, EntryBB, ".split_new_and_old", &DT, &LI, &RI);
+  SplitBlock->setName("polly.split_new_and_old");
 
-    // Update RegionInfo.
-    SplitBlock = OldBlock;
-    OldBlock->setName("polly.split");
-    NewBlock->setName(OldName);
-    R.replaceEntryRecursive(NewBlock);
-    RI.setRegionFor(NewBlock, &R);
-  } else {
-    RI.setRegionFor(NewBlock, R.getParent());
-    SplitBlock = NewBlock;
-  }
+  // Create a join block
+  BasicBlock *ExitingBB = R.getExitingBlock();
+  BasicBlock *ExitBB = R.getExit();
+  assert(ExitingBB && "Must be a simple region");
+  BasicBlock *MergeBlock =
+      splitEdge(ExitingBB, ExitBB, ".merge_new_and_old", &DT, &LI, &RI);
+  MergeBlock->setName("polly.merge_new_and_old");
 
-  SplitBlock->setName("polly.split_new_and_old");
+  // Exclude the join block from the region.
+  R.replaceExitRecursive(MergeBlock);
+  RI.setRegionFor(MergeBlock, R.getParent());
+
+  //      \   /      //
+  //    EnteringBB   //
+  //        |        //
+  //    SplitBlock   //
+  //   _____|_____   //
+  //  /  EntryBB  \  //
+  //  |  (region) |  //
+  //  \_ExitingBB_/  //
+  //        |        //
+  //    MergeBlock   //
+  //        |        //
+  //      ExitBB     //
+  //      /    \     //
+
+  // Create the start block.
   Function *F = SplitBlock->getParent();
-  StartBlock = BasicBlock::Create(F->getContext(), "polly.start", F);
+  BasicBlock *StartBlock =
+      BasicBlock::Create(F->getContext(), "polly.start", F);
   SplitBlock->getTerminator()->eraseFromParent();
   Builder.SetInsertPoint(SplitBlock);
   Builder.CreateCondBr(RTC, StartBlock, R.getEntry());
   if (Loop *L = LI.getLoopFor(SplitBlock))
     L->addBasicBlockToLoop(StartBlock, LI);
   DT.addNewBlock(StartBlock, SplitBlock);
-  Builder.SetInsertPoint(StartBlock);
-
-  BasicBlock *MergeBlock;
+  RI.setRegionFor(StartBlock, RI.getRegionFor(SplitBlock));
 
-  if (R.getExit()->getSinglePredecessor())
-    // No splitEdge required.  A block with a single predecessor cannot have
-    // PHI nodes that would complicate life.
-    MergeBlock = R.getExit();
-  else {
-    MergeBlock = SplitEdge(R.getExitingBlock(), R.getExit(), &DT, &LI);
-    // SplitEdge will never split R.getExit(), as R.getExit() has more than
-    // one predecessor. Hence, mergeBlock is always a newly generated block.
-    R.replaceExitRecursive(MergeBlock);
-    RI.setRegionFor(MergeBlock, &R);
-  }
+  //      \   /                    //
+  //    EnteringBB                 //
+  //        |                      //
+  //    SplitBlock---------\       //
+  //   _____|_____         |       //
+  //  /  EntryBB  \    StartBlock  //
+  //  |  (region) |                //
+  //  \_ExitingBB_/                //
+  //        |                      //
+  //    MergeBlock                 //
+  //        |                      //
+  //      ExitBB                   //
+  //      /    \                   //
 
+  // Connect start block to the join block.
+  Builder.SetInsertPoint(StartBlock);
   Builder.CreateBr(MergeBlock);
-  MergeBlock->setName("polly.merge_new_and_old");
-
-  if (DT.dominates(SplitBlock, MergeBlock))
-    DT.changeImmediateDominator(MergeBlock, SplitBlock);
+
+  //      \   /                    //
+  //    EnteringBB                 //
+  //        |                      //
+  //    SplitBlock---------\       //
+  //   _____|_____         |       //
+  //  /  EntryBB  \    StartBlock  //
+  //  |  (region) |        |       //
+  //  \_ExitingBB_/        |       //
+  //        |              |       //
+  //    MergeBlock---------/       //
+  //        |                      //
+  //      ExitBB                   //
+  //      /    \                   //
+
   return StartBlock;
 }

lib/Support/ScopHelper.cpp

 #include "llvm/Analysis/RegionInfo.h"
 #include "llvm/Analysis/ScalarEvolution.h"
 #include "llvm/Analysis/ScalarEvolutionExpressions.h"
 #include "llvm/IR/CFG.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
+using namespace polly;
 
 #define DEBUG_TYPE "polly-scop-helper"
 
 // Helper function for Scop
 // TODO: Add assertion to not allow parameter to be null
 //===----------------------------------------------------------------------===//
 // Temporary Hack for extended region tree.
 // Cast the region to loop if there is a loop have the same header and exit.

 bool polly::hasInvokeEdge(const PHINode *PN) {
   for (unsigned i = 0, e = PN->getNumIncomingValues(); i < e; ++i)
     if (InvokeInst *II = dyn_cast<InvokeInst>(PN->getIncomingValue(i)))
       if (II->getParent() == PN->getIncomingBlock(i))
         return true;
 
   return false;
 }
 
-BasicBlock *polly::createSingleExitEdge(Region *R, Pass *P) {
-  BasicBlock *BB = R->getExit();
+// Ensures that there is just one predecessor to the entry node from outside the
+// region.
+// The identity of the region entry node is preserved.
+static void simplifyRegionEntry(Region *R, DominatorTree *DT, LoopInfo *LI,
+                                RegionInfo *RI) {
+  BasicBlock *EnteringBB = R->getEnteringBlock();
+  BasicBlock *Entry = R->getEntry();
+
+  // Before (one of):
+  //
+  //                       \    /            //
+  //                      EnteringBB         //
+  //                        |    \------>    //
+  //   \   /                |                //
+  //   Entry <--\         Entry <--\         //
+  //   /   \    /         /   \    /         //
+  //        ....               ....          //
 
+  // Create single entry edge if the region has multiple entry edges.
+  if (!EnteringBB) {
     SmallVector<BasicBlock *, 4> Preds;
-  for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI)
-    if (R->contains(*PI))
-      Preds.push_back(*PI);
+    for (BasicBlock *P : predecessors(Entry))
+      if (!R->contains(P))
+        Preds.push_back(P);
 
-  auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
-  auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
-  auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
-  auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
+    BasicBlock *NewEntering =
+        SplitBlockPredecessors(Entry, Preds, ".region_entering", DT, LI);
 
-  return SplitBlockPredecessors(BB, Preds, ".region", DT, LI);
+    if (RI) {
+      // The exit block of predecessing regions must be changed to NewEntering
+      for (BasicBlock *ExitPred : predecessors(NewEntering)) {
+        Region *RegionOfPred = RI->getRegionFor(ExitPred);
+        if (RegionOfPred->getExit() != Entry)
+          continue;
+
+        while (!RegionOfPred->isTopLevelRegion() &&
+               RegionOfPred->getExit() == Entry) {
+          RegionOfPred->replaceExit(NewEntering);
+          RegionOfPred = RegionOfPred->getParent();
+        }
       }
 
-static void replaceScopAndRegionEntry(polly::Scop *S, BasicBlock *OldEntry,
-                                      BasicBlock *NewEntry) {
-  if (polly::ScopStmt *Stmt = S->getStmtForBasicBlock(OldEntry))
-    Stmt->setBasicBlock(NewEntry);
+      // Make all ancestors use EnteringBB as entry; there might be edges to it
+      Region *AncestorR = R->getParent();
+      RI->setRegionFor(NewEntering, AncestorR);
+      while (!AncestorR->isTopLevelRegion() && AncestorR->getEntry() == Entry) {
+        AncestorR->replaceEntry(NewEntering);
+        AncestorR = AncestorR->getParent();
+      }
+    }
 
-  S->getRegion().replaceEntryRecursive(NewEntry);
+    EnteringBB = NewEntering;
   }
+  assert(R->getEnteringBlock() == EnteringBB);
 
-BasicBlock *polly::simplifyRegion(Scop *S, Pass *P) {
-  Region *R = &S->getRegion();
+  // After:
+  //
+  //    \    /       //
+  //  EnteringBB     //
+  //      |          //
+  //      |          //
+  //    Entry <--\   //
+  //    /   \    /   //
+  //         ....    //
+}
+
+// Ensure that the region has a single block that branches to the exit node.
+static void simplifyRegionExit(Region *R, DominatorTree *DT, LoopInfo *LI,
+                               RegionInfo *RI) {
+  BasicBlock *ExitBB = R->getExit();
+  BasicBlock *ExitingBB = R->getExitingBlock();
 
-  // The entering block for the region.
-  BasicBlock *EnteringBB = R->getEnteringBlock();
-  BasicBlock *OldEntry = R->getEntry();
-  BasicBlock *NewEntry = nullptr;
+  // Before:
+  //
+  //   (Region)   ______/  //
+  //      \  |   /         //
+  //       ExitBB          //
+  //       /    \          //
 
-  auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
-  auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
-  auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
-  auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
+  if (!ExitingBB) {
+    SmallVector<BasicBlock *, 4> Preds;
+    for (BasicBlock *P : predecessors(ExitBB))
+      if (R->contains(P))
+        Preds.push_back(P);
+
+    //  Preds[0] Preds[1]      otherBB //
+    //         \  |  ________/         //
+    //          \ | /                  //
+    //           BB                    //
+    ExitingBB =
+        SplitBlockPredecessors(ExitBB, Preds, ".region_exiting", DT, LI);
+    // Preds[0] Preds[1]      otherBB  //
+    //        \  /           /         //
+    // BB.region_exiting    /          //
+    //                  \  /           //
+    //                   BB            //
+
+    if (RI)
+      RI->setRegionFor(ExitingBB, R);
+
+    // Change the exit of nested regions, but not the region itself,
+    R->replaceExitRecursive(ExitingBB);
+    R->replaceExit(ExitBB);
+  }
+  assert(ExitingBB == R->getExitingBlock());
 
-  // Create single entry edge if the region has multiple entry edges.
-  if (!EnteringBB) {
-    NewEntry = SplitBlock(OldEntry, OldEntry->begin(), DT, LI);
-    EnteringBB = OldEntry;
-  }
+  // After:
+  //
+  //     \   /                //
+  //    ExitingBB     _____/  //
+  //          \      /        //
+  //           ExitBB         //
+  //           /    \         //
+}
+
+void polly::simplifyRegion(Region *R, DominatorTree *DT, LoopInfo *LI,
+                           RegionInfo *RI) {
+  assert(R && !R->isTopLevelRegion());
+  assert(!RI || RI == R->getRegionInfo());
+  assert((!RI || DT) &&
+         "RegionInfo requires DominatorTree to be updated as well");
+
+  simplifyRegionEntry(R, DT, LI, RI);
+  simplifyRegionExit(R, DT, LI, RI);
+  assert(R->isSimple());
 
-  // Create an unconditional entry edge.
-  if (EnteringBB->getTerminator()->getNumSuccessors() != 1) {
-    BasicBlock *EntryBB = NewEntry ? NewEntry : OldEntry;
-    BasicBlock *SplitEdgeBB = SplitEdge(EnteringBB, EntryBB, DT, LI);
-
-    // Once the edge between EnteringBB and EntryBB is split, two cases arise.
-    // The first is simple. The new block is inserted between EnteringBB and
-    // EntryBB. In this case no further action is needed. However it might
-    // happen (if the splitted edge is not critical) that the new block is
-    // inserted __after__ EntryBB causing the following situation:
-    //
-    // EnteringBB
-    //    _|_
-    //    | |
-    //    |  \-> some_other_BB_not_in_R
-    //    V
-    // EntryBB
-    //    |
-    //    V
-    // SplitEdgeBB
-    //
-    // In this case we need to swap the role of EntryBB and SplitEdgeBB.
-
-    // Check which case SplitEdge produced:
-    if (SplitEdgeBB->getTerminator()->getSuccessor(0) == EntryBB) {
-      // First (simple) case.
-      EnteringBB = SplitEdgeBB;
-    } else {
-      // Second (complicated) case.
-      NewEntry = SplitEdgeBB;
-      EnteringBB = EntryBB;
-    }
-
-    EnteringBB->setName("polly.entering.block");
-  }
-
-  if (NewEntry)
-    replaceScopAndRegionEntry(S, OldEntry, NewEntry);
-
-  // Create single exit edge if the region has multiple exit edges.
-  if (!R->getExitingBlock()) {
-    BasicBlock *NewExiting = createSingleExitEdge(R, P);
-    (void)NewExiting;
-    assert(NewExiting == R->getExitingBlock() &&
-           "Did not create a single exiting block");
+// Split the block into two successive blocks.
+//
+// Like llvm::SplitBlock, but also preserves RegionInfo
+static BasicBlock *splitBlock(BasicBlock *Old, Instruction *SplitPt,
+                              DominatorTree *DT, llvm::LoopInfo *LI,
+                              RegionInfo *RI) {
+  assert(Old && SplitPt);
+
+  // Before:
+  //
+  //  \   /  //
+  //   Old   //
+  //  /   \  //
+
+  BasicBlock *NewBlock = llvm::SplitBlock(Old, SplitPt, DT, LI);
+
+  if (RI) {
+    Region *R = RI->getRegionFor(Old);
+    RI->setRegionFor(NewBlock, R);
   }
 
-  return EnteringBB;
+  // After:
+  //
+  //   \   /    //
+  //    Old     //
+  //     |      //
+  //  NewBlock  //
+  //   /   \    //
+
+  return NewBlock;
 }
 
 void polly::splitEntryBlockForAlloca(BasicBlock *EntryBlock, Pass *P) {
   // Find first non-alloca instruction. Every basic block has a non-alloc
   // instruction, as every well formed basic block has a terminator.
   BasicBlock::iterator I = EntryBlock->begin();
   while (isa<AllocaInst>(I))
     ++I;
 
-  auto *DTWP = P->getAnalysisIfAvailable<DominatorTreeWrapperPass>();
+  auto *DTWP =
+      P ? P->getAnalysisIfAvailable<DominatorTreeWrapperPass>() : nullptr;
   auto *DT = DTWP ? &DTWP->getDomTree() : nullptr;
-  auto *LIWP = P->getAnalysisIfAvailable<LoopInfoWrapperPass>();
+  auto *LIWP = P ? P->getAnalysisIfAvailable<LoopInfoWrapperPass>() : nullptr;
   auto *LI = LIWP ? &LIWP->getLoopInfo() : nullptr;
+  auto RIP = P ? P->getAnalysisIfAvailable<RegionInfoPass>() : nullptr;
+  auto RI = RIP ? &RIP->getRegionInfo() : nullptr;
 
-  // SplitBlock updates DT, DF and LI.
-  BasicBlock *NewEntry = SplitBlock(EntryBlock, I, DT, LI);
-  if (RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>())
-    RIP->getRegionInfo().splitBlock(NewEntry, EntryBlock);
+  // splitBlock updates DT, DF, LI and RI.
+  splitBlock(EntryBlock, I, DT, LI, RI);
 }

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: while.begin:
+; CHECK-LABEL: while.begin.region_exiting:
+; CHECK:         br label %polly.merge_new_and_old
+
+; CHECK-LABEL: while.begin:
 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.entering.block
+; CHECK:  br i1 %tobool, label %while.end, label %polly.split_new_and_old
   br i1 %tobool, label %while.end, label %if
 
-; CHECK: polly.entering.block:
-; CHECK:   br label %polly.split_new_and_old
-
 ; CHECK: polly.split_new_and_old:
-; CHECK:   br i1 true, label %polly.start, label %if.split
+; CHECK:   br i1 true, label %polly.start, label %if
 
-; CHECK: if.split:
+; CHECK: if:
 if:                                               ; preds = %while.begin
 ; CHECK: %tobool2 = icmp eq i32 %b, 0
   %tobool2 = icmp eq i32 %b, 0
 ; CHECK: br i1 %tobool2, label %while.begin{{[a-zA-Z._]*}}, label %for.cond
   br i1 %tobool2, label %while.begin, label %for.cond
 
 for.cond:                                         ; preds = %for.inc, %if
   %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %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:      polly.merge_new_and_old:
-; CHECK-NEXT:  ret
-;
-; CHECK:      polly.start:
-; CHECK-NEXT:   store float 0.000000e+00, float* %tmp.0.phiops
+
+; CHECK-LABEL: exit:
+; CHECK-NEXT:    ret
+
+; CHECK-LABEL: polly.start:
+; CHECK-NEXT:    store float 0.000000e+00, float* %tmp.0.phiops
 
-; CHECK:      polly.merge:
-; CHECK-NEXT:   br label %polly.merge_new_and_old
+; CHECK-LABEL: polly.merge:
+; CHECK-NEXT:    br label %polly.merge_new_and_old
 
-; CHECK:      polly.stmt.bb1{{[0-9]*}}:
-; CHECK-NEXT:   %tmp.0.phiops.reload[[R1:[0-9]*]] = load float, float* %tmp.0.phiops
-; CHECK:        store float %tmp.0.phiops.reload[[R1]], float* %tmp.0.s2a
+; CHECK-LABEL: polly.stmt.bb1{{[0-9]*}}:
+; CHECK-NEXT:    %tmp.0.phiops.reload[[R1:[0-9]*]] = load float, float* %tmp.0.phiops
+; CHECK:         store float %tmp.0.phiops.reload[[R1]], float* %tmp.0.s2a
 
-; CHECK:      polly.stmt.bb1{{[0-9]*}}:
-; CHECK-NEXT:   %tmp.0.phiops.reload[[R2:[0-9]*]] = load float, float* %tmp.0.phiops
-; CHECK:        store float %tmp.0.phiops.reload[[R2]], float* %tmp.0.s2a
+; CHECK-LABEL: polly.stmt.bb1{{[0-9]*}}:
+; CHECK-NEXT:    %tmp.0.phiops.reload[[R2:[0-9]*]] = load float, float* %tmp.0.phiops
+; CHECK:         store float %tmp.0.phiops.reload[[R2]], float* %tmp.0.s2a
 
-; CHECK: polly.stmt.bb4:                                   ; preds = %polly.then3
-; CHECK:   %tmp[[R5:[0-9]*]]_p_scalar_ = load float, float* %scevgep, align 4, !alias.scope !0, !noalias !2
-; CHECK:   %tmp.0.s2a.reload[[R3:[0-9]*]] = load float, float* %tmp.0.s2a
-; CHECK:   %p_tmp[[R4:[0-9]*]] = fadd float %tmp.0.s2a.reload[[R3]], %tmp[[R5]]_p_scalar_
-; CHECK:   store float %p_tmp[[R4]], float* %tmp.0.phiops
+; CHECK-LABEL: polly.stmt.bb4:                                   ; preds = %polly.then3
+; CHECK:         %tmp[[R5:[0-9]*]]_p_scalar_ = load float, float* %scevgep, align 4, !alias.scope !0, !noalias !2
+; CHECK:         %tmp.0.s2a.reload[[R3:[0-9]*]] = load float, float* %tmp.0.s2a
+; CHECK:         %p_tmp[[R4:[0-9]*]] = fadd float %tmp.0.s2a.reload[[R3]], %tmp[[R5]]_p_scalar_
+; CHECK:         store float %p_tmp[[R4]], float* %tmp.0.phiops
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define void @f(float* %A, i32 %N) {
 bb:
   %tmp = sext i32 %N to i64
   br label %bb1
 

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:      polly.merge_new_and_old:
-; CHECK-NEXT:   %tmp.0.merge = phi float [ %tmp.0.final_reload, %polly.merge ], [ %tmp.0, %bb8 ]
-; CHECK-NEXT:   ret float %tmp.0.merge
-;
-; CHECK:      polly.start:
-; CHECK-NEXT:   store float 0.000000e+00, float* %tmp.0.phiops
+
+; 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-LABEL: polly.start:
+; CHECK-NEXT:    store float 0.000000e+00, float* %tmp.0.phiops
 
-; CHECK:      polly.merge:
-; CHECK-NEXT:   %tmp.0.final_reload = load float, float* %tmp.0.s2a
-; CHECK-NEXT:   br label %polly.merge_new_and_old
+; 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
 
-; CHECK:      polly.stmt.bb1{{[0-9]*}}:
-; CHECK-NEXT:   %tmp.0.phiops.reload[[R1:[0-9]*]] = load float, float* %tmp.0.phiops
-; CHECK-:       store float %tmp.0.phiops.reload[[R1]], float* %tmp.0.s2a
+; CHECK-LABEL: polly.stmt.bb1{{[0-9]*}}:
+; CHECK-NEXT:    %tmp.0.phiops.reload[[R1:[0-9]*]] = load float, float* %tmp.0.phiops
+; CHECK-:        store float %tmp.0.phiops.reload[[R1]], float* %tmp.0.s2a
 
-; CHECK:      polly.stmt.bb1{{[0-9]*}}:
-; CHECK-NEXT:   %tmp.0.phiops.reload[[R2:[0-9]*]] = load float, float* %tmp.0.phiops
-; CHECK:        store float %tmp.0.phiops.reload[[R2]], float* %tmp.0.s2a
+; CHECK-LABEL: polly.stmt.bb1{{[0-9]*}}:
+; CHECK-NEXT:    %tmp.0.phiops.reload[[R2:[0-9]*]] = load float, float* %tmp.0.phiops
+; CHECK:         store float %tmp.0.phiops.reload[[R2]], float* %tmp.0.s2a
 
-; CHECK: polly.stmt.bb4:                                   ; preds = %polly.then3
-; CHECK:   %tmp[[R5:[0-9]*]]_p_scalar_ = load float, float* %scevgep, align 4, !alias.scope !0, !noalias !2
-; CHECK:   %tmp.0.s2a.reload[[R3:[0-9]*]] = load float, float* %tmp.0.s2a
-; CHECK:   %p_tmp[[R4:[0-9]*]] = fadd float %tmp.0.s2a.reload[[R3]], %tmp[[R5]]_p_scalar_
-; CHECK:   store float %p_tmp[[R4]], float* %tmp.0.phiops
+; CHECK-LABEL: polly.stmt.bb4:                                   ; preds = %polly.then3
+; CHECK:         %tmp[[R5:[0-9]*]]_p_scalar_ = load float, float* %scevgep, align 4, !alias.scope !0, !noalias !2
+; CHECK:         %tmp.0.s2a.reload[[R3:[0-9]*]] = load float, float* %tmp.0.s2a
+; CHECK:         %p_tmp[[R4:[0-9]*]] = fadd float %tmp.0.s2a.reload[[R3]], %tmp[[R5]]_p_scalar_
+; CHECK:         store float %p_tmp[[R4]], float* %tmp.0.phiops
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 
 define float @f(float* %A, i32 %N) {
 bb:
   %tmp = sext i32 %N to i64
   br label %bb1
 

test/Isl/CodeGen/simple_non_single_entry.ll

for.i:
   %exitcond = icmp eq i64 %indvar.next, %N
   br i1 %exitcond, label %return, label %for.i
 
 return:
   fence seq_cst
   ret void
 }
 
-; CHECK: Create LLVM-IR from SCoPs' for region: 'next.split => polly.merge_new_and_old'
+; CHECK: Create LLVM-IR from SCoPs' for region: 'next => polly.merge_new_and_old'
 ; CHECK-CODE: polly.split_new_and_old
 ; CHECK-CODE: polly.merge_new_and_old