summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
Diffstat
-rw-r--r--polly/include/polly/CodeGen/LoopGenerators.h8
-rw-r--r--polly/lib/CodeGen/IslCodeGeneration.cpp6
-rw-r--r--polly/lib/CodeGen/LoopGenerators.cpp87
-rw-r--r--polly/test/Isl/CodeGen/no_guard_bb.ll33
4 files changed, 91 insertions, 43 deletions
diff --git a/polly/include/polly/CodeGen/LoopGenerators.h b/polly/include/polly/CodeGen/LoopGenerators.h
index 6467161d10f..6f766e4d88c 100644
--- a/polly/include/polly/CodeGen/LoopGenerators.h
+++ b/polly/include/polly/CodeGen/LoopGenerators.h
@@ -27,7 +27,7 @@ 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.
@@ -43,12 +43,16 @@ using namespace llvm;
/// @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:
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());
diff --git a/polly/test/Isl/CodeGen/no_guard_bb.ll b/polly/test/Isl/CodeGen/no_guard_bb.ll
new file mode 100644
index 00000000000..3b51c77a95f
--- /dev/null
+++ b/polly/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
+}
OpenPOWER on IntegriCloud