Simple virtual machine in C

Question

I've been learning about compiled and interpreted languages. I decided to start somewhere by writing a virtual machine designed for a C-like language.

I already plan to add other features like a callstack for procedures and memory addressing for the stack and callstack. I'm already planning to group globals into a singleton struct.

How can I improve this VM any more other than the features I've mentioned? Also, is there a way to add better float support rather than cross converting integers and floats? Is there a better way to implement the stack?

Don't hold anything back in your review!

#include <stdio.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdlib.h>
bool running = true;
// index pointers should NEVER go under 0...
uint8_t ip=0, sp=0, callbp=0, callsp=0;
// we need this register stuff to save necessary values!
// technically this is still a stack machine since almost everything we do fiddles with the stack.
// saving and loading from registers still requires the stack.
enum {
 r1=0,
 r2, r3
};
uint64_t reg[3];
typedef enum {
 // push and pop are always assumed to hold a long int
 nop=0,
 push, pop, // 1
 add, fadd, sub, fsub, // 3
 mul, fmul, idiv, fdiv, mod, // 7
 jmp, lt, gt, cmp /* cmp does == */, 
 jnz, jz,
 inc, dec, shl, shr, //and, or, xor,
 // cpy copies the top of the stack and pushes that to the top.
 cpy, swap,
 load, // put register value to top of stack.
 store, // stores top of stack to register.
 halt,
} InstrSet;
#define STACKSIZE 256
uint64_t stack[STACKSIZE];
void exec(uint64_t *code)
{
 union {
 uint64_t ll;
 double d;
 char c[8];
 } converter;
 uint64_t b, a;
 double da, db;
 static const void *dispatch[] = {
 &&exec_nop,
 &&exec_push, &&exec_pop,
 &&exec_add, &&exec_fadd, &&exec_sub, &&exec_fsub,
 &&exec_mul, &&exec_fmul, &&exec_idiv, &&exec_fdiv, &&exec_mod,
 &&exec_jmp, &&exec_lessthan, &&exec_grtrthan, &&exec_cmp,
 &&exec_jnz, &&exec_jz,
 &&exec_inc, &&exec_dec, &&exec_shl, &&exec_shr, //&&exec_and, &&exec_or, &&exec_xor,
 &&exec_cpy, &&exec_swap, &&exec_load, &&exec_store,
 //&&exec_z,
 &&exec_halt
 };
 //printf("current instruction == \'%u\'\n", instr);
 if( code[ip] > halt || code[ip] < nop ) {
 printf("handled instruction exception. instruction == \'%llu\'\n", code[ip]);
 goto *dispatch[halt];
 return;
 }
 #define DISPATCH() goto *dispatch[ code[ip] ]
 DISPATCH();
exec_nop:; return;
exec_halt:;
 running = false;
 printf("vm done\n");
 return;
exec_cpy:; // makes a copy of the current value at the top of the stack and places the copy at the top.
 a=stack[sp];
 stack[++sp] = a;
 printf("copied %llu, top of stack: %llu\n", stack[sp-1], stack[sp]);
 return;
exec_swap:; // swaps two, topmost stack values.
 a = stack[sp--];
 b = stack[sp--];
 stack[sp++] = b;
 stack[sp++] = a;
 printf("swapped: a == %llu | b == %llu\n", stack[sp-2], stack[sp-1]);
 return;
exec_load:; // stores a register value into the top of the stack.
 a = code[++ip];
 stack[sp] = reg[a];
 printf("loaded %llu from reg[%llu]\n", stack[sp], a);
 return;
exec_store:; // pops value off the stack into a register.
 a = code[++ip];
 reg[a] = stack[sp--];
 printf("stored %llu to reg[%llu] | reg[%llu] = %llu\n", reg[a], a, a, stack[sp+1]);
 return;
// various jumps
exec_jmp:; // unconditional jump
 ip = code[++ip];
 printf("jumping to... %u\n", ip);
 DISPATCH();
exec_jnz:; // Jump if Not Zero = JNZ
 ++ip;
 if( stack[sp] ) {
 ip=code[ip];
 printf("jnz'ing to... %u\n", ip);
 DISPATCH();
 }
 return;
exec_jz:; // Jump if Zero = JZ
 ++ip;
 if( !stack[sp] ) {
 ip=code[ip];
 printf("jz'ing to... %u\n", ip);
 DISPATCH();
 }
 return;
// conditional stuff. Conditionals are always done signed I believe.
exec_lessthan:;
 b = stack[sp--];
 a = stack[sp--];
 stack[++sp] = (int64_t)a < (int64_t)b;
 printf("less than result %llu < %llu == %llu\n", a, b, stack[sp]);
 return;
exec_grtrthan:;
 b = stack[sp--];
 a = stack[sp--];
 stack[++sp] = (int64_t)a > (int64_t)b;
 printf("greater than result %llu > %llu == %llu\n", a, b, stack[sp]);
 return;
exec_cmp:;
 b = stack[sp--];
 a = stack[sp--];
 stack[++sp] = (int64_t)a == (int64_t)b;
 printf("compare result %llu == %llu %llu\n", a, b, stack[sp]);
 return;
// push and pop
exec_push:; // put an item on the top of the stack
 sp++;
 if( !sp ) { // if we increment sp and sp is 0, we ran out of stack memory.
 printf("stack overflow!\n");
 goto *dispatch[halt];
 }
 stack[sp] = code[++ip];
 printf("pushing %llu\n", stack[sp]);
 return;
exec_pop:; // reduce stack
 if( sp )
 --sp;
 if( sp==255 ) { // if we decrement sp and sp's bits went all 1, we popped too much!
 printf("stack underflow!\n");
 goto *dispatch[halt];
 }
 printf("popped, stack pointer 0x%x\n", sp);
 return;
// arithmetic maths. order: int math, float math is last.
exec_add:;
 b = stack[sp--];
 a = stack[sp--];
 // we then add the result and push it to the stack
 stack[++sp] = a+b; // set the value to the top of the stack
 printf("add result %llu\n", stack[sp]);
 return;
exec_sub:;
 b = stack[sp--];
 a = stack[sp--];
 stack[++sp] = b-a;
 // 0x8... is uint64_t's sign bit
 if( stack[sp] & 0x8000000000000000 )
 printf( "sub result %lli\n", (int64_t)stack[sp] );
 else printf( "sub result %llu\n", stack[sp] );
 return;
exec_mul:;
 b = stack[sp--];
 a = stack[sp--];
 stack[++sp] = a*b;
 printf("mul result %llu\n", stack[sp]);
 return;
exec_idiv:;
 b = stack[sp--];
 a = stack[sp--];
 if( a==0 ) {
 printf("div by 0 not allowed, restoring stack\n");
 sp += 2;
 return;
 }
 stack[++sp] = b/a;
 printf("div result %llu\n", stack[sp]);
 return;
exec_mod:;
 b = stack[sp--];
 a = stack[sp--];
 stack[++sp] = b%a;
 printf("mod result %llu\n", stack[sp]);
 return;
exec_inc:;
 stack[sp]++;
 printf("increment result %llu\n", stack[sp]);
 return;
exec_dec:;
 stack[sp]--;
 printf("decrement result %llu\n", stack[sp]);
 return;
exec_shl:;
 b = stack[sp--];
 a = stack[sp--];
 stack[++sp] = b<<a;
 printf( "bit shift left result %llu\n", stack[sp] );
 return;
exec_shr:;
 b = stack[sp--];
 a = stack[sp--];
 stack[++sp] = b>>a;
 printf( "bit shift right result %llu\n", stack[sp] );
 return;
// floating point maths
exec_fadd:;
 // gotta convert long int bits into float/double bits
 converter.ll = stack[sp--];
 db = converter.d;
 converter.ll = stack[sp--];
 da = converter.d;
 //printf("da %f | db %f\n", da, db);
 converter.d = da+db;
 stack[++sp] = converter.ll;
 printf("f add result %f\n", converter.d);
 return;
exec_fsub:;
 converter.ll = stack[sp--];
 db = converter.d;
 converter.ll = stack[sp--];
 da = converter.d;
 //printf("da %f | db %f\n", da, db);
 converter.d = db-da;
 stack[++sp] = converter.ll;
 printf("f sub result %f\n", converter.d);
 return;
exec_fmul:;
 converter.ll = stack[sp--];
 db = converter.d;
 converter.ll = stack[sp--];
 da = converter.d;
 //printf("da %f | db %f\n", da, db);
 converter.d = da*db;
 stack[++sp] = converter.ll;
 printf("f mul result %f\n", converter.d);
 return;
exec_fdiv:;
 converter.ll = stack[sp--];
 db = converter.d;
 converter.ll = stack[sp--];
 da = converter.d;
 printf("da %f | db %f\n", da, db);
 if( da==0 ) {
 printf("fdiv by 0.0 not allowed, restoring stack\n");
 sp += 2;
 return;
 }
 converter.d = db/da;
 stack[++sp] = converter.ll;
 printf("f div result %f\n", converter.d);
 return;
}
uint64_t get_file_size(FILE *pFile)
{
 if( !pFile )
 return 0;
 fseek(pFile, 0, SEEK_END);
 uint64_t size = ftell(pFile);
 rewind(pFile);
 return size;
}
int main(void)
{
 // floats are converted to double
 uint64_t program[] = {
 // to deal with floats, we first convert them to an unsigned longs bit value
 push, 0,
 push, 0x4014000000000000,
 fdiv,
 pop,
 halt
 };
 while( running ) {
 exec( program );
 ip++;
 }
 return 0;
}

