[wasm] Implement parallel compilation.

[wasm] Implement parallel compilation.

With this CL it is possible to compile a wasm module with multiple
threads in parallel. Parallel compilation works as follows:

1)   The main thread allocates a compilation unit for each wasm function.
2)   The main thread spawns WasmCompilationTasks which run on the
     background threads.
3.a) The background threads and the main thread pick one compilation unit
     at a time and execute the parallel phase of the compilation unit.
     After finishing the execution of the parallel phase, the compilation
     unit is stored in a result queue.
3.b) If the result queue contains a compilation unit, the main thread
     dequeues it and finishes its compilation.
4)   After the execution of the parallel phase of all compilation units has
     started, the main thread waits for all WasmCompilationTasks to finish.
5)   The main thread finalizes the compilation of the module.

I'm going to add some additional tests before committing this CL.

R=titzer@chromium.org, bmeurer@chromium.org, mlippautz@chromium.org, mstarzinger@chromium.org

Committed: https://crrev.com/17215438659d8ff2d7d55f95226bf8a1477ccd79
Cr-Commit-Position: refs/heads/master@{#36178}

Committed: https://crrev.com/4aec7ba1aa34e6b45618e0672ed1c2a0026e5b04
Cr-Commit-Position: refs/heads/master@{#36207}

[ahaas, 2016-05-09 16:13:57]

On 2016/05/09 at 13:56:58, ahaas wrote:
> 

I added some tests now.

[Michael Lippautz, 2016-05-10 07:36:41]

Only non-wasm specific comments on the parallelization effort.

https://codereview.chromium.org/1961973002/diff/20001/src/wasm/wasm-module.cc
File src/wasm/wasm-module.cc (right):

https://codereview.chromium.org/1961973002/diff/20001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:415:
static_cast<size_t>(base::NoBarrier_AtomicIncrement(next_unit, 1)) - 1;
nit: Don't know if you require the use of a 32bit atomic. If not, you could use
AtomicNumber<size_t> in atomic-utils.h and avoid the casting dance.

https://codereview.chromium.org/1961973002/diff/20001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:622: base::Semaphore pending_tasks(0);
base:Semaphore and friends do not make sure the internal native handle is
properly aligned. We only have checks that crash if the semaphore is not
aligned. Since we cannot guarantee what the stack looks like we usually those
primitives on the heap.

(You can still allocate on the stack but should be prepared for breakage at any
time on any bot.)

https://codereview.chromium.org/1961973002/diff/20001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:636: bool done = false;
nit: Wouldn't it make more sense to clearly separate the phases, i.e., not have
parallel execution on main thread (3a) intertwined with waiting (4) and
sequential fixup (3b)?

(e.g. PageParallelJob)

[Michael Starzinger, 2016-05-10 09:06:47]

I am only reviewing the changes to wasm-compiler.cc, please let me know if I
should look at other pieces too.

https://codereview.chromium.org/1961973002/diff/20001/src/compiler/wasm-compi...
File src/compiler/wasm-compiler.cc (right):

https://codereview.chromium.org/1961973002/diff/20001/src/compiler/wasm-compi...
src/compiler/wasm-compiler.cc:1885:
Handle<HeapObject>::cast(module_->GetFunctionCode(index))));
nit: Why is this up-cast necessary? Isn't GetFunctionCode returning a
Handle<Code> already. Same comment applies throughout the file.

[ahaas, 2016-05-10 09:45:49]

https://codereview.chromium.org/1961973002/diff/20001/src/compiler/wasm-compi...
File src/compiler/wasm-compiler.cc (right):

https://codereview.chromium.org/1961973002/diff/20001/src/compiler/wasm-compi...
src/compiler/wasm-compiler.cc:1885:
Handle<HeapObject>::cast(module_->GetFunctionCode(index))));
On 2016/05/10 at 09:06:46, Michael Starzinger wrote:
> nit: Why is this up-cast necessary? Isn't GetFunctionCode returning a
Handle<Code> already. Same comment applies throughout the file.

I removed the up-casts. Thanks

https://codereview.chromium.org/1961973002/diff/20001/src/wasm/wasm-module.cc
File src/wasm/wasm-module.cc (right):

