[Bug fortran/31593] New: Invariant DO loop variables (and I/O)

[Bug fortran/31593] New: Invariant DO loop variables (and I/O)

[tkoenig at gcc dot gnu dot org]

Compare this:

$ cat count.f90
program main
  implicit none
  integer, parameter :: value = 747
  integer :: p1, p2, p3, p4
  integer :: i

  do i=1, 10
     do p1 = 1, value-2
        do p2 = p1 + 1, value - p1
           do p3 = p2 + 1, value - p1 - p2
              p4 = value - p1 - p2 - p3
              if (p1 * p2 * p3 * p4 == value * 1000000) &
                   print '(4(I0,:" "))',p1,p2,p3,p4
           end do
        end do
     end do
  end do
end program main
$ gfortran -O3 count.f90
$ time ./a.out > /dev/null

real    0m0.634s
user    0m0.620s
sys     0m0.004s


with the equivalent

$ cat count.c
#include <stdio.h>

const int value = 747;

int main()
{
  int i, p1, p2, p3, p4;

  for (i=1; i<=10; i++)
    {
      for (p1 = 1; p1 <= value - 2 ; p1++)
        {
          for (p2 = p1 + 1; p2 <= value - p1; p2++)
            {
              for (p3 = p2 + 1; p3 <= value - p1 - p2; p3++)
                {
                  p4 = value - p1 - p2 - p3;
                  if (p1 * p2 * p3 * p4 == value * 1000000)
                    printf("%d %d %d %d\n", p1, p2, p3, p4);
                }
            }
        }
    }
}
$ gcc -O3 count.c
$ time ./a.out > /dev/null

real    0m0.396s
user    0m0.380s
sys     0m0.000s


We don't

- take advantage of the fact that p1, p2, p3 and p4 cannot
  be legally changed in the do loop

- take advantage of the fact that the I/O statemetns don't change
  the values

so we miss out on common subexpression elimination.  Here's a
part from the *.optimized file:

<L34>:;
  p2.3 = p2;
  p3.5 = p2.3 + 1;
  D.1014 = (747 - p1) - p2.3;
  p3 = p3.5;
  if (p3.5 <= D.1014) goto <L35>; else goto <L12>;

<L35>:;
  p1.58 = p1;
  p2.60 = p2;
  p3.61 = p3;
  p4.7 = ((747 - p1.58) - p2.60) - p3.61;
  p4 = p4.7;
  if (((p2.60 * p1.58) * p3.61) * p4.7 == 747000000) goto <L8>; else goto <L9>;


-- 
           Summary: Invariant DO loop variables (and I/O)
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: enhancement
          Priority: P3
         Component: fortran
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: tkoenig at gcc dot gnu dot org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables (and I/O)

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2007-04-16 22:54 -------
This is not suprising as it is a dup of bug 20165 anyways.

*** This bug has been marked as a duplicate of 20165 ***


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |RESOLVED
         Resolution|                            |DUPLICATE


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tkoenig at gcc dot gnu dot org]

