Instruction selection

For example, for the following sequence of middle-level IR code

t1 = a t2 = b t3 = t1 + t2 a = t3 b = t1

a good instruction sequence for the x86 architecture is

<span id="mwFQ"></span><span class="nf" id="mwFg">MOV</span><span class="w" id="mwFw"> </span><span class="no" id="mwGA">EAX</span><span class="p" id="mwGQ">,</span><span class="w" id="mwGg"> </span><span class="no" id="mwGw">a</span> <span class="nf" id="mwHA">XCHG</span><span class="w" id="mwHQ"> </span><span class="no" id="mwHg">EAX</span><span class="p" id="mwHw">,</span><span class="w" id="mwIA"> </span><span class="no" id="mwIQ">b</span> <span class="nf" id="mwIg">ADD</span><span class="w" id="mwIw"> </span><span class="no" id="mwJA">a</span><span class="p" id="mwJQ">,</span><span class="w" id="mwJg"> </span><span class="no" id="mwJw">EAX</span>

For a comprehensive survey on instruction selection, see.

Macro expansion

The simplest approach to instruction selection is known as macro expansion or interpretative code generation. A macro-expanding instruction selector operates by matching templates over the middle-level IR. Upon a match the corresponding macro is executed, using the matched portion of the IR as input, which emits the appropriate target instructions. Macro expansion can be done either directly on the textual representation of the middle-level IR, or the IR can first be transformed into a graphical representation which is then traversed depth-first. In the latter, a template matches one or more adjacent nodes in the graph.

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. This is known as the Davidson-Fraser approach and is currently applied in GCC.