[Polly] Allow to generate a loop without the GuardBB

[jdoerfert]

Summary

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.

[dpeixott]

Needs a test case to demonstrate the omission of the guard bb. Otherwise, LGTM.

[jdoerfert]

Closed by commit rL217525 (authored by @jdoerfert).

polly/trunk/include/polly/CodeGen/LoopGenerators.h

 class Value;
 class Pass;
 class BasicBlock;
 }
 
 namespace polly {
 using namespace llvm;
 
-/// @brief Create a scalar loop.
+/// @brief Create a scalar do/for-style loop.
 ///
 /// @param LowerBound The starting value of the induction variable.
 /// @param UpperBound The upper bound of the induction variable.
 /// @param Stride     The value by which the induction variable is incremented.
 ///
 /// @param Builder    The builder used to create the loop.
 /// @param P          A pointer to the pass that uses this function. It is used
 ///                   to update analysis information.
 /// @param LI         The loop info for the current function
 /// @param DT         The dominator tree we need to update
 /// @param ExitBlock  The block the loop will exit to.
 /// @param Predicate  The predicate used to generate the upper loop bound.
 /// @param Annotator  This function can (optionally) take a LoopAnnotator which
 ///                   tracks the loop structure.
 /// @param Parallel   If this loop should be marked parallel in the Annotator.
+/// @param UseGuard   Create a guard in front of the header to check if the
+///                   loop is executed at least once, otherwise just assume it.
+///
 /// @return Value*    The newly created induction variable for this loop.
 Value *createLoop(Value *LowerBound, Value *UpperBound, Value *Stride,
                   PollyIRBuilder &Builder, Pass *P, LoopInfo &LI,
                   DominatorTree &DT, BasicBlock *&ExitBlock,
                   ICmpInst::Predicate Predicate,
-                  LoopAnnotator *Annotator = NULL, bool Parallel = false);
+                  LoopAnnotator *Annotator = NULL, bool Parallel = false,
+                  bool UseGuard = true);
 
 class OMPGenerator {
 public:
   typedef std::map<Value *, Value *> ValueToValueMapTy;
 
   OMPGenerator(PollyIRBuilder &Builder, Pass *P) : Builder(Builder), P(P) {}
 
   /// @brief Create an OpenMP parallel loop.

polly/trunk/lib/CodeGen/IslCodeGeneration.cpp

void IslNodeBuilder::createForSequential(__isl_take isl_ast_node *For) {
 
   if (MaxType != ValueLB->getType())
     ValueLB = Builder.CreateSExt(ValueLB, MaxType);
   if (MaxType != ValueUB->getType())
     ValueUB = Builder.CreateSExt(ValueUB, MaxType);
   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);
 
   Annotator.End();
 
   IDToValue.erase(IteratorID);
 

polly/trunk/lib/CodeGen/LoopGenerators.cpp

 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Module.h"
 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
 
 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
-//
-// 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.
+//              BeforeBB                      BeforeBB
+//                 |                             |
+//                 v                             v
+//              GuardBB                      PreHeaderBB
+//              /      |                         |   _____
+//     __  PreHeaderBB  |                        v  \/    |
+//    /  \    /         |                     HeaderBB  latch
+// latch  HeaderBB      |                        |\       |
+//    \  /    \         /                        | \------/
+//     <       \       /                         |
+//              \     /                          v
+//              ExitBB                         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();
 
   assert(LB->getType() == UB->getType() && "Types of loop bounds do not match");
   IntegerType *LoopIVType = dyn_cast<IntegerType>(UB->getType());
   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);
 
   if (Annotator) {
     Annotator->Begin(HeaderBB);
     if (Parallel)
       Annotator->SetCurrentParallel();
   }
 
   // Update LoopInfo
   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());
 
   // ExitBB
   ExitBB = SplitBlock(BeforeBB, Builder.GetInsertPoint()++, P);
   ExitBB->setName("polly.loop_exit");
 
   // BeforeBB
+  if (GuardBB) {
     BeforeBB->getTerminator()->setSuccessor(0, GuardBB);
+    DT.addNewBlock(GuardBB, BeforeBB);
 
     // 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);
+    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);
 
   // HeaderBB
   DT.addNewBlock(HeaderBB, PreHeaderBB);
   Builder.SetInsertPoint(HeaderBB);
   PHINode *IV = Builder.CreatePHI(LoopIVType, 2, "polly.indvar");
   IV->addIncoming(LB, PreHeaderBB);
   Stride = Builder.CreateZExtOrBitCast(Stride, LoopIVType);
   Value *IncrementedIV = Builder.CreateNSWAdd(IV, Stride, "polly.indvar_next");
   Value *LoopCondition;
   UB = Builder.CreateSub(UB, Stride, "polly.adjust_ub");
   LoopCondition = Builder.CreateICmp(Predicate, IV, UB);
   LoopCondition->setName("polly.loop_cond");
   Builder.CreateCondBr(LoopCondition, HeaderBB, ExitBB);
   IV->addIncoming(IncrementedIV, HeaderBB);
+  if (GuardBB)
     DT.changeImmediateDominator(ExitBB, GuardBB);
+  else
+    DT.changeImmediateDominator(ExitBB, BeforeBB);
 
   // The loop body should be added here.
   Builder.SetInsertPoint(HeaderBB->getFirstNonPHI());
   return IV;
 }
 
 void OMPGenerator::createCallParallelLoopStart(
     Value *SubFunction, Value *SubfunctionParam, Value *NumberOfThreads,
Value *OMPGenerator::createSubfunction(Value *Stride, Value *StructData,
   // whereas the codegenForSequential function creates a <= comparison.
   UpperBound = Builder.CreateSub(UpperBound, ConstantInt::get(IntPtrTy, 1),
                                  "omp.upperBoundAdjusted");
 
   Builder.CreateBr(CheckNextBB);
   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());
 
   // Add code to terminate this openmp subfunction.
   Builder.SetInsertPoint(ExitBB);
   createCallLoopEndNowait();
   Builder.CreateRetVoid();

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

+; RUN: opt %loadPolly -polly-codegen-isl -S < %s | FileCheck %s
+;
+; CHECK-NOT: br i1 true, label %polly.{{.*}}, label %polly.{{.*}}
+;
+;    void jd(int *A) {
+;      for (int i = 0; i < 1024; i++)
+;        A[i] = i;
+;    }
+;
+target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
+
+define void @jd(i32* %A) {
+entry:
+  br label %for.cond
+
+for.cond:                                         ; preds = %for.inc, %entry
+  %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %entry ]
+  %exitcond = icmp ne i64 %indvars.iv, 1024
+  br i1 %exitcond, label %for.body, label %for.end
+
+for.body:                                         ; preds = %for.cond
+  %arrayidx = getelementptr inbounds i32* %A, i64 %indvars.iv
+  %tmp = trunc i64 %indvars.iv to i32
+  store i32 %tmp, i32* %arrayidx, align 4
+  br label %for.inc
+
+for.inc:                                          ; preds = %for.body
+  %indvars.iv.next = add nuw nsw i64 %indvars.iv, 1
+  br label %for.cond
+
+for.end:                                          ; preds = %for.cond
+  ret void
+}