SyntheticTypeNameBuilder.cpp

Go to the documentation of this file.

//===- SyntheticTypeNameBuilder.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 "SyntheticTypeNameBuilder.h"
#include "DWARFLinkerCompileUnit.h"
#include "llvm/DWARFLinker/Utils.h"
#include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
#include "llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h"
#include "llvm/DebugInfo/DWARF/DWARFDie.h"
#include "llvm/Support/xxhash.h"
 
using namespace llvm;
using namespace dwarf_linker;
using namespace dwarf_linker::parallel;
 
Error SyntheticTypeNameBuilder::assignName(
    UnitEntryPairTy InputUnitEntryPair,
    std::optional<std::pair<size_t, size_t>> ChildIndex) {
  [[maybe_unused]] const CompileUnit::DIEInfo &Info =
      InputUnitEntryPair.CU->getDIEInfo(InputUnitEntryPair.DieEntry);
  assert(Info.needToPlaceInTypeTable() &&
         "Cann't assign name for non-type DIE");
 
  if (InputUnitEntryPair.CU->getDieTypeEntry(InputUnitEntryPair.DieEntry) !=
      nullptr)
    return Error::success();
 
  SyntheticName.resize(0);
  RecursionDepth = 0;
  return addDIETypeName(InputUnitEntryPair, ChildIndex, true);
}
 
void SyntheticTypeNameBuilder::addArrayDimension(
    UnitEntryPairTy InputUnitEntryPair) {
  for (const DWARFDebugInfoEntry *CurChild =
           InputUnitEntryPair.CU->getFirstChildEntry(
               InputUnitEntryPair.DieEntry);
       CurChild && CurChild->getAbbreviationDeclarationPtr();
       CurChild = InputUnitEntryPair.CU->getSiblingEntry(CurChild)) {
    if (CurChild->getTag() == dwarf::DW_TAG_subrange_type ||
        CurChild->getTag() == dwarf::DW_TAG_generic_subrange) {
      SyntheticName += "[";
      if (std::optional<DWARFFormValue> Val =
              InputUnitEntryPair.CU->find(CurChild, dwarf::DW_AT_count)) {
        if (std::optional<uint64_t> ConstVal = Val->getAsUnsignedConstant()) {
          SyntheticName += std::to_string(*ConstVal);
        } else if (std::optional<int64_t> ConstVal =
                       Val->getAsSignedConstant()) {
          SyntheticName += std::to_string(*ConstVal);
        }
      }
 
      SyntheticName += "]";
    }
  }
}
 
static dwarf::Attribute TypeAttr[] = {dwarf::DW_AT_type};
Error SyntheticTypeNameBuilder::addSignature(UnitEntryPairTy InputUnitEntryPair,
                                             bool addTemplateParameters) {
  // Add entry type.
  if (Error Err = addReferencedODRDies(InputUnitEntryPair, false, TypeAttr))
    return Err;
  SyntheticName += ':';
 
  SmallVector<const DWARFDebugInfoEntry *, 10> TemplateParameters;
  SmallVector<const DWARFDebugInfoEntry *, 20> FunctionParameters;
  for (const DWARFDebugInfoEntry *CurChild =
           InputUnitEntryPair.CU->getFirstChildEntry(
               InputUnitEntryPair.DieEntry);
       CurChild && CurChild->getAbbreviationDeclarationPtr();
       CurChild = InputUnitEntryPair.CU->getSiblingEntry(CurChild)) {
    dwarf::Tag ChildTag = CurChild->getTag();
    if (addTemplateParameters &&
        (ChildTag == dwarf::DW_TAG_template_type_parameter ||
         ChildTag == dwarf::DW_TAG_template_value_parameter))
      TemplateParameters.push_back(CurChild);
    else if (ChildTag == dwarf::DW_TAG_formal_parameter ||
             ChildTag == dwarf::DW_TAG_unspecified_parameters)
      FunctionParameters.push_back(CurChild);
    else if (addTemplateParameters &&
             ChildTag == dwarf::DW_TAG_GNU_template_parameter_pack) {
      for (const DWARFDebugInfoEntry *CurGNUChild =
               InputUnitEntryPair.CU->getFirstChildEntry(CurChild);
           CurGNUChild && CurGNUChild->getAbbreviationDeclarationPtr();
           CurGNUChild = InputUnitEntryPair.CU->getSiblingEntry(CurGNUChild))
        TemplateParameters.push_back(CurGNUChild);
    } else if (ChildTag == dwarf::DW_TAG_GNU_formal_parameter_pack) {
      for (const DWARFDebugInfoEntry *CurGNUChild =
               InputUnitEntryPair.CU->getFirstChildEntry(CurChild);
           CurGNUChild && CurGNUChild->getAbbreviationDeclarationPtr();
           CurGNUChild = InputUnitEntryPair.CU->getSiblingEntry(CurGNUChild))
        FunctionParameters.push_back(CurGNUChild);
    }
  }
 
  // Add parameters.
  if (Error Err = addParamNames(*InputUnitEntryPair.CU, FunctionParameters))
    return Err;
 
  // Add template parameters.
  if (Error Err =
          addTemplateParamNames(*InputUnitEntryPair.CU, TemplateParameters))
    return Err;
 
  return Error::success();
}
 
