If Fortran requires i to be HUGE(i) + 1 after the loop body then what does
it say about the overflow?

That is, what would be valid at the end of this loop?

  if (i .ne. HUGE(i) + 1) call abort

?

(In reply to comment #1)
> If Fortran requires i to be HUGE(i) + 1 after the loop body then what does
> it say about the overflow?

Interesting question.


The Fortran standard just states (F2008):

"8.1.6.6.4 Loop termination"

"For a DO construct that is not a DO CONCURRENT construct, the loop terminates, and the DO construct becomes inactive, when any of the following occurs.
[...]
"* The iteration count is determined to be zero or the scalar-logical-expr is false, when tested during step (1) of the above execution cycle."
[...]
"When a DO construct becomes inactive, the DO variable, if any, of the DO construct retains its last defined value."


where (1) is the first step of the iteration (8.1.6.6.2 The execution cycle):

 "(1) The iteration count, if any, is tested. If it is zero, the loop terminates and the DO construct becomes inactive. [...]
 "(2) The range of the loop is executed.
 "(3) The iteration count, if any, is decremented by one. The DO variable, if any, is incremented by the value of the incrementation parameter m3."



Additionally, the standard specifies:

"7.1.5.2.4 Evaluation of numeric intrinsic operations"
"The execution of any numeric operation whose result is not defined by the arithmetic used by the processor is prohibited."

"7.1.5.2.4 Evaluation of numeric intrinsic operations"
"The execution of any numeric operation whose result is not defined by the
arithmetic used by the processor is prohibited."

Hm, the arithmetic used by the processor specifies that HUGE(i) + 1 is -INF.
Does that mean the value after the loop should be the wrapped value?

From the sentence above I do not read that the standard requires a
specific behavior, just that it prohibits undefined behavior.  Which
means this is similar to C implementation specific behavior?  Does
the standard require us to be consistent there then?  Currently GCC
assumes signed overflow invokes undefined behavior.

(In reply to comment #3)
> "7.1.5.2.4 Evaluation of numeric intrinsic operations"
> "The execution of any numeric operation whose result is not defined by the
> arithmetic used by the processor is prohibited."

(Note that "processor" in the standard refers to the combination of compiler, libraries, operating system and hardware/CPU.)


> Hm, the arithmetic used by the processor specifies that HUGE(i) + 1 is -INF.

I think you mean -HUGE(i)-1. (That's at least the hardware part of the "processor".)


> Does that mean the value after the loop should be the wrapped value?

Seems so - at least that is what one gets after "huge(i)+1" - at least if one regards it as defined by the processor.


> From the sentence above I do not read that the standard requires a
> specific behavior, just that it prohibits undefined behavior.

The wording is a bit vague as it is a catch all phrase.

Well, to a certain extend it is undefined behaviour: It depends on the "processor" whether it is valid or not.


> Which means this is similar to C implementation specific behavior?

I don't know the exact wording for this case in the C standard, but I assume so.


> Does the standard require us to be consistent there then?  Currently GCC
> assumes signed overflow invokes undefined behavior.

I think it doesn't require (but permits) this consistency. (As the semantic differs between C and Fortran it can't require it.) The standard only specifies interoperability with the "companion processor" for variables and function calls.


Thus, the question is mostly what can a user (reasonably) expect. Users seemingly like to use HUGE in loop bounds (cf. also PR 40205). For real-world code I could imagine some use like
  do i = 1, huge(i)
    ...
    if (cond) exit
  end do
But I am not sure whether any real-world code contains such algorithms. At least the two codes I use don't.

I asked at https://groups.google.com/forum/?fromgroups=#!topic/comp.lang.fortran/mkbYH6F9G2M and two former J3 committee members concur that the code of comment 0 is invalid:

Dick Hendrickson wrote: 'I think there was an interpretation request a few years ago about something like this.  I think the answer was "bad program".'

Richard Maine wrote: [...] 'the answer from the standard, which is basically
that the program is not conforming on procesors where the result for i
is not defined.'


Thus, I close the bug as INVALID.

(In reply to comment #5)
> I asked at
> https://groups.google.com/forum/?fromgroups=#!topic/comp.lang.fortran/mkbYH6F9G2M
> and two former J3 committee members concur that the code of comment 0 is
> invalid:
> 
> Dick Hendrickson wrote: 'I think there was an interpretation request a few
> years ago about something like this.  I think the answer was "bad program".'
> 
> Richard Maine wrote: [...] 'the answer from the standard, which is basically
> that the program is not conforming on procesors where the result for i
> is not defined.'
> 
> 
> Thus, I close the bug as INVALID.

I don't care enough to re-open the PR, but you'll
see that at least one person disagrees with both
former J3 members.

The Standard does not define 'incremented' and
'incrementation', and in particular, these words
are not defined in terms of the numeric intrinsic
operations and so you cannot appeal to Section 7.

(In reply to comment #6)
> but you'll see that at least one person disagrees with both
> former J3 members.

The only way to get a definite answer is to fill an interpretation request and wait until it has passed both the J3 and WG5 vote. However, based on my reading of the standard and the three Richards (Maine, Hendrickson, and Biener), it is invalid. I haven't seen so far any standard-backed argument which reasons why it should be valid. (Besides that it were nice and I concur that, if one forgets about the value after the loop, it seems to be reasonable if m2 == huge(int-do-var) were valid.)

I quickly tried to find the IR request


> The Standard does not define 'incremented' and
> 'incrementation', and in particular, these words
> are not defined in terms of the numeric intrinsic
> operations and so you cannot appeal to Section 7.

I disagree. One can surely read something differently, but I think it is very difficult to have a reading which makes both sense in terms of the English language ("increment" = "the action or process of increasing especially in quantity or value : enlargement"; source: Marriam-Webster) and the common understanding how programs behave.

For instance, for

  do i = 2, 5, 1
    print *, i
  end do

The standard has: "The DO variable, if any, is incremented by the value of the incrementation parameter m3."

In my reading of the standard, the program will print 2, 3, 4, 5 and after the loop i has the value 6. That matches in my understanding "i = i + 1" where m3 == 1; thus, I fail to see why Section 7.1.5.2.4 shouldn't apply in this case.

Can you come up with a (somewhat sensible) different interpretation which still allows the program of comment 0?

(I concur that the invalidity of the program when m2 == huge(integer-do-variable) is a bit surprising at a glance, but that doesn't make the program valid. I also concur that one could have written the standard differently such that the program becomes valid.)

On Wed, Oct 17, 2012 at 06:51:08PM +0000, burnus at gcc dot gnu.org wrote:
> 
> > The Standard does not define 'incremented' and
> > 'incrementation', and in particular, these words
> > are not defined in terms of the numeric intrinsic
> > operations and so you cannot appeal to Section 7.
> 
> I disagree. One can surely read something differently, but I think it is very
> difficult to have a reading which makes both sense in terms of the English
> language ("increment" = "the action or process of increasing especially in
> quantity or value : enlargement"; source: Marriam-Webster) and the common
> understanding how programs behave.
> 
> For instance, for
> 
>   do i = 2, 5, 1
>     print *, i
>   end do
> 
> The standard has: "The DO variable, if any, is incremented by the value of the
> incrementation parameter m3."
> 
> In my reading of the standard, the program will print 2, 3, 4, 5 and after the
> loop i has the value 6. That matches in my understanding "i = i + 1" where m3
> == 1; thus, I fail to see why Section 7.1.5.2.4 shouldn't apply in this case.
> 
> Can you come up with a (somewhat sensible) different interpretation which still
> allows the program of comment 0?
> 

As I point out in c.l.f, the incrementataion process is
not defined by the standard.  While certainly, one would
assume that this process is i = i + m3 and so Section 7
rules apply.  The incrementation process could be done
in some other manner such as

   integer(8)
   j = int(i,8) + m3
   if (j < int(huge(i),8) + 1) then
      i = j
   else
      i = - huge(i) - 1 + m3 ! Assume wrap around semantics
   end if                    ! Preventing a possible hardware trap

or the incrementation process could be implemented via
bit-wise shift, and, and [x]or.  With bit manipulations
none of the numeric intrinsic operations are used, so
section 7 does not apply.

> (I concur that the invalidity of the program when m2 ==
> huge(integer-do-variable) is a bit surprising at a glance,
> but that doesn't make the program valid. I also concur that
> one could have written the standard differently such that
> the program becomes valid.)

The standard simply should have stated that the incrementation
process follows the rules of 7.1.5.2.4. 

As I said I don't care enough about the PR to 
re-open it.  In any event, gfortran should 
probably issue a warning if m2=huge(i) and
m3 > 0.

> Thus, I close the bug as INVALID.
... in wich case could you, please, update the testcase to be valid and remove
the XFAIL I introduced?

Honza

> ... in wich case could you, please, update the testcase to be valid and remove
> the XFAIL I introduced?

I cannot commit anything, but the XFAIL can be fixed in several ways:
(1) keep the test, but restrict it to option -O0
(2) change the test along the following line to make it valid:

--- ../_clean/gcc/testsuite/gfortran.dg/do_1.f90	2012-10-18 20:35:25.000000000 +0200
+++ gcc/testsuite/gfortran.dg/do_1.f90	2012-10-23 18:31:32.000000000 +0200
@@ -1,4 +1,4 @@
-! { dg-do run { xfail *-*-* } }
+! { dg-do run }
 ! XFAIL is tracked in PR 54932
 ! Program to check corner cases for DO statements.
 program do_1
@@ -7,18 +7,18 @@ program do_1
 
   ! limit=HUGE(i), step 1
   j = 0
-  do i = HUGE(i) - 10, HUGE(i), 1
+  do i = HUGE(i) - 11, HUGE(i) - 1, 1
     j = j + 1
   end do
   if (j .ne. 11) call abort
   ! limit=HUGE(i), step > 1
   j = 0
-  do i = HUGE(i) - 10, HUGE(i), 2
+  do i = HUGE(i) - 11, HUGE(i) - 1, 2
     j = j + 1
   end do
   if (j .ne. 6) call abort
   j = 0
-  do i = HUGE(i) - 9, HUGE(i), 2
+  do i = HUGE(i) - 10, HUGE(i) - 1, 2
     j = j + 1
   end do
   if (j .ne. 5) call abort
@@ -62,7 +62,7 @@ function test1(r, step)
   integer test1, r, step
   integer k, n
   k = 0
-  do n = HUGE(n) - r, HUGE(n), step
+  do n = HUGE(n) - r - 1, HUGE(n) - 1, step
     k = k + 1
   end do
   test1 = k

(tested on darwin),
(3) do (1) and add a new test along (2),
(4) ...

As asked in several other mails, would it be possible that the optimizer emits a warning/error when it relies on a DETECTED undefined behavior (here the number of unrolling does not match the number of iterations computed from the loop bounds)?

(In reply to comment #9)
> > Thus, I close the bug as INVALID.
> ... in wich case could you, please, update the testcase to be valid and remove
> the XFAIL I introduced?

We jump through some hoops in or DO loop code generation to execute
a loop until HUGE(i) in a way that somebody who did not read the
standard well might expect, but which is actually invalid.

If we do not do this any more, then we can probably simplify our DO
loops considerably.

We should also warn about invalid code in the FE.

(In reply to comment #11)
> > > Thus, I close the bug as INVALID.
> > ... in wich case could you, please, update the testcase to be valid and remove
> > the XFAIL I introduced?
>
> We jump through some hoops in or DO loop code generation to execute
> a loop until HUGE(i) in a way that somebody who did not read the
> standard well might expect, but which is actually invalid.
>
> If we do not do this any more, then we can probably simplify our DO
> loops considerably.

This is probably too late for 4.8.0. The following patch takes advantage of the new option -fno-aggressive-loop-optimizations to remove the xfail (and the two XPASS at -O0 and -O1):

--- /opt/gcc/_gcc_clean/gcc/testsuite/gfortran.dg/do_1.f90	2012-10-18 00:34:47.000000000 +0200
+++ /opt/gcc/work/gcc/testsuite/gfortran.dg/do_1.f90	2013-01-31 22:02:16.000000000 +0100
@@ -1,5 +1,5 @@
-! { dg-do run { xfail *-*-* } }
-! XFAIL is tracked in PR 54932
+! { dg-do run }
+! { dg-additional-options "-fno-aggressive-loop-optimizations" }
 ! Program to check corner cases for DO statements.
 program do_1
   implicit none

Tested on x86_64-apple-darwin10 and powerpc-apple-darwin9.

> We should also warn about invalid code in the FE.

One example is

program test_real_do
	integer n
	integer x
	n=0
	do x=0.0,10.0,0.1
		n=n+1
	end do
	print *, "N is ", n
end program test_real_do

which on x86_64-apple-darwin10 gives

Program received signal SIGFPE: Floating-point exception - erroneous arithmetic operation.

when executed. This is due to the division by zero in

    x = 0;
    countm1.0 = 10 / 0;
    while (1)
      {
        {
          unsigned int countm1t.1;

          n = n + 1;
          L.1:;
          x = NON_LVALUE_EXPR <x>;
          countm1t.1 = countm1.0;
          countm1.0 = countm1.0 + 4294967295;
          if (countm1t.1 == 0) goto L.2;
        }
      }
    L.2:;

The FE should detect that the stride is zero and output an error.

Note that on powerpc-apple-darwin9, the same test (with the same dump-tree-original) runs and outputs

 N is            1

!?-(

> 
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54932
> 
> --- Comment #12 from Dominique d'Humieres <dominiq at lps dot ens.fr> 2013-02-01 13:59:11 UTC ---
> (In reply to comment #11)
> > > > Thus, I close the bug as INVALID.
> > > ... in wich case could you, please, update the testcase to be valid and remove
> > > the XFAIL I introduced?
> >
> > We jump through some hoops in or DO loop code generation to execute
> > a loop until HUGE(i) in a way that somebody who did not read the
> > standard well might expect, but which is actually invalid.
> >
> > If we do not do this any more, then we can probably simplify our DO
> > loops considerably.
> 
> This is probably too late for 4.8.0. The following patch takes advantage of the
> new option -fno-aggressive-loop-optimizations to remove the xfail (and the two
> XPASS at -O0 and -O1):

This seems like good idea even fo 4.8.  Please also split the testcase - it contains
several tests and only one has invalid overflow.

Honza

(In reply to comment #13)
> Please also split the testcase - it contains
> several tests and only one has invalid overflow.

Actually there are three of them
(a)

program do_1
  implicit none
  integer i, j

  ! limit=HUGE(i), step 1
  j = 0
  do i = HUGE(i) - 10, HUGE(i), 1
    j = j + 1
  end do
!  print *, i
  if (j .ne. 11) call abort
end program

(b)

program do_1
  implicit none
  integer i, j

  ! limit=HUGE(i), step > 1
  j = 0
  do i = HUGE(i) - 10, HUGE(i), 2
    j = j + 1
  end do
  if (j .ne. 6) call abort
!  print *, i
end program

(c)

program do_1
  implicit none
  integer i, j

  ! limit=HUGE(i), step > 1
  j = 0
  do i = HUGE(i) - 9, HUGE(i), 2
    j = j + 1
  end do
!  print *, i
  if (j .ne. 5) call abort

end program

Only (a) aborts and only if the PRINT is commented. (b) and (c) don't abort even in the PRINT is uncommented.

Finally I have tested

program do_1
  implicit none
  integer i, j, i1, i2, i3, j1, j2, j3

  ! limit=HUGE(i), step 1
  j = 0
  do i = HUGE(i) - 10, HUGE(i), 1
    j = j + 1
  end do
  i1 = i
  j1 = j
!  if (j .ne. 11) call abort
  ! limit=HUGE(i), step > 1
  j = 0
  do i = HUGE(i) - 10, HUGE(i), 2
    j = j + 1
  end do
  i2 = i
  j2 = j
!  if (j .ne. 6) call abort
  j = 0
  do i = HUGE(i) - 9, HUGE(i), 2
    j = j + 1
  end do
  i3 = i
  j3 = j
!  if (j .ne. 5) call abort

  ! Same again, but unknown loop step
  if (test1(10, 1) .ne. 11) call abort
  if (test1(10, 2) .ne. 6) call abort
  if (test1(9, 2) .ne. 5) call abort

  print *, i3, j3
  if (j3 .ne. 5) call abort
  print *, i2, j2
  if (j2 .ne. 6) call abort
  print *, i1, j1
  if (j1 .ne. 11) call abort
contains
! Returns the number of iterations performed.
function test1(r, step)
  implicit none
  integer test1, r, step
  integer k, n
  k = 0
  do n = HUGE(n) - r, HUGE(n), step
    k = k + 1
  end do
  print *, n, k
  test1 = k
end function

end program

which shows that a contained function is enough to hide the invalid behavior, which detected for the three loops when put together.

Since very recently (between 20130313 and 20130315) gfortran.dg/do_1.f90
execution started to XPASS not only at -O0/-O1, but at every optimisation level.
I think it would be bad to release 4.8.0 with that testsuite noise, but nothing
has happened on this front for a long time.

How to proceed?  Simply remove the xfail, add -fno-aggressive-loop-optimizations
as Dominique proposed?

  Rainer

> Since very recently (between 20130313 and 20130315) gfortran.dg/do_1.f90
> execution started to XPASS not only at -O0/-O1, but at every optimisation
> level.
> I think it would be bad to release 4.8.0 with that testsuite noise, but nothing
> has happened on this front for a long time.

I believe it was Jakub's patch that disabled the transformation for some obvious wrong code cases.
> 
> How to proceed?  Simply remove the xfail, add
> -fno-aggressive-loop-optimizations
> as Dominique proposed?

Or perhaps disable the XFAIL when the testcase is valid fortran and we get it right
now (even though we do it by accident more than by design)

Honza

Author: ro
Date: Wed Mar 20 11:34:56 2013
New Revision: 196821

URL: http://gcc.gnu.org/viewcvs?rev=196821&root=gcc&view=rev
Log:
Don't XFAIL gfortran.dg/do_1.f90 (PR fortran/54932)

	PR fortran/54932
	* gfortran.dg/do_1.f90: Don't xfail.

Modified:
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gfortran.dg/do_1.f90