VR-VALUES: Simplify comparison using range pairs

  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
  

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)?

In the linear search above I'm missing an earlier out
if op1 falls inside a sub-range, you seem to walk the whole
array?

When is this transform profitable on its own and why would
it enable followup simplifications?  The example you quote
is for turning the compare into a compare with zero which
is usually cheap but this case would also be easy to special
case.  Transforming to an equality test in the end enables
conditional constant propagation, so that's another thing but
any other case should point out missed secondary opportunities
in ranger?

Thanks,
Richard.

> +      if (cond_code == LT_EXPR
> +          && val_op1 != lower)
> +        {
> +         op1 = wide_int_to_tree (type, lower);
> +         cond_code = LE_EXPR;
> +         return true;
> +        }
> +      if (cond_code == LE_EXPR
> +          && val_op1 != upper
> +          && val_op1 != lower)
> +        {
> +         op1 = wide_int_to_tree (type, lower);
> +         cond_code = LE_EXPR;
> +         return true;
> +        }
> +      if (cond_code == GT_EXPR
> +          && val_op1 != upper)
> +        {
> +         op1 = wide_int_to_tree (type, upper);
> +         cond_code = GE_EXPR;
> +         return true;
> +        }
> +      if (cond_code == GE_EXPR
> +          && val_op1 != lower
> +          && val_op1 != upper)
> +        {
> +         op1 = wide_int_to_tree (type, upper);
> +         cond_code = GE_EXPR;
> +         return true;
> +        }
> +    }
> +  return false;
> +}
> +
>  /* Return whether the value range *VR fits in an integer type specified
>     by PRECISION and UNSIGNED_P.  */
>
> @@ -1235,6 +1298,8 @@ 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 ())
>         {
> +         if (simplify_compare_using_range_pairs (cond_code, op0, op1, &vr))
> +           happened = true;
>           tree new_tree = test_for_singularity (cond_code, op0, op1, &vr);
>           if (new_tree)
>             {
> --
> 2.31.1
>
  

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.

Thanks,
Richard
  

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::?

> Thanks,
> Richard
  

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
  

On Thu, Aug 10, 2023 at 12:18 AM Richard Biener via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
> 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)?
>
> In the linear search above I'm missing an earlier out
> if op1 falls inside a sub-range, you seem to walk the whole
> array?
>
> When is this transform profitable on its own and why would
> it enable followup simplifications?  The example you quote
> is for turning the compare into a compare with zero which
> is usually cheap but this case would also be easy to special
> case.  Transforming to an equality test in the end enables
> conditional constant propagation, so that's another thing but
> any other case should point out missed secondary opportunities
> in ranger?

I was going back and forth on if I should just handle the two edge
(first or the last ranges being singleton) cases or make it generic.
In the end I ended up posting the generic case.
I will post the patch which handles the two edge cases later today
instead since that should be simpler and does not have the linear
search.

Thanks,
Andrew

>
> Thanks,
> Richard.
>
> > +      if (cond_code == LT_EXPR
> > +          && val_op1 != lower)
> > +        {
> > +         op1 = wide_int_to_tree (type, lower);
> > +         cond_code = LE_EXPR;
> > +         return true;
> > +        }
> > +      if (cond_code == LE_EXPR
> > +          && val_op1 != upper
> > +          && val_op1 != lower)
> > +        {
> > +         op1 = wide_int_to_tree (type, lower);
> > +         cond_code = LE_EXPR;
> > +         return true;
> > +        }
> > +      if (cond_code == GT_EXPR
> > +          && val_op1 != upper)
> > +        {
> > +         op1 = wide_int_to_tree (type, upper);
> > +         cond_code = GE_EXPR;
> > +         return true;
> > +        }
> > +      if (cond_code == GE_EXPR
> > +          && val_op1 != lower
> > +          && val_op1 != upper)
> > +        {
> > +         op1 = wide_int_to_tree (type, upper);
> > +         cond_code = GE_EXPR;
> > +         return true;
> > +        }
> > +    }
> > +  return false;
> > +}
> > +
> >  /* Return whether the value range *VR fits in an integer type specified
> >     by PRECISION and UNSIGNED_P.  */
> >
> > @@ -1235,6 +1298,8 @@ 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 ())
> >         {
> > +         if (simplify_compare_using_range_pairs (cond_code, op0, op1, &vr))
> > +           happened = true;
> >           tree new_tree = test_for_singularity (cond_code, op0, op1, &vr);
> >           if (new_tree)
> >             {
> > --
> > 2.31.1
> >
  

On Thu, Aug 10, 2023 at 12:08 PM Andrew Pinski <pinskia@gmail.com> wrote:
>
> On Thu, Aug 10, 2023 at 12:18 AM Richard Biener via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
> >
> > 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)?
> >
> > In the linear search above I'm missing an earlier out
> > if op1 falls inside a sub-range, you seem to walk the whole
> > array?
> >
> > When is this transform profitable on its own and why would
> > it enable followup simplifications?  The example you quote
> > is for turning the compare into a compare with zero which
> > is usually cheap but this case would also be easy to special
> > case.  Transforming to an equality test in the end enables
> > conditional constant propagation, so that's another thing but
> > any other case should point out missed secondary opportunities
> > in ranger?
>
> I was going back and forth on if I should just handle the two edge
> (first or the last ranges being singleton) cases or make it generic.
> In the end I ended up posting the generic case.
> I will post the patch which handles the two edge cases later today
> instead since that should be simpler and does not have the linear
> search.

So I found a better way of implementing this which is to use
range_op_handler and then check for singleton after that.
The code is much simpler than before and does not need to do any
linear searching or even special case the edge cases.
Also can be extended later on to catch other cases if we want to add them.
This also removes the old code that was done for test_for_singularity
as it is handled by this new version of the code without any issues.
I will be posting the patch once the bootstrap/test is finished.

Thanks,
Andrew


>
> Thanks,
> Andrew
>
> >
> > Thanks,
> > Richard.
> >
> > > +      if (cond_code == LT_EXPR
> > > +          && val_op1 != lower)
> > > +        {
> > > +         op1 = wide_int_to_tree (type, lower);
> > > +         cond_code = LE_EXPR;
> > > +         return true;
> > > +        }
> > > +      if (cond_code == LE_EXPR
> > > +          && val_op1 != upper
> > > +          && val_op1 != lower)
> > > +        {
> > > +         op1 = wide_int_to_tree (type, lower);
> > > +         cond_code = LE_EXPR;
> > > +         return true;
> > > +        }
> > > +      if (cond_code == GT_EXPR
> > > +          && val_op1 != upper)
> > > +        {
> > > +         op1 = wide_int_to_tree (type, upper);
> > > +         cond_code = GE_EXPR;
> > > +         return true;
> > > +        }
> > > +      if (cond_code == GE_EXPR
> > > +          && val_op1 != lower
> > > +          && val_op1 != upper)
> > > +        {
> > > +         op1 = wide_int_to_tree (type, upper);
> > > +         cond_code = GE_EXPR;
> > > +         return true;
> > > +        }
> > > +    }
> > > +  return false;
> > > +}
> > > +
> > >  /* Return whether the value range *VR fits in an integer type specified
> > >     by PRECISION and UNSIGNED_P.  */
> > >
> > > @@ -1235,6 +1298,8 @@ 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 ())
> > >         {
> > > +         if (simplify_compare_using_range_pairs (cond_code, op0, op1, &vr))
> > > +           happened = true;
> > >           tree new_tree = test_for_singularity (cond_code, op0, op1, &vr);
> > >           if (new_tree)
> > >             {
> > > --
> > > 2.31.1
> > >