[Bug tree-optimization/94787] New: Failure to detect single bit popcount pattern

[Bug tree-optimization/94787] New: Failure to detect single bit popcount pattern

[gabravier at gmail dot com]

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

            Bug ID: 94787
           Summary: Failure to detect single bit popcount pattern
           Product: gcc
           Version: 10.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: ---

bool f(unsigned v)
{
    return v && !(v & (v - 1));
}

Depending on the supported architecture, we may want to optimize this to
`__builtin_popcount(v) == 1;` (when a fast hardware instruction is available).
For example, on x86, this should make programs faster when `popcnt` is
available. LLVM already does this.

Comparison with x86 `-mpopcnt` here : https://godbolt.org/z/M6f28d

[Bug tree-optimization/94787] Failure to detect single bit popcount pattern

[gabravier at gmail dot com]

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

--- Comment #1 from Gabriel Ravier <gabravier at gmail dot com> ---
Inversely, I'd also suggest doing the opposite. That is, if there is no
hardware popcount instruction, `__builtin_popcount(v) == 1` should be optimized
to `v && !(v & (v - 1))`

[Bug tree-optimization/94787] Failure to detect single bit popcount pattern

[rguenth at gcc dot gnu.org]

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

Richard Biener <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Last reconfirmed|                            |2020-04-27
             Status|UNCONFIRMED                 |NEW
     Ever confirmed|0                           |1

--- Comment #2 from Richard Biener <rguenth at gcc dot gnu.org> ---
Confirmed.  match.pd plus RTL expansion helper.

[Bug tree-optimization/94787] Failure to detect single bit popcount pattern

[wilco at gcc dot gnu.org]

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

Wilco <wilco at gcc dot gnu.org> changed:

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

--- Comment #3 from Wilco <wilco at gcc dot gnu.org> ---
(In reply to Gabriel Ravier from comment #1)
> Inversely, I'd also suggest doing the opposite. That is, if there is no
> hardware popcount instruction, `__builtin_popcount(v) == 1` should be
> optimized to `v && !(v & (v - 1))`

I actually posted a patch for this and popcount(x) > 1 given the reverse
transformation is faster on all targets - even if they have popcount
instruction (since they are typically more expensive). This is true on x86 as
well, (x-1) <u (x & -x) is never slower than using popcount.

So I suggest not to have LLVM emit popcount for this is there a popcount
instruction since that is non-optimal for pretty much every target.

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

[Bug middle-end/94787] Failure to detect single bit popcount pattern

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement
          Component|tree-optimization           |middle-end

[Bug middle-end/94787] Failure to detect single bit popcount pattern

[tavianator at gmail dot com]

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

Tavian Barnes <tavianator at gmail dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |tavianator at gmail dot com

--- Comment #4 from Tavian Barnes <tavianator at gmail dot com> ---
(In reply to Wilco from comment #3)
> I actually posted a patch for this and popcount(x) > 1 given the reverse
> transformation is faster on all targets - even if they have popcount
> instruction (since they are typically more expensive). This is true on x86
> as well, (x-1) <u (x & -x) is never slower than using popcount.

There's also these:

(x-1) <u (x ^ (x-1))

-x >u (x ^ -x)

[Bug middle-end/94787] Failure to detect single bit popcount pattern

[pinskia at gcc dot gnu.org]

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

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

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Note the expansion part is handled by r14-5612, r14-5613, and r14-6940 .

So now we just need the match part which I will handle for 15.

[Bug middle-end/94787] Failure to detect single bit popcount pattern

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #5)
> Note the expansion part is handled by r14-5612, r14-5613, and r14-6940 .
> 
> So now we just need the match part which I will handle for 15.

Actually the expansion part is not fully complete.
```
int f(int a)
{
        return __builtin_popcount(a) <= 1;
}

int f1(int a)
{
        return __builtin_popcount(a) == 1;
}
```

f1 is handled but f is not.
f should expand to `!(v & (v - 1))`.

The other match patterns needed:
```
int g(int a)
{
        if (a == 0) return 0;
        return __builtin_popcount(a) <= 1;
}

int g1(int a)
{
        if (a == 0) return 1;
        return __builtin_popcount(a) <= 1;
}
```

g should be transformed into just `__builtin_popcount(a) == 1`
and g1 should be transformed into just `__builtin_popcount(a) <= 1`.
Both during phi-opt.

[Bug middle-end/94787] Failure to detect single bit popcount pattern

[pinskia at gcc dot gnu.org]

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

--- Comment #7 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
And add:
```
int h(int a)
{
        if (a == 0) return 0;
        return __builtin_popcount(a) == 1;
}

int h1(int a)
{
        if (a == 0) return 1;
        return __builtin_popcount(a) == 1;
}
```

h should be just `__builtin_popcount(a) == 1`.
While h1 should be just `__builtin_popcount(a) <= 1`.