[Bug c/103660] New: Sub-optimal code with relational operators

[Bug c/103660] New: Sub-optimal code with relational operators

[david at westcontrol dot com]

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

            Bug ID: 103660
           Summary: Sub-optimal code with relational operators
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: c
          Assignee: unassigned at gcc dot gnu.org
          Reporter: david at westcontrol dot com
  Target Milestone: ---

I recently looked at some of gcc's "if-conversions" and other optimisations of
expressions involving relational operators - something people might use when
trying to write branchless code.  I know that it is often best to write in the
clearest way, including branches, and let the compiler handle the optimisation.
 But people do try to do this kind of thing by hand.

I tested 6 examples of ways to write a simple "min" function:


int min1(int a, int b) {
    if (a < b) return a; else return b;
}

int min2(int a, int b) {
    return (a < b) ? a : b;
}

int min3(int a, int b) {
    return (a < b) * a | (a >= b) * b;
}

int min4(int a, int b) {
    return (a < b) * a + (a >= b) * b;
}

int min5(int a, int b) {
    const int c = a < b;
    return c * a + (1 - c) * b;
}

int min6(int a, int b) {
    const bool c = a < b;
    return c * a + !c * b;
}


gcc happily optimises the first two versions.  For the next two, it uses
conditional moves for each half of the expression, then combines them with "or"
or "add".  For version 5, it generates two multiply instructions, and version 6
is even worse in trunk (gcc 12).  This last one is a regression - gcc 11
generates the same code for version 6 as for version 4 (not optimal, but not as
bad).

For comparison, clang 5+ generates optimal code for all versions.  I have tried
a number of different targets (godbolt is wonderful for this stuff), with
similar results.

[Bug tree-optimization/103660] Sub-optimal code with relational operators

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2021-12-12
                 CC|                            |pinskia at gcc dot gnu.org
             Status|UNCONFIRMED                 |NEW
           Severity|normal                      |enhancement
     Ever confirmed|0                           |1

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
For min3/min4:
  _3 = a_7(D) < b_8(D) ? a_7(D) : 0;
  _6 = a_7(D) >= b_8(D) ? b_8(D) : 0;
  _9 = _3 | _6;


A pattern like:
(for op (add bit_ior)
 (simplify
  (op:c
   (cond (lt @0 @1) @0 integer_zero_p@2)
   (cond (ge @0 @1) @0 @2))
  (min @0 @1)))

And make one for the others too.

min5/6 is more complex:
min5:
  _1 = a_5(D) < b_6(D);
  c_7 = (const int) _1;
  _2 = a_5(D) * c_7;
  _3 = 1 - c_7;
  _4 = _3 * b_6(D);
  _8 = _2 + _4;

min6:
  _5 = a_1(D) < b_2(D);
  _6 = (int) _5;
  _7 = a_1(D) * _6;
  _8 = a_1(D) >= b_2(D);
  _9 = (int) _8;
  _10 = b_2(D) * _9;
  _11 = _7 + _10;

I think I have a patch which helps these, I have to finish it up and then it
goes back to min3/min4 issue.

[Bug tree-optimization/103660] Sub-optimal code with relational operators

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Actually:
```
(for (op plus bit_ior bit_xor)
 (simplify
  (op (cond @0 @1 integer_zero_p)
      (cond @2 @3 integer_zero_p))
  (with { bool wascmp; }
   (if (bitwise_inverted_equal_p (@0, @2, wascmp))
    (cond @0 @1 @3)
   )
  )
 )
)
```
Should fix this.

Well that replaces the pattern that was added in r13-4620-g4d9db4bdd458 and
extends it to for plus and bit_xor.

[Bug tree-optimization/103660] Sub-optimal code with relational operators

[pinskia at gcc dot gnu.org]

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

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #2)
> Actually:
> ```
> (for (op plus bit_ior bit_xor)
>  (simplify
>   (op (cond @0 @1 integer_zero_p)
>       (cond @2 @3 integer_zero_p))
>   (with { bool wascmp; }
>    (if (bitwise_inverted_equal_p (@0, @2, wascmp))
>     (cond @0 @1 @3)
>    )
>   )
>  )
> )
> ```
> Should fix this.
> 
> Well that replaces the pattern that was added in r13-4620-g4d9db4bdd458 and
> extends it to for plus and bit_xor.

