This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH] Allow an arbitrary number of multiplications and additions in tail-call optimized functions
What about it?
Thanks,
Giuseppe
> Ok, this is the complete patch, including the new testcase.
>
> I have regtested it on GNU/Linux i686 and there are no regressions. I
> executed tests running: make bootstrap && make -k check.
>
> Before:
>
> # of expected passes 59465
>
> After:
>
> # of expected passes 59467
>
>
> Other results are unchanged.
>
>
> Regards,
> Giuseppe
>
>
>
> gcc/ChangeLog
>
> 2009-09-13 Giuseppe Scrivano <gscrivano@gnu.org>
>
> * 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/ChangeLog
>
> 2009-09-13 Giuseppe Scrivano <gscrivano@gnu.org>
>
> * gcc.dg/tree-ssa/tailrecursion-6.c: New file.
>
>
> diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c
> index d1f6dc1..c29bfc3 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)
> 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 0000000..3794275
> --- /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\]" } } */