diff options
Diffstat (limited to 'gcc/tree-chrec.c')
| -rw-r--r-- | gcc/tree-chrec.c | 209 |
1 files changed, 151 insertions, 58 deletions
diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c index 54960449217..25041f03f13 100644 --- a/gcc/tree-chrec.c +++ b/gcc/tree-chrec.c @@ -1,5 +1,5 @@ /* Chains of recurrences. - Copyright (C) 2003, 2004 Free Software Foundation, Inc. + Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc. Contributed by Sebastian Pop <s.pop@laposte.net> This file is part of GCC. @@ -35,7 +35,8 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "varray.h" #include "tree-chrec.h" #include "tree-pass.h" - +/* APPLE LOCAL mainline 4080945/ PR 20742 */ +#include "params.h" /* Extended folder for chrecs. */ @@ -286,11 +287,19 @@ 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)); +/* APPLE LOCAL begin mainline 4080945/ PR 20742 */ + { + 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; + } +/* APPLE LOCAL end mainline 4080945/ PR 20742 */ } } } @@ -383,63 +392,111 @@ chrec_fold_multiply (tree type, /* Operations. */ -/* The factorial. */ - +/* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate + calculation overflows, otherwise return C(n,k) with type TYPE. */ + static tree -tree_fold_factorial (tree f) +tree_fold_binomial (tree type, tree n, unsigned int k) { - if (tree_int_cst_sgn (f) <= 0) - return integer_one_node; + unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum; + HOST_WIDE_INT hidx, hnum, hdenom, hres, hdum; + unsigned int i; + tree res; + + /* Handle the most frequent cases. */ + if (k == 0) + return build_int_cst (type, 1); + if (k == 1) + return fold_convert (type, n); + + /* Check that k <= n. */ + if (TREE_INT_CST_HIGH (n) == 0 + && TREE_INT_CST_LOW (n) < k) + return NULL_TREE; + + /* Numerator = n. */ + lnum = TREE_INT_CST_LOW (n); + hnum = TREE_INT_CST_HIGH (n); + + /* Denominator = 2. */ + ldenom = 2; + hdenom = 0; + + /* Index = Numerator-1. */ + if (lnum == 0) + { + hidx = hnum - 1; + lidx = ~ (unsigned HOST_WIDE_INT) 0; + } else - return fold - (build (MULT_EXPR, integer_type_node, f, - tree_fold_factorial (fold (build (MINUS_EXPR, integer_type_node, - f, integer_one_node))))); -} + { + hidx = hnum; + lidx = lnum - 1; + } -/* The binomial coefficient. */ + /* Numerator = Numerator*Index = n*(n-1). */ + if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum)) + return NULL_TREE; -static tree -tree_fold_binomial (tree n, - tree k) -{ - return fold - (build (EXACT_DIV_EXPR, integer_type_node, tree_fold_factorial (n), - fold (build (MULT_EXPR, integer_type_node, - tree_fold_factorial (k), - tree_fold_factorial - (fold (build (MINUS_EXPR, integer_type_node, - n, k))))))); + for (i = 3; i <= k; i++) + { + /* Index--. */ + if (lidx == 0) + { + hidx--; + lidx = ~ (unsigned HOST_WIDE_INT) 0; + } + else + lidx--; + + /* Numerator *= Index. */ + if (mul_double (lnum, hnum, lidx, hidx, &lnum, &hnum)) + return NULL_TREE; + + /* Denominator *= i. */ + mul_double (ldenom, hdenom, i, 0, &ldenom, &hdenom); + } + + /* Result = Numerator / Denominator. */ + div_and_round_double (EXACT_DIV_EXPR, 1, lnum, hnum, ldenom, hdenom, + &lres, &hres, &ldum, &hdum); + + res = build_int_cst_wide (type, lres, hres); + return int_fits_type_p (res, type) ? res : NULL_TREE; } /* Helper function. Use the Newton's interpolating formula for evaluating the value of the evolution function. */ static tree -chrec_evaluate (unsigned var, - tree chrec, - tree n, - tree k) +chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k) { - tree type = chrec_type (chrec); - tree binomial_n_k = tree_fold_binomial (n, k); - - if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) + tree arg0, arg1, binomial_n_k; + tree type = TREE_TYPE (chrec); + + while (TREE_CODE (chrec) == POLYNOMIAL_CHREC + && CHREC_VARIABLE (chrec) > var) + chrec = CHREC_LEFT (chrec); + + if (TREE_CODE (chrec) == POLYNOMIAL_CHREC + && CHREC_VARIABLE (chrec) == var) { - if (CHREC_VARIABLE (chrec) > var) - return chrec_evaluate (var, CHREC_LEFT (chrec), n, k); - - if (CHREC_VARIABLE (chrec) == var) - return chrec_fold_plus - (type, - fold (build (MULT_EXPR, type, binomial_n_k, CHREC_LEFT (chrec))), - chrec_evaluate (var, CHREC_RIGHT (chrec), n, - fold (build (PLUS_EXPR, type, k, integer_one_node)))); - - return fold (build (MULT_EXPR, type, binomial_n_k, chrec)); + arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1); + if (arg0 == chrec_dont_know) + return chrec_dont_know; + 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)); + return chrec_fold_plus (type, arg0, arg1); } - else - return fold (build (MULT_EXPR, type, binomial_n_k, chrec)); + + binomial_n_k = tree_fold_binomial (type, n, k); + if (!binomial_n_k) + return chrec_dont_know; + + return fold (build2 (MULT_EXPR, type, chrec, binomial_n_k)); } /* Evaluates "CHREC (X)" when the varying variable is VAR. @@ -493,7 +550,7 @@ chrec_apply (unsigned var, 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); + res = chrec_evaluate (var, chrec, x, 0); else res = chrec_dont_know; @@ -669,7 +726,8 @@ reset_evolution_in_loop (unsigned loop_num, { if (TREE_CODE (chrec) == POLYNOMIAL_CHREC && CHREC_VARIABLE (chrec) > loop_num) - return build +/* APPLE LOCAL mainline 4080945/ PR 20742 */ + return build2 (TREE_CODE (chrec), build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)), reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), new_evol), @@ -814,29 +872,36 @@ chrec_contains_undetermined (tree chrec) } } -/* Determines whether the tree EXPR contains chrecs. */ +/* APPLE LOCAL begin mainline 4080945/ PR 20742 */ +/* 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)) +/* APPLE LOCAL end mainline 4080945/ PR 20742 */ return true; default: @@ -954,7 +1019,23 @@ nb_vars_in_chrec (tree chrec) -/* Convert the initial condition of chrec to type. */ +/* Convert CHREC to TYPE. The following is rule is always true: + TREE_TYPE (chrec) == TREE_TYPE (CHREC_LEFT (chrec)) == TREE_TYPE + (CHREC_RIGHT (chrec)). An example of what could happen when adding + two chrecs and the type of the CHREC_RIGHT is different than + CHREC_LEFT is: + + {(uint) 0, +, (uchar) 10} + + {(uint) 0, +, (uchar) 250} + + that would produce a wrong result if CHREC_RIGHT is not (uint): + + {(uint) 0, +, (uchar) 4} + + instead of + + {(uint) 0, +, (uint) 260} +*/ tree chrec_convert (tree type, @@ -989,6 +1070,18 @@ chrec_convert (tree type, TREE_OVERFLOW (res) = 0; if (CONSTANT_CLASS_P (res)) TREE_CONSTANT_OVERFLOW (res) = 0; + + /* But reject constants that don't fit in their type after conversion. + This can happen if TYPE_MIN_VALUE or TYPE_MAX_VALUE are not the + natural values associated with TYPE_PRECISION and TYPE_UNSIGNED, + and can cause problems later when computing niters of loops. Note + that we don't do the check before converting because we don't want + to reject conversions of negative chrecs to unsigned types. */ + if (TREE_CODE (res) == INTEGER_CST + && TREE_CODE (type) == INTEGER_TYPE + && !int_fits_type_p (res, type)) + res = chrec_dont_know; + return res; } } |