Q7Compiler Design

Code generation is the final major phase of a compiler, responsible for translating the optimized intermediate representation into executable target machine code (or assembly). The code generator must produce correct code that efficiently uses machine resources.

• Instruction Selection: Mapping IR operations to machine instructions. Multiple machine instructions may implement a single IR operation; the code generator selects the most efficient sequence. Tree pattern matching or dynamic programming is used.
• Register Allocation: Deciding which variables/temporaries to keep in registers at each program point. More variables than registers require 'spilling' to memory. Graph coloring is the standard approach.
• Register Assignment: Assigning specific physical registers to the allocated register slots.
• Instruction Scheduling (Ordering): Reordering instructions to minimize pipeline stalls, fill delay slots, and improve instruction-level parallelism while preserving data dependencies.
• Memory Access Optimization: Choosing between stack, static, and register storage; generating efficient address computations for arrays and pointers.

• Simple code generation: Generate one or a few machine instructions per IR instruction, using a fixed mapping. Simple but not optimal.
• Macro expansion: Each IR operator is independently expanded into a fixed machine code template.
• Tree rewriting: Represent IR as a tree and use a pattern-matching rewriter to select instruction sequences that cover the tree (optimal via dynamic programming).
• Graph coloring register allocation: Build an interference graph and color it with k colors (registers); spill nodes that can't be colored.