[Bug target/55181] [4.7/4.8 Regression] Expensive shift loop where a bit-testing instruction could be used

[steven at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=55181

Steven Bosscher <steven at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Target|avr                         |
                 CC|                            |steven at gcc dot gnu.org

--- Comment #5 from Steven Bosscher <steven at gcc dot gnu.org> 2013-03-05 23:45:38 UTC ---
At trunk r196410, the .164t.optimized dump looks like this:

lfsr (long unsigned int number)
{
  unsigned char b;
  long unsigned int _4;
  long unsigned int _5;
  _Bool _8;

  <bb 2>:
  _4 = number_3(D) & 536870912;
  _8 = _4 != 0;
  b_10 = (unsigned char) _8;
  _5 = number_3(D) & 8192;
  if (_5 != 0)
    goto <bb 3>;
  else
    goto <bb 4>;

  <bb 3>:
  b_6 = b_10 + 1;

  <bb 4>:
  # b_2 = PHI <b_10(2), b_6(3)>
  return b_2;

}

and exact_log2 could be used to identify the and-instruction as
a bit test instruction:
(gdb) p exact_log2(536870912)
$1 = 29
(gdb) 

AFAIK there are no named patterns for bit tests, perhaps there should be.
(http://gcc.gnu.org/onlinedocs/gccint/Standard-Names.html#Standard-Names)

So at least on x86_64 the test gets expanded as a shift:

    6: {r65:DI=r64:DI 0>>0x1d;clobber flags:CC;}
    7: {r59:QI=r65:DI#0&0x1;clobber flags:CC;}
    8: {r66:DI=r64:DI&0x2000;clobber flags:CC;}
    9: flags:CCZ=cmp(r66:DI,0)

i.e. also far from optimal.