• Daerdemandt: Why not switch though? If it's for optimisation then you have to compare performances of compiled code (with relevant flags) because compilers get too fancy. (not a C pro, just having read this). Also, why hold the stack globally but pass the code as argument?
• user3629249: you cannot execute code that is located on the stack. Code has to be in an area where the memory is marked as executable.
• user3629249: the code should be checking the returned value from fseek() and from ftell() to assure the operation was successful.
• user3629249: exec() is a well known system function, it is very poor programming practice to name your function that same as a system function name.
• user3629249: taking the address of a label is non standard, so will not work everywhere and causes the compiler to output a warning message/ This applies to every entry in the dispatch[] array.

Answer 1

I see a number of things that may help you improve your program.

Don't take the address of a label

Taking the address of a label is NOT supported by the standard and is, to my knowledge, solely a feature of gcc. Besides the fact that this is a non-standard extension, it's also not a very good way to express what you're trying to do. See the next suggestion for a better way.

Use a switch where appropriate

A much more direct, efficient, and portable method for exec would be to use a switch instead of goto. It's more efficient and also easily handles the illegal opcodes via a default case. Simply use your enum contants and eliminate the dispatch table. This would also alert you to the fact that lessthan, grtrthan as labels could instead be lt and gt to match the enum declarations.

