/* Chains of recurrences.
- Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2003, 2004, 2005, 2006, 2007, 2008, 2009
+ Free Software Foundation, Inc.
Contributed by Sebastian Pop <pop@cri.ensmp.fr>
This file is part of GCC.
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);
}
return chrec_fold_automatically_generated_operands (op0, op1);
if (integer_zerop (op0))
- return chrec_convert (type, op1, NULL_TREE);
+ return chrec_convert (type, op1, NULL);
if (integer_zerop (op1))
- return chrec_convert (type, op0, NULL_TREE);
+ return chrec_convert (type, op0, NULL);
if (POINTER_TYPE_P (type))
code = POINTER_PLUS_EXPR;
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_rhs (type, x, NULL_TREE);
+ x = chrec_convert_rhs (type, x, NULL);
res = chrec_fold_multiply (TREE_TYPE (x), CHREC_RIGHT (chrec), x);
- if (!integer_zerop (CHREC_LEFT (chrec)))
- res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
+ res = chrec_fold_plus (type, CHREC_LEFT (chrec), res);
}
else if (TREE_CODE (chrec) != POLYNOMIAL_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)
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);
/* 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, tree at_stmt)
+chrec_convert_rhs (tree type, tree chrec, gimple at_stmt)
{
if (POINTER_TYPE_P (type))
type = sizetype;
*/
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;
right = CHREC_RIGHT (chrec);
lc = chrec_convert_aggressive (type, left);
if (!lc)
- lc = chrec_convert (type, left, NULL_TREE);
+ lc = chrec_convert (type, left, NULL);
rc = chrec_convert_aggressive (rtype, right);
if (!rc)
- rc = chrec_convert (rtype, 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;
+ }
+}
+
+/* Returns true when the operation can be part of a linear
+ expression. */
+
+static inline bool
+operator_is_linear (tree scev)
+{
+ switch (TREE_CODE (scev))
+ {
+ case INTEGER_CST:
+ case POLYNOMIAL_CHREC:
+ case PLUS_EXPR:
+ case POINTER_PLUS_EXPR:
+ case MULT_EXPR:
+ case MINUS_EXPR:
+ case NEGATE_EXPR:
+ case SSA_NAME:
+ case NON_LVALUE_EXPR:
+ CASE_CONVERT:
+ return true;
+
+ default:
+ return false;
+ }
+}
+
+/* Return true when SCEV is a linear expression. Linear expressions
+ can contain additions, substractions and multiplications.
+ Multiplications are restricted to constant scaling: "cst * x". */
+
+bool
+scev_is_linear_expression (tree scev)
+{
+ if (scev == NULL
+ || !operator_is_linear (scev))
+ return false;
+
+ if (TREE_CODE (scev) == MULT_EXPR)
+ return !(tree_contains_chrecs (TREE_OPERAND (scev, 0), NULL)
+ && tree_contains_chrecs (TREE_OPERAND (scev, 1), NULL));
+
+ switch (TREE_CODE_LENGTH (TREE_CODE (scev)))
+ {
+ case 3:
+ return scev_is_linear_expression (TREE_OPERAND (scev, 0))
+ && scev_is_linear_expression (TREE_OPERAND (scev, 1))
+ && scev_is_linear_expression (TREE_OPERAND (scev, 2));
+
+ 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));
+
+ case 0:
+ return true;
+
+ default:
+ return false;
+ }
+}
OSDN Git Service
