Index: ELF/MarkLive.cpp =================================================================== --- ELF/MarkLive.cpp +++ ELF/MarkLive.cpp @@ -41,66 +41,72 @@ using namespace lld; using namespace lld::elf; +namespace { +template class MarkLive { +public: + void run(); + +private: + void enqueue(InputSectionBase *Sec, uint64_t Offset); + void markSymbol(Symbol *Sym); + + template + void resolveReloc(InputSectionBase &Sec, RelTy &Rel, bool IsLSDA); + + template + void scanEhFrameSection(EhInputSection &EH, ArrayRef Rels); + + // A list of sections to visit. + SmallVector Queue; + + // There are normally few input sections whose names are valid C + // identifiers, so we just store a std::vector instead of a multimap. + DenseMap> CNamedSections; +}; +} // namespace + template -static typename ELFT::uint getAddend(InputSectionBase &Sec, - const typename ELFT::Rel &Rel) { +static uint64_t getAddend(InputSectionBase &Sec, + const typename ELFT::Rel &Rel) { return Target->getImplicitAddend(Sec.data().begin() + Rel.r_offset, Rel.getType(Config->IsMips64EL)); } template -static typename ELFT::uint getAddend(InputSectionBase &Sec, - const typename ELFT::Rela &Rel) { +static uint64_t getAddend(InputSectionBase &Sec, + const typename ELFT::Rela &Rel) { return Rel.r_addend; } -// There are normally few input sections whose names are valid C -// identifiers, so we just store a std::vector instead of a multimap. -static DenseMap> CNamedSections; - -template -static void -resolveReloc(InputSectionBase &Sec, RelT &Rel, - llvm::function_ref Fn) { - Symbol &B = Sec.getFile()->getRelocTargetSym(Rel); +template +template +void MarkLive::resolveReloc(InputSectionBase &Sec, RelTy &Rel, + bool IsLSDA) { + Symbol &Sym = Sec.getFile()->getRelocTargetSym(Rel); // If a symbol is referenced in a live section, it is used. - B.Used = true; - if (auto *SS = dyn_cast(&B)) - if (!SS->isWeak()) - SS->getFile().IsNeeded = true; + Sym.Used = true; - if (auto *D = dyn_cast(&B)) { + if (auto *D = dyn_cast(&Sym)) { auto *RelSec = dyn_cast_or_null(D->Section); if (!RelSec) return; + uint64_t Offset = D->Value; if (D->isSection()) Offset += getAddend(Sec, Rel); - Fn(RelSec, Offset); + + if (!IsLSDA || !(RelSec->Flags & SHF_EXECINSTR)) + enqueue(RelSec, Offset); return; } - if (!B.isDefined()) - for (InputSectionBase *Sec : CNamedSections.lookup(B.getName())) - Fn(Sec, 0); -} - -// Calls Fn for each section that Sec refers to via relocations. -template -static void -forEachSuccessor(InputSection &Sec, - llvm::function_ref Fn) { - if (Sec.AreRelocsRela) { - for (const typename ELFT::Rela &Rel : Sec.template relas()) - resolveReloc(Sec, Rel, Fn); - } else { - for (const typename ELFT::Rel &Rel : Sec.template rels()) - resolveReloc(Sec, Rel, Fn); - } + if (auto *SS = dyn_cast(&Sym)) + if (!SS->isWeak()) + SS->getFile().IsNeeded = true; - for (InputSectionBase *IS : Sec.DependentSections) - Fn(IS, 0); + for (InputSectionBase *Sec : CNamedSections.lookup(Sym.getName())) + enqueue(Sec, 0); } // The .eh_frame section is an unfortunate special case. @@ -117,54 +123,33 @@ // A possible improvement would be to fully process .eh_frame in the middle of // the gc pass. With that we would be able to also gc some sections holding // LSDAs and personality functions if we found that they were unused. -template -static void -scanEhFrameSection(EhInputSection &EH, ArrayRef Rels, - llvm::function_ref Fn) { - const endianness E = ELFT::TargetEndianness; - - for (unsigned I = 0, N = EH.Pieces.size(); I < N; ++I) { +template +template +void MarkLive::scanEhFrameSection(EhInputSection &EH, + ArrayRef Rels) { + for (size_t I = 0, End = EH.Pieces.size(); I < End; ++I) { EhSectionPiece &Piece = EH.Pieces[I]; - unsigned FirstRelI = Piece.FirstRelocation; + size_t FirstRelI = Piece.FirstRelocation; if (FirstRelI == (unsigned)-1) continue; - if (read32(Piece.data().data() + 4) == 0) { + + if (read32(Piece.data().data() + 4) == 0) { // This is a CIE, we only need to worry about the first relocation. It is // known to point to the personality function. - resolveReloc(EH, Rels[FirstRelI], Fn); + resolveReloc(EH, Rels[FirstRelI], false); continue; } + // This is a FDE. The relocations point to the described function or to // a LSDA. We only need to keep the LSDA alive, so ignore anything that // points to executable sections. - typename ELFT::uint PieceEnd = Piece.InputOff + Piece.Size; - for (unsigned I2 = FirstRelI, N2 = Rels.size(); I2 < N2; ++I2) { - const RelTy &Rel = Rels[I2]; - if (Rel.r_offset >= PieceEnd) - break; - resolveReloc(EH, Rels[I2], - [&](InputSectionBase *Sec, uint64_t Offset) { - if (Sec && Sec != &InputSection::Discarded && - !(Sec->Flags & SHF_EXECINSTR)) - Fn(Sec, 0); - }); - } + uint64_t PieceEnd = Piece.InputOff + Piece.Size; + for (size_t J = FirstRelI, End2 = Rels.size(); J < End2; ++J) + if (Rels[J].r_offset < PieceEnd) + resolveReloc(EH, Rels[J], true); } } -template -static void -scanEhFrameSection(EhInputSection &EH, - llvm::function_ref Fn) { - if (!EH.NumRelocations) - return; - - if (EH.AreRelocsRela) - scanEhFrameSection(EH, EH.template relas(), Fn); - else - scanEhFrameSection(EH, EH.template rels(), Fn); -} - // Some sections are used directly by the loader, so they should never be // garbage-collected. This function returns true if a given section is such // section. @@ -183,57 +168,54 @@ } } -// This is the main function of the garbage collector. -// Starting from GC-root sections, this function visits all reachable -// sections to set their "Live" bits. -template static void doGcSections() { - SmallVector Q; - CNamedSections.clear(); - - auto Enqueue = [&](InputSectionBase *Sec, uint64_t Offset) { - // Skip over discarded sections. This in theory shouldn't happen, because - // the ELF spec doesn't allow a relocation to point to a deduplicated - // COMDAT section directly. Unfortunately this happens in practice (e.g. - // .eh_frame) so we need to add a check. - if (Sec == &InputSection::Discarded) - return; +template +void MarkLive::enqueue(InputSectionBase *Sec, uint64_t Offset) { + // Skip over discarded sections. This in theory shouldn't happen, because + // the ELF spec doesn't allow a relocation to point to a deduplicated + // COMDAT section directly. Unfortunately this happens in practice (e.g. + // .eh_frame) so we need to add a check. + if (Sec == &InputSection::Discarded) + return; + // Usually, a whole section is marked as live or dead, but in mergeable + // (splittable) sections, each piece of data has independent liveness bit. + // So we explicitly tell it which offset is in use. + if (auto *MS = dyn_cast(Sec)) + MS->getSectionPiece(Offset)->Live = true; - // Usually, a whole section is marked as live or dead, but in mergeable - // (splittable) sections, each piece of data has independent liveness bit. - // So we explicitly tell it which offset is in use. - if (auto *MS = dyn_cast(Sec)) - MS->getSectionPiece(Offset)->Live = true; + if (Sec->Live) + return; + Sec->Live = true; - if (Sec->Live) - return; - Sec->Live = true; + // Add input section to the queue. + if (InputSection *S = dyn_cast(Sec)) + Queue.push_back(S); +} - // Add input section to the queue. - if (InputSection *S = dyn_cast(Sec)) - Q.push_back(S); - }; - - auto MarkSymbol = [&](Symbol *Sym) { - if (auto *D = dyn_cast_or_null(Sym)) - if (auto *IS = dyn_cast_or_null(D->Section)) - Enqueue(IS, D->Value); - }; +template void MarkLive::markSymbol(Symbol *Sym) { + if (auto *D = dyn_cast_or_null(Sym)) + if (auto *IS = dyn_cast_or_null(D->Section)) + enqueue(IS, D->Value); +} +// This is the main function of the garbage collector. +// Starting from GC-root sections, this function visits all reachable +// sections to set their "Live" bits. +template void MarkLive::run() { // Add GC root symbols. - MarkSymbol(Symtab->find(Config->Entry)); - MarkSymbol(Symtab->find(Config->Init)); - MarkSymbol(Symtab->find(Config->Fini)); + markSymbol(Symtab->find(Config->Entry)); + markSymbol(Symtab->find(Config->Init)); + markSymbol(Symtab->find(Config->Fini)); for (StringRef S : Config->Undefined) - MarkSymbol(Symtab->find(S)); + markSymbol(Symtab->find(S)); for (StringRef S : Script->ReferencedSymbols) - MarkSymbol(Symtab->find(S)); + markSymbol(Symtab->find(S)); // Preserve externally-visible symbols if the symbols defined by this // file can interrupt other ELF file's symbols at runtime. for (Symbol *S : Symtab->getSymbols()) if (S->includeInDynsym()) - MarkSymbol(S); + markSymbol(S); // Preserve special sections and those which are specified in linker // script KEEP command. @@ -244,14 +226,20 @@ // referenced by .eh_frame sections, so we scan them for that here. if (auto *EH = dyn_cast(Sec)) { EH->Live = true; - scanEhFrameSection(*EH, Enqueue); + if (!EH->NumRelocations) + continue; + + if (EH->AreRelocsRela) + scanEhFrameSection(*EH, EH->template relas()); + else + scanEhFrameSection(*EH, EH->template rels()); } if (Sec->Flags & SHF_LINK_ORDER) continue; if (isReserved(Sec) || Script->shouldKeep(Sec)) { - Enqueue(Sec, 0); + enqueue(Sec, 0); } else if (isValidCIdentifier(Sec->Name)) { CNamedSections[Saver.save("__start_" + Sec->Name)].push_back(Sec); CNamedSections[Saver.save("__stop_" + Sec->Name)].push_back(Sec); @@ -259,16 +247,28 @@ } // Mark all reachable sections. - while (!Q.empty()) - forEachSuccessor(*Q.pop_back_val(), Enqueue); + while (!Queue.empty()) { + InputSectionBase &Sec = *Queue.pop_back_val(); + + if (Sec.AreRelocsRela) { + for (const typename ELFT::Rela &Rel : Sec.template relas()) + resolveReloc(Sec, Rel, false); + } else { + for (const typename ELFT::Rel &Rel : Sec.template rels()) + resolveReloc(Sec, Rel, false); + } + + for (InputSectionBase *IS : Sec.DependentSections) + enqueue(IS, 0); + } } // Before calling this function, Live bits are off for all // input sections. This function make some or all of them on // so that they are emitted to the output file. template void elf::markLive() { + // If -gc-sections is not given, no sections are removed. if (!Config->GcSections) { - // If -gc-sections is missing, no sections are removed. for (InputSectionBase *Sec : InputSections) Sec->Live = true; @@ -280,6 +280,8 @@ return; } + // Otheriwse, do mark-sweep GC. + // // The -gc-sections option works only for SHF_ALLOC sections // (sections that are memory-mapped at runtime). So we can // unconditionally make non-SHF_ALLOC sections alive except @@ -303,12 +305,13 @@ bool IsAlloc = (Sec->Flags & SHF_ALLOC); bool IsLinkOrder = (Sec->Flags & SHF_LINK_ORDER); bool IsRel = (Sec->Type == SHT_REL || Sec->Type == SHT_RELA); + if (!IsAlloc && !IsLinkOrder && !IsRel) Sec->Live = true; } // Follow the graph to mark all live sections. - doGcSections(); + MarkLive().run(); // Report garbage-collected sections. if (Config->PrintGcSections)