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

[Zdenek Dvorak <rakdver@atrey.karlin.mff.cuni.cz>]

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.

and is quite a bit harder to manipulate (don't ask me why, just try to
think for a while how would you implement this; if you still feel it is
easy then, persuade me :-) ).  Yes, it could be also done this way, but
I don't find the saving so important to make the things more complicated
than necessary.

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

??? I don't really quite get you.  Either the information should be
available for every statement or not at all. Having something in the
middle is just confusing.

Zdenek