Program too large!

classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

Program too large!

ElliottS

Hey everyone! I have written a simple calculator program in Jack just to get my hands dirty. I was testing it on the VM emulator and was curious if I could get it to run on the CPU emulator.

I took the Main.vm that was the result of running my jack file through the supplied compiler and put it into a folder with all the .vm files that represent the OS. I then ran that folder through my VM translator that I built in the previous chapter. When I try to load the result into a CPU emulator however I get an error telling me that the program is too large!

Is it possible that that the VM translator I built is not working properly, even though it passed all the tests from the previous chapter? Or is there something else that I am missing?

side note: It is painfully slow to test a program on the VM emulator. Don't get me wrong it is very cool to see how it all works. Sometimes however I want it to just run the jack code as fast as possible so that I may test my code!

calc.asm

I have uploaded the resulting .asm file. the code for my basic calculator is as follows:

class Main{
        function void main(){
                var int selection;
                while (true){
                        let selection = Main.mainMenu();
                        if (selection = 1){
                                do Main.addition();
                        }
                       
                        if (selection = 2){
                                do Main.subtraction();
                        }
                       
                        if (selection = 3){
                                do Main.multiplication();
                        }
                       
                        if(selection = 4){
                                do Main.division();
                        }
                       
                        if (selection = 5){
                                return;
                        }
                }
                return;
        }
       
        function int mainMenu(){
                do Output.println();
                do Output.printString("-----Main menu-----");
                do Output.println();
                do Output.printString("1. Addition");
                do Output.println();
                do Output.printString("2. Subtraction");
                do Output.println();
                do Output.printString("3. Multiplication");
                do Output.println();
                do Output.printString("4. Division");
                do Output.println();
                do Output.printString("5. Quit");
                do Output.println();
                return Keyboard.readInt("Enter selection: ");
        }
       
        function void addition(){
                var int firstNum, secondNum, answer;
                do Output.println();
                let firstNum = Keyboard.readInt("Please enter the first number: ");
                do Output.println();
                let secondNum = Keyboard.readInt("Please enter a number to add to the first: ");
                do Output.println();
                let answer = firstNum + secondNum;
                do Output.printInt(answer);
                do Output.println();
                return;
        }
       
        function void subtraction(){
                var int firstNum, secondNum, answer;
                do Output.println();
                let firstNum = Keyboard.readInt("Please enter the first number: ");
                do Output.println();
                let secondNum = Keyboard.readInt("Please enter a number to subtract from the first: ");
                do Output.println();
                let answer = firstNum - secondNum;
                do Output.printInt(answer);
                do Output.println();
                return;
        }
       
        function void multiplication(){
                var int firstNum, secondNum, answer;
                do Output.println();
                let firstNum = Keyboard.readInt("Please enter the first number: ");
                do Output.println();
                let secondNum = Keyboard.readInt("Please enter a number to multiply the first by: ");
                do Output.println();
                let answer = firstNum * secondNum;
                do Output.printInt(answer);
                do Output.println();
                return;
        }
       
        function void division(){
                var int firstNum, secondNum, answer;
                do Output.println();
                let firstNum = Keyboard.readInt("Please enter the first number: ");
                do Output.println();
                let secondNum = Keyboard.readInt("Please enter a number to divide the first by: ");
                do Output.println();
                let answer = firstNum / secondNum;
                do Output.printInt(answer);
                do Output.println();
                return;
        }
}
Reply | Threaded
Open this post in threaded view
|

Re: Program too large!

cadet1620
Administrator
ElliottS wrote
side note: It is painfully slow to test a program on the VM emulator. Don't get me wrong it is very cool to see how it all works. Sometimes however I want it to just run the jack code as fast as possible so that I may test my code!
Make sure that you have Animate: set to No Animation and speed set to Fast. Also, the VMEmulator will run faster if you just have your program's VM files in the directory and not the OS VM files. That way it will be using its built-in OS classes.
Hey everyone! I have written a simple calculator program in Jack just to get my hands dirty. I was testing it on the VM emulator and was curious if I could get it to run on the CPU emulator.

I took the Main.vm that was the result of running my jack file through the supplied compiler and put it into a folder with all the .vm files that represent the OS. I then ran that folder through my VM translator that I built in the previous chapter. When I try to load the result into a CPU emulator however I get an error telling me that the program is too large!

Is it possible that that the VM translator I built is not working properly, even though it passed all the tests from the previous chapter? Or is there something else that I am missing?
There is nothing "wrong" with your VM translator.  You are just generating ASM code inefficiently.  The code for call and return VM commands is huge, and there are lots of them in the VM files. gt, lt and eq are fairly big too. In your program, with the OS, here are the counts:
call: 703
return: 66
gt: 47
lt: 79
eq: 30
The first thing to notice is that all return commands generate exactly the same ASM code.  This means that you can write it once with a label and thereafter just jump to the code written for the first return.

