PR/20742

	* Makefile.in (tree-chrec.o): Depend on params.h.
	* params.def (PARAM_SCEV_MAX_EXPR_SIZE): New parameter with
	default value 20.
	* tree-chrec.c: Depend on params.h.  Replace build with buildN,
	and fold build with fold_buildN.
	(chrec_fold_plus_1): Fail with a chrec_don_know when the size of
	the expression exceeds PARAM_SCEV_MAX_EXPR_SIZE.
	(tree_contains_chrecs): Compute an estimation of the size of the
	given expression.
	* tree-chrec.h (tree_contains_chrecs): Modify its declaration.
	(tree_does_not_contain_chrecs): Update the use of tree_contains_chrecs.
	* tree-scalar-evolution.c (simple_iv): Ditto.
	* doc/invoke.texi (scev-max-expr-size): Documented.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@98497 138bc75d-0d04-0410-961f-82ee72b054a4

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index c77cef1..9a640af 100644 (file)
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,20 @@
+2005-04-21  Sebastian Pop  <pop@cri.ensmp.fr>
+
+       PR/20742
+       * Makefile.in (tree-chrec.o): Depend on params.h.
+       * params.def (PARAM_SCEV_MAX_EXPR_SIZE): New parameter with
+       default value 20.
+       * tree-chrec.c: Depend on params.h.  Replace build with buildN,
+       and fold build with fold_buildN.
+       (chrec_fold_plus_1): Fail with a chrec_don_know when the size of
+       the expression exceeds PARAM_SCEV_MAX_EXPR_SIZE.
+       (tree_contains_chrecs): Compute an estimation of the size of the
+       given expression.
+       * tree-chrec.h (tree_contains_chrecs): Modify its declaration.
+       (tree_does_not_contain_chrecs): Update the use of tree_contains_chrecs.
+       * tree-scalar-evolution.c (simple_iv): Ditto.
+       * doc/invoke.texi (scev-max-expr-size): Documented.
+
 2005-04-21  Richard Sandiford  <rsandifo@redhat.com>
 
        * config.gcc (*-*-darwin*): Add darwin.opt to $extra_options.

diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 5e2e9c6..d55603b 100644 (file)
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1795,7 +1795,7 @@ tree-browser.o : tree-browser.c tree-browser.def $(CONFIG_H) $(SYSTEM_H) \
    $(TREE_H) errors.h tree-inline.h diagnostic.h $(HASHTAB_H) \
    $(TM_H) coretypes.h
 tree-chrec.o: tree-chrec.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
-   errors.h $(GGC_H) $(TREE_H) tree-chrec.h tree-pass.h
+   errors.h $(GGC_H) $(TREE_H) tree-chrec.h tree-pass.h $(PARAMS_H)
 tree-scalar-evolution.o: tree-scalar-evolution.c $(CONFIG_H) $(SYSTEM_H) \
    coretypes.h $(TM_H) errors.h $(GGC_H) $(TREE_H) $(RTL_H) \
    $(BASIC_BLOCK_H) diagnostic.h $(TREE_FLOW_H) $(TREE_DUMP_H) \

diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index cb1e776..1b68630 100644 (file)
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -5680,6 +5680,10 @@ If number of candidates in the set is smaller than this value,
 we always try to remove unnecessary ivs from the set during its
 optimization when a new iv is added to the set.
 
+@item scev-max-expr-size
+Bound on size of expressions used in the scalar evolutions analyzer.
+Large expressions slow the analyzer.
+
 @item max-iterations-to-track
 
 The maximum number of iterations of a loop the brute force algorithm

diff --git a/gcc/params.def b/gcc/params.def
index 6a90a02..f2b25c0 100644 (file)
--- a/gcc/params.def
+++ b/gcc/params.def
@@ -372,6 +372,11 @@ DEFPARAM(PARAM_IV_ALWAYS_PRUNE_CAND_SET_BOUND,
         "If number of candidates in the set is smaller, we always try to remove unused ivs during its optimization",
         10, 0, 0)
 
+DEFPARAM(PARAM_SCEV_MAX_EXPR_SIZE,
+        "scev-max-expr-size",
+        "Bound on size of expressions used in the scalar evolutions analyzer",
+        20, 0, 0)
+
 /* The product of the next two is used to decide whether or not to
    use .GLOBAL_VAR.  See tree-dfa.c.  */
 DEFPARAM(PARAM_GLOBAL_VAR_THRESHOLD,

diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c
index b6276e9..967a3cd 100644 (file)
--- a/gcc/tree-chrec.c
+++ b/gcc/tree-chrec.c
@@ -35,6 +35,7 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "varray.h"
 #include "tree-chrec.h"
 #include "tree-pass.h"
+#include "params.h"
 
 \f
 
@@ -286,11 +287,17 @@ chrec_fold_plus_1 (enum tree_code code,
                                    build_int_cst_type (type, -1)));
 
        default:
