diff options
Diffstat (limited to 'docs/CodeGenerator.html')
| -rw-r--r-- | docs/CodeGenerator.html | 2169 |
1 files changed, 2169 insertions, 0 deletions
diff --git a/docs/CodeGenerator.html b/docs/CodeGenerator.html new file mode 100644 index 0000000000..fbdc294e4a --- /dev/null +++ b/docs/CodeGenerator.html @@ -0,0 +1,2169 @@ +<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" + "http://www.w3.org/TR/html4/strict.dtd"> +<html> +<head> + <meta http-equiv="content-type" content="text/html; charset=utf-8"> + <title>The LLVM Target-Independent Code Generator</title> + <link rel="stylesheet" href="llvm.css" type="text/css"> +</head> +<body> + +<div class="doc_title"> + The LLVM Target-Independent Code Generator +</div> + +<ol> + <li><a href="#introduction">Introduction</a> + <ul> + <li><a href="#required">Required components in the code generator</a></li> + <li><a href="#high-level-design">The high-level design of the code + generator</a></li> + <li><a href="#tablegen">Using TableGen for target description</a></li> + </ul> + </li> + <li><a href="#targetdesc">Target description classes</a> + <ul> + <li><a href="#targetmachine">The <tt>TargetMachine</tt> class</a></li> + <li><a href="#targetdata">The <tt>TargetData</tt> class</a></li> + <li><a href="#targetlowering">The <tt>TargetLowering</tt> class</a></li> + <li><a href="#targetregisterinfo">The <tt>TargetRegisterInfo</tt> class</a></li> + <li><a href="#targetinstrinfo">The <tt>TargetInstrInfo</tt> class</a></li> + <li><a href="#targetframeinfo">The <tt>TargetFrameInfo</tt> class</a></li> + <li><a href="#targetsubtarget">The <tt>TargetSubtarget</tt> class</a></li> + <li><a href="#targetjitinfo">The <tt>TargetJITInfo</tt> class</a></li> + </ul> + </li> + <li><a href="#codegendesc">Machine code description classes</a> + <ul> + <li><a href="#machineinstr">The <tt>MachineInstr</tt> class</a></li> + <li><a href="#machinebasicblock">The <tt>MachineBasicBlock</tt> + class</a></li> + <li><a href="#machinefunction">The <tt>MachineFunction</tt> class</a></li> + </ul> + </li> + <li><a href="#codegenalgs">Target-independent code generation algorithms</a> + <ul> + <li><a href="#instselect">Instruction Selection</a> + <ul> + <li><a href="#selectiondag_intro">Introduction to SelectionDAGs</a></li> + <li><a href="#selectiondag_process">SelectionDAG Code Generation + Process</a></li> + <li><a href="#selectiondag_build">Initial SelectionDAG + Construction</a></li> + <li><a href="#selectiondag_legalize_types">SelectionDAG LegalizeTypes Phase</a></li> + <li><a href="#selectiondag_legalize">SelectionDAG Legalize Phase</a></li> + <li><a href="#selectiondag_optimize">SelectionDAG Optimization + Phase: the DAG Combiner</a></li> + <li><a href="#selectiondag_select">SelectionDAG Select Phase</a></li> + <li><a href="#selectiondag_sched">SelectionDAG Scheduling and Formation + Phase</a></li> + <li><a href="#selectiondag_future">Future directions for the + SelectionDAG</a></li> + </ul></li> + <li><a href="#liveintervals">Live Intervals</a> + <ul> + <li><a href="#livevariable_analysis">Live Variable Analysis</a></li> + <li><a href="#liveintervals_analysis">Live Intervals Analysis</a></li> + </ul></li> + <li><a href="#regalloc">Register Allocation</a> + <ul> + <li><a href="#regAlloc_represent">How registers are represented in + LLVM</a></li> + <li><a href="#regAlloc_howTo">Mapping virtual registers to physical + registers</a></li> + <li><a href="#regAlloc_twoAddr">Handling two address instructions</a></li> + <li><a href="#regAlloc_ssaDecon">The SSA deconstruction phase</a></li> + <li><a href="#regAlloc_fold">Instruction folding</a></li> + <li><a href="#regAlloc_builtIn">Built in register allocators</a></li> + </ul></li> + <li><a href="#codeemit">Code Emission</a> + <ul> + <li><a href="#codeemit_asm">Generating Assembly Code</a></li> + <li><a href="#codeemit_bin">Generating Binary Machine Code</a></li> + </ul></li> + </ul> + </li> + <li><a href="#targetimpls">Target-specific Implementation Notes</a> + <ul> + <li><a href="#tailcallopt">Tail call optimization</a></li> + <li><a href="#sibcallopt">Sibling call optimization</a></li> + <li><a href="#x86">The X86 backend</a></li> + <li><a href="#ppc">The PowerPC backend</a> + <ul> + <li><a href="#ppc_abi">LLVM PowerPC ABI</a></li> + <li><a href="#ppc_frame">Frame Layout</a></li> + <li><a href="#ppc_prolog">Prolog/Epilog</a></li> + <li><a href="#ppc_dynamic">Dynamic Allocation</a></li> + </ul></li> + </ul></li> + +</ol> + +<div class="doc_author"> + <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>, + <a href="mailto:isanbard@gmail.com">Bill Wendling</a>, + <a href="mailto:pronesto@gmail.com">Fernando Magno Quintao + Pereira</a> and + <a href="mailto:jlaskey@mac.com">Jim Laskey</a></p> +</div> + +<div class="doc_warning"> + <p>Warning: This is a work in progress.</p> +</div> + +<!-- *********************************************************************** --> +<div class="doc_section"> + <a name="introduction">Introduction</a> +</div> +<!-- *********************************************************************** --> + +<div class="doc_text"> + +<p>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:</p> + +<ol> + <li><a href="#targetdesc">Abstract target description</a> interfaces which + capture important properties about various aspects of the machine, + independently of how they will be used. These interfaces are defined in + <tt>include/llvm/Target/</tt>.</li> + + <li>Classes used to represent the <a href="#codegendesc">machine code</a> + being generated for a target. These classes are intended to be abstract + enough to represent the machine code for <i>any</i> target machine. These + classes are defined in <tt>include/llvm/CodeGen/</tt>.</li> + + <li><a href="#codegenalgs">Target-independent algorithms</a> used to implement + various phases of native code generation (register allocation, scheduling, + stack frame representation, etc). This code lives + in <tt>lib/CodeGen/</tt>.</li> + + <li><a href="#targetimpls">Implementations of the abstract target description + interfaces</a> 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 <tt>lib/Target/</tt>.</li> + + <li><a href="#jit">The target-independent JIT components</a>. The LLVM JIT is + completely target independent (it uses the <tt>TargetJITInfo</tt> + structure to interface for target-specific issues. The code for the + target-independent JIT lives in <tt>lib/ExecutionEngine/JIT</tt>.</li> +</ol> + +<p>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 <a href="#targetdesc">target description</a> + and <a href="#codegendesc">machine code representation</a> classes. If you + want to add a backend for a new target, you will need + to <a href="#targetimpls">implement the target description</a> classes for + your new target and understand the <a href="LangRef.html">LLVM code + representation</a>. If you are interested in implementing a + new <a href="#codegenalgs">code generation algorithm</a>, it should only + depend on the target-description and machine code representation classes, + ensuring that it is portable.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="required">Required components in the code generator</a> +</div> + +<div class="doc_text"> + +<p>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 + (<a href="#targetmachine"><tt>TargetMachine</tt></a> + and <a href="#targetdata"><tt>TargetData</tt></a>) 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.</p> + +<p>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.</p> + +<p>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.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="high-level-design">The high-level design of the code generator</a> +</div> + +<div class="doc_text"> + +<p>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:</p> + +<ol> + <li><b><a href="#instselect">Instruction Selection</a></b> — 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.</li> + + <li><b><a href="#selectiondag_sched">Scheduling and Formation</a></b> — + 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 <tt><a href="#machineinstr">MachineInstr</a></tt>s with that ordering. + Note that we describe this in the <a href="#instselect">instruction + selection section</a> because it operates on + a <a href="#selectiondag_intro">SelectionDAG</a>.</li> + + <li><b><a href="#ssamco">SSA-based Machine Code Optimizations</a></b> — + 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.</li> + + <li><b><a href="#regalloc">Register Allocation</a></b> — 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.</li> + + <li><b><a href="#proepicode">Prolog/Epilog Code Insertion</a></b> — 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.</li> + + <li><b><a href="#latemco">Late Machine Code Optimizations</a></b> — + Optimizations that operate on "final" machine code can go here, such as + spill code scheduling and peephole optimizations.</li> + + <li><b><a href="#codeemit">Code Emission</a></b> — The final stage + actually puts out the code for the current function, either in the target + assembler format or in machine code.</li> +</ol> + +<p>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.</p> + +<p>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.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="tablegen">Using TableGen for target description</a> +</div> + +<div class="doc_text"> + +<p>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 <tt>add</tt> instruction is almost identical to a + <tt>sub</tt> instruction). In order to allow the maximum amount of + commonality to be factored out, the LLVM code generator uses + the <a href="TableGenFundamentals.html">TableGen</a> 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.</p> + +<p>As LLVM continues to be developed and refined, we plan to move more and more + of the target description to the <tt>.td</tt> 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 <tt>tblgen</tt>, we only need a change in one place (<tt>tblgen</tt>) to + update all of the targets to a new interface.</p> + +</div> + +<!-- *********************************************************************** --> +<div class="doc_section"> + <a name="targetdesc">Target description classes</a> +</div> +<!-- *********************************************************************** --> + +<div class="doc_text"> + +<p>The LLVM target description classes (located in the + <tt>include/llvm/Target</tt> directory) provide an abstract description of + the target machine independent of any particular client. These classes are + designed to capture the <i>abstract</i> properties of the target (such as the + instructions and registers it has), and do not incorporate any particular + pieces of code generation algorithms.</p> + +<p>All of the target description classes (except the + <tt><a href="#targetdata">TargetData</a></tt> class) are designed to be + subclassed by the concrete target implementation, and have virtual methods + implemented. To get to these implementations, the + <tt><a href="#targetmachine">TargetMachine</a></tt> class provides accessors + that should be implemented by the target.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="targetmachine">The <tt>TargetMachine</tt> class</a> +</div> + +<div class="doc_text"> + +<p>The <tt>TargetMachine</tt> class provides virtual methods that are used to + access the target-specific implementations of the various target description + classes via the <tt>get*Info</tt> methods (<tt>getInstrInfo</tt>, + <tt>getRegisterInfo</tt>, <tt>getFrameInfo</tt>, etc.). This class is + designed to be specialized by a concrete target implementation + (e.g., <tt>X86TargetMachine</tt>) which implements the various virtual + methods. The only required target description class is + the <a href="#targetdata"><tt>TargetData</tt></a> class, but if the code + generator components are to be used, the other interfaces should be + implemented as well.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="targetdata">The <tt>TargetData</tt> class</a> +</div> + +<div class="doc_text"> + +<p>The <tt>TargetData</tt> 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). <tt>TargetData</tt> 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.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="targetlowering">The <tt>TargetLowering</tt> class</a> +</div> + +<div class="doc_text"> + +<p>The <tt>TargetLowering</tt> 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:</p> + +<ul> + <li>an initial register class to use for various <tt>ValueType</tt>s,</li> + + <li>which operations are natively supported by the target machine,</li> + + <li>the return type of <tt>setcc</tt> operations,</li> + + <li>the type to use for shift amounts, and</li> + + <li>various high-level characteristics, like whether it is profitable to turn + division by a constant into a multiplication sequence</li> +</ul> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="targetregisterinfo">The <tt>TargetRegisterInfo</tt> class</a> +</div> + +<div class="doc_text"> + +<p>The <tt>TargetRegisterInfo</tt> class is used to describe the register file + of the target and any interactions between the registers.</p> + +<p>Registers in the code generator are represented in the code generator by + 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.</p> + +<p>Each register in the processor description has an associated + <tt>TargetRegisterDesc</tt> 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).</p> + +<p>In addition to the per-register description, the <tt>TargetRegisterInfo</tt> + class exposes a set of processor specific register classes (instances of the + <tt>TargetRegisterClass</tt> 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.</p> + +<p>The target-specific implementations of these classes is auto-generated from + a <a href="TableGenFundamentals.html">TableGen</a> description of the + register file.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="targetinstrinfo">The <tt>TargetInstrInfo</tt> class</a> +</div> + +<div class="doc_text"> + +<p>The <tt>TargetInstrInfo</tt> class is used to describe the machine + instructions supported by the target. It is essentially an array of + <tt>TargetInstrDescriptor</tt> 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.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="targetframeinfo">The <tt>TargetFrameInfo</tt> class</a> +</div> + +<div class="doc_text"> + +<p>The <tt>TargetFrameInfo</tt> 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.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="targetsubtarget">The <tt>TargetSubtarget</tt> class</a> +</div> + +<div class="doc_text"> + +<p>The <tt>TargetSubtarget</tt> class is used to provide information about the + specific chip set being targeted. A sub-target informs code generation of + which instructions are supported, instruction latencies and instruction + execution itinerary; i.e., which processing units are used, in what order, + and for how long.</p> + +</div> + + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="targetjitinfo">The <tt>TargetJITInfo</tt> class</a> +</div> + +<div class="doc_text"> + +<p>The <tt>TargetJITInfo</tt> class exposes an abstract interface used by the + Just-In-Time code generator to perform target-specific activities, such as + emitting stubs. If a <tt>TargetMachine</tt> supports JIT code generation, it + should provide one of these objects through the <tt>getJITInfo</tt> + method.</p> + +</div> + +<!-- *********************************************************************** --> +<div class="doc_section"> + <a name="codegendesc">Machine code description classes</a> +</div> +<!-- *********************************************************************** --> + +<div class="doc_text"> + +<p>At the high-level, LLVM code is translated to a machine specific + representation formed out of + <a href="#machinefunction"><tt>MachineFunction</tt></a>, + <a href="#machinebasicblock"><tt>MachineBasicBlock</tt></a>, + and <a href="#machineinstr"><tt>MachineInstr</tt></a> instances (defined + in <tt>include/llvm/CodeGen</tt>). 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.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="machineinstr">The <tt>MachineInstr</tt> class</a> +</div> + +<div class="doc_text"> + +<p>Target machine instructions are represented as instances of the + <tt>MachineInstr</tt> 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.</p> + +<p>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 <tt>*InstrInfo.td</tt> file for the target. The opcode enum values are + auto-generated from this description. The <tt>MachineInstr</tt> 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 + <tt><a href="#targetinstrinfo">TargetInstrInfo</a></tt> class.</p> + +<p>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).</p> + +<p>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: "<tt>add %i1, %i2, %i3</tt>" 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 "<tt>%i3, %i1, %i2</tt>": with the + destination first.</p> + +<p>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:</p> + +<div class="doc_code"> +<pre> +%r3 = add %i1, %i2 +</pre> +</div> + +<p>Also if the first operand is a def, it is easier to <a href="#buildmi">create + instructions</a> whose only def is the first operand.</p> + +</div> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="buildmi">Using the <tt>MachineInstrBuilder.h</tt> functions</a> +</div> + +<div class="doc_text"> + +<p>Machine instructions are created by using the <tt>BuildMI</tt> functions, + located in the <tt>include/llvm/CodeGen/MachineInstrBuilder.h</tt> file. The + <tt>BuildMI</tt> functions make it easy to build arbitrary machine + instructions. Usage of the <tt>BuildMI</tt> functions look like this:</p> + +<div class="doc_code"> +<pre> +// 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 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 self looping branch instruction. +BuildMI(MBB, X86::JNE, 1).addMBB(&MBB); +</pre> +</div> + +<p>The key thing to remember with the <tt>BuildMI</tt> 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:</p> + +<div class="doc_code"> +<pre> +MI.addReg(Reg, RegState::Define); +</pre> +</div> + +</div> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="fixedregs">Fixed (preassigned) registers</a> +</div> + +<div class="doc_text"> + +<p>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 <em>must</em> 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 <tt>EAX</tt>/<tt>EDX</tt> 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.</p> + +<p>For example, consider this simple LLVM example:</p> + +<div class="doc_code"> +<pre> +define i32 @test(i32 %X, i32 %Y) { + %Z = udiv i32 %X, %Y + ret i32 %Z +} +</pre> +</div> + +<p>The X86 instruction selector produces this machine code for the <tt>div</tt> + and <tt>ret</tt> (use "<tt>llc X.bc -march=x86 -print-machineinstrs</tt>" to + get this):</p> + +<div class="doc_code"> +<pre> +;; 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 +</pre> +</div> + +<p>By the end of code generation, the register allocator has coalesced the + registers and deleted the resultant identity moves producing the following + code:</p> + +<div class="doc_code"> +<pre> +;; X is in EAX, Y is in ECX +mov %EAX, %EDX +sar %EDX, 31 +idiv %ECX +ret +</pre> +</div> + +<p>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 <em>must</em> live in a virtual + register.</p> + +</div> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="ssa">Machine code in SSA form</a> +</div> + +<div class="doc_text"> + +<p><tt>MachineInstr</tt>'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.</p> + +<p>After register allocation, machine code is no longer in SSA-form because + there are no virtual registers left in the code.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="machinebasicblock">The <tt>MachineBasicBlock</tt> class</a> +</div> + +<div class="doc_text"> + +<p>The <tt>MachineBasicBlock</tt> class contains a list of machine instructions + (<tt><a href="#machineinstr">MachineInstr</a></tt> 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 <tt>MachineBasicBlock</tt> class has a + "<tt>getBasicBlock</tt>" method, which returns the LLVM basic block that it + comes from.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="machinefunction">The <tt>MachineFunction</tt> class</a> +</div> + +<div class="doc_text"> + +<p>The <tt>MachineFunction</tt> class contains a list of machine basic blocks + (<tt><a href="#machinebasicblock">MachineBasicBlock</a></tt> instances). It + corresponds one-to-one with the LLVM function input to the instruction + selector. In addition to a list of basic blocks, + the <tt>MachineFunction</tt> contains a a <tt>MachineConstantPool</tt>, + a <tt>MachineFrameInfo</tt>, a <tt>MachineFunctionInfo</tt>, and a + <tt>MachineRegisterInfo</tt>. See + <tt>include/llvm/CodeGen/MachineFunction.h</tt> for more information.</p> + +</div> + +<!-- *********************************************************************** --> +<div class="doc_section"> + <a name="codegenalgs">Target-independent code generation algorithms</a> +</div> +<!-- *********************************************************************** --> + +<div class="doc_text"> + +<p>This section documents the phases described in the + <a href="#high-level-design">high-level design of the code generator</a>. + It explains how they work and some of the rationale behind their design.</p> + +</div> + +<!-- ======================================================================= --> +<div class="doc_subsection"> + <a name="instselect">Instruction Selection</a> +</div> + +<div class="doc_text"> + +<p>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.</p> + +<p>Portions of the DAG instruction selector are generated from the target + description (<tt>*.td</tt>) files. Our goal is for the entire instruction + selector to be generated from these <tt>.td</tt> files, though currently + there are still things that require custom C++ code.</p> + +</div> + +<!-- _______________________________________________________________________ --> +<div class="doc_subsubsection"> + <a name="selectiondag_intro">Introduction to SelectionDAGs</a> +</div> + +<div class="doc_text"> + +<p>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) <a href="#selectiondag_optimize">optimizations</a> may be + performed; ones which require extensive information about the instructions + efficiently supported by the target.</p> + +<p>The SelectionDAG is a Directed-Acyclic-Graph whose nodes are instances of the + <tt>SDNode</tt> class. The primary payload of the <tt>SDNode</tt> 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 <tt>include/llvm/CodeGen/SelectionDAGNodes.h</tt> + file.</p> + +<p>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 <tt>SDValue</tt> + class, which is a <tt><SDNode, unsigned></tt> pair, indicating the node + and result value being used, respectively. Each value produced by + an <tt>SDNode</tt> has an associated <tt>MVT</tt> (Machine Value Type) + indicating what the type of the value is.</p> + +<p>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 <tt>MVT::Other</tt>. + These edges provide an or |