https://codereview.chromium.org/1961973002/diff/20001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:415:
static_cast<size_t>(base::NoBarrier_AtomicIncrement(next_unit, 1)) - 1;
On 2016/05/10 at 07:36:41, Michael Lippautz wrote:
> nit: Don't know if you require the use of a 32bit atomic. If not, you could
use AtomicNumber<size_t> in atomic-utils.h and avoid the casting dance.

Done, thanks.

https://codereview.chromium.org/1961973002/diff/20001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:622: base::Semaphore pending_tasks(0);
On 2016/05/10 at 07:36:41, Michael Lippautz wrote:
> base:Semaphore and friends do not make sure the internal native handle is
properly aligned. We only have checks that crash if the semaphore is not
aligned. Since we cannot guarantee what the stack looks like we usually those
primitives on the heap.
> 
> (You can still allocate on the stack but should be prepared for breakage at
any time on any bot.)

Done. I allocate the Semaphore on the heap now.

https://codereview.chromium.org/1961973002/diff/20001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:636: bool done = false;
On 2016/05/10 at 07:36:41, Michael Lippautz wrote:
> nit: Wouldn't it make more sense to clearly separate the phases, i.e., not
have parallel execution on main thread (3a) intertwined with waiting (4) and
sequential fixup (3b)?
> 
> (e.g. PageParallelJob)

I don't see a way to clearly separate these phases for the following reasons:
* We cannot wait with the sequential fixup (3b) until after the parallel
execution has finished because we would run out of memory.
* The fixup has to done after the waiting because otherwise I would miss the
last functions.
* I want the main thread to participate in the parallel execution to guarantee
progress.

I will add a comment.

[Michael Starzinger, 2016-05-10 10:29:59]

LGTM on wasm-compiler. Didn't look at the rest at all.

https://codereview.chromium.org/1961973002/diff/40001/src/compiler/wasm-compi...
File src/compiler/wasm-compiler.cc (right):

