[Bug fortran/30404] New: Wrong FORALL result

[Bug fortran/30404] New: Wrong FORALL result

[dominiq at lps dot ens dot fr]

On OSX 10.3 PPC with gfortran version 4.3.0 20070105, the following code:

! tests FORALL statements with a mask
program forall_8
  real, dimension (5, 5, 5, 5) :: a, b, c, d

  a (:, :, :, :) = 4
  forall (i = 1:5)
    a (i, i, 6 - i, i) = 7
  end forall
  forall (i = 1:5)
    a (i, 6 - i, i, i) = 7
  end forall
  forall (i = 1:5)
    a (6 - i, i, i, i) = 7
  end forall
  forall (i = 1:5:2)
    a (1, 2, 3, i) = 0
  end forall

  b (:, :, :, :) = 4
  do i = 1, 5
    b(6 - i, i, i, i) = 7
    b(i, 6 - i, i, i) = 7
    b(i, i, 6 - i, i) = 7
  end do
  b(1, 2, 3, 1) = 0
  b(1, 2, 3, 3) = 0
  b(1, 2, 3, 5) = 0

  if (any (a /= b )) call abort ()

  forall (i = 1:5, j = 1:5, k = 1:5, ((a (i, j, k, i) .gt. 6) .or. (a (i, j, k,
j) .gt. 6)))
      forall (l = 1:5, a (1, 2, 3, l) .lt. 2)
        b (i, j, k, l) = i - j + k - l + 0.5
      end forall
  end forall

  forall (i = 1:5, j = 1:5, a (i, j, 1, 1) .lt. 8)
!  forall (i = 1:5, j = 1:5)
    forall (k = 1:5, ((a (i, j, k, i) .gt. 6) .or. (a (i, j, k, j) .gt. 6)))
      forall (l = 1:5, a (1, 2, 3, l) .lt. 2)
        a (i, j, k, l) = i - j + k - l + 0.5
      end forall
    end forall
  end forall

  print *, a(5, 1, 1, 1), b(5, 1, 1, 1)
  if (any (a /= b )) call abort ()

end

gives:

   7.000000       4.500000    
Abort

I get the same result on AMD64. If I replace

  forall (i = 1:5, j = 1:5, a (i, j, 1, 1) .lt. 8)

by

  forall (i = 1:5, j = 1:5)

I get a segmentation fault on OSX, but not on AMD64.


-- 
           Summary: Wrong FORALL result
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: fortran
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: dominiq at lps dot ens dot fr


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

[Bug fortran/30404] Wrong FORALL result

[pault at gcc dot gnu dot org]

------- Comment #1 from pault at gcc dot gnu dot org  2007-01-08 11:23 -------
There appears to be a double problem here; the segfault, which I can reproduce
by adding more statements in the forall block that sets a, and the incorrect
rendering of the mask logic, according to where the masking is applied.

The program below illustrates the problem more simply.

I have cc'd Roger Sayle.

Paul

  integer, dimension (3, 3) :: a, b, c
  logical, dimension (3,3) :: l1 = .FALSE.
  integer :: i, j

  a = 2
  a (1,1) = 1
  a (3,3) = 1
  a (2,1) = 3
  a (2,3) = 3

  b = a
  c = a

  forall (i = 1:3, a(i, 1) == 1)     ! mask true for i = 1
    forall (j = 1:3, a(2, j) == 3)   ! mask true for j = 1,3
      b (i, j) = 99                  ! set for (i = 1) && (j = 1,3)
      l1 (i, j) = .TRUE.
    end forall
  end forall

   forall (i = 1:3, a(i, 1) .lt. 1000)
    forall (j = 1:3, l1(i, j))       ! mask true for (i = 1) && (j = 1,3)
      c (i, j) = 99                  ! SHOULD be set for (i = 1) && (j = 1,3)
    end forall
  end forall

!  forall (i = 1:3) !                 this segfaults
   forall (i = 1:3, a(i, 1) .lt. 1000)
    forall (j = 1:3, &
 (a(i, 1) == 1 .and. a(2, j) == 3))  ! mask true for (i = 1) && (j = 1,3)
      a (i, j) = 99                  ! SHOULD be set for (i = 1) && (j = 1,3)
    end forall
  end forall

  print *, a                         ! a remains unchanged for gfortran
  print *, b                         ! b is changed correctly
  print *, c                         ! c(2,:) == 99 *sigh*

