[LTO] Handles commons in monolithic LTO

[mehdi_amini]

Summary

The gold-plugin was doing this internally, now the API is handling
commons correctly based on the given resolution.

I didn't test the gold plugin, I need someone to do it for me.

[mehdi_amini]

Fix typo

[mehdi_amini]

One more typo...

[tejohnson]

Thanks for doing this. Will test with gold using LLVM tests and SPEC and get back.

[tejohnson]

I fixed a couple of unused variables, diff shown below. But I am getting a test failure, see further below.

diff --git a/tools/gold/gold-plugin.cpp b/tools/gold/gold-plugin.cpp
index e5d2f2a..ee2f3f3 100644

• a/tools/gold/gold-plugin.cpp

+++ b/tools/gold/gold-plugin.cpp
@@ -564,12 +564,10 @@ static void addModule(LTO &Lto, claimed_file &F, const void *View) {

          toString(ObjOrErr.takeError()).c_str());
 
InputFile &Obj = **ObjOrErr;

• bool HasThinLTOSummary =
• hasGlobalValueSummary(Obj.getMemoryBufferRef(), diagnosticHandler);
  
  unsigned SymNum = 0; std::vector<SymbolResolution> Resols(F.syms.size());
• for (auto &ObjSym : Obj.symbols()) {

+ for (LLVM_ATTRIBUTE_UNUSED auto &ObjSym : Obj.symbols()) {

ld_plugin_symbol &Sym = F.syms[SymNum];
SymbolResolution &R = Resols[SymNum];
++SymNum;

I am getting a failure in the gold common test:

llvm_13/test/tools/gold/X86/common.ll:14:6: error: expected string not found in input
; A: @a = common global [4 x i8] zeroinitializer, align 8

^

<stdin>:4:1: note: possible intended match here
@a = common global [2 x i8] zeroinitializer, align 8
^

I'll need to dig unless you can figure out what might be going on. Will try to look tonight if I have time.

[mehdi_amini]

Change the handling to ignore the prevailing information, every common are taken into account now.

[tejohnson]

Still needs the unused var fixes I noted in the previous comments.

lib/LTO/LTO.cpp

296 ↗

(On Diff #68794)

I noticed that what the existing gold-plugin support does is treat either all as prevailing or none as prevailing - it tracks whether any was prevailing in the CommonResolution structure, and doesn't create a new merged common if none were. Perhaps that should be done here, but I'm not sure when the linker would decide none was prevailing?

[mehdi_amini]

Update gold plugin

[mehdi_amini]

lib/LTO/LTO.cpp

296 ↗

(On Diff #68795)

I none is prevailing, then the linker would drop this global anyway?
Note that the global already exists in the merged module, so if we track if none is prevailing, should we remove it?

296 ↗

(On Diff #68795)

We'd need a clear spec...

[tejohnson]

Getting a failure in your new test. I assume it wasn't designed for the case where we assume all are prevailing.

/usr/local/google/home/tejohnson/llvm/llvm_13/test/tools/llvm-lto2/common.ll:61:23: error: expected string not found in input
; LARGE_LITTLE_ALIGN: @v = common global [2 x i8] zeroinitializer, align 4

^

<stdin>:1:1: note: scanning from here
; ModuleID = '<stdin>'
^
<stdin>:5:1: note: possible intended match here
@v = common global [2 x i8] zeroinitializer, align 8
^

lib/LTO/LTO.cpp

298 ↗

(On Diff #68795)

Missing opening "("

[tejohnson]

But BTW SPEC cpu2006 all pass.

[mehdi_amini]

Add missing parenthesis

[tejohnson]

LGTM

[pcc]

This change doesn't look right to me.

$ cat c1.c
#include <stdio.h>

short x;

int main() {
  printf("%d\n", x);
}
$ cat c2.c
int x = 42;
$ src/llvm/ra/bin/clang -flto -fuse-ld=gold c1.c c2.c
$ ./a.out 
0

The previous implementation handled this correctly by tracking whether any common symbol prevailed.

As I mentioned before, these semantics are gold-specific, and I don't want any other linker to rely on them. If nothing else, can we put these semantics behind a flag?

[mehdi_amini]

I don't have an easy access to gold, can you provide the IR and the resolution so that I can reproduce with llvm-lto2?

Ultimately we need a consistent story for commons, and document it clearly in the API.
Note that we have the hook taking a "const Module &" now which is not something I'd like to regress.

[pcc]

I don't have an easy access to gold, can you provide the IR and the resolution so that I can reproduce with llvm-lto2?

Sure:

$ cat c1.ll
source_filename = "c1.c"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

@x = common global i16 0, align 2
$ cat c2.ll
; ModuleID = 'c2.o'
source_filename = "c2.c"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

@x = global i32 42, align 4
$ ~/src/llvm/ra/bin/llvm-as -o c1.o c1.ll
$ ~/src/llvm/ra/bin/llvm-as -o c2.o c2.ll
$ ~/src/llvm/ra/bin/llvm-lto2 c1.o -r=c1.o,x,l c2.o -r=c2.o,x,pl -o foo -save-temps
$ ~/src/llvm/ra/bin/llvm-dis -o - foo.0.0.preopt.bc 
; ModuleID = 'foo.0.0.preopt.bc'
source_filename = "ld-temp.o"
target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
target triple = "x86_64-unknown-linux-gnu"

@x = common global [2 x i8] zeroinitializer, align 2

Ultimately we need a consistent story for commons, and document it clearly in the API.

I think our story for all symbols should be that there can only be a maximum of a single prevailing symbol. That would be the simplest interface/implementation on the lib/LTO side. It is sufficient for non-ELF, and (with the exception of common symbols) for ELF. There are various workarounds that ELF linkers can use for common symbols, but the implementation of those workarounds ideally shouldn't live in lib/LTO.

[mehdi_amini]

In D23739#541738, @pcc wrote:

I don't have an easy access to gold, can you provide the IR and the resolution so that I can reproduce with llvm-lto2?

Sure:

Thanks.

Ultimately we need a consistent story for commons, and document it clearly in the API.

I think our story for all symbols should be that there can only be a maximum of a single prevailing symbol.

It means that we 1) rely on the client to pick the largest common and 2) we can't adjust the alignment to the largest

So we need to make sure the IRMover handles correctly commons in this case and does not merge them but keep only the prevailing one.

I wonder if we don't risk to have some issues though, if a module was generated with a larger alignement, the loads/stores can be annotated with the high alignment (and other optimization relies on that).
Unless the optimizer knows that he can't assume anything on the alignment of commons...

That would be the simplest interface/implementation on the lib/LTO side. It is sufficient for non-ELF, and (with the exception of common symbols) for ELF. There are various workarounds that ELF linkers can use for common symbols, but the implementation of those workarounds ideally shouldn't live in lib/LTO.

Can you clarify what makes it different for non-ELF linker to handle common? (Or what makes ELF linker to need workaround).

[pcc]

It means that we 1) rely on the client to pick the largest common

The logic already needs to exist in the linker anyway to handle native object files, so I don't see it as a huge problem.

and 2) we can't adjust the alignment to the largest

I would ideally want to keep that logic out of lib/LTO (see below).

I wonder if we don't risk to have some issues though, if a module was generated with a larger alignement, the loads/stores can be annotated with the high alignment (and other optimization relies on that).
Unless the optimizer knows that he can't assume anything on the alignment of commons...

If we avoid emitting common symbols into the module, we can avoid this problem. I suspect optimizations involving alignment of common symbols to be rare, so maybe it's not worth the additional complexity to support them.

Can you clarify what makes it different for non-ELF linker to handle common? (Or what makes ELF linker to need workaround).

I was operating on the assumption that non-ELF linkers only take max size, which would make it straightforward to pick a single prevailing symbol, but from IRC it sounds like linkers for most object formats do in fact want something similar to max size + max alignment.

The workaround I speak of is whatever is needed to create a symbol with the correct size and alignment. That can be done by synthesizing a common symbol that would be internal to the linker (i.e. not creating it in the module) and reporting all common symbols to lib/LTO as non-prevailing, or by creating a common symbol in the module and hence the native object file (which is what the code is currently doing).

If clients can synthesize the symbol, we can avoid having to deal with this issue in lib/LTO. Creating the symbol in the native object file also seems like it may be more complicated on the linker side because it would need to be merged with any other native symbols. So I think the API should be targeted to clients that can synthesize a common symbol, which means having a single prevailing symbol and ignoring all others.

On the other hand, there are clients (i.e. gold) that need the common symbol in the native object file, so maybe this can be a feature of lib/LTO until we have a chance to do something more principled in a way that would be compatible with gold (e.g. the gold plugin could use MC to create its own native object file with the common symbol resolutions).

llvm/trunk/include/llvm/LTO/LTO.h

public:
   /// to add native object files to the link.
   Error run(AddOutputFn AddOutput);
 
 private:
   Config Conf;
 
   struct RegularLTOState {
     RegularLTOState(unsigned ParallelCodeGenParallelismLevel, Config &Conf);
+    struct CommonResolution {
+      uint64_t Size = 0;
+      unsigned Align = 0;
+    };
+    std::map<std::string, CommonResolution> Commons;
 
     unsigned ParallelCodeGenParallelismLevel;
     LTOLLVMContext Ctx;
     bool HasModule = false;
     std::unique_ptr<Module> CombinedModule;
     IRMover Mover;
   } RegularLTO;
 

llvm/trunk/lib/LTO/LTO.cpp

if (Res.Prevailing && GV) {
       case GlobalValue::LinkOnceAnyLinkage:
         GV->setLinkage(GlobalValue::WeakAnyLinkage);
         break;
       case GlobalValue::LinkOnceODRLinkage:
         GV->setLinkage(GlobalValue::WeakODRLinkage);
         break;
       }
     }
+    // Common resolution: collect the maximum size/alignment.
+    // FIXME: right now we ignore the prevailing information, it is not clear
+    // what is the "right" behavior here.
+    if (Sym.getFlags() & object::BasicSymbolRef::SF_Common) {
+      auto &CommonRes = RegularLTO.Commons[Sym.getIRName()];
+      CommonRes.Size = std::max(CommonRes.Size, Sym.getCommonSize());
+      CommonRes.Align = std::max(CommonRes.Align, Sym.getCommonAlignment());
+    }
 
     // FIXME: use proposed local attribute for FinalDefinitionInLinkageUnit.
   }
   assert(ResI == Res.end());
 
   return RegularLTO.Mover.move(Obj->takeModule(), Keep,
                                [](GlobalValue &, IRMover::ValueAdder) {});
 }
