Target Code Generation
The final compiler phase: translating optimized intermediate code into instruction-level machine code tailored to a specific hardware architecture.
Issues in Code Generator Design
Designing an efficient code generator requires balancing compile time vs. execution time. Key issues include:
Target Program Choice
Should the compiler output absolute machine code (fastest, immovable), relocatable machine code (supports separate compilation mapping), or assembly language (requires later assembly pass)?
Instruction Selection
Mapping intermediate (IR) variables to the target machine's specific instruction set. Must consider instruction speed, cost, and side effects.
Register Allocation
Registers are the fastest but most limited hardware memory. Deciding which values stay in registers vs. main memory (RAM) is crucial.
Evaluation Order
Changing the order in which expressions are evaluated can drastically reduce the number of temporary registers needed.
The Target Machine Profile
A naive generic code generator models the target CPU as a generic architecture with a byte-addressable memory, general-purpose registers (R0, R1... R(n-1)), and standard instruction formats (OP dest, src). Real-world code generators (like LLVM Backends) contain thousands of lines modeling highly specific CPU quirks, instruction pipelines, and cache hierarchies.
Liveness & Register Allocation
Next-Use Information
Before allocating registers within a Basic Block, the compiler calculates the Liveness and Next-Use info for every variable.
By scanning a block backwards, it determines the exact instruction index where a variable is next read. Once a variable is read for the last time (it goes "dead"), the register holding it can be safely freed and reassigned to another variable!
Register Allocation & Assignment
The hardest problem in code generation. Can be framed as a Graph Coloring Problem.
- Allocation: Selecting which variables reside in registers vs memory.
- Assignment: Picking the exact physical register (e.g., RAX vs RCX) for a variable.
Runtime Storage Organization
When a program executes, the OS allocates memory. The compiler must structure exactly how data is laid out during runtime.
Memory Segments
- CodeImmutable machine instructions. Generated directly by the compiler. Size is fixed at compile time.
- StaticGlobal variables and constants. Size is fixed at compile time.
- HeapDynamic memory allocated at runtime (e.g.,
malloc()ornew). Grows upward. - StackFunction calls, local variables, and return addresses. Grows downward to meet the heap.
Activation Records
Every time a function is called, a block of memory called an Activation Record (or Stack Frame) is pushed onto the Call Stack. It tracks: