[patch, fortran] PR32489 and PR20923 Endless loop when compiling, slow for large array constrcutors

[Jerry DeLisle <jvdelisle at verizon dot net>]

Hi folks,

I have combined the original patch for pr20923, previously approved. with the 
exploratory patch I posted earlier.  This patch speeds up certain compilations 
by doing two things.

If an array constructor is found to be already a constant, it can be traversed 
directly without calling gfc_is_constant_expr.  This provides significant speed 
up for the test cases in PR20923.  The speedup is due to avoiding the more 
complicated logic in gfc_is_constant_expr which must handle all expression 
types.  For large arrays. the time can add up fast.

The second improvement comes from observing that if an array constructor is not 
involved in a parameter, it need not be fully expanded.  See PR32489 for the 
fft257.f90 test case.  The new function, gfc_is_expandable_expr traverses the 
constructor and if it finds a variable with flavor FL_PARAMETER, it returns 
true, indicating to proceed with full expansion.

Parameters must be expanded fully because they need to be used by the gfortran 
front-end to build other expressions.  Expressions that are not related to 
parameters do not need to be fully expanded (unrolled).  The troublesome 
expression in fft257.f90 is currently expanded fine by the gfortran front-end, 
but the resulting complexity bogs down the middle-end completely.  With this 
patch, the complex expression is simply translated into a few loops, allowing 
the middle-end to optimize where possible.

I have provided some test results below.

Regression tested on x86-64.  OK for trunk?

Regards,

Jerry

2009-12-13 Jerry DeLisle  <jvdelisle@gcc.gnu.org>

	PR fortran/20923
	PR fortran/32489
	* trans-array.c (gfc_conv_array_initializer): Change call to
	gfc_error_now to call to gfc_fatal_error.
	* array.c (count_elements): Whitespace. (extract_element): Whitespace.
	(is_constant_element): Changed name from constant_element.
	(gfc_constant_ac): Only use expand_construuctor for expression
	types of EXPR_ARRAY.  If expression type is EXPR_CONSTANT, no need to
	call gfc_is_constant_expr.
	* expr.c (gfc_reduce_init_expr): Adjust conditionals and delete error
	message.
	* resolve.c (gfc_is_expandable_expr): New function that determiners if
	array expressions should have their constructors expanded.
	(gfc_resolve_expr): Use new function to determine whether or not to call
	gfc_expand_constructor.

Some test results:

1) fft257.f90 failed to complete compilation on my system after 448 minutes. 
Reducing the size of the problem from N=257 to N=75 and commenting out the call 
to fft257 to avoid compile errors from mismatched array size, we get the 
following compile times.

gfortran unpatched:

real	0m20.792s
user	0m20.226s
sys	0m0.544s

gfortran patched:

real	0m1.713s
user	0m1.626s
sys	0m0.076s

2) With the original test case in pr20923.

gfortran unpatched:

real	0m8.239s
user	0m8.202s
sys	0m0.033s

gfortran patched:

real	0m2.128s
user	0m2.106s
sys	0m0.022s

3) Parameter test case from pr34554.
   (Difference is not significant)

gfortran unpatched:

real	2m6.507s
user	2m6.461s
sys	0m0.017s

gfortran patched:

real	2m5.835s
user	2m5.784s
sys	0m0.022s



