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: Tue, 24 Nov 2020 13:44:35 +0800 [thread overview]
Message-ID: <h48sg8z48cc.fsf@genoa.aus.stglabs.ibm.com> (raw)
In-Reply-To: <5c0c5060-15d2-b628-1b32-6bf32164e193@redhat.com> (Jeff Law's message of "Wed, 18 Nov 2020 16:45:44 -0700")
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
next prev parent reply other threads:[~2020-11-24 5:44 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 [this message]
2020-12-04 3:05 ` Jiufu Guo
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=h48sg8z48cc.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).