Index: polly/trunk/include/polly/CodeGen/LoopGenerators.h =================================================================== --- polly/trunk/include/polly/CodeGen/LoopGenerators.h +++ polly/trunk/include/polly/CodeGen/LoopGenerators.h @@ -27,7 +27,7 @@ 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. @@ -43,12 +43,16 @@ /// @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: Index: polly/trunk/lib/CodeGen/IslCodeGeneration.cpp =================================================================== --- polly/trunk/lib/CodeGen/IslCodeGeneration.cpp +++ polly/trunk/lib/CodeGen/IslCodeGeneration.cpp @@ -352,8 +352,12 @@ if (MaxType != ValueInc->getType()) ValueInc = Builder.CreateSExt(ValueInc, MaxType); + // If we can show that LB 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); Index: polly/trunk/lib/CodeGen/LoopGenerators.cpp =================================================================== --- polly/trunk/lib/CodeGen/LoopGenerators.cpp +++ polly/trunk/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 @@ 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 @@ 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 @@ 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 @@ 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 @@ Builder.SetInsertPoint(--Builder.GetInsertPoint()); LoopInfo &LI = P->getAnalysis(); 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()); Index: polly/trunk/test/Isl/CodeGen/no_guard_bb.ll =================================================================== --- polly/trunk/test/Isl/CodeGen/no_guard_bb.ll +++ polly/trunk/test/Isl/CodeGen/no_guard_bb.ll @@ -0,0 +1,33 @@ +; 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 +}