[DebugInfo] Make children iterator bidirectional

[JDevlieghere]

Summary

Make the DIE iterator bidirectional so we can move to the previous sibling of a DIE.

[JDevlieghere]

• Remove null check so we can iterate backwards from the end iterator.

[JDevlieghere]

• Update comments

[dblaikie]

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

354 ↗

(On Diff #155005)

Why was this change needed?

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

595–599 ↗

(On Diff #155005)

Unlike get(Next)Sibling, this loop may need to check for "<= Depth" and then return DWARFDie() if it's the < case.

When going forwards, there's always a null die sibling to break this loop (well, I guess a null die is returned from getSibling - and then no caller tries to call getSibling on the null die) - because it has the same depth.

But going backwards there's no null die to break the loop - oh, well, kind of.

So if you've got this arrangement: Unit{A{B,NULL},C{D,NULL},NULL}

And at D you "get previous" then you'll return the NULL child of A... which is still a null child, and that works I suppose. But you could've stopped searching once you saw C - because you've stepped out of C's children list by going to a shallower depth than the depth of D who's sibling you were searching for.

Oh... and it's undefined to dereference a begin iterator anyway, so none of that really matters, I suppose? :)

[JDevlieghere]

• Address review feedback Dave

[JDevlieghere]

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

354 ↗

(On Diff #155005)

For a bidirectional iterator you should be able to start iterating from end(), right? (so long you don't dereference it)

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

595–599 ↗

(On Diff #155005)

Indeed. I added the check at some point but looks like it didn't make it into the patch. Even if it doesn't matter for the iterator (I assume you mean dereferencing the end iterator?) the check is cheap so we might as well make the interface behave as you'd expect.

[dblaikie]

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

595–599 ↗

(On Diff #155005)

Yeah - if it were just the iterator API I'd say maybe make it an assert - but since this is a "getPrevSibling" it makes sense to me that it's not UB to call it on the first child, and for it to be symmetric with "get(Next)Sibling" in terms of returning null on the first/last element.

626 ↗

(On Diff #155021)

Maybe assert that DieArray[I].getDepth() > Depth - to ensure it didn't some how jump out of the children?

[JDevlieghere]

Thanks for the review!

llvm/lib/DebugInfo/DWARF/DWARFUnit.cpp

626 ↗

(On Diff #155021)

Good idea, I'll add that before committing.

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

public:
   DWARFDie getParent() const;
 
   /// 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;
 
+  /// Get the previous 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 getPreviousSibling() 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;
 
+  /// Get the last child of this DIE object.
+  ///
+  /// \returns a valid null DWARFDie instance if this object has children or an
+  /// invalid DWARFDie instance if it doesn't.
+  DWARFDie getLastChild() const;
+
   /// Dump the DIE and all of its attributes to the supplied stream.
   ///
   /// \param OS the stream to use for output.
   /// \param indent the number of characters to indent each line that is output.
   void dump(raw_ostream &OS, unsigned indent = 0,
             DIDumpOptions DumpOpts = DIDumpOptions()) const;
 
 
class DWARFDie::attribute_iterator :
   /// will be set to the end value so iteration stops.
   void updateForIndex(const DWARFAbbreviationDeclaration &AbbrDecl, uint32_t I);
 
 public:
   attribute_iterator() = delete;
   explicit attribute_iterator(DWARFDie D, bool End);
 
   attribute_iterator &operator++();
+  attribute_iterator &operator--();
   explicit operator bool() const { return AttrValue.isValid(); }
   const DWARFAttribute &operator*() const { return AttrValue; }
   bool operator==(const attribute_iterator &X) const { return Index == X.Index; }
 };
 
 inline bool operator==(const DWARFDie &LHS, const DWARFDie &RHS) {
   return LHS.getDebugInfoEntry() == RHS.getDebugInfoEntry() &&
       LHS.getDwarfUnit() == RHS.getDwarfUnit();
 }
 
 inline bool operator!=(const DWARFDie &LHS, const DWARFDie &RHS) {
   return !(LHS == RHS);
 }
 
 inline bool operator<(const DWARFDie &LHS, const DWARFDie &RHS) {
   return LHS.getOffset() < RHS.getOffset();
 }
 
-class DWARFDie::iterator : public iterator_facade_base<iterator,
-                                                      std::forward_iterator_tag,
-                                                      const DWARFDie> {
+class DWARFDie::iterator
+    : public iterator_facade_base<iterator, std::bidirectional_iterator_tag,
   DWARFDie Die;
-  void skipNull() {
-    if (Die && Die.isNULL())
-      Die = DWARFDie();
-  }
 public:
   iterator() = default;
 
   explicit iterator(DWARFDie D) : Die(D) {
-    // If we start out with only a Null DIE then invalidate.
-    skipNull();
   }
 
   iterator &operator++() {
     Die = Die.getSibling();
-    // Don't include the NULL die when iterating.
-    skipNull();
+    return *this;
+  }
+
+  iterator &operator--() {
+    Die = Die.getPreviousSibling();
     return *this;
   }
 
   explicit operator bool() const { return Die.isValid(); }
   const DWARFDie &operator*() const { return Die; }
   bool operator==(const iterator &X) const { return Die == X.Die; }
 };
 
 // These inline functions must follow the DWARFDie::iterator definition above
 // as they use functions from that class.
 inline DWARFDie::iterator DWARFDie::begin() const {
   return iterator(getFirstChild());
 }
 
 inline DWARFDie::iterator DWARFDie::end() const {
-  return iterator();
+  return iterator(getLastChild());
 }
 
 inline iterator_range<DWARFDie::iterator> DWARFDie::children() const {
   return make_range(begin(), end());
 }
 
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_DWARFDIE_H

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

public:
   /// Return the DIE object at the given index.
   DWARFDie getDIEAtIndex(unsigned Index) {
     assert(Index < DieArray.size());
     return DWARFDie(this, &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
   /// 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());

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

 }
 
 DWARFDie DWARFDie::getSibling() const {
   if (isValid())
     return U->getSibling(Die);
   return DWARFDie();
 }
 
+DWARFDie DWARFDie::getPreviousSibling() const {
+  if (isValid())
+    return U->getPreviousSibling(Die);
+  return DWARFDie();
+}
+
 DWARFDie DWARFDie::getFirstChild() const {
   if (isValid())
     return U->getFirstChild(Die);
   return DWARFDie();
 }
 
+DWARFDie DWARFDie::getLastChild() const {
+  if (isValid())
+    return U->getLastChild(Die);
+  return DWARFDie();
+}
+
 iterator_range<DWARFDie::attribute_iterator> DWARFDie::attributes() const {
   return make_range(attribute_iterator(*this, false),
                     attribute_iterator(*this, true));
 }
 
 DWARFDie::attribute_iterator::attribute_iterator(DWARFDie D, bool End)
     : Die(D), AttrValue(0), Index(0) {
   auto AbbrDecl = Die.getAbbreviationDeclarationPtr();

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

DWARFDie DWARFUnit::getSibling(const DWARFDebugInfoEntry *Die) {
   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();
 }
 
+DWARFDie DWARFUnit::getPreviousSibling(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();
+
+  // Find the previous DIE whose depth is the same as the Die's depth.
+  for (size_t I = getDIEIndex(Die) - 1; I >= 0; --I) {
+    if (DieArray[I].getDepth() == Depth - 1)
+      return DWARFDie();
+    if (DieArray[I].getDepth() == Depth)
+      return DWARFDie(this, &DieArray[I]);
+  }
+  return DWARFDie();
+}
+
 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::getLastChild(const DWARFDebugInfoEntry *Die) {
+  if (!Die->hasChildren())
+    return DWARFDie();
+
+  uint32_t Depth = Die->getDepth();
+  for (size_t I = getDIEIndex(Die) + 1, EndIdx = DieArray.size(); I < EndIdx;
+       ++I) {
+    if (DieArray[I].getDepth() == Depth + 1 &&
+        DieArray[I].getTag() == dwarf::DW_TAG_null)
+      return DWARFDie(this, &DieArray[I]);
+    assert(DieArray[I].getDepth() > Depth && "Not processing children?");
+  }
+  return DWARFDie();
+}
+
 const DWARFAbbreviationDeclarationSet *DWARFUnit::getAbbreviations() const {
   if (!Abbrevs)
     Abbrevs = Abbrev->getAbbreviationDeclarationSet(Header.getAbbrOffset());
   return Abbrevs;
 }
 
 llvm::Optional<BaseAddress> DWARFUnit::getBaseAddress() {
   if (BaseAddr)

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

template <uint16_t Version, class AddrType> void TestChildren() {
   // 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());
   }
+
+  // Verify the previous sibling of our subprogram is our integer base type.
+  IntDieDG = NullDieDG.getPreviousSibling();
+  EXPECT_TRUE(IntDieDG.isValid());
+  EXPECT_EQ(IntDieDG.getTag(), DW_TAG_base_type);
 }
 
 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) {
 
   // Verify all children of the B DIE correctly valid or invalid.
   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(C1.getParent(), C);
   EXPECT_EQ(C2.getParent(), C);
+
+  // Make sure bidirectional iterator works as expected.
+  auto Begin = A.begin();
+  auto End = A.end();
+  auto It = A.begin();
+
+  EXPECT_EQ(It, Begin);
+  EXPECT_EQ(*It, B);
+  ++It;
+  EXPECT_EQ(*It, C);
+  ++It;
+  EXPECT_EQ(*It, D);
+  ++It;
+  EXPECT_EQ(It, End);
+  --It;
+  EXPECT_EQ(*It, D);
+  --It;
+  EXPECT_EQ(*It, C);
+  --It;
+  EXPECT_EQ(*It, B);
+  EXPECT_EQ(It, Begin);
 }
 
 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());