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

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

[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] Maintaining/representing def-use/use-def information

[Chris Lattner]

On 12 Dec 2003, Andrew MacLeod wrote:
> 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.

How were you representing the information before?  Why was it taking so
much space?

I have said it before (http://gcc.gnu.org/ml/gcc/2002-08/msg01555.html),
but I still think that the reason that GCC & tree-ssa have all of these
memory problems is the insistence on using "tree" structures for something
that should be _much_ simpler and lighter-weight.  LLVM is very efficient,
has a small memory footprint, and all of the allocation/deallocation is
explicit (no GC), which is made possible by a trivial ownership model.  I
don't see how you can do these things with a tree representation.

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

LLVM doesn't use FUD chains, nor would tree-ssa.

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

The point is that the cache would be irrelevant if you representation had
the information you needed directly in it...

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

I'm really confused by all of this talk about memory footprint.  How are
you guys representing def-use chains?

-Chris

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

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] Maintaining/representing def-use/use-def information

[Andrew MacLeod]

On Fri, 2003-12-12 at 15:01, Chris Lattner wrote:
> On 12 Dec 2003, Andrew MacLeod wrote:
> > 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.
> 
> How were you representing the information before?  Why was it taking so
> much space?

memory and time spent constructing. The current representation is
reasonably efficient, but its still unneccessary space when you have
45000 ssa versions and a list of uses for each one.  The code is in the
sources :-)
> 
> I have said it before (http://gcc.gnu.org/ml/gcc/2002-08/msg01555.html),
> but I still think that the reason that GCC & tree-ssa have all of these
> memory problems is the insistence on using "tree" structures for something
> that should be _much_ simpler and lighter-weight.  LLVM is very efficient,
> has a small memory footprint, and all of the allocation/deallocation is
> explicit (no GC), which is made possible by a trivial ownership model.  I
> don't see how you can do these things with a tree representation.
> 

There is a longer term plan to compress trees into a more rational
memory consumption format, none has gotten to it yet. We are far more
likely to make trees more efficient than we are to throw them away to
replace them with something equivilent. 


> > > > 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.
> 
> I'm really confused by all of this talk about memory footprint.  How are
> you guys representing def-use chains?
> 
Thats not the issue. Its not that memeory inefficient, it just takes
memory, and there is enough being consumed at the moment that we're
being careful when we allocate memory. Even mainline has some problems
now on larger programs, we use a bit more memory, partially due to
GIMPLE, and then SSA uasea bit more. It means we trigger the memory
problems earlier than mainline does.  

Memory inefficiancy of trees is known, and since its becoming an issue,
it will have to get visited and fixed. 

None of this is really related to the issue that, for the moment, I dont
see a need to maintain def->use chains across the entire function for
all variables through all optimization passes.   Down the road, once
trees have been fixed and are more efficient, perhaps it wont be as much
an issue, but right now we are attempting to get the branch into shape
to make it compete with mainline, we can't afford to exacerbate the
situation.

Andrew

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] Maintaining/representing def-use/use-def information

[Chris Lattner]

On 13 Dec 2003, Andrew MacLeod wrote:
> > > 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.
> >
> > How were you representing the information before?  Why was it taking so
> > much space?
>
> memory and time spent constructing. The current representation is
> reasonably efficient, but its still unneccessary space when you have
> 45000 ssa versions and a list of uses for each one.

It seems to me that the problem is that SSA is a second class citizen in
your representation, something that is hacked onto the side.  Maybe if it
were better integrated, some of the problems would go away.  There is no
reason for the SSA_NAME's to be distinct memory objects from the
expressions.

> The code is in the sources :-)

Sorry, but I already have a compiler to work on.  :)   I'm just here to
spout very opinionated ideas.  :)

> > I have said it before (http://gcc.gnu.org/ml/gcc/2002-08/msg01555.html),
> > but I still think that the reason that GCC & tree-ssa have all of these
> > memory problems is the insistence on using "tree" structures for something
> > that should be _much_ simpler and lighter-weight.  LLVM is very efficient,
> > has a small memory footprint, and all of the allocation/deallocation is
> > explicit (no GC), which is made possible by a trivial ownership model.  I
> > don't see how you can do these things with a tree representation.

> There is a longer term plan to compress trees into a more rational
> memory consumption format, none has gotten to it yet. We are far more
> likely to make trees more efficient than we are to throw them away to
> replace them with something equivilent.

Perhaps you should be looking into this, rather than not having def-use
chains?

> > I'm really confused by all of this talk about memory footprint.  How are
> > you guys representing def-use chains?

> Thats not the issue. Its not that memeory inefficient, it just takes
> memory, and there is enough being consumed at the moment that we're
> being careful when we allocate memory. Even mainline has some problems
> now on larger programs, we use a bit more memory, partially due to
> GIMPLE, and then SSA uasea bit more. It means we trigger the memory
> problems earlier than mainline does.

The point is that you are trading off a fundamental part of SSA form for a
temporary space efficiency issue.  If you fixed the basic problems with
your representation, and treated SSA like a first class citizen in the
compiler, this would not be a problem.  Instead it appears that you would
rather "fix" the little, easy, "problems", even if that makes the compiler
harder to work on and less efficient in the future.  Besides, mainline has
it's own memory consumption problems.  It doesn't seem like that should be
the ultimate target (an intermediate target is fine, but you should be
aiming to do much better).

> Memory inefficiancy of trees is known, and since its becoming an issue,
> it will have to get visited and fixed.

If you are already hitting swap, the problem is here now.

> None of this is really related to the issue that, for the moment, I dont
> see a need to maintain def->use chains across the entire function for
> all variables through all optimization passes.   Down the road, once
> trees have been fixed and are more efficient, perhaps it wont be as much
> an issue, but right now we are attempting to get the branch into shape
> to make it compete with mainline, we can't afford to exacerbate the
> situation.

This is related insofar as you are deciding that you need to save memory
by not representing a fundamental part of SSA form, to provide a memory
savings.  Coupled with the fact that you claim def-use chains to not
consume much memory, you are sending a confusing message.  If you are
hitting swap _now_ with such simple transformations, it does not seem
likely that more aggressive analyses and transformations will be feasible.

Adding capabilities like this at a late date will mean that a lot of code
will need to be rewritten.

-Chris

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

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Andrew MacLeod]

