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 <kug...@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 <kug...@linaro.org>
PR middle-end/63586
* tree-ssa-reassoc.c (transform_add_to_multiply): New.
(reassociate_bb): Call transform_add_to_multiply.
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)
