[PR,91579] Avoid creating redundant PHI nodes in tail-call pass

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?

Martin


2019-08-28  Martin Jambor  <mjambor@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

On Thu, Aug 29, 2019 at 11:04 AM Martin Jambor <mjambor@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  <mjambor@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
>

Hi,

On Thu, Aug 29 2019, Richard Biener wrote:
> On Thu, Aug 29, 2019 at 11:04 AM Martin Jambor <mjambor@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.

Thanks,

Martin


2019-08-29  Martin Jambor  <mjambor@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;

On Thu, Aug 29, 2019 at 3:56 PM Martin Jambor <mjambor@suse.cz> wrote:
>
> Hi,
>
> On Thu, Aug 29 2019, Richard Biener wrote:
> > On Thu, Aug 29, 2019 at 11:04 AM Martin Jambor <mjambor@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  <mjambor@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
>