Jiufu Guo <guoji...@linux.ibm.com> writes: > Jiufu Guo <guoji...@linux.ibm.com> writes: > >> Jeff Law <l...@redhat.com> writes: >> >>> On 11/18/20 12:28 AM, Richard Biener wrote: >>>> On Tue, 17 Nov 2020, Jeff Law wrote: >>>> >>>>> Minor questions for Jan and Richi embedded below... >>>>> >>>>> On 10/9/20 4:12 AM, guojiufu via Gcc-patches wrote: >>>>>> When investigating the issue from >>>>>> https://gcc.gnu.org/pipermail/gcc-patches/2020-July/549786.html >>>>>> I find the BB COUNTs of loop seems are not accurate in some case. >>>>>> For example: >>>>>> >>>>>> In below figure: >>>>>> >>>>>> >>>>>> COUNT:268435456<bb 2> pre-header >>>>>> | >>>>>> | .--------------------. >>>>>> | | | >>>>>> V v | >>>>>> COUNT:805306369<bb 3> | >>>>>> / \ | >>>>>> 33%/ \ | >>>>>> / \ | >>>>>> v v | >>>>>> COUNT:268435456<bb 10> COUNT:536870911<bb 15> | >>>>>> exit-edge | latch | >>>>>> ._________________. >>>>>> >>>>>> Those COUNTs have below equations: >>>>>> COUNT of exit-edge:268435456 = COUNT of pre-header:268435456 >>>>>> COUNT of exit-edge:268435456 = COUNT of header:805306369 * 33 >>>>>> COUNT of header:805306369 = COUNT of pre-header:268435456 + COUNT of >>>>>> latch:536870911 >>>>>> >>>>>> >>>>>> While after pcom: >>>>>> >>>>>> COUNT:268435456<bb 2> pre-header >>>>>> | >>>>>> | .--------------------. >>>>>> | | | >>>>>> V v | >>>>>> COUNT:268435456<bb 3> | >>>>>> / \ | >>>>>> 50%/ \ | >>>>>> / \ | >>>>>> v v | >>>>>> COUNT:134217728<bb 10> COUNT:134217728<bb 15> | >>>>>> exit-edge | latch | >>>>>> ._________________. >>>>>> >>>>>> COUNT<bb 3> != COUNT<bb 2> + COUNT<bb 15> >>>>>> COUNT<bb 10> != COUNT<bb2> >>>>>> >>>>>> In some cases, the probility of exit-edge is easy to estimate, then >>>>>> those COUNTs of other BBs in loop can be re-caculated. >>>>>> >>>>>> Bootstrap and regtest pass on ppc64le. Is this ok for trunk? >>>>>> >>>>>> Jiufu >>>>>> >>>>>> gcc/ChangeLog: >>>>>> 2020-10-09 Jiufu Guo <guoji...@linux.ibm.com> >>>>>> >>>>>> * cfgloopmanip.h (recompute_loop_frequencies): New function. >>>>>> * cfgloopmanip.c (recompute_loop_frequencies): New implementation. >>>>>> * tree-ssa-loop-manip.c (tree_transform_and_unroll_loop): Call >>>>>> recompute_loop_frequencies. >>>>>> >>>>>> --- >>>>>> gcc/cfgloopmanip.c | 53 +++++++++++++++++++++++++++++++++++++++ >>>>>> gcc/cfgloopmanip.h | 2 +- >>>>>> gcc/tree-ssa-loop-manip.c | 28 +++------------------ >>>>>> 3 files changed, 57 insertions(+), 26 deletions(-) >>>>>> >>>>>> diff --git a/gcc/cfgloopmanip.c b/gcc/cfgloopmanip.c >>>>>> index 73134a20e33..b0ca82a67fd 100644 >>>>>> --- a/gcc/cfgloopmanip.c >>>>>> +++ b/gcc/cfgloopmanip.c >>>>>> @@ -31,6 +31,7 @@ along with GCC; see the file COPYING3. If not see >>>>>> #include "gimplify-me.h" >>>>>> #include "tree-ssa-loop-manip.h" >>>>>> #include "dumpfile.h" >>>>>> +#include "cfgrtl.h" >>>>>> >>>>>> static void copy_loops_to (class loop **, int, >>>>>> class loop *); >>>>>> @@ -1773,3 +1774,55 @@ loop_version (class loop *loop, >>>>>> >>>>>> return nloop; >>>>>> } >>>>>> + >>>>>> +/* Recalculate the COUNTs of BBs in LOOP, if the probability of exit >>>>>> edge >>>>>> + is NEW_PROB. */ >>>>>> + >>>>>> +bool >>>>>> +recompute_loop_frequencies (class loop *loop, profile_probability >>>>>> new_prob) >>>>>> +{ >>>>>> + edge exit = single_exit (loop); >>>>>> + if (!exit) >>>>>> + return false; >>>>>> + >>>>>> + edge e; >>>>>> + edge_iterator ei; >>>>>> + edge non_exit; >>>>>> + basic_block * bbs; >>>>>> + profile_count exit_count = loop_preheader_edge (loop)->count (); >>>>>> + profile_probability exit_p = exit_count.probability_in >>>>>> (loop->header->count); >>>>>> + profile_count base_count = loop->header->count; >>>>>> + profile_count after_num = base_count.apply_probability (exit_p); >>>>>> + profile_count after_den = base_count.apply_probability (new_prob); >>>>>> + >>>>>> + /* Update BB counts in loop body. >>>>>> + COUNT<exit> = COUNT<preheader> >>>>>> + COUNT<exit> = COUNT<header> * exit_edge_probility >>>>>> + The COUNT<new_header> = COUNT<old_header> * old_exit_p / new_prob. >>>>>> */ >>>>>> + bbs = get_loop_body (loop); >>>>>> + scale_bbs_frequencies_profile_count (bbs, loop->num_nodes, after_num, >>>>>> + after_den); >>>>>> + free (bbs); >>>>>> + >>>>>> + /* Update probability and count of the BB besides exit edge (maybe >>>>>> latch). */ >>>>>> + FOR_EACH_EDGE (e, ei, exit->src->succs) >>>>>> + if (e != exit) >>>>>> + break; >>>>>> + non_exit = e; >>>>> Are we sure that exit->src has just two successors (will that case be >>>>> canonicalized before we get here?).? If it has > 2 successors, then I'm >>>>> pretty sure the frequencies get mucked up.? Richi could probably answer >>>>> whether or not the block with the loop exit edge can have > 2 successors. >>>> There's nothing preventing more than two edges in the SRC generally >>>> (the exit could be an edge off a switch). >>> That's precisely the case I was concerned about. >>> >>>> But of course this function >>>> is very likely called on loops that are countable which means niter >>>> analysis has to handle it which in turn means all exits are controlled >>>> by simple conditions on IVs. >>> Thanks. It sounds like it's unlikely we'll have > 2 out edges. >>>> >>>> I guess adding a gcc_assert (EDGE_COUNT (exit->src->succs) == 2) can't >>>> hurt (with a comment reflecting the above). >>> Sounds good to me. Just catching this case if it happens is good >>> enough for me -- if it trips we can come back and adjust the code to >>> distribute across the edges. >> With this gcc_assert, run bootstrap and regression test, no failure >> occur. >> For this patch, in the original code, there is code: >> - new_nonexit = single_pred_edge (loop->latch); >> - prob = new_nonexit->probability; >> - new_nonexit->probability = new_exit->probability.invert (); >> Which is also assume 2 successors. So, it may relative safe. >> >> Thanks, >> Jiufu Guo. >> >>> >>> So if Jan could chime in on the downstream edge updates question then I >>> think we'd be ready to move forward. Oh, this may be indicate 'approval with comments', right? :)
Thanks, Jiufu Guo. >>> >>> jeff > > Hi, > > I saw Jeff say ok for patch [PATCH 2/2] > https://gcc.gnu.org/pipermail/gcc-patches/2020-December/560833.html. > > I'm wondering if we can approval this patch [PATCH 1/2] > https://gcc.gnu.org/pipermail/gcc-patches/2020-October/555871.html. > and then I may commit these patches to trunk. :) > > Thanks, > Jiufu Guo.
