[tree-ssa] RFC: Making control flow more explicit

[Andrew MacLeod]

On Sat, 2003-08-09 at 13:43, Zdenek Dvorak wrote:
> Hello,
> 
> I have spent a few hours thinking about the issue and I now think there
> might be a way to split the patch into smaller ones (perhaps also not
> seeing the code for a day helped :-). The proposed splitting (numbers
> in brackets mean my estimate on size of the change):
> 
> 1) elimination of LOOP_EXPRs [500] -- a few lines in gimplification, removal
>    of references to them in tree-*, plus loop note regeneration just
>    before loop header copying

I had originally though LOOP_EXPRs would be useful, but ultimately, no
one could explain how :-).  So I see no problem with eliminating them,
and I had planned to do so myself (it was on my short todo list) because
the way we currently expand LOOP_EXPRs causes us to never get counted
loops recognized by the RTL optimizations, and we get hit in various
benchmarks because we never have decrement/branch type instructions
generated by the backend. I'd certainly like to see our loops generated
differently.

> 2) lowering of SWITCH_EXPRs and COND_EXPRs (so that their branches are
>    just gotos) [500-1000] -- a change to gimplification, cleanup + a few changes in
>    optimizers.

Im sure others have better comments on the SWITCH, but this seems like a
decent solution for lowering COND_EXPR's...

> 3) replacing COMPOUND_EXPRs with double-linked chain of statements [500-1000] --
>    mostly changes to block iterators + places in code that rely on the
>    fact that the whole function tree is kept, and final pass that
>    regenerates COMPOUND_EXPRs

This one Im not so sure about. We've always had the desire to replace
COMPOUND_EXPR nodes right at the tree level with iterators which allow
us to represent it differently. The last/best scheme was rth's which is
commented on somewhere back 8 or 10 months. We want to keep iterators
which deal with an abstract container (in fact, I been looking for the
time to go change the typedefs of containers to tsi_container_p and
bsi_container_p  from 'tree *' to facilitate this further).  This is a
much more complicated discussion however. 

That said, a double linked list was, and still is, the desired end
result.  We've toyed with the idea of going to a linked list which in
SSA mode, (Diego has done it within blocks at least once I think).  As
long as CE nodes still exist, it was dual maintenace. 

If I understand what you are doing, you are ripping out all the CE
nodes, and using the CFG to control the linking between blocks? That was
briefly examined back in december, but at the time we were already doing
some big changes (non-rewriting form to rewriting form, among others
:-), and that was just too much more at the time.

The only problem I remember discussing at the time was potential rtl
generation/ordering issues from the CFG form. I dont remember anything
concrete, just concerns. We didnt consider moving back to CE nodes at
the time.  It might be that translating to linked lists when we build
the CFG, and then converting back to GIMPLE/CE nodes before rtl
expansion would be quick enough that you would pick up all the required
time by easier trasversal and satmt manipulation. Its worth examining
anyway I think. Would you do this just before creating the CFG, or
sometime after?  I dont know if we have many callbacks into the CFG
builder so I dont know if this is significant or not.

One problem I would see with that is that we can't hook back into the
gimplifier. Do we ever do that anywhere now once we go to SSA or build
the CFG?  It also mean you better be able to keep the CFG up to date and
accuarate 100% of the time :-)  I would like to continue to see total
use of the block iterators (which would be rewritten, but much simpler
of course). We shouldn't have to change the API of the iterators at all.
So it would only be identifiying those optimizzations which broke the
iterator rules, or which where looking for CE nodes out of misguided
necessity.

Since there are a lot of ways of doing this, I'd like to see more
discussion about the specifics of what we really want to do here.


> 4) moving BIND_EXPRs and exception handling constructs to their own tree [2000]
>    probably the most complicated step; some changes to iterators, many
>    to cleanup, final pass to move structures back.  This is basically
>    equivalent to the core of my current patch, I will try to think more
>    on how to make this step less painful.

Can you elaborate on this more?  I dont understand what/how you are
trying to do here, other than eliminate BIND_EXPR's.


> In reality I will of course not completely follow this list (especially
> because some of the points partially overlap), but this should be the
> rough idea.

These four things ought not overlap tho?  Each ought to be independantly
implemented I think.
> 
> Is this acceptable? It will of course be a great lot of patches, so I
> won't go into it unless I know that someone is ready to take the burden
> of reviewing them.


Im sure most people *much* prefer looking at many small patches than one
big one...  And if any of these steps can be broken into smaller peices,
even better.

Andrew