Add self-scheduling to threaded translation (vs static)

tools/pnacl-llc/pnacl-llc.cpp

 //===-- pnacl-llc.cpp - PNaCl-specific llc: pexe ---> nexe  ---------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // pnacl-llc: the core of the PNaCl translator, compiling a pexe into a nexe.
@@ skipping 27 matching lines @@
 #include "llvm/Support/PrettyStackTrace.h"
 #include "llvm/Support/Signals.h"
 #include "llvm/Support/SourceMgr.h"
 #include "llvm/Support/StreamableMemoryObject.h"
 #include "llvm/Support/TargetRegistry.h"
 #include "llvm/Support/TargetSelect.h"
 #include "llvm/Support/ToolOutputFile.h"
 #include "llvm/Target/TargetLibraryInfo.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Transforms/NaCl.h"
+#include "ThreadedFunctionQueue.h"
 #include "ThreadedStreamingCache.h"
 #include <pthread.h>
 #include <memory>
 
-
 using namespace llvm;
 
 // NOTE: When __native_client__ is defined it means pnacl-llc is built as a
 // sandboxed translator (from pnacl-llc.pexe to pnacl-llc.nexe). In this mode
 // it uses SRPC operations instead of direct OS intefaces.
 #if defined(__native_client__)
 int srpc_main(int argc, char **argv);
 int getObjectFileFD(unsigned index);
 DataStreamer *getNaClBitcodeStreamer();
 
@@ skipping 61 matching lines @@
 
 cl::opt<bool>
 DisableSimplifyLibCalls("disable-simplify-libcalls",
                         cl::desc("Disable simplify-libcalls"),
                         cl::init(false));
 
 cl::opt<unsigned>
 SplitModuleCount("split-module",
                  cl::desc("Split PNaCl module"), cl::init(1U));
 
