[Internalize] Rename instead of removal if a to-be-internalized comdat has more than one member

[MaskRay]

Summary

Beside the comdat any deduplication feature, instrumentations use comdat to
establish dependencies among a group of sections, to prevent section based
linker garbage collection from discarding some members without discarding all.
LangRef acknowledges this usage with the following wording:

All global objects that specify this key will only end up in the final object file if the linker chooses that key over some other key.

On ELF, for PGO instrumentation, a __llvm_prf_cnts section and its associated
__llvm_prf_data section are placed in the same GRP_COMDAT group. A
__llvm_prf_data is usually not referenced and expects the liveness of its
associated __llvm_prf_cnts to retain it.

The setComdat(nullptr) code (added by D10679) in InternalizePass can break the
use case (a __llvm_prf_data may be dropped with its associated __llvm_prf_cnts retained).
The main goal of this patch is to fix the dependency relationship.

I think it makes sense for InternalizePass to internalize a comdat and thus
suppress the deduplication feature, e.g. a relocatable link of a regular LTO can
create an object file affected by InternalizePass.
If a non-internal comdat in a.o is prevailed by an internal comdat in b.o, the a.o references to the comdat definitions will be non-resolvable (references cannot bind to STB_LOCAL definitions in b.o)

hide deduplication so that the result object file cannot collide with a
subsequent link with a comdat with the same signature but non-internal.
The approach adopted by this patch tries to keep this semantics working.

On PE-COFF, for a non-external selection symbol, deduplication is naturally
suppressed with link.exe and lld-link. However, this is fuzzy on ELF and I tend
to believe the spec creator has not thought about this use case (see D102973).

GNU ld and gold are still using the "signature is name based" interpretation.
So even if D102973 for ld.lld is accepted, for portability, a better approach is
to rename the comdat. A comdat with one single member is the common case,
leaving the comdat can waste (sizeof(Elf64_Shdr)+4*2) bytes, so we optimize by
deleting the comdat; otherwise we rename the comdat.

[tejohnson]

This seems like a reasonable approach to me. Couple minor comments below. Hoping others can take a look in case I am missing anything.

llvm/include/llvm/Transforms/IPO/Internalize.h

37

Struct fields could use some descriptive comments.

llvm/test/Transforms/Internalize/comdat-empty-moduleid.ll

5

Presumably this doesn't hurt in practice because all of the internal symbols get removed during optimization?

[MaskRay]

Add comments

llvm/test/Transforms/Internalize/comdat-empty-moduleid.ll

5

Confirmed that GlobalOpt will discard all the internal symbols.

opt -internalize a.ll | opt -O2 -S

[xur]

I can understand the single member comdat part -- it should be safe to internalize it without break anything. I'm not sure I follow the rename part. Why can't the linker handle the duplicated comdat? Is deduplication should be done by linker?

[MaskRay]

In D103043#2778216, @xur wrote:

I can understand the single member comdat part -- it should be safe to internalize it without break anything. I'm not sure I follow the rename part. Why can't the linker handle the duplicated comdat? Is deduplication should be done by linker?

On PE-COFF, a comdat with a non-external selection symbol does not deduplicate.

On ELF, a comdat with a STB_LOCAL signature symbol still deduplicates with all of ld.lld/GNU ld/gold. If a non-internal comdat in a.o is prevailed by an internal comdat in b.o, the a.o references to the comdat definitions will be un-resolvable (references cannot bind to STB_LOCAL definitions in b.o)

[tejohnson]

lgtm

[MaskRay]

Thanks! I'll push this in the afternoon if I have seen no objection.

[nickdesaulniers]

This seems to be causing some build breakage for us when building with thinLTO+PGO: https://github.com/ClangBuiltLinux/linux/issues/1388.

ld.lld: error: drivers/gpu/drm/amd/amdgpu/amdgpu.lto.o: SHT_SYMTAB_SHNDX has 79582 entries, but the symbol table associated has 79583

Should "the symbol table associated" also have some renaming done, rather than removal?

[MaskRay]

In D103043#2791494, @nickdesaulniers wrote:

This seems to be causing some build breakage for us when building with thinLTO+PGO: https://github.com/ClangBuiltLinux/linux/issues/1388.

ld.lld: error: drivers/gpu/drm/amd/amdgpu/amdgpu.lto.o: SHT_SYMTAB_SHNDX has 79582 entries, but the symbol table associated has 79583

Should "the symbol table associated" also have some renaming done, rather than removal?

The diagnostic is about size(.symtab) and size(.symtab_shndx) mismatch, unrelated to what the patch did.

