Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / ad1f0cd0cc88b39d237df67722e1fa7b56d5e74c / . / docs / CodeGenerator.html
blob: 258fd04e20e5128f5d3d9f48420915e5c8c92063 [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
361<tt>MRegisterDesc</tt> entry, which provides a textual name for the register
362(used for assembly output and debugging dumps), a set of aliases (used to
363indicate that one register overlaps with another), and some flag bits.
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
386<!-- ======================================================================= -->
387<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]388 <a name="targetframeinfo">The <tt>TargetFrameInfo</tt> class</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]389</div>
390
391<!-- ======================================================================= -->
392<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]393 <a name="targetjitinfo">The <tt>TargetJITInfo</tt> class</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]394</div>
395
396<!-- *********************************************************************** -->
397<div class="doc_section">
398 <a name="codegendesc">Machine code description classes</a>
399</div>
400<!-- *********************************************************************** -->
401
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]402<div class="doc_text">
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]403
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]404<p>
405At the high-level, LLVM code is translated to a machine specific representation
406formed out of MachineFunction, MachineBasicBlock, and <a
407href="#machineinstr"><tt>MachineInstr</tt></a> instances
408(defined in include/llvm/CodeGen). This representation is completely target
409agnostic, representing instructions in their most abstract form: an opcode and a
410series of operands. This representation is designed to support both SSA
411representation for machine code, as well as a register allocated, non-SSA form.
412</p>
413
414</div>
415
416<!-- ======================================================================= -->
417<div class="doc_subsection">
418 <a name="machineinstr">The <tt>MachineInstr</tt> class</a>
419</div>
420
421<div class="doc_text">
422
423<p>Target machine instructions are represented as instances of the
424<tt>MachineInstr</tt> class. This class is an extremely abstract way of
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]425representing machine instructions. In particular, it only keeps track of
426an opcode number and a set of operands.</p>
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]427
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]428<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]429specific backend. All of the instructions for a target should be defined in
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]430the <tt>*InstrInfo.td</tt> file for the target. The opcode enum values
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]431are auto-generated from this description. The <tt>MachineInstr</tt> class does
432not have any information about how to interpret the instruction (i.e., what the
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]433semantics of the instruction are): for that you must refer to the
434<tt><a href="#targetinstrinfo">TargetInstrInfo</a></tt> class.</p>
435
436<p>The operands of a machine instruction can be of several different types:
437they can be a register reference, constant integer, basic block reference, etc.
438In addition, a machine operand should be marked as a def or a use of the value
439(though only registers are allowed to be defs).</p>
440
441<p>By convention, the LLVM code generator orders instruction operands so that
442all register definitions come before the register uses, even on architectures
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]443that are normally printed in other orders. For example, the SPARC add
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]444instruction: "<tt>add %i1, %i2, %i3</tt>" adds the "%i1", and "%i2" registers
445and stores the result into the "%i3" register. In the LLVM code generator,
446the operands should be stored as "<tt>%i3, %i1, %i2</tt>": with the destination
447first.</p>
448
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]449<p>Keeping destination (definition) operands at the beginning of the operand
450list has several advantages. In particular, the debugging printer will print
451the instruction like this:</p>
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]452
453<pre>
454 %r3 = add %i1, %i2
455</pre>
456
457<p>If the first operand is a def, and it is also easier to <a
458href="#buildmi">create instructions</a> whose only def is the first
459operand.</p>
460
461</div>
462
463<!-- _______________________________________________________________________ -->
464<div class="doc_subsubsection">
465 <a name="buildmi">Using the <tt>MachineInstrBuilder.h</tt> functions</a>
466</div>
467
468<div class="doc_text">
469
470<p>Machine instructions are created by using the <tt>BuildMI</tt> functions,
471located in the <tt>include/llvm/CodeGen/MachineInstrBuilder.h</tt> file. The
472<tt>BuildMI</tt> functions make it easy to build arbitrary machine
473instructions. Usage of the <tt>BuildMI</tt> functions look like this:
474</p>
475
476<pre>
477 // Create a 'DestReg = mov 42' (rendered in X86 assembly as 'mov DestReg, 42')
478 // instruction. The '1' specifies how many operands will be added.
479 MachineInstr *MI = BuildMI(X86::MOV32ri, 1, DestReg).addImm(42);
480
481 // Create the same instr, but insert it at the end of a basic block.
482 MachineBasicBlock &amp;MBB = ...
483 BuildMI(MBB, X86::MOV32ri, 1, DestReg).addImm(42);
484
485 // Create the same instr, but insert it before a specified iterator point.
486 MachineBasicBlock::iterator MBBI = ...
487 BuildMI(MBB, MBBI, X86::MOV32ri, 1, DestReg).addImm(42);
488
489 // Create a 'cmp Reg, 0' instruction, no destination reg.
490 MI = BuildMI(X86::CMP32ri, 2).addReg(Reg).addImm(0);
491 // Create an 'sahf' instruction which takes no operands and stores nothing.
492 MI = BuildMI(X86::SAHF, 0);
493
494 // Create a self looping branch instruction.
495 BuildMI(MBB, X86::JNE, 1).addMBB(&amp;MBB);
496</pre>
497
498<p>
499The key thing to remember with the <tt>BuildMI</tt> functions is that you have
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]500to specify the number of operands that the machine instruction will take. This
501allows for efficient memory allocation. You also need to specify if operands
502default to be uses of values, not definitions. If you need to add a definition
503operand (other than the optional destination register), you must explicitly
504mark it as such.
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]505</p>
506
507</div>
508
509<!-- _______________________________________________________________________ -->
510<div class="doc_subsubsection">
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]511 <a name="fixedregs">Fixed (preassigned) registers</a>
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]512</div>
513
514<div class="doc_text">
515
516<p>One important issue that the code generator needs to be aware of is the
517presence of fixed registers. In particular, there are often places in the
518instruction stream where the register allocator <em>must</em> arrange for a
519particular value to be in a particular register. This can occur due to
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]520limitations 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]521with the <tt>EAX</tt>/<tt>EDX</tt> registers), or external factors like calling
522conventions. In any case, the instruction selector should emit code that
523copies a virtual register into or out of a physical register when needed.</p>
524
525<p>For example, consider this simple LLVM example:</p>
526
527<pre>
528 int %test(int %X, int %Y) {
529 %Z = div int %X, %Y
530 ret int %Z
531 }
532</pre>
533
534<p>The X86 instruction selector produces this machine code for the div
535and ret (use
536"<tt>llc X.bc -march=x86 -print-machineinstrs</tt>" to get this):</p>
537
538<pre>
539 ;; Start of div
540 %EAX = mov %reg1024 ;; Copy X (in reg1024) into EAX
541 %reg1027 = sar %reg1024, 31
542 %EDX = mov %reg1027 ;; Sign extend X into EDX
543 idiv %reg1025 ;; Divide by Y (in reg1025)
544 %reg1026 = mov %EAX ;; Read the result (Z) out of EAX
545
546 ;; Start of ret
547 %EAX = mov %reg1026 ;; 32-bit return value goes in EAX
548 ret
549</pre>
550
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]551<p>By the end of code generation, the register allocator has coalesced
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]552the registers and deleted the resultant identity moves, producing the
553following code:</p>
554
555<pre>
556 ;; X is in EAX, Y is in ECX
557 mov %EAX, %EDX
558 sar %EDX, 31
559 idiv %ECX
560 ret
561</pre>
562
563<p>This approach is extremely general (if it can handle the X86 architecture,
564it can handle anything!) and allows all of the target specific
565knowledge about the instruction stream to be isolated in the instruction
566selector. Note that physical registers should have a short lifetime for good
567code generation, and all physical registers are assumed dead on entry and
568exit of basic blocks (before register allocation). Thus if you need a value
569to be live across basic block boundaries, it <em>must</em> live in a virtual
570register.</p>
571
572</div>
573
574<!-- _______________________________________________________________________ -->
575<div class="doc_subsubsection">
576 <a name="ssa">Machine code SSA form</a>
577</div>
578
579<div class="doc_text">
580
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]581<p><tt>MachineInstr</tt>'s are initially selected in SSA-form, and
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]582are maintained in SSA-form until register allocation happens. For the most
583part, this is trivially simple since LLVM is already in SSA form: LLVM PHI nodes
584become machine code PHI nodes, and virtual registers are only allowed to have a
585single definition.</p>
586
587<p>After register allocation, machine code is no longer in SSA-form, as there
588are no virtual registers left in the code.</p>
589
590</div>
591
592<!-- *********************************************************************** -->
593<div class="doc_section">
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]594 <a name="codegenalgs">Target-independent code generation algorithms</a>
595</div>
596<!-- *********************************************************************** -->
597
598<div class="doc_text">
599
600<p>This section documents the phases described in the <a
601href="high-level-design">high-level design of the code generator</a>. It
602explains how they work and some of the rationale behind their design.</p>
603
604</div>
605
606<!-- ======================================================================= -->
607<div class="doc_subsection">
608 <a name="instselect">Instruction Selection</a>
609</div>
610
611<div class="doc_text">
612<p>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]613Instruction Selection is the process of translating LLVM code presented to the
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]614code generator into target-specific machine instructions. There are several
615well-known ways to do this in the literature. In LLVM there are two main forms:
616the old-style 'simple' instruction selector (which effectively peephole selects
617each LLVM instruction into a series of machine instructions), and the new
618SelectionDAG based instruction selector.
619</p>
620
621<p>The 'simple' instruction selectors are tedious to write, require a lot of
622boiler plate code, and are difficult to get correct. Additionally, any
623optimizations written for a simple instruction selector cannot be used by other
624targets. For this reason, LLVM is moving to a new SelectionDAG based
625instruction selector, which is described in this section. If you are starting a
626new port, we recommend that you write the instruction selector using the
627SelectionDAG infrastructure.</p>
628
629<p>In time, most of the target-specific code for instruction selection will be
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]630auto-generated from the target description (<tt>*.td</tt>) files. For now,
631however, the <a href="#selectiondag_select">Select Phase</a> must still be
632written by hand.</p>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]633</div>
634
635<!-- _______________________________________________________________________ -->
636<div class="doc_subsubsection">
637 <a name="selectiondag_intro">Introduction to SelectionDAGs</a>
638</div>
639
640<div class="doc_text">
641
642<p>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]643The SelectionDAG provides an abstraction for code representation in a way that
644is amenable to instruction selection using automatic techniques
645(e.g. dynamic-programming based optimal pattern matching selectors), It is also
646well suited to other phases of code generation; in particular, instruction scheduling. Additionally, the SelectionDAG provides a host representation where a
647large variety of very-low-level (but target-independent)
648<a href="#selectiondag_optimize">optimizations</a> may be
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]649performed: ones which require extensive information about the instructions
650efficiently supported by the target.
651</p>
652
653<p>
654The SelectionDAG is a Directed-Acyclic-Graph whose nodes are instances of the
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]655<tt>SDNode</tt> class. The primary payload of the <tt>SDNode</tt> is its
656operation code (Opcode) that indicates what operation the node performs.
657The various operation node types are described at the top of the
658<tt>include/llvm/CodeGen/SelectionDAGNodes.h</tt> file. Depending on the
659operation, nodes may contain additional information (e.g. the condition code
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]660for a SETCC node) contained in a derived class.</p>
661
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]662<p>Although most operations define a single value, each node in the graph may
663define multiple values. For example, a combined div/rem operation will define
664both the dividend and the remainder. Many other situations require multiple
665values as well. Each node also has some number of operands, which are edges
666to the node defining the used value. Because nodes may define multiple values,
667edges are represented by instances of the <tt>SDOperand</tt> class, which is
668a &lt;SDNode, unsigned&gt; pair, indicating the node and result
669value being used, respectively. Each value produced by an SDNode has an
670associated MVT::ValueType, indicating what type the value is.
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]671</p>
672
673<p>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]674SelectionDAGs contain two different kinds of values: those that represent data
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]675flow and those that represent control flow dependencies. Data values are simple
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]676edges with an integer or floating point value type. Control edges are
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]677represented as "chain" edges which are of type MVT::Other. These edges provide
678an ordering between nodes that have side effects (such as
679loads/stores/calls/return/etc). All nodes that have side effects should take a
680token chain as input and produce a new one as output. By convention, token
681chain inputs are always operand #0, and chain results are always the last
682value produced by an operation.</p>
683
684<p>
685A SelectionDAG has designated "Entry" and "Root" nodes. The Entry node is
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]686always a marker node with an Opcode of ISD::TokenFactor. The Root node is the
687final side-effecting node in the token chain. For example, in a single basic
688block function, this would be the return node.
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^]692One important concept for SelectionDAGs is the notion of a "legal" vs. "illegal"
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]693DAG. A legal DAG for a target is one that only uses supported operations and
694supported types. On PowerPC, for example, a DAG with any values of i1, i8, i16,
695or i64 type would be illegal. The <a href="#selectiondag_legalize">legalize</a>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]696phase is responsible for turning an illegal DAG into a legal DAG.
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]697</p>
698</div>
699
700<!-- _______________________________________________________________________ -->
701<div class="doc_subsubsection">
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]702 <a name="selectiondag_process">SelectionDAG Instruction Selection Process</a>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]703</div>
704
705<div class="doc_text">
706
707<p>
708SelectionDAG-based instruction selection consists of the following steps:
709</p>
710
711<ol>
712<li><a href="#selectiondag_build">Build initial DAG</a> - This stage performs
713 a simple translation from the input LLVM code to an illegal SelectionDAG.
714 </li>
715<li><a href="#selectiondag_optimize">Optimize SelectionDAG</a> - This stage
716 performs simple optimizations on the SelectionDAG to simplify it and
717 recognize meta instructions (like rotates and div/rem pairs) for
718 targets that support these meta operations. This makes the resultant code
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]719 more efficient and the 'select instructions from DAG' phase (below) simpler.
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]720</li>
721<li><a href="#selectiondag_legalize">Legalize SelectionDAG</a> - This stage
722 converts the illegal SelectionDAG to a legal SelectionDAG, by eliminating
723 unsupported operations and data types.</li>
724<li><a href="#selectiondag_optimize">Optimize SelectionDAG (#2)</a> - This
725 second run of the SelectionDAG optimized the newly legalized DAG, to
726 eliminate inefficiencies introduced by legalization.</li>
727<li><a href="#selectiondag_select">Select instructions from DAG</a> - Finally,
728 the target instruction selector matches the DAG operations to target
729 instructions, emitting them and building the MachineFunction being
730 compiled.</li>
731</ol>
732
733<p>After all of these steps are complete, the SelectionDAG is destroyed and the
734rest of the code generation passes are run.</p>
735
736</div>
737
738<!-- _______________________________________________________________________ -->
739<div class="doc_subsubsection">
740 <a name="selectiondag_build">Initial SelectionDAG Construction</a>
741</div>
742
743<div class="doc_text">
744
745<p>
746The initial SelectionDAG is naively peephole expanded from the LLVM input by
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]747the <tt>SelectionDAGLowering</tt> class in the SelectionDAGISel.cpp file. The
748intent of this pass is to expose as much low-level, target-specific details
749to the SelectionDAG as possible. This pass is mostly hard-coded (e.g. an LLVM
750add turns into an SDNode add while a geteelementptr is expanded into the obvious
751arithmetic). This pass requires target-specific hooks to lower calls and
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]752returns, varargs, etc. For these features, the TargetLowering interface is
753used.
754</p>
755
756</div>
757
758<!-- _______________________________________________________________________ -->
759<div class="doc_subsubsection">
760 <a name="selectiondag_legalize">SelectionDAG Legalize Phase</a>
761</div>
762
763<div class="doc_text">
764
765<p>The Legalize phase is in charge of converting a DAG to only use the types and
766operations that are natively supported by the target. This involves two major
767tasks:</p>
768
769<ol>
770<li><p>Convert values of unsupported types to values of supported types.</p>
771 <p>There are two main ways of doing this: promoting a small type to a larger
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]772 type (e.g. f32 -> f64, or i16 -> i32), and demoting larg integer types
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]773 to smaller ones (e.g. implementing i64 with i32 operations where
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]774 possible). Type conversions can insert sign and zero extensions as
775 needed to make sure that the final code has the same behavior as the
776 input.</p>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]777</li>
778
779<li><p>Eliminate operations that are not supported by the target in a supported
780 type.</p>
781 <p>Targets often have wierd constraints, such as not supporting every
782 operation on every supported datatype (e.g. X86 does not support byte
783 conditional moves). Legalize takes care of either open-coding another
784 sequence of operations to emulate the operation (this is known as
785 expansion), promoting to a larger type that supports the operation
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]786 (promotion), or using a target-specific hook to implement the
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]787 legalization.</p>
788</li>
789</ol>
790
791<p>
792Instead of using a Legalize pass, we could require that every target-specific
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]793<a href="#selectiondag_optimize">selector</a> supports and expands every
794operator and type even if they are not supported and may require many
795instructions to implement (in fact, this is the approach taken by the
796"simple" selectors). However, using a Legalize pass allows all of the
797cannonicalization patterns to be shared across targets which makes it very
798easy to optimize the cannonicalized code because it is still in the form of
799a DAG.
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]800</p>
801
802</div>
803
804<!-- _______________________________________________________________________ -->
805<div class="doc_subsubsection">
806 <a name="selectiondag_optimize">SelectionDAG Optimization Phase</a>
807</div>
808
809<div class="doc_text">
810
811<p>
812The SelectionDAG optimization phase is run twice for code generation: once
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]813immediately after the DAG is built and once after legalization. The first run
814of the pass allows the initial code to be cleaned up (e.g. performing
815optimizations that depend on knowing that the operators have restricted type
816inputs). The second run of the pass cleans up the messy code generated by the
817Legalize pass, allowing Legalize to be very simple since it can ignore many
818special cases.
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]819</p>
820
821<p>
822One important class of optimizations that this pass will do in the future is
823optimizing inserted sign and zero extension instructions. Here are some good
824papers on the subject:</p>
825
826<p>
827"<a href="http://www.eecs.harvard.edu/~nr/pubs/widen-abstract.html">Widening
828integer arithmetic</a>"<br>
829Kevin Redwine and Norman Ramsey<br>
830International Conference on Compiler Construction (CC) 2004
831</p>
832
833
834<p>
835 "<a href="http://portal.acm.org/citation.cfm?doid=512529.512552">Effective
836 sign extension elimination</a>"<br>
837 Motohiro Kawahito, Hideaki Komatsu, and Toshio Nakatani<br>
838 Proceedings of the ACM SIGPLAN 2002 Conference on Programming Language Design
839 and Implementation.
840</p>
841
842</div>
843
844<!-- _______________________________________________________________________ -->
845<div class="doc_subsubsection">
846 <a name="selectiondag_select">SelectionDAG Select Phase</a>
847</div>
848
849<div class="doc_text">
850
851<p>The Select phase is the bulk of the target-specific code for instruction
852selection. This phase takes a legal SelectionDAG as input, and does simple
853pattern matching on the DAG to generate code. In time, the Select phase will
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]854be automatically generated from the target's InstrInfo.td file, which is why we
855want to make the Select phase as simple and mechanical as possible.</p>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]856
857</div>
858
859<!-- _______________________________________________________________________ -->
860<div class="doc_subsubsection">
861 <a name="selectiondag_future">Future directions for the SelectionDAG</a>
862</div>
863
864<div class="doc_text">
865
866<ol>
867<li>Optional whole-function selection.</li>
868<li>Select is a graph translation phase.</li>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]869<li>Place the machine instructions resulting from Select according to register
870pressure or a schedule.</li>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]871<li>DAG Scheduling.</li>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]872<li>Auto-generate the Select phase from the target description (*.td) files.
873</li>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]874</ol>
875
876</div>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]877
878<!-- ======================================================================= -->
879<div class="doc_subsection">
880 <a name="ssamco">SSA-based Machine Code Optimizations</a>
881</div>
882<div class="doc_text"><p>To Be Written</p></div>
883<!-- ======================================================================= -->
884<div class="doc_subsection">
885 <a name="regalloc">Register Allocation</a>
886</div>
887<div class="doc_text"><p>To Be Written</p></div>
888<!-- ======================================================================= -->
889<div class="doc_subsection">
890 <a name="proepicode">Prolog/Epilog Code Insertion</a>
891</div>
892<div class="doc_text"><p>To Be Written</p></div>
893<!-- ======================================================================= -->
894<div class="doc_subsection">
895 <a name="latemco">Late Machine Code Optimizations</a>
896</div>
897<div class="doc_text"><p>To Be Written</p></div>
898<!-- ======================================================================= -->
899<div class="doc_subsection">
900 <a name="codemission">Code Emission</a>
901</div>
Chris Lattneraa5bcb52005-01-28 17:22:53 +0000[diff] [blame]902
903<!-- *********************************************************************** -->
904<div class="doc_section">
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]905 <a name="targetimpls">Target description implementations</a>
906</div>
907<!-- *********************************************************************** -->
908
909<div class="doc_text">
910
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]911<p>This section of the document explains features or design decisions that
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]912are specific to the code generator for a particular target.</p>
913
914</div>
915
916
917<!-- ======================================================================= -->
918<div class="doc_subsection">
919 <a name="x86">The X86 backend</a>
920</div>
921
922<div class="doc_text">
923
924<p>
925The X86 code generator lives in the <tt>lib/Target/X86</tt> directory. This
926code generator currently targets a generic P6-like processor. As such, it
927produces a few P6-and-above instructions (like conditional moves), but it does
928not 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]929will have sub-target support added for specific processor families and
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]930implementations.</p>
931
932</div>
933
934<!-- _______________________________________________________________________ -->
935<div class="doc_subsubsection">
936 <a name="x86_memory">Representing X86 addressing modes in MachineInstrs</a>
937</div>
938
939<div class="doc_text">
940
Misha Brukman600df452005-02-17 22:22:24 +0000[diff] [blame]941<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]942forming memory addresses of the following expression directly in integer
943instructions (which use ModR/M addressing):</p>
944
945<pre>
946 Base+[1,2,4,8]*IndexReg+Disp32
947</pre>
948
Misha Brukman600df452005-02-17 22:22:24 +0000[diff] [blame]949<p>In order to represent this, LLVM tracks no less than 4 operands for each
950memory operand of this form. This means that the "load" form of 'mov' has the
951following <tt>MachineOperand</tt>s in this order:</p>
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]952
953<pre>
954Index: 0 | 1 2 3 4
955Meaning: DestReg, | BaseReg, Scale, IndexReg, Displacement
956OperandTy: VirtReg, | VirtReg, UnsImm, VirtReg, SignExtImm
957</pre>
958
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]959<p>Stores, and all other instructions, treat the four memory operands in the
960same way, in the same order.</p>
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]961
962</div>
963
964<!-- _______________________________________________________________________ -->
965<div class="doc_subsubsection">
966 <a name="x86_names">Instruction naming</a>
967</div>
968
969<div class="doc_text">
970
971<p>
Reid Spencerad1f0cd2005-04-24 20:56:18 +0000[diff] [blame^]972An instruction name consists of the base name, a default operand size, and a
973a character per operand with an optional special size. For example:</p>
Chris Lattnerec94f802004-06-04 00:16:02 +0000[diff] [blame]974
975<p>
976<tt>ADD8rr</tt> -&gt; add, 8-bit register, 8-bit register<br>
977<tt>IMUL16rmi</tt> -&gt; imul, 16-bit register, 16-bit memory, 16-bit immediate<br>
978<tt>IMUL16rmi8</tt> -&gt; imul, 16-bit register, 16-bit memory, 8-bit immediate<br>
979<tt>MOVSX32rm16</tt> -&gt; movsx, 32-bit register, 16-bit memory
980</p>
981
982</div>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]983
984<!-- *********************************************************************** -->
985<hr>
986<address>
987 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
988 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
989 <a href="http://validator.w3.org/check/referer"><img
990 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
991
992 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
993 <a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a><br>
994 Last modified: $Date$
995</address>
996
997</body>
998</html>