Hack ROM is too long!

[FinnW]

My Hack (Symbolic) file is now so long after all these OS scripts that it can not fit the label addresses on an A instruction

For example my lowest label is (Sys.error$ret.85) at line 53482
But "@Sys.error$ret.85" has to become an A instruction of only 16-bits and of course 16-bits only goes to 32,767

I honestly have no idea how to fix this, and right at the end of the course too

Hope someone can help me, thanks

[WBahn]

It can be very challenging to get everything to fit in the ROM. It CAN be done, but it actually isn't a requirement that you do it. It is sufficient that your code runs properly in the VM Emulator.

[dolomiti7]

Can you describe in more detail what you are trying to achieve?
I presume that you want to translate Pong with your own toolchain including your own OS?

Also could you clarify what you mean by your "lowest" label? If all of the labels in your program are resulting in addresses >32k, there is likely something substantially wrong in your translation.

In general remaining below the 32k limit can be challenging. As a first step it would be helpful to find out which part of the toolchain is contributing the most to the large size of the program. In most cases the efficiency of the VM translator is not sufficient.

This is how I would check the quality of my toolchain:
1. OS
-> Compile your own OS with the official JackCompiler
-> Compare the number of lines (or more precisely the number of VM instructions excluding labels) with the number of lines in the VM files of the official OS (from the tools/OS folder)
-> If your OS results in significantly more VM code, your jack code in project 12 can be improved

2. Compiler
-> Compile the 4 Pong *.jack files from project 11 with your own compiler
-> Compiler the 4 Pong *.jack files with the official compiler
-> Compare the number of lines in the resulting VM files
-> If your compiler generates more VM code, your compiler code generation from project 10/11 can be improved

3. VM Translator (most likely root cause)
-> As a KPI to measure the quality of the generated ASM code, you can calculate the number of lines in the generated ASM file divided by the number of lines of code in the VM files.
-> (exclude labels in both VM and ASM files in the KPI calculation, since labels are just used for addressing and don't generate any hack code)
-> A good translator should be around max 5-6 ASM lines per VM
-> There are plenty of posts regarding the reduction of generated code in this forum under "project 8"
-> Low hanging fruits are:
-->Dead code elimination (removal of code that is not in use, i.e. Math.sqrt is like many other OS routines not used by Pong, so the translator can detect that and safely remove all respective functions)
-->Global functions for certain VM commands (the easiest one probably being RETURN; instead of generating the code for return for every occurrence, you can just generate a generic return handler and jump to the routine for every subsequent occurrence of RETURN)

4. More complex programs than Pong
If the above measures are not sufficient because the program that you want to translate is too long/complex, you may want to look into a code generation technique that I briefly explained here

[FinnW]

I actually managed to get it myself by going through each translation and removing unneeded assembly such as:
@0
D=A
becomes
D=0
And other stuff like that

But most of my optimization came from creating special edge cases in the translator for certain sequences of commands such as:
push x
pop y
I made it so if this happens it doesn't involve the stack pointer at all and just directly copies the value across
I also optimized:
push memSeg x
push constant y
add
pop memSeg z
And
push memSeg x
push constant y
add
pop memSeg x

Overall I was able to reduce the instructions length by about 15% getting me under the 32k limit
Thanks for the reply though

[WBahn]

Good job.

You are dipping your toes into the world of optimizing compilers.

A few years ago I challenged my students to get the OS libraries down as small as they could. Most made very modest improvements, but one of them really got it down. I don't remember how small he got it, but I was very amazed and impressed.

[dolomiti7]

How did you measure the improvements? Based on the number of VM lines?

For my own OS I tried to find a good balance between size, speed and RAM footprint. I ended up with improvements in all three areas. As I've mentioned in project 8, especially the output class can be reduced significantly in size by using a compressed charset (757 VM lines versus 1852). The Heap RAM usage is only 50% (about 1k, mostly for the unpacked charset) and at the same time printChar is about 60% faster. Multiply and divide are 70% faster.  Extreme speed improvements are possible with horizontal lines (400x) and drawCircle (8.8x). Happy to share my compiled VM files if that is in line with the nand2tetris rules. Needless to say, if you'll ever challenge your students on the OS again, I'll throw in my OS as benchmark ;-)

[WBahn]

There are certainly different metrics and which ones count the most depend on context. Of course, the most important one is that the end program has to fit within the ROM. Since the course I'm talking about was a Compiler course, I walked them through a very direct implementation of the VM Translator that was intentionally not optimized in any way. They had the option of spinning their own, or starting with that one. The compiler, of course, was all theirs. They could also use the authors' OS libraries or roll their own.

Then I gave them a Jack program that, using my VM Translator and the provided OS libraries, was noticeably too big to fit in ROM, so they had to do some analysis to decide where to put in the effort.

But the primary metric was speed. I wrote a simulator (no screen output or keyboard input) that measured the number of clock cycles to run their program. At the end of the simulation, it captured the SCREEN memory block and produced a BMP file of the image, which used all of the graphics library routines.

They then had to write a report and give a presentation on how they went about optimizing their tools, focusing not so much on what they did, but the thought process that they followed and how they decided what to focus on and how they measured the impact. Overall, I was pretty pleased with the results.

[pm100]

I can now fit in a huge (in hack terms, 800 lines of jack) space invaders game.

I did similar optimizations plus-

- factor out the code for call and return, its huge, into a couple of assembler subroutines
- create a linker that only includes the needed pieces of the OS code, eg if you dont call Screen.drawCircle the code isnt there

[dolomiti7]

I presume you are referring to this space invaders implementation:
http://nand2tetris-questions-and-answers-forum.52.s1.nabble.com/Space-Invaders-tp4032384.html

https://github.com/jcon/SpaceInvaders

You can do much more to reduce code size (10,910 instructions):
Space_Invaders.hack

Translated with threaded code and some asm libs for Memory and Math.

Edit: just saw your post in project 9, and that your translation was related to that WIP implementation... anyway, you might want to test your toolchain with the above program which is working

[pm100]

Yes, the supplied OS .vm files are a great opportunity for optimization (strings! - the horror). But I decided to leave as was, I just needed some non trivial apps for my main project.

Main project is getting mini-unix (a real mode unix v6 version that ran on original pdp11) running on my fpga implementation of hack system. For that I need
- an FPGA implementation - done , no screen yet tho
- a c compiler, working on tinycc to add hack backend
- a proper debugger, I now have my own implementation of cpu emulator with debugger. Now adding debug data generation (line numbers, variables locations...) to my toolchain. Will need to be adapted for the c compiler.

original pdp11 is about the same power as hack.
Need to add more memory mapped io
- disk read / write
- ram read / write - treat RAM as addressable peripheral.

My aim is not to change the hack architecture, the lack of shift / rotate, interupts, byte addressing are all challenges.

[pm100]

actually no, i was referring to this one https://github.com/blacknand/nand2tetris/tree/main/9/SpaceInvaders