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

[Andrew MacLeod <amacleod at redhat dot com>]

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