Code Generation

The code generator maps intermediate code to target instructions. Its main concerns are instruction selection, register allocation and instruction ordering.

Example

Source:  x = (a + b) * (c - d)

TAC:              Target code:
t1 = a + b        MOV a, R0
t2 = c - d        ADD b, R0
t3 = t1 * t2      MOV c, R1
x  = t3           SUB d, R1
                  MUL R1, R0
                  MOV R0, x

Register Allocation

Registers are the fastest storage, so they're used for the most-used values. Graph colouring is the classic approach: build an interference graph of variables that are live at the same time and colour it with k colours (registers). Uncoloured variables are spilled to memory.

Runtime Environment

Memory layout:   | Code | Static data | Heap → ...    ... ← Stack |

Activation record (stack frame):
+---------------------+
| Actual parameters   |
| Return value        |
| Control link        |  → caller's activation record
| Access link         |  → enclosing scope (non-local data)
| Saved machine state |  (return address, registers)
| Local data          |
| Temporaries         |
+---------------------+

Symbol Table

The symbol table stores each identifier's name, type, scope, size and memory location. It's usually implemented as a hash table, with one table per scope linked in a chain for nested scopes.