Drawtomata / Three-address code and code generation
Three-address code and code generation
Type an expression such as a = b * -c + b * -c or a short program above. Drawtomata produces three-address code with quadruples, triples and indirect triples, and goes on to DAGs, SSA, basic blocks, liveness, target code and peephole optimization.
Three-address code
Every instruction has at most one operator and three addresses, such as t2 = b * t1. Temporaries hold intermediate results, in the order the expression is evaluated. For a = b * -c + b * -c:
| # | op | arg1 | arg2 | result |
|---|---|---|---|---|
| 0 | minus | c | t1 | |
| 1 | * | b | t1 | t2 |
| 2 | minus | c | t3 | |
| 3 | * | b | t3 | t4 |
| 4 | + | t2 | t4 | t5 |
| 5 | = | t5 | a |
Triples drop the result column and refer to earlier results by their number; indirect triples add a list of pointers so an optimizer can reorder instructions.
What else is on the tab
- DAG of a block by the value-number method, and the shorter code rebuilt from it.
- Static single-assignment form with φ-functions.
- Leaders, basic blocks, the flow graph and natural loops.
- Live variables and next-use information.
- A simple code generator with register and address descriptors and instruction costs.
- Peephole optimization of both three-address and target code.
Every optimized program is run against the original on random inputs before it is shown.