Instruction Selection Using Tree Grammars

Maximal Munch

  • start from root
  • take tile with most nodes that fits

Dynamic Programming

More sophisticated: dynamic programming

  • bottom up
  • find best tiling for each subtree

See Tiger book, page 182

Compiling Dynamic Programming Tiling for Given Architecture

When we fix architecture,

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

A tree automaton:

  • starts from leaves
  • move up according to transition function
  • transition function maps states in children and node type, into parent state

How to do it? See e.g. paper by T.Proebsting.

  • simplify the grammar to make it flat
  • use the fact that there are only finitely many types of nodes, and cost is additive (simplifying assumption)