[Bug tree-optimization/103857] New: implement ternary without jump (and comparison)

[Bug tree-optimization/103857] New: implement ternary without jump (and comparison)

[drepper.fsp+rhbz at gmail dot com]

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

            Bug ID: 103857
           Summary: implement ternary without jump (and comparison)
           Product: gcc
           Version: 12.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: drepper.fsp+rhbz at gmail dot com
  Target Milestone: ---

This test case is derived from actual code and I expect it to be not uncommon
in general.  Maybe not exactly in this form but perhaps the matcher can catch a
few more cases.

Take this code:

extern void g(int);
void f1(int* a, int b, int c)
{
  for (unsigned i = 0; i < 100; ++i)
    g(a[i] == b ? c : b);
}
void f2(int* a)
{
  for (unsigned i = 0; i < 100; ++i)
    g(a[i] == 42 ? 10 : 42);
}


The function 'g' is called in each loop with one of two values which is the
opposite from the one that is match in the condition of the ternary operation. 
This allows the respective loops to be rewritten as

  for (unsigned i = 0; i < 100; ++i)
    g(a[i] ^ c ^ b);

and

  for (unsigned i = 0; i < 100; ++i)
    g(a[i] ^ 10 ^ 42);

In the former case the c ^ b operation can be hoisted.

This should be faster and smaller in pretty much all situations and on all
platforms.

[Bug tree-optimization/103857] implement ternary without jump (and comparison)

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |jakub at gcc dot gnu.org

--- Comment #1 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I don't think that's equivalent.  For a[i] equal to b it will be and similarly
it will be for a[i] equal to c, but not for all the other values.
E.g. 13 == 42 ? 24 : 42 is 42, but 13 ^ (24 ^ 42) is 63.
So, we could do this only if something assures us that a[i] only has 2 possible
values, either equal to b or to c.  So that would rule out non-constant b or c,
perhaps it could be done if value range is two adjacent constants equal to b
and c, or perhaps if the non-zero bits has a single bit and one of b or c is 0
and the other one is that non-zero bitmask of the other comparison operand.

[Bug tree-optimization/103857] implement ternary without jump (and comparison)

[drepper.fsp+rhbz at gmail dot com]

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

--- Comment #2 from Ulrich Drepper <drepper.fsp+rhbz at gmail dot com> ---
(In reply to Jakub Jelinek from comment #1)
> I don't think that's equivalent.

You're right, I tried to generalize the code and failed.  I my actual case this
was a single variable the compiler saw the assignments of.  Adding

  if (a[i] != 42 && a[i] != 10)
    __builtin_unreachable();

etc could simulate this.

[Bug tree-optimization/103857] implement ternary without jump (and comparison)

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
           Keywords|                            |missed-optimization
     Ever confirmed|0                           |1
           Severity|normal                      |enhancement
   Last reconfirmed|                            |2021-12-29

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Reduced testcase:
int f(int a, int b, int c)
{
  if (a != b && a != c) __builtin_unreachable();
  return a == b ? b : c;
}

This should just translate into:
int f1(int a, int b, int c)
{
  if (a != b && a != c) __builtin_unreachable();
  return a;
}

The ^ part is not needed really if it is just selecting between two values.

[Bug tree-optimization/103857] implement ternary without jump (and comparison)

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #3)
> Reduced testcase:
> int f(int a, int b, int c)
> {
>   if (a != b && a != c) __builtin_unreachable();
>   return a == b ? b : c;
> }
> 
> This should just translate into:
> int f1(int a, int b, int c)
> {
>   if (a != b && a != c) __builtin_unreachable();
>   return a;
> }
> 
> The ^ part is not needed really if it is just selecting between two values.

Oh it was swapping around the two values:

int f(int a, int b, int c)
{
  if (a != b && a != c) __builtin_unreachable();
  return a == b ? c : b;
}
int f1(int a, int b, int c)
{
  if (a != b && a != c) __builtin_unreachable();
  return a ^ b ^ c;
}

And then the ^ are needed.