Stack-based virtual machine function call/return implementation issues

Question

Today I decided to create a little stack-based virtual machine in C++11 for fun - everything was going pretty well until I got to function calling and returning from functions.

I've been trying to follow calling guidelines similar to x86 assembly but I'm getting really confused.

I have trouble dealing with stack base pointer offsets and with return values.

It seems very hard to keep track of registers used for return values and of arguments (for the function calls) on the stack.

I've created a simple assembly-like language and compiler. Here's a commented example (that my virtual machine compiles and executes). I tried to explain what's happening and to share my thoughts in the comments.

//!ssvasm

$require_registers(3);

// C++ style preprocessor define directives to refer to registers
$define(R0, 0);
$define(R1, 1);
$define(R2, 2); 

// Load the 2.f float constant value into register R0
loadFloatCVToR(R0, 2.f);

// I want to pass 2.f as an argument to my next function call:
// I have to push it on top of the stack (as with x86 assembly)
pushRVToS(R0);

// I call the FN_QUAD function here: calling a function pushes both
// the current `stack base offset` and the `return instruction index`
// on the stack
callPI(FN_QUAD); 

// And get rid of the now-useless argument that still lies on top of the stack
// by dumping it into the unused R2 register 
popSVToR(R2);

halt(); // Halt virtual machine execution



$label(FN_DUP); // Function FN_DUP - returns its argument, duplicated

// I need the arg, but since it's beneath `old offset` and `return instruction`
// it has to copied into a register - I choose R0 - ...

// To avoid losing other data in R0, I "save" it by pushing it on the stack
// (Is this the correct way of saving a register's contents?)
pushRVToS(R0);

// To put the arg in R0, I need to copy the value under the top two stack values
// (Read as: "move stack value offset by 2 from base to R0")
// (Is this how I should deal with arguments? Or is there a better way?)
moveSBOVToR(R0, 2);

// Function logic: I duplicate the value by pushing it twice and adding
pushRVToS(R0); pushRVToS(R0); addFloat2SVs();

// The result is on top of the stack - I store it in R1, to get it from the caller
// (Is this how I should deal with return values? Or is there a better way?)
popSVToR(R1);

popSVToR(R0); // Restore R0 with its old value (it's now at the top of the stack)

// Return to the caller: this pops twice - it uses `old stack base offset` and
// unconditionally jumps to `return instruction index`
returnPI();



$label(FN_QUAD); // Function FN_QUAD

pushRVToS(R0);
moveSBOVToR(R0, 2);

// Call duplicate twice (using the first call's return value as the second
// call's argument)
pushRVToS(R0); callPI(FN_DUP); popSVToR(R2);
pushRVToS(R1); callPI(FN_DUP); popSVToR(R2);

popSVToR(R0);
returnPI();

I've never programmed in assembly before, so I'm not too sure the techniques I'm using are correct (or efficient).

Is the way I'm handling arguments/return values/registers correct?

Should the caller of a function push the arguments, then call, then pop the arguments? It seems that using a register would be easier, but I've read that x86 uses the stack to pass arguments. I'm confident that the method I'm using here is incorrect.

Should I push both old stack offset and return instruction index on a function call? Or should I store the old stack offset in a register? (Or avoid storing it at all?)

Answer 1

What you're talking about is calling the call convention. In other words defining who builds the stack and how, caller or callee, and how should the stack look like.

They are many ways to do it and no one is better than the other, you just have to keep it conscistent.

As it would be to long to describe the different call convetions, you should just check the wikipedia article that is really complete.

But still quickly, the x86 C calling convention specifies that the caller must save its registers and build the stack and let the callee free of using the registers, to return a value or just simply to do things.

For the specific questions at the end of your post, the best is to have the same stack as C does, storing inside the last EIP and EBP and leave the registers free to use. Stack space is not as limited as the number of registers you have.

Answer 2

I solved this problem in my stack machine I've been working on, in the following way:

A void function call (with no parameters) instruction does something like this:

There is _stack[] (the main stack), and a _cstack[] (the call stack, containing information about calls, such as return size).

When calling a function, (the VCALL (void function call) is encountered) the following is done:

        u64& _next = _peeknext; //refer to next bytecode (which will be function address)
        AssertAbort((_next > -1) && (_next < _PROGRAM_SIZE), "Can't call function. Invalid address");
        cstack_push(ip + 2); //address to return to (current address +2, to account for function parameters next to function call)
        cstack_push(fp); //curr frame pointer
        cstack_push(_STACK_SIZE); //curr stack size
        cstack_push(0); //size of return value(would be 4 if int, 8 for long etc),in this case void
        ip = (_next)-1; //address to jump to (-1 to counter iteration incrementation of program counter(ip))

Then, when a RET (return) instruction is encountered, the following is done:

        AssertAbort(cstackhas(3), "Can't return. No address to return to.");
        u64 return_size = cstack_pop(); // pop size of return value form call stack
        _STACK_SIZE = cstack_pop(); //set the stack size to what it was before the function call, not accounting for the return value size
        fp = cstack_pop(); //reset the frame pointer to the current value to where it was before the function call
        ip = cstack_pop() - 1; //set program counter to addres storedon call stack from last function call

        _cstack.resize(_STACK_SIZE + return_size); //leave the top of the stack intact (size of return value in bytes), but disregard the rest.

This is probably useless to you now, as this question is quite old, but you can ask any questions if you wish :)

Answer 3

The best solution depends on the machine.

If push and pop in the stack are as fast as using registers (on chip stack or on chip L1 baked stack) and at the same time you are very limited on the number of registers it would make sense to use the stack.

If you have plenty of registers you can use some of them to store counters (pointers) or variables.

In general to make modules communicate with each other or to translate (or compile) other languages into your assembly you should specify an Application Binary Interface.

You should compare different ABIs for different hardware (or virtual machines) to find the techniques suitable for your machine. Once you define your ABI, programs should comply for binary compatibility.