/* Chains of recurrences.
- Copyright (C) 2003, 2004, 2005 Free Software Foundation, Inc.
- Contributed by Sebastian Pop <s.pop@laposte.net>
+ Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
+ Contributed by Sebastian Pop <pop@cri.ensmp.fr>
This file is part of GCC.
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, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA. */
+Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
+02110-1301, USA. */
/* This file implements operations on chains of recurrences. Chains
of recurrences are used for modeling evolution functions of scalar
#include "system.h"
#include "coretypes.h"
#include "tm.h"
-#include "errors.h"
#include "ggc.h"
#include "tree.h"
+#include "real.h"
#include "diagnostic.h"
-#include "varray.h"
+#include "cfgloop.h"
+#include "tree-flow.h"
#include "tree-chrec.h"
#include "tree-pass.h"
#include "params.h"
+#include "tree-scalar-evolution.h"
\f
gcc_assert (cst);
gcc_assert (TREE_CODE (poly) == POLYNOMIAL_CHREC);
gcc_assert (!is_not_constant_evolution (cst));
-
+ gcc_assert (type == chrec_type (poly));
+
switch (code)
{
case PLUS_EXPR:
tree poly1)
{
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);
+ 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}_1 + {c, +, d}_2 -> {{a, +, b}_1 + c, +, d}_2,
{a, +, b}_2 + {c, +, d}_1 -> {{c, +, d}_1 + a, +, b}_2,
{a, +, b}_x + {c, +, d}_x -> {a+c, +, b+d}_x. */
- if (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
+ 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)),
(CHREC_VARIABLE (poly1),
chrec_fold_minus (type, poly0, CHREC_LEFT (poly1)),
chrec_fold_multiply (type, CHREC_RIGHT (poly1),
- build_int_cst_type (type, -1)));
+ SCALAR_FLOAT_TYPE_P (type)
+ ? build_real (type, dconstm1)
+ : build_int_cst_type (type, -1)));
}
- if (CHREC_VARIABLE (poly0) > CHREC_VARIABLE (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),
chrec_fold_minus (type, CHREC_LEFT (poly0), poly1),
CHREC_RIGHT (poly0));
}
-
- if (code == PLUS_EXPR)
+
+ /* 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
(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
{
tree poly0,
tree poly1)
{
+ tree t0, t1, t2;
+ int var;
+ struct loop *loop0 = get_chrec_loop (poly0);
+ struct loop *loop1 = get_chrec_loop (poly1);
+
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));
+ 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 (CHREC_VARIABLE (poly0) < CHREC_VARIABLE (poly1))
+ if (flow_loop_nested_p (loop0, loop1))
/* poly0 is a constant wrt. poly1. */
return build_polynomial_chrec
(CHREC_VARIABLE (poly1),
chrec_fold_multiply (type, CHREC_LEFT (poly1), poly0),
CHREC_RIGHT (poly1));
- if (CHREC_VARIABLE (poly1) < CHREC_VARIABLE (poly0))
+ if (flow_loop_nested_p (loop1, loop0))
/* poly1 is a constant wrt. 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. */
- return
- build_polynomial_chrec
- (CHREC_VARIABLE (poly0),
- build_polynomial_chrec
- (CHREC_VARIABLE (poly0),
- /* "a*c". */
- chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1)),
-
- /* "a*d + b*c + b*d". */
- chrec_fold_plus
- (type, chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_RIGHT (poly1)),
-
- chrec_fold_plus
- (type,
- chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_LEFT (poly1)),
- chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1))))),
-
- /* "2*b*d". */
- chrec_fold_multiply
- (type, build_int_cst (NULL_TREE, 2),
- chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1))));
+ /* "a*c". */
+ t0 = chrec_fold_multiply (type, CHREC_LEFT (poly0), CHREC_LEFT (poly1));
+
+ /* "a*d + b*c + b*d". */
+ 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". */
+ t2 = chrec_fold_multiply (type, CHREC_RIGHT (poly0), CHREC_RIGHT (poly1));
+ t2 = chrec_fold_multiply (type, SCALAR_FLOAT_TYPE_P (type)
+ ? build_real (type, dconst2)
+ : build_int_cst (type, 2), t2);
+
+ var = CHREC_VARIABLE (poly0);
+ return build_polynomial_chrec (var, t0,
+ build_polynomial_chrec (var, t1, t2));
}
/* When the operands are automatically_generated_chrec_p, the fold has
/* Fold the addition of two chrecs. */
static tree
-chrec_fold_plus_1 (enum tree_code code,
- tree type,
- tree op0,
- tree op1)
+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)),
return build_polynomial_chrec
(CHREC_VARIABLE (op1),
chrec_fold_minus (type, op0, CHREC_LEFT (op1)),
- chrec_fold_multiply (type, CHREC_RIGHT (op1),
- build_int_cst_type (type, -1)));
+ chrec_fold_multiply (type, CHREC_RIGHT (op1),
+ SCALAR_FLOAT_TYPE_P (type)
+ ? build_real (type, dconstm1)
+ : build_int_cst_type (type, -1)));
default:
{
&& 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);
+ return fold_build2 (code, type,
+ fold_convert (type, op0),
+ 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_TREE);
if (integer_zerop (op1))
- return op0;
+ return chrec_convert (type, op0, NULL_TREE);
+
+ 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. */
tree op0,
tree op1)
{
+ if (automatically_generated_chrec_p (op0)
+ || automatically_generated_chrec_p (op1))
+ return chrec_fold_automatically_generated_operands (op0, op1);
+
if (integer_zerop (op1))
return op0;
if (integer_onep (op1))
return op0;
if (integer_zerop (op1))
- return build_int_cst_type (type, 0);
+ return build_int_cst (type, 0);
return build_polynomial_chrec
(CHREC_VARIABLE (op0),
return op1;
if (integer_zerop (op0))
- return build_int_cst_type (type, 0);
+ return build_int_cst (type, 0);
switch (TREE_CODE (op1))
{
if (integer_onep (op1))
return op0;
if (integer_zerop (op1))
- return build_int_cst_type (type, 0);
+ return build_int_cst (type, 0);
return fold_build2 (MULT_EXPR, type, op0, op1);
}
}
{
tree arg0, arg1, binomial_n_k;
tree type = TREE_TYPE (chrec);
+ struct loop *var_loop = get_loop (var);
while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
- && CHREC_VARIABLE (chrec) > var)
+ && flow_loop_nested_p (var_loop, get_chrec_loop (chrec)))
chrec = CHREC_LEFT (chrec);
if (TREE_CODE (chrec) == POLYNOMIAL_CHREC
/* When the symbols are defined in an outer loop, it is possible
to symbolically compute the apply, since the symbols are
constants with respect to the varying loop. */
- || chrec_contains_symbols_defined_in_loop (chrec, var)
- || chrec_contains_symbols (x))
+ || 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");
+ if (TREE_CODE (x) == INTEGER_CST && SCALAR_FLOAT_TYPE_P (type))
+ x = build_real_from_int_cst (type, x);
+
if (evolution_function_is_affine_p (chrec))
{
/* "{a, +, b} (x)" -> "a + b*x". */
- if (TREE_CODE (CHREC_LEFT (chrec)) == INTEGER_CST
- && integer_zerop (CHREC_LEFT (chrec)))
- res = chrec_fold_multiply (type, CHREC_RIGHT (chrec), x);
-
- else
- res = chrec_fold_plus (type, CHREC_LEFT (chrec),
- chrec_fold_multiply (type,
- CHREC_RIGHT (chrec), x));
+ x = chrec_convert_rhs (type, x, NULL_TREE);
+ 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);
}
else if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
&& tree_int_cst_sgn (x) == 1)
/* testsuite/.../ssa-chrec-38.c. */
res = chrec_evaluate (var, chrec, x, 0);
-
else
res = chrec_dont_know;
{
if (automatically_generated_chrec_p (chrec))
return chrec;
-
+
+ gcc_assert (chrec_type (chrec) == chrec_type (init_cond));
+
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
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:
- if (CHREC_VARIABLE (chrec) == loop_num)
+ 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),
CHREC_RIGHT (chrec));
- else if (CHREC_VARIABLE (chrec) < loop_num)
+ else if (flow_loop_nested_p (chloop, loop))
/* There is no evolution in this loop. */
return initial_condition (chrec);
else
- return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
- loop_num);
+ {
+ gcc_assert (flow_loop_nested_p (loop, chloop));
+ return hide_evolution_in_other_loops_than_loop (CHREC_LEFT (chrec),
+ loop_num);
+ }
default:
return chrec;
bool right)
{
tree component;
+ struct loop *loop = get_loop (loop_num), *chloop;
if (automatically_generated_chrec_p (chrec))
return chrec;
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
- if (CHREC_VARIABLE (chrec) == loop_num)
+ chloop = get_chrec_loop (chrec);
+
+ if (chloop == loop)
{
if (right)
component = CHREC_RIGHT (chrec);
component);
}
- else if (CHREC_VARIABLE (chrec) < loop_num)
+ else if (flow_loop_nested_p (chloop, loop))
/* There is no evolution part in this loop. */
return NULL_TREE;
else
- return chrec_component_in_loop_num (CHREC_LEFT (chrec),
- loop_num,
- right);
+ {
+ gcc_assert (flow_loop_nested_p (loop, chloop));
+ return chrec_component_in_loop_num (CHREC_LEFT (chrec),
+ loop_num,
+ right);
+ }
default:
if (right)
tree chrec,
tree new_evol)
{
+ struct loop *loop = get_loop (loop_num);
+
+ 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
- && CHREC_VARIABLE (chrec) > loop_num)
- return build2
- (TREE_CODE (chrec),
- build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
- reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec), new_evol),
- reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec), new_evol));
-
+ && flow_loop_nested_p (loop, get_chrec_loop (chrec)))
+ {
+ tree left = reset_evolution_in_loop (loop_num, CHREC_LEFT (chrec),
+ new_evol);
+ tree right = reset_evolution_in_loop (loop_num, CHREC_RIGHT (chrec),
+ new_evol);
+ return build3 (POLYNOMIAL_CHREC, TREE_TYPE (left),
+ build_int_cst (NULL_TREE, CHREC_VARIABLE (chrec)),
+ left, right);
+ }
+
while (TREE_CODE (chrec) == POLYNOMIAL_CHREC
&& CHREC_VARIABLE (chrec) == loop_num)
chrec = CHREC_LEFT (chrec);
if (chrec2 == chrec_not_analyzed_yet)
return chrec1;
- if (operand_equal_p (chrec1, chrec2, 0))
+ if (eq_evolutions_p (chrec1, chrec2))
return chrec1;
return chrec_dont_know;
bool
chrec_contains_symbols (tree chrec)
{
+ int i, n;
+
if (chrec == NULL_TREE)
return false;
|| TREE_CODE (chrec) == RESULT_DECL
|| TREE_CODE (chrec) == FIELD_DECL)
return true;
-
- switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
- {
- case 3:
- if (chrec_contains_symbols (TREE_OPERAND (chrec, 2)))
- return true;
-
- case 2:
- if (chrec_contains_symbols (TREE_OPERAND (chrec, 1)))
- return true;
-
- case 1:
- if (chrec_contains_symbols (TREE_OPERAND (chrec, 0)))
- return true;
-
- default:
- return false;
- }
+
+ n = TREE_OPERAND_LENGTH (chrec);
+ for (i = 0; i < n; i++)
+ if (chrec_contains_symbols (TREE_OPERAND (chrec, i)))
+ return true;
+ return false;
}
/* Determines whether the chrec contains undetermined coefficients. */
bool
chrec_contains_undetermined (tree chrec)
{
- if (chrec == chrec_dont_know
- || chrec == chrec_not_analyzed_yet
- || chrec == NULL_TREE)
+ int i, n;
+
+ if (chrec == chrec_dont_know)
return true;
-
- switch (TREE_CODE_LENGTH (TREE_CODE (chrec)))
- {
- case 3:
- if (chrec_contains_undetermined (TREE_OPERAND (chrec, 2)))
- return true;
-
- case 2:
- if (chrec_contains_undetermined (TREE_OPERAND (chrec, 1)))
- return true;
-
- case 1:
- if (chrec_contains_undetermined (TREE_OPERAND (chrec, 0)))
- return true;
-
- default:
- return false;
- }
+
+ if (chrec == NULL_TREE)
+ return false;
+
+ n = TREE_OPERAND_LENGTH (chrec);
+ for (i = 0; i < n; i++)
+ if (chrec_contains_undetermined (TREE_OPERAND (chrec, i)))
+ return true;
+ return false;
}
/* Determines whether the tree EXPR contains chrecs, and increment
bool
tree_contains_chrecs (tree expr, int *size)
{
+ int i, n;
+
if (expr == NULL_TREE)
return false;
if (tree_is_chrec (expr))
return true;
- switch (TREE_CODE_LENGTH (TREE_CODE (expr)))
+ n = TREE_OPERAND_LENGTH (expr);
+ for (i = 0; i < n; i++)
+ if (tree_contains_chrecs (TREE_OPERAND (expr, i), size))
+ return true;
+ return false;
+}
+
+/* Recursive helper function. */
+
+static bool
+evolution_function_is_invariant_rec_p (tree chrec, int loopnum)
+{
+ if (evolution_function_is_constant_p (chrec))
+ return true;
+
+ if (TREE_CODE (chrec) == SSA_NAME
+ && expr_invariant_in_loop_p (get_loop (loopnum), chrec))
+ return true;
+
+ if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
+ {
+ if (CHREC_VARIABLE (chrec) == (unsigned) loopnum
+ || !evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec),
+ loopnum)
+ || !evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec),
+ loopnum))
+ return false;
+ return true;
+ }
+
+ switch (TREE_OPERAND_LENGTH (chrec))
{
- case 3:
- if (tree_contains_chrecs (TREE_OPERAND (expr, 2), size))
- return true;
-
case 2:
- if (tree_contains_chrecs (TREE_OPERAND (expr, 1), size))
- return true;
+ if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 1),
+ loopnum))
+ return false;
case 1:
- if (tree_contains_chrecs (TREE_OPERAND (expr, 0), size))
- return true;
-
+ if (!evolution_function_is_invariant_rec_p (TREE_OPERAND (chrec, 0),
+ loopnum))
+ return false;
+ return true;
+
default:
return false;
}
+
+ return false;
+}
+
+/* Return true if CHREC is invariant in loop LOOPNUM, false otherwise. */
+
+bool
+evolution_function_is_invariant_p (tree chrec, int loopnum)
+{
+ 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)
+evolution_function_is_affine_multivariate_p (tree chrec, int loopnum)
{
if (chrec == NULL_TREE)
return false;
switch (TREE_CODE (chrec))
{
case POLYNOMIAL_CHREC:
- if (evolution_function_is_constant_p (CHREC_LEFT (chrec)))
+ if (evolution_function_is_invariant_rec_p (CHREC_LEFT (chrec), loopnum))
{
- if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
+ if (evolution_function_is_invariant_rec_p (CHREC_RIGHT (chrec), loopnum))
return true;
else
{
&& CHREC_VARIABLE (CHREC_RIGHT (chrec))
!= CHREC_VARIABLE (chrec)
&& evolution_function_is_affine_multivariate_p
- (CHREC_RIGHT (chrec)))
+ (CHREC_RIGHT (chrec), loopnum))
return true;
else
return false;
}
else
{
- if (evolution_function_is_constant_p (CHREC_RIGHT (chrec))
+ 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
- (CHREC_LEFT (chrec)))
+ (CHREC_LEFT (chrec), loopnum))
return true;
else
return false;
}
}
+/* Returns true if TYPE is a type in that we cannot directly perform
+ arithmetics, even though it is a scalar type. */
+
+static bool
+avoid_arithmetics_in_type_p (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
+ be casted to the subtype. */
+ if (TREE_CODE (type) == INTEGER_TYPE && TREE_TYPE (type) != NULL_TREE)
+ return true;
+
+ return false;
+}
+
+static tree chrec_convert_1 (tree, tree, tree, 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
+ evaluated. 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. Returns true if the
+ conversion succeeded, false otherwise. */
+
+bool
+convert_affine_scev (struct loop *loop, tree type,
+ tree *base, tree *step, tree 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))
+ return false;
+
+ /* 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
+ are 254, 255, 0, 1, ..., but those on the right side are
+ 254, 255, 256, 257, ...
+ 2) In case that we must also preserve the fact that signed ivs do not
+ overflow, we must additionally check that the new iv does not wrap.
+ For example, unsigned char [125, +, 1] casted to signed char could
+ become a wrapping variable with values 125, 126, 127, -128, -127, ...,
+ which would confuse optimizers that assume that this does not
+ happen. */
+ must_check_src_overflow = TYPE_PRECISION (ct) < TYPE_PRECISION (type);
+
+ enforce_overflow_semantics = (use_overflow_semantics
+ && nowrap_type_p (type));
+ if (enforce_overflow_semantics)
+ {
+ /* We can avoid checking whether the result overflows in the following
+ cases:
+
+ -- must_check_src_overflow is true, and the range of TYPE is superset
+ of the range of CT -- i.e., in all cases except if CT signed and
+ TYPE unsigned.
+ -- both CT and TYPE have the same precision and signedness, and we
+ verify instead that the source does not overflow (this may be
+ easier than verifying it for the result, as we may use the
+ information about the semantics of overflow in CT). */
+ if (must_check_src_overflow)
+ {
+ if (TYPE_UNSIGNED (type) && !TYPE_UNSIGNED (ct))
+ must_check_rslt_overflow = true;
+ else
+ must_check_rslt_overflow = false;
+ }
+ else if (TYPE_UNSIGNED (ct) == TYPE_UNSIGNED (type)
+ && TYPE_PRECISION (ct) == TYPE_PRECISION (type))
+ {
+ must_check_rslt_overflow = false;
+ must_check_src_overflow = true;
+ }
+ else
+ must_check_rslt_overflow = true;
+ }
+ else
+ must_check_rslt_overflow = false;
+
+ if (must_check_src_overflow
+ && scev_probably_wraps_p (*base, *step, at_stmt, loop,
+ use_overflow_semantics))
+ return false;
+
+ new_base = chrec_convert_1 (type, *base, at_stmt,
+ use_overflow_semantics);
+ /* The step must be sign extended, regardless of the signedness
+ 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
+ performed by default when CT is signed. */
+ new_step = *step;
+ 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 (step_type, new_step, at_stmt, use_overflow_semantics);
+
+ if (automatically_generated_chrec_p (new_base)
+ || automatically_generated_chrec_p (new_step))
+ return false;
+
+ if (must_check_rslt_overflow
+ /* Note that in this case we cannot use the fact that signed variables
+ do not overflow, as this is what we are verifying for the new iv. */
+ && scev_probably_wraps_p (new_base, new_step, at_stmt, loop, false))
+ return false;
+
+ *base = new_base;
+ *step = new_step;
+ return true;
+}
\f
-/* 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:
+/* 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)
+{
+ 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
+ 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.
+
+ The following 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}
*/
tree
-chrec_convert (tree type,
- tree chrec)
+chrec_convert (tree type, tree chrec, tree at_stmt)
{
- tree ct;
-
+ return chrec_convert_1 (type, chrec, at_stmt, true);
+}
+
+/* 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
+ 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
+chrec_convert_1 (tree type, tree chrec, tree at_stmt,
+ bool use_overflow_semantics)
+{
+ tree ct, res;
+ tree base, step;
+ struct loop *loop;
+
if (automatically_generated_chrec_p (chrec))
return chrec;
if (ct == type)
return chrec;
- if (TYPE_PRECISION (ct) < TYPE_PRECISION (type))
- return count_ev_in_wider_type (type, chrec);
+ if (!evolution_function_is_affine_p (chrec))
+ goto keep_cast;
+
+ loop = get_chrec_loop (chrec);
+ base = CHREC_LEFT (chrec);
+ step = CHREC_RIGHT (chrec);
+
+ if (convert_affine_scev (loop, type, &base, &step, at_stmt,
+ use_overflow_semantics))
+ return build_polynomial_chrec (loop->num, base, step);
+
+ /* If we cannot propagate the cast inside the chrec, just keep the cast. */
+keep_cast:
+ res = fold_convert (type, chrec);
+
+ /* Don't propagate overflows. */
+ if (CONSTANT_CLASS_P (res))
+ TREE_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;
- switch (TREE_CODE (chrec))
- {
- case POLYNOMIAL_CHREC:
- return build_polynomial_chrec (CHREC_VARIABLE (chrec),
- chrec_convert (type,
- CHREC_LEFT (chrec)),
- chrec_convert (type,
- CHREC_RIGHT (chrec)));
+ return res;
+}
- default:
- {
- tree res = fold_convert (type, chrec);
+/* Convert CHREC to TYPE, without regard to signed overflows. Returns the new
+ chrec if something else than what chrec_convert would do happens, NULL_TREE
+ otherwise. */
- /* Don't propagate overflows. */
- if (CONSTANT_CLASS_P (res))
- {
- TREE_CONSTANT_OVERFLOW (res) = 0;
- TREE_OVERFLOW (res) = 0;
- }
+tree
+chrec_convert_aggressive (tree type, tree chrec)
+{
+ tree inner_type, left, right, lc, rc, rtype;
- /* 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;
- }
- }
+ if (automatically_generated_chrec_p (chrec)
+ || TREE_CODE (chrec) != POLYNOMIAL_CHREC)
+ return NULL_TREE;
+
+ inner_type = TREE_TYPE (chrec);
+ if (TYPE_PRECISION (type) > TYPE_PRECISION (inner_type))
+ return NULL_TREE;
+
+ /* If we cannot perform arithmetic in TYPE, avoid creating an scev. */
+ 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 (rtype, right);
+ if (!rc)
+ rc = chrec_convert (rtype, right, NULL_TREE);
+
+ return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
}
-/* Returns the type of the chrec. */
+/* Returns true when CHREC0 == CHREC1. */
-tree
-chrec_type (tree chrec)
+bool
+eq_evolutions_p (tree chrec0,
+ tree chrec1)
{
- if (automatically_generated_chrec_p (chrec))
- return NULL_TREE;
-
- return TREE_TYPE (chrec);
+ if (chrec0 == NULL_TREE
+ || chrec1 == NULL_TREE
+ || TREE_CODE (chrec0) != TREE_CODE (chrec1))
+ return false;
+
+ if (chrec0 == chrec1)
+ return true;
+
+ switch (TREE_CODE (chrec0))
+ {
+ case INTEGER_CST:
+ return operand_equal_p (chrec0, chrec1, 0);
+
+ case POLYNOMIAL_CHREC:
+ return (CHREC_VARIABLE (chrec0) == CHREC_VARIABLE (chrec1)
+ && eq_evolutions_p (CHREC_LEFT (chrec0), CHREC_LEFT (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),
+ EV_DECREASES if it decreases, and EV_UNKNOWN if we cannot determine
+ which of these cases happens. */
+
+enum ev_direction
+scev_direction (tree chrec)
+{
+ tree step;
+
+ if (!evolution_function_is_affine_p (chrec))
+ return EV_DIR_UNKNOWN;
+
+ step = CHREC_RIGHT (chrec);
+ if (TREE_CODE (step) != INTEGER_CST)
+ return EV_DIR_UNKNOWN;
+
+ if (tree_int_cst_sign_bit (step))
+ return EV_DIR_DECREASES;
+ else
+ return EV_DIR_GROWS;
}