diff mbox

[0/2,fortran] Better code generation for DO loops with +-1 step

Message ID c1dd7016-53bc-0ff9-cb26-36054bfdbaaa@suse.cz
State New
Headers show

Commit Message

Martin Liška July 8, 2016, 8:33 a.m. UTC 
On 07/07/2016 04:40 PM, Jan Hubicka wrote:
>>
>> Why is the behavior only undefined for step 1 if the last iteration IV
>> increment overflows?
>> Doesn't this apply to all step values?
> 
> This is what Fortran standard says:
> 
>   The iteration count is established and is the value of the expression (m2-m1+m3)/m3 unless that value is negative,
>   in which case the iteration count is 0.
> 
> My reading of this is that the do statement is undefined whenever the expression above is undefined
> (m1 is lower bound, m2 is upper bound, m3 is step) and because I think the evaulation order of
> m2-m1+m3 is not fixed, I think the statement is not defined whethever (m2-m1), (m1+m3) or (m2-m1)+m3
> overflows or underflows as signed integer.
> 
> For example it is not valid to iterate from -10 to INT_MAX with step 1.
> Honza
> 

Hi.

I'm attaching a candidate patch that emits the warnings. Problem with current implementation of loop generation
(w/ step different than 1) is that it utilizes unsigned type, thus the calculation of iteration count works
even though the expression overflows:

  do i = array(1), array(2), 17 
      block(i) = block(i) + 10
  end do

is transformed to:

    D.3428 = (*array)[0];
    D.3429 = (*array)[1];
    i = D.3428;
    countm1.0 = ((unsigned int) D.3429 - (unsigned int) D.3428) / 17;, if (D.3429 < D.3428)
      {
        goto L.2;
      };

Thoughts about the patch?
Martin

Comments

Jakub Jelinek July 8, 2016, 8:40 a.m. UTC | #1 
On Fri, Jul 08, 2016 at 10:33:45AM +0200, Martin Liška wrote:
> On 07/07/2016 04:40 PM, Jan Hubicka wrote:
> >>
> >> Why is the behavior only undefined for step 1 if the last iteration IV
> >> increment overflows?
> >> Doesn't this apply to all step values?
> > 
> > This is what Fortran standard says:
> > 
> >   The iteration count is established and is the value of the expression (m2-m1+m3)/m3 unless that value is negative,
> >   in which case the iteration count is 0.
> > 
> > My reading of this is that the do statement is undefined whenever the expression above is undefined
> > (m1 is lower bound, m2 is upper bound, m3 is step) and because I think the evaulation order of
> > m2-m1+m3 is not fixed, I think the statement is not defined whethever (m2-m1), (m1+m3) or (m2-m1)+m3

m1+m3?  Did you mean m3-m1 or -m1+m3 instead?

	Jakub
Jan Hubicka July 8, 2016, 9:03 a.m. UTC | #2 
> On Fri, Jul 08, 2016 at 10:33:45AM +0200, Martin Liška wrote:
> > On 07/07/2016 04:40 PM, Jan Hubicka wrote:
> > >>
> > >> Why is the behavior only undefined for step 1 if the last iteration IV
> > >> increment overflows?
> > >> Doesn't this apply to all step values?
> > > 
> > > This is what Fortran standard says:
> > > 
> > >   The iteration count is established and is the value of the expression (m2-m1+m3)/m3 unless that value is negative,
> > >   in which case the iteration count is 0.
> > > 
> > > My reading of this is that the do statement is undefined whenever the expression above is undefined
> > > (m1 is lower bound, m2 is upper bound, m3 is step) and because I think the evaulation order of
> > > m2-m1+m3 is not fixed, I think the statement is not defined whethever (m2-m1), (m1+m3) or (m2-m1)+m3
> 
> m1+m3?  Did you mean m3-m1 or -m1+m3 instead?

Ah yes, -m1+m3.  But I am by no means language expert - this was meant as a heads up to Fortran
people :)

