Re: Question about updating CFG block counters in purge_dead_edges [was "Questionon bad counters."]

[Peter Steinmetz <steinmtz at us dot ibm dot com>]

Added a better subject line.. Pete.


gcc-owner@gcc.gnu.org wrote on 09/30/2005 11:03:59 AM:

>
> I'm not entirely sure how gcc's CFG structure all fits together yet, so
> I'll ask for some input on this one:
>
> While looking through some dumps from a compile using -fprofile-use, I
> noticed the following in the "jump" dump file:
>
> Basic block 164 prev 163, next -2, loop_depth 0, count 1672, freq 1482.
> Predecessors:  163 [100.0%]  count:836 (fallthru)
> Successors:  EXIT [100.0%]  count:1672 (fallthru)
> Invalid sum of incoming frequencies 741, should be 1482
> Invalid sum of incoming counts 836, should be 1672
>
> I decided to try and figure out why the sum of incoming frequencies was
> invalid.  I've found where the mistake is introduced, and think I know
what
> needs to be done to fix it, but perhaps someone can confirm or suggest an
> alternative.
>
>
>
> Here are the last few blocks dumped just before
> cfgbuild.find_bb_boundaries.  The counts look good at this point (note
> especially block 162).
>
> Basic block 153 prev 152, next 154, loop_depth 0, count 836, freq 741.
> Predecessors:  0 [27.8%]  count:232 12 151 [100.0%]  count:604 152
[100.0%]
> (fallthru)
> Successors:  162 [100.0%]  count:836
>
> Basic block 154 prev 153, next 155, loop_depth 1, count 195, freq 173,
> probably never executed.
> Predecessors:  72 [8.1%]  count:36 74 [39.0%]  count:159 73 159 [100.0%]
> Successors:  78 [66.7%]  count:130 155 [33.3%]  count:65 (fallthru)
>
> Basic block 155 prev 154, next 162, loop_depth 0, count 65, freq 58,
> probably never executed.
> Predecessors:  154 [33.3%]  count:65 (fallthru)
> Successors:  79 [100.0%]  count:65
>
> Basic block 162 prev 155, next -2, loop_depth 0, count 836, freq 741.
> Predecessors:  153 [100.0%]  count:836
> Successors:  EXIT [100.0%]  count:836 (fallthru)
>
>
> -------------
> After cfgbuild.find_bb_boundaries, there are a few new blocks, and block
> 162 has been disconnected from the graph.  Block 162 has no predecessors,
> yet it's count remains at 836 and it's frequency at 741 which are
invalid.
> I believe blocks 163 and 164 were created while splitting block 162, and
> thus inherited the same count and frequency.
>
>
> Basic block 153 prev 152, next 154, loop_depth 0, count 836, freq 741.
> Predecessors:  0 [27.8%]  count:232 12 151 [100.0%]  count:604 152
[100.0%]
> (fallthru)
> Successors:
>
> Basic block 154 prev 153, next 155, loop_depth 1, count 195, freq 173,
> probably never executed.
> Predecessors:  72 [8.1%]  count:36 74 [39.0%]  count:159 73 159 [100.0%]
> Successors:  78 [66.7%]  count:130 155 [33.3%]  count:65 (fallthru)
>
> Basic block 155 prev 154, next 162, loop_depth 0, count 65, freq 58,
> probably never executed.
> Predecessors:  154 [33.3%]  count:65 (fallthru)
> Successors:  79 [100.0%]  count:65
>
> Basic block 162 prev 155, next 163, loop_depth 0, count 836, freq 741.
> Predecessors:
> Successors:
> Invalid sum of incoming frequencies 0, should be 741
> Invalid sum of incoming counts 0, should be 836
>
> Basic block 163 prev 162, next 164, loop_depth 0, count 836, freq 741.
> Predecessors:
> Successors:
> Invalid sum of incoming frequencies 0, should be 741
> Invalid sum of incoming counts 0, should be 836
>
> Basic block 164 prev 163, next -2, loop_depth 0, count 836, freq 741.
> Predecessors:
> Successors:  EXIT [100.0%]  count:836 (fallthru)
> Invalid sum of incoming frequencies 0, should be 741
> Invalid sum of incoming counts 0, should be 836
>
>
> -------------
> Later on, the cfg has apparently been rebuilt.  Some of the blocks with
bad
> counts were reattached to the graph and their counts propagated.  The
> result is the invalid block count I initially observed.  Note here that
the
> count and frequency for block 164 are exactly double what they should be.
>
> Basic block 159 prev 158, next 160, loop_depth 0, count 836, freq 741.
> Predecessors:  1 [27.8%]  count:232 13 157 [100.0%]  count:604 158
[100.0%]
> (fallthru)
> Successors:  163 [100.0%]  count:836
>
> Basic block 160 prev 159, next 161, loop_depth 1, count 195, freq 173,
> probably never executed.
> Predecessors:  75 [8.1%]  count:36 77 [39.0%]  count:159 76 79 [100.0%]
> Successors:  82 [66.7%]  count:130 161 [33.3%]  count:65 (fallthru)
>
> Basic block 161 prev 160, next 163, loop_depth 0, count 65, freq 58,
> probably never executed.
> Predecessors:  160 [33.3%]  count:65 (fallthru)
> Successors:  83 [100.0%]  count:65
>
> Basic block 163 prev 161, next 164, loop_depth 0, count 836, freq 741.
> Predecessors:  159 [100.0%]  count:836
> Successors:  164 [100.0%]  count:836 (fallthru)
>
> Basic block 164 prev 163, next -2, loop_depth 0, count 1672, freq 1482.
> Predecessors:  163 [100.0%]  count:836 (fallthru)
> Successors:  EXIT [100.0%]  count:1672 (fallthru)
> Invalid sum of incoming frequencies 741, should be 1482
> Invalid sum of incoming counts 836, should be 1672
>
>
> ------------
>
> The problem appears to be in the function cfgrtl.purge_dead_edges which
is
> called by find_bb_boundaries.  There are a couple of cases where
> "remove_edge" is called to remove an edge from the graph.  In the above
> example, the edge being removed is the only predecessor edge of the
> destination block(162).  The edge is removed, but the count and frequency
> of the now orphaned destination block(162) are not adjusted.  When these
> orphaned blocks later get reconnected to the graph (the part I'm not
clear
> on :-) .. their bad counts get incrementally added back to the flow of
the
> graph.
>
> I experimented with adjusting the count and frequency of the destination
> block prior to removing the edge in purge_dead_edges and that seems to
> solve the problem.
>
> I keep wondering if there is a more generic way the counts should be
> adjusted when an edge is removed.. for example in the remove_edge code
> itself.  But doing it there seems to break other things.  Any thoughts
are
> appreciated.
>
> Pete.
>