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

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

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>