On Sat, 2003-12-13 at 22:41, Chris Lattner wrote:
> On 13 Dec 2003, Andrew MacLeod wrote:
> > > > 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.
> > >
> > > How were you representing the information before?  Why was it taking so
> > > much space?
> >
> > memory and time spent constructing. The current representation is
> > reasonably efficient, but its still unneccessary space when you have
> > 45000 ssa versions and a list of uses for each one.
> 
> It seems to me that the problem is that SSA is a second class citizen in
> your representation, something that is hacked onto the side.  Maybe if it
> were better integrated, some of the problems would go away.  There is no
> reason for the SSA_NAME's to be distinct memory objects from the
> expressions.

Actually, SSA is very well integrated. The addition of SSA requires not
much more than PHI nodes and SSA_NAME tree nodes, which are
fundamentally the same as a variable, except they add a version number.
I wouldn't call SSA a second class citizen at all.


> 
> The point is that you are trading off a fundamental part of SSA form for a
> temporary space efficiency issue.  If you fixed the basic problems with
> your representation, and treated SSA like a first class citizen in the

Fixing the "basic problem" (which is probably memory usage of trees at
this point) is an expansive task that will be tackled in due time, when
either its significance rises to the point where one of us *has* to take
care of it, or when somone else is motivated to take on the task. That
is unlikely until we manage a merge with mainline, (or mainline takes
care of it :-). We're doing a pretty decent job now at keeping the
tree-ssa branch from being much worse than mainline is. And we're still
doing more. None of the things we are doing are at the expense of the
implementation. 

> compiler, this would not be a problem.  Instead it appears that you would
> rather "fix" the little, easy, "problems", even if that makes the compiler
> harder to work on and less efficient in the future.  Besides, mainline has
> it's own memory consumption problems.  It doesn't seem like that should be
> the ultimate target (an intermediate target is fine, but you should be
> aiming to do much better).

Appearences can be misleading :-) Everything we are doing is making the
compiler easier to maintain and more efficient in the future. Many of
them are a far cry from easy little fixes.  What we have is quite
flexible.

> 
> > None of this is really related to the issue that, for the moment, I dont
> > see a need to maintain def->use chains across the entire function for
> > all variables through all optimization passes.   Down the road, once
> > trees have been fixed and are more efficient, perhaps it wont be as much
> > an issue, but right now we are attempting to get the branch into shape
> > to make it compete with mainline, we can't afford to exacerbate the
> > situation.
> 
> This is related insofar as you are deciding that you need to save memory
> by not representing a fundamental part of SSA form, to provide a memory

As far as def->use chain go, the architecture is modular enough that it
is quite trivial to add them, and maintain them if need be. I haven't
seen a need to keep them around all the time yet, and since we haven't
gotten to the tree memory issue yet, I dont see why would try to keep
them around and up to date all the time when there are very few
consumers of it so far. 

> savings.  Coupled with the fact that you claim def-use chains to not
> consume much memory, you are sending a confusing message.  If you are

They consume enough to cause an increase in memory usage, and time
required to calculate/keep up to date.  The confusion is probably due,
in part, to the fact that I do think we will eventually be keeping them
around for at least part of the compilation phase. I simply can't see
justification for it until we tackle the tree issue. Perhaps my opinion
will change before that, Zdenek is starting to run into cases where he
need immediate uses, which would bump the priority.

Our memory problems are not as bad as they were, and the immediate uses
data will probably not have the significant impact it did back when I
did the original work in august, or whenever it was. That has not been
verified tho.  I may take a look at it next now that everyone seems so
interested in it :-)

> Adding capabilities like this at a late date will mean that a lot of code
> will need to be rewritten.
> 

I think virtually nothing will have to be rewritten to add this
capability. I have to make a minor change to the way immediate uses is
currently calculated/stored, but its pretty minor. And we'll have the
capability to calculate/maintain def->use links without a lot of
trouble.

Andrew

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Chris Lattner]

On 15 Dec 2003, Andrew MacLeod wrote:
> > It seems to me that the problem is that SSA is a second class citizen in
> > your representation, something that is hacked onto the side.  Maybe if it
> > were better integrated, some of the problems would go away.  There is no
> > reason for the SSA_NAME's to be distinct memory objects from the
> > expressions.
>
> Actually, SSA is very well integrated. The addition of SSA requires not
> much more than PHI nodes and SSA_NAME tree nodes, which are
> fundamentally the same as a variable, except they add a version number.
> I wouldn't call SSA a second class citizen at all.

That is my point.  There is no reason to have an extra SSA_NAME memory
allocation at all.  If SSA is properly integrated into the representation
(ie, not something tacked onto an existing representation designed for
something else), then the expression implicitly defines the computed
value.

> > The point is that you are trading off a fundamental part of SSA form for a
> > temporary space efficiency issue.  If you fixed the basic problems with
> > your representation, and treated SSA like a first class citizen in the
>
> Fixing the "basic problem" (which is probably memory usage of trees at
> this point) is an expansive task that will be tackled in due time, when
> either its significance rises to the point where one of us *has* to take
> care of it, or when somone else is motivated to take on the task. That
> is unlikely until we manage a merge with mainline, (or mainline takes
> care of it :-). We're doing a pretty decent job now at keeping the
> tree-ssa branch from being much worse than mainline is. And we're still
> doing more.  None of the things we are doing are at the expense of the
> implementation.

My point is basically that if it is such a big problem that it prevents
you from using important data structures, maybe it should be looked into
_now_ instead of waiting for someone else to fix it.  That said, I
understand how it's not reasonable to expect someone to pick it up in a
volunteer project, unless it's an extremely pressing need.

> > This is related insofar as you are deciding that you need to save memory
> > by not representing a fundamental part of SSA form, to provide a memory
>
> As far as def->use chain go, the architecture is modular enough that it
> is quite trivial to add them, and maintain them if need be. I haven't
> seen a need to keep them around all the time yet, and since we haven't
> gotten to the tree memory issue yet, I dont see why would try to keep
> them around and up to date all the time when there are very few
> consumers of it so far.

Ok, I guess its a reasonable approach just to make them available and then
see how often it gets used, as long as the current implementation is
efficient enough that people will not avoid using it when it makes
sense...

> > Adding capabilities like this at a late date will mean that a lot of code
> > will need to be rewritten.

> I think virtually nothing will have to be rewritten to add this
> capability. I have to make a minor change to the way immediate uses is
> currently calculated/stored, but its pretty minor. And we'll have the
> capability to calculate/maintain def->use links without a lot of
> trouble.

Ok, that makes sense.  :)

-Chris

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

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Andrew MacLeod]

