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

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

In particular, node lists for in and out edges of a CfgNode, and the live range segment list in a Variable.  This is done by making the Cfg allocator globally available through TLS, and providing the STL containers with an allocator struct that uses this.

This also cleans up some other allocation-related issues:

* The allocator is now hung off the Cfg via a pointer, rather than being embedded into the Cfg.  This allows a const Cfg pointer to be stored in TLS while still allowing its allocator to be mutated.

* Cfg is now created via a static create() method.

* The redundant Cfg::allocateInst<> methods are removed.

* The Variable::asType() method allocates a whole new Variable from the Cfg arena, rather than allocating it on the stack, removing the need for the move constructor in Variable and Operand.  This is OK since asType() is only used for textual asm emission.

* The same 1MB arena allocator is now used by the assembler as well.  The fact that it wasn't changed over to be the same as Cfg and GlobalContext was an oversight.  (It turns out this adds ~3MB to the translator memory footprint, so that could be tuned later.)

BUG= none
R=jfb@chromium.org, jvoung@chromium.org

Committed: https://gerrit.chromium.org/gerrit/gitweb?p=native_client/pnacl-subzero.git;a=commit;h=31c955905a2d861a944f1e0ca60cd9e4c6f1b37d

[Jim Stichnoth, 2014-12-18 05:25:53]

stichnot@chromium.org changed reviewers:
+ jfb@chromium.org, jvoung@chromium.org, kschimpf@google.com

[Jim Stichnoth, 2014-12-18 05:27:09]

This reduces the pnacl-llc.pexe footprint from 33MB to 12MB.  Translation time
seems as good or better than before.

[JF, 2014-12-18 06:36:53]

https://codereview.chromium.org/802183004/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/802183004/diff/20001/src/IceCfg.cpp#newcode26
src/IceCfg.cpp:26: thread_local const Cfg *Cfg::CurrentCfg = NULL;
nullptr

https://codereview.chromium.org/802183004/diff/20001/src/IceCfg.cpp#newcode30
src/IceCfg.cpp:30: }
Why have this method as well as Cfg::getCurrentCfgAllocator?

https://codereview.chromium.org/802183004/diff/20001/src/IceCfg.cpp#newcode47
src/IceCfg.cpp:47: // TODO(stichnot,kschimpf): Set CurrentCfg=NULL in the dtor
for
nullptr

https://codereview.chromium.org/802183004/diff/20001/src/IceCfg.cpp#newcode51
src/IceCfg.cpp:51: // CurrentCfg to NULL).
nullptr

https://codereview.chromium.org/802183004/diff/20001/src/IceCfg.h
File src/IceCfg.h (right):

https://codereview.chromium.org/802183004/diff/20001/src/IceCfg.h#newcode39
src/IceCfg.h:39: }
You should have a symmetric "destroy" static member.

https://codereview.chromium.org/802183004/diff/20001/src/IceConverter.cpp
File src/IceConverter.cpp (right):

https://codereview.chromium.org/802183004/diff/20001/src/IceConverter.cpp#new...
src/IceConverter.cpp:86: Func = Ice::Cfg::create(Ctx);
The Cfg should probably be created (and deleted) where your thread is
created/deleted.

Though now that I think about it... Does it make sense to bound the allocator to
a single CFG? In LLVM we batch up a few functions per thread, so that as the
stream gets decoded we enqueue a few functions at a time into a worker to reduce
synchronization overhead. That would also reduce bump allocator creation
overhead, but it would increase memory usage.

https://codereview.chromium.org/802183004/diff/20001/src/IceDefs.h
File src/IceDefs.h (right):

https://codereview.chromium.org/802183004/diff/20001/src/IceDefs.h#newcode60
src/IceDefs.h:60: typedef llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 1024
* 1024>
Why 1024? The default LLVM provides is 4x that.

https://codereview.chromium.org/802183004/diff/20001/src/IceDefs.h#newcode93
src/IceDefs.h:93: typedef std::vector<CfgNode *, CfgLocalAllocator<CfgNode *> >
NodeList;
Closing braces don't need the space.

https://codereview.chromium.org/802183004/diff/20001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/802183004/diff/20001/src/IceOperand.h#newcode365
src/IceOperand.h:365: typedef std::vector<RangeElementType,
CfgLocalAllocator<RangeElementType> >
>>

[jvoung (off chromium), 2014-12-18 18:40:00]

https://codereview.chromium.org/802183004/diff/20001/src/assembler.h
File src/assembler.h (right):

https://codereview.chromium.org/802183004/diff/20001/src/assembler.h#newcode233
src/assembler.h:233: ArenaAllocator Allocator;
I wonder if the assembler should just use the CFG allocator. Its allocation
should happen after the other CFG allocations. There are tiny relocation
objects, and label objects that get allocated. Then there is the contiguous
AssemblerBuffer chunks that represent the function's .text section, that get
allocated/grow.


Anyway, that can be tuned later.

[Jim Stichnoth, 2014-12-18 23:39:56]

https://codereview.chromium.org/802183004/diff/20001/src/IceCfg.cpp
File src/IceCfg.cpp (right):

