[dwarfdump] Add DWARF verifiers for address ranges

[JDevlieghere]

Summary

I started to rebase Greg's differential (D32821) and quickly noticed
that it'd require quite a lot of changes. Rather than blindly fixing the
merge conflicts I started adding the functionality one by one. The
result is both quite similar and different at the same time. This also
gave me a better understanding of the code, which hopefully makes it
easier for me to address any remaining issues.

I've managed to keep everything contained in`DieRangeInfo` (with the
help of the existing DWARFAddressRange). I've done my best to keep
things as analogous as possible between checking for intersection
between an address range within the same DIE and children's address
ranges. The actual checking is also contained to verifyDieRanges.

I've reused all Greg's test so the result should be identical. I've also
ran this on some large internal projects for verification.

[aprantl]

Seems generally good. Since David had a lot of comments on the original review, I'll defer to him to accept this.

include/llvm/DebugInfo/DWARF/DWARFVerifier.h

60 ↗

(On Diff #114621)

does this comment belong to the next function?

83 ↗

(On Diff #114621)

///

lib/DebugInfo/DWARF/DWARFVerifier.cpp

61 ↗

(On Diff #114621)

s/fasts/fast./

[JDevlieghere]

Thanks Adrian!

[dblaikie]

Does this handle the interesting cases (test cases are a bit verbose, so I admit I haven't looked through them carefully) that came up in the original review:

Nested functions (a function inside a function - where the inner function shouldn't be contained within the ranges of the outer function (I find this weird, but apparently this is what Adrian & Paul & others think is right, and I can sort of see it - LLVM doesn't produce anything like this))?

Maybe that was the only interesting one...

include/llvm/DebugInfo/DWARF/DWARFVerifier.h

46 ↗

(On Diff #114621)

Drop "Ranges(), Children()" from here - they're the default

50 ↗

(On Diff #114621)

Drop the "Die()" and "Children()" from here - they're the default anyway?

50 ↗

(On Diff #114621)

use "Ranges(std::move(Ranges))" to avoid an unnecessary copy of the Ranges vector

lib/DebugInfo/DWARF/DWARFVerifier.cpp

35–36 ↗

(On Diff #114621)

drop else after return

[JDevlieghere]

Thanks Dave! There's no logic that deals specifically with nested functions, so I don't think it'll handle this particular case. Before hacking this in, I think it might be good to obtain a real example rather than an artificial one, to ensure we don't make the verification broader than necessary.

[JDevlieghere]

Add support and test case for nested functions, which should not be contained by their parent.

[dblaikie]

Also - how does this work (what does it do, does it catch things correctly) when there are DIEs without ranges - such as compile_unit{namespace{subprogram}} - does it still check that the subprogram is contained within the compile_unit?

lib/DebugInfo/DWARF/DWARFVerifier.cpp

338 ↗

(On Diff #115048)

the LLVM style doesn't generally use top-level const on locals - probably best to drop that for consistency

338–341 ↗

(On Diff #115048)

Would this correctly check that the nested subprogram is contained within the CU, though? (looks like it just punts on the nested subprogram entirely?)

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

2618–2619 ↗

(On Diff #115048)

Wouldn't this need three zero entries? (one to finish each DIE's child list)

[JDevlieghere]

In D37696#869811, @dblaikie wrote:

Also - how does this work (what does it do, does it catch things correctly) when there are DIEs without ranges - such as compile_unit{namespace{subprogram}} - does it still check that the subprogram is contained within the compile_unit?

Currently it only looks at an entity's direct parent. It will not detect that the subprogram is not part of the compile unit in this situation. If we keep a reference to the parent in each DWARFAddressRange we could walk up the chain until we find the first ancestor with a range. If it's contained this would would guarantee that it's also contained further up.

Would you agree to keep that for a separate diff? This situation would only result in a false-negative and I really think we would benefit from having this functionality checked-in.

lib/DebugInfo/DWARF/DWARFVerifier.cpp

338 ↗

(On Diff #115048)

Interesting. What's the reasoning behind this?

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

2618–2619 ↗

(On Diff #115048)

Thanks, I modified an existing test but forgot to update this part.

[dblaikie]

In D37696#870056, @JDevlieghere wrote:

In D37696#869811, @dblaikie wrote:

Also - how does this work (what does it do, does it catch things correctly) when there are DIEs without ranges - such as compile_unit{namespace{subprogram}} - does it still check that the subprogram is contained within the compile_unit?

Currently it only looks at an entity's direct parent. It will not detect that the subprogram is not part of the compile unit in this situation. If we keep a reference to the parent in each DWARFAddressRange we could walk up the chain until we find the first ancestor with a range. If it's contained this would would guarantee that it's also contained further up.

Would you agree to keep that for a separate diff? This situation would only result in a false-negative and I really think we would benefit from having this functionality checked-in.

Sure, fair enough.

One other thing: maybe revisit the testing (I know you brought that in from the previous patch, but I would've had the same feedback there, once we got past the other issus). It looks like a lot of testing that may be redundant (eg: the specific testing for subprograms V lexical blocks seems like maybe it could be omitted - the code doesn't special case them anyway). Also all the range overlapping checking - is some of that testing redundant or not well reduced? (it looks like full NxMx... sort of testing, when maybe representative examples could be taken without needing the fully combinatorial explosion of checks)

lib/DebugInfo/DWARF/DWARFVerifier.cpp

338 ↗

(On Diff #115048)

Isn't considered to add enough safety for the syntactic overhead, I guess. It'd be a /lot/ of const.

unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp

2618–2619 ↗

(On Diff #115048)

Does the test case fail with this mistake? (if it passes, why?)

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

 
 struct BaseAddress;
 class raw_ostream;
 
 struct DWARFAddressRange {
   uint64_t LowPC;
   uint64_t HighPC;
   uint64_t SectionIndex;
+
+  DWARFAddressRange() = default;
+
+  /// Used for unit testing.
+  DWARFAddressRange(uint64_t LowPC, uint64_t HighPC, uint64_t SectionIndex = 0)
+      : LowPC(LowPC), HighPC(HighPC), SectionIndex(SectionIndex) {}
+
+  /// Returns true if LowPC is smaller or equal to HighPC. This accounts for
+  /// dead-stripped ranges.
+  bool valid() const { return LowPC <= HighPC; }
+
+  /// Returns true if [LowPC, HighPC) intersects with [RHS.LowPC, RHS.HighPC).
+  bool intersects(const DWARFAddressRange &RHS) const {
+    // Empty ranges can't intersect.
+    if (LowPC == HighPC || RHS.LowPC == RHS.HighPC)
+      return false;
+    return (LowPC < RHS.HighPC) && (HighPC > RHS.LowPC);
+  }
+
+  /// Returns true if [LowPC, HighPC) fully contains [RHS.LowPC, RHS.HighPC).
+  bool contains(const DWARFAddressRange &RHS) const {
+    if (LowPC <= RHS.LowPC && RHS.LowPC <= HighPC)
+      return LowPC <= RHS.HighPC && RHS.HighPC <= HighPC;
+    return false;
+  }
 };
 
+static inline bool operator<(const DWARFAddressRange &LHS,
+                             const DWARFAddressRange &RHS) {
+  return std::tie(LHS.LowPC, LHS.HighPC) < std::tie(RHS.LowPC, RHS.HighPC);
+}
+
 /// DWARFAddressRangesVector - represents a set of absolute address ranges.
 using DWARFAddressRangesVector = std::vector<DWARFAddressRange>;
 
 class DWARFDebugRangeList {
 public:
   struct RangeListEntry {
     /// A beginning address offset. This address offset has the size of an
     /// address and is relative to the applicable base address of the

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

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> {
   DWARFDie Die;
   void skipNull() {
     if (Die && Die.isNULL())
       Die = DWARFDie();
   }

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

 //===- DWARFVerifier.h ----------------------------------------------------===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DEBUGINFO_DWARF_DWARFVERIFIER_H
 #define LLVM_DEBUGINFO_DWARF_DWARFVERIFIER_H
 
 #include "llvm/DebugInfo/DIContext.h"
+#include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h"
+#include "llvm/DebugInfo/DWARF/DWARFDie.h"
 
 #include <cstdint>
 #include <map>
 #include <set>
 
 namespace llvm {
 class raw_ostream;
 struct DWARFAttribute;
 class DWARFContext;
 class DWARFDie;
 class DWARFUnit;
 class DWARFAcceleratorTable;
 class DWARFDataExtractor;
 class DWARFDebugAbbrev;
 class DataExtractor;
 struct DWARFSection;
 
 /// A class that verifies DWARF debug information given a DWARF Context.
 class DWARFVerifier {
+public:
+  /// A class that keeps the address range information for a single DIE.
+  struct DieRangeInfo {
+    DWARFDie Die;
+
+    /// Sorted DWARFAddressRanges.
+    std::vector<DWARFAddressRange> Ranges;
+
+    /// Sorted DWARFAddressRangeInfo.
+    std::set<DieRangeInfo> Children;
+
+    DieRangeInfo() = default;
+    DieRangeInfo(DWARFDie Die) : Die(Die) {}
+
+    /// Used for unit testing.
+    DieRangeInfo(std::vector<DWARFAddressRange> Ranges)
+        : Ranges(std::move(Ranges)) {}
+
+    typedef std::vector<DWARFAddressRange>::const_iterator
+        address_range_iterator;
+    typedef std::set<DieRangeInfo>::const_iterator die_range_info_iterator;
+
+    /// Inserts the address range. If the range overlaps with an existing
+    /// range, the range is *not* added and an iterator to the overlapping
+    /// range is returned.
+    ///
+    /// This is used for finding overlapping ranges within the same DIE.
+    address_range_iterator insert(const DWARFAddressRange &R);
+
+    /// Finds an address range in the sorted vector of ranges.
+    address_range_iterator findRange(const DWARFAddressRange &R) const {
+      const auto Begin = Ranges.cbegin();
+      const auto End = Ranges.cend();
+      auto Iter = std::upper_bound(Begin, End, R);
+      if (Iter != Begin)
+        --Iter;
+      return Iter;
+    }
+
+    /// Inserts the address range info. If any of its ranges overlaps with a
+    /// range in an existing range info, the range info is *not* added and an
+    /// iterator to the overlapping range info.
+    ///
+    /// This is used for finding overlapping children of the same DIE.
+    die_range_info_iterator insert(const DieRangeInfo &RI);
+
+    /// Return true if ranges in this object contains all ranges within RHS.
+    bool contains(const DieRangeInfo &RHS) const;
+
+    /// Return true if any range in this object intersects with any range in
+    /// RHS.
+    bool intersects(const DieRangeInfo &RHS) const;
+  };
+
+private:
   raw_ostream &OS;
   DWARFContext &DCtx;
   DIDumpOptions DumpOpts;
   /// A map that tracks all references (converted absolute references) so we
   /// can verify each reference points to a valid DIE and not an offset that
   /// lies between to valid DIEs.
   std::map<uint64_t, std::set<uint32_t>> ReferenceToDIEOffsets;
   uint32_t NumDebugLineErrors = 0;
private:
   bool verifyUnitContents(DWARFUnit Unit);
 
   /// Verify that all Die ranges are valid.
   ///
   /// This function currently checks for:
   /// - cases in which lowPC >= highPC
   ///
   /// \returns Number of errors that occured during verification.
-  unsigned verifyDieRanges(const DWARFDie &Die);
+  unsigned verifyDieRanges(const DWARFDie &Die, DieRangeInfo &ParentRI);
 
   /// Verifies the attribute's DWARF attribute and its value.
   ///
   /// This function currently checks for:
   /// - DW_AT_ranges values is a valid .debug_ranges offset
   /// - DW_AT_stmt_list is a valid .debug_line offset
   ///
   /// \param Die          The DWARF DIE that owns the attribute value
public:
   /// Any errors are reported to the stream that was this object was
   /// constructed with.
   ///
   /// \returns true if the existing Apple-style accelerator tables verify
   /// successfully, false otherwise.
   bool handleAccelTables();
 };
 
+static inline bool operator<(const DWARFVerifier::DieRangeInfo &LHS,
+                             const DWARFVerifier::DieRangeInfo &RHS) {
+  return std::tie(LHS.Ranges, LHS.Die) < std::tie(RHS.Ranges, RHS.Die);
+}
+
 } // end namespace llvm
 
 #endif // LLVM_DEBUGINFO_DWARF_DWARFCONTEXT_H

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

 #include <map>
 #include <set>
 #include <vector>
 
 using namespace llvm;
 using namespace dwarf;
 using namespace object;
 
+DWARFVerifier::DieRangeInfo::address_range_iterator
+DWARFVerifier::DieRangeInfo::insert(const DWARFAddressRange &R) {
+  const auto Begin = Ranges.cbegin();
+  const auto End = Ranges.cend();
+  auto Pos = std::lower_bound(Begin, End, R);
+
+  if (Pos != End) {
+    if (Pos->intersects(R))
+      return Pos;
+    if (Pos != Begin) {
+      auto Iter = Pos - 1;
+      if (Iter->intersects(R))
+        return Iter;
+    }
+  }
+
+  Ranges.insert(Pos, R);
+  return Ranges.cend();
+}
+
+DWARFVerifier::DieRangeInfo::die_range_info_iterator
+DWARFVerifier::DieRangeInfo::insert(const DieRangeInfo &RI) {
+  const auto End = Children.end();
+  auto Iter = Children.begin();
+  while (Iter != End) {
+    if (Iter->intersects(RI))
+      return Iter;
+    ++Iter;
+  }
+  Children.insert(RI);
+  return Children.cend();
+}
+
+bool DWARFVerifier::DieRangeInfo::contains(const DieRangeInfo &RHS) const {
+  // Both list of ranges are sorted so we can make this fast.
+
+  if (Ranges.empty() || RHS.Ranges.empty())
+    return false;
+
+  // Since the ranges are sorted we can advance where we start searching with
+  // this object's ranges as we traverse RHS.Ranges.
+  const auto End = Ranges.cend();
+  auto Iter = findRange(RHS.Ranges.front());
+
+  // Now linearly walk the ranges in this object and see if they contain each
+  // ranges from RHS.Ranges.
+  for (const auto &R : RHS.Ranges) {
+    while (Iter != End) {
+      if (Iter->contains(R))
+        break;
+      ++Iter;
+    }
+    if (Iter == End)
+      return false;
+  }
+  return true;
+}
+
+bool DWARFVerifier::DieRangeInfo::intersects(const DieRangeInfo &RHS) const {
+  if (Ranges.empty() || RHS.Ranges.empty())
+    return false;
+
+  const auto End = Ranges.end();
+  auto Iter = findRange(RHS.Ranges.front());
+  for (const auto &R : RHS.Ranges) {
+    if (R.HighPC <= Iter->LowPC)
+      continue;
+    while (Iter != End) {
+      if (Iter->intersects(R))
+        return true;
+      ++Iter;
+    }
+  }
+
+  return false;
+}
+
 bool DWARFVerifier::verifyUnitHeader(const DWARFDataExtractor DebugInfoData,
                                      uint32_t *Offset, unsigned UnitIndex,
                                      uint8_t &UnitType, bool &isUnitDWARF64) {
   uint32_t AbbrOffset, Length;
   uint8_t AddrSize = 0;
   uint16_t Version;
   bool Success = true;
 

 
 bool DWARFVerifier::verifyUnitContents(DWARFUnit Unit) {
   uint32_t NumUnitErrors = 0;
   unsigned NumDies = Unit.getNumDIEs();
   for (unsigned I = 0; I < NumDies; ++I) {
     auto Die = Unit.getDIEAtIndex(I);
     if (Die.getTag() == DW_TAG_null)
       continue;
-    NumUnitErrors += verifyDieRanges(Die);
     for (auto AttrValue : Die.attributes()) {
       NumUnitErrors += verifyDebugInfoAttribute(Die, AttrValue);
       NumUnitErrors += verifyDebugInfoForm(Die, AttrValue);
     }
   }
+
+  DieRangeInfo RI;
+  DWARFDie Die = Unit.getUnitDIE(/* ExtractUnitDIEOnly = */ false);
+  NumUnitErrors += verifyDieRanges(Die, RI);
   return NumUnitErrors == 0;
 }
 
 unsigned DWARFVerifier::verifyAbbrevSection(const DWARFDebugAbbrev *Abbrev) {
   unsigned NumErrors = 0;
   if (Abbrev) {
     const DWARFAbbreviationDeclarationSet *AbbrDecls =
         Abbrev->getAbbreviationDeclarationSet(0);
bool DWARFVerifier::handleDebugInfo() {
   if (UnitIdx == 0 && !hasDIE) {
     OS << "Warning: .debug_info is empty.\n";
     isHeaderChainValid = true;
   }
   NumDebugInfoErrors += verifyDebugInfoReferences();
   return (isHeaderChainValid && NumDebugInfoErrors == 0);
 }
 
-unsigned DWARFVerifier::verifyDieRanges(const DWARFDie &Die) {
+unsigned DWARFVerifier::verifyDieRanges(const DWARFDie &Die,
+                                        DieRangeInfo &ParentRI) {
   unsigned NumErrors = 0;
-  for (auto Range : Die.getAddressRanges()) {
-    if (Range.LowPC >= Range.HighPC) {
+
+  if (!Die.isValid())
+    return NumErrors;
+
+  DWARFAddressRangesVector Ranges = Die.getAddressRanges();
+
+  // Build RI for this DIE and check that ranges within this DIE do not
+  // overlap.
+  DieRangeInfo RI(Die);
+  for (auto Range : Ranges) {
+    if (!Range.valid()) {
       ++NumErrors;
       OS << format("error: Invalid address range [0x%08" PRIx64
                    " - 0x%08" PRIx64 "].\n",
                    Range.LowPC, Range.HighPC);
+      continue;
     }
+
+    // Verify that ranges don't intersect.
+    const auto IntersectingRange = RI.insert(Range);
+    if (IntersectingRange != RI.Ranges.cend()) {
+      ++NumErrors;
+      OS << format("error: DIE has overlapping address ranges: [0x%08" PRIx64
+                   " - 0x%08" PRIx64 "] and [0x%08" PRIx64 " - 0x%08" PRIx64
+                   "].\n",
+                   Range.LowPC, Range.HighPC, IntersectingRange->LowPC,
+                   IntersectingRange->HighPC);
+      break;
+    }
+  }
+
+  // Verify that children don't intersect.
+  const auto IntersectingChild = ParentRI.insert(RI);
+  if (IntersectingChild != ParentRI.Children.cend()) {
+    ++NumErrors;
+    OS << "error: DIEs have overlapping address ranges:";
+    Die.dump(OS, 0);
+    IntersectingChild->Die.dump(OS, 0);
+    OS << "\n";
   }
+
+  // Verify that ranges are contained within their parent.
+  bool ShouldBeContained = !Ranges.empty() && !ParentRI.Ranges.empty() &&
+                           !(Die.getTag() == DW_TAG_subprogram &&
+                             ParentRI.Die.getTag() == DW_TAG_subprogram);
+  if (ShouldBeContained && !ParentRI.contains(RI)) {
+    ++NumErrors;
+    OS << "error: DIE address ranges are not "
+          "contained in its parent's ranges:";
+    Die.dump(OS, 0);
+    ParentRI.Die.dump(OS, 0);
+    OS << "\n";
+  }
+
+  // Recursively check children.
+  for (DWARFDie Child : Die)
+    NumErrors += verifyDieRanges(Child, RI);
+
   return NumErrors;
 }
 
 unsigned DWARFVerifier::verifyDebugInfoAttribute(const DWARFDie &Die,
                                                  DWARFAttribute &AttrValue) {
   const DWARFObject &DObj = DCtx.getDWARFObj();
   unsigned NumErrors = 0;
   const auto Attr = AttrValue.Attr;

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

 #include "llvm/ADT/Triple.h"
 #include "llvm/BinaryFormat/Dwarf.h"
 #include "llvm/CodeGen/AsmPrinter.h"
 #include "llvm/Config/llvm-config.h"
 #include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
 #include "llvm/DebugInfo/DWARF/DWARFContext.h"
 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
 #include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
+#include "llvm/DebugInfo/DWARF/DWARFVerifier.h"
 #include "llvm/MC/MCContext.h"
 #include "llvm/MC/MCSectionELF.h"
 #include "llvm/MC/MCStreamer.h"
 #include "llvm/Object/ObjectFile.h"
 #include "llvm/ObjectYAML/DWARFEmitter.h"
 #include "llvm/ObjectYAML/DWARFYAML.h"
 #include "llvm/Support/Error.h"
 #include "llvm/Support/MemoryBuffer.h"

 
 void VerifyError(DWARFContext &DwarfContext, StringRef Error) {
   SmallString<1024> Str;
   raw_svector_ostream Strm(Str);
   EXPECT_FALSE(DwarfContext.verify(Strm, DIDT_All));
   EXPECT_TRUE(Str.str().contains(Error));
 }
 
+void VerifySuccess(DWARFContext &DwarfContext) {
+  SmallString<1024> Str;
+  raw_svector_ostream Strm(Str);
+  EXPECT_TRUE(DwarfContext.verify(Strm, DIDT_All));
+}
+
 TEST(DWARFDebugInfo, TestDwarfVerifyInvalidCURef) {
   // Create a single compile unit with a single function that has a DW_AT_type
-  // that is CU relative. The CU offset is not valid becuase it is larger than
+  // that is CU relative. The CU offset is not valid because it is larger than
   // the compile unit itself.
 
   const char *yamldata = R"(
     debug_str:
       - ''
       - /tmp/main.c
       - main
     debug_abbrev:
std::unique_ptr<DWARFContext> Ctx2 =
       DWARFContext::create(**Obj, nullptr, [&](Error E) {
         ++Errors;
         consumeError(std::move(E));
         return ErrorPolicy::Halt;
       });
   EXPECT_TRUE(Errors == 1);
 }
 
+TEST(DWARFDebugInfo, TestDwarfVerifyCURangesIncomplete) {
+  // Create a single compile unit with a single function. The compile
+  // unit has a DW_AT_ranges attribute that doesn't fully contain the
+  // address range of the function. The verification should fail due to
+  // the CU ranges not containing all of the address ranges of all of the
+  // functions.
+  StringRef yamldata = R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+    debug_abbrev:
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_yes
+        Attributes:
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+      - Code:            0x00000002
+        Tag:             DW_TAG_subprogram
+        Children:        DW_CHILDREN_no
+        Attributes:
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+    debug_info:
+      - Length:
+          TotalLength:     46
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:
+          - AbbrCode:        0x00000001
+            Values:
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000001500
+              - Value:           0x0000000000000001
+          - AbbrCode:        0x00000002
+            Values:
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000000
+            Values:
+  )";
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+  std::unique_ptr<DWARFContext> DwarfContext =
+      DWARFContext::create(*ErrOrSections, 8);
+  VerifyError(*DwarfContext, "error: DIE address ranges are not "
+                             "contained in its parent's ranges:");
+}
+
+TEST(DWARFDebugInfo, TestDwarfVerifyLexicalBlockRanges) {
+  // Create a single compile unit with a single function that has a lexical
+  // block whose address range is not contained in the function address range.
+  StringRef yamldata = R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+      - main
+    debug_abbrev:
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_yes
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+      - Code:            0x00000002
+        Tag:             DW_TAG_subprogram
+        Children:        DW_CHILDREN_yes
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+      - Code:            0x00000003
+        Tag:             DW_TAG_lexical_block
+        Children:        DW_CHILDREN_no
+        Attributes:
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+    debug_info:
+      - Length:
+          TotalLength:     52
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:
+          - AbbrCode:        0x00000001
+            Values:
+              - Value:           0x0000000000000001
+          - AbbrCode:        0x00000002
+            Values:
+              - Value:           0x000000000000000D
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000003
+            Values:
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002001
+          - AbbrCode:        0x00000000
+            Values:
+          - AbbrCode:        0x00000000
+            Values:
+  )";
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+  std::unique_ptr<DWARFContext> DwarfContext =
+      DWARFContext::create(*ErrOrSections, 8);
+  VerifyError(*DwarfContext, "error: DIE address ranges are not "
+                             "contained in its parent's ranges:");
+}
+
+TEST(DWARFDebugInfo, TestDwarfVerifyOverlappingFunctionRanges) {
+  // Create a single compile unit with a two functions that have overlapping
+  // address ranges.
+  StringRef yamldata = R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+      - main
+      - foo
+    debug_abbrev:
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_yes
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+      - Code:            0x00000002
+        Tag:             DW_TAG_subprogram
+        Children:        DW_CHILDREN_no
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+    debug_info:
+      - Length:
+          TotalLength:     55
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:
+          - AbbrCode:        0x00000001
+            Values:
+              - Value:           0x0000000000000001
+          - AbbrCode:        0x00000002
+            Values:
+              - Value:           0x000000000000000D
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000002
+            Values:
+              - Value:           0x0000000000000012
+              - Value:           0x0000000000001FFF
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000000
+            Values:
+  )";
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+  std::unique_ptr<DWARFContext> DwarfContext =
+      DWARFContext::create(*ErrOrSections, 8);
+  VerifyError(*DwarfContext, "error: DIEs have overlapping address ranges:");
+}
+
+TEST(DWARFDebugInfo, TestDwarfVerifyOverlappingLexicalBlockRanges) {
+  // Create a single compile unit with a one function that has two lexical
+  // blocks with overlapping address ranges.
+  StringRef yamldata = R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+      - main
+    debug_abbrev:
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_yes
+        Attributes:
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+      - Code:            0x00000002
+        Tag:             DW_TAG_subprogram
+        Children:        DW_CHILDREN_yes
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+      - Code:            0x00000003
+        Tag:             DW_TAG_lexical_block
+        Children:        DW_CHILDREN_no
+        Attributes:
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+    debug_info:
+      - Length:
+          TotalLength:     85
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:
+          - AbbrCode:        0x00000001
+            Values:
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+              - Value:           0x0000000000000001
+          - AbbrCode:        0x00000002
+            Values:
+              - Value:           0x000000000000000D
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000003
+            Values:
+              - Value:           0x0000000000001100
+              - Value:           0x0000000000001300
+          - AbbrCode:        0x00000003
+            Values:
+              - Value:           0x00000000000012FF
+              - Value:           0x0000000000001300
+          - AbbrCode:        0x00000000
+            Values:
+          - AbbrCode:        0x00000000
+            Values:
+  )";
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+  std::unique_ptr<DWARFContext> DwarfContext =
+      DWARFContext::create(*ErrOrSections, 8);
+  VerifyError(*DwarfContext, "error: DIEs have overlapping address ranges:");
+}
+
+TEST(DWARFDebugInfo, TestDwarfVerifyInvalidDIERange) {
+  // Create a single compile unit with a single function that has an invalid
+  // address range where the high PC is smaller than the low PC.
+  StringRef yamldata = R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+      - main
+    debug_abbrev:
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_yes
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+      - Code:            0x00000002
+        Tag:             DW_TAG_subprogram
+        Children:        DW_CHILDREN_no
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+    debug_info:
+      - Length:
+          TotalLength:     34
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:
+          - AbbrCode:        0x00000001
+            Values:
+              - Value:           0x0000000000000001
+          - AbbrCode:        0x00000002
+            Values:
+              - Value:           0x000000000000000D
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000000900
+          - AbbrCode:        0x00000000
+            Values:
+  )";
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+  std::unique_ptr<DWARFContext> DwarfContext =
+      DWARFContext::create(*ErrOrSections, 8);
+  VerifyError(*DwarfContext, "error: Invalid address range");
+}
+
+TEST(DWARFDebugInfo, TestDwarfVerifyElidedDoesntFail) {
+  // Create a single compile unit with two functions: one that has a valid range
+  // and one whose low and high PC are the same. When the low and high PC are
+  // the same, this indicates the function was dead code stripped. We want to
+  // ensure that verification succeeds.
+  StringRef yamldata = R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+      - main
+      - elided
+    debug_abbrev:
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_yes
+        Attributes:
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+      - Code:            0x00000002
+        Tag:             DW_TAG_subprogram
+        Children:        DW_CHILDREN_no
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+    debug_info:
+      - Length:
+          TotalLength:     71
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:
+          - AbbrCode:        0x00000001
+            Values:
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+              - Value:           0x0000000000000001
+          - AbbrCode:        0x00000002
+            Values:
+              - Value:           0x000000000000000D
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000002
+            Values:
+              - Value:           0x0000000000000012
+              - Value:           0x0000000000002000
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000000
+            Values:
+  )";
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+  std::unique_ptr<DWARFContext> DwarfContext =
+      DWARFContext::create(*ErrOrSections, 8);
+  VerifySuccess(*DwarfContext);
+}
+
+TEST(DWARFDebugInfo, TestDwarfVerifyNestedFunctions) {
+  // Create a single compile unit with a nested function which is not contained
+  // in its parent. Although LLVM doesn't generate this, it is valid accoridng
+  // to the DWARF standard.
+  StringRef yamldata = R"(
+    debug_str:
+      - ''
+      - /tmp/main.c
+      - main
+      - nested
+    debug_abbrev:
+      - Code:            0x00000001
+        Tag:             DW_TAG_compile_unit
+        Children:        DW_CHILDREN_yes
+        Attributes:
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+      - Code:            0x00000002
+        Tag:             DW_TAG_subprogram
+        Children:        DW_CHILDREN_yes
+        Attributes:
+          - Attribute:       DW_AT_name
+            Form:            DW_FORM_strp
+          - Attribute:       DW_AT_low_pc
+            Form:            DW_FORM_addr
+          - Attribute:       DW_AT_high_pc
+            Form:            DW_FORM_addr
+    debug_info:
+      - Length:
+          TotalLength:     73
+        Version:         4
+        AbbrOffset:      0
+        AddrSize:        8
+        Entries:
+          - AbbrCode:        0x00000001
+            Values:
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000002000
+              - Value:           0x0000000000000001
+          - AbbrCode:        0x00000002
+            Values:
+              - Value:           0x000000000000000D
+              - Value:           0x0000000000001000
+              - Value:           0x0000000000001500
+          - AbbrCode:        0x00000002
+            Values:
+              - Value:           0x0000000000000012
+              - Value:           0x0000000000001500
+              - Value:           0x0000000000002000
+          - AbbrCode:        0x00000000
+            Values:
+          - AbbrCode:        0x00000000
+            Values:
+          - AbbrCode:        0x00000000
+            Values:
+  )";
+  auto ErrOrSections = DWARFYAML::EmitDebugSections(yamldata);
+  ASSERT_TRUE((bool)ErrOrSections);
+  std::unique_ptr<DWARFContext> DwarfContext =
+      DWARFContext::create(*ErrOrSections, 8);
+  VerifySuccess(*DwarfContext);
+}
+
+TEST(DWARFDebugInfo, TestDwarfRangesContains) {
+  DWARFAddressRange R(0x10, 0x20);
+
+  //----------------------------------------------------------------------
+  // Test ranges that start before R...
+  //----------------------------------------------------------------------
+  // Other range ends before start of R
+  ASSERT_FALSE(R.contains({0x0f, 0x10}));
+  // Other range end address is start of a R
+  ASSERT_FALSE(R.contains({0x0f, 0x11}));
+  // Other range end address is at and of R
+  ASSERT_FALSE(R.contains({0x0f, 0x20}));
+  // Other range end address is past end of R
+  ASSERT_FALSE(R.contains({0x0f, 0x40}));
+
+  //----------------------------------------------------------------------
+  // Test ranges that start at R's start address
+  //----------------------------------------------------------------------
+  // Ensure empty ranges matches
+  ASSERT_TRUE(R.contains({0x10, 0x10}));
+  // 1 byte of Range
+  ASSERT_TRUE(R.contains({0x10, 0x11}));
+  // same as Range
+  ASSERT_TRUE(R.contains({0x10, 0x20}));
+  // 1 byte past Range
+  ASSERT_FALSE(R.contains({0x10, 0x21}));
+
+  //----------------------------------------------------------------------
+  // Test ranges that start inside Range
+  //----------------------------------------------------------------------
+  // empty in range
+  ASSERT_TRUE(R.contains({0x11, 0x11}));
+  // all in Range
+  ASSERT_TRUE(R.contains({0x11, 0x1f}));
+  // ends at end of Range
+  ASSERT_TRUE(R.contains({0x11, 0x20}));
+  // ends past Range
+  ASSERT_FALSE(R.contains({0x11, 0x21}));
+
+  //----------------------------------------------------------------------
+  // Test ranges that start at last bytes of Range
+  //----------------------------------------------------------------------
+  // ends at end of Range
+  ASSERT_TRUE(R.contains({0x1f, 0x20}));
+  // ends past Range
+  ASSERT_FALSE(R.contains({0x1f, 0x21}));
+
+  //----------------------------------------------------------------------
+  // Test ranges that start after Range
+  //----------------------------------------------------------------------
+  // empty considered in Range
+  ASSERT_TRUE(R.contains({0x20, 0x20}));
+  // valid past Range
+  ASSERT_FALSE(R.contains({0x20, 0x21}));
+}
+
+TEST(DWARFDebugInfo, TestDWARFDieRangeInfoContains) {
+  DWARFVerifier::DieRangeInfo Ranges({{0x10, 0x20}, {0x30, 0x40}});
+
+  ASSERT_FALSE(Ranges.contains({{{0x0f, 0x10}}}));
+  ASSERT_FALSE(Ranges.contains({{{0x20, 0x30}}}));
+  ASSERT_FALSE(Ranges.contains({{{0x40, 0x41}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x10, 0x20}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x11, 0x12}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x1f, 0x20}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x30, 0x40}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x31, 0x32}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x3f, 0x40}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x10, 0x20}, {0x30, 0x40}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x11, 0x12}, {0x31, 0x32}}}));
+  ASSERT_TRUE(Ranges.contains(
+      {{{0x11, 0x12}, {0x12, 0x13}, {0x31, 0x32}, {0x32, 0x33}}}));
+  ASSERT_FALSE(Ranges.contains({{{0x11, 0x12},
+                                 {0x12, 0x13},
+                                 {0x20, 0x21},
+                                 {0x31, 0x32},
+                                 {0x32, 0x33}}}));
+  ASSERT_FALSE(Ranges.contains(
+      {{{0x11, 0x12}, {0x12, 0x13}, {0x31, 0x32}, {0x32, 0x41}}}));
+}
+
+namespace {
+
+void AssertRangesIntersect(const DWARFAddressRange &LHS,
+                           const DWARFAddressRange &RHS) {
+  ASSERT_TRUE(LHS.intersects(RHS));
+  ASSERT_TRUE(RHS.intersects(LHS));
+}
+void AssertRangesDontIntersect(const DWARFAddressRange &LHS,
+                               const DWARFAddressRange &RHS) {
+  ASSERT_FALSE(LHS.intersects(RHS));
+  ASSERT_FALSE(RHS.intersects(LHS));
+}
+
+void AssertRangesIntersect(const DWARFVerifier::DieRangeInfo &LHS,
+                           const DWARFAddressRangesVector &Ranges) {
+  DWARFVerifier::DieRangeInfo RHS(Ranges);
+  ASSERT_TRUE(LHS.intersects(RHS));
+  ASSERT_TRUE(RHS.intersects(LHS));
+}
+
+void AssertRangesDontIntersect(const DWARFVerifier::DieRangeInfo &LHS,
+                               const DWARFAddressRangesVector &Ranges) {
+  DWARFVerifier::DieRangeInfo RHS(Ranges);
+  ASSERT_FALSE(LHS.intersects(RHS));
+  ASSERT_FALSE(RHS.intersects(LHS));
+}
+
+} // namespace
+TEST(DWARFDebugInfo, TestDwarfRangesIntersect) {
+  DWARFAddressRange R(0x10, 0x20);
+
+  //----------------------------------------------------------------------
+  // Test ranges that start before R...
+  //----------------------------------------------------------------------
+  // Other range ends before start of R
+  AssertRangesDontIntersect(R, {0x00, 0x10});
+  // Other range end address is start of a R
+  AssertRangesIntersect(R, {0x00, 0x11});
+  // Other range end address is in R
+  AssertRangesIntersect(R, {0x00, 0x15});
+  // Other range end address is at and of R
+  AssertRangesIntersect(R, {0x00, 0x20});
+  // Other range end address is past end of R
+  AssertRangesIntersect(R, {0x00, 0x40});
+
+  //----------------------------------------------------------------------
+  // Test ranges that start at R's start address
+  //----------------------------------------------------------------------
+  // Ensure empty ranges doesn't match
+  AssertRangesDontIntersect(R, {0x10, 0x10});
+  // 1 byte of Range
+  AssertRangesIntersect(R, {0x10, 0x11});
+  // same as Range
+  AssertRangesIntersect(R, {0x10, 0x20});
+  // 1 byte past Range
+  AssertRangesIntersect(R, {0x10, 0x21});
+
+  //----------------------------------------------------------------------
+  // Test ranges that start inside Range
+  //----------------------------------------------------------------------
+  // empty in range
+  AssertRangesDontIntersect(R, {0x11, 0x11});
+  // all in Range
+  AssertRangesIntersect(R, {0x11, 0x1f});
+  // ends at end of Range
+  AssertRangesIntersect(R, {0x11, 0x20});
+  // ends past Range
+  AssertRangesIntersect(R, {0x11, 0x21});
+
+  //----------------------------------------------------------------------
+  // Test ranges that start at last bytes of Range
+  //----------------------------------------------------------------------
+  // ends at end of Range
+  AssertRangesIntersect(R, {0x1f, 0x20});
+  // ends past Range
+  AssertRangesIntersect(R, {0x1f, 0x21});
+
+  //----------------------------------------------------------------------
+  // Test ranges that start after Range
+  //----------------------------------------------------------------------
+  // empty just past in Range
+  AssertRangesDontIntersect(R, {0x20, 0x20});
+  // valid past Range
+  AssertRangesDontIntersect(R, {0x20, 0x21});
+}
+
+TEST(DWARFDebugInfo, TestDWARFDieRangeInfoIntersects) {
+
+  DWARFVerifier::DieRangeInfo Ranges({{0x10, 0x20}, {0x30, 0x40}});
+
+  // Test empty range
+  AssertRangesDontIntersect(Ranges, {});
+  // Test range that appears before all ranges in Ranges
+  AssertRangesDontIntersect(Ranges, {{0x00, 0x10}});
+  // Test range that appears between ranges in Ranges
+  AssertRangesDontIntersect(Ranges, {{0x20, 0x30}});
+  // Test range that appears after ranges in Ranges
+  AssertRangesDontIntersect(Ranges, {{0x40, 0x50}});
+
+  // Test range that start before first range
+  AssertRangesIntersect(Ranges, {{0x00, 0x11}});
+  // Test range that start at first range
+  AssertRangesIntersect(Ranges, {{0x10, 0x11}});
+  // Test range that start in first range
+  AssertRangesIntersect(Ranges, {{0x11, 0x12}});
+  // Test range that start at end of first range
+  AssertRangesIntersect(Ranges, {{0x1f, 0x20}});
+  // Test range that starts at end of first range
+  AssertRangesDontIntersect(Ranges, {{0x20, 0x21}});
+  // Test range that starts at end of first range
+  AssertRangesIntersect(Ranges, {{0x20, 0x31}});
+
+  // Test range that start before second range and ends before second
+  AssertRangesDontIntersect(Ranges, {{0x2f, 0x30}});
+  // Test range that start before second range and ends in second
+  AssertRangesIntersect(Ranges, {{0x2f, 0x31}});
+  // Test range that start at second range
+  AssertRangesIntersect(Ranges, {{0x30, 0x31}});
+  // Test range that start in second range
+  AssertRangesIntersect(Ranges, {{0x31, 0x32}});
+  // Test range that start at end of second range
+  AssertRangesIntersect(Ranges, {{0x3f, 0x40}});
+  // Test range that starts at end of second range
+  AssertRangesDontIntersect(Ranges, {{0x40, 0x41}});
+}
+
 } // end anonymous namespace