Chapter 7 Control Flow: If/Else

Where is this going: we want to add basic control flow to our language, starting with conditionals (if/else).

We need to learn about labels and jumps at the assembly level, and some background about how the CPU chooses the next instruction.

We touch on the idea of continuations, as a way of describing “what to do next”: the point in the code where execution resumes after an if/else is the continuation of the statement.

7.1 Language Definition

7.1.1 Syntax

<op>    ::= '+' | '-' | '*' | '/'
<bop>   ::= '==' | '!=' | '<' | '>' | '<=' | '>='
<atom>  ::= <number>
          | '('<simp>')'
          | <ident>
          | '{'<exp>'}'
<uatom> ::= [<op>]<atom>
<cond>  ::= <simp><bop><simp>
<simp>  ::= <uatom>[<op><uatom>]*
          | 'if' '('<cond>')' <simp> 'else' <simp>
<exp>   ::= <simp>
          | 'val' <ident> '=' <simp>';' <exp>

7.1.2 AST

case class Cond(op: String, lop: Exp, rop: Exp)
case class If(cond: Cond, tBranch: Exp, eBranch: Exp) extends Exp

7.1.3 Semantics

type Val = Int
def evalCond(op: String)(v: Val, w: Val) = op match {
  case "==" => v == w
  // ...
}
def eval(exp: Exp)(env: Env): Val = exp match {
  case If(Cond(op, l, r), tBranch, eBranch) =>
    if (evalCond(op)(eval(l)(env), eval(r)(env)))
      eval(tBranch)(env)
    else
      eval(eBranch)(env)
}

Example

eval(Let("x", 1,   // Omitted Lit
       If(Cond(">", Ref("x"), 0), Prim("+", 2, Ref("x")), 0)))(Map())

7.2 Code Generation

7.2.1 Machine model

The CPU has a program counter register (PC) that specifies where to load the next instruction from. The ISA provides jump or branch instructions that modify the program counter, e.g. specifying “add 16” to the PC.

At the essembly level, we don’t have to deal with numeric offsets for jumps explicitly. Instead, we can define labels in the assembly code. The assembler, which compiles source-level assembly code to binary machine code, and the linker, which merges separately compiled modules, will figure out the correct jump offset in the generated binary executable.

Hardware architectures also support indirect jumps, where an absolute target address is provided in a register, and conditional jumps (these are often called branches), which are only executed if a given condition is true. A conditional jump based on comparing two values, for example, is typically executed in two steps. First, the two values are compared, and the result is stored in a special flags register, e.g. setting a bit that indicates one of the value was smaller that the other one. Then, a conditional jump instruction is executed that inspects the desired bit in the flags register, and either does nothing or updates the PC to continue execution at the specified target address based on the outcome of the test.

Todo: X86 Example here

Todo: Scala Example here

In Scala, we can simulate jumps using functions that do not return. These have return type Nothing.

Example:

def main(): Nothing = {
  if (cond) thenBranch() else elseBranch()
}
def thenBranch(): Nothing = {
  ...
  endIf()
}
def elseBranch(): Nothing = {
  ...
  endIf()
}
def endIf(): Nothing = {
  ...
  exit() // provided by runtime
}

Note: function calls like this still consume stack space in Scala, so they aren’t real jumps.

The function endIf is called the continuation of the if/else statement, because this is where execution continues afterwards. Following this terminology, endIf is also the continuation of thenBranch and elseBranch.

7.2.2 Stack-Based Interpreter

Focus on handling of flags register first.

val memory = new Array[Int](MEM_SIZE)
var flag = 0

def evalCond(op: String) = op match {
  case "==" => flag == 0
  // ...
}

def eval(exp: Exp, sp: Int)(env: Env): Unit = exp match {
  case If(Cond(op, l, r), tBranch, eBranch) =>
    flag = eval(l, sp)(env) - eval(r, sp + 1)(env)
    if (evalCond(op))
      eval(tBranch, sp)(env)
    else
      eval(eBranch, sp)(env)
}

