Hack on FPGA - optimized VM Translator needed

[Steku]

I managed to implement Hack Computer on Digilent Basys 3 FPGA Board in Verilog.



The asm version of Pong supplied with the course works fine on it as well as some basic assembler programs I managed to write. However programming in assembler is very time consuming and I would like to test my machine further using some Jack programs and Hack OS.

The missing piece is the VM translator. I started to write it, however I quickly realized that the generated code will be far from optimal (I'm much better at the H/W part than S/W optimizing) and I will probably not manage to fit the entire OS in the available ROM. I managed to find some VM translators on GitHub, they all generate code too big to fit in ROM even for such simple tests like "OutputTest" from project 12.

Is there a way to obtain mature version of VM translator, generating assembly code optimized enough to fit in in the available ROM with the necessary OS? Anybody could be kind enough to share your translators with me?

The VM file consuming most of the ROM is Output.vm containig all the character definitions. In my FPGA implementation I have the ability to inject the character definitions directly into RAM when initiating it on the FPGA. So I already managed to preload the character bitmaps to RAM and then to make Output.initMap much shorter by creating a loops reading preloaded bitmaps from RAM with Memory.peek instead of specifying all the bitmaps implicitly in the Output.initMap. It resulted in the asm code ca. 2K smaller, but this is still not enough to handle any substantial program written in Jack.

However the effective VM translator, able to generate optimized asm code, would save me the need for all this trickery.



I discovered that in the VM translator I'm using (from GitHub) the most of assembly code is repeated over and over again, to handle the return from the function, for example, this piece of code:

D=A
@SP
A=M
M=D
@SP
M=M+1
@LCL
D=M
@SP
A=M
M=D
@SP
M=M+1
@ARG
D=M
@SP
A=M
M=D
@SP
M=M+1
@THIS
D=M
@SP
A=M
M=D
@SP
M=M+1
@THAT
D=M
@SP
A=M
M=D
@SP
M=M+1

is repeated 225 times in the asm program which is 33000 lines long, so it contributes to ca. 25% of the entire asm code. Would be great to find a way to optimise this.

IvanT was kind enough to share with me his VM Translator - here is the result:
Crude FPGA Hack movie on YouTube

[Lozminda]

Hi

I read, i think on this forum, a post that some one had written in the more "fun to go" section about VM translation optimisation.

That person maybe a good person to speak to, but can I find the link !?! I'll probe further...

Ps your machine looks great !

PPs http://nand2tetris-questions-and-answers-forum.32033.n3.nabble.com/Generated-code-size-tt1201814.html#a4026264

This isn't the link I'm looking for, any help though ?

[ivant]

Here are 3 related posts by cadet1620:

Links to posts discussing generated Assembly Language size

My optimizing VM translator

[Lozminda]

Thanks @ivant, I was thinking @cadet1620 might be the person to speak to, if they're still about (only coz I read their article, I'm sure there are others who can help, just not me !)

Lozminda

[Steku]

IvanT shared with me his very effective VM Translator - I added link to the resulting movie at the end of the original post. Enjoy the flashing LEDs! You can even try to read the code being executed!

[Gerrit0]

This is awesome! I have exactly opposite of your skills, the software was fun to build, but something I'd done before, while I've done almost nothing in the H/W realm. I'd like to do something similar to what you've done.

I'd offer to share my VM translator, but looks like IvanT beat me to it.

[Lozminda]

Glad it worked out !!