[gcc r13-5111] PR tree-optimization/71343: Value number X<<2 as X*4.

[gcc r13-5111] PR tree-optimization/71343: Value number X<<2 as X*4.

[Roger Sayle]

https://gcc.gnu.org/g:98837d6e79dd27c15f5218f3f1ddf838cda4796c

commit r13-5111-g98837d6e79dd27c15f5218f3f1ddf838cda4796c
Author: Roger Sayle <roger@nextmovesoftware.com>
Date:   Wed Jan 11 16:54:58 2023 +0000

    PR tree-optimization/71343: Value number X<<2 as X*4.
    
    This patch is the second part of a fix for PR tree-optimization/71343,
    that implements Richard Biener's suggestion of using tree-ssa's value
    numbering instead of match.pd.  The change is that when assigning a
    value number for the expression X<<C, we actually look-up or insert
    the value number for the multiplication X*(1<<C).  This elegantly
    handles the fact that we (intentionally) don't canonicalize these as
    equivalent in GIMPLE, and the optimization/equivalence in PR 71343 now
    happens by (tree-ssa SCCVN) magic.
    
    2023-01-11  Roger Sayle  <roger@nextmovesoftware.com>
    
    gcc/ChangeLog
            PR tree-optimization/71343
            * tree-ssa-sccvn.cc (visit_nary_op) <case LSHIFT_EXPR>: Make
            the value number of the expression X << C the same as the value
            number for the multiplication X * (1<<C).
    
    gcc/testsuite/ChangeLog
            PR tree-optimization/71343
            * gcc.dg/pr71343-2.c: New test case.

Diff:
---
 gcc/testsuite/gcc.dg/pr71343-2.c | 34 ++++++++++++++++++++++++++++++++++
 gcc/tree-ssa-sccvn.cc            | 26 ++++++++++++++++++++++++++
 2 files changed, 60 insertions(+)

diff --git a/gcc/testsuite/gcc.dg/pr71343-2.c b/gcc/testsuite/gcc.dg/pr71343-2.c
new file mode 100644
index 00000000000..11800a9191e
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr71343-2.c
@@ -0,0 +1,34 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+unsigned int test1(unsigned int a , unsigned int b)
+{
+  return (a << 2) + (b << 2) == a * 4 + b * 4;
+}
+
+unsigned int test2(unsigned int a , unsigned int b)
+{
+  return (a << 2) + (b << 2) == (a + b) << 2;
+}
+
+unsigned int test3(unsigned int a , unsigned int b)
+{
+  return a * 4 + b * 4 == (a + b) * 4;
+}
+
+unsigned int test4(unsigned int a , unsigned int b)
+{
+  return (a + b) << 2 == (a + b) * 4;
+}
+
+unsigned int test5(unsigned int a , unsigned int b)
+{
+  return (a << 2) + (b << 2) ==  (a + b) * 4;
+}
+
+unsigned int test6(unsigned int a , unsigned int b)
+{
+  return (a + b) << 2 == a * 4 + b * 4;
+}
+
+/* { dg-final { scan-tree-dump-times "return 1" 6 "optimized" } } */
diff --git a/gcc/tree-ssa-sccvn.cc b/gcc/tree-ssa-sccvn.cc
index d6c436b4103..a01022b0d12 100644
--- a/gcc/tree-ssa-sccvn.cc
+++ b/gcc/tree-ssa-sccvn.cc
@@ -5385,6 +5385,32 @@ visit_nary_op (tree lhs, gassign *stmt)
 	    }
 	}
       break;
+    case LSHIFT_EXPR:
+      /* For X << C, use the value number of X * (1 << C).  */
+      if (INTEGRAL_TYPE_P (type)
+	  && TYPE_OVERFLOW_WRAPS (type)
+	  && !TYPE_SATURATING (type))
+	{
+	  tree rhs2 = gimple_assign_rhs2 (stmt);
+	  if (TREE_CODE (rhs2) == INTEGER_CST
+	      && tree_fits_uhwi_p (rhs2)
+	      && tree_to_uhwi (rhs2) < TYPE_PRECISION (type))
+	    {
+	      wide_int w = wi::set_bit_in_zero (tree_to_uhwi (rhs2),
+						TYPE_PRECISION (type));
+	      gimple_match_op match_op (gimple_match_cond::UNCOND,
+					MULT_EXPR, type, rhs1,
+					wide_int_to_tree (type, w));
+	      result = vn_nary_build_or_lookup (&match_op);
+	      if (result)
+		{
+		  bool changed = set_ssa_val_to (lhs, result);
+		  vn_nary_op_insert_stmt (stmt, result);
+		  return changed;
+		}
+	    }
+	}
+      break;
     default:
       break;
     }