On Thu, Aug 29, 2019 at 3:56 PM Martin Jambor <mjam...@suse.cz> wrote:
>
> Hi,
>
> On Thu, Aug 29 2019, Richard Biener wrote:
> > On Thu, Aug 29, 2019 at 11:04 AM Martin Jambor <mjam...@suse.cz> wrote:
> >>
> >> Hi,
> >>
> >> when turning a tail-recursive call into a loop, the tail-call pass
> >> creates a phi node for each gimple_reg function parameter that has any
> >> use at all, even when the value passed to the original call is the same
> >> as the received one, when it is the parameter's default definition.
> >> This results in a redundant phi node in which one argument is the
> >> default definition and all others are the LHS of the same phi node. See
> >> the Bugzilla entry for an example. These phi nodes in turn confuses
> >> ipa-prop.c which cannot skip them and may not create a pass-through jump
> >> function when it should.
> >>
> >> Fixed by the following patch which just adds a bitmap to remember where
> >> there are non-default-defs passed to a tail-recursive call and then
> >> creates phi nodes only for such parameters. It has passed bootstrap and
> >> testing on x86_64-linux.
> >>
> >> OK for trunk?
> >
> > OK. Eventually arg_needs_copy_p can be elided completely
> > and pre-computed into the bitmap so we can just check
> > the positional? And rename the bitmap to arg_need_copy itself.
>
> Like this? Bootstrapped and tested on x86_64-linux.
Yes. This is OK.
Thanks,
Richard.
> Thanks,
>
> Martin
>
>
> 2019-08-29 Martin Jambor <mjam...@suse.cz>
>
> tree-optimization/91579
> * tree-tailcall.c (tailr_arg_needs_copy): New variable.
> (find_tail_calls): Allocate tailr_arg_needs_copy and set its bits as
> appropriate.
> (arg_needs_copy_p): Removed.
> (eliminate_tail_call): Test tailr_arg_needs_copy instead of calling
> arg_needs_copy_p.
> (tree_optimize_tail_calls_1): Likewise. Free tailr_arg_needs_copy.
>
> testsuite/
> * gcc.dg/tree-ssa/pr91579.c: New test.
> ---
> gcc/testsuite/gcc.dg/tree-ssa/pr91579.c | 22 ++++++++++++
> gcc/tree-tailcall.c | 48 +++++++++++++------------
> 2 files changed, 47 insertions(+), 23 deletions(-)
> create mode 100644 gcc/testsuite/gcc.dg/tree-ssa/pr91579.c
>
> diff --git a/gcc/testsuite/gcc.dg/tree-ssa/pr91579.c
> b/gcc/testsuite/gcc.dg/tree-ssa/pr91579.c
> new file mode 100644
> index 00000000000..ee752be1a85
> --- /dev/null
> +++ b/gcc/testsuite/gcc.dg/tree-ssa/pr91579.c
> @@ -0,0 +1,22 @@
> +/* { dg-do compile } */
> +/* { dg-options "-O2 -fdump-tree-tailr1" } */
> +
> +typedef long unsigned int size_t;
> +typedef int (*compare_t)(const void *, const void *);
> +
> +int partition (void *base, size_t nmemb, size_t size, compare_t cmp);
> +
> +void
> +my_qsort (void *base, size_t nmemb, size_t size, compare_t cmp)
> +{
> + int pt;
> + if (nmemb > 1)
> + {
> + pt = partition (base, nmemb, size, cmp);
> + my_qsort (base, pt + 1, size, cmp);
> + my_qsort ((void*)((char*) base + (pt + 1) * size),
> + nmemb - pt - 1, size, cmp);
> + }
> +}
> +
> +/* { dg-final { scan-tree-dump-not "cmp\[^\r\n\]*PHI" "tailr1" } } */
> diff --git a/gcc/tree-tailcall.c b/gcc/tree-tailcall.c
> index a4b563efd73..4824a5e650f 100644
> --- a/gcc/tree-tailcall.c
> +++ b/gcc/tree-tailcall.c
> @@ -126,6 +126,11 @@ struct tailcall
> accumulator. */
> static tree m_acc, a_acc;
>
> +/* Bitmap with a bit for each function parameter which is set to true if we
> + have to copy the parameter for conversion of tail-recursive calls. */
> +
> +static bitmap tailr_arg_needs_copy;
> +
> static bool optimize_tail_call (struct tailcall *, bool);
> static void eliminate_tail_call (struct tailcall *);
>
> @@ -727,6 +732,18 @@ find_tail_calls (basic_block bb, struct tailcall **ret)
> gimple_stmt_iterator mgsi = gsi_for_stmt (stmt);
> gsi_move_before (&mgsi, &gsi);
> }
> + if (!tailr_arg_needs_copy)
> + tailr_arg_needs_copy = BITMAP_ALLOC (NULL);
> + for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
> + param;
> + param = DECL_CHAIN (param), idx++)
> + {
> + tree ddef, arg = gimple_call_arg (call, idx);
> + if (is_gimple_reg (param)
> + && (ddef = ssa_default_def (cfun, param))
> + && (arg != ddef))
> + bitmap_set_bit (tailr_arg_needs_copy, idx);
> + }
> }
>
> nw = XNEW (struct tailcall);
> @@ -905,25 +922,6 @@ decrease_profile (basic_block bb, profile_count count)
> }
> }
>
> -/* Returns true if argument PARAM of the tail recursive call needs to be
> copied
> - when the call is eliminated. */
> -
> -static bool
> -arg_needs_copy_p (tree param)
> -{
> - tree def;
> -
> - if (!is_gimple_reg (param))
> - return false;
> -
> - /* Parameters that are only defined but never used need not be copied. */
> - def = ssa_default_def (cfun, param);
> - if (!def)
> - return false;
> -
> - return true;
> -}
> -
> /* Eliminates tail call described by T. TMP_VARS is a list of
> temporary variables used to copy the function arguments. */
>
> @@ -1005,7 +1003,7 @@ eliminate_tail_call (struct tailcall *t)
> param;
> param = DECL_CHAIN (param), idx++)
> {
> - if (!arg_needs_copy_p (param))
> + if (!bitmap_bit_p (tailr_arg_needs_copy, idx))
> continue;
>
> arg = gimple_call_arg (stmt, idx);
> @@ -1139,10 +1137,11 @@ tree_optimize_tail_calls_1 (bool opt_tailcalls)
> split_edge (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
>
> /* Copy the args if needed. */
> - for (param = DECL_ARGUMENTS (current_function_decl);
> + unsigned idx;
> + for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
> param;
> - param = DECL_CHAIN (param))
> - if (arg_needs_copy_p (param))
> + param = DECL_CHAIN (param), idx++)
> + if (bitmap_bit_p (tailr_arg_needs_copy, idx))
> {
> tree name = ssa_default_def (cfun, param);
> tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT
> (name));
> @@ -1206,6 +1205,9 @@ tree_optimize_tail_calls_1 (bool opt_tailcalls)
> if (phis_constructed)
> mark_virtual_operands_for_renaming (cfun);
>
> + if (tailr_arg_needs_copy)
> + BITMAP_FREE (tailr_arg_needs_copy);
> +
> if (changed)
> return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
> return 0;
> --
> 2.22.0
>
