Re: [tree-ssa] Removal of gotos from cfg based ir

[Jan Hubicka <jh at suse dot cz>]

> On Thu, 2003-11-27 at 12:13, Zdenek Dvorak wrote:
> > Hello,
> > 
> > > > > I am not quite sure what was the resolution of the discussion; anyway,
> > > > > here is the patch without the {COND,SWITCH}_EXPR ==> CF_EXPR change.
> > > > 
> > > > My honest belief is that we end up with agreement that declaring CFG as
> > > > part of low level trees IL is good idea, so I really hope we will make
> > > > progress on this and get into job of doing real cfg_cleanup and CFG
> > > > manipulation infrastructure soon.
> > > > 
> > > To date I have not seen a convincing argument supporting this IL
> > > change.
> > 
> > ummm. I believe Honza has sent a list with a long list of such arguments
> > in the thread; I don't want to repeat it here, since it should be easy
> > to find.
> Then I think a summary is in order since I don't recall seeing a long
> list of supporting arguments. I recall 2 things.
> 
> > 
> > There is of course nothing that would be impossible in the current
> > state; this is equivalent change.  Just many things are easier, since
> > you have no problems of this type:
> > 
> 
> I recall these 2, are there more?
> 
> 1 - copying blocks with fallthrough edges AND abnormal edges causes a
> new block to be created. (this was the primary reason I think)
> 2 - propagating profiling information along the cfg.

Actually 2 is independent on how we decide to deal with CFG
THe problems I run into so far are:

This is all about magically appearing blocks, but to summary, the
following problems we got into while working on RTL:
1) redirect_edge_and_branch may create basic block.  So each pass has to decide
   whether to call redirect_edge_and_branch and lose in some cases or
   redirect_edge_and_branch_force and update datastructures
2) Edge splitting implementation is much more convenient and always
   result in only 1 basic block created, now 2 that are dificult to
   communicate with updating pass
3) Basic block merging does not introduce new basic blocks
4) RTL optimizer has cfg_cleanup implemented as "iterate until
   stabilized" optimization because fallthru edges create new problems.
   With no fallthru forwarders one can first forward edges, then delete
   unrechable blocks, merge blocks last.
5) RTL cfg_cleanup does jump threading and crossjumping because of
   complex interactions
6) We had to invent cfg_layout mode (identical to Zdenek's scheme on
   trees) in order to write unroller and basic block reordering pass

Also I would like to point out that the scheme is used in some other
compilers.  It is also similar to one used by Morgan's book that also do
combine CFG construction and intermediate code production
> 
> If those are the only significant problem (and I dont consider things
> like having to add a label or modify a jump to be significant. Magically

Agreed here.
> appearing BB's *are* a problem) it seems like a lot of impact in order
> to make them simpler when we can handle it a different way, and we wont
> impact things like mudflap and the inliner, which are pretty unrelated.

Zdenek's code does not impact mudflap nor inliner in any way.
There are three different issues - how we want to represent program
during optimization, how we want to represent program during RTL
expansion and how we want to represent program during inlining.  These
three are already all different.

> 
> Out of curiosity, why can't we deal with 1) by delaying updating the IL
> until we're done, like we do with edge insertion.
> 
>   BB1
>      call X
>   BB2			BB9
>      <..>		  exception...
> 
> 
> duplicate BB1, make the edges the same, a fallthrough edge to BB2, and
> an abnormal edge to BB9. 
> 
> So we duplicate BB1, producing BB12:
> BB1
>   call X
> BB2                     BB9
>   <...>			  exception
> 
> BB12
>   call X  (BB12--fallthru-> BB2,  BB12--abnorm-> BB(
> 
> Then when you are done with the block manipulations, call
> commit_block_replications() or somesuch thing, and any block which has
> more than 1 fallthru predecessor gets a label, and a goto is inserted
> into a new block following each of those preds.  You don't get new basic
> blocks forming all over the place until you specifically want them.

This is precisely what cfglayout mode is doing on RTL.
The problem is that we then effectivly do have two different forms of
RTL and we need to duplicate a lot of code depending on what form the
particular pass is using.  Thus we do have longer term plan of
converting all passes to CFGlayout mode as it make all passes either
easier or equally hard as they are now.
> 
> Is there a reason the insert_on_edge/commit_edge_insertions model, or
> some variation,  wouldn't work for
> block_replication/commit_block_replication() sequences?
It is not only about replication.
For example if you want to take advantage for this during cfgcleanup,
you will have to enter the block_replication mode very often, kill all
gotos and forwarder blocks and re-emit them during leaving.  This is
expensive.

Honza
> 
> Andrew