xref: /freebsd-src/contrib/llvm-project/llvm/lib/ExecutionEngine/JITLink/COFFLinkGraphBuilder.cpp (revision bdd1243df58e60e85101c09001d9812a789b6bc4)
1753f127fSDimitry Andric //=--------- COFFLinkGraphBuilder.cpp - COFF LinkGraph builder ----------===//
2753f127fSDimitry Andric //
3753f127fSDimitry Andric // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4753f127fSDimitry Andric // See https://llvm.org/LICENSE.txt for license information.
5753f127fSDimitry Andric // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6753f127fSDimitry Andric //
7753f127fSDimitry Andric //===----------------------------------------------------------------------===//
8753f127fSDimitry Andric //
9753f127fSDimitry Andric // Generic COFF LinkGraph buliding code.
10753f127fSDimitry Andric //
11753f127fSDimitry Andric //===----------------------------------------------------------------------===//
12753f127fSDimitry Andric #include "COFFLinkGraphBuilder.h"
13753f127fSDimitry Andric 
14753f127fSDimitry Andric #define DEBUG_TYPE "jitlink"
15753f127fSDimitry Andric 
16753f127fSDimitry Andric static const char *CommonSectionName = "__common";
17753f127fSDimitry Andric 
18753f127fSDimitry Andric namespace llvm {
19753f127fSDimitry Andric namespace jitlink {
20753f127fSDimitry Andric 
21972a253aSDimitry Andric static Triple createTripleWithCOFFFormat(Triple T) {
22972a253aSDimitry Andric   T.setObjectFormat(Triple::COFF);
23972a253aSDimitry Andric   return T;
24972a253aSDimitry Andric }
25972a253aSDimitry Andric 
26753f127fSDimitry Andric COFFLinkGraphBuilder::COFFLinkGraphBuilder(
27753f127fSDimitry Andric     const object::COFFObjectFile &Obj, Triple TT,
28753f127fSDimitry Andric     LinkGraph::GetEdgeKindNameFunction GetEdgeKindName)
29753f127fSDimitry Andric     : Obj(Obj),
30972a253aSDimitry Andric       G(std::make_unique<LinkGraph>(Obj.getFileName().str(),
31972a253aSDimitry Andric                                     createTripleWithCOFFFormat(TT),
32972a253aSDimitry Andric                                     getPointerSize(Obj), getEndianness(Obj),
33972a253aSDimitry Andric                                     std::move(GetEdgeKindName))) {
34753f127fSDimitry Andric   LLVM_DEBUG({
35753f127fSDimitry Andric     dbgs() << "Created COFFLinkGraphBuilder for \"" << Obj.getFileName()
36753f127fSDimitry Andric            << "\"\n";
37753f127fSDimitry Andric   });
38753f127fSDimitry Andric }
39753f127fSDimitry Andric 
40753f127fSDimitry Andric COFFLinkGraphBuilder::~COFFLinkGraphBuilder() = default;
41753f127fSDimitry Andric 
42753f127fSDimitry Andric unsigned
43753f127fSDimitry Andric COFFLinkGraphBuilder::getPointerSize(const object::COFFObjectFile &Obj) {
44753f127fSDimitry Andric   return Obj.getBytesInAddress();
45753f127fSDimitry Andric }
46753f127fSDimitry Andric 
47753f127fSDimitry Andric support::endianness
48753f127fSDimitry Andric COFFLinkGraphBuilder::getEndianness(const object::COFFObjectFile &Obj) {
49753f127fSDimitry Andric   return Obj.isLittleEndian() ? support::little : support::big;
50753f127fSDimitry Andric }
51753f127fSDimitry Andric 
52753f127fSDimitry Andric uint64_t COFFLinkGraphBuilder::getSectionSize(const object::COFFObjectFile &Obj,
53753f127fSDimitry Andric                                               const object::coff_section *Sec) {
54753f127fSDimitry Andric   // Consider the difference between executable form and object form.
55753f127fSDimitry Andric   // More information is inside COFFObjectFile::getSectionSize
56753f127fSDimitry Andric   if (Obj.getDOSHeader())
57753f127fSDimitry Andric     return std::min(Sec->VirtualSize, Sec->SizeOfRawData);
58753f127fSDimitry Andric   return Sec->SizeOfRawData;
59753f127fSDimitry Andric }
60753f127fSDimitry Andric 
61753f127fSDimitry Andric uint64_t
62753f127fSDimitry Andric COFFLinkGraphBuilder::getSectionAddress(const object::COFFObjectFile &Obj,
63753f127fSDimitry Andric                                         const object::coff_section *Section) {
64753f127fSDimitry Andric   return Section->VirtualAddress + Obj.getImageBase();
65753f127fSDimitry Andric }
66753f127fSDimitry Andric 
67753f127fSDimitry Andric bool COFFLinkGraphBuilder::isComdatSection(
68753f127fSDimitry Andric     const object::coff_section *Section) {
69753f127fSDimitry Andric   return Section->Characteristics & COFF::IMAGE_SCN_LNK_COMDAT;
70753f127fSDimitry Andric }
71753f127fSDimitry Andric 
72753f127fSDimitry Andric Section &COFFLinkGraphBuilder::getCommonSection() {
73753f127fSDimitry Andric   if (!CommonSection)
74*bdd1243dSDimitry Andric     CommonSection = &G->createSection(CommonSectionName,
75*bdd1243dSDimitry Andric                                       orc::MemProt::Read | orc::MemProt::Write);
76753f127fSDimitry Andric   return *CommonSection;
77753f127fSDimitry Andric }
78753f127fSDimitry Andric 
79753f127fSDimitry Andric Expected<std::unique_ptr<LinkGraph>> COFFLinkGraphBuilder::buildGraph() {
80753f127fSDimitry Andric   if (!Obj.isRelocatableObject())
81753f127fSDimitry Andric     return make_error<JITLinkError>("Object is not a relocatable COFF file");
82753f127fSDimitry Andric 
83753f127fSDimitry Andric   if (auto Err = graphifySections())
84753f127fSDimitry Andric     return std::move(Err);
85753f127fSDimitry Andric 
86753f127fSDimitry Andric   if (auto Err = graphifySymbols())
87753f127fSDimitry Andric     return std::move(Err);
88753f127fSDimitry Andric 
89753f127fSDimitry Andric   if (auto Err = addRelocations())
90753f127fSDimitry Andric     return std::move(Err);
91753f127fSDimitry Andric 
92753f127fSDimitry Andric   return std::move(G);
93753f127fSDimitry Andric }
94753f127fSDimitry Andric 
95753f127fSDimitry Andric StringRef
96753f127fSDimitry Andric COFFLinkGraphBuilder::getCOFFSectionName(COFFSectionIndex SectionIndex,
97753f127fSDimitry Andric                                          const object::coff_section *Sec,
98753f127fSDimitry Andric                                          object::COFFSymbolRef Sym) {
99753f127fSDimitry Andric   switch (SectionIndex) {
100753f127fSDimitry Andric   case COFF::IMAGE_SYM_UNDEFINED: {
101753f127fSDimitry Andric     if (Sym.getValue())
102753f127fSDimitry Andric       return "(common)";
103753f127fSDimitry Andric     else
104753f127fSDimitry Andric       return "(external)";
105753f127fSDimitry Andric   }
106753f127fSDimitry Andric   case COFF::IMAGE_SYM_ABSOLUTE:
107753f127fSDimitry Andric     return "(absolute)";
108753f127fSDimitry Andric   case COFF::IMAGE_SYM_DEBUG: {
109753f127fSDimitry Andric     // Used with .file symbol
110753f127fSDimitry Andric     return "(debug)";
111753f127fSDimitry Andric   }
112753f127fSDimitry Andric   default: {
113753f127fSDimitry Andric     // Non reserved regular section numbers
114753f127fSDimitry Andric     if (Expected<StringRef> SecNameOrErr = Obj.getSectionName(Sec))
115753f127fSDimitry Andric       return *SecNameOrErr;
116753f127fSDimitry Andric   }
117753f127fSDimitry Andric   }
118753f127fSDimitry Andric   return "";
119753f127fSDimitry Andric }
120753f127fSDimitry Andric 
121753f127fSDimitry Andric Error COFFLinkGraphBuilder::graphifySections() {
122753f127fSDimitry Andric   LLVM_DEBUG(dbgs() << "  Creating graph sections...\n");
123753f127fSDimitry Andric 
124753f127fSDimitry Andric   GraphBlocks.resize(Obj.getNumberOfSections() + 1);
125753f127fSDimitry Andric   // For each section...
126753f127fSDimitry Andric   for (COFFSectionIndex SecIndex = 1;
127753f127fSDimitry Andric        SecIndex <= static_cast<COFFSectionIndex>(Obj.getNumberOfSections());
128753f127fSDimitry Andric        SecIndex++) {
129753f127fSDimitry Andric     Expected<const object::coff_section *> Sec = Obj.getSection(SecIndex);
130753f127fSDimitry Andric     if (!Sec)
131753f127fSDimitry Andric       return Sec.takeError();
132753f127fSDimitry Andric 
133753f127fSDimitry Andric     StringRef SectionName;
134753f127fSDimitry Andric     if (Expected<StringRef> SecNameOrErr = Obj.getSectionName(*Sec))
135753f127fSDimitry Andric       SectionName = *SecNameOrErr;
136753f127fSDimitry Andric 
137753f127fSDimitry Andric     // FIXME: Skip debug info sections
138753f127fSDimitry Andric 
139753f127fSDimitry Andric     LLVM_DEBUG({
140753f127fSDimitry Andric       dbgs() << "    "
141753f127fSDimitry Andric              << "Creating section for \"" << SectionName << "\"\n";
142753f127fSDimitry Andric     });
143753f127fSDimitry Andric 
144753f127fSDimitry Andric     // Get the section's memory protection flags.
145*bdd1243dSDimitry Andric     orc::MemProt Prot = orc::MemProt::Read;
146753f127fSDimitry Andric     if ((*Sec)->Characteristics & COFF::IMAGE_SCN_MEM_EXECUTE)
147*bdd1243dSDimitry Andric       Prot |= orc::MemProt::Exec;
148753f127fSDimitry Andric     if ((*Sec)->Characteristics & COFF::IMAGE_SCN_MEM_READ)
149*bdd1243dSDimitry Andric       Prot |= orc::MemProt::Read;
150753f127fSDimitry Andric     if ((*Sec)->Characteristics & COFF::IMAGE_SCN_MEM_WRITE)
151*bdd1243dSDimitry Andric       Prot |= orc::MemProt::Write;
152753f127fSDimitry Andric 
153753f127fSDimitry Andric     // Look for existing sections first.
154753f127fSDimitry Andric     auto *GraphSec = G->findSectionByName(SectionName);
155753f127fSDimitry Andric     if (!GraphSec)
156753f127fSDimitry Andric       GraphSec = &G->createSection(SectionName, Prot);
157753f127fSDimitry Andric     if (GraphSec->getMemProt() != Prot)
158753f127fSDimitry Andric       return make_error<JITLinkError>("MemProt should match");
159753f127fSDimitry Andric 
160753f127fSDimitry Andric     Block *B = nullptr;
161753f127fSDimitry Andric     if ((*Sec)->Characteristics & COFF::IMAGE_SCN_CNT_UNINITIALIZED_DATA)
162753f127fSDimitry Andric       B = &G->createZeroFillBlock(
163753f127fSDimitry Andric           *GraphSec, getSectionSize(Obj, *Sec),
164753f127fSDimitry Andric           orc::ExecutorAddr(getSectionAddress(Obj, *Sec)),
165753f127fSDimitry Andric           (*Sec)->getAlignment(), 0);
166753f127fSDimitry Andric     else {
167753f127fSDimitry Andric       ArrayRef<uint8_t> Data;
168753f127fSDimitry Andric       if (auto Err = Obj.getSectionContents(*Sec, Data))
169753f127fSDimitry Andric         return Err;
170753f127fSDimitry Andric 
171*bdd1243dSDimitry Andric       auto CharData = ArrayRef<char>(
172*bdd1243dSDimitry Andric           reinterpret_cast<const char *>(Data.data()), Data.size());
173*bdd1243dSDimitry Andric 
174*bdd1243dSDimitry Andric       if (SectionName == getDirectiveSectionName())
175*bdd1243dSDimitry Andric         if (auto Err = handleDirectiveSection(
176*bdd1243dSDimitry Andric                 StringRef(CharData.data(), CharData.size())))
177*bdd1243dSDimitry Andric           return Err;
178*bdd1243dSDimitry Andric 
179753f127fSDimitry Andric       B = &G->createContentBlock(
180*bdd1243dSDimitry Andric           *GraphSec, CharData, orc::ExecutorAddr(getSectionAddress(Obj, *Sec)),
181753f127fSDimitry Andric           (*Sec)->getAlignment(), 0);
182753f127fSDimitry Andric     }
183753f127fSDimitry Andric 
184753f127fSDimitry Andric     setGraphBlock(SecIndex, B);
185753f127fSDimitry Andric   }
186753f127fSDimitry Andric 
187753f127fSDimitry Andric   return Error::success();
188753f127fSDimitry Andric }
189753f127fSDimitry Andric 
190753f127fSDimitry Andric Error COFFLinkGraphBuilder::graphifySymbols() {
191753f127fSDimitry Andric   LLVM_DEBUG(dbgs() << "  Creating graph symbols...\n");
192753f127fSDimitry Andric 
193753f127fSDimitry Andric   SymbolSets.resize(Obj.getNumberOfSections() + 1);
194972a253aSDimitry Andric   PendingComdatExports.resize(Obj.getNumberOfSections() + 1);
195753f127fSDimitry Andric   GraphSymbols.resize(Obj.getNumberOfSymbols());
196753f127fSDimitry Andric 
197753f127fSDimitry Andric   for (COFFSymbolIndex SymIndex = 0;
198753f127fSDimitry Andric        SymIndex < static_cast<COFFSymbolIndex>(Obj.getNumberOfSymbols());
199753f127fSDimitry Andric        SymIndex++) {
200753f127fSDimitry Andric     Expected<object::COFFSymbolRef> Sym = Obj.getSymbol(SymIndex);
201753f127fSDimitry Andric     if (!Sym)
202753f127fSDimitry Andric       return Sym.takeError();
203753f127fSDimitry Andric 
204753f127fSDimitry Andric     StringRef SymbolName;
205753f127fSDimitry Andric     if (Expected<StringRef> SymNameOrErr = Obj.getSymbolName(*Sym))
206753f127fSDimitry Andric       SymbolName = *SymNameOrErr;
207753f127fSDimitry Andric 
208753f127fSDimitry Andric     COFFSectionIndex SectionIndex = Sym->getSectionNumber();
209753f127fSDimitry Andric     const object::coff_section *Sec = nullptr;
210753f127fSDimitry Andric 
211753f127fSDimitry Andric     if (!COFF::isReservedSectionNumber(SectionIndex)) {
212753f127fSDimitry Andric       auto SecOrErr = Obj.getSection(SectionIndex);
213753f127fSDimitry Andric       if (!SecOrErr)
214753f127fSDimitry Andric         return make_error<JITLinkError>(
215753f127fSDimitry Andric             "Invalid COFF section number:" + formatv("{0:d}: ", SectionIndex) +
216753f127fSDimitry Andric             " (" + toString(SecOrErr.takeError()) + ")");
217753f127fSDimitry Andric       Sec = *SecOrErr;
218753f127fSDimitry Andric     }
219753f127fSDimitry Andric 
220753f127fSDimitry Andric     // Create jitlink symbol
221753f127fSDimitry Andric     jitlink::Symbol *GSym = nullptr;
222753f127fSDimitry Andric     if (Sym->isFileRecord())
223753f127fSDimitry Andric       LLVM_DEBUG({
224753f127fSDimitry Andric         dbgs() << "    " << SymIndex << ": Skipping FileRecord symbol \""
225753f127fSDimitry Andric                << SymbolName << "\" in "
226753f127fSDimitry Andric                << getCOFFSectionName(SectionIndex, Sec, *Sym)
227753f127fSDimitry Andric                << " (index: " << SectionIndex << ") \n";
228753f127fSDimitry Andric       });
229753f127fSDimitry Andric     else if (Sym->isUndefined()) {
230*bdd1243dSDimitry Andric       GSym = createExternalSymbol(SymIndex, SymbolName, *Sym, Sec);
231753f127fSDimitry Andric     } else if (Sym->isWeakExternal()) {
232972a253aSDimitry Andric       auto *WeakExternal = Sym->getAux<object::coff_aux_weak_external>();
233972a253aSDimitry Andric       COFFSymbolIndex TagIndex = WeakExternal->TagIndex;
234972a253aSDimitry Andric       uint32_t Characteristics = WeakExternal->Characteristics;
235972a253aSDimitry Andric       WeakExternalRequests.push_back(
236972a253aSDimitry Andric           {SymIndex, TagIndex, Characteristics, SymbolName});
237753f127fSDimitry Andric     } else {
238753f127fSDimitry Andric       Expected<jitlink::Symbol *> NewGSym =
239753f127fSDimitry Andric           createDefinedSymbol(SymIndex, SymbolName, *Sym, Sec);
240753f127fSDimitry Andric       if (!NewGSym)
241753f127fSDimitry Andric         return NewGSym.takeError();
242753f127fSDimitry Andric       GSym = *NewGSym;
243753f127fSDimitry Andric       if (GSym) {
244753f127fSDimitry Andric         LLVM_DEBUG({
245753f127fSDimitry Andric           dbgs() << "    " << SymIndex
246753f127fSDimitry Andric                  << ": Creating defined graph symbol for COFF symbol \""
247753f127fSDimitry Andric                  << SymbolName << "\" in "
248753f127fSDimitry Andric                  << getCOFFSectionName(SectionIndex, Sec, *Sym)
249753f127fSDimitry Andric                  << " (index: " << SectionIndex << ") \n";
250753f127fSDimitry Andric           dbgs() << "      " << *GSym << "\n";
251753f127fSDimitry Andric         });
252753f127fSDimitry Andric       }
253753f127fSDimitry Andric     }
254753f127fSDimitry Andric 
255753f127fSDimitry Andric     // Register the symbol
256753f127fSDimitry Andric     if (GSym)
257753f127fSDimitry Andric       setGraphSymbol(SectionIndex, SymIndex, *GSym);
258753f127fSDimitry Andric     SymIndex += Sym->getNumberOfAuxSymbols();
259753f127fSDimitry Andric   }
260753f127fSDimitry Andric 
261753f127fSDimitry Andric   if (auto Err = flushWeakAliasRequests())
262753f127fSDimitry Andric     return Err;
263753f127fSDimitry Andric 
264*bdd1243dSDimitry Andric   if (auto Err = handleAlternateNames())
265*bdd1243dSDimitry Andric     return Err;
266*bdd1243dSDimitry Andric 
267753f127fSDimitry Andric   if (auto Err = calculateImplicitSizeOfSymbols())
268753f127fSDimitry Andric     return Err;
269753f127fSDimitry Andric 
270753f127fSDimitry Andric   return Error::success();
271753f127fSDimitry Andric }
272753f127fSDimitry Andric 
273*bdd1243dSDimitry Andric Error COFFLinkGraphBuilder::handleDirectiveSection(StringRef Str) {
274*bdd1243dSDimitry Andric   auto Parsed = DirectiveParser.parse(Str);
275*bdd1243dSDimitry Andric   if (!Parsed)
276*bdd1243dSDimitry Andric     return Parsed.takeError();
277*bdd1243dSDimitry Andric   for (auto *Arg : *Parsed) {
278*bdd1243dSDimitry Andric     StringRef S = Arg->getValue();
279*bdd1243dSDimitry Andric     switch (Arg->getOption().getID()) {
280*bdd1243dSDimitry Andric     case COFF_OPT_alternatename: {
281*bdd1243dSDimitry Andric       StringRef From, To;
282*bdd1243dSDimitry Andric       std::tie(From, To) = S.split('=');
283*bdd1243dSDimitry Andric       if (From.empty() || To.empty())
284*bdd1243dSDimitry Andric         return make_error<JITLinkError>(
285*bdd1243dSDimitry Andric             "Invalid COFF /alternatename directive");
286*bdd1243dSDimitry Andric       AlternateNames[From] = To;
287*bdd1243dSDimitry Andric       break;
288*bdd1243dSDimitry Andric     }
289*bdd1243dSDimitry Andric     case COFF_OPT_incl: {
290*bdd1243dSDimitry Andric       auto DataCopy = G->allocateString(S);
291*bdd1243dSDimitry Andric       StringRef StrCopy(DataCopy.data(), DataCopy.size());
292*bdd1243dSDimitry Andric       ExternalSymbols[StrCopy] = &G->addExternalSymbol(StrCopy, 0, false);
293*bdd1243dSDimitry Andric       ExternalSymbols[StrCopy]->setLive(true);
294*bdd1243dSDimitry Andric       break;
295*bdd1243dSDimitry Andric     }
296*bdd1243dSDimitry Andric     case COFF_OPT_export:
297*bdd1243dSDimitry Andric       break;
298*bdd1243dSDimitry Andric     default: {
299*bdd1243dSDimitry Andric       LLVM_DEBUG({
300*bdd1243dSDimitry Andric         dbgs() << "Unknown coff directive: " << Arg->getSpelling() << "\n";
301*bdd1243dSDimitry Andric       });
302*bdd1243dSDimitry Andric       break;
303*bdd1243dSDimitry Andric     }
304*bdd1243dSDimitry Andric     }
305*bdd1243dSDimitry Andric   }
306*bdd1243dSDimitry Andric   return Error::success();
307*bdd1243dSDimitry Andric }
308*bdd1243dSDimitry Andric 
309753f127fSDimitry Andric Error COFFLinkGraphBuilder::flushWeakAliasRequests() {
310753f127fSDimitry Andric   // Export the weak external symbols and alias it
311972a253aSDimitry Andric   for (auto &WeakExternal : WeakExternalRequests) {
312972a253aSDimitry Andric     if (auto *Target = getGraphSymbol(WeakExternal.Target)) {
313753f127fSDimitry Andric       Expected<object::COFFSymbolRef> AliasSymbol =
314972a253aSDimitry Andric           Obj.getSymbol(WeakExternal.Alias);
315753f127fSDimitry Andric       if (!AliasSymbol)
316753f127fSDimitry Andric         return AliasSymbol.takeError();
317753f127fSDimitry Andric 
318972a253aSDimitry Andric       // FIXME: IMAGE_WEAK_EXTERN_SEARCH_NOLIBRARY and
319972a253aSDimitry Andric       // IMAGE_WEAK_EXTERN_SEARCH_LIBRARY are handled in the same way.
320972a253aSDimitry Andric       Scope S =
321972a253aSDimitry Andric           WeakExternal.Characteristics == COFF::IMAGE_WEAK_EXTERN_SEARCH_ALIAS
322972a253aSDimitry Andric               ? Scope::Default
323972a253aSDimitry Andric               : Scope::Local;
324972a253aSDimitry Andric 
325*bdd1243dSDimitry Andric       auto NewSymbol =
326*bdd1243dSDimitry Andric           createAliasSymbol(WeakExternal.SymbolName, Linkage::Weak, S, *Target);
327*bdd1243dSDimitry Andric       if (!NewSymbol)
328*bdd1243dSDimitry Andric         return NewSymbol.takeError();
329972a253aSDimitry Andric       setGraphSymbol(AliasSymbol->getSectionNumber(), WeakExternal.Alias,
330*bdd1243dSDimitry Andric                      **NewSymbol);
331753f127fSDimitry Andric       LLVM_DEBUG({
332972a253aSDimitry Andric         dbgs() << "    " << WeakExternal.Alias
333753f127fSDimitry Andric                << ": Creating weak external symbol for COFF symbol \""
334972a253aSDimitry Andric                << WeakExternal.SymbolName << "\" in section "
335753f127fSDimitry Andric                << AliasSymbol->getSectionNumber() << "\n";
336*bdd1243dSDimitry Andric         dbgs() << "      " << **NewSymbol << "\n";
337753f127fSDimitry Andric       });
338753f127fSDimitry Andric     } else
339753f127fSDimitry Andric       return make_error<JITLinkError>("Weak symbol alias requested but actual "
340753f127fSDimitry Andric                                       "symbol not found for symbol " +
341972a253aSDimitry Andric                                       formatv("{0:d}", WeakExternal.Alias));
342753f127fSDimitry Andric   }
343753f127fSDimitry Andric   return Error::success();
344753f127fSDimitry Andric }
345753f127fSDimitry Andric 
346*bdd1243dSDimitry Andric Error COFFLinkGraphBuilder::handleAlternateNames() {
347*bdd1243dSDimitry Andric   for (auto &KeyValue : AlternateNames)
348*bdd1243dSDimitry Andric     if (DefinedSymbols.count(KeyValue.second) &&
349*bdd1243dSDimitry Andric         ExternalSymbols.count(KeyValue.first)) {
350*bdd1243dSDimitry Andric       auto *Target = DefinedSymbols[KeyValue.second];
351*bdd1243dSDimitry Andric       auto *Alias = ExternalSymbols[KeyValue.first];
352*bdd1243dSDimitry Andric       G->makeDefined(*Alias, Target->getBlock(), Target->getOffset(),
353*bdd1243dSDimitry Andric                      Target->getSize(), Linkage::Weak, Scope::Local, false);
354*bdd1243dSDimitry Andric     }
355*bdd1243dSDimitry Andric   return Error::success();
356*bdd1243dSDimitry Andric }
357*bdd1243dSDimitry Andric 
358*bdd1243dSDimitry Andric Symbol *COFFLinkGraphBuilder::createExternalSymbol(
359*bdd1243dSDimitry Andric     COFFSymbolIndex SymIndex, StringRef SymbolName,
360*bdd1243dSDimitry Andric     object::COFFSymbolRef Symbol, const object::coff_section *Section) {
361*bdd1243dSDimitry Andric   if (!ExternalSymbols.count(SymbolName))
362*bdd1243dSDimitry Andric     ExternalSymbols[SymbolName] =
363*bdd1243dSDimitry Andric         &G->addExternalSymbol(SymbolName, Symbol.getValue(), false);
364*bdd1243dSDimitry Andric 
365*bdd1243dSDimitry Andric   LLVM_DEBUG({
366*bdd1243dSDimitry Andric     dbgs() << "    " << SymIndex
367*bdd1243dSDimitry Andric            << ": Creating external graph symbol for COFF symbol \""
368*bdd1243dSDimitry Andric            << SymbolName << "\" in "
369*bdd1243dSDimitry Andric            << getCOFFSectionName(Symbol.getSectionNumber(), Section, Symbol)
370*bdd1243dSDimitry Andric            << " (index: " << Symbol.getSectionNumber() << ") \n";
371*bdd1243dSDimitry Andric   });
372*bdd1243dSDimitry Andric   return ExternalSymbols[SymbolName];
373*bdd1243dSDimitry Andric }
374*bdd1243dSDimitry Andric 
375*bdd1243dSDimitry Andric Expected<Symbol *> COFFLinkGraphBuilder::createAliasSymbol(StringRef SymbolName,
376*bdd1243dSDimitry Andric                                                            Linkage L, Scope S,
377*bdd1243dSDimitry Andric                                                            Symbol &Target) {
378*bdd1243dSDimitry Andric   if (!Target.isDefined()) {
379*bdd1243dSDimitry Andric     // FIXME: Support this when there's a way to handle this.
380*bdd1243dSDimitry Andric     return make_error<JITLinkError>("Weak external symbol with external "
381*bdd1243dSDimitry Andric                                     "symbol as alternative not supported.");
382*bdd1243dSDimitry Andric   }
383*bdd1243dSDimitry Andric   return &G->addDefinedSymbol(Target.getBlock(), Target.getOffset(), SymbolName,
384*bdd1243dSDimitry Andric                               Target.getSize(), L, S, Target.isCallable(),
385*bdd1243dSDimitry Andric                               false);
386*bdd1243dSDimitry Andric }
387*bdd1243dSDimitry Andric 
388753f127fSDimitry Andric // In COFF, most of the defined symbols don't contain the size information.
389753f127fSDimitry Andric // Hence, we calculate the "implicit" size of symbol by taking the delta of
390753f127fSDimitry Andric // offsets of consecutive symbols within a block. We maintain a balanced tree
391753f127fSDimitry Andric // set of symbols sorted by offset per each block in order to achieve
392753f127fSDimitry Andric // logarithmic time complexity of sorted symbol insertion. Symbol is inserted to
393753f127fSDimitry Andric // the set once it's processed in graphifySymbols. In this function, we iterate
394753f127fSDimitry Andric // each collected symbol in sorted order and calculate the implicit size.
395753f127fSDimitry Andric Error COFFLinkGraphBuilder::calculateImplicitSizeOfSymbols() {
396753f127fSDimitry Andric   for (COFFSectionIndex SecIndex = 1;
397753f127fSDimitry Andric        SecIndex <= static_cast<COFFSectionIndex>(Obj.getNumberOfSections());
398753f127fSDimitry Andric        SecIndex++) {
399753f127fSDimitry Andric     auto &SymbolSet = SymbolSets[SecIndex];
400972a253aSDimitry Andric     if (SymbolSet.empty())
401972a253aSDimitry Andric       continue;
402753f127fSDimitry Andric     jitlink::Block *B = getGraphBlock(SecIndex);
403753f127fSDimitry Andric     orc::ExecutorAddrDiff LastOffset = B->getSize();
404753f127fSDimitry Andric     orc::ExecutorAddrDiff LastDifferentOffset = B->getSize();
405753f127fSDimitry Andric     orc::ExecutorAddrDiff LastSize = 0;
406753f127fSDimitry Andric     for (auto It = SymbolSet.rbegin(); It != SymbolSet.rend(); It++) {
407753f127fSDimitry Andric       orc::ExecutorAddrDiff Offset = It->first;
408753f127fSDimitry Andric       jitlink::Symbol *Symbol = It->second;
409753f127fSDimitry Andric       orc::ExecutorAddrDiff CandSize;
410753f127fSDimitry Andric       // Last offset can be same when aliasing happened
411753f127fSDimitry Andric       if (Symbol->getOffset() == LastOffset)
412753f127fSDimitry Andric         CandSize = LastSize;
413753f127fSDimitry Andric       else
414753f127fSDimitry Andric         CandSize = LastOffset - Offset;
415753f127fSDimitry Andric 
416753f127fSDimitry Andric       LLVM_DEBUG({
417753f127fSDimitry Andric         if (Offset + Symbol->getSize() > LastDifferentOffset)
418753f127fSDimitry Andric           dbgs() << "  Overlapping symbol range generated for the following "
419753f127fSDimitry Andric                     "symbol:"
420753f127fSDimitry Andric                  << "\n"
421753f127fSDimitry Andric                  << "    " << *Symbol << "\n";
422753f127fSDimitry Andric       });
423753f127fSDimitry Andric       (void)LastDifferentOffset;
424753f127fSDimitry Andric       if (LastOffset != Offset)
425753f127fSDimitry Andric         LastDifferentOffset = Offset;
426753f127fSDimitry Andric       LastSize = CandSize;
427753f127fSDimitry Andric       LastOffset = Offset;
428753f127fSDimitry Andric       if (Symbol->getSize()) {
429753f127fSDimitry Andric         // Non empty symbol can happen in COMDAT symbol.
430753f127fSDimitry Andric         // We don't consider the possibility of overlapping symbol range that
431753f127fSDimitry Andric         // could be introduced by disparity between inferred symbol size and
432753f127fSDimitry Andric         // defined symbol size because symbol size information is currently only
433753f127fSDimitry Andric         // used by jitlink-check where we have control to not make overlapping
434753f127fSDimitry Andric         // ranges.
435753f127fSDimitry Andric         continue;
436753f127fSDimitry Andric       }
437753f127fSDimitry Andric 
438753f127fSDimitry Andric       LLVM_DEBUG({
439753f127fSDimitry Andric         if (!CandSize)
440753f127fSDimitry Andric           dbgs() << "  Empty implicit symbol size generated for the following "
441753f127fSDimitry Andric                     "symbol:"
442753f127fSDimitry Andric                  << "\n"
443753f127fSDimitry Andric                  << "    " << *Symbol << "\n";
444753f127fSDimitry Andric       });
445753f127fSDimitry Andric 
446753f127fSDimitry Andric       Symbol->setSize(CandSize);
447753f127fSDimitry Andric     }
448753f127fSDimitry Andric   }
449753f127fSDimitry Andric   return Error::success();
450753f127fSDimitry Andric }
451753f127fSDimitry Andric 
452753f127fSDimitry Andric Expected<Symbol *> COFFLinkGraphBuilder::createDefinedSymbol(
453753f127fSDimitry Andric     COFFSymbolIndex SymIndex, StringRef SymbolName,
454753f127fSDimitry Andric     object::COFFSymbolRef Symbol, const object::coff_section *Section) {
455753f127fSDimitry Andric   if (Symbol.isCommon()) {
456753f127fSDimitry Andric     // FIXME: correct alignment
457*bdd1243dSDimitry Andric     return &G->addDefinedSymbol(
458*bdd1243dSDimitry Andric         G->createZeroFillBlock(getCommonSection(), Symbol.getValue(),
459*bdd1243dSDimitry Andric                                orc::ExecutorAddr(), Symbol.getValue(), 0),
460*bdd1243dSDimitry Andric         0, SymbolName, Symbol.getValue(), Linkage::Strong, Scope::Default,
461*bdd1243dSDimitry Andric         false, false);
462753f127fSDimitry Andric   }
463753f127fSDimitry Andric   if (Symbol.isAbsolute())
464753f127fSDimitry Andric     return &G->addAbsoluteSymbol(SymbolName,
465753f127fSDimitry Andric                                  orc::ExecutorAddr(Symbol.getValue()), 0,
466753f127fSDimitry Andric                                  Linkage::Strong, Scope::Local, false);
467753f127fSDimitry Andric 
468753f127fSDimitry Andric   if (llvm::COFF::isReservedSectionNumber(Symbol.getSectionNumber()))
469753f127fSDimitry Andric     return make_error<JITLinkError>(
470753f127fSDimitry Andric         "Reserved section number used in regular symbol " +
471753f127fSDimitry Andric         formatv("{0:d}", SymIndex));
472753f127fSDimitry Andric 
473753f127fSDimitry Andric   Block *B = getGraphBlock(Symbol.getSectionNumber());
474972a253aSDimitry Andric   if (!B) {
475972a253aSDimitry Andric     LLVM_DEBUG({
476972a253aSDimitry Andric       dbgs() << "    " << SymIndex
477972a253aSDimitry Andric              << ": Skipping graph symbol since section was not created for "
478972a253aSDimitry Andric                 "COFF symbol \""
479972a253aSDimitry Andric              << SymbolName << "\" in section " << Symbol.getSectionNumber()
480972a253aSDimitry Andric              << "\n";
481972a253aSDimitry Andric     });
482972a253aSDimitry Andric     return nullptr;
483972a253aSDimitry Andric   }
484972a253aSDimitry Andric 
485753f127fSDimitry Andric   if (Symbol.isExternal()) {
486753f127fSDimitry Andric     // This is not a comdat sequence, export the symbol as it is
487972a253aSDimitry Andric     if (!isComdatSection(Section)) {
488*bdd1243dSDimitry Andric       auto GSym = &G->addDefinedSymbol(
489753f127fSDimitry Andric           *B, Symbol.getValue(), SymbolName, 0, Linkage::Strong, Scope::Default,
490753f127fSDimitry Andric           Symbol.getComplexType() == COFF::IMAGE_SYM_DTYPE_FUNCTION, false);
491*bdd1243dSDimitry Andric       DefinedSymbols[SymbolName] = GSym;
492*bdd1243dSDimitry Andric       return GSym;
493972a253aSDimitry Andric     } else {
494972a253aSDimitry Andric       if (!PendingComdatExports[Symbol.getSectionNumber()])
495753f127fSDimitry Andric         return make_error<JITLinkError>("No pending COMDAT export for symbol " +
496753f127fSDimitry Andric                                         formatv("{0:d}", SymIndex));
497972a253aSDimitry Andric 
498753f127fSDimitry Andric       return exportCOMDATSymbol(SymIndex, SymbolName, Symbol);
499753f127fSDimitry Andric     }
500753f127fSDimitry Andric   }
501753f127fSDimitry Andric 
502972a253aSDimitry Andric   if (Symbol.getStorageClass() == COFF::IMAGE_SYM_CLASS_STATIC ||
503972a253aSDimitry Andric       Symbol.getStorageClass() == COFF::IMAGE_SYM_CLASS_LABEL) {
504753f127fSDimitry Andric     const object::coff_aux_section_definition *Definition =
505753f127fSDimitry Andric         Symbol.getSectionDefinition();
506753f127fSDimitry Andric     if (!Definition || !isComdatSection(Section)) {
507753f127fSDimitry Andric       // Handle typical static symbol
508753f127fSDimitry Andric       return &G->addDefinedSymbol(
509753f127fSDimitry Andric           *B, Symbol.getValue(), SymbolName, 0, Linkage::Strong, Scope::Local,
510753f127fSDimitry Andric           Symbol.getComplexType() == COFF::IMAGE_SYM_DTYPE_FUNCTION, false);
511753f127fSDimitry Andric     }
512753f127fSDimitry Andric     if (Definition->Selection == COFF::IMAGE_COMDAT_SELECT_ASSOCIATIVE) {
513972a253aSDimitry Andric       auto Target = Definition->getNumber(Symbol.isBigObj());
514972a253aSDimitry Andric       auto GSym = &G->addDefinedSymbol(
515753f127fSDimitry Andric           *B, Symbol.getValue(), SymbolName, 0, Linkage::Strong, Scope::Local,
516753f127fSDimitry Andric           Symbol.getComplexType() == COFF::IMAGE_SYM_DTYPE_FUNCTION, false);
517972a253aSDimitry Andric       getGraphBlock(Target)->addEdge(Edge::KeepAlive, 0, *GSym, 0);
518972a253aSDimitry Andric       return GSym;
519753f127fSDimitry Andric     }
520972a253aSDimitry Andric     if (PendingComdatExports[Symbol.getSectionNumber()])
521753f127fSDimitry Andric       return make_error<JITLinkError>(
522753f127fSDimitry Andric           "COMDAT export request already exists before symbol " +
523753f127fSDimitry Andric           formatv("{0:d}", SymIndex));
524753f127fSDimitry Andric     return createCOMDATExportRequest(SymIndex, Symbol, Definition);
525753f127fSDimitry Andric   }
526753f127fSDimitry Andric   return make_error<JITLinkError>("Unsupported storage class " +
527753f127fSDimitry Andric                                   formatv("{0:d}", Symbol.getStorageClass()) +
528753f127fSDimitry Andric                                   " in symbol " + formatv("{0:d}", SymIndex));
529753f127fSDimitry Andric }
530753f127fSDimitry Andric 
531753f127fSDimitry Andric // COMDAT handling:
532753f127fSDimitry Andric // When IMAGE_SCN_LNK_COMDAT flag is set in the flags of a section,
533753f127fSDimitry Andric // the section is called a COMDAT section. It contains two symbols
534753f127fSDimitry Andric // in a sequence that specifes the behavior. First symbol is the section
535753f127fSDimitry Andric // symbol which contains the size and name of the section. It also contains
536753f127fSDimitry Andric // selection type that specifies how duplicate of the symbol is handled.
537753f127fSDimitry Andric // Second symbol is COMDAT symbol which usually defines the external name and
538753f127fSDimitry Andric // data type.
539753f127fSDimitry Andric //
540753f127fSDimitry Andric // Since two symbols always come in a specific order, we initiate pending COMDAT
541753f127fSDimitry Andric // export request when we encounter the first symbol and actually exports it
542753f127fSDimitry Andric // when we process the second symbol.
543753f127fSDimitry Andric //
544753f127fSDimitry Andric // Process the first symbol of COMDAT sequence.
545753f127fSDimitry Andric Expected<Symbol *> COFFLinkGraphBuilder::createCOMDATExportRequest(
546753f127fSDimitry Andric     COFFSymbolIndex SymIndex, object::COFFSymbolRef Symbol,
547753f127fSDimitry Andric     const object::coff_aux_section_definition *Definition) {
548753f127fSDimitry Andric   Linkage L = Linkage::Strong;
549753f127fSDimitry Andric   switch (Definition->Selection) {
550753f127fSDimitry Andric   case COFF::IMAGE_COMDAT_SELECT_NODUPLICATES: {
551753f127fSDimitry Andric     L = Linkage::Strong;
552753f127fSDimitry Andric     break;
553753f127fSDimitry Andric   }
554753f127fSDimitry Andric   case COFF::IMAGE_COMDAT_SELECT_ANY: {
555753f127fSDimitry Andric     L = Linkage::Weak;
556753f127fSDimitry Andric     break;
557753f127fSDimitry Andric   }
558753f127fSDimitry Andric   case COFF::IMAGE_COMDAT_SELECT_EXACT_MATCH:
559753f127fSDimitry Andric   case COFF::IMAGE_COMDAT_SELECT_SAME_SIZE: {
560753f127fSDimitry Andric     // FIXME: Implement size/content validation when LinkGraph is able to
561753f127fSDimitry Andric     // handle this.
562753f127fSDimitry Andric     L = Linkage::Weak;
563753f127fSDimitry Andric     break;
564753f127fSDimitry Andric   }
565753f127fSDimitry Andric   case COFF::IMAGE_COMDAT_SELECT_LARGEST: {
566972a253aSDimitry Andric     // FIXME: Support IMAGE_COMDAT_SELECT_LARGEST properly when LinkGraph is
567972a253aSDimitry Andric     // able to handle this.
568972a253aSDimitry Andric     LLVM_DEBUG({
569972a253aSDimitry Andric       dbgs() << "    " << SymIndex
570972a253aSDimitry Andric              << ": Partially supported IMAGE_COMDAT_SELECT_LARGEST was used"
571972a253aSDimitry Andric                 " in section "
572*bdd1243dSDimitry Andric              << Symbol.getSectionNumber() << " (size: " << Definition->Length
573*bdd1243dSDimitry Andric              << ")\n";
574972a253aSDimitry Andric     });
575972a253aSDimitry Andric     L = Linkage::Weak;
576972a253aSDimitry Andric     break;
577753f127fSDimitry Andric   }
578753f127fSDimitry Andric   case COFF::IMAGE_COMDAT_SELECT_NEWEST: {
579753f127fSDimitry Andric     // Even link.exe doesn't support this selection properly.
580753f127fSDimitry Andric     return make_error<JITLinkError>(
581753f127fSDimitry Andric         "IMAGE_COMDAT_SELECT_NEWEST is not supported.");
582753f127fSDimitry Andric   }
583753f127fSDimitry Andric   default: {
584753f127fSDimitry Andric     return make_error<JITLinkError>("Invalid comdat selection type: " +
585753f127fSDimitry Andric                                     formatv("{0:d}", Definition->Selection));
586753f127fSDimitry Andric   }
587753f127fSDimitry Andric   }
588*bdd1243dSDimitry Andric   PendingComdatExports[Symbol.getSectionNumber()] = {SymIndex, L,
589*bdd1243dSDimitry Andric                                                      Definition->Length};
590*bdd1243dSDimitry Andric   return nullptr;
591753f127fSDimitry Andric }
592753f127fSDimitry Andric 
593753f127fSDimitry Andric // Process the second symbol of COMDAT sequence.
594753f127fSDimitry Andric Expected<Symbol *>
595753f127fSDimitry Andric COFFLinkGraphBuilder::exportCOMDATSymbol(COFFSymbolIndex SymIndex,
596753f127fSDimitry Andric                                          StringRef SymbolName,
597753f127fSDimitry Andric                                          object::COFFSymbolRef Symbol) {
598*bdd1243dSDimitry Andric   Block *B = getGraphBlock(Symbol.getSectionNumber());
599972a253aSDimitry Andric   auto &PendingComdatExport = PendingComdatExports[Symbol.getSectionNumber()];
600*bdd1243dSDimitry Andric   // NOTE: ComdatDef->Legnth is the size of "section" not size of symbol.
601*bdd1243dSDimitry Andric   // We use zero symbol size to not reach out of bound of block when symbol
602*bdd1243dSDimitry Andric   // offset is non-zero.
603*bdd1243dSDimitry Andric   auto GSym = &G->addDefinedSymbol(
604*bdd1243dSDimitry Andric       *B, Symbol.getValue(), SymbolName, 0, PendingComdatExport->Linkage,
605*bdd1243dSDimitry Andric       Scope::Default, Symbol.getComplexType() == COFF::IMAGE_SYM_DTYPE_FUNCTION,
606*bdd1243dSDimitry Andric       false);
607753f127fSDimitry Andric   LLVM_DEBUG({
608753f127fSDimitry Andric     dbgs() << "    " << SymIndex
609753f127fSDimitry Andric            << ": Exporting COMDAT graph symbol for COFF symbol \"" << SymbolName
610753f127fSDimitry Andric            << "\" in section " << Symbol.getSectionNumber() << "\n";
611*bdd1243dSDimitry Andric     dbgs() << "      " << *GSym << "\n";
612753f127fSDimitry Andric   });
613*bdd1243dSDimitry Andric   setGraphSymbol(Symbol.getSectionNumber(), PendingComdatExport->SymbolIndex,
614*bdd1243dSDimitry Andric                  *GSym);
615*bdd1243dSDimitry Andric   DefinedSymbols[SymbolName] = GSym;
616*bdd1243dSDimitry Andric   PendingComdatExport = std::nullopt;
617*bdd1243dSDimitry Andric   return GSym;
618753f127fSDimitry Andric }
619753f127fSDimitry Andric 
620753f127fSDimitry Andric } // namespace jitlink
621753f127fSDimitry Andric } // namespace llvm
622