GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
-Software Foundation; either version 2, or (at your option) any later
+Software Foundation; either version 3, or (at your option) any later
version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY
for more details.
You should have received a copy of the GNU General Public License
-along with GCC; see the file COPYING. If not, write to the Free
-Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, USA. */
+along with GCC; see the file COPYING3. If not see
+<http://www.gnu.org/licenses/>. */
/* This file implements operations on chains of recurrences. Chains
of recurrences are used for modeling evolution functions of scalar
/* Determines whether CST is not a constant evolution. */
static inline bool
-is_not_constant_evolution (tree cst)
+is_not_constant_evolution (const_tree cst)
{
return (TREE_CODE (cst) == POLYNOMIAL_CHREC);
}
tree left, right;
struct loop *loop0 = get_chrec_loop (poly0);
struct loop *loop1 = get_chrec_loop (poly1);
+ tree rtype = code == POINTER_PLUS_EXPR ? sizetype : type;
gcc_assert (poly0);
gcc_assert (poly1);
gcc_assert (TREE_CODE (poly0) == POLYNOMIAL_CHREC);
gcc_assert (TREE_CODE (poly1) == POLYNOMIAL_CHREC);
- gcc_assert (chrec_type (poly0) == chrec_type (poly1));
+ if (POINTER_TYPE_P (chrec_type (poly0)))
+ gcc_assert (chrec_type (poly1) == sizetype);
+ else
+ gcc_assert (chrec_type (poly0) == chrec_type (poly1));
gcc_assert (type == chrec_type (poly0));
/*
{a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
if (flow_loop_nested_p (loop0, loop1))
{
- if (code == PLUS_EXPR)
+ if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
return build_polynomial_chrec
(CHREC_VARIABLE (poly1),
chrec_fold_plus (type, poly0, CHREC_LEFT (poly1)),
if (flow_loop_nested_p (loop1, loop0))
{
- if (code == PLUS_EXPR)
+ if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
return build_polynomial_chrec
(CHREC_VARIABLE (poly0),
chrec_fold_plus (type, CHREC_LEFT (poly0), poly1),
do not belong to the same loop nest. */
gcc_assert (loop0 == loop1);
- if (code == PLUS_EXPR)
+ if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
{
left = chrec_fold_plus
(type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
right = chrec_fold_plus
- (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
+ (rtype, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
}
else
{
chrec_fold_plus_1 (enum tree_code code, tree type,
tree op0, tree op1)
{
+ tree op1_type = code == POINTER_PLUS_EXPR ? sizetype : type;
+
if (automatically_generated_chrec_p (op0)
|| automatically_generated_chrec_p (op1))
return chrec_fold_automatically_generated_operands (op0, op1);
return chrec_fold_plus_poly_poly (code, type, op0, op1);
default:
- if (code == PLUS_EXPR)
+ if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
return build_polynomial_chrec
(CHREC_VARIABLE (op0),
chrec_fold_plus (type, CHREC_LEFT (op0), op1),
switch (TREE_CODE (op1))
{
case POLYNOMIAL_CHREC:
- if (code == PLUS_EXPR)
+ if (code == PLUS_EXPR || code == POINTER_PLUS_EXPR)
return build_polynomial_chrec
(CHREC_VARIABLE (op1),
chrec_fold_plus (type, op0, CHREC_LEFT (op1)),
else if (size < PARAM_VALUE (PARAM_SCEV_MAX_EXPR_SIZE))
return fold_build2 (code, type,
fold_convert (type, op0),
- fold_convert (type, op1));
+ fold_convert (op1_type, op1));
else
return chrec_dont_know;
}
tree op0,
tree op1)
{
+ enum tree_code code;
if (automatically_generated_chrec_p (op0)
|| automatically_generated_chrec_p (op1))
return chrec_fold_automatically_generated_operands (op0, op1);
if (integer_zerop (op0))
- return op1;
+ return chrec_convert (type, op1, NULL);
if (integer_zerop (op1))
- return op0;
+ return chrec_convert (type, op0, NULL);
+
+ if (POINTER_TYPE_P (type))
+ code = POINTER_PLUS_EXPR;
+ else
+ code = PLUS_EXPR;
- return chrec_fold_plus_1 (PLUS_EXPR, type, op0, op1);
+ return chrec_fold_plus_1 (code, type, op0, op1);
}
/* Fold the subtraction of two chrecs. */
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
&& CHREC_VARIABLE (chrec) == var)
{
- arg0 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
- if (arg0 == chrec_dont_know)
+ arg1 = chrec_evaluate (var, CHREC_RIGHT (chrec), n, k + 1);
+ if (arg1 == 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,
+ arg0 = fold_build2 (MULT_EXPR, type,
CHREC_LEFT (chrec), binomial_n_k);
return chrec_fold_plus (type, arg0, arg1);
}
if (evolution_function_is_affine_p (chrec))
{
/* "{a, +, b} (x)" -> "a + b*x". */
- x = chrec_convert (type, x, NULL_TREE);
- res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
- if (!integer_zerop (CHREC_LEFT (chrec)))
- res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
+ x = chrec_convert_rhs (type, x, NULL);
+ 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)
{
struct loop *loop = get_loop (loop_num);
- gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
+ if (POINTER_TYPE_P (chrec_type (chrec)))
+ gcc_assert (sizetype == chrec_type (new_evol));
+ else
+ gcc_assert (chrec_type (chrec) == chrec_type (new_evol));
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
&& flow_loop_nested_p (loop, get_chrec_loop (chrec)))
/* Helper function for is_multivariate_chrec. */
static bool
-is_multivariate_chrec_rec (tree chrec, unsigned int rec_var)
+is_multivariate_chrec_rec (const_tree chrec, unsigned int rec_var)
{
if (chrec == NULL_TREE)
return false;
/* Determine whether the given chrec is multivariate or not. */
bool
-is_multivariate_chrec (tree chrec)
+is_multivariate_chrec (const_tree chrec)
{
if (chrec == NULL_TREE)
return false;
/* Determines whether the chrec contains symbolic names or not. */
bool
-chrec_contains_symbols (tree chrec)
+chrec_contains_symbols (const_tree chrec)
{
int i, n;
/* Determines whether the chrec contains undetermined coefficients. */
bool
-chrec_contains_undetermined (tree chrec)
+chrec_contains_undetermined (const_tree chrec)
{
int i, n;
the tree. */
bool
-tree_contains_chrecs (tree expr, int *size)
+tree_contains_chrecs (const_tree expr, int *size)
{
int i, n;
if (evolution_function_is_constant_p (chrec))
return true;
- if (TREE_CODE (chrec) == SSA_NAME
- && expr_invariant_in_loop_p (get_loop (loopnum), chrec))
+ if (TREE_CODE (chrec) == SSA_NAME
+ && (loopnum == 0
+ || expr_invariant_in_loop_p (get_loop (loopnum), chrec)))
return true;
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
bool
evolution_function_is_invariant_p (tree chrec, int loopnum)
{
- if (evolution_function_is_constant_p (chrec))
- return true;
-
- if (current_loops != NULL)
- return evolution_function_is_invariant_rec_p (chrec, loopnum);
-
- return false;
+ return evolution_function_is_invariant_rec_p (chrec, loopnum);
}
/* Determine whether the given tree is an affine multivariate
evolution. */
bool
-evolution_function_is_affine_multivariate_p (tree chrec, int loopnum)
+evolution_function_is_affine_multivariate_p (const_tree chrec, int loopnum)
{
if (chrec == NULL_TREE)
return false;
variables. */
bool
-evolution_function_is_univariate_p (tree chrec)
+evolution_function_is_univariate_p (const_tree chrec)
{
if (chrec == NULL_TREE)
return true;
arithmetics, even though it is a scalar type. */
static bool
-avoid_arithmetics_in_type_p (tree type)
+avoid_arithmetics_in_type_p (const_tree type)
{
/* Ada frontend uses subtypes -- an arithmetic cannot be directly performed
in the subtype, but a base type must be used, and the result then can
return false;
}
-static tree chrec_convert_1 (tree, tree, tree, bool);
+static tree chrec_convert_1 (tree, tree, gimple, bool);
/* Converts BASE and STEP of affine scev to TYPE. LOOP is the loop whose iv
the scev corresponds to. AT_STMT is the statement at that the scev is
bool
convert_affine_scev (struct loop *loop, tree type,
- tree *base, tree *step, tree at_stmt,
+ tree *base, tree *step, gimple at_stmt,
bool use_overflow_semantics)
{
tree ct = TREE_TYPE (*step);
bool enforce_overflow_semantics;
bool must_check_src_overflow, must_check_rslt_overflow;
tree new_base, new_step;
+ tree step_type = POINTER_TYPE_P (type) ? sizetype : type;
/* If we cannot perform arithmetic in TYPE, avoid creating an scev. */
if (avoid_arithmetics_in_type_p (type))
[100, +, 255] with values 100, 355, ...; the sign-extension is
performed by default when CT is signed. */
new_step = *step;
- if (TYPE_PRECISION (type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
+ if (TYPE_PRECISION (step_type) > TYPE_PRECISION (ct) && TYPE_UNSIGNED (ct))
new_step = chrec_convert_1 (signed_type_for (ct), new_step, at_stmt,
use_overflow_semantics);
- new_step = chrec_convert_1 (type, new_step, at_stmt, use_overflow_semantics);
+ new_step = chrec_convert_1 (step_type, new_step, at_stmt, use_overflow_semantics);
if (automatically_generated_chrec_p (new_base)
|| automatically_generated_chrec_p (new_step))
}
\f
+/* Convert CHREC for the right hand side of a CREC.
+ The increment for a pointer type is always sizetype. */
+tree
+chrec_convert_rhs (tree type, tree chrec, gimple at_stmt)
+{
+ if (POINTER_TYPE_P (type))
+ type = sizetype;
+ return chrec_convert (type, chrec, at_stmt);
+}
+
/* Convert CHREC to TYPE. When the analyzer knows the context in
which the CHREC is built, it sets AT_STMT to the statement that
contains the definition of the analyzed variable, otherwise the
*/
tree
-chrec_convert (tree type, tree chrec, tree at_stmt)
+chrec_convert (tree type, tree chrec, gimple at_stmt)
{
return chrec_convert_1 (type, chrec, at_stmt, true);
}
tests, but also to enforce that the result follows them. */
static tree
-chrec_convert_1 (tree type, tree chrec, tree at_stmt,
+chrec_convert_1 (tree type, tree chrec, gimple at_stmt,
bool use_overflow_semantics)
{
tree ct, res;
tree
chrec_convert_aggressive (tree type, tree chrec)
{
- tree inner_type, left, right, lc, rc;
+ tree inner_type, left, right, lc, rc, rtype;
if (automatically_generated_chrec_p (chrec)
|| TREE_CODE (chrec) != POLYNOMIAL_CHREC)
if (avoid_arithmetics_in_type_p (type))
return NULL_TREE;
+ rtype = POINTER_TYPE_P (type) ? sizetype : type;
+
left = CHREC_LEFT (chrec);
right = CHREC_RIGHT (chrec);
lc = chrec_convert_aggressive (type, left);
if (!lc)
- lc = chrec_convert (type, left, NULL_TREE);
- rc = chrec_convert_aggressive (type, right);
+ lc = chrec_convert (type, left, NULL);
+ rc = chrec_convert_aggressive (rtype, right);
if (!rc)
- rc = chrec_convert (type, right, NULL_TREE);
+ rc = chrec_convert (rtype, right, NULL);
return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
}
/* Returns true when CHREC0 == CHREC1. */
bool
-eq_evolutions_p (tree chrec0,
- tree chrec1)
+eq_evolutions_p (const_tree chrec0, const_tree chrec1)
{
if (chrec0 == NULL_TREE
|| chrec1 == NULL_TREE
which of these cases happens. */
enum ev_direction
-scev_direction (tree chrec)
+scev_direction (const_tree chrec)
{
- tree step;
+ const_tree step;
if (!evolution_function_is_affine_p (chrec))
return EV_DIR_UNKNOWN;
else
return EV_DIR_GROWS;
}
+
+/* Iterates over all the components of SCEV, and calls CBCK. */
+
+void
+for_each_scev_op (tree *scev, bool (*cbck) (tree *, void *), void *data)
+{
+ switch (TREE_CODE_LENGTH (TREE_CODE (*scev)))
+ {
+ case 3:
+ for_each_scev_op (&TREE_OPERAND (*scev, 2), cbck, 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);
+
+ default:
+ cbck (scev, data);
+ break;
+ }
+}
+
OSDN Git Service
