IR Generator

What?

• Converts the AST into Internal Representation (IR) Graph, which is fed into the Compiler Backend.
• There’s a fundamental problem with the AST. It doesn’t actually denote the order of which the code occurs (control-flow or data-flow). The IR helps that problem

What is the IR Graph?

Basically, we take an AST, and then convert it into English-like MIPS. So we go from:

IfStatement
├── Condition: BinaryOp('>', Var(x), IntLiteral(10))
├── ThenBranch: Assignment(Var(y), BinaryOp('+', Var(x), IntLiteral(5)))
└── ElseBranch: Assignment(Var(y), IntLiteral(20))

To:

block0:
    t1 = load x
    t2 = t1 > 10
    branch_if t2 block1 block2
 
block1:   // then branch
    t3 = t1 + 5
    store y, t3
    jump block3
 
block2:   // else branch
    store y, 20
    jump block3
 
block3:   // join point
    // continue execution

This then get’s converted into a graph:

The Details:

• Mutations are problematic. When optimising our IR, we actually rename our variables (e.g. x, which changed) to something that is only used once.
  • This is called Static Single Assignment - when each variable is a target of exactly one assignment.