From 60f2d2f36d770c7d771ee5c1b3ae5a7b7169f894 Mon Sep 17 00:00:00 2001
From: Alan Lawrence <alan.lawrence@arm.com>
Date: Thu, 5 Nov 2015 18:39:38 +0000
Subject: [PATCH] [PATCH] tree-scalar-evolution.c: Handle LSHIFT by constant

gcc/:

	PR tree-optimization/65963
	* tree-scalar-evolution.c (interpret_rhs_expr): Try to handle
	LSHIFT_EXPRs as equivalent unsigned MULT_EXPRs.

gcc/testsuite/:

	* gcc.dg/pr68112.c: New.
	* gcc.dg/vect/vect-strided-shift-1.c: New.

From-SVN: r229825
---
 gcc/ChangeLog                                    |  6 +++++
 gcc/testsuite/ChangeLog                          |  5 ++++
 gcc/testsuite/gcc.dg/pr68112.c                   | 11 ++++++++
 gcc/testsuite/gcc.dg/vect/vect-strided-shift-1.c | 33 ++++++++++++++++++++++++
 gcc/tree-scalar-evolution.c                      | 17 ++++++++++++
 5 files changed, 72 insertions(+)
 create mode 100644 gcc/testsuite/gcc.dg/pr68112.c
 create mode 100644 gcc/testsuite/gcc.dg/vect/vect-strided-shift-1.c

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 4c37a91..0dd763a 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,9 @@
+2015-11-05  Alan Lawrence  <alan.lawrence@arm.com>
+
+	PR tree-optimization/65963
+	* tree-scalar-evolution.c (interpret_rhs_expr): Try to handle
+	LSHIFT_EXPRs as equivalent unsigned MULT_EXPRs.
+
 2015-11-05  James Greenhalgh  <james.greenhalgh@arm.com>
 
 	* ifcvt.c (bb_ok_for_noce_convert_multiple_sets): New.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 2727d7d..d41124e 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2015-11-05  Alan Lawrence  <alan.lawrence@arm.com>
+
+	* gcc.dg/pr68112.c: New.
+	* gcc.dg/vect/vect-strided-shift-1.c: New.
+
 2015-11-05  Marek Polacek  <polacek@redhat.com>
 
 	PR c/68090
diff --git a/gcc/testsuite/gcc.dg/pr68112.c b/gcc/testsuite/gcc.dg/pr68112.c
new file mode 100644
index 0000000..0a45b03
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/pr68112.c
@@ -0,0 +1,11 @@
+/* { dg-do compile } */
+/* { dg-options "-O2 -Waggressive-loop-optimizations" } */
+
+int *a;
+
+void
+foo ()
+{
+  for (int i = 0; i < 65536; i++)
+    *a = i << 24;
+}
diff --git a/gcc/testsuite/gcc.dg/vect/vect-strided-shift-1.c b/gcc/testsuite/gcc.dg/vect/vect-strided-shift-1.c
new file mode 100644
index 0000000..b1ce2ec
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/vect/vect-strided-shift-1.c
@@ -0,0 +1,33 @@
+/* PR tree-optimization/65963.  */
+#include "tree-vect.h"
+
+#define N 512
+
+int in[2*N], out[N];
+
+__attribute__ ((noinline)) void
+loop (void)
+{
+  for (int i = 0; i < N; i++)
+    out[i] = in[i << 1] + 7;
+}
+
+int
+main (int argc, char **argv)
+{
+  check_vect ();
+  for (int i = 0; i < 2*N; i++)
+    {
+      in[i] = i;
+      __asm__ volatile ("" : : : "memory");
+    }
+  loop ();
+  __asm__ volatile ("" : : : "memory");
+  for (int i = 0; i < N; i++)
+    {
+      if (out[i] != i*2 + 7)
+	abort ();
+    }
+  return 0;
+}
+/* { dg-final { scan-tree-dump-times "vectorized 1 loops in function" 1 "vect" { target { vect_strided2 } } } } */
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
index bb27b07..5cd7b15 100644
--- a/gcc/tree-scalar-evolution.c
+++ b/gcc/tree-scalar-evolution.c
@@ -1827,6 +1827,23 @@ interpret_rhs_expr (struct loop *loop, gimple *at_stmt,
       res = chrec_fold_multiply (type, chrec1, chrec2);
       break;
 
+    case LSHIFT_EXPR:
+      {
+	/* Handle A<<B as A * (1<<B).  */
+	tree uns = unsigned_type_for (type);
+	chrec1 = analyze_scalar_evolution (loop, rhs1);
+	chrec2 = analyze_scalar_evolution (loop, rhs2);
+	chrec1 = chrec_convert (uns, chrec1, at_stmt);
+	chrec1 = instantiate_parameters (loop, chrec1);
+	chrec2 = instantiate_parameters (loop, chrec2);
+
+	tree one = build_int_cst (uns, 1);
+	chrec2 = fold_build2 (LSHIFT_EXPR, uns, one, chrec2);
+	res = chrec_fold_multiply (uns, chrec1, chrec2);
+	res = chrec_convert (type, res, at_stmt);
+      }
+      break;
+
     CASE_CONVERT:
       /* In case we have a truncation of a widened operation that in
          the truncated type has undefined overflow behavior analyze
-- 
2.7.4