Change LLVM bitcode linking to use tree reduction to scale better

llvm/tools/lto/LTOCodeGenerator.cpp

 //===-LTOCodeGenerator.cpp - LLVM Link Time Optimizer ---------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // This file implements the Link Time Optimization library. This library is
@@ skipping 83 matching lines @@
 bool LTOCodeGenerator::addModule(LTOModule* mod, std::string& errMsg) {
   bool ret = _linker.LinkInModule(mod->getLLVVMModule(), &errMsg);
 
   const std::vector<const char*> &undefs = mod->getAsmUndefinedRefs();
   for (int i = 0, e = undefs.size(); i != e; ++i)
     _asmUndefinedRefs[undefs[i]] = 1;
 
   return ret;
 }
 
+
+// @LOCALMOD-BEGIN
+bool LTOCodeGenerator::gatherModule(LTOModule* mod) {

[robertm, 2012/08/01 14:02:31]

gather is no a very specific term.
Maybe add a comment or use a better function name:
e.g. :
// Add module to list of modules which are part of the "linked" image.
// Note: the link does not happen right away but is delayed 
// so that we can optimize this rather costly step

[jvoung (off chromium), 2012/08/01 17:11:01]

renamed to gatherModuleForLink(), but yeah, not sure what is best.  Added some
comments though.

+  _gatheredModules.push_back(mod);
+}
+
+bool LTOCodeGenerator::linkGatheredModulesAndDispose(std::string& errMsg) {
+  // We gather the asm undefs earlier than addModule() does,

[robertm, 2012/08/01 14:02:31]

since the llvm folks did not seem to have commented this asm undef stuff.
Could you describe in a comment what you have learned about that.

[jvoung (off chromium), 2012/08/01 17:11:01]

Added some comments.  Hopefully this is a constant array that is not modified by
merging.  It looks like it is a "char*" of some global's name coming straight
from ASM, so that shouldn't be interpreted and changed by llvm???

+  // since we delete the modules earlier.
+  for (unsigned i = 0, ei = _gatheredModules.size(); i != ei; ++i) {
+    const std::vector<const char*> &undefs =
+        _gatheredModules[i]->getAsmUndefinedRefs();
+    for (int j = 0, ej = undefs.size(); j != ej; ++j) {
+      _asmUndefinedRefs[undefs[j]] = 1;
+    }
+  }
+
+  // Tree-reduce the mods, re-using the incoming mods as scratch
+  // intermediate results.  Module i is linked with (i + stride), with i as
+  // the dest.  Eventually the Module with the content of all other modules
+  // will be Module 0.

[robertm, 2012/08/01 14:02:31]

not sure whether this adds all that much:
After the first round (stride = 1) only modules with even index are still there,
after the second round (stride = 2) only the modules with indices divisible by 4
are still there, etc. 


If you can find some algorithmic reference that would be even better. 
Also say that we disregard module sizes for now.

[jvoung (off chromium), 2012/08/01 17:11:01]

Done.

+  unsigned stride = 1;
+  unsigned len = _gatheredModules.size();
+  while (stride < len) {

[robertm, 2012/08/01 14:02:31]

why not use a for loop here as well

[jvoung (off chromium), 2012/08/01 17:11:01]

Done.

+    for (unsigned i = 0; i + stride < len; i = i + (stride * 2)) {
+      if (Linker::LinkModules(_gatheredModules[i]->getLLVVMModule(),
+                              _gatheredModules[i+stride]->getLLVVMModule(),
+                              Linker::DestroySource, &errMsg)) {
+        errs() << "LinkModules " << i << " w/ " << i + stride << " failed...\n";
+        // We leak the memory in this case...
+        return true;
+      }
+      delete _gatheredModules[i+stride];
+    }
+    stride = stride * 2;
+  }
+
+  // Finally, link Node 0 with the Dest and delete Node 0.
+  if (_linker.LinkInModule(_gatheredModules[0]->getLLVVMModule(), &errMsg)) {
+    errs() << "LinkModules Dst w/ _gatheredModules[0] failed...\n";
+    return true;
+  }
+  delete _gatheredModules[0];
+
+  return false;
+}
+// @LOCALMOD-END
+
 bool LTOCodeGenerator::setDebugInfo(lto_debug_model debug,
                                     std::string& errMsg) {
   switch (debug) {
   case LTO_DEBUG_MODEL_NONE:
     _emitDwarfDebugInfo = false;
     return false;
 
   case LTO_DEBUG_MODEL_DWARF:
     _emitDwarfDebugInfo = true;
     return false;
@@ skipping 372 matching lines @@
 void LTOCodeGenerator::setCodeGenDebugOptions(const char *options) {
   for (std::pair<StringRef, StringRef> o = getToken(options);
        !o.first.empty(); o = getToken(o.second)) {
     // ParseCommandLineOptions() expects argv[0] to be program name. Lazily add
     // that.
     if ( _codegenOptions.empty() )
       _codegenOptions.push_back(strdup("libLTO"));
     _codegenOptions.push_back(strdup(o.first.str().c_str()));
   }
 }