Instruction selection
[1] [2] The simplest approach to instruction selection is known as macro expansion[3] or interpretative code generation.Unless the target machine is very simple, macro expansion in isolation typically generates inefficient code.To mitigate this limitation, compilers that apply this approach typically combine it with peephole optimization to replace combinations of simple instructions with more complex equivalents that increase performance and reduce code size.A pattern is a template that matches a portion of the graph and can be implemented with a single instruction provided by the target machine.For tree-shaped graphs, the least-cost cover can be found in linear time using dynamic programming,[11] but for DAGs and full-fledged graphs the problem becomes NP-complete and thus is most often solved using either greedy algorithms or methods from combinatorial optimization.