Fortran loops

Fortran loops

[Jan Hubicka]

Hello,
I have a Fortran question.  The following program loops infinitly when compiled
with ifort -O0, while it does the expected number of iterations with gfortran.
The issue is that we do produce quite ineffective code to deal with
side cases like this.

is the program bellow valid and expected to terminate?  If so I guess we want
to have it as a testcase.

Thanks,
Honza

program test_program
integer(4) :: b(2), a(22), x
integer(8) :: suma

b(1) = huge(x)-10
b(2) = huge(x)

call test2(b, suma)
print *,suma

end program test_program
function test2(array, s)
  integer(4) :: i, block(9), array(2)
  integer (8) :: s
  s = 1

  do i = array(1), array(2)
      s = s + 1
  end do

end function test2

Re: Fortran loops

[William Clodius]

The code with huge as array(2) is not standard conforming and gfortran can any of:
1. Not attempt to deal with the resulting overflow and generate the efficient code with the likely infinite runtime;
2. Insert a test for the overflow and generate a runtime error;
3. Insert a test for the overflow and kluge around the overflow as a special case giving the expected result; and
4. Treat i as integer(8) and not generate an overflow in spite of the type declaration.

There may of course be other options. I suspect ifort by default does 1 with the compiler switches used, while gfortran does 3 unless debugging switches are set, and does 2 with some combination of compiler debugging switches.

> On Jun 27, 2016, at 6:56 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> 
> Hello,
> I have a Fortran question.  The following program loops infinitly when compiled
> with ifort -O0, while it does the expected number of iterations with gfortran.
> The issue is that we do produce quite ineffective code to deal with
> side cases like this.
> 
> is the program bellow valid and expected to terminate?  If so I guess we want
> to have it as a testcase.
> 
> Thanks,
> Honza
> 
> program test_program
> integer(4) :: b(2), a(22), x
> integer(8) :: suma
> 
> b(1) = huge(x)-10
> b(2) = huge(x)
> 
> call test2(b, suma)
> print *,suma
> 
> end program test_program
> function test2(array, s)
>  integer(4) :: i, block(9), array(2)
>  integer (8) :: s
>  s = 1
> 
>  do i = array(1), array(2)
>      s = s + 1
>  end do
> 
> end function test2
> 

Re: Fortran loops

[Adam Hirst]

