[Bug tree-optimization/57755] New: Improve fold_binary_op_with_conditional_arg

[Bug tree-optimization/57755] New: Improve fold_binary_op_with_conditional_arg

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57755

            Bug ID: 57755
           Summary: Improve fold_binary_op_with_conditional_arg
           Product: gcc
           Version: 4.9.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: glisse at gcc dot gnu.org

Hello,

fold_binary_op_with_conditional_arg performs the following:

   Transform `a + (b ? x : y)' into `b ? (a + x) : (a + y)'.
   Transform, `a + (x < y)' into `(x < y) ? (a + 1) : (a + 0)'.

It gives up in this first case (arg is 'a' above):

  if (!TREE_CONSTANT (arg)
      && (TREE_SIDE_EFFECTS (arg)
          || TREE_CODE (arg) == COND_EXPR || TREE_CODE (arg) == VEC_COND_EXPR
          || TREE_CONSTANT (true_value) || TREE_CONSTANT (false_value)))
    return NULL_TREE;

and after folding both branches:

  if (!TREE_CONSTANT (arg) && !TREE_CONSTANT (lhs) && !TREE_CONSTANT (rhs))
    return NULL_TREE;

This seems suboptimal. On the one hand, for ((a<b)?a:c)*3/2+1, it distributes
the operations to a < b ? (a * 3) / 2 + 1 : (c * 3) / 2 + 1 (we can add as many
operations with constants as we want) and this isn't completely undone later
(partially with -Os, not at all with -O3). On the other hand, for
((a<2)?-1u:0)&b, it gives up instead of producing (a<2)?b:0.

We must be careful with recursions (PR55219) and with folders performing the
reverse transformations, but I think we should be able to optimize:
(((a<2)?-1:0)&((b<1)?-1:0))!=0

(obviously, the title doesn't prevent from moving this functionality to gimple)

[Bug tree-optimization/57755] Improve fold_binary_op_with_conditional_arg

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=57755

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at gcc dot gnu.org      |glisse at gcc dot gnu.org

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
Created attachment 30408
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=30408&action=edit
patch

This patch seems to help for the testcases in this PR and passes the testsuite
(with one XPASS). I'll add some testcases and post it to gcc-patches later.

[Bug tree-optimization/57755] Improve fold_binary_op_with_conditional_arg

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57755

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2023-05-05
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
I think we should optimize this testcases slightly different from "improving"
fold_binary_op_with_conditional_arg (I think
fold_binary_op_with_conditional_arg 
 should go away even but that is a different story).

Let's start with:
```
int f(int a,int b){
  return (((a<=3)?-1:0)&((b<=2)?-1:0))!=0;
}
```
After ccp1 we have:
  # iftmp.1_4 = PHI <-1(4), 0(5)>
  _1 = iftmp.0_3 & iftmp.1_4;

But really that should just become:
# _1 = PHI <iftmp.0_3(4), 0(5)>

PRE does that but that is way too late.

Anyways we also have another chance of doing something:
  _1 = _9 ? _14 : 0;
  _2 = _1 != 0;

We could recognize that to be:
_t = _14 != 0
_2 = _9 & _t


For the full IR we have:
  _12 = a_5(D) <= 3;
  _13 = (int) _12;
  _14 = -_13;
  _9 = b_6(D) <= 2;
  _1 = _9 ? _14 : 0;
  _2 = _1 != 0;
  _7 = (int) _2;

Which then gets translated into:
  _12 = a_5(D) <= 3;
  _13 = (int) _12; // dead
  _14 = -_13; // dead
  _9 = b_6(D) <= 2;
  _t = _14 != 0 <-- _t = _13 != 0 <-- _12 != 0 --> _12
  _2 = _9 & _t
  _7 = (int) _2;

Which gets translated into just:
  _12 = a_5(D) <= 3;
  _9 = b_6(D) <= 2;
  _2 = _9 & _12
  _7 = (int) _2;

Which is exactly as requested.

I think I will add the pattern to match:
(cmp (cond @1 @2 CST@3) CST@4) -> (bit_ior (bit_and @1 (cmp @2 @4)) (bit_and
(bit_not @1) (cmp @3 @4)))

Not (cmp @3 @4) will simplify to either true or false which allows
the whole thing to simplify to either @1 & (cmp @2 @4) or false.

[Bug tree-optimization/57755] Improve fold_binary_op_with_conditional_arg

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57755

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
unsigned g(unsigned a,unsigned b,unsigned c){
  return ((a<b)?a:c)*3/42+1;
}

has a few related bug reports already.

Last example from the patch:
unsigned h(unsigned a,unsigned b){
  return ((a<=42)?b:0)&b;
}
PRE is able to optimize this so I don't think it should be done (unless we have
another pass which does similar to what I suggested in the first part of
comment #4).

[Bug tree-optimization/57755] Improve fold_binary_op_with_conditional_arg

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57755

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #4)
> I think we should optimize this testcases slightly different from
> "improving" fold_binary_op_with_conditional_arg (I think
> fold_binary_op_with_conditional_arg 
>  should go away even but that is a different story).
> 
> Let's start with:
> ```
> int f(int a,int b){
>   return (((a<=3)?-1:0)&((b<=2)?-1:0))!=0;
> }
> ```
> After ccp1 we have:
>   # iftmp.1_4 = PHI <-1(4), 0(5)>
>   _1 = iftmp.0_3 & iftmp.1_4;
> 
> But really that should just become:
> # _1 = PHI <iftmp.0_3(4), 0(5)>
> 
> PRE does that but that is way too late.

Actually another way of fixing the above is we have in forwprop3:
  _14 = a_5(D) <= 3;
  _17 = (int) _14;
  _18 = -_17;
  _9 = b_6(D) <= 2;
  _12 = (int) _9;
  _1 = _12 * _18;
  _2 = _1 != 0;
  _7 = (int) _2;

Well we can see (_12 * _18) != 0 is really _12 != 0 & _18 != 0 which can be
done easier as _12 has a range of [0,1].

If we do that then in forwprop3 we get:
  _9 = b_6(D) <= 2;
  _3 = a_5(D) <= 3;
  _2 = _3 & _9;
  _7 = (int) _2;

which what we want ...

That is that transformation is what we have in bug 110992 comment #9 . the
reason for the check of [0,1] is that we know there would be no overflows and
can be safely done no matter what.

[Bug tree-optimization/57755] Improve fold_binary_op_with_conditional_arg

[pinskia at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=57755

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Severity|normal                      |enhancement
           See Also|                            |https://gcc.gnu.org/bugzill
                   |                            |a/show_bug.cgi?id=94274

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Undoing the badness of fold_binary_op_with_conditional_arg is PR 94274.

I have a patch which handles what fold_binary_op_with_conditional_arg is trying
to solve in phiopt though currently only handles constants but I suspect I
could extend it to ssa names too ..