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:

    “I am always glad to think that my education was, for the most part, informal, and had not the slightest reference to a future business career. It left me free and untrammeled to approach my business problems without the limiting influence of specific training.”
    —Alice Foote MacDougall (1867–1945)

    “This is an approach to that universal language which men have sought in vain.”
    —Henry David Thoreau (1817–1862)

    “So live that when thy summons comes to join
    The innumerable caravan that moves
    To that mysterious realm, where each shall take
    His chamber in the silent halls of death,
    Thou go not, like the quarry-slave at night,
    Scourged to his dungeon, but, sustained and soothed
    By an unfaltering trust, approach thy grave
    Like one who wraps the drapery of his couch
    About him and lies down to pleasant dreams.”
    —William Cullen Bryant (1794–1878)