On Fri, 15 Jun 2012, Richard Guenther wrote:
>
> This tries to completely implement the intersect primitive for
> VRP (what extract_range_from_assert does at its end when merging
> new and old knowledge).
>
> Bootstrap and regtest pending on x86_64-unknown-linux-gnu.
>
> I plan to re-organize vrp_meet in a similar fashion as a followup.
The following is what I ended up applying, less conservative in the
[ () ] and ( [] ) cases.
Bootstrapped and tested on x86_64-unknown-linux-gnu.
Richard.
2012-06-18 Richard Guenther <rguent...@suse.de>
* tree-vrp.c (extract_range_from_assert): Split out range
intersecting code.
(intersect_ranges): New function.
(vrp_intersect_ranges): Likewise.
Index: trunk/gcc/tree-vrp.c
===================================================================
*** trunk.orig/gcc/tree-vrp.c 2012-06-18 11:23:34.000000000 +0200
--- trunk/gcc/tree-vrp.c 2012-06-18 11:37:39.117212903 +0200
*************** live_on_edge (edge e, tree name)
*** 95,100 ****
--- 95,101 ----
static int compare_values (tree val1, tree val2);
static int compare_values_warnv (tree val1, tree val2, bool *);
static void vrp_meet (value_range_t *, value_range_t *);
+ static void vrp_intersect_ranges (value_range_t *, value_range_t *);
static tree vrp_evaluate_conditional_warnv_with_ops (enum tree_code,
tree, tree, bool, bool *,
bool *);
*************** static void
*** 1515,1521 ****
extract_range_from_assert (value_range_t *vr_p, tree expr)
{
tree var, cond, limit, min, max, type;
! value_range_t *var_vr, *limit_vr;
enum tree_code cond_code;
var = ASSERT_EXPR_VAR (expr);
--- 1516,1522 ----
extract_range_from_assert (value_range_t *vr_p, tree expr)
{
tree var, cond, limit, min, max, type;
! value_range_t *limit_vr;
enum tree_code cond_code;
var = ASSERT_EXPR_VAR (expr);
*************** extract_range_from_assert (value_range_t
*** 1777,2014 ****
else
gcc_unreachable ();
! /* If VAR already had a known range, it may happen that the new
! range we have computed and VAR's range are not compatible. For
! instance,
!
! if (p_5 == NULL)
! p_6 = ASSERT_EXPR <p_5, p_5 == NULL>;
! x_7 = p_6->fld;
! p_8 = ASSERT_EXPR <p_6, p_6 != NULL>;
!
! While the above comes from a faulty program, it will cause an ICE
! later because p_8 and p_6 will have incompatible ranges and at
! the same time will be considered equivalent. A similar situation
! would arise from
!
! if (i_5 > 10)
! i_6 = ASSERT_EXPR <i_5, i_5 > 10>;
! if (i_5 < 5)
! i_7 = ASSERT_EXPR <i_6, i_6 < 5>;
!
! Again i_6 and i_7 will have incompatible ranges. It would be
! pointless to try and do anything with i_7's range because
! anything dominated by 'if (i_5 < 5)' will be optimized away.
! Note, due to the wa in which simulation proceeds, the statement
! i_7 = ASSERT_EXPR <...> we would never be visited because the
! conditional 'if (i_5 < 5)' always evaluates to false. However,
! this extra check does not hurt and may protect against future
! changes to VRP that may get into a situation similar to the
! NULL pointer dereference example.
!
! Note that these compatibility tests are only needed when dealing
! with ranges or a mix of range and anti-range. If VAR_VR and VR_P
! are both anti-ranges, they will always be compatible, because two
! anti-ranges will always have a non-empty intersection. */
!
! var_vr = get_value_range (var);
!
! /* We may need to make adjustments when VR_P and VAR_VR are numeric
! ranges or anti-ranges. */
! if (vr_p->type == VR_VARYING
! || vr_p->type == VR_UNDEFINED
! || var_vr->type == VR_VARYING
! || var_vr->type == VR_UNDEFINED
! || symbolic_range_p (vr_p)
! || symbolic_range_p (var_vr))
! return;
!
! if (var_vr->type == VR_RANGE && vr_p->type == VR_RANGE)
! {
! /* If the two ranges have a non-empty intersection, we can
! refine the resulting range. Since the assert expression
! creates an equivalency and at the same time it asserts a
! predicate, we can take the intersection of the two ranges to
! get better precision. */
! if (value_ranges_intersect_p (var_vr, vr_p))
! {
! /* Use the larger of the two minimums. */
! if (compare_values (vr_p->min, var_vr->min) == -1)
! min = var_vr->min;
! else
! min = vr_p->min;
!
! /* Use the smaller of the two maximums. */
! if (compare_values (vr_p->max, var_vr->max) == 1)
! max = var_vr->max;
! else
! max = vr_p->max;
!
! set_value_range (vr_p, vr_p->type, min, max, vr_p->equiv);
! }
! else
! {
! /* The two ranges do not intersect, set the new range to
! VARYING, because we will not be able to do anything
! meaningful with it. */
! set_value_range_to_varying (vr_p);
! }
! }
! else if ((var_vr->type == VR_RANGE && vr_p->type == VR_ANTI_RANGE)
! || (var_vr->type == VR_ANTI_RANGE && vr_p->type == VR_RANGE))
! {
! /* A range and an anti-range will cancel each other only if
! their ends are the same. For instance, in the example above,
! p_8's range ~[0, 0] and p_6's range [0, 0] are incompatible,
! so VR_P should be set to VR_VARYING. */
! if (compare_values (var_vr->min, vr_p->min) == 0
! && compare_values (var_vr->max, vr_p->max) == 0)
! set_value_range_to_varying (vr_p);
! else
! {
! tree min, max, anti_min, anti_max, real_min, real_max;
! int cmp;
!
! /* We want to compute the logical AND of the two ranges;
! there are three cases to consider.
!
!
! 1. The VR_ANTI_RANGE range is completely within the
! VR_RANGE and the endpoints of the ranges are
! different. In that case the resulting range
! should be whichever range is more precise.
! Typically that will be the VR_RANGE.
!
! 2. The VR_ANTI_RANGE is completely disjoint from
! the VR_RANGE. In this case the resulting range
! should be the VR_RANGE.
!
! 3. There is some overlap between the VR_ANTI_RANGE
! and the VR_RANGE.
!
! 3a. If the high limit of the VR_ANTI_RANGE resides
! within the VR_RANGE, then the result is a new
! VR_RANGE starting at the high limit of the
! VR_ANTI_RANGE + 1 and extending to the
! high limit of the original VR_RANGE.
!
! 3b. If the low limit of the VR_ANTI_RANGE resides
! within the VR_RANGE, then the result is a new
! VR_RANGE starting at the low limit of the original
! VR_RANGE and extending to the low limit of the
! VR_ANTI_RANGE - 1. */
! if (vr_p->type == VR_ANTI_RANGE)
! {
! anti_min = vr_p->min;
! anti_max = vr_p->max;
! real_min = var_vr->min;
! real_max = var_vr->max;
! }
! else
! {
! anti_min = var_vr->min;
! anti_max = var_vr->max;
! real_min = vr_p->min;
! real_max = vr_p->max;
! }
!
!
! /* Case 1, VR_ANTI_RANGE completely within VR_RANGE,
! not including any endpoints. */
! if (compare_values (anti_max, real_max) == -1
! && compare_values (anti_min, real_min) == 1)
! {
! /* If the range is covering the whole valid range of
! the type keep the anti-range. */
! if (!vrp_val_is_min (real_min)
! || !vrp_val_is_max (real_max))
! set_value_range (vr_p, VR_RANGE, real_min,
! real_max, vr_p->equiv);
! }
! /* Case 2, VR_ANTI_RANGE completely disjoint from
! VR_RANGE. */
! else if (compare_values (anti_min, real_max) == 1
! || compare_values (anti_max, real_min) == -1)
! {
! set_value_range (vr_p, VR_RANGE, real_min,
! real_max, vr_p->equiv);
! }
! /* Case 3a, the anti-range extends into the low
! part of the real range. Thus creating a new
! low for the real range. */
! else if (((cmp = compare_values (anti_max, real_min)) == 1
! || cmp == 0)
! && compare_values (anti_max, real_max) == -1)
! {
! gcc_assert (!is_positive_overflow_infinity (anti_max));
! if (needs_overflow_infinity (TREE_TYPE (anti_max))
! && vrp_val_is_max (anti_max))
! {
! if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
! {
! set_value_range_to_varying (vr_p);
! return;
! }
! min = positive_overflow_infinity (TREE_TYPE (var_vr->min));
! }
! else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
! {
! if (TYPE_PRECISION (TREE_TYPE (var_vr->min)) == 1
! && !TYPE_UNSIGNED (TREE_TYPE (var_vr->min)))
! min = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
! anti_max,
! build_int_cst (TREE_TYPE (var_vr->min),
! -1));
! else
! min = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
! anti_max,
! build_int_cst (TREE_TYPE (var_vr->min),
! 1));
! }
! else
! min = fold_build_pointer_plus_hwi (anti_max, 1);
! max = real_max;
! set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
! }
! /* Case 3b, the anti-range extends into the high
! part of the real range. Thus creating a new
! higher for the real range. */
! else if (compare_values (anti_min, real_min) == 1
! && ((cmp = compare_values (anti_min, real_max)) == -1
! || cmp == 0))
! {
! gcc_assert (!is_negative_overflow_infinity (anti_min));
! if (needs_overflow_infinity (TREE_TYPE (anti_min))
! && vrp_val_is_min (anti_min))
! {
! if (!supports_overflow_infinity (TREE_TYPE (var_vr->min)))
! {
! set_value_range_to_varying (vr_p);
! return;
! }
! max = negative_overflow_infinity (TREE_TYPE (var_vr->min));
! }
! else if (!POINTER_TYPE_P (TREE_TYPE (var_vr->min)))
! {
! if (TYPE_PRECISION (TREE_TYPE (var_vr->min)) == 1
! && !TYPE_UNSIGNED (TREE_TYPE (var_vr->min)))
! max = fold_build2 (PLUS_EXPR, TREE_TYPE (var_vr->min),
! anti_min,
! build_int_cst (TREE_TYPE (var_vr->min),
! -1));
! else
! max = fold_build2 (MINUS_EXPR, TREE_TYPE (var_vr->min),
! anti_min,
! build_int_cst (TREE_TYPE (var_vr->min),
! 1));
! }
! else
! max = fold_build_pointer_plus_hwi (anti_min, -1);
! min = real_min;
! set_value_range (vr_p, VR_RANGE, min, max, vr_p->equiv);
! }
! }
! }
}
--- 1778,1785 ----
else
gcc_unreachable ();
! /* Finally intersect the new range with what we already know about var. */
! vrp_intersect_ranges (vr_p, get_value_range (var));
}
*************** vrp_visit_stmt (gimple stmt, edge *taken
*** 6999,7004 ****
--- 6770,7007 ----
return SSA_PROP_VARYING;
}
+ /* Intersect the two value-ranges { *VR0TYPE, *VR0MIN, *VR0MAX } and
+ { VR1TYPE, VR0MIN, VR0MAX } and store the result
+ in { *VR0TYPE, *VR0MIN, *VR0MAX }. This may not be the smallest
+ possible such range. The resulting range is not canonicalized. */
+
+ static void
+ intersect_ranges (enum value_range_type *vr0type,
+ tree *vr0min, tree *vr0max,
+ enum value_range_type vr1type,
+ tree vr1min, tree vr1max)
+ {
+ /* [] is vr0, () is vr1 in the following classification comments. */
+ if (operand_less_p (*vr0max, vr1min) == 1
+ || operand_less_p (vr1max, *vr0min) == 1)
+ {
+ /* [ ] ( ) or ( ) [ ]
+ If the ranges have an empty intersection, the result of the
+ intersect operation is the range for intersecting an
+ anti-range with a range or empty when intersecting two ranges.
+ For intersecting two anti-ranges simply choose vr0. */
+ if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ ;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ /* Take VR0. */
+ }
+ }
+ else if (operand_less_p (vr1max, *vr0max) == 1
+ && operand_less_p (*vr0min, vr1min) == 1)
+ {
+ /* [ ( ) ] */
+ if (*vr0type == VR_RANGE)
+ {
+ /* If the outer is a range choose the inner one.
+ ??? If the inner is an anti-range this arbitrarily chooses
+ the anti-range. */
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ /* If both are anti-ranges the result is the outer one. */
+ ;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ /* The intersection is empty. */
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if (operand_less_p (*vr0max, vr1max) == 1
+ && operand_less_p (vr1min, *vr0min) == 1)
+ {
+ /* ( [ ] ) */
+ if (vr1type == VR_RANGE)
+ /* If the outer is a range, choose the inner one.
+ ??? If the inner is an anti-range this arbitrarily chooses
+ the anti-range. */
+ ;
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ /* If both are anti-ranges the result is the outer one. */
+ *vr0type = vr1type;
+ *vr0min = vr1min;
+ *vr0max = vr1max;
+ }
+ else if (vr1type == VR_ANTI_RANGE
+ && *vr0type == VR_RANGE)
+ {
+ /* The intersection is empty. */
+ *vr0type = VR_UNDEFINED;
+ *vr0min = NULL_TREE;
+ *vr0max = NULL_TREE;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if ((operand_less_p (vr1min, *vr0max) == 1
+ || operand_equal_p (vr1min, *vr0max, 0))
+ && (operand_less_p (*vr0min, vr1min) == 1
+ || operand_equal_p (*vr0min, vr1min, 0)))
+ {
+ /* [ ( ] ) */
+ if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ *vr0max = vr1max;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ *vr0min = vr1min;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ if (TREE_CODE (vr1min) == INTEGER_CST)
+ *vr0max = int_const_binop (MINUS_EXPR, vr1min,
+ integer_one_node);
+ else
+ *vr0max = vr1min;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = VR_RANGE;
+ if (TREE_CODE (*vr0max) == INTEGER_CST)
+ *vr0min = int_const_binop (PLUS_EXPR, *vr0max,
+ integer_one_node);
+ else
+ *vr0min = *vr0max;
+ *vr0max = vr1max;
+ }
+ else
+ gcc_unreachable ();
+ }
+ else if ((operand_less_p (*vr0min, vr1max) == 1
+ || operand_equal_p (*vr0min, vr1max, 0))
+ && (operand_less_p (vr1min, *vr0min) == 1
+ || operand_equal_p (vr1min, *vr0min, 0)))
+ {
+ /* ( [ ) ] */
+ if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ *vr0min = vr1min;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_RANGE)
+ *vr0max = vr1max;
+ else if (*vr0type == VR_RANGE
+ && vr1type == VR_ANTI_RANGE)
+ {
+ if (TREE_CODE (vr1max) == INTEGER_CST)
+ *vr0min = int_const_binop (PLUS_EXPR, vr1max,
+ integer_one_node);
+ else
+ *vr0min = vr1max;
+ }
+ else if (*vr0type == VR_ANTI_RANGE
+ && vr1type == VR_RANGE)
+ {
+ *vr0type = VR_RANGE;
+ if (TREE_CODE (*vr0min) == INTEGER_CST)
+ *vr0max = int_const_binop (MINUS_EXPR, *vr0min,
+ integer_one_node);
+ else
+ *vr0max = *vr0min;
+ *vr0min = vr1min;
+ }
+ else
+ gcc_unreachable ();
+ }
+
+ /* As a fallback simply use { *VRTYPE, *VR0MIN, *VR0MAX } as
+ result for the intersection. That's always a conservative
+ correct estimate. */
+
+ return;
+ }
+
+
+ /* Intersect the two value-ranges *VR0 and *VR1 and store the result
+ in *VR0. This may not be the smallest possible such range. */
+
+ static void
+ vrp_intersect_ranges (value_range_t *vr0, value_range_t *vr1)
+ {
+ value_range_t saved;
+
+ /* If either range is VR_VARYING the other one wins. */
+ if (vr1->type == VR_VARYING)
+ return;
+ if (vr0->type == VR_VARYING)
+ {
+ copy_value_range (vr0, vr1);
+ return;
+ }
+
+ /* When either range is VR_UNDEFINED the resulting range is
+ VR_UNDEFINED, too. */
+ if (vr0->type == VR_UNDEFINED)
+ return;
+ if (vr1->type == VR_UNDEFINED)
+ {
+ set_value_range_to_undefined (vr0);
+ return;
+ }
+
+ /* Save the original vr0 so we can return it as conservative intersection
+ result when our worker turns things to varying. */
+ saved = *vr0;
+ intersect_ranges (&vr0->type, &vr0->min, &vr0->max,
+ vr1->type, vr1->min, vr1->max);
+ /* Make sure to canonicalize the result though as the inversion of a
+ VR_RANGE can still be a VR_RANGE. */
+ set_and_canonicalize_value_range (vr0, vr0->type,
+ vr0->min, vr0->max, vr0->equiv);
+ /* If that failed, use the saved original VR0. */
+ if (vr0->type == VR_VARYING)
+ {
+ *vr0 = saved;
+ return;
+ }
+ /* If the result is VR_UNDEFINED there is no need to mess with
+ the equivalencies. */
+ if (vr0->type == VR_UNDEFINED)
+ return;
+
+ /* The resulting set of equivalences for range intersection is the union of
+ the two sets. */
+ if (vr0->equiv && vr1->equiv && vr0->equiv != vr1->equiv)
+ bitmap_ior_into (vr0->equiv, vr1->equiv);
+ else if (vr1->equiv && !vr0->equiv)
+ bitmap_copy (vr0->equiv, vr1->equiv);
+ }
/* Meet operation for value ranges. Given two value ranges VR0 and
VR1, store in VR0 a range that contains both VR0 and VR1. This
