This is an archive of the discontinued LLVM Phabricator instance.

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

Authored by avl on Sep 23 2021, 2:00 PM.

Details

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).

Diff Detail

Event Timeline

avl created this revision.Sep 23 2021, 2:00 PM
avl requested review of this revision.Sep 23 2021, 2:00 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 23 2021, 2:00 PM

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

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–797

Ditto

799

This function could be done down in DWARFDebugInfoEntry now.

828

This function could be done down in DWARFDebugInfoEntry now.

839

This function could be done down in DWARFDebugInfoEntry now.

851–872

This code should no longer be needed right?

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 added a comment.Sep 28 2021, 4:10 AM

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
839

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 added a comment.Sep 28 2021, 5:55 AM

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?

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.

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.

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.

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 added a comment.Sep 28 2021, 12:23 PM
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).

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 added a comment.Sep 28 2021, 1:39 PM

(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"

(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.

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

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp
786–788

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

799

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.

859–871

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 added inline comments.Sep 29 2021, 2:44 AM
llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp
786–788

Ok.

799

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.

859–871

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 updated this revision to Diff 375890.Sep 29 2021, 7:49 AM

addressed comments.

clayborg accepted this revision.Sep 29 2021, 10:11 AM

LGTM. David you ok with everything?

This revision is now accepted and ready to land.Sep 29 2021, 10:11 AM
dblaikie added inline comments.Sep 30 2021, 8:45 PM
llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp
807–823

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]);
854

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 added inline comments.Oct 1 2021, 2:40 AM
llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp
807–823

Yeah. Good idea. Will do.

854

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 updated this revision to Diff 376578.Oct 1 2021, 11:06 AM

addressed comments(rewrote getPreviousSibling())

avl added inline comments.Oct 1 2021, 11:14 AM
llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp
807–823

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 added inline comments.Oct 1 2021, 11:21 AM
llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp
854

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 added inline comments.Oct 1 2021, 11:33 AM
llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp
854
// 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 added inline comments.Oct 1 2021, 11:37 AM
llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp
807–823

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 updated this revision to Diff 376611.Oct 1 2021, 12:54 PM

addressed comments(implemented getPreviousSibling as requested)

dblaikie accepted this revision.Oct 1 2021, 1:04 PM

Looks alright, thanks!