From 07f6ce0b83ac97879e2d1010c329158ee6db17b8 Mon Sep 17 00:00:00 2001 From: Shankar Easwaran Date: Fri, 20 Mar 2015 23:47:03 +0000 Subject: [PATCH] [ELF] OrderPass : Order atoms only by ordinals. Move the init array/fini array sorting to the Output ELF writer. AFAIK, this is only needed by the X86_64/ARM ABI. This shaves time taken to self host lld by 0.2 seconds. Before patch ---------------- 4791.062059 task-clock # 1.634 CPUs utilized ( +- 0.28% ) 61,107 context-switches # 0.013 M/sec ( +- 0.56% ) 2.932902671 seconds time elapsed ( +- 0.84% ) After patch ------------- 4608.417248 task-clock # 1.669 CPUs utilized ( +- 0.30% ) 61,616 context-switches # 0.013 M/sec ( +- 0.63% ) 2.761012703 seconds time elapsed ( +- 0.63% ) llvm-svn: 232866 --- lld/lib/ReaderWriter/ELF/DefaultLayout.h | 55 ++++++++++++++++++++++ lld/lib/ReaderWriter/ELF/OrderPass.h | 40 +--------------- .../ReaderWriter/ELF/X86_64/X86_64TargetHandler.h | 5 ++ lld/test/elf/init_array-order.test | 14 ++---- 4 files changed, 66 insertions(+), 48 deletions(-) diff --git a/lld/lib/ReaderWriter/ELF/DefaultLayout.h b/lld/lib/ReaderWriter/ELF/DefaultLayout.h index 05c7cdd..de03ce1 100644 --- a/lld/lib/ReaderWriter/ELF/DefaultLayout.h +++ b/lld/lib/ReaderWriter/ELF/DefaultLayout.h @@ -316,13 +316,25 @@ public: return _copiedDynSymNames.count(sla->name()); } + /// \brief Handle SORT_BY_PRIORITY. + void sortOutputSectionByPriority(StringRef outputSectionName, + StringRef prefix); + protected: + /// \brief TargetLayouts may use these functions to reorder the input sections + /// in a order defined by their ABI. + virtual void finalizeOutputSectionLayout() {} + /// \brief Allocate a new section. virtual AtomSection *createSection( StringRef name, int32_t contentType, DefinedAtom::ContentPermissions contentPermissions, SectionOrder sectionOrder); +private: + /// Helper function that returns the priority value from an input section. + uint32_t getPriorityFromSectionName(StringRef sectionName) const; + protected: llvm::BumpPtrAllocator _allocator; SectionMapT _sectionMap; @@ -657,13 +669,56 @@ template void DefaultLayout::createOutputSections() { } } +template +uint32_t +DefaultLayout::getPriorityFromSectionName(StringRef sectionName) const { + StringRef priority = sectionName.drop_front().rsplit('.').second; + uint32_t prio; + if (priority.getAsInteger(10, prio)) + return std::numeric_limits::max(); + return prio; +} + +template +void DefaultLayout::sortOutputSectionByPriority( + StringRef outputSectionName, StringRef prefix) { + OutputSection *outputSection = findOutputSection(outputSectionName); + if (!outputSection) + return; + + auto sections = outputSection->sections(); + + std::sort(sections.begin(), sections.end(), + [&](Chunk *lhs, Chunk *rhs) { + Section *lhsSection = dyn_cast>(lhs); + Section *rhsSection = dyn_cast>(rhs); + if (!lhsSection || !rhsSection) + return false; + StringRef lhsSectionName = lhsSection->inputSectionName(); + StringRef rhsSectionName = rhsSection->inputSectionName(); + + if (!prefix.empty()) { + if (!lhsSectionName.startswith(prefix) || + !rhsSectionName.startswith(prefix)) + return false; + } + return getPriorityFromSectionName(lhsSectionName) < + getPriorityFromSectionName(rhsSectionName); + }); +}; + template void DefaultLayout::assignSectionsToSegments() { ScopedTask task(getDefaultDomain(), "assignSectionsToSegments"); ELFLinkingContext::OutputMagic outputMagic = _context.getOutputMagic(); // sort the sections by their order as defined by the layout sortInputSections(); + // Create output sections. createOutputSections(); + + // Finalize output section layout. + finalizeOutputSectionLayout(); + // Set the ordinal after sorting the sections int ordinal = 1; for (auto osi : _outputSections) { diff --git a/lld/lib/ReaderWriter/ELF/OrderPass.h b/lld/lib/ReaderWriter/ELF/OrderPass.h index 0948485..d126b83 100644 --- a/lld/lib/ReaderWriter/ELF/OrderPass.h +++ b/lld/lib/ReaderWriter/ELF/OrderPass.h @@ -17,49 +17,13 @@ namespace lld { namespace elf { /// \brief This pass sorts atoms by file and atom ordinals. -/// .{init,fini}_array. sections are handled specially. class OrderPass : public Pass { public: void perform(std::unique_ptr &file) override { - MutableFile::DefinedAtomRange defined = file->definedAtoms(); - auto last = std::partition(defined.begin(), defined.end(), isInitFini); - parallel_sort(defined.begin(), last, compareInitFini); - parallel_sort(last, defined.end(), DefinedAtom::compareByPosition); - } - -private: - static bool isInitFini(const DefinedAtom *atom) { - if (atom->sectionChoice() != DefinedAtom::sectionCustomRequired) - return false; - StringRef name = atom->customSectionName(); - return name.startswith(".init_array") || name.startswith(".fini_array"); - } - - // Parses the number in .{init,fini}_array.. - // Returns UINT32_MAX by default. - static uint32_t getPriority(const DefinedAtom *atom) { - StringRef sec = atom->customSectionName(); - StringRef num = sec.drop_front().rsplit('.').second; - uint32_t prio; - if (num.getAsInteger(10, prio)) - return std::numeric_limits::max(); - return prio; - } - - static bool compareInitFini(const DefinedAtom *lhs, const DefinedAtom *rhs) { - // Sort {.init_array, .fini_array}[.] sections - // according to their number. Sections without optional - // numer suffix should go last. - uint32_t lp = getPriority(lhs); - uint32_t rp = getPriority(rhs); - if (lp != rp) - return lp < rp; - - // If both atoms have the same priority, fall back to default. - return DefinedAtom::compareByPosition(lhs, rhs); + parallel_sort(file->definedAtoms().begin(), file->definedAtoms().end(), + DefinedAtom::compareByPosition); } }; - } } diff --git a/lld/lib/ReaderWriter/ELF/X86_64/X86_64TargetHandler.h b/lld/lib/ReaderWriter/ELF/X86_64/X86_64TargetHandler.h index 24cdd98..57da7bc 100644 --- a/lld/lib/ReaderWriter/ELF/X86_64/X86_64TargetHandler.h +++ b/lld/lib/ReaderWriter/ELF/X86_64/X86_64TargetHandler.h @@ -24,6 +24,11 @@ class X86_64TargetLayout : public TargetLayout { public: X86_64TargetLayout(X86_64LinkingContext &context) : TargetLayout(context) {} + + void finalizeOutputSectionLayout() override { + sortOutputSectionByPriority(".init_array", ".init_array"); + sortOutputSectionByPriority(".fini_array", ".fini_array"); + } }; class X86_64TargetHandler diff --git a/lld/test/elf/init_array-order.test b/lld/test/elf/init_array-order.test index 1ebb24b..b57b380 100644 --- a/lld/test/elf/init_array-order.test +++ b/lld/test/elf/init_array-order.test @@ -1,6 +1,7 @@ #RUN: yaml2obj -format=elf %s > %t #RUN: lld -flavor gnu -target x86_64-linux %t --noinhibit-exec \ -#RUN: --output-filetype=yaml | FileCheck %s +#RUN: -o %t1.out +#RUN: llvm-objdump -s %t1.out | FileCheck %s !ELF FileHeader: @@ -62,12 +63,5 @@ Symbols: Type: STT_SECTION Section: .init_array -#CHECK: defined-atoms: -#CHECK: content: [ 01, -#CHECK: section-name: .init_array.1 -#CHECK: content: [ 02, -#CHECK: section-name: .init_array.2 -#CHECK: content: [ 03, -#CHECK: section-name: .init_array.3 -#CHECK: content: [ 99, -#CHECK: section-name: .init_array +#CHECK: {{[0xa-f0-9]+}} 01000000 00000000 02000000 00000000 +#CHECK: {{[0xa-f0-9]+}} 03000000 00000000 99000000 00000000 -- 2.7.4