-<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN" "http://www.w3.org/TR/html4/strict.dtd">
+<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01//EN"
+ "http://www.w3.org/TR/html4/strict.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>LLVM Bitcode File Format</title>
<link rel="stylesheet" href="llvm.css" type="text/css">
- <style type="text/css">
- TR, TD { border: 2px solid gray; padding-left: 4pt; padding-right: 4pt;
- padding-top: 2pt; padding-bottom: 2pt; }
- TH { border: 2px solid gray; font-weight: bold; font-size: 105%; }
- TABLE { text-align: center; border: 2px solid black;
- border-collapse: collapse; margin-top: 1em; margin-left: 1em;
- margin-right: 1em; margin-bottom: 1em; }
- .td_left { border: 2px solid gray; text-align: left; }
- </style>
</head>
<body>
<div class="doc_title"> LLVM Bitcode File Format </div>
<ol>
<li><a href="#abstract">Abstract</a></li>
- <li><a href="#concepts">Concepts</a></li>
+ <li><a href="#overview">Overview</a></li>
+ <li><a href="#bitstream">Bitstream Format</a>
+ <ol>
+ <li><a href="#magic">Magic Numbers</a></li>
+ <li><a href="#primitives">Primitives</a></li>
+ <li><a href="#abbrevid">Abbreviation IDs</a></li>
+ <li><a href="#blocks">Blocks</a></li>
+ <li><a href="#datarecord">Data Records</a></li>
+ <li><a href="#abbreviations">Abbreviations</a></li>
+ </ol>
+ </li>
+ <li><a href="#llvmir">LLVM IR Encoding</a></li>
</ol>
<div class="doc_author">
- <p>Written by <a href="mailto:rspencer@x10sys.com">Reid Spencer</a> and
- <a href="mailto:sabre@nondot.org">Chris Lattner</a>.
+ <p>Written by <a href="mailto:sabre@nondot.org">Chris Lattner</a>.
</p>
</div>
+
<!-- *********************************************************************** -->
-<div class="doc_section"> <a name="abstract">Abstract </a></div>
+<div class="doc_section"> <a name="abstract">Abstract</a></div>
<!-- *********************************************************************** -->
+
<div class="doc_text">
-<p>This document describes the LLVM bitcode file format. It specifies
-the binary encoding rules of the bitcode file format so that
-equivalent systems can encode bitcode files correctly. The LLVM
-bitcode representation is used to store the intermediate
-representation on disk in a compacted form.</p>
-<p>This document supercedes the LLVM bytecode file format for the 2.0
-release.</p>
+
+<p>This document describes the LLVM bitstream file format and the encoding of
+the LLVM IR into it.</p>
+
</div>
+
<!-- *********************************************************************** -->
-<div class="doc_section"> <a name="concepts">Concepts</a> </div>
+<div class="doc_section"> <a name="overview">Overview</a></div>
<!-- *********************************************************************** -->
+
<div class="doc_text">
-<p>This section describes the general concepts of the bitcode file
-format without getting into specific layout details. It is recommended
-that you read this section thoroughly before interpreting the detailed
-descriptions.</p>
+
+<p>
+What is commonly known as the LLVM bitcode file format (also, sometimes
+anachronistically known as bytecode) is actually two things: a <a
+href="#bitstream">bitstream container format</a>
+and an <a href="#llvmir">encoding of LLVM IR</a> into the container format.</p>
+
+<p>
+The bitstream format is an abstract encoding of structured data, very
+similar to XML in some ways. Like XML, bitstream files contain tags, and nested
+structures, and you can parse the file without having to understand the tags.
+Unlike XML, the bitstream format is a binary encoding, and unlike XML it
+provides a mechanism for the file to self-describe "abbreviations", which are
+effectively size optimizations for the content.</p>
+
+<p>This document first describes the LLVM bitstream format, then describes the
+record structure used by LLVM IR files.
+</p>
+
+</div>
+
+<!-- *********************************************************************** -->
+<div class="doc_section"> <a name="bitstream">Bitstream Format</a></div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+
+<p>
+The bitstream format is literally a stream of bits, with a very simple
+structure. This structure consists of the following concepts:
+</p>
+
+<ul>
+<li>A "<a href="#magic">magic number</a>" that identifies the contents of
+ the stream.</li>
+<li>Encoding <a href="#primitives">primitives</a> like variable bit-rate
+ integers.</li>
+<li><a href="#blocks">Blocks</a>, which define nested content.</li>
+<li><a href="#datarecord">Data Records</a>, which describe entities within the
+ file.</li>
+<li>Abbreviations, which specify compression optimizations for the file.</li>
+</ul>
+
+<p>Note that the <a
+href="CommandGuide/html/llvm-bcanalyzer.html">llvm-bcanalyzer</a> tool can be
+used to dump and inspect arbitrary bitstreams, which is very useful for
+understanding the encoding.</p>
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection"><a name="magic">Magic Numbers</a>
+</div>
+
+<div class="doc_text">
+
+<p>The first four bytes of the stream identify the encoding of the file. This
+is used by a reader to know what is contained in the file.</p>
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection"><a name="primitives">Primitives</a>
+</div>
+
+<div class="doc_text">
+
+<p>
+A bitstream literally consists of a stream of bits. This stream is made up of a
+number of primitive values that encode a stream of integer values. These
+integers are are encoded in two ways: either as <a href="#fixedwidth">Fixed
+Width Integers</a> or as <a href="#variablewidth">Variable Width
+Integers</a>.
+</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection"> <a name="fixedwidth">Fixed Width Integers</a>
+</div>
+
+<div class="doc_text">
+
+<p>Fixed-width integer values have their low bits emitted directly to the file.
+ For example, a 3-bit integer value encodes 1 as 001. Fixed width integers
+ are used when there are a well-known number of options for a field. For
+ example, boolean values are usually encoded with a 1-bit wide integer.
+</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection"> <a name="variablewidth">Variable Width
+Integers</a></div>
+
+<div class="doc_text">
+
+<p>Variable-width integer (VBR) values encode values of arbitrary size,
+optimizing for the case where the values are small. Given a 4-bit VBR field,
+any 3-bit value (0 through 7) is encoded directly, with the high bit set to
+zero. Values larger than N-1 bits emit their bits in a series of N-1 bit
+chunks, where all but the last set the high bit.</p>
+
+<p>For example, the value 27 (0x1B) is encoded as 1011 0011 when emitted as a
+vbr4 value. The first set of four bits indicates the value 3 (011) with a
+continuation piece (indicated by a high bit of 1). The next word indicates a
+value of 24 (011 << 3) with no continuation. The sum (3+24) yields the value
+27.
+</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection"> <a name="char6">6-bit characters</a></div>
+
+<div class="doc_text">
+
+<p>6-bit characters encode common characters into a fixed 6-bit field. They
+represent the following characters with the following 6-bit values:</p>
+
+<ul>
+<li>'a' .. 'z' - 0 .. 25</li>
+<li>'A' .. 'Z' - 26 .. 52</li>
+<li>'0' .. '9' - 53 .. 61</li>
+<li>'.' - 62</li>
+<li>'_' - 63</li>
+</ul>
+
+<p>This encoding is only suitable for encoding characters and strings that
+consist only of the above characters. It is completely incapable of encoding
+characters not in the set.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection"> <a name="wordalign">Word Alignment</a></div>
+
+<div class="doc_text">
+
+<p>Occasionally, it is useful to emit zero bits until the bitstream is a
+multiple of 32 bits. This ensures that the bit position in the stream can be
+represented as a multiple of 32-bit words.</p>
+
+</div>
+
+
+<!-- ======================================================================= -->
+<div class="doc_subsection"><a name="abbrevid">Abbreviation IDs</a>
+</div>
+
+<div class="doc_text">
+
+<p>
+A bitstream is a sequential series of <a href="#blocks">Blocks</a> and
+<a href="#datarecord">Data Records</a>. Both of these start with an
+abbreviation ID encoded as a fixed-bitwidth field. The width is specified by
+the current block, as described below. The value of the abbreviation ID
+specifies either a builtin ID (which have special meanings, defined below) or
+one of the abbreviation IDs defined by the stream itself.
+</p>
+
+<p>
+The set of builtin abbrev IDs is:
+</p>
+
+<ul>
+<li>0 - <a href="#END_BLOCK">END_BLOCK</a> - This abbrev ID marks the end of the
+ current block.</li>
+<li>1 - <a href="#ENTER_SUBBLOCK">ENTER_SUBBLOCK</a> - This abbrev ID marks the
+ beginning of a new block.</li>
+<li>2 - <a href="#DEFINE_ABBREV">DEFINE_ABBREV</a> - This defines a new
+ abbreviation.</li>
+<li>3 - <a href="#UNABBREV_RECORD">UNABBREV_RECORD</a> - This ID specifies the
+ definition of an unabbreviated record.</li>
+</ul>
+
+<p>Abbreviation IDs 4 and above are defined by the stream itself, and specify
+an <a href="#abbrev_records">abbreviated record encoding</a>.</p>
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection"><a name="blocks">Blocks</a>
+</div>
+
+<div class="doc_text">
+
+<p>
+Blocks in a bitstream denote nested regions of the stream, and are identified by
+a content-specific id number (for example, LLVM IR uses an ID of 12 to represent
+function bodies). Nested blocks capture the hierachical structure of the data
+encoded in it, and various properties are associated with blocks as the file is
+parsed. Block definitions allow the reader to efficiently skip blocks
+in constant time if the reader wants a summary of blocks, or if it wants to
+efficiently skip data they do not understand. The LLVM IR reader uses this
+mechanism to skip function bodies, lazily reading them on demand.
+</p>
+
+<p>
+When reading and encoding the stream, several properties are maintained for the
+block. In particular, each block maintains:
+</p>
+
+<ol>
+<li>A current abbrev id width. This value starts at 2, and is set every time a
+ block record is entered. The block entry specifies the abbrev id width for
+ the body of the block.</li>
+
+<li>A set of abbreviations. Abbreviations may be defined within a block, or
+ they may be associated with all blocks of a particular ID.
+</li>
+</ol>
+
+<p>As sub blocks are entered, these properties are saved and the new sub-block
+has its own set of abbreviations, and its own abbrev id width. When a sub-block
+is popped, the saved values are restored.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection"> <a name="ENTER_SUBBLOCK">ENTER_SUBBLOCK
+Encoding</a></div>
+
+<div class="doc_text">
+
+<p><tt>[ENTER_SUBBLOCK, blockid<sub>vbr8</sub>, newabbrevlen<sub>vbr4</sub>,
+ <align32bits>, blocklen<sub>32</sub>]</tt></p>
+
+<p>
+The ENTER_SUBBLOCK abbreviation ID specifies the start of a new block record.
+The <tt>blockid</tt> value is encoded as a 8-bit VBR identifier, and indicates
+the type of block being entered (which is application specific). The
+<tt>newabbrevlen</tt> value is a 4-bit VBR which specifies the
+abbrev id width for the sub-block. The <tt>blocklen</tt> is a 32-bit aligned
+value that specifies the size of the subblock, in 32-bit words. This value
+allows the reader to skip over the entire block in one jump.
+</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection"> <a name="END_BLOCK">END_BLOCK
+Encoding</a></div>
+
+<div class="doc_text">
+
+<p><tt>[END_BLOCK, <align32bits>]</tt></p>
+
+<p>
+The END_BLOCK abbreviation ID specifies the end of the current block record.
+Its end is aligned to 32-bits to ensure that the size of the block is an even
+multiple of 32-bits.</p>
+
+</div>
+
+
+
+<!-- ======================================================================= -->
+<div class="doc_subsection"><a name="datarecord">Data Records</a>
+</div>
+
+<div class="doc_text">
+<p>
+Data records consist of a record code and a number of (up to) 64-bit integer
+values. The interpretation of the code and values is application specific and
+there are multiple different ways to encode a record (with an unabbrev record
+or with an abbreviation). In the LLVM IR format, for example, there is a record
+which encodes the target triple of a module. The code is MODULE_CODE_TRIPLE,
+and the values of the record are the ascii codes for the characters in the
+string.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection"> <a name="UNABBREV_RECORD">UNABBREV_RECORD
+Encoding</a></div>
+
+<div class="doc_text">
+
+<p><tt>[UNABBREV_RECORD, code<sub>vbr6</sub>, numops<sub>vbr6</sub>,
+ op0<sub>vbr6</sub>, op1<sub>vbr6</sub>, ...]</tt></p>
+
+<p>An UNABBREV_RECORD provides a default fallback encoding, which is both
+completely general and also extremely inefficient. It can describe an arbitrary
+record, by emitting the code and operands as vbrs.</p>
+
+<p>For example, emitting an LLVM IR target triple as an unabbreviated record
+requires emitting the UNABBREV_RECORD abbrevid, a vbr6 for the
+MODULE_CODE_TRIPLE code, a vbr6 for the length of the string (which is equal to
+the number of operands), and a vbr6 for each character. Since there are no
+letters with value less than 32, each letter would need to be emitted as at
+least a two-part VBR, which means that each letter would require at least 12
+bits. This is not an efficient encoding, but it is fully general.</p>
+
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection"> <a name="abbrev_records">Abbreviated Record
+Encoding</a></div>
+
+<div class="doc_text">
+
+<p><tt>[<abbrevid>, fields...]</tt></p>
+
+<p>An abbreviated record is a abbreviation id followed by a set of fields that
+are encoded according to the <a href="#abbreviations">abbreviation
+definition</a>. This allows records to be encoded significantly more densely
+than records encoded with the <a href="#UNABBREV_RECORD">UNABBREV_RECORD</a>
+type, and allows the abbreviation types to be specified in the stream itself,
+which allows the files to be completely self describing. The actual encoding
+of abbreviations is defined below.
+</p>
+
+</div>
+
+<!-- ======================================================================= -->
+<div class="doc_subsection"><a name="abbreviations">Abbreviations</a>
+</div>
+
+<div class="doc_text">
+<p>
+Abbreviations are an important form of compression for bitstreams. The idea is
+to specify a dense encoding for a class of records once, then use that encoding
+to emit many records. It takes space to emit the encoding into the file, but
+the space is recouped (hopefully plus some) when the records that use it are
+emitted.
+</p>
+
+<p>
+Abbreviations can be determined dynamically per client, per file. Since the
+abbreviations are stored in the bitstream itself, different streams of the same
+format can contain different sets of abbreviations if the specific stream does
+not need it. As a concrete example, LLVM IR files usually emit an abbreviation
+for binary operators. If a specific LLVM module contained no or few binary
+operators, the abbreviation does not need to be emitted.
+</p>
+</div>
+
+<!-- _______________________________________________________________________ -->
+<div class="doc_subsubsection"><a name="DEFINE_ABBREV">DEFINE_ABBREV
+ Encoding</a></div>
+
+<div class="doc_text">
+
+<p><tt>[DEFINE_ABBREV, numabbrevops<sub>vbr5</sub>, abbrevop0, abbrevop1,
+ ...]</tt></p>
+
+<p>An abbreviation definition consists of the DEFINE_ABBREV abbrevid followed
+by a VBR that specifies the number of abbrev operands, then the abbrev
+operands themselves. Abbreviation operands come in three forms. They all start
+with a single bit that indicates whether the abbrev operand is a literal operand
+(when the bit is 1) or an encoding operand (when the bit is 0).</p>
+
+<ol>
+<li>Literal operands - <tt>[1<sub>1</sub>, litvalue<sub>vbr8</sub>]</tt> -
+Literal operands specify that the value in the result
+is always a single specific value. This specific value is emitted as a vbr8
+after the bit indicating that it is a literal operand.</li>
+<li>Encoding info without data - <tt>[0<sub>1</sub>, encoding<sub>3</sub>]</tt>
+ - blah
+</li>
+<li>Encoding info with data - <tt>[0<sub>1</sub>, encoding<sub>3</sub>,
+value<sub>vbr5</sub>]</tt> -
+
+</li>
+</ol>
+
+</div>
+
+
+<!-- *********************************************************************** -->
+<div class="doc_section"> <a name="llvmir">LLVM IR Encoding</a></div>
+<!-- *********************************************************************** -->
+
+<div class="doc_text">
+
+<p></p>
+
</div>
+
+
<!-- *********************************************************************** -->
<hr>
<address> <a href="http://jigsaw.w3.org/css-validator/check/referer"><img
src="http://jigsaw.w3.org/css-validator/images/vcss" alt="Valid CSS!"></a>
<a href="http://validator.w3.org/check/referer"><img
src="http://www.w3.org/Icons/valid-html401" alt="Valid HTML 4.01!"></a>
-<a href="mailto:rspencer@x10sys.com">Reid Spencer</a> and <a
- href="mailto:sabre@nondot.org">Chris Lattner</a><br>
+ <a href="mailto:sabre@nondot.org">Chris Lattner</a><br>
<a href="http://llvm.org">The LLVM Compiler Infrastructure</a><br>
Last modified: $Date$
</address>
projects / oota-llvm.git / blobdiff