[DebugInfo] Verify that sibling and children fall in parent range.

[JDevlieghere]

Summary

I was recently looking at a binary where a TAG_subprogram didn't fall in its parent range. The dwarfdump that ships with Darwin was able to detect this, while LLVM's version didn't. This patch adds this verification.

I'm looking on input how best to test this. It seems to be currently tested in the unit tests with YAML input. I I have an object file of a minimal example, generated with an old compiler. However, just the DWARF corresponds to about 700 lines of YAML, which I'm afraid is not really appropriate for a unit tests.

[JDevlieghere]

@dblaikie wrote:

Might be worth looking at the previous review on this: https://reviews.llvm.org/D32821

(yeah, it stalled out - partly my fault, I did go back to try to work up the changes I'd been suggesting, but hit some other issues that I gave up on - might be worth discussing design first a bit before diving into the code changes)

I imagine a test for this could be reduced beyond 700 lines of YAML - happy to help with that if you get stuck/have trouble reducing/simplifying it.

(I mean there's several things to test for here, but one basic one should be well reduced to ~10s of lines, hopefully)

Thanks David, that looks very similar indeed! The truth is that I don't really have an idea how to get started on reducing a YAML test case without breaking everything. I've given it a try but the result wasn't valid anymore, even before changing the ranges.

[clayborg]

I tend to use the DWARF generator to create a super minimal DWARF file, then obj2yaml that. It tends to be really short and ok for adding as a test. The DWARF generator only exists in the gtest for the DWARF, but you can add a new gtest, generate the DWARF, then remove the gtest.

[JDevlieghere]

Abandoning in favor of D37696

lib/DebugInfo/DWARF/DWARFVerifier.cpp

bool DWARFVerifier::handleDebugInfo() {
   if (UnitIdx == 0 && !hasDIE) {
     OS << "Warning: .debug_info is empty.\n";
     isHeaderChainValid = true;
   }
   NumDebugInfoErrors += verifyDebugInfoReferences();
   return (isHeaderChainValid && NumDebugInfoErrors == 0);
 }
 
+static unsigned verifyDieParentRange(raw_ostream &OS,
+                                     const DWARFAddressRange &Range,
+                                     uint64_t ParentLowPC,
+                                     uint64_t ParentHighPC) {
+  unsigned NumErrors = 0;
+
+  if (Range.LowPC < ParentLowPC) {
+    ++NumErrors;
+    OS << format("error: Address 0x%08" PRIx64
+                 " not in parent range [0x%08" PRIx64 " - 0x%08" PRIx64 "].\n",
+                 Range.LowPC, ParentLowPC, ParentHighPC);
+  }
+
+  if (Range.HighPC > ParentHighPC) {
+    ++NumErrors;
+    OS << format("error: Address 0x%08" PRIx64
+                 " not in parent range [0x%08" PRIx64 " - 0x%08" PRIx64 "].\n",
+                 Range.HighPC, ParentLowPC, ParentHighPC);
+  }
+
+  return NumErrors;
+}
+
 unsigned DWARFVerifier::verifyDieRanges(const DWARFDie &Die) {
   unsigned NumErrors = 0;
+
+  // Remember low and high PC.
+  uint64_t LowPC = -1;
+  uint64_t HighPC = 0;
+
   for (auto Range : Die.getAddressRanges()) {
+    if (Range.LowPC < LowPC)
+      LowPC = Range.LowPC;
+    if (Range.HighPC > HighPC)
+      HighPC = Range.HighPC;
     if (Range.LowPC >= Range.HighPC) {
       ++NumErrors;
       OS << format("error: Invalid address range [0x%08" PRIx64
                    " - 0x%08" PRIx64 "].\n",
                    Range.LowPC, Range.HighPC);
     }
   }
+
+  // The loop didn't execute and there's nothing more to check.
+  if (LowPC > HighPC)
+    return NumErrors;
+
+  // Verify that all children fall within parent range.
+  DWARFAddressRangesVector ChildrenRanges;
+  Die.collectChildrenAddressRanges(ChildrenRanges);
+  for (auto Range : ChildrenRanges) {
+    NumErrors += verifyDieParentRange(OS, Range, LowPC, HighPC);
+  }
+
+  // Verify that sibling falls within parent range.
+  if (DWARFDie Sibling = Die.getSibling()) {
+    for (auto Range : Die.getSibling().getAddressRanges()) {
+      NumErrors += verifyDieParentRange(OS, Range, LowPC, HighPC);
+    }
+  }
+
   return NumErrors;
 }
 
 unsigned DWARFVerifier::verifyDebugInfoAttribute(const DWARFDie &Die,
                                                  DWARFAttribute &AttrValue) {
   const DWARFObject &DObj = DCtx.getDWARFObj();
   unsigned NumErrors = 0;
   const auto Attr = AttrValue.Attr;