Error SyntheticTypeNameBuilder::addParamNames(
    CompileUnit &CU,
    SmallVector<const DWARFDebugInfoEntry *, 20> &FunctionParameters) {
  SyntheticName += '(';
  for (const DWARFDebugInfoEntry *FunctionParameter : FunctionParameters) {
    if (SyntheticName.back() != '(')
      SyntheticName += ", ";
    if (dwarf::toUnsigned(CU.find(FunctionParameter, dwarf::DW_AT_artificial),
                          0))
      SyntheticName += "^";
    if (Error Err = addReferencedODRDies(
            UnitEntryPairTy{&CU, FunctionParameter}, false, TypeAttr))
      return Err;
  }
  SyntheticName += ')';
  return Error::success();
}
 
Error SyntheticTypeNameBuilder::addTemplateParamNames(
    CompileUnit &CU,
    SmallVector<const DWARFDebugInfoEntry *, 10> &TemplateParameters) {
  if (!TemplateParameters.empty()) {
    SyntheticName += '<';
    for (const DWARFDebugInfoEntry *Parameter : TemplateParameters) {
      if (SyntheticName.back() != '<')
        SyntheticName += ", ";
 
      if (Parameter->getTag() == dwarf::DW_TAG_template_value_parameter) {
        if (std::optional<DWARFFormValue> Val =
                CU.find(Parameter, dwarf::DW_AT_const_value)) {
          if (std::optional<uint64_t> ConstVal = Val->getAsUnsignedConstant())
            SyntheticName += std::to_string(*ConstVal);
          else if (std::optional<int64_t> ConstVal = Val->getAsSignedConstant())
            SyntheticName += std::to_string(*ConstVal);
        }
      }
 
      if (Error Err = addReferencedODRDies(UnitEntryPairTy{&CU, Parameter},
                                           false, TypeAttr))
        return Err;
    }
    SyntheticName += '>';
  }
  return Error::success();
}
 
void SyntheticTypeNameBuilder::addOrderedName(
    std::pair<size_t, size_t> ChildIdx) {
  std::string Name;
  llvm::raw_string_ostream stream(Name);
  stream << format_hex_no_prefix(ChildIdx.first, ChildIdx.second);
  SyntheticName += Name;
}
 
// Examine DIE and return type deduplication candidate: some DIEs could not be
// deduplicated, namespace may refer to another namespace.
static std::optional<UnitEntryPairTy>
getTypeDeduplicationCandidate(UnitEntryPairTy UnitEntryPair) {
  switch (UnitEntryPair.DieEntry->getTag()) {
  case dwarf::DW_TAG_null:
  case dwarf::DW_TAG_compile_unit:
  case dwarf::DW_TAG_partial_unit:
  case dwarf::DW_TAG_type_unit:
  case dwarf::DW_TAG_skeleton_unit: {
    return std::nullopt;
  }
  case dwarf::DW_TAG_namespace: {
    // Check if current namespace refers another.
    if (UnitEntryPair.CU->find(UnitEntryPair.DieEntry, dwarf::DW_AT_extension))
      UnitEntryPair = UnitEntryPair.getNamespaceOrigin();
 
    // Content of anonimous namespaces should not be deduplicated.
    if (!UnitEntryPair.CU->find(UnitEntryPair.DieEntry, dwarf::DW_AT_name))
      llvm_unreachable("Cann't deduplicate anonimous namespace");
 
    return UnitEntryPair;
  }
  default:
    return UnitEntryPair;
  }
}
 
