| blob | 15b05230d020712d3ddf43be1ef9e3e169044166 |
3 <html>
4 <head>
8 </head>
9 <body>
11 <ol>
15 <ol>
23 </ol>
24 </li>
26 </li>
28 <ol>
30 </ol>
31 </li>
32 </ol>
36 </p>
37 </div>
39 <!-- *********************************************************************** -->
41 <!-- *********************************************************************** -->
45 <p>This document describes the LLVM bitstream file format and the encoding of
46 the LLVM IR into it.</p>
48 </div>
50 <!-- *********************************************************************** -->
52 <!-- *********************************************************************** -->
56 <p>
57 What is commonly known as the LLVM bitcode file format (also, sometimes
58 anachronistically known as bytecode) is actually two things: a <a
62 <p>
63 The bitstream format is an abstract encoding of structured data, very
64 similar to XML in some ways. Like XML, bitstream files contain tags, and nested
65 structures, and you can parse the file without having to understand the tags.
66 Unlike XML, the bitstream format is a binary encoding, and unlike XML it
67 provides a mechanism for the file to self-describe "abbreviations", which are
68 effectively size optimizations for the content.</p>
72 along with LLVM IR files.</p>
74 <p>This document first describes the LLVM bitstream format, describes the
75 wrapper format, then describes the record structure used by LLVM IR files.
76 </p>
78 </div>
80 <!-- *********************************************************************** -->
82 <!-- *********************************************************************** -->
86 <p>
87 The bitstream format is literally a stream of bits, with a very simple
88 structure. This structure consists of the following concepts:
89 </p>
91 <ul>
93 the stream.</li>
95 integers.</li>
98 file.</li>
100 </ul>
104 used to dump and inspect arbitrary bitstreams, which is very useful for
105 understanding the encoding.</p>
107 </div>
109 <!-- ======================================================================= -->
111 </div>
116 The second two bytes are an application-specific magic number. Generic
117 bitcode tools can look at only the first two bytes to verify the file is
118 bitcode, while application-specific programs will want to look at all four.</p>
120 </div>
122 <!-- ======================================================================= -->
124 </div>
128 <p>
129 A bitstream literally consists of a stream of bits, which are read in order
130 starting with the least significant bit of each byte. The stream is made up of a
131 number of primitive values that encode a stream of unsigned integer values.
132 These
135 Integers</a>.
136 </p>
138 </div>
140 <!-- _______________________________________________________________________ -->
142 </div>
146 <p>Fixed-width integer values have their low bits emitted directly to the file.
148 are used when there are a well-known number of options for a field. For
149 example, boolean values are usually encoded with a 1-bit wide integer.
150 </p>
152 </div>
154 <!-- _______________________________________________________________________ -->
156 Integers</a></div>
160 <p>Variable-width integer (VBR) values encode values of arbitrary size,
161 optimizing for the case where the values are small. Given a 4-bit VBR field,
164 chunks, where all but the last set the high bit.</p>
168 continuation piece (indicated by a high bit of 1). The next word indicates a
170 27.
171 </p>
173 </div>
175 <!-- _______________________________________________________________________ -->
184 <pre>
190 </pre>
191 </div>
193 <p>This encoding is only suitable for encoding characters and strings that
194 consist only of the above characters. It is completely incapable of encoding
195 characters not in the set.</p>
197 </div>
199 <!-- _______________________________________________________________________ -->
204 <p>Occasionally, it is useful to emit zero bits until the bitstream is a
205 multiple of 32 bits. This ensures that the bit position in the stream can be
208 </div>
211 <!-- ======================================================================= -->
213 </div>
217 <p>
220 abbreviation ID encoded as a fixed-bitwidth field. The width is specified by
221 the current block, as described below. The value of the abbreviation ID
222 specifies either a builtin ID (which have special meanings, defined below) or
223 one of the abbreviation IDs defined by the stream itself.
224 </p>
226 <p>
227 The set of builtin abbrev IDs is:
228 </p>
230 <ul>
232 the end of the current block.</li>
234 abbrev ID marks the beginning of a new block.</li>
236 a new abbreviation.</li>
238 specifies the definition of an unabbreviated record.</li>
239 </ul>
244 </div>
246 <!-- ======================================================================= -->
248 </div>
252 <p>
253 Blocks in a bitstream denote nested regions of the stream, and are identified by
254 a content-specific id number (for example, LLVM IR uses an ID of 12 to represent
256 whose meaning is defined by Bitcode; block IDs 8 and greater are
257 application specific. Nested blocks capture the hierachical structure of the data
258 encoded in it, and various properties are associated with blocks as the file is
259 parsed. Block definitions allow the reader to efficiently skip blocks
260 in constant time if the reader wants a summary of blocks, or if it wants to
261 efficiently skip data they do not understand. The LLVM IR reader uses this
262 mechanism to skip function bodies, lazily reading them on demand.
263 </p>
265 <p>
266 When reading and encoding the stream, several properties are maintained for the
267 block. In particular, each block maintains:
268 </p>
270 <ol>
272 block record is entered. The block entry specifies the abbrev id width for
273 the body of the block.</li>
275 <li>A set of abbreviations. Abbreviations may be defined within a block, in
276 which case they are only defined in that block (neither subblocks nor
277 enclosing blocks see the abbreviation). Abbreviations can also be defined
279 they are defined in all blocks that match the ID that the BLOCKINFO block is
280 describing.
281 </li>
282 </ol>
284 <p>
285 As sub blocks are entered, these properties are saved and the new sub-block has
286 its own set of abbreviations, and its own abbrev id width. When a sub-block is
287 popped, the saved values are restored.
288 </p>
290 </div>
292 <!-- _______________________________________________________________________ -->
294 Encoding</a></div>
301 <p>
304 indicates the type of block being entered, which can be
308 that specifies the size of the subblock in 32-bit words. This value allows the
309 reader to skip over the entire block in one jump.
310 </p>
312 </div>
314 <!-- _______________________________________________________________________ -->
316 Encoding</a></div>
322 <p>
324 record. Its end is aligned to 32-bits to ensure that the size of the block is
325 an even multiple of 32-bits.
326 </p>
328 </div>
332 <!-- ======================================================================= -->
334 </div>
337 <p>
338 Data records consist of a record code and a number of (up to) 64-bit integer
339 values. The interpretation of the code and values is application specific and
340 there are multiple different ways to encode a record (with an unabbrev record or
341 with an abbreviation). In the LLVM IR format, for example, there is a record
342 which encodes the target triple of a module. The code is
344 for the characters in the string.
345 </p>
347 </div>
349 <!-- _______________________________________________________________________ -->
351 Encoding</a></div>
358 <p>
360 completely general and extremely inefficient. It can describe an arbitrary
361 record by emitting the code and operands as vbrs.
362 </p>
364 <p>
365 For example, emitting an LLVM IR target triple as an unabbreviated record
368 equal to the number of operands, and a vbr6 for each character. Because there
369 are no letters with values less than 32, each letter would need to be emitted as
370 at least a two-part VBR, which means that each letter would require at least 12
371 bits. This is not an efficient encoding, but it is fully general.
372 </p>
374 </div>
376 <!-- _______________________________________________________________________ -->
378 Encoding</a></div>
384 <p>
385 An abbreviated record is a abbreviation id followed by a set of fields that are
387 This allows records to be encoded significantly more densely than records
389 and allows the abbreviation types to be specified in the stream itself, which
390 allows the files to be completely self describing. The actual encoding of
391 abbreviations is defined below.
392 </p>
394 </div>
396 <!-- ======================================================================= -->
398 </div>
401 <p>
402 Abbreviations are an important form of compression for bitstreams. The idea is
403 to specify a dense encoding for a class of records once, then use that encoding
404 to emit many records. It takes space to emit the encoding into the file, but
405 the space is recouped (hopefully plus some) when the records that use it are
406 emitted.
407 </p>
409 <p>
410 Abbreviations can be determined dynamically per client, per file. Because the
411 abbreviations are stored in the bitstream itself, different streams of the same
412 format can contain different sets of abbreviations if the specific stream does
413 not need it. As a concrete example, LLVM IR files usually emit an abbreviation
414 for binary operators. If a specific LLVM module contained no or few binary
415 operators, the abbreviation does not need to be emitted.
416 </p>
417 </div>
419 <!-- _______________________________________________________________________ -->
421 Encoding</a></div>
426 ...]</tt></p>
428 <p>
430 defined abbreviations in the scope of this block. This definition only exists
431 inside this immediate block — it is not visible in subblocks or enclosing
432 blocks. Abbreviations are implicitly assigned IDs sequentially starting from 4
433 (the first application-defined abbreviation ID). Any abbreviations defined in a
435 abbreviations defined within the block itself. Abbreviated data records
436 reference this ID to indicate what abbreviation they are invoking.
437 </p>
439 <p>
441 followed by a VBR that specifies the number of abbrev operands, then the abbrev
442 operands themselves. Abbreviation operands come in three forms. They all start
443 with a single bit that indicates whether the abbrev operand is a literal operand
445 </p>
447 <ol>
449 — Literal operands specify that the value in the result is always a single
450 specific value. This specific value is emitted as a vbr8 after the bit
451 indicating that it is a literal operand.</li>
454 data are just emitted as their code.
455 </li>
458 emitted as their code, followed by the extra data.
459 </li>
460 </ol>
464 <ol>
465 <li>Fixed: The field should be emitted as
467 the operand's extra data.</li>
468 <li>VBR: The field should be emitted as
470 specified by the operand's extra data.</li>
471 <li>Array: This field is an array of values. The array operand
472 has no extra data, but expects another operand to follow it which indicates
473 the element type of the array. When reading an array in an abbreviated
474 record, the first integer is a vbr6 that indicates the array length,
475 followed by the encoded elements of the array. An array may only occur as
476 the last operand of an abbreviation (except for the one final operand that
477 gives the array's type).</li>
478 <li>Char6: This field should be emitted as
480 extra data.</li>
481 <li>Blob: This field is emitted as a vbr6, followed by padding to a
483 bytes is further followed by tail padding to ensure that its total length is
484 a multiple of 4 bytes. This makes it very efficient for the reader to
485 decode the data without having to make a copy of it: it can use a pointer to
486 the data in the mapped in file and poke directly at it. A blob may only
487 occur as the last operand of an abbreviation.</li>
488 </ol>
490 <p>
491 For example, target triples in LLVM modules are encoded as a record of the
493 the following abbrev entry:
494 </p>
497 <pre>
499 [0, Array]
500 [0, Char6]
501 </pre>
502 </div>
504 <p>
505 When emitting a record with this abbreviation, the above entry would be emitted
506 as:
507 </p>
510 <p>
513 </p>
514 </div>
518 <ol>
522 <li>The rest of the values are the char6 encoded values
524 </ol>
526 <p>
527 With this abbreviation, the triple is emitted with only 37 bits (assuming a
528 abbrev id width of 3). Without the abbreviation, significantly more space would
530 is not emitted as a literal in the abbreviation, the abbreviation can also be
531 used for any other string value.
532 </p>
534 </div>
536 <!-- ======================================================================= -->
538 </div>
542 <p>
543 In addition to the basic block structure and record encodings, the bitstream
544 also defines specific builtin block types. These block types specify how the
545 stream is to be decoded or other metadata. In the future, new standard blocks
547 </p>
549 </div>
551 <!-- _______________________________________________________________________ -->
553 Block</a></div>
557 <p>
559 blocks. The currently specified records are:
560 </p>
563 <pre>
564 [SETBID (#1), blockid]
565 [DEFINE_ABBREV, ...]
566 [BLOCKNAME, ...name...]
567 [SETRECORDNAME, RecordID, ...name...]
568 </pre>
569 </div>
571 <p>
574 block to change which block ID is being described. There must be
576 </p>
578 <p>
580 blocks, but unlike their occurrence in normal blocks, the abbreviation is
585 </p>
588 the record are the bytes for the string name of the block. llvm-bcanalyzer uses
589 this to dump out bitcode files symbolically.</p>
592 first entry is a record ID number and the rest of the elements of the record are
593 the bytes for the string name of the record. llvm-bcanalyzer uses
594 this to dump out bitcode files symbolically.</p>
596 <p>
598 "metadata," the abbreviations they contain are essential for parsing records
599 from the corresponding blocks. It is not safe to skip them.
600 </p>
602 </div>
604 <!-- *********************************************************************** -->
606 <!-- *********************************************************************** -->
610 <p>
611 Bitcode files for LLVM IR may optionally be wrapped in a simple wrapper
612 structure. This structure contains a simple header that indicates the offset
613 and size of the embedded BC file. This allows additional information to be
614 stored alongside the BC file. The structure of this file header is:
615 </p>
618 <p>
621 </p>
622 </div>
624 <p>
625 Each of the fields are 32-bit fields stored in little endian form (as with
626 the rest of the bitcode file fields). The Magic number is always
628 field is the offset in bytes to the start of the bitcode stream in the file, and
629 the Size field is a size in bytes of the stream. CPUType is a target-specific
630 value that can be used to encode the CPU of the target.
631 </p>
633 </div>
635 <!-- *********************************************************************** -->
637 <!-- *********************************************************************** -->
641 <p>
642 LLVM IR is encoded into a bitstream by defining blocks and records. It uses
643 blocks for things like constant pools, functions, symbol tables, etc. It uses
644 records for things like instructions, global variable descriptors, type
645 descriptions, etc. This document does not describe the set of abbreviations
646 that the writer uses, as these are fully self-described in the file, and the
647 reader is not allowed to build in any knowledge of this.
648 </p>
650 </div>
652 <!-- ======================================================================= -->
654 </div>
656 <!-- _______________________________________________________________________ -->
661 <p>
662 The magic number for LLVM IR files is:
663 </p>
666 <p>
668 </p>
669 </div>
671 <p>
672 When combined with the bitcode magic number and viewed as bytes, this is
674 </p>
676 </div>
678 <!-- _______________________________________________________________________ -->
683 <p>
685 encode arbitrary sized unsigned values, but is an extremely inefficient way to
686 encode signed values (as signed values are otherwise treated as maximally large
687 unsigned values).
688 </p>
690 <p>
691 As such, signed vbr values of a specific width are emitted as follows:
692 </p>
694 <ul>
695 <li>Positive values are emitted as vbrs of the specified width, but with their
696 value shifted left by one.</li>
697 <li>Negative values are emitted as vbrs of the specified width, but the negated
698 value is shifted left by one, and the low bit is set.</li>
699 </ul>
701 <p>
702 With this encoding, small positive and small negative values can both be emitted
703 efficiently.
704 </p>
706 </div>
709 <!-- _______________________________________________________________________ -->
714 <p>
715 LLVM IR is defined with the following blocks:
716 </p>
718 <ul>
720 contains the entire module, and describes a variety of per-module
721 information.</li>
723 attributes.</li>
725 the module.</li>
727 module or function.</li>
729 body.</li>
731 table.</li>
733 table.</li>
734 </ul>
736 </div>
738 <!-- ======================================================================= -->
740 </div>
744 <p>
745 </p>
747 </div>
750 <!-- *********************************************************************** -->
751 <hr>
758 Last modified: $Date$
759 </address>
760 </body>
761 </html>