@@ -90,51 +119,51 @@
The LLVM target-independent code generator is a framework that provides a
-suite of reusable components for translating the LLVM internal representation to
-the machine code for a specified target -- either in assembly form (suitable for
-a static compiler) or in binary machine code format (usable for a JIT compiler).
-The LLVM target-independent code generator consists of five main components:
+ suite of reusable components for translating the LLVM internal representation
+ to the machine code for a specified target—either in assembly form
+ (suitable for a static compiler) or in binary machine code format (usable for
+ a JIT compiler). The LLVM target-independent code generator consists of five
+ main components:
-- Abstract target description interfaces which
-capture important properties about various aspects of the machine, independently
-of how they will be used. These interfaces are defined in
-include/llvm/Target/.
-
-- Classes used to represent the machine code being
-generated for a target. These classes are intended to be abstract enough to
-represent the machine code for any target machine. These classes are
-defined in include/llvm/CodeGen/.
-
-- Target-independent algorithms used to implement
-various phases of native code generation (register allocation, scheduling, stack
-frame representation, etc). This code lives in lib/CodeGen/.
-
-- Implementations of the abstract target description
-interfaces for particular targets. These machine descriptions make use of
-the components provided by LLVM, and can optionally provide custom
-target-specific passes, to build complete code generators for a specific target.
-Target descriptions live in lib/Target/.
-
-- The target-independent JIT components. The LLVM JIT is
-completely target independent (it uses the TargetJITInfo structure to
-interface for target-specific issues. The code for the target-independent
-JIT lives in lib/ExecutionEngine/JIT.
-
+ - Abstract target description interfaces which
+ capture important properties about various aspects of the machine,
+ independently of how they will be used. These interfaces are defined in
+ include/llvm/Target/.
+
+ - Classes used to represent the machine code
+ being generated for a target. These classes are intended to be abstract
+ enough to represent the machine code for any target machine. These
+ classes are defined in include/llvm/CodeGen/.
+
+ - Target-independent algorithms used to implement
+ various phases of native code generation (register allocation, scheduling,
+ stack frame representation, etc). This code lives
+ in lib/CodeGen/.
+
+ - Implementations of the abstract target description
+ interfaces for particular targets. These machine descriptions make
+ use of the components provided by LLVM, and can optionally provide custom
+ target-specific passes, to build complete code generators for a specific
+ target. Target descriptions live in lib/Target/.
+
+ - The target-independent JIT components. The LLVM JIT is
+ completely target independent (it uses the TargetJITInfo
+ structure to interface for target-specific issues. The code for the
+ target-independent JIT lives in lib/ExecutionEngine/JIT.
-
-Depending on which part of the code generator you are interested in working on,
-different pieces of this will be useful to you. In any case, you should be
-familiar with the target description and machine code representation classes. If you want to add
-a backend for a new target, you will need to implement the
-target description classes for your new target and understand the LLVM code representation. If you are interested in
-implementing a new code generation algorithm, it
-should only depend on the target-description and machine code representation
-classes, ensuring that it is portable.
-
+
Depending on which part of the code generator you are interested in working
+ on, different pieces of this will be useful to you. In any case, you should
+ be familiar with the target description
+ and machine code representation classes. If you
+ want to add a backend for a new target, you will need
+ to implement the target description classes for
+ your new target and understand the LLVM code
+ representation. If you are interested in implementing a
+ new code generation algorithm, it should only
+ depend on the target-description and machine code representation classes,
+ ensuring that it is portable.
@@ -146,38 +175,27 @@ classes, ensuring that it is portable.
The two pieces of the LLVM code generator are the high-level interface to the
-code generator and the set of reusable components that can be used to build
-target-specific backends. The two most important interfaces (TargetMachine and TargetData) are the only ones that are
-required to be defined for a backend to fit into the LLVM system, but the others
-must be defined if the reusable code generator components are going to be
-used.
+ code generator and the set of reusable components that can be used to build
+ target-specific backends. The two most important interfaces
+ (
TargetMachine
+ and
TargetData) are the only ones that are
+ required to be defined for a backend to fit into the LLVM system, but the
+ others must be defined if the reusable code generator components are going to
+ be used.
This design has two important implications. The first is that LLVM can
-support completely non-traditional code generation targets. For example, the C
-backend does not require register allocation, instruction selection, or any of
-the other standard components provided by the system. As such, it only
-implements these two interfaces, and does its own thing. Another example of a
-code generator like this is a (purely hypothetical) backend that converts LLVM
-to the GCC RTL form and uses GCC to emit machine code for a target.
-
-
This design also implies that it is possible to design and
-implement radically different code generators in the LLVM system that do not
-make use of any of the built-in components. Doing so is not recommended at all,
-but could be required for radically different targets that do not fit into the
-LLVM machine description model: programmable FPGAs for example.
-
-
Important Note: For historical reasons, the LLVM SparcV9 code
-generator uses almost entirely different code paths than described in this
-document. For this reason, there are some deprecated interfaces (such as
-TargetSchedInfo), which are only used by the
-V9 backend and should not be used by any other targets. Also, all code in the
-lib/Target/SparcV9 directory and subdirectories should be considered
-deprecated, and should not be used as the basis for future code generator work.
-The SparcV9 backend is slowly being merged into the rest of the
-target-independent code generators, but this is a low-priority process with no
-predictable completion date.
+ support completely non-traditional code generation targets. For example, the
+ C backend does not require register allocation, instruction selection, or any
+ of the other standard components provided by the system. As such, it only
+ implements these two interfaces, and does its own thing. Another example of
+ a code generator like this is a (purely hypothetical) backend that converts
+ LLVM to the GCC RTL form and uses GCC to emit machine code for a target.
+
+
This design also implies that it is possible to design and implement
+ radically different code generators in the LLVM system that do not make use
+ of any of the built-in components. Doing so is not recommended at all, but
+ could be required for radically different targets that do not fit into the
+ LLVM machine description model: FPGAs for example.
@@ -188,78 +206,73 @@ predictable completion date.
-
The LLVM target-independent code generator is designed to support efficient and
-quality code generation for standard register-based microprocessors. Code
-generation in this model is divided into the following stages:
+
The LLVM target-independent code generator is designed to support efficient
+ and quality code generation for standard register-based microprocessors.
+ Code generation in this model is divided into the following stages:
-- Instruction Selection - This phase
-determines an efficient way to express the input LLVM code in the target
-instruction set.
-This stage produces the initial code for the program in the target instruction
-set, then makes use of virtual registers in SSA form and physical registers that
-represent any required register assignments due to target constraints or calling
-conventions. This step turns the LLVM code into a DAG of target
-instructions.
-
-- Scheduling and Formation - This
-phase takes the DAG of target instructions produced by the instruction selection
-phase, determines an ordering of the instructions, then emits the instructions
-as MachineInstrs with that ordering. Note
-that we describe this in the instruction selection
-section because it operates on a SelectionDAG.
-
-
-- SSA-based Machine Code Optimizations - This
-optional stage consists of a series of machine-code optimizations that
-operate on the SSA-form produced by the instruction selector. Optimizations
-like modulo-scheduling or peephole optimization work here.
-
-
-- Register Allocation - The
-target code is transformed from an infinite virtual register file in SSA form
-to the concrete register file used by the target. This phase introduces spill
-code and eliminates all virtual register references from the program.
-
-- Prolog/Epilog Code Insertion - Once the
-machine code has been generated for the function and the amount of stack space
-required is known (used for LLVM alloca's and spill slots), the prolog and
-epilog code for the function can be inserted and "abstract stack location
-references" can be eliminated. This stage is responsible for implementing
-optimizations like frame-pointer elimination and stack packing.
-
-- Late Machine Code Optimizations - Optimizations
-that operate on "final" machine code can go here, such as spill code scheduling
-and peephole optimizations.
-
-- Code Emission - The final stage actually
-puts out the code for the current function, either in the target assembler
-format or in machine code.
-
+ - Instruction Selection — This phase
+ determines an efficient way to express the input LLVM code in the target
+ instruction set. This stage produces the initial code for the program in
+ the target instruction set, then makes use of virtual registers in SSA
+ form and physical registers that represent any required register
+ assignments due to target constraints or calling conventions. This step
+ turns the LLVM code into a DAG of target instructions.
+
+ - Scheduling and Formation —
+ This phase takes the DAG of target instructions produced by the
+ instruction selection phase, determines an ordering of the instructions,
+ then emits the instructions
+ as MachineInstrs with that ordering.
+ Note that we describe this in the instruction
+ selection section because it operates on
+ a SelectionDAG.
+
+ - SSA-based Machine Code Optimizations —
+ This optional stage consists of a series of machine-code optimizations
+ that operate on the SSA-form produced by the instruction selector.
+ Optimizations like modulo-scheduling or peephole optimization work
+ here.
+
+ - Register Allocation — The target code
+ is transformed from an infinite virtual register file in SSA form to the
+ concrete register file used by the target. This phase introduces spill
+ code and eliminates all virtual register references from the program.
+
+ - Prolog/Epilog Code Insertion — Once
+ the machine code has been generated for the function and the amount of
+ stack space required is known (used for LLVM alloca's and spill slots),
+ the prolog and epilog code for the function can be inserted and "abstract
+ stack location references" can be eliminated. This stage is responsible
+ for implementing optimizations like frame-pointer elimination and stack
+ packing.
+
+ - Late Machine Code Optimizations —
+ Optimizations that operate on "final" machine code can go here, such as
+ spill code scheduling and peephole optimizations.
+
+ - Code Emission — The final stage
+ actually puts out the code for the current function, either in the target
+ assembler format or in machine code.
-
-The code generator is based on the assumption that the instruction selector will
-use an optimal pattern matching selector to create high-quality sequences of
-native instructions. Alternative code generator designs based on pattern
-expansion and
-aggressive iterative peephole optimization are much slower. This design
-permits efficient compilation (important for JIT environments) and
-aggressive optimization (used when generating code offline) by allowing
-components of varying levels of sophistication to be used for any step of
-compilation.
+
The code generator is based on the assumption that the instruction selector
+ will use an optimal pattern matching selector to create high-quality
+ sequences of native instructions. Alternative code generator designs based
+ on pattern expansion and aggressive iterative peephole optimization are much
+ slower. This design permits efficient compilation (important for JIT
+ environments) and aggressive optimization (used when generating code offline)
+ by allowing components of varying levels of sophistication to be used for any
+ step of compilation.
-
-In addition to these stages, target implementations can insert arbitrary
-target-specific passes into the flow. For example, the X86 target uses a
-special pass to handle the 80x87 floating point stack architecture. Other
-targets with unusual requirements can be supported with custom passes as needed.
-
+
In addition to these stages, target implementations can insert arbitrary
+ target-specific passes into the flow. For example, the X86 target uses a
+ special pass to handle the 80x87 floating point stack architecture. Other
+ targets with unusual requirements can be supported with custom passes as
+ needed.
-
Using TableGen for target description
@@ -268,25 +281,23 @@ targets with unusual requirements can be supported with custom passes as needed.
The target description classes require a detailed description of the target
-architecture. These target descriptions often have a large amount of common
-information (e.g., an add instruction is almost identical to a
-sub instruction).
-In order to allow the maximum amount of commonality to be factored out, the LLVM
-code generator uses the TableGen tool to
-describe big chunks of the target machine, which allows the use of
-domain-specific and target-specific abstractions to reduce the amount of
-repetition.
-
+ architecture. These target descriptions often have a large amount of common
+ information (e.g., an
add instruction is almost identical to a
+
sub instruction). In order to allow the maximum amount of
+ commonality to be factored out, the LLVM code generator uses
+ the
TableGen tool to describe big
+ chunks of the target machine, which allows the use of domain-specific and
+ target-specific abstractions to reduce the amount of repetition.
As LLVM continues to be developed and refined, we plan to move more and more
-of the target description to be in .td form. Doing so gives us a
-number of advantages. The most important is that it makes it easier to port
-LLVM, because it reduces the amount of C++ code that has to be written and the
-surface area of the code generator that needs to be understood before someone
-can get in an get something working. Second, it is also important to us because
-it makes it easier to change things: in particular, if tables and other things
-are all emitted by tblgen, we only need to change one place (tblgen) to update
-all of the targets to a new interface.
+ of the target description to the
.td form. Doing so gives us a
+ number of advantages. The most important is that it makes it easier to port
+ LLVM because it reduces the amount of C++ code that has to be written, and
+ the surface area of the code generator that needs to be understood before
+ someone can get something working. Second, it makes it easier to change
+ things. In particular, if tables and other things are all emitted
+ by
tblgen, we only need a change in one place (
tblgen) to
+ update all of the targets to a new interface.
@@ -298,19 +309,19 @@ all of the targets to a new interface.
-
The LLVM target description classes (which are located in the
-include/llvm/Target directory) provide an abstract description of the
-target machine; independent of any particular client. These classes are
-designed to capture the abstract properties of the target (such as the
-instructions and registers it has), and do not incorporate any particular pieces
-of code generation algorithms.
+
The LLVM target description classes (located in the
+ include/llvm/Target directory) provide an abstract description of
+ the target machine independent of any particular client. These classes are
+ designed to capture the abstract properties of the target (such as the
+ instructions and registers it has), and do not incorporate any particular
+ pieces of code generation algorithms.
-
All of the target description classes (except the TargetData class) are designed to be subclassed by
-the concrete target implementation, and have virtual methods implemented. To
-get to these implementations, the TargetMachine class provides accessors that
-should be implemented by the target.
+
All of the target description classes (except the
+ TargetData class) are designed to be
+ subclassed by the concrete target implementation, and have virtual methods
+ implemented. To get to these implementations, the
+ TargetMachine class provides accessors
+ that should be implemented by the target.
@@ -322,19 +333,18 @@ should be implemented by the target.
The TargetMachine class provides virtual methods that are used to
-access the target-specific implementations of the various target description
-classes via the get*Info methods (getInstrInfo,
-getRegisterInfo, getFrameInfo, etc.). This class is
-designed to be specialized by
-a concrete target implementation (e.g., X86TargetMachine) which
-implements the various virtual methods. The only required target description
-class is the TargetData class, but if the
-code generator components are to be used, the other interfaces should be
-implemented as well.
+ access the target-specific implementations of the various target description
+ classes via the
get*Info methods (
getInstrInfo,
+
getRegisterInfo,
getFrameInfo, etc.). This class is
+ designed to be specialized by a concrete target implementation
+ (e.g.,
X86TargetMachine) which implements the various virtual
+ methods. The only required target description class is
+ the
TargetData class, but if the code
+ generator components are to be used, the other interfaces should be
+ implemented as well.
-
The TargetData class
@@ -343,11 +353,11 @@ implemented as well.
The TargetData class is the only required target description class,
-and it is the only class that is not extensible (you cannot derived a new
-class from it). TargetData specifies information about how the target
-lays out memory for structures, the alignment requirements for various data
-types, the size of pointers in the target, and whether the target is
-little-endian or big-endian.
+ and it is the only class that is not extensible (you cannot derived a new
+ class from it).
TargetData specifies information about how the
+ target lays out memory for structures, the alignment requirements for various
+ data types, the size of pointers in the target, and whether the target is
+ little-endian or big-endian.
@@ -359,52 +369,55 @@ little-endian or big-endian.
The TargetLowering class is used by SelectionDAG based instruction
-selectors primarily to describe how LLVM code should be lowered to SelectionDAG
-operations. Among other things, this class indicates:
-
- an initial register class to use for various ValueTypes
- - which operations are natively supported by the target machine
- - the return type of setcc operations
- - the type to use for shift amounts
+ selectors primarily to describe how LLVM code should be lowered to
+ SelectionDAG operations. Among other things, this class indicates:
+
+
+ - an initial register class to use for various ValueTypes,
+
+ - which operations are natively supported by the target machine,
+
+ - the return type of setcc operations,
+
+ - the type to use for shift amounts, and
+
- various high-level characteristics, like whether it is profitable to turn
division by a constant into a multiplication sequence
-
+
-
The MRegisterInfo class (which will eventually be renamed to
-TargetRegisterInfo) is used to describe the register file of the
-target and any interactions between the registers.
+
The TargetRegisterInfo class is used to describe the register file
+ of the target and any interactions between the registers.
Registers in the code generator are represented in the code generator by
-unsigned numbers. Physical registers (those that actually exist in the target
-description) are unique small numbers, and virtual registers are generally
-large. Note that register #0 is reserved as a flag value.
+ unsigned integers. Physical registers (those that actually exist in the
+ target description) are unique small numbers, and virtual registers are
+ generally large. Note that register #0 is reserved as a flag value.
Each register in the processor description has an associated
-TargetRegisterDesc entry, which provides a textual name for the register
-(used for assembly output and debugging dumps) and a set of aliases (used to
-indicate that one register overlaps with another).
-
+
TargetRegisterDesc entry, which provides a textual name for the
+ register (used for assembly output and debugging dumps) and a set of aliases
+ (used to indicate whether one register overlaps with another).
-
In addition to the per-register description, the MRegisterInfo class
-exposes a set of processor specific register classes (instances of the
-TargetRegisterClass class). Each register class contains sets of
-registers that have the same properties (for example, they are all 32-bit
-integer registers). Each SSA virtual register created by the instruction
-selector has an associated register class. When the register allocator runs, it
-replaces virtual registers with a physical register in the set.
+
In addition to the per-register description, the TargetRegisterInfo
+ class exposes a set of processor specific register classes (instances of the
+ TargetRegisterClass class). Each register class contains sets of
+ registers that have the same properties (for example, they are all 32-bit
+ integer registers). Each SSA virtual register created by the instruction
+ selector has an associated register class. When the register allocator runs,
+ it replaces virtual registers with a physical register in the set.
-
-The target-specific implementations of these classes is auto-generated from a TableGen description of the register file.
-
+
The target-specific implementations of these classes is auto-generated from
+ a TableGen description of the
+ register file.
@@ -414,13 +427,16 @@ href="TableGenFundamentals.html">TableGen description of the register file.
-
The TargetInstrInfo class is used to describe the machine
- instructions supported by the target. It is essentially an array of
- TargetInstrDescriptor objects, each of which describes one
- instruction the target supports. Descriptors define things like the mnemonic
- for the opcode, the number of operands, the list of implicit register uses
- and defs, whether the instruction has certain target-independent properties
- (accesses memory, is commutable, etc), and holds any target-specific flags.
+
+
The TargetInstrInfo class is used to describe the machine
+ instructions supported by the target. It is essentially an array of
+ TargetInstrDescriptor objects, each of which describes one
+ instruction the target supports. Descriptors define things like the mnemonic
+ for the opcode, the number of operands, the list of implicit register uses
+ and defs, whether the instruction has certain target-independent properties
+ (accesses memory, is commutable, etc), and holds any target-specific
+ flags.
+
@@ -429,12 +445,14 @@ href="TableGenFundamentals.html">TableGen description of the register file.
-
The TargetFrameInfo class is used to provide information about the
- stack frame layout of the target. It holds the direction of stack growth,
- the known stack alignment on entry to each function, and the offset to the
- locals area. The offset to the local area is the offset from the stack
- pointer on function entry to the first location where function data (local
- variables, spill locations) can be stored.
+
+
The TargetFrameInfo class is used to provide information about the
+ stack frame layout of the target. It holds the direction of stack growth, the
+ known stack alignment on entry to each function, and the offset to the local
+ area. The offset to the local area is the offset from the stack pointer on
+ function entry to the first location where function data (local variables,
+ spill locations) can be stored.
+
@@ -443,13 +461,13 @@ href="TableGenFundamentals.html">TableGen description of the register file.
Machine code description classes
@@ -466,16 +494,16 @@ href="TableGenFundamentals.html">TableGen description of the register file.
-
-At the high-level, LLVM code is translated to a machine specific representation
-formed out of MachineFunction,
-MachineBasicBlock, and MachineInstr instances
-(defined in include/llvm/CodeGen). This representation is completely target
-agnostic, representing instructions in their most abstract form: an opcode and a
-series of operands. This representation is designed to support both SSA
-representation for machine code, as well as a register allocated, non-SSA form.
-
+
At the high-level, LLVM code is translated to a machine specific
+ representation formed out of
+ MachineFunction,
+ MachineBasicBlock,
+ and MachineInstr instances (defined
+ in include/llvm/CodeGen). This representation is completely target
+ agnostic, representing instructions in their most abstract form: an opcode
+ and a series of operands. This representation is designed to support both an
+ SSA representation for machine code, as well as a register allocated, non-SSA
+ form.
@@ -487,42 +515,43 @@ representation for machine code, as well as a register allocated, non-SSA form.
Target machine instructions are represented as instances of the
-MachineInstr class. This class is an extremely abstract way of
-representing machine instructions. In particular, it only keeps track of
-an opcode number and a set of operands.
-
-
The opcode number is a simple unsigned number that only has meaning to a
-specific backend. All of the instructions for a target should be defined in
-the *InstrInfo.td file for the target. The opcode enum values
-are auto-generated from this description. The MachineInstr class does
-not have any information about how to interpret the instruction (i.e., what the
-semantics of the instruction are): for that you must refer to the
-TargetInstrInfo class.
-
-
The operands of a machine instruction can be of several different types:
-they can be a register reference, constant integer, basic block reference, etc.
-In addition, a machine operand should be marked as a def or a use of the value
-(though only registers are allowed to be defs).
+
MachineInstr class. This class is an extremely abstract way of
+ representing machine instructions. In particular, it only keeps track of an
+ opcode number and a set of operands.
+
+
The opcode number is a simple unsigned integer that only has meaning to a
+ specific backend. All of the instructions for a target should be defined in
+ the *InstrInfo.td file for the target. The opcode enum values are
+ auto-generated from this description. The MachineInstr class does
+ not have any information about how to interpret the instruction (i.e., what
+ the semantics of the instruction are); for that you must refer to the
+ TargetInstrInfo class.
+
+
The operands of a machine instruction can be of several different types: a
+ register reference, a constant integer, a basic block reference, etc. In
+ addition, a machine operand should be marked as a def or a use of the value
+ (though only registers are allowed to be defs).
By convention, the LLVM code generator orders instruction operands so that
-all register definitions come before the register uses, even on architectures
-that are normally printed in other orders. For example, the SPARC add
-instruction: "add %i1, %i2, %i3" adds the "%i1", and "%i2" registers
-and stores the result into the "%i3" register. In the LLVM code generator,
-the operands should be stored as "%i3, %i1, %i2": with the destination
-first.
-
-
Keeping destination (definition) operands at the beginning of the operand
-list has several advantages. In particular, the debugging printer will print
-the instruction like this:
-
+ all register definitions come before the register uses, even on architectures
+ that are normally printed in other orders. For example, the SPARC add
+ instruction: "
add %i1, %i2, %i3" adds the "%i1", and "%i2" registers
+ and stores the result into the "%i3" register. In the LLVM code generator,
+ the operands should be stored as "
%i3, %i1, %i2": with the
+ destination first.
+
+
Keeping destination (definition) operands at the beginning of the operand
+ list has several advantages. In particular, the debugging printer will print
+ the instruction like this:
+
+
- %r3 = add %i1, %i2
+%r3 = add %i1, %i2
+
-
If the first operand is a def, and it is also easier to create instructions whose only def is the first
-operand.
+
Also if the first operand is a def, it is easier to create
+ instructions whose only def is the first operand.
@@ -534,41 +563,46 @@ operand.
Machine instructions are created by using the BuildMI functions,
-located in the include/llvm/CodeGen/MachineInstrBuilder.h file. The
-BuildMI functions make it easy to build arbitrary machine
-instructions. Usage of the BuildMI functions look like this:
-
+ located in the
include/llvm/CodeGen/MachineInstrBuilder.h file. The
+
BuildMI functions make it easy to build arbitrary machine
+ instructions. Usage of the
BuildMI functions look like this:
+
- // Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
- // instruction. The '1' specifies how many operands will be added.
- MachineInstr *MI = BuildMI(X86::MOV32ri, 1, DestReg).addImm(42);
+// Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
+// instruction. The '1' specifies how many operands will be added.
+MachineInstr *MI = BuildMI(X86::MOV32ri, 1, DestReg).addImm(42);
- // Create the same instr, but insert it at the end of a basic block.
- MachineBasicBlock &MBB = ...
- BuildMI(MBB, X86::MOV32ri, 1, DestReg).addImm(42);
+// Create the same instr, but insert it at the end of a basic block.
+MachineBasicBlock &MBB = ...
+BuildMI(MBB, X86::MOV32ri, 1, DestReg).addImm(42);
- // Create the same instr, but insert it before a specified iterator point.
- MachineBasicBlock::iterator MBBI = ...
- BuildMI(MBB, MBBI, X86::MOV32ri, 1, DestReg).addImm(42);
+// Create the same instr, but insert it before a specified iterator point.
+MachineBasicBlock::iterator MBBI = ...
+BuildMI(MBB, MBBI, X86::MOV32ri, 1, DestReg).addImm(42);
- // Create a 'cmp Reg, 0' instruction, no destination reg.
- MI = BuildMI(X86::CMP32ri, 2).addReg(Reg).addImm(0);
- // Create an 'sahf' instruction which takes no operands and stores nothing.
- MI = BuildMI(X86::SAHF, 0);
+// Create a 'cmp Reg, 0' instruction, no destination reg.
+MI = BuildMI(X86::CMP32ri, 2).addReg(Reg).addImm(0);
+// Create an 'sahf' instruction which takes no operands and stores nothing.
+MI = BuildMI(X86::SAHF, 0);
- // Create a self looping branch instruction.
- BuildMI(MBB, X86::JNE, 1).addMBB(&MBB);
+// Create a self looping branch instruction.
+BuildMI(MBB, X86::JNE, 1).addMBB(&MBB);
+
+
+
The key thing to remember with the BuildMI functions is that you
+ have to specify the number of operands that the machine instruction will
+ take. This allows for efficient memory allocation. You also need to specify
+ if operands default to be uses of values, not definitions. If you need to
+ add a definition operand (other than the optional destination register), you
+ must explicitly mark it as such:
-
-The key thing to remember with the BuildMI functions is that you have
-to specify the number of operands that the machine instruction will take. This
-allows for efficient memory allocation. You also need to specify if operands
-default to be uses of values, not definitions. If you need to add a definition
-operand (other than the optional destination register), you must explicitly
-mark it as such.
-
+
+
+MI.addReg(Reg, RegState::Define);
+
+
@@ -580,78 +614,85 @@ mark it as such.
One important issue that the code generator needs to be aware of is the
-presence of fixed registers. In particular, there are often places in the
-instruction stream where the register allocator must arrange for a
-particular value to be in a particular register. This can occur due to
-limitations of the instruction set (e.g., the X86 can only do a 32-bit divide
-with the EAX/EDX registers), or external factors like calling
-conventions. In any case, the instruction selector should emit code that
-copies a virtual register into or out of a physical register when needed.
+ presence of fixed registers. In particular, there are often places in the
+ instruction stream where the register allocator
must arrange for a
+ particular value to be in a particular register. This can occur due to
+ limitations of the instruction set (e.g., the X86 can only do a 32-bit divide
+ with the
EAX/
EDX registers), or external factors like
+ calling conventions. In any case, the instruction selector should emit code
+ that copies a virtual register into or out of a physical register when
+ needed.
For example, consider this simple LLVM example:
+
- int %test(int %X, int %Y) {
- %Z = div int %X, %Y
- ret int %Z
- }
+define i32 @test(i32 %X, i32 %Y) {
+ %Z = udiv i32 %X, %Y
+ ret i32 %Z
+}
+
-
The X86 instruction selector produces this machine code for the div
-and ret (use
-"llc X.bc -march=x86 -print-machineinstrs" to get this):
+
The X86 instruction selector produces this machine code for the div
+ and ret (use "llc X.bc -march=x86 -print-machineinstrs" to
+ get this):
+
- ;; Start of div
- %EAX = mov %reg1024 ;; Copy X (in reg1024) into EAX
- %reg1027 = sar %reg1024, 31
- %EDX = mov %reg1027 ;; Sign extend X into EDX
- idiv %reg1025 ;; Divide by Y (in reg1025)
- %reg1026 = mov %EAX ;; Read the result (Z) out of EAX
-
- ;; Start of ret
- %EAX = mov %reg1026 ;; 32-bit return value goes in EAX
- ret
+;; Start of div
+%EAX = mov %reg1024 ;; Copy X (in reg1024) into EAX
+%reg1027 = sar %reg1024, 31
+%EDX = mov %reg1027 ;; Sign extend X into EDX
+idiv %reg1025 ;; Divide by Y (in reg1025)
+%reg1026 = mov %EAX ;; Read the result (Z) out of EAX
+
+;; Start of ret
+%EAX = mov %reg1026 ;; 32-bit return value goes in EAX
+ret
+
-
By the end of code generation, the register allocator has coalesced
-the registers and deleted the resultant identity moves, producing the
-following code:
+
By the end of code generation, the register allocator has coalesced the
+ registers and deleted the resultant identity moves producing the following
+ code:
+
- ;; X is in EAX, Y is in ECX
- mov %EAX, %EDX
- sar %EDX, 31
- idiv %ECX
- ret
+;; X is in EAX, Y is in ECX
+mov %EAX, %EDX
+sar %EDX, 31
+idiv %ECX
+ret
+
-
This approach is extremely general (if it can handle the X86 architecture,
-it can handle anything!) and allows all of the target specific
-knowledge about the instruction stream to be isolated in the instruction
-selector. Note that physical registers should have a short lifetime for good
-code generation, and all physical registers are assumed dead on entry and
-exit of basic blocks (before register allocation). Thus if you need a value
-to be live across basic block boundaries, it must live in a virtual
-register.
+
This approach is extremely general (if it can handle the X86 architecture, it
+ can handle anything!) and allows all of the target specific knowledge about
+ the instruction stream to be isolated in the instruction selector. Note that
+ physical registers should have a short lifetime for good code generation, and
+ all physical registers are assumed dead on entry to and exit from basic
+ blocks (before register allocation). Thus, if you need a value to be live
+ across basic block boundaries, it must live in a virtual
+ register.
-
MachineInstr's are initially selected in SSA-form, and
-are maintained in SSA-form until register allocation happens. For the most
-part, this is trivially simple since LLVM is already in SSA form: LLVM PHI nodes
-become machine code PHI nodes, and virtual registers are only allowed to have a
-single definition.
+
MachineInstr's are initially selected in SSA-form, and are
+ maintained in SSA-form until register allocation happens. For the most part,
+ this is trivially simple since LLVM is already in SSA form; LLVM PHI nodes
+ become machine code PHI nodes, and virtual registers are only allowed to have
+ a single definition.
-
After register allocation, machine code is no longer in SSA-form, as there
-are no virtual registers left in the code.
+
After register allocation, machine code is no longer in SSA-form because
+ there are no virtual registers left in the code.
@@ -663,12 +704,12 @@ are no virtual registers left in the code.
The MachineBasicBlock class contains a list of machine instructions
-(MachineInstr instances). It roughly corresponds to
-the LLVM code input to the instruction selector, but there can be a one-to-many
-mapping (i.e. one LLVM basic block can map to multiple machine basic blocks).
-The MachineBasicBlock class has a "getBasicBlock" method, which returns
-the LLVM basic block that it comes from.
-
+ (
MachineInstr instances). It roughly
+ corresponds to the LLVM code input to the instruction selector, but there can
+ be a one-to-many mapping (i.e. one LLVM basic block can map to multiple
+ machine basic blocks). The
MachineBasicBlock class has a
+ "
getBasicBlock" method, which returns the LLVM basic block that it
+ comes from.
@@ -680,18 +721,16 @@ the LLVM basic block that it comes from.
The MachineFunction class contains a list of machine basic blocks
-(MachineBasicBlock instances). It corresponds
-one-to-one with the LLVM function input to the instruction selector. In
-addition to a list of basic blocks, the MachineFunction contains a
-the MachineConstantPool, MachineFrameInfo, MachineFunctionInfo,
-SSARegMap, and a set of live in and live out registers for the function. See
-MachineFunction.h for more information.
-
+ (
MachineBasicBlock instances). It
+ corresponds one-to-one with the LLVM function input to the instruction
+ selector. In addition to a list of basic blocks,
+ the
MachineFunction contains a a
MachineConstantPool,
+ a
MachineFrameInfo, a
MachineFunctionInfo, and a
+
MachineRegisterInfo. See
+
include/llvm/CodeGen/MachineFunction.h for more information.
-
-
-
-Instruction Selection is the process of translating LLVM code presented to the
-code generator into target-specific machine instructions. There are several
-well-known ways to do this in the literature. In LLVM there are two main forms:
-the SelectionDAG based instruction selector framework and an old-style 'simple'
-instruction selector (which effectively peephole selects each LLVM instruction
-into a series of machine instructions). We recommend that all targets use the
-SelectionDAG infrastructure.
-
-
Portions of the DAG instruction selector are generated from the target
-description files (*.td) files. Eventually, we aim for the entire
-instruction selector to be generated from these .td files.
+
Instruction Selection is the process of translating LLVM code presented to
+ the code generator into target-specific machine instructions. There are
+ several well-known ways to do this in the literature. LLVM uses a
+ SelectionDAG based instruction selector.
+
+
Portions of the DAG instruction selector are generated from the target
+ description (*.td) files. Our goal is for the entire instruction
+ selector to be generated from these .td files, though currently
+ there are still things that require custom C++ code.
+
@@ -734,65 +771,59 @@ instruction selector to be generated from these
.td files.
-
-The SelectionDAG provides an abstraction for code representation in a way that
-is amenable to instruction selection using automatic techniques
-(e.g. dynamic-programming based optimal pattern matching selectors), It is also
-well suited to other phases of code generation; in particular,
-instruction scheduling (SelectionDAG's are very close to scheduling DAGs
-post-selection). Additionally, the SelectionDAG provides a host representation
-where a large variety of very-low-level (but target-independent)
-optimizations may be
-performed: ones which require extensive information about the instructions
-efficiently supported by the target.
-
-
-
-The SelectionDAG is a Directed-Acyclic-Graph whose nodes are instances of the
-SDNode class. The primary payload of the SDNode is its
-operation code (Opcode) that indicates what operation the node performs and
-the operands to the operation.
-The various operation node types are described at the top of the
-include/llvm/CodeGen/SelectionDAGNodes.h file.
-
-
Although most operations define a single value, each node in the graph may
-define multiple values. For example, a combined div/rem operation will define
-both the dividend and the remainder. Many other situations require multiple
-values as well. Each node also has some number of operands, which are edges
-to the node defining the used value. Because nodes may define multiple values,
-edges are represented by instances of the SDOperand class, which is
-a <SDNode, unsigned> pair, indicating the node and result
-value being used, respectively. Each value produced by an SDNode has an
-associated MVT::ValueType, indicating what type the value is.
-
-
-
-SelectionDAGs contain two different kinds of values: those that represent data
-flow and those that represent control flow dependencies. Data values are simple
-edges with an integer or floating point value type. Control edges are
-represented as "chain" edges which are of type MVT::Other. These edges provide
-an ordering between nodes that have side effects (such as
-loads/stores/calls/return/etc). All nodes that have side effects should take a
-token chain as input and produce a new one as output. By convention, token
-chain inputs are always operand #0, and chain results are always the last
-value produced by an operation.
-
-
-A SelectionDAG has designated "Entry" and "Root" nodes. The Entry node is
-always a marker node with an Opcode of ISD::EntryToken. The Root node is the
-final side-effecting node in the token chain. For example, in a single basic
-block function, this would be the return node.
-
-
-
-One important concept for SelectionDAGs is the notion of a "legal" vs. "illegal"
-DAG. A legal DAG for a target is one that only uses supported operations and
-supported types. On a 32-bit PowerPC, for example, a DAG with any values of i1,
-i8, i16,
-or i64 type would be illegal, as would a DAG that uses a SREM or UREM operation.
-The legalize
-phase is responsible for turning an illegal DAG into a legal DAG.
-
+
The SelectionDAG provides an abstraction for code representation in a way
+ that is amenable to instruction selection using automatic techniques
+ (e.g. dynamic-programming based optimal pattern matching selectors). It is
+ also well-suited to other phases of code generation; in particular,
+ instruction scheduling (SelectionDAG's are very close to scheduling DAGs
+ post-selection). Additionally, the SelectionDAG provides a host
+ representation where a large variety of very-low-level (but
+ target-independent) optimizations may be
+ performed; ones which require extensive information about the instructions
+ efficiently supported by the target.
+
+
The SelectionDAG is a Directed-Acyclic-Graph whose nodes are instances of the
+ SDNode class. The primary payload of the SDNode is its
+ operation code (Opcode) that indicates what operation the node performs and
+ the operands to the operation. The various operation node types are
+ described at the top of the include/llvm/CodeGen/SelectionDAGNodes.h
+ file.
+
+
Although most operations define a single value, each node in the graph may
+ define multiple values. For example, a combined div/rem operation will
+ define both the dividend and the remainder. Many other situations require
+ multiple values as well. Each node also has some number of operands, which
+ are edges to the node defining the used value. Because nodes may define
+ multiple values, edges are represented by instances of the SDValue
+ class, which is a <SDNode, unsigned> pair, indicating the node
+ and result value being used, respectively. Each value produced by
+ an SDNode has an associated MVT (Machine Value Type)
+ indicating what the type of the value is.
+
+
SelectionDAGs contain two different kinds of values: those that represent
+ data flow and those that represent control flow dependencies. Data values
+ are simple edges with an integer or floating point value type. Control edges
+ are represented as "chain" edges which are of type MVT::Other.
+ These edges provide an ordering between nodes that have side effects (such as
+ loads, stores, calls, returns, etc). All nodes that have side effects should
+ take a token chain as input and produce a new one as output. By convention,
+ token chain inputs are always operand #0, and chain results are always the
+ last value produced by an operation.
+
+
A SelectionDAG has designated "Entry" and "Root" nodes. The Entry node is
+ always a marker node with an Opcode of ISD::EntryToken. The Root
+ node is the final side-effecting node in the token chain. For example, in a
+ single basic block function it would be the return node.
+
+
One important concept for SelectionDAGs is the notion of a "legal" vs.
+ "illegal" DAG. A legal DAG for a target is one that only uses supported
+ operations and supported types. On a 32-bit PowerPC, for example, a DAG with
+ a value of type i1, i8, i16, or i64 would be illegal, as would a DAG that
+ uses a SREM or UREM operation. The
+ legalize types and
+ legalize operations phases are
+ responsible for turning an illegal DAG into a legal DAG.
+
@@ -802,48 +833,78 @@ phase is responsible for turning an illegal DAG into a legal DAG.
-
-SelectionDAG-based instruction selection consists of the following steps:
-
+
SelectionDAG-based instruction selection consists of the following steps:
-- Build initial DAG - This stage performs
- a simple translation from the input LLVM code to an illegal SelectionDAG.
-
-- Optimize SelectionDAG - This stage
- performs simple optimizations on the SelectionDAG to simplify it and
- recognize meta instructions (like rotates and div/rem pairs) for
- targets that support these meta operations. This makes the resultant code
- more efficient and the 'select instructions from DAG' phase (below) simpler.
-
-- Legalize SelectionDAG - This stage
- converts the illegal SelectionDAG to a legal SelectionDAG, by eliminating
- unsupported operations and data types.
-- Optimize SelectionDAG (#2) - This
- second run of the SelectionDAG optimized the newly legalized DAG, to
- eliminate inefficiencies introduced by legalization.
-- Select instructions from DAG - Finally,
- the target instruction selector matches the DAG operations to target
- instructions. This process translates the target-independent input DAG into
- another DAG of target instructions.
-- SelectionDAG Scheduling and Formation
- - The last phase assigns a linear order to the instructions in the
- target-instruction DAG and emits them into the MachineFunction being
- compiled. This step uses traditional prepass scheduling techniques.
+ - Build initial DAG — This stage
+ performs a simple translation from the input LLVM code to an illegal
+ SelectionDAG.
+
+ - Optimize SelectionDAG — This
+ stage performs simple optimizations on the SelectionDAG to simplify it,
+ and recognize meta instructions (like rotates
+ and div/rem pairs) for targets that support these meta
+ operations. This makes the resultant code more efficient and
+ the select instructions from DAG phase
+ (below) simpler.
+
+ - Legalize SelectionDAG Types
+ — This stage transforms SelectionDAG nodes to eliminate any types
+ that are unsupported on the target.
+
+ - Optimize SelectionDAG — The
+ SelectionDAG optimizer is run to clean up redundancies exposed by type
+ legalization.
+
+ - Legalize SelectionDAG Types —
+ This stage transforms SelectionDAG nodes to eliminate any types that are
+ unsupported on the target.
+
+ - Optimize SelectionDAG — The
+ SelectionDAG optimizer is run to eliminate inefficiencies introduced by
+ operation legalization.
+
+ - Select instructions from DAG —
+ Finally, the target instruction selector matches the DAG operations to
+ target instructions. This process translates the target-independent input
+ DAG into another DAG of target instructions.
+
+ - SelectionDAG Scheduling and Formation
+ — The last phase assigns a linear order to the instructions in the
+ target-instruction DAG and emits them into the MachineFunction being
+ compiled. This step uses traditional prepass scheduling techniques.
After all of these steps are complete, the SelectionDAG is destroyed and the
-rest of the code generation passes are run.
+ rest of the code generation passes are run.
+
+
One great way to visualize what is going on here is to take advantage of a
+ few LLC command line options. The following options pop up a window
+ displaying the SelectionDAG at specific times (if you only get errors printed
+ to the console while using this, you probably
+ need to configure your system
+ to add support for it).
+
+
+ - -view-dag-combine1-dags displays the DAG after being built,
+ before the first optimization pass.
+
+ - -view-legalize-dags displays the DAG before Legalization.
+
+ - -view-dag-combine2-dags displays the DAG before the second
+ optimization pass.
+
+ - -view-isel-dags displays the DAG before the Select phase.
+
+ - -view-sched-dags displays the DAG before Scheduling.
+
+
+
The -view-sunit-dags displays the Scheduler's dependency graph.
+ This graph is based on the final SelectionDAG, with nodes that must be
+ scheduled together bundled into a single scheduling-unit node, and with
+ immediate operands and other nodes that aren't relevant for scheduling
+ omitted.
-
One great way to visualize what is going on here is to take advantage of a
-few LLC command line options. In particular, the -view-isel-dags
-option pops up a window with the SelectionDAG input to the Select phase for all
-of the code compiled (if you only get errors printed to the console while using
-this, you probably need to configure
-your system to add support for it). The -view-sched-dags option
-views the SelectionDAG output from the Select phase and input to the Scheduler
-phase.
-
@@ -853,17 +914,49 @@ phase.
-
-The initial SelectionDAG is naively peephole expanded from the LLVM input by
-the SelectionDAGLowering class in the SelectionDAGISel.cpp file. The
-intent of this pass is to expose as much low-level, target-specific details
-to the SelectionDAG as possible. This pass is mostly hard-coded (e.g. an LLVM
-add turns into an SDNode add while a geteelementptr is expanded into the obvious
-arithmetic). This pass requires target-specific hooks to lower calls and
-returns, varargs, etc. For these features, the TargetLowering interface is
-used.
-
+
The initial SelectionDAG is naïvely peephole expanded from the LLVM
+ input by the SelectionDAGLowering class in the
+ lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp file. The intent of
+ this pass is to expose as much low-level, target-specific details to the
+ SelectionDAG as possible. This pass is mostly hard-coded (e.g. an
+ LLVM add turns into an SDNode add while a
+ getelementptr is expanded into the obvious arithmetic). This pass
+ requires target-specific hooks to lower calls, returns, varargs, etc. For
+ these features, the TargetLowering
+ interface is used.
+
+
+
+
+
+
+
+
+
The Legalize phase is in charge of converting a DAG to only use the types
+ that are natively supported by the target.
+
+
There are two main ways of converting values of unsupported scalar types to
+ values of supported types: converting small types to larger types
+ ("promoting"), and breaking up large integer types into smaller ones
+ ("expanding"). For example, a target might require that all f32 values are
+ promoted to f64 and that all i1/i8/i16 values are promoted to i32. The same
+ target might require that all i64 values be expanded into pairs of i32
+ values. These changes can insert sign and zero extensions as needed to make
+ sure that the final code has the same behavior as the input.
+
+
There are two main ways of converting values of unsupported vector types to
+ value of supported types: splitting vector types, multiple times if
+ necessary, until a legal type is found, and extending vector types by adding
+ elements to the end to round them out to legal types ("widening"). If a
+ vector gets split all the way down to single-element parts with no supported
+ vector type being found, the elements are converted to scalars
+ ("scalarizing").
+
+
A target implementation tells the legalizer which types are supported (and
+ which register class to use for them) by calling the
+ addRegisterClass method in its TargetLowering constructor.
@@ -874,50 +967,28 @@ used.
-
The Legalize phase is in charge of converting a DAG to only use the types and
-operations that are natively supported by the target. This involves two major
-tasks:
+
The Legalize phase is in charge of converting a DAG to only use the
+ operations that are natively supported by the target.
-
-Convert values of unsupported types to values of supported types.
- There are two main ways of doing this: converting small types to
- larger types ("promoting"), and breaking up large integer types
- into smaller ones ("expanding"). For example, a target might require
- that all f32 values are promoted to f64 and that all i1/i8/i16 values
- are promoted to i32. The same target might require that all i64 values
- be expanded into i32 values. These changes can insert sign and zero
- extensions as
- needed to make sure that the final code has the same behavior as the
- input.
- A target implementation tells the legalizer which types are supported
- (and which register class to use for them) by calling the
- "addRegisterClass" method in its TargetLowering constructor.
-Eliminate operations that are not supported by the target.
- Targets often have weird constraints, such as not supporting every
- operation on every supported datatype (e.g. X86 does not support byte
- conditional moves and PowerPC does not support sign-extending loads from
- a 16-bit memory location). Legalize takes care by open-coding
- another sequence of operations to emulate the operation ("expansion"), by
- promoting to a larger type that supports the operation
- (promotion), or using a target-specific hook to implement the
- legalization (custom).
- A target implementation tells the legalizer which operations are not
- supported (and which of the above three actions to take) by calling the
- "setOperationAction" method in its TargetLowering constructor.
-
+
Targets often have weird constraints, such as not supporting every operation
+ on every supported datatype (e.g. X86 does not support byte conditional moves
+ and PowerPC does not support sign-extending loads from a 16-bit memory
+ location). Legalize takes care of this by open-coding another sequence of
+ operations to emulate the operation ("expansion"), by promoting one type to a
+ larger type that supports the operation ("promotion"), or by using a
+ target-specific hook to implement the legalization ("custom").
+
+
A target implementation tells the legalizer which operations are not
+ supported (and which of the above three actions to take) by calling the
+ setOperationAction method in its TargetLowering
+ constructor.
-
-Prior to the existance of the Legalize pass, we required that every
-target selector supported and handled every
-operator and type even if they are not natively supported. The introduction of
-the Legalize phase allows all of the
-cannonicalization patterns to be shared across targets, and makes it very
-easy to optimize the cannonicalized code because it is still in the form of
-a DAG.
-
+
Prior to the existence of the Legalize passes, we required that every target
+ selector supported and handled every
+ operator and type even if they are not natively supported. The introduction
+ of the Legalize phases allows all of the canonicalization patterns to be
+ shared across targets, and makes it very easy to optimize the canonicalized
+ code because it is still in the form of a DAG.
@@ -929,37 +1000,30 @@ a DAG.
-
-The SelectionDAG optimization phase is run twice for code generation: once
-immediately after the DAG is built and once after legalization. The first run
-of the pass allows the initial code to be cleaned up (e.g. performing
-optimizations that depend on knowing that the operators have restricted type
-inputs). The second run of the pass cleans up the messy code generated by the
-Legalize pass, which allows Legalize to be very simple (it can focus on making
-code legal instead of focusing on generating good and legal code).
-
-
-
-One important class of optimizations performed is optimizing inserted sign and
-zero extension instructions. We currently use ad-hoc techniques, but could move
-to more rigorous techniques in the future. Here are some good
-papers on the subject:
+
The SelectionDAG optimization phase is run multiple times for code
+ generation, immediately after the DAG is built and once after each
+ legalization. The first run of the pass allows the initial code to be
+ cleaned up (e.g. performing optimizations that depend on knowing that the
+ operators have restricted type inputs). Subsequent runs of the pass clean up
+ the messy code generated by the Legalize passes, which allows Legalize to be
+ very simple (it can focus on making code legal instead of focusing on
+ generating good and legal code).
-
-"Widening
-integer arithmetic"
-Kevin Redwine and Norman Ramsey
-International Conference on Compiler Construction (CC) 2004
-
+
One important class of optimizations performed is optimizing inserted sign
+ and zero extension instructions. We currently use ad-hoc techniques, but
+ could move to more rigorous techniques in the future. Here are some good
+ papers on the subject:
+
"Widening
+ integer arithmetic"
+ Kevin Redwine and Norman Ramsey
+ International Conference on Compiler Construction (CC) 2004
-
- "Effective
- sign extension elimination"
- Motohiro Kawahito, Hideaki Komatsu, and Toshio Nakatani
- Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design
- and Implementation.
-
+
"Effective
+ sign extension elimination"
+ Motohiro Kawahito, Hideaki Komatsu, and Toshio Nakatani
+ Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design
+ and Implementation.
@@ -971,40 +1035,44 @@ International Conference on Compiler Construction (CC) 2004
The Select phase is the bulk of the target-specific code for instruction
-selection. This phase takes a legal SelectionDAG as input,
-pattern matches the instructions supported by the target to this DAG, and
-produces a new DAG of target code. For example, consider the following LLVM
-fragment:
+ selection. This phase takes a legal SelectionDAG as input, pattern matches
+ the instructions supported by the target to this DAG, and produces a new DAG
+ of target code. For example, consider the following LLVM fragment:
+
- %t1 = add float %W, %X
- %t2 = mul float %t1, %Y
- %t3 = add float %t2, %Z
+%t1 = add float %W, %X
+%t2 = mul float %t1, %Y
+%t3 = add float %t2, %Z
+
-
This LLVM code corresponds to a SelectionDAG that looks basically like this:
-
+
This LLVM code corresponds to a SelectionDAG that looks basically like
+ this:
+
- (fadd:f32 (fmul:f32 (fadd:f32 W, X), Y), Z)
+(fadd:f32 (fmul:f32 (fadd:f32 W, X), Y), Z)
+
-
If a target supports floating point multiply-and-add (FMA) operations, one
-of the adds can be merged with the multiply. On the PowerPC, for example, the
-output of the instruction selector might look like this DAG:
+
If a target supports floating point multiply-and-add (FMA) operations, one of
+ the adds can be merged with the multiply. On the PowerPC, for example, the
+ output of the instruction selector might look like this DAG:
+
- (FMADDS (FADDS W, X), Y, Z)
+(FMADDS (FADDS W, X), Y, Z)
+
-
-The FMADDS instruction is a ternary instruction that multiplies its first two
-operands and adds the third (as single-precision floating-point numbers). The
-FADDS instruction is a simple binary single-precision add instruction. To
-perform this pattern match, the PowerPC backend includes the following
-instruction definitions:
-
+
The FMADDS instruction is a ternary instruction that multiplies its
+first two operands and adds the third (as single-precision floating-point
+numbers). The FADDS instruction is a simple binary single-precision
+add instruction. To perform this pattern match, the PowerPC backend includes
+the following instruction definitions:
+
def FMADDS : AForm_1<59, 29,
(ops F4RC:$FRT, F4RC:$FRA, F4RC:$FRC, F4RC:$FRB),
@@ -1016,89 +1084,107 @@ def FADDS : AForm_2<59, 21,
"fadds $FRT, $FRA, $FRB",
[(set F4RC:$FRT, (fadd F4RC:$FRA, F4RC:$FRB))]>;
+
The portion of the instruction definition in bold indicates the pattern used
-to match the instruction. The DAG operators (like fmul/fadd)
-are defined in the lib/Target/TargetSelectionDAG.td file.
-"F4RC" is the register class of the input and result values.
+ to match the instruction. The DAG operators
+ (like fmul/fadd) are defined in
+ the lib/Target/TargetSelectionDAG.td file. "F4RC" is the
+ register class of the input and result values.
-
The TableGen DAG instruction selector generator reads the instruction
-patterns in the .td and automatically builds parts of the pattern matching code
-for your target. It has the following strengths:
+
The TableGen DAG instruction selector generator reads the instruction
+ patterns in the .td file and automatically builds parts of the
+ pattern matching code for your target. It has the following strengths:
-
-While it has many strengths, the system currently has some limitations,
-primarily because it is a work in progress and is not yet finished:
-
+
While it has many strengths, the system currently has some limitations,
+ primarily because it is a work in progress and is not yet finished:
-- Overall, there is no way to define or match SelectionDAG nodes that define
- multiple values (e.g. ADD_PARTS, LOAD, CALL, etc). This is the biggest
- reason that you currently still have to write custom C++ code for
- your instruction selector.
-- There is no great way to support match complex addressing modes yet. In the
- future, we will extend pattern fragments to allow them to define multiple
- values (e.g. the four operands of the X86 addressing
- mode). In addition, we'll extend fragments so that a fragment can match
- multiple different patterns.
-- We don't automatically infer flags like isStore/isLoad yet.
-- We don't automatically generate the set of supported registers and
- operations for the Legalizer yet.
-- We don't have a way of tying in custom legalized nodes yet.
+ - Overall, there is no way to define or match SelectionDAG nodes that define
+ multiple values (e.g. SMUL_LOHI, LOAD, CALL,
+ etc). This is the biggest reason that you currently still have
+ to write custom C++ code for your instruction selector.
+
+ - There is no great way to support matching complex addressing modes yet.
+ In the future, we will extend pattern fragments to allow them to define
+ multiple values (e.g. the four operands of the X86
+ addressing mode, which are currently matched with custom C++ code).
+ In addition, we'll extend fragments so that a fragment can match multiple
+ different patterns.
+
+ - We don't automatically infer flags like isStore/isLoad yet.
+
+ - We don't automatically generate the set of supported registers and
+ operations for the Legalizer
+ yet.
+
+ - We don't have a way of tying in custom legalized nodes yet.
Despite these limitations, the instruction selector generator is still quite
-useful for most of the binary and logical operations in typical instruction
-sets. If you run into any problems or can't figure out how to do something,
-please let Chris know!
+ useful for most of the binary and logical operations in typical instruction
+ sets. If you run into any problems or can't figure out how to do something,
+ please let Chris know!
@@ -1110,16 +1196,16 @@ please let Chris know!
The scheduling phase takes the DAG of target instructions from the selection
-phase and assigns an order. The scheduler can pick an order depending on
-various constraints of the machines (i.e. order for minimal register pressure or
-try to cover instruction latencies). Once an order is established, the DAG is
-converted to a list of MachineInstrs and the
-Selection DAG is destroyed.
-
+ phase and assigns an order. The scheduler can pick an order depending on
+ various constraints of the machines (i.e. order for minimal register pressure
+ or try to cover instruction latencies). Once an order is established, the
+ DAG is converted to a list
+ of
MachineInstrs and the SelectionDAG is
+ destroyed.
-
Note that this phase is logically seperate from the instruction selection
-phase, but is tied to it closely in the code because it operates on
-SelectionDAGs.
+
Note that this phase is logically separate from the instruction selection
+ phase, but is tied to it closely in the code because it operates on
+ SelectionDAGs.
@@ -1131,9 +1217,9 @@ SelectionDAGs.
-- Optional function-at-a-time selection.
-- Auto-generate entire selector from .td file.
-
+ - Optional function-at-a-time selection.
+
+ - Auto-generate entire selector from .td file.
@@ -1143,11 +1229,401 @@ SelectionDAGs.
SSA-based Machine Code Optimizations
+
+
In LLVM, physical registers are denoted by integer numbers that normally
+ range from 1 to 1023. To see how this numbering is defined for a particular
+ architecture, you can read the GenRegisterNames.inc file for that
+ architecture. For instance, by
+ inspecting lib/Target/X86/X86GenRegisterNames.inc we see that the
+ 32-bit register EAX is denoted by 15, and the MMX register
+ MM0 is mapped to 48.
+
+
Some architectures contain registers that share the same physical location. A
+ notable example is the X86 platform. For instance, in the X86 architecture,
+ the registers EAX, AX and AL share the first eight
+ bits. These physical registers are marked as aliased in LLVM. Given a
+ particular architecture, you can check which registers are aliased by
+ inspecting its RegisterInfo.td file. Moreover, the method
+ TargetRegisterInfo::getAliasSet(p_reg) returns an array containing
+ all the physical registers aliased to the register p_reg.
+
+
Physical registers, in LLVM, are grouped in Register Classes.
+ Elements in the same register class are functionally equivalent, and can be
+ interchangeably used. Each virtual register can only be mapped to physical
+ registers of a particular class. For instance, in the X86 architecture, some
+ virtuals can only be allocated to 8 bit registers. A register class is
+ described by TargetRegisterClass objects. To discover if a virtual
+ register is compatible with a given physical, this code can be used:
+
+
+
+bool RegMapping_Fer::compatible_class(MachineFunction &mf,
+ unsigned v_reg,
+ unsigned p_reg) {
+ assert(TargetRegisterInfo::isPhysicalRegister(p_reg) &&
+ "Target register must be physical");
+ const TargetRegisterClass *trc = mf.getRegInfo().getRegClass(v_reg);
+ return trc->contains(p_reg);
+}
+
+
+
+
Sometimes, mostly for debugging purposes, it is useful to change the number
+ of physical registers available in the target architecture. This must be done
+ statically, inside the TargetRegsterInfo.td file. Just grep
+ for RegisterClass, the last parameter of which is a list of
+ registers. Just commenting some out is one simple way to avoid them being
+ used. A more polite way is to explicitly exclude some registers from
+ the allocation order. See the definition of the GR8 register
+ class in lib/Target/X86/X86RegisterInfo.td for an example of this.
+
+
+
Virtual registers are also denoted by integer numbers. Contrary to physical
+ registers, different virtual registers never share the same number. The
+ smallest virtual register is normally assigned the number 1024. This may
+ change, so, in order to know which is the first virtual register, you should
+ access TargetRegisterInfo::FirstVirtualRegister. Any register whose
+ number is greater than or equal
+ to TargetRegisterInfo::FirstVirtualRegister is considered a virtual
+ register. Whereas physical registers are statically defined in
+ a TargetRegisterInfo.td file and cannot be created by the
+ application developer, that is not the case with virtual registers. In order
+ to create new virtual registers, use the
+ method MachineRegisterInfo::createVirtualRegister(). This method
+ will return a virtual register with the highest code.
+
+
Before register allocation, the operands of an instruction are mostly virtual
+ registers, although physical registers may also be used. In order to check if
+ a given machine operand is a register, use the boolean
+ function MachineOperand::isRegister(). To obtain the integer code of
+ a register, use MachineOperand::getReg(). An instruction may define
+ or use a register. For instance, ADD reg:1026 := reg:1025 reg:1024
+ defines the registers 1024, and uses registers 1025 and 1026. Given a
+ register operand, the method MachineOperand::isUse() informs if that
+ register is being used by the instruction. The
+ method MachineOperand::isDef() informs if that registers is being
+ defined.
+
+
We will call physical registers present in the LLVM bitcode before register
+ allocation pre-colored registers. Pre-colored registers are used in
+ many different situations, for instance, to pass parameters of functions
+ calls, and to store results of particular instructions. There are two types
+ of pre-colored registers: the ones implicitly defined, and
+ those explicitly defined. Explicitly defined registers are normal
+ operands, and can be accessed
+ with MachineInstr::getOperand(int)::getReg(). In order to check
+ which registers are implicitly defined by an instruction, use
+ the TargetInstrInfo::get(opcode)::ImplicitDefs,
+ where opcode is the opcode of the target instruction. One important
+ difference between explicit and implicit physical registers is that the
+ latter are defined statically for each instruction, whereas the former may
+ vary depending on the program being compiled. For example, an instruction
+ that represents a function call will always implicitly define or use the same
+ set of physical registers. To read the registers implicitly used by an
+ instruction,
+ use TargetInstrInfo::get(opcode)::ImplicitUses. Pre-colored
+ registers impose constraints on any register allocation algorithm. The
+ register allocator must make sure that none of them is been overwritten by
+ the values of virtual registers while still alive.
+
+
+ src="http://jigsaw.w3.org/css-validator/images/vcss-blue" alt="Valid CSS">