[Bug rtl-optimization/97738] New: Optimizing division by value & - value for HAKMEM 175

["tkoenig at gcc dot gnu.org" <gcc-bugzilla@gcc.gnu.org>]

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

            Bug ID: 97738
           Summary: Optimizing division by value & - value for HAKMEM 175
           Product: gcc
           Version: 11.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: rtl-optimization
          Assignee: unassigned at gcc dot gnu.org
          Reporter: tkoenig at gcc dot gnu.org
  Target Milestone: ---

A straightforward implementation of HAKMEM 175 (returning
the next number with the same number of bits) is

unsigned int
next_same_bit (unsigned int value)
{
  unsigned int lowest_bit;
  unsigned int left_bits;
  unsigned int changed_bits;
  unsigned int right_bits;

  lowest_bit = value & - value;
  left_bits = value + lowest_bit;
  changed_bits = value ^ left_bits;
  right_bits = (changed_bits / lowest_bit) >> 2;
  return left_bits | right_bits;
}

In two's complement, this can be replaced by

unsigned int
next_s_bit (unsigned int value)
{
  unsigned int lowest_bit;
  unsigned int ctz;
  unsigned int left_bits;
  unsigned int changed_bits;
  unsigned int right_bits;

  ctz = __builtin_ctz (value);
  lowest_bit = 1u << ctz;
  left_bits = value + lowest_bit;
  changed_bits = value ^ left_bits;
  right_bits = changed_bits >> (ctz + 2);
  return left_bits | right_bits;
}

to replace the expensive division by what is known to be a
power of two by a shift.

That transformation is counter-productive (and might be done
the other way) if there is no division by lowest_bit.