Don't store the NULL DIEs in the DIE array in the DWARFUnit.

[clayborg]

Summary

Storing a DWARFDebugInfoEntry for each NULL DIE that terminates a sibling chain takes up memory. We can get away with not storing the NULL DIEs as long as we still can dump the DWARF correctly and also get the sibling DIEs correctly. This patch implements this and removes the "bool DWARFDie::IsNULL()" function as it is no longer needed.

llvm-dsymutil performance improved very slightly when making a dSYM file for a debug version of clang with over 1200 .o files.

[aprantl]

lib/DebugInfo/DWARF/DWARFDie.cpp

354–356

Is there a better alternative to returning a magic value?

tools/dsymutil/DwarfLinker.cpp

1799

Might make sense to add a method that returns something like a SiblingIterator at some point in the future?

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1065–1067

Should we introduce something like a hasSibling() method? This almost sounds like it has a corrupted sibling DIE.

[dblaikie]

include/llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h

37–38

Comment seems temporal - it describes the change ("are /now/ removed") rather than the current state, which might be confusing for future readers.

It also might be easier if the member was called "isLastChild".

(similar comment on other comments - and a comment below might remove the need for this HasNullSibling/isLastChild member)

39

This should be a bool.

lib/DebugInfo/DWARF/DWARFDie.cpp

275–276

Is this necessary? (similarly for collectChildrenAddressRanges, dump, etc) - or should we just require clients not to call these operations on invalid DIEs?

392–399

I'm still not sure it should be the responsibility of this node to print the NULL entry here. Perhaps it should be handled when printing children instead? Between line 392 and 393 seems pretty ideal.

& it doesn't look like the 'getHasNULLSibling' property would be needed to correctly emit the NULL element at that location.

394

Seems unnecessary to call 'getDebugInfoEntry' from within DWARFDie - rather than accessing the 'Die' member directly.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1048–1059

As mentioned in previous comments - I'd suggest just dropping more of these checks. Do they add substantial value over the existing checks? (eg: are there bugs that are likely to be found by examining B & C's parentage that wouldn't be found by testing A's parentage?)

[aprantl]

Otherwise I think this looks nice. Does the memory usage go down measureably?

[clayborg]

Added inline comments and responses. New patch coming with fixes.

include/llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h

39

If you change the type it won't be part of the uint32_t for HasNullSibling. I compiled a quick example:

#include <stdint.h>

struct Test {
  uint32_t Depth : 31;
  bool IsLastChild : 1;
};

int main (int argc, char const *argv[])
{
  Test t = { 123, false };
  if (t.Depth)
    return 0;
  return 1;
}

And I got the following DWARF:

0x000000b0:     TAG_structure_type [8] *
                 AT_name( "Test" )
                 AT_byte_size( 0x04 )
                 AT_decl_file( "/private/tmp/main.c" )
                 AT_decl_line( 3 )

0x000000b8:         TAG_member [9]  
                     AT_name( "Depth" )
                     AT_type( {0x00000000000000e3} ( uint32_t ) )
                     AT_decl_file( "/private/tmp/main.c" )
                     AT_decl_line( 4 )
                     AT_byte_size( 0x04 )
                     AT_bit_size( 0x1f )
                     AT_bit_offset( 0x01 )
                     AT_data_member_location( +0 )

0x000000cd:         TAG_member [9]  
                     AT_name( "IsLastChild" )
                     AT_type( {0x00000000000000f9} ( bool ) )
                     AT_decl_file( "/private/tmp/main.c" )
                     AT_decl_line( 5 )
                     AT_byte_size( 0x01 )
                     AT_bit_size( 0x01 )
                     AT_bit_offset( 0x00 )
                     AT_data_member_location( +3 )

0x000000e2:         NULL

Note that IsLastChild has a AT_data_member_location that is +3 so it is in its own block. The type has to be the same in order to share storage. Changing IsLastChild to a uint32_t we see things are right:

0x000000b0:     TAG_structure_type [8] *
                 AT_name( "Test" )
                 AT_byte_size( 0x04 )
                 AT_decl_file( "/private/tmp/main.c" )
                 AT_decl_line( 3 )

0x000000b8:         TAG_member [9]  
                     AT_name( "Depth" )
                     AT_type( {0x00000000000000e3} ( uint32_t ) )
                     AT_decl_file( "/private/tmp/main.c" )
                     AT_decl_line( 4 )
                     AT_byte_size( 0x04 )
                     AT_bit_size( 0x1f )
                     AT_bit_offset( 0x01 )
                     AT_data_member_location( +0 )

