[PATCH] Fix and improve tail recursion with pointer types (PR tree-optimization/58209)
Richard Biener
rguenther@suse.de
Fri Aug 23 07:30:00 GMT 2013
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
More information about the Gcc-patches
mailing list