[Bug rtl-optimization/33512] New: Simple bitwise simplification missed

[Bug rtl-optimization/33512] New: Simple bitwise simplification missed

[pinskia at gcc dot gnu dot org]

These two functions should produce the same code:
int f(int y, int x)
{
  return x & ((~x) | y);
}
int g(int y, int x)
{
  return y & x;
}

x & ((~x) | y) is the same as (x & ~x) | (x & y) using distribution and that
becomes (x & y) because (x & ~x) is always 0 and 0 | x is x.

This should be done at both the tree level and the RTL level.


-- 
           Summary: Simple bitwise simplification missed
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Keywords: missed-optimization
          Severity: normal
          Priority: P3
         Component: rtl-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: pinskia at gcc dot gnu dot org


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

[Bug rtl-optimization/33512] Simple bitwise simplification missed

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement


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

[Bug rtl-optimization/33512] Simple bitwise simplification missed

[pinskia at gcc dot gnu dot org]

------- Comment #1 from pinskia at gcc dot gnu dot org  2007-10-02 18:44 -------
Mine for RTL level:
Index: simplify-rtx.c
===================================================================
--- simplify-rtx.c      (revision 2035)
+++ simplify-rtx.c      (revision 2036)
@@ -1885,6 +1885,18 @@ simplify_binary_operation_1 (enum rtx_co
          return simplify_gen_unary (NOT, mode, tem, mode);
        }

+      /* (and X (ior (not X) Y) -> (and X Y) */
+      if (GET_CODE (op1) == IOR
+         && GET_CODE (XEXP (op1, 0)) == NOT
+         && op0 == XEXP (XEXP (op1, 0), 0))
+       return simplify_gen_binary (AND, mode, op0, XEXP (op1, 1));
+
+      /* (and (ior (not X) Y) X) -> (and X Y) */
+      if (GET_CODE (op0) == IOR
+         && GET_CODE (XEXP (op0, 0)) == NOT
+         && op1 == XEXP (XEXP (op0, 0), 0))
+       return simplify_gen_binary (AND, mode, op1, XEXP (op0, 1));
+
       tem = simplify_associative_operation (code, mode, op0, op1);
       if (tem)
        return tem;


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pinskia at gcc dot gnu dot
                   |dot org                     |org
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-10-02 18:44:09
               date|                            |


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

[Bug rtl-optimization/33512] Simple bitwise simplification missed

[pinskia at gcc dot gnu dot org]

------- Comment #2 from pinskia at gcc dot gnu dot org  2008-02-23 17:59 -------
Subject: Bug 33512

