Instruction Selection - Approach

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 = t1

A good tiling for the x86 architecture is a succinct set of instructions:

MOV EAX, a XCHG EAX, b ADD 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.

Read more about this topic:  Instruction Selection

Famous quotes containing the word approach:

    “To approach a city ... as if it were [an] ... architectural problem ... is to make the mistake of attempting to substitute art for life.... The results ... are neither life nor art. They are taxidermy.”
    —Jane Jacobs (b. 1916)

    “I maintain that Truth is a pathless land, and you cannot approach it by any path whatsoever, by any religion, by any sect.”
    —Jiddu Krishnamurti (1895–1986)

    “The modern world needs people with a complex identity who are intellectually autonomous and prepared to cope with uncertainty; who are able to tolerate ambiguity and not be driven by fear into a rigid, single-solution approach to problems, who are rational, foresightful and who look for facts; who can draw inferences and can control their behavior in the light of foreseen consequences, who are altruistic and enjoy doing for others, and who understand social forces and trends.”
    —Robert Havighurst (20th century)