[Debuginfo][DWARF][NFC] Add paired methods working with DWARFDebugInfoEntry.

[avl]

Summary

This review is extracted from D96035.

DWARF Debuginfo classes have two representations for DIEs: DWARFDebugInfoEntry
(short) and DWARFDie(extended). Depending on the task, it might be more convenient
to use DWARFDebugInfoEntry or/and DWARFDie. DWARFUnit class already has methods
working with DWARFDie and DWARFDebugInfoEntry. This patch adds more
methods working with DWARFDebugInfoEntry to have paired functionality.

[clayborg]

I would actually request that no one can play with DWARFDebugInfoEntry items at all except for the DWARFDie class. The main issue is you can ask the wrong DWARFUnit class to do something with a DWARFDebugInfoEntry object that it doesn't own. We ran into this problem in LLDB and this is why we created the DWARFDie class in LLDB. If you encapsulate everything into the DWARFDie class and control all entry points, then this mistake can not be made since everyone needs to use the DWARFDie class. If you do want it add it, I would suggest adding an assert that verifies that the DWARFDebugInfoEntry belongs to the current DWARFUnit in each new function that takes a "DWARFDebugInfoEntry *", but I would still rather see everyone use DWARFDie if possible for safety reason and to avoid having an assert in each call.

[avl]

In D126059#3528520, @clayborg wrote:

I would actually request that no one can play with DWARFDebugInfoEntry items at all except for the DWARFDie class. The main issue is you can ask the wrong DWARFUnit class to do something with a DWARFDebugInfoEntry object that it doesn't own. We ran into this problem in LLDB and this is why we created the DWARFDie class in LLDB. If you encapsulate everything into the DWARFDie class and control all entry points, then this mistake can not be made since everyone needs to use the DWARFDie class. If you do want it add it, I would suggest adding an assert that verifies that the DWARFDebugInfoEntry belongs to the current DWARFUnit in each new function that takes a "DWARFDebugInfoEntry *", but I would still rather see everyone use DWARFDie if possible for safety reason and to avoid having an assert in each call.

The reason to use DWARFDebugInfoEntry is the performance concern.
The non optimized DWARF for clang binary has more than 160 million dies:

llvm-dwarfdump --debug-info clang | grep -c DW_TAG 
162452994

There are a many methods which create dies, f.e.:

DWARFDie getDIEAtIndex(unsigned Index) {
  return DWARFDie(this, getDebugInfoEntry(Index));
}

DWARFDie getDIEForOffset(uint64_t Offset) {
  if (Optional<uint32_t> DieIdx = getDIEIndexForOffset(Offset))
    return DWARFDie(this, &DieArray[*DieIdx]);

  return DWARFDie();
}

...

these methods are called for each die more than once, this causes the DWARFDie class constructor to be called a very large number of times.
While using DWARFDebugInfoEntry is cheap. They are allocated once at DieArray and later are passed as the pointers(No need to call constructor).

Other than that, passing DWARFDie by value leads to copying more data - 16 bytes instead of 8 bytes for DWARFDebugInfoEntry*.

All above lead to noticable performance impact.

If we can agree on using asserts to check that the proper unit is used(as you suggested) then I propose to use that approach.
Will update this review to use assertions checking DWARFUnit.

[dblaikie]

You mention performance concerns - even in an optimized build? What sort of performance data do you have? Would be good to have that documented here in the review/in the commit message to justify the use of these more error-prone APIs.

[avl]

In D126059#3529762, @dblaikie wrote:

You mention performance concerns - even in an optimized build?

yes, the performance improvement could be achieved even in an optimized build.

What sort of performance data do you have?

When I replaced ~50% usages of DWARFDie with DWARFDebugInfoEntry for D96035 I got 1-2% improvement.

[clayborg]

A 1 to 2 percent improvement is probably going to go away if the asserts are enabled when it has to do the check each time. If would still hesitate to add this kind of API as it will encourage others to use the APIs. I would be ok with it if the methods are protected or private and if we can add the DWARFLinker as a friend class to allow access to these performant but dangerous APIs only in certain situations that really require it. I really want to avoid most people from being able to use these APIs if possible to make sure we don't end up with bugs. We had many many bugs that stemmed from mismatching DWARFUnit + DWARFDebugIntoEntry before the DWARFDie class was created, mostly when doing cross CU references or in Fission cases where you have the skeleton CU vs the actual DWO CU + a DWARFDebugInfoEntry that comes from the actual DWO file. So there is a real danger to the safety and correctness of the code here.

