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;
};
of values that SSA name N_I may take. */
static value_range_t **vr_value;
+/* For a PHI node which sets SSA name N_I, VR_COUNTS[I] holds the
+ number of executable edges we saw the last time we visited the
+ 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
+ the same value with TREE_OVERFLOW clear. This can be used to avoid
+ confusing a regular value with an overflow value. */
+
+static inline tree
+avoid_overflow_infinity (tree val)
+{
+ if (!is_overflow_infinity (val))
+ return val;
+
+ if (vrp_val_is_max (val))
+ return vrp_val_max (TREE_TYPE (val));
+ else
+ {
+#ifdef ENABLE_CHECKING
+ gcc_assert (vrp_val_is_min (val));
+#endif
+ return vrp_val_min (TREE_TYPE (val));
+ }
}
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
gcc_assert (min && max);
if (INTEGRAL_TYPE_P (TREE_TYPE (min)) && t == VR_ANTI_RANGE)
- gcc_assert ((min != TYPE_MIN_VALUE (TREE_TYPE (min))
- && !is_negative_overflow_infinity (min))
- || (max != TYPE_MAX_VALUE (TREE_TYPE (max))
- && !is_positive_overflow_infinity (max)));
+ gcc_assert (!vrp_val_is_min (min) || !vrp_val_is_max (max));
cmp = compare_values (min, max);
gcc_assert (cmp == 0 || cmp == -1 || cmp == -2);
+
+ if (needs_overflow_infinity (TREE_TYPE (min)))
+ gcc_assert (!is_overflow_infinity (min)
+ || !is_overflow_infinity (max));
}
if (t == VR_UNDEFINED || t == VR_VARYING)
/* Since updating the equivalence set involves deep copying the
bitmaps, only do it if absolutely necessary. */
- if (vr->equiv == NULL)
+ if (vr->equiv == NULL
+ && equiv != NULL)
vr->equiv = BITMAP_ALLOC (NULL);
if (equiv != vr->equiv)
}
+/* 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 void
+set_and_canonicalize_value_range (value_range_t *vr, enum value_range_type t,
+ tree min, tree max, bitmap 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;
+
+ /* 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, from->type, from->min, from->max, from->equiv);
}
-
-/* Set value range VR to VR_VARYING. */
+/* Set value range VR to a single value. This function is only called
+ with values we get from statements, and exists to clear the
+ TREE_OVERFLOW flag so that we don't think we have an overflow
+ infinity when we shouldn't. */
static inline void
-set_value_range_to_varying (value_range_t *vr)
+set_value_range_to_value (value_range_t *vr, tree val, bitmap equiv)
{
- vr->type = VR_VARYING;
- vr->min = vr->max = NULL_TREE;
- if (vr->equiv)
- bitmap_clear (vr->equiv);
+ gcc_assert (is_gimple_min_invariant (val));
+ val = avoid_overflow_infinity (val);
+ set_value_range (vr, VR_RANGE, val, val, equiv);
}
/* Set value range VR to a non-negative range of type TYPE.
- OVERFLOW_INFINITY indicates whether to use a overflow infinity
+ OVERFLOW_INFINITY indicates whether to use an overflow infinity
rather than TYPE_MAX_VALUE; this should be true if we determine
that the range is nonnegative based on the assumption that signed
overflow does not occur. */
static inline void
set_value_range_to_null (value_range_t *vr, tree type)
{
- tree zero = build_int_cst (type, 0);
- set_value_range (vr, VR_RANGE, zero, zero, vr->equiv);
+ set_value_range_to_value (vr, build_int_cst (type, 0), vr->equiv);
}
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;
/* Create a default value range. */
vr_value[ver] = vr = XCNEW (value_range_t);
- /* Allocate an equivalence set. */
- vr->equiv = BITMAP_ALLOC (NULL);
+ /* Defer allocating the equivalence set. */
+ vr->equiv = NULL;
/* If VAR is a default definition, the variable can take any value
in VAR's type. */
/* 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;
new_vr->equiv);
BITMAP_FREE (new_vr->equiv);
- new_vr->equiv = NULL;
return is_new;
}
-/* Add VAR and VAR's equivalence set to EQUIV. */
+/* Add VAR and VAR's equivalence set to EQUIV. This is the central
+ 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];
- bitmap_set_bit (equiv, ver);
+ if (*equiv == NULL)
+ *equiv = BITMAP_ALLOC (NULL);
+ bitmap_set_bit (*equiv, ver);
if (vr && vr->equiv)
- bitmap_ior_into (equiv, vr->equiv);
+ bitmap_ior_into (*equiv, vr->equiv);
}
|| !is_gimple_min_invariant (vr->max));
}
-/* Return true if value range VR uses a overflow infinity. */
+/* Return true if value range VR uses an overflow infinity. */
static inline bool
overflow_infinity_range_p (value_range_t *vr)
fold_undefer_and_ignore_overflow_warnings ();
- if (!tcmp)
+ if (!tcmp
+ || TREE_CODE (tcmp) != INTEGER_CST)
return -2;
if (!integer_zerop (tcmp))
both integers. */
gcc_assert (POINTER_TYPE_P (TREE_TYPE (val1))
== POINTER_TYPE_P (TREE_TYPE (val2)));
+ /* Convert the two values into the same type. This is needed because
+ sizetype causes sign extension even for unsigned types. */
+ val2 = fold_convert (TREE_TYPE (val1), val2);
+ STRIP_USELESS_TYPE_CONVERSION (val2);
if ((TREE_CODE (val1) == SSA_NAME
|| TREE_CODE (val1) == PLUS_EXPR
if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)))
return -2;
- if (strict_overflow_p != NULL)
+ if (strict_overflow_p != NULL
+ && (code1 == SSA_NAME || !TREE_NO_WARNING (val1))
+ && (code2 == SSA_NAME || !TREE_NO_WARNING (val2)))
*strict_overflow_p = true;
if (code1 == SSA_NAME)
|| 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);
+
type = TREE_TYPE (limit);
gcc_assert (limit != var);
predicates, we will need to trim the set of equivalences before
we are done. */
gcc_assert (vr_p->equiv == NULL);
- vr_p->equiv = BITMAP_ALLOC (NULL);
- add_equivalence (vr_p->equiv, var);
+ add_equivalence (&vr_p->equiv, var);
/* Extract a new range based on the asserted comparison for VAR and
LIMIT's value range. Notice that if LIMIT has an anti-range, we
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;
SSA name, the new range will also inherit the equivalence set
from LIMIT. */
if (TREE_CODE (limit) == SSA_NAME)
- add_equivalence (vr_p->equiv, limit);
+ add_equivalence (&vr_p->equiv, limit);
}
else if (cond_code == NE_EXPR)
{
/* If MIN and MAX cover the whole range for their type, then
just use the original LIMIT. */
if (INTEGRAL_TYPE_P (type)
- && (min == TYPE_MIN_VALUE (type)
- || is_negative_overflow_infinity (min))
- && (max == TYPE_MAX_VALUE (type)
- || is_positive_overflow_infinity (max)))
+ && vrp_val_is_min (min)
+ && vrp_val_is_max (max))
min = max = limit;
set_value_range (vr_p, VR_ANTI_RANGE, min, max, vr_p->equiv);
{
tree one = build_int_cst (type, 1);
max = fold_build2 (MINUS_EXPR, type, max, one);
+ if (EXPR_P (max))
+ TREE_NO_WARNING (max) = 1;
}
set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
{
tree one = build_int_cst (type, 1);
min = fold_build2 (PLUS_EXPR, type, min, one);
+ if (EXPR_P (min))
+ TREE_NO_WARNING (min) = 1;
}
set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
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. */
{
gcc_assert (!is_positive_overflow_infinity (anti_max));
if (needs_overflow_infinity (TREE_TYPE (anti_max))
- && anti_max == TYPE_MAX_VALUE (TREE_TYPE (anti_max)))
+ && vrp_val_is_max (anti_max))
{
if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
{
}
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);
}
{
gcc_assert (!is_negative_overflow_infinity (anti_min));
if (needs_overflow_infinity (TREE_TYPE (anti_min))
- && anti_min == TYPE_MIN_VALUE (TREE_TYPE (anti_min)))
+ && vrp_val_is_min (anti_min))
{
if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
{
}
max = negative_overflow_infinity (TREE_TYPE (var_vr->min));
}
- else
+ else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
anti_min,
build_int_cst (TREE_TYPE (var_vr->min), 1));
+ else
+ max = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (var_vr->min),
+ anti_min,
+ size_int (-1));
min = real_min;
set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
}
else
set_value_range (vr, VR_RANGE, var, var, NULL);
- add_equivalence (vr->equiv, var);
+ add_equivalence (&vr->equiv, var);
}
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 };
meaningful way. Handle only arithmetic operations. */
if (code != PLUS_EXPR
&& code != MINUS_EXPR
+ && code != POINTER_PLUS_EXPR
&& code != MULT_EXPR
&& code != TRUNC_DIV_EXPR
&& code != FLOOR_DIV_EXPR
&& 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))
- set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
+ set_value_range_to_value (&vr0, op0, NULL);
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))
- set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
+ set_value_range_to_value (&vr1, op1, NULL);
else
set_value_range_to_varying (&vr1);
}
/* 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)))
{
- /* For pointer types, we are really only interested in asserting
- whether the expression evaluates to non-NULL. FIXME, we used
- to gcc_assert (code == PLUS_EXPR || code == MINUS_EXPR), but
- ivopts is generating expressions with pointer multiplication
- in them. */
- if (code == PLUS_EXPR)
+ if (code == MIN_EXPR || code == MAX_EXPR)
{
- if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
- set_value_range_to_nonnull (vr, TREE_TYPE (expr));
+ /* For MIN/MAX expressions with pointers, we only care about
+ nullness, if both are non null, then the result is nonnull.
+ 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, 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);
+
+ return;
}
+ gcc_assert (code == POINTER_PLUS_EXPR);
+ /* 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, expr_type);
+ else if (range_is_null (&vr0) && range_is_null (&vr1))
+ set_value_range_to_null (vr, expr_type);
else
- {
- /* Subtracting from a pointer, may yield 0, so just drop the
- resulting range to varying. */
- set_value_range_to_varying (vr);
- }
+ set_value_range_to_varying (vr);
return;
}
/* 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;
}
}
/* If we have a RSHIFT_EXPR with any shift values outside [0..prec-1],
then drop to VR_VARYING. Outside of this range we get undefined
- behaviour from the shift operation. We cannot even trust
+ behavior from the shift operation. We cannot even trust
SHIFT_COUNT_TRUNCATED at this stage, because that applies to rtl
shifts, and the operation at the tree level may be widened. */
if (code == RSHIFT_EXPR)
|| !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
We learn nothing when we have INF and INF(OVF) on both sides.
Note that we do accept [-INF, -INF] and [+INF, +INF] without
overflow. */
- if ((min == TYPE_MIN_VALUE (TREE_TYPE (min))
- || is_overflow_infinity (min))
- && (max == TYPE_MAX_VALUE (TREE_TYPE (max))
- || is_overflow_infinity (max)))
+ if ((vrp_val_is_min (min) || is_overflow_infinity (min))
+ && (vrp_val_is_max (max) || is_overflow_infinity (max)))
{
set_value_range_to_varying (vr);
return;
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))
- set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
+ set_value_range_to_value (&vr0, op0, NULL);
else
set_value_range_to_varying (&vr0);
/* 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)
- && (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));
- else if (vr0.max != TYPE_MIN_VALUE (TREE_TYPE (expr)))
- min = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
- else if (needs_overflow_infinity (TREE_TYPE (expr)))
+ min = positive_overflow_infinity (type);
+ else if (!vrp_val_is_min (vr0.max))
+ min = fold_unary_to_constant (code, type, vr0.max);
+ else if (needs_overflow_infinity (type))
{
- if (supports_overflow_infinity (TREE_TYPE (expr)))
- min = positive_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 (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));
- else if (vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr)))
- max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
- else if (needs_overflow_infinity (TREE_TYPE (expr)))
+ max = positive_overflow_infinity (type);
+ else if (!vrp_val_is_min (vr0.min))
+ 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
- && vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
+ && vrp_val_is_min (vr0.min))
|| (vr0.type == VR_ANTI_RANGE
- && vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr))
+ && !vrp_val_is_min (vr0.min)
&& !range_includes_zero_p (&vr0))))
{
set_value_range_to_varying (vr);
/* 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));
- else if (vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr)))
- 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 = positive_overflow_infinity (type);
+ else if (!vrp_val_is_min (vr0.min))
+ 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));
- else if (vr0.max != TYPE_MIN_VALUE (TREE_TYPE (expr)))
- 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 = positive_overflow_infinity (type);
+ else if (!vrp_val_is_min (vr0.max))
+ 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);
+
+ /* If both sides have overflowed, we don't know
+ anything. */
+ if ((is_overflow_infinity (vr0.min)
+ || TREE_OVERFLOW (min))
+ && (is_overflow_infinity (vr0.max)
+ || TREE_OVERFLOW (max)))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
if (is_overflow_infinity (vr0.min))
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)));
if (TREE_CODE (op0) == SSA_NAME)
vr0 = *(get_value_range (op0));
else if (is_gimple_min_invariant (op0))
- set_value_range (&vr0, VR_RANGE, op0, op0, NULL);
+ set_value_range_to_value (&vr0, op0, NULL);
else
set_value_range_to_varying (&vr0);
if (TREE_CODE (op1) == SSA_NAME)
vr1 = *(get_value_range (op1));
else if (is_gimple_min_invariant (op1))
- set_value_range (&vr1, VR_RANGE, op1, op1, NULL);
+ set_value_range_to_value (&vr1, op1, NULL);
else
set_value_range_to_varying (&vr1);
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);
- set_value_range (vr, VR_RANGE, val, val, vr->equiv);
+ val = fold_convert (type, val);
+ if (is_gimple_min_invariant (val))
+ set_value_range_to_value (vr, val, vr->equiv);
+ else
+ set_value_range (vr, VR_RANGE, val, val, vr->equiv);
}
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 (vr, VR_RANGE, expr, expr, NULL);
+ set_value_range_to_value (vr, expr, NULL);
else
set_value_range_to_varying (vr);
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;
if (compare_values (min, max) == 1)
return;
}
+
+ /* According to the loop information, the variable does not
+ overflow. If we think it does, probably because of an
+ overflow due to arithmetic on a different INF value,
+ reset now. */
+ if (is_negative_overflow_infinity (min))
+ min = tmin;
}
else
{
if (compare_values (min, max) == 1)
return;
}
+
+ if (is_positive_overflow_infinity (max))
+ max = tmax;
}
set_value_range (vr, VR_RANGE, min, max, vr->equiv);
}
}
+/* Return true if VAR may overflow at STMT. This checks any available
+ loop information to see if we can determine that VAR does not
+ overflow. */
+
+static bool
+vrp_var_may_overflow (tree var, tree stmt)
+{
+ struct loop *l;
+ tree chrec, init, step;
+
+ if (current_loops == NULL)
+ return true;
+
+ l = loop_containing_stmt (stmt);
+ if (l == NULL)
+ return true;
+
+ chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var));
+ if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
+ return true;
+
+ init = initial_condition_in_loop_num (chrec, l->num);
+ step = evolution_part_in_loop_num (chrec, l->num);
+
+ if (step == NULL_TREE
+ || !is_gimple_min_invariant (step)
+ || !valid_value_p (init))
+ return true;
+
+ /* If we get here, we know something useful about VAR based on the
+ loop information. If it wraps, it may overflow. */
+
+ if (scev_probably_wraps_p (init, step, stmt, get_chrec_loop (chrec),
+ true))
+ return true;
+
+ if (dump_file && (dump_flags & TDF_DETAILS) != 0)
+ {
+ print_generic_expr (dump_file, var, 0);
+ fprintf (dump_file, ": loop information indicates does not overflow\n");
+ }
+
+ return false;
+}
+
/* Given two numeric value ranges VR0, VR1 and a comparison code COMP:
fprintf (file, "%s[", (vr->type == VR_ANTI_RANGE) ? "~" : "");
- if (INTEGRAL_TYPE_P (type)
- && !TYPE_UNSIGNED (type)
- && vr->min == TYPE_MIN_VALUE (type))
- fprintf (file, "-INF");
- else if (needs_overflow_infinity (type)
- && is_negative_overflow_infinity (vr->min))
+ if (is_negative_overflow_infinity (vr->min))
fprintf (file, "-INF(OVF)");
+ else if (INTEGRAL_TYPE_P (type)
+ && !TYPE_UNSIGNED (type)
+ && vrp_val_is_min (vr->min))
+ fprintf (file, "-INF");
else
print_generic_expr (file, vr->min, 0);
fprintf (file, ", ");
- if (INTEGRAL_TYPE_P (type)
- && vr->max == TYPE_MAX_VALUE (type))
- fprintf (file, "+INF");
- else if (needs_overflow_infinity (type)
- && is_positive_overflow_infinity (vr->max))
+ if (is_positive_overflow_infinity (vr->max))
fprintf (file, "+INF(OVF)");
+ else if (INTEGRAL_TYPE_P (type)
+ && vrp_val_is_max (vr->max))
+ fprintf (file, "+INF");
else
print_generic_expr (file, vr->max, 0);
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;
+
+ /* 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);
- /* VRP does not handle float types. */
- if (SCALAR_FLOAT_TYPE_P (TREE_TYPE (val)))
- return false;
+ 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;
+ }
- /* 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 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
}
}
+/* Searches if the expr T, located at LOCATION computes
+ address of an ARRAY_REF, and call check_array_ref on it. */
+
+static void
+search_for_addr_array(tree t, location_t* location)
+{
+ while (TREE_CODE (t) == SSA_NAME)
+ {
+ t = SSA_NAME_DEF_STMT (t);
+ if (TREE_CODE (t) != GIMPLE_MODIFY_STMT)
+ return;
+ t = GIMPLE_STMT_OPERAND (t, 1);
+ }
+
+
+ /* We are only interested in addresses of ARRAY_REF's. */
+ if (TREE_CODE (t) != ADDR_EXPR)
+ return;
+
+ /* Check each ARRAY_REFs in the reference chain. */
+ do
+ {
+ if (TREE_CODE (t) == ARRAY_REF)
+ check_array_ref (t, location, true /*ignore_off_by_one*/);
+
+ t = TREE_OPERAND(t,0);
+ }
+ while (handled_component_p (t));
+}
+
/* walk_tree() callback that checks if *TP is
an ARRAY_REF inside an ADDR_EXPR (in which an array
subscript one outside the valid range is allowed). Call
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)
check_array_ref (t, location, false /*ignore_off_by_one*/);
- else if (TREE_CODE (t) == ADDR_EXPR)
- {
- use_operand_p op;
- tree use_stmt;
- t = TREE_OPERAND (t, 0);
-
- /* Don't warn on statements like
-
- ssa_name = 500 + &array[-200]
-
- or
- ssa_name = &array[-200]
- other_name = ssa_name + 300;
-
- which are sometimes
- produced by other optimizing passes. */
-
- if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
- && BINARY_CLASS_P (GIMPLE_STMT_OPERAND (stmt, 1)))
- *walk_subtree = FALSE;
-
- if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
- && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 0)) == SSA_NAME
- && single_imm_use (GIMPLE_STMT_OPERAND (stmt, 0), &op, &use_stmt)
- && TREE_CODE (use_stmt) == GIMPLE_MODIFY_STMT
- && BINARY_CLASS_P (GIMPLE_STMT_OPERAND (use_stmt, 1)))
- *walk_subtree = FALSE;
+ if (TREE_CODE (t) == INDIRECT_REF
+ || (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)))
+ search_for_addr_array (TREE_OPERAND (t, 0), location);
+ else if (TREE_CODE (t) == CALL_EXPR)
+ {
+ tree arg;
+ call_expr_arg_iterator iter;
- while (*walk_subtree && handled_component_p (t))
- {
- if (TREE_CODE (t) == ARRAY_REF)
- check_array_ref (t, location, true /*ignore_off_by_one*/);
- t = TREE_OPERAND (t, 0);
- }
- *walk_subtree = FALSE;
+ FOR_EACH_CALL_EXPR_ARG (arg, iter, t)
+ search_for_addr_array (arg, location);
}
+ if (TREE_CODE (t) == ADDR_EXPR)
+ *walk_subtree = FALSE;
+
return NULL_TREE;
}
basic_block bb;
vr_value = XCNEWVEC (value_range_t *, num_ssa_names);
+ vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names);
FOR_EACH_BB (bb)
{
return SSA_PROP_VARYING;
}
+/* Helper that gets the value range of the SSA_NAME with version I
+ or a symbolic range containing the SSA_NAME only if the value range
+ is varying or undefined. */
+
+static inline value_range_t
+get_vr_for_comparison (int i)
+{
+ value_range_t vr = *(vr_value[i]);
+
+ /* If name N_i does not have a valid range, use N_i as its own
+ range. This allows us to compare against names that may
+ have N_i in their ranges. */
+ if (vr.type == VR_VARYING || vr.type == VR_UNDEFINED)
+ {
+ vr.type = VR_RANGE;
+ vr.min = ssa_name (i);
+ vr.max = ssa_name (i);
+ }
+
+ return vr;
+}
/* Compare all the value ranges for names equivalent to VAR with VAL
using comparison code COMP. Return the same value returned by
bitmap e;
tree retval, t;
int used_strict_overflow;
-
- t = retval = NULL_TREE;
+ bool sop;
+ value_range_t equiv_vr;
/* Get the set of equivalences for VAR. */
e = get_value_range (var)->equiv;
- /* Add VAR to its own set of equivalences so that VAR's value range
- is processed by this loop (otherwise, we would have to replicate
- the body of the loop just to check VAR's value range). */
- bitmap_set_bit (e, SSA_NAME_VERSION (var));
-
/* Start at -1. Set it to 0 if we do a comparison without relying
on overflow, or 1 if all comparisons rely on overflow. */
used_strict_overflow = -1;
- EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
- {
- bool sop;
-
- value_range_t equiv_vr = *(vr_value[i]);
+ /* Compare vars' value range with val. */
+ equiv_vr = get_vr_for_comparison (SSA_NAME_VERSION (var));
+ sop = false;
+ retval = compare_range_with_value (comp, &equiv_vr, val, &sop);
+ if (retval)
+ used_strict_overflow = sop ? 1 : 0;
- /* If name N_i does not have a valid range, use N_i as its own
- range. This allows us to compare against names that may
- have N_i in their ranges. */
- if (equiv_vr.type == VR_VARYING || equiv_vr.type == VR_UNDEFINED)
- {
- equiv_vr.type = VR_RANGE;
- equiv_vr.min = ssa_name (i);
- equiv_vr.max = ssa_name (i);
- }
+ /* If the equiv set is empty we have done all work we need to do. */
+ if (e == NULL)
+ {
+ if (retval
+ && used_strict_overflow > 0)
+ *strict_overflow_p = true;
+ return retval;
+ }
+ EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
+ {
+ equiv_vr = get_vr_for_comparison (i);
sop = false;
t = compare_range_with_value (comp, &equiv_vr, val, &sop);
if (t)
}
}
- /* Remove VAR from its own equivalence set. */
- bitmap_clear_bit (e, SSA_NAME_VERSION (var));
+ if (retval
+ && used_strict_overflow > 0)
+ *strict_overflow_p = true;
- if (retval)
- {
- if (used_strict_overflow > 0)
- *strict_overflow_p = true;
- return retval;
- }
-
- /* We couldn't find a non-NULL value for the predicate. */
- return NULL_TREE;
+ return retval;
}
bitmap_iterator bi1, bi2;
unsigned i1, i2;
int used_strict_overflow;
+ static bitmap_obstack *s_obstack = NULL;
+ static bitmap s_e1 = NULL, s_e2 = NULL;
/* Compare the ranges of every name equivalent to N1 against the
ranges of every name equivalent to N2. */
e1 = get_value_range (n1)->equiv;
e2 = get_value_range (n2)->equiv;
+ /* Use the fake bitmaps if e1 or e2 are not available. */
+ if (s_obstack == NULL)
+ {
+ s_obstack = XNEW (bitmap_obstack);
+ bitmap_obstack_initialize (s_obstack);
+ s_e1 = BITMAP_ALLOC (s_obstack);
+ s_e2 = BITMAP_ALLOC (s_obstack);
+ }
+ if (e1 == NULL)
+ e1 = s_e1;
+ if (e2 == NULL)
+ e2 = s_e2;
+
/* Add N1 and N2 to their own set of equivalences to avoid
duplicating the body of the loop just to check N1 and N2
ranges. */
of the loop just to check N1 and N2 ranges. */
EXECUTE_IF_SET_IN_BITMAP (e1, 0, i1, bi1)
{
- value_range_t vr1 = *(vr_value[i1]);
-
- /* If the range is VARYING or UNDEFINED, use the name itself. */
- if (vr1.type == VR_VARYING || vr1.type == VR_UNDEFINED)
- {
- vr1.type = VR_RANGE;
- vr1.min = ssa_name (i1);
- vr1.max = ssa_name (i1);
- }
+ value_range_t vr1 = get_vr_for_comparison (i1);
t = retval = NULL_TREE;
EXECUTE_IF_SET_IN_BITMAP (e2, 0, i2, bi2)
{
- bool sop;
-
- value_range_t vr2 = *(vr_value[i2]);
+ bool sop = false;
- if (vr2.type == VR_VARYING || vr2.type == VR_UNDEFINED)
- {
- vr2.type = VR_RANGE;
- vr2.min = ssa_name (i2);
- vr2.max = ssa_name (i2);
- }
+ value_range_t vr2 = get_vr_for_comparison (i2);
t = compare_ranges (comp, &vr1, &vr2, &sop);
if (t)
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. */
else
goto give_up;
+ /* Check for useless ranges. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (min))
+ && ((vrp_val_is_min (min) || is_overflow_infinity (min))
+ && (vrp_val_is_max (max) || is_overflow_infinity (max))))
+ goto give_up;
+
/* The resulting set of equivalences is the intersection of
the two sets. */
if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
tree lhs = PHI_RESULT (phi);
value_range_t *lhs_vr = get_value_range (lhs);
value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
- bool all_const = true;
+ int edges, old_edges;
copy_value_range (&vr_result, lhs_vr);
print_generic_expr (dump_file, phi, dump_flags);
}
+ edges = 0;
for (i = 0; i < PHI_NUM_ARGS (phi); i++)
{
edge e = PHI_ARG_EDGE (phi, i);
tree arg = PHI_ARG_DEF (phi, i);
value_range_t vr_arg;
+ ++edges;
+
if (TREE_CODE (arg) == SSA_NAME)
{
vr_arg = *(get_value_range (arg));
- all_const = false;
}
else
{
+ if (is_overflow_infinity (arg))
+ {
+ arg = copy_node (arg);
+ TREE_OVERFLOW (arg) = 0;
+ }
+
vr_arg.type = VR_RANGE;
vr_arg.min = arg;
vr_arg.max = arg;
if (vr_result.type == VR_VARYING)
goto varying;
+ old_edges = vr_phi_edge_counts[SSA_NAME_VERSION (lhs)];
+ vr_phi_edge_counts[SSA_NAME_VERSION (lhs)] = edges;
+
/* To prevent infinite iterations in the algorithm, derive ranges
when the new value is slightly bigger or smaller than the
- previous one. */
+ previous one. We don't do this if we have seen a new executable
+ edge; this helps us avoid an overflow infinity for conditionals
+ which are not in a loop. */
if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE
- && !all_const)
+ && edges <= old_edges)
{
if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
{
{
/* If we will end up with a (-INF, +INF) range, set it
to VARYING. */
- if (is_positive_overflow_infinity (vr_result.max)
- || (vr_result.max
- == TYPE_MAX_VALUE (TREE_TYPE (vr_result.max))))
+ if (vrp_val_is_max (vr_result.max))
goto varying;
- if (!needs_overflow_infinity (TREE_TYPE (vr_result.min)))
+ if (!needs_overflow_infinity (TREE_TYPE (vr_result.min))
+ || !vrp_var_may_overflow (lhs, phi))
vr_result.min = TYPE_MIN_VALUE (TREE_TYPE (vr_result.min));
else if (supports_overflow_infinity (TREE_TYPE (vr_result.min)))
vr_result.min =
{
/* If we will end up with a (-INF, +INF) range, set it
to VARYING. */
- if (is_negative_overflow_infinity (vr_result.min)
- || (vr_result.min
- == TYPE_MIN_VALUE (TREE_TYPE (vr_result.min))))
+ if (vrp_val_is_min (vr_result.min))
goto varying;
- if (!needs_overflow_infinity (TREE_TYPE (vr_result.max)))
+ if (!needs_overflow_infinity (TREE_TYPE (vr_result.max))
+ || !vrp_var_may_overflow (lhs, phi))
vr_result.max = TYPE_MAX_VALUE (TREE_TYPE (vr_result.max));
else if (supports_overflow_infinity (TREE_TYPE (vr_result.max)))
vr_result.max =
{
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
{
tree one = build_int_cst (TREE_TYPE (op0), 1);
max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
+ if (EXPR_P (max))
+ TREE_NO_WARNING (max) = 1;
}
}
else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
{
tree one = build_int_cst (TREE_TYPE (op0), 1);
min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
+ if (EXPR_P (min))
+ TREE_NO_WARNING (min) = 1;
}
}
}
}
+/* 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
static void
finalize_jump_threads (void)
{
- bool cfg_altered = false;
- cfg_altered = thread_through_all_blocks ();
-
- /* If we threaded jumps, then we need to recompute the dominance
- information. */
- if (cfg_altered)
- free_dominance_info (CDI_DOMINATORS);
+ thread_through_all_blocks (false);
VEC_free (tree, heap, stack);
}
free (single_val_range);
free (vr_value);
+ free (vr_phi_edge_counts);
/* So that we can distinguish between VRP data being available
and not available. */
vr_value = NULL;
+ 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 ();
- loop_optimizer_init (LOOPS_NORMAL);
- if (current_loops)
- scev_initialize ();
+ /* 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 ();
- if (current_loops)
- {
- scev_finalize ();
- loop_optimizer_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
update_ssa (TODO_update_ssa);
finalize_jump_threads ();
+ scev_finalize ();
+ loop_optimizer_finalize ();
+
return 0;
}
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
