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)
+the Free Software Foundation; either version 3, or (at your option)
any later version.
GCC is distributed in the hope that it will be useful,
GNU General Public License 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/>. */
#include "config.h"
#include "system.h"
static int compare_values_warnv (tree val1, tree val2, bool *);
static void vrp_meet (value_range_t *, value_range_t *);
static tree vrp_evaluate_conditional_warnv (tree, bool, bool *);
+static tree vrp_evaluate_conditional_warnv_with_ops (enum tree_code,
+ tree, tree, bool, bool *);
/* Location information for ASSERT_EXPRs. Each instance of this
structure describes an ASSERT_EXPR for an SSA name. Since a single
/* Value being compared against. */
tree val;
+ /* Expression to compare. */
+ tree expr;
+
/* Next node in the linked list. */
struct assert_locus_d *next;
};
node. */
static int *vr_phi_edge_counts;
+typedef struct {
+ tree stmt;
+ tree vec;
+} switch_update;
+
+static VEC (edge, heap) *to_remove_edges;
+DEF_VEC_O(switch_update);
+DEF_VEC_ALLOC_O(switch_update, heap);
+static VEC (switch_update, heap) *to_update_switch_stmts;
+
+
+/* Return the maximum value for TYPEs base type. */
+
+static inline tree
+vrp_val_max (const_tree type)
+{
+ if (!INTEGRAL_TYPE_P (type))
+ return NULL_TREE;
+
+ /* For integer sub-types the values for the base type are relevant. */
+ if (TREE_TYPE (type))
+ type = TREE_TYPE (type);
+
+ return TYPE_MAX_VALUE (type);
+}
+
+/* Return the minimum value for TYPEs base type. */
+
+static inline tree
+vrp_val_min (const_tree type)
+{
+ if (!INTEGRAL_TYPE_P (type))
+ return NULL_TREE;
+
+ /* For integer sub-types the values for the base type are relevant. */
+ if (TREE_TYPE (type))
+ type = TREE_TYPE (type);
+
+ return TYPE_MIN_VALUE (type);
+}
+
+/* Return whether VAL is equal to the maximum value of its type. This
+ will be true for a positive overflow infinity. We can't do a
+ simple equality comparison with TYPE_MAX_VALUE because C typedefs
+ and Ada subtypes can produce types whose TYPE_MAX_VALUE is not ==
+ to the integer constant with the same value in the type. */
+
+static inline bool
+vrp_val_is_max (const_tree val)
+{
+ tree type_max = vrp_val_max (TREE_TYPE (val));
+ return (val == type_max
+ || (type_max != NULL_TREE
+ && operand_equal_p (val, type_max, 0)));
+}
+
+/* Return whether VAL is equal to the minimum value of its type. This
+ will be true for a negative overflow infinity. */
+
+static inline bool
+vrp_val_is_min (const_tree val)
+{
+ tree type_min = vrp_val_min (TREE_TYPE (val));
+ return (val == type_min
+ || (type_min != NULL_TREE
+ && operand_equal_p (val, type_min, 0)));
+}
+
/* Return whether TYPE should use an overflow infinity distinct from
TYPE_{MIN,MAX}_VALUE. We use an overflow infinity value to
TYPE_{MIN,MAX}_VALUE. */
static inline bool
-needs_overflow_infinity (tree type)
+needs_overflow_infinity (const_tree type)
{
- return INTEGRAL_TYPE_P (type) && !TYPE_OVERFLOW_WRAPS (type);
+ return (INTEGRAL_TYPE_P (type)
+ && !TYPE_OVERFLOW_WRAPS (type)
+ /* Integer sub-types never overflow as they are never
+ operands of arithmetic operators. */
+ && !(TREE_TYPE (type) && TREE_TYPE (type) != type));
}
/* Return whether TYPE can support our overflow infinity
VARYING. */
static inline bool
-supports_overflow_infinity (tree type)
+supports_overflow_infinity (const_tree type)
{
+ tree min = vrp_val_min (type), max = vrp_val_max (type);
#ifdef ENABLE_CHECKING
gcc_assert (needs_overflow_infinity (type));
#endif
- return (TYPE_MIN_VALUE (type) != NULL_TREE
- && CONSTANT_CLASS_P (TYPE_MIN_VALUE (type))
- && TYPE_MAX_VALUE (type) != NULL_TREE
- && CONSTANT_CLASS_P (TYPE_MAX_VALUE (type)));
+ return (min != NULL_TREE
+ && CONSTANT_CLASS_P (min)
+ && max != NULL_TREE
+ && CONSTANT_CLASS_P (max));
}
/* VAL is the maximum or minimum value of a type. Return a
#ifdef ENABLE_CHECKING
gcc_assert (supports_overflow_infinity (type));
#endif
- return make_overflow_infinity (TYPE_MIN_VALUE (type));
+ return make_overflow_infinity (vrp_val_min (type));
}
/* Return a positive overflow infinity for TYPE. */
#ifdef ENABLE_CHECKING
gcc_assert (supports_overflow_infinity (type));
#endif
- return make_overflow_infinity (TYPE_MAX_VALUE (type));
+ return make_overflow_infinity (vrp_val_max (type));
}
/* Return whether VAL is a negative overflow infinity. */
static inline bool
-is_negative_overflow_infinity (tree val)
+is_negative_overflow_infinity (const_tree val)
{
return (needs_overflow_infinity (TREE_TYPE (val))
&& CONSTANT_CLASS_P (val)
&& TREE_OVERFLOW (val)
- && operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0));
+ && vrp_val_is_min (val));
}
/* Return whether VAL is a positive overflow infinity. */
static inline bool
-is_positive_overflow_infinity (tree val)
+is_positive_overflow_infinity (const_tree val)
{
return (needs_overflow_infinity (TREE_TYPE (val))
&& CONSTANT_CLASS_P (val)
&& TREE_OVERFLOW (val)
- && operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0));
+ && vrp_val_is_max (val));
}
/* Return whether VAL is a positive or negative overflow infinity. */
static inline bool
-is_overflow_infinity (tree val)
+is_overflow_infinity (const_tree val)
{
return (needs_overflow_infinity (TREE_TYPE (val))
&& CONSTANT_CLASS_P (val)
&& TREE_OVERFLOW (val)
- && (operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0)
- || operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0)));
+ && (vrp_val_is_min (val) || vrp_val_is_max (val)));
}
/* If VAL is now an overflow infinity, return VAL. Otherwise, return
if (!is_overflow_infinity (val))
return val;
- if (operand_equal_p (val, TYPE_MAX_VALUE (TREE_TYPE (val)), 0))
- return TYPE_MAX_VALUE (TREE_TYPE (val));
+ if (vrp_val_is_max (val))
+ return vrp_val_max (TREE_TYPE (val));
else
{
#ifdef ENABLE_CHECKING
- gcc_assert (operand_equal_p (val, TYPE_MIN_VALUE (TREE_TYPE (val)), 0));
+ gcc_assert (vrp_val_is_min (val));
#endif
- return TYPE_MIN_VALUE (TREE_TYPE (val));
+ return vrp_val_min (TREE_TYPE (val));
}
}
-/* Return whether VAL is equal to the maximum value of its type. This
- will be true for a positive overflow infinity. We can't do a
- simple equality comparison with TYPE_MAX_VALUE because C typedefs
- and Ada subtypes can produce types whose TYPE_MAX_VALUE is not ==
- to the integer constant with the same value in the type. */
-
-static inline bool
-vrp_val_is_max (tree val)
-{
- tree type_max = TYPE_MAX_VALUE (TREE_TYPE (val));
-
- return (val == type_max
- || (type_max != NULL_TREE
- && operand_equal_p (val, type_max, 0)));
-}
-
-/* Return whether VAL is equal to the minimum value of its type. This
- will be true for a negative overflow infinity. */
-
-static inline bool
-vrp_val_is_min (tree val)
-{
- tree type_min = TYPE_MIN_VALUE (TREE_TYPE (val));
-
- return (val == type_min
- || (type_min != NULL_TREE
- && operand_equal_p (val, type_min, 0)));
-}
-
-
/* Return true if ARG is marked with the nonnull attribute in the
current function signature. */
static bool
-nonnull_arg_p (tree arg)
+nonnull_arg_p (const_tree arg)
{
tree t, attrs, fntype;
unsigned HOST_WIDE_INT arg_num;
}
+/* Set value range VR to VR_VARYING. */
+
+static inline void
+set_value_range_to_varying (value_range_t *vr)
+{
+ vr->type = VR_VARYING;
+ vr->min = vr->max = NULL_TREE;
+ if (vr->equiv)
+ bitmap_clear (vr->equiv);
+}
+
+
/* Set value range VR to {T, MIN, MAX, EQUIV}. */
static void
}
-/* Copy value range FROM into value range TO. */
+/* Set value range VR to the canonical form of {T, MIN, MAX, EQUIV}.
+ This means adjusting T, MIN and MAX representing the case of a
+ wrapping range with MAX < MIN covering [MIN, type_max] U [type_min, MAX]
+ as anti-rage ~[MAX+1, MIN-1]. Likewise for wrapping anti-ranges.
+ In corner cases where MAX+1 or MIN-1 wraps this will fall back
+ to varying.
+ This routine exists to ease canonicalization in the case where we
+ extract ranges from var + CST op limit. */
-static inline void
-copy_value_range (value_range_t *to, value_range_t *from)
+static void
+set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t,
+ tree min, tree max, bitmap equiv)
{
- set_value_range (to, from->type, from->min, from->max, from->equiv);
-}
+ /* Nothing to canonicalize for symbolic or unknown or varying ranges. */
+ if ((t != VR_RANGE
+ && t != VR_ANTI_RANGE)
+ || TREE_CODE (min) != INTEGER_CST
+ || TREE_CODE (max) != INTEGER_CST)
+ {
+ set_value_range (vr, t, min, max, equiv);
+ return;
+ }
+ /* Wrong order for min and max, to swap them and the VR type we need
+ to adjust them. */
+ if (tree_int_cst_lt (max, min))
+ {
+ tree one = build_int_cst (TREE_TYPE (min), 1);
+ tree tmp = int_const_binop (PLUS_EXPR, max, one, 0);
+ max = int_const_binop (MINUS_EXPR, min, one, 0);
+ min = tmp;
-/* Set value range VR to VR_VARYING. */
+ /* There's one corner case, if we had [C+1, C] before we now have
+ that again. But this represents an empty value range, so drop
+ to varying in this case. */
+ if (tree_int_cst_lt (max, min))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
+ t = t == VR_RANGE ? VR_ANTI_RANGE : VR_RANGE;
+ }
+
+ /* Anti-ranges that can be represented as ranges should be so. */
+ if (t == VR_ANTI_RANGE)
+ {
+ bool is_min = vrp_val_is_min (min);
+ bool is_max = vrp_val_is_max (max);
+
+ if (is_min && is_max)
+ {
+ /* We cannot deal with empty ranges, drop to varying. */
+ set_value_range_to_varying (vr);
+ return;
+ }
+ else if (is_min
+ /* As a special exception preserve non-null ranges. */
+ && !(TYPE_UNSIGNED (TREE_TYPE (min))
+ && integer_zerop (max)))
+ {
+ tree one = build_int_cst (TREE_TYPE (max), 1);
+ min = int_const_binop (PLUS_EXPR, max, one, 0);
+ max = vrp_val_max (TREE_TYPE (max));
+ t = VR_RANGE;
+ }
+ else if (is_max)
+ {
+ tree one = build_int_cst (TREE_TYPE (min), 1);
+ max = int_const_binop (MINUS_EXPR, min, one, 0);
+ min = vrp_val_min (TREE_TYPE (min));
+ t = VR_RANGE;
+ }
+ }
+
+ set_value_range (vr, t, min, max, equiv);
+}
+
+/* Copy value range FROM into value range TO. */
static inline void
-set_value_range_to_varying (value_range_t *vr)
+copy_value_range (value_range_t *to, value_range_t *from)
{
- vr->type = VR_VARYING;
- vr->min = vr->max = NULL_TREE;
- if (vr->equiv)
- bitmap_clear (vr->equiv);
+ set_value_range (to, from->type, from->min, from->max, from->equiv);
}
/* Set value range VR to a single value. This function is only called
return NULL. Otherwise create an empty range if none existed for VAR. */
static value_range_t *
-get_value_range (tree var)
+get_value_range (const_tree var)
{
value_range_t *vr;
tree sym;
/* Return true, if VAL1 and VAL2 are equal values for VRP purposes. */
static inline bool
-vrp_operand_equal_p (tree val1, tree val2)
+vrp_operand_equal_p (const_tree val1, const_tree val2)
{
if (val1 == val2)
return true;
/* Return true, if the bitmaps B1 and B2 are equal. */
static inline bool
-vrp_bitmap_equal_p (bitmap b1, bitmap b2)
+vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
{
return (b1 == b2
|| (b1 && b2
is the range object associated with another SSA name. */
static inline bool
-update_value_range (tree var, value_range_t *new_vr)
+update_value_range (const_tree var, value_range_t *new_vr)
{
value_range_t *old_vr;
bool is_new;
point where equivalence processing can be turned on/off. */
static void
-add_equivalence (bitmap *equiv, tree var)
+add_equivalence (bitmap *equiv, const_tree var)
{
unsigned ver = SSA_NAME_VERSION (var);
value_range_t *vr = vr_value[ver];
fold_undefer_and_ignore_overflow_warnings ();
- if (!tcmp)
+ if (!tcmp
+ || TREE_CODE (tcmp) != INTEGER_CST)
return -2;
if (!integer_zerop (tcmp))
|| TREE_CODE (val2) != INTEGER_CST)
{
t = fold_binary_to_constant (NE_EXPR, boolean_type_node, val1, val2);
- if (t && tree_expr_nonzero_p (t))
+ if (t && integer_onep (t))
return 2;
}
false otherwise or if no value range information is available. */
bool
-ssa_name_nonnegative_p (tree t)
+ssa_name_nonnegative_p (const_tree t)
{
value_range_t *vr = get_value_range (t);
false otherwise or if no value range information is available. */
bool
-ssa_name_nonzero_p (tree t)
+ssa_name_nonzero_p (const_tree t)
{
value_range_t *vr = get_value_range (t);
gcc_assert (COMPARISON_CLASS_P (cond));
/* Find VAR in the ASSERT_EXPR conditional. */
- if (var == TREE_OPERAND (cond, 0))
+ if (var == TREE_OPERAND (cond, 0)
+ || TREE_CODE (TREE_OPERAND (cond, 0)) == PLUS_EXPR
+ || TREE_CODE (TREE_OPERAND (cond, 0)) == NOP_EXPR)
{
/* If the predicate is of the form VAR COMP LIMIT, then we just
take LIMIT from the RHS and use the same comparison code. */
- limit = TREE_OPERAND (cond, 1);
cond_code = TREE_CODE (cond);
+ limit = TREE_OPERAND (cond, 1);
+ cond = TREE_OPERAND (cond, 0);
}
else
{
/* If the predicate is of the form LIMIT COMP VAR, then we need
to flip around the comparison code to create the proper range
for VAR. */
- limit = TREE_OPERAND (cond, 0);
cond_code = swap_tree_comparison (TREE_CODE (cond));
+ limit = TREE_OPERAND (cond, 0);
+ cond = TREE_OPERAND (cond, 1);
}
limit = avoid_overflow_infinity (limit);
instance, ASSERT_EXPR <x_2, x_2 <= b_4>. If b_4 is ~[2, 10],
then b_4 takes on the ranges [-INF, 1] and [11, +INF]. There is
no single range for x_2 that could describe LE_EXPR, so we might
- as well build the range [b_4, +INF] for it. */
- if (cond_code == EQ_EXPR)
+ as well build the range [b_4, +INF] for it.
+ One special case we handle is extracting a range from a
+ range test encoded as (unsigned)var + CST <= limit. */
+ if (TREE_CODE (cond) == NOP_EXPR
+ || TREE_CODE (cond) == PLUS_EXPR)
+ {
+ if (TREE_CODE (cond) == PLUS_EXPR)
+ {
+ min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (cond, 1)),
+ TREE_OPERAND (cond, 1));
+ max = int_const_binop (PLUS_EXPR, limit, min, 0);
+ cond = TREE_OPERAND (cond, 0);
+ }
+ else
+ {
+ min = build_int_cst (TREE_TYPE (var), 0);
+ max = limit;
+ }
+
+ /* Make sure to not set TREE_OVERFLOW on the final type
+ conversion. We are willingly interpreting large positive
+ unsigned values as negative singed values here. */
+ min = force_fit_type_double (TREE_TYPE (var), TREE_INT_CST_LOW (min),
+ TREE_INT_CST_HIGH (min), 0, false);
+ max = force_fit_type_double (TREE_TYPE (var), TREE_INT_CST_LOW (max),
+ TREE_INT_CST_HIGH (max), 0, false);
+
+ /* We can transform a max, min range to an anti-range or
+ vice-versa. Use set_and_canonicalize_value_range which does
+ this for us. */
+ if (cond_code == LE_EXPR)
+ set_and_canonicalize_value_range (vr_p, VR_RANGE,
+ min, max, vr_p->equiv);
+ else if (cond_code == GT_EXPR)
+ set_and_canonicalize_value_range (vr_p, VR_ANTI_RANGE,
+ min, max, vr_p->equiv);
+ else
+ gcc_unreachable ();
+ }
+ else if (cond_code == EQ_EXPR)
{
enum value_range_type range_type;
if (compare_values (anti_max, real_max) == -1
&& compare_values (anti_min, real_min) == 1)
{
- set_value_range (vr_p, VR_RANGE, real_min,
- real_max, vr_p->equiv);
+ /* If the range is covering the whole valid range of
+ the type keep the anti-range. */
+ if (!vrp_val_is_min (real_min)
+ || !vrp_val_is_max (real_max))
+ set_value_range (vr_p, VR_RANGE, real_min,
+ real_max, vr_p->equiv);
}
/* Case 2, VR_ANTI_RANGE completely disjoint from
VR_RANGE. */
}
min = positive_overflow_infinity (TREE_TYPE (var_vr->min));
}
- else
+ else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
anti_max,
build_int_cst (TREE_TYPE (var_vr->min), 1));
+ else
+ min = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (var_vr->min),
+ anti_max, size_int (1));
max = real_max;
set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
}
the ranges of each of its operands and the expression code. */
static void
-extract_range_from_binary_expr (value_range_t *vr, tree expr)
+extract_range_from_binary_expr (value_range_t *vr,
+ enum tree_code code,
+ tree expr_type, tree op0, tree op1)
{
- enum tree_code code = TREE_CODE (expr);
enum value_range_type type;
- tree op0, op1, min, max;
+ tree min, max;
int cmp;
value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
&& code != MIN_EXPR
&& code != MAX_EXPR
&& code != BIT_AND_EXPR
- && code != TRUTH_ANDIF_EXPR
- && code != TRUTH_ORIF_EXPR
&& code != TRUTH_AND_EXPR
&& code != TRUTH_OR_EXPR)
{
/* Get value ranges for each operand. For constant operands, create
a new value range with the operand to simplify processing. */
- op0 = TREE_OPERAND (expr, 0);
if (TREE_CODE (op0) == SSA_NAME)
vr0 = *(get_value_range (op0));
else if (is_gimple_min_invariant (op0))
else
set_value_range_to_varying (&vr0);
- op1 = TREE_OPERAND (expr, 1);
if (TREE_CODE (op1) == SSA_NAME)
vr1 = *(get_value_range (op1));
else if (is_gimple_min_invariant (op1))
}
/* Now evaluate the expression to determine the new range. */
- if (POINTER_TYPE_P (TREE_TYPE (expr))
+ if (POINTER_TYPE_P (expr_type)
|| POINTER_TYPE_P (TREE_TYPE (op0))
|| POINTER_TYPE_P (TREE_TYPE (op1)))
{
If both are null, then the result is null. Otherwise they
are varying. */
if (range_is_nonnull (&vr0) && range_is_nonnull (&vr1))
- set_value_range_to_nonnull (vr, TREE_TYPE (expr));
+ set_value_range_to_nonnull (vr, expr_type);
else if (range_is_null (&vr0) && range_is_null (&vr1))
- set_value_range_to_null (vr, TREE_TYPE (expr));
+ set_value_range_to_null (vr, expr_type);
else
set_value_range_to_varying (vr);
/* For pointer types, we are really only interested in asserting
whether the expression evaluates to non-NULL. */
if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
- set_value_range_to_nonnull (vr, TREE_TYPE (expr));
+ set_value_range_to_nonnull (vr, expr_type);
else if (range_is_null (&vr0) && range_is_null (&vr1))
- set_value_range_to_null (vr, TREE_TYPE (expr));
+ set_value_range_to_null (vr, expr_type);
else
set_value_range_to_varying (vr);
/* For integer ranges, apply the operation to each end of the
range and see what we end up with. */
- if (code == TRUTH_ANDIF_EXPR
- || code == TRUTH_ORIF_EXPR
- || code == TRUTH_AND_EXPR
+ if (code == TRUTH_AND_EXPR
|| code == TRUTH_OR_EXPR)
{
/* If one of the operands is zero, we know that the whole
&& integer_zerop (vr1.max))))
{
type = VR_RANGE;
- min = max = build_int_cst (TREE_TYPE (expr), 0);
+ min = max = build_int_cst (expr_type, 0);
}
/* If one of the operands is one, we know that the whole
expression evaluates one. */
&& integer_onep (vr1.max))))
{
type = VR_RANGE;
- min = max = build_int_cst (TREE_TYPE (expr), 1);
+ min = max = build_int_cst (expr_type, 1);
}
else if (vr0.type != VR_VARYING
&& vr1.type != VR_VARYING
&& !overflow_infinity_range_p (&vr1))
{
/* Boolean expressions cannot be folded with int_const_binop. */
- min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min);
- max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
+ min = fold_binary (code, expr_type, vr0.min, vr1.min);
+ max = fold_binary (code, expr_type, vr0.max, vr1.max);
}
else
{
/* The result of a TRUTH_*_EXPR is always true or false. */
- set_value_range_to_truthvalue (vr, TREE_TYPE (expr));
+ set_value_range_to_truthvalue (vr, expr_type);
return;
}
}
|| !vrp_expr_computes_nonnegative (op1, &sop)
|| (operand_less_p
(build_int_cst (TREE_TYPE (vr1.max),
- TYPE_PRECISION (TREE_TYPE (expr)) - 1),
+ TYPE_PRECISION (expr_type) - 1),
vr1.max) != 0))
{
set_value_range_to_varying (vr);
&& !TREE_OVERFLOW (vr0.max)
&& tree_int_cst_sgn (vr0.max) >= 0)
{
- min = build_int_cst (TREE_TYPE (expr), 0);
+ min = build_int_cst (expr_type, 0);
max = vr0.max;
}
else if (vr1.type == VR_RANGE
&& tree_int_cst_sgn (vr1.max) >= 0)
{
type = VR_RANGE;
- min = build_int_cst (TREE_TYPE (expr), 0);
+ min = build_int_cst (expr_type, 0);
max = vr1.max;
}
else
the range of its operand and the expression code. */
static void
-extract_range_from_unary_expr (value_range_t *vr, tree expr)
+extract_range_from_unary_expr (value_range_t *vr, enum tree_code code,
+ tree type, tree op0)
{
- enum tree_code code = TREE_CODE (expr);
- tree min, max, op0;
+ tree min, max;
int cmp;
value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
/* Get value ranges for the operand. For constant operands, create
a new value range with the operand to simplify processing. */
- op0 = TREE_OPERAND (expr, 0);
if (TREE_CODE (op0) == SSA_NAME)
vr0 = *(get_value_range (op0));
else if (is_gimple_min_invariant (op0))
/* If the expression involves pointers, we are only interested in
determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
- if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0)))
+ if (POINTER_TYPE_P (type) || POINTER_TYPE_P (TREE_TYPE (op0)))
{
bool sop;
sop = false;
if (range_is_nonnull (&vr0)
- || (tree_expr_nonzero_warnv_p (expr, &sop)
+ || (tree_unary_nonzero_warnv_p (code, type, op0, &sop)
&& !sop))
- set_value_range_to_nonnull (vr, TREE_TYPE (expr));
+ set_value_range_to_nonnull (vr, type);
else if (range_is_null (&vr0))
- set_value_range_to_null (vr, TREE_TYPE (expr));
+ set_value_range_to_null (vr, type);
else
set_value_range_to_varying (vr);
}
/* Handle unary expressions on integer ranges. */
- if (code == NOP_EXPR || code == CONVERT_EXPR)
+ if ((code == NOP_EXPR
+ || code == CONVERT_EXPR)
+ && INTEGRAL_TYPE_P (type)
+ && INTEGRAL_TYPE_P (TREE_TYPE (op0)))
{
tree inner_type = TREE_TYPE (op0);
- tree outer_type = TREE_TYPE (expr);
-
- /* If VR0 represents a simple range, then try to convert
- the min and max values for the range to the same type
- as OUTER_TYPE. If the results compare equal to VR0's
- min and max values and the new min is still less than
- or equal to the new max, then we can safely use the newly
- computed range for EXPR. This allows us to compute
- accurate ranges through many casts. */
- if ((vr0.type == VR_RANGE
- && !overflow_infinity_range_p (&vr0))
- || (vr0.type == VR_VARYING
- && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)))
+ tree outer_type = type;
+
+ /* Always use base-types here. This is important for the
+ correct signedness. */
+ if (TREE_TYPE (inner_type))
+ inner_type = TREE_TYPE (inner_type);
+ if (TREE_TYPE (outer_type))
+ outer_type = TREE_TYPE (outer_type);
+
+ /* If VR0 is varying and we increase the type precision, assume
+ a full range for the following transformation. */
+ if (vr0.type == VR_VARYING
+ && TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type))
{
- tree new_min, new_max, orig_min, orig_max;
-
- /* Convert the input operand min/max to OUTER_TYPE. If
- the input has no range information, then use the min/max
- for the input's type. */
- if (vr0.type == VR_RANGE)
- {
- orig_min = vr0.min;
- orig_max = vr0.max;
- }
- else
- {
- orig_min = TYPE_MIN_VALUE (inner_type);
- orig_max = TYPE_MAX_VALUE (inner_type);
- }
-
- new_min = fold_convert (outer_type, orig_min);
- new_max = fold_convert (outer_type, orig_max);
-
- /* Verify the new min/max values are gimple values and
- that they compare equal to the original input's
- min/max values. */
- if (is_gimple_val (new_min)
- && is_gimple_val (new_max)
- && tree_int_cst_equal (new_min, orig_min)
- && tree_int_cst_equal (new_max, orig_max)
- && (!is_overflow_infinity (new_min)
- || !is_overflow_infinity (new_max))
- && (cmp = compare_values (new_min, new_max)) <= 0
- && cmp >= -1)
- {
- set_value_range (vr, VR_RANGE, new_min, new_max, vr->equiv);
- return;
- }
+ vr0.type = VR_RANGE;
+ vr0.min = TYPE_MIN_VALUE (inner_type);
+ vr0.max = TYPE_MAX_VALUE (inner_type);
}
- /* When converting types of different sizes, set the result to
- VARYING. Things like sign extensions and precision loss may
- change the range. For instance, if x_3 is of type 'long long
- int' and 'y_5 = (unsigned short) x_3', if x_3 is ~[0, 0], it
- is impossible to know at compile time whether y_5 will be
- ~[0, 0]. */
- if (TYPE_SIZE (inner_type) != TYPE_SIZE (outer_type)
- || TYPE_PRECISION (inner_type) != TYPE_PRECISION (outer_type))
+ /* If VR0 is a constant range or anti-range and the conversion is
+ not truncating we can convert the min and max values and
+ canonicalize the resulting range. Otherwise we can do the
+ conversion if the size of the range is less than what the
+ precision of the target type can represent and the range is
+ not an anti-range. */
+ if ((vr0.type == VR_RANGE
+ || vr0.type == VR_ANTI_RANGE)
+ && TREE_CODE (vr0.min) == INTEGER_CST
+ && TREE_CODE (vr0.max) == INTEGER_CST
+ && !is_overflow_infinity (vr0.min)
+ && !is_overflow_infinity (vr0.max)
+ && (TYPE_PRECISION (outer_type) >= TYPE_PRECISION (inner_type)
+ || (vr0.type == VR_RANGE
+ && integer_zerop (int_const_binop (RSHIFT_EXPR,
+ int_const_binop (MINUS_EXPR, vr0.max, vr0.min, 0),
+ size_int (TYPE_PRECISION (outer_type)), 0)))))
{
- set_value_range_to_varying (vr);
+ tree new_min, new_max;
+ new_min = force_fit_type_double (outer_type,
+ TREE_INT_CST_LOW (vr0.min),
+ TREE_INT_CST_HIGH (vr0.min), 0, 0);
+ new_max = force_fit_type_double (outer_type,
+ TREE_INT_CST_LOW (vr0.max),
+ TREE_INT_CST_HIGH (vr0.max), 0, 0);
+ set_and_canonicalize_value_range (vr, vr0.type,
+ new_min, new_max, NULL);
return;
}
+
+ set_value_range_to_varying (vr);
+ return;
}
/* Conversion of a VR_VARYING value to a wider type can result
/* Apply the operation to each end of the range and see what we end
up with. */
if (code == NEGATE_EXPR
- && !TYPE_UNSIGNED (TREE_TYPE (expr)))
+ && !TYPE_UNSIGNED (type))
{
/* NEGATE_EXPR flips the range around. We need to treat
TYPE_MIN_VALUE specially. */
if (is_positive_overflow_infinity (vr0.max))
- min = negative_overflow_infinity (TREE_TYPE (expr));
+ min = negative_overflow_infinity (type);
else if (is_negative_overflow_infinity (vr0.max))
- min = positive_overflow_infinity (TREE_TYPE (expr));
+ min = positive_overflow_infinity (type);
else if (!vrp_val_is_min (vr0.max))
- min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
- else if (needs_overflow_infinity (TREE_TYPE (expr)))
+ min = fold_unary_to_constant (code, type, vr0.max);
+ else if (needs_overflow_infinity (type))
{
- if (supports_overflow_infinity (TREE_TYPE (expr))
+ if (supports_overflow_infinity (type)
&& !is_overflow_infinity (vr0.min)
&& !vrp_val_is_min (vr0.min))
- min = positive_overflow_infinity (TREE_TYPE (expr));
+ min = positive_overflow_infinity (type);
else
{
set_value_range_to_varying (vr);
}
}
else
- min = TYPE_MIN_VALUE (TREE_TYPE (expr));
+ min = TYPE_MIN_VALUE (type);
if (is_positive_overflow_infinity (vr0.min))
- max = negative_overflow_infinity (TREE_TYPE (expr));
+ max = negative_overflow_infinity (type);
else if (is_negative_overflow_infinity (vr0.min))
- max = positive_overflow_infinity (TREE_TYPE (expr));
+ max = positive_overflow_infinity (type);
else if (!vrp_val_is_min (vr0.min))
- max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
- else if (needs_overflow_infinity (TREE_TYPE (expr)))
+ max = fold_unary_to_constant (code, type, vr0.min);
+ else if (needs_overflow_infinity (type))
{
- if (supports_overflow_infinity (TREE_TYPE (expr)))
- max = positive_overflow_infinity (TREE_TYPE (expr));
+ if (supports_overflow_infinity (type))
+ max = positive_overflow_infinity (type);
else
{
set_value_range_to_varying (vr);
}
}
else
- max = TYPE_MIN_VALUE (TREE_TYPE (expr));
+ max = TYPE_MIN_VALUE (type);
}
else if (code == NEGATE_EXPR
- && TYPE_UNSIGNED (TREE_TYPE (expr)))
+ && TYPE_UNSIGNED (type))
{
if (!range_includes_zero_p (&vr0))
{
- max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
- min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
+ max = fold_unary_to_constant (code, type, vr0.min);
+ min = fold_unary_to_constant (code, type, vr0.max);
}
else
{
if (range_is_null (&vr0))
- set_value_range_to_null (vr, TREE_TYPE (expr));
+ set_value_range_to_null (vr, type);
else
set_value_range_to_varying (vr);
return;
}
}
else if (code == ABS_EXPR
- && !TYPE_UNSIGNED (TREE_TYPE (expr)))
+ && !TYPE_UNSIGNED (type))
{
/* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
useful range. */
- if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (expr))
+ if (!TYPE_OVERFLOW_UNDEFINED (type)
&& ((vr0.type == VR_RANGE
&& vrp_val_is_min (vr0.min))
|| (vr0.type == VR_ANTI_RANGE
/* ABS_EXPR may flip the range around, if the original range
included negative values. */
if (is_overflow_infinity (vr0.min))
- min = positive_overflow_infinity (TREE_TYPE (expr));
+ min = positive_overflow_infinity (type);
else if (!vrp_val_is_min (vr0.min))
- min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
- else if (!needs_overflow_infinity (TREE_TYPE (expr)))
- min = TYPE_MAX_VALUE (TREE_TYPE (expr));
- else if (supports_overflow_infinity (TREE_TYPE (expr)))
- min = positive_overflow_infinity (TREE_TYPE (expr));
+ min = fold_unary_to_constant (code, type, vr0.min);
+ else if (!needs_overflow_infinity (type))
+ min = TYPE_MAX_VALUE (type);
+ else if (supports_overflow_infinity (type))
+ min = positive_overflow_infinity (type);
else
{
set_value_range_to_varying (vr);
}
if (is_overflow_infinity (vr0.max))
- max = positive_overflow_infinity (TREE_TYPE (expr));
+ max = positive_overflow_infinity (type);
else if (!vrp_val_is_min (vr0.max))
- max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
- else if (!needs_overflow_infinity (TREE_TYPE (expr)))
- max = TYPE_MAX_VALUE (TREE_TYPE (expr));
- else if (supports_overflow_infinity (TREE_TYPE (expr)))
- max = positive_overflow_infinity (TREE_TYPE (expr));
+ max = fold_unary_to_constant (code, type, vr0.max);
+ else if (!needs_overflow_infinity (type))
+ max = TYPE_MAX_VALUE (type);
+ else if (supports_overflow_infinity (type))
+ max = positive_overflow_infinity (type);
else
{
set_value_range_to_varying (vr);
or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
flag_wrapv is set and the original anti-range doesn't include
TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */
- if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (expr)))
+ if (TYPE_OVERFLOW_WRAPS (type))
{
- tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr));
+ tree type_min_value = TYPE_MIN_VALUE (type);
min = (vr0.min != type_min_value
? int_const_binop (PLUS_EXPR, type_min_value,
else
{
if (overflow_infinity_range_p (&vr0))
- min = negative_overflow_infinity (TREE_TYPE (expr));
+ min = negative_overflow_infinity (type);
else
- min = TYPE_MIN_VALUE (TREE_TYPE (expr));
+ min = TYPE_MIN_VALUE (type);
}
}
else
flag_wrapv since TYPE_MIN_VALUE is in the original
anti-range. */
vr0.type = VR_RANGE;
- min = build_int_cst (TREE_TYPE (expr), 0);
- if (needs_overflow_infinity (TREE_TYPE (expr)))
+ min = build_int_cst (type, 0);
+ if (needs_overflow_infinity (type))
{
- if (supports_overflow_infinity (TREE_TYPE (expr)))
- max = positive_overflow_infinity (TREE_TYPE (expr));
+ if (supports_overflow_infinity (type))
+ max = positive_overflow_infinity (type);
else
{
set_value_range_to_varying (vr);
}
}
else
- max = TYPE_MAX_VALUE (TREE_TYPE (expr));
+ max = TYPE_MAX_VALUE (type);
}
}
{
if (cmp == 1)
max = min;
- min = build_int_cst (TREE_TYPE (expr), 0);
+ min = build_int_cst (type, 0);
}
else
{
else
{
/* Otherwise, operate on each end of the range. */
- min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
- max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
+ min = fold_unary_to_constant (code, type, vr0.min);
+ max = fold_unary_to_constant (code, type, vr0.max);
- if (needs_overflow_infinity (TREE_TYPE (expr)))
+ if (needs_overflow_infinity (type))
{
gcc_assert (code != NEGATE_EXPR && code != ABS_EXPR);
min = vr0.min;
else if (TREE_OVERFLOW (min))
{
- if (supports_overflow_infinity (TREE_TYPE (expr)))
+ if (supports_overflow_infinity (type))
min = (tree_int_cst_sgn (min) >= 0
? positive_overflow_infinity (TREE_TYPE (min))
: negative_overflow_infinity (TREE_TYPE (min)));
max = vr0.max;
else if (TREE_OVERFLOW (max))
{
- if (supports_overflow_infinity (TREE_TYPE (expr)))
+ if (supports_overflow_infinity (type))
max = (tree_int_cst_sgn (max) >= 0
? positive_overflow_infinity (TREE_TYPE (max))
: negative_overflow_infinity (TREE_TYPE (max)));
on the range of its operand and the expression code. */
static void
-extract_range_from_comparison (value_range_t *vr, tree expr)
+extract_range_from_comparison (value_range_t *vr, enum tree_code code,
+ tree type, tree op0, tree op1)
{
bool sop = false;
- tree val = vrp_evaluate_conditional_warnv (expr, false, &sop);
+ tree val = vrp_evaluate_conditional_warnv_with_ops (code,
+ op0,
+ op1,
+ false, &sop);
/* A disadvantage of using a special infinity as an overflow
representation is that we lose the ability to record overflow
/* Since this expression was found on the RHS of an assignment,
its type may be different from _Bool. Convert VAL to EXPR's
type. */
- val = fold_convert (TREE_TYPE (expr), val);
+ val = fold_convert (type, val);
if (is_gimple_min_invariant (val))
set_value_range_to_value (vr, val, vr->equiv);
else
}
else
/* The result of a comparison is always true or false. */
- set_value_range_to_truthvalue (vr, TREE_TYPE (expr));
+ set_value_range_to_truthvalue (vr, type);
}
else if (code == SSA_NAME)
extract_range_from_ssa_name (vr, expr);
else if (TREE_CODE_CLASS (code) == tcc_binary
- || code == TRUTH_ANDIF_EXPR
- || code == TRUTH_ORIF_EXPR
|| code == TRUTH_AND_EXPR
|| code == TRUTH_OR_EXPR
|| code == TRUTH_XOR_EXPR)
- extract_range_from_binary_expr (vr, expr);
+ extract_range_from_binary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr),
+ TREE_OPERAND (expr, 0),
+ TREE_OPERAND (expr, 1));
else if (TREE_CODE_CLASS (code) == tcc_unary)
- extract_range_from_unary_expr (vr, expr);
+ extract_range_from_unary_expr (vr, TREE_CODE (expr), TREE_TYPE (expr),
+ TREE_OPERAND (expr, 0));
else if (code == COND_EXPR)
extract_range_from_cond_expr (vr, expr);
else if (TREE_CODE_CLASS (code) == tcc_comparison)
- extract_range_from_comparison (vr, expr);
+ extract_range_from_comparison (vr, TREE_CODE (expr), TREE_TYPE (expr),
+ TREE_OPERAND (expr, 0),
+ TREE_OPERAND (expr, 1));
else if (is_gimple_min_invariant (expr))
set_value_range_to_value (vr, expr, NULL);
else
if (vr->type == VR_ANTI_RANGE)
return;
+ /* Ensure that there are not values in the scev cache based on assumptions
+ on ranges of ssa names that were changed
+ (in set_value_range/set_value_range_to_varying). Preserve cached numbers
+ of iterations, that were computed before the start of VRP (we do not
+ recompute these each time to save the compile time). */
+ scev_reset_except_niters ();
+
chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
+
+ /* Like in PR19590, scev can return a constant function. */
+ if (is_gimple_min_invariant (chrec))
+ {
+ set_value_range_to_value (vr, chrec, vr->equiv);
+ return;
+ }
+
if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
return;
point values. */
static inline bool
-fp_predicate (tree expr)
+fp_predicate (const_tree expr)
{
return (COMPARISON_CLASS_P (expr)
&& FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
/* If NAME doesn't have an ASSERT_EXPR registered for asserting
- 'NAME COMP_CODE VAL' at a location that dominates block BB or
+ 'EXPR COMP_CODE VAL' at a location that dominates block BB or
E->DEST, then register this location as a possible insertion point
- for ASSERT_EXPR <NAME, NAME COMP_CODE VAL>.
+ for ASSERT_EXPR <NAME, EXPR COMP_CODE VAL>.
BB, E and SI provide the exact insertion point for the new
ASSERT_EXPR. If BB is NULL, then the ASSERT_EXPR is to be inserted
must not be NULL. */
static void
-register_new_assert_for (tree name,
+register_new_assert_for (tree name, tree expr,
enum tree_code comp_code,
tree val,
basic_block bb,
{
if (loc->comp_code == comp_code
&& (loc->val == val
- || operand_equal_p (loc->val, val, 0)))
+ || operand_equal_p (loc->val, val, 0))
+ && (loc->expr == expr
+ || operand_equal_p (loc->expr, expr, 0)))
{
/* If the assertion NAME COMP_CODE VAL has already been
registered at a basic block that dominates DEST_BB, then
n->si = si;
n->comp_code = comp_code;
n->val = val;
+ n->expr = expr;
n->next = NULL;
if (last_loc)
bitmap_set_bit (need_assert_for, SSA_NAME_VERSION (name));
}
-/* COND is a predicate which uses NAME. Extract a suitable test code
- and value and store them into *CODE_P and *VAL_P so the predicate
- is normalized to NAME *CODE_P *VAL_P.
+/* (COND_OP0 COND_CODE COND_OP1) is a predicate which uses NAME.
+ Extract a suitable test code and value and store them into *CODE_P and
+ *VAL_P so the predicate is normalized to NAME *CODE_P *VAL_P.
If no extraction was possible, return FALSE, otherwise return TRUE.
If INVERT is true, then we invert the result stored into *CODE_P. */
static bool
-extract_code_and_val_from_cond (tree name, tree cond, bool invert,
- enum tree_code *code_p, tree *val_p)
+extract_code_and_val_from_cond_with_ops (tree name, enum tree_code cond_code,
+ tree cond_op0, tree cond_op1,
+ bool invert, enum tree_code *code_p,
+ tree *val_p)
{
enum tree_code comp_code;
tree val;
- /* Predicates may be a single SSA name or NAME OP VAL. */
- if (cond == name)
+ /* Otherwise, we have a comparison of the form NAME COMP VAL
+ or VAL COMP NAME. */
+ if (name == cond_op1)
{
- /* If the predicate is a name, it must be NAME, in which
- case we create the predicate NAME == true or
- NAME == false accordingly. */
- comp_code = EQ_EXPR;
- val = invert ? boolean_false_node : boolean_true_node;
+ /* If the predicate is of the form VAL COMP NAME, flip
+ COMP around because we need to register NAME as the
+ first operand in the predicate. */
+ comp_code = swap_tree_comparison (cond_code);
+ val = cond_op0;
}
else
{
- /* Otherwise, we have a comparison of the form NAME COMP VAL
- or VAL COMP NAME. */
- if (name == TREE_OPERAND (cond, 1))
- {
- /* If the predicate is of the form VAL COMP NAME, flip
- COMP around because we need to register NAME as the
- first operand in the predicate. */
- comp_code = swap_tree_comparison (TREE_CODE (cond));
- val = TREE_OPERAND (cond, 0);
+ /* The comparison is of the form NAME COMP VAL, so the
+ comparison code remains unchanged. */
+ comp_code = cond_code;
+ val = cond_op1;
+ }
+
+ /* Invert the comparison code as necessary. */
+ if (invert)
+ comp_code = invert_tree_comparison (comp_code, 0);
+
+ /* VRP does not handle float types. */
+ if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)))
+ return false;
+
+ /* Do not register always-false predicates.
+ FIXME: this works around a limitation in fold() when dealing with
+ enumerations. Given 'enum { N1, N2 } x;', fold will not
+ fold 'if (x > N2)' to 'if (0)'. */
+ if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
+ && INTEGRAL_TYPE_P (TREE_TYPE (val)))
+ {
+ tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
+ tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
+
+ if (comp_code == GT_EXPR
+ && (!max
+ || compare_values (val, max) == 0))
+ return false;
+
+ if (comp_code == LT_EXPR
+ && (!min
+ || compare_values (val, min) == 0))
+ return false;
+ }
+ *code_p = comp_code;
+ *val_p = val;
+ return true;
+}
+
+/* Try to register an edge assertion for SSA name NAME on edge E for
+ the condition COND contributing to the conditional jump pointed to by BSI.
+ Invert the condition COND if INVERT is true.
+ Return true if an assertion for NAME could be registered. */
+
+static bool
+register_edge_assert_for_2 (tree name, edge e, block_stmt_iterator bsi,
+ enum tree_code cond_code,
+ tree cond_op0, tree cond_op1, bool invert)
+{
+ tree val;
+ enum tree_code comp_code;
+ bool retval = false;
+
+ if (!extract_code_and_val_from_cond_with_ops (name, cond_code,
+ cond_op0,
+ cond_op1,
+ invert, &comp_code, &val))
+ return false;
+
+ /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
+ reachable from E. */
+ if (TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name))
+ && !has_single_use (name))
+ {
+ register_new_assert_for (name, name, comp_code, val, NULL, e, bsi);
+ retval = true;
+ }
+
+ /* In the case of NAME <= CST and NAME being defined as
+ NAME = (unsigned) NAME2 + CST2 we can assert NAME2 >= -CST2
+ and NAME2 <= CST - CST2. We can do the same for NAME > CST.
+ This catches range and anti-range tests. */
+ if ((comp_code == LE_EXPR
+ || comp_code == GT_EXPR)
+ && TREE_CODE (val) == INTEGER_CST
+ && TYPE_UNSIGNED (TREE_TYPE (val)))
+ {
+ tree def_stmt = SSA_NAME_DEF_STMT (name);
+ tree cst2 = NULL_TREE, name2 = NULL_TREE, name3 = NULL_TREE;
+
+ /* Extract CST2 from the (optional) addition. */
+ if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
+ && TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == PLUS_EXPR)
+ {
+ name2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
+ cst2 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 1);
+ if (TREE_CODE (name2) == SSA_NAME
+ && TREE_CODE (cst2) == INTEGER_CST)
+ def_stmt = SSA_NAME_DEF_STMT (name2);
}
- else
+
+ /* Extract NAME2 from the (optional) sign-changing cast. */
+ if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
+ && (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == NOP_EXPR
+ || TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == CONVERT_EXPR))
{
- /* The comparison is of the form NAME COMP VAL, so the
- comparison code remains unchanged. */
- comp_code = TREE_CODE (cond);
- val = TREE_OPERAND (cond, 1);
+ tree rhs = GIMPLE_STMT_OPERAND (def_stmt, 1);
+ if ((TREE_CODE (rhs) == NOP_EXPR
+ || TREE_CODE (rhs) == CONVERT_EXPR)
+ && ! TYPE_UNSIGNED (TREE_TYPE (TREE_OPERAND (rhs, 0)))
+ && (TYPE_PRECISION (TREE_TYPE (rhs))
+ == TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (rhs, 0)))))
+ name3 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
}
- /* Invert the comparison code as necessary. */
- if (invert)
- comp_code = invert_tree_comparison (comp_code, 0);
+ /* If name3 is used later, create an ASSERT_EXPR for it. */
+ if (name3 != NULL_TREE
+ && TREE_CODE (name3) == SSA_NAME
+ && (cst2 == NULL_TREE
+ || TREE_CODE (cst2) == INTEGER_CST)
+ && INTEGRAL_TYPE_P (TREE_TYPE (name3))
+ && TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name3))
+ && !has_single_use (name3))
+ {
+ tree tmp;
- /* VRP does not handle float types. */
- if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)))
- return false;
+ /* Build an expression for the range test. */
+ tmp = build1 (NOP_EXPR, TREE_TYPE (name), name3);
+ if (cst2 != NULL_TREE)
+ tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2);
- /* Do not register always-false predicates.
- FIXME: this works around a limitation in fold() when dealing with
- enumerations. Given 'enum { N1, N2 } x;', fold will not
- fold 'if (x > N2)' to 'if (0)'. */
- if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
- && INTEGRAL_TYPE_P (TREE_TYPE (val)))
+ if (dump_file)
+ {
+ fprintf (dump_file, "Adding assert for ");
+ print_generic_expr (dump_file, name3, 0);
+ fprintf (dump_file, " from ");
+ print_generic_expr (dump_file, tmp, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ register_new_assert_for (name3, tmp, comp_code, val, NULL, e, bsi);
+
+ retval = true;
+ }
+
+ /* If name2 is used later, create an ASSERT_EXPR for it. */
+ if (name2 != NULL_TREE
+ && TREE_CODE (name2) == SSA_NAME
+ && TREE_CODE (cst2) == INTEGER_CST
+ && INTEGRAL_TYPE_P (TREE_TYPE (name2))
+ && TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name2))
+ && !has_single_use (name2))
{
- tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
- tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
-
- if (comp_code == GT_EXPR
- && (!max
- || compare_values (val, max) == 0))
- return false;
-
- if (comp_code == LT_EXPR
- && (!min
- || compare_values (val, min) == 0))
- return false;
+ tree tmp;
+
+ /* Build an expression for the range test. */
+ tmp = name2;
+ if (TREE_TYPE (name) != TREE_TYPE (name2))
+ tmp = build1 (NOP_EXPR, TREE_TYPE (name), tmp);
+ if (cst2 != NULL_TREE)
+ tmp = build2 (PLUS_EXPR, TREE_TYPE (name), tmp, cst2);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Adding assert for ");
+ print_generic_expr (dump_file, name2, 0);
+ fprintf (dump_file, " from ");
+ print_generic_expr (dump_file, tmp, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ register_new_assert_for (name2, tmp, comp_code, val, NULL, e, bsi);
+
+ retval = true;
}
}
- *code_p = comp_code;
- *val_p = val;
- return true;
+
+ return retval;
}
/* OP is an operand of a truth value expression which is known to have
{
bool retval = false;
tree op_def, rhs, val;
+ enum tree_code rhs_code;
/* We only care about SSA_NAMEs. */
if (TREE_CODE (op) != SSA_NAME)
if (!has_single_use (op))
{
val = build_int_cst (TREE_TYPE (op), 0);
- register_new_assert_for (op, code, val, NULL, e, bsi);
+ register_new_assert_for (op, op, code, val, NULL, e, bsi);
retval = true;
}
return retval;
rhs = GIMPLE_STMT_OPERAND (op_def, 1);
+ rhs_code = TREE_CODE (rhs);
if (COMPARISON_CLASS_P (rhs))
{
tree op0 = TREE_OPERAND (rhs, 0);
tree op1 = TREE_OPERAND (rhs, 1);
- /* Conditionally register an assert for each SSA_NAME in the
- comparison. */
- if (TREE_CODE (op0) == SSA_NAME
- && !has_single_use (op0)
- && extract_code_and_val_from_cond (op0, rhs,
- invert, &code, &val))
- {
- register_new_assert_for (op0, code, val, NULL, e, bsi);
- retval = true;
- }
-
- /* Similarly for the second operand of the comparison. */
- if (TREE_CODE (op1) == SSA_NAME
- && !has_single_use (op1)
- && extract_code_and_val_from_cond (op1, rhs,
- invert, &code, &val))
- {
- register_new_assert_for (op1, code, val, NULL, e, bsi);
- retval = true;
- }
+ if (TREE_CODE (op0) == SSA_NAME)
+ retval |= register_edge_assert_for_2 (op0, e, bsi, rhs_code, op0, op1,
+ invert);
+ if (TREE_CODE (op1) == SSA_NAME)
+ retval |= register_edge_assert_for_2 (op1, e, bsi, rhs_code, op0, op1,
+ invert);
}
else if ((code == NE_EXPR
&& (TREE_CODE (rhs) == TRUTH_AND_EXPR
Return true if an assertion for NAME could be registered. */
static bool
-register_edge_assert_for (tree name, edge e, block_stmt_iterator si, tree cond)
+register_edge_assert_for (tree name, edge e, block_stmt_iterator si,
+ enum tree_code cond_code, tree cond_op0,
+ tree cond_op1)
{
tree val;
enum tree_code comp_code;
if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (name))
return false;
- if (!extract_code_and_val_from_cond (name, cond, is_else_edge,
- &comp_code, &val))
+ if (!extract_code_and_val_from_cond_with_ops (name, cond_code,
+ cond_op0, cond_op1,
+ is_else_edge,
+ &comp_code, &val))
return false;
- /* Only register an ASSERT_EXPR if NAME was found in the sub-graph
- reachable from E. */
- if (TEST_BIT (found_in_subgraph, SSA_NAME_VERSION (name)))
- {
- register_new_assert_for (name, comp_code, val, NULL, e, si);
- retval = true;
- }
+ /* Register ASSERT_EXPRs for name. */
+ retval |= register_edge_assert_for_2 (name, e, si, cond_code, cond_op0,
+ cond_op1, is_else_edge);
+
/* If COND is effectively an equality test of an SSA_NAME against
the value zero or one, then we may be able to assert values
if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
&& (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == TRUTH_OR_EXPR
- || TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == BIT_IOR_EXPR))
+ /* For BIT_IOR_EXPR only if NAME == 0 both operands have
+ necessarily zero value. */
+ || (comp_code == EQ_EXPR
+ && (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1))
+ == BIT_IOR_EXPR))))
{
tree op0 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
tree op1 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 1);
/* Traverse the strictly dominated sub-graph rooted at E->DEST
to determine if any of the operands in the conditional
predicate are used. */
- if (e->dest != bb)
- need_assert |= find_assert_locations (e->dest);
+ need_assert |= find_assert_locations (e->dest);
/* Register the necessary assertions for each operand in the
conditional predicate. */
FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
- need_assert |= register_edge_assert_for (op, e, bsi,
- COND_EXPR_COND (last));
+ {
+ tree cond = COND_EXPR_COND (last);
+ if (op != cond)
+ need_assert |= register_edge_assert_for (op, e, bsi,
+ TREE_CODE (cond),
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1));
+ else
+ need_assert |= register_edge_assert_for (op, e, bsi, EQ_EXPR, op,
+ boolean_true_node);
+ }
}
/* Finally, indicate that we have found the operands in the
static int
compare_case_labels (const void *p1, const void *p2)
{
- tree case1 = *(tree *)p1;
- tree case2 = *(tree *)p2;
+ const_tree const case1 = *(const_tree const*)p1;
+ const_tree const case2 = *(const_tree const*)p2;
unsigned int uid1 = DECL_UID (CASE_LABEL (case1));
unsigned int uid2 = DECL_UID (CASE_LABEL (case2));
{
bool need_assert;
block_stmt_iterator bsi;
- tree op, cond;
+ tree op;
edge e;
tree vec = SWITCH_LABELS (last), vec2;
size_t n = TREE_VEC_LENGTH (vec);
/* Register the necessary assertions for the operand in the
SWITCH_EXPR. */
- cond = build2 (max ? GE_EXPR : EQ_EXPR, boolean_type_node,
- op, fold_convert (TREE_TYPE (op), min));
- need_assert |= register_edge_assert_for (op, e, bsi, cond);
+ need_assert |= register_edge_assert_for (op, e, bsi,
+ max ? GE_EXPR : EQ_EXPR,
+ op,
+ fold_convert (TREE_TYPE (op),
+ min));
if (max)
{
- cond = build2 (LE_EXPR, boolean_type_node,
- op, fold_convert (TREE_TYPE (op), max));
- need_assert |= register_edge_assert_for (op, e, bsi, cond);
+ need_assert |= register_edge_assert_for (op, e, bsi, LE_EXPR,
+ op,
+ fold_convert (TREE_TYPE (op),
+ max));
}
}
conversion. */
if (! has_single_use (t))
{
- register_new_assert_for (t, comp_code, value,
+ register_new_assert_for (t, t, comp_code, value,
bb, NULL, si);
need_assert = true;
}
ASSERT_EXPR would do nothing but increase compile time. */
if (!has_single_use (op))
{
- register_new_assert_for (op, comp_code, value, bb, NULL, si);
+ register_new_assert_for (op, op, comp_code, value,
+ bb, NULL, si);
need_assert = true;
}
}
edge_iterator ei;
edge e;
- cond = build2 (loc->comp_code, boolean_type_node, name, loc->val);
+ cond = build2 (loc->comp_code, boolean_type_node, loc->expr, loc->val);
assert_expr = build_assert_expr_for (cond, name);
if (loc->e)
low_sub = up_sub = TREE_OPERAND (ref, 1);
- if (!up_bound || !locus || TREE_NO_WARNING (ref)
+ if (!up_bound || TREE_NO_WARNING (ref)
|| TREE_CODE (up_bound) != INTEGER_CST
/* Can not check flexible arrays. */
|| (TYPE_SIZE (TREE_TYPE (ref)) == NULL_TREE
tree stmt = (tree)data;
location_t *location = EXPR_LOCUS (stmt);
+ if (!EXPR_HAS_LOCATION (stmt))
+ {
+ *walk_subtree = FALSE;
+ return NULL_TREE;
+ }
+
*walk_subtree = TRUE;
if (TREE_CODE (t) == ARRAY_REF)
return NULL_TREE;
}
+/* Helper function for vrp_evaluate_conditional_warnv. */
+
+static tree
+vrp_evaluate_conditional_warnv_with_ops (enum tree_code code, tree op0,
+ tree op1, bool use_equiv_p,
+ bool *strict_overflow_p)
+{
+ /* We only deal with integral and pointer types. */
+ if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
+ && !POINTER_TYPE_P (TREE_TYPE (op0)))
+ return NULL_TREE;
+
+ if (use_equiv_p)
+ {
+ if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
+ return compare_names (code, op0, op1,
+ strict_overflow_p);
+ else if (TREE_CODE (op0) == SSA_NAME)
+ return compare_name_with_value (code, op0, op1,
+ strict_overflow_p);
+ else if (TREE_CODE (op1) == SSA_NAME)
+ return (compare_name_with_value
+ (swap_tree_comparison (code), op1, op0,
+ strict_overflow_p));
+ }
+ else
+ {
+ value_range_t *vr0, *vr1;
+
+ vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
+ vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
+
+ if (vr0 && vr1)
+ return compare_ranges (code, vr0, vr1,
+ strict_overflow_p);
+ else if (vr0 && vr1 == NULL)
+ return compare_range_with_value (code, vr0, op1,
+ strict_overflow_p);
+ else if (vr0 == NULL && vr1)
+ return (compare_range_with_value
+ (swap_tree_comparison (code), vr1, op0,
+ strict_overflow_p));
+ }
+ return NULL_TREE;
+}
/* Given a conditional predicate COND, try to determine if COND yields
true or false based on the value ranges of its operands. Return
return vr->min;
}
else
- {
- tree op0 = TREE_OPERAND (cond, 0);
- tree op1 = TREE_OPERAND (cond, 1);
-
- /* We only deal with integral and pointer types. */
- if (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
- && !POINTER_TYPE_P (TREE_TYPE (op0)))
- return NULL_TREE;
-
- if (use_equiv_p)
- {
- if (TREE_CODE (op0) == SSA_NAME && TREE_CODE (op1) == SSA_NAME)
- return compare_names (TREE_CODE (cond), op0, op1,
- strict_overflow_p);
- else if (TREE_CODE (op0) == SSA_NAME)
- return compare_name_with_value (TREE_CODE (cond), op0, op1,
- strict_overflow_p);
- else if (TREE_CODE (op1) == SSA_NAME)
- return (compare_name_with_value
- (swap_tree_comparison (TREE_CODE (cond)), op1, op0,
- strict_overflow_p));
- }
- else
- {
- value_range_t *vr0, *vr1;
-
- vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
- vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
-
- if (vr0 && vr1)
- return compare_ranges (TREE_CODE (cond), vr0, vr1,
- strict_overflow_p);
- else if (vr0 && vr1 == NULL)
- return compare_range_with_value (TREE_CODE (cond), vr0, op1,
- strict_overflow_p);
- else if (vr0 == NULL && vr1)
- return (compare_range_with_value
- (swap_tree_comparison (TREE_CODE (cond)), vr1, op0,
- strict_overflow_p));
- }
- }
+ return vrp_evaluate_conditional_warnv_with_ops (TREE_CODE (cond),
+ TREE_OPERAND (cond, 0),
+ TREE_OPERAND (cond, 1),
+ use_equiv_p,
+ strict_overflow_p);
/* Anything else cannot be computed statically. */
return NULL_TREE;
}
}
+ if (warn_type_limits
+ && ret
+ && TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison
+ && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME)
+ {
+ /* If the comparison is being folded and the operand on the LHS
+ is being compared against a constant value that is outside of
+ the natural range of OP0's type, then the predicate will
+ always fold regardless of the value of OP0. If -Wtype-limits
+ was specified, emit a warning. */
+ const char *warnmsg = NULL;
+ tree op0 = TREE_OPERAND (cond, 0);
+ tree op1 = TREE_OPERAND (cond, 1);
+ tree type = TREE_TYPE (op0);
+ value_range_t *vr0 = get_value_range (op0);
+
+ if (vr0->type != VR_VARYING
+ && INTEGRAL_TYPE_P (type)
+ && vrp_val_is_min (vr0->min)
+ && vrp_val_is_max (vr0->max)
+ && is_gimple_min_invariant (op1))
+ {
+ if (integer_zerop (ret))
+ warnmsg = G_("comparison always false due to limited range of "
+ "data type");
+ else
+ warnmsg = G_("comparison always true due to limited range of "
+ "data type");
+ }
+
+ if (warnmsg)
+ {
+ location_t locus;
+
+ if (!EXPR_HAS_LOCATION (stmt))
+ locus = input_location;
+ else
+ locus = EXPR_LOCATION (stmt);
+
+ warning (OPT_Wtype_limits, "%H%s", &locus, warnmsg);
+ }
+ }
+
return ret;
}
bool sop;
*taken_edge_p = NULL;
-
- /* FIXME. Handle SWITCH_EXPRs. */
- if (TREE_CODE (stmt) == SWITCH_EXPR)
- return SSA_PROP_VARYING;
-
cond = COND_EXPR_COND (stmt);
if (dump_file && (dump_flags & TDF_DETAILS))
}
+/* Searches the case label vector VEC for the index *IDX the CASE_LABEL
+ includes the value VAL. The search starts at index START_IDX and
+ true is returned if *IDX corresponds to such an index. False is
+ returned in case VAL hits the default case label and *IDX in this
+ case is the next higher or the next lower case label index. */
+
+static bool
+find_case_label_index (tree vec, size_t start_idx, tree val, size_t *idx)
+{
+ size_t n = TREE_VEC_LENGTH (vec);
+ size_t low, high, i = start_idx;
+
+ /* Find case label for minimum of the value range or the next one. */
+ for (low = start_idx - 1, high = n - 1; high - low > 1; )
+ {
+ tree t;
+ int cmp;
+ i = (high + low) / 2;
+ t = TREE_VEC_ELT (vec, i);
+
+ /* Cache the result of comparing CASE_LOW and val. */
+ cmp = tree_int_cst_compare (CASE_LOW (t), val);
+
+ if (cmp > 0)
+ high = i;
+ else
+ low = i;
+
+ if (CASE_HIGH (t) == NULL)
+ {
+ /* A singe-valued case label. */
+ if (cmp == 0)
+ {
+ *idx = i;
+ return true;
+ }
+ }
+ else
+ {
+ /* A case range. We can only handle integer ranges. */
+ if (cmp <= 0 && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
+ {
+ *idx = i;
+ return true;
+ }
+ }
+ }
+
+ *idx = i;
+ return false;
+}
+
+/* Visit switch statement STMT. If we can determine which edge
+ will be taken out of STMT's basic block, record it in
+ *TAKEN_EDGE_P and return SSA_PROP_INTERESTING. Otherwise, return
+ SSA_PROP_VARYING. */
+
+static enum ssa_prop_result
+vrp_visit_switch_stmt (tree stmt, edge *taken_edge_p)
+{
+ tree op, val;
+ value_range_t *vr;
+ size_t i = 0, j = 0, n;
+ tree vec;
+ bool min_take_default, max_take_default;
+
+ *taken_edge_p = NULL;
+ op = TREE_OPERAND (stmt, 0);
+ if (TREE_CODE (op) != SSA_NAME)
+ return SSA_PROP_VARYING;
+
+ vr = get_value_range (op);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "\nVisiting switch expression with operand ");
+ print_generic_expr (dump_file, op, 0);
+ fprintf (dump_file, " with known range ");
+ dump_value_range (dump_file, vr);
+ fprintf (dump_file, "\n");
+ }
+
+ if (vr->type != VR_RANGE
+ || symbolic_range_p (vr))
+ return SSA_PROP_VARYING;
+
+ /* Find the single edge that is taken from the switch expression. */
+ vec = SWITCH_LABELS (stmt);
+ n = TREE_VEC_LENGTH (vec);
+
+ /* Find case label for minimum of the value range or the next one. */
+ min_take_default = !find_case_label_index (vec, 0, vr->min, &i);
+
+ /* Find case label for maximum of the value range or the previous one. */
+ max_take_default = !find_case_label_index (vec, i, vr->max, &j);
+
+ /* Check if we reach the default label only. */
+ if (j < i)
+ val = TREE_VEC_ELT (vec, n - 1);
+ /* Check if we reach exactly one label and not the default label. */
+ else if (i == j
+ && !min_take_default
+ && !max_take_default)
+ val = TREE_VEC_ELT (vec, i);
+ else
+ {
+ /* Check if labels with index i to j are all reaching the same label.
+ If we don't hit a single case label only, the default case also has
+ to branch to the same label. */
+ val = TREE_VEC_ELT (vec, i);
+ if (CASE_LABEL (TREE_VEC_ELT (vec, n - 1)) != CASE_LABEL (val))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " not a single destination for this "
+ "range\n");
+ return SSA_PROP_VARYING;
+ }
+ for (++i; i <= j; ++i)
+ {
+ if (CASE_LABEL (TREE_VEC_ELT (vec, i)) != CASE_LABEL (val))
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ fprintf (dump_file, " not a single destination for this "
+ "range\n");
+ return SSA_PROP_VARYING;
+ }
+ }
+ }
+
+ *taken_edge_p = find_edge (bb_for_stmt (stmt),
+ label_to_block (CASE_LABEL (val)));
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, " will take edge to ");
+ print_generic_stmt (dump_file, CASE_LABEL (val), 0);
+ }
+
+ return SSA_PROP_INTERESTING;
+}
+
+
/* Evaluate statement STMT. If the statement produces a useful range,
return SSA_PROP_INTERESTING and record the SSA name with the
interesting range into *OUTPUT_P.
|| ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
return vrp_visit_assignment (stmt, output_p);
}
- else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
+ else if (TREE_CODE (stmt) == COND_EXPR)
return vrp_visit_cond_stmt (stmt, taken_edge_p);
+ else if (TREE_CODE (stmt) == SWITCH_EXPR)
+ return vrp_visit_switch_stmt (stmt, taken_edge_p);
/* All other statements produce nothing of interest for VRP, so mark
their outputs varying and prevent further simulation. */
{
bool sop = false;
- val = compare_range_with_value (GT_EXPR, vr, integer_zero_node, &sop);
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
if (val
&& sop
}
}
+/* Simplify a switch statement using the value range of the switch
+ argument. */
+
+static void
+simplify_switch_using_ranges (tree stmt)
+{
+ tree op = TREE_OPERAND (stmt, 0);
+ value_range_t *vr;
+ bool take_default;
+ edge e;
+ edge_iterator ei;
+ size_t i = 0, j = 0, n, n2;
+ tree vec, vec2;
+ switch_update su;
+
+ if (TREE_CODE (op) != SSA_NAME)
+ return;
+
+ vr = get_value_range (op);
+
+ /* We can only handle integer ranges. */
+ if (vr->type != VR_RANGE
+ || symbolic_range_p (vr))
+ return;
+
+ /* Find case label for min/max of the value range. */
+ vec = SWITCH_LABELS (stmt);
+ n = TREE_VEC_LENGTH (vec);
+ take_default = !find_case_label_index (vec, 0, vr->min, &i);
+ take_default |= !find_case_label_index (vec, i, vr->max, &j);
+
+ /* If the case label range is continuous, we do not need to
+ preserve the default case label. Verify that. */
+ if (!take_default && j > i)
+ {
+ tree low, high;
+ size_t k;
+
+ high = CASE_LOW (TREE_VEC_ELT (vec, i));
+ if (CASE_HIGH (TREE_VEC_ELT (vec, i)))
+ high = CASE_HIGH (TREE_VEC_ELT (vec, i));
+ for (k = i + 1; k <= j; ++k)
+ {
+ low = CASE_LOW (TREE_VEC_ELT (vec, k));
+ if (!integer_onep (int_const_binop (MINUS_EXPR, low, high, 0)))
+ {
+ take_default = true;
+ break;
+ }
+ high = low;
+ if (CASE_HIGH (TREE_VEC_ELT (vec, k)))
+ high = CASE_HIGH (TREE_VEC_ELT (vec, k));
+ }
+ }
+
+ /* Bail out if this is just all edges taken. */
+ if (i == 0
+ && j == n - 2
+ && take_default)
+ return;
+
+ /* Build a new vector of taken case labels. */
+ vec2 = make_tree_vec (j - i + 1 + (int)take_default);
+ for (n2 = 0; i <= j; ++i, ++n2)
+ TREE_VEC_ELT (vec2, n2) = TREE_VEC_ELT (vec, i);
+
+ /* Add the default edge, if necessary. */
+ if (take_default)
+ TREE_VEC_ELT (vec2, n2++) = TREE_VEC_ELT (vec, n - 1);
+
+ /* Mark needed edges. */
+ for (i = 0; i < n2; ++i)
+ {
+ e = find_edge (bb_for_stmt (stmt),
+ label_to_block (CASE_LABEL (TREE_VEC_ELT (vec2, i))));
+ e->aux = (void *)-1;
+ }
+
+ /* Queue not needed edges for later removal. */
+ FOR_EACH_EDGE (e, ei, bb_for_stmt (stmt)->succs)
+ {
+ if (e->aux == (void *)-1)
+ {
+ e->aux = NULL;
+ continue;
+ }
+
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "removing unreachable case label\n");
+ }
+ VEC_safe_push (edge, heap, to_remove_edges, e);
+ }
+
+ /* And queue an update for the stmt. */
+ su.stmt = stmt;
+ su.vec = vec2;
+ VEC_safe_push (switch_update, heap, to_update_switch_stmts, &su);
+}
+
/* Simplify STMT using ranges if possible. */
void
}
else if (TREE_CODE (stmt) == COND_EXPR
&& COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
- {
- simplify_cond_using_ranges (stmt);
- }
+ simplify_cond_using_ranges (stmt);
+ else if (TREE_CODE (stmt) == SWITCH_EXPR)
+ simplify_switch_using_ranges (stmt);
}
/* Stack of dest,src equivalency pairs that need to be restored after
{
basic_block bb;
tree dummy;
+ int i;
+ edge e;
/* Ugh. When substituting values earlier in this pass we can
wipe the dominance information. So rebuild the dominator
recompute it. */
mark_dfs_back_edges ();
+ /* Do not thread across edges we are about to remove. Just marking
+ them as EDGE_DFS_BACK will do. */
+ for (i = 0; VEC_iterate (edge, to_remove_edges, i, e); ++i)
+ e->flags |= EDGE_DFS_BACK;
+
/* Allocate our unwinder stack to unwind any temporary equivalences
that might be recorded. */
stack = VEC_alloc (tree, heap, 20);
&& INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
{
edge_iterator ei;
- edge e;
/* We've got a block with multiple predecessors and multiple
successors which also ends in a suitable conditional. For
vr_phi_edge_counts = NULL;
}
+/* Calculates number of iterations for all loops, to ensure that they are
+ cached. */
+
+static void
+record_numbers_of_iterations (void)
+{
+ loop_iterator li;
+ struct loop *loop;
+
+ FOR_EACH_LOOP (li, loop, 0)
+ {
+ number_of_latch_executions (loop);
+ }
+}
/* Main entry point to VRP (Value Range Propagation). This pass is
loosely based on J. R. C. Patterson, ``Accurate Static Branch
static unsigned int
execute_vrp (void)
{
+ int i;
+ edge e;
+ switch_update *su;
+
loop_optimizer_init (LOOPS_NORMAL | LOOPS_HAVE_RECORDED_EXITS);
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
scev_initialize ();
insert_range_assertions ();
+ /* Compute the # of iterations for each loop before we start the VRP
+ analysis. The value ranges determined by VRP are used in expression
+ simplification, that is also used by the # of iterations analysis.
+ However, in the middle of the VRP analysis, the value ranges do not take
+ all the possible paths in CFG into account, so they do not have to be
+ correct, and the # of iterations analysis can obtain wrong results.
+ This is a problem, since the results of the # of iterations analysis
+ are cached, so these mistakes would not be corrected when the value
+ ranges are corrected. */
+ record_numbers_of_iterations ();
+
+ to_remove_edges = VEC_alloc (edge, heap, 10);
+ to_update_switch_stmts = VEC_alloc (switch_update, heap, 5);
+
vrp_initialize ();
ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
vrp_finalize ();
+ /* Remove dead edges from SWITCH_EXPR optimization. This leaves the
+ CFG in a broken state and requires a cfg_cleanup run. */
+ for (i = 0; VEC_iterate (edge, to_remove_edges, i, e); ++i)
+ remove_edge (e);
+ /* Update SWITCH_EXPR case label vector. */
+ for (i = 0; VEC_iterate (switch_update, to_update_switch_stmts, i, su); ++i)
+ SWITCH_LABELS (su->stmt) = su->vec;
+
+ if (VEC_length (edge, to_remove_edges) > 0)
+ free_dominance_info (CDI_DOMINATORS);
+
+ VEC_free (edge, heap, to_remove_edges);
+ VEC_free (switch_update, heap, to_update_switch_stmts);
+
/* ASSERT_EXPRs must be removed before finalizing jump threads
as finalizing jump threads calls the CFG cleanup code which
does not properly handle ASSERT_EXPRs. */
return flag_tree_vrp != 0;
}
-struct tree_opt_pass pass_vrp =
+struct gimple_opt_pass pass_vrp =
{
+ {
+ GIMPLE_PASS,
"vrp", /* name */
gate_vrp, /* gate */
execute_vrp, /* execute */
| TODO_ggc_collect
| TODO_verify_ssa
| TODO_dump_func
- | TODO_update_ssa, /* todo_flags_finish */
- 0 /* letter */
+ | TODO_update_ssa /* todo_flags_finish */
+ }
};
OSDN Git Service
