[Polly][Refactor] Cleanup runtime code generation

[jdoerfert]

Summary

+ Refactor the runtime condition build function
+ Use regexp in two test case.

[grosser]

Hi Johannes,

thanks a lot for putting the time to first improve the existing code before you add new features. I think this is very valuable in ensuring the code remains maintainable in the long run.

Regarding this patch, it seems the main contribution is that you factor most code into smaller helper functions. I think this is a good idea, as it makes the runOnScop() function a lot more readable.

It also seems your refactoring changes the way the run-time code is generated. Before we first built the run-time condition with a placeholder (i1 true) and then later replaced this placeholder with the actual run-time condition. Your new code now first generates the condition and then uses the result when introducing the run-time check. This change also has some semantic implications. Specifically, the code that evaluates the run-time condition is now inserted earlier. For the attached test case (

scop-is-never-executed.ll1 KBDownload

), this means evaluate the run-time condition even in cases, in which the actual scop is never executed. This seems to be a regression compared to the old code, right? Do you think we could get the same more readable code, even without these semantic changes?

I have a couple of more-detailed inline comments.

Cheers,
Tobias

[Refactor] Cleanup runtime code generation

What is "runtime code generation"? I think this abbreviation is misleading.

+ Refactor the runtime condition build function
+ Use regexp in two test case.

I think this commit message is rather short. If you could explain in two or three cases what kind of changes you did this would help both the people who skim through the commit messages and also people like me who want to understand the patch. Things I asked myself:

• What are the actual refactoring changes that have been applied. Why are they beneficial?
• Are there any semantic changes?

E.g.:

• Factor out code into helper functions to make runOnScop() function more readable.
• Change construction of run-time-check. Instead of first introducing a placeholder value that is later replaced by the actual condition, we first build the condition and then use it directly in the run-time check.
• Make analysis pass variables class variables. (Why is this useful?)

include/polly/CodeGen/IRBuilder.h

112 ↗