https://codereview.chromium.org/1961973002/diff/40001/src/compiler/wasm-compi...
src/compiler/wasm-compiler.cc:2946: jsgraph_(new (graph_zone()) JSGraph(
Comment just for posterity (not actionable): IMHO the wasm-compiler shouldn't
use the JSGraph class. It doesn't need a JSOperatorBuilder or a
SimplifiedOperatorBuilder. In the long run we might consider switching
wasm-compiler to use the underlying Graph class directly (or alternatively a
dedicated container).

[Michael Lippautz, 2016-05-10 10:35:51]

https://codereview.chromium.org/1961973002/diff/20001/src/wasm/wasm-module.cc
File src/wasm/wasm-module.cc (right):

https://codereview.chromium.org/1961973002/diff/20001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:636: bool done = false;
On 2016/05/10 09:45:48, ahaas wrote:
> I don't see a way to clearly separate these phases for the following reasons:
> * We cannot wait with the sequential fixup (3b) until after the parallel
> execution has finished because we would run out of memory.

Alright, then memory consumption is the reason to have have those phases
intertwined :)

> * The fixup has to done after the waiting because otherwise I would miss the
> last functions.
> * I want the main thread to participate in the parallel execution to guarantee
> progress.

You can make progress on the main thread during parallel execution and still
separate the phases. That's what we do for the GC.

[titzer, 2016-05-10 12:32:11]

https://codereview.chromium.org/1961973002/diff/40001/src/compiler/wasm-compi...
File src/compiler/wasm-compiler.cc (right):

https://codereview.chromium.org/1961973002/diff/40001/src/compiler/wasm-compi...
src/compiler/wasm-compiler.cc:1884: args[0] = graph()->NewNode(
Can you extract a helper function for this sequence?

https://codereview.chromium.org/1961973002/diff/40001/src/wasm/wasm-module.cc
File src/wasm/wasm-module.cc (right):

https://codereview.chromium.org/1961973002/diff/40001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:404: bool FetchAndExecuteCompilation(
Put this into an anonymous namespace.

https://codereview.chromium.org/1961973002/diff/40001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:575: //    and stores them in the vector
compilation_units.
We've adopted the {} style for comments, so
s/compilation_units/{compilation_units}/g, here and elsewhere.

https://codereview.chromium.org/1961973002/diff/40001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:593: if (FLAG_wasm_num_compilation_tasks != 0) {
This function is getting huge. Can you split out the numbered steps, each into
their own function? Then it will read really nice :-)

https://codereview.chromium.org/1961973002/diff/40001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:594: CanonicalHandleScope canonical(isolate);
Comment on why we need a canonical handle scope here.

https://codereview.chromium.org/1961973002/diff/40001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:685: // First pass: compile each function and initialize
the code table.
This comment is now out of date.

https://codereview.chromium.org/1961973002/diff/40001/test/mjsunit/wasm/wasm-...
File test/mjsunit/wasm/wasm-module-builder.js (right):

https://codereview.chromium.org/1961973002/diff/40001/test/mjsunit/wasm/wasm-...
test/mjsunit/wasm/wasm-module-builder.js:346: function assertModule(module,
memsize) {
These are assertion (testing) functions, so they don't really belong with the
builder. It'd be better to either factor them out to another common file or just
duplicate them in the new test.

[ahaas, 2016-05-11 09:52:22]

https://codereview.chromium.org/1961973002/diff/40001/src/compiler/wasm-compi...
File src/compiler/wasm-compiler.cc (right):

https://codereview.chromium.org/1961973002/diff/40001/src/compiler/wasm-compi...
src/compiler/wasm-compiler.cc:1884: args[0] = graph()->NewNode(
On 2016/05/10 at 12:32:10, titzer wrote:
> Can you extract a helper function for this sequence?

Done. PTAL

https://codereview.chromium.org/1961973002/diff/40001/src/compiler/wasm-compi...
src/compiler/wasm-compiler.cc:2946: jsgraph_(new (graph_zone()) JSGraph(
On 2016/05/10 at 10:29:59, Michael Starzinger wrote:
> Comment just for posterity (not actionable): IMHO the wasm-compiler shouldn't
use the JSGraph class. It doesn't need a JSOperatorBuilder or a
SimplifiedOperatorBuilder. In the long run we might consider switching
wasm-compiler to use the underlying Graph class directly (or alternatively a
dedicated container).

I plan to remove the JSGraph in a separate CL.

https://codereview.chromium.org/1961973002/diff/40001/src/wasm/wasm-module.cc
File src/wasm/wasm-module.cc (right):

https://codereview.chromium.org/1961973002/diff/40001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:404: bool FetchAndExecuteCompilation(
On 2016/05/10 at 12:32:10, titzer wrote:
> Put this into an anonymous namespace.

done.

https://codereview.chromium.org/1961973002/diff/40001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:575: //    and stores them in the vector
compilation_units.
On 2016/05/10 at 12:32:10, titzer wrote:
> We've adopted the {} style for comments, so
s/compilation_units/{compilation_units}/g, here and elsewhere.

done.

https://codereview.chromium.org/1961973002/diff/40001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:593: if (FLAG_wasm_num_compilation_tasks != 0) {
On 2016/05/10 at 12:32:10, titzer wrote:
> This function is getting huge. Can you split out the numbered steps, each into
their own function? Then it will read really nice :-)

Done.

https://codereview.chromium.org/1961973002/diff/40001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:594: CanonicalHandleScope canonical(isolate);
On 2016/05/10 at 12:32:10, titzer wrote:
> Comment on why we need a canonical handle scope here.

Done.

https://codereview.chromium.org/1961973002/diff/40001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:685: // First pass: compile each function and initialize
the code table.
On 2016/05/10 at 12:32:10, titzer wrote:
> This comment is now out of date.

Done.

https://codereview.chromium.org/1961973002/diff/40001/test/mjsunit/wasm/wasm-...
File test/mjsunit/wasm/wasm-module-builder.js (right):

https://codereview.chromium.org/1961973002/diff/40001/test/mjsunit/wasm/wasm-...
test/mjsunit/wasm/wasm-module-builder.js:346: function assertModule(module,
memsize) {
On 2016/05/10 at 12:32:11, titzer wrote:
> These are assertion (testing) functions, so they don't really belong with the
builder. It'd be better to either factor them out to another common file or just
duplicate them in the new test.

I duplicated the code now.

[titzer, 2016-05-11 12:38:50]

lgtm

https://codereview.chromium.org/1961973002/diff/80001/src/wasm/wasm-module.cc
File src/wasm/wasm-module.cc (right):

https://codereview.chromium.org/1961973002/diff/80001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:546: for (size_t i = 0; i < num_tasks; i++) {
Please add a comment here as per in-person discussion about why the main thread
is trying to abort the compilation tasks.

https://codereview.chromium.org/1961973002/diff/80001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:557: // 3.b) If executed_units contains a compilation
unit, the main thread
Move this comment into the caller?

[ahaas, 2016-05-11 13:43:08]

https://codereview.chromium.org/1961973002/diff/80001/src/wasm/wasm-module.cc
File src/wasm/wasm-module.cc (right):

https://codereview.chromium.org/1961973002/diff/80001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:546: for (size_t i = 0; i < num_tasks; i++) {
On 2016/05/11 at 12:38:50, titzer wrote:
> Please add a comment here as per in-person discussion about why the main
thread is trying to abort the compilation tasks.

Done.

https://codereview.chromium.org/1961973002/diff/80001/src/wasm/wasm-module.cc...
src/wasm/wasm-module.cc:557: // 3.b) If executed_units contains a compilation
unit, the main thread
On 2016/05/11 at 12:38:50, titzer wrote:
> Move this comment into the caller?

Done.

[ahaas, 2016-05-11 13:43:10]

The CQ bit was checked by ahaas@chromium.org

[ahaas, 2016-05-11 13:43:10]

The patchset sent to the CQ was uploaded after l-g-t-m from
mstarzinger@chromium.org, titzer@chromium.org
Link to the patchset: https://codereview.chromium.org/1961973002/#ps100001
(title: " ")

[commit-bot: I haz the power, 2016-05-11 13:43:20]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1961973002/100001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1961973002/100001

[commit-bot: I haz the power, 2016-05-11 14:07:02]

Committed patchset #6 (id:100001)

[commit-bot: I haz the power, 2016-05-11 14:09:02]

Description was changed from

==========
[wasm] Implement parallel compilation.

With this CL it is possible to compile a wasm module with multiple
threads in parallel. Parallel compilation works as follows:

1)   The main thread allocates a compilation unit for each wasm function.
2)   The main thread spawns WasmCompilationTasks which run on the
     background threads.
3.a) The background threads and the main thread pick one compilation unit
     at a time and execute the parallel phase of the compilation unit.
     After finishing the execution of the parallel phase, the compilation
     unit is stored in a result queue.
3.b) If the result queue contains a compilation unit, the main thread
     dequeues it and finishes its compilation.
4)   After the execution of the parallel phase of all compilation units has
     started, the main thread waits for all WasmCompilationTasks to finish.
