Add self-scheduling to threaded translation (vs static)

tools/pnacl-llc/ThreadedFunctionQueue.h

Index: tools/pnacl-llc/ThreadedFunctionQueue.h
diff --git a/tools/pnacl-llc/ThreadedFunctionQueue.h b/tools/pnacl-llc/ThreadedFunctionQueue.h
new file mode 100644
index 0000000000000000000000000000000000000000..54a0e8a378fc6ee58eecb35b5de1e81d307cd3cb
--- /dev/null
+++ b/tools/pnacl-llc/ThreadedFunctionQueue.h
@@ -0,0 +1,89 @@
+//===- ThreadedFunctionQueue.h - Function work units for threads -*- C++ -*-==//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef THREADEDFUNCTIONQUEUE_H
+#define THREADEDFUNCTIONQUEUE_H
+
+#include "llvm/IR/Module.h"
+
+// A "queue" that keeps track of which functions have been assigned to
+// threads and which functions have not yet been assigned. It does not
+// actually use a queue data structure and instead uses a number which
+// tracks the minimum unassigned function ID, expecting each thread
+// to have the same view of function IDs.
+class ThreadedFunctionQueue {
+ public:
+  ThreadedFunctionQueue(Module *mod, unsigned SplitModuleCount)
+      : SplitModuleCount(SplitModuleCount),

[JF, 2014/03/19 04:47:05]

Silly corner case, but checking that SplitModuleCount isn't 0 seems like a good
idea.

[jvoung (off chromium), 2014/03/19 18:44:37]

Done.

+        NumFunctions(mod->getFunctionList().size()),
+        CurrentFunction(0) {
+    // NOTE: NumFunctions is only the approximate number of functions.
+    // Some additional declarations will be added by other passes:
+    // AddPNaClExternalDeclsPass (for setjmp/longjmp and nacl variants),
+    // and the NaCl Atomics pass adds declarations of NaCl atomic intrinsics.
+  }
+  ~ThreadedFunctionQueue() {}
+
+  // Assign functions in a static manner between threads.
+  bool GrabFunctionStatic(unsigned FuncIndex, unsigned ThreadIndex) const {
+    return FuncIndex % SplitModuleCount == ThreadIndex;

[JF, 2014/03/19 04:47:05]

IIUC this won't work if SplitModuleCount < ThreadIndex? Say you have 16 threads
and you statically split modules 8 ways, then each function will get translated
twice?

[jvoung (off chromium), 2014/03/19 18:44:37]

It's pretty unlikely SplitModuleCount < ThreadIndex, or if it is we would have a
different parallelization strategy.

That would mean it's safe to share the same module between threads. If that was
true, then we would just share the single global module between every thread
instead of having the overhead of cloning global variables and memcpy'ing
bitcode stream bytes for the different modules.


However, this probably won't work with SplitModuleCount > # Threads either. It
would leave some functions out because there wouldn't be any threads to work on
some of the modules. In order to support that, the module sharding would need to
be organized a bit differently. E.g., some modules would take functions [0,
NumFuncs/N), some would take [NumFuncs/N, 2 * NumFuncs/N), ... Then those module
sets would be sharded further between the threads, e.g., with this modulo style
of sharding.

Overall, I think this class is only concerned about sharding things between # of
threads, and the range of functions. For now, the range of functions is [0,
NumFuncs). Perhaps SplitModuleCount should be renamed to NumThreads to be more
accurate then.

If we ever change the sharding so that SplitModuleCount != NumThreads, then we
only need to change the function range assumption away from [0, NumFuncs). The
linker will also complain loudly when we make such changes to the assumptions
without having fixed up each part.

[JF, 2014/03/19 20:26:08]

It would be useful to assert on this value then, with a comment explaining this
tradeoff.

[jvoung (off chromium), 2014/03/19 21:45:17]

Done.

+  }
+
+  // Assign functions between threads dynamically.
+  // Returns true if FuncIndex is unassigned and the calling thread
+  // is assigned functions [FuncIndex, FuncIndex + ChunkSize).
+  // Returns false if the calling thread is not assigned functions
+  // [FuncIndex, FuncIndex + ChunkSize).
+  //
+  // NextIndex will be set to the next unassigned function ID, so that
+  // the calling thread will know which function ID to attempt to grab
+  // next. Each thread may have a different value for the ideal ChunkSize
+  // so it is hard to predict the next available function solely based
+  // on incrementing by ChunkSize.
+  bool GrabFunctionDynamic(unsigned FuncIndex, unsigned ChunkSize,
+                           unsigned &NextIndex) {
+    unsigned Cur = CurrentFunction;
+    if (FuncIndex < Cur) {
+      NextIndex = Cur;
+      return false;
+    }
+    NextIndex = Cur + ChunkSize;
+    return __sync_bool_compare_and_swap(&CurrentFunction, Cur, NextIndex);

[JF, 2014/03/19 04:47:05]

The failure case here doesn't actually set NextIndex at the right location: say
ChunkSize was 8 for this thread and 4 for another, the other thread consumes
first, then this thread will fail consuming, but its NextIndex will be advanced
by 8 instead of 4.

[jvoung (off chromium), 2014/03/19 18:44:37]

Good catch -- I'll see if the cmpxchange succeeded or not. If it failed then
re-read CurrentFunction into NextIndex.

Otherwise, perhaps just using a mutex would have been more clean. The perf is
actually about the same w/ a mutex vs cmpxchange (at least on my linux x86
workstation)...

[JF, 2014/03/19 20:26:08]

That works, but it's cleaner to just use:
if (Cur == (Index = __sync_compare_and_swap)) {
  return true;
}
NextIndex = Index;
return false;

You remove one contended read in that case.

[jvoung (off chromium), 2014/03/19 21:45:17]

Done.

+  }
+
+  // Returns a recommended ChunkSize for use in calling GrabFunctionDynamic().
+  // ChunkSize starts out "large" to reduce synchronization cost. However,
+  // it cannot be too large, otherwise it will encompass too many bytes
+  // and defeats streaming translation. Assigning too many functions to
+  // a single thread also throws off load balancing, so the ChunkSize is
+  // reduced when the remaining number of functions is low so that
+  // load balancing can be achieved near the end.
+  unsigned RecommendedChunkSize() const {
+    // Since NumFunctions may be less than the actual number of functions
+    // (see note in ctor), clamp remaining functions to 1.
+    unsigned ApproxRemainingFuncs =
+        std::max((int)(NumFunctions - CurrentFunction), 1);

[JF, 2014/03/19 04:47:05]

Converting an unsigned that's not representable as signed is undefined behavior.
I'd just have everything be signed from the start :-)

[jvoung (off chromium), 2014/03/19 18:44:37]

Note that NumFunctions was unsigned to begin with because .size() returns a
size_t (unsigned). So if I make it signed, then I'd have to add a check that
size() returns something within range. Once I do that check in the ctor, I guess
I wouldn't need to do any checks after though.

+    unsigned DynamicChunkSize = ApproxRemainingFuncs / (SplitModuleCount * 4);
+    if (DynamicChunkSize > 8U)
+      return 8U;
+    else
+      return std::max(1U, DynamicChunkSize);

[JF, 2014/03/19 04:47:05]

return max(1, min(8, DynamicChunkSize));

[jvoung (off chromium), 2014/03/19 18:44:37]

Done.

+  }
+
+ private:
+  const unsigned SplitModuleCount;
+  const unsigned NumFunctions;
+  volatile unsigned CurrentFunction;
+
+  ThreadedFunctionQueue(
+      const ThreadedFunctionQueue&) LLVM_DELETED_FUNCTION;
+  void operator=(const ThreadedFunctionQueue&) LLVM_DELETED_FUNCTION;

[JF, 2014/03/19 04:47:05]

Not that it matters since it's deleted, but operator= usually returns T&.

[jvoung (off chromium), 2014/03/19 18:44:37]

LLVM's style is to have void, e.g.,

include/llvm/IR/Instruction.h:  void operator=(const Instruction &)
LLVM_DELETED_FUNCTION;

So... I'm just following that style.

+};
+
+#endif