Re: [PATCH] Allow an arbitrary number of multiplications and additions in tail-call optimized functions

[Richard Guenther <richard dot guenther at gmail dot com>]

On Mon, Sep 21, 2009 at 10:00 AM, Giuseppe Scrivano <gscrivano@gnu.org> wrote:
> What about it?

The patch is ok.

Thanks,
Richard.

> 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\]" } } */
>