# COMS W4115 Programming Languages and Translators Lecture 23: Code Generation Algorithms April 21, 2008

## Lecture Outline

1. Review
2. Next-use information
3. A simple code generator
4. Optimal code generation for expression trees

## 1. Review

• Instruction selection
• Optimization of basic blocks
• Order of evaluation

## 2. Next-use Information

• If there is a three-address instruction sequence of the form
• ``````
i:  x = y + z

.
. no assignments to x
.

j:  a = x + b
``````
then we say statement `j` uses the value of `x` computed at `i`.
• We also say that `x` is live at statement `i`.
• A simple way to find next uses is to scan backward from the end of a basic block keeping track for each name `x` whether `x` has a next use in the block and if not whether `x` is live on exit from that block. See Alg. 8.7, p. 528.

## 3. A Simple Code Generator

• There is a simple algorithm to generate code for a basic block. It generates code for each three-address instruction in turn, keeping track of what values are in what registers to avoid generating redundant loads and stores.
• It uses a register descriptor to keep track of what value is currently in each register.
• It uses an address descriptor to keep track of locations where the current value of a name can be found at run time.
• It uses a routine `getReg` to return a location `L` to hold the value of the variable `x` for a three-address instruction `x = y + z`.
• See Section 8.6 (pp. 542-548) for details of the algorithm.

## 4. Optimal Code Generation for Expression Trees

• Assume a simple register machine with instructions of the form
• `LD reg, mem`
• `ST mem, reg`
• `OP reg, reg, reg`
• Label the nodes in an expression tree with Ershov numbers.
• The Sethi-Ullman algorithm (Alg. 8.24, pp. 568-572) can be used to generate code that minimizes the number of spills to evaluate the expression tree.