-         if (tree_contains_chrecs (op0)
-             || tree_contains_chrecs (op1))
-           return build (code, type, op0, op1);
-         else
-           return fold (build (code, type, op0, op1));
+         {
+           int size = 0;
+           if ((tree_contains_chrecs (op0, &size)
+                || tree_contains_chrecs (op1, &size))
+               && size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
+             return build2 (code, type, op0, op1);
+           else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
+             return fold_build2 (code, type, op0, op1);
+           else
+             return chrec_dont_know;
+         }
        }
     }
 }
@@ -374,7 +381,7 @@ chrec_fold_multiply (tree type,
            return op0;
          if (integer_zerop (op1))
            return build_int_cst_type (type, 0);
-         return fold (build (MULT_EXPR, type, op0, op1));
+         return fold_build2 (MULT_EXPR, type, op0, op1);
        }
     }
 }
@@ -478,8 +485,8 @@ chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
       binomial_n_k = tree_fold_binomial (type, n, k);
       if (!binomial_n_k)
        return chrec_dont_know;
-      arg1 = fold (build2 (MULT_EXPR, type,
-                          CHREC_LEFT (chrec), binomial_n_k));
+      arg1 = fold_build2 (MULT_EXPR, type,
+                         CHREC_LEFT (chrec), binomial_n_k);
       return chrec_fold_plus (type, arg0, arg1);
     }
 
@@ -487,7 +494,7 @@ chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k)
   if (!binomial_n_k)
     return chrec_dont_know;
   
-  return fold (build2 (MULT_EXPR, type, chrec, binomial_n_k));
+  return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k);
 }
 
 /* Evaluates "CHREC (X)" when the varying variable is VAR.  
@@ -717,7 +724,7 @@ reset_evolution_in_loop (unsigned loop_num,
 {
   if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
       && CHREC_VARIABLE (chrec) > loop_num)
-    return build 
+    return build2 
       (TREE_CODE (chrec), 
        build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)), 
        reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), new_evol), 
@@ -862,29 +869,34 @@ chrec_contains_undetermined (tree chrec)
     }
 }
 
-/* Determines whether the tree EXPR contains chrecs.  */
+/* Determines whether the tree EXPR contains chrecs, and increment
+   SIZE if it is not a NULL pointer by an estimation of the depth of
+   the tree.  */
 
 bool
-tree_contains_chrecs (tree expr)
+tree_contains_chrecs (tree expr, int *size)
 {
   if (expr == NULL_TREE)
     return false;
+
+  if (size)
+    (*size)++;
   
   if (tree_is_chrec (expr))
     return true;
-  
+
   switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
     {
     case 3:
-      if (tree_contains_chrecs (TREE_OPERAND (expr, 2)))
+      if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size))
        return true;
       
     case 2:
-      if (tree_contains_chrecs (TREE_OPERAND (expr, 1)))
+      if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size))
        return true;
       
     case 1:
-      if (tree_contains_chrecs (TREE_OPERAND (expr, 0)))
+      if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size))
        return true;
       
     default:

diff --git a/gcc/tree-chrec.h b/gcc/tree-chrec.h
index a3e2190..8f8c065 100644 (file)
--- a/gcc/tree-chrec.h
+++ b/gcc/tree-chrec.h
@@ -87,7 +87,7 @@ extern bool chrec_is_positive (tree, bool *);
 extern bool chrec_contains_symbols (tree);
 extern bool chrec_contains_symbols_defined_in_loop (tree, unsigned);
 extern bool chrec_contains_undetermined (tree);
-extern bool tree_contains_chrecs (tree);
+extern bool tree_contains_chrecs (tree, int *);
 extern bool evolution_function_is_affine_multivariate_p (tree);
 extern bool evolution_function_is_univariate_p (tree);
 extern unsigned nb_vars_in_chrec (tree);
@@ -183,7 +183,7 @@ evolution_function_is_affine_or_constant_p (tree chrec)
 static inline bool
 tree_does_not_contain_chrecs (tree expr)
 {
-  return !tree_contains_chrecs (expr);
+  return !tree_contains_chrecs (expr, NULL);
 }
 
 /* Determines whether CHREC is a loop invariant with respect to LOOP_NUM.  

diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index e7c7545..ca80893 100644 (file)
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -2582,7 +2582,7 @@ simple_iv (struct loop *loop, tree stmt, tree op, tree *base, tree *step)
   if (TREE_CODE (*step) != INTEGER_CST)
     return false;
   *base = CHREC_LEFT (ev);
-  if (tree_contains_chrecs (*base)
+  if (tree_contains_chrecs (*base, NULL)
       || chrec_contains_symbols_defined_in_loop (*base, loop->num))
     return false;