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

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

[Chris Lattner]

Zdenek Dvorak wrote:
> 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.

This is exactly what I was talking about here:
http://gcc.gnu.org/ml/gcc/2003-12/msg00691.html

Imagine if the value you are using is the constant "0".  If you represent
use chains of the 0, there may be "several" instructions on the list.  The
lists can get large.  In LLVM, this is a constant time operation.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

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

[Chris Lattner]

Jeff Law wrote:

> While it's nice to think about a world where you always have immediate
> uses, you end up with FUD chains if you do that -- with ultimately a
> tangled nest of pointers that is bloody impossible to work with in the
> real world.

Uh, no.  Here's a counter-example:
http://llvm.cs.uiuc.edu/

Having efficient, transparently & efficiently updated immediate use
information is extremely valuable for a wide variety of optimizations.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

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

[law]

In message <Pine.LNX.4.44.0312111514190.2582-100000@nondot.org>, Chris Lattner 
writes:
 >
 >Jeff Law wrote:
 >
 >> While it's nice to think about a world where you always have immediate
 >> uses, you end up with FUD chains if you do that -- with ultimately a
 >> tangled nest of pointers that is bloody impossible to work with in the
 >> real world.
 >
 >Uh, no.  Here's a counter-example:
 >http://llvm.cs.uiuc.edu/
 >
 >Having efficient, transparently & efficiently updated immediate use
 >information is extremely valuable for a wide variety of optimizations.
OK.  Maybe it was just Diego implementation that was an unmaintainable
mess :-)

jeff

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

[Chris Lattner]

On Thu, 11 Dec 2003 law@redhat.com wrote:
>  >Jeff Law wrote:
>  >> While it's nice to think about a world where you always have immediate
>  >> uses, you end up with FUD chains if you do that -- with ultimately a
>  >> tangled nest of pointers that is bloody impossible to work with in the
>  >> real world.
>  >
>  >Uh, no.  Here's a counter-example:
>  > http://llvm.cs.uiuc.edu/
>  >
>  >Having efficient, transparently & efficiently updated immediate use
>  >information is extremely valuable for a wide variety of optimizations.
> OK.  Maybe it was just Diego implementation that was an unmaintainable
> mess :-)

I really can't emphasize enough how important this is.  For example, this
information allows an efficient implementation of the LLVM
Value::replaceAllUsesOf operation (which makes all users of a value use
something else, think replacing 'add 2, 4' with '6').  The presence of
this operation makes copy operations in the IR completely superfluous,
along with "copy-propagation" passes (which either effectively have to be
run between all transformations, or be built into all of them).  This
simplifies transformations, makes code more maintainable, etc...

That said, implementing this efficiently is non-obvious.  It is easy to
implement replaceAllUsesOf in O(M*N) time (where N is number of users of
an operation and M is the average number of operands in the users), but
this is obviously disasterous if you have "users" with a large number of
operands, such as PHI nodes for high-degree basic blocks.

If you're interested in how we do this in LLVM, which is O(N), the code
lives in the User, Use, and Value classes.  Following the User::setOperand
code path will probably illustrate the design, and I'm more than happy to
answer any questions about it.  I believe that O(N) is the most efficient
possible, without using algorithms like union-find.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

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

[Andrew MacLeod]

On Thu, 2003-12-11 at 22:43, Chris Lattner wrote:
> On Thu, 11 Dec 2003 law@redhat.com wrote:
> >  >Jeff Law wrote:
> >  >> While it's nice to think about a world where you always have immediate
> >  >> uses, you end up with FUD chains if you do that -- with ultimately a
> >  >> tangled nest of pointers that is bloody impossible to work with in the
> >  >> real world.
> >  >
> >  >Uh, no.  Here's a counter-example:
> >  > http://llvm.cs.uiuc.edu/
> >  >
> >  >Having efficient, transparently & efficiently updated immediate use
> >  >information is extremely valuable for a wide variety of optimizations.
> > OK.  Maybe it was just Diego implementation that was an unmaintainable
> > mess :-)
> 
> I really can't emphasize enough how important this is.  For example, this
> information allows an efficient implementation of the LLVM
> Value::replaceAllUsesOf operation (which makes all users of a value use
> something else, think replacing 'add 2, 4' with '6').  The presence of
> this operation makes copy operations in the IR completely superfluous,
> along with "copy-propagation" passes (which either effectively have to be
> run between all transformations, or be built into all of them).  This
> simplifies transformations, makes code more maintainable, etc...

Its not just maintainability that is at issue. Maintaining immediate
uses is not difficult.  Memory consumption rises dramatically when you
have a lot ssa names and uses and maintain those links. It was a
Significant memory win to only calculate immediate uses for the
ssa_names we cared about in CCP as opposed to all ssa-names.  

 We already have memory footprint problems, and maintaining def->use
links all the time is going to aggravate that situation even more. If
there are times when it is necessary, it ought not be hard to maintain
that information within our current framework. I see no reason to have
it present all the time when only some consumers need it... 

I suspect the loop optimizations are going to fall into the same
category as CCP in that they are going to be interested in the immediate
uses of only a partial subset of variables most of the time. I think its
far more efficient to calculate those when you need them/know what they
are, and possibly maintain just those def->uses.

Andrew

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

[Zdenek Dvorak]

Hello,

> I suspect the loop optimizations are going to fall into the same
> category as CCP in that they are going to be interested in the immediate
> uses of only a partial subset of variables most of the time. I think its
> far more efficient to calculate those when you need them/know what they
> are, and possibly maintain just those def->uses.

hardly; you still must scan all statements to find the uses, so I don't
see where you would want to get the extra efficiency.

Zdenek

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

[Andrew MacLeod]

On Fri, 2003-12-12 at 14:24, Zdenek Dvorak wrote:
> Hello,
> 
> > I suspect the loop optimizations are going to fall into the same
> > category as CCP in that they are going to be interested in the immediate
> > uses of only a partial subset of variables most of the time. I think its
> > far more efficient to calculate those when you need them/know what they
> > are, and possibly maintain just those def->uses.
> 
> hardly; you still must scan all statements to find the uses, so I don't
> see where you would want to get the extra efficiency.
> 
Scanning stmts is very cheap. The uses/defs are all cached. Its barely
even measurable. If you can trim the number of stmt's you are looking at
for immediate_uses by even 50%, you are going to save a lot of memory on
your def-use chains, and you'll have less memory swapping problems.

 And if you do need it over a chain of optimizations, do it once, and
then keep the info up to date/.  You'll be a lot better off I think

Andrew.

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

[Chris Lattner]

> > hardly; you still must scan all statements to find the uses, so I don't
> > see where you would want to get the extra efficiency.
> >
> Scanning stmts is very cheap.

You must not have run across programs that have PHI nodes with thousands
of operands...

> The uses/defs are all cached.

Don't caches take space?

> And if you do need it over a chain of optimizations, do it once, and
> then keep the info up to date/.  You'll be a lot better off I think

Isn't that the whole idea?

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

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

[Andrew MacLeod]

On Fri, 2003-12-12 at 14:46, Chris Lattner wrote:
> > > hardly; you still must scan all statements to find the uses, so I don't
> > > see where you would want to get the extra efficiency.
> > >
> > Scanning stmts is very cheap.
> 
> You must not have run across programs that have PHI nodes with thousands
> of operands...
> 

Yes, thats why CCP had to trim down its def->use chains to just the
variables it cared about rather than all of them. It was a large memory
savings to do that.

> > The uses/defs are all cached.
> 
> Don't caches take space?
> 

Yeah, but thats already consumed. If you are suggesting we replace our
entire operand implemenation with FUDs, I'm pretty sure thats not going
to happen :-)

So our operand cache takes up space. Adding def->use chains takes up
even more space

> > And if you do need it over a chain of optimizations, do it once, and
> > then keep the info up to date/.  You'll be a lot better off I think
> 
> Isn't that the whole idea?
> 

Yes, but I am suggesting we dont keep it around all the time since many
optimizations do not need it, and it costs memory. The ones that do need
it can build that info for the variables it cares about more
efficiently.  CCP cares about a different set of variables than the loop
optimizer likely does.

Andrew

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

[Diego Novillo]

On Fri, 2003-12-12 at 14:53, Andrew MacLeod wrote:

> Yeah, but thats already consumed. If you are suggesting we replace our
> entire operand implemenation with FUDs, I'm pretty sure thats not going
> to happen :-)
> 
But Chris's point has nothing to do with FUD chains.  FUD chains is just
another SSA representation.  It is not related to how you keep track of
your operands.  It merely determines whether you rewrite operands or
keep explicit use-def links between statements.


Diego.

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

[Chris Lattner]

> > I really can't emphasize enough how important this is.  For example, this
> > information allows an efficient implementation of the LLVM
> > Value::replaceAllUsesOf operation (which makes all users of a value use
> > something else, think replacing 'add 2, 4' with '6').  The presence of
> > this operation makes copy operations in the IR completely superfluous,
> > along with "copy-propagation" passes (which either effectively have to be
> > run between all transformations, or be built into all of them).  This
> > simplifies transformations, makes code more maintainable, etc...
>
> Its not just maintainability that is at issue. Maintaining immediate
> uses is not difficult.  Memory consumption rises dramatically when you
> have a lot ssa names and uses and maintain those links. It was a
> Significant memory win to only calculate immediate uses for the
> ssa_names we cared about in CCP as opposed to all ssa-names.

How much memory consumption are we talking about here?  In LLVM, each
instruction consumes space for itself (to hold the opcode, type, etc.),
and 4 words for each operand.  The 4 words includes all use-def and def
use information.  SSA can be a very light-weight representation.

> We already have memory footprint problems, and maintaining def->use
> links all the time is going to aggravate that situation even more. If
> there are times when it is necessary, it ought not be hard to maintain
> that information within our current framework. I see no reason to have
> it present all the time when only some consumers need it...