------- Comment #2 from tkoenig at gcc dot gnu dot org  2007-04-16 23:03 -------
(In reply to comment #1)
> This is not suprising as it is a dup of bug 20165 anyways.
> 
> *** This bug has been marked as a duplicate of 20165 ***

Only one part.

The other part is that we don't mark the variables in a do
statement as unchanging.

Consider the following:

$ cat count-3.f90
program main
  implicit none
  integer, parameter :: value = 747
  integer :: p1, p2, p3, p4
  integer :: i

  do i=1, 10
     do p1 = 1, value-2
        do p2 = p1 + 1, value - p1
           do p3 = p2 + 1, value - p1 - p2
              p4 = value - p1 - p2 - p3
              if (p1 * p2 * p3 * p4 == value * 1000000) &
                call output (p1, p2, p3, p4)
           end do
        end do
     end do
  end do
end program main

This produces the (partial) dump

<L34>:;
  p2.2 = p2;
  p3.4 = p2.2 + 1;
  D.1014 = (747 - p1) - p2.2;
  p3 = p3.4;
  if (p3.4 <= D.1014) goto <L35>; else goto <L12>;

<L35>:;
  p1.57 = p1;
  p2.59 = p2;
  p3.60 = p3;
  p4.6 = ((747 - p1.57) - p2.59) - p3.60;
  p4 = p4.6;
  if (((p2.59 * p1.57) * p3.60) * p4.6 == 747000000) goto <L8>; else goto <L9>;

Reopening, adjusting subject.


-- 

tkoenig at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |UNCONFIRMED
         Resolution|DUPLICATE                   |
            Summary|Invariant DO loop variables |Invariant DO loop variables
                   |(and I/O)                   |and subroutines


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2007-04-16 23:12 -------
                call output (p1, p2, p3, p4)

That still clobbers p1, p2, p3, and p4 as they are passed by reference so is it
really undefined code if output changes the values for the do loop?


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #4 from tobi at gcc dot gnu dot org  2007-04-17 01:14 -------
(In reply to comment #3)
>                 call output (p1, p2, p3, p4)
> 
> That still clobbers p1, p2, p3, and p4 as they are passed by reference so is it
> really undefined code if output changes the values for the do loop?

Yes.


-- 

tobi at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |tobi at gcc dot gnu dot org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-04-17 01:14:52
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[fxcoudert at gcc dot gnu dot org]

-- 

fxcoudert at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |fxcoudert at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2007-04-17 01:14:52         |2008-02-19 16:08:27
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[fxcoudert at gcc dot gnu dot org]

-- 

fxcoudert at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|fxcoudert at gcc dot gnu dot|unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[burnus at gcc dot gnu dot org]

------- Comment #5 from burnus at gcc dot gnu dot org  2009-07-02 12:36 -------
> >                 call output (p1, p2, p3, p4)
> > That still clobbers p1, p2, p3, and p4 as they are passed by reference so
> > is it really undefined code if output changes the values for the do loop?
> Yes.

Conformance can now be tested at runtime via -fcheck=do. If one wants to change
the loop variable, one should use "i=0; do; i = i + 1; if(i >= 10) exit; end
do" instead.

>From the F2003 standard, which also applies to loops of the form (2*i, i=1,N)
"8.1.6.4.2 The execution cycle":

"Except for the incrementation of the DO variable that occurs in step (3), the
DO variable shall neither be redefined nor become undefined while the DO
construct is active."


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tkoenig at gcc dot gnu dot org]

------- Comment #6 from tkoenig at gcc dot gnu dot org  2009-08-12 17:53 -------
We get a dramatic speedup when enclosing the arguments to
print in parentheses:

This is something we can do for

- write and print statements
- intent(in) arguments
- any do variable passed as an argument within the loop

$ gfortran -O2 count-2.f90 && time ./a.out > /dev/null

real    0m11.395s
user    0m11.361s
sys     0m0.004s
$ gfortran -O2 count-3.f90 && time ./a.out > /dev/null

real    0m4.607s
user    0m4.560s
sys     0m0.040s

$ cat count-2.f90
program main     
  implicit none  
  integer :: value
  integer :: p1, p2, p3, p4
  integer :: i             

  do value = 750,800
     do i=1, 10     
        do p1 = 1, value-2
           do p2 = p1 + 1, value - p1
              do p3 = p2 + 1, (value - (p1 + p2))/2
                 p4 = value - p1 - p2 - p3         
                 if (p1 * p2 * p3 * p4 == value * 1000000) &
                      print '(5(I0,:" "))',value,p1,p2,p3,p4
              end do                                        
           end do
        end do
     end do
  end do
end program main
$ cat count-3.f90
program main
  implicit none
  integer :: value
  integer :: p1, p2, p3, p4
  integer :: i

  do value = 750,800
     do i=1, 10
        do p1 = 1, value-2
           do p2 = p1 + 1, value - p1
              do p3 = p2 + 1, (value - (p1 + p2))/2
                 p4 = value - p1 - p2 - p3
                 if (p1 * p2 * p3 * p4 == value * 1000000) &
                      print '(5(I0,:" "))',(value),(p1),(p2),(p3),(p4)
              end do
           end do
        end do
     end do
  end do
end program main


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[Tobias Schlüter <tobias dot schlueter at physik dot uni-muenchen dot de>]

------- Comment #7 from =?ISO-8859-1?Q?Tobias_Schl=FCter?=
 <tobias dot schlueter at physik dot uni-muenchen dot de>  2009-08-12 18:11 -------
Subject: Re:  Invariant DO loop variables and subroutines

tkoenig at gcc dot gnu dot org wrote:
> ------- Comment #6 from tkoenig at gcc dot gnu dot org  2009-08-12 17:53 -------
> We get a dramatic speedup when enclosing the arguments to
> print in parentheses:
> 
> This is something we can do for
> 
> - write and print statements
> - intent(in) arguments
> - any do variable passed as an argument within the loop

An interesting approach.  As long as you don't print array slices in the 
loops this should work around the escaping pointer problem.  It comes at 
the risk of creating excessive copies.

Actually, perhaps the right way of achieving this is not to add 
OP_PARENTHESES in the frontend, but to do a copy when creating the call.

Cheers,
- Tobi


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tkoenig at gcc dot gnu dot org]

