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.

2 files changed, 60 insertions, 0 deletions

diff --git a/gcc/testsuite/gcc.dg/pr71343-2.c b/gcc/testsuite/gcc.dg/pr71343-2.c
new file mode 100644
index 0000000..11800a9
--- /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 d6c436b..a01022b 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;
     }