[Bug tree-optimization/52631] New: VN does not use simplified expression for lookup

[Bug tree-optimization/52631] New: VN does not use simplified expression for lookup

[pinskia at gcc dot gnu.org]

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

             Bug #: 52631
           Summary: VN does not use simplified expression for lookup
    Classification: Unclassified
           Product: gcc
           Version: 4.7.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned@gcc.gnu.org
        ReportedBy: pinskia@gcc.gnu.org


Take:
unsigned f(unsigned a)
{
  unsigned b = a >> 31;
  return b&1;
}

--- CUT ---
Even though we have a simplified expression of a>>31 for b, VN does not use it.
SCC consists of: a_1(D)
Setting value number of a_1(D) to a_1(D)
SCC consists of: b_2
Value numbering b_2 stmt = b_2 = a_1(D) >> 31;
Setting value number of b_2 to b_2 (changed)
SCC consists of: D.1708_3
Value numbering D.1708_3 stmt = D.1708_3 = b_2 & 1;
RHS b_2 & 1 simplified to a_1(D) >> 31 has constants 1
Setting value number of D.1708_3 to D.1708_3 (changed)

This is a regression from 4.3.

[Bug tree-optimization/52631] [4.6/4.7/4.8 Regression] VN does not use simplified expression for lookup

[pinskia at gcc dot gnu.org]

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

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

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |ASSIGNED
           Keywords|                            |missed-optimization
   Last reconfirmed|                            |2012-03-20
         AssignedTo|unassigned at gcc dot       |pinskia at gcc dot gnu.org
                   |gnu.org                     |
     Ever Confirmed|0                           |1
            Summary|VN does not use simplified  |[4.6/4.7/4.8 Regression] VN
                   |expression for lookup       |does not use simplified
                   |                            |expression for lookup
   Target Milestone|---                         |4.7.1

--- Comment #1 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-03-20 06:09:18 UTC ---
I am working on a fix.  Note I did not find this because a performance issue
but rather I found this while working on my gimple SSA combiner/simplifer
patches.

[Bug tree-optimization/52631] [4.6/4.7/4.8 Regression] VN does not use simplified expression for lookup

[pinskia at gcc dot gnu.org]

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

--- Comment #2 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-03-20 06:57:51 UTC ---
Created attachment 26927
  --> http://gcc.gnu.org/bugzilla/attachment.cgi?id=26927
Patch which fixes the problem

[Bug tree-optimization/52631] [4.6/4.7/4.8 Regression] VN does not use simplified expression for lookup

[rguenth at gcc dot gnu.org]

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

--- Comment #3 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-03-20 11:13:57 UTC ---
Hmm, but then you'd pessimize the case where b_2 & 1 were available?  Thus,
don't you need to do the lookup with the original expression anyway if the
lookup for the simplified expression fails?  Oh, and doesn't the testcase
show a missed canonicalization?

[Bug tree-optimization/52631] [4.6/4.7/4.8 Regression] VN does not use simplified expression for lookup

[pinskia at gcc dot gnu.org]

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

