Re: [PATCH] VR-VALUES: Simplify comparison using range pairs

[Richard Sandiford <richard.sandiford@arm.com>]

Richard Biener <richard.guenther@gmail.com> writes:
> On Thu, Aug 10, 2023 at 3:44 PM Richard Sandiford
> <richard.sandiford@arm.com> wrote:
>>
>> Richard Biener via Gcc-patches <gcc-patches@gcc.gnu.org> writes:
>> > On Wed, Aug 9, 2023 at 6:16 PM Andrew Pinski via Gcc-patches
>> > <gcc-patches@gcc.gnu.org> wrote:
>> >>
>> >> If `A` has a range of `[0,0][100,INF]` and the comparison
>> >> of `A < 50`. This should be optimized to `A <= 0` (which then
>> >> will be optimized to just `A == 0`).
>> >> This patch implement this via a new function which sees if
>> >> the constant of a comparison is in the middle of 2 range pairs
>> >> and change the constant to the either upper bound of the first pair
>> >> or the lower bound of the second pair depending on the comparison.
>> >>
>> >> This is the first step in fixing the following PRS:
>> >> PR 110131, PR 108360, and PR 108397.
>> >>
>> >> OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.
>> >
>> >
>> >
>> >> gcc/ChangeLog:
>> >>
>> >>         * vr-values.cc (simplify_compare_using_range_pairs): New function.
>> >>         (simplify_using_ranges::simplify_compare_using_ranges_1): Call
>> >>         it.
>> >>
>> >> gcc/testsuite/ChangeLog:
>> >>
>> >>         * gcc.dg/tree-ssa/vrp124.c: New test.
>> >>         * gcc.dg/pr21643.c: Disable VRP.
>> >> ---
>> >>  gcc/testsuite/gcc.dg/pr21643.c         |  6 ++-
>> >>  gcc/testsuite/gcc.dg/tree-ssa/vrp124.c | 44 +++++++++++++++++
>> >>  gcc/vr-values.cc                       | 65 ++++++++++++++++++++++++++
>> >>  3 files changed, 114 insertions(+), 1 deletion(-)
>> >>  create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp124.c
>> >>
>> >> diff --git a/gcc/testsuite/gcc.dg/pr21643.c b/gcc/testsuite/gcc.dg/pr21643.c
>> >> index 4e7f93d351a..7f121d7006f 100644
>> >> --- a/gcc/testsuite/gcc.dg/pr21643.c
>> >> +++ b/gcc/testsuite/gcc.dg/pr21643.c
>> >> @@ -1,6 +1,10 @@
>> >>  /* PR tree-optimization/21643 */
>> >>  /* { dg-do compile } */
>> >> -/* { dg-options "-O2 -fdump-tree-reassoc1-details --param logical-op-non-short-circuit=1" } */
>> >> +/* Note VRP is able to transform `c >= 0x20` in f7
>> >> +   to `c >= 0x21` since we want to test
>> >> +   reassociation and not VRP, turn it off. */
>> >> +
>> >> +/* { dg-options "-O2 -fdump-tree-reassoc1-details --param logical-op-non-short-circuit=1 -fno-tree-vrp" } */
>> >>
>> >>  int
>> >>  f1 (unsigned char 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/vr-values.cc b/gcc/vr-values.cc
>> >> index a4fddd62841..1262e7cf9f0 100644
>> >> --- a/gcc/vr-values.cc
>> >> +++ b/gcc/vr-values.cc
>> >> @@ -968,9 +968,72 @@ test_for_singularity (enum tree_code cond_code, tree op0,
>> >>        if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
>> >>         return min;
>> >>      }
>> >> +
>> >>    return NULL;
>> >>  }
>> >>
>> >> +/* Simplify integer comparisons such that the constant is one of the range pairs.
>> >> +   For an example,
>> >> +   A has a range of [0,0][100,INF]
>> >> +   and the comparison of `A < 50`.
>> >> +   This should be optimized to `A <= 0`
>> >> +   and then test_for_singularity can optimize it to `A == 0`.   */
>> >> +
>> >> +static bool
>> >> +simplify_compare_using_range_pairs (tree_code &cond_code, tree &op0, tree &op1,
>> >> +                                   const value_range *vr)
>> >> +{
>> >> +  if (TREE_CODE (op1) != INTEGER_CST
>> >> +      || vr->num_pairs () < 2)
>> >> +    return false;
>> >> +  auto val_op1 = wi::to_wide (op1);
>> >> +  tree type = TREE_TYPE (op0);
>> >> +  auto sign = TYPE_SIGN (type);
>> >> +  auto p = vr->num_pairs ();
>> >> +  /* Find the value range pair where op1
>> >> +     is in the middle of if one exist. */
>> >> +  for (unsigned i = 1; i < p; i++)
>> >> +    {
>> >> +      auto lower = vr->upper_bound (i - 1);
>> >> +      auto upper = vr->lower_bound (i);
>> >> +      if (wi::lt_p (val_op1, lower, sign))
>> >> +       continue;
>> >> +      if (wi::gt_p (val_op1, upper, sign))
>> >> +       continue;
>> >
>> > That looks like a linear search - it looks like m_base[] is
>> > a sorted array of values so we should be able to
>> > binary search here?  array_slice::bsearch could be
>> > used if it existed (simply port it over from vec<> and
>> > use array_slice from that)?
>>
>> Better to use std::lower_bound IMO, rather than implement our
>> own custom bsearch.
>
> Though we have that available already in vec::, just need to
> port that over to array_slice:: and use that from vec::?

array_slice was supposed to be a close approximation to std::span.
I think it's more idiomatic to use the standard library on it,
rather than adding our own custom substitutes (even if we can
move the code from elsewhere).

std::lower_bound supports lambdas, rather than needing to use
the void * thing.

Thanks,
Richard