[avl]

In D126059#3532264, @clayborg wrote:

A 1 to 2 percent improvement is probably going to go away if the asserts are enabled when it has to do the check each time. If would still hesitate to add this kind of API as it will encourage others to use the APIs. I would be ok with it if the methods are protected or private and if we can add the DWARFLinker as a friend class to allow access to these performant but dangerous APIs only in certain situations that really require it. I really want to avoid most people from being able to use these APIs if possible to make sure we don't end up with bugs. We had many many bugs that stemmed from mismatching DWARFUnit + DWARFDebugIntoEntry before the DWARFDie class was created, mostly when doing cross CU references or in Fission cases where you have the skeleton CU vs the actual DWO CU + a DWARFDebugInfoEntry that comes from the actual DWO file. So there is a real danger to the safety and correctness of the code here.

if all of these bugs could be caught by assertions then the problem probably does not look too severe?
Running debug version of the application will show the problems.

Anyway, if we do not want these methods to be used by others - I am OK to make these methods protected and make DWARFLinker the only one using them.

[clayborg]

In D126059#3532473, @avl wrote:

In D126059#3532264, @clayborg wrote:

A 1 to 2 percent improvement is probably going to go away if the asserts are enabled when it has to do the check each time. If would still hesitate to add this kind of API as it will encourage others to use the APIs. I would be ok with it if the methods are protected or private and if we can add the DWARFLinker as a friend class to allow access to these performant but dangerous APIs only in certain situations that really require it. I really want to avoid most people from being able to use these APIs if possible to make sure we don't end up with bugs. We had many many bugs that stemmed from mismatching DWARFUnit + DWARFDebugIntoEntry before the DWARFDie class was created, mostly when doing cross CU references or in Fission cases where you have the skeleton CU vs the actual DWO CU + a DWARFDebugInfoEntry that comes from the actual DWO file. So there is a real danger to the safety and correctness of the code here.

if all of these bugs could be caught by assertions then the problem probably does not look too severe?
Running debug version of the application will show the problems.

Anyway, if we do not want these methods to be used by others - I am OK to make these methods protected and make DWARFLinker the only one using them.

I personally would be fine if there were guardrails on this feature where we make them protected, though I am not a code owner the DWARF parser in LLVM, so some input from the LLVM DWARF community would be good to verify they agree with this direction.

[dblaikie]

In D126059#3532264, @clayborg wrote:

A 1 to 2 percent improvement is probably going to go away if the asserts are enabled when it has to do the check each time.

Though the asserts would only be done in +Asserts builds - still providing the performance in release/non-asserts builds.

If would still hesitate to add this kind of API as it will encourage others to use the APIs. I would be ok with it if the methods are protected or private and if we can add the DWARFLinker as a friend class to allow access to these performant but dangerous APIs only in certain situations that really require it. I really want to avoid most people from being able to use these APIs if possible to make sure we don't end up with bugs. We had many many bugs that stemmed from mismatching DWARFUnit + DWARFDebugIntoEntry before the DWARFDie class was created, mostly when doing cross CU references or in Fission cases where you have the skeleton CU vs the actual DWO CU + a DWARFDebugInfoEntry that comes from the actual DWO file. So there is a real danger to the safety and correctness of the code here.

Fair enough. I don't feel super strongly about it/sounds OK to me.

[avl]

addressed comments: make methods working with DWARFDebugInfoEntry to be protected.

[clayborg]

Looks good to me, but someone that owns the DWARF parser in LLVM should give the final ok.

[avl]

rebased.

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

class DWARFUnit {
   /// std::map::upper_bound for address range lookup.
   std::map<uint64_t, std::pair<uint64_t, DWARFDie>> AddrDieMap;
 
   using die_iterator_range =
       iterator_range<std::vector<DWARFDebugInfoEntry>::iterator>;
 
   std::shared_ptr<DWARFUnit> DWO;
 
-  uint32_t getDIEIndex(const DWARFDebugInfoEntry *Die) {
-    auto First = DieArray.data();
-    assert(Die >= First && Die < First + DieArray.size());
-    return Die - First;
-  }
-
 protected:
   const DWARFUnitHeader &getHeader() const { return Header; }
 