+enum SplitModuleSchedulerKind {
+  SplitModuleDynamic,
+  SplitModuleStatic
+};
+
+cl::opt<SplitModuleSchedulerKind>
+SplitModuleSched(
+    "split-module-sched",
+    cl::desc("Choose thread scheduler for split module compilation."),
+    cl::values(
+        clEnumValN(SplitModuleDynamic, "dynamic",
+                   "Dynamic thread scheduling (default)"),
+        clEnumValN(SplitModuleStatic, "static",
+                   "Static thread scheduling"),
+        clEnumValEnd),
+    cl::init(SplitModuleDynamic));
+
 /// Compile the module provided to pnacl-llc. The file name for reading the
 /// module and other options are taken from globals populated by command-line
 /// option parsing.
 static int compileModule(StringRef ProgramName);
 
 #if !defined(__native_client__)
 // GetFileNameRoot - Helper function to get the basename of a filename.
 static std::string
 GetFileNameRoot(StringRef InputFilename) {
   std::string IFN = InputFilename;
@@ skipping 184 matching lines @@
     // Err.print is prettier, so use it for the non-sandboxed translator.
     Err.print(ProgramName.data(), errs());
     return NULL;
 #endif
   }
   return M;
 }
 
 static int runCompilePasses(Module *mod,
                             unsigned ModuleIndex,
+                            ThreadedFunctionQueue *FuncQueue,
                             const Triple &TheTriple,
                             TargetMachine &Target,
                             StringRef ProgramName,
                             formatted_raw_ostream &FOS){
   // Add declarations for external functions required by PNaCl. The
   // ResolvePNaClIntrinsics function pass running during streaming
   // depends on these declarations being in the module.
   OwningPtr<ModulePass> AddPNaClExternalDeclsPass(
     createAddPNaClExternalDeclsPass());
   AddPNaClExternalDeclsPass->runOnModule(*mod);
@@ skipping 77 matching lines @@
                                  /* DisableVerify */ true)) {
     errs() << ProgramName
     << ": target does not support generation of this file type!\n";
     return 1;
   }
 
   if (LazyBitcode) {
     FunctionPassManager* P = static_cast<FunctionPassManager*>(PM.get());
     P->doInitialization();
     unsigned FuncIndex = 0;
-    for (Module::iterator I = mod->begin(), E = mod->end(); I != E; ++I) {
-      if (FuncIndex++ % SplitModuleCount == ModuleIndex) {
-        P->run(*I);
-        CheckABIVerifyErrors(ABIErrorReporter, "Function " + I->getName());
-        I->Dematerialize();
+    if (SplitModuleSched == SplitModuleStatic) {

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

It would be nicer if this were a switch on SplitModuleSched, since adding a new
scheduling type then wouldn't require changing if/else/else if, and may give a
compiler warning on unhandled enum value.

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

Done.

+      for (Module::iterator I = mod->begin(), E = mod->end(); I != E; ++I) {
+        if (FuncQueue->GrabFunctionStatic(FuncIndex, ModuleIndex)) {
+          P->run(*I);
+          CheckABIVerifyErrors(ABIErrorReporter, "Function " + I->getName());
+          I->Dematerialize();
+        }
+        ++FuncIndex;
+      }
+    } else {
+      unsigned ChunkSize = 0;
+      for (Module::iterator I = mod->begin(), E = mod->end(); I != E; ) {
+        ChunkSize = FuncQueue->RecommendedChunkSize();
+        unsigned NextIndex;
+        bool grabbed = FuncQueue->GrabFunctionDynamic(FuncIndex, ChunkSize,
+                                                      NextIndex);
+        if (grabbed) {
+          while (FuncIndex < NextIndex && I != E) {

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

Can it happen that I == E? Shouldn't we have failed to get that many functions?

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

It happened back when I was experimenting with ChunkSize tapering and did not
necessarily have ChunkSize taper down to 1 near the end. E.g., taper down to 2
instead.

Now that it tapers down to 1, we can assume "I" will hit "E" exactly when
FuncIndex hits NextIndex. If we ever change the tapering, then we'd have to
readjust.

[jvoung (off chromium), 2014/03/20 15:50:31]

Looks like not all threads agree on how many functions and declarations there
should be:

Thread 1 finished at 115
Thread 3 finished at 116
Thread 0 finished at 116
Thread 2 finished at 116

This can happen in small programs if some thread is "lucky" and never sees a
function w/ a function call... when they run the ResolvePNaClIntrinsics.cpp
function pass, they won't end up adding intrinsic declarations to the module
because that only happens when visitCall() is used. Meanwhile other threads will
probably see a function call and add an intrinsic declaration. Adding an
intrinsic declaration adds to the set of things that can be iterated over...

If the threads don't agree on where the end should be, then one of the threads
may be in a position where they call GrabFunctionDynamic() w/ say FuncIndex =
TrueEndForThread - 50, lose the race and are told that NextIndex shall be
TrueEndEndForThread + NumExtraDecls (because TrueEndForThread + NumExtraDecls ==
TrueEndForSomeOtherThread).

Going to add back the check for now.

I think ultimately, our intrinsic resolving passes should add needed
declarations up front early and consistently, so that there isn't this type of
difference. Then we can remove the check for I != E. Also, by adding the decls
early, the NumFunctions used to initialized FuncQueue will be accurate and
include the added decls, instead of being an underapproximation.

+            P->run(*I);
+            CheckABIVerifyErrors(ABIErrorReporter, "Function " + I->getName());
+            I->Dematerialize();
+            ++FuncIndex;
+            ++I;
+          }
+        } else {
+          while (FuncIndex < NextIndex && I != E) {
+            ++FuncIndex;
+            ++I;
+          }
+        }
       }
     }
     P->doFinalization();
   } else {
     static_cast<PassManager*>(PM.get())->run(*mod);
   }
   return 0;
 }
 
 
 static int compileSplitModule(const TargetOptions &Options,
                               const Triple &TheTriple,
                               const Target *TheTarget,
                               const std::string &FeaturesStr,
                               CodeGenOpt::Level OLvl,
                               const StringRef &ProgramName,
                               Module *GlobalModule,
                               StreamingMemoryObject *StreamingObject,
-                              unsigned ModuleIndex) {
+                              unsigned ModuleIndex,
+                              ThreadedFunctionQueue *FuncQueue) {
   std::auto_ptr<TargetMachine>
     target(TheTarget->createTargetMachine(TheTriple.getTriple(),
                                           MCPU, FeaturesStr, Options,
                                           RelocModel, CMModel, OLvl));
   assert(target.get() && "Could not allocate target machine!");
   TargetMachine &Target = *target.get();
   // Override default to generate verbose assembly.
   Target.setAsmVerbosityDefault(true);
   if (RelaxAll) {
     if (FileType != TargetMachine::CGFT_ObjectFile)
@@ skipping 19 matching lines @@
 
   mod->setTargetTriple(Triple::normalize(UserDefinedTriple));
   {
 #if !defined(__native_client__)
       // Figure out where we are going to send the output.
     std::string N(OutputFilename);
     raw_string_ostream OutFileName(N);
     if (ModuleIndex > 0)
       OutFileName << ".module" << ModuleIndex;
     OwningPtr<tool_output_file> Out
-    (GetOutputStream(TheTarget->getName(), TheTriple.getOS(),
-     OutFileName.str()));
+        (GetOutputStream(TheTarget->getName(), TheTriple.getOS(),
+                         OutFileName.str()));
     if (!Out) return 1;
     formatted_raw_ostream FOS(Out->os());
 #else
     raw_fd_ostream ROS(getObjectFileFD(ModuleIndex), true);
     ROS.SetBufferSize(1 << 20);
     formatted_raw_ostream FOS(ROS);
 #endif
-    int ret = runCompilePasses(mod, ModuleIndex, TheTriple, Target, ProgramName,
+    int ret = runCompilePasses(mod, ModuleIndex, FuncQueue,
+                               TheTriple, Target, ProgramName,
                                FOS);
     if (ret)
       return ret;
 #if defined (__native_client__)
     FOS.flush();
     ROS.flush();
 #else
     // Declare success.
     Out->keep();
 #endif // __native_client__
   }
   return 0;
 }
 
 struct ThreadData {
   const TargetOptions *Options;
   const Triple *TheTriple;
   const Target *TheTarget;
   std::string FeaturesStr;
   CodeGenOpt::Level OLvl;
   std::string ProgramName;
   Module *GlobalModule;
   StreamingMemoryObject *StreamingObject;
   unsigned ModuleIndex;
+  ThreadedFunctionQueue *FuncQueue;
 };
 
 
 static void *runCompileThread(void *arg) {
   struct ThreadData *Data = static_cast<ThreadData *>(arg);
   int ret = compileSplitModule(*Data->Options,
                                *Data->TheTriple,
                                Data->TheTarget,
                                Data->FeaturesStr,
                                Data->OLvl,
                                Data->ProgramName,
                                Data->GlobalModule,
                                Data->StreamingObject,
-                               Data->ModuleIndex);
+                               Data->ModuleIndex,
+                               Data->FuncQueue);
   return reinterpret_cast<void *>(static_cast<intptr_t>(ret));
 }
 
 static int compileModule(StringRef ProgramName) {
   // Use a new context instead of the global context for the main module. It must
   // outlive the module object, declared below. We do this because
   // lib/CodeGen/PseudoSourceValue.cpp gets a type from the global context and
   // races with any other use of the context. Rather than doing an invasive
   // plumbing change to fix it, we work around it by using a new context here
   // and leaving PseudoSourceValue as the only user of the global context.
@@ skipping 89 matching lines @@
     return 1;
   case ' ': break;
   case '0': OLvl = CodeGenOpt::None; break;
   case '1': OLvl = CodeGenOpt::Less; break;
   case '2': OLvl = CodeGenOpt::Default; break;
   case '3': OLvl = CodeGenOpt::Aggressive; break;
   }
 
   SmallVector<pthread_t, 4> Pthreads(SplitModuleCount);
   SmallVector<ThreadData, 4> ThreadDatas(SplitModuleCount);
+  ThreadedFunctionQueue FuncQueue(mod.get(), SplitModuleCount);
 
   if (SplitModuleCount == 1) {
+    // No need for dynamic scheduling with one thread.
+    SplitModuleSched = SplitModuleStatic;
     return compileSplitModule(Options, TheTriple, TheTarget, FeaturesStr,
-                              OLvl, ProgramName, mod.get(), NULL, 0);
+                              OLvl, ProgramName, mod.get(), NULL, 0,
+                              &FuncQueue);
   }
 
   for(unsigned ModuleIndex = 0; ModuleIndex < SplitModuleCount; ++ModuleIndex) {
     ThreadDatas[ModuleIndex].Options = &Options;
     ThreadDatas[ModuleIndex].TheTriple = &TheTriple;
     ThreadDatas[ModuleIndex].TheTarget = TheTarget;
     ThreadDatas[ModuleIndex].FeaturesStr = FeaturesStr;
     ThreadDatas[ModuleIndex].OLvl = OLvl;
     ThreadDatas[ModuleIndex].ProgramName = ProgramName.str();
     ThreadDatas[ModuleIndex].GlobalModule = mod.get();
     ThreadDatas[ModuleIndex].StreamingObject = StreamingObject.get();
     ThreadDatas[ModuleIndex].ModuleIndex = ModuleIndex;
+    ThreadDatas[ModuleIndex].FuncQueue = &FuncQueue;
     if (pthread_create(&Pthreads[ModuleIndex], NULL, runCompileThread,
                         &ThreadDatas[ModuleIndex])) {
       report_fatal_error("Failed to create thread");
     }
   }
   for(unsigned ModuleIndex = 0; ModuleIndex < SplitModuleCount; ++ModuleIndex) {
     void *retval;
     if (pthread_join(Pthreads[ModuleIndex], &retval))
       report_fatal_error("Failed to join thread");
     intptr_t ret = reinterpret_cast<intptr_t>(retval);
     if (ret != 0)
       report_fatal_error("Thread returned nonzero");
   }
   return 0;
 }
 
 int main(int argc, char **argv) {
 #if defined(__native_client__)
   return srpc_main(argc, argv);
 #else
   return llc_main(argc, argv);
 #endif // __native_client__
 }