blob: 70f0ec27492161798c9789a6bbf479411875d9bf [file] [log] [blame]
Chris Lattner3a1716d2007-05-12 05:37:42 +00001<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
2 "http://www.w3.org/TR/html4/strict.dtd">
Reid Spencer2c1ce4f2007-01-20 23:21:08 +00003<html>
4<head>
5 <meta http-equiv="Content-Type" content="text/html; charset=utf-8">
6 <title>LLVM Bitcode File Format</title>
7 <link rel="stylesheet" href="llvm.css" type="text/css">
Reid Spencer2c1ce4f2007-01-20 23:21:08 +00008</head>
9<body>
10<div class="doc_title"> LLVM Bitcode File Format </div>
11<ol>
12 <li><a href="#abstract">Abstract</a></li>
Chris Lattnere9ef4572007-05-12 03:23:40 +000013 <li><a href="#overview">Overview</a></li>
14 <li><a href="#bitstream">Bitstream Format</a>
15 <ol>
16 <li><a href="#magic">Magic Numbers</a></li>
Chris Lattner3a1716d2007-05-12 05:37:42 +000017 <li><a href="#primitives">Primitives</a></li>
18 <li><a href="#abbrevid">Abbreviation IDs</a></li>
19 <li><a href="#blocks">Blocks</a></li>
20 <li><a href="#datarecord">Data Records</a></li>
Chris Lattnerdaeb63c2007-05-12 07:49:15 +000021 <li><a href="#abbreviations">Abbreviations</a></li>
Chris Lattner7300af52007-05-13 00:59:52 +000022 <li><a href="#stdblocks">Standard Blocks</a></li>
Chris Lattnere9ef4572007-05-12 03:23:40 +000023 </ol>
24 </li>
25 <li><a href="#llvmir">LLVM IR Encoding</a></li>
Reid Spencer2c1ce4f2007-01-20 23:21:08 +000026</ol>
27<div class="doc_author">
Chris Lattnere9ef4572007-05-12 03:23:40 +000028 <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>.
Reid Spencer2c1ce4f2007-01-20 23:21:08 +000029</p>
30</div>
Chris Lattnere9ef4572007-05-12 03:23:40 +000031
Reid Spencer2c1ce4f2007-01-20 23:21:08 +000032<!-- *********************************************************************** -->
Chris Lattnere9ef4572007-05-12 03:23:40 +000033<div class="doc_section"> <a name="abstract">Abstract</a></div>
Reid Spencer2c1ce4f2007-01-20 23:21:08 +000034<!-- *********************************************************************** -->
Chris Lattnere9ef4572007-05-12 03:23:40 +000035
Reid Spencer2c1ce4f2007-01-20 23:21:08 +000036<div class="doc_text">
Chris Lattnere9ef4572007-05-12 03:23:40 +000037
38<p>This document describes the LLVM bitstream file format and the encoding of
39the LLVM IR into it.</p>
40
Reid Spencer2c1ce4f2007-01-20 23:21:08 +000041</div>
Chris Lattnere9ef4572007-05-12 03:23:40 +000042
Reid Spencer2c1ce4f2007-01-20 23:21:08 +000043<!-- *********************************************************************** -->
Chris Lattnere9ef4572007-05-12 03:23:40 +000044<div class="doc_section"> <a name="overview">Overview</a></div>
Reid Spencer2c1ce4f2007-01-20 23:21:08 +000045<!-- *********************************************************************** -->
Chris Lattnere9ef4572007-05-12 03:23:40 +000046
Reid Spencer2c1ce4f2007-01-20 23:21:08 +000047<div class="doc_text">
Chris Lattnere9ef4572007-05-12 03:23:40 +000048
49<p>
50What is commonly known as the LLVM bitcode file format (also, sometimes
51anachronistically known as bytecode) is actually two things: a <a
52href="#bitstream">bitstream container format</a>
53and an <a href="#llvmir">encoding of LLVM IR</a> into the container format.</p>
54
55<p>
Reid Spencer58d05472007-05-12 08:01:52 +000056The bitstream format is an abstract encoding of structured data, very
Chris Lattnere9ef4572007-05-12 03:23:40 +000057similar to XML in some ways. Like XML, bitstream files contain tags, and nested
58structures, and you can parse the file without having to understand the tags.
59Unlike XML, the bitstream format is a binary encoding, and unlike XML it
60provides a mechanism for the file to self-describe "abbreviations", which are
61effectively size optimizations for the content.</p>
62
63<p>This document first describes the LLVM bitstream format, then describes the
64record structure used by LLVM IR files.
65</p>
66
Reid Spencer2c1ce4f2007-01-20 23:21:08 +000067</div>
Chris Lattnere9ef4572007-05-12 03:23:40 +000068
69<!-- *********************************************************************** -->
70<div class="doc_section"> <a name="bitstream">Bitstream Format</a></div>
71<!-- *********************************************************************** -->
72
73<div class="doc_text">
74
75<p>
76The bitstream format is literally a stream of bits, with a very simple
77structure. This structure consists of the following concepts:
78</p>
79
80<ul>
Chris Lattner3a1716d2007-05-12 05:37:42 +000081<li>A "<a href="#magic">magic number</a>" that identifies the contents of
82 the stream.</li>
83<li>Encoding <a href="#primitives">primitives</a> like variable bit-rate
84 integers.</li>
85<li><a href="#blocks">Blocks</a>, which define nested content.</li>
86<li><a href="#datarecord">Data Records</a>, which describe entities within the
87 file.</li>
Chris Lattnere9ef4572007-05-12 03:23:40 +000088<li>Abbreviations, which specify compression optimizations for the file.</li>
89</ul>
90
91<p>Note that the <a
92href="CommandGuide/html/llvm-bcanalyzer.html">llvm-bcanalyzer</a> tool can be
93used to dump and inspect arbitrary bitstreams, which is very useful for
94understanding the encoding.</p>
95
96</div>
97
98<!-- ======================================================================= -->
99<div class="doc_subsection"><a name="magic">Magic Numbers</a>
100</div>
101
102<div class="doc_text">
103
Chris Lattner3a1716d2007-05-12 05:37:42 +0000104<p>The first four bytes of the stream identify the encoding of the file. This
105is used by a reader to know what is contained in the file.</p>
Chris Lattnere9ef4572007-05-12 03:23:40 +0000106
107</div>
108
Chris Lattner3a1716d2007-05-12 05:37:42 +0000109<!-- ======================================================================= -->
110<div class="doc_subsection"><a name="primitives">Primitives</a>
111</div>
Chris Lattnere9ef4572007-05-12 03:23:40 +0000112
113<div class="doc_text">
114
Chris Lattner3a1716d2007-05-12 05:37:42 +0000115<p>
116A bitstream literally consists of a stream of bits. This stream is made up of a
117number of primitive values that encode a stream of integer values. These
118integers are are encoded in two ways: either as <a href="#fixedwidth">Fixed
119Width Integers</a> or as <a href="#variablewidth">Variable Width
120Integers</a>.
Chris Lattnere9ef4572007-05-12 03:23:40 +0000121</p>
122
123</div>
124
Chris Lattner3a1716d2007-05-12 05:37:42 +0000125<!-- _______________________________________________________________________ -->
126<div class="doc_subsubsection"> <a name="fixedwidth">Fixed Width Integers</a>
127</div>
128
129<div class="doc_text">
130
131<p>Fixed-width integer values have their low bits emitted directly to the file.
132 For example, a 3-bit integer value encodes 1 as 001. Fixed width integers
133 are used when there are a well-known number of options for a field. For
134 example, boolean values are usually encoded with a 1-bit wide integer.
135</p>
136
137</div>
138
139<!-- _______________________________________________________________________ -->
140<div class="doc_subsubsection"> <a name="variablewidth">Variable Width
141Integers</a></div>
142
143<div class="doc_text">
144
145<p>Variable-width integer (VBR) values encode values of arbitrary size,
146optimizing for the case where the values are small. Given a 4-bit VBR field,
147any 3-bit value (0 through 7) is encoded directly, with the high bit set to
148zero. Values larger than N-1 bits emit their bits in a series of N-1 bit
149chunks, where all but the last set the high bit.</p>
150
151<p>For example, the value 27 (0x1B) is encoded as 1011 0011 when emitted as a
152vbr4 value. The first set of four bits indicates the value 3 (011) with a
153continuation piece (indicated by a high bit of 1). The next word indicates a
154value of 24 (011 << 3) with no continuation. The sum (3+24) yields the value
15527.
156</p>
157
158</div>
159
160<!-- _______________________________________________________________________ -->
161<div class="doc_subsubsection"> <a name="char6">6-bit characters</a></div>
162
163<div class="doc_text">
164
165<p>6-bit characters encode common characters into a fixed 6-bit field. They
Chris Lattnerf1d64e92007-05-12 07:50:14 +0000166represent the following characters with the following 6-bit values:</p>
Chris Lattner3a1716d2007-05-12 05:37:42 +0000167
168<ul>
169<li>'a' .. 'z' - 0 .. 25</li>
170<li>'A' .. 'Z' - 26 .. 52</li>
171<li>'0' .. '9' - 53 .. 61</li>
172<li>'.' - 62</li>
173<li>'_' - 63</li>
174</ul>
175
176<p>This encoding is only suitable for encoding characters and strings that
177consist only of the above characters. It is completely incapable of encoding
178characters not in the set.</p>
179
180</div>
181
182<!-- _______________________________________________________________________ -->
183<div class="doc_subsubsection"> <a name="wordalign">Word Alignment</a></div>
184
185<div class="doc_text">
186
187<p>Occasionally, it is useful to emit zero bits until the bitstream is a
188multiple of 32 bits. This ensures that the bit position in the stream can be
189represented as a multiple of 32-bit words.</p>
190
191</div>
192
193
194<!-- ======================================================================= -->
195<div class="doc_subsection"><a name="abbrevid">Abbreviation IDs</a>
196</div>
197
198<div class="doc_text">
199
200<p>
201A bitstream is a sequential series of <a href="#blocks">Blocks</a> and
202<a href="#datarecord">Data Records</a>. Both of these start with an
203abbreviation ID encoded as a fixed-bitwidth field. The width is specified by
204the current block, as described below. The value of the abbreviation ID
205specifies either a builtin ID (which have special meanings, defined below) or
206one of the abbreviation IDs defined by the stream itself.
207</p>
208
209<p>
210The set of builtin abbrev IDs is:
211</p>
212
213<ul>
214<li>0 - <a href="#END_BLOCK">END_BLOCK</a> - This abbrev ID marks the end of the
215 current block.</li>
216<li>1 - <a href="#ENTER_SUBBLOCK">ENTER_SUBBLOCK</a> - This abbrev ID marks the
217 beginning of a new block.</li>
Chris Lattnerdaeb63c2007-05-12 07:49:15 +0000218<li>2 - <a href="#DEFINE_ABBREV">DEFINE_ABBREV</a> - This defines a new
219 abbreviation.</li>
220<li>3 - <a href="#UNABBREV_RECORD">UNABBREV_RECORD</a> - This ID specifies the
221 definition of an unabbreviated record.</li>
Chris Lattner3a1716d2007-05-12 05:37:42 +0000222</ul>
223
Chris Lattnerdaeb63c2007-05-12 07:49:15 +0000224<p>Abbreviation IDs 4 and above are defined by the stream itself, and specify
225an <a href="#abbrev_records">abbreviated record encoding</a>.</p>
Chris Lattner3a1716d2007-05-12 05:37:42 +0000226
227</div>
228
229<!-- ======================================================================= -->
230<div class="doc_subsection"><a name="blocks">Blocks</a>
231</div>
232
233<div class="doc_text">
234
235<p>
236Blocks in a bitstream denote nested regions of the stream, and are identified by
237a content-specific id number (for example, LLVM IR uses an ID of 12 to represent
238function bodies). Nested blocks capture the hierachical structure of the data
239encoded in it, and various properties are associated with blocks as the file is
240parsed. Block definitions allow the reader to efficiently skip blocks
241in constant time if the reader wants a summary of blocks, or if it wants to
242efficiently skip data they do not understand. The LLVM IR reader uses this
243mechanism to skip function bodies, lazily reading them on demand.
244</p>
245
246<p>
247When reading and encoding the stream, several properties are maintained for the
248block. In particular, each block maintains:
249</p>
250
251<ol>
252<li>A current abbrev id width. This value starts at 2, and is set every time a
253 block record is entered. The block entry specifies the abbrev id width for
254 the body of the block.</li>
255
256<li>A set of abbreviations. Abbreviations may be defined within a block, or
257 they may be associated with all blocks of a particular ID.
258</li>
259</ol>
260
261<p>As sub blocks are entered, these properties are saved and the new sub-block
262has its own set of abbreviations, and its own abbrev id width. When a sub-block
263is popped, the saved values are restored.</p>
264
265</div>
266
267<!-- _______________________________________________________________________ -->
268<div class="doc_subsubsection"> <a name="ENTER_SUBBLOCK">ENTER_SUBBLOCK
269Encoding</a></div>
270
271<div class="doc_text">
272
273<p><tt>[ENTER_SUBBLOCK, blockid<sub>vbr8</sub>, newabbrevlen<sub>vbr4</sub>,
274 &lt;align32bits&gt;, blocklen<sub>32</sub>]</tt></p>
275
276<p>
277The ENTER_SUBBLOCK abbreviation ID specifies the start of a new block record.
278The <tt>blockid</tt> value is encoded as a 8-bit VBR identifier, and indicates
279the type of block being entered (which is application specific). The
280<tt>newabbrevlen</tt> value is a 4-bit VBR which specifies the
281abbrev id width for the sub-block. The <tt>blocklen</tt> is a 32-bit aligned
282value that specifies the size of the subblock, in 32-bit words. This value
283allows the reader to skip over the entire block in one jump.
284</p>
285
286</div>
287
288<!-- _______________________________________________________________________ -->
289<div class="doc_subsubsection"> <a name="END_BLOCK">END_BLOCK
290Encoding</a></div>
291
292<div class="doc_text">
293
294<p><tt>[END_BLOCK, &lt;align32bits&gt;]</tt></p>
295
296<p>
297The END_BLOCK abbreviation ID specifies the end of the current block record.
298Its end is aligned to 32-bits to ensure that the size of the block is an even
299multiple of 32-bits.</p>
300
301</div>
302
303
304
305<!-- ======================================================================= -->
306<div class="doc_subsection"><a name="datarecord">Data Records</a>
307</div>
308
309<div class="doc_text">
Chris Lattnerdaeb63c2007-05-12 07:49:15 +0000310<p>
311Data records consist of a record code and a number of (up to) 64-bit integer
312values. The interpretation of the code and values is application specific and
313there are multiple different ways to encode a record (with an unabbrev record
314or with an abbreviation). In the LLVM IR format, for example, there is a record
315which encodes the target triple of a module. The code is MODULE_CODE_TRIPLE,
316and the values of the record are the ascii codes for the characters in the
317string.</p>
318
319</div>
320
321<!-- _______________________________________________________________________ -->
322<div class="doc_subsubsection"> <a name="UNABBREV_RECORD">UNABBREV_RECORD
323Encoding</a></div>
324
325<div class="doc_text">
326
327<p><tt>[UNABBREV_RECORD, code<sub>vbr6</sub>, numops<sub>vbr6</sub>,
328 op0<sub>vbr6</sub>, op1<sub>vbr6</sub>, ...]</tt></p>
329
330<p>An UNABBREV_RECORD provides a default fallback encoding, which is both
331completely general and also extremely inefficient. It can describe an arbitrary
332record, by emitting the code and operands as vbrs.</p>
333
334<p>For example, emitting an LLVM IR target triple as an unabbreviated record
335requires emitting the UNABBREV_RECORD abbrevid, a vbr6 for the
336MODULE_CODE_TRIPLE code, a vbr6 for the length of the string (which is equal to
337the number of operands), and a vbr6 for each character. Since there are no
338letters with value less than 32, each letter would need to be emitted as at
339least a two-part VBR, which means that each letter would require at least 12
340bits. This is not an efficient encoding, but it is fully general.</p>
341
342</div>
343
344<!-- _______________________________________________________________________ -->
345<div class="doc_subsubsection"> <a name="abbrev_records">Abbreviated Record
346Encoding</a></div>
347
348<div class="doc_text">
349
350<p><tt>[&lt;abbrevid&gt;, fields...]</tt></p>
351
352<p>An abbreviated record is a abbreviation id followed by a set of fields that
353are encoded according to the <a href="#abbreviations">abbreviation
354definition</a>. This allows records to be encoded significantly more densely
355than records encoded with the <a href="#UNABBREV_RECORD">UNABBREV_RECORD</a>
356type, and allows the abbreviation types to be specified in the stream itself,
357which allows the files to be completely self describing. The actual encoding
358of abbreviations is defined below.
359</p>
360
361</div>
362
363<!-- ======================================================================= -->
364<div class="doc_subsection"><a name="abbreviations">Abbreviations</a>
365</div>
366
367<div class="doc_text">
368<p>
369Abbreviations are an important form of compression for bitstreams. The idea is
370to specify a dense encoding for a class of records once, then use that encoding
371to emit many records. It takes space to emit the encoding into the file, but
372the space is recouped (hopefully plus some) when the records that use it are
373emitted.
374</p>
Chris Lattner3a1716d2007-05-12 05:37:42 +0000375
376<p>
Chris Lattnerdaeb63c2007-05-12 07:49:15 +0000377Abbreviations can be determined dynamically per client, per file. Since the
378abbreviations are stored in the bitstream itself, different streams of the same
379format can contain different sets of abbreviations if the specific stream does
380not need it. As a concrete example, LLVM IR files usually emit an abbreviation
381for binary operators. If a specific LLVM module contained no or few binary
382operators, the abbreviation does not need to be emitted.
Chris Lattner3a1716d2007-05-12 05:37:42 +0000383</p>
Chris Lattnerdaeb63c2007-05-12 07:49:15 +0000384</div>
385
386<!-- _______________________________________________________________________ -->
387<div class="doc_subsubsection"><a name="DEFINE_ABBREV">DEFINE_ABBREV
388 Encoding</a></div>
389
390<div class="doc_text">
391
392<p><tt>[DEFINE_ABBREV, numabbrevops<sub>vbr5</sub>, abbrevop0, abbrevop1,
393 ...]</tt></p>
394
395<p>An abbreviation definition consists of the DEFINE_ABBREV abbrevid followed
396by a VBR that specifies the number of abbrev operands, then the abbrev
397operands themselves. Abbreviation operands come in three forms. They all start
398with a single bit that indicates whether the abbrev operand is a literal operand
399(when the bit is 1) or an encoding operand (when the bit is 0).</p>
400
401<ol>
402<li>Literal operands - <tt>[1<sub>1</sub>, litvalue<sub>vbr8</sub>]</tt> -
403Literal operands specify that the value in the result
404is always a single specific value. This specific value is emitted as a vbr8
405after the bit indicating that it is a literal operand.</li>
406<li>Encoding info without data - <tt>[0<sub>1</sub>, encoding<sub>3</sub>]</tt>
Chris Lattner7300af52007-05-13 00:59:52 +0000407 - Operand encodings that do not have extra data are just emitted as their code.
Chris Lattnerdaeb63c2007-05-12 07:49:15 +0000408</li>
409<li>Encoding info with data - <tt>[0<sub>1</sub>, encoding<sub>3</sub>,
Chris Lattner7300af52007-05-13 00:59:52 +0000410value<sub>vbr5</sub>]</tt> - Operand encodings that do have extra data are
411emitted as their code, followed by the extra data.
Chris Lattnerdaeb63c2007-05-12 07:49:15 +0000412</li>
413</ol>
Chris Lattner3a1716d2007-05-12 05:37:42 +0000414
Chris Lattner7300af52007-05-13 00:59:52 +0000415<p>The possible operand encodings are:</p>
416
417<ul>
418<li>1 - Fixed - The field should be emitted as a <a
419 href="#fixedwidth">fixed-width value</a>, whose width
420 is specified by the encoding operand.</li>
421<li>2 - VBR - The field should be emitted as a <a
422 href="#variablewidth">variable-width value</a>, whose width
423 is specified by the encoding operand.</li>
424<li>3 - Array - This field is an array of values. The element type of the array
425 is specified by the next encoding operand.</li>
426<li>4 - Char6 - This field should be emitted as a <a href="#char6">char6-encoded
427 value</a>.</li>
428</ul>
429
430<p>For example, target triples in LLVM modules are encoded as a record of the
431form <tt>[TRIPLE, 'a', 'b', 'c', 'd']</tt>. Consider if the bitstream emitted
432the following abbrev entry:</p>
433
434<ul>
435<li><tt>[0, Fixed, 4]</tt></li>
436<li><tt>[0, Array]</tt></li>
437<li><tt>[0, Char6]</tt></li>
438</ul>
439
440<p>When emitting a record with this abbreviation, the above entry would be
441emitted as:</p>
442
443<p><tt>[4<sub>abbrevwidth</sub>, 2<sub>4</sub>, 4<sub>vbr6</sub>,
444 0<sub>6</sub>, 1<sub>6</sub>, 2<sub>6</sub>, 3<sub>6</sub>]</tt></p>
445
446<p>These values are:</p>
447
448<ol>
449<li>The first value, 4, is the abbreviation ID for this abbreviation.</li>
450<li>The second value, 2, is the code for TRIPLE in LLVM IR files.</li>
451<li>The third value, 4, is the length of the array.</li>
452<li>The rest of the values are the char6 encoded values for "abcd".</li>
453</ol>
454
455<p>With this abbreviation, the triple is emitted with only 37 bits (assuming a
456abbrev id width of 3). Without the abbreviation, significantly more space would
457be required to emit the target triple. Also, since the TRIPLE value is not
458emitted as a literal in the abbreviation, the abbreviation can also be used for
459any other string value.
460</p>
461
Chris Lattner3a1716d2007-05-12 05:37:42 +0000462</div>
463
Chris Lattner7300af52007-05-13 00:59:52 +0000464<!-- ======================================================================= -->
465<div class="doc_subsection"><a name="stdblocks">Standard Blocks</a>
466</div>
467
468<div class="doc_text">
469
470<p>
471In addition to the basic block structure and record encodings, the bitstream
472also defines specific builtin block types. These block types specify how the
473stream is to be decoded or other metadata. In the future, new standard blocks
474may be added.
475</p>
476
477</div>
478
479<!-- _______________________________________________________________________ -->
480<div class="doc_subsubsection"><a name="BLOCKINFO">#0 - BLOCKINFO
481Block</a></div>
482
483<div class="doc_text">
484
485<p>The BLOCKINFO block allows the description of metadata for other blocks. The
486 currently specified records are:</p>
487
488<ul>
489<li><tt>[SETBID (#1), blockid]</tt></li>
490<li><tt>[DEFINE_ABBREV, ...]</tt></li>
491</ul>
492
493<p>
494The SETBID record indicates which block ID is being described. The standard
495DEFINE_ABBREV record specifies an abbreviation. The abbreviation is associated
496with the record ID, and any records with matching ID automatically get the
497abbreviation.
498</p>
499
500</div>
Chris Lattner3a1716d2007-05-12 05:37:42 +0000501
Chris Lattnere9ef4572007-05-12 03:23:40 +0000502<!-- *********************************************************************** -->
503<div class="doc_section"> <a name="llvmir">LLVM IR Encoding</a></div>
504<!-- *********************************************************************** -->
505
506<div class="doc_text">
507
508<p></p>
509
510</div>
511
512
Reid Spencer2c1ce4f2007-01-20 23:21:08 +0000513<!-- *********************************************************************** -->
514<hr>
515<address> <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
516 src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
517<a href="http://validator.w3.org/check/referer"><img
518 src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
Chris Lattnere9ef4572007-05-12 03:23:40 +0000519 <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
Reid Spencer2c1ce4f2007-01-20 23:21:08 +0000520<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
521Last modified: $Date$
522</address>
523</body>
524</html>