! Other compilers end up with a == b == c
end


-- 

pault at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |sayle at gcc dot gnu dot org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-01-08 11:23:23
               date|                            |


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

[Bug fortran/30404] Wrong FORALL result

[pault at gcc dot gnu dot org]

------- Comment #2 from pault at gcc dot gnu dot org  2007-01-08 12:23 -------
  logical :: l1(2,2) = reshape ((/.false.,.true.,.true.,.false./), (/2,2/))
  integer :: it(2,2) = reshape ((/1,2,3,4/), (/2,2/))
  forall (i = 1:2, i < 3)
    forall (j = 1:2, l1(i,j))
      it(i, j) = 0
    end forall
  end forall
!  print *, l1
!  print '(4i2)', it
end

gfortran gives:
 F T T F
 0 0 0 0

the correct result is, of course:
 F T T F
 1 0 0 4

The (annotated) code is:

MAIN__ ()
{
  int4 j;
  static int4 it[4] = {1, 2, 3, 4};
  int4 i;
  static logical4 l1[4] = {0, 1, 1, 0};

  _gfortran_set_std (70, 127, 0);
  {
    int4 mi.2;
    int4 count.3;
    logical1 temp.1[2];
    int4 i.0;

    mi.2 = 0;
    i.0 = 1;
    count.3 = 2;
    while (1)
      {
        if (count.3 <= 0) goto L.1;
        temp.1[mi.2] = i.0 <= 2;
        mi.2 = mi.2 + 1;
        i.0 = i.0 + 1;
        count.3 = count.3 - 1;
      }
    L.1:;
    {
      int4 mi.6;
      int4 count.9;
      int4 count.8;
      int4 count.7;
      logical1 temp.5[2];
      int4 j.4;

      mi.6 = 0;
      j.4 = 1;
      count.7 = 2;
      while (1)                 /* i.0 is now 3 */
        {
          if (count.7 <= 0) goto L.2;
          temp.5[mi.6] = (logical1) l1[j.4 * 2 + NON_LVALUE_EXPR <i.0> + -3];
          mi.6 = mi.6 + 1;
          j.4 = j.4 + 1;
          count.7 = count.7 - 1;
        }
      L.2:;                    /* temp.5 = {1, ?} */
      i.0 = 1;
      mi.2 = 0;
      count.9 = 2;
      while (1)
        {
          if (count.9 <= 0) goto L.4;
          if (temp.1[mi.2])
            {
              j.4 = 1;
              mi.6 = 0;
              count.8 = 2;
              while (1)
                {
                  if (count.8 <= 0) goto L.3;
                  if (temp.5[mi.6])       /* {1, ?} */
                    {
                      it[j.4 * 2 + NON_LVALUE_EXPR <i.0> + -3] = 0;
                    }
                  j.4 = j.4 + 1;
                  mi.6 = mi.6 + 1;
                  count.8 = count.8 - 1;
                }                         /* Since ? probably != 0 => it = 0 */
              L.3:;
            }
          i.0 = i.0 + 1;
          mi.2 = mi.2 + 1;
          count.9 = count.9 - 1;
        }
      L.4:;
    }
  }
}

>From which we see that nested masks, with dependencies on the outer indices,
are not being evaluated with anything other than out of range values for the
outer indices.  In fact the mask is either not being given the correct rank or
the nesting of each block should include evaluation of the mask within the
outer loops.  I have not thought through if the last is consistent with
dependency analysis.

Paul


-- 


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

[Bug fortran/30404] Wrong FORALL result

[roger at eyesopen dot com]

------- Comment #3 from roger at eyesopen dot com  2007-01-11 16:56 -------
Ok, I've now spent some time reading the code, I understand what's going wrong
and what needs to be done to fix it.  The problem resolves around the
"nest_flag" argument to gfc_trans_nested_forall_loop.  This argument only ever
has the value zero when called  from gfc_trans_forall_1 when calculating the
mask for a nested forall.  Unfortunately, this use is incorrect.  Conceptually
in a nested forall the mask needs to have one element for each
execution/iteration of the assignment statement.  So in Paul's reduced testcase
in comment #5, the inner mask (translated as needs temp.5) to help in an array
of size 4!  This is required because the body of the loop may potentially
affect either the inner or outer mask condition.

