Subzero: Add a detailed design document.

DESIGN.rst

+Design of the Subzero fast code generator
+=========================================
+
+Introduction
+------------
+
+The `Portable Native Client (PNaCl) <http://gonacl.com>`_ project includes
+compiler technology based on `LLVM <http://llvm.org/>`_.  The developer uses the
+PNaCl toolchain to compile their application to architecture-neutral PNaCl
+bitcode (a ``.pexe`` file), using as much architecture-neutral optimization as
+possible.  The ``.pexe`` file is downloaded to the user's browser where the
+PNaCl translator (a component of Chrome) compiles the ``.pexe`` file to
+`sandboxed
+<https://developer.chrome.com/native-client/reference/sandbox_internals/index>`_
+native code.  The translator uses architecture-specific optimizations as much as
+practical to generate good native code.
+
+The native code can be cached by the browser to avoid repeating translation on
+future page loads.  However, first-time user experience is hampered by long
+translation times.  The LLVM-based PNaCl translator is pretty slow, even when
+using ``-O0`` to minimize optimizations, so delays are especially noticeable on
+slow browser platforms such as ARM-based Chromebooks.
+
+Translator slowness can be mitigated or hidden in a number of ways.
+
+- Parallel translation.  However, slow machines where this matters most, e.g.
+  ARM-based Chromebooks, are likely to have fewer cores to parallelize across,
+  and are likely to less memory available for multiple translation threads to
+  use.
+
+- Streaming translation, i.e. start translating as soon as the download starts.
+  This doesn't help much when translation speed is 10x slower than download

[JF, 2015/09/03 00:35:21]

10×

[Jim Stichnoth, 2015/09/03 06:47:03]

Done.

+  speed, or the ``.pexe`` file is already cached while the translated binary was
+  flushed from the cache.
+
+- Arrange the web page such that translation is done in parallel with
+  downloading large assets.
+
+- Arrange the web page to distract the user with `cat videos
+  <https://www.youtube.com/watch?v=tLt5rBfNucc>`_ while translation is in
+  progress.
+
+Or, improve translator performance to something more reasonable.
+
+This document describes Subzero's attempt to improve translation speed by an
+order of magnitude while rivaling LLVM's code quality.  Subzero does this
+through minimal IR layering, lean data structures and passes, and a careful
+selection of fast optimization passes.  It two optimization recipes: full

[JF, 2015/09/03 00:35:21]

"It two optimization recipes"
It no Englishy.

[Jim Stichnoth, 2015/09/03 06:47:03]

Doed.

+optimizations (``O2``) and minimal optimizations (``Om1``).  The recipes are the
+following (described in more detail below):
+
++-----------------------------------+-----------------------+
+| O2 recipe                         | Om1 recipe            |
++===================================+=======================+
+| Parse .pexe file                  | Parse .pexe file      |
++-----------------------------------+-----------------------+
+| Address mode inference            |                       |
++-----------------------------------+-----------------------+
+| Read-modify-write (RMW) transform |                       |
++-----------------------------------+-----------------------+
+| Basic liveness analysis           |                       |
++-----------------------------------+-----------------------+
+| Load optimization                 |                       |
++-----------------------------------+-----------------------+
+|                                   | Phi lowering (simple) |
++-----------------------------------+-----------------------+
+| Target lowering                   | Target lowering       |
++-----------------------------------+-----------------------+
+| Full liveness analysis            |                       |
++-----------------------------------+-----------------------+
+| Register allocation               |                       |
++-----------------------------------+-----------------------+
+| Phi lowering (advanced)           |                       |
++-----------------------------------+-----------------------+
+| Post-phi register allocation      |                       |
++-----------------------------------+-----------------------+
+| Branch optimization               |                       |
++-----------------------------------+-----------------------+
+| Code emission                     | Code emission         |
++-----------------------------------+-----------------------+
+
+Goals
+=====
+
+Translation speed
+-----------------
+
+We'd like to be able to translate a ``.pexe`` file as fast as download speed.
+Any faster is in a sense wasted effort.  Download speed varies greatly, but
+we'll arbitrarily say 1 MB/sec.  We'll pick the ARM A15 CPU as the example of a
+slow machine.  We observe a 3× single-thread performance difference between A15
+and a high-end x86 Xeon E5-2690 based workstation, and aggressively assume a
+``.pexe`` file could be compressed to 50% on the web server using gzip transport
+compression, so we set the translation speed goal to 6 MB/sec on a z620
+workstation.

[JF, 2015/09/03 00:35:21]

on the Xeon workstation

[Jim Stichnoth, 2015/09/03 06:47:02]

Done.

+
+Currently, at the ``-O0`` level, the LLVM-based PNaCl translation translates at
+⅒ the target rate.  The ``-O2`` mode takes 3× as long as the ``-O0`` mode.
+
+In other words, Subzero's goal is to improve over LLVM's translation speed by
+10×.
+
+Code quality
+------------
+
+Subzero's initial goal is to produce code that meets or exceeds LLVM's ``-O0``
+code quality.  The stretch goal is to approach LLVM ``-O2`` code quality.  On
+average, LLVM ``-O2`` performs twice as well as LLVM ``-O0``.
+
+It's important to note that the quality of Subzero-generated code depends on
+target-neutral optimizations and simplifications being run beforehand in the
+developer environment.  The ``.pexe`` file reflects these optimizations.  For
+example, Subzero assumes that the basic blocks are ordered topologically where
+possible (which makes liveness analysis converge fastest), and Subzero does not
+do any function inlining because it should already have been done.
+
+Translator size
+---------------
+
+The current LLVM-based translator binary (``pnacl-llc``) is about 10 MB in size.
+We think 1 MB is a more reasonable size -- especially for such a component that
+might be distributed to a billion Chrome users.  Thus we target a 10× reduction

[JF, 2015/09/03 00:35:21]

Not just might! It *is* distributed to over a billion users!

[Jim Stichnoth, 2015/09/03 06:47:03]

Done.

+in binary size.
+
+For development, Subzero can be built for all target architectures, and all
+debugging and diagnostic options enabled.  For a smaller translator, we restrict
+to a single target architecture, and define a MINIMAL build where unnecessary
+features are compiled out.
+
+Memory footprint
+----------------
+
+The current LLVM-based translator suffers from an issue in which some
+function-specific data has to be retained in memory until all translation
+completes, and therefore the memory footprint grows without bound.  Large
+``.pexe`` files can lead to the translator process holding hundreds of MB of
+memory by the end.  The translator runs in a separate process, so this memory
+growth doesn't *directly* affect other processes, but it does dirty the physical
+memory and contributes to a perception of bloat, especially noticeable on weaker
+systems.

[JF, 2015/09/03 00:35:21]

"bloat, and in the extreme case out-of-memory tab killing"

[Jim Stichnoth, 2015/09/03 06:47:03]

Done.

