Flow Control Instructions in a virtual machine

Question

I've been implementing my own scripting language + virtual machine from scratch for a small experiment. A script reader parses the script and translates it to a stream of instructions that a runtime engine will execute.

At the beginning I didn't think about it but now I'd like to include flow control (loops, branching etc). I'm not well versed with language theory and just looked at some examples for inspiration.

But both the x86 and the java virtual machine have a plethora of instructions used for flow control. In x86 there are plenty instructions that jump based on the state of flags and other instructions that manipulate the relevant flags one way or another. In Java there seem to be 16 instructions that make some sort of comparison and a conditional jump.

This might be efficient or motivated by hardware specific reasons but it's not what I'm looking for.

I look for a lean, elegant solution to flow control that only requires a few dedicated instructions and isn't too complicated to implement and maintain.

I'm pretty confident I could come up with something that works but I'd rather improve my knowledge instead of reinventing the wheel. Any explanations or links to relevant material are very welcome!

Answer 1

Generally the minimum primitives required for flow control are

• unconditional jump

• conditional jump

Of these, the conditional jump is the complex one, and at a minimum it needs to support the following atomically:

• test a binary variable/flag

• if the flag is set, cause instruction execution to jump to some specified location

• if the flag is unset, allow instruction execution to continue uninterrupted

However with such a primitive conditional jump, you would need ways to set that binary variable/flag to the appropriate value for every type of boolean expression that could be used in the flow control structures of your language.

This would therefore either lead to the need for various primitives of varying complexity for setting the binary variable/flag, or the need to emit complex sequences of instructions to get the desired effect.

The other alternative is to introduce more complex conditional jump primitives.

Generally there will be a trade-off between the number and complexity of each of: conditional jump primitives; condition (variable/flag) setting primitives; emitted instructions.