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..e473e988e98184e72367119dc2f4c29176eb1042
--- /dev/null
+++ b/tools/pnacl-llc/ThreadedFunctionQueue.h
@@ -0,0 +1,86 @@
+//===- 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),
+        NumFunctions(0),
+        CurrentFunction(0) {
+    // This 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.
+    NumFunctions = mod->getFunctionList().size();
+  }
+  ~ThreadedFunctionQueue() {}
+
+  // Assign functions in a static manner between threads.
+  bool GrabFunctionStatic(unsigned FuncIndex, unsigned ThreadIndex) const {
+    return FuncIndex % SplitModuleCount == ThreadIndex;
+  }
+
+  // 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);
+  }
+
+  // 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() {

[Jim Stichnoth, 2014/03/18 20:49:49]

declare as const

[jvoung (off chromium), 2014/03/18 22:01:17]

Done.

+    // 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);
+    unsigned DynamicChunkSize = ApproxRemainingFuncs / (SplitModuleCount * 4);
+    if (DynamicChunkSize > 8U)
+      return 8U;
+    else
+      return std::max(1U, DynamicChunkSize);
+  }
+
+ private:
+  unsigned SplitModuleCount;

[Jim Stichnoth, 2014/03/18 20:49:49]

Make SplitModuleCount and NumFunctions const?

[jvoung (off chromium), 2014/03/18 22:01:17]

Done.

+  unsigned NumFunctions;
+  volatile unsigned CurrentFunction;
+};
+
+#endif