On Thu, Aug 10, 2023 at 3:44 PM Richard Sandiford
<richard.sandif...@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
