Making Decisions: Compiling If Statements to P-Code

mgcadmin 24-02-2025

When we last left off, I had covered compiling while statements, which involved branching, conditional branching and labels, as well as the basic technique of backpatching. In todays post we're going to kick our backpatch-fu up a level by using it in combination with conditional branching to implement if/else statements. Unlike in the previous post where we made use of labels to calculate addresses, In todays post we're going to do without the labels.

As we did in the previous article, we'll start from the AST level, and work our way down to the VM level. So without further ado, let's get to it!

If/Else Statements As Abstract Syntax Trees

The ability to choose a path of execution based on the condition of a variable is without doubt fundamental to computing as a whole. At their most basic, If statements allow us to choose whether a statement should be executed or not based on the result of a boolen expression. 

if (m < p) { 
    println "aiite"; 
}

This type of if statement, as seen below, can easily be implement with a simple binary tree node.

[IF_STMT] [TK_IF, if]
  [RELOP_EXPR] [TK_LT, <]
    [ID_EXPR] [TK_ID, m]
    [ID_EXPR] [TK_ID, p]
  [PRINT_STMT] [TK_PRINT, println]
    [STR_EXPR] [TK_STR, aiite]

If/Else statements take the concept one step further by adding an explicit second path of execution to be executed when the result of the boolean expression is false.

if (x < y) { 
     println "x is less than y"; 
} else { 
     println "x is not less than y"; 
}

This translates into a ternary node, with the leftmost child being the test expression, with the two other child nodes representing the "true" path of execution and "false" path of execution, respectively.

 [TK_IF, if]
  [relop expr][TK_LT, <]
   [id expr][TK_ID, x]
   [id expr][TK_ID, y]
  [print stmt][TK_PRINT, print]
   [cosnt expr][TK_STR, "x is less than y"]
  [print stmt][TK_PRINT, print]
   [cosnt expr][TK_STR, "x is not less than y"]

Interestingly, both the first and second types compile to almost exactly the same pcode. Let's take a look at how its generated to understand way.

If/Else Statements As P-Code

Starting again with our simple example from above, we can see that an if statement with no else branch makes use of two jump instructions, one conditional, the other absolute. The first jump is immediately after the code for our test expression, and as you would expect, is a conditional jump.

When the test expression is evaluated, the result is left as the top item on the stack. The conditional jump pops that value from the stack and if it is false, performs a jump to after the statements for the "true" path, otherwise the instruction pointer increments as normal and the print statement is executed.

 if (x < y) {
   println "ok";
}

 6:   ( LOD, 5000, 0)   ;  x
 7:   ( LOD, 4999, 0)   ;  y
 8:   (  LT, (nil), 0)       ;   x < y ?
 9:   ( JPC, 13, 0)       ;  if not, jump to ip 13
10:   ( LDC, ok, 0)      ;
11:   (PRINT, (nil), 0)  ;  println "ok"
12:   ( JMP, 13, 0)
13:   (HALT, (nil), 0)

As you can see below, despite adding an additonal explicit path of execution, the code generated is practically the same, with the exception that the unconditional jump performed at the end of the "true" path makes alot more sense when it has something to in fact, jump over.

 if (x < y) {
    println "ok";
 } else {
   println "not ok";
 } 

 6:  (  LOD,     5000,     0)       ; x
 7:  (  LOD,     4999,     0)       ; y
 8:  (   LT,     (nil),     0)           ; x < y ?
 9:  (  JPC,     13,     0)           ; if not, jump to 13
10:  (  LDC,     ok,     0)         ' 'true branch'
11:  (PRINT,     (nil),     0)      ; print ok
12:  (  JMP,     15,     0)         ; skip else branch
13:  (  LDC,     not ok,     0)  ; 'else branch'
14:  (PRINT,     (nil),     0)     ; print "not ok"
15:  ( HALT,     (nil),     0)

So How do we get from the abstract syntax tree to the pictured p-code? I'm glad you asked, because that's what we will be covering next.

Generating P-Code for If Statements

As we saw above, the first action taken in any type of if statement is to execute the test expression. As such, we begin code generation of if statements by emit the instructions for the test expression by calling genCode() on the left most child.

void genIfStmt(ASTNode* node, bool isAddr) {
        genCode(node->child[0], isAddr);
        int skipPos1 = skipEmit(1);

We know that we need to emit a conditional jump after the test expression, but since we don't yet know where to jump to, we instead reserve the space with a call to skipEmit(1), saving the skipped address for backpatching.

Next, we call genCode() on the "true" case subtree. Upon returning from the call, we do a little fancy footwork with the calls to skipEmit() to facilitate our backpatching.

        genCode(node->child[1], isAddr);
        int skipPos2 = skipEmit(1);
        int currPos = skipEmit(0);

First, we skip one position, saving it's address: this is the slot we will later backpatch the unconditional jump into.

Then we call skipEmit with an argument of 0. Instead of skipping a slot, this instead returns the address of the current position. At our current point in the code generation, this also happens to be the address we need for back patching into the conditional jump from above.

        backup(skipPos1);
        emit(JPC, makeInt(currPos));
        restore();

After backpatching the conditional jump we call restore() to place us back at the end of the codepage to continue emitting instructions. We then call genCode() on the "else" branch of the if statement, and this is where we kind of get the functionality "for free". 

        genCode(node->child[2], isAddr);
        currPos = skipEmit(0);

Even if there is no "else" branch, and it simply returns after being called without emitting anything, upon returning we emit the same code we would have if there had been one.

        backup(skipPos2);
        emit(JMP, makeInt(currPos));
        restore();
}

The only thing that was left to do is backpatch the address for the uncoditional jump to the end of the if statement.

Well, that's what I've got for today. Until next time, Happy Hacking!

---