From b5c862e15caf4d8aa34bbc6ee25af8da9a9405a4 Mon Sep 17 00:00:00 2001 From: Lang Hames Date: Fri, 17 Mar 2023 20:14:11 -0700 Subject: [PATCH] [JITLink] Store Sections in a DenseMap with the section name as key. This speeds up section lookup by name. This change was motivated by poor performance of a testcase while trying to fix the NoAlloc lifetime patch that was originally landed as 2cc64df0bd6. The NoAlloc lifetime patch causes ELF non-SHF_ALLOC sections to be given a JITLink Section (previously they were skipped), and the llvm/test/ExecutionEngine/JITLink/X86/ELF_shndex.s testcase creates > 64k non-SHF_ALLOC sections, each of which now needs to be checked to ensure that its name does not clash. Moving to a DenseMap allows us to implement this check efficiently. --- .../include/llvm/ExecutionEngine/JITLink/JITLink.h | 96 +++++++++++++--------- .../X86/COFF_comdat_associative_dead_strip.test | 5 +- 2 files changed, 59 insertions(+), 42 deletions(-) diff --git a/llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h b/llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h index 1123b35..47adf01 100644 --- a/llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h +++ b/llvm/include/llvm/ExecutionEngine/JITLink/JITLink.h @@ -826,7 +826,7 @@ private: class LinkGraph { private: - using SectionList = std::vector>; + using SectionMap = DenseMap>; using ExternalSymbolSet = DenseSet; using BlockSet = DenseSet; @@ -865,7 +865,7 @@ private: } static iterator_range - getSectionConstBlocks(Section &S) { + getSectionConstBlocks(const Section &S) { return S.blocks(); } @@ -875,15 +875,27 @@ private: } static iterator_range - getSectionConstSymbols(Section &S) { + getSectionConstSymbols(const Section &S) { return S.symbols(); } + struct GetSectionMapEntryValue { + Section &operator()(SectionMap::value_type &KV) const { return *KV.second; } + }; + + struct GetSectionMapEntryConstValue { + const Section &operator()(const SectionMap::value_type &KV) const { + return *KV.second; + } + }; + public: using external_symbol_iterator = ExternalSymbolSet::iterator; - using section_iterator = pointee_iterator; - using const_section_iterator = pointee_iterator; + using section_iterator = + mapped_iterator; + using const_section_iterator = + mapped_iterator; template getInnerRange( @@ -933,18 +945,17 @@ public: }; using defined_symbol_iterator = - nested_collection_iterator; + nested_collection_iterator; using const_defined_symbol_iterator = nested_collection_iterator; - using block_iterator = nested_collection_iterator; + using block_iterator = + nested_collection_iterator; using const_block_iterator = nested_collection_iterator &Sec) { - return Sec->getName() == Name; - }) && - "Duplicate section name"); + assert(!Sections.count(Name) && "Duplicate section name"); std::unique_ptr
Sec(new Section(Name, Prot, Sections.size())); - Sections.push_back(std::move(Sec)); - return *Sections.back(); + return *Sections.insert(std::make_pair(Name, std::move(Sec))).first->second; } /// Create a content block. @@ -1207,29 +1213,39 @@ public: } iterator_range sections() { - return make_range(section_iterator(Sections.begin()), - section_iterator(Sections.end())); + return make_range( + section_iterator(Sections.begin(), GetSectionMapEntryValue()), + section_iterator(Sections.end(), GetSectionMapEntryValue())); + } + + iterator_range sections() const { + return make_range( + const_section_iterator(Sections.begin(), + GetSectionMapEntryConstValue()), + const_section_iterator(Sections.end(), GetSectionMapEntryConstValue())); } - SectionList::size_type sections_size() const { return Sections.size(); } + size_t sections_size() const { return Sections.size(); } /// Returns the section with the given name if it exists, otherwise returns /// null. Section *findSectionByName(StringRef Name) { - for (auto &S : sections()) - if (S.getName() == Name) - return &S; - return nullptr; + auto I = Sections.find(Name); + if (I == Sections.end()) + return nullptr; + return I->second.get(); } iterator_range blocks() { - return make_range(block_iterator(Sections.begin(), Sections.end()), - block_iterator(Sections.end(), Sections.end())); + auto Secs = sections(); + return make_range(block_iterator(Secs.begin(), Secs.end()), + block_iterator(Secs.end(), Secs.end())); } iterator_range blocks() const { - return make_range(const_block_iterator(Sections.begin(), Sections.end()), - const_block_iterator(Sections.end(), Sections.end())); + auto Secs = sections(); + return make_range(const_block_iterator(Secs.begin(), Secs.end()), + const_block_iterator(Secs.end(), Secs.end())); } iterator_range external_symbols() { @@ -1241,14 +1257,15 @@ public: } iterator_range defined_symbols() { - return make_range(defined_symbol_iterator(Sections.begin(), Sections.end()), - defined_symbol_iterator(Sections.end(), Sections.end())); + auto Secs = sections(); + return make_range(defined_symbol_iterator(Secs.begin(), Secs.end()), + defined_symbol_iterator(Secs.end(), Secs.end())); } iterator_range defined_symbols() const { - return make_range( - const_defined_symbol_iterator(Sections.begin(), Sections.end()), - const_defined_symbol_iterator(Sections.end(), Sections.end())); + auto Secs = sections(); + return make_range(const_defined_symbol_iterator(Secs.begin(), Secs.end()), + const_defined_symbol_iterator(Secs.end(), Secs.end())); } /// Make the given symbol external (must not already be external). @@ -1447,11 +1464,10 @@ public: /// Remove a section. The section reference is defunct after calling this /// function and should no longer be used. void removeSection(Section &Sec) { - auto I = llvm::find_if(Sections, [&Sec](const std::unique_ptr
&S) { - return S.get() == &Sec; - }); - assert(I != Sections.end() && "Section does not appear in this graph"); - Sections.erase(I); + assert(Sections.count(Sec.getName()) && "Section not found"); + assert(Sections.find(Sec.getName())->second.get() == &Sec && + "Section map entry invalid"); + Sections.erase(Sec.getName()); } /// Accessor for the AllocActions object for this graph. This can be used to @@ -1474,7 +1490,7 @@ private: unsigned PointerSize; support::endianness Endianness; GetEdgeKindNameFunction GetEdgeKindName = nullptr; - SectionList Sections; + DenseMap> Sections; ExternalSymbolSet ExternalSymbols; ExternalSymbolSet AbsoluteSymbols; orc::shared::AllocActions AAs; diff --git a/llvm/test/ExecutionEngine/JITLink/X86/COFF_comdat_associative_dead_strip.test b/llvm/test/ExecutionEngine/JITLink/X86/COFF_comdat_associative_dead_strip.test index dd2e4bc..ad6b5a0 100644 --- a/llvm/test/ExecutionEngine/JITLink/X86/COFF_comdat_associative_dead_strip.test +++ b/llvm/test/ExecutionEngine/JITLink/X86/COFF_comdat_associative_dead_strip.test @@ -6,9 +6,10 @@ # Check a comdat child block connected by associative selection type is dead strip when # parent block is dead. # -# CHECK: section parent: +# CHECK: Link graph +# CHECK-DAG: section parent: # CHECK-EMPTY: -# CHECK-NEXT: section child: +# CHECK-DAG: section child: # CHECK-EMPTY: --- !COFF -- 2.7.4