On Mon, 2003-12-15 at 14:12, Chris Lattner wrote:
> On 15 Dec 2003, Andrew MacLeod wrote:
> > > It seems to me that the problem is that SSA is a second class citizen in
> > > your representation, something that is hacked onto the side.  Maybe if it
> > > were better integrated, some of the problems would go away.  There is no
> > > reason for the SSA_NAME's to be distinct memory objects from the
> > > expressions.
> >
> > Actually, SSA is very well integrated. The addition of SSA requires not
> > much more than PHI nodes and SSA_NAME tree nodes, which are
> > fundamentally the same as a variable, except they add a version number.
> > I wouldn't call SSA a second class citizen at all.
> 
> That is my point.  There is no reason to have an extra SSA_NAME memory
> allocation at all.  If SSA is properly integrated into the representation
> (ie, not something tacked onto an existing representation designed for
> something else), then the expression implicitly defines the computed
> value.
> 

An SSA_NAME is a decl, just like a variable declaration.
so in non ssa LAND, we have 
 a = 10

thats a tree:
  MODIFY_EXPR
  /      \
VAR_DECL  CONST
   A        10

in ssa land we have

a_2 = 10

    MODIFY_EXPR
    /         \
  SSA_NAME    CONST
  /       \      10
VAR_DECL   2
   A

so the expression does implicitly define the computed value. Its really
no different than  variable except we can associate the version number
with a var_decl.

Its not much different than duplicating the var_decl for A and adding an
integer field for the version number.  We chose this way because there
is a ton of variable specific information like type, etc etc that we
dont need to duplicate, and it doesnt impact any non-ssa parts of the
compiler. It also makes it trivial to look at a cariable and tell if its
in SSA form or not.


> > As far as def->use chain go, the architecture is modular enough that it
> > is quite trivial to add them, and maintain them if need be. I haven't
> > seen a need to keep them around all the time yet, and since we haven't
> > gotten to the tree memory issue yet, I dont see why would try to keep
> > them around and up to date all the time when there are very few
> > consumers of it so far.
> 
> Ok, I guess its a reasonable approach just to make them available and then
> see how often it gets used, as long as the current implementation is
> efficient enough that people will not avoid using it when it makes
> sense...
> 

Well, when it does become a problem, thats when we tackle the efficiency
of the implementation :-)

> > > Adding capabilities like this at a late date will mean that a lot of code
> > > will need to be rewritten.
> 
> > I think virtually nothing will have to be rewritten to add this
> > capability. I have to make a minor change to the way immediate uses is
> > currently calculated/stored, but its pretty minor. And we'll have the
> > capability to calculate/maintain def->use links without a lot of
> > trouble.
> 
> Ok, that makes sense.  :)

We just cant do everything up front. We implement additional
features/requirements things as we need them, and attempt to keep the
architecture well enough designed to let us add these things, hopefully,
without much trouble. Its just not worth spending time on something that
someone might need in the future.

Thats all :-)

Andrew

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Diego Novillo]

On Mon, 2003-12-15 at 14:12, Chris Lattner wrote:
> On 15 Dec 2003, Andrew MacLeod wrote:
>
> > Actually, SSA is very well integrated. The addition of SSA requires not
> > much more than PHI nodes and SSA_NAME tree nodes, which are
> > fundamentally the same as a variable, except they add a version number.
> > I wouldn't call SSA a second class citizen at all.
> 
> That is my point.  There is no reason to have an extra SSA_NAME memory
> allocation at all.  If SSA is properly integrated into the representation
> (ie, not something tacked onto an existing representation designed for
> something else), then the expression implicitly defines the computed
> value.
> 
This was done un purpose when I switched the SSA representation from FUD
chains to a rewriting form.  In GCC, variables are represented by struct
tree_decl, which on a 64 bit host takes up 28 words.

Since each expression must compute a unique variable, I obviously didn't
want to create a new VAR_DECL for every new SSA version we created.  So,
I introduced SSA_NAMEs (6 words) which are the variables that the SSA
passes operate on.

Could the tree_decls be smaller?  Probably.  Do the optimizers care? 
Not in the least.  To them it's just an object that says 'true' when you
call SSA_VAR_P(), they can be added to expression operands, etc.

The guiding principle we have is try not to get distracted with
syntactic sugar or changes that we know are mechanical or can be hidden
behind some API.  That not always works, of course.  And we've had a
fair number of changes that have overhauled large chunks of the
implementation.


Diego.

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Chris Lattner]

> > That is my point.  There is no reason to have an extra SSA_NAME memory
> > allocation at all.  If SSA is properly integrated into the representation
> > (ie, not something tacked onto an existing representation designed for
> > something else), then the expression implicitly defines the computed
> > value.

> An SSA_NAME is a decl, just like a variable declaration.
> so in non ssa LAND, we have
>  a = 10
>
> thats a tree:
>   MODIFY_EXPR
>   /      \
> VAR_DECL  CONST
>    A        10
>
> in ssa land we have
>
> a_2 = 10
>
>     MODIFY_EXPR
>     /         \
>   SSA_NAME    CONST
>   /       \      10
> VAR_DECL   2
>    A
>
> so the expression does implicitly define the computed value. Its really
> no different than  variable except we can associate the version number
> with a var_decl.

What you are saying is that instead of _one_ memory allocation to
represent a logical operation, you are uisng 4 (VAR_DECL, SSA_NAME, "2",
MODIFY_EXPR).  Even if some of these are shared, doesn't this make
traversing the representation really expensive and cache unfriendly.  You
also didn't show how a variable is referenced as an operand.

When I said that the SSA form wasn't integrated as a first-class entity,
this is _exactly_ what I meant: your SSA form is added on top of the
existing trees.  Contrast this with LLVM.  Consider the expression: "X =
(1+2); Y = X+X;", which is following LLVM instructions:

  %X = add int 1, 2
  %Y = add int %X, %X

Ignoring types, which every value has, the following are the memory
objects we have to allocate and process:

   CONST1     CONST2
        \     /
          ADD
          | |
          ADD

ie, there are _4_ memory allocation, ones for each instruction, and one
for the two constants being referenced.  There are no intermediate objects
used to represent "SSA_NAME"s or variables being declared, etc.  An
instruction which computes a value is directly pointed to by operands.
There is no need to go through an auxillary symbol table to traverse
def-use or use-def chains.

This is what I mean by integrating SSA as a first-class feature in your
representation.  How would this be represented in tree-ssa?

