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