5)   The main thread finalizes the compilation of the module.

I'm going to add some additional tests before committing this CL.

R=titzer@chromium.org, bmeurer@chromium.org, mlippautz@chromium.org,
mstarzinger@chromium.org
==========

to

==========
[wasm] Implement parallel compilation.

With this CL it is possible to compile a wasm module with multiple
threads in parallel. Parallel compilation works as follows:

1)   The main thread allocates a compilation unit for each wasm function.
2)   The main thread spawns WasmCompilationTasks which run on the
     background threads.
3.a) The background threads and the main thread pick one compilation unit
     at a time and execute the parallel phase of the compilation unit.
     After finishing the execution of the parallel phase, the compilation
     unit is stored in a result queue.
3.b) If the result queue contains a compilation unit, the main thread
     dequeues it and finishes its compilation.
4)   After the execution of the parallel phase of all compilation units has
     started, the main thread waits for all WasmCompilationTasks to finish.
5)   The main thread finalizes the compilation of the module.

I'm going to add some additional tests before committing this CL.

R=titzer@chromium.org, bmeurer@chromium.org, mlippautz@chromium.org,
mstarzinger@chromium.org

Committed: https://crrev.com/17215438659d8ff2d7d55f95226bf8a1477ccd79
Cr-Commit-Position: refs/heads/master@{#36178}
==========

[commit-bot: I haz the power, 2016-05-11 14:09:03]

Patchset 6 (id:??) landed as
https://crrev.com/17215438659d8ff2d7d55f95226bf8a1477ccd79
Cr-Commit-Position: refs/heads/master@{#36178}

[ahaas, 2016-05-11 15:57:54]

A revert of this CL (patchset #6 id:100001) has been created in
https://codereview.chromium.org/1965243003/ by ahaas@chromium.org.

The reason for reverting is: The ThreadSanitizer finds data races..

[ahaas, 2016-05-12 08:26:53]

On 2016/05/11 at 15:57:54, ahaas wrote:
> A revert of this CL (patchset #6 id:100001) has been created in
https://codereview.chromium.org/1965243003/ by ahaas@chromium.org.
> 
> The reason for reverting is: The ThreadSanitizer finds data races..

I fixed some data races now:
* I added a LazyInstance wrapper around the SigTable in wasm-opcodes.cc.
* I removed the histogram counters in wasm-compiler.cc for now.
* I do the emptiness check of {executed_units} in FinishCompilationUnits inside
the lock now.

PTAL

[titzer, 2016-05-12 08:41:35]

lgtm

[ahaas, 2016-05-12 11:56:47]

The CQ bit was checked by ahaas@chromium.org

[ahaas, 2016-05-12 11:56:47]

The patchset sent to the CQ was uploaded after l-g-t-m from
mstarzinger@chromium.org
Link to the patchset: https://codereview.chromium.org/1961973002/#ps120001
(title: "Make the implementation thread-safe.")

[commit-bot: I haz the power, 2016-05-12 11:56:57]

CQ is trying da patch. Follow status at
 https://chromium-cq-status.appspot.com/patch-status/1961973002/120001
View timeline at
 https://chromium-cq-status.appspot.com/patch-timeline/1961973002/120001

[commit-bot: I haz the power, 2016-05-12 11:58:33]

Committed patchset #7 (id:120001)

[commit-bot: I haz the power, 2016-05-12 11:58:56]

Description was changed from

==========
[wasm] Implement parallel compilation.

With this CL it is possible to compile a wasm module with multiple
threads in parallel. Parallel compilation works as follows:

1)   The main thread allocates a compilation unit for each wasm function.
2)   The main thread spawns WasmCompilationTasks which run on the
     background threads.
3.a) The background threads and the main thread pick one compilation unit
     at a time and execute the parallel phase of the compilation unit.
     After finishing the execution of the parallel phase, the compilation
     unit is stored in a result queue.
3.b) If the result queue contains a compilation unit, the main thread
     dequeues it and finishes its compilation.
