[Fortran] Another array reference dependency improvement

[Roger Sayle <roger at eyesopen dot com>]

The patch below is a follow-up to (and applies on top of) yesterday's
dependency improvement patch.  I decided to heed the wise advice
that "a month's hard work in the lab can save a morning's trip to
the library", and do some more background reading on Fortran95
array dependence analysis.

One interesting paper that I came across was:

http://citeseer.ist.psu.edu/roth01evaluation.html
"Evaluation of Array Syntax Dependence Analysis"
Gerald Roth, Gonzaga University,
Proceedings of the International Conference on Parallel and
Distributed Processing Techniques and Applications (PDPTA 2001),
Las Vegas, Nevada, June 2001.

One of the clever ideas in that paper is that because scalarization
only cares about detection of "loop-caried true dependencies", all
scalar subscripts can be ignored.  Implementing this in gfortran's
infrastructure turns out to be a one line change, but a subtle one.

In gfc_check_element_vs_element we could return GFC_DEP_EQUAL for
two unordered scalar subscripts (elements).  Originally, when
examining subscripts if we discovered that X and Y were unordered
in a(X,...) vs. a(Y,...) we'd return GFC_DEP_NODEP (a bug) which was
treated by the caller like X<Y or X>Y, and incorrectly returned
"no dependency" without examining the "...".  This was fixed
yesterday by taking the pessimistic assumption that unordered X
and Y, should return GFC_DEP_OVERLAP.  This causes the caller to
inspect the remaining dimensions such that if it finds a later
NODEP, there's no dependency as in a(X,0,:) = a(Y,1,:) where
the 0 != 1 guarantees independence.  The tweak below is to
optimistically/safely return GFC_DEP_EQUAL, which again forces
the examination of "...", but allows us to notice independence
at the end.  i.e. elements that return GFC_DEP_EQUAL are effectively
ignored in the dependency analysis.

Fortunately, there's a whole paper on this, if the above explanation
wasn't too confusing.  dependency.c actually does slightly better
(or will shortly be slightly better) than the analysis described in
that paper, which was used in SUN's and Cray's F90 compilers.

The following patch has been tested on x86_64-unknown-linux-gnu,
on top of yesterday's patch, with a full "make bootstrap", including
fortran, and regression tested with a top-level "make -k check"
with no new failures.  I'm predicting this will help polyhedron
timings, but I haven't run the benchmarks.  Note, this still isn't
the follow-up that I was originally planning.

Ok for mainline?



2006-03-03  Roger Sayle  <roger@eyesopen.com>

	* dependency.c (gfc_check_element_vs_element): Consider two
	unordered scalar subscripts as (potentially) equal.

	* gfortran.dg/dependency_9.f90: New test case.



*** patchd2/gcc/fortran/dependency.c	2006-03-02 12:21:13.000000000 -0700
--- patchd3/gcc/fortran/dependency.c	2006-03-02 17:28:03.000000000 -0700
*************** gfc_check_element_vs_element (gfc_ref *
*** 739,746 ****
    i = gfc_dep_compare_expr (r_start, l_start);
    if (i == 0)
      return GFC_DEP_EQUAL;
    if (i == -2)
!     return GFC_DEP_OVERLAP;
    return GFC_DEP_NODEP;
  }

--- 739,752 ----
    i = gfc_dep_compare_expr (r_start, l_start);
    if (i == 0)
      return GFC_DEP_EQUAL;
+   /* Treat two scalar variables as potentially equal.  This allows
+      us to prove that a(i,:) and a(j,:) have no dependency.  See
+      Gerald Roth, "Evaluation of Array Syntax Dependence Analysis",
+      Proceedings of the International Conference on Parallel and
+      Distributed Processing Techniques and Applications (PDPTA2001),
+      Las Vegas, Nevada, June 2001.  This used to be GFC_DEP_OVERLAP.  */
    if (i == -2)
!     return GFC_DEP_EQUAL;
    return GFC_DEP_NODEP;
  }



! { dg-do compile }
! { dg-options "-O2 -fdump-tree-original" }
subroutine foo(a,i,j)
  integer, dimension (4,4) :: a
  integer :: i
  integer :: j

  where (a(i,:) .ne. 0)
    a(j,:) = 1
  endwhere
end subroutine
! { dg-final { scan-tree-dump-times "malloc" 0 "original" } }
! { dg-final { cleanup-tree-dump "original" } }


Roger
--