> Its not much different than duplicating the var_decl for A and adding an
> integer field for the version number.  We chose this way because there
> is a ton of variable specific information like type, etc etc that we
> dont need to duplicate, and it doesnt impact any non-ssa parts of the
> compiler. It also makes it trivial to look at a cariable and tell if its
> in SSA form or not.

I understand why you chose to use the existing tree representation as the
basis of tree-ssa, but you have to admit that it has some serious
overheads and costs.  I am not at all convinced that you can eliminate all
of them, even if substantial effort is put towards slimming them down.

> > > > Adding capabilities like this at a late date will mean that a lot of code
> > > > will need to be rewritten.
> >
> > > I think virtually nothing will have to be rewritten to add this
> > > capability. I have to make a minor change to the way immediate uses is
> > > currently calculated/stored, but its pretty minor. And we'll have the
> > > capability to calculate/maintain def->use links without a lot of
> > > trouble.
> >
> > Ok, that makes sense.  :)
>
> We just cant do everything up front. We implement additional
> features/requirements things as we need them, and attempt to keep the
> architecture well enough designed to let us add these things, hopefully,
> without much trouble. Its just not worth spending time on something that
> someone might need in the future.

Ok, sounds good.  Also, you have a much better chance designing a _good_
interface if you have several use cases.  Your approach makes sense.

-Chris

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

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Diego Novillo]

On Mon, 2003-12-15 at 15:06, Chris Lattner wrote:

> I understand why you chose to use the existing tree representation as the
> basis of tree-ssa, but you have to admit that it has some serious
> overheads and costs.  I am not at all convinced that you can eliminate all
> of them, even if substantial effort is put towards slimming them down.
> 
Oh, absolutely.  GCC trees are pretty bulky for lots of reasons.  That
needs to be addressed, but that problem is completely orthogonal to
tree-ssa.

It just happens that tree-ssa exacerbates the shortcomings of the tree
data structure.  Changing that will probably end up being a mini project
of its own.  But in the grand scheme of things, it is just a data
structure change for the sake of memory and cache.  There is no need to
alter the algorithms nor the basic design for this.

Something similar happened to the way statements are chained in the IL. 
What we had before was extremely unfriendly for iterators.  We have
something more decent now.

We didn't want to start by ripping out the tree representation for the
obvious time/effort reasons.  How soon it gets done will depend on the
usual factors.


Diego.

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Andrew MacLeod]

On Mon, 2003-12-15 at 15:06, Chris Lattner wrote:

> What you are saying is that instead of _one_ memory allocation to
> represent a logical operation, you are uisng 4 (VAR_DECL, SSA_NAME, "2",
> MODIFY_EXPR).  Even if some of these are shared, doesn't this make
> traversing the representation really expensive and cache unfriendly.  You
> also didn't show how a variable is referenced as an operand.
> 

The number of memory allocations isnt the point when we are talking
about how well integrated something is. the VAR_DECL, SSA_NAME. "2",
MODIFY *could* be implemented as a single allcoation if we so chose, but
it wouldnt take much less memory, and it wouldnt make anything else
better or easier. We still need all the information in those various
nodes.  There is a minor amount of duplication (ie, MODIFY and VAR_DECL
both have types), but thats not where we have siginificant memory
lossage. SSA_NAMES themselves are fairly efficient and only exist once.

We reference and operand by pointing to the SSA_NAME if the defining
stmt. there is no allocation involved for a reference.

> When I said that the SSA form wasn't integrated as a first-class entity,
> this is _exactly_ what I meant: your SSA form is added on top of the
> existing trees.  Contrast this with LLVM.  Consider the expression: "X =

Is no more a second class citizen than any other decl tree element we
add like a var_decl or a parm_decl.

> (1+2); Y = X+X;", which is following LLVM instructions:
> 
>   %X = add int 1, 2
>   %Y = add int %X, %X
> 
> Ignoring types, which every value has, the following are the memory
> objects we have to allocate and process:
> 
>    CONST1     CONST2
>         \     /
>           ADD
>           | |
>           ADD
> 
> ie, there are _4_ memory allocation, ones for each instruction, and one
> for the two constants being referenced.  There are no intermediate objects
> used to represent "SSA_NAME"s or variables being declared, etc.  An
> instruction which computes a value is directly pointed to by operands.
> There is no need to go through an auxillary symbol table to traverse
> def-use or use-def chains.

we keep our expressions shorter. we use temporaries to define the result
of a MODIFY.  When you boil away all the minor detail crap, The single
thing of significance which is different between what you are doing and
what we are doing is that you don't have the equivient of a
MODIFY_EXPR.  You make the modify implicit in the defining operation.

How do you deal with a stmt which has more than once DEF?  We have
precious few, but they do exist. 

 Example Diego? You added the multiple def support...

We also deal with virtual definitions and uses to handle non-scalar or
non-ssa interactions/side-effects, and there can be multiple virtual
definitions on a given stmt.

> 
> This is what I mean by integrating SSA as a first-class feature in your
> representation.  How would this be represented in tree-ssa?

a_2 = 1 + 2
a_3 = a_2 + a_2

we have 2 SSA_NAMES, allocated once.

   SSA_NAME   and     SSA_NAME
    /    \             /   \
   a      3           a     2

both of which could have been a single allocation if we chose, but it
turns out to be less memory to allocate them as SSA_NAMEs as Diego has
already pointed out.


  MODIFY_EXPR
   /      \
 a_2      PLUS
          /   \
         1     2

  MODIFY_EXPR
   /       \
  a_3      PLUS
          /    \
        a_2    a_2

So we have a total of 8 allocations. a_2, a_3, 2 MODIFY_EXPRS, 2 PLUS
and 1, and 2.

Yes, perhaps the MODIFY_EXPR's could be considered superfluous, but
thats really the only significant difference. We maintain the root
variable in the SSA_NAMEs so we can map the epressions back to the
original variables in the program:

Its not much of a stretch to say that we would have exactly the same
thing as you if we rolled all the SSA_NAME information into our
MODIFY_EXPR node. I happen to like it explicit a little better
personally.


I presume you keep information about the original defining variable in
the operation node, like your ADD, which is the same information we are
keeping in our SSA_NAME by pointing at a DECL. Otherwise you would have
a hard time generating debug information. So the amount of information
hanging around is not significantly different, you just have slightly
less duplication and pointers.


Ultimately, I dont see much difference other than implementation
details...

Andrew

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Zdenek Dvorak]

Hello,

> Ultimately, I dont see much difference other than implementation
> details...

... and about three times more memory spent, I would estimate. For a
single assignment statement, we have:

