tailcall: Handle NEGATE_EXPR and MINUS_EXPR

Hi Paolo,

thanks for the review.  I have changed the patch accordingly.

Giuseppe


gcc/ChangeLog

2010-08-13  Giuseppe Scrivano  <gscrivano@gnu.org>

	* tree-tailcall.c (process_assignment): Handle NEGATE_EXPR and
	MINUS_EXPR.



gcc/testsuite/ChangeLog

2010-08-13  Giuseppe Scrivano  <gscrivano@gnu.org>

	* gcc.dg/tree-ssa/tailrecursion-7.c: New file.

PING



Giuseppe Scrivano <gscrivano@gnu.org> writes:

> gcc/ChangeLog
>
> 2010-08-13  Giuseppe Scrivano  <gscrivano@gnu.org>
>
> 	* tree-tailcall.c (process_assignment): Handle NEGATE_EXPR and
> 	MINUS_EXPR.
>
>
>
> gcc/testsuite/ChangeLog
>
> 2010-08-13  Giuseppe Scrivano  <gscrivano@gnu.org>
>
> 	* gcc.dg/tree-ssa/tailrecursion-7.c: New file.
>
>
> diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c
> index 65eaa40..fadcafe 100644
> --- a/gcc/tree-tailcall.c
> +++ b/gcc/tree-tailcall.c
> @@ -278,9 +278,6 @@ process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
>        return true;
>      }
>  
> -  if (rhs_class != GIMPLE_BINARY_RHS)
> -    return false;
> -
>    /* Accumulator optimizations will reverse the order of operations.
>       We can only do that for floating-point types if we're assuming
>       that addition and multiplication are associative.  */
> @@ -288,20 +285,12 @@ process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
>      if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
>        return false;
>  
> -  /* We only handle the code like
> -
> -     x = call ();
> -     y = m * x;
> -     z = y + a;
> -     return z;
> -
> -     TODO -- Extend it for cases where the linear transformation of the output
> -     is expressed in a more complicated way.  */
> -
>    op0 = gimple_assign_rhs1 (stmt);
>    op1 = gimple_assign_rhs2 (stmt);
>  
> -  if (op0 == *ass_var
> +  if (rhs_class == GIMPLE_UNARY_RHS)
> +    non_ass_var = op0;
> +  else if (op0 == *ass_var
>        && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
>      ;
>    else if (op1 == *ass_var
> @@ -322,8 +311,31 @@ process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
>        *ass_var = dest;
>        return true;
>  
> -      /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR,
> -	 POINTER_PLUS_EXPR).  */
> +    case NEGATE_EXPR:
> +      if (FLOAT_TYPE_P (TREE_TYPE (non_ass_var)))
> +        return false;
> +
> +      *m = build_int_cst (TREE_TYPE (non_ass_var), -1);
> +      *ass_var = dest;
> +      return true;
> +
> +    case MINUS_EXPR:
> +
> +      if (*ass_var == op0)
> +        *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
> +      else
> +        {
> +          if (FLOAT_TYPE_P (TREE_TYPE (non_ass_var)))
> +            return false;
> +
> +          *m = build_int_cst (TREE_TYPE (non_ass_var), -1);
> +          *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
> +        }
> +
> +      *ass_var = dest;
> +
> +      return true;
> +      /* TODO -- Handle POINTER_PLUS_EXPR.  */
>  
>      default:
>        return false;
> diff --git a/./gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-7.c b/./gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-7.c
> new file mode 100644
> index 0000000..875a6aa
> --- /dev/null
> +++ b/./gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-7.c
> @@ -0,0 +1,40 @@
> +/* { dg-do run } */
> +/* { dg-options "-O1 -foptimize-sibling-calls -fdump-tree-optimized" } */
> +
> +extern void abort (void);
> +extern void exit (int);
> +
> +int foo (int n)
> +{
> +  return n == 0 ? 1 : n * (n - foo (n - 1));
> +}
> +
> +int bar (int n)
> +{
> +  return n == 0 ? 1 : n * (- bar (n - 1));
> +}
> +
> +int baz (int n, int m)
> +{
> +  return n == 0 ? 100 : (baz (n - 1, m) - m);
> +}
> +
> +int main (void)
> +{
> +  if (foo (6) != 726)
> +    abort ();
> +
> +  if (bar (7) != -5040)
> +    abort ();
> +
> +  if (baz (10, 5) != 50)
> +    abort ();
> +
> +  exit (0);
> +}
> +
> +/* { dg-final { scan-tree-dump-times "\\mfoo\\M" 4 "optimized"} } */
> +/* { dg-final { scan-tree-dump-times "\\mbar\\M" 4 "optimized"} } */
> +/* { dg-final { scan-tree-dump-times "\\mbaz\\M" 4 "optimized"} } */
> +
> +/* { dg-final { cleanup-tree-dump "optimized" } } */

On Mon, Aug 23, 2010 at 10:49 PM, Giuseppe Scrivano <gscrivano@gnu.org> wrote:
> PING
>
>
>
> Giuseppe Scrivano <gscrivano@gnu.org> writes:
>
>> gcc/ChangeLog
>>
>> 2010-08-13  Giuseppe Scrivano  <gscrivano@gnu.org>
>>
>>       * tree-tailcall.c (process_assignment): Handle NEGATE_EXPR and
>>       MINUS_EXPR.
>>
>>
>>
>> gcc/testsuite/ChangeLog
>>
>> 2010-08-13  Giuseppe Scrivano  <gscrivano@gnu.org>
>>
>>       * gcc.dg/tree-ssa/tailrecursion-7.c: New file.
>>
>>
>> diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c
>> index 65eaa40..fadcafe 100644
>> --- a/gcc/tree-tailcall.c
>> +++ b/gcc/tree-tailcall.c
>> @@ -278,9 +278,6 @@ process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
>>        return true;
>>      }
>>
>> -  if (rhs_class != GIMPLE_BINARY_RHS)
>> -    return false;
>> -
>>    /* Accumulator optimizations will reverse the order of operations.
>>       We can only do that for floating-point types if we're assuming
>>       that addition and multiplication are associative.  */
>> @@ -288,20 +285,12 @@ process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
>>      if (FLOAT_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
>>        return false;
>>
>> -  /* We only handle the code like
>> -
>> -     x = call ();
>> -     y = m * x;
>> -     z = y + a;
>> -     return z;
>> -
>> -     TODO -- Extend it for cases where the linear transformation of the output
>> -     is expressed in a more complicated way.  */
>> -
>>    op0 = gimple_assign_rhs1 (stmt);
>>    op1 = gimple_assign_rhs2 (stmt);

You are now accessing rhs2 even for UNARY_RHS which will touch
unallocated memory.  Please wrap the assignment to op1 in a
common else path besides the GIMPLE_UNARY_RHS which
should check for GIMPLE_BINARY_RHS, add an else path
to return false for any other rhs class.

>> -  if (op0 == *ass_var
>> +  if (rhs_class == GIMPLE_UNARY_RHS)
>> +    non_ass_var = op0;
>> +  else if (op0 == *ass_var
>>        && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
>>      ;
>>    else if (op1 == *ass_var
>> @@ -322,8 +311,31 @@ process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
>>        *ass_var = dest;
>>        return true;
>>
>> -      /* TODO -- Handle other codes (NEGATE_EXPR, MINUS_EXPR,
>> -      POINTER_PLUS_EXPR).  */
>> +    case NEGATE_EXPR:
>> +      if (FLOAT_TYPE_P (TREE_TYPE (non_ass_var)))
>> +        return false;

So we don't support negate/minus for float values.  What's the
reason for this?

>> +      *m = build_int_cst (TREE_TYPE (non_ass_var), -1);
>> +      *ass_var = dest;
>> +      return true;
>> +
>> +    case MINUS_EXPR:
>> +

Excessive vertical space.

Otherwise the patch looks like an improvement.  Please rework as
suggested.

Thanks,
Richard.

>> +      if (*ass_var == op0)
>> +        *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
>> +      else
>> +        {
>> +          if (FLOAT_TYPE_P (TREE_TYPE (non_ass_var)))
>> +            return false;
>> +          *m = build_int_cst (TREE_TYPE (non_ass_var), -1);
>> +          *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
>> +        }
>> +
>> +      *ass_var = dest;
>> +
>> +      return true;
>> +      /* TODO -- Handle POINTER_PLUS_EXPR.  */
>>
>>      default:
>>        return false;
>> diff --git a/./gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-7.c b/./gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-7.c
>> new file mode 100644
>> index 0000000..875a6aa
>> --- /dev/null
>> +++ b/./gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-7.c
>> @@ -0,0 +1,40 @@
>> +/* { dg-do run } */
>> +/* { dg-options "-O1 -foptimize-sibling-calls -fdump-tree-optimized" } */
>> +
>> +extern void abort (void);
>> +extern void exit (int);
>> +
>> +int foo (int n)
>> +{
>> +  return n == 0 ? 1 : n * (n - foo (n - 1));
>> +}
>> +
>> +int bar (int n)
>> +{
>> +  return n == 0 ? 1 : n * (- bar (n - 1));
>> +}
>> +
>> +int baz (int n, int m)
>> +{
>> +  return n == 0 ? 100 : (baz (n - 1, m) - m);
>> +}
>> +
>> +int main (void)
>> +{
>> +  if (foo (6) != 726)
>> +    abort ();
>> +
>> +  if (bar (7) != -5040)
>> +    abort ();
>> +
>> +  if (baz (10, 5) != 50)
>> +    abort ();
>> +
>> +  exit (0);
>> +}
>> +
>> +/* { dg-final { scan-tree-dump-times "\\mfoo\\M" 4 "optimized"} } */
>> +/* { dg-final { scan-tree-dump-times "\\mbar\\M" 4 "optimized"} } */
>> +/* { dg-final { scan-tree-dump-times "\\mbaz\\M" 4 "optimized"} } */
>> +
>> +/* { dg-final { cleanup-tree-dump "optimized" } } */
>

Hi,

> Giuseppe Scrivano <gscrivano@gnu.org> writes:
> 
> > gcc/ChangeLog
> >
> > 2010-08-13  Giuseppe Scrivano  <gscrivano@gnu.org>
> >
> > 	* tree-tailcall.c (process_assignment): Handle NEGATE_EXPR and
> > 	MINUS_EXPR.
> >

> > -  if (op0 == *ass_var
> > +  if (rhs_class == GIMPLE_UNARY_RHS)
> > +    non_ass_var = op0;

using non_ass_var to store op0 in this case is somewhat confusing.  Instead, it would be better to
set non_ass_var to NULL and ...

> > +    case NEGATE_EXPR:
> > +      if (FLOAT_TYPE_P (TREE_TYPE (non_ass_var)))
> > +        return false;
> > +
> > +      *m = build_int_cst (TREE_TYPE (non_ass_var), -1);

... use *ass_var instead of non_ass_var here.

> > +    case MINUS_EXPR:
> > +
> > +      if (*ass_var == op0)
> > +        *a = fold_build1 (NEGATE_EXPR, TREE_TYPE (non_ass_var), non_ass_var);
> > +      else
> > +        {
> > +          if (FLOAT_TYPE_P (TREE_TYPE (non_ass_var)))
> > +            return false;

This restriction seems unnecessary.  Just use build_real (type, dconstm1) instead of build_int_cst
if the type is floating.

Other than that, I think the patch is OK (but I do not have right to approve it).

Zdenek