Re: [PATCH 2/2] VR-VALUES: Rewrite test_for_singularity using range_op_handler

[Andrew Pinski <pinskia@gmail.com>]

On Fri, Aug 11, 2023 at 8:08 AM Andrew MacLeod via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
>
> On 8/11/23 05:51, Richard Biener wrote:
> > On Fri, Aug 11, 2023 at 11:17 AM Andrew Pinski via Gcc-patches
> > <gcc-patches@gcc.gnu.org> wrote:
> >> So it turns out there was a simplier way of starting to
> >> improve VRP to start to fix PR 110131, PR 108360, and PR 108397.
> >> That was rewrite test_for_singularity to use range_op_handler
> >> and Value_Range.
> >>
> >> This patch implements that and
> >>
> >> OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.
> > I'm hoping Andrew/Aldy can have a look here.
> >
> > Richard.
> >
> >> gcc/ChangeLog:
> >>
> >>          * vr-values.cc (test_for_singularity): Add edge argument
> >>          and rewrite using range_op_handler.
> >>          (simplify_compare_using_range_pairs): Use Value_Range
> >>          instead of value_range and update test_for_singularity call.
> >>
> >> gcc/testsuite/ChangeLog:
> >>
> >>          * gcc.dg/tree-ssa/vrp124.c: New test.
> >>          * gcc.dg/tree-ssa/vrp125.c: New test.
> >> ---
> >>   gcc/testsuite/gcc.dg/tree-ssa/vrp124.c | 44 +++++++++++++
> >>   gcc/testsuite/gcc.dg/tree-ssa/vrp125.c | 44 +++++++++++++
> >>   gcc/vr-values.cc                       | 91 ++++++++------------------
> >>   3 files changed, 114 insertions(+), 65 deletions(-)
> >>   create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp124.c
> >>   create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp125.c
> >>
> >> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp124.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp124.c
> >> new file mode 100644
> >> index 00000000000..6ccbda35d1b
> >> --- /dev/null
> >> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp124.c
> >> @@ -0,0 +1,44 @@
> >> +/* { dg-do compile } */
> >> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> >> +
> >> +/* Should be optimized to a == -100 */
> >> +int g(int a)
> >> +{
> >> +  if (a == -100 || a >= 0)
> >> +    ;
> >> +  else
> >> +    return 0;
> >> +  return a < 0;
> >> +}
> >> +
> >> +/* Should optimize to a == 0 */
> >> +int f(int a)
> >> +{
> >> +  if (a == 0 || a > 100)
> >> +    ;
> >> +  else
> >> +    return 0;
> >> +  return a < 50;
> >> +}
> >> +
> >> +/* Should be optimized to a == 0. */
> >> +int f2(int a)
> >> +{
> >> +  if (a == 0 || a > 100)
> >> +    ;
> >> +  else
> >> +    return 0;
> >> +  return a < 100;
> >> +}
> >> +
> >> +/* Should optimize to a == 100 */
> >> +int f1(int a)
> >> +{
> >> +  if (a < 0 || a == 100)
> >> +    ;
> >> +  else
> >> +    return 0;
> >> +  return a > 50;
> >> +}
> >> +
> >> +/* { dg-final { scan-tree-dump-not "goto " "optimized" } } */
> >> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/vrp125.c b/gcc/testsuite/gcc.dg/tree-ssa/vrp125.c
> >> new file mode 100644
> >> index 00000000000..f6c2f8e35f1
> >> --- /dev/null
> >> +++ b/gcc/testsuite/gcc.dg/tree-ssa/vrp125.c
> >> @@ -0,0 +1,44 @@
> >> +/* { dg-do compile } */
> >> +/* { dg-options "-O2 -fdump-tree-optimized" } */
> >> +
> >> +/* Should be optimized to a == -100 */
> >> +int g(int a)
> >> +{
> >> +  if (a == -100 || a == -50 || a >= 0)
> >> +    ;
> >> +  else
> >> +    return 0;
> >> +  return a < -50;
> >> +}
> >> +
> >> +/* Should optimize to a == 0 */
> >> +int f(int a)
> >> +{
> >> +  if (a == 0 || a == 50 || a > 100)
> >> +    ;
> >> +  else
> >> +    return 0;
> >> +  return a < 50;
> >> +}
> >> +
> >> +/* Should be optimized to a == 0. */
> >> +int f2(int a)
> >> +{
> >> +  if (a == 0 || a == 50 || a > 100)
> >> +    ;
> >> +  else
> >> +    return 0;
> >> +  return a < 25;
> >> +}
> >> +
> >> +/* Should optimize to a == 100 */
> >> +int f1(int a)
> >> +{
> >> +  if (a < 0 || a == 50 || a == 100)
> >> +    ;
> >> +  else
> >> +    return 0;
> >> +  return a > 50;
> >> +}
> >> +
> >> +/* { dg-final { scan-tree-dump-not "goto " "optimized" } } */
> >> diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc
> >> index a4fddd62841..7004b0224bd 100644
> >> --- a/gcc/vr-values.cc
> >> +++ b/gcc/vr-values.cc
> >> @@ -907,66 +907,30 @@ simplify_using_ranges::simplify_bit_ops_using_ranges
> >>      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.
> >> -
> >> -   If signed overflow must be undefined for the value to satisfy
> >> -   the conditional, then set *STRICT_OVERFLOW_P to true.  */
> >> +   conditional on the EDGE, then return that value.
> >> +   Else return NULL.  */
> >>
> >>   static tree
> >>   test_for_singularity (enum tree_code cond_code, tree op0,
> >> -                     tree op1, const value_range *vr)
> >> +                     tree op1, Value_Range vr, bool edge)
>
> VR should be a "vrange &".   THis is the top level base class for all
> ranges of all types/kinds, and what we usually pass values around as if
> we want tohem to be any kind.   If this is inetger only, we'd pass a an
> 'irange &'
>
> Value_Range is the opposite. Its the sink that contains one of each kind
> of range and can switch around between them as needed. You do not want
> to pass that by value!   The generic engine uses these so it can suppose
> floats. int, pointers, whatever...
>
> >>   {
> >> -  tree min = NULL;
> >> -  tree max = NULL;
> >> -
> >> -  /* Extract minimum/maximum values which satisfy the conditional as it was
> >> -     written.  */
> >> -  if (cond_code == LE_EXPR || cond_code == LT_EXPR)
> >> +  /* This is already a singularity.  */
> >> +  if (cond_code == NE_EXPR || cond_code == EQ_EXPR)
> >> +    return NULL;
> >> +  auto range_op = range_op_handler (cond_code);
> >> +  int_range<2> op1_range (TREE_TYPE (op0));
> >> +  wide_int w = wi::to_wide (op1);
> >> +  op1_range.set (TREE_TYPE (op1), w, w);
>
> If this is only going to work with integers, you might want to check
> that somewhere or switch to irange and int_range_max..
>
> You can make it work with any kind (if you know op1 is a constant) by
> simply doing
>
> Value_Range op1_range (TREE_TYPE (op1))
> get_global_range_query->range_of_expr (op1_range, op1)
>
> That will convert trees to a the appropriate range...  THis is also true
> for integer constants... but you can also just do the WI conversion like
> you do.
>
> The routine also get confusing to read because it passes in op0 and
> op1,  but of course ranger uses op1 and op2 nomenclature, and it looks a
> bit confusing :-P   I'd change the operands passed in to op1 and op2 if
> we are rewriting the routine.
>
> >> +  Value_Range vr1(TREE_TYPE (op0));
> >> +  if (range_op.op1_range (vr1, TREE_TYPE (op0),
> >> +                         edge ? range_true () : range_false (),
> >> +                         op1_range))
>
> IF you decide to stick with integers, then you can just make vr1 an
>     int_range_max  vr1;
> You don't need the type in the declaration if you know its an irange.
> Value_Range needs  a type because it needs to know if its an integr or a
> floating point (or whatever) that it is going ot be used as.
> >>       {
> >> -      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);
> >> -         /* Signal to compare_values_warnv this expr doesn't overflow.  */
> >> -         if (EXPR_P (max))
> >> -           suppress_warning (max, OPT_Woverflow);
> >> -       }
> >> -    }
> >> -  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);
> >> -         /* Signal to compare_values_warnv this expr doesn't overflow.  */
> >> -         if (EXPR_P (min))
> >> -           suppress_warning (min, OPT_Woverflow);
> >> -       }
> >> -    }
> >> -
> >> -  /* Now refine the minimum and maximum values using any
> >> -     value range information we have for op0.  */
> >> -  if (min && max)
> >> -    {
> >> -      tree type = TREE_TYPE (op0);
> >> -      tree tmin = wide_int_to_tree (type, vr->lower_bound ());
> >> -      tree tmax = wide_int_to_tree (type, vr->upper_bound ());
> >> -      if (compare_values (tmin, min) == 1)
> >> -       min = tmin;
> >> -      if (compare_values (tmax, max) == -1)
> >> -       max = tmax;
> >> -
> >> -      /* 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;
> >> +      vr.intersect (vr1);
> >> +      tree newop1;
> >> +      /* If the updated range is just a singleton, then we can just do a comparison */
> >> +      if (vr.singleton_p (&newop1))
> >> +       return newop1;
> >>       }
> >>     return NULL;
> >>   }
> >> @@ -1224,9 +1188,9 @@ simplify_using_ranges::simplify_compare_using_ranges_1 (tree_code &cond_code, tr
> >>         && cond_code != EQ_EXPR
> >>         && TREE_CODE (op0) == SSA_NAME
> >>         && INTEGRAL_TYPE_P (TREE_TYPE (op0))
> >> -      && is_gimple_min_invariant (op1))
> >> +      && TREE_CODE (op1) == INTEGER_CST)
> >>       {
> >> -      value_range vr;
> >> +      Value_Range vr (TREE_TYPE (op0));
> OK, so we know they are integers.. you could just iuse int_range_max
> vr;   if you want to stick to integers
> >>
> >>         if (!query->range_of_expr (vr, op0, stmt))
> >>          vr.set_undefined ();
> >> @@ -1235,20 +1199,17 @@ simplify_using_ranges::simplify_compare_using_ranges_1 (tree_code &cond_code, tr
> >>           able to simplify this conditional. */
> >>         if (!vr.undefined_p () && !vr.varying_p ())
> >>          {
> >> -         tree new_tree = test_for_singularity (cond_code, op0, op1, &vr);
> >> +         tree new_tree = test_for_singularity (cond_code, op0, op1, vr,
> >> +                                               true);
> >>            if (new_tree)
> >>              {
> >>                cond_code = EQ_EXPR;
> >>                op1 = new_tree;
> >>                happened = true;
> >>              }
> >> -
> >> -         /* Try again after inverting the condition.  We only deal
> >> -            with integral types here, so no need to worry about
> >> -            issues with inverting FP comparisons.  */
> >> -         new_tree = test_for_singularity
> >> -                      (invert_tree_comparison (cond_code, false),
> >> -                       op0, op1, &vr);
> >> +         /* Try again after inverting the condition. */
> >> +         new_tree = test_for_singularity (cond_code, op0, op1, vr,
> >> +                                          false);
> >>            if (new_tree)
> >>              {
> >>                cond_code = NE_EXPR;
> >> --
> >> 2.31.1
> >>
> Other than that, LGTM.

I am going to update this patch based on the review here; I just need
a few more days to do it.

Thanks,
Andrew

>
> Andrew
>