Re: Fix PR 53743 and other -freorder-blocks-and-partition failures (issue6823047)

[Teresa Johnson <tejohnson at google dot com>]

On Fri, May 10, 2013 at 4:52 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> On 05/07/13 23:13, Teresa Johnson wrote:
>> >----------------------
>> >Revised patch that fixes failures encountered when enabling
>> >-freorder-blocks-and-partition, including the failure reported in PR 53743.
>> >
>> >This includes new verification code to ensure no cold blocks dominate hot
>> >blocks contributed by Steven Bosscher.
>> Seems like a reasonable verification; presumably if we have a cold
>> block dominating a hot block, then the block/edge frequencies are
>> badly broken.  Ah, just saw the comments for the other case where
>> this happens.  cold entry, but hot loop inside pushing over the
>> barrier. Arguably given a cold block in the dominator graph, all its
>> children should have their frequences scaled down to avoid that situation.
>
> Yep, also note that sanity checking anything about frequencies is really hard.
> There are very many places in compiler that necesarilly need to invalidate
> frequencies in weird ways (at least short of rebuilding the whole profile
> from probabilities again).

Yes, as noted in the comments this was in part due to several places
where counts/frequencies were not kept in sync. Rather than try to fix
all of these, or do any scaling of frequencies, the partitioning code
now just enforces that the partitioning is sane w.r.t. the given
counts. This is done during bb partitioning. The sanity checking
routine was also useful for finding places where optimization passes
were splitting edges and causing hot blocks previously reached by both
hot and cold blocks to become dominated by cold blocks (see comments
in commit_edge_insertions in my patch), and making sure they got fixed
up.

But there is the issue of what we should do in the case of an
infrequent but non-zero entry (marked cold by maybe_hot_count_p
because its count is less than the number of training runs) that leads
to a hot loop. The code I added to the partitioning routine
(find_rarely_executed_basic_blocks_and_crossing_edges) will cause the
entry to also be placed in the hot partition. I would argue this is
the desired behavior - if the routine contains code that is very hot
for, say, 1/2 its training runs, the entry and hot loop (and
everything on the path in between) should be in the hot partition.

>
>> I can't really comment on the cfglayout and related stuff -- it was
>> added at a time when I wasn't doing much with GCC and thus I don't
>> know much about it.
>
> I think I can take a look at the cfglayout stuff. Splitting the patch would be great.

Thanks, that would be great. I can split the patch first.

>
> Honza
>>
>> However, I like the changes to record if we've done partitioning and
>> checking those instead of flag_reorder_blocks_and_partition.  That's
>> simple enough that I'd support pulling it out as a separate patch
>> and installing immediately if that can be done so without major
>> headaches.

Ok, thanks, will do.

>>
>> I think we could do something similar with the code to verify the
>> idom of a hot block is also hot.  Though looking at the
>> implementation I wonder if it could be simplified by walking the
>> dominator tree?  I can't look at it real closely tonight though.

Looking at this code again, I agree with you. It looks like it is
going to walk cold bb's more than once and O(n^2) in the worst case. I
will fix this (there are a couple places in the patch that do a walk
to ensure that this is not violated).

>>
>> Could you pull those two logical hunks of work out into individual
>> patches.

Will do. The only complication with splitting out the dominance
checking stuff is that there are a number of changes in the patch to
ensure that we don't violate this (hot block can't be dominated by
cold block). I am not sure it makes sense or will be easy to split all
of these out. I think what I will do is try to pull the big related
chunks of them out to a separate patch (the new verification code, the
code to prevent this in the partitioning routine, and
fixup_partitions), but there are going to be a few places in the other
patch that do some fixups related to this (e.g. in rtl_split_edge)
that I would like to leave in the larger correctness patch.

Thanks,
Teresa

>>
>> jeff



--
Teresa Johnson | Software Engineer | tejohnson@google.com | 408-460-2413