re PR tree-optimization/63586 (x+x+x+x -> 4*x in gimple)

gcc/testsuite/ChangeLog:

2016-05-17  Kugan Vivekanandarajah  <kuganv@linaro.org>

	PR middle-end/63586
	* gcc.dg/tree-ssa/pr63586-2.c: New test.
	* gcc.dg/tree-ssa/pr63586.c: New test.
	* gcc.dg/tree-ssa/reassoc-14.c: Adjust multiplication count.

gcc/ChangeLog:

2016-05-17  Kugan Vivekanandarajah  <kuganv@linaro.org>

	PR middle-end/63586
	* tree-ssa-reassoc.c (transform_add_to_multiply): New.
	(reassociate_bb): Call transform_add_to_multiply.

From-SVN: r236356

4 files changed, 96 insertions, 2 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 1404d22..2f294c8 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,5 +1,11 @@
 2016-05-17  Kugan Vivekanandarajah  <kuganv@linaro.org>
 
+	PR middle-end/63586
+	* tree-ssa-reassoc.c (transform_add_to_multiply): New.
+	(reassociate_bb): Call transform_add_to_multiply.
+
+2016-05-17  Kugan Vivekanandarajah  <kuganv@linaro.org>
+
 	* config/aarch64/aarch64.c (all_extensions): Removed unused static variable.
 
 2016-05-17  Nathan Sidwell  <nathan@acm.org>
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index e803bd6..87fd63a 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,10 @@
+2016-05-17  Kugan Vivekanandarajah  <kuganv@linaro.org>
+
+	PR middle-end/63586
+	* gcc.dg/tree-ssa/pr63586-2.c: New test.
+	* gcc.dg/tree-ssa/pr63586.c: New test.
+	* gcc.dg/tree-ssa/reassoc-14.c: Adjust multiplication count.
+
 2016-05-17  Nathan Sidwell  <nathan@acm.org>
 
 	* gcc.c-torture/execute/20030222-1.c: Skip on ptx.
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-14.c b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-14.c
index 62802d1..16ebc86 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/reassoc-14.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/reassoc-14.c
@@ -19,6 +19,7 @@ unsigned int test2 (unsigned int x, unsigned int y, unsigned int z,
   return tmp1 + tmp2 + tmp3;
 }
 
-/* There should be one multiplication left in test1 and three in test2.  */
+/* There should be two multiplication left in test1 (inculding one generated
+   when converting addition to multiplication) and three in test2.  */
 
-/* { dg-final { scan-tree-dump-times "\\\*" 4 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times "\\\*" 5 "reassoc1" } } */
diff --git a/gcc/tree-ssa-reassoc.c b/gcc/tree-ssa-reassoc.c
index 7408977..3b5f36b 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -1756,6 +1756,82 @@ eliminate_redundant_comparison (enum tree_code opcode,
   return false;
 }
 
+/* Transform repeated addition of same values into multiply with
+   constant.  */
+static bool
+transform_add_to_multiply (gimple *stmt, vec<operand_entry *> *ops)
+{
+  operand_entry *oe;
+  tree op = NULL_TREE;
+  int j;
+  int i, start = -1, end = 0, count = 0;
+  vec<std::pair <int, int> > indxs = vNULL;
+  bool changed = false;
+
+  if (!INTEGRAL_TYPE_P (TREE_TYPE ((*ops)[0]->op))
+      && !flag_unsafe_math_optimizations)
+    return false;
+
+  /* Look for repeated operands.  */
+  FOR_EACH_VEC_ELT (*ops, i, oe)
+    {
+      if (start == -1)
+	{
+	  count = 1;
+	  op = oe->op;
+	  start = i;
+	}
+      else if (operand_equal_p (oe->op, op, 0))
+	{
+	  count++;
+	  end = i;
+	}
+      else
+	{
+	  if (count > 1)
+	    indxs.safe_push (std::make_pair (start, end));
+	  count = 1;
+	  op = oe->op;
+	  start = i;
+	}
+    }
+
+  if (count > 1)
+    indxs.safe_push (std::make_pair (start, end));
+
+  for (j = indxs.length () - 1; j >= 0; --j)
+    {
+      /* Convert repeated operand addition to multiplication.  */
+      start = indxs[j].first;
+      end = indxs[j].second;
+      op = (*ops)[start]->op;
+      count = end - start + 1;
+      for (i = end; i >= start; --i)
+	ops->unordered_remove (i);
+      tree tmp = make_ssa_name (TREE_TYPE (op));
+      tree cst = build_int_cst (integer_type_node, count);
+      gimple *def_stmt = SSA_NAME_DEF_STMT (op);
+      gassign *mul_stmt
+	= gimple_build_assign (tmp, MULT_EXPR,
+			       op, fold_convert (TREE_TYPE (op), cst));
+      if (gimple_code (def_stmt) == GIMPLE_NOP
+	  || gimple_bb (stmt) != gimple_bb (def_stmt))
+	{
+	  gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+	  gimple_set_uid (mul_stmt, gimple_uid (stmt));
+	  gsi_insert_before (&gsi, mul_stmt, GSI_NEW_STMT);
+	}
+      else
+	insert_stmt_after (mul_stmt, def_stmt);
+      gimple_set_visited (mul_stmt, true);
+      add_to_ops_vec (ops, tmp);
+      changed = true;
+    }
+
+  return changed;
+}
+
+
 /* Perform various identities and other optimizations on the list of
    operand entries, stored in OPS.  The tree code for the binary
    operation between all the operands is OPCODE.  */
@@ -5110,6 +5186,10 @@ reassociate_bb (basic_block bb)
 		  optimize_ops_list (rhs_code, &ops);
 		}
 
+	      if (rhs_code == PLUS_EXPR
+		  && transform_add_to_multiply (stmt, &ops))
+		ops.qsort (sort_by_operand_rank);
+
 	      if (rhs_code == BIT_IOR_EXPR || rhs_code == BIT_AND_EXPR)
 		{
 		  if (is_vector)