move .rst to docs

ALLOCATION.rst

-Object allocation and lifetime in ICE
-=====================================
-
-This document discusses object lifetime and scoping issues, starting with
-bitcode parsing and ending with ELF file emission.
-
-Multithreaded translation model
--------------------------------
-
-A single thread is responsible for parsing PNaCl bitcode (possibly concurrently
-with downloading the bitcode file) and constructing the initial high-level ICE.
-The result is a queue of Cfg pointers.  The parser thread incrementally adds a
-Cfg pointer to the queue after the Cfg is created, and then moves on to parse
-the next function.
-
-Multiple translation worker threads draw from the queue of Cfg pointers as they
-are added to the queue, such that several functions can be translated in parallel.
-The result is a queue of assembler buffers, each of which consists of machine code
-plus fixups.
-
-A single thread is responsible for writing the assembler buffers to an ELF file.
-It consumes the assembler buffers from the queue that the translation threads
-write to.
-
-This means that Cfgs are created by the parser thread and destroyed by the
-translation thread (including Cfg nodes, instructions, and most kinds of
-operands), and assembler buffers are created by the translation thread and
-destroyed by the writer thread.
-
-Deterministic execution
-^^^^^^^^^^^^^^^^^^^^^^^
-
-Although code randomization is a key aspect of security, deterministic and
-repeatable translation is sometimes needed, e.g. for regression testing.
-Multithreaded translation introduces potential for randomness that may need to
-be made deterministic.
-
-* Bitcode parsing is sequential, so it's easy to use a FIFO queue to keep the
-  translation queue in deterministic order.  But since translation is
-  multithreaded, FIFO order for the assembler buffer queue may not be
-  deterministic.  The writer thread would be responsible for reordering the
-  buffers, potentially waiting for slower translations to complete even if other
-  assembler buffers are available.
-
-* Different translation threads may add new constant pool entries at different
-  times.  Some constant pool entries are emitted as read-only data.  This
-  includes floating-point constants for x86, as well as integer immediate
-  randomization through constant pooling.  These constant pool entries are
-  emitted after all assembler buffers have been written.  The writer needs to be
-  able to sort them deterministically before emitting them.
-
-Object lifetimes
-----------------
-
-Objects of type Constant, or a subclass of Constant, are pooled globally.  The
-pooling is managed by the GlobalContext class.  Since Constants are added or
-looked up by translation threads and the parser thread, access to the constant
-pools, as well as GlobalContext in general, need to be arbitrated by locks.
-(It's possible that if there's too much contention, we can maintain a
-thread-local cache for Constant pool lookups.)  Constants live across all
-function translations, and are destroyed only at the end.
-
-Several object types are scoped within the lifetime of the Cfg.  These include
-CfgNode, Inst, Variable, and any target-specific subclasses of Inst and Operand.
-When the Cfg is destroyed, these scoped objects are destroyed as well.  To keep
-this cheap, the Cfg includes a slab allocator from which these objects are
-allocated, and the objects should not contain fields with non-trivial
-destructors.  Most of these fields are POD, but in a couple of cases these
-fields are STL containers.  We deal with this, and avoid leaking memory, by
-providing the container with an allocator that uses the Cfg-local slab
-allocator.  Since the container allocator generally needs to be stateless, we
-store a pointer to the slab allocator in thread-local storage (TLS).  This is
-straightforward since on any of the threads, only one Cfg is active at a time,
-and a given Cfg is only active in one thread at a time (either the parser
-thread, or at most one translation thread, or the writer thread).
-
-Even though there is a one-to-one correspondence between Cfgs and assembler
-buffers, they need to use different allocators.  This is because the translation
-thread wants to destroy the Cfg and reclaim all its memory after translation
-completes, but possibly before the assembly buffer is written to the ELF file.
-Ownership of the assembler buffer and its allocator are transferred to the
-writer thread after translation completes, similar to the way ownership of the
-Cfg and its allocator are transferred to the translation thread after parsing
-completes.
-
-Allocators and TLS
-------------------
-
-Part of the Cfg building, and transformations on the Cfg, include STL container
-operations which may need to allocate additional memory in a stateless fashion.
-This requires maintaining the proper slab allocator pointer in TLS.
-
-When the parser thread creates a new Cfg object, it puts a pointer to the Cfg's
-slab allocator into its own TLS.  This is used as the Cfg is built within the
-parser thread.  After the Cfg is built, the parser thread clears its allocator
-pointer, adds the new Cfg pointer to the translation queue, continues with the
-next function.
-
-When the translation thread grabs a new Cfg pointer, it installs the Cfg's slab
-allocator into its TLS and translates the function.  When generating the
-assembly buffer, it must take care not to use the Cfg's slab allocator.  If
-there is a slab allocator for the assembler buffer, a pointer to it can also be
-installed in TLS if needed.
-
-The translation thread destroys the Cfg when it is done translating, including
-the Cfg's slab allocator, and clears the allocator pointer from its TLS.
-Likewise, the writer thread destroys the assembler buffer when it is finished
-with it.
-
-Thread safety
--------------
-
-The parse/translate/write stages of the translation pipeline are fairly
-independent, with little opportunity for threads to interfere.  The Subzero
-design calls for all shared accesses to go through the GlobalContext, which adds
-locking as appropriate.  This includes the coarse-grain work queues for Cfgs and
-assembler buffers.  It also includes finer-grain access to constant pool
-entries, as well as output streams for verbose debugging output.
-
-If locked access to constant pools becomes a bottleneck, we can investigate
-thread-local caches of constants (as mentioned earlier).  Also, it should be
-safe though slightly less efficient to allow duplicate copies of constants
-across threads (which could be de-dupped by the writer at the end).
-
-We will use ThreadSanitizer as a way to detect potential data races in the
-implementation.