[WIP] Add debug location check to verifier.

[JDevlieghere]

Summary

Verify that at least one entry in the location list overlaps with the parent’s address range.

[JDevlieghere]

Increment number of errors so we have a non-zero exit code when this is hit.

[aprantl]

This would be very useful to find bugs in LLVM. That said, this looks like it is more a quality-of-implementation issue, and not a DWARF correctness issue. Should we separate the two? Or does DWARF mandate this?

[probinson]

We require that the child's (instruction) address range is contained within the parent's address range; I think it's equally sensible to verify that the location-list ranges are contained within the address range.
I don't know that DWARF explicitly requires this contained-ness, but it's clearly implicit in some of the sections I looked at while trying to answer that question.

llvm/include/llvm/DebugInfo/DWARF/DWARFAddressRange.h

struct DWARFAddressRange {
   /// 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; }
 
+  bool empty() const {  return LowPC == HighPC; }
+
   /// Returns true if [LowPC, HighPC) intersects with [RHS.LowPC, RHS.HighPC).
   bool intersects(const DWARFAddressRange &RHS) const {
     assert(valid() && RHS.valid());
     // Empty ranges can't intersect.
-    if (LowPC == HighPC || RHS.LowPC == RHS.HighPC)
+    if (empty())
       return false;
     return LowPC < RHS.HighPC && RHS.LowPC < HighPC;
   }
 
   /// Returns true if [LowPC, HighPC) fully contains [RHS.LowPC, RHS.HighPC).
   bool contains(const DWARFAddressRange &RHS) const {
     assert(valid() && RHS.valid());
     return LowPC <= RHS.LowPC && RHS.HighPC <= HighPC;

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

struct DieRangeInfo {
     /// 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

llvm/lib/DebugInfo/DWARF/DWARFVerifier.cpp

unsigned DWARFVerifier::verifyDieRanges(const DWARFDie &Die,
   if (IntersectingChild != ParentRI.Children.end()) {
     ++NumErrors;
     error() << "DIEs have overlapping address ranges:";
     Die.dump(OS, 0);
     IntersectingChild->Die.dump(OS, 0);
     OS << "\n";
   }
 
+  // Verify that location lists intersect with the parent's address range.
+  if (ParentRI.Die.isValid() && ParentRI.Die.getTag() != DW_TAG_inlined_subroutine) {
+    if (Optional<BaseAddress> BA = Die.getDwarfUnit()->getBaseAddress()) {
+      if (Optional<DWARFFormValue> FormValue = Die.find(DW_AT_location)) {
+        if (auto LocOffset = FormValue->getAsSectionOffset()) {
+          if (auto DebugLoc = DCtx.getDebugLoc()) {
+            if (auto LocList = DebugLoc->getLocationListAtOffset(*LocOffset)) {
+              // Build a list of address ranges from the location list. Don't
+              // use the insert method because according to the standard the
+              // ranges can overlap.
+              DieRangeInfo LocationRI;
+              for (auto Entry : LocList->Entries) {
+                LocationRI.Ranges.emplace_back(Entry.Begin + BA->Address,
+                                               Entry.End + BA->Address);
+              }
+              // Now make sure that at least one range overlaps with the parent
+              // range.
+              if (!ParentRI.Ranges.empty() &&
+                  !ParentRI.intersects(LocationRI)) {
+                error() << "No entry in the location list shares an address "
+                           "range with its parent: ";
+                ParentRI.Die.dump(OS, 0);
+                Die.dump(OS, 2);
+                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;
     error() << "DIE address ranges are not contained in its parent's ranges:";
     ParentRI.Die.dump(OS, 0);