This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [PATCH][4/n] VRP and anti-range handling


2012/6/18 Richard Guenther <rguenther@suse.de>:
> 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  <rguenther@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

This caused:

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=54098

Roman.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]