A compiler backend uses macro expansion: each IR operation maps directly to one fixed machine instruction. The target architecture has a single 'load-and-add' instruction that loads from memory and adds to a register in one cycle. What will the macro expansion backend do?
AAutomatically recognize the opportunity and emit the load-and-add instruction when the pattern appears
BEmit a separate LOAD followed by a separate ADD, missing the opportunity to use the combined instruction
CProduce the same output as tree pattern matching since the semantics are equivalent
DEmit a load-and-add only if the IR was explicitly annotated to request it
Macro expansion maps each IR instruction to a fixed template in isolation, so it can't recognize patterns that span multiple IR nodes. The load-and-add instruction corresponds to a two-node subtree (add whose child is a load), but macro expansion sees only one IR node at a time. Tree pattern matching exists precisely to exploit these combined instructions by covering multi-node IR subtrees with single machine instructions.
Question 2 Multiple Choice
Why does the optimal instruction selection problem become NP-hard in general when the IR is a DAG rather than a tree?
ADAGs have exponentially more nodes than equivalent trees, making pattern enumeration infeasible
BCommon subexpressions share nodes that could be covered by multiple overlapping patterns; choosing the globally optimal assignment is computationally intractable in general
CDynamic programming cannot process directed graphs, eliminating the efficient algorithm available for trees
DMachine instruction sets are too large for the DAG case to enumerate all possible coverings
In a tree, each node has exactly one parent, so pattern choices at each node interact only with their subtree. In a DAG, a shared node (common subexpression) can be reached from multiple places. A pattern covering that node affects the cost of covering every path through it. Optimizing these interdependent choices globally is NP-hard, unlike the tree case where dynamic programming produces an optimal linear-time solution.
Question 3 True / False
Optimal tree-tiling instruction selection can be solved in linear time using dynamic programming, but the analogous problem for DAGs is NP-hard in general.
TTrue
FFalse
Answer: True
For trees, dynamic programming works bottom-up: at each node, it considers all patterns whose root matches that node, computes the cost as the pattern's cost plus the optimal costs of the uncovered subtrees, and picks the minimum. This is O(n) in the tree size. For DAGs, shared nodes create interdependencies between covering decisions that the bottom-up algorithm can't handle optimally without exponential enumeration. Practical compilers handle this via heuristics like decomposing DAGs into trees.
Question 4 True / False
The goal of instruction selection is to minimize the total number of machine instructions emitted, since fewer instructions usually means faster execution.
TTrue
FFalse
Answer: False
The goal is to minimize total cost, not instruction count. Instructions have different costs—some take one cycle, others take many; some are compact, others occupy more code space. A single complex instruction (like load-and-add) can replace two simpler instructions and cost less in total even though it 'counts' as one. Equally, sometimes emitting slightly more instructions that use cheap, fast operations produces better code than fewer expensive ones. The tree-tiling algorithm minimizes cost based on a cost model assigned to each pattern.
Question 5 Short Answer
What is 'tree tiling' in instruction selection, and why does it produce better code than simple macro expansion?
Think about your answer, then reveal below.
Model answer: Tree tiling is the process of covering an IR expression tree with a set of non-overlapping pattern templates, where each pattern corresponds to one machine instruction that implements the semantics of a subtree. The algorithm finds the minimum-cost set of patterns that covers every node in the tree. It produces better code than macro expansion because it can use complex instructions that span multiple IR nodes—such as a single 'load-and-add' that implements a two-node add-over-load subtree—rather than emitting one instruction per IR node in isolation. Dynamic programming solves the optimal tiling for trees in linear time by computing, bottom-up at each node, the minimum-cost pattern assignment that covers the subtree rooted there.
The key insight is that the IR-to-machine mapping is not one-to-one: a single IR subtree can often be implemented by several different machine instruction sequences with different costs, and modern architectures have complex instructions specifically designed to exploit common patterns. Macro expansion ignores this by collapsing each IR node independently; tree tiling exploits it by considering the structure of the entire expression.