Tree-SSA self checking infrastructure

[Andrew MacLeod]

On Wed, 2003-11-19 at 13:46, law@redhat.com wrote:
> In message <1069266325.30707.833.camel@p4>, Andrew MacLeod writes:
>  >On Wed, 2003-11-19 at 13:04, law@redhat.com wrote:
>  >
>  >> 
>  >>  >3) SSA form testing
>  >>  >   We should have verify_ssa that ensures that stream is in valid SSA
>  >>  >   form.  I am not quite sure how to best implement this, but I guess I
>  >>  >   can simply verify that all the pointers points corectly and that each
>  >>  >   use is dominated by the def it points to.  Correct?
>  >> Right.  Each use needs to be dominated by its def and there should only be
>  >> a single def for each SSA_NAME.
>  >> 
>  >
>  >Isnt that already verified in SSA->normal?
> Yes.  Though it'd be nice to be able to check this independently of doing
> SSA->Normal.
> 
> In fact, if you had that capability and put the check immediately after PRE,
> you'd find it failing as PRE is creating uses which are not dominated by
> defs.
> 

I could try hacking together the few bits into one function and see if
it works... should be pretty simple.


>  >> Long term we _may_ want the ability to run the SSA to normal pass on a
>  >> specific set of variables.  That would allow us to do dominator based
>  >> jump threading anytime we want, take the injured variables out of SSA
>  >> form, then put them back into SSA form.
>  >
>  >That would actually be pretty trivial..
> Well, if it would be that trivial, then I'm definitely interested.  It
> would allow us to kill jump threading as a separate pass which has a 
> ton of nice properties -- especially with the changes I've been working
> on.
> 
>  > it already runs only on
>  >partitions created by create_ssa_var_map().. all you need to do is
>  >create a different partition set with just the variables you care
>  >about... dead simple :-)
> Cool.  Care to cobble together some code I can poke with?  It doesn't
> have to be perfect, but something to send me along the right path.
> 
> Conceptually assume that I know the uid of every variable I want to 
> take out of SSA form.  I could probably get all the related SSA_NAMEs
> with a little more work.  I'm guessing you're going to need the latter
> rather than the former.
> 
>  > Of course you might be interested in any new names that overlaping live
>  > ranges create...
> Yup.  That creates some minor difficulties, but I expect it to be 
> managable.

Well, its all pretty modular. Im not sure what the resulting speed with
be. It requires building the live-on-entry information for the SSA_NAMES
in question, then live on exit, then building a conflict graph,
coalescing them, running the SSA->Normal copy algorithm, inserting
required copies, then rewriting back to the original variable.

So thats not really much work, its just a matter of calling each
routine. I'll look at it.

What I would need to have for input would be a list of all the base
variables you want to un-ssa-ify. If you have a complete list of the
SSA_VERSIONs already, that would prevent a pass through the IL looking
for them. Before the algorithm can run, they have to be collected and
enumerated in a partition data structure (var_map).  Thats pretty
trivial to set up if you know what they are. 
tree-ssa-live.c::create_ssa_var_map() builds the var_map by traversing
the entire function once looking for uses and defs and registering them
via a call to tree-ssa-live.c::register_ssa_partition(). Everything is
then driven from that partition list. You'd want to create one with the
SSA_NAMEs you care about rewriting back. 

After that, its just a matter of calling the appropriate routines, and
tweaking the rewrite-IL step a hair.  I'll write an entry point which
takes in a var_map and rewites back to the original variables.

Andrew