Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / e35d3bb84e73b85d4c96fc4ad75120541844b080 / . / docs / CodeGenerator.html
blob: a4a6ea0dbae15f14d2e8201e341ce94570546e98 [file] [log] [blame]
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
3<html>
4<head>
5 <title>The LLVM Target-Independent Code Generator</title>
6 <link rel="stylesheet" href="llvm.css" type="text/css">
7</head>
8<body>
9
10<div class="doc_title">
11 The LLVM Target-Independent Code Generator
12</div>
13
14<ol>
15 <li><a href="#introduction">Introduction</a>
16 <ul>
17 <li><a href="#required">Required components in the code generator</a></li>
Chris Lattnere35d3bb2005-10-16 00:36:38 +0000[diff] [blame^]18 <li><a href="#high-level-design">The high-level design of the code
19 generator</a></li>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]20 <li><a href="#tablegen">Using TableGen for target description</a></li>
21 </ul>
22 </li>
23 <li><a href="#targetdesc">Target description classes</a>
24 <ul>
25 <li><a href="#targetmachine">The <tt>TargetMachine</tt> class</a></li>
26 <li><a href="#targetdata">The <tt>TargetData</tt> class</a></li>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]27 <li><a href="#targetlowering">The <tt>TargetLowering</tt> class</a></li>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]28 <li><a href="#mregisterinfo">The <tt>MRegisterInfo</tt> class</a></li>
29 <li><a href="#targetinstrinfo">The <tt>TargetInstrInfo</tt> class</a></li>
30 <li><a href="#targetframeinfo">The <tt>TargetFrameInfo</tt> class</a></li>
31 <li><a href="#targetjitinfo">The <tt>TargetJITInfo</tt> class</a></li>
32 </ul>
33 </li>
34 <li><a href="#codegendesc">Machine code description classes</a>
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]35 <ul>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]36 <li><a href="#machineinstr">The <tt>MachineInstr</tt> class</a></li>
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]37 </ul>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]38 </li>
39 <li><a href="#codegenalgs">Target-independent code generation algorithms</a>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]40 <ul>
41 <li><a href="#instselect">Instruction Selection</a>
42 <ul>
43 <li><a href="#selectiondag_intro">Introduction to SelectionDAGs</a></li>
44 <li><a href="#selectiondag_process">SelectionDAG Code Generation
45 Process</a></li>
46 <li><a href="#selectiondag_build">Initial SelectionDAG
47 Construction</a></li>
48 <li><a href="#selectiondag_legalize">SelectionDAG Legalize Phase</a></li>
49 <li><a href="#selectiondag_optimize">SelectionDAG Optimization
Chris Lattnere35d3bb2005-10-16 00:36:38 +0000[diff] [blame^]50 Phase: the DAG Combiner</a></li>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]51 <li><a href="#selectiondag_select">SelectionDAG Select Phase</a></li>
Chris Lattnere35d3bb2005-10-16 00:36:38 +0000[diff] [blame^]52 <li><a href="#selectiondag_sched">SelectionDAG Scheduling and Emission
53 Phase</a></li>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]54 <li><a href="#selectiondag_future">Future directions for the
55 SelectionDAG</a></li>
56 </ul></li>
57 </ul>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]58 </li>
59 <li><a href="#targetimpls">Target description implementations</a>
60 <ul>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]61 <li><a href="#x86">The X86 backend</a></li>
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]62 </ul>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]63 </li>
64
65</ol>
66
67<div class="doc_author">
68 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
69</div>
70
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]71<div class="doc_warning">
72 <p>Warning: This is a work in progress.</p>
73</div>
74
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]75<!-- *********************************************************************** -->
76<div class="doc_section">
77 <a name="introduction">Introduction</a>
78</div>
79<!-- *********************************************************************** -->
80
81<div class="doc_text">
82
83<p>The LLVM target-independent code generator is a framework that provides a
84suite of reusable components for translating the LLVM internal representation to
85the machine code for a specified target -- either in assembly form (suitable for
86a static compiler) or in binary machine code format (usable for a JIT compiler).
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]87The LLVM target-independent code generator consists of five main components:</p>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]88
89<ol>
90<li><a href="#targetdesc">Abstract target description</a> interfaces which
Reid Spencerbdbcb8a2004-06-05 14:39:24 +0000[diff] [blame]91capture important properties about various aspects of the machine, independently
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]92of how they will be used. These interfaces are defined in
93<tt>include/llvm/Target/</tt>.</li>
94
95<li>Classes used to represent the <a href="#codegendesc">machine code</a> being
Reid Spencerbdbcb8a2004-06-05 14:39:24 +0000[diff] [blame]96generated for a target. These classes are intended to be abstract enough to
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]97represent the machine code for <i>any</i> target machine. These classes are
98defined in <tt>include/llvm/CodeGen/</tt>.</li>
99
100<li><a href="#codegenalgs">Target-independent algorithms</a> used to implement
101various phases of native code generation (register allocation, scheduling, stack
102frame representation, etc). This code lives in <tt>lib/CodeGen/</tt>.</li>
103
104<li><a href="#targetimpls">Implementations of the abstract target description
105interfaces</a> for particular targets. These machine descriptions make use of
106the components provided by LLVM, and can optionally provide custom
107target-specific passes, to build complete code generators for a specific target.
108Target descriptions live in <tt>lib/Target/</tt>.</li>
109
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]110<li><a href="#jit">The target-independent JIT components</a>. The LLVM JIT is
111completely target independent (it uses the <tt>TargetJITInfo</tt> structure to
112interface for target-specific issues. The code for the target-independent
113JIT lives in <tt>lib/ExecutionEngine/JIT</tt>.</li>
114
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]115</ol>
116
117<p>
118Depending on which part of the code generator you are interested in working on,
119different pieces of this will be useful to you. In any case, you should be
120familiar with the <a href="#targetdesc">target description</a> and <a
121href="#codegendesc">machine code representation</a> classes. If you want to add
Reid Spencerbdbcb8a2004-06-05 14:39:24 +0000[diff] [blame]122a backend for a new target, you will need to <a href="#targetimpls">implement the
123target description</a> classes for your new target and understand the <a
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]124href="LangRef.html">LLVM code representation</a>. If you are interested in
125implementing a new <a href="#codegenalgs">code generation algorithm</a>, it
126should only depend on the target-description and machine code representation
127classes, ensuring that it is portable.
128</p>
129
130</div>
131
132<!-- ======================================================================= -->
133<div class="doc_subsection">
134 <a name="required">Required components in the code generator</a>
135</div>
136
137<div class="doc_text">
138
139<p>The two pieces of the LLVM code generator are the high-level interface to the
140code generator and the set of reusable components that can be used to build
141target-specific backends. The two most important interfaces (<a
142href="#targetmachine"><tt>TargetMachine</tt></a> and <a
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]143href="#targetdata"><tt>TargetData</tt></a>) are the only ones that are
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]144required to be defined for a backend to fit into the LLVM system, but the others
145must be defined if the reusable code generator components are going to be
146used.</p>
147
148<p>This design has two important implications. The first is that LLVM can
149support completely non-traditional code generation targets. For example, the C
150backend does not require register allocation, instruction selection, or any of
151the other standard components provided by the system. As such, it only
152implements these two interfaces, and does its own thing. Another example of a
153code generator like this is a (purely hypothetical) backend that converts LLVM
154to the GCC RTL form and uses GCC to emit machine code for a target.</p>
155
Reid Spencerbdbcb8a2004-06-05 14:39:24 +0000[diff] [blame]156<p>This design also implies that it is possible to design and
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]157implement radically different code generators in the LLVM system that do not
158make use of any of the built-in components. Doing so is not recommended at all,
159but could be required for radically different targets that do not fit into the
160LLVM machine description model: programmable FPGAs for example.</p>
Chris Lattner900bf8c2004-06-02 07:06:06 +0000[diff] [blame]161
162<p><b>Important Note:</b> For historical reasons, the LLVM SparcV9 code
163generator uses almost entirely different code paths than described in this
164document. For this reason, there are some deprecated interfaces (such as
165<tt>TargetRegInfo</tt> and <tt>TargetSchedInfo</tt>), which are only used by the
166V9 backend and should not be used by any other targets. Also, all code in the
167<tt>lib/Target/SparcV9</tt> directory and subdirectories should be considered
168deprecated, and should not be used as the basis for future code generator work.
Misha Brukmanf3709d62004-06-03 16:55:57 +0000[diff] [blame]169The SparcV9 backend is slowly being merged into the rest of the
170target-independent code generators, but this is a low-priority process with no
Chris Lattner900bf8c2004-06-02 07:06:06 +0000[diff] [blame]171predictable completion date.</p>
172
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]173</div>
174
175<!-- ======================================================================= -->
176<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]177 <a name="high-level-design">The high-level design of the code generator</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]178</div>
179
180<div class="doc_text">
181
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]182<p>The LLVM target-independent code generator is designed to support efficient and
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]183quality code generation for standard register-based microprocessors. Code
184generation in this model is divided into the following stages:</p>
185
186<ol>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]187<li><b><a href="#instselect">Instruction Selection</a></b> - Determining an
188efficient implementation of the input LLVM code in the target instruction set.
189This stage produces the initial code for the program in the target instruction
190set, then makes use of virtual registers in SSA form and physical registers that
191represent any required register assignments due to target constraints or calling
192conventions.</li>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]193
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]194<li><b><a href="#ssamco">SSA-based Machine Code Optimizations</a></b> - This
195optional stage consists of a series of machine-code optimizations that
196operate on the SSA-form produced by the instruction selector. Optimizations
197like modulo-scheduling, normal scheduling, or peephole optimization work here.
198</li>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]199
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]200<li><b><a name="#regalloc">Register Allocation</a></b> - The
201target code is transformed from an infinite virtual register file in SSA form
202to the concrete register file used by the target. This phase introduces spill
203code and eliminates all virtual register references from the program.</li>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]204
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]205<li><b><a name="#proepicode">Prolog/Epilog Code Insertion</a></b> - Once the
206machine code has been generated for the function and the amount of stack space
207required is known (used for LLVM alloca's and spill slots), the prolog and
208epilog code for the function can be inserted and "abstract stack location
209references" can be eliminated. This stage is responsible for implementing
210optimizations like frame-pointer elimination and stack packing.</li>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]211
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]212<li><b><a name="latemco">Late Machine Code Optimizations</a></b> - Optimizations
213that operate on "final" machine code can go here, such as spill code scheduling
214and peephole optimizations.</li>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]215
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]216<li><b><a name="codemission">Code Emission</a></b> - The final stage actually
217puts out the code for the current function, either in the target assembler
218format or in machine code.</li>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]219
220</ol>
221
222<p>
223The code generator is based on the assumption that the instruction selector will
224use an optimal pattern matching selector to create high-quality sequences of
Reid Spencerbdbcb8a2004-06-05 14:39:24 +0000[diff] [blame]225native instructions. Alternative code generator designs based on pattern
226expansion and
227aggressive iterative peephole optimization are much slower. This design
228permits efficient compilation (important for JIT environments) and
229aggressive optimization (used when generating code offline) by allowing
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]230components of varying levels of sophistication to be used for any step of
Reid Spencerbdbcb8a2004-06-05 14:39:24 +0000[diff] [blame]231compilation.</p>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]232
233<p>
234In addition to these stages, target implementations can insert arbitrary
235target-specific passes into the flow. For example, the X86 target uses a
236special pass to handle the 80x87 floating point stack architecture. Other
237targets with unusual requirements can be supported with custom passes as needed.
238</p>
239
240</div>
241
242
243<!-- ======================================================================= -->
244<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]245 <a name="tablegen">Using TableGen for target description</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]246</div>
247
248<div class="doc_text">
249
Chris Lattner5489e932004-06-01 18:35:00 +0000[diff] [blame]250<p>The target description classes require a detailed description of the target
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]251architecture. These target descriptions often have a large amount of common
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]252information (e.g., an <tt>add</tt> instruction is almost identical to a
253<tt>sub</tt> instruction).
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]254In order to allow the maximum amount of commonality to be factored out, the LLVM
255code generator uses the <a href="TableGenFundamentals.html">TableGen</a> tool to
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]256describe big chunks of the target machine, which allows the use of
257domain-specific and target-specific abstractions to reduce the amount of
258repetition.
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]259</p>
260
261</div>
262
263<!-- *********************************************************************** -->
264<div class="doc_section">
265 <a name="targetdesc">Target description classes</a>
266</div>
267<!-- *********************************************************************** -->
268
269<div class="doc_text">
270
271<p>The LLVM target description classes (which are located in the
272<tt>include/llvm/Target</tt> directory) provide an abstract description of the
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]273target machine; independent of any particular client. These classes are
274designed to capture the <i>abstract</i> properties of the target (such as the
275instructions and registers it has), and do not incorporate any particular pieces
276of code generation algorithms. These interfaces do not take interference graphs
277as inputs or other algorithm-specific data structures.</p>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]278
279<p>All of the target description classes (except the <tt><a
280href="#targetdata">TargetData</a></tt> class) are designed to be subclassed by
281the concrete target implementation, and have virtual methods implemented. To
Reid Spencerbdbcb8a2004-06-05 14:39:24 +0000[diff] [blame]282get to these implementations, the <tt><a
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]283href="#targetmachine">TargetMachine</a></tt> class provides accessors that
284should be implemented by the target.</p>
285
286</div>
287
288<!-- ======================================================================= -->
289<div class="doc_subsection">
290 <a name="targetmachine">The <tt>TargetMachine</tt> class</a>
291</div>
292
293<div class="doc_text">
294
295<p>The <tt>TargetMachine</tt> class provides virtual methods that are used to
296access the target-specific implementations of the various target description
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]297classes via the <tt>get*Info</tt> methods (<tt>getInstrInfo</tt>,
298<tt>getRegisterInfo</tt>, <tt>getFrameInfo</tt>, etc.). This class is
299designed to be specialized by
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]300a concrete target implementation (e.g., <tt>X86TargetMachine</tt>) which
301implements the various virtual methods. The only required target description
302class is the <a href="#targetdata"><tt>TargetData</tt></a> class, but if the
303code generator components are to be used, the other interfaces should be
304implemented as well.</p>
305
306</div>
307
308
309<!-- ======================================================================= -->
310<div class="doc_subsection">
311 <a name="targetdata">The <tt>TargetData</tt> class</a>
312</div>
313
314<div class="doc_text">
315
316<p>The <tt>TargetData</tt> class is the only required target description class,
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]317and it is the only class that is not extensible. You cannot derived a new
318class from it. <tt>TargetData</tt> specifies information about how the target
319lays out memory for structures, the alignment requirements for various data
320types, the size of pointers in the target, and whether the target is
321little-endian or big-endian.</p>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]322
323</div>
324
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]325<!-- ======================================================================= -->
326<div class="doc_subsection">
327 <a name="targetlowering">The <tt>TargetLowering</tt> class</a>
328</div>
329
330<div class="doc_text">
331
332<p>The <tt>TargetLowering</tt> class is used by SelectionDAG based instruction
333selectors primarily to describe how LLVM code should be lowered to SelectionDAG
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]334operations. Among other things, this class indicates:
335<ul><li>an initial register class to use for various ValueTypes,</li>
336 <li>which operations are natively supported by the target machine,</li>
337 <li>the return type of setcc operations, and</li>
338 <li>the type to use for shift amounts, etc</li>.
339</ol></p>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]340
341</div>
342
343
344
345
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]346
347<!-- ======================================================================= -->
348<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]349 <a name="mregisterinfo">The <tt>MRegisterInfo</tt> class</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]350</div>
351
352<div class="doc_text">
353
354<p>The <tt>MRegisterInfo</tt> class (which will eventually be renamed to
355<tt>TargetRegisterInfo</tt>) is used to describe the register file of the
356target and any interactions between the registers.</p>
357
358<p>Registers in the code generator are represented in the code generator by
359unsigned numbers. Physical registers (those that actually exist in the target
360description) are unique small numbers, and virtual registers are generally
361large.</p>
362
363<p>Each register in the processor description has an associated
Chris Lattner88a06d22005-09-30 17:46:55 +0000[diff] [blame]364<tt>TargetRegisterDesc</tt> entry, which provides a textual name for the register
365(used for assembly output and debugging dumps) and a set of aliases (used to
366indicate that one register overlaps with another).
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]367</p>
368
369<p>In addition to the per-register description, the <tt>MRegisterInfo</tt> class
370exposes a set of processor specific register classes (instances of the
371<tt>TargetRegisterClass</tt> class). Each register class contains sets of
372registers that have the same properties (for example, they are all 32-bit
373integer registers). Each SSA virtual register created by the instruction
374selector has an associated register class. When the register allocator runs, it
375replaces virtual registers with a physical register in the set.</p>
376
377<p>
378The target-specific implementations of these classes is auto-generated from a <a
379href="TableGenFundamentals.html">TableGen</a> description of the register file.
380</p>
381
382</div>
383
384<!-- ======================================================================= -->
385<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]386 <a name="targetinstrinfo">The <tt>TargetInstrInfo</tt> class</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]387</div>
388
Reid Spencer627cd002005-07-19 01:36:35 +0000[diff] [blame]389<div class="doc_text">
390 <p>The <tt>TargetInstrInfo</tt> class is used to describe the machine
391 instructions supported by the target. It is essentially an array of
392 <tt>TargetInstrDescriptor</tt> objects, each of which describes one
393 instruction the target supports. Descriptors define things like the mnemonic
Chris Lattnera3079782005-07-19 03:37:48 +0000[diff] [blame]394 for the opcode, the number of operands, the list of implicit register uses
395 and defs, whether the instruction has certain target-independent properties
396 (accesses memory, is commutable, etc), and holds any target-specific flags.</p>
Reid Spencer627cd002005-07-19 01:36:35 +0000[diff] [blame]397</div>
398
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]399<!-- ======================================================================= -->
400<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]401 <a name="targetframeinfo">The <tt>TargetFrameInfo</tt> class</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]402</div>
403
Reid Spencer627cd002005-07-19 01:36:35 +0000[diff] [blame]404<div class="doc_text">
405 <p>The <tt>TargetFrameInfo</tt> class is used to provide information about the
406 stack frame layout of the target. It holds the direction of stack growth,
407 the known stack alignment on entry to each function, and the offset to the
408 locals area. The offset to the local area is the offset from the stack
409 pointer on function entry to the first location where function data (local
410 variables, spill locations) can be stored.</p>
Reid Spencer627cd002005-07-19 01:36:35 +0000[diff] [blame]411</div>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]412<!-- ======================================================================= -->
413<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]414 <a name="targetjitinfo">The <tt>TargetJITInfo</tt> class</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]415</div>
416
417<!-- *********************************************************************** -->
418<div class="doc_section">
419 <a name="codegendesc">Machine code description classes</a>
420</div>
421<!-- *********************************************************************** -->
422
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]423<div class="doc_text">
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]424
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]425<p>
426At the high-level, LLVM code is translated to a machine specific representation
427formed out of MachineFunction, MachineBasicBlock, and <a
428href="#machineinstr"><tt>MachineInstr</tt></a> instances
429(defined in include/llvm/CodeGen). This representation is completely target
430agnostic, representing instructions in their most abstract form: an opcode and a
431series of operands. This representation is designed to support both SSA
432representation for machine code, as well as a register allocated, non-SSA form.
433</p>
434
435</div>
436
437<!-- ======================================================================= -->
438<div class="doc_subsection">
439 <a name="machineinstr">The <tt>MachineInstr</tt> class</a>
440</div>
441
442<div class="doc_text">
443
444<p>Target machine instructions are represented as instances of the
445<tt>MachineInstr</tt> class. This class is an extremely abstract way of
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]446representing machine instructions. In particular, it only keeps track of
447an opcode number and a set of operands.</p>
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]448
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]449<p>The opcode number is a simple unsigned number that only has meaning to a
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]450specific backend. All of the instructions for a target should be defined in
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]451the <tt>*InstrInfo.td</tt> file for the target. The opcode enum values
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]452are auto-generated from this description. The <tt>MachineInstr</tt> class does
453not have any information about how to interpret the instruction (i.e., what the
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]454semantics of the instruction are): for that you must refer to the
455<tt><a href="#targetinstrinfo">TargetInstrInfo</a></tt> class.</p>
456
457<p>The operands of a machine instruction can be of several different types:
458they can be a register reference, constant integer, basic block reference, etc.
459In addition, a machine operand should be marked as a def or a use of the value
460(though only registers are allowed to be defs).</p>
461
462<p>By convention, the LLVM code generator orders instruction operands so that
463all register definitions come before the register uses, even on architectures
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]464that are normally printed in other orders. For example, the SPARC add
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]465instruction: "<tt>add %i1, %i2, %i3</tt>" adds the "%i1", and "%i2" registers
466and stores the result into the "%i3" register. In the LLVM code generator,
467the operands should be stored as "<tt>%i3, %i1, %i2</tt>": with the destination
468first.</p>
469
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]470<p>Keeping destination (definition) operands at the beginning of the operand
471list has several advantages. In particular, the debugging printer will print
472the instruction like this:</p>
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]473
474<pre>
475 %r3 = add %i1, %i2
476</pre>
477
478<p>If the first operand is a def, and it is also easier to <a
479href="#buildmi">create instructions</a> whose only def is the first
480operand.</p>
481
482</div>
483
484<!-- _______________________________________________________________________ -->
485<div class="doc_subsubsection">
486 <a name="buildmi">Using the <tt>MachineInstrBuilder.h</tt> functions</a>
487</div>
488
489<div class="doc_text">
490
491<p>Machine instructions are created by using the <tt>BuildMI</tt> functions,
492located in the <tt>include/llvm/CodeGen/MachineInstrBuilder.h</tt> file. The
493<tt>BuildMI</tt> functions make it easy to build arbitrary machine
494instructions. Usage of the <tt>BuildMI</tt> functions look like this:
495</p>
496
497<pre>
498 // Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
499 // instruction. The '1' specifies how many operands will be added.
500 MachineInstr *MI = BuildMI(X86::MOV32ri, 1, DestReg).addImm(42);
501
502 // Create the same instr, but insert it at the end of a basic block.
503 MachineBasicBlock &amp;MBB = ...
504 BuildMI(MBB, X86::MOV32ri, 1, DestReg).addImm(42);
505
506 // Create the same instr, but insert it before a specified iterator point.
507 MachineBasicBlock::iterator MBBI = ...
508 BuildMI(MBB, MBBI, X86::MOV32ri, 1, DestReg).addImm(42);
509
510 // Create a 'cmp Reg, 0' instruction, no destination reg.
511 MI = BuildMI(X86::CMP32ri, 2).addReg(Reg).addImm(0);
512 // Create an 'sahf' instruction which takes no operands and stores nothing.
513 MI = BuildMI(X86::SAHF, 0);
514
515 // Create a self looping branch instruction.
516 BuildMI(MBB, X86::JNE, 1).addMBB(&amp;MBB);
517</pre>
518
519<p>
520The key thing to remember with the <tt>BuildMI</tt> functions is that you have
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]521to specify the number of operands that the machine instruction will take. This
522allows for efficient memory allocation. You also need to specify if operands
523default to be uses of values, not definitions. If you need to add a definition
524operand (other than the optional destination register), you must explicitly
525mark it as such.
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]526</p>
527
528</div>
529
530<!-- _______________________________________________________________________ -->
531<div class="doc_subsubsection">
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]532 <a name="fixedregs">Fixed (preassigned) registers</a>
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]533</div>
534
535<div class="doc_text">
536
537<p>One important issue that the code generator needs to be aware of is the
538presence of fixed registers. In particular, there are often places in the
539instruction stream where the register allocator <em>must</em> arrange for a
540particular value to be in a particular register. This can occur due to
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]541limitations of the instruction set (e.g., the X86 can only do a 32-bit divide
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]542with the <tt>EAX</tt>/<tt>EDX</tt> registers), or external factors like calling
543conventions. In any case, the instruction selector should emit code that
544copies a virtual register into or out of a physical register when needed.</p>
545
546<p>For example, consider this simple LLVM example:</p>
547
548<pre>
549 int %test(int %X, int %Y) {
550 %Z = div int %X, %Y
551 ret int %Z
552 }
553</pre>
554
555<p>The X86 instruction selector produces this machine code for the div
556and ret (use
557"<tt>llc X.bc -march=x86 -print-machineinstrs</tt>" to get this):</p>
558
559<pre>
560 ;; Start of div
561 %EAX = mov %reg1024 ;; Copy X (in reg1024) into EAX
562 %reg1027 = sar %reg1024, 31
563 %EDX = mov %reg1027 ;; Sign extend X into EDX
564 idiv %reg1025 ;; Divide by Y (in reg1025)
565 %reg1026 = mov %EAX ;; Read the result (Z) out of EAX
566
567 ;; Start of ret
568 %EAX = mov %reg1026 ;; 32-bit return value goes in EAX
569 ret
570</pre>
571
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]572<p>By the end of code generation, the register allocator has coalesced
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]573the registers and deleted the resultant identity moves, producing the
574following code:</p>
575
576<pre>
577 ;; X is in EAX, Y is in ECX
578 mov %EAX, %EDX
579 sar %EDX, 31
580 idiv %ECX
581 ret
582</pre>
583
584<p>This approach is extremely general (if it can handle the X86 architecture,
585it can handle anything!) and allows all of the target specific
586knowledge about the instruction stream to be isolated in the instruction
587selector. Note that physical registers should have a short lifetime for good
588code generation, and all physical registers are assumed dead on entry and
589exit of basic blocks (before register allocation). Thus if you need a value
590to be live across basic block boundaries, it <em>must</em> live in a virtual
591register.</p>
592
593</div>
594
595<!-- _______________________________________________________________________ -->
596<div class="doc_subsubsection">
597 <a name="ssa">Machine code SSA form</a>
598</div>
599
600<div class="doc_text">
601
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]602<p><tt>MachineInstr</tt>'s are initially selected in SSA-form, and
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]603are maintained in SSA-form until register allocation happens. For the most
604part, this is trivially simple since LLVM is already in SSA form: LLVM PHI nodes
605become machine code PHI nodes, and virtual registers are only allowed to have a
606single definition.</p>
607
608<p>After register allocation, machine code is no longer in SSA-form, as there
609are no virtual registers left in the code.</p>
610
611</div>
612
613<!-- *********************************************************************** -->
614<div class="doc_section">
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]615 <a name="codegenalgs">Target-independent code generation algorithms</a>
616</div>
617<!-- *********************************************************************** -->
618
619<div class="doc_text">
620
621<p>This section documents the phases described in the <a
622href="high-level-design">high-level design of the code generator</a>. It
623explains how they work and some of the rationale behind their design.</p>
624
625</div>
626
627<!-- ======================================================================= -->
628<div class="doc_subsection">
629 <a name="instselect">Instruction Selection</a>
630</div>
631
632<div class="doc_text">
633<p>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]634Instruction Selection is the process of translating LLVM code presented to the
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]635code generator into target-specific machine instructions. There are several
636well-known ways to do this in the literature. In LLVM there are two main forms:
Chris Lattnere35d3bb2005-10-16 00:36:38 +0000[diff] [blame^]637the SelectionDAG based instruction selector framework and an old-style 'simple'
638instruction selector (which effectively peephole selects each LLVM instruction
639into a series of machine instructions). We recommend that all targets use the
640SelectionDAG infrastructure.
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]641</p>
642
Chris Lattnere35d3bb2005-10-16 00:36:38 +0000[diff] [blame^]643<p>Portions of the DAG instruction selector are generated from the target
644description files (<tt>*.td</tt>) files. Eventually, we aim for the entire
645instruction selector to be generated from these <tt>.td</tt> files.</p>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]646</div>
647
648<!-- _______________________________________________________________________ -->
649<div class="doc_subsubsection">
650 <a name="selectiondag_intro">Introduction to SelectionDAGs</a>
651</div>
652
653<div class="doc_text">
654
655<p>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]656The SelectionDAG provides an abstraction for code representation in a way that
657is amenable to instruction selection using automatic techniques
658(e.g. dynamic-programming based optimal pattern matching selectors), It is also
659well suited to other phases of code generation; in particular, instruction scheduling. Additionally, the SelectionDAG provides a host representation where a
660large variety of very-low-level (but target-independent)
661<a href="#selectiondag_optimize">optimizations</a> may be
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]662performed: ones which require extensive information about the instructions
663efficiently supported by the target.
664</p>
665
666<p>
667The SelectionDAG is a Directed-Acyclic-Graph whose nodes are instances of the
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]668<tt>SDNode</tt> class. The primary payload of the <tt>SDNode</tt> is its
669operation code (Opcode) that indicates what operation the node performs.
670The various operation node types are described at the top of the
671<tt>include/llvm/CodeGen/SelectionDAGNodes.h</tt> file. Depending on the
672operation, nodes may contain additional information (e.g. the condition code
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]673for a SETCC node) contained in a derived class.</p>
674
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]675<p>Although most operations define a single value, each node in the graph may
676define multiple values. For example, a combined div/rem operation will define
677both the dividend and the remainder. Many other situations require multiple
678values as well. Each node also has some number of operands, which are edges
679to the node defining the used value. Because nodes may define multiple values,
680edges are represented by instances of the <tt>SDOperand</tt> class, which is
681a &lt;SDNode, unsigned&gt; pair, indicating the node and result
682value being used, respectively. Each value produced by an SDNode has an
683associated MVT::ValueType, indicating what type the value is.
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]684</p>
685
686<p>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]687SelectionDAGs contain two different kinds of values: those that represent data
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]688flow and those that represent control flow dependencies. Data values are simple
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]689edges with an integer or floating point value type. Control edges are
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]690represented as "chain" edges which are of type MVT::Other. These edges provide
691an ordering between nodes that have side effects (such as
692loads/stores/calls/return/etc). All nodes that have side effects should take a
693token chain as input and produce a new one as output. By convention, token
694chain inputs are always operand #0, and chain results are always the last
695value produced by an operation.</p>
696
697<p>
698A SelectionDAG has designated "Entry" and "Root" nodes. The Entry node is
Chris Lattnere0c13172005-05-09 15:41:03 +0000[diff] [blame]699always a marker node with an Opcode of ISD::EntryToken. The Root node is the
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]700final side-effecting node in the token chain. For example, in a single basic
701block function, this would be the return node.
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]702</p>
703
704<p>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]705One important concept for SelectionDAGs is the notion of a "legal" vs. "illegal"
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]706DAG. A legal DAG for a target is one that only uses supported operations and
707supported types. On PowerPC, for example, a DAG with any values of i1, i8, i16,
708or i64 type would be illegal. The <a href="#selectiondag_legalize">legalize</a>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]709phase is responsible for turning an illegal DAG into a legal DAG.
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]710</p>
711</div>
712
713<!-- _______________________________________________________________________ -->
714<div class="doc_subsubsection">
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]715 <a name="selectiondag_process">SelectionDAG Instruction Selection Process</a>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]716</div>
717
718<div class="doc_text">
719
720<p>
721SelectionDAG-based instruction selection consists of the following steps:
722</p>
723
724<ol>
725<li><a href="#selectiondag_build">Build initial DAG</a> - This stage performs
726 a simple translation from the input LLVM code to an illegal SelectionDAG.
727 </li>
728<li><a href="#selectiondag_optimize">Optimize SelectionDAG</a> - This stage
729 performs simple optimizations on the SelectionDAG to simplify it and
730 recognize meta instructions (like rotates and div/rem pairs) for
731 targets that support these meta operations. This makes the resultant code
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]732 more efficient and the 'select instructions from DAG' phase (below) simpler.
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]733</li>
734<li><a href="#selectiondag_legalize">Legalize SelectionDAG</a> - This stage
735 converts the illegal SelectionDAG to a legal SelectionDAG, by eliminating
736 unsupported operations and data types.</li>
737<li><a href="#selectiondag_optimize">Optimize SelectionDAG (#2)</a> - This
738 second run of the SelectionDAG optimized the newly legalized DAG, to
739 eliminate inefficiencies introduced by legalization.</li>
740<li><a href="#selectiondag_select">Select instructions from DAG</a> - Finally,
741 the target instruction selector matches the DAG operations to target
Chris Lattnere35d3bb2005-10-16 00:36:38 +0000[diff] [blame^]742 instructions. This process translates the target-independent input DAG into
743 another DAG of target instructions.</li>
744<li><a href="#selectiondag_sched">SelectionDAG Scheduling and Emission</a>
745 - The last phase assigns a linear order to the instructions in the
746 target-instruction DAG and emits them into the MachineFunction being
747 compiled. This step uses traditional prepass scheduling techniques.</li>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]748</ol>
749
750<p>After all of these steps are complete, the SelectionDAG is destroyed and the
751rest of the code generation passes are run.</p>
752
753</div>
754
755<!-- _______________________________________________________________________ -->
756<div class="doc_subsubsection">
757 <a name="selectiondag_build">Initial SelectionDAG Construction</a>
758</div>
759
760<div class="doc_text">
761
762<p>
763The initial SelectionDAG is naively peephole expanded from the LLVM input by
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]764the <tt>SelectionDAGLowering</tt> class in the SelectionDAGISel.cpp file. The
765intent of this pass is to expose as much low-level, target-specific details
766to the SelectionDAG as possible. This pass is mostly hard-coded (e.g. an LLVM
767add turns into an SDNode add while a geteelementptr is expanded into the obvious
768arithmetic). This pass requires target-specific hooks to lower calls and
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]769returns, varargs, etc. For these features, the TargetLowering interface is
770used.
771</p>
772
773</div>
774
775<!-- _______________________________________________________________________ -->
776<div class="doc_subsubsection">
777 <a name="selectiondag_legalize">SelectionDAG Legalize Phase</a>
778</div>
779
780<div class="doc_text">
781
782<p>The Legalize phase is in charge of converting a DAG to only use the types and
783operations that are natively supported by the target. This involves two major
784tasks:</p>
785
786<ol>
787<li><p>Convert values of unsupported types to values of supported types.</p>
788 <p>There are two main ways of doing this: promoting a small type to a larger
Chris Lattnerfd84c2d2005-04-25 00:38:52 +0000[diff] [blame]789 type (e.g. f32 -&gt; f64, or i16 -&gt; i32), and breaking up large
790 integer types
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]791 to smaller ones (e.g. implementing i64 with i32 operations where
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]792 possible). Type conversions can insert sign and zero extensions as
793 needed to make sure that the final code has the same behavior as the
794 input.</p>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]795</li>
796
797<li><p>Eliminate operations that are not supported by the target in a supported
798 type.</p>
799 <p>Targets often have wierd constraints, such as not supporting every
800 operation on every supported datatype (e.g. X86 does not support byte
801 conditional moves). Legalize takes care of either open-coding another
802 sequence of operations to emulate the operation (this is known as
803 expansion), promoting to a larger type that supports the operation
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]804 (promotion), or using a target-specific hook to implement the
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]805 legalization.</p>
806</li>
807</ol>
808
809<p>
810Instead of using a Legalize pass, we could require that every target-specific
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]811<a href="#selectiondag_optimize">selector</a> supports and expands every
812operator and type even if they are not supported and may require many
813instructions to implement (in fact, this is the approach taken by the
814"simple" selectors). However, using a Legalize pass allows all of the
815cannonicalization patterns to be shared across targets which makes it very
816easy to optimize the cannonicalized code because it is still in the form of
817a DAG.
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]818</p>
819
820</div>
821
822<!-- _______________________________________________________________________ -->
823<div class="doc_subsubsection">
Chris Lattnere35d3bb2005-10-16 00:36:38 +0000[diff] [blame^]824 <a name="selectiondag_optimize">SelectionDAG Optimization Phase: the DAG
825 Combiner</a>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]826</div>
827
828<div class="doc_text">
829
830<p>
831The SelectionDAG optimization phase is run twice for code generation: once
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]832immediately after the DAG is built and once after legalization. The first run
833of the pass allows the initial code to be cleaned up (e.g. performing
834optimizations that depend on knowing that the operators have restricted type
835inputs). The second run of the pass cleans up the messy code generated by the
836Legalize pass, allowing Legalize to be very simple since it can ignore many
837special cases.
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]838</p>
839
840<p>
Chris Lattnere35d3bb2005-10-16 00:36:38 +0000[diff] [blame^]841One important class of optimizations performed is optimizing inserted sign and
842zero extension instructions. We currently use ad-hoc techniques, but could move
843to more rigorous techniques in the future. Here are some good
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]844papers on the subject:</p>
845
846<p>
847"<a href="http://www.eecs.harvard.edu/~nr/pubs/widen-abstract.html">Widening
848integer arithmetic</a>"<br>
849Kevin Redwine and Norman Ramsey<br>
850International Conference on Compiler Construction (CC) 2004
851</p>
852
853
854<p>
855 "<a href="http://portal.acm.org/citation.cfm?doid=512529.512552">Effective
856 sign extension elimination</a>"<br>
857 Motohiro Kawahito, Hideaki Komatsu, and Toshio Nakatani<br>
858 Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design
859 and Implementation.
860</p>
861
862</div>
863
864<!-- _______________________________________________________________________ -->
865<div class="doc_subsubsection">
866 <a name="selectiondag_select">SelectionDAG Select Phase</a>
867</div>
868
869<div class="doc_text">
870
871<p>The Select phase is the bulk of the target-specific code for instruction
872selection. This phase takes a legal SelectionDAG as input, and does simple
873pattern matching on the DAG to generate code. In time, the Select phase will
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]874be automatically generated from the target's InstrInfo.td file, which is why we
875want to make the Select phase as simple and mechanical as possible.</p>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]876
877</div>
878
879<!-- _______________________________________________________________________ -->
880<div class="doc_subsubsection">
Chris Lattnere35d3bb2005-10-16 00:36:38 +0000[diff] [blame^]881 <a name="selectiondag_sched">SelectionDAG Scheduling and Emission Phase</a>
882</div>
883
884<div class="doc_text">
885
886<p>The scheduling phase takes the DAG of target instructions from the selection
887phase and assigns an order. The scheduler can pick an order depending on
888various constraints of the machines (i.e. order for minimal register pressure or
889try to cover instruction latencies). Once an order is established, the DAG is
890converted to a list of <a href="#machineinstr">MachineInstr</a>s and the
891Selection DAG is destroyed.
892</p>
893
894</div>
895
896<!-- _______________________________________________________________________ -->
897<div class="doc_subsubsection">
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]898 <a name="selectiondag_future">Future directions for the SelectionDAG</a>
899</div>
900
901<div class="doc_text">
902
903<ol>
Chris Lattnere35d3bb2005-10-16 00:36:38 +0000[diff] [blame^]904<li>Optional function-at-a-time selection.</li>
905<li>Auto-generate entire selector from .td file.</li>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]906</li>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]907</ol>
908
909</div>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]910
911<!-- ======================================================================= -->
912<div class="doc_subsection">
913 <a name="ssamco">SSA-based Machine Code Optimizations</a>
914</div>
915<div class="doc_text"><p>To Be Written</p></div>
916<!-- ======================================================================= -->
917<div class="doc_subsection">
918 <a name="regalloc">Register Allocation</a>
919</div>
920<div class="doc_text"><p>To Be Written</p></div>
921<!-- ======================================================================= -->
922<div class="doc_subsection">
923 <a name="proepicode">Prolog/Epilog Code Insertion</a>
924</div>
925<div class="doc_text"><p>To Be Written</p></div>
926<!-- ======================================================================= -->
927<div class="doc_subsection">
928 <a name="latemco">Late Machine Code Optimizations</a>
929</div>
930<div class="doc_text"><p>To Be Written</p></div>
931<!-- ======================================================================= -->
932<div class="doc_subsection">
933 <a name="codemission">Code Emission</a>
934</div>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]935
936<!-- *********************************************************************** -->
937<div class="doc_section">
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]938 <a name="targetimpls">Target description implementations</a>
939</div>
940<!-- *********************************************************************** -->
941
942<div class="doc_text">
943
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]944<p>This section of the document explains features or design decisions that
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]945are specific to the code generator for a particular target.</p>
946
947</div>
948
949
950<!-- ======================================================================= -->
951<div class="doc_subsection">
952 <a name="x86">The X86 backend</a>
953</div>
954
955<div class="doc_text">
956
957<p>
958The X86 code generator lives in the <tt>lib/Target/X86</tt> directory. This
959code generator currently targets a generic P6-like processor. As such, it
960produces a few P6-and-above instructions (like conditional moves), but it does
961not make use of newer features like MMX or SSE. In the future, the X86 backend
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]962will have sub-target support added for specific processor families and
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]963implementations.</p>
964
965</div>
966
967<!-- _______________________________________________________________________ -->
968<div class="doc_subsubsection">
Chris Lattner9b988be2005-07-12 00:20:49 +0000[diff] [blame]969 <a name="x86_tt">X86 Target Triples Supported</a>
970</div>
971
972<div class="doc_text">
973<p>
974The following are the known target triples that are supported by the X86
975backend. This is not an exhaustive list, but it would be useful to add those
976that people test.
977</p>
978
979<ul>
980<li><b>i686-pc-linux-gnu</b> - Linux</li>
981<li><b>i386-unknown-freebsd5.3</b> - FreeBSD 5.3</li>
982<li><b>i686-pc-cygwin</b> - Cygwin on Win32</li>
983<li><b>i686-pc-mingw32</b> - MingW on Win32</li>
984<li><b>i686-apple-darwin*</b> - Apple Darwin</li>
985</ul>
986
987</div>
988
989<!-- _______________________________________________________________________ -->
990<div class="doc_subsubsection">
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]991 <a name="x86_memory">Representing X86 addressing modes in MachineInstrs</a>
992</div>
993
994<div class="doc_text">
995
Misha Brukman600df452005-02-17 22:22:24 +0000[diff] [blame]996<p>The x86 has a very flexible way of accessing memory. It is capable of
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]997forming memory addresses of the following expression directly in integer
998instructions (which use ModR/M addressing):</p>
999
1000<pre>
1001 Base+[1,2,4,8]*IndexReg+Disp32
1002</pre>
1003
Misha Brukman600df452005-02-17 22:22:24 +0000[diff] [blame]1004<p>In order to represent this, LLVM tracks no less than 4 operands for each
1005memory operand of this form. This means that the "load" form of 'mov' has the
1006following <tt>MachineOperand</tt>s in this order:</p>
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]1007
1008<pre>
1009Index: 0 | 1 2 3 4
1010Meaning: DestReg, | BaseReg, Scale, IndexReg, Displacement
1011OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg, SignExtImm
1012</pre>
1013
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]1014<p>Stores, and all other instructions, treat the four memory operands in the
1015same way, in the same order.</p>
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]1016
1017</div>
1018
1019<!-- _______________________________________________________________________ -->
1020<div class="doc_subsubsection">
1021 <a name="x86_names">Instruction naming</a>
1022</div>
1023
1024<div class="doc_text">
1025
1026<p>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame]1027An instruction name consists of the base name, a default operand size, and a
1028a character per operand with an optional special size. For example:</p>
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]1029
1030<p>
1031<tt>ADD8rr</tt> -&gt; add, 8-bit register, 8-bit register<br>
1032<tt>IMUL16rmi</tt> -&gt; imul, 16-bit register, 16-bit memory, 16-bit immediate<br>
1033<tt>IMUL16rmi8</tt> -&gt; imul, 16-bit register, 16-bit memory, 8-bit immediate<br>
1034<tt>MOVSX32rm16</tt> -&gt; movsx, 32-bit register, 16-bit memory
1035</p>
1036
1037</div>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]1038
1039<!-- *********************************************************************** -->
1040<hr>
1041<address>
1042 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
1043 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
1044 <a href="http://validator.w3.org/check/referer"><img
1045 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
1046
1047 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
1048 <a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a><br>
1049 Last modified: $Date$
1050</address>
1051
1052</body>
1053</html>