Avoid calculating the string hash twice in GsymCreator::insertString.

[simon.giesecke]

Summary

Do the single hash calculation before acquiring the lock, to reduce
lock contention. If Copy is true, and the string was not yet contained
in the StringStorage, use the new address from StringStorage, but
reuse the hash we already calculated.

Move FunctionInfo in addFunctionInfo rather than copying.

Use a non-recursive mutex in GsymCreator.

There doesn't seem to be a need to support recursive locking,
and a recursive mutex is unnecessarily inefficient.

Avoid underestimating the number of DIEs for a given debug info size.

Calculate indexes of last child of each DWARF entry once during tryExtractDIEsIfNeeded.

This ensures that the last child indexes are calculated in linear time and
can later be queried in constant time by getLastChild.

The baseline situation was that individual calls to getLastChild were linear in the
size of DieArray. Calling getLastChild once for every DWARFDebugInfoEntry was
amortized quadratic in the size of DieArray.

Reformat DWARFUnit.cpp

llvm/include/llvm/DebugInfo/DWARF/DWARFUnit.h

 //===- DWARFUnit.h ----------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 
class DWARFUnit {
   /// Start, length, and DWARF format of the unit's contribution to the string
   /// offsets table (DWARF v5).
   Optional<StrOffsetsContributionDescriptor> StringOffsetsTableContribution;
 
   mutable const DWARFAbbreviationDeclarationSet *Abbrevs;
   llvm::Optional<object::SectionedAddress> BaseAddr;
   /// The compile unit debug information entry items.
   std::vector<DWARFDebugInfoEntry> DieArray;
+  std::vector<size_t> LastChildren;
 
   /// Map from range's start address to end address and corresponding DIE.
   /// IntervalMap does not support range removal, as a result, we use the
   /// std::map::upper_bound for address range lookup.
   std::map<uint64_t, std::pair<uint64_t, DWARFDie>> AddrDieMap;
 
   using die_iterator_range =
       iterator_range<std::vector<DWARFDebugInfoEntry>::iterator>;

llvm/include/llvm/DebugInfo/GSYM/GsymCreator.h

 //===- GsymCreator.h --------------------------------------------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 

 ///
 /// The function info data is the payload that contains information about the
 /// address that is being looked up. It contains all of the encoded
 /// FunctionInfo objects. Each encoded FunctionInfo's data is pointed to by an
 /// entry in the Function Info Offsets Table. For details on the exact encoding
 /// of FunctionInfo objects, see "llvm/DebugInfo/GSYM/FunctionInfo.h".
 class GsymCreator {
   // Private member variables require Mutex protections
-  mutable std::recursive_mutex Mutex;
+  mutable std::mutex Mutex;
   std::vector<FunctionInfo> Funcs;
   StringTableBuilder StrTab;
   StringSet<> StringStorage;
   DenseMap<llvm::gsym::FileEntry, uint32_t> FileEntryToIndex;
   std::vector<llvm::gsym::FileEntry> Files;
   std::vector<uint8_t> UUID;
   Optional<AddressRanges> ValidTextRanges;
   AddressRanges Ranges;

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

 //===- DWARFUnit.cpp ------------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 

 #include "llvm/Support/DataExtractor.h"
 #include "llvm/Support/Errc.h"
 #include "llvm/Support/Path.h"
 #include <algorithm>
 #include <cassert>
 #include <cstddef>
 #include <cstdint>
 #include <cstdio>
+#include <stack>
 #include <utility>
 #include <vector>
 
 using namespace llvm;
 using namespace dwarf;
 
 void DWARFUnitVector::addUnitsForSection(DWARFContext &C,
                                          const DWARFSection &Section,
                                          DWARFSectionKind SectionKind) {
   const DWARFObject &D = C.getDWARFObj();
   addUnitsImpl(C, D, Section, C.getDebugAbbrev(), &D.getRangesSection(),
-               &D.getLocSection(), D.getStrSection(),
-               D.getStrOffsetsSection(), &D.getAddrSection(),
-               D.getLineSection(), D.isLittleEndian(), false, false,
-               SectionKind);
+               &D.getLocSection(), D.getStrSection(), D.getStrOffsetsSection(),
+               &D.getAddrSection(), D.getLineSection(), D.isLittleEndian(),
+               false, false, SectionKind);
 }
 