------- Comment #8 from tkoenig at gcc dot gnu dot org  2009-08-12 20:36 -------
(In reply to comment #7)

> An interesting approach.  As long as you don't print array slices in the 
> loops this should work around the escaping pointer problem.  It comes at 
> the risk of creating excessive copies.

Apparently, the optimizers are smart enough for that at least for
simple cases.

The loop in the following subroutine gets translated to

subroutine foo
  do i=1,10
    call bar((i))
  end do
end subroutine foo

       leal    -12(%ebp), %esi
        .p2align 4,,7
L2:
        movl    %ebx, -12(%ebp)
        addl    $1, %ebx
        movl    %esi, (%esp)
        call    bar_
        cmpl    $11, %ebx
        jne     L2

which is pretty good.

> Actually, perhaps the right way of achieving this is not to add 
> OP_PARENTHESES in the frontend, but to do a copy when creating the call.

This would likely have the same result, the subprogram

subroutine foo
  do i=1,10
    j = i
    call bar(j)
  end do
end subroutine foo

gets the same code as the one above.

For comparision, the unadorned

$ cat a.f90
subroutine foo
  do i=1,10
    call bar(i)
  end do
end subroutine foo

gets

        movl    $1, -12(%ebp)
.L2:
        movl    %ebx, (%esp)
        call    bar_
        movl    -12(%ebp), %eax
        leal    1(%eax), %edx
        cmpl    $10, %eax
        movl    %edx, -12(%ebp)
        jne     .L2


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #9 from tobi at gcc dot gnu dot org  2009-08-12 20:52 -------
Side remark:
  DO i = 1,10
    call bar(i)
  END DO
wouldn't be valid if bar changed its argument, i.e. the compiler should
generate the same, better code it does for the case where you copy the argument
(bar((i))).

I was worrying about the case where a whole array is passed as an argument, for
a contrived example say:
DO I=1,1000
  DO J=1,1000
     a(i,j) = i*j
     PRINT *, a  ! don't want to copy all of a here
  END DO
END DO

The remark about OP_PARENTHESES was more about a clean implementation. 
Implementing this via OP_PARENTHESES would likely only be a few lines here and
there, but it would be hackish as it would be workign around a deficiency
further down.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[jv244 at cam dot ac dot uk]

------- Comment #10 from jv244 at cam dot ac dot uk  2009-08-13 09:13 -------
(In reply to comment #9)

I believe there are at least two important independent issues. One is the fact
that the compiler ignores INTENT(IN) and similarly issues (see also PR 40194).
This holds for general variables. Loop variables have an even stronger
property, that it doesn't even matter if an INTENT is present.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2009-08-13 13:30 -------
  DO i = 1,10
    call bar(i)
  END DO

if bar may not modify i then the frontend can simply communicate that to the
middle-end by doing

  DO i = 1,10
    j = i;
    call bar (j)
  END DO

likewise if loop bounds are not allowed to be changed (are they?)

  Do i = n,m
    ...

to
  tmp1 = n
  tmp2 = m
  Do i = tmp1,tmp2
    ...


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #12 from tobi at gcc dot gnu dot org  2009-08-13 13:39 -------
(In reply to comment #11)
>   DO i = 1,10
>     call bar(i)
>   END DO
> 
> if bar may not modify i then the frontend can simply communicate that to the
> middle-end by doing
> 
>   DO i = 1,10
>     j = i;
>     call bar (j)
>   END DO

That's exactly what Thomas is achieving by adding parentheses.  Thomas, If you
want to tackle something more difficult, I'm willing to do this over the
weekend in order to warm up my knowledge of gfortran's internals.


-- 

tobi at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |tobi at gcc dot gnu dot org
                   |dot org                     |
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2008-02-19 16:08:27         |2009-08-13 13:39:23
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tkoenig at gcc dot gnu dot org]

------- Comment #13 from tkoenig at gcc dot gnu dot org  2009-08-13 18:55 -------
(In reply to comment #12)

> That's exactly what Thomas is achieving by adding parentheses.  Thomas, If you
> want to tackle something more difficult, I'm willing to do this over the
> weekend in order to warm up my knowledge of gfortran's internals.

I'm glad if you take this on.

Will you do this for scalar actual arguments corresponding to intent(in)
dummy arguments, and for scalar writes as well?


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[Tobias Schlüter <tobias dot schlueter at physik dot uni-muenchen dot de>]

------- Comment #14 from =?ISO-8859-1?Q?Tobias_Schl=FCter?=
 <tobias dot schlueter at physik dot uni-muenchen dot de>  2009-08-13 23:33 -------
Subject: Re:  Invariant DO loop variables and subroutines

tkoenig at gcc dot gnu dot org wrote:
> ------- Comment #13 from tkoenig at gcc dot gnu dot org  2009-08-13 18:55 -------
> (In reply to comment #12)
> 
>> That's exactly what Thomas is achieving by adding parentheses.  Thomas, If you
>> want to tackle something more difficult, I'm willing to do this over the
>> weekend in order to warm up my knowledge of gfortran's internals.
> 
> I'm glad if you take this on.
> 
> Will you do this for scalar actual arguments corresponding to intent(in)
> dummy arguments, and for scalar writes as well?

I'll start with the latter, and see if I can achieve the former afterwards.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #15 from tobi at gcc dot gnu dot org  2009-08-14 18:12 -------
I'm wondering if instead we can't simply mark all arguments to the transfer
functions in PRINT, WRITE and INTENT(IN) arguments as 'const *' instead of '*'.
 Are there any reasons against this?  I can't think of any except that this
would mean adding a new set of transfer functions to the library.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #16 from tobi at gcc dot gnu dot org  2009-08-14 19:28 -------
Created an attachment (id=18367)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18367&action=view)
use const * when writing

Thomas, can you please test the attached patch with your testcase from comment
#6.  I can't get compiled code working at the moment, I'm not sure if it is an
issue with my installation.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #17 from tobi at gcc dot gnu dot org  2009-08-14 19:55 -------
Created an attachment (id=18368)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18368&action=view)
Speed up loops where the loop variable is used as function argument inside the
loop

This patch gives the good assembly with the testcase from #8.  Again, I can't
run the testsuite right now, so if anybody could take care of this, I would be
grateful.

Let's see if INTENT(IN) arguments give in as easily.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[jvdelisle at gcc dot gnu dot org]

------- Comment #18 from jvdelisle at gcc dot gnu dot org  2009-08-14 20:18 -------
Patch applied cleanly, building , and will test shortly


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[mikael at gcc dot gnu dot org]

------- Comment #19 from mikael at gcc dot gnu dot org  2009-08-14 21:18 -------
(In reply to comment #17)
>From quickly looking at the code, the copy to real_to is probably unnecessary
because loop bounds are passed through gfc_evaluate_now before calling
gfc_trans_simple_do ( never mind if it gives the good assembly :) ).
Couldn't the same be made in gfc_trans_do ?


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #20 from tobi at gcc dot gnu dot org  2009-08-14 21:31 -------
Created an attachment (id=18369)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18369&action=view)
updated patch

Corrected patch, I copied the variables in the wrong order on loop entry,
clobbering the upper bound if it also happened to be the DO variable.


-- 

tobi at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  Attachment #18368|0                           |1
        is obsolete|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #21 from tobi at gcc dot gnu dot org  2009-08-14 21:44 -------
(In reply to comment #19)
> (In reply to comment #17)
> From quickly looking at the code, the copy to real_to is probably unnecessary
> because loop bounds are passed through gfc_evaluate_now before calling
> gfc_trans_simple_do ( never mind if it gives the good assembly :) ).

I suspected that this reason wouldn't hold.  Place a wrong statement on the
internet, you will no after a few seconds :)  The real reason is that no
pointer to the upper bound that is compared against can escape, so that better
assembler will result.  I will update the comment.

> Couldn't the same be made in gfc_trans_do ?

There, the number of iterations is calculated before the loop, so the problem
doesn't arise.  I'm guessing that before my patch, gfc_trans_simple_do actually
lead to a net slowdown of the generated code.  Lesson learnt: don't optimize
without measuring or at least looking at the generated code :)


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #22 from tobi at gcc dot gnu dot org  2009-08-14 21:46 -------
(In reply to comment #21)
> (In reply to comment #19)
> > (In reply to comment #17)
> > From quickly looking at the code, the copy to real_to is probably unnecessary
> > because loop bounds are passed through gfc_evaluate_now before calling
> > gfc_trans_simple_do ( never mind if it gives the good assembly :) ).
> 
> I suspected that this reason wouldn't hold.  Place a wrong statement on the
> internet, you will no after a few seconds :)  The real reason is that no
                     ^^ know
> pointer to the upper bound that is compared against can escape, so that better
                             ^^^^^^^^^^^^^^^^^^^^^^^^ scratch that, and one can
                                                      actually understand it.
> assembler will result.  I will update the comment.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tkoenig at gcc dot gnu dot org]

