AST -> Bytecode determine conditional jumps

  1. What do you want to achieve?
    I’m currently trying to make my own custom language using a Register style VM. It’s almost completly identical to lua’s except with a few minor additions.

  2. What is the issue?
    The current issue is that I don’t know how to calculate and determine conditional jumps. For example:

>local m, n; return m >= n
; function [0] definition (level 1)
; 0 upvalues, 0 params, 3 stacks
.function  0 0 2 3
.local  "m"  ; 0
.local  "n"  ; 1
[1] le         1   1   0    ; to [3] if false    (n <= m)
[2] jmp        1            ; to [4]
[3] loadbool   2   0   1    ; false, to [5]      (false path)
[4] loadbool   2   1   0    ; true               (true path)
[5] return     2   2      [6] return     0   1     

I understand how it should work, but I don’t know how to put it into practice since there can be lot’s of different variables at play. This is an example of how it can get crazy:

>if 8 > 9 then return 8 elseif 5 >= 4 then return 5 else return 9 end
; function [0] definition (level 1)
; 0 upvalues, 0 params, 2 stacks.function  0 0 2 2
.const  8  ; 0
.const  9  ; 1
.const  5  ; 2
.const  4  ; 3
[01] lt         0   257 256  ; 9 8, to [3] if true    (9 < 8)
[02] jmp        3            ; to [6]
[03] loadk      0   0        ; 8                      (1st true block)
[04] return     0   2      
[05] jmp        7            ; to [13]
[06] le         0   259 258  ; 4 5, to [8] if true    (4 <= 5)
[07] jmp        3            ; to [11]
[08] loadk      0   2        ; 5                      (2nd true block)
[09] return     0   2      
[10] jmp        2            ; to [13]
[11] loadk      0   1        ; 9                      (2nd false block)
[12] return     0   2     
[13] return     0   1      ; end of function

Any advice would definitely be appreciated!

This is taken from http://luaforge.net/docman/83/98/ANoFrillsIntroToLua51VMInstructions.pdf

You need some sort of labeling system. The Lua parser sucks at being idiomatic in how it does it, but you need some sort of way to track jump targets.

For forward jumps, the easiest way is to keep an array with addresses to your jump instructions. When you exit or enter a scope, iterate that array for any jumps you have pending and set their offset to point to the current program counter.

For backwards jumps, you should keep the program counter of where each control structure begins (ex. where the loop condition starts) and calculate the offset as soon as you generate the jump.

1 Like