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