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 76 matching lines @@
   if (Target.addPassesToEmitFile(*PM, FOS, FileType,
                                  /* 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();
+    int FuncIndex = 0;
+    switch (SplitModuleSched) {
+    case SplitModuleStatic:
+      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;
       }
+      break;
+    case SplitModuleDynamic:
+      unsigned ChunkSize = 0;
+      for (Module::iterator I = mod->begin(), E = mod->end(); I != E; ) {
+        ChunkSize = FuncQueue->RecommendedChunkSize();
+        int NextIndex;
+        bool grabbed = FuncQueue->GrabFunctionDynamic(FuncIndex, ChunkSize,
+                                                      NextIndex);
+        if (grabbed) {
+          while (FuncIndex < NextIndex && I != E) {
+            P->run(*I);
+            CheckABIVerifyErrors(ABIErrorReporter, "Function " + I->getName());
+            I->Dematerialize();
+            ++FuncIndex;
+            ++I;
+          }
+        } else {
+          // Currently the ResolvePNaClIntrinsics function pass may
+          // add more declarations as we iterate. Some threads may get
+          // "lucky" and not add the related declarations, so those
+          // threads would have an earlier endpoint than other
+          // threads.  the final NextIndex established by another
+          // thread would then be out of the bounds of the current thread.
+          // TODO(jvoung): Ensure that all declarations are added up front
+          // and uniformly so that we don't need this I != E check.
+          while (FuncIndex < NextIndex && I != E) {
+            ++FuncIndex;
+            ++I;
+          }
+        }
+      }
+      break;
     }
     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__
 }