[Bug tree-optimization/94919] New: Failure to recognize max pattern

[Bug tree-optimization/94919] New: Failure to recognize max pattern

[gabravier at gmail dot com]

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

            Bug ID: 94919
           Summary: Failure to recognize max pattern
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: gabravier at gmail dot com
  Target Milestone: ---

int f(int x, int y)
{
    return ((x ^ y) & -(x >= y)) ^ y;
}

This can be optimized to `x >= y ? x : y`. LLVM makes this transformation, but
GCC does not.

[Bug tree-optimization/94919] Failure to recognize max pattern

[glisse at gcc dot gnu.org]

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

--- Comment #1 from Marc Glisse <glisse at gcc dot gnu.org> ---
This seems related to another one you reported, in the category: i&-b == b?i:0
(for b∈{0,1}). The first form has the advantage of no branch, while the second
is less obfuscated and simplifies more naturally (like when we combine x<0||y<0
to (x|y)<0 we get something shorter, but more obfuscated which can hinder other
optimizations). Here this equivalence gives the intermediate step of
(x>=y?x^y:0)^y.

I didn't see if you posted it somewhere, but I assume those tests come from the
llvm testsuite? Did people really hit such weird code in the wild and add them
one by one to llvm? Or was there some automated process involved ? I could
imagine looking at all the expressions of a certain size using some list of
operators and only 2 variables (and maybe a few constants), compute the table
of values for a small type (a 3-bit integer?), put them in a hash table, and
study collisions? Generating completely automatically the list of
transformations may be a bit hard though. And handling undefined cases (like
signed overflow) complicates things, since we are not looking for exact matches
there.

[Bug tree-optimization/94919] Failure to recognize max pattern

[gabravier at gmail dot com]

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

--- Comment #2 from Gabriel Ravier <gabravier at gmail dot com> ---
Essentially, what I've been doing in my spare time for the past few weeks is
looking at random pieces of code all over the internet, looking at the results
trunk gcc/clang give (usually on x86-64 (though I've been thinking about
looking at arm and other architectures), with flags like -Ofast
-march=tigerlake) and seeing whether GCC or LLVM optimizes them better than the
other (and making appropriate bug reports). Some of these are from actual
projects, some are from websites listing bithacks, some are from books like
Hacker's Delight, some were written by myself when studying the code from those
above sources, and finally a few of them were from testsuites in either LLVM or
GCC (though those are rarer, especially for LLVM, since it takes time to
convert them from LLVM bytecode to something I can compile with both GCC and
Clang).

For this particular bug report, I believe this is *probably* from somewhere in
Hacker's Delight.

[Bug tree-optimization/94919] Failure to recognize max pattern

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
   Last reconfirmed|                            |2020-05-25
     Ever confirmed|0                           |1
           Severity|normal                      |enhancement
           Assignee|unassigned at gcc dot gnu.org      |pinskia at gcc dot gnu.org

--- Comment #3 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
The transformation we should do is:
((x ^ y) & -(Z)) ^ y

Where Z has the range of [0...1] (bool).
To:
Z ? x : y

I will look into adding this to match.pd and all.

[Bug tree-optimization/94919] Failure to recognize max pattern

[gabravier at gmail dot com]

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

Gabriel Ravier <gabravier at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         Resolution|---                         |FIXED
             Status|ASSIGNED                    |RESOLVED

--- Comment #4 from Gabriel Ravier <gabravier at gmail dot com> ---
Looks like this is now recognized by GCC 11, I can't really identify what exact
patch does this but it was fixed in some way since I now get optimal code
generation.