if (RegularLTO.HasModule || Conf.PreOptModuleHook ||
       Conf.PostInternalizeModuleHook || Conf.PostOptModuleHook ||
       Conf.PreCodeGenModuleHook)
     if (auto E = runRegularLTO(AddOutput))
       return E;
   return runThinLTO(AddOutput);
 }
 
 Error LTO::runRegularLTO(AddOutputFn AddOutput) {
+  // Make sure commons have the right size/alignment: we kept the largest from
+  // all the prevailing when adding the inputs, and we apply it here.
+  for (auto &I : RegularLTO.Commons) {
+    ArrayType *Ty =
+        ArrayType::get(Type::getInt8Ty(RegularLTO.Ctx), I.second.Size);
+    GlobalVariable *OldGV = RegularLTO.CombinedModule->getNamedGlobal(I.first);
+    if (OldGV && OldGV->getType()->getElementType() == Ty) {
+      // Don't create a new global if the type is already correct, just make
+      // sure the alignment is correct.
+      OldGV->setAlignment(I.second.Align);
+      continue;
+    }
+    auto *GV = new GlobalVariable(*RegularLTO.CombinedModule, Ty, false,
+                                  GlobalValue::CommonLinkage,
+                                  ConstantAggregateZero::get(Ty), "");
+    GV->setAlignment(I.second.Align);
+    if (OldGV) {
+      OldGV->replaceAllUsesWith(ConstantExpr::getBitCast(GV, OldGV->getType()));
+      GV->takeName(OldGV);
+      OldGV->eraseFromParent();
+    } else {
+      GV->setName(I.first);
+    }
+  }
+
   if (Conf.PreOptModuleHook &&
       !Conf.PreOptModuleHook(0, *RegularLTO.CombinedModule))
     return Error();
 
   if (!Conf.CodeGenOnly) {
     for (const auto &R : GlobalResolutions) {
       if (R.second.IRName.empty())
         continue;

llvm/trunk/test/tools/llvm-lto2/Inputs/common.ll

+target triple = "x86_64-apple-macosx10.11.0"
+
+@v = common global i16 0, align 4
+
+define i16 *@bar() {
+ ret i16 *@v
+}
 No newline at end of file

llvm/trunk/test/tools/llvm-lto2/common.ll

+; RUN: llvm-as < %s > %t1.bc
+; RUN: llvm-as < %p/Inputs/common.ll > %t2.bc
+
+; Test that the common merging (size + alignment) is properly handled
+
+; Client marked the "large with little alignment" one as prevailing
+; RUN: llvm-lto2 %t1.bc %t2.bc -o %t.o -save-temps \
+; RUN:  -r %t1.bc,v,x \
+; RUN:  -r %t2.bc,v,px \
+; RUN:  -r %t1.bc,foo,px \
+; RUN:  -r %t2.bc,bar,px
+; RUN: llvm-dis < %t.o.0.0.preopt.bc | FileCheck %s
+
+; Same as before, but reversing the order of the inputs
+; RUN: llvm-lto2 %t2.bc %t1.bc -o %t.o -save-temps \
+; RUN:  -r %t1.bc,v,x \
+; RUN:  -r %t2.bc,v,px \
+; RUN:  -r %t1.bc,foo,px \
+; RUN:  -r %t2.bc,bar,px
+; RUN: llvm-dis < %t.o.0.0.preopt.bc | FileCheck %s
+
+
+; Client marked the "small with large alignment" one as prevailing
+; RUN: llvm-lto2 %t1.bc %t2.bc -o %t.o -save-temps \
+; RUN:  -r %t1.bc,v,px \
+; RUN:  -r %t2.bc,v,x \
+; RUN:  -r %t1.bc,foo,px \
+; RUN:  -r %t2.bc,bar,px
+; RUN: llvm-dis < %t.o.0.0.preopt.bc | FileCheck %s
+
+; Same as before, but reversing the order of the inputs
+; RUN: llvm-lto2 %t2.bc %t1.bc -o %t.o -save-temps \
+; RUN:  -r %t1.bc,v,px \
+; RUN:  -r %t2.bc,v,x \
+; RUN:  -r %t1.bc,foo,px \
+; RUN:  -r %t2.bc,bar,px
+; RUN: llvm-dis < %t.o.0.0.preopt.bc | FileCheck  %s
+
+
+; Client didn't mark any as prevailing, we keep the first one we see as "external"
+; RUN: llvm-lto2 %t1.bc %t2.bc -o %t.o -save-temps \
+; RUN:  -r %t1.bc,v,x \
+; RUN:  -r %t2.bc,v,x \
+; RUN:  -r %t1.bc,foo,px \
+; RUN:  -r %t2.bc,bar,px
+; RUN: llvm-dis < %t.o.0.0.preopt.bc | FileCheck  %s
+
+; Same as before, but reversing the order of the inputs
+; RUN: llvm-lto2 %t2.bc %t1.bc -o %t.o -save-temps \
+; RUN:  -r %t1.bc,v,x \
+; RUN:  -r %t2.bc,v,x \
+; RUN:  -r %t1.bc,foo,px \
+; RUN:  -r %t2.bc,bar,px
+; RUN: llvm-dis < %t.o.0.0.preopt.bc | FileCheck  %s
+
+target triple = "x86_64-apple-macosx10.11.0"
+
+@v = common global i8 0, align 8
+
+
+; CHECK: @v = common global [2 x i8] zeroinitializer, align 8
+
+define i8 *@foo() {
+ ret i8 *@v
+}
 No newline at end of file

llvm/trunk/tools/gold/gold-plugin.cpp

struct PluginInputFile {
   PluginInputFile &operator=(PluginInputFile &&RHS) = default;
 };
 
 struct ResolutionInfo {
   bool CanOmitFromDynSym = true;
   bool DefaultVisibility = true;
 };
 
-struct CommonResolution {
-  bool Prevailing = false;
-  bool VisibleToRegularObj = false;
-  uint64_t Size = 0;
-  unsigned Align = 0;
-};
-
 }
 
 static ld_plugin_add_symbols add_symbols = nullptr;
 static ld_plugin_get_symbols get_symbols = nullptr;
 static ld_plugin_add_input_file add_input_file = nullptr;
 static ld_plugin_set_extra_library_path set_extra_library_path = nullptr;
 static ld_plugin_get_view get_view = nullptr;
 static bool IsExecutable = false;
 static Optional<Reloc::Model> RelocationModel;
 static std::string output_name = "";
 static std::list<claimed_file> Modules;
 static DenseMap<int, void *> FDToLeaderHandle;
 static StringMap<ResolutionInfo> ResInfo;
-static std::map<std::string, CommonResolution> Commons;
 static std::vector<std::string> Cleanup;
 static llvm::TargetOptions TargetOpts;
 static size_t MaxTasks;
 
 namespace options {
   enum OutputType {
     OT_NORMAL,
     OT_DISABLE,
static void addModule(LTO &Lto, claimed_file &F, const void *View) {
   MemoryBufferRef BufferRef(StringRef((const char *)View, F.filesize), F.name);
   Expected<std::unique_ptr<InputFile>> ObjOrErr = InputFile::create(BufferRef);
 
   if (!ObjOrErr)
     message(LDPL_FATAL, "Could not read bitcode from file : %s",
             toString(ObjOrErr.takeError()).c_str());
 
   InputFile &Obj = **ObjOrErr;
-  bool HasThinLTOSummary =
-      hasGlobalValueSummary(Obj.getMemoryBufferRef(), diagnosticHandler);
 
   unsigned SymNum = 0;
   std::vector<SymbolResolution> Resols(F.syms.size());
-  for (auto &ObjSym : Obj.symbols()) {
+  for (LLVM_ATTRIBUTE_UNUSED auto &ObjSym : Obj.symbols()) {
     ld_plugin_symbol &Sym = F.syms[SymNum];
     SymbolResolution &R = Resols[SymNum];
     ++SymNum;
 
     ld_plugin_symbol_resolution Resolution =
         (ld_plugin_symbol_resolution)Sym.resolution;
 
     ResolutionInfo &Res = ResInfo[Sym.name];
case LDPR_PREVAILING_DEF_IRONLY_EXP:
         R.VisibleToRegularObj = true;
       break;
     }
 
     if (Resolution != LDPR_RESOLVED_DYN && Resolution != LDPR_UNDEF &&
         (IsExecutable || !Res.DefaultVisibility))
       R.FinalDefinitionInLinkageUnit = true;
 
-    if ((ObjSym.getFlags() & object::BasicSymbolRef::SF_Common) &&
-        !HasThinLTOSummary) {
-      // We ignore gold's resolution for common symbols. A common symbol with
-      // the correct size and alignment is added to the module by the pre-opt
-      // module hook if any common symbol prevailed.
-      CommonResolution &CommonRes = Commons[ObjSym.getIRName()];
-      if (R.Prevailing) {
-        CommonRes.Prevailing = true;
-        CommonRes.VisibleToRegularObj = R.VisibleToRegularObj;
-      }
-      CommonRes.Size = std::max(CommonRes.Size, ObjSym.getCommonSize());
-      CommonRes.Align = std::max(CommonRes.Align, ObjSym.getCommonAlignment());
-      R.Prevailing = false;
-    }
-
     freeSymName(Sym);
   }
 
   check(Lto.add(std::move(*ObjOrErr), Resols),
         std::string("Failed to link module ") + F.name);
 }
 
 static void recordFile(std::string Filename, bool TempOutFile) {
if (EC)
               EC.message().c_str());
   } else {
     NewFilename = InFilename;
     if (TaskID >= 0)
       NewFilename += utostr(TaskID);
   }
 }
 
-/// Add all required common symbols to M, which is expected to be the first
-/// combined module.
-static void addCommons(Module &M) {
-  for (auto &I : Commons) {
-    if (!I.second.Prevailing)
-      continue;
-    ArrayType *Ty =
-        ArrayType::get(Type::getInt8Ty(M.getContext()), I.second.Size);
-    GlobalVariable *OldGV = M.getNamedGlobal(I.first);
-    auto *GV = new GlobalVariable(M, Ty, false, GlobalValue::CommonLinkage,
-                                  ConstantAggregateZero::get(Ty), "");
-    GV->setAlignment(I.second.Align);
-    if (OldGV) {
-      OldGV->replaceAllUsesWith(ConstantExpr::getBitCast(GV, OldGV->getType()));
-      GV->takeName(OldGV);
-      OldGV->eraseFromParent();
-    } else {
-      GV->setName(I.first);
-    }
-    // We may only internalize commons if there is a single LTO task because
-    // other native object files may require the common.
-    if (MaxTasks == 1 && !I.second.VisibleToRegularObj)
-      GV->setLinkage(GlobalValue::InternalLinkage);
-  }
-}
-
 static CodeGenOpt::Level getCGOptLevel() {
   switch (options::OptLevel) {
   case 0:
     return CodeGenOpt::None;
   case 1:
     return CodeGenOpt::Less;
   case 2:
     return CodeGenOpt::Default;
Backend = createWriteIndexesThinBackend(
         options::thinlto_linked_objects_file);
   }
 
   Conf.OverrideTriple = options::triple;
   Conf.DefaultTriple = sys::getDefaultTargetTriple();
 
   Conf.DiagHandler = diagnosticHandler;
 
-  Conf.PreOptModuleHook = [](size_t Task, Module &M) {
-    if (Task == 0)
-      addCommons(M);
-    return true;
-  };
-
   switch (options::TheOutputType) {
   case options::OT_NORMAL:
     break;
 
   case options::OT_DISABLE:
     Conf.PreOptModuleHook = [](size_t Task, Module &M) { return false; };
     break;