Programming Languages and Translators
Lecture 23: Code Generation Algorithms
April 21, 2008
- Next-use information
- A simple code generator
- Optimal code generation for expression trees
- Instruction selection
- Optimization of basic blocks
- Order of evaluation
2. Next-use Information
- If there is a three-address instruction sequence of the form
then we say statement
i: x = y + z
. no assignments to x
j: a = x + b
j uses the
x computed at
We also say that
x is live at statement
A simple way to find next uses is to scan backward from
the end of a basic block keeping track for each name
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
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.
- ALSU, Sections 8.4, 8.6, 8.10