| blob | f1ddefdea9afefe7664c6a7433234a1364dde6e8 |
3 <html>
4 <head>
8 </head>
9 <body>
11 <ol>
15 <ol>
23 </ol>
24 </li>
26 </li>
28 <ol>
39 </ol>
40 </li>
41 </ol>
45 </p>
46 </div>
48 <!-- *********************************************************************** -->
50 <!-- *********************************************************************** -->
54 <p>This document describes the LLVM bitstream file format and the encoding of
55 the LLVM IR into it.</p>
57 </div>
59 <!-- *********************************************************************** -->
61 <!-- *********************************************************************** -->
65 <p>
66 What is commonly known as the LLVM bitcode file format (also, sometimes
67 anachronistically known as bytecode) is actually two things: a <a
71 <p>
72 The bitstream format is an abstract encoding of structured data, very
73 similar to XML in some ways. Like XML, bitstream files contain tags, and nested
74 structures, and you can parse the file without having to understand the tags.
75 Unlike XML, the bitstream format is a binary encoding, and unlike XML it
76 provides a mechanism for the file to self-describe "abbreviations", which are
77 effectively size optimizations for the content.</p>
81 along with LLVM IR files.</p>
83 <p>This document first describes the LLVM bitstream format, describes the
84 wrapper format, then describes the record structure used by LLVM IR files.
85 </p>
87 </div>
89 <!-- *********************************************************************** -->
91 <!-- *********************************************************************** -->
95 <p>
96 The bitstream format is literally a stream of bits, with a very simple
97 structure. This structure consists of the following concepts:
98 </p>
100 <ul>
102 the stream.</li>
104 integers.</li>
107 file.</li>
109 </ul>
113 used to dump and inspect arbitrary bitstreams, which is very useful for
114 understanding the encoding.</p>
116 </div>
118 <!-- ======================================================================= -->
120 </div>
125 The second two bytes are an application-specific magic number. Generic
126 bitcode tools can look at only the first two bytes to verify the file is
127 bitcode, while application-specific programs will want to look at all four.</p>
129 </div>
131 <!-- ======================================================================= -->
133 </div>
137 <p>
138 A bitstream literally consists of a stream of bits, which are read in order
139 starting with the least significant bit of each byte. The stream is made up of a
140 number of primitive values that encode a stream of unsigned integer values.
143 Integers</a>.
144 </p>
146 </div>
148 <!-- _______________________________________________________________________ -->
150 </div>
154 <p>Fixed-width integer values have their low bits emitted directly to the file.
156 are used when there are a well-known number of options for a field. For
157 example, boolean values are usually encoded with a 1-bit wide integer.
158 </p>
160 </div>
162 <!-- _______________________________________________________________________ -->
164 Integers</a></div>
168 <p>Variable-width integer (VBR) values encode values of arbitrary size,
169 optimizing for the case where the values are small. Given a 4-bit VBR field,
172 chunks, where all but the last set the high bit.</p>
176 continuation piece (indicated by a high bit of 1). The next word indicates a
178 27.
179 </p>
181 </div>
183 <!-- _______________________________________________________________________ -->
192 <pre>
198 </pre>
199 </div>
201 <p>This encoding is only suitable for encoding characters and strings that
202 consist only of the above characters. It is completely incapable of encoding
203 characters not in the set.</p>
205 </div>
207 <!-- _______________________________________________________________________ -->
212 <p>Occasionally, it is useful to emit zero bits until the bitstream is a
213 multiple of 32 bits. This ensures that the bit position in the stream can be
216 </div>
219 <!-- ======================================================================= -->
221 </div>
225 <p>
228 abbreviation ID encoded as a fixed-bitwidth field. The width is specified by
229 the current block, as described below. The value of the abbreviation ID
230 specifies either a builtin ID (which have special meanings, defined below) or
231 one of the abbreviation IDs defined for the current block by the stream itself.
232 </p>
234 <p>
235 The set of builtin abbrev IDs is:
236 </p>
238 <ul>
240 the end of the current block.</li>
242 abbrev ID marks the beginning of a new block.</li>
244 a new abbreviation.</li>
246 specifies the definition of an unabbreviated record.</li>
247 </ul>
252 </div>
254 <!-- ======================================================================= -->
256 </div>
260 <p>
261 Blocks in a bitstream denote nested regions of the stream, and are identified by
262 a content-specific id number (for example, LLVM IR uses an ID of 12 to represent
264 whose meaning is defined by Bitcode; block IDs 8 and greater are
265 application specific. Nested blocks capture the hierarchical structure of the data
266 encoded in it, and various properties are associated with blocks as the file is
267 parsed. Block definitions allow the reader to efficiently skip blocks
268 in constant time if the reader wants a summary of blocks, or if it wants to
269 efficiently skip data it does not understand. The LLVM IR reader uses this
270 mechanism to skip function bodies, lazily reading them on demand.
271 </p>
273 <p>
274 When reading and encoding the stream, several properties are maintained for the
275 block. In particular, each block maintains:
276 </p>
278 <ol>
280 the stream, and is set every time a
281 block record is entered. The block entry specifies the abbrev id width for
282 the body of the block.</li>
284 <li>A set of abbreviations. Abbreviations may be defined within a block, in
285 which case they are only defined in that block (neither subblocks nor
286 enclosing blocks see the abbreviation). Abbreviations can also be defined
288 they are defined in all blocks that match the ID that the BLOCKINFO block is
289 describing.
290 </li>
291 </ol>
293 <p>
294 As sub blocks are entered, these properties are saved and the new sub-block has
295 its own set of abbreviations, and its own abbrev id width. When a sub-block is
296 popped, the saved values are restored.
297 </p>
299 </div>
301 <!-- _______________________________________________________________________ -->
303 Encoding</a></div>
310 <p>
313 indicates the type of block being entered, which can be
317 that specifies the size of the subblock in 32-bit words. This value allows the
318 reader to skip over the entire block in one jump.
319 </p>
321 </div>
323 <!-- _______________________________________________________________________ -->
325 Encoding</a></div>
331 <p>
333 record. Its end is aligned to 32-bits to ensure that the size of the block is
334 an even multiple of 32-bits.
335 </p>
337 </div>
341 <!-- ======================================================================= -->
343 </div>
346 <p>
347 Data records consist of a record code and a number of (up to) 64-bit
348 integer values. The interpretation of the code and values is
349 application specific and may vary between different block types.
350 Records can be encoded either using an unabbrev record, or with an
351 abbreviation. In the LLVM IR format, for example, there is a record
352 which encodes the target triple of a module. The code is
354 ASCII codes for the characters in the string.
355 </p>
357 </div>
359 <!-- _______________________________________________________________________ -->
361 Encoding</a></div>
368 <p>
370 completely general and extremely inefficient. It can describe an arbitrary
371 record by emitting the code and operands as VBRs.
372 </p>
374 <p>
375 For example, emitting an LLVM IR target triple as an unabbreviated record
378 equal to the number of operands, and a vbr6 for each character. Because there
379 are no letters with values less than 32, each letter would need to be emitted as
380 at least a two-part VBR, which means that each letter would require at least 12
381 bits. This is not an efficient encoding, but it is fully general.
382 </p>
384 </div>
386 <!-- _______________________________________________________________________ -->
388 Encoding</a></div>
394 <p>
395 An abbreviated record is a abbreviation id followed by a set of fields that are
397 This allows records to be encoded significantly more densely than records
399 and allows the abbreviation types to be specified in the stream itself, which
400 allows the files to be completely self describing. The actual encoding of
401 abbreviations is defined below.
402 </p>
404 <p>The record code, which is the first field of an abbreviated record,
405 may be encoded in the abbreviation definition (as a literal
406 operand) or supplied in the abbreviated record (as a Fixed or VBR
407 operand value).</p>
409 </div>
411 <!-- ======================================================================= -->
413 </div>
416 <p>
417 Abbreviations are an important form of compression for bitstreams. The idea is
418 to specify a dense encoding for a class of records once, then use that encoding
419 to emit many records. It takes space to emit the encoding into the file, but
420 the space is recouped (hopefully plus some) when the records that use it are
421 emitted.
422 </p>
424 <p>
425 Abbreviations can be determined dynamically per client, per file. Because the
426 abbreviations are stored in the bitstream itself, different streams of the same
427 format can contain different sets of abbreviations according to the needs
428 of the specific stream.
429 As a concrete example, LLVM IR files usually emit an abbreviation
430 for binary operators. If a specific LLVM module contained no or few binary
431 operators, the abbreviation does not need to be emitted.
432 </p>
433 </div>
435 <!-- _______________________________________________________________________ -->
437 Encoding</a></div>
442 ...]</tt></p>
444 <p>
446 defined abbreviations in the scope of this block. This definition only exists
447 inside this immediate block — it is not visible in subblocks or enclosing
448 blocks. Abbreviations are implicitly assigned IDs sequentially starting from 4
449 (the first application-defined abbreviation ID). Any abbreviations defined in a
451 receive IDs first, in order, followed by any
452 abbreviations defined within the block itself. Abbreviated data records
453 reference this ID to indicate what abbreviation they are invoking.
454 </p>
456 <p>
458 followed by a VBR that specifies the number of abbrev operands, then the abbrev
459 operands themselves. Abbreviation operands come in three forms. They all start
460 with a single bit that indicates whether the abbrev operand is a literal operand
462 </p>
464 <ol>
466 — Literal operands specify that the value in the result is always a single
467 specific value. This specific value is emitted as a vbr8 after the bit
468 indicating that it is a literal operand.</li>
471 data are just emitted as their code.
472 </li>
475 emitted as their code, followed by the extra data.
476 </li>
477 </ol>
481 <ul>
484 the operand's extra data.</li>
487 specified by the operand's extra data.</li>
489 has no extra data, but expects another operand to follow it, indicating
490 the element type of the array. When reading an array in an abbreviated
491 record, the first integer is a vbr6 that indicates the array length,
492 followed by the encoded elements of the array. An array may only occur as
493 the last operand of an abbreviation (except for the one final operand that
494 gives the array's type).</li>
497 extra data. Char6 encoding is normally used as an array element type.
498 </li>
501 bytes is further followed by tail padding to ensure that its total length is
502 a multiple of 4 bytes. This makes it very efficient for the reader to
503 decode the data without having to make a copy of it: it can use a pointer to
504 the data in the mapped in file and poke directly at it. A blob may only
505 occur as the last operand of an abbreviation.</li>
506 </ul>
508 <p>
509 For example, target triples in LLVM modules are encoded as a record of the
511 the following abbrev entry:
512 </p>
515 <pre>
517 [0, Array]
518 [0, Char6]
519 </pre>
520 </div>
522 <p>
523 When emitting a record with this abbreviation, the above entry would be emitted
524 as:
525 </p>
528 <p>
531 </p>
532 </div>
536 <ol>
538 <li>The second value, 2, is the record code for <tt>TRIPLE</tt> records within LLVM IR file <tt>MODULE_BLOCK</tt> blocks.</li>
540 <li>The rest of the values are the char6 encoded values
542 </ol>
544 <p>
545 With this abbreviation, the triple is emitted with only 37 bits (assuming a
546 abbrev id width of 3). Without the abbreviation, significantly more space would
548 is not emitted as a literal in the abbreviation, the abbreviation can also be
549 used for any other string value.
550 </p>
552 </div>
554 <!-- ======================================================================= -->
556 </div>
560 <p>
561 In addition to the basic block structure and record encodings, the bitstream
562 also defines specific built-in block types. These block types specify how the
563 stream is to be decoded or other metadata. In the future, new standard blocks
565 </p>
567 </div>
569 <!-- _______________________________________________________________________ -->
571 Block</a></div>
575 <p>
577 blocks. The currently specified records are:
578 </p>
581 <pre>
582 [SETBID (#1), blockid]
583 [DEFINE_ABBREV, ...]
584 [BLOCKNAME, ...name...]
585 [SETRECORDNAME, RecordID, ...name...]
586 </pre>
587 </div>
589 <p>
592 block to change which block ID is being described. There must be
594 </p>
596 <p>
598 blocks, but unlike their occurrence in normal blocks, the abbreviation is
603 </p>
606 the record are the bytes of the string name of the block. llvm-bcanalyzer can use
607 this to dump out bitcode files symbolically.</p>
610 first operand value is a record ID number, and the rest of the elements of the record are
611 the bytes for the string name of the record. llvm-bcanalyzer can use
612 this to dump out bitcode files symbolically.</p>
614 <p>
616 "metadata," the abbreviations they contain are essential for parsing records
617 from the corresponding blocks. It is not safe to skip them.
618 </p>
620 </div>
622 <!-- *********************************************************************** -->
624 <!-- *********************************************************************** -->
628 <p>
629 Bitcode files for LLVM IR may optionally be wrapped in a simple wrapper
630 structure. This structure contains a simple header that indicates the offset
631 and size of the embedded BC file. This allows additional information to be
632 stored alongside the BC file. The structure of this file header is:
633 </p>
636 <p>
639 </p>
640 </div>
642 <p>
643 Each of the fields are 32-bit fields stored in little endian form (as with
644 the rest of the bitcode file fields). The Magic number is always
646 field is the offset in bytes to the start of the bitcode stream in the file, and
647 the Size field is the size in bytes of the stream. CPUType is a target-specific
648 value that can be used to encode the CPU of the target.
649 </p>
651 </div>
653 <!-- *********************************************************************** -->
655 <!-- *********************************************************************** -->
659 <p>
660 LLVM IR is encoded into a bitstream by defining blocks and records. It uses
661 blocks for things like constant pools, functions, symbol tables, etc. It uses
662 records for things like instructions, global variable descriptors, type
663 descriptions, etc. This document does not describe the set of abbreviations
664 that the writer uses, as these are fully self-described in the file, and the
665 reader is not allowed to build in any knowledge of this.
666 </p>
668 </div>
670 <!-- ======================================================================= -->
672 </div>
674 <!-- _______________________________________________________________________ -->
679 <p>
680 The magic number for LLVM IR files is:
681 </p>
684 <p>
686 </p>
687 </div>
689 <p>
690 When combined with the bitcode magic number and viewed as bytes, this is
692 </p>
694 </div>
696 <!-- _______________________________________________________________________ -->
701 <p>
703 encode arbitrary sized unsigned values, but is an extremely inefficient for
704 encoding signed values, as signed values are otherwise treated as maximally large
705 unsigned values.
706 </p>
708 <p>
709 As such, signed VBR values of a specific width are emitted as follows:
710 </p>
712 <ul>
713 <li>Positive values are emitted as VBRs of the specified width, but with their
714 value shifted left by one.</li>
715 <li>Negative values are emitted as VBRs of the specified width, but the negated
716 value is shifted left by one, and the low bit is set.</li>
717 </ul>
719 <p>
720 With this encoding, small positive and small negative values can both
721 be emitted efficiently. Signed VBR encoding is used in
724 </p>
726 </div>
729 <!-- _______________________________________________________________________ -->
734 <p>
735 LLVM IR is defined with the following blocks:
736 </p>
738 <ul>
739 <li>8 — <a href="#MODULE_BLOCK"><tt>MODULE_BLOCK</tt></a> — This is the top-level block that
740 contains the entire module, and describes a variety of per-module
741 information.</li>
742 <li>9 — <a href="#PARAMATTR_BLOCK"><tt>PARAMATTR_BLOCK</tt></a> — This enumerates the parameter
743 attributes.</li>
744 <li>10 — <a href="#TYPE_BLOCK"><tt>TYPE_BLOCK</tt></a> — This describes all of the types in
745 the module.</li>
746 <li>11 — <a href="#CONSTANTS_BLOCK"><tt>CONSTANTS_BLOCK</tt></a> — This describes constants for a
747 module or function.</li>
748 <li>12 — <a href="#FUNCTION_BLOCK"><tt>FUNCTION_BLOCK</tt></a> — This describes a function
749 body.</li>
750 <li>13 — <a href="#TYPE_SYMTAB_BLOCK"><tt>TYPE_SYMTAB_BLOCK</tt></a> — This describes the type symbol
751 table.</li>
752 <li>14 — <a href="#VALUE_SYMTAB_BLOCK"><tt>VALUE_SYMTAB_BLOCK</tt></a> — This describes a value symbol
753 table.</li>
754 <li>15 — <a href="#METADATA_BLOCK"><tt>METADATA_BLOCK</tt></a> — This describes metadata items.</li>
755 <li>16 — <a href="#METADATA_ATTACHMENT"><tt>METADATA_ATTACHMENT</tt></a> — This contains records associating metadata with function instruction values.</li>
756 </ul>
758 </div>
760 <!-- ======================================================================= -->
762 </div>
767 bitcode files, and each bitcode file must contain exactly one. In
768 addition to records (described below) containing information
770 following sub-blocks:
771 </p>
773 <ul>
782 </ul>
784 </div>
786 <!-- _______________________________________________________________________ -->
788 </div>
795 indicating the format version. Only version 0 is supported at this
796 time.</p>
797 </div>
799 <!-- _______________________________________________________________________ -->
801 </div>
808 specification string.</p>
809 </div>
811 <!-- _______________________________________________________________________ -->
812 <div class="doc_subsubsection"><a name="MODULE_CODE_DATALAYOUT">MODULE_CODE_DATALAYOUT Record</a>
813 </div>
820 specification string.</p>
821 </div>
823 <!-- _______________________________________________________________________ -->
825 </div>
833 </div>
835 <!-- _______________________________________________________________________ -->
836 <div class="doc_subsubsection"><a name="MODULE_CODE_SECTIONNAME">MODULE_CODE_SECTIONNAME Record</a>
837 </div>
843 of values representing the bytes of a single section name
845 section name referenced (e.g., in global variable or function
849 </div>
851 <!-- _______________________________________________________________________ -->
853 </div>
859 values representing the bytes of a single dependent library name
862 library name referenced.</p>
863 </div>
865 <!-- _______________________________________________________________________ -->
867 </div>
870 <p><tt>[GLOBALVAR, pointer type, isconst, initid, linkage, alignment, section, visibility, threadlocal]</tt></p>
873 definition of a global variable. The operand fields are:</p>
875 <ul>
877 this global variable</li>
880 the module, or zero if it is not</li>
886 type for this variable:
887 <ul>
902 </ul>
903 </li>
910 entries.</li>
913 encoding of the visibility of this variable:
914 <ul>
918 </ul>
919 </li>
924 </ul>
925 </div>
927 <!-- _______________________________________________________________________ -->
929 </div>
933 <p><tt>[FUNCTION, type, callingconv, isproto, linkage, paramattr, alignment, section, visibility, gc]</tt></p>
936 definition of a function. The operand fields are:</p>
938 <ul>
942 <ul>
951 </ul>
952 </li>
955 rather than a definition</li>
958 for this function</li>
962 entries.</li>
969 entries.</li>
972 of this function</li>
975 index in the table of
977 </ul>
978 </div>
980 <!-- _______________________________________________________________________ -->
982 </div>
989 alias. The operand fields are</p>
991 <ul>
997 for this alias</li>
1002 </ul>
1003 </div>
1005 <!-- _______________________________________________________________________ -->
1006 <div class="doc_subsubsection"><a name="MODULE_CODE_PURGEVALS">MODULE_CODE_PURGEVALS Record</a>
1007 </div>
1013 value list to the size given by the single operand value. Module-level
1017 </div>
1019 <!-- _______________________________________________________________________ -->
1021 </div>
1027 values representing the bytes of a single garbage collector name
1032 </div>
1034 <!-- ======================================================================= -->
1036 </div>
1041 </p>
1043 </div>
1046 <!-- _______________________________________________________________________ -->
1048 </div>
1055 </p>
1056 </div>
1058 <!-- ======================================================================= -->
1060 </div>
1065 </p>
1067 </div>
1070 <!-- ======================================================================= -->
1072 </div>
1077 </p>
1079 </div>
1082 <!-- ======================================================================= -->
1084 </div>
1089 </p>
1091 <p>In addition to the record types described below, a
1093 </p>
1095 <ul>
1099 </ul>
1101 </div>
1104 <!-- ======================================================================= -->
1106 </div>
1111 </p>
1113 </div>
1116 <!-- ======================================================================= -->
1118 </div>
1123 </p>
1125 </div>
1128 <!-- ======================================================================= -->
1130 </div>
1135 </p>
1137 </div>
1140 <!-- ======================================================================= -->
1142 </div>
1147 </p>
1149 </div>
1152 <!-- *********************************************************************** -->
1153 <hr>
1160 Last modified: $Date$
1161 </address>
1162 </body>
1163 </html>