ipa-cp: Propagation boost for recursion generated values
Recursive call graph edges, even when they are hot and important for
the compiled program, can never have frequency bigger than one, even
when the actual time savings in the next recursion call are not
realized just once but depend on the depth of recursion. The current
IPA-CP effect propagation code did not take that into account and just
used the frequency, thus severely underestimating the effect.
This patch artificially boosts values taking part in such calls. If a
value feeds into itself through a recursive call, the frequency of the
edge is multiplied by a parameter with default value of 6, basically
assuming that the recursion will take place 6 times. This value can
of course be subject to change.
Moreover, values which do not feed into themselves but which were
generated for a self-recursive call with an arithmetic
pass-function (aka the 548.exchange "hack" which however is generally
applicable for recursive functions which count the recursion depth in
a parameter) have the edge frequency multiplied as many times as there
are generated values in the chain. In essence, we will assume they
are all useful.
This patch partially fixes the current situation when we fail to
optimize 548.exchange with PGO. In the benchmark one recursive edge
count overwhelmingly dominates all other counts in the program and so
we fail to perform the first cloning (for the nonrecursive entry call)
because it looks totally insignificant.
gcc/ChangeLog:
2021-07-16 Martin Jambor <mjambor@suse.cz>
* params.opt (ipa-cp-recursive-freq-factor): New.
* ipa-cp.c (ipcp_value): Switch to inline initialization. New members
scc_no, self_recursion_generated_level, same_scc and
self_recursion_generated_p.
(ipcp_lattice::add_value): Replaced parameter unlimited with
same_lat_gen_level, usit it determine limit of values and store it to
the value.
(ipcp_lattice<valtype>::print): Dump the new fileds.
(allocate_and_init_ipcp_value): Take same_lat_gen_level as a new
parameter and store it to the new value.
(self_recursively_generated_p): Removed.
(propagate_vals_across_arith_jfunc): Use self_recursion_generated_p
instead of self_recursively_generated_p, store self generation level
to such values.
(value_topo_info<valtype>::add_val): Set scc_no.
(value_topo_info<valtype>::propagate_effects): Multiply frequencies of
recursively feeding values and self generated values by appropriate
new factors.