This is the mail archive of the mailing list for the GCC project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

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

On Thu, 2003-11-27 at 16:02, Jan Hubicka wrote:
> > On Thu, 2003-11-27 at 12:13, Zdenek Dvorak wrote:
> > > Hello,

> 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

the main problem is the appearing BB's then

> 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

I, for one, never trust anything I read :-) They always expound the
virtues, and its an exercise left to the reader to discover the horrible
reality of making the author's choices. :-)

> > 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.

Why should the program be represented differently during all these
phases when we the representation we have works? We dont want a
different IL during inlining or expansion in my opinion. 

If mudflap is going to insert code and branches and stuff after SSA
runs, but before expansion, then its going to have to update the CFG and
create new basic blocks etc etc etc. Isn't that true? If the inliner
were to run after SSA, then it would have to deal with cfg edges rather
than branches.. So Im not sure why it wouldn't impacts any of these.
They wont see any GOTO's and labels,. just CFG edges.

> > 
> > 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.

I dont think its the same thing at all. We dont have two forms of trees
any more than we do when we are inserting stmts on edges. See below.
> > 
> > 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.

No, Im not suggesting we "enter" block replication mode. There is no
translation in and out of unaffected regions.

What I am suggesting is that if you want to replicate a block, you call
a routine, "replicate_block(bb)" which performs your block replication,
creates your new BB, creates appropriate edges, and enters this new BB
into a list.

Then when you are ready to handle any new basic blocks that might be
required, you call "commit_block_replications()" which goes through the
list of new blocks that have been created, checks each one to see if it
has caused a successor with more than one predecessor which is a
fallthu, and if so, adds the required new BB, GOTOs and labels to make
the trees correct, all at once.

This is in principle what insert_on_edge does. It delays creating any
new basic blocks because of the critical edge splitting problem. It
doesnt affect any other part of the program, and neither would this.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]