 void DWARFUnitVector::addUnitsForDWOSection(DWARFContext &C,
                                             const DWARFSection &DWOSection,
                                             DWARFSectionKind SectionKind,
                                             bool Lazy) {
   const DWARFObject &D = C.getDWARFObj();
-  addUnitsImpl(C, D, DWOSection, C.getDebugAbbrevDWO(), &D.getRangesDWOSection(),
-               &D.getLocDWOSection(), D.getStrDWOSection(),
-               D.getStrOffsetsDWOSection(), &D.getAddrSection(),
-               D.getLineDWOSection(), C.isLittleEndian(), true, Lazy,
-               SectionKind);
+  addUnitsImpl(C, D, DWOSection, C.getDebugAbbrevDWO(),
+               &D.getRangesDWOSection(), &D.getLocDWOSection(),
+               D.getStrDWOSection(), D.getStrOffsetsDWOSection(),
+               &D.getAddrSection(), D.getLineDWOSection(), C.isLittleEndian(),
+               true, Lazy, SectionKind);
 }
 
 void DWARFUnitVector::addUnitsImpl(
     DWARFContext &Context, const DWARFObject &Obj, const DWARFSection &Section,
     const DWARFDebugAbbrev *DA, const DWARFSection *RS,
     const DWARFSection *LocSection, StringRef SS, const DWARFSection &SOS,
     const DWARFSection *AOS, const DWARFSection &LS, bool LE, bool IsDWO,
     bool Lazy, DWARFSectionKind SectionKind) {
Parser = [=, &Context, &Obj, &Section, &SOS,
             Context, Header.isTypeUnit() ? DW_SECT_EXT_TYPES : DW_SECT_INFO);
         IndexEntry = Index.getFromOffset(Header.getOffset());
       }
       if (IndexEntry && !Header.applyIndexEntry(IndexEntry))
         return nullptr;
       std::unique_ptr<DWARFUnit> U;
       if (Header.isTypeUnit())
         U = std::make_unique<DWARFTypeUnit>(Context, InfoSection, Header, DA,
-                                             RS, LocSection, SS, SOS, AOS, LS,
-                                             LE, IsDWO, *this);
       else
-        U = std::make_unique<DWARFCompileUnit>(Context, InfoSection, Header,
-                                                DA, RS, LocSection, SS, SOS,
-                                                AOS, LS, LE, IsDWO, *this);
+        U = std::make_unique<DWARFCompileUnit>(Context, InfoSection, Header, DA,
+                                               RS, LocSection, SS, SOS, AOS, LS,
+                                               LE, IsDWO, *this);
       return U;
     };
   }
   if (Lazy)
     return;
   // Find a reasonable insertion point within the vector.  We skip over
   // (a) units from a different section, (b) units from the same section
   // but with lower offset-within-section.  This keeps units in order
bool DWARFUnitHeader::applyIndexEntry(const DWARFUnitIndex::Entry *Entry) {
   if (!AbbrEntry)
     return false;
   AbbrOffset = AbbrEntry->Offset;
   return true;
 }
 
 // Parse the rangelist table header, including the optional array of offsets
 // following it (DWARF v5 and later).
