Tree-SSA self checking infrastructure

Tree-SSA self checking infrastructure

[Jan Hubicka]

Hi,
I was thinking about the current somwhat frustrating situation
concerning dependency of tree-SSA branch on the environment it is tested
in.  Obivously the amount of existing bugs is high enought so while
testing patch on one machine I fix only those bugs affecting it hitting
other bugs later as unpleasant surprise.

One thing that never hurts is extra sanity checking in the compiler.
On RTL, implementing any self checking feature is dificult given how
complex the code base is and how many times it breaks the interfaces.
For tree-SSA this should be easier, so I would like to do some work on
it.  Here I would like to ask for ideas what shall be implemented.  So
far I can come up with:

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?
   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?
   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?
   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?
   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?
2) CFG testing
   I believe that verify_flow_info is now mostly feature complette, but
   in the case you notice some missed tests, please let me know
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?

   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?
4) Aliasing
   I think I can check that TREE_ADDRESSABLE is set for each argument of
   ADDR_EXPR.  This is somewhat stupid, but seems to break in current
   tree in many interesting ways.  More ideas?

I will try to work on this plan now and delay my other projects of
improving testsuite, so any ideas are welcome soon :)

Re: Tree-SSA self checking infrastructure

[law]

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.

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.

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.

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).

 >   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.


 >   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.  

 >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.


 >   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.

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.

Jeff

Re: Tree-SSA self checking infrastructure

[Andrew MacLeod]

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?

> 
>  >   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.
> 
> 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.. 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 :-)  Of course you might be interested in any new
names that overlaping live ranges create...

Andrew

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> 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

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> 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?
It would be easier to have this in simple function so one can call it in
the middle of queue.
> 
> > 
> >  >   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.
> > 
> > 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.. 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 :-)  Of course you might be interested in any new
> names that overlaping live ranges create...

Would be possible for you to look into it?
I think the current sollution has good potential to bring hidden
problems.

Honza
> 
> Andrew

Re: Tree-SSA self checking infrastructure

[law]

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.

 >> 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.


Jeff

Re: Tree-SSA self checking infrastructure

[Andrew MacLeod]

On Wed, 2003-11-19 at 13:38, Jan Hubicka wrote:
> > 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?
> It would be easier to have this in simple function so one can call it in
> the middle of queue.

I beleive we put it there because the information naturally flowed out
of the work SSA->normal was doing when trying to coalesce ssa versions
together. An SSA version which the live range analysis determines is
live on entry to the program which also has a DEF in the program
somewhere is determined to be in error, and we abort. 

You could call it from anywhere, but its in the live-on-entry
calculator, so you'd be doing some additional work. You could call
create_ssa_var_map() to create the partition set, followed by
live_on_entry() then throw away the results...

Wouldnt be too difficult... just a waste of some compile time.

Andrew

Re: Tree-SSA self checking infrastructure

[Richard Henderson]

On Wed, Nov 19, 2003 at 06:44:50PM +0100, Jan Hubicka wrote:
>    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'm working on some of this this afternoon, verifying that the types
match across ADDR_EXPR, INDIRECT_REF, ARRAY_REF only.  My interest 
here comes out of wanting to fix ...

>    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.  After my fold_stmt changes as of this morning, the only
way (that I know of so far) of producing *(&var + 8) is for there to
be a front-end bug wrt types.  Try to produce one of these from the
C level and you'll get a cast which will prevent propagating the
address into the dereference.

I've found more than a dozen such bugs so far.

At present, NOP_EXPRs are *not* valid gimple operands.  Believe it
or not, but allowing that is even more complex than the PLUS_EXPR
that we currently allow.

>    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?

Try again.


r~

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> On Wed, Nov 19, 2003 at 06:44:50PM +0100, Jan Hubicka wrote:
> >    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'm working on some of this this afternoon, verifying that the types
> match across ADDR_EXPR, INDIRECT_REF, ARRAY_REF only.  My interest 
> here comes out of wanting to fix ...

OK, so I am skipping this bit and wairing for your job :)
I am almost done with verify_stmts except for tree sharing, as I am
still not clear about the tree sharing rules.  (Did I mentioned it in
original email?)

> 
> >    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.  After my fold_stmt changes as of this morning, the only
> way (that I know of so far) of producing *(&var + 8) is for there to
> be a front-end bug wrt types.  Try to produce one of these from the
> C level and you'll get a cast which will prevent propagating the
> address into the dereference.
OKm I will update the tree.  I am not sure I understand your correctly.
How complex may the symbolic references look like now?
> 
> I've found more than a dozen such bugs so far.
> 
> At present, NOP_EXPRs are *not* valid gimple operands.  Believe it
> or not, but allowing that is even more complex than the PLUS_EXPR
> that we currently allow.
> 
> >    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?
> 
> Try again.
Will do.

Honza
> 
> 
> r~

Re: Tree-SSA self checking infrastructure

[law]

In message <20031119182545.GN16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
s:
 >I think we can move PHI checks to verify_ssa.  Does this look plausible?
That would be perfect as long as we don't call verify_ssa directly from
verify_cfg or cleanup_cfg.

 >>  >   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?
I haven't thought a lot about it.    I've got a TODO based on one of
your earlier messages to look at some stuff, but haven't gotten around
to it.

For non-pointer integral types the rules are trivial (and in fact they are
symmetric and transitive -- it's only pointers that can't be made
transitive and symmetric).

The nop conversion is consider useless if

  same types

  or

  same type main variant

  or

  same modes && same signedness && same precision


The problem you're trying to solve isn't necessarily solvable because
you don't know what the expression's original type was.  ie, given an
expr, you know its current type, but you don't know the original type
of the expression.




 >>  >   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.
The problem is once you allow it in a PLUS (or anywhere else other than the
RHS of a MODIFY_EXPR) that you've changed the gimple grammar and you have
to account for that change in the gimple grammar.  ie, you can no longer
make assumptions that the first argument of a PLUS is a gimple variable.
It might now be a NOP.

That's the fundamental issue -- it changes the grammar.

But as I've harped on, type conversions are killing us in terms of optimization
so we keep looking at ways to either eliminate the NOPs or find ways to
allow them in certain expressions.

We don't have a serious long term strategy for dealing with nops.


 >> 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?
They rewrite newly exposed variables.  ie, they're rewriting VAR_DECLs,
PARM_DECLs, that were addressable, but due to optimizations they are no
longer addressable and thus can be put into SSA form and optimized.

The exception is the dominator based jump threader where we do rerewrite
existing SSA_NAMEs.  In that case we know there are no overlaps as we have
done no optimizations which could have created an overlap.

Jeff

Re: 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

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

Hi,
I will give deeper tought to the pointer types.  About the other
topics...
>  >>  >   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.
> The problem is once you allow it in a PLUS (or anywhere else other than the
> RHS of a MODIFY_EXPR) that you've changed the gimple grammar and you have
> to account for that change in the gimple grammar.  ie, you can no longer
> make assumptions that the first argument of a PLUS is a gimple variable.
> It might now be a NOP.
> 
> That's the fundamental issue -- it changes the grammar.

I don't mean allowing some extra.  I am seeing these NOP_EXPRs inside
ADDR_EXPRs all the time so I assumed they are valid.
OK, now I see it is bug, so I will try to fix it (unless Richard already
did so).
>  >> 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?
> They rewrite newly exposed variables.  ie, they're rewriting VAR_DECLs,
> PARM_DECLs, that were addressable, but due to optimizations they are no
> longer addressable and thus can be put into SSA form and optimized.

This brings me into questions about my tail call updating code.
Perhaps I need to re-do SSA form on call cobbered variables after
removing the call?
> 
> The exception is the dominator based jump threader where we do rerewrite
> existing SSA_NAMEs.  In that case we know there are no overlaps as we have
> done no optimizations which could have created an overlap.

I see.  It would be nice to drop a comment somewhere in tree-optimize.c
clarifying what can be renamed when.

Honza
> 
> Jeff
> 

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> For non-pointer integral types the rules are trivial (and in fact they are
> symmetric and transitive -- it's only pointers that can't be made
> transitive and symmetric).
> 
> The nop conversion is consider useless if
> 
>   same types
> 
>   or
> 
>   same type main variant
> 
>   or
> 
>   same modes && same signedness && same precision
> 
> 
> The problem you're trying to solve isn't necessarily solvable because
> you don't know what the expression's original type was.  ie, given an
> expr, you know its current type, but you don't know the original type
> of the expression.

I am still in dark here.  Can you give me some example of pointer types
where we don't want transitivity? What abut symmetricity?

Honza

Re: Tree-SSA self checking infrastructure

[law]

In message <1069267901.30709.844.camel@p4>, Andrew MacLeod writes:
 >I beleive we put it there because the information naturally flowed out
 >of the work SSA->normal was doing when trying to coalesce ssa versions
 >together. An SSA version which the live range analysis determines is
 >live on entry to the program which also has a DEF in the program
 >somewhere is determined to be in error, and we abort. 
 >
 >You could call it from anywhere, but its in the live-on-entry
 >calculator, so you'd be doing some additional work. You could call
 >create_ssa_var_map() to create the partition set, followed by
 >live_on_entry() then throw away the results...
 >
 >Wouldnt be too difficult... just a waste of some compile time.
Yup.  That's why it'd have to be under an ENABLE_CHECKING directive of
some kind.

Note that we don't necessarily have to do the live-at-entry check.  Can't
we do something like

FOR_EACH_BB
  FOR_EACH_STMT
    FOR_EACH_OPERAND
      def_bb = bb_for_stmt (SSA_NAME_DEF_STMT (operand))
      if (! def_bb dominates bb)
        abort

With a special check for the default definition?

jeff




 >
 >Andrew
 >

Re: Tree-SSA self checking infrastructure

[law]

In message <20031119190649.GQ16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
s:
 >This brings me into questions about my tail call updating code.
 >Perhaps I need to re-do SSA form on call cobbered variables after
 >removing the call?
Are you changing the CFG?  Are you changing the dominator tree?  Those
are the key questions.

 >> The exception is the dominator based jump threader where we do rerewrite
 >> existing SSA_NAMEs.  In that case we know there are no overlaps as we have
 >> done no optimizations which could have created an overlap.
 >
 >I see.  It would be nice to drop a comment somewhere in tree-optimize.c
 >clarifying what can be renamed when.
Err, I thought there was a comment regarding this issue in the code.  
Regardless, from discussions with Andrew we may have the ability to
un-ssa specific variables, which would make this a non-issue.
jeff

Re: Tree-SSA self checking infrastructure

[law]

In message <20031119190939.GR16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
s:
 >I am still in dark here.  Can you give me some example of pointer types
 >where we don't want transitivity? What abut symmetricity?
If the inner type is a pointer and the outer type is a void *, then we
have a useless conversion.

  First realize this loses no information.  It strictly increases the
  amount of information available.

  Second realize that if the outer type was a void *, then the resulting
  pointer can only be used in very specific ways (such as parameter
  passing).  You can't do arithmetic or dereference a void * pointer.
  So the additional information you get by dropping the useless conversion
  to void * doesn't hurt either.


The opposite is not true.

Consider the case where the outer type is a function pointer and the
inner type is a void *. 

  First realize that eliminating the cast loses information.  ie, we 
  originally had a function pointer, now we have a wonderful generic
  void *.

  Second realize that the result of the original expression could be
  dereferenced.  ie, if it was a function pointer, then you can dereference
  the pointer which ultimately calls a function.  If you eliminate the
  typecast, then you're trying to dereference a void *.  Not a good idea.

  Third realize that some ABI's require in-depth knowledge about the
  called function's signature.  In fact, ia32 is an example.  The way
  parameters are passed, values returned and possibly even caller-pops
  may be dependent on the signature of the called function.  If you've
  eliminated the typecast, then you don't have access to the function's
  signature.  All hell breaks loose after that.



jeff

Re: Tree-SSA self checking infrastructure

[law]

In message <1069268637.30703.858.camel@p4>, Andrew MacLeod writes:
 >> 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.
If you need a testcase, look for a message from me in the archives
"More PRE problems".  PRE will create a use which is not dominated by the 
def for the included testcase.

 >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.
Well, there's one way to find out :-)  It can't be that much worse
than the contortions I'm going through to build a good jump threader.


 >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.
Ah, yes, I've got the base variables handy in sbitmap form :-)  I'll 
translate into whatever form you might want :-)

It probably wouldn't be that terrible to get the SSA_NAMEs.  That data
is pretty handy at the time when I realize that I'm going to need to
re-rewrite something.

 >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.
Sweet.  If you can set up that entry point and throw the code my way, I'll
take it from there and see what's missing/broken ;-)
jeff

Re: Tree-SSA self checking infrastructure

[Andrew MacLeod]

On Wed, 2003-11-19 at 14:13, law@redhat.com wrote:
> In message <20031119190649.GQ16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
> s:
>  >This brings me into questions about my tail call updating code.
>  >Perhaps I need to re-do SSA form on call cobbered variables after
>  >removing the call?
> Are you changing the CFG?  Are you changing the dominator tree?  Those
> are the key questions.
> 
>  >> The exception is the dominator based jump threader where we do rerewrite
>  >> existing SSA_NAMEs.  In that case we know there are no overlaps as we have
>  >> done no optimizations which could have created an overlap.
>  >
>  >I see.  It would be nice to drop a comment somewhere in tree-optimize.c
>  >clarifying what can be renamed when.
> Err, I thought there was a comment regarding this issue in the code.  
> Regardless, from discussions with Andrew we may have the ability to
> un-ssa specific variables, which would make this a non-issue.

If you want to hack around with it, the following *ought* to get you
what you are looking for.  If you can create the var_map like
create_ssa_var_map does to include only the things you are interested
in. (and it ought to include *all* versions of a variable or the live
range stuff wont be right when its coalesced back to the root variable).

The only thing I had to break out was the bits that physically rewrote
the trees.

Your entry point is the function "remove_ssa_form (var_map)"

I'll work through any problems you run into, but thats the basic gist of
what needs to be done.

I haven't run tests or anything on this to make sure I didnt break
anything, but they are running now. I would expect no problems with
existing code, and I would think that if you create a var_map the new
entry point ought to workl just fine. There isnt much new there, so it
should work fine.


Andrew


