Re: Caclulating operand stack size

clearm@comcast.net writes:
>I am developing a stack-based virtual machine similar to the JVM.
>Unfortunately, everytime I push or load something onto the operand
>stack, I have to do this:
>
>if(++SP == stackSize)
> growStack();


A simple way to deal with this problem is to allocate a stack as big
as you would ever grow it, and use that. To catch any overruns,
memory-protect the end of the stack. The cost of that is just in
virtual address space of your program, and (on OSs that do not
overcommit memory) swap space.


If you cannot do that (e.g., because you want to support many stacks),
you could memory-protect the end of the current stack and grow it when
you get a signal because of an overflow.


If that is not an option for you, then yes, you can calculate the
maximum stack depth for a basic block or a function, and check that at
the start.


You can even calculate the depth including any non-recursive direct
calls from the current function, and check for that, so you don't need
to check at every such call. You have to arrange the calling
convention appropriately; I would do it like this: the caller is
responsible for the checking and growing, and (for indirect calls)
accesses a field in the callee that contains information about the
maximum stack depth of the callee before the next check.


>I *think* it is possible to statically calculate a stack size limit
>using attribute grammars, but I'm not sure.


Yes, that is pretty straightforward. However, this means that you
have to keep the code generation and the stack depth calculation in
sync. It may be better to calculate the maximum stack depth by
symbolically executing the generated code (maybe during code
generation). If you can generate the code for the actual execution
and the symbolic execution out of the same source (e.g., something
like the Vmgen input language), you eliminate another error source.


About the possibility to statically calculate the maximum stack depth:
It is possible to design a VM where this is not generally possible
(e.g., because it has an instruction that does something run-time-data
dependent to the stack), but if you don't want that, just don't do it;
stack VMs typically don't do such things for the most part.


Even if all VM instructions have static stack effects, one can still
make life hard for static analysis through control flow (e.g., have a
loop that pushes a value on the stack on each iteration), but usually
one does not want to do this, either (both compilers and humans
typically don't generate such code). The JVM actually requires that
the stack contents are the same on both branches reaching a control
flow join.


However, if you do support features that make static depth
calculations impossible at the function level, you can at least
combine the checks for parts that can be statically computed, e.g.,
for blocks without control flow and without dynamic-stack-effect VM
instructions.


- anton
--
M. Anton Ertl
anton@mips.complang.tuwien.ac.at
http://www.complang.tuwien.ac.at/anton/home.html

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