Error SyntheticTypeNameBuilder::addParentName(
    UnitEntryPairTy &InputUnitEntryPair) {
  std::optional<UnitEntryPairTy> UnitEntryPair = InputUnitEntryPair.getParent();
  if (!UnitEntryPair)
    return Error::success();
 
  UnitEntryPair = getTypeDeduplicationCandidate(*UnitEntryPair);
  if (!UnitEntryPair)
    return Error::success();
 
  if (TypeEntry *ImmediateParentName =
          UnitEntryPair->CU->getDieTypeEntry(UnitEntryPair->DieEntry)) {
    SyntheticName += ImmediateParentName->getKey();
    SyntheticName += ".";
    return Error::success();
  }
 
  // Collect parent entries.
  SmallVector<UnitEntryPairTy, 10> Parents;
  do {
    Parents.push_back(*UnitEntryPair);
 
    UnitEntryPair = UnitEntryPair->getParent();
    if (!UnitEntryPair)
      break;
 
    UnitEntryPair = getTypeDeduplicationCandidate(*UnitEntryPair);
    if (!UnitEntryPair)
      break;
 
  } while (!UnitEntryPair->CU->getDieTypeEntry(UnitEntryPair->DieEntry));
 
  // Assign name for each parent entry.
  size_t NameStart = SyntheticName.size();
  for (UnitEntryPairTy Parent : reverse(Parents)) {
    SyntheticName.resize(NameStart);
    if (Error Err = addDIETypeName(Parent, std::nullopt, true))
      return Err;
  }
 
  // Add parents delimiter.
  SyntheticName += ".";
  return Error::success();
}
 
void SyntheticTypeNameBuilder::addDieNameFromDeclFileAndDeclLine(
    UnitEntryPairTy &InputUnitEntryPair, bool &HasDeclFileName) {
  if (std::optional<DWARFFormValue> DeclFileVal = InputUnitEntryPair.CU->find(
          InputUnitEntryPair.DieEntry, dwarf::DW_AT_decl_file)) {
    if (std::optional<DWARFFormValue> DeclLineVal = InputUnitEntryPair.CU->find(
            InputUnitEntryPair.DieEntry, dwarf::DW_AT_decl_line)) {
      if (std::optional<std::pair<StringRef, StringRef>> DirAndFilename =
              InputUnitEntryPair.CU->getDirAndFilenameFromLineTable(
                  *DeclFileVal)) {
        SyntheticName += DirAndFilename->first;
        SyntheticName += DirAndFilename->second;
 
        if (std::optional<uint64_t> DeclLineIntVal =
                dwarf::toUnsigned(*DeclLineVal)) {
          SyntheticName += " ";
          SyntheticName += utohexstr(*DeclLineIntVal);
        }
 
        HasDeclFileName = true;
      }
    }
  }
}
 
void SyntheticTypeNameBuilder::addValueName(UnitEntryPairTy InputUnitEntryPair,
                                            dwarf::Attribute Attr) {
  if (std::optional<DWARFFormValue> Val =
          InputUnitEntryPair.CU->find(InputUnitEntryPair.DieEntry, Attr)) {
    if (std::optional<uint64_t> ConstVal = Val->getAsUnsignedConstant()) {
      SyntheticName += " ";
      SyntheticName += std::to_string(*ConstVal);
    } else if (std::optional<int64_t> ConstVal = Val->getAsSignedConstant()) {
      SyntheticName += " ";
      SyntheticName += std::to_string(*ConstVal);
    }
  }
}
 
Expected<std::optional<UnitEntryPairTy>>
SyntheticTypeNameBuilder::resolveReference(UnitEntryPairTy InputUnitEntryPair,
                                           dwarf::Attribute Attr) {
  std::optional<DWARFFormValue> AttrValue =
      InputUnitEntryPair.CU->find(InputUnitEntryPair.DieEntry, Attr);
  if (!AttrValue)
    return std::nullopt;
 
  std::optional<UnitEntryPairTy> RefDie =
      InputUnitEntryPair.CU->resolveDIEReference(
          *AttrValue, ResolveInterCUReferencesMode::Resolve);
  if (RefDie && !RefDie->DieEntry)
    return createStringError(std::errc::invalid_argument,
                             "cannot resolve DIE reference");
  return RefDie;
}
 
Error SyntheticTypeNameBuilder::incrementRecursionDepth() {
  if (++RecursionDepth > MaxRecursionDepth)
    return createStringError(std::errc::invalid_argument,
                             "cannot parse input DWARF: recursive dependence");
  return Error::success();
}
 
Error SyntheticTypeNameBuilder::addReferencedODRDies(
    UnitEntryPairTy InputUnitEntryPair, bool AssignNameToTypeDescriptor,
    ArrayRef<dwarf::Attribute> ODRAttrs) {
  bool FirstIteration = true;
  for (dwarf::Attribute Attr : ODRAttrs) {
    Expected<std::optional<UnitEntryPairTy>> RefDie =
        resolveReference(InputUnitEntryPair, Attr);
    if (!RefDie)
      return RefDie.takeError();
    if (!*RefDie)
      continue;
 
    if (!FirstIteration)
      SyntheticName += ",";
 
    if (Error Err = incrementRecursionDepth())
      return Err;
    if (Error Err =
            addDIETypeName(**RefDie, std::nullopt, AssignNameToTypeDescriptor))
      return Err;
    RecursionDepth--;
    FirstIteration = false;
  }
 
  return Error::success();
}
 
Error SyntheticTypeNameBuilder::addTypeName(UnitEntryPairTy InputUnitEntryPair,
                                            bool AddParentNames) {
  bool HasLinkageName = false;
  bool HasShortName = false;
  bool HasTemplatesInShortName = false;
  bool HasDeclFileName = false;
 
  // Try to get name from the DIE.
  if (std::optional<DWARFFormValue> Val = InputUnitEntryPair.CU->find(
          InputUnitEntryPair.DieEntry,
          {dwarf::DW_AT_MIPS_linkage_name, dwarf::DW_AT_linkage_name})) {
    // Firstly check for linkage name.
    SyntheticName += dwarf::toStringRef(Val);
    HasLinkageName = true;
  } else if (std::optional<DWARFFormValue> Val = InputUnitEntryPair.CU->find(
                 InputUnitEntryPair.DieEntry, dwarf::DW_AT_name)) {
    // Then check for short name.
    StringRef Name = dwarf::toStringRef(Val);
    SyntheticName += Name;
 
    HasShortName = true;
    HasTemplatesInShortName =
        Name.ends_with(">") && Name.count("<") != 0 && !Name.ends_with("<=>");
  } else {
    // Finally check for declaration attributes.
    addDieNameFromDeclFileAndDeclLine(InputUnitEntryPair, HasDeclFileName);
 
    // Unnamed types declared on one line differ only in their contents.
    if (HasDeclFileName)
      if (Error Err = addUnnamedTypeContents(InputUnitEntryPair))
        return Err;
  }
 
  // Add additional name parts for some DIEs.
  switch (InputUnitEntryPair.DieEntry->getTag()) {
  case dwarf::DW_TAG_union_type:
  case dwarf::DW_TAG_interface_type:
  case dwarf::DW_TAG_class_type:
  case dwarf::DW_TAG_structure_type:
  case dwarf::DW_TAG_subroutine_type:
  case dwarf::DW_TAG_subprogram: {
    if (InputUnitEntryPair.CU->find(InputUnitEntryPair.DieEntry,
                                    dwarf::DW_AT_artificial))
      SyntheticName += "^";
 
    // No need to add signature information for linkage name,
    // also no need to add template parameters name if short name already
    // includes them.
    if (!HasLinkageName)
      if (Error Err =
              addSignature(InputUnitEntryPair, !HasTemplatesInShortName))
        return Err;
  } break;
  case dwarf::DW_TAG_coarray_type:
  case dwarf::DW_TAG_array_type: {
    addArrayDimension(InputUnitEntryPair);
  } break;
  case dwarf::DW_TAG_subrange_type: {
    addValueName(InputUnitEntryPair, dwarf::DW_AT_count);
  } break;
  case dwarf::DW_TAG_template_value_parameter: {
    if (!HasTemplatesInShortName) {
      // TODO add support for DW_AT_location
      addValueName(InputUnitEntryPair, dwarf::DW_AT_const_value);
    }
  } break;
  default: {
    // Nothing to do.
  } break;
  }
 
  // If name for the DIE is not determined yet or if the DIE is a typedef, add
  // referenced types to the name.
  if ((!HasLinkageName && !HasShortName && !HasDeclFileName) ||
      InputUnitEntryPair.DieEntry->getTag() == dwarf::DW_TAG_typedef) {
    if (InputUnitEntryPair.CU->find(InputUnitEntryPair.DieEntry,
                                    getODRAttributes()))
      if (Error Err = addReferencedODRDies(InputUnitEntryPair, AddParentNames,
                                           getODRAttributes()))
        return Err;
  }
 
  return Error::success();
}
 
