[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

   /// 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;
   }

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

 
     DieRangeInfo() = default;
     DieRangeInfo(DWARFDie Die) : Die(Die) {}
-
-    /// Used for unit testing.
     DieRangeInfo(std::vector<DWARFAddressRange> Ranges)
         : Ranges(std::move(Ranges)) {}
 

llvm/lib/DebugInfo/DWARF/DWARFVerifier.cpp

     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)) {
+                ++NumErrors;
+                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 &&