Patchwork Fix and improve tail recursion with pointer types (PR tree-optimization/58209)

login
register
mail settings
Submitter Jakub Jelinek
Date Aug. 23, 2013, 7:04 a.m.
Message ID <20130823070426.GH1814@tucnak.redhat.com>
Download mbox | patch
Permalink /patch/269303/
State New
Headers show

Comments

Jakub Jelinek - Aug. 23, 2013, 7:04 a.m.
Hi!

The tail recursion optimization hasn't been adjusted for POINTER_PLUS_EXPR
introduction, so we can try to produce PLUS_EXPR with 2 pointer operands or
not optimize testcases we could with preexisting POINTER_PLUS_EXPR.

The following patch attempts to fix that.  The last two hunks teach it
to use sizetype for the addend and POINTER_PLUS_EXPR for pointer return
values, the middle-hunk just verifies we never attempt to multiply pointers
and the second hunk makes tail recursion optimization recognize
POINTER_PLUS_EXPR.  Bootstrapped/regtested on x86_64-linux and i686-linux,
ok for trunk?

For the release branches I think I'd lean towards just applying
+  /* For pointers bail out if there are any additions or multiplications.  */
+  if ((m || a)
+      && POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
+    return;
+
instead.

2013-08-23  Jakub Jelinek  <jakub@redhat.com>

	PR tree-optimization/58209
	* tree-tailcall.c (process_assignment): Handle POINTER_PLUS_EXPR.
	(find_tail_calls): Give up for pointer result types if m is non-NULL.
	(adjust_return_value_with_ops): For PLUS_EXPR and pointer result type
	emit POINTER_PLUS_EXPR.
	(create_tailcall_accumulator): For pointer result type accumulate in
	sizetype type.

	* gcc.c-torture/execute/pr58209.c: New test.


	Jakub
Richard Guenther - Aug. 23, 2013, 7:26 a.m.
Jakub Jelinek <jakub@redhat.com> wrote:
>Hi!
>
>The tail recursion optimization hasn't been adjusted for
>POINTER_PLUS_EXPR
>introduction, so we can try to produce PLUS_EXPR with 2 pointer
>operands or
>not optimize testcases we could with preexisting POINTER_PLUS_EXPR.
>
>The following patch attempts to fix that.  The last two hunks teach it
>to use sizetype for the addend and POINTER_PLUS_EXPR for pointer return
>values, the middle-hunk just verifies we never attempt to multiply
>pointers
>and the second hunk makes tail recursion optimization recognize
>POINTER_PLUS_EXPR.  Bootstrapped/regtested on x86_64-linux and
>i686-linux,
>ok for trunk?
>
>For the release branches I think I'd lean towards just applying
>+  /* For pointers bail out if there are any additions or
>multiplications.  */
>+  if ((m || a)
>+      && POINTER_TYPE_P (TREE_TYPE (DECL_RESULT
>(current_function_decl))))
>+    return;
>+
>instead.

Ok.

Thanks,
Richard.

>2013-08-23  Jakub Jelinek  <jakub@redhat.com>
>
>	PR tree-optimization/58209
>	* tree-tailcall.c (process_assignment): Handle POINTER_PLUS_EXPR.
>	(find_tail_calls): Give up for pointer result types if m is non-NULL.
>	(adjust_return_value_with_ops): For PLUS_EXPR and pointer result type
>	emit POINTER_PLUS_EXPR.
>	(create_tailcall_accumulator): For pointer result type accumulate in
>	sizetype type.
>
>	* gcc.c-torture/execute/pr58209.c: New test.
>
>--- gcc/tree-tailcall.c.jj	2013-08-13 12:20:27.000000000 +0200
>+++ gcc/tree-tailcall.c	2013-08-22 11:09:17.913399969 +0200
>@@ -305,7 +305,7 @@ process_assignment (gimple stmt, gimple_
>   if (rhs_class == GIMPLE_UNARY_RHS)
>     ;
>   else if (op0 == *ass_var
>-      && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
>+	   && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
>     ;
>   else if (op1 == *ass_var
> 	   && (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
>@@ -320,6 +320,13 @@ process_assignment (gimple stmt, gimple_
>       *ass_var = dest;
>       return true;
> 
>+    case POINTER_PLUS_EXPR:
>+      if (op0 != *ass_var)
>+	return false;
>+      *a = non_ass_var;
>+      *ass_var = dest;
>+      return true;
>+
>     case MULT_EXPR:
>       *m = non_ass_var;
>       *ass_var = dest;
>@@ -562,6 +569,10 @@ find_tail_calls (basic_block bb, struct
>   if (!tail_recursion && (m || a))
>     return;
> 
>+  /* For pointers only allow additions.  */
>+  if (m && POINTER_TYPE_P (TREE_TYPE (DECL_RESULT
>(current_function_decl))))
>+    return;
>+
>   nw = XNEW (struct tailcall);
> 
>   nw->call_gsi = gsi;
>@@ -604,15 +615,23 @@ adjust_return_value_with_ops (enum tree_
>   tree result = make_temp_ssa_name (ret_type, NULL, label);
>   gimple stmt;
> 
>-  if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
>+  if (POINTER_TYPE_P (ret_type))
>+    {
>+      gcc_assert (code == PLUS_EXPR && TREE_TYPE (acc) == sizetype);
>+      code = POINTER_PLUS_EXPR;
>+    }
>+  if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1))
>+      && code != POINTER_PLUS_EXPR)
>     stmt = gimple_build_assign_with_ops (code, result, acc, op1);
>   else
>     {
>-      tree rhs = fold_convert (TREE_TYPE (acc),
>-			       fold_build2 (code,
>-					    TREE_TYPE (op1),
>-					    fold_convert (TREE_TYPE (op1), acc),
>-					    op1));
>+      tree tem;
>+      if (code == POINTER_PLUS_EXPR)
>+	tem = fold_build2 (code, TREE_TYPE (op1), op1, acc);
>+      else
>+	tem = fold_build2 (code, TREE_TYPE (op1),
>+			   fold_convert (TREE_TYPE (op1), acc), op1);
>+      tree rhs = fold_convert (ret_type, tem);
>       rhs = force_gimple_operand_gsi (&gsi, rhs,
> 				      false, NULL, true, GSI_SAME_STMT);
>       stmt = gimple_build_assign (result, rhs);
>@@ -892,6 +911,9 @@ static tree
>create_tailcall_accumulator (const char *label, basic_block bb, tree
>init)
> {
>   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
>+  if (POINTER_TYPE_P (ret_type))
>+    ret_type = sizetype;
>+
>   tree tmp = make_temp_ssa_name (ret_type, NULL, label);
>   gimple phi;
> 
>--- gcc/testsuite/gcc.c-torture/execute/pr58209.c.jj	2013-08-22
>11:15:36.827752889 +0200
>+++ gcc/testsuite/gcc.c-torture/execute/pr58209.c	2013-08-22
>11:15:17.000000000 +0200
>@@ -0,0 +1,32 @@
>+/* PR tree-optimization/58209 */
>+
>+extern void abort (void);
>+typedef __INTPTR_TYPE__ T;
>+T buf[1024];
>+
>+T *
>+foo (T n)
>+{
>+  if (n == 0)
>+    return (T *) buf;
>+  T s = (T) foo (n - 1);
>+  return (T *) (s + sizeof (T));
>+}
>+
>+T *
>+bar (T n)
>+{
>+  if (n == 0)
>+    return buf;
>+  return foo (n - 1) + 1;
>+}
>+
>+int
>+main ()
>+{
>+  int i;
>+  for (i = 0; i < 27; i++)
>+    if (foo (i) != buf + i || bar (i) != buf + i)
>+      abort ();
>+  return 0;
>+}
>
>	Jakub

Patch

--- gcc/tree-tailcall.c.jj	2013-08-13 12:20:27.000000000 +0200
+++ gcc/tree-tailcall.c	2013-08-22 11:09:17.913399969 +0200
@@ -305,7 +305,7 @@  process_assignment (gimple stmt, gimple_
   if (rhs_class == GIMPLE_UNARY_RHS)
     ;
   else if (op0 == *ass_var
-      && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
+	   && (non_ass_var = independent_of_stmt_p (op1, stmt, call)))
     ;
   else if (op1 == *ass_var
 	   && (non_ass_var = independent_of_stmt_p (op0, stmt, call)))
@@ -320,6 +320,13 @@  process_assignment (gimple stmt, gimple_
       *ass_var = dest;
       return true;
 
+    case POINTER_PLUS_EXPR:
+      if (op0 != *ass_var)
+	return false;
+      *a = non_ass_var;
+      *ass_var = dest;
+      return true;
+
     case MULT_EXPR:
       *m = non_ass_var;
       *ass_var = dest;
@@ -562,6 +569,10 @@  find_tail_calls (basic_block bb, struct
   if (!tail_recursion && (m || a))
     return;
 
+  /* For pointers only allow additions.  */
+  if (m && POINTER_TYPE_P (TREE_TYPE (DECL_RESULT (current_function_decl))))
+    return;
+
   nw = XNEW (struct tailcall);
 
   nw->call_gsi = gsi;
@@ -604,15 +615,23 @@  adjust_return_value_with_ops (enum tree_
   tree result = make_temp_ssa_name (ret_type, NULL, label);
   gimple stmt;
 
-  if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1)))
+  if (POINTER_TYPE_P (ret_type))
+    {
+      gcc_assert (code == PLUS_EXPR && TREE_TYPE (acc) == sizetype);
+      code = POINTER_PLUS_EXPR;
+    }
+  if (types_compatible_p (TREE_TYPE (acc), TREE_TYPE (op1))
+      && code != POINTER_PLUS_EXPR)
     stmt = gimple_build_assign_with_ops (code, result, acc, op1);
   else
     {
-      tree rhs = fold_convert (TREE_TYPE (acc),
-			       fold_build2 (code,
-					    TREE_TYPE (op1),
-					    fold_convert (TREE_TYPE (op1), acc),
-					    op1));
+      tree tem;
+      if (code == POINTER_PLUS_EXPR)
+	tem = fold_build2 (code, TREE_TYPE (op1), op1, acc);
+      else
+	tem = fold_build2 (code, TREE_TYPE (op1),
+			   fold_convert (TREE_TYPE (op1), acc), op1);
+      tree rhs = fold_convert (ret_type, tem);
       rhs = force_gimple_operand_gsi (&gsi, rhs,
 				      false, NULL, true, GSI_SAME_STMT);
       stmt = gimple_build_assign (result, rhs);
@@ -892,6 +911,9 @@  static tree
 create_tailcall_accumulator (const char *label, basic_block bb, tree init)
 {
   tree ret_type = TREE_TYPE (DECL_RESULT (current_function_decl));
+  if (POINTER_TYPE_P (ret_type))
+    ret_type = sizetype;
+
   tree tmp = make_temp_ssa_name (ret_type, NULL, label);
   gimple phi;
 
--- gcc/testsuite/gcc.c-torture/execute/pr58209.c.jj	2013-08-22 11:15:36.827752889 +0200
+++ gcc/testsuite/gcc.c-torture/execute/pr58209.c	2013-08-22 11:15:17.000000000 +0200
@@ -0,0 +1,32 @@ 
+/* PR tree-optimization/58209 */
+
+extern void abort (void);
+typedef __INTPTR_TYPE__ T;
+T buf[1024];
+
+T *
+foo (T n)
+{
+  if (n == 0)
+    return (T *) buf;
+  T s = (T) foo (n - 1);
+  return (T *) (s + sizeof (T));
+}
+
+T *
+bar (T n)
+{
+  if (n == 0)
+    return buf;
+  return foo (n - 1) + 1;
+}
+
+int
+main ()
+{
+  int i;
+  for (i = 0; i < 27; i++)
+    if (foo (i) != buf + i || bar (i) != buf + i)
+      abort ();
+  return 0;
+}