ThinLTOBitcodeWriter: delete comdats if their keys are renamed

[inglorion]

Summary

COFF requires that every comdat contain a symbol with the same name as the comdat. ThinLTOBitcodeWriter renames symbols, which may cause this requirement to be violated. This change avoids such violations by deleting the affected comdats.

[pcc]

It isn't clear whether this does the right thing if the comdat contains associated members, only some of which need to be moved to the merged module. Although I believe that the frontend will never attach !type metadata to a global in a comdat with associated members, the asan globals feature could add an associated member to such a comdat.

An optimal fix would be to rename the comdat to match the symbol name and ensure that all comdat members are moved to the merged module if any member needs to be moved. But I think it would also be valid to remove the comdats from both modules, as this change (almost) does.

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

79

I think it would be simpler to do two passes over global_values, one where you decide which comdats to delete and the other where you delete them.

[inglorion]

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

79

Definitely simpler. Are you ok with iterating all the globals again? This more complex implementation tries to avoid some of the work by immediately deleting references to comdats already slated for deletion and indexing globals by comdat to avoid having to iterate over all the globals again (based on the assumption that most globals either won't have a comdat or the comdat will have the same name as the global).

Also, did you want me to iterate over the symbols in ImportM as well (as per your "remove the comdats from both modules")?

[rnk]

Does clang generate internal globals with comdats that *don't* have other associated globals in that comdat? If so, that's probably a bug, but thinlto should still tolerate it.

Maybe thinlto is internalizing globals without removing their comdats?

[mehdi_amini]

COFF requires that every comdat contain a symbol with the same name as the comdat.

Is there a verifier for this? Also if I read correctly your test-case, the symbol @foo isn't part of the comdat $foo?
It isn't clear to me that this patch isn't working around a bug somewhere else.

[rnk]

In D31735#719700, @pcc wrote:

It isn't clear whether this does the right thing if the comdat contains associated members, only some of which need to be moved to the merged module. Although I believe that the frontend will never attach !type metadata to a global in a comdat with associated members, the asan globals feature could add an associated member to such a comdat.

An optimal fix would be to rename the comdat to match the symbol name and ensure that all comdat members are moved to the merged module if any member needs to be moved. But I think it would also be valid to remove the comdats from both modules, as this change (almost) does.

I'd like to push to get the rename implemented. If we have an internal global with a comdat group, the frontend probably put it there for a good reason (the non-leader is probably metadata) and we shouldn't mess with it.

I hadn't considered that ThinLTO might try to import part of a comdat group, splitting the group. That seems like something we shouldn't do.

[pcc]

Maybe thinlto is internalizing globals without removing their comdats?

This pass is being run in clang prior to internalization, which is done in the linker.

Also if I read correctly your test-case, the symbol @foo isn't part of the comdat $foo?

Aliases are part of the same comdat as their aliasee. The test case seems valid to me.

I'd like to push to get the rename implemented. If we have an internal global with a comdat group, the frontend probably put it there for a good reason (the non-leader is probably metadata) and we shouldn't mess with it.

If we remove comdat from an internal global, it will become a GC root. So we will handle it and its metadata correctly, but less optimally.

---

Actually now that I think about it, we would still have the asan globals problem for vtables with external linkage. So I suspect that we may have to move all members of externally visible comdats to the merged module if any member needs to be moved. That is orthogonal to this change because we would still need to handle internal comdats, for example by dropping them, as this change is doing.

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

79

Definitely simpler. Are you ok with iterating all the globals again?

Fine with me, modulo this being the right place for the fix.

Also, did you want me to iterate over the symbols in ImportM as well (as per your "remove the comdats from both modules")?

I think the best place to do it is in a separate function, where this function is responsible for collecting and the other one is responsible for removing. Basically the caller would do something like this:

std::set<Comdat *> ComdatsToRemove;
promoteInternals(*MergedM, M, ModuleId, ComdatsToRemove);
promoteInternals(M, *MergedM, ModuleId, ComdatsToRemove);

removeInternalComdats(M, ComdatsToRemove);
removeInternalComdats(*MergedM, ComdatsToRemove);

[tejohnson]

In D31735#719730, @rnk wrote:

I hadn't considered that ThinLTO might try to import part of a comdat group, splitting the group. That seems like something we shouldn't do.

Note that this isn't ThinLTO importing. This is splitting the module into two pieces (in clang) for the purposes of CFI and devirtualization, where one piece needs to use regular LTO module merging and the other uses ThinLTO style compilation.

In D31735#719738, @pcc wrote:

Actually now that I think about it, we would still have the asan globals problem for vtables with external linkage. So I suspect that we may have to move all members of externally visible comdats to the merged module if any member needs to be moved. That is orthogonal to this change because we would still need to handle internal comdats, for example by dropping them, as this change is doing.

I'm not familiar with the asan globals problem specifically, but yes, splitting and then removing the comdat would cause an issue if the comdat also contains any values with external linkage.

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

79

Agree with pcc, a two pass solution is cleaner and more readable.

[inglorion]

@mehdi_amini: W.r.t. your question about verifying the requirements for comdats, this happens in Codegen/TargetLoweringObjectFileImpl.cpp for COFF, ELF, and Mach-O. They each have their own restrictions.

[inglorion]

two-pass implementation

[pcc]

Please add a test for the case where a comdat contains one member with !type metadata and another member without.

[inglorion]

also test the case where the comdat leader has !type metadata and the other member doesn't

[pcc]

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

98

And because globals not in comdats are GC roots.

182

This can just enumerate global_objects instead of checking that the global is a GlobalObject.

test/Transforms/ThinLTOBitcodeWriter/comdat.ll

8–9

This isn't checking for the correct syntax for comdats.

19

remove ; before :

35–41

This appears to be one comdat with a single member (the leader) with metadata and another where the leader has metadata and the non-leader doesn't. Please add a non-leader to the former and change the latter so that the non-leader has metadata and the leader doesn't.

Please also give the globals less confusing names and group them by comdat.

There should also be a negative test showing that we keep the comdat if no global has type metadata.

[inglorion]

I've implemented more of the suggestions (keeping comdats together, renaming instead of deleting comdats) in D31963. If that diff looks good to you guys, I would like to land that one instead of this one.

[pcc]

In D31735#724364, @inglorion wrote:

I've implemented more of the suggestions (keeping comdats together, renaming instead of deleting comdats) in D31963. If that diff looks good to you guys, I would like to land that one instead of this one.

Yes let's go with D31963, thanks for working on this!

lib/Transforms/IPO/ThinLTOBitcodeWriter.cpp

std::string getModuleId(Module *M) {
   SmallString<32> Str;
   MD5::stringifyResult(R, Str);
   return ("$" + Str).str();
 }
 
 // Promote each local-linkage entity defined by ExportM and used by ImportM by
 // changing visibility and appending the given ModuleId.
 void promoteInternals(Module &ExportM, Module &ImportM, StringRef ModuleId) {
+  DenseMap<StringRef, SmallVector<GlobalObject *, 1>> ComdatMap;
+  DenseSet<StringRef> ComdatsToDelete;
   for (auto &ExportGV : ExportM.global_values()) {
+    Comdat *C = ExportGV.getComdat();
+    if (C) {
+      if (auto *GO = dyn_cast<GlobalObject>(&ExportGV)) {
+        if (ComdatsToDelete.count(C->getName()))
+          GO->setComdat(nullptr);
+        else if (C->getName() != ExportGV.getName())
+          ComdatMap[C->getName()].push_back(GO);
+      }
+    }
+
     if (!ExportGV.hasLocalLinkage())
       continue;
 
-    GlobalValue *ImportGV = ImportM.getNamedValue(ExportGV.getName());
+    StringRef Name = ExportGV.getName();
+    GlobalValue *ImportGV = ImportM.getNamedValue(Name);
     if (!ImportGV || ImportGV->use_empty())
       continue;
 
-    std::string NewName = (ExportGV.getName() + ModuleId).str();
+    std::string NewName = (Name + ModuleId).str();
+
+    // COFF requires that every COMDAT contain a symbol with the same name
+    // as the COMDAT. If renaming this value would break that requirement,
+    // delete the COMDAT. This is safe, because this COMDAT is not going to
+    // be merged anyway.
+    if (C && C->getName() == Name) {
+      if (auto *GO = dyn_cast<GlobalObject>(&ExportGV))
+        GO->setComdat(nullptr);
+      ComdatsToDelete.insert(Name);
+      auto I = ComdatMap.find(Name);
+      if (I != ComdatMap.end())
+        for (auto &O : I->second)
+          O->setComdat(nullptr);
+    }
 
     ExportGV.setName(NewName);
     ExportGV.setLinkage(GlobalValue::ExternalLinkage);
     ExportGV.setVisibility(GlobalValue::HiddenVisibility);
 
     ImportGV->setName(NewName);
     ImportGV->setVisibility(GlobalValue::HiddenVisibility);
   }
+
+  auto &Comdats = ExportM.getComdatSymbolTable();
+  for (auto C : ComdatsToDelete)
+    Comdats.erase(C);
 }
 
 // Promote all internal (i.e. distinct) type ids used by the module by replacing
 // them with external type ids formed using the module id.
 //
 // Note that this needs to be done before we clone the module because each clone
 // will receive its own set of distinct metadata nodes.
 void promoteTypeIds(Module &M, StringRef ModuleId) {
for (auto MD : MDs) {
           LLVMContext::MD_type,
           *MDNode::get(M.getContext(),
                        ArrayRef<Metadata *>{MD->getOperand(0), I->second}));
     }
   }
 }
 
 // Drop unused globals, and drop type information from function declarations.
 // FIXME: If we made functions typeless then there would be no need to do this.
 void simplifyExternals(Module &M) {
   FunctionType *EmptyFT =
       FunctionType::get(Type::getVoidTy(M.getContext()), false);
 
   for (auto I = M.begin(), E = M.end(); I != E;) {
     Function &F = *I++;
     if (F.isDeclaration() && F.use_empty()) {
       F.eraseFromParent();

test/Transforms/ThinLTOBitcodeWriter/comdat.ll

+; RUN: opt -thinlto-bc -o %t %s
+; RUN: llvm-modextract -n 0 -o - %t | llvm-dis | FileCheck --check-prefix=CHECK0 %s
+; RUN: llvm-modextract -n 1 -o - %t | llvm-dis | FileCheck --check-prefix=CHECK1 %s
+
+; foo should have been renamed, and there should no longer be a comdat
+; with the original name.
+; CHECK0: {{@"?foo[^ ]+}} = external hidden global
+; CHECK1-NOT: $foo = comdat
+; CHECK1: {{@"?foo[^ ]+}} = hidden
+
+target datalayout = "e-m:w-i64:64-f80:128-n8:16:32:64-S128"
+target triple = "x86_64-pc-windows-msvc19.0.24215"
+
+$foo = comdat any
+
+@anon = private unnamed_addr constant { [1 x i8*] } { [1 x i8*] [i8* null] }, comdat($foo), !type !0
+
+@foo = internal unnamed_addr alias i8*, getelementptr inbounds ({ [1 x i8*] }, { [1 x i8*] }* @anon, i32 0, i32 0, i32 1)
+
+define i8* @bar() {
+  %1 = load i8*, i8** @foo
+  ret i8* %1
+}
+
+!0 = !{i64 8, !"?AVA@@"}