thr3ads.net - llvm dev - [LLVMdev] BackedgeTakenCount calculation for fortran loops and DragonEgg gfortran-4.6 [Feb 2012]

If this information is useful, please help other people find it:
Share via:

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

Nick Lewycky

2012-Feb-08 23:52 UTC

head link

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

On 8 February 2012 15:50, Marcello Maggioni <hayarms at gmail.com> wrote:
> 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.
>
I'm not sure -- when I tried to track the IR in your screenshot through the
code in SCEV I came up with a completely different reason it would return
the CNC than the one you gave in your email. It would really help to have a
testcase in .ll format.

Nick

> 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
> >>
> >
>-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120208/38feb6bb/attachment.html>

Marcello Maggioni

2012-Feb-09 00:14 UTC

head link

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

This is the .ll for that graph (attached). I think I understand what
you are saying.
This particular testcase returns CNC not because the exit block
doesn't have a unique predecessor, but because the unique predecessor
(the inner loop block) has a successor that is inside the loop (in
this case itself, because it's the inner loop block).

That doesn't change, anyway, the assuption that this condition ( an
exit block that jumps to a block with an unconditional jump that jumps
to the loop header and that has as unique predecessor the exit block)
is equivalent to jumping directly to the loop header.

2012/2/9 Nick Lewycky <nlewycky at google.com>:> On 8 February 2012 15:50, Marcello Maggioni <hayarms at gmail.com>
wrote:
>>
>> 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.
>
>
> I'm not sure -- when I tried to track the IR in your screenshot through
the
> code in SCEV I came up with a completely different reason it would return
> the CNC than the one you gave in your email. It would really help to have a
> testcase in .ll format.
>
> Nick
>
>>
>> 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
>> >>
>> >
>
>-------------- next part --------------
A non-text attachment was scrubbed...
Name: test2.preopt.ll
Type: application/octet-stream
Size: 3666 bytes
Desc: not available
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20120209/6b490e74/attachment.obj>

Reasonably Related Threads

Search for more possibly parallel threads

llvm dev - Feb 2012 - [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

Reasonably Related Threads