[CodeGen] Break critical edge from RTC to original loop.

[efriedma]

Summary

This makes polly generate a CFG which is closer to what we want in LLVM IR, with a loop preheader for the original loop. This is just a cleanup, but it exposes some fragile assumptions.

I'm not completely happy with the changes related to expandCodeFor; RTCBB->getTerminator() is basically a random insertion point which happens to work due to the way we generate runtime checks. I'm not sure what the right answer looks like, though.

[grosser]

Hi Eli,

this change looks good to me, besides some minor comments. Can you possibly test this change also with POLLY_ENABLE_GPGPU_CODEGEN=ON.

Best,
Tobias

PS: Can you possibly add the [Polly] tag to future phabricator reviews. This is mostly to help people on the mailing list, as phabricator does not add the project name in its review messages.

include/polly/CodeGen/BlockGenerators.h

85 ↗

(On Diff #76143)

Please document StartBlock.

include/polly/CodeGen/IslExprBuilder.h

128 ↗

(On Diff #76143)

Could you document StartBlock?

(I know not all parameters are documented. Besides this obviously not being good, this seems useful especially for the change at discussion)

include/polly/Support/ScopHelper.h

348 ↗

(On Diff #76143)

Could you document RTCBB?

lib/CodeGen/Utils.cpp

218 ↗

(On Diff #76143)

This looks good to me.

lib/Support/ScopHelper.cpp

232 ↗

(On Diff #76143)

I like that this patch makes the insert position of new instructions explicit, as the old code was clearly very fragile.

This change exposes really an unnecessary strong connection between the insert location and the run-time block where we currently insert code to. I wonder if we not even want to just name this InsertBlock instead of RTCBB.

[efriedma]

lib/Support/ScopHelper.cpp

232 ↗

(On Diff #76143)

I'm currently not completely sure what the intent here actually is... the code in question is exercised by precisely one regression test, and there aren't any comments explaining the logic.

I think it makes sense to make the variable name reflect the actual value; if someone does come through and clean this up at some point, they can rename it to something appropriate, or make the function take an actual insertion point as a parameter.

[efriedma]

Address review comments. Now builds with POLLY_ENABLE_GPGPU_CODEGEN.

[grosser]

OK. We can leave this as RTCBB. I would like to see this cleaned up, but this does not need to hold back this patch. I might improve this and add documentation when I get to it. Feel to commit this as it is.

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

public:
   /// @param ScalarMap   Map from scalars to their demoted location.
   /// @param PHIOpMap    Map from PHIs to their demoted operand location.
   /// @param EscapeMap   Map from scalars to their escape users and locations.
   /// @param GlobalMap   A mapping from llvm::Values used in the original scop
   ///                    region to a new set of llvm::Values. Each reference to
   ///                    an original value appearing in this mapping is replaced
   ///                    with the new value it is mapped to.
   /// @param ExprBuilder An expression builder to generate new access functions.
+  /// @param StartBlock  The first basic block after the RTC.
   BlockGenerator(PollyIRBuilder &Builder, LoopInfo &LI, ScalarEvolution &SE,
                  DominatorTree &DT, ScalarAllocaMapTy &ScalarMap,
                  ScalarAllocaMapTy &PHIOpMap, EscapeUsersAllocaMapTy &EscapeMap,
-                 ValueMapT &GlobalMap, IslExprBuilder *ExprBuilder = nullptr);
+                 ValueMapT &GlobalMap, IslExprBuilder *ExprBuilder,
+                 BasicBlock *StartBlock);
 
   /// Copy the basic block.
   ///
   /// This copies the entire basic block and updates references to old values
   /// with references to new values, as defined by GlobalMap.
   ///
   /// @param Stmt        The block statement to code generate.
   /// @param LTS         A map from old loops to new induction variables as
protected:
   /// Map from instructions to their escape users as well as the alloca.
   EscapeUsersAllocaMapTy &EscapeMap;
 
   /// A map from llvm::Values referenced in the old code to a new set of
   ///        llvm::Values, which is used to replace these old values during
   ///        code generation.
   ValueMapT &GlobalMap;
 
+  /// The first basic block after the RTC.
+  BasicBlock *StartBlock;
+
   /// Split @p BB to create a new one we can use to clone @p BB in.
   BasicBlock *splitBB(BasicBlock *BB);
 
   /// Copy the given basic block.
   ///
   /// @param Stmt      The statement to code generate.
   /// @param BB        The basic block to code generate.
   /// @param BBMap     A mapping from old values to their new values in this

polly/trunk/include/polly/CodeGen/IslExprBuilder.h

public:
 
   /// Set the isl_id to ScopArrayInfo map.
   ///
   /// @param NewIDToSAI The new isl_id to ScopArrayInfo map to use.
   void setIDToSAI(IDToScopArrayInfoTy *NewIDToSAI) { IDToSAI = NewIDToSAI; }
 
   /// Construct an IslExprBuilder.
   ///
-  /// @param Builder The IRBuilder used to construct the isl_ast_expr[ession].
-  ///                The insert location of this IRBuilder defines WHERE the
-  ///                corresponding LLVM-IR is generated.
-  ///
-  /// @param IDToValue The isl_ast_expr[ession] may reference parameters or
-  ///                  variables (identified by an isl_id). The IDTOValue map
-  ///                  specifies the LLVM-IR Values that correspond to these
-  ///                  parameters and variables.
+  /// @param Builder     The IRBuilder used to construct the
+  ///                    isl_ast_expr[ession]. The insert location of this
+  ///                    IRBuilder defines WHERE the  corresponding LLVM-IR
+  ///                    is generated.
+  /// @param IDToValue   The isl_ast_expr[ession] may reference parameters or
+  ///                    variables (identified by an isl_id). The IDTOValue map
+  ///                    specifies the LLVM-IR Values that correspond to these
+  ///                    parameters and variables.
+  /// @param GlobalMap   A mapping from llvm::Values used in the original scop
+  ///                    region to a new set of llvm::Values.
+  /// @param DL          DataLayout for the current Module.
+  /// @param SE          ScalarEvolution analysis for the current function.
+  /// @param DT          DominatorTree analysis for the current function.
+  /// @param LI          LoopInfo analysis for the current function.
+  /// @param StartBlock The first basic block after the RTC.
   IslExprBuilder(Scop &S, PollyIRBuilder &Builder, IDToValueTy &IDToValue,
                  ValueMapT &GlobalMap, const llvm::DataLayout &DL,
                  llvm::ScalarEvolution &SE, llvm::DominatorTree &DT,
-                 llvm::LoopInfo &LI);
+                 llvm::LoopInfo &LI, llvm::BasicBlock *StartBlock);
 
   /// Create LLVM-IR for an isl_ast_expr[ession].
   ///
   /// @param Expr The ast expression for which we generate LLVM-IR.
   ///
   /// @return The llvm::Value* containing the result of the computation.
   llvm::Value *create(__isl_take isl_ast_expr *Expr);
 
private:
   PollyIRBuilder &Builder;
   IDToValueTy &IDToValue;
   ValueMapT &GlobalMap;
 
   const llvm::DataLayout &DL;
   llvm::ScalarEvolution &SE;
   llvm::DominatorTree &DT;
   llvm::LoopInfo &LI;
+  llvm::BasicBlock *StartBlock;
 
   llvm::Value *createOp(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpUnary(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpAccess(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpBin(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpNAry(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpSelect(__isl_take isl_ast_expr *Expr);
   llvm::Value *createOpICmp(__isl_take isl_ast_expr *Expr);

polly/trunk/include/polly/CodeGen/IslNodeBuilder.h

 ///                         references?
 isl_stat addReferencesFromStmt(const ScopStmt *Stmt, void *UserPtr,
                                bool CreateScalarRefs = true);
 
 class IslNodeBuilder {
 public:
   IslNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, Pass *P,
                  const DataLayout &DL, LoopInfo &LI, ScalarEvolution &SE,
-                 DominatorTree &DT, Scop &S)
+                 DominatorTree &DT, Scop &S, BasicBlock *StartBlock)
       : S(S), Builder(Builder), Annotator(Annotator),
-        ExprBuilder(S, Builder, IDToValue, ValueMap, DL, SE, DT, LI),
+        ExprBuilder(S, Builder, IDToValue, ValueMap, DL, SE, DT, LI,
+                    StartBlock),
         BlockGen(Builder, LI, SE, DT, ScalarMap, PHIOpMap, EscapeMap, ValueMap,
-                 &ExprBuilder),
-        RegionGen(BlockGen), P(P), DL(DL), LI(LI), SE(SE), DT(DT) {}
+                 &ExprBuilder, StartBlock),
+        RegionGen(BlockGen), P(P), DL(DL), LI(LI), SE(SE), DT(DT),
+        StartBlock(StartBlock) {}
 
   virtual ~IslNodeBuilder() {}
 
   void addParameters(__isl_take isl_set *Context);
 
   /// Generate code that evaluates @p Condition at run-time.
   ///
   /// This function is typically called to generate the LLVM-IR for the
protected:
   /// The generator used to copy a non-affine region.
   RegionGenerator RegionGen;
 
   Pass *const P;
   const DataLayout &DL;
   LoopInfo &LI;
   ScalarEvolution &SE;
   DominatorTree &DT;
+  BasicBlock *StartBlock;
 
   /// The current iteration of out-of-scop loops
   ///
   /// This map provides for a given loop a llvm::Value that contains the current
   /// loop iteration.
   LoopToScevMapT OutsideLoopIterations;
 
   // This maps an isl_id* to the Value* it has in the generated program. For now

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

 ///
 /// This wrapper will internally call the SCEVExpander but also makes sure that
 /// all additional features not represented in SCEV (e.g., SDiv/SRem are not
 /// black boxes but can be part of the function) will be expanded correctly.
 ///
 /// The parameters are the same as for the creation of a SCEVExpander as well
 /// as the call to SCEVExpander::expandCodeFor:
 ///
-/// @param S    The current Scop.
-/// @param SE   The Scalar Evolution pass.
-/// @param DL   The module data layout.
-/// @param Name The suffix added to the new instruction names.
-/// @param E    The expression for which code is actually generated.
-/// @param Ty   The type of the resulting code.
-/// @param IP   The insertion point for the new code.
-/// @param VMap A remaping of values used in @p E.
+/// @param S     The current Scop.
+/// @param SE    The Scalar Evolution pass.
+/// @param DL    The module data layout.
+/// @param Name  The suffix added to the new instruction names.
+/// @param E     The expression for which code is actually generated.
+/// @param Ty    The type of the resulting code.
+/// @param IP    The insertion point for the new code.
+/// @param VMap  A remaping of values used in @p E.
+/// @param RTCBB The last block of the RTC. Used to insert loop-invariant
+///              instructions in rare cases.
 llvm::Value *expandCodeFor(Scop &S, llvm::ScalarEvolution &SE,
                            const llvm::DataLayout &DL, const char *Name,
                            const llvm::SCEV *E, llvm::Type *Ty,
-                           llvm::Instruction *IP, ValueMapT *VMap = nullptr);
+                           llvm::Instruction *IP, ValueMapT *VMap,
+                           llvm::BasicBlock *RTCBB);
 
 /// Check if the block is a error block.
 ///
 /// A error block is currently any block that fullfills at least one of
 /// the following conditions:
 ///
 ///  - It is terminated by an unreachable instruction
 ///  - It contains a call to a non-pure function that is not immediately

polly/trunk/lib/CodeGen/BlockGenerators.cpp

static cl::opt<bool> Aligned("enable-polly-aligned",
                              cl::Hidden, cl::init(false), cl::ZeroOrMore,
                              cl::cat(PollyCategory));
 
 static cl::opt<bool> DebugPrinting(
     "polly-codegen-add-debug-printing",
     cl::desc("Add printf calls that show the values loaded/stored."),
     cl::Hidden, cl::init(false), cl::ZeroOrMore, cl::cat(PollyCategory));
 
-BlockGenerator::BlockGenerator(PollyIRBuilder &B, LoopInfo &LI,
-                               ScalarEvolution &SE, DominatorTree &DT,
-                               ScalarAllocaMapTy &ScalarMap,
-                               ScalarAllocaMapTy &PHIOpMap,
-                               EscapeUsersAllocaMapTy &EscapeMap,
-                               ValueMapT &GlobalMap,
-                               IslExprBuilder *ExprBuilder)
+BlockGenerator::BlockGenerator(
+    PollyIRBuilder &B, LoopInfo &LI, ScalarEvolution &SE, DominatorTree &DT,
+    ScalarAllocaMapTy &ScalarMap, ScalarAllocaMapTy &PHIOpMap,
+    EscapeUsersAllocaMapTy &EscapeMap, ValueMapT &GlobalMap,
+    IslExprBuilder *ExprBuilder, BasicBlock *StartBlock)
     : Builder(B), LI(LI), SE(SE), ExprBuilder(ExprBuilder), DT(DT),
       EntryBB(nullptr), PHIOpMap(PHIOpMap), ScalarMap(ScalarMap),
-      EscapeMap(EscapeMap), GlobalMap(GlobalMap) {}
+      EscapeMap(EscapeMap), GlobalMap(GlobalMap), StartBlock(StartBlock) {}
 
 Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old,
                                              ValueMapT &BBMap,
                                              LoopToScevMapT &LTS,
                                              Loop *L) const {
   if (!SE.isSCEVable(Old->getType()))
     return nullptr;
 
Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old,
 
   Scop &S = *Stmt.getParent();
   const DataLayout &DL = S.getFunction().getParent()->getDataLayout();
   auto IP = Builder.GetInsertPoint();
 
   assert(IP != Builder.GetInsertBlock()->end() &&
          "Only instructions can be insert points for SCEVExpander");
   Value *Expanded =
-      expandCodeFor(S, SE, DL, "polly", NewScev, Old->getType(), &*IP, &VTV);
+      expandCodeFor(S, SE, DL, "polly", NewScev, Old->getType(), &*IP, &VTV,
+                    StartBlock->getSinglePredecessor());
 
   BBMap[Old] = Expanded;
   return Expanded;
 }
 
 Value *BlockGenerator::getNewValue(ScopStmt &Stmt, Value *Old, ValueMapT &BBMap,
                                    LoopToScevMapT &LTS, Loop *L) const {
   // Constants that do not reference any named value can always remain
assert((!isa<Instruction>(Address) ||
                          Builder.GetInsertBlock())) &&
            "Domination violation");
     Builder.CreateStore(Val, Address);
   }
 }
 
 void BlockGenerator::createScalarInitialization(Scop &S) {
   BasicBlock *ExitBB = S.getExit();
+  BasicBlock *PreEntryBB = S.getEnteringBlock();
 
-  // The split block __just before__ the region and optimized region.
-  BasicBlock *SplitBB = S.getEnteringBlock();
-  BranchInst *SplitBBTerm = cast<BranchInst>(SplitBB->getTerminator());
-  assert(SplitBBTerm->getNumSuccessors() == 2 && "Bad region entering block!");
-
-  // Get the start block of the __optimized__ region.
-  BasicBlock *StartBB = SplitBBTerm->getSuccessor(0);
-  if (StartBB == S.getEntry())
-    StartBB = SplitBBTerm->getSuccessor(1);
-
-  Builder.SetInsertPoint(&*StartBB->begin());
+  Builder.SetInsertPoint(&*StartBlock->begin());
 
   for (auto &Array : S.arrays()) {
     if (Array->getNumberOfDimensions() != 0)
       continue;
     if (Array->isPHIKind()) {
       // For PHI nodes, the only values we need to store are the ones that
       // reach the PHI node from outside the region. In general there should
       // only be one such incoming edge and this edge should enter through
-      // 'SplitBB'.
+      // 'PreEntryBB'.
       auto PHI = cast<PHINode>(Array->getBasePtr());
 
       for (auto BI = PHI->block_begin(), BE = PHI->block_end(); BI != BE; BI++)
-        if (!S.contains(*BI) && *BI != SplitBB)
+        if (!S.contains(*BI) && *BI != PreEntryBB)
           llvm_unreachable("Incoming edges from outside the scop should always "
-                           "come from SplitBB");
+                           "come from PreEntryBB");
 
-      int Idx = PHI->getBasicBlockIndex(SplitBB);
+      int Idx = PHI->getBasicBlockIndex(PreEntryBB);
       if (Idx < 0)
         continue;
 
       Value *ScalarValue = PHI->getIncomingValue(Idx);
 
       Builder.CreateStore(ScalarValue, getOrCreatePHIAlloca(PHI));
       continue;
     }

polly/trunk/lib/CodeGen/CodeGeneration.cpp

bool runOnScop(Scop &S) override {
     Annotator.buildAliasScopes(S);
 
     simplifyRegion(R, DT, LI, RI);
     assert(R->isSimple());
     BasicBlock *EnteringBB = S.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();
 
+    IslNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, S,
+                               StartBlock);
+
     // First generate code for the hoisted invariant loads and transitively the
     // parameters they reference. Afterwards, for the remaining parameters that
     // might reference the hoisted loads. Finally, build the runtime check
     // that might reference both hoisted loads as well as parameters.
     // If the hoisting fails we have to bail and execute the original code.
     Builder.SetInsertPoint(SplitBlock->getTerminator());
     if (!NodeBuilder.preloadInvariantLoads()) {
 

polly/trunk/lib/CodeGen/IslExprBuilder.cpp

cl::values(clEnumValN(OT_NEVER, "never", "Never track the overflow bit."),
                           "Track the overflow bit if requested."),
                clEnumValN(OT_ALWAYS, "always",
                           "Always track the overflow bit.")),
     cl::Hidden, cl::init(OT_REQUEST), cl::ZeroOrMore, cl::cat(PollyCategory));
 
 IslExprBuilder::IslExprBuilder(Scop &S, PollyIRBuilder &Builder,
                                IDToValueTy &IDToValue, ValueMapT &GlobalMap,
                                const DataLayout &DL, ScalarEvolution &SE,
-                               DominatorTree &DT, LoopInfo &LI)
+                               DominatorTree &DT, LoopInfo &LI,
+                               BasicBlock *StartBlock)
     : S(S), Builder(Builder), IDToValue(IDToValue), GlobalMap(GlobalMap),
-      DL(DL), SE(SE), DT(DT), LI(LI) {
+      DL(DL), SE(SE), DT(DT), LI(LI), StartBlock(StartBlock) {
   OverflowState = (OTMode == OT_ALWAYS) ? Builder.getFalse() : nullptr;
 }
 
 void IslExprBuilder::setTrackOverflow(bool Enable) {
   // If potential overflows are tracked always or never we ignore requests
   // to change the behaviour.
   if (OTMode != OT_REQUEST)
     return;
if (u + 1 >= e)
       break;
 
     const SCEV *DimSCEV = SAI->getDimensionSize(u);
 
     llvm::ValueToValueMap Map(GlobalMap.begin(), GlobalMap.end());
     DimSCEV = SCEVParameterRewriter::rewrite(DimSCEV, SE, Map);
     Value *DimSize =
         expandCodeFor(S, SE, DL, "polly", DimSCEV, DimSCEV->getType(),
-                      &*Builder.GetInsertPoint());
+                      &*Builder.GetInsertPoint(), nullptr,
+                      StartBlock->getSinglePredecessor());
 
     Type *Ty = getWidestType(DimSize->getType(), IndexOp->getType());
 
     if (Ty != IndexOp->getType())
       IndexOp = Builder.CreateSExtOrTrunc(IndexOp, Ty,
                                           "polly.access.sext." + BaseName);
     if (Ty != DimSize->getType())
       DimSize = Builder.CreateSExtOrTrunc(DimSize, Ty,

polly/trunk/lib/CodeGen/IslNodeBuilder.cpp

Value *IslNodeBuilder::generateSCEV(const SCEV *Expr) {
   ///
   /// We also do not need to update the Builder here, as new instructions are
   /// always inserted _before_ the given InsertLocation. As a result, the
   /// insert location remains valid.
   assert(Builder.GetInsertBlock()->end() != Builder.GetInsertPoint() &&
          "Insert location points after last valid instruction");
   Instruction *InsertLocation = &*Builder.GetInsertPoint();
   return expandCodeFor(S, SE, DL, "polly", Expr, Expr->getType(),
-                       InsertLocation, &ValueMap);
+                       InsertLocation, &ValueMap,
+                       StartBlock->getSinglePredecessor());
 }
 
 /// The AST expression we generate to perform the run-time check assumes
 /// computations on integer types of infinite size. As we only use 64-bit
 /// arithmetic we check for overflows, in case of which we set the result
 /// of this run-time check to false to be cosnservatively correct,
 Value *IslNodeBuilder::createRTC(isl_ast_expr *Condition) {
   auto ExprBuilder = getExprBuilder();

polly/trunk/lib/CodeGen/PPCGCodeGeneration.cpp

 /// generates code for general-prupose AST nodes, with special functionality
 /// for generating GPU specific user nodes.
 ///
 /// @see GPUNodeBuilder::createUser
 class GPUNodeBuilder : public IslNodeBuilder {
 public:
   GPUNodeBuilder(PollyIRBuilder &Builder, ScopAnnotator &Annotator, Pass *P,
                  const DataLayout &DL, LoopInfo &LI, ScalarEvolution &SE,
-                 DominatorTree &DT, Scop &S, gpu_prog *Prog)
-      : IslNodeBuilder(Builder, Annotator, P, DL, LI, SE, DT, S), Prog(Prog) {
+                 DominatorTree &DT, Scop &S, BasicBlock *StartBlock,
+                 gpu_prog *Prog)
+      : IslNodeBuilder(Builder, Annotator, P, DL, LI, SE, DT, S, StartBlock),
+        Prog(Prog) {
     getExprBuilder().setIDToSAI(&IDToSAI);
   }
 
   /// Create after-run-time-check initialization code.
   void initializeAfterRTH();
 
   /// Finalize the generated scop.
   virtual void finalize();
void generateCode(__isl_take isl_ast_node *Root, gpu_prog *Prog) {
     Region *R = &S->getRegion();
 
     simplifyRegion(R, DT, LI, RI);
 
     BasicBlock *EnteringBB = R->getEnteringBlock();
 
     PollyIRBuilder Builder = createPollyIRBuilder(EnteringBB, Annotator);
 
-    GPUNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, *S,
-                               Prog);
-
     // 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());
 
+    GPUNodeBuilder NodeBuilder(Builder, Annotator, this, *DL, *LI, *SE, *DT, *S,
+                               StartBlock, Prog);
+
     // TODO: Handle LICM
     auto SplitBlock = StartBlock->getSinglePredecessor();
     Builder.SetInsertPoint(SplitBlock->getTerminator());
     NodeBuilder.addParameters(S->getContext());
 
     isl_ast_build *Build = isl_ast_build_alloc(S->getIslCtx());
     isl_ast_expr *Condition = IslAst::buildRunCondition(S, Build);
     isl_ast_expr *SufficientCompute = createSufficientComputeCheck(*S, Build);

polly/trunk/lib/CodeGen/Utils.cpp

BasicBlock *polly::executeScopConditionally(Scop &S, Pass *P, Value *RTC) {
   //  /  EntryBB  \    StartBlock  //
   //  |  (region) |        |       //
   //  \_ExitingBB_/   ExitingBlock //
   //        |              |       //
   //    MergeBlock---------/       //
   //        |                      //
   //      ExitBB                   //
   //      /    \                   //
+  //
+
+  // Split the edge between SplitBlock and EntryBB, to avoid a critical edge.
+  splitEdge(SplitBlock, EntryBB, ".pre_entry_bb", &DT, &LI, &RI);
+
+  //      \   /                    //
+  //    EnteringBB                 //
+  //        |                      //
+  //    SplitBlock---------\       //
+  //        |              |       //
+  //    PreEntryBB         |       //
+  //   _____|_____         |       //
+  //  /  EntryBB  \    StartBlock  //
+  //  |  (region) |        |       //
+  //  \_ExitingBB_/   ExitingBlock //
+  //        |              |       //
+  //    MergeBlock---------/       //
+  //        |                      //
+  //      ExitBB                   //
+  //      /    \                   //
 
   return StartBlock;
 }

polly/trunk/lib/Support/ScopHelper.cpp

 /// however to generate new code if the instruction is in the analyzed region
 /// and we generate code outside/in front of that region. Hence, we generate the
 /// code for the SDiv/SRem operands in front of the analyzed region and then
 /// create a new SDiv/SRem operation there too.
 struct ScopExpander : SCEVVisitor<ScopExpander, const SCEV *> {
   friend struct SCEVVisitor<ScopExpander, const SCEV *>;
 
   explicit ScopExpander(const Region &R, ScalarEvolution &SE,
-                        const DataLayout &DL, const char *Name, ValueMapT *VMap)
+                        const DataLayout &DL, const char *Name, ValueMapT *VMap,
+                        BasicBlock *RTCBB)
       : Expander(SCEVExpander(SE, DL, Name)), SE(SE), Name(Name), R(R),
-        VMap(VMap) {}
+        VMap(VMap), RTCBB(RTCBB) {}
 
   Value *expandCodeFor(const SCEV *E, Type *Ty, Instruction *I) {
     // If we generate code in the region we will immediately fall back to the
     // SCEVExpander, otherwise we will stop at all unknowns in the SCEV and if
     // needed replace them by copies computed in the entering block.
     if (!R.contains(I))
       E = visit(E);
     return Expander.expandCodeFor(E, Ty, I);
   }
 
 private:
   SCEVExpander Expander;
   ScalarEvolution &SE;
   const char *Name;
   const Region &R;
   ValueMapT *VMap;
+  BasicBlock *RTCBB;
 
   const SCEV *visitGenericInst(const SCEVUnknown *E, Instruction *Inst,
                                Instruction *IP) {
     if (!Inst || !R.contains(Inst))
       return E;
 
     assert(!Inst->mayThrow() && !Inst->mayReadOrWriteMemory() &&
            !isa<PHINode>(Inst));
if (NewVal) {
       auto *NewE = SE.getSCEV(NewVal);
 
       // While the mapped value might be different the SCEV representation might
       // not be. To this end we will check before we go into recursion here.
       if (E != NewE)
         return visit(NewE);
     }
 
-    auto *EnteringBB = R.getEnteringBlock();
     Instruction *Inst = dyn_cast<Instruction>(E->getValue());
     Instruction *IP;
     if (Inst && !R.contains(Inst))
       IP = Inst;
-    else if (Inst && EnteringBB->getParent() == Inst->getFunction())
-      IP = EnteringBB->getTerminator();
+    else if (Inst && RTCBB->getParent() == Inst->getFunction())
+      IP = RTCBB->getTerminator();
     else
-      IP = EnteringBB->getParent()->getEntryBlock().getTerminator();
+      IP = RTCBB->getParent()->getEntryBlock().getTerminator();
 
     if (!Inst || (Inst->getOpcode() != Instruction::SRem &&
                   Inst->getOpcode() != Instruction::SDiv))
       return visitGenericInst(E, Inst, IP);
 
     const SCEV *LHSScev = SE.getSCEV(Inst->getOperand(0));
     const SCEV *RHSScev = SE.getSCEV(Inst->getOperand(1));
 
for (const SCEV *Op : E->operands())
       NewOps.push_back(visit(Op));
     return SE.getAddRecExpr(NewOps, E->getLoop(), E->getNoWrapFlags());
   }
   ///}
 };
 
 Value *polly::expandCodeFor(Scop &S, ScalarEvolution &SE, const DataLayout &DL,
                             const char *Name, const SCEV *E, Type *Ty,
-                            Instruction *IP, ValueMapT *VMap) {
-  ScopExpander Expander(S.getRegion(), SE, DL, Name, VMap);
+                            Instruction *IP, ValueMapT *VMap,
+                            BasicBlock *RTCBB) {
+  ScopExpander Expander(S.getRegion(), SE, DL, Name, VMap, RTCBB);
   return Expander.expandCodeFor(E, Ty, IP);
 }
 
 bool polly::isErrorBlock(BasicBlock &BB, const Region &R, LoopInfo &LI,
                          const DominatorTree &DT) {
 
   if (isa<UnreachableInst>(BB.getTerminator()))
     return true;