diff mbox

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

Message ID 572AA887.7060408@linaro.org
State New
Headers show

Commit Message

Kugan Vivekanandarajah May 5, 2016, 1:57 a.m. UTC 
Hi Richard,

>

> maybe instert_stmt_after will help here, I don't think you got the insertion

> logic correct, thus insert_stmt_after (mul_stmt, def_stmt) which I think

> misses GIMPLE_NOP handling.  At least

>

> +      if (SSA_NAME_VAR (op) != NULL

>

> huh?  I suppose you could have tested SSA_NAME_IS_DEFAULT_DEF

> but just the GIMPLE_NOP def-stmt test should be enough.

>

> +         && 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);

>

> not sure if that is the best insertion point choice, it un-does all

> code-sinking done

> (and no further sinking is run after the last reassoc pass).  We do know we

> are handling all uses of op in our chain so inserting before the plus-expr

> chain root should work here (thus 'stmt' in the caller context).  I'd

> use that here instead.

> I think I'd use that unconditionally even if it works and not bother

> finding something

> more optimal.

>


I now tried using instert_stmt_after with special handling for 
GIMPLE_PHI as you described.


> Apart from this this now looks ok to me.

>

> But the testcases need some work

>

>

> --- 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-final { scan-tree-dump-times "\\\*" 4 "reassoc1" } } */

>

> I would have expected 3.


We now have an additional _15 = x_1(D) * 2

   Also please check for \\\* 5 for example
> to be more specific (and change the cases so you get different constants

> for the different functions).


>

> That said, please make the scans more specific.


I have now changes the test-cases to scan more specific multiplication 
scan as you wanted.


Does this now look better?


Thanks,
Kugan
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..0dcfe32 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr63586-2.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr63586-2.c
@@ -0,0 +1,32 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -ffast-math -fdump-tree-reassoc1" } */
+
+float f1_float (float x, float z)
+{
+    float y = x + z;
+    y = y + 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 + 4 * x + x;
+    return y;
+}
+
+/* { dg-final { scan-tree-dump-times "\\\* 8\\\.0e\\\+0" 1 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times "\\\* 5\\\.0e\\\+0" 1 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times "\\\* 6" 1 "reassoc1" } } */
+
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c b/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c
index e69de29..470be8c 100644
--- a/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c
+++ b/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c
@@ -0,0 +1,70 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-reassoc1" } */
+
+unsigned f1 (unsigned x, unsigned z)
+{
+    unsigned y = x + z;
+    y = y + x;
+    y = y + x;
+    y = y + x;
+    y = y + x;
+    y = y + x;
+    y = y + x;
+    return y;
+}
+
+/* { dg-final { scan-tree-dump-times "\\\* 7" 1 "reassoc1" } } */
+
+unsigned f2 (unsigned x, unsigned z)
+{
+    unsigned y = x + z;
+    y = y + x;
+    y = y + x;
+    y = y + x;
+    y = y + z;
+    y = y + z;
+    y = y + z;
+    y = y + z;
+    return y;
+}
+
+/* { dg-final { scan-tree-dump-times "\\\* 5" 1 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times "\\\* 4" 1 "reassoc1" } } */
+
+unsigned f3 (unsigned x, unsigned z, unsigned k)
+{
+    unsigned y = x + z;
+    y = y + x;
+    y = y + z;
+    y = y + z;
+    y = y + k;
+    return y;
+}
+
+/* { dg-final { scan-tree-dump-times "\\\* 2" 1 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times "\\\* 3" 1 "reassoc1" } } */
+
+unsigned f4 (unsigned x, unsigned z, unsigned k)
+{
+    unsigned y = k + x;
+    y = y + z;
+    y = y + z;
+    y = y + z;
+    y = y + z;
+    y = y + z;
+    y = y + z;
+    y = y + z;
+    y = y + z;
+    return y;
+}
+/* { dg-final { scan-tree-dump-times "\\\* 8" 1 "reassoc1" } } */
+
+unsigned f5 (unsigned x, unsigned y, unsigned z)
+{
+    return x + y + y + y + y + y \
+      + y + z + z + z + z + z + z + z + z + z;
+}
+
+/* { dg-final { scan-tree-dump-times "\\\* 6" 1 "reassoc1" } } */
+/* { dg-final { scan-tree-dump-times "\\\* 9" 1 "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..cd7e588 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -1756,6 +1756,81 @@  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_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.  */
@@ -5118,6 +5193,10 @@  reassociate_bb (basic_block bb)
 		    optimize_range_tests (rhs_code, &ops);
 	        }
 
+	      if (rhs_code == PLUS_EXPR
+		  && transform_add_to_multiply (stmt, &ops))
+		ops.qsort (sort_by_operand_rank);
+
 	      if (rhs_code == MULT_EXPR && !is_vector)
 	        {
 		  attempt_builtin_copysign (&ops);