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

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

[phython at gcc dot gnu dot org]

------- Additional Comments From phython at gcc dot gnu dot org  2005-07-11 03:56 -------
 This should actually be "Convert (a >> c1) & 2**c2" to a & (c2 << c1)".

-- 


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

[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

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

[phython at gcc dot gnu dot org]

------- Additional Comments From phython at gcc dot gnu dot org  2005-08-14 21:56 -------
 Actually, doing (a >> c1) & 2**c2 -> (a & (1<<c1+c2)) >> c1 looks worse, but
can be transformed into (a & (1<<c1+c2)) CMP c3 << c1.  However, I haven't
figure out the details of the second transformation.  There is a bug about it
though.

-- 


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

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

[sayle at gcc dot gnu dot org]

------- Comment #7 from sayle at gcc dot gnu dot org  2006-02-26 15:36 -------
Subject: Bug 21137

Author: sayle
Date: Sun Feb 26 15:36:52 2006
New Revision: 111453

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=111453
Log:
2006-02-26  Roger Sayle  <roger@eyesopen.com>
            James A. Morrison  <phython@gcc.gnu.org>

        PR middle-end/21137
        * fold-const.c (fold_binary) <EQ_EXPR>:  Fold ((X>>C1)&C2) eq/ne 0,
        when C2 is a power of two, as either (X&(C2<<C1)) eq/ne 0 if the
        new constant C2<<C1, or as (X<0) or (X,false) depending upon the
        signedness of the shift operation.

        * gcc.dg/fold-eqandshift-1.c: New test case.


Added:
    trunk/gcc/testsuite/gcc.dg/fold-eqandshift-1.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/fold-const.c
    trunk/gcc/testsuite/ChangeLog


-- 


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

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

[roger at eyesopen dot com]

------- Comment #8 from roger at eyesopen dot com  2006-02-26 18:39 -------
Fixed on mainline.  I'm still investiating some related optimizations.


-- 

roger at eyesopen dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.2.0


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

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

[rask at sygehus dot dk]

------- Comment #9 from rask at sygehus dot dk  2007-07-24 14:56 -------
This is not fully fixed yet. Compile these two functions with -O2
-fdump-tree-original:

void test5_1(int e)
{
  if ((e >> 31) & 64)
    foo();
}

typedef int myint;

void test5_2(myint e)
{
  if ((e >> 31) & 64)
    foo();
}

On x86_64-unknown-linux-gnu, I get (4.2.0, 4.2.1 and mainline):

;; Function test5_1 (test5_1)
;; enabled by -tree-original


{
  if (e < 0)
    {
      foo ();
    }
}



;; Function test5_2 (test5_2)
;; enabled by -tree-original

{
  if (((int) (e >> 31) & 64) != 0)
    {
      foo ();
    }
}


We should get identical dumps for the two functions. I noticed this problem
while trying to fix the original testcase to work targets where an int is
not exactly 32 bits wide. The attached patch to fix the testcase revealed
the problem.


-- 

rask at sygehus dot dk changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rask at sygehus dot dk


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

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

[rask at sygehus dot dk]

------- Comment #10 from rask at sygehus dot dk  2007-07-24 15:00 -------
Created an attachment (id=13959)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=13959&action=view)
Patch to fix testcase when int isn't exactly 32 bits


-- 


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

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

[rask at gcc dot gnu dot org]

------- Comment #11 from rask at gcc dot gnu dot org  2007-07-26 09:33 -------
Reopening since this was only partially fixed.


-- 

rask at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
         Resolution|FIXED                       |


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

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

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.2.0                       |---


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

[Bug tree-optimization/21137] New: Convert (a >> 2) & 1 != 0 into a & 4 != 0

[kazu at cs dot umass dot edu]

At tree level, we would like to canonicalize (a >> 2) & 1 != 0 into a & 4 != 0.

Currently,

void bar (void);

void
foo (int a)
{
  if ((a >> 2) & 1)
    bar ();
}

turns into

foo (a)
{
  int D.1235;
  int D.1236;
  _Bool D.1237;

  D.1235 = a >> 2;
  D.1236 = D.1235 & 1;
  D.1237 = (_Bool) D.1236;
  if (D.1237)
    {
      bar ();
    }
  else
    {
      
    }
}

-- 
           Summary: Convert (a >> 2) & 1 != 0 into a & 4 != 0
           Product: gcc
           Version: unknown
            Status: UNCONFIRMED
          Severity: enhancement
          Priority: P2
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: kazu at cs dot umass dot edu
                CC: gcc-bugs at gcc dot gnu dot org


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

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

[pinskia at gcc dot gnu dot org]

------- Additional Comments From pinskia at gcc dot gnu dot org  2005-04-21 00:50 -------
Confirmed.

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
          Component|tree-optimization           |middle-end
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-04-21 00:50:52
               date|                            |


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