Re: Stack based-Register Based

  Andrew Berg <andrewb@votehere.net> writes:
>The TAO VM used in the new AmigaOS is register based, but they claim
>that you can define an unlimited number of registers. Whether it
>really is unlimited, or the limit is just really big, I don't know.
>What kind of expression would make 2^32 registers be "too few"?
>(That's an expression I would hate to meet in a dark alley.)


The TAO VM has 32-bit register specifiers? It must be quite
voluminous then.


Or does it have variable-sized specifiers? That would be additional
complexity in all components dealing with the VM code.


>Admittedly, the TAO stuff was designed to be compiled into native as
>it was loaded rather than being ever interpreted. However, many JAVA
>VMs have JITs which are attempting to do a very similar thing. Having
>register usage not obscured by DUPs, ROTs, PICKs, and DROPs can only
>help the JIT compiler.


Not really, because dealing with the stack instructions is pretty easy
for a JIT (as long as the stack depth is statically determinable).
The stack representation has the additional advantage of making it
explicit when a value is dead; on a register machine you can emulate
this feature by adding kill annotations (does TAO do this?).


>Since the stack is "virtually unlimited" it is quite likely to be
>larger than the number of physical registers.


That does not follow. E.g., in the JVM the stack is typically used
only within the code for a statement, and that usually requires only a
few registers.


>I wonder if any study has been done of a compiler which analizes the
>called routine's register usage and only saves those registers which
>both are overwritten by the called routine, and contain important
>values.


Typical calling conventions try to achieve that effect by having both
caller-saved and callee-saved registers, and allocating values to the
appropriate registers. There are also papers about interprocedural
register allocation.


>My intuition is that as long as the high
>level compiler is optimizing for a number of virtual registers which
>is greater than or equal to the number of physical registers that
>everything is good.


That depends on how sophisticated the register allocator of the
compiler is. With a simple priority-based colouring register
allocator without live range splitting, you might be right (but I am
not sure how this combines with caller/callee-saved registers).


However, with Briggs-style colouring (where the colouring order is
based on Chaitin-style simplification, where the number of registers
plays a role), and/or with live range splitting (where you split only
if you run out of registers) the allocation depends on the actual
number of registers.


Keeping the original register allocation would also constrict
instruction scheduling and some more sophisticated optimizations. It
would be interesting to see how much the combination of these effects
would hurt.


In any case, with the JVM the front end can view the locals as your
virtual registers, and perform colouring on them; you will get similar
results (just reserve 2-3 registers for the stack temporaries). The
major performance problem with the JVM in this approach is not the
stack, but that it does not separate integers and floats (in contrast
to many current architectures), and that the front end cannot
eliminate range checks, or perform strength reduction and induction
variable elimination for array accesses; so, if you want these
optimizations, the JIT has to perform them.


- anton
--
M. Anton Ertl Some things have to be seen to be believed
anton@mips.complang.tuwien.ac.at Most things have to be believed to be seen
http://www.complang.tuwien.ac.at/anton/home.html

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