diff options
| -rw-r--r-- | polly/lib/Support/ScopHelper.cpp | 59 | ||||
| -rw-r--r-- | polly/test/Isl/CodeGen/loop_with_conditional_entry_edge_splited_hard_case.ll | 63 |
2 files changed, 111 insertions, 11 deletions
diff --git a/polly/lib/Support/ScopHelper.cpp b/polly/lib/Support/ScopHelper.cpp index 01c1dd0048a..1aec0523e30 100644 --- a/polly/lib/Support/ScopHelper.cpp +++ b/polly/lib/Support/ScopHelper.cpp @@ -86,33 +86,70 @@ BasicBlock *polly::createSingleExitEdge(Region *R, Pass *P) { return SplitBlockPredecessors(BB, Preds, ".region", P); } +static void replaceScopAndRegionEntry(polly::Scop *S, BasicBlock *OldEntry, + BasicBlock *NewEntry) { + for (polly::ScopStmt *Stmt : *S) + if (Stmt->getBasicBlock() == OldEntry) { + Stmt->setBasicBlock(NewEntry); + break; + } + + S->getRegion().replaceEntryRecursive(NewEntry); +} + BasicBlock *polly::simplifyRegion(Scop *S, Pass *P) { Region *R = &S->getRegion(); // The entering block for the region. BasicBlock *EnteringBB = R->getEnteringBlock(); + BasicBlock *OldEntry = R->getEntry(); + BasicBlock *NewEntry = nullptr; // Create single entry edge if the region has multiple entry edges. if (!EnteringBB) { - BasicBlock *OldEntry = R->getEntry(); - BasicBlock *NewEntry = SplitBlock(OldEntry, OldEntry->begin(), P); - - for (ScopStmt *Stmt : *S) - if (Stmt->getBasicBlock() == OldEntry) { - Stmt->setBasicBlock(NewEntry); - break; - } - - R->replaceEntryRecursive(NewEntry); + NewEntry = SplitBlock(OldEntry, OldEntry->begin(), P); EnteringBB = OldEntry; } // Create an unconditional entry edge. if (EnteringBB->getTerminator()->getNumSuccessors() != 1) { - EnteringBB = SplitEdge(EnteringBB, R->getEntry(), P); + BasicBlock *EntryBB = NewEntry ? NewEntry : OldEntry; + BasicBlock *SplitEdgeBB = SplitEdge(EnteringBB, EntryBB, P); + + // Once the edge between EnteringBB and EntryBB is split, two cases arise. + // The first is simple. The new block is inserted between EnteringBB and + // EntryBB. In this case no further action is needed. However it might + // happen (if the splitted edge is not critical) that the new block is + // inserted __after__ EntryBB causing the following situation: + // + // EnteringBB + // | + // / \ + // | \-> some_other_BB_not_in_R + // V + // EntryBB + // | + // V + // SplitEdgeBB + // + // In this case we need to swap the role of EntryBB and SplitEdgeBB. + + // Check which case SplitEdge produced: + if (SplitEdgeBB->getTerminator()->getSuccessor(0) == EntryBB) { + // First (simple) case. + EnteringBB = SplitEdgeBB; + } else { + // Second (complicated) case. + NewEntry = SplitEdgeBB; + EnteringBB = EntryBB; + } + EnteringBB->setName("polly.entering.block"); } + if (NewEntry) + replaceScopAndRegionEntry(S, OldEntry, NewEntry); + // Create single exit edge if the region has multiple exit edges. if (!R->getExitingBlock()) { BasicBlock *NewExit = createSingleExitEdge(R, P); diff --git a/polly/test/Isl/CodeGen/loop_with_conditional_entry_edge_splited_hard_case.ll b/polly/test/Isl/CodeGen/loop_with_conditional_entry_edge_splited_hard_case.ll new file mode 100644 index 00000000000..997a24c7219 --- /dev/null +++ b/polly/test/Isl/CodeGen/loop_with_conditional_entry_edge_splited_hard_case.ll @@ -0,0 +1,63 @@ +; RUN: opt %loadPolly -polly-codegen-isl -S < %s | FileCheck %s +; +; Test case to trigger the hard way of creating a unique entering +; edge for the SCoP. It is triggered because the entering edge +; here: %while.begin --> %if is __not__ critical. +; +; int f(void); +; void jd(int b, int *A) { +; while (f()) { +; if (b) +; 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 %b, i32* %A) { +entry: + br label %while.begin + +; CHECK: while.begin: +while.begin: +; CHECK: %call = call i32 @f() + %call = call i32 @f() +; CHECK: %tobool = icmp eq i32 %call, 0 + %tobool = icmp eq i32 %call, 0 +; CHECK: br i1 %tobool, label %while.end, label %polly.entering.block + br i1 %tobool, label %while.end, label %if + +; CHECK: polly.entering.block: +; CHECK: br label %polly.split_new_and_old + +; CHECK: polly.split_new_and_old: +; CHECK: br i1 true, label %polly.start, label %if.split + +; CHECK: if.split: +if: ; preds = %while.begin +; CHECK: %tobool2 = icmp eq i32 %b, 0 + %tobool2 = icmp eq i32 %b, 0 +; CHECK: br i1 %tobool2, label %while.begin{{[a-zA-Z._]*}}, label %for.cond + br i1 %tobool2, label %while.begin, label %for.cond + +for.cond: ; preds = %for.inc, %if + %indvars.iv = phi i64 [ %indvars.iv.next, %for.inc ], [ 0, %if ] + %exitcond = icmp ne i64 %indvars.iv, 1024 + br i1 %exitcond, label %for.body, label %while.begin + +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 + +while.end: ; preds = %entry, %for.cond + ret void +} + +declare i32 @f() |