Honza
> 
> 	Jakub
Jakub Jelinek July 8, 2016, 9:05 a.m. UTC | #3 
On Fri, Jul 08, 2016 at 11:03:35AM +0200, Jan Hubicka wrote:
> > On Fri, Jul 08, 2016 at 10:33:45AM +0200, Martin Liška wrote:
> > > On 07/07/2016 04:40 PM, Jan Hubicka wrote:
> > > >>
> > > >> Why is the behavior only undefined for step 1 if the last iteration IV
> > > >> increment overflows?
> > > >> Doesn't this apply to all step values?
> > > > 
> > > > This is what Fortran standard says:
> > > > 
> > > >   The iteration count is established and is the value of the expression (m2-m1+m3)/m3 unless that value is negative,
> > > >   in which case the iteration count is 0.
> > > > 
> > > > My reading of this is that the do statement is undefined whenever the expression above is undefined
> > > > (m1 is lower bound, m2 is upper bound, m3 is step) and because I think the evaulation order of
> > > > m2-m1+m3 is not fixed, I think the statement is not defined whethever (m2-m1), (m1+m3) or (m2-m1)+m3
> > 
> > m1+m3?  Did you mean m3-m1 or -m1+m3 instead?
> 
> Ah yes, -m1+m3.  But I am by no means language expert - this was meant as a heads up to Fortran
> people :)

Heads up to Fortran people should be sent to fortran@gcc.gnu.org ;)

	Jakub
FX Coudert July 8, 2016, 9:12 a.m. UTC | #4 
>>>>> This is what Fortran standard says:
>>>>> 
>>>>>  The iteration count is established and is the value of the expression (m2-m1+m3)/m3 unless that value is negative,
>>>>>  in which case the iteration count is 0.
>>>>> 
>>>>> My reading of this is that the do statement is undefined whenever the expression above is undefined
>>>>> (m1 is lower bound, m2 is upper bound, m3 is step) and because I think the evaulation order of
>>>>> m2-m1+m3 is not fixed, I think the statement is not defined whethever (m2-m1), (m1+m3) or (m2-m1)+m3

In the Fortran standard, (m2-m1+m3)/m3 is a mathematical expression, not a “construct”. So it cannot be “undefined”.
If you have explicit cases where you are asking “is this valid or invalid” please post them here (fortran@) and we will tell you.

FX
diff mbox

Patch

From 744e824a58f5861c4376e32c9e3169f4e52e2e00 Mon Sep 17 00:00:00 2001
From: marxin <mliska@suse.cz>
Date: Fri, 8 Jul 2016 10:16:29 +0200
Subject: [PATCH] Enhance warning message for DO loops with |step| != 1.

---
 gcc/fortran/trans-stmt.c                        | 44 ++++++++++++++++++
 gcc/testsuite/gfortran.dg/do_undefined_warn.f90 | 61 +++++++++++++++++++++++++
 2 files changed, 105 insertions(+)
 create mode 100644 gcc/testsuite/gfortran.dg/do_undefined_warn.f90

diff --git a/gcc/fortran/trans-stmt.c b/gcc/fortran/trans-stmt.c
index 6e4e2a7..1c1cd18 100644
--- a/gcc/fortran/trans-stmt.c
+++ b/gcc/fortran/trans-stmt.c
@@ -2014,6 +2014,7 @@  gfc_trans_do (gfc_code * code, tree exit_cond)
   gfc_start_block (&block);
 
   loc = code->ext.iterator->start->where.lb->location;
+  locus *location = &code->ext.iterator->start->where;
 
   /* Evaluate all the expressions in the iterator.  */
   gfc_init_se (&se, NULL);