------- Comment #23 from tkoenig at gcc dot gnu dot org  2009-08-14 22:05 -------
(In reply to comment #20)
> Created an attachment (id=18369)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18369&action=view) [edit]
> updated patch
> 
> Corrected patch, I copied the variables in the wrong order on loop entry,
> clobbering the upper bound if it also happened to be the DO variable.

Hello Tobi,

your patch doesn't help a lot for this test case:

module foo                         
contains                           
  subroutine output(i1,i2,i3,i4,i5)
    print '(5(I0,:" "))',i1,i2,i3,i4,i5
  end subroutine output                
end module foo                         
program main                           
  use foo
  implicit none
  integer :: value
  integer :: p1, p2, p3, p4
  integer :: i

  do value = 750,800
     do i=1, 10
        do p1 = 1, value-2
           do p2 = p1 + 1, value - p1
              do p3 = p2 + 1, (value - (p1 + p2))/2
                 p4 = value - p1 - p2 - p3
                 if (p1 * p2 * p3 * p4 == value * 1000000) &
                 & call output(value,p1,p2,p3,p4)
              end do
           end do
        end do
     end do
  end do
end program main

Without your patch:

tkoenig@gcc16:~/Do$ gfortran -fdump-tree-original -O2 count-4.f90 && time
./a.out > /dev/null