Index: trans-array.c
===================================================================
--- trans-array.c	(revision 155200)
+++ trans-array.c	(working copy)
@@ -4109,11 +4109,11 @@ gfc_conv_array_initializer (tree type, gfc_expr *
             {
               /* Problems occur when we get something like
                  integer :: a(lots) = (/(i, i=1, lots)/)  */
-              gfc_error_now ("The number of elements in the array constructor "
-			     "at %L requires an increase of the allowed %d "
-			     "upper limit.   See -fmax-array-constructor "
-			     "option", &expr->where,
-			     gfc_option.flag_max_array_constructor);
+              gfc_fatal_error ("The number of elements in the array constructor "
+			       "at %L requires an increase of the allowed %d "
+			       "upper limit.   See -fmax-array-constructor "
+			       "option", &expr->where,
+			       gfc_option.flag_max_array_constructor);
 	      return NULL_TREE;
 	    }
           if (mpz_cmp_si (c->n.offset, 0) != 0)
Index: array.c
===================================================================
--- array.c	(revision 155200)
+++ array.c	(working copy)
@@ -1237,7 +1237,6 @@ count_elements (gfc_expr *e)
 static gfc_try
 extract_element (gfc_expr *e)
 {
-
   if (e->rank != 0)
     {				/* Something unextractable */
       gfc_free_expr (e);
@@ -1250,6 +1249,7 @@ extract_element (gfc_expr *e)
     gfc_free_expr (e);
 
   current_expand.extract_count++;
+  
   return SUCCESS;
 }
 
@@ -1495,7 +1495,7 @@ done:
    FAILURE if not so.  */
 
 static gfc_try
-constant_element (gfc_expr *e)
+is_constant_element (gfc_expr *e)
 {
   int rv;
 
@@ -1517,14 +1517,38 @@ gfc_constant_ac (gfc_expr *e)
 {
   expand_info expand_save;
   gfc_try rc;
+  gfc_constructor * con;
+  
+  rc = SUCCESS;
 
-  iter_stack = NULL;
-  expand_save = current_expand;
-  current_expand.expand_work_function = constant_element;
+  if (e->value.constructor
+      && e->value.constructor->expr->expr_type == EXPR_ARRAY 
+      && !e->value.constructor->iterator)
+    {
+      /* Expand the constructor.  */
+      iter_stack = NULL;
+      expand_save = current_expand;
+      current_expand.expand_work_function = is_constant_element;
 
-  rc = expand_constructor (e->value.constructor);
+      rc = expand_constructor (e->value.constructor);
 
-  current_expand = expand_save;
+      current_expand = expand_save;
+    }
+  else
+    {
+      /* No need to expand this further.  */
+      for (con = e->value.constructor; con; con = con->next)
+	{
+	  if (con->expr->expr_type == EXPR_CONSTANT)
+	    continue;
+	  else
+	    {
+	      if (!gfc_is_constant_expr (con->expr))
+		rc = FAILURE;
+	    }
+	}
+    }
+
   if (rc == FAILURE)
     return 0;
 
Index: expr.c
===================================================================
--- expr.c	(revision 155200)
+++ expr.c	(working copy)
@@ -2461,18 +2461,12 @@ gfc_reduce_init_expr (gfc_expr *expr)
   if (t == FAILURE)
     return FAILURE;
 
-  if (expr->expr_type == EXPR_ARRAY
-      && (gfc_check_constructor_type (expr) == FAILURE
-      || gfc_expand_constructor (expr) == FAILURE))
-    return FAILURE;
-
-  /* Not all inquiry functions are simplified to constant expressions
-     so it is necessary to call check_inquiry again.  */ 
-  if (!gfc_is_constant_expr (expr) && check_inquiry (expr, 1) != MATCH_YES
-      && !gfc_in_match_data ())
+  if (expr->expr_type == EXPR_ARRAY)
     {
-      gfc_error ("Initialization expression didn't reduce %C");
-      return FAILURE;
+      if (gfc_check_constructor_type (expr) == FAILURE)
+	return FAILURE;
+      if (gfc_expand_constructor (expr) == FAILURE)
+	return FAILURE;
     }
 
   return SUCCESS;
Index: resolve.c
===================================================================
--- resolve.c	(revision 155200)
+++ resolve.c	(working copy)
@@ -5493,6 +5493,32 @@ resolve_expr_ppc (gfc_expr* e)
 }
 
 
+static bool
+gfc_is_expandable_expr (gfc_expr *e)
+{
+  gfc_constructor *con;
+
+  if (e->expr_type == EXPR_ARRAY)
+    {
+      /* Traverse the constructor looking for variables that are flavor
+	 parameter.  Parameters must be expanded since they are fully used at
+	 compile time.  */
+      for (con = e->value.constructor; con; con = con->next)
+	{
+	  if (con->expr->expr_type == EXPR_VARIABLE
+	  && con->expr->symtree
+	  && (con->expr->symtree->n.sym->attr.flavor == FL_PARAMETER
+	      || con->expr->symtree->n.sym->attr.flavor == FL_VARIABLE))
+	    return true;
+	  if (con->expr->expr_type == EXPR_ARRAY
+	    && gfc_is_expandable_expr (con->expr))
+	    return true;
+	}
+    }
+
+  return false;
+}
+
 /* Resolve an expression.  That is, make sure that types of operands agree
    with their operators, intrinsic operators are converted to function calls
    for overloaded types and unresolved function references are resolved.  */
@@ -5559,14 +5585,20 @@ gfc_resolve_expr (gfc_expr *e)
       if (t == SUCCESS)
 	{
 	  expression_rank (e);
-	  gfc_expand_constructor (e);
+	  if (gfc_is_constant_expr (e) || gfc_is_expandable_expr (e))
+	    gfc_expand_constructor (e);
 	}
 
       /* This provides the opportunity for the length of constructors with
 	 character valued function elements to propagate the string length
 	 to the expression.  */
       if (t == SUCCESS && e->ts.type == BT_CHARACTER)
-	t = gfc_resolve_character_array_constructor (e);
+        {
+	  /* For efficiency, we call gfc_expand_constructor for BT_CHARACTER
+	     here rather then add a duplicate test for it above.  */ 
+	  gfc_expand_constructor (e);
+	  t = gfc_resolve_character_array_constructor (e);
+	}
 
       break;