Index: tree-ssa-live.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-live.h,v
retrieving revision 1.1.2.10
diff -c -p -r1.1.2.10 tree-ssa-live.h
*** tree-ssa-live.h	14 Nov 2003 16:50:02 -0000	1.1.2.10
--- tree-ssa-live.h	19 Nov 2003 19:34:59 -0000
*************** extern void dump_var_map (FILE *, var_ma
*** 62,67 ****
--- 62,68 ----
  extern int var_union (var_map, tree, tree);
  extern void change_partition_var (var_map, tree, int);
  extern void compact_var_map (var_map, int);
+ extern void remove_ssa_form (var_map);
  
  static inline int num_var_partitions (var_map);
  static inline tree var_to_partition_to_var (var_map, tree);
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.153
diff -c -p -r1.1.4.153 tree-ssa.c
*** tree-ssa.c	16 Nov 2003 11:00:40 -0000	1.1.4.153
--- tree-ssa.c	19 Nov 2003 19:35:00 -0000
*************** dump_replaceable_exprs (FILE *f, tree *e
*** 2313,2396 ****
  }
  
  
! /* Take function FNDECL out of SSA form.
! 
!    PHASE indicates which dump file from the DUMP_FILES array to use when
!    dumping debugging information.  */
! 
! void
! rewrite_out_of_ssa (tree fndecl, enum tree_dump_index phase)
  {
    basic_block bb;
    block_stmt_iterator si;
    edge e;
!   var_map map;
!   tree phi, next;
!   elim_graph g;
!   tree_live_info_p liveinfo;
!   tree *values = NULL;
!   int var_flags = 0;
! 
!   timevar_push (TV_TREE_SSA_TO_NORMAL);
! 
!   dump_file = dump_begin (phase, &dump_flags);
! 
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
! 
!   if (flag_tree_ter)
!     var_flags = SSA_VAR_MAP_REF_COUNT;
!   map = create_ssa_var_map (var_flags);
!   eliminate_extraneous_phis (map);
! 
!   /* Shrink the map to include only referenced variables.  */
!   if (flag_tree_combine_temps)
!     compact_var_map (map, VARMAP_NORMAL);
!   else
!     compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
! 
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     dump_var_map (dump_file, map);
! 
!   liveinfo = coalesce_ssa_name (map);
! 
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     {
!       fprintf (dump_file, "After Coalescing:\n");
!       dump_var_map (dump_file, map);
!     }
!   if (!flag_tree_combine_temps)
!     compact_var_map (map, VARMAP_NORMAL);
! 
!   /* This is the final var list, so assign real variables to the different
!      partitions.  */
!   assign_vars (map);
! 
!   if (dump_file && (dump_flags & TDF_DETAILS))
!     {
!       fprintf (dump_file, "After Root variable replacement:\n");
!       dump_var_map (dump_file, map);
!     }
! 
!   if (flag_tree_ter)
!     {
!       values = find_replaceable_exprs (map);
!       if (values && dump_file && (dump_flags & TDF_DETAILS))
! 	dump_replaceable_exprs (dump_file, values);
!     }
! 
!   if (flag_tree_combine_temps && liveinfo)
!     {
!       coalesce_vars (map, liveinfo);
!       if (dump_file && (dump_flags & TDF_DETAILS))
! 	{
! 	  fprintf (dump_file, "After variable memory coalescing:\n");
! 	  dump_var_map (dump_file, map);
! 	}
!     }
! 
!   if (liveinfo)
!     delete_tree_live_info (liveinfo);
  
    /* Replace PHI nodes with any required copies.  */
    g = new_elim_graph (map->num_partitions);
--- 2313,2326 ----
  }
  
  
! static void
! rewrite_trees (var_map map, tree *values)
  {
+   elim_graph g;
    basic_block bb;
    block_stmt_iterator si;
    edge e;
!   tree phi;
  
    /* Replace PHI nodes with any required copies.  */
    g = new_elim_graph (map->num_partitions);
*************** rewrite_out_of_ssa (tree fndecl, enum tr
*** 2460,2480 ****
          {
  	  for (e = bb->pred; e; e = e->pred_next)
  	    eliminate_phi (e, phi_arg_from_edge (phi, e), g);
- 	  for ( ; phi; phi = next)
- 	    {
- 	      next = TREE_CHAIN (phi);
- 	      remove_phi_node (phi, NULL_TREE, bb);
- 	    }
  	}
      }
  
    delete_elim_graph (g);
  
!   if (values)
!     free (values);
  
    /* If any copies were inserted on edges, actually insert them now.  */
    bsi_commit_edge_inserts (0, NULL);
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
--- 2390,2524 ----
          {
  	  for (e = bb->pred; e; e = e->pred_next)
  	    eliminate_phi (e, phi_arg_from_edge (phi, e), g);
  	}
      }
  
    delete_elim_graph (g);
+ }
+ 
+ /* Remove the variables specified in a var map from SSA form.  */
+ void
+ remove_ssa_form (var_map map)
+ {
+   tree_live_info_p liveinfo;
+   basic_block bb;
+   tree phi, next;
+   FILE *save;
+ 
+   save = dump_file;
+   dump_file = NULL;
+ 
+   compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
+   liveinfo = coalesce_ssa_name (map);
+   compact_var_map (map, VARMAP_NORMAL);
+   assign_vars (map);
+   if (liveinfo)
+     delete_tree_live_info (liveinfo);
+   rewrite_trees (map, NULL);
  
!   /* Remove phi nodes which have been translated back to real variables.  */
!   FOR_EACH_BB (bb)
!     {
!       for (phi = phi_nodes (bb); phi; phi = next)
! 	{
! 	  next = TREE_CHAIN (phi);
! 	  if (var_to_partition (map, PHI_RESULT (phi)) != NO_PARTITION)
! 	    remove_phi_node (phi, NULL_TREE, bb);
! 	}
!     }
  
    /* If any copies were inserted on edges, actually insert them now.  */
    bsi_commit_edge_inserts (0, NULL);
+ 
+   dump_file = save;
+ }
+ 
+ /* Take function FNDECL out of SSA form.
+ 
+    PHASE indicates which dump file from the DUMP_FILES array to use when
+    dumping debugging information.  */
+ 
+ void
+ rewrite_out_of_ssa (tree fndecl, enum tree_dump_index phase)
+ {
+   basic_block bb;
+   var_map map;
+   tree phi, next;
+   tree_live_info_p liveinfo;
+   tree *values = NULL;
+   int var_flags = 0;
+ 
+   timevar_push (TV_TREE_SSA_TO_NORMAL);
+ 
+   dump_file = dump_begin (phase, &dump_flags);
+ 
+   if (dump_file && (dump_flags & TDF_DETAILS))
+     dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
+ 
+   if (flag_tree_ter)
+     var_flags = SSA_VAR_MAP_REF_COUNT;
+   map = create_ssa_var_map (var_flags);
+   eliminate_extraneous_phis (map);
+ 
+   /* Shrink the map to include only referenced variables.  */
+   if (flag_tree_combine_temps)
+     compact_var_map (map, VARMAP_NORMAL);
+   else
+     compact_var_map (map, VARMAP_NO_SINGLE_DEFS);
+ 
+   if (dump_file && (dump_flags & TDF_DETAILS))
+     dump_var_map (dump_file, map);
+ 
+   liveinfo = coalesce_ssa_name (map);
+ 
+   if (dump_file && (dump_flags & TDF_DETAILS))
+     {
+       fprintf (dump_file, "After Coalescing:\n");
+       dump_var_map (dump_file, map);
+     }
+   if (!flag_tree_combine_temps)
+     compact_var_map (map, VARMAP_NORMAL);
+ 
+   /* This is the final var list, so assign real variables to the different
+      partitions.  */
+   assign_vars (map);
+ 
+   if (dump_file && (dump_flags & TDF_DETAILS))
+     {
+       fprintf (dump_file, "After Root variable replacement:\n");
+       dump_var_map (dump_file, map);
+     }
+ 
+   if (flag_tree_ter)
+     {
+       values = find_replaceable_exprs (map);
+       if (values && dump_file && (dump_flags & TDF_DETAILS))
+ 	dump_replaceable_exprs (dump_file, values);
+     }
+ 
+   if (flag_tree_combine_temps && liveinfo)
+     {
+       coalesce_vars (map, liveinfo);
+       if (dump_file && (dump_flags & TDF_DETAILS))
+ 	{
+ 	  fprintf (dump_file, "After variable memory coalescing:\n");
+ 	  dump_var_map (dump_file, map);
+ 	}
+     }
+ 
+   if (liveinfo)
+     delete_tree_live_info (liveinfo);
+ 
+   rewrite_trees (map, values);
+ 
+   FOR_EACH_BB (bb)
+     {
+       for (phi = phi_nodes (bb); phi; phi = next)
+ 	{
+ 	  next = TREE_CHAIN (phi);
+ 	  remove_phi_node (phi, NULL_TREE, bb);
+ 	}
+     }
  
    if (dump_file && (dump_flags & TDF_DETAILS))
      dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);

Re: Tree-SSA self checking infrastructure

[Andrew MacLeod]

On Wed, 2003-11-19 at 14:39, Andrew MacLeod wrote:
> On Wed, 2003-11-19 at 14:13, law@redhat.com wrote:
> > In message <20031119190649.GQ16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write

> Your entry point is the function "remove_ssa_form (var_map)"
> 
> I'll work through any problems you run into, but thats the basic gist of
> what needs to be done.
> 

There will probably be a few little things I'll need to take care of on
toip of this. I suspect we need to reset the out_of_ssa_tag flag on any
rewritten partitions, and you will probably want to know if any
variables were created. that information is within the var_map, but not
directly avialable via a function call. 

Those sorts of details will probably come up :-)  I'll get
accessors/correctors  for that information in a bit.

Andrew

Re: Tree-SSA self checking infrastructure

[Andrew MacLeod]

On Wed, 2003-11-19 at 14:39, Andrew MacLeod wrote:
> On Wed, 2003-11-19 at 14:13, law@redhat.com wrote:
> > In message <20031119190649.GQ16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write

> 
> I haven't run tests or anything on this to make sure I didnt break
> anything, but they are running now. I would expect no problems with
> existing code, and I would think that if you create a var_map the new
> entry point ought to workl just fine. There isnt much new there, so it
> should work fine.
> 
So I need to tweak it a bit, I have a few failing testcases :-| Musta
missed something going through so quickly...

Andrew

Re: Tree-SSA self checking infrastructure

[Andrew MacLeod]

On Wed, 2003-11-19 at 15:23, Andrew MacLeod wrote:
> On Wed, 2003-11-19 at 14:39, Andrew MacLeod wrote:
> > On Wed, 2003-11-19 at 14:13, law@redhat.com wrote:
> > > In message <20031119190649.GQ16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
> 
> > 
> > I haven't run tests or anything on this to make sure I didnt break
> > anything, but they are running now. I would expect no problems with
> > existing code, and I would think that if you create a var_map the new
> > entry point ought to workl just fine. There isnt much new there, so it
> > should work fine.
> > 
> So I need to tweak it a bit, I have a few failing testcases :-| Musta
> missed something going through so quickly...
> 
Ah, I think its because the ssa->normal alogorithm is expecting all the
unrelated PHIs to have been removed already by tye call to
eliminate_extraneous_phis().

when I wrote TER, I had code to switch this so that it checked a PHI
node first to see if its one it cared about, but ended up not needing
it, guess I should add it back in now since we definately need it now.

So dont try using this until tomorrow. I'll have a good patch for you
then.

Anything else you need?  The entry point should remain/look the same,
and I'll provide a hook into var_map that you can as what variable a
specific SSA_VERSION number was mapped to. That'll help you find any new
variables that were created.

Andrew

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> In message <20031119190649.GQ16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
> s:
>  >This brings me into questions about my tail call updating code.
>  >Perhaps I need to re-do SSA form on call cobbered variables after
>  >removing the call?
> Are you changing the CFG?  Are you changing the dominator tree?  Those
I replace tail call by edge back to the beggining of function and I
possibly split edge fron entry point.  I also take care to construct PHI
nodes for all referenced arguments by hand.
This does change CFG, but does not change dominance relationships.
I am however removing call and perhaps we are maintaining something that
relies on the presence of call...

Honza
> are the key questions.
> 
>  >> The exception is the dominator based jump threader where we do rerewrite
>  >> existing SSA_NAMEs.  In that case we know there are no overlaps as we have
>  >> done no optimizations which could have created an overlap.
>  >
>  >I see.  It would be nice to drop a comment somewhere in tree-optimize.c
>  >clarifying what can be renamed when.
> Err, I thought there was a comment regarding this issue in the code.  
> Regardless, from discussions with Andrew we may have the ability to
> un-ssa specific variables, which would make this a non-issue.
> jeff

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> In message <20031119190939.GR16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
> s:
>  >I am still in dark here.  Can you give me some example of pointer types
>  >where we don't want transitivity? What abut symmetricity?
> If the inner type is a pointer and the outer type is a void *, then we
> have a useless conversion.
> 
>   First realize this loses no information.  It strictly increases the
>   amount of information available.
> 
>   Second realize that if the outer type was a void *, then the resulting
>   pointer can only be used in very specific ways (such as parameter
>   passing).  You can't do arithmetic or dereference a void * pointer.
>   So the additional information you get by dropping the useless conversion
>   to void * doesn't hurt either.
> 
> 
> The opposite is not true.
> 
> Consider the case where the outer type is a function pointer and the
> inner type is a void *. 

I see, thanks.  Still this breaks the symmetricity only.
With transitivity, we still shall be able to verify that we have useless
conversion from PLUS_EXPR into it's operands, for instance.
Even that appears to be broken at the moment. Why?

Honza
> 
>   First realize that eliminating the cast loses information.  ie, we 
>   originally had a function pointer, now we have a wonderful generic
>   void *.
> 
>   Second realize that the result of the original expression could be
>   dereferenced.  ie, if it was a function pointer, then you can dereference
>   the pointer which ultimately calls a function.  If you eliminate the
>   typecast, then you're trying to dereference a void *.  Not a good idea.
> 
>   Third realize that some ABI's require in-depth knowledge about the
>   called function's signature.  In fact, ia32 is an example.  The way
>   parameters are passed, values returned and possibly even caller-pops
>   may be dependent on the signature of the called function.  If you've
>   eliminated the typecast, then you don't have access to the function's
>   signature.  All hell breaks loose after that.
> 
> 
> 
> jeff
> 
> 
> 
> 
> 
> 
> 

Re: Tree-SSA self checking infrastructure

[law]

In message <20031119203653.GT16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
s:
 >I see, thanks.  Still this breaks the symmetricity only.
 >With transitivity, we still shall be able to verify that we have useless
 >conversion from PLUS_EXPR into it's operands, for instance.
 >Even that appears to be broken at the moment. Why?
I don't know.  As I said I have a todo to look at it, but haven't had
the time.  I would certainly appreciate it if you could poke at it a
little.

Jeff

Re: Tree-SSA self checking infrastructure

[law]

In message <20031119203450.GS16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
s:
 >> In message <20031119190649.GQ16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka w
 >rite
 >> s:
 >>  >This brings me into questions about my tail call updating code.
 >>  >Perhaps I need to re-do SSA form on call cobbered variables after
 >>  >removing the call?
 >> Are you changing the CFG?  Are you changing the dominator tree?  Those
 >I replace tail call by edge back to the beggining of function and I
 >possibly split edge fron entry point.  I also take care to construct PHI
 >nodes for all referenced arguments by hand.
 >This does change CFG, but does not change dominance relationships.
 >I am however removing call and perhaps we are maintaining something that
 >relies on the presence of call...
Since you're not changing the dominance relationships, I think you are
safe.  Presumably you create a PHI node for every variable that is set
inside the newly created loop which is also live at the head of the loop.
Right?



Jeff

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> In message <20031119203450.GS16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
> s:
>  >> In message <20031119190649.GQ16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka w
>  >rite
>  >> s:
>  >>  >This brings me into questions about my tail call updating code.
>  >>  >Perhaps I need to re-do SSA form on call cobbered variables after
>  >>  >removing the call?
>  >> Are you changing the CFG?  Are you changing the dominator tree?  Those
>  >I replace tail call by edge back to the beggining of function and I
>  >possibly split edge fron entry point.  I also take care to construct PHI
>  >nodes for all referenced arguments by hand.
>  >This does change CFG, but does not change dominance relationships.
>  >I am however removing call and perhaps we are maintaining something that
>  >relies on the presence of call...
> Since you're not changing the dominance relationships, I think you are
> safe.  Presumably you create a PHI node for every variable that is set
> inside the newly created loop which is also live at the head of the loop.
> Right?
Hmm, well, does the case of uninitialized variables count?  Can I detect
these somehow?

Honza
> 
> 
> 
> Jeff

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> In message <20031119203653.GT16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
> s:
>  >I see, thanks.  Still this breaks the symmetricity only.
>  >With transitivity, we still shall be able to verify that we have useless
>  >conversion from PLUS_EXPR into it's operands, for instance.
>  >Even that appears to be broken at the moment. Why?
> I don't know.  As I said I have a todo to look at it, but haven't had
> the time.  I would certainly appreciate it if you could poke at it a
> little.
OK, I will add it into my TODO too after the other checks I have better
idea about and lets see who will get it first :)
Honza
> 
> Jeff
> 

Re: Tree-SSA self checking infrastructure

[Richard Henderson]

On Wed, Nov 19, 2003 at 12:13:06PM -0700, law@redhat.com wrote:
>  >This brings me into questions about my tail call updating code.
>  >Perhaps I need to re-do SSA form on call cobbered variables after
>  >removing the call?
> Are you changing the CFG?  Are you changing the dominator tree?  Those
> are the key questions.

Yes, he is, but only by adding a new block on the ENTRY->BB0 edge,
and then edges into that block from the tail recursion sites.

I may be mistaken, but I thought the new phi nodes he was adding 
there would be correct.  Perhaps this is a good test for a verify_ssa
pass?


r~

Re: Tree-SSA self checking infrastructure

[Richard Henderson]

On Wed, Nov 19, 2003 at 09:36:53PM +0100, Jan Hubicka wrote:
> With transitivity, we still shall be able to verify that we have useless
> conversion from PLUS_EXPR into it's operands, for instance.
> Even that appears to be broken at the moment. Why?

See the block comment above maybe_fold_stmt_plus.
IMO that example is a front end bug.


r~

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> On Wed, Nov 19, 2003 at 12:13:06PM -0700, law@redhat.com wrote:
> >  >This brings me into questions about my tail call updating code.
> >  >Perhaps I need to re-do SSA form on call cobbered variables after
> >  >removing the call?
> > Are you changing the CFG?  Are you changing the dominator tree?  Those
> > are the key questions.
> 
> Yes, he is, but only by adding a new block on the ENTRY->BB0 edge,
> and then edges into that block from the tail recursion sites.
> 
> I may be mistaken, but I thought the new phi nodes he was adding 
> there would be correct.  Perhaps this is a good test for a verify_ssa
> pass?
Actually good motivation to write it.
However I didn't find anythign wrong about it, just double checking
everything.

The problem appears to be must_alias related.  If I do tailcall/tail
recursion before it, everything works, after it it breaks, but of course
disabling must_alias may alter decisions of later passes.
I've collected several fixes to must_alias/tree-dfa and I re-testing now
so perhaps the bug will just go away....

Honza
> 
> 
> r~

Re: Tree-SSA self checking infrastructure

[Richard Henderson]

On Wed, Nov 19, 2003 at 08:01:52PM +0100, Jan Hubicka wrote:
> I am almost done with verify_stmts except for tree sharing, as I am
> still not clear about the tree sharing rules.  (Did I mentioned it in
> original email?)

Yes.  I don't know anything about tree sharing rules.  I expect we
can't share much.

> How complex may the symbolic references look like now?

The only valid argument to an INDIRECT_REF is a gimple_reg.

Symbolic references like &ssaname->a.b.c.d[4].y.z[5][6] is valid.
The string of COMPONENT_REF and ARRAY_REFs all reduce to a single
constant addition.



r~

Re: Tree-SSA self checking infrastructure

[law]

In message <20031119210127.GB31811@redhat.com>, Richard Henderson writes:
 >On Wed, Nov 19, 2003 at 12:13:06PM -0700, law@redhat.com wrote:
 >>  >This brings me into questions about my tail call updating code.
 >>  >Perhaps I need to re-do SSA form on call cobbered variables after
 >>  >removing the call?
 >> Are you changing the CFG?  Are you changing the dominator tree?  Those
 >> are the key questions.
 >
 >Yes, he is, but only by adding a new block on the ENTRY->BB0 edge,
 >and then edges into that block from the tail recursion sites.
So that would mean he needs PHIs for any arguments that are changed which
reach the loop backedge and for local variables in the toplevel scope
which have a definition which reaches the backedge.




 > I may be mistaken, but I thought the new phi nodes he was adding 
 > there would be correct.  Perhaps this is a good test for a verify_ssa
 > pass?
Definitely a good test.
jeff

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> In message <20031119210127.GB31811@redhat.com>, Richard Henderson writes:
>  >On Wed, Nov 19, 2003 at 12:13:06PM -0700, law@redhat.com wrote:
>  >>  >This brings me into questions about my tail call updating code.
>  >>  >Perhaps I need to re-do SSA form on call cobbered variables after
>  >>  >removing the call?
>  >> Are you changing the CFG?  Are you changing the dominator tree?  Those
>  >> are the key questions.
>  >
>  >Yes, he is, but only by adding a new block on the ENTRY->BB0 edge,
>  >and then edges into that block from the tail recursion sites.
> So that would mean he needs PHIs for any arguments that are changed which
> reach the loop backedge and for local variables in the toplevel scope
> which have a definition which reaches the backedge.

