[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 ...