[2/2] VR-VALUES: Rewrite test_for_singularity using range_op_handler
Checks
Commit Message
So it turns out there was a simplier way of starting to
improve VRP to start to fix PR 110131, PR 108360, and PR 108397.
That was rewrite test_for_singularity to use range_op_handler
and Value_Range.
This patch implements that and
OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.
gcc/ChangeLog:
* vr-values.cc (test_for_singularity): Add edge argument
and rewrite using range_op_handler.
(simplify_compare_using_range_pairs): Use Value_Range
instead of value_range and update test_for_singularity call.
gcc/testsuite/ChangeLog:
* gcc.dg/tree-ssa/vrp124.c: New test.
* gcc.dg/tree-ssa/vrp125.c: New test.
---
gcc/testsuite/gcc.dg/tree-ssa/vrp124.c | 44 ++++++++++++
gcc/testsuite/gcc.dg/tree-ssa/vrp125.c | 44 ++++++++++++
gcc/vr-values.cc | 99 ++++++++------------------
3 files changed, 117 insertions(+), 70 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp124.c
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/vrp125.c
Comments
On 9/1/23 11:30, Andrew Pinski via Gcc-patches wrote:
> So it turns out there was a simplier way of starting to
> improve VRP to start to fix PR 110131, PR 108360, and PR 108397.
> That was rewrite test_for_singularity to use range_op_handler
> and Value_Range.
>
> This patch implements that and
>
> OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.
>
> gcc/ChangeLog:
>
> * vr-values.cc (test_for_singularity): Add edge argument
> and rewrite using range_op_handler.
> (simplify_compare_using_range_pairs): Use Value_Range
> instead of value_range and update test_for_singularity call.
>
> gcc/testsuite/ChangeLog:
>
> * gcc.dg/tree-ssa/vrp124.c: New test.
> * gcc.dg/tree-ssa/vrp125.c: New test.
> ---
> diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc
> index 52ab4fe6109..2474e57ee90 100644
> --- a/gcc/vr-values.cc
> +++ b/gcc/vr-values.cc
> @@ -904,69 +904,33 @@ simplify_using_ranges::simplify_bit_ops_using_ranges
> }
>
> /* We are comparing trees OP1 and OP2 using COND_CODE. OP1 has
> - a known value range VR.
> + a known value range OP1_RANGE.
>
> If there is one and only one value which will satisfy the
> - conditional, then return that value. Else return NULL.
> -
> - If signed overflow must be undefined for the value to satisfy
> - the conditional, then set *STRICT_OVERFLOW_P to true. */
> + conditional on the EDGE, then return that value.
> + Else return NULL. */
>
> static tree
> test_for_singularity (enum tree_code cond_code, tree op1,
> - tree op2, const value_range *vr)
> + tree op2, const int_range_max &op1_range, bool edge)
> {
> - tree min = NULL;
> - tree max = NULL;
> -
> - /* Extract minimum/maximum values which satisfy the conditional as it was
> - written. */
> - if (cond_code == LE_EXPR || cond_code == LT_EXPR)
> + /* This is already a singularity. */
> + if (cond_code == NE_EXPR || cond_code == EQ_EXPR)
> + return NULL;
I don't think this is necessarily the right thing to do for NE.
Consider if op1 has the range [0,1] and op2 has the value 1. If the
code is NE, then we should be able to return a singularity of 0 since
that's the only value for x where x ne 1 is true given the range for x.
I like what you're trying to do, it just needs a bit of refinement I think.
jeff
On Mon, Sep 4, 2023 at 11:06 PM Jeff Law via Gcc-patches
<gcc-patches@gcc.gnu.org> wrote:
>
>
>
> On 9/1/23 11:30, Andrew Pinski via Gcc-patches wrote:
> > So it turns out there was a simplier way of starting to
> > improve VRP to start to fix PR 110131, PR 108360, and PR 108397.
> > That was rewrite test_for_singularity to use range_op_handler
> > and Value_Range.
> >
> > This patch implements that and
> >
> > OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.
> >
> > gcc/ChangeLog:
> >
> > * vr-values.cc (test_for_singularity): Add edge argument
> > and rewrite using range_op_handler.
> > (simplify_compare_using_range_pairs): Use Value_Range
> > instead of value_range and update test_for_singularity call.
> >
> > gcc/testsuite/ChangeLog:
> >
> > * gcc.dg/tree-ssa/vrp124.c: New test.
> > * gcc.dg/tree-ssa/vrp125.c: New test.
> > ---
>
> > diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc
> > index 52ab4fe6109..2474e57ee90 100644
> > --- a/gcc/vr-values.cc
> > +++ b/gcc/vr-values.cc
> > @@ -904,69 +904,33 @@ simplify_using_ranges::simplify_bit_ops_using_ranges
> > }
> >
> > /* We are comparing trees OP1 and OP2 using COND_CODE. OP1 has
> > - a known value range VR.
> > + a known value range OP1_RANGE.
> >
> > If there is one and only one value which will satisfy the
> > - conditional, then return that value. Else return NULL.
> > -
> > - If signed overflow must be undefined for the value to satisfy
> > - the conditional, then set *STRICT_OVERFLOW_P to true. */
> > + conditional on the EDGE, then return that value.
> > + Else return NULL. */
> >
> > static tree
> > test_for_singularity (enum tree_code cond_code, tree op1,
> > - tree op2, const value_range *vr)
> > + tree op2, const int_range_max &op1_range, bool edge)
> > {
> > - tree min = NULL;
> > - tree max = NULL;
> > -
> > - /* Extract minimum/maximum values which satisfy the conditional as it was
> > - written. */
> > - if (cond_code == LE_EXPR || cond_code == LT_EXPR)
> > + /* This is already a singularity. */
> > + if (cond_code == NE_EXPR || cond_code == EQ_EXPR)
> > + return NULL;
> I don't think this is necessarily the right thing to do for NE.
>
> Consider if op1 has the range [0,1] and op2 has the value 1. If the
> code is NE, then we should be able to return a singularity of 0 since
> that's the only value for x where x ne 1 is true given the range for x.
The "false" edge singularity is already known when NE is supplied. I
don't think changing it to the "true" edge singularity will be helpful
all of the time; preferring the value of 0 is a different story.
But that is a different patch and for a different location rather than
inside VRP; it should be in either isel or expand (more likely isel).
Thanks,
Andrew
>
>
>
> I like what you're trying to do, it just needs a bit of refinement I think.
>
> jeff
On 9/5/23 01:12, Andrew Pinski wrote:
> On Mon, Sep 4, 2023 at 11:06 PM Jeff Law via Gcc-patches
> <gcc-patches@gcc.gnu.org> wrote:
>>
>>
>>
>> On 9/1/23 11:30, Andrew Pinski via Gcc-patches wrote:
>>> So it turns out there was a simplier way of starting to
>>> improve VRP to start to fix PR 110131, PR 108360, and PR 108397.
>>> That was rewrite test_for_singularity to use range_op_handler
>>> and Value_Range.
>>>
>>> This patch implements that and
>>>
>>> OK? Bootstrapped and tested on x86_64-linux-gnu with no regressions.
>>>
>>> gcc/ChangeLog:
>>>
>>> * vr-values.cc (test_for_singularity): Add edge argument
>>> and rewrite using range_op_handler.
>>> (simplify_compare_using_range_pairs): Use Value_Range
>>> instead of value_range and update test_for_singularity call.
>>>
>>> gcc/testsuite/ChangeLog:
>>>
>>> * gcc.dg/tree-ssa/vrp124.c: New test.
>>> * gcc.dg/tree-ssa/vrp125.c: New test.
>>> ---
>>
>>> diff --git a/gcc/vr-values.cc b/gcc/vr-values.cc
>>> index 52ab4fe6109..2474e57ee90 100644
>>> --- a/gcc/vr-values.cc
>>> +++ b/gcc/vr-values.cc
>>> @@ -904,69 +904,33 @@ simplify_using_ranges::simplify_bit_ops_using_ranges
>>> }
>>>
>>> /* We are comparing trees OP1 and OP2 using COND_CODE. OP1 has
>>> - a known value range VR.
>>> + a known value range OP1_RANGE.
>>>
>>> If there is one and only one value which will satisfy the
>>> - conditional, then return that value. Else return NULL.
>>> -
>>> - If signed overflow must be undefined for the value to satisfy
>>> - the conditional, then set *STRICT_OVERFLOW_P to true. */
>>> + conditional on the EDGE, then return that value.
>>> + Else return NULL. */
>>>
>>> static tree
>>> test_for_singularity (enum tree_code cond_code, tree op1,
>>> - tree op2, const value_range *vr)
>>> + tree op2, const int_range_max &op1_range, bool edge)
>>> {
>>> - tree min = NULL;
>>> - tree max = NULL;
>>> -
>>> - /* Extract minimum/maximum values which satisfy the conditional as it was
>>> - written. */
>>> - if (cond_code == LE_EXPR || cond_code == LT_EXPR)
>>> + /* This is already a singularity. */
>>> + if (cond_code == NE_EXPR || cond_code == EQ_EXPR)
>>> + return NULL;
>> I don't think this is necessarily the right thing to do for NE.
>>
>> Consider if op1 has the range [0,1] and op2 has the value 1. If the
>> code is NE, then we should be able to return a singularity of 0 since
>> that's the only value for x where x ne 1 is true given the range for x.
>
> The "false" edge singularity is already known when NE is supplied. I
> don't think changing it to the "true" edge singularity will be helpful
> all of the time; preferring the value of 0 is a different story.
> But that is a different patch and for a different location rather than
> inside VRP; it should be in either isel or expand (more likely isel).
I forgot something critically important here. Specifically, this code
is supposed to be subsumed by Ranger.
The whole point of this routine is to rewrite to EQ/NE comparisons so
that we can expose equivalences on the true/false arm of the conditional
(and NE is just as important as EQ). It's not really about preferring
any particular value like 0.
The problem with this routine is it loses information after the code has
been transformed. Let's say we had a test x < 4. If we assume that VRP
is able to prove X doesn't have any of the values [MIN..3], then we can
change the test to x == 4 and propagate 4 for any uses of X in the true arm.
But on the false ARM we end up with x != 4 which is a wider range than
[5..MAX]. So if we were to instantiate a new Ranger after the
transformation we'd lose information on the false arm. More
importantly, I think the transformation was bad for either SCEV or loop
iteration analysis.
When Andrew, Aldy and I kicked this problem around the consensus was
that Ranger should find and propagate the equivalence, including making
it visible to jump threading. That should make the rewriting totally
unnecessary.
So the net is we really ought to be doing here is looking for cases
where this code actually helps code generation and if it does we need to
understand how/why as this code is supposed to go away.
Given you're already poking around in here, you might have such cases
handy :-) If you do, I'm sure Andrew, Aldy and I would love to see them.
jeff
new file mode 100644
@@ -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" } } */
new file mode 100644
@@ -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 == -50 || a >= 0)
+ ;
+ else
+ return 0;
+ return a < -50;
+}
+
+/* Should optimize to a == 0 */
+int f(int a)
+{
+ if (a == 0 || a == 50 || a > 100)
+ ;
+ else
+ return 0;
+ return a < 50;
+}
+
+/* Should be optimized to a == 0. */
+int f2(int a)
+{
+ if (a == 0 || a == 50 || a > 100)
+ ;
+ else
+ return 0;
+ return a < 25;
+}
+
+/* Should optimize to a == 100 */
+int f1(int a)
+{
+ if (a < 0 || a == 50 || a == 100)
+ ;
+ else
+ return 0;
+ return a > 50;
+}
+
+/* { dg-final { scan-tree-dump-not "goto " "optimized" } } */
@@ -904,69 +904,33 @@ simplify_using_ranges::simplify_bit_ops_using_ranges
}
/* We are comparing trees OP1 and OP2 using COND_CODE. OP1 has
- a known value range VR.
+ a known value range OP1_RANGE.
If there is one and only one value which will satisfy the
- conditional, then return that value. Else return NULL.
-
- If signed overflow must be undefined for the value to satisfy
- the conditional, then set *STRICT_OVERFLOW_P to true. */
+ conditional on the EDGE, then return that value.
+ Else return NULL. */
static tree
test_for_singularity (enum tree_code cond_code, tree op1,
- tree op2, const value_range *vr)
+ tree op2, const int_range_max &op1_range, bool edge)
{
- tree min = NULL;
- tree max = NULL;
-
- /* Extract minimum/maximum values which satisfy the conditional as it was
- written. */
- if (cond_code == LE_EXPR || cond_code == LT_EXPR)
+ /* This is already a singularity. */
+ if (cond_code == NE_EXPR || cond_code == EQ_EXPR)
+ return NULL;
+ auto range_op = range_op_handler (cond_code);
+ wide_int w = wi::to_wide (op2);
+ int_range<1> op2_range (TREE_TYPE (op2), w, w);
+ int_range_max vr;
+ if (range_op.op1_range (vr, TREE_TYPE (op1),
+ edge ? range_true () : range_false (),
+ op2_range))
{
- min = TYPE_MIN_VALUE (TREE_TYPE (op1));
-
- max = op2;
- if (cond_code == LT_EXPR)
- {
- tree one = build_int_cst (TREE_TYPE (op1), 1);
- max = fold_build2 (MINUS_EXPR, TREE_TYPE (op1), max, one);
- /* Signal to compare_values_warnv this expr doesn't overflow. */
- if (EXPR_P (max))
- suppress_warning (max, OPT_Woverflow);
- }
- }
- else if (cond_code == GE_EXPR || cond_code == GT_EXPR)
- {
- max = TYPE_MAX_VALUE (TREE_TYPE (op1));
-
- min = op2;
- if (cond_code == GT_EXPR)
- {
- tree one = build_int_cst (TREE_TYPE (op1), 1);
- min = fold_build2 (PLUS_EXPR, TREE_TYPE (op1), min, one);
- /* Signal to compare_values_warnv this expr doesn't overflow. */
- if (EXPR_P (min))
- suppress_warning (min, OPT_Woverflow);
- }
- }
-
- /* Now refine the minimum and maximum values using any
- value range information we have for op1. */
- if (min && max)
- {
- tree type = TREE_TYPE (op1);
- tree tmin = wide_int_to_tree (type, vr->lower_bound ());
- tree tmax = wide_int_to_tree (type, vr->upper_bound ());
- if (compare_values (tmin, min) == 1)
- min = tmin;
- if (compare_values (tmax, max) == -1)
- max = tmax;
-
- /* If the new min/max values have converged to a single value,
- then there is only one value which can satisfy the condition,
- return that value. */
- if (operand_equal_p (min, max, 0) && is_gimple_min_invariant (min))
- return min;
+ int_range_max new_range = op1_range;
+ new_range.intersect (vr);
+ tree newop2;
+ /* If the updated range is just a singleton, then we can just do a comparison */
+ if (new_range.singleton_p (&newop2))
+ return newop2;
}
return NULL;
}
@@ -1224,31 +1188,26 @@ simplify_using_ranges::simplify_compare_using_ranges_1 (tree_code &cond_code, tr
&& cond_code != EQ_EXPR
&& TREE_CODE (op0) == SSA_NAME
&& INTEGRAL_TYPE_P (TREE_TYPE (op0))
- && is_gimple_min_invariant (op1))
+ && TREE_CODE (op1) == INTEGER_CST)
{
- value_range vr;
-
- if (!query->range_of_expr (vr, op0, stmt))
- vr.set_undefined ();
+ int_range_max vr;
/* If we have range information for OP0, then we might be
able to simplify this conditional. */
- if (!vr.undefined_p () && !vr.varying_p ())
+ if (query->range_of_expr (vr, op0, stmt)
+ && !vr.undefined_p () && !vr.varying_p ())
{
- tree new_tree = test_for_singularity (cond_code, op0, op1, &vr);
+ tree new_tree = test_for_singularity (cond_code, op0, op1, vr,
+ true);
if (new_tree)
{
cond_code = EQ_EXPR;
op1 = new_tree;
happened = true;
}
-
- /* Try again after inverting the condition. We only deal
- with integral types here, so no need to worry about
- issues with inverting FP comparisons. */
- new_tree = test_for_singularity
- (invert_tree_comparison (cond_code, false),
- op0, op1, &vr);
+ /* Try again after inverting the condition. */
+ new_tree = test_for_singularity (cond_code, op0, op1, vr,
+ false);
if (new_tree)
{
cond_code = NE_EXPR;