# 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

- 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

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)