I am doing the first, how can I implement the second? That may be
actually one problems I am seeing...
(given the fact that only the tail recursion ellimination run as very
last pass before de-ssa breaks I think it is actually not the case, but
definitly needs to be done right)

Honza
> 
> 
> 
> 
>  > I may be mistaken, but I thought the new phi nodes he was adding 
>  > there would be correct.  Perhaps this is a good test for a verify_ssa
>  > pass?
> Definitely a good test.
> jeff

Re: Tree-SSA self checking infrastructure

[law]

In message <20031119205044.GL11681@kam.mff.cuni.cz>, Jan Hubicka writes:
 >> In message <20031119203450.GS16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka w
 >rite
 >> s:
 >>  >> In message <20031119190649.GQ16923@atrey.karlin.mff.cuni.cz>, Jan Hubic
 >ka w
 >>  >rite
 >>  >> s:
 >>  >>  >This brings me into questions about my tail call updating code.
 >>  >>  >Perhaps I need to re-do SSA form on call cobbered variables after
 >>  >>  >removing the call?
 >>  >> Are you changing the CFG?  Are you changing the dominator tree?  Those
 >>  >I replace tail call by edge back to the beggining of function and I
 >>  >possibly split edge fron entry point.  I also take care to construct PHI
 >>  >nodes for all referenced arguments by hand.
 >>  >This does change CFG, but does not change dominance relationships.
 >>  >I am however removing call and perhaps we are maintaining something that
 >>  >relies on the presence of call...
 >> Since you're not changing the dominance relationships, I think you are
 >> safe.  Presumably you create a PHI node for every variable that is set
 >> inside the newly created loop which is also live at the head of the loop.
 >> Right?
 >Hmm, well, does the case of uninitialized variables count?  Can I detect
 >these somehow?
Yes, I think they do.  This has always been a little fuzzy to me, but
I believe folks have argued that you want a PHI if there is a join point
where the uninitialized version meets with some initialized version.

jeffa

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> On Wed, Nov 19, 2003 at 08:01:52PM +0100, Jan Hubicka wrote:
> > I am almost done with verify_stmts except for tree sharing, as I am
> > still not clear about the tree sharing rules.  (Did I mentioned it in
> > original email?)
> 
> Yes.  I don't know anything about tree sharing rules.  I expect we
> can't share much.

I think we do pretty heavy shaing via CCP that does move around the
constant PLUS_EXPRs and friends.  I am not even aware of way to copy
tree expressions.
I wrote the code for testing and will run it once my other bootstrap
finish and come back with results.
> 
> > How complex may the symbolic references look like now?
> 
> The only valid argument to an INDIRECT_REF is a gimple_reg.
> 
> Symbolic references like &ssaname->a.b.c.d[4].y.z[5][6] is valid.
> The string of COMPONENT_REF and ARRAY_REFs all reduce to a single
> constant addition.
THis is nice, however
I am mostly concerned about constants like &a+8 and so.
We are allowing them as gimple operands, or did you changed this?

Honza
> 
> 
> 
> r~

Re: Tree-SSA self checking infrastructure

[Richard Henderson]

On Wed, Nov 19, 2003 at 10:33:58PM +0100, Jan Hubicka wrote:
> I am mostly concerned about constants like &a+8 and so.
> We are allowing them as gimple operands, or did you changed this?

We allow them as gimple operands, to allow propagation.  We do 
not properly support them in get_expr_operands.  I havn't added
the abort back there yet, because of the other type problems I'm
still tracking down.


r~

Re: Tree-SSA self checking infrastructure

[Andrew MacLeod]

On Wed, 2003-11-19 at 16:29, law@redhat.com wrote:
> In message <20031119205044.GL11681@kam.mff.cuni.cz>, Jan Hubicka writes:
>  >> In message <20031119203450.GS16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka w
>  >rite
>  >> s:
>  >>  >> In message <20031119190649.GQ16923@atrey.karlin.mff.cuni.cz>, Jan Hubic
>  >ka w
>  >>  >rite
>  >>  >> s:
>  >>  >>  >This brings me into questions about my tail call updating code.
>  >>  >>  >Perhaps I need to re-do SSA form on call cobbered variables after
>  >>  >>  >removing the call?
>  >>  >> Are you changing the CFG?  Are you changing the dominator tree?  Those
>  >>  >I replace tail call by edge back to the beggining of function and I
>  >>  >possibly split edge fron entry point.  I also take care to construct PHI
>  >>  >nodes for all referenced arguments by hand.
>  >>  >This does change CFG, but does not change dominance relationships.
>  >>  >I am however removing call and perhaps we are maintaining something that
>  >>  >relies on the presence of call...
>  >> Since you're not changing the dominance relationships, I think you are
>  >> safe.  Presumably you create a PHI node for every variable that is set
>  >> inside the newly created loop which is also live at the head of the loop.
>  >> Right?
>  >Hmm, well, does the case of uninitialized variables count?  Can I detect
>  >these somehow?
> Yes, I think they do.  This has always been a little fuzzy to me, but
> I believe folks have argued that you want a PHI if there is a join point
> where the uninitialized version meets with some initialized version.
> 
> jeffa
> 

An SSA version which is uninitialized (apparently there can be only one)
for any given variable can be found via:

          d = default_def (var);



So if the default definition of a variable is an empty stmt, that means
it has no DEF.

so...


 if (EMPTY_STMT_P (SSA_NAME_DEF_STMT (ssa_name))
    {  
       /* This means there is no definition of ssa_var */

       if (default_def (SSA_NAME_VAR (ssa_name)) == ssa_name)
          {
	    /* This is the uninitialized ssa version for the variable.*/
          }
       else
          {
 	    /* This is an error condition. This is not the default
	       definintion, nor is it defined.  */
          }
    }


I thinki its owrks that way. That shjow we check in live_on_entry in
tree-ssa-live.c

If you dont like it, talk to Diego, thats the way he implelemted it
after I pestered him for a long time in order to be able to detect these
:-)

Andrew

Re: Tree-SSA self checking infrastructure

[law]

In message <20031119213603.GW16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
s:
 >I am doing the first, how can I implement the second? That may be
 >actually one problems I am seeing...
 >(given the fact that only the tail recursion ellimination run as very
 >last pass before de-ssa breaks I think it is actually not the case, but
 >definitly needs to be done right)
I'm not absolutely sure myself.  Again, my recollection is a bit fuzzy, but 
I think people have argued that you do want those PHI nodes for the meet
between the uninitialized path and the initialized path.  But before you
spend a lot of time on it, you might want to do a little research.

It's also worth noting that we don't seem to be creating PHIs for this
right now.  Consider:

foo(x)
{

  int a;
label:

  a = 20;

  goto label;
  
}

We don't get a PHI at "label" -- so even if it is recommended that we
have PHIs at the join point between initialized and uninitialized, it
doesn't appear that we currently do it.

jeff

Re: Tree-SSA self checking infrastructure

[Richard Henderson]

On Wed, Nov 19, 2003 at 02:27:12PM -0700, law@redhat.com wrote:
> So that would mean he needs PHIs for any arguments that are changed which
> reach the loop backedge and for local variables in the toplevel scope
> which have a definition which reaches the backedge.

No local variables should reach the backedge.  If a value
isn't passed as an argument, then it's dead.


r~

Re: Tree-SSA self checking infrastructure

[Andrew MacLeod]

On Wed, 2003-11-19 at 15:29, Andrew MacLeod wrote:
> On Wed, 2003-11-19 at 15:23, Andrew MacLeod wrote:
> > On Wed, 2003-11-19 at 14:39, Andrew MacLeod wrote:
> > > On Wed, 2003-11-19 at 14:13, law@redhat.com wrote:
> > > > In message <20031119190649.GQ16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
> > 
> > > 
> > > I haven't run tests or anything on this to make sure I didnt break
> > > anything, but they are running now. I would expect no problems with
> > > existing code, and I would think that if you create a var_map the new
> > > entry point ought to workl just fine. There isnt much new there, so it
> > > should work fine.
> > > 
> > So I need to tweak it a bit, I have a few failing testcases :-| Musta
> > missed something going through so quickly...
> > 
So here's a minor wrinkle in the idea.

if you are rewriting just A, and its versions A_1, A_7, and A_9, and we
have a PHI node:

   B_8 = PHI <B_3(1), B_4(2), A_9(3)>

we aren't trying to turn this PHI node into copies, but we also can't
leave A_9 in the PHI.

We cannot turn A_9 into just A and leave that in the PHI node either.

In fact, the only thing we can do at this point is introduce another
temp, and make that copy.

ie

                  tmp_12 = A_9
                   /
                  /
   B_8 = PHI <B_3(1), B_4(2), tmp_12(3)>

Then we're free to go and ignore the PHI nodes.


Since SSA->normal never had to deal with this (any virtual PHIs are
removed, and all thats left are all the real operands and all real
operands are in the reduction graph.), we'll have to deal with it now.

In order to do this, we'll need a prepass to go and insert those copies
on edges and commit them. I dont see why this couldnt also be done in
remove_ssa_form() as wel, unless you have a more efficient place.

Andrew

Re: Tree-SSA self checking infrastructure

[Andrew MacLeod]

On Wed, 2003-11-19 at 16:44, law@redhat.com wrote:
> In message <20031119213603.GW16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
> s:
>  >I am doing the first, how can I implement the second? That may be
>  >actually one problems I am seeing...
>  >(given the fact that only the tail recursion ellimination run as very
>  >last pass before de-ssa breaks I think it is actually not the case, but
>  >definitly needs to be done right)
> I'm not absolutely sure myself.  Again, my recollection is a bit fuzzy, but 
> I think people have argued that you do want those PHI nodes for the meet
> between the uninitialized path and the initialized path.  But before you
> spend a lot of time on it, you might want to do a little research.
> 
> It's also worth noting that we don't seem to be creating PHIs for this
> right now.  Consider:
> 
> foo(x)
> {
> 
>   int a;
> label:
> 
>   a = 20;
> 
>   goto label;
>   
> }
> 
> We don't get a PHI at "label" -- so even if it is recommended that we
> have PHIs at the join point between initialized and uninitialized, it
> doesn't appear that we currently do it.
> 


I think Diego is triggering it on the uses.   If there is a use of a
that needs to be re-written, and its uninitialized, then we get the
phi's and the default def.


hum.

Andrew

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> In message <20031119213603.GW16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
> s:
>  >I am doing the first, how can I implement the second? That may be
>  >actually one problems I am seeing...
>  >(given the fact that only the tail recursion ellimination run as very
>  >last pass before de-ssa breaks I think it is actually not the case, but
>  >definitly needs to be done right)
> I'm not absolutely sure myself.  Again, my recollection is a bit fuzzy, but 
> I think people have argued that you do want those PHI nodes for the meet
> between the uninitialized path and the initialized path.  But before you
> spend a lot of time on it, you might want to do a little research.
> 
> It's also worth noting that we don't seem to be creating PHIs for this
> right now.  Consider:
> 
> foo(x)
> {
> 
>   int a;
> label:
> 
>   a = 20;
> 
>   goto label;
>   
> }
> 
> We don't get a PHI at "label" -- so even if it is recommended that we
> have PHIs at the join point between initialized and uninitialized, it
> doesn't appear that we currently do it.

THe uninitialized variables does not appear to be big deal.  The more
problem can be global scope variables that we maintain in SSA form.  I
guess these really need PHI node in case function modify them, right?
I think I do have the new SSA names as these will be call clobbered
variables so the call I am converting is implicit set of these.  How do
I figure out the proper names?

Honza
> 
> jeff

Tree sharing issues...

[Jan Hubicka]

> > On Wed, Nov 19, 2003 at 08:01:52PM +0100, Jan Hubicka wrote:
> > > I am almost done with verify_stmts except for tree sharing, as I am
> > > still not clear about the tree sharing rules.  (Did I mentioned it in
> > > original email?)
> > 
> > Yes.  I don't know anything about tree sharing rules.  I expect we
> > can't share much.
> 
> I think we do pretty heavy shaing via CCP that does move around the
> constant PLUS_EXPRs and friends.  I am not even aware of way to copy
> tree expressions.
> I wrote the code for testing and will run it once my other bootstrap
> finish and come back with results.
OK, first possitive in bootstrap is not very far:
stage1/xgcc -Bstage1/ -B/usr/local/i686-pc-linux-gnu/bin/ -c   -g -O2
-DIN_GCC   -W -Wall -Wwrite-strings -Wstrict-prototypes
-Wmissing-prototypes -pedantic -Wno-long-long -Wold-style-definition
-Werror -fno-common   -DHAVE_CONFIG_H -DGENERATOR_FILE    -I. -I.
-I../../gcc -I../../gcc/.
-I../../gcc/../include   ../../gcc/gengtype.c -o gengtype.o
(const char *)"*x";

../../gcc/gengtype.c: In function `write_local_func_for_structure':

../../gcc/gengtype.c:2184: error: Wrong sharing of tree nodes
../../gcc/gengtype.c:2184: internal compiler error: verify_stmts failed.


A shared NOP.  Is this valid? If not, how to duplicate the nodes in CCP?

Honza

Re: Tree sharing issues...

[law]

In message <20031119221355.GN11681@kam.mff.cuni.cz>, Jan Hubicka writes:
 >> > On Wed, Nov 19, 2003 at 08:01:52PM +0100, Jan Hubicka wrote:
 >> > > I am almost done with verify_stmts except for tree sharing, as I am
 >> > > still not clear about the tree sharing rules.  (Did I mentioned it in
 >> > > original email?)
 >> > 
 >> > Yes.  I don't know anything about tree sharing rules.  I expect we
 >> > can't share much.
 >> 
 >> I think we do pretty heavy shaing via CCP that does move around the
 >> constant PLUS_EXPRs and friends.  I am not even aware of way to copy
 >> tree expressions.
 >> I wrote the code for testing and will run it once my other bootstrap
 >> finish and come back with results.
 >OK, first possitive in bootstrap is not very far:
 >stage1/xgcc -Bstage1/ -B/usr/local/i686-pc-linux-gnu/bin/ -c   -g -O2
 >-DIN_GCC   -W -Wall -Wwrite-strings -Wstrict-prototypes
 >-Wmissing-prototypes -pedantic -Wno-long-long -Wold-style-definition
 >-Werror -fno-common   -DHAVE_CONFIG_H -DGENERATOR_FILE    -I. -I.
 >-I../../gcc -I../../gcc/.
 >-I../../gcc/../include   ../../gcc/gengtype.c -o gengtype.o
 >(const char *)"*x";
 >
 >../../gcc/gengtype.c: In function `write_local_func_for_structure':
 >
 >../../gcc/gengtype.c:2184: error: Wrong sharing of tree nodes
 >../../gcc/gengtype.c:2184: internal compiler error: verify_stmts failed.
 >
 >
 >A shared NOP.  Is this valid? If not, how to duplicate the nodes in CCP?
Not enough context to know if it's valid.

I would expect a NOP of a constant to be shared since that's still a
constant and we generally try to share constants.

jeff

Re: Tree sharing issues...

[Jan Hubicka]