real    0m8.448s
user    0m8.449s
sys     0m0.000s

With your patch:

tkoenig@gcc16:~/Do$ gfortran -fdump-tree-original -O2 count-4.f90 && time
./a.out > /dev/null

real    0m7.772s
user    0m7.768s
sys     0m0.004s

The test case

tkoenig@gcc16:~/Do$ cat count-5.f90
module foo                         
contains                           
  subroutine output(i1,i2,i3,i4,i5)
    print '(5(I0,:" "))',i1,i2,i3,i4,i5
  end subroutine output                
end module foo                         
program main                           
  use foo
  implicit none
  integer :: value
  integer :: p1, p2, p3, p4
  integer :: i

  do value = 750,800
     do i=1, 10
        do p1 = 1, value-2
           do p2 = p1 + 1, value - p1
              do p3 = p2 + 1, (value - (p1 + p2))/2
                 p4 = value - p1 - p2 - p3
                 if (p1 * p2 * p3 * p4 == value * 1000000) &
                 & call output((value),(p1),(p2),(p3),(p4))
              end do
           end do
        end do
     end do
  end do
end program main
tkoenig@gcc16:~/Do$ gfortran -fdump-tree-original -O2 count-5.f90 && time
./a.out > /dev/null

real    0m4.057s
user    0m4.056s

