Q5Compiler Design

Code generation is the process of mapping optimized intermediate representation to target machine instructions. The code generator must correctly implement the program's semantics while efficiently using machine resources (registers, cache, pipeline).

For each IR operation, the code generator selects appropriate machine instructions. Multiple instruction sequences may implement the same operation; the choice affects performance. Tree pattern matching selects instructions by matching the IR tree against patterns corresponding to machine instructions and choosing covers with minimum cost.

Register allocation determines which program variables/temporaries are kept in registers at each point. It is formulated as a graph coloring problem:

• Liveness Analysis: Compute which variables are live (still needed) at each program point using backward data flow analysis. IN[B] = use[B] ∪ (OUT[B] - def[B]); OUT[B] = ∪ IN[S] for successors S.
• Build Interference Graph: Create a node for each variable. Add an edge between two nodes if the variables are simultaneously live (their live ranges overlap). Simultaneously live variables cannot share a register.
• Graph Coloring: Color the interference graph with k colors (k = number of available registers) such that no two adjacent nodes have the same color. Each color represents a register.
• Spilling: If the graph cannot be k-colored, select a variable to spill (store in memory instead of a register). Add load/store instructions for the spilled variable and repeat coloring.
• Register Assignment: Map each color to a specific physical register.

A DAG (Directed Acyclic Graph) is a compact representation of a basic block that makes common subexpressions explicit and identifies dead computations. Construction:

• For each statement x = y op z in the basic block: check if a node labeled op with children node(y) and node(z) already exists; if yes, do not create a new node (CSE identified); if no, create a new interior node labeled op with children node(y) and node(z). Label the new node with x.
• Leaf nodes represent variables/constants as they appear at the start of the block.
• Interior nodes represent computed values; labels on nodes are the variables that currently hold that value.
• Dead computations: nodes with no labels (their values are never used) can be eliminated.

• t1 = a + b
• t2 = a + b → same as t1 (CSE: t2 and t1 share the same '+' node)
• t3 = t1 t2 → '' node with children being the shared '+' node (equivalent to t1^2)
• Generated code using DAG: t1 = a + b; t3 = t1 * t1 (saving one addition)

Instruction scheduling reorders instructions to minimize pipeline stalls while preserving data and control dependencies. It exploits instruction-level parallelism. List scheduling is a common greedy technique: maintain a list of ready instructions (all dependencies satisfied), schedule the highest-priority ready instruction, update the ready list, and repeat.