https://codereview.chromium.org/802183004/diff/20001/src/IceCfg.cpp#newcode26
src/IceCfg.cpp:26: thread_local const Cfg *Cfg::CurrentCfg = NULL;
On 2014/12/18 06:36:53, JF wrote:
> nullptr

I was planning to make a global NULL-->nullptr pass as a separate CL, and in the
meantime try to keep consistency within each file.  (Never mind the existing
single use of nullptr in this file...)

https://codereview.chromium.org/802183004/diff/20001/src/IceCfg.cpp#newcode30
src/IceCfg.cpp:30: }
On 2014/12/18 06:36:53, JF wrote:
> Why have this method as well as Cfg::getCurrentCfgAllocator?

The CfgLocalAllocator struct uses this function, and it needs to be defined
before Cfg is defined, so I broke it up this way.

https://codereview.chromium.org/802183004/diff/20001/src/IceCfg.h
File src/IceCfg.h (right):

https://codereview.chromium.org/802183004/diff/20001/src/IceCfg.h#newcode39
src/IceCfg.h:39: }
On 2014/12/18 06:36:53, JF wrote:
> You should have a symmetric "destroy" static member.

After discussion offline, I added a TODO to change the return type to
unique_ptr<Cfg> to help clarify.

Also added ALLOCATION.rst to describe object lifetime and scoping expectations.

https://codereview.chromium.org/802183004/diff/20001/src/IceConverter.cpp
File src/IceConverter.cpp (right):

https://codereview.chromium.org/802183004/diff/20001/src/IceConverter.cpp#new...
src/IceConverter.cpp:86: Func = Ice::Cfg::create(Ctx);
On 2014/12/18 06:36:53, JF wrote:
> The Cfg should probably be created (and deleted) where your thread is
> created/deleted.
> 
> Though now that I think about it... Does it make sense to bound the allocator
to
> a single CFG? In LLVM we batch up a few functions per thread, so that as the
> stream gets decoded we enqueue a few functions at a time into a worker to
reduce
> synchronization overhead. That would also reduce bump allocator creation
> overhead, but it would increase memory usage.

I think the threading will work the following way.  Parsing and initial IR
creation is done in a single thread.  That thread adds new Cfgs to a work queue
(possibly self-throttling if the work queue gets too large).  Worker threads
grab Cfgs from the work queue and translate them, and add assembly buffers to a
write queue.  A separate writer thread grabs assembly buffers from the write
queue and linearizes them to disk.

This will affect how the allocator pointer gets stored into TLS, but
fundamentally I think each Cfg and its allocator need to be tightly coupled, and
each worker thread should translate more than one Cfg.

https://codereview.chromium.org/802183004/diff/20001/src/IceDefs.h
File src/IceDefs.h (right):

https://codereview.chromium.org/802183004/diff/20001/src/IceDefs.h#newcode60
src/IceDefs.h:60: typedef llvm::BumpPtrAllocatorImpl<llvm::MallocAllocator, 1024
* 1024>
On 2014/12/18 06:36:53, JF wrote:
> Why 1024? The default LLVM provides is 4x that.

The LLVM default is 4K, I increased it to 1M in a previous CL because expansions
were showing up in the profile.

https://codereview.chromium.org/802183004/diff/20001/src/IceDefs.h#newcode93
src/IceDefs.h:93: typedef std::vector<CfgNode *, CfgLocalAllocator<CfgNode *> >
NodeList;
On 2014/12/18 06:36:53, JF wrote:
> Closing braces don't need the space.

Done.  Nice job C++, I knew you could do it!

https://codereview.chromium.org/802183004/diff/20001/src/IceOperand.h
File src/IceOperand.h (right):

https://codereview.chromium.org/802183004/diff/20001/src/IceOperand.h#newcode365
src/IceOperand.h:365: typedef std::vector<RangeElementType,
CfgLocalAllocator<RangeElementType> >
On 2014/12/18 06:36:53, JF wrote:
> >>

Done.

https://codereview.chromium.org/802183004/diff/20001/src/assembler.h
File src/assembler.h (right):

https://codereview.chromium.org/802183004/diff/20001/src/assembler.h#newcode233
src/assembler.h:233: ArenaAllocator Allocator;
On 2014/12/18 18:39:59, jvoung wrote:
> I wonder if the assembler should just use the CFG allocator. Its allocation
> should happen after the other CFG allocations. There are tiny relocation
> objects, and label objects that get allocated. Then there is the contiguous
> AssemblerBuffer chunks that represent the function's .text section, that get
> allocated/grow.
> 
> 
> Anyway, that can be tuned later.

I think the assembler should use its own allocator for the machine code bytes
and the fixups.  This is because we probably want a separate thread to serialize
the assembly across all functions into the ELF file.  The translator threads
would add the assembly buffers to a work queue, destroy the Cfg, and grab a new
function to translate.

I added a new ALLOCATION.rst file to try to document these assumptions.

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

