[DWARF][NFC] add ParentIdx and SiblingIdx to DWARFDebugInfoEntry for faster navigation.

[avl]

Summary

This patch implements suggestion done while reviewing D102634. It adds two fields:
ParentIdx and SiblingIdx. These fields allow fast navigation to die parent and
die sibling. These fields are set at the moment when dies are loaded.

dsymutil works 2% faster with this patch(run on clang binary).

[clayborg]

So the DWARFUnit class no longer needs to be involved in the getting the parent, sibling, child stuff if we end up setting ParentIdx and SiblingIdx as a relative offset. LLDB's DWARF parser stores, and yes has a bad name for, the parent index which is the offset to subtract from "this" where "this" is a DWARFDebugInfoEntry. Since the DWARFUnits store an vector of DWARFDebugInfoEntry items after it parses all of the DIEs, then you can just subtract "ParentIdx" (which might be better named "ParentOffset") from "this" and get the correct DWARFDebugInfoEntry. Same with the SiblingIdx, if it is non zero, it is the offset to add to "this" to get the sibling. See inlined comments and see LLDB's DWARFDebugInfoEntry.h/.cpp and DWARFDie.h/.cpp.

The other thing to note is LLDB doesn't store the NULL tags in this DWARFDebugInfoEntry vector in the DWARFUnit. This saves a lot of memory for us, but that is for another patch.

llvm/include/llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h

28

LLDB actually stores this as the offset from this. So you can easily just do subtract math with "this" when you have a DWARFDebugInfoEntry since we know it is stored in an array. LLDB comments from it's DWARFDebugInfoEntry.h:

// How many to subtract from "this" to get the parent. If zero this die has no parent

30

Same deal where sibling index is actually the number to add to "this" to get the sibling DIE.

