[DWARF] Fix DWARFVerifier::DieRangeInfo::contains

It didn't handle empty LHS correctly. If two ranges of LHS were
contiguous and jointly contained one range of RHS, it could also be incorrect.

DWARFAddressRange::contains can be removed and its tests can be merged into DWARFVerifier::DieRangeInfo::contains

llvm-svn: 358387

3 files changed, 41 insertions, 83 deletions

diff --git a/llvm/include/llvm/DebugInfo/DWARF/DWARFAddressRange.h b/llvm/include/llvm/DebugInfo/DWARF/DWARFAddressRange.h
index 56d46c696fd..2d5f9f3c765 100644
--- a/llvm/include/llvm/DebugInfo/DWARF/DWARFAddressRange.h
+++ b/llvm/include/llvm/DebugInfo/DWARF/DWARFAddressRange.h
@@ -42,12 +42,6 @@ struct DWARFAddressRange {
     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;
-  }
-
   void dump(raw_ostream &OS, uint32_t AddressSize,
             DIDumpOptions DumpOpts = {}) const;
 };
diff --git a/llvm/lib/DebugInfo/DWARF/DWARFVerifier.cpp b/llvm/lib/DebugInfo/DWARF/DWARFVerifier.cpp
index 43e83c83fd9..a95c4f982c0 100644
--- a/llvm/lib/DebugInfo/DWARF/DWARFVerifier.cpp
+++ b/llvm/lib/DebugInfo/DWARF/DWARFVerifier.cpp
@@ -60,28 +60,27 @@ DWARFVerifier::DieRangeInfo::insert(const DieRangeInfo &RI) {
 }
 
 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.
-  auto End = Ranges.end();
-  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;
+  auto I1 = Ranges.begin(), E1 = Ranges.end();
+  auto I2 = RHS.Ranges.begin(), E2 = RHS.Ranges.end();
+  if (I2 == E2)
+    return true;
+
+  DWARFAddressRange R = *I2;
+  while (I1 != E1) {
+    bool Covered = I1->LowPC <= R.LowPC;
+    if (R.LowPC == R.HighPC || (Covered && R.HighPC <= I1->HighPC)) {
+      if (++I2 == E2)
+        return true;
+      R = *I2;
+      continue;
     }
-    if (Iter == End)
+    if (!Covered)
       return false;
+    if (R.LowPC < I1->HighPC)
+      R.LowPC = I1->HighPC;
+    ++I1;
   }
-  return true;
+  return false;
 }
 
 bool DWARFVerifier::DieRangeInfo::intersects(const DieRangeInfo &RHS) const {
diff --git a/llvm/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp b/llvm/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
index d3643ca4bb7..ef51ce0fbff 100644
--- a/llvm/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
+++ b/llvm/unittests/DebugInfo/DWARF/DWARFDebugInfoTest.cpp
@@ -2983,72 +2983,34 @@ TEST(DWARFDebugInfo, TestDwarfVerifyNestedFunctions) {
   VerifySuccess(*DwarfContext);
 }
 
-TEST(DWARFDebugInfo, TestDwarfRangesContains) {
-  DWARFAddressRange R(0x10, 0x20);
+TEST(DWARFDebugInfo, TestDWARFDieRangeInfoContains) {
+  DWARFVerifier::DieRangeInfo Empty;
+  ASSERT_TRUE(Empty.contains(Empty));
 
-  //----------------------------------------------------------------------
-  // 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}));
+  DWARFVerifier::DieRangeInfo Ranges(
+      {{0x10, 0x20}, {0x30, 0x40}, {0x40, 0x50}});
+
+  ASSERT_TRUE(Ranges.contains(Empty));
+  ASSERT_FALSE(Ranges.contains({{{0x0f, 0x10}}}));
+  ASSERT_FALSE(Ranges.contains({{{0x0f, 0x20}}}));
+  ASSERT_FALSE(Ranges.contains({{{0x0f, 0x21}}}));
 
-  //----------------------------------------------------------------------
   // 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}));
+  ASSERT_TRUE(Ranges.contains({{{0x10, 0x10}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x10, 0x11}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x10, 0x20}}}));
+  ASSERT_FALSE(Ranges.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}));
+  ASSERT_TRUE(Ranges.contains({{{0x11, 0x12}}}));
 
-  //----------------------------------------------------------------------
   // 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}));
+  ASSERT_TRUE(Ranges.contains({{{0x1f, 0x20}}}));
+  ASSERT_FALSE(Ranges.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_TRUE(Ranges.contains({{{0x20, 0x20}}}));
+  ASSERT_FALSE(Ranges.contains({{{0x20, 0x21}}}));
 
-  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}}}));
@@ -3061,7 +3023,10 @@ TEST(DWARFDebugInfo, TestDWARFDieRangeInfoContains) {
                                  {0x31, 0x32},
                                  {0x32, 0x33}}}));
   ASSERT_FALSE(Ranges.contains(
-      {{{0x11, 0x12}, {0x12, 0x13}, {0x31, 0x32}, {0x32, 0x41}}}));
+      {{{0x11, 0x12}, {0x12, 0x13}, {0x31, 0x32}, {0x32, 0x51}}}));
+  ASSERT_TRUE(Ranges.contains({{{0x11, 0x12}, {0x30, 0x50}}}));
+  ASSERT_FALSE(Ranges.contains({{{0x30, 0x51}}}));
+  ASSERT_FALSE(Ranges.contains({{{0x50, 0x51}}}));
 }
 
 namespace {