Marcello Maggioni
2012-Feb-08 16:42 UTC
[LLVMdev] BackedgeTakenCount calculation for fortran loops and DragonEgg gfortran-4.6
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
Marcello Maggioni
2012-Feb-08 20:02 UTC
[LLVMdev] BackedgeTakenCount calculation for fortran loops and DragonEgg gfortran-4.6
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
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>
Apparently Analagous 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