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.
Thanks,
Richard.
>
> Martin
>
>
> 2019-08-28 Martin Jambor <mjam...@suse.cz>
>
> tree-optimization/91579
> * tree-tailcall.c (tailr_non_ddef_args): New variable.
> (find_tail_calls): Allocate tailr_non_ddef_args and set its bits as
> appropriate.
> (arg_needs_copy_p): New parameter idx. Also check
> tailr_non_ddef_args.
> (tree_optimize_tail_calls_1): Free tailr_non_ddef_args.
>
> testsuite/
> * gcc.dg/tree-ssa/pr91579.c: New test.
> ---
> gcc/testsuite/gcc.dg/tree-ssa/pr91579.c | 22 ++++++++++++++
> gcc/tree-tailcall.c | 38 +++++++++++++++++++------
> 2 files changed, 52 insertions(+), 8 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..23d60f492da 100644
> --- a/gcc/tree-tailcall.c
> +++ b/gcc/tree-tailcall.c
> @@ -126,6 +126,13 @@ struct tailcall
> accumulator. */
> static tree m_acc, a_acc;
>
> +/* Bitmap with a bit for each function parameter which is set to true if in a
> + tail-recursion we pass to the actual argument something else than the
> + default definition of the corresponding formal parameter. It has no
> meaning
> + for non-gimple-register parameters. */
> +
> +static bitmap tailr_non_ddef_args;
> +
> static bool optimize_tail_call (struct tailcall *, bool);
> static void eliminate_tail_call (struct tailcall *);
>
> @@ -727,6 +734,17 @@ find_tail_calls (basic_block bb, struct tailcall **ret)
> gimple_stmt_iterator mgsi = gsi_for_stmt (stmt);
> gsi_move_before (&mgsi, &gsi);
> }
> + if (!tailr_non_ddef_args)
> + tailr_non_ddef_args = BITMAP_ALLOC (NULL);
> + for (param = DECL_ARGUMENTS (current_function_decl), idx = 0;
> + param;
> + param = DECL_CHAIN (param), idx++)
> + {
> + tree arg = gimple_call_arg (call, idx);
> + if (is_gimple_reg (param)
> + && (arg != ssa_default_def (cfun, param)))
> + bitmap_set_bit (tailr_non_ddef_args, idx);
> + }
> }
>
> nw = XNEW (struct tailcall);
> @@ -905,11 +923,11 @@ 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. */
> +/* Returns true if PARAM, which is the IDX-th argument of the tail
> recursively
> + called function, needs to be copied when the call is eliminated. */
>
> static bool
> -arg_needs_copy_p (tree param)
> +arg_needs_copy_p (tree param, unsigned idx)
> {
> tree def;
>
> @@ -918,7 +936,7 @@ arg_needs_copy_p (tree param)
>
> /* Parameters that are only defined but never used need not be copied. */
> def = ssa_default_def (cfun, param);
> - if (!def)
> + if (!def || !bitmap_bit_p (tailr_non_ddef_args, idx))
> return false;
>
> return true;
> @@ -1005,7 +1023,7 @@ eliminate_tail_call (struct tailcall *t)
> param;
> param = DECL_CHAIN (param), idx++)
> {
> - if (!arg_needs_copy_p (param))
> + if (!arg_needs_copy_p (param, idx))
> continue;
>
> arg = gimple_call_arg (stmt, idx);
> @@ -1139,10 +1157,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 (arg_needs_copy_p (param, idx))
> {
> tree name = ssa_default_def (cfun, param);
> tree new_name = make_ssa_name (param, SSA_NAME_DEF_STMT
> (name));
> @@ -1206,6 +1225,9 @@ tree_optimize_tail_calls_1 (bool opt_tailcalls)
> if (phis_constructed)
> mark_virtual_operands_for_renaming (cfun);
>
> + if (tailr_non_ddef_args)
> + BITMAP_FREE (tailr_non_ddef_args);
> +
> if (changed)
> return TODO_cleanup_cfg | TODO_update_ssa_only_virtuals;
> return 0;
> --
> 2.22.0
>
