[v2] phi-opt: Add missed optimization for "(cond | (a != b)) ? b : a"

  Thanks for the feedback on the first version of the patch. Accordingly:

I have corrected the code formatting as requested. I added new tests to
the existing file phi-opt-11.c, instead of creating a new one.

I performed testing before and after applying the patch on the x86
architecture, and I confirm that there are no new regressions.

The logic and general code of the patch itself have not been changed.

> So the A EQ/NE B expression, we can reverse A and B in the expression
> and still get the same result. But don't we have to be more careful for
> the TRUE/FALSE arms of the ternary? For BIT_AND we need ? a : b for
> BIT_IOR we need ? b : a.
>
> I don't see that gets verified in the existing code or after your
> change. I suspect I'm just missing something here. Can you clarify how
> we verify that BIT_AND gets ? a : b for the true/false arms and that
> BIT_IOR gets ? b : a for the true/false arms?

I did not communicate this clearly last time, but the existing optimization
simplifies the expression "(cond & (a == b)) ? a : b" to the simpler "b".
Similarly, the expression "(cond & (a == b)) ? b : a" simplifies to "a".

Thus, the existing and my optimization perform the following
simplifications:

(cond & (a == b)) ? a : b -> b
(cond & (a == b)) ? b : a -> a
(cond | (a != b)) ? a : b -> a
(cond | (a != b)) ? b : a -> b

For this reason, for BIT_AND_EXPR when we have A EQ B, it is sufficient to
confirm that one operand matches the true/false arm and the other matches
the false/true arm. In both cases, we simplify the expression to the third
operand of the ternary operation (i.e., OP0 ? OP1 : OP2 simplifies to OP2).
This is achieved in the value_replacement function after successfully
setting the value of *code within the rhs_is_fed_for_value_replacement
function to EQ_EXPR.

For BIT_IOR_EXPR, the same check is performed for A NE B, except now
*code remains NE_EXPR, and then value_replacement returns the second
operand (i.e., OP0 ? OP1 : OP2 simplifies to OP1).

2024-10-30  Jovan Vukic  <Jovan.Vukic@rt-rk.com>

gcc/ChangeLog:

        * tree-ssa-phiopt.cc
        (rhs_is_fed_for_value_replacement): Add a new optimization opportunity
        for BIT_IOR_EXPR and a != b.
        (operand_equal_for_value_replacement): Ditto.

gcc/testsuite/ChangeLog:

        * gcc.dg/tree-ssa/phi-opt-11.c: Add more tests.


CONFIDENTIALITY: The contents of this e-mail are confidential and intended only for the above addressee(s). If you are not the intended recipient, or the person responsible for delivering it to the intended recipient, copying or delivering it to anyone else or using it in any unauthorized manner is prohibited and may be unlawful. If you receive this e-mail by mistake, please notify the sender and the systems administrator at straymail@rt-rk.com immediately.
---
 gcc/testsuite/gcc.dg/tree-ssa/phi-opt-11.c | 31 +++++++++++++-
 gcc/tree-ssa-phiopt.cc                     | 48 ++++++++++++++--------
 2 files changed, 60 insertions(+), 19 deletions(-)
  

On Wed, Oct 30, 2024 at 5:34 AM Jovan Vukic <Jovan.Vukic@rt-rk.com> wrote:
>
> Thanks for the feedback on the first version of the patch. Accordingly:
>
> I have corrected the code formatting as requested. I added new tests to
> the existing file phi-opt-11.c, instead of creating a new one.

The previous practice has been adding a new file rather than appending
to the old one.
Though maybe this is a good exception to that rule. The main reason is
to compare between a much older testsuite run and a testsuite run
after this patch.
I am not so picky about this either way though; just bring up the
reasons why we did it differently before.

