Instruction selection
Encyclopedia
In computer science
, instruction selection is the stage of a compiler
backend that transforms its tree-based middle-level intermediate representation (IR) into a low-level IR very close to its final target language. In a typical compiler, it precedes both instruction scheduling
and register allocation
, so its output IR has an infinite set of pseudoregisters and may still be subject to peephole optimization
; otherwise, it closely resembles the target machine code
, bytecode
, or assembly language
. It works by "covering" the intermediate representation with as few tiles as possible. A tile is a template that matches a portion of the IR tree and can be implemented with a single target instruction.
For example, see the following sequence of intermediate instructions:
A good tiling for the x86 architecture is a succinct set of instructions:
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
.
is to build for the lowest common architecture. Use of any available processor extension is switched off by default, unless explicitly switched on by command line switches.
The use of a lowest common denominator strategy means that Processor Supplementary Instructions and Processor Supplementary Capabilities features are not used by default.
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, instruction selection is the stage of a compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
backend that transforms its tree-based middle-level intermediate representation (IR) into a low-level IR very close to its final target language. In a typical compiler, it precedes both instruction scheduling
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...
and register allocation
Register allocation
In compiler optimization, register allocation is the process of assigning a large number of target program variables onto a small number of CPU registers...
, so its output IR has an infinite set of pseudoregisters and may still be subject to peephole optimization
Peephole optimization
In compiler theory, peephole optimization is a kind of optimization performed over a very small set of instructions in a segment of generated code. The set is called a "peephole" or a "window"...
; otherwise, it closely resembles the target machine code
Machine code
Machine code or machine language is a system of impartible instructions executed directly by a computer's central processing unit. Each instruction performs a very specific task, typically either an operation on a unit of data Machine code or machine language is a system of impartible instructions...
, bytecode
Bytecode
Bytecode, also known as p-code , is a term which has been used to denote various forms of instruction sets designed for efficient execution by a software interpreter as well as being suitable for further compilation into machine code...
, or assembly language
Assembly language
An assembly language is a low-level programming language for computers, microprocessors, microcontrollers, and other programmable devices. It implements a symbolic representation of the machine codes and other constants needed to program a given CPU architecture...
. It works by "covering" the intermediate representation with as few tiles as possible. A tile is a template that matches a portion of the IR tree and can be implemented with a single target instruction.
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 promote 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:
XCHG EAX, b
ADD a, EAX
Typically, instruction selection is implemented with a backwards dynamic programming
Dynamic programming
In mathematics and computer science, dynamic programming is a method for solving complex problems by breaking them down into simpler subproblems. It is applicable to problems exhibiting the properties of overlapping subproblems which are only slightly smaller and optimal substructure...
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
Greedy algorithm
A greedy algorithm is any algorithm that follows the problem solving heuristic of making the locally optimal choice at each stagewith the hope of finding the global optimum....
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
Burg
Burg is the word for castle in various Germanic languages.Burg or Bürg or Buerg may refer to:*Burg bei Magdeburg, a city in Germany*Den Burg, a town in the Netherlands* Burg, former name of Melber, Kentucky...
.
Lowest common denominator strategy
The lowest common denominator strategy is an instruction selection technique used on platforms where Processor Supplementary Instructions exist to make executable programs portable across a wide range of computers. Under a lowest common denominator strategy, the default behaviour of the compilerCompiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
is to build for the lowest common architecture. Use of any available processor extension is switched off by default, unless explicitly switched on by command line switches.
The use of a lowest common denominator strategy means that Processor Supplementary Instructions and Processor Supplementary Capabilities features are not used by default.