// How many to add to "this" to get the sibling.
// If it is zero, then the DIE doesn't have children, or the
// DWARF claimed it had children but the DIE only contained
// a single NULL terminating child.
`

47–65

If we store this as an offset for the parent index and sibling index, we can add simple functions here:

DWARFDebugInfoEntry *getParent() {
  return ParentIdx > 0 ? this - ParentIdx : nullptr;
}

const DWARFDebugInfoEntry *getSibling() const {
  return SiblingIdx > 0 ? this + SiblingIdx : nullptr;
}

DWARFDebugInfoEntry *getFirstChild() {
  return hasChildren() ? this + 1 : nullptr;
}

And then these functions can be used in the DWARFDie class.

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

769–780

This entire function is no longer needed if we use the suggested functions in DWARFDebugInfoEntry

782–793

Ditto

795

This function could be done down in DWARFDebugInfoEntry now.

825

This function could be done down in DWARFDebugInfoEntry now.

838

This function could be done down in DWARFDebugInfoEntry now.

850–871

This code should no longer be needed right?

[dblaikie]

ParentRelativeOffset and NextSiblingRelativeOffset might be suitable - though I guess technically the latter could be "numDescendants" (total number of direct and indirect descendants - including nulls, if those are in the list, or not if they aren't). I can't think of a good equivalent name for the parent one - I guess "siblingNumber/siblingIndex/childIndex/something" but I don't have a great name there.

[avl]

So the DWARFUnit class no longer needs to be involved in the getting the parent, sibling, child stuff if we end up setting ParentIdx and SiblingIdx as a relative offset. LLDB's DWARF parser stores, and yes has a bad name for, the parent index which is the offset to subtract from "this" where "this" is a DWARFDebugInfoEntry. Since the DWARFUnits store an vector of DWARFDebugInfoEntry items after it parses all of the DIEs, then you can just subtract "ParentIdx" (which might be better named "ParentOffset") from "this" and get the correct DWARFDebugInfoEntry. Same with the SiblingIdx, if it is non zero, it is the offset to add to "this" to get the sibling. See inlined comments and see LLDB's DWARFDebugInfoEntry.h/.cpp and DWARFDie.h/.cpp.

Oh, I missed the idea to not use DWARFUnit for navigation. Will change indexes to deltas.

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

838

Only this part could not be moved into the DWARFDebugInfoEntry:

uint32_t DieIdx = getDIEIndex(Die);
if (DieIdx == 0 && DieArray.size() > 1 &&
    DieArray.back().getTag() == dwarf::DW_TAG_null) {
  // For the unit die we might take last item from DieArray.
  assert(DieIdx == getDIEIndex(getUnitDIE()) && "Bad unit die");
  return DWARFDie(this, &DieArray.back());
}

Thus, it looks like getLastChild may still be implemented in DWARFUnit.

[avl]

After some thinking, it looks like this idea "So the DWARFUnit class no longer needs to be involved in the getting the parent, sibling, child stuff" may not be suitable for dies navigation. The reason for this is that DWARFDebugInfoEntry does not know the size of DWARFDebugInfoEntry vector. That makes it impossible to assert and/or check whether new pointers to the DWARFDebugInfoEntry-es are valid. i.e.

a) we could not write assertions for the proper value of DWARFDebugInfoEntry pointer.
b) we could not stop parsing if we passes out of DWARFDebugInfoEntry vector.

f.e. :

  DWARFDie DWARFUnit::getFirstChild(const DWARFDebugInfoEntry *Die) {
  if (!Die->hasChildren())
    return DWARFDie();

  // We do not want access out of bounds when parsing corrupted debug data.
  size_t I = getDIEIndex(Die) + 1;
  if (I >= DieArray.size())    <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    return DWARFDie();
  return DWARFDie(this, &DieArray[I]);
}

We could not do the same check inside DWARFDebugInfoEntry::getFirstChild()

DWARFDie DWARFUnit::getLastChild(const DWARFDebugInfoEntry *Die) {
...
  uint32_t ChildIdx = DieIdx + 1;
  while (ChildIdx < DieArray.size()) {   <<<<<<<<<<<<<<<<<<<<
    assert(*DieArray[ChildIdx].getParentIdx() == DieIdx && "Bad parent");

    if (DieArray[ChildIdx].getTag() == dwarf::DW_TAG_null)
      return DWARFDie(this, &DieArray[ChildIdx]);

    if (Optional<uint32_t> Idx = DieArray[ChildIdx].getSiblingIdx())
      ChildIdx = *Idx;
    else
      // Return empty die if DWARF is corrupted.
      return DWARFDie();
  }

We could not do the same check inside DWARFDebugInfoEntry::getLastChild()

if (Optional<uint32_t> SiblingIdx = Die->getSiblingIdx()) {
  assert(*SiblingIdx < DieArray.size() &&   <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
         "SiblingIdx is out of DieArray boundaries");
  assert(DieArray[*SiblingIdx - 1].getTag() == dwarf::DW_TAG_null &&
         "Bad end of children marker");
  return DWARFDie(this, &DieArray[*SiblingIdx - 1]);
}

above assertion could not be done inside DWARFDebugInfoEntry.

I propose to use current solution when DWARFUnit does dies navigation and properly validates elements. What do you think?

[clayborg]

In D110363#3027286, @avl wrote:

After some thinking, it looks like this idea "So the DWARFUnit class no longer needs to be involved in the getting the parent, sibling, child stuff" may not be suitable for dies navigation. The reason for this is that DWARFDebugInfoEntry does not know the size of DWARFDebugInfoEntry vector. That makes it impossible to assert and/or check whether new pointers to the DWARFDebugInfoEntry-es are valid. i.e.

I propose to use current solution when DWARFUnit does dies navigation and properly validates elements. What do you think?

The assertions can't be done, that is true, but the theory is if we parse all of the DIEs correctly, they should all have valid values for the ParentIdx and SiblingIdx up front and we should have nothing to worry about. We should create the data correctly one time and then trust it. We have been using this in the LLDB parser for many years and it is quite stable and efficient.

[clayborg]

In D110363#3028027, @clayborg wrote:

In D110363#3027286, @avl wrote:

After some thinking, it looks like this idea "So the DWARFUnit class no longer needs to be involved in the getting the parent, sibling, child stuff" may not be suitable for dies navigation. The reason for this is that DWARFDebugInfoEntry does not know the size of DWARFDebugInfoEntry vector. That makes it impossible to assert and/or check whether new pointers to the DWARFDebugInfoEntry-es are valid. i.e.

I propose to use current solution when DWARFUnit does dies navigation and properly validates elements. What do you think?

The assertions can't be done, that is true, but the theory is if we parse all of the DIEs correctly, they should all have valid values for the ParentIdx and SiblingIdx up front and we should have nothing to worry about. We should create the data correctly one time and then trust it. We have been using this in the LLDB parser for many years and it is quite stable and efficient.

Though if you strongly believe this should be done I have no issue with it.

[clayborg]

From a performance perspective, I would rather parse all of the DIEs correctly one time and do any needed asserts in there, and then keep DIE navigation as fast as possible with as few checks as possible knowing that we created solid data structures.

[dblaikie]

In D110363#3028027, @clayborg wrote:

In D110363#3027286, @avl wrote:

After some thinking, it looks like this idea "So the DWARFUnit class no longer needs to be involved in the getting the parent, sibling, child stuff" may not be suitable for dies navigation. The reason for this is that DWARFDebugInfoEntry does not know the size of DWARFDebugInfoEntry vector. That makes it impossible to assert and/or check whether new pointers to the DWARFDebugInfoEntry-es are valid. i.e.

I propose to use current solution when DWARFUnit does dies navigation and properly validates elements. What do you think?

The assertions can't be done, that is true, but the theory is if we parse all of the DIEs correctly, they should all have valid values for the ParentIdx and SiblingIdx up front and we should have nothing to worry about. We should create the data correctly one time and then trust it. We have been using this in the LLDB parser for many years and it is quite stable and efficient.

Yep, +1 to that. If these offsets were based on parsed input, then there'd be a possibility of them being incorrect/invalid/out of range, but they aren't - they'd be computed based on the hierarchy created in memory by libDebugInfo.

That said, I do find it a bit unfortunate to have objects that have an implicit requirement on how they're allocated - knowing they're in an array and walking around that array to find other things. But that ship's probably solidly sailed on these APIs and might as well do more of it? (or would it be reasonable to shift these sort of APIs up into DWARFDie and access the array via the DWARFUnit? Though maybe there's observable performance cost of that? I'd be a bit surprised)

[avl]

The assertions can't be done, that is true, but the theory is if we parse all of the DIEs correctly, they should all have valid values for the ParentIdx and SiblingIdx up front and we should have nothing to worry about. We should create the data correctly one time and then trust it. We have been using this in the LLDB parser for many years and it is quite stable and efficient.

Yep, +1 to that. If these offsets were based on parsed input, then there'd be a possibility of them being incorrect/invalid/out of range, but they aren't - they'd be computed based on the hierarchy created in memory by libDebugInfo.

Agreed that data should be created correctly and then no need to insert *run time* checks for them. But things looks differently for the assertions - that is a purpose of assertions to prove things which should be correct. In such case if any error occurred - the assertion will show it. If some incorrect memory access from new other code would overwrite ParentIdx then assertion will show it.

Other then assertions there are cases when we still need run-time checks for array boundaries, even for correctly parsed DWARF:

  DWARFDie DWARFUnit::getFirstChild(const DWARFDebugInfoEntry *Die) {
  if (!Die->hasChildren())
    return DWARFDie();

  // We do not want access out of bounds when parsing corrupted debug data.
  size_t I = getDIEIndex(Die) + 1;
  if (I >= DieArray.size())    <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    return DWARFDie();
  return DWARFDie(this, &DieArray[I]);
}

DWARFDie DWARFUnit::getPreviousSibling(const DWARFDebugInfoEntry *Die) {
  if (!Die)
    return DWARFDie();

  ...

  // Find the previous DIE whose parent is the same as the Die's parent.
  for (size_t I = getDIEIndex(Die); I > 0;) {   <<<<<<<<<< We need to know DieArray boundary to properly search for the previous sibling.
    --I;

In short, I think having assertions is useful, but if you think they are not needed then I am OK to removing them. Without assertions we still have a cases when array size should be known for proper navigation. Thus it looks correct to leave this navigation API(getParent, GetSibling, GetPrevSibling, GetFirstChild, GetLastChild) inside DWARFUnit(Since DWARFDebugInfoEntry does not know about DieArray).

[dblaikie]

In D110363#3028338, @avl wrote:

The assertions can't be done, that is true, but the theory is if we parse all of the DIEs correctly, they should all have valid values for the ParentIdx and SiblingIdx up front and we should have nothing to worry about. We should create the data correctly one time and then trust it. We have been using this in the LLDB parser for many years and it is quite stable and efficient.

Yep, +1 to that. If these offsets were based on parsed input, then there'd be a possibility of them being incorrect/invalid/out of range, but they aren't - they'd be computed based on the hierarchy created in memory by libDebugInfo.

Agreed that data should be created correctly and then no need to insert *run time* checks for them. But things looks differently for the assertions - that is a purpose of assertions to prove things which should be correct. In such case if any error occurred - the assertion will show it. If some incorrect memory access from new other code would overwrite ParentIdx then assertion will show it.

Other then assertions there are cases when we still need run-time checks for array boundaries, even for correctly parsed DWARF:

  DWARFDie DWARFUnit::getFirstChild(const DWARFDebugInfoEntry *Die) {
  if (!Die->hasChildren())
    return DWARFDie();

  // We do not want access out of bounds when parsing corrupted debug data.
  size_t I = getDIEIndex(Die) + 1;
  if (I >= DieArray.size())    <<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<<
    return DWARFDie();
  return DWARFDie(this, &DieArray[I]);
}

Yeah, we could classify the data as invalid sooner - like we wouldn't add a partial DIE (one where its abbreviation-defined size is larger than the remaining buffer space to read from) we perhaps could consider a DIE that says it has children but there's no space for children or no null child DIE to define the end of the list - as invalid too.

DWARFDie DWARFUnit::getPreviousSibling(const DWARFDebugInfoEntry *Die) {
  if (!Die)
    return DWARFDie();

  ...

  // Find the previous DIE whose parent is the same as the Die's parent.
  for (size_t I = getDIEIndex(Die); I > 0;) {   <<<<<<<<<< We need to know DieArray boundary to properly search for the previous sibling.
    --I;

In short, I think having assertions is useful, but if you think they are not needed then I am OK to removing them. Without assertions we still have a cases when array size should be known for proper navigation. Thus it looks correct to leave this navigation API(getParent, GetSibling, GetPrevSibling, GetFirstChild, GetLastChild) inside DWARFUnit(Since DWARFDebugInfoEntry does not know about DieArray).

What does LLDB use here? Does it not offer a 'previous sibling' API?

(though, honestly - if some operations require the underlying array anyway - I think using absolute indexes is probably reasonable unless there's some compelling performance issues)

[avl]

(though, honestly - if some operations require the underlying array anyway - I think using absolute indexes is probably reasonable unless there's some compelling performance issues)

My understanding is that from performance point of view indexes and deltas - are equal:

"DieArray.begin() + ParentIdx" vs "this + ParentRelativeOffset"

[dblaikie]

In D110363#3028518, @avl wrote:

(though, honestly - if some operations require the underlying array anyway - I think using absolute indexes is probably reasonable unless there's some compelling performance issues)

My understanding is that from performance point of view indexes and deltas - are equal:

"DieArray.begin() + ParentIdx" vs "this + ParentRelativeOffset"

There's the potential for /some/ performance difference here since accessing the DieArray requires dereferencing 'this' - so there a memory access in the first case, and none (just pointer arithmetic) in the second. But yeah, I'd be surprised if it made an observable difference.

[clayborg]

I am fine with keeping stuff in DWARFUnit if you want the extra asserts in the code.

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

784–785

We don't need this if statement anymore as the sibling index won't be set for NULL DIEs.

795

This is a complex function. Do we even use it? I would doubt that anyone ever asks for the previous DIE or uses a reverse iterator. It would be nice to remove this and the operator-- from the iterator, and the reverse_iterator for the DWARFDie and see if anyone is actually using it besides the unit test that tests it. IF we don't use it we can get rid of this and stop having to modify it if we update how DWARFDebugInfoEntry stores its data.

858–870

What is this last while loop for? We should only need the normal case where SiblingIdx is set, or we have the unit die right? Everything should have a sibling except the unit DIE.

[avl]

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

784–785

Ok.

795

It is used in DWARFLinker.cpp:

for (auto Child : reverse(Die.children())) {

Probably that code might be refactored and usage of reverse iterator would not be necessary. I suggest to leave this refactoring for separate patch.

858–870

I assumed it to be used for incorrect dwarf case. But you are right - that loop might be safely removed even for incorrect dwarf case.

[avl]

addressed comments.

[clayborg]

LGTM. David you ok with everything?

[dblaikie]

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

816–832

I think this algorithm might be a bit slower than it needs to be. Maybe a bit harder to follow than it needs to be too?

Rather than checking every node from the current index back to the parent index - each node you visit that isn't a sibling, you can ask for its parent that'll let you jump potentially much further back in the index/closer to the parent.

eg: in the worst case, your previous sibling has a long chain of single children - then the algorithm I'm describing will be just as bad as a linear walk. But in the best case, where your previous sibling's first child has no children - no matter how many previous siblings that child has you can do this in only a couple of steps.

So I think the algorithm would look something like this:

// hmm, I might pull out the root die case differently:
size_t I = getDIEIndex(Die);
Optional<uint32_t> ParentIdx = Die->getParentIdx();
if (!ParentIdx) // root DIE
  return DWARFDie();
while (I > *ParentIdx)
  Optional<uint32_t> PrevDieParentIdx = DieArray[I].getParentIdx();
  // since we haven't reached the parent, this must have a valid parent (it's a sibling or a sibling's child)
  if (*PrevDieParentIdx == *ParentIdx)
    return DWARFDie(this, &DieArray[I]);
  // since we haven't reached the parent (the loop condition didn't break)
  // and we haven't reached a sibling (since we have inequal parent index) 
  // then we must be at a sibling's children - so try that DIE's parent next
  I = *PrevDieParentIdx;
}

Does that work/make sense?

Hmm, maybe it could be simplified further - there's no need to check the index every iteration because we can't skip the parent if the previous node isn't already our parent (or we're the root)... let's see:

if (!Die)
  return DWARFDie();
Optional<uint32_t> ParentIdx = Die->getParentIdx();
if (!ParentIdx) // root
  return DWARFDie();
size_t I = getDIEIndex(Die) - 1;
while (I != *ParentIdx)
  I = *DieArray[I].getParentIdx();
return DWARFDie(this, &DieArray[I]);

853

Why is this case checked for (rather than asserted) here - but for the non-root-DIE case above, it's asserted? Is this (as the TODO suggests) an invalidity that passes for the root DIE, but is caught earlier for non-root DIEs?

[avl]

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

816–832

Yeah. Good idea. Will do.

853

yeas, the reason is an invalidity that passes for the root DIE, but is caught earlier for non-root DIE. The idea is that if SiblingIdx is set in DWARFUnit::extractDIEsToVector then format is good and assertion must be satisfied. But we cannot rely on SiblingIdx of the root DIE. That is why we have run-time check for the root die and assertion for others.

[avl]

addressed comments(rewrote getPreviousSibling())

[avl]

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

816–832

I implemented variant looking more like first version. Because we need to have additional variable keeping prev die index:

while (I != *ParentIdx) <<< if I equals to ParentIdx

I = *DieArray[I].getParentIdx();

return DWARFDie(this, &DieArray[I]); <<< then we return not a prev sibling but parent.

[dblaikie]

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

853

Fair enough - could you expand on that in the comment a bit - explaining that there's this difference between the root node and other nodes.

[avl]

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

853

// If SiblingIdx is set for non-root dies we could be sure that DWARF is correct 
// and "end of children marker" must be found. For root die we do not have such a 
// guarantee(parsing root die might be stopped if "end of children marker" is missing,
// SiblingIdx is always zero for root die). That is why we do not use assertion 
// for checking for "end of children marker" for root die.

[dblaikie]

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

816–832

Oh, fair point about returning the parent - but I'd like to keep the code a bit simpler if possible.

Specifically handling the "I'm the root node" and "I have no previous sibling" up-front, and then letting the rest of the code only handle the "I'm eventually going to find my sibling" case - at least I /think/ that'd be more legible, but let's see..

Optional<uint32_t> ParentIdx = Die->getParentIdx();
if (!ParentIdx)
  return DWARFDie();
uint32_t I = getDIEIndex(Die) - 1;
if (I == *ParentIdx)  // immediately previous node is parent, there is no previous sibling
  return DWARFDie();
while (DieArray[I].getParentIdx() != *ParentIdx)
  I = DieArray[I].getParentIdx();
return DWARFDie(this, &DieArray[I]);

Maybe that?

[avl]

addressed comments(implemented getPreviousSibling as requested)

[dblaikie]

Looks alright, thanks!

llvm/include/llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h

 class DataExtractor;
 class DWARFUnit;
 
 /// DWARFDebugInfoEntry - A DIE with only the minimum required data.
 class DWARFDebugInfoEntry {
   /// Offset within the .debug_info of the start of this entry.
   uint64_t Offset = 0;
 
-  // FIXME: This could be changed to a parent_idx/sibling_idx based solution
-  // like lldb's that could be used to improve the performance of sibling
-  // iteration. Memory usage is probably acceptable - if it's good enough for
-  // lldb it's probably good enough for llvm-symbolizer, etc.
-  // There's some discussion of this direction in D102634.
-  /// The integer depth of this DIE within the compile unit DIEs where the
-  /// compile/type unit DIE has a depth of zero.
-  uint32_t Depth = 0;
+  /// Index of the parent die. UINT32_MAX if there is no parent.
+  uint32_t ParentIdx = UINT32_MAX;
+
+  /// Index of the sibling die. Zero if there is no sibling.
+  uint32_t SiblingIdx = 0;
 
   const DWARFAbbreviationDeclaration *AbbrevDecl = nullptr;
 
 public:
   DWARFDebugInfoEntry() = default;
 
   /// Extracts a debug info entry, which is a child of a given unit,
   /// starting at a given offset. If DIE can't be extracted, returns false and
   /// doesn't change OffsetPtr.
   /// High performance extraction should use this call.
   bool extractFast(const DWARFUnit &U, uint64_t *OffsetPtr,
                    const DWARFDataExtractor &DebugInfoData, uint64_t UEndOffset,
-                   uint32_t Depth);
+                   uint32_t ParentIdx);
 
   uint64_t getOffset() const { return Offset; }
-  uint32_t getDepth() const { return Depth; }
+
+  /// Returns index of the parent die.
+  Optional<uint32_t> getParentIdx() const {
+    if (ParentIdx == UINT32_MAX)
+      return None;
+
+    return ParentIdx;
+  }
+
+  /// Returns index of the sibling die.
+  Optional<uint32_t> getSiblingIdx() const {
+    if (SiblingIdx == 0)
+      return None;
+
+    return SiblingIdx;
+  }
+
+  /// Set index of sibling.
+  void setSiblingIdx(uint32_t Idx) { SiblingIdx = Idx; }
 
   dwarf::Tag getTag() const {
     return AbbrevDecl ? AbbrevDecl->getTag() : dwarf::DW_TAG_null;
   }
 
   bool hasChildren() const { return AbbrevDecl && AbbrevDecl->hasChildren(); }
 
   const DWARFAbbreviationDeclaration *getAbbreviationDeclarationPtr() const {
     return AbbrevDecl;
   }
 };
 
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_DWARF_DWARFDEBUGINFOENTRY_H

llvm/lib/DebugInfo/DWARF/DWARFDebugInfoEntry.cpp

 #include <cstddef>
 #include <cstdint>
 
 using namespace llvm;
 using namespace dwarf;
 
 bool DWARFDebugInfoEntry::extractFast(const DWARFUnit &U, uint64_t *OffsetPtr,
                                       const DWARFDataExtractor &DebugInfoData,
-                                      uint64_t UEndOffset, uint32_t D) {
+                                      uint64_t UEndOffset, uint32_t ParentIdx) {
   Offset = *OffsetPtr;
-  Depth = D;
+  this->ParentIdx = ParentIdx;
   if (Offset >= UEndOffset) {
     U.getContext().getWarningHandler()(
         createStringError(errc::invalid_argument,
                           "DWARF unit from offset 0x%8.8" PRIx64 " incl. "
                           "to offset 0x%8.8" PRIx64 " excl. "
                           "tries to read DIEs at offset 0x%8.8" PRIx64,
                           U.getOffset(), U.getNextUnitOffset(), *OffsetPtr));
     return false;

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

void DWARFUnit::extractDIEsToVector(
   // Set the offset to that of the first DIE and calculate the start of the
   // next compilation unit header.
   uint64_t DIEOffset = getOffset() + getHeaderSize();
   uint64_t NextCUOffset = getNextUnitOffset();
   DWARFDebugInfoEntry DIE;
   DWARFDataExtractor DebugInfoData = getDebugInfoExtractor();
   // The end offset has been already checked by DWARFUnitHeader::extract.
   assert(DebugInfoData.isValidOffset(NextCUOffset - 1));
-  uint32_t Depth = 0;
+  std::vector<uint32_t> Parents;
+  std::vector<uint32_t> PrevSiblings;
   bool IsCUDie = true;
 
-  while (DIE.extractFast(*this, &DIEOffset, DebugInfoData, NextCUOffset,
-                         Depth)) {
+  assert(
+      ((AppendCUDie && Dies.empty()) || (!AppendCUDie && Dies.size() == 1)) &&
+      "Dies array is not empty");
+
+  // Fill Parents and Siblings stacks with initial value.
+  Parents.push_back(UINT32_MAX);
+  if (!AppendCUDie)
+    Parents.push_back(0);
+  PrevSiblings.push_back(0);
+
+  // Start to extract dies.
+  do {
+    assert(Parents.size() > 0 && "Empty parents stack");
+    assert((Parents.back() == UINT32_MAX || Parents.back() <= Dies.size()) &&
+           "Wrong parent index");
+
+    // Extract die. Stop if any error occured.
+    if (!DIE.extractFast(*this, &DIEOffset, DebugInfoData, NextCUOffset,
+                         Parents.back()))
+      break;
+
+    // If previous sibling is remembered then update it`s SiblingIdx field.
+    if (PrevSiblings.back() > 0) {
+      assert(PrevSiblings.back() < Dies.size() &&
+             "Previous sibling index is out of Dies boundaries");
+      Dies[PrevSiblings.back()].setSiblingIdx(Dies.size());
+    }
+
+    // Store die into the Dies vector.
     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
       // our DIE entries accordingly.
       Dies.reserve(Dies.size() + getDebugInfoSize() / 14);
