From: Jiufu Guo <guojiufu@linux.ibm.com>
To: Jeff Law <law@redhat.com>
Cc: Richard Biener <rguenther@suse.de>,
gcc-patches@gcc.gnu.org, wschmidt@linux.ibm.com,
dje.gcc@gmail.com, segher@kernel.crashing.org,
Jan Hubicka <jh@suse.de>
Subject: Re: [PATCH 1/2] correct BB frequencies after loop changed
Date: Fri, 04 Dec 2020 11:05:38 +0800 [thread overview]
Message-ID: <h48lfee46f1.fsf@genoa.aus.stglabs.ibm.com> (raw)
In-Reply-To: <h48sg8z48cc.fsf@genoa.aus.stglabs.ibm.com> (Jiufu Guo's message of "Tue, 24 Nov 2020 13:44:35 +0800")
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.
>>
>> 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.
next prev parent reply other threads:[~2020-12-04 3:06 UTC|newest]
Thread overview: 19+ messages / expand[flat|nested] mbox.gz Atom feed top
2020-10-09 10:12 guojiufu
2020-10-09 10:12 ` [PATCH 2/2] reset edge probibility and BB-count for peeled/unrolled loop guojiufu
2020-11-12 3:03 ` Jiufu Guo
2020-12-02 5:26 ` Jeff Law
2020-11-17 22:07 ` [PATCH 1/2] correct BB frequencies after loop changed Jeff Law
2020-11-18 7:28 ` Richard Biener
2020-11-18 23:45 ` Jeff Law
2020-11-24 5:44 ` Jiufu Guo
2020-12-04 3:05 ` Jiufu Guo [this message]
2020-12-04 6:17 ` Jiufu Guo
2020-12-04 6:59 ` Martin Liška
2021-05-07 2:36 ` Ping: " guojiufu
2021-05-20 7:19 ` Ping^1: " guojiufu
2021-06-07 2:37 ` Ping^2: " guojiufu
2021-06-14 2:38 ` Ping: " Jeff Law
2021-06-14 9:16 ` Jan Hubicka
2021-06-15 4:57 ` guojiufu
2021-06-18 8:24 ` guojiufu
2021-07-05 3:13 ` guojiufu
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=h48lfee46f1.fsf@genoa.aus.stglabs.ibm.com \
--to=guojiufu@linux.ibm.com \
--cc=dje.gcc@gmail.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=jh@suse.de \
--cc=law@redhat.com \
--cc=rguenther@suse.de \
--cc=segher@kernel.crashing.org \
--cc=wschmidt@linux.ibm.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).