Note I think the patterns added in that revision were incorrect:
+   (cond (cmp@0  @01 @02) @3 zerop)
+   (cond (icmp@4 @01 @02) @5 zerop))

allows for @1 and @2 (which by the way 01 and 02 is; just using base 8 rather
than base 10).

[Bug tree-optimization/103660] Sub-optimal code with relational operators

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #3)
> Note I think the patterns added in that revision were incorrect:
> +   (cond (cmp@0  @01 @02) @3 zerop)
> +   (cond (icmp@4 @01 @02) @5 zerop))
> 
> allows for @1 and @2 (which by the way 01 and 02 is; just using base 8
> rather than base 10).

for floating point and guess what !(a < b) for floating point is not the same
as (a >= b). I will file a bug about that ...

[Bug tree-optimization/103660] Sub-optimal code with relational operators

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Two more cases, this time with XOR (^):
```
int min7(int a, int b) {
    const int c = a < b;
    return (c * a) ^ ((1 - c) * b);
}

int min8(int a, int b) {
    const bool c = a < b;
    return (c * a) ^ (!c * b);
}
```

Because `0 ^ a` is `a`. Should be easy to change the pattern to accept all 3
(XOR, IOR and PLUS) instead of just IOR.

[Bug tree-optimization/103660] Sub-optimal code with relational operators

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 58915
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58915&action=edit
scalar gimple testcases

Note f2 is not optimized either.

It should be simple as:
(simplify
 (op:c
  (cnd @0 @00 integer_zero_p)
  (cnd @0 integer_zero_p @01))
 (cnd @0 @00 @01))

[Bug tree-optimization/103660] Sub-optimal code with relational operators

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Created attachment 58916
  --> https://gcc.gnu.org/bugzilla/attachment.cgi?id=58916&action=edit
vector testcases

Note f2 is handled for all OP because of:
```
/* Sink binary operation to branches, but only if we can fold it.  */
(for op (tcc_comparison plus minus mult bit_and bit_ior bit_xor
         lshift rshift rdiv trunc_div ceil_div floor_div round_div
         trunc_mod ceil_mod floor_mod round_mod min max)
/* (c ? a : b) op (c ? d : e)  -->  c ? (a op d) : (b op e) */
 (simplify
  (op (vec_cond:s @0 @1 @2) (vec_cond:s @0 @3 @4))
  (if (TREE_CODE_CLASS (op) != tcc_comparison
       || types_match (type, TREE_TYPE (@1))
       || expand_vec_cond_expr_p (type, TREE_TYPE (@0), ERROR_MARK)
       || (optimize_vectors_before_lowering_p ()
           /* The following is optimistic on the side of non-support, we are
              missing the legacy vcond{,u,eq} cases.  Do this only when
              lowering will be able to fixup..  */
           && !expand_vec_cond_expr_p (TREE_TYPE (@1),
                                       TREE_TYPE (@0), ERROR_MARK)))
   (vec_cond @0 (op! @1 @3) (op! @2 @4))))
```

I do think we should handle this without that pattern though.
Note also I had to use another variable for f2 to hold 0 because otherwise we
switch around the VEC_COND to be similar to f1.

[Bug tree-optimization/103660] Sub-optimal code with relational operators

[pinskia at gcc dot gnu.org]

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

--- Comment #8 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Patch posted for the original testcases:
https://gcc.gnu.org/pipermail/gcc-patches/2024-August/660221.html

[Bug tree-optimization/103660] Sub-optimal code with relational operators

[cvs-commit at gcc dot gnu.org]

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

--- Comment #9 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:82a2f1386b2e8c951e910e1096a04bed21bbd39b

