Re: [patch] Lno branch merge part 3 -- ssa form updating improvements

[Zdenek Dvorak <rakdver at atrey dot karlin dot mff dot cuni dot cz>]

Hello,

> > you may use rewrite_ssa_into_ssa for this, as well as incremental
> > updating and often in an easier way.  So I don't really see what you
> > protest against (so far you have provided no reason except for your
> > personal dislike of the concept, sorry).
> > 
> The approach you took is too heavy handed.  It is duplicating fields
> from var_ann_d

I may store these values in local tables, if you prefer.

> replicating most of the SSA renamer,

Which any ssa updating algorithm must do.  I have tried to reuse as much
as possible, but the way tree-into-ssa.c written, it does not work very well.

> treating SSA_NAMEs as not really unique definitions

Do you have a saner way how to do it for general code copying (like in
the jump forwarding algorithm presented by Kenneth on the gcc summit,
or in the trace formation)? Or do you want to solve each such case
specially, so that we have even more code duplication in the compiler
and even more places where we need to fix bugs?

> and forcing another scan over the IL
> when all the optimization is doing are just local changes.

you must do the global pass to be able to rename all the uses anyway
(at least for now).  Once we have the immediate uses available,
this can be improved by passing the list of changed definitions to
rewrite_ssa_into_ssa.

> Let me go through what I think is the problem that you are trying to
> solve.  We have some loop:
> 
> 	|
> 	v
>    +->START
>    |	|
>    |	+--------> END
>    |	|
>    |	v
>    |  BODY
>    |	|
>    +----+
> 
> which we want to convert into
> 
> 	|
> 	v
>       START
>    	|
>    	+--------> END
>    	|           ^
>    	v           |
>    +->BODY          |
>    |	|           |
>    |	v           |
>    |  START' -------+
>    |    |
>    +----+
> 
> Is that correct?

yes.

> I'm assuming that we will have built a loop-closed form by inserting
> EXIT_COPY nodes at END (new tree nodes) before going into SSA.  I could
> give you a patch for this in LNO soonish.

I disagree with this patch for the reasons I have presented in the
previous mails.  I think you first have to argue that preserving
loop closed ssa form at all times is

1) feasible
2) useful

neither of which is obvious and neither of which I tend to believe
just because of the authority of Kenneth Zadeck (the fact that they
did that in their experimental compiler has very little relevancy to
whether it can and should be done in a real world compiler).

> For this particular problem, we could do the following algorithm:
> 
>      1. Replicate all the PHI nodes in START in the first block of
>         BODY.  Remove the SSA_NAMEs from all the operands and make new
>         SSA_NAMEs for the LHS of each node.
>      2. Delete the back edge BODY->START.  That will convert the PHI
>         nodes into assignments.
>      3. Create START' and attach it as shown above.
>      4. Copy statements from START in START'.  Create new SSA_NAMEs for
>         every assignment found.
>      5. Do a dominator walk of loop body beginning at START keeping
>         track of current definitions and repairing USE/V_USE operands
>         that don't match up.
> 
> We need to wrap step #2 in a generic API call, if we don't have it
> already.
> Step #5 could also be wrapped in a generic API.

Or we can do it the way I do, without need to worry about all these
technical details and equally efficiently (once we have immediate uses).

Zdenek