@@ -2097,6 +2098,49 @@  gfc_trans_do (gfc_code * code, tree exit_cond)
     {
       tree pos, neg, tou, fromu, stepu, tmp2;
 
+      if (TREE_CODE (from) == INTEGER_CST
+	  && TREE_CODE (to) == INTEGER_CST
+	  && TREE_CODE (step) == INTEGER_CST)
+	{
+	  wide_int t = to;
+	  wide_int f = from;
+	  wide_int s = step;
+	  bool r1_overflow, r2_overflow, r3_overflow;
+	  bool cmp1, cmp2, cmp3;
+	  bool has_warning = false;
+
+	  wide_int r1 = wi::sub (t, f, SIGNED, &r1_overflow);
+	  cmp1 = wi::les_p (f, t);
+	  wi::add (f, s, SIGNED, &r2_overflow);
+	  cmp2 = !wi::neg_p (f);
+	  wi::add (r1, s, SIGNED, &r3_overflow);
+	  cmp3 = wi::les_p (s, r1);
+
+	  if (r1_overflow)
+	    {
+	      gfc_warning (OPT_Wundefined_do_loop,
+			   "DO loop at %L is undefined as the expression "
+			   "TO - FROM %s",
+			   location, cmp1 ? "overflows" : "underflows");
+	      has_warning = true;
+	    }
+
+	  if (r2_overflow && !has_warning)
+	    {
+	      gfc_warning (OPT_Wundefined_do_loop,
+			   "DO loop at %L is undefined as the expression "
+			   "FROM + STEP %s", location,
+			   cmp2 ? "overflows" : "underflows");
+	      has_warning = true;
+	    }
+
+	  if (r3_overflow && !has_warning)
+	    gfc_warning (OPT_Wundefined_do_loop,
+			 "DO loop at %L is undefined as the expression "
+			 "TO - FROM + STEP %s", location,
+			 cmp3 ? "overflows" : "underflows");
+	}
+
       /* The distance from FROM to TO cannot always be represented in a signed
          type, thus use unsigned arithmetic, also to avoid any undefined
 	 overflow issues.  */
diff --git a/gcc/testsuite/gfortran.dg/do_undefined_warn.f90 b/gcc/testsuite/gfortran.dg/do_undefined_warn.f90
new file mode 100644
index 0000000..3c20e00
--- /dev/null
+++ b/gcc/testsuite/gfortran.dg/do_undefined_warn.f90
@@ -0,0 +1,61 @@ 
+! { dg-options "-Wundefined-do-loop" }
+! Program to check corner cases for DO statements.
+
+function test2(array, s, block)
+integer(1) :: i, block(9), array(2)
+integer(2) :: j
+integer (8) :: s
+s = 1
+
+do i = -HUGE(i)-1, HUGE(i), 2 ! { dg-warning "is undefined as the expression TO - FROM overflows" }
+  s = s + 1
+end do
+
+do i = HUGE(i) - 10, HUGE(i), 12 ! { dg-warning "is undefined as the expression FROM \\+ STEP overflows" }
+  s = s + 1
+end do
+
+do i = 10, HUGE(i) - 10, 100 ! { dg-warning "is undefined as the expression TO - FROM \\+ STEP overflows" }
+ s = s + 1
+end do
+
+do i = 2, -HUGE(i)-1, 2 ! { dg-warning "is undefined as the expression TO - FROM underflows" }
+  s = s + 1
+end do
+
+do i = -HUGE(i)+11, 0, -13 ! { dg-warning "is undefined as the expression FROM \\+ STEP underflows" }
+  s = s + 1
+end do
+
+do i = -5, -HUGE(i) + 10, -22 ! { dg-warning "is undefined as the expression TO - FROM \\+ STEP underflows" }
+ s = s + 1
+end do
+
+! wider type
+
+do j = -HUGE(i)-1, HUGE(i), 2
+  s = s + 1
+end do
+
+do j = HUGE(i) - 10, HUGE(i), 12
+  s = s + 1
+end do
+
+do j = 10, HUGE(i) - 10, 100
+ s = s + 1
+end do
+
+do j = 2, -HUGE(i)-1, 2
+  s = s + 1
+end do
+
+do j = -HUGE(i)+11, 0, -13
+  s = s + 1
+end do
+
+do j = -5, -HUGE(i) + 10, -22
+ s = s + 1
+end do
+
+
+end function test2
-- 
2.8.4