From mboxrd@z Thu Jan  1 00:00:00 1970
Return-Path: <sayle@sourceware.org>
Received: by sourceware.org (Postfix, from userid 1251)
	id 6B9D93858C83; Wed, 11 Jan 2023 16:55:58 +0000 (GMT)
DKIM-Filter: OpenDKIM Filter v2.11.0 sourceware.org 6B9D93858C83
DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gcc.gnu.org;
	s=default; t=1673456158;
	bh=EtXugjKmeTaoa6v+clsAXTBTiL13xcJE5c7rgw4OKmc=;
	h=From:To:Subject:Date:From;
	b=o7W8pBonkbKINdH0wFqW7FUsLYo223R07WWbrn7/q1wWAFShkaN6l4jkJ04fNDSdr
	 6ui5IXr/vHYPzp1/eaOL1ir6Z0EQqeif9Eyja86hAN70rgyj/9Ovipb+DFP9FmmJ71
	 YF7e+rSqh2OOkjz+k52vAyZop3xw090C1UWtanOs=
MIME-Version: 1.0
Content-Transfer-Encoding: 7bit
Content-Type: text/plain; charset="utf-8"
From: Roger Sayle <sayle@gcc.gnu.org>
To: gcc-cvs@gcc.gnu.org
Subject: [gcc r13-5111] PR tree-optimization/71343: Value number X<<2 as X*4.
X-Act-Checkin: gcc
X-Git-Author: Roger Sayle <roger@nextmovesoftware.com>
X-Git-Refname: refs/heads/master
X-Git-Oldrev: c7279270a2deda81eaeba37a87d721bee0ed6004
X-Git-Newrev: 98837d6e79dd27c15f5218f3f1ddf838cda4796c
Message-Id: <20230111165558.6B9D93858C83@sourceware.org>
Date: Wed, 11 Jan 2023 16:55:58 +0000 (GMT)
List-Id: <gcc-cvs.sourceware.org>

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;
     }