>
> I performed testing before and after applying the patch on the x86
> architecture, and I confirm that there are no new regressions.
>
> The logic and general code of the patch itself have not been changed.
>
> > So the A EQ/NE B expression, we can reverse A and B in the expression
> > and still get the same result. But don't we have to be more careful for
> > the TRUE/FALSE arms of the ternary? For BIT_AND we need ? a : b for
> > BIT_IOR we need ? b : a.
> >
> > I don't see that gets verified in the existing code or after your
> > change. I suspect I'm just missing something here. Can you clarify how
> > we verify that BIT_AND gets ? a : b for the true/false arms and that
> > BIT_IOR gets ? b : a for the true/false arms?
>
> I did not communicate this clearly last time, but the existing optimization
> simplifies the expression "(cond & (a == b)) ? a : b" to the simpler "b".
> Similarly, the expression "(cond & (a == b)) ? b : a" simplifies to "a".
>
> Thus, the existing and my optimization perform the following
> simplifications:
>
> (cond & (a == b)) ? a : b -> b
> (cond & (a == b)) ? b : a -> a
> (cond | (a != b)) ? a : b -> a
> (cond | (a != b)) ? b : a -> b
>
> For this reason, for BIT_AND_EXPR when we have A EQ B, it is sufficient to
> confirm that one operand matches the true/false arm and the other matches
> the false/true arm. In both cases, we simplify the expression to the third
> operand of the ternary operation (i.e., OP0 ? OP1 : OP2 simplifies to OP2).
> This is achieved in the value_replacement function after successfully
> setting the value of *code within the rhs_is_fed_for_value_replacement
> function to EQ_EXPR.
>
> For BIT_IOR_EXPR, the same check is performed for A NE B, except now
> *code remains NE_EXPR, and then value_replacement returns the second
> operand (i.e., OP0 ? OP1 : OP2 simplifies to OP1).

I had started to rewrite this part of phiopt to use match-and-simplify
and to handle these kind of things.
I attached the first set of patches to
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=51030 and redid a
simplified version attached here:
https://gcc.gnu.org/bugzilla/show_bug.cgi?id=61110 .
I am not blocking this patch but mentioning that a rewrite is on the
way (how long before I get back to this, I don't know yet).
Also as far as reviewing the patch as it stands alone.

+   && ((bit_expression_code == BIT_AND_EXPR
+        && gimple_assign_rhs_code (def1) == EQ_EXPR)
+       || (bit_expression_code == BIT_IOR_EXPR
+   && gimple_assign_rhs_code (def1) == NE_EXPR)))

This could be simplified down to I think:
`gimple_assign_rhs_code (def1) == (bit_expression_code ==
BIT_AND_EXPR) ? EQ_EXPR : NE_EXPR`

And then add an assert at the beginning of
rhs_is_fed_for_value_replacement checking to make sure
bit_expression_code is either `BIT_AND_EXPR` or `BIT_IOR_EXPR` or
maybe return false right if it is not BIT_AND_EXPR/BIT_IOR_EXPR.

