Re: [PATCH] Fix bug in recursiveness check for function to be cloned (ipa/pr93707)

[Feng Xue OS <fxue@os.amperecomputing.com>]

It is a good solution.

Thanks,
Feng
________________________________________
From: Martin Jambor <mjambor@suse.cz>
Sent: Saturday, February 22, 2020 2:15 AM
To: Feng Xue OS; Tamar Christina; Jan Hubicka; gcc-patches@gcc.gnu.org
Cc: nd
Subject: Re: [PATCH] Fix bug in recursiveness check for function to be cloned (ipa/pr93707)

Hi,

On Thu, Feb 20 2020, Feng Xue OS wrote:
> This is a simpel and nice fix, but could suppress some CP opportunities for
> self-recursive call.  Using the test case as example, the first should be a
> for-all-context clone, and the call "recur_fn (i, 1, depth + 1)" is replaced with
> a newly created recursive node. Thus, in the next round of CP iteration, the
> way to do CP for the 2nd arugment "1" is blocked, because its coming edge
> can not pass check by cgraph_edge_brings_value_p().
>
> +__attribute__((noinline)) static int recur_fn (int i, int j, int depth)
> +{
> +   if (depth > 10)
> +     return 1;
> +
> +   data[i + j]++;
> +
> +   if (depth & 3)
> +     recur_fn (i, 1, depth + 1);
> +   else
> +     recur_fn (i, j & 1, depth + 1);
> +
> +   foo();
> +
> +   return i + j;
> +}
> +
> +int caller (int v, int depth)
> +{
> +  recur_fn (1, v, depth);
> +
> +  return 0;
> +}
>
>
>>However, I believe that his approach mostly papers over a bug that
>>happens earlier, specifically that cgraph_edge_brings_value_p returned
>>true for the self-recursive edge from all-context clone to itself, even
>>though when evaluating the second argument.  We assume that all context
>>clones get at least as many constants as any other potential clone, but
>>that does not work for self-recursive edges with pass-through parameters
>>that that just pass along the received constant.
>
> The following check on value in cgraph_edge_brings_value_p could ensure
> whether the value can arrive the dest node or not. If the value is a constant
> without source, as above example "1", this is allowed. Otherwise, code snippet
> enclosed by "if (caller_info->ipcp_orig_node)" could capture for-all-context clone.

there has not been any "following check" in your email but I believe I
understand what you mean, and I added such check to my patch so that the
edge carrying the non-pass through jump function was accepted by the
cgraph_edge_brings_value_p predicate.

However, that lead to the same assert in
find_more_scalar_values_for_callers_subset because on that edge it tried
to compute the depth + 1 value before it had any value to calculate it
from.

So after staring at the problem for another while I realized that the
users self_recursive_pass_through_p and
self_recursive_agg_pass_through_p would be OK if it returned false for
self-recursive calls from/to a node which is already a clone - clones
have their known constant values set at the point of their creation -
and that doing so avoids this problem.  So that is what the patch below
does.  I have still kept the cgraph_edge_brings_value_p hunks too, so
that edges are collected reliably.

Bootstrapped and tested on an x86_64-linux, LTO bootstrap underway.

What do you think?

Martin


2020-02-21  Martin Jambor  <mjambor@suse.cz>
            Feng Xue  <fxue@os.amperecomputing.com>

        PR ipa/93707
        * ipa-cp.c (same_node_or_its_all_contexts_clone_p): Replaced with
        new function calls_same_node_or_its_all_contexts_clone_p.
        (cgraph_edge_brings_value_p): Use it.
        (cgraph_edge_brings_value_p): Likewise.
        (self_recursive_pass_through_p): Return false if caller is a clone.
        (self_recursive_agg_pass_through_p): Likewise.

        testsuite/
        * gcc.dg/ipa/pr93707.c: New test.
---
 gcc/ChangeLog                      | 11 +++++++++
 gcc/ipa-cp.c                       | 38 +++++++++++++++++-------------
 gcc/testsuite/ChangeLog            |  6 +++++
 gcc/testsuite/gcc.dg/ipa/pr93707.c | 31 ++++++++++++++++++++++++
 4 files changed, 69 insertions(+), 17 deletions(-)
 create mode 100644 gcc/testsuite/gcc.dg/ipa/pr93707.c

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 7c481407de9..a965cae4f07 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,14 @@
+2020-02-21  Martin Jambor  <mjambor@suse.cz>
+           Feng Xue  <fxue@os.amperecomputing.com>
+
+       PR ipa/93707
+       * ipa-cp.c (same_node_or_its_all_contexts_clone_p): Replaced with
+       new function calls_same_node_or_its_all_contexts_clone_p.
+       (cgraph_edge_brings_value_p): Use it.
+       (cgraph_edge_brings_value_p): Likewise.
+       (self_recursive_pass_through_p): Return false if caller is a clone.
+       (self_recursive_agg_pass_through_p): Likewise.
+
 2020-02-17  Richard Biener  <rguenther@suse.de>

        PR c/86134
diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c
index 4f5b72e6994..aa228df1204 100644
--- a/gcc/ipa-cp.c
+++ b/gcc/ipa-cp.c
@@ -4033,15 +4033,24 @@ edge_clone_summary_t::duplicate (cgraph_edge *src_edge, cgraph_edge *dst_edge,
   src_data->next_clone = dst_edge;
 }

