From 4e32b1c1e8b968955e9c1e4011060cb6b97b4f01 Mon Sep 17 00:00:00 2001 From: bonzini Date: Mon, 21 Sep 2009 16:41:58 +0000 Subject: [PATCH] 2009-09-21 Giuseppe Scrivano * tree-tailcall.c (process_assignment): Don't check if a multiplication or an addition are already present. (find_tail_calls): Combine multiple additions and multiplications. (adjust_accumulator_values): Emit accumulators. testsuite: 2009-09-21 Giuseppe Scrivano * gcc.dg/tree-ssa/tailrecursion-6.c: New file. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@151935 138bc75d-0d04-0410-961f-82ee72b054a4 --- gcc/ChangeLog | 7 +++++ gcc/testsuite/ChangeLog | 4 +++ gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c | 12 +++++++ gcc/tree-tailcall.c | 42 +++++++++++++++++-------- 4 files changed, 52 insertions(+), 13 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 9dbabcd1256..f7d6ceefe4d 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,10 @@ +2009-09-21 Giuseppe Scrivano + + * tree-tailcall.c (process_assignment): Don't check if a multiplication + or an addition are already present. + (find_tail_calls): Combine multiple additions and multiplications. + (adjust_accumulator_values): Emit accumulators. + 2009-09-21 Kai Tietz * config/i386/i386.c (ix86_expand_epilogue): Adjust offset for diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index 2df641b4fb1..8bf9349fd73 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,7 @@ +2009-09-21 Giuseppe Scrivano + + * gcc.dg/tree-ssa/tailrecursion-6.c: New file. + 2009-09-21 Jason Merrill PR c++/41421 diff --git a/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c b/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c new file mode 100644 index 00000000000..37942752aef --- /dev/null +++ b/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c @@ -0,0 +1,12 @@ +/* { dg-do compile } */ +/* { dg-options "-O1 -foptimize-sibling-calls -fdump-tree-tailr-details" } */ +int +foo (int a) +{ + if (a) + return a * (2 * (foo (a - 1))) + a + 1; + else + return 0; +} +/* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tailr1"} } */ +/* { dg-final { cleanup-tree-dump "tailr\[1-2\]" } } */ diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c index d1f6dc1488a..c29bfc304c5 100644 --- a/gcc/tree-tailcall.c +++ b/gcc/tree-tailcall.c @@ -326,22 +326,11 @@ process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m, switch (code) { case PLUS_EXPR: - /* There should be no previous addition. TODO -- it should be fairly - straightforward to lift this restriction -- just allow storing - more complicated expressions in *A, and gimplify it in - adjust_accumulator_values. */ - if (*a) - return false; *a = non_ass_var; *ass_var = dest; return true; case MULT_EXPR: - /* Similar remark applies here. Handling multiplication after addition - is just slightly more complicated -- we need to multiply both *A and - *M. */ - if (*a || *m) - return false; *m = non_ass_var; *ass_var = dest; return true; @@ -484,6 +473,8 @@ find_tail_calls (basic_block bb, struct tailcall **ret) agsi = gsi; while (1) { + tree tmp_a = NULL_TREE; + tree tmp_m = NULL_TREE; gsi_next (&agsi); while (gsi_end_p (agsi)) @@ -508,8 +499,26 @@ find_tail_calls (basic_block bb, struct tailcall **ret) return; /* This is a gimple assign. */ - if (! process_assignment (stmt, gsi, &m, &a, &ass_var)) + if (! process_assignment (stmt, gsi, &tmp_m, &tmp_a, &ass_var)) return; + + if (tmp_a) + { + if (a) + a = fold_build2 (PLUS_EXPR, TREE_TYPE (tmp_a), a, tmp_a); + else + a = tmp_a; + } + if (tmp_m) + { + if (m) + m = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), m, tmp_m); + else + m = tmp_m; + + if (a) + a = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), a, tmp_m); + } } /* See if this is a tail call we can handle. */ @@ -605,8 +614,15 @@ update_accumulator_with_ops (enum tree_code code, tree acc, tree op1, static void adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back) { - tree var, a_acc_arg = a_acc, m_acc_arg = m_acc; + tree var, a_acc_arg, m_acc_arg; + + if (m) + m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT); + if (a) + a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT); + a_acc_arg = a_acc; + m_acc_arg = m_acc; if (a) { if (m_acc) -- 2.11.4.GIT