Error SyntheticTypeNameBuilder::addDIETypeName(
    UnitEntryPairTy InputUnitEntryPair,
    std::optional<std::pair<size_t, size_t>> ChildIndex,
    bool AssignNameToTypeDescriptor) {
  std::optional<UnitEntryPairTy> UnitEntryPair =
      getTypeDeduplicationCandidate(InputUnitEntryPair);
  if (!UnitEntryPair)
    return Error::success();
 
  TypeEntry *TypeEntryPtr =
      InputUnitEntryPair.CU->getDieTypeEntry(InputUnitEntryPair.DieEntry);
  // Check if DIE already has a name.
  if (!TypeEntryPtr) {
    size_t NameStart = SyntheticName.size();
    // Prepend the parent scope so this name matches the key the type is
    // stored under in the pool (the getKey() branch below). Otherwise the
    // same type gets different names depending on whether it already has a
    // pool entry, which races under parallel assignment and breaks
    // deterministic deduplication.
    if (Error Err = addParentName(*UnitEntryPair))
      return Err;
    addTypePrefix(*UnitEntryPair->CU, UnitEntryPair->DieEntry);
 
    if (ChildIndex) {
      addOrderedName(*ChildIndex);
    } else {
      if (Error Err = addTypeName(*UnitEntryPair, AssignNameToTypeDescriptor))
        return Err;
    }
 
    if (AssignNameToTypeDescriptor) {
      // Add built name to the DIE.
      TypeEntryPtr = TypePoolRef.insert(SyntheticName.substr(NameStart));
      InputUnitEntryPair.CU->setDieTypeEntry(InputUnitEntryPair.DieEntry,
                                             TypeEntryPtr);
    }
  } else
    SyntheticName += TypeEntryPtr->getKey();
 
  return Error::success();
}
 
Error SyntheticTypeNameBuilder::addUnnamedTypeContents(
    UnitEntryPairTy InputUnitEntryPair) {
  if (!isIdentifiedByChildren(InputUnitEntryPair.DieEntry->getTag()))
    return Error::success();
 
  auto It = ContentsDigests.find(InputUnitEntryPair.DieEntry);
  if (It != ContentsDigests.end()) {
    SyntheticName += It->second;
    return Error::success();
  }
 
  CompileUnit &CU = *InputUnitEntryPair.CU;
  size_t ContentsStart = SyntheticName.size();
  SyntheticName += '(';
  for (const DWARFDebugInfoEntry *CurChild =
           CU.getFirstChildEntry(InputUnitEntryPair.DieEntry);
       CurChild && CurChild->getAbbreviationDeclarationPtr();
       CurChild = CU.getSiblingEntry(CurChild)) {
    if (!isIdentifyingChild(DWARFDie(&CU.getOrigUnit(), CurChild)))
      continue;
 
    if (SyntheticName.size() != ContentsStart + 1)
      SyntheticName += ", ";
    addTypePrefix(CU, CurChild);
    if (std::optional<DWARFFormValue> Val =
            CU.find(CurChild, dwarf::DW_AT_name))
      SyntheticName += dwarf::toStringRef(Val);
    if (Error Err = addUnqualifiedTypeName(UnitEntryPairTy{&CU, CurChild}))
      return Err;
  }
  SyntheticName += ')';
 
  // Replace the contents with a fixed-size digest, so the names of the types
  // referring to this one do not grow with its size or nesting depth.
  StringRef Contents = StringRef(SyntheticName).substr(ContentsStart);
  XXH128_hash_t Hash = xxh3_128bits(arrayRefFromStringRef<uint8_t>(Contents));
  std::string Digest = "<" + utohexstr(Hash.high64, true, 16) +
                       utohexstr(Hash.low64, true, 16) + ">";
  SyntheticName.resize(ContentsStart);
  SyntheticName += Digest;
  ContentsDigests.try_emplace(InputUnitEntryPair.DieEntry, std::move(Digest));
  return Error::success();
}
 
