|
|
@@ -0,0 +1,239 @@ |
|
|
/** |
|
|
* Educational Stack-based VM. |
|
|
* |
|
|
* See also Register-based VM example: https://gist.github.com/DmitrySoshnikov/6407781 |
|
|
* |
|
|
* by Dmitry Soshnikov <[email protected]> |
|
|
* MIT Stye License (C) 2015 |
|
|
*/ |
|
|
|
|
|
var _stack = []; // main evaluation stack |
|
|
|
|
|
var _pc = 0; // program counter |
|
|
|
|
|
var _regs = {$a: 0, $b: 0, $c: 0, $d: 0}; // generic registers |
|
|
|
|
|
var $sp; // stack pointer |
|
|
var $fp; // frame pointer |
|
|
|
|
|
var _running = false; // whether the machine is running |
|
|
|
|
|
// --------------------------------------------------------------- |
|
|
// 1. Opcodes (directly in assembly mnemonics for bravity). |
|
|
// |
|
|
// In real machine this would be actual binary code of of an |
|
|
// instruction corresponding to the assembly mnemonic. |
|
|
// --------------------------------------------------------------- |
|
|
var ops = { |
|
|
// Stops the execution. |
|
|
halt: function() { |
|
|
_running = false; |
|
|
}, |
|
|
|
|
|
// Moves contents to a register. |
|
|
mov: function(r, v) { |
|
|
_regs[r] = eval(v); |
|
|
}, |
|
|
|
|
|
// Sums two registers, result is in the first one. |
|
|
add: function(r1, r2) { |
|
|
_regs[r1] = _regs[r1] + _regs[r2]; |
|
|
}, |
|
|
|
|
|
// Pushes on the stack advancing the stack pointer. |
|
|
push: function(v) { |
|
|
_stack.push(eval(v)); |
|
|
$sp = _stack.length - 1; |
|
|
}, |
|
|
|
|
|
// Pops a value from top of the stack. If the register |
|
|
// is passed, stores value there. |
|
|
pop: function(r) { |
|
|
var v = _stack.pop(); |
|
|
$sp = _stack.length - 1; |
|
|
// Pop may provide a register to store the value. |
|
|
if (r) { |
|
|
_regs[r] = v; |
|
|
} |
|
|
return v; |
|
|
}, |
|
|
|
|
|
/** |
|
|
* Calls a procedure. |
|
|
* Caller pushes params on the stack, and the |
|
|
* `call` in addition does the routine work by saving |
|
|
* the frame pointer (`$fp`), and saving the return address. |
|
|
* The return value is always passed in the `$a` (accumulator) register. |
|
|
* All together it's an Activation Record (AR, aka a "stack frame"): |
|
|
* |
|
|
* AR: |
|
|
* |
|
|
* ----------- |
|
|
* param1 |
|
|
* param2 Caller's reponsibility |
|
|
* ... |
|
|
* paramN |
|
|
* ----------- |
|
|
* fp Callee's responsibility |
|
|
* ret addr (pc + 1) |
|
|
* ----------- |
|
|
*/ |
|
|
call: function(proc) { |
|
|
this.push($fp); // Save caller's frame pointer |
|
|
|
|
|
$fp = $sp - 1; // And set it to proc params |
|
|
|
|
|
this.push(_pc + 1); // Save the return address (follows the `call`) |
|
|
|
|
|
this.jmp(_labels[proc + ':']); // actual control transfer to procedure |
|
|
}, |
|
|
|
|
|
/** |
|
|
* This version uses "Callee clean-up" convention, meaning the callee |
|
|
* removes all passed params from the stack. The `n` param says how many |
|
|
* param (bytes in real machines) to remove from the stack. As the result |
|
|
* of this instruction the whole AR is pop from the stack, and the control is |
|
|
* transferred back to the caller. |
|
|
* |
|
|
* Notice, since the callee cleans everything up, this convention doesn't |
|
|
* support passing of variant number of params. |
|
|
*/ |
|
|
ret: function(n) { |
|
|
n = n || 0; // number of params (bytes) to pop |
|
|
|
|
|
// Return address is restored. |
|
|
_pc = this.pop(); |
|
|
// Don't advance PC in main cycle since we just changed it. |
|
|
_shouldAdvancePc = false; |
|
|
|
|
|
// Params unwind. |
|
|
while (n > 0) { |
|
|
this.pop(); |
|
|
n--; |
|
|
} |
|
|
|
|
|
// Caller's fp is restored. |
|
|
$fp = this.pop(); |
|
|
}, |
|
|
|
|
|
jmp: function(addr) { |
|
|
_pc = addr; |
|
|
// Tell CPU don't advance pc since we just changed it in `jmp`. |
|
|
_shouldAdvancePc = false; |
|
|
}, |
|
|
}; |
|
|
|
|
|
// --------------------------------------------------------------- |
|
|
// 2. Assembler. In real world has two passes: at first collects all labels, |
|
|
// in the second replaces labels with addresses and actually translates |
|
|
// to machine code. Here we only will collect the labels, and remove them |
|
|
// from the program, skipping the translation to byte-code for brevity |
|
|
// (the program runner will work directly with assembly mnemonics) |
|
|
// --------------------------------------------------------------- |
|
|
|
|
|
// A map from label id to address in the program. |
|
|
var _labels = {}; |
|
|
|
|
|
function assemble(program) { |
|
|
var translated = []; |
|
|
var labelsCount = 0; |
|
|
for (var i = 0; i < program.length; i++) { |
|
|
// if it's a label, record the address. |
|
|
if (/:$/.test(program[i])) { |
|
|
_labels[program[i]] = i - labelsCount; |
|
|
labelsCount++; |
|
|
continue; |
|
|
} |
|
|
translated.push(program[i]); |
|
|
} |
|
|
return translated; |
|
|
} |
|
|
|
|
|
|
|
|
// --------------------------------------------------------------- |
|
|
// 3. CPU |
|
|
// Main CPU cycle of running the program: "fetch, decode, eval". |
|
|
// --------------------------------------------------------------- |
|
|
|
|
|
var _shouldAdvancePc = true; |
|
|
|
|
|
var CPU = { |
|
|
execute: function(program) { |
|
|
_pc = _labels['main:']; // jump to the entry point of the program |
|
|
_running = true; |
|
|
|
|
|
while (_running) { |
|
|
var instr = program[_pc]; // "fetch!" |
|
|
_shouldAdvancePc = true; |
|
|
|
|
|
// ... |
|
|
// here should be decode step, but we skip it |
|
|
// for brevity since work directly with assembler |
|
|
// ... |
|
|
ops[instr[0]].apply(ops, instr.slice(1)); // "eval!" |
|
|
|
|
|
// If it's not unconditional jump (which modifies the pc itself) |
|
|
// just go to the next instruction. |
|
|
if (_shouldAdvancePc) { |
|
|
_pc++; |
|
|
} |
|
|
} |
|
|
} |
|
|
}; |
|
|
|
|
|
// --------------------------------------------------------------- |
|
|
// 4. Test program |
|
|
// --------------------------------------------------------------- |
|
|
|
|
|
var program = [ |
|
|
// The `sum` function (label). |
|
|
'sum:', |
|
|
['mov', '$a', '_stack[$fp]'], |
|
|
['mov', '$b', '_stack[$fp - 1]'], |
|
|
['add', '$a', '$b'], |
|
|
['ret', 2], |
|
|
|
|
|
// Main entry point. |
|
|
'main:', |
|
|
|
|
|
// Call the `sum` function. |
|
|
// Params are passed (pushed onto the stack) |
|
|
['push', 10], |
|
|
['push', 20], |
|
|
['call', 'sum'], |
|
|
|
|
|
// Exit. |
|
|
['halt'] |
|
|
]; |
|
|
|
|
|
// Print the example program. |
|
|
console.log('Execute the program:'); |
|
|
program.forEach(function(instr) { |
|
|
if (Array.isArray(instr)) { |
|
|
console.log(' ', instr[0], instr.slice(1).join(', ')); |
|
|
} else { |
|
|
console.log('\n', instr); // lable |
|
|
} |
|
|
}); |
|
|
|
|
|
// Run the program. |
|
|
CPU.execute(assemble(program)); |
|
|
|
|
|
// Check the result in the accumulator. |
|
|
console.log('\nAccumulator result ($a):', _regs.$a, '\n'); |
|
|
|
|
|
// Execute the program: |
|
|
// |
|
|
// sum: |
|
|
// mov $a, _stack[$fp] |
|
|
// mov $b, _stack[$fp - 1] |
|
|
// add $a, $b |
|
|
// ret 2 |
|
|
// |
|
|
// main: |
|
|
// push 10 |
|
|
// push 20 |
|
|
// call sum |
|
|
// halt |
|
|
// |
|
|
// Accumulator result ($a): 30 |
DmitrySoshnikov revised this gist