This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: Patch for bug 20742
Richard Henderson wrote:
> On Fri, Apr 08, 2005 at 12:36:44PM +0200, Sebastian Pop wrote:
> > (chrec_fold_plus_1): Fail with a chrec_don_know
> > when the size of the expression exceeds 20.
>
> I'd prefer this magic number be replaced with a --param.
>
Whoups, this was a typo in the ChangeLog: I have fixed the code as
proposed by Jakub, and forgot to modify this bit in the previous
ChangeLog. Here is the updated patch and ChangeLog.
* 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.
Index: params.def
===================================================================
RCS file: /cvs/gcc/gcc/gcc/params.def,v
retrieving revision 1.57
diff -d -u -p -r1.57 params.def
--- params.def 6 Apr 2005 20:03:14 -0000 1.57
+++ params.def 11 Apr 2005 08:18:39 -0000
@@ -372,6 +372,11 @@ DEFPARAM(PARAM_IV_ALWAYS_PRUNE_CAND_SET_
"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,
Index: tree-chrec.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.c,v
retrieving revision 2.14
diff -d -u -p -r2.14 tree-chrec.c
--- tree-chrec.c 5 Apr 2005 07:06:23 -0000 2.14
+++ tree-chrec.c 11 Apr 2005 08:18:39 -0000
@@ -35,6 +35,7 @@ Software Foundation, 59 Temple Place - S
#include "varray.h"
#include "tree-chrec.h"
#include "tree-pass.h"
+#include "params.h"
@@ -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
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
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_n
{
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:
Index: tree-chrec.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-chrec.h,v
retrieving revision 2.6
diff -d -u -p -r2.6 tree-chrec.h
--- tree-chrec.h 17 Nov 2004 22:06:00 -0000 2.6
+++ tree-chrec.h 11 Apr 2005 08:18:39 -0000
@@ -87,7 +87,7 @@ extern bool chrec_is_positive (tree, boo
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
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.
Index: tree-loop-linear.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-loop-linear.c,v
retrieving revision 2.10
diff -d -u -p -r2.10 tree-loop-linear.c
--- tree-loop-linear.c 5 Apr 2005 19:05:02 -0000 2.10
+++ tree-loop-linear.c 11 Apr 2005 08:18:40 -0000
@@ -293,9 +293,13 @@ linear_transform_loops (struct loops *lo
VARRAY_GENERIC_PTR_INIT (dependence_relations, 10,
"dependence_relations");
-
+
+ dump_file = stderr;
+ dump_flags = 31;
compute_data_dependences_for_loop (depth, loop_nest,
&datarefs, &dependence_relations);
+ dump_data_references (stderr, dependence_relations);
+
if (dump_file && (dump_flags & TDF_DETAILS))
{
unsigned int j;
Index: tree-scalar-evolution.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-scalar-evolution.c,v
retrieving revision 2.18
diff -d -u -p -r2.18 tree-scalar-evolution.c
--- tree-scalar-evolution.c 30 Mar 2005 12:14:49 -0000 2.18
+++ tree-scalar-evolution.c 11 Apr 2005 08:18:43 -0000
@@ -2563,7 +2563,7 @@ simple_iv (struct loop *loop, tree stmt,
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;
Index: doc/invoke.texi
===================================================================
RCS file: /cvs/gcc/gcc/gcc/doc/invoke.texi,v
retrieving revision 1.601
diff -d -u -p -r1.601 invoke.texi
--- doc/invoke.texi 6 Apr 2005 20:03:15 -0000 1.601
+++ doc/invoke.texi 11 Apr 2005 08:18:46 -0000
@@ -5633,6 +5633,10 @@ If number of candidates in the set is sm
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