/* 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
+ 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"
+/* 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;
+
/* Set of SSA names found live during the RPO traversal of the function
for still active basic-blocks. */
static sbitmap *live;
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;
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
&& 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;
}
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. */
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));
{
value_range_t *vr = get_value_range (t);
+ if (INTEGRAL_TYPE_P (t)
+ && TYPE_UNSIGNED (t))
+ return true;
+
if (!vr)
return false;
{
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
{
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)
}
+/* 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 bool
+zero_nonzero_bits_from_vr (value_range_t *vr, double_int *may_be_nonzero,
+ double_int *must_be_nonzero)
+{
+ if (range_int_cst_p (vr))
+ {
+ if (range_int_cst_singleton_p (vr))
+ {
+ *may_be_nonzero = tree_to_double_int (vr->min);
+ *must_be_nonzero = *may_be_nonzero;
+ return true;
+ }
+ if (tree_int_cst_sgn (vr->min) >= 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;
+ }
+ return true;
+ }
+ }
+ may_be_nonzero->low = ALL_ONES;
+ may_be_nonzero->high = ALL_ONES;
+ must_be_nonzero->low = 0;
+ must_be_nonzero->high = 0;
+ return false;
+}
+
+
/* Extract range information from a binary expression EXPR based on
the ranges of each of its operands and the expression code. */
&& code != CEIL_DIV_EXPR
&& code != EXACT_DIV_EXPR
&& code != ROUND_DIV_EXPR
+ && code != TRUNC_MOD_EXPR
&& code != RSHIFT_EXPR
&& code != MIN_EXPR
&& code != MAX_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
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);
+ 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);
+ gcc_unreachable ();
return;
}
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;
+ if (code == PLUS_EXPR)
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+ /* 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);
}
-
- /* 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);
/* If both additions overflowed the range kind is still correct.
This happens regularly with subtracting something in unsigned
}
}
+ /* For divisions, if flag_non_call_exceptions is true, we must
+ not eliminate a division by zero. */
+ if ((code == TRUNC_DIV_EXPR
+ || code == FLOOR_DIV_EXPR
+ || code == CEIL_DIV_EXPR
+ || code == EXACT_DIV_EXPR
+ || code == ROUND_DIV_EXPR)
+ && 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. */
}
}
}
+ else if (code == TRUNC_MOD_EXPR)
+ {
+ bool sop = false;
+ 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, TREE_TYPE (vr1.min), 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 (TREE_TYPE (max))
+ || (vrp_expr_computes_nonnegative (op0, &sop) && !sop))
+ min = build_int_cst (TREE_TYPE (max), 0);
+ else
+ min = fold_unary_to_constant (NEGATE_EXPR, TREE_TYPE (max), 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)
+ else if (code == BIT_AND_EXPR || code == BIT_IOR_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
+ bool vr0_int_cst_singleton_p, vr1_int_cst_singleton_p;
+ bool int_cst_range0, int_cst_range1;
+ double_int may_be_nonzero0, may_be_nonzero1;
+ double_int must_be_nonzero0, must_be_nonzero1;
+
+ vr0_int_cst_singleton_p = range_int_cst_singleton_p (&vr0);
+ vr1_int_cst_singleton_p = range_int_cst_singleton_p (&vr1);
+ 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 (vr0_int_cst_singleton_p && vr1_int_cst_singleton_p)
+ min = max = int_const_binop (code, vr0.max, vr1.max);
+ else if (!int_cst_range0 && !int_cst_range1)
{
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)
+ {
+ min = double_int_to_tree (expr_type,
+ double_int_and (must_be_nonzero0,
+ must_be_nonzero1));
+ max = double_int_to_tree (expr_type,
+ double_int_and (may_be_nonzero0,
+ may_be_nonzero1));
+ if (TREE_OVERFLOW (min) || tree_int_cst_sgn (min) < 0)
+ min = NULL_TREE;
+ if (TREE_OVERFLOW (max) || tree_int_cst_sgn (max) < 0)
+ max = NULL_TREE;
+ if (int_cst_range0 && tree_int_cst_sgn (vr0.min) >= 0)
{
- ior_max.low = ~(unsigned HOST_WIDE_INT)0u;
- ior_max.high |= ((HOST_WIDE_INT) 1
- << floor_log2 (ior_max.high)) - 1;
+ if (min == NULL_TREE)
+ min = build_int_cst (expr_type, 0);
+ if (max == NULL_TREE || tree_int_cst_lt (vr0.max, max))
+ max = vr0.max;
+ }
+ if (int_cst_range1 && tree_int_cst_sgn (vr1.min) >= 0)
+ {
+ if (min == NULL_TREE)
+ min = build_int_cst (expr_type, 0);
+ if (max == NULL_TREE || tree_int_cst_lt (vr1.max, max))
+ max = vr1.max;
}
- 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
+ else if (!int_cst_range0
+ || !int_cst_range1
+ || tree_int_cst_sgn (vr0.min) < 0
+ || tree_int_cst_sgn (vr1.min) < 0)
{
set_value_range_to_varying (vr);
return;
}
+ else
+ {
+ min = double_int_to_tree (expr_type,
+ double_int_ior (must_be_nonzero0,
+ must_be_nonzero1));
+ max = double_int_to_tree (expr_type,
+ double_int_ior (may_be_nonzero0,
+ may_be_nonzero1));
+ if (TREE_OVERFLOW (min) || tree_int_cst_sgn (min) < 0)
+ min = vr0.min;
+ else
+ min = vrp_int_const_binop (MAX_EXPR, min, vr0.min);
+ if (TREE_OVERFLOW (max) || tree_int_cst_sgn (max) < 0)
+ max = NULL_TREE;
+ min = vrp_int_const_binop (MAX_EXPR, min, vr1.min);
+ }
}
else
gcc_unreachable ();
|| 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);
+ tree_to_double_int (vr0.min),
+ 0, false);
new_max = force_fit_type_double (outer_type,
- TREE_INT_CST_LOW (vr0.max),
- TREE_INT_CST_HIGH (vr0.max), 0, 0);
+ tree_to_double_int (vr0.max),
+ 0, false);
+ if (is_overflow_infinity (vr0.min))
+ new_min = negative_overflow_infinity (outer_type);
+ if (is_overflow_infinity (vr0.max))
+ new_max = positive_overflow_infinity (outer_type);
set_and_canonicalize_value_range (vr, vr0.type,
new_min, new_max, NULL);
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
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.
+ We are interested in the number of executions of the latch, while
+ nb_iterations_upper_bound includes the last execution of the exit test. */
+ if (TREE_CODE (step) == INTEGER_CST
+ && loop->any_upper_bound
+ && !double_int_zero_p (loop->nb_iterations_upper_bound)
+ && is_gimple_val (init)
+ && (TREE_CODE (init) != SSA_NAME
+ || get_value_range (init)->type == VR_RANGE))
+ {
+ value_range_t maxvr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+ 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),
+ double_int_sub (
+ loop->nb_iterations_upper_bound,
+ double_int_one),
+ unsigned_p, &overflow);
+ tem = double_int_to_tree (TREE_TYPE (init), dtmp);
+ /* If the multiplication overflowed we can't do a meaningful
+ adjustment. */
+ if (!overflow && double_int_equal_p (dtmp, tree_to_double_int (tem)))
+ {
+ 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;
+ min = init;
- /* Again, avoid creating invalid range by failing. */
- if (compare_values (min, max) == 1)
- return;
- }
-
- 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);
}
}
return true;
l = loop_containing_stmt (stmt);
- if (l == NULL)
+ if (l == NULL
+ || !loop_outer (l))
return true;
chrec = instantiate_parameters (l, analyze_scalar_evolution (l, var));
/* Dump value range VR to stderr. */
-void
+DEBUG_FUNCTION void
debug_value_range (value_range_t *vr)
{
dump_value_range (stderr, vr);
/* Dump all value ranges to stderr. */
-void
+DEBUG_FUNCTION void
debug_all_value_ranges (void)
{
dump_all_value_ranges (stderr);
/* 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 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;
}
edge_iterator ei;
edge e;
+ /* If we have X <=> X do not insert an assert expr for that. */
+ if (loc->expr == loc->val)
+ return false;
+
cond = build2 (loc->comp_code, boolean_type_node, loc->expr, loc->val);
assert_stmt = build_assert_expr_for (cond, name);
if (loc->e)
{
/* We have been asked to insert the assertion on an edge. This
is used only by COND_EXPR and SWITCH_EXPR assertions. */
-#if defined ENABLE_CHECKING
- gcc_assert (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);
}
}
+/* 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))))
{
- struct loop *l;
value_range_t new_vr = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
- 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);
- /* If STMT is inside a loop, we may be able to know something
- else about the range of LHS by examining scalar evolution
- information. */
- if (current_loops && (l = loop_containing_stmt (stmt)))
- adjust_range_with_scev (&new_vr, l, stmt, lhs);
-
if (update_value_range (lhs, &new_vr))
{
*output_p = lhs;
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)))
value_range_t *lhs_vr = get_value_range (lhs);
value_range_t vr_result = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
int edges, old_edges;
-
- copy_value_range (&vr_result, lhs_vr);
+ struct loop *l;
if (dump_file && (dump_flags & TDF_DETAILS))
{
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. */
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;
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_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+ value_range_t vr1 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
+ 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 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 (gimple_assign_rhs1 (stmt))))
+ return simplify_bit_ops_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;
+ unsigned num = num_ssa_names;
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; 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);
rewrite_into_loop_closed_ssa (NULL, TODO_update_ssa);
scev_initialize ();
+ /* Estimate number of iterations - but do not use undefined behavior
+ for this. We can't do this lazily as other functions may compute
+ this using undefined behavior. */
+ free_numbers_of_iterations_estimates ();
+ estimate_numbers_of_iterations (false);
+
insert_range_assertions ();
to_remove_edges = VEC_alloc (edge, heap, 10);
/* 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_verify_flow
| TODO_dump_func
- | TODO_update_ssa /* todo_flags_finish */
+ | TODO_ggc_collect /* todo_flags_finish */
}
};