Instruction Selection

A systematic way to select one of the many ways to translate basic block computations


  • 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

  1. specify machine code instructions using tree patterns
  2. tool generate code generator that selects tiles
  3. can precompute optimal choices: do dynamic programming at generation time
  4. at compile time just run bottom-up tree automaton

Tree automata

  • 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: