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. > > jeff
