A basic approach in instruction selection is to use some templates for translation of each instruction in an intermediate representation. But naïve use of templates leads to inefficient code in general. Additional attention needs to be paid to avoid duplicated memory access by reordering and merging instructions and promote the usage of registers.
For example, see the following sequence of intermediate instructions:
t1 = a t2 = b t3 = t1 + t2 a = t3 b = t1
A good tiling for the x86 architecture is a succinct set of instructions:
XCHG EAX, b XADD a, EAX
Typically, instruction selection is implemented with a backwards dynamic programming algorithm which computes the "optimal" tiling for each point starting from the end of the program and based from there. Instruction selection can also be implemented with a greedy algorithm that chooses a local optimum at each step.
The code that performs instruction selection is usually automatically generated from a list of valid patterns. Various generator programs differ in the amount of analysis that they perform while they run, rather during the compiler's instruction selection phase. An example of generator program for instruction selection is BURG.
US Patent Issued to Seiko-Epson on May 10 for "High-Performance Superscalar-Based Computer System with Out-Of Order Instruction Execution and Concurrent Results Distribution" (California Inventors)
May 11, 2011; ALEXANDRIA, Va., May 11 -- United States Patent no. 7,941,635, issued on May 10, was assigned to Seiko-Epson Corp. (Tokyo)....