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:

    “There is no calm philosophy of life here, such as you might put at the end of the Almanac, to hang over the farmer’s hearth,—how men shall live in these winter, in these summer days. No philosophy, properly speaking, of love, or friendship, or religion, or politics, or education, or nature, or spirit; perhaps a nearer approach to a philosophy of kingship, and of the place of the literary man, than of anything else.”
    —Henry David Thoreau (1817–1862)

    “The white man regards the universe as a gigantic machine hurtling through time and space to its final destruction: individuals in it are but tiny organisms with private lives that lead to private deaths: personal power, success and fame are the absolute measures of values, the things to live for. This outlook on life divides the universe into a host of individual little entities which cannot help being in constant conflict thereby hastening the approach of the hour of their final destruction.”
    —Policy statement, 1944, of the Youth League of the African National Congress. pt. 2, ch. 4, Fatima Meer, Higher than Hope (1988)

    “Saints are simply men & women who have fulfilled their natural obligation which is to approach God.”
    —Evelyn Waugh (1903–1966)