[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