/* 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
+ 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 "tree-pretty-print.h"
+#include "gimple-pretty-print.h"
+#include "diagnostic-core.h"
#include "toplev.h"
#include "intl.h"
#include "cfgloop.h"
#include "tree-chrec.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;
&& 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;
/* 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
res = int_const_binop (code, val1, val2, 0);
- /* If we are not using wrapping arithmetic, operate symbolically
- on -INF and +INF. */
- if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
+ /* If we are using unsigned arithmetic, operate symbolically
+ on -INF and +INF as int_const_binop only handles signed overflow. */
+ if (TYPE_UNSIGNED (TREE_TYPE (val1)))
{
int checkz = compare_values (res, val1);
bool overflow = false;
}
}
+ else if (TYPE_OVERFLOW_WRAPS (TREE_TYPE (val1)))
+ /* If the singed operation wraps then int_const_binop has done
+ everything we want. */
+ ;
else if ((TREE_OVERFLOW (res)
&& !TREE_OVERFLOW (val1)
&& !TREE_OVERFLOW (val2))
}
+/* 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;
}
}
}
+ /* 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, 0);
+ /* 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, 0);
+ 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,
{
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;
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;
-
- /* 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);
}
}
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
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, 0);
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);
FOR_EACH_BB (bb)
{
- /* Skip bb's that are clearly unreachable. */
- if (single_pred_p (bb))
- {
- int i;
- bool reachable = true;
- edge e2;
- edge e = EDGE_PRED (bb, 0);
- basic_block pred_bb = e->src;
- gimple ls = NULL;
-
- for (i = 0; VEC_iterate (edge, to_remove_edges, i, e2); ++i)
- if (e == e2)
- {
- reachable = false;
- break;
- }
-
- if (!reachable)
- continue;
+ edge_iterator ei;
+ edge e;
+ bool executable = false;
- if (!gsi_end_p (gsi_last_bb (pred_bb)))
- ls = gsi_stmt (gsi_last_bb (pred_bb));
+ /* Skip blocks that were found to be unreachable. */
+ FOR_EACH_EDGE (e, ei, bb->preds)
+ executable |= !!(e->flags & EDGE_EXECUTABLE);
+ if (!executable)
+ continue;
- if (ls && gimple_code (ls) == GIMPLE_COND
- && ((gimple_cond_false_p (ls)
- && (EDGE_PRED (bb, 0)->flags & EDGE_TRUE_VALUE))
- || (gimple_cond_true_p (ls)
- && (EDGE_PRED (bb, 0)->flags & EDGE_FALSE_VALUE))))
- continue;
- }
for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
{
gimple stmt = gsi_stmt (si);
&& 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)
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;
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
+ && 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;
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.
fprintf (dump_file, "removing unreachable case label\n");
}
VEC_safe_push (edge, heap, to_remove_edges, e);
+ e->flags &= ~EDGE_EXECUTABLE;
}
/* And queue an update for the stmt. */
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
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 ();
+ check_all_array_refs ();
/* We must identify jump threading opportunities before we release
the datastructures built by VRP. */
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);
OSDN Git Service
