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 10× slower than download
+  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 has two optimization recipes: full
+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 the high-end
+Xeon workstation.
+
+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
+is distributed to a billion Chrome users.  Thus we target a 10× reduction 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.
+
+Subzero leverages some data structures from LLVM's ``ADT`` and ``Support``
+include directories, which have little impact on translator size.  It also uses
+some of LLVM's bitcode decoding code (for binary-format ``.pexe`` files), again
+with little size impact.  In non-``MINIMAL`` builds, the translator size is much
+larger due to including code for parsing text-format bitcode files and forming
+LLVM IR.
+
+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 and sometimes a reality of
+out-of-memory tab killing, especially noticeable on weaker systems.
+
+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
+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.

[jvoung (off chromium), 2015/09/03 14:40:25]

If you take the pexe with symbols and emit dwarf, it seems that by "high-level
debuggability", you don't mean "source-level" (or, that you would consider the
pexe as the "source" and not the c/c++ code).

To debug at the c/c++ level, you would need something like the llvm.dbg
intrinsics and metadata that we strip out too to actually have line numbers in
stack traces, track inlining, track source variables (which have undergone some
alpha-renaming and ssa conversion, etc.).

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

Oh, excellent point.  I added that to the discussion.

+
+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

[jvoung (off chromium), 2015/09/03 14:40:25]

related to optimized templates: things like bool folding?

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

Bool folding is one place, but I added a simpler example instead -- x=x+1 being
potentially simpler than x=1+x (ignoring the non-SSA aspect).

+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:
+

[jvoung (off chromium), 2015/09/03 14:40:25]

Loop nest analysis too, but I guess that's still in progress.

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

Done.

+- 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 provide
+safety when running untrusted code in a browser or other environment.  Subzero
+implements Native Client's `sandboxing
+<https://developer.chrome.com/native-client/reference/sandbox_internals/index>`_
+to enable Subzero-translated 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

[jvoung (off chromium), 2015/09/03 14:40:25]

Technically, some known-near forward branches injected by lowering will use
short offsets.  It's the forward branches come from the original CFG that harder
to predict and "always use long offsets".

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

Done.

+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.
+
+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.  It may still be susceptible to
+  `blind ROP <http://www.scs.stanford.edu/brop/bittau-brop.pdf>`_ attacks,
+  security is still overall improved.
+
+- Instruction selection diversification.  It may be possible to lower a given
+  instruction in several largely equivalent ways, which gives more opportunities
+  for code randomization.
+
+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

[jvoung (off chromium), 2015/09/03 14:40:25]

I don't they can analyze both simultaneously =)

"clang: error: invalid argument '-fsanitize=address' not allowed with
'-fsanitize=thread'"

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

Oops!  Split this into two examples.

+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.