Labels are not statements

A label is not a statement and does not need a terminating semicolon.

Use portable constants for printing

On your machine, %llu may well be the correct printf format for printing a uint64_t, but on my 64-bit machine, it would be %lu. Rather than having to guess, simply use the constants defined in <intypes.h> and do it like this:

printf("loaded %" PRIu64 " from reg[%" PRIu64 "]\n", stack[sp], a);

Keep closely associated variables in a struct

The instruction pointer ip, the registers, the other pointers and the stack in your virtual machine are all very closely associated. It would make more sense to collect those all together rather than having them be global variables.

Use const where practical

The current exec() routine does not (and should not) modify the passed code, and so it should be declared const:

void exec(const uint64_t * code)

Eliminate global variables where practical

Having routines dependent on global variables makes it that much more difficult to understand the logic and introduces many opportunities for error. Eliminating global variables where practical is always a good idea. In this case, if you wrap all of the associated values into a struct as in the previous suggestion, then you can pass a pointer to the struct into exec. This has many benefits, including the ability to have multiple simultaneous virtual machines running at the same time.

Create a reset function

Real CPUs have a reset pin which sets the machine to a defined, known state. You could implement a reset function for the virtual machine as well that could take a pointer to the vm struct as suggested above.

Make functions coherent and atomic where practical

