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

[Marcello Maggioni]

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
>>
>