Working through WACC – chapter 6, if and ternary

Just because all text is boring 🙂

The only really tricky thing in this chapter is dealing with the ternary , conditional expression ‘operator’. ie

int x = 2;
int y = x > 1 ? x : 42;

but the book walks through the recommended way of parsing this, and it works well.

Backend Generation

One really cool thing about this compiler design is how often things in a chapter ‘just work’ once we have done the TACKY generation phase. In fact we have not modified the TACKY grammar, and hence the x64 code generator, since chapter 4. Here is some sample TACKY for the features we added in this chapter, just FYI.

int main(void) {
  int x = 4;
  int y = 3;
  int z = x + y;
  if (x > 4)
    y= 10;
  else
    y = 0;
  return y == 42 ? x : 24;
}

produces

  Copy Int(4) Variable("x$0")
  Copy Int(3) Variable("y$1")
  Binary Add Variable("x$0") Variable("y$1") Variable("temp.0")
  Copy Variable("temp.0") Variable("z$2")
  Binary GreaterThan Variable("x$0") Int(4) Variable("temp.1")
  JumpIfZero Variable("temp.1") "_if_false_2"
  Copy Int(10) Variable("y$1")
  Jump "_if_end_3"
Label "_if_false_2"
  Copy Int(0) Variable("y$1")
Label "_if_end_3"
  Binary Equal Variable("y$1") Int(42) Variable("temp.4")
  JumpIfZero Variable("temp.4") "_ternary_false_6"
  Copy Variable("x$0") Variable("temp.7")
  Jump "_ternary_true_5"
Label "_ternary_false_6"
  Copy Int(24) Variable("temp.7")
Label "_ternary_true_5"
  Return Variable("temp.7")

You can see the variable renaming scheme described in chapter 5 in action.

I mentioned at the start how the backend is a two step process. It produces an intermediate form that I christened ‘moira’, a fix up phase then runs over the moira code, this is then used to generate x64 code.

Here is the moira code for the same program

  Mov(Immediate(4), Pseudo("x$0"))
  Mov(Immediate(3), Pseudo("y$1"))
  Mov(Pseudo("x$0"), Pseudo("temp.0"))
  Binary(Add, Pseudo("y$1"), Pseudo("temp.0"))
  Mov(Pseudo("temp.0"), Pseudo("z$2"))
  Cmp(Immediate(4), Pseudo("x$0"))
  Mov(Immediate(0), Pseudo("temp.1"))
  SetCC(G, Pseudo("temp.1"))
  Cmp(Immediate(0), Pseudo("temp.1"))
  JmpCC(E, "_if_false_2")
  Mov(Immediate(10), Pseudo("y$1"))
  Jmp("_if_end_3")
Label("_if_false_2")
  Mov(Immediate(0), Pseudo("y$1"))
Label("_if_end_3")
  Cmp(Immediate(42), Pseudo("y$1"))
  Mov(Immediate(0), Pseudo("temp.4"))
  SetCC(E, Pseudo("temp.4"))
  Cmp(Immediate(0), Pseudo("temp.4"))
  JmpCC(E, "_ternary_false_6")
  Mov(Pseudo("x$0"), Pseudo("temp.7"))
  Jmp("_ternary_true_5")
Label("_ternary_false_6")
  Mov(Immediate(24), Pseudo("temp.7"))
Label("_ternary_true_5")
  Mov(Pseudo("temp.7"), Register(AX))
  Ret

You can see how this closely follows the TACKY code but is aware of the x64 overall architecture, registers etc., plus it knows how to return a value to the OS via AX.

After the fix up phase the moira code looks like this

    Mov(Immediate(4), Stack(4))
    Mov(Immediate(3), Stack(8))
    Mov(Stack(4), Register(R10))
    Mov(Register(R10), Stack(12))
    Mov(Stack(8), Register(R10))
    Binary(Add, Register(R10), Stack(12))
    Mov(Stack(12), Register(R10))
    Mov(Register(R10), Stack(16))
    Cmp(Immediate(4), Stack(4))
    Mov(Immediate(0), Stack(20))
    SetCC(G, Stack(20))
    Cmp(Immediate(0), Stack(20))
    JmpCC(E, "_if_false_2")
    Mov(Immediate(10), Stack(8))
    Jmp("_if_end_3")
Label("_if_false_2")
    Mov(Immediate(0), Stack(8))
Label("_if_end_3")
    Cmp(Immediate(42), Stack(8))
    Mov(Immediate(0), Stack(24))
    SetCC(E, Stack(24))
    Cmp(Immediate(0), Stack(24))
    JmpCC(E, "_ternary_false_6")
    Mov(Stack(4), Register(R10))
    Mov(Register(R10), Stack(28))
    Jmp("_ternary_true_5")
Label("_ternary_false_6")
    Mov(Immediate(24), Stack(28))
Label("_ternary_true_5")
    Mov(Stack(28), Register(AX))
    Ret

This has mapped variables and temporaries to the stack, and any instruction that had both operands as memory addresses was converted to use a register instead. (Follow the evolution of the code for int z = x + y;)

You can see that this is very close to x64 code.

Its interesting to look at the inefficiencies here, that line int z = x + y; ends up as

Binary Add Variable("x$0") Variable("y$1") Variable("temp.0")
  Copy Variable("temp.0") Variable("z$2")

Why not just do

Binary Add Variable("x$0") Variable("y$1") Variable("z$2")

The reason is that the parser does not know where the result of the right hand expression is going to end up, so it puts it in a temporary, then the parser emits code to put that temporary into the variable z. Is that a by product of my single pass parse to TACKY, not sure, I am going to reread some earlier stuff in the book. If its not my fault then hopefully part III (optimizations) will clean it up.

Just to be complete here is the generated x64 code

INCLUDELIB LIBCMT
_TEXT   SEGMENT
PUBLIC main
main PROC
        push rbp
        mov rbp, rsp
        sub rsp, 28
        mov DWORD PTR[rbp-4], 4
        mov DWORD PTR[rbp-8], 3
        mov r10d, DWORD PTR[rbp-4]
        mov DWORD PTR[rbp-12], r10d
        mov r10d, DWORD PTR[rbp-8]
        add DWORD PTR[rbp-12], r10d
        mov r10d, DWORD PTR[rbp-12]
        mov DWORD PTR[rbp-16], r10d
        cmp DWORD PTR[rbp-4], 4
        mov DWORD PTR[rbp-20], 0
        setg BYTE PTR[rbp-20]
        cmp DWORD PTR[rbp-20], 0
        je _if_false_2
        mov DWORD PTR[rbp-8], 10
        jmp _if_end_3
_if_false_2:
        mov DWORD PTR[rbp-8], 0
_if_end_3:
        cmp DWORD PTR[rbp-8], 42
        mov DWORD PTR[rbp-24], 0
        sete BYTE PTR[rbp-24]
        cmp DWORD PTR[rbp-24], 0
        je _ternary_false_6
        mov r10d, DWORD PTR[rbp-4]
        mov DWORD PTR[rbp-28], r10d
        jmp _ternary_true_5
_ternary_false_6:
        mov DWORD PTR[rbp-28], 24
_ternary_true_5:
        mov eax, DWORD PTR[rbp-28]
        mov rsp, rbp
        pop rbp
        ret
main ENDP
_TEXT   ENDS
END

Note the DWORD and BYTE length specifiers

---

On to chapter 7