move .rst to docs

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      |
-+-----------------------------------+-----------------------+
-| Loop nest analysis                |                       |
-+-----------------------------------+-----------------------+
-| 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.
-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.  That said, fully supporting debuggability
-would require a few additions:
-
-- DWARF support would need to be added to Subzero's ELF file emitter.  Subzero
-  propagates global symbol names, local variable names, and function-internal
-  label names that are present in the ``.pexe`` file.  This would allow a
-  debugger to map addresses back to symbols in the ``.pexe`` file.
-
-- To map ``.pexe`` file symbols back to meaningful source-level symbol names,
-  file names, line numbers, etc., Subzero would need to handle `LLVM bitcode
-  metadata <http://llvm.org/docs/LangRef.html#metadata>`_ and ``llvm.dbg``
-  `instrinsics<http://llvm.org/docs/LangRef.html#dbg-intrinsics>`_.
-
-- The PNaCl toolchain explicitly strips all this from the ``.pexe`` file, and so
-  the toolchain would need to be modified to preserve it.
-
-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 (for
-example, ``x=x+1`` might allow a bettern lowering than ``x=1+x``).  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:
-
-- Loop nest analysis
-
-- 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
-generally use long offsets unless it is an intra-block branch of "known" short
-length.)  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.
-
-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) or `ThreadSanitizer
-<http://clang.llvm.org/docs/ThreadSanitizer.html>`_ (TSan) support.  This is
-done using something as simple as ``make ASAN=1`` or ``make 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.  `Control flow integrity sanitization
-<http://clang.llvm.org/docs/ControlFlowIntegrity.html>`_ is also under
-consideration.
-
-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.