patch [RFC] Simple loop runs out of stack at -O1

[Fariborz Jahanian]

Hi,
There gotta be a PR on this because it is so easy to reproduce. 
Following test case runs out of stack space when
gcc tries to compute factorial (1599999). I have a patch which does two 
simple things. 1) it rewrites tree_fold_factorial
function into its non-recursive version, and 2) it sets a limit before 
deciding to call chrec_evaluate. This limit is arbitrary in this
patch. Author of the algorithm may want to decide when to stop 
evaluating feasibility of this optimization. Note that even with this 
limit,
the computed factorial overflows. So, even a much smaller limit is 
needed if this value is significant.

- fariborz ([EMAIL PROTECTED])
/* bad.c */
static unsigned int *buffer;
void FUNC (void)
{
 unsigned int *base;
 int i, j;
 for (i = 0; i < 4; i++)
  for (j = 0; j < 1600000; j++)
   *base++ = buffer[j];
}
% mygccm5 -c -O1 bad.c
Out of stack space.
Try running 'limit stacksize unlimited' in the shell to raise its limit.

Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.c,v
retrieving revision 1.1.4.9
diff -c -p -r1.1.4.9 tree-chrec.c
*** tree-chrec.c        11 Nov 2004 01:12:45 -0000      1.1.4.9
--- tree-chrec.c        25 Feb 2005 20:35:49 -0000
*************** chrec_fold_multiply (tree type, 
*** 388,400 ****
  static tree 
  tree_fold_factorial (tree f)
  {
    if (tree_int_cst_sgn (f) <= 0)
      return integer_one_node;
!   else
!     return fold 
!       (build (MULT_EXPR, integer_type_node, f, 
!             tree_fold_factorial (fold (build (MINUS_EXPR, integer_type_node, 
!                                               f, integer_one_node)))));
  }
  
  /* The binomial coefficient.  */
--- 388,411 ----
  static tree 
  tree_fold_factorial (tree f)
  {
+   int i, limit;
+   tree fact;
+ 
    if (tree_int_cst_sgn (f) <= 0)
      return integer_one_node;
! 
!   limit = tree_low_cst (f, 1);
!   fact = f;
!   for (i = limit; i > 1; i--)
!      {
!        tree itree = build_int_cst_type (integer_type_node, i);
!        fact = fold 
!               (build (MULT_EXPR, integer_type_node, fact, 
!                       fold (
!                         build (MINUS_EXPR, integer_type_node, 
!                                itree, integer_one_node))));
!      }
!   return fact;
  }
  
  /* The binomial coefficient.  */
*************** chrec_apply (unsigned var,
*** 491,497 ****
      res = chrec;
    
    else if (TREE_CODE (x) == INTEGER_CST
!          && tree_int_cst_sgn (x) == 1)
      /* testsuite/.../ssa-chrec-38.c.  */
      res = chrec_evaluate (var, chrec, x, integer_zero_node);
  
--- 502,509 ----
      res = chrec;
    
    else if (TREE_CODE (x) == INTEGER_CST
!          && tree_int_cst_sgn (x) == 1
!          && tree_low_cst (x, 1) <= 1024)
      /* testsuite/.../ssa-chrec-38.c.  */
      res = chrec_evaluate (var, chrec, x, integer_zero_node);