FVM is an embedded programming system that utilizes a language with a C-style syntax. Its implementation consists of two parts: A compiler that compiles source code to byte code, and a virtual machine that links compiled code with externals at runtime (functions, classes, etc) and executes its byte code.
Sum the contents of a text file that contains integers:
#define IO_READ 1 #define IO_WRITE 2 int sum_file(string filename) { File file = new File(); if (!file->open(filename, IO_READ)) { print("Error: Unable to open file"); delete file; return -1; } int sum = 0; while (!file->eof()) { sum = sum + file->read_int(); } file->close(); delete file; return sum; } print("The sum of the file's contents is %d.\n", sum_file("inputfile.txt"));
// Generated assembly: // Line 4: int sum_file(string filename) // Function int sum_file 0x0 jmp 0x42 // Arg: string filename // Line 6: File file = new File(); 0x2 pushc 0x10000 // Call ctor File 0x4 call_linked_cc 0x10000 # Pop to File file with id 65537 (0x10001) 0x6 popv 0x10001 // Line 7: if (!file->open(filename, 1)) // Call function open in File // Arg index 0 = filename 0x8 pushv 0x10000 // Arg index 1 = 1 # Push constant int = 1 with id 131072 (0x20000) 0xA pushc 0x20000 0xC load_v_addr 0x10001 0xE call_lcfunc 0x0 0x10 not 0x11 jz 0x20 // Line 9: print("Error: Unable to open file"); // Call linked function print with id 1 # Push constant string = "Error: Unable to open file" with id 131073 (0x20001) 0x13 pushc 0x20001 0x15 call_lfunc 0x6 0x17 pop // Line 10: delete file; 0x18 pushv 0x10001 0x1A call_linked_dc // Line 11: return -1; # Push constant int = 1 with id 131072 (0x20000) 0x1B setv_c 0x10003 0x6 # Reduced and simplified constant NEG 1 to pushc -1 id = 0x6 # Reduced PUSHC, POPV 0x1E jmp 0x40 // Line 12: } // Line 14: int sum = 0; # Push constant int = 0 with id 65537 (0x10001) 0x20 setv_c 0x10002 0x10001 # Pop to int sum with id 65538 (0x10002) # Reduced PUSHC, POPV // Line 15: while (!file->eof()) // condition !file->eof() // Call function eof in File 0x23 load_v_addr 0x10001 0x25 call_lcfunc 0x2 0x27 not 0x28 jz 0x35 // Line 17: sum = sum + file->read_int(); 0x2A pushv 0x10002 // Call function read_int in File 0x2C load_v_addr 0x10001 0x2E call_lcfunc 0x3 0x30 add # Pop to int sum with id 65538 (0x10002) 0x31 popv 0x10002 // Line 18: } 0x33 jmp 0x23 // Line 20: file->close(); // Call function close in File 0x35 load_v_addr 0x10001 0x37 call_lcfunc 0x1 0x39 pop // Line 21: delete file; 0x3A pushv 0x10001 0x3C call_linked_dc // Line 22: return sum; 0x3D setv_v 0x10003 0x10002 # Reduced PUSHV, POPV // Line 23: } 0x40 ret_func 0x10003 // End function int sum_file // Line 25: print("The sum of the file's contents is %d.\n", sum_file("inputfile.txt")); // Call linked function print with id 1 # Push constant string = "The sum of the file's contents is %d. " with id 0 (0x0) 0x42 pushc 0x0 // Call function sum_file at loc 0 0x44 frame_create 0x1 // Arg 0x10000 filename = "inputfile.txt" # Push constant string = "inputfile.txt" with id 1 (0x1) 0x46 setv_c 0x10000 0x1 # Reduced PUSHC, POPV 0x49 call_func 0x2 0x4B frame_destroy 0x1 0x4D pushc 0x2 0x4F call_lfunc 0x1 0x51 pop
The compiler runs a preprocessor on each input file, then does a two-pass compilation of each translation unit using a recursive descent parser. The first pass identifies signatures and types of functions, structures, classes and variables. The second pass is code generation. Next, the following optimizations are applied in multiple passes:
For example, the expression "2 * ((13 - 4) * 142 + 3 * i + (133 * 23 * (4 - 2) - 3 * (20 + 40)))" is simplified to "a * i + b" where a and b are constants. Similar folding optimizations are applied to binary, comparison and other operators acting on constants.
// Line 6: res = 2 * ((13 - 4) * 142 + 3 * i + (133 * 23 * (4 - 2) - 3 * (20 + 40))); # Push constant int = 3 with id 65537 (0x10001) 0xF pushc 0x10001 0x11 pushv 0x10000 0x13 mul # Push constant int = 2 with id 65538 (0x10002) 0x14 pushc 0xB # Push constant int = 13 with id 65539 (0x10003) # Push constant int = 4 with id 65540 (0x10004) # Reduced and simplified constant SUB 4, 13 to pushc 9 id = 0x2 # Push constant int = 142 with id 65541 (0x10005) # Reduced and simplified constant MUL 142, 9 to pushc 1278 id = 0x3 # Push constant int = 133 with id 65542 (0x10006) # Push constant int = 23 with id 65543 (0x10007) # Reduced and simplified constant MUL 23, 133 to pushc 3059 id = 0x4 # Push constant int = 4 with id 65540 (0x10004) # Push constant int = 2 with id 65538 (0x10002) # Reduced and simplified constant SUB 2, 4 to pushc 2 id = 0x5 # Reduced and simplified constant MUL 2, 3059 to pushc 6118 id = 0x6 # Push constant int = 3 with id 65537 (0x10001) # Push constant int = 20 with id 65544 (0x10008) # Push constant int = 40 with id 65545 (0x10009) # Reduced and simplified constant ADD 40, 20 to pushc 60 id = 0x7 # Reduced and simplified constant MUL 60, 3 to pushc 180 id = 0x8 # Reduced and simplified constant SUB 180, 6118 to pushc 5938 id = 0x9 # Reduced and simplified constant ADD 5938, 1278 to pushc 7216 id = 0xA # Reduced and simplified constant MUL 7216, 2 to pushc 14432 id = 0xB 0x16 add # Pop to int res with id 1 (0x1) 0x17 popv 0x1
Consider the expression "func(x) + func(y)". An obvious peephole optimization is to allow the second call to func to reuse the stack frame that was created for the first call for func, only updating the parameter passed. A more complex example involves live variable analysis. Consider the quicksort routine:
void qsort(int l, int r) { int i = l, j = r; int v = A[(l + r) / 2]; while (i <= j) { while (A[i] < v) { i++; } while (A[j] > v) { j--; } if (i > j) { break; } int v = A[i]; A[i] = A[j]; A[j] = v; i++; j--; } if (l < j) { qsort(l, j); } if (r > i) { qsort(i, r); } }
At the first recursive call to qsort, the variables i and r are still "alive" (as determined by data flow analysis), so their values are saved. At the second recursive call to qsort, no variables need to be saved since they are no longer live at the point of the function call. FVM will re-use the memory locations occupied by l, j, i, r and v. I do not pass the array in the function as, currently, all variables are passed by value, and copying a very large array repeatedly is not a good idea.
The last optimization consists of replacing redundant instructions, such as a jmp to a location immediately following itself, or instructions for which a mnemonic exists, such as replacing pushv(x), incr, popv(x) with incrv(x).
The final list of instructions is assembled to byte code.
The following is an example of linking functions, variables and classes to FVM.
class File { public: bool open(const char* filename, int mode) { ifs.open(filename); return ifs.is_open(); } bool eof() { return ifs.eof(); } void close() { ifs.close(); } int read_int() { int v; ifs >> v; return v; } private: std::ifstream ifs; }; class TestClass { public: void test() { std::cout << "abc" << std::endl; } void print_message(int n) { std::cout << "Test class, test message = " << n << std::endl; } int test_value() { return 234; } TestClass(int v) : val(v) { std::cout << "TestClass ctor" << std::endl; } ~TestClass() { std::cout << "TestClass dtor" << std::endl; } int val; }; TestClass* create_test_class(int value) { return new TestClass(value); } void print_test_class(TestClass* t) { std::cout << t->val << std::endl; } ... Compiler c; c.LinkFunction(new LinkedFunction1<float, float>(sinf, "sin")); c.LinkFunction(new LinkedFunction1<float, float>(cosf, "cos")); LinkedClass<TestClass>* TestClass_linked = new LinkedClass1<TestClass, int>("TestClass"); TestClass_linked->LinkClassFunction(new LinkedClassFunction0<TestClass, void>(&TestClass::test, "test")); TestClass_linked->LinkClassFunction(new LinkedClassFunction0<TestClass, int>(&TestClass::test_value, "test_value")); TestClass_linked->LinkClassFunction(new LinkedClassFunction1<TestClass, void, int>(&TestClass::print_message, "print_message")); c.LinkClass(TestClass_linked); c.LinkFunction(new LinkedFunction1<TestClass*, int>(create_test_class, "create_test_class")); c.LinkFunction(new LinkedFunction1<void, TestClass*>(print_test_class, "print_test_class")); LinkedClass<File>* FileClass_linked = new LinkedClass0<File>("File"); FileClass_linked->LinkClassFunction(new LinkedClassFunction2<FileClass, bool, const char*, int>(&FileClass::open, "open")); FileClass_linked->LinkClassFunction(new LinkedClassFunction0<FileClass, void>(&File::close, "close")); FileClass_linked->LinkClassFunction(new LinkedClassFunction0<FileClass, bool>(&File::eof, "eof")); FileClass_linked->LinkClassFunction(new LinkedClassFunction0<FileClass, int>(&File::read_int, "read_int")); c.LinkClass(FileClass_linked); Program* prog = c.Compile("test.txt"); prog->GetVariable("from_prog")->set_int(123); vm.Run(prog, prog->namespaces, false); float a =(float)*prog->GetVariable("a"); float b = (float)*prog->GetVariable("b"); std::vector<int> bc = Variable::ArrayToType<int>(*prog->GetVariable("bc")); std::vector<const char*> test_strings = Variable::ArrayToType<const char*>(*prog->GetVariable("s")); std::vector<float> arr = Variable::ArrayToType<float>(*prog->GetVariable("arr")); delete prog;
C++ integration allows C++ code to interact with the VM by linking functions and classes, and by passing or retrieving variables. Cast operators are provided for primitive datatypes, while explicit methods exist to quickly convert arrays and structures from the VM's memory to and from types that are compatible with the C++ program. This is especially useful for function calls or calling class methods from within byte code running in the VM, or when passing complex structures to the VM. Structures (classes without methods) can be defined from within source code compiled in FVM and can be passed to and from C++ code through a custom function that uses FVM's Variable data type as a parameter to interface members.
The height of each bar represents the time taken to run a script. Lower is better.
A loop with an expression that can be partly folded. Since this can be folded to a trivial expression, FVM's advantage increases as the complexity of the function increases.
int num = 10000000, res = 0; for (int i = 0; i < num; i++) { res = 2 * ((13 - 4) * 142 + 3 * i + (133 * 23 * (4 - 2) - 3 * (20 + 40))); }
Calculate fib(32) of the Fibonacci sequence recursively.
int fib(int n) { if (n < 2) { return 1; } return fib(n - 1) + fib(n - 2); } print_int(fib(32));
Sort 50,000 integers using quicksort.
int length = 50000; int A[length]; for (int i = 0; i < length; i++) { A[i] = (43 * i) % 50; } void qsort(int l, int r) { int i = l, j = r; int v = A[(l + r) / 2]; while (i <= j) { while (A[i] < v) { i++; } while (A[j] > v) { j--; } if (i > j) { break; } int v = A[i]; A[i] = A[j]; A[j] = v; i++; j--; } if (l < j) { qsort(l, j); } if (r > i) { qsort(i, r); } } qsort(0, length - 1);
int num = 300; int steps = 5000; float arr[num]; for (int i = 0; i < num; i++) { float v = 0; for (int j = 0; j < steps; j++) { float num = 3.14159f * j; num = num / steps; v = 2 * sin(i * v) + cos(num) - 2 * cos(v); } if (v < 0) { v = -v; } arr[i] = v; }
Although FVM produces fairly well-optimized assembly, Lua is significantly faster due to the fact that its stack-based VM uses simpler types in memory, and because it directly makes use of registers. From what could be determined through benchmarking, Python's optimization is far from comparable, leaving its VM with a lot more bloat to deal with. However, FVM's main advantage over these embeddable languages is its ease of integration with C++ code bases.