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