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

[Giuseppe Scrivano <gscrivano at gnu dot org>]

have somebody looked at this patch?  If it is the proper way to proceed,
I'll continue to work on the tail recursion optimizer.

Thanks,
Giuseppe


gcc/ChangeLog

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.


testsuite/ChangeLog

2009-08-29  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..4dd4e96 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))
@@ -508,8 +502,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 +617,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)