eval(Let("x", 1,   // Omitted Lit
       If(Cond(">", Ref("x"), 0), Prim("+", 2, Ref("x")), 0)), 0)(Map())

7.2.3 Stack-Based Compiler

def emitCode(exp: Exp): Unit = {
  emitln("val memory = new Array[Int](1000)")
  emitln("var flag = 0")
  trans(exp, 0)(Env())
  emitln(s"memory(0)")
}

def trans(exp: Exp, sp: Int)(env: Env) = exp match {
  case If(Cond(op, l, r), tBranch, eBranch) =>
    trans(l, sp)(env); trans(r, sp+1)(env)
    emitln(s"flag = (memory($sp) - memory(${sp+1}))") // Set flag value
    emitln(s"if (flag $op 0) {")
    trans(tBranch, sp)(env)
    emitln("} else {")
    trans(eBranch, sp)(env)
    emitln("}")
}

Example:

emitCode(Let("x", 1,   // Omitted Lit
       If(Cond(">", Ref("x"), 0), Prim("+", 2, Ref("x")), 0)))

val memory = new Array[Int](1000); var flag = 0

memory(0) = 1
memory(1) = memory(0); memory(2) = 0
flag = (memory(1) - memory(2))
if (flag > 0) {
  memory(1) = 2
  memory(2) = memory(0)
  memory(1) += memory(2)
} else {
  memory(1) = 0
}
memory(0) = memory(1)
memory(0)

Note: this isn’t the full deal. Need labels

7.2.4 Stack-Based Compiler with Labels and Jumps

val memory = new Array[Int](1000); var flag = 0

def main() {
  memory(0) = 1
  memory(1) = memory(0); memory(2) = 0
  flag = (memory(1) - memory(2))
  if (flag > 0) thenBranch() else elseBranch()
}
def thenBranch() = {
  memory(1) = 2
  memory(2) = memory(0)
  memory(1) += memory(2)
  endIf()
}
def elseBranch() = {
  memory(1) = 0
  endIf()
}
def endIf() = {
  memory(0) = memory(1)
  exit()
}

Exercise: implement compiler that emits this

Exercise (hard, need background): derive this compiler from an interpreter. Hint: continuation passing style (CPS)

7.2.5 x86 Flags And Jumps

The x86 processor is using flags to handle comparison.

cmpq %rbx, %rax    # compare %rax to rbx and set the flags accordingly

Several instructions can be used for jump:

je  labelA          # jump equals
jne labelA          # jump not equals
jg  labelA          # jump greater
jge labelA          # jump greater or equals
jl  labelA          # jump less
jle labelA          # jump less or equals
jmp labelA          # always jump

Example:

  movq $0, %rax
  movq $1, %rbx
  cmpq %rbx, %rax    # operands inverted (%rax > %rbx)!!
  jg greater
  movq $1, %rax
greater:
  ret                # what value is in %rax?

Returns 1, because 0 is not greater than 1 so the jump doesn’t happen.

7.2.6 Compiling Ifs

trans(If(Cond(op, l, r), tBranch, eBranch), 0)(Map())

In order to compile the if statement, we are going to follow this idea:

  ... # code for l and r
  cmpq <r>, <l>
  j<op> if_then # the jump operation depends on 'op'
  ... #  code for else branch
  jmp if_end   # unconditional jump
if_then: # label for the beginning of the then branch
  ..  # code for then branch
if_end:
   ... # code for the rest

Example:

trans(If(Cond("==", 1, 0), 2, 3), 0)(Map())

# begin code generated
  movq $1, %rbx # generate code that compute l, stored in %rbx
  movq $0, %rcx # generate code that compute r, stored in %rcx
  cmpq %rcx, %rbx
  je if1_then
  movq $3, %rbx # generate code for eBranch, store result in %rbx
  jmp if1_end
if1_then:
  movq $2, %rbx # generate code for tBranch, store result in %rbx
if1_end:
# end code generated
  movq %rbx, %rax
  ret

7.3 Parsing

Todo: Simple, left as exercise.

7.4 Where Are We?

We added IF statements to our language and discussed the syntax, semantics and simple implementation.