Patchwork [PING] tailcall: Handle NEGATE_EXPR and MINUS_EXPR

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

Comments

Giuseppe Scrivano - Aug. 24, 2010, 3:43 p.m.
Thanks for your comments.  I have modified the patch following them.

bootstrapped and regtested on i686-linux.

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.

Patch

diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c
index 65eaa40..7fdab62 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, non_ass_var = NULL;
   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" } } */