[JITLink] Introduce WeakExternal linkage type.

[sunho]

Summary

Introduces WeakExternal linkage type to JITLink that looks up external definition before trying to use definition in current linkgraph.

In COFF, there is a notion of weak external symbol. The exact behaviour is defined as follwing in the spec: "If a definition of external symbol is linked, then an external reference to the symbol is resolved normally. If a definition of external symbol is not linked, then all references to the weak external for external symbol refer to stub symbol instead."

An aspect where it's inaccurate to use current Weak jitlink linkage type is that it does not eagerly looks for external definition, but everyone defines it blindly and the one defined earlier is used. So, in the testcase added in this patch, it will not look for definition in strong_def.yaml, thus linkgraph of strong_def.yaml will not even be emitted. WeakExternal linkage type gives a priority to external definition which solves this issue.

[lhames]

"If a definition of external symbol is linked, then an external reference to the symbol is resolved normally. If a definition of external symbol is not linked, then all references to the weak external for external symbol refer to stub symbol instead."

This is curious. Is it just a weaker weak? I.e. "Prefer another weak def if you have one, but use me as a last resort"? What happens if you have multiple instances of a symbol all tagged with this linkage? Does the linker just choose arbitrarily the same way that it would for a regular weak symbol? And how does this interact with COMDATs? Or is it never used on symbols in COMDAT sections?

If this behaves differently to "weak" or "strong" we'll need a new JITSymbolFlag for it too, and handling in the ORC symbol tables.

[sunho]

In D130449#3678079, @lhames wrote:

"If a definition of external symbol is linked, then an external reference to the symbol is resolved normally. If a definition of external symbol is not linked, then all references to the weak external for external symbol refer to stub symbol instead."

This is curious. Is it just a weaker weak? I.e. "Prefer another weak def if you have one, but use me as a last resort"? What happens if you have multiple instances of a symbol all tagged with this linkage? Does the linker just choose arbitrarily the same way that it would for a regular weak symbol? And how does this interact with COMDATs? Or is it never used on symbols in COMDAT sections?

If this behaves differently to "weak" or "strong" we'll need a new JITSymbolFlag for it too, and handling in the ORC symbol tables.

@lhames The way I understand this now is that the characteristics flag decide whether it will be exported to the external objects or not. For instance, if anything else than weak_alias flag is used it will be set "SF_undefined" in symbol list provided in libObject implementation. So, technically weak_alias is more similar to traditional weak symbol while other flags like search_library/no_library are "really weak."

For weak_alias case, it's fine to deal it with weak linkage type as they will be visible to the outside world and potentially crash with strong definition. But, for search_library and alternatename case, it will be not visible in symbol list cause SF_undefined flag is set or symbol is just not in symbol table. In this case, strong definition will not even be emitted so they don't get a chance to even crash with strong definition, or user provided definition is ignored.

For COMDATs, they are fine to be dealt with weak as they are always visible to external world AFAIK. There is one inaccuracy in how we're dealing with them -- strong + COMDAT any is duplicate definition error. But, I think that is fine.

[sunho]

This is the relevant part in libObject: https://github.com/llvm/llvm-project/blob/main/llvm/lib/Object/COFFObjectFile.cpp#L220

[lhames]

I just read up on the details here -- https://docs.microsoft.com/en-us/windows/win32/debug/pe-format#auxiliary-format-3-weak-externals. I was too focused on the Weak bit, not enough on the "External" bit. :)

@lhames The way I understand this now is that the characteristics flag decide whether it will be exported to the external objects or not. For instance, if anything else than weak_alias flag is used it will be set "SF_undefined" in symbol list provided in libObject implementation. So, technically weak_alias is more similar to traditional weak symbol while other flags like search_library/no_library are "really weak."

Let me see if I understand these modes:

weak_alias -- A weak extern with Characteristics == IMAGE_WEAK_EXTERN_SEARCH_ALIAS. Should be treated as a weak alias (we should introduce a proper alias concept into JITLink)
alternatename -- A weak extern with either Characteristics == IMAGE_WEAK_EXTERN_SEARCH_LIBRARY or Characteristics == IMAGE_WEAK_EXTERN_SEARCH_NOLIBRARY. Should be treated as a weak-ref of the external name, but transform into an alias for the alternatename if the external name is not found. The Characteristics determine whether the weak-ref should proceed into other libraries, or stay within the current one.