If you're trying to work around the problem with caches and recomputation
of information, I suspect that you are barking up the wrong tree.  That
said, I don't know exactly what's going on in the tree-ssa world, so there
may be complicating factors.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

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

[Andrew MacLeod]

On Fri, 2003-12-12 at 14:57, Chris Lattner wrote:
> > > I really can't emphasize enough how important this is.  For example, this
> > > information allows an efficient implementation of the LLVM
> > > Value::replaceAllUsesOf operation (which makes all users of a value use
> > > something else, think replacing 'add 2, 4' with '6').  The presence of
> > > this operation makes copy operations in the IR completely superfluous,
> > > along with "copy-propagation" passes (which either effectively have to be
> > > run between all transformations, or be built into all of them).  This
> > > simplifies transformations, makes code more maintainable, etc...
> >
> > Its not just maintainability that is at issue. Maintaining immediate
> > uses is not difficult.  Memory consumption rises dramatically when you
> > have a lot ssa names and uses and maintain those links. It was a
> > Significant memory win to only calculate immediate uses for the
> > ssa_names we cared about in CCP as opposed to all ssa-names.
> 
> How much memory consumption are we talking about here?  In LLVM, each
> instruction consumes space for itself (to hold the opcode, type, etc.),
> and 4 words for each operand.  The 4 words includes all use-def and def
> use information.  SSA can be a very light-weight representation.
> 

Its not the SSA space thats the memory consumption problem. gcc is now
unit at a time, so the entire program is read into memory as trees and
held there. the tree-ssa branch also uses GIMPLE, which creates more
trees. Then you add even a lightweight SSA and this simply magnifies any
additional memory that is used. Once the machine starts swapping, its
another order of magnitude on timing.  So we are trying to watch memory
very carefully.  That plus we are still working within the existing tree
data structures. I beleive our representation of SSA is quite
lightweight. It only becomes less so when you try to add a bunch of
stuff that isnt needed everywhere. 

> > We already have memory footprint problems, and maintaining def->use
> > links all the time is going to aggravate that situation even more. If
> > there are times when it is necessary, it ought not be hard to maintain
> > that information within our current framework. I see no reason to have
> > it present all the time when only some consumers need it...
> 
> If you're trying to work around the problem with caches and recomputation
> of information, I suspect that you are barking up the wrong tree.  That
> said, I don't know exactly what's going on in the tree-ssa world, so there
> may be complicating factors.
> 

The Cache isnt something we're trying to work around. Thats there to
prevent us from having to muck around in trees looking for things which
are operands. The stmt is in the form of trees, our "cache" is the
equivilent of your instruction. It consists of the operands plus looking
at the tree code(s) of the stmt. 

So we have 1 word for each operand. It points to the SSA_NAME in the
stmt tree which represents that ssa version. 

As far as Im concerned, we're not working around anything. Everything
works just fine. IF someone wants/needs the def->use inforation, it can
be built today. What we dont have is the ability to keep it up to date
for some period of time, simply because we've never needed it. If the
time comes that we do need it, it is not hard to add. 

Andrew

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

[Chris Lattner]

> Its not the SSA space thats the memory consumption problem. gcc is now
> unit at a time, so the entire program is read into memory as trees and
> held there. the tree-ssa branch also uses GIMPLE, which creates more
> trees. Then you add even a lightweight SSA and this simply magnifies any
> additional memory that is used. Once the machine starts swapping, its
> another order of magnitude on timing.

Why exactly do you need all of these representations?  In LLVM, we
routinely optimize _entire_ reasonably large C++ programs (like LLVM
itself), without even coming _near_ swap.  Can't you get rid of some of
the duplicate information you are holding?

> So we are trying to watch memory very carefully.  That plus we are still
> working within the existing tree data structures. I beleive our
> representation of SSA is quite lightweight. It only becomes less so when
> you try to add a bunch of stuff that isnt needed everywhere.

It seems to me that you are trying to save memory in the wrong places, but
my knowledge of tree-ssa is pretty limited, so I could certainly be wrong.
I think that you should be looking for the fundamental gains, especially
at this stage of the project.  If you try to make any big changes when you
have lots of transformations written, it will only be harder.  If you
build on a non-sustainable foundation, and never change it, ultimately the
project will become unwieldy.  Perhaps trees are not the right approach.

Saving memory by not having basic things like use-def or def-use chains is
not the right approach either in my mind.

> > If you're trying to work around the problem with caches and recomputation
> > of information, I suspect that you are barking up the wrong tree.  That
> > said, I don't know exactly what's going on in the tree-ssa world, so there
> > may be complicating factors.
>
> The Cache isnt something we're trying to work around. Thats there to
> prevent us from having to muck around in trees looking for things which
> are operands. The stmt is in the form of trees, our "cache" is the
> equivilent of your instruction. It consists of the operands plus looking
> at the tree code(s) of the stmt.

I'm not saying that you are trying to work around the cache: I'm saying
the cache is a workaround.  If "mucking around in the trees looking for
things" is that expensive, you have other problems which the cache is only
disguising.

> So we have 1 word for each operand. It points to the SSA_NAME in the
> stmt tree which represents that ssa version.

How big is each "SSA_NAME"?  What is the _total allocated size_?  Has
anyone looked into what the aggregate footprint is of a simple plus node
with two SSA operands?

> As far as Im concerned, we're not working around anything. Everything
> works just fine. IF someone wants/needs the def->use inforation, it can
> be built today. What we dont have is the ability to keep it up to date
> for some period of time, simply because we've never needed it. If the
> time comes that we do need it, it is not hard to add.

You have to remember that my opinion is not worth very much, and that my
knowledge of tree-ssa is quite limited.  That said, I am qualified to say
that def-use information can be put to good use by _almost every
transformation_, and that the information should be _automatically kept
up-to-date_ by the infrastructure.

Doing it any other way will cause tremendous problems down the road.

-Chris

-- 
http://llvm.cs.uiuc.edu/
http://www.nondot.org/~sabre/Projects/

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

[law]

In message <1071323157.3257.138.camel@p4>, Andrew MacLeod writes:
 >The Cache isnt something we're trying to work around. Thats there to
 >prevent us from having to muck around in trees looking for things which
 >are operands. The stmt is in the form of trees, our "cache" is the
 >equivilent of your instruction. It consists of the operands plus looking
 >at the tree code(s) of the stmt. 
 >
 >So we have 1 word for each operand. It points to the SSA_NAME in the
 >stmt tree which represents that ssa version. 
 >
 >As far as Im concerned, we're not working around anything. Everything
 >works just fine. IF someone wants/needs the def->use inforation, it can
 >be built today. What we dont have is the ability to keep it up to date
 >for some period of time, simply because we've never needed it. If the
 >time comes that we do need it, it is not hard to add. 
In fact, we could even ponder the idea of what we now know as the operand
cache morphing into a lighter-weight IL at some point in the future.


Jeff

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

[Andrew MacLeod]

On Mon, 2003-12-15 at 18:36, law@redhat.com wrote:
> In message <1071323157.3257.138.camel@p4>, Andrew MacLeod writes:
>  >The Cache isnt something we're trying to work around. Thats there to
>  >prevent us from having to muck around in trees looking for things which
>  >are operands. The stmt is in the form of trees, our "cache" is the
>  >equivilent of your instruction. It consists of the operands plus looking
>  >at the tree code(s) of the stmt. 
>  >
>  >So we have 1 word for each operand. It points to the SSA_NAME in the
>  >stmt tree which represents that ssa version. 
>  >
>  >As far as Im concerned, we're not working around anything. Everything
>  >works just fine. IF someone wants/needs the def->use inforation, it can
>  >be built today. What we dont have is the ability to keep it up to date
>  >for some period of time, simply because we've never needed it. If the
>  >time comes that we do need it, it is not hard to add. 
> In fact, we could even ponder the idea of what we now know as the operand
> cache morphing into a lighter-weight IL at some point in the future.
> 
Indeed, it is the core of what we deal with.

Andrew

[tree-ssa] Lazy updating of stmt operands

[Zdenek Dvorak]

Hello,

what is the purpose of having lists of stmt operands updated on demand?
I thought that it is for performance reasons, but this seems not to be
the case as all the statements are anyway scanned in the final dce pass,
so they end up in updated forms and we cannot gain anything elsewhere.

Why I am interested in this is that it prevents us from having also
def-use edges (immediate uses) provided explicitly, which would be
convenient in two cases I have encountered recently.

Zdenek

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

[Diego Novillo]

On Sun, 2003-12-07 at 11:19, Zdenek Dvorak wrote:

> what is the purpose of having lists of stmt operands updated on demand?
>
Performance.  If the statement hasn't changed, no point re-scanning it.

> I thought that it is for performance reasons, but this seems not to be
> the case as all the statements are anyway scanned in the final dce pass,
> so they end up in updated forms and we cannot gain anything elsewhere.
> 
The call to get_stmt_operands doesn't necessarily mean that the
statement will be re-scanned.

> Why I am interested in this is that it prevents us from having also
> def-use edges (immediate uses) provided explicitly, which would be
> convenient in two cases I have encountered recently.
> 
tree-dfa.c:compute_immediate_uses()


Diego.

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

[Zdenek Dvorak]

Hello,

> > what is the purpose of having lists of stmt operands updated on demand?
> >
> Performance.  If the statement hasn't changed, no point re-scanning it.

right.  But this would as well be the case if the information was always
kept up-to-date.

