[LTO] Restore original linkage of externals prior to splitting

[tobiasvk]

Summary

This is a companion patch for http://reviews.llvm.org/D16124.

Internalized symbols increase the size of strongly-connected components in
SCC-based module splitting and thus reduce the amount of parallelism. This
patch records the original linkage of non-local symbols prior to
internalization and then restores it just before splitting/CodeGen. This is
also useful for cases where the linker requires symbols to remain external, for
instance, so they can be placed according to linker script rules.

It's currently under its own flag (-restore-globals) but should eventually
share a common flag with D16124.

[mehdi_amini]

That LGTM, but let's wait a bit for Peter to comment.

[pcc]

LGTM, but this should land after D16124.

include/llvm/LTO/LTOCodeGenerator.h

 
 #ifndef LLVM_LTO_LTOCODEGENERATOR_H
 #define LLVM_LTO_LTOCODEGENERATOR_H
 
 #include "llvm-c/lto.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/StringMap.h"
+#include "llvm/IR/GlobalValue.h"
 #include "llvm/Target/TargetMachine.h"
 #include "llvm/Target/TargetOptions.h"
 #include <string>
 #include <vector>
 
 namespace llvm {
   class LLVMContext;
   class DiagnosticInfo;
-  class GlobalValue;
   class Linker;
   class Mangler;
   class MemoryBuffer;
   class TargetLibraryInfo;
   class TargetMachine;
   class raw_ostream;
   class raw_pwrite_stream;
 
struct LTOCodeGenerator {
   LLVMContext &getContext() { return Context; }
 
   void resetMergedModule() { MergedModule.reset(); }
 
 private:
   void initializeLTOPasses();
 
   bool compileOptimizedToFile(const char **Name);
+  void restoreLinkageForExternals();
   void applyScopeRestrictions();
   void applyRestriction(GlobalValue &GV, ArrayRef<StringRef> Libcalls,
                         std::vector<const char *> &MustPreserveList,
                         SmallPtrSetImpl<GlobalValue *> &AsmUsed,
                         Mangler &Mangler);
   bool determineTarget();
 
   static void DiagnosticHandler(const DiagnosticInfo &DI, void *Context);
 
   void DiagnosticHandler2(const DiagnosticInfo &DI);
 
   void emitError(const std::string &ErrMsg);
 
   typedef StringMap<uint8_t> StringSet;
 
   LLVMContext &Context;
   std::unique_ptr<Module> MergedModule;
   std::unique_ptr<Linker> TheLinker;
   std::unique_ptr<TargetMachine> TargetMach;
   bool EmitDwarfDebugInfo = false;
   bool ScopeRestrictionsDone = false;
   Reloc::Model RelocModel = Reloc::Default;
   StringSet MustPreserveSymbols;
   StringSet AsmUndefinedRefs;
+  StringMap<GlobalValue::LinkageTypes> ExternalSymbols;
   std::vector<std::string> CodegenOptions;
   std::string FeatureStr;
   std::string MCpu;
   std::string MAttr;
   std::string NativeObjectPath;
   TargetOptions Options;
   CodeGenOpt::Level CGOptLevel = CodeGenOpt::Default;
   unsigned OptLevel = 2;
   lto_diagnostic_handler_t DiagHandler = nullptr;
   void *DiagContext = nullptr;
   bool ShouldInternalize = true;
   bool ShouldEmbedUselists = false;
   TargetMachine::CodeGenFileType FileType = TargetMachine::CGFT_ObjectFile;
 };
 }
 #endif

lib/LTO/LTOCodeGenerator.cpp

 #include "llvm/Target/TargetRegisterInfo.h"
 #include "llvm/Target/TargetSubtargetInfo.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/IPO/PassManagerBuilder.h"
 #include "llvm/Transforms/ObjCARC.h"
 #include <system_error>
 using namespace llvm;
 
+static cl::opt<bool>
+RestoreExternals("restore-globals", cl::Hidden, cl::init(false),
+                 cl::desc("Restore original linkage of internalized globals"));
+
 const char* LTOCodeGenerator::getVersionString() {
 #ifdef LLVM_VERSION_INFO
   return PACKAGE_NAME " version " PACKAGE_VERSION ", " LLVM_VERSION_INFO;
 #else
   return PACKAGE_NAME " version " PACKAGE_VERSION;
 #endif
 }
 
