[wasm] Implement parallel compilation.

src/wasm/wasm-module.cc

 // Copyright 2015 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "src/macro-assembler.h"
 #include "src/objects.h"
 #include "src/property-descriptor.h"
 #include "src/v8.h"
 
 #include "src/simulator.h"
@@ skipping 112 matching lines @@
       : isolate_(isolate), placeholder_code_(size), function_code_(size) {}
 
   // Get the code object for a function, allocating a placeholder if it has
   // not yet been compiled.
   Handle<Code> GetFunctionCode(uint32_t index) {
     DCHECK(index < function_code_.size());
     if (function_code_[index].is_null()) {
       // Create a placeholder code object and encode the corresponding index in
       // the {constant_pool_offset} field of the code object.
       // TODO(titzer): placeholder code objects are somewhat dangerous.
-      Handle<Code> self(nullptr, isolate_);
       byte buffer[] = {0, 0, 0, 0, 0, 0, 0, 0};  // fake instructions.
       CodeDesc desc = {buffer, 8, 8, 0, 0, nullptr};
       Handle<Code> code = isolate_->factory()->NewCode(
-          desc, Code::KindField::encode(Code::WASM_FUNCTION), self);
+          desc, Code::KindField::encode(Code::WASM_FUNCTION),
+          Handle<Object>::null());
       code->set_constant_pool_offset(index + kPlaceholderMarker);
       placeholder_code_[index] = code;
       function_code_[index] = code;
     }
     return function_code_[index];
   }
 
   void Finish(uint32_t index, Handle<Code> code) {
     DCHECK(index < function_code_.size());
     function_code_[index] = code;
@@ skipping 243 matching lines @@
   }
 
   if (!function->IsJSFunction()) {
     return ReportFFIError(thrower, "not a function", index, module_name,
                           function_name);
   }
 
   return Handle<JSFunction>::cast(function);
 }
 
