Index: lld/trunk/ELF/Driver.cpp =================================================================== --- lld/trunk/ELF/Driver.cpp +++ lld/trunk/ELF/Driver.cpp @@ -1323,6 +1323,27 @@ Symtab->fetchLazy(Sym); } +// Replaces common symbols with defined symbols reside in .bss sections. +// This function is called after all symbol names are resolved. As a +// result, the passes after the symbol resolution won't see any +// symbols of type CommonSymbol. +static void replaceCommonSymbols() { + for (Symbol *Sym : Symtab->getSymbols()) { + auto *S = dyn_cast(Sym); + if (!S) + continue; + + auto *Bss = make("COMMON", S->Size, S->Alignment); + Bss->File = S->File; + Bss->Live = !Config->GcSections; + InputSections.push_back(Bss); + + Defined New(S->File, S->getName(), S->Binding, S->StOther, S->Type, + /*Value=*/0, S->Size, Bss); + replaceSymbol(S, &New); + } +} + // If all references to a DSO happen to be weak, the DSO is not added // to DT_NEEDED. If that happens, we need to eliminate shared symbols // created from the DSO. Otherwise, they become dangling references @@ -1681,6 +1702,9 @@ if (!Config->Relocatable) InputSections.push_back(createCommentSection()); + // Replace common symbols with regular symbols. + replaceCommonSymbols(); + // Do size optimizations: garbage collection, merging of SHF_MERGE sections // and identical code folding. splitSections(); Index: lld/trunk/ELF/InputFiles.cpp =================================================================== --- lld/trunk/ELF/InputFiles.cpp +++ lld/trunk/ELF/InputFiles.cpp @@ -899,7 +899,7 @@ fatal(toString(this) + ": common symbol '" + Name + "' has invalid alignment: " + Twine(Value)); return Symtab->addCommon( - Defined{this, Name, Binding, StOther, Type, Value, Size, nullptr}); + CommonSymbol{this, Name, Binding, StOther, Type, Value, Size}); } switch (Binding) { @@ -1266,9 +1266,9 @@ } if (ObjSym.isCommon()) - return Symtab->addCommon(Defined{&F, Name, Binding, Visibility, STT_OBJECT, - ObjSym.getCommonAlignment(), - ObjSym.getCommonSize(), nullptr}); + return Symtab->addCommon( + CommonSymbol{&F, Name, Binding, Visibility, STT_OBJECT, + ObjSym.getCommonAlignment(), ObjSym.getCommonSize()}); Defined New(&F, Name, Binding, Visibility, Type, 0, 0, nullptr); if (CanOmitFromDynSym) Index: lld/trunk/ELF/LinkerScript.cpp =================================================================== --- lld/trunk/ELF/LinkerScript.cpp +++ lld/trunk/ELF/LinkerScript.cpp @@ -186,8 +186,8 @@ Defined New(nullptr, Cmd->Name, STB_GLOBAL, Visibility, STT_NOTYPE, SymValue, 0, Sec); - Symbol *Sym; - std::tie(Sym, std::ignore) = Symtab->insert(New); + Symbol *Sym = Symtab->insert(New); + Symtab->mergeProperties(Sym, New); replaceSymbol(Sym, &New); Cmd->Sym = cast(Sym); } @@ -203,8 +203,8 @@ nullptr); // We can't calculate final value right now. - Symbol *Sym; - std::tie(Sym, std::ignore) = Symtab->insert(New); + Symbol *Sym = Symtab->insert(New); + Symtab->mergeProperties(Sym, New); replaceSymbol(Sym, &New); Cmd->Sym = cast(Sym); Index: lld/trunk/ELF/SymbolTable.h =================================================================== --- lld/trunk/ELF/SymbolTable.h +++ lld/trunk/ELF/SymbolTable.h @@ -18,6 +18,7 @@ namespace lld { namespace elf { +class CommonSymbol; class Defined; class LazyArchive; class LazyObject; @@ -46,7 +47,7 @@ template Symbol *addUndefined(const Undefined &New); - Defined *addDefined(const Defined &New); + Symbol *addDefined(const Defined &New); void addShared(const SharedSymbol &New); @@ -54,9 +55,10 @@ template void addLazyObject(const LazyObject &New); Symbol *addBitcode(const Defined &New); - Symbol *addCommon(const Defined &New); + Symbol *addCommon(const CommonSymbol &New); - std::pair insert(const Symbol &New); + Symbol *insert(const Symbol &New); + void mergeProperties(Symbol *Old, const Symbol &New); template void fetchLazy(Symbol *Sym); Index: lld/trunk/ELF/SymbolTable.cpp =================================================================== --- lld/trunk/ELF/SymbolTable.cpp +++ lld/trunk/ELF/SymbolTable.cpp @@ -86,11 +86,8 @@ return std::min(VA, VB); } -// Find an existing symbol or create and insert a new one, then apply the given -// attributes. -std::pair SymbolTable::insert(const Symbol &New) { - // Find an existing symbol or create and insert a new one. - +// Find an existing symbol or create and insert a new one. +Symbol *SymbolTable::insert(const Symbol &New) { // @@ means the symbol is the default version. In that // case @@ will be used to resolve references to . // @@ -130,26 +127,36 @@ Old = SymVector[SymIndex]; } + return Old; +} + +// Merge symbol properties. +// +// When we have many symbols of the same name, we choose one of them, +// and that's the result of symbol resolution. However, symbols that +// were not chosen still affect some symbol properteis. +void SymbolTable::mergeProperties(Symbol *Old, const Symbol &New) { // Merge symbol properties. Old->ExportDynamic = Old->ExportDynamic || New.ExportDynamic; Old->IsUsedInRegularObj = Old->IsUsedInRegularObj || New.IsUsedInRegularObj; // DSO symbols do not affect visibility in the output. - if (!isa(&New)) + if (!isa(New)) Old->Visibility = getMinVisibility(Old->Visibility, New.Visibility); - - return {Old, IsNew}; } template Symbol *SymbolTable::addUndefined(const Undefined &New) { - Symbol *Old; - bool WasInserted; - std::tie(Old, WasInserted) = insert(New); + Symbol *Old = insert(New); + mergeProperties(Old, New); + + if (Old->isPlaceholder()) { + replaceSymbol(Old, &New); + return Old; + } // An undefined symbol with non default visibility must be satisfied // in the same DSO. - if (WasInserted || - (isa(Old) && New.Visibility != STV_DEFAULT)) { + if (Old->isShared() && New.Visibility != STV_DEFAULT) { replaceSymbol(Old, &New); return Old; } @@ -245,95 +252,80 @@ return 0; } -// We have a new defined symbol with the specified binding. Return 1 if the new -// symbol should win, -1 if the new symbol should lose, or 0 if both symbols are -// strong defined symbols. -static int compareDefined(const Symbol *Old, const Symbol *New) { - if (!Old->isDefined()) +// Compare two symbols. Return 1 if the new symbol should win, -1 if +// the new symbol should lose, or 0 if there is a conflict. +static int compare(const Symbol *Old, const Symbol *New) { + assert(New->isDefined() || New->isCommon()); + + if (!Old->isDefined() && !Old->isCommon()) return 1; + if (int Cmp = compareVersion(Old->getName(), New->getName())) return Cmp; - if (New->Binding == STB_WEAK) + + if (New->isWeak()) return -1; + if (Old->isWeak()) return 1; - return 0; -} -// We have a new non-common defined symbol with the specified binding. Return 1 -// if the new symbol should win, -1 if the new symbol should lose, or 0 if there -// is a conflict. If the new symbol wins, also update the binding. -static int compareDefinedNonCommon(const Symbol *OldSym, const Defined *New) { - if (int Cmp = compareDefined(OldSym, New)) - return Cmp; - - if (auto *Old = dyn_cast(OldSym)) { - if (Old->Section && isa(Old->Section)) { - // Non-common symbols take precedence over common symbols. - if (Config->WarnCommon) - warn("common " + Old->getName() + " is overridden"); - return 1; - } + if (Old->isCommon() && New->isCommon()) { + if (Config->WarnCommon) + warn("multiple common of " + Old->getName()); + return 0; + } - if (New->File && isa(New->File)) - return 0; + if (Old->isCommon()) { + if (Config->WarnCommon) + warn("common " + Old->getName() + " is overridden"); + return 1; + } - if (Old->Section == nullptr && New->Section == nullptr && - Old->Value == New->Value && New->Binding == STB_GLOBAL) - return -1; + if (New->isCommon()) { + if (Config->WarnCommon) + warn("common " + Old->getName() + " is overridden"); + return -1; } + + auto *OldSym = cast(Old); + auto *NewSym = cast(New); + + if (New->File && isa(New->File)) + return 0; + + if (!OldSym->Section && !NewSym->Section && OldSym->Value == NewSym->Value && + NewSym->Binding == STB_GLOBAL) + return -1; + return 0; } -Symbol *SymbolTable::addCommon(const Defined &New) { - Symbol *Old; - bool WasInserted; - std::tie(Old, WasInserted) = insert(New); - - auto Replace = [&] { - auto *Bss = make("COMMON", New.Size, New.Value); - Bss->File = New.File; - Bss->Live = !Config->GcSections; - InputSections.push_back(Bss); - - Defined Sym = New; - Sym.Value = 0; - Sym.Section = Bss; - replaceSymbol(Old, &Sym); - }; +Symbol *SymbolTable::addCommon(const CommonSymbol &New) { + Symbol *Old = insert(New); + mergeProperties(Old, New); - if (WasInserted) { - Replace(); + if (Old->isPlaceholder()) { + replaceSymbol(Old, &New); return Old; } - int Cmp = compareDefined(Old, &New); + int Cmp = compare(Old, &New); if (Cmp < 0) return Old; if (Cmp > 0) { - Replace(); - return Old; - } - - auto *D = cast(Old); - auto *Bss = dyn_cast_or_null(D->Section); - if (!Bss) { - // Non-common symbols take precedence over common symbols. - if (Config->WarnCommon) - warn("common " + Old->getName() + " is overridden"); + replaceSymbol(Old, &New); return Old; } - if (Config->WarnCommon) - warn("multiple common of " + D->getName()); + CommonSymbol *OldSym = cast(Old); - Bss->Alignment = std::max(Bss->Alignment, New.Value); - if (New.Size > Bss->Size) { - D->File = Bss->File = New.File; - D->Size = Bss->Size = New.Size; + OldSym->Alignment = std::max(OldSym->Alignment, New.Alignment); + if (OldSym->Size < New.Size) { + OldSym->File = New.File; + OldSym->Size = New.Size; } - return Old; + return OldSym; } static void reportDuplicate(Symbol *Sym, InputFile *NewFile, @@ -371,38 +363,38 @@ error(Msg); } -Defined *SymbolTable::addDefined(const Defined &New) { - Symbol *Old; - bool WasInserted; - std::tie(Old, WasInserted) = insert(New); +Symbol *SymbolTable::addDefined(const Defined &New) { + Symbol *Old = insert(New); + mergeProperties(Old, New); - if (WasInserted) { + if (Old->isPlaceholder()) { replaceSymbol(Old, &New); - return cast(Old); + return Old; } - int Cmp = compareDefinedNonCommon(Old, &New); + int Cmp = compare(Old, &New); if (Cmp > 0) replaceSymbol(Old, &New); else if (Cmp == 0) reportDuplicate(Old, New.File, dyn_cast_or_null(New.Section), New.Value); - return cast(Old); + return Old; } void SymbolTable::addShared(const SharedSymbol &New) { - Symbol *Old; - bool WasInserted; - std::tie(Old, WasInserted) = insert(New); + Symbol *Old = insert(New); + mergeProperties(Old, New); // Make sure we preempt DSO symbols with default visibility. if (New.Visibility == STV_DEFAULT) Old->ExportDynamic = true; - if (WasInserted) { + if (Old->isPlaceholder()) { replaceSymbol(Old, &New); - } else if (Old->Visibility == STV_DEFAULT && - (Old->isUndefined() || Old->isLazy())) { + return; + } + + if (Old->Visibility == STV_DEFAULT && (Old->isUndefined() || Old->isLazy())) { // An undefined symbol with non default visibility must be satisfied // in the same DSO. uint8_t Binding = Old->Binding; @@ -412,16 +404,15 @@ } Symbol *SymbolTable::addBitcode(const Defined &New) { - Symbol *Old; - bool WasInserted; - std::tie(Old, WasInserted) = insert(New); + Symbol *Old = insert(New); + mergeProperties(Old, New); - if (WasInserted) { + if (Old->isPlaceholder()) { replaceSymbol(Old, &New); return Old; } - int Cmp = compareDefinedNonCommon(Old, &New); + int Cmp = compare(Old, &New); if (Cmp > 0) replaceSymbol(Old, &New); else if (Cmp == 0) @@ -439,11 +430,10 @@ } template void SymbolTable::addLazy(const LazyT &New) { - Symbol *Old; - bool WasInserted; - std::tie(Old, WasInserted) = insert(New); + Symbol *Old = insert(New); + mergeProperties(Old, New); - if (WasInserted) { + if (Old->isPlaceholder()) { replaceSymbol(Old, &New); return; } @@ -502,7 +492,7 @@ if (!DemangledSyms) { DemangledSyms.emplace(); for (Symbol *Sym : SymVector) { - if (!Sym->isDefined()) + if (!Sym->isDefined() && !Sym->isCommon()) continue; if (Optional S = demangleItanium(Sym->getName())) (*DemangledSyms)[*S].push_back(Sym); @@ -517,7 +507,7 @@ if (Ver.IsExternCpp) return getDemangledSyms().lookup(Ver.Name); if (Symbol *B = find(Ver.Name)) - if (B->isDefined()) + if (B->isDefined() || B->isCommon()) return {B}; return {}; } @@ -534,7 +524,7 @@ } for (Symbol *Sym : SymVector) - if (Sym->isDefined() && M.match(Sym->getName())) + if ((Sym->isDefined() || Sym->isCommon()) && M.match(Sym->getName())) Res.push_back(Sym); return Res; } Index: lld/trunk/ELF/Symbols.h =================================================================== --- lld/trunk/ELF/Symbols.h +++ lld/trunk/ELF/Symbols.h @@ -51,6 +51,7 @@ enum Kind { PlaceholderKind, DefinedKind, + CommonKind, SharedKind, UndefinedKind, LazyArchiveKind, @@ -124,8 +125,11 @@ bool isWeak() const { return Binding == llvm::ELF::STB_WEAK; } bool isUndefined() const { return SymbolKind == UndefinedKind; } + bool isCommon() const { return SymbolKind == CommonKind; } bool isDefined() const { return SymbolKind == DefinedKind; } bool isShared() const { return SymbolKind == SharedKind; } + bool isPlaceholder() const { return SymbolKind == PlaceholderKind; } + bool isLocal() const { return Binding == llvm::ELF::STB_LOCAL; } bool isLazy() const { @@ -229,6 +233,40 @@ SectionBase *Section; }; +// Represents a common symbol. +// +// On Unix, it is traditionally allowed to write variable definitions +// without initialization expressions (such as "int foo;") to header +// files. Such definition is called "tentative definition". +// +// Using tentative definition is usually considered a bad practice +// because you should write only declarations (such as "extern int +// foo;") to header files. Nevertheless, the linker and the compiler +// have to do something to support bad code by allowing duplicate +// definitions for this particular case. +// +// Common symbols represent variable definitions without initializations. +// The compiler creates common symbols when it sees varaible definitions +// without initialization (you can suppress this behavior and let the +// compiler create a regular defined symbol by -fno-common). +// +// The linker allows common symbols to be replaced by regular defined +// symbols. If there are remaining common symbols after name resolution is +// complete, they are converted to regular defined symbols in a .bss +// section. (Therefore, the later passes don't see any CommonSymbols.) +class CommonSymbol : public Symbol { +public: + CommonSymbol(InputFile *File, StringRefZ Name, uint8_t Binding, + uint8_t StOther, uint8_t Type, uint64_t Alignment, uint64_t Size) + : Symbol(CommonKind, File, Name, Binding, StOther, Type), + Alignment(Alignment), Size(Size) {} + + static bool classof(const Symbol *S) { return S->isCommon(); } + + uint32_t Alignment; + uint64_t Size; +}; + class Undefined : public Symbol { public: Undefined(InputFile *File, StringRefZ Name, uint8_t Binding, uint8_t StOther, Index: lld/trunk/ELF/Symbols.cpp =================================================================== --- lld/trunk/ELF/Symbols.cpp +++ lld/trunk/ELF/Symbols.cpp @@ -122,6 +122,8 @@ case Symbol::LazyObjectKind: assert(Sym.IsUsedInRegularObj && "lazy symbol reached writer"); return 0; + case Symbol::CommonKind: + llvm_unreachable("common symbol reached writer"); case Symbol::PlaceholderKind: llvm_unreachable("placeholder symbol reached writer"); } @@ -291,7 +293,7 @@ S = ": lazy definition of "; else if (Sym->isShared()) S = ": shared definition of "; - else if (dyn_cast_or_null(cast(Sym)->Section)) + else if (Sym->isCommon()) S = ": common definition of "; else S = ": definition of "; Index: lld/trunk/ELF/Writer.cpp =================================================================== --- lld/trunk/ELF/Writer.cpp +++ lld/trunk/ELF/Writer.cpp @@ -180,14 +180,17 @@ if (!S || S->isDefined()) return nullptr; - return Symtab->addDefined(Defined{/*File=*/nullptr, Name, Binding, StOther, - STT_NOTYPE, Val, - /*Size=*/0, Sec}); + return cast(Symtab->addDefined( + Defined{/*File=*/nullptr, Name, Binding, StOther, STT_NOTYPE, Val, + /*Size=*/0, Sec})); } static Defined *addAbsolute(StringRef Name) { - return Symtab->addDefined(Defined{nullptr, Name, STB_GLOBAL, STV_HIDDEN, - STT_NOTYPE, 0, 0, nullptr}); + Defined New(nullptr, Name, STB_GLOBAL, STV_HIDDEN, STT_NOTYPE, 0, 0, nullptr); + Symbol *Sym = Symtab->addDefined(New); + if (!Sym->isDefined()) + error("duplicate symbol: " + toString(*Sym)); + return cast(Sym); } // The linker is expected to define some symbols depending on @@ -236,10 +239,10 @@ if (Config->EMachine == EM_PPC || Config->EMachine == EM_PPC64) GotOff = 0x8000; - ElfSym::GlobalOffsetTable = - Symtab->addDefined(Defined{/*File=*/nullptr, GotSymName, STB_GLOBAL, - STV_HIDDEN, STT_NOTYPE, GotOff, - /*Size=*/0, Out::ElfHeader}); + Symtab->addDefined(Defined{/*File=*/nullptr, GotSymName, STB_GLOBAL, + STV_HIDDEN, STT_NOTYPE, GotOff, /*Size=*/0, + Out::ElfHeader}); + ElfSym::GlobalOffsetTable = cast(S); } // __ehdr_start is the location of ELF file headers. Note that we define