Add the ability for DWARFDie objects to get the parent DWARFDie.

[clayborg]

Summary

In order for the llvm DWARF parser to be used in LLDB we will need to be able to get the parent of a DIE. This patch adds that functionality by changing the DWARFDebugInfoEntry class to store a depth field instead of a sibling index. Using a depth field allows us to easily calculate the sibling and the parent without increasing the size of DWARFDebugInfoEntry.

I tested llvm-dsymutil on a debug version of clang where this fully parses DWARF in over 1200 .o files to verify there was no serious regression in performance.

Added a full suite of unit tests to test this functionality.

[dblaikie]

lib/DebugInfo/DWARF/DWARFUnit.cpp

412–416 ↗

(On Diff #82127)

Could this accidentally walk into children of another DIE?

(eg: if this is the last child of a DIE - then the next DIE at the same level could be not a sibling, but a child of the following DIE?)

A
  A1
B
  B1

The next DIE at the same level as A1 is B1 (unless the 'null' at the end of A's child list qualifies as the next sibling? But then, if the null is a DIE, what about its next sibling?)

If I read the test case correctly, it's testing CU{int, subprogram{param(i), param(j)}} - so it doesn't test this case where there's a following child at the same level that isn't a sibling. So if it does work, might be good to have a test case for it.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

993–1004 ↗

(On Diff #82127)

I'd actually be inclined to make /less/ realistic DWARF, just to make it obvious that the semantics of DWARF aren't important here. We're just interested in tags and their children (probably don't have attributes at all - use the same tag for everything (perhaps some 'unknown' tag value, if possible)).

1072–1112 ↗

(On Diff #82127)

I don't think we need to test all these variations - the code seems pretty agnostic/independent of these features, such that the variations don't add a lot of value to the test coverage.

[clayborg]

I will update the test cases to not add attributes and not do all the variants. David: let me know if you agree with my assessment on the A1 sibling case.

lib/DebugInfo/DWARF/DWARFUnit.cpp

416 ↗

(On Diff #82127)

Actually it won't because your example actually looks like:

A
  A1
  NULL
B
  B1
  NULL
NULL

So the sibling of "A1" would be the first NULL and that NULL wouldn't return a sibling (see line 409).

I can modify the test case to test this though as a follow on patch I was going to do was to actually not store the NULL dies in the DieArray. The NULL dies take up a lot of memory, but if I remove them, then I will need to make sure the above function behaves correctly by watching for a depth to go lower than the current depth, so adding a test as you mentioned is a good idea.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1004 ↗

(On Diff #82127)

Yeah, I can remove them. I was thinking about that as I was making the test.

1112 ↗

(On Diff #82127)

Sounds good, I will just do a single variation for this then.

[clayborg]

Improved the tests to make sure we have coverage for:

CU
  A
    A1
    A2
  B
    B1
    B2

[clayborg]

Marked things as done.

[dblaikie]

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

985–999 ↗

(On Diff #82149)

Again, I'd probably skip tags (or is there something in the DWARF parser that has trouble dealing with a CU with no attributes?) & use the same tag repeatedly (preferably a clearly bogus tag - if we have a DW_TAG_unknown or something, that'd be ideal) to make it clear that the semantics of tag relationships aren't what's being tested here.

1015 ↗

(On Diff #82149)

The rest of this function appears to do too much testing - I doubt every relationship between every node in this tree pulls its weight in testing. Looks like they mostly test the same codepaths over and over again.

Could this be a bit more targeted? (test representative cases of interesting relationships - rather than every relationship)

[clayborg]

Simplify DWARF test for testing relations to not use real tags.

[dblaikie]

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

984–992 ↗

(On Diff #82166)

Is there a need for nodes in this tree to be identifiable by their tags? Could they just be identifiable by pointers or other handles? (eg: could the first test be something like... oh, right, this is roundtripping through DWARF bytes so it's not the same objects on both sides)

Does this test need to roundtrip through DWARF bytes? Could we build some DWARF data types and demonstrate that their parent/sibling walks work correctly after we build them, without having to use DWARF bytes at all? Or is the API not practical to represent in-memory directly without backing bytes?

More like that test at the end that creates DWARFDie and tests it directly, without going through any DWARF byte emission/parsing.

1053–1103 ↗

(On Diff #82166)

This testing still seems unnecessarily exhaustive - it'd be good to understand which things are being tested and why. Selectively testing interesting parts of the tree walk to ensure things work, without having lots of redundancy - this way tests are easier to maintain and clearer what they are and aren't testing.

1105–1110 ↗

(On Diff #82166)

This looks like it could/should be a separate test case/function - since it's not related to the rest of this function.

[clayborg]

I am not sure I would want to trim much more. Let me know if you see things I can trim. I could remove the "C2" die, but that is about it. Let me know if you see other stuff that can be trimmed.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

992 ↗

(On Diff #82166)

The blocks you build with (classes in llvm/CodeGen) are different from the blocks that are in the DWARF parser API (llvm/DebugInfo/DWARF) so it really isn't practical to try and just create DIE objects since that isn't what our parser is using. So the only way to currently use the API is to actually encode bytes so we can decode them and use the DWARF parsing API.

1103 ↗

(On Diff #82166)

I believe this is close to the bare bones as we can get it. We are testing two DIEs, B and C that have children and making sure all functions get the right children and siblings. I can cut out the whole C tree, but then that won't test asking B2 to get its sibling and making sure we don't return C1 as its sibling... What would you cut from this? I can cut the B2 and C2, bit would rather not, as I want two consecutive DIEs with no children as a test.

1110 ↗

(On Diff #82166)

I can remove it,

[clayborg]

Removed C2 from relations test to minimize the coverage to just what is needed and added an operator == to DWARFDie.

[clayborg]

Fixed:

• DWARFUnit::getDIEAtIndex() to assert and not bounds check index
• Don't use getDIEAtIndex() in DWARFUnit::getParent(DWARFDebugInfoEntry *) or DWARFUnit::getSibling(DWARFDebugInfoEntry *)
• Don't test "C" in the DWARF tests as we already covered the functionality when testing "B" and "C" is just there to ensure B keeps working.

[dblaikie]

Some remaining ways to simplify the test cases - perhaps Adrian can lend a hand in person. Otherwise I'm happy to go through it in more detail/write up some examples of what I have in mind.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1045–1048 ↗

(On Diff #82257)

Not sure if this is interesting to test - I assume we already have pretty good coverage on node tags.

1049–1052 ↗

(On Diff #82257)

& probably have pretty good coverage on the hasChildren flag too.

1054–1058 ↗

(On Diff #82257)

Unless these are interestingly different, I'd just test one.

1060 ↗

(On Diff #82257)

What's the purpose of A? To test a node without children? Perhaps you could use B1 for that instead? (& then probably rename B -> A and C -> B)

1067–1069 ↗

(On Diff #82257)

I'd probably skip these too - the tags are sort of interesting, but really it's about the structure we're creating. I don't think checking the tags really makes this test much more robust/provides substantially better coverage for the change being tested.

(which was what motivated my earlier/original suggestion to use some obvious (& pre-existing) tag for everything, to demonstrate that the tags aren't interesting to the test)

1071–1073 ↗

(On Diff #82257)

Test just one of these? "// Verify that a node without children has an invalid first child" or something like that.

1075–1077 ↗

(On Diff #82257)

I'd probably skip these - you already tested parental links on A.

1079–1084 ↗

(On Diff #82257)

Pull this out into a separate test function/case.

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

 class DWARFFormValue;
 struct DWARFDebugInfoEntryInlinedChain;
 
 /// DWARFDebugInfoEntry - A DIE with only the minimum required data.
 class DWARFDebugInfoEntry {
   /// Offset within the .debug_info of the start of this entry.
   uint32_t Offset;
 
-  /// How many to add to "this" to get the sibling.
-  uint32_t SiblingIdx;
+  /// 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;
 
   const DWARFAbbreviationDeclaration *AbbrevDecl;
 public:
   DWARFDebugInfoEntry()
-    : Offset(0), SiblingIdx(0), AbbrevDecl(nullptr) {}
+    : Offset(0), Depth(0), AbbrevDecl(nullptr) {}
 
   /// 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.
   bool extractFast(const DWARFUnit &U, uint32_t *OffsetPtr);
   /// High performance extraction should use this call.
   bool extractFast(const DWARFUnit &U, uint32_t *OffsetPtr,
-                   const DataExtractor &DebugInfoData, uint32_t UEndOffset);
+                   const DataExtractor &DebugInfoData,
+                   uint32_t UEndOffset,
+                   uint32_t Depth);
 
   uint32_t getOffset() const { return Offset; }
-  bool hasChildren() const { return AbbrevDecl && 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 DWARFDebugInfoEntry *getSibling() const {
-    return SiblingIdx > 0 ? this + SiblingIdx : 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 DWARFDebugInfoEntry *getFirstChild() const {
-    return hasChildren() ? this + 1 : nullptr;
+  uint32_t getDepth() const { return Depth; }
+  dwarf::Tag getTag() const {
+    return AbbrevDecl ? AbbrevDecl->getTag() : dwarf::DW_TAG_null;
   }
-
-  void setSibling(const DWARFDebugInfoEntry *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;
-  }
-
+  bool hasChildren() const { return AbbrevDecl && AbbrevDecl->hasChildren(); }
   const DWARFAbbreviationDeclaration *getAbbreviationDeclarationPtr() const {
     return AbbrevDecl;
   }
 };
 
 }
 
 #endif

llvm/trunk/include/llvm/DebugInfo/DWARF/DWARFDie.h

class DWARFDie {
   DWARFUnit *U;
   const DWARFDebugInfoEntry *Die;
 public:
   DWARFDie() : U(nullptr), Die(nullptr) {}
   DWARFDie(DWARFUnit *Unit, const DWARFDebugInfoEntry * D) : U(Unit), Die(D) {}
   
   bool isValid() const { return U && Die; }
   explicit operator bool() const { return isValid(); }
+  bool operator ==(const DWARFDie &RHS) const {
+    return Die == RHS.Die && U == RHS.U;
+  }
   const DWARFDebugInfoEntry *getDebugInfoEntry() const { return Die; }
   DWARFUnit *getDwarfUnit() const { return U; }
 
 
   /// Get the abbreviation declaration for this DIE.
   ///
   /// \returns the abbreviation declaration or NULL for null tags.
   const DWARFAbbreviationDeclaration *getAbbreviationDeclarationPtr() const {
bool isNULL() const {
     return getAbbreviationDeclarationPtr() == nullptr;
   }
   /// Returns true if DIE represents a subprogram (not inlined).
   bool isSubprogramDIE() const;
 
   /// Returns true if DIE represents a subprogram or an inlined subroutine.
   bool isSubroutineDIE() const;
 
+  /// Get the parent of this DIE object.
+  ///
+  /// \returns a valid DWARFDie instance if this object has a parent or an
+  /// invalid DWARFDie instance if it doesn't.
+  DWARFDie getParent() const;
   
-  /// Get the silbing of this DIE object.
+  /// Get the sibling of this DIE object.
   ///
   /// \returns a valid DWARFDie instance if this object has a sibling or an
   /// invalid DWARFDie instance if it doesn't.
-  DWARFDie getSibling() const {
-    assert(isValid() && "must check validity prior to calling");
-    return DWARFDie(U, Die->getSibling());
-  }
+  DWARFDie getSibling() const;
   
   /// Get the first child of this DIE object.
   ///
   /// \returns a valid DWARFDie instance if this object has children or an
   /// invalid DWARFDie instance if it doesn't.
   DWARFDie getFirstChild() const {
-    assert(isValid() && "must check validity prior to calling");
-    return DWARFDie(U, Die->getFirstChild());
+    if (isValid() && Die->hasChildren())
+      return DWARFDie(U, Die + 1);
+    return DWARFDie();
   }
   
   /// Dump the DIE and all of its attributes to the supplied stream.
   ///
   /// \param OS the stream to use for output.
   /// \param recurseDepth the depth to recurse to when dumping this DIE and its
   /// children.
   /// \param indent the number of characters to indent each line that is output.

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

class DWARFUnit {
   public:
     DWOHolder(StringRef DWOPath);
     DWARFUnit *getUnit() const { return DWOU; }
   };
   std::unique_ptr<DWOHolder> DWO;
 
   const DWARFUnitIndex::Entry *IndexEntry;
 
+  uint32_t getDIEIndex(const DWARFDebugInfoEntry *Die) {
+    auto First = DieArray.data();
+    assert(Die >= First && Die < First + DieArray.size());
+    return Die - First;
+  }
+
 protected:
   virtual bool extractImpl(DataExtractor debug_info, uint32_t *offset_ptr);
   /// Size in bytes of the unit header.
   virtual uint32_t getHeaderSize() const { return 11; }
 
 public:
   DWARFUnit(DWARFContext &Context, const DWARFSection &Section,
             const DWARFDebugAbbrev *DA, StringRef RS, StringRef SS,
public:
 
   /// \brief 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) {
-    auto DIE = D.getDebugInfoEntry();
-    assert(!DieArray.empty() && DIE >= &DieArray[0] &&
-           DIE < &DieArray[0] + DieArray.size());
-    return DIE - &DieArray[0];
+    return getDIEIndex(D.getDebugInfoEntry());
   }
 
   /// \brief Return the DIE object at the given index.
   DWARFDie getDIEAtIndex(unsigned Index) {
-    if (Index < DieArray.size())
-      return DWARFDie(this, &DieArray[Index]);
-    return DWARFDie();
+    assert(Index < DieArray.size());
   }
 
+  DWARFDie getParent(const DWARFDebugInfoEntry *Die);
+  DWARFDie getSibling(const DWARFDebugInfoEntry *Die);
+
   /// \brief Return the DIE object for a given offset inside the
   /// unit's DIE vector.
   ///
   /// The unit needs to have its DIEs extracted for this method to work.
   DWARFDie getDIEForOffset(uint32_t Offset) {
     extractDIEsIfNeeded(false);
     assert(!DieArray.empty());
     auto it = std::lower_bound(
private:
   size_t getDebugInfoSize() const { return Length + 4 - getHeaderSize(); }
 
   /// extractDIEsIfNeeded - Parses a compile unit and indexes its DIEs if it
   /// hasn't already been done. Returns the number of DIEs parsed at this call.
   size_t extractDIEsIfNeeded(bool CUDieOnly);
   /// extractDIEsToVector - Appends all parsed DIEs to a vector.
   void extractDIEsToVector(bool AppendCUDie, bool AppendNonCUDIEs,
                            std::vector<DWARFDebugInfoEntry> &DIEs) const;
-  /// setDIERelations - We read in all of the DIE entries into our flat list
-  /// of DIE entries and now we need to go back through all of them and set the
-  /// parent, sibling and child pointers for quick DIE navigation.
-  void setDIERelations();
   /// clearDIEs - Clear parsed DIEs to keep memory usage low.
   void clearDIEs(bool KeepCUDie);
 
   /// parseDWO - Parses .dwo file for current compile unit. Returns true if
   /// it was actually constructed.
   bool parseDWO();
 
   /// getSubprogramForAddress - Returns subprogram DIE with address range
   /// encompassing the provided address. The pointer is alive as long as parsed
   /// compile unit DIEs are not cleared.
   DWARFDie getSubprogramForAddress(uint64_t Address);
 };
 
 }
 
 #endif

llvm/trunk/lib/DebugInfo/DWARF/DWARFDebugInfoEntry.cpp

 using namespace llvm;
 using namespace dwarf;
 using namespace syntax;
 
 bool DWARFDebugInfoEntry::extractFast(const DWARFUnit &U,
                                              uint32_t *OffsetPtr) {
   DataExtractor DebugInfoData = U.getDebugInfoExtractor();
   const uint32_t UEndOffset = U.getNextUnitOffset();
-  return extractFast(U, OffsetPtr, DebugInfoData, UEndOffset);
+  return extractFast(U, OffsetPtr, DebugInfoData, UEndOffset, 0);
 }
-bool DWARFDebugInfoEntry::extractFast(const DWARFUnit &U,
-                                             uint32_t *OffsetPtr,
-                                             const DataExtractor &DebugInfoData,
-                                             uint32_t UEndOffset) {
+bool DWARFDebugInfoEntry::extractFast(const DWARFUnit &U, uint32_t *OffsetPtr,
+                                      uint32_t UEndOffset, uint32_t D) {
   Offset = *OffsetPtr;
+  Depth = D;
   if (Offset >= UEndOffset || !DebugInfoData.isValidOffset(Offset))
     return false;
   uint64_t AbbrCode = DebugInfoData.getULEB128(OffsetPtr);
   if (0 == AbbrCode) {
     // NULL debug tag entry.
     AbbrevDecl = nullptr;
     return true;
   }

llvm/trunk/lib/DebugInfo/DWARF/DWARFDie.cpp

while (Child) {
       Child = Child.getSibling();
     }
     DIE = Child;
   }
   // Reverse the obtained chain to make the root of inlined chain last.
   std::reverse(InlinedChain.begin(), InlinedChain.end());
 }
 
+DWARFDie DWARFDie::getParent() const {
+  if (isValid())
+    return U->getParent(Die);
+  return DWARFDie();
+}
+
+DWARFDie DWARFDie::getSibling() const {
+  if (isValid())
+    return U->getSibling(Die);
+  return DWARFDie();
+}

llvm/trunk/lib/DebugInfo/DWARF/DWARFUnit.cpp

 const char *DWARFUnit::getCompilationDir() {
   return getUnitDIE().getAttributeValueAsString(DW_AT_comp_dir, nullptr);
 }
 
 Optional<uint64_t> DWARFUnit::getDWOId() {
   return getUnitDIE().getAttributeValueAsUnsignedConstant(DW_AT_GNU_dwo_id);
 }
 
-void DWARFUnit::setDIERelations() {
-  if (DieArray.size() <= 1)
-    return;
-
-  std::vector<DWARFDebugInfoEntry *> ParentChain;
-  DWARFDebugInfoEntry *SiblingChain = nullptr;
-  for (auto &DIE : DieArray) {
-    if (SiblingChain) {
-      SiblingChain->setSibling(&DIE);
-    }
-    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());
-}
-
 void DWARFUnit::extractDIEsToVector(
     bool AppendCUDie, bool AppendNonCUDies,
     std::vector<DWARFDebugInfoEntry> &Dies) const {
   if (!AppendCUDie && !AppendNonCUDies)
     return;
 
   // Set the offset to that of the first DIE and calculate the start of the
   // next compilation unit header.
   uint32_t DIEOffset = Offset + getHeaderSize();
   uint32_t NextCUOffset = getNextUnitOffset();
   DWARFDebugInfoEntry DIE;
   DataExtractor DebugInfoData = getDebugInfoExtractor();
   uint32_t Depth = 0;
   bool IsCUDie = true;
 
-  while (DIE.extractFast(*this, &DIEOffset, DebugInfoData, NextCUOffset)) {
+  while (DIE.extractFast(*this, &DIEOffset, DebugInfoData, NextCUOffset,
+                         Depth)) {
     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.
if (!HasCUDie) {
     AddrOffsetSectionBase = UnitDie.getAttributeValueAsSectionOffset(
         DW_AT_GNU_addr_base, 0);
     RangeSectionBase = UnitDie.getAttributeValueAsSectionOffset(
         DW_AT_rnglists_base, 0);
     // Don't fall back to DW_AT_GNU_ranges_base: it should be ignored for
     // skeleton CU DIE, so that DWARF users not aware of it are not broken.
   }
 
-  setDIERelations();
   return DieArray.size();
 }
 
 DWARFUnit::DWOHolder::DWOHolder(StringRef DWOPath)
     : DWOU(nullptr) {
   auto Obj = object::ObjectFile::createObjectFile(DWOPath);
   if (!Obj) {
     // TODO: Actually report errors helpfully.

 const DWARFUnitIndex &getDWARFUnitIndex(DWARFContext &Context,
                                         DWARFSectionKind Kind) {
   if (Kind == DW_SECT_INFO)
     return Context.getCUIndex();
   assert(Kind == DW_SECT_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]);
+  }
+  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]);
+  }
+  return DWARFDie();
+}
+
 } // end namespace llvm

llvm/trunk/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

 
 TEST(DWARFDebugInfo, TestDWARF32Version4Addr8Addresses) {
   // Test that we can decode address values in DWARF32, version 4, with 8 byte
   // addresses.
   typedef uint64_t AddrType;
   TestAddresses<4, AddrType>();
 }
 
+TEST(DWARFDebugInfo, TestRelations) {
+  // Test the DWARF APIs related to accessing the DW_AT_low_pc and
+  // DW_AT_high_pc.
+  uint16_t Version = 4;
+  
+  const uint8_t AddrSize = sizeof(void *);
+  initLLVMIfNeeded();
+  Triple Triple = getHostTripleForAddrSize(AddrSize);
+  auto ExpectedDG = dwarfgen::Generator::create(Triple, Version);
+  if (HandleExpectedError(ExpectedDG))
+    return;
+  dwarfgen::Generator *DG = ExpectedDG.get().get();
+  dwarfgen::CompileUnit &CU = DG->addCompileUnit();
+  
+  enum class Tag: uint16_t  {
+    A = dwarf::DW_TAG_lo_user,
+    B,
+    B1,
+    B2,
+    C,
+    C1
+  };
+
+  // Scope to allow us to re-use the same DIE names
+  {
+    // Create DWARF tree that looks like:
+    //
+    // CU
+    //   A
+    //   B
+    //     B1
+    //     B2
+    //   C
+    //     C1
+    dwarfgen::DIE CUDie = CU.getUnitDIE();
+    CUDie.addChild((dwarf::Tag)Tag::A);
+    dwarfgen::DIE B = CUDie.addChild((dwarf::Tag)Tag::B);
+    dwarfgen::DIE C = CUDie.addChild((dwarf::Tag)Tag::C);
+    B.addChild((dwarf::Tag)Tag::B1);
+    B.addChild((dwarf::Tag)Tag::B2);
+    C.addChild((dwarf::Tag)Tag::C1);
+  }
+
+  MemoryBufferRef FileBuffer(DG->generate(), "dwarf");
+  auto Obj = object::ObjectFile::createObjectFile(FileBuffer);
+  EXPECT_TRUE((bool)Obj);
+  DWARFContextInMemory DwarfContext(*Obj.get());
+  
+  // Verify the number of compile units is correct.
+  uint32_t NumCUs = DwarfContext.getNumCompileUnits();
+  EXPECT_EQ(NumCUs, 1u);
+  DWARFCompileUnit *U = DwarfContext.getCompileUnitAtIndex(0);
+  
+  // Get the compile unit DIE is valid.
+  auto CUDie = U->getUnitDIE(false);
+  EXPECT_TRUE(CUDie.isValid());
+  // DieDG.dump(llvm::outs(), U, UINT32_MAX);
+  
+  // The compile unit doesn't have a parent or a sibling.
+  auto ParentDie = CUDie.getParent();
+  EXPECT_FALSE(ParentDie.isValid());
+  auto SiblingDie = CUDie.getSibling();
+  EXPECT_FALSE(SiblingDie.isValid());
+  
+  // Get the children of the compile unit
+  auto A = CUDie.getFirstChild();
+  auto B = A.getSibling();
+  auto C = B.getSibling();
+  auto Null = C.getSibling();
+  
+  // Verify NULL Die is NULL and has no children or siblings
+  EXPECT_TRUE(Null.isNULL());
+  EXPECT_FALSE(Null.getSibling().isValid());
+  EXPECT_FALSE(Null.getFirstChild().isValid());
+  
+  // Verify all children of the compile unit DIE are correct.
+  EXPECT_EQ(A.getTag(), (dwarf::Tag)Tag::A);
+  EXPECT_EQ(B.getTag(), (dwarf::Tag)Tag::B);
+  EXPECT_EQ(C.getTag(), (dwarf::Tag)Tag::C);
+
+  // Verify who has children
+  EXPECT_FALSE(A.hasChildren());
+  EXPECT_TRUE(B.hasChildren());
+
+  // Make sure the parent of all the children of the compile unit are the
+  // compile unit.
+  EXPECT_EQ(A.getParent(), CUDie);
+  EXPECT_EQ(B.getParent(), CUDie);
+  EXPECT_EQ(Null.getParent(), CUDie);
+
+  EXPECT_FALSE(A.getFirstChild().isValid());
+
+  // Verify the children of the B DIE
+  auto B1 = B.getFirstChild();
+  auto B2 = B1.getSibling();
+  EXPECT_TRUE(B2.getSibling().isNULL());
+  
+  // Verify all children of the B DIE correctly valid or invalid.
+  EXPECT_EQ(B1.getTag(), (dwarf::Tag)Tag::B1);
+  EXPECT_EQ(B2.getTag(), (dwarf::Tag)Tag::B2);
+
+  // Make sure the parent of all the children of the B are the B.
+  EXPECT_EQ(B1.getParent(), B);
+  EXPECT_EQ(B2.getParent(), B);
+}
+
+TEST(DWARFDebugInfo, TestDWARFDie) {
+
+  // Make sure a default constructed DWARFDie doesn't have any parent, sibling
+  // or child;
+  DWARFDie DefaultDie;
+  EXPECT_FALSE(DefaultDie.getParent().isValid());
+  EXPECT_FALSE(DefaultDie.getFirstChild().isValid());
+  EXPECT_FALSE(DefaultDie.getSibling().isValid());
+}
+
 
 } // end anonymous namespace