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