> In message <20031119221355.GN11681@kam.mff.cuni.cz>, Jan Hubicka writes:
>  >> > On Wed, Nov 19, 2003 at 08:01:52PM +0100, Jan Hubicka wrote:
>  >> > > I am almost done with verify_stmts except for tree sharing, as I am
>  >> > > still not clear about the tree sharing rules.  (Did I mentioned it in
>  >> > > original email?)
>  >> > 
>  >> > Yes.  I don't know anything about tree sharing rules.  I expect we
>  >> > can't share much.
>  >> 
>  >> I think we do pretty heavy shaing via CCP that does move around the
>  >> constant PLUS_EXPRs and friends.  I am not even aware of way to copy
>  >> tree expressions.
>  >> I wrote the code for testing and will run it once my other bootstrap
>  >> finish and come back with results.
>  >OK, first possitive in bootstrap is not very far:
>  >stage1/xgcc -Bstage1/ -B/usr/local/i686-pc-linux-gnu/bin/ -c   -g -O2
>  >-DIN_GCC   -W -Wall -Wwrite-strings -Wstrict-prototypes
>  >-Wmissing-prototypes -pedantic -Wno-long-long -Wold-style-definition
>  >-Werror -fno-common   -DHAVE_CONFIG_H -DGENERATOR_FILE    -I. -I.
>  >-I../../gcc -I../../gcc/.
>  >-I../../gcc/../include   ../../gcc/gengtype.c -o gengtype.o
>  >(const char *)"*x";
>  >
>  >../../gcc/gengtype.c: In function `write_local_func_for_structure':
>  >
>  >../../gcc/gengtype.c:2184: error: Wrong sharing of tree nodes
>  >../../gcc/gengtype.c:2184: internal compiler error: verify_stmts failed.
>  >
>  >
>  >A shared NOP.  Is this valid? If not, how to duplicate the nodes in CCP?
> Not enough context to know if it's valid.
You may see dump above:
(const char *)"*x";
It is constant.
> 
> I would expect a NOP of a constant to be shared since that's still a
> constant and we generally try to share constants.

OK, I will extend my sharing test by is_gimple_min_invariant.  Does that
look right?

Honza
> 
> jeff

Re: Tree-SSA self checking infrastructure

[law]

In message <1069278417.10538.26.camel@p4>, Andrew MacLeod writes:
 >On Wed, 2003-11-19 at 15:29, Andrew MacLeod wrote:
 >> On Wed, 2003-11-19 at 15:23, Andrew MacLeod wrote:
 >> > On Wed, 2003-11-19 at 14:39, Andrew MacLeod wrote:
 >> > > On Wed, 2003-11-19 at 14:13, law@redhat.com wrote:
 >> > > > In message <20031119190649.GQ16923@atrey.karlin.mff.cuni.cz>, Jan Hub
 >icka write
 >> > 
 >> > > 
 >> > > I haven't run tests or anything on this to make sure I didnt break
 >> > > anything, but they are running now. I would expect no problems with
 >> > > existing code, and I would think that if you create a var_map the new
 >> > > entry point ought to workl just fine. There isnt much new there, so it
 >> > > should work fine.
 >> > > 
 >> > So I need to tweak it a bit, I have a few failing testcases :-| Musta
 >> > missed something going through so quickly...
 >> > 
 >So here's a minor wrinkle in the idea.
Na, already thought of this one.


 >if you are rewriting just A, and its versions A_1, A_7, and A_9, and we
 >have a PHI node:
 >
 >   B_8 = PHI <B_3(1), B_4(2), A_9(3)>
Nope.   If you run into this, then you need to rewrite both A & B.

We mark every root variable appearing in a PHI node we thread through
as needing to be rewritten.

That in turn may trigger other variables to rewrite, so you add them
to your set and iterate until you reach a steady state.

Now the hope (of course) is that this doesn't happen often and that it's
cheap to build the set of variables needing to be rewritten :-)


 >we aren't trying to turn this PHI node into copies, but we also can't
 >leave A_9 in the PHI.
 >
 >We cannot turn A_9 into just A and leave that in the PHI node either.
 >
 >In fact, the only thing we can do at this point is introduce another
 >temp, and make that copy.
 >
 >ie
 >
 >                  tmp_12 = A_9
 >                   /
 >                  /
 >   B_8 = PHI <B_3(1), B_4(2), tmp_12(3)>
 >
 >Then we're free to go and ignore the PHI nodes.
 >
 >
 >Since SSA->normal never had to deal with this (any virtual PHIs are
 >removed, and all thats left are all the real operands and all real
 >operands are in the reduction graph.), we'll have to deal with it now.
 >
 >In order to do this, we'll need a prepass to go and insert those copies
 >on edges and commit them. I dont see why this couldnt also be done in
 >remove_ssa_form() as wel, unless you have a more efficient place.
Hmmm, yours might be more efficient.  It may ultimately depend on how
often this kind of thing happens.

jeff

Re: Tree sharing issues...

[law]

In message <20031119222038.GO11681@kam.mff.cuni.cz>, Jan Hubicka writes:
 >> In message <20031119221355.GN11681@kam.mff.cuni.cz>, Jan Hubicka writes:
 >>  >> > On Wed, Nov 19, 2003 at 08:01:52PM +0100, Jan Hubicka wrote:
 >>  >> > > I am almost done with verify_stmts except for tree sharing, as I am
 >>  >> > > still not clear about the tree sharing rules.  (Did I mentioned it 
 >in
 >>  >> > > original email?)
 >>  >> > 
 >>  >> > Yes.  I don't know anything about tree sharing rules.  I expect we
 >>  >> > can't share much.
 >>  >> 
 >>  >> I think we do pretty heavy shaing via CCP that does move around the
 >>  >> constant PLUS_EXPRs and friends.  I am not even aware of way to copy
 >>  >> tree expressions.
 >>  >> I wrote the code for testing and will run it once my other bootstrap
 >>  >> finish and come back with results.
 >>  >OK, first possitive in bootstrap is not very far:
 >>  >stage1/xgcc -Bstage1/ -B/usr/local/i686-pc-linux-gnu/bin/ -c   -g -O2
 >>  >-DIN_GCC   -W -Wall -Wwrite-strings -Wstrict-prototypes
 >>  >-Wmissing-prototypes -pedantic -Wno-long-long -Wold-style-definition
 >>  >-Werror -fno-common   -DHAVE_CONFIG_H -DGENERATOR_FILE    -I. -I.
 >>  >-I../../gcc -I../../gcc/.
 >>  >-I../../gcc/../include   ../../gcc/gengtype.c -o gengtype.o
 >>  >(const char *)"*x";
 >>  >
 >>  >../../gcc/gengtype.c: In function `write_local_func_for_structure':
 >>  >
 >>  >../../gcc/gengtype.c:2184: error: Wrong sharing of tree nodes
 >>  >../../gcc/gengtype.c:2184: internal compiler error: verify_stmts failed.
 >>  >
 >>  >
 >>  >A shared NOP.  Is this valid? If not, how to duplicate the nodes in CCP?
 >> Not enough context to know if it's valid.
 >You may see dump above:
 >(const char *)"*x";
 >It is constant.
 >> 
 >> I would expect a NOP of a constant to be shared since that's still a
 >> constant and we generally try to share constants.
 >
 >OK, I will extend my sharing test by is_gimple_min_invariant.  Does that
 >look right?
is_gimple_min_invariant (blah) && ! IS_EMPTY_STMT (blah) since I
believe the empty statement is (void) 0, but is not shared.

Ugh.

jeff

Re: Tree-SSA self checking infrastructure

[law]

In message <20031119215117.GX16923@atrey.karlin.mff.cuni.cz>, Jan Hubicka write
s:
 >THe uninitialized variables does not appear to be big deal.  The more
 >problem can be global scope variables that we maintain in SSA form.
Err, aren't these addressable, and thus not rewritten into SSA form.



Jeff

Re: Tree-SSA self checking infrastructure

[law]

In message <1069273770.30703.896.camel@p4>, Andrew MacLeod writes:
 >Anything else you need? 
Not sure.  Experimentation will be the next obvious step :-)

jeff

Re: Tree sharing issues...

[Jan Hubicka]

>  >OK, I will extend my sharing test by is_gimple_min_invariant.  Does that
>  >look right?
> is_gimple_min_invariant (blah) && ! IS_EMPTY_STMT (blah) since I
> believe the empty statement is (void) 0, but is not shared.
> 
> Ugh.
OK, another positive:
../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
#   hard_regs_to_save_6 = VDEF <hard_regs_to_save_624>;
hard_regs_to_save[1] = T.329_1370;

hard_regs_to_save[1];

../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
#   hard_regs_to_save_143 = VDEF <hard_regs_to_save_81>;
hard_regs_to_save[1] = T.339_1393;

hard_regs_to_save[1];

../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
#   hard_regs_to_save_623 = VDEF <hard_regs_to_save_488>;
hard_regs_to_save[1] = T.349_1416;

hard_regs_to_save[1];

../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
#   hard_regs_to_save_80 = VDEF <hard_regs_to_save_5>;
hard_regs_to_save[1] = T.357_1437;

hard_regs_to_save[1];


This looks wrong.  Seems to happen during jump threading...
Ideas?

Honza
> 
> jeff

Re: Tree sharing issues...

[law]

In message <20031119224619.GP11681@kam.mff.cuni.cz>, Jan Hubicka writes:
 >>  >OK, I will extend my sharing test by is_gimple_min_invariant.  Does that
 >>  >look right?
 >> is_gimple_min_invariant (blah) && ! IS_EMPTY_STMT (blah) since I
 >> believe the empty statement is (void) 0, but is not shared.
 >> 
 >> Ugh.
 >OK, another positive:
 >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
 >#   hard_regs_to_save_6 = VDEF <hard_regs_to_save_624>;
 >hard_regs_to_save[1] = T.329_1370;
 >
 >hard_regs_to_save[1];
 >
 >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
 >#   hard_regs_to_save_143 = VDEF <hard_regs_to_save_81>;
 >hard_regs_to_save[1] = T.339_1393;
 >
 >hard_regs_to_save[1];
 >
 >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
 >#   hard_regs_to_save_623 = VDEF <hard_regs_to_save_488>;
 >hard_regs_to_save[1] = T.349_1416;
 >
 >hard_regs_to_save[1];
 >
 >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
 >#   hard_regs_to_save_80 = VDEF <hard_regs_to_save_5>;
 >hard_regs_to_save[1] = T.357_1437;
 >
 >hard_regs_to_save[1];
 >
 >
 >This looks wrong.  Seems to happen during jump threading...
I'm not sure why we wouldn't be sharing that node
(hard_regs_to_save[1]).

Diego?

jeff

Re: Tree sharing issues...

[Jan Hubicka]

> In message <20031119224619.GP11681@kam.mff.cuni.cz>, Jan Hubicka writes:
>  >>  >OK, I will extend my sharing test by is_gimple_min_invariant.  Does that
>  >>  >look right?
>  >> is_gimple_min_invariant (blah) && ! IS_EMPTY_STMT (blah) since I
>  >> believe the empty statement is (void) 0, but is not shared.
>  >> 
>  >> Ugh.
>  >OK, another positive:
>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
>  >#   hard_regs_to_save_6 = VDEF <hard_regs_to_save_624>;
>  >hard_regs_to_save[1] = T.329_1370;
>  >
>  >hard_regs_to_save[1];
>  >
>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
>  >#   hard_regs_to_save_143 = VDEF <hard_regs_to_save_81>;
>  >hard_regs_to_save[1] = T.339_1393;
>  >
>  >hard_regs_to_save[1];
>  >
>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
>  >#   hard_regs_to_save_623 = VDEF <hard_regs_to_save_488>;
>  >hard_regs_to_save[1] = T.349_1416;
>  >
>  >hard_regs_to_save[1];
>  >
>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
>  >#   hard_regs_to_save_80 = VDEF <hard_regs_to_save_5>;
>  >hard_regs_to_save[1] = T.357_1437;
>  >
>  >hard_regs_to_save[1];
>  >
>  >
>  >This looks wrong.  Seems to happen during jump threading...
> I'm not sure why we wouldn't be sharing that node
> (hard_regs_to_save[1]).
> 
> Diego?
I can add it into my definition of shareable nodes, if you tell me how
to recognize these.

Honza
> 
> jeff
> 
> 

Re: Tree sharing issues...

[law]

In message <20031119225619.GR11681@kam.mff.cuni.cz>, Jan Hubicka writes:
 >> In message <20031119224619.GP11681@kam.mff.cuni.cz>, Jan Hubicka writes:
 >>  >>  >OK, I will extend my sharing test by is_gimple_min_invariant.  Does t
 >hat
 >>  >>  >look right?
 >>  >> is_gimple_min_invariant (blah) && ! IS_EMPTY_STMT (blah) since I
 >>  >> believe the empty statement is (void) 0, but is not shared.
 >>  >> 
 >>  >> Ugh.
 >>  >OK, another positive:
 >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
 >>  >#   hard_regs_to_save_6 = VDEF <hard_regs_to_save_624>;
 >>  >hard_regs_to_save[1] = T.329_1370;
 >>  >
 >>  >hard_regs_to_save[1];
 >>  >
 >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
 >>  >#   hard_regs_to_save_143 = VDEF <hard_regs_to_save_81>;
 >>  >hard_regs_to_save[1] = T.339_1393;
 >>  >
 >>  >hard_regs_to_save[1];
 >>  >
 >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
 >>  >#   hard_regs_to_save_623 = VDEF <hard_regs_to_save_488>;
 >>  >hard_regs_to_save[1] = T.349_1416;
 >>  >
 >>  >hard_regs_to_save[1];
 >>  >
 >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
 >>  >#   hard_regs_to_save_80 = VDEF <hard_regs_to_save_5>;
 >>  >hard_regs_to_save[1] = T.357_1437;
 >>  >
 >>  >hard_regs_to_save[1];
 >>  >
 >>  >
 >>  >This looks wrong.  Seems to happen during jump threading...
 >> I'm not sure why we wouldn't be sharing that node
 >> (hard_regs_to_save[1]).
 >> 
 >> Diego?
 >I can add it into my definition of shareable nodes, if you tell me how
 >to recognize these.

 TREE_ADDRESSABLE (var)
  || decl_function_context (var) != current_function_decl
  || may_aliases (var)

Or something close to that.

Jeff

Re: Tree sharing issues...

[Jan Hubicka]

> In message <20031119225619.GR11681@kam.mff.cuni.cz>, Jan Hubicka writes:
>  >> In message <20031119224619.GP11681@kam.mff.cuni.cz>, Jan Hubicka writes:
>  >>  >>  >OK, I will extend my sharing test by is_gimple_min_invariant.  Does t
>  >hat
>  >>  >>  >look right?
>  >>  >> is_gimple_min_invariant (blah) && ! IS_EMPTY_STMT (blah) since I
>  >>  >> believe the empty statement is (void) 0, but is not shared.
>  >>  >> 
>  >>  >> Ugh.
>  >>  >OK, another positive:
>  >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
>  >>  >#   hard_regs_to_save_6 = VDEF <hard_regs_to_save_624>;
>  >>  >hard_regs_to_save[1] = T.329_1370;
>  >>  >
>  >>  >hard_regs_to_save[1];
>  >>  >
>  >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
>  >>  >#   hard_regs_to_save_143 = VDEF <hard_regs_to_save_81>;
>  >>  >hard_regs_to_save[1] = T.339_1393;
>  >>  >
>  >>  >hard_regs_to_save[1];
>  >>  >
>  >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
>  >>  >#   hard_regs_to_save_623 = VDEF <hard_regs_to_save_488>;
>  >>  >hard_regs_to_save[1] = T.349_1416;
>  >>  >
>  >>  >hard_regs_to_save[1];
>  >>  >
>  >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
>  >>  >#   hard_regs_to_save_80 = VDEF <hard_regs_to_save_5>;
>  >>  >hard_regs_to_save[1] = T.357_1437;
>  >>  >
>  >>  >hard_regs_to_save[1];
>  >>  >
>  >>  >
>  >>  >This looks wrong.  Seems to happen during jump threading...
>  >> I'm not sure why we wouldn't be sharing that node
>  >> (hard_regs_to_save[1]).
>  >> 
>  >> Diego?
>  >I can add it into my definition of shareable nodes, if you tell me how
>  >to recognize these.
> 
>  TREE_ADDRESSABLE (var)
>   || decl_function_context (var) != current_function_decl
>   || may_aliases (var)
> 
> Or something close to that.
I am already allowing sharing of all DECL_P nodes.  The node above is
ARRAY_REF with constant operand, isn't it?  So I need some kind of test
"if array_ref is having all arguments constant, then it can be shared"
or am I wrong?

Honza
> 
> Jeff
> 
> 

Re: Tree sharing issues...

[law]

In message <20031119230806.GU11681@kam.mff.cuni.cz>, Jan Hubicka writes:
 >> In message <20031119225619.GR11681@kam.mff.cuni.cz>, Jan Hubicka writes:
 >>  >> In message <20031119224619.GP11681@kam.mff.cuni.cz>, Jan Hubicka writes
 >:
 >>  >>  >>  >OK, I will extend my sharing test by is_gimple_min_invariant.  Do
 >es t
 >>  >hat
 >>  >>  >>  >look right?
 >>  >>  >> is_gimple_min_invariant (blah) && ! IS_EMPTY_STMT (blah) since I
 >>  >>  >> believe the empty statement is (void) 0, but is not shared.
 >>  >>  >> 
 >>  >>  >> Ugh.
 >>  >>  >OK, another positive:
 >>  >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
 >>  >>  >#   hard_regs_to_save_6 = VDEF <hard_regs_to_save_624>;
 >>  >>  >hard_regs_to_save[1] = T.329_1370;
 >>  >>  >
 >>  >>  >hard_regs_to_save[1];
 >>  >>  >
 >>  >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
 >>  >>  >#   hard_regs_to_save_143 = VDEF <hard_regs_to_save_81>;
 >>  >>  >hard_regs_to_save[1] = T.339_1393;
 >>  >>  >
 >>  >>  >hard_regs_to_save[1];
 >>  >>  >
 >>  >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
 >>  >>  >#   hard_regs_to_save_623 = VDEF <hard_regs_to_save_488>;
 >>  >>  >hard_regs_to_save[1] = T.349_1416;
 >>  >>  >
 >>  >>  >hard_regs_to_save[1];
 >>  >>  >
 >>  >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
 >>  >>  >#   hard_regs_to_save_80 = VDEF <hard_regs_to_save_5>;
 >>  >>  >hard_regs_to_save[1] = T.357_1437;
 >>  >>  >
 >>  >>  >hard_regs_to_save[1];
 >>  >>  >
 >>  >>  >
 >>  >>  >This looks wrong.  Seems to happen during jump threading...
 >>  >> I'm not sure why we wouldn't be sharing that node
 >>  >> (hard_regs_to_save[1]).
 >>  >> 
 >>  >> Diego?
 >>  >I can add it into my definition of shareable nodes, if you tell me how
 >>  >to recognize these.
 >> 
 >>  TREE_ADDRESSABLE (var)
 >>   || decl_function_context (var) != current_function_decl
 >>   || may_aliases (var)
 >> 
 >> Or something close to that.
 >I am already allowing sharing of all DECL_P nodes.  The node above is
 >ARRAY_REF with constant operand, isn't it?  So I need some kind of test
 >"if array_ref is having all arguments constant, then it can be shared"
 >or am I wrong?
Well, you also need to allow sharing of certain constants, SSA_NAME nodes
and probably other stuff.

Fundamentally trees haven't had well defined sharing rules, so you're going
to largely have to "figure things out and document them".


Jeff

Re: Tree sharing issues...

[Jan Hubicka]

