Assembler failed with Program Too Large

[bupjae]

As "post-project", I'm implementing HACK computer on FPGA evaluation board.
Currently, I successfully run Pong.hack on the board, and I'm trying to run various JACK programs too.

With blank JACK file (only contains Main class, which has only main() function, which has only one return; statement) and supplied OS codes,
I used supplied JackCompiler and my own VMTranslator. (I couldn't find VMTranslator on supplied tools)

The resulting ASM file contains 35241 lines of code, exluding comment and labels.

Supplied Assembler failed to translate to binary code, with error message "Program Too Large".


1) Is there VMTranslator in the supplied tools?
2) Could you suggest optimize points for VMTranslator?

[WBahn]

Before I begin, let me say that I would love to hear more about your hardware implementation. In particular, what FPGA board are you using and how are you handling keyboard input? I would also be interested in how you chose to do your screen mapped I/O, but that's pretty straightforward.

What kind of display are you using?

Okay, now to your questions. I do not believe that there is a supplied VMTranslator because their compiler generates VM code and you can run it in the VM emulator. The reasoning is probably to prevent students from just using the supplied tools to create the files that they turn in instead of using the VM translator that you wrote.

There are numerous optimizations that you could apply, but it's impossible to even start talking about them until we have some idea of what you are currently doing. One thing you might consider is to turn your longer VM commands into subroutine calls that call a common ASM instruction list and then return to the point where called. This adds about four clock cycles per call, but for commands that are called a lot, the space savings can add up quickly.

Then, of course, there's always just go through your VM translation templates and squeeze every instruction out of them that you can. Since these are called over and over, a single removed instruction can have a significant impact.

Some other options, particularly since you are probably moving beyond the Hack as defined already (or probably soon will):

You are not bound to their memory map. If I had been doing this I would have used the entire 32K addresses available via the A-instruction and parked the SCREEN memory right at the top of it and put the KBD just below it, making another 8K - 1 address available for the heap (i.e., increasing the total memory by just non-mapped memory by about 50%).

I don't know their rationale for the way they did it. It could have been to put a chunk of writable memory between the heap and the keyboard interface. But who knows.

Another thing you can do is utilize the undocumented instructions. With the exception of XOR and XNOR, the ALU supports all 16 binary Boolean functions directly. What I did was add the instuction Xhh where hh is a two digit hexadecimal value that directly translates to the 7 control signals ('a' plus the six ALU control lines). So it's a simply extension of the assembler.

[ivant]

In addition to this, I'd like to link to this post by Mark about his VM to HACK compiler. It discusses various optimization techniques and what effect they have on his test program.

[bupjae]

I'll upload full "report" once I'm finished implementation.

Here is summary what I've used:

* FPGA board - Terasic DE10-Lite
  # https://www.terasic.com.tw/cgi-bin/page/archive.pl?Language=English&No=1021
  # Intel MAX 10 series: 10M50DAF484C7G
  # VGA connector
  # Arduino Shield connector
* Addon board - Arduino USB Host Shield
  # https://store.arduino.cc/usa/arduino-usb-host-shield
  # USB Controler: MAX3421E
  # One USB-A female connector
* Keyboard - Happy Hacking Keyboard Lite 2 USB (Black)
  # https://www.amazon.com/Happy-Hacking-Keyboard-Lite2-Black/dp/B0000U1DJ2
  # Contains 2-port USB hub
* Monitor - Samsung Samtron 73S
  # https://www.amazon.co.uk/SAMTRON-73V-display-0-264-ivory/dp/B0006B177S
  # Above link is not exact match, but the most similar product I could found.
* Development tool - Intel Quartus Prime Lite v18.1
  # https://www.intel.com/content/www/us/en/software/programmable/quartus-prime/overview.html
  # Supports Verilog and VHDL; using both in one project is also possible.
  # I used VHDL for keyboard controller, and Verilog for other parts.


Regarding keyboard controller, I know that USB keyboard is *harder* to establish connection than PS/2. Unfortunely, I don't have any PS/2 Keyboard. For now, I implemented minimum USB protocol that would works only on one particular cofiguration - HHKL2 is connected directly (without any additional hubs) on Shield.


Regarding screen controller, the board provides simple connection between FPGA and VGA connector; hsync and vsync is connected directly, and RGB signals is connected via 4-bit resistor array DAC. As FPGA provides true 2-port RAM blocks, implementation was rather simple - read/write from HACK cpu to screen buffer uses port A, and from screen buffer to physical monitor uses port B.



Now optimization.

The most big concern is that the whole program should fit in 32K-word ROM. Therefore, let's assume that optimization means "code size reduction" on here.

I'm currently working on VMTranslator for more compact code generation template. After some works, I could reduce size of "blank project" from 35241 words to 30384 words. Still, I need more works. For example, current size of KeyboardTest is 48028 words.

Here is current score board:

push constant: 6
push local / argument / this / that: 9
push pointer / temp / static: 6

pop local / argument / this / that 0: 6 (was 12)
pop local / argument / this / that 1: 7 (was 12)
pop local / argument / this / that n: 12
pop pointer / temp / static: 5

add, sub, and, or: 5 (was 7)
neg, not: 3
eq, gt, lt: 11

goto: 2
if-goto: 5

call: 35 (current candidate of extracting)
function [name] 0: 0
function [name] n: 4 + 2*n
return: 2 (extracted as "subroutine", was 39)

bootstrap + subroutine: 53

[WBahn]

Ignoring the question of optimizations from Jack to VM (for now), I would recommend analyzing your VM code and counting how many times each of the commands is called. That way you can tell which commands will result in the biggest space savings if they can be reduced.

[Erik Umble]

One idea as to why they chose the Screen and Keyboard memory map as they did was so that it would be convenient binary number addresses which made the Memory.hdl easier to write. In their memory map, screen is from 0100000000000000 to 0111111111111111, and keyboard is 1000000000000000. So, it is quite wasteful, but it made it very nice for connecting wires to know where the screen and keyboard are.