指令选择可能是一个大型的排列组合任务。对于像CISC这样的具有丰富寻址模式的机器，或者具有某些特殊目的指令（比如信号处理指令）的机器尤其如此。即使我们假设求值的顺序已经给定，并且假设寄存器通过另一个独立的机制进行分配，指令选择——为实现中间表示形式中出现的运算符而选择目标语言指令的问题——仍然是一个规模很大的排列组合任务。

我们把指令选择当作一个树重写问题来处理。目标指令的树形表示已经在代码生成器的生成器中得到有效使用。这种生成器可以依据目标机器的高层规约自动构造出一个代码生成器的指令选择阶段。对于某些机器，相对于使用树表示方法而言，使用DAG表示方法能够生成更好的代码。但是DAG匹配比树匹配更加复杂。