Marcello Maggioni
2012-Feb-08 20:05 UTC
[LLVMdev] BackedgeTakenCount calculation for fortran loops and DragonEgg gfortran-4.6
Attached 2012/2/8 Marcello Maggioni <hayarms at gmail.com>:> Mmm, sorry, the patch I posted crashes if ExitBr is null (which it may > be ...) , this one should be ok (and passess all the ScalarEvolution > tests in LLVM): > > diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp > index daf7742..b10fab2 100644 > --- a/lib/Analysis/ScalarEvolution.cpp > +++ b/lib/Analysis/ScalarEvolution.cpp > @@ -4293,9 +4293,15 @@ ScalarEvolution::ComputeExitLimit(const Loop > *L, BasicBlock *ExitingBlock) { > // > // FIXME: we should be able to handle switch instructions (with a > single exit) > BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); > + > if (ExitBr == 0) return getCouldNotCompute(); > assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!"); > > + BranchInst* BrFirstSucc = dyn_cast<BranchInst>(ExitBr-> > + getSuccessor(0)->getTerminator()); > + BranchInst* BrSecondSucc = dyn_cast<BranchInst>(ExitBr-> > + getSuccessor(1)->getTerminator()); > + > // At this point, we know we have a conditional branch that > determines whether > // the loop is exited. However, we don't know if the branch is executed each > // time through the loop. If not, then the execution count of the > branch will > @@ -4316,10 +4322,23 @@ ScalarEvolution::ComputeExitLimit(const Loop > *L, BasicBlock *ExitingBlock) { > if (ExitBr->getSuccessor(0) != L->getHeader() && > ExitBr->getSuccessor(1) != L->getHeader() && > ExitBr->getParent() != L->getHeader()) { > - // The simple checks failed, try climbing the unique predecessor chain > - // up to the header. > + > bool Ok = false; > - for (BasicBlock *BB = ExitBr->getParent(); BB; ) { > + //Check if the one of the successor of the exit branch has the is a block > + //that has only one predecessor and has an unconditional branch to the > + //loop header > + if (BrFirstSucc && BrFirstSucc->isUnconditional() && > + BrFirstSucc->getSuccessor(0) == L->getHeader() && > + BrFirstSucc->getParent()->getUniquePredecessor()) > + Ok = true; > + if (BrSecondSucc && BrSecondSucc->isUnconditional() && > + BrSecondSucc->getSuccessor(0) == L->getHeader() && > + BrSecondSucc->getParent()->getUniquePredecessor()) > + Ok = true; > + // The simple checks failed, try climbing the unique predecessor chain > + // up to the header. > + > + for (BasicBlock *BB = ExitBr->getParent(); BB && !Ok; ) { > BasicBlock *Pred = BB->getUniquePredecessor(); > if (!Pred) > return getCouldNotCompute(); > > anyway, this patch is only "a concept" of what I'm talking about. > > PS=Sorry for the bad english in the previous post :p > > 2012/2/8 Marcello Maggioni <hayarms at gmail.com>: >> Hello, I'm finding problems with BackEdgeTaken count calculation in >> even simple fortran loops with gfortran-4.6 + DragonEgg 3.0. >> >> Even for simple double loops like this one: >> >> program test2 >> integer i,j,k >> dimension k(100,100) >> do j=1,100 >> do i=1,100 >> k(i,j) = i >> enddo >> enddo >> write(*,*) k(1,30) >> end >> >> make the ScalarEvolution engine return "CouldNotCompute" even for the >> outer loop (the inner loop is fine). >> >> You can find a screenshot of the translation of this loop here (with >> -view-cfg Polly version): >> http://i.imgur.com/Jyaqd.png >> >> The problem seems to be the fact that the ScalarEvolution can't >> consider the outer loop exit branch instruction as the trivial case >> (where one of the successors of the exit block is the loop header or >> the exit block is the loop header itself) because of the (strange?) >> loop shape (the exit block instead of jumping to the header of the >> loop jumps instead to another block that increments the induction >> variable and has an unconditional branch to the loop header) and so >> starts backtracking the predecessors of the of the exit block and >> stops when it reaches the inner loop that has a block without a unique >> predecessor. >> >> What do you think about this problem? This makes , for example, >> difficult analyzing even simple fortran loops with Polly . >> I believe the case portrayed in the picture is the same to the trivial >> case (because the exit block jumps to a block with an unconditional >> jump to the header of the loop), am I right? >> >> I've written this little patch that adds this case to the trivial case : >> >> diff --git a/lib/Analysis/ScalarEvolution.cpp b/lib/Analysis/ScalarEvolution.cpp >> index daf7742..fcbaffe 100644 >> --- a/lib/Analysis/ScalarEvolution.cpp >> +++ b/lib/Analysis/ScalarEvolution.cpp >> @@ -4293,6 +4293,11 @@ ScalarEvolution::ComputeExitLimit(const Loop >> *L, BasicBlock *ExitingBlock) { >> // >> // FIXME: we should be able to handle switch instructions (with a >> single exit) >> BranchInst *ExitBr = dyn_cast<BranchInst>(ExitingBlock->getTerminator()); >> + BranchInst* BrFirstSucc = dyn_cast<BranchInst>(ExitBr-> >> + getSuccessor(0)->getTerminator()); >> + BranchInst* BrSecondSucc = dyn_cast<BranchInst>(ExitBr-> >> + getSuccessor(1)->getTerminator()); >> + >> if (ExitBr == 0) return getCouldNotCompute(); >> assert(ExitBr->isConditional() && "If unconditional, it can't be in loop!"); >> >> @@ -4315,8 +4320,12 @@ ScalarEvolution::ComputeExitLimit(const Loop >> *L, BasicBlock *ExitingBlock) { >> // >> if (ExitBr->getSuccessor(0) != L->getHeader() && >> ExitBr->getSuccessor(1) != L->getHeader() && >> - ExitBr->getParent() != L->getHeader()) { >> - // The simple checks failed, try climbing the unique predecessor chain >> + ExitBr->getParent() != L->getHeader() && >> + !((BrFirstSucc && BrFirstSucc->isUnconditional() && >> + BrFirstSucc->getSuccessor(0) == L->getHeader()) || >> + (BrSecondSucc && BrSecondSucc->isUnconditional() && >> + BrSecondSucc->getSuccessor(0) == L->getHeader())) ) { >> + // The simple checks failed, try climbing the unique predecessor chain >> // up to the header. >> bool Ok = false; >> for (BasicBlock *BB = ExitBr->getParent(); BB; ) { >> >> what do you think about this? There is a better solution to the >> problem? Is the compiler itself broken? >> >> Thank you >> >> Marcello-------------- next part -------------- A non-text attachment was scrubbed... Name: scevconcept.patch Type: application/octet-stream Size: 2395 bytes Desc: not available URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120208/f8cc55c8/attachment.obj>
Nick Lewycky
2012-Feb-08 23:38 UTC
[LLVMdev] BackedgeTakenCount calculation for fortran loops and DragonEgg gfortran-4.6
Your patch should include a testcase, see test/Analysis/ScalarEvolution for examples. "BranchInst* " should be "BranchInst *". You should have spaces after the // in your comments. One of the comment lines isn't indented properly. Nick On 8 February 2012 12:05, Marcello Maggioni <hayarms at gmail.com> wrote:> Attached > > 2012/2/8 Marcello Maggioni <hayarms at gmail.com>: > > Mmm, sorry, the patch I posted crashes if ExitBr is null (which it may > > be ...) , this one should be ok (and passess all the ScalarEvolution > > tests in LLVM): > > > > diff --git a/lib/Analysis/ScalarEvolution.cpp > b/lib/Analysis/ScalarEvolution.cpp > > index daf7742..b10fab2 100644 > > --- a/lib/Analysis/ScalarEvolution.cpp > > +++ b/lib/Analysis/ScalarEvolution.cpp > > @@ -4293,9 +4293,15 @@ ScalarEvolution::ComputeExitLimit(const Loop > > *L, BasicBlock *ExitingBlock) { > > // > > // FIXME: we should be able to handle switch instructions (with a > > single exit) > > BranchInst *ExitBr > dyn_cast<BranchInst>(ExitingBlock->getTerminator()); > > + > > if (ExitBr == 0) return getCouldNotCompute(); > > assert(ExitBr->isConditional() && "If unconditional, it can't be in > loop!"); > > > > + BranchInst* BrFirstSucc = dyn_cast<BranchInst>(ExitBr-> > > + > getSuccessor(0)->getTerminator()); > > + BranchInst* BrSecondSucc = dyn_cast<BranchInst>(ExitBr-> > > + > getSuccessor(1)->getTerminator()); > > + > > // At this point, we know we have a conditional branch that > > determines whether > > // the loop is exited. However, we don't know if the branch is > executed each > > // time through the loop. If not, then the execution count of the > > branch will > > @@ -4316,10 +4322,23 @@ ScalarEvolution::ComputeExitLimit(const Loop > > *L, BasicBlock *ExitingBlock) { > > if (ExitBr->getSuccessor(0) != L->getHeader() && > > ExitBr->getSuccessor(1) != L->getHeader() && > > ExitBr->getParent() != L->getHeader()) { > > - // The simple checks failed, try climbing the unique predecessor > chain > > - // up to the header. > > + > > bool Ok = false; > > - for (BasicBlock *BB = ExitBr->getParent(); BB; ) { > > + //Check if the one of the successor of the exit branch has the is a > block > > + //that has only one predecessor and has an unconditional branch to > the > > + //loop header > > + if (BrFirstSucc && BrFirstSucc->isUnconditional() && > > + BrFirstSucc->getSuccessor(0) == L->getHeader() && > > + BrFirstSucc->getParent()->getUniquePredecessor()) > > + Ok = true; > > + if (BrSecondSucc && BrSecondSucc->isUnconditional() && > > + BrSecondSucc->getSuccessor(0) == L->getHeader() && > > + BrSecondSucc->getParent()->getUniquePredecessor()) > > + Ok = true; > > + // The simple checks failed, try climbing the unique predecessor > chain > > + // up to the header. > > + > > + for (BasicBlock *BB = ExitBr->getParent(); BB && !Ok; ) { > > BasicBlock *Pred = BB->getUniquePredecessor(); > > if (!Pred) > > return getCouldNotCompute(); > > > > anyway, this patch is only "a concept" of what I'm talking about. > > > > PS=Sorry for the bad english in the previous post :p > > > > 2012/2/8 Marcello Maggioni <hayarms at gmail.com>: > >> Hello, I'm finding problems with BackEdgeTaken count calculation in > >> even simple fortran loops with gfortran-4.6 + DragonEgg 3.0. > >> > >> Even for simple double loops like this one: > >> > >> program test2 > >> integer i,j,k > >> dimension k(100,100) > >> do j=1,100 > >> do i=1,100 > >> k(i,j) = i > >> enddo > >> enddo > >> write(*,*) k(1,30) > >> end > >> > >> make the ScalarEvolution engine return "CouldNotCompute" even for the > >> outer loop (the inner loop is fine). > >> > >> You can find a screenshot of the translation of this loop here (with > >> -view-cfg Polly version): > >> http://i.imgur.com/Jyaqd.png > >> > >> The problem seems to be the fact that the ScalarEvolution can't > >> consider the outer loop exit branch instruction as the trivial case > >> (where one of the successors of the exit block is the loop header or > >> the exit block is the loop header itself) because of the (strange?) > >> loop shape (the exit block instead of jumping to the header of the > >> loop jumps instead to another block that increments the induction > >> variable and has an unconditional branch to the loop header) and so > >> starts backtracking the predecessors of the of the exit block and > >> stops when it reaches the inner loop that has a block without a unique > >> predecessor. > >> > >> What do you think about this problem? This makes , for example, > >> difficult analyzing even simple fortran loops with Polly . > >> I believe the case portrayed in the picture is the same to the trivial > >> case (because the exit block jumps to a block with an unconditional > >> jump to the header of the loop), am I right? > >> > >> I've written this little patch that adds this case to the trivial case : > >> > >> diff --git a/lib/Analysis/ScalarEvolution.cpp > b/lib/Analysis/ScalarEvolution.cpp > >> index daf7742..fcbaffe 100644 > >> --- a/lib/Analysis/ScalarEvolution.cpp > >> +++ b/lib/Analysis/ScalarEvolution.cpp > >> @@ -4293,6 +4293,11 @@ ScalarEvolution::ComputeExitLimit(const Loop > >> *L, BasicBlock *ExitingBlock) { > >> // > >> // FIXME: we should be able to handle switch instructions (with a > >> single exit) > >> BranchInst *ExitBr > dyn_cast<BranchInst>(ExitingBlock->getTerminator()); > >> + BranchInst* BrFirstSucc = dyn_cast<BranchInst>(ExitBr-> > >> + > getSuccessor(0)->getTerminator()); > >> + BranchInst* BrSecondSucc = dyn_cast<BranchInst>(ExitBr-> > >> + > getSuccessor(1)->getTerminator()); > >> + > >> if (ExitBr == 0) return getCouldNotCompute(); > >> assert(ExitBr->isConditional() && "If unconditional, it can't be in > loop!"); > >> > >> @@ -4315,8 +4320,12 @@ ScalarEvolution::ComputeExitLimit(const Loop > >> *L, BasicBlock *ExitingBlock) { > >> // > >> if (ExitBr->getSuccessor(0) != L->getHeader() && > >> ExitBr->getSuccessor(1) != L->getHeader() && > >> - ExitBr->getParent() != L->getHeader()) { > >> - // The simple checks failed, try climbing the unique predecessor > chain > >> + ExitBr->getParent() != L->getHeader() && > >> + !((BrFirstSucc && BrFirstSucc->isUnconditional() && > >> + BrFirstSucc->getSuccessor(0) == L->getHeader()) || > >> + (BrSecondSucc && BrSecondSucc->isUnconditional() && > >> + BrSecondSucc->getSuccessor(0) == L->getHeader())) ) { > >> + // The simple checks failed, try climbing the unique predecessor > chain > >> // up to the header. > >> bool Ok = false; > >> for (BasicBlock *BB = ExitBr->getParent(); BB; ) { > >> > >> what do you think about this? There is a better solution to the > >> problem? Is the compiler itself broken? > >> > >> Thank you > >> > >> Marcello > > _______________________________________________ > LLVM Developers mailing list > LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20120208/a700cf8b/attachment.html>
Marcello Maggioni
2012-Feb-08 23:50 UTC
[LLVMdev] BackedgeTakenCount calculation for fortran loops and DragonEgg gfortran-4.6
Well, it wasn't intended as a "real" patch to be included , but more as a "proof of concept" for a solution. Do you think it is a valid solution and I'm correct in my assumption? If so then I'll clean up the patch and attach a testcase for inclusion. Thanks! Marcello 2012/2/9 Nick Lewycky <nlewycky at google.com>:> Your patch should include a testcase, see test/Analysis/ScalarEvolution for > examples. "BranchInst* " should be "BranchInst *". You should have spaces > after the // in your comments. One of the comment lines isn't indented > properly. > > Nick > > On 8 February 2012 12:05, Marcello Maggioni <hayarms at gmail.com> wrote: >> >> Attached >> >> 2012/2/8 Marcello Maggioni <hayarms at gmail.com>: >> > Mmm, sorry, the patch I posted crashes if ExitBr is null (which it may >> > be ...) , this one should be ok (and passess all the ScalarEvolution >> > tests in LLVM): >> > >> > diff --git a/lib/Analysis/ScalarEvolution.cpp >> > b/lib/Analysis/ScalarEvolution.cpp >> > index daf7742..b10fab2 100644 >> > --- a/lib/Analysis/ScalarEvolution.cpp >> > +++ b/lib/Analysis/ScalarEvolution.cpp >> > @@ -4293,9 +4293,15 @@ ScalarEvolution::ComputeExitLimit(const Loop >> > *L, BasicBlock *ExitingBlock) { >> > // >> > // FIXME: we should be able to handle switch instructions (with a >> > single exit) >> > BranchInst *ExitBr >> > dyn_cast<BranchInst>(ExitingBlock->getTerminator()); >> > + >> > if (ExitBr == 0) return getCouldNotCompute(); >> > assert(ExitBr->isConditional() && "If unconditional, it can't be in >> > loop!"); >> > >> > + BranchInst* BrFirstSucc = dyn_cast<BranchInst>(ExitBr-> >> > + >> > getSuccessor(0)->getTerminator()); >> > + BranchInst* BrSecondSucc = dyn_cast<BranchInst>(ExitBr-> >> > + >> > getSuccessor(1)->getTerminator()); >> > + >> > // At this point, we know we have a conditional branch that >> > determines whether >> > // the loop is exited. However, we don't know if the branch is >> > executed each >> > // time through the loop. If not, then the execution count of the >> > branch will >> > @@ -4316,10 +4322,23 @@ ScalarEvolution::ComputeExitLimit(const Loop >> > *L, BasicBlock *ExitingBlock) { >> > if (ExitBr->getSuccessor(0) != L->getHeader() && >> > ExitBr->getSuccessor(1) != L->getHeader() && >> > ExitBr->getParent() != L->getHeader()) { >> > - // The simple checks failed, try climbing the unique predecessor >> > chain >> > - // up to the header. >> > + >> > bool Ok = false; >> > - for (BasicBlock *BB = ExitBr->getParent(); BB; ) { >> > + //Check if the one of the successor of the exit branch has the is a >> > block >> > + //that has only one predecessor and has an unconditional branch to >> > the >> > + //loop header >> > + if (BrFirstSucc && BrFirstSucc->isUnconditional() && >> > + BrFirstSucc->getSuccessor(0) == L->getHeader() && >> > + BrFirstSucc->getParent()->getUniquePredecessor()) >> > + Ok = true; >> > + if (BrSecondSucc && BrSecondSucc->isUnconditional() && >> > + BrSecondSucc->getSuccessor(0) == L->getHeader() && >> > + BrSecondSucc->getParent()->getUniquePredecessor()) >> > + Ok = true; >> > + // The simple checks failed, try climbing the unique predecessor >> > chain >> > + // up to the header. >> > + >> > + for (BasicBlock *BB = ExitBr->getParent(); BB && !Ok; ) { >> > BasicBlock *Pred = BB->getUniquePredecessor(); >> > if (!Pred) >> > return getCouldNotCompute(); >> > >> > anyway, this patch is only "a concept" of what I'm talking about. >> > >> > PS=Sorry for the bad english in the previous post :p >> > >> > 2012/2/8 Marcello Maggioni <hayarms at gmail.com>: >> >> Hello, I'm finding problems with BackEdgeTaken count calculation in >> >> even simple fortran loops with gfortran-4.6 + DragonEgg 3.0. >> >> >> >> Even for simple double loops like this one: >> >> >> >> program test2 >> >> integer i,j,k >> >> dimension k(100,100) >> >> do j=1,100 >> >> do i=1,100 >> >> k(i,j) = i >> >> enddo >> >> enddo >> >> write(*,*) k(1,30) >> >> end >> >> >> >> make the ScalarEvolution engine return "CouldNotCompute" even for the >> >> outer loop (the inner loop is fine). >> >> >> >> You can find a screenshot of the translation of this loop here (with >> >> -view-cfg Polly version): >> >> http://i.imgur.com/Jyaqd.png >> >> >> >> The problem seems to be the fact that the ScalarEvolution can't >> >> consider the outer loop exit branch instruction as the trivial case >> >> (where one of the successors of the exit block is the loop header or >> >> the exit block is the loop header itself) because of the (strange?) >> >> loop shape (the exit block instead of jumping to the header of the >> >> loop jumps instead to another block that increments the induction >> >> variable and has an unconditional branch to the loop header) and so >> >> starts backtracking the predecessors of the of the exit block and >> >> stops when it reaches the inner loop that has a block without a unique >> >> predecessor. >> >> >> >> What do you think about this problem? This makes , for example, >> >> difficult analyzing even simple fortran loops with Polly . >> >> I believe the case portrayed in the picture is the same to the trivial >> >> case (because the exit block jumps to a block with an unconditional >> >> jump to the header of the loop), am I right? >> >> >> >> I've written this little patch that adds this case to the trivial case >> >> : >> >> >> >> diff --git a/lib/Analysis/ScalarEvolution.cpp >> >> b/lib/Analysis/ScalarEvolution.cpp >> >> index daf7742..fcbaffe 100644 >> >> --- a/lib/Analysis/ScalarEvolution.cpp >> >> +++ b/lib/Analysis/ScalarEvolution.cpp >> >> @@ -4293,6 +4293,11 @@ ScalarEvolution::ComputeExitLimit(const Loop >> >> *L, BasicBlock *ExitingBlock) { >> >> // >> >> // FIXME: we should be able to handle switch instructions (with a >> >> single exit) >> >> BranchInst *ExitBr >> >> dyn_cast<BranchInst>(ExitingBlock->getTerminator()); >> >> + BranchInst* BrFirstSucc = dyn_cast<BranchInst>(ExitBr-> >> >> + >> >> getSuccessor(0)->getTerminator()); >> >> + BranchInst* BrSecondSucc = dyn_cast<BranchInst>(ExitBr-> >> >> + >> >> getSuccessor(1)->getTerminator()); >> >> + >> >> if (ExitBr == 0) return getCouldNotCompute(); >> >> assert(ExitBr->isConditional() && "If unconditional, it can't be in >> >> loop!"); >> >> >> >> @@ -4315,8 +4320,12 @@ ScalarEvolution::ComputeExitLimit(const Loop >> >> *L, BasicBlock *ExitingBlock) { >> >> // >> >> if (ExitBr->getSuccessor(0) != L->getHeader() && >> >> ExitBr->getSuccessor(1) != L->getHeader() && >> >> - ExitBr->getParent() != L->getHeader()) { >> >> - // The simple checks failed, try climbing the unique predecessor >> >> chain >> >> + ExitBr->getParent() != L->getHeader() && >> >> + !((BrFirstSucc && BrFirstSucc->isUnconditional() && >> >> + BrFirstSucc->getSuccessor(0) == L->getHeader()) || >> >> + (BrSecondSucc && BrSecondSucc->isUnconditional() && >> >> + BrSecondSucc->getSuccessor(0) == L->getHeader())) ) { >> >> + // The simple checks failed, try climbing the unique predecessor >> >> chain >> >> // up to the header. >> >> bool Ok = false; >> >> for (BasicBlock *BB = ExitBr->getParent(); BB; ) { >> >> >> >> what do you think about this? There is a better solution to the >> >> problem? Is the compiler itself broken? >> >> >> >> Thank you >> >> >> >> Marcello >> >> _______________________________________________ >> LLVM Developers mailing list >> LLVMdev at cs.uiuc.edu http://llvm.cs.uiuc.edu >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev >> >
Possibly Parallel Threads
- [LLVMdev] BackedgeTakenCount calculation for fortran loops and DragonEgg gfortran-4.6
- [LLVMdev] BackedgeTakenCount calculation for fortran loops and DragonEgg gfortran-4.6
- [LLVMdev] BackedgeTakenCount calculation for fortran loops and DragonEgg gfortran-4.6
- [LLVMdev] BackedgeTakenCount calculation for fortran loops and DragonEgg gfortran-4.6
- [LLVMdev] BackedgeTakenCount calculation for fortran loops and DragonEgg gfortran-4.6