/* Support routines for Value Range Propagation (VRP).
- Copyright (C) 2005, 2006, 2007 Free Software Foundation, Inc.
+ Copyright (C) 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>.
This file is part of GCC.
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"
#include "timevar.h"
#include "diagnostic.h"
#include "toplev.h"
+#include "intl.h"
#include "cfgloop.h"
#include "tree-scalar-evolution.h"
#include "tree-ssa-propagate.h"
#include "tree-chrec.h"
-/* Set of SSA names found during the dominator traversal of a
- sub-graph in find_assert_locations. */
-static sbitmap found_in_subgraph;
+
+/* Set of SSA names found live during the RPO traversal of the function
+ for still active basic-blocks. */
+static sbitmap *live;
+
+/* Return true if the SSA name NAME is live on the edge E. */
+
+static bool
+live_on_edge (edge e, tree name)
+{
+ return (live[e->dest->index]
+ && TEST_BIT (live[e->dest->index], SSA_NAME_VERSION (name)));
+}
/* Local functions. */
static int compare_values (tree val1, tree val2);
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_with_ops (enum tree_code,
+ tree, tree, bool, bool *,
+ bool *);
/* Location information for ASSERT_EXPRs. Each instance of this
structure describes an ASSERT_EXPR for an SSA name. Since a single
edge e;
/* Pointer to the statement that generated this assertion. */
- block_stmt_iterator si;
+ gimple_stmt_iterator si;
/* Predicate code for the ASSERT_EXPR. Must be COMPARISON_CLASS_P. */
enum tree_code comp_code;
/* Value being compared against. */
tree val;
+ /* Expression to compare. */
+ tree expr;
+
/* Next node in the linked list. */
struct assert_locus_d *next;
};
ASSERT_EXPRs for SSA name N_I should be inserted. */
static assert_locus_t *asserts_for;
-/* Set of blocks visited in find_assert_locations. Used to avoid
- visiting the same block more than once. */
-static sbitmap blocks_visited;
-
/* Value range array. After propagation, VR_VALUE[I] holds the range
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 {
+ gimple 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)));
+}
+
+/* Return whether STMT has a constant rhs that is_overflow_infinity. */
+
+static inline bool
+stmt_overflow_infinity (gimple stmt)
+{
+ if (is_gimple_assign (stmt)
+ && get_gimple_rhs_class (gimple_assign_rhs_code (stmt)) ==
+ GIMPLE_SINGLE_RHS)
+ return is_overflow_infinity (gimple_assign_rhs1 (stmt));
+ return false;
+}
+
+/* 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)
|| is_overflow_infinity (vr->max)));
}
+/* Return false if we can not make a valid comparison based on VR;
+ this will be the case if it uses an overflow infinity and overflow
+ is not undefined (i.e., -fno-strict-overflow is in effect).
+ Otherwise return true, and set *STRICT_OVERFLOW_P to true if VR
+ uses an overflow infinity. */
+
+static bool
+usable_range_p (value_range_t *vr, bool *strict_overflow_p)
+{
+ gcc_assert (vr->type == VR_RANGE);
+ if (is_overflow_infinity (vr->min))
+ {
+ *strict_overflow_p = true;
+ if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->min)))
+ return false;
+ }
+ if (is_overflow_infinity (vr->max))
+ {
+ *strict_overflow_p = true;
+ if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (vr->max)))
+ return false;
+ }
+ return true;
+}
+
+
/* Like tree_expr_nonnegative_warnv_p, but this function uses value
ranges obtained so far. */
static bool
vrp_expr_computes_nonnegative (tree expr, bool *strict_overflow_p)
{
- return tree_expr_nonnegative_warnv_p (expr, strict_overflow_p);
+ return (tree_expr_nonnegative_warnv_p (expr, strict_overflow_p)
+ || (TREE_CODE (expr) == SSA_NAME
+ && ssa_name_nonnegative_p (expr)));
+}
+
+/* Return true if the result of assignment STMT is know to be non-negative.
+ If the return value is based on the assumption that signed overflow is
+ undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
+ *STRICT_OVERFLOW_P.*/
+
+static bool
+gimple_assign_nonnegative_warnv_p (gimple stmt, bool *strict_overflow_p)
+{
+ enum tree_code code = gimple_assign_rhs_code (stmt);
+ switch (get_gimple_rhs_class (code))
+ {
+ case GIMPLE_UNARY_RHS:
+ return tree_unary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt),
+ gimple_expr_type (stmt),
+ gimple_assign_rhs1 (stmt),
+ strict_overflow_p);
+ case GIMPLE_BINARY_RHS:
+ return tree_binary_nonnegative_warnv_p (gimple_assign_rhs_code (stmt),
+ gimple_expr_type (stmt),
+ gimple_assign_rhs1 (stmt),
+ gimple_assign_rhs2 (stmt),
+ strict_overflow_p);
+ case GIMPLE_SINGLE_RHS:
+ return tree_single_nonnegative_warnv_p (gimple_assign_rhs1 (stmt),
+ strict_overflow_p);
+ case GIMPLE_INVALID_RHS:
+ gcc_unreachable ();
+ default:
+ gcc_unreachable ();
+ }
+}
+
+/* Return true if return value of call STMT is know to be non-negative.
+ If the return value is based on the assumption that signed overflow is
+ undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
+ *STRICT_OVERFLOW_P.*/
+
+static bool
+gimple_call_nonnegative_warnv_p (gimple stmt, bool *strict_overflow_p)
+{
+ tree arg0 = gimple_call_num_args (stmt) > 0 ?
+ gimple_call_arg (stmt, 0) : NULL_TREE;
+ tree arg1 = gimple_call_num_args (stmt) > 1 ?
+ gimple_call_arg (stmt, 1) : NULL_TREE;
+
+ return tree_call_nonnegative_warnv_p (gimple_expr_type (stmt),
+ gimple_call_fndecl (stmt),
+ arg0,
+ arg1,
+ strict_overflow_p);
+}
+
+/* Return true if STMT is know to to compute a non-negative value.
+ If the return value is based on the assumption that signed overflow is
+ undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
+ *STRICT_OVERFLOW_P.*/
+
+static bool
+gimple_stmt_nonnegative_warnv_p (gimple stmt, bool *strict_overflow_p)
+{
+ switch (gimple_code (stmt))
+ {
+ case GIMPLE_ASSIGN:
+ return gimple_assign_nonnegative_warnv_p (stmt, strict_overflow_p);
+ case GIMPLE_CALL:
+ return gimple_call_nonnegative_warnv_p (stmt, strict_overflow_p);
+ default:
+ gcc_unreachable ();
+ }
+}
+
+/* Return true if the result of assignment STMT is know to be non-zero.
+ If the return value is based on the assumption that signed overflow is
+ undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
+ *STRICT_OVERFLOW_P.*/
+
+static bool
+gimple_assign_nonzero_warnv_p (gimple stmt, bool *strict_overflow_p)
+{
+ enum tree_code code = gimple_assign_rhs_code (stmt);
+ switch (get_gimple_rhs_class (code))
+ {
+ case GIMPLE_UNARY_RHS:
+ return tree_unary_nonzero_warnv_p (gimple_assign_rhs_code (stmt),
+ gimple_expr_type (stmt),
+ gimple_assign_rhs1 (stmt),
+ strict_overflow_p);
+ case GIMPLE_BINARY_RHS:
+ return tree_binary_nonzero_warnv_p (gimple_assign_rhs_code (stmt),
+ gimple_expr_type (stmt),
+ gimple_assign_rhs1 (stmt),
+ gimple_assign_rhs2 (stmt),
+ strict_overflow_p);
+ case GIMPLE_SINGLE_RHS:
+ return tree_single_nonzero_warnv_p (gimple_assign_rhs1 (stmt),
+ strict_overflow_p);
+ case GIMPLE_INVALID_RHS:
+ gcc_unreachable ();
+ default:
+ gcc_unreachable ();
+ }
+}
+
+/* Return true if STMT is know to to compute a non-zero value.
+ If the return value is based on the assumption that signed overflow is
+ undefined, set *STRICT_OVERFLOW_P to true; otherwise, don't change
+ *STRICT_OVERFLOW_P.*/
+
+static bool
+gimple_stmt_nonzero_warnv_p (gimple stmt, bool *strict_overflow_p)
+{
+ switch (gimple_code (stmt))
+ {
+ case GIMPLE_ASSIGN:
+ return gimple_assign_nonzero_warnv_p (stmt, strict_overflow_p);
+ case GIMPLE_CALL:
+ return gimple_alloca_call_p (stmt);
+ default:
+ gcc_unreachable ();
+ }
}
/* Like tree_expr_nonzero_warnv_p, but this function uses value ranges
obtained so far. */
static bool
-vrp_expr_computes_nonzero (tree expr, bool *strict_overflow_p)
+vrp_stmt_computes_nonzero (gimple stmt, bool *strict_overflow_p)
{
- if (tree_expr_nonzero_warnv_p (expr, strict_overflow_p))
+ if (gimple_stmt_nonzero_warnv_p (stmt, strict_overflow_p))
return true;
/* If we have an expression of the form &X->a, then the expression
is nonnull if X is nonnull. */
- if (TREE_CODE (expr) == ADDR_EXPR)
+ if (is_gimple_assign (stmt)
+ && gimple_assign_rhs_code (stmt) == ADDR_EXPR)
{
+ tree expr = gimple_assign_rhs1 (stmt);
tree base = get_base_address (TREE_OPERAND (expr, 0));
if (base != NULL_TREE
{
tree tcmp;
+ fold_defer_overflow_warnings ();
+
tcmp = fold_binary_to_constant (LT_EXPR, boolean_type_node, val, val2);
- if (!tcmp)
+
+ fold_undefer_and_ignore_overflow_warnings ();
+
+ 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)
infinities. */
if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
{
- if (!TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (val1)))
- return -2;
-
+ if (strict_overflow_p != NULL)
+ *strict_overflow_p = true;
if (is_negative_overflow_infinity (val1))
return is_negative_overflow_infinity (val2) ? 0 : -1;
else if (is_negative_overflow_infinity (val2))
|| 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;
}
}
}
-/* Compare values like compare_values_warnv, but treat comparisons
- which rely on undefined overflow as incomparable. */
+/* Compare values like compare_values_warnv, but treat comparisons of
+ nonconstants which rely on undefined overflow as incomparable. */
static int
compare_values (tree val1, tree val2)
sop = false;
ret = compare_values_warnv (val1, val2, &sop);
- if (sop)
+ if (sop
+ && (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2)))
ret = -2;
return ret;
}
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);
return false;
}
+/* If OP has a value range with a single constant value return that,
+ otherwise return NULL_TREE. This returns OP itself if OP is a
+ constant. */
+
+static tree
+op_with_constant_singleton_value_range (tree op)
+{
+ value_range_t *vr;
+
+ if (is_gimple_min_invariant (op))
+ return op;
+
+ if (TREE_CODE (op) != SSA_NAME)
+ return NULL_TREE;
+
+ vr = get_value_range (op);
+ if (vr->type == VR_RANGE
+ && operand_equal_p (vr->min, vr->max, 0)
+ && is_gimple_min_invariant (vr->min))
+ return vr->min;
+
+ return NULL_TREE;
+}
+
/* Extract value range information from an ASSERT_EXPR EXPR and store
it in *VR_P. */
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);
3a. If the high limit of the VR_ANTI_RANGE resides
within the VR_RANGE, then the result is a new
VR_RANGE starting at the high limit of the
- the VR_ANTI_RANGE + 1 and extending to the
+ VR_ANTI_RANGE + 1 and extending to the
high limit of the original VR_RANGE.
3b. If the low limit of the VR_ANTI_RANGE resides
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);
}
&& !supports_overflow_infinity (TREE_TYPE (res)))
return NULL_TREE;
- /* We have to punt on subtracting infinities of the same sign,
- since we can't tell what the sign of the result should
- be. */
- if (code == MINUS_EXPR
- && sgn1 == sgn2
+ /* We have to punt on adding infinities of different signs,
+ since we can't tell what the sign of the result should be.
+ Likewise for subtracting infinities of the same sign. */
+ if (((code == PLUS_EXPR && sgn1 != sgn2)
+ || (code == MINUS_EXPR && sgn1 == sgn2))
&& is_overflow_infinity (val1)
&& is_overflow_infinity (val2))
return NULL_TREE;
+ /* Don't try to handle division or shifting of infinities. */
+ if ((code == TRUNC_DIV_EXPR
+ || code == FLOOR_DIV_EXPR
+ || code == CEIL_DIV_EXPR
+ || code == EXACT_DIV_EXPR
+ || code == ROUND_DIV_EXPR
+ || code == RSHIFT_EXPR)
+ && (is_overflow_infinity (val1)
+ || is_overflow_infinity (val2)))
+ return NULL_TREE;
+
/* Notice that we only need to handle the restricted set of
operations handled by extract_range_from_binary_expr.
Among them, only multiplication, addition and subtraction
if ((code == MULT_EXPR && sgn1 == sgn2)
/* For addition, the operands must be of the same sign
to yield an overflow. Its sign is therefore that
- of one of the operands, for example the first. */
- || (code == PLUS_EXPR && sgn1 > 0)
+ of one of the operands, for example the first. For
+ infinite operands X + -INF is negative, not positive. */
+ || (code == PLUS_EXPR
+ && (sgn1 >= 0
+ ? !is_negative_overflow_infinity (val2)
+ : is_positive_overflow_infinity (val2)))
/* For subtraction, non-infinite operands must be of
different signs to yield an overflow. Its sign is
therefore that of the first operand or the opposite of
&& (sgn1 >= 0
? !is_positive_overflow_infinity (val2)
: is_negative_overflow_infinity (val2)))
+ /* We only get in here with positive shift count, so the
+ overflow direction is the same as the sign of val1.
+ Actually rshift does not overflow at all, but we only
+ handle the case of shifting overflowed -INF and +INF. */
+ || (code == RSHIFT_EXPR
+ && sgn1 >= 0)
/* For division, the only case is -INF / -1 = +INF. */
|| code == TRUNC_DIV_EXPR
|| code == FLOOR_DIV_EXPR
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 != CEIL_DIV_EXPR
&& code != EXACT_DIV_EXPR
&& code != ROUND_DIV_EXPR
+ && code != RSHIFT_EXPR
&& code != MIN_EXPR
&& code != MAX_EXPR
&& code != BIT_AND_EXPR
- && code != TRUTH_ANDIF_EXPR
- && code != TRUTH_ORIF_EXPR
+ && code != BIT_IOR_EXPR
&& code != TRUTH_AND_EXPR
&& code != TRUTH_OR_EXPR)
{
+ /* We can still do constant propagation here. */
+ tree const_op0 = op_with_constant_singleton_value_range (op0);
+ tree const_op1 = op_with_constant_singleton_value_range (op1);
+ if (const_op0 || const_op1)
+ {
+ tree tem = fold_binary (code, expr_type,
+ const_op0 ? const_op0 : op0,
+ const_op1 ? const_op1 : op1);
+ if (tem
+ && is_gimple_min_invariant (tem)
+ && !is_overflow_infinity (tem))
+ {
+ set_value_range (vr, VR_RANGE, tem, tem, NULL);
+ return;
+ }
+ }
set_value_range_to_varying (vr);
return;
}
/* 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 (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
- set_value_range_to_nonnull (vr, TREE_TYPE (expr));
+ if (code == MIN_EXPR || code == MAX_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;
}
}
|| code == FLOOR_DIV_EXPR
|| code == CEIL_DIV_EXPR
|| code == EXACT_DIV_EXPR
- || code == ROUND_DIV_EXPR)
+ || code == ROUND_DIV_EXPR
+ || code == RSHIFT_EXPR)
{
tree val[4];
size_t i;
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
+ 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)
+ {
+ if (vr1.type == VR_ANTI_RANGE
+ || !vrp_expr_computes_nonnegative (op1, &sop)
+ || (operand_less_p
+ (build_int_cst (TREE_TYPE (vr1.max),
+ TYPE_PRECISION (expr_type) - 1),
+ vr1.max) != 0))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+ }
+
/* Multiplications and divisions are a bit tricky to handle,
depending on the mix of signs we have in the two ranges, we
need to operate on different values to get the minimum and
the new range. */
/* Divisions by zero result in a VARYING value. */
- if (code != MULT_EXPR
- && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
+ else if (code != MULT_EXPR
+ && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
{
set_value_range_to_varying (vr);
return;
&& !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
return;
}
}
+ else if (code == BIT_IOR_EXPR)
+ {
+ if (vr0.type == VR_RANGE
+ && vr1.type == VR_RANGE
+ && TREE_CODE (vr0.min) == INTEGER_CST
+ && TREE_CODE (vr1.min) == INTEGER_CST
+ && TREE_CODE (vr0.max) == INTEGER_CST
+ && TREE_CODE (vr1.max) == INTEGER_CST
+ && tree_int_cst_sgn (vr0.min) >= 0
+ && tree_int_cst_sgn (vr1.min) >= 0)
+ {
+ double_int vr0_max = tree_to_double_int (vr0.max);
+ double_int vr1_max = tree_to_double_int (vr1.max);
+ double_int ior_max;
+
+ /* Set all bits to the right of the most significant one to 1.
+ For example, [0, 4] | [4, 4] = [4, 7]. */
+ ior_max.low = vr0_max.low | vr1_max.low;
+ ior_max.high = vr0_max.high | vr1_max.high;
+ if (ior_max.high != 0)
+ {
+ ior_max.low = ~0u;
+ ior_max.high |= ((HOST_WIDE_INT) 1
+ << floor_log2 (ior_max.high)) - 1;
+ }
+ else
+ ior_max.low |= ((unsigned HOST_WIDE_INT) 1u
+ << floor_log2 (ior_max.low)) - 1;
+
+ /* Both of these endpoints are conservative. */
+ min = vrp_int_const_binop (MAX_EXPR, vr0.min, vr1.min);
+ max = double_int_to_tree (expr_type, ior_max);
+ }
+ else
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+ }
else
gcc_unreachable ();
return;
}
- if ((min == TYPE_MIN_VALUE (TREE_TYPE (min))
- || is_negative_overflow_infinity (min))
- && (max == TYPE_MAX_VALUE (TREE_TYPE (max))
- || is_positive_overflow_infinity (max)))
+ /* We punt if:
+ 1) [-INF, +INF]
+ 2) [-INF, +-INF(OVF)]
+ 3) [+-INF(OVF), +INF]
+ 4) [+-INF(OVF), +-INF(OVF)]
+ 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 ((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 };
if (code == FIX_TRUNC_EXPR
|| code == FLOAT_EXPR
|| code == BIT_NOT_EXPR
- || code == NON_LVALUE_EXPR
|| code == CONJ_EXPR)
{
+ /* We can still do constant propagation here. */
+ if ((op0 = op_with_constant_singleton_value_range (op0)) != NULL_TREE)
+ {
+ tree tem = fold_unary (code, type, op0);
+ if (tem
+ && is_gimple_min_invariant (tem)
+ && !is_overflow_infinity (tem))
+ {
+ set_value_range (vr, VR_RANGE, tem, tem, NULL);
+ return;
+ }
+ }
set_value_range_to_varying (vr);
return;
}
/* 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 (CONVERT_EXPR_CODE_P (code)
+ && 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. */
+ 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))
+ {
+ vr0.type = VR_RANGE;
+ vr0.min = TYPE_MIN_VALUE (inner_type);
+ vr0.max = TYPE_MAX_VALUE (inner_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
- && !overflow_infinity_range_p (&vr0))
- || (vr0.type == VR_VARYING
- && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)))
+ || 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)))))
{
- tree new_min, new_max, orig_min, orig_max;
+ 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;
+ }
- /* 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;
- }
- }
-
- /* 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))
- {
- set_value_range_to_varying (vr);
- 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)
+ /* We shouldn't generate [+INF, +INF] as set_value_range
+ doesn't like this and ICEs. */
+ && !is_positive_overflow_infinity (min))
+ 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 (expr, false, &sop);
+ tree val;
+
+ val = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, false, &sop,
+ NULL);
/* 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);
+}
+
+/* Try to derive a nonnegative or nonzero range out of STMT relying
+ primarily on generic routines in fold in conjunction with range data.
+ Store the result in *VR */
+
+static void
+extract_range_basic (value_range_t *vr, gimple stmt)
+{
+ bool sop = false;
+ tree type = gimple_expr_type (stmt);
+
+ if (INTEGRAL_TYPE_P (type)
+ && gimple_stmt_nonnegative_warnv_p (stmt, &sop))
+ set_value_range_to_nonnegative (vr, type,
+ sop || stmt_overflow_infinity (stmt));
+ else if (vrp_stmt_computes_nonzero (stmt, &sop)
+ && !sop)
+ set_value_range_to_nonnull (vr, type);
+ else
+ set_value_range_to_varying (vr);
}
-/* Try to compute a useful range out of expression EXPR and store it
+/* Try to compute a useful range out of assignment STMT and store it
in *VR. */
static void
-extract_range_from_expr (value_range_t *vr, tree expr)
+extract_range_from_assignment (value_range_t *vr, gimple stmt)
{
- enum tree_code code = TREE_CODE (expr);
+ enum tree_code code = gimple_assign_rhs_code (stmt);
if (code == ASSERT_EXPR)
- extract_range_from_assert (vr, expr);
+ extract_range_from_assert (vr, gimple_assign_rhs1 (stmt));
else if (code == SSA_NAME)
- extract_range_from_ssa_name (vr, expr);
+ extract_range_from_ssa_name (vr, gimple_assign_rhs1 (stmt));
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, gimple_assign_rhs_code (stmt),
+ gimple_expr_type (stmt),
+ gimple_assign_rhs1 (stmt),
+ gimple_assign_rhs2 (stmt));
else if (TREE_CODE_CLASS (code) == tcc_unary)
- extract_range_from_unary_expr (vr, expr);
+ extract_range_from_unary_expr (vr, gimple_assign_rhs_code (stmt),
+ gimple_expr_type (stmt),
+ gimple_assign_rhs1 (stmt));
else if (code == COND_EXPR)
- extract_range_from_cond_expr (vr, expr);
+ extract_range_from_cond_expr (vr, gimple_assign_rhs1 (stmt));
else if (TREE_CODE_CLASS (code) == tcc_comparison)
- extract_range_from_comparison (vr, expr);
- else if (is_gimple_min_invariant (expr))
- set_value_range (vr, VR_RANGE, expr, expr, NULL);
+ extract_range_from_comparison (vr, gimple_assign_rhs_code (stmt),
+ gimple_expr_type (stmt),
+ gimple_assign_rhs1 (stmt),
+ gimple_assign_rhs2 (stmt));
+ else if (get_gimple_rhs_class (code) == GIMPLE_SINGLE_RHS
+ && is_gimple_min_invariant (gimple_assign_rhs1 (stmt)))
+ set_value_range_to_value (vr, gimple_assign_rhs1 (stmt), NULL);
else
set_value_range_to_varying (vr);
- /* If we got a varying range from the tests above, try a final
- time to derive a nonnegative or nonzero range. This time
- relying primarily on generic routines in fold in conjunction
- with range data. */
if (vr->type == VR_VARYING)
- {
- bool sop = false;
-
- if (INTEGRAL_TYPE_P (TREE_TYPE (expr))
- && vrp_expr_computes_nonnegative (expr, &sop))
- set_value_range_to_nonnegative (vr, TREE_TYPE (expr),
- sop || is_overflow_infinity (expr));
- else if (vrp_expr_computes_nonzero (expr, &sop)
- && !sop)
- set_value_range_to_nonnull (vr, TREE_TYPE (expr));
- }
+ extract_range_basic (vr, stmt);
}
/* Given a range VR, a LOOP and a variable VAR, determine whether it
for VAR. If so, update VR with the new limits. */
static void
-adjust_range_with_scev (value_range_t *vr, struct loop *loop, tree stmt,
- tree var)
+adjust_range_with_scev (value_range_t *vr, struct loop *loop,
+ gimple stmt, tree var)
{
tree init, step, chrec, tmin, tmax, min, max, type;
enum ev_direction dir;
return;
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, gimple 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:
return NULL_TREE;
}
+ if (!usable_range_p (vr0, strict_overflow_p)
+ || !usable_range_p (vr1, strict_overflow_p))
+ return NULL_TREE;
+
/* Simplify processing. If COMP is GT_EXPR or GE_EXPR, switch the
operands around and change the comparison code. */
if (comp == GT_EXPR || comp == GE_EXPR)
return NULL_TREE;
}
+ if (!usable_range_p (vr, strict_overflow_p))
+ return NULL_TREE;
+
if (comp == EQ_EXPR)
{
/* EQ_EXPR may only be computed if VR represents exactly
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);
create a new SSA name N and return the assertion assignment
'V = ASSERT_EXPR <V, V OP W>'. */
-static tree
+static gimple
build_assert_expr_for (tree cond, tree v)
{
- tree n, assertion;
+ tree n;
+ gimple assertion;
gcc_assert (TREE_CODE (v) == SSA_NAME);
- n = duplicate_ssa_name (v, NULL_TREE);
+ n = duplicate_ssa_name (v, NULL);
if (COMPARISON_CLASS_P (cond))
{
tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
- assertion = build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (v), n, a);
+ assertion = gimple_build_assign (n, a);
}
else if (TREE_CODE (cond) == TRUTH_NOT_EXPR)
{
/* Given !V, build the assignment N = false. */
tree op0 = TREE_OPERAND (cond, 0);
gcc_assert (op0 == v);
- assertion = build2 (GIMPLE_MODIFY_STMT, TREE_TYPE (v), n,
- boolean_false_node);
+ assertion = gimple_build_assign (n, boolean_false_node);
}
else if (TREE_CODE (cond) == SSA_NAME)
{
/* Given V, build the assignment N = true. */
gcc_assert (v == cond);
- assertion = build2 (GIMPLE_MODIFY_STMT,
- TREE_TYPE (v), n, boolean_true_node);
+ assertion = gimple_build_assign (n, boolean_true_node);
}
else
gcc_unreachable ();
point values. */
static inline bool
-fp_predicate (tree expr)
+fp_predicate (gimple stmt)
{
- return (COMPARISON_CLASS_P (expr)
- && FLOAT_TYPE_P (TREE_TYPE (TREE_OPERAND (expr, 0))));
+ GIMPLE_CHECK (stmt, GIMPLE_COND);
+
+ return FLOAT_TYPE_P (TREE_TYPE (gimple_cond_lhs (stmt)));
}
inferred. */
static bool
-infer_value_range (tree stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
+infer_value_range (gimple stmt, tree op, enum tree_code *comp_code_p, tree *val_p)
{
*val_p = NULL_TREE;
*comp_code_p = ERROR_MARK;
/* Similarly, don't infer anything from statements that may throw
exceptions. */
- if (tree_could_throw_p (stmt))
+ if (stmt_could_throw_p (stmt))
return false;
/* If STMT is the last statement of a basic block with no
successors, there is no point inferring anything about any of its
operands. We would not be able to find a proper insertion point
for the assertion, anyway. */
- if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0)
+ if (stmt_ends_bb_p (stmt) && EDGE_COUNT (gimple_bb (stmt)->succs) == 0)
return false;
/* We can only assume that a pointer dereference will yield
non-NULL if -fdelete-null-pointer-checks is enabled. */
- if (flag_delete_null_pointer_checks && POINTER_TYPE_P (TREE_TYPE (op)))
+ if (flag_delete_null_pointer_checks
+ && POINTER_TYPE_P (TREE_TYPE (op))
+ && gimple_code (stmt) != GIMPLE_ASM)
{
- bool is_store;
- unsigned num_uses, num_derefs;
+ unsigned num_uses, num_loads, num_stores;
- count_uses_and_derefs (op, stmt, &num_uses, &num_derefs, &is_store);
- if (num_derefs > 0)
+ count_uses_and_derefs (op, stmt, &num_uses, &num_loads, &num_stores);
+ if (num_loads + num_stores > 0)
{
*val_p = build_int_cst (TREE_TYPE (op), 0);
*comp_code_p = NE_EXPR;
while (loc)
{
fprintf (file, "\t");
- print_generic_expr (file, bsi_stmt (loc->si), 0);
+ print_gimple_stmt (file, gsi_stmt (loc->si), 0, 0);
fprintf (file, "\n\tBB #%d", loc->bb->index);
if (loc->e)
{
/* 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,
edge e,
- block_stmt_iterator si)
+ gimple_stmt_iterator si)
{
assert_locus_t n, loc, last_loc;
bool found;
gcc_assert (bb == NULL || e == NULL);
if (e == NULL)
- gcc_assert (TREE_CODE (bsi_stmt (si)) != COND_EXPR
- && TREE_CODE (bsi_stmt (si)) != SWITCH_EXPR);
+ gcc_assert (gimple_code (gsi_stmt (si)) != GIMPLE_COND
+ && gimple_code (gsi_stmt (si)) != GIMPLE_SWITCH);
#endif
+ /* Never build an assert comparing against an integer constant with
+ TREE_OVERFLOW set. This confuses our undefined overflow warning
+ machinery. */
+ if (TREE_CODE (val) == INTEGER_CST
+ && TREE_OVERFLOW (val))
+ val = build_int_cst_wide (TREE_TYPE (val),
+ TREE_INT_CST_LOW (val), TREE_INT_CST_HIGH (val));
+
/* The new assertion A will be inserted at BB or E. We need to
determine if the new location is dominated by a previously
registered location for A. If we are doing an edge insertion,
{
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, gimple_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 (live_on_edge (e, 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)))
+ {
+ gimple def_stmt = SSA_NAME_DEF_STMT (name);
+ tree cst2 = NULL_TREE, name2 = NULL_TREE, name3 = NULL_TREE;
+
+ /* Extract CST2 from the (optional) addition. */
+ if (is_gimple_assign (def_stmt)
+ && gimple_assign_rhs_code (def_stmt) == PLUS_EXPR)
+ {
+ name2 = gimple_assign_rhs1 (def_stmt);
+ cst2 = gimple_assign_rhs2 (def_stmt);
+ 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 (gimple_assign_cast_p (def_stmt))
{
- /* 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);
+ if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
+ && ! TYPE_UNSIGNED (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))
+ && (TYPE_PRECISION (gimple_expr_type (def_stmt))
+ == TYPE_PRECISION (TREE_TYPE (gimple_assign_rhs1 (def_stmt)))))
+ name3 = gimple_assign_rhs1 (def_stmt);
}
- /* 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))
+ && live_on_edge (e, 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);
+
+ 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");
+ }
- /* 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)))
+ 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))
+ && live_on_edge (e, name2)
+ && !has_single_use (name2))
{
- tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
- tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
+ tree tmp;
- if (comp_code == GT_EXPR
- && (!max
- || compare_values (val, max) == 0))
- return false;
+ /* 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 (comp_code == LT_EXPR
- && (!min
- || compare_values (val, min) == 0))
- return false;
+ 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
static bool
register_edge_assert_for_1 (tree op, enum tree_code code,
- edge e, block_stmt_iterator bsi)
+ edge e, gimple_stmt_iterator bsi)
{
bool retval = false;
- tree op_def, rhs, val;
+ gimple op_def;
+ tree 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;
}
a truth operation or some bit operations, then we may be able
to register information about the operands of that assignment. */
op_def = SSA_NAME_DEF_STMT (op);
- if (TREE_CODE (op_def) != GIMPLE_MODIFY_STMT)
+ if (gimple_code (op_def) != GIMPLE_ASSIGN)
return retval;
- rhs = GIMPLE_STMT_OPERAND (op_def, 1);
+ rhs_code = gimple_assign_rhs_code (op_def);
- if (COMPARISON_CLASS_P (rhs))
+ if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
{
bool invert = (code == EQ_EXPR ? true : false);
- 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;
- }
+ tree op0 = gimple_assign_rhs1 (op_def);
+ tree op1 = gimple_assign_rhs2 (op_def);
- /* 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
- || TREE_CODE (rhs) == BIT_AND_EXPR))
+ && (gimple_assign_rhs_code (op_def) == TRUTH_AND_EXPR
+ || gimple_assign_rhs_code (op_def) == BIT_AND_EXPR))
|| (code == EQ_EXPR
- && (TREE_CODE (rhs) == TRUTH_OR_EXPR
- || TREE_CODE (rhs) == BIT_IOR_EXPR)))
+ && (gimple_assign_rhs_code (op_def) == TRUTH_OR_EXPR
+ || gimple_assign_rhs_code (op_def) == BIT_IOR_EXPR)))
{
/* Recurse on each operand. */
- retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
+ retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
code, e, bsi);
- retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 1),
+ retval |= register_edge_assert_for_1 (gimple_assign_rhs2 (op_def),
code, e, bsi);
}
- else if (TREE_CODE (rhs) == TRUTH_NOT_EXPR)
+ else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR)
{
/* Recurse, flipping CODE. */
code = invert_tree_comparison (code, false);
- retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
+ retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
code, e, bsi);
}
- else if (TREE_CODE (rhs) == SSA_NAME)
+ else if (gimple_assign_rhs_code (op_def) == SSA_NAME)
{
/* Recurse through the copy. */
- retval |= register_edge_assert_for_1 (rhs, code, e, bsi);
+ retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
+ code, e, bsi);
}
- else if (TREE_CODE (rhs) == NOP_EXPR
- || TREE_CODE (rhs) == CONVERT_EXPR
- || TREE_CODE (rhs) == VIEW_CONVERT_EXPR
- || TREE_CODE (rhs) == NON_LVALUE_EXPR)
+ else if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (op_def)))
{
/* Recurse through the type conversion. */
- retval |= register_edge_assert_for_1 (TREE_OPERAND (rhs, 0),
+ retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
code, e, bsi);
}
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, gimple_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 (((comp_code == EQ_EXPR && integer_onep (val))
|| (comp_code == NE_EXPR && integer_zerop (val))))
{
- tree def_stmt = SSA_NAME_DEF_STMT (name);
+ gimple def_stmt = SSA_NAME_DEF_STMT (name);
- if (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
- && (TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == TRUTH_AND_EXPR
- || TREE_CODE (GIMPLE_STMT_OPERAND (def_stmt, 1)) == BIT_AND_EXPR))
+ if (is_gimple_assign (def_stmt)
+ && (gimple_assign_rhs_code (def_stmt) == TRUTH_AND_EXPR
+ || gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR))
{
- tree op0 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
- tree op1 = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 1);
+ tree op0 = gimple_assign_rhs1 (def_stmt);
+ tree op1 = gimple_assign_rhs2 (def_stmt);
retval |= register_edge_assert_for_1 (op0, NE_EXPR, e, si);
retval |= register_edge_assert_for_1 (op1, NE_EXPR, e, si);
}
if (((comp_code == EQ_EXPR && integer_zerop (val))
|| (comp_code == NE_EXPR && integer_onep (val))))
{
- tree def_stmt = SSA_NAME_DEF_STMT (name);
+ gimple def_stmt = SSA_NAME_DEF_STMT (name);
- 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))
+ if (is_gimple_assign (def_stmt)
+ && (gimple_assign_rhs_code (def_stmt) == TRUTH_OR_EXPR
+ /* For BIT_IOR_EXPR only if NAME == 0 both operands have
+ necessarily zero value. */
+ || (comp_code == EQ_EXPR
+ && (gimple_assign_rhs_code (def_stmt) == 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);
+ tree op0 = gimple_assign_rhs1 (def_stmt);
+ tree op1 = gimple_assign_rhs2 (def_stmt);
retval |= register_edge_assert_for_1 (op0, EQ_EXPR, e, si);
retval |= register_edge_assert_for_1 (op1, EQ_EXPR, e, si);
}
}
-static bool find_assert_locations (basic_block bb);
-
/* Determine whether the outgoing edges of BB should receive an
ASSERT_EXPR for each of the operands of BB's LAST statement.
- The last statement of BB must be a COND_EXPR or a SWITCH_EXPR.
+ The last statement of BB must be a COND_EXPR.
If any of the sub-graphs rooted at BB have an interesting use of
the predicate operands, an assert location node is added to the
list of assertions for the corresponding operands. */
static bool
-find_conditional_asserts (basic_block bb, tree last)
+find_conditional_asserts (basic_block bb, gimple last)
{
bool need_assert;
- block_stmt_iterator bsi;
+ gimple_stmt_iterator bsi;
tree op;
edge_iterator ei;
edge e;
ssa_op_iter iter;
need_assert = false;
- bsi = bsi_for_stmt (last);
+ bsi = gsi_for_stmt (last);
/* Look for uses of the operands in each of the sub-graphs
rooted at BB. We need to check each of the outgoing edges
if (e->dest == bb)
continue;
- /* Remove the COND_EXPR operands from the FOUND_IN_SUBGRAPH bitmap.
- Otherwise, when we finish traversing each of the sub-graphs, we
- won't know whether the variables were found in the sub-graphs or
- if they had been found in a block upstream from BB.
-
- This is actually a bad idea is some cases, particularly jump
- threading. Consider a CFG like the following:
-
- 0
- /|
- 1 |
- \|
- 2
- / \
- 3 4
-
- Assume that one or more operands in the conditional at the
- end of block 0 are used in a conditional in block 2, but not
- anywhere in block 1. In this case we will not insert any
- assert statements in block 1, which may cause us to miss
- opportunities to optimize, particularly for jump threading. */
- FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
- RESET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
-
- /* 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);
-
/* 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));
+ {
+ need_assert |= register_edge_assert_for (op, e, bsi,
+ gimple_cond_code (last),
+ gimple_cond_lhs (last),
+ gimple_cond_rhs (last));
+ }
+ }
+
+ return need_assert;
+}
+
+/* Compare two case labels sorting first by the destination label uid
+ and then by the case value. */
+
+static int
+compare_case_labels (const void *p1, const void *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));
+
+ if (uid1 < uid2)
+ return -1;
+ else if (uid1 == uid2)
+ {
+ /* Make sure the default label is first in a group. */
+ if (!CASE_LOW (case1))
+ return -1;
+ else if (!CASE_LOW (case2))
+ return 1;
+ else
+ return tree_int_cst_compare (CASE_LOW (case1), CASE_LOW (case2));
}
+ else
+ return 1;
+}
+
+/* Determine whether the outgoing edges of BB should receive an
+ ASSERT_EXPR for each of the operands of BB's LAST statement.
+ The last statement of BB must be a SWITCH_EXPR.
+
+ If any of the sub-graphs rooted at BB have an interesting use of
+ the predicate operands, an assert location node is added to the
+ list of assertions for the corresponding operands. */
+
+static bool
+find_switch_asserts (basic_block bb, gimple last)
+{
+ bool need_assert;
+ gimple_stmt_iterator bsi;
+ tree op;
+ edge e;
+ tree vec2;
+ size_t n = gimple_switch_num_labels(last);
+#if GCC_VERSION >= 4000
+ unsigned int idx;
+#else
+ /* Work around GCC 3.4 bug (PR 37086). */
+ volatile unsigned int idx;
+#endif
+
+ need_assert = false;
+ bsi = gsi_for_stmt (last);
+ op = gimple_switch_index (last);
+ if (TREE_CODE (op) != SSA_NAME)
+ return false;
+
+ /* Build a vector of case labels sorted by destination label. */
+ vec2 = make_tree_vec (n);
+ for (idx = 0; idx < n; ++idx)
+ TREE_VEC_ELT (vec2, idx) = gimple_switch_label (last, idx);
+ qsort (&TREE_VEC_ELT (vec2, 0), n, sizeof (tree), compare_case_labels);
+
+ for (idx = 0; idx < n; ++idx)
+ {
+ tree min, max;
+ tree cl = TREE_VEC_ELT (vec2, idx);
+
+ min = CASE_LOW (cl);
+ max = CASE_HIGH (cl);
+
+ /* If there are multiple case labels with the same destination
+ we need to combine them to a single value range for the edge. */
+ if (idx + 1 < n
+ && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx + 1)))
+ {
+ /* Skip labels until the last of the group. */
+ do {
+ ++idx;
+ } while (idx < n
+ && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx)));
+ --idx;
+
+ /* Pick up the maximum of the case label range. */
+ if (CASE_HIGH (TREE_VEC_ELT (vec2, idx)))
+ max = CASE_HIGH (TREE_VEC_ELT (vec2, idx));
+ else
+ max = CASE_LOW (TREE_VEC_ELT (vec2, idx));
+ }
+
+ /* Nothing to do if the range includes the default label until we
+ can register anti-ranges. */
+ if (min == NULL_TREE)
+ continue;
- /* Finally, indicate that we have found the operands in the
- conditional. */
- FOR_EACH_SSA_TREE_OPERAND (op, last, iter, SSA_OP_USE)
- SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
+ /* Find the edge to register the assert expr on. */
+ e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
+
+ /* Register the necessary assertions for the operand in the
+ SWITCH_EXPR. */
+ need_assert |= register_edge_assert_for (op, e, bsi,
+ max ? GE_EXPR : EQ_EXPR,
+ op,
+ fold_convert (TREE_TYPE (op),
+ min));
+ if (max)
+ {
+ need_assert |= register_edge_assert_for (op, e, bsi, LE_EXPR,
+ op,
+ fold_convert (TREE_TYPE (op),
+ max));
+ }
+ }
return need_assert;
}
If this function returns true, then it means that there are names
for which we need to generate ASSERT_EXPRs. Those assertions are
- inserted by process_assert_insertions.
-
- TODO. Handle SWITCH_EXPR. */
+ inserted by process_assert_insertions. */
static bool
-find_assert_locations (basic_block bb)
+find_assert_locations_1 (basic_block bb, sbitmap live)
{
- block_stmt_iterator si;
- tree last, phi;
+ gimple_stmt_iterator si;
+ gimple last;
+ gimple phi;
bool need_assert;
- basic_block son;
-
- if (TEST_BIT (blocks_visited, bb->index))
- return false;
-
- SET_BIT (blocks_visited, bb->index);
need_assert = false;
+ last = last_stmt (bb);
- /* Traverse all PHI nodes in BB marking used operands. */
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
- {
- use_operand_p arg_p;
- ssa_op_iter i;
+ /* If BB's last statement is a conditional statement involving integer
+ operands, determine if we need to add ASSERT_EXPRs. */
+ if (last
+ && gimple_code (last) == GIMPLE_COND
+ && !fp_predicate (last)
+ && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
+ need_assert |= find_conditional_asserts (bb, last);
- FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
- {
- tree arg = USE_FROM_PTR (arg_p);
- if (TREE_CODE (arg) == SSA_NAME)
- {
- gcc_assert (is_gimple_reg (PHI_RESULT (phi)));
- SET_BIT (found_in_subgraph, SSA_NAME_VERSION (arg));
- }
- }
- }
+ /* If BB's last statement is a switch statement involving integer
+ operands, determine if we need to add ASSERT_EXPRs. */
+ if (last
+ && gimple_code (last) == GIMPLE_SWITCH
+ && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
+ need_assert |= find_switch_asserts (bb, last);
/* Traverse all the statements in BB marking used names and looking
for statements that may infer assertions for their used operands. */
- last = NULL_TREE;
- for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+ for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
{
- tree stmt, op;
+ gimple stmt;
+ tree op;
ssa_op_iter i;
- stmt = bsi_stmt (si);
+ stmt = gsi_stmt (si);
/* See if we can derive an assertion for any of STMT's operands. */
FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_USE)
tree value;
enum tree_code comp_code;
- /* Mark OP in bitmap FOUND_IN_SUBGRAPH. If STMT is inside
- the sub-graph of a conditional block, when we return from
- this recursive walk, our parent will use the
- FOUND_IN_SUBGRAPH bitset to determine if one of the
- operands it was looking for was present in the sub-graph. */
- SET_BIT (found_in_subgraph, SSA_NAME_VERSION (op));
+ /* Mark OP in our live bitmap. */
+ SET_BIT (live, SSA_NAME_VERSION (op));
/* If OP is used in such a way that we can infer a value
range for it, and we don't find a previous assertion for
if (comp_code == NE_EXPR && integer_zerop (value))
{
tree t = op;
- tree def_stmt = SSA_NAME_DEF_STMT (t);
+ gimple def_stmt = SSA_NAME_DEF_STMT (t);
- while (TREE_CODE (def_stmt) == GIMPLE_MODIFY_STMT
- && TREE_CODE
- (GIMPLE_STMT_OPERAND (def_stmt, 1)) == NOP_EXPR
+ while (is_gimple_assign (def_stmt)
+ && gimple_assign_rhs_code (def_stmt) == NOP_EXPR
&& TREE_CODE
- (TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1),
- 0)) == SSA_NAME
+ (gimple_assign_rhs1 (def_stmt)) == SSA_NAME
&& POINTER_TYPE_P
- (TREE_TYPE (TREE_OPERAND
- (GIMPLE_STMT_OPERAND (def_stmt,
- 1), 0))))
+ (TREE_TYPE (gimple_assign_rhs1 (def_stmt))))
{
- t = TREE_OPERAND (GIMPLE_STMT_OPERAND (def_stmt, 1), 0);
+ t = gimple_assign_rhs1 (def_stmt);
def_stmt = SSA_NAME_DEF_STMT (t);
/* Note we want to register the assert for the
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;
}
}
}
-
- /* Remember the last statement of the block. */
- last = stmt;
}
- /* If BB's last statement is a conditional expression
- involving integer operands, recurse into each of the sub-graphs
- rooted at BB to determine if we need to add ASSERT_EXPRs. */
- if (last
- && TREE_CODE (last) == COND_EXPR
- && !fp_predicate (COND_EXPR_COND (last))
- && !ZERO_SSA_OPERANDS (last, SSA_OP_USE))
- need_assert |= find_conditional_asserts (bb, last);
+ /* Traverse all PHI nodes in BB marking used operands. */
+ for (si = gsi_start_phis (bb); !gsi_end_p(si); gsi_next (&si))
+ {
+ use_operand_p arg_p;
+ ssa_op_iter i;
+ phi = gsi_stmt (si);
- /* Recurse into the dominator children of BB. */
- for (son = first_dom_son (CDI_DOMINATORS, bb);
- son;
- son = next_dom_son (CDI_DOMINATORS, son))
- need_assert |= find_assert_locations (son);
+ FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_USE)
+ {
+ tree arg = USE_FROM_PTR (arg_p);
+ if (TREE_CODE (arg) == SSA_NAME)
+ SET_BIT (live, SSA_NAME_VERSION (arg));
+ }
+ }
return need_assert;
}
-
-/* Create an ASSERT_EXPR for NAME and insert it in the location
- indicated by LOC. Return true if we made any edge insertions. */
+/* Do an RPO walk over the function computing SSA name liveness
+ on-the-fly and deciding on assert expressions to insert.
+ Returns true if there are assert expressions to be inserted. */
static bool
-process_assert_insertions_for (tree name, assert_locus_t loc)
+find_assert_locations (void)
{
- /* Build the comparison expression NAME_i COMP_CODE VAL. */
- tree stmt, cond, assert_expr;
- edge_iterator ei;
- edge e;
+ int *rpo = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
+ int *bb_rpo = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
+ int *last_rpo = XCNEWVEC (int, last_basic_block + NUM_FIXED_BLOCKS);
+ int rpo_cnt, i;
+ bool need_asserts;
+
+ live = XCNEWVEC (sbitmap, last_basic_block + NUM_FIXED_BLOCKS);
+ rpo_cnt = pre_and_rev_post_order_compute (NULL, rpo, false);
+ for (i = 0; i < rpo_cnt; ++i)
+ bb_rpo[rpo[i]] = i;
+
+ need_asserts = false;
+ for (i = rpo_cnt-1; i >= 0; --i)
+ {
+ basic_block bb = BASIC_BLOCK (rpo[i]);
+ edge e;
+ edge_iterator ei;
+
+ if (!live[rpo[i]])
+ {
+ live[rpo[i]] = sbitmap_alloc (num_ssa_names);
+ sbitmap_zero (live[rpo[i]]);
+ }
+
+ /* Process BB and update the live information with uses in
+ this block. */
+ need_asserts |= find_assert_locations_1 (bb, live[rpo[i]]);
+
+ /* Merge liveness into the predecessor blocks and free it. */
+ if (!sbitmap_empty_p (live[rpo[i]]))
+ {
+ int pred_rpo = i;
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ {
+ int pred = e->src->index;
+ if (e->flags & EDGE_DFS_BACK)
+ continue;
+
+ if (!live[pred])
+ {
+ live[pred] = sbitmap_alloc (num_ssa_names);
+ sbitmap_zero (live[pred]);
+ }
+ sbitmap_a_or_b (live[pred], live[pred], live[rpo[i]]);
+
+ if (bb_rpo[pred] < pred_rpo)
+ pred_rpo = bb_rpo[pred];
+ }
+
+ /* Record the RPO number of the last visited block that needs
+ live information from this block. */
+ last_rpo[rpo[i]] = pred_rpo;
+ }
+ else
+ {
+ sbitmap_free (live[rpo[i]]);
+ live[rpo[i]] = NULL;
+ }
+
+ /* We can free all successors live bitmaps if all their
+ predecessors have been visited already. */
+ FOR_EACH_EDGE (e, ei, bb->succs)
+ if (last_rpo[e->dest->index] == i
+ && live[e->dest->index])
+ {
+ sbitmap_free (live[e->dest->index]);
+ live[e->dest->index] = NULL;
+ }
+ }
+
+ XDELETEVEC (rpo);
+ XDELETEVEC (bb_rpo);
+ XDELETEVEC (last_rpo);
+ for (i = 0; i < last_basic_block + NUM_FIXED_BLOCKS; ++i)
+ if (live[i])
+ sbitmap_free (live[i]);
+ XDELETEVEC (live);
+
+ return need_asserts;
+}
+
+/* Create an ASSERT_EXPR for NAME and insert it in the location
+ indicated by LOC. Return true if we made any edge insertions. */
- cond = build2 (loc->comp_code, boolean_type_node, name, loc->val);
- assert_expr = build_assert_expr_for (cond, name);
+static bool
+process_assert_insertions_for (tree name, assert_locus_t loc)
+{
+ /* Build the comparison expression NAME_i COMP_CODE VAL. */
+ gimple stmt;
+ tree cond;
+ gimple assert_stmt;
+ edge_iterator ei;
+ edge e;
+ cond = build2 (loc->comp_code, boolean_type_node, loc->expr, loc->val);
+ assert_stmt = build_assert_expr_for (cond, name);
if (loc->e)
{
/* We have been asked to insert the assertion on an edge. This
is used only by COND_EXPR and SWITCH_EXPR assertions. */
#if defined ENABLE_CHECKING
- gcc_assert (TREE_CODE (bsi_stmt (loc->si)) == COND_EXPR
- || TREE_CODE (bsi_stmt (loc->si)) == SWITCH_EXPR);
+ gcc_assert (gimple_code (gsi_stmt (loc->si)) == GIMPLE_COND
+ || gimple_code (gsi_stmt (loc->si)) == GIMPLE_SWITCH);
#endif
- bsi_insert_on_edge (loc->e, assert_expr);
+ gsi_insert_on_edge (loc->e, assert_stmt);
return true;
}
/* Otherwise, we can insert right after LOC->SI iff the
statement must not be the last statement in the block. */
- stmt = bsi_stmt (loc->si);
+ stmt = gsi_stmt (loc->si);
if (!stmt_ends_bb_p (stmt))
{
- bsi_insert_after (&loc->si, assert_expr, BSI_SAME_STMT);
+ gsi_insert_after (&loc->si, assert_stmt, GSI_SAME_STMT);
return false;
}
FOR_EACH_EDGE (e, ei, loc->bb->succs)
if (!(e->flags & EDGE_ABNORMAL))
{
- bsi_insert_on_edge (e, assert_expr);
+ gsi_insert_on_edge (e, assert_stmt);
return true;
}
}
if (update_edges_p)
- bsi_commit_edge_inserts ();
+ gsi_commit_edge_inserts ();
- if (dump_file && (dump_flags & TDF_STATS))
- fprintf (dump_file, "\nNumber of ASSERT_EXPR expressions inserted: %d\n\n",
- num_asserts);
+ statistics_counter_event (cfun, "Number of ASSERT_EXPR expressions inserted",
+ num_asserts);
}
static void
insert_range_assertions (void)
{
- edge e;
- edge_iterator ei;
- bool update_ssa_p;
-
- found_in_subgraph = sbitmap_alloc (num_ssa_names);
- sbitmap_zero (found_in_subgraph);
-
- blocks_visited = sbitmap_alloc (last_basic_block);
- sbitmap_zero (blocks_visited);
-
need_assert_for = BITMAP_ALLOC (NULL);
asserts_for = XCNEWVEC (assert_locus_t, num_ssa_names);
calculate_dominance_info (CDI_DOMINATORS);
- update_ssa_p = false;
- FOR_EACH_EDGE (e, ei, ENTRY_BLOCK_PTR->succs)
- if (find_assert_locations (e->dest))
- update_ssa_p = true;
-
- if (update_ssa_p)
+ if (find_assert_locations ())
{
process_assert_insertions ();
update_ssa (TODO_update_ssa_no_phi);
dump_function_to_file (current_function_decl, dump_file, dump_flags);
}
- sbitmap_free (found_in_subgraph);
free (asserts_for);
BITMAP_FREE (need_assert_for);
}
IGNORE_OFF_BY_ONE is true if the ARRAY_REF is inside a ADDR_EXPR. */
static void
-check_array_ref (tree ref, location_t* locus, bool ignore_off_by_one)
+check_array_ref (tree ref, const location_t *location, bool ignore_off_by_one)
{
value_range_t* vr = NULL;
tree low_sub, up_sub;
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_int_cst_lt (low_sub, low_bound))
{
warning (OPT_Warray_bounds,
- "%Harray subscript is outside array bounds", locus);
+ "%Harray subscript is outside array bounds", location);
TREE_NO_WARNING (ref) = 1;
}
}
up_sub)))
{
warning (OPT_Warray_bounds, "%Harray subscript is above array bounds",
- locus);
+ location);
TREE_NO_WARNING (ref) = 1;
}
else if (TREE_CODE (low_sub) == INTEGER_CST
&& tree_int_cst_lt (low_sub, low_bound))
{
warning (OPT_Warray_bounds, "%Harray subscript is below array bounds",
- locus);
+ location);
TREE_NO_WARNING (ref) = 1;
}
}
+/* 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, const location_t *location)
+{
+ while (TREE_CODE (t) == SSA_NAME)
+ {
+ gimple g = SSA_NAME_DEF_STMT (t);
+
+ if (gimple_code (g) != GIMPLE_ASSIGN)
+ return;
+
+ if (get_gimple_rhs_class (gimple_assign_rhs_code (g)) !=
+ GIMPLE_SINGLE_RHS)
+ return;
+
+ t = gimple_assign_rhs1 (g);
+ }
+
+
+ /* 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
check_array_bounds (tree *tp, int *walk_subtree, void *data)
{
tree t = *tp;
- tree stmt = (tree)data;
- location_t *location = EXPR_LOCUS (stmt);
+ struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
+ const location_t *location = (const location_t *) wi->info;
*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
+ if (TREE_CODE (t) == INDIRECT_REF
+ || (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)))
+ search_for_addr_array (TREE_OPERAND (t, 0), location);
- 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;
-
- 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;
- }
+ if (TREE_CODE (t) == ADDR_EXPR)
+ *walk_subtree = FALSE;
return NULL_TREE;
}
check_all_array_refs (void)
{
basic_block bb;
- block_stmt_iterator si;
+ gimple_stmt_iterator si;
FOR_EACH_BB (bb)
{
if (single_pred_p (bb))
{
basic_block pred_bb = EDGE_PRED (bb, 0)->src;
- tree ls = NULL_TREE;
+ gimple ls = NULL;
- if (!bsi_end_p (bsi_last (pred_bb)))
- ls = bsi_stmt (bsi_last (pred_bb));
+ if (!gsi_end_p (gsi_last_bb (pred_bb)))
+ ls = gsi_stmt (gsi_last_bb (pred_bb));
- if (ls && TREE_CODE (ls) == COND_EXPR
- && ((COND_EXPR_COND (ls) == boolean_false_node
+ if (ls && gimple_code (ls) == GIMPLE_COND
+ && ((gimple_cond_false_p (ls)
&& (EDGE_PRED (bb, 0)->flags & EDGE_TRUE_VALUE))
- || (COND_EXPR_COND (ls) == boolean_true_node
+ || (gimple_cond_true_p (ls)
&& (EDGE_PRED (bb, 0)->flags & EDGE_FALSE_VALUE))))
continue;
}
- for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
- walk_tree (bsi_stmt_ptr (si), check_array_bounds,
- bsi_stmt (si), NULL);
+ for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
+ {
+ gimple stmt = gsi_stmt (si);
+ const location_t *location = gimple_location_ptr (stmt);
+ struct walk_stmt_info wi;
+ if (!gimple_has_location (stmt))
+ continue;
+
+ if (is_gimple_call (stmt))
+ {
+ size_t i;
+ size_t n = gimple_call_num_args (stmt);
+ for (i = 0; i < n; i++)
+ {
+ tree arg = gimple_call_arg (stmt, i);
+ search_for_addr_array (arg, location);
+ }
+ }
+ else
+ {
+ memset (&wi, 0, sizeof (wi));
+ wi.info = CONST_CAST (void *, (const void *) location);
+
+ walk_gimple_op (gsi_stmt (si),
+ check_array_bounds,
+ &wi);
+ }
+ }
}
}
remove_range_assertions (void)
{
basic_block bb;
- block_stmt_iterator si;
+ gimple_stmt_iterator si;
/* Note that the BSI iterator bump happens at the bottom of the
loop and no bump is necessary if we're removing the statement
referenced by the current BSI. */
FOR_EACH_BB (bb)
- for (si = bsi_start (bb); !bsi_end_p (si);)
+ for (si = gsi_start_bb (bb); !gsi_end_p (si);)
{
- tree stmt = bsi_stmt (si);
- tree use_stmt;
+ gimple stmt = gsi_stmt (si);
+ gimple use_stmt;
- if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT
- && TREE_CODE (GIMPLE_STMT_OPERAND (stmt, 1)) == ASSERT_EXPR)
+ if (is_gimple_assign (stmt)
+ && gimple_assign_rhs_code (stmt) == ASSERT_EXPR)
{
- tree rhs = GIMPLE_STMT_OPERAND (stmt, 1), var;
+ tree rhs = gimple_assign_rhs1 (stmt);
+ tree var;
tree cond = fold (ASSERT_EXPR_COND (rhs));
use_operand_p use_p;
imm_use_iterator iter;
/* Propagate the RHS into every use of the LHS. */
var = ASSERT_EXPR_VAR (rhs);
FOR_EACH_IMM_USE_STMT (use_stmt, iter,
- GIMPLE_STMT_OPERAND (stmt, 0))
+ gimple_assign_lhs (stmt))
FOR_EACH_IMM_USE_ON_STMT (use_p, iter)
{
SET_USE (use_p, var);
}
/* And finally, remove the copy, it is not needed. */
- bsi_remove (&si, true);
+ gsi_remove (&si, true);
release_defs (stmt);
}
else
- bsi_next (&si);
+ gsi_next (&si);
}
-
- sbitmap_free (blocks_visited);
}
/* Return true if STMT is interesting for VRP. */
static bool
-stmt_interesting_for_vrp (tree stmt)
+stmt_interesting_for_vrp (gimple stmt)
{
- if (TREE_CODE (stmt) == PHI_NODE
- && is_gimple_reg (PHI_RESULT (stmt))
- && (INTEGRAL_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))
- || POINTER_TYPE_P (TREE_TYPE (PHI_RESULT (stmt)))))
+ if (gimple_code (stmt) == GIMPLE_PHI
+ && is_gimple_reg (gimple_phi_result (stmt))
+ && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_phi_result (stmt)))
+ || POINTER_TYPE_P (TREE_TYPE (gimple_phi_result (stmt)))))
return true;
- else if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+ else if (is_gimple_assign (stmt) || is_gimple_call (stmt))
{
- tree lhs = GIMPLE_STMT_OPERAND (stmt, 0);
- tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
+ tree lhs = gimple_get_lhs (stmt);
/* In general, assignments with virtual operands are not useful
for deriving ranges, with the obvious exception of calls to
builtin functions. */
- if (TREE_CODE (lhs) == SSA_NAME
+ if (lhs && TREE_CODE (lhs) == SSA_NAME
&& (INTEGRAL_TYPE_P (TREE_TYPE (lhs))
|| POINTER_TYPE_P (TREE_TYPE (lhs)))
- && ((TREE_CODE (rhs) == CALL_EXPR
- && TREE_CODE (CALL_EXPR_FN (rhs)) == ADDR_EXPR
- && DECL_P (TREE_OPERAND (CALL_EXPR_FN (rhs), 0))
- && DECL_IS_BUILTIN (TREE_OPERAND (CALL_EXPR_FN (rhs), 0)))
+ && ((is_gimple_call (stmt)
+ && gimple_call_fndecl (stmt) != NULL_TREE
+ && DECL_IS_BUILTIN (gimple_call_fndecl (stmt)))
|| ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)))
return true;
}
- else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
+ else if (gimple_code (stmt) == GIMPLE_COND
+ || gimple_code (stmt) == GIMPLE_SWITCH)
return true;
return false;
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)
{
- block_stmt_iterator si;
- tree phi;
+ gimple_stmt_iterator si;
- for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
+ for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
{
+ gimple phi = gsi_stmt (si);
if (!stmt_interesting_for_vrp (phi))
{
tree lhs = PHI_RESULT (phi);
set_value_range_to_varying (get_value_range (lhs));
- DONT_SIMULATE_AGAIN (phi) = true;
+ prop_set_simulate_again (phi, false);
}
else
- DONT_SIMULATE_AGAIN (phi) = false;
+ prop_set_simulate_again (phi, true);
}
- for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+ for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
{
- tree stmt = bsi_stmt (si);
+ gimple stmt = gsi_stmt (si);
if (!stmt_interesting_for_vrp (stmt))
{
tree def;
FOR_EACH_SSA_TREE_OPERAND (def, stmt, i, SSA_OP_DEF)
set_value_range_to_varying (get_value_range (def));
- DONT_SIMULATE_AGAIN (stmt) = true;
+ prop_set_simulate_again (stmt, false);
}
else
{
- DONT_SIMULATE_AGAIN (stmt) = false;
+ prop_set_simulate_again (stmt, true);
}
}
}
the SSA name in *OUTPUT_P. */
static enum ssa_prop_result
-vrp_visit_assignment (tree stmt, tree *output_p)
+vrp_visit_assignment_or_call (gimple stmt, tree *output_p)
{
- tree lhs, rhs, def;
+ tree def, lhs;
ssa_op_iter iter;
-
- lhs = GIMPLE_STMT_OPERAND (stmt, 0);
- rhs = GIMPLE_STMT_OPERAND (stmt, 1);
+ enum gimple_code code = gimple_code (stmt);
+ lhs = gimple_get_lhs (stmt);
/* We only keep track of ranges in integral and pointer types. */
if (TREE_CODE (lhs) == SSA_NAME
struct loop *l;
value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
- extract_range_from_expr (&new_vr, rhs);
+ if (code == GIMPLE_CALL)
+ extract_range_basic (&new_vr, stmt);
+ else
+ extract_range_from_assignment (&new_vr, stmt);
/* If STMT is inside a loop, we may be able to know something
else about the range of LHS by examining scalar evolution
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)
- {
- if (used_strict_overflow > 0)
- *strict_overflow_p = true;
- return retval;
- }
+ if (retval
+ && used_strict_overflow > 0)
+ *strict_overflow_p = true;
- /* 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;
+ bool sop = false;
- value_range_t vr2 = *(vr_value[i2]);
-
- 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. */
-/* Given a conditional predicate COND, try to determine if COND yields
- true or false based on the value ranges of its operands. Return
- BOOLEAN_TRUE_NODE if the conditional always evaluates to true,
- BOOLEAN_FALSE_NODE if the conditional always evaluates to false, and,
- NULL if the conditional cannot be evaluated at compile time.
+static tree
+vrp_evaluate_conditional_warnv_with_ops_using_ranges (enum tree_code code,
+ tree op0, tree op1,
+ bool * strict_overflow_p)
+{
+ 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;
+}
- If USE_EQUIV_P is true, the ranges of all the names equivalent with
- the operands in COND are used when trying to compute its value.
- This is only used during final substitution. During propagation,
- we only check the range of each variable and not its equivalents.
+/* 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, bool *only_ranges)
+{
+ tree ret;
+ if (only_ranges)
+ *only_ranges = true;
+
+ /* 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 (only_ranges
+ && (ret = vrp_evaluate_conditional_warnv_with_ops_using_ranges
+ (code, op0, op1, strict_overflow_p)))
+ return ret;
+ *only_ranges = false;
+ 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
+ return vrp_evaluate_conditional_warnv_with_ops_using_ranges (code, op0, op1,
+ strict_overflow_p);
+ return NULL_TREE;
+}
- Set *STRICT_OVERFLOW_P to indicate whether we relied on an overflow
- infinity to produce the result. */
+/* Given (CODE OP0 OP1) within STMT, try to simplify it based on value range
+ information. Return NULL if the conditional can not be evaluated.
+ The ranges of all the names equivalent with the operands in COND
+ will be used when trying to compute the value. If the result is
+ based on undefined signed overflow, issue a warning if
+ appropriate. */
tree
-vrp_evaluate_conditional (tree cond, bool use_equiv_p, bool *strict_overflow_p)
+vrp_evaluate_conditional (enum tree_code code, tree op0, tree op1, gimple stmt)
{
- gcc_assert (TREE_CODE (cond) == SSA_NAME
- || TREE_CODE_CLASS (TREE_CODE (cond)) == tcc_comparison);
+ bool sop;
+ tree ret;
+ bool only_ranges;
+
+ sop = false;
+ ret = vrp_evaluate_conditional_warnv_with_ops (code, op0, op1, true, &sop,
+ &only_ranges);
- if (TREE_CODE (cond) == SSA_NAME)
+ if (ret && sop)
{
- value_range_t *vr;
- tree retval;
+ enum warn_strict_overflow_code wc;
+ const char* warnmsg;
- if (use_equiv_p)
- retval = compare_name_with_value (NE_EXPR, cond, boolean_false_node,
- strict_overflow_p);
+ if (is_gimple_min_invariant (ret))
+ {
+ wc = WARN_STRICT_OVERFLOW_CONDITIONAL;
+ warnmsg = G_("assuming signed overflow does not occur when "
+ "simplifying conditional to constant");
+ }
else
{
- value_range_t *vr = get_value_range (cond);
- retval = compare_range_with_value (NE_EXPR, vr, boolean_false_node,
- strict_overflow_p);
+ wc = WARN_STRICT_OVERFLOW_COMPARISON;
+ warnmsg = G_("assuming signed overflow does not occur when "
+ "simplifying conditional");
}
- /* If COND has a known boolean range, return it. */
- if (retval)
- return retval;
+ if (issue_strict_overflow_warning (wc))
+ {
+ location_t location;
- /* Otherwise, if COND has a symbolic range of exactly one value,
- return it. */
- vr = get_value_range (cond);
- if (vr->type == VR_RANGE && vr->min == vr->max)
- return vr->min;
+ if (!gimple_has_location (stmt))
+ location = input_location;
+ else
+ location = gimple_location (stmt);
+ warning (OPT_Wstrict_overflow, "%H%s", &location, warnmsg);
+ }
}
- 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 (warn_type_limits
+ && ret && only_ranges
+ && TREE_CODE_CLASS (code) == tcc_comparison
+ && TREE_CODE (op0) == 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 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 (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));
+ 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");
}
- else
+
+ if (warnmsg)
{
- value_range_t *vr0, *vr1;
+ location_t location;
- vr0 = (TREE_CODE (op0) == SSA_NAME) ? get_value_range (op0) : NULL;
- vr1 = (TREE_CODE (op1) == SSA_NAME) ? get_value_range (op1) : NULL;
+ if (!gimple_has_location (stmt))
+ location = input_location;
+ else
+ location = gimple_location (stmt);
- 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));
+ warning (OPT_Wtype_limits, "%H%s", &location, warnmsg);
}
}
- /* Anything else cannot be computed statically. */
- return NULL_TREE;
+ return ret;
}
SSA_PROP_VARYING. */
static enum ssa_prop_result
-vrp_visit_cond_stmt (tree stmt, edge *taken_edge_p)
+vrp_visit_cond_stmt (gimple stmt, edge *taken_edge_p)
{
- tree cond, val;
+ tree val;
bool sop;
*taken_edge_p = NULL;
- /* FIXME. Handle SWITCH_EXPRs. But first, the assert pass needs to
- add ASSERT_EXPRs for them. */
- if (TREE_CODE (stmt) == SWITCH_EXPR)
- return SSA_PROP_VARYING;
-
- cond = COND_EXPR_COND (stmt);
-
if (dump_file && (dump_flags & TDF_DETAILS))
{
tree use;
ssa_op_iter i;
fprintf (dump_file, "\nVisiting conditional with predicate: ");
- print_generic_expr (dump_file, cond, 0);
+ print_gimple_stmt (dump_file, stmt, 0, 0);
fprintf (dump_file, "\nWith known ranges\n");
FOR_EACH_SSA_TREE_OPERAND (use, stmt, i, SSA_OP_USE)
MICO, TRAMP3D and SPEC2000) showed that doing this results in
4 more predicates folded in SPEC. */
sop = false;
- val = vrp_evaluate_conditional (cond, false, &sop);
+
+ val = vrp_evaluate_conditional_warnv_with_ops (gimple_cond_code (stmt),
+ gimple_cond_lhs (stmt),
+ gimple_cond_rhs (stmt),
+ false, &sop, NULL);
if (val)
{
if (!sop)
- *taken_edge_p = find_taken_edge (bb_for_stmt (stmt), val);
+ *taken_edge_p = find_taken_edge (gimple_bb (stmt), val);
else
{
if (dump_file && (dump_flags & TDF_DETAILS))
return (*taken_edge_p) ? SSA_PROP_INTERESTING : SSA_PROP_VARYING;
}
+/* Searches the case label vector VEC for the index *IDX of the CASE_LABEL
+ that includes the value VAL. The search is restricted to the range
+ [START_IDX, n - 1] where n is the size of VEC.
+
+ If there is a CASE_LABEL for VAL, its index is placed in IDX and true is
+ returned.
+
+ If there is no CASE_LABEL for VAL and the is one that is larger than VAL,
+ it is placed in IDX and false is returned.
+
+ If VAL is larger than any CASE_LABEL, n is placed on IDX and false is
+ returned. */
+
+static bool
+find_case_label_index (gimple stmt, size_t start_idx, tree val, size_t *idx)
+{
+ size_t n = gimple_switch_num_labels (stmt);
+ size_t low, high;
+
+ /* Find case label for minimum of the value range or the next one.
+ At each iteration we are searching in [low, high - 1]. */
+
+ for (low = start_idx, high = n; high != low; )
+ {
+ tree t;
+ int cmp;
+ /* Note that i != high, so we never ask for n. */
+ size_t i = (high + low) / 2;
+ t = gimple_switch_label (stmt, i);
+
+ /* Cache the result of comparing CASE_LOW and val. */
+ cmp = tree_int_cst_compare (CASE_LOW (t), val);
+
+ if (cmp == 0)
+ {
+ /* Ranges cannot be empty. */
+ *idx = i;
+ return true;
+ }
+ else if (cmp > 0)
+ high = i;
+ else
+ {
+ low = i + 1;
+ if (CASE_HIGH (t) != NULL
+ && tree_int_cst_compare (CASE_HIGH (t), val) >= 0)
+ {
+ *idx = i;
+ return true;
+ }
+ }
+ }
+
+ *idx = high;
+ return false;
+}
+
+/* Searches the case label vector VEC for the range of CASE_LABELs that is used
+ for values between MIN and MAX. The first index is placed in MIN_IDX. The
+ last index is placed in MAX_IDX. If the range of CASE_LABELs is empty
+ then MAX_IDX < MIN_IDX.
+ Returns true if the default label is not needed. */
+
+static bool
+find_case_label_range (gimple stmt, tree min, tree max, size_t *min_idx,
+ size_t *max_idx)
+{
+ size_t i, j;
+ bool min_take_default = !find_case_label_index (stmt, 1, min, &i);
+ bool max_take_default = !find_case_label_index (stmt, i, max, &j);
+
+ if (i == j
+ && min_take_default
+ && max_take_default)
+ {
+ /* Only the default case label reached.
+ Return an empty range. */
+ *min_idx = 1;
+ *max_idx = 0;
+ return false;
+ }
+ else
+ {
+ bool take_default = min_take_default || max_take_default;
+ tree low, high;
+ size_t k;
+
+ if (max_take_default)
+ j--;
+
+ /* If the case label range is continuous, we do not need
+ the default case label. Verify that. */
+ high = CASE_LOW (gimple_switch_label (stmt, i));
+ if (CASE_HIGH (gimple_switch_label (stmt, i)))
+ high = CASE_HIGH (gimple_switch_label (stmt, i));
+ for (k = i + 1; k <= j; ++k)
+ {
+ low = CASE_LOW (gimple_switch_label (stmt, k));
+ if (!integer_onep (int_const_binop (MINUS_EXPR, low, high, 0)))
+ {
+ take_default = true;
+ break;
+ }
+ high = low;
+ if (CASE_HIGH (gimple_switch_label (stmt, k)))
+ high = CASE_HIGH (gimple_switch_label (stmt, k));
+ }
+
+ *min_idx = i;
+ *max_idx = j;
+ return !take_default;
+ }
+}
+
+/* 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 (gimple stmt, edge *taken_edge_p)
+{
+ tree op, val;
+ value_range_t *vr;
+ size_t i = 0, j = 0, n;
+ bool take_default;
+
+ *taken_edge_p = NULL;
+ op = gimple_switch_index (stmt);
+ 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. */
+ n = gimple_switch_num_labels (stmt);
+
+ take_default = !find_case_label_range (stmt, vr->min, vr->max, &i, &j);
+
+ /* Check if the range spans no CASE_LABEL. If so, we only reach the default
+ label */
+ if (j < i)
+ {
+ gcc_assert (take_default);
+ val = gimple_switch_default_label (stmt);
+ }
+ else
+ {
+ /* Check if labels with index i to j and maybe the default label
+ are all reaching the same label. */
+
+ val = gimple_switch_label (stmt, i);
+ if (take_default
+ && CASE_LABEL (gimple_switch_default_label (stmt))
+ != 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 (gimple_switch_label (stmt, 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 (gimple_bb (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
If STMT produces a varying value, return SSA_PROP_VARYING. */
static enum ssa_prop_result
-vrp_visit_stmt (tree stmt, edge *taken_edge_p, tree *output_p)
+vrp_visit_stmt (gimple stmt, edge *taken_edge_p, tree *output_p)
{
tree def;
ssa_op_iter iter;
- stmt_ann_t ann;
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nVisiting statement:\n");
- print_generic_stmt (dump_file, stmt, dump_flags);
+ print_gimple_stmt (dump_file, stmt, 0, dump_flags);
fprintf (dump_file, "\n");
}
- ann = stmt_ann (stmt);
- if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+ if (is_gimple_assign (stmt) || is_gimple_call (stmt))
{
- tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
-
/* In general, assignments with virtual operands are not useful
for deriving ranges, with the obvious exception of calls to
builtin functions. */
- if ((TREE_CODE (rhs) == CALL_EXPR
- && TREE_CODE (CALL_EXPR_FN (rhs)) == ADDR_EXPR
- && DECL_P (TREE_OPERAND (CALL_EXPR_FN (rhs), 0))
- && DECL_IS_BUILTIN (TREE_OPERAND (CALL_EXPR_FN (rhs), 0)))
+
+ if ((is_gimple_call (stmt)
+ && gimple_call_fndecl (stmt) != NULL_TREE
+ && DECL_IS_BUILTIN (gimple_call_fndecl (stmt)))
|| ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
- return vrp_visit_assignment (stmt, output_p);
+ return vrp_visit_assignment_or_call (stmt, output_p);
}
- else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR)
+ else if (gimple_code (stmt) == GIMPLE_COND)
return vrp_visit_cond_stmt (stmt, taken_edge_p);
+ else if (gimple_code (stmt) == GIMPLE_SWITCH)
+ 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)
value ranges, set a new range for the LHS of PHI. */
static enum ssa_prop_result
-vrp_visit_phi_node (tree phi)
+vrp_visit_phi_node (gimple phi)
{
- int i;
+ size_t i;
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);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nVisiting PHI node: ");
- print_generic_expr (dump_file, phi, dump_flags);
+ print_gimple_stmt (dump_file, phi, 0, dump_flags);
}
- for (i = 0; i < PHI_NUM_ARGS (phi); i++)
+ edges = 0;
+ for (i = 0; i < gimple_phi_num_args (phi); i++)
{
- edge e = PHI_ARG_EDGE (phi, i);
+ edge e = gimple_phi_arg_edge (phi, i);
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file,
"\n Argument #%d (%d -> %d %sexecutable)\n",
- i, e->src->index, e->dest->index,
+ (int) i, e->src->index, e->dest->index,
(e->flags & EDGE_EXECUTABLE) ? "" : "not ");
}
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 =
return SSA_PROP_VARYING;
}
+/* Simplify boolean operations if the source is known
+ to be already a boolean. */
+static bool
+simplify_truth_ops_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
+{
+ enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
+ tree val = NULL;
+ tree op0, op1;
+ value_range_t *vr;
+ bool sop = false;
+ bool need_conversion;
+
+ op0 = gimple_assign_rhs1 (stmt);
+ vr = get_value_range (op0);
+ if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
+ {
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+
+ if (rhs_code == TRUTH_NOT_EXPR)
+ {
+ rhs_code = NE_EXPR;
+ op1 = build_int_cst (TREE_TYPE (op0), 1);
+ }
+ else
+ {
+ op1 = gimple_assign_rhs2 (stmt);
+
+ /* Reduce number of cases to handle. */
+ if (is_gimple_min_invariant (op1))
+ {
+ /* Exclude anything that should have been already folded. */
+ gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR
+ || rhs_code == TRUTH_XOR_EXPR);
+ gcc_assert (integer_zerop (op1) || integer_onep (op1)
+ || integer_all_onesp (op1));
+
+ /* Limit the number of cases we have to consider. */
+ if (rhs_code == EQ_EXPR)
+ {
+ rhs_code = NE_EXPR;
+ op1 = fold_unary (TRUTH_NOT_EXPR, TREE_TYPE (op1), op1);
+ }
+ }
+ else
+ {
+ /* Punt on A == B as there is no BIT_XNOR_EXPR. */
+ if (rhs_code == EQ_EXPR)
+ return false;
+
+ if (TYPE_PRECISION (TREE_TYPE (op1)) != 1)
+ {
+ vr = get_value_range (op1);
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+
+ val = compare_range_with_value (LE_EXPR, vr, integer_one_node, &sop);
+ if (!val || !integer_onep (val))
+ return false;
+ }
+ }
+ }
+
+ if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
+ {
+ location_t location;
+
+ if (!gimple_has_location (stmt))
+ location = input_location;
+ else
+ location = gimple_location (stmt);
+
+ if (rhs_code == TRUTH_AND_EXPR || rhs_code == TRUTH_OR_EXPR)
+ warning_at (location, OPT_Wstrict_overflow,
+ _("assuming signed overflow does not occur when "
+ "simplifying && or || to & or |"));
+ else
+ warning_at (location, OPT_Wstrict_overflow,
+ _("assuming signed overflow does not occur when "
+ "simplifying ==, != or ! to identity or ^"));
+ }
+
+ need_conversion =
+ !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
+ TREE_TYPE (op0));
+
+ switch (rhs_code)
+ {
+ case TRUTH_AND_EXPR:
+ rhs_code = BIT_AND_EXPR;
+ break;
+ case TRUTH_OR_EXPR:
+ rhs_code = BIT_IOR_EXPR;
+ break;
+ case TRUTH_XOR_EXPR:
+ case NE_EXPR:
+ if (integer_zerop (op1))
+ {
+ gimple_assign_set_rhs_with_ops (gsi,
+ need_conversion ? NOP_EXPR : SSA_NAME,
+ op0, NULL);
+ update_stmt (gsi_stmt (*gsi));
+ return true;
+ }
+
+ rhs_code = BIT_XOR_EXPR;
+ break;
+ default:
+ gcc_unreachable ();
+ }
+
+ if (need_conversion)
+ return false;
+
+ gimple_assign_set_rhs_with_ops (gsi, rhs_code, op0, op1);
+ update_stmt (gsi_stmt (*gsi));
+ return true;
+}
+
/* Simplify a division or modulo operator to a right shift or
bitwise and if the first operand is unsigned or is greater
than zero and the second operand is an exact power of two. */
-static void
-simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code)
+static bool
+simplify_div_or_mod_using_ranges (gimple stmt)
{
+ enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
tree val = NULL;
- tree op = TREE_OPERAND (rhs, 0);
- value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
+ tree op0 = gimple_assign_rhs1 (stmt);
+ tree op1 = gimple_assign_rhs2 (stmt);
+ value_range_t *vr = get_value_range (gimple_assign_rhs1 (stmt));
- if (TYPE_UNSIGNED (TREE_TYPE (op)))
+ if (TYPE_UNSIGNED (TREE_TYPE (op0)))
{
val = integer_one_node;
}
{
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
+ && integer_onep (val)
+ && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
+ {
+ location_t location;
+
+ if (!gimple_has_location (stmt))
+ location = input_location;
+ else
+ location = gimple_location (stmt);
+ warning (OPT_Wstrict_overflow,
+ ("%Hassuming signed overflow does not occur when "
+ "simplifying / or %% to >> or &"),
+ &location);
+ }
}
if (val && integer_onep (val))
{
tree t;
- tree op0 = TREE_OPERAND (rhs, 0);
- tree op1 = TREE_OPERAND (rhs, 1);
if (rhs_code == TRUNC_DIV_EXPR)
{
t = build_int_cst (NULL_TREE, tree_log2 (op1));
- t = build2 (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
+ gimple_assign_set_rhs_code (stmt, RSHIFT_EXPR);
+ gimple_assign_set_rhs1 (stmt, op0);
+ gimple_assign_set_rhs2 (stmt, t);
}
else
{
t = build_int_cst (TREE_TYPE (op1), 1);
t = int_const_binop (MINUS_EXPR, op1, t, 0);
t = fold_convert (TREE_TYPE (op0), t);
- t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
+
+ gimple_assign_set_rhs_code (stmt, BIT_AND_EXPR);
+ gimple_assign_set_rhs1 (stmt, op0);
+ gimple_assign_set_rhs2 (stmt, t);
}
- GIMPLE_STMT_OPERAND (stmt, 1) = t;
update_stmt (stmt);
+ return true;
}
+
+ return false;
}
/* If the operand to an ABS_EXPR is >= 0, then eliminate the
ABS_EXPR. If the operand is <= 0, then simplify the
ABS_EXPR into a NEGATE_EXPR. */
-static void
-simplify_abs_using_ranges (tree stmt, tree rhs)
+static bool
+simplify_abs_using_ranges (gimple stmt)
{
tree val = NULL;
- tree op = TREE_OPERAND (rhs, 0);
+ tree op = gimple_assign_rhs1 (stmt);
tree type = TREE_TYPE (op);
- value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
+ value_range_t *vr = get_value_range (op);
if (TYPE_UNSIGNED (type))
{
if (val
&& (integer_onep (val) || integer_zerop (val)))
{
- tree t;
+ if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
+ {
+ location_t location;
+ if (!gimple_has_location (stmt))
+ location = input_location;
+ else
+ location = gimple_location (stmt);
+ warning (OPT_Wstrict_overflow,
+ ("%Hassuming signed overflow does not occur when "
+ "simplifying abs (X) to X or -X"),
+ &location);
+ }
+
+ gimple_assign_set_rhs1 (stmt, op);
if (integer_onep (val))
- t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
+ gimple_assign_set_rhs_code (stmt, NEGATE_EXPR);
else
- t = op;
-
- GIMPLE_STMT_OPERAND (stmt, 1) = t;
+ gimple_assign_set_rhs_code (stmt, SSA_NAME);
update_stmt (stmt);
+ return true;
}
}
+
+ return false;
}
/* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
{
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;
}
}
test if the range information indicates only one value can satisfy
the original conditional. */
-static void
-simplify_cond_using_ranges (tree stmt)
+static bool
+simplify_cond_using_ranges (gimple stmt)
{
- tree cond = COND_EXPR_COND (stmt);
- tree op0 = TREE_OPERAND (cond, 0);
- tree op1 = TREE_OPERAND (cond, 1);
- enum tree_code cond_code = TREE_CODE (cond);
+ tree op0 = gimple_cond_lhs (stmt);
+ tree op1 = gimple_cond_rhs (stmt);
+ enum tree_code cond_code = gimple_cond_code (stmt);
if (cond_code != NE_EXPR
&& cond_code != EQ_EXPR
able to simplify this conditional. */
if (vr->type == VR_RANGE)
{
- tree new = test_for_singularity (cond_code, op0, op1, vr);
+ tree new_tree = test_for_singularity (cond_code, op0, op1, vr);
- if (new)
+ if (new_tree)
{
if (dump_file)
{
fprintf (dump_file, "Simplified relational ");
- print_generic_expr (dump_file, cond, 0);
+ print_gimple_stmt (dump_file, stmt, 0, 0);
fprintf (dump_file, " into ");
}
- COND_EXPR_COND (stmt)
- = build2 (EQ_EXPR, boolean_type_node, op0, new);
+ gimple_cond_set_code (stmt, EQ_EXPR);
+ gimple_cond_set_lhs (stmt, op0);
+ gimple_cond_set_rhs (stmt, new_tree);
+
update_stmt (stmt);
if (dump_file)
{
- print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
+ print_gimple_stmt (dump_file, stmt, 0, 0);
fprintf (dump_file, "\n");
}
- return;
+ return true;
}
/* Try again after inverting the condition. We only deal
with integral types here, so no need to worry about
issues with inverting FP comparisons. */
cond_code = invert_tree_comparison (cond_code, false);
- new = test_for_singularity (cond_code, op0, op1, vr);
+ new_tree = test_for_singularity (cond_code, op0, op1, vr);
- if (new)
+ if (new_tree)
{
if (dump_file)
{
fprintf (dump_file, "Simplified relational ");
- print_generic_expr (dump_file, cond, 0);
+ print_gimple_stmt (dump_file, stmt, 0, 0);
fprintf (dump_file, " into ");
}
- COND_EXPR_COND (stmt)
- = build2 (NE_EXPR, boolean_type_node, op0, new);
+ gimple_cond_set_code (stmt, NE_EXPR);
+ gimple_cond_set_lhs (stmt, op0);
+ gimple_cond_set_rhs (stmt, new_tree);
+
update_stmt (stmt);
if (dump_file)
{
- print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
+ print_gimple_stmt (dump_file, stmt, 0, 0);
fprintf (dump_file, "\n");
}
- return;
+ return true;
}
}
}
+
+ return false;
+}
+
+/* Simplify a switch statement using the value range of the switch
+ argument. */
+
+static bool
+simplify_switch_using_ranges (gimple stmt)
+{
+ tree op = gimple_switch_index (stmt);
+ value_range_t *vr;
+ bool take_default;
+ edge e;
+ edge_iterator ei;
+ size_t i = 0, j = 0, n, n2;
+ tree vec2;
+ switch_update su;
+
+ if (TREE_CODE (op) != SSA_NAME)
+ return false;
+
+ vr = get_value_range (op);
+
+ /* We can only handle integer ranges. */
+ if (vr->type != VR_RANGE
+ || symbolic_range_p (vr))
+ return false;
+
+ /* Find case label for min/max of the value range. */
+ n = gimple_switch_num_labels (stmt);
+ take_default = !find_case_label_range (stmt, vr->min, vr->max, &i, &j);
+
+ /* Bail out if this is just all edges taken. */
+ if (i == 1
+ && j == n - 1
+ && take_default)
+ return false;
+
+ /* Build a new vector of taken case labels. */
+ vec2 = make_tree_vec (j - i + 1 + (int)take_default);
+ n2 = 0;
+
+ /* Add the default edge, if necessary. */
+ if (take_default)
+ TREE_VEC_ELT (vec2, n2++) = gimple_switch_default_label (stmt);
+
+ for (; i <= j; ++i, ++n2)
+ TREE_VEC_ELT (vec2, n2) = gimple_switch_label (stmt, i);
+
+ /* Mark needed edges. */
+ for (i = 0; i < n2; ++i)
+ {
+ e = find_edge (gimple_bb (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, gimple_bb (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);
+ return false;
}
/* Simplify STMT using ranges if possible. */
-void
-simplify_stmt_using_ranges (tree stmt)
+bool
+simplify_stmt_using_ranges (gimple_stmt_iterator *gsi)
{
- if (TREE_CODE (stmt) == GIMPLE_MODIFY_STMT)
+ gimple stmt = gsi_stmt (*gsi);
+ if (is_gimple_assign (stmt))
{
- tree rhs = GIMPLE_STMT_OPERAND (stmt, 1);
- enum tree_code rhs_code = TREE_CODE (rhs);
+ enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
+
+ switch (rhs_code)
+ {
+ case EQ_EXPR:
+ case NE_EXPR:
+ case TRUTH_NOT_EXPR:
+ case TRUTH_AND_EXPR:
+ case TRUTH_OR_EXPR:
+ case TRUTH_XOR_EXPR:
+ /* Transform EQ_EXPR, NE_EXPR, TRUTH_NOT_EXPR into BIT_XOR_EXPR
+ or identity if the RHS is zero or one, and the LHS are known
+ to be boolean values. Transform all TRUTH_*_EXPR into
+ BIT_*_EXPR if both arguments are known to be boolean values. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))
+ return simplify_truth_ops_using_ranges (gsi, stmt);
+ break;
/* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
and BIT_AND_EXPR respectively if the first operand is greater
than zero and the second operand is an exact power of two. */
- if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
- && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
- && integer_pow2p (TREE_OPERAND (rhs, 1)))
- simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code);
+ case TRUNC_DIV_EXPR:
+ case TRUNC_MOD_EXPR:
+ if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))
+ && integer_pow2p (gimple_assign_rhs2 (stmt)))
+ return simplify_div_or_mod_using_ranges (stmt);
+ break;
/* Transform ABS (X) into X or -X as appropriate. */
- if (rhs_code == ABS_EXPR
- && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
- && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
- simplify_abs_using_ranges (stmt, rhs);
- }
- else if (TREE_CODE (stmt) == COND_EXPR
- && COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
- {
- simplify_cond_using_ranges (stmt);
+ case ABS_EXPR:
+ if (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))
+ return simplify_abs_using_ranges (stmt);
+ break;
+
+ default:
+ break;
+ }
}
+ else if (gimple_code (stmt) == GIMPLE_COND)
+ return simplify_cond_using_ranges (stmt);
+ else if (gimple_code (stmt) == GIMPLE_SWITCH)
+ return simplify_switch_using_ranges (stmt);
+
+ return false;
}
/* Stack of dest,src equivalency pairs that need to be restored after
restored. */
static VEC(tree,heap) *stack;
-/* A trivial wrapper so that we can present the generic jump
- threading code with a simple API for simplifying statements. */
+/* A trivial wrapper so that we can present the generic jump threading
+ code with a simple API for simplifying statements. STMT is the
+ statement we want to simplify, WITHIN_STMT provides the location
+ for any overflow warnings. */
+
static tree
-simplify_stmt_for_jump_threading (tree stmt)
+simplify_stmt_for_jump_threading (gimple stmt, gimple within_stmt)
{
- bool sop;
-
/* We only use VRP information to simplify conditionals. This is
overly conservative, but it's unclear if doing more would be
worth the compile time cost. */
- if (TREE_CODE (stmt) != COND_EXPR)
+ if (gimple_code (stmt) != GIMPLE_COND)
return NULL;
- sop = false;
- return vrp_evaluate_conditional (COND_EXPR_COND (stmt), true, &sop);
+ return vrp_evaluate_conditional (gimple_cond_code (stmt),
+ gimple_cond_lhs (stmt),
+ gimple_cond_rhs (stmt), within_stmt);
}
/* Blocks which have more than one predecessor and more than
- one successor present jump threading opportunities. ie,
+ one successor present jump threading opportunities, i.e.,
when the block is reached from a specific predecessor, we
may be able to determine which of the outgoing edges will
be traversed. When this optimization applies, we are able
identify_jump_threads (void)
{
basic_block bb;
- tree dummy;
+ gimple 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);
/* To avoid lots of silly node creation, we create a single
conditional and just modify it in-place when attempting to
thread jumps. */
- dummy = build2 (EQ_EXPR, boolean_type_node, NULL, NULL);
- dummy = build3 (COND_EXPR, void_type_node, dummy, NULL, NULL);
+ dummy = gimple_build_cond (EQ_EXPR,
+ integer_zero_node, integer_zero_node,
+ NULL, NULL);
/* Walk through all the blocks finding those which present a
potential jump threading opportunity. We could set this up
point in compilation. */
FOR_EACH_BB (bb)
{
- tree last, cond;
+ gimple last;
/* If the generic jump threading code does not find this block
interesting, then there is nothing to do. */
/* We only care about blocks ending in a COND_EXPR. While there
may be some value in handling SWITCH_EXPR here, I doubt it's
terribly important. */
- last = bsi_stmt (bsi_last (bb));
- if (TREE_CODE (last) != COND_EXPR)
+ last = gsi_stmt (gsi_last_bb (bb));
+ if (gimple_code (last) != GIMPLE_COND)
continue;
/* We're basically looking for any kind of conditional with
integral type arguments. */
- cond = COND_EXPR_COND (last);
- if ((TREE_CODE (cond) == SSA_NAME
- && INTEGRAL_TYPE_P (TREE_TYPE (cond)))
- || (COMPARISON_CLASS_P (cond)
- && TREE_CODE (TREE_OPERAND (cond, 0)) == SSA_NAME
- && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 0)))
- && (TREE_CODE (TREE_OPERAND (cond, 1)) == SSA_NAME
- || is_gimple_min_invariant (TREE_OPERAND (cond, 1)))
- && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (cond, 1)))))
+ if (TREE_CODE (gimple_cond_lhs (last)) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last)))
+ && (TREE_CODE (gimple_cond_rhs (last)) == SSA_NAME
+ || is_gimple_min_invariant (gimple_cond_rhs (last)))
+ && INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_rhs (last))))
{
edge_iterator ei;
- edge e;
/* We've got a block with multiple predecessors and multiple
successors which also ends in a suitable conditional. For
if (e->flags & (EDGE_DFS_BACK | EDGE_COMPLEX))
continue;
- thread_across_edge (dummy, e, true,
- &stack,
+ thread_across_edge (dummy, e, true, &stack,
simplify_stmt_for_jump_threading);
}
}
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;
}
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 ();
+ 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 ();
- }
-
/* 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. */
update_ssa (TODO_update_ssa);
finalize_jump_threads ();
+
+ /* 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)
+ {
+ size_t j;
+ size_t n = TREE_VEC_LENGTH (su->vec);
+ gimple_switch_set_num_labels (su->stmt, n);
+ for (j = 0; j < n; j++)
+ gimple_switch_set_label (su->stmt, j, TREE_VEC_ELT (su->vec, j));
+ }
+
+ 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);
+
+ 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_update_smt_usage, /* todo_flags_finish */
- 0 /* letter */
+ | TODO_update_ssa /* todo_flags_finish */
+ }
};
OSDN Git Service