-/* Return true is NODE is DEST or its clone for all contexts.  */
+/* Return true is CS calls DEST or its clone for all contexts, except for
+   self-recursive nodes in which it has to be DEST itself.  */

 static bool
-same_node_or_its_all_contexts_clone_p (cgraph_node *node, cgraph_node *dest)
+calls_same_node_or_its_all_contexts_clone_p (cgraph_edge *cs, cgraph_node *dest,
+                                            bool allow_recursion_to_clone)
 {
-  if (node == dest)
+  enum availability availability;
+  cgraph_node *callee = cs->callee->function_symbol (&availability);
+
+  if (availability <= AVAIL_INTERPOSABLE)
+    return false;
+  if (callee == dest)
     return true;
+  if (!allow_recursion_to_clone && cs->caller == callee)
+    return false;

-  class ipa_node_params *info = IPA_NODE_REF (node);
+  class ipa_node_params *info = IPA_NODE_REF (callee);
   return info->is_all_contexts_clone && info->ipcp_orig_node == dest;
 }

@@ -4053,11 +4062,8 @@ cgraph_edge_brings_value_p (cgraph_edge *cs, ipcp_value_source<tree> *src,
                            cgraph_node *dest, ipcp_value<tree> *dest_val)
 {
   class ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
-  enum availability availability;
-  cgraph_node *real_dest = cs->callee->function_symbol (&availability);

-  if (availability <= AVAIL_INTERPOSABLE
-      || !same_node_or_its_all_contexts_clone_p (real_dest, dest)
+  if (!calls_same_node_or_its_all_contexts_clone_p (cs, dest, !src->val)
       || caller_info->node_dead)
     return false;

@@ -4076,9 +4082,6 @@ cgraph_edge_brings_value_p (cgraph_edge *cs, ipcp_value_source<tree> *src,
     }
   else
     {
-      /* At the moment we do not propagate over arithmetic jump functions in
-        SCCs, so it is safe to detect self-feeding recursive calls in this
-        way.  */
       if (src->val == dest_val)
        return true;

@@ -4113,11 +4116,8 @@ cgraph_edge_brings_value_p (cgraph_edge *cs,
                            ipcp_value<ipa_polymorphic_call_context> *)
 {
   class ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
-  enum availability avail;
-  cgraph_node *real_dest = cs->callee->function_symbol (&avail);

-  if (avail <= AVAIL_INTERPOSABLE
-      || !same_node_or_its_all_contexts_clone_p (real_dest, dest)
+  if (!calls_same_node_or_its_all_contexts_clone_p (cs, dest, true)
       || caller_info->node_dead)
     return false;
   if (!src->val)
@@ -4630,7 +4630,9 @@ self_recursive_pass_through_p (cgraph_edge *cs, ipa_jump_func *jfunc, int i,
       && availability > AVAIL_INTERPOSABLE
       && jfunc->type == IPA_JF_PASS_THROUGH
       && (!simple || ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
-      && ipa_get_jf_pass_through_formal_id (jfunc) == i)
+      && ipa_get_jf_pass_through_formal_id (jfunc) == i
+      && IPA_NODE_REF (cs->caller)
+      && !IPA_NODE_REF (cs->caller)->ipcp_orig_node)
     return true;
   return false;
 }
@@ -4651,7 +4653,9 @@ self_recursive_agg_pass_through_p (cgraph_edge *cs, ipa_agg_jf_item *jfunc,
       && jfunc->offset == jfunc->value.load_agg.offset
       && (!simple || jfunc->value.pass_through.operation == NOP_EXPR)
       && jfunc->value.pass_through.formal_id == i
-      && useless_type_conversion_p (jfunc->value.load_agg.type, jfunc->type))
+      && useless_type_conversion_p (jfunc->value.load_agg.type, jfunc->type)
+      && IPA_NODE_REF (cs->caller)
+      && !IPA_NODE_REF (cs->caller)->ipcp_orig_node)
     return true;
   return false;
 }
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index b326529ac75..e8c9f197e42 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,9 @@
+2020-02-18  Martin Jambor  <mjambor@suse.cz>
+           Feng Xue  <fxue@os.amperecomputing.com>
+
+       PR ipa/93707
+       * gcc.dg/ipa/pr93707.c: New test.
+
 2020-02-17  Richard Biener  <rguenther@suse.de>

        PR c/86134
diff --git a/gcc/testsuite/gcc.dg/ipa/pr93707.c b/gcc/testsuite/gcc.dg/ipa/pr93707.c
new file mode 100644
index 00000000000..685fae45020
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ipa/pr93707.c
@@ -0,0 +1,31 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 --param ipa-cp-eval-threshold=1 -fdump-ipa-cp" } */
+
+int foo();
+int data[100];
+
+__attribute__((noinline)) static int recur_fn (int i, int j, int depth)
+{
+   if (depth > 10)
+     return 1;
+
+   data[i + j]++;
+
+   if (depth & 3)
+     recur_fn (i, 1, depth + 1);
+   else
+     recur_fn (i, j & 1, depth + 1);
+
+   foo();
+
+   return i + j;
+}
+
+int caller (int v, int depth)
+{
+  recur_fn (1, v, depth);
+
+  return 0;
+}
+
+/* { dg-final { scan-ipa-dump-times "Clone of recur_fn/" 2 "cp" } } */
--
2.25.0