Implement Instruction Selection Using Tree Pattern Matching

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.