[Bug tree-optimization/107043] New: range information not used in popcount

[Bug tree-optimization/107043] New: range information not used in popcount

[drepper.fsp+rhbz at gmail dot com]

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

            Bug ID: 107043
           Summary: range information not used in popcount
           Product: gcc
           Version: 13.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 code could be compiled to a simple return of the value 1 but it isn't
because the range information for n does not survive long enough.

int g(int n)
{
  n &= 0x8000;
  if (n == 0)
    return 1;
  return __builtin_popcount(n);
}

The code generated today is lengthy:

   0:   81 e7 00 80 00 00       and    $0x8000,%edi
   6:   ba 01 00 00 00          mov    $0x1,%edx
   b:   89 f8                   mov    %edi,%eax
   d:   c1 e8 0f                shr    $0xf,%eax
  10:   85 ff                   test   %edi,%edi
  12:   0f 44 c2                cmove  %edx,%eax
  15:   c3                      ret

[Bug tree-optimization/107043] range information not used in popcount

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
   Last reconfirmed|                            |2022-09-26
     Ever confirmed|0                           |1
           Severity|normal                      |enhancement

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> ---
Confirmed. The following two should be optimized too:
int g0(int n)
{
  int n1 = n & 0x8000;
  if (n1 == 0)
    return 1;
  // n1 will be 0x8000 here.
  return (n1 >> 15) & 0x1;
}

int g1(int n)
{
  int n1 = n & 0x8000;
  if (n1 == 0)
    return 1;
  // n>>15 will be xxxxxx1 here.
  return (n >> 15) & 0x1;
}

[Bug tree-optimization/107043] range information not used in popcount

[drepper.fsp+rhbz at gmail dot com]

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

--- Comment #2 from Ulrich Drepper <drepper.fsp+rhbz at gmail dot com> ---
My original example and Andrew's g0 are handled by Aldy's patches

2022-09-26  Aldy Hernandez  <aldyh@redhat.com>

        PR tree-optimization/107009
        * range-op.cc (operator_bitwise_and::op1_range): Optimize 0 = x & MASK.
        (range_op_bitwise_and_tests): New test.

2022-09-26  Aldy Hernandez  <aldyh@redhat.com>

        PR tree-optimization/107009
        * tree-ssa-dom.cc
        (dom_opt_dom_walker::set_global_ranges_from_unreachable_edges):
        Iterate over exports.


The g1 test case isn't handled, yet.

[Bug tree-optimization/107043] range information not used in popcount

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

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

--- Comment #3 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
(In reply to Andrew Pinski from comment #1)

> int g1(int n)
> {
>   int n1 = n & 0x8000;
>   if (n1 == 0)
>     return 1;
>   // n>>15 will be xxxxxx1 here.
>   return (n >> 15) & 0x1;
> }

Interestingly, getting this one requires us to track something completely
different, the bits that are *definitely* set.

[Right now we track the nonzero mask, which is a misnomer because we're not
tracking bits are nonzero but the bits that *may* be nonzero.  Or more
precisely the inverse of the bits that are known to be 0.  For example, a
"nonzero" mask of 0xfffffff0 means the least significant 8 bits are known to be
zero, and the rest of the bits are unknown.  So we're tracking the "and mask"
of a number?  Or the maybe_nonzero bits?  The reason for the name is because
legacy VRP had this name.]

To get the above, we'd need to track the bits that are definitely 1 (the "or
mask" of a number?).  For example, on the 2->4 edge we'd need to know that n_3
has the 0x8000 bit set:

  <bb 2> :
  n1_4 = n_3(D) & 32768;
  if (n1_4 == 0)
    goto <bb 3>; [INV]
  else
    goto <bb 4>; [INV]

  <bb 3> :
  goto <bb 5>; [INV]

  <bb 4> :
  _1 = n_3(D) >> 15;
  _5 = _1 & 1;

  <bb 5> :
  # _2 = PHI <1(3), _5(4)>
  return _2;

What we're looking for is solving n_3:

[not-zero] = n_3 & 32768

which should give us:

[-INF,-1][32768, +INF] ORMASK [0x8000]

or whatever the hell we want to call it.  I hate these names.  Please someone,
come up with a name that makes sense to us all!

Andrew M and I had a plan for this earlier this cycle, but got sidetracked by
floats.  What we'd need is a way to track or-mask's in addition to and-masks.

There's actual infrastructure missing here, but it should be as easy as what we
did for "nonzero" tracking in commit 4e82205b68024f5c1a9006fe2b62e1a0fa7f1245
(plus supporting patches).  Basically we need to add a slot for the or-mask in
the irange, add union/intersect code, and then add some glue in range-ops to
solve:

1 = x & mask
x = y | mask
etc etc.

Thanks for the testcase, it's quite useful.

[Bug tree-optimization/107043] range information not used in popcount

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #4 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
I think ccp tracks instead a pair of value and mask,
X & ~mask == value & ~mask.
So, set bits in the mask mean don't know if the bit is set or clear,
clear bits mean we know it and the corresponding bit in value says if it is
known to be zero or non-zero.
That way we can express these 5 bits are known to be zero and these other 3
bits are known to be set, the rest unknown.

[Bug tree-optimization/107043] range information not used in popcount

[cvs-commit at gcc dot gnu.org]

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

--- Comment #5 from CVS Commits <cvs-commit at gcc dot gnu.org> ---
The master branch has been updated by Aldy Hernandez <aldyh@gcc.gnu.org>:

https://gcc.gnu.org/g:7a5e47658904de9dc90f1292f3f69769177706f9

commit r14-2480-g7a5e47658904de9dc90f1292f3f69769177706f9
Author: Aldy Hernandez <aldyh@redhat.com>
Date:   Thu Jul 6 10:55:46 2023 +0200

    [range-op] Take known mask into account for bitwise ands [PR107043]

            PR tree-optimization/107043

    gcc/ChangeLog:

            * range-op.cc (operator_bitwise_and::op1_range): Update bitmask.

    gcc/testsuite/ChangeLog:

            * gcc.dg/tree-ssa/pr107043.c: New test.

[Bug tree-optimization/107043] range information not used in popcount

[aldyh at gcc dot gnu.org]

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

Aldy Hernandez <aldyh at gcc dot gnu.org> changed:

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

--- Comment #6 from Aldy Hernandez <aldyh at gcc dot gnu.org> ---
Finally... fixed in trunk :).