[Fortran] Scalar index dependency fix for dependency_9.f90 (fwd)

[Roger Sayle <roger at eyesopen dot com>]

The following patch is my second attempt at implementing the gfortran
optimization that scalar indices are always independent, allowing the
original dependency_9.f90 test case to pass.  My first attempt ran
into problems with forall_4.f90 and forall_7.f90, due to poor
interactions with variables that are used as FORALL index names.
These variables behave differently from regular variables/expressions
in fortran9x array expressions, as their values may change during
the scalarized traversal of an array expression.

To identify these troublesome cases, the code below introduces a new
"forall_index" bit-field that is associated with each gfc_symbol.
There are numerous spare bits, so there is no increase in the size
of this structure.  This bit is set whilst parsing FORALL statements
and FORALL constructs, to mark the iteration variable's gfc_symbol.
This flag is then used in dependency.c's check_element_vs_element
to enable the Roth2001 optimization described previously.
http://gcc.gnu.org/ml/gcc-patches/2006-03/msg00209.html


This patch introduces a new function "contains_forall_index_p" that
traverses an expression to see whether any subexpression or operand
is a FORALL index.  This new function is based heavily on the
function expr.c's gfc_expr_set_symbols_referenced that traverses
an expression to identify all the symbols it contains.  The new
function behaves similarly, but inspects the forall_index bit at
each EXPR_VARIABLE node.


The following patch has been tested on x86_64-unknown-linux-gnu with
a full "make bootstrap", all languages including fortran, and regression
tested with a top-level "make -k check" with no new failures.  The
previous reversion of my original patch resulted in a performance
regression on polyhedron, which I hope is resolved (and maybe
improved upon) with this patch, but I've not yet tested that.  It's
possible the affected array references did mention FORALL indices.

Ok for mainline?  Sorry again for the earlier inconvenience.



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

	* gfortran.h (gfc_symbol): Add a new "forall_index" bit field.
	* match.c (match_forall_iterator): Set forall_index field on
	the iteration variable's symbol.
	* dependency.c (contains_forall_index_p): New function to
	traverse a gfc_expr to check whether it contains a variable
	with forall_index set in it's symbol.
	(gfc_check_element_vs_element): Return GFC_DEP_EQUAL for scalar
	constant expressions that don't variables used as FORALL indices.

	* gfortran.dg/dependency_9.f90: New (resurected) test case.


Index: gfortran.h
===================================================================
*** gfortran.h	(revision 111839)
--- gfortran.h	(working copy)
*************** typedef struct gfc_symbol
*** 852,857 ****
--- 852,859 ----
    /* Nonzero if all equivalences associated with this symbol have been
       processed.  */
    unsigned equiv_built:1;
+   /* Set if this variable is used as an index name in a FORALL.  */
+   unsigned forall_index:1;
    int refs;
    struct gfc_namespace *ns;	/* namespace containing this symbol */

Index: match.c
===================================================================
*** match.c	(revision 111839)
--- match.c	(working copy)
*************** match_forall_iterator (gfc_forall_iterat
*** 3370,3375 ****
--- 3370,3378 ----
  	goto cleanup;
      }

+   /* Mark the iteration variable's symbol as used as a FORALL index.  */
+   iter->var->symtree->n.sym->forall_index = true;
+
    *result = iter;
    return MATCH_YES;

Index: dependency.c
===================================================================
*** dependency.c	(revision 111839)
--- dependency.c	(working copy)
*************** gfc_check_element_vs_section( gfc_ref *
*** 721,726 ****
--- 721,804 ----
  }


+ /* Traverse expr, checking all EXPR_VARIABLE symbols for their
+    forall_index attribute.  Return true if any variable may be
+    being used as a FORALL index.  Its safe to pessimistically
+    return true, and assume a dependency.  */
+
+ static bool
+ contains_forall_index_p (gfc_expr * expr)
+ {
+   gfc_actual_arglist *arg;
+   gfc_constructor *c;
+   gfc_ref *ref;
+   int i;
+
+   if (!expr)
+     return false;
+
+   switch (expr->expr_type)
+     {
+     case EXPR_VARIABLE:
+       if (expr->symtree->n.sym->forall_index)
+ 	return true;
+       break;
+
+     case EXPR_OP:
+       if (contains_forall_index_p (expr->value.op.op1)
+ 	  || contains_forall_index_p (expr->value.op.op2))
+ 	return true;
+       break;
+
+     case EXPR_FUNCTION:
+       for (arg = expr->value.function.actual; arg; arg = arg->next)
+ 	if (contains_forall_index_p (arg->expr))
+ 	  return true;
+       break;
+
+     case EXPR_CONSTANT:
+     case EXPR_NULL:
+     case EXPR_SUBSTRING:
+       break;
+
+     case EXPR_STRUCTURE:
+     case EXPR_ARRAY:
+       for (c = expr->value.constructor; c; c = c->next)
+ 	if (contains_forall_index_p (c->expr))
+ 	  return true;
+       break;
+
+     default:
+       gcc_unreachable ();
+     }
+
+   for (ref = expr->ref; ref; ref = ref->next)
+     switch (ref->type)
+       {
+       case REF_ARRAY:
+ 	for (i = 0; i < ref->u.ar.dimen; i++)
+ 	  if (contains_forall_index_p (ref->u.ar.start[i])
+ 	      || contains_forall_index_p (ref->u.ar.end[i])
+ 	      || contains_forall_index_p (ref->u.ar.stride[i]))
+ 	    return true;
+ 	break;
+
+       case REF_COMPONENT:
+ 	break;
+
+       case REF_SUBSTRING:
+ 	if (contains_forall_index_p (ref->u.ss.start)
+ 	    || contains_forall_index_p (ref->u.ss.end))
+ 	  return true;
+ 	break;
+
+       default:
+ 	gcc_unreachable ();
+       }
+
+   return false;
+ }
+
  /* Determines overlapping for two single element array references.  */

  static gfc_dependency
*************** gfc_check_element_vs_element (gfc_ref *
*** 739,747 ****
    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;
  }


--- 817,839 ----
    i = gfc_dep_compare_expr (r_start, l_start);
    if (i == 0)
      return GFC_DEP_EQUAL;
!   if (i != -2)
!     return GFC_DEP_NODEP;
!
!   /* 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.  */
!   /* However, we need to be careful when either scalar expression
!      contains a FORALL index, as these can potentially change value
!      during the scalarization/traversal of this array reference.  */
!   if (contains_forall_index_p (r_start)
!       || contains_forall_index_p (l_start))
      return GFC_DEP_OVERLAP;
!
!   return GFC_DEP_EQUAL;
  }



! { 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
--