Change LLVM bitcode linking to use tree reduction to scale better

llvm/tools/lto/LTOCodeGenerator.cpp

Index: llvm/tools/lto/LTOCodeGenerator.cpp
===================================================================
--- a/llvm/tools/lto/LTOCodeGenerator.cpp
+++ b/llvm/tools/lto/LTOCodeGenerator.cpp
@@ -101,6 +101,54 @@
   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) {