[DebugInfo] Add a getParent method to DWARFDebugInformationEntryMinimal.

[friss]

Summary

The DIE representation of libDebugInfo is designed to be minimal
(as the class name implies). The information that's there allows
to walk the DIE tree down, but you can't get back to the root
from an arbitrary node.

This patch adds this ability with the goal of using it in
llvm-dsymutil. I could also use this information in dwarfdump
itself to easily support dumping the full DIE hierarchy of a
selected DIE when I finally implement a search option.

The added information definitely has a cost: the size of
the structure is increased by 8 bytes on 64 bits archs
due to padding and this combined to the added logic makes
the raw parsing between 5 and 10% slower.

Just for llvm-dsymutil, this is optional. I can gather the
parent chains in a separate path and store them, but I think
that the performance/aded functionality benefit is worth
it. WDYT?

include/llvm/DebugInfo/DWARFDebugInfoEntry.h

 class DWARFFormValue;
 struct DWARFDebugInfoEntryInlinedChain;
 
 /// DWARFDebugInfoEntryMinimal - A DIE with only the minimum required data.
 class DWARFDebugInfoEntryMinimal {
   /// Offset within the .debug_info of the start of this entry.
   uint32_t Offset;
 
+  /// How many to substract to "this" to get the parent.
+  uint32_t ParentIdx;
+
   /// How many to add to "this" to get the sibling.
   uint32_t SiblingIdx;
 
   const DWARFAbbreviationDeclaration *AbbrevDecl;
 public:
   DWARFDebugInfoEntryMinimal()
-    : Offset(0), SiblingIdx(0), AbbrevDecl(nullptr) {}
+    : Offset(0), ParentIdx(0), SiblingIdx(0), AbbrevDecl(nullptr) {}
 
   void dump(raw_ostream &OS, DWARFUnit *u, unsigned recurseDepth,
             unsigned indent = 0) const;
   void dumpAttribute(raw_ostream &OS, DWARFUnit *u, uint32_t *offset_ptr,
                      uint16_t attr, uint16_t form, unsigned indent = 0) const;
 
   /// 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
public:
   bool hasChildren() const { return !isNULL() && AbbrevDecl->hasChildren(); }
 
   // We know we are kept in a vector of contiguous entries, so we know
   // our sibling will be some index after "this".
   const DWARFDebugInfoEntryMinimal *getSibling() const {
     return SiblingIdx > 0 ? this + SiblingIdx : nullptr;
   }
 
+  // Returns the parent DIE or null if this is the root DIE.
+  const DWARFDebugInfoEntryMinimal *getParent() const {
+    return ParentIdx ? this - ParentIdx : nullptr;
+  }
+
   // We know we are kept in a vector of contiguous entries, so we know
   // we don't need to store our child pointer, if we have a child it will
   // be the next entry in the list...
   const DWARFDebugInfoEntryMinimal *getFirstChild() const {
     return hasChildren() ? this + 1 : nullptr;
   }
 
   void setSibling(const DWARFDebugInfoEntryMinimal *Sibling) {
     if (Sibling) {
       // We know we are kept in a vector of contiguous entries, so we know
       // our sibling will be some index after "this".
       SiblingIdx = Sibling - this;
     } else
       SiblingIdx = 0;
   }
 
+  void setParent(const DWARFDebugInfoEntryMinimal *Parent) {
+    if (Parent) {
+      // We know we are kept in a vector of contiguous entries, so we know
+      // our parent will be soewhere before "this".
+      ParentIdx = this - Parent;
+    } else
+      ParentIdx = 0;
+  }
+
   const DWARFAbbreviationDeclaration *getAbbreviationDeclarationPtr() const {
     return AbbrevDecl;
   }
 
   bool getAttributeValue(const DWARFUnit *U, const uint16_t Attr,
                          DWARFFormValue &FormValue) const;
 
   const char *getAttributeValueAsString(const DWARFUnit *U, const uint16_t Attr,

lib/DebugInfo/DWARFUnit.cpp

uint64_t DWARFUnit::getDWOId() {
   return DieArray[0]
       .getAttributeValueAsUnsignedConstant(this, DW_AT_GNU_dwo_id, FailValue);
 }
 
 void DWARFUnit::setDIERelations() {
   if (DieArray.size() <= 1)
     return;
 
-  std::vector<DWARFDebugInfoEntryMinimal *> ParentChain;
+  // Make sure the vector is never empty so that we don't have to
+  // check for emptyness inside the loop bellow.
+  std::vector<DWARFDebugInfoEntryMinimal *> ParentChain(1,&DieArray[0]);
   DWARFDebugInfoEntryMinimal *SiblingChain = nullptr;
   for (auto &DIE : DieArray) {
     if (SiblingChain) {
       SiblingChain->setSibling(&DIE);
     }
+    // Note that this will call setParent with itself on the root
+    // node. This will result in a null offset which is handled as 'no
+    // parent'.
+    DIE.setParent(ParentChain.back());
     if (const DWARFAbbreviationDeclaration *AbbrDecl =
             DIE.getAbbreviationDeclarationPtr()) {
       // Normal DIE.
       if (AbbrDecl->hasChildren()) {
         ParentChain.push_back(&DIE);
         SiblingChain = nullptr;
       } else {
         SiblingChain = &DIE;
       }
     } else {
       // NULL entry terminates the sibling chain.
       SiblingChain = ParentChain.back();
       ParentChain.pop_back();
     }
   }
   assert(SiblingChain == nullptr || SiblingChain == &DieArray[0]);
-  assert(ParentChain.empty());
+  assert(ParentChain.size() == 1 && ParentChain[0] == &DieArray[0]);
 }
 
 void DWARFUnit::extractDIEsToVector(
     bool AppendCUDie, bool AppendNonCUDies,
     std::vector<DWARFDebugInfoEntryMinimal> &Dies) const {
   if (!AppendCUDie && !AppendNonCUDies)
     return;