+
+Subzero should maintain a stable memory footprint throughout translation.  It's
+not really practical to set a specific limit, because there is not really a
+practical limit on a single function's size, but the footprint should be
+"reasonable" and be proportional to the largest input function size, not the
+total ``.pexe`` file size.  Simply put, Subzero should not have memory leaks or
+inexorable memory growth.  (We use ASAN builds to test for leaks.)
+
+Multithreaded translation
+-------------------------
+
+It should be practical to translate different functions concurrently and see
+good scalability.  Some locking may be needed, such as accessing output buffers
+or constant pools, but that should be fairly minimal.  In contrast, LLVM was
+only designed for module-level parallelism, and as such, the PNaCl translator
+internally splits a ``.pexe`` file into several modules for concurrent
+translation.  All output needs to be deterministic regardless of the level of
+multithreading, i.e. functions and data should always be output in the same
+order.
+
+Target architectures
+--------------------
+
+Initial target architectures are x86-32, x86-64, ARM32, and MIPS32.  Future
+targets include ARM64 and MIPS64, though these targets lack NaCl support
+including a sandbox model or a validator.
+
+The first implementation is for x86-32, because it was expected to be
+particularly challenging, and thus more likely to draw out any design problems
+early:
+
+- There are a number of special cases, asymmetries, and warts in the x86
+  instruction set.
+
+- Complex addressing modes may be leveraged for better code quality.
+
+- 64-bit integer operations have to be lowered into longer sequences of 32-bit
+  operations.
+
+- Paucity of physical registers may reveal code quality issues early in the
+  design.
+
+Detailed design
+===============
+
+Intermediate representation - ICE
+---------------------------------
+
+Subzero's IR is called ICE.  It is designed to be reasonably similar to LLVM's
+IR, which is reflected in the ``.pexe`` file's bitcode structure.  It has a
+representation of global variables and initializers, and a set of functions.
+Each function contains a list of basic blocks, and each basic block constains a
+list of instructions.  Instructions that operate on stack and register variables
+do so using static single assignment (SSA) form.
+
+The ``.pexe`` file is translated one function at a time (or in parallel by
+multiple translation threads).  The recipe for optimization passes depends on
+the specific target and optimization level, and is described in detail below.
+Global variables (types and initializers) are simply and directly translated to
+object code, without any meaningful attempts at optimization.
+
+A function's control flow graph (CFG) is represented by the ``Ice::Cfg`` class.
+Its key contents include:
+
+- A list of ``CfgNode`` pointers, generally held in topological order.
+
+- A list of ``Variable`` pointers corresponding to local variables used in the
+  function plus compiler-generated temporaries.
+
+A basic block is represented by the ``Ice::CfgNode`` class.  Its key contents
+include:
+
+- A linear list of instructions, in the same style as LLVM.  The last
+  instruction of the list is always a terminator instruction: branch, switch,
+  return, unreachable.
+
+- A list of Phi instructions, also in the same style as LLVM.  They are held as
+  a linear list for convenience, though per Phi semantics, they are executed "in
+  parallel" without dependencies on each other.
+
+- An unordered list of ``CfgNode`` pointers corresponding to incoming edges, and
+  another list for outgoing edges.
+
+- The node's unique, 0-based index into the CFG's node list.
+
+An instruction is represented by the ``Ice::Inst`` class.  Its key contents
+include:
+
+- A list of source operands.
+
+- Its destination variable, if the instruction produces a result in an
+  ``Ice::Variable``.
+
+- A bitvector indicating which variables' live ranges this instruction ends.
+  This is computed during liveness analysis.
+
+Instructions kinds are divided into high-level ICE instructions and low-level
+ICE instructions.  High-level instructions consist of the PNaCl/LLVM bitcode
+instruction kinds.  Each target architecture implementation extends the
+instruction space with its own set of low-level instructions.  Generally,
+low-level instructions correspond to individual machine instructions.  The
+high-level ICE instruction space includes a few additional instruction kinds
+that are not part of LLVM but are generally useful (e.g., an Assignment
+instruction), or are useful across targets (e.g., BundleLock and BundleUnlock
+instructions for sandboxing).
+
+Specifically, high-level ICE instructions that derive from LLVM (but with PNaCl
+ABI restrictions as documented in the `PNaCl Bitcode Reference Manual
+<https://developer.chrome.com/native-client/reference/pnacl-bitcode-abi>`_) are
+the following:
+
+- Alloca: allocate data on the stack
+
+- Arithmetic: binary operations of the form ``A = B op C``
+
+- Br: conditional or unconditional branch
+
+- Call: function call
+
+- Cast: unary type-conversion operations
+
+- ExtractElement: extract a scalar element from a vector-type value
+
+- Fcmp: floating-point comparison
+
+- Icmp: integer comparison
+
+- IntrinsicCall: call a known intrinsic
+
+- InsertElement: insert a scalar element into a vector-type value
+
+- Load: load a value from memory
+
+- Phi: implement the SSA phi node
+
+- Ret: return from the function
+
+- Select: essentially the C language operation of the form ``X = C ? Y : Z``
+
+- Store: store a value into memory
+
+- Switch: generalized branch to multiple possible locations
+
+- Unreachable: indicate that this portion of the code is unreachable
+
+The additional high-level ICE instructions are the following:
+
+- Assign: a simple ``A=B`` assignment.  This is useful for e.g. lowering Phi
+  instructions to non-SSA assignments, before lowering to machine code.
+
+- BundleLock, BundleUnlock.  These are markers used for sandboxing, but are
+  common across all targets and so they are elevated to the high-level
+  instruction set.
+
+- FakeDef, FakeUse, FakeKill.  These are tools used to preserve consistency in
+  liveness analysis, elevated to the high-level because they are used by all
+  targets.  They are described in more detail at the end of this section.
+
+- JumpTable: this represents the result of switch optimization analysis, where
+  some switch instructions may use jump tables instead of cascading
+  compare/branches.
+
+An operand is represented by the ``Ice::Operand`` class.  In high-level ICE, an
+operand is either an ``Ice::Constant`` or an ``Ice::Variable``.  Constants
+include scalar integer constants, scalar floating point constants, Undef (an
+unspecified constant of a particular scalar or vector type), and symbol
+constants (essentially addresses of globals).  Note that the PNaCl ABI does not
+include vector-type constants besides Undef, and as such, Subzero (so far) has
+no reason to represent vector-type constants internally..  A variable represents

[JF, 2015/09/03 00:35:21]

Too many dots!!

[Jim Stichnoth, 2015/09/03 06:47:03]

Done...

