Re: [PATCH] VR-VALUES: Simplify comparison using range pairs
On Thu, Aug 10, 2023 at 12:08 PM Andrew Pinski wrote:
>
> On Thu, Aug 10, 2023 at 12:18 AM Richard Biener via Gcc-patches
> wrote:
> >
> > On Wed, Aug 9, 2023 at 6:16 PM Andrew Pinski via Gcc-patches
> > 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 000..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 _code, tree ,
> > > tree ,
> > > + 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,
Re: [PATCH] VR-VALUES: Simplify comparison using range pairs
On Thu, Aug 10, 2023 at 12:18 AM Richard Biener via Gcc-patches
wrote:
>
> On Wed, Aug 9, 2023 at 6:16 PM Andrew Pinski via Gcc-patches
> 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 000..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 _code, tree , tree
> > ,
> > + 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)?
>
>
Re: [PATCH] VR-VALUES: Simplify comparison using range pairs
Richard Biener writes:
> On Thu, Aug 10, 2023 at 3:44 PM Richard Sandiford
> wrote:
>>
>> Richard Biener via Gcc-patches writes:
>> > On Wed, Aug 9, 2023 at 6:16 PM Andrew Pinski via Gcc-patches
>> > 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 000..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 _code, tree ,
>> >> tree ,
>> >> + 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,
Re: [PATCH] VR-VALUES: Simplify comparison using range pairs
On Thu, Aug 10, 2023 at 3:44 PM Richard Sandiford
wrote:
>
> Richard Biener via Gcc-patches writes:
> > On Wed, Aug 9, 2023 at 6:16 PM Andrew Pinski via Gcc-patches
> > 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 000..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 _code, tree , tree
> >> ,
> >> + 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
> >
Re: [PATCH] VR-VALUES: Simplify comparison using range pairs
Richard Biener via Gcc-patches writes:
> On Wed, Aug 9, 2023 at 6:16 PM Andrew Pinski via Gcc-patches
> 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 000..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 _code, tree , tree
>> ,
>> + 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
Re: [PATCH] VR-VALUES: Simplify comparison using range pairs
On Wed, Aug 9, 2023 at 6:16 PM Andrew Pinski via Gcc-patches
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 000..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 _code, tree , tree
> ,
> + 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
[PATCH] 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
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 000..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 _code, tree , tree ,
+ 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;
+ 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
