/* Chains of recurrences.
- Copyright (C) 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
+ 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.
return true;
if (TREE_CODE (chrec) == SSA_NAME
- && expr_invariant_in_loop_p (current_loops->parray[loopnum],
- chrec))
+ && 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 (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;
+
+ /* 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 (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);
+
+ 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. When the analyzer knows the context in
tree
chrec_convert (tree type, tree chrec, tree at_stmt)
{
+ 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 (evolution_function_is_affine_p (chrec))
- {
- tree base, step;
- bool dummy;
- struct loop *loop = current_loops->parray[CHREC_VARIABLE (chrec)];
-
- base = instantiate_parameters (loop, CHREC_LEFT (chrec));
- step = instantiate_parameters (loop, CHREC_RIGHT (chrec));
-
- /* Avoid conversion of (signed char) {(uchar)1, +, (uchar)1}_x
- when it is not possible to prove that the scev does not wrap.
- See PR22236, where a sequence 1, 2, ..., 255 has to be
- converted to signed char, but this would wrap:
- 1, 2, ..., 127, -128, ... The result should not be
- {(schar)1, +, (schar)1}_x, but instead, we should keep the
- conversion: (schar) {(uchar)1, +, (uchar)1}_x. */
- if (scev_probably_wraps_p (type, base, step, at_stmt, loop,
- &dummy, &dummy))
- goto failed_to_convert;
-
- step = convert_step (loop, type, base, step, at_stmt);
- if (!step)
- {
- failed_to_convert:;
- if (dump_file && (dump_flags & TDF_DETAILS))
- {
- fprintf (dump_file, "(failed conversion:");
- fprintf (dump_file, "\n type: ");
- print_generic_expr (dump_file, type, 0);
- fprintf (dump_file, "\n base: ");
- print_generic_expr (dump_file, base, 0);
- fprintf (dump_file, "\n step: ");
- print_generic_expr (dump_file, step, 0);
- fprintf (dump_file, "\n estimated_nb_iterations: ");
- print_generic_expr (dump_file, loop->estimated_nb_iterations, 0);
- fprintf (dump_file, "\n)\n");
- }
+ if (!evolution_function_is_affine_p (chrec))
+ goto keep_cast;
- return fold_convert (type, chrec);
- }
+ loop = get_chrec_loop (chrec);
+ base = CHREC_LEFT (chrec);
+ step = CHREC_RIGHT (chrec);
- return build_polynomial_chrec (CHREC_VARIABLE (chrec),
- chrec_convert (type, CHREC_LEFT (chrec),
- at_stmt),
- step);
- }
-
- if (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
- return chrec_dont_know;
+ 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_CONSTANT_OVERFLOW (res) = 0;
- TREE_OVERFLOW (res) = 0;
- }
+ 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
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;
+
left = CHREC_LEFT (chrec);
right = CHREC_RIGHT (chrec);
lc = chrec_convert_aggressive (type, left);
rc = chrec_convert_aggressive (type, right);
if (!rc)
rc = chrec_convert (type, right, NULL_TREE);
-
- /* Ada creates sub-types where TYPE_MIN_VALUE/TYPE_MAX_VALUE do not
- cover the entire range of values allowed by TYPE_PRECISION.
-
- We do not want to optimize away conversions to such types. Long
- term I'd rather see the Ada front-end fixed. */
- if (INTEGRAL_TYPE_P (type))
- {
- tree t;
-
- t = upper_bound_in_type (type, inner_type);
- if (! TYPE_MAX_VALUE (type)
- || ! operand_equal_p (TYPE_MAX_VALUE (type), t, 0))
- return NULL_TREE;
-
- t = lower_bound_in_type (type, inner_type);
- if (! TYPE_MIN_VALUE (type)
- || ! operand_equal_p (TYPE_MIN_VALUE (type), t, 0))
- return NULL_TREE;
- }
-
+
return build_polynomial_chrec (CHREC_VARIABLE (chrec), lc, rc);
}
}
}
+/* 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;
+}
OSDN Git Service
