[LLVMdev] BackedgeTakenCount calculation for fortran loops and DragonEgg gfortran-4.6

[Nick Lewycky]

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>