That looks better, but I think the unordered_remove will break operand sorting
and thus you probably don't handle x + x + x + x + y + y + y + y + y +
y + z + z + z + z
optimally.
I'd say you simply want to avoid the recursion and collect a vector of
[start, end] pairs
before doing any modification to the ops vector.
Hi Richard,
Is the attached patch looks better?
Thanks,
Kugan
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c
b/gcc/testsuite/gcc.dg/tree-ssa/pr63586.c
index e69de29..a002bdd 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 17eb64f..0a43faf 100644
--- a/gcc/tree-ssa-reassoc.c
+++ b/gcc/tree-ssa-reassoc.c
@@ -1698,6 +1698,79 @@ eliminate_redundant_comparison (enum tree_code opcode,
return false;
}
+/* Transoform repeated addition of same values into multiply with
+ constant. */
+static void
+transform_add_to_multiply (gimple_stmt_iterator *gsi, gimple *stmt,
vec<operand_entry *> *ops)
+{
+ operand_entry *oe;
+ tree op = NULL_TREE;
+ int j;
+ int i, start = -1, end = 0, count = 0;
+ vec<int> start_inds = vNULL;
+ vec<int> end_inds = vNULL;
+ vec<tree> op_list = vNULL;
+
+ /* 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)
+ {
+ start_inds.safe_push (start);
+ end_inds.safe_push (end);
+ op_list.safe_push (op);
+ }
+ count = 1;
+ op = oe->op;
+ start = i;
+ }
+ }
+
+ if (count > 1)
+ {
+ start_inds.safe_push (start);
+ end_inds.safe_push (end);
+ op_list.safe_push (op);
+ }
+
+ for (j = start_inds.length () - 1; j >= 0; --j)
+ {
+ /* Convert repeated operand addition to multiplication. */
+ start = start_inds[j];
+ end = end_inds[j];
+ op = op_list[j];
+ count = end - start + 1;
+ for (i = end; i >= start; --i)
+ ops->unordered_remove (i);
+ 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));
+ 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);
+ oe = operand_entry_pool.allocate ();
+ oe->op = tmp;
+ oe->rank = get_rank (op) * count;
+ oe->id = 0;
+ oe->count = 1;
+ ops->safe_push (oe);
+ }
+}
+
+
/* 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. */
@@ -4922,6 +4995,12 @@ reassociate_bb (basic_block bb)
&& flag_unsafe_math_optimizations)
powi_result = attempt_builtin_powi (stmt, &ops);
+ if (rhs_code == PLUS_EXPR)
+ {
+ transform_add_to_multiply (&gsi, stmt, &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)