-template<typename ListTableType>
-static Expected<ListTableType>
-parseListTableHeader(DWARFDataExtractor &DA, uint64_t Offset,
+template <typename ListTableType>
+static Expected<ListTableType> parseListTableHeader(DWARFDataExtractor &DA,
+                                                    uint64_t Offset,
                                                     DwarfFormat Format) {
   // We are expected to be called with Offset 0 or pointing just past the table
   // header. Correct Offset in the latter case so that it points to the start
   // of the header.
   if (Offset > 0) {
     uint64_t HeaderSize = DWARFListTableHeader::getHeaderSize(Format);
     if (Offset < HeaderSize)
-      return createStringError(errc::invalid_argument, "did not detect a valid"
+      return createStringError(errc::invalid_argument,
+                               "did not detect a valid"
                                " list table with base = 0x%" PRIx64 "\n",
                                Offset);
     Offset -= HeaderSize;
   }
   ListTableType Table;
   if (Error E = Table.extractHeaderAndOffsets(DA, &Offset))
     return std::move(E);
   return Table;
void DWARFUnit::extractDIEsToVector(
   // next compilation unit header.
   uint64_t DIEOffset = getOffset() + getHeaderSize();
   uint64_t NextCUOffset = getNextUnitOffset();
   DWARFDebugInfoEntry DIE;
   DWARFDataExtractor DebugInfoData = getDebugInfoExtractor();
   uint32_t Depth = 0;
   bool IsCUDie = true;
 
-  while (DIE.extractFast(*this, &DIEOffset, DebugInfoData, NextCUOffset,
-                         Depth)) {
+  while (
+      DIE.extractFast(*this, &DIEOffset, DebugInfoData, NextCUOffset, Depth)) {
     if (IsCUDie) {
       if (AppendCUDie)
         Dies.push_back(DIE);
       if (!AppendNonCUDies)
         break;
       // The average bytes per DIE entry has been seen to be
-      // around 14-20 so let's pre-reserve the needed memory for
+      // around 6-12 so let's pre-reserve the needed memory for
       // our DIE entries accordingly.
-      Dies.reserve(Dies.size() + getDebugInfoSize() / 14);
+      Dies.reserve(Dies.size() + getDebugInfoSize() / 6);
       IsCUDie = false;
     } else {
       Dies.push_back(DIE);
     }
 
     if (const DWARFAbbreviationDeclaration *AbbrDecl =
             DIE.getAbbreviationDeclarationPtr()) {
       // Normal DIE
       if (AbbrDecl->hasChildren())
         ++Depth;
     } else {
       // NULL DIE.
       if (Depth > 0)
         --Depth;
       if (Depth == 0)
-        break;  // We are done with this compile unit!
+        break; // We are done with this compile unit!
     }
   }
 
+  Dies.shrink_to_fit();
+
   // Give a little bit of info if we encounter corrupt DWARF (our offset
   // should always terminate at or before the start of the next compilation
   // unit header).
   if (DIEOffset > NextCUOffset)
     Context.getWarningHandler()(
         createStringError(errc::invalid_argument,
                           "DWARF compile unit extends beyond its "
                           "bounds cu 0x%8.8" PRIx64 " "
                           "at 0x%8.8" PRIx64 "\n",
                           getOffset(), DIEOffset));
 }
 
 void DWARFUnit::extractDIEsIfNeeded(bool CUDieOnly) {
   if (Error e = tryExtractDIEsIfNeeded(CUDieOnly))
     Context.getRecoverableErrorHandler()(std::move(e));
 }
 
+template <typename In, typename GetDepthFunc, typename HasChildrenPred,
+          typename IsEndTagPred>
+auto findLastChildren(const In &InRange, const GetDepthFunc &GetDepth,
+                      const HasChildrenPred &HasChildren,
+                      const IsEndTagPred &IsEndTag) {
+  using DepthType = decltype(GetDepth(*InRange.begin()));
+  using IndexType = typename In::size_type;
+
+  std::vector<IndexType> LastChildren(InRange.size(), 0);
+
+  std::stack<DepthType, std::vector<IndexType>> ParentIdxs;
+  for (IndexType I = 0, EndIdx = InRange.size(); I < EndIdx; ++I) {
+    if (!ParentIdxs.empty()) {
+      DepthType CurrentDepth = GetDepth(InRange[I]);
+
+      DepthType StackSize = ParentIdxs.size();
+      if (CurrentDepth <= StackSize) {
+        // a child of the current parent
+        while (CurrentDepth < StackSize--) {
+          ParentIdxs.pop();
+        }
+
+        assert(!LastChildren[ParentIdxs.top()]);
+
+        if (IsEndTag(InRange[I])) {
+          // the last child of the current parent
+          LastChildren[ParentIdxs.top()] = I;
+        }
+      }
+    }
+
+    if (HasChildren(InRange[I])) {
+      assert(GetDepth(InRange[I]) == ParentIdxs.size());
+      ParentIdxs.push(I);
+    }
+  }
+
+  return LastChildren;
+}
+
 Error DWARFUnit::tryExtractDIEsIfNeeded(bool CUDieOnly) {
-  if ((CUDieOnly && !DieArray.empty()) ||
-      DieArray.size() > 1)
+  if ((CUDieOnly && !DieArray.empty()) || DieArray.size() > 1)
     return Error::success(); // Already parsed.
 
   bool HasCUDie = !DieArray.empty();
   extractDIEsToVector(!HasCUDie, !CUDieOnly, DieArray);
 
   if (DieArray.empty())
     return Error::success();
 
LocTable = std::make_unique<DWARFDebugLoclists>(
                            isLittleEndian, getAddressByteSize()),
         getVersion());
   } else {
     LocTable = std::make_unique<DWARFDebugLoc>(DWARFDataExtractor(
         Context.getDWARFObj(), Context.getDWARFObj().getLocSection(),
         isLittleEndian, getAddressByteSize()));
   }
 
+  LastChildren =
+      findLastChildren(DieArray, std::mem_fn(&DWARFDebugInfoEntry::getDepth),
+                       std::mem_fn(&DWARFDebugInfoEntry::hasChildren),
+                       [](const DWARFDebugInfoEntry &DIE) {
+                         return DIE.getTag() == dwarf::DW_TAG_null;
+                       });
+
   // Don't fall back to DW_AT_GNU_ranges_base: it should be ignored for
   // skeleton CU DIE, so that DWARF users not aware of it are not broken.
   return Error::success();
 }
 
 bool DWARFUnit::parseDWO() {
   if (IsDWO)
     return false;
if (R == AddrDieMap.begin())
     return DWARFDie();
   // upper_bound's previous item contains Address.
   --R;
   if (Address >= R->second.first)
     return DWARFDie();
   return R->second.second;
 }
 
-void
-DWARFUnit::getInlinedChainForAddress(uint64_t Address,
-                                     SmallVectorImpl<DWARFDie> &InlinedChain) {
+void DWARFUnit::getInlinedChainForAddress(
+    uint64_t Address, SmallVectorImpl<DWARFDie> &InlinedChain) {
   assert(InlinedChain.empty());
   // Try to look for subprogram DIEs in the DWO file.
   parseDWO();
   // First, find the subroutine that contains the given address (the leaf
   // of inlined chain).
   DWARFDie SubroutineDIE =
       (DWO ? *DWO : *this).getSubroutineForAddress(Address);
 
   while (SubroutineDIE) {
     if (SubroutineDIE.isSubprogramDIE()) {
       InlinedChain.push_back(SubroutineDIE);
       return;
     }
     if (SubroutineDIE.getTag() == DW_TAG_inlined_subroutine)
       InlinedChain.push_back(SubroutineDIE);
-    SubroutineDIE  = SubroutineDIE.getParent();
+    SubroutineDIE = SubroutineDIE.getParent();
   }
 }
 
 const DWARFUnitIndex &llvm::getDWARFUnitIndex(DWARFContext &Context,
                                               DWARFSectionKind Kind) {
   if (Kind == DW_SECT_INFO)
     return Context.getCUIndex();
   assert(Kind == DW_SECT_EXT_TYPES);
if (I >= DieArray.size())
     return DWARFDie();
   return DWARFDie(this, &DieArray[I]);
 }
 
 DWARFDie DWARFUnit::getLastChild(const DWARFDebugInfoEntry *Die) {
   if (!Die->hasChildren())
     return DWARFDie();
 
-  uint32_t Depth = Die->getDepth();
-  for (size_t I = getDIEIndex(Die) + 1, EndIdx = DieArray.size(); I < EndIdx;
-       ++I) {
-    if (DieArray[I].getDepth() == Depth + 1 &&
-        DieArray[I].getTag() == dwarf::DW_TAG_null)
-      return DWARFDie(this, &DieArray[I]);
-    assert(DieArray[I].getDepth() > Depth && "Not processing children?");
-  }
+  // We do not want access out of bounds when parsing corrupted debug data.
+  size_t I = getDIEIndex(Die);
+  if (I >= LastChildren.size())
     return DWARFDie();
+  size_t LastChild = LastChildren[I];
+  if (!LastChild) {
+    // TODO Shouldn't Die->hasChildren() be false in that case?
+    return DWARFDie();
+  }
+  return DWARFDie(this, &DieArray[LastChild]);
 }
 
 const DWARFAbbreviationDeclarationSet *DWARFUnit::getAbbreviations() const {
   if (!Abbrevs)
     Abbrevs = Abbrev->getAbbreviationDeclarationSet(Header.getAbbrOffset());
   return Abbrevs;
 }
 
StrOffsetsContributionDescriptor::validateContributionSize(
   uint8_t EntrySize = getDwarfOffsetByteSize();
   // In order to ensure that we don't read a partial record at the end of
   // the section we validate for a multiple of the entry size.
   uint64_t ValidationSize = alignTo(Size, EntrySize);
   // Guard against overflow.
   if (ValidationSize >= Size)
     if (DA.isValidOffsetForDataOfSize((uint32_t)Base, ValidationSize))
       return *this;
-  return createStringError(errc::invalid_argument, "length exceeds section size");
+  return createStringError(errc::invalid_argument,
+                           "length exceeds section size");
 }
 
 // Look for a DWARF64-formatted contribution to the string offsets table
 // starting at a given offset and record it in a descriptor.
 static Expected<StrOffsetsContributionDescriptor>
 parseDWARF64StringOffsetsTableHeader(DWARFDataExtractor &DA, uint64_t Offset) {
   if (!DA.isValidOffsetForDataOfSize(Offset, 16))
-    return createStringError(errc::invalid_argument, "section offset exceeds section size");
+    return createStringError(errc::invalid_argument,
+                             "section offset exceeds section size");
 
   if (DA.getU32(&Offset) != dwarf::DW_LENGTH_DWARF64)
-    return createStringError(errc::invalid_argument, "32 bit contribution referenced from a 64 bit unit");
+    return createStringError(
+        errc::invalid_argument,
+        "32 bit contribution referenced from a 64 bit unit");
 
   uint64_t Size = DA.getU64(&Offset);
   uint8_t Version = DA.getU16(&Offset);
   (void)DA.getU16(&Offset); // padding
   // The encoded length includes the 2-byte version field and the 2-byte
   // padding, so we need to subtract them out when we populate the descriptor.
   return StrOffsetsContributionDescriptor(Offset, Size - 4, Version, DWARF64);
 }
 
 // Look for a DWARF32-formatted contribution to the string offsets table
 // starting at a given offset and record it in a descriptor.
 static Expected<StrOffsetsContributionDescriptor>
 parseDWARF32StringOffsetsTableHeader(DWARFDataExtractor &DA, uint64_t Offset) {
   if (!DA.isValidOffsetForDataOfSize(Offset, 8))
-    return createStringError(errc::invalid_argument, "section offset exceeds section size");
+    return createStringError(errc::invalid_argument,
+                             "section offset exceeds section size");
 
   uint32_t ContributionSize = DA.getU32(&Offset);
   if (ContributionSize >= dwarf::DW_LENGTH_lo_reserved)
     return createStringError(errc::invalid_argument, "invalid length");
 
   uint8_t Version = DA.getU16(&Offset);
   (void)DA.getU16(&Offset); // padding
   // The encoded length includes the 2-byte version field and the 2-byte
   // padding, so we need to subtract them out when we populate the descriptor.
   return StrOffsetsContributionDescriptor(Offset, ContributionSize - 4, Version,
                                           DWARF32);
 }
 
 static Expected<StrOffsetsContributionDescriptor>
 parseDWARFStringOffsetsTableHeader(DWARFDataExtractor &DA,
                                    llvm::dwarf::DwarfFormat Format,
                                    uint64_t Offset) {
   StrOffsetsContributionDescriptor Desc;
   switch (Format) {
   case dwarf::DwarfFormat::DWARF64: {
     if (Offset < 16)
-      return createStringError(errc::invalid_argument, "insufficient space for 64 bit header prefix");
+      return createStringError(errc::invalid_argument,
+                               "insufficient space for 64 bit header prefix");
     auto DescOrError = parseDWARF64StringOffsetsTableHeader(DA, Offset - 16);
     if (!DescOrError)
       return DescOrError.takeError();
     Desc = *DescOrError;
     break;
   }
   case dwarf::DwarfFormat::DWARF32: {
     if (Offset < 8)
-      return createStringError(errc::invalid_argument, "insufficient space for 32 bit header prefix");
+      return createStringError(errc::invalid_argument,
+                               "insufficient space for 32 bit header prefix");
     auto DescOrError = parseDWARF32StringOffsetsTableHeader(DA, Offset - 8);
     if (!DescOrError)
       return DescOrError.takeError();
     Desc = *DescOrError;
     break;
   }
   }
   return Desc.validateContributionSize(DA);
 }
 
 Expected<Optional<StrOffsetsContributionDescriptor>>
 DWARFUnit::determineStringOffsetsTableContribution(DWARFDataExtractor &DA) {
   assert(!IsDWO);
   auto OptOffset = toSectionOffset(getUnitDIE().find(DW_AT_str_offsets_base));
   if (!OptOffset)
     return None;
   auto DescOrError =
       parseDWARFStringOffsetsTableHeader(DA, Header.getFormat(), *OptOffset);
   if (!DescOrError)
     return DescOrError.takeError();
   return *DescOrError;
 }
 
 Expected<Optional<StrOffsetsContributionDescriptor>>
-DWARFUnit::determineStringOffsetsTableContributionDWO(DWARFDataExtractor & DA) {
+DWARFUnit::determineStringOffsetsTableContributionDWO(DWARFDataExtractor &DA) {
   assert(IsDWO);
   uint64_t Offset = 0;
   auto IndexEntry = Header.getIndexEntry();
   const auto *C =
       IndexEntry ? IndexEntry->getContribution(DW_SECT_STR_OFFSETS) : nullptr;
   if (C)
     Offset = C->Offset;
   if (getVersion() >= 5) {
     if (DA.getData().data() == nullptr)
       return None;
     Offset += Header.getFormat() == dwarf::DwarfFormat::DWARF32 ? 8 : 16;
     // Look for a valid contribution at the given offset.
-    auto DescOrError = parseDWARFStringOffsetsTableHeader(DA, Header.getFormat(), Offset);
+    auto DescOrError =
+        parseDWARFStringOffsetsTableHeader(DA, Header.getFormat(), Offset);
     if (!DescOrError)
       return DescOrError.takeError();
     return *DescOrError;
   }
   // Prior to DWARF v5, we derive the contribution size from the
   // index table (in a package file). In a .dwo file it is simply
   // the length of the string offsets section.
   StrOffsetsContributionDescriptor Desc;

llvm/lib/DebugInfo/GSYM/GsymCreator.cpp

 //===- GsymCreator.cpp ----------------------------------------------------===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/GSYM/GsymCreator.h"
uint32_t GsymCreator::insertFile(StringRef Path, llvm::sys::path::Style Style) {
   // We must insert the strings first, then call the FileEntry constructor.
   // If we inline the insertString() function call into the constructor, the
   // call order is undefined due to parameter lists not having any ordering
   // requirements.
   const uint32_t Dir = insertString(directory);
   const uint32_t Base = insertString(filename);
   FileEntry FE(Dir, Base);
 
-  std::lock_guard<std::recursive_mutex> Guard(Mutex);
+  std::lock_guard<std::mutex> Guard(Mutex);
   const auto NextIndex = Files.size();
   // Find FE in hash map and insert if not present.
   auto R = FileEntryToIndex.insert(std::make_pair(FE, NextIndex));
   if (R.second)
     Files.emplace_back(FE);
   return R.first->second;
 }
 
 llvm::Error GsymCreator::save(StringRef Path,
                               llvm::support::endianness ByteOrder) const {
   std::error_code EC;
   raw_fd_ostream OutStrm(Path, EC);
   if (EC)
     return llvm::errorCodeToError(EC);
   FileWriter O(OutStrm, ByteOrder);
   return encode(O);
 }
 
 llvm::Error GsymCreator::encode(FileWriter &O) const {
-  std::lock_guard<std::recursive_mutex> Guard(Mutex);
+  std::lock_guard<std::mutex> Guard(Mutex);
   if (Funcs.empty())
     return createStringError(std::errc::invalid_argument,
                              "no functions to encode");
   if (!Finalized)
     return createStringError(std::errc::invalid_argument,
                              "GsymCreator wasn't finalized prior to encoding");
 
   if (Funcs.size() > UINT32_MAX)
if (FirstIt != LastIt)
           PrevIt = FirstIt;
           *FirstIt++ = std::move(*CurrIt);
         }
   }
   return FirstIt;
 }
 
 llvm::Error GsymCreator::finalize(llvm::raw_ostream &OS) {
-  std::lock_guard<std::recursive_mutex> Guard(Mutex);
+  std::lock_guard<std::mutex> Guard(Mutex);
   if (Finalized)
     return createStringError(std::errc::invalid_argument, "already finalized");
   Finalized = true;
 
   // Sort function infos so we can emit sorted functions.
   llvm::sort(Funcs);
 
   // Don't let the string table indexes change by finalizing in order.
llvm::Error GsymCreator::finalize(llvm::raw_ostream &OS) {
   OS << "Pruned " << NumBefore - Funcs.size() << " functions, ended with "
      << Funcs.size() << " total\n";
   return Error::success();
 }
 
 uint32_t GsymCreator::insertString(StringRef S, bool Copy) {
   if (S.empty())
     return 0;
-  std::lock_guard<std::recursive_mutex> Guard(Mutex);
+
+  // The hash can be calculated outside the lock.
+  CachedHashStringRef CHStr(S);
+  std::lock_guard<std::mutex> Guard(Mutex);
   if (Copy) {
     // We need to provide backing storage for the string if requested
     // since StringTableBuilder stores references to strings. Any string
     // that comes from a section in an object file doesn't need to be
     // copied, but any string created by code will need to be copied.
     // This allows GsymCreator to be really fast when parsing DWARF and
     // other object files as most strings don't need to be copied.
-    CachedHashStringRef CHStr(S);
     if (!StrTab.contains(CHStr))
-      S = StringStorage.insert(S).first->getKey();
+      CHStr = CachedHashStringRef{StringStorage.insert(S).first->getKey(),
+                                  CHStr.hash()};
   }
-  return StrTab.add(S);
+  return StrTab.add(CHStr);
 }
 
 void GsymCreator::addFunctionInfo(FunctionInfo &&FI) {
-  std::lock_guard<std::recursive_mutex> Guard(Mutex);
+  std::lock_guard<std::mutex> Guard(Mutex);
   Ranges.insert(FI.Range);
-  Funcs.emplace_back(FI);
+  Funcs.emplace_back(std::move(FI));
 }
 
 void GsymCreator::forEachFunctionInfo(
     std::function<bool(FunctionInfo &)> const &Callback) {
-  std::lock_guard<std::recursive_mutex> Guard(Mutex);
+  std::lock_guard<std::mutex> Guard(Mutex);
   for (auto &FI : Funcs) {
     if (!Callback(FI))
       break;
   }
 }
 
 void GsymCreator::forEachFunctionInfo(
     std::function<bool(const FunctionInfo &)> const &Callback) const {
-  std::lock_guard<std::recursive_mutex> Guard(Mutex);
+  std::lock_guard<std::mutex> Guard(Mutex);
   for (const auto &FI : Funcs) {
     if (!Callback(FI))
       break;
   }
 }
 
 size_t GsymCreator::getNumFunctionInfos() const {
-  std::lock_guard<std::recursive_mutex> Guard(Mutex);
+  std::lock_guard<std::mutex> Guard(Mutex);
   return Funcs.size();
 }
 
 bool GsymCreator::IsValidTextAddress(uint64_t Addr) const {
   if (ValidTextRanges)
     return ValidTextRanges->contains(Addr);
   return true; // No valid text ranges has been set, so accept all ranges.
 }
 
 bool GsymCreator::hasFunctionInfoForAddress(uint64_t Addr) const {
-  std::lock_guard<std::recursive_mutex> Guard(Mutex);
+  std::lock_guard<std::mutex> Guard(Mutex);
   return Ranges.contains(Addr);
 }