cfg_layout_split_edge doesn't handle the general case correctly

[Mostafa Hagog]

James E Wilson <wilson@specifixinc.com> wrote on 20/08/2004 04:30:58:

> Mostafa Hagog wrote:
> > according to the below lines, cfg_layout_split_edge adds the newly
> > created basic block after e->src, this is not correct when there
> > is at least one additional edge that is fallthru that is going out
> > of e->src.
>
> I am not very familiar with the cfg code.
>
> Looking at this, you didn't say exactly why what cfg_layout_split_edge
> is doing is wrong.  You didn't say why you got an ICE in
> commit_edge_insertions.  I would need more info about what is going on.
>
> You pointed at the tree code as a counter example, but the comments in
> the tree code indicate that it is doing something just to make the dumps
> look prettier.  It doesn't say anything about correctness.  So this
> isn't very convincing.
>
> Trying to guess what is wrong, I would guess that perhaps there is an
> ordering issue.  When we traverse the list of basic blocks, maybe we
> need to initialize something for one block before another block?
> However, you haven't provided any info about what is being initialized
> or why the initialization is order dependent, so I can't suggest
solutions.
> --
> Jim Wilson, GNU Tools Support, http://www.SpecifixInc.com

The wrong thing is cfg_layout_split_edge is the fact that the newly created
basic
block is always inserted after the edge->src in the linked list of the
basic blocks
(bb_next, bb_prev fields of basic_block form this list). The problematic
case is when
the source block (of the splitted edge) has two successors and we are
splitting the non fallthru edge, in such a case we cannot insert the new
block in between.
Example:
  ______
 |      |
BB1 <---
 |
  ---fallthru--> BB2

We want to split the back-edge (not the fallthru edge).
A new BB3 is created. Before the splitting BB1->next_bb == BB2,
cfg_layout_split_edge inserts BB3 between BB1 and BB2 in the linked list
and now BB1->next_bb == BB3, and BB3->next_bb == BB2 (bb_prev is set
correctly).
This is wrong because if we have a fullthru edge going of a block next_bb
must
be the destination of that fallthru edge.

Mostafa.