   /// Find the unit's contribution to the string offsets table and determine its
   /// length and form. The given offset is expected to be derived from the unit
   /// DIE's DW_AT_str_offsets_base attribute.
   Expected<Optional<StrOffsetsContributionDescriptor>>
   determineStringOffsetsTableContribution(DWARFDataExtractor &DA);
public:
 
   /// Returns the number of DIEs in the unit. Parses the unit
   /// if necessary.
   unsigned getNumDIEs() {
     extractDIEsIfNeeded(false);
     return DieArray.size();
   }
 
+  /// Return the index of a \p Die entry inside the unit's DIE vector.
+  ///
+  /// It is illegal to call this method with a DIE that hasn't be
+  /// created by this unit. In other word, it's illegal to call this
+  /// method on a DIE that isn't accessible by following
+  /// children/sibling links starting from this unit's getUnitDIE().
+  uint32_t getDIEIndex(const DWARFDebugInfoEntry *Die) const {
+    auto First = DieArray.data();
+    assert(Die >= First && Die < First + DieArray.size());
+    return Die - First;
+  }
+
   /// Return the index of a DIE inside the unit's DIE vector.
   ///
   /// It is illegal to call this method with a DIE that hasn't be
   /// created by this unit. In other word, it's illegal to call this
   /// method on a DIE that isn't accessible by following
   /// children/sibling links starting from this unit's getUnitDIE().
-  uint32_t getDIEIndex(const DWARFDie &D) {
+  uint32_t getDIEIndex(const DWARFDie &D) const {
     return getDIEIndex(D.getDebugInfoEntry());
   }
 
-  /// Return the DIE object at the given index.
+  /// Return the DIE object at the given index \p Index.
   DWARFDie getDIEAtIndex(unsigned Index) {
+    return DWARFDie(this, getDebugInfoEntry(Index));
+  }
+
+  /// Return DWARFDebugInfoEntry for the specified index \p Index.
+  const DWARFDebugInfoEntry *getDebugInfoEntry(unsigned Index) const {
     assert(Index < DieArray.size());
-    return DWARFDie(this, &DieArray[Index]);
+    return &DieArray[Index];
   }
 
   DWARFDie getParent(const DWARFDebugInfoEntry *Die);
   DWARFDie getSibling(const DWARFDebugInfoEntry *Die);
   DWARFDie getPreviousSibling(const DWARFDebugInfoEntry *Die);
   DWARFDie getFirstChild(const DWARFDebugInfoEntry *Die);
   DWARFDie getLastChild(const DWARFDebugInfoEntry *Die);
 
-  /// Return the DIE object for a given offset inside the
+  const DWARFDebugInfoEntry *
+  getParentEntry(const DWARFDebugInfoEntry *Die) const;
+  const DWARFDebugInfoEntry *
+  getSiblingEntry(const DWARFDebugInfoEntry *Die) const;
+  const DWARFDebugInfoEntry *
+  getPreviousSiblingEntry(const DWARFDebugInfoEntry *Die) const;
+  const DWARFDebugInfoEntry *
+  getFirstChildEntry(const DWARFDebugInfoEntry *Die) const;
+  const DWARFDebugInfoEntry *
+  getLastChildEntry(const DWARFDebugInfoEntry *Die) const;
+
+  /// Return the DIE object for a given offset \p Offset inside the
   /// unit's DIE vector.
-  ///
-  /// The unit needs to have its DIEs extracted for this method to work.
   DWARFDie getDIEForOffset(uint64_t Offset) {
+    if (Optional<uint32_t> DieIdx = getDIEIndexForOffset(Offset))
+      return DWARFDie(this, &DieArray[*DieIdx]);
+
+    return DWARFDie();
+  }
+
+  /// Return the DIE index for a given offset \p Offset inside the
+  /// unit's DIE vector.
+  Optional<uint32_t> getDIEIndexForOffset(uint64_t Offset) {
     extractDIEsIfNeeded(false);
     auto It =
         llvm::partition_point(DieArray, [=](const DWARFDebugInfoEntry &DIE) {
           return DIE.getOffset() < Offset;
         });
     if (It != DieArray.end() && It->getOffset() == Offset)
-      return DWARFDie(this, &*It);
-    return DWARFDie();
+      return It - DieArray.begin();
+    return None;
   }
 
   uint32_t getLineTableOffset() const {
     if (auto IndexEntry = Header.getIndexEntry())
       if (const auto *Contrib = IndexEntry->getContribution(DW_SECT_LINE))
         return Contrib->Offset;
     return 0;
   }

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

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();
+  if (const DWARFDebugInfoEntry *Entry = getParentEntry(Die))
+    return DWARFDie(this, Entry);
+
+}
+
+const DWARFDebugInfoEntry *
+DWARFUnit::getParentEntry(const DWARFDebugInfoEntry *Die) const {
+  if (!Die)
+    return nullptr;
 
   if (Optional<uint32_t> ParentIdx = Die->getParentIdx()) {
     assert(*ParentIdx < DieArray.size() &&
            "ParentIdx is out of DieArray boundaries");
-    return DWARFDie(this, &DieArray[*ParentIdx]);
+    return getDebugInfoEntry(*ParentIdx);
   }
 
-  return DWARFDie();
+  return nullptr;
 }
 
