__NOTOC__
In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, ''instruction selection'' is the stage of a
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
backend that transforms its middle-level
intermediate representation
An intermediate representation (IR) is the data structure or code used internally by a compiler or virtual machine to represent source code. An IR is designed to be conducive to further processing, such as optimization and translation. A "good" ...
(IR) into a low-level IR. In a typical compiler, instruction selection precedes both
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, it tries to do the following without changing ...
and
register allocation
In compiler optimization, register allocation is the process of assigning local automatic variables and expression results to a limited number of processor registers.
Register allocation can happen over a basic block (''local register allocation' ...
; hence its output IR has an infinite set of pseudo-registers (often known as ''temporaries'') and may still be – and typically is – subject to
peephole optimization
Peephole optimization is an optimization technique performed on a small set of compiler-generated instructions; the small set is known as the peephole or window.
Peephole optimization involves changing the small set of instructions to an equiva ...
. Otherwise, it closely resembles the target
machine code
In computer programming, machine code is any low-level programming language, consisting of machine language instructions, which are used to control a computer's central processing unit (CPU). Each instruction causes the CPU to perform a very ...
,
bytecode
Bytecode (also called portable code or p-code) is a form of instruction set designed for efficient execution by a software interpreter. Unlike human-readable source code, bytecodes are compact numeric codes, constants, and references (norma ...
, or
assembly language
In computer programming, assembly language (or assembler language, or symbolic machine code), often referred to simply as Assembly and commonly abbreviated as ASM or asm, is any low-level programming language with a very strong correspondence be ...
.
For example, for the following sequence of middle-level IR code
t1 = a
t2 = b
t3 = t1 + t2
a = t3
b = t1
a good instruction sequence for the
x86 architecture
x86 (also known as 80x86 or the 8086 family) is a family of complex instruction set computer (CISC) instruction set architectures initially developed by Intel based on the Intel 8086 microprocessor and its 8088 variant. The 8086 was introd ...
is
MOV EAX, a
XCHG EAX, b
ADD a, EAX
For a comprehensive survey on instruction selection, see.
[
]
[
]
Macro expansion
The simplest approach to instruction selection is known as ''macro expansion'' or ''interpretative code generation''. A macro-expanding instruction selector operates by matching ''templates'' over the middle-level IR. Upon a match the corresponding ''macro'' is executed, using the matched portion of the IR as input, which emits the appropriate target instructions. Macro expansion can be done either directly on the textual representation of the middle-level IR, or the IR can first be transformed into a graphical representation which is then traversed depth-first. In the latter, a template matches one or more adjacent nodes in the graph.
Unless the target machine is very simple, macro expansion in isolation typically generates inefficient code. To mitigate this limitation, compilers that apply this approach typically combine it with
peephole optimization
Peephole optimization is an optimization technique performed on a small set of compiler-generated instructions; the small set is known as the peephole or window.
Peephole optimization involves changing the small set of instructions to an equiva ...
to replace combinations of simple instructions with more complex equivalents that increase performance and reduce code size. This is known as the ''Davidson-Fraser approach'' and is currently applied in
GCC.
Graph covering
Another approach is to first transform the middle-level IR into a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discre ...
and then
cover the graph using ''patterns''. A pattern is a template that matches a portion of the graph and can be implemented with a single instruction provided by the target machine. The goal is to cover the graph such that the total cost of the selected patterns is minimized, where the cost typically represents the number of cycles it takes to execute the instruction. For tree-shaped graphs, the least-cost cover can be found in linear time using
dynamic programming
Dynamic programming is both a mathematical optimization method and a computer programming method. The method was developed by Richard Bellman in the 1950s and has found applications in numerous fields, from aerospace engineering to economics.
I ...
, but for
DAGs and full-fledged graphs the problem becomes NP-complete and thus is most often solved using either
greedy algorithm
A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
s or methods from combinatorial optimization.
Lowest common denominator strategy
The ''
lowest common denominator
In mathematics, the lowest common denominator or least common denominator (abbreviated LCD) is the lowest common multiple of the denominators of a set of fractions. It simplifies adding, subtracting, and comparing fractions.
Description
The low ...
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
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs that ...
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
capabilities are not used by default.
References
External links
Alternative ways of supporting different generations of computer
{{Compiler optimizations
Compiler optimizations