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