I've commented on https://github.com/ClangBuiltLinux/linux/issues/1388

llvm/include/llvm/Transforms/IPO/Internalize.h

 // For example: Internalizing a function with external linkage. Only if we are
 // told it is only used from within this module, it is safe to do it.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_TRANSFORMS_IPO_INTERNALIZE_H
 #define LLVM_TRANSFORMS_IPO_INTERNALIZE_H
 
-#include "llvm/ADT/DenseSet.h"
+#include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/StringSet.h"
 #include "llvm/IR/GlobalValue.h"
 #include "llvm/IR/PassManager.h"
 #include <functional>
 
 namespace llvm {
 class Module;
 class CallGraph;
 
 /// A pass that internalizes all functions and variables other than those that
 /// must be preserved according to \c MustPreserveGV.
 class InternalizePass : public PassInfoMixin<InternalizePass> {
+  struct ComdatInfo {
+    size_t Size = 0;
+    bool External = false;
+    Comdat *Dest = nullptr;
+  };
+
+  // For ELF, we need to rename comdat to a uniquified name. We derive the new
+  // comdat name from ModuleId.
+  std::string ModuleId;
+  bool IsELF = false;
+
   /// Client supplied callback to control wheter a symbol must be preserved.
   const std::function<bool(const GlobalValue &)> MustPreserveGV;
   /// Set of symbols private to the compiler that this pass should not touch.
   StringSet<> AlwaysPreserved;
 
   /// Return false if we're allowed to internalize this GV.
   bool shouldPreserveGV(const GlobalValue &GV);
   /// Internalize GV if it is possible to do so, i.e. it is not externally
   /// visible and is not a member of an externally visible comdat.
   bool maybeInternalize(GlobalValue &GV,
-                        const DenseSet<const Comdat *> &ExternalComdats);
+                        DenseMap<const Comdat *, ComdatInfo> &ComdatMap);
   /// If GV is part of a comdat and is externally visible, keep track of its
   /// comdat so that we don't internalize any of its members.
-  void checkComdatVisibility(GlobalValue &GV,
-                             DenseSet<const Comdat *> &ExternalComdats);
+  void checkComdat(GlobalValue &GV,
+                   DenseMap<const Comdat *, ComdatInfo> &ComdatMap);
 
 public:
   InternalizePass();
   InternalizePass(std::function<bool(const GlobalValue &)> MustPreserveGV)
       : MustPreserveGV(std::move(MustPreserveGV)) {}
 
   /// Run the internalizer on \p TheModule, returns true if any changes was
   /// made.

llvm/lib/Transforms/IPO/Internalize.cpp

 // told it is only used from within this module, it is safe to do it.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Transforms/IPO/Internalize.h"
 #include "llvm/ADT/SmallPtrSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/ADT/StringSet.h"
+#include "llvm/ADT/Triple.h"
 #include "llvm/Analysis/CallGraph.h"
 #include "llvm/IR/Module.h"
 #include "llvm/InitializePasses.h"
 #include "llvm/Pass.h"
 #include "llvm/Support/CommandLine.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/LineIterator.h"
 #include "llvm/Support/MemoryBuffer.h"
 #include "llvm/Support/raw_ostream.h"
 #include "llvm/Transforms/IPO.h"
 #include "llvm/Transforms/Utils/GlobalStatus.h"
+#include "llvm/Transforms/Utils/ModuleUtils.h"
 using namespace llvm;
 
 #define DEBUG_TYPE "internalize"
 
 STATISTIC(NumAliases, "Number of aliases internalized");
 STATISTIC(NumFunctions, "Number of functions internalized");
 STATISTIC(NumGlobals, "Number of global vars internalized");
 
bool InternalizePass::shouldPreserveGV(const GlobalValue &GV) {
   // Check some special cases
   if (AlwaysPreserved.count(GV.getName()))
     return true;
 
   return MustPreserveGV(GV);
 }
 
 bool InternalizePass::maybeInternalize(
-    GlobalValue &GV, const DenseSet<const Comdat *> &ExternalComdats) {
+    GlobalValue &GV, DenseMap<const Comdat *, ComdatInfo> &ComdatMap) {
+  SmallString<0> ComdatName;
   if (Comdat *C = GV.getComdat()) {
-    if (ExternalComdats.count(C))
+    // For GlobalAlias, C is the aliasee object's comdat which may have been
+    // redirected. So ComdatMap may not contain C.
+    if (ComdatMap.lookup(C).External)
       return false;
 
-    // If a comdat is not externally visible we can drop it.
-    if (auto GO = dyn_cast<GlobalObject>(&GV))
+    if (auto GO = dyn_cast<GlobalObject>(&GV)) {
+      // If a comdat with one member is not externally visible, we can drop it.
+      // Otherwise, the comdat can be used to establish dependencies among the
+      // group of sections. Thus we have to keep the comdat.
+      //
+      // On ELF, GNU ld and gold use the signature name as the comdat
+      // deduplication key. Rename the comdat to suppress deduplication with
+      // other object files. On COFF, non-external selection symbol suppresses
+      // deduplication and thus does not need renaming.
+      ComdatInfo &Info = ComdatMap.find(C)->second;
+      if (Info.Size == 1) {
         GO->setComdat(nullptr);
+      } else if (IsELF) {
+        if (Info.Dest == nullptr)
+          Info.Dest = GV.getParent()->getOrInsertComdat(
+              (C->getName() + ModuleId).toStringRef(ComdatName));
+        GO->setComdat(Info.Dest);
+      }
+    }
 
     if (GV.hasLocalLinkage())
       return false;
   } else {
     if (GV.hasLocalLinkage())
       return false;
 
     if (shouldPreserveGV(GV))
       return false;
   }
 
   GV.setVisibility(GlobalValue::DefaultVisibility);
   GV.setLinkage(GlobalValue::InternalLinkage);
   return true;
 }
 
-// If GV is part of a comdat and is externally visible, keep track of its
-// comdat so that we don't internalize any of its members.
-void InternalizePass::checkComdatVisibility(
-    GlobalValue &GV, DenseSet<const Comdat *> &ExternalComdats) {
+// If GV is part of a comdat and is externally visible, update the comdat size
+// and keep track of its comdat so that we don't internalize any of its members.
+void InternalizePass::checkComdat(
+    GlobalValue &GV, DenseMap<const Comdat *, ComdatInfo> &ComdatMap) {
   Comdat *C = GV.getComdat();
   if (!C)
     return;
 
+  ComdatInfo &Info = ComdatMap.try_emplace(C).first->second;
+  ++Info.Size;
   if (shouldPreserveGV(GV))
-    ExternalComdats.insert(C);
+    Info.External = true;
 }
 
 bool InternalizePass::internalizeModule(Module &M, CallGraph *CG) {
   bool Changed = false;
   CallGraphNode *ExternalNode = CG ? CG->getExternalCallingNode() : nullptr;
 
   SmallVector<GlobalValue *, 4> Used;
   collectUsedGlobalVariables(M, Used, false);
 
-  // Collect comdat visiblity information for the module.
-  DenseSet<const Comdat *> ExternalComdats;
+  // Collect comdat size and visiblity information for the module.
+  DenseMap<const Comdat *, ComdatInfo> ComdatMap;
   if (!M.getComdatSymbolTable().empty()) {
     for (Function &F : M)
-      checkComdatVisibility(F, ExternalComdats);
+      checkComdat(F, ComdatMap);
     for (GlobalVariable &GV : M.globals())
-      checkComdatVisibility(GV, ExternalComdats);
+      checkComdat(GV, ComdatMap);
     for (GlobalAlias &GA : M.aliases())
-      checkComdatVisibility(GA, ExternalComdats);
+      checkComdat(GA, ComdatMap);
   }
 
   // We must assume that globals in llvm.used have a reference that not even
   // the linker can see, so we don't internalize them.
   // For llvm.compiler.used the situation is a bit fuzzy. The assembler and
   // linker can drop those symbols. If this pass is running as part of LTO,
   // one might think that it could just drop llvm.compiler.used. The problem
   // is that even in LTO llvm doesn't see every reference. For example,
   // we don't see references from function local inline assembly. To be
   // conservative, we internalize symbols in llvm.compiler.used, but we
   // keep llvm.compiler.used so that the symbol is not deleted by llvm.
   for (GlobalValue *V : Used) {
     AlwaysPreserved.insert(V->getName());
   }
 
   // Mark all functions not in the api as internal.
+  ModuleId = getUniqueModuleId(&M);
+  IsELF = Triple(M.getTargetTriple()).isOSBinFormatELF();
   for (Function &I : M) {
-    if (!maybeInternalize(I, ExternalComdats))
+    if (!maybeInternalize(I, ComdatMap))
       continue;
     Changed = true;
 
     if (ExternalNode)
       // Remove a callgraph edge from the external node to this function.
       ExternalNode->removeOneAbstractEdgeTo((*CG)[&I]);
 
     ++NumFunctions;
bool InternalizePass::internalizeModule(Module &M, CallGraph *CG) {
   // FIXME: We should probably add this (and the __stack_chk_guard) via some
   // type of call-back in CodeGen.
   AlwaysPreserved.insert("__stack_chk_fail");
   AlwaysPreserved.insert("__stack_chk_guard");
 
   // Mark all global variables with initializers that are not in the api as
   // internal as well.
   for (auto &GV : M.globals()) {
-    if (!maybeInternalize(GV, ExternalComdats))
+    if (!maybeInternalize(GV, ComdatMap))
       continue;
     Changed = true;
 
     ++NumGlobals;
     LLVM_DEBUG(dbgs() << "Internalized gvar " << GV.getName() << "\n");
   }
 
   // Mark all aliases that are not in the api as internal as well.
   for (auto &GA : M.aliases()) {
-    if (!maybeInternalize(GA, ExternalComdats))
+    if (!maybeInternalize(GA, ComdatMap))
       continue;
     Changed = true;
 
     ++NumAliases;
     LLVM_DEBUG(dbgs() << "Internalized alias " << GA.getName() << "\n");
   }
 
   return Changed;

llvm/test/Transforms/Internalize/comdat-empty-moduleid.ll

+; RUN: opt < %s -mtriple=x86_64 -internalize -S | FileCheck %s
+
+$c2 = comdat any
+
+;; Without an exported symbol, the module ID is empty. In this case we don't rename comdat for ELF.
+
+; CHECK: define internal void @c2_a() comdat($c2) {
+define void @c2_a() comdat($c2) {
+  ret void
+}
+
+; CHECK: define internal void @c2_b() comdat($c2) {
+define void @c2_b() comdat($c2) {
+  ret void
+}

llvm/test/Transforms/Internalize/comdat.ll

-; RUN: opt < %s -internalize -internalize-public-api-list c1 -internalize-public-api-list c2 -internalize-public-api-list c3 -internalize-public-api-list c4 -S | FileCheck %s
+; RUN: opt < %s -mtriple=x86_64 -internalize -internalize-public-api-list main -internalize-public-api-list c1 -internalize-public-api-list c2 \
+; RUN:   -internalize-public-api-list c3 -internalize-public-api-list c4 -S | FileCheck %s --check-prefixes=CHECK,ELF
+; RUN: opt < %s -mtriple=x86_64-windows -internalize -internalize-public-api-list main -internalize-public-api-list c1 -internalize-public-api-list c2 \
+; RUN:   -internalize-public-api-list c3 -internalize-public-api-list c4 -S | FileCheck %s --check-prefixes=CHECK,COFF
 
 $c1 = comdat any
 $c2 = comdat any
 $c3 = comdat any
 $c4 = comdat any
+$c5 = comdat any
+
+; ELF:   $c2.[[MODULEID:[0-9a-f]+]] = comdat any
+; COFF:  $c2 = comdat any
 
 ; CHECK: @c1_c = global i32 0, comdat($c1)
 @c1_c = global i32 0, comdat($c1)
 
-; CHECK: @c2_b = internal global i32 0{{$}}
+;; $c2 has more than one member. Keep the comdat.
+; ELF:   @c2_b = internal global i32 0, comdat($c2.[[MODULEID]])
+; COFF:  @c2_b = internal global i32 0, comdat($c2)
 @c2_b = global i32 0, comdat($c2)
 
 ; CHECK: @c3 = global i32 0, comdat{{$}}
 @c3 = global i32 0, comdat
 
 ; CHECK: @c4_a = internal global i32 0, comdat($c4)
 @c4_a = internal global i32 0, comdat($c4)
 
define void @c1() comdat {
   ret void
 }
 
 ; CHECK: define void @c1_a() comdat($c1) {
 define void @c1_a() comdat($c1) {
   ret void
 }
 
-; CHECK: define internal void @c2() {
+; ELF:   define internal void @c2() comdat($c2.[[MODULEID]]) {
+; COFF:  define internal void @c2() comdat {
 define internal void @c2() comdat {
   ret void
 }
 
-; CHECK: define internal void @c2_a() {
+; ELF:   define internal void @c2_a() comdat($c2.[[MODULEID]]) {
+; COFF:  define internal void @c2_a() comdat($c2) {
 define void @c2_a() comdat($c2) {
   ret void
 }
 
 ; CHECK: define void @c3_a() comdat($c3) {
 define void @c3_a() comdat($c3) {
   ret void
 }
+
+;; There is only one member in the comdat. Delete the comdat as a size optimization.
+; CHECK: define internal void @c5() {
+define void @c5() comdat($c5) {
+  ret void
+}
+
+;; Add a non-comdat symbol to ensure the module ID is not empty so that we can
+;; create unique comdat names.
+define void @main() {
+  ret void
+}