Subzero: Use CFG-local arena allocation for relevant containers.

ALLOCATION.rst

Index: ALLOCATION.rst
diff --git a/ALLOCATION.rst b/ALLOCATION.rst
new file mode 100644
index 0000000000000000000000000000000000000000..d902bf9e73b834fb6a573316c416b601b2e88248
--- /dev/null
+++ b/ALLOCATION.rst
@@ -0,0 +1,78 @@
+Object allocation and lifetime in ICE

[JF, 2014/12/19 05:34:41]

You'll need to link to this document from another rst document, assuming `make
documentation` does anything!

[Jim Stichnoth, 2014/12/19 15:22:28]

Hmm, I guess maybe I need a new document to add a TODO to...

+=====================================
+
+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 and constructing the

[JF, 2014/12/19 05:34:41]

I'd mention that parsing overlaps download.

[Jim Stichnoth, 2014/12/19 15:22:28]

Done.

+initial high-level ICE.  The result is a set of Cfg pointers.  The parser thread
+incrementally adds a Cfg pointer to the set after the Cfg is created, and then
+moves on to parse the next function.

[JF, 2014/12/19 05:34:41]

I'd call it a queue, since's it's pretty much FIFO (ignoring randomization).
Same thing later in this document.

[Jim Stichnoth, 2014/12/19 15:22:28]

Changed all sets to queues.  Also added a subsection about making emission
deterministic with multithreaded translation, for regression testing.  This
includes function order as well as constant pool order; let me know if you can
think of other possible nondeterminism.

+
+Multiple translation worker threads draw from the set of Cfg pointers as they
+are added to the set, such that several functions can be translated in parallel.
+The result is a set 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 set that the translation threads
+write to.
+
+This means that Cfgs are created by the parser thread and destroyed by the
+translation thread, and assembler buffers are created by the translation thread

[JF, 2014/12/19 05:34:41]

In the middle: new IR nodes are created in a Cfg by the workers.

[Jim Stichnoth, 2014/12/19 15:22:28]

Done (including Cfg nodes, instructions, and most kinds of operands).

+and destroyed by the writer thread.
+
+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
+lookup 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 only one Cfg is active at a time.

[JF, 2014/12/19 05:34:41]

Only one Cfg is active at a time in a given thread (either the parser thread, or
one of the workers).

[Jim Stichnoth, 2014/12/19 15:22:28]

Done.

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

[JF, 2014/12/19 05:34:41]

Ownership of the assembly buffers is transfered to the thread responsible for
ELF file writing.

[Jim Stichnoth, 2014/12/19 15:22:28]

Done.

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

[JF, 2014/12/19 05:34:41]

Mention tsan testing in a new section.

[Jim Stichnoth, 2014/12/19 15:22:28]

Done.