So there's good news and bad news.

The bad news is that in the general case, we can't determine how many times the
 loop body will be iterated at compile-time.  When the loop bounds are
constant, we can simply multiply together innersize * outersize.  But often,
the shape of the iteration may be irregular, such as triangular operations:

  forall(i=1:10,mask1[i])
    forall(j=1:i,mask2[i,j])
      foo(i,j)

or completely irregular such as

  forall(i=1:10,mask1[i])
    forall(j=1:bound[i],mask2[i,j])
      bar(i,j)

The good news is that the current expansion of forall loops can be restructured
to get the fortran9x semantics correct.  In the worst case, we need to generate
another nested set of loops to determine the mask size, at run-time, before
allocating and then populating the array.  One nice aspect of this is that the
inner mask can take into account how sparse the outermask is.  i.e. for bar()
above we can do better than sum(bound[1:10]).  The bad news is this form of
conservative implementation is likely to be less efficient than the current
incorrect (and poor) implementation.  The good news is that in follow-up
patches, we should be able to significantly optimize FORALL much like we now do
with WHERE and generate much more efficient code for the common case, with mask
elimination, loop fusion etc...  For Paul's example in comment #5, it should be
possible to implement this loop without any mask arrays, as a single
doubly-nested loop.  However, the most immediate goal is rewriting gfortran's
forall expansion to produce the correct result.

Hopefully, I'll have the first in a series of patches to rewrite the basics of
nested FORALL expansion soon.  Unfortunately, its taking slightly longer than
I anticipated, though I've now confirmed that this isn't a simple few-line fix,
but a more fundamental design issue in nested forall expansion.

Paul, Steve, Please let me know if you see an issue with the above analysis.
Hopefully, the three-loop strategy of (i) determine mask size, (ii) populate
mask and (iii) conditionally execute loop makes sense?


-- 

roger at eyesopen dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |roger at eyesopen dot com
                   |dot org                     |
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2007-01-08 11:23:23         |2007-01-11 16:56:25
               date|                            |


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

[Bug fortran/30404] Wrong FORALL result

[kargl at gcc dot gnu dot org]