This is pretty much lgtm after some documentation polishing. Gotta make sure
that shed is shiny.

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst
File ALLOCATION.rst (right):

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst#newcode1
ALLOCATION.rst:1: Object allocation and lifetime in ICE
You'll need to link to this document from another rst document, assuming `make
documentation` does anything!

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst#newcode10
ALLOCATION.rst:10: A single thread is responsible for parsing PNaCl bitcode and
constructing the
I'd mention that parsing overlaps download.

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst#newcode13
ALLOCATION.rst:13: moves on to parse the next function.
I'd call it a queue, since's it's pretty much FIFO (ignoring randomization).
Same thing later in this document.

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst#newcode25
ALLOCATION.rst:25: translation thread, and assembler buffers are created by the
translation thread
In the middle: new IR nodes are created in a Cfg by the workers.

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst#newcode49
ALLOCATION.rst:49: straightforward since only one Cfg is active at a time.
Only one Cfg is active at a time in a given thread (either the parser thread, or
one of the workers).

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst#newcode54
ALLOCATION.rst:54: completes, but possibly before the assembly buffer is written
to the ELF file.
Ownership of the assembly buffers is transfered to the thread responsible for
ELF file writing.

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst#newcode78
ALLOCATION.rst:78: with it.
Mention tsan testing in a new section.

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

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst
File ALLOCATION.rst (right):

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst#newcode1
ALLOCATION.rst:1: Object allocation and lifetime in ICE
On 2014/12/19 05:34:41, JF wrote:
> You'll need to link to this document from another rst document, assuming `make
> documentation` does anything!

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

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst#newcode10
ALLOCATION.rst:10: A single thread is responsible for parsing PNaCl bitcode and
constructing the
On 2014/12/19 05:34:41, JF wrote:
> I'd mention that parsing overlaps download.

Done.

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst#newcode13
ALLOCATION.rst:13: moves on to parse the next function.
On 2014/12/19 05:34:41, JF wrote:
> I'd call it a queue, since's it's pretty much FIFO (ignoring randomization).
> Same thing later in this document.

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.

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst#newcode25
ALLOCATION.rst:25: translation thread, and assembler buffers are created by the
translation thread
On 2014/12/19 05:34:41, JF wrote:
> In the middle: new IR nodes are created in a Cfg by the workers.

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

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst#newcode49
ALLOCATION.rst:49: straightforward since only one Cfg is active at a time.
On 2014/12/19 05:34:41, JF wrote:
> Only one Cfg is active at a time in a given thread (either the parser thread,
or
> one of the workers).

Done.

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst#newcode54
ALLOCATION.rst:54: completes, but possibly before the assembly buffer is written
to the ELF file.
On 2014/12/19 05:34:41, JF wrote:
> Ownership of the assembly buffers is transfered to the thread responsible for
> ELF file writing.

Done.

https://codereview.chromium.org/802183004/diff/40001/ALLOCATION.rst#newcode78
ALLOCATION.rst:78: with it.
On 2014/12/19 05:34:41, JF wrote:
> Mention tsan testing in a new section.

Done.

[jvoung (off chromium), 2014-12-19 17:42:23]

LGTM

https://codereview.chromium.org/802183004/diff/60001/ALLOCATION.rst
File ALLOCATION.rst (right):

https://codereview.chromium.org/802183004/diff/60001/ALLOCATION.rst#newcode57
ALLOCATION.rst:57: lookup up by translation threads and the parser thread,
access to the constant
"lookup up by" -> "looked up by" ?

https://codereview.chromium.org/802183004/diff/60001/ALLOCATION.rst#newcode102
ALLOCATION.rst:102: there is a slab allocator for the assembler buffer, a
pointer to it can also be
re: "If there is a slab allocator for the assembler buffer...", there is a slab
allocator for the assembler buffer? I guess currently a pointer to it isn't
installed in TLS, but can be if needed. Then that would need the same care when
transferring ownership between one of the translation threads and the writer
thread.

[Jim Stichnoth, 2014-12-19 20:51:25]

https://codereview.chromium.org/802183004/diff/60001/ALLOCATION.rst
File ALLOCATION.rst (right):

https://codereview.chromium.org/802183004/diff/60001/ALLOCATION.rst#newcode57
ALLOCATION.rst:57: lookup up by translation threads and the parser thread,
access to the constant
On 2014/12/19 17:42:23, jvoung wrote:
> "lookup up by" -> "looked up by" ?

Done.

https://codereview.chromium.org/802183004/diff/60001/ALLOCATION.rst#newcode102
ALLOCATION.rst:102: there is a slab allocator for the assembler buffer, a
pointer to it can also be
On 2014/12/19 17:42:23, jvoung wrote:
> re: "If there is a slab allocator for the assembler buffer...", there is a
slab
> allocator for the assembler buffer? I guess currently a pointer to it isn't
> installed in TLS, but can be if needed. Then that would need the same care
when
> transferring ownership between one of the translation threads and the writer
> thread.

Right, I think that's where we'll need to go when we rearrange things to
implement parallel translation.

[Jim Stichnoth, 2014-12-19 20:51:50]

Committed patchset #5 (id:80001) manually as
31c955905a2d861a944f1e0ca60cd9e4c6f1b37d (presubmit successful).