applyRestriction(GlobalValue &GV,
   // Conservatively append user-supplied runtime library functions to
   // llvm.compiler.used.  These could be internalized and deleted by
   // optimizations like -globalopt, causing problems when later optimizations
   // add new library calls (e.g., llvm.memset => memset and printf => puts).
   // Leave it to the linker to remove any dead code (e.g. with -dead_strip).
   if (isa<Function>(GV) &&
       std::binary_search(Libcalls.begin(), Libcalls.end(), GV.getName()))
     AsmUsed.insert(&GV);
+
+  // Record the linkage type of non-local symbols so they can be restored prior
+  // to module splitting.
+  if (RestoreExternals && !GV.hasAvailableExternallyLinkage() &&
+      !GV.hasLocalLinkage() && GV.hasName())
+    ExternalSymbols.insert(std::make_pair(GV.getName(), GV.getLinkage()));
 }
 
 static void findUsedValues(GlobalVariable *LLVMUsed,
                            SmallPtrSetImpl<GlobalValue*> &UsedValues) {
   if (!LLVMUsed) return;
 
   ConstantArray *Inits = cast<ConstantArray>(LLVMUsed->getInitializer());
   for (unsigned i = 0, e = Inits->getNumOperands(); i != e; ++i)
void LTOCodeGenerator::applyScopeRestrictions() {
   passes.add(createInternalizePass(MustPreserveList));
 
   // apply scope restrictions
   passes.run(*MergedModule);
 
   ScopeRestrictionsDone = true;
 }
 
+/// Restore original linkage for symbols that may have been internalized
+void LTOCodeGenerator::restoreLinkageForExternals() {
+  if (!ShouldInternalize || !RestoreExternals)
+    return;
+
+  assert(ScopeRestrictionsDone &&
+         "Cannot externalize without internalization!");
+
+  if (ExternalSymbols.empty())
+    return;
+
+  auto externalize = [this](GlobalValue &GV) {
+    if (!GV.hasLocalLinkage() || !GV.hasName())
+      return;
+
+    auto I = ExternalSymbols.find(GV.getName());
+    if (I == ExternalSymbols.end())
+      return;
+
+    GV.setLinkage(I->second);
+  };
+
+  std::for_each(MergedModule->begin(), MergedModule->end(), externalize);
+  std::for_each(MergedModule->global_begin(), MergedModule->global_end(),
+                externalize);
+  std::for_each(MergedModule->alias_begin(), MergedModule->alias_end(),
+                externalize);
+}
+
 /// Optimize merged modules using various IPO passes
 bool LTOCodeGenerator::optimize(bool DisableVerify, bool DisableInline,
                                 bool DisableGVNLoadPRE,
                                 bool DisableVectorization) {
   if (!this->determineTarget())
     return false;
 
   // Mark which symbols can not be internalized
bool LTOCodeGenerator::compileOptimized(ArrayRef<raw_pwrite_stream *> Out) {
 
   legacy::PassManager preCodeGenPasses;
 
   // If the bitcode files contain ARC code and were compiled with optimization,
   // the ObjCARCContractPass must be run, so do it unconditionally here.
   preCodeGenPasses.add(createObjCARCContractPass());
   preCodeGenPasses.run(*MergedModule);
 
+  // Re-externalize globals that may have been internalized to increase scope
+  // for splitting
+  restoreLinkageForExternals();
+
   // Do code generation. We need to preserve the module in case the client calls
   // writeMergedModules() after compilation, but we only need to allow this at
   // parallelism level 1. This is achieved by having splitCodeGen return the
   // original module at parallelism level 1 which we then assign back to
   // MergedModule.
   MergedModule =
       splitCodeGen(std::move(MergedModule), Out, MCpu, FeatureStr, Options,
                    RelocModel, CodeModel::Default, CGOptLevel, FileType);

test/LTO/X86/restore-externals.ll

+; Check that "internalizedfn" is re-externalized prior to CodeGen
+;
+; RUN: llvm-as < %s > %t1
+; RUN: llvm-lto -exported-symbol=preservedfn -restore-globals -filetype=asm -o - %t1 | FileCheck %s
+;
+; CHECK: .globl internalizedfn
+
+target triple = "x86_64-unknown-linux-gnu"
+
+declare void @f()
+
+define void @internalizedfn() noinline {
+entry:
+  call void @f()
+  ret void
+}
+
+define void @preservedfn() {
+entry:
+  call void @internalizedfn()
+  ret void
+}
+