Index: lld/trunk/COFF/Chunks.h =================================================================== --- lld/trunk/COFF/Chunks.h +++ lld/trunk/COFF/Chunks.h @@ -159,10 +159,9 @@ void addAssociative(SectionChunk *Child); StringRef getDebugName() override; - void setSymbol(DefinedRegular *S) { if (!Sym) Sym = S; } - // Returns true if the chunk was not dropped by GC or COMDAT deduplication. - bool isLive() { return Live && !Discarded; } + // Returns true if the chunk was not dropped by GC. + bool isLive() { return Live; } // Used by the garbage collector. void markLive() { @@ -171,13 +170,6 @@ Live = true; } - // Returns true if this chunk was dropped by COMDAT deduplication. - bool isDiscarded() const { return Discarded; } - - // Used by the SymbolTable when discarding unused comdat sections. This is - // redundant when GC is enabled, as all comdat sections will start out dead. - void markDiscarded() { Discarded = true; } - // True if this is a codeview debug info chunk. These will not be laid out in // the image. Instead they will end up in the PDB, if one is requested. bool isCodeView() const { @@ -213,24 +205,21 @@ // The file that this chunk was created from. ObjFile *File; + // The COMDAT leader symbol if this is a COMDAT chunk. + DefinedRegular *Sym = nullptr; + private: StringRef SectionName; std::vector AssocChildren; llvm::iterator_range Relocs; size_t NumRelocs; - // True if this chunk was discarded because it was a duplicate comdat section. - bool Discarded; - // Used by the garbage collector. bool Live; // Used for ICF (Identical COMDAT Folding) void replace(SectionChunk *Other); uint32_t Class[2] = {0, 0}; - - // Sym points to a section symbol if this is a COMDAT chunk. - DefinedRegular *Sym = nullptr; }; // A chunk for common symbols. Common chunks don't have actual data. Index: lld/trunk/COFF/Chunks.cpp =================================================================== --- lld/trunk/COFF/Chunks.cpp +++ lld/trunk/COFF/Chunks.cpp @@ -38,9 +38,6 @@ Alignment = Header->getAlignment(); - // Chunks may be discarded during comdat merging. - Discarded = false; - // If linker GC is disabled, every chunk starts out alive. If linker GC is // enabled, treat non-comdat sections as roots. Generally optimized object // files will be built with -ffunction-sections or /Gy, so most things worth @@ -362,12 +359,8 @@ void SectionChunk::printDiscardedMessage() const { // Removed by dead-stripping. If it's removed by ICF, ICF already // printed out the name, so don't repeat that here. - if (Sym && this == Repl) { - if (Discarded) - message("Discarded comdat symbol " + Sym->getName()); - else if (!Live) - message("Discarded " + Sym->getName()); - } + if (Sym && this == Repl) + message("Discarded " + Sym->getName()); } StringRef SectionChunk::getDebugName() { Index: lld/trunk/COFF/InputFiles.h =================================================================== --- lld/trunk/COFF/InputFiles.h +++ lld/trunk/COFF/InputFiles.h @@ -142,7 +142,19 @@ void initializeSymbols(); void initializeSEH(); - Symbol *createDefined(COFFSymbolRef Sym, const void *Aux, bool IsFirst); + SectionChunk * + readSection(uint32_t SectionNumber, + const llvm::object::coff_aux_section_definition *Def); + + void readAssociativeDefinition( + COFFSymbolRef COFFSym, + const llvm::object::coff_aux_section_definition *Def); + + llvm::Optional + createDefined(COFFSymbolRef Sym, + std::vector + &ComdatDefs); + Symbol *createRegular(COFFSymbolRef Sym); Symbol *createUndefined(COFFSymbolRef Sym); std::unique_ptr COFFObj; Index: lld/trunk/COFF/InputFiles.cpp =================================================================== --- lld/trunk/COFF/InputFiles.cpp +++ lld/trunk/COFF/InputFiles.cpp @@ -119,86 +119,158 @@ initializeSEH(); } +// We set SectionChunk pointers in the SparseChunks vector to this value +// temporarily to mark comdat sections as having an unknown resolution. As we +// walk the object file's symbol table, once we visit either a leader symbol or +// an associative section definition together with the parent comdat's leader, +// we set the pointer to either nullptr (to mark the section as discarded) or a +// valid SectionChunk for that section. +static SectionChunk *const PendingComdat = reinterpret_cast(1); + void ObjFile::initializeChunks() { uint32_t NumSections = COFFObj->getNumberOfSections(); Chunks.reserve(NumSections); SparseChunks.resize(NumSections + 1); for (uint32_t I = 1; I < NumSections + 1; ++I) { const coff_section *Sec; - StringRef Name; if (auto EC = COFFObj->getSection(I, Sec)) fatal("getSection failed: #" + Twine(I) + ": " + EC.message()); - if (auto EC = COFFObj->getSectionName(Sec, Name)) - fatal("getSectionName failed: #" + Twine(I) + ": " + EC.message()); - if (Name == ".sxdata") { - SXData = Sec; - continue; - } - if (Name == ".drectve") { - ArrayRef Data; - COFFObj->getSectionContents(Sec, Data); - Directives = std::string((const char *)Data.data(), Data.size()); - continue; - } - // Object files may have DWARF debug info or MS CodeView debug info - // (or both). - // - // DWARF sections don't need any special handling from the perspective - // of the linker; they are just a data section containing relocations. - // We can just link them to complete debug info. - // - // CodeView needs a linker support. We need to interpret and debug - // info, and then write it to a separate .pdb file. - - // Ignore debug info unless /debug is given. - if (!Config->Debug && Name.startswith(".debug")) - continue; - - if (Sec->Characteristics & llvm::COFF::IMAGE_SCN_LNK_REMOVE) - continue; - auto *C = make(this, Sec); - - // CodeView sections are stored to a different vector because they are not - // linked in the regular manner. - if (C->isCodeView()) - DebugChunks.push_back(C); + if (Sec->Characteristics & IMAGE_SCN_LNK_COMDAT) + SparseChunks[I] = PendingComdat; else - Chunks.push_back(C); + SparseChunks[I] = readSection(I, nullptr); + } +} + +SectionChunk *ObjFile::readSection(uint32_t SectionNumber, + const coff_aux_section_definition *Def) { + const coff_section *Sec; + StringRef Name; + if (auto EC = COFFObj->getSection(SectionNumber, Sec)) + fatal("getSection failed: #" + Twine(SectionNumber) + ": " + EC.message()); + if (auto EC = COFFObj->getSectionName(Sec, Name)) + fatal("getSectionName failed: #" + Twine(SectionNumber) + ": " + + EC.message()); + if (Name == ".sxdata") { + SXData = Sec; + return nullptr; + } + if (Name == ".drectve") { + ArrayRef Data; + COFFObj->getSectionContents(Sec, Data); + Directives = std::string((const char *)Data.data(), Data.size()); + return nullptr; + } + + // Object files may have DWARF debug info or MS CodeView debug info + // (or both). + // + // DWARF sections don't need any special handling from the perspective + // of the linker; they are just a data section containing relocations. + // We can just link them to complete debug info. + // + // CodeView needs a linker support. We need to interpret and debug + // info, and then write it to a separate .pdb file. + + // Ignore debug info unless /debug is given. + if (!Config->Debug && Name.startswith(".debug")) + return nullptr; + + if (Sec->Characteristics & llvm::COFF::IMAGE_SCN_LNK_REMOVE) + return nullptr; + auto *C = make(this, Sec); + if (Def) + C->Checksum = Def->CheckSum; + + // CodeView sections are stored to a different vector because they are not + // linked in the regular manner. + if (C->isCodeView()) + DebugChunks.push_back(C); + else + Chunks.push_back(C); + + return C; +} + +void ObjFile::readAssociativeDefinition( + COFFSymbolRef Sym, const coff_aux_section_definition *Def) { + SectionChunk *Parent = SparseChunks[Def->getNumber(Sym.isBigObj())]; + + // If the parent is pending, it probably means that its section definition + // appears after us in the symbol table. Leave the associated section as + // pending; we will handle it during the second pass in initializeSymbols(). + if (Parent == PendingComdat) + return; - SparseChunks[I] = C; + // Check whether the parent is prevailing. If it is, so are we, and we read + // the section; otherwise mark it as discarded. + int32_t SectionNumber = Sym.getSectionNumber(); + if (Parent) { + SparseChunks[SectionNumber] = readSection(SectionNumber, Def); + Parent->addAssociative(SparseChunks[SectionNumber]); + } else { + SparseChunks[SectionNumber] = nullptr; } } +Symbol *ObjFile::createRegular(COFFSymbolRef Sym) { + SectionChunk *SC = SparseChunks[Sym.getSectionNumber()]; + if (Sym.isExternal()) { + StringRef Name; + COFFObj->getSymbolName(Sym, Name); + if (SC) + return Symtab->addRegular(this, Name, Sym.getGeneric(), SC); + return Symtab->addUndefined(Name, this, false); + } + if (SC) + return make(this, /*Name*/ "", false, + /*IsExternal*/ false, Sym.getGeneric(), SC); + return nullptr; +} + void ObjFile::initializeSymbols() { uint32_t NumSymbols = COFFObj->getNumberOfSymbols(); Symbols.resize(NumSymbols); SmallVector, 8> WeakAliases; - int32_t LastSectionNumber = 0; + std::vector PendingIndexes; + PendingIndexes.reserve(NumSymbols); + + std::vector ComdatDefs( + COFFObj->getNumberOfSections() + 1); for (uint32_t I = 0; I < NumSymbols; ++I) { COFFSymbolRef COFFSym = check(COFFObj->getSymbol(I)); - - const void *AuxP = nullptr; - if (COFFSym.getNumberOfAuxSymbols()) - AuxP = check(COFFObj->getSymbol(I + 1)).getRawPtr(); - bool IsFirst = (LastSectionNumber != COFFSym.getSectionNumber()); - - Symbol *Sym = nullptr; if (COFFSym.isUndefined()) { - Sym = createUndefined(COFFSym); + Symbols[I] = createUndefined(COFFSym); } else if (COFFSym.isWeakExternal()) { - Sym = createUndefined(COFFSym); - uint32_t TagIndex = - static_cast(AuxP)->TagIndex; - WeakAliases.emplace_back(Sym, TagIndex); + Symbols[I] = createUndefined(COFFSym); + uint32_t TagIndex = COFFSym.getAux()->TagIndex; + WeakAliases.emplace_back(Symbols[I], TagIndex); + } else if (Optional OptSym = createDefined(COFFSym, ComdatDefs)) { + Symbols[I] = *OptSym; } else { - Sym = createDefined(COFFSym, AuxP, IsFirst); + // createDefined() returns None if a symbol belongs to a section that + // was pending at the point when the symbol was read. This can happen in + // two cases: + // 1) section definition symbol for a comdat leader; + // 2) symbol belongs to a comdat section associated with a section whose + // section definition symbol appears later in the symbol table. + // In both of these cases, we can expect the section to be resolved by + // the time we finish visiting the remaining symbols in the symbol + // table. So we postpone the handling of this symbol until that time. + PendingIndexes.push_back(I); } - Symbols[I] = Sym; I += COFFSym.getNumberOfAuxSymbols(); - LastSectionNumber = COFFSym.getSectionNumber(); + } + + for (uint32_t I : PendingIndexes) { + COFFSymbolRef Sym = check(COFFObj->getSymbol(I)); + if (auto *Def = Sym.getSectionDefinition()) + if (Def->Selection == IMAGE_COMDAT_SELECT_ASSOCIATIVE) + readAssociativeDefinition(Sym, Def); + Symbols[I] = createRegular(Sym); } for (auto &KV : WeakAliases) { @@ -214,8 +286,9 @@ return Symtab->addUndefined(Name, this, Sym.isWeakExternal()); } -Symbol *ObjFile::createDefined(COFFSymbolRef Sym, const void *AuxP, - bool IsFirst) { +Optional ObjFile::createDefined( + COFFSymbolRef Sym, + std::vector &ComdatDefs) { StringRef Name; if (Sym.isCommon()) { auto *C = make(Sym); @@ -254,37 +327,46 @@ if ((uint32_t)SectionNumber >= SparseChunks.size()) fatal("broken object file: " + toString(this)); - // Nothing else to do without a section chunk. - auto *SC = SparseChunks[SectionNumber]; - if (!SC) - return nullptr; - - // Handle section definitions - if (IsFirst && AuxP) { - auto *Aux = reinterpret_cast(AuxP); - if (Aux->Selection == IMAGE_COMDAT_SELECT_ASSOCIATIVE) - if (auto *ParentSC = SparseChunks[Aux->getNumber(Sym.isBigObj())]) { - ParentSC->addAssociative(SC); - // If we already discarded the parent, discard the child. - if (ParentSC->isDiscarded()) - SC->markDiscarded(); - } - SC->Checksum = Aux->CheckSum; + // Handle comdat leader symbols. + if (const coff_aux_section_definition *Def = ComdatDefs[SectionNumber]) { + ComdatDefs[SectionNumber] = nullptr; + Symbol *Leader; + bool Prevailing; + if (Sym.isExternal()) { + COFFObj->getSymbolName(Sym, Name); + std::tie(Leader, Prevailing) = + Symtab->addComdat(this, Name, Sym.getGeneric()); + } else { + Leader = make(this, /*Name*/ "", false, + /*IsExternal*/ false, Sym.getGeneric()); + Prevailing = true; + } + if (Prevailing) { + SectionChunk *C = readSection(SectionNumber, Def); + SparseChunks[SectionNumber] = C; + C->Sym = cast(Leader); + cast(Leader)->Data = &C->Repl; + } else { + SparseChunks[SectionNumber] = nullptr; + } + return Leader; } - DefinedRegular *B; - if (Sym.isExternal()) { - COFFObj->getSymbolName(Sym, Name); - Symbol *S = - Symtab->addRegular(this, Name, SC->isCOMDAT(), Sym.getGeneric(), SC); - B = cast(S); - } else - B = make(this, /*Name*/ "", SC->isCOMDAT(), - /*IsExternal*/ false, Sym.getGeneric(), SC); - if (SC->isCOMDAT() && Sym.getValue() == 0 && !AuxP) - SC->setSymbol(B); + // Read associative section definitions and prepare to handle the comdat + // leader symbol by setting the section's ComdatDefs pointer if we encounter a + // non-associative comdat. + if (SparseChunks[SectionNumber] == PendingComdat) { + if (auto *Def = Sym.getSectionDefinition()) { + if (Def->Selection == IMAGE_COMDAT_SELECT_ASSOCIATIVE) + readAssociativeDefinition(Sym, Def); + else + ComdatDefs[SectionNumber] = Def; + } + } - return B; + if (SparseChunks[SectionNumber] == PendingComdat) + return None; + return createRegular(Sym); } void ObjFile::initializeSEH() { @@ -361,8 +443,12 @@ void BitcodeFile::parse() { Obj = check(lto::InputFile::create(MemoryBufferRef( MB.getBuffer(), Saver.save(ParentName + MB.getBufferIdentifier())))); + std::vector> Comdat(Obj->getComdatTable().size()); + for (size_t I = 0; I != Obj->getComdatTable().size(); ++I) + Comdat[I] = Symtab->addComdat(this, Saver.save(Obj->getComdatTable()[I])); for (const lto::InputFile::Symbol &ObjSym : Obj->symbols()) { StringRef SymName = Saver.save(ObjSym.getName()); + int ComdatIndex = ObjSym.getComdatIndex(); Symbol *Sym; if (ObjSym.isUndefined()) { Sym = Symtab->addUndefined(SymName, this, false); @@ -374,9 +460,15 @@ std::string Fallback = ObjSym.getCOFFWeakExternalFallback(); Symbol *Alias = Symtab->addUndefined(Saver.save(Fallback)); checkAndSetWeakAlias(Symtab, this, Sym, Alias); + } else if (ComdatIndex != -1) { + if (SymName == Obj->getComdatTable()[ComdatIndex]) + Sym = Comdat[ComdatIndex].first; + else if (Comdat[ComdatIndex].second) + Sym = Symtab->addRegular(this, SymName); + else + Sym = Symtab->addUndefined(SymName, this, false); } else { - bool IsCOMDAT = ObjSym.getComdatIndex() != -1; - Sym = Symtab->addRegular(this, SymName, IsCOMDAT); + Sym = Symtab->addRegular(this, SymName); } SymbolBodies.push_back(Sym); } Index: lld/trunk/COFF/MarkLive.cpp =================================================================== --- lld/trunk/COFF/MarkLive.cpp +++ lld/trunk/COFF/MarkLive.cpp @@ -52,13 +52,6 @@ while (!Worklist.empty()) { SectionChunk *SC = Worklist.pop_back_val(); - - // If this section was discarded, there are relocations referring to - // discarded sections. Ignore these sections to avoid crashing. They will be - // diagnosed during relocation processing. - if (SC->isDiscarded()) - continue; - assert(SC->isLive() && "We mark as live when pushing onto the worklist!"); // Mark all symbols listed in the relocation table for this section. Index: lld/trunk/COFF/SymbolTable.h =================================================================== --- lld/trunk/COFF/SymbolTable.h +++ lld/trunk/COFF/SymbolTable.h @@ -83,9 +83,12 @@ Symbol *addUndefined(StringRef Name, InputFile *F, bool IsWeakAlias); void addLazy(ArchiveFile *F, const Archive::Symbol Sym); Symbol *addAbsolute(StringRef N, COFFSymbolRef S); - Symbol *addRegular(InputFile *F, StringRef N, bool IsCOMDAT, + Symbol *addRegular(InputFile *F, StringRef N, const llvm::object::coff_symbol_generic *S = nullptr, SectionChunk *C = nullptr); + std::pair + addComdat(InputFile *F, StringRef N, + const llvm::object::coff_symbol_generic *S = nullptr); Symbol *addCommon(InputFile *F, StringRef N, uint64_t Size, const llvm::object::coff_symbol_generic *S = nullptr, CommonChunk *C = nullptr); Index: lld/trunk/COFF/SymbolTable.cpp =================================================================== --- lld/trunk/COFF/SymbolTable.cpp +++ lld/trunk/COFF/SymbolTable.cpp @@ -24,36 +24,6 @@ namespace lld { namespace coff { -enum SymbolPreference { - SP_EXISTING = -1, - SP_CONFLICT = 0, - SP_NEW = 1, -}; - -/// Checks if an existing symbol S should be kept or replaced by a new symbol. -/// Returns SP_EXISTING when S should be kept, SP_NEW when the new symbol -/// should be kept, and SP_CONFLICT if no valid resolution exists. -static SymbolPreference compareDefined(Symbol *S, bool WasInserted, - bool NewIsCOMDAT) { - // If the symbol wasn't previously known, the new symbol wins by default. - if (WasInserted || !isa(S)) - return SP_NEW; - - // If the existing symbol is a DefinedRegular, both it and the new symbol - // must be comdats. In that case, we have no reason to prefer one symbol - // over the other, and we keep the existing one. If one of the symbols - // is not a comdat, we report a conflict. - if (auto *R = dyn_cast(S)) { - if (NewIsCOMDAT && R->isCOMDAT()) - return SP_EXISTING; - else - return SP_CONFLICT; - } - - // Existing symbol is not a DefinedRegular; new symbol wins. - return SP_NEW; -} - SymbolTable *Symtab; void SymbolTable::addFile(InputFile *File) { @@ -240,7 +210,7 @@ return S; } -Symbol *SymbolTable::addRegular(InputFile *F, StringRef N, bool IsCOMDAT, +Symbol *SymbolTable::addRegular(InputFile *F, StringRef N, const coff_symbol_generic *Sym, SectionChunk *C) { Symbol *S; @@ -248,22 +218,32 @@ std::tie(S, WasInserted) = insert(N); if (!isa(F)) S->IsUsedInRegularObj = true; - SymbolPreference SP = compareDefined(S, WasInserted, IsCOMDAT); - if (SP == SP_CONFLICT) { + if (WasInserted || !isa(S)) + replaceSymbol(S, F, N, /*IsCOMDAT*/ false, + /*IsExternal*/ true, Sym, C); + else reportDuplicate(S, F); - } else if (SP == SP_NEW) { - replaceSymbol(S, F, N, IsCOMDAT, /*IsExternal*/ true, Sym, - C); - } else if (SP == SP_EXISTING && IsCOMDAT && C) { - C->markDiscarded(); - // Discard associative chunks that we've parsed so far. No need to recurse - // because an associative section cannot have children. - for (SectionChunk *Child : C->children()) - Child->markDiscarded(); - } return S; } +std::pair +SymbolTable::addComdat(InputFile *F, StringRef N, + const coff_symbol_generic *Sym) { + Symbol *S; + bool WasInserted; + std::tie(S, WasInserted) = insert(N); + if (!isa(F)) + S->IsUsedInRegularObj = true; + if (WasInserted || !isa(S)) { + replaceSymbol(S, F, N, /*IsCOMDAT*/ true, + /*IsExternal*/ true, Sym, nullptr); + return {S, true}; + } + if (!cast(S)->isCOMDAT()) + reportDuplicate(S, F); + return {S, false}; +} + Symbol *SymbolTable::addCommon(InputFile *F, StringRef N, uint64_t Size, const coff_symbol_generic *Sym, CommonChunk *C) { Symbol *S; Index: lld/trunk/COFF/Symbols.h =================================================================== --- lld/trunk/COFF/Symbols.h +++ lld/trunk/COFF/Symbols.h @@ -169,7 +169,6 @@ SectionChunk *getChunk() const { return *Data; } uint32_t getValue() const { return Sym->Value; } -private: SectionChunk **Data; }; Index: lld/trunk/test/COFF/reloc-discarded.s =================================================================== --- lld/trunk/test/COFF/reloc-discarded.s +++ lld/trunk/test/COFF/reloc-discarded.s @@ -18,7 +18,6 @@ .section .CRT$XCU,"dr",associative,main_global .p2align 3 - .globl assoc_global assoc_global: .quad main_global Index: llvm/trunk/include/llvm/Object/COFF.h =================================================================== --- llvm/trunk/include/llvm/Object/COFF.h +++ llvm/trunk/include/llvm/Object/COFF.h @@ -275,6 +275,8 @@ support::ulittle32_t Value; }; +struct coff_aux_section_definition; + class COFFSymbolRef { public: COFFSymbolRef() = default; @@ -346,6 +348,18 @@ return (getType() & 0xF0) >> COFF::SCT_COMPLEX_TYPE_SHIFT; } + template const T *getAux() const { + return CS16 ? reinterpret_cast(CS16 + 1) + : reinterpret_cast(CS32 + 1); + } + + const coff_aux_section_definition *getSectionDefinition() const { + if (!getNumberOfAuxSymbols() || + getStorageClass() != COFF::IMAGE_SYM_CLASS_STATIC) + return nullptr; + return getAux(); + } + bool isAbsolute() const { return getSectionNumber() == -1; }