1 //===- SyntheticTypeNameBuilder.cpp ---------------------------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 
9 #include "SyntheticTypeNameBuilder.h"
10 #include "DWARFLinkerCompileUnit.h"
11 #include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
12 #include "llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h"
13 #include "llvm/Support/ScopedPrinter.h"
14 
15 using namespace llvm;
16 using namespace dwarf_linker;
17 using namespace dwarf_linker::parallel;
18 
19 Error SyntheticTypeNameBuilder::assignName(
20     UnitEntryPairTy InputUnitEntryPair,
21     std::optional<std::pair<size_t, size_t>> ChildIndex) {
22   [[maybe_unused]] const CompileUnit::DIEInfo &Info =
23       InputUnitEntryPair.CU->getDIEInfo(InputUnitEntryPair.DieEntry);
24   assert(Info.needToPlaceInTypeTable() &&
25          "Cann't assign name for non-type DIE");
26 
27   if (InputUnitEntryPair.CU->getDieTypeEntry(InputUnitEntryPair.DieEntry) !=
28       nullptr)
29     return Error::success();
30 
31   SyntheticName.resize(0);
32   RecursionDepth = 0;
33   return addDIETypeName(InputUnitEntryPair, ChildIndex, true);
34 }
35 
36 void SyntheticTypeNameBuilder::addArrayDimension(
37     UnitEntryPairTy InputUnitEntryPair) {
38   for (const DWARFDebugInfoEntry *CurChild =
39            InputUnitEntryPair.CU->getFirstChildEntry(
40                InputUnitEntryPair.DieEntry);
41        CurChild && CurChild->getAbbreviationDeclarationPtr();
42        CurChild = InputUnitEntryPair.CU->getSiblingEntry(CurChild)) {
43     if (CurChild->getTag() == dwarf::DW_TAG_subrange_type ||
44         CurChild->getTag() == dwarf::DW_TAG_generic_subrange) {
45       SyntheticName += "[";
46       if (std::optional<DWARFFormValue> Val =
47               InputUnitEntryPair.CU->find(CurChild, dwarf::DW_AT_count)) {
48         if (std::optional<uint64_t> ConstVal = Val->getAsUnsignedConstant()) {
49           SyntheticName += std::to_string(*ConstVal);
50         } else if (std::optional<int64_t> ConstVal =
51                        Val->getAsSignedConstant()) {
52           SyntheticName += std::to_string(*ConstVal);
53         }
54       }
55 
56       SyntheticName += "]";
57     }
58   }
59 }
60 
61 static dwarf::Attribute TypeAttr[] = {dwarf::DW_AT_type};
62 Error SyntheticTypeNameBuilder::addSignature(UnitEntryPairTy InputUnitEntryPair,
63                                              bool addTemplateParameters) {
64   // Add entry type.
65   if (Error Err = addReferencedODRDies(InputUnitEntryPair, false, TypeAttr))
66     return Err;
67   SyntheticName += ':';
68 
69   SmallVector<const DWARFDebugInfoEntry *, 10> TemplateParameters;
70   SmallVector<const DWARFDebugInfoEntry *, 20> FunctionParameters;
71   for (const DWARFDebugInfoEntry *CurChild =
72            InputUnitEntryPair.CU->getFirstChildEntry(
73                InputUnitEntryPair.DieEntry);
74        CurChild && CurChild->getAbbreviationDeclarationPtr();
75        CurChild = InputUnitEntryPair.CU->getSiblingEntry(CurChild)) {
76     dwarf::Tag ChildTag = CurChild->getTag();
77     if (addTemplateParameters &&
78         (ChildTag == dwarf::DW_TAG_template_type_parameter ||
79          ChildTag == dwarf::DW_TAG_template_value_parameter))
80       TemplateParameters.push_back(CurChild);
81     else if (ChildTag == dwarf::DW_TAG_formal_parameter ||
82              ChildTag == dwarf::DW_TAG_unspecified_parameters)
83       FunctionParameters.push_back(CurChild);
84     else if (addTemplateParameters &&
85              ChildTag == dwarf::DW_TAG_GNU_template_parameter_pack) {
86       for (const DWARFDebugInfoEntry *CurGNUChild =
87                InputUnitEntryPair.CU->getFirstChildEntry(CurChild);
88            CurGNUChild && CurGNUChild->getAbbreviationDeclarationPtr();
89            CurGNUChild = InputUnitEntryPair.CU->getSiblingEntry(CurGNUChild))
90         TemplateParameters.push_back(CurGNUChild);
91     } else if (ChildTag == dwarf::DW_TAG_GNU_formal_parameter_pack) {
92       for (const DWARFDebugInfoEntry *CurGNUChild =
93                InputUnitEntryPair.CU->getFirstChildEntry(CurChild);
94            CurGNUChild && CurGNUChild->getAbbreviationDeclarationPtr();
95            CurGNUChild = InputUnitEntryPair.CU->getSiblingEntry(CurGNUChild))
96         FunctionParameters.push_back(CurGNUChild);
97     }
98   }
99 
100   // Add parameters.
101   if (Error Err = addParamNames(*InputUnitEntryPair.CU, FunctionParameters))
102     return Err;
103 
104   // Add template parameters.
105   if (Error Err =
106           addTemplateParamNames(*InputUnitEntryPair.CU, TemplateParameters))
107     return Err;
108 
109   return Error::success();
110 }
111 
112 Error SyntheticTypeNameBuilder::addParamNames(
113     CompileUnit &CU,
114     SmallVector<const DWARFDebugInfoEntry *, 20> &FunctionParameters) {
115   SyntheticName += '(';
116   for (const DWARFDebugInfoEntry *FunctionParameter : FunctionParameters) {
117     if (SyntheticName.back() != '(')
118       SyntheticName += ", ";
119     if (dwarf::toUnsigned(CU.find(FunctionParameter, dwarf::DW_AT_artificial),
120                           0))
121       SyntheticName += "^";
122     if (Error Err = addReferencedODRDies(
123             UnitEntryPairTy{&CU, FunctionParameter}, false, TypeAttr))
124       return Err;
125   }
126   SyntheticName += ')';
127   return Error::success();
128 }
129 
130 Error SyntheticTypeNameBuilder::addTemplateParamNames(
131     CompileUnit &CU,
132     SmallVector<const DWARFDebugInfoEntry *, 10> &TemplateParameters) {
133   if (!TemplateParameters.empty()) {
134     SyntheticName += '<';
135     for (const DWARFDebugInfoEntry *Parameter : TemplateParameters) {
136       if (SyntheticName.back() != '<')
137         SyntheticName += ", ";
138 
139       if (Parameter->getTag() == dwarf::DW_TAG_template_value_parameter) {
140         if (std::optional<DWARFFormValue> Val =
141                 CU.find(Parameter, dwarf::DW_AT_const_value)) {
142           if (std::optional<uint64_t> ConstVal = Val->getAsUnsignedConstant())
143             SyntheticName += std::to_string(*ConstVal);
144           else if (std::optional<int64_t> ConstVal = Val->getAsSignedConstant())
145             SyntheticName += std::to_string(*ConstVal);
146         }
147       }
148 
149       if (Error Err = addReferencedODRDies(UnitEntryPairTy{&CU, Parameter},
150                                            false, TypeAttr))
151         return Err;
152     }
153     SyntheticName += '>';
154   }
155   return Error::success();
156 }
157 
158 void SyntheticTypeNameBuilder::addOrderedName(
159     std::pair<size_t, size_t> ChildIdx) {
160   std::string Name;
161   llvm::raw_string_ostream stream(Name);
162   stream << format_hex_no_prefix(ChildIdx.first, ChildIdx.second);
163   SyntheticName += Name;
164 }
165 
166 // Examine DIE and return type deduplication candidate: some DIEs could not be
167 // deduplicated, namespace may refer to another namespace.
168 static std::optional<UnitEntryPairTy>
169 getTypeDeduplicationCandidate(UnitEntryPairTy UnitEntryPair) {
170   switch (UnitEntryPair.DieEntry->getTag()) {
171   case dwarf::DW_TAG_null:
172   case dwarf::DW_TAG_compile_unit:
173   case dwarf::DW_TAG_partial_unit:
174   case dwarf::DW_TAG_type_unit:
175   case dwarf::DW_TAG_skeleton_unit: {
176     return std::nullopt;
177   }
178   case dwarf::DW_TAG_namespace: {
179     // Check if current namespace refers another.
180     if (UnitEntryPair.CU->find(UnitEntryPair.DieEntry, dwarf::DW_AT_extension))
181       UnitEntryPair = UnitEntryPair.getNamespaceOrigin();
182 
183     // Content of anonimous namespaces should not be deduplicated.
184     if (!UnitEntryPair.CU->find(UnitEntryPair.DieEntry, dwarf::DW_AT_name))
185       llvm_unreachable("Cann't deduplicate anonimous namespace");
186 
187     return UnitEntryPair;
188   }
189   default:
190     return UnitEntryPair;
191   }
192 }
193 
194 Error SyntheticTypeNameBuilder::addParentName(
195     UnitEntryPairTy &InputUnitEntryPair) {
196   std::optional<UnitEntryPairTy> UnitEntryPair = InputUnitEntryPair.getParent();
197   if (!UnitEntryPair)
198     return Error::success();
199 
200   UnitEntryPair = getTypeDeduplicationCandidate(*UnitEntryPair);
201   if (!UnitEntryPair)
202     return Error::success();
203 
204   if (TypeEntry *ImmediateParentName =
205           UnitEntryPair->CU->getDieTypeEntry(UnitEntryPair->DieEntry)) {
206     SyntheticName += ImmediateParentName->getKey();
207     SyntheticName += ".";
208     return Error::success();
209   }
210 
211   // Collect parent entries.
212   SmallVector<UnitEntryPairTy, 10> Parents;
213   do {
214     Parents.push_back(*UnitEntryPair);
215 
216     UnitEntryPair = UnitEntryPair->getParent();
217     if (!UnitEntryPair)
218       break;
219 
220     UnitEntryPair = getTypeDeduplicationCandidate(*UnitEntryPair);
221     if (!UnitEntryPair)
222       break;
223 
224   } while (!UnitEntryPair->CU->getDieTypeEntry(UnitEntryPair->DieEntry));
225 
226   // Assign name for each parent entry.
227   size_t NameStart = SyntheticName.size();
228   for (UnitEntryPairTy Parent : reverse(Parents)) {
229     SyntheticName.resize(NameStart);
230     if (Error Err = addDIETypeName(Parent, std::nullopt, true))
231       return Err;
232   }
233 
234   // Add parents delimiter.
235   SyntheticName += ".";
236   return Error::success();
237 }
238 
239 void SyntheticTypeNameBuilder::addDieNameFromDeclFileAndDeclLine(
240     UnitEntryPairTy &InputUnitEntryPair, bool &HasDeclFileName) {
241   if (std::optional<DWARFFormValue> DeclFileVal = InputUnitEntryPair.CU->find(
242           InputUnitEntryPair.DieEntry, dwarf::DW_AT_decl_file)) {
243     if (std::optional<DWARFFormValue> DeclLineVal = InputUnitEntryPair.CU->find(
244             InputUnitEntryPair.DieEntry, dwarf::DW_AT_decl_line)) {
245       if (std::optional<std::pair<StringRef, StringRef>> DirAndFilename =
246               InputUnitEntryPair.CU->getDirAndFilenameFromLineTable(
247                   *DeclFileVal)) {
248         SyntheticName += DirAndFilename->first;
249         SyntheticName += DirAndFilename->second;
250 
251         if (std::optional<uint64_t> DeclLineIntVal =
252                 dwarf::toUnsigned(*DeclLineVal)) {
253           SyntheticName += " ";
254           SyntheticName += utohexstr(*DeclLineIntVal);
255         }
256 
257         HasDeclFileName = true;
258       }
259     }
260   }
261 }
262 
263 void SyntheticTypeNameBuilder::addValueName(UnitEntryPairTy InputUnitEntryPair,
264                                             dwarf::Attribute Attr) {
265   if (std::optional<DWARFFormValue> Val =
266           InputUnitEntryPair.CU->find(InputUnitEntryPair.DieEntry, Attr)) {
267     if (std::optional<uint64_t> ConstVal = Val->getAsUnsignedConstant()) {
268       SyntheticName += " ";
269       SyntheticName += std::to_string(*ConstVal);
270     } else if (std::optional<int64_t> ConstVal = Val->getAsSignedConstant()) {
271       SyntheticName += " ";
272       SyntheticName += std::to_string(*ConstVal);
273     }
274   }
275 }
276 
277 Error SyntheticTypeNameBuilder::addReferencedODRDies(
278     UnitEntryPairTy InputUnitEntryPair, bool AssignNameToTypeDescriptor,
279     ArrayRef<dwarf::Attribute> ODRAttrs) {
280   bool FirstIteration = true;
281   for (dwarf::Attribute Attr : ODRAttrs) {
282     if (std::optional<DWARFFormValue> AttrValue =
283             InputUnitEntryPair.CU->find(InputUnitEntryPair.DieEntry, Attr)) {
284       std::optional<UnitEntryPairTy> RefDie =
285           InputUnitEntryPair.CU->resolveDIEReference(
286               *AttrValue, ResolveInterCUReferencesMode::Resolve);
287 
288       if (!RefDie)
289         continue;
290 
291       if (!RefDie->DieEntry)
292         return createStringError(std::errc::invalid_argument,
293                                  "Cann't resolve DIE reference");
294 
295       if (!FirstIteration)
296         SyntheticName += ",";
297 
298       RecursionDepth++;
299       if (RecursionDepth > 1000)
300         return createStringError(
301             std::errc::invalid_argument,
302             "Cann't parse input DWARF. Recursive dependence.");
303 
304       if (Error Err =
305               addDIETypeName(*RefDie, std::nullopt, AssignNameToTypeDescriptor))
306         return Err;
307       RecursionDepth--;
308       FirstIteration = false;
309     }
310   }
311 
312   return Error::success();
313 }
314 
315 Error SyntheticTypeNameBuilder::addTypeName(UnitEntryPairTy InputUnitEntryPair,
316                                             bool AddParentNames) {
317   bool HasLinkageName = false;
318   bool HasShortName = false;
319   bool HasTemplatesInShortName = false;
320   bool HasDeclFileName = false;
321 
322   // Try to get name from the DIE.
323   if (std::optional<DWARFFormValue> Val = InputUnitEntryPair.CU->find(
324           InputUnitEntryPair.DieEntry,
325           {dwarf::DW_AT_MIPS_linkage_name, dwarf::DW_AT_linkage_name})) {
326     // Firstly check for linkage name.
327     SyntheticName += dwarf::toStringRef(Val);
328     HasLinkageName = true;
329   } else if (std::optional<DWARFFormValue> Val = InputUnitEntryPair.CU->find(
330                  InputUnitEntryPair.DieEntry, dwarf::DW_AT_name)) {
331     // Then check for short name.
332     StringRef Name = dwarf::toStringRef(Val);
333     SyntheticName += Name;
334 
335     HasShortName = true;
336     HasTemplatesInShortName =
337         Name.ends_with(">") && Name.count("<") != 0 && !Name.ends_with("<=>");
338   } else {
339     // Finally check for declaration attributes.
340     addDieNameFromDeclFileAndDeclLine(InputUnitEntryPair, HasDeclFileName);
341   }
342 
343   // Add additional name parts for some DIEs.
344   switch (InputUnitEntryPair.DieEntry->getTag()) {
345   case dwarf::DW_TAG_union_type:
346   case dwarf::DW_TAG_interface_type:
347   case dwarf::DW_TAG_class_type:
348   case dwarf::DW_TAG_structure_type:
349   case dwarf::DW_TAG_subroutine_type:
350   case dwarf::DW_TAG_subprogram: {
351     if (InputUnitEntryPair.CU->find(InputUnitEntryPair.DieEntry,
352                                     dwarf::DW_AT_artificial))
353       SyntheticName += "^";
354 
355     // No need to add signature information for linkage name,
356     // also no need to add template parameters name if short name already
357     // includes them.
358     if (!HasLinkageName)
359       if (Error Err =
360               addSignature(InputUnitEntryPair, !HasTemplatesInShortName))
361         return Err;
362   } break;
363   case dwarf::DW_TAG_coarray_type:
364   case dwarf::DW_TAG_array_type: {
365     addArrayDimension(InputUnitEntryPair);
366   } break;
367   case dwarf::DW_TAG_subrange_type: {
368     addValueName(InputUnitEntryPair, dwarf::DW_AT_count);
369   } break;
370   case dwarf::DW_TAG_template_value_parameter: {
371     if (!HasTemplatesInShortName) {
372       // TODO add support for DW_AT_location
373       addValueName(InputUnitEntryPair, dwarf::DW_AT_const_value);
374     }
375   } break;
376   default: {
377     // Nothing to do.
378   } break;
379   }
380 
381   // If name for the DIE is not determined yet add referenced types to the name.
382   if (!HasLinkageName && !HasShortName && !HasDeclFileName) {
383     if (InputUnitEntryPair.CU->find(InputUnitEntryPair.DieEntry,
384                                     getODRAttributes()))
385       if (Error Err = addReferencedODRDies(InputUnitEntryPair, AddParentNames,
386                                            getODRAttributes()))
387         return Err;
388   }
389 
390   return Error::success();
391 }
392 
393 Error SyntheticTypeNameBuilder::addDIETypeName(
394     UnitEntryPairTy InputUnitEntryPair,
395     std::optional<std::pair<size_t, size_t>> ChildIndex,
396     bool AssignNameToTypeDescriptor) {
397   std::optional<UnitEntryPairTy> UnitEntryPair =
398       getTypeDeduplicationCandidate(InputUnitEntryPair);
399   if (!UnitEntryPair)
400     return Error::success();
401 
402   TypeEntry *TypeEntryPtr =
403       InputUnitEntryPair.CU->getDieTypeEntry(InputUnitEntryPair.DieEntry);
404   // Check if DIE already has a name.
405   if (!TypeEntryPtr) {
406     size_t NameStart = SyntheticName.size();
407     if (AssignNameToTypeDescriptor) {
408       if (Error Err = addParentName(*UnitEntryPair))
409         return Err;
410     }
411     addTypePrefix(UnitEntryPair->DieEntry);
412 
413     if (ChildIndex) {
414       addOrderedName(*ChildIndex);
415     } else {
416       if (Error Err = addTypeName(*UnitEntryPair, AssignNameToTypeDescriptor))
417         return Err;
418     }
419 
420     if (AssignNameToTypeDescriptor) {
421       // Add built name to the DIE.
422       TypeEntryPtr = TypePoolRef.insert(SyntheticName.substr(NameStart));
423       InputUnitEntryPair.CU->setDieTypeEntry(InputUnitEntryPair.DieEntry,
424                                              TypeEntryPtr);
425     }
426   } else
427     SyntheticName += TypeEntryPtr->getKey();
428 
429   return Error::success();
430 }
431 
432 void SyntheticTypeNameBuilder::addTypePrefix(
433     const DWARFDebugInfoEntry *DieEntry) {
434   switch (DieEntry->getTag()) {
435   case dwarf::DW_TAG_base_type: {
436     SyntheticName += "{0}";
437   } break;
438   case dwarf::DW_TAG_namespace: {
439     SyntheticName += "{1}";
440   } break;
441   case dwarf::DW_TAG_formal_parameter: {
442     SyntheticName += "{2}";
443   } break;
444   // dwarf::DW_TAG_unspecified_parameters have the same prefix as before.
445   case dwarf::DW_TAG_unspecified_parameters: {
446     SyntheticName += "{2}";
447   } break;
448   case dwarf::DW_TAG_template_type_parameter: {
449     SyntheticName += "{3}";
450   } break;
451   // dwarf::DW_TAG_template_value_parameter have the same prefix as before.
452   case dwarf::DW_TAG_template_value_parameter: {
453     SyntheticName += "{3}";
454   } break;
455   case dwarf::DW_TAG_GNU_formal_parameter_pack: {
456     SyntheticName += "{4}";
457   } break;
458   case dwarf::DW_TAG_GNU_template_parameter_pack: {
459     SyntheticName += "{5}";
460   } break;
461   case dwarf::DW_TAG_inheritance: {
462     SyntheticName += "{6}";
463   } break;
464   case dwarf::DW_TAG_array_type: {
465     SyntheticName += "{7}";
466   } break;
467   case dwarf::DW_TAG_class_type: {
468     SyntheticName += "{8}";
469   } break;
470   case dwarf::DW_TAG_enumeration_type: {
471     SyntheticName += "{9}";
472   } break;
473   case dwarf::DW_TAG_imported_declaration: {
474     SyntheticName += "{A}";
475   } break;
476   case dwarf::DW_TAG_member: {
477     SyntheticName += "{B}";
478   } break;
479   case dwarf::DW_TAG_pointer_type: {
480     SyntheticName += "{C}";
481   } break;
482   case dwarf::DW_TAG_reference_type: {
483     SyntheticName += "{D}";
484   } break;
485   case dwarf::DW_TAG_string_type: {
486     SyntheticName += "{E}";
487   } break;
488   case dwarf::DW_TAG_structure_type: {
489     SyntheticName += "{F}";
490   } break;
491   case dwarf::DW_TAG_subroutine_type: {
492     SyntheticName += "{G}";
493   } break;
494   case dwarf::DW_TAG_typedef: {
495     SyntheticName += "{H}";
496   } break;
497   case dwarf::DW_TAG_union_type: {
498     SyntheticName += "{I}";
499   } break;
500   case dwarf::DW_TAG_variant: {
501     SyntheticName += "{J}";
502   } break;
503   case dwarf::DW_TAG_inlined_subroutine: {
504     SyntheticName += "{K}";
505   } break;
506   case dwarf::DW_TAG_module: {
507     SyntheticName += "{L}";
508   } break;
509   case dwarf::DW_TAG_ptr_to_member_type: {
510     SyntheticName += "{M}";
511   } break;
512   case dwarf::DW_TAG_set_type: {
513     SyntheticName += "{N}";
514   } break;
515   case dwarf::DW_TAG_subrange_type: {
516     SyntheticName += "{O}";
517   } break;
518   case dwarf::DW_TAG_with_stmt: {
519     SyntheticName += "{P}";
520   } break;
521   case dwarf::DW_TAG_access_declaration: {
522     SyntheticName += "{Q}";
523   } break;
524   case dwarf::DW_TAG_catch_block: {
525     SyntheticName += "{R}";
526   } break;
527   case dwarf::DW_TAG_const_type: {
528     SyntheticName += "{S}";
529   } break;
530   case dwarf::DW_TAG_constant: {
531     SyntheticName += "{T}";
532   } break;
533   case dwarf::DW_TAG_enumerator: {
534     SyntheticName += "{U}";
535   } break;
536   case dwarf::DW_TAG_file_type: {
537     SyntheticName += "{V}";
538   } break;
539   case dwarf::DW_TAG_friend: {
540     SyntheticName += "{W}";
541   } break;
542   case dwarf::DW_TAG_namelist: {
543     SyntheticName += "{X}";
544   } break;
545   case dwarf::DW_TAG_namelist_item: {
546     SyntheticName += "{Y}";
547   } break;
548   case dwarf::DW_TAG_packed_type: {
549     SyntheticName += "{Z}";
550   } break;
551   case dwarf::DW_TAG_subprogram: {
552     SyntheticName += "{a}";
553   } break;
554   case dwarf::DW_TAG_thrown_type: {
555     SyntheticName += "{b}";
556   } break;
557   case dwarf::DW_TAG_variant_part: {
558     SyntheticName += "{c}";
559   } break;
560   case dwarf::DW_TAG_variable: {
561     SyntheticName += "{d}";
562   } break;
563   case dwarf::DW_TAG_volatile_type: {
564     SyntheticName += "{e}";
565   } break;
566   case dwarf::DW_TAG_dwarf_procedure: {
567     SyntheticName += "{f}";
568   } break;
569   case dwarf::DW_TAG_restrict_type: {
570     SyntheticName += "{g}";
571   } break;
572   case dwarf::DW_TAG_interface_type: {
573     SyntheticName += "{h}";
574   } break;
575   case dwarf::DW_TAG_imported_module: {
576     SyntheticName += "{i}";
577   } break;
578   case dwarf::DW_TAG_unspecified_type: {
579     SyntheticName += "{j}";
580   } break;
581   case dwarf::DW_TAG_imported_unit: {
582     SyntheticName += "{k}";
583   } break;
584   case dwarf::DW_TAG_condition: {
585     SyntheticName += "{l}";
586   } break;
587   case dwarf::DW_TAG_shared_type: {
588     SyntheticName += "{m}";
589   } break;
590   case dwarf::DW_TAG_rvalue_reference_type: {
591     SyntheticName += "{n}";
592   } break;
593   case dwarf::DW_TAG_template_alias: {
594     SyntheticName += "{o}";
595   } break;
596   case dwarf::DW_TAG_coarray_type: {
597     SyntheticName += "{p}";
598   } break;
599   case dwarf::DW_TAG_generic_subrange: {
600     SyntheticName += "{q}";
601   } break;
602   case dwarf::DW_TAG_dynamic_type: {
603     SyntheticName += "{r}";
604   } break;
605   case dwarf::DW_TAG_atomic_type: {
606     SyntheticName += "{s}";
607   } break;
608   case dwarf::DW_TAG_call_site: {
609     SyntheticName += "{t}";
610   } break;
611   case dwarf::DW_TAG_call_site_parameter: {
612     SyntheticName += "{u}";
613   } break;
614   case dwarf::DW_TAG_immutable_type: {
615     SyntheticName += "{v}";
616   } break;
617   case dwarf::DW_TAG_entry_point: {
618     SyntheticName += "{w}";
619   } break;
620   case dwarf::DW_TAG_label: {
621     SyntheticName += "{x}";
622   } break;
623   case dwarf::DW_TAG_lexical_block: {
624     SyntheticName += "{y}";
625   } break;
626   case dwarf::DW_TAG_common_block: {
627     SyntheticName += "{z}";
628   } break;
629   case dwarf::DW_TAG_common_inclusion: {
630     SyntheticName += "{|}";
631   } break;
632   case dwarf::DW_TAG_try_block: {
633     SyntheticName += "{~}";
634   } break;
635 
636   case dwarf::DW_TAG_null: {
637     llvm_unreachable("No type prefix for DW_TAG_null");
638   } break;
639   case dwarf::DW_TAG_compile_unit: {
640     llvm_unreachable("No type prefix for DW_TAG_compile_unit");
641   } break;
642   case dwarf::DW_TAG_partial_unit: {
643     llvm_unreachable("No type prefix for DW_TAG_partial_unit");
644   } break;
645   case dwarf::DW_TAG_type_unit: {
646     llvm_unreachable("No type prefix for DW_TAG_type_unit");
647   } break;
648   case dwarf::DW_TAG_skeleton_unit: {
649     llvm_unreachable("No type prefix for DW_TAG_skeleton_unit");
650   } break;
651 
652   default: {
653     SyntheticName += "{~~";
654     SyntheticName += utohexstr(DieEntry->getTag());
655     SyntheticName += "}";
656   } break;
657   }
658 }
659 
660 OrderedChildrenIndexAssigner::OrderedChildrenIndexAssigner(
661     CompileUnit &CU, const DWARFDebugInfoEntry *DieEntry) {
662   switch (DieEntry->getTag()) {
663   case dwarf::DW_TAG_array_type:
664   case dwarf::DW_TAG_coarray_type:
665   case dwarf::DW_TAG_class_type:
666   case dwarf::DW_TAG_common_block:
667   case dwarf::DW_TAG_lexical_block:
668   case dwarf::DW_TAG_structure_type:
669   case dwarf::DW_TAG_subprogram:
670   case dwarf::DW_TAG_subroutine_type:
671   case dwarf::DW_TAG_union_type:
672   case dwarf::DW_TAG_GNU_template_template_param:
673   case dwarf::DW_TAG_GNU_formal_parameter_pack: {
674     NeedCountChildren = true;
675   } break;
676   case dwarf::DW_TAG_enumeration_type: {
677     // TODO : do we need to add condition
678     NeedCountChildren = true;
679   } break;
680   default: {
681     // Nothing to do.
682   }
683   }
684 
685   // Calculate maximal index value
686   if (NeedCountChildren) {
687     for (const DWARFDebugInfoEntry *CurChild = CU.getFirstChildEntry(DieEntry);
688          CurChild && CurChild->getAbbreviationDeclarationPtr();
689          CurChild = CU.getSiblingEntry(CurChild)) {
690       std::optional<size_t> ArrayIndex = tagToArrayIndex(CU, CurChild);
691       if (!ArrayIndex)
692         continue;
693 
694       assert((*ArrayIndex < ChildIndexesWidth.size()) &&
695              "Wrong index for ChildIndexesWidth");
696       ChildIndexesWidth[*ArrayIndex]++;
697     }
698 
699     // Calculate index field width(number of digits in hexadecimal
700     // representation).
701     for (size_t &Width : ChildIndexesWidth) {
702       size_t digitsCounter = 1;
703       size_t NumToCompare = 15;
704 
705       while (NumToCompare < Width) {
706         NumToCompare <<= 4;
707         digitsCounter++;
708       }
709 
710       Width = digitsCounter;
711     }
712   }
713 }
714 
715 std::optional<size_t> OrderedChildrenIndexAssigner::tagToArrayIndex(
716     CompileUnit &CU, const DWARFDebugInfoEntry *DieEntry) {
717   if (!NeedCountChildren)
718     return std::nullopt;
719 
720   switch (DieEntry->getTag()) {
721   case dwarf::DW_TAG_unspecified_parameters:
722   case dwarf::DW_TAG_formal_parameter:
723     return 0;
724   case dwarf::DW_TAG_template_value_parameter:
725   case dwarf::DW_TAG_template_type_parameter:
726     return 1;
727   case dwarf::DW_TAG_enumeration_type:
728     if (std::optional<uint32_t> ParentIdx = DieEntry->getParentIdx()) {
729       if (*ParentIdx && CU.getDebugInfoEntry(*ParentIdx)->getTag() ==
730                             dwarf::DW_TAG_array_type)
731         return 2;
732     }
733     return std::nullopt;
734   case dwarf::DW_TAG_subrange_type:
735     return 3;
736   case dwarf::DW_TAG_generic_subrange:
737     return 4;
738   case dwarf::DW_TAG_enumerator:
739     return 5;
740   case dwarf::DW_TAG_namelist_item:
741     return 6;
742   case dwarf::DW_TAG_member:
743     return 7;
744   default:
745     return std::nullopt;
746   };
747 }
748 
749 std::optional<std::pair<size_t, size_t>>
750 OrderedChildrenIndexAssigner::getChildIndex(
751     CompileUnit &CU, const DWARFDebugInfoEntry *ChildDieEntry) {
752   std::optional<size_t> ArrayIndex = tagToArrayIndex(CU, ChildDieEntry);
753   if (!ArrayIndex)
754     return std::nullopt;
755 
756   assert((*ArrayIndex < OrderedChildIdxs.size()) &&
757          "Wrong index for ChildIndexesWidth");
758   assert(ChildIndexesWidth[*ArrayIndex] < 16 &&
759          "Index width exceeds 16 digits.");
760 
761   std::pair<size_t, size_t> Result = std::make_pair(
762       OrderedChildIdxs[*ArrayIndex], ChildIndexesWidth[*ArrayIndex]);
763   OrderedChildIdxs[*ArrayIndex]++;
764   return Result;
765 }
766