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

Technologies

Step by step

  1. Write a three-address code interpreter first, to check every later step.
  2. Find basic blocks and edges, and print the graph.
  3. Add the local optimizations one at a time, comparing results with the interpreter after each.
  4. Add liveness analysis and use it to remove values that are dead across blocks.
  5. Add linear-scan allocation and print the register of every value.
  6. 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

Ways to improve it