1) The var_decl node
2) The ssa name
3) modify_expr
4) operation_expr

+ pointers to link them together, versus

1) single entity containing just the operation code and two pointers to
   the arguments (+additional information like type, etc).

Zdenek

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Diego Novillo]

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

>  Example Diego? You added the multiple def support...
> 
__asm__


Diego.

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Andrew MacLeod]

On Mon, 2003-12-15 at 15:55, Zdenek Dvorak wrote:
> Hello,
> 
> > Ultimately, I dont see much difference other than implementation
> > details...
> 
> ... and about three times more memory spent, I would estimate. For a
> single assignment statement, we have:

Which is an implementation detail, not an architecture one.
> 
> 1) The var_decl node
> 2) The ssa name
> 3) modify_expr
> 4) operation_expr
> 
> + pointers to link them together, versus
> 
> 1) single entity containing just the operation code and two pointers to
>    the arguments (+additional information like type, etc).
> 

Yes, but that is not what we were discussing, we were discussing that
ssa-names were not first class citizens nor well integrated into the
compiler.

Absolutely we spend more memory in tree form, I never claimed that we
didn't. And there are plans to do something about that.  Both compressed
trees and compressed rtl have both been proposed, but no one has
bothered with it yet. I would expect that it would have very similar
memory properties once its done. Its simply not an SSA specific problem,
but rather an overlal tree issue.

Andrew

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Chris Lattner]

On 15 Dec 2003, Andrew MacLeod wrote:
> On Mon, 2003-12-15 at 15:06, Chris Lattner wrote:
> > What you are saying is that instead of _one_ memory allocation to
> > represent a logical operation, you are uisng 4 (VAR_DECL, SSA_NAME, "2",
> > MODIFY_EXPR).  Even if some of these are shared, doesn't this make
> > traversing the representation really expensive and cache unfriendly.  You
> > also didn't show how a variable is referenced as an operand.

> The number of memory allocations isnt the point when we are talking
> about how well integrated something is. the VAR_DECL, SSA_NAME. "2",
> MODIFY *could* be implemented as a single allcoation if we so chose, but
> it wouldnt take much less memory, and it wouldnt make anything else
> better or easier. We still need all the information in those various
> nodes.  There is a minor amount of duplication (ie, MODIFY and VAR_DECL
> both have types), but thats not where we have siginificant memory
> lossage. SSA_NAMES themselves are fairly efficient and only exist once.

Ok.  I was just trying to point out a deficiency in your system that I
perceived.  If you don't agree, then I certainly will not try to force the
point.  I'm just trying to point out stuff that might become a problem
down the line as early as possible, as opposed to letting you discover the
problem later when it may be harder to recover.  I'm truly not trying to
start a pointless flamewar. :)

> > When I said that the SSA form wasn't integrated as a first-class entity,
> > this is _exactly_ what I meant: your SSA form is added on top of the
> > existing trees.  Contrast this with LLVM.  Consider the expression: "X =
>
> Is no more a second class citizen than any other decl tree element we
> add like a var_decl or a parm_decl.

Uhm, exactly. :)

> we keep our expressions shorter. we use temporaries to define the result
> of a MODIFY.  When you boil away all the minor detail crap, The single
> thing of significance which is different between what you are doing and
> what we are doing is that you don't have the equivient of a
> MODIFY_EXPR.  You make the modify implicit in the defining operation.

Uhm.  Ok, if you boil away everything but that, then yes, you're right.

> How do you deal with a stmt which has more than once DEF?  We have
> precious few, but they do exist.

We don't.  They don't exist in SSA form.  The only feature we have not
implemented yet is inline assembly, and for that I plan to use lvalues
("by reference parameters") to represent the multiple outputs possible
from a single "asm statement". Everything else is fully implemented in
LLVM, and we have not had a problem so far.

> We also deal with virtual definitions and uses to handle non-scalar or
> non-ssa interactions/side-effects, and there can be multiple virtual
> definitions on a given stmt.

LLVM does not have this complication.

> > This is what I mean by integrating SSA as a first-class feature in your
> > representation.  How would this be represented in tree-ssa?
>
> a_2 = 1 + 2
> a_3 = a_2 + a_2
>
> we have 2 SSA_NAMES, allocated once.
>
>    SSA_NAME   and     SSA_NAME
>     /    \             /   \
>    a      3           a     2
>
> both of which could have been a single allocation if we chose, but it
> turns out to be less memory to allocate them as SSA_NAMEs as Diego has
> already pointed out.

So, you're saying that it's better than using VAR_DECL's directly, which,
of course, carry a lot of baggage that you're not interested in.  Why use
them at all?

>
>   MODIFY_EXPR
>    /      \
>  a_2      PLUS
>           /   \
>          1     2
>
>   MODIFY_EXPR
>    /       \
>   a_3      PLUS
>           /    \
>         a_2    a_2
>
> So we have a total of 8 allocations. a_2, a_3, 2 MODIFY_EXPRS, 2 PLUS
> and 1, and 2.

Don't forget the VARDECL for A.  Also note that you changed the expression
that I gave you.  In LLVM, there is no memory difference at all between "X
=(1+2); Y = X+X;" and "X = (1+2); X = X+X;", but in tree-ssa you just
elided an extra VARDECL and SSANAME, so your count is off.

> I presume you keep information about the original defining variable in
> the operation node,

No, we don't.  We don't have any concept of "defining variable" or
"versions" at all.  Though all SSA construction papers talk about building
versions of source variables, once you start doing transformations, that
idea becomes quickly meaningless.  I think you guys have already run into
this in your "out-of-ssa" pass.

> Ultimately, I dont see much difference other than implementation
> details...

I really do not want to start a flamewar here or step on people's toes.
The reason this thread started is because I think that use-def and def-use
information are both _critical_ to SSA optimizers, and it seemed at that
point that you were avoiding building this information due to unrelated
memory problems elsewhere in tree-ssa.  That's all!

-Chris

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

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Zdenek Dvorak]

Hello,

> > > Ultimately, I dont see much difference other than implementation
> > > details...
> > 
> > ... and about three times more memory spent, I would estimate. For a
> > single assignment statement, we have:
> 
> Which is an implementation detail, not an architecture one.

on contrary, I see this as a major architectural decision -- identifying the
variable with the statement that defines it is a very interesting idea.

Zdenek

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Andrew MacLeod]