+a value allocated on the stack (though not including alloca-derived storage).
+Among other things, a variable holds its unique, 0-based index into the CFG's
+variable list.
+
+Each target can extend the ``Constant`` and ``Variable`` classes for its own
+needs.  In addition, the ``Operand`` class may be extended, e.g. to define an
+x86 ``MemOperand`` that encodes a base register, an index register, an index
+register shift amount, and a constant offset.
+
+Register allocation and liveness analysis are restricted to Variable operands.
+Because of the importance of register allocation to code quality, and the
+translation-time cost of liveness analysis, Variable operands get some special
+treatment in ICE.  Most notably, a frequent pattern in Subzero is to iterate
+across all the Variables of an instruction.  An instruction holds a list of
+operands, but an operand may contain 0, 1, or more Variables.  As such, the
+``Operand`` class specially holds a list of Variables contained within, for
+quick access.
+
+A Subzero transformation pass may work by deleting an existing instruction and
+replacing it with zero or more new instructions.  Instead of actually deleting
+the existing instruction, we generally mark it as deleted and insert the new
+instructions right after the deleted instruction.  When printing the IR for
+debugging, this is a big help because it makes it much more clear how the
+non-deleted instructions came about.
+
+Subzero has a few special instructions to help with liveness analysis
+consistency.
+
+- The FakeDef instruction gives a fake definition of some variable.  For
+  example, on x86-32, a divide instruction defines both ``%eax`` and ``%edx``
+  but an ICE instruction can represent only one destination variable.  This is
+  similar for multiply instructions, and for function calls that return a 64-bit
+  integer result in the ``%edx:%eax`` pair.  Also, using the ``xor %eax, %eax``
+  trick to set ``%eax`` to 0 requires an initial FakeDef of ``%eax``.
+
+- The FakeUse instruction registers a use of a variable, typically to prevent an
+  earlier assignment to that variable from being dead-code eliminated.  For
+  example, lowering an operation like ``x=cc?y:z`` may be done using x86's
+  conditional move (cmov) instruction: ``mov z, x; cmov_cc y, x``.  Without a
+  FakeUse of ``x`` between the two instructions, the liveness analysis pass may
+  dead-code eliminate the first instruction.
+
+- The FakeKill instruction is added after a call instruction, and is a quick way
+  of indicating that caller-save registers are invalidated.
+
+Pexe parsing
+------------
+
+Subzero includes an integrated PNaCl bitcode parser for ``.pexe`` files.  It
+parses the ``.pexe`` file function by function, ultimately constructing an ICE
+CFG for each function.  After a function is parsed, its CFG is handed off to the
+translation phase.  The bitcode parser also parses global initializer data and
+hands it off to be translated to data sections in the object file.
+
+Subzero has another parsing strategy for testing/debugging.  LLVM libraries can
+be used to parse a module into LLVM IR (though very slowly relative to Subzero
+native parsing).  Then we iterate across the LLVM IR and construct high-level
+ICE, handing off each CFG to the translation phase.
+
+Overview of lowering
+--------------------
+
+In general, translation goes like this:
+
+- Parse the next function from the ``.pexe`` file and construct a CFG consisting
+  of high-level ICE.
+
+- Do analysis passes and transformation passes on the high-level ICE, as
+  desired.
+
+- Lower each high-level ICE instruction into a sequence of zero or more
+  low-level ICE instructions.  Each high-level instruction is generally lowered
+  independently, though the target lowering is allowed to look ahead in the
+  CfgNode's instruction list if desired.
+
+- Do more analysis and transformation passes on the low-level ICE, as desired.
+
+- Assemble the low-level CFG into an ELF object file (alternatively, a textual
+  assembly file that is later assembled by some external tool).
+
+- Repeat for all functions, and also produce object code for data such as global
+  initializers and internal constant pools.
+
+Currently there are two optimization levels: ``O2`` and ``Om1``.  For ``O2``,
+the intention is to apply all available optimizations to get the best code
+quality (though the initial code quality goal is measured against LLVM's ``O0``
+code quality).  For ``Om1``, the intention is to apply as few optimizations as
+possible and produce code as quickly as possible, accepting poor code quality.
+``Om1`` is short for "O-minus-one", i.e. "worse than O0", or in other words,
+"sub-zero".
+
+High-level debuggability of generated code is so far not a design requirement,
+but Subzero doesn't really do transformations that would obfuscate debugging.
+The main thing might be that register allocation (including stack slot
+coalescing for stack-allocated variables whose live ranges don't overlap) may
+render a variable's value unobtainable after its live range ends.  This would
+not be an issue for ``Om1`` since it doesn't register-allocate program-level
+variables, nor does it coalesce stack slots.  Adding debugging support would
+primarily involve adding DWARF support to the ELF file emitter.  Subzero
+propagates global symbol names, local variable names, and function-internal
+label names that are present in the ``.pexe`` file, but the PNaCl toolchain
+would need to not strip these symbols to make it most useful.
+
+Our experience so far is that ``Om1`` translates twice as fast as ``O2``, but
+produces code with one third the code quality.  ``Om1`` is good for testing and
+debugging -- during translation, it tends to expose errors in the basic lowering
+that might otherwise have been hidden by the register allocator or other
+optimization passes.  It also helps determine whether a code correctness problem
+is a fundamental problem in the basic lowering, or an error in another
+optimization pass.
+
+The implementation of target lowering also controls the recipe of passes used
+for ``Om1`` and ``O2`` translation.  For example, address mode inference may
+only be relevant for x86.
+
+Lowering strategy
+-----------------
+
+The core of Subzero's lowering from high-level ICE to low-level ICE is to lower
+each high-level instruction down to a sequence of low-level target-specific
+instructions, in a largely context-free setting.  That is, each high-level
+instruction conceptually has a simple template expansion into low-level
+instructions, and lowering can in theory be done in any order.  This may sound
+like a small effort, but quite a large number of templates may be needed because
+of the number of PNaCl types and instruction variants.  Furthermore, there may
+be optimized templates, e.g. to take advantage of operator commutativity.  This
+is similar to other template-based approaches in fast code generation or
+interpretation, though some decisions are deferred until after some global
+analysis passes, mostly related to register allocation, stack slot assignment,
+and specific choice of instruction variant and addressing mode.
+
+The key idea for a lowering template is to produce valid low-level instructions
+that are guaranteed to meet address mode and other structural requirements of
+the instruction set.  For example, on x86, the source operand of an integer
+store instruction must be an immediate or a physical register; a shift
+instruction's shift amount must be an immediate or in register ``%cl``; a
+function's integer return value is in ``%eax``; most x86 instructions are
+two-operand, in contrast to corresponding three-operand high-level instructions;
+etc.
+
+Because target lowering runs before register allocation, there is no way to know
+whether a given ``Ice::Variable`` operand lives on the stack or in a physical
+register.  When the low-level instruction calls for a physical register operand,
+the target lowering can create an infinite-weight Variable.  This tells the
+register allocator to assign infinite weight when making decisions, effectively
+guaranteeing some physical register.  Variables can also be pre-colored to a
+specific physical register (``cl`` in the shift example above), which also gives
+infinite weight.
+
+To illustrate, consider a high-level arithmetic instruction on 32-bit integer
+operands::
+
+    A = B + C
+
+X86 target lowering might produce the following::
+
+    T.inf = B  // mov instruction
+    T.inf += C // add instruction
+    A = T.inf  // mov instruction
+
+Here, ``T.inf`` is an infinite-weight temporary.  As long as ``T.inf`` has a
+physical register, the three lowered instructions are all encodable regardless
+of whether ``B`` and ``C`` are physical registers, memory, or immediates, and
+whether ``A`` is a physical register or in memory.
+
+In this example, ``A`` must be a Variable and one may be tempted to simplify the
+lowering sequence by setting ``A`` as infinite-weight and using::
+
+        A = B  // mov instruction
+        A += C // add instruction
+
+This has two problems.  First, if the original instruction was actually ``A =
+B + A``, the result would be incorrect.  Second, assigning ``A`` a physical
+register applies throughout ``A``'s entire live range.  This is probably not
+what is intended, and may ultimately lead to a failure to allocate a register
+for an infinite-weight variable.
+
+This style of lowering leads to many temporaries being generated, so in ``O2``
+mode, we rely on the register allocator to clean things up.  For example, in the
+example above, if ``B`` ends up getting a physical register and its live range
+ends at this instruction, the register allocator is likely to reuse that
+register for ``T.inf``.  This leads to ``T.inf=B`` being a redundant register
+copy, which is removed as an emission-time peephole optimization.
+
+O2 lowering
+-----------
+
+Currently, the ``O2`` lowering recipe is the following:
+
+- Address mode inference
+
+- Read-modify-write (RMW) transformation
+
+- Basic liveness analysis
+
+- Load optimization
+
+- Target lowering
+
+- Full liveness analysis
+
+- Register allocation
+
+- Phi instruction lowering (advanced)
+
+- Post-phi lowering register allocation
+
+- Branch optimization
+
+These passes are described in more detail below.
+
+Om1 lowering
+------------
+
+Currently, the ``Om1`` lowering recipe is the following:
+
+- Phi instruction lowering (simple)
+
+- Target lowering
+
+- Register allocation (infinite-weight and pre-colored only)
+
+Optimization passes
+-------------------
+
+Liveness analysis
+^^^^^^^^^^^^^^^^^
+
+Liveness analysis is a standard dataflow optimization, implemented as follows.
+For each node (basic block), its live-out set is computed as the union of the
+live-in sets of its successor nodes.  Then the node's instructions are processed
+in reverse order, updating the live set, until the beginning of the node is
+reached, and the node's live-in set is recorded.  If this iteration has changed
+the node's live-in set, the node's predecessors are marked for reprocessing.
+This continues until no more nodes need reprocessing.  If nodes are processed in
+reverse topological order, the number of iterations over the CFG is generally
+equal to the maximum loop nest depth.
+
+To implement this, each node records its live-in and live-out sets, initialized
+to the empty set.  Each instruction records which of its Variables' live ranges
+end in that instruction, initialized to the empty set.  A side effect of
+liveness analysis is dead instruction elimination.  Each instruction can be
+marked as tentatively dead, and after the algorithm converges, the tentatively
+dead instructions are permanently deleted.
+
+Optionally, after this liveness analysis completes, we can do live range
+construction, in which we calculate the live range of each variable in terms of
+instruction numbers.  A live range is represented as a union of segments, where
+the segment endpoints are instruction numbers.  Instruction numbers are required
+to be unique across the CFG, and monotonically increasing within a basic block.
+As a union of segments, live ranges can contain "gaps" and are therefore
+precise.  Because of SSA properties, a variable's live range can start at most
+once in a basic block, and can end at most once in a basic block.  Liveness
+analysis keeps track of which variable/instruction tuples begin live ranges and
+end live ranges, and combined with live-in and live-out sets, we can efficiently
+build up live ranges of all variables across all basic blocks.
+
+A lot of care is taken to try to make liveness analysis fast and efficient.
+Because of the lowering strategy, the number of variables is generally
+proportional to the number of instructions, leading to an O(N^2) complexity
+algorithm if implemented naively.  To improve things based on sparsity, we note
+that most variables are "local" and referenced in at most one basic block (in
+contrast to the "global" variables with multi-block usage), and therefore cannot
+be live across basic blocks.  Therefore, the live-in and live-out sets,
+typically represented as bit vectors, can be limited to the set of global
+variables, and the intra-block liveness bit vector can be compacted to hold the
+global variables plus the local variables for that block.
+
+Register allocation
+^^^^^^^^^^^^^^^^^^^
+
+Subzero implements a simple linear-scan register allocator, based on the
+allocator described by Hanspeter Mössenböck and Michael Pfeiffer in `Linear Scan
+Register Allocation in the Context of SSA Form and Register Constraints
+<ftp://ftp.ssw.uni-linz.ac.at/pub/Papers/Moe02.PDF>`_.  This allocator has
+several nice features:
+
+- Live ranges are represented as unions of segments, as described above, rather
+  than a single start/end tuple.
+
+- It allows pre-coloring of variables with specific physical registers.
+
+- It applies equally well to pre-lowered Phi instructions.
+
+The paper suggests an approach of aggressively coalescing variables across Phi
+instructions (i.e., trying to force Phi source and destination variables to have
+the same register assignment), but we reject that in favor of the more natural
+preference mechanism described below.
+
+We enhance the algorithm in the paper with the capability of automatic inference
+of register preference, and with the capability of allowing overlapping live
+ranges to safely share the same register in certain circumstances.  If we are
+considering register allocation for variable ``A``, and ``A`` has a single
+defining instruction ``A=B+C``, then the preferred register for ``A``, if
+available, would be the register assigned to ``B`` or ``C``, if any, provided
+that ``B`` or ``C``'s live range does not overlap ``A``'s live range.  In this
+way we infer a good register preference for ``A``.
+
+We allow overlapping live ranges to get the same register in certain cases.
+Suppose a high-level instruction like::
+
+    A = unary_op(B)
+
+has been target-lowered like::
+
+    T.inf = B
+    A = unary_op(T.inf)
+
+Further, assume that ``B``'s live range continues beyond this instruction
+sequence, and that ``B`` has already been assigned some register.  Normally, we
+might want to infer ``B``'s register as a good candidate for ``T.inf``, but it
+turns out that ``T.inf`` and ``B``'s live ranges overlap, requiring them to have
+different registers.  But ``T.inf`` is just a read-only copy of ``B`` that is
+guaranteed to be in a register, so in theory these overlapping live ranges could
+safely have the same register.  Our implementation allows this overlap as long
+as ``T.inf`` is never modified within ``B``'s live range, and ``B`` is never
+modified within ``T.inf``'s live range.
+
+Subzero's register allocator can be run in 3 configurations.
+
+- Normal mode.  All Variables are considered for register allocation.  It
+  requires full liveness analysis and live range construction as a prerequisite.
+  This is used by ``O2`` lowering.
+
+- Minimal mode.  Only infinite-weight or pre-colored Variables are considered.
+  All other Variables are stack-allocated.  It does not require liveness
+  analysis; instead, it quickly scans the instructions and records first
+  definitions and last uses of all relevant Variables, using that to construct a
+  single-segment live range.  Although this includes most of the Variables, the
+  live ranges are mostly simple, short, and rarely overlapping, which the
+  register allocator handles efficiently.  This is used by ``Om1`` lowering.
+
+- Post-phi lowering mode.  Advanced phi lowering is done after normal-mode
+  register allocation, and may result in new infinite-weight Variables that need
+  registers.  One would like to just run something like minimal mode to assign
+  registers to the new Variables while respecting existing register allocation
+  decisions.  However, it sometimes happens that there are no free registers.
+  In this case, some register needs to be forcibly spilled to the stack and
+  temporarily reassigned to the new Variable, and reloaded at the end of the new
+  Variable's live range.  The register must be one that has no explicit
+  references during the Variable's live range.  Since Subzero currently doesn't
+  track def/use chains (though it does record the CfgNode where a Variable is
+  defined), we just do a brute-force search across the CfgNode's instruction
+  list for the instruction numbers of interest.  This situation happens very
+  rarely, so there's little point for now in improving its performance.
+
+The basic linear-scan algorithm may, as it proceeds, rescind an early register
+allocation decision, leaving that Variable to be stack-allocated.  Some of these
+times, it turns out that the Variable could have been given a different register
+without conflict, but by this time it's too late.  The literature recognizes
+this situation and describes "second-chance bin-packing", which Subzero can do.
+We can rerun the register allocator in a mode that respects existing register
+allocation decisions, and sometimes it finds new non-conflicting opportunities.
+In fact, we can repeatedly run the register allocator until convergence.
+Unfortunately, in the current implementation, these subsequent register
+allocation passes end up being extremely expensive.  This is because of the
+treatment of the "unhandled pre-colored" Variable set, which is normally very
+small but ends up being quite large on subsequent passes.  Its performance can
+probably be made acceptable with a better choice of data structures, but for now
+this second-chance mechanism is disabled.
+
+Future work is to implement LLVM's `Greedy
+<http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html>`_
+register allocator as a replacement for the basic linear-scan algorithm, given
+LLVM's experience with its improvement in code quality.  (The blog post claims
+that the Greedy allocator also improved maintainability because a lot of hacks
+could be removed, but Subzero is probably not yet to that level of hacks, and is
+less likely to see that particular benefit.)
+
+Basic phi lowering
+^^^^^^^^^^^^^^^^^^
+
+The simplest phi lowering strategy works as follows (this is how LLVM ``-O0``
+implements it).  Consider this example::
+
+    L1:
+      ...
+      br L3
+    L2:
+      ...
+      br L3
+    L3:
+      A = phi [B, L1], [C, L2]
+      X = phi [Y, L1], [Z, L2]
+
+For each destination of a phi instruction, we can create a temporary and insert
+the temporary's assignment at the end of the predecessor block::
+
+    L1:
+      ...
+      A' = B
+      X' = Y
+      br L3
+    L2:
+      ...
+      A' = C
+      X' = Z
+      br L3
+    L2:
+      A = A'
+      X = X'
+
+This transformation is very simple and reliable.  It can be done before target
+lowering and register allocation, and it easily avoids the classic lost-copy and
+related problems.  ``Om1`` lowering uses this strategy.
+
+However, it has the disadvantage of initializing temporaries even for branches
+not taken, though that could be mitigated by splitting non-critical edges and
+putting assignments in the edge-split nodes.  Another problem is that without
+extra machinery, the assignments to ``A``, ``A'``, ``X``, and ``X'`` are given a
+specific ordering even though phi semantics are that the assignments are
+parallel or unordered.  This sometimes imposes false live range overlaps and
+leads to poorer register allocation.
+
+Advanced phi lowering
+^^^^^^^^^^^^^^^^^^^^^
+
+``O2`` lowering defers phi lowering until after register allocation to avoid the
+problem of false live range overlaps.  It works as follows.  We split each
+incoming edge and move the (parallel) phi assignments into the split nodes.  We
+linearize each set of assignments by finding a safe, topological ordering of the
+assignments, respecting register assignments as well.  For example::
+
+    A = B
+    X = Y
+
+Normally these assignments could be executed in either order, but if ``B`` and
+``X`` are assigned the same physical register, we would want to use the above
+ordering.  Dependency cycles are broken by introducing a temporary.  For
+example::
+
+    A = B
+    B = A
+
+Here, a temporary breaks the cycle::
+
+    t = A
+    A = B
+    B = t
+
+Finally, we use the existing target lowering to lower the assignments in this
+basic block, and once that is done for all basic blocks, we run the post-phi
+variant of register allocation on the edge-split basic blocks.
+
+When computing a topological order, we try to first schedule assignments whose
+source has a physical register, and last schedule assignments whose destination
+has a physical register.  This helps reduce register pressure.
+
+X86 address mode inference
+^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+We try to take advantage of the x86 addressing mode that includes a base
+register, an index register, an index register scale amount, and an immediate
+offset.  We do this through simple pattern matching.  Starting with a load or
+store instruction where the address is a variable, we initialize the base
+register to that variable, and look up the instruction where that variable is
+defined.  If that is an add instruction of two variables and the index register
+hasn't been set, we replace the base and index register with those two
+variables.  If instead it is an add instruction of a variable and a constant, we
+replace the base register with the variable and add the constant to the
+immediate offset.
+
+There are several more patterns that can be matched.  This pattern matching
+continues on the load or store instruction until no more matches are found.
+Because a program typically has few load and store instructions (not to be
+confused with instructions that manipulate stack variables), this address mode
+inference pass is fast.
+
+X86 read-modify-write inference
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+A reasonably common bitcode pattern is a non-atomic update of a memory
+location::
+
+    x = load addr
+    y = add x, 1
+    store y, addr
+
+On x86, with good register allocation, the Subzero passes described above
+generate code with only this quality::
+
+    mov [%ebx], %eax
+    add $1, %eax
+    mov %eax, [%ebx]
+
+However, x86 allows for this kind of code::
+
+    add $1, [%ebx]
+
+which requires fewer instructions, but perhaps more importantly, requires fewer
+physical registers.
+
+It's also important to note that this transformation only makes sense if the
+store instruction ends ``x``'s live range.
+
+Subzero's ``O2`` recipe includes an early pass to find read-modify-write (RMW)
+opportunities via simple pattern matching.  The only problem is that it is run
+before liveness analysis, which is needed to determine whether ``x``'s live
+range ends after the RMW.  Since liveness analysis is one of the most expensive
+passes, it's not attractive to run it an extra time just for RMW analysis.
+Instead, we essentially generate both the RMW and the non-RMW versions, and then
+during lowering, the RMW version deletes itself if it finds x still live.
+
+X86 compare-branch inference
+^^^^^^^^^^^^^^^^^^^^^^^^^^^^
+
+In the LLVM instruction set, the compare/branch pattern works like this::
+
+    cond = icmp eq a, b
+    br cond, target
+
+The result of the icmp instruction is a single bit, and a conditional branch
+tests that bit.  By contrast, most target architectures use this pattern::
+
+    cmp a, b  // implicitly sets various bits of FLAGS register
+    br eq, target  // branch on a particular FLAGS bit
+
+A naive lowering sequence conditionally sets ``cond`` to 0 or 1, then tests
+``cond`` and conditionally branches.  Subzero has a pass that identifies
+boolean-based operations like this and folds them into a single
+compare/branch-like operation.  It is set up for more than just cmp/br though.
+Boolean producers include icmp (integer compare), fcmp (floating-point compare),
+and trunc (integer truncation when the destination has bool type).  Boolean
+consumers include branch, select (the ternary operator from the C language), and
+sign-extend and zero-extend when the source has bool type.
+
+Sandboxing
+^^^^^^^^^^
+
+Native Client's sandbox model uses software fault isolation (SFI) to help
+provide safety when running untrusted code in a browser or other environment.

[JF, 2015/09/03 00:35:21]

Drop "help".

[Jim Stichnoth, 2015/09/03 06:47:03]

Done.

+Subzero implements Native Client's sandboxing to enable Subzero-translated

[JF, 2015/09/03 00:35:21]

Re-link to
https://developer.chrome.com/native-client/reference/sandbox_internals/index

[Jim Stichnoth, 2015/09/03 06:47:03]

Done.

+executables to be run inside Chrome.  Subzero also provides a fairly simple
+framework for investigating alternative sandbox models or other restrictions on
+the sandbox model.
+
+Sandboxing in Subzero is not actually implemented as a separate pass, but is
+integrated into lowering and assembly.
+
+- Indirect branches, including the ret instruction, are masked to a bundle
+  boundary and bundle-locked.
+
+- Call instructions are aligned to the end of the bundle so that the return
+  address is bundle-aligned.
+
+- Indirect branch targets, including function entry and targets in a switch
+  statement jump table, are bundle-aligned.
+
+- The intrinsic for reading the thread pointer is inlined appropriately.
+
+- For x86-64, non-stack memory accesses are with respect to the reserved sandbox
+  base register.  We reduce the aggressiveness of address mode inference to
+  leave room for the sandbox base register during lowering.  There are no memory
+  sandboxing changes for x86-32.
+
+Code emission
+-------------
+
+Subzero's integrated assembler is derived from Dart's `assembler code
+<https://github.com/dart-lang/sdk/tree/master/runtime/vm>'_.  There is a pass
+that iterates through the low-level ICE instructions and invokes the relevant
+assembler functions.  Placeholders are added for later fixup of branch target
+offsets.  (Backward branches use short offsets if possible; forward branches
+always use long offsets.)  The assembler emits into a staging buffer.  Once
+emission into the staging buffer for a function is complete, the data is emitted
+to the output file as an ELF object file, and metadata such as relocations,
+symbol table, and string table, are accumulated for emission at the end.  Global
+data initializers are emitted similarly.  A key point is that at this point, the
+staging buffer can be deallocated, and only a minimum of data needs to held
+until the end.
+
+As a debugging alternative, Subzero can emit textual assembly code which can
+then be run through an external assembler.  This is of course super slow, but
+quite valuable when bringing up a new target.
+
+As another debugging option, the staging buffer can be emitted as textual
+assembly, primarily in the form of ".byte" lines.  This allows the assembler to
+be tested separately from the ELF related code.
+
+Memory management
+-----------------
+
+Where possible, we allocate from a ``CfgLocalAllocator`` which derives from
+LLVM's ``BumpPtrAllocator``.  This is an arena-style allocator where objects
+allocated from the arena are never actually freed; instead, when the CFG
+translation completes and the CFG is deleted, the entire arena memory is
+reclaimed at once.  This style of allocation works well in an environment like a
+compiler where there are distinct phases with only easily-identifiable objects
+living across phases.  It frees the developer from having to manage object
+deletion, and it amortizes deletion costs across just a single arena deletion at
+the end of the phase.  Furthermore, it helps scalability by allocating entirely
+from thread-local memory pools, and minimizing global locking of the heap.
+
+Instructions are probably the most heavily allocated complex class in Subzero.
+We represent an instruction list as an intrusive doubly linked list, allocate
+all instructions from the ``CfgLocalAllocator``, and we make sure each
+instruction subclass is basically `POD
+<http://en.cppreference.com/w/cpp/concept/PODType>`_ (Plain Old Data) with a
+trivial destructor.  This way, when the CFG is finished, we don't need to
+individually deallocate every instruction.  We do similar for Variables, which
+is probably the second most popular complex class.
+
+There are some situations where passes need to use some `STL container class
+<http://en.cppreference.com/w/cpp/container>`_.  Subzero has a way of using the
+``CfgLocalAllocator`` as the container allocator if this is needed.

[JF, 2015/09/03 00:35:21]

This STL mention reminds me: you don't explain how subzero uses LLVM! It's built
as a separate tool, which only uses the stand-alone LLVM utility library ADT.

I don't think this is the right place for it, but it should be somewhere in the
document.

[Jim Stichnoth, 2015/09/03 06:47:03]

Good point, and I agree there's not an obvious place to mention it.

I mentioned the ADT and Support stuff as part of the translator size discussion,
and a mention of including the IR in a non-MINIMAL build.

+
+Multithreaded translation
+-------------------------
+
+Subzero is designed to be able to translate functions in parallel.  With the
+``-threads=N`` command-line option, there is a 3-stage producer-consumer
+pipeline:
+
+- A single thread parses the ``.pexe`` file and produces a sequence of work
+  units.  A work unit can be either a fully constructed CFG, or a set of global
+  initializers.  The work unit includes its sequence number denoting its parse
+  order.  Each work unit is added to the translation queue.
+
+- There are N translation threads that draw work units from the translation
+  queue and lower them into assembler buffers.  Each assembler buffer is added
+  to the emitter queue, tagged with its sequence number.  The CFG and its
+  ``CfgLocalAllocator`` are disposed of at this point.
+
+- A single thread draws assembler buffers from the emitter queue and appends to
+  the output file.  It uses the sequence numbers to reintegrate the assembler
+  buffers according to the original parse order, such that output order is
+  always deterministic.
+
+This means that with ``-threads=N``, there are actually ``N+1`` spawned threads
+for a total of ``N+2`` execution threads, taking the parser and emitter threads
+into account.  For the special case of ``N=0``, execution is entirely sequential
+-- the same thread parses, translates, and emits, one function at a time.  This
+is useful for performance measurements.
+
+Ideally, we would like to get near-linear scalability as the number of
+translation threads increases.  We expect that ``-threads=1`` should be slightly
+faster than ``-threads=0`` as the small amount of time spent parsing and
+emitting is done largely in parallel with translation.  With perfect
+scalability, we see ``-threads=N`` translating ``N`` times as fast as
+``-threads=1``, up until the point where parsing or emitting becomes the
+bottleneck, or ``N+2`` exceeds the number of CPU cores.  In reality, memory
+performance would become a bottleneck and efficiency might peak at, say, 75%.
+
+Currently, parsing takes about 11% of total sequential time.  If translation
+scalability ever gets so fast and awesomely scalable that parsing becomes a
+bottleneck, it should be possible to make parsing multithreaded as well.
+
+Internally, all shared, mutable data is held in the GlobalContext object, and
+access to each field is guarded by a mutex.
+
+Security
+--------
+
+Subzero includes a number of security features in the generated code, as well as
+in the Subzero translator itself, which run on top of the existing Native Client
+sandbox as well as Chrome's OS-level sandbox.
+
+Sandboxed translator
+^^^^^^^^^^^^^^^^^^^^
+
+When running inside the browser, the Subzero translator executes as sandboxed,
+untrusted code that is initially checked by the validator, just like the
+LLVM-based ``pnacl-llc`` translator.  As such, the Subzero binary should be no
+more or less secure than the translator it replaces, from the point of view of
+the Chrome sandbox.  That said, Subzero is much smaller than ``pnacl-llc`` and
+was designed from the start with security in mind, so one expects fewer attacker
+opportunities here.
+
+Code diversification
+^^^^^^^^^^^^^^^^^^^^
+
+`Return-oriented programming
+<https://en.wikipedia.org/wiki/Return-oriented_programming>`_ (ROP) is a
+now-common technique for starting with e.g. a known buffer overflow situation
+and launching it into a deeper exploit.  The attacker scans the executable
+looking for ROP gadgets, which are short sequences of code that happen to load
+known values into known registers and then return.  An attacker who manages to
+overwrite parts of the stack can overwrite it with carefully chosen return
+addresses such that certain ROP gadgets are effectively chained together to set
+up the register state as desired, finally returning to some code that manages to
+do something nasty based on those register values.
+
+If there is a popular ``.pexe`` with a large install base, the attacker could
+run Subzero on it and scan the executable for suitable ROP gadgets to use as
+part of a potential exploit.  Note that if the trusted validator is working
+correctly, these ROP gadgets are limited to starting at a bundle boundary and
+cannot use the trick of finding a gadget that happens to begin inside another
+instruction.  All the same, gadgets with these constraints still exist and the
+attacker has access to them.  This is the attack model we focus most on --
+protecting the user against misuse of a "trusted" developer's application, as
+opposed to mischief from a malicious ``.pexe`` file.
+
+Subzero can mitigate these attacks to some degree through code diversification.
+Specifically, we can apply some randomness to the code generation that makes ROP
+gadgets less predictable.  This randomness can have some compile-time cost, and
+it can affect the code quality; and some diversifications may be more effective
+than others.  A more detailed treatment of hardening techniques may be found in
+the Matasano report "`Attacking Clientside JIT Compilers
+<https://www.nccgroup.trust/globalassets/resources/us/presentations/documents/attacking_clientside_jit_compilers_paper.pdf>`_".
+
+To evaluate diversification effectiveness, we use a third-party ROP gadget
+finder and limit its results to bundle-aligned addresses.  For a given
+diversification technique, we run it with a number of different random seeds,
+find ROP gadgets for each version, and determine how persistent each ROP gadget
+is across the different versions.  A gadget is persistent if the same gadget is
+found at the same code address.  The best diversifications are ones with low
+gadget persistence rates.
+
+Subzero implements 7 different diversification techniques.  Below is a
+discussion of each technique, its effectiveness, and its cost.  The discussions
+of cost and effectiveness are for a single diversification technique; the
+translation-time costs for multiple techniques are additive, but the effects of
+multiple techniques on code quality and effectiveness are not yet known.
+
+In Subzero's implementation, each randomization is "repeatable" in a sense.
+Each pass that includes a randomization option gets its own private instance of
+a random number generator (RNG).  The RNG is seeded with a combination of a
+global seed, the pass ID, and the function's sequence number.  The global seed
+is designed to be different across runs (perhaps based on the current time), but
+for debugging, the global seed can be set to a specific value and the results
+will be repeatable.
+
+Subzero-generated code is subject to diversification once per translation, and
+then Chrome caches the diversified binary for subsequent executions.  An
+attacker may attempt to run the binary multiple times hoping for
+higher-probability combinations of ROP gadgets.  When the attacker guesses
+wrong, a likely outcome is an application crash.  Chrome throttles creation of
+crashy processes which reduces the likelihood of the attacker eventually gaining
+a foothold.
+
+Constant blinding
+~~~~~~~~~~~~~~~~~
+
+Here, we prevent attackers from controlling large immediates in the text
+(executable) section.  A random cookie is generated for each function, and if
+the constant exceeds a specified threshold, the constant is obfuscated with the
+cookie and equivalent code is generated.  For example, instead of this x86
+instruction::
+
+    mov $0x11223344, <%Reg/Mem>
+
+the following code might be generated::
+
+    mov $(0x11223344+Cookie), %temp
+    lea -Cookie(%temp), %temp
+    mov %temp, <%Reg/Mem>
+
+The ``lea`` instruction is used rather than e.g. ``add``/``sub`` or ``xor``, to
+prevent unintended effects on the flags register.
+
+This transformation has almost no effect on translation time, and about 1%
+impact on code quality, depending on the threshold chosen.  It does little to
+reduce gadget persistence, but it does remove a lot of potential opportunities
+to construct intra-instruction ROP gadgets (which an attacker could use only if
+a validator bug were discovered, since the Native Client sandbox and associated
+validator force returns and other indirect branches to be to bundle-aligned
+addresses).
+
+Constant pooling
+~~~~~~~~~~~~~~~~
+
+This is similar to constant blinding, in that large immediates are removed from
+the text section.  In this case, each unique constant above the threshold is
+stored in a read-only data section and the constant is accessed via a memory
+load.  For the above example, the following code might be generated::
+
+    mov $Label$1, %temp
+    mov %temp, <%Reg/Mem>
+
+This has a similarly small impact on translation time and ROP gadget
+persistence, and a smaller (better) impact on code quality.  This is because it
+uses fewer instructions, and in some cases good register allocation leads to no
+increase in instruction count.  Note that this still gives an attacker some
+limited amount of control over some text section values, unless we randomize the
+constant pool layout.
+
+Static data reordering
+~~~~~~~~~~~~~~~~~~~~~~
+
+This transformation limits the attacker's ability to control bits in global data
+address references.  It simply permutes the order in memory of global variables
+and internal constant pool entries.  For the constant pool, we only permute
+within a type (i.e., emit a randomized list of ints, followed by a randomized
+list of floats, etc.) to maintain good packing in the face of alignment
+constraints.
+
+As might be expected, this has no impact on code quality, translation time, or
+ROP gadget persistence (though as above, it limits opportunities for
+intra-instruction ROP gadgets with a broken validator).
+
+Basic block reordering
+~~~~~~~~~~~~~~~~~~~~~~
+
+Here, we randomize the order of basic blocks within a function, with the
+constraint that we still want to maintain a topological order as much as
+possible, to avoid making the code too branchy.
+
+This has no impact on code quality, and about 1% impact on translation time, due
+to a separate pass to recompute layout.  It ends up having a huge effect on ROP
+gadget persistence, tied for best with nop insertion, reducing ROP gadget
+persistence to less than 5%.
+
+Function reordering
+~~~~~~~~~~~~~~~~~~~
+
+Here, we permute the order that functions are emitted, primarily to shift ROP
+gadgets around to less predictable locations.  It may also change call address
+offsets in case the attacker was trying to control that offset in the code.
+
+To control latency and memory footprint, we don't arbitrarily permute functions.
+Instead, for some relatively small value of N, we queue up N assembler buffers,
+and then emit the N functions in random order, and repeat until all functions
+are emitted.
+
+Function reordering has no impact on translation time or code quality.
+Measurements indicate that it reduces ROP gadget persistence to about 15%.
+
+Nop insertion
+~~~~~~~~~~~~~
+
+This diversification randomly adds a nop instruction after each regular
+instruction, with some probability.  Nop instructions of different lengths may
+be selected.  Nop instructions are never added inside a bundle_lock region.
+Note that when sandboxing is enabled, nop instructions are already being added
+for bundle alignment, so the diversification nop instructions may simply be
+taking the place of alignment nop instructions, though distributed differently
+through the bundle.
+
+In Subzero's currently implementation, nop insertion adds 3-5% to the
+translation time, but this is probably because it is implemented as a separate
+pass that adds actual nop instructions to the IR.  The overhead would probably
+be a lot less if it were integrated into the assembler pass.  The code quality
+is also reduced by 3-5%, making nop insertion the most expensive of the
+diversification techniques.
+
+Nop insertion is very effective in reducing ROP gadget persistence, at the same
+level as basic block randomization (less than 5%).  But given nop insertion's
+impact on translation time and code quality, one would most likely prefer to use
+basic block randomization instead (though the combined effects of the different
+diversification techniques have not yet been studied).
+
+Register allocation randomization
+~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+In this diversification, the register allocator tries to make different but
+mostly functionally equivalent choices, while maintaining stable code quality.
+
+A naive approach would be the following.  Whenever the allocator has more than
+one choice for assigning a register, choose randomly among those options.  And
+whenever there are no registers available and there is a tie for the
+lowest-weight variable, randomly select one of the lowest-weight variables to
+evict.  Because of the one-pass nature of the linear-scan algorithm, this
+randomization strategy can have a large impact on which variables are ultimately
+assigned registers, with a corresponding large impact on code quality.
+
+Instead, we choose an approach that tries to keep code quality stable regardless
+of the random seed.  We partition the set of physical registers into equivalence
+classes.  If a register is pre-colored in the function (i.e., referenced
+explicitly by name), it forms its own equivalence class.  The remaining
+registers are partitioned according to their combination of attributes such as
+integer versus floating-point, 8-bit versus 32-bit, caller-save versus
+callee-saved, etc.  Each equivalence class is randomly permuted, and the
+complete permutation is applied to the final register assignments.
+
+Register randomization reduces ROP gadget persistence to about 10% on average,
+though there tends to be fairly high variance across functions and applications.
+This probably has to do with the set of restrictions in the x86-32 instruction
+set and ABI, such as few general-purpose registers, ``%eax`` used for return
+values, ``%edx`` used for division, ``%cl`` used for shifting, etc.  As
+intended, register randomization has no impact on code quality, and a slight
+(0.5%) impact on translation time due to an extra scan over the variables to
+identify pre-colored registers.
+
+Fuzzing
+^^^^^^^
+
+We have started fuzz-testing the ``.pexe`` files input to Subzero, using a
+combination of `afl-fuzz <http://lcamtuf.coredump.cx/afl/>`_, LLVM's `libFuzzer
+<http://llvm.org/docs/LibFuzzer.html>`_, and custom tooling.  The purpose is to
+find and fix cases where Subzero crashes or otherwise ungracefully fails on
+unexpected inputs, and to do so automatically over a large range of unexpected
+inputs.  By fixing bugs that arise from fuzz testing, we reduce the possibility
+of an attacker exploiting these bugs.
+
+Most of the problems found so far are ones most appropriately handled in the
+parser.  However, there have been a couple that have identified problems in the
+lowering, or otherwise inappropriately triggered assertion failures and fatal
+errors.  We continue to dig into this area.
+
+Future security work
+^^^^^^^^^^^^^^^^^^^^
+
+Subzero is well-positioned to explore other future security enhancements, e.g.:
+
+- Tightening the Native Client sandbox.  ABI changes, such as the previous work
+  on `hiding the sandbox base address
+  <https://docs.google.com/document/d/1eskaI4353XdsJQFJLRnZzb_YIESQx4gNRzf31dqXVG8>`_
+  in x86-64, are easy to experiment with in Subzero.
+
+- Making the executable code section read-only.  This would prevent a PNaCl
+  application from inspecting its own binary and trying to find ROP gadgets even
+  after code diversification has been performed.

[JF, 2015/09/03 00:35:21]

Though this is still susceptible to "blind ROP" (link), it would substantially
improve security.

[Jim Stichnoth, 2015/09/03 06:47:03]

Cool.

+
+- Instruction selection diversification.  It may be possible to lower a given
+  instruction in several largely equivalent ways, which gives more opportunities
+  for code randomization.

[JF, 2015/09/03 00:35:21]

Mention using dataflow sanitizer as another improvement.

[Jim Stichnoth, 2015/09/03 06:47:03]

Before doing that, what are your thoughts on how it could be used?  What aspect
of Subzero or its generated code would be getting the taint analysis?

[JF, 2015/09/03 16:18:50]

Oops, I meant this:
http://clang.llvm.org/docs/ControlFlowIntegrity.html

I'm confusing the names of two of Peter's projects, though I now realize that
their names are actually quite descriptive.

[Jim Stichnoth, 2015/09/03 18:21:24]

Ah, much better.  Added essentially a TODO for that.

+
+Chrome integration
+------------------
+
+Currently Subzero is available in Chrome for the x86-32 architecture, but under
+a flag.  When the flag is enabled, Subzero is used when the `manifest file
+<https://developer.chrome.com/native-client/reference/nacl-manifest-format>`_
+linking to the ``.pexe`` file specifies the ``O0`` optimization level.
+
+The next step is to remove the flag, i.e. invoke Subzero as the only translator
+for ``O0``-specified manifest files.
+
+Ultimately, Subzero might produce code rivaling LLVM ``O2`` quality, in which
+case Subzero could be used for all PNaCl translation.
+
+Command line options
+--------------------
+
+Subzero has a number of command-line options for debugging and diagnostics.
+Among the more interesting are the following.
+
+- Using the ``-verbose`` flag, Subzero will dump the CFG, or produce other
+  diagnostic output, with various levels of detail after each pass.  Instruction
+  numbers can be printed or suppressed.  Deleted instructions can be printed or
+  suppressed (they are retained in the instruction list, as discussed earlier,
+  because they can help explain how lower-level instructions originated).
+  Liveness information can be printed when available.  Details of register
+  allocation can be printed as register allocator decisions are made.  And more.
+
+- Running Subzero with any level of verbosity produces an enormous amount of
+  output.  When debugging a single function, verbose output can be suppressed
+  except for a particular function.  The ``-verbose-focus`` flag suppresses
+  verbose output except for the specified function.
+
+- Subzero has a ``-timing`` option that prints a breakdown of pass-level timing
+  at exit.  Timing markers can be placed in the Subzero source code to demarcate
+  logical operations or passes of interest.  Basic timing information plus
+  call-stack type timing information is printed at the end.
+
+- Along with ``-timing``, the user can instead get a report on the overall
+  translation time for each function, to help focus on timing outliers.  Also,
+  ``-timing-focus`` limits the ``-timing`` reporting to a single function,
+  instead of aggregating pass timing across all functions.
+
+- The ``-szstats`` option reports various statistics on each function, such as
+  stack frame size, static instruction count, etc.  It may be helpful to track
+  these stats over time as Subzero is improved, as an approximate measure of
+  code quality.
+
+- The flag ``-asm-verbose``, in conjunction with emitting textual assembly
+  output, annotate the assembly output with register-focused liveness
+  information.  In particular, each basic block is annotated with which
+  registers are live-in and live-out, and each instruction is annotated with
+  which registers' and stack locations' live ranges end at that instruction.
+  This is really useful when studying the generated code to find opportunities
+  for code quality improvements.
+
+Testing and debugging
+---------------------
+
+LLVM lit tests
+^^^^^^^^^^^^^^
+
+For basic testing, Subzero uses LLVM's `lit
+<http://llvm.org/docs/CommandGuide/lit.html>`_ framework for running tests.  We
+have a suite of hundreds of small functions where we test for particular
+assembly code patterns across different target architectures.
+
+Cross tests
+^^^^^^^^^^^
+
+Unfortunately, the lit tests don't do a great job of precisely testing the
+correctness of the output.  Much better are the cross tests, which are execution
+tests that compare Subzero and ``pnacl-llc`` translated bitcode across a wide
+variety of interesting inputs.  Each cross test consists of a set of C, C++,
+and/or low-level bitcode files.  The C and C++ source files are compiled down to
+bitcode.  The bitcode files are translated by ``pnacl-llc`` and also by Subzero.
+Subzero mangles global symbol names with a special prefix to avoid duplicate
+symbol errors.  A driver program invokes both versions on a large set of
+interesting inputs, and reports when the Subzero and ``pnacl-llc`` results
+differ.  Cross tests turn out to be an excellent way of testing the basic
+lowering patterns, but they are less useful for testing more global things like
+liveness analysis and register allocation.
+
+Bisection debugging
+^^^^^^^^^^^^^^^^^^^
+
+Sometimes with a new application, Subzero will end up producing incorrect code
+that either crashes at runtime or otherwise produces the wrong results.  When
+this happens, we need to narrow it down to a single function (or small set of
+functions) that yield incorrect behavior.  For this, we have a bisection
+debugging framework.  Here, we initially translate the entire application once
+with Subzero and once with ``pnacl-llc``.  We then use ``objdump`` to
+selectively weaken symbols based on a whitelist or blacklist provided on the
+command line.  The two object files can then be linked together without link
+errors, with the desired version of each method "winning".  Then the binary is
+tested, and bisection proceeds based on whether the binary produces correct
+output.
+
+When the bisection completes, we are left with a minimal set of
+Subzero-translated functions that cause the failure.  Usually it is a single
+function, though sometimes it might require a combination of several functions
+to cause a failure; this may be due to an incorrect call ABI, for example.
+However, Murphy's Law implies that the single failing function is enormous and
+impractical to debug.  In that case, we can restart the bisection, explicitly
+blacklisting the enormous function, and try to find another candidate to debug.
+(Future work is to automate this to find all minimal sets of functions, so that
+debugging can focus on the simplest example.)
+
+Fuzz testing
+^^^^^^^^^^^^
+
+As described above, we try to find internal Subzero bugs using fuzz testing
+techniques.
+
+Sanitizers
+^^^^^^^^^^
+
+Subzero can be built with `AddressSanitizer
+<http://clang.llvm.org/docs/AddressSanitizer.html>`_ (ASan) and/or
+`ThreadSanitizer <http://clang.llvm.org/docs/ThreadSanitizer.html>`_ (TSan)
+support.  This is done using something as simple as ``make ASAN=1 TSAN=1``.  So
+far, multithreading has been simple enough that TSan hasn't found any bugs, but
+ASan has found at least one memory leak which was subsequently fixed.
+`UndefinedBehaviorSanitizer
+<http://clang.llvm.org/docs/UsersManual.html#controlling-code-generation>`_
+(UBSan) support is in progress.
+
+Current status
+==============
+
+Target architectures
+--------------------
+
+Subzero is currently more or less complete for the x86-32 target.  It has been
+refactored and extended to handle x86-64 as well, and that is mostly complete at
+this point.
+
+ARM32 work is in progress.  It currently lacks the testing level of x86, at
+least in part because Subzero's register allocator needs modifications to handle
+ARM's aliasing of floating point and vector registers.  Specifically, a 64-bit
+register is actually a gang of two consecutive and aligned 32-bit registers, and
+a 128-bit register is a gang of 4 consecutive and aligned 32-bit registers.
+ARM64 work has not started; when it does, it will be native-only since the
+Native Client sandbox model, validator, and other tools have never been defined.
+
+An external contributor is adding MIPS support, in most part by following the
+ARM work.
+
+Translator performance
+----------------------
+
+Single-threaded translation speed is currently about 5× the ``pnacl-llc``
+translation speed.  For a large ``.pexe`` file, the time breaks down as:
+
+- 11% for parsing and initial IR building
+
+- 4% for emitting to /dev/null
+
+- 27% for liveness analysis (two liveness passes plus live range construction)
+
+- 15% for linear-scan register allocation
+
+- 9% for basic lowering
+
+- 10% for advanced phi lowering
+
+- ~11% for other minor analysis
+
+- ~10% measurement overhead to acquire these numbers
+
+Some improvements could undoubtedly be made, but it will be hard to increase the
+speed to 10× of ``pnacl-llc`` while keeping acceptable code quality.  With
+``-Om1`` (lack of) optimization, we do actually achieve roughly 10×
+``pnacl-llc`` translation speed, but code quality drops by a factor of 3.
+
+Code quality
+------------
+
+Measured across 16 components of spec2k, Subzero's code quality is uniformly
+better than ``pnacl-llc`` ``-O0`` code quality, and in many cases solidly
+between ``pnacl-llc`` ``-O0`` and ``-O2``.
+
+Translator size
+---------------
+
+When built in MINIMAL mode, the x86-64 native translator size for the x86-32
+target is about 700 KB, not including the size of functions referenced in
+dynamically-linked libraries.  The sandboxed version of Subzero is a bit over 1
+MB, and it is statically linked and also includes nop padding for bundling as
+well as indirect branch masking.
+
+Translator memory footprint
+---------------------------
+
+It's hard to draw firm conclusions about memory footprint, since the footprint
+is at least proportional to the input function size, and there is no real limit
+on the size of functions in the ``.pexe`` file.
+
+That said, we looked at the memory footprint over time as Subzero translated
+``pnacl-llc.pexe``, which is the largest ``.pexe`` file (7.2 MB) at our
+disposal.  One of LLVM's libraries that Subzero uses can report the current
+malloc heap usage.  With single-threaded translation, Subzero tends to hover
+around 15 MB of memory usage.  There are a couple of monstrous functions where
+Subzero grows to around 100 MB, but then it drops back down after those
+functions finish translating.  In contrast, ``pnacl-llc`` grows larger and
+larger throughout translation, reaching several hundred MB by the time it
+completes.
+
+It's a bit more interesting when we enable multithreaded translation.  When
+there are N translation threads, Subzero implements a policy that limits the
+size of the translation queue to N entries -- if it is "full" when the parser
+tries to add a new CFG, the parser blocks until one of the translation threads
+removes a CFG.  This means the number of in-memory CFGs can (and generally does)
+reach 2*N+1, and so the memory footprint rises in proportion to the number of
+threads.  Adding to the pressure is the observation that the monstrous functions
+also take proportionally longer time to translate, so there's a good chance many
+of the monstrous functions will be active at the same time with multithreaded
+translation.  As a result, for N=32, Subzero's memory footprint peaks at about
+260 MB, but drops back down as the large functions finish translating.
+
+If this peak memory size becomes a problem, it might be possible for the parser
+to resequence the functions to try to spread out the larger functions, or to
+throttle the translation queue to prevent too many in-flight large functions.
+It may also be possible to throttle based on memory pressure signaling from
+Chrome.
+
+Translator scalability
+----------------------
+
+Currently scalability is "not very good".  Multiple translation threads lead to
+faster translation, but not to the degree desired.  We haven't dug in to
+investigate yet.
+
+There are a few areas to investigate.  First, there may be contention on the
+constant pool, which all threads access, and which requires locked access even
+for reading.  This could be mitigated by keeping a CFG-local cache of the most
+common constants.
+
+Second, there may be contention on memory allocation.  While almost all CFG
+objects are allocated from the CFG-local allocator, some passes use temporary
+STL containers that use the default allocator, which may require global locking.
+This could be mitigated by switching these to the CFG-local allocator.
+
+Third, multithreading may make the default allocator strategy more expensive.
+In a single-threaded environment, a pass will allocate its containers, run the
+pass, and deallocate the containers.  This results in stack-like allocation
+behavior and makes the heap free list easier to manage, with less heap
+fragmentation.  But when multithreading is added, the allocations and
+deallocations become much less stack-like, making allocation and deallocation
+operations individually more expensive.  Again, this could be mitigated by
+switching these to the CFG-local allocator.