Re: Activation Records on Stack Based Machines

io@spunge.org (leibniz) writes:


> I am working on a small imperative language that uses a stack based
> virtual machine. I've searched/read about activation records, but
> all I found was register-based machines way of pushing activation
> records on the stack. Where do I place the return value of a
> function, save program counter, allocate space for local
> variables...etc. Can someone give me pointers on how that can be
> done on stack-based machines?


It is even easier on a stack-based VM: You allocate everyting on the
stack and use stack-top-relative addressing to access these. A
function call f(e1,e2,e3) could have the following structure:


    1) Evaluate e1 to ToS (Top of Stack).
    2) Evaluate e2 to ToS.
    3) Evaluate e3 to ToS.
    4) Jump to f, saving return address on ToS.


The function f will then do:


    1) Allocate local variables by pushing them on the stack.
    2) Execute body, accessing both parameters and local variables by
          offsets from ToS. The offsets are known at compile-time.
    3) Before return, the return value will be at the ToS. Now write
          this to the stack location that held the first parameter.
    4) Pop off local variables etc. down to the return address.
    5) Do a return (taking the return address from the ToS).


After returning, the caller does:


    5) Pop off two elements (number of parameters minus one). The value
          of the function will now be at ToS, with the rest of the stack
          unchanged.


There are a lot of variants to this theme, depending on what stack
operations are available and what features the language has. Also,
note that the above assumes that there is at least one parameter and
result to the call. If this is not the case, some small modifications
are required.


Several compiler books have detailed descriptions of compiling for
stack-based machines. A few suggestions:


    Programming Language Processors in Java
    David A. Watt & Deryck F. Brown
    Prentice Hall, 2000


    Modern Compiler Design
    Dick Grune, Henri E. Bal, Ceriel J.H. Jacobs & Koen G. Langendoen
    Wiley, 2000


Torben Mogensen

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