Error SyntheticTypeNameBuilder::addUnqualifiedTypeName(
    UnitEntryPairTy InputUnitEntryPair) {
  Expected<std::optional<UnitEntryPairTy>> RefDie =
      resolveReference(InputUnitEntryPair, dwarf::DW_AT_type);
  if (!RefDie)
    return RefDie.takeError();
  if (!*RefDie)
    return Error::success();
 
  if (Error Err = incrementRecursionDepth())
    return Err;
 
  UnitEntryPairTy Type = **RefDie;
  SyntheticName += ':';
  addTypePrefix(*Type.CU, Type.DieEntry);
  if (std::optional<DWARFFormValue> Val =
          Type.CU->find(Type.DieEntry, dwarf::DW_AT_name)) {
    SyntheticName += dwarf::toStringRef(Val);
  } else {
    if (Type.DieEntry->getTag() == dwarf::DW_TAG_array_type)
      addArrayDimension(Type);
    if (Error Err = addUnnamedTypeContents(Type))
      return Err;
    if (Error Err = addUnqualifiedTypeName(Type))
      return Err;
  }
 
  RecursionDepth--;
  return Error::success();
}
 
void SyntheticTypeNameBuilder::addTypePrefix(
    CompileUnit &CU, const DWARFDebugInfoEntry *DieEntry) {
  switch (DieEntry->getTag()) {
  case dwarf::DW_TAG_base_type: {
    SyntheticName += "{0}";
  } break;
  case dwarf::DW_TAG_namespace: {
    SyntheticName += "{1}";
  } break;
  case dwarf::DW_TAG_formal_parameter: {
    SyntheticName += "{2}";
  } break;
  // dwarf::DW_TAG_unspecified_parameters have the same prefix as before.
  case dwarf::DW_TAG_unspecified_parameters: {
    SyntheticName += "{2}";
  } break;
  case dwarf::DW_TAG_template_type_parameter: {
    SyntheticName += "{3}";
  } break;
  // dwarf::DW_TAG_template_value_parameter have the same prefix as before.
  case dwarf::DW_TAG_template_value_parameter: {
    SyntheticName += "{3}";
  } break;
  case dwarf::DW_TAG_GNU_formal_parameter_pack: {
    SyntheticName += "{4}";
  } break;
  case dwarf::DW_TAG_GNU_template_parameter_pack: {
    SyntheticName += "{5}";
  } break;
  case dwarf::DW_TAG_inheritance: {
    SyntheticName += "{6}";
  } break;
  case dwarf::DW_TAG_array_type: {
    SyntheticName += "{7}";
  } break;
  case dwarf::DW_TAG_class_type: {
    SyntheticName += "{8}";
  } break;
  case dwarf::DW_TAG_enumeration_type: {
    SyntheticName += "{9}";
  } break;
  case dwarf::DW_TAG_imported_declaration: {
    SyntheticName += "{A}";
  } break;
  case dwarf::DW_TAG_member: {
    // Treat a static data member the same way regardless of whether it's
    // described as a DW_TAG_member or a DW_TAG_variable.
    if (isStaticDataMember(DWARFDie(&CU.getOrigUnit(), DieEntry)))
      SyntheticName += "{d}";
    else
      SyntheticName += "{B}";
  } break;
  case dwarf::DW_TAG_pointer_type: {
    SyntheticName += "{C}";
  } break;
  case dwarf::DW_TAG_reference_type: {
    SyntheticName += "{D}";
  } break;
  case dwarf::DW_TAG_string_type: {
    SyntheticName += "{E}";
  } break;
  case dwarf::DW_TAG_structure_type: {
    SyntheticName += "{F}";
  } break;
  case dwarf::DW_TAG_subroutine_type: {
    SyntheticName += "{G}";
  } break;
  case dwarf::DW_TAG_typedef: {
    SyntheticName += "{H}";
  } break;
  case dwarf::DW_TAG_union_type: {
    SyntheticName += "{I}";
  } break;
  case dwarf::DW_TAG_variant: {
    SyntheticName += "{J}";
  } break;
  case dwarf::DW_TAG_inlined_subroutine: {
    SyntheticName += "{K}";
  } break;
  case dwarf::DW_TAG_module: {
    SyntheticName += "{L}";
  } break;
  case dwarf::DW_TAG_ptr_to_member_type: {
    SyntheticName += "{M}";
  } break;
  case dwarf::DW_TAG_set_type: {
    SyntheticName += "{N}";
  } break;
  case dwarf::DW_TAG_subrange_type: {
    SyntheticName += "{O}";
  } break;
  case dwarf::DW_TAG_with_stmt: {
    SyntheticName += "{P}";
  } break;
  case dwarf::DW_TAG_access_declaration: {
    SyntheticName += "{Q}";
  } break;
  case dwarf::DW_TAG_catch_block: {
    SyntheticName += "{R}";
  } break;
  case dwarf::DW_TAG_const_type: {
    SyntheticName += "{S}";
  } break;
  case dwarf::DW_TAG_constant: {
    SyntheticName += "{T}";
  } break;
  case dwarf::DW_TAG_enumerator: {
    SyntheticName += "{U}";
  } break;
  case dwarf::DW_TAG_file_type: {
    SyntheticName += "{V}";
  } break;
  case dwarf::DW_TAG_friend: {
    SyntheticName += "{W}";
  } break;
  case dwarf::DW_TAG_namelist: {
    SyntheticName += "{X}";
  } break;
  case dwarf::DW_TAG_namelist_item: {
    SyntheticName += "{Y}";
  } break;
  case dwarf::DW_TAG_packed_type: {
    SyntheticName += "{Z}";
  } break;
  case dwarf::DW_TAG_subprogram: {
    SyntheticName += "{a}";
  } break;
  case dwarf::DW_TAG_thrown_type: {
    SyntheticName += "{b}";
  } break;
  case dwarf::DW_TAG_variant_part: {
    SyntheticName += "{c}";
  } break;
  case dwarf::DW_TAG_variable: {
    SyntheticName += "{d}";
  } break;
  case dwarf::DW_TAG_volatile_type: {
    SyntheticName += "{e}";
  } break;
  case dwarf::DW_TAG_dwarf_procedure: {
    SyntheticName += "{f}";
  } break;
  case dwarf::DW_TAG_restrict_type: {
    SyntheticName += "{g}";
  } break;
  case dwarf::DW_TAG_interface_type: {
    SyntheticName += "{h}";
  } break;
  case dwarf::DW_TAG_imported_module: {
    SyntheticName += "{i}";
  } break;
  case dwarf::DW_TAG_unspecified_type: {
    SyntheticName += "{j}";
  } break;
  case dwarf::DW_TAG_imported_unit: {
    SyntheticName += "{k}";
  } break;
  case dwarf::DW_TAG_condition: {
    SyntheticName += "{l}";
  } break;
  case dwarf::DW_TAG_shared_type: {
    SyntheticName += "{m}";
  } break;
  case dwarf::DW_TAG_rvalue_reference_type: {
    SyntheticName += "{n}";
  } break;
  case dwarf::DW_TAG_template_alias: {
    SyntheticName += "{o}";
  } break;
  case dwarf::DW_TAG_coarray_type: {
    SyntheticName += "{p}";
  } break;
  case dwarf::DW_TAG_generic_subrange: {
    SyntheticName += "{q}";
  } break;
  case dwarf::DW_TAG_dynamic_type: {
    SyntheticName += "{r}";
  } break;
  case dwarf::DW_TAG_atomic_type: {
    SyntheticName += "{s}";
  } break;
  case dwarf::DW_TAG_call_site: {
    SyntheticName += "{t}";
  } break;
  case dwarf::DW_TAG_call_site_parameter: {
    SyntheticName += "{u}";
  } break;
  case dwarf::DW_TAG_immutable_type: {
    SyntheticName += "{v}";
  } break;
  case dwarf::DW_TAG_entry_point: {
    SyntheticName += "{w}";
  } break;
  case dwarf::DW_TAG_label: {
    SyntheticName += "{x}";
  } break;
  case dwarf::DW_TAG_lexical_block: {
    SyntheticName += "{y}";
  } break;
  case dwarf::DW_TAG_common_block: {
    SyntheticName += "{z}";
  } break;
  case dwarf::DW_TAG_common_inclusion: {
    SyntheticName += "{|}";
  } break;
  case dwarf::DW_TAG_try_block: {
    SyntheticName += "{~}";
  } break;
 
  case dwarf::DW_TAG_null: {
    llvm_unreachable("No type prefix for DW_TAG_null");
  } break;
  case dwarf::DW_TAG_compile_unit: {
    llvm_unreachable("No type prefix for DW_TAG_compile_unit");
  } break;
  case dwarf::DW_TAG_partial_unit: {
    llvm_unreachable("No type prefix for DW_TAG_partial_unit");
  } break;
  case dwarf::DW_TAG_type_unit: {
    llvm_unreachable("No type prefix for DW_TAG_type_unit");
  } break;
  case dwarf::DW_TAG_skeleton_unit: {
    llvm_unreachable("No type prefix for DW_TAG_skeleton_unit");
  } break;
 
  default: {
    SyntheticName += "{~~";
    SyntheticName += utohexstr(DieEntry->getTag());
    SyntheticName += "}";
  } break;
  }
}
 