4)   After the execution of the parallel phase of all compilation units has
     started, the main thread waits for all WasmCompilationTasks to finish.
5)   The main thread finalizes the compilation of the module.

I'm going to add some additional tests before committing this CL.

R=titzer@chromium.org, bmeurer@chromium.org, mlippautz@chromium.org,
mstarzinger@chromium.org

Committed: https://crrev.com/17215438659d8ff2d7d55f95226bf8a1477ccd79
Cr-Commit-Position: refs/heads/master@{#36178}
==========

to

==========
[wasm] Implement parallel compilation.

With this CL it is possible to compile a wasm module with multiple
threads in parallel. Parallel compilation works as follows:

1)   The main thread allocates a compilation unit for each wasm function.
2)   The main thread spawns WasmCompilationTasks which run on the
     background threads.
3.a) The background threads and the main thread pick one compilation unit
     at a time and execute the parallel phase of the compilation unit.
     After finishing the execution of the parallel phase, the compilation
     unit is stored in a result queue.
3.b) If the result queue contains a compilation unit, the main thread
     dequeues it and finishes its compilation.
4)   After the execution of the parallel phase of all compilation units has
     started, the main thread waits for all WasmCompilationTasks to finish.
5)   The main thread finalizes the compilation of the module.

I'm going to add some additional tests before committing this CL.

R=titzer@chromium.org, bmeurer@chromium.org, mlippautz@chromium.org,
mstarzinger@chromium.org

Committed: https://crrev.com/17215438659d8ff2d7d55f95226bf8a1477ccd79
Cr-Commit-Position: refs/heads/master@{#36178}

Committed: https://crrev.com/4aec7ba1aa34e6b45618e0672ed1c2a0026e5b04
Cr-Commit-Position: refs/heads/master@{#36207}
==========

[commit-bot: I haz the power, 2016-05-12 11:58:57]

Patchset 7 (id:??) landed as
https://crrev.com/4aec7ba1aa34e6b45618e0672ed1c2a0026e5b04
Cr-Commit-Position: refs/heads/master@{#36207}