From: Teresa Johnson <tejohnson@google.com>
To: Jan Hubicka <hubicka@ucw.cz>
Cc: "gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>,
"marxin.liska" <marxin.liska@gmail.com>
Subject: Re: [PATCH] Sanitize block partitioning under -freorder-blocks-and-partition
Date: Wed, 02 Oct 2013 17:55:00 -0000 [thread overview]
Message-ID: <CAAe5K+Vrt07aHBx_SOGEPbAwA4_9RvGS+vVGjoQW7nDQE147mA@mail.gmail.com> (raw)
In-Reply-To: <20131002161917.GD7181@kam.mff.cuni.cz>
On Wed, Oct 2, 2013 at 9:19 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> 2013-09-29 Teresa Johnson <tejohnson@google.com>
>>
>> * bb-reorder.c (find_rarely_executed_basic_blocks_and_crossing_edges):
>> Treat profile insanities conservatively.
>> * predict.c (probably_never_executed): New function. Treat profile
>> insanities conservatively.
>> (probably_never_executed_bb_p): Invoke probably_never_executed.
>> (probably_never_executed_edge_p): Invoke probably_never_executed.
>>
>> Index: bb-reorder.c
>> ===================================================================
>> --- bb-reorder.c (revision 202947)
>> +++ bb-reorder.c (working copy)
>> @@ -1564,8 +1564,25 @@ find_rarely_executed_basic_blocks_and_crossing_edg
>> /* Mark which partition (hot/cold) each basic block belongs in. */
>> FOR_EACH_BB (bb)
>> {
>> + bool cold_bb = false;
>
> whitespace here
meaning add a line of whitespace? Ok, done.
>
>> if (probably_never_executed_bb_p (cfun, bb))
>> {
>> + /* Handle profile insanities created by upstream optimizations
>> + by also checking the incoming edge weights. If there is a non-cold
>> + incoming edge, conservatively prevent this block from being split
>> + into the cold section. */
>> + cold_bb = true;
>> + FOR_EACH_EDGE (e, ei, bb->preds)
>> + {
>> + if (!probably_never_executed_edge_p (cfun, e))
>> + {
>> + cold_bb = false;
>> + break;
>> + }
>> + }
>
> You can probably elimnate the extra braces.
> So we won't propagate deeper in the CFG, right?
Done.
>
> This change is OK.
>
>> + }
>> + if (cold_bb)
>> + {
>> BB_SET_PARTITION (bb, BB_COLD_PARTITION);
>> cold_bb_count++;
>> }
>> Index: predict.c
>> ===================================================================
>> --- predict.c (revision 202947)
>> +++ predict.c (working copy)
>> @@ -226,26 +226,26 @@ maybe_hot_edge_p (edge e)
>> }
>>
>>
>> -/* Return true in case BB is probably never executed. */
>>
>> -bool
>> -probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
>> +/* Return true if profile COUNT and FREQUENCY, or function FUN static
>> + node frequency reflects never being executed. */
>> +
>> +static bool
>> +probably_never_executed (struct function *fun,
>> + gcov_type count, int frequency)
>> {
>> gcc_checking_assert (fun);
>> if (profile_status_for_function (fun) == PROFILE_READ)
>> {
>> - if ((bb->count * 4 + profile_info->runs / 2) / profile_info->runs > 0)
>> + if ((count * 4 + profile_info->runs / 2) / profile_info->runs > 0)
>> return false;
>> - if (!bb->frequency)
>> - return true;
>> - if (!ENTRY_BLOCK_PTR->frequency)
>> - return false;
>> - if (ENTRY_BLOCK_PTR->count && ENTRY_BLOCK_PTR->count < REG_BR_PROB_BASE)
>> - {
>> - return (RDIV (bb->frequency * ENTRY_BLOCK_PTR->count,
>> - ENTRY_BLOCK_PTR->frequency)
>> - < REG_BR_PROB_BASE / 4);
>> - }
>> + // If this is a profiled function (entry bb non-zero count), then base
>> + // the coldness decision on the frequency. This will handle cases where
>> + // counts are not updated properly during optimizations or expansion.
>> + if (ENTRY_BLOCK_PTR->count)
>> + return frequency == 0;
>> + // Unprofiled function, frequencies statically assigned. All bbs are
>> + // treated as cold.
>
> I would avoid combining C and C++ comments in the function.
Fixed.
> Did you get some data on how many basic blocks we now consider hot?
No, I can do that.
>
> The previous implemntation consdered block as never executed when frequencies
> indicates that it is executed in at most 1/4th of invocations of program.
> You essentially chnage to 1/10000. The first seems bit too high given the
> way we distribute probabilities in dojump and firends, second looks too low.
But why do we want to consider blocks as "probably never executed"
when the frequency suggests they are sometimes executed?
AFAICT, there are 2 main callers of this routine:
1) function splitting in bb-layout
2) function cgraph node weight
Where #2 will affect optimization of the function for size and also
function layout by the linker.
I would argue that for function splitting, we really want to know when
it is probably *never* executed - i.e. completely cold, since the cost
of jumping back and forth to the cold section is likely to be high.
I am not sure for #2 what the right ratio is. For function layout, we
may also want to place only really cold *never* executed functions
into the cold section, but I am less sure about optimization for size.
Perhaps we really need two different interfaces to test for different
levels of coldness:
probably_never_executed()
-> returns true when there is profile information for the function
and the bb has 0 count and 0 frequency.
-> invoked from bb-reorder.cc to drive function splitting
-> may want to consider invoking this as an additional check before
putting function into unlikely text section in the future.
possibly_never_executed()
-> essentially the existing logic in probably_never_executed_bb_p
-> invoked when marking the cgraph node
>
> The change introducing probably_never_executed with the current logic is OK.
Ok, I will commit the two approved parts for now (the change to
bb-reorder.c and the addition of probably_never_executed that uses the
existing logic from probably_never_executed_bb_p.
Thanks,
Teresa
> We may want to fine tune the ratio.
>
> Honza
>> return true;
>> }
>> if ((!profile_info || !flag_branch_probabilities)
>> @@ -256,19 +256,21 @@ maybe_hot_edge_p (edge e)
>> }
>>
>>
>> +/* Return true in case BB is probably never executed. */
>> +
>> +bool
>> +probably_never_executed_bb_p (struct function *fun, const_basic_block bb)
>> +{
>> + return probably_never_executed (fun, bb->count, bb->frequency);
>> +}
>> +
>> +
>> /* Return true in case edge E is probably never executed. */
>>
>> bool
>> probably_never_executed_edge_p (struct function *fun, edge e)
>> {
>> - gcc_checking_assert (fun);
>> - if (profile_info && flag_branch_probabilities)
>> - return ((e->count + profile_info->runs / 2) / profile_info->runs) == 0;
>> - if ((!profile_info || !flag_branch_probabilities)
>> - && (cgraph_get_node (fun->decl)->frequency
>> - == NODE_FREQUENCY_UNLIKELY_EXECUTED))
>> - return true;
>> - return false;
>> + return probably_never_executed (fun, e->count, EDGE_FREQUENCY (e));
>> }
>>
>> /* Return true if NODE should be optimized for size. */
--
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413
next prev parent reply other threads:[~2013-10-02 17:55 UTC|newest]
Thread overview: 62+ messages / expand[flat|nested] mbox.gz Atom feed top
2013-08-01 16:32 Teresa Johnson
2013-08-02 11:22 ` Bernhard Reutner-Fischer
2013-08-02 14:51 ` Teresa Johnson
2013-08-02 15:05 ` Jan Hubicka
2013-08-02 23:05 ` Steven Bosscher
2013-08-03 4:53 ` Teresa Johnson
2013-08-03 4:48 ` Teresa Johnson
2013-08-05 13:36 ` Teresa Johnson
2013-08-05 14:11 ` Jan Hubicka
2013-08-05 14:57 ` Teresa Johnson
2013-08-06 3:01 ` Teresa Johnson
[not found] ` <20130808222332.GA31755@kam.mff.cuni.cz>
2013-08-08 23:04 ` Teresa Johnson
2013-08-09 9:58 ` Jan Hubicka
2013-08-09 14:38 ` Teresa Johnson
2013-08-09 15:28 ` Jan Hubicka
2013-08-09 15:54 ` Martin Liška
2013-08-09 21:03 ` Teresa Johnson
2013-08-09 21:02 ` Teresa Johnson
2013-08-09 22:43 ` Jan Hubicka
2013-08-11 12:21 ` Jan Hubicka
2013-08-11 13:25 ` Teresa Johnson
2013-08-11 15:55 ` Martin Liška
2013-08-11 17:55 ` Jan Hubicka
2013-08-11 21:05 ` Jan Hubicka
2013-08-17 15:54 ` Teresa Johnson
2013-08-17 21:02 ` Jan Hubicka
2013-08-19 13:51 ` Teresa Johnson
2013-08-19 15:16 ` Jan Hubicka
2013-08-19 17:48 ` Teresa Johnson
2013-08-19 19:56 ` Martin Liška
2013-08-27 18:12 ` Teresa Johnson
2013-08-28 16:59 ` Jan Hubicka
2013-08-28 18:35 ` Teresa Johnson
2013-08-30 7:17 ` Teresa Johnson
2013-08-30 9:16 ` Jan Hubicka
2013-08-30 15:13 ` Teresa Johnson
2013-08-30 15:28 ` Jan Hubicka
2013-08-30 15:54 ` Teresa Johnson
2013-08-30 21:56 ` Rong Xu
2013-08-31 16:20 ` Jan Hubicka
2013-08-31 23:40 ` Jan Hubicka
2013-09-24 8:07 ` Teresa Johnson
2013-09-24 13:44 ` Jan Hubicka
2013-09-24 19:06 ` Teresa Johnson
2013-09-26 20:55 ` Rong Xu
2013-09-26 22:23 ` Jan Hubicka
2013-09-26 22:54 ` Rong Xu
2013-09-24 18:28 ` Jan Hubicka
2013-09-24 18:51 ` Teresa Johnson
2013-09-25 23:10 ` Teresa Johnson
2013-09-26 8:44 ` Teresa Johnson
2013-09-26 22:26 ` Jan Hubicka
2013-09-27 14:50 ` Teresa Johnson
2013-09-29 17:34 ` Teresa Johnson
2013-10-02 16:19 ` Jan Hubicka
2013-10-02 17:55 ` Teresa Johnson [this message]
2013-10-02 18:10 ` Jan Hubicka
2013-10-03 13:42 ` Teresa Johnson
2013-10-03 23:37 ` Teresa Johnson
2013-10-01 17:36 ` Teresa Johnson
2013-08-19 15:34 ` Teresa Johnson
2013-08-21 15:31 ` Jan Hubicka
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=CAAe5K+Vrt07aHBx_SOGEPbAwA4_9RvGS+vVGjoQW7nDQE147mA@mail.gmail.com \
--to=tejohnson@google.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=hubicka@ucw.cz \
--cc=marxin.liska@gmail.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).