Target code generation

The code generator takes the (optimized) intermediate representation and the symbol-table information and produces target machine code that is correct and efficient.

Major stages

1. Instruction selection - choose target instructions for each IR operation.
2. Register allocation and assignment - decide which values live in registers.
3. Instruction scheduling (ordering) - choose the order of instructions.
4. Final clean-up such as peephole optimization, then emit the code.

1. Instruction selection

Maps IR operations to machine instructions, choosing the cheapest sequence that implements them. The choice depends on the instruction set and addressing modes. Techniques: tree-pattern matching, dynamic programming over expression trees.

For a = b + c a naive translation is

LD  R0, b
LD  R1, c
ADD R0, R0, R1
ST  a, R0

and for x = x + 1 a good selector uses a single INC x (or an add with an immediate) instead of load, add and store.

Contribution: decides the number and cost of instructions, so the code is small and fast, and uses special instructions where available.

2. Register allocation

Registers are far faster than memory but very few. Allocation decides which variables/temporaries to keep in registers; assignment picks the specific register. Methods: usage counts, graph colouring (variables that are live at the same time interfere and get different registers). If there are not enough registers, a value is spilled to memory.

Contribution: reduces loads and stores, which dominate execution time.

3. Instruction scheduling

Reorders independent instructions to avoid pipeline stalls and to use all functional units, without changing the program's result (data dependences must be respected).

Assume a load takes one extra cycle before its result can be used:

Unscheduled	Scheduled
LD R1, a	LD R1, a
ADD R2, R1, R3 (stall)	LD R4, b
LD R4, b	ADD R2, R1, R3
ADD R5, R4, R6 (stall)	ADD R5, R4, R6

The scheduled version has no stalls.

Contribution: hides latency and increases instruction-level parallelism, so the program runs faster on the pipeline.

Interaction: the stages influence each other. Scheduling more instructions in parallel needs more registers, and heavy register reuse creates dependences that limit scheduling. Compilers therefore balance the two.

Summary

Stage	Goal	Result
Instruction selection	Correct, low-cost instruction sequence	Fewer, cheaper instructions
Register allocation	Keep hot values in registers	Fewer memory accesses
Instruction scheduling	Avoid stalls, fill pipeline	Fewer cycles