> > I thought that it is for performance reasons, but this seems not to be
> > the case as all the statements are anyway scanned in the final dce pass,
> > so they end up in updated forms and we cannot gain anything elsewhere.
> > 
> The call to get_stmt_operands doesn't necessarily mean that the
> statement will be re-scanned.
>
> > Why I am interested in this is that it prevents us from having also
> > def-use edges (immediate uses) provided explicitly, which would be
> > convenient in two cases I have encountered recently.
> > 
> tree-dfa.c:compute_immediate_uses()

Which needs to pass through every single statement in the program. Not
really terribly efficient.

Zdenek

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

[Diego Novillo]

On Sun, 2003-12-07 at 12:14, Zdenek Dvorak wrote:

> right.  But this would as well be the case if the information was always
> kept up-to-date.
> 
Not possible.  In DOM we build hash tables that do value numbering on
the operands and voperands.  If we used and eager scheme to keep this
information up-to-date, we would not be able to remove statements from
hash tables after modifying them.  See how DOM very carefully avoids
calling get_stmt_operands while it's doing its thing.

Also, mark_new_vars_to_rename relies on the stale operands to still be
there to find what variables need to be renamed.

Changing the current lazy approach into an eager scheme, would mean
modifying several, seemingly unrelated, things.


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

But I'm ready to be convinced otherwise.  Say, with an implementation
comparing both approaches with timings over a reasonable code base (a
typical GCC bootstrap or one of the compile-time related PRs).


Diego.

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

[Zdenek Dvorak]

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.

the cases when I would find it convenient:

1) Merge_blocks.  The natural way (for virtual operands, the only way) of
   getting rid of the degenerated phi nodes in the second block is to copy
   propagate the set implied by the phi node.  Since cfg cleanup should
   be fast, I don't like scanning of all statements as implied by
   compute_immediate_uses.
2) Generic incremental updating of SSA also requires the def-use edges;
   (this can probably be avoided by solving each special case separately
   or fixing the tree-ssa form only after end of the pass, by calling
   rewrite_into_ssa).

Neither of them is a showstopper, but they seemed important enough to me
to ask for ideas.

Zdenek

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

[law]

In message <20031207174622.GA13528@atrey.karlin.mff.cuni.cz>, Zdenek Dvorak wri
tes:
 >1) Merge_blocks.  The natural way (for virtual operands, the only way) of
 >   getting rid of the degenerated phi nodes in the second block is to copy
 >   propagate the set implied by the phi node.  Since cfg cleanup should
 >   be fast, I don't like scanning of all statements as implied by
 >   compute_immediate_uses.
Before spending a lot of time worrying about this, I would first look into
why the combination of the dominator optimizer and DCE doesn't kill such
PHI nodes.

While I'd like to have some generic code to optimize away useless PHIs, in
practice I've haven't found the need.

jeff

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

[Steven Bosscher]

On Sunday 07 December 2003 18:29, Diego Novillo wrote:
> > > 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.

There are going to be more passes that need immediate uses.  Even a simple 
pass to kill redundant PHIs (say, after unswitching a loop) will have to go 
over _all_ statements to get the immediate uses of one or two statements.  It 
would be really nice if there were some way to keep this information 
up-to-date at all times...

Gr.
Steven

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

[Andrew MacLeod]

On Sun, 2003-12-07 at 16:41, Steven Bosscher wrote:
> On Sunday 07 December 2003 18:29, Diego Novillo wrote:
> > > > 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.
> 
> There are going to be more passes that need immediate uses.  Even a simple 
> pass to kill redundant PHIs (say, after unswitching a loop) will have to go 
> over _all_ statements to get the immediate uses of one or two statements.  It 
> would be really nice if there were some way to keep this information 
> up-to-date at all times...

So use get_immidiate_uses() which does what is required on demand, and
if we discover its a serious performance issue down the road, it ought
to be easy enough to change. The interface is abstracted out already.
since operands are cached, a pass through the IL is actually pretty
cheap. Its nothing like the expense of a pass through rtl.

The effort and memory required to keep this information up to date
throughout all compilations would not be insignificant, and until it is
demonstrated that its a win to do so, I wouldn't want to keep it around
all the time.

CCP uses the information, and one of the big compile time and memory
savings on that pass was to optimize the immediate_uses code to only
build it for SSA_NAMEs which we actually cared about. It was a
significant memory hit to build it and have it around for all stmts. 

It would also be possible down the road, if it is an issue, to maintain
the immediate uses information only for as long as it is required. 
Ie, get_stmt_operands could update the immediate_uses info if its
present and we want to keep it up to date. Then if you have a string of
optimizations that want the information, you can keep it up to date
automatically. 

I'd wait until we measure a performance need to do this however. 

Andrew

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

[Zdenek Dvorak]

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.
> > 
> > There are going to be more passes that need immediate uses.  Even a simple 
> > pass to kill redundant PHIs (say, after unswitching a loop) will have to go 
> > over _all_ statements to get the immediate uses of one or two statements.  It 
> > would be really nice if there were some way to keep this information 
> > up-to-date at all times...
> 
> So use get_immidiate_uses() which does what is required on demand, and
> if we discover its a serious performance issue down the road, it ought
> to be easy enough to change.

we are talking about updating ssa after every operation; this would mean
calling get_immediate_uses a lot. I am quite sure there would be a
performance problem.  There is a little sense in not keeping the
information, especially given that it is entirely trivial.  I will
prepare a patch so that we may measure whether the costs of the updating
are significant.

Zdenek

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

[law]

In message <1070979982.17702.2610.camel@p4>, Andrew MacLeod writes:
 >So use get_immidiate_uses() which does what is required on demand, and
 >if we discover its a serious performance issue down the road, it ought
 >to be easy enough to change. The interface is abstracted out already.
 >since operands are cached, a pass through the IL is actually pretty
 >cheap. Its nothing like the expense of a pass through rtl.
Precisely.


 >The effort and memory required to keep this information up to date
 >throughout all compilations would not be insignificant, and until it is
 >demonstrated that its a win to do so, I wouldn't want to keep it around
 >all the time.
Right.  We already went down that path.  It was completely unusable.


 >CCP uses the information, and one of the big compile time and memory
 >savings on that pass was to optimize the immediate_uses code to only
 >build it for SSA_NAMEs which we actually cared about. It was a
 >significant memory hit to build it and have it around for all stmts. 
 >
 >It would also be possible down the road, if it is an issue, to maintain
 >the immediate uses information only for as long as it is required. 
 >Ie, get_stmt_operands could update the immediate_uses info if its
 >present and we want to keep it up to date. Then if you have a string of
 >optimizations that want the information, you can keep it up to date
 >automatically. 
Precisely.

jeff

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

[law]

In message <1070818186.7334.30.camel@frodo.toronto.redhat.com>, Diego Novillo w
rites:
 >> > 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.
 >
 >But I'm ready to be convinced otherwise.  Say, with an implementation
 >comparing both approaches with timings over a reasonable code base (a
 >typical GCC bootstrap or one of the compile-time related PRs).
IMHO, when we have the need, then we'll expand on the immediate uses
interface -- either by having a way to incrementally update it, or 
rebuild it.

While it's nice to think about a world where you always have immediate uses,
you end up with FUD chains if you do that -- with ultimately a tangled nest
of pointers that is bloody impossible to work with in the real world.

jeff

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

[Zdenek Dvorak]

Hello,

>  >> 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.
>  >
>  >But I'm ready to be convinced otherwise.  Say, with an implementation
>  >comparing both approaches with timings over a reasonable code base (a
>  >typical GCC bootstrap or one of the compile-time related PRs).
> IMHO, when we have the need, then we'll expand on the immediate uses
> interface -- either by having a way to incrementally update it, or 
> rebuild it.
> 
> While it's nice to think about a world where you always have immediate uses,
> you end up with FUD chains if you do that -- with ultimately a tangled nest
> of pointers that is bloody impossible to work with in the real world.

why? I have this written and it does not seem very complicated.  I
didn't get to measuring its speed yet, and of course there is unpleasant
memory overhead, but I don't see any other problems.

Zdenek

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

[Zdenek Dvorak]

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.
>  >
>  >But I'm ready to be convinced otherwise.  Say, with an implementation
>  >comparing both approaches with timings over a reasonable code base (a
>  >typical GCC bootstrap or one of the compile-time related PRs).
> IMHO, when we have the need, then we'll expand on the immediate uses
> interface -- either by having a way to incrementally update it, or 
> rebuild it.
> 
> While it's nice to think about a world where you always have immediate uses,
> you end up with FUD chains if you do that -- with ultimately a tangled nest
> of pointers that is bloody impossible to work with in the real world.

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.

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.

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.

Zdenek

