[Fortran] Improvements to dependency analysis

[Roger Sayle <roger at eyesopen dot com>]

The following patch makes some improvements to the gfortran front-end's
dependency analysis.  Currently gfortran is transitioning from dependency
analysis based in the scalarizer (checking gfc_ss*) to analysis based
on expressions (checking gfc_expr*) [see the comment above
trans-array.c:gfc_conv_resolve_dependencies].  The old API uses
gfc_conv_resolve_dependencies (which calls gfc_dep_resolver), whilst
the new API uses dependency.c:gfc_check_dependency.

The significant bit of the patch below is to hook the intelligence
of the array reference dependency checking in gfc_dep_resolver into
the preferred gfc_check_dependency API.

As an example of the improvement this provides, gfc_check_dependency
could previously determine that array refs "a" and "a" were equal
and therefore hadn't a dependency, but couldn't tell that "a(:)"
and "a(:)" or that "a(1:3)" and "a(1:3)" were equal.  A convenient
model system for gfc_check_dependency is the F90 WHERE statement
generation, where its easy to construct tests that check whether a
dependency was identified by scanning the output for the allocation
of a temporary array.

Whilst double checking this hook-up, I discovered a potential problem
in gfc_check_element_vs_element.  Where we didn't check for a -2
return value from gfc_dep_compare_expr, meaning that we couldn't
determine the equality or ordering of the operands at compile-time
(for example, with two distinct variables).  In this eventually, its
unsafe to assume that array refs have no dependency.  By assuming
that these variables are not equal, we current skip checking the later
dimensions, which may have a conflict.

Consider,

	a(i,1:3) = a(j,0:2)

This has a dependency, because if i == j, we need to confirm that
the second dimensions don't overlap.  This is fixed below by
cleaning up gfc_check_element_vs_element.  I also changed the code
to assume both arguments are ARRAY_REFs to consistently match the
implementations of both gfc_check_element_vs_section and
gfc_check_section_vs_section.

Finally, because I'm paranoid, I added an extra test or two to
gfc_dep_resolver to ensure that both reference chains have the
same depth, and assume a dependency if they don't match up.


The following patch has been tested on x86_64-unknown-linux-gnu
with a full "make bootstrap", including fortran, and tested with
a top-level "make -k check" with no new failures in the fortran
or gomp testsuites.

Ok for mainline?  I've a follow-up patch that improves this part
of gfortran's dependency checking even further, inspired by some
of the source code in the polyhedron benchmarks.



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

	* dependency.c (gfc_check_dependency): Call gfc_dep_resolver to
	check whether two array references have a dependency.
	(gfc_check_element_vs_element): Assume lref and rref must be
	REF_ARRAYs.  If gfc_dep_compare_expr returns -2, assume these
	references could potentially overlap.
	(gfc_dep_resolver): Whitespace and comment tweaks.  Assume a
	dependency if the references have different depths.  Rewrite
	final term to clarrify we only have a dependency for overlaps.

	* gfortran.dg/dependency_4.f90: New test case.
	* gfortran.dg/dependency_5.f90: New test case.
	* gfortran.dg/dependency_6.f90: New test case.
	* gfortran.dg/dependency_7.f90: New test case.
	* gfortran.dg/dependency_8.f90: New test case.


Index: dependency.c
===================================================================
*** dependency.c	(revision 111630)
--- dependency.c	(working copy)
*************** gfc_check_dependency (gfc_expr * expr1,
*** 460,475 ****
        if (identical)
  	return 1;

!       /* Identical ranges return 0, overlapping ranges return 1.  */
!
        /* Return zero if we refer to the same full arrays.  */
!       if (expr1->ref->type == REF_ARRAY
! 	  && expr2->ref->type == REF_ARRAY
! 	  && expr1->ref->u.ar.type == AR_FULL
! 	  && expr2->ref->u.ar.type == AR_FULL
! 	  && !expr1->ref->next
! 	  && !expr2->ref->next)
! 	return 0;

        return 1;

--- 460,470 ----
        if (identical)
  	return 1;

!       /* Identical and disjoint ranges return 0,
! 	 overlapping ranges return 1.  */
        /* Return zero if we refer to the same full arrays.  */
!       if (expr1->ref->type == REF_ARRAY && expr2->ref->type == REF_ARRAY)
! 	return gfc_dep_resolver (expr1->ref, expr2->ref);

        return 1;

*************** gfc_check_element_vs_element (gfc_ref *
*** 735,764 ****
    gfc_array_ref r_ar;
    gfc_expr *l_start;
    gfc_expr *r_start;
!   gfc_dependency nIsDep;
!
!   if (lref->type == REF_ARRAY && rref->type == REF_ARRAY)
!     {
!       l_ar = lref->u.ar;
!       r_ar = rref->u.ar;
!       l_start = l_ar.start[n] ;
!       r_start = r_ar.start[n] ;
!       if (gfc_dep_compare_expr (r_start, l_start) == 0)
! 	nIsDep = GFC_DEP_EQUAL;
!       else
! 	nIsDep = GFC_DEP_NODEP;
!   }
!   else
!     nIsDep = GFC_DEP_NODEP;

!   return nIsDep;
  }


  /* Finds if two array references are overlapping or not.
     Return value
     	1 : array references are overlapping.
!    	0 : array references are not overlapping.  */

  int
  gfc_dep_resolver (gfc_ref * lref, gfc_ref * rref)
--- 730,754 ----
    gfc_array_ref r_ar;
    gfc_expr *l_start;
    gfc_expr *r_start;
!   int i;

!   l_ar = lref->u.ar;
!   r_ar = rref->u.ar;
!   l_start = l_ar.start[n] ;
!   r_start = r_ar.start[n] ;
!   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;
  }


  /* Finds if two array references are overlapping or not.
     Return value
     	1 : array references are overlapping.
!    	0 : array references are identical or not overlapping.  */

  int
  gfc_dep_resolver (gfc_ref * lref, gfc_ref * rref)
*************** gfc_dep_resolver (gfc_ref * lref, gfc_re
*** 792,798 ****
  	  return 0;

  	case REF_ARRAY:
-
  	  for (n=0; n < lref->u.ar.dimen; n++)
  	    {
  	      /* Assume dependency when either of array reference is vector
--- 782,787 ----
*************** gfc_dep_resolver (gfc_ref * lref, gfc_re
*** 844,852 ****
    /* If we haven't seen any array refs then something went wrong.  */
    gcc_assert (fin_dep != GFC_DEP_ERROR);

!   if (fin_dep < GFC_DEP_OVERLAP)
!     return 0;
!   else
      return 1;
  }

--- 833,842 ----
    /* If we haven't seen any array refs then something went wrong.  */
    gcc_assert (fin_dep != GFC_DEP_ERROR);

!   /* Assume the worst if we nest to different depths.  */
!   if (!lref || !rref)
      return 1;
+
+   return fin_dep == GFC_DEP_OVERLAP;
  }



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

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


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

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



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

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


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

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


! { 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,1:3) .ne. 0)
    a(j,2:4) = 1
  endwhere
end subroutine
! { dg-final { scan-tree-dump-times "malloc" 1 "original" } }
! { dg-final { cleanup-tree-dump "original" } }


Roger
--