Allow to generate a loop without the GuardBB

  This allows us to omit the GuardBB in front of created loops
  if we can show the loop trip count is at least one. It also
  simplifies the dominance relation inside the new created region.
  A GuardBB (even with a constant branch condition) might trigger
  false dominance errors during function verification.

Differential Revision: http://reviews.llvm.org/D5297

llvm-svn: 217525

2 files changed, 52 insertions, 41 deletions

diff --git a/polly/lib/CodeGen/IslCodeGeneration.cpp b/polly/lib/CodeGen/IslCodeGeneration.cpp
index 84b91ed65d5..0d9a798de04 100644
--- a/polly/lib/CodeGen/IslCodeGeneration.cpp
+++ b/polly/lib/CodeGen/IslCodeGeneration.cpp
@@ -352,8 +352,12 @@ void IslNodeBuilder::createForSequential(__isl_take isl_ast_node *For) {
   if (MaxType != ValueInc->getType())
     ValueInc = Builder.CreateSExt(ValueInc, MaxType);
 
+  // If we can show that LB <Predicate> UB holds at least once, we can
+  // omit the GuardBB in front of the loop.
+  bool UseGuardBB =
+      !SE.isKnownPredicate(Predicate, SE.getSCEV(ValueLB), SE.getSCEV(ValueUB));
   IV = createLoop(ValueLB, ValueUB, ValueInc, Builder, P, LI, DT, ExitBlock,
-                  Predicate, &Annotator, Parallel);
+                  Predicate, &Annotator, Parallel, UseGuardBB);
   IDToValue[IteratorID] = IV;
 
   create(Body);
diff --git a/polly/lib/CodeGen/LoopGenerators.cpp b/polly/lib/CodeGen/LoopGenerators.cpp
index 4eaaac0bc6d..267caeb5001 100644
--- a/polly/lib/CodeGen/LoopGenerators.cpp
+++ b/polly/lib/CodeGen/LoopGenerators.cpp
@@ -23,34 +23,33 @@
 using namespace llvm;
 using namespace polly;
 
-// We generate a loop of the following structure
+// We generate a loop of either of the following structures:
 //
-//              BeforeBB
-//                 |
-//                 v
-//              GuardBB
-//              /      |
-//     __  PreHeaderBB  |
-//    /  \    /         |
-// latch  HeaderBB      |
-//    \  /    \         /
-//     <       \       /
-//              \     /
-//              ExitBB
+//              BeforeBB                      BeforeBB
+//                 |                             |
+//                 v                             v
+//              GuardBB                      PreHeaderBB
+//              /      |                         |   _____
+//     __  PreHeaderBB  |                        v  \/    |
+//    /  \    /         |                     HeaderBB  latch
+// latch  HeaderBB      |                        |\       |
+//    \  /    \         /                        | \------/
+//     <       \       /                         |
+//              \     /                          v
+//              ExitBB                         ExitBB
 //
-// GuardBB checks if the loop is executed at least once. If this is the case
-// we branch to PreHeaderBB and subsequently to the HeaderBB, which contains the
-// loop iv 'polly.indvar', the incremented loop iv 'polly.indvar_next' as well
-// as the condition to check if we execute another iteration of the loop. After
-// the loop has finished, we branch to ExitBB.
-//
-// TODO: We currently always create the GuardBB. If we can prove the loop is
-//       always executed at least once, we can get rid of this branch.
+// depending on whether or not we know that it is executed at least once. If
+// not, GuardBB checks if the loop is executed at least once. If this is the
+// case we branch to PreHeaderBB and subsequently to the HeaderBB, which
+// contains the loop iv 'polly.indvar', the incremented loop iv
+// 'polly.indvar_next' as well as the condition to check if we execute another
+// iteration of the loop. After the loop has finished, we branch to ExitBB.
 Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
                          PollyIRBuilder &Builder, Pass *P, LoopInfo &LI,
                          DominatorTree &DT, BasicBlock *&ExitBB,
                          ICmpInst::Predicate Predicate,