Otherwise the change looks good to me (but I can't fully approve it).

Thanks,
Andrew Pinski

>
> 2024-10-30  Jovan Vukic  <Jovan.Vukic@rt-rk.com>
>
> gcc/ChangeLog:
>
>         * tree-ssa-phiopt.cc
>         (rhs_is_fed_for_value_replacement): Add a new optimization opportunity
>         for BIT_IOR_EXPR and a != b.
>         (operand_equal_for_value_replacement): Ditto.
>
> gcc/testsuite/ChangeLog:
>
>         * gcc.dg/tree-ssa/phi-opt-11.c: Add more tests.
>
>
> CONFIDENTIALITY: The contents of this e-mail are confidential and intended only for the above addressee(s). If you are not the intended recipient, or the person responsible for delivering it to the intended recipient, copying or delivering it to anyone else or using it in any unauthorized manner is prohibited and may be unlawful. If you receive this e-mail by mistake, please notify the sender and the systems administrator at straymail@rt-rk.com immediately.
  

On 10/30/24 6:33 AM, Jovan Vukic wrote:
> Thanks for the feedback on the first version of the patch. Accordingly:
> 
> I have corrected the code formatting as requested. I added new tests to
> the existing file phi-opt-11.c, instead of creating a new one.
> 
> I performed testing before and after applying the patch on the x86
> architecture, and I confirm that there are no new regressions.
> 
> The logic and general code of the patch itself have not been changed.
> 
>> So the A EQ/NE B expression, we can reverse A and B in the expression
>> and still get the same result. But don't we have to be more careful for
>> the TRUE/FALSE arms of the ternary? For BIT_AND we need ? a : b for
>> BIT_IOR we need ? b : a.
>>
>> I don't see that gets verified in the existing code or after your
>> change. I suspect I'm just missing something here. Can you clarify how
>> we verify that BIT_AND gets ? a : b for the true/false arms and that
>> BIT_IOR gets ? b : a for the true/false arms?
> 
> I did not communicate this clearly last time, but the existing optimization
> simplifies the expression "(cond & (a == b)) ? a : b" to the simpler "b".
> Similarly, the expression "(cond & (a == b)) ? b : a" simplifies to "a".
> 
> Thus, the existing and my optimization perform the following
> simplifications:
> 
> (cond & (a == b)) ? a : b -> b
> (cond & (a == b)) ? b : a -> a
> (cond | (a != b)) ? a : b -> a
> (cond | (a != b)) ? b : a -> b
This is well understood.  The key in my mind is that for AND we always 
select the FALSE arm.  For IOR we always select the TRUE arm.


> 
> For this reason, for BIT_AND_EXPR when we have A EQ B, it is sufficient to
> confirm that one operand matches the true/false arm and the other matches
> the false/true arm. In both cases, we simplify the expression to the third
> operand of the ternary operation (i.e., OP0 ? OP1 : OP2 simplifies to OP2).
Right.  No concerns there.

> This is achieved in the value_replacement function after successfully
> setting the value of *code within the rhs_is_fed_for_value_replacement
> function to EQ_EXPR.


> 
> For BIT_IOR_EXPR, the same check is performed for A NE B, except now
> *code remains NE_EXPR, and then value_replacement returns the second
> operand (i.e., OP0 ? OP1 : OP2 simplifies to OP1).
This is the part I'm struggling a bit with.  But I'm guessing you're 
referring to this code:

>      /* For NE_EXPR, we want to build an assignment result = arg where
>          arg is the PHI argument associated with the true edge.  For
>          EQ_EXPR we want the PHI argument associated with the false edge.  */
>       e = (code == NE_EXPR ? true_edge : false_edge);
If I understand everything correctly your assertion is that we'll only 
get here for AND/EQ_EXPR and IOR/NE_EXPR.  There's no way to get here 
for AND/NE_EXPR or IOR/EQ_EXPR?

Intuitively that's probably true since if it wasn't we'd likely already 
be generating incorrect code for AND with NE_EXPR.  But I'd like you to 
confirm my basic understanding.

Thanks,
jeff
  

On 11/02/24, Jeff Law wrote:
>This is well understood.  The key in my mind is that for AND we always
>select the FALSE arm.  For IOR we always select the TRUE arm.

Yes, I agree.

>>       e = (code == NE_EXPR ? true_edge : false_edge);
>If I understand everything correctly your assertion is that we'll only
>get here for AND/EQ_EXPR and IOR/NE_EXPR.  There's no way to get here
>for AND/NE_EXPR or IOR/EQ_EXPR?

If we examine the patch step by step, we can see that the function
rhs_is_fed_for_value_replacement enters the if block exclusively for
the combinations BIT_AND_EXPR/EQ_EXPR and BIT_IOR_EXPR/NE_EXPR. It is
only at this point that it returns true and sets the value of *code. This is
evident in the code:

>  if (TREE_CODE (rhs) == SSA_NAME)
>    {
>      ...
>      if (is_gimple_assign (def1)
>         && ((bit_expression_code == BIT_AND_EXPR
>              && gimple_assign_rhs_code (def1) == EQ_EXPR)
>             || (bit_expression_code == BIT_IOR_EXPR
>                 && gimple_assign_rhs_code (def1) == NE_EXPR)))
>       {
>         ...
>             *code = gimple_assign_rhs_code (def1);
>             return true;
>         ...
>       }
>    }
>  return false;

The function operand_equal_for_value_replacement only passes the value
it receives from rhs_is_fed_for_value_replacement to the call site.

At the call site, the returned value initializes the variable equal_p.

Thus, the return value is simply passed from
rhs_is_fed_for_value_replacement to the variable equal_p, and it is
true only in the situation of BIT_AND_EXPR/EQ_EXPR or
BIT_IOR_EXPR/NE_EXPR because that is how it is defined in
rhs_is_fed_for_value_replacement.

The patch only sets equal_p to true for the combinations AND/EQ and
OR/NE. These are the only two situations when equal_p becomes true as
a result of the patch, and therefore, only in those situations, as a
consequence of the patch, does the line of code you quoted execute:

> if (equal_p || maybe_equal_p)
> {
>       ...
>       e = (code == NE_EXPR ? true_edge : false_edge);
>       ...
>       if (...)
>       {
>               ...
>               if (equal_p)
>               {
>                       ...
>                       return 2;
>               }
>       }
>       else if (equal_p)
>       {
>               ...
>               return 1;
>       }
> }

Also, Mr. Pinski left a comment
(https://gcc.gnu.org/pipermail/gcc-patches/2024-November/667258.html)
and offered some suggestions about the patch.

He also mentioned that he is working on integrating the affected code into
match-and-simplify, so the rewrite is on the way. We can either move forward
with this patch or stop it. Either way, I’m fine with any decision made.


CONFIDENTIALITY: The contents of this e-mail are confidential and intended only for the above addressee(s). If you are not the intended recipient, or the person responsible for delivering it to the intended recipient, copying or delivering it to anyone else or using it in any unauthorized manner is prohibited and may be unlawful. If you receive this e-mail by mistake, please notify the sender and the systems administrator at straymail@rt-rk.com immediately.
  

[ Thanks for your patience.  It's been a long month ;-) ]


On 11/4/24 6:23 AM, Jovan Vukic wrote:
> On 11/02/24, Jeff Law wrote:
>> This is well understood.  The key in my mind is that for AND we always
>> select the FALSE arm.  For IOR we always select the TRUE arm.
> 
> Yes, I agree.
> 
>>>        e = (code == NE_EXPR ? true_edge : false_edge);
>> If I understand everything correctly your assertion is that we'll only
>> get here for AND/EQ_EXPR and IOR/NE_EXPR.  There's no way to get here
>> for AND/NE_EXPR or IOR/EQ_EXPR?
> 
> If we examine the patch step by step, we can see that the function
> rhs_is_fed_for_value_replacement enters the if block exclusively for
> the combinations BIT_AND_EXPR/EQ_EXPR and BIT_IOR_EXPR/NE_EXPR. It is
> only at this point that it returns true and sets the value of *code. This is
> evident in the code:
Thanks.  I was just looking for a yes/no to verify that my understanding 
was correct.  It's been ~20 years since I looked at this code in any 
significant way.

Your comments and re-reviewing the patch have addressed my concerns.


>
> 
> Also, Mr. Pinski left a comment
> (https://gcc.gnu.org/pipermail/gcc-patches/2024-November/667258.html)
> and offered some suggestions about the patch.
> 
> He also mentioned that he is working on integrating the affected code into
> match-and-simplify, so the rewrite is on the way. We can either move forward
> with this patch or stop it. Either way, I’m fine with any decision made.
I'd prefer to move forward.  We're definitely moving a lot of 
transformations into the match.pd framework and this one probably fits 
in there reasonably well.

It'll make a bit more work for Andrew as part of his desire to move this 
stuff into match.pd, but I don't see his work landing in this cycle and 
he's indicated he doesn't have a problem with your patch going forward 
at this time.


I'll push it into the tree after some additional light testing given 
its' been a month since the last discussion on this patch.

jeff