This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]