still produces much better code.

I think it would be better to use the original loop variable, and to create a
copy each time it is passed by reference.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #24 from tobi at gcc dot gnu dot org  2009-08-14 22:38 -------
(In reply to comment #23)

That's sad.  I'm guessing that everytime it enters one of the inner loops, it
has to deal with the fact that the upper bound escaped.  A way without all the
copying would be to set the DO variable to upper bound+1 after the loop, but
before the exit label.

I have a patch in the pipeline which makes INTENT(IN) arguments const pointers,
but that wouldn't suffice either.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #25 from tobi at gcc dot gnu dot org  2009-08-14 22:46 -------
(In reply to comment #23)

Actually, you're right.  In nested loops, there's no way without copying.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #26 from tobi at gcc dot gnu dot org  2009-08-14 22:58 -------
(In reply to comment #25)
> (In reply to comment #23)
> 
> Actually, you're right.  In nested loops, there's no way without copying.
> 
If it weren't for the outermost loop it would actually be perfectly legal to
modify 'value' inside the loops.  If there were a way of telling the compiler
"this pointer can't escape" this would be really easy to solve.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[jv244 at cam dot ac dot uk]

------- Comment #27 from jv244 at cam dot ac dot uk  2009-08-15 07:50 -------
(In reply to comment #26)
> If it weren't for the outermost loop it would actually be perfectly legal to
> modify 'value' inside the loops.  If there were a way of telling the compiler
> "this pointer can't escape" this would be really easy to solve.

actually value can be legally modified in the inner loops (I believe), only it
doesn't influence the loop count (which is determined before the loop start). I
believe it is only the do loop variable which is not allowed to be modified.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[jv244 at cam dot ac dot uk]

------- Comment #28 from jv244 at cam dot ac dot uk  2009-08-15 07:53 -------
(In reply to comment #23)

>   subroutine output(i1,i2,i3,i4,i5)
>     print '(5(I0,:" "))',i1,i2,i3,i4,i5
>   end subroutine output                

[..]

>                  if (p1 * p2 * p3 * p4 == value * 1000000) &
>                  & call output(value,p1,p2,p3,p4)
[..]
>                  if (p1 * p2 * p3 * p4 == value * 1000000) &
>                  & call output((value),(p1),(p2),(p3),(p4))
> still produces much better code.

obviously this optimization is only allowed if the arguments of 'output' would
be explicitly declared intent in (or the compiler nows this, e.g. because it is
an intrinsic or e.g. a write statement).


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tkoenig at gcc dot gnu dot org]

------- Comment #29 from tkoenig at gcc dot gnu dot org  2009-08-15 09:22 -------
Subject: Re:  Invariant DO loop variables and subroutines

On Sat, 2009-08-15 at 07:53 +0000, jv244 at cam dot ac dot uk wrote:
> 
> ------- Comment #28 from jv244 at cam dot ac dot uk  2009-08-15 07:53 -------
> (In reply to comment #23)
> 
> >   subroutine output(i1,i2,i3,i4,i5)
> >     print '(5(I0,:" "))',i1,i2,i3,i4,i5
> >   end subroutine output                
> 
> [..]
> 
> >                  if (p1 * p2 * p3 * p4 == value * 1000000) &
> >                  & call output(value,p1,p2,p3,p4)
> [..]
> >                  if (p1 * p2 * p3 * p4 == value * 1000000) &
> >                  & call output((value),(p1),(p2),(p3),(p4))
> > still produces much better code.
> 
> obviously this optimization is only allowed if the arguments of 'output' would
> be explicitly declared intent in (or the compiler nows this, e.g. because it is
> an intrinsic or e.g. a write statement).

It's the other way around:  If output were to modify any of its
arguments, the program would be illegal.  Therefore, the compiler can
assume that this doesn't happen.  Intent(in) would be redundant for this
particular case (though useful, so the compiler could easier detect
errors).


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tkoenig at gcc dot gnu dot org]

------- Comment #30 from tkoenig at gcc dot gnu dot org  2009-08-15 09:25 -------
Subject: Re:  Invariant DO loop variables and subroutines

On Fri, 2009-08-14 at 22:58 +0000, tobi at gcc dot gnu dot org wrote:
> 
> ------- Comment #26 from tobi at gcc dot gnu dot org  2009-08-14 22:58 -------
> (In reply to comment #25)
> > (In reply to comment #23)
> > 
> > Actually, you're right.  In nested loops, there's no way without copying.
> > 
> If it weren't for the outermost loop it would actually be perfectly legal to
> modify 'value' inside the loops.  If there were a way of telling the compiler
> "this pointer can't escape" this would be really easy to solve.

Escaping pointers for non-target dummy arguments can't happen in
Fortran, can they?  Could we just disable this (or ad a
TREE_CANNOT_ALIAS flag to the middle end, which is on by default for
Fortran)?


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #31 from tobi at gcc dot gnu dot org  2009-08-15 09:51 -------
(In reply to comment #30)
> Escaping pointers for non-target dummy arguments can't happen in
> Fortran, can they?  Could we just disable this (or ad a
> TREE_CANNOT_ALIAS flag to the middle end, which is on by default for
> Fortran)?

Yes.  I've asked Richard about this on the mailing list.  BTW with my patches,
aermodf90 runs ~8% faster, and the other polyhedron benchmarks also seem to
have consistently improved.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[jv244 at cam dot ac dot uk]

------- Comment #32 from jv244 at cam dot ac dot uk  2009-08-15 10:05 -------
(In reply to comment #29)

> It's the other way around:  If output were to modify any of its
> arguments, the program would be illegal.  Therefore, the compiler can
> assume that this doesn't happen.  Intent(in) would be redundant for this
> particular case (though useful, so the compiler could easier detect
> errors).
that's true for pX, but value can be modified by output. I.e. this is (afaict)
valid fortran that write the numbers from 1 to 10
n=10
DO i=1,n
n=0
write(6,*)i
ENDDO


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[Tobias Schlüter <tobias dot schlueter at physik dot uni-muenchen dot de>]

------- Comment #33 from =?ISO-8859-1?Q?Tobias_Schl=FCter?=
 <tobias dot schlueter at physik dot uni-muenchen dot de>  2009-08-15 10:17 -------
Subject: Re:  Invariant DO loop variables and subroutines

jv244 at cam dot ac dot uk wrote:
> ------- Comment #32 from jv244 at cam dot ac dot uk  2009-08-15 10:05 -------
> (In reply to comment #29)
> 
>> It's the other way around:  If output were to modify any of its
>> arguments, the program would be illegal.  Therefore, the compiler can
>> assume that this doesn't happen.  Intent(in) would be redundant for this
>> particular case (though useful, so the compiler could easier detect
>> errors).
> that's true for pX, but value can be modified by output. I.e. this is (afaict)
> valid fortran that write the numbers from 1 to 10
> n=10
> DO i=1,n
> n=0
> write(6,*)i
> ENDDO

Actually, we're buggy there, and my patch fixes it.  I'm just now trying 
out testcases.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tkoenig at gcc dot gnu dot org]

------- Comment #34 from tkoenig at gcc dot gnu dot org  2009-08-15 10:57 -------
(In reply to comment #33)

> Actually, we're buggy there, and my patch fixes it.  I'm just now trying 
> out testcases.

Are we really buggy?

$ cat gaga.f90
n=10
do i=1,n
call foo(n)
print *,i
end do
end

subroutine foo(n)
n=4
end
$ gfortran -O2 gaga.f90 && ./a.out
           1
           2
           3
           4
           5
           6
           7
           8
           9
          10
$ gfortran-4.4 -O2 gaga.f90 && ./a.out
           1
           2
           3
           4
           5
           6
           7
           8
           9
          10


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[Tobias Schlüter <tobias dot schlueter at physik dot uni-muenchen dot de>]

------- Comment #35 from =?ISO-8859-1?Q?Tobias_Schl=FCter?=
 <tobias dot schlueter at physik dot uni-muenchen dot de>  2009-08-15 10:58 -------
Subject: Re:  Invariant DO loop variables and subroutines

tkoenig at gcc dot gnu dot org wrote:
> ------- Comment #34 from tkoenig at gcc dot gnu dot org  2009-08-15 10:57 -------
> (In reply to comment #33)
> 
>> Actually, we're buggy there, and my patch fixes it.  I'm just now trying 
>> out testcases.
> 
> Are we really buggy?

No, I looked at the wrong thing, sorry.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #36 from tobi at gcc dot gnu dot org  2009-08-16 15:57 -------
I have a patch which copies DO loop variables that are passed as arguments to
functions, which gives the same speedup as enclosing the arguments into
parentheses.  Now I only need to figure out how to make that patch pass the
testsuite :)


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tkoenig at gcc dot gnu dot org]

------- Comment #37 from tkoenig at gcc dot gnu dot org  2009-08-16 16:12 -------
Subject: Re:  Invariant DO loop variables and subroutines

On Sun, 2009-08-16 at 15:57 +0000, tobi at gcc dot gnu dot org wrote:
> Now I only need to figure out how to make that patch pass the
> testsuite :)

If you post it, I might be able to help in testing :-)


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #38 from tobi at gcc dot gnu dot org  2009-08-16 16:20 -------
Thanks(In reply to comment #37)
> Subject: Re:  Invariant DO loop variables and subroutines
> 
> On Sun, 2009-08-16 at 15:57 +0000, tobi at gcc dot gnu dot org wrote:
> > Now I only need to figure out how to make that patch pass the
> > testsuite :)
> 
> If you post it, I might be able to help in testing :-)

Thanks for the offer, but I'd rather have it look clean before I show it to the
world :)


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #39 from tobi at gcc dot gnu dot org  2009-08-16 17:00 -------
Sigh, with the patch capacita.f90 loses 4%.  Your testcase really is nasty,
Thomas!  :)


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #40 from tobi at gcc dot gnu dot org  2009-08-17 22:08 -------
Created an attachment (id=18392)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=18392&action=view)
Patch for savin function arguments

This patch copies do loops which are passed as actual arguments to a temporary
variable and then passes the temporary.  The patch creates one copy for every
single call, so this could be done better.  Also, the naming is not finalized. 
Finally, this would need someone who is more familiar with the scalarizer's
workings to make sure that it doesn't break anything.  I'm actually surprised
that the patch passes the testsuite.

I don't plan to submit this, because Michael Matz is apparently working on
something better, that would at least make part of this patch superfluous.  See
<http://gcc.gnu.org/ml/fortran/2009-08/msg00200.html>.  If his patch goes in,
the part that creates the copy could be dropped and instead the function
argument could be properly labeled read-only.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[tobi at gcc dot gnu dot org]

------- Comment #41 from tobi at gcc dot gnu dot org  2009-08-17 22:39 -------
(In reply to comment #40)

One more thing: my previous benchmarks were wrong, I had an error in my setup. 
With a correct benchmark, polyhedron improves slightly in the testcases where
the change is outside the measurement noise.  This includes capacita.f90 which
gains some 2%.  Further, and as expected, with the patch, Thomas's testcases
from comment #6 both run at the same speed that only the 'call by value'
version did without the patch.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[steven at gcc dot gnu dot org]

------- Comment #42 from steven at gcc dot gnu dot org  2009-10-08 11:06 -------
Add Matz, following comment #40.  Micha, maybe you can open a separate bug
report for the issues you mention in your mail
(http://gcc.gnu.org/ml/fortran/2009-08/msg00200.html) and make that new PR
block this existing one?


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |matz at gcc dot gnu dot org
   Last reconfirmed|2009-08-13 13:39:23         |2009-10-08 11:06:55
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593

[Bug fortran/31593] Invariant DO loop variables and subroutines

[matz at gcc dot gnu dot org]

------- Comment #43 from matz at gcc dot gnu dot org  2009-10-08 11:24 -------
There already is PR31094 about this enhancement.


-- 

matz at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |31094


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=31593