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. 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. If I remember correctly (it's been a while since I
left the team):
1) All pseudo defs get the value of <bottom> so rematerialization,
etc. are not pessimized.
2) Pseudo definitions are ignored during the interference graph
construction (ie, they never cause edges to be added to the
interference graph).
3) More things I can't think of at the moment.
This was a win for the iSeries compiler since a fair number of
applications were/are written in RPG which is essentially a one
procedure application, so the number of basic blocks and live
ranges/webs can be quite high. I recall one program we ran into
that had about 150K basic blocks and about 1.5M live ranges.
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.
Peter
--
Peter Bergner
Linux on Power Toolchain
IBM Linux Technology Center