commit r15-3039-g82a2f1386b2e8c951e910e1096a04bed21bbd39b
Author: Andrew Pinski <quic_apinski@quicinc.com>
Date:   Mon Aug 12 15:13:04 2024 -0700

    testsuite: Add testcases for part of PR 103660

    IOR part of the bug report was fixed by r13-4620-g4d9db4bdd458 but
    that added only aarch64 specific testcases. This adds 4
    generic testcases for this to check to make sure they are optimized.
    The C++ testcases are the vector type versions.

            PR tree-optimization/103660

    gcc/testsuite/ChangeLog:

            * g++.dg/tree-ssa/pr103660-0.C: New test.
            * g++.dg/tree-ssa/pr103660-1.C: New test.
            * gcc.dg/tree-ssa/pr103660-0.c: New test.
            * gcc.dg/tree-ssa/pr103660-1.c: New test.

    Signed-off-by: Andrew Pinski <quic_apinski@quicinc.com>

[Bug tree-optimization/103660] Sub-optimal code with relational operators

[cvs-commit at gcc dot gnu.org]

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

--- Comment #10 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:b73373520f0ed5d131d2cd6ee9078939a98d7a0d

commit r15-3040-gb73373520f0ed5d131d2cd6ee9078939a98d7a0d
Author: Andrew Pinski <quic_apinski@quicinc.com>
Date:   Mon Aug 12 16:00:45 2024 -0700

    match: extend the `((a CMP b) ? c : 0) | ((a CMP' b) ? d : 0)` patterns to
support ^ and + [PR103660]

    r13-4620-g4d9db4bdd458 Added a few patterns and some of them can be
extended to support XOR and PLUS.
    This extends the patterns to support XOR and PLUS instead of just IOR.

    Bootstrapped and tested on x86_64-linux-gnu.

            PR tree-optimization/103660

    gcc/ChangeLog:

            * match.pd (`((a CMP b) ? c : 0) | ((a CMP' b) ? d : 0)`): Extend
to support
            XOR and PLUS.

    gcc/testsuite/ChangeLog:

            * g++.dg/tree-ssa/pr103660-2.C: New test.
            * g++.dg/tree-ssa/pr103660-3.C: New test.
            * gcc.dg/tree-ssa/pr103660-2.c: New test.
            * gcc.dg/tree-ssa/pr103660-3.c: New test.

    Signed-off-by: Andrew Pinski <quic_apinski@quicinc.com>

[Bug tree-optimization/103660] Sub-optimal code with relational operators

[cvs-commit at gcc dot gnu.org]

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

--- Comment #11 from GCC Commits <cvs-commit at gcc dot gnu.org> ---
The trunk branch has been updated by Andrew Pinski <pinskia@gcc.gnu.org>:

https://gcc.gnu.org/g:eface71c18caea3009ddc1ac624cb41647e9d5c4

commit r15-3041-geface71c18caea3009ddc1ac624cb41647e9d5c4
Author: Andrew Pinski <quic_apinski@quicinc.com>
Date:   Mon Aug 12 17:37:32 2024 -0700

    Match: Add pattern for `(a ? b : 0) | (a ? 0 : c)` into `a ? b : c`
[PR103660]

    This adds a pattern to convert `(a ? b : 0) | (a ? 0 : c)` into `a ? b : c`
    which is simplier. It adds both for cond and vec_cond; even though vec_cond
is
    handled via a different pattern currently but requires extra steps for
matching
    so this should be slightly faster.

    Also handle it for xor and plus too since those can be handled the same
way.

    Bootstrapped and tested on x86_64-linux-gnu with no regressions.

            PR tree-optimization/103660

    gcc/ChangeLog:

            * match.pd (`(a ? b : 0) | (a ? 0 : c)`): New pattern.

    gcc/testsuite/ChangeLog:

            * g++.dg/tree-ssa/pr103660-4.C: New test.
            * gcc.dg/tree-ssa/pr103660-4.c: New test.

    Signed-off-by: Andrew Pinski <quic_apinski@quicinc.com>

[Bug tree-optimization/103660] Sub-optimal code with relational operators

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED
   Target Milestone|---                         |15.0

--- Comment #12 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Fixed for GCC 15.