jeudi 21 février 2019

How to compile an if-statement with variable-length instructions

I'm writing a little language VM with arbitrary integer (encoding, not literally) parameters, and I'm about to implement if-statements. The tried-and-true formula for if statements is to compile

if (EXPRESSION) {
    BODY
}

into

EXPRESSION
JUMP-IF-FALSE body-length
BODY

However, I'm struggling to see how a single-pass compiler can determine the body length while it's generating the JUMP-IF-FALSE command.

With constant-sized instructions, you can just add two extra bytes or something and go back and patch it, but with variable-sized ones that would require either insertion or concatenation, two O(N) processes.

So, my only option appears to be to switch to constant-sized jump instructions and every MAXJUMP-1 bytes insert a command to jump over the next instruction, and then another JUMP instruction.

Even if this situation (65k+ flat bytes with 2-byte jump) is really unlikely I would really, really like to not have do this.

Aucun commentaire:

Enregistrer un commentaire