Re: [tree-ssa] Translation out of SSA

[law at redhat dot com]

In message <20030424232723 dot GA4937 at petteflet dot ntlworld dot com>, Jan Vroonhof writes:
 >Sorry to to but in, but if you could spare a few minutes to clear up a
 >few details for us lurkers trying to follow what is going on.
 >
 >>  - conflict graph based coalesing of partitions.
 >
 >Unless  I am very confused doesn't this mean this the comment in tree-ssa.c
 >
 >/* The following procedures implement the out of SSA algorithm detailed in 
 >   the Morgan Book pages 176-186.  */
 >
 >is not quite true (anymore)?
No, the comment is still correct.

 >The partition equivalence relation given
 >in the Morgan book seems much weaker (only coalescing partitions just
 >enough to avoid inserting copies on abnormal critical edges), whereas
 >the one you just implemented seems to be right on the other end of the
 >spectrum (i.e. coalesce unless we absolute cannot[1]).
See pages 312-316 in Morgan -- it discusses how to use a more aggressive
partitioning scheme.  It's unfortunate that he doesn't give you a
forward reference in the SSA chapter to the recommended way to 
partition.

While you can do an SSA->normal translation with the weaker partitioning,
you end up with a lot more copies than you really need.

You could leave this for a post-ssa pass to clean up, doing so is rather
wasteful (you generate a lot more nodes for later passes of the compiler
to process).    It's doubly wasteful in that the data structure you need
to do renaming & coalescing are the same as you need to do the SSA->Normal
translation.

 >  2. How the partitioning in your algorithm avoids inserting copies on
 >abnormal critical edges (at least to me it is non-obvious that the
 >algorithm guarantees the SSA temps of the same variable on both sides
 >of an abnormal edge end up in the same partition).
 >or am I just showing my lack of knowledge and this is all trivial?
I wouldn't be terribly surprised if this isn't handled yet.  It's
not particularly difficult to handle.


 >> Then we'll remove the abort() permanently, and start allowing overlapping 
 >> live ranges, but not before I debug them :-). I know there is a bug in edge
 >> insertion I have to get to, and a couple of other things.
 >
 >Are you talking about the following[2]
Unknown.  The most interesting thing I've run into in the insertion code
is it mucked things up because we had different blocks recorded for
the current statement and its container.  That caused all kinds of
problems.

 >The Briggs, e.a. "Practical Improvements ..." paper that is the basis
 >for the SSA rewriting phase actually claims that you can solve the
 >latter problem (possible cycles in the PHI nodes within one block)
 >without actually constructing the graph itself. At first glance at
 >least they seem to be solving the same problem.
Yes, the problems are very very closely related, if not identical.


 >[1]  The code even optimistically assumes it can map all the
 >partitions to their root variable and maps it to a different temporary
 >if it absolutely has to (quite different from the union-find proposed
 >by Morgan).
Nope, you just have to go elsewhere in Morgan to get his real partitioner :-)

Jeff