 DWARFDie DWARFUnit::getSibling(const DWARFDebugInfoEntry *Die) {
-  if (!Die)
-    return DWARFDie();
+  if (const DWARFDebugInfoEntry *Sibling = getSiblingEntry(Die))
+    return DWARFDie(this, Sibling);
+
+}
+
+const DWARFDebugInfoEntry *
+DWARFUnit::getSiblingEntry(const DWARFDebugInfoEntry *Die) const {
+  if (!Die)
+    return nullptr;
 
   if (Optional<uint32_t> SiblingIdx = Die->getSiblingIdx()) {
     assert(*SiblingIdx < DieArray.size() &&
            "SiblingIdx is out of DieArray boundaries");
-    return DWARFDie(this, &DieArray[*SiblingIdx]);
+    return &DieArray[*SiblingIdx];
   }
 
-  return DWARFDie();
+  return nullptr;
 }
 
 DWARFDie DWARFUnit::getPreviousSibling(const DWARFDebugInfoEntry *Die) {
-  if (!Die)
-    return DWARFDie();
+  if (const DWARFDebugInfoEntry *Sibling = getPreviousSiblingEntry(Die))
+    return DWARFDie(this, Sibling);
+
+}
+
+const DWARFDebugInfoEntry *
+DWARFUnit::getPreviousSiblingEntry(const DWARFDebugInfoEntry *Die) const {
+  if (!Die)
+    return nullptr;
 
   Optional<uint32_t> ParentIdx = Die->getParentIdx();
   if (!ParentIdx)
     // Die is a root die, there is no previous sibling.
-    return DWARFDie();
+    return nullptr;
 
   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.
-    return DWARFDie();
+    return nullptr;
 
   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(this, &DieArray[PrevDieIdx]);
+  return &DieArray[PrevDieIdx];
 }
 
 DWARFDie DWARFUnit::getFirstChild(const DWARFDebugInfoEntry *Die) {
-  if (!Die->hasChildren())
-    return DWARFDie();
+  if (const DWARFDebugInfoEntry *Child = getFirstChildEntry(Die))
+    return DWARFDie(this, Child);
+
+}
+
+const DWARFDebugInfoEntry *
+DWARFUnit::getFirstChildEntry(const DWARFDebugInfoEntry *Die) const {
+  if (!Die->hasChildren())
+    return nullptr;
 
   // 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]);
+    return nullptr;
+  return &DieArray[I];
 }
 
 DWARFDie DWARFUnit::getLastChild(const DWARFDebugInfoEntry *Die) {
-  if (!Die->hasChildren())
-    return DWARFDie();
+  if (const DWARFDebugInfoEntry *Child = getLastChildEntry(Die))
+    return DWARFDie(this, Child);
+
+}
+
+const DWARFDebugInfoEntry *
+DWARFUnit::getLastChildEntry(const DWARFDebugInfoEntry *Die) const {
+  if (!Die->hasChildren())
+    return nullptr;
 
   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]);
+    return &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());
+    assert(getDIEIndex(Die) ==
+               getDIEIndex(const_cast<DWARFUnit *>(this)->getUnitDIE()) &&
+           "Bad unit die");
+    return &DieArray.back();
   }
 
-  return DWARFDie();
+  return nullptr;
 }
 
 const DWARFAbbreviationDeclarationSet *DWARFUnit::getAbbreviations() const {
   if (!Abbrevs)
     Abbrevs = Abbrev->getAbbreviationDeclarationSet(getAbbreviationsOffset());
   return Abbrevs;
 }