Re: Stack based-Register Based

"Jonathan Barker" <ucapjab@ucl.ac.uk>
1 Feb 2001 17:41:44 -0500

          From comp.compilers

Related articles
Stack based-Register Based vinoth@india.ti.com (Vinoth Kumar) (2001-01-19)
Re: Stack based-Register Based anton@mips.complang.tuwien.ac.at (2001-01-20)
Re: Stack based-Register Based vbdis@aol.com (2001-01-20)
Re: Stack based-Register Based roedy@mindprod.com (Roedy Green) (2001-01-26)
Re: Stack based-Register Based peter_flass@yahoo.com (2001-01-26)
Re: Stack based-Register Based andrewb@votehere.net (Andrew Berg) (2001-01-28)
Re: Stack based-Register Based rog@vitanuova.com (2001-02-01)
Re: Stack based-Register Based ucapjab@ucl.ac.uk (Jonathan Barker) (2001-02-01)
Re: Stack based-Register Based rpw3@rigden.engr.sgi.com (2001-02-04)
Re: Stack based-Register Based Martin.Ward@durham.ac.uk (2001-02-04)
Re: Stack based-Register Based anton@mips.complang.tuwien.ac.at (2001-02-04)
Re: Stack based-Register Based anton@mips.complang.tuwien.ac.at (2001-02-04)
Re: Stack based-Register Based joachim_d@gmx.de (Joachim Durchholz) (2001-02-15)
Re: Stack based-Register Based joachim_d@gmx.de (Joachim Durchholz) (2001-02-25)
[3 later articles]
| List of all articles for this month |

From: "Jonathan Barker" <ucapjab@ucl.ac.uk>
Newsgroups: comp.compilers
Date: 1 Feb 2001 17:41:44 -0500
Organization: Compilers Central
References: 01-01-124 01-01-137 01-01-162
Keywords: architecture, interpreter
Posted-Date: 01 Feb 2001 17:41:44 EST

> IOW: I claim that if our VM has 256 registers, our ISA has 32
> registers and our expression has 300 concurrent temporary values, the
> high level language can schedule the block down to 256 registers by
> adding stores and loads as appropriate. These stores and loads should
> not hinder the JIT or load-time compiler from also being able to
> generate an optimized register scheduling. In fact, the stores and
> loads added in should be ones that would have been added in anyhow if
> the compiler were optimizing directly from the 300 values to the 32
> values in a single step.
>
> I don't, however know if this is true. Anyone out there able to offer a
> better proof either way?


That would be nice, wouldn't it? Let's suppose that your optimisers
are 'associative' (there is probably an "official" term for this but I
don't know what it is)...


By 'associative optimiser' I mean an optimiser which transforms
semantically equivalent programs A and B into equivalently "good"
programs A' and B'. Note that A' and B' need not be the same, just
equivalently good under whatever criteria for optimisation are
desired.


If all your optimisers are associative, then your assertion must be
true since they must, pretty much by definition, leave semantics
unchanged.


Notice that an ideal optimiser *must* be associative. Given
semantically equivalent programs A and B, it must always produce
equivalently good code A' and B'. So if your optimisers are ideal,
your assertion is true.


However, I don't know that provably optimal (or even associative)
optimisers exist. But my limited knowledge on this subject leads me to
believe that most scheduling and register allocation algorithms use
heuristics of some sort (esp in the JIT case). If this is the case,
the quality of the output will almost certainly depend on the input,
even if the semantics are unchanged.


All the best


Jonathan


Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.