Does that sound right?

I think that we probably need new LinkGraph infrastructure for this, but I don't think a new LinkageType is the right approach. I suspect that we want to define symbol alias support, and encode this behavior into that. I'll wait to get confirmation from you about how I'm looking at this before I dig too much deeper though.

[sunho]

Copy pasting the message I sent eariler again here to make context clear:

I've confirmed a lot of behavior through toying with link.exe.
IMAGE_WEAK_EXTERN_SEARCH_NOLIBRARY:

• Impression: does not look up strong definitions from static libraries, but if a strong symbol from a static library was loaded by other means, it will use it. Strong definition inside input object files of executable was always honored – I believe this is because MSVC load all object files of executable by default
• Symbol is not visible to the outside; usually for importing functions that are to be used internally within an object file.
• Used a lot by msvc.

IMAGE_WEAK_EXTERN_SEARCH_LIBRARY:

• This one does look up strong definitions from static archives.
• I haven’t seen it used by both msvc and clang.

IMAGE_WEAK_EXTERN_SEARCH_ALIAS:

• Basically the same as IMAGE_WEAK_EXTERN_SEARCH_NOLIBRARY, but it is visible to outside.
• Used a lot by clang, never seem to be used by msvc.

Summing up, we can just use ordinary strong and weak linkage types except for IMAGE_WEAK_EXTERN_SEARCH_LIBRARY if we are not going to support alias to external symbol. (alias to external symbol is not used by both toolchains so far) I probably got confused by it always honoring strong def from object files of executable. For "force loading" object files of executable, this shouldn't be dealt inside jitlink at all. (probably inside llvm-jitllnk tool or ORC linkinglayer?)

Anyways, we definitely don't need this patch -- some part of it can be taken to implement search_library or executable object files behaviour though.

BTW, Lookup api might still be worth it even if we are not going to implement search_library. Relocations should reference symbols of other jitdylib only through dllimport stub. It makes sense to split lookup ranges.

llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h

 
 // Align a orc::ExecutorAddr to conform with block alignment requirements.
 inline orc::ExecutorAddr alignToBlock(orc::ExecutorAddr Addr, Block &B) {
   return orc::ExecutorAddr(alignToBlock(Addr.getValue(), B));
 }
 
 /// Describes symbol linkage. This can be used to make resolve definition
 /// clashes.
+///   Strong -- Error when symbol is already defined outside current linkgraph.
+///   Weak -- If symbol was defined before use that definition, otherwise
+///           uses this definition.
+///   WeakExternal -- If symbol was not defined before looks up a definition
+///                   outside current linkgraph. If symbol was still not
+///                   found, uses this definition.
+///
 enum class Linkage : uint8_t {
   Strong,
   Weak,
+  WeakExternal,
 };
 
 /// For errors and debugging output.
 const char *getLinkageName(Linkage L);
 
 /// Defines the scope in which this symbol should be visible:
 ///   Default -- Visible in the public interface of the linkage unit.
 ///   Hidden -- Visible within the linkage unit, but not exported from it.
public:
 
   /// Returns true if this Symbol has content (potentially) defined within this
   /// object file (i.e. is anything but an external or absolute symbol).
   bool isDefined() const {
     assert(Base && "Attempt to access null symbol");
     return Base->isDefined();
   }
 
+  /// Returns truw if this symbol has content defined wihthin this object file
+  /// but as a weak external stub.
+  bool isWeakExternal() const {
+    assert(Base && "Attempt to access null symbol");
+    return Base->isDefined() && getLinkage() == Linkage::WeakExternal;
+  }
+
   /// Returns true if this symbol is live (i.e. should be treated as a root for
   /// dead stripping).
   bool isLive() const {
     assert(Base && "Attempting to access null symbol");
     return IsLive;
   }
 
   /// Set this symbol's live bit.
   void setLive(bool IsLive) { this->IsLive = IsLive; }
 