+// Fetches the compilation unit of a wasm function and executes its parallel
+// phase.
+bool FetchAndExecuteCompilation(
+    Isolate* isolate,
+    std::vector<compiler::WasmCompilationUnit*>* compilation_units,
+    std::queue<compiler::WasmCompilationUnit*>* executed_units,
+    base::Mutex* result_mutex, base::Atomic32* next_unit) {
+  DisallowHeapAllocation no_allocation;
+  DisallowHandleAllocation no_handles;
+  DisallowHandleDereference no_deref;
+  DisallowCodeDependencyChange no_dependency_change;
+
+  // - 1 because AtomicIntrement returns the value after the atomic increment.
+  size_t index =
+      static_cast<size_t>(base::NoBarrier_AtomicIncrement(next_unit, 1)) - 1;

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

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.

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

Done, thanks.

+  if (index >= compilation_units->size()) {
+    return false;
+  }
+
+  compiler::WasmCompilationUnit* unit = compilation_units->at(index);
+  if (unit != nullptr) {
+    compiler::ExecuteCompilation(unit);
+    {
+      base::LockGuard<base::Mutex> guard(result_mutex);
+      executed_units->push(unit);
+    }
+  }
+  return true;
+}
+
+class WasmCompilationTask : public CancelableTask {
+ public:
+  WasmCompilationTask(
+      Isolate* isolate,
+      std::vector<compiler::WasmCompilationUnit*>* compilation_units,
+      std::queue<compiler::WasmCompilationUnit*>* executed_units,
+      base::Semaphore* on_finished, base::Mutex* result_mutex,
+      base::Atomic32* next_unit)
+      : CancelableTask(isolate),
+        isolate_(isolate),
+        compilation_units_(compilation_units),
+        executed_units_(executed_units),
+        on_finished_(on_finished),
+        result_mutex_(result_mutex),
+        next_unit_(next_unit) {}
+
+  void RunInternal() override {
+    while (FetchAndExecuteCompilation(isolate_, compilation_units_,
+                                      executed_units_, result_mutex_,
+                                      next_unit_)) {
+    }
+    on_finished_->Signal();
+  }
+
+  Isolate* isolate_;
+  std::vector<compiler::WasmCompilationUnit*>* compilation_units_;
+  std::queue<compiler::WasmCompilationUnit*>* executed_units_;
+  base::Semaphore* on_finished_;
+  base::Mutex* result_mutex_;
+  base::Atomic32* next_unit_;
+};
+
 // Instantiates a wasm module as a JSObject.
 //  * allocates a backing store of {mem_size} bytes.
 //  * installs a named property "memory" for that buffer if exported
 //  * installs named properties on the object for exported functions
 //  * compiles wasm code to machine code
 MaybeHandle<JSObject> WasmModule::Instantiate(Isolate* isolate,
                                               Handle<JSReceiver> ffi,
                                               Handle<JSArrayBuffer> memory) {
   HistogramTimerScope wasm_instantiate_module_time_scope(
       isolate->counters()->wasm_instantiate_module_time());
@@ skipping 89 matching lines @@
     }
   }
 
   //-------------------------------------------------------------------------
   // Compile all functions in the module.
   //-------------------------------------------------------------------------
   {
     isolate->counters()->wasm_functions_per_module()->AddSample(
         static_cast<int>(functions.size()));
 
+    //-----------------------------------------------------------------------
+    // For parallel compilation:
+    // 1) The main thread allocates a compilation unit for each wasm function
+    //    and stores them in the vector compilation_units.
+    // 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 result is
+    //      enqueued in executed_units.
+    // 3.b) If executed_units contains a compilation unit, the main thread
+    //      dequeues it and finishes the compilation.
+    // 4) After the parallel phase of all compilation units has started, the
+    //    main thread waits for all WasmCompilationTasks to finish.
+    // 5) The main thread finishes the compilation.
+
     std::vector<compiler::WasmCompilationUnit*> compilation_units(
         functions.size());
     std::queue<compiler::WasmCompilationUnit*> executed_units;
     std::vector<Handle<Code>> results(functions.size());
 
-    if (FLAG_wasm_parallel_compilation) {
+    if (FLAG_wasm_num_compilation_tasks != 0) {
+      CanonicalHandleScope canonical(isolate);
+
       // Create a placeholder code object for all functions.
       // TODO(ahaas): Maybe we could skip this for external functions.
       for (uint32_t i = 0; i < functions.size(); i++) {
         linker.GetFunctionCode(i);
       }
 
+      // 1) The main thread allocates a compilation unit for each wasm function
+      //    and stores them in the vector compilation_units.
       for (uint32_t i = FLAG_skip_compiling_wasm_funcs; i < functions.size();
            i++) {
         if (!functions[i].external) {
           compilation_units[i] = compiler::CreateWasmCompilationUnit(
               &thrower, isolate, &module_env, &functions[i], i);
+        } else {
+          compilation_units[i] = nullptr;
         }
       }
 
+      // 2) The main thread spawns WasmCompilationTasks which run on the
+      //    background threads.
+      const size_t max_num_tasks =
+          Min(static_cast<size_t>(FLAG_wasm_num_compilation_tasks),
+              V8::GetCurrentPlatform()->NumberOfAvailableBackgroundThreads());
+
+      base::SmartArrayPointer<uint32_t> task_ids(new uint32_t[max_num_tasks]);
+
+      base::Semaphore pending_tasks(0);

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

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

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

Done. I allocate the Semaphore on the heap now.

+      base::Mutex result_mutex;
+      base::Atomic32 next_unit = FLAG_skip_compiling_wasm_funcs;
+
+      for (size_t i = 0; i < max_num_tasks; i++) {
+        WasmCompilationTask* task = new WasmCompilationTask(
+            isolate, &compilation_units, &executed_units, &pending_tasks,
+            &result_mutex, &next_unit);
+        task_ids[i] = task->id();
+        V8::GetCurrentPlatform()->CallOnBackgroundThread(
+            task, v8::Platform::kShortRunningTask);
+      }
+
       index = FLAG_skip_compiling_wasm_funcs;
-      while (true) {
+      bool done = false;

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

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)

[ahaas, 2016/05/10 09:45:48]

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 Lippautz, 2016/05/10 10:35:51]

Alright, then memory consumption is the reason to have have those phases
intertwined :)
You can make progress on the main thread during parallel execution and still
separate the phases. That's what we do for the GC.

+      while (!done) {
+        // 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
+        //      result is enqueued in executed_units.
+        if (!FetchAndExecuteCompilation(isolate, &compilation_units,
+                                        &executed_units, &result_mutex,
+                                        &next_unit)) {
+          // 4) After the parallel phase of all compilation units has started,
+          //    the main thread waits for all WasmCompilationTasks to finish.
+          for (size_t i = 0; i < max_num_tasks; i++) {
+            if (!isolate->cancelable_task_manager()->TryAbort(task_ids[i])) {
+              pending_tasks.Wait();
+            }
+          }
+          done = true;
+        }
+        // 3.b) If executed_units contains a compilation unit, the main thread
+        //      dequeues it and finishes the compilation.
         while (!executed_units.empty()) {
-          compiler::WasmCompilationUnit* unit = executed_units.front();
-          executed_units.pop();
-          int i = compiler::GetIndexOfWasmCompilationUnit(unit);
-          results[i] = compiler::FinishCompilation(unit);
-        }
-        if (index < functions.size()) {
-          if (!functions[index].external) {
-            compiler::ExecuteCompilation(compilation_units[index]);
-            executed_units.push(compilation_units[index]);
-            index++;
+          compiler::WasmCompilationUnit* unit = nullptr;
+          {
+            base::LockGuard<base::Mutex> guard(&result_mutex);
+            if (!executed_units.empty()) {
+              unit = executed_units.front();
+              executed_units.pop();
+            }
           }
-        } else {
-          break;
+          if (unit != nullptr) {
+            int j = compiler::GetIndexOfWasmCompilationUnit(unit);
+            if (!functions[j].external) {
+              results[j] = compiler::FinishCompilation(unit);
+            }
+          }
         }
       }
     }
-
+    // 5) The main thread finishes the compilation.
     // First pass: compile each function and initialize the code table.
     for (uint32_t i = FLAG_skip_compiling_wasm_funcs; i < functions.size();
          i++) {
       const WasmFunction& func = functions[i];
       if (thrower.error()) break;
       DCHECK_EQ(i, func.func_index);
 
       WasmName str = GetName(func.name_offset, func.name_length);
       WasmName str_null = {nullptr, 0};
       Handle<String> name = factory->InternalizeUtf8String(str);
       Handle<Code> code = Handle<Code>::null();
       Handle<JSFunction> function = Handle<JSFunction>::null();
       if (func.external) {
         // Lookup external function in FFI object.
         MaybeHandle<JSFunction> function =
             LookupFunction(thrower, factory, ffi, i, str, str_null);
         if (function.is_null()) return MaybeHandle<JSObject>();
         code = compiler::CompileWasmToJSWrapper(isolate, &module_env,
                                                 function.ToHandleChecked(),
                                                 func.sig, str, str_null);
       } else {
-        if (FLAG_wasm_parallel_compilation) {
+        if (FLAG_wasm_num_compilation_tasks != 0) {
           code = results[i];
         } else {
           // Compile the function.
+          CanonicalHandleScope canonical(isolate);
           code = compiler::CompileWasmFunction(&thrower, isolate, &module_env,
                                                &func);
         }
         if (code.is_null()) {
           thrower.Error("Compilation of #%d:%.*s failed.", i, str.length(),
                         str.start());
           return MaybeHandle<JSObject>();
         }
         if (func.exported) {
           function = compiler::CompileJSToWasmWrapper(
@@ skipping 230 matching lines @@
       wasm->GetInternalField(kWasmFunctionNamesArray), wasm->GetIsolate());
   if (func_names_arr_obj->IsUndefined())
     return func_names_arr_obj;  // Return undefined.
   return GetWasmFunctionNameFromTable(
       Handle<ByteArray>::cast(func_names_arr_obj), func_index);
 }
 
 }  // namespace wasm
 }  // namespace internal
 }  // namespace v8