[-- Attachment #1: Type: text/plain, Size: 2826 bytes --]

Hi there William,

Why exactly is this not standard conforming? In the main program unit
he's calling Huge(x) where x is of type integer(4) and storing it in an
element of array b (also of integer(4)); and this is being passed to
dummy array "array" in the subroutine (yet again of integer(4)). When I
print (or use gdb) to view the contents of this variable it appears on
my machine to indeed be 2^n(machine dependent, I assume)-1.

Is there some bizzare quirk about the Huge() routine that I am missing?
I would have checked the definition in my copy of Modern Fortran
Explained or in the Standard but I am not at my work desk right now.

Cheers,
Adam Hirst

P.S. I was just about to send a message saying that by my reckoning, the
program should have indeed terminated with a result of 12 (with the
addition that the Function should of course have been defined as a
Subroutine, I guess that was just a typo.)

On 27/06/16 19:45, William Clodius wrote:
> The code with huge as array(2) is not standard conforming and gfortran can any of:
> 1. Not attempt to deal with the resulting overflow and generate the efficient code with the likely infinite runtime;
> 2. Insert a test for the overflow and generate a runtime error;
> 3. Insert a test for the overflow and kluge around the overflow as a special case giving the expected result; and
> 4. Treat i as integer(8) and not generate an overflow in spite of the type declaration.
> 
> There may of course be other options. I suspect ifort by default does 1 with the compiler switches used, while gfortran does 3 unless debugging switches are set, and does 2 with some combination of compiler debugging switches.
> 
>> On Jun 27, 2016, at 6:56 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>
>> Hello,
>> I have a Fortran question.  The following program loops infinitly when compiled
>> with ifort -O0, while it does the expected number of iterations with gfortran.
>> The issue is that we do produce quite ineffective code to deal with
>> side cases like this.
>>
>> is the program bellow valid and expected to terminate?  If so I guess we want
>> to have it as a testcase.
>>
>> Thanks,
>> Honza
>>
>> program test_program
>> integer(4) :: b(2), a(22), x
>> integer(8) :: suma
>>
>> b(1) = huge(x)-10
>> b(2) = huge(x)
>>
>> call test2(b, suma)
>> print *,suma
>>
>> end program test_program
>> function test2(array, s)
>>  integer(4) :: i, block(9), array(2)
>>  integer (8) :: s
>>  s = 1
>>
>>  do i = array(1), array(2)
>>      s = s + 1
>>  end do
>>
>> end function test2
>>
> 

-- 
Using GPG? Add my key, and respond to me with it enabled!
Also, feel free to verify my key with me online or in person!

Not using GPG? You should, it's easy!
https://www.enigmail.net/documentation/quickstart.php


[-- Attachment #2: OpenPGP digital signature --]
[-- Type: application/pgp-signature, Size: 473 bytes --]

Re: Fortran loops

[William Clodius]

The standard defines that on each iteration at the end of each loop
i = i + increment
where the default increment is 1. In this case at the start of the last cycle of the loop
i = huge(0)
For the default compiler switches on modern processors the default integer kind is a 32 bit twos complement integer. For a 32 bit twos complement integer
huge(0) == 2**31-1
For a twos complement integer the increment of huge(0) results in an overflow so
huge(0) + 1 == -2**31
i.e. a negative integer. Therefore the final increment of i will not satisfy “normal” integer arithmetic. By having an implied code operation that doesn’t satisfy “normal” arithmetic the code is not standard conforming. With this requirement on conformance the determination of the iteration for a do loop of the form
do i=m1, m2, m3
…
end do

is very simply evaluated as
i = i + m3
if (i > m2) exit

With i a twos complement, and m3 the default value of 1 then on the last cycle
i = huge(0) + 1 ! => i = -2**31
if (i > m3) exit ! => if (-2**31 > 2**31-1) exit => no exit and the loop continues to cycle.

The latest versions of the Fortran standard describes the loop cycle for standard conforming code not directly in terms of the incrementation by rather as the equivalent of
number of iterations = max(0, (m2-m1+m3)/m3)
This can be used to keep track of the number of iterations separate from the loop variable avoiding the problem with the if (i > m3) exit test, but at the cost of calculating the expression max(0, (m2-m1+m3)/m3), and perhaps having cyclic iterations of both the loop variable and the cycle count. The expression (m2-m1+m3)/m3 can be expensive for small cycle counts if m3 is not known to be a fixed power of two, or if the compiler doesn’t recognize the optimization possible for a fixed power of two. (Of course for the default m3==1, (m2-m1+m3)/m3==m2-m1+1). Having to keep track of two incrementing quantities can also be a significant overhead for simple loops, but for this simple loop i is not directly used so at higher optimizations its calculation can be optimized away.

The problem can also be circumvented by using a larger bit size integer for the calculations so that the overflow never happens.


> On Jun 27, 2016, at 7:55 PM, Adam Hirst <ahirst@cedint.upm.es> wrote:
> 
> Hi there William,
> 
> Why exactly is this not standard conforming? In the main program unit
> he's calling Huge(x) where x is of type integer(4) and storing it in an
> element of array b (also of integer(4)); and this is being passed to
> dummy array "array" in the subroutine (yet again of integer(4)). When I
> print (or use gdb) to view the contents of this variable it appears on
> my machine to indeed be 2^n(machine dependent, I assume)-1.
> 
> Is there some bizzare quirk about the Huge() routine that I am missing?
> I would have checked the definition in my copy of Modern Fortran
> Explained or in the Standard but I am not at my work desk right now.
> 
> Cheers,
> Adam Hirst
> 
> P.S. I was just about to send a message saying that by my reckoning, the
> program should have indeed terminated with a result of 12 (with the
> addition that the Function should of course have been defined as a
> Subroutine, I guess that was just a typo.)
> 
> On 27/06/16 19:45, William Clodius wrote:
>> The code with huge as array(2) is not standard conforming and gfortran can any of:
>> 1. Not attempt to deal with the resulting overflow and generate the efficient code with the likely infinite runtime;
>> 2. Insert a test for the overflow and generate a runtime error;
>> 3. Insert a test for the overflow and kluge around the overflow as a special case giving the expected result; and
>> 4. Treat i as integer(8) and not generate an overflow in spite of the type declaration.
>> 
>> There may of course be other options. I suspect ifort by default does 1 with the compiler switches used, while gfortran does 3 unless debugging switches are set, and does 2 with some combination of compiler debugging switches.
>> 
>>> On Jun 27, 2016, at 6:56 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>> 
>>> Hello,
>>> I have a Fortran question.  The following program loops infinitly when compiled
>>> with ifort -O0, while it does the expected number of iterations with gfortran.
>>> The issue is that we do produce quite ineffective code to deal with
>>> side cases like this.
>>> 
>>> is the program bellow valid and expected to terminate?  If so I guess we want
>>> to have it as a testcase.
>>> 
>>> Thanks,
>>> Honza
>>> 
>>> program test_program
>>> integer(4) :: b(2), a(22), x
>>> integer(8) :: suma
>>> 
>>> b(1) = huge(x)-10
>>> b(2) = huge(x)
>>> 
>>> call test2(b, suma)
>>> print *,suma
>>> 
>>> end program test_program
>>> function test2(array, s)
>>> integer(4) :: i, block(9), array(2)
>>> integer (8) :: s
>>> s = 1
>>> 
>>> do i = array(1), array(2)
>>>     s = s + 1
>>> end do
>>> 
>>> end function test2
>>> 
>> 
> 
> -- 
> Using GPG? Add my key, and respond to me with it enabled!
> Also, feel free to verify my key with me online or in person!
> 
> Not using GPG? You should, it's easy!
> https://www.enigmail.net/documentation/quickstart.php
> 

Re: Fortran loops

[Anton Shterenlikht]

>is the program bellow valid and expected to terminate?  If so I guess we want

No, the program is not conforming.
You cannot CALL a function.

Anton

>
>Thanks,
>Honza
>
>program test_program
>integer(4) :: b(2), a(22), x
>integer(8) :: suma
>
>b(1) = huge(x)-10
>b(2) = huge(x)
>
>call test2(b, suma)
>print *,suma
>
>end program test_program
>function test2(array, s)
>  integer(4) :: i, block(9), array(2)
>  integer (8) :: s
>  s = 1
>
>  do i = array(1), array(2)
>      s = s + 1
>  end do
>
>end function test2
>
>

Re: Fortran loops

[Jan Hubicka]

> > Martin implemented the C-style codegen and it does improve code quality.
> > If the fact that we produce the complex loop code above is just QOI, perhaps
> > we can introduce a flag controlling this and turn into C-style loop expansion
> > by default when optimizing?
> > The do-3.f90 testcase tests some of those so it will need to be split into
> > valid loops and invalid loops.
> 
> I guess it might be GCC on its own removing the exit test based on
> undefined-overflow
> and computing an upper bound on the iteration.

It is explicitly testing loops that are unefined according to this discussion
define TEST_LOOP(var,from,to,step,total,test,final) \                          
  TEST_LOOP(i1, -huge(i1)-1_1, huge(i1), 1_1, int(huge(i1))*2+2, test_i1, huge(i1)+1_1)
this is loop from INT_MIN to INT_MAX which can't be implemented in c-style manner without
a wider type
> 
> So if the testcases are really invalid I suppose that at least with
> -Ofast the Fortran
> FE could avoid the extra check.  But IIRC the issue appeared on valid
> loops as well.

I don't know of any other testcase than one above.  I guess we could implement flag,
default it for -Ofast and see what is the impact and consequently discuss O2/O3.
Any suggestions for flag name? -ffast-do-loops?

> (that said - I've been here before)

Honza
> 
> Richard.
> 
> > Honza
> >
> >> Dominique
> >> > On Jun 27, 2016, at 6:56 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> >> >
> >> > Hello,
> >> > I have a Fortran question.  The following program loops infinitly when compiled
> >> > with ifort -O0, while it does the expected number of iterations with gfortran.
> >> > The issue is that we do produce quite ineffective code to deal with
> >> > side cases like this.
> >> >
> >> > is the program bellow valid and expected to terminate?  If so I guess we want
> >> > to have it as a testcase.
> >> >
> >> > Thanks,
> >> > Honza
> >> >
> >> > program test_program
> >> > integer(4) :: b(2), a(22), x
> >> > integer(8) :: suma
> >> >
> >> > b(1) = huge(x)-10
> >> > b(2) = huge(x)
> >> >
> >> > call test2(b, suma)
> >> > print *,suma
> >> >
> >> > end program test_program
> >> > function test2(array, s)
> >> >  integer(4) :: i, block(9), array(2)
> >> >  integer (8) :: s
> >> >  s = 1
> >> >
> >> >  do i = array(1), array(2)
> >> >      s = s + 1
> >> >  end do
> >> >
> >> > end function test2
> >> >

Re: Fortran loops

[Richard Biener]

On Tue, Jun 28, 2016 at 2:10 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> IIRC this has already been discussed in the past (gfortran.dg/do_1.f90).
>> The Fortran standard requires that the variable i is equal to array(2)+1 on the loop exit, which causes an overflow if array(2) is equal to huge(i).
>> So the code is invalid when b(2) = huge(x), but I don’t see why the overflow of the exit value should lead to an infinite loop.
>
> The reason why I ask (again as I just noticed - thanks for reminding :) is that
> the C equivalent:
>
> for(i=low;i<=high;i++)
>   ... body ...
>
> is a lot easier to compile, but it will loop infinitly when the upper bound
> happens to be INT_MAX.  To avoid that Fortran FE expand the loop as:
>
> if (low<high)
>   {
>     i=low;
>     do {
>       ... body ...
>       if (i==high)
>         break;
>       i++
>     }
>     while (1)
>   }
>
> This results in at least one extra compare and usually also extra register needed.
> If we could avoid this codegen based on fact that such loops are undefined, we would
> get improvements in thight and deeply nested loops. I.e. in exchange2 benchmark.
>
> Martin implemented the C-style codegen and it does improve code quality.
> If the fact that we produce the complex loop code above is just QOI, perhaps
> we can introduce a flag controlling this and turn into C-style loop expansion
> by default when optimizing?
> The do-3.f90 testcase tests some of those so it will need to be split into
> valid loops and invalid loops.

I guess it might be GCC on its own removing the exit test based on
undefined-overflow
and computing an upper bound on the iteration.

So if the testcases are really invalid I suppose that at least with
-Ofast the Fortran
FE could avoid the extra check.  But IIRC the issue appeared on valid
loops as well.
(that said - I've been here before)

Richard.

> Honza
>
>> Dominique
>> > On Jun 27, 2016, at 6:56 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> >
>> > Hello,
>> > I have a Fortran question.  The following program loops infinitly when compiled
>> > with ifort -O0, while it does the expected number of iterations with gfortran.
>> > The issue is that we do produce quite ineffective code to deal with
>> > side cases like this.
>> >
>> > is the program bellow valid and expected to terminate?  If so I guess we want
>> > to have it as a testcase.
>> >
>> > Thanks,
>> > Honza
>> >
>> > program test_program
>> > integer(4) :: b(2), a(22), x
>> > integer(8) :: suma
>> >
>> > b(1) = huge(x)-10
>> > b(2) = huge(x)
>> >
>> > call test2(b, suma)
>> > print *,suma
>> >
>> > end program test_program
>> > function test2(array, s)
>> >  integer(4) :: i, block(9), array(2)
>> >  integer (8) :: s
>> >  s = 1
>> >
>> >  do i = array(1), array(2)
>> >      s = s + 1
>> >  end do
>> >
>> > end function test2
>> >

Re: Fortran loops

[Jan Hubicka]

> IIRC this has already been discussed in the past (gfortran.dg/do_1.f90). 
> The Fortran standard requires that the variable i is equal to array(2)+1 on the loop exit, which causes an overflow if array(2) is equal to huge(i). 
> So the code is invalid when b(2) = huge(x), but I don’t see why the overflow of the exit value should lead to an infinite loop.

The reason why I ask (again as I just noticed - thanks for reminding :) is that
the C equivalent:

for(i=low;i<=high;i++)
  ... body ...

is a lot easier to compile, but it will loop infinitly when the upper bound
happens to be INT_MAX.  To avoid that Fortran FE expand the loop as:

if (low<high)
  {
    i=low;
    do {
      ... body ...
      if (i==high)
	break;
      i++
    }
    while (1)
  }

This results in at least one extra compare and usually also extra register needed.
If we could avoid this codegen based on fact that such loops are undefined, we would
get improvements in thight and deeply nested loops. I.e. in exchange2 benchmark.

Martin implemented the C-style codegen and it does improve code quality.
If the fact that we produce the complex loop code above is just QOI, perhaps
we can introduce a flag controlling this and turn into C-style loop expansion
by default when optimizing?
The do-3.f90 testcase tests some of those so it will need to be split into
valid loops and invalid loops.  

Honza

> Dominique
> > On Jun 27, 2016, at 6:56 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> > 
> > Hello,
> > I have a Fortran question.  The following program loops infinitly when compiled
> > with ifort -O0, while it does the expected number of iterations with gfortran.
> > The issue is that we do produce quite ineffective code to deal with
> > side cases like this.
> > 
> > is the program bellow valid and expected to terminate?  If so I guess we want
> > to have it as a testcase.
> > 
> > Thanks,
> > Honza
> > 
> > program test_program
> > integer(4) :: b(2), a(22), x
> > integer(8) :: suma
> > 
> > b(1) = huge(x)-10
> > b(2) = huge(x)
> > 
> > call test2(b, suma)
> > print *,suma
> > 
> > end program test_program
> > function test2(array, s)
> >  integer(4) :: i, block(9), array(2)
> >  integer (8) :: s
> >  s = 1
> > 
> >  do i = array(1), array(2)
> >      s = s + 1
> >  end do
> > 
> > end function test2
> > 

Re: Fortran loops

[William Clodius]

I am slightly surprised you special case to avoid calculating the iteration count for increments of +/-1. The iteration count is easiest to determine for these two increments.

> On Jun 27, 2016, at 10:22 PM, FX <fxcoudert@gmail.com> wrote:
> 
>> The Fortran standard requires that the variable i is equal to array(2)+1 on the loop exit, which causes an overflow if array(2) is equal to huge(i). 
>> So the code is invalid when b(2) = huge(x), but I don’t see why the overflow of the exit value should lead to an infinite loop.
> 
> In general, DO loops in Fortran are more messy than in C, because they are not defined in terms of a condition but instead the standard clearly calls for the calculation of an iteration count which is then decremented.
> 
> Dominique is right that the code is invalid, because on the last iteration of the DO execution cycle, the value of I is is incremented from HUGE(I) and thus overflowing. However, as a quality of implementation, I think it would be nice for this code which has clear meaning not to give rise to undefined behavior, because the value of I is not used.
> 
> Generally in the Fortran front-end we implement DO loops with an iteration count, as the standard specifies them. However, the case of integer DO loops with ±1 increments is handled as a special case in gfc_trans_simple_do() [trans-stmt.c], without an actual count.
> 
> FX

Re: Fortran loops

[FX]

> The Fortran standard requires that the variable i is equal to array(2)+1 on the loop exit, which causes an overflow if array(2) is equal to huge(i). 
> So the code is invalid when b(2) = huge(x), but I don’t see why the overflow of the exit value should lead to an infinite loop.

In general, DO loops in Fortran are more messy than in C, because they are not defined in terms of a condition but instead the standard clearly calls for the calculation of an iteration count which is then decremented.

Dominique is right that the code is invalid, because on the last iteration of the DO execution cycle, the value of I is is incremented from HUGE(I) and thus overflowing. However, as a quality of implementation, I think it would be nice for this code which has clear meaning not to give rise to undefined behavior, because the value of I is not used.

Generally in the Fortran front-end we implement DO loops with an iteration count, as the standard specifies them. However, the case of integer DO loops with ±1 increments is handled as a special case in gfc_trans_simple_do() [trans-stmt.c], without an actual count.

FX

Re: Fortran loops

[Dominique d'Humières]

> Le 27 juin 2016 à 21:36, Dominique d'Humières <dominiq@lps.ens.fr> a écrit :
> 
> IIRC this has already been discussed in the past (gfortran.dg/do_1.f90). 

pr54932!-(

Dominique

Re: Fortran loops

[Adam Hirst]

I don't know how the compiler handles this exactly, but my "educated
guess" would be that it depends on whether the loop is unrolled and on
whether the incrementing of the loop index variable occurs before or
after the check at the "start" of each loop iteration.

If "at" (i.e. just before, while still inside) the end of the "last"
iteration the value is huge(x), and it then decides to add one (causing
it to overflow to a -ve number), and THEN compare to huge(x) to see
whether the loop is over, it ought then go on forever infinitely
repeating the entire span of the integer type.

But I'm not an "informed" person. :)

~ Adam

On 27/06/16 21:36, Dominique d'Humières wrote:
> IIRC this has already been discussed in the past (gfortran.dg/do_1.f90). 
> The Fortran standard requires that the variable i is equal to array(2)+1 on the loop exit, which causes an overflow if array(2) is equal to huge(i). 
> So the code is invalid when b(2) = huge(x), but I don’t see why the overflow of the exit value should lead to an infinite loop.
> Dominique
>> On Jun 27, 2016, at 6:56 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
>>
>> Hello,
>> I have a Fortran question.  The following program loops infinitly when compiled
>> with ifort -O0, while it does the expected number of iterations with gfortran.
>> The issue is that we do produce quite ineffective code to deal with
>> side cases like this.
>>
>> is the program bellow valid and expected to terminate?  If so I guess we want
>> to have it as a testcase.
>>
>> Thanks,
>> Honza
>>
>> program test_program
>> integer(4) :: b(2), a(22), x
>> integer(8) :: suma
>>
>> b(1) = huge(x)-10
>> b(2) = huge(x)
>>
>> call test2(b, suma)
>> print *,suma
>>
>> end program test_program
>> function test2(array, s)
>>  integer(4) :: i, block(9), array(2)
>>  integer (8) :: s
>>  s = 1
>>
>>  do i = array(1), array(2)
>>      s = s + 1
>>  end do
>>
>> end function test2
>>
> 

-- 
Using GPG? Add my key, and respond to me with it enabled!
Also, feel free to verify my key with me online or in person!

Not using GPG? You should, it's easy!
https://www.enigmail.net/documentation/quickstart.php

Re: Fortran loops

[Dominique d'Humières]

IIRC this has already been discussed in the past (gfortran.dg/do_1.f90). 
The Fortran standard requires that the variable i is equal to array(2)+1 on the loop exit, which causes an overflow if array(2) is equal to huge(i). 
So the code is invalid when b(2) = huge(x), but I don’t see why the overflow of the exit value should lead to an infinite loop.
Dominique
> On Jun 27, 2016, at 6:56 PM, Jan Hubicka <hubicka@ucw.cz> wrote:
> 
> Hello,
> I have a Fortran question.  The following program loops infinitly when compiled
> with ifort -O0, while it does the expected number of iterations with gfortran.
> The issue is that we do produce quite ineffective code to deal with
> side cases like this.
> 
> is the program bellow valid and expected to terminate?  If so I guess we want
> to have it as a testcase.
> 
> Thanks,
> Honza
> 
> program test_program
> integer(4) :: b(2), a(22), x
> integer(8) :: suma
> 
> b(1) = huge(x)-10
> b(2) = huge(x)
> 
> call test2(b, suma)
> print *,suma
> 
> end program test_program
> function test2(array, s)
>  integer(4) :: i, block(9), array(2)
>  integer (8) :: s
>  s = 1
> 
>  do i = array(1), array(2)
>      s = s + 1
>  end do
> 
> end function test2
>