FizzBuzz in ToyVM

Question

Since I have my own virtual machine and an assembler for it, I decided to test it with a FizzBuzz implementation. I have this:

fizzbuzz.toy

    const reg4 100
    const reg2 1

loop_begin: // The main loop counting from 1 to 100

    add reg2 reg1
    cmp reg1 reg4
    ja end
    pusha
    push reg1
    call print_function
    pop reg1
    popa
    jmp loop_begin

print_function: // The function responsible
                // for printing the relevant token

    lsp reg1
    const reg2 4
    add reg2 reg1
    rload reg1 reg1
    const reg2 15
    mod reg1 reg2
    const reg3 0
    cmp reg2 reg3
    ja try_5
    jb try_5
    const reg3 str_fb
    push reg3
    int 2
    jmp end_of_print_function

try_5:

    const reg2 5
    mod reg1 reg2
    const reg3 0
    cmp reg2 reg3
    ja try_3
    jb try_3
    const reg3 str_b
    push reg3
    int 2
    jmp end_of_print_function

try_3:

    const reg2 3
    mod reg1 reg2
    const reg3 0
    cmp reg2 reg3
    ja no_match
    jb no_match
    const reg3 str_f
    push reg3
    int 2
    jmp end_of_print_function

no_match: // Just print the line number.

    push reg1
    int 1
    const reg4 str_nl
    push reg4
    int 2

end_of_print_function:
    ret

end:
    halt

    str str_fb "FizzBuzz\n"
    str str_f  "Fizz\n"
    str str_b  "Buzz\n"
    str str_nl "\n"

(The virtual machine is here.) (The assembler is here.)

Assembling: java -jar jToyAssembler-1.6.jar fizzbuzz.toy

Running: toy fizzbuzz.brick

Please, tell me anything that comes to mind.

Answer 1

The control flow would be a bit more natural with a REPEAT loop (tail-tested) instead of WHILE (front-tested), and associating the constant 1 with 'reg1' instead of 'reg2' makes the code a wee bit smoother to read. The loop counter register (reg1 in the original code) is not assigned an explicit value, so it is presumably 0?

It is worth it to keep the separation between main loop and the processing code, instead of inlining the processing. Since the interpreter forces one to jump through major hoops for accessing parameters on the stack, one might as well pass the lone parameter in a register. 'mov reg4 reg1' is still less overhead than the rigmarole for extracting the value from the stack.

    const reg1 1    // loop increment
    const reg2 101  // upper bound + 1
    const reg4 1    // loop variable

loop:
    pusha
    call process_number_in_reg4
    popa
    add reg1 reg4
    cmp reg2 reg4
    ja loop

    halt

process_number_in_reg4:
    mov reg4 reg1
    ...

If you want then you can still pull the parameter from the stack exactly as before, since I deviously assigned loop variable duty to reg4.

Similar considerations apply to the rest of the code, which can be tightened considerably. However, Edward has already done a superb job on that, and so it's time to address the more interesting - if implicit - part of the question, which is ToyVM itself.

Overall I must say that both your byte code and your interpreter need seriously serious reworking, starting with the design. The byte code language is lacking many basic features (starting with a simple jae or jnb and so on). In some cases this can be worked around without additional instructions by expedients like changing loop boundaries (as with the 101 instead of 100 in the fragment above), but overall the effect is an unnecessary reduction in effectiveness and unnecessary complications for code generators (including human programmers). Assembly programmers and code generator programmers don't mind hoops much if they get something in return, like blistering performance. Conversely, arbitrary limitations without payback are greeted with a decided lack of enthusiasm.

Also, your flags need reworking - take some inspiration from the guys who've been doing this for several decades (Intel, Motorola, Zilog, ...). It just doesn't make sense to have independent 'above' and 'below' flags. If you don't want to do the research for developing a decent flag design, why not simply take the basic x86 scheme (i.e. the arithmetic flags like CF and ZF)?

Also, it would make sense to adopt a simple and strong rule for what is source and destination, e.g. the direction of moves and so on. Use strict Intel rules (first operand is destination) or the AT&T rules, but get rid of the arbitrariness you have now. I found it impossible to work out the meaning of the flags based on operand order and the usual rule that cmp equates to sub without assignment of the result... Studying the .c files didn't help either.

The interpreter is several orders of magnitude too slow for the hoops it makes programmers jump through. I've experimented with a simple three-address machine as byte code interpreter for a simple C-like language (with inspiration from FoxPro and C#), and basic processing rate was about 500 million instructions per second. I can only recommend using a three-address code as well because it strikes the best balance between complexity and power on all levels but you should first get some experience working with 0, 1, and 2 address machines (i.e. implementing real algorithms/functions, like the tasks on code challenge sites).

Overall it is a very interesting project, but I would recommend studying existing interpreters and VMs before tackling v2... Byte code systems like FoxPro, Java and/or the Neverwinter Nights script engine can give a lot of inspiration. You can target Java and .NET IL for some hands-on experience with compiling to bytecode/IL, unless you want to stay strictly on the assembly level. Also recommended is doing a stint of assembly programming across many different processor architectures (some code challenge sites allow at least x86 assembly), including some excursions into Brainf*ck and INTERCAL. This will definitely broaden your outlook and you will gather not only lots of ideas but also lots of frustrations about things that are bad in these existing systems and that you would wish to be different in your ideal language (and its next provisional rendering, i.e. ToyVM v2).

Answer 2

Here are some things that may help you improve your code. Since this toy machine does not have timing information associated with instructions, optimization of the assembly language code can't be done based on the timing costs of instructions. Still, there are some things that can be done.

Eliminate redundant jumps

In several places, we have the following sequence:

mod reg1 reg2
const reg3 0
cmp reg2 reg3
ja try_5
jb try_5

However, both registers reg1 and reg2 are positive integers, so the result in reg2 will never be a negative number. For that reason, only the ja instruction is needed.

Explicitly initialize register before use

The reg1 register is used before it's initialized. It is not good practice to rely on reset values. If you absolutely must, at least it should have a comment.

Document register use

In assembly languages in general, and particularly with a machine with very few registers, it is useful to document which registers are inputs, which are outputs and which are trashed by each routine.

Pass by register where possible

The loop calls print_function after pushing all of the registers and then redundantly pushing reg1. Better would be to restructure the code so that the needed value(s) are passed by register.

Reuse as much as possible

By careful restructuring of the code, you could have the int 2 called only once.

Putting it all together

Here is a rewritten version using all of these suggestions. I find it easier to read and it's certainly shorter.

// fizzbuzz 
// reg1 = counter
// reg2 = working v'ble
// reg3 = 0  
// reg4 = string to print

    const reg1 1
    const reg3 0

loop_begin: // The main loop counting from 1 to 100

    const reg2 15
    mod reg1 reg2
    cmp reg2 reg3
    const reg4 str_fb
    je printString

    const reg2 3
    mod reg1 reg2
    cmp reg2 reg3
    const reg4 str_f
    je printString

    const reg2 5
    mod reg1 reg2
    cmp reg2 reg3
    const reg4 str_b
    je printString

    // just print the number
    push reg1
    int 1
    const reg4 str_nl

printString:
    push reg4
    int 2

    // increment counter 
    const reg2 1     
    add reg2 reg1
    // loop until done
    const reg2 101
    cmp reg1 reg2
    jb loop_begin
    halt

    str str_fb "FizzBuzz\n"
    str str_f  "Fizz\n"
    str str_b  "Buzz\n"
    str str_nl "\n"