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

[Andrew MacLeod <amacleod at redhat dot com>]

On Mon, 2003-12-15 at 14:18, 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?
> 
> suppose a statement is changed.  To update the immediate uses of this
> statement, you would need to go to the defining statement for each
> variable, find yourself in a (possibly very long) list of uses and
> make the update.  This would be a disaster for the performance.
> 

And how is that different than what you have to update? Oh, I see you
are actually maintaining a double linked list for each use or def.  It
would require less memory to keep integer index that this use is in the
defining stmt's use-list. Thats only one word instead of two for a
prev/next pointer.

However, point taken that we dont want to do any searching at all to
perform the update. That just means a little more memory required to
maintain the info.

> > 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.
> 
> Immediate use is not a property of the statement, but the property of
> the ssa name; so it should be in the SSA_NAME, as my patch does,
> not in the statement annotations.

Point of view.  the SSA_NAME is defined by its stmt, so the two are
inextricably linked. The SSA_NAME exists so we have a DECL node. 

The immediate uses information is all stmt based data flow information,
so it should be in the stmt, IMO. If you change a stmt, you change the
uses information. We never "change" an SSA_NAME, we just change its
defining stmt.  Its six of one, and a half dozen of the other I guess, I
just think its more constant to keep it all the dataflow info in stmt
annotaions, rather than half in ssa_names and half in stmts.

In any case, I'll make immediate_uses my next task (unless there is
something more pressing?). I'll think about whether putting it into
SSA_NAMES makes sense or not. 

I presume you are going to have a need in the loop infrastructure code
to maintain it up to date? Presuming so, I can make it so that its be
updated, if its present.

In order to move forward, I also presume you need a way to ask whether a
specific SSA_NAME has immediate_uses infomation available for it so you
can decide whether to merge blocks or not right?  

something like 
bool immediate_uses_avail_p (tree ssa_name)
  or
bool immediate_uses_avail_p (tree stmt)  

Presumably the latter, but both are easy to provide.

Andrew