Approach
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 promoting the usage of registers.
For example, see the following sequence of intermediate instructions:
t1 = a t2 = b t3 = t1 + t2 a = t3 b = t1A good tiling for the x86 architecture is a succinct set of instructions:
MOV EAX, a XCHG EAX, b ADD a, EAXTypically, 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.
Read more about this topic: Instruction Selection
Famous quotes containing the word approach:
“A lady with whom I was riding in the forest said to me that the woods always seemed to her to wait, as if the genii who inhabit them suspend their deeds until the wayfarer had passed onward; a thought which poetry has celebrated in the dance of the fairies, which breaks off on the approach of human feet.”
—Ralph Waldo Emerson (1803–1882)
“I have watched ... many literary fashions shoot up and blossom, and then fade and drop.... Yet with the many that I have seen come and go, I have never yet encountered a mode of thinking that regarded itself as simply a changing fashion, and not as an infallible approach to the right culture.”
—Ellen Glasgow (1873–1945)
“Do not approach with anything even resembling assurance a restaurant that moves.”
—Fran Lebowitz (b. 1950)