0x000000cd:         TAG_member [9]  
                     AT_name( "IsLastChild" )
                     AT_type( {0x00000000000000e3} ( uint32_t ) )
                     AT_decl_file( "/private/tmp/main.c" )
                     AT_decl_line( 5 )
                     AT_byte_size( 0x04 )
                     AT_bit_size( 0x01 )
                     AT_bit_offset( 0x00 )
                     AT_data_member_location( +0 )

0x000000e2:         NULL

lib/DebugInfo/DWARF/DWARFDie.cpp

354–356

We should probably just assert this object is valid. Clients should check prior to calling.

395–399

I believe this does belong here. A DIE could claim to have children but only have a NULL inside of it, then we would fail to print the NULL if we try to do it with children at line 392. Also, if RecurseDepth is zero, we still need to print the NULL die since it is at the current recurse level. Given these reasons, it seems that we still need the getHasNULLSibling() property and this code belongs where it currently is.

tools/dsymutil/DwarfLinker.cpp

1799

I agree. A later commit we can add a function like:

DieIteratorRange DWARFDie::Children();

So we can then so:

for (auto Child: DIE.Children()) {

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1049–1059

I argue this one is needed. A was the first child of CU, B was the second child after A had no children, and C is the third child that follows B which had children. I do think all are valid tests that we can't regress on. This is testing the DWARF parser and making sure it they can track down their relations correctly. If we significantly change DWARFDebugInfoEntry at any point, we should verify everything still works.

Knowing the current algorithm to find the parent when we find the parent for A the depth decreases only as you walk backwards. The depth for B does, but it also has A at the same depth. The depth for C will go up when it sees the children for B and then go back down again, so I do believe all these tests are valid.

1065–1067

Now when we ask for a sibling and it doesn't have one we get an invalid DWARFDie back so this is the new way to check for that. I am not sure adding a hasSibling() method will make the code any clearer? If you wrote a loop using the current code, it currently looks like:

for (auto Child = Die.getFirstChild(); Child; Child = Child.getSibling())

We the "Child;" test is using the operator bool. If we add the hasSibling() would code actually use it? Does this look clearer:

for (auto Child = Die.getFirstChild(); Child; Child = Child.hasSibling() ? Child.getSibling() : DWARFDie())

So if we introduced it, who would actually use it? We could switch the code to use operator bool:

EXPECT_FALSE((bool)B2.getSibling());

But I am not sure that makes things clearer.

[clayborg]

Marked things as done.

tools/dsymutil/DwarfLinker.cpp

1799

Let me know if you guys want me to do the iterator thing in this patch?

[clayborg]

My current DWARF (dSYM) file for clang has 3448988 NULL dies. This means if we parsed all Dies and had them in memory, we would save 53MB of memory.

[clayborg]

Converting email only comments to be here with responses.

include/llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h

38

dblaike commented in email:

I think you might be misreading the DWARF (& it looks like the DWARF is a bit confusing, as well).

For starters - in both your examples, the byte_size of the struct is 4 bytes. So it seems storage is shared, or at least that using the same type doesn't improve/reduce the size of the struct - so on that basis I'd probably suggest using the bool type.

Beyond that, though. The AT_data_member_location is +3, as you say - not +4, so it is still using the top (or bottom - the counting here is a bit weird imho, but seems to work out) byte of the previous 4 byte value.

Also - we have /lots/ of similar mixed type bitfields in llvm, I think (have a grep around - it looks like it to me, at least) - so if this isn't doing the right thing I'd be /really/ surprised.

I did misread the DWARF, it is correct. I will switch this to bool.

lib/DebugInfo/DWARF/DWARFDie.cpp

399

dblaike said:

How would we succeed to print the NULL if we aren't printing children? There would be no 'last child' & so we wouldn't print the NULL in that case either.

So if you tell the CU DIE to print itself and have a recurse depth of 1 for DWARF like:

0x0: CU
0x1:  A
0x2    A1
0x3:   NULL
0x4:  B
0x5:   B1 
0x6:   NULL
0x7:  NULL

you would expect to see:

0x0: CU
0x1:  A
0x4:  B
0x7:  NULL

You're right though, we wouldn't print it in 392, but perhaps we should change the condition here from "if (Die->isLastChild())" to "if (Die->hasChildren())" ?

I think the misunderstanding here is that the NULL is actually terminating the current DIEs sibling chain, not the children's sibling chain. If we use "if (Die->hasChildren())" then we would print a NULL after every Die that has children, and since the NULL is for the current DIEs sibling, not the children, that would do the wrong thing:

0x0: CU
0x1:  A
0x2:  NULL // these would be incorrect
0x4:  B
0x5:  NULL // these would be incorrect
0x7:  NULL

Also, a test case for an empty child list would be good.

Agreed, I can add it.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

1049–1059

dblaike said:

Just to be clear - I'm never suggesting there are test cases we "can regress on", just asking about whether the test cases pull their weight - whether they exercise sufficiently distinct/interesting codepaths that make them important tests compared to the existing coverage.

It looks like C is perhaps a superset - it demonstrates we can go down into children, and back up. But, yes, good point that A and B are boundary/corner cases that are probably reasonable to test for separately.

Please add comments describing what makes each of these paths interesting. (eg: " verify an immediate parent", " verify skipping preceding siblings", "// verify skipping preceding niblings" (luls: https://en.wiktionary.org/wiki/nibling ) - those probably aren't the perfect comments, but a rough idea)

Will do.

[probinson]

include/llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h

38

No, please leave it as uint32_t. MSVC will do what you thought the DWARF said, and make the struct bigger unnecessarily.

@dblaikie yes we have mixed-type bitfields in llvm, but we also have places that deliberately use the same type when space savings matter. I see commits to change bitfield base types now and again for exactly that reason.

[clayborg]

Updated the DWARF tests to make sure we are testing the parent finding code correctly. The previous test was testing children that were at a depth of 1, but that was a special case in the test where any child with a depth of 1 has a parent of the compile/type unit DIE. By increasing the depth we are now testing the ability to find the parent by looking for the depth that is 1 less than the current depth.

[clayborg]

There are test failures with the obj2yaml and yaml2obj. After thinking about this patch more, we should probably leave in the NULL DIEs. My reasoning is
the NULLs correctly show the structure of the DWARF without needing any magic to reconstruct the NULL dies like we needed to do when dumping the DWARF. This was easy to work around for the dumping since we were using the getFirstChild()/getSibling() calls, but other clients that just want to walk through the DWARFDebugInfoEntry array, like the obj2yaml, would need to magically reconstruct these extra NULL dies with the correct offset.

So in order to not ruin the accurate representation that we currently have I will leave the NULL dies in.

include/llvm/DebugInfo/DWARF/DWARFDebugInfoEntry.h

 
 /// 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;
 
   /// 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;
+  uint32_t Depth : 31;
+  /// If non-zero this DIE is the last child in a sibling chain.
+  uint32_t IsLastChild : 1;
 
   const DWARFAbbreviationDeclaration *AbbrevDecl;
 public:
   DWARFDebugInfoEntry()
-    : Offset(0), Depth(0), AbbrevDecl(nullptr) {}
+    : Offset(0), Depth(0), IsLastChild(false), 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,
                    uint32_t Depth);
 
   uint32_t getOffset() const { return Offset; }
   uint32_t getDepth() const { return Depth; }
+  bool isLastChild() const { return IsLastChild; }
+  void setIsLastChild(bool B) { IsLastChild = B; }
   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;
   }
 };
 
 }
 
 #endif