-  /// Returns true is this symbol is callable.
+  /// Returns true if this symbol is callable.
   bool isCallable() const { return IsCallable; }
 
   /// Set this symbol's callable bit.
   void setCallable(bool IsCallable) { this->IsCallable = IsCallable; }
 
   /// Returns true if the underlying addressable is an unresolved external.
   bool isExternal() const {
     assert(Base && "Attempt to access null symbol");
void setOffset(orc::ExecutorAddrDiff NewOffset) {
     Offset = NewOffset;
   }
 
   static constexpr uint64_t MaxOffset = (1ULL << 59) - 1;
 
   // FIXME: A char* or SymbolStringPtr may pack better.
   StringRef Name;
   Addressable *Base = nullptr;
-  uint64_t Offset : 59;
-  uint64_t L : 1;
+  uint64_t Offset : 58;
+  uint64_t L : 2;
   uint64_t S : 2;
   uint64_t IsLive : 1;
   uint64_t IsCallable : 1;
   orc::ExecutorAddrDiff Size = 0;
 };
 
 raw_ostream &operator<<(raw_ostream &OS, const Symbol &A);
 

llvm/lib/ExecutionEngine/JITLink/COFFLinkGraphBuilder.cpp

if (auto *Target = getGraphSymbol(WeakExternal.Target)) {
 
       // FIXME: IMAGE_WEAK_EXTERN_SEARCH_NOLIBRARY and
       // IMAGE_WEAK_EXTERN_SEARCH_LIBRARY are handled in the same way.
       Scope S =
           WeakExternal.Characteristics == COFF::IMAGE_WEAK_EXTERN_SEARCH_ALIAS
               ? Scope::Default
               : Scope::Local;
 
-      auto NewSymbol =
-          createAliasSymbol(WeakExternal.SymbolName, Linkage::Weak, S, *Target);
+      auto NewSymbol = createAliasSymbol(WeakExternal.SymbolName,
+                                         Linkage::WeakExternal, S, *Target);
       if (!NewSymbol)
         return NewSymbol.takeError();
       setGraphSymbol(AliasSymbol->getSectionNumber(), WeakExternal.Alias,
                      **NewSymbol);
       LLVM_DEBUG({
         dbgs() << "    " << WeakExternal.Alias
                << ": Creating weak external symbol for COFF symbol \""
                << WeakExternal.SymbolName << "\" in section "
                << AliasSymbol->getSectionNumber() << "\n";
         dbgs() << "      " << **NewSymbol << "\n";
       });
     } else
       return make_error<JITLinkError>("Weak symbol alias requested but actual "
                                       "symbol not found for symbol " +
                                       formatv("{0:d}", WeakExternal.Alias));
   }
   return Error::success();
 }
 
 Error COFFLinkGraphBuilder::handleAlternateNames() {
-  // FIXME: Use proper alias
   for (auto &KeyValue : AlternateNames)
     if (DefinedSymbols.count(KeyValue.second) &&
         ExternalSymbols.count(KeyValue.first)) {
       auto *Target = DefinedSymbols[KeyValue.second];
       auto *Alias = ExternalSymbols[KeyValue.first];
       G->makeDefined(*Alias, Target->getBlock(), Target->getOffset(),
-                     Target->getSize(), Linkage::Weak, Scope::Local, false);
+                     Target->getSize(), Linkage::WeakExternal, Scope::Local,
+                     false);
     }
   return Error::success();
 }
 
 Symbol *COFFLinkGraphBuilder::createExternalSymbol(
     COFFSymbolIndex SymIndex, StringRef SymbolName,
     object::COFFSymbolRef Symbol, const object::coff_section *Section) {
   if (!ExternalSymbols.count(SymbolName))
COFFLinkGraphBuilder::exportCOMDATSymbol(COFFSymbolIndex SymIndex,
   });
   PendingComdatExport = None;
   DefinedSymbols[SymbolName] = Target;
   return Target;
 }
 
 } // namespace jitlink
 } // namespace llvm
 No newline at end of file