The exec function doesn't, by itself, increment the ip. This is a very odd choice and weakens that coherence of the program. Instead, have each instruction appropriately update ip and the ugly DISPATCH() macro can be deleted.

Eliminate ambiguous code

The code currently contains this line:

ip = code[++ip];

The problem with that is that ip is updated twice. What is really meant is this:

ip = code[ip + 1];

This assures that ip is only updated once, unambiguously.

Omit return 0

When a C or C++ program reaches the end of main the compiler will automatically generate code to return 0, so there is no need to put return 0; explicitly at the end of main.

Note: when I make this suggestion, it's almost invariably followed by one of two kinds of comments: "I didn't know that." or "That's bad advice!" My rationale is that it's safe and useful to rely on compiler behavior explicitly supported by the standard. For C, since C99; see ISO/IEC 9899:1999 section 5.1.2.2.3:

[...] a return from the initial call to the main function is equivalent to calling the exit function with the value returned by the main function as its argument; reaching the } that terminates the main function returns a value of 0.

For C++, since the first standard in 1998; see ISO/IEC 14882:1998 section 3.6.1:

If control reaches the end of main without encountering a return statement, the effect is that of executing return 0;

All versions of both standards since then (C99 and C++98) have maintained the same idea. We rely on automatically generated member functions in C++, and few people write explicit return; statements at the end of a void function. Reasons against omitting seem to boil down to "it looks weird". If, like me, you're curious about the rationale for the change to the C standard read this question. Also note that in the early 1990s this was considered "sloppy practice" because it was undefined behavior (although widely supported) at the time.

So I advocate omitting it; others disagree (often vehemently!) In any case, if you encounter code that omits it, you'll know that it's explicitly supported by the standard and you'll know what it means.

• ratchet freak: A small little point: pointer based bitcasts between double and uint64 violate C++'s strict aliasing, memcpy like I suggested will always work. And it's intrinsic enough that the actual copy will get optimized out.
• Nergal: true but this VM is in C. I need it to be as fast as possible (on linux), the engine will be C++ but the vm will be implemented as a static library.
• ratchet freak: C++ can be as fast as C if you know what you are doing. Speed hasn't been a reason to choose C over C++ in a long time.
• Nergal: I still dislike C++'s strict aliasing and stronger typing. There's a good reason why I'll be using C++ on my game engine and there's a good reason why I'm using C on my (unnamed for now) scripting language ;)
• Edward: @Nergal: in C++, one could easily use something like a Variant object to handle such conversions efficiently. If I have time later today, I'll post a question showing this technique.

Answer 2

I would add the (currently global) VM state as a parameter to the exec function. This will make exec reentrant and allows multiple VMs working in parallel.

I would prefer a switch for dispatch, it reads cleaner, and there is less chance of the jump table being messed up because you miscounted.

Just a stack with only a view to the top 2 elements and 3 registers is very likely not enough. It's not Turing complete in its current form. You cannot sort an array with it for example.

Add bounds checks for storing and loading the registers. Add bounds checks for stack over/undeflow as well.

For a VM to be useful it needs to interact with the outside world, that means opcodes for input and output from peripherals/game engine.

Stack implementation is fine (except for the bounds check) though using union to bitcast between types is Undefined Behavior in C++. You will need to use a memcpy to do the bitcast:

exec_fadd:;
 // gotta convert long int bits into float/double bits
 memcpy(&db, &stack[sp--], sizeof(db));
 memcpy(&da, &stack[sp--], sizeof(da));
 //printf("da %f | db %f\n", da, db);
 double res = da+db;
 memcpy(stack[++sp], &res, sizeof(res));
 printf("f add result %f\n", res );
 return;

• Nergal: I'm assuming that for it to be turing complete, I would require addressing to random areas in the stack correct?
• ratchet freak: @Nergal yeah or an arbitrary number of registers, or a auxiliary bit or addressable memory
• Nergal: which would u recommend for a stack-based VM? To be turing complete that is.
• Deduplicator: Yep, C++ is stricter with aliasing than C. Lucky this is C.