[Bug middle-end/21137] Convert (a >> 2) & 1 != 0 into a & 4 != 0

[roger at eyesopen dot com]

------- Additional Comments From roger at eyesopen dot com  2005-08-14 19:17 -------
Hi James,

Unfortunately, there are a few mistakes in your proposed patch for PR21137.

Firstly Kazu's proposed transformation is only valid when the results of the
bitwise-AND are being tested for equality or inequality with zero.  i.e. its
safe to transform
  "((a >> 2) & 1) != 0"  into  "(a & 4) != 0"
but not
  "x = (a >> 2) & 1;"  into "x = (a & 4)".

Your patch is in the general fold path for BIT_AND_EXPR, so you'll transform
both.  It's surprising there are no testsuite checks for the second example
above; it might be worth adding them to prevent anyone making a similar mistake
in future.

Secondly, this transformation is only valid is c1 + c2 < TYPE_PRECISION(type).
Consider the following code:

      signed char c;
      if ((c >> 6) & 64) ...

this is not equivalent to

      if (c & (char)(64<<6)) ...
i.e.  if (c & (char)4096) ...
i.e.  if (c & 0) ...
i.e.  if (0)

Of course, when c1+c2 >= TYPE_PRECISION(type), there are two additional
optimizations that can be performed.  If TYPE_UNSIGNED(type) the result
is always false, and if !TYPE_UNSIGNED(type), the condition is equivalent
to "a < 0".  So in the example of mine above, optimization should produce:
       if (c < 0) ...

Finally, in your patch, you use "break", if the transformation is invalid.
This isn't really the correct "idiom/style" for fold, where if the guard
for a transformation fails, you shouldn't drop out of the switch, but instead
continue onto the following/next transformation "in the list".
So instead of "if (!guard) break; return transform();", this optimization
should be written as "if (guard) return transform();".  I haven't looked
for other examples for "break" in fold_unary/fold_binary/fold_ternary, but
if there are any, they're probably (latent) missed-optimization bugs.

Other than that the patch looks good.  Thanks for looking into this.


-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |phython at gcc dot gnu dot
                   |                            |org


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