Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / f3709d6c54a8bf29ad248c6ba9fb714e3e0f2843 / . / docs / CodeGenerator.html
blob: 2145449f0a0a83f6c1e61f7ca54271a90dd8a5d2 [file] [log] [blame]
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]1<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
3<html>
4<head>
5 <title>The LLVM Target-Independent Code Generator</title>
6 <link rel="stylesheet" href="llvm.css" type="text/css">
7</head>
8<body>
9
10<div class="doc_title">
11 The LLVM Target-Independent Code Generator
12</div>
13
14<ol>
15 <li><a href="#introduction">Introduction</a>
16 <ul>
17 <li><a href="#required">Required components in the code generator</a></li>
18 <li><a href="#high-level-design">The high-level design of the code generator</a></li>
19 <li><a href="#tablegen">Using TableGen for target description</a></li>
20 </ul>
21 </li>
22 <li><a href="#targetdesc">Target description classes</a>
23 <ul>
24 <li><a href="#targetmachine">The <tt>TargetMachine</tt> class</a></li>
25 <li><a href="#targetdata">The <tt>TargetData</tt> class</a></li>
26 <li><a href="#mregisterinfo">The <tt>MRegisterInfo</tt> class</a></li>
27 <li><a href="#targetinstrinfo">The <tt>TargetInstrInfo</tt> class</a></li>
28 <li><a href="#targetframeinfo">The <tt>TargetFrameInfo</tt> class</a></li>
29 <li><a href="#targetjitinfo">The <tt>TargetJITInfo</tt> class</a></li>
30 </ul>
31 </li>
32 <li><a href="#codegendesc">Machine code description classes</a>
33 </li>
34 <li><a href="#codegenalgs">Target-independent code generation algorithms</a>
35 </li>
36 <li><a href="#targetimpls">Target description implementations</a>
37 <ul>
38 <li><a href="#x86">The X86 backend</a></li>
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]39 </ul>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]40 </li>
41
42</ol>
43
44<div class="doc_author">
45 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a></p>
46</div>
47
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]48<div class="doc_warning">
49 <p>Warning: This is a work in progress.</p>
50</div>
51
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]52<!-- *********************************************************************** -->
53<div class="doc_section">
54 <a name="introduction">Introduction</a>
55</div>
56<!-- *********************************************************************** -->
57
58<div class="doc_text">
59
60<p>The LLVM target-independent code generator is a framework that provides a
61suite of reusable components for translating the LLVM internal representation to
62the machine code for a specified target -- either in assembly form (suitable for
63a static compiler) or in binary machine code format (usable for a JIT compiler).
64The LLVM target-independent code generator consists of four main components:</p>
65
66<ol>
67<li><a href="#targetdesc">Abstract target description</a> interfaces which
68capture improtant properties about various aspects of the machine independently
69of how they will be used. These interfaces are defined in
70<tt>include/llvm/Target/</tt>.</li>
71
72<li>Classes used to represent the <a href="#codegendesc">machine code</a> being
73generator for a target. These classes are intended to be abstract enough to
74represent the machine code for <i>any</i> target machine. These classes are
75defined in <tt>include/llvm/CodeGen/</tt>.</li>
76
77<li><a href="#codegenalgs">Target-independent algorithms</a> used to implement
78various phases of native code generation (register allocation, scheduling, stack
79frame representation, etc). This code lives in <tt>lib/CodeGen/</tt>.</li>
80
81<li><a href="#targetimpls">Implementations of the abstract target description
82interfaces</a> for particular targets. These machine descriptions make use of
83the components provided by LLVM, and can optionally provide custom
84target-specific passes, to build complete code generators for a specific target.
85Target descriptions live in <tt>lib/Target/</tt>.</li>
86
87</ol>
88
89<p>
90Depending on which part of the code generator you are interested in working on,
91different pieces of this will be useful to you. In any case, you should be
92familiar with the <a href="#targetdesc">target description</a> and <a
93href="#codegendesc">machine code representation</a> classes. If you want to add
94a backend for a new target, you will need <a href="#targetimpls">implement the
95targe description</a> classes for your new target and understand the <a
96href="LangRef.html">LLVM code representation</a>. If you are interested in
97implementing a new <a href="#codegenalgs">code generation algorithm</a>, it
98should only depend on the target-description and machine code representation
99classes, ensuring that it is portable.
100</p>
101
102</div>
103
104<!-- ======================================================================= -->
105<div class="doc_subsection">
106 <a name="required">Required components in the code generator</a>
107</div>
108
109<div class="doc_text">
110
111<p>The two pieces of the LLVM code generator are the high-level interface to the
112code generator and the set of reusable components that can be used to build
113target-specific backends. The two most important interfaces (<a
114href="#targetmachine"><tt>TargetMachine</tt></a> and <a
115href="#targetdata"><tt>TargetData</tt></a> classes) are the only ones that are
116required to be defined for a backend to fit into the LLVM system, but the others
117must be defined if the reusable code generator components are going to be
118used.</p>
119
120<p>This design has two important implications. The first is that LLVM can
121support completely non-traditional code generation targets. For example, the C
122backend does not require register allocation, instruction selection, or any of
123the other standard components provided by the system. As such, it only
124implements these two interfaces, and does its own thing. Another example of a
125code generator like this is a (purely hypothetical) backend that converts LLVM
126to the GCC RTL form and uses GCC to emit machine code for a target.</p>
127
128<p>The other implication of this design is that it is possible to design and
129implement radically different code generators in the LLVM system that do not
130make use of any of the built-in components. Doing so is not recommended at all,
131but could be required for radically different targets that do not fit into the
132LLVM machine description model: programmable FPGAs for example.</p>
Chris Lattner900bf8c2004-06-02 07:06:06 +0000[diff] [blame]133
134<p><b>Important Note:</b> For historical reasons, the LLVM SparcV9 code
135generator uses almost entirely different code paths than described in this
136document. For this reason, there are some deprecated interfaces (such as
137<tt>TargetRegInfo</tt> and <tt>TargetSchedInfo</tt>), which are only used by the
138V9 backend and should not be used by any other targets. Also, all code in the
139<tt>lib/Target/SparcV9</tt> directory and subdirectories should be considered
140deprecated, and should not be used as the basis for future code generator work.
Misha Brukmanf3709d62004-06-03 16:55:57 +0000[diff] [blame^]141The SparcV9 backend is slowly being merged into the rest of the
142target-independent code generators, but this is a low-priority process with no
Chris Lattner900bf8c2004-06-02 07:06:06 +0000[diff] [blame]143predictable completion date.</p>
144
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]145</div>
146
147<!-- ======================================================================= -->
148<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]149 <a name="high-level-design">The high-level design of the code generator</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]150</div>
151
152<div class="doc_text">
153
154<p>The LLVM target-indendent code generator is designed to support efficient and
155quality code generation for standard register-based microprocessors. Code
156generation in this model is divided into the following stages:</p>
157
158<ol>
159<li><b>Instruction Selection</b> - Determining a efficient implementation of the
160input LLVM code in the target instruction set. This stage produces the initial
161code for the program in the target instruction set the makes use of virtual
162registers in SSA form and physical registers that represent any required
163register assignments due to target constraints or calling conventions.</li>
164
165<li><b>SSA-based Machine Code Optimizations</b> - This (optional) stage consists
166of a series of machine-code optimizations that operate on the SSA-form produced
167by the instruction selector. Optimizations like modulo-scheduling, normal
168scheduling, or peephole optimization work here.</li>
169
170<li><b>Register Allocation</b> - The target code is transformed from an infinite
171virtual register file in SSA form to the concrete register file used by the
172target. This phase introduces spill code and eliminates all virtual register
173references from the program.</li>
174
175<li><b>Prolog/Epilog Code Insertion</b> - Once the machine code has been
176generated for the function and the amount of stack space required is known (used
177for LLVM alloca's and spill slots), the prolog and epilog code for the function
178can be inserted and "abstract stack location references" can be eliminated.
179This stage is responsible for implementing optimizations like frame-pointer
180elimination and stack packing.</li>
181
182<li><b>Late Machine Code Optimizations</b> - Optimizations that operate on
183"final" machine code can go here, such as spill code scheduling and peephole
184optimizations.</li>
185
186<li><b>Code Emission</b> - The final stage actually outputs the machine code for
187the current function, either in the target assembler format or in machine
188code.</li>
189
190</ol>
191
192<p>
193The code generator is based on the assumption that the instruction selector will
194use an optimal pattern matching selector to create high-quality sequences of
195native code. Alternative code generator designs based on pattern expansion and
196aggressive iterative peephole optimization are much slower. This design is
197designed to permit efficient compilation (important for JIT environments) and
198aggressive optimization (used when generate code offline) by allowing components
199of varying levels of sophisication to be used for any step of compilation.</p>
200
201<p>
202In addition to these stages, target implementations can insert arbitrary
203target-specific passes into the flow. For example, the X86 target uses a
204special pass to handle the 80x87 floating point stack architecture. Other
205targets with unusual requirements can be supported with custom passes as needed.
206</p>
207
208</div>
209
210
211<!-- ======================================================================= -->
212<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]213 <a name="tablegen">Using TableGen for target description</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]214</div>
215
216<div class="doc_text">
217
Chris Lattner5489e932004-06-01 18:35:00 +0000[diff] [blame]218<p>The target description classes require a detailed description of the target
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]219architecture. These target descriptions often have a large amount of common
220information (e.g., an add instruction is almost identical to a sub instruction).
221In order to allow the maximum amount of commonality to be factored out, the LLVM
222code generator uses the <a href="TableGenFundamentals.html">TableGen</a> tool to
Chris Lattner5489e932004-06-01 18:35:00 +0000[diff] [blame]223describe big chunks of the target machine, which allows the use of domain- and
224target-specific abstractions to reduce the amount of repetition.
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]225</p>
226
227</div>
228
229<!-- *********************************************************************** -->
230<div class="doc_section">
231 <a name="targetdesc">Target description classes</a>
232</div>
233<!-- *********************************************************************** -->
234
235<div class="doc_text">
236
237<p>The LLVM target description classes (which are located in the
238<tt>include/llvm/Target</tt> directory) provide an abstract description of the
239target machine, independent of any particular client. These classes are
240designed to capture the <i>abstract</i> properties of the target (such as what
241instruction and registers it has), and do not incorporate any particular pieces
242of code generation algorithms (these interfaces do not take interference graphs
243as inputs or other algorithm-specific data structures).</p>
244
245<p>All of the target description classes (except the <tt><a
246href="#targetdata">TargetData</a></tt> class) are designed to be subclassed by
247the concrete target implementation, and have virtual methods implemented. To
248get to these implementations, <tt><a
249href="#targetmachine">TargetMachine</a></tt> class provides accessors that
250should be implemented by the target.</p>
251
252</div>
253
254<!-- ======================================================================= -->
255<div class="doc_subsection">
256 <a name="targetmachine">The <tt>TargetMachine</tt> class</a>
257</div>
258
259<div class="doc_text">
260
261<p>The <tt>TargetMachine</tt> class provides virtual methods that are used to
262access the target-specific implementations of the various target description
263classes (with the <tt>getInstrInfo</tt>, <tt>getRegisterInfo</tt>,
264<tt>getFrameInfo</tt>, ... methods). This class is designed to be subclassed by
265a concrete target implementation (e.g., <tt>X86TargetMachine</tt>) which
266implements the various virtual methods. The only required target description
267class is the <a href="#targetdata"><tt>TargetData</tt></a> class, but if the
268code generator components are to be used, the other interfaces should be
269implemented as well.</p>
270
271</div>
272
273
274<!-- ======================================================================= -->
275<div class="doc_subsection">
276 <a name="targetdata">The <tt>TargetData</tt> class</a>
277</div>
278
279<div class="doc_text">
280
281<p>The <tt>TargetData</tt> class is the only required target description class,
282and it is the only class that is not extensible (it cannot be derived from). It
283specifies information about how the target lays out memory for structures, the
284alignment requirements for various data types, the size of pointers in the
285target, and whether the target is little- or big-endian.</p>
286
287</div>
288
289
290<!-- ======================================================================= -->
291<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]292 <a name="mregisterinfo">The <tt>MRegisterInfo</tt> class</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]293</div>
294
295<div class="doc_text">
296
297<p>The <tt>MRegisterInfo</tt> class (which will eventually be renamed to
298<tt>TargetRegisterInfo</tt>) is used to describe the register file of the
299target and any interactions between the registers.</p>
300
301<p>Registers in the code generator are represented in the code generator by
302unsigned numbers. Physical registers (those that actually exist in the target
303description) are unique small numbers, and virtual registers are generally
304large.</p>
305
306<p>Each register in the processor description has an associated
307<tt>MRegisterDesc</tt> entry, which provides a textual name for the register
308(used for assembly output and debugging dumps), a set of aliases (used to
309indicate that one register overlaps with another), and some flag bits.
310</p>
311
312<p>In addition to the per-register description, the <tt>MRegisterInfo</tt> class
313exposes a set of processor specific register classes (instances of the
314<tt>TargetRegisterClass</tt> class). Each register class contains sets of
315registers that have the same properties (for example, they are all 32-bit
316integer registers). Each SSA virtual register created by the instruction
317selector has an associated register class. When the register allocator runs, it
318replaces virtual registers with a physical register in the set.</p>
319
320<p>
321The target-specific implementations of these classes is auto-generated from a <a
322href="TableGenFundamentals.html">TableGen</a> description of the register file.
323</p>
324
325</div>
326
327<!-- ======================================================================= -->
328<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]329 <a name="targetinstrinfo">The <tt>TargetInstrInfo</tt> class</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]330</div>
331
332<!-- ======================================================================= -->
333<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]334 <a name="targetframeinfo">The <tt>TargetFrameInfo</tt> class</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]335</div>
336
337<!-- ======================================================================= -->
338<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame]339 <a name="targetjitinfo">The <tt>TargetJITInfo</tt> class</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]340</div>
341
342<!-- *********************************************************************** -->
343<div class="doc_section">
344 <a name="codegendesc">Machine code description classes</a>
345</div>
346<!-- *********************************************************************** -->
347
348
349
350<!-- *********************************************************************** -->
351<hr>
352<address>
353 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
354 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
355 <a href="http://validator.w3.org/check/referer"><img
356 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
357
358 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
359 <a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a><br>
360 Last modified: $Date$
361</address>
362
363</body>
364</html>