From 74aef0cd2f40ff828a4b2abcbbdbbf4b1aea1fcf Mon Sep 17 00:00:00 2001
From: Feng Xue <fxue@os.amperecomputing.com>
Date: Tue, 21 Jan 2020 20:53:38 +0800
Subject: [PATCH] Generalized value pass-through for self-recusive function
---
gcc/ipa-cp.c | 195 ++++++++++++++++++-----------
gcc/testsuite/g++.dg/ipa/pr93203.C | 95 ++++++++++++++
gcc/testsuite/gcc.dg/ipa/ipcp-1.c | 2 +-
3 files changed, 216 insertions(+), 76 deletions(-)
create mode 100644 gcc/testsuite/g++.dg/ipa/pr93203.C
@@ -1850,7 +1850,7 @@ ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs,
{
ipcp_value_source<valtype> *s;
for (s = val->sources; s; s = s->next)
- if (s->cs == cs)
+ if (s->cs == cs && s->val == src_val)
break;
if (s)
return false;
@@ -4207,6 +4207,33 @@ get_info_about_necessary_edges (ipcp_value<valtype> *val, cgraph_node *dest,
return hot;
}
+/* Given a NODE, and a set of its CALLERS, try to adjust order of the callers
+ to let a non-self-recursive caller be the first element. Thus, we can
+ simplify intersecting operations on values that arrive from all of these
+ callers, especially when there exists self-recursive call. Return true if
+ this kind of adjustment is possible. */
+
+static bool
+adjust_callers_for_value_intersection (vec<cgraph_edge *> callers,
+ cgraph_node *node)
+{
+ for (unsigned i = 0; i < callers.length (); i++)
+ {
+ cgraph_edge *cs = callers[i];
+
+ if (cs->caller != node)
+ {
+ if (i > 0)
+ {
+ callers[i] = callers[0];
+ callers[0] = cs;
+ }
+ return true;
+ }
+ }
+ return false;
+}
+
/* Return a vector of incoming edges that do bring value VAL to node DEST. It
is assumed their number is known and equal to CALLER_COUNT. */
@@ -4230,6 +4257,9 @@ gather_edges_for_value (ipcp_value<valtype> *val, cgraph_node *dest,
}
}
+ if (caller_count > 1)
+ adjust_callers_for_value_intersection (ret, dest);
+
return ret;
}
@@ -4241,7 +4271,6 @@ get_replacement_map (class ipa_node_params *info, tree value, int parm_num)
{
struct ipa_replace_map *replace_map;
-
replace_map = ggc_alloc<ipa_replace_map> ();
if (dump_file)
{
@@ -4592,36 +4621,40 @@ create_specialized_node (struct cgraph_node *node,
}
/* Return true, if JFUNC, which describes a i-th parameter of call CS, is a
- simple no-operation pass-through function to itself. */
+ pass-through function to itself. When SIMPLE is true, further check if
+ JFUNC is a simple no-operation pass-through. */
static bool
-self_recursive_pass_through_p (cgraph_edge *cs, ipa_jump_func *jfunc, int i)
+self_recursive_pass_through_p (cgraph_edge *cs, ipa_jump_func *jfunc, int i,
+ bool simple = true)
{
enum availability availability;
if (cs->caller == cs->callee->function_symbol (&availability)
&& availability > AVAIL_INTERPOSABLE
&& jfunc->type == IPA_JF_PASS_THROUGH
- && ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR
+ && (!simple || ipa_get_jf_pass_through_operation (jfunc) == NOP_EXPR)
&& ipa_get_jf_pass_through_formal_id (jfunc) == i)
return true;
return false;
}
/* Return true, if JFUNC, which describes a part of an aggregate represented
- or pointed to by the i-th parameter of call CS, is a simple no-operation
- pass-through function to itself. */
+ or pointed to by the i-th parameter of call CS, is a pass-through function
+ to itself. When SIMPLE is true, further check if JFUNC is a simple
+ no-operation pass-through. */
static bool
self_recursive_agg_pass_through_p (cgraph_edge *cs, ipa_agg_jf_item *jfunc,
- int i)
+ int i, bool simple = true)
{
enum availability availability;
if (cs->caller == cs->callee->function_symbol (&availability)
&& availability > AVAIL_INTERPOSABLE
&& jfunc->jftype == IPA_JF_LOAD_AGG
&& jfunc->offset == jfunc->value.load_agg.offset
- && jfunc->value.pass_through.operation == NOP_EXPR
- && jfunc->value.pass_through.formal_id == i)
+ && (!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))
return true;
return false;
}
@@ -4653,9 +4686,6 @@ find_more_scalar_values_for_callers_subset (struct cgraph_node *node,
struct ipa_jump_func *jump_func;
tree t;
- if (IPA_NODE_REF (cs->caller) && IPA_NODE_REF (cs->caller)->node_dead)
- continue;
-
if (!IPA_EDGE_REF (cs)
|| i >= ipa_get_cs_argument_count (IPA_EDGE_REF (cs))
|| (i == 0
@@ -4665,10 +4695,30 @@ find_more_scalar_values_for_callers_subset (struct cgraph_node *node,
break;
}
jump_func = ipa_get_ith_jump_func (IPA_EDGE_REF (cs), i);
- if (self_recursive_pass_through_p (cs, jump_func, i))
- continue;
- t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func, type);
+ /* Besides simple pass-through jump function, arithmetic jump
+ function could also introduce argument-direct-pass-through for
+ self-feeding recursive call. For example,
+
+ fn (int i)
+ {
+ fn (i & 1);
+ }
+
+ Given that i is 0, recursive propagation via (i & 1) also gets
+ 0. */
+ if (self_recursive_pass_through_p (cs, jump_func, i, false))
+ {
+ gcc_assert (newval);
+ t = ipa_get_jf_arith_result (
+ ipa_get_jf_pass_through_operation (jump_func),
+ newval,
+ ipa_get_jf_pass_through_operand (jump_func),
+ type);
+ }
+ else
+ t = ipa_value_from_jfunc (IPA_NODE_REF (cs->caller), jump_func,
+ type);
if (!t
|| (newval
&& !values_equal_for_ipcp_p (t, newval))
@@ -4817,19 +4867,12 @@ intersect_with_plats (class ipcp_param_lattices *plats,
break;
if (aglat->offset - offset == item->offset)
{
- gcc_checking_assert (item->value);
if (aglat->is_single_const ())
{
tree value = aglat->values->value;
if (values_equal_for_ipcp_p (item->value, value))
found = true;
- else if (item->value == error_mark_node)
- {
- /* Replace unknown place holder value with real one. */
- item->value = value;
- found = true;
- }
}
break;
}
@@ -4898,12 +4941,6 @@ intersect_with_agg_replacements (struct cgraph_node *node, int index,
{
if (values_equal_for_ipcp_p (item->value, av->value))
found = true;
- else if (item->value == error_mark_node)
- {
- /* Replace place holder value with real one. */
- item->value = av->value;
- found = true;
- }
break;
}
}
@@ -5008,31 +5045,16 @@ intersect_aggregates_with_edge (struct cgraph_edge *cs, int index,
for (unsigned i = 0; i < jfunc->agg.items->length (); i++)
{
struct ipa_agg_jf_item *agg_item = &(*jfunc->agg.items)[i];
- struct ipa_agg_value agg_value;
-
- if (self_recursive_agg_pass_through_p (cs, agg_item, index))
- {
- /* For a self-recursive call, if aggregate jump function is a
- simple pass-through, the exact value that it stands for is
- not known at this point, which must comes from other call
- sites. But we still need to add a place holder in value
- sets to indicate it, here we use error_mark_node to
- represent the special unknown value, which will be replaced
- with real one during later intersecting operations. */
- agg_value.value = error_mark_node;
- }
- else
+ tree value = ipa_agg_value_from_node (caller_info, cs->caller,
+ agg_item);
+ if (value)
{
- tree value = ipa_agg_value_from_node (caller_info, cs->caller,
- agg_item);
- if (!value)
- continue;
+ struct ipa_agg_value agg_value;
agg_value.value = value;
+ agg_value.offset = agg_item->offset;
+ inter.safe_push (agg_value);
}
-
- agg_value.offset = agg_item->offset;
- inter.safe_push (agg_value);
}
else
FOR_EACH_VEC_ELT (inter, k, item)
@@ -5053,25 +5075,32 @@ intersect_aggregates_with_edge (struct cgraph_edge *cs, int index,
{
tree value;
- if (self_recursive_agg_pass_through_p (cs, ti, index))
- {
- /* A simple aggregate pass-through in self-recursive
- call should lead to same value. */
- found = true;
- }
- else if ((value = ipa_agg_value_from_node (caller_info,
- cs->caller, ti)))
- {
- if (values_equal_for_ipcp_p (item->value, value))
- found = true;
- else if (item->value == error_mark_node)
- {
- /* Replace unknown place holder value with real
- one. */
- item->value = value;
- found = true;
- }
- }
+ /* Besides simple pass-through aggregate jump function,
+ arithmetic aggregate jump function could also bring
+ same aggregate value as parameter passed-in for
+ self-feeding recursive call. For example,
+
+ fn (int *i)
+ {
+ int j = *i & 1;
+ fn (&j);
+ }
+
+ Given that *i is 0, recursive propagation via (*i & 1)
+ also gets 0. */
+ if (self_recursive_agg_pass_through_p (cs, ti, index,
+ false))
+ value = ipa_get_jf_arith_result (
+ ti->value.pass_through.operation,
+ item->value,
+ ti->value.pass_through.operand,
+ ti->type);
+ else
+ value = ipa_agg_value_from_node (caller_info,
+ cs->caller, ti);
+
+ if (value && values_equal_for_ipcp_p (item->value, value))
+ found = true;
break;
}
l++;
@@ -5147,9 +5176,6 @@ find_aggregate_values_for_callers_subset (struct cgraph_node *node,
if (!item->value)
continue;
- /* All values must be real values, not unknown place holders. */
- gcc_assert (item->value != error_mark_node);
-
v = ggc_alloc<ipa_agg_replacement_value> ();
v->index = i;
v->offset = item->offset;
@@ -5545,13 +5571,33 @@ decide_whether_version_node (struct cgraph_node *node)
if (info->do_clone_for_all_contexts)
{
struct cgraph_node *clone;
- vec<cgraph_edge *> callers;
+ vec<cgraph_edge *> callers = node->collect_callers ();
+
+ for (int i = callers.length () - 1; i >= 0; i--)
+ {
+ cgraph_edge *cs = callers[i];
+ class ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
+
+ if (caller_info && caller_info->node_dead)
+ callers.unordered_remove (i);
+ }
+
+ if (!adjust_callers_for_value_intersection (callers, node))
+ {
+ /* If node is not called by anyone, or all its caller edges are
+ self-recursive, the node is not really be in use, no need to
+ do cloning. */
+ callers.release ();
+ known_csts.release ();
+ known_contexts.release ();
+ info->do_clone_for_all_contexts = false;
+ return ret;
+ }
if (dump_file)
fprintf (dump_file, " - Creating a specialized node of %s "
"for all known contexts.\n", node->dump_name ());
- callers = node->collect_callers ();
find_more_scalar_values_for_callers_subset (node, known_csts, callers);
find_more_contexts_for_caller_subset (node, &known_contexts, callers);
ipa_agg_replacement_value *aggvals
@@ -5564,7 +5610,6 @@ decide_whether_version_node (struct cgraph_node *node)
}
clone = create_specialized_node (node, known_csts, known_contexts,
aggvals, callers);
- info = IPA_NODE_REF (node);
info->do_clone_for_all_contexts = false;
IPA_NODE_REF (clone)->is_all_contexts_clone = true;
ret = true;
new file mode 100644
@@ -0,0 +1,95 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -w -std=gnu++11" } */
+
+class a {
+public:
+ a(char *);
+};
+class ad {
+public:
+ ad(a *);
+};
+class b {};
+using ah = class ak {
+ using al = char;
+
+public:
+ ak(b) : ak(0) {}
+ ak an() { return ap & 1; }
+ al ap;
+ ak(al af) : ap(af) {}
+};
+struct at {
+ ah au;
+ int av;
+ char aw;
+ char ax;
+};
+class az {
+public:
+ struct ba {
+ void bb(ak am) {
+ ak bc = am.an();
+ bb(bc);
+ }
+ };
+ void bd(ak am) { be.bb(am); }
+ ba be;
+};
+class bg {
+public:
+ int bh;
+ at bi;
+};
+int bj;
+int *bk;
+int c;
+class bl {
+ bool bm();
+ bg bn;
+ az bo;
+ int e;
+ int bq;
+};
+class bs {
+public:
+ bs(int *, ah *, char *, char *, int);
+};
+template < typename bt > class bu : bs {
+ using bv = typename bt::bv;
+
+public:
+ template < typename... bx >
+ bu(a *by, int *bz, at body, bx...)
+ : bs(bz, &body.au, &body.aw, &body.ax, body.av), ca(bx()...), cb(by),
+ cc(by), cd(by), ce(by) {}
+ void cf() {
+ auto cg = ch();
+ auto ci = *cj();
+ ca.ck(this, cg, &ci);
+ }
+ bt ca;
+ ad cb;
+ ad cc;
+ ad cd;
+ ad ce;
+ bv *cj();
+ bv ch();
+};
+class cl {
+public:
+ using bv = struct {};
+ cl(az *, int, int, int, int, a *, int, int **);
+ void ck(bs *, bv, bv *) {
+ b d;
+ ak ci(d);
+ bo.bd(ci);
+ }
+ az bo;
+};
+bool bl::bm() {
+ a by("");
+ bu< cl > cn(&by, &bj, bn.bi, &bo, c, bn.bh, e, 0, &by, bq, &bk);
+ cn.cf();
+}
+
@@ -45,7 +45,7 @@ main (int argc, char *argv[])
}
-/* { dg-final { scan-ipa-dump "Creating a specialized node of f.*for all known contexts" "cp" } } */
+/* { dg-final { scan-ipa-dump "Creating a specialized node of f" "cp" } } */
/* { dg-final { scan-ipa-dump "replacing param .0 a with const 7" "cp" } } */
--
2.17.1