This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
[PATCH] tailcall: Handle NEGATE_EXPR and MINUS_EXPR
- From: Giuseppe Scrivano <gscrivano at gnu dot org>
- To: gcc-patches at gcc dot gnu dot org
- Date: Fri, 13 Aug 2010 03:33:44 +0200
- Subject: [PATCH] tailcall: Handle NEGATE_EXPR and MINUS_EXPR
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.
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" } } */