(On Diff #12967)

This looks good.

include/polly/CodeGen/Utils.h

35 ↗

(On Diff #12967)

This comment was really outdated. It is good that we replace it.

lib/CodeGen/IslCodeGeneration.cpp

578 ↗

(On Diff #12967)

Making these analysis pass definitions class variables seems a conceptually independent change. It possibly does not hurt in this patch, but if you believe tracking those analysis passes as class variables is better style, I wonder if we should not have an independent patch that does this kind of transformation all over Polly. This patch would help to educate other people about the reasons this style is preferred and could also be a reference in future patch reviews.

There are other similar uses in ScheduleOptimizer.cpp, ScopInfo.cpp.

Also, before writing such a patch, it may be good to discuss the reason why this change is preferred. I personally try to always make the life time of a variable as short as possible. This change goes against this goal. So it would be good to understand why you believe this is better? There may be very good reasons, which I may have missed. Is this e.g. to align our style with LLVM? Or just to have a more consistent style in Polly (our code is rather inconsistent)?

581 ↗

(On Diff #12967)

By moving the LoopAnnotator into class scop, we extend its lifetime. This means the code generation of different scops will use the same loop annotator. Hence, in case an earlier scop leaves the loop annotator in non-clear state, this may impact later scops.

Was this intentional?

593 ↗

(On Diff #12967)

Creating a new function for run time condition handling makes this code a lot more readable.

Two minor remarks:

• Please use RunTimeCondition instead of RTC, as this is not really a common expression.
• Run time conditions can conceptually be used (and hopefully will be used) for a lot more than delinearization. Hence, calling it delinearization condition is misleading. However, we could still use delinearization as an example or what a run time condition is or where it is used.

616 ↗

(On Diff #12967)

Very nice cleanup. This function is a lot more readable now.

618 ↗

(On Diff #12967)

Was adding this DEBUG statement intentional? I think it may be a little verbose for day-to-day use.

test/Isl/CodeGen/blas_sscal_simplified.ll

8 ↗

(On Diff #12967)

It is unclear what is tested in this test case. I assume this is the test case that broke previously. Could you add a comment to it to explain why it failed before. Something like.

This test case segfaulted previously due to us not properly supporting load instructions followed by zexts in the
run-time condition.

(Please replace by the actual problem)

test/Isl/CodeGen/multidim_2d_parametric_array_static_loop_bounds.ll

17 ↗

(On Diff #12967)

This test case explicitly tests that the computations for the run-time condition are created in the basic block that is named polly.split_new_and_old, the block in which we branch according to the run-time condition. This seems a good place to put those instructions.

It seems your patch changes this to now generate the instructions somewhere earlier. Where exactly? Was this intentional? In case it was, it would be good to explain the motivation/reason behind this.

Also, any changes to the generated IR seems suspicious in re-factorings that to my understanding aim to not change functionality.

test/Isl/CodeGen/run-time-condition-with-scev-parameters.ll

8 ↗

(On Diff #12967)

I just checked what has changed in the actual test case output and it seems the actual change is:

-; CHECK: %4 = icmp ne i64 0, %3
+; CHECK: %4 = icmp ne i64 %3, 0

Introducing the regexp seems not necessary here and also hides the actual change needed. In fact, I run this test case trying to understand why your refactoring caused the statement numbers to change.

[jdoerfert]

I will again look into the changed RTC location, namely where we generate the RTC instructions. I don't think it makes a difference but I will change it back to split_new_and_old if possible, or at least try to argue why we don't need that (LLVM optimizations do similar stuff all the time).

I also added a few inline comments because I do not agree with some of the review.

lib/CodeGen/IslCodeGeneration.cpp

578 ↗

(On Diff #12967)

A few thoughts to this commit (not all related to each other):

• Why do I need to extract non invasiv move of 4 variables in a refactoring patch? At some point the amount of work I'm supposed to put into "cleaning" my patches becomes ridiculous, especially compared to what else goes in.
• Polly is inconsistent here, we have both styles, local variables and class members, however the latter can "always" be used.
• The class I edit here has one function,...one. Where these variables are defined (in this one function) or as a memeber will only change the kind of comment we can add to their declaration.

581 ↗

(On Diff #12967)

Yes.

I'd say:

Don't leave anything in an unclean state and comment your variables like:
  "LoobAnnotator Annotator;"

Is there any reason (except the state thing) that would benefit from constructing a new one all the time?

593 ↗

(On Diff #12967)

• You don't like my variables names (even though they are clear abrivations of the full names) and now I have to change that?
• At the moment there is only delinearization, why should I paint a picture of the future in the description of a feature?

618 ↗

(On Diff #12967)

I like to see the endresult of the code generation if I debug the whole thing, if I'm the only one then I can remove the stmt.

test/Isl/CodeGen/blas_sscal_simplified.ll

8 ↗

(On Diff #12967)

I will add something.

test/Isl/CodeGen/multidim_2d_parametric_array_static_loop_bounds.ll

17 ↗

(On Diff #12967)

The first part (the BB where the RTC is generated) is a valid comment. I will look into that anyway but I think we can generate it again in split_new_and_old or we can argue LLVM will move it there anyway.
However, the second part (about the IR change) is not helping at all. If you test for unnamed variables every little thing can change the result, even stupid stuff like the ordering of the basic blocks in the function. This would clearly be without functionality change but it could trigger your test...

test/Isl/CodeGen/run-time-condition-with-scev-parameters.ll

8 ↗

(On Diff #12967)

Even if it doesn't change the statement numbers, someone at somepoint will and he/she/it has to fix test cases like this with no good reason to hardcode these numbers. We do not care if it is called %1 or %0 here, why test for it?!?

[jdoerfert]

Updated version + additional code placement test case

[jdoerfert]

The difference to the first version is in the "simplifyRegion" function. It will now ensure that the unique entering edge is also unconditional, thus when we put our runtime check code into the entering block it will always execute at least the rtc guard.

[dpeixott]

Minor typo. Otherwise the patch looks reasonable to me.

include/polly/CodeGen/IRBuilder.h

99 ↗

(On Diff #13405)

It looks like these comments are just commented out code. Could probably delete them as long as you are cleaning up.

lib/CodeGen/IslCodeGeneration.cpp

586 ↗

(On Diff #13405)

typo save/unsave -> safe/unsafe

[jdoerfert]

@grosser: Can I push this if I change the commit according to davids comments?

[grosser]

Thanks Johannes for the update.

I like the solution with adapting the simplifyRegion function. It avoids the regression the earlier patch introduced and still allows us to build the run-time condition before splitting the region.

Some minor points that are still open (some mentioned before):

• You talk twice about "runtime code generation". This term seems wrong. I suppose you mean "run-time-check generation"?

• It would be great if the commit message contains a brief description of the changes you applied, possibly mentioning the need to ensure an unconditional entry edge.

• You still have the regexp change in this commit. I would prefer if you do not apply them in this commit, as they hide the actual code changes. You can commit them immediately after, if you like. (In fact, if you add some checks on the bb labels as well, the tests will really nicely document your changes)

Two more areas where I would like to learn more about your motivations (both not blocking the commit), to understand if/what I should pay attention to when writing patches myself:

• Why is moving variables to class scope better. Because we can document them there?

• I would like to understand in which situations we needed REGEXPs? For all checks? Only unnamed checks?

include/polly/CodeGen/Utils.h

31 ↗

(On Diff #13405)

We already wasted too much time on this, if you feel strong about this, leave it as it is.

However, I still think we should use a more descriptive name instead of RTC. To explain you this is not just me not _liking_ your names, I cite the LLVM developer policy:

"Avoid abbreviations unless they are well known"

http://llvm.org/docs/CodingStandards.html#name-types-functions-variables-and-enumerators-properly

In LLVM there are a couple of uses of RT to abbreviate run time, and in fact RTCheck or RTCondition is a lot clearer to me. Maybe that works for you as well.

include/polly/Support/ScopHelper.h

55 ↗

(On Diff #13405)

typo: unconditional

lib/CodeGen/IslCodeGeneration.cpp

578 ↗

(On Diff #13405)

typo: annotator

581 ↗

(On Diff #12967)

I don't think the overhead of (re)constructing it is measurable.

In terms of state, I was not talking about clean, but clear. Assuming, the LoopAnnotator
would contain a std::set, which would be _cleared_ on destruction, your change could cause old pointers to remain in this set unintended.

Keeping the live-time of variables short, avoids the need to think about such changes. In this case I looked into the LoopAnnotator and moving it seems to not break any assumptions.

[jdoerfert]

comment

include/polly/CodeGen/Utils.h

31 ↗

(On Diff #13405)

To much time,... indeed.

Wrt. "well know":

https://software.intel.com/sites/products/documentation/doclib/iss/2013/compiler/cpp-lin/GUID-65F1FC0F-16CB-441E-8E38-3A49DED905F6.htm
http://msdn.microsoft.com/en-us/library/6kasb93x.aspx

I don't mind you changing my variable names to whatever if you think that helps to understand the code or is otherwise contradicting the developer policy but I don't see it here. (Btw. there are other variable names not according to the policy, you could change those too.)

[jdoerfert]

Closed by commit rL217508 (authored by @jdoerfert).

polly/trunk/include/polly/CodeGen/IRBuilder.h

 private:
   class LoopAnnotator *Annotator;
 };
 
 // TODO: We should not name instructions in NDEBUG builds.
 //
 // We currently always name instructions, as the polly test suite currently
 // matches for certain names.
-//
-// typedef PollyBuilderInserter<false> IRInserter;
-// typedef llvm::IRBuilder<false, llvm::ConstantFolder, IRInserter>
-// PollyIRBuilder;
 typedef PollyBuilderInserter<true> IRInserter;
 typedef llvm::IRBuilder<true, llvm::ConstantFolder, IRInserter> PollyIRBuilder;
+
+/// @brief Return an IR builder pointed before the @p BB terminator.
+static inline PollyIRBuilder createPollyIRBuilder(llvm::BasicBlock *BB,
+                                                  LoopAnnotator &LA) {
+  PollyIRBuilder Builder(BB->getContext(), llvm::ConstantFolder(),
+                         polly::IRInserter(LA));
+  Builder.SetInsertPoint(BB->getTerminator());
+  return Builder;
+}
 }
 #endif

polly/trunk/include/polly/CodeGen/Utils.h

 // This file contains utility functions for the code generation.
 //===----------------------------------------------------------------------===//
 
 #ifndef POLLY_CODEGEN_UTILS_H
 #define POLLY_CODEGEN_UTILS_H
 
 namespace llvm {
 class Pass;
+class Value;
 class BasicBlock;
 }
 
 namespace polly {
 
 class Scop;
 
-/// @brief Execute a Scop conditionally.
+/// @brief Execute a Scop conditionally wrt @p RTC.
 ///
 /// In the CFG the optimized code of the Scop is generated next to the
 /// original code. Both the new and the original version of the code remain
-/// in the CFG. A branch statement decides which version is executed.
-/// For now, we always execute the new version (the old one is dead code
-/// eliminated by the cleanup passes). In the future we may decide to execute
-/// the new version only if certain run time checks succeed. This will be
-/// useful to support constructs for which we cannot prove all assumptions at
-/// compile time.
+/// in the CFG. A branch statement decides which version is executed based on
+/// the runtime value of @p RTC.
 ///
 /// Before transformation:
 ///
 ///                        bb0
 ///                         |
 ///                     orig_scop
 ///                         |
 ///                        bb1
 ///
 /// After transformation:
 ///                        bb0
 ///                         |
 ///                  polly.splitBlock
 ///                     /       \.
 ///                     |     startBlock
 ///                     |        |
 ///               orig_scop   new_scop
 ///                     \      /
 ///                      \    /
 ///                        bb1 (joinBlock)
 ///
-/// @param S The Scop to execute conditionally.
-/// @param PassInfo A reference to the pass calling this function.
-/// @return BasicBlock The 'StartBlock' to which new code can be added.
-llvm::BasicBlock *executeScopConditionally(Scop &S, llvm::Pass *PassInfo);
+/// @param S   The Scop to execute conditionally.
+/// @param P   A reference to the pass calling this function.
+/// @param RTC The runtime condition checked before executing the new SCoP.
+///
+/// @return The 'StartBlock' to which new code can be added.
+llvm::BasicBlock *executeScopConditionally(Scop &S, llvm::Pass *P,
+                                           llvm::Value *RTC);
 }
 #endif

polly/trunk/include/polly/Support/ScopHelper.h

 /// @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 entry edge
-///        and a single exit edge.
+/// @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 S  The SCoP that is simplified.
 /// @param P  The pass that is currently running.
 ///
-void simplifyRegion(polly::Scop *S, llvm::Pass *P);
+/// @return The unique entering block for the region.
+llvm::BasicBlock *simplifyRegion(polly::Scop *S, llvm::Pass *P);
 
 /// @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

polly/trunk/lib/CodeGen/CodeGeneration.cpp

public:
   bool runOnScop(Scop &S) {
     ParallelLoops.clear();
 
     assert(!S.getRegion().isTopLevelRegion() &&
            "Top level regions are not supported");
 
     simplifyRegion(&S, this);
 
-    BasicBlock *StartBlock = executeScopConditionally(S, this);
+    Value *RTC = ConstantInt::getTrue(S.getSE()->getContext());
+    BasicBlock *StartBlock = executeScopConditionally(S, this, RTC);
 
     PollyIRBuilder Builder(StartBlock->begin());
 
     ClastStmtCodeGen CodeGen(&S, Builder, this);
     CloogInfo &C = getAnalysis<CloogInfo>();
     CodeGen.codegen(C.getClast());
 
     ParallelLoops.insert(ParallelLoops.begin(),

polly/trunk/lib/CodeGen/IslCodeGeneration.cpp

 
 namespace {
 class IslCodeGeneration : public ScopPass {
 public:
   static char ID;
 
   IslCodeGeneration() : ScopPass(ID) {}
 
+  /// @name The analysis passes we need to generate code.
+  ///
+  ///{
+  LoopInfo *LI;
+  IslAstInfo *AI;
+  DominatorTree *DT;
+  ScalarEvolution *SE;
+  ///}
+
+  /// @brief The loop annotator to generate llvm.loop metadata.
+  LoopAnnotator Annotator;
+
+  /// @brief Build the runtime condition.
+  ///
+  /// Build the condition that evaluates at run-time to true iff all
+  /// assumptions taken for the SCoP hold, and to false otherwise.
+  ///
+  /// @return A value evaluating to true/false if execution is save/unsafe.
+  Value *buildRTC(PollyIRBuilder &Builder, IslExprBuilder &ExprBuilder) {
+    Builder.SetInsertPoint(Builder.GetInsertBlock()->getTerminator());
+    Value *RTC = ExprBuilder.create(AI->getRunCondition());
+    return Builder.CreateIsNotNull(RTC);
+  }
+
   bool runOnScop(Scop &S) {
-    LoopInfo &LI = getAnalysis<LoopInfo>();
-    IslAstInfo &AstInfo = getAnalysis<IslAstInfo>();
-    ScalarEvolution &SE = getAnalysis<ScalarEvolution>();
-    DominatorTree &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    LI = &getAnalysis<LoopInfo>();
+    AI = &getAnalysis<IslAstInfo>();
+    DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+    SE = &getAnalysis<ScalarEvolution>();
 
     assert(!S.getRegion().isTopLevelRegion() &&
            "Top level regions are not supported");
 
-    simplifyRegion(&S, this);
-
-    BasicBlock *StartBlock = executeScopConditionally(S, this);
-    isl_ast_node *Ast = AstInfo.getAst();
-    LoopAnnotator Annotator;
-    PollyIRBuilder Builder(StartBlock->getContext(), llvm::ConstantFolder(),
-                           polly::IRInserter(Annotator));
-    Builder.SetInsertPoint(StartBlock->begin());
-
-    IslNodeBuilder NodeBuilder(Builder, Annotator, this, LI, SE, DT);
+    BasicBlock *EnteringBB = simplifyRegion(&S, this);
+    PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
 
-    Builder.SetInsertPoint(StartBlock->getSinglePredecessor()->begin());
+    IslNodeBuilder NodeBuilder(Builder, Annotator, this, *LI, *SE, *DT);
     NodeBuilder.addMemoryAccesses(S);
     NodeBuilder.addParameters(S.getContext());
-    // Build condition that evaluates at run-time if all assumptions taken
-    // for the scop hold. If we detect some assumptions do not hold, the
-    // original code is executed.
-    Value *V = NodeBuilder.getExprBuilder().create(AstInfo.getRunCondition());
-    Value *Zero = ConstantInt::get(V->getType(), 0);
-    V = Builder.CreateICmp(CmpInst::ICMP_NE, Zero, V);
-    BasicBlock *PrevBB = StartBlock->getUniquePredecessor();
-    BranchInst *Branch = dyn_cast<BranchInst>(PrevBB->getTerminator());
-    Branch->setCondition(V);
+
+    Value *RTC = buildRTC(Builder, NodeBuilder.getExprBuilder());
+    BasicBlock *StartBlock = executeScopConditionally(S, this, RTC);
     Builder.SetInsertPoint(StartBlock->begin());
 
-    NodeBuilder.create(Ast);
+    NodeBuilder.create(AI->getAst());
     return true;
   }
 
   virtual void printScop(raw_ostream &OS) const {}
 
   virtual void getAnalysisUsage(AnalysisUsage &AU) const {
     AU.addRequired<DominatorTreeWrapperPass>();
     AU.addRequired<IslAstInfo>();

polly/trunk/lib/CodeGen/Utils.cpp

 #include "polly/CodeGen/IRBuilder.h"
 #include "polly/ScopInfo.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 using namespace llvm;
 
-BasicBlock *polly::executeScopConditionally(Scop &S, Pass *PassInfo) {
+BasicBlock *polly::executeScopConditionally(Scop &S, Pass *P, Value *RTC) {
   BasicBlock *StartBlock, *SplitBlock, *NewBlock;
   Region &R = S.getRegion();
   PollyIRBuilder Builder(R.getEntry());
-  DominatorTree &DT =
-      PassInfo->getAnalysis<DominatorTreeWrapperPass>().getDomTree();
-  RegionInfo &RI = PassInfo->getAnalysis<RegionInfoPass>().getRegionInfo();
-  LoopInfo &LI = PassInfo->getAnalysis<LoopInfo>();
+  DominatorTree &DT = P->getAnalysis<DominatorTreeWrapperPass>().getDomTree();
+  RegionInfo &RI = P->getAnalysis<RegionInfoPass>().getRegionInfo();
+  LoopInfo &LI = P->getAnalysis<LoopInfo>();
 
   // 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(), PassInfo);
+  NewBlock = SplitEdge(R.getEnteringBlock(), R.getEntry(), P);
   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);
if (DT.dominates(R.getEntry(), NewBlock)) {
     SplitBlock = NewBlock;
   }
 
   SplitBlock->setName("polly.split_new_and_old");
   Function *F = SplitBlock->getParent();
   StartBlock = BasicBlock::Create(F->getContext(), "polly.start", F);
   SplitBlock->getTerminator()->eraseFromParent();
   Builder.SetInsertPoint(SplitBlock);
-  Builder.CreateCondBr(Builder.getTrue(), StartBlock, R.getEntry());
+  Builder.CreateCondBr(RTC, StartBlock, R.getEntry());
   if (Loop *L = LI.getLoopFor(SplitBlock))
     L->addBasicBlockToLoop(StartBlock, LI.getBase());
   DT.addNewBlock(StartBlock, SplitBlock);
   Builder.SetInsertPoint(StartBlock);
 
   BasicBlock *MergeBlock;
 
   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(), PassInfo);
+    MergeBlock = SplitEdge(R.getExitingBlock(), R.getExit(), P);
     // 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);
   }
 
   Builder.CreateBr(MergeBlock);
   MergeBlock->setName("polly.merge_new_and_old");
 
   if (DT.dominates(SplitBlock, MergeBlock))
     DT.changeImmediateDominator(MergeBlock, SplitBlock);
   return StartBlock;
 }

polly/trunk/lib/Support/ScopHelper.cpp

BasicBlock *polly::createSingleExitEdge(Region *R, Pass *P) {
   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);
 
   return SplitBlockPredecessors(BB, Preds, ".region", P);
 }
 
-void polly::simplifyRegion(Scop *S, Pass *P) {
+BasicBlock *polly::simplifyRegion(Scop *S, Pass *P) {
   Region *R = &S->getRegion();
 
+  // The entering block for the region.
+  BasicBlock *EnteringBB = R->getEnteringBlock();
+
   // Create single entry edge if the region has multiple entry edges.
-  if (!R->getEnteringBlock()) {
+  if (!EnteringBB) {
     BasicBlock *OldEntry = R->getEntry();
     BasicBlock *NewEntry = SplitBlock(OldEntry, OldEntry->begin(), P);
 
     for (ScopStmt *Stmt : *S)
       if (Stmt->getBasicBlock() == OldEntry) {
         Stmt->setBasicBlock(NewEntry);
         break;
       }
 
     R->replaceEntryRecursive(NewEntry);
+    EnteringBB = OldEntry;
+  }
+
+  // Create an unconditional entry edge.
+  if (EnteringBB->getTerminator()->getNumSuccessors() != 1) {
+    EnteringBB = SplitEdge(EnteringBB, R->getEntry(), P);
+    EnteringBB->setName("polly.entering.block");
   }
 
   // Create single exit edge if the region has multiple exit edges.
   if (!R->getExitingBlock()) {
     BasicBlock *NewExit = createSingleExitEdge(R, P);
 
     for (auto &&SubRegion : *R)
       SubRegion->replaceExitRecursive(NewExit);
   }
+
+  return EnteringBB;
 }
 
 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;
 
   // SplitBlock updates DT, DF and LI.
   BasicBlock *NewEntry = SplitBlock(EntryBlock, I, P);
   if (RegionInfoPass *RIP = P->getAnalysisIfAvailable<RegionInfoPass>())
     RIP->getRegionInfo().splitBlock(NewEntry, EntryBlock);
 }

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

+; RUN: opt %loadPolly -polly-codegen-isl < %s
+;
+; Regression test for a bug in the runtime check generation.
+
+; This was extracted from the blas testcase. It crashed in one
+; part of the runtime check generation at some point. To be
+; precise, we couldn't find a suitable block to put the RTC code in.
+;
+; int sscal(int n, float sa, float *sx) {
+;   for(int i=0; i<n; i++, sx++)
+;     *sx *= sa;
+;   return 0;
+; }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define i32 @sscal(i32 %n, float %sa, float* %sx) {
+entry:
+  br label %entry.split
+
+entry.split:                                      ; preds = %entry
+  %cmp1 = icmp sgt i32 %n, 0
+  br i1 %cmp1, label %for.body.lr.ph, label %for.end
+
+for.body.lr.ph:                                   ; preds = %entry.split
+  %0 = zext i32 %n to i64
+  br label %for.body
+
+for.body:                                         ; preds = %for.body.lr.ph, %for.body
+  %indvar = phi i64 [ 0, %for.body.lr.ph ], [ %indvar.next, %for.body ]
+  %sx.addr.02 = getelementptr float* %sx, i64 %indvar
+  %tmp = load float* %sx.addr.02, align 4
+  %mul = fmul float %tmp, %sa
+  store float %mul, float* %sx.addr.02, align 4
+  %indvar.next = add i64 %indvar, 1
+  %exitcond = icmp ne i64 %indvar.next, %0
+  br i1 %exitcond, label %for.body, label %for.cond.for.end_crit_edge
+
+for.cond.for.end_crit_edge:                       ; preds = %for.body
+  br label %for.end
+
+for.end:                                          ; preds = %for.cond.for.end_crit_edge, %entry.split
+  ret i32 0
+}

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

 ; RUN: opt %loadPolly -polly-codegen-isl -S -polly-delinearize < %s | FileCheck %s
 target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 ; Derived from the following code:
 ;
 ; void foo(long n, long m, double A[n][m]) {
 ;   for (long i = 0; i < 100; i++)
 ;     for (long j = 0; j < 150; j++)
 ;       A[i][j] = 1.0;
 ; }
-
-; CHECK: polly.split_new_and_old:
+;
+; CHECK: entry:
 ; CHECK: %0 = icmp sge i64 %m, 150
 ; CHECK: %1 = select i1 %0, i64 1, i64 0
-; CHECK: %2 = icmp ne i64 0, %1
+; CHECK: %2 = icmp ne i64 %1, 0
+; CHECK: polly.split_new_and_old:
 ; CHECK: br i1 %2, label %polly.start, label %for.i
 
 define void @foo(i64 %n, i64 %m, double* %A) {
 entry:
   br label %for.i
 
 for.i:
   %i = phi i64 [ 0, %entry ], [ %i.inc, %for.i.inc ]

polly/trunk/test/Isl/CodeGen/run-time-condition-with-scev-parameters.ll

 ; RUN: opt %loadPolly -polly-codegen-isl -S -polly-delinearize < %s | FileCheck %s
 ; RUN: opt %loadPolly -polly-codegen-isl -S -polly-delinearize -polly-codegen-scev < %s | FileCheck %s
 
 ; CHECK: %1 = zext i32 %n to i64
 ; CHECK: %2 = icmp sge i64 %1, 1
 ; CHECK: %3 = select i1 %2, i64 1, i64 0
-; CHECK: %4 = icmp ne i64 0, %3
+; CHECK: %4 = icmp ne i64 %3, 0
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 define void @init_array(i32 %n, double* %data) {
 entry:
   %0 = zext i32 %n to i64
   br label %for.body4

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

+; RUN: opt %loadPolly -polly-codegen-isl -S -polly-delinearize < %s | FileCheck %s
+; RUN: opt %loadPolly -polly-codegen-isl -S -polly-delinearize -polly-codegen-scev < %s | FileCheck %s
+
+; Verify that we generate the runtime check code after the conditional branch
+; in the SCoP region entering block (here %entry).
+;
+; CHECK: entry:
+; CHECK: zext i32 %n to i64
+; CHECK: br i1 false
+;
+; CHECK: %[[T0:[._a-zA-Z0-9]]] = zext i32 %n to i64
+; CHECK: %[[T1:[._a-zA-Z0-9]]] = icmp sge i64 %[[T0]], 1
+; CHECK: %[[T2:[._a-zA-Z0-9]]] = select i1 %[[T1]], i64 1, i64 0
+; CHECK: %[[T3:[._a-zA-Z0-9]]] = icmp ne i64 %[[T2]], 0
+
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-unknown-linux-gnu"
+
+define void @init_array(i32 %n, double* %data) {
+entry:
+  %0 = zext i32 %n to i64
+  br i1 false, label %for.end10, label %for.body4
+
+for.body4:                                        ; preds = %for.body4, %entry
+  %indvar1 = phi i64 [ %indvar.next2, %for.body4 ], [ 0, %entry ]
+  %.moved.to.for.body4 = mul i64 %0, %indvar1
+  %1 = add i64 %.moved.to.for.body4, 0
+  %arrayidx7 = getelementptr double* %data, i64 %1
+  store double undef, double* %arrayidx7, align 8
+  %indvar.next2 = add i64 %indvar1, 1
+  br i1 false, label %for.body4, label %for.end10
+
+for.end10:                                        ; preds = %for.body4
+  ret void
+}