> In message <20031119230806.GU11681@kam.mff.cuni.cz>, Jan Hubicka writes:
>  >> In message <20031119225619.GR11681@kam.mff.cuni.cz>, Jan Hubicka writes:
>  >>  >> In message <20031119224619.GP11681@kam.mff.cuni.cz>, Jan Hubicka writes
>  >:
>  >>  >>  >>  >OK, I will extend my sharing test by is_gimple_min_invariant.  Do
>  >es t
>  >>  >hat
>  >>  >>  >>  >look right?
>  >>  >>  >> is_gimple_min_invariant (blah) && ! IS_EMPTY_STMT (blah) since I
>  >>  >>  >> believe the empty statement is (void) 0, but is not shared.
>  >>  >>  >> 
>  >>  >>  >> Ugh.
>  >>  >>  >OK, another positive:
>  >>  >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
>  >>  >>  >#   hard_regs_to_save_6 = VDEF <hard_regs_to_save_624>;
>  >>  >>  >hard_regs_to_save[1] = T.329_1370;
>  >>  >>  >
>  >>  >>  >hard_regs_to_save[1];
>  >>  >>  >
>  >>  >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
>  >>  >>  >#   hard_regs_to_save_143 = VDEF <hard_regs_to_save_81>;
>  >>  >>  >hard_regs_to_save[1] = T.339_1393;
>  >>  >>  >
>  >>  >>  >hard_regs_to_save[1];
>  >>  >>  >
>  >>  >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
>  >>  >>  >#   hard_regs_to_save_623 = VDEF <hard_regs_to_save_488>;
>  >>  >>  >hard_regs_to_save[1] = T.349_1416;
>  >>  >>  >
>  >>  >>  >hard_regs_to_save[1];
>  >>  >>  >
>  >>  >>  >../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
>  >>  >>  >#   hard_regs_to_save_80 = VDEF <hard_regs_to_save_5>;
>  >>  >>  >hard_regs_to_save[1] = T.357_1437;
>  >>  >>  >
>  >>  >>  >hard_regs_to_save[1];
>  >>  >>  >
>  >>  >>  >
>  >>  >>  >This looks wrong.  Seems to happen during jump threading...
>  >>  >> I'm not sure why we wouldn't be sharing that node
>  >>  >> (hard_regs_to_save[1]).
>  >>  >> 
>  >>  >> Diego?
>  >>  >I can add it into my definition of shareable nodes, if you tell me how
>  >>  >to recognize these.
>  >> 
>  >>  TREE_ADDRESSABLE (var)
>  >>   || decl_function_context (var) != current_function_decl
>  >>   || may_aliases (var)
>  >> 
>  >> Or something close to that.
>  >I am already allowing sharing of all DECL_P nodes.  The node above is
>  >ARRAY_REF with constant operand, isn't it?  So I need some kind of test
>  >"if array_ref is having all arguments constant, then it can be shared"
>  >or am I wrong?
> Well, you also need to allow sharing of certain constants, SSA_NAME nodes
> and probably other stuff.
> 
> Fundamentally trees haven't had well defined sharing rules, so you're going
> to largely have to "figure things out and document them".
Yes, I quite understand the uglyness of situation :) 
Even on RTL we are breaking sharing all the time, so that is why
I want to implement this early.

This is my current status:
/* Return true when the T can be shared.  */
static bool
tree_node_shared_p (tree t)
{
  if (TYPE_P (t) || DECL_P (t)
      || is_gimple_min_invariant (t)
      || TREE_CODE (t) == SSA_NAME)
    return true;
  return false;
}
It pretty much match what you are mentioning.
The array reference above is other stuff.  If you think it makes
sense, I will add check for ARRAY_REF with all operands passing
is_gimple_min_invariant.  DOes that sound plausible?
Or do we want to fix jump threading?

Honza
> 
> 
> Jeff
> 

Re: Tree sharing issues...

[Richard Henderson]

On Thu, Nov 20, 2003 at 12:17:30AM +0100, Jan Hubicka wrote:
> The array reference above is other stuff.  If you think it makes
> sense, I will add check for ARRAY_REF with all operands passing
> is_gimple_min_invariant.  DOes that sound plausible?

Yes.  Similar with INDIRECT_REF, ADDR_EXPR, COMPONENT_REF,
the two complex operators.


r~

Re: Tree sharing issues...

[law]

In message <20031119231730.GV11681@kam.mff.cuni.cz>, Jan Hubicka writes:
 >This is my current status:
 >/* Return true when the T can be shared.  */
 >static bool
 >tree_node_shared_p (tree t)
 >{
 >  if (TYPE_P (t) || DECL_P (t)
 >      || is_gimple_min_invariant (t)
 >      || TREE_CODE (t) == SSA_NAME)
 >    return true;
 >  return false;
 >}
 >It pretty much match what you are mentioning.
It's a start.  I'm sure we're going to find more stuff.

 >The array reference above is other stuff.  If you think it makes
 >sense, I will add check for ARRAY_REF with all operands passing
 >is_gimple_min_invariant.  DOes that sound plausible?
I'm simply not sure.

 >Or do we want to fix jump threading?
I don't see how jump threading could be creating this.  It doesn't 
muck around with statements in that manner. 

jeff

Re: Tree sharing issues...

[Richard Henderson]

On Wed, Nov 19, 2003 at 04:22:07PM -0700, law@redhat.com wrote:
> I don't see how jump threading could be creating this.  It doesn't 
> muck around with statements in that manner. 

I'm sure he means .dom1's copy/const propagation.


r~

Re: Tree sharing issues...

[Jan Hubicka]

> In message <20031119231730.GV11681@kam.mff.cuni.cz>, Jan Hubicka writes:
>  >This is my current status:
>  >/* Return true when the T can be shared.  */
>  >static bool
>  >tree_node_shared_p (tree t)
>  >{
>  >  if (TYPE_P (t) || DECL_P (t)
>  >      || is_gimple_min_invariant (t)
>  >      || TREE_CODE (t) == SSA_NAME)
>  >    return true;
>  >  return false;
>  >}
>  >It pretty much match what you are mentioning.
> It's a start.  I'm sure we're going to find more stuff.
> 
>  >The array reference above is other stuff.  If you think it makes
>  >sense, I will add check for ARRAY_REF with all operands passing
>  >is_gimple_min_invariant.  DOes that sound plausible?
> I'm simply not sure.
> 
>  >Or do we want to fix jump threading?
> I don't see how jump threading could be creating this.  It doesn't 
> muck around with statements in that manner. 
Apparently it is result of re-renaming.

Honza
> 
> jeff
> 

Re: Tree sharing issues...

[Jan Hubicka]

> On Wed, Nov 19, 2003 at 04:22:07PM -0700, law@redhat.com wrote:
> > I don't see how jump threading could be creating this.  It doesn't 
> > muck around with statements in that manner. 
> 
> I'm sure he means .dom1's copy/const propagation.
Right, I missread the if statement and thought it is all about
threading, but it does dom_1 too.  It ineed it the dom_1 pass.

Honza
> 
> 
> r~

Re: Tree-SSA self checking infrastructure

[Diego Novillo]

On Wed, 2003-11-19 at 16:49, Andrew MacLeod wrote:

> I think Diego is triggering it on the uses.   If there is a use of a
> that needs to be re-written, and its uninitialized, then we get the
> phi's and the default def.
> 
Yes.  Default definitions *only* get created if we need to rewrite a
use/vuse that is not dominated by any prior definition.


Diego.

Re: Tree-SSA self checking infrastructure

[Diego Novillo]

On Wed, 2003-11-19 at 16:33, Jan Hubicka wrote:

> > Yes.  I don't know anything about tree sharing rules.  I expect we
> > can't share much.
> 
> I think we do pretty heavy shaing via CCP that does move around the
> constant PLUS_EXPRs and friends.  I am not even aware of way to copy
> tree expressions.
>
Eh, no.  That shouldn't happen.  We share only DECLs and perhaps
constants.  In particular, we should not be sharing expressions that are
going to be re-written.  Otherwise the SSA renamer pass munges up the
program real good.


> THis is nice, however
> I am mostly concerned about constants like &a+8 and so.
> We are allowing them as gimple operands, or did you changed this?
> 
&a+8 should be a gimple_val, yes.  We were missing an obvious VUSE when
used as a CALL_EXPR argument.  I thought you had fixed that (or did it
get reverted as well?).


Diego.

Re: Tree sharing issues...

[Diego Novillo]

On Wed, 2003-11-19 at 17:46, Jan Hubicka wrote:

> ../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
> #   hard_regs_to_save_80 = VDEF <hard_regs_to_save_5>;
> hard_regs_to_save[1] = T.357_1437;
> 
> hard_regs_to_save[1];
> 
> 
> This looks wrong.  Seems to happen during jump threading...
>
We are generating a statement that is just an ARRAY_REF?  I don't
understand what's being shared here.


Diego.

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> On Wed, 2003-11-19 at 16:33, Jan Hubicka wrote:
> 
> > > Yes.  I don't know anything about tree sharing rules.  I expect we
> > > can't share much.
> > 
> > I think we do pretty heavy shaing via CCP that does move around the
> > constant PLUS_EXPRs and friends.  I am not even aware of way to copy
> > tree expressions.
> >
> Eh, no.  That shouldn't happen.  We share only DECLs and perhaps
> constants.  In particular, we should not be sharing expressions that are
> going to be re-written.  Otherwise the SSA renamer pass munges up the
> program real good.
> 
> 
> > THis is nice, however
> > I am mostly concerned about constants like &a+8 and so.
> > We are allowing them as gimple operands, or did you changed this?
> > 
> &a+8 should be a gimple_val, yes.  We were missing an obvious VUSE when
> used as a CALL_EXPR argument.  I thought you had fixed that (or did it
> get reverted as well?).
Yes, you did reverted that too. I am going to send the bugfix part of
patch again at friday.  (likely I can't do full testing before that)

Honza
> 
> 
> Diego.

Re: Tree sharing issues...

[Jan Hubicka]

> On Wed, 2003-11-19 at 17:46, Jan Hubicka wrote:
> 
> > ../../gcc/caller-save.c:370: error: Wrong sharing of tree nodes
> > #   hard_regs_to_save_80 = VDEF <hard_regs_to_save_5>;
> > hard_regs_to_save[1] = T.357_1437;
> > 
> > hard_regs_to_save[1];
> > 
> > 
> > This looks wrong.  Seems to happen during jump threading...
> >
> We are generating a statement that is just an ARRAY_REF?  I don't
> understand what's being shared here.
It is the hard_regs_to_save[1] inside statement
hard_regs_to_save[1] = T.357_1437;
as we disucssed later, we probably want to allow the sharing here.

Honza
> 
> 
> Diego.
> 

Re: Tree sharing issues...

[Diego Novillo]

On Wed, 2003-11-19 at 18:21, Richard Henderson wrote:
> On Thu, Nov 20, 2003 at 12:17:30AM +0100, Jan Hubicka wrote:
> > The array reference above is other stuff.  If you think it makes
> > sense, I will add check for ARRAY_REF with all operands passing
> > is_gimple_min_invariant.  DOes that sound plausible?
> 
> Yes.  Similar with INDIRECT_REF,
>
No.  INDIRECT_REF nodes must not be shared, we rename the operand inside
INDIRECT_REFs.

>  ADDR_EXPR,

>  COMPONENT_REF,
>
Same problem.  We also rewrite inside COMPONENT_REFs.


Diego.

Re: Tree sharing issues...

[Jan Hubicka]

> On Wed, 2003-11-19 at 18:21, Richard Henderson wrote:
> > On Thu, Nov 20, 2003 at 12:17:30AM +0100, Jan Hubicka wrote:
> > > The array reference above is other stuff.  If you think it makes
> > > sense, I will add check for ARRAY_REF with all operands passing
> > > is_gimple_min_invariant.  DOes that sound plausible?
> > 
> > Yes.  Similar with INDIRECT_REF,
> >
> No.  INDIRECT_REF nodes must not be shared, we rename the operand inside
> INDIRECT_REFs.
> 
> >  ADDR_EXPR,
> 
> >  COMPONENT_REF,
> >
> Same problem.  We also rewrite inside COMPONENT_REFs.

OK.  What about the ARRAY_REF issue?  Do we have plans to rename inside
too?  In that case we probably should fix dominator pass instead
relaxing my tester...

Honza
> 
> 
> Diego.

Re: Tree sharing issues...

[Diego Novillo]

On Wed, 2003-11-19 at 18:17, Jan Hubicka wrote:

> It pretty much match what you are mentioning.
> The array reference above is other stuff.  If you think it makes
> sense, I will add check for ARRAY_REF with all operands passing
> is_gimple_min_invariant.  DOes that sound plausible?
>
In general, we must not allow sharing of any expression that may contain
an operand inside.  I'd use the different get_expr_operands handlers as
a guide.  If a handler calls add_stmt_operand with one of its operands,
then that node must not be shared.


Diego.

Re: Tree sharing issues...

[Jan Hubicka]

> On Wed, 2003-11-19 at 18:17, Jan Hubicka wrote:
> 
> > It pretty much match what you are mentioning.
> > The array reference above is other stuff.  If you think it makes
> > sense, I will add check for ARRAY_REF with all operands passing
> > is_gimple_min_invariant.  DOes that sound plausible?
> >
> In general, we must not allow sharing of any expression that may contain
> an operand inside.  I'd use the different get_expr_operands handlers as
> a guide.  If a handler calls add_stmt_operand with one of its operands,
> then that node must not be shared.
Hmm, then we are unsafe even on is_gimple_min_invariant, as we
add_stmt_operand ADDR_EXPRs that may apepar inside invariant PLUS_EXPR
and then we get things very terribly wrong in CCP and DOM, or is
ADDR_EXPR an exception?

Honza
> 
> 
> Diego.

Re: Tree sharing issues...

[Diego Novillo]

On Wed, 2003-11-19 at 19:20, Jan Hubicka wrote:

> OK.  What about the ARRAY_REF issue?  Do we have plans to rename inside
> too?  In that case we probably should fix dominator pass instead
> relaxing my tester...
> 
We always rewrite inside an ARRAY_REF.  Consider A[i][j].  Both i and j
will be typically renamed.


Diego.

Re: Tree sharing issues...

[Diego Novillo]

On Wed, 2003-11-19 at 19:15, Jan Hubicka wrote:

> It is the hard_regs_to_save[1] inside statement
> hard_regs_to_save[1] = T.357_1437;
> as we disucssed later, we probably want to allow the sharing here.
> 
Oh, that.  Yeah, sharing hard_regs_to_save[1] ought to be safe.

Re: Tree sharing issues...

[Jan Hubicka]

> On Wed, 2003-11-19 at 18:17, Jan Hubicka wrote:
> 
> > It pretty much match what you are mentioning.
> > The array reference above is other stuff.  If you think it makes
> > sense, I will add check for ARRAY_REF with all operands passing
> > is_gimple_min_invariant.  DOes that sound plausible?
> >
> In general, we must not allow sharing of any expression that may contain
> an operand inside.  I'd use the different get_expr_operands handlers as
> a guide.  If a handler calls add_stmt_operand with one of its operands,
> then that node must not be shared.

Hi,
for your amusement I am attaching my current checking patch.  It is
mostly complette but I now have to analyze all the failures I get on
testsuite and figure out what are bugs in my checking code (but most of
bugs on checking side appears to be gone)
Any comments are welcome and if you are advantureous enought to try it
out, let me know.

It looks like the tree sharing problems in tree-ssa-dom and ADDRESSOF
issue are the main shooters right now.
My updated SSA form in tail call passes the testing...

Honza

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.220
diff -c -3 -p -r1.1.4.220 tree-cfg.c
*** tree-cfg.c	19 Nov 2003 02:22:18 -0000	1.1.4.220
--- tree-cfg.c	20 Nov 2003 00:33:48 -0000
*************** make_exit_edges (basic_block bb)
*** 562,567 ****
--- 562,572 ----
  	 create abnormal edges to them.  */
        make_eh_edges (last);
  
+       if (call_expr_flags (last) & ECF_LONGJMP)
+ 	{
+ 	  make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
+ 	  return;
+ 	}
        /* Some calls are known not to return.  For such calls we create
  	 a fake edge.
  
*************** tree_verify_flow_info (void)
*** 2752,2759 ****
      {
        edge e;
        bool found_ctrl_stmt = false;
-       tree phi;
-       int i;
  
        for (e = bb->pred; e; e = e->pred_next)
  	if (e->aux)
--- 2757,2762 ----
*************** tree_verify_flow_info (void)
*** 2761,2803 ****
  	    error ("Aux pointer initialized for edge %d->%d\n", e->src->index, e->dest->index);
  	    err = 1;
  	  }
-       phi = phi_nodes (bb);
-       for ( ; phi; phi = TREE_CHAIN (phi))
- 	{
- 	  int phi_num_args = PHI_NUM_ARGS (phi);
- 
- 	  for (e = bb->pred; e; e = e->pred_next)
- 	    e->aux = (void *)1;
- 	  for (i = 0; i < phi_num_args; i++)
- 	    {
- 	      e = PHI_ARG_EDGE (phi, i);
- 	      if (e->dest != bb)
- 		{
- 		  error ("Phi node for edge %d->%d in %d\n", e->src->index, e->dest->index, bb->index);
- 		  err = 1;
- 		}
- 	      if (e->aux == (void *)0)
- 		{
- 		  error ("Phi node for dead edge %d->%d\n", e->src->index, e->dest->index);
- 		  err = 1;
- 		}
- 	      if (e->aux == (void *)2)
- 		{
- 		  error ("Phi node duplicated for edge %d->%d\n", e->src->index, e->dest->index);
- 		  err = 1;
- 		}
- 	      e->aux = (void *)2;
- 	    }
- 	  for (e = bb->pred; e; e = e->pred_next)
- 	    {
- 	      if (e->aux != (void *)2)
- 		{
- 		  error ("Edge %d->%d miss phi node entry\n", e->src->index, e->dest->index);
- 		  err = 1;
- 		}
- 	      e->aux = (void *)0;
- 	    }
- 	}
  
        /* Skip labels on the start of basic block.  */
        for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
--- 2764,2769 ----
*************** tree_verify_flow_info (void)
*** 3005,3010 ****
--- 2971,3336 ----
    return err;
  }
  
