Re: [tree-ssa] Lazy updating of stmt operands

[Andrew MacLeod <amacleod@redhat.com>]

On Thu, 2003-12-11 at 17:30, Zdenek Dvorak wrote:
> Hello,
> 
> >  >> > tree-dfa.c:compute_immediate_uses()
> >  >> 
> >  >> Which needs to pass through every single statement in the program. Not
> >  >> really terribly efficient.
> >  >> 
> >  >*shrug*, it's used by SSA-CCP.  Since def-use edges are only needed by
> >  >some passes, I don't think it would be worth our while trying to
> >  >maintain them in get_stmt_operands.

> here is the patch.  It increases time for compiling preprocessed gcc
> sources from 3m43.734s to 3m47.967s.  It does not use interface of
> immediate uses, since that is not well suited for updating; instead it
> just keeps lists of uses for each ssa name.  The old interface and ccp
> that uses it are not changed by the patch, so in fact the cost would
> be a bit smaller.

Why isn't it well suited for updating? The information is in the
defining stmt's annotation, so given any SSA variable, you can get to
the immediate uses by looking at the annotation for SSA_NAME_DEF_STMT.
It needs a marginal extention to deal with the fact that there can be
multiple defs/vdefs on one stmt, but we need to do that to handle
virtual defs anyway.  I would prefer to keep this information right with
the stmt rather than in a table on the side.

Diego, default defs have a (void *)0 stmt, but we can still attach a
stmt annotation to them right? (ie, they arent shared) We need to be
able to, so you better say yes :-)

> 
> It turned out to be simpler not to require the immediate uses to be
> updated all the time; just to keep the list of statements that were
> modified and to update it when get_stmt_operands is called.
> 

Indeed, I think we *have* to maintain some laziness about the way stmts
are updated. Otherwise if you copy the use of a variable and change it
to a new ssa version  before you copy/create the feeding defintion, its
hard to get it right. 

The tricky part is undoing what the stmt use to do when its been
modified. We have the operand cache, but it points at what *use* to be
in the stmt, and that may have potentially been free'd and re-alloced,
or reused for something else.  There are many places where we simply
change the operand and mark the stmt as modified.

We can fix that by extending the information slightly in the data flow
structure to include a reference to what ssa name the data relates to,
but thats reasonably trivial.

I'll think about it over the holidays, it should be possible to provide
lazy updates of the information for whatever variables are present
without too much trouble.  It should tie in nicely with the new operands
work Ive been doing.

> The cost is not insignificant, so we probably don't want to do this
> unless I am able to cut it down or we really need it.

You will find it much cheaper if you only include the specific variables
you are interested in, as CCP does.



Andrew