/* Support routines for Value Range Propagation (VRP).
- Copyright (C) 2005, 2006, 2007, 2008, 2009 Free Software Foundation, Inc.
+ Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
+ Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>.
This file is part of GCC.
#include "tree-pass.h"
#include "tree-dump.h"
#include "timevar.h"
-#include "diagnostic.h"
-#include "toplev.h"
+#include "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
+#include "diagnostic-core.h"
#include "intl.h"
#include "cfgloop.h"
#include "tree-scalar-evolution.h"
#include "tree-ssa-propagate.h"
#include "tree-chrec.h"
+#include "gimple-fold.h"
+#include "expr.h"
+#include "optabs.h"
+/* Type of value ranges. See value_range_d for a description of these
+ types. */
+enum value_range_type { VR_UNDEFINED, VR_RANGE, VR_ANTI_RANGE, VR_VARYING };
+
+/* Range of values that can be associated with an SSA_NAME after VRP
+ has executed. */
+struct value_range_d
+{
+ /* Lattice value represented by this range. */
+ enum value_range_type type;
+
+ /* Minimum and maximum values represented by this range. These
+ values should be interpreted as follows:
+
+ - If TYPE is VR_UNDEFINED or VR_VARYING then MIN and MAX must
+ be NULL.
+
+ - If TYPE == VR_RANGE then MIN holds the minimum value and
+ MAX holds the maximum value of the range [MIN, MAX].
+
+ - If TYPE == ANTI_RANGE the variable is known to NOT
+ take any values in the range [MIN, MAX]. */
+ tree min;
+ tree max;
+
+ /* Set of SSA names whose value ranges are equivalent to this one.
+ This set is only valid when TYPE is VR_RANGE or VR_ANTI_RANGE. */
+ bitmap equiv;
+};
+
+typedef struct value_range_d value_range_t;
+
+#define VR_INITIALIZER { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL }
+
/* Set of SSA names found live during the RPO traversal of the function
for still active basic-blocks. */
static sbitmap *live;
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 void vrp_intersect_ranges (value_range_t *, value_range_t *);
static tree vrp_evaluate_conditional_warnv_with_ops (enum tree_code,
tree, tree, bool, bool *,
bool *);
/* Value range array. After propagation, VR_VALUE[I] holds the range
of values that SSA name N_I may take. */
+static unsigned num_vr_values;
static value_range_t **vr_value;
+static bool values_propagated;
/* 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
static inline tree
make_overflow_infinity (tree val)
{
-#ifdef ENABLE_CHECKING
- gcc_assert (val != NULL_TREE && CONSTANT_CLASS_P (val));
-#endif
+ gcc_checking_assert (val != NULL_TREE && CONSTANT_CLASS_P (val));
val = copy_node (val);
TREE_OVERFLOW (val) = 1;
return val;
static inline tree
negative_overflow_infinity (tree type)
{
-#ifdef ENABLE_CHECKING
- gcc_assert (supports_overflow_infinity (type));
-#endif
+ gcc_checking_assert (supports_overflow_infinity (type));
return make_overflow_infinity (vrp_val_min (type));
}
static inline tree
positive_overflow_infinity (tree type)
{
-#ifdef ENABLE_CHECKING
- gcc_assert (supports_overflow_infinity (type));
-#endif
+ gcc_checking_assert (supports_overflow_infinity (type));
return make_overflow_infinity (vrp_val_max (type));
}
return vrp_val_max (TREE_TYPE (val));
else
{
-#ifdef ENABLE_CHECKING
- gcc_assert (vrp_val_is_min (val));
-#endif
+ gcc_checking_assert (vrp_val_is_min (val));
return vrp_val_min (TREE_TYPE (val));
}
}
/* Get the position number for ARG in the function signature. */
for (arg_num = 1, t = DECL_ARGUMENTS (current_function_decl);
t;
- t = TREE_CHAIN (t), arg_num++)
+ t = DECL_CHAIN (t), arg_num++)
{
if (t == arg)
break;
}
+/* Set value range VR to VR_UNDEFINED. */
+
+static inline void
+set_value_range_to_undefined (value_range_t *vr)
+{
+ vr->type = VR_UNDEFINED;
+ vr->min = vr->max = NULL_TREE;
+ if (vr->equiv)
+ bitmap_clear (vr->equiv);
+}
+
+
/* Set value range VR to VR_VARYING. */
static inline 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
+ /* Use the canonical setters for VR_UNDEFINED and VR_VARYING. */
+ if (t == VR_UNDEFINED)
+ {
+ set_value_range_to_undefined (vr);
+ return;
+ }
+ else if (t == VR_VARYING)
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
+ /* Nothing to canonicalize for symbolic ranges. */
+ if (TREE_CODE (min) != INTEGER_CST
|| TREE_CODE (max) != INTEGER_CST)
{
set_value_range (vr, t, min, max, equiv);
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);
+ tree tmp = int_const_binop (PLUS_EXPR, max, one);
+ max = int_const_binop (MINUS_EXPR, min, one);
min = tmp;
/* There's one corner case, if we had [C+1, C] before we now have
if (is_min && is_max)
{
- /* We cannot deal with empty ranges, drop to varying. */
+ /* We cannot deal with empty ranges, drop to varying.
+ ??? This could be VR_UNDEFINED instead. */
set_value_range_to_varying (vr);
return;
}
&& integer_zerop (max)))
{
tree one = build_int_cst (TREE_TYPE (max), 1);
- min = int_const_binop (PLUS_EXPR, max, one, 0);
+ min = int_const_binop (PLUS_EXPR, max, one);
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);
+ max = int_const_binop (MINUS_EXPR, min, one);
min = vrp_val_min (TREE_TYPE (min));
t = VR_RANGE;
}
}
+ /* Drop [-INF(OVF), +INF(OVF)] to varying. */
+ if (needs_overflow_infinity (TREE_TYPE (min))
+ && is_overflow_infinity (min)
+ && is_overflow_infinity (max))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
set_value_range (vr, t, min, max, equiv);
}
}
-/* Set value range VR to VR_UNDEFINED. */
-
-static inline void
-set_value_range_to_undefined (value_range_t *vr)
-{
- vr->type = VR_UNDEFINED;
- vr->min = vr->max = NULL_TREE;
- if (vr->equiv)
- bitmap_clear (vr->equiv);
-}
-
-
/* If abs (min) < abs (max), set VR to [-max, max], if
abs (min) >= abs (max), set VR to [-min, min]. */
static value_range_t *
get_value_range (const_tree var)
{
+ static const struct value_range_d vr_const_varying
+ = { VR_VARYING, NULL_TREE, NULL_TREE, NULL };
value_range_t *vr;
tree sym;
unsigned ver = SSA_NAME_VERSION (var);
if (! vr_value)
return NULL;
+ /* If we query the range for a new SSA name return an unmodifiable VARYING.
+ We should get here at most from the substitute-and-fold stage which
+ will never try to change values. */
+ if (ver >= num_vr_values)
+ return CONST_CAST (value_range_t *, &vr_const_varying);
+
vr = vr_value[ver];
if (vr)
return vr;
+ /* After propagation finished do not allocate new value-ranges. */
+ if (values_propagated)
+ return CONST_CAST (value_range_t *, &vr_const_varying);
+
/* Create a default value range. */
vr_value[ver] = vr = XCNEW (value_range_t);
/* Defer allocating the equivalence set. */
vr->equiv = NULL;
- /* If VAR is a default definition, the variable can take any value
- in VAR's type. */
+ /* If VAR is a default definition of a parameter, the variable can
+ take any value in VAR's type. */
sym = SSA_NAME_VAR (var);
if (SSA_NAME_IS_DEFAULT_DEF (var))
{
- /* Try to use the "nonnull" attribute to create ~[0, 0]
- anti-ranges for pointers. Note that this is only valid with
- default definitions of PARM_DECLs. */
- if (TREE_CODE (sym) == PARM_DECL
- && POINTER_TYPE_P (TREE_TYPE (sym))
- && nonnull_arg_p (sym))
+ if (TREE_CODE (sym) == PARM_DECL)
+ {
+ /* Try to use the "nonnull" attribute to create ~[0, 0]
+ anti-ranges for pointers. Note that this is only valid with
+ default definitions of PARM_DECLs. */
+ if (POINTER_TYPE_P (TREE_TYPE (sym))
+ && nonnull_arg_p (sym))
+ set_value_range_to_nonnull (vr, TREE_TYPE (sym));
+ else
+ set_value_range_to_varying (vr);
+ }
+ else if (TREE_CODE (sym) == RESULT_DECL
+ && DECL_BY_REFERENCE (sym))
set_value_range_to_nonnull (vr, TREE_TYPE (sym));
- else
- set_value_range_to_varying (vr);
}
return vr;
vrp_bitmap_equal_p (const_bitmap b1, const_bitmap b2)
{
return (b1 == b2
+ || ((!b1 || bitmap_empty_p (b1))
+ && (!b2 || bitmap_empty_p (b2)))
|| (b1 && b2
&& bitmap_equal_p (b1, b2)));
}
&& integer_zerop (vr->max);
}
+/* Return true if max and min of VR are INTEGER_CST. It's not necessary
+ a singleton. */
+
+static inline bool
+range_int_cst_p (value_range_t *vr)
+{
+ return (vr->type == VR_RANGE
+ && TREE_CODE (vr->max) == INTEGER_CST
+ && TREE_CODE (vr->min) == INTEGER_CST
+ && !TREE_OVERFLOW (vr->max)
+ && !TREE_OVERFLOW (vr->min));
+}
+
+/* Return true if VR is a INTEGER_CST singleton. */
+
+static inline bool
+range_int_cst_singleton_p (value_range_t *vr)
+{
+ return (range_int_cst_p (vr)
+ && tree_int_cst_equal (vr->min, vr->max));
+}
/* Return true if value range VR involves at least one symbol. */
}
-/* 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)
- || (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
gimple_assign_rhs1 (stmt),
gimple_assign_rhs2 (stmt),
strict_overflow_p);
+ case GIMPLE_TERNARY_RHS:
+ return false;
case GIMPLE_SINGLE_RHS:
return tree_single_nonnegative_warnv_p (gimple_assign_rhs1 (stmt),
strict_overflow_p);
gimple_assign_rhs1 (stmt),
gimple_assign_rhs2 (stmt),
strict_overflow_p);
+ case GIMPLE_TERNARY_RHS:
+ return false;
case GIMPLE_SINGLE_RHS:
return tree_single_nonzero_warnv_p (gimple_assign_rhs1 (stmt),
strict_overflow_p);
tree base = get_base_address (TREE_OPERAND (expr, 0));
if (base != NULL_TREE
- && TREE_CODE (base) == INDIRECT_REF
+ && TREE_CODE (base) == MEM_REF
&& TREE_CODE (TREE_OPERAND (base, 0)) == SSA_NAME)
{
value_range_t *vr = get_value_range (TREE_OPERAND (base, 0));
return (value_inside_range (zero, vr) == 1);
}
+/* Return true if *VR is know to only contain nonnegative values. */
+
+static inline bool
+value_range_nonnegative_p (value_range_t *vr)
+{
+ /* Testing for VR_ANTI_RANGE is not useful here as any anti-range
+ which would return a useful value should be encoded as a
+ VR_RANGE. */
+ if (vr->type == VR_RANGE)
+ {
+ int result = compare_values (vr->min, integer_zero_node);
+ return (result == 0 || result == 1);
+ }
+
+ return false;
+}
+
/* Return true if T, an SSA_NAME, is known to be nonnegative. Return
false otherwise or if no value range information is available. */
{
value_range_t *vr = get_value_range (t);
+ if (INTEGRAL_TYPE_P (t)
+ && TYPE_UNSIGNED (t))
+ return true;
+
if (!vr)
return false;
- /* Testing for VR_ANTI_RANGE is not useful here as any anti-range
- which would return a useful value should be encoded as a VR_RANGE. */
- if (vr->type == VR_RANGE)
- {
- int result = compare_values (vr->min, integer_zero_node);
+ return value_range_nonnegative_p (vr);
+}
- return (result == 0 || result == 1);
- }
- return false;
+/* If *VR has a value rante that is a single constant value return that,
+ otherwise return NULL_TREE. */
+
+static tree
+value_range_constant_singleton (value_range_t *vr)
+{
+ 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;
}
/* If OP has a value range with a single constant value return that,
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;
+ return value_range_constant_singleton (get_value_range (op));
}
+/* Return true if op is in a boolean [0, 1] value-range. */
+
+static bool
+op_with_boolean_value_range_p (tree op)
+{
+ value_range_t *vr;
+
+ if (TYPE_PRECISION (TREE_TYPE (op)) == 1)
+ return true;
+
+ if (integer_zerop (op)
+ || integer_onep (op))
+ return true;
+
+ if (TREE_CODE (op) != SSA_NAME)
+ return false;
+
+ vr = get_value_range (op);
+ return (vr->type == VR_RANGE
+ && integer_zerop (vr->min)
+ && integer_onep (vr->max));
+}
/* Extract value range information from an ASSERT_EXPR EXPR and store
it in *VR_P. */
extract_range_from_assert (value_range_t *vr_p, tree expr)
{
tree var, cond, limit, min, max, type;
- value_range_t *var_vr, *limit_vr;
+ value_range_t *limit_vr;
enum tree_code cond_code;
var = ASSERT_EXPR_VAR (expr);
limit = avoid_overflow_infinity (limit);
- type = TREE_TYPE (limit);
+ type = TREE_TYPE (var);
gcc_assert (limit != var);
/* For pointer arithmetic, we only keep track of pointer equality
{
min = fold_build1 (NEGATE_EXPR, TREE_TYPE (TREE_OPERAND (cond, 1)),
TREE_OPERAND (cond, 1));
- max = int_const_binop (PLUS_EXPR, limit, min, 0);
+ max = int_const_binop (PLUS_EXPR, limit, min);
cond = TREE_OPERAND (cond, 0);
}
else
/* 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);
+ min = force_fit_type_double (TREE_TYPE (var), tree_to_double_int (min),
+ 0, false);
+ max = force_fit_type_double (TREE_TYPE (var), tree_to_double_int (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
/* For LT_EXPR, we create the range [MIN, MAX - 1]. */
if (cond_code == LT_EXPR)
{
- tree one = build_int_cst (type, 1);
- max = fold_build2 (MINUS_EXPR, type, max, one);
+ if (TYPE_PRECISION (TREE_TYPE (max)) == 1
+ && !TYPE_UNSIGNED (TREE_TYPE (max)))
+ max = fold_build2 (PLUS_EXPR, TREE_TYPE (max), max,
+ build_int_cst (TREE_TYPE (max), -1));
+ else
+ max = fold_build2 (MINUS_EXPR, TREE_TYPE (max), max,
+ build_int_cst (TREE_TYPE (max), 1));
if (EXPR_P (max))
TREE_NO_WARNING (max) = 1;
}
/* For GT_EXPR, we create the range [MIN + 1, MAX]. */
if (cond_code == GT_EXPR)
{
- tree one = build_int_cst (type, 1);
- min = fold_build2 (PLUS_EXPR, type, min, one);
+ if (TYPE_PRECISION (TREE_TYPE (min)) == 1
+ && !TYPE_UNSIGNED (TREE_TYPE (min)))
+ min = fold_build2 (MINUS_EXPR, TREE_TYPE (min), min,
+ build_int_cst (TREE_TYPE (min), -1));
+ else
+ min = fold_build2 (PLUS_EXPR, TREE_TYPE (min), min,
+ build_int_cst (TREE_TYPE (min), 1));
if (EXPR_P (min))
TREE_NO_WARNING (min) = 1;
}
else
gcc_unreachable ();
- /* If VAR already had a known range, it may happen that the new
- range we have computed and VAR's range are not compatible. For
- instance,
-
- if (p_5 == NULL)
- p_6 = ASSERT_EXPR <p_5, p_5 == NULL>;
- x_7 = p_6->fld;
- p_8 = ASSERT_EXPR <p_6, p_6 != NULL>;
-
- While the above comes from a faulty program, it will cause an ICE
- later because p_8 and p_6 will have incompatible ranges and at
- the same time will be considered equivalent. A similar situation
- would arise from
-
- if (i_5 > 10)
- i_6 = ASSERT_EXPR <i_5, i_5 > 10>;
- if (i_5 < 5)
- i_7 = ASSERT_EXPR <i_6, i_6 < 5>;
-
- Again i_6 and i_7 will have incompatible ranges. It would be
- pointless to try and do anything with i_7's range because
- anything dominated by 'if (i_5 < 5)' will be optimized away.
- Note, due to the wa in which simulation proceeds, the statement
- i_7 = ASSERT_EXPR <...> we would never be visited because the
- conditional 'if (i_5 < 5)' always evaluates to false. However,
- this extra check does not hurt and may protect against future
- changes to VRP that may get into a situation similar to the
- NULL pointer dereference example.
-
- Note that these compatibility tests are only needed when dealing
- with ranges or a mix of range and anti-range. If VAR_VR and VR_P
- are both anti-ranges, they will always be compatible, because two
- anti-ranges will always have a non-empty intersection. */
-
- var_vr = get_value_range (var);
-
- /* We may need to make adjustments when VR_P and VAR_VR are numeric
- ranges or anti-ranges. */
- if (vr_p->type == VR_VARYING
- || vr_p->type == VR_UNDEFINED
- || var_vr->type == VR_VARYING
- || var_vr->type == VR_UNDEFINED
- || symbolic_range_p (vr_p)
- || symbolic_range_p (var_vr))
- return;
-
- if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
- {
- /* If the two ranges have a non-empty intersection, we can
- refine the resulting range. Since the assert expression
- creates an equivalency and at the same time it asserts a
- predicate, we can take the intersection of the two ranges to
- get better precision. */
- if (value_ranges_intersect_p (var_vr, vr_p))
- {
- /* Use the larger of the two minimums. */
- if (compare_values (vr_p->min, var_vr->min) == -1)
- min = var_vr->min;
- else
- min = vr_p->min;
-
- /* Use the smaller of the two maximums. */
- if (compare_values (vr_p->max, var_vr->max) == 1)
- max = var_vr->max;
- else
- max = vr_p->max;
-
- set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
- }
- else
- {
- /* The two ranges do not intersect, set the new range to
- VARYING, because we will not be able to do anything
- meaningful with it. */
- set_value_range_to_varying (vr_p);
- }
- }
- else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
- || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
- {
- /* A range and an anti-range will cancel each other only if
- their ends are the same. For instance, in the example above,
- p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible,
- so VR_P should be set to VR_VARYING. */
- if (compare_values (var_vr->min, vr_p->min) == 0
- && compare_values (var_vr->max, vr_p->max) == 0)
- set_value_range_to_varying (vr_p);
- else
- {
- tree min, max, anti_min, anti_max, real_min, real_max;
- int cmp;
-
- /* We want to compute the logical AND of the two ranges;
- there are three cases to consider.
-
-
- 1. The VR_ANTI_RANGE range is completely within the
- VR_RANGE and the endpoints of the ranges are
- different. In that case the resulting range
- should be whichever range is more precise.
- Typically that will be the VR_RANGE.
-
- 2. The VR_ANTI_RANGE is completely disjoint from
- the VR_RANGE. In this case the resulting range
- should be the VR_RANGE.
-
- 3. There is some overlap between the VR_ANTI_RANGE
- and the VR_RANGE.
-
- 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
- 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
- within the VR_RANGE, then the result is a new
- VR_RANGE starting at the low limit of the original
- VR_RANGE and extending to the low limit of the
- VR_ANTI_RANGE - 1. */
- if (vr_p->type == VR_ANTI_RANGE)
- {
- anti_min = vr_p->min;
- anti_max = vr_p->max;
- real_min = var_vr->min;
- real_max = var_vr->max;
- }
- else
- {
- anti_min = var_vr->min;
- anti_max = var_vr->max;
- real_min = vr_p->min;
- real_max = vr_p->max;
- }
-
-
- /* Case 1, VR_ANTI_RANGE completely within VR_RANGE,
- not including any endpoints. */
- if (compare_values (anti_max, real_max) == -1
- && compare_values (anti_min, real_min) == 1)
- {
- /* 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. */
- else if (compare_values (anti_min, real_max) == 1
- || compare_values (anti_max, real_min) == -1)
- {
- set_value_range (vr_p, VR_RANGE, real_min,
- real_max, vr_p->equiv);
- }
- /* Case 3a, the anti-range extends into the low
- part of the real range. Thus creating a new
- low for the real range. */
- else if (((cmp = compare_values (anti_max, real_min)) == 1
- || cmp == 0)
- && compare_values (anti_max, real_max) == -1)
- {
- gcc_assert (!is_positive_overflow_infinity (anti_max));
- if (needs_overflow_infinity (TREE_TYPE (anti_max))
- && vrp_val_is_max (anti_max))
- {
- if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
- {
- set_value_range_to_varying (vr_p);
- return;
- }
- min = positive_overflow_infinity (TREE_TYPE (var_vr->min));
- }
- 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);
- }
- /* Case 3b, the anti-range extends into the high
- part of the real range. Thus creating a new
- higher for the real range. */
- else if (compare_values (anti_min, real_min) == 1
- && ((cmp = compare_values (anti_min, real_max)) == -1
- || cmp == 0))
- {
- gcc_assert (!is_negative_overflow_infinity (anti_min));
- if (needs_overflow_infinity (TREE_TYPE (anti_min))
- && vrp_val_is_min (anti_min))
- {
- if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
- {
- set_value_range_to_varying (vr_p);
- return;
- }
- max = negative_overflow_infinity (TREE_TYPE (var_vr->min));
- }
- 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);
- }
- }
- }
+ /* Finally intersect the new range with what we already know about var. */
+ vrp_intersect_ranges (vr_p, get_value_range (var));
}
{
tree res;
- res = int_const_binop (code, val1, val2, 0);
+ res = int_const_binop (code, val1, val2);
/* If we are using unsigned arithmetic, operate symbolically
on -INF and +INF as int_const_binop only handles signed overflow. */
{
tree tmp = int_const_binop (TRUNC_DIV_EXPR,
res,
- val1, 0);
+ val1);
int check = compare_values (tmp, val2);
if (check != 0)
}
-/* Extract range information from a binary expression EXPR based on
- the ranges of each of its operands and the expression code. */
+/* For range VR compute two double_int bitmasks. In *MAY_BE_NONZERO
+ bitmask if some bit is unset, it means for all numbers in the range
+ the bit is 0, otherwise it might be 0 or 1. In *MUST_BE_NONZERO
+ bitmask if some bit is set, it means for all numbers in the range
+ the bit is 1, otherwise it might be 0 or 1. */
-static void
-extract_range_from_binary_expr (value_range_t *vr,
- enum tree_code code,
- tree expr_type, tree op0, tree op1)
+static bool
+zero_nonzero_bits_from_vr (value_range_t *vr,
+ double_int *may_be_nonzero,
+ double_int *must_be_nonzero)
{
- enum value_range_type type;
- 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 };
+ *may_be_nonzero = double_int_minus_one;
+ *must_be_nonzero = double_int_zero;
+ if (!range_int_cst_p (vr))
+ return false;
- /* Not all binary expressions can be applied to ranges in a
- 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 != 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;
- }
+ if (range_int_cst_singleton_p (vr))
+ {
+ *may_be_nonzero = tree_to_double_int (vr->min);
+ *must_be_nonzero = *may_be_nonzero;
+ }
+ else if (tree_int_cst_sgn (vr->min) >= 0
+ || tree_int_cst_sgn (vr->max) < 0)
+ {
+ double_int dmin = tree_to_double_int (vr->min);
+ double_int dmax = tree_to_double_int (vr->max);
+ double_int xor_mask = double_int_xor (dmin, dmax);
+ *may_be_nonzero = double_int_ior (dmin, dmax);
+ *must_be_nonzero = double_int_and (dmin, dmax);
+ if (xor_mask.high != 0)
+ {
+ unsigned HOST_WIDE_INT mask
+ = ((unsigned HOST_WIDE_INT) 1
+ << floor_log2 (xor_mask.high)) - 1;
+ may_be_nonzero->low = ALL_ONES;
+ may_be_nonzero->high |= mask;
+ must_be_nonzero->low = 0;
+ must_be_nonzero->high &= ~mask;
+ }
+ else if (xor_mask.low != 0)
+ {
+ unsigned HOST_WIDE_INT mask
+ = ((unsigned HOST_WIDE_INT) 1
+ << floor_log2 (xor_mask.low)) - 1;
+ may_be_nonzero->low |= mask;
+ must_be_nonzero->low &= ~mask;
}
- 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. */
- if (TREE_CODE (op0) == SSA_NAME)
- vr0 = *(get_value_range (op0));
- else if (is_gimple_min_invariant (op0))
- set_value_range_to_value (&vr0, op0, NULL);
- else
- set_value_range_to_varying (&vr0);
+ return true;
+}
- if (TREE_CODE (op1) == SSA_NAME)
- vr1 = *(get_value_range (op1));
- else if (is_gimple_min_invariant (op1))
- set_value_range_to_value (&vr1, op1, NULL);
- else
- set_value_range_to_varying (&vr1);
+/* Create two value-ranges in *VR0 and *VR1 from the anti-range *AR
+ so that *VR0 U *VR1 == *AR. Returns true if that is possible,
+ false otherwise. If *AR can be represented with a single range
+ *VR1 will be VR_UNDEFINED. */
- /* If either range is UNDEFINED, so is the result. */
- if (vr0.type == VR_UNDEFINED || vr1.type == VR_UNDEFINED)
- {
- set_value_range_to_undefined (vr);
- return;
- }
+static bool
+ranges_from_anti_range (value_range_t *ar,
+ value_range_t *vr0, value_range_t *vr1)
+{
+ tree type = TREE_TYPE (ar->min);
- /* The type of the resulting value range defaults to VR0.TYPE. */
+ vr0->type = VR_UNDEFINED;
+ vr1->type = VR_UNDEFINED;
+
+ if (ar->type != VR_ANTI_RANGE
+ || TREE_CODE (ar->min) != INTEGER_CST
+ || TREE_CODE (ar->max) != INTEGER_CST
+ || !vrp_val_min (type)
+ || !vrp_val_max (type))
+ return false;
+
+ if (!vrp_val_is_min (ar->min))
+ {
+ vr0->type = VR_RANGE;
+ vr0->min = vrp_val_min (type);
+ vr0->max
+ = double_int_to_tree (type,
+ double_int_sub (tree_to_double_int (ar->min),
+ double_int_one));
+ }
+ if (!vrp_val_is_max (ar->max))
+ {
+ vr1->type = VR_RANGE;
+ vr1->min
+ = double_int_to_tree (type,
+ double_int_add (tree_to_double_int (ar->max),
+ double_int_one));
+ vr1->max = vrp_val_max (type);
+ }
+ if (vr0->type == VR_UNDEFINED)
+ {
+ *vr0 = *vr1;
+ vr1->type = VR_UNDEFINED;
+ }
+
+ return vr0->type != VR_UNDEFINED;
+}
+
+/* Helper to extract a value-range *VR for a multiplicative operation
+ *VR0 CODE *VR1. */
+
+static void
+extract_range_from_multiplicative_op_1 (value_range_t *vr,
+ enum tree_code code,
+ value_range_t *vr0, value_range_t *vr1)
+{
+ enum value_range_type type;
+ tree val[4];
+ size_t i;
+ tree min, max;
+ bool sop;
+ int cmp;
+
+ /* Multiplications, divisions and shifts 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
+ maximum values for the new range. One approach is to figure
+ out all the variations of range combinations and do the
+ operations.
+
+ However, this involves several calls to compare_values and it
+ is pretty convoluted. It's simpler to do the 4 operations
+ (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
+ MAX1) and then figure the smallest and largest values to form
+ the new range. */
+ gcc_assert (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);
+ gcc_assert ((vr0->type == VR_RANGE
+ || (code == MULT_EXPR && vr0->type == VR_ANTI_RANGE))
+ && vr0->type == vr1->type);
+
+ type = vr0->type;
+
+ /* Compute the 4 cross operations. */
+ sop = false;
+ val[0] = vrp_int_const_binop (code, vr0->min, vr1->min);
+ if (val[0] == NULL_TREE)
+ sop = true;
+
+ if (vr1->max == vr1->min)
+ val[1] = NULL_TREE;
+ else
+ {
+ val[1] = vrp_int_const_binop (code, vr0->min, vr1->max);
+ if (val[1] == NULL_TREE)
+ sop = true;
+ }
+
+ if (vr0->max == vr0->min)
+ val[2] = NULL_TREE;
+ else
+ {
+ val[2] = vrp_int_const_binop (code, vr0->max, vr1->min);
+ if (val[2] == NULL_TREE)
+ sop = true;
+ }
+
+ if (vr0->min == vr0->max || vr1->min == vr1->max)
+ val[3] = NULL_TREE;
+ else
+ {
+ val[3] = vrp_int_const_binop (code, vr0->max, vr1->max);
+ if (val[3] == NULL_TREE)
+ sop = true;
+ }
+
+ if (sop)
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
+ /* Set MIN to the minimum of VAL[i] and MAX to the maximum
+ of VAL[i]. */
+ min = val[0];
+ max = val[0];
+ for (i = 1; i < 4; i++)
+ {
+ if (!is_gimple_min_invariant (min)
+ || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
+ || !is_gimple_min_invariant (max)
+ || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
+ break;
+
+ if (val[i])
+ {
+ if (!is_gimple_min_invariant (val[i])
+ || (TREE_OVERFLOW (val[i])
+ && !is_overflow_infinity (val[i])))
+ {
+ /* If we found an overflowed value, set MIN and MAX
+ to it so that we set the resulting range to
+ VARYING. */
+ min = max = val[i];
+ break;
+ }
+
+ if (compare_values (val[i], min) == -1)
+ min = val[i];
+
+ if (compare_values (val[i], max) == 1)
+ max = val[i];
+ }
+ }
+
+ /* If either MIN or MAX overflowed, then set the resulting range to
+ VARYING. But we do accept an overflow infinity
+ representation. */
+ if (min == NULL_TREE
+ || !is_gimple_min_invariant (min)
+ || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
+ || max == NULL_TREE
+ || !is_gimple_min_invariant (max)
+ || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
+ /* 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;
+ }
+
+ cmp = compare_values (min, max);
+ if (cmp == -2 || cmp == 1)
+ {
+ /* If the new range has its limits swapped around (MIN > MAX),
+ then the operation caused one of them to wrap around, mark
+ the new range VARYING. */
+ set_value_range_to_varying (vr);
+ }
+ else
+ set_value_range (vr, type, min, max, NULL);
+}
+
+/* Extract range information from a binary operation CODE based on
+ the ranges of each of its operands, *VR0 and *VR1 with resulting
+ type EXPR_TYPE. The resulting range is stored in *VR. */
+
+static void
+extract_range_from_binary_expr_1 (value_range_t *vr,
+ enum tree_code code, tree expr_type,
+ value_range_t *vr0_, value_range_t *vr1_)
+{
+ value_range_t vr0 = *vr0_, vr1 = *vr1_;
+ value_range_t vrtem0 = VR_INITIALIZER, vrtem1 = VR_INITIALIZER;
+ enum value_range_type type;
+ tree min = NULL_TREE, max = NULL_TREE;
+ int cmp;
+
+ if (!INTEGRAL_TYPE_P (expr_type)
+ && !POINTER_TYPE_P (expr_type))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
+ /* Not all binary expressions can be applied to ranges in a
+ 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 != TRUNC_MOD_EXPR
+ && code != RSHIFT_EXPR
+ && code != LSHIFT_EXPR
+ && code != MIN_EXPR
+ && code != MAX_EXPR
+ && code != BIT_AND_EXPR
+ && code != BIT_IOR_EXPR
+ && code != BIT_XOR_EXPR)
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
+ /* If both ranges are UNDEFINED, so is the result. */
+ if (vr0.type == VR_UNDEFINED && vr1.type == VR_UNDEFINED)
+ {
+ set_value_range_to_undefined (vr);
+ return;
+ }
+ /* If one of the ranges is UNDEFINED drop it to VARYING for the following
+ code. At some point we may want to special-case operations that
+ have UNDEFINED result for all or some value-ranges of the not UNDEFINED
+ operand. */
+ else if (vr0.type == VR_UNDEFINED)
+ set_value_range_to_varying (&vr0);
+ else if (vr1.type == VR_UNDEFINED)
+ set_value_range_to_varying (&vr1);
+
+ /* Now canonicalize anti-ranges to ranges when they are not symbolic
+ and express ~[] op X as ([]' op X) U ([]'' op X). */
+ if (vr0.type == VR_ANTI_RANGE
+ && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
+ {
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &vrtem0, vr1_);
+ if (vrtem1.type != VR_UNDEFINED)
+ {
+ value_range_t vrres = VR_INITIALIZER;
+ extract_range_from_binary_expr_1 (&vrres, code, expr_type,
+ &vrtem1, vr1_);
+ vrp_meet (vr, &vrres);
+ }
+ return;
+ }
+ /* Likewise for X op ~[]. */
+ if (vr1.type == VR_ANTI_RANGE
+ && ranges_from_anti_range (&vr1, &vrtem0, &vrtem1))
+ {
+ extract_range_from_binary_expr_1 (vr, code, expr_type, vr0_, &vrtem0);
+ if (vrtem1.type != VR_UNDEFINED)
+ {
+ value_range_t vrres = VR_INITIALIZER;
+ extract_range_from_binary_expr_1 (&vrres, code, expr_type,
+ vr0_, &vrtem1);
+ vrp_meet (vr, &vrres);
+ }
+ return;
+ }
+
+ /* The type of the resulting value range defaults to VR0.TYPE. */
type = vr0.type;
/* Refuse to operate on VARYING ranges, ranges of different kinds
divisions. TODO, we may be able to derive anti-ranges in
some cases. */
if (code != BIT_AND_EXPR
- && code != TRUTH_AND_EXPR
- && code != TRUTH_OR_EXPR
+ && code != BIT_IOR_EXPR
&& code != TRUNC_DIV_EXPR
&& code != FLOOR_DIV_EXPR
&& code != CEIL_DIV_EXPR
&& code != EXACT_DIV_EXPR
&& code != ROUND_DIV_EXPR
+ && code != TRUNC_MOD_EXPR
&& (vr0.type == VR_VARYING
|| vr1.type == VR_VARYING
|| vr0.type != vr1.type
}
/* Now evaluate the expression to determine the new range. */
- if (POINTER_TYPE_P (expr_type)
- || POINTER_TYPE_P (TREE_TYPE (op0))
- || POINTER_TYPE_P (TREE_TYPE (op1)))
+ if (POINTER_TYPE_P (expr_type))
{
if (code == MIN_EXPR || code == MAX_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 if (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
+ set_value_range_to_varying (vr);
+ }
+ else if (code == BIT_AND_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
+ set_value_range_to_varying (vr);
+ }
else
set_value_range_to_varying (vr);
/* For integer ranges, apply the operation to each end of the
range and see what we end up with. */
- if (code == TRUTH_AND_EXPR
- || code == TRUTH_OR_EXPR)
- {
- /* If one of the operands is zero, we know that the whole
- expression evaluates zero. */
- if (code == TRUTH_AND_EXPR
- && ((vr0.type == VR_RANGE
- && integer_zerop (vr0.min)
- && integer_zerop (vr0.max))
- || (vr1.type == VR_RANGE
- && integer_zerop (vr1.min)
- && integer_zerop (vr1.max))))
- {
- type = VR_RANGE;
- min = max = build_int_cst (expr_type, 0);
- }
- /* If one of the operands is one, we know that the whole
- expression evaluates one. */
- else if (code == TRUTH_OR_EXPR
- && ((vr0.type == VR_RANGE
- && integer_onep (vr0.min)
- && integer_onep (vr0.max))
- || (vr1.type == VR_RANGE
- && integer_onep (vr1.min)
- && integer_onep (vr1.max))))
- {
- type = VR_RANGE;
- min = max = build_int_cst (expr_type, 1);
- }
- else if (vr0.type != VR_VARYING
- && vr1.type != VR_VARYING
- && vr0.type == vr1.type
- && !symbolic_range_p (&vr0)
- && !overflow_infinity_range_p (&vr0)
- && !symbolic_range_p (&vr1)
- && !overflow_infinity_range_p (&vr1))
- {
- /* Boolean expressions cannot be folded with int_const_binop. */
- 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, expr_type);
- return;
- }
- }
- else if (code == PLUS_EXPR
- || code == MIN_EXPR
- || code == MAX_EXPR)
+ if (code == PLUS_EXPR)
{
/* If we have a PLUS_EXPR with two VR_ANTI_RANGEs, drop to
VR_VARYING. It would take more effort to compute a precise
op0 + op1 == 0, so we cannot claim that the sum is in ~[0,0].
Note that we are guaranteed to have vr0.type == vr1.type at
this point. */
- if (code == PLUS_EXPR && vr0.type == VR_ANTI_RANGE)
+ if (vr0.type == VR_ANTI_RANGE)
{
set_value_range_to_varying (vr);
return;
This happens regularly with subtracting something in unsigned
arithmetic.
??? See PR30318 for all the cases we do not handle. */
- if (code == PLUS_EXPR
- && (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
+ if ((TREE_OVERFLOW (min) && !is_overflow_infinity (min))
&& (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
{
min = build_int_cst_wide (TREE_TYPE (min),
TREE_INT_CST_HIGH (max));
}
}
- else if (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)
+ else if (code == MIN_EXPR
+ || code == MAX_EXPR)
+ {
+ if (vr0.type == VR_ANTI_RANGE)
+ {
+ /* For MIN_EXPR and MAX_EXPR with two VR_ANTI_RANGEs,
+ the resulting VR_ANTI_RANGE is the same - intersection
+ of the two ranges. */
+ min = vrp_int_const_binop (MAX_EXPR, vr0.min, vr1.min);
+ max = vrp_int_const_binop (MIN_EXPR, vr0.max, vr1.max);
+ }
+ else
+ {
+ /* For operations that make the resulting range directly
+ proportional to the original ranges, apply the operation to
+ the same end of each range. */
+ min = vrp_int_const_binop (code, vr0.min, vr1.min);
+ max = vrp_int_const_binop (code, vr0.max, vr1.max);
+ }
+ }
+ else if (code == MULT_EXPR)
{
- tree val[4];
- size_t i;
- bool sop;
-
/* If we have an unsigned MULT_EXPR with two VR_ANTI_RANGEs,
drop to VR_VARYING. It would take more effort to compute a
precise range for such a case. For example, if we have
we cannot claim that the product is in ~[0,0]. Note that we
are guaranteed to have vr0.type == vr1.type at this
point. */
- if (code == MULT_EXPR
- && vr0.type == VR_ANTI_RANGE
- && !TYPE_OVERFLOW_UNDEFINED (TREE_TYPE (op0)))
+ if (vr0.type == VR_ANTI_RANGE
+ && !TYPE_OVERFLOW_UNDEFINED (expr_type))
{
set_value_range_to_varying (vr);
return;
}
+ extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
+ return;
+ }
+ else if (code == RSHIFT_EXPR)
+ {
/* 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;
- }
+ if (vr1.type != VR_RANGE
+ || !value_range_nonnegative_p (&vr1)
+ || TREE_CODE (vr1.max) != INTEGER_CST
+ || compare_tree_int (vr1.max, TYPE_PRECISION (expr_type) - 1) == 1)
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
+ extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
+ return;
+ }
+ else if (code == LSHIFT_EXPR)
+ {
+ /* If we have a LSHIFT_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 (vr1.type != VR_RANGE
+ || !value_range_nonnegative_p (&vr1)
+ || TREE_CODE (vr1.max) != INTEGER_CST
+ || compare_tree_int (vr1.max, TYPE_PRECISION (expr_type) - 1) == 1)
+ {
+ set_value_range_to_varying (vr);
+ return;
}
- else if ((code == TRUNC_DIV_EXPR
- || code == FLOOR_DIV_EXPR
- || code == CEIL_DIV_EXPR
- || code == EXACT_DIV_EXPR
- || code == ROUND_DIV_EXPR)
- && (vr0.type != VR_RANGE || symbolic_range_p (&vr0)))
+ /* We can map shifts by constants to MULT_EXPR handling. */
+ if (range_int_cst_singleton_p (&vr1))
+ {
+ value_range_t vr1p = VR_INITIALIZER;
+ vr1p.type = VR_RANGE;
+ vr1p.min
+ = double_int_to_tree (expr_type,
+ double_int_lshift (double_int_one,
+ TREE_INT_CST_LOW (vr1.min),
+ TYPE_PRECISION (expr_type),
+ false));
+ vr1p.max = vr1p.min;
+ extract_range_from_multiplicative_op_1 (vr, MULT_EXPR, &vr0, &vr1p);
+ return;
+ }
+
+ set_value_range_to_varying (vr);
+ return;
+ }
+ else if (code == TRUNC_DIV_EXPR
+ || code == FLOOR_DIV_EXPR
+ || code == CEIL_DIV_EXPR
+ || code == EXACT_DIV_EXPR
+ || code == ROUND_DIV_EXPR)
+ {
+ if (vr0.type != VR_RANGE || symbolic_range_p (&vr0))
{
/* For division, if op1 has VR_RANGE but op0 does not, something
can be deduced just from that range. Say [min, max] / [4, max]
&& !range_includes_zero_p (&vr1))
{
vr0.type = type = VR_RANGE;
- vr0.min = vrp_val_min (TREE_TYPE (op0));
- vr0.max = vrp_val_max (TREE_TYPE (op1));
+ vr0.min = vrp_val_min (expr_type);
+ vr0.max = vrp_val_max (expr_type);
}
else
{
}
}
+ /* For divisions, if flag_non_call_exceptions is true, we must
+ not eliminate a division by zero. */
+ if (cfun->can_throw_non_call_exceptions
+ && (vr1.type != VR_RANGE
+ || symbolic_range_p (&vr1)
+ || range_includes_zero_p (&vr1)))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
/* For divisions, if op0 is VR_RANGE, we can deduce a range
even if op1 is VR_VARYING, VR_ANTI_RANGE, symbolic or can
include 0. */
- if ((code == TRUNC_DIV_EXPR
- || code == FLOOR_DIV_EXPR
- || code == CEIL_DIV_EXPR
- || code == EXACT_DIV_EXPR
- || code == ROUND_DIV_EXPR)
- && vr0.type == VR_RANGE
+ if (vr0.type == VR_RANGE
&& (vr1.type != VR_RANGE
|| symbolic_range_p (&vr1)
|| range_includes_zero_p (&vr1)))
tree zero = build_int_cst (TREE_TYPE (vr0.min), 0);
int cmp;
- sop = false;
min = NULL_TREE;
max = NULL_TREE;
- if (vrp_expr_computes_nonnegative (op1, &sop) && !sop)
+ if (TYPE_UNSIGNED (expr_type)
+ || value_range_nonnegative_p (&vr1))
{
/* For unsigned division or when divisor is known
to be non-negative, the range has to cover
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
- maximum values for the new range. One approach is to figure
- out all the variations of range combinations and do the
- operations.
-
- However, this involves several calls to compare_values and it
- is pretty convoluted. It's simpler to do the 4 operations
- (MIN0 OP MIN1, MIN0 OP MAX1, MAX0 OP MIN1 and MAX0 OP MAX0 OP
- MAX1) and then figure the smallest and largest values to form
- the new range. */
else
{
- gcc_assert ((vr0.type == VR_RANGE
- || (code == MULT_EXPR && vr0.type == VR_ANTI_RANGE))
- && vr0.type == vr1.type);
-
- /* Compute the 4 cross operations. */
- sop = false;
- val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
- if (val[0] == NULL_TREE)
- sop = true;
-
- if (vr1.max == vr1.min)
- val[1] = NULL_TREE;
- else
- {
- val[1] = vrp_int_const_binop (code, vr0.min, vr1.max);
- if (val[1] == NULL_TREE)
- sop = true;
- }
-
- if (vr0.max == vr0.min)
- val[2] = NULL_TREE;
- else
- {
- val[2] = vrp_int_const_binop (code, vr0.max, vr1.min);
- if (val[2] == NULL_TREE)
- sop = true;
- }
-
- if (vr0.min == vr0.max || vr1.min == vr1.max)
- val[3] = NULL_TREE;
- else
- {
- val[3] = vrp_int_const_binop (code, vr0.max, vr1.max);
- if (val[3] == NULL_TREE)
- sop = true;
- }
-
- if (sop)
- {
- set_value_range_to_varying (vr);
- return;
- }
-
- /* Set MIN to the minimum of VAL[i] and MAX to the maximum
- of VAL[i]. */
- min = val[0];
- max = val[0];
- for (i = 1; i < 4; i++)
- {
- if (!is_gimple_min_invariant (min)
- || (TREE_OVERFLOW (min) && !is_overflow_infinity (min))
- || !is_gimple_min_invariant (max)
- || (TREE_OVERFLOW (max) && !is_overflow_infinity (max)))
- break;
-
- if (val[i])
- {
- if (!is_gimple_min_invariant (val[i])
- || (TREE_OVERFLOW (val[i])
- && !is_overflow_infinity (val[i])))
- {
- /* If we found an overflowed value, set MIN and MAX
- to it so that we set the resulting range to
- VARYING. */
- min = max = val[i];
- break;
- }
-
- if (compare_values (val[i], min) == -1)
- min = val[i];
-
- if (compare_values (val[i], max) == 1)
- max = val[i];
- }
- }
+ extract_range_from_multiplicative_op_1 (vr, code, &vr0, &vr1);
+ return;
}
}
+ else if (code == TRUNC_MOD_EXPR)
+ {
+ if (vr1.type != VR_RANGE
+ || symbolic_range_p (&vr1)
+ || range_includes_zero_p (&vr1)
+ || vrp_val_is_min (vr1.min))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+ type = VR_RANGE;
+ /* Compute MAX <|vr1.min|, |vr1.max|> - 1. */
+ max = fold_unary_to_constant (ABS_EXPR, expr_type, vr1.min);
+ if (tree_int_cst_lt (max, vr1.max))
+ max = vr1.max;
+ max = int_const_binop (MINUS_EXPR, max, integer_one_node);
+ /* If the dividend is non-negative the modulus will be
+ non-negative as well. */
+ if (TYPE_UNSIGNED (expr_type)
+ || value_range_nonnegative_p (&vr0))
+ min = build_int_cst (TREE_TYPE (max), 0);
+ else
+ min = fold_unary_to_constant (NEGATE_EXPR, expr_type, max);
+ }
else if (code == MINUS_EXPR)
{
/* If we have a MINUS_EXPR with two VR_ANTI_RANGEs, drop to
min = vrp_int_const_binop (code, vr0.min, vr1.max);
max = vrp_int_const_binop (code, vr0.max, vr1.min);
}
- else if (code == BIT_AND_EXPR)
- {
- if (vr0.type == VR_RANGE
- && vr0.min == vr0.max
- && TREE_CODE (vr0.max) == INTEGER_CST
- && !TREE_OVERFLOW (vr0.max)
- && tree_int_cst_sgn (vr0.max) >= 0)
- {
- min = build_int_cst (expr_type, 0);
- max = vr0.max;
- }
- else if (vr1.type == VR_RANGE
- && vr1.min == vr1.max
- && TREE_CODE (vr1.max) == INTEGER_CST
- && !TREE_OVERFLOW (vr1.max)
- && tree_int_cst_sgn (vr1.max) >= 0)
- {
- type = VR_RANGE;
- min = build_int_cst (expr_type, 0);
- max = vr1.max;
- }
- else
- {
- set_value_range_to_varying (vr);
- 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)
+ else if (code == BIT_AND_EXPR || code == BIT_IOR_EXPR || code == BIT_XOR_EXPR)
+ {
+ bool int_cst_range0, int_cst_range1;
+ double_int may_be_nonzero0, may_be_nonzero1;
+ double_int must_be_nonzero0, must_be_nonzero1;
+
+ int_cst_range0 = zero_nonzero_bits_from_vr (&vr0, &may_be_nonzero0,
+ &must_be_nonzero0);
+ int_cst_range1 = zero_nonzero_bits_from_vr (&vr1, &may_be_nonzero1,
+ &must_be_nonzero1);
+
+ type = VR_RANGE;
+ if (code == BIT_AND_EXPR)
+ {
+ double_int dmax;
+ min = double_int_to_tree (expr_type,
+ double_int_and (must_be_nonzero0,
+ must_be_nonzero1));
+ dmax = double_int_and (may_be_nonzero0, may_be_nonzero1);
+ /* If both input ranges contain only negative values we can
+ truncate the result range maximum to the minimum of the
+ input range maxima. */
+ if (int_cst_range0 && int_cst_range1
+ && tree_int_cst_sgn (vr0.max) < 0
+ && tree_int_cst_sgn (vr1.max) < 0)
{
- ior_max.low = ~(unsigned HOST_WIDE_INT)0u;
- ior_max.high |= ((HOST_WIDE_INT) 1
- << floor_log2 (ior_max.high)) - 1;
+ dmax = double_int_min (dmax, tree_to_double_int (vr0.max),
+ TYPE_UNSIGNED (expr_type));
+ dmax = double_int_min (dmax, tree_to_double_int (vr1.max),
+ TYPE_UNSIGNED (expr_type));
}
- else if (ior_max.low != 0)
- 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;
+ /* If either input range contains only non-negative values
+ we can truncate the result range maximum to the respective
+ maximum of the input range. */
+ if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0)
+ dmax = double_int_min (dmax, tree_to_double_int (vr0.max),
+ TYPE_UNSIGNED (expr_type));
+ if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0)
+ dmax = double_int_min (dmax, tree_to_double_int (vr1.max),
+ TYPE_UNSIGNED (expr_type));
+ max = double_int_to_tree (expr_type, dmax);
+ }
+ else if (code == BIT_IOR_EXPR)
+ {
+ double_int dmin;
+ max = double_int_to_tree (expr_type,
+ double_int_ior (may_be_nonzero0,
+ may_be_nonzero1));
+ dmin = double_int_ior (must_be_nonzero0, must_be_nonzero1);
+ /* If the input ranges contain only positive values we can
+ truncate the minimum of the result range to the maximum
+ of the input range minima. */
+ if (int_cst_range0 && int_cst_range1
+ && tree_int_cst_sgn (vr0.min) >= 0
+ && tree_int_cst_sgn (vr1.min) >= 0)
+ {
+ dmin = double_int_max (dmin, tree_to_double_int (vr0.min),
+ TYPE_UNSIGNED (expr_type));
+ dmin = double_int_max (dmin, tree_to_double_int (vr1.min),
+ TYPE_UNSIGNED (expr_type));
+ }
+ /* If either input range contains only negative values
+ we can truncate the minimum of the result range to the
+ respective minimum range. */
+ if (int_cst_range0 && tree_int_cst_sgn (vr0.max) < 0)
+ dmin = double_int_max (dmin, tree_to_double_int (vr0.min),
+ TYPE_UNSIGNED (expr_type));
+ if (int_cst_range1 && tree_int_cst_sgn (vr1.max) < 0)
+ dmin = double_int_max (dmin, tree_to_double_int (vr1.min),
+ TYPE_UNSIGNED (expr_type));
+ min = double_int_to_tree (expr_type, dmin);
+ }
+ else if (code == BIT_XOR_EXPR)
+ {
+ double_int result_zero_bits, result_one_bits;
+ result_zero_bits
+ = double_int_ior (double_int_and (must_be_nonzero0,
+ must_be_nonzero1),
+ double_int_not
+ (double_int_ior (may_be_nonzero0,
+ may_be_nonzero1)));
+ result_one_bits
+ = double_int_ior (double_int_and
+ (must_be_nonzero0,
+ double_int_not (may_be_nonzero1)),
+ double_int_and
+ (must_be_nonzero1,
+ double_int_not (may_be_nonzero0)));
+ max = double_int_to_tree (expr_type,
+ double_int_not (result_zero_bits));
+ min = double_int_to_tree (expr_type, result_one_bits);
+ /* If the range has all positive or all negative values the
+ result is better than VARYING. */
+ if (tree_int_cst_sgn (min) < 0
+ || tree_int_cst_sgn (max) >= 0)
+ ;
+ else
+ max = min = NULL_TREE;
}
}
else
set_value_range (vr, type, min, max, NULL);
}
-
-/* Extract range information from a unary expression EXPR based on
- the range of its operand and the expression code. */
+/* Extract range information from a binary expression OP0 CODE OP1 based on
+ the ranges of each of its operands with resulting type EXPR_TYPE.
+ The resulting range is stored in *VR. */
static void
-extract_range_from_unary_expr (value_range_t *vr, enum tree_code code,
- tree type, tree op0)
+extract_range_from_binary_expr (value_range_t *vr,
+ enum tree_code code,
+ tree expr_type, tree op0, tree op1)
{
- tree min, max;
- int cmp;
- value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
-
- /* Refuse to operate on certain unary expressions for which we
- cannot easily determine a resulting range. */
- if (code == FIX_TRUNC_EXPR
- || code == FLOAT_EXPR
- || code == BIT_NOT_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;
- }
+ value_range_t vr0 = VR_INITIALIZER;
+ value_range_t vr1 = VR_INITIALIZER;
- /* Get value ranges for the operand. For constant operands, create
+ /* Get value ranges for each operand. For constant operands, create
a new value range with the operand to simplify processing. */
if (TREE_CODE (op0) == SSA_NAME)
vr0 = *(get_value_range (op0));
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_to_value (&vr1, op1, NULL);
+ else
+ set_value_range_to_varying (&vr1);
+
+ extract_range_from_binary_expr_1 (vr, code, expr_type, &vr0, &vr1);
+}
+
+/* Extract range information from a unary operation CODE based on
+ the range of its operand *VR0 with type OP0_TYPE with resulting type TYPE.
+ The The resulting range is stored in *VR. */
+
+static void
+extract_range_from_unary_expr_1 (value_range_t *vr,
+ enum tree_code code, tree type,
+ value_range_t *vr0_, tree op0_type)
+{
+ value_range_t vr0 = *vr0_, vrtem0 = VR_INITIALIZER, vrtem1 = VR_INITIALIZER;
+
+ /* VRP only operates on integral and pointer types. */
+ if (!(INTEGRAL_TYPE_P (op0_type)
+ || POINTER_TYPE_P (op0_type))
+ || !(INTEGRAL_TYPE_P (type)
+ || POINTER_TYPE_P (type)))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
/* If VR0 is UNDEFINED, so is the result. */
if (vr0.type == VR_UNDEFINED)
{
return;
}
- /* Refuse to operate on symbolic ranges, or if neither operand is
- a pointer or integral type. */
- if ((!INTEGRAL_TYPE_P (TREE_TYPE (op0))
- && !POINTER_TYPE_P (TREE_TYPE (op0)))
- || (vr0.type != VR_VARYING
- && symbolic_range_p (&vr0)))
+ /* Handle operations that we express in terms of others. */
+ if (code == PAREN_EXPR)
{
- set_value_range_to_varying (vr);
+ /* PAREN_EXPR is a simple copy. */
+ copy_value_range (vr, &vr0);
return;
}
-
- /* 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 (type) || POINTER_TYPE_P (TREE_TYPE (op0)))
+ else if (code == NEGATE_EXPR)
{
- bool sop;
-
- sop = false;
- if (range_is_nonnull (&vr0)
- || (tree_unary_nonzero_warnv_p (code, type, op0, &sop)
- && !sop))
- set_value_range_to_nonnull (vr, type);
- else if (range_is_null (&vr0))
- set_value_range_to_null (vr, type);
- else
- set_value_range_to_varying (vr);
+ /* -X is simply 0 - X, so re-use existing code that also handles
+ anti-ranges fine. */
+ value_range_t zero = VR_INITIALIZER;
+ set_value_range_to_value (&zero, build_int_cst (type, 0), NULL);
+ extract_range_from_binary_expr_1 (vr, MINUS_EXPR, type, &zero, &vr0);
+ return;
+ }
+ else if (code == BIT_NOT_EXPR)
+ {
+ /* ~X is simply -1 - X, so re-use existing code that also handles
+ anti-ranges fine. */
+ value_range_t minusone = VR_INITIALIZER;
+ set_value_range_to_value (&minusone, build_int_cst (type, -1), NULL);
+ extract_range_from_binary_expr_1 (vr, MINUS_EXPR,
+ type, &minusone, &vr0);
+ return;
+ }
+ /* Now canonicalize anti-ranges to ranges when they are not symbolic
+ and express op ~[] as (op []') U (op []''). */
+ if (vr0.type == VR_ANTI_RANGE
+ && ranges_from_anti_range (&vr0, &vrtem0, &vrtem1))
+ {
+ extract_range_from_unary_expr_1 (vr, code, type, &vrtem0, op0_type);
+ if (vrtem1.type != VR_UNDEFINED)
+ {
+ value_range_t vrres = VR_INITIALIZER;
+ extract_range_from_unary_expr_1 (&vrres, code, type,
+ &vrtem1, op0_type);
+ vrp_meet (vr, &vrres);
+ }
return;
}
- /* Handle unary expressions on integer ranges. */
- if (CONVERT_EXPR_CODE_P (code)
- && INTEGRAL_TYPE_P (type)
- && INTEGRAL_TYPE_P (TREE_TYPE (op0)))
+ if (CONVERT_EXPR_CODE_P (code))
{
- tree inner_type = TREE_TYPE (op0);
+ tree inner_type = op0_type;
tree outer_type = type;
+ /* If the expression evaluates to a pointer, we are only interested in
+ determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
+ if (POINTER_TYPE_P (type))
+ {
+ if (range_is_nonnull (&vr0))
+ set_value_range_to_nonnull (vr, type);
+ else if (range_is_null (&vr0))
+ set_value_range_to_null (vr, type);
+ else
+ set_value_range_to_varying (vr);
+ return;
+ }
+
/* If VR0 is varying and we increase the type precision, assume
a full range for the following transformation. */
if (vr0.type == VR_VARYING
+ && INTEGRAL_TYPE_P (inner_type)
&& TYPE_PRECISION (inner_type) < TYPE_PRECISION (outer_type))
{
vr0.type = VR_RANGE;
|| vr0.type == VR_ANTI_RANGE)
&& TREE_CODE (vr0.min) == INTEGER_CST
&& TREE_CODE (vr0.max) == INTEGER_CST
- && !is_overflow_infinity (vr0.min)
- && !is_overflow_infinity (vr0.max)
+ && (!is_overflow_infinity (vr0.min)
+ || (vr0.type == VR_RANGE
+ && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)
+ && needs_overflow_infinity (outer_type)
+ && supports_overflow_infinity (outer_type)))
+ && (!is_overflow_infinity (vr0.max)
+ || (vr0.type == VR_RANGE
+ && TYPE_PRECISION (outer_type) > TYPE_PRECISION (inner_type)
+ && needs_overflow_infinity (outer_type)
+ && supports_overflow_infinity (outer_type)))
&& (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)))))
+ int_const_binop (MINUS_EXPR, vr0.max, vr0.min),
+ size_int (TYPE_PRECISION (outer_type)))))))
{
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);
+ if (is_overflow_infinity (vr0.min))
+ new_min = negative_overflow_infinity (outer_type);
+ else
+ new_min = force_fit_type_double (outer_type,
+ tree_to_double_int (vr0.min),
+ 0, false);
+ if (is_overflow_infinity (vr0.max))
+ new_max = positive_overflow_infinity (outer_type);
+ else
+ new_max = force_fit_type_double (outer_type,
+ tree_to_double_int (vr0.max),
+ 0, false);
set_and_canonicalize_value_range (vr, vr0.type,
new_min, new_max, NULL);
return;
set_value_range_to_varying (vr);
return;
}
-
- /* Conversion of a VR_VARYING value to a wider type can result
- in a usable range. So wait until after we've handled conversions
- before dropping the result to VR_VARYING if we had a source
- operand that is VR_VARYING. */
- if (vr0.type == VR_VARYING)
+ else if (code == ABS_EXPR)
{
- set_value_range_to_varying (vr);
- return;
- }
+ tree min, max;
+ int cmp;
- /* Apply the operation to each end of the range and see what we end
- up with. */
- if (code == NEGATE_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 (type);
- else if (is_negative_overflow_infinity (vr0.max))
- 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))
+ /* Pass through vr0 in the easy cases. */
+ if (TYPE_UNSIGNED (type)
+ || value_range_nonnegative_p (&vr0))
{
- 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);
- return;
- }
+ copy_value_range (vr, &vr0);
+ return;
}
- else
- min = TYPE_MIN_VALUE (type);
- if (is_positive_overflow_infinity (vr0.min))
- max = negative_overflow_infinity (type);
- else if (is_negative_overflow_infinity (vr0.min))
- 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 (type))
- max = positive_overflow_infinity (type);
- else
- {
- set_value_range_to_varying (vr);
- return;
- }
- }
- else
- max = TYPE_MIN_VALUE (type);
- }
- else if (code == NEGATE_EXPR
- && TYPE_UNSIGNED (type))
- {
- if (!range_includes_zero_p (&vr0))
- {
- max = fold_unary_to_constant (code, type, vr0.min);
- min = fold_unary_to_constant (code, type, vr0.max);
- }
- else
+ /* For the remaining varying or symbolic ranges we can't do anything
+ useful. */
+ if (vr0.type == VR_VARYING
+ || symbolic_range_p (&vr0))
{
- if (range_is_null (&vr0))
- set_value_range_to_null (vr, type);
- else
- set_value_range_to_varying (vr);
+ set_value_range_to_varying (vr);
return;
}
- }
- else if (code == ABS_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 (type)
&& ((vr0.type == VR_RANGE
&& vrp_val_is_min (vr0.min))
|| (vr0.type == VR_ANTI_RANGE
- && !vrp_val_is_min (vr0.min)
- && !range_includes_zero_p (&vr0))))
+ && !vrp_val_is_min (vr0.min))))
{
set_value_range_to_varying (vr);
return;
min = (vr0.min != type_min_value
? int_const_binop (PLUS_EXPR, type_min_value,
- integer_one_node, 0)
+ integer_one_node)
: type_min_value);
}
else
max = t;
}
}
- }
- else
- {
- /* Otherwise, operate on each end of the range. */
- min = fold_unary_to_constant (code, type, vr0.min);
- max = fold_unary_to_constant (code, type, vr0.max);
- if (needs_overflow_infinity (type))
+ cmp = compare_values (min, max);
+ if (cmp == -2 || cmp == 1)
{
- gcc_assert (code != NEGATE_EXPR && code != ABS_EXPR);
+ /* If the new range has its limits swapped around (MIN > MAX),
+ then the operation caused one of them to wrap around, mark
+ the new range VARYING. */
+ set_value_range_to_varying (vr);
+ }
+ else
+ set_value_range (vr, vr0.type, min, max, NULL);
+ return;
+ }
- /* 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;
- }
+ /* For unhandled operations fall back to varying. */
+ 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 (type))
- min = (tree_int_cst_sgn (min) >= 0
- ? positive_overflow_infinity (TREE_TYPE (min))
- : negative_overflow_infinity (TREE_TYPE (min)));
- else
- {
- set_value_range_to_varying (vr);
- return;
- }
- }
- if (is_overflow_infinity (vr0.max))
- max = vr0.max;
- else if (TREE_OVERFLOW (max))
- {
- if (supports_overflow_infinity (type))
- max = (tree_int_cst_sgn (max) >= 0
- ? positive_overflow_infinity (TREE_TYPE (max))
- : negative_overflow_infinity (TREE_TYPE (max)));
- else
- {
- set_value_range_to_varying (vr);
- return;
- }
- }
- }
- }
+/* Extract range information from a unary expression CODE OP0 based on
+ the range of its operand with resulting type TYPE.
+ The resulting range is stored in *VR. */
- cmp = compare_values (min, max);
- if (cmp == -2 || cmp == 1)
- {
- /* If the new range has its limits swapped around (MIN > MAX),
- then the operation caused one of them to wrap around, mark
- the new range VARYING. */
- set_value_range_to_varying (vr);
- }
+static void
+extract_range_from_unary_expr (value_range_t *vr, enum tree_code code,
+ tree type, tree op0)
+{
+ value_range_t vr0 = VR_INITIALIZER;
+
+ /* Get value ranges for the operand. For constant operands, create
+ a new value range with the operand to simplify processing. */
+ if (TREE_CODE (op0) == SSA_NAME)
+ vr0 = *(get_value_range (op0));
+ else if (is_gimple_min_invariant (op0))
+ set_value_range_to_value (&vr0, op0, NULL);
else
- set_value_range (vr, vr0.type, min, max, NULL);
+ set_value_range_to_varying (&vr0);
+
+ extract_range_from_unary_expr_1 (vr, code, type, &vr0, TREE_TYPE (op0));
}
-/* Extract range information from a conditional expression EXPR based on
+/* Extract range information from a conditional expression STMT based on
the ranges of each of its operands and the expression code. */
static void
-extract_range_from_cond_expr (value_range_t *vr, tree expr)
+extract_range_from_cond_expr (value_range_t *vr, gimple stmt)
{
tree op0, op1;
- value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
- value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+ value_range_t vr0 = VR_INITIALIZER;
+ value_range_t vr1 = VR_INITIALIZER;
/* Get value ranges for each operand. For constant operands, create
a new value range with the operand to simplify processing. */
- op0 = COND_EXPR_THEN (expr);
+ op0 = gimple_assign_rhs2 (stmt);
if (TREE_CODE (op0) == SSA_NAME)
vr0 = *(get_value_range (op0));
else if (is_gimple_min_invariant (op0))
else
set_value_range_to_varying (&vr0);
- op1 = COND_EXPR_ELSE (expr);
+ op1 = gimple_assign_rhs3 (stmt);
if (TREE_CODE (op1) == SSA_NAME)
vr1 = *(get_value_range (op1));
else if (is_gimple_min_invariant (op1))
set_value_range_to_varying (&vr1);
/* The resulting value range is the union of the operand ranges */
- vrp_meet (&vr0, &vr1);
copy_value_range (vr, &vr0);
+ vrp_meet (vr, &vr1);
}
extract_range_from_assert (vr, gimple_assign_rhs1 (stmt));
else if (code == SSA_NAME)
extract_range_from_ssa_name (vr, gimple_assign_rhs1 (stmt));
- else if (TREE_CODE_CLASS (code) == tcc_binary
- || code == TRUTH_AND_EXPR
- || code == TRUTH_OR_EXPR
- || code == TRUTH_XOR_EXPR)
+ else if (TREE_CODE_CLASS (code) == tcc_binary)
extract_range_from_binary_expr (vr, gimple_assign_rhs_code (stmt),
gimple_expr_type (stmt),
gimple_assign_rhs1 (stmt),
gimple_expr_type (stmt),
gimple_assign_rhs1 (stmt));
else if (code == COND_EXPR)
- extract_range_from_cond_expr (vr, gimple_assign_rhs1 (stmt));
+ extract_range_from_cond_expr (vr, stmt);
else if (TREE_CODE_CLASS (code) == tcc_comparison)
extract_range_from_comparison (vr, gimple_assign_rhs_code (stmt),
gimple_expr_type (stmt),
adjust_range_with_scev (value_range_t *vr, struct loop *loop,
gimple stmt, tree var)
{
- tree init, step, chrec, tmin, tmax, min, max, type;
+ tree init, step, chrec, tmin, tmax, min, max, type, tem;
enum ev_direction dir;
/* TODO. Don't adjust anti-ranges. An anti-range may provide
return;
init = initial_condition_in_loop_num (chrec, loop->num);
+ tem = op_with_constant_singleton_value_range (init);
+ if (tem)
+ init = tem;
step = evolution_part_in_loop_num (chrec, loop->num);
+ tem = op_with_constant_singleton_value_range (step);
+ if (tem)
+ step = tem;
/* If STEP is symbolic, we can't know whether INIT will be the
minimum or maximum value in the range. Also, unless INIT is
else
tmax = TYPE_MAX_VALUE (type);
+ /* Try to use estimated number of iterations for the loop to constrain the
+ final value in the evolution. */
+ if (TREE_CODE (step) == INTEGER_CST
+ && is_gimple_val (init)
+ && (TREE_CODE (init) != SSA_NAME
+ || get_value_range (init)->type == VR_RANGE))
+ {
+ double_int nit;
+
+ /* We are only entering here for loop header PHI nodes, so using
+ the number of latch executions is the correct thing to use. */
+ if (max_loop_iterations (loop, &nit))
+ {
+ value_range_t maxvr = VR_INITIALIZER;
+ double_int dtmp;
+ bool unsigned_p = TYPE_UNSIGNED (TREE_TYPE (step));
+ int overflow = 0;
+
+ dtmp = double_int_mul_with_sign (tree_to_double_int (step), nit,
+ unsigned_p, &overflow);
+ /* If the multiplication overflowed we can't do a meaningful
+ adjustment. Likewise if the result doesn't fit in the type
+ of the induction variable. For a signed type we have to
+ check whether the result has the expected signedness which
+ is that of the step as number of iterations is unsigned. */
+ if (!overflow
+ && double_int_fits_to_tree_p (TREE_TYPE (init), dtmp)
+ && (unsigned_p
+ || ((dtmp.high ^ TREE_INT_CST_HIGH (step)) >= 0)))
+ {
+ tem = double_int_to_tree (TREE_TYPE (init), dtmp);
+ extract_range_from_binary_expr (&maxvr, PLUS_EXPR,
+ TREE_TYPE (init), init, tem);
+ /* Likewise if the addition did. */
+ if (maxvr.type == VR_RANGE)
+ {
+ tmin = maxvr.min;
+ tmax = maxvr.max;
+ }
+ }
+ }
+ }
+
if (vr->type == VR_VARYING || vr->type == VR_UNDEFINED)
{
min = tmin;
/* INIT is the maximum value. If INIT is lower than VR->MAX
but no smaller than VR->MIN, set VR->MAX to INIT. */
if (compare_values (init, max) == -1)
- {
- max = init;
-
- /* If we just created an invalid range with the minimum
- greater than the maximum, we fail conservatively.
- This should happen only in unreachable
- parts of code, or for invalid programs. */
- if (compare_values (min, max) == 1)
- return;
- }
+ max = init;
/* 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))
+ if (is_negative_overflow_infinity (min)
+ || compare_values (min, tmin) == -1)
min = tmin;
+
}
else
{
/* If INIT is bigger than VR->MIN, set VR->MIN to INIT. */
if (compare_values (init, min) == 1)
- {
- min = init;
-
- /* Again, avoid creating invalid range by failing. */
- if (compare_values (min, max) == 1)
- return;
- }
+ min = init;
- if (is_positive_overflow_infinity (max))
+ if (is_positive_overflow_infinity (max)
+ || compare_values (tmax, max) == -1)
max = tmax;
}
+ /* If we just created an invalid range with the minimum
+ greater than the maximum, we fail conservatively.
+ This should happen only in unreachable
+ parts of code, or for invalid programs. */
+ if (compare_values (min, max) == 1)
+ return;
+
set_value_range (vr, VR_RANGE, min, max, vr->equiv);
}
}
/* Dump value range VR to stderr. */
-void
+DEBUG_FUNCTION void
debug_value_range (value_range_t *vr)
{
dump_value_range (stderr, vr);
{
size_t i;
- for (i = 0; i < num_ssa_names; i++)
+ for (i = 0; i < num_vr_values; i++)
{
if (vr_value[i])
{
/* Dump all value ranges to stderr. */
-void
+DEBUG_FUNCTION void
debug_all_value_ranges (void)
{
dump_all_value_ranges (stderr);
tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
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 = gimple_build_assign (n, boolean_false_node);
- }
else if (TREE_CODE (cond) == SSA_NAME)
{
/* Given V, build the assignment N = true. */
/* Dump all the registered assertions for NAME to stderr. */
-void
+DEBUG_FUNCTION void
debug_asserts_for (tree name)
{
dump_asserts_for (stderr, name);
/* Dump all the registered assertions for all the names to stderr. */
-void
+DEBUG_FUNCTION void
debug_all_asserts (void)
{
dump_all_asserts (stderr);
assert_locus_t n, loc, last_loc;
basic_block dest_bb;
-#if defined ENABLE_CHECKING
- gcc_assert (bb == NULL || e == NULL);
+ gcc_checking_assert (bb == NULL || e == NULL);
if (e == NULL)
- gcc_assert (gimple_code (gsi_stmt (si)) != GIMPLE_COND
- && gimple_code (gsi_stmt (si)) != GIMPLE_SWITCH);
-#endif
+ gcc_checking_assert (gimple_code (gsi_stmt (si)) != GIMPLE_COND
+ && gimple_code (gsi_stmt (si)) != GIMPLE_SWITCH);
/* Never build an assert comparing against an integer constant with
TREE_OVERFLOW set. This confuses our undefined overflow warning
return true;
}
+/* Find out smallest RES where RES > VAL && (RES & MASK) == RES, if any
+ (otherwise return VAL). VAL and MASK must be zero-extended for
+ precision PREC. If SGNBIT is non-zero, first xor VAL with SGNBIT
+ (to transform signed values into unsigned) and at the end xor
+ SGNBIT back. */
+
+static double_int
+masked_increment (double_int val, double_int mask, double_int sgnbit,
+ unsigned int prec)
+{
+ double_int bit = double_int_one, res;
+ unsigned int i;
+
+ val = double_int_xor (val, sgnbit);
+ for (i = 0; i < prec; i++, bit = double_int_add (bit, bit))
+ {
+ res = mask;
+ if (double_int_zero_p (double_int_and (res, bit)))
+ continue;
+ res = double_int_sub (bit, double_int_one);
+ res = double_int_and_not (double_int_add (val, bit), res);
+ res = double_int_and (res, mask);
+ if (double_int_ucmp (res, val) > 0)
+ return double_int_xor (res, sgnbit);
+ }
+ return double_int_xor (val, sgnbit);
+}
+
/* 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.
}
}
+ if (TREE_CODE_CLASS (comp_code) == tcc_comparison
+ && TREE_CODE (val) == INTEGER_CST)
+ {
+ gimple def_stmt = SSA_NAME_DEF_STMT (name);
+ tree name2 = NULL_TREE, names[2], cst2 = NULL_TREE;
+ tree val2 = NULL_TREE;
+ double_int mask = double_int_zero;
+ unsigned int prec = TYPE_PRECISION (TREE_TYPE (val));
+
+ /* Add asserts for NAME cmp CST and NAME being defined
+ as NAME = (int) NAME2. */
+ if (!TYPE_UNSIGNED (TREE_TYPE (val))
+ && (comp_code == LE_EXPR || comp_code == LT_EXPR
+ || comp_code == GT_EXPR || comp_code == GE_EXPR)
+ && gimple_assign_cast_p (def_stmt))
+ {
+ name2 = gimple_assign_rhs1 (def_stmt);
+ if (CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt))
+ && INTEGRAL_TYPE_P (TREE_TYPE (name2))
+ && TYPE_UNSIGNED (TREE_TYPE (name2))
+ && prec == TYPE_PRECISION (TREE_TYPE (name2))
+ && (comp_code == LE_EXPR || comp_code == GT_EXPR
+ || !tree_int_cst_equal (val,
+ TYPE_MIN_VALUE (TREE_TYPE (val))))
+ && live_on_edge (e, name2)
+ && !has_single_use (name2))
+ {
+ tree tmp, cst;
+ enum tree_code new_comp_code = comp_code;
+
+ cst = fold_convert (TREE_TYPE (name2),
+ TYPE_MIN_VALUE (TREE_TYPE (val)));
+ /* Build an expression for the range test. */
+ tmp = build2 (PLUS_EXPR, TREE_TYPE (name2), name2, cst);
+ cst = fold_build2 (PLUS_EXPR, TREE_TYPE (name2), cst,
+ fold_convert (TREE_TYPE (name2), val));
+ if (comp_code == LT_EXPR || comp_code == GE_EXPR)
+ {
+ new_comp_code = comp_code == LT_EXPR ? LE_EXPR : GT_EXPR;
+ cst = fold_build2 (MINUS_EXPR, TREE_TYPE (name2), cst,
+ build_int_cst (TREE_TYPE (name2), 1));
+ }
+
+ 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, new_comp_code, cst, NULL,
+ e, bsi);
+
+ retval = true;
+ }
+ }
+
+ /* Add asserts for NAME cmp CST and NAME being defined as
+ NAME = NAME2 >> CST2.
+
+ Extract CST2 from the right shift. */
+ if (is_gimple_assign (def_stmt)
+ && gimple_assign_rhs_code (def_stmt) == RSHIFT_EXPR)
+ {
+ name2 = gimple_assign_rhs1 (def_stmt);
+ cst2 = gimple_assign_rhs2 (def_stmt);
+ if (TREE_CODE (name2) == SSA_NAME
+ && host_integerp (cst2, 1)
+ && INTEGRAL_TYPE_P (TREE_TYPE (name2))
+ && IN_RANGE (tree_low_cst (cst2, 1), 1, prec - 1)
+ && prec <= HOST_BITS_PER_DOUBLE_INT
+ && prec == GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (val)))
+ && live_on_edge (e, name2)
+ && !has_single_use (name2))
+ {
+ mask = double_int_mask (tree_low_cst (cst2, 1));
+ val2 = fold_binary (LSHIFT_EXPR, TREE_TYPE (val), val, cst2);
+ }
+ }
+ if (val2 != NULL_TREE
+ && TREE_CODE (val2) == INTEGER_CST
+ && simple_cst_equal (fold_build2 (RSHIFT_EXPR,
+ TREE_TYPE (val),
+ val2, cst2), val))
+ {
+ enum tree_code new_comp_code = comp_code;
+ tree tmp, new_val;
+
+ tmp = name2;
+ if (comp_code == EQ_EXPR || comp_code == NE_EXPR)
+ {
+ if (!TYPE_UNSIGNED (TREE_TYPE (val)))
+ {
+ tree type = build_nonstandard_integer_type (prec, 1);
+ tmp = build1 (NOP_EXPR, type, name2);
+ val2 = fold_convert (type, val2);
+ }
+ tmp = fold_build2 (MINUS_EXPR, TREE_TYPE (tmp), tmp, val2);
+ new_val = double_int_to_tree (TREE_TYPE (tmp), mask);
+ new_comp_code = comp_code == EQ_EXPR ? LE_EXPR : GT_EXPR;
+ }
+ else if (comp_code == LT_EXPR || comp_code == GE_EXPR)
+ new_val = val2;
+ else
+ {
+ double_int maxval
+ = double_int_max_value (prec, TYPE_UNSIGNED (TREE_TYPE (val)));
+ mask = double_int_ior (tree_to_double_int (val2), mask);
+ if (double_int_equal_p (mask, maxval))
+ new_val = NULL_TREE;
+ else
+ new_val = double_int_to_tree (TREE_TYPE (val2), mask);
+ }
+
+ if (new_val)
+ {
+ 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, new_comp_code, new_val,
+ NULL, e, bsi);
+ retval = true;
+ }
+ }
+
+ /* Add asserts for NAME cmp CST and NAME being defined as
+ NAME = NAME2 & CST2.
+
+ Extract CST2 from the and. */
+ names[0] = NULL_TREE;
+ names[1] = NULL_TREE;
+ cst2 = NULL_TREE;
+ if (is_gimple_assign (def_stmt)
+ && gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR)
+ {
+ name2 = gimple_assign_rhs1 (def_stmt);
+ cst2 = gimple_assign_rhs2 (def_stmt);
+ if (TREE_CODE (name2) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (name2))
+ && TREE_CODE (cst2) == INTEGER_CST
+ && !integer_zerop (cst2)
+ && prec <= HOST_BITS_PER_DOUBLE_INT
+ && (prec > 1
+ || TYPE_UNSIGNED (TREE_TYPE (val))))
+ {
+ gimple def_stmt2 = SSA_NAME_DEF_STMT (name2);
+ if (gimple_assign_cast_p (def_stmt2))
+ {
+ names[1] = gimple_assign_rhs1 (def_stmt2);
+ if (!CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt2))
+ || !INTEGRAL_TYPE_P (TREE_TYPE (names[1]))
+ || (TYPE_PRECISION (TREE_TYPE (name2))
+ != TYPE_PRECISION (TREE_TYPE (names[1])))
+ || !live_on_edge (e, names[1])
+ || has_single_use (names[1]))
+ names[1] = NULL_TREE;
+ }
+ if (live_on_edge (e, name2)
+ && !has_single_use (name2))
+ names[0] = name2;
+ }
+ }
+ if (names[0] || names[1])
+ {
+ double_int minv, maxv = double_int_zero, valv, cst2v;
+ double_int tem, sgnbit;
+ bool valid_p = false, valn = false, cst2n = false;
+ enum tree_code ccode = comp_code;
+
+ valv = double_int_zext (tree_to_double_int (val), prec);
+ cst2v = double_int_zext (tree_to_double_int (cst2), prec);
+ if (!TYPE_UNSIGNED (TREE_TYPE (val)))
+ {
+ valn = double_int_negative_p (double_int_sext (valv, prec));
+ cst2n = double_int_negative_p (double_int_sext (cst2v, prec));
+ }
+ /* If CST2 doesn't have most significant bit set,
+ but VAL is negative, we have comparison like
+ if ((x & 0x123) > -4) (always true). Just give up. */
+ if (!cst2n && valn)
+ ccode = ERROR_MARK;
+ if (cst2n)
+ sgnbit = double_int_zext (double_int_lshift (double_int_one,
+ prec - 1, prec,
+ false), prec);
+ else
+ sgnbit = double_int_zero;
+ minv = double_int_and (valv, cst2v);
+ switch (ccode)
+ {
+ case EQ_EXPR:
+ /* Minimum unsigned value for equality is VAL & CST2
+ (should be equal to VAL, otherwise we probably should
+ have folded the comparison into false) and
+ maximum unsigned value is VAL | ~CST2. */
+ maxv = double_int_ior (valv, double_int_not (cst2v));
+ maxv = double_int_zext (maxv, prec);
+ valid_p = true;
+ break;
+ case NE_EXPR:
+ tem = double_int_ior (valv, double_int_not (cst2v));
+ tem = double_int_zext (tem, prec);
+ /* If VAL is 0, handle (X & CST2) != 0 as (X & CST2) > 0U. */
+ if (double_int_zero_p (valv))
+ {
+ cst2n = false;
+ sgnbit = double_int_zero;
+ goto gt_expr;
+ }
+ /* If (VAL | ~CST2) is all ones, handle it as
+ (X & CST2) < VAL. */
+ if (double_int_equal_p (tem, double_int_mask (prec)))
+ {
+ cst2n = false;
+ valn = false;
+ sgnbit = double_int_zero;
+ goto lt_expr;
+ }
+ if (!cst2n
+ && double_int_negative_p (double_int_sext (cst2v, prec)))
+ sgnbit = double_int_zext (double_int_lshift (double_int_one,
+ prec - 1, prec,
+ false), prec);
+ if (!double_int_zero_p (sgnbit))
+ {
+ if (double_int_equal_p (valv, sgnbit))
+ {
+ cst2n = true;
+ valn = true;
+ goto gt_expr;
+ }
+ if (double_int_equal_p (tem, double_int_mask (prec - 1)))
+ {
+ cst2n = true;
+ goto lt_expr;
+ }
+ if (!cst2n)
+ sgnbit = double_int_zero;
+ }
+ break;
+ case GE_EXPR:
+ /* Minimum unsigned value for >= if (VAL & CST2) == VAL
+ is VAL and maximum unsigned value is ~0. For signed
+ comparison, if CST2 doesn't have most significant bit
+ set, handle it similarly. If CST2 has MSB set,
+ the minimum is the same, and maximum is ~0U/2. */
+ if (!double_int_equal_p (minv, valv))
+ {
+ /* If (VAL & CST2) != VAL, X & CST2 can't be equal to
+ VAL. */
+ minv = masked_increment (valv, cst2v, sgnbit, prec);
+ if (double_int_equal_p (minv, valv))
+ break;
+ }
+ maxv = double_int_mask (prec - (cst2n ? 1 : 0));
+ valid_p = true;
+ break;
+ case GT_EXPR:
+ gt_expr:
+ /* Find out smallest MINV where MINV > VAL
+ && (MINV & CST2) == MINV, if any. If VAL is signed and
+ CST2 has MSB set, compute it biased by 1 << (prec - 1). */
+ minv = masked_increment (valv, cst2v, sgnbit, prec);
+ if (double_int_equal_p (minv, valv))
+ break;
+ maxv = double_int_mask (prec - (cst2n ? 1 : 0));
+ valid_p = true;
+ break;
+ case LE_EXPR:
+ /* Minimum unsigned value for <= is 0 and maximum
+ unsigned value is VAL | ~CST2 if (VAL & CST2) == VAL.
+ Otherwise, find smallest VAL2 where VAL2 > VAL
+ && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
+ as maximum.
+ For signed comparison, if CST2 doesn't have most
+ significant bit set, handle it similarly. If CST2 has
+ MSB set, the maximum is the same and minimum is INT_MIN. */
+ if (double_int_equal_p (minv, valv))
+ maxv = valv;
+ else
+ {
+ maxv = masked_increment (valv, cst2v, sgnbit, prec);
+ if (double_int_equal_p (maxv, valv))
+ break;
+ maxv = double_int_sub (maxv, double_int_one);
+ }
+ maxv = double_int_ior (maxv, double_int_not (cst2v));
+ maxv = double_int_zext (maxv, prec);
+ minv = sgnbit;
+ valid_p = true;
+ break;
+ case LT_EXPR:
+ lt_expr:
+ /* Minimum unsigned value for < is 0 and maximum
+ unsigned value is (VAL-1) | ~CST2 if (VAL & CST2) == VAL.
+ Otherwise, find smallest VAL2 where VAL2 > VAL
+ && (VAL2 & CST2) == VAL2 and use (VAL2 - 1) | ~CST2
+ as maximum.
+ For signed comparison, if CST2 doesn't have most
+ significant bit set, handle it similarly. If CST2 has
+ MSB set, the maximum is the same and minimum is INT_MIN. */
+ if (double_int_equal_p (minv, valv))
+ {
+ if (double_int_equal_p (valv, sgnbit))
+ break;
+ maxv = valv;
+ }
+ else
+ {
+ maxv = masked_increment (valv, cst2v, sgnbit, prec);
+ if (double_int_equal_p (maxv, valv))
+ break;
+ }
+ maxv = double_int_sub (maxv, double_int_one);
+ maxv = double_int_ior (maxv, double_int_not (cst2v));
+ maxv = double_int_zext (maxv, prec);
+ minv = sgnbit;
+ valid_p = true;
+ break;
+ default:
+ break;
+ }
+ if (valid_p
+ && !double_int_equal_p (double_int_zext (double_int_sub (maxv,
+ minv),
+ prec),
+ double_int_mask (prec)))
+ {
+ tree tmp, new_val, type;
+ int i;
+
+ for (i = 0; i < 2; i++)
+ if (names[i])
+ {
+ double_int maxv2 = maxv;
+ tmp = names[i];
+ type = TREE_TYPE (names[i]);
+ if (!TYPE_UNSIGNED (type))
+ {
+ type = build_nonstandard_integer_type (prec, 1);
+ tmp = build1 (NOP_EXPR, type, names[i]);
+ }
+ if (!double_int_zero_p (minv))
+ {
+ tmp = build2 (PLUS_EXPR, type, tmp,
+ double_int_to_tree (type,
+ double_int_neg (minv)));
+ maxv2 = double_int_sub (maxv, minv);
+ }
+ new_val = double_int_to_tree (type, maxv2);
+
+ if (dump_file)
+ {
+ fprintf (dump_file, "Adding assert for ");
+ print_generic_expr (dump_file, names[i], 0);
+ fprintf (dump_file, " from ");
+ print_generic_expr (dump_file, tmp, 0);
+ fprintf (dump_file, "\n");
+ }
+
+ register_new_assert_for (names[i], tmp, LE_EXPR,
+ new_val, NULL, e, bsi);
+ retval = true;
+ }
+ }
+ }
+ }
+
return retval;
}
invert);
}
else if ((code == NE_EXPR
- && (gimple_assign_rhs_code (op_def) == TRUTH_AND_EXPR
- || gimple_assign_rhs_code (op_def) == BIT_AND_EXPR))
+ && gimple_assign_rhs_code (op_def) == BIT_AND_EXPR)
|| (code == EQ_EXPR
- && (gimple_assign_rhs_code (op_def) == TRUTH_OR_EXPR
- || gimple_assign_rhs_code (op_def) == BIT_IOR_EXPR)))
+ && gimple_assign_rhs_code (op_def) == BIT_IOR_EXPR))
{
/* Recurse on each operand. */
retval |= register_edge_assert_for_1 (gimple_assign_rhs1 (op_def),
retval |= register_edge_assert_for_1 (gimple_assign_rhs2 (op_def),
code, e, bsi);
}
- else if (gimple_assign_rhs_code (op_def) == TRUTH_NOT_EXPR)
+ else if (gimple_assign_rhs_code (op_def) == BIT_NOT_EXPR
+ && TYPE_PRECISION (TREE_TYPE (gimple_assign_lhs (op_def))) == 1)
{
/* Recurse, flipping CODE. */
code = invert_tree_comparison (code, false);
the value zero or one, then we may be able to assert values
for SSA_NAMEs which flow into COND. */
- /* In the case of NAME == 1 or NAME != 0, for TRUTH_AND_EXPR defining
- statement of NAME we can assert both operands of the TRUTH_AND_EXPR
+ /* In the case of NAME == 1 or NAME != 0, for BIT_AND_EXPR defining
+ statement of NAME we can assert both operands of the BIT_AND_EXPR
have nonzero value. */
if (((comp_code == EQ_EXPR && integer_onep (val))
|| (comp_code == NE_EXPR && integer_zerop (val))))
gimple def_stmt = SSA_NAME_DEF_STMT (name);
if (is_gimple_assign (def_stmt)
- && (gimple_assign_rhs_code (def_stmt) == TRUTH_AND_EXPR
- || gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR))
+ && gimple_assign_rhs_code (def_stmt) == BIT_AND_EXPR)
{
tree op0 = gimple_assign_rhs1 (def_stmt);
tree op1 = gimple_assign_rhs2 (def_stmt);
}
}
- /* In the case of NAME == 0 or NAME != 1, for TRUTH_OR_EXPR defining
- statement of NAME we can assert both operands of the TRUTH_OR_EXPR
+ /* In the case of NAME == 0 or NAME != 1, for BIT_IOR_EXPR defining
+ statement of NAME we can assert both operands of the BIT_IOR_EXPR
have zero value. */
if (((comp_code == EQ_EXPR && integer_zerop (val))
|| (comp_code == NE_EXPR && integer_onep (val))))
{
gimple def_stmt = SSA_NAME_DEF_STMT (name);
+ /* For BIT_IOR_EXPR only if NAME == 0 both operands have
+ necessarily zero value, or if type-precision is one. */
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))))
+ && (gimple_assign_rhs_code (def_stmt) == BIT_IOR_EXPR
+ && (TYPE_PRECISION (TREE_TYPE (name)) == 1
+ || comp_code == EQ_EXPR)))
{
tree op0 = gimple_assign_rhs1 (def_stmt);
tree op1 = gimple_assign_rhs2 (def_stmt);
return need_assert;
}
-/* Compare two case labels sorting first by the destination label uid
+struct case_info
+{
+ tree expr;
+ basic_block bb;
+};
+
+/* Compare two case labels sorting first by the destination bb index
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));
+ const struct case_info *ci1 = (const struct case_info *) p1;
+ const struct case_info *ci2 = (const struct case_info *) p2;
+ int idx1 = ci1->bb->index;
+ int idx2 = ci2->bb->index;
- if (uid1 < uid2)
+ if (idx1 < idx2)
return -1;
- else if (uid1 == uid2)
+ else if (idx1 == idx2)
{
/* Make sure the default label is first in a group. */
- if (!CASE_LOW (case1))
+ if (!CASE_LOW (ci1->expr))
return -1;
- else if (!CASE_LOW (case2))
+ else if (!CASE_LOW (ci2->expr))
return 1;
else
- return tree_int_cst_compare (CASE_LOW (case1), CASE_LOW (case2));
+ return tree_int_cst_compare (CASE_LOW (ci1->expr),
+ CASE_LOW (ci2->expr));
}
else
return 1;
gimple_stmt_iterator bsi;
tree op;
edge e;
- tree vec2;
- size_t n = gimple_switch_num_labels(last);
+ struct case_info *ci;
+ size_t n = gimple_switch_num_labels (last);
#if GCC_VERSION >= 4000
unsigned int idx;
#else
return false;
/* Build a vector of case labels sorted by destination label. */
- vec2 = make_tree_vec (n);
+ ci = XNEWVEC (struct case_info, 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);
+ {
+ ci[idx].expr = gimple_switch_label (last, idx);
+ ci[idx].bb = label_to_block (CASE_LABEL (ci[idx].expr));
+ }
+ qsort (ci, n, sizeof (struct case_info), compare_case_labels);
for (idx = 0; idx < n; ++idx)
{
tree min, max;
- tree cl = TREE_VEC_ELT (vec2, idx);
+ tree cl = ci[idx].expr;
+ basic_block cbb = ci[idx].bb;
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)))
+ if (idx + 1 < n && cbb == ci[idx + 1].bb)
{
/* Skip labels until the last of the group. */
do {
++idx;
- } while (idx < n
- && CASE_LABEL (cl) == CASE_LABEL (TREE_VEC_ELT (vec2, idx)));
+ } while (idx < n && cbb == ci[idx].bb);
--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));
+ if (CASE_HIGH (ci[idx].expr))
+ max = CASE_HIGH (ci[idx].expr);
else
- max = CASE_LOW (TREE_VEC_ELT (vec2, idx));
+ max = CASE_LOW (ci[idx].expr);
}
/* Nothing to do if the range includes the default label until we
continue;
/* Find the edge to register the assert expr on. */
- e = find_edge (bb, label_to_block (CASE_LABEL (cl)));
+ e = find_edge (bb, cbb);
/* Register the necessary assertions for the operand in the
SWITCH_EXPR. */
}
}
+ XDELETEVEC (ci);
return need_assert;
}
{
/* 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 (gimple_code (gsi_stmt (loc->si)) == GIMPLE_COND
- || gimple_code (gsi_stmt (loc->si)) == GIMPLE_SWITCH);
-#endif
+ gcc_checking_assert (gimple_code (gsi_stmt (loc->si)) == GIMPLE_COND
+ || (gimple_code (gsi_stmt (loc->si))
+ == GIMPLE_SWITCH));
gsi_insert_on_edge (loc->e, assert_stmt);
return true;
{
value_range_t* vr = NULL;
tree low_sub, up_sub;
- tree low_bound, up_bound = array_ref_up_bound (ref);
+ tree low_bound, up_bound, up_bound_p1;
+ tree base;
+
+ if (TREE_NO_WARNING (ref))
+ return;
low_sub = up_sub = TREE_OPERAND (ref, 1);
+ up_bound = array_ref_up_bound (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
- && TYPE_DOMAIN (TREE_TYPE (ref)) != NULL_TREE
- && TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (ref))) == NULL_TREE)
- /* Accesses after the end of arrays of size 0 (gcc
- extension) and 1 are likely intentional ("struct
- hack"). */
- || compare_tree_int (up_bound, 1) <= 0)
+ /* Can not check flexible arrays. */
+ if (!up_bound
+ || TREE_CODE (up_bound) != INTEGER_CST)
return;
+ /* Accesses to trailing arrays via pointers may access storage
+ beyond the types array bounds. */
+ base = get_base_address (ref);
+ if (base && TREE_CODE (base) == MEM_REF)
+ {
+ tree cref, next = NULL_TREE;
+
+ if (TREE_CODE (TREE_OPERAND (ref, 0)) != COMPONENT_REF)
+ return;
+
+ cref = TREE_OPERAND (ref, 0);
+ if (TREE_CODE (TREE_TYPE (TREE_OPERAND (cref, 0))) == RECORD_TYPE)
+ for (next = DECL_CHAIN (TREE_OPERAND (cref, 1));
+ next && TREE_CODE (next) != FIELD_DECL;
+ next = DECL_CHAIN (next))
+ ;
+
+ /* If this is the last field in a struct type or a field in a
+ union type do not warn. */
+ if (!next)
+ return;
+ }
+
low_bound = array_ref_low_bound (ref);
+ up_bound_p1 = int_const_binop (PLUS_EXPR, up_bound, integer_one_node);
if (TREE_CODE (low_sub) == SSA_NAME)
{
}
}
else if (TREE_CODE (up_sub) == INTEGER_CST
- && tree_int_cst_lt (up_bound, up_sub)
- && !tree_int_cst_equal (up_bound, up_sub)
- && (!ignore_off_by_one
- || !tree_int_cst_equal (int_const_binop (PLUS_EXPR,
- up_bound,
- integer_one_node,
- 0),
- up_sub)))
+ && (ignore_off_by_one
+ ? (tree_int_cst_lt (up_bound, up_sub)
+ && !tree_int_cst_equal (up_bound_p1, up_sub))
+ : (tree_int_cst_lt (up_bound, up_sub)
+ || tree_int_cst_equal (up_bound_p1, up_sub))))
{
warning_at (location, OPT_Warray_bounds,
"array subscript is above array bounds");
t = TREE_OPERAND (t, 0);
}
while (handled_component_p (t));
+
+ if (TREE_CODE (t) == MEM_REF
+ && TREE_CODE (TREE_OPERAND (t, 0)) == ADDR_EXPR
+ && !TREE_NO_WARNING (t))
+ {
+ tree tem = TREE_OPERAND (TREE_OPERAND (t, 0), 0);
+ tree low_bound, up_bound, el_sz;
+ double_int idx;
+ if (TREE_CODE (TREE_TYPE (tem)) != ARRAY_TYPE
+ || TREE_CODE (TREE_TYPE (TREE_TYPE (tem))) == ARRAY_TYPE
+ || !TYPE_DOMAIN (TREE_TYPE (tem)))
+ return;
+
+ low_bound = TYPE_MIN_VALUE (TYPE_DOMAIN (TREE_TYPE (tem)));
+ up_bound = TYPE_MAX_VALUE (TYPE_DOMAIN (TREE_TYPE (tem)));
+ el_sz = TYPE_SIZE_UNIT (TREE_TYPE (TREE_TYPE (tem)));
+ if (!low_bound
+ || TREE_CODE (low_bound) != INTEGER_CST
+ || !up_bound
+ || TREE_CODE (up_bound) != INTEGER_CST
+ || !el_sz
+ || TREE_CODE (el_sz) != INTEGER_CST)
+ return;
+
+ idx = mem_ref_offset (t);
+ idx = double_int_sdiv (idx, tree_to_double_int (el_sz), TRUNC_DIV_EXPR);
+ if (double_int_scmp (idx, double_int_zero) < 0)
+ {
+ warning_at (location, OPT_Warray_bounds,
+ "array subscript is below array bounds");
+ TREE_NO_WARNING (t) = 1;
+ }
+ else if (double_int_scmp (idx,
+ double_int_add
+ (double_int_add
+ (tree_to_double_int (up_bound),
+ double_int_neg
+ (tree_to_double_int (low_bound))),
+ double_int_one)) > 0)
+ {
+ warning_at (location, OPT_Warray_bounds,
+ "array subscript is above array bounds");
+ TREE_NO_WARNING (t) = 1;
+ }
+ }
}
/* walk_tree() callback that checks if *TP is
if (TREE_CODE (t) == ARRAY_REF)
check_array_ref (location, t, false /*ignore_off_by_one*/);
- if (TREE_CODE (t) == INDIRECT_REF
+ if (TREE_CODE (t) == MEM_REF
|| (TREE_CODE (t) == RETURN_EXPR && TREE_OPERAND (t, 0)))
search_for_addr_array (TREE_OPERAND (t, 0), location);
|| POINTER_TYPE_P (TREE_TYPE (lhs)))
&& ((is_gimple_call (stmt)
&& gimple_call_fndecl (stmt) != NULL_TREE
- && DECL_IS_BUILTIN (gimple_call_fndecl (stmt)))
+ && DECL_BUILT_IN (gimple_call_fndecl (stmt)))
|| !gimple_vuse (stmt)))
return true;
}
{
basic_block bb;
- vr_value = XCNEWVEC (value_range_t *, num_ssa_names);
+ values_propagated = false;
+ num_vr_values = num_ssa_names;
+ vr_value = XCNEWVEC (value_range_t *, num_vr_values);
vr_phi_edge_counts = XCNEWVEC (int, num_ssa_names);
FOR_EACH_BB (bb)
}
}
+/* Return the singleton value-range for NAME or NAME. */
+
+static inline tree
+vrp_valueize (tree name)
+{
+ if (TREE_CODE (name) == SSA_NAME)
+ {
+ value_range_t *vr = get_value_range (name);
+ if (vr->type == VR_RANGE
+ && (vr->min == vr->max
+ || operand_equal_p (vr->min, vr->max, 0)))
+ return vr->min;
+ }
+ return name;
+}
/* Visit assignment STMT. If it produces an interesting range, record
the SSA name in *OUTPUT_P. */
&& TYPE_MAX_VALUE (TREE_TYPE (lhs)))
|| POINTER_TYPE_P (TREE_TYPE (lhs))))
{
- value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+ value_range_t new_vr = VR_INITIALIZER;
- if (code == GIMPLE_CALL)
+ /* Try folding the statement to a constant first. */
+ tree tem = gimple_fold_stmt_to_constant (stmt, vrp_valueize);
+ if (tem && !is_overflow_infinity (tem))
+ set_value_range (&new_vr, VR_RANGE, tem, tem, NULL);
+ /* Then dispatch to value-range extracting functions. */
+ else if (code == GIMPLE_CALL)
extract_range_basic (&new_vr, stmt);
else
extract_range_from_assignment (&new_vr, stmt);
static inline value_range_t
get_vr_for_comparison (int i)
{
- value_range_t vr = *(vr_value[i]);
+ value_range_t vr = *get_value_range (ssa_name (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
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)))
+ if (!integer_onep (int_const_binop (MINUS_EXPR, low, high)))
{
take_default = true;
break;
/* In general, assignments with virtual operands are not useful
for deriving ranges, with the obvious exception of calls to
builtin functions. */
-
if ((is_gimple_call (stmt)
&& gimple_call_fndecl (stmt) != NULL_TREE
- && DECL_IS_BUILTIN (gimple_call_fndecl (stmt)))
+ && DECL_BUILT_IN (gimple_call_fndecl (stmt)))
|| !gimple_vuse (stmt))
return vrp_visit_assignment_or_call (stmt, output_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. */
- FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
- set_value_range_to_varying (get_value_range (def));
+ /* All other statements produce nothing of interest for VRP, so mark
+ their outputs varying and prevent further simulation. */
+ FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_DEF)
+ set_value_range_to_varying (get_value_range (def));
+
+ return SSA_PROP_VARYING;
+}
+
+/* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
+ { VR1TYPE, VR0MIN, VR0MAX } and store the result
+ in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
+ possible such range. The resulting range is not canonicalized. */
+
+static void
+intersect_ranges (enum value_range_type *vr0type,
+ tree *vr0min, tree *vr0max,
+ enum value_range_type vr1type,
+ tree vr1min, tree vr1max)
+{
+ bool mineq = operand_equal_p (*vr0min, vr1min, 0);
+ bool maxeq = operand_equal_p (*vr0max, vr1max, 0);
+
+ /* [] is vr0, () is vr1 in the following classification comments. */
+ if (mineq && maxeq)
+ {
+ /* [( )] */
+ if (*vr0type == vr1type)
+ /* Nothing to do for equal ranges. */
+ ;
+ else if ((*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ || (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE))
+ {
+ /* For anti-range with range intersection the result is empty. */
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if (operand_less_p (*vr0max, vr1min) == 1
+ || operand_less_p (vr1max, *vr0min) == 1)
+ {
+ /* [ ] ( ) or ( ) [ ]
+ If the ranges have an empty intersection, the result of the
+ intersect operation is the range for intersecting an
+ anti-range with a range or empty when intersecting two ranges.
+ For intersecting two anti-ranges simply choose vr0. */
+ if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ ;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ /* Take VR0. */
+ }
+ }
+ else if ((maxeq || operand_less_p (vr1max, *vr0max) == 1)
+ && (mineq || operand_less_p (*vr0min, vr1min) == 1))
+ {
+ /* [ ( ) ] or [( ) ] or [ ( )] */
+ if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ {
+ /* If both are ranges the result is the inner one. */
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ /* Choose the right gap if the left one is empty. */
+ if (mineq)
+ {
+ if (TREE_CODE (vr1max) == INTEGER_CST)
+ *vr0min = int_const_binop (PLUS_EXPR, vr1max, integer_one_node);
+ else
+ *vr0min = vr1max;
+ }
+ /* Choose the left gap if the right one is empty. */
+ else if (maxeq)
+ {
+ if (TREE_CODE (vr1min) == INTEGER_CST)
+ *vr0max = int_const_binop (MINUS_EXPR, vr1min,
+ integer_one_node);
+ else
+ *vr0max = vr1min;
+ }
+ /* Choose the anti-range if the range is effectively varying. */
+ else if (vrp_val_is_min (*vr0min)
+ && vrp_val_is_max (*vr0max))
+ {
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ /* Else choose the range. */
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ /* If both are anti-ranges the result is the outer one. */
+ ;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ /* The intersection is empty. */
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if ((maxeq || operand_less_p (*vr0max, vr1max) == 1)
+ && (mineq || operand_less_p (vr1min, *vr0min) == 1))
+ {
+ /* ( [ ] ) or ([ ] ) or ( [ ]) */
+ if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ /* Choose the inner range. */
+ ;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ /* Choose the right gap if the left is empty. */
+ if (mineq)
+ {
+ *vr0type = VR_RANGE;
+ if (TREE_CODE (*vr0max) == INTEGER_CST)
+ *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
+ integer_one_node);
+ else
+ *vr0min = *vr0max;
+ *vr0max = vr1max;
+ }
+ /* Choose the left gap if the right is empty. */
+ else if (maxeq)
+ {
+ *vr0type = VR_RANGE;
+ if (TREE_CODE (*vr0min) == INTEGER_CST)
+ *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
+ integer_one_node);
+ else
+ *vr0max = *vr0min;
+ *vr0min = vr1min;
+ }
+ /* Choose the anti-range if the range is effectively varying. */
+ else if (vrp_val_is_min (vr1min)
+ && vrp_val_is_max (vr1max))
+ ;
+ /* Else choose the range. */
+ else
+ {
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ /* If both are anti-ranges the result is the outer one. */
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (vr1type == VR_ANTI_RANGE
+ && *vr0type == VR_RANGE)
+ {
+ /* The intersection is empty. */
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if ((operand_less_p (vr1min, *vr0max) == 1
+ || operand_equal_p (vr1min, *vr0max, 0))
+ && operand_less_p (*vr0min, vr1min) == 1)
+ {
+ /* [ ( ] ) or [ ]( ) */
+ if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ *vr0max = vr1max;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ *vr0min = vr1min;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ if (TREE_CODE (vr1min) == INTEGER_CST)
+ *vr0max = int_const_binop (MINUS_EXPR, vr1min,
+ integer_one_node);
+ else
+ *vr0max = vr1min;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = VR_RANGE;
+ if (TREE_CODE (*vr0max) == INTEGER_CST)
+ *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
+ integer_one_node);
+ else
+ *vr0min = *vr0max;
+ *vr0max = vr1max;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if ((operand_less_p (*vr0min, vr1max) == 1
+ || operand_equal_p (*vr0min, vr1max, 0))
+ && operand_less_p (vr1min, *vr0min) == 1)
+ {
+ /* ( [ ) ] or ( )[ ] */
+ if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ *vr0min = vr1min;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ *vr0max = vr1max;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ if (TREE_CODE (vr1max) == INTEGER_CST)
+ *vr0min = int_const_binop (PLUS_EXPR, vr1max,
+ integer_one_node);
+ else
+ *vr0min = vr1max;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = VR_RANGE;
+ if (TREE_CODE (*vr0min) == INTEGER_CST)
+ *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
+ integer_one_node);
+ else
+ *vr0max = *vr0min;
+ *vr0min = vr1min;
+ }
+ else
+ gcc_unreachable ();
+ }
+
+ /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
+ result for the intersection. That's always a conservative
+ correct estimate. */
+
+ return;
+}
+
+
+/* Intersect the two value-ranges *VR0 and *VR1 and store the result
+ in *VR0. This may not be the smallest possible such range. */
+
+static void
+vrp_intersect_ranges_1 (value_range_t *vr0, value_range_t *vr1)
+{
+ value_range_t saved;
+
+ /* If either range is VR_VARYING the other one wins. */
+ if (vr1->type == VR_VARYING)
+ return;
+ if (vr0->type == VR_VARYING)
+ {
+ copy_value_range (vr0, vr1);
+ return;
+ }
+
+ /* When either range is VR_UNDEFINED the resulting range is
+ VR_UNDEFINED, too. */
+ if (vr0->type == VR_UNDEFINED)
+ return;
+ if (vr1->type == VR_UNDEFINED)
+ {
+ set_value_range_to_undefined (vr0);
+ return;
+ }
+
+ /* Save the original vr0 so we can return it as conservative intersection
+ result when our worker turns things to varying. */
+ saved = *vr0;
+ intersect_ranges (&vr0->type, &vr0->min, &vr0->max,
+ vr1->type, vr1->min, vr1->max);
+ /* Make sure to canonicalize the result though as the inversion of a
+ VR_RANGE can still be a VR_RANGE. */
+ set_and_canonicalize_value_range (vr0, vr0->type,
+ vr0->min, vr0->max, vr0->equiv);
+ /* If that failed, use the saved original VR0. */
+ if (vr0->type == VR_VARYING)
+ {
+ *vr0 = saved;
+ return;
+ }
+ /* If the result is VR_UNDEFINED there is no need to mess with
+ the equivalencies. */
+ if (vr0->type == VR_UNDEFINED)
+ return;
- return SSA_PROP_VARYING;
+ /* The resulting set of equivalences for range intersection is the union of
+ the two sets. */
+ if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
+ bitmap_ior_into (vr0->equiv, vr1->equiv);
+ else if (vr1->equiv && !vr0->equiv)
+ bitmap_copy (vr0->equiv, vr1->equiv);
}
+static void
+vrp_intersect_ranges (value_range_t *vr0, value_range_t *vr1)
+{
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Intersecting\n ");
+ dump_value_range (dump_file, vr0);
+ fprintf (dump_file, "\nand\n ");
+ dump_value_range (dump_file, vr1);
+ fprintf (dump_file, "\n");
+ }
+ vrp_intersect_ranges_1 (vr0, vr1);
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "to\n ");
+ dump_value_range (dump_file, vr0);
+ fprintf (dump_file, "\n");
+ }
+}
/* Meet operation for value ranges. Given two value ranges VR0 and
VR1, store in VR0 a range that contains both VR0 and VR1. This
{
if (vr0->type == VR_UNDEFINED)
{
- copy_value_range (vr0, vr1);
+ /* Drop equivalences. See PR53465. */
+ set_value_range (vr0, vr1->type, vr1->min, vr1->max, NULL);
return;
}
if (vr1->type == VR_UNDEFINED)
{
- /* Nothing to do. VR0 already has the resulting range. */
+ /* VR0 already has the resulting range, just drop equivalences.
+ See PR53465. */
+ if (vr0->equiv)
+ bitmap_clear (vr0->equiv);
return;
}
return;
}
- if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
+ if (vr0->type == vr1->type
+ && compare_values (vr0->min, vr1->min) == 0
+ && compare_values (vr0->max, vr1->max) == 0)
+ {
+ /* If the value-ranges are identical just insersect
+ their equivalencies. */
+ }
+ else if (vr0->type == VR_RANGE && vr1->type == VR_RANGE)
{
int cmp;
tree min, max;
- /* Compute the convex hull of the ranges. The lower limit of
- the new range is the minimum of the two ranges. If they
+ /* If the two ranges represent an anti-range produce a
+ VR_RANGE with swapped min/max and let the range canonicalization
+ fix things up. */
+ if (vrp_val_is_min (vr0->min) && !is_overflow_infinity (vr0->min)
+ && vrp_val_is_max (vr1->max) && !is_overflow_infinity (vr1->max)
+ && TREE_CODE (vr1->min) == INTEGER_CST
+ && TREE_CODE (vr0->max) == INTEGER_CST
+ && compare_values (vr0->max, vr1->min) == -1)
+ {
+ min = vr1->min;
+ max = vr0->max;
+ }
+ else if (vrp_val_is_min (vr1->min) && !is_overflow_infinity (vr1->min)
+ && vrp_val_is_max (vr0->max) && !is_overflow_infinity (vr0->max)
+ && TREE_CODE (vr1->max) == INTEGER_CST
+ && TREE_CODE (vr0->min) == INTEGER_CST
+ && compare_values (vr1->max, vr0->min) == -1)
+ {
+ max = vr1->max;
+ min = vr0->min;
+ }
+ /* Otherwise compute the convex hull of the ranges. The lower limit of
+ the new range is the minimum of the two ranges. If they
cannot be compared, then give up. */
- cmp = compare_values (vr0->min, vr1->min);
- if (cmp == 0 || cmp == 1)
- min = vr1->min;
- else if (cmp == -1)
- min = vr0->min;
- else
- goto give_up;
-
- /* Similarly, the upper limit of the new range is the maximum
- of the two ranges. If they cannot be compared, then
- give up. */
- cmp = compare_values (vr0->max, vr1->max);
- if (cmp == 0 || cmp == -1)
- max = vr1->max;
- else if (cmp == 1)
- max = vr0->max;
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)
- bitmap_and_into (vr0->equiv, vr1->equiv);
- else if (vr0->equiv && !vr1->equiv)
- bitmap_clear (vr0->equiv);
-
- set_value_range (vr0, vr0->type, min, max, vr0->equiv);
- }
- else if (vr0->type == VR_ANTI_RANGE && vr1->type == VR_ANTI_RANGE)
- {
- /* Two anti-ranges meet only if their complements intersect.
- Only handle the case of identical ranges. */
- if (compare_values (vr0->min, vr1->min) == 0
- && compare_values (vr0->max, vr1->max) == 0
- && compare_values (vr0->min, vr0->max) == 0)
{
- /* The resulting set of equivalences is the intersection of
- the two sets. */
- if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
- bitmap_and_into (vr0->equiv, vr1->equiv);
- else if (vr0->equiv && !vr1->equiv)
- bitmap_clear (vr0->equiv);
+ cmp = compare_values (vr0->min, vr1->min);
+ if (cmp == 0 || cmp == 1)
+ min = vr1->min;
+ else if (cmp == -1)
+ min = vr0->min;
+ else
+ goto give_up;
+
+ /* Similarly, the upper limit of the new range is the maximum
+ of the two ranges. If they cannot be compared, then
+ give up. */
+ cmp = compare_values (vr0->max, vr1->max);
+ if (cmp == 0 || cmp == -1)
+ max = vr1->max;
+ else if (cmp == 1)
+ max = vr0->max;
+ 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;
}
- else
- goto give_up;
+
+ set_and_canonicalize_value_range (vr0, vr0->type, min, max, vr0->equiv);
}
else if (vr0->type == VR_ANTI_RANGE || vr1->type == VR_ANTI_RANGE)
{
- /* For a numeric range [VAL1, VAL2] and an anti-range ~[VAL3, VAL4],
- only handle the case where the ranges have an empty intersection.
- The result of the meet operation is the anti-range. */
- if (!symbolic_range_p (vr0)
- && !symbolic_range_p (vr1)
- && !value_ranges_intersect_p (vr0, vr1))
- {
- /* Copy most of VR1 into VR0. Don't copy VR1's equivalence
- set. We need to compute the intersection of the two
- equivalence sets. */
- if (vr1->type == VR_ANTI_RANGE)
- set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv);
+ if (symbolic_range_p (vr0)
+ || symbolic_range_p (vr1))
+ goto give_up;
- /* The resulting set of equivalences is the intersection of
- the two sets. */
- if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
- bitmap_and_into (vr0->equiv, vr1->equiv);
- else if (vr0->equiv && !vr1->equiv)
- bitmap_clear (vr0->equiv);
+ /* [] is vr0, () is vr1 in the following classification comments. */
+ if (operand_less_p (vr0->max, vr1->min) == 1
+ || operand_less_p (vr1->max, vr0->min) == 1)
+ {
+ /* [ ] ( ) or ( ) [ ]
+ If the ranges have an empty intersection, result of the meet
+ operation is the anti-range or if both are anti-ranges
+ it covers all. */
+ if (vr0->type == VR_ANTI_RANGE
+ && vr1->type == VR_ANTI_RANGE)
+ goto give_up;
+ else if (vr1->type == VR_ANTI_RANGE)
+ set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv);
+ }
+ else if (operand_less_p (vr1->max, vr0->max) == 1
+ && operand_less_p (vr0->min, vr1->min) == 1)
+ {
+ /* [ ( ) ]
+ Arbitrarily choose the left or inner gap. */
+ if (vr0->type == VR_ANTI_RANGE
+ && vr1->type == VR_ANTI_RANGE)
+ set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv);
+ else if (vr0->type == VR_ANTI_RANGE)
+ set_and_canonicalize_value_range (vr0, vr0->type, vr0->min,
+ int_const_binop (MINUS_EXPR, vr1->min, integer_one_node),
+ vr0->equiv);
+ else
+ goto give_up;
+ }
+ else if (operand_less_p (vr0->max, vr1->max) == 1
+ && operand_less_p (vr1->min, vr0->min) == 1)
+ {
+ /* ( [ ] )
+ Arbitrarily choose the left or inner gap. */
+ if (vr0->type == VR_ANTI_RANGE
+ && vr1->type == VR_ANTI_RANGE)
+ /* Nothing to do. */;
+ else if (vr1->type == VR_ANTI_RANGE)
+ set_and_canonicalize_value_range (vr0, vr1->type, vr1->min,
+ int_const_binop (MINUS_EXPR, vr0->min, integer_one_node),
+ vr0->equiv);
+ else
+ goto give_up;
+ }
+ else if (operand_less_p (vr1->min, vr0->max) == 1
+ && operand_less_p (vr0->max, vr1->max) == 1)
+ {
+ /* [ ( ] ) */
+ if (vr0->type == VR_ANTI_RANGE
+ && vr1->type == VR_ANTI_RANGE)
+ set_value_range (vr0, vr0->type, vr1->min, vr0->max, vr0->equiv);
+ else if (vr0->type == VR_ANTI_RANGE)
+ set_and_canonicalize_value_range (vr0, vr0->type, vr0->min,
+ int_const_binop (MINUS_EXPR, vr1->min, integer_one_node),
+ vr0->equiv);
+ else
+ set_and_canonicalize_value_range (vr0, vr1->type,
+ int_const_binop (PLUS_EXPR, vr0->max, integer_one_node),
+ vr1->max, vr0->equiv);
+ }
+ else if (operand_less_p (vr0->min, vr1->max) == 1
+ && operand_less_p (vr1->max, vr0->max) == 1)
+ {
+ /* ( [ ) ] */
+ if (vr0->type == VR_ANTI_RANGE
+ && vr1->type == VR_ANTI_RANGE)
+ set_value_range (vr0, vr1->type, vr0->min, vr1->max, vr0->equiv);
+ else if (vr0->type == VR_ANTI_RANGE)
+ set_and_canonicalize_value_range (vr0, vr0->type,
+ int_const_binop (PLUS_EXPR, vr1->max, integer_one_node),
+ vr0->max, vr0->equiv);
+ else
+ set_and_canonicalize_value_range (vr0, vr1->type, vr1->min,
+ int_const_binop (MINUS_EXPR, vr0->min, integer_one_node),
+ vr0->equiv);
}
else
goto give_up;
else
gcc_unreachable ();
+ /* The resulting set of equivalences is always the intersection of
+ the two sets. Above we always left the equivalency set of vr0 as-is. */
+ if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
+ bitmap_and_into (vr0->equiv, vr1->equiv);
+ else if (vr0->equiv && !vr1->equiv)
+ bitmap_clear (vr0->equiv);
+
return;
give_up:
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 };
+ value_range_t vr_result = VR_INITIALIZER;
+ bool first = true;
int edges, old_edges;
struct loop *l;
- copy_value_range (&vr_result, lhs_vr);
-
if (dump_file && (dump_flags & TDF_DETAILS))
{
fprintf (dump_file, "\nVisiting PHI node: ");
fprintf (dump_file, "\n");
}
- vrp_meet (&vr_result, &vr_arg);
+ if (first)
+ copy_value_range (&vr_result, &vr_arg);
+ else
+ vrp_meet (&vr_result, &vr_arg);
+ first = false;
if (vr_result.type == VR_VARYING)
break;
}
}
- /* If this is a loop PHI node SCEV may known more about its
- value-range. */
- if (current_loops
- && (l = loop_containing_stmt (phi))
- && l->header == gimple_bb (phi))
- adjust_range_with_scev (&vr_result, l, phi, lhs);
-
if (vr_result.type == VR_VARYING)
goto varying;
+ else if (vr_result.type == VR_UNDEFINED)
+ goto update_range;
old_edges = vr_phi_edge_counts[SSA_NAME_VERSION (lhs)];
vr_phi_edge_counts[SSA_NAME_VERSION (lhs)] = edges;
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
- && edges <= old_edges)
- {
- if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
- {
- int cmp_min = compare_values (lhs_vr->min, vr_result.min);
- int cmp_max = compare_values (lhs_vr->max, vr_result.max);
-
- /* If the new minimum is smaller or larger than the previous
- one, go all the way to -INF. In the first case, to avoid
- iterating millions of times to reach -INF, and in the
- other case to avoid infinite bouncing between different
- minimums. */
- if (cmp_min > 0 || cmp_min < 0)
- {
- /* If we will end up with a (-INF, +INF) range, set it to
- VARYING. Same if the previous max value was invalid for
- the type and we'd end up with vr_result.min > vr_result.max. */
- if (vrp_val_is_max (vr_result.max)
- || compare_values (TYPE_MIN_VALUE (TREE_TYPE (vr_result.min)),
- vr_result.max) > 0)
- goto varying;
-
- 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 =
- negative_overflow_infinity (TREE_TYPE (vr_result.min));
- else
- goto varying;
- }
-
- /* Similarly, if the new maximum is smaller or larger than
- the previous one, go all the way to +INF. */
- if (cmp_max < 0 || cmp_max > 0)
- {
- /* If we will end up with a (-INF, +INF) range, set it to
- VARYING. Same if the previous min value was invalid for
- the type and we'd end up with vr_result.max < vr_result.min. */
- if (vrp_val_is_min (vr_result.min)
- || compare_values (TYPE_MAX_VALUE (TREE_TYPE (vr_result.max)),
- vr_result.min) < 0)
- goto varying;
-
- 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 =
- positive_overflow_infinity (TREE_TYPE (vr_result.max));
- else
- goto varying;
- }
- }
+ if (edges > 0
+ && gimple_phi_num_args (phi) > 1
+ && edges == old_edges)
+ {
+ int cmp_min = compare_values (lhs_vr->min, vr_result.min);
+ int cmp_max = compare_values (lhs_vr->max, vr_result.max);
+
+ /* For non VR_RANGE or for pointers fall back to varying if
+ the range changed. */
+ if ((lhs_vr->type != VR_RANGE || vr_result.type != VR_RANGE
+ || POINTER_TYPE_P (TREE_TYPE (lhs)))
+ && (cmp_min != 0 || cmp_max != 0))
+ goto varying;
+
+ /* If the new minimum is smaller or larger than the previous
+ one, go all the way to -INF. In the first case, to avoid
+ iterating millions of times to reach -INF, and in the
+ other case to avoid infinite bouncing between different
+ minimums. */
+ if (cmp_min > 0 || cmp_min < 0)
+ {
+ 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 =
+ negative_overflow_infinity (TREE_TYPE (vr_result.min));
+ }
+
+ /* Similarly, if the new maximum is smaller or larger than
+ the previous one, go all the way to +INF. */
+ if (cmp_max < 0 || cmp_max > 0)
+ {
+ 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 =
+ positive_overflow_infinity (TREE_TYPE (vr_result.max));
+ }
+
+ /* If we dropped either bound to +-INF then if this is a loop
+ PHI node SCEV may known more about its value-range. */
+ if ((cmp_min > 0 || cmp_min < 0
+ || cmp_max < 0 || cmp_max > 0)
+ && current_loops
+ && (l = loop_containing_stmt (phi))
+ && l->header == gimple_bb (phi))
+ adjust_range_with_scev (&vr_result, l, phi, lhs);
+
+ /* If we will end up with a (-INF, +INF) range, set it to
+ VARYING. Same if the previous max value was invalid for
+ the type and we end up with vr_result.min > vr_result.max. */
+ if ((vrp_val_is_max (vr_result.max)
+ && vrp_val_is_min (vr_result.min))
+ || compare_values (vr_result.min,
+ vr_result.max) > 0)
+ goto varying;
}
/* If the new range is different than the previous value, keep
iterating. */
+update_range:
if (update_value_range (lhs, &vr_result))
- return SSA_PROP_INTERESTING;
+ {
+ if (dump_file && (dump_flags & TDF_DETAILS))
+ {
+ fprintf (dump_file, "Found new range for ");
+ print_generic_expr (dump_file, lhs, 0);
+ fprintf (dump_file, ": ");
+ dump_value_range (dump_file, &vr_result);
+ fprintf (dump_file, "\n\n");
+ }
+
+ return SSA_PROP_INTERESTING;
+ }
/* Nothing changed, don't add outgoing edges. */
return SSA_PROP_NOT_INTERESTING;
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;
+ tree lhs, op0, op1;
bool need_conversion;
- op0 = gimple_assign_rhs1 (stmt);
- if (TYPE_PRECISION (TREE_TYPE (op0)) != 1)
- {
- if (TREE_CODE (op0) != SSA_NAME)
- return false;
- vr = get_value_range (op0);
-
- 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. */
- if (rhs_code != EQ_EXPR
- && rhs_code != NE_EXPR
- && rhs_code != TRUTH_XOR_EXPR)
- return false;
-
- if (!integer_zerop (op1)
- && !integer_onep (op1)
- && !integer_all_onesp (op1))
- return false;
+ /* We handle only !=/== case here. */
+ gcc_assert (rhs_code == EQ_EXPR || rhs_code == NE_EXPR);
- /* 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;
+ op0 = gimple_assign_rhs1 (stmt);
+ if (!op_with_boolean_value_range_p (op0))
+ 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;
- }
- }
- }
+ op1 = gimple_assign_rhs2 (stmt);
+ if (!op_with_boolean_value_range_p (op1))
+ return false;
- if (sop && issue_strict_overflow_warning (WARN_STRICT_OVERFLOW_MISC))
+ /* Reduce number of cases to handle to NE_EXPR. As there is no
+ BIT_XNOR_EXPR we cannot replace A == B with a single statement. */
+ if (rhs_code == EQ_EXPR)
{
- 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 |"));
+ if (TREE_CODE (op1) == INTEGER_CST)
+ op1 = int_const_binop (BIT_XOR_EXPR, op1, integer_one_node);
else
- warning_at (location, OPT_Wstrict_overflow,
- _("assuming signed overflow does not occur when "
- "simplifying ==, != or ! to identity or ^"));
+ return false;
}
- need_conversion =
- !useless_type_conversion_p (TREE_TYPE (gimple_assign_lhs (stmt)),
- TREE_TYPE (op0));
+ lhs = gimple_assign_lhs (stmt);
+ need_conversion
+ = !useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (op0));
- /* Make sure to not sign-extend -1 as a boolean value. */
+ /* Make sure to not sign-extend a 1-bit 1 when converting the result. */
if (need_conversion
&& !TYPE_UNSIGNED (TREE_TYPE (op0))
- && TYPE_PRECISION (TREE_TYPE (op0)) == 1)
- return false;
-
- 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)
+ && TYPE_PRECISION (TREE_TYPE (op0)) == 1
+ && TYPE_PRECISION (TREE_TYPE (lhs)) > 1)
return false;
- gimple_assign_set_rhs_with_ops (gsi, rhs_code, op0, op1);
+ /* For A != 0 we can substitute A itself. */
+ if (integer_zerop (op1))
+ gimple_assign_set_rhs_with_ops (gsi,
+ need_conversion
+ ? NOP_EXPR : TREE_CODE (op0),
+ op0, NULL_TREE);
+ /* For A != B we substitute A ^ B. Either with conversion. */
+ else if (need_conversion)
+ {
+ gimple newop;
+ tree tem = create_tmp_reg (TREE_TYPE (op0), NULL);
+ newop = gimple_build_assign_with_ops (BIT_XOR_EXPR, tem, op0, op1);
+ tem = make_ssa_name (tem, newop);
+ gimple_assign_set_lhs (newop, tem);
+ gsi_insert_before (gsi, newop, GSI_SAME_STMT);
+ update_stmt (newop);
+ gimple_assign_set_rhs_with_ops (gsi, NOP_EXPR, tem, NULL_TREE);
+ }
+ /* Or without. */
+ else
+ gimple_assign_set_rhs_with_ops (gsi, BIT_XOR_EXPR, op0, op1);
update_stmt (gsi_stmt (*gsi));
+
return true;
}
if (rhs_code == TRUNC_DIV_EXPR)
{
- t = build_int_cst (NULL_TREE, tree_log2 (op1));
+ t = build_int_cst (integer_type_node, tree_log2 (op1));
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 = int_const_binop (MINUS_EXPR, op1, t);
t = fold_convert (TREE_TYPE (op0), t);
gimple_assign_set_rhs_code (stmt, BIT_AND_EXPR);
return false;
}
+/* Optimize away redundant BIT_AND_EXPR and BIT_IOR_EXPR.
+ If all the bits that are being cleared by & are already
+ known to be zero from VR, or all the bits that are being
+ set by | are already known to be one from VR, the bit
+ operation is redundant. */
+
+static bool
+simplify_bit_ops_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
+{
+ tree op0 = gimple_assign_rhs1 (stmt);
+ tree op1 = gimple_assign_rhs2 (stmt);
+ tree op = NULL_TREE;
+ value_range_t vr0 = VR_INITIALIZER;
+ value_range_t vr1 = VR_INITIALIZER;
+ double_int may_be_nonzero0, may_be_nonzero1;
+ double_int must_be_nonzero0, must_be_nonzero1;
+ double_int mask;
+
+ if (TREE_CODE (op0) == SSA_NAME)
+ vr0 = *(get_value_range (op0));
+ else if (is_gimple_min_invariant (op0))
+ set_value_range_to_value (&vr0, op0, NULL);
+ else
+ return false;
+
+ if (TREE_CODE (op1) == SSA_NAME)
+ vr1 = *(get_value_range (op1));
+ else if (is_gimple_min_invariant (op1))
+ set_value_range_to_value (&vr1, op1, NULL);
+ else
+ return false;
+
+ if (!zero_nonzero_bits_from_vr (&vr0, &may_be_nonzero0, &must_be_nonzero0))
+ return false;
+ if (!zero_nonzero_bits_from_vr (&vr1, &may_be_nonzero1, &must_be_nonzero1))
+ return false;
+
+ switch (gimple_assign_rhs_code (stmt))
+ {
+ case BIT_AND_EXPR:
+ mask = double_int_and_not (may_be_nonzero0, must_be_nonzero1);
+ if (double_int_zero_p (mask))
+ {
+ op = op0;
+ break;
+ }
+ mask = double_int_and_not (may_be_nonzero1, must_be_nonzero0);
+ if (double_int_zero_p (mask))
+ {
+ op = op1;
+ break;
+ }
+ break;
+ case BIT_IOR_EXPR:
+ mask = double_int_and_not (may_be_nonzero0, must_be_nonzero1);
+ if (double_int_zero_p (mask))
+ {
+ op = op1;
+ break;
+ }
+ mask = double_int_and_not (may_be_nonzero1, must_be_nonzero0);
+ if (double_int_zero_p (mask))
+ {
+ op = op0;
+ break;
+ }
+ break;
+ default:
+ gcc_unreachable ();
+ }
+
+ if (op == NULL_TREE)
+ return false;
+
+ gimple_assign_set_rhs_with_ops (gsi, TREE_CODE (op), op, NULL);
+ update_stmt (gsi_stmt (*gsi));
+ return true;
+}
+
/* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
a known value range VR.
return false;
}
+/* Simplify an integral conversion from an SSA name in STMT. */
+
+static bool
+simplify_conversion_using_ranges (gimple stmt)
+{
+ tree innerop, middleop, finaltype;
+ gimple def_stmt;
+ value_range_t *innervr;
+ bool inner_unsigned_p, middle_unsigned_p, final_unsigned_p;
+ unsigned inner_prec, middle_prec, final_prec;
+ double_int innermin, innermed, innermax, middlemin, middlemed, middlemax;
+
+ finaltype = TREE_TYPE (gimple_assign_lhs (stmt));
+ if (!INTEGRAL_TYPE_P (finaltype))
+ return false;
+ middleop = gimple_assign_rhs1 (stmt);
+ def_stmt = SSA_NAME_DEF_STMT (middleop);
+ if (!is_gimple_assign (def_stmt)
+ || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (def_stmt)))
+ return false;
+ innerop = gimple_assign_rhs1 (def_stmt);
+ if (TREE_CODE (innerop) != SSA_NAME)
+ return false;
+
+ /* Get the value-range of the inner operand. */
+ innervr = get_value_range (innerop);
+ if (innervr->type != VR_RANGE
+ || TREE_CODE (innervr->min) != INTEGER_CST
+ || TREE_CODE (innervr->max) != INTEGER_CST)
+ return false;
+
+ /* Simulate the conversion chain to check if the result is equal if
+ the middle conversion is removed. */
+ innermin = tree_to_double_int (innervr->min);
+ innermax = tree_to_double_int (innervr->max);
+
+ inner_prec = TYPE_PRECISION (TREE_TYPE (innerop));
+ middle_prec = TYPE_PRECISION (TREE_TYPE (middleop));
+ final_prec = TYPE_PRECISION (finaltype);
+
+ /* If the first conversion is not injective, the second must not
+ be widening. */
+ if (double_int_cmp (double_int_sub (innermax, innermin),
+ double_int_mask (middle_prec), true) > 0
+ && middle_prec < final_prec)
+ return false;
+ /* We also want a medium value so that we can track the effect that
+ narrowing conversions with sign change have. */
+ inner_unsigned_p = TYPE_UNSIGNED (TREE_TYPE (innerop));
+ if (inner_unsigned_p)
+ innermed = double_int_rshift (double_int_mask (inner_prec),
+ 1, inner_prec, false);
+ else
+ innermed = double_int_zero;
+ if (double_int_cmp (innermin, innermed, inner_unsigned_p) >= 0
+ || double_int_cmp (innermed, innermax, inner_unsigned_p) >= 0)
+ innermed = innermin;
+
+ middle_unsigned_p = TYPE_UNSIGNED (TREE_TYPE (middleop));
+ middlemin = double_int_ext (innermin, middle_prec, middle_unsigned_p);
+ middlemed = double_int_ext (innermed, middle_prec, middle_unsigned_p);
+ middlemax = double_int_ext (innermax, middle_prec, middle_unsigned_p);
+
+ /* Require that the final conversion applied to both the original
+ and the intermediate range produces the same result. */
+ final_unsigned_p = TYPE_UNSIGNED (finaltype);
+ if (!double_int_equal_p (double_int_ext (middlemin,
+ final_prec, final_unsigned_p),
+ double_int_ext (innermin,
+ final_prec, final_unsigned_p))
+ || !double_int_equal_p (double_int_ext (middlemed,
+ final_prec, final_unsigned_p),
+ double_int_ext (innermed,
+ final_prec, final_unsigned_p))
+ || !double_int_equal_p (double_int_ext (middlemax,
+ final_prec, final_unsigned_p),
+ double_int_ext (innermax,
+ final_prec, final_unsigned_p)))
+ return false;
+
+ gimple_assign_set_rhs1 (stmt, innerop);
+ update_stmt (stmt);
+ return true;
+}
+
+/* Return whether the value range *VR fits in an integer type specified
+ by PRECISION and UNSIGNED_P. */
+
+static bool
+range_fits_type_p (value_range_t *vr, unsigned precision, bool unsigned_p)
+{
+ tree src_type;
+ unsigned src_precision;
+ double_int tem;
+
+ /* We can only handle integral and pointer types. */
+ src_type = TREE_TYPE (vr->min);
+ if (!INTEGRAL_TYPE_P (src_type)
+ && !POINTER_TYPE_P (src_type))
+ return false;
+
+ /* An extension is always fine, so is an identity transform. */
+ src_precision = TYPE_PRECISION (TREE_TYPE (vr->min));
+ if (src_precision < precision
+ || (src_precision == precision
+ && TYPE_UNSIGNED (src_type) == unsigned_p))
+ return true;
+
+ /* Now we can only handle ranges with constant bounds. */
+ if (vr->type != VR_RANGE
+ || TREE_CODE (vr->min) != INTEGER_CST
+ || TREE_CODE (vr->max) != INTEGER_CST)
+ return false;
+
+ /* For precision-preserving sign-changes the MSB of the double-int
+ has to be clear. */
+ if (src_precision == precision
+ && (TREE_INT_CST_HIGH (vr->min) | TREE_INT_CST_HIGH (vr->max)) < 0)
+ return false;
+
+ /* Then we can perform the conversion on both ends and compare
+ the result for equality. */
+ tem = double_int_ext (tree_to_double_int (vr->min), precision, unsigned_p);
+ if (!double_int_equal_p (tree_to_double_int (vr->min), tem))
+ return false;
+ tem = double_int_ext (tree_to_double_int (vr->max), precision, unsigned_p);
+ if (!double_int_equal_p (tree_to_double_int (vr->max), tem))
+ return false;
+
+ return true;
+}
+
+/* Simplify a conversion from integral SSA name to float in STMT. */
+
+static bool
+simplify_float_conversion_using_ranges (gimple_stmt_iterator *gsi, gimple stmt)
+{
+ tree rhs1 = gimple_assign_rhs1 (stmt);
+ value_range_t *vr = get_value_range (rhs1);
+ enum machine_mode fltmode = TYPE_MODE (TREE_TYPE (gimple_assign_lhs (stmt)));
+ enum machine_mode mode;
+ tree tem;
+ gimple conv;
+
+ /* We can only handle constant ranges. */
+ if (vr->type != VR_RANGE
+ || TREE_CODE (vr->min) != INTEGER_CST
+ || TREE_CODE (vr->max) != INTEGER_CST)
+ return false;
+
+ /* First check if we can use a signed type in place of an unsigned. */
+ if (TYPE_UNSIGNED (TREE_TYPE (rhs1))
+ && (can_float_p (fltmode, TYPE_MODE (TREE_TYPE (rhs1)), 0)
+ != CODE_FOR_nothing)
+ && range_fits_type_p (vr, GET_MODE_PRECISION
+ (TYPE_MODE (TREE_TYPE (rhs1))), 0))
+ mode = TYPE_MODE (TREE_TYPE (rhs1));
+ /* If we can do the conversion in the current input mode do nothing. */
+ else if (can_float_p (fltmode, TYPE_MODE (TREE_TYPE (rhs1)),
+ TYPE_UNSIGNED (TREE_TYPE (rhs1))))
+ return false;
+ /* Otherwise search for a mode we can use, starting from the narrowest
+ integer mode available. */
+ else
+ {
+ mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
+ do
+ {
+ /* If we cannot do a signed conversion to float from mode
+ or if the value-range does not fit in the signed type
+ try with a wider mode. */
+ if (can_float_p (fltmode, mode, 0) != CODE_FOR_nothing
+ && range_fits_type_p (vr, GET_MODE_PRECISION (mode), 0))
+ break;
+
+ mode = GET_MODE_WIDER_MODE (mode);
+ /* But do not widen the input. Instead leave that to the
+ optabs expansion code. */
+ if (GET_MODE_PRECISION (mode) > TYPE_PRECISION (TREE_TYPE (rhs1)))
+ return false;
+ }
+ while (mode != VOIDmode);
+ if (mode == VOIDmode)
+ return false;
+ }
+
+ /* It works, insert a truncation or sign-change before the
+ float conversion. */
+ tem = create_tmp_var (build_nonstandard_integer_type
+ (GET_MODE_PRECISION (mode), 0), NULL);
+ conv = gimple_build_assign_with_ops (NOP_EXPR, tem, rhs1, NULL_TREE);
+ tem = make_ssa_name (tem, conv);
+ gimple_assign_set_lhs (conv, tem);
+ gsi_insert_before (gsi, conv, GSI_SAME_STMT);
+ gimple_assign_set_rhs1 (stmt, tem);
+ update_stmt (stmt);
+
+ return true;
+}
+
/* Simplify STMT using ranges if possible. */
static bool
if (is_gimple_assign (stmt))
{
enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
+ tree rhs1 = gimple_assign_rhs1 (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))))
+ /* Transform EQ_EXPR, NE_EXPR into BIT_XOR_EXPR or identity
+ if the RHS is zero or one, and the LHS are known to be boolean
+ values. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
return simplify_truth_ops_using_ranges (gsi, stmt);
break;
than zero and the second operand is an exact power of two. */
case TRUNC_DIV_EXPR:
case TRUNC_MOD_EXPR:
- if (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt)))
+ if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
&& integer_pow2p (gimple_assign_rhs2 (stmt)))
return simplify_div_or_mod_using_ranges (stmt);
break;
/* Transform ABS (X) into X or -X as appropriate. */
case ABS_EXPR:
- if (TREE_CODE (gimple_assign_rhs1 (stmt)) == SSA_NAME
- && INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_rhs1 (stmt))))
+ if (TREE_CODE (rhs1) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
return simplify_abs_using_ranges (stmt);
break;
+ case BIT_AND_EXPR:
+ case BIT_IOR_EXPR:
+ /* Optimize away BIT_AND_EXPR and BIT_IOR_EXPR
+ if all the bits being cleared are already cleared or
+ all the bits being set are already set. */
+ if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
+ return simplify_bit_ops_using_ranges (gsi, stmt);
+ break;
+
+ CASE_CONVERT:
+ if (TREE_CODE (rhs1) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
+ return simplify_conversion_using_ranges (stmt);
+ break;
+
+ case FLOAT_EXPR:
+ if (TREE_CODE (rhs1) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (rhs1)))
+ return simplify_float_conversion_using_ranges (gsi, stmt);
+ break;
+
default:
break;
}
/* 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)
+ FOR_EACH_VEC_ELT (edge, to_remove_edges, i, e)
e->flags |= EDGE_DFS_BACK;
/* Allocate our unwinder stack to unwind any temporary equivalences
may be some value in handling SWITCH_EXPR here, I doubt it's
terribly important. */
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. */
- 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))))
+ /* We're basically looking for a switch or any kind of conditional with
+ integral or pointer type arguments. Note the type of the second
+ argument will be the same as the first argument, so no need to
+ check it explicitly. */
+ if (gimple_code (last) == GIMPLE_SWITCH
+ || (gimple_code (last) == GIMPLE_COND
+ && TREE_CODE (gimple_cond_lhs (last)) == SSA_NAME
+ && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_cond_lhs (last)))
+ || POINTER_TYPE_P (TREE_TYPE (gimple_cond_lhs (last))))
+ && (TREE_CODE (gimple_cond_rhs (last)) == SSA_NAME
+ || is_gimple_min_invariant (gimple_cond_rhs (last)))))
{
edge_iterator ei;
/* We've got a block with multiple predecessors and multiple
- successors which also ends in a suitable conditional. For
- each predecessor, see if we can thread it to a specific
- successor. */
+ successors which also ends in a suitable conditional or
+ switch statement. For each predecessor, see if we can thread
+ it to a specific successor. */
FOR_EACH_EDGE (e, ei, bb->preds)
{
/* Do not thread across back edges or abnormal edges
vrp_finalize (void)
{
size_t i;
- prop_value_t *single_val_range;
- bool do_value_subst_p;
+
+ values_propagated = true;
if (dump_file)
{
fprintf (dump_file, "\n");
}
- /* We may have ended with ranges that have exactly one value. Those
- values can be substituted as any other const propagated
- value using substitute_and_fold. */
- single_val_range = XCNEWVEC (prop_value_t, num_ssa_names);
-
- do_value_subst_p = false;
- for (i = 0; i < num_ssa_names; i++)
- if (vr_value[i]
- && vr_value[i]->type == VR_RANGE
- && vr_value[i]->min == vr_value[i]->max
- && is_gimple_min_invariant (vr_value[i]->min))
- {
- single_val_range[i].value = vr_value[i]->min;
- do_value_subst_p = true;
- }
-
- if (!do_value_subst_p)
- {
- /* We found no single-valued ranges, don't waste time trying to
- do single value substitution in substitute_and_fold. */
- free (single_val_range);
- single_val_range = NULL;
- }
-
- substitute_and_fold (single_val_range, vrp_fold_stmt);
+ substitute_and_fold (op_with_constant_singleton_value_range,
+ vrp_fold_stmt, false);
if (warn_array_bounds)
check_all_array_refs ();
identify_jump_threads ();
/* Free allocated memory. */
- for (i = 0; i < num_ssa_names; i++)
+ for (i = 0; i < num_vr_values; i++)
if (vr_value[i])
{
BITMAP_FREE (vr_value[i]->equiv);
free (vr_value[i]);
}
- free (single_val_range);
free (vr_value);
free (vr_phi_edge_counts);
ssa_propagate (vrp_visit_stmt, vrp_visit_phi_node);
vrp_finalize ();
+ free_numbers_of_iterations_estimates ();
+
/* 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. */
/* 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)
+ FOR_EACH_VEC_ELT (edge, to_remove_edges, i, e)
remove_edge (e);
/* Update SWITCH_EXPR case label vector. */
- for (i = 0; VEC_iterate (switch_update, to_update_switch_stmts, i, su); ++i)
+ FOR_EACH_VEC_ELT (switch_update, to_update_switch_stmts, i, su)
{
size_t j;
size_t n = TREE_VEC_LENGTH (su->vec);
0, /* properties_destroyed */
0, /* todo_flags_start */
TODO_cleanup_cfg
- | TODO_ggc_collect
+ | TODO_update_ssa
| TODO_verify_ssa
- | TODO_dump_func
- | TODO_update_ssa /* todo_flags_finish */
+ | TODO_verify_flow
+ | TODO_ggc_collect /* todo_flags_finish */
}
};