[JITLink][COFF] Handle duplicate external symbols.

[sunho]

Summary

Handles duplicate external symbols. This happens in few static libraries generaed from msvc toolchain.

[sgraenitz]

Is this happening on a regular basis? Any idea why it happens?

llvm/lib/ExecutionEngine/JITLink/COFFLinkGraphBuilder.cpp

229

Tracking all symbols names in new collection appears expensive. Could we check LinkGraph::external_symbols() instead?

[sunho]

@sgraenitz I'm not exactly sure what's going on but this happens a lot when I load up microsoft stl library (msvcp.lib, libcpmt.lib) which is needed to load static orc runtime. I can dig more into why this is happening.

For collection side, maybe we should change jitlink graph to store external symbols with DenseMap instead? We must iterate over the entire external_symobls() in order to check duplicate right now. (which sounded expensive for me) I always thought we should change it to densemap but didn't proceed on as it has been invalid for object file to list symbol twice.

[sunho]

The object file in the testcase is accepted without error by link.exe, so it seems to be allowed to list duplicate external symbols in MSVC.

[sunho]

Also, for densemap idea, we could clear up the old todo of changing stringref to symbolstringref in order to make it more efficient. (densemap with 64 bit integer key should be dead efficient)

[sunho]

I tried symbolstringptr idea but it needs larger changes, I have it in local I can submit it as another patch. Maybe make sense to keep as it is here for this patch?

[lhames]

LGTM.

llvm/lib/ExecutionEngine/JITLink/COFFLinkGraphBuilder.cpp

229

LinkGraph::external_symbols() is a vector at the moment -- it won't scale well if there are lots of duplicates. I wonder if LinkGraph should have a SmallDenseMap structure -- vector if/when it has <N elements, otherwise a DenseMap?

That's a problem for another patch though. I think it's fine for COFFLinkGraphBuilder to use a separate map while we're bringing COFF support up, and we can tune it later.

[lhames]

For collection side, maybe we should change jitlink graph to store external symbols with DenseMap instead? We must iterate over the entire external_symobls() in order to check duplicate right now. (which sounded expensive for me) I always thought we should change it to densemap but didn't proceed on as it has been invalid for object file to list symbol twice.

I totally missed that you had already identified this issue @sunho. Sorry! :)

llvm/lib/ExecutionEngine/JITLink/COFFLinkGraphBuilder.h

StringRef getCOFFSectionName(COFFSectionIndex SectionIndex,
                                object::COFFSymbolRef Sym);
 
   const object::COFFObjectFile &Obj;
   std::unique_ptr<LinkGraph> G;
 
   Section *CommonSection = nullptr;
   std::vector<Block *> GraphBlocks;
   std::vector<Symbol *> GraphSymbols;
+
+  DenseMap<StringRef, Symbol *> ExternalSymbols;
 };
 
 template <typename RelocHandlerFunction>
 Error COFFLinkGraphBuilder::forEachRelocation(const object::SectionRef &RelSec,
                                               RelocHandlerFunction &&Func,
                                               bool ProcessDebugSections) {
 
   auto COFFRelSect = Obj.getCOFFSection(RelSec);

llvm/lib/ExecutionEngine/JITLink/COFFLinkGraphBuilder.cpp

for (COFFSymbolIndex SymIndex = 0;
     else if (Sym->isUndefined()) {
       LLVM_DEBUG({
         dbgs() << "    " << SymIndex
                << ": Creating external graph symbol for COFF symbol \""
                << SymbolName << "\" in "
                << getCOFFSectionName(SectionIndex, Sec, *Sym)
                << " (index: " << SectionIndex << ") \n";
       });
-      GSym =
+      if (!ExternalSymbols.count(SymbolName))
+        ExternalSymbols[SymbolName] =
             &G->addExternalSymbol(SymbolName, Sym->getValue(), Linkage::Strong);
+      GSym = ExternalSymbols[SymbolName];
     } else if (Sym->isWeakExternal()) {
       COFFSymbolIndex TagIndex =
           Sym->getAux<object::coff_aux_weak_external>()->TagIndex;
       assert(Sym->getAux<object::coff_aux_weak_external>()->Characteristics !=
                  COFF::IMAGE_WEAK_EXTERN_SEARCH_NOLIBRARY &&
              "IMAGE_WEAK_EXTERN_SEARCH_NOLIBRARY is not supported.");
       assert(Sym->getAux<object::coff_aux_weak_external>()->Characteristics !=
                  COFF::IMAGE_WEAK_EXTERN_SEARCH_LIBRARY &&
LLVM_DEBUG({
     dbgs() << "      " << *Target << "\n";
   });
   PendingComdatExport = None;
   return Target;
 }
 
 } // namespace jitlink
 } // namespace llvm
 No newline at end of file

llvm/test/ExecutionEngine/JITLink/X86/COFF_duplicate_externals.test

+# REQUIRES: asserts
+# RUN: yaml2obj %s -o %t
+# RUN: llvm-jitlink -noexec -abs __ImageBase=0xfff00000 \
+# RUN: --debug-only=jitlink \
+# RUN: -slab-allocate 100Kb -slab-address 0xfff00000 -slab-page-size 4096 \
+# RUN: %t 2>&1 | FileCheck %s
+# 
+# Check duplicate undefined external symbols are handled correctly.
+#
+# CHECK: Creating graph symbols...
+# CHECK: 3: Creating external graph symbol for COFF symbol "func" in (external) (index: 0)
+# CHECK-NEXT: 4: Creating external graph symbol for COFF symbol "func" in (external) (index: 0)
+--- !COFF
+header:
+  Machine:         IMAGE_FILE_MACHINE_AMD64
+  Characteristics: [  ]
+sections:
+  - Name:            .text
+    Characteristics: [ IMAGE_SCN_CNT_CODE, IMAGE_SCN_MEM_EXECUTE, IMAGE_SCN_MEM_READ ]
+    Alignment:       16
+    SectionData:     '0000000000000000'
+symbols:
+  - Name:            .text
+    Value:           0
+    SectionNumber:   1
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_NULL
+    StorageClass:    IMAGE_SYM_CLASS_STATIC
+    SectionDefinition:
+      Length:          8
+      NumberOfRelocations: 0
+      CheckSum:            0
+      NumberOfLinenumbers: 0
+      Number:          1
+  - Name:            main
+    Value:           0
+    SectionNumber:   1
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_FUNCTION
+    StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
+  - Name:            func
+    Value:           0
+    SectionNumber:   0
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_FUNCTION
+    StorageClass:    IMAGE_SYM_CLASS_EXTERNAL
+  - Name:            func
+    Value:           0
+    SectionNumber:   0
+    SimpleType:      IMAGE_SYM_TYPE_NULL
+    ComplexType:     IMAGE_SYM_DTYPE_FUNCTION
+    StorageClass:    IMAGE_SYM_CLASS_EXTERNAL