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