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:
“Fishermen, hunters, woodchoppers, and others, spending their lives in the fields and woods, in a peculiar sense a part of Nature themselves, are often in a more favorable mood for observing her, in the intervals of their pursuits, than philosophers or poets even, who approach her with expectation. She is not afraid to exhibit herself to them.”
—Henry David Thoreau (1817–1862)
“F.R. Leavis’s “eat up your broccoli” approach to fiction emphasises this junkfood/wholefood dichotomy. If reading a novel—for the eighteenth century reader, the most frivolous of diversions—did not, by the middle of the twentieth century, make you a better person in some way, then you might as well flush the offending volume down the toilet, which was by far the best place for the undigested excreta of dubious nourishment.”
—Angela Carter (1940–1992)
“Let me approach at least, and touch thy hand.
[Samson:] Not for thy life, lest fierce remembrance wake
My sudden rage to tear thee joint by joint.
At distance I forgive thee, go with that;
Bewail thy falsehood, and the pious works
It hath brought forth to make thee memorable
Among illustrious women, faithful wives:
Cherish thy hast’n’d widowhood with the gold
Of Matrimonial treason: so farewel.”
—John Milton (1608–1674)