Re: Problem with the special live analyzer in global alloc

[Daniel Berlin <dberlin@dberlin.org>]

On Tue, 2005-08-23 at 22:10 -0500, Peter Bergner wrote:
> On Tue, 2005-08-23 at 21:26 +0200, Bernd Schmidt wrote:
> > As Jim points out, we may have to do that for IA64 anyway, so we could 
> > consider doing it on all targets.  Dan is correct that this can 
> > introduce new code that won't be eliminated.  One question is how often 
> > this is going to occur in practice.
> 
> The IBM iSeries (aka AS/400) compiler actually inserts definitions
> on edges where a pseudo/register is undefined.  However, unlike the
> discussion here, our "pseudo" definitions never lead to generated
> code
I listed that as a possible option, the problem is that you have to know
that they are pseudo definitions, and teach other things this too.
This is the part i alluded to being probably uglier than partial
liveness analysis itself.
> .  Our pseudo definitions were added to simplify some analysis
> phases in the compiler (eg, liveness can be simplified down to LIVE
> rather than LIVE & AVAL).  Note that we needed to handle these pseudo
> definitions specially in some cases so they don't reduce optimization
> opportunities. 
Like this :)

Is LIVE & AVAIL really that much slower these days for most programs?

I imagine if you have 300k bb's or 1.5 million live pseudos to consider,
it probably makes a real difference, but that's not *too* common in our
supported languages (30k bb's/150k pseudos is probably the practical
upper limit of what we see, though i'm sure someone is going to say
they've seen larger :P)


> I know we used to have a white paper describing the internals of the
> iSeries compiler (titled "The AS/400 Optimizing Translator"), but all
> of the links I can find are stale.  However, I did come across their
> patent (5,761,514) describing the idea: "Register allocation method
> and apparatus for truncating runaway lifetimes of program variables
> in a computer system".  I have no idea whether this was one of the
> patents made available by IBM for use by the OSS community or not.

Just FYI, I've read this patent, and regardless of whether you think
this is something should have patented, etc, the claims are broad enough
to cover any way as long as you are doing liveness analysis and then
inserting something into the instruction stream to truncate the ranges
(real, fake, whatever) .

However, if this is what you guys want to do, please don't let that stop
you.  Let me know if you want to go this route, and we'll work on
getting IBM to release it.

--Dan