On Mon, 2003-12-15 at 16:01, Diego Novillo wrote:
> On Mon, 2003-12-15 at 15:47, Andrew MacLeod wrote:
> 
> >  Example Diego? You added the multiple def support...
> > 
> __asm__
> 
Ah yes, an inline asm can have mutliple results. I knew there was
something we needed it for.

Andrew

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Zdenek Dvorak]

Hello,

> No, we don't.  We don't have any concept of "defining variable" or
> "versions" at all.  Though all SSA construction papers talk about building
> versions of source variables, once you start doing transformations, that
> idea becomes quickly meaningless.

except for ssa-pre, that requires the original variable names.  I still
consider it an indication that there is something rotten with the
optimization, but did not get the idea how to make it better so far.

Zdenek

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Chris Lattner]

On Mon, 15 Dec 2003, Zdenek Dvorak wrote:

> Hello,
>
> > No, we don't.  We don't have any concept of "defining variable" or
> > "versions" at all.  Though all SSA construction papers talk about building
> > versions of source variables, once you start doing transformations, that
> > idea becomes quickly meaningless.
>
> except for ssa-pre, that requires the original variable names.  I still
> consider it an indication that there is something rotten with the
> optimization, but did not get the idea how to make it better so far.

Yes.  SSA-PRE, as presented in the papers, only works on a program which
just been just newly converted into SSA form (things like overlapping
lifetimes for "versions" of variables break it severely).

There are ways around this, but the SSAPRE papers have several fairly
severe bugs and ommissions in them.  This information is not really needed
for implementing PRE on SSA form.

-Chris

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

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Diego Novillo]

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

> on contrary, I see this as a major architectural decision -- identifying the
> variable with the statement that defines it is a very interesting idea.
> 
Sorry?  SSA_NAME_DEF_STMT() tells you exactly that.  Or are you asking
something else?


Diego.

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Zdenek Dvorak]

Hello,

> > on contrary, I see this as a major architectural decision -- identifying the
> > variable with the statement that defines it is a very interesting idea.
> > 
> Sorry?  SSA_NAME_DEF_STMT() tells you exactly that.  Or are you asking
> something else?

no, I am just speaking about the fact that LLVM in fact does not have
variables at all.  Not really new idea, but definitely interesting and
seems to fit nicely with the ssa concept.

Zdenek

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Andrew MacLeod]

On Mon, 2003-12-15 at 16:11, Chris Lattner wrote:
> On 15 Dec 2003, Andrew MacLeod wrote:

> > I presume you keep information about the original defining variable in
> > the operation node,
> 
> No, we don't.  We don't have any concept of "defining variable" or
> "versions" at all.  Though all SSA construction papers talk about building
> versions of source variables, once you start doing transformations, that
> idea becomes quickly meaningless.  I think you guys have already run into
> this in your "out-of-ssa" pass.
> 

Not really. We do create new numbered version of the user's variables in
SSA->normal (ie 'A' may have an 'A.2' floating around somewhere if there
was an overlapping live range), but the debug information is correct in
a lot of places. The resulting programs still have decent debug info, as
far as optimized debug info goes.  

> > Ultimately, I dont see much difference other than implementation
> > details...
> 
> I really do not want to start a flamewar here or step on people's toes.
> The reason this thread started is because I think that use-def and def-use
> information are both _critical_ to SSA optimizers, and it seemed at that
> point that you were avoiding building this information due to unrelated
> memory problems elsewhere in tree-ssa.  That's all!
> 

Not a problem, I learned a little more about LLVM today :-) In fact, I
don't think its as different from us as I thought it was.


Andrew

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Andrew MacLeod]

On Mon, 2003-12-15 at 16:11, Zdenek Dvorak wrote:
> Hello,
> 
> > > > Ultimately, I dont see much difference other than implementation
> > > > details...
> > > 
> > > ... and about three times more memory spent, I would estimate. For a
> > > single assignment statement, we have:
> > 
> > Which is an implementation detail, not an architecture one.
> 
> on contrary, I see this as a major architectural decision -- identifying the
> variable with the statement that defines it is a very interesting idea.
> 

And did I not say that that one thing was exactly the difference? and
that the rest of the differences, like memory consumption was an
implementation detail?

And we could make that architectural change if we so chose. We could
define an SSA_NAME to have an impllcit MODIFY easily enough, and point
direcdtly to the operational part of the modify. It wouldnt be that big
a deal. Its just not worth doing until we do tree-compaction, whatever
that turns out to be.  For now we work with trees.

Andrew

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Daniel Berlin]

On Dec 15, 2003, at 4:14 PM, Zdenek Dvorak wrote:

> Hello,
>
>> No, we don't.  We don't have any concept of "defining variable" or
>> "versions" at all.  Though all SSA construction papers talk about 
>> building
>> versions of source variables, once you start doing transformations, 
>> that
>> idea becomes quickly meaningless.
>
> except for ssa-pre, that requires the original variable names.

Uh, only to determine lexical equivalence of expressions.

> I still
> consider it an indication that there is something rotten with the
> optimization, but did not get the idea how to make it better so far.
>

Give me value numbers, and it'll do it based on value numbers.

>

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Daniel Berlin]

On Dec 15, 2003, at 4:18 PM, Chris Lattner wrote:

> On Mon, 15 Dec 2003, Zdenek Dvorak wrote:
>
>> Hello,
>>
>>> No, we don't.  We don't have any concept of "defining variable" or
>>> "versions" at all.  Though all SSA construction papers talk about 
>>> building
>>> versions of source variables, once you start doing transformations, 
>>> that
>>> idea becomes quickly meaningless.
>>
>> except for ssa-pre, that requires the original variable names.  I 
>> still
>> consider it an indication that there is something rotten with the
>> optimization, but did not get the idea how to make it better so far.
>
> Yes.  SSA-PRE, as presented in the papers, only works on a program 
> which
> just been just newly converted into SSA form (things like overlapping
> lifetimes for "versions" of variables break it severely).

> There are ways around this, but the SSAPRE papers have several fairly
> severe bugs and ommissions in them.  This information is not really 
> needed
> for implementing PRE on SSA form.
>

Yes, you could do E-Path PRE, but it's harder to extend it to perform 
strength reduction or load speculation.
Besides, I've been working on SSAPRE since before E-path PRE existed :P.
--Dan

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Chris Lattner]

On Mon, 15 Dec 2003, Daniel Berlin wrote:
> > There are ways around this, but the SSAPRE papers have several fairly
> > severe bugs and ommissions in them.  This information is not really
> > needed
> > for implementing PRE on SSA form.
> >
>
> Yes, you could do E-Path PRE, but it's harder to extend it to perform
> strength reduction or load speculation.