Index: Makefile.in
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Makefile.in,v
retrieving revision 1.903.2.153
diff -c -3 -p -r1.903.2.153 Makefile.in
*** Makefile.in	8 Dec 2003 13:52:58 -0000	1.903.2.153
--- Makefile.in	11 Dec 2003 09:00:59 -0000
*************** tree-ssa-dom.o : tree-ssa-dom.c $(TREE_F
*** 1558,1564 ****
     errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
     $(BASIC_BLOCK_H) domwalk.h
  tree-ssanames.o : tree-ssanames.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
!    $(TM_H) $(TREE_H) varray.h $(GGC_H) gt-tree-ssanames.h 
  tree-phinodes.o : tree-phinodes.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
     $(TM_H) $(TREE_H) varray.h $(GGC_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) \
     gt-tree-phinodes.h $(RTL_H)
--- 1558,1564 ----
     errors.h function.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
     $(BASIC_BLOCK_H) domwalk.h
  tree-ssanames.o : tree-ssanames.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
!    $(TM_H) $(TREE_H) varray.h $(GGC_H) gt-tree-ssanames.h tree-flow.h
  tree-phinodes.o : tree-phinodes.c $(CONFIG_H) $(SYSTEM_H) coretypes.h \
     $(TM_H) $(TREE_H) varray.h $(GGC_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) \
     gt-tree-phinodes.h $(RTL_H)
Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.235
diff -c -3 -p -r1.1.4.235 tree-cfg.c
*** tree-cfg.c	11 Dec 2003 01:29:50 -0000	1.1.4.235
--- tree-cfg.c	11 Dec 2003 09:00:59 -0000
*************** void
*** 2446,2452 ****
  bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
  {
    set_bb_for_stmt (t, i->bb);
!   modify_stmt (t);
    tsi_link_before (&i->tsi, t, m);
  }
  
--- 2446,2452 ----
  bsi_insert_before (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
  {
    set_bb_for_stmt (t, i->bb);
!   stmt_added (t);
    tsi_link_before (&i->tsi, t, m);
  }
  
*************** void
*** 2456,2462 ****
  bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
  {
    set_bb_for_stmt (t, i->bb);
!   modify_stmt (t);
    tsi_link_after (&i->tsi, t, m);
  }
  
--- 2456,2462 ----
  bsi_insert_after (block_stmt_iterator *i, tree t, enum bsi_iterator_update m)
  {
    set_bb_for_stmt (t, i->bb);
!   stmt_added (t);
    tsi_link_after (&i->tsi, t, m);
  }
  
*************** bsi_remove (block_stmt_iterator *i)
*** 2468,2474 ****
  {
    tree t = bsi_stmt (*i);
    set_bb_for_stmt (t, NULL);
!   modify_stmt (t);
    tsi_delink (&i->tsi);
  }
  
--- 2468,2474 ----
  {
    tree t = bsi_stmt (*i);
    set_bb_for_stmt (t, NULL);
!   stmt_removed (t);
    tsi_delink (&i->tsi);
  }
  
*************** bsi_replace (const block_stmt_iterator *
*** 2527,2533 ****
      }
  
    *bsi_stmt_ptr (*bsi) = stmt;
!   modify_stmt (stmt);
  }
  
  /* This routine locates a place to insert a statement on an edge.  Every
--- 2527,2533 ----
      }
  
    *bsi_stmt_ptr (*bsi) = stmt;
!   stmt_added (stmt);
  }
  
  /* This routine locates a place to insert a statement on an edge.  Every
Index: tree-dfa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-dfa.c,v
retrieving revision 1.1.4.200
diff -c -3 -p -r1.1.4.200 tree-dfa.c
*** tree-dfa.c	11 Dec 2003 01:27:02 -0000	1.1.4.200
--- tree-dfa.c	11 Dec 2003 09:00:59 -0000
*************** static int dump_flags;
*** 124,129 ****
--- 124,131 ----
  /* Data and functions shared with tree-ssa.c.  */
  struct dfa_stats_d dfa_stats;
  
+ /* A list of statements to rescan.  */
+ varray_type statements_to_rescan;
  
  /* Local functions.  */
  static void note_addressable (tree, stmt_ann_t);
*************** add_use (tree *use_p, tree stmt)
*** 721,726 ****
--- 723,730 ----
      abort ();
  #endif
  
+   add_name_use (*use_p, stmt);
+ 
    if (ann->ops == NULL)
      {
        ann->ops = ggc_alloc (sizeof (struct operands_d));
*************** add_vdef (tree var, tree stmt, voperands
*** 787,792 ****
--- 791,798 ----
        source = var;
      }
  
+   add_name_use (source, stmt);
+ 
    if (ann->vops == NULL)
      {
        ann->vops = ggc_alloc (sizeof (struct voperands_d));
*************** add_vuse (tree var, tree stmt, voperands
*** 849,854 ****
--- 855,862 ----
    if (found)
      var = vuse;
  
+   add_name_use (var, stmt);
+ 
    if (ann->vops == NULL)
      {
        ann->vops = ggc_alloc (sizeof (struct voperands_d));
*************** mark_new_vars_to_rename (tree stmt, bitm
*** 2780,2785 ****
--- 2834,2877 ----
      bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
  
    BITMAP_XFREE (vars_in_vops_to_rename);
+ }
+ 
+ /* Record the statement STMT to a list of statements to rescan.  */
+ 
+ void
+ record_modified_stmt (tree stmt)
+ {
+   if (!statements_to_rescan)
+     VARRAY_TREE_INIT (statements_to_rescan, 1000, "statements_to_rescan");
+ 
+   VARRAY_PUSH_TREE (statements_to_rescan, stmt);
+ }
+ 
+ /* Rescan operands of all the modified statements.  */
+ 
+ void
+ rescan_modified_stmts (void)
+ {
+   unsigned i;
+   tree stmt;
+   stmt_ann_t ann;
+ 
+   if (!statements_to_rescan)
+     return;
+ 
+   for (i = 0; i < VARRAY_ACTIVE_SIZE (statements_to_rescan); i++)
+     {
+       stmt = VARRAY_TREE (statements_to_rescan, i);
+       VARRAY_TREE (statements_to_rescan, i) = NULL_TREE;
+ 
+       ann = stmt_ann (stmt);
+       if (ann && ann->removed)
+ 	continue;
+ 
+       get_stmt_operands (stmt);
+     }
+ 
+   VARRAY_POP_ALL (statements_to_rescan);
  }
  
  #include "gt-tree-dfa.h"
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow-inline.h,v
retrieving revision 1.1.2.61
diff -c -3 -p -r1.1.2.61 tree-flow-inline.h
*** tree-flow-inline.h	8 Dec 2003 12:58:22 -0000	1.1.2.61
--- tree-flow-inline.h	11 Dec 2003 09:00:59 -0000
*************** get_filename (tree expr)
*** 170,181 ****
--- 170,208 ----
  }
  
  static inline void
+ stmt_removed (tree t)
+ {
+   stmt_ann_t ann = stmt_ann (t);
+   if (ann)
+     {
+       ann->modified = 1;
+       ann->removed = 1;
+       if (ann->name_uses)
+ 	remove_stmt_uses (t);
+     }
+ }
+ 
+ static inline void
  modify_stmt (tree t)
  {
    stmt_ann_t ann = stmt_ann (t);
    if (ann == NULL)
      ann = create_stmt_ann (t);
+   if (!ann->modified)
+     record_modified_stmt (t);
    ann->modified = 1;
+   if (ann->name_uses)
+     remove_stmt_uses (t);
+ }
+ 
+ static inline void
+ stmt_added (tree t)
+ {
+   stmt_ann_t ann;
+   modify_stmt (t);
+ 
+   ann = stmt_ann (t);
+   ann->removed = 0;
  }
  
  static inline void
Index: tree-flow.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow.h,v
retrieving revision 1.1.4.167
diff -c -3 -p -r1.1.4.167 tree-flow.h
*** tree-flow.h	8 Dec 2003 12:58:22 -0000	1.1.4.167
--- tree-flow.h	11 Dec 2003 09:00:59 -0000
*************** struct stmt_ann_d GTY(())
*** 221,226 ****
--- 221,229 ----
       need to be scanned again).  */
    unsigned modified : 1;
  
+   /* Nonzero if the statement has been removed.  */
+   unsigned removed : 1;
+ 
    /* Nonzero if the statement is in the CCP worklist and has not been
       "cancelled".  If we ever need to use this bit outside CCP, then
       it should be renamed.  */
*************** struct stmt_ann_d GTY(())
*** 248,253 ****
--- 251,259 ----
    /* Virtual operands (VDEF and VUSE).  */
    voperands_t vops;
  
+   /* A list of ssa names uses in the statement.  */
+   struct ssa_name_use *name_uses;
+ 
    /* Dataflow information.  */
    dataflow_t df;
  
*************** static inline enum tree_ann_type ann_typ
*** 275,280 ****
--- 281,288 ----
  static inline basic_block bb_for_stmt (tree);
  extern void set_bb_for_stmt (tree, basic_block);
  static inline void modify_stmt (tree);
+ static inline void stmt_removed (tree);
+ static inline void stmt_added (tree);
  static inline void unmodify_stmt (tree);
  static inline bool stmt_modified_p (tree);
  static inline varray_type may_aliases (tree);
*************** extern GTY(()) varray_type call_clobbere
*** 362,367 ****
--- 370,377 ----
  
  #define PERCENT(x,y) ((float)(x) * 100.0 / (float)(y))
  
+ /* A list of statements to rescan.  */
+ extern GTY(()) varray_type statements_to_rescan;
  
  /*---------------------------------------------------------------------------
  			      Block iterators
*************** extern stmt_ann_t create_stmt_ann (tree)
*** 461,466 ****
--- 471,477 ----
  extern tree create_phi_node (tree, basic_block);
  extern void add_phi_arg (tree *, tree, edge);
  extern void remove_phi_arg (tree, basic_block);
+ extern void replace_phi_arg_num (tree, int, tree);
  extern void remove_phi_arg_num (tree, int);
  extern void remove_phi_node (tree, tree, basic_block);
  extern void remove_all_phi_nodes_for (bitmap);
*************** extern void add_vuse (tree, tree, vopera
*** 489,494 ****
--- 501,508 ----
  extern void create_global_var (void);
  extern void add_referenced_tmp_var (tree var);
  extern void mark_new_vars_to_rename (tree, bitmap);
+ extern void record_modified_stmt (tree);
+ extern void rescan_modified_stmts (void);
  
  /* Flags used when computing reaching definitions and reached uses.  */
  #define TDFA_USE_OPS		1 << 0
Index: tree-optimize.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-optimize.c,v
retrieving revision 1.1.4.92
diff -c -3 -p -r1.1.4.92 tree-optimize.c
*** tree-optimize.c	9 Dec 2003 15:39:11 -0000	1.1.4.92
--- tree-optimize.c	11 Dec 2003 09:00:59 -0000
*************** optimize_function_tree (tree fndecl, tre
*** 122,127 ****
--- 122,129 ----
  	  if (bitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_2);
  
+ 	  rescan_modified_stmts ();
+ 
  #ifdef ENABLE_CHECKING
  	  verify_ssa ();
  #endif
*************** optimize_function_tree (tree fndecl, tre
*** 157,162 ****
--- 159,166 ----
  	  /* Run the SSA pass again if we need to rename new variables.  */
  	  if (bitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_3);
+ 
+ 	  rescan_modified_stmts ();
            ggc_collect ();
  
  #ifdef ENABLE_CHECKING
*************** optimize_function_tree (tree fndecl, tre
*** 166,171 ****
--- 170,176 ----
  
        /* Eliminate tail recursion calls.  */
        tree_optimize_tail_calls ();
+       rescan_modified_stmts ();
  
  #ifdef ENABLE_CHECKING
        verify_ssa ();
*************** optimize_function_tree (tree fndecl, tre
*** 180,185 ****
--- 185,192 ----
  	  /* Run the SSA pass again if we need to rename new variables.  */
  	  if (bitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_4);
+ 
+ 	  rescan_modified_stmts ();
            ggc_collect ();
  
  #ifdef ENABLE_CHECKING
*************** optimize_function_tree (tree fndecl, tre
*** 196,201 ****
--- 203,209 ----
  	  /* Run the SSA pass again if we need to rename new variables.  */
  	  if (bitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_5);
+ 	  rescan_modified_stmts ();
            ggc_collect ();
  
  #ifdef ENABLE_CHECKING
*************** optimize_function_tree (tree fndecl, tre
*** 207,212 ****
--- 215,221 ----
        if (flag_tree_pre)
  	{
  	  tree_perform_ssapre (fndecl, TDI_pre);
+ 	  rescan_modified_stmts ();
  	  ggc_collect ();
  
  #ifdef ENABLE_CHECKING
*************** optimize_function_tree (tree fndecl, tre
*** 224,229 ****
--- 233,239 ----
  	  if (bitmap_first_set_bit (vars_to_rename) >= 0)
  	    rewrite_into_ssa (fndecl, vars_to_rename, TDI_ssa_6);
  
+ 	  rescan_modified_stmts ();
  #ifdef ENABLE_CHECKING
  	  verify_ssa ();
  #endif
*************** optimize_function_tree (tree fndecl, tre
*** 245,250 ****
--- 255,261 ----
        tree_optimize_tail_calls (true, TDI_tail2);
  #endif
  
+       rescan_modified_stmts ();
  #ifdef ENABLE_CHECKING
        verify_flow_info ();
        verify_stmts ();
Index: tree-phinodes.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-phinodes.c,v
retrieving revision 1.1.2.8
diff -c -3 -p -r1.1.2.8 tree-phinodes.c
*** tree-phinodes.c	8 Dec 2003 12:58:22 -0000	1.1.2.8
--- tree-phinodes.c	11 Dec 2003 09:00:59 -0000
*************** release_phi_node (tree phi)
*** 218,223 ****
--- 218,224 ----
    int bucket;
    int len = PHI_ARG_CAPACITY (phi);
  
+   remove_stmt_uses (phi);
    bucket = len > NUM_BUCKETS - 1 ? NUM_BUCKETS - 1 : len;
    bucket -= 2;
    TREE_CHAIN (phi) = free_phinodes[bucket];
*************** resize_phi_node (tree *phi, int len)
*** 234,245 ****
    int size, old_size;
    tree new_phi;
    int i, old_len, bucket = NUM_BUCKETS - 2;
!                                                                                 
  #ifdef ENABLE_CHECKING
    if (len < PHI_ARG_CAPACITY (*phi))
      abort ();
  #endif
!                                                                                 
    size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d);
  
    if (free_phinode_count)
--- 235,246 ----
    int size, old_size;
    tree new_phi;
    int i, old_len, bucket = NUM_BUCKETS - 2;
! 
  #ifdef ENABLE_CHECKING
    if (len < PHI_ARG_CAPACITY (*phi))
      abort ();
  #endif
! 
    size = sizeof (struct tree_phi_node) + (len - 1) * sizeof (struct phi_arg_d);
  
    if (free_phinode_count)
*************** resize_phi_node (tree *phi, int len)
*** 273,285 ****
  
    old_len = PHI_ARG_CAPACITY (new_phi);
    PHI_ARG_CAPACITY (new_phi) = len;
!                                                                                 
!   for (i = old_len; i < len; i++)
      {
        PHI_ARG_DEF (new_phi, i) = NULL_TREE;
        PHI_ARG_EDGE (new_phi, i) = NULL;
      }
!                                                                                 
    *phi = new_phi;
  }
  
--- 274,294 ----
  
    old_len = PHI_ARG_CAPACITY (new_phi);
    PHI_ARG_CAPACITY (new_phi) = len;
! 
!   for (i = 0; i < old_len; i++)
!     if (PHI_ARG_USE (new_phi, i))
!       {
! 	PHI_ARG_USE (new_phi, i)->stmt = new_phi;
! 	PHI_ARG_USE (*phi, i) = NULL;
!       }
! 
!   for (; i < len; i++)
      {
        PHI_ARG_DEF (new_phi, i) = NULL_TREE;
        PHI_ARG_EDGE (new_phi, i) = NULL;
+       PHI_ARG_USE (new_phi, i) = NULL;
      }
! 
    *phi = new_phi;
  }
  
*************** add_phi_arg (tree *phi, tree def, edge e
*** 362,367 ****
--- 371,378 ----
        SSA_NAME_OCCURS_IN_ABNORMAL_PHI (PHI_RESULT (*phi)) = 1;
      }
  
+   PHI_ARG_USE (*phi, i) = add_name_use (def, *phi);
+ 
    PHI_ARG_DEF (*phi, i) = def;
    PHI_ARG_EDGE (*phi, i) = e;
    PHI_NUM_ARGS (*phi)++;
*************** remove_phi_arg (tree phi, basic_block bl
*** 389,394 ****
--- 400,418 ----
      }
  }
  
+ /* Replace the Ith arg of PHI by VAL.  */
+ 
+ void
+ replace_phi_arg_num (tree phi, int i, tree val)
+ {
+   remove_phi_arg_use (phi, i);
+   PHI_ARG_USE (phi, i) = add_name_use (val, phi);
+   if (TREE_CODE (val) == SSA_NAME
+       && TREE_CODE (PHI_ARG_DEF (phi, i)) == SSA_NAME)
+     propagate_copy (&PHI_ARG_DEF (phi, i), val);
+   else
+     PHI_ARG_DEF (phi, i) = val;
+ }
  
  /* Remove the Ith argument from PHI's argument list.  This routine assumes
     ordering of alternatives in the vector is not important and implements
*************** remove_phi_arg_num (tree phi, int i)
*** 400,416 ****
--- 424,444 ----
  {
    int num_elem = PHI_NUM_ARGS (phi);
  
+   remove_phi_arg_use (phi, i);
+ 
    /* If we are not at the last element, switch the last element
       with the element we want to delete.  */
    if (i != num_elem - 1)
      {
        PHI_ARG_DEF (phi, i) = PHI_ARG_DEF (phi, num_elem - 1);
        PHI_ARG_EDGE (phi, i) = PHI_ARG_EDGE (phi, num_elem - 1);
+       PHI_ARG_USE (phi, i) = PHI_ARG_USE (phi, num_elem - 1);
      }
  
    /* Shrink the vector and return.  */
    PHI_ARG_DEF (phi, num_elem - 1) = NULL_TREE;
    PHI_ARG_EDGE (phi, num_elem - 1) = NULL;
+   PHI_ARG_USE (phi, num_elem - 1) = NULL;
    PHI_NUM_ARGS (phi)--;
  
    /* If we removed the last PHI argument, then go ahead and
Index: tree-ssa-ccp.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-ccp.c,v
retrieving revision 1.1.2.123
diff -c -3 -p -r1.1.2.123 tree-ssa-ccp.c
*** tree-ssa-ccp.c	10 Dec 2003 21:43:52 -0000	1.1.2.123
--- tree-ssa-ccp.c	11 Dec 2003 09:00:59 -0000
*************** substitute_and_fold (bitmap vars_to_rena
*** 344,358 ****
  	  for (i = 0; i < PHI_NUM_ARGS (phi); i++)
  	    {
  	      value *new_val;
! 	      tree *orig_p = &PHI_ARG_DEF (phi, i);
  
! 	      if (! SSA_VAR_P (*orig_p))
  		break;
  
! 	      new_val = get_value (*orig_p);
  	      if (new_val->lattice_val == CONSTANT
! 		  && may_propagate_copy (*orig_p, new_val->const_val))
! 		*orig_p = new_val->const_val;
  	    }
  	}
  
--- 344,358 ----
  	  for (i = 0; i < PHI_NUM_ARGS (phi); i++)
  	    {
  	      value *new_val;
! 	      tree orig = PHI_ARG_DEF (phi, i);
  
! 	      if (! SSA_VAR_P (orig))
  		break;
  
! 	      new_val = get_value (orig);
  	      if (new_val->lattice_val == CONSTANT
! 		  && may_propagate_copy (orig, new_val->const_val))
! 		replace_phi_arg_num (phi, i, new_val->const_val);
  	    }
  	}
  
Index: tree-ssa-dom.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa-dom.c,v
retrieving revision 1.1.2.93
diff -c -3 -p -r1.1.2.93 tree-ssa-dom.c
*** tree-ssa-dom.c	11 Dec 2003 01:29:50 -0000	1.1.2.93
--- tree-ssa-dom.c	11 Dec 2003 09:00:59 -0000
*************** cprop_into_phis (struct dom_walk_data *w
*** 1989,1995 ****
  	{
  	  int i;
  	  tree new;
! 	  tree *orig_p;
  
  	  /* If the hint is valid (!= phi_num_args), see if it points
  	     us to the desired phi alternative.  */
--- 1989,1995 ----
  	{
  	  int i;
  	  tree new;
! 	  tree orig;
  
  	  /* If the hint is valid (!= phi_num_args), see if it points
  	     us to the desired phi alternative.  */
*************** cprop_into_phis (struct dom_walk_data *w
*** 2015,2032 ****
  
  	  /* The alternative may be associated with a constant, so verify
  	     it is an SSA_NAME before doing anything with it.  */
! 	  orig_p = &PHI_ARG_DEF (phi, hint);
! 	  if (TREE_CODE (*orig_p) != SSA_NAME)
  	    continue;
  
  	  /* If we have *ORIG_P in our constant/copy table, then replace
  	     ORIG_P with its value in our constant/copy table.  */
! 	  new = get_value_for (*orig_p, const_and_copies);
  	  if (new
  	      && (TREE_CODE (new) == SSA_NAME
  		  || is_gimple_min_invariant (new))
! 	      && may_propagate_copy (*orig_p, new))
! 	    propagate_value (orig_p, new);
  	}
      }
  }
--- 2015,2032 ----
  
  	  /* The alternative may be associated with a constant, so verify
  	     it is an SSA_NAME before doing anything with it.  */
! 	  orig = PHI_ARG_DEF (phi, hint);
! 	  if (TREE_CODE (orig) != SSA_NAME)
  	    continue;
  
  	  /* If we have *ORIG_P in our constant/copy table, then replace
  	     ORIG_P with its value in our constant/copy table.  */
! 	  new = get_value_for (orig, const_and_copies);
  	  if (new
  	      && (TREE_CODE (new) == SSA_NAME
  		  || is_gimple_min_invariant (new))
! 	      && may_propagate_copy (orig, new))
! 	    replace_phi_arg_num (phi, hint, new);
  	}
      }
  }
*************** record_equivalences_from_stmt (tree stmt
*** 2248,2253 ****
--- 2248,2257 ----
  	      tree op = VDEF_RESULT (vdefs, j);
  	      add_vuse (op, new, NULL);
  	    }
+ 
+ 	  /* Forget the statement uses; if we ever use it anywhere, they will
+ 	     be rescanned anyway.  */
+ 	  remove_stmt_uses (new);
  
  	  /* Finally enter the statement into the available expression
  	     table.  */
Index: tree-ssa.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssa.c,v
retrieving revision 1.1.4.174
diff -c -3 -p -r1.1.4.174 tree-ssa.c
*** tree-ssa.c	5 Dec 2003 23:02:24 -0000	1.1.4.174
--- tree-ssa.c	11 Dec 2003 09:01:00 -0000
*************** static void set_livein_block (tree, basi
*** 187,193 ****
  static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
  static void insert_phi_nodes (bitmap *);
  static void rewrite_stmt (block_stmt_iterator, varray_type *);
! static inline void rewrite_operand (tree *);
  static void register_new_def (tree, tree, varray_type *);
  static void insert_phi_nodes_for (tree, bitmap *);
  static tree get_reaching_def (tree);
--- 187,193 ----
  static bool prepare_operand_for_rename (tree *op_p, size_t *uid_p);
  static void insert_phi_nodes (bitmap *);
  static void rewrite_stmt (block_stmt_iterator, varray_type *);
! static inline void rewrite_operand (tree *, tree);
  static void register_new_def (tree, tree, varray_type *);
  static void insert_phi_nodes_for (tree, bitmap *);
  static tree get_reaching_def (tree);
*************** rewrite_stmt (block_stmt_iterator si, va
*** 3194,3204 ****
  
    /* Step 1.  Rewrite USES and VUSES in the statement.  */
    for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)
!     rewrite_operand (VARRAY_TREE_PTR (uses, i));
  
    /* Rewrite virtual uses in the statement.  */
    for (i = 0; vuses && i < VARRAY_ACTIVE_SIZE (vuses); i++)
!     rewrite_operand (&VARRAY_TREE (vuses, i));
  
    /* Step 2.  Register the statement's DEF and VDEF operands.  */
    for (i = 0; defs && i < VARRAY_ACTIVE_SIZE (defs); i++)
--- 3194,3204 ----
  
    /* Step 1.  Rewrite USES and VUSES in the statement.  */
    for (i = 0; uses && i < VARRAY_ACTIVE_SIZE (uses); i++)
!     rewrite_operand (VARRAY_TREE_PTR (uses, i), stmt);
  
    /* Rewrite virtual uses in the statement.  */
    for (i = 0; vuses && i < VARRAY_ACTIVE_SIZE (vuses); i++)
!     rewrite_operand (&VARRAY_TREE (vuses, i), stmt);
  
    /* Step 2.  Register the statement's DEF and VDEF operands.  */
    for (i = 0; defs && i < VARRAY_ACTIVE_SIZE (defs); i++)
*************** rewrite_stmt (block_stmt_iterator si, va
*** 3216,3222 ****
    /* Register new virtual definitions made by the statement.  */
    for (i = 0; vdefs && i < NUM_VDEFS (vdefs); i++)
      {
!       rewrite_operand (&(VDEF_OP (vdefs, i)));
  
        if (TREE_CODE (VDEF_RESULT (vdefs, i)) != SSA_NAME)
  	VDEF_RESULT (vdefs, i) = make_ssa_name (VDEF_RESULT (vdefs, i), stmt);
--- 3216,3222 ----
    /* Register new virtual definitions made by the statement.  */
    for (i = 0; vdefs && i < NUM_VDEFS (vdefs); i++)
      {
!       rewrite_operand (&(VDEF_OP (vdefs, i)), stmt);
  
        if (TREE_CODE (VDEF_RESULT (vdefs, i)) != SSA_NAME)
  	VDEF_RESULT (vdefs, i) = make_ssa_name (VDEF_RESULT (vdefs, i), stmt);
*************** set_is_used (tree t)
*** 3240,3252 ****
  
  
  /* Replace the operand pointed by OP_P with its immediate reaching
!    definition.  */
  
  static inline void
! rewrite_operand (tree *op_p)
  {
    if (TREE_CODE (*op_p) != SSA_NAME)
!     *op_p = get_reaching_def (*op_p);
  }
  
  
--- 3240,3255 ----
  
  
  /* Replace the operand pointed by OP_P with its immediate reaching
!    definition in STMT.  */
  
  static inline void
! rewrite_operand (tree *op_p, tree stmt)
  {
    if (TREE_CODE (*op_p) != SSA_NAME)
!     {
!       *op_p = get_reaching_def (*op_p);
!       add_name_use (*op_p, stmt);
!     }
  }
  
  
*************** delete_tree_ssa (void)
*** 3314,3319 ****
--- 3317,3324 ----
  	referenced_var (i)->common.ann = NULL;
        referenced_vars = NULL;
      }
+ 
+   statements_to_rescan = NULL;
  
    fini_ssanames ();
    fini_phinodes ();
Index: tree-ssanames.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-ssanames.c,v
retrieving revision 1.1.2.6
diff -c -3 -p -r1.1.2.6 tree-ssanames.c
*** tree-ssanames.c	1 Dec 2003 22:15:15 -0000	1.1.2.6
--- tree-ssanames.c	11 Dec 2003 09:01:00 -0000
*************** Boston, MA 02111-1307, USA.  */
*** 24,29 ****
--- 24,30 ----
  #include "tm.h"
  #include "tree.h"
  #include "varray.h"
+ #include "tree-flow.h"
  #include "ggc.h"
  
  /* Rewriting a function into SSA form can create a huge number of SSA_NAMEs,
*************** unsigned int highest_ssa_version;
*** 64,69 ****
--- 65,74 ----
     after we leave SSA form.  */
  static GTY (()) tree free_ssanames;
  
+ /* Free list of SSA_NAME use occurences.  Linked through next_stmt_use
+    field. */
+ static GTY(()) struct ssa_name_use *free_name_uses;
+ 
  /* Version numbers with special meanings.  We start allocating new version
     numbers after the special ones.  */
  #define UNUSED_NAME_VERSION 0
*************** init_ssanames (void)
*** 80,85 ****
--- 85,91 ----
  {
    highest_ssa_version = UNUSED_NAME_VERSION + 1;
    free_ssanames = NULL;
+   free_name_uses = NULL;
  }
  
  /* Finalize management of SSA_NAMEs.  */
*************** void
*** 88,93 ****
--- 94,100 ----
  fini_ssanames (void)
  {
    free_ssanames = NULL;
+   free_name_uses = NULL;
  }
  
  /* Dump some simple statistics regarding the re-use of SSA_NAME nodes.  */
*************** make_ssa_name (tree var, tree stmt)
*** 151,156 ****
--- 158,165 ----
    TREE_TYPE (t) = TREE_TYPE (var);
    SSA_NAME_VAR (t) = var;
    SSA_NAME_DEF_STMT (t) = stmt;
+   SSA_NAME_USES (t)->next_name_use = SSA_NAME_USES (t);
+   SSA_NAME_USES (t)->prev_name_use = SSA_NAME_USES (t);
  
    return t;
  }
*************** release_ssa_name (tree var)
*** 179,184 ****
--- 188,286 ----
        TREE_CHAIN (var) = free_ssanames;
        free_ssanames = var;
      }
+ }
+ 
+ /* Add a record of using the ssa name NAME in the statement STMT.  */
+ 
+ struct ssa_name_use *
+ add_name_use (tree name, tree stmt)
+ {
+   struct ssa_name_use *use;
+   stmt_ann_t ann;
+ 
+   if (TREE_CODE (name) != SSA_NAME)
+     return NULL;
+ 
+   if (free_name_uses)
+     {
+       use = free_name_uses;
+       free_name_uses = free_name_uses->next_name_use;
+     }
+   else
+     use = ggc_alloc (sizeof (struct ssa_name_use));
+ 
+   use->stmt = stmt;
+   use->next_name_use = SSA_NAME_USES (name)->next_name_use;
+   use->prev_name_use = SSA_NAME_USES (name);
+   use->next_name_use->prev_name_use = use;
+   use->prev_name_use->next_name_use = use;
+ 
+   if (TREE_CODE (stmt) == PHI_NODE)
+     use->next_stmt_use = NULL;
+   else
+     {
+       ann = stmt_ann (stmt);
+       use->next_stmt_use = ann->name_uses;
+       ann->name_uses = use;
+     }
+ 
+   return use;
+ }
+ 
+ /* Remove the USE from the list of uses of the variable.  */
+ static void
+ remove_stmt_use (struct ssa_name_use *use)
+ {
+   struct ssa_name_use *next = use->next_name_use, *prev = use->prev_name_use;
+ 
+   next->prev_name_use = prev;
+   prev->next_name_use = next;
+   use->stmt = NULL_TREE;
+   use->prev_name_use = use->next_name_use = NULL;
+ }
+ 
+ /* Remove records of use of the i-th arg of the PHI node.  */
+ 
+ void
+ remove_phi_arg_use (tree phi, int i)
+ {
+   struct ssa_name_use *use = PHI_ARG_USE (phi, i);
+ 
+   if (!use)
+     return;
+ 
+   remove_stmt_use (use);
+   use->next_stmt_use = free_name_uses;
+   free_name_uses = use;
+   PHI_ARG_USE (phi, i) = NULL;
+ }
+ 
+ /* Remove records of uses in the statement STMT.  */
+ 
+ void
+ remove_stmt_uses (tree stmt)
+ {
+   struct ssa_name_use **use, **w;
+   stmt_ann_t ann;
+   int i;
+   
+   if (TREE_CODE (stmt) == PHI_NODE)
+     {
+       for (i = 0; i < PHI_NUM_ARGS (stmt); i++)
+ 	remove_phi_arg_use (stmt, i);
+ 
+       return;
+     }
+       
+   ann = stmt_ann (stmt);
+   w = &ann->name_uses;
+ 
+   for (use = w; *use; use = &(*use)->next_stmt_use)
+     remove_stmt_use (*use);
+ 
+   *use = free_name_uses;
+   free_name_uses = *w;
+   *w = NULL;
  }
  
  #include "gt-tree-ssanames.h"
Index: tree.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree.h,v
retrieving revision 1.342.2.150
diff -c -3 -p -r1.342.2.150 tree.h
*** tree.h	8 Dec 2003 20:29:26 -0000	1.342.2.150
--- tree.h	11 Dec 2003 09:01:00 -0000
*************** struct tree_exp GTY(())
*** 1021,1027 ****
  
  /* Returns the variable being referenced.  Once released, this is the
     only field that can be relied upon.  */
! #define SSA_NAME_VAR(NODE)	SSA_NAME_CHECK (NODE)->ssa_name.var
  
  /* Returns the statement which defines this reference.   Note that
     we use the same field when chaining SSA_NAME nodes together on
--- 1021,1027 ----
  
  /* Returns the variable being referenced.  Once released, this is the
     only field that can be relied upon.  */
! #define SSA_NAME_VAR(NODE)	SSA_NAME_CHECK (NODE)->ssa_name.uses.stmt
  
  /* Returns the statement which defines this reference.   Note that
     we use the same field when chaining SSA_NAME nodes together on
*************** struct tree_exp GTY(())
*** 1032,1037 ****
--- 1032,1040 ----
     tree SSA, version numbers are not per variable and may be recycled.  */
  #define SSA_NAME_VERSION(NODE)	SSA_NAME_CHECK (NODE)->ssa_name.version
  
+ /* Returns the list of uses of the SSA name.  */
+ #define SSA_NAME_USES(NODE) (&SSA_NAME_CHECK (NODE)->ssa_name.uses)
+ 
  /* Nonzero if this SSA name occurs in an abnormal PHI.  SSA_NAMES are
     never output, so we can safely use the ASM_WRITTEN_FLAG for this
     status bit.  */
*************** struct tree_exp GTY(())
*** 1044,1058 ****
  #define SSA_NAME_IN_FREE_LIST(NODE) \
      SSA_NAME_CHECK (NODE)->common.nothrow_flag
  
  struct tree_ssa_name GTY(())
  {
    struct tree_common common;
  
-   /* _DECL wrapped by this SSA name.  */
-   tree var;
- 
    /* SSA version number.  */
    unsigned int version;
  };
  \f
  /* In a PHI_NODE node.  */
--- 1047,1082 ----
  #define SSA_NAME_IN_FREE_LIST(NODE) \
      SSA_NAME_CHECK (NODE)->common.nothrow_flag
  
+ /* The instance of the use of the SSA name.  They are linked in two list;
+    one of them is a list of uses in the same statement, the second one
+    is the list of uses of the SSA name.  The second list is double cyclic
+    list with a head. To conserve a few bytes of memory, the head has STMT set
+    to the _DECL the SSA name is based on.  */
+ struct ssa_name_use GTY(())
+ {
+   /* Statement in that the SSA name is used.  */
+   tree stmt;
+ 
+   /* Next and previous use of the same SSA name in the linked list of all
+      uses.  The `skip' here is so that we may let it point to a non-ggc
+      allocated head; next_stmt_use list is sufficient to keep the reference
+      alive as long as we need it.  */
+   struct ssa_name_use * GTY((skip (""))) next_name_use;
+   struct ssa_name_use * GTY((skip (""))) prev_name_use;
+ 
+   /* Entry for a next SSA name used in the STMT.  */
+   struct ssa_name_use *next_stmt_use;
+ };
+ 
  struct tree_ssa_name GTY(())
  {
    struct tree_common common;
  
    /* SSA version number.  */
    unsigned int version;
+ 
+   /* A list of SSA name uses.  */
+   struct ssa_name_use uses;
  };
  \f
  /* In a PHI_NODE node.  */
*************** struct tree_ssa_name GTY(())
*** 1066,1071 ****
--- 1090,1096 ----
  #define PHI_ARG_ELT(NODE, I)	PHI_NODE_ELT_CHECK (NODE, I)
  #define PHI_ARG_EDGE(NODE, I)	PHI_NODE_ELT_CHECK (NODE, I).e
  #define PHI_ARG_DEF(NODE, I)	PHI_NODE_ELT_CHECK (NODE, I).def
+ #define PHI_ARG_USE(NODE, I)	PHI_NODE_ELT_CHECK (NODE, I).use
  
  struct edge_def;
  
*************** struct phi_arg_d GTY(())
*** 1073,1078 ****
--- 1098,1106 ----
  {
    tree def;
    struct edge_def * GTY((skip (""))) e;
+ 
+   /* SSA name use.  */
+   struct ssa_name_use *use;
  };
  
  struct tree_phi_node GTY(())
*************** extern void release_ssa_name (tree);
*** 2564,2569 ****
--- 2592,2601 ----
  #ifdef GATHER_STATISTICS
  extern void ssanames_print_statistics (void);
  #endif
+ 
+ extern struct ssa_name_use *add_name_use (tree, tree);
+ extern void remove_stmt_uses (tree);
+ extern void remove_phi_arg_use (tree, int);
  
  /* Return the (unique) IDENTIFIER_NODE node for a given name.
     The name is supplied as a char *.  */

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

[Andrew MacLeod]

On Thu, 2003-12-11 at 17:30, Zdenek Dvorak wrote:
> Hello,
> 
>
> > While it's nice to think about a world where you always have immediate uses,
> > you end up with FUD chains if you do that -- with ultimately a tangled nest
> > of pointers that is bloody impossible to work with in the real world.
> 
> 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.

More interesting is the time effectit has on larger C++ cases like
Geralds where we already have memory problem we are trying to resolve.
Thats where it was a significant issue for CCP in the system swap time.

Andrew

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

[Andrew MacLeod]

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

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

[Zdenek Dvorak]

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.

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

Zdenek

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

[Andrew MacLeod]

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

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

[Zdenek Dvorak]

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

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

[Andrew MacLeod]

On Mon, 2003-12-15 at 16:03, Zdenek Dvorak wrote:

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

We'll get back to this part later :-)

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

I dont see why. If you want to track just a few variables,  why should
you pay for tracking 45,000?  It'll be a lot cheaper just to track the
ones you want.  Thats not to say one wouldn't want all the information
sometimes, but I can assure you that in CCP we dont want the info for
all variables or you get more slowdown.

Now, it may turn out that we get a reasonably efficient implemnation
evetually it wont be an issue, but it will be an issue for the
forseeable near future I think.

You may find the same thing when doing loop optimizations that you only
want the info for the loop you are working on.

In any case, it simple enough to provide it this way now, and if it ever
becomes an all-or-nothing implementation, we simply dont look at the
argument to the call.


Actually, come to think of it, you ought to never merge blocks if there
is *any* phi node. If we do implement immediate_uses, then when we
remove the PHi argument which reduces the PHI to a single argument, we
will also remove the PHI at the same time using the uses info, so you
will never see a PHI with a single argument if the inforamtion is
available. If it isn't available, you are going to punt and not do the
merge anyway.  So if you see a PHI, punt.


Andrew

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

[Zdenek Dvorak]

Hello,

> > > 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.
> > 
> 
> I dont see why. If you want to track just a few variables,  why should
> you pay for tracking 45,000?

because you generally don't know which variables you are interested in.
Also chosing the different ones in the different passes requieres
recomputing the information, and it is not at all obvious to me whether
this would not make this actually more expensive.

> Now, it may turn out that we get a reasonably efficient implemnation
> evetually it wont be an issue, but it will be an issue for the
> forseeable near future I think.

I am not sure whether this is not saving on the wrong place.  You need
some 12 bytes per operand (perhaps 8, with some extra effort), which
seems incomparable to the amount of memory we waste everywhere else.

> Actually, come to think of it, you ought to never merge blocks if there
> is *any* phi node. If we do implement immediate_uses, then when we
> remove the PHi argument which reduces the PHI to a single argument, we
> will also remove the PHI at the same time using the uses info, so you
> will never see a PHI with a single argument if the inforamtion is
> available. If it isn't available, you are going to punt and not do the
> merge anyway.  So if you see a PHI, punt.

Yes, this would be cool (and actually a great argument for keeping the
immediate uses of all variables up-to-date at all times :-)

Zdenek

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

[Andrew MacLeod]

On Mon, 2003-12-15 at 16:47, Zdenek Dvorak wrote:
> Hello,
> 
> > > > 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.
> > > 
> > 
> > I dont see why. If you want to track just a few variables,  why should
> > you pay for tracking 45,000?
> 
> because you generally don't know which variables you are interested in.
> Also chosing the different ones in the different passes requieres
> recomputing the information, and it is not at all obvious to me whether
> this would not make this actually more expensive.
> 

I guess it depends on how hard it is to find out. CCP goes and
determines an initial value for every variable. If the initial value is
something we already know cannot be a constant, we dont include it. THis
was very significant for virtual PHI nodes, since that means they never
got included,so we save a lot on those 2000 element phi nodes.

Typically, you'd have to do something like zip though all the operands
of the stmt s in blocks you are about to deal with, and add them to the
list. Zipping through the stms looking at operands it extremely quick.

> > Now, it may turn out that we get a reasonably efficient implemnation
> > evetually it wont be an issue, but it will be an issue for the
> > forseeable near future I think.
> 
> I am not sure whether this is not saving on the wrong place.  You need
> some 12 bytes per operand (perhaps 8, with some extra effort), which
> seems incomparable to the amount of memory we waste everywhere else.

It may be suprising, but you end up with PHIs which have 2000 operands,
and they reach 40 different places.. it does both consume a reasonable
amount of memory, and it takes measurable amounts of time to build the
additional information.

To take a step back, this was quite a while ago before we did some of
our recent wonderful memory work. I will look at it again, and see if
its still nasty. You can give it a quick try yourself. the function
  need_imm_uses_for
in tree-ssa-ccp, change it to return true all the time, and see what the
compilation time difference for gerald testcase is. It use to increase
CCPs time as well as overall time noticably. Perhaps it doesn't now, I
havent tried it lately.

> 
> > Actually, come to think of it, you ought to never merge blocks if there
> > is *any* phi node. If we do implement immediate_uses, then when we
> > remove the PHi argument which reduces the PHI to a single argument, we
> > will also remove the PHI at the same time using the uses info, so you
> > will never see a PHI with a single argument if the inforamtion is
> > available. If it isn't available, you are going to punt and not do the
> > merge anyway.  So if you see a PHI, punt.
> 
> Yes, this would be cool (and actually a great argument for keeping the
> immediate uses of all variables up-to-date at all times :-)

:-) I know, but I dont think it actually happens frequeently enough, and
with enough impact to make it worth carrying immediate uses unless it
gets a lot more efficient :-)



Andrew

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

[law]

In message <1071525828.3257.1907.camel@p4>, Andrew MacLeod writes:
 >I guess it depends on how hard it is to find out. CCP goes and
 >determines an initial value for every variable. If the initial value is
 >something we already know cannot be a constant, we dont include it. THis
 >was very significant for virtual PHI nodes, since that means they never
 >got included,so we save a lot on those 2000 element phi nodes.
Right.

 >> I am not sure whether this is not saving on the wrong place.  You need
 >> some 12 bytes per operand (perhaps 8, with some extra effort), which
 >> seems incomparable to the amount of memory we waste everywhere else.
 >
 >It may be suprising, but you end up with PHIs which have 2000 operands,
 >and they reach 40 different places.. it does both consume a reasonable
 >amount of memory, and it takes measurable amounts of time to build the
 >additional information.
 >
 >To take a step back, this was quite a while ago before we did some of
 >our recent wonderful memory work. I will look at it again, and see if
 >its still nasty. You can give it a quick try yourself. the function
 >  need_imm_uses_for
 >in tree-ssa-ccp, change it to return true all the time, and see what the
 >compilation time difference for gerald testcase is. It use to increase
 >CCPs time as well as overall time noticably. Perhaps it doesn't now, I
 >havent tried it lately.
I doubt Zdenek will see a huge change -- largely because we factor the
computed gotos which were causing the PHI explosions.  But the underlying
concept of filtering out variables we do not care about (because we know
they are varying) is still wise.

And to a much lesser extent, part of the problem is that we create way
too many virtual operands because of our lousy aliasing.

jeff

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

[law]

In message <20031215214727.GA31524@atrey.karlin.mff.cuni.cz>, Zdenek Dvorak wri
tes:
 >Hello,
 >
 >> > > 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.
 >> > 
 >> 
 >> I dont see why. If you want to track just a few variables,  why should
 >> you pay for tracking 45,000?
 >
 >because you generally don't know which variables you are interested in.
But sometimes you do (for example CCP) and not computing it for all those
variables you don't care about is a significant win.


 >Also chosing the different ones in the different passes requieres
 >recomputing the information, and it is not at all obvious to me whether
 >this would not make this actually more expensive.
True.  There's now way to know for sure until you actually try it.

However, our experience so far has been that "pruning" the set of things
we're computing (whether they're immediate uses, variables which might
need PHIs, etc) has been very advantageous from both a compile time
standpoint and a runtime standpoint.


Jeff

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

[Andrew MacLeod]

On Mon, 2003-12-15 at 14:18, Zdenek Dvorak wrote:
> Hello,
> 
> 
> > 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.

After pondering it, I have concluded you are correct, the immediate uses
info should be attached to the SSA_NAME.  The pragmatic reason is that
it eliminates the need to have the def stmt of the SSA_NAME in place
before the uses are seen... 

ie, keeping the information accurate when you are adding a new ssa_name
would *require* you to create the DEF first, or you have no place to put
the uses information.  Although its probably good practice to issue the
DEF first, enforcing that is pretty lame.  Putting it in the SSA_NAME
resolves ths problem since the SSA_NAME must exist in order to actually
occur in the stmt :-). 

