An optimizing back end
The problem
Build a back end that takes three-address code, optimizes it, analyses its control flow and assigns registers, and show how much each step improves the code.
Requirements
- Read three-address code with labels, jumps and prints
- Split it into basic blocks and build the control-flow graph
- Optimize each block with constant folding, copy propagation, common subexpressions and dead code elimination
- Compute live variables for every block
- Allocate a chosen number of registers with linear scan and report spills
- Check that the optimized code prints the same results as the original with an interpreter
Technologies
- Python
- Graphs
- Sets
- Dataflow analysis
Step by step
- Write a three-address code interpreter first, to check every later step.
- Find basic blocks and edges, and print the graph.
- Add the local optimizations one at a time, comparing results with the interpreter after each.
- Add liveness analysis and use it to remove values that are dead across blocks.
- Add linear-scan allocation and print the register of every value.
- Measure instruction counts and steps before and after, on several programs.
Expected result
A back end that reports, for each program, the code before and after optimization, the control-flow graph, the live sets and the register assignment.
How it is evaluated
- Optimized programs always print the same results as the originals
- Liveness results match hand calculations on small examples
- The allocator never gives one register to two values that are live together
- The report shows the effect of each optimization
Ways to improve it
- Allocate registers with graph colouring and compare the number of spills
- Convert the code to SSA form before optimizing
- Move loop-invariant computations out of loops