+ /* Callback for walk_tree, check that all elements with address taken are
+    properly noticed as such.  */
+ 
+ static tree
+ verify_addr_expr (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
+ 		  void *data ATTRIBUTE_UNUSED)
+ {
+   if (TREE_CODE (*tp) == ADDR_EXPR)
+     {
+       tree x = TREE_OPERAND (*tp, 0);
+       if (TREE_CODE (x) == ARRAY_REF
+ 	  || TREE_CODE (x) == COMPONENT_REF
+ 	  || TREE_CODE (x) == REALPART_EXPR
+ 	  || TREE_CODE (x) == IMAGPART_EXPR)
+ 	x = TREE_OPERAND (x, 0);
+       if (TREE_CODE (x) == STRING_CST
+ 	  || TREE_CODE (x) == LABEL_DECL
+ 	  || TREE_CODE (x) == FUNCTION_DECL)
+ 	return NULL;
+       if (!TREE_ADDRESSABLE (x))
+         return x;
+     }
+   return NULL;
+ }
+ 
+ /* Verify the STMT, return true if STMT is missformed.
+    Always keep global so it can be called via GDB. 
+ 
+    TODO: Implement type checking.  */
+ bool
+ verify_stmt (tree stmt)
+ {
+   tree addr;
+ 
+   if (!is_gimple_stmt (stmt))
+     {
+       debug_generic_stmt (stmt);
+       error ("Is not valid gimple statement.");
+       return true;
+     }
+   addr = walk_tree (&stmt, verify_addr_expr, NULL, NULL);
+   if (addr)
+     {
+       debug_generic_stmt (addr);
+       error ("Address taken, but ADDRESABLE bit not set");
+       return true;
+     }
+   return false;
+ }
+ 
+ /* Return true when the T can be shared.  */
+ static bool
+ tree_node_shared_p (tree t)
+ {
+   if (TYPE_P (t) || DECL_P (t)
+       || is_gimple_min_invariant (t)
+       || TREE_CODE (t) == SSA_NAME)
+     return true;
+   return false;
+ }
+ 
+ /* Called via walk_trees.  Verify tree sharing.  */
+ static tree
+ verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
+ {
+   htab_t htab = (htab_t) data;
+   void **slot;
+ 
+   if (tree_node_shared_p (*tp))
+     {
+       *walk_subtrees = false;
+       return NULL;
+     }
+   slot = htab_find_slot (htab, *tp, INSERT);
+   if (*slot)
+     return *slot;
+   *slot = *tp;
+   return NULL;
+ }
+ 
+ 
+ /* Verify GIMPLE stmt chain.
+    TODO: veirfy sharing constraints.  */
+ void
+ verify_stmts (void)
+ {
+   basic_block bb;
+   block_stmt_iterator bsi;
+   bool err = false;
+   htab_t htab;
+   tree addr;
+ 
+   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
+ 
+   FOR_EACH_BB (bb)
+     {
+       tree phi;
+       int i;
+ 
+       phi = phi_nodes (bb);
+       for (; phi; phi = TREE_CHAIN (phi))
+ 	{
+ 	  int phi_num_args = PHI_NUM_ARGS (phi);
+ 
+ 	  for (i = 0; i < phi_num_args; i++)
+ 	    {
+ 	      tree t = PHI_ARG_DEF (phi, i);
+ 	      tree addr;
+ 
+ 	      /* Addressable variables do have SSA_NAMEs but they
+ 	         are not considered gimple values.  */
+ 	      if (TREE_CODE (t) != SSA_NAME
+ 		  && TREE_CODE (t) != FUNCTION_DECL
+ 		  && !is_gimple_val (t))
+ 		{
+ 		  debug_generic_stmt (phi);
+ 		  debug_generic_stmt (t);
+ 		  error ("PHI def is not GIMPLE value");
+ 		  err |= true;
+ 		}
+ 	      addr = walk_tree (&t, verify_addr_expr, NULL, NULL);
+ 	      if (addr)
+ 		{
+ 		  debug_generic_stmt (addr);
+ 		  error ("Address taken, but ADDRESABLE bit not set");
+ 		  err |= true;
+ 		}
+ 	      addr = walk_tree (&t, verify_node_sharing, htab, NULL);
+ 	      if (addr)
+ 		{
+ 		  debug_generic_stmt (phi);
+ 		  debug_generic_stmt (addr);
+ 		  error ("Wrong sharing of tree nodes");
+ 		  err |= true;
+ 		}
+ 	    }
+ 	}
+       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ 	{
+ 	  tree stmt = bsi_stmt (bsi);
+ 	  err |= verify_stmt (stmt);
+ 	  addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
+ 	  if (addr)
+ 	    {
+ 	      debug_generic_stmt (stmt);
+ 	      debug_generic_stmt (addr);
+ 	      error ("Wrong sharing of tree nodes");
+ 	      err |= true;
+ 	    }
+ 	}
+     }
+   if (err)
+     internal_error ("verify_stmts failed.");
+   htab_delete (htab);
+ }
+ 
+ /* Used by verify_ssa.  Do sanity checking on OP defined by SSA in block BB.  */
+ static bool
+ verify_def (basic_block bb, basic_block * definition_block, tree op,
+     	    tree stmt, bool abnormal)
+ {
+   bool err = false;
+   if (definition_block[SSA_NAME_VERSION (op)])
+     {
+       debug_generic_stmt (stmt);
+       debug_generic_stmt (op);
+       error ("SSA_NAME set in BB %i and %i",
+ 	     definition_block[SSA_NAME_VERSION (op)]->index, bb->index);
+       err = 1;
+     }
+   definition_block[SSA_NAME_VERSION (op)] = bb;
+   if (SSA_NAME_DEF_STMT (op) != stmt)
+     {
+       debug_generic_stmt (stmt);
+       error ("SSA_NAME_DEF_STMT wrong");
+       err = 1;
+     }
+   if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op) != abnormal)
+     {
+       debug_generic_stmt (stmt);
+       error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI shall be %s",
+ 	     abnormal ? "true" : "false");
+       err = 1;
+     }
+   return err;
+ }
+ 
+ /* Used by verify_ssa.  Do sanity checking on OP used by SSA in block BB.  */
+ static bool
+ verify_use (basic_block bb, basic_block * definition_block, tree op,
+ 	    tree stmt, dominance_info idom)
+ {
+   basic_block dbb = definition_block [SSA_NAME_VERSION (op)];
+   bool err = false;
+ 
+   if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (op)))
+     ;
+   else if (!dbb)
+     {
+       debug_generic_stmt (stmt);
+       debug_generic_stmt (op);
+       error ("Definition is missing");
+       err = 1;
+     }
+   else if (bb != dbb && !dominated_by_p (idom, bb, dbb))
+     {
+       debug_generic_stmt (stmt);
+       debug_generic_stmt (op);
+       error ("Definition in bb %i does not dominate use in bb %i",
+ 	     dbb->index, bb->index);
+       err = 1;
+     }
+   return err;
+ }
+ /* Verify common invariants about SSA graph.
+    TODO: verify the variable annotations
+    verify that use is dominated by definition.  */
+ void
+ verify_ssa (void)
+ {
+   int err = 0;
+   basic_block bb;
+   dominance_info idom;
+   basic_block *definition_block = xcalloc (highest_ssa_version,
+ 		  			   sizeof (basic_block));
+ 
+   idom = calculate_dominance_info (CDI_DOMINATORS);
+   FOR_EACH_BB (bb)
+   {
+     tree phi;
+     block_stmt_iterator bsi;
+     bool abnormal = false;
+ 
+     phi = phi_nodes (bb);
+     for (; phi; phi = TREE_CHAIN (phi))
+       err |= verify_def (bb, definition_block, PHI_RESULT (phi),
+ 	  		 phi, abnormal);
+     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+       {
+ 	tree stmt = bsi_stmt (bsi);
+ 	unsigned int j;
+ 	varray_type vdefs;
+ 	varray_type defs;
+ 
+ 	get_stmt_operands (stmt);
+ 	vdefs = vdef_ops (stmt_ann (stmt));
+ 
+ 	for (j = 0; vdefs && j < VARRAY_ACTIVE_SIZE (vdefs); j++)
+ 	  {
+ 	    tree op = VDEF_RESULT (VARRAY_TREE (vdefs, j));
+ 	    err |= verify_def (bb, definition_block, op, stmt, 0);
+ 	  }
+ 	defs = def_ops (stmt_ann (stmt));
+ 	
+ 	for (j = 0; defs && j < VARRAY_ACTIVE_SIZE (defs); j++)
+ 	  {
+             tree op = *VARRAY_TREE_PTR (defs, j);
+ 	    err |= verify_def (bb, definition_block, op, stmt, 0);
+ 	  }
+       }
+   }
+   FOR_EACH_BB (bb)
+   {
+     edge e;
+     tree phi;
+     block_stmt_iterator bsi;
+     int i;
+     bool abnormal = false;
+ 
+     for (e = bb->pred; e; e = e->pred_next)
+       {
+ 	if (e->flags & EDGE_ABNORMAL)
+ 	  abnormal = true;
+ 	if (e->aux)
+ 	  {
+ 	    error ("Aux pointer initialized for edge %d->%d\n", e->src->index,
+ 		   e->dest->index);
+ 	    err = 1;
+ 	  }
+       }
+     phi = phi_nodes (bb);
+     for (; phi; phi = TREE_CHAIN (phi))
+       {
+ 	int phi_num_args = PHI_NUM_ARGS (phi);
+ 	for (e = bb->pred; e; e = e->pred_next)
+ 	  e->aux = (void *) 1;
+ 	for (i = 0; i < phi_num_args; i++)
+ 	  {
+ 	    tree op = PHI_ARG_DEF (phi, i);
+ 
+ 	    e = PHI_ARG_EDGE (phi, i);
+ 	    if (!is_gimple_min_invariant (op))
+ 	      err |= verify_use (e->src, definition_block, op, phi, idom);
+ 	    if (e->dest != bb)
+ 	      {
+ 		error ("Phi node for edge %d->%d in %d\n", e->src->index,
+ 		       e->dest->index, bb->index);
+ 		err = 1;
+ 	      }
+ 	    if (e->aux == (void *) 0)
+ 	      {
+ 		error ("Phi node for dead edge %d->%d\n", e->src->index,
+ 		       e->dest->index);
+ 		err = 1;
+ 	      }
+ 	    if (e->aux == (void *) 2)
+ 	      {
+ 		error ("Phi node duplicated for edge %d->%d\n", e->src->index,
+ 		       e->dest->index);
+ 		err = 1;
+ 	      }
+ 	    e->aux = (void *) 2;
+ 
+ 	  }
+ 	for (e = bb->pred; e; e = e->pred_next)
+ 	  {
+ 	    if (e->aux != (void *) 2)
+ 	      {
+ 		error ("Edge %d->%d miss phi node entry\n", e->src->index,
+ 		       e->dest->index);
+ 		err = 1;
+ 	      }
+ 	    e->aux = (void *) 0;
+ 	  }
+       }
+ 
+     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+       {
+ 	tree stmt = bsi_stmt (bsi);
+ 	unsigned int j;
+ 	varray_type vuses;
+ 	varray_type uses;
+ 
+ 	get_stmt_operands (stmt);
+ 	vuses = vuse_ops (stmt_ann (stmt));
+ 
+ 	/* For each VDEF on the original statement, we want to create a
+ 	   VUSE of the VDEF result on the new statement.  */
+ 	for (j = 0; vuses && j < VARRAY_ACTIVE_SIZE (vuses); j++)
+ 	  {
+             tree op = VARRAY_TREE (vuses, j);
+ 
+ 	    err |= verify_use (bb, definition_block, op, stmt, idom);
+ 	  }
+ 	uses = use_ops (stmt_ann (stmt));
+ 	
+ 	for (j = 0; uses && j < VARRAY_ACTIVE_SIZE (uses); j++)
+ 	  {
+             tree op = *VARRAY_TREE_PTR (uses, j);
+ 
+ 	    err |= verify_use (bb, definition_block, op, stmt, idom);
+ 	  }
+       }
+   }
+ 
+   free_dominance_info (idom);
+   free (definition_block);
+   if (err)
+     internal_error ("verify_ssa failed.");
+ }
  
  /* Split BB into entry part and rest; if REDIRECT_LATCH, redirect edges
     marked as latch into entry part, analogically for REDIRECT_NONLATCH.
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.181
diff -c -3 -p -r1.1.4.181 tree-dfa.c
*** tree-dfa.c	19 Nov 2003 20:10:00 -0000	1.1.4.181
--- tree-dfa.c	20 Nov 2003 00:33:49 -0000
*************** get_expr_operands (tree stmt, tree *expr
*** 467,473 ****
        get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_none, prev_vops);
  
        for (op = TREE_OPERAND (expr, 1); op; op = TREE_CHAIN (op))
! 	add_stmt_operand (&TREE_VALUE (op), stmt, opf_none, prev_vops);
  
        if (num_call_clobbered_vars > 0)
  	{
--- 467,473 ----
        get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_none, prev_vops);
  
        for (op = TREE_OPERAND (expr, 1); op; op = TREE_CHAIN (op))
!         get_expr_operands (stmt, &TREE_VALUE (op), opf_none, prev_vops);
  
        if (num_call_clobbered_vars > 0)
  	{
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.156
diff -c -3 -p -r1.1.4.156 tree-flow.h
*** tree-flow.h	19 Nov 2003 20:10:01 -0000	1.1.4.156
--- tree-flow.h	20 Nov 2003 00:33:49 -0000
*************** extern void bsi_commit_edge_inserts (boo
*** 443,448 ****
--- 443,451 ----
  extern void bsi_insert_on_edge_immediate (edge, tree);
  extern void notice_special_calls (tree);
  extern void clear_special_calls (void);
+ extern bool verify_stmt (tree);
+ extern void verify_stmts (void);
+ extern void verify_ssa (void);
  
  /* In tree-pretty-print.c.  */
  extern void dump_generic_bb (FILE *, basic_block, int, int);
Index: tree-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-inline.h,v
retrieving revision 1.4.2.4
diff -c -3 -p -r1.4.2.4 tree-inline.h
*** tree-inline.h	25 Oct 2003 19:42:52 -0000	1.4.2.4
--- tree-inline.h	20 Nov 2003 00:33:49 -0000
*************** Boston, MA 02111-1307, USA.  */
*** 26,33 ****
  
  void optimize_inline_calls (tree);
  bool tree_inlinable_function_p (tree);
- tree walk_tree (tree*, walk_tree_fn, void*, void*);
- tree walk_tree_without_duplicates (tree*, walk_tree_fn, void*);
  tree copy_tree_r (tree*, int*, void*);
  void clone_body (tree, tree, void*);
  void remap_save_expr (tree*, void*, tree, int*);
