/* 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.
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)
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)
}
}
-/* 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 (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
- 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);
+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);
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.
/* 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;
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);
+ 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);
}
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
