[PATCH] Allow an arbitrary number of multiplications and additions in tail-call optimized functions
Giuseppe Scrivano
gscrivano@gnu.org
Sat Aug 29 19:41:00 GMT 2009
Hello,
Thanks for the explanation. I cleaned the patch using
force_gimple_operand_gsi to emit the value of the accumulators. Also, I
added a new test case.
Cheers,
Giuseppe
>From b253836295b5ae5fc99b4bd13929ac23f2d6feb3 Mon Sep 17 00:00:00 2001
From: Giuseppe Scrivano <gscrivano@gnu.org>
Date: Sat, 29 Aug 2009 15:50:09 +0200
Subject: [PATCH] Allow an arbitrary number of multiplications and additions in tail-call optimized functions
---
gcc/ChangeLog | 7 ++++
gcc/testsuite/ChangeLog | 4 ++
gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c | 12 ++++++
gcc/tree-tailcall.c | 45 ++++++++++++++++-------
4 files changed, 55 insertions(+), 13 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index aec6044..addf1e2 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,10 @@
+2009-08-29 Giuseppe Scrivano <gscrivano@gnu.org>
+
+ * tree-tailcall.c (process_assignment): Don't check if a multiplication
+ or an addition are already present.
+ (find_tail_calls): Combine multiple additions and multiplications.
+ (adjust_accumulator_values): Emit accumulators.
+
2009-08-28 Sebastian Pop <sebastian.pop@amd.com>
* graphite-dependences.c (graphite_legal_transform_bb): Call
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 719e905..619758b 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,7 @@
+2009-08-29 Giuseppe Scrivano <gscrivano@gnu.org>
+
+ * gcc.dg/tree-ssa/tailrecursion-6.c: New file.
+
2009-08-28 Cary Coutant <ccoutant@google.com>
PR debug/41063
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c b/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c
new file mode 100644
index 0000000..3794275
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/tailrecursion-6.c
@@ -0,0 +1,12 @@
+/* { dg-do compile } */
+/* { dg-options "-O1 -foptimize-sibling-calls -fdump-tree-tailr-details" } */
+int
+foo (int a)
+{
+ if (a)
+ return a * (2 * (foo (a - 1))) + a + 1;
+ else
+ return 0;
+}
+/* { dg-final { scan-tree-dump-times "Eliminated tail recursion" 1 "tailr1"} } */
+/* { dg-final { cleanup-tree-dump "tailr\[1-2\]" } } */
diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c
index efd6bc2..1237462 100644
--- a/gcc/tree-tailcall.c
+++ b/gcc/tree-tailcall.c
@@ -123,6 +123,9 @@ static bool suitable_for_tail_opt_p (void);
static bool optimize_tail_call (struct tailcall *, bool);
static void eliminate_tail_call (struct tailcall *);
static void find_tail_calls (basic_block, struct tailcall **);
+static tree adjust_return_value_with_ops (enum tree_code code, const char *label,
+ tree op0, tree op1, gimple_stmt_iterator gsi,
+ enum gsi_iterator_update update);
/* Returns false when the function is not suitable for tail call optimization
from some reason (e.g. if it takes variable number of arguments). */
@@ -326,22 +329,11 @@ process_assignment (gimple stmt, gimple_stmt_iterator call, tree *m,
switch (code)
{
case PLUS_EXPR:
- /* There should be no previous addition. TODO -- it should be fairly
- straightforward to lift this restriction -- just allow storing
- more complicated expressions in *A, and gimplify it in
- adjust_accumulator_values. */
- if (*a)
- return false;
*a = non_ass_var;
*ass_var = dest;
return true;
case MULT_EXPR:
- /* Similar remark applies here. Handling multiplication after addition
- is just slightly more complicated -- we need to multiply both *A and
- *M. */
- if (*a || *m)
- return false;
*m = non_ass_var;
*ass_var = dest;
return true;
@@ -484,6 +476,8 @@ find_tail_calls (basic_block bb, struct tailcall **ret)
agsi = gsi;
while (1)
{
+ tree tmp_a = NULL_TREE;
+ tree tmp_m = NULL_TREE;
gsi_next (&agsi);
while (gsi_end_p (agsi))
@@ -505,8 +499,26 @@ find_tail_calls (basic_block bb, struct tailcall **ret)
return;
/* This is a gimple assign. */
- if (! process_assignment (stmt, gsi, &m, &a, &ass_var))
+ if (! process_assignment (stmt, gsi, &tmp_m, &tmp_a, &ass_var))
return;
+
+ if (tmp_a)
+ {
+ if (a)
+ a = fold_build2 (PLUS_EXPR, TREE_TYPE (tmp_a), a, tmp_a);
+ else
+ a = tmp_a;
+ }
+ if (tmp_m)
+ {
+ if (m)
+ m = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), m, tmp_m);
+ else
+ m = tmp_m;
+
+ if (a)
+ a = fold_build2 (MULT_EXPR, TREE_TYPE (tmp_m), a, tmp_m);
+ }
}
/* See if this is a tail call we can handle. */
@@ -602,8 +614,15 @@ update_accumulator_with_ops (enum tree_code code, tree acc, tree op1,
static void
adjust_accumulator_values (gimple_stmt_iterator gsi, tree m, tree a, edge back)
{
- tree var, a_acc_arg = a_acc, m_acc_arg = m_acc;
+ tree var, a_acc_arg, m_acc_arg;
+
+ if (m)
+ m = force_gimple_operand_gsi (&gsi, m, true, NULL, true, GSI_SAME_STMT);
+ if (a)
+ a = force_gimple_operand_gsi (&gsi, a, true, NULL, true, GSI_SAME_STMT);
+ a_acc_arg = a_acc;
+ m_acc_arg = m_acc;
if (a)
{
if (m_acc)
--
1.6.3.3
More information about the Gcc-patches
mailing list