Yup, and FWIW, LLVM uses an e-path based formulation of PRE on SSA form.

-Chris

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

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Daniel Berlin]

On Dec 15, 2003, at 5:07 PM, Chris Lattner wrote:

> On Mon, 15 Dec 2003, Daniel Berlin wrote:
>>> There are ways around this, but the SSAPRE papers have several fairly
>>> severe bugs and ommissions in them.  This information is not really
>>> needed
>>> for implementing PRE on SSA form.
>>>
>>
>> Yes, you could do E-Path PRE, but it's harder to extend it to perform
>> strength reduction or load speculation.
>
> Yup, and FWIW, LLVM uses an e-path based formulation of PRE on SSA 
> form.
I remember looking at it.
Did I mention we can do LFTR too :P.
The only thing that really bothers me about SSAPRE is that you have to 
look at working implementations to figure out the algorithm, because of 
the bugs and "left out" pieces of the papers.  After about a year, i've 
got it pretty much down.

I should note that E-Path PRE doesn't really solve Zdenek's "problem" 
(that it requires variable names) with SSAPRE either.  You still need 
to determine equivalence of the expressions, you guys just do it with 
value numbers instead of variable names, (which we could do as well, 
given the information):

"
   ValueNumbering *VN;
   // Ok, this is the first time we have seen the expression.  Build a 
set of
   // equivalent expressions using SSA def/use information.  We consider
   // expressions to be equivalent if they are the same opcode and have
   // equivalent operands.  As a special case for SSA, values produced 
by PHI
   // nodes are considered to be equivalent to all of their operands.
   //
   std::vector<Value*> Values;
   VN->getEqualNumberNodes(Expr, Values);
"

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[law]

In message <Pine.LNX.4.44.0312121357450.16876-100000@nondot.org>, Chris Lattner
 writes:
 >On 12 Dec 2003, Andrew MacLeod wrote:
 >> 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.
 >
 >How were you representing the information before?  Why was it taking so
 >much space?
I believe the core problem was that the computed jumps resulted in 
insanely large PHIs and an insanely large number of PHIs.  The resulting
use-def information was correspondingly large.


 >I have said it before (http://gcc.gnu.org/ml/gcc/2002-08/msg01555.html),
 >but I still think that the reason that GCC & tree-ssa have all of these
 >memory problems is the insistence on using "tree" structures for something
 >that should be _much_ simpler and lighter-weight.  LLVM is very efficient,
 >has a small memory footprint, and all of the allocation/deallocation is
 >explicit (no GC), which is made possible by a trivial ownership model.  I
 >don't see how you can do these things with a tree representation.
In this particular case, I don't think that the problem is using the
tree structures.

Given infinite time and resources we might not have started with trees.
However, starting with trees gave us somewhere to stand while we dealt
with a lot of other issues and got us to a point where we could actually
do some interesting things a lot faster.

It may be the case that we won't always use trees.  Then again, someone
may come along and significantly rework trees to make them reasonably
efficient.



Jeff

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Chris Lattner]

On Mon, 15 Dec 2003, Daniel Berlin wrote:
> On Dec 15, 2003, at 5:07 PM, Chris Lattner wrote:
> >> Yes, you could do E-Path PRE, but it's harder to extend it to perform
> >> strength reduction or load speculation.
> >
> > Yup, and FWIW, LLVM uses an e-path based formulation of PRE on SSA
> > form.
> I remember looking at it.
> Did I mention we can do LFTR too :P.

Something I've never understood about the SSAPRE paper and subsequent
extensions: why does it make sense to incorporate things like LFTR into
PRE?  I understand the idea of integrating load/store motion into it, but
LFTR?  It seems like a simplish problem.  What am I missing?

> The only thing that really bothers me about SSAPRE is that you have to
> look at working implementations to figure out the algorithm, because of
> the bugs and "left out" pieces of the papers.  After about a year, i've
> got it pretty much down.

Yeah.  We had a group of people that tried to reimplement it from first
principles in LLVM, and they made a valiant effort, but never got it
working 100% robustly (largely due to time contraints), and it was never
integrated into the LLVM tree.  If you're interested in reading their
experiences, the report is here:
http://llvm.cs.uiuc.edu/ProjectsWithLLVM/2002-Fall-CS426-SSAPRE.pdf

> I should note that E-Path PRE doesn't really solve Zdenek's "problem"
> (that it requires variable names) with SSAPRE either.  You still need
> to determine equivalence of the expressions, you guys just do it with
> value numbers instead of variable names, (which we could do as well,
> given the information):

Yup.  Another issue is that PHI nodes can cause two non "lexically
identical" expressions to have dynamically equal values that PRE should be
aware of.  The current LLVM implementation of PRE doesn't handle this case
yet, so it's not as aggressive as it could be.  I need to get some time to
finish that missing piece up.  24 hour days are so limiting. :)

>
> "
>    ValueNumbering *VN;
>    // Ok, this is the first time we have seen the expression.  Build a
> set of
>    // equivalent expressions using SSA def/use information.  We consider
>    // expressions to be equivalent if they are the same opcode and have
>    // equivalent operands.  As a special case for SSA, values produced
> by PHI
>    // nodes are considered to be equivalent to all of their operands.
>    //
>    std::vector<Value*> Values;
>    VN->getEqualNumberNodes(Expr, Values);
> "

Exactly.  Note that in LLVM, the -load-vn pass automatically provides
value number information for loads too (using an arbitrary implementation
of the AliasAnalysis interface), allowing for load motion.  :)

-Chris

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

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[Chris Lattner]

On Mon, 15 Dec 2003 law@redhat.com wrote:
>  >> 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.
>  >
>  >How were you representing the information before?  Why was it taking so
>  >much space?
> I believe the core problem was that the computed jumps resulted in
> insanely large PHIs and an insanely large number of PHIs.  The resulting
> use-def information was correspondingly large.

use-def and def-use information should have the exact same size, or at
worst within a constant factor if each other.  All operations for
manipulating it should also be extremely cheap.  In LLVM, for example,
changing the operand of an instruction to different value automatically
updates the use-def and def-use information for the old used value, the
new used value, and the current instruction, all in constant time (and
without any memory allocations :).

> Given infinite time and resources we might not have started with trees.
> However, starting with trees gave us somewhere to stand while we dealt
> with a lot of other issues and got us to a point where we could actually
> do some interesting things a lot faster.

