diff mbox

tailcall: Handle NEGATE_EXPR and MINUS_EXPR

Message ID 87vd7ffg93.fsf@valhalla.homenet
State New
Headers show

Commit Message

Giuseppe Scrivano Aug. 13, 2010, 1:33 a.m. UTC 
Hello,

I have attached a small patch, now the tail call optimizator handles
NEGATE_EXPR and MINUS_EXPR too.

Bootstrapped and regtested on i686-linux.

Cheers,
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.

Comments

Paolo Carlini Aug. 16, 2010, 12:20 p.m. UTC | #1 
Hi,
> +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 (11) != -39916789)
> +    abort ();
> +
> +  if (bar (11) != -39916800)
> +    abort ();
>   
As a matter of fact, I don't think the testsuite is completely clean wrt
16-bit machines, but maybe better using long anyway?

Thanks,
Paolo.
diff mbox

Patch

diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c
index 65eaa40..cdda9fa 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,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 (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);
+          *ass_var = dest;
+        }
+      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..8c37d67
--- /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 (11) != -39916789)
+    abort ();
+
+  if (bar (11) != -39916800)
+    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" } } */