Re: [PATCH] Allow an arbitrary number of multiplications and additions in tail-call optimized functions

[Giuseppe Scrivano <gscrivano at gnu dot org>]

Hello,


Zdenek Dvorak <rakdver@kam.mff.cuni.cz> writes:

> please include also the testcase in the patch.  Also, did you test it?
> Otherwise, I think the patch is OK (but I do not have the right to
> approve it),

Ok, this is the complete patch, including the new testcase.

I have regtested it on GNU/Linux i686 and there are no regressions.  I
executed tests running: make bootstrap && make -k check.

Before:

# of expected passes		59465

After:

# of expected passes		59467


Other results are unchanged.


Regards,
Giuseppe



gcc/ChangeLog

2009-09-13  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.


testsuite/ChangeLog

2009-09-13  Giuseppe Scrivano <gscrivano@gnu.org>

	* gcc.dg/tree-ssa/tailrecursion-6.c: New file.


diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c
index d1f6dc1..c29bfc3 100644
--- a/gcc/tree-tailcall.c
+++ b/gcc/tree-tailcall.c
@@ -326,22 +326,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 +473,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))
@@ -508,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.  */
@@ -605,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)
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\]" } } */