llvm/lib/ExecutionEngine/JITLink/JITLink.cpp

 }
 
 const char *getLinkageName(Linkage L) {
   switch (L) {
   case Linkage::Strong:
     return "strong";
   case Linkage::Weak:
     return "weak";
+  case Linkage::WeakExternal:
+    return "weakexternal";
   }
   llvm_unreachable("Unrecognized llvm.jitlink.Linkage enum");
 }
 
 const char *getScopeName(Scope S) {
   switch (S) {
   case Scope::Default:
     return "default";
return OS << B.getAddress() << " -- " << (B.getAddress() + B.getSize())
             << ", align-ofs = " << B.getAlignmentOffset()
             << ", section = " << B.getSection().getName();
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const Symbol &Sym) {
   OS << Sym.getAddress() << " (" << (Sym.isDefined() ? "block" : "addressable")
      << " + " << formatv("{0:x8}", Sym.getOffset())
      << "): size: " << formatv("{0:x8}", Sym.getSize())
-     << ", linkage: " << formatv("{0:6}", getLinkageName(Sym.getLinkage()))
+     << ", linkage: " << formatv("{0:12}", getLinkageName(Sym.getLinkage()))
      << ", scope: " << formatv("{0:8}", getScopeName(Sym.getScope())) << ", "
      << (Sym.isLive() ? "live" : "dead") << "  -   "
      << (Sym.hasName() ? Sym.getName() : "<anonymous symbol>");
   return OS;
 }
 
 void printEdge(raw_ostream &OS, const Block &B, const Edge &E,
                StringRef EdgeKindName) {

llvm/lib/ExecutionEngine/JITLink/JITLinkGeneric.cpp

JITLinkContext::LookupMap JITLinkerBase::getExternalSymbolNames() const {
   // Identify unresolved external symbols.
   JITLinkContext::LookupMap UnresolvedExternals;
   for (auto *Sym : G->external_symbols()) {
     assert(!Sym->getAddress() &&
            "External has already been assigned an address");
     assert(Sym->getName() != StringRef() && Sym->getName() != "" &&
            "Externals must be named");
     SymbolLookupFlags LookupFlags =
-        Sym->getLinkage() == Linkage::Weak
-            ? SymbolLookupFlags::WeaklyReferencedSymbol
-            : SymbolLookupFlags::RequiredSymbol;
+        Sym->getLinkage() == Linkage::Strong
+            ? SymbolLookupFlags::RequiredSymbol
+            : SymbolLookupFlags::WeaklyReferencedSymbol;
     UnresolvedExternals[Sym->getName()] = LookupFlags;
   }
+  for (auto *Sym : G->defined_symbols()) {
+    if (Sym->getLinkage() != Linkage::WeakExternal)
+      continue;
+    assert(Sym->getAddress() && "Weak external has no stub definition");
+    assert(Sym->getName() != StringRef() && Sym->getName() != "" &&
+           "Weak external must be named");
+    UnresolvedExternals[Sym->getName()] =
+        SymbolLookupFlags::WeaklyReferencedSymbol;
+  }
   return UnresolvedExternals;
 }
 
 void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
   for (auto *Sym : G->external_symbols()) {
     assert(Sym->getOffset() == 0 &&
            "External symbol is not at the start of its addressable block");
     assert(!Sym->getAddress() && "Symbol already resolved");
     assert(!Sym->isDefined() && "Symbol being resolved is already defined");
     auto ResultI = Result.find(Sym->getName());
     if (ResultI != Result.end())
       Sym->getAddressable().setAddress(
           orc::ExecutorAddr(ResultI->second.getAddress()));
     else
       assert(Sym->getLinkage() == Linkage::Weak &&
              "Failed to resolve non-weak reference");
   }
+  for (auto *Sym : G->defined_symbols()) {
+    if (Sym->getLinkage() != Linkage::WeakExternal)
+      continue;
+    auto ResultI = Result.find(Sym->getName());
+    if (ResultI != Result.end())
+      Sym->getAddressable().setAddress(
+          orc::ExecutorAddr(ResultI->second.getAddress()));
+  }
 
   LLVM_DEBUG({
     dbgs() << "Externals after applying lookup result:\n";
     for (auto *Sym : G->external_symbols())
       dbgs() << "  " << Sym->getName() << ": "
              << formatv("{0:x16}", Sym->getAddress().getValue()) << "\n";
+    for (auto *Sym : G->defined_symbols()) {
+      if (Sym->getLinkage() != Linkage::WeakExternal)
+        continue;
+      dbgs() << "  " << Sym->getName() << ": "
+             << formatv("{0:x16}", Sym->getAddress().getValue()) << "\n";
+    }
   });
 }
 
 void JITLinkerBase::abandonAllocAndBailOut(std::unique_ptr<JITLinkerBase> Self,
                                            Error Err) {
   assert(Err && "Should not be bailing out on success value");
   assert(Alloc && "can not call abandonAllocAndBailOut before allocation");
   Alloc->abandon([S = std::move(Self), E1 = std::move(Err)](Error E2) mutable {

llvm/test/ExecutionEngine/JITLink/X86/COFF_weak_external.s

 # REQUIRES: asserts
 # RUN: llvm-mc -filetype=obj -triple=x86_64-windows-msvc %s -o %t
 # RUN: llvm-jitlink -abs var=0xcafef00d --debug-only=jitlink -noexec %t 2>&1 | FileCheck %s
 #
 # Check a default symbol is aliased as a weak external symbol.
 #
 # CHECK: Creating graph symbols...
 # CHECK:      8: Creating defined graph symbol for COFF symbol ".weak.func.default.main" in .text (index: 1)
 # CHECK-NEXT:   0x0 (block + 0x00000000): size: 0x00000000, linkage: strong, scope: default, dead  -   .weak.func.default.main 
 # CHECK-NEXT: 9: Creating defined graph symbol for COFF symbol "main" in .text (index: 1)
 # CHECK-NEXT:   0x10 (block + 0x00000010): size: 0x00000000, linkage: strong, scope: default, dead  -   main
 # CHECK-NEXT: 6: Creating weak external symbol for COFF symbol "func" in section 0
-# CHECK-NEXT:   0x0 (block + 0x00000000): size: 0x00000000, linkage: weak, scope: default, dead  -   func
+# CHECK-NEXT:   0x0 (block + 0x00000000): size: 0x00000000, linkage: weakexternal, scope: default, dead  -   func
 
   .text
 
   .def  func;
   .scl  2;
   .type 32;
   .endef
   .weak func

llvm/test/ExecutionEngine/JITLink/X86/COFF_weak_external_multiple_defs.s

+# RUN: rm -rf %t && mkdir -p %t
+# RUN: yaml2obj %S/Inputs/COFF_strong_def.yaml -o %t/COFF_strong.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64-windows-msvc %s -o %t/COFF_main.o
+# RUN: llvm-jitlink --debug-only=jitlink -slab-allocate 100Kb -slab-address 0xfff00000 -slab-page-size 4096 \
+# RUN: -show-graph -noexec %t/COFF_strong.o %t/COFF_main.o 2>&1 | FileCheck %s
+#
+# Check symbol with weakalias linkage type uses the external definition 
+# from COFF_strong_def.yaml.
+#
+# CHECK: Link graph "{{.*}}COFF_strong.o" before post-allocation passes:
+# CHECK-NEXT: section strongfunc:
+# CHECK-EMPTY:
+# CHECK-NEXT: block 0xfff01000 size = 0x00000001, align = 16, alignment-offset = 0
+# CHECK-NEXT: symbols:
+# CHECK-NEXT: 0xfff01000 (block + 0x00000000): size: 0x00000001, linkage: strong, scope: default, live  -   func
+# CHECK: Externals after applying lookup result:
+# CHECK-NEXT: func: 0x00000000fff01000
+
+  .text
+  
+  .def   func_def;
+  .scl  2;
+  .type 32;
+  .endef
+  .globl  func_def
+  .p2align  4, 0x90
+func_def:
+  retq
+
+  .def  main;
+  .scl  2;
+  .type 32;
+  .endef
+  .globl  main
+  .p2align  4, 0x90
+main:
+  callq func
+  retq
+
+.section .drectve,"yn"
+.ascii "/alternatename:func=func_def"