OrderedChildrenIndexAssigner::OrderedChildrenIndexAssigner(
    CompileUnit &CU, const DWARFDebugInfoEntry *DieEntry) {
  switch (DieEntry->getTag()) {
  case dwarf::DW_TAG_array_type:
  case dwarf::DW_TAG_coarray_type:
  case dwarf::DW_TAG_class_type:
  case dwarf::DW_TAG_common_block:
  case dwarf::DW_TAG_lexical_block:
  case dwarf::DW_TAG_structure_type:
  case dwarf::DW_TAG_subprogram:
  case dwarf::DW_TAG_subroutine_type:
  case dwarf::DW_TAG_union_type:
  case dwarf::DW_TAG_GNU_template_template_param:
  case dwarf::DW_TAG_GNU_formal_parameter_pack:
  case dwarf::DW_TAG_GNU_template_parameter_pack: {
    NeedCountChildren = true;
  } break;
  case dwarf::DW_TAG_enumeration_type: {
    // TODO : do we need to add condition
    NeedCountChildren = true;
  } break;
  default: {
    // Nothing to do.
  }
  }
 
  // Calculate maximal index value
  if (NeedCountChildren) {
    for (const DWARFDebugInfoEntry *CurChild = CU.getFirstChildEntry(DieEntry);
         CurChild && CurChild->getAbbreviationDeclarationPtr();
         CurChild = CU.getSiblingEntry(CurChild)) {
      std::optional<size_t> ArrayIndex = tagToArrayIndex(CU, CurChild);
      if (!ArrayIndex)
        continue;
 
      assert((*ArrayIndex < ChildIndexesWidth.size()) &&
             "Wrong index for ChildIndexesWidth");
      ChildIndexesWidth[*ArrayIndex]++;
    }
 
    // Calculate index field width(number of digits in hexadecimal
    // representation).
    for (size_t &Width : ChildIndexesWidth) {
      size_t digitsCounter = 1;
      size_t NumToCompare = 15;
 
      while (NumToCompare < Width) {
        NumToCompare <<= 4;
        digitsCounter++;
      }
 
      Width = digitsCounter;
    }
  }
}
 
