[tree-ssa] edge insertion/split problem

[Michael Matz]

Hi,

On Mon, 16 Jun 2003 law@redhat.com wrote:

Sorry to continually interrupt your tree-ssa discussions without any
work on it, but these lengthy discussions about things which ought to be
trivial make me a bit nervous about the new infrastructure.

> I don't see how that can work.  What we effectively have is something like
> this:
>
>            7
>           /|\
>          / | \
>         8  |  |
>          \ |  |
>           \|  |
>            9  |
>             \ /
>              10
>
> [ All control flow down. ]
>
> 7->10 and 9->10 are both fall-thru edges.

How can both be fall-thru?  Fall-thru is an edge whose head transfers flow
to the tail by a non-jump.  That's by definition only possible for one of
the predecessors of a block.  I.e. one of either 9 and 7 already has to
have a jump insn at the end.  Even if 9 is empty one of the edges has to
be non-fallthru, at least conceptually.

> If you're going to insert on the edge from 7->10 in this graph, you must
> modify block 9.  I can't see any sensible alternatives.

Two cases:
  1) 7->10 is fall-through.  9 jumps already to 10, so it doesn't need to
     be changed.  A new block is created in front of 10, which falls thru
     to 10, and which is jumped to by 7.  Alternatively it's created after
     7, fall-thru from 7, and itself jumps to 10.  If both aren't possible
     it's created out of way, and and explicitely is jumped into by 7, and
     itself jumps to 10.
  2) 9->10 is fall-through.  Ergo 7->10 can't be.  The new block is jumped
     into by 7, and itself jumps to 10.

No changing of block 9 involved either way.

It would all be even easier, if you don't have any fall-thru edges at all,
and make all jumps explicit.  Let any bb-reorder take care of creating
fall-throughs.

Your notion of nested trees which can involve control transfer is at root
of all this confusion, as it seems to me that this creates the funny
problem of multiple fall-thru predecessors of a block.  It's simply
impossible to have such.  Similar for all the other problems you were
discussing over the last weeks dealing with critical edges and edge
splitting.  Those are long solved with a normal CFG.


Ciao,
Michael.