PR90838: Support ctz idioms

PR90838: Support ctz idioms

Support common idioms for count trailing zeroes using an array lookup.
The canonical form is array[((x & -x) * C) >> SHIFT] where C is a magic
constant which when multiplied by a power of 2 creates a unique value
in the top 5 or 6 bits.  This is then indexed into a table which maps it
to the number of trailing zeroes.  When the table is valid, we emit a
sequence using the target defined value for ctz (0):

int ctz1 (unsigned x)
{
  static const char table[32] =
    {
      0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
      31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
    };

  return table[((unsigned)((x & -x) * 0x077CB531U)) >> 27];
}

Is optimized to:

	rbit	w0, w0
	clz	w0, w0
	and	w0, w0, 31
	ret

    gcc/
	PR tree-optimization/90838
	* tree-ssa-forwprop.c (check_ctz_array): Add new function.
	(check_ctz_string): Likewise.
	(optimize_count_trailing_zeroes): Likewise.
	(simplify_count_trailing_zeroes): Likewise.
	(pass_forwprop::execute): Try ctz simplification.
	* match.pd: Add matching for ctz idioms.

    testsuite/
	PR tree-optimization/90838
	* testsuite/gcc.target/aarch64/pr90838.c: New test.

From-SVN: r280132