Gitiles
Code Review Sign In
gerrit-public.fairphone.software / fp2-dev / platform / external / llvm / 10d6800742cc773bc7578fbd8b5cd516e2563d03 / . / docs / CodeGenerator.html
blob: 8480d34d3a2baebef45832c5a6857adbdbd940a8 [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 Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]133</div>
134
135<!-- ======================================================================= -->
136<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame^]137 <a name="high-level-design">The high-level design of the code generator</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]138</div>
139
140<div class="doc_text">
141
142<p>The LLVM target-indendent code generator is designed to support efficient and
143quality code generation for standard register-based microprocessors. Code
144generation in this model is divided into the following stages:</p>
145
146<ol>
147<li><b>Instruction Selection</b> - Determining a efficient implementation of the
148input LLVM code in the target instruction set. This stage produces the initial
149code for the program in the target instruction set the makes use of virtual
150registers in SSA form and physical registers that represent any required
151register assignments due to target constraints or calling conventions.</li>
152
153<li><b>SSA-based Machine Code Optimizations</b> - This (optional) stage consists
154of a series of machine-code optimizations that operate on the SSA-form produced
155by the instruction selector. Optimizations like modulo-scheduling, normal
156scheduling, or peephole optimization work here.</li>
157
158<li><b>Register Allocation</b> - The target code is transformed from an infinite
159virtual register file in SSA form to the concrete register file used by the
160target. This phase introduces spill code and eliminates all virtual register
161references from the program.</li>
162
163<li><b>Prolog/Epilog Code Insertion</b> - Once the machine code has been
164generated for the function and the amount of stack space required is known (used
165for LLVM alloca's and spill slots), the prolog and epilog code for the function
166can be inserted and "abstract stack location references" can be eliminated.
167This stage is responsible for implementing optimizations like frame-pointer
168elimination and stack packing.</li>
169
170<li><b>Late Machine Code Optimizations</b> - Optimizations that operate on
171"final" machine code can go here, such as spill code scheduling and peephole
172optimizations.</li>
173
174<li><b>Code Emission</b> - The final stage actually outputs the machine code for
175the current function, either in the target assembler format or in machine
176code.</li>
177
178</ol>
179
180<p>
181The code generator is based on the assumption that the instruction selector will
182use an optimal pattern matching selector to create high-quality sequences of
183native code. Alternative code generator designs based on pattern expansion and
184aggressive iterative peephole optimization are much slower. This design is
185designed to permit efficient compilation (important for JIT environments) and
186aggressive optimization (used when generate code offline) by allowing components
187of varying levels of sophisication to be used for any step of compilation.</p>
188
189<p>
190In addition to these stages, target implementations can insert arbitrary
191target-specific passes into the flow. For example, the X86 target uses a
192special pass to handle the 80x87 floating point stack architecture. Other
193targets with unusual requirements can be supported with custom passes as needed.
194</p>
195
196</div>
197
198
199<!-- ======================================================================= -->
200<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame^]201 <a name="tablegen">Using TableGen for target description</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]202</div>
203
204<div class="doc_text">
205
206<p>The target description classes require a detailed descriptions of the target
207architecture. These target descriptions often have a large amount of common
208information (e.g., an add instruction is almost identical to a sub instruction).
209In order to allow the maximum amount of commonality to be factored out, the LLVM
210code generator uses the <a href="TableGenFundamentals.html">TableGen</a> tool to
211allow
212</p>
213
214</div>
215
216<!-- *********************************************************************** -->
217<div class="doc_section">
218 <a name="targetdesc">Target description classes</a>
219</div>
220<!-- *********************************************************************** -->
221
222<div class="doc_text">
223
224<p>The LLVM target description classes (which are located in the
225<tt>include/llvm/Target</tt> directory) provide an abstract description of the
226target machine, independent of any particular client. These classes are
227designed to capture the <i>abstract</i> properties of the target (such as what
228instruction and registers it has), and do not incorporate any particular pieces
229of code generation algorithms (these interfaces do not take interference graphs
230as inputs or other algorithm-specific data structures).</p>
231
232<p>All of the target description classes (except the <tt><a
233href="#targetdata">TargetData</a></tt> class) are designed to be subclassed by
234the concrete target implementation, and have virtual methods implemented. To
235get to these implementations, <tt><a
236href="#targetmachine">TargetMachine</a></tt> class provides accessors that
237should be implemented by the target.</p>
238
239</div>
240
241<!-- ======================================================================= -->
242<div class="doc_subsection">
243 <a name="targetmachine">The <tt>TargetMachine</tt> class</a>
244</div>
245
246<div class="doc_text">
247
248<p>The <tt>TargetMachine</tt> class provides virtual methods that are used to
249access the target-specific implementations of the various target description
250classes (with the <tt>getInstrInfo</tt>, <tt>getRegisterInfo</tt>,
251<tt>getFrameInfo</tt>, ... methods). This class is designed to be subclassed by
252a concrete target implementation (e.g., <tt>X86TargetMachine</tt>) which
253implements the various virtual methods. The only required target description
254class is the <a href="#targetdata"><tt>TargetData</tt></a> class, but if the
255code generator components are to be used, the other interfaces should be
256implemented as well.</p>
257
258</div>
259
260
261<!-- ======================================================================= -->
262<div class="doc_subsection">
263 <a name="targetdata">The <tt>TargetData</tt> class</a>
264</div>
265
266<div class="doc_text">
267
268<p>The <tt>TargetData</tt> class is the only required target description class,
269and it is the only class that is not extensible (it cannot be derived from). It
270specifies information about how the target lays out memory for structures, the
271alignment requirements for various data types, the size of pointers in the
272target, and whether the target is little- or big-endian.</p>
273
274</div>
275
276
277<!-- ======================================================================= -->
278<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame^]279 <a name="mregisterinfo">The <tt>MRegisterInfo</tt> class</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]280</div>
281
282<div class="doc_text">
283
284<p>The <tt>MRegisterInfo</tt> class (which will eventually be renamed to
285<tt>TargetRegisterInfo</tt>) is used to describe the register file of the
286target and any interactions between the registers.</p>
287
288<p>Registers in the code generator are represented in the code generator by
289unsigned numbers. Physical registers (those that actually exist in the target
290description) are unique small numbers, and virtual registers are generally
291large.</p>
292
293<p>Each register in the processor description has an associated
294<tt>MRegisterDesc</tt> entry, which provides a textual name for the register
295(used for assembly output and debugging dumps), a set of aliases (used to
296indicate that one register overlaps with another), and some flag bits.
297</p>
298
299<p>In addition to the per-register description, the <tt>MRegisterInfo</tt> class
300exposes a set of processor specific register classes (instances of the
301<tt>TargetRegisterClass</tt> class). Each register class contains sets of
302registers that have the same properties (for example, they are all 32-bit
303integer registers). Each SSA virtual register created by the instruction
304selector has an associated register class. When the register allocator runs, it
305replaces virtual registers with a physical register in the set.</p>
306
307<p>
308The target-specific implementations of these classes is auto-generated from a <a
309href="TableGenFundamentals.html">TableGen</a> description of the register file.
310</p>
311
312</div>
313
314<!-- ======================================================================= -->
315<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame^]316 <a name="targetinstrinfo">The <tt>TargetInstrInfo</tt> class</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]317</div>
318
319<!-- ======================================================================= -->
320<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame^]321 <a name="targetframeinfo">The <tt>TargetFrameInfo</tt> class</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]322</div>
323
324<!-- ======================================================================= -->
325<div class="doc_subsection">
Chris Lattner10d68002004-06-01 17:18:11 +0000[diff] [blame^]326 <a name="targetjitinfo">The <tt>TargetJITInfo</tt> class</a>
Chris Lattnerce52b7e2004-06-01 06:48:00 +0000[diff] [blame]327</div>
328
329<!-- *********************************************************************** -->
330<div class="doc_section">
331 <a name="codegendesc">Machine code description classes</a>
332</div>
333<!-- *********************************************************************** -->
334
335
336
337<!-- *********************************************************************** -->
338<hr>
339<address>
340 <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
341 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
342 <a href="http://validator.w3.org/check/referer"><img
343 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!" /></a>
344
345 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
346 <a href="http://llvm.cs.uiuc.edu">The LLVM Compiler Infrastructure</a><br>
347 Last modified: $Date$
348</address>
349
350</body>
351</html>