--- 26,31 ----
Index: tree-must-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-must-alias.c,v
retrieving revision 1.1.2.8
diff -c -3 -p -r1.1.2.8 tree-must-alias.c
*** tree-must-alias.c	11 Nov 2003 18:04:46 -0000	1.1.2.8
--- tree-must-alias.c	20 Nov 2003 00:33:49 -0000
*************** find_addressable_vars (sbitmap addresses
*** 172,180 ****
--- 172,194 ----
  	    {
  	      tree t = PHI_ARG_DEF (phi, i);
  
+ 	      if (TREE_CODE (t) == NOP_EXPR)
+ 		t = TREE_OPERAND (t, 0);
+ 
+ 	      if (TREE_CODE (t) == PLUS_EXPR)
+ 		t = TREE_OPERAND (t, 0);
+ 
+ 	      if (TREE_CODE (t) == NOP_EXPR)
+ 		t = TREE_OPERAND (t, 0);
+ 
  	      if (TREE_CODE (t) != ADDR_EXPR)
  		continue;
  	      t = TREE_OPERAND (t, 0);
+ 	      if (TREE_CODE (t) == ARRAY_REF
+ 		  || TREE_CODE (t) == COMPONENT_REF
+ 		  || TREE_CODE (t) == REALPART_EXPR
+ 		  || TREE_CODE (t) == IMAGPART_EXPR)
+ 		t = TREE_OPERAND (t, 0);
  	      if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != PARM_DECL)
  		continue;
  	      SET_BIT (addresses_needed, var_ann (t)->uid);
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.75
diff -c -3 -p -r1.1.4.75 tree-optimize.c
*** tree-optimize.c	18 Nov 2003 19:02:29 -0000	1.1.4.75
--- tree-optimize.c	20 Nov 2003 00:33:49 -0000
*************** optimize_function_tree (tree fndecl, tre
*** 93,98 ****
--- 93,103 ----
        /* Rewrite the function into SSA form.  Initially, request all
  	 variables to be renamed.  */
        rewrite_into_ssa (fndecl, NULL, TDI_ssa_1);
+ #ifdef ENABLE_CHECKING
+       verify_stmts ();
+       verify_ssa ();
+       verify_flow_info ();
+ #endif
  
        /* Set up VARS_TO_RENAME to allow passes to inform which variables
  	 need to be renamed.  */
*************** optimize_function_tree (tree fndecl, tre
*** 102,125 ****
        if (flag_tree_dom)
  	{
  	  tree_ssa_dominator_thread_jumps (fndecl, TDI_thread_jumps);
  
  	  sbitmap_zero (vars_to_rename);
  	  tree_ssa_dominator_optimize (fndecl, vars_to_rename, TDI_dom_1);
  
  	  /* If the dominator optimizations exposed new variables, we need
  	      to repeat the SSA renaming process for those symbols.  */
  	  if (sbitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_2);
  	}
  
        /* Do a first DCE pass prior to must-alias.  This pass will remove
  	 dead pointer assignments taking the address of local variables.  */
        if (flag_tree_dce)
  	tree_ssa_dce (fndecl, TDI_dce_1);
  
! #if 0
!       /* Eliminate tail recursion calls.  */
!       tree_optimize_tail_calls (false, TDI_tail1);
  #endif
  
        /* The must-alias pass removes the aliasing and addressability bits
--- 107,144 ----
        if (flag_tree_dom)
  	{
  	  tree_ssa_dominator_thread_jumps (fndecl, TDI_thread_jumps);
+ #ifdef ENABLE_CHECKING
+ 	  verify_stmts ();
+ 	  verify_flow_info ();
+ #endif
  
  	  sbitmap_zero (vars_to_rename);
  	  tree_ssa_dominator_optimize (fndecl, vars_to_rename, TDI_dom_1);
+ #ifdef ENABLE_CHECKING
+ 	  verify_stmts ();
+ 	  verify_flow_info ();
+ #endif
  
  	  /* If the dominator optimizations exposed new variables, we need
  	      to repeat the SSA renaming process for those symbols.  */
  	  if (sbitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_2);
  	}
+ #ifdef ENABLE_CHECKING
+       verify_stmts ();
+       verify_ssa ();
+       verify_flow_info ();
+ #endif
  
        /* Do a first DCE pass prior to must-alias.  This pass will remove
  	 dead pointer assignments taking the address of local variables.  */
        if (flag_tree_dce)
  	tree_ssa_dce (fndecl, TDI_dce_1);
  
! #ifdef ENABLE_CHECKING
!       verify_stmts ();
!       verify_ssa ();
!       verify_flow_info ();
  #endif
  
        /* The must-alias pass removes the aliasing and addressability bits
*************** optimize_function_tree (tree fndecl, tre
*** 133,138 ****
--- 152,162 ----
  	  if (sbitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_3);
  	}
+ #ifdef ENABLE_CHECKING
+       verify_stmts ();
+       verify_ssa ();
+       verify_flow_info ();
+ #endif
  
        /* Run SCCP (Sparse Conditional Constant Propagation).  */
        if (flag_tree_ccp)
*************** optimize_function_tree (tree fndecl, tre
*** 144,153 ****
--- 168,187 ----
  	  if (sbitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_4);
  	}
+ #ifdef ENABLE_CHECKING
+       verify_stmts ();
+       verify_ssa ();
+       verify_flow_info ();
+ #endif
  
        /* Run SSA-PRE (Partial Redundancy Elimination).  */
        if (flag_tree_pre)
  	tree_perform_ssapre (fndecl, TDI_pre);
+ #ifdef ENABLE_CHECKING
+       verify_stmts ();
+       verify_ssa ();
+       verify_flow_info ();
+ #endif
  
        /* Perform a second pass of dominator optimizations.  */
        if (flag_tree_dom)
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.155
diff -c -3 -p -r1.1.4.155 tree-ssa.c
*** tree-ssa.c	19 Nov 2003 20:10:02 -0000	1.1.4.155
--- tree-ssa.c	20 Nov 2003 00:33:49 -0000
*************** rewrite_out_of_ssa (tree fndecl, enum tr
*** 2478,2483 ****
--- 2478,2486 ----
    if (dump_file && (dump_flags & TDF_DETAILS))
      dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
  
+ #ifdef ENABLE_CHECKING
+   verify_stmts ();
+ #endif
    /* Do some cleanups which reduce the amount of data the
       tree->rtl expanders deal with.  */
    cfg_remove_useless_stmts ();
*************** rewrite_out_of_ssa (tree fndecl, enum tr
*** 2491,2496 ****
--- 2494,2502 ----
        dump_function_to_file (fndecl, dump_file, dump_flags & ~TDF_VOPS);
        dump_end (phase, dump_file);
      }
+ #ifdef ENABLE_CHECKING
+   verify_stmts ();
+ #endif
  
    /* Flush out flow graph and SSA data.  */
    delete_tree_ssa (fndecl);
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.133
diff -c -3 -p -r1.342.2.133 tree.h
*** tree.h	19 Nov 2003 20:10:03 -0000	1.342.2.133
--- tree.h	20 Nov 2003 00:33:49 -0000
*************** extern void dwarf2out_return_reg (const 
*** 3525,3530 ****
--- 3525,3532 ----
  /* The type of a callback function for walking over tree structure.  */
  
  typedef tree (*walk_tree_fn) (tree *, int *, void *);
+ tree walk_tree (tree*, walk_tree_fn, void*, void*);
+ tree walk_tree_without_duplicates (tree*, walk_tree_fn, void*);
  
  /* In tree-dump.c */
  

Re: Tree sharing issues...

[law]

In message <1069288378.22708.2.camel@frodo.toronto.redhat.com>, Diego Novillo w
rites:
 >On Wed, 2003-11-19 at 19:20, Jan Hubicka wrote:
 >
 >> OK.  What about the ARRAY_REF issue?  Do we have plans to rename inside
 >> too?  In that case we probably should fix dominator pass instead
 >> relaxing my tester...
 >> 
 >We always rewrite inside an ARRAY_REF.  Consider A[i][j].  Both i and j
 >will be typically renamed.
Err, what about when the index is a constant?

jeff

Re: Tree sharing issues...

[Diego Novillo]

On Wed, 2003-11-19 at 19:40, law@redhat.com wrote:
> In message <1069288378.22708.2.camel@frodo.toronto.redhat.com>, Diego Novillo w
> rites:
>  
>  >We always rewrite inside an ARRAY_REF.  Consider A[i][j].  Both i and j
>  >will be typically renamed.
> Err, what about when the index is a constant?
> 
Yeah, I had missed that.  In that case, sharing shouldn't be a problem
(like the example Jan posted earlier).  It goes back to following what
get_expr_operands does.  Any tree operand that may end up in def_ops or
use_ops must not be shared.


Diego.

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

Hi,
here is updated patch so it deals correctly with sharing of _REFs.  Now
it passes most of testsuite with exception of -O3 compilations (caused
by ADDRESSOF bug disucssed earlier).  I also had to disable SSAPRE pass
as it does not pass veirfy_ssa anymore. The same step (together with
mustalias fixes present in the patch too) makes all bootstraps of
sibcall testing to pass, but it may be conicidence.  I am will try to
figure out what is gong on.

I will break out the fixes and prepare cleaner patch at friday.

Honza

Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.220
diff -c -3 -p -r1.1.4.220 tree-cfg.c
*** tree-cfg.c	19 Nov 2003 02:22:18 -0000	1.1.4.220
--- tree-cfg.c	20 Nov 2003 01:21:07 -0000
*************** make_exit_edges (basic_block bb)
*** 562,567 ****
--- 562,572 ----
  	 create abnormal edges to them.  */
        make_eh_edges (last);
  
+       if (call_expr_flags (last) & ECF_LONGJMP)
+ 	{
+ 	  make_edge (bb, EXIT_BLOCK_PTR, EDGE_FAKE);
+ 	  return;
+ 	}
        /* Some calls are known not to return.  For such calls we create
  	 a fake edge.
  
*************** tree_verify_flow_info (void)
*** 2752,2759 ****
      {
        edge e;
        bool found_ctrl_stmt = false;
-       tree phi;
-       int i;
  
        for (e = bb->pred; e; e = e->pred_next)
  	if (e->aux)
--- 2757,2762 ----
*************** tree_verify_flow_info (void)
*** 2761,2803 ****
  	    error ("Aux pointer initialized for edge %d->%d\n", e->src->index, e->dest->index);
  	    err = 1;
  	  }
-       phi = phi_nodes (bb);
-       for ( ; phi; phi = TREE_CHAIN (phi))
- 	{
- 	  int phi_num_args = PHI_NUM_ARGS (phi);
- 
- 	  for (e = bb->pred; e; e = e->pred_next)
- 	    e->aux = (void *)1;
- 	  for (i = 0; i < phi_num_args; i++)
- 	    {
- 	      e = PHI_ARG_EDGE (phi, i);
- 	      if (e->dest != bb)
- 		{
- 		  error ("Phi node for edge %d->%d in %d\n", e->src->index, e->dest->index, bb->index);
- 		  err = 1;
- 		}
- 	      if (e->aux == (void *)0)
- 		{
- 		  error ("Phi node for dead edge %d->%d\n", e->src->index, e->dest->index);
- 		  err = 1;
- 		}
- 	      if (e->aux == (void *)2)
- 		{
- 		  error ("Phi node duplicated for edge %d->%d\n", e->src->index, e->dest->index);
- 		  err = 1;
- 		}
- 	      e->aux = (void *)2;
- 	    }
- 	  for (e = bb->pred; e; e = e->pred_next)
- 	    {
- 	      if (e->aux != (void *)2)
- 		{
- 		  error ("Edge %d->%d miss phi node entry\n", e->src->index, e->dest->index);
- 		  err = 1;
- 		}
- 	      e->aux = (void *)0;
- 	    }
- 	}
  
        /* Skip labels on the start of basic block.  */
        for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
--- 2764,2769 ----
*************** tree_verify_flow_info (void)
*** 3005,3010 ****
--- 2971,3340 ----
    return err;
  }
  
+ /* Callback for walk_tree, check that all elements with address taken are
+    properly noticed as such.  */
+ 
+ static tree
+ verify_addr_expr (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
+ 		  void *data ATTRIBUTE_UNUSED)
+ {
+   if (TREE_CODE (*tp) == ADDR_EXPR)
+     {
+       tree x = TREE_OPERAND (*tp, 0);
+       if (TREE_CODE (x) == ARRAY_REF
+ 	  || TREE_CODE (x) == COMPONENT_REF
+ 	  || TREE_CODE (x) == REALPART_EXPR
+ 	  || TREE_CODE (x) == IMAGPART_EXPR)
+ 	x = TREE_OPERAND (x, 0);
+       if (TREE_CODE (x) == STRING_CST
+ 	  || TREE_CODE (x) == LABEL_DECL
+ 	  || TREE_CODE (x) == FUNCTION_DECL)
+ 	return NULL;
+       if (!TREE_ADDRESSABLE (x))
+         return x;
+     }
+   return NULL;
+ }
+ 
+ /* Verify the STMT, return true if STMT is missformed.
+    Always keep global so it can be called via GDB. 
+ 
+    TODO: Implement type checking.  */
+ bool
+ verify_stmt (tree stmt)
+ {
+   tree addr;
+ 
+   if (!is_gimple_stmt (stmt))
+     {
+       debug_generic_stmt (stmt);
+       error ("Is not valid gimple statement.");
+       return true;
+     }
+   addr = walk_tree (&stmt, verify_addr_expr, NULL, NULL);
+   if (addr)
+     {
+       debug_generic_stmt (addr);
+       error ("Address taken, but ADDRESABLE bit not set");
+       return true;
+     }
+   return false;
+ }
+ 
+ /* Return true when the T can be shared.  */
+ static bool
+ tree_node_shared_p (tree t)
+ {
+   if (TYPE_P (t) || DECL_P (t)
+       || is_gimple_min_invariant (t)
+       || TREE_CODE (t) == SSA_NAME)
+     return true;
+   if ((TREE_CODE (t) == ARRAY_REF
+        || TREE_CODE (t) == COMPONENT_REF)
+       && DECL_P (TREE_OPERAND (t, 0))
+       && is_gimple_min_invariant (TREE_OPERAND (t, 1)))
+     return true;
+   if ((TREE_CODE (t) == REALPART_EXPR
+        || TREE_CODE (t) == INDIRECT_REF
+        || TREE_CODE (t) == IMAGPART_EXPR)
+       && is_gimple_min_invariant (TREE_OPERAND (t, 0)))
+     return true;
+   return false;
+ }
+ 
+ /* Called via walk_trees.  Verify tree sharing.  */
+ static tree
+ verify_node_sharing (tree * tp, int *walk_subtrees, void *data)
+ {
+   htab_t htab = (htab_t) data;
+   void **slot;
+ 
+   if (tree_node_shared_p (*tp))
+     {
+       *walk_subtrees = false;
+       return NULL;
+     }
+   slot = htab_find_slot (htab, *tp, INSERT);
+   if (*slot)
+     return *slot;
+   *slot = *tp;
+   return NULL;
+ }
+ 
+ 
+ /* Verify GIMPLE stmt chain.  */
+ void
+ verify_stmts (void)
+ {
+   basic_block bb;
+   block_stmt_iterator bsi;
+   bool err = false;
+   htab_t htab;
+   tree addr;
+ 
+   htab = htab_create (37, htab_hash_pointer, htab_eq_pointer, NULL);
+ 
+   FOR_EACH_BB (bb)
+     {
+       tree phi;
+       int i;
+ 
+       phi = phi_nodes (bb);
+       for (; phi; phi = TREE_CHAIN (phi))
+ 	{
+ 	  int phi_num_args = PHI_NUM_ARGS (phi);
+ 
+ 	  for (i = 0; i < phi_num_args; i++)
+ 	    {
+ 	      tree t = PHI_ARG_DEF (phi, i);
+ 	      tree addr;
+ 
+ 	      /* Addressable variables do have SSA_NAMEs but they
+ 	         are not considered gimple values.  */
+ 	      if (TREE_CODE (t) != SSA_NAME
+ 		  && TREE_CODE (t) != FUNCTION_DECL
+ 		  && !is_gimple_val (t))
+ 		{
+ 		  debug_generic_stmt (phi);
+ 		  debug_generic_stmt (t);
+ 		  error ("PHI def is not GIMPLE value");
+ 		  err |= true;
+ 		}
+ 	      addr = walk_tree (&t, verify_addr_expr, NULL, NULL);
+ 	      if (addr)
+ 		{
+ 		  debug_generic_stmt (addr);
+ 		  error ("Address taken, but ADDRESABLE bit not set");
+ 		  err |= true;
+ 		}
+ 	      addr = walk_tree (&t, verify_node_sharing, htab, NULL);
+ 	      if (addr)
+ 		{
+ 		  debug_generic_stmt (phi);
+ 		  debug_generic_stmt (addr);
+ 		  error ("Wrong sharing of tree nodes");
+ 		  err |= true;
+ 		}
+ 	    }
+ 	}
+       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+ 	{
+ 	  tree stmt = bsi_stmt (bsi);
+ 	  err |= verify_stmt (stmt);
+ 	  addr = walk_tree (&stmt, verify_node_sharing, htab, NULL);
+ 	  if (addr)
+ 	    {
+ 	      debug_generic_stmt (stmt);
+ 	      debug_generic_stmt (addr);
+ 	      error ("Wrong sharing of tree nodes");
+ 	      err |= true;
+ 	    }
+ 	}
+     }
+   if (err)
+     internal_error ("verify_stmts failed.");
+   htab_delete (htab);
+ }
+ 
+ /* Used by verify_ssa.  Do sanity checking on OP defined by SSA in block BB.  */
+ static bool
+ verify_def (basic_block bb, basic_block * definition_block, tree op,
+     	    tree stmt)
+ {
+   bool err = false;
+   if (definition_block[SSA_NAME_VERSION (op)])
+     {
+       debug_generic_stmt (stmt);
+       debug_generic_stmt (op);
+       error ("SSA_NAME set in BB %i and %i",
+ 	     definition_block[SSA_NAME_VERSION (op)]->index, bb->index);
+       err = 1;
+     }
+   definition_block[SSA_NAME_VERSION (op)] = bb;
+   if (SSA_NAME_DEF_STMT (op) != stmt)
+     {
+       debug_generic_stmt (stmt);
+       error ("SSA_NAME_DEF_STMT wrong");
+       err = 1;
+     }
+   return err;
+ }
+ 
+ /* Used by verify_ssa.  Do sanity checking on OP used by SSA in block BB.  */
+ static bool
+ verify_use (basic_block bb, basic_block * definition_block, tree op,
+ 	    tree stmt, dominance_info idom, bool abnormal)
+ {
+   basic_block dbb = definition_block [SSA_NAME_VERSION (op)];
+   bool err = false;
+ 
+   if (IS_EMPTY_STMT (SSA_NAME_DEF_STMT (op)))
+     ;
+   else if (!dbb)
+     {
+       debug_generic_stmt (stmt);
+       debug_generic_stmt (op);
+       error ("Definition is missing");
+       err = 1;
+     }
+   else if (bb != dbb && !dominated_by_p (idom, bb, dbb))
+     {
+       debug_generic_stmt (stmt);
+       debug_generic_stmt (op);
+       error ("Definition in bb %i does not dominate use in bb %i",
+ 	     dbb->index, bb->index);
+       err = 1;
+     }
+   if (!SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op) && abnormal)
+     {
+       debug_generic_stmt (stmt);
+       error ("SSA_NAME_OCCURS_IN_ABNORMAL_PHI shall be set");
+       err = 1;
+     }
+   return err;
+ }
+ /* Verify common invariants about SSA graph.
+    TODO: verify the variable annotations.  */
+ void
+ verify_ssa (void)
+ {
+   int err = 0;
+   basic_block bb;
+   dominance_info idom;
+   basic_block *definition_block = xcalloc (highest_ssa_version,
+ 		  			   sizeof (basic_block));
+ 
+   idom = calculate_dominance_info (CDI_DOMINATORS);
+   FOR_EACH_BB (bb)
+   {
+     tree phi;
+     block_stmt_iterator bsi;
+ 
+     phi = phi_nodes (bb);
+     for (; phi; phi = TREE_CHAIN (phi))
+       err |= verify_def (bb, definition_block, PHI_RESULT (phi),
+ 	  		 phi);
+     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+       {
+ 	tree stmt = bsi_stmt (bsi);
+ 	unsigned int j;
+ 	varray_type vdefs;
+ 	varray_type defs;
+ 
+ 	get_stmt_operands (stmt);
+ 	vdefs = vdef_ops (stmt_ann (stmt));
+ 
+ 	for (j = 0; vdefs && j < VARRAY_ACTIVE_SIZE (vdefs); j++)
+ 	  {
+ 	    tree op = VDEF_RESULT (VARRAY_TREE (vdefs, j));
+ 	    err |= verify_def (bb, definition_block, op, stmt);
+ 	  }
+ 	defs = def_ops (stmt_ann (stmt));
+ 	
+ 	for (j = 0; defs && j < VARRAY_ACTIVE_SIZE (defs); j++)
+ 	  {
+             tree op = *VARRAY_TREE_PTR (defs, j);
+ 	    err |= verify_def (bb, definition_block, op, stmt);
+ 	  }
+       }
+   }
+   FOR_EACH_BB (bb)
+   {
+     edge e;
+     tree phi;
+     block_stmt_iterator bsi;
+     int i;
+ 
+     for (e = bb->pred; e; e = e->pred_next)
+       {
+ 	if (e->aux)
+ 	  {
+ 	    error ("Aux pointer initialized for edge %d->%d\n", e->src->index,
+ 		   e->dest->index);
+ 	    err = 1;
+ 	  }
+       }
+     phi = phi_nodes (bb);
+     for (; phi; phi = TREE_CHAIN (phi))
+       {
+ 	int phi_num_args = PHI_NUM_ARGS (phi);
+ 	for (e = bb->pred; e; e = e->pred_next)
+ 	  e->aux = (void *) 1;
+ 	for (i = 0; i < phi_num_args; i++)
+ 	  {
+ 	    tree op = PHI_ARG_DEF (phi, i);
+ 
+ 	    e = PHI_ARG_EDGE (phi, i);
+ 	    if (!is_gimple_min_invariant (op))
+ 	      err |= verify_use (e->src, definition_block, op, phi, idom,
+ 			         e->flags & EDGE_ABNORMAL);
+ 	    if (e->dest != bb)
+ 	      {
+ 		error ("Phi node for edge %d->%d in %d\n", e->src->index,
+ 		       e->dest->index, bb->index);
+ 		err = 1;
+ 	      }
+ 	    if (e->aux == (void *) 0)
+ 	      {
+ 		error ("Phi node for dead edge %d->%d\n", e->src->index,
+ 		       e->dest->index);
+ 		err = 1;
+ 	      }
+ 	    if (e->aux == (void *) 2)
+ 	      {
+ 		error ("Phi node duplicated for edge %d->%d\n", e->src->index,
+ 		       e->dest->index);
+ 		err = 1;
+ 	      }
+ 	    e->aux = (void *) 2;
+ 
+ 	  }
+ 	for (e = bb->pred; e; e = e->pred_next)
+ 	  {
+ 	    if (e->aux != (void *) 2)
+ 	      {
+ 		error ("Edge %d->%d miss phi node entry\n", e->src->index,
+ 		       e->dest->index);
+ 		err = 1;
+ 	      }
+ 	    e->aux = (void *) 0;
+ 	  }
+       }
+ 
+     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+       {
+ 	tree stmt = bsi_stmt (bsi);
+ 	unsigned int j;
+ 	varray_type vuses;
+ 	varray_type uses;
+ 
+ 	get_stmt_operands (stmt);
+ 	vuses = vuse_ops (stmt_ann (stmt));
+ 
+ 	/* For each VDEF on the original statement, we want to create a
+ 	   VUSE of the VDEF result on the new statement.  */
+ 	for (j = 0; vuses && j < VARRAY_ACTIVE_SIZE (vuses); j++)
+ 	  {
+             tree op = VARRAY_TREE (vuses, j);
+ 
+ 	    err |= verify_use (bb, definition_block, op, stmt, idom, false);
+ 	  }
+ 	uses = use_ops (stmt_ann (stmt));
+ 	
+ 	for (j = 0; uses && j < VARRAY_ACTIVE_SIZE (uses); j++)
+ 	  {
+             tree op = *VARRAY_TREE_PTR (uses, j);
+ 
+ 	    err |= verify_use (bb, definition_block, op, stmt, idom, false);
+ 	  }
+       }
+   }
+ 
+   free_dominance_info (idom);
+   free (definition_block);
+   if (err)
+     internal_error ("verify_ssa failed.");
+ }
  
  /* Split BB into entry part and rest; if REDIRECT_LATCH, redirect edges
     marked as latch into entry part, analogically for REDIRECT_NONLATCH.
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.181
diff -c -3 -p -r1.1.4.181 tree-dfa.c
*** tree-dfa.c	19 Nov 2003 20:10:00 -0000	1.1.4.181
--- tree-dfa.c	20 Nov 2003 01:21:07 -0000
*************** get_expr_operands (tree stmt, tree *expr
*** 467,473 ****
        get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_none, prev_vops);
  
        for (op = TREE_OPERAND (expr, 1); op; op = TREE_CHAIN (op))
! 	add_stmt_operand (&TREE_VALUE (op), stmt, opf_none, prev_vops);
  
        if (num_call_clobbered_vars > 0)
  	{
--- 467,473 ----
        get_expr_operands (stmt, &TREE_OPERAND (expr, 0), opf_none, prev_vops);
  
        for (op = TREE_OPERAND (expr, 1); op; op = TREE_CHAIN (op))
!         get_expr_operands (stmt, &TREE_VALUE (op), opf_none, prev_vops);
  
        if (num_call_clobbered_vars > 0)
  	{
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.156
diff -c -3 -p -r1.1.4.156 tree-flow.h
*** tree-flow.h	19 Nov 2003 20:10:01 -0000	1.1.4.156
--- tree-flow.h	20 Nov 2003 01:21:07 -0000
*************** extern void bsi_commit_edge_inserts (boo
*** 443,448 ****
--- 443,451 ----
  extern void bsi_insert_on_edge_immediate (edge, tree);
  extern void notice_special_calls (tree);
  extern void clear_special_calls (void);
+ extern bool verify_stmt (tree);
+ extern void verify_stmts (void);
+ extern void verify_ssa (void);
  
  /* In tree-pretty-print.c.  */
  extern void dump_generic_bb (FILE *, basic_block, int, int);
Index: tree-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-inline.h,v
retrieving revision 1.4.2.4
diff -c -3 -p -r1.4.2.4 tree-inline.h
*** tree-inline.h	25 Oct 2003 19:42:52 -0000	1.4.2.4
--- tree-inline.h	20 Nov 2003 01:21:07 -0000
*************** Boston, MA 02111-1307, USA.  */
*** 26,33 ****
  
  void optimize_inline_calls (tree);
  bool tree_inlinable_function_p (tree);
- tree walk_tree (tree*, walk_tree_fn, void*, void*);
- tree walk_tree_without_duplicates (tree*, walk_tree_fn, void*);
  tree copy_tree_r (tree*, int*, void*);
  void clone_body (tree, tree, void*);
  void remap_save_expr (tree*, void*, tree, int*);
--- 26,31 ----
Index: tree-must-alias.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-must-alias.c,v
retrieving revision 1.1.2.8
diff -c -3 -p -r1.1.2.8 tree-must-alias.c
*** tree-must-alias.c	11 Nov 2003 18:04:46 -0000	1.1.2.8
--- tree-must-alias.c	20 Nov 2003 01:21:07 -0000
*************** find_addressable_vars (sbitmap addresses
*** 172,180 ****
--- 172,194 ----
  	    {
  	      tree t = PHI_ARG_DEF (phi, i);
  
+ 	      if (TREE_CODE (t) == NOP_EXPR)
+ 		t = TREE_OPERAND (t, 0);
+ 
+ 	      if (TREE_CODE (t) == PLUS_EXPR)
+ 		t = TREE_OPERAND (t, 0);
+ 
+ 	      if (TREE_CODE (t) == NOP_EXPR)
+ 		t = TREE_OPERAND (t, 0);
+ 
  	      if (TREE_CODE (t) != ADDR_EXPR)
  		continue;
  	      t = TREE_OPERAND (t, 0);
+ 	      if (TREE_CODE (t) == ARRAY_REF
+ 		  || TREE_CODE (t) == COMPONENT_REF
+ 		  || TREE_CODE (t) == REALPART_EXPR
+ 		  || TREE_CODE (t) == IMAGPART_EXPR)
+ 		t = TREE_OPERAND (t, 0);
  	      if (TREE_CODE (t) != VAR_DECL && TREE_CODE (t) != PARM_DECL)
  		continue;
  	      SET_BIT (addresses_needed, var_ann (t)->uid);
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.75
diff -c -3 -p -r1.1.4.75 tree-optimize.c
*** tree-optimize.c	18 Nov 2003 19:02:29 -0000	1.1.4.75
--- tree-optimize.c	20 Nov 2003 01:21:07 -0000
*************** optimize_function_tree (tree fndecl, tre
*** 93,98 ****
--- 93,103 ----
        /* Rewrite the function into SSA form.  Initially, request all
  	 variables to be renamed.  */
        rewrite_into_ssa (fndecl, NULL, TDI_ssa_1);
+ #ifdef ENABLE_CHECKING
+       verify_stmts ();
+       verify_ssa ();
+       verify_flow_info ();
+ #endif
  
        /* Set up VARS_TO_RENAME to allow passes to inform which variables
  	 need to be renamed.  */
*************** optimize_function_tree (tree fndecl, tre
*** 102,125 ****
        if (flag_tree_dom)
  	{
  	  tree_ssa_dominator_thread_jumps (fndecl, TDI_thread_jumps);
  
  	  sbitmap_zero (vars_to_rename);
  	  tree_ssa_dominator_optimize (fndecl, vars_to_rename, TDI_dom_1);
  
  	  /* If the dominator optimizations exposed new variables, we need
  	      to repeat the SSA renaming process for those symbols.  */
  	  if (sbitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_2);
  	}
  
        /* Do a first DCE pass prior to must-alias.  This pass will remove
  	 dead pointer assignments taking the address of local variables.  */
        if (flag_tree_dce)
  	tree_ssa_dce (fndecl, TDI_dce_1);
  
! #if 0
!       /* Eliminate tail recursion calls.  */
!       tree_optimize_tail_calls (false, TDI_tail1);
  #endif
  
        /* The must-alias pass removes the aliasing and addressability bits
--- 107,144 ----
        if (flag_tree_dom)
  	{
  	  tree_ssa_dominator_thread_jumps (fndecl, TDI_thread_jumps);
+ #ifdef ENABLE_CHECKING
+ 	  verify_stmts ();
+ 	  verify_flow_info ();
+ #endif
  
  	  sbitmap_zero (vars_to_rename);
  	  tree_ssa_dominator_optimize (fndecl, vars_to_rename, TDI_dom_1);
+ #ifdef ENABLE_CHECKING
+ 	  verify_stmts ();
+ 	  verify_flow_info ();
+ #endif
  
  	  /* If the dominator optimizations exposed new variables, we need
  	      to repeat the SSA renaming process for those symbols.  */
  	  if (sbitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_2);
  	}
+ #ifdef ENABLE_CHECKING
+       verify_stmts ();
+       verify_ssa ();
+       verify_flow_info ();
+ #endif
  
        /* Do a first DCE pass prior to must-alias.  This pass will remove
  	 dead pointer assignments taking the address of local variables.  */
        if (flag_tree_dce)
  	tree_ssa_dce (fndecl, TDI_dce_1);
  
! #ifdef ENABLE_CHECKING
!       verify_stmts ();
!       verify_ssa ();
!       verify_flow_info ();
  #endif
  
        /* The must-alias pass removes the aliasing and addressability bits
*************** optimize_function_tree (tree fndecl, tre
*** 133,138 ****
--- 152,171 ----
  	  if (sbitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_3);
  	}
+ #ifdef ENABLE_CHECKING
+       verify_stmts ();
+       verify_ssa ();
+       verify_flow_info ();
+ #endif
+ 
+       /* Eliminate tail recursion calls and discover sibling calls.  */
+       tree_optimize_tail_calls ();
+ 
+ #ifdef ENABLE_CHECKING
+       verify_stmts ();
+       verify_ssa ();
+       verify_flow_info ();
+ #endif
  
        /* Run SCCP (Sparse Conditional Constant Propagation).  */
        if (flag_tree_ccp)
*************** optimize_function_tree (tree fndecl, tre
*** 144,153 ****
  	  if (sbitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_4);
  	}
  
        /* Run SSA-PRE (Partial Redundancy Elimination).  */
!       if (flag_tree_pre)
  	tree_perform_ssapre (fndecl, TDI_pre);
  
        /* Perform a second pass of dominator optimizations.  */
        if (flag_tree_dom)
--- 177,196 ----
  	  if (sbitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_4);
  	}
+ #ifdef ENABLE_CHECKING
+       verify_stmts ();
+       verify_ssa ();
+       verify_flow_info ();
+ #endif
  
        /* Run SSA-PRE (Partial Redundancy Elimination).  */
!       if (flag_tree_pre && 0)
  	tree_perform_ssapre (fndecl, TDI_pre);
+ #ifdef ENABLE_CHECKING
+       verify_stmts ();
+       verify_ssa ();
+       verify_flow_info ();
+ #endif
  
        /* Perform a second pass of dominator optimizations.  */
        if (flag_tree_dom)
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.155
diff -c -3 -p -r1.1.4.155 tree-ssa.c
*** tree-ssa.c	19 Nov 2003 20:10:02 -0000	1.1.4.155
--- tree-ssa.c	20 Nov 2003 01:21:07 -0000
*************** rewrite_out_of_ssa (tree fndecl, enum tr
*** 2478,2483 ****
--- 2478,2486 ----
    if (dump_file && (dump_flags & TDF_DETAILS))
      dump_tree_cfg (dump_file, dump_flags & ~TDF_DETAILS);
  
+ #ifdef ENABLE_CHECKING
+   verify_stmts ();
+ #endif
    /* Do some cleanups which reduce the amount of data the
       tree->rtl expanders deal with.  */
    cfg_remove_useless_stmts ();
*************** rewrite_out_of_ssa (tree fndecl, enum tr
*** 2491,2496 ****
--- 2494,2502 ----
        dump_function_to_file (fndecl, dump_file, dump_flags & ~TDF_VOPS);
        dump_end (phase, dump_file);
      }
+ #ifdef ENABLE_CHECKING
+   verify_stmts ();
+ #endif
  
    /* Flush out flow graph and SSA data.  */
    delete_tree_ssa (fndecl);
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.133
diff -c -3 -p -r1.342.2.133 tree.h
*** tree.h	19 Nov 2003 20:10:03 -0000	1.342.2.133
--- tree.h	20 Nov 2003 01:21:08 -0000
*************** extern void dwarf2out_return_reg (const 
*** 3525,3530 ****
--- 3525,3532 ----
  /* The type of a callback function for walking over tree structure.  */
  
  typedef tree (*walk_tree_fn) (tree *, int *, void *);
+ tree walk_tree (tree*, walk_tree_fn, void*, void*);
+ tree walk_tree_without_duplicates (tree*, walk_tree_fn, void*);
  
  /* In tree-dump.c */
  

Re: Tree sharing issues...

[law]

In message <20031119233018.GY11681@kam.mff.cuni.cz>, Jan Hubicka writes:
 >> In message <20031119231730.GV11681@kam.mff.cuni.cz>, Jan Hubicka writes:
 >>  >This is my current status:
 >>  >/* Return true when the T can be shared.  */
 >>  >static bool
 >>  >tree_node_shared_p (tree t)
 >>  >{
 >>  >  if (TYPE_P (t) || DECL_P (t)
 >>  >      || is_gimple_min_invariant (t)
 >>  >      || TREE_CODE (t) == SSA_NAME)
 >>  >    return true;
 >>  >  return false;
 >>  >}
 >>  >It pretty much match what you are mentioning.
 >> It's a start.  I'm sure we're going to find more stuff.
 >> 
 >>  >The array reference above is other stuff.  If you think it makes
 >>  >sense, I will add check for ARRAY_REF with all operands passing
 >>  >is_gimple_min_invariant.  DOes that sound plausible?
 >> I'm simply not sure.
 >> 
 >>  >Or do we want to fix jump threading?
 >> I don't see how jump threading could be creating this.  It doesn't 
 >> muck around with statements in that manner. 
 >Apparently it is result of re-renaming.
renaming wouldn't touch that kind of expression either (storing into
an array at a constant position). 


jeff

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> 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.
> 
> 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.
Are you sure this scheme is safe?
CFG cleanup updates SSA form and expect it to be valid on the input.
This looks like wrong interface and it seems to me that cfg_cleanup
should actually call verify_ssa...  Why can't you do re-renaming before
cleaning?

Honza

Re: Tree-SSA self checking infrastructure

[law]

In message <20031121013047.GF341@atrey.karlin.mff.cuni.cz>, Jan Hubicka writes:
 >> 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.
 >> 
 >> 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.
 >Are you sure this scheme is safe?
 >CFG cleanup updates SSA form and expect it to be valid on the input.
I'm pretty sure.  However, long term cleanup_cfg shouldn't be looking at
the SSA graph in any meaningful way.

 >This looks like wrong interface and it seems to me that cfg_cleanup
 >should actually call verify_ssa... 
No, it means cleanup_cfg needs to be re-thought, particularly those
routines which examine/modify the SSA graph.

 > Why can't you do re-renaming before cleaning?
You can do renaming before cleaning, but that's totally silly.  You've
just munged the CFG is lots of interesting ways.  Blocks are going to
go away,  conditionals turn into direct jumps, etc.  All this affects 
renaming.

Jeff

Re: Tree-SSA self checking infrastructure

[Jan Hubicka]

> In message <20031121013047.GF341@atrey.karlin.mff.cuni.cz>, Jan Hubicka writes:
>  >> 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.
>  >> 
>  >> 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.
>  >Are you sure this scheme is safe?
>  >CFG cleanup updates SSA form and expect it to be valid on the input.
> I'm pretty sure.  However, long term cleanup_cfg shouldn't be looking at
> the SSA graph in any meaningful way.
> 
>  >This looks like wrong interface and it seems to me that cfg_cleanup
>  >should actually call verify_ssa... 
> No, it means cleanup_cfg needs to be re-thought, particularly those
> routines which examine/modify the SSA graph.

How can one cleanup the CFG without updating the underlying SSA?

Honza
> 
>  > Why can't you do re-renaming before cleaning?
> You can do renaming before cleaning, but that's totally silly.  You've
> just munged the CFG is lots of interesting ways.  Blocks are going to
> go away,  conditionals turn into direct jumps, etc.  All this affects 
> renaming.
> 
> Jeff