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

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.

Differential Revision: https://reviews.llvm.org/D26053

llvm-svn: 285864

7 files changed, 61 insertions, 43 deletions

diff --git a/polly/lib/CodeGen/BlockGenerators.cpp b/polly/lib/CodeGen/BlockGenerators.cpp
index 835f2c5953e..b3e4f356b8f 100644
--- a/polly/lib/CodeGen/BlockGenerators.cpp
+++ b/polly/lib/CodeGen/BlockGenerators.cpp
@@ -48,16 +48,14 @@ static cl::opt<bool> DebugPrinting(
     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,
@@ -85,7 +83,8 @@ Value *BlockGenerator::trySynthesizeNewValue(ScopStmt &Stmt, Value *Old,
   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;
@@ -524,18 +523,9 @@ void BlockGenerator::generateScalarStores(
 
 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)
@@ -544,15 +534,15 @@ void BlockGenerator::createScalarInitialization(Scop &S) {
       // 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;
 
diff --git a/polly/lib/CodeGen/CodeGeneration.cpp b/polly/lib/CodeGen/CodeGeneration.cpp
index 68b1d830e47..9fcd6dfba37 100644
--- a/polly/lib/CodeGen/CodeGeneration.cpp
+++ b/polly/lib/CodeGen/CodeGeneration.cpp
@@ -133,8 +133,6 @@ public:
     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
@@ -145,6 +143,9 @@ public:
         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
diff --git a/polly/lib/CodeGen/IslExprBuilder.cpp b/polly/lib/CodeGen/IslExprBuilder.cpp
index 160a574e817..9075ee08da2 100644
--- a/polly/lib/CodeGen/IslExprBuilder.cpp
+++ b/polly/lib/CodeGen/IslExprBuilder.cpp
@@ -41,9 +41,10 @@ static cl::opt<OverflowTrackingChoice> OTMode(
 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;
 }
 
@@ -284,7 +285,8 @@ Value *IslExprBuilder::createAccessAddress(isl_ast_expr *Expr) {
     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());
 
diff --git a/polly/lib/CodeGen/IslNodeBuilder.cpp b/polly/lib/CodeGen/IslNodeBuilder.cpp
index 0869a7fc86b..5c50fbf0e88 100644
--- a/polly/lib/CodeGen/IslNodeBuilder.cpp
+++ b/polly/lib/CodeGen/IslNodeBuilder.cpp
@@ -1286,7 +1286,8 @@ Value *IslNodeBuilder::generateSCEV(const SCEV *Expr) {
          "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
diff --git a/polly/lib/CodeGen/PPCGCodeGeneration.cpp b/polly/lib/CodeGen/PPCGCodeGeneration.cpp
index 6b872c35351..a2edb715ec2 100644
--- a/polly/lib/CodeGen/PPCGCodeGeneration.cpp
+++ b/polly/lib/CodeGen/PPCGCodeGeneration.cpp
@@ -146,8 +146,10 @@ 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);
   }
 
@@ -2398,9 +2400,6 @@ public:
 
     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
@@ -2410,6 +2409,9 @@ public:
     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());
diff --git a/polly/lib/CodeGen/Utils.cpp b/polly/lib/CodeGen/Utils.cpp
index 890d90192e2..9aa22dae829 100644
--- a/polly/lib/CodeGen/Utils.cpp
+++ b/polly/lib/CodeGen/Utils.cpp
@@ -196,6 +196,26 @@ BasicBlock *polly::executeScopConditionally(Scop &S, Pass *P, Value *RTC) {
   //        |                      //
   //      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;
 }
diff --git a/polly/lib/Support/ScopHelper.cpp b/polly/lib/Support/ScopHelper.cpp
index 9e94b9f5740..71e788f8751 100644
--- a/polly/lib/Support/ScopHelper.cpp
+++ b/polly/lib/Support/ScopHelper.cpp
@@ -226,9 +226,10 @@ 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
@@ -245,6 +246,7 @@ private:
   const char *Name;
   const Region &R;
   ValueMapT *VMap;
+  BasicBlock *RTCBB;
 
   const SCEV *visitGenericInst(const SCEVUnknown *E, Instruction *Inst,
                                Instruction *IP) {
@@ -280,15 +282,14 @@ private:
         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))
@@ -363,8 +364,9 @@ private:
 
 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);
 }