Compiling If Statements - Conversion to Binary

[blossoms75]

I am working on the Conversion to Binary Main.jack to Main.vm test. The trouble I am having is with compiling if statements.

The first problem is with these two lines:
if (~(position > 16)) {
   if (~((value & mask) = 0)) {

According to Chapter 11, an "if statement" should be compiled like this:

compiled (expression)
not
if-goto L1
compiled (statements1)
goto L2
Label L1
compiled (statements2)
Label L2

So for the above lines, my compiler returns:
not
not
if-goto IF_TRUE1
...

That makes sense to me because you need one "not" for the ~(position > 16) and another one as part of the if-statement algorithm. The code generated from the supplied compiler only has one. Why is that?

The other problem I am having is with the order of if and goto statements. The vm code you get with the Jack Compiler looks something like this:

not
if-goto IF_TRUE1
goto IF_FALSE1
label IF_TRUE1
(Code from compiled statement)

But according to the given algorithm, shouldn't it be something more like:
not
if-goto IF_TRUE1
(code from compiled statements)
goto IF_FALSE1

Based on how I think the stack works and previous assignments, the code that the Jack compiler puts out makes sense. However, it doesn't look like it's following the algorithm. Can someone offer some help on where I'm getting the logic wrong?

Thanks for any help.

[ivant]

It makes sense to answer your two questions in reverse order.

Le'ts look at how we can compile the Jack expression

    if (EXPR_COND) {
        EXPR_THEN
    } else {
        EXPR_ELSE
    }

We need to generate code for EXPR_COND, EXPR_THEN and EXPR_ELSE, and we need to put some control logic around it, so that the last two are executed only in the correct case:

    EXPR_COND_COMPILED
    some_code_1
    EXPR_THEN_COMPILED
    some_code_2
    EXPR_ELSE_COMPILED
    some_code_3

In some_code_1, we need to make sure that the THEN part only will be executed if the COND is evaluated to true. So if COND is true, we can just continue. If it's false we should jump to the ELSE part. The VM only has if-goto, which jumps if the top of the stack is true. That's why we need to NOT it first. The code now looks like this:

    EPXR_COND_COMPILED
    not
    if-goto LABEL_ELSE
    EXPR_THEN_COMPILED
    some_code_2
label LABEL_ELSE
    EXPR_ELSE_COMPILED
    some_code_3

The some_code_2 part is reached only after the THEN expression is executed. It needs to make sure that ELSE isn't executed in this case. It's as easy as a unconditional jump:

    EPXR_COND_COMPILED
    not
    if-goto LABEL_ELSE
    EXPR_THEN_COMPILED
    goto LABEL_END_IF
label LABEL_ELSE
    EXPR_ELSE_COMPILED
    some_code_3
label LABEL_END_IF

We can see that some_code_3 doesn't have to do anything, so we can just remove it:

    EPXR_COND_COMPILED
    not
    if-goto LABEL_ELSE
    EXPR_THEN_COMPILED
    goto LABEL_END_IF
label LABEL_ELSE
    EXPR_ELSE_COMPILED
label LABEL_END_IF

Note that we can instead decide to compile the code as follows:

    EXPR_COND_COMPILED
    some_code_1
    EXPR_ELSE_COMPILED
    some_code_2
    EXPR_THEN_COMPILED
    some_code_3

That is, we switch the places of THEN and ELSE expressions. Why? Well, we can skip one NOT instruction in this case, because we don't need to invert the COND result. I'll leave it to you to finish this, if you want to.

In general, compilation can involve several passes, including various analysis and optimization ones. One easy and common optimization technique is called peep-hole optimization. In it, the compiler identifies sequences of instructions, which can be replaced by other, more effective sequences. For example the sequence:

    NOT
    NOT

can be eliminated altogether (or replaced with an empty sequence), because the effect is exactly the same. My guess is, that the official compiler produced 3 NOTs and then removed two of them and so you see just one.

You don't need to do any optimizations in the compiler to finish the course. After that you can dive in this very interesting problem. There are some very interesting results and resources in this forum.