Instruction selection

Instruction selection

In computer programming, Instruction selection is a compiler optimization that transforms an intermediate representation of a program into the final compiled code, either in binary or assembly format. It works by "covering" the intermediate representation with as few tiles as possible.

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 promote the usage of registers.

For example, see the following sequence of intermediate instructions:

t1 = at2 = bt3 = t1 + t2a = t3b = t1

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

XCHG EAX, bXADD 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. An example of generator program for instruction selection is BURG.


Wikimedia Foundation. 2010.

Игры ⚽ Нужен реферат?

Look at other dictionaries:

  • Instruction scheduling — In computer science, instruction scheduling is a compiler optimization used to improve instruction level parallelism, which improves performance on machines with instruction pipelines. Put more simply, without changing the meaning of the code, it …   Wikipedia

  • Instruction Concerning the Criteria for the Discernment of Vocations with regard to Persons with Homosexual Tendencies in view of their Admission to the Seminary and to Holy Orders — is a document published in November 2005 by the Congregation for Catholic Education, one of the top level offices of the Catholic Church. Contents 1 Commentary and implications 2 Reactions to the document …   Wikipedia

  • Instruction set — An instruction set, or instruction set architecture (ISA), is the part of the computer architecture related to programming, including the native data types, instructions, registers, addressing modes, memory architecture, interrupt and exception… …   Wikipedia

  • Sélection internationale — École normale supérieure (rue d Ulm Paris) Pour les articles homonymes, voir Ulm (homonymie) et École normale supérieure. École normale supérieure rue d Ulm Paris …   Wikipédia en Français

  • Unite d'instruction de la brigade Gurkha — Unité d instruction de la brigade Gurkha Stationnée à Catterick en Grande Bretagne, cette unité d instruction de la brigade Gurkha a en charge le recrutement et la formation initiale des Gurkhas. Sommaire 1 Histoire 1.1 Training Depot Brigade of… …   Wikipédia en Français

  • Unité d'instruction de la brigade gurkha — Stationnée à Catterick en Grande Bretagne, cette unité d instruction de la brigade Gurkha a en charge le recrutement et la formation initiale des Gurkhas. Sommaire 1 Histoire 1.1 Training Depot Brigade of Gurkhas (TDBG) …   Wikipédia en Français

  • Unité d'instruction de la brigade Gurkha — Stationnée à Catterick en Grande Bretagne, cette unité d instruction de la brigade Gurkha a en charge le recrutement et la formation initiale des Gurkhas. Sommaire 1 Histoire 1.1 Training Depot Brigade of Gurkhas (TDBG) 1.2 …   Wikipédia en Français

  • Sheltered instruction — is an approach to teaching English language learners which integrates language and content instruction. The dual goals of sheltered instruction are: # to provide access to mainstream, grade level content, and # to promote the development of… …   Wikipedia

  • Oregon Superintendent of Public Instruction — Great Seal of the State of Oregon Details of Office Branch: Executive Type …   Wikipedia

  • Officer Selection Officer — A Marine Corps Officer Selection Officer (OSO) leads a team of Marines and Civilian employees that assists university students with their applications for a Marine Corps Commission as 2nd Lieutenant. Contents 1 Responsibilities 2 Programs 3… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”