The rest of it Im still thinking about :-)

Andrew

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

[Zdenek Dvorak]

Hello,

> > > 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.
> 
> After pondering it, I have concluded you are correct, the immediate uses
> info should be attached to the SSA_NAME.  The pragmatic reason is that
> it eliminates the need to have the def stmt of the SSA_NAME in place
> before the uses are seen... 
> 
> ie, keeping the information accurate when you are adding a new ssa_name
> would *require* you to create the DEF first, or you have no place to put
> the uses information.  Although its probably good practice to issue the
> DEF first, enforcing that is pretty lame.  Putting it in the SSA_NAME
> resolves ths problem since the SSA_NAME must exist in order to actually
> occur in the stmt :-). 

my reason for having the information stored in the SSA_NAME actually
was that there may be multiple definitions in a single statement,
thus making it necessary to somehow determine of which of them is used
in the statement recorded as the immediate use; this would be extremely
cumbersome.

Zdenek

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

[Andrew MacLeod]

On Tue, 2003-12-16 at 17:20, Zdenek Dvorak wrote:
> Hello,
> 
> > > > 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.
> > 
> > After pondering it, I have concluded you are correct, the immediate uses
> > info should be attached to the SSA_NAME.  The pragmatic reason is that
> > it eliminates the need to have the def stmt of the SSA_NAME in place
> > before the uses are seen... 
> > 
> > ie, keeping the information accurate when you are adding a new ssa_name
> > would *require* you to create the DEF first, or you have no place to put
> > the uses information.  Although its probably good practice to issue the
> > DEF first, enforcing that is pretty lame.  Putting it in the SSA_NAME
> > resolves ths problem since the SSA_NAME must exist in order to actually
> > occur in the stmt :-). 
> 
> my reason for having the information stored in the SSA_NAME actually
> was that there may be multiple definitions in a single statement,
> thus making it necessary to somehow determine of which of them is used
> in the statement recorded as the immediate use; this would be extremely
> cumbersome.
> 
I would have just associated it with the new operand infrastructure..
ie, you ask for the immediate uses info for a def index or vdef index,
since we have that index info available easily. It was maintaining it
that was the clincher for me.

