Please check the attachment, and this patch is based on the previous extended
agg-jump-function patch.
Thanks,
Feng
________________________________________
From: Jan Hubicka <hubi...@ucw.cz>
Sent: Tuesday, November 12, 2019 8:41 PM
To: Feng Xue OS
Subject: Re: Ping: [PATCH V6] Extend IPA-CP to support arithmetically-computed
value-passing on by-ref argument (PR ipa/91682)
Hi,
also can you please send me links to remaining IPA patches which I need
to review? I remember there is also one on clonning self recursive
functions for exchange right? I am sorry for taking so long on this - I
really appreachiate your work.
Honza
From e83508d8e037d5b6683a0293bd2891f482c2b1c6 Mon Sep 17 00:00:00 2001
From: Feng Xue <f...@os.amperecomputing.com>
Date: Tue, 24 Sep 2019 11:48:26 +0800
Subject: [PATCH] cost
---
gcc/ChangeLog | 18 +++
gcc/doc/invoke.texi | 3 +
gcc/ipa-cp.c | 210 ++++++++++++++++++++++---
gcc/ipa-prop.h | 2 +
gcc/params.opt | 4 +
gcc/testsuite/ChangeLog | 5 +
gcc/testsuite/gcc.dg/ipa/ipa-clone-2.c | 47 ++++++
7 files changed, 265 insertions(+), 24 deletions(-)
create mode 100644 gcc/testsuite/gcc.dg/ipa/ipa-clone-2.c
diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 047052835f0..e800209b695 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,21 @@
+2019-11-13 Feng Xue <f...@os.amperecomputing.com>
+
+ PR ipa/92133
+ * doc/invoke.texi (ipa-cp-max-recursion-depth): Document new option.
+ * params.opt (ipa-cp-max-recursion-depth): New.
+ * ipa-cp.c (ipcp_lattice<valtype>::add_value): Add two new parameters
+ val_pos_p and unlimited.
+ (self_recursively_generated_p): New function.
+ (get_val_across_arith_op): Likewise.
+ (propagate_vals_across_arith_jfunc): Add constant propagation for
+ self-recursive function.
+ (incorporate_penalties): Do not penalize pure self-recursive function.
+ (good_cloning_opportunity_p): Dump node_is_self_scc flag.
+ (propagate_constants_topo): Set node_is_self_scc flag for cgraph node.
+ (get_info_about_necessary_edges): Relax hotness check for edge to
+ self-recursive function.
+ * ipa-prop.h (ipa_node_params): Add new field node_is_self_scc.
+
2019-11-13 Richard Sandiford <richard.sandif...@arm.com>
* tree-vect-loop.c (vect_estimate_min_profitable_iters): Include
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 00eb7e77808..ff917e99ff3 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -12046,6 +12046,9 @@ IPA-CP calculates its own score of cloning profitability heuristics
and performs those cloning opportunities with scores that exceed
@option{ipa-cp-eval-threshold}.
+@item ipa-cp-max-recursion-depth
+Maximum depth of recursive cloning for self-recursive function.
+
@item ipa-cp-recursion-penalty
Percentage penalty the recursive functions will receive when they
are evaluated for cloning.
diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c
index 984d3b08267..420f99960fb 100644
--- a/gcc/ipa-cp.c
+++ b/gcc/ipa-cp.c
@@ -228,7 +228,9 @@ public:
inline bool set_contains_variable ();
bool add_value (valtype newval, cgraph_edge *cs,
ipcp_value<valtype> *src_val = NULL,
- int src_idx = 0, HOST_WIDE_INT offset = -1);
+ int src_idx = 0, HOST_WIDE_INT offset = -1,
+ ipcp_value<valtype> **val_pos_p = NULL,
+ bool unlimited = false);
void print (FILE * f, bool dump_sources, bool dump_benefits);
};
@@ -1738,22 +1740,37 @@ allocate_and_init_ipcp_value (ipa_polymorphic_call_context source)
/* Try to add NEWVAL to LAT, potentially creating a new ipcp_value for it. CS,
SRC_VAL SRC_INDEX and OFFSET are meant for add_source and have the same
meaning. OFFSET -1 means the source is scalar and not a part of an
- aggregate. */
+ aggregate. If non-NULL, VAL_POS_P specifies position in value list,
+ after which newly created ipcp_value will be inserted, and it is also
+ used to record address of the added ipcp_value before function returns.
+ UNLIMITED means whether value count should not exceed the limit given
+ by PARAM_IPA_CP_VALUE_LIST_SIZE. */
template <typename valtype>
bool
ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs,
ipcp_value<valtype> *src_val,
- int src_idx, HOST_WIDE_INT offset)
+ int src_idx, HOST_WIDE_INT offset,
+ ipcp_value<valtype> **val_pos_p,
+ bool unlimited)
{
ipcp_value<valtype> *val;
+ if (val_pos_p)
+ {
+ for (val = values; val && val != *val_pos_p; val = val->next);
+ gcc_checking_assert (val);
+ }
+
if (bottom)
return false;
for (val = values; val; val = val->next)
if (values_equal_for_ipcp_p (val->value, newval))
{
+ if (val_pos_p)
+ *val_pos_p = val;
+
if (ipa_edge_within_scc (cs))
{
ipcp_value_source<valtype> *s;
@@ -1768,7 +1785,7 @@ ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs,
return false;
}
- if (values_count == param_ipa_cp_value_list_size)
+ if (!unlimited && values_count == param_ipa_cp_value_list_size)
{
/* We can only free sources, not the values themselves, because sources
of other values in this SCC might point to them. */
@@ -1782,6 +1799,9 @@ ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs,
}
}
+ if (val_pos_p)
+ *val_pos_p = NULL;
+
values = NULL;
return set_to_bottom ();
}
@@ -1789,11 +1809,74 @@ ipcp_lattice<valtype>::add_value (valtype newval, cgraph_edge *cs,
values_count++;
val = allocate_and_init_ipcp_value (newval);
val->add_source (cs, src_val, src_idx, offset);
- val->next = values;
- values = val;
+ if (val_pos_p)
+ {
+ val->next = (*val_pos_p)->next;
+ (*val_pos_p)->next = val;
+ *val_pos_p = val;
+ }
+ else
+ {
+ val->next = values;
+ values = val;
+ }
+
return true;
}
+/* Return true, if a ipcp_value VAL is orginated from parameter value of
+ self-feeding recursive function by applying non-passthrough arithmetic
+ transformation. */
+
+static bool
+self_recursively_generated_p (ipcp_value<tree> *val)
+{
+ class ipa_node_params *info = NULL;
+
+ for (ipcp_value_source<tree> *src = val->sources; src; src = src->next)
+ {
+ cgraph_edge *cs = src->cs;
+
+ if (!src->val || cs->caller != cs->callee->function_symbol ()
+ || src->val == val)
+ return false;
+
+ if (!info)
+ info = IPA_NODE_REF (cs->caller);
+
+ class ipcp_param_lattices *plats = ipa_get_parm_lattices (info,
+ src->index);
+ ipcp_lattice<tree> *src_lat = src->offset == -1 ? &plats->itself
+ : plats->aggs;
+ ipcp_value<tree> *src_val;
+
+ for (src_val = src_lat->values; src_val && src_val != val;
+ src_val = src_val->next);
+
+ if (!src_val)
+ return false;
+ }
+
+ return true;
+}
+
+static tree
+get_val_across_arith_op (enum tree_code opcode,
+ tree opnd1_type,
+ tree opnd2,
+ ipcp_value<tree> *src_val,
+ tree res_type)
+{
+ tree opnd1 = src_val->value;
+
+ /* Skip source values that is incompatible with specified type. */
+ if (opnd1_type
+ && !useless_type_conversion_p (opnd1_type, TREE_TYPE (opnd1)))
+ return NULL_TREE;
+
+ return ipa_get_jf_arith_result (opcode, opnd1, opnd2, res_type);
+}
+
/* Propagate values through an arithmetic transformation described by a jump
function associated with edge CS, taking values from SRC_LAT and putting
them into DEST_LAT. OPND1_TYPE is expected type for the values in SRC_LAT.
@@ -1817,24 +1900,69 @@ propagate_vals_across_arith_jfunc (cgraph_edge *cs,
ipcp_value<tree> *src_val;
bool ret = false;
- /* Do not create new values when propagating within an SCC because if there
- are arithmetic functions with circular dependencies, there is infinite
- number of them and we would just make lattices bottom. If this condition
- is ever relaxed we have to detect self-feeding recursive calls in
- cgraph_edge_brings_value_p in a smarter way. */
+ /* Due to circular dependencies, propagating within an SCC through arithmetic
+ transformation would create infinite number of values. But for
+ self-feeding recursive function, we could allow propagation in a limited
+ count, and this can enable a simple kind of recursive function versioning.
+ For other scenario, we would just make lattices bottom. */
if (opcode != NOP_EXPR && ipa_edge_within_scc (cs))
- ret = dest_lat->set_contains_variable ();
+ {
+ int i;
+
+ if (src_lat != dest_lat || param_ipa_cp_max_recursion_depth < 1)
+ return dest_lat->set_contains_variable ();
+
+ auto_vec<ipcp_value<tree> *, 8> val_seeds;
+
+ for (src_val = src_lat->values; src_val; src_val = src_val->next)
+ {
+ /* Now we do not use self-recursively generated value as propagation
+ source, this is absolutely conservative, but could avoid explosion
+ of lattice's value space, especially when one recursive function
+ calls another recursive. */
+ if (self_recursively_generated_p (src_val))
+ {
+ /* If the lattice has already been propagated for the call site,
+ no need to do that again. */
+ for (ipcp_value_source<tree> *s = src_val->sources; s;
+ s = s->next)
+ if (s->cs == cs)
+ return dest_lat->set_contains_variable ();
+ }
+ else
+ val_seeds.safe_push (src_val);
+ }
+
+ /* Recursively generate lattice values with a limited count. */
+ FOR_EACH_VEC_ELT (val_seeds, i, src_val)
+ {
+ for (int j = 1; j < param_ipa_cp_max_recursion_depth; j++)
+ {
+ tree cstval = get_val_across_arith_op (opcode, opnd1_type, opnd2,
+ src_val, res_type);
+ if (!cstval)
+ break;
+
+ /* Try to place the new lattice value after its source, which
+ can decrease iterations of propagate stage. */
+ ret |= dest_lat->add_value (cstval, cs, src_val, src_idx,
+ src_offset, &src_val, true);
+ gcc_checking_assert (src_val);
+ }
+ }
+ ret |= dest_lat->set_contains_variable ();
+ }
else
for (src_val = src_lat->values; src_val; src_val = src_val->next)
{
- tree opnd1 = src_val->value;
- tree cstval = NULL_TREE;
-
- /* Skip source values that is incompatible with specified type. */
- if (!opnd1_type
- || useless_type_conversion_p (opnd1_type, TREE_TYPE (opnd1)))
- cstval = ipa_get_jf_arith_result (opcode, opnd1, opnd2, res_type);
+ /* Now we do not use self-recursively generated value as propagation
+ source, otherwise it is easy to make value space of normal lattice
+ overflow. */
+ if (self_recursively_generated_p (src_val))
+ continue;
+ tree cstval = get_val_across_arith_op (opcode, opnd1_type, opnd2,
+ src_val, res_type);
if (cstval)
ret |= dest_lat->add_value (cstval, cs, src_val, src_idx,
src_offset);
@@ -2939,7 +3067,7 @@ hint_time_bonus (ipa_hints hints)
static inline int64_t
incorporate_penalties (ipa_node_params *info, int64_t evaluation)
{
- if (info->node_within_scc)
+ if (info->node_within_scc && !info->node_is_self_scc)
evaluation = (evaluation
* (100 - param_ipa_cp_recursion_penalty)) / 100;
@@ -2983,7 +3111,8 @@ good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit,
count_sum.dump (dump_file);
fprintf (dump_file, "%s%s) -> evaluation: " "%" PRId64
", threshold: %i\n",
- info->node_within_scc ? ", scc" : "",
+ info->node_within_scc
+ ? (info->node_is_self_scc ? ", self_scc" : ", scc") : "",
info->node_calling_single_call ? ", single_call" : "",
evaluation, param_ipa_cp_eval_threshold);
}
@@ -3001,7 +3130,8 @@ good_cloning_opportunity_p (struct cgraph_node *node, int time_benefit,
"size: %i, freq_sum: %i%s%s) -> evaluation: "
"%" PRId64 ", threshold: %i\n",
time_benefit, size_cost, freq_sum,
- info->node_within_scc ? ", scc" : "",
+ info->node_within_scc
+ ? (info->node_is_self_scc ? ", self_scc" : ", scc") : "",
info->node_calling_single_call ? ", single_call" : "",
evaluation, param_ipa_cp_eval_threshold);
@@ -3495,14 +3625,30 @@ propagate_constants_topo (class ipa_topo_info *topo)
while (v)
{
struct cgraph_edge *cs;
+ class ipa_node_params *info = NULL;
+ bool self_scc = true;
for (cs = v->callees; cs; cs = cs->next_callee)
if (ipa_edge_within_scc (cs))
{
- IPA_NODE_REF (v)->node_within_scc = true;
+ cgraph_node *callee = cs->callee->function_symbol ();
+
+ if (v != callee)
+ self_scc = false;
+
+ if (!info)
+ {
+ info = IPA_NODE_REF (v);
+ info->node_within_scc = true;
+ }
+
if (propagate_constants_across_call (cs))
- push_node_to_stack (topo, cs->callee->function_symbol ());
+ push_node_to_stack (topo, callee);
}
+
+ if (info)
+ info->node_is_self_scc = self_scc;
+
v = pop_node_from_stack (topo);
}
@@ -3884,6 +4030,9 @@ get_info_about_necessary_edges (ipcp_value<valtype> *val, cgraph_node *dest,
hot |= cs->maybe_hot_p ();
if (cs->caller != dest)
non_self_recursive = true;
+ else if (src->val)
+ gcc_assert (values_equal_for_ipcp_p (src->val->value,
+ val->value));
}
cs = get_next_cgraph_edge_clone (cs);
}
@@ -3897,6 +4046,19 @@ get_info_about_necessary_edges (ipcp_value<valtype> *val, cgraph_node *dest,
*freq_sum = freq;
*count_sum = cnt;
*caller_count = count;
+
+ if (!hot && IPA_NODE_REF (dest)->node_within_scc)
+ {
+ struct cgraph_edge *cs;
+
+ /* Cold non-SCC source edge could trigger hot recursive execution of
+ function. Consider the case as hot and rely on following cost model
+ computation to further select right one. */
+ for (cs = dest->callers; cs; cs = cs->next_caller)
+ if (cs->caller == dest && cs->maybe_hot_p ())
+ return true;
+ }
+
return hot;
}
diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
index 7eb96a057fe..ff7675dbf6f 100644
--- a/gcc/ipa-prop.h
+++ b/gcc/ipa-prop.h
@@ -495,6 +495,8 @@ public:
unsigned node_dead : 1;
/* Node is involved in a recursion, potentionally indirect. */
unsigned node_within_scc : 1;
+ /* Node contains only direct recursion. */
+ unsigned node_is_self_scc : 1;
/* Node is calling a private function called only once. */
unsigned node_calling_single_call : 1;
/* False when there is something makes versioning impossible. */
diff --git a/gcc/params.opt b/gcc/params.opt
index be0a3a15598..8951935cc77 100644
--- a/gcc/params.opt
+++ b/gcc/params.opt
@@ -210,6 +210,10 @@ Threshold ipa-cp opportunity evaluation that is still considered beneficial to c
Common Joined UInteger Var(param_ipa_cp_loop_hint_bonus) Init(64) Param
Compile-time bonus IPA-CP assigns to candidates which make loop bounds or strides known.
+-param=ipa-cp-max-recursion-depth=
+Common Joined UInteger Var(param_ipa_cp_max_recursion_depth) Init(7) Param
+Maximum depth of recursive cloning for self-recursive function.
+
-param=ipa-cp-recursion-penalty=
Common Joined UInteger Var(param_ipa_cp_recursion_penalty) Init(40) IntegerRange(0, 100) Param
Percentage penalty the recursive functions will receive when they are evaluated for cloning.
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 834c17a6d7f..cd572e67fc4 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@
+2019-11-13 Feng Xue <f...@os.amperecomputing.com>
+
+ PR ipa/92133
+ * gcc.dg/ipa/ipa-clone-2.c: New test.
+
2019-11-13 Richard Sandiford <richard.sandif...@arm.com>
* gcc.target/aarch64/sve/mask_struct_store_3.c: Add
diff --git a/gcc/testsuite/gcc.dg/ipa/ipa-clone-2.c b/gcc/testsuite/gcc.dg/ipa/ipa-clone-2.c
new file mode 100644
index 00000000000..c6c26f73ee5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/ipa/ipa-clone-2.c
@@ -0,0 +1,47 @@
+/* { dg-do compile } */
+/* { dg-options "-O3 -fdump-ipa-cp-details -fno-early-inlining --param ipa-cp-max-recursion-depth=8" } */
+
+int fn();
+
+int data[100];
+
+int recur_fn (int i)
+{
+ int j;
+
+ if (i == 6)
+ {
+ fn();
+ fn();
+ fn();
+ fn();
+ fn();
+ fn();
+ fn();
+ fn();
+ fn();
+ fn();
+ fn();
+ fn();
+ return 10;
+ }
+
+ data[i] = i;
+
+ for (j = 0; j < 100; j++)
+ recur_fn (i + 1);
+
+ return i;
+}
+
+int main ()
+{
+ int i;
+
+ for (i = 0; i < 100; i++)
+ recur_fn (1) + recur_fn (-5);
+
+ return 1;
+}
+
+/* { dg-final { scan-ipa-dump-times "Creating a specialized node of recur_fn/\[0-9\]*\\." 12 "cp" } } */
--
2.17.1
