Instruction Selection
A systematic way to select one of the many ways to translate basic block computations
Note:
- instructions can do several simple steps at once
- computed expressions also do several things at once
Goal: represent expressions using instructions
Idea: both instructions and expressions are trees
- 'cover' expression trees with instruction trees
- 'tiling' problem on trees
Quadruples and moves in SimpleCFG.scala are trees
Can compute bigger trees:
- eliminate temporary variables that are used only in one block
- reverting CFG translation a bit, but need not worry about branches
How to tile a trees?
Maximal munch:
- start from root
- take tile with most nodes that fits
More sophisticated: dynamic programming
- bottom up
- find best tiling for each subtree
Tool support: code generator generators
- specify machine code instructions using tree patterns
- tool generate code generator that selects tiles
- can precompute optimal choices: do dynamic programming at generation time
- at compile time just run bottom-up tree automaton
- start from leaves
- move up according to transition function
- transition function maps states in children and node type, into parent state
A code generator generator approach:
- BURS Automata Generation by Proebsting