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

More sophisticated: dynamic programming

• bottom up
• find best tiling for each subtree

See Tiger book, page 182

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)