Initial draft of PNaCl bitcode files document.

native_client_sdk/doc_generated/reference/pnacl-bitcode-manual.html

+{{+bindTo:partials.standard_nacl_article}}
+
+<section id="pnacl-bitcode-file-reference-manual">
+<h1 id="pnacl-bitcode-file-reference-manual">PNaCl Bitcode File Reference Manual</h1>
+<div class="contents local" id="contents" style="display: none">
+<ul class="small-gap">
+<li><a class="reference internal" href="#introduction" id="id19">Introduction</a></li>
+<li><a class="reference internal" href="#high-level-basics" id="id20">High Level Basics</a></li>
+<li><a class="reference internal" href="#pnacl-blocks" id="id21">PNaCl Blocks</a></li>
+<li><a class="reference internal" href="#pnacl-records" id="id22">PNaCl Records</a></li>
+<li><a class="reference internal" href="#conventions-for-describing-records" id="id23">Conventions for describing records</a></li>
+<li><p class="first"><a class="reference internal" href="#parse-state" id="id24">Parse State</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#typing" id="id25">Typing</a></li>
+<li><a class="reference internal" href="#id-counters" id="id26">ID Counters</a></li>
+<li><a class="reference internal" href="#size-variables" id="id27">Size Variables</a></li>
+<li><a class="reference internal" href="#other-variables" id="id28">Other Variables</a></li>
+</ul>
+</li>
+<li><p class="first"><a class="reference internal" href="#special-records" id="id29">Special records</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#header-record" id="id30">Header Record</a></li>
+<li><a class="reference internal" href="#enter-block-record" id="id31">Enter Block Record</a></li>
+<li><a class="reference internal" href="#exit-block-record" id="id32">Exit Block Record</a></li>
+</ul>
+</li>
+<li><p class="first"><a class="reference internal" href="#types-block" id="id33">Types Block</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#count-record" id="id34">Count Record</a></li>
+<li><a class="reference internal" href="#void-type" id="id35">Void Type</a></li>
+<li><a class="reference internal" href="#integer-types" id="id36">Integer Types</a></li>
+<li><a class="reference internal" href="#bit-floating-type" id="id37">32-Bit Floating Type</a></li>
+<li><a class="reference internal" href="#id1" id="id38">64-bit Floating Type</a></li>
+<li><a class="reference internal" href="#vector-types" id="id39">Vector Types</a></li>
+<li><a class="reference internal" href="#function-types" id="id40">Function Types</a></li>
+</ul>
+</li>
+<li><p class="first"><a class="reference internal" href="#globals-block" id="id41">Globals block</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#id2" id="id42">Count Record</a></li>
+<li><a class="reference internal" href="#global-variable-addressses" id="id43">Global Variable Addressses</a></li>
+<li><a class="reference internal" href="#glboal-constant-addresses" id="id44">Glboal Constant Addresses</a></li>
+<li><a class="reference internal" href="#zerofill-initializer" id="id45">Zerofill Initializer</a></li>
+<li><a class="reference internal" href="#data-initializer" id="id46">Data Initializer</a></li>
+<li><a class="reference internal" href="#relocation-initializer" id="id47">Relocation Initializer</a></li>
+<li><a class="reference internal" href="#subfield-relocation-initializer" id="id48">Subfield Relocation Initializer</a></li>
+<li><a class="reference internal" href="#compound-initializer" id="id49">Compound Initializer</a></li>
+</ul>
+</li>
+<li><a class="reference internal" href="#valuesymtab-block" id="id50">Valuesymtab Block</a></li>
+<li><p class="first"><a class="reference internal" href="#module-block" id="id51">Module Block</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#version" id="id52">Version</a></li>
+<li><p class="first"><a class="reference internal" href="#function-address" id="id53">Function Address</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#updates" id="id54">Updates</a></li>
+</ul>
+</li>
+</ul>
+</li>
+<li><a class="reference internal" href="#constants-blocks" id="id55">Constants Blocks</a></li>
+<li><p class="first"><a class="reference internal" href="#function-blocks" id="id56">Function Blocks</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#function-enter" id="id57">Function enter</a></li>
+<li><p class="first"><a class="reference internal" href="#id3" id="id58">Count Record</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#id4" id="id59">Updates</a></li>
+</ul>
+</li>
+<li><p class="first"><a class="reference internal" href="#terminator-instructions" id="id60">Terminator Instructions</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#return-void-instruction" id="id61">Return Void Instruction</a></li>
+<li><a class="reference internal" href="#return-value-instruction" id="id62">Return Value Instruction</a></li>
+<li><a class="reference internal" href="#unconditional-branch-instruction" id="id63">Unconditional Branch Instruction</a></li>
+<li><a class="reference internal" href="#conditional-branch-instruction" id="id64">Conditional Branch Instruction</a></li>
+<li><a class="reference internal" href="#unreachable" id="id65">Unreachable</a></li>
+<li><a class="reference internal" href="#switch-instruction" id="id66">Switch Instruction</a></li>
+</ul>
+</li>
+<li><p class="first"><a class="reference internal" href="#binary-inststructions" id="id67">Binary Inststructions</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#add-instruction" id="id68">Add Instruction</a></li>
+<li><a class="reference internal" href="#subtract-instruction" id="id69">Subtract Instruction</a></li>
+<li><a class="reference internal" href="#multiply-instruction" id="id70">Multiply Instruction</a></li>
+<li><a class="reference internal" href="#divide-instruction" id="id71">Divide Instruction</a></li>
+<li><a class="reference internal" href="#remainder-instruction" id="id72">Remainder Instruction</a></li>
+<li><a class="reference internal" href="#shift-left-instruction" id="id73">Shift left Instruction</a></li>
+<li><a class="reference internal" href="#logical-shift-right-instructions" id="id74">Logical Shift right Instructions</a></li>
+<li><a class="reference internal" href="#arithmetic-shift-right-instructions" id="id75">Arithmetic Shift right Instructions</a></li>
+<li><a class="reference internal" href="#and-instruction" id="id76">And Instruction</a></li>
+<li><a class="reference internal" href="#or-instruction" id="id77">Or Instruction</a></li>
+<li><a class="reference internal" href="#xor-instruction" id="id78">Xor Instruction</a></li>
+</ul>
+</li>
+<li><p class="first"><a class="reference internal" href="#memory-creation-and-access-instructions" id="id79">Memory creation and access Instructions</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#stack-frame-memory-allocation-instruction" id="id80">Stack frame memory allocation Instruction</a></li>
+<li><a class="reference internal" href="#load-instruction" id="id81">Load Instruction</a></li>
+<li><a class="reference internal" href="#store-instruction" id="id82">Store Instruction</a></li>
+</ul>
+</li>
+<li><p class="first"><a class="reference internal" href="#conversion-instructions" id="id83">Conversion Instructions</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#truncating-instructions" id="id84">Truncating Instructions</a></li>
+<li><a class="reference internal" href="#extending-instructions" id="id85">Extending Instructions</a></li>
+</ul>
+</li>
+<li><a class="reference internal" href="#comparison-instructions" id="id86">Comparison Instructions</a></li>
+<li><p class="first"><a class="reference internal" href="#other-instructions" id="id87">Other Instructions</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#phi-instruction" id="id88">Phi Instruction</a></li>
+<li><a class="reference internal" href="#forward-type-declarations" id="id89">Forward type declarations</a></li>
+<li><a class="reference internal" href="#select-instruction" id="id90">Select Instruction</a></li>
+<li><a class="reference internal" href="#call-instructions" id="id91">Call Instructions</a></li>
+</ul>
+</li>
+<li><a class="reference internal" href="#intrinsic-functions" id="id92">Intrinsic Functions</a></li>
+<li><p class="first"><a class="reference internal" href="#support-functions" id="id93">Support Functions</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#absoluteindex" id="id94">AbsoluteIndex</a></li>
+<li><a class="reference internal" href="#relativeindex" id="id95">RelativeIndex</a></li>
+</ul>
+</li>
+<li><p class="first"><a class="reference internal" href="#abbreviations" id="id96">Abbreviations</a></p>
+<ul class="small-gap">
+<li><a class="reference internal" href="#id18" id="id97">Introduction</a></li>
+<li><a class="reference internal" href="#bitstream-format" id="id98">Bitstream Format</a></li>
+</ul>
+</li>
+<li><a class="reference internal" href="#reference-implementation" id="id99">Reference Implementation</a></li>
+</ul>
+</li>
+</ul>
+
+</div><section id="introduction">
+<h2 id="introduction">Introduction</h2>
+<p>This document is a reference manual for the contents of PNaCl bitcode
+files. It is presented using assembly language <em>PNaClAsm</em>. PNaClAsm
+uses a <em>static single assignment</em> (SSA) model, based a representation
+that requires generated results to have a single (assignment)
+source. PNaClAsm is the textual version of the bitcode file.</p>
+<p>PNaClAsm focusses on the semantic content of the file, not the
+bit-encoding of that content. However, it does provide annotations
+that allows one to specify how the PNaCl bitcode writer converts the
+semantic content of a PNaClAsm program, into a specific bit sequence.</p>
+<p>Below PNaClAsm is the high-level form of the data stored in PNaCl
+bitcode files. Each construct in PNaClAsm defines a corresponding
+<em>PNaCl record</em> [ref].  A PNaCl bitcode file is simply a sequence of
+PNaCl records. The goal of PNaClAsm is to make records easier to read,
+and not to define a high-level user programming language.</p>
+<p>PNaCl records are an abstract encoding of structured data, similar
+to XML. Like XML, PNaCl records have a notion of tags (i.e. the first
+element in a record, called a <em>code</em>), and nested structures. The
+nested structures are defined by corresponding <em>enter</em> and <em>exit</em>
+block records.</p>
+<p>These block records must be used like parentheses to define the block
+structure that is imposed on top of records. Each exit record must be
+preceded by a corresponding enter record. Blocks can be nested by
+nesting enter/exit records appropriately.</p>
+<p>The <em>PNaCl bitcode wrtier</em> takes the sequence of records, defined by a
+PNaClAsm program, and coverts each record into a (variable) sequence
+of bits. The output of each bit sequence is appended together. The
+resulting generated sequence of bits is the contents of the PNaCl
+bitcode file.</p>
+<p>For every kind of record, there are default methods for converting
+records into bit sequences. These methods correspond to a notion of
+<em>abbreviations</em> [ref]. Each abbreviation defines a specific bit
+sequence conversion to be applied. The default conversion methods are
+simply predefined abbreviations.</p>
+<p>The default abbreviations can be overriddeen with user-specified
+abbrreviations.  All user-specified abbreviations are included in the
+generated bitcode file. Each abbreviation defines how records are
+converted to bit sequences. The <em>PNaCl bitcode writer</em> uses these
+abbreviations to convert the corresponding record sequence into a
+corresponding bit sequence. As a result, all records have an
+abbreviation (user or default) associated with them.</p>
+<p>The <em>PNaCl bitcode reader</em> then uses these abbreviations to convert
+the bit sequences back into the corresponding records.</p>
+<p>Conceptually, abbreviations are used to define how to pack the
+contents of records into bit sequenes.  The main reason for defining
+abbreviations is to save space. The default abbreviations are
+simplistic and are intended to handle all possible records. The
+default abbreviations do not really worry about being efficient, in
+terms of the number of bits generated.</p>
+<p>By separating the concepts of PNaCl records and abbreviations, the
+notion of data compression is cleanly seperated from semantic
+content. This allows different use cases to decide how much effort
+should be spent on compressing records.</p>
+<p>For a JIT translator, little (if any) compression should be
+applied. In fact, the API to the JIT may just be the records
+themselves.  The goal of a JIT is to perform the final translation to
+machine code as quickly as possible.  On the other hand, when
+delivering accross the web, one may want to compress the sequence of
+bits considerably, to reduce costs in delivering web pages.</p>
+</section><section id="high-level-basics">
+<h2 id="high-level-basics">High Level Basics</h2>
+<p>A program is defined as a sequence of top-level Blocks. Blocks
+can be nested within other blocks. Each <em>block</em> defines a sequence of
+records.</p>
+<p>Most of the records, within a block, also define a unique values.
+Each unique value is given a corresponding unique identifier
+(i.e. <em>ID</em>). In PNaClAms. each kind of block defines it own kind of
+identifiers. The names of these identifiers are defined by
+concatinating a prefix character (&#8216;&#64;&#8217; or &#8216;%&#8217;), the kind of block (a
+single character), and a suffix index. The suffix index is defined by
+the positional location of the defined value within the records of the
+corresponding block. The indices are all zero based, meaning that the
+first defined value (within a block) is defined using index 0.</p>
+<p>Identifiers are categorized into two types, <em>local</em> and
+<em>global</em>. Local identifiers are identifiers that are associated with
+the implementation of a single function. All other identifiers are
+global. This split is intentional. Global identifiers are used by
+multiple functions, and therefore must be unique accross all function
+implementations. Local identifiers only apply to a single function,
+and can be reused between functions.  The <em>PNaCl translator</em> uses this
+separation to parallelize the compilation of functions.</p>
+<p>Global identifiers use the prefix character <em>&#8216;&#64;&#8217;</em> while local
+identifiers use the prefix character <em>&#8216;%&#8217;</em>.</p>
+<p>Note: There is one exception to this separation of local and global
+identifiers.  Abbreviations can be defined locally and globally. An
+abbreviation is local if it only applies to the block it appears
+in. If it is global, the abberviation can apply to multiple block
+instances.</p>
+<p>Note that by using positional location to define identifiers (within a
+block), the values defined in PNaCl bitcode files need not be
+explicitly included in the bitcode file. Rather, they are inferred by
+the (ordered) position of the record in the block.  This is also
+intentional. It is used to reduce the amount of data that must be
+(explicitly) passed to the PNaCl translator.</p>
+<p>In general, most of the records and blocks are assumed to be
+topologically sorted, putting value definitions before thier uses.
+This implies that records do not need to encode data if it can use the
+corresponding information from it&#8217;s uses.</p>
+<p>The most common use of this is that many instructions use the type of
+their operands to determine the type of the instruction. Again, this
+is intentional. It allows less information to be stored with the
+instruction.</p>
+<p>However, For function blocks (which define instructions), no
+topological sort exists. Loop carried value dependencies simply do not
+allow topologically sorting. To deal with this, function blocks have a
+notion of a forward (instruction value) declarations. These
+decalrations must appear before any of the uses of that value, if the
+(instruction) value is defined later in the function, than its first
+use.</p>
+</section><section id="pnacl-blocks">
+<h2 id="pnacl-blocks">PNaCl Blocks</h2>
+<p>Blocks are used to organize records in the bitcode file.  The
+kinds of blocks defined in PNaClAsm are:</p>
+<dl class="docutils">
+<dt>Types block</dt>
+<dd>Defines the set of types used by the program. All types used in the
+program must be defined in this block.</dd>
+<dt>Globals block</dt>
+<dd>Defines the set of global addresses of global variables and
+constants, used by the program. It also defines how each global
+(associated with the global address) is initialized.</dd>
+<dt>Valuesymtab block</dt>
+<dd>Defines textual names for global and function addresses.</dd>
+<dt>Function block</dt>
+<dd>Each function (implemented) in a program has it&#8217;s own block that
+defines the implementation of the corresponding function.</dd>
+<dt>Constants Block</dt>
+<dd>Each implemented function, that uses constants in its
+instructions, defines a constant block. Constants blocks appear
+within corresponding function block.</dd>
+<dt>Modue block</dt>
+<dd>A top-level block defining the program. This block defines global
+information used by the program, followed by function blocks
+defining the implementation of functions within the program.</dd>
+<dt>Abbreviations block</dt>
+<dd>Defines abbreviations that are used to compress PNaCl records. This
+block is segmented into multiple sections, one section for each kind
+of block. This block is optional and need not be defined.</dd>
+</dl>
+<p>A PNaCl program consists of a header record, an optional abbreviations
+block, and a module block.</p>
+<p>Each block, within a bitcode file, defines values. These values are
+associated with IDs. Each type of block defines different kinds of
+IDs.</p>
+<p>The <em>types block</em> [ref] defines types used by the program. Each record
+in the types block defines a separate type. Valid types include
+various sizes of integer and floating types. They also define higher
+level constructs such as vectors and function signatures. For each
+definition, a type ID is defined. A type ID is of the form <em>&#64;tN</em>,
+where <em>N</em> corresponds to the (relative) position of the corresponding
+defining record in the types block.</p>
+<p>The types block must appear within the module block,
+and must appear before any block that uses a typed value.  Many
+PNaClAsm constructs allows one to use explicit type names, rather than
+type IDs. However, they are internally converted to the corresponding
+type ID in the types block. Hence, the requirement that the types
+block must appear early in the module block.</p>
+<p>The <em>module block</em> [ref] contains all other blocks (except for the
+abbreviations block, which can either appear within the module block,
+or immediately before the module block). The only values defined in a
+module block are function addresses.  All remaining definitions appear
+within blocks of the module block.</p>
+<p>Function addresses are global IDs of the form <em>&#64;fN</em>, where <em>N</em>
+corresponds to the position of the corresponding function address
+record in the module block. Function addresses must appear after the
+types block.</p>
+<p>The <em>globals block</em> [ref] defines global addresses for global variables
+and constants, used in the program. This block not only defines the
+addresses, but the size of the corresponding memory associated with
+these addresses, and how the memory should be initialized.</p>
+<p>The globals block must appear in the module block, and after all
+function address records.  Global addresses (defined by the globals
+block) are of the form <em>&#64;gN</em>, where <em>N</em> is the (relative) position of
+the corresponding defining records.</p>
+<p>The <em>valuesymtab block</em> [ref] does not define any values. Rather, its
+only goal is to associate text names with previously defined global
+addresses (i.e. function, constant, and variable).  Each association
+is defined by a record in the Valuesymtab block. Currently, only
+<em>intrinsic</em> [ref] function addresses need a name. All other entries in
+this block are considered as a hint for debugging. The PNaCl
+translator may (or may not) pass these names to the running
+executable, allowing the (runtime) debugger to associate names with
+addresses.</p>
+<p>Each <em>function block</em> [ref] defines the implementation of a single
+function. Each function block defines the control-flow graph of the
+function, which consists of basic blocks and instructions. If
+constants are used within instructions, they are defined in a
+<em>constants block</em>, nested within the corresponding function block.</p>
+<p>All function blocks are associated with a corresponding function
+address. This association is (again) positional rather than
+explicit. That is, the Nth function block in a module block
+corresponds to the Nth defining function address record in the
+module block.</p>
+<p>Hence, within a function block, there is no explicit reference to the
+function address the block defines. For readability, PNaClAsm uses the
+corresponding function heading, associated with the corresponding
+function address record, even though that data does not appear in the
+corresponding records.</p>
+<p>Unlike other blocks, a function block defines multiple kinds of
+values: parameter, basic block, and instruction. Parameter IDs (in
+PNaClAsm) are identified using local IDs of the form <em>%pN</em>. Basic
+block IDs are identified using local IDs of the form
+<em>%bN</em>. Instructions that generate values are identified using local
+IDs of the form <em>%vN</em>.</p>
+<p>Hence, <em>%pN</em> denotes the Nth parameter of the function. <em>%bN</em> denotes
+the <em>Nth</em> basic block within the function. <em>%vN</em> denotes the value
+generated by the <em>Nth</em> instruction that generates a value. Note: <em>%vN</em>
+does not necessarily refer to the <em>Nth</em> instruction in the function
+block, because not all instructions generate values.</p>
+<p>Within a function block, basic blocks are not explicitly defined in
+the PNaCl records of a function block. Rather, the first record of the
+block identifies how many basic blocks appear in the control flow
+graph of the function. This record is then followed by a sequence of
+records, each record defining a single instruction. Special
+<em>terminating</em> [ref] (i.e. branch) instructions are used to determine
+block boundaries.</p>
+<p>Each <em>constants block</em> [ref] defines constants that are used by the
+enclosing function block. The purpose of the constant block is to
+merge all uses of a constant (within a function) into a single
+defining ID.  Constant IDs are of the form <em>%cN</em>, where <em>N</em>
+corresponds to the (relative) position of constant defined in the
+corresponding constants block.  The constants block must appear before
+any instruction.</p>
+<p>The <em>abbreviations block</em> [ref] is optional. If it is included, it is
+divided into sections.  Each section is a sequence of records. Each
+record in the sequence defines a user-defined abbreviation.  Each
+section defines abbreviations that can be applied to all (succeeding)
+blocks of a particular kind. These abbreviations ares denoted by the
+(global) ID of the form <em>&#64;aN</em>.</p>
+</section><section id="pnacl-records">
+<h2 id="pnacl-records">PNaCl Records</h2>
+<p>A PNaCl record is a non-empty sequence of unsigned, 64-bit,
+integers. A record is identified by the record <em>code</em>, which is the
+first element in the sequence. Record codes are unique within a
+specific kind of block, but are not necessarily unique accross
+different kinds of blocks. The record code acts as the variant
+descriminator (i.e. tag) within a block, to identify what type of
+record it is.</p>
+<p>Record codes are typically small numbers. In an ideal world, they
+would be a consecutive sequence of integers, starting at
+zero. However, the reality is that PNaCl records evolved over time
+(and actually started as LLVM records[ref]).  For backwards
+compatability, old numbers have not been reused, leaving gaps in the
+actual record code values used.</p>
+<p>The exception of using small numbers for record codes, are four
+special kinds of records.  What makes these four kinds of records
+special is that they either apply in multiple blocks, or don&#8217;t occur
+in any block. To make these cases clear, and to leave room for lots of
+future growth in PNaClAsm, these special records have record codes
+close to value 2**16. Note: Well-formed PNaCl bitcode files do not
+have record codes &gt;= 2**16.</p>
+<p>A PNaCl record is denoted as follows:</p>
+<pre class="prettyprint">
+&lt;v1, v2, ... , vN&gt;
+</pre>
+<p>The value <em>v1</em> is the record code. The remaining values, <em>v2</em> through
+<em>vN</em>, are parameters that fill in additional information needed by the
+construct it represents. All records must hava record code. Hence,
+empty PNaCl records are not allowed.</p>
+<p>While most records (for a given record code) are of the same length,
+it is not true of all record codes. Some record codes, such as the
+records for the call instruction, can have arbitrary length.</p>
+<p>In PNaClAsm, if the record is converted to a bit sequence using the
+default abbreviation, no additional notation is used. Otherwise, the
+record is prefixed with the the abbreviation ID <em>I</em> to use (wrt the
+block it appears in) as follows:</p>
+<pre class="prettyprint">
+I: &lt;v1, v2, ... , vN&gt;
+</pre>
+<p>The PNaCl bitcode writer, which converts records to bit sequences,
+does this by writing out the abbreviation index used to encode the
+record, followed by the contents of the PNaCl record. The details of
+this are left to section on abbreviations[ref]. However, at the PNaCL
+record level, one important aspect of this appears in block enter
+records.  These records must define how many bits are required to hold
+abbreviation indices associated with records of that block.</p>
+<p>There are 4 predefined (default) abbreviation indices, used as the
+default abbreviations for PNaCl records. A block may (in addition),
+define a list of block specific, user-defined, abbreviations (of
+length <em>U&amp;). The number of bits *B</em> specified for an enter
+record must be sufficiently large such that</p>
+<pre class="prettyprint">
+2**B &gt;= U + 4
+</pre>
+<p>In addition, the upper limit for B is 32.</p>
+<p>Like much of PNaClAsm, PNaClAsm requires that you specify sizes
+(associated with a block) up front so that the PNaCl bitcode
+reader/writer can determine how to encode abbreviation indices. Hence,
+within an enter block record, you must specify how bits will be used
+to hold abbreviation indexes.</p>
+</section><section id="conventions-for-describing-records">
+<h2 id="conventions-for-describing-records">Conventions for describing records</h2>
+<p>The PNaClAsm assembler can be viewed as a parser of PNaCl records. The
+Each PNaCl record is described by a corresponding PNaClAsm
+construct. These constructs are described using syntax rules, and
+semantics on how they are converted to records. The parser also has
+state, that is updated after the instruction is parsed.  These state
+updates are part of the sementics of the corresponding record
+construct.</p>
+<p>For each PNaCl construct, we define multiple subsections. The <strong>Syntax</strong>
+subsection defines a syntax rule for the construct. The <strong>Record</strong>
+subsection defines the corresponding record associated with the syntax
+rule. The <strong>Semantics</strong> subsection describes the semantics
+associated with the record, in terms of data within the parse state
+and the corresponding syntax.</p>
+<p>The <strong>Constraints</strong> subsection (if present) defines any constraints
+associated with the construct. The <strong>Updates</strong> subsection (if present)
+defines how the parse state is updated when the construct is parsed.
+The <strong>Examples</strong> subsection gives one (or more) examples of using the
+corresponding PNaClAsm construct.</p>
+<p>Some semantics subsections use functions to compute values. The
+meaning of functions can be found in <em>Support Functions</em> [ref].</p>
+<p>Within a syntax rule, there may specifications about abbreviations.
+These abbreviation specifications, if allowed, are at the end of the
+construct, and enclosed in <em>&lt;</em> and <em>&gt;</em> bracket. These abbreviation
+specifications are optional in the syntax, and can be omitted. If they
+are used, the abbreviation brackets are part of the actual syntax of
+the construct. To make it clear that abbreviation specifications are
+optional, syntax rules separate abbreviation specifications using
+plenty of whitespace.</p>
+<p>Abbreviation specifications consist of user-defined abbreviations,
+abbreviation identifiers, and the number of bits required to repressent
+abbreviations in a block. These notations appear, as appropriate, in
+the corresponding syntax rules.</p>
+<p>The most common abbreviation syntax is the corresponding abbreviation
+identifier to use to read/write the corresponding record. In such
+cases, if the specified abbreviation identifier is omitted, the
+corresponding default abbreviation will be used by the PNaCl
+reader/writer.</p>
+<p>Also, within PNaClAsm, all alphabetic characters are lower case unless
+they appear within a literal value. Hence, if we mix lower and upper
+case letters within a name appearing in a syntax rule, the lower case
+letters are literal while the upper case sequence of letters denote
+(rule specific) values. If an upper case sequence of letters is
+followed by digits, the corresponding embedded name includes both the
+upper case letters and the digits.  The valid values for each of these
+names will be defined in the corresponding semantics subsection.</p>
+<p>For example, consider the following syntax rule:</p>
+<pre class="prettyprint">
+%vN = add T O1, O2;                            &lt;A&gt;
+</pre>
+<p>This rule defines a PNaClAsm add instruction.  This construct defines
+an instruction that adds to two values (<em>O1</em> and <em>O2</em>) to generate
+instruction value <em>%vN</em>. The types of the arguments, and the result,
+are all of type <em>T</em>. Since abbreviation ID <em>A</em> is present,  the
+record is encoded using that abbreviation.</p>
+<p>To be concrete, the syntactic rule above defines the structure of the
+following PNaClAsm examples.</p>
+<pre class="prettyprint">
+%v10 = add i32 %v1, %v2;  &lt;&#64;a5&gt;
+%v11 = add i32 %v10, %v3;
+</pre>
+<p>In addition to specifying the syntax, each syntax rule also specifies
+the contents of the corresponding record in the corresponding record
+subsection. In simple cases, the elements of the corresponding record
+are predefined (literal) constants. Otherwise the record element is a
+name that is defined by the other subsections associated with the
+construct.</p>
+</section><section id="parse-state">
+<h2 id="parse-state">Parse State</h2>
+<p>This section describes the parse state of the PNaClAsm assembler. It
+is used to define contextual data that is carried between records. The
+following subsections describes each element of the parse state.</p>
+<section id="typing">
+<h3 id="typing">Typing</h3>
+<p>Associated with most identifiers is a type. This type defines what
+type the corresponding value has. It is defined by the (initially
+empty) map</p>
+<pre class="prettyprint">
+TypeOf: ID -&gt; Type
+</pre>
+<p>For each type in the <em>types block</em> [ref], a corresponding inverse map</p>
+<pre class="prettyprint">
+TypeID: Type -&gt; ID
+</pre>
+<p>is maintained to convert syntactic types to the corresponding type ID.
+Note: This document assumes that map <em>TypeID</em> is automatically
+maintained during updates to map <em>TypeOf</em> (when given a type
+ID). Hence, <em>updates</em> subsections will not contain assignments to this
+map.</p>
+<p>Associated with each function identifier is it&#8217;s type signature. This
+is different than the type of the function identifer, since function
+identifiers are pointers (and always implemented as a 32-bit integer).</p>
+<p>Function type signatures are maintained using:</p>
+<pre class="prettyprint">
+TypeOfFcn: ID -&gt; Type
+</pre>
+<p>In addition, if a function address is defining, there is a corresponding
+implementation associated with the function address. To capture this association,
+we use the set:</p>
+<pre class="prettyprint">
+DefiningFcnIDs: set(ID)
+</pre>
+</section><section id="id-counters">
+<h3 id="id-counters">ID Counters</h3>
+<p>Each block defines one (or more) kinds of values.  Value indices are
+generated sequentially, starting at zero. To capture this, the
+following counters are defined:</p>
+<dl class="docutils">
+<dt>NumTypes</dt>
+<dd>The number of types defined so far (in the types block)</dd>
+<dt>NumFuncAddresses</dt>
+<dd>The number of function addresses defined so far (in the module
+block).</dd>
+<dt>NumDefinedFcnAddresses</dt>
+<dd>The number of defining function addresses defined so far (in the
+module block).</dd>
+<dt>NumFuncImpls</dt>
+<dd>The number of implemented functions defined so far (in the module block).</dd>
+<dt>NumGlobalAddresses</dt>
+<dd>The number of global variable/constant addresses defined so far (in
+the globals block).</dd>
+<dt>NumParams</dt>
+<dd>The number of parameters defined for a function.</dd>
+<dt>NumFcnConsts</dt>
+<dd>The number of constants defined in a fucntion.</dd>
+<dt>NumBasicBlocks</dt>
+<dd>The number of basic blocks defined so far (within a function block).</dd>
+<dt>NumValuedInsts</dt>
+<dd>The number of instructions, generating values, defined so far
+(within a function block).</dd>
+</dl>
+</section><section id="size-variables">
+<h3 id="size-variables">Size Variables</h3>
+<p>A number of blocks define expected sizes of constructs. These sizes are recorded
+in the following size variables:</p>
+<dl class="docutils">
+<dt>ExpectedBasicBlocks</dt>
+<dd>The expected number of basic blocks within a function
+implementation.</dd>
+<dt>ExpectTypes</dt>
+<dd>The expected number of types defined in the Types Block.</dd>
+<dt>ExpectedGlobals</dt>
+<dd>The expected number of global variable/constant addresses in the
+globals block.</dd>
+<dt>ExpectedInitializers</dt>
+<dd>The expected number of initializers for a global variable/constant
+address in the globals block.</dd>
+</dl>
+</section><section id="other-variables">
+<h3 id="other-variables">Other Variables</h3>
+<dl class="docutils">
+<dt>EnclosingFcnID</dt>
+<dd>The function ID of the function block being processed.</dd>
+</dl>
+</section></section><section id="special-records">
+<h2 id="special-records">Special records</h2>
+<p>There are four special PNaCl records, each having their own record
+code. These special records are:</p>
+<dl class="docutils">
+<dt>Header</dt>
+<dd>The header record is the first record of a PNaCl bitcode file, and
+identifies the file&#8217;s magic number, as well as the bitcode version it
+uses. The record defines the sequence of bytes that make up the
+header and uniquely identifies the file as a PNaCl bitcode file.</dd>
+<dt>Enter</dt>
+<dd>An enter record defines the beginning of a block. Since blocks
+can be nested, it can appear inside other blocks, as well as at the
+top level.</dd>
+<dt>Exit</dt>
+<dd>An exit record defines the end of a block. Hence, it must appear in
+every block, to end the block.</dd>
+<dt>Addreviation</dt>
+<dd>An abbreviation record defines a user-defined abbreviation to be
+applied to records within blocks.  Abbreviation records appearing in
+the abbreviations block define global abbreviations. All other
+abbreviations are local to the block they appear in, and can only be
+used in that block.</dd>
+</dl>
+<p>All special records can&#8217;t have user-defined abbreviations associated
+with them. The default abbreviation is always used.</p>
+<p>The following subsections define valid special records, other than abbreviation
+records. Abbreviation records are described in the Abbreviations[ref] section.</p>
+<section id="header-record">
+<h3 id="header-record">Header Record</h3>
+<p>The header record must be the first record in the file. It is the only
+record in the bitcode file that doesn&#8217;t have a corresponding construct
+in PNaClAsm. Rather, the PNaClAsm assembler always automatically
+inserts this record as the first record of the PNaCl bitcode file.</p>
+<p><strong>Syntax</strong></p>
+<p>There is no syntax for header records in PNaClAsm. They are
+automatically inserted by the PNaCl bitcode writer.</p>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+&lt;66532, 80, 69, 88, 69, 1, 0, 8, 0, 17, 0, 4, 0, 2, 0, 0, 0&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>The header record defines the initial sequence of bytes that must
+appear at the beginning of all (PNaCl bitcode version 2) files. That
+sequence is the list of bytes inside the record (excluding the record
+code). As such, it uniquely identifies PNaCl bitcode files.</p>
+<p><strong>Examples</strong></p>
+<p>There are no examples for the header record, since it is not part of
+PNaClAsm.</p>
+</section><section id="enter-block-record">
+<h3 id="enter-block-record">Enter Block Record</h3>
+<p>Block records can be top-level, as well as nested in other
+blocks. Blocks must begin with an <em>enter</em> record, and end with
+an <em>exit</em> record.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+N {                                             &lt;B&gt;
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+&lt;655335, BlockID, B&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>Enter block records define the beginning of a block.  <em>B</em>, if present,
+is the number of bits needed to represent all possible abbreviation
+indices used within the block. If omitted, B=2 is always assumed.</p>
+<p>The <em>BlockID</em> value is dependent on the name <em>N</em>. Valid names and
+corresponding <em>BlockID</em> values are defined as follows:</p>
+<table border="1" class="docutils">
+<colgroup>
+</colgroup>
+<thead valign="bottom">
+<tr class="row-odd"><th class="head">Name</th>
+<th class="head">BlockID</th>
+</tr>
+</thead>
+<tbody valign="top">
+<tr class="row-even"><td>abbreviations</td>
+<td>0</td>
+</tr>
+<tr class="row-odd"><td>constants</td>
+<td>11</td>
+</tr>
+<tr class="row-even"><td>function</td>
+<td>12</td>
+</tr>
+<tr class="row-odd"><td>globals</td>
+<td>19</td>
+</tr>
+<tr class="row-even"><td>module</td>
+<td>8</td>
+</tr>
+<tr class="row-odd"><td>types</td>
+<td>17</td>
+</tr>
+<tr class="row-even"><td>valuesymtab</td>
+<td>14</td>
+</tr>
+</tbody>
+</table>
+<p>Note: For readability, PNaClAsm allows a more readable form of a
+function block enter record.  See <em>function blocks</em> [ref] for more
+details.</p>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+module {
+  types {
+    count: 0;
+  }
+  globals {
+    count: 0;
+  }
+}
+</pre>
+<p>This example defines a module, types, and globals block. Both the type
+and the modules block appears within the module block.</p>
+<p>The corresponding records are:</p>
+<pre class="prettyprint">
+&lt;655335, 8, 2&gt;
+&lt;655335, 17, 2&gt;
+&lt;1, 0&gt;
+&lt;655334&gt;
+&lt;655335, 19, 2&gt;
+&lt;5, 0&gt;
+&lt;655334&gt;
+&lt;655334&gt;
+</pre>
+</section><section id="exit-block-record">
+<h3 id="exit-block-record">Exit Block Record</h3>
+<p>Block records can be top-level, as well as nested, records. Blocks must begin
+with an <em>enter</em> record, and end with an <em>exit</em> record.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+}
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+&lt;65536&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>All exit records are identical, no matter what block they are ending. An
+exit record defines the end of the block.</p>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+module {
+  types {
+    count: 0;
+  }
+  globals {
+    count: 0;
+  }
+}
+</pre>
+<p>This example defines a module, types, and globals block. Both the type
+and the modules block appears within the module block.</p>
+<p>The corresponding records are:</p>
+<pre class="prettyprint">
+&lt;655335, 8, 2&gt;
+&lt;655335, 17, 2&gt;
+&lt;1, 0&gt;
+&lt;655334&gt;
+&lt;655335, 19, 2&gt;
+&lt;5, 0&gt;
+&lt;655334&gt;
+&lt;655334&gt;
+</pre>
+</section></section><section id="types-block">
+<h2 id="types-block">Types Block</h2>
+<p>The types block defines all types used in a program. It must appear in
+the module block, before any function address records, the globals
+block, the valuesymtab block, and any function blocks.</p>
+<p>Each record in the types block defines a type used by the program.
+Types can be broken into the following groups:</p>
+<dl class="docutils">
+<dt>Primitive types</dt>
+<dd>Defines the set of base types for values. This includes various
+sizes of integral and floating types, as well as vector types.</dd>
+<dt>Void type</dt>
+<dd>A primitive type that doesn&#8217;t represent any value and has no size.</dd>
+<dt>Function types</dt>
+<dd>The type signatures of functions.</dd>
+<dt>Vector type</dt>
+<dd>Defines vectors of primitive types.</dd>
+</dl>
+<p>In addition, any type that is not defined using another type is a
+primitive type.  All other types (i.e. function and vector)are
+composite types.</p>
+<p>Types must be defined in a topological order, causing primitive types
+to apear before the composite types that use them.  There are no
+additional restrictions on the order that types can be defined in a
+types block.</p>
+<p>The following subsections introduces each valid PNaClAsm type, and the
+corresponding PNaClAsm construct that defines the type. Types not
+defined in the types block, can&#8217;t be used in a PNaCl program.</p>
+<p>The first record of a types block must be a <em>count</em> record, defining
+how many types are defined by the types block. All remaining records
+defines a type. The following subsections define valid records within
+a types block. The order of type records is important. The position of
+these defining records implicitly define the type ID that will be used
+to denote that type, within other PNaCl records of the bitcode file.</p>
+<p>To make this more concrete, consider the following example types
+block:</p>
+<pre class="prettyprint">
+types {
+  count: 4;
+  &#64;t0 = void;
+  &#64;t1 = i32;
+  &#64;t2 = float;
+  &#64;t3 = void (i32, float);
+}
+</pre>
+<p>This example defines a types block that defines four type IDs:</p>
+<ol class="arabic simple" start="0">
+<li>The void type.</li>
+<li>A 32-bit integer type.</li>
+<li>A 32-bit floating type.</li>
+<li>A function, taking 32-bit integer and float arguments, and returns void.</li>
+</ol>
+<p>Note that the order defines the corresponding ID that will be used for
+that type, is based on the position of the type within the types
+record. Hence, the assignment to ID &#64;tN can never appear before the
+assignment to ID &#64;tN-1. Further, if type ID &#64;tN is assigned, it must
+appear immediatedly after the assignment to ID &#64;tN-1.</p>
+<section id="count-record">
+<h3 id="count-record">Count Record</h3>
+<p>The <em>count record</em> defines how many types are defined in the
+types block. Following the types count record are records that define
+types used by the PNaCl program.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+count: N;                                       &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<blockquote>
+<div>I: &lt;1, N&gt;</div></blockquote>
+<p><strong>Semantics</strong></p>
+<p>This construct defines the number of types used by the PNaCl program.
+<em>N</em> is the number of types defined in the types block. It is an error
+to define more (or less) types than value <em>N</em>, within the enclosing
+types block. <em>I</em> is the (optional) abbreviation associated with the
+record.</p>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+ExpectedTypes = N;
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+types {
+  count: 2;
+  &#64;t0 = float;
+  &#64;t1 = i32;
+}
+</pre>
+<p>This example defines that the only types used by the PNaCl program are
+are 32 bit integer and floating type.</p>
+<p>The corresponding PNaCl Records are:</p>
+<pre class="prettyprint">
+&lt;655335, 17, 2&gt;
+&lt;1, 2&gt;
+&lt;3&gt;
+&lt;7, 32&gt;
+&lt;655334&gt;
+</pre>
+</section><section id="void-type">
+<h3 id="void-type">Void Type</h3>
+<p>The <em>void</em> type record defines the void type, which corrresponds to
+the type that doesn&#8217;t define any value, and has no size.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+&#64;tN = void;                                     &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;2&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>The void type record defines the type that has no values and has no
+size.  <em>I</em> is the (optional) abbreviation associated with the record.</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+N == NumTypes
+NumTypes &lt; ExpectedTypes
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+++NumTypes;
+TypeOf(&#64;tN) = void;
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+&#64;t0 = void;
+</pre>
+<p>defines the record</p>
+<pre class="prettyprint">
+&lt;2&gt;
+</pre>
+</section><section id="integer-types">
+<h3 id="integer-types">Integer Types</h3>
+<p>PNaClAsm allows integral types for various bit sizes. Valid bit sizes
+are 1, 8, 16, 32, and 64. Integers can be signed or unsigned, but the
+signed component of in integer is not specified by the type. Rather,
+individual instructions determine whether the value is assumed to be
+signed or unsigned.</p>
+<p>It should be noted that in PNaClAsm, all pointers are implemented as
+32-bit (unsigned) integers.  There isn&#8217;t a separate type for
+pointers. The only way to tell that a 32-bit integer is a pointer, is
+when it is used in an instruction that requires a pointer (such as
+load and store instructions).</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+&#64;tN = iB;                                      &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<blockquote>
+<div>I: &lt;7, B&gt;</div></blockquote>
+<p><strong>Semantics</strong></p>
+<p>An integer type record defines an integral type. <em>B</em> defines the
+number of bits of the integral type.  <em>I</em> is the (optional)
+abbreviation associated with the record.</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+N == NumTypes
+NumTypes &lt; ExpectedTypes
+B in {1, 8, 16, 32, 64}
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+++NumTypes;
+TypeOf(&#64;tN) = iB;
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+&#64;t1 = i32;
+&#64;t2 = i1;
+&#64;t3 = i64;
+</pre>
+<p>defines the records</p>
+<pre class="prettyprint">
+&lt;7, 32&gt;
+&lt;7, 1&gt;
+&lt;7, 64&gt;
+</pre>
+</section><section id="bit-floating-type">
+<h3 id="bit-floating-type">32-Bit Floating Type</h3>
+<p>PNaClAsm allows computation on 32-bit floating values. A floating type
+record defines the 32-bit floating type.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+&#64;tN = float;                                    &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;3&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>A floating type record defines the 32-bit floating type.  <em>I</em> is the
+(optional) abbreviation associated with the record.</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+N == NumTypes
+NumTypes &lt; ExpectedTypes
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+++NumTypes;
+TypeOf(&#64;tN) = float;
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+&#64;t5 = float;
+</pre>
+<p>defines the record</p>
+<pre class="prettyprint">
+&lt;3&gt;
+</pre>
+</section><section id="id1">
+<h3 id="id1">64-bit Floating Type</h3>
+<p>PNaClAsm allows computation on 64-bit floating values. A double type
+record defines the 64-bit floating type.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+&#64;tN = double;                                   &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;4&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>A double type record defines the 64-bit floating type.  <em>I</em> is the
+(optional) abbreviation associated with the record.</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+N == NumTypes
+NumTypes &lt; ExpectedTypes
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+++NumTypes;
+TypeOf(&#64;tN) = double;
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+&#64;t3 = double;
+</pre>
+<p>defines the record</p>
+<pre class="prettyprint">
+&lt;4&gt;
+</pre>
+</section><section id="vector-types">
+<h3 id="vector-types">Vector Types</h3>
+<p>TBD.</p>
+</section><section id="function-types">
+<h3 id="function-types">Function Types</h3>
+<p>TBD.</p>
+</section></section><section id="globals-block">
+<h2 id="globals-block">Globals block</h2>
+<p>The globals block defines global addresses of variables and constants,
+used by the PNaCl program. It also defines the memory associated with
+the global addresses, and how to initialize each global
+variable/constant. It must appear in the module block. It must appear
+after the types block, as well as after all function address
+records. But, it must also appear before the valuesymtab block, and
+any function blocks.</p>
+<p>The globals block begins with a count record, defining how many global
+addresses are defined by the PNaCl program. It is then followed by a
+sequence of records that defines how each global addresss is
+initialized.</p>
+<p>The standard sequence, for defining global addresses, begins with a
+global address record.  It is then followed by a sequence of records
+defining how the global address is initialized.  If the initializer is
+simple, a single record is used. Otherwise, the initializer is
+preceded with a compound record, specifying a number <em>N</em>, followed by
+sequence of <em>N</em> simple initializer records.</p>
+<p>The size of the memory referenced by each global address is defined by
+its initalizer records. All simple initializer records define a
+sequence of bytes. A compound initializer defines a sequence of bytes
+by concatenating corresponding sequence of bytes for each of its
+simple initializer records.</p>
+<p>For notational convenience, PNaClAsm begins a compound record with a
+&#8220;{&#8221;, and inserts a &#8220;}&#8221; after the last initializer record associated
+compound record. This latter &#8220;}&#8221; does not correspond to any record. It
+is implicitly assumed by the size specified in the compound record,
+and is added only to improve readability.</p>
+<p>For example, consider the following:</p>
+<pre class="prettyprint">
+globals {
+  count: 2;
+  const &#64;g0, align 1,
+    zerofill 8;
+  var &#64;g1, align 4,
+    initializers 2 {
+      {1, 2, 3, 4},
+      zerofill 2;
+    }
+}
+</pre>
+<p>In this example, the globals block contains 9 records. All lines,
+inside the block delimiters of this example (except the second to
+last) defines a record. The first record defines the number of global
+addresses defined by the program, i.e. 2. The second defines that
+second global addresses will be defined.</p>
+<p>The third record defines the global constant address <em>&#64;g0</em>, and it&#8217;s
+corresponding memory layout alignment. The forth record defines to
+initialize the constant with 8 bytes, all with the value zero. This
+size of <em>&#64;g0</em> is 8 bytes.</p>
+<p>The fifth record defines the global variable address <em>&#64;g1</em>, and it&#8217;s
+corresponding memory layout alignment. The sixth record defines that
+the initial value of <em>&#64;g1</em> is defined by the sequence of bytes defined
+by the following 2 initializer records. The seventh record defines that
+the first 4 bytes of <em>&#64;g1</em> are initialized with bytes 1, 2, 3, 4. The
+eighth record initializes bytes 5 and 6 to zero. The size of <em>&#64;g2</em> is
+therefore 6 bytes.</p>
+<p>The nine record is the exit block record.</p>
+<p>In other words, the corresponding records are:</p>
+<pre class="prettyprint">
+&lt;655335, 19, 2&gt;
+&lt;5, 2&gt;
+&lt;0, 1, 1&gt;
+&lt;2, 8&gt;
+&lt;0, 4, 0&gt;
+&lt;1, 2&gt;
+&lt;3, 1, 2, 3, 4&gt;
+&lt;2, 2&gt;
+&lt;655334&gt;
+</pre>
+<section id="id2">
+<h3 id="id2">Count Record</h3>
+<p>The count record defines the number of global addresses used by the
+PNaCl program.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+count: N;                                       &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;5, N&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>This record must appear first in the globals block.  The count record
+defines the number of global addresses used by the program. <em>I</em> is the
+(optional) abbreviation associated with the record.</p>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+ExpectedGlobals = N;
+ExpectedInitializers = 0;
+</pre>
+</section><section id="global-variable-addressses">
+<h3 id="global-variable-addressses">Global Variable Addressses</h3>
+<p>A global variable address record defines a global address to global
+data.  The global variable address record must be immediatedly
+followed by initializer record(s) that define how the corresponding
+global variable is initialized.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+var &#64;gN, align A,                               &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;0, A, 0&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>A global varaible address record defines a global address for a global
+variable.  <em>A</em> is the alignment to for the global variable.  <em>I</em> is
+the (optional) abbreviation associated with the record.</p>
+<p>It is assumed that the memory, referenced by the global variable
+address, can be both read and written to.</p>
+<p>??? Valid values for A. Section defining notion of memory alignments ???</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+N == NumGlobalAddresses
+NumGlobalAddresses &lt; ExpectedGlobals
+ExpectedInitializers == 0
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+++NumGlobalAddresses;
+ExpectedInitializers = 1;
+TypeOf(&#64;gN) = i32;
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+var &#64;g0, align 1,
+  zerofill 8;
+var &#64;g1, align 1,
+  {1, 2, 3, 4}
+</pre>
+<p>This example defines two global variable addresses, <em>&#64;g0</em> and
+<em>&#64;g1</em>. Both use memory alignment of 1. <em>&#64;g0</em> is an 8 byte variable
+initialized to zero.  <em>&#64;g1</em> is a 4 byte variable, initialized by the
+sequence of bytes 1, 2, 3, and 4.</p>
+<p>The corresponding records defined by the example above are:</p>
+<pre class="prettyprint">
+&lt;0, 1, 0&gt;
+&lt;2, 8&gt;
+&lt;0, 1, 0&gt;
+&lt;3, 1, 2, 3, 4&gt;
+</pre>
+</section><section id="glboal-constant-addresses">
+<h3 id="glboal-constant-addresses">Glboal Constant Addresses</h3>
+<p>A global constant address record defines an address corresponding to a
+global constant that can&#8217;t be modified by the program. The global
+constant address record must be immediatedly followed by initializer
+record(s) that define how the corresponding global constant is
+initialized.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+const &#64;gN, align A,                             &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;0, A, 1&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>A global constant address record defines a global address for a global
+constant.  <em>A</em> is the memory alignment for the global constant. <em>I</em> is
+the (optional) abbreviation associated with the record.</p>
+<p>It is assumed that the memory, referenced by the global constant
+address, is only read, and can&#8217;t be written to.</p>
+<p>??? Valid values for A. Section defining notion of memory alignments ???</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+N == NumGlobalAddresses
+NumGlobalAddresses &lt; ExpectedGlobals
+ExpectedInitializers = 0
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+++NumGlobalAddresses;
+ExpectedInitializers = 1;
+TypeOf(&#64;gN) = i32;
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+const &#64;g0, align 1,
+  zerofill 8;
+var &#64;g1, align 1,
+  {1, 2}
+</pre>
+<p>This example defines two global constants, with global addresses <em>&#64;g0</em>
+and <em>&#64;g1</em>. Both use memory alignment of 1. <em>&#64;g0</em> is an 8 byte constant
+initialized to zero.  <em>&#64;g1</em> is a 2 byte variable, initialized by the
+sequence of bytes 1 and 2.</p>
+<p>The corresponding PNaCl bitcode records are:</p>
+<pre class="prettyprint">
+&lt;0, 1, 1&gt;
+&lt;2, 8&gt;
+&lt;0, 1, 1&gt;
+&lt;3, 1, 2&gt;
+</pre>
+</section><section id="zerofill-initializer">
+<h3 id="zerofill-initializer">Zerofill Initializer</h3>
+<p>The zerofill initializer record intializes a sequence of bytes,
+associated with a global address, with zeros.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+zerofill N;                                     &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;2, N&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>A zerofill initializer record intializes a sequence of bytes,
+associated with a global address, with zeros. <em>I</em> is the (optional)
+abbreviation of the associated record.</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+ExpectedInitializers &gt; 0;
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+--ExpectedInitializers;
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+const &#64;g0, align 1,
+  zerofill 8;
+var &#64;g1, align 1,
+  zerofill 4;
+</pre>
+<p>This example defines two global constants, with global addresses <em>&#64;g0</em>
+and <em>&#64;g1</em>.  The global memory associated with address <em>&#64;g0</em>, is an
+eight byte value, initialized to zero.  The global memory associated
+with address <em>&#64;g1</em>, is a 4 byte value, initialized to zero.</p>
+<p>The corresponding PNaCl records are:</p>
+<pre class="prettyprint">
+&lt;0, 1, 1&gt;
+&lt;2, 8&gt;
+&lt;0, 1, 1&gt;
+&lt;2, 4&gt;
+</pre>
+</section><section id="data-initializer">
+<h3 id="data-initializer">Data Initializer</h3>
+<p>Data records define a sequence of bytes, defining the contents of the
+corresponding memory. The bytes defined by a data record corresponds
+the the corresponding bytes the memory will be initialized with.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+{ B1 , .... , BN }                              &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;3, B1, ..., BN&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>A data record defines a sequence of bytes <em>B1</em> throught <em>BN</em>, that
+intialize <em>N</em> bytes of memory. <em>I</em> is the (optional) abbreviation
+associated with the record.</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+ExpectedInitializers &gt; 0
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+--ExpectedInitializers;
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+const &#64;g0, align 1,
+  {1, 2, 97, 36, 44, 88, 44}
+const &#64;g1, align 1
+  initializers 3 {
+    {4, 5, 6, 7}
+    reloc &#64;f1;
+    {99, 66, 22, 12}
+  }
+</pre>
+<p>The corresponding PNaCl records are:</p>
+<pre class="prettyprint">
+&lt;0, 1, 1&gt;
+&lt;3, 1, 2, 97, 36, 44, 88, 44&gt;
+&lt;0, 1, 1&gt;
+&lt;1, 3&gt;
+&lt;3, 4, 5, 6, 7&gt;
+&lt;4, 1&gt;
+&lt;3, 99, 66, 22, 12&gt;
+</pre>
+</section><section id="relocation-initializer">
+<h3 id="relocation-initializer">Relocation Initializer</h3>
+<p>A relocation initializer record allows one to fill the initial value
+with the value of another global address (i.e. either function,
+variable, or constant). Since addresses are pointers, and in PNaClAsm
+all pointers are of integral type i32, a relocation initializer record
+defines 4 bytes of memory.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+reloc A;                                        &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;4, N&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>A relocation initializer record defines a 4-byte value containing the
+specified global address <em>A</em>. <em>N</em> is the absolute index associated
+with address <em>A</em>. <em>I</em> is the (optional) abbreviation associated with
+the record.</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+N == AbsoluteIndex(A);
+ExpectedInitializers &gt; 0
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+--ExpectedInitializers;
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+var &#64;g0, align 1,
+  initializers 3 {
+    reloc &#64;f1;
+    reloc &#64;g0;
+    reloc &#64;g10;
+  }
+</pre>
+<p>This example defines global address <em>&#64;g0</em>. It defines 12 bytes of
+memory, and is initialized with three addresses <em>&#64;f1</em>, <em>&#64;g0</em>, and
+<em>&#64;g10</em>. Note that all globals can be used in a relocation
+initialization record, even if it isn&#8217;t defined yet.</p>
+<p>Assuming</p>
+<pre class="prettyprint">
+100 = AbsoluteIndex(&#64;g0))
+</pre>
+<p>The corresponding PNaCl bitcode records are:</p>
+<pre class="prettyprint">
+&lt;0, 1, 0&gt;
+&lt;1, 3&gt;
+&lt;4, 1&gt;
+&lt;4, 100&gt;
+&lt;4, 110&gt;
+</pre>
+</section><section id="subfield-relocation-initializer">
+<h3 id="subfield-relocation-initializer">Subfield Relocation Initializer</h3>
+<p>A subfield relocation initializer record allows one to fill the
+initial value with the value of another (non-function) global address
+(i.e. either variable or constant), plus a constant. This constant
+must refer to an offset within the memory associated with the global
+address. Since addresses are pointers, and in PNaClAsm all pointers
+are of integral type i32, a relocation initializer record defines 4
+bytes of memory.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+reloc A + V;                                    &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;4, N, V&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>A relocation initializer record defines a 4-byte value containing the
+specified global (non-funciton) address <em>A</em>, modified by the (unsigned
+integer) offset <em>V</em>. <em>N</em> is the absolute indexassociated with <em>A</em>. The
+size of <em>V</em> must refer to a byte in the memory associated with address
+<em>A</em>. <em>I</em> is the (optional) abbreviation associated with the record.</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+N == AbsoluteIndex(A)
+V &gt;= 0
+ExpectedInitializers &gt; 0
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+--ExpectedInitializers;
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+var &#64;g0, align 1,
+  initializers 3 {
+    reloc &#64;f1;
+    reloc &#64;g0 + 4;
+    reloc &#64;g10 + 32;
+  }
+</pre>
+<p>This example defines global address <em>&#64;g0</em>, and is initialized with
+three pointers, addresses <em>&#64;f1</em>, <em>&#64;g0+4</em>, and <em>&#64;g10+32</em>. Note that all
+global addresses can be used in a relocation initialization record,
+even if it isn&#8217;t defined yet. Validity of the reference can be
+verified, since a global address <em>&#64;g10</em> must be smaller than the value
+specified in the globals count record.</p>
+<p>Assuming</p>
+<pre class="prettyprint">
+100 = AbsoluteIndex(&#64;g0))
+</pre>
+<p>The corresponding PNaCl bitcode records are:</p>
+<pre class="prettyprint">
+&lt;0, 1, 0&gt;
+&lt;1, 3&gt;
+&lt;4, 1&gt;
+&lt;4, 100, 4&gt;
+&lt;4, 110, 32&gt;
+</pre>
+</section><section id="compound-initializer">
+<h3 id="compound-initializer">Compound Initializer</h3>
+<p>The compound initializer record must immediately follow a global variable/constant
+address record. It defines how many (non-compound) initializer records are used to
+define the initializer. The size of the corresponding memory is the sum of the bytes
+needed for each of the succeeding initializers.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+initializers N {                                &lt;I&gt;
+ ...
+}
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;1, N&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>Defines that the next <em>N</em> initializers should be associated with the
+global address of the previous record. <em>I</em> is the (optional)
+abbreviation index associated with the record.</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+ExpectedInitializers == 1
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+ExpectedInitializers = N;
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+const &#64;g1, align 1
+  initializers 3 {
+    {4, 5, 6, 7}
+    reloc &#64;f1;
+    {99, 66, 22, 12}
+  }
+</pre>
+<p>The corresponding PNaCl records are:</p>
+<pre class="prettyprint">
+&lt;0, 1, 1&gt;
+&lt;1, 3&gt;
+&lt;3, 4, 5, 6, 7&gt;
+&lt;4, 1&gt;
+&lt;3, 99, 66, 22, 12&gt;
+</pre>
+</section></section><section id="valuesymtab-block">
+<h2 id="valuesymtab-block">Valuesymtab Block</h2>
+<p>TBD.</p>
+</section><section id="module-block">
+<h2 id="module-block">Module Block</h2>
+<p>The module block, like all blocks, are enclosed in a pair of
+enter/exit records, using block ID 8. A well-formed module block
+consists The following records (in order):</p>
+<dl class="docutils">
+<dt>A version record</dt>
+<dd>The version record communicates the version of the PNaCl bitcode
+reader/writer to use. Note that this is different than the PNaCl
+bitcode (ABI) verion. The PNaCl bitcode (ABI) version defines what
+is expected in records, and is defined in the header record of the
+bitcode file. The version record defines the version of the PNaC
+bitcode reader/writer to use to convert records into bit
+sequences.</dd>
+<dt>Optional local abbreviations</dt>
+<dd>Defines a list of local abbreviations to use for records within
+the module block.</dd>
+<dt>An optional abbreviations block</dt>
+<dd>The abbreviations block defines user-defined, global abbreviations
+that are used to convert PNaCl records to bit sequences in blocks
+following the abbreviations block.</dd>
+<dt>A types block</dt>
+<dd>The types block defines the set of all types used in the program.</dd>
+<dt>A non-empty sequence of function address records</dt>
+<dd>Each record defines a function address used by the
+program. Function addresses must either be external, or defined
+internally by the program. If they are defined by the program,
+there must be a function block (appearing later in the module)
+that defines the sequence of instructions for each defined
+function.</dd>
+<dt>A globals block defining the global variables.</dt>
+<dd>This block defines the set of global variable (addresses) used by
+the program. In addition to the addresses, each global variable
+also defines how the corresponding global variable is initialized.</dd>
+<dt>An optional value symbol table block.</dt>
+<dd>This block, if defined, provides textual names for function and
+global variable addresses (previously defined in the module). Note
+that only names for instrinsic functions must be provided. Any
+additional names are hints that may (or may not) be used by the
+PNaCl translator, and be available for debugging when executed.</dd>
+<dt>A sequence of function blocks.</dt>
+<dd>Each function block defines the corresponding control flow graph
+for each defined function. The order of function blocks is used to
+associate them with function addresses.  The order of the defined
+function blocks must follow the same order as the corresponding
+function addresses defined in the module block.</dd>
+</dl>
+<p>Descriptions of the abbreviations[ref], types[ref], global
+variables[ref], value symbol table[ref], and function[ref] blocks are
+not provided here. See the appropriate reference for more details. The
+following subsections describe each of the records that can appear in
+a module block.</p>
+<section id="version">
+<h3 id="version">Version</h3>
+<p>The version record defines the implementation of the PNaCl
+reader/writer that converts PNaCl records to bit sequences. Note that
+this is different than the PNaCl version of the bitcode file (encoded
+in the header record of the bitcode file).  The PNaCl version defines
+the valid forms of PNaCl records. The version record is specific to
+the PNaCl version, and may have different values for different PNaCl
+versions.</p>
+<p>Note that currently, only PNaCl version 2, and version record value 1
+is defined.  Larger version record values are reserved for future
+changes.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+version N;                                  &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;1, N&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>The version record defines which PNaCl reader/writer rules should be
+followed. <em>N</em> is the version number. Currently <em>N</em> must be 1. Future
+versions of PNaCl may define other values. <em>I</em> is the (optional)
+abbreviation index associated with the record.</p>
+<p><em>Examples</em></p>
+<pre class="prettyprint">
+version 1;
+</pre>
+<p>The corresponding record is:</p>
+<pre class="prettyprint">
+&lt;1, 1&gt;
+</pre>
+</section><section id="function-address">
+<h3 id="function-address">Function Address</h3>
+<p>A function address record defines a function address. Defining
+function addresses also imply a corresponding
+implementation. Implementations of function addresses are defined by a
+corresponding function block. The association of defining function
+address with the corresponding function block is based on position.
+The <em>Nth</em> defining function address record, in the module block, has
+its implementation in the <em>Nth</em> function block of that module block.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+PN LN T0 &#64;fN ( T1 , ... , TM );                 &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<p><strong>Semnatics</strong></p>
+<p>Defines the function address <em>&#64;fN</em>. <em>PN</em> is the name that specifies
+the prototype value <em>P</em> associated with the function. A function
+address is defining only if <em>P==0</em>. Otherwise, it is only declared.
+The type of the function is defined by function type <em>&#64;tT. *L</em>
+is the linkage specification corresponding to name <em>LN</em>. <em>C</em> is the
+calling convention used by the function.</p>
+<p>Type <em>&#64;tT</em> (associated with the corresponding syntax rules) is
+defined as:</p>
+<pre class="prettyprint">
+&#64;tT = TypeOf(T0 ( T1 , ... , TN ))
+</pre>
+<p>Valid prototype names <em>PN</em>, and corresponding <em>P</em> values, are:</p>
+<table border="1" class="docutils">
+<colgroup>
+</colgroup>
+<thead valign="bottom">
+<tr class="row-odd"><th class="head">P</th>
+<th class="head">PN</th>
+</tr>
+</thead>
+<tbody valign="top">
+<tr class="row-even"><td>1</td>
+<td>declare</td>
+</tr>
+<tr class="row-odd"><td>0</td>
+<td>define</td>
+</tr>
+</tbody>
+</table>
+<p>Valid linkage names <em>LN</em>, and corresponding <em>L</em> values, are:</p>
+<table border="1" class="docutils">
+<colgroup>
+</colgroup>
+<thead valign="bottom">
+<tr class="row-odd"><th class="head">L</th>
+<th class="head">LN</th>
+</tr>
+</thead>
+<tbody valign="top">
+<tr class="row-even"><td>3</td>
+<td>internal</td>
+</tr>
+<tr class="row-odd"><td>0</td>
+<td>external</td>
+</tr>
+</tbody>
+</table>
+<p>Currently, only one calling convention <em>C</em> is supported:</p>
+<table border="1" class="docutils">
+<colgroup>
+</colgroup>
+<thead valign="bottom">
+<tr class="row-odd"><th class="head">C</th>
+<th class="head">Calling Convention</th>
+</tr>
+</thead>
+<tbody valign="top">
+<tr class="row-even"><td>0</td>
+<td>C calling convention</td>
+</tr>
+</tbody>
+</table>
+<p><strong>Constraint</strong></p>
+<pre class="prettyprint">
+N == NumFuncAddresses
+</pre>
+<section id="updates">
+<h4 id="updates">Updates</h4>
+<pre class="prettyprint">
+++NumFuncAddresses;
+TypeOf(&#64;fN) = TypeOf(TypeID(i32));
+TypeOfFcn(&#64;fN) = TypeOf(&#64;tT);
+
+if PN == 0:
+  DefiningFcnIDs += &#64;FN;
+  ++NumDefinedFunctionAddresses;
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+module {
+  ...
+  types {
+    &#64;t0 = void;
+    &#64;t1 = i32;
+    &#64;t3 = float;
+    &#64;t4 = void (i32, float);
+    &#64;t5 = i32 ();
+  }
+  ...
+  declare external void &#64;f0(i32, float);
+  define internal i32 &#64;f1();
+</pre>
+<p>This defines function addresses <em>&#64;f0</em> and <em>&#64;f1</em>. Function address
+<em>&#64;f0</em> is defined externally while <em>&#64;f2</em> has an implementation (defined
+by a corresponding function block). The type signature of <em>&#64;f0</em> is
+defined by type <em>&#64;t4</em> while the type signature of <em>&#64;f1</em> is <em>&#64;t5</em>.</p>
+<p>The corresopnding records for these two function addresses are:</p>
+<pre class="prettyprint">
+&lt;8, 4, 0, 1, 0&gt;
+&lt;8, 5, 0, 0, 1&gt;
+</pre>
+</section></section></section><section id="constants-blocks">
+<h2 id="constants-blocks">Constants Blocks</h2>
+<p>TBD.</p>
+</section><section id="function-blocks">
+<h2 id="function-blocks">Function Blocks</h2>
+<p>A function block defines the implementation of a function address. The
+function address it defines is based on the position of the
+corresponding defining function address. The Nth defining function
+address always corresponds to the corresponding Nth function block in
+the module block.</p>
+<p>A function definition contains a list of basic block, forming the CFG
+(control flow graph). Each basic block contains a list of
+instructions, and ends with a <em>terminator</em> [ref] (branch) instruction.</p>
+<p>The first basic block in a function is special in two ways: it is
+immediately executed on entrance to the function, and it is not
+allowed to have predecessor basic blocks (i.e. there can&#8217;t be any
+branches to the entry block of a function). Because the entry block
+has no predecessors, it also can&#8217;t have any <em>PHI nodes</em> [ref].</p>
+<p>The parameters are implied by the type of the corresponding function
+address. One parameter is defined for each argument of the function
+type signature.</p>
+<p>The number of basic blocks are defined by the count record. Each
+termimintor instruction ends the current basic block, and the next
+instruction begins a new basic blocks.  Basic blocks are numbered by
+the order they appear (starting with index 0). Basic block IDs have
+the form <em>%bN</em>, where <em>N</em> corresponds to the position of the basic
+block within the function block.</p>
+<p>Each instruction, within a function block, corresponds to a
+corresponding PNaCl record.  The layout of a function block is the
+(basic block) count record, followed by a sequence of instruction
+records.</p>
+<p>For readability, PNaClAsm introduces block IDs. These block IDs do not
+correspond to PNaCl records, since basic block boundaries are defined
+implicitly, after terminator instructions. They appear only for
+readability.</p>
+<p>Most operands of instructions are encoded using a relative index
+value, rather than abolute. The is done because most instruction
+operands refer to values defined earlier in the (same) basic block.
+As a result, the relative distance (back) from the next defining
+instruction value index (for the function block) is frequently a small
+number. Small numbers tend to require less bits when they are
+converted to bit sequences. This distance is used in the corresponding
+records to denote the operand values.</p>
+<p>The following subsections define records that can appear in a function
+block.</p>
+<section id="function-enter">
+<h3 id="function-enter">Function enter</h3>
+<p>PNaClAsm defines a function enter block construct. The corresponding
+record is simply an enter block record, with BlockID value 12. All
+context about the defining address is implicit by the position of the
+function block, and the corresponding defining function address. To
+improve readability, PNaClAsm includes the function signature into the
+syntax rule.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+function TR &#64;fN ( T0 %p0, ... , TM %pM) {             &lt;B&gt;
+</pre>
+<p><strong>Record</strong></p>
+<blockquote>
+<div>&lt;655335, 12, B&gt;</div></blockquote>
+<p><strong>Semantics</strong></p>
+<p><em>B</em> is the number of bits reserved for abbreviations in the block. See
+enter block records[ref] for more details.</p>
+<p>The value of <em>N</em> corresponds the the positional index of the
+corresponding defining function address this block is associated
+with. <em>M</em> is the number of defined paramaters (plus one)
+in the function heading.</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+N == NumFcnImpls
+&#64;fN in DefiningFcnIDs
+TypeOfFcn(&#64;fN) == TypeOf(TypeID(TR (T0, ... , TM)))
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+++NumFcnImpls;
+EnclosingFcnID = &#64;fN;
+NumBasicBlocks = 0;
+ExpectedBlocks = 0;
+NumParams = M;
+for I in [0..M]:
+  TypeOf(%pI) = TypeOf(TypeID(TI));
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+types {
+  ...
+  &#64;t10 = void (i32, float);
+  ...
+}
+...
+define internal void &#64;f12(i32, float);
+...
+function void &#64;f12(i32 %p0, float %p1) {
+...
+}
+</pre>
+<p>defines the enter block record:</p>
+<pre class="prettyprint">
+&lt;655335, 12, 2&gt;
+</pre>
+</section><section id="id3">
+<h3 id="id3">Count Record</h3>
+<p>The count record, within a function block, defines the number of basic
+blocks used to define the function implementation.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+  blocks: N;                                    &lt;I&gt;
+%b0:
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;1, N&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>The count record defines the number of basic blocks <em>N</em>, defined by
+the implemented function. <em>I</em> is the (optional) abbreviation
+associated with the record.</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+ExpectedBasicBlocks == 0
+NumBasicBlocks == 0
+</pre>
+<section id="id4">
+<h4 id="id4">Updates</h4>
+<pre class="prettyprint">
+ExpectedBlocks = N;
+</pre>
+<p><strong>Examples</strong></p>
+<pre class="prettyprint">
+blocks: 5
+</pre>
+<p>The corresponding PNaCl bitcode record is:</p>
+<pre class="prettyprint">
+&lt;1, 5&gt;
+</pre>
+</section></section><section id="terminator-instructions">
+<h3 id="terminator-instructions">Terminator Instructions</h3>
+<p>Terminator instructions are instructions that appear in a function
+block, and define the end of the current basic block. A terminator
+instuction indicates which block should be executed after the current
+block is finished. The function block is well formed only if the number
+of terminator instructions, in the function block, corresponds to the
+value defined by the corresponding count block.</p>
+<section id="return-void-instruction">
+<h4 id="return-void-instruction">Return Void Instruction</h4>
+<p>The return void instruction is used to return control from a function
+back to the caller, without returning any value.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+  ret;                                          &lt;I&gt;
+%bB:
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;10&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>The return instruction returns control to the calling function.</p>
+<p><em>B</em> is the number associated with the next basic block. Label <em>%bB:</em>
+only appears if <em>B + 1 &lt; ExpectedBasicBlocks</em>. That is, the label is
+omitted only if this terminator instruction is the last instruction in
+the function block.  <em>I</em> is the (optional) abbreviation index
+associated with the record.</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+B == NumBasicBlocks
+NumBasicBlocks &lt; ExpectedBasicBLocks
+ReturnType(TypeOf(EnclosingFcnID)) == void
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+++NumBasicBlocks;
+</pre>
+<p><strong>Examples</strong></p>
+<p>The following shows the implementation of a function that simply returns.</p>
+<pre class="prettyprint">
+function void &#64;f5() {
+  ret;
+}
+</pre>
+<p>The corresponding PNaCl records are:</p>
+<pre class="prettyprint">
+&lt;655335, 12, 2&gt;
+&lt;10&gt;
+&lt;655334&gt;
+</pre>
+</section><section id="return-value-instruction">
+<h4 id="return-value-instruction">Return Value Instruction</h4>
+<p>The return value instruction is used to return control from a
+function back to the caller, including a value. The value must
+correspond to the return type of the enclosing function.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+  ret T V;                                      &lt;I&gt;
+%bB:
+</pre>
+<p><strong>Record</strong></p>
+<pre class="prettyprint">
+I: &lt;10, R&gt;
+</pre>
+<p><strong>Semantics</strong></p>
+<p>The return instruction returns control to the calling function,
+returning the provided value.</p>
+<p><em>V</em> is the value to return. <em>R</em> is the corresponding relative index
+defining the value to return.  Type <em>T</em> must be of the type returned
+by the function.  It must also be the type associated with value <em>V</em>.
+<em>I</em> is the (optional) abbreviation index associated with the record.</p>
+<p><em>B</em> is the number associated with the next basic block.  Label <em>%bB:</em>
+only appears if <em>B + 1 &lt; ExpectedBasicBlocks</em>. That is, the label is
+omitted only if this terminator instruction is the last instruction in
+the function block.</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+R = RelativeIndex(V)
+B == NumBasicBlocks
+NumBasicBlocks &lt; ExpectedBasicBlocks
+T == TypeOf(V) == ReturnType(TypeOf(EnclosingFcnID))
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+++NumBasicBlocks;
+</pre>
+<p><strong>Examples</strong></p>
+<p>The following shows a return statement that returns the value
+generated by the previous instruction:</p>
+<pre class="prettyprint">
+%v10 = add i32 %v1, &#64;v2;
+ret i32 &#64;v10;
+</pre>
+<p>The corresponding PNaCl records are:</p>
+<pre class="prettyprint">
+&lt;2, 9, 8, 0&gt;
+&lt;10, 1&gt;
+</pre>
+</section><section id="unconditional-branch-instruction">
+<h4 id="unconditional-branch-instruction">Unconditional Branch Instruction</h4>
+<p>The unconditional branch instruction is used to cause control flow to
+transfer to a different basic block of the function.</p>
+<section id="syntax">
+<h5 id="syntax">Syntax</h5>
+<pre class="prettyprint">
+  br %bN;                                       &lt;I&gt;
+%bB:
+</pre>
+</section><section id="record">
+<h5 id="record">Record</h5>
+<pre class="prettyprint">
+I: &lt;11, N&gt;
+</pre>
+</section><section id="semantics">
+<h5 id="semantics">Semantics</h5>
+<p>The unconditional branch instruction causes control flow to transfer
+to basic block <em>N</em>.  <em>I</em> is the (optional) abbreviation index
+associated with the record.</p>
+<p><em>B</em> is the number associated with the next basic block. Label <em>%bB:</em>
+only appears if <em>B + 1 &lt; ExpectedBasicBlocks</em>. That is, the label is
+omitted only if this terminator instruction is the last instruction in
+the function block.</p>
+</section><section id="constraints">
+<h5 id="constraints">Constraints</h5>
+<pre class="prettyprint">
+0 &lt; N
+N &lt; ExpectedBasicBlocks
+B == NumBasicBlocks
+NumBasicBlocks &lt; ExpectedBasicBlocks
+</pre>
+</section><section id="id5">
+<h5 id="id5">Updates</h5>
+<pre class="prettyprint">
+++NumBasicBlocks;
+</pre>
+</section><section id="examples">
+<h5 id="examples">Examples</h5>
+<pre class="prettyprint">
+br %b2;
+</pre>
+<p>This branch instruction branches to the 3rd basic block of the function. It
+defines the following PNaCL record:</p>
+<pre class="prettyprint">
+&lt;11, 2&gt;
+</pre>
+</section></section><section id="conditional-branch-instruction">
+<h4 id="conditional-branch-instruction">Conditional Branch Instruction</h4>
+<p>The conditional branch instruction is used to cause control flow to
+transfer to a different basic block of the function, based on a
+boolean test condition.</p>
+<section id="id6">
+<h5 id="id6">Syntax</h5>
+<pre class="prettyprint">
+  br i1 C, %bB1, %bB2;                          &lt;I&gt;
+%bB:
+</pre>
+</section><section id="id7">
+<h5 id="id7">Record</h5>
+<pre class="prettyprint">
+I: &lt;11, B1, B2, V&gt;
+</pre>
+</section><section id="id8">
+<h5 id="id8">Semantics</h5>
+<p>Upon execution of a conditional branch instruction, the <em>i1</em> (boolean)
+argument <em>C</em> is evaluated. If the value is <em>true</em>, control flows to
+basic block <em>B1</em>. Otherwise control flows to basic block
+<em>B2</em>. Condition value V is the relative index of condition C. <em>I</em> is
+the (optional) abbreviation index associated with the record.</p>
+<p><em>B</em> is the number associated with the next basic block. Label <em>%bB:</em>
+only appears if <em>B + 1 &lt; ExpectedBasicBlocks</em>. That is, the label is
+omitted only if this terminator instruction is the last instruction in
+the function block.</p>
+</section><section id="id9">
+<h5 id="id9">Constraints</h5>
+<pre class="prettyprint">
+V == RelativeIndex(C)
+0 &lt; B1
+B1 &lt; ExpectedBasicBlocks
+0 &lt; B2
+B2 &lt; ExpectedBasicBlocks
+B == NumBasicBlocks and
+NumBasicBlocks &lt; ExpectedBasicBlocks
+TypeOf(C) == i1
+</pre>
+</section><section id="id10">
+<h5 id="id10">Updates</h5>
+<pre class="prettyprint">
+++NumBasicBlocks;
+</pre>
+</section><section id="id11">
+<h5 id="id11">Examples</h5>
+<pre class="prettyprint">
+%b2:
+  %v10 = cmp eq i32 %v8, %v9;
+  br i1 %v10, %b3, %b4;
+%b3:
+  ret i32 1;
+%b4:
+  ret i32 0;
+</pre>
+<p>The record generated for the conditional branch instruction is:</p>
+<pre class="prettyprint">
+&lt;11, 3, 4, 1&gt;
+</pre>
+</section></section><section id="unreachable">
+<h4 id="unreachable">Unreachable</h4>
+<p>The unreachable instruction has no defined semantics. The instruction
+is used to inform the <em>PNaCl translator</em> that control can&#8217;t reach this
+instruction.  The most common use of this is when one calls a
+no-return function.</p>
+<section id="id12">
+<h5 id="id12">Syntax</h5>
+<pre class="prettyprint">
+  unreachable;                                  &lt;I&gt;
+%bB:
+</pre>
+</section><section id="id13">
+<h5 id="id13">Record</h5>
+<pre class="prettyprint">
+I: &lt;15&gt;
+</pre>
+</section><section id="id14">
+<h5 id="id14">Semantics</h5>
+<p>Directive to the <em>PNaCl translator</em> that this instruction is unreachable.</p>
+<p><em>I</em> is the (optional) abbreviation index associated with the record.</p>
+<p><em>B</em> is the number associated with the next basic block. Label <em>%bB:</em>
+only appears if <em>B + 1 &lt; ExpectedBasicBlocks</em>. That is, the label is
+omitted only if this terminator instruction is the last instruction in
+the function block.</p>
+</section><section id="id15">
+<h5 id="id15">Constraints</h5>
+<pre class="prettyprint">
+B == NumBasicBlocks and
+NumBasicBlocks &lt; ExpectedBasicBlocks
+</pre>
+</section><section id="id16">
+<h5 id="id16">Updates</h5>
+<pre class="prettyprint">
+++NumBasicBlocks;
+</pre>
+</section><section id="id17">
+<h5 id="id17">Examples</h5>
+<p>TBD.</p>
+</section></section><section id="switch-instruction">
+<h4 id="switch-instruction">Switch Instruction</h4>
+<p>TBD.</p>
+</section></section><section id="binary-inststructions">
+<h3 id="binary-inststructions">Binary Inststructions</h3>
+<p>Binary instructions are used to do most of the computation in a
+program. They require two operands of the same type, execute an
+operation on them, and produce a value. The value may represent
+multiple values if the type is a vector type.  The result value always
+has the same type as its operands.</p>
+<p>Most integer binary operations can be applied to signed and unsigned
+integers.  In the few cases where the sign can make a difference,
+there are two separate binary operations, one for each case. For
+floating binary operations, the binary operation has the same name as
+the corresponding signed integer operation. One can tell whether the
+operation is integral or floating, by the type associated with the
+binary operation.</p>
+<section id="add-instruction">
+<h4 id="add-instruction">Add Instruction</h4>
+<p>The add instruction returns the sum of its two operands. Both
+arguments, and the result, must be an integer, floating, or vector
+type.</p>
+<p><strong>Syntax</strong></p>
+<pre class="prettyprint">
+%vN = add T V1, V2;                             &lt;I&gt;
+</pre>
+<p><strong>Record</strong></p>
+<blockquote>
+<div>I: &lt;2, A1, A2, 0&gt;</div></blockquote>
+<p><strong>Semantics</strong></p>
+<p>The add instruction returns the sum of its two operands. Arguments
+<em>V1</em> and <em>V2</em>, and the result <em>%vN</em>, must be of type <em>T</em>. <em>T</em> must be
+an integral, floating, or vector type.  <em>N</em> is defined by the record
+position, defining the corresponding value generated by the
+instruction.  <em>I</em> is the (optiona) abbreviation associated with the
+corresponding record.</p>
+<p><strong>Constraints</strong></p>
+<pre class="prettyprint">
+A1 == RelativeIndex(V1)
+A2 == RelativeIndex(V2)
+TypeOf(V1) == TypeOf(V2)
+N == NumValuedInsts
+NumBasicBlocks &lt; ExpectedBasicBlocks
+</pre>
+<p><strong>Updates</strong></p>
+<pre class="prettyprint">
+++NumValuedInsts;
+TypeOf(%vN) = T
+</pre>
+<p><strong>Examples</strong></p>
+<p>TBD.</p>
+</section><section id="subtract-instruction">
+<h4 id="subtract-instruction">Subtract Instruction</h4>
+<p>sub</p>
+<p>TBD.</p>
+</section><section id="multiply-instruction">
+<h4 id="multiply-instruction">Multiply Instruction</h4>
+<p>mul</p>
+<p>TBD.</p>
+</section><section id="divide-instruction">
+<h4 id="divide-instruction">Divide Instruction</h4>
+<p>div
+sdiv</p>
+<p>TBD.</p>
+</section><section id="remainder-instruction">
+<h4 id="remainder-instruction">Remainder Instruction</h4>
+<p>div
+sdiv</p>
+<p>TBD.</p>
+</section><section id="shift-left-instruction">
+<h4 id="shift-left-instruction">Shift left Instruction</h4>
+<p>shl</p>
+<p>TBD.</p>
+</section><section id="logical-shift-right-instructions">
+<h4 id="logical-shift-right-instructions">Logical Shift right Instructions</h4>
+<p>ashr</p>
+<p>TBD.</p>
+</section><section id="arithmetic-shift-right-instructions">
+<h4 id="arithmetic-shift-right-instructions">Arithmetic Shift right Instructions</h4>
+<p>ashr</p>
+<p>TBD.</p>
+</section><section id="and-instruction">
+<h4 id="and-instruction">And Instruction</h4>
+<p>TBD.</p>
+</section><section id="or-instruction">
+<h4 id="or-instruction">Or Instruction</h4>
+<p>TBD.</p>
+</section><section id="xor-instruction">
+<h4 id="xor-instruction">Xor Instruction</h4>
+<p>TBD.</p>
+</section></section><section id="memory-creation-and-access-instructions">
+<h3 id="memory-creation-and-access-instructions">Memory creation and access Instructions</h3>
+<p>TBD.</p>
+<section id="stack-frame-memory-allocation-instruction">
+<h4 id="stack-frame-memory-allocation-instruction">Stack frame memory allocation Instruction</h4>
+<p>alloca</p>
+<p>TBD.</p>
+</section><section id="load-instruction">
+<h4 id="load-instruction">Load Instruction</h4>
+<p>load</p>
+<p>TBD.</p>
+<p>??? Vector</p>
+</section><section id="store-instruction">
+<h4 id="store-instruction">Store Instruction</h4>
+<p>store</p>
+<p>??? Vector.</p>
+</section></section><section id="conversion-instructions">
+<h3 id="conversion-instructions">Conversion Instructions</h3>
+<p>TBD.</p>
+<section id="truncating-instructions">
+<h4 id="truncating-instructions">Truncating Instructions</h4>
+<p>trunc
+fptrunc</p>
+<p>TBD.</p>
+</section><section id="extending-instructions">
+<h4 id="extending-instructions">Extending Instructions</h4>
+<ul class="small-gap">
+<li>Extending</li>
+<li>Type Conversion</li>
+</ul>
+<p>TBD.</p>
+</section></section><section id="comparison-instructions">
+<h3 id="comparison-instructions">Comparison Instructions</h3>
+<p>cmp</p>
+<p>TBD.</p>
+</section><section id="other-instructions">
+<h3 id="other-instructions">Other Instructions</h3>
+<p>TBD.</p>
+<section id="phi-instruction">
+<h4 id="phi-instruction">Phi Instruction</h4>
+<p>TBD.</p>
+</section><section id="forward-type-declarations">
+<h4 id="forward-type-declarations">Forward type declarations</h4>
+<p>TBD.</p>
+</section><section id="select-instruction">
+<h4 id="select-instruction">Select Instruction</h4>
+<p>TBD.</p>
+</section><section id="call-instructions">
+<h4 id="call-instructions">Call Instructions</h4>
+<p>TBD.</p>
+</section></section><section id="intrinsic-functions">
+<h3 id="intrinsic-functions">Intrinsic Functions</h3>
+<p>TBD.</p>
+</section><section id="support-functions">
+<h3 id="support-functions">Support Functions</h3>
+<p>Defines functions used to convert syntactic representation to corresponding
+records.</p>
+<section id="absoluteindex">
+<h4 id="absoluteindex">AbsoluteIndex</h4>
+<p>Bitcode ID&#8217;s of the forms <em>&#64;fN</em>, <em>&#64;gN</em>, <em>%pN</em>, <em>%cN</em>, and <em>%vN</em>, are
+combined into a single index space. This can be done because of the
+ordering imposed by PNaClAsm. All function address bitcode IDs must be
+defined before any of the other forms of bitcode IDs. All global
+address bitcode IDs must be defined before any local bitcode
+IDs. Within a function block, the parameter bitcode IDs must be
+defined before constant IDs, and constant IDs must be defined before
+instruction value IDs.</p>
+<p>Hence, within a function block, it is safe to refer to all of these
+bitcode IDs using a single <em>absolute</em> index. The abolute index for
+each kind of bitcode ID is computed as follows:</p>
+<table border="1" class="docutils">
+<colgroup>
+</colgroup>
+<thead valign="bottom">
+<tr class="row-odd"><th class="head">Bitcode ID</th>
+<th class="head">AbsoluteIndex</th>
+</tr>
+</thead>
+<tbody valign="top">
+<tr class="row-even"><td>&#64;fN</td>
+<td>N</td>
+</tr>
+<tr class="row-odd"><td>&#64;gN</td>
+<td>N + NumDefinedFcnAddresses</td>
+</tr>
+<tr class="row-even"><td>&#64;pN</td>
+<td>N + NumDefinedFcnAddresses + NumGlobalAddresses</td>
+</tr>
+<tr class="row-odd"><td>&#64;cN</td>
+<td>N + NumDefinedFcnAddresses + NumGlobalAddresses + NumParams</td>
+</tr>
+<tr class="row-even"><td>&#64;vN</td>
+<td>N + NumDefinedFcnAddresses + NumGlobalAddresses + NumParams + NumFcnConsts</td>
+</tr>
+</tbody>
+</table>
+</section><section id="relativeindex">
+<h4 id="relativeindex">RelativeIndex</h4>
+<p>Relative indices are used to refer to values within instructions of a
+function.  The relative index of an ID is always defined in terms of
+the index associated with the next value generating instruction. It is
+defined as follows:
+.. naclcode:</p>
+<pre class="prettyprint">
+RelativeIndex(J) = AbsoluteIndex(NumValuedInsts) - AbsoluteIndex(J)
+</pre>
+</section></section><section id="abbreviations">
+<h3 id="abbreviations">Abbreviations</h3>
+<p>TBD.</p>
+<section id="id18">
+<h4 id="id18">Introduction</h4>
+<p>TBD.</p>
+<ul class="small-gap">
+<li>Blocks</li>
+<li>Data Records</li>
+<li>Abbreviations</li>
+<li>Abbreviation Ids.</li>
+</ul>
+</section><section id="bitstream-format">
+<h4 id="bitstream-format">Bitstream Format</h4>
+<p>TBD.</p>
+<ul class="small-gap">
+<li>Header</li>
+<li>Block Structue</li>
+<li>Primitives</li>
+<li>Abbreviations</li>
+<li>BlockInfoBlock</li>
+</ul>
+</section></section><section id="reference-implementation">
+<h3 id="reference-implementation">Reference Implementation</h3>
+<p>TBD.</p>
+</section></section></section>
+
+{{/partials.standard_nacl_article}}