-      IsCUDie = false;
     } else {
+      // Remember last previous sibling.
+      PrevSiblings.back() = Dies.size();
+
       Dies.push_back(DIE);
     }
 
+    // Check for new children scope.
     if (const DWARFAbbreviationDeclaration *AbbrDecl =
             DIE.getAbbreviationDeclarationPtr()) {
-      // Normal DIE
-      if (AbbrDecl->hasChildren())
-        ++Depth;
-      else if (Depth == 0)
-        break; // This unit has a single DIE with no children.
-    } else {
-      // NULL DIE.
-      if (Depth > 0)
-        --Depth;
-      if (Depth == 0)
-        break;  // We are done with this compile unit!
+      if (AbbrDecl->hasChildren()) {
+        if (AppendCUDie || !IsCUDie) {
+          assert(Dies.size() > 0 && "Dies does not contain any die");
+          Parents.push_back(Dies.size() - 1);
+          PrevSiblings.push_back(0);
         }
+      } else if (IsCUDie)
+        // Stop if we have single compile unit die w/o children.
+        break;
+    } else {
+      // NULL DIE: finishes current children scope.
+      Parents.pop_back();
+      PrevSiblings.pop_back();
     }
+
+    if (IsCUDie)
+      IsCUDie = false;
+
+    // Stop when compile unit die is removed from the parents stack.
+  } while (Parents.size() > 1);
 }
 
 void DWARFUnit::extractDIEsIfNeeded(bool CUDieOnly) {
   if (Error e = tryExtractDIEsIfNeeded(CUDieOnly))
     Context.getRecoverableErrorHandler()(std::move(e));
 }
 
 Error DWARFUnit::tryExtractDIEsIfNeeded(bool CUDieOnly) {

 const DWARFUnitIndex &llvm::getDWARFUnitIndex(DWARFContext &Context,
                                               DWARFSectionKind Kind) {
   if (Kind == DW_SECT_INFO)
     return Context.getCUIndex();
   assert(Kind == DW_SECT_EXT_TYPES);
   return Context.getTUIndex();
 }
 
 DWARFDie DWARFUnit::getParent(const DWARFDebugInfoEntry *Die) {
   if (!Die)
     return DWARFDie();
-  const uint32_t Depth = Die->getDepth();
-  // Unit DIEs always have a depth of zero and never have parents.
-  if (Depth == 0)
-    return DWARFDie();
-  // Depth of 1 always means parent is the compile/type unit.
-  if (Depth == 1)
-    return getUnitDIE();
-  // Look for previous DIE with a depth that is one less than the Die's depth.
-  const uint32_t ParentDepth = Depth - 1;
-  for (uint32_t I = getDIEIndex(Die) - 1; I > 0; --I) {
-    if (DieArray[I].getDepth() == ParentDepth)
-      return DWARFDie(this, &DieArray[I]);
+
+  if (Optional<uint32_t> ParentIdx = Die->getParentIdx()) {
+    assert(*ParentIdx < DieArray.size() &&
+           "ParentIdx is out of DieArray boundaries");
+    return DWARFDie(this, &DieArray[*ParentIdx]);
   }
+
   return DWARFDie();
 }
 
 DWARFDie DWARFUnit::getSibling(const DWARFDebugInfoEntry *Die) {
   if (!Die)
     return DWARFDie();
-  uint32_t Depth = Die->getDepth();
-  // Unit DIEs always have a depth of zero and never have siblings.
-  if (Depth == 0)
-    return DWARFDie();
-  // NULL DIEs don't have siblings.
-  if (Die->getAbbreviationDeclarationPtr() == nullptr)
-    return DWARFDie();
 
-  // Find the next DIE whose depth is the same as the Die's depth.
-  for (size_t I = getDIEIndex(Die) + 1, EndIdx = DieArray.size(); I < EndIdx;
-       ++I) {
-    if (DieArray[I].getDepth() == Depth)
-      return DWARFDie(this, &DieArray[I]);
+  if (Optional<uint32_t> SiblingIdx = Die->getSiblingIdx()) {
+    assert(*SiblingIdx < DieArray.size() &&
+           "SiblingIdx is out of DieArray boundaries");
+    return DWARFDie(this, &DieArray[*SiblingIdx]);
   }
+
   return DWARFDie();
 }
 
 DWARFDie DWARFUnit::getPreviousSibling(const DWARFDebugInfoEntry *Die) {
   if (!Die)
     return DWARFDie();
-  uint32_t Depth = Die->getDepth();
-  // Unit DIEs always have a depth of zero and never have siblings.
-  if (Depth == 0)
+
+  Optional<uint32_t> ParentIdx = Die->getParentIdx();
+  if (!ParentIdx)
+    // Die is a root die, there is no previous sibling.
     return DWARFDie();
 
-  // Find the previous DIE whose depth is the same as the Die's depth.
-  for (size_t I = getDIEIndex(Die); I > 0;) {
-    --I;
-    if (DieArray[I].getDepth() == Depth - 1)
-      return DWARFDie();
-    if (DieArray[I].getDepth() == Depth)
-      return DWARFDie(this, &DieArray[I]);
+  assert(*ParentIdx < DieArray.size() &&
+         "ParentIdx is out of DieArray boundaries");
+  assert(getDIEIndex(Die) > 0 && "Die is a root die");
+
+  uint32_t PrevDieIdx = getDIEIndex(Die) - 1;
+  if (PrevDieIdx == *ParentIdx)
+    // Immediately previous node is parent, there is no previous sibling.
+
+  while (DieArray[PrevDieIdx].getParentIdx() != *ParentIdx) {
+    PrevDieIdx = *DieArray[PrevDieIdx].getParentIdx();
+
+    assert(PrevDieIdx < DieArray.size() &&
+           "PrevDieIdx is out of DieArray boundaries");
+    assert(PrevDieIdx >= *ParentIdx &&
+           "PrevDieIdx is not a child of parent of Die");
   }
-  return DWARFDie();
+
+  return DWARFDie(this, &DieArray[PrevDieIdx]);
 }
 
 DWARFDie DWARFUnit::getFirstChild(const DWARFDebugInfoEntry *Die) {
   if (!Die->hasChildren())
     return DWARFDie();
 
+  // TODO: Instead of checking here for invalid die we might reject
+  // invalid dies at parsing stage(DWARFUnit::extractDIEsToVector).
   // We do not want access out of bounds when parsing corrupted debug data.
   size_t I = getDIEIndex(Die) + 1;
   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?");
+  if (Optional<uint32_t> SiblingIdx = Die->getSiblingIdx()) {
+    assert(*SiblingIdx < DieArray.size() &&
+           "SiblingIdx is out of DieArray boundaries");
+    assert(DieArray[*SiblingIdx - 1].getTag() == dwarf::DW_TAG_null &&
+           "Bad end of children marker");
+    return DWARFDie(this, &DieArray[*SiblingIdx - 1]);
+  }
+
+  // If SiblingIdx is set for non-root dies we could be sure that DWARF is
+  // correct and "end of children marker" must be found. For root die we do not
+  // have such a guarantee(parsing root die might be stopped if "end of children
+  // marker" is missing, SiblingIdx is always zero for root die). That is why we
+  // do not use assertion for checking for "end of children marker" for root
+  // die.
+
+  // TODO: Instead of checking here for invalid die we might reject
+  // invalid dies at parsing stage(DWARFUnit::extractDIEsToVector).
+  if (getDIEIndex(Die) == 0 && DieArray.size() > 1 &&
+      DieArray.back().getTag() == dwarf::DW_TAG_null) {
+    // For the unit die we might take last item from DieArray.
+    assert(getDIEIndex(Die) == getDIEIndex(getUnitDIE()) && "Bad unit die");
+    return DWARFDie(this, &DieArray.back());
   }
+
   return DWARFDie();
 }
 
 const DWARFAbbreviationDeclarationSet *DWARFUnit::getAbbreviations() const {
   if (!Abbrevs)
     Abbrevs = Abbrev->getAbbreviationDeclarationSet(getAbbreviationsOffset());
   return Abbrevs;
 }
 
 llvm::Optional<object::SectionedAddress> DWARFUnit::getBaseAddress() {
   if (BaseAddr)
     return BaseAddr;
 
   DWARFDie UnitDie = getUnitDIE();

llvm/unittests/DebugInfo/DWARF/DWARFDieManualExtractTest.cpp

TEST(DWARFDie, manualExtractDump) {
 
   DWARFCompileUnit *CU = Ctx->getCompileUnitForOffset(0);
   ASSERT_NE(nullptr, CU);
   // Manually extracting DWARF DIE.
   uint64_t DIEOffset = CU->getOffset() + CU->getHeaderSize();
   uint64_t NextCUOffset = CU->getNextUnitOffset();
   DWARFDebugInfoEntry DieInfo;
   DWARFDataExtractor DebugInfoData = CU->getDebugInfoExtractor();
-  uint32_t Depth = 0;
-  ASSERT_TRUE(
-      DieInfo.extractFast(*CU, &DIEOffset, DebugInfoData, NextCUOffset, Depth));
+  ASSERT_TRUE(DieInfo.extractFast(*CU, &DIEOffset, DebugInfoData, NextCUOffset,
+                                  UINT32_MAX));
   DWARFDie Die(CU, &DieInfo);
   ASSERT_TRUE(Die.isValid());
   ASSERT_TRUE(Die.hasChildren());
   // Since we have extracted manually DieArray is empty.
   // Dump function should respect the default flags and print just current DIE,
   // and not explore children.
   SmallString<512> Output;
   raw_svector_ostream OS(Output);