Re: [PATCH 1/2] correct BB frequencies after loop changed

[Jiufu Guo <guojiufu@linux.ibm.com>]

Jiufu Guo <guojiufu@linux.ibm.com> writes:

> Jiufu Guo <guojiufu@linux.ibm.com> writes:
>
>> Jeff Law <law@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   <guojiufu@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.