X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Ftree-chrec.c;h=18ed4ed2a38c043672f72476b98fddb5bd16ee55;hb=0378889e03cb5daa8dbca43966085838a7ae5b1c;hp=495f95a8be7ede91f95e39dc087854462b392e8e;hpb=a9538d681b63fb9ff2291c3fde1ddd1ab389576c;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/tree-chrec.c b/gcc/tree-chrec.c index 495f95a8be7..18ed4ed2a38 100644 --- a/gcc/tree-chrec.c +++ b/gcc/tree-chrec.c @@ -37,6 +37,7 @@ along with GCC; see the file COPYING3. If not see #include "tree-chrec.h" #include "tree-pass.h" #include "params.h" +#include "flags.h" #include "tree-scalar-evolution.h" @@ -53,10 +54,10 @@ is_not_constant_evolution (const_tree cst) /* Fold CODE for a polynomial function and a constant. */ -static inline tree -chrec_fold_poly_cst (enum tree_code code, - tree type, - tree poly, +static inline tree +chrec_fold_poly_cst (enum tree_code code, + tree type, + tree poly, tree cst) { gcc_assert (poly); @@ -68,23 +69,23 @@ chrec_fold_poly_cst (enum tree_code code, switch (code) { case PLUS_EXPR: - return build_polynomial_chrec - (CHREC_VARIABLE (poly), + return build_polynomial_chrec + (CHREC_VARIABLE (poly), chrec_fold_plus (type, CHREC_LEFT (poly), cst), CHREC_RIGHT (poly)); - + case MINUS_EXPR: - return build_polynomial_chrec - (CHREC_VARIABLE (poly), + return build_polynomial_chrec + (CHREC_VARIABLE (poly), chrec_fold_minus (type, CHREC_LEFT (poly), cst), CHREC_RIGHT (poly)); - + case MULT_EXPR: - return build_polynomial_chrec - (CHREC_VARIABLE (poly), + return build_polynomial_chrec + (CHREC_VARIABLE (poly), chrec_fold_multiply (type, CHREC_LEFT (poly), cst), chrec_fold_multiply (type, CHREC_RIGHT (poly), cst)); - + default: return chrec_dont_know; } @@ -92,10 +93,10 @@ chrec_fold_poly_cst (enum tree_code code, /* Fold the addition of two polynomial functions. */ -static inline tree -chrec_fold_plus_poly_poly (enum tree_code code, - tree type, - tree poly0, +static inline tree +chrec_fold_plus_poly_poly (enum tree_code code, + tree type, + tree poly0, tree poly1) { tree left, right; @@ -112,7 +113,7 @@ chrec_fold_plus_poly_poly (enum tree_code code, else gcc_assert (chrec_type (poly0) == chrec_type (poly1)); gcc_assert (type == chrec_type (poly0)); - + /* {a, +, b}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2, {a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2, @@ -120,67 +121,67 @@ chrec_fold_plus_poly_poly (enum tree_code code, if (flow_loop_nested_p (loop0, loop1)) { if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) - return build_polynomial_chrec - (CHREC_VARIABLE (poly1), + return build_polynomial_chrec + (CHREC_VARIABLE (poly1), chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)), CHREC_RIGHT (poly1)); else - return build_polynomial_chrec - (CHREC_VARIABLE (poly1), + return build_polynomial_chrec + (CHREC_VARIABLE (poly1), chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)), - chrec_fold_multiply (type, CHREC_RIGHT (poly1), + chrec_fold_multiply (type, CHREC_RIGHT (poly1), SCALAR_FLOAT_TYPE_P (type) ? build_real (type, dconstm1) : build_int_cst_type (type, -1))); } - + if (flow_loop_nested_p (loop1, loop0)) { if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) - return build_polynomial_chrec - (CHREC_VARIABLE (poly0), + return build_polynomial_chrec + (CHREC_VARIABLE (poly0), chrec_fold_plus (type, CHREC_LEFT (poly0), poly1), CHREC_RIGHT (poly0)); else - return build_polynomial_chrec - (CHREC_VARIABLE (poly0), + return build_polynomial_chrec + (CHREC_VARIABLE (poly0), chrec_fold_minus (type, CHREC_LEFT (poly0), poly1), CHREC_RIGHT (poly0)); } - + /* This function should never be called for chrecs of loops that do not belong to the same loop nest. */ gcc_assert (loop0 == loop1); if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) { - left = chrec_fold_plus + left = chrec_fold_plus (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); - right = chrec_fold_plus + right = chrec_fold_plus (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); } else { - left = chrec_fold_minus + left = chrec_fold_minus (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); - right = chrec_fold_minus + right = chrec_fold_minus (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); } if (chrec_zerop (right)) return left; else - return build_polynomial_chrec - (CHREC_VARIABLE (poly0), left, right); + return build_polynomial_chrec + (CHREC_VARIABLE (poly0), left, right); } /* Fold the multiplication of two polynomial functions. */ -static inline tree -chrec_fold_multiply_poly_poly (tree type, - tree poly0, +static inline tree +chrec_fold_multiply_poly_poly (tree type, + tree poly0, tree poly1) { tree t0, t1, t2; @@ -194,42 +195,42 @@ chrec_fold_multiply_poly_poly (tree type, gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC); gcc_assert (chrec_type (poly0) == chrec_type (poly1)); gcc_assert (type == chrec_type (poly0)); - + /* {a, +, b}_1 * {c, +, d}_2 -> {c*{a, +, b}_1, +, d}_2, {a, +, b}_2 * {c, +, d}_1 -> {a*{c, +, d}_1, +, b}_2, {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ if (flow_loop_nested_p (loop0, loop1)) /* poly0 is a constant wrt. poly1. */ - return build_polynomial_chrec - (CHREC_VARIABLE (poly1), + return build_polynomial_chrec + (CHREC_VARIABLE (poly1), chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0), CHREC_RIGHT (poly1)); - + if (flow_loop_nested_p (loop1, loop0)) /* poly1 is a constant wrt. poly0. */ - return build_polynomial_chrec - (CHREC_VARIABLE (poly0), + return build_polynomial_chrec + (CHREC_VARIABLE (poly0), chrec_fold_multiply (type, CHREC_LEFT (poly0), poly1), CHREC_RIGHT (poly0)); - + gcc_assert (loop0 == loop1); /* poly0 and poly1 are two polynomials in the same variable, {a, +, b}_x * {c, +, d}_x -> {a*c, +, a*d + b*c + b*d, +, 2*b*d}_x. */ - + /* "a*c". */ t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)); - /* "a*d + b*c + b*d". */ + /* "a*d + b*c". */ t1 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1)); t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_LEFT (poly1))); - t1 = chrec_fold_plus (type, t1, chrec_fold_multiply (type, - CHREC_RIGHT (poly0), - CHREC_RIGHT (poly1))); - /* "2*b*d". */ + /* "b*d". */ t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1)); + /* "a*d + b*c + b*d". */ + t1 = chrec_fold_plus (type, t1, t2); + /* "2*b*d". */ t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type) ? build_real (type, dconst2) : build_int_cst (type, 2), t2); @@ -242,22 +243,22 @@ chrec_fold_multiply_poly_poly (tree type, /* When the operands are automatically_generated_chrec_p, the fold has to respect the semantics of the operands. */ -static inline tree -chrec_fold_automatically_generated_operands (tree op0, +static inline tree +chrec_fold_automatically_generated_operands (tree op0, tree op1) { if (op0 == chrec_dont_know || op1 == chrec_dont_know) return chrec_dont_know; - + if (op0 == chrec_known || op1 == chrec_known) return chrec_known; - + if (op0 == chrec_not_analyzed_yet || op1 == chrec_not_analyzed_yet) return chrec_not_analyzed_yet; - + /* The default case produces a safe result. */ return chrec_dont_know; } @@ -265,7 +266,7 @@ chrec_fold_automatically_generated_operands (tree op0, /* Fold the addition of two chrecs. */ static tree -chrec_fold_plus_1 (enum tree_code code, tree type, +chrec_fold_plus_1 (enum tree_code code, tree type, tree op0, tree op1) { tree op1_type = code == POINTER_PLUS_EXPR ? sizetype : type; @@ -273,7 +274,7 @@ chrec_fold_plus_1 (enum tree_code code, tree type, if (automatically_generated_chrec_p (op0) || automatically_generated_chrec_p (op1)) return chrec_fold_automatically_generated_operands (op0, op1); - + switch (TREE_CODE (op0)) { case POLYNOMIAL_CHREC: @@ -284,13 +285,13 @@ chrec_fold_plus_1 (enum tree_code code, tree type, default: if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) - return build_polynomial_chrec - (CHREC_VARIABLE (op0), + return build_polynomial_chrec + (CHREC_VARIABLE (op0), chrec_fold_plus (type, CHREC_LEFT (op0), op1), CHREC_RIGHT (op0)); else - return build_polynomial_chrec - (CHREC_VARIABLE (op0), + return build_polynomial_chrec + (CHREC_VARIABLE (op0), chrec_fold_minus (type, CHREC_LEFT (op0), op1), CHREC_RIGHT (op0)); } @@ -300,15 +301,15 @@ chrec_fold_plus_1 (enum tree_code code, tree type, { case POLYNOMIAL_CHREC: if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR) - return build_polynomial_chrec - (CHREC_VARIABLE (op1), + return build_polynomial_chrec + (CHREC_VARIABLE (op1), chrec_fold_plus (type, op0, CHREC_LEFT (op1)), CHREC_RIGHT (op1)); else - return build_polynomial_chrec - (CHREC_VARIABLE (op1), + return build_polynomial_chrec + (CHREC_VARIABLE (op1), chrec_fold_minus (type, op0, CHREC_LEFT (op1)), - chrec_fold_multiply (type, CHREC_RIGHT (op1), + chrec_fold_multiply (type, CHREC_RIGHT (op1), SCALAR_FLOAT_TYPE_P (type) ? build_real (type, dconstm1) : build_int_cst_type (type, -1))); @@ -334,7 +335,7 @@ chrec_fold_plus_1 (enum tree_code code, tree type, /* Fold the addition of two chrecs. */ tree -chrec_fold_plus (tree type, +chrec_fold_plus (tree type, tree op0, tree op1) { @@ -352,15 +353,15 @@ chrec_fold_plus (tree type, code = POINTER_PLUS_EXPR; else code = PLUS_EXPR; - + return chrec_fold_plus_1 (code, type, op0, op1); } /* Fold the subtraction of two chrecs. */ -tree -chrec_fold_minus (tree type, - tree op0, +tree +chrec_fold_minus (tree type, + tree op0, tree op1) { if (automatically_generated_chrec_p (op0) @@ -369,21 +370,21 @@ chrec_fold_minus (tree type, if (integer_zerop (op1)) return op0; - + return chrec_fold_plus_1 (MINUS_EXPR, type, op0, op1); } /* Fold the multiplication of two chrecs. */ tree -chrec_fold_multiply (tree type, +chrec_fold_multiply (tree type, tree op0, tree op1) { if (automatically_generated_chrec_p (op0) || automatically_generated_chrec_p (op1)) return chrec_fold_automatically_generated_operands (op0, op1); - + switch (TREE_CODE (op0)) { case POLYNOMIAL_CHREC: @@ -391,34 +392,34 @@ chrec_fold_multiply (tree type, { case POLYNOMIAL_CHREC: return chrec_fold_multiply_poly_poly (type, op0, op1); - + default: if (integer_onep (op1)) return op0; if (integer_zerop (op1)) return build_int_cst (type, 0); - - return build_polynomial_chrec - (CHREC_VARIABLE (op0), + + return build_polynomial_chrec + (CHREC_VARIABLE (op0), chrec_fold_multiply (type, CHREC_LEFT (op0), op1), chrec_fold_multiply (type, CHREC_RIGHT (op0), op1)); } - + default: if (integer_onep (op0)) return op1; - + if (integer_zerop (op0)) return build_int_cst (type, 0); - + switch (TREE_CODE (op1)) { case POLYNOMIAL_CHREC: - return build_polynomial_chrec - (CHREC_VARIABLE (op1), + return build_polynomial_chrec + (CHREC_VARIABLE (op1), chrec_fold_multiply (type, CHREC_LEFT (op1), op0), chrec_fold_multiply (type, CHREC_RIGHT (op1), op0)); - + default: if (integer_onep (op1)) return op0; @@ -436,7 +437,7 @@ chrec_fold_multiply (tree type, /* Evaluate the binomial coefficient. Return NULL_TREE if the intermediate calculation overflows, otherwise return C(n,k) with type TYPE. */ -static tree +static tree tree_fold_binomial (tree type, tree n, unsigned int k) { unsigned HOST_WIDE_INT lidx, lnum, ldenom, lres, ldum; @@ -509,7 +510,7 @@ tree_fold_binomial (tree type, tree n, unsigned int k) /* Helper function. Use the Newton's interpolating formula for evaluating the value of the evolution function. */ -static tree +static tree chrec_evaluate (unsigned var, tree chrec, tree n, unsigned int k) { tree arg0, arg1, binomial_n_k; @@ -537,24 +538,24 @@ 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; - + return fold_build2 (MULT_EXPR, type, chrec, binomial_n_k); } -/* Evaluates "CHREC (X)" when the varying variable is VAR. - Example: Given the following parameters, - +/* Evaluates "CHREC (X)" when the varying variable is VAR. + Example: Given the following parameters, + var = 1 chrec = {3, +, 4}_1 x = 10 - - The result is given by the Newton's interpolating formula: + + The result is given by the Newton's interpolating formula: 3 * \binom{10}{0} + 4 * \binom{10}{1}. */ -tree +tree chrec_apply (unsigned var, - tree chrec, + tree chrec, tree x) { tree type = chrec_type (chrec); @@ -568,7 +569,7 @@ chrec_apply (unsigned var, constants with respect to the varying loop. */ || chrec_contains_symbols_defined_in_loop (chrec, var)) return chrec_dont_know; - + if (dump_file && (dump_flags & TDF_DETAILS)) fprintf (dump_file, "(chrec_apply \n"); @@ -582,17 +583,17 @@ chrec_apply (unsigned var, res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x); res = chrec_fold_plus (type, CHREC_LEFT (chrec), res); } - + else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC) 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, 0); else res = chrec_dont_know; - + if (dump_file && (dump_flags & TDF_DETAILS)) { fprintf (dump_file, " (varying_loop = %d\n", var); @@ -604,14 +605,14 @@ chrec_apply (unsigned var, print_generic_expr (dump_file, res, 0); fprintf (dump_file, "))\n"); } - + return res; } /* Replaces the initial condition in CHREC with INIT_COND. */ -tree -chrec_replace_initial_condition (tree chrec, +tree +chrec_replace_initial_condition (tree chrec, tree init_cond) { if (automatically_generated_chrec_p (chrec)) @@ -622,11 +623,11 @@ chrec_replace_initial_condition (tree chrec, switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: - return build_polynomial_chrec + return build_polynomial_chrec (CHREC_VARIABLE (chrec), chrec_replace_initial_condition (CHREC_LEFT (chrec), init_cond), CHREC_RIGHT (chrec)); - + default: return init_cond; } @@ -634,12 +635,12 @@ chrec_replace_initial_condition (tree chrec, /* Returns the initial condition of a given CHREC. */ -tree +tree initial_condition (tree chrec) { if (automatically_generated_chrec_p (chrec)) return chrec; - + if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) return initial_condition (CHREC_LEFT (chrec)); else @@ -649,37 +650,37 @@ initial_condition (tree chrec) /* Returns a univariate function that represents the evolution in LOOP_NUM. Mask the evolution of any other loop. */ -tree -hide_evolution_in_other_loops_than_loop (tree chrec, +tree +hide_evolution_in_other_loops_than_loop (tree chrec, unsigned loop_num) { struct loop *loop = get_loop (loop_num), *chloop; if (automatically_generated_chrec_p (chrec)) return chrec; - + switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: chloop = get_chrec_loop (chrec); if (chloop == loop) - return build_polynomial_chrec - (loop_num, - hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), - loop_num), + return build_polynomial_chrec + (loop_num, + hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), + loop_num), CHREC_RIGHT (chrec)); - + else if (flow_loop_nested_p (chloop, loop)) /* There is no evolution in this loop. */ return initial_condition (chrec); - + else { gcc_assert (flow_loop_nested_p (loop, chloop)); - return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), + return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec), loop_num); } - + default: return chrec; } @@ -688,8 +689,8 @@ hide_evolution_in_other_loops_than_loop (tree chrec, /* Returns the evolution part of CHREC in LOOP_NUM when RIGHT is true, otherwise returns the initial condition in LOOP_NUM. */ -static tree -chrec_component_in_loop_num (tree chrec, +static tree +chrec_component_in_loop_num (tree chrec, unsigned loop_num, bool right) { @@ -698,7 +699,7 @@ chrec_component_in_loop_num (tree chrec, if (automatically_generated_chrec_p (chrec)) return chrec; - + switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: @@ -714,28 +715,28 @@ chrec_component_in_loop_num (tree chrec, if (TREE_CODE (CHREC_LEFT (chrec)) != POLYNOMIAL_CHREC || CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec)) return component; - + else return build_polynomial_chrec - (loop_num, - chrec_component_in_loop_num (CHREC_LEFT (chrec), - loop_num, - right), + (loop_num, + chrec_component_in_loop_num (CHREC_LEFT (chrec), + loop_num, + right), component); } - + else if (flow_loop_nested_p (chloop, loop)) /* There is no evolution part in this loop. */ return NULL_TREE; - + else { gcc_assert (flow_loop_nested_p (loop, chloop)); - return chrec_component_in_loop_num (CHREC_LEFT (chrec), - loop_num, + return chrec_component_in_loop_num (CHREC_LEFT (chrec), + loop_num, right); } - + default: if (right) return NULL_TREE; @@ -745,22 +746,22 @@ chrec_component_in_loop_num (tree chrec, } /* Returns the evolution part in LOOP_NUM. Example: the call - evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns + evolution_part_in_loop_num ({{0, +, 1}_1, +, 2}_1, 1) returns {1, +, 2}_1 */ -tree -evolution_part_in_loop_num (tree chrec, +tree +evolution_part_in_loop_num (tree chrec, unsigned loop_num) { return chrec_component_in_loop_num (chrec, loop_num, true); } /* Returns the initial condition in LOOP_NUM. Example: the call - initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns + initial_condition_in_loop_num ({{0, +, 1}_1, +, 2}_2, 2) returns {0, +, 1}_1 */ -tree -initial_condition_in_loop_num (tree chrec, +tree +initial_condition_in_loop_num (tree chrec, unsigned loop_num) { return chrec_component_in_loop_num (chrec, loop_num, false); @@ -771,9 +772,9 @@ initial_condition_in_loop_num (tree chrec, chrec_dont_know, for example after having determined that it is impossible to say how many times a loop will execute. */ -tree +tree reset_evolution_in_loop (unsigned loop_num, - tree chrec, + tree chrec, tree new_evol) { struct loop *loop = get_loop (loop_num); @@ -798,7 +799,7 @@ reset_evolution_in_loop (unsigned loop_num, while (TREE_CODE (chrec) == POLYNOMIAL_CHREC && CHREC_VARIABLE (chrec) == loop_num) chrec = CHREC_LEFT (chrec); - + return build_polynomial_chrec (loop_num, chrec, new_evol); } @@ -806,14 +807,14 @@ reset_evolution_in_loop (unsigned loop_num, alternate paths of a conditional expression. */ tree -chrec_merge (tree chrec1, +chrec_merge (tree chrec1, tree chrec2) { if (chrec1 == chrec_dont_know || chrec2 == chrec_dont_know) return chrec_dont_know; - if (chrec1 == chrec_known + if (chrec1 == chrec_known || chrec2 == chrec_known) return chrec_known; @@ -834,18 +835,18 @@ chrec_merge (tree chrec1, /* Helper function for is_multivariate_chrec. */ -static bool +static bool is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var) { if (chrec == NULL_TREE) return false; - + if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) { if (CHREC_VARIABLE (chrec) != rec_var) return true; else - return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var) + return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), rec_var) || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), rec_var)); } else @@ -854,16 +855,16 @@ is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var) /* Determine whether the given chrec is multivariate or not. */ -bool +bool is_multivariate_chrec (const_tree chrec) { if (chrec == NULL_TREE) return false; - + if (TREE_CODE (chrec) == POLYNOMIAL_CHREC) - return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), + return (is_multivariate_chrec_rec (CHREC_LEFT (chrec), CHREC_VARIABLE (chrec)) - || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), + || is_multivariate_chrec_rec (CHREC_RIGHT (chrec), CHREC_VARIABLE (chrec))); else return false; @@ -871,14 +872,14 @@ is_multivariate_chrec (const_tree chrec) /* Determines whether the chrec contains symbolic names or not. */ -bool +bool chrec_contains_symbols (const_tree chrec) { int i, n; if (chrec == NULL_TREE) return false; - + if (TREE_CODE (chrec) == SSA_NAME || TREE_CODE (chrec) == VAR_DECL || TREE_CODE (chrec) == PARM_DECL @@ -897,7 +898,7 @@ chrec_contains_symbols (const_tree chrec) /* Determines whether the chrec contains undetermined coefficients. */ -bool +bool chrec_contains_undetermined (const_tree chrec) { int i, n; @@ -929,7 +930,7 @@ tree_contains_chrecs (const_tree expr, int *size) if (size) (*size)++; - + if (tree_is_chrec (expr)) return true; @@ -970,7 +971,7 @@ evolution_function_is_invariant_rec_p (tree chrec, int loopnum) if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1), loopnum)) return false; - + case 1: if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0), loopnum)) @@ -995,12 +996,12 @@ evolution_function_is_invariant_p (tree chrec, int loopnum) /* Determine whether the given tree is an affine multivariate evolution. */ -bool +bool evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum) { if (chrec == NULL_TREE) return false; - + switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: @@ -1011,9 +1012,9 @@ evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum) else { if (TREE_CODE (CHREC_RIGHT (chrec)) == POLYNOMIAL_CHREC - && CHREC_VARIABLE (CHREC_RIGHT (chrec)) + && CHREC_VARIABLE (CHREC_RIGHT (chrec)) != CHREC_VARIABLE (chrec) - && evolution_function_is_affine_multivariate_p + && evolution_function_is_affine_multivariate_p (CHREC_RIGHT (chrec), loopnum)) return true; else @@ -1025,19 +1026,19 @@ evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum) if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum) && TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC && CHREC_VARIABLE (CHREC_LEFT (chrec)) != CHREC_VARIABLE (chrec) - && evolution_function_is_affine_multivariate_p + && evolution_function_is_affine_multivariate_p (CHREC_LEFT (chrec), loopnum)) return true; else return false; } - + default: return false; } } -/* Determine whether the given tree is a function in zero or one +/* Determine whether the given tree is a function in zero or one variables. */ bool @@ -1045,7 +1046,7 @@ evolution_function_is_univariate_p (const_tree chrec) { if (chrec == NULL_TREE) return true; - + switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: @@ -1057,11 +1058,11 @@ evolution_function_is_univariate_p (const_tree chrec) if (!evolution_function_is_univariate_p (CHREC_LEFT (chrec))) return false; break; - + default: break; } - + switch (TREE_CODE (CHREC_RIGHT (chrec))) { case POLYNOMIAL_CHREC: @@ -1070,11 +1071,11 @@ evolution_function_is_univariate_p (const_tree chrec) if (!evolution_function_is_univariate_p (CHREC_RIGHT (chrec))) return false; break; - + default: - break; + break; } - + default: return true; } @@ -1083,7 +1084,7 @@ evolution_function_is_univariate_p (const_tree chrec) /* Returns the number of variables of CHREC. Example: the call nb_vars_in_chrec ({{0, +, 1}_5, +, 2}_6) returns 2. */ -unsigned +unsigned nb_vars_in_chrec (tree chrec) { if (chrec == NULL_TREE) @@ -1092,7 +1093,7 @@ nb_vars_in_chrec (tree chrec) switch (TREE_CODE (chrec)) { case POLYNOMIAL_CHREC: - return 1 + nb_vars_in_chrec + return 1 + nb_vars_in_chrec (initial_condition_in_loop_num (chrec, CHREC_VARIABLE (chrec))); default: @@ -1124,7 +1125,7 @@ convert_affine_scev (struct loop *loop, tree type, /* In general, (TYPE) (BASE + STEP * i) = (TYPE) BASE + (TYPE -- sign extend) STEP * i, but we must check some assumptions. - + 1) If [BASE, +, STEP] wraps, the equation is not valid when precision of CT is smaller than the precision of TYPE. For example, when we cast unsigned char [254, +, 1] to unsigned, the values on left side @@ -1182,7 +1183,7 @@ convert_affine_scev (struct loop *loop, tree type, of CT and TYPE. This only needs to be handled specially when CT is unsigned -- to avoid e.g. unsigned char [100, +, 255] (with values 100, 99, 98, ...) from becoming signed or unsigned - [100, +, 255] with values 100, 355, ...; the sign-extension is + [100, +, 255] with values 100, 355, ...; the sign-extension is performed by default when CT is signed. */ new_step = *step; if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct)) @@ -1208,7 +1209,7 @@ convert_affine_scev (struct loop *loop, tree type, /* Convert CHREC for the right hand side of a CREC. The increment for a pointer type is always sizetype. */ -tree +tree chrec_convert_rhs (tree type, tree chrec, gimple at_stmt) { if (POINTER_TYPE_P (type)) @@ -1227,12 +1228,12 @@ chrec_convert_rhs (tree type, tree chrec, gimple at_stmt) 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 @@ -1240,7 +1241,7 @@ chrec_convert_rhs (tree type, tree chrec, gimple at_stmt) {(uint) 0, +, (uint) 260} */ -tree +tree chrec_convert (tree type, tree chrec, gimple at_stmt) { return chrec_convert_1 (type, chrec, at_stmt, true); @@ -1252,13 +1253,13 @@ chrec_convert (tree type, tree chrec, gimple at_stmt) conversion is less accurate: the information is used for determining a more accurate estimation of the number of iterations. By default AT_STMT could be safely set to NULL_TREE. - + USE_OVERFLOW_SEMANTICS is true if this function should assume that the rules for overflow of the given language apply (e.g., that signed arithmetics in C does not overflow) -- i.e., to use them to avoid unnecessary tests, but also to enforce that the result follows them. */ -static tree +static tree chrec_convert_1 (tree type, tree chrec, gimple at_stmt, bool use_overflow_semantics) { @@ -1268,7 +1269,7 @@ chrec_convert_1 (tree type, tree chrec, gimple at_stmt, if (automatically_generated_chrec_p (chrec)) return chrec; - + ct = chrec_type (chrec); if (ct == type) return chrec; @@ -1286,7 +1287,21 @@ chrec_convert_1 (tree type, tree chrec, gimple at_stmt, /* If we cannot propagate the cast inside the chrec, just keep the cast. */ keep_cast: - res = fold_convert (type, chrec); + /* Fold will not canonicalize (long)(i - 1) to (long)i - 1 because that + may be more expensive. We do want to perform this optimization here + though for canonicalization reasons. */ + if (use_overflow_semantics + && (TREE_CODE (chrec) == PLUS_EXPR + || TREE_CODE (chrec) == MINUS_EXPR) + && TREE_CODE (type) == INTEGER_TYPE + && TREE_CODE (ct) == INTEGER_TYPE + && TYPE_PRECISION (type) > TYPE_PRECISION (ct) + && TYPE_OVERFLOW_UNDEFINED (ct)) + res = fold_build2 (TREE_CODE (chrec), type, + fold_convert (type, TREE_OPERAND (chrec, 0)), + fold_convert (type, TREE_OPERAND (chrec, 1))); + else + res = fold_convert (type, chrec); /* Don't propagate overflows. */ if (CONSTANT_CLASS_P (res)) @@ -1333,13 +1348,13 @@ chrec_convert_aggressive (tree type, tree chrec) rc = chrec_convert_aggressive (rtype, right); if (!rc) rc = chrec_convert (rtype, right, NULL); - + return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc); } /* Returns true when CHREC0 == CHREC1. */ -bool +bool eq_evolutions_p (const_tree chrec0, const_tree chrec1) { if (chrec0 == NULL_TREE @@ -1361,7 +1376,7 @@ eq_evolutions_p (const_tree chrec0, const_tree chrec1) && eq_evolutions_p (CHREC_RIGHT (chrec0), CHREC_RIGHT (chrec1))); default: return false; - } + } } /* Returns EV_GROWS if CHREC grows (assuming that it does not overflow), @@ -1398,7 +1413,7 @@ for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data) case 2: for_each_scev_op (&TREE_OPERAND (*scev, 1), cbck, data); - + case 1: for_each_scev_op (&TREE_OPERAND (*scev, 0), cbck, data); @@ -1425,6 +1440,7 @@ operator_is_linear (tree scev) case NEGATE_EXPR: case SSA_NAME: case NON_LVALUE_EXPR: + case BIT_NOT_EXPR: CASE_CONVERT: return true; @@ -1448,6 +1464,10 @@ scev_is_linear_expression (tree scev) return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL) && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL)); + if (TREE_CODE (scev) == POLYNOMIAL_CHREC + && !evolution_function_is_affine_multivariate_p (scev, CHREC_VARIABLE (scev))) + return false; + switch (TREE_CODE_LENGTH (TREE_CODE (scev))) { case 3: @@ -1458,7 +1478,7 @@ scev_is_linear_expression (tree scev) case 2: return scev_is_linear_expression (TREE_OPERAND (scev, 0)) && scev_is_linear_expression (TREE_OPERAND (scev, 1)); - + case 1: return scev_is_linear_expression (TREE_OPERAND (scev, 0)); @@ -1469,3 +1489,33 @@ scev_is_linear_expression (tree scev) return false; } } + +/* Determines whether the expression CHREC contains only interger consts + in the right parts. */ + +bool +evolution_function_right_is_integer_cst (const_tree chrec) +{ + if (chrec == NULL_TREE) + return false; + + switch (TREE_CODE (chrec)) + { + case INTEGER_CST: + return true; + + case POLYNOMIAL_CHREC: + if (!evolution_function_right_is_integer_cst (CHREC_RIGHT (chrec))) + return false; + + if (TREE_CODE (CHREC_LEFT (chrec)) == POLYNOMIAL_CHREC + && !evolution_function_right_is_integer_cst (CHREC_LEFT (chrec))) + return false; + + return true; + + default: + return false; + } +} +