Author: pinskia
Date: Sat Feb 23 17:58:48 2008
New Revision: 132575

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=132575
Log:
2008-02-23  Andrew Pinski  <andrew_pinski@playstation.sony.com>

        PR rtl-opt/33512
        * simplify-rtx.c (simplify_binary_operation_1): Add simplification
        of (and X (ior (not X) Y) and (and (ior (not X) Y) X).

2008-02-23  Andrew Pinski  <andrew_pinski@playstation.sony.com>

        PR rtl-opt/33512
        * gcc.dg/and-1.c: New test.



Added:
    trunk/gcc/testsuite/gcc.dg/and-1.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/simplify-rtx.c
    trunk/gcc/testsuite/ChangeLog


-- 


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

[Bug tree-optimization/33512] Simple bitwise simplification missed

[pinskia at gcc dot gnu dot org]

------- Comment #3 from pinskia at gcc dot gnu dot org  2008-02-23 18:02 -------
The RTL level has been fixed.  The tree level needs fixing still but I am not
working on that.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|33702                       |
              nThis|                            |
         AssignedTo|pinskia at gcc dot gnu dot  |unassigned at gcc dot gnu
                   |org                         |dot org
                URL|http://gcc.gnu.org/ml/gcc-  |
                   |patches/2008-               |
                   |02/msg01008.html            |
             Status|ASSIGNED                    |NEW
          Component|rtl-optimization            |tree-optimization
           Keywords|patch                       |TREE


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

[Bug tree-optimization/33512] Simple bitwise simplification missed

[janis at gcc dot gnu dot org]

------- Comment #4 from janis at gcc dot gnu dot org  2008-04-04 21:19 -------
Test gcc.dg/and-1.c, added as a fix for this PR, fails on powerpc64-linux.  The
code generated for "-m64 -O2" is:

f:
        mr 0,3
        neg 3,3
        nand 3,3,0
        and 3,3,0
        blr


-- 


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

[Bug tree-optimization/33512] Simple bitwise simplification missed

[pinskia at gcc dot gnu dot org]

------- Comment #5 from pinskia at gcc dot gnu dot org  2008-04-04 21:22 -------
(In reply to comment #4)
> Test gcc.dg/and-1.c, added as a fix for this PR, fails on powerpc64-linux.  The
> code generated for "-m64 -O2" is:

The issue is we see (and X (ior Y (not X) ) ), I will add this extra check
later this weekend.  In GCC 4.1.1, we saw what I had expected but for some
reasons GCC 4.3.0 has a different order of arguments.


-- 


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

[Bug tree-optimization/33512] Simple bitwise simplification missed

[pinskia at gcc dot gnu dot org]

------- Comment #6 from pinskia at gcc dot gnu dot org  2008-07-15 14:53 -------
Mine still.


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |pinskia at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED


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

[Bug tree-optimization/33512] Simple bitwise simplification missed

[pinskia at gcc dot gnu dot org]

------- Comment #7 from pinskia at gcc dot gnu dot org  2008-11-23 18:45 -------
*** Bug 38218 has been marked as a duplicate of this bug. ***


-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |howarth at nitro dot med dot
                   |                            |uc dot edu


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

[Bug tree-optimization/33512] Simple bitwise simplification missed

[bergner at gcc dot gnu dot org]

------- Comment #8 from bergner at gcc dot gnu dot org  2010-07-02 19:52 -------
So what asm do we expect that we should get form the and-1.c testcase?


-- 

bergner at gcc dot gnu dot org changed:

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


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

[Bug tree-optimization/33512] Simple bitwise simplification missed

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

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

--- Comment #16 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-04-24 08:56:43 UTC ---
Fixed the bootstrap issue now so closing as fixed.

[Bug tree-optimization/33512] Simple bitwise simplification missed

[pinskia at gcc dot gnu.org]

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

--- Comment #15 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-04-24 08:37:52 UTC ---
>Hmm, I have right now in my tree

The most common case is with b being a constant which is why I only looked into
that case.

[Bug tree-optimization/33512] Simple bitwise simplification missed

[ktietz at gcc dot gnu.org]

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

--- Comment #14 from Kai Tietz <ktietz at gcc dot gnu.org> 2012-04-24 08:30:49 UTC ---
Hmm, I have right now in my tree

Index: tree-ssa-forwprop.c
===================================================================
--- tree-ssa-forwprop.c (revision 186753)
+++ tree-ssa-forwprop.c (working copy)
@@ -1912,17 +1912,25 @@

    /* Simplify (A & B) OP0 (C & B) to (A OP0 C) & B. */
    if (def1_code == def2_code
-       && def1_code == BIT_AND_EXPR
-       && operand_equal_for_phi_arg_p (gimple_assign_rhs2 (def1),
-                                      gimple_assign_rhs2 (def2)))
+       && def1_code == BIT_AND_EXPR)
     {
-      tree b = gimple_assign_rhs2 (def1);
-      tree a = def1_arg1;
-      tree c = def2_arg1;
-      tree inner = fold_build2 (code, TREE_TYPE (arg2), a, c);
+      tree inner, a = NULL_TREE, b = NULL_TREE, c = NULL_TREE;
+
+      if (operand_equal_for_phi_arg_p (def1_arg2, def2_arg2))
+       { b = def1_arg2; a = def1_arg1; c = def2_arg1; }
+      else if (operand_equal_for_phi_arg_p (def1_arg1, def2_arg1))
+       { b = def1_arg1; a = def1_arg2; c = def2_arg2; }
+      else if (operand_equal_for_phi_arg_p (def1_arg1, def2_arg2))
+       { b = def1_arg1; a = def1_arg2; c = def2_arg1; }
+      else if (operand_equal_for_phi_arg_p (def1_arg2, def2_arg1))
+       { b = def1_arg2; a = def1_arg1; c = def2_arg2; }
+      if (a && c)
+       inner = fold_build2 (code, TREE_TYPE (arg2), a, c);
+      if (!a || !b || !c)
+       ;
       /* If A OP0 C (this usually means C is the same as A) is 0
         then fold it down correctly. */
-      if (integer_zerop (inner))
+      else if (integer_zerop (inner))
        {
          gimple_assign_set_rhs_from_tree (gsi, inner);
          update_stmt (stmt);

It has the advantage of handling also cases for (A & B) OP0 (C & B) to (A OP0
C) & B, (B & A) OP0 (C & B) to (A OP0 C) & B, (A & B) OP0 (B & C) to (A OP0 C)
& B, and (B & A) OP0 (B & C) to (A OP0 C) & B.

It bootstraps fine.

[Bug tree-optimization/33512] Simple bitwise simplification missed

[pinskia at gcc dot gnu.org]

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

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-04-24 08:19:59 UTC ---
Patch which I am testing:
Index: tree-ssa-forwprop.c
===================================================================
--- tree-ssa-forwprop.c    (revision 186755)
+++ tree-ssa-forwprop.c    (working copy)
@@ -1913,10 +1913,10 @@ simplify_bitwise_binary (gimple_stmt_ite
    /* Simplify (A & B) OP0 (C & B) to (A OP0 C) & B. */
    if (def1_code == def2_code
        && def1_code == BIT_AND_EXPR
-       && operand_equal_for_phi_arg_p (gimple_assign_rhs2 (def1),
-                       gimple_assign_rhs2 (def2)))
+       && operand_equal_for_phi_arg_p (def1_arg2,
+                       def2_arg2))
     {
-      tree b = gimple_assign_rhs2 (def1);
+      tree b = def1_arg2;
       tree a = def1_arg1;
       tree c = def2_arg1;
       tree inner = fold_build2 (code, TREE_TYPE (arg2), a, c);

--- CUT ---
This was definitely my fault.  I tested both patches independently and forgot
to test them together.  Sorry about that.

[Bug tree-optimization/33512] Simple bitwise simplification missed

[ktietz at gcc dot gnu.org]

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

Kai Tietz <ktietz at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|RESOLVED                    |REOPENED
                 CC|                            |ktietz at gcc dot gnu.org
         Resolution|FIXED                       |

--- Comment #12 from Kai Tietz <ktietz at gcc dot gnu.org> 2012-04-24 07:38:25 UTC ---
Cause bootstrap failure

./../gcc/gcc/tree-ssa-ifcombine.c -o tree-ssa-ifcombine.o
../../gcc/gcc/tree-ssa-forwprop.c: In function `simplify_bitwise_binary':
../../gcc/gcc/tree-ssa-forwprop.c:1916: error: `def1' undeclared (first use in
this function)
../../gcc/gcc/tree-ssa-forwprop.c:1916: error: (Each undeclared identifier is
reported only once
../../gcc/gcc/tree-ssa-forwprop.c:1916: error: for each function it appears
in.)

../../gcc/gcc/tree-ssa-forwprop.c:1917: error: `def2' undeclared (first use in
this function)

[Bug tree-optimization/33512] Simple bitwise simplification missed

[pinskia at gcc dot gnu.org]

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

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED
   Target Milestone|---                         |4.8.0

--- Comment #11 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-04-24 07:05:48 UTC ---
Fixed.

[Bug tree-optimization/33512] Simple bitwise simplification missed

[pinskia at gcc dot gnu.org]

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

--- Comment #10 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-04-24 07:05:15 UTC ---
Author: pinskia
Date: Tue Apr 24 07:05:09 2012
New Revision: 186749

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=186749
Log:

2012-04-24  Andrew Pinski  <apinski@cavium.com>

    PR tree-opt/33512
    * tree-ssa-forwprop.c (defcodefor_name): New function.
    (simplify_bitwise_binary): Use defcodefor_name instead of manually
    Simplify "( X | Y) & X" to X and "( X & Y) | X" to X.
    Simplify "(~X | Y) & X" to "X & Y" and
    "(~X & Y) | X" to "X | Y".

2012-04-24  Andrew Pinski  <apinski@cavium.com>

    PR tree-opt/33512
    * gcc.dg/tree-ssa/andor-3.c: New testcase.
    * gcc.dg/tree-ssa/andor-4.c: New testcase.
    * gcc.dg/tree-ssa/andor-5.c: New testcase.


Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/andor-3.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/andor-4.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/andor-5.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-forwprop.c