I understand why tree-ssa chose to base the work on trees, and it is a
good choice.  That said, use-def and def-use information should be cheap
to keep always up-to-date and available for clients, regardless of the
representation.

-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] Maintaining/representing def-use/use-def information

[Daniel Berlin]

On Dec 15, 2003, at 6:28 PM, Chris Lattner wrote:

> On Mon, 15 Dec 2003, Daniel Berlin wrote:
>> On Dec 15, 2003, at 5:07 PM, Chris Lattner wrote:
>>>> Yes, you could do E-Path PRE, but it's harder to extend it to 
>>>> perform
>>>> strength reduction or load speculation.
>>>
>>> Yup, and FWIW, LLVM uses an e-path based formulation of PRE on SSA
>>> form.
>> I remember looking at it.
>> Did I mention we can do LFTR too :P.
>
> Something I've never understood about the SSAPRE paper and subsequent
> extensions: why does it make sense to incorporate things like LFTR into
> PRE?  I understand the idea of integrating load/store motion into it, 
> but
> LFTR?  It seems like a simplish problem.  What am I missing?
>
It was easy?

Strength reduction i know they do because it does *straight line code* 
strength reduction, not just traditional loop based strength reduction.

IE it'll transform

a = b * 5
if (whatever)
{
	b = b + 1
}
a =  b * 5

into

pretmp = b * 5
a = pretmp
if (whatever)
{
	pretmp = pretmp + <i'm working on a final and i don't feel like 
calculating the increment in my head :P>
	b = b + 1
}
a = pretmp


The ability to repair "injuries" exposes quite a few more redundancies.

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

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[law]

In message <Pine.LNX.4.44.0312151502130.27073-100000@nondot.org>, Chris Lattner
 writes:
 >On 15 Dec 2003, Andrew MacLeod wrote:
 >> On Mon, 2003-12-15 at 15:06, Chris Lattner wrote:
 >> > What you are saying is that instead of _one_ memory allocation to
 >> > represent a logical operation, you are uisng 4 (VAR_DECL, SSA_NAME, "2",
 >> > MODIFY_EXPR).  Even if some of these are shared, doesn't this make
 >> > traversing the representation really expensive and cache unfriendly.  You
 >> > also didn't show how a variable is referenced as an operand.
 >
 >> The number of memory allocations isnt the point when we are talking
 >> about how well integrated something is. the VAR_DECL, SSA_NAME. "2",
 >> MODIFY *could* be implemented as a single allcoation if we so chose, but
 >> it wouldnt take much less memory, and it wouldnt make anything else
 >> better or easier. We still need all the information in those various
 >> nodes.  There is a minor amount of duplication (ie, MODIFY and VAR_DECL
 >> both have types), but thats not where we have siginificant memory
 >> lossage. SSA_NAMES themselves are fairly efficient and only exist once.
 >
 >Ok.  I was just trying to point out a deficiency in your system that I
 >perceived.  If you don't agree, then I certainly will not try to force the
 >point.  I'm just trying to point out stuff that might become a problem
 >down the line as early as possible, as opposed to letting you discover the
 >problem later when it may be harder to recover.  I'm truly not trying to
 >start a pointless flamewar. :)
And just so it's clear, it is appreciated, even if sometimes we argue or
don't take your advice, it is definitely appreciated.

 >> How do you deal with a stmt which has more than once DEF?  We have
 >> precious few, but they do exist.
 >
 >We don't.  They don't exist in SSA form.  The only feature we have not
 >implemented yet is inline assembly, and for that I plan to use lvalues
 >("by reference parameters") to represent the multiple outputs possible
 >from a single "asm statement". Everything else is fully implemented in
 >LLVM, and we have not had a problem so far.
ASMs are the root of all evil.  Oh wait, that was nested functions :-)



 >> > This is what I mean by integrating SSA as a first-class feature in your
 >> > representation.  How would this be represented in tree-ssa?
 >>
 >> a_2 = 1 + 2
 >> a_3 = a_2 + a_2
 >>
 >> we have 2 SSA_NAMES, allocated once.
 >>
 >>    SSA_NAME   and     SSA_NAME
 >>     /    \             /   \
 >>    a      3           a     2
 >>
 >> both of which could have been a single allocation if we chose, but it
 >> turns out to be less memory to allocate them as SSA_NAMEs as Diego has
 >> already pointed out.
 >
 >So, you're saying that it's better than using VAR_DECL's directly, which,
 >of course, carry a lot of baggage that you're not interested in.  Why use
 >them at all?
They're interesting when they refer to user variables from a debugging
standpoint.  I don't think they're particularly interesting when they
refer to expression temporaries.

More than once I've thought about what it would take to simply not have
_DECL nodes for expression temporaries.  I just haven't see a clean way
to make them go away within our current framework.

Andrew's recent work in operand walking actually makes it easier to do
some of this kind of stuff -- though we're certainly a long way from
being able to make that happen.

I would seriously consider banning stuff like TREE_OPERAND and TREE_CODE
(and instead expanding upon Andrew's framework) from the SSA optimizers
once we've past the first milestone of getting integrated into the mainline
tree.  But it's something I don't think we want to tackle right now.

jeff

Re: [tree-ssa] Maintaining/representing def-use/use-def information

[law]

In message <20031215205553.GA24610@atrey.karlin.mff.cuni.cz>, Zdenek Dvorak wri
tes:
 >Hello,
 >
 >> Ultimately, I dont see much difference other than implementation
 >> details...
 >
 >... and about three times more memory spent, I would estimate. For a
 >single assignment statement, we have:
 >
 >1) The var_decl node
Which was already going to exist anyawy.

 >2) The ssa name
Which are shared among every reference to the name version #.

 >3) modify_expr
Yes.    Particularly since we can't share them among lexically idential
statements.

 >4) operation_expr
Yes.  Particularly since we can't share these either.


 >+ pointers to link them together, versus
 >
 >1) single entity containing just the operation code and two pointers to
 >   the arguments (+additional information like type, etc).
And as I stated in a message yesterday, Andrew's recent work actually
takes us one step closer to this model.  Is it there yet?  Certainly not,
but I can see a day in the future (after initial integration with the
mainline) where we'd want to look at using Andrew's work as the basis
for all the SSA optimizers and ban looking at the underlying trees.  Hell,
the underlying trees might simply be able to disappear.

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

[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

[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

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

[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

[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

[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: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,

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

[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

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

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

[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

[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

[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

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

[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,

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

[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

[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

[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

[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,

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

[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