First return:
// return
($RETURN$)      // return common code
    @LCL
    D=M
    @R15
    M=D
    @5
    A=D-A
    ...
    @R14
    A=M
    0;JMP
All other returns:
// return
    @$RETURN$
    0;JMP
[Note that '$' is a legal character in ASM symbols that is not legal in Jack labels. By using them in my generated labels, my labels can't conflict with VM label commands.]

The other commands are trickier to deal with because you can't just jump to their code to reuse it.
You need to write Assembly Language Subroutines. The simplest are for the comparisons which do the same computation for each instance of their command. Assembly language subroutines with no parameters only require 4 ASM instructions
// gt
    @$RIP123
    D=A
    @$GT$
    0;JMP
The inline code for gt is about 15 instructions, so this saves quite a bit. The $GT$ subroutine looks like this:
($GT$)      // GT compare common code
    @R13
    M=D
    ...     // inline code for gt VM command
    @R13
    0;JMP
The easiest place to write the $GT$ (and other) subroutine is immediately following the bootstrap code.

Call is a bit trickier because it needs 3 parameters: the function, the argument count, and the return address. The return address can be stored in D as in the $GT$ function. The other parameters need to be stored into 2 of the temporary registers, R13-15, before jumping to $CALL$.
// call Sys.init 0
    @RIP$1
    D=A
    @R13
    M=D
    @Sys.init
    D=A
    @R14
    M=D
    @0
    D=A
    @$CALL$
    0;JMP
(RIP$1)
I'll leave you to figure out how to use the saved arguments in your generated call code. Note that which argument to pass in which of R13-15 and D will depend on your current call code.

As you start working on optimizing you generated code it gets even harder to read.  It's a good idea to write the input VM commands into the ASM as comments:
// not
    @SP
    A=M-1
    M=!M
// if-goto IF_TRUE0
    @SP
    AM=M-1
    D=M
    @Array.new$IF_TRUE0
    D;JNE
// goto IF_FALSE0
    @Array.new$IF_FALSE0
    0;JMP
// label IF_TRUE0
(Array.new$IF_TRUE0)
// push constant 2
    @2
    D=A


--Mark
Reply | Threaded
Open this post in threaded view
|

Re: Program too large!

ivant

Another common optimization stems from the fact, that not all functions/methods are used in each program.

One way to find which are used is this:

  1. Create a new empty set of used functions
  2. Create a list of functions to-process and put "Sys.init" in it.
  3. While to-process isn't empty do:
    1. Remove the first function name from the to-process list
    2. If it's already in the used set, go to 3
    3. Otherwise add it to used
    4. Find all the functions it calls (you'll just need to find all the VM CALL instructions) and add them to the to-process list.
  4. The used set will contain all the functions that are used by this program. You can safely skip the code generation for the others

Reply | Threaded
Open this post in threaded view
|

Re: Program too large!

cadet1620
Administrator
In reply to this post by ElliottS
I also forgot to mention that identical call commands can be even shorter than the 12 instruction assembly language call. For instance, in your program thre are 411 "call String.appendChar 2" commands.

All of these are identical except for the return address. Put a label in the first call and the repeated calls can jump to it after setting the return address.
// call String.appendChar 2
    @RIP$123
    D=A
($CALL$String.appendChar$2$)
    @R13
    M=D
    @String.appendChar
    D=A
    @R14
    M=D
    @2
    D=A
    @$CALL$
    0;JMP
(RIP$123)
A later instances of this same call is just
// call String.appendChar 2
    @RIP$456
    D=A
    @$CALL$String.appendChar$2$
    0;JMP
(RIP$456)

In your program there are 703 total calls and 52 unique calls, so this would save (703-52)*8 = 5208 instructions.

--Mark
Reply | Threaded
Open this post in threaded view
|

Re: Program too large!

ElliottS
In reply to this post by ivant
Very interesting information, thank you. Makes me appreciate all the optimizations that must go into modern compilers / assemblers. I'm not sure if I want to go back and optimize my translator right now, or continue on with the rest of the compiler.. Defiantly do want to fix it eventually, the most satisfying thing about this course is how it connects all the levels from high level language down to the logic circuits. Wouldn't sit right with me if I couldn't write a high level language and then follow all the steps down to the lowest level!

I am surprised that this has not been brought up before. Do most people who do this course not try to compile all the way down? Or are they mostly just better coders than i am? :S
Reply | Threaded
Open this post in threaded view
|

Re: Program too large!

cadet1620
Administrator
Yes, you should move on to the compiler and OS. Don't worry about optimizing your VM translator at this point.

When you write your compiler, write the Jack source lines as comments in the generated VM files. It will make debugging your compiler much easier.


For more on VM translator optimization check these forum posts:
Generated code size
I HAVE DONE IT PEOPLE

--Mark