Patchwork [PING] tailcall: Handle NEGATE_EXPR and MINUS_EXPR

login
register
mail settings
Submitter Giuseppe Scrivano
Date Aug. 24, 2010, 4:28 p.m.
Message ID <87k4ngynz2.fsf@valhalla.homenet>
Download mbox | patch
Permalink /patch/62610/
State New
Headers show

Comments

Giuseppe Scrivano - Aug. 24, 2010, 4:28 p.m.
ops, sorry.  I was using NULL instead of NULL_TREE to initialize `op1'
and `non_ass_var'.

I have amended this small change.

Cheers,
Giuseppe



gcc/ChangeLog

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

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



gcc/testsuite/ChangeLog

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

	* gcc.dg/tree-ssa/tailrecursion-7.c: New file.
Richard Guenther - Aug. 27, 2010, 7:56 p.m.
On Tue, Aug 24, 2010 at 6:28 PM, Giuseppe Scrivano <gscrivano@gnu.org> wrote:
> ops, sorry.  I was using NULL instead of NULL_TREE to initialize `op1'
> and `non_ass_var'.
>
> I have amended this small change.

If that patch bootstrapped and tested ok then it is fine for trunk.  Do you have
a copyright assignment on file?

Thanks,
Richard.

> Cheers,
> Giuseppe
>
>
>
> gcc/ChangeLog
>
> 2010-08-24  Giuseppe Scrivano  <gscrivano@gnu.org>
>
>        * tree-tailcall.c (process_assignment): Handle NEGATE_EXPR and
>        MINUS_EXPR.
>
>
>
> gcc/testsuite/ChangeLog
>
> 2010-08-24  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..71a273f 100644
> --- a/gcc/tree-tailcall.c
> +++ b/gcc/tree-tailcall.c
> @@ -252,7 +252,7 @@ static bool
>  process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
>                    tree *a, tree *ass_var)
>  {
> -  tree op0, op1, non_ass_var;
> +  tree op0, op1 = NULL_TREE, non_ass_var = NULL_TREE;
>   tree dest = gimple_assign_lhs (stmt);
>   enum tree_code code = gimple_assign_rhs_code (stmt);
>   enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
> @@ -278,8 +278,20 @@ process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
>       return true;
>     }
>
> -  if (rhs_class != GIMPLE_BINARY_RHS)
> -    return false;
> +  switch (rhs_class)
> +    {
> +    case GIMPLE_BINARY_RHS:
> +      op1 = gimple_assign_rhs2 (stmt);
> +
> +      /* Fall through.  */
> +
> +    case GIMPLE_UNARY_RHS:
> +      op0 = gimple_assign_rhs1 (stmt);
> +      break;
> +
> +    default:
> +      return false;
> +    }
>
>   /* Accumulator optimizations will reverse the order of operations.
>      We can only do that for floating-point types if we're assuming
> @@ -288,20 +300,9 @@ 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)
> +    ;
> +  else if (op0 == *ass_var
>       && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
>     ;
>   else if (op1 == *ass_var
> @@ -322,8 +323,32 @@ 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 (op0)))
> +        *m = build_real (TREE_TYPE (op0), dconstm1);
> +      else
> +        *m = build_int_cst (TREE_TYPE (op0), -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)))
> +            *m = build_real (TREE_TYPE (non_ass_var), dconstm1);
> +          else
> +            *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" } } */
>
Giuseppe Scrivano - Aug. 28, 2010, 2:12 p.m.
Richard Guenther <richard.guenther@gmail.com> writes:

> If that patch bootstrapped and tested ok then it is fine for trunk.  Do you have
> a copyright assignment on file?

bootstrapped and regtested on i686-linux.  I have a copyright
assignment.

Thanks,
Giuseppe
Giuseppe Scrivano - Sept. 5, 2010, 11 p.m.
Richard Guenther <richard.guenther@gmail.com> writes:

> If that patch bootstrapped and tested ok then it is fine for trunk.  Do you have
> a copyright assignment on file?

I don't have write access to the repository, so somebody should install
the patch.

Thanks,
Giuseppe
Paolo Carlini - Sept. 5, 2010, 11:39 p.m.
On 09/06/2010 01:00 AM, Giuseppe Scrivano wrote:
> Richard Guenther <richard.guenther@gmail.com> writes:
>
>   
>> If that patch bootstrapped and tested ok then it is fine for trunk.  Do you have
>> a copyright assignment on file?
>>     
> I don't have write access to the repository, so somebody should install
> the patch.
>   
Booted C/C++ on x86_64-linux, and committed.

Paolo.

Patch

diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c
index 65eaa40..71a273f 100644
--- a/gcc/tree-tailcall.c
+++ b/gcc/tree-tailcall.c
@@ -252,7 +252,7 @@  static bool
 process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
 		    tree *a, tree *ass_var)
 {
-  tree op0, op1, non_ass_var;
+  tree op0, op1 = NULL_TREE, non_ass_var = NULL_TREE;
   tree dest = gimple_assign_lhs (stmt);
   enum tree_code code = gimple_assign_rhs_code (stmt);
   enum gimple_rhs_class rhs_class = get_gimple_rhs_class (code);
@@ -278,8 +278,20 @@  process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
       return true;
     }
 
-  if (rhs_class != GIMPLE_BINARY_RHS)
-    return false;
+  switch (rhs_class)
+    {
+    case GIMPLE_BINARY_RHS:
+      op1 = gimple_assign_rhs2 (stmt);
+
+      /* Fall through.  */
+
+    case GIMPLE_UNARY_RHS:
+      op0 = gimple_assign_rhs1 (stmt);
+      break;
+
+    default:
+      return false;
+    }
 
   /* Accumulator optimizations will reverse the order of operations.
      We can only do that for floating-point types if we're assuming
@@ -288,20 +300,9 @@  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)
+    ;
+  else if (op0 == *ass_var
       && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
     ;
   else if (op1 == *ass_var
@@ -322,8 +323,32 @@  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 (op0)))
+        *m = build_real (TREE_TYPE (op0), dconstm1);
+      else
+        *m = build_int_cst (TREE_TYPE (op0), -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)))
+            *m = build_real (TREE_TYPE (non_ass_var), dconstm1);
+          else
+            *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" } } */