std::optional<size_t> OrderedChildrenIndexAssigner::tagToArrayIndex(
    CompileUnit &CU, const DWARFDebugInfoEntry *DieEntry) {
  if (!NeedCountChildren)
    return std::nullopt;
 
  switch (DieEntry->getTag()) {
  case dwarf::DW_TAG_unspecified_parameters:
  case dwarf::DW_TAG_formal_parameter:
    return 0;
  case dwarf::DW_TAG_template_value_parameter:
  case dwarf::DW_TAG_template_type_parameter:
  case dwarf::DW_TAG_GNU_template_template_param:
    return 1;
  case dwarf::DW_TAG_enumeration_type:
    if (std::optional<uint32_t> ParentIdx = DieEntry->getParentIdx()) {
      if (*ParentIdx && CU.getDebugInfoEntry(*ParentIdx)->getTag() ==
                            dwarf::DW_TAG_array_type)
        return 2;
    }
    return std::nullopt;
  case dwarf::DW_TAG_subrange_type:
    return 3;
  case dwarf::DW_TAG_generic_subrange:
    return 4;
  case dwarf::DW_TAG_enumerator:
    return 5;
  case dwarf::DW_TAG_namelist_item:
    return 6;
  case dwarf::DW_TAG_member:
    // Treat a static data member the same way regardless of whether it's
    // described as a DW_TAG_member or a DW_TAG_variable.
    if (isStaticDataMember(DWARFDie(&CU.getOrigUnit(), DieEntry)))
      return std::nullopt;
    return 7;
  default:
    return std::nullopt;
  };
}
 
std::optional<std::pair<size_t, size_t>>
OrderedChildrenIndexAssigner::getChildIndex(
    CompileUnit &CU, const DWARFDebugInfoEntry *ChildDieEntry) {
  std::optional<size_t> ArrayIndex = tagToArrayIndex(CU, ChildDieEntry);
  if (!ArrayIndex)
    return std::nullopt;
 
  assert((*ArrayIndex < OrderedChildIdxs.size()) &&
         "Wrong index for ChildIndexesWidth");
  assert(ChildIndexesWidth[*ArrayIndex] < 16 &&
         "Index width exceeds 16 digits.");
 
  std::pair<size_t, size_t> Result = std::make_pair(
      OrderedChildIdxs[*ArrayIndex], ChildIndexesWidth[*ArrayIndex]);
  OrderedChildIdxs[*ArrayIndex]++;
  return Result;
}