Added a better subject line.. Pete.
[EMAIL PROTECTED] 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. >