Andrew

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

[law]

In message <1071611437.13020.198.camel@p4>, Andrew MacLeod writes:
 >On Mon, 2003-12-15 at 14:18, Zdenek Dvorak wrote:
 >> Hello,
 >> 
 >> 
 >> > 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.
 >
 >After pondering it, I have concluded you are correct, the immediate uses
 >info should be attached to the SSA_NAME.  The pragmatic reason is that
 >it eliminates the need to have the def stmt of the SSA_NAME in place
 >before the uses are seen... 
I'll note that this would actually make the whole SSA_NAME recycling
vs dangling references problem in the IL a lot easier to detect and
maybe solve.

When the time comes to release an SSA_NAME, fundamentally we know that
all its references ought to be dead as well and we should remove them
from the IL.  If we had immediate uses that would be relatively easy
to do.

Instead right now we rely upon folks to release SSA_NAMEs and not to
leave any dangling references in the IL.  We've already run into a 
couple places where this has been problematical.

[ Jan's got checking code for this, which I'm hoping to take a close look
  at tonight. ]


Jeff

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

[Diego Novillo]

On Mon, 2003-12-15 at 14:04, Andrew MacLeod wrote:

> 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 :-)
> 
Oh, OK.  If you insist.  Yes, tree-ssa.c:get_reaching_def.


Diego.