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