Re: Tree-SSA self checking infrastructure

[Jan Hubicka <hubicka@ucw.cz>]

> In message <20031119174450.GI11681@kam.mff.cuni.cz>, Jan Hubicka writes:
>  >1) Gimple testing
>  >   a) verifying that each stmt is gimple is trivial, will hook it into
>  >   verify_flow_info, or shal I invent verify_stmt/verify_stmts?
> Please do not hook this into verify_flow_info.  Testing that the statements
> are gimple has absolutely nothing to do with verification that the CFG
> is correct.

I am having verify_stmts and I am working on it right now.
> 
> In fact, one could argue that some of the stuff in verify_flow_info really
> belongs elsewhere.  Consider this situation (which I'm already bumping into).
> 
>   I want to thread a jump to a block with a PHI node.  So I update the CFG
>   and the block with the PHI node now has an additional edge.
> 
>   Then I want to cleanup the CFG.
> 
>   Then I want to rebuild the dominator tree.
> 
>   Then I want to re-rename those objects which were affected by the
>   CFG changes.

I think we can move PHI checks to verify_ssa.  Does this look plausible?
> 
> The problem is cleaning the cfg calls into the verification routines which
> want to verify the state of the PHI nodes.  Well, in this case the PHI nodes
> are in a state of flux.   I could add an argument to the PHI node, but
> that seems awful wasteful since I'm going to be throwing away the PHI node
> as part of the re-renaming process.  Deleting the PHI node isn't an option
> since the tree cfg cleanup code needs to know about their existence to
> avoid certain unsafe transformations.
> 
> We need separate routines for verifying the CFG, verifying the SSA graph
> (and its associated PHI nodes), verifying that we're in gimple form, etc.

Currently I invented verify_flow_info/verify_stmts/verify_ssa split.
That should be fine for the moment.  We can do more finely grained
splits, but that all costs some extra CPU time, so I would do that on
demand.
> 
> Those should not all be hooked together.
> 
> 
>  >   b) verifying gimple types is almost impossible now.  The reason is
>  >   ssa_useless_type_conversion.  Where we got about the plans to make it
>  >   transitive and symteric?
> I can't be transitive and symmetric.  Fundamentally it can't be that way.
> (think about casting of function pointers).

Is there any way to check that given random gimple expr resulting from
sequence of substitutions is still having matching types in this relaxed
way?
It don't have to be completely strict, but at least some relaxed
checking would be very cool so we don't do stupid mistakes, like in the
builtin simplifiers.
> 
>  >   c) I commonly got hit by the feature of gimple allowing almost
>  >   arbitrarily complex constant operands.  What about restricting it
>  >   into primitive constants +
>  >   (plus_expr (nop_expr (addr_exr )) (integer_cst) as the most complex
>  >   form?
> This has been a subject of great debate.  I don't think we have a solid
> answer on where a NOP_EXPR might appear.

It seems to always appear inside the PLUS expr.  It seems like natural
choice.
Without that we should have to make recursive walk each time we are
looking for ADDR_EXPR.
> 
> 
>  >   d) We should verify gimple sharing restrictions.  But what are these?
>  >   We share constant nodes now.  I think we share constant
>  >   expressions as well.  What else can be shared?
> That would be a good.
> 
>  >   e) We should maintain invariant that no statements fold further after
>  >   each optimization pass.  THis is currently not the case as gimplifier
>  >   can produce unfolded statements.  Doing fold_stmt as part of
>  >   remove_useless_* uncovers latent bugs in fold_stmt.  Any plans on
>  >   fixing the folders and any progress on this?
> That would be a nice goal, but I don't think it should necessarily be a
> strict invariant.  

If it is not strict invariant, we will be breaking it unknowingly.
I think it makes sense to define interfaces in a way that they can be
machine verified even when it costs little inconvenciences (like
discovering new and new places where we produce simplifiable statement
in the side cases).
It still is much better to fold after changes, than doing folding "just
for sure", like we do right now.
> 
>  >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.

Good :)
> 
> 
>  >   This also brings me into question how the rewrite_into_ssa updates
>  >   the SSA form.  What happens when the variable has been already
>  >   optimized so live ranges of it's SSA_NAMES overlap and I ask for
>  >   variable SSA form to be recomputed?
> You lose.  You lose badly.  Don't do that :-)
> 
> Having a verification step that you don't rename an already renamed 
> variable after a certain point (after the dominator based jump threading)
> would be good.
Many passes seems to rewrite variables efter dominater pass.  What to
do?
> 
> 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.
UHmm.

Thanks!
Honza
> 
> Jeff