-                         LoopAnnotator *Annotator, bool Parallel) {
+                         LoopAnnotator *Annotator, bool Parallel,
+                         bool UseGuard) {
   Function *F = Builder.GetInsertBlock()->getParent();
   LLVMContext &Context = F->getContext();
 
@@ -59,7 +58,8 @@ Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
   assert(LoopIVType && "UB is not integer?");
 
   BasicBlock *BeforeBB = Builder.GetInsertBlock();
-  BasicBlock *GuardBB = BasicBlock::Create(Context, "polly.loop_if", F);
+  BasicBlock *GuardBB =
+      UseGuard ? BasicBlock::Create(Context, "polly.loop_if", F) : nullptr;
   BasicBlock *HeaderBB = BasicBlock::Create(Context, "polly.loop_header", F);
   BasicBlock *PreHeaderBB =
       BasicBlock::Create(Context, "polly.loop_preheader", F);
@@ -74,16 +74,15 @@ Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
   Loop *OuterLoop = LI.getLoopFor(BeforeBB);
   Loop *NewLoop = new Loop();
 
-  if (OuterLoop) {
+  if (OuterLoop)
     OuterLoop->addChildLoop(NewLoop);
-  } else {
+  else
     LI.addTopLevelLoop(NewLoop);
-  }
 
-  if (OuterLoop) {
+  if (OuterLoop && GuardBB)
     OuterLoop->addBasicBlockToLoop(GuardBB, LI.getBase());
+  else if (OuterLoop)
     OuterLoop->addBasicBlockToLoop(PreHeaderBB, LI.getBase());
-  }
 
   NewLoop->addBasicBlockToLoop(HeaderBB, LI.getBase());
 
@@ -92,18 +91,23 @@ Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
   ExitBB->setName("polly.loop_exit");
 
   // BeforeBB
-  BeforeBB->getTerminator()->setSuccessor(0, GuardBB);
-
-  // GuardBB
-  DT.addNewBlock(GuardBB, BeforeBB);
-  Builder.SetInsertPoint(GuardBB);
-  Value *LoopGuard;
-  LoopGuard = Builder.CreateICmp(Predicate, LB, UB);
-  LoopGuard->setName("polly.loop_guard");
-  Builder.CreateCondBr(LoopGuard, PreHeaderBB, ExitBB);
+  if (GuardBB) {
+    BeforeBB->getTerminator()->setSuccessor(0, GuardBB);
+    DT.addNewBlock(GuardBB, BeforeBB);
+
+    // GuardBB
+    Builder.SetInsertPoint(GuardBB);
+    Value *LoopGuard;
+    LoopGuard = Builder.CreateICmp(Predicate, LB, UB);
+    LoopGuard->setName("polly.loop_guard");
+    Builder.CreateCondBr(LoopGuard, PreHeaderBB, ExitBB);
+    DT.addNewBlock(PreHeaderBB, GuardBB);
+  } else {
+    BeforeBB->getTerminator()->setSuccessor(0, PreHeaderBB);
+    DT.addNewBlock(PreHeaderBB, BeforeBB);
+  }
 
   // PreHeaderBB
-  DT.addNewBlock(PreHeaderBB, GuardBB);
   Builder.SetInsertPoint(PreHeaderBB);
   Builder.CreateBr(HeaderBB);
 
@@ -120,7 +124,10 @@ Value *polly::createLoop(Value *LB, Value *UB, Value *Stride,
   LoopCondition->setName("polly.loop_cond");
   Builder.CreateCondBr(LoopCondition, HeaderBB, ExitBB);
   IV->addIncoming(IncrementedIV, HeaderBB);
-  DT.changeImmediateDominator(ExitBB, GuardBB);
+  if (GuardBB)
+    DT.changeImmediateDominator(ExitBB, GuardBB);
+  else
+    DT.changeImmediateDominator(ExitBB, BeforeBB);
 
   // The loop body should be added here.
   Builder.SetInsertPoint(HeaderBB->getFirstNonPHI());
@@ -322,7 +329,7 @@ Value *OMPGenerator::createSubfunction(Value *Stride, Value *StructData,
   Builder.SetInsertPoint(--Builder.GetInsertPoint());
   LoopInfo &LI = P->getAnalysis<LoopInfo>();
   IV = createLoop(LowerBound, UpperBound, Stride, Builder, P, LI, DT, AfterBB,
-                  ICmpInst::ICMP_SLE);
+                  ICmpInst::ICMP_SLE, nullptr, true, /* UseGuard */ false);
 
   BasicBlock::iterator LoopBody = Builder.GetInsertPoint();
   Builder.SetInsertPoint(AfterBB->begin());