------- Comment #4 from kargl at gcc dot gnu dot org  2007-01-11 17:25 -------
(In reply to comment #3)
> Paul, Steve, Please let me know if you see an issue with the above analysis.
> Hopefully, the three-loop strategy of (i) determine mask size, (ii) populate
> mask and (iii) conditionally execute loop makes sense?

Roger, I haven't looked too closely at the guts of the forall implementation,
but your analysis and 3-loop strategy to fixing the bug seems reasonable.  In
fact, most of the forall code may be the original code implemented by pbrook.

I particularly like the concept of "make it work and then worry about
optimizations".  One thing to keep in mind is that the forall statement is
a parallel assignment operation.  You may be able to take advantage of the
tree-vectorize work for the inner loop.


-- 

kargl at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |kargl at gcc dot gnu dot org


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

[Bug fortran/30404] Wrong FORALL result

[sayle at gcc dot gnu dot org]

------- Comment #5 from sayle at gcc dot gnu dot org  2007-01-16 18:15 -------
Subject: Bug 30404

Author: sayle
Date: Tue Jan 16 18:15:19 2007
New Revision: 120829

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=120829
Log:
2007-01-16  Roger Sayle  <roger@eyesopen.com>

        PR fortran/30404
        * trans-stmt.c (forall_info): Remove pmask field.
        (gfc_trans_forall_loop): Remove NVAR argument, instead assume that
        NVAR covers all the interation variables in the current forall_info.
        Add an extra OUTER parameter, which specified the loop header in
        which to place mask index initializations.
        (gfc_trans_nested_forall_loop): Remove NEST_FLAG argument.
        Change the semantics of MASK_FLAG to only control the mask in the
        innermost loop.
        (compute_overall_iter_number): Optimize the trivial case of a
        top-level loop having a constant number of iterations.  Update
        call to gfc_trans_nested_forall_loop.  Calculate the number of
        times the inner loop will be executed, not to size of the 
        iteration space.
        (allocate_temp_for_forall_nest_1): Reuse SIZE as BYTESIZE when
        sizeof(type) == 1.  Tidy up.
        (gfc_trans_assign_need_temp): Remove NEST_FLAG argument from calls
        to gfc_trans_nested_forall_loop.
        (gfc_trans_pointer_assign_need_temp): Likewise.
        (gfc_trans_forall_1): Remove unused BYTESIZE, TMPVAR, SIZEVAR and
        LENVAR local variables.  Split mask allocation into a separate
        hunk/pass from mask population.  Use allocate_temp_for_forall_nest
        to allocate the FORALL mask with the correct size.  Update calls
        to gfc_trans_nested_forall_loop.
        (gfc_evaluate_where_mask): Update call to
        gfc_trans_nested_forall_loop.
        (gfc_trans_where_2): Likewise.

        * gfortran.dg/forall_6.f90: New test case.
        * gfortran.dg/dependency_8.f90: Update test to find "temp" array.
        * gfortran.dg/dependency_13.f90: Likewise.


Added:
    trunk/gcc/testsuite/gfortran.dg/forall_6.f90
Modified:
    trunk/gcc/fortran/ChangeLog
    trunk/gcc/fortran/trans-stmt.c
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gfortran.dg/dependency_13.f90
    trunk/gcc/testsuite/gfortran.dg/dependency_8.f90


-- 


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

[Bug fortran/30404] Wrong FORALL result

[sayle at gcc dot gnu dot org]

------- Comment #6 from sayle at gcc dot gnu dot org  2007-01-29 03:27 -------
Subject: Bug 30404

Author: sayle
Date: Mon Jan 29 03:27:07 2007
New Revision: 121279

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=121279
Log:

        PR fortran/30404
        * trans-stmt.c (forall_info): Remove pmask field.
        (gfc_trans_forall_loop): Remove NVAR argument, instead assume that
        NVAR covers all the interation variables in the current forall_info.
        Add an extra OUTER parameter, which specified the loop header in
        which to place mask index initializations.
        (gfc_trans_nested_forall_loop): Remove NEST_FLAG argument.
        Change the semantics of MASK_FLAG to only control the mask in the
        innermost loop.
        (compute_overall_iter_number): Optimize the trivial case of a
        top-level loop having a constant number of iterations.  Update
        call to gfc_trans_nested_forall_loop.  Calculate the number of
        times the inner loop will be executed, not to size of the 
        iteration space.
        (allocate_temp_for_forall_nest_1): Reuse SIZE as BYTESIZE when
        sizeof(type) == 1.  Tidy up.
        (gfc_trans_assign_need_temp): Remove NEST_FLAG argument from calls
        to gfc_trans_nested_forall_loop.
        (gfc_trans_pointer_assign_need_temp): Likewise.
        (gfc_trans_forall_1): Remove unused BYTESIZE, TMPVAR, SIZEVAR and
        LENVAR local variables.  Split mask allocation into a separate
        hunk/pass from mask population.  Use allocate_temp_for_forall_nest
        to allocate the FORALL mask with the correct size.  Update calls
        to gfc_trans_nested_forall_loop.
        (gfc_evaluate_where_mask): Update call to
        gfc_trans_nested_forall_loop.
        (gfc_trans_where_2): Likewise.

        * gfortran.dg/forall_6.f90: New test case.
        * gfortran.dg/dependency_8.f90: Update test to find "temp" array.
        * gfortran.dg/dependency_13.f90: Likewise.


Added:
    branches/gcc-4_2-branch/gcc/testsuite/gfortran.dg/forall_6.f90
Modified:
    branches/gcc-4_2-branch/gcc/fortran/ChangeLog
    branches/gcc-4_2-branch/gcc/fortran/trans-stmt.c
    branches/gcc-4_2-branch/gcc/testsuite/ChangeLog
    branches/gcc-4_2-branch/gcc/testsuite/gfortran.dg/dependency_13.f90
    branches/gcc-4_2-branch/gcc/testsuite/gfortran.dg/dependency_8.f90


-- 


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

[Bug fortran/30404] [4.1 only] Wrong FORALL result

[fxcoudert at gcc dot gnu dot org]

------- Comment #7 from fxcoudert at gcc dot gnu dot org  2007-02-10 16:23 -------
Fixed, don't you think?


-- 

fxcoudert at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
           Keywords|                            |patch
         Resolution|                            |FIXED
            Summary|Wrong FORALL result         |[4.1 only] Wrong FORALL
                   |                            |result
   Target Milestone|---                         |4.2.0


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