On Mon, Oct 22, 2012 at 10:27:52PM +0200, Steven Bosscher wrote:
> I understand what your patch does, but I don't understand why it is correct.
>
> Why are there fake edges from bb7 and bb8 to exit when both are
> reverse-reachable from exit via the infinite loops? The infinite loops
> should be connected to exit, and bb7 and bb8 should be found by the
> DFS from the really dead ends in the cfg.
See what dominance.c does:
if (saw_unconnected)
{
FOR_EACH_BB_REVERSE (b)
{
if (di->dfs_order[b->index])
continue;
bitmap_set_bit (di->fake_exit_edge, b->index);
di->dfs_order[b->index] = di->dfsnum;
di->dfs_to_bb[di->dfsnum] = b;
di->dfs_parent[di->dfsnum] = di->dfs_order[last_basic_block];
di->dfsnum++;
calc_dfs_tree_nonrec (di, b, reverse);
}
}
bb7/bb8 (i.e. all bbs that are always in the end followed by infinite loops)
as well as all the bbs on the infinite loops are processed the above way,
they have no real path to exit, so aren't processed on the first iteration,
they aren't processed even after adding fake edges from zero successor bbs.
calc_dfs_tree then picks pretty much random bbs (one with highest index),
adds fake edge to it, walks it, then goes on with other bbs that are still
unconnected.
dominance.c doesn't use cfgloop.h (can it? Isn't it used before loops are
computed, perhaps after loops destroyed, etc.), so there is no guarantee
that loop->latch of endless loop will have the fake edge added and no other
bb before it. As 7 and 8 are bigger than 4 or 6, the above loop
starts with bb 8, finds that its predecessor has already been searched and
stops there, similarly for 7, then goes on with 6 with another fake edge to
exit.
Jakub
