/* Support routines for Value Range Propagation (VRP).
- Copyright (C) 2005 Free Software Foundation, Inc.
+ Copyright (C) 2005, 2006 Free Software Foundation, Inc.
Contributed by Diego Novillo <dnovillo@redhat.com>.
This file is part of GCC.
You should have received a copy of the GNU General Public License
along with GCC; see the file COPYING. If not, write to
-the Free Software Foundation, 59 Temple Place - Suite 330,
-Boston, MA 02111-1307, USA. */
+the Free Software Foundation, 51 Franklin Street, Fifth Floor,
+Boston, MA 02110-1301, USA. */
#include "config.h"
#include "system.h"
of values that SSA name N_I may take. */
static value_range_t **vr_value;
-/* Given a comparison code, return its opposite. Note that this is *not*
- the same as inverting its truth value (invert_tree_comparison). Here we
- just want to literally flip the comparison around.
-
- So, '<' gets '>', '<=' gets '>='. Both '==' and '!=' are returned
- unchanged. */
-
-static enum tree_code
-opposite_comparison (enum tree_code code)
-{
- switch (code)
- {
- case EQ_EXPR:
- case NE_EXPR:
- case ORDERED_EXPR:
- case UNORDERED_EXPR:
- case LTGT_EXPR:
- case UNEQ_EXPR:
- return code;
- case GT_EXPR:
- return LT_EXPR;
- case GE_EXPR:
- return LE_EXPR;
- case LT_EXPR:
- return GT_EXPR;
- case LE_EXPR:
- return GE_EXPR;
- case UNGT_EXPR:
- return UNLT_EXPR;
- case UNGE_EXPR:
- return UNLE_EXPR;
- case UNLT_EXPR:
- return UNGT_EXPR;
- case UNLE_EXPR:
- return UNGE_EXPR;
- default:
- gcc_unreachable ();
- }
-}
-
-
-/* Return true if EXPR computes a non-zero value. */
-
-bool
-expr_computes_nonzero (tree expr)
-{
- /* Type casts won't change anything, so just strip them. */
- STRIP_NOPS (expr);
-
- /* Calling alloca, guarantees that the value is non-NULL. */
- if (alloca_call_p (expr))
- return true;
-
- /* The address of a non-weak symbol is never NULL, unless the user
- has requested not to remove NULL pointer checks. */
- if (flag_delete_null_pointer_checks
- && TREE_CODE (expr) == ADDR_EXPR
- && DECL_P (TREE_OPERAND (expr, 0))
- && !DECL_WEAK (TREE_OPERAND (expr, 0)))
- return true;
-
- /* IOR of any value with a nonzero value will result in a nonzero
- value. */
- if (TREE_CODE (expr) == BIT_IOR_EXPR
- && integer_nonzerop (TREE_OPERAND (expr, 1)))
- return true;
-
- return false;
-}
-
/* Return true if ARG is marked with the nonnull attribute in the
current function signature. */
/* If VAR is a default definition, the variable can take any value
in VAR's type. */
sym = SSA_NAME_VAR (var);
- if (var == var_ann (sym)->default_def)
+ if (var == default_def (sym))
{
/* Try to use the "nonnull" attribute to create ~[0, 0]
anti-ranges for pointers. Note that this is only valid with
}
-/* Like expr_computes_nonzero, but this function uses value ranges
+/* Like tree_expr_nonzero_p, but this function uses value ranges
obtained so far. */
static bool
vrp_expr_computes_nonzero (tree expr)
{
- if (expr_computes_nonzero (expr))
+ if (tree_expr_nonzero_p (expr))
return true;
/* If we have an expression of the form &X->a, then the expression
if (!is_gimple_min_invariant (val1) || !is_gimple_min_invariant (val2))
return -2;
- /* We cannot compare overflowed values. */
- if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
- return -2;
-
if (!POINTER_TYPE_P (TREE_TYPE (val1)))
- return tree_int_cst_compare (val1, val2);
+ {
+ /* We cannot compare overflowed values. */
+ if (TREE_OVERFLOW (val1) || TREE_OVERFLOW (val2))
+ return -2;
+
+ return tree_int_cst_compare (val1, val2);
+ }
else
{
tree t;
/* Return 1 if VAL is inside value range VR (VR->MIN <= VAL <= VR->MAX),
0 if VAL is not inside VR,
- -2 if we cannot tell either way. */
+ -2 if we cannot tell either way.
+
+ FIXME, the current semantics of this functions are a bit quirky
+ when taken in the context of VRP. In here we do not care
+ about VR's type. If VR is the anti-range ~[3, 5] the call
+ value_inside_range (4, VR) will return 1.
+
+ This is counter-intuitive in a strict sense, but the callers
+ currently expect this. They are calling the function
+ merely to determine whether VR->MIN <= VAL <= VR->MAX. The
+ callers are applying the VR_RANGE/VR_ANTI_RANGE semantics
+ themselves.
+
+ This also applies to value_ranges_intersect_p and
+ range_includes_zero_p. The semantics of VR_RANGE and
+ VR_ANTI_RANGE should be encoded here, but that also means
+ adapting the users of these functions to the new semantics. */
static inline int
value_inside_range (tree val, value_range_t *vr)
}
-/* Return true if VR includes the value zero, false otherwise. */
+/* Return true if VR includes the value zero, false otherwise. FIXME,
+ currently this will return false for an anti-range like ~[-4, 3].
+ This will be wrong when the semantics of value_inside_range are
+ modified (currently the users of this function expect these
+ semantics). */
static inline bool
range_includes_zero_p (value_range_t *vr)
}
+/* When extracting ranges from X_i = ASSERT_EXPR <Y_j, pred>, we will
+ initially consider X_i and Y_j equivalent, so the equivalence set
+ of Y_j is added to the equivalence set of X_i. However, it is
+ possible to have a chain of ASSERT_EXPRs whose predicates are
+ actually incompatible. This is usually the result of nesting of
+ contradictory if-then-else statements. For instance, in PR 24670:
+
+ count_4 has range [-INF, 63]
+
+ if (count_4 != 0)
+ {
+ count_19 = ASSERT_EXPR <count_4, count_4 != 0>
+ if (count_19 > 63)
+ {
+ count_18 = ASSERT_EXPR <count_19, count_19 > 63>
+ if (count_18 <= 63)
+ ...
+ }
+ }
+
+ Notice that 'if (count_19 > 63)' is trivially false and will be
+ folded out at the end. However, during propagation, the flowgraph
+ is not cleaned up and so, VRP will evaluate predicates more
+ predicates than necessary, so it must support these
+ inconsistencies. The problem here is that because of the chaining
+ of ASSERT_EXPRs, the equivalency set for count_18 includes count_4.
+ Since count_4 has an incompatible range, we ICE when evaluating the
+ ranges in the equivalency set. So, we need to remove count_4 from
+ it. */
+
+static void
+fix_equivalence_set (value_range_t *vr_p)
+{
+ bitmap_iterator bi;
+ unsigned i;
+ bitmap e = vr_p->equiv;
+ bitmap to_remove = BITMAP_ALLOC (NULL);
+
+ /* Only detect inconsistencies on numeric ranges. */
+ if (vr_p->type == VR_VARYING
+ || vr_p->type == VR_UNDEFINED
+ || symbolic_range_p (vr_p))
+ return;
+
+ EXECUTE_IF_SET_IN_BITMAP (e, 0, i, bi)
+ {
+ value_range_t *equiv_vr = vr_value[i];
+
+ if (equiv_vr->type == VR_VARYING
+ || equiv_vr->type == VR_UNDEFINED
+ || symbolic_range_p (equiv_vr))
+ continue;
+
+ if (equiv_vr->type == VR_RANGE
+ && vr_p->type == VR_RANGE
+ && !value_ranges_intersect_p (vr_p, equiv_vr))
+ bitmap_set_bit (to_remove, i);
+ else if ((equiv_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
+ || (equiv_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
+ {
+ /* A range and an anti-range have an empty intersection if
+ their end points are the same. FIXME,
+ value_ranges_intersect_p should handle this
+ automatically. */
+ if (compare_values (equiv_vr->min, vr_p->min) == 0
+ && compare_values (equiv_vr->max, vr_p->max) == 0)
+ bitmap_set_bit (to_remove, i);
+ }
+ }
+
+ bitmap_and_compl_into (vr_p->equiv, to_remove);
+ BITMAP_FREE (to_remove);
+}
+
+
/* Extract value range information from an ASSERT_EXPR EXPR and store
it in *VR_P. */
to flip around the comparison code to create the proper range
for VAR. */
limit = TREE_OPERAND (cond, 0);
- cond_code = opposite_comparison (TREE_CODE (cond));
+ cond_code = swap_tree_comparison (TREE_CODE (cond));
}
type = TREE_TYPE (limit);
}
}
- /* The new range has the same set of equivalences of VAR's range. */
+ /* Initially, the new range has the same set of equivalences of
+ VAR's range. This will be revised before returning the final
+ value. Since assertions may be chained via mutually exclusive
+ predicates, we will need to trim the set of equivalences before
+ we are done. */
gcc_assert (vr_p->equiv == NULL);
vr_p->equiv = BITMAP_ALLOC (NULL);
add_equivalence (vr_p->equiv, var);
LIMIT's range was ~[0, 0], the assertion 'VAR != LIMIT' does
not imply that VAR's range is [0, 0]. So, in the case of
anti-ranges, we just assert the inequality using LIMIT and
- not its anti-range. */
- if (limit_vr == NULL
- || limit_vr->type == VR_ANTI_RANGE)
+ not its anti-range.
+
+ If LIMIT_VR is a range, we can only use it to build a new
+ anti-range if LIMIT_VR is a single-valued range. For
+ instance, if LIMIT_VR is [0, 1], the predicate
+ VAR != [0, 1] does not mean that VAR's range is ~[0, 1].
+ Rather, it means that for value 0 VAR should be ~[0, 0]
+ and for value 1, VAR should be ~[1, 1]. We cannot
+ represent these ranges.
+
+ The only situation in which we can build a valid
+ anti-range is when LIMIT_VR is a single-valued range
+ (i.e., LIMIT_VR->MIN == LIMIT_VR->MAX). In that case,
+ build the anti-range ~[LIMIT_VR->MIN, LIMIT_VR->MAX]. */
+ if (limit_vr
+ && limit_vr->type == VR_RANGE
+ && compare_values (limit_vr->min, limit_vr->max) == 0)
{
- min = limit;
- max = limit;
+ min = limit_vr->min;
+ max = limit_vr->max;
}
else
{
- min = limit_vr->min;
- max = limit_vr->max;
+ /* In any other case, we cannot use LIMIT's range to build a
+ valid anti-range. */
+ min = max = limit;
}
/* If MIN and MAX cover the whole range for their type, then
if (cond_code == LT_EXPR)
{
tree one = build_int_cst (type, 1);
- max = fold (build (MINUS_EXPR, type, max, one));
+ max = fold_build2 (MINUS_EXPR, type, max, one);
}
set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
if (cond_code == GT_EXPR)
{
tree one = build_int_cst (type, 1);
- min = fold (build (PLUS_EXPR, type, min, one));
+ min = fold_build2 (PLUS_EXPR, type, min, one);
}
set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
else
gcc_unreachable ();
- /* If VAR already had a known range and 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 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);
- if (var_vr->type == VR_RANGE
- && vr_p->type == VR_RANGE
- && value_ranges_intersect_p (var_vr, vr_p))
+
+ /* 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))
+ goto done;
+
+ if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
{
- /* 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;
+ /* 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;
+ /* 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);
+ 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);
}
+
+ /* Remove names from the equivalence set that have ranges
+ incompatible with VR_P. */
+done:
+ fix_equivalence_set (vr_p);
}
}
+/* Wrapper around int_const_binop. If the operation overflows and we
+ are not using wrapping arithmetic, then adjust the result to be
+ -INF or +INF depending on CODE, VAL1 and VAL2. */
+
+static inline tree
+vrp_int_const_binop (enum tree_code code, tree val1, tree val2)
+{
+ tree res;
+
+ if (flag_wrapv)
+ return int_const_binop (code, val1, val2, 0);
+
+ /* If we are not using wrapping arithmetic, operate symbolically
+ on -INF and +INF. */
+ res = int_const_binop (code, val1, val2, 0);
+
+ if (TYPE_UNSIGNED (TREE_TYPE (val1)))
+ {
+ int checkz = compare_values (res, val1);
+
+ /* Ensure that res = val1 + val2 >= val1
+ or that res = val1 - val2 <= val1. */
+ if ((code == PLUS_EXPR && !(checkz == 1 || checkz == 0))
+ || (code == MINUS_EXPR && !(checkz == 0 || checkz == -1)))
+ {
+ res = copy_node (res);
+ TREE_OVERFLOW (res) = 1;
+ }
+ }
+ /* If the operation overflowed but neither VAL1 nor VAL2 are
+ overflown, return -INF or +INF depending on the operation
+ and the combination of signs of the operands. */
+ else if (TREE_OVERFLOW (res)
+ && !TREE_OVERFLOW (val1)
+ && !TREE_OVERFLOW (val2))
+ {
+ int sgn1 = tree_int_cst_sgn (val1);
+ int sgn2 = tree_int_cst_sgn (val2);
+
+ /* Notice that we only need to handle the restricted set of
+ operations handled by extract_range_from_binary_expr.
+ Among them, only multiplication, addition and subtraction
+ can yield overflow without overflown operands because we
+ are working with integral types only... except in the
+ case VAL1 = -INF and VAL2 = -1 which overflows to +INF
+ for division too. */
+
+ /* For multiplication, the sign of the overflow is given
+ by the comparison of the signs of the operands. */
+ if ((code == MULT_EXPR && sgn1 == sgn2)
+ /* For addition, the operands must be of the same sign
+ to yield an overflow. Its sign is therefore that
+ of one of the operands, for example the first. */
+ || (code == PLUS_EXPR && sgn1 > 0)
+ /* For subtraction, the operands must be of different
+ signs to yield an overflow. Its sign is therefore
+ that of the first operand or the opposite of that
+ of the second operand. A first operand of 0 counts
+ as positive here, for the corner case 0 - (-INF),
+ which overflows, but must yield +INF. */
+ || (code == MINUS_EXPR && sgn1 >= 0)
+ /* For division, the only case is -INF / -1 = +INF. */
+ || code == TRUNC_DIV_EXPR
+ || code == FLOOR_DIV_EXPR
+ || code == CEIL_DIV_EXPR
+ || code == EXACT_DIV_EXPR
+ || code == ROUND_DIV_EXPR)
+ return TYPE_MAX_VALUE (TREE_TYPE (res));
+ else
+ return TYPE_MIN_VALUE (TREE_TYPE (res));
+ }
+
+ return res;
+}
+
+
/* Extract range information from a binary expression EXPR based on
the ranges of each of its operands and the expression code. */
extract_range_from_binary_expr (value_range_t *vr, tree expr)
{
enum tree_code code = TREE_CODE (expr);
+ enum value_range_type type;
tree op0, op1, min, max;
int cmp;
value_range_t vr0 = { VR_UNDEFINED, NULL_TREE, NULL_TREE, NULL };
&& code != ROUND_DIV_EXPR
&& code != MIN_EXPR
&& code != MAX_EXPR
+ && code != BIT_AND_EXPR
&& code != TRUTH_ANDIF_EXPR
&& code != TRUTH_ORIF_EXPR
&& code != TRUTH_AND_EXPR
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
- and symbolic ranges. TODO, we may be able to derive anti-ranges
- in some cases. */
- if (vr0.type == VR_VARYING
- || vr1.type == VR_VARYING
- || vr0.type != vr1.type
- || symbolic_range_p (&vr0)
- || symbolic_range_p (&vr1))
+ and symbolic ranges. As an exception, we allow BIT_AND_EXPR
+ because we may be able to derive a useful range even if one of
+ the operands is VR_VARYING or symbolic range. 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
+ && (vr0.type == VR_VARYING
+ || vr1.type == VR_VARYING
+ || vr0.type != vr1.type
+ || symbolic_range_p (&vr0)
+ || symbolic_range_p (&vr1)))
{
set_value_range_to_varying (vr);
return;
ivopts is generating expressions with pointer multiplication
in them. */
if (code == PLUS_EXPR)
- set_value_range_to_nonnull (vr, TREE_TYPE (expr));
+ {
+ if (range_is_nonnull (&vr0) || range_is_nonnull (&vr1))
+ set_value_range_to_nonnull (vr, TREE_TYPE (expr));
+ else if (range_is_null (&vr0) && range_is_null (&vr1))
+ set_value_range_to_null (vr, TREE_TYPE (expr));
+ else
+ set_value_range_to_varying (vr);
+ }
else
{
/* Subtracting from a pointer, may yield 0, so just drop the
|| code == TRUTH_OR_EXPR
|| code == TRUTH_XOR_EXPR)
{
- /* Boolean expressions cannot be folded with int_const_binop. */
- min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min);
- max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
+ /* 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 (TREE_TYPE (expr), 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 (TREE_TYPE (expr), 1);
+ }
+ else if (vr0.type != VR_VARYING
+ && vr1.type != VR_VARYING
+ && vr0.type == vr1.type
+ && !symbolic_range_p (&vr0)
+ && !symbolic_range_p (&vr1))
+ {
+ /* Boolean expressions cannot be folded with int_const_binop. */
+ min = fold_binary (code, TREE_TYPE (expr), vr0.min, vr1.min);
+ max = fold_binary (code, TREE_TYPE (expr), vr0.max, vr1.max);
+ }
+ else
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
}
else if (code == PLUS_EXPR
- || code == MULT_EXPR
|| code == MIN_EXPR
|| code == MAX_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
+ range for such a case. For example, if we have op0 == 1 and
+ op1 == -1 with their ranges both being ~[0,0], we would have
+ 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)
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
/* For operations that make the resulting range directly
proportional to the original ranges, apply the operation to
the same end of each range. */
- min = int_const_binop (code, vr0.min, vr1.min, 0);
- max = int_const_binop (code, vr0.max, vr1.max, 0);
+ min = vrp_int_const_binop (code, vr0.min, vr1.min);
+ max = vrp_int_const_binop (code, vr0.max, vr1.max);
}
- else if (code == TRUNC_DIV_EXPR
+ 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)
{
- tree zero;
-
- /* Divisions are a bit tricky to handle, depending on the mix of
- signs we have in the two range, we will need to divide
- different values to get the minimum and maximum values for
- the new range. If VR1 includes zero, the result is VARYING. */
- if (range_includes_zero_p (&vr1))
+ tree val[4];
+ size_t i;
+
+ /* 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
+ op0 == 65536 and op1 == 65536 with their ranges both being
+ ~[0,0] on a 32-bit machine, we would have op0 * op1 == 0, so
+ 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
+ && (flag_wrapv || TYPE_UNSIGNED (TREE_TYPE (op0))))
{
set_value_range_to_varying (vr);
return;
}
- /* We have three main variations to handle for VR0: all negative
- values, all positive values and a mix of negative and
- positive. For each of these, we need to consider if VR1 is
- all negative or all positive. In total, there are 6
- combinations to handle. */
- zero = build_int_cst (TREE_TYPE (expr), 0);
- if (compare_values (vr0.max, zero) == -1)
- {
- /* VR0 is all negative. */
- if (compare_values (vr1.min, zero) == 1)
- {
- /* If VR1 is all positive, the new range is obtained
- with [VR0.MIN / VR1.MIN, VR0.MAX / VR1.MAX]. */
- min = int_const_binop (code, vr0.min, vr1.min, 0);
- max = int_const_binop (code, vr0.max, vr1.max, 0);
- }
- else
- {
- /* If VR1 is all negative, the new range is obtained
- with [VR0.MAX / VR1.MIN, VR0.MIN / VR1.MAX]. */
- gcc_assert (compare_values (vr1.max, zero) == -1);
- min = int_const_binop (code, vr0.max, vr1.min, 0);
- max = int_const_binop (code, vr0.min, vr1.max, 0);
- }
- }
- else if (range_includes_zero_p (&vr0))
+ /* 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. */
+
+ /* Divisions by zero result in a VARYING value. */
+ if (code != MULT_EXPR
+ && (vr0.type == VR_ANTI_RANGE || range_includes_zero_p (&vr1)))
{
- /* VR0 is a mix of negative and positive values. */
- if (compare_values (vr1.min, zero) == 1)
- {
- /* If VR1 is all positive, the new range is obtained
- with [VR0.MIN / VR1.MIN, VR0.MAX / VR1.MIN]. */
- min = int_const_binop (code, vr0.min, vr1.min, 0);
- max = int_const_binop (code, vr0.max, vr1.min, 0);
- }
- else
- {
- /* If VR1 is all negative, the new range is obtained
- with [VR0.MAX / VR1.MAX, VR0.MIN / VR1.MAX]. */
- gcc_assert (compare_values (vr1.max, zero) == -1);
- min = int_const_binop (code, vr0.max, vr1.max, 0);
- max = int_const_binop (code, vr0.min, vr1.max, 0);
- }
+ set_value_range_to_varying (vr);
+ return;
}
- else
+
+ /* Compute the 4 cross operations. */
+ val[0] = vrp_int_const_binop (code, vr0.min, vr1.min);
+
+ val[1] = (vr1.max != vr1.min)
+ ? vrp_int_const_binop (code, vr0.min, vr1.max)
+ : NULL_TREE;
+
+ val[2] = (vr0.max != vr0.min)
+ ? vrp_int_const_binop (code, vr0.max, vr1.min)
+ : NULL_TREE;
+
+ val[3] = (vr0.min != vr0.max && vr1.min != vr1.max)
+ ? vrp_int_const_binop (code, vr0.max, vr1.max)
+ : NULL_TREE;
+
+ /* 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++)
{
- /* VR0 is all positive. */
- gcc_assert (compare_values (vr0.min, zero) == 1);
- if (compare_values (vr1.min, zero) == 1)
- {
- /* If VR1 is all positive, the new range is obtained
- with [VR0.MIN / VR1.MAX, VR0.MAX / VR1.MIN]. */
- min = int_const_binop (code, vr0.min, vr1.max, 0);
- max = int_const_binop (code, vr0.max, vr1.min, 0);
- }
- else
+ if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min)
+ || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max))
+ break;
+
+ if (val[i])
{
- /* If VR1 is all negative, the new range is obtained
- with [VR0.MAX / VR1.MAX, VR0.MIN / VR1.MIN]. */
- gcc_assert (compare_values (vr1.max, zero) == -1);
- min = int_const_binop (code, vr0.max, vr1.max, 0);
- max = int_const_binop (code, vr0.min, vr1.min, 0);
+ if (!is_gimple_min_invariant (val[i]) || TREE_OVERFLOW (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];
}
}
}
else if (code == MINUS_EXPR)
{
- /* For MINUS_EXPR, apply the operation to the opposite ends of
- each range. */
- min = int_const_binop (code, vr0.min, vr1.max, 0);
- max = int_const_binop (code, vr0.max, vr1.min, 0);
- }
- else
- gcc_unreachable ();
-
- /* If MAX overflowed, then the result depends on whether we are
- using wrapping arithmetic or not. */
- if (TREE_OVERFLOW (max))
- {
- /* If we are using wrapping arithmetic, set the result to
- VARYING. */
- if (flag_wrapv)
+ /* If we have a MINUS_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 op0 == 1 and
+ op1 == 1 with their ranges both being ~[0,0], we would have
+ op0 - op1 == 0, so we cannot claim that the difference is in
+ ~[0,0]. Note that we are guaranteed to have
+ vr0.type == vr1.type at this point. */
+ if (vr0.type == VR_ANTI_RANGE)
{
set_value_range_to_varying (vr);
return;
}
- /* Otherwise, set MAX to +INF. */
- max = TYPE_MAX_VALUE (TREE_TYPE (expr));
+ /* For MINUS_EXPR, apply the operation to the opposite ends of
+ each range. */
+ min = vrp_int_const_binop (code, vr0.min, vr1.max);
+ max = vrp_int_const_binop (code, vr0.max, vr1.min);
}
-
- /* If MIN overflowed, then the result depends on whether we are
- using wrapping arithmetic or not. */
- if (TREE_OVERFLOW (min))
+ else if (code == BIT_AND_EXPR)
{
- /* If we are using wrapping arithmetic, set the result to
- VARYING. */
- if (flag_wrapv)
+ if (vr0.type == VR_RANGE
+ && vr0.min == vr0.max
+ && tree_expr_nonnegative_p (vr0.max)
+ && TREE_CODE (vr0.max) == INTEGER_CST)
+ {
+ min = build_int_cst (TREE_TYPE (expr), 0);
+ max = vr0.max;
+ }
+ else if (vr1.type == VR_RANGE
+ && vr1.min == vr1.max
+ && tree_expr_nonnegative_p (vr1.max)
+ && TREE_CODE (vr1.max) == INTEGER_CST)
+ {
+ type = VR_RANGE;
+ min = build_int_cst (TREE_TYPE (expr), 0);
+ max = vr1.max;
+ }
+ else
{
set_value_range_to_varying (vr);
return;
}
+ }
+ else
+ gcc_unreachable ();
- /* Otherwise, set MIN to -INF. */
- min = TYPE_MIN_VALUE (TREE_TYPE (expr));
+ /* If either MIN or MAX overflowed, then set the resulting range to
+ VARYING. */
+ if (!is_gimple_min_invariant (min) || TREE_OVERFLOW (min)
+ || !is_gimple_min_invariant (max) || TREE_OVERFLOW (max))
+ {
+ set_value_range_to_varying (vr);
+ return;
}
cmp = compare_values (min, max);
set_value_range_to_varying (vr);
}
else
- set_value_range (vr, vr0.type, min, max, NULL);
+ set_value_range (vr, type, min, max, NULL);
}
/* Refuse to operate on varying and symbolic ranges. Also, if the
operand is neither a pointer nor an integral type, set the
resulting range to VARYING. TODO, in some cases we may be able
- to derive anti-ranges (like non-zero values). */
+ to derive anti-ranges (like nonzero values). */
if (vr0.type == VR_VARYING
|| (!INTEGRAL_TYPE_P (TREE_TYPE (op0))
&& !POINTER_TYPE_P (TREE_TYPE (op0)))
determining if it evaluates to NULL [0, 0] or non-NULL (~[0, 0]). */
if (POINTER_TYPE_P (TREE_TYPE (expr)) || POINTER_TYPE_P (TREE_TYPE (op0)))
{
- if (range_is_nonnull (&vr0) || expr_computes_nonzero (expr))
+ if (range_is_nonnull (&vr0) || tree_expr_nonzero_p (expr))
set_value_range_to_nonnull (vr, TREE_TYPE (expr));
else if (range_is_null (&vr0))
set_value_range_to_null (vr, TREE_TYPE (expr));
tree inner_type = TREE_TYPE (op0);
tree outer_type = TREE_TYPE (expr);
+ /* If VR0 represents a simple range, then try to convert
+ the min and max values for the range to the same type
+ as OUTER_TYPE. If the results compare equal to VR0's
+ min and max values and the new min is still less than
+ or equal to the new max, then we can safely use the newly
+ computed range for EXPR. This allows us to compute
+ accurate ranges through many casts. */
+ if (vr0.type == VR_RANGE)
+ {
+ tree new_min, new_max;
+
+ /* Convert VR0's min/max to OUTER_TYPE. */
+ new_min = fold_convert (outer_type, vr0.min);
+ new_max = fold_convert (outer_type, vr0.max);
+
+ /* Verify the new min/max values are gimple values and
+ that they compare equal to VR0's min/max values. */
+ if (is_gimple_val (new_min)
+ && is_gimple_val (new_max)
+ && tree_int_cst_equal (new_min, vr0.min)
+ && tree_int_cst_equal (new_max, vr0.max)
+ && compare_values (new_min, new_max) <= 0
+ && compare_values (new_min, new_max) >= -1)
+ {
+ set_value_range (vr, VR_RANGE, new_min, new_max, vr->equiv);
+ return;
+ }
+ }
+
/* When converting types of different sizes, set the result to
VARYING. Things like sign extensions and precision loss may
change the range. For instance, if x_3 is of type 'long long
if (code == NEGATE_EXPR
&& !TYPE_UNSIGNED (TREE_TYPE (expr)))
{
- /* Negating an anti-range doesn't really do anything to it. The
- new range will also not take on the same range of values
- excluded by the original anti-range. */
- if (vr0.type == VR_ANTI_RANGE)
- {
- copy_value_range (vr, &vr0);
- return;
- }
-
/* NEGATE_EXPR flips the range around. */
- min = (vr0.max == TYPE_MAX_VALUE (TREE_TYPE (expr)))
- ? TYPE_MIN_VALUE (TREE_TYPE (expr))
- : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
+ min = (vr0.max == TYPE_MAX_VALUE (TREE_TYPE (expr)) && !flag_wrapv)
+ ? TYPE_MIN_VALUE (TREE_TYPE (expr))
+ : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
- max = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
- ? TYPE_MAX_VALUE (TREE_TYPE (expr))
- : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
+ max = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)) && !flag_wrapv)
+ ? TYPE_MAX_VALUE (TREE_TYPE (expr))
+ : fold_unary_to_constant (code, TREE_TYPE (expr), vr0.min);
}
else if (code == ABS_EXPR
&& !TYPE_UNSIGNED (TREE_TYPE (expr)))
{
+ /* -TYPE_MIN_VALUE = TYPE_MIN_VALUE with flag_wrapv so we can't get a
+ useful range. */
+ if (flag_wrapv
+ && ((vr0.type == VR_RANGE
+ && vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
+ || (vr0.type == VR_ANTI_RANGE
+ && vr0.min != TYPE_MIN_VALUE (TREE_TYPE (expr))
+ && !range_includes_zero_p (&vr0))))
+ {
+ set_value_range_to_varying (vr);
+ return;
+ }
+
/* ABS_EXPR may flip the range around, if the original range
included negative values. */
min = (vr0.min == TYPE_MIN_VALUE (TREE_TYPE (expr)))
max = fold_unary_to_constant (code, TREE_TYPE (expr), vr0.max);
- /* If the range was reversed, swap MIN and MAX. */
- if (compare_values (min, max) == 1)
+ cmp = compare_values (min, max);
+
+ /* If a VR_ANTI_RANGEs contains zero, then we have
+ ~[-INF, min(MIN, MAX)]. */
+ if (vr0.type == VR_ANTI_RANGE)
+ {
+ if (range_includes_zero_p (&vr0))
+ {
+ tree type_min_value = TYPE_MIN_VALUE (TREE_TYPE (expr));
+
+ /* Take the lower of the two values. */
+ if (cmp != 1)
+ max = min;
+
+ /* Create ~[-INF, min (abs(MIN), abs(MAX))]
+ or ~[-INF + 1, min (abs(MIN), abs(MAX))] when
+ flag_wrapv is set and the original anti-range doesn't include
+ TYPE_MIN_VALUE, remember -TYPE_MIN_VALUE = TYPE_MIN_VALUE. */
+ min = (flag_wrapv && vr0.min != type_min_value
+ ? int_const_binop (PLUS_EXPR,
+ type_min_value,
+ integer_one_node, 0)
+ : type_min_value);
+ }
+ else
+ {
+ /* All else has failed, so create the range [0, INF], even for
+ flag_wrapv since TYPE_MIN_VALUE is in the original
+ anti-range. */
+ vr0.type = VR_RANGE;
+ min = build_int_cst (TREE_TYPE (expr), 0);
+ max = TYPE_MAX_VALUE (TREE_TYPE (expr));
+ }
+ }
+
+ /* If the range contains zero then we know that the minimum value in the
+ range will be zero. */
+ else if (range_includes_zero_p (&vr0))
{
- tree t = min;
- min = max;
- max = t;
+ if (cmp == 1)
+ max = min;
+ min = build_int_cst (TREE_TYPE (expr), 0);
+ }
+ else
+ {
+ /* If the range was reversed, swap MIN and MAX. */
+ if (cmp == 1)
+ {
+ tree t = min;
+ min = max;
+ max = t;
+ }
}
}
else
extract_range_from_unary_expr (vr, expr);
else if (TREE_CODE_CLASS (code) == tcc_comparison)
extract_range_from_comparison (vr, expr);
- else if (vrp_expr_computes_nonzero (expr))
- set_value_range_to_nonnull (vr, TREE_TYPE (expr));
else if (is_gimple_min_invariant (expr))
set_value_range (vr, VR_RANGE, expr, expr, NULL);
+ else if (vrp_expr_computes_nonzero (expr))
+ set_value_range_to_nonnull (vr, TREE_TYPE (expr));
else
set_value_range_to_varying (vr);
}
tree var)
{
tree init, step, chrec;
- bool init_is_max;
+ bool init_is_max, unknown_max;
/* TODO. Don't adjust anti-ranges. An anti-range may provide
better opportunities than a regular range, but I'm not sure. */
if (vr->type == VR_ANTI_RANGE)
return;
- chrec = analyze_scalar_evolution (loop, var);
+ chrec = instantiate_parameters (loop, analyze_scalar_evolution (loop, var));
if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
return;
- init = CHREC_LEFT (chrec);
- step = CHREC_RIGHT (chrec);
+ init = initial_condition_in_loop_num (chrec, loop->num);
+ step = evolution_part_in_loop_num (chrec, loop->num);
/* If STEP is symbolic, we can't know whether INIT will be the
minimum or maximum value in the range. */
- if (!is_gimple_min_invariant (step))
+ if (step == NULL_TREE
+ || !is_gimple_min_invariant (step))
return;
/* Do not adjust ranges when chrec may wrap. */
if (scev_probably_wraps_p (chrec_type (chrec), init, step, stmt,
cfg_loops->parray[CHREC_VARIABLE (chrec)],
- &init_is_max))
+ &init_is_max, &unknown_max)
+ || unknown_max)
return;
if (!POINTER_TYPE_P (TREE_TYPE (init))
else if (cmp_min != -2 && cmp_max != -2)
return boolean_false_node;
}
+ /* If [V0_MIN, V1_MAX] < [V1_MIN, V1_MAX] then V0 != V1. */
+ else if (compare_values (vr0->min, vr1->max) == 1
+ || compare_values (vr1->min, vr0->max) == 1)
+ return boolean_false_node;
return NULL_TREE;
}
|| comp == LE_EXPR)
return NULL_TREE;
- /* ~[VAL, VAL] == VAL is always false. */
- if (compare_values (vr->min, val) == 0
- && compare_values (vr->max, val) == 0)
+ /* ~[VAL_1, VAL_2] OP VAL is known if VAL_1 <= VAL <= VAL_2. */
+ if (value_inside_range (val, vr) == 1)
return (comp == NE_EXPR) ? boolean_true_node : boolean_false_node;
return NULL_TREE;
if (COMPARISON_CLASS_P (cond))
{
- tree a = build (ASSERT_EXPR, TREE_TYPE (v), v, cond);
- assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, a);
+ tree a = build2 (ASSERT_EXPR, TREE_TYPE (v), v, cond);
+ assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), 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 = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
+ assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_false_node);
}
else if (TREE_CODE (cond) == SSA_NAME)
{
/* Given V, build the assignment N = true. */
gcc_assert (v == cond);
- assertion = build (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
+ assertion = build2 (MODIFY_EXPR, TREE_TYPE (v), n, boolean_true_node);
}
else
gcc_unreachable ();
if (tree_could_throw_p (stmt))
return false;
+ /* If STMT is the last statement of a basic block with no
+ successors, there is no point inferring anything about any of its
+ operands. We would not be able to find a proper insertion point
+ for the assertion, anyway. */
+ if (stmt_ends_bb_p (stmt) && EDGE_COUNT (bb_for_stmt (stmt)->succs) == 0)
+ return false;
+
if (POINTER_TYPE_P (TREE_TYPE (op)))
{
bool is_store;
/* Try to register an edge assertion for SSA name NAME on edge E for
- the conditional jump pointed by SI. Return true if an assertion
+ the conditional jump pointed to by SI. Return true if an assertion
for NAME could be registered. */
static bool
/* If the predicate is of the form VAL COMP NAME, flip
COMP around because we need to register NAME as the
first operand in the predicate. */
- comp_code = opposite_comparison (TREE_CODE (cond));
+ comp_code = swap_tree_comparison (TREE_CODE (cond));
val = TREE_OPERAND (cond, 0);
}
else
need to invert the sign comparison. */
if (is_else_edge)
comp_code = invert_tree_comparison (comp_code, 0);
+
+ /* Do not register always-false predicates. FIXME, this
+ works around a limitation in fold() when dealing with
+ enumerations. Given 'enum { N1, N2 } x;', fold will not
+ fold 'if (x > N2)' to 'if (0)'. */
+ if ((comp_code == GT_EXPR || comp_code == LT_EXPR)
+ && (INTEGRAL_TYPE_P (TREE_TYPE (val))
+ || SCALAR_FLOAT_TYPE_P (TREE_TYPE (val))))
+ {
+ tree min = TYPE_MIN_VALUE (TREE_TYPE (val));
+ tree max = TYPE_MAX_VALUE (TREE_TYPE (val));
+
+ if (comp_code == GT_EXPR && compare_values (val, max) == 0)
+ return false;
+
+ if (comp_code == LT_EXPR && compare_values (val, min) == 0)
+ return false;
+ }
}
}
else
edge_iterator ei;
edge e;
- cond = build (loc->comp_code, boolean_type_node, name, loc->val);
+ cond = build2 (loc->comp_code, boolean_type_node, name, loc->val);
assert_expr = build_assert_expr_for (cond, name);
if (loc->e)
}
-/* Convert range assertion expressions into the implied copies.
+/* Convert range assertion expressions into the implied copies and
+ copy propagate away the copies. Doing the trivial copy propagation
+ here avoids the need to run the full copy propagation pass after
+ VRP.
FIXME, this will eventually lead to copy propagation removing the
names that had useful range information attached to them. For
things like jump threading.
The problem with keeping ASSERT_EXPRs around is that passes after
- VRP need to handle them appropriately. */
+ VRP need to handle them appropriately.
+
+ Another approach would be to make the range information a first
+ class property of the SSA_NAME so that it can be queried from
+ any pass. This is made somewhat more complex by the need for
+ multiple ranges to be associated with one SSA_NAME. */
static void
remove_range_assertions (void)
basic_block bb;
block_stmt_iterator si;
+ /* Note that the BSI iterator bump happens at the bottom of the
+ loop and no bump is necessary if we're removing the statement
+ referenced by the current BSI. */
FOR_EACH_BB (bb)
- for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+ for (si = bsi_start (bb); !bsi_end_p (si);)
{
tree stmt = bsi_stmt (si);
{
tree rhs = TREE_OPERAND (stmt, 1);
tree cond = fold (ASSERT_EXPR_COND (rhs));
+ use_operand_p use_p;
+ imm_use_iterator iter;
+
gcc_assert (cond != boolean_false_node);
TREE_OPERAND (stmt, 1) = ASSERT_EXPR_VAR (rhs);
update_stmt (stmt);
+
+ /* The statement is now a copy. Propagate the RHS into
+ every use of the LHS. */
+ FOR_EACH_IMM_USE_SAFE (use_p, iter, TREE_OPERAND (stmt, 0))
+ {
+ SET_USE (use_p, ASSERT_EXPR_VAR (rhs));
+ update_stmt (USE_STMT (use_p));
+ }
+
+ /* And finally, remove the copy, it is not needed. */
+ bsi_remove (&si, true);
}
+ else
+ bsi_next (&si);
}
+
+ sbitmap_free (blocks_visited);
}
}
-/* Initialize local data structures for VRP. Return true if VRP
- is worth running (i.e. if we found any statements that could
- benefit from range information). */
+/* Initialize local data structures for VRP. */
static void
vrp_initialize (void)
return compare_name_with_value (TREE_CODE (cond), op0, op1);
else if (TREE_CODE (op1) == SSA_NAME)
return compare_name_with_value (
- opposite_comparison (TREE_CODE (cond)), op1, op0);
+ swap_tree_comparison (TREE_CODE (cond)), op1, op0);
}
else
{
return compare_range_with_value (TREE_CODE (cond), vr0, op1);
else if (vr0 == NULL && vr1)
return compare_range_with_value (
- opposite_comparison (TREE_CODE (cond)), vr1, op0);
+ swap_tree_comparison (TREE_CODE (cond)), vr1, op0);
}
}
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);
}
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);
}
else
goto no_meet;
&& !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)
- copy_value_range (vr0, vr1);
+ set_value_range (vr0, vr1->type, vr1->min, vr1->max, vr0->equiv);
+
+ /* 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);
}
else
goto no_meet;
no_meet:
/* The two range VR0 and VR1 do not meet. Before giving up and
setting the result to VARYING, see if we can at least derive a
- useful anti-range. */
+ useful anti-range. FIXME, all this nonsense about distinguishing
+ anti-ranges from ranges is necessary because of the odd
+ semantics of range_includes_zero_p and friends. */
if (!symbolic_range_p (vr0)
- && !range_includes_zero_p (vr0)
+ && ((vr0->type == VR_RANGE && !range_includes_zero_p (vr0))
+ || (vr0->type == VR_ANTI_RANGE && range_includes_zero_p (vr0)))
&& !symbolic_range_p (vr1)
- && !range_includes_zero_p (vr1))
- set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min));
+ && ((vr1->type == VR_RANGE && !range_includes_zero_p (vr1))
+ || (vr1->type == VR_ANTI_RANGE && range_includes_zero_p (vr1))))
+ {
+ set_value_range_to_nonnull (vr0, TREE_TYPE (vr0->min));
+
+ /* Since this meet operation did not result from the meeting of
+ two equivalent names, VR0 cannot have any equivalences. */
+ if (vr0->equiv)
+ bitmap_clear (vr0->equiv);
+ }
else
set_value_range_to_varying (vr0);
}
/* To prevent infinite iterations in the algorithm, derive ranges
when the new value is slightly bigger or smaller than the
previous one. */
- if (lhs_vr->type == VR_RANGE)
+ if (lhs_vr->type == VR_RANGE && vr_result.type == VR_RANGE)
{
if (!POINTER_TYPE_P (TREE_TYPE (lhs)))
{
return SSA_PROP_VARYING;
}
-/* Walk through the IL simplifying expressions using knowledge
- gathered by VRP. */
+/* Simplify a division or modulo operator to a right shift or
+ bitwise and if the first operand is unsigned or is greater
+ than zero and the second operand is an exact power of two. */
static void
-simplify_using_ranges (void)
+simplify_div_or_mod_using_ranges (tree stmt, tree rhs, enum tree_code rhs_code)
{
- basic_block bb;
+ tree val = NULL;
+ tree op = TREE_OPERAND (rhs, 0);
+ value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
- FOR_EACH_BB (bb)
+ if (TYPE_UNSIGNED (TREE_TYPE (op)))
+ {
+ val = integer_one_node;
+ }
+ else
+ {
+ val = compare_range_with_value (GT_EXPR, vr, integer_zero_node);
+ }
+
+ if (val && integer_onep (val))
+ {
+ tree t;
+ tree op0 = TREE_OPERAND (rhs, 0);
+ tree op1 = TREE_OPERAND (rhs, 1);
+
+ if (rhs_code == TRUNC_DIV_EXPR)
+ {
+ t = build_int_cst (NULL_TREE, tree_log2 (op1));
+ t = build2 (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
+ }
+ else
+ {
+ t = build_int_cst (TREE_TYPE (op1), 1);
+ t = int_const_binop (MINUS_EXPR, op1, t, 0);
+ t = fold_convert (TREE_TYPE (op0), t);
+ t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
+ }
+
+ TREE_OPERAND (stmt, 1) = t;
+ update_stmt (stmt);
+ }
+}
+
+/* If the operand to an ABS_EXPR is >= 0, then eliminate the
+ ABS_EXPR. If the operand is <= 0, then simplify the
+ ABS_EXPR into a NEGATE_EXPR. */
+
+static void
+simplify_abs_using_ranges (tree stmt, tree rhs)
+{
+ tree val = NULL;
+ tree op = TREE_OPERAND (rhs, 0);
+ tree type = TREE_TYPE (op);
+ value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
+
+ if (TYPE_UNSIGNED (type))
+ {
+ val = integer_zero_node;
+ }
+ else if (vr)
+ {
+ val = compare_range_with_value (LE_EXPR, vr, integer_zero_node);
+ if (!val)
+ {
+ val = compare_range_with_value (GE_EXPR, vr, integer_zero_node);
+
+ if (val)
+ {
+ if (integer_zerop (val))
+ val = integer_one_node;
+ else if (integer_onep (val))
+ val = integer_zero_node;
+ }
+ }
+
+ if (val
+ && (integer_onep (val) || integer_zerop (val)))
+ {
+ tree t;
+
+ if (integer_onep (val))
+ t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
+ else
+ t = op;
+
+ TREE_OPERAND (stmt, 1) = t;
+ update_stmt (stmt);
+ }
+ }
+}
+
+/* We are comparing trees OP0 and OP1 using COND_CODE. OP0 has
+ a known value range VR.
+
+ If there is one and only one value which will satisfy the
+ conditional, then return that value. Else return NULL. */
+
+static tree
+test_for_singularity (enum tree_code cond_code, tree op0,
+ tree op1, value_range_t *vr)
+{
+ tree min = NULL;
+ tree max = NULL;
+
+ /* Extract minimum/maximum values which satisfy the
+ the conditional as it was written. */
+ if (cond_code == LE_EXPR || cond_code == LT_EXPR)
+ {
+ min = TYPE_MIN_VALUE (TREE_TYPE (op0));
+
+ max = op1;
+ if (cond_code == LT_EXPR)
+ {
+ tree one = build_int_cst (TREE_TYPE (op0), 1);
+ max = fold_build2 (MINUS_EXPR, TREE_TYPE (op0), max, one);
+ }
+ }
+ else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
+ {
+ max = TYPE_MAX_VALUE (TREE_TYPE (op0));
+
+ min = op1;
+ if (cond_code == GT_EXPR)
+ {
+ tree one = build_int_cst (TREE_TYPE (op0), 1);
+ min = fold_build2 (PLUS_EXPR, TREE_TYPE (op0), min, one);
+ }
+ }
+
+ /* Now refine the minimum and maximum values using any
+ value range information we have for op0. */
+ if (min && max)
{
- block_stmt_iterator bsi;
+ if (compare_values (vr->min, min) == -1)
+ min = min;
+ else
+ min = vr->min;
+ if (compare_values (vr->max, max) == 1)
+ max = max;
+ else
+ max = vr->max;
+
+ /* If the new min/max values have converged to a single value,
+ then there is only one value which can satisfy the condition,
+ return that value. */
+ if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
+ return min;
+ }
+ return NULL;
+}
- for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+/* Simplify a conditional using a relational operator to an equality
+ test if the range information indicates only one value can satisfy
+ the original conditional. */
+
+static void
+simplify_cond_using_ranges (tree stmt)
+{
+ tree cond = COND_EXPR_COND (stmt);
+ tree op0 = TREE_OPERAND (cond, 0);
+ tree op1 = TREE_OPERAND (cond, 1);
+ enum tree_code cond_code = TREE_CODE (cond);
+
+ if (cond_code != NE_EXPR
+ && cond_code != EQ_EXPR
+ && TREE_CODE (op0) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (op0))
+ && is_gimple_min_invariant (op1))
+ {
+ value_range_t *vr = get_value_range (op0);
+
+ /* If we have range information for OP0, then we might be
+ able to simplify this conditional. */
+ if (vr->type == VR_RANGE)
{
- tree stmt = bsi_stmt (bsi);
+ tree new = test_for_singularity (cond_code, op0, op1, vr);
- if (TREE_CODE (stmt) == MODIFY_EXPR)
+ if (new)
{
- tree rhs = TREE_OPERAND (stmt, 1);
- enum tree_code rhs_code = TREE_CODE (rhs);
-
- /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
- and BIT_AND_EXPR respectively if the first operand is greater
- than zero and the second operand is an exact power of two. */
- if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
- && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
- && integer_pow2p (TREE_OPERAND (rhs, 1)))
+ if (dump_file)
{
- tree val = NULL;
- tree op = TREE_OPERAND (rhs, 0);
- value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
-
- if (TYPE_UNSIGNED (TREE_TYPE (op)))
- {
- val = integer_one_node;
- }
- else
- {
- val = compare_range_with_value (GT_EXPR, vr,
- integer_zero_node);
- }
-
- if (val && integer_onep (val))
- {
- tree t;
- tree op0 = TREE_OPERAND (rhs, 0);
- tree op1 = TREE_OPERAND (rhs, 1);
-
- if (rhs_code == TRUNC_DIV_EXPR)
- {
- t = build_int_cst (NULL_TREE, tree_log2 (op1));
- t = build (RSHIFT_EXPR, TREE_TYPE (op0), op0, t);
- }
- else
- {
- t = build_int_cst (TREE_TYPE (op1), 1);
- t = int_const_binop (MINUS_EXPR, op1, t, 0);
- t = fold_convert (TREE_TYPE (op0), t);
- t = build2 (BIT_AND_EXPR, TREE_TYPE (op0), op0, t);
- }
-
- TREE_OPERAND (stmt, 1) = t;
- update_stmt (stmt);
- }
-
+ fprintf (dump_file, "Simplified relational ");
+ print_generic_expr (dump_file, cond, 0);
+ fprintf (dump_file, " into ");
}
- /* Transform ABS (X) into X or -X as appropriate. */
- if (rhs_code == ABS_EXPR
- && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
- && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
+ COND_EXPR_COND (stmt)
+ = build2 (EQ_EXPR, boolean_type_node, op0, new);
+ update_stmt (stmt);
+
+ if (dump_file)
{
- tree val = NULL;
- tree op = TREE_OPERAND (rhs, 0);
- tree type = TREE_TYPE (op);
- value_range_t *vr = get_value_range (TREE_OPERAND (rhs, 0));
-
- if (TYPE_UNSIGNED (type))
- {
- val = integer_zero_node;
- }
- else if (vr)
- {
- val = compare_range_with_value (LE_EXPR, vr,
- integer_zero_node);
- if (!val)
- {
- val = compare_range_with_value (GE_EXPR, vr,
- integer_zero_node);
-
- if (val)
- {
- if (integer_zerop (val))
- val = integer_one_node;
- else if (integer_onep (val))
- val = integer_zero_node;
- }
- }
-
- if (val
- && (integer_onep (val) || integer_zerop (val)))
- {
- tree t;
-
- if (integer_onep (val))
- t = build1 (NEGATE_EXPR, TREE_TYPE (op), op);
- else
- t = op;
-
- TREE_OPERAND (stmt, 1) = t;
- update_stmt (stmt);
- }
- }
+ print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
+ fprintf (dump_file, "\n");
}
+ return;
+
}
- /* TODO. Simplify conditionals. */
+ /* Try again after inverting the condition. We only deal
+ with integral types here, so no need to worry about
+ issues with inverting FP comparisons. */
+ cond_code = invert_tree_comparison (cond_code, false);
+ new = test_for_singularity (cond_code, op0, op1, vr);
+
+ if (new)
+ {
+ if (dump_file)
+ {
+ fprintf (dump_file, "Simplified relational ");
+ print_generic_expr (dump_file, cond, 0);
+ fprintf (dump_file, " into ");
+ }
+
+ COND_EXPR_COND (stmt)
+ = build2 (NE_EXPR, boolean_type_node, op0, new);
+ update_stmt (stmt);
+
+ if (dump_file)
+ {
+ print_generic_expr (dump_file, COND_EXPR_COND (stmt), 0);
+ fprintf (dump_file, "\n");
+ }
+ return;
+
+ }
}
}
}
+/* Simplify STMT using ranges if possible. */
+
+void
+simplify_stmt_using_ranges (tree stmt)
+{
+ if (TREE_CODE (stmt) == MODIFY_EXPR)
+ {
+ tree rhs = TREE_OPERAND (stmt, 1);
+ enum tree_code rhs_code = TREE_CODE (rhs);
+
+ /* Transform TRUNC_DIV_EXPR and TRUNC_MOD_EXPR into RSHIFT_EXPR
+ and BIT_AND_EXPR respectively if the first operand is greater
+ than zero and the second operand is an exact power of two. */
+ if ((rhs_code == TRUNC_DIV_EXPR || rhs_code == TRUNC_MOD_EXPR)
+ && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0)))
+ && integer_pow2p (TREE_OPERAND (rhs, 1)))
+ simplify_div_or_mod_using_ranges (stmt, rhs, rhs_code);
+
+ /* Transform ABS (X) into X or -X as appropriate. */
+ if (rhs_code == ABS_EXPR
+ && TREE_CODE (TREE_OPERAND (rhs, 0)) == SSA_NAME
+ && INTEGRAL_TYPE_P (TREE_TYPE (TREE_OPERAND (rhs, 0))))
+ simplify_abs_using_ranges (stmt, rhs);
+ }
+ else if (TREE_CODE (stmt) == COND_EXPR
+ && COMPARISON_CLASS_P (COND_EXPR_COND (stmt)))
+ {
+ simplify_cond_using_ranges (stmt);
+ }
+}
+
+
/* Traverse all the blocks folding conditionals with known ranges. */
substitute_and_fold (single_val_range, true);
- /* One could argue all simplifications should be done here
- rather than using substitute_and_fold since this code
- is going to have to perform a complete walk through the
- IL anyway. */
- simplify_using_ranges ();
-
/* Free allocated memory. */
for (i = 0; i < num_ssa_names; i++)
if (vr_value[i])
OSDN Git Service