include/llvm/DebugInfo/DWARF/DWARFDie.h

dwarf::Tag getTag() const {
     return dwarf::DW_TAG_null;
   }
 
   bool hasChildren() const {
     assert(isValid() && "must check validity prior to calling");
     return Die->hasChildren();
   }
   
-  /// Returns true for a valid DIE that terminates a sibling chain.
-  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.
   ///
public:
   }
   
   /// 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.
-  void dump(raw_ostream &OS, unsigned recurseDepth, unsigned indent = 0) const;
+  /// \returns the DIE offset that follows all of the DIEs that were dumped.
+  uint32_t dump(raw_ostream &OS, unsigned recurseDepth, unsigned indent = 0) const;
   
   /// Extract the specified attribute from this DIE.
   ///
   /// Extract an attribute value from this DIE only. This call doesn't look
   /// for the attribute value in any DW_AT_specification or
   /// DW_AT_abstract_origin referenced DIEs.
   ///
   /// \param Attr the attribute to extract.

lib/DebugInfo/DWARF/DWARFDie.cpp

if (auto HighPcAddr = getHighPC(*LowPcAddr)) {
     LowPC = *LowPcAddr;
     HighPC = *HighPcAddr;
     return true;
   }
   return false;
 }
 
 DWARFAddressRangesVector
 DWARFDie::getAddressRanges() const {
-  if (isNULL())
-    return DWARFAddressRangesVector();
+  assert(isValid() && "DIE must be checked before calling this function");
   // Single range specified by low/high PC.
   uint64_t LowPC, HighPC;
   if (getLowAndHighPC(LowPC, HighPC)) {
     return DWARFAddressRangesVector(1, std::make_pair(LowPC, HighPC));
   }
   // Multiple ranges from .debug_ranges section.
   auto RangesOffset = getAttributeValueAsSectionOffset(DW_AT_ranges);
   if (RangesOffset) {
     DWARFDebugRangeList RangeList;
     if (U->extractRangeList(*RangesOffset, RangeList))
       return RangeList.getAbsoluteRanges(U->getBaseAddress());
   }
   return DWARFAddressRangesVector();
 }
 
 void
 DWARFDie::collectChildrenAddressRanges(DWARFAddressRangesVector& Ranges) const {
-  if (isNULL())
-    return;
+  assert(isValid() && "DIE must be checked before calling this function");
   if (isSubprogramDIE()) {
     const auto &DIERanges = getAddressRanges();
     Ranges.insert(Ranges.end(), DIERanges.begin(), DIERanges.end());
   }
 
   DWARFDie Child = getFirstChild();
   while (Child) {
     Child.collectChildrenAddressRanges(Ranges);

 
 void DWARFDie::getCallerFrame(uint32_t &CallFile, uint32_t &CallLine,
                               uint32_t &CallColumn) const {
   CallFile = getAttributeValueAsUnsignedConstant(DW_AT_call_file, 0);
   CallLine = getAttributeValueAsUnsignedConstant(DW_AT_call_line, 0);
   CallColumn = getAttributeValueAsUnsignedConstant(DW_AT_call_column, 0);
 }
 
-void DWARFDie::dump(raw_ostream &OS, unsigned RecurseDepth,
+uint32_t DWARFDie::dump(raw_ostream &OS, unsigned RecurseDepth,
                         unsigned Indent) const {
-  if (!isValid())
-    return;
+  assert(isValid() && "DIE must be checked before calling this function");
   DataExtractor debug_info_data = U->getDebugInfoExtractor();
-  const uint32_t Offset = getOffset();
-  uint32_t offset = Offset;
+  const uint32_t DieOffset = getOffset();
+  uint32_t Offset = DieOffset;
   
-  if (debug_info_data.isValidOffset(offset)) {
-    uint32_t abbrCode = debug_info_data.getULEB128(&offset);
-    WithColor(OS, syntax::Address).get() << format("\n0x%8.8x: ", Offset);
+  if (debug_info_data.isValidOffset(Offset)) {
+    uint32_t abbrCode = debug_info_data.getULEB128(&Offset);
+    WithColor(OS, syntax::Address).get() << format("\n0x%8.8x: ", DieOffset);
     
     if (abbrCode) {
       auto AbbrevDecl = getAbbreviationDeclarationPtr();
       if (AbbrevDecl) {
         auto tagString = TagString(getTag());
         if (!tagString.empty())
           WithColor(OS, syntax::Tag).get().indent(Indent) << tagString;
         else
           WithColor(OS, syntax::Tag).get().indent(Indent)
           << format("DW_TAG_Unknown_%x", getTag());
         
         OS << format(" [%u] %c\n", abbrCode,
                      AbbrevDecl->hasChildren() ? '*' : ' ');
         
         // Dump all data in the DIE for the attributes.
         for (const auto &AttrSpec : AbbrevDecl->attributes()) {
-          dumpAttribute(OS, *this, &offset, AttrSpec.Attr, AttrSpec.Form,
+          dumpAttribute(OS, *this, &Offset, AttrSpec.Attr, AttrSpec.Form,
                         Indent);
         }
         
         DWARFDie child = getFirstChild();
         if (RecurseDepth > 0 && child) {
           while (child) {
-            child.dump(OS, RecurseDepth-1, Indent+2);
+            Offset = child.dump(OS, RecurseDepth-1, Indent+2);
             child = child.getSibling();
           }
         }
+        
+        // We don't have NULL DIEs in our DWARFUnit anymore so we have to
+        // conjure up the NULL DIE when printing.
+        if (Die->isLastChild()) {
+          WithColor(OS, syntax::Address).get() << format("\n0x%8.8x: ", Offset);
+          OS.indent(Indent) << "NULL\n";
+          // Add 1 to the offset for the ULEB128 abbreviation code byte.
+          Offset += 1;
+        }
       } else {
         OS << "Abbreviation code not found in 'debug_abbrev' class for code: "
         << abbrCode << '\n';
       }
     } else {
       OS.indent(Indent) << "NULL\n";
     }
   }
+  // Return the offset of the next DIE in case we need to print a NULL DIE.
+  return Offset;
 }
 
 
 void DWARFDie::getInlinedChainForAddress(
     const uint64_t Address, SmallVectorImpl<DWARFDie> &InlinedChain) const {
-  if (isNULL())
-    return;
+  assert(isValid() && "DIE must be checked before calling this function");
   DWARFDie DIE(*this);
   while (DIE) {
     // Append current DIE to inlined chain only if it has correct tag
     // (e.g. it is not a lexical block).
     if (DIE.isSubroutineDIE())
       InlinedChain.push_back(DIE);
 
     // Try to get child which also contains provided address.

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.
   uint32_t DIEOffset = Offset + getHeaderSize();
   uint32_t NextCUOffset = getNextUnitOffset();
   DWARFDebugInfoEntry DIE;
   DataExtractor DebugInfoData = getDebugInfoExtractor();
   uint32_t Depth = 0;
   bool IsCUDie = true;
+  // We don't add NULL DIEs do the Dies array anymore so we need to keep track
+  // of the indexes for DIEs at each depth so we can modify DIEs to tell them
+  // that they have a NULL sibling DIE so we can dump the NULL dies correctly.
+  SmallVector<uint32_t, 16> DieIndexes;
+  DieIndexes.push_back(0);
 
   while (DIE.extractFast(*this, &DIEOffset, DebugInfoData, NextCUOffset,
                          Depth)) {
+    auto AbbrDecl = DIE.getAbbreviationDeclarationPtr();
     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 {
+    } else if (AbbrDecl) {
+      // Only append non NULL DIEs to the array.
       Dies.push_back(DIE);
     }
 
-    if (const DWARFAbbreviationDeclaration *AbbrDecl =
-            DIE.getAbbreviationDeclarationPtr()) {
+    if (AbbrDecl) {
       // Normal DIE
-      if (AbbrDecl->hasChildren())
+      
+      // Set the DIE index in the DIE index array so we can track which siblings
+      // would have had NULL DIEs.
+      DieIndexes.back() = Dies.size() - 1;
+      if (AbbrDecl->hasChildren()) {
+        // Add an extra level to the DieIndexes when we have a child DIE. We
+        // set the index to the size of the Dies array since that will be the
+        // next DIE index.
+        DieIndexes.push_back(Dies.size());
         ++Depth;
+      }
     } else {
       // NULL DIE.
+      
+      // Tell the previous sibing that is has a NULL sibling so we can dump
+      // the DWARF correctly.
+      Dies[DieIndexes.back()].setIsLastChild(true);
+      DieIndexes.pop_back();
       if (Depth > 0)
         --Depth;
       if (Depth == 0)
         break;  // We are done with this compile unit!
     }
   }
 
   // Give a little bit of info if we encounter corrupt DWARF (our offset
DWARFDie DWARFUnit::getSibling(const DWARFDebugInfoEntry *Die) {
   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)
+    auto CurrDepth = DieArray[I].getDepth();
+    if (CurrDepth == Depth)
       return DWARFDie(this, &DieArray[I]);
+    // We don't have NULL DIEs anymore to terminate a sibling chain so we need
+    // to watch for the current depth going below our current depth since that
+    // will be a parent DIE and break out if we see that.
+    if (CurrDepth < Depth)
+      break;
   }
   return DWARFDie();
 }
 
 } // end namespace llvm

tools/dsymutil/DwarfLinker.cpp

if (CurrentDeclContext) {
       Info.Ctxt =
           PtrInvalidPair.getInt() ? nullptr : PtrInvalidPair.getPointer();
     } else
       Info.Ctxt = CurrentDeclContext = nullptr;
   }
 
   Info.Prune = InImportedModule;
   if (DIE.hasChildren())
-    for (auto Child = DIE.getFirstChild(); Child && !Child.isNULL();
-         Child = Child.getSibling())
+    for (auto Child = DIE.getFirstChild(); Child; Child = Child.getSibling())
       Info.Prune &= analyzeContextInfo(Child, MyIdx, CU, CurrentDeclContext,
                                        StringPool, Contexts, InImportedModule);
 
   // Prune this DIE if it is either a forward declaration inside a
   // DW_TAG_module or a DW_TAG_module that contains nothing but
   // forward declarations.
   Info.Prune &= (DIE.getTag() == dwarf::DW_TAG_module) ||
                 DIE.getAttributeValueAsUnsignedConstant(
void DwarfLinker::lookForDIEsToKeep(RelocationManager &RelocMgr,
   // set of DIE types for which we want to ignore that directive and still
   // walk their children.
   if (dieNeedsChildrenToBeMeaningful(Die.getTag()))
     Flags &= ~TF_ParentWalk;
 
   if (!Die.hasChildren() || (Flags & TF_ParentWalk))
     return;
 
-  for (auto Child = Die.getFirstChild(); Child && !Child.isNULL();
-       Child = Child.getSibling())
+  for (auto Child = Die.getFirstChild(); Child; Child = Child.getSibling())
     lookForDIEsToKeep(RelocMgr, Child, DMO, CU, Flags);
 }
 
 /// \brief Assign an abbreviation numer to \p Abbrev.
 ///
 /// Our DIEs get freed after every DebugMapObject has been processed,
 /// thus the FoldingSet we use to unique DIEAbbrevs cannot refer to
 /// the instances hold by the DIEs. When we encounter an abbreviation
if (AttrInfo.Name)
                               Tag == dwarf::DW_TAG_inlined_subroutine);
   } else if (isTypeTag(Tag) && !AttrInfo.IsDeclaration &&
              getDIENames(InputDIE, AttrInfo)) {
     Unit.addTypeAccelerator(Die, AttrInfo.Name, AttrInfo.NameOffset);
   }
 
   // Determine whether there are any children that we want to keep.
   bool HasChildren = false;
-  for (auto Child = InputDIE.getFirstChild(); Child && !Child.isNULL();
+  for (auto Child = InputDIE.getFirstChild(); Child;
        Child = Child.getSibling()) {
     unsigned Idx = U.getDIEIndex(Child);
     if (Unit.getInfo(Idx).Keep) {
       HasChildren = true;
       break;
     }
   }
 
DIE *DwarfLinker::DIECloner::cloneDIE(
 
   if (!HasChildren) {
     // Update our size.
     Die->setSize(OutOffset - Die->getOffset());
     return Die;
   }
 
   // Recursively clone children.
-  for (auto Child = InputDIE.getFirstChild(); Child && !Child.isNULL();
+  for (auto Child = InputDIE.getFirstChild(); Child;
        Child = Child.getSibling()) {
     if (DIE *Clone = cloneDIE(Child, Unit, PCOffset, OutOffset, Flags)) {
       Die->addChild(Clone);
       OutOffset = Clone->getOffset() + Clone->getSize();
     }
   }
 
   // Account for the end of children marker.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

template <uint16_t Version, class AddrType> void TestChildren() {
   EXPECT_EQ(SubprogramDieDG.getTag(), DW_TAG_subprogram);
 
   // Verify the first child of the subprogram is our formal parameter.
   auto ArgcDieDG = SubprogramDieDG.getFirstChild();
   EXPECT_TRUE(ArgcDieDG.isValid());
   EXPECT_EQ(ArgcDieDG.getTag(), DW_TAG_formal_parameter);
 
   // Verify our formal parameter has a NULL tag sibling.
-  auto NullDieDG = ArgcDieDG.getSibling();
-  EXPECT_TRUE(NullDieDG.isValid());
-  if (NullDieDG) {
-    EXPECT_EQ(NullDieDG.getTag(), DW_TAG_null);
-    EXPECT_TRUE(!NullDieDG.getSibling().isValid());
-    EXPECT_TRUE(!NullDieDG.getFirstChild().isValid());
-  }
+  EXPECT_FALSE(ArgcDieDG.getSibling().isValid());
 
   // Verify the sibling of our subprogram is our integer base type.
   auto IntDieDG = SubprogramDieDG.getSibling();
   EXPECT_TRUE(IntDieDG.isValid());
   EXPECT_EQ(IntDieDG.getTag(), DW_TAG_base_type);
 
   // Verify the sibling of our subprogram is our integer base is a NULL tag.
-  NullDieDG = IntDieDG.getSibling();
-  EXPECT_TRUE(NullDieDG.isValid());
-  if (NullDieDG) {
-    EXPECT_EQ(NullDieDG.getTag(), DW_TAG_null);
-    EXPECT_TRUE(!NullDieDG.getSibling().isValid());
-    EXPECT_TRUE(!NullDieDG.getFirstChild().isValid());
-  }
+  EXPECT_FALSE(IntDieDG.getSibling().isValid());
 }
 
 TEST(DWARFDebugInfo, TestDWARF32Version2Addr4Children) {
   // Test that we can decode all forms for DWARF32, version 2, with 4 byte
   // addresses.
   typedef uint32_t AddrType;
   TestChildren<2, AddrType>();
 }
TEST(DWARFDebugInfo, TestRelations) {
   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
+    C1,
+    C2,
+    D,
+    D1
   };
 
   // Scope to allow us to re-use the same DIE names
   {
     // Create DWARF tree that looks like:
     //
     // CU
     //   A
-    //   B
-    //     B1
-    //     B2
-    //   C
-    //     C1
+    //     B
+    //     C
+    //       C1
+    //       C2
+    //     D
+    //       D1
     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);
+    dwarfgen::DIE A = CUDie.addChild((dwarf::Tag)Tag::A);
+    A.addChild((dwarf::Tag)Tag::B);
+    dwarfgen::DIE C = A.addChild((dwarf::Tag)Tag::C);
+    dwarfgen::DIE D = A.addChild((dwarf::Tag)Tag::D);
     C.addChild((dwarf::Tag)Tag::C1);
+    C.addChild((dwarf::Tag)Tag::C2);
+    D.addChild((dwarf::Tag)Tag::D1);
   }
 
   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);
+  // CUDie.dump(llvm::outs(), 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 B = A.getFirstChild();
   auto C = B.getSibling();
-  auto Null = C.getSibling();
+  auto D = 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 C's sibling is invalid as we no longer store NULL DIEs.
+  EXPECT_FALSE(D.getSibling().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);
+  EXPECT_EQ(D.getTag(), (dwarf::Tag)Tag::D);
 
   // Verify who has children
-  EXPECT_FALSE(A.hasChildren());
-  EXPECT_TRUE(B.hasChildren());
+  EXPECT_TRUE(A.hasChildren());
+  EXPECT_FALSE(B.hasChildren());
+  EXPECT_TRUE(C.hasChildren());
+  EXPECT_TRUE(D.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());
+  // Make sure the parent of all the children of A are the A.
+  // B is the first child in A, so we need to verify we can get the previous
+  // DIE as the parent.
+  EXPECT_EQ(B.getParent(), A);
+  // C is the second child in A, so we need to make sure we can backup across
+  // other DIE (B) at the same level to get the correct parent.
+  EXPECT_EQ(C.getParent(), A);
+  // D is the third child of A. We need to verify we can backup across other DIE
+  // (B and C) including DIE that have children (D) to get the correct parent.
+  EXPECT_EQ(D.getParent(), A);
+
+  // Verify that a DIE with no children returns an invalid DWARFDie.
+  EXPECT_FALSE(B.getFirstChild().isValid());
 
   // Verify the children of the B DIE
-  auto B1 = B.getFirstChild();
-  auto B2 = B1.getSibling();
-  EXPECT_TRUE(B2.getSibling().isNULL());
+  auto C1 = C.getFirstChild();
+  auto C2 = C1.getSibling();
+  EXPECT_FALSE(C2.getSibling().isValid());
   
   // 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);
+  EXPECT_EQ(C1.getTag(), (dwarf::Tag)Tag::C1);
+  EXPECT_EQ(C2.getTag(), (dwarf::Tag)Tag::C2);
 
   // Make sure the parent of all the children of the B are the B.
-  EXPECT_EQ(B1.getParent(), B);
-  EXPECT_EQ(B2.getParent(), B);
+  EXPECT_EQ(C1.getParent(), C);
+  EXPECT_EQ(C2.getParent(), C);
 }
 
 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