Implement Instruction Selection Using Tree Pattern Matching

Topic Overview

Tree Pattern Matching

Instruction selection maps IR trees to machine instruction trees. BURG and LLVM's SelectionDAG use dynamic programming over tree patterns. A simple matcher associates IR opcodes with assembly templates and picks the cheapest covering.

Tile the Tree

Break the IR expression tree into tiles each coverable by one or two machine instructions. a + b where both are in registers tiles to a single add. a + constant may tile to lea on x86.

cCopy
Loading…

• Leaf tiles: constants fit in immediates, else load
• Commutative ops may swap operands for better tiles
• Address modes: [base + index*scale + offset] on x86
• Covering is dynamic programming bottom-up on the tree

Connecting to real compilers

Production compilers embed this step inside a longer pipeline. GCC flows through cpp, cc1, assembly, and ld; Clang uses the driver, Sema, LLVM IR passes, and a target backend. LLVM bitcode, JVM bytecode, and WASM are other familiar IRs at the same layer. The exercise isolates one pass so you can test it alone before chaining it to the next stage.

Why for this exercise

You will implement instruction selection using tree pattern matching. This exercise asks you to match IR operation trees to assembly instruction sequences, choosing tiles that minimize instruction count.

Your Task

Select machine instructions by tiling IR trees with the cheapest set of instruction patterns (optimal tiling by dynamic programming), for the Jouette machine from Appel's Modern Compiler Implementation.

Input

One IR tree per line, as an S-expression:

cCopy
Loading…

A TEMP is already in a register named after it; r0 always holds 0. A MOVE is always to memory.

Tiles (in table order: the order breaks ties)

Every tile costs 1; e marks a subtree the tile leaves to other tiles, c a CONST.

A TEMP leaf costs 0 (it is its own register).

Algorithm

1. Label bottom-up: the cost of a node is the minimum over matching tiles of 1 + the costs of the tile's e-subtrees. On a tie, the tile earlier in the table wins.
2. Emit top-down from the root's chosen tile: first emit the tile's e-subtrees left to right, then the tile itself, writing its result to a new register r1, r2, … (numbered in emission order, restarting at r1 for each tree).

Output

For each tree: the tree echoed with single spaces, then its instructions indented two spaces, then cost=N. Finish with trees=T total-cost=C.

Example

Input:

cCopy
Loading…

Output:

cCopy
Loading…

Requirements

1. Store the best cost and tile on each node during a post-order labelling pass; emit in a separate pass.
2. Tiles that swallow a CONST operand must not also charge for that constant.

Hidden tests include Appel's a[i] := x tree (two optimal tilings of cost 6: the table order decides), constant folding opportunities the tiler cannot see ((+ (CONST 3) (CONST 4))), and every LOAD/STORE form.