diff mbox

[RFC,PR63586] Convert x+x+x+x into 4*x

Message ID 571BF10E.2060809@linaro.org
State Superseded
Headers show

Commit Message

Kugan Vivekanandarajah April 23, 2016, 10:02 p.m. UTC 
Hi Richard,

As you have said in the other email, I tried implementing with the 
add_reapeats_to_ops_vec but the whole repeat vector is designed for 
MULT_EXPR chain. I tried changing it but it turned out to be not 
straightforward without lots of re-write. Therefore I tried to implement 
based on your review here. Please tell me what you think.

>> +/* Transoform repeated addition of same values into multiply with

>> +   constant.  */

>>

>> Transform


Done.

>>

>> +static void

>> +transform_add_to_multiply (gimple_stmt_iterator *gsi, gimple *stmt,

>> vec<operand_entry *> *ops)

>>

>> split the long line


Done.

>>

>> op_list looks redundant - ops[start]->op gives you the desired value

>> already and if you

>> use a vec<std::pair<int, int>> you can have a more C++ish start,end pair.

>>

>> +      tree tmp = make_temp_ssa_name (TREE_TYPE (op), NULL, "reassocmul");

>> +      gassign *mul_stmt = gimple_build_assign (tmp, MULT_EXPR,

>> +                                              op, build_int_cst

>> (TREE_TYPE(op), count));

>>

>> this won't work for floating point or complex numbers - you need to use sth like

>> fold_convert (TREE_TYPE (op), build_int_cst (integer_type_node, count));


Done.

>>

>> For FP types you need to guard the transform with flag_unsafe_math_optimizations


Done.

>>

>> +      gimple_set_location (mul_stmt, gimple_location (stmt));

>> +      gimple_set_uid (mul_stmt, gimple_uid (stmt));

>> +      gsi_insert_before (gsi, mul_stmt, GSI_SAME_STMT);

>>

>> I think you do not want to set the stmt uid


assert in reassoc_stmt_dominates_p (gcc_assert (gimple_uid (s1) && 
gimple_uid (s2))) is failing. So I tried to add the uid of the adjacent 
stmt and it seems to work.

>> and you want to insert the

>> stmt right

>> after the def of op (or at the original first add - though you can't

>> get your hands at


Done.

>> that easily).  You also don't want to set the location to the last stmt of the

>> whole add sequence - simply leave it unset.

>>

>> +      oe = operand_entry_pool.allocate ();

>> +      oe->op = tmp;

>> +      oe->rank = get_rank (op) * count;

>>

>> ?  Why that?  oe->rank should be get_rank (tmp).

>>

>> +      oe->id = 0;

>>

>> other places use next_operand_entry_id++.  I think you want to simply

>> use add_to_ops_vec (oe, tmp); here for all of the above.


Done.

>>

>> Please return whether you did any optimization and do the

>> qsort of the operand vector only if you did sth.


Done.


>> Testcase with FP math missing.  Likewise with complex or vector math.

>

> Btw, does it handle associating

>

>    x + 3 * x + x

>

> to

>

>    5 * x

>

> ?


Added this to the testcase and verified it is working.

Regression tested and bootstrapped on x86-64-linux-gnu with no new 
regressions.

Is this OK for trunk?

Thanks,
Kugan


gcc/testsuite/ChangeLog:

2016-04-24  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-04-24  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.
diff mbox

Patch

diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr63586-2.c b/gcc/testsuite/gcc.dg/tree-ssa/pr63586-2.c
index e69de29..2774fbd 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr63586-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr63586-2.c
@@ -0,0 +1,29 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -ffast-math -fdump-tree-reassoc1" } */
+
+float f1_float (float x)
+{
+    float y = x + x;
+    y = y + x;
+    y = y + x;
+    y = y + x;
+    y = y + x;
+    y = y + x;
+    y = y + x;
+    return y;
+}
+
+float f1_float2 (float x)
+{
+    float y = x + 3 * x + x;
+    return y;
+}
+
+int f1_int (int x)
+{
+    int y = x + 3 * x + x;
+    return y;
+}
+
+/* { dg-final { scan-tree-dump-times "\\\*" 4 "reassoc1" } } */
+
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c b/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c
index e69de29..a0f705b 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c
@@ -0,0 +1,59 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-reassoc1" } */
+
+unsigned f1 (unsigned x)
+{
+    unsigned y = x + x;
+    y = y + x;
+    y = y + x;
+    y = y + x;
+    y = y + x;
+    y = y + x;
+    y = y + x;
+    return y;
+}
+
+unsigned f2 (unsigned x, unsigned z)
+{
+    unsigned y = x + x;
+    y = y + x;
+    y = y + x;
+    y = y + z;
+    y = y + z;
+    y = y + z;
+    y = y + z;
+    return y;
+}
+
+unsigned f3 (unsigned x, unsigned z, unsigned k)
+{
+    unsigned y = x + x;
+    y = y + x;
+    y = y + x;
+    y = y + z;
+    y = y + z;
+    y = y + z;
+    y = y + k;
+    return y;
+}
+
+unsigned f4 (unsigned x, unsigned z, unsigned k)
+{
+    unsigned y = k + x;
+    y = y + x;
+    y = y + x;
+    y = y + z;
+    y = y + z;
+    y = y + z;
+    y = y + x;
+    return y;
+}
+
+unsigned f5 (unsigned x, unsigned y, unsigned z)
+{
+    return x + x + x + x + y + y + y + y + y \
+      + y + z + z + z + z;
+}
+
+/* { dg-final { scan-tree-dump-times "\\\*" 10 "reassoc1" } } */
+
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 d23dabd..6e57d44 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -1756,6 +1756,95 @@  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 (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;
+  gimple *stmt;
+
+  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));
+      gimple_stmt_iterator gsi;
+      if (SSA_NAME_VAR (op) != NULL
+	  && gimple_code (def_stmt) == GIMPLE_NOP)
+	{
+	  gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
+	  stmt = gsi_stmt (gsi);
+	  gsi_insert_before (&gsi, mul_stmt, GSI_NEW_STMT);
+	}
+      else if (gimple_code (def_stmt) == GIMPLE_PHI)
+	{
+	  gsi = gsi_after_labels (gimple_bb (def_stmt));
+	  stmt = gsi_stmt (gsi);
+	  gsi_insert_before (&gsi, mul_stmt, GSI_NEW_STMT);
+	}
+      else
+	{
+	  gsi = gsi_for_stmt (def_stmt);
+	  stmt = gsi_stmt (gsi);
+	  gsi_insert_after (&gsi, mul_stmt, GSI_NEW_STMT);
+	}
+      gimple_set_uid (mul_stmt, gimple_uid (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.  */
@@ -5127,6 +5216,10 @@  reassociate_bb (basic_block bb)
 		    powi_result = attempt_builtin_powi (stmt, &ops);
 		}
 
+	      if (rhs_code == PLUS_EXPR
+		  && transform_add_to_multiply (&ops))
+		ops.qsort (sort_by_operand_rank);
+
 	      /* If the operand vector is now empty, all operands were 
 		 consumed by the __builtin_powi optimization.  */
 	      if (ops.length () == 0)