[Bug tree-optimization/94800] Failure to optimize yet another popcount idiom

[jakub at gcc dot gnu.org]

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

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

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

--- Comment #2 from Jakub Jelinek <jakub at gcc dot gnu.org> ---
Rather than adding yet another popcount pattern, I wonder if we shouldn't just
canonicalize the x + (x << cst) to x * (1 + (1 << cst)) and
(x << cst1) + (x << cst2) to x * ((1 << cst1) + (1 << cst2)), and this PR would
fall naturally out of that.  We already have code to emit the best
multiplication expansion and if it is not the fastest on some target, we should
tweak it anyway, because users could write the multiplication by constant.

Testcase to consider:
unsigned long long int
foo (unsigned long long int x)
{
  unsigned long long int a = x + (x << 8);
  unsigned long long int b = a + (a << 16);
  unsigned long long int c = b + (b << 32);
  return c;
}

unsigned long long int
bar (unsigned long long int x)
{
  return x * 0x0101010101010101ULL;
}

unsigned int
baz (unsigned int x)
{
  unsigned int a = x + (x << 8);
  unsigned int b = a + (a << 16);
  return b;
}

unsigned int
qux (unsigned int x)
{
  return x * 0x01010101U;
}

unsigned long long int
quux (unsigned long long int x)
{
  unsigned long long int a = (x << 2) + (x << 10);
  unsigned long long int b = a + (a << 16);
  unsigned long long int c = b + (b << 32);
  return c;
}

unsigned long long int
corge (unsigned long long int x)
{
  unsigned long long int a = x + (x << 4);
  unsigned long long int b = a + (a << 8);
  unsigned long long int c = b + (b << 16);
  unsigned long long int d = c + (c << 32);
  return d;
}

unsigned long long int
corge2 (unsigned long long int x)
{
  unsigned long long int a = x * 0x11;
  unsigned long long int b = a * 0x101;
  unsigned long long int c = b * 0x10001;
  unsigned long long int d = c * 0x100000001ULL;
  return d;
}