--- Comment #4 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-03-21 00:14:37 UTC ---
(In reply to comment #3)
> Hmm, but then you'd pessimize the case where b_2 & 1 were available?  Thus,
> don't you need to do the lookup with the original expression anyway if the
> lookup for the simplified expression fails?  Oh, and doesn't the testcase
> show a missed canonicalization?

My patch just gets us back to where we were before tuples.
Before tuples we would do:

      else if (simplified)
        {
          if (TREE_CODE (lhs) == SSA_NAME)
        {
          VN_INFO (lhs)->has_constants = expr_has_constants (simplified);
          /* We have to unshare the expression or else
             valuizing may change the IL stream.  */
          VN_INFO (lhs)->expr = unshare_expr (simplified);
        }
          rhs = simplified;
        }

And then use rhs in the switch statement for visit_unary_op/visit_binary_op .

I don't see a missed canonicalization anywhere as we are combing (a>>31)&1 and
then calling fold on it and it returns a>>31 which is the correct thing to do. 
The main issue is we never do a lookup on a>>31 after we do the simplification,
we only do it on the b&1.  

Let me see if I can understand the question about b&1 being available, a
testcase would be something like:
unsigned f(unsigned a, unsigned b, unsigned c)
{
  unsigned d = c&1;
  if(b)
    c = a>>31;
  return (c & 1) + d;
}

--- CUT ---
PRE produces (with both the patch and before):
<bb 2>:
  d_3 = c_2(D) & 1;
  if (b_4(D) != 0)
    goto <bb 3>;
  else
    goto <bb 5>;

<bb 5>:
  goto <bb 4>;

<bb 3>:
  c_6 = a_5(D) >> 31;
  pretmp.3_11 = c_6 & 1;

<bb 4>:
  # c_1 = PHI <c_2(D)(5), c_6(3)>
  # prephitmp.4_12 = PHI <d_3(5), pretmp.3_11(3)>
  D.1713_7 = prephitmp.4_12;
  D.1712_8 = D.1713_7 + d_3;
  return D.1712_8;

Which means we don't even do the simplifications while doing a PRE anyways.

[Bug tree-optimization/52631] [4.6/4.7/4.8 Regression] VN does not use simplified expression for lookup

[pinskia at gcc dot gnu.org]

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

--- Comment #5 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-03-24 03:10:37 UTC ---
Ok, I have a patch which only tries to looking up the simplified expression and
then if we find it, use it, otherwise use the original expression.  I now
understand why this makes a difference (for FRE it does not though).

[Bug tree-optimization/52631] [4.6/4.7/4.8 Regression] VN does not use simplified expression for lookup

[pinskia at gcc dot gnu.org]

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

--- Comment #6 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-03-24 03:21:29 UTC ---
Here is the simpler patch:
Index: tree-ssa-sccvn.c
===================================================================
--- tree-ssa-sccvn.c    (revision 185559)
+++ tree-ssa-sccvn.c    (working copy)
@@ -3295,6 +3295,17 @@ visit_use (tree use)
                }
              else
                {
+                 /* First try to lookup the simplified expression. */
+                 if (simplified && valid_gimple_rhs_p (simplified))
+                   {
+                     tree result = vn_nary_op_lookup (simplified, NULL);
+                     if (result)
+                       {
+                         changed = set_ssa_val_to (lhs, result);
+                         goto done;
+                       }
+                   }
+                 /* Otherwise visit the original statement. */
                  switch (get_gimple_rhs_class (code))
                    {
                    case GIMPLE_UNARY_RHS:
---- CUT -----

ChangeLog:
* tree-ssa-sccvn.c (visit_use): Before looking up the original statement, try
looking up the simplified expression.

[Bug tree-optimization/52631] [4.6/4.7/4.8 Regression] VN does not use simplified expression for lookup

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2
      Known to work|                            |4.3.6

--- Comment #7 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-04-13 13:10:04 UTC ---
That looks good apart from the use of valid_gimple_rhs_p which allows too much.
I'd rather use get_gimple_rhs_class (TREE_CODE (simplified)) and allow
GIMPLE_UNARY_RHS, GIMPLE_BINARY_RHS and GIMPLE_TERNARY_RHS here.

[Bug tree-optimization/52631] [4.6/4.7/4.8 Regression] VN does not use simplified expression for lookup

[rguenth at gcc dot gnu.org]

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

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.7.1                       |4.7.2

--- Comment #8 from Richard Guenther <rguenth at gcc dot gnu.org> 2012-06-14 08:21:25 UTC ---
GCC 4.7.1 is being released, adjusting target milestone.

[Bug tree-optimization/52631] [4.6/4.7/4.8 Regression] VN does not use simplified expression for lookup

[jakub at gcc dot gnu.org]

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

Jakub Jelinek <jakub at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
   Target Milestone|4.7.2                       |4.7.3

--- Comment #9 from Jakub Jelinek <jakub at gcc dot gnu.org> 2012-09-20 10:16:19 UTC ---
GCC 4.7.2 has been released.

[Bug tree-optimization/52631] [4.6/4.7/4.8 Regression] VN does not use simplified expression for lookup

[law at gcc dot gnu.org]

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

--- Comment #10 from Jeffrey A. Law <law at gcc dot gnu.org> 2013-01-20 05:01:04 UTC ---
Author: law
Date: Sun Jan 20 05:00:56 2013
New Revision: 195318

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=195318
Log:
        PR tree-optimization/52631
        * tree-ssa-sccvn (visit_use): Before looking up the original
        statement, try looking up the simplified expression.

        PR tree-optimization/52631
        * tree-ssa/pr52631.c: New test.
        * tree-ssa/ssa-fre-9: Update expected output.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr52631.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-fre-9.c
    trunk/gcc/tree-ssa-sccvn.c

[Bug tree-optimization/52631] [4.6/4.7/4.8 Regression] VN does not use simplified expression for lookup

[law at redhat dot com]

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

Jeffrey A. Law <law at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
                 CC|                            |law at redhat dot com
         Resolution|                            |FIXED
   Target Milestone|4.7.3                       |4.8.0

--- Comment #11 from Jeffrey A. Law <law at redhat dot com> 2013-01-20 05:02:28 UTC ---
Fixed on trunk.

[Bug tree-optimization/52631] [4.6/4.7/4.8 Regression] VN does not use simplified expression for lookup

[gjl at gcc dot gnu.org]

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

--- Comment #12 from Georg-Johann Lay <gjl at gcc dot gnu.org> 2013-03-04 11:12:42 UTC ---
Author: gjl
Date: Mon Mar  4 11:12:30 2013
New Revision: 196428

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=196428
Log:
    PR testsuite/52641
    PR tree-optimization/52631
    * gcc.dg/tree-ssa/pr52631.c: Fix 16-bit int.


Modified:
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr52631.c