Revert "[dsymutil] dsymutil produces broken lines info (probably) with LTO on mac"

This reverts commit 56edf062bdb64f0ce89860ed3e643f29a2f90e45.

This change modified the public API/ABI which is not allowed in stable releases.

7 files changed, 207 insertions, 398 deletions

diff --git a/llvm/include/llvm/ADT/AddressRanges.h b/llvm/include/llvm/ADT/AddressRanges.h
index 415d30bbb5cf..f2052d82e7c1 100644
--- a/llvm/include/llvm/ADT/AddressRanges.h
+++ b/llvm/include/llvm/ADT/AddressRanges.h
@@ -28,11 +28,7 @@ public:
   uint64_t start() const { return Start; }
   uint64_t end() const { return End; }
   uint64_t size() const { return End - Start; }
-  uint64_t empty() const { return size() == 0; }
   bool contains(uint64_t Addr) const { return Start <= Addr && Addr < End; }
-  bool contains(const AddressRange &R) const {
-    return Start <= R.Start && R.End <= End;
-  }
   bool intersects(const AddressRange &R) const {
     return Start < R.End && R.Start < End;
   }
@@ -49,163 +45,101 @@ private:
   uint64_t End = 0;
 };
 
-/// The AddressRangesBase class presents the base functionality for the
-/// normalized address ranges collection. This class keeps a sorted vector
-/// of AddressRange-like objects and can perform searches efficiently.
-/// The address ranges are always sorted and never contain any invalid,
-/// empty or intersected address ranges.
-
-template <typename T> class AddressRangesBase {
+/// The AddressRanges class helps normalize address range collections.
+/// This class keeps a sorted vector of AddressRange objects and can perform
+/// insertions and searches efficiently. The address ranges are always sorted
+/// and never contain any invalid or empty address ranges.
+/// Intersecting([100,200), [150,300)) and adjacent([100,200), [200,300))
+/// address ranges are combined during insertion.
+class AddressRanges {
 protected:
-  using Collection = SmallVector<T>;
+  using Collection = SmallVector<AddressRange>;
   Collection Ranges;
 
 public:
   void clear() { Ranges.clear(); }
   bool empty() const { return Ranges.empty(); }
-  bool contains(uint64_t Addr) const {
-    return find(Addr, Addr + 1) != Ranges.end();
-  }
+  bool contains(uint64_t Addr) const { return find(Addr) != Ranges.end(); }
   bool contains(AddressRange Range) const {
-    return find(Range.start(), Range.end()) != Ranges.end();
+    return find(Range) != Ranges.end();
   }
-  void reserve(size_t Capacity) { Ranges.reserve(Capacity); }
-  size_t size() const { return Ranges.size(); }
-
-  std::optional<T> getRangeThatContains(uint64_t Addr) const {
-    typename Collection::const_iterator It = find(Addr, Addr + 1);
+  std::optional<AddressRange> getRangeThatContains(uint64_t Addr) const {
+    Collection::const_iterator It = find(Addr);
     if (It == Ranges.end())
       return std::nullopt;
 
     return *It;
   }
-
-  typename Collection::const_iterator begin() const { return Ranges.begin(); }
-  typename Collection::const_iterator end() const { return Ranges.end(); }
-
-  const T &operator[](size_t i) const {
+  Collection::const_iterator insert(AddressRange Range);
+  void reserve(size_t Capacity) { Ranges.reserve(Capacity); }
+  size_t size() const { return Ranges.size(); }
+  bool operator==(const AddressRanges &RHS) const {
+    return Ranges == RHS.Ranges;
+  }
+  const AddressRange &operator[](size_t i) const {
     assert(i < Ranges.size());
     return Ranges[i];
   }
-
-  bool operator==(const AddressRangesBase<T> &RHS) const {
-    return Ranges == RHS.Ranges;
-  }
+  Collection::const_iterator begin() const { return Ranges.begin(); }
+  Collection::const_iterator end() const { return Ranges.end(); }
 
 protected:
-  typename Collection::const_iterator find(uint64_t Start, uint64_t End) const {
-    if (Start >= End)
-      return Ranges.end();
-
-    auto It =
-        std::partition_point(Ranges.begin(), Ranges.end(), [=](const T &R) {
-          return AddressRange(R).start() <= Start;
-        });
-
-    if (It == Ranges.begin())
-      return Ranges.end();
-
-    --It;
-    if (End > AddressRange(*It).end())
-      return Ranges.end();
-
-    return It;
-  }
+  Collection::const_iterator find(uint64_t Addr) const;
+  Collection::const_iterator find(AddressRange Range) const;
 };
 
-/// The AddressRanges class helps normalize address range collections.
-/// This class keeps a sorted vector of AddressRange objects and can perform
-/// insertions and searches efficiently. Intersecting([100,200), [150,300))
-/// and adjacent([100,200), [200,300)) address ranges are combined during
-/// insertion.
-class AddressRanges : public AddressRangesBase<AddressRange> {
-public:
-  Collection::const_iterator insert(AddressRange Range) {
-    if (Range.empty())
-      return Ranges.end();
-
-    auto It = llvm::upper_bound(Ranges, Range);
-    auto It2 = It;
-    while (It2 != Ranges.end() && It2->start() <= Range.end())
-      ++It2;
-    if (It != It2) {
-      Range = {Range.start(), std::max(Range.end(), std::prev(It2)->end())};
-      It = Ranges.erase(It, It2);
-    }
-    if (It != Ranges.begin() && Range.start() <= std::prev(It)->end()) {
-      --It;
-      *It = {It->start(), std::max(It->end(), Range.end())};
-      return It;
-    }
-
-    return Ranges.insert(It, Range);
-  }
-};
-
-class AddressRangeValuePair {
-public:
-  operator AddressRange() const { return Range; }
-
-  AddressRange Range;
-  int64_t Value = 0;
-};
-
-inline bool operator==(const AddressRangeValuePair &LHS,
-                       const AddressRangeValuePair &RHS) {
-  return LHS.Range == RHS.Range && LHS.Value == RHS.Value;
-}
-
 /// AddressRangesMap class maps values to the address ranges.
-/// It keeps normalized address ranges and corresponding values.
-/// This class keeps a sorted vector of AddressRangeValuePair objects
-/// and can perform insertions and searches efficiently.
-/// Intersecting([100,200), [150,300)) ranges splitted into non-conflicting
-/// parts([100,200), [200,300)). Adjacent([100,200), [200,300)) address
-/// ranges are not combined during insertion.
-class AddressRangesMap : public AddressRangesBase<AddressRangeValuePair> {
+/// It keeps address ranges and corresponding values. If ranges
+/// are combined during insertion, then combined range keeps
+/// newly inserted value.
+template <typename T> class AddressRangesMap : protected AddressRanges {
 public:
-  void insert(AddressRange Range, int64_t Value) {
-    if (Range.empty())
+  void clear() {
+    Ranges.clear();
+    Values.clear();
+  }
+  bool empty() const { return AddressRanges::empty(); }
+  bool contains(uint64_t Addr) const { return AddressRanges::contains(Addr); }
+  bool contains(AddressRange Range) const {
+    return AddressRanges::contains(Range);
+  }
+  void insert(AddressRange Range, T Value) {
+    size_t InputSize = Ranges.size();
+    Collection::const_iterator RangesIt = AddressRanges::insert(Range);
+    if (RangesIt == Ranges.end())
       return;
 
-    // Search for range which is less than or equal incoming Range.
-    auto It = std::partition_point(Ranges.begin(), Ranges.end(),
-                                   [=](const AddressRangeValuePair &R) {
-                                     return R.Range.start() <= Range.start();
-                                   });
-
-    if (It != Ranges.begin())
-      It--;
-
-    while (!Range.empty()) {
-      // Inserted range does not overlap with any range.
-      // Store it into the Ranges collection.
-      if (It == Ranges.end() || Range.end() <= It->Range.start()) {
-        Ranges.insert(It, {Range, Value});
-        return;
-      }
-
-      // Inserted range partially overlaps with current range.
-      // Store not overlapped part of inserted range.
-      if (Range.start() < It->Range.start()) {
-        It = Ranges.insert(It, {{Range.start(), It->Range.start()}, Value});
-        It++;
-        Range = {It->Range.start(), Range.end()};
-        continue;
-      }
-
-      // Inserted range fully overlaps with current range.
-      if (Range.end() <= It->Range.end())
-        return;
-
-      // Inserted range partially overlaps with current range.
-      // Remove overlapped part from the inserted range.
-      if (Range.start() < It->Range.end())
-        Range = {It->Range.end(), Range.end()};
-
-      It++;
-    }
+    // make Values match to Ranges.
+    size_t Idx = RangesIt - Ranges.begin();
+    typename ValuesCollection::iterator ValuesIt = Values.begin() + Idx;
+    if (InputSize < Ranges.size())
+      Values.insert(ValuesIt, T());
+    else if (InputSize > Ranges.size())
+      Values.erase(ValuesIt, ValuesIt + InputSize - Ranges.size());
+    assert(Ranges.size() == Values.size());
+
+    // set value to the inserted or combined range.
+    Values[Idx] = Value;
   }
+  size_t size() const {
+    assert(Ranges.size() == Values.size());
+    return AddressRanges::size();
+  }
+  std::optional<std::pair<AddressRange, T>>
+  getRangeValueThatContains(uint64_t Addr) const {
+    Collection::const_iterator It = find(Addr);
+    if (It == Ranges.end())
+      return std::nullopt;
+
+    return std::make_pair(*It, Values[It - Ranges.begin()]);
+  }
+  std::pair<AddressRange, T> operator[](size_t Idx) const {
+    return std::make_pair(Ranges[Idx], Values[Idx]);
+  }
+
+protected:
+  using ValuesCollection = SmallVector<T>;
+  ValuesCollection Values;
 };
 
 } // namespace llvm
diff --git a/llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h b/llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h
index 9c7f24e69d48..5b0ea339c4d6 100644
--- a/llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h
+++ b/llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h
@@ -21,7 +21,7 @@ class DeclContext;
 
 /// Mapped value in the address map is the offset to apply to the
 /// linked address.
-using RangesTy = AddressRangesMap;
+using RangesTy = AddressRangesMap<int64_t>;
 
 // FIXME: Delete this structure.
 struct PatchLocation {
diff --git a/llvm/lib/DWARFLinker/DWARFLinker.cpp b/llvm/lib/DWARFLinker/DWARFLinker.cpp
index d302d61894fa..9f6e54377ede 100644
--- a/llvm/lib/DWARFLinker/DWARFLinker.cpp
+++ b/llvm/lib/DWARFLinker/DWARFLinker.cpp
@@ -1659,7 +1659,7 @@ void DWARFLinker::patchRangesForUnit(const CompileUnit &Unit,
   DWARFDataExtractor RangeExtractor(OrigDwarf.getDWARFObj(),
                                     OrigDwarf.getDWARFObj().getRangesSection(),
                                     OrigDwarf.isLittleEndian(), AddressSize);
-  std::optional<AddressRangeValuePair> CachedRange;
+  std::optional<std::pair<AddressRange, int64_t>> CachedRange;
   DWARFUnit &OrigUnit = Unit.getOrigUnit();
   auto OrigUnitDie = OrigUnit.getUnitDIE(false);
   uint64_t UnitBaseAddress =
@@ -1687,9 +1687,9 @@ void DWARFLinker::patchRangesForUnit(const CompileUnit &Unit,
         }
 
         if (!CachedRange ||
-            !CachedRange->Range.contains(Range.StartAddress + BaseAddress))
-          CachedRange = FunctionRanges.getRangeThatContains(Range.StartAddress +
-                                                            BaseAddress);
+            !CachedRange->first.contains(Range.StartAddress + BaseAddress))
+          CachedRange = FunctionRanges.getRangeValueThatContains(
+              Range.StartAddress + BaseAddress);
 
         // All range entries should lie in the function range.
         if (!CachedRange) {
@@ -1698,8 +1698,8 @@ void DWARFLinker::patchRangesForUnit(const CompileUnit &Unit,
         }
 
         LinkedRanges.insert(
-            {Range.StartAddress + BaseAddress + CachedRange->Value,
-             Range.EndAddress + BaseAddress + CachedRange->Value});
+            {Range.StartAddress + BaseAddress + CachedRange->second,
+             Range.EndAddress + BaseAddress + CachedRange->second});
       }
     }
 
@@ -1802,7 +1802,7 @@ void DWARFLinker::patchLineTableForUnit(CompileUnit &Unit,
   // in NewRows.
   std::vector<DWARFDebugLine::Row> Seq;
   const auto &FunctionRanges = Unit.getFunctionRanges();
-  std::optional<AddressRangeValuePair> CurrRange;
+  std::optional<std::pair<AddressRange, int64_t>> CurrRange;
 
   // FIXME: This logic is meant to generate exactly the same output as
   // Darwin's classic dsymutil. There is a nicer way to implement this
@@ -1821,13 +1821,13 @@ void DWARFLinker::patchLineTableForUnit(CompileUnit &Unit,
     // it is marked as end_sequence in the input (because in that
     // case, the relocation offset is accurate and that entry won't
     // serve as the start of another function).
-    if (!CurrRange || !CurrRange->Range.contains(Row.Address.Address) ||
-        (Row.Address.Address == CurrRange->Range.end() && !Row.EndSequence)) {
+    if (!CurrRange || !CurrRange->first.contains(Row.Address.Address) ||
+        (Row.Address.Address == CurrRange->first.end() && !Row.EndSequence)) {
       // We just stepped out of a known range. Insert a end_sequence
       // corresponding to the end of the range.
       uint64_t StopAddress =
-          CurrRange ? CurrRange->Range.end() + CurrRange->Value : -1ULL;
-      CurrRange = FunctionRanges.getRangeThatContains(Row.Address.Address);
+          CurrRange ? CurrRange->first.end() + CurrRange->second : -1ULL;
+      CurrRange = FunctionRanges.getRangeValueThatContains(Row.Address.Address);
       if (!CurrRange) {
         if (StopAddress != -1ULL) {
           // Try harder by looking in the Address ranges map.
@@ -1836,9 +1836,9 @@ void DWARFLinker::patchLineTableForUnit(CompileUnit &Unit,
           // for now do as dsymutil.
           // FIXME: Understand exactly what cases this addresses and
           // potentially remove it along with the Ranges map.
-          if (std::optional<AddressRangeValuePair> Range =
-                  Ranges.getRangeThatContains(Row.Address.Address))
-            StopAddress = Row.Address.Address + (*Range).Value;
+          if (std::optional<std::pair<AddressRange, int64_t>> Range =
+                  Ranges.getRangeValueThatContains(Row.Address.Address))
+            StopAddress = Row.Address.Address + (*Range).second;
         }
       }
       if (StopAddress != -1ULL && !Seq.empty()) {
@@ -1863,7 +1863,7 @@ void DWARFLinker::patchLineTableForUnit(CompileUnit &Unit,
       continue;
 
     // Relocate row address and add it to the current sequence.
-    Row.Address.Address += CurrRange->Value;
+    Row.Address.Address += CurrRange->second;
     Seq.emplace_back(Row);
 
     if (Row.EndSequence)
@@ -2002,8 +2002,8 @@ void DWARFLinker::patchFrameInfoForObject(const DWARFFile &File,
     // the function entry point, thus we can't just lookup the address
     // in the debug map. Use the AddressInfo's range map to see if the FDE
     // describes something that we can relocate.
-    std::optional<AddressRangeValuePair> Range =
-        Ranges.getRangeThatContains(Loc);
+    std::optional<std::pair<AddressRange, int64_t>> Range =
+        Ranges.getRangeValueThatContains(Loc);
     if (!Range) {
       // The +4 is to account for the size of the InitialLength field itself.
       InputOffset = EntryOffset + InitialLength + 4;
@@ -2032,7 +2032,7 @@ void DWARFLinker::patchFrameInfoForObject(const DWARFFile &File,
     // fields that will get reconstructed by emitFDE().
     unsigned FDERemainingBytes = InitialLength - (4 + AddrSize);
     TheDwarfEmitter->emitFDE(IteratorInserted.first->getValue(), AddrSize,
-                             Loc + Range->Value,
+                             Loc + Range->second,
                              FrameData.substr(InputOffset, FDERemainingBytes));
     InputOffset += FDERemainingBytes;
   }
diff --git a/llvm/lib/DWARFLinker/DWARFStreamer.cpp b/llvm/lib/DWARFLinker/DWARFStreamer.cpp
index ae79e8cb9066..5cad267fd845 100644
--- a/llvm/lib/DWARFLinker/DWARFStreamer.cpp
+++ b/llvm/lib/DWARFLinker/DWARFStreamer.cpp
@@ -402,9 +402,10 @@ void DwarfStreamer::emitUnitRangesEntries(CompileUnit &Unit,
   // Linked addresses might end up in a different order.
   // Build linked address ranges.
   AddressRanges LinkedRanges;
-  for (const AddressRangeValuePair &Range : FunctionRanges)
+  for (size_t Idx = 0; Idx < FunctionRanges.size(); Idx++)
     LinkedRanges.insert(
-        {Range.Range.start() + Range.Value, Range.Range.end() + Range.Value});
+        {FunctionRanges[Idx].first.start() + FunctionRanges[Idx].second,
+         FunctionRanges[Idx].first.end() + FunctionRanges[Idx].second});
 
   if (!FunctionRanges.empty())
     emitDwarfDebugArangesTable(Unit, LinkedRanges);
diff --git a/llvm/lib/Support/AddressRanges.cpp b/llvm/lib/Support/AddressRanges.cpp
new file mode 100644
index 000000000000..187d5be00dae
--- /dev/null
+++ b/llvm/lib/Support/AddressRanges.cpp
@@ -0,0 +1,70 @@
+//===- AddressRanges.cpp ----------------------------------------*- C++ -*-===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+
+#include "llvm/ADT/AddressRanges.h"
+#include "llvm/ADT/STLExtras.h"
+#include <inttypes.h>
+
+using namespace llvm;
+
+AddressRanges::Collection::const_iterator
+AddressRanges::insert(AddressRange Range) {
+  if (Range.size() == 0)
+    return Ranges.end();
+
+  auto It = llvm::upper_bound(Ranges, Range);
+  auto It2 = It;
+  while (It2 != Ranges.end() && It2->start() <= Range.end())
+    ++It2;
+  if (It != It2) {
+    Range = {Range.start(), std::max(Range.end(), std::prev(It2)->end())};
+    It = Ranges.erase(It, It2);
+  }
+  if (It != Ranges.begin() && Range.start() <= std::prev(It)->end()) {
+    --It;
+    *It = {It->start(), std::max(It->end(), Range.end())};
+    return It;
+  }
+
+  return Ranges.insert(It, Range);
+}
+
+AddressRanges::Collection::const_iterator
+AddressRanges::find(uint64_t Addr) const {
+  auto It = std::partition_point(
+      Ranges.begin(), Ranges.end(),
+      [=](const AddressRange &R) { return R.start() <= Addr; });
+
+  if (It == Ranges.begin())
+    return Ranges.end();
+
+  --It;
+  if (Addr >= It->end())
+    return Ranges.end();
+
+  return It;
+}
+
+AddressRanges::Collection::const_iterator
+AddressRanges::find(AddressRange Range) const {
+  if (Range.size() == 0)
+    return Ranges.end();
+
+  auto It = std::partition_point(
+      Ranges.begin(), Ranges.end(),
+      [=](const AddressRange &R) { return R.start() <= Range.start(); });
+
+  if (It == Ranges.begin())
+    return Ranges.end();
+
+  --It;
+  if (Range.end() > It->end())
+    return Ranges.end();
+
+  return It;
+}
diff --git a/llvm/lib/Support/CMakeLists.txt b/llvm/lib/Support/CMakeLists.txt
index 8fbb2ca4c164..4cbc3b79f3bb 100644
--- a/llvm/lib/Support/CMakeLists.txt
+++ b/llvm/lib/Support/CMakeLists.txt
@@ -117,6 +117,7 @@ endif()
 add_subdirectory(BLAKE3)
 
 add_llvm_component_library(LLVMSupport
+  AddressRanges.cpp
   ABIBreak.cpp
   AMDGPUMetadata.cpp
   APFixedPoint.cpp
diff --git a/llvm/unittests/Support/AddressRangeTest.cpp b/llvm/unittests/Support/AddressRangeTest.cpp
index 06b326678402..468f1e22ffa8 100644
--- a/llvm/unittests/Support/AddressRangeTest.cpp
+++ b/llvm/unittests/Support/AddressRangeTest.cpp
@@ -149,31 +149,8 @@ TEST(AddressRangeTest, TestRanges) {
   EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x5000));
 }
 
-TEST(AddressRangeTest, TestRangesRandom) {
-  AddressRanges Ranges;
-  size_t NumElements = 100;
-
-  std::srand(std::time(nullptr));
-
-  // Fill ranges.
-  for (size_t Idx = 0; Idx < NumElements; Idx++) {
-    uint64_t Start = static_cast<uint64_t>(std::rand() % 1000);
-    uint64_t End = Start + static_cast<uint64_t>(std::rand() % 1000);
-    Ranges.insert({Start, End});
-  }
-
-  // Check ranges.
-  for (size_t Idx = 0; Idx + 1 < Ranges.size(); Idx++) {
-    // Check that ranges are not intersected.
-    EXPECT_FALSE(Ranges[Idx].intersects(Ranges[Idx + 1]));
-
-    // Check that ranges are sorted and not adjusted.
-    EXPECT_TRUE(Ranges[Idx].end() < Ranges[Idx + 1].start());
-  }
-}
-
 TEST(AddressRangeTest, TestRangesMap) {
-  AddressRangesMap Ranges;
+  AddressRangesMap<int> Ranges;
 
   EXPECT_EQ(Ranges.size(), 0u);
   EXPECT_TRUE(Ranges.empty());
@@ -185,247 +162,73 @@ TEST(AddressRangeTest, TestRangesMap) {
   EXPECT_TRUE(Ranges.contains(0x1500));
   EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x2000)));
 
-  ///////////////////////////////////////
-  /// Check ranges with the same mapped value.
-
-  // Clear ranges.
-  Ranges.clear();
-  EXPECT_EQ(Ranges.size(), 0u);
-  EXPECT_TRUE(Ranges.empty());
-
-  // Add range and check mapped value.
-  Ranges.insert(AddressRange(0x1000, 0x2000), 0x11);
-  EXPECT_EQ(Ranges.size(), 1u);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0x11);
-
-  // Add adjacent range and check mapped value.
-  Ranges.insert(AddressRange(0x2000, 0x3000), 0x11);
-  EXPECT_EQ(Ranges.size(), 2u);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0x11);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x2000)->Value, 0x11);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x2900)->Value, 0x11);
-  EXPECT_FALSE(Ranges.getRangeThatContains(0x3000));
-
-  // Add intersecting range and check mapped value.
-  Ranges.insert(AddressRange(0x1000, 0x3000), 0x11);
-  EXPECT_EQ(Ranges.size(), 2u);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0x11);
-
-  // Add second range and check mapped values.
-  Ranges.insert(AddressRange(0x4000, 0x5000), 0x11);
-  EXPECT_EQ(Ranges.size(), 3u);
-  EXPECT_EQ(Ranges[0].Range, AddressRange(0x1000, 0x2000));
-  EXPECT_EQ(Ranges[0].Value, 0x11);
-  EXPECT_EQ(Ranges[1].Range, AddressRange(0x2000, 0x3000));
-  EXPECT_EQ(Ranges[1].Value, 0x11);
-  EXPECT_EQ(Ranges[2].Range, AddressRange(0x4000, 0x5000));
-  EXPECT_EQ(Ranges[2].Value, 0x11);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0x11);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x4000)->Value, 0x11);
-
-  // Add intersecting range and check mapped value.
-  Ranges.insert(AddressRange(0x0, 0x6000), 0x11);
-  EXPECT_EQ(Ranges.size(), 6u);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0x11);
-
-  // Check that mapped values are correctly preserved for combined ranges.
-  Ranges.clear();
-  Ranges.insert(AddressRange(0x0, 0xff), 0x11);
-  Ranges.insert(AddressRange(0x100, 0x1ff), 0x11);
-  Ranges.insert(AddressRange(0x200, 0x2ff), 0x11);
-  Ranges.insert(AddressRange(0x500, 0x5ff), 0x11);
-  Ranges.insert(AddressRange(0x300, 0x3ff), 0x11);
-  Ranges.insert(AddressRange(0x400, 0x4ff), 0x11);
-  Ranges.insert(AddressRange(0x600, 0x6ff), 0x11);
-  EXPECT_EQ(Ranges.size(), 7u);
-
-  Ranges.insert(AddressRange(0x150, 0x350), 0x11);
-  EXPECT_EQ(Ranges.size(), 9u);
-  EXPECT_EQ(Ranges[0].Range, AddressRange(0x0, 0xff));
-  EXPECT_EQ(Ranges[0].Value, 0x11);
-  EXPECT_EQ(Ranges[1].Range, AddressRange(0x100, 0x1ff));
-  EXPECT_EQ(Ranges[1].Value, 0x11);
-  EXPECT_EQ(Ranges[2].Range, AddressRange(0x1ff, 0x200));
-  EXPECT_EQ(Ranges[2].Value, 0x11);
-  EXPECT_EQ(Ranges[3].Range, AddressRange(0x200, 0x2ff));
-  EXPECT_EQ(Ranges[3].Value, 0x11);
-  EXPECT_EQ(Ranges[4].Range, AddressRange(0x2ff, 0x300));
-  EXPECT_EQ(Ranges[4].Value, 0x11);
-  EXPECT_EQ(Ranges[5].Range, AddressRange(0x300, 0x3ff));
-  EXPECT_EQ(Ranges[5].Value, 0x11);
-  EXPECT_EQ(Ranges[6].Range, AddressRange(0x400, 0x4ff));
-  EXPECT_EQ(Ranges[6].Value, 0x11);
-  EXPECT_EQ(Ranges[7].Range, AddressRange(0x500, 0x5ff));
-  EXPECT_EQ(Ranges[7].Value, 0x11);
-  EXPECT_EQ(Ranges[8].Range, AddressRange(0x600, 0x6ff));
-  EXPECT_EQ(Ranges[8].Value, 0x11);
-
-  Ranges.insert(AddressRange(0x3ff, 0x400), 0x11);
-  EXPECT_EQ(Ranges.size(), 10u);
-  EXPECT_EQ(Ranges[0].Range, AddressRange(0x0, 0xff));
-  EXPECT_EQ(Ranges[0].Value, 0x11);
-  EXPECT_EQ(Ranges[1].Range, AddressRange(0x100, 0x1ff));
-  EXPECT_EQ(Ranges[1].Value, 0x11);
-  EXPECT_EQ(Ranges[2].Range, AddressRange(0x1ff, 0x200));
-  EXPECT_EQ(Ranges[2].Value, 0x11);
-  EXPECT_EQ(Ranges[3].Range, AddressRange(0x200, 0x2ff));
-  EXPECT_EQ(Ranges[3].Value, 0x11);
-  EXPECT_EQ(Ranges[4].Range, AddressRange(0x2ff, 0x300));
-  EXPECT_EQ(Ranges[4].Value, 0x11);
-  EXPECT_EQ(Ranges[5].Range, AddressRange(0x300, 0x3ff));
-  EXPECT_EQ(Ranges[5].Value, 0x11);
-  EXPECT_EQ(Ranges[6].Range, AddressRange(0x3ff, 0x400));
-  EXPECT_EQ(Ranges[6].Value, 0x11);
-  EXPECT_EQ(Ranges[7].Range, AddressRange(0x400, 0x4ff));
-  EXPECT_EQ(Ranges[7].Value, 0x11);
-  EXPECT_EQ(Ranges[8].Range, AddressRange(0x500, 0x5ff));
-  EXPECT_EQ(Ranges[8].Value, 0x11);
-  EXPECT_EQ(Ranges[9].Range, AddressRange(0x600, 0x6ff));
-  EXPECT_EQ(Ranges[9].Value, 0x11);
-
-  /////////////////////////////////////////////
-  /// Check ranges with various mapped values.
-
   // Clear ranges.
   Ranges.clear();
   EXPECT_EQ(Ranges.size(), 0u);
   EXPECT_TRUE(Ranges.empty());
 
-  // Add range and check mapped value.
+  // Add range and check value.
   Ranges.insert(AddressRange(0x1000, 0x2000), 0xfe);
   EXPECT_EQ(Ranges.size(), 1u);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0xfe);
+  EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0xfe);
 
-  // Add adjacent range and check mapped value.
+  // Add adjacent range and check value.
   Ranges.insert(AddressRange(0x2000, 0x3000), 0xfc);
-  EXPECT_EQ(Ranges.size(), 2u);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0xfe);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x2000)->Value, 0xfc);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x2900)->Value, 0xfc);
-  EXPECT_FALSE(Ranges.getRangeThatContains(0x3000));
+  EXPECT_EQ(Ranges.size(), 1u);
+  EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0xfc);
+  EXPECT_EQ(Ranges.getRangeValueThatContains(0x2000)->second, 0xfc);
+  EXPECT_EQ(Ranges.getRangeValueThatContains(0x2900)->second, 0xfc);
+  EXPECT_FALSE(Ranges.getRangeValueThatContains(0x3000));
 
-  // Add intersecting range and check mapped value.
-  Ranges.insert(AddressRange(0x1000, 0x3000), 0xff);
-  EXPECT_EQ(Ranges.size(), 2u);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0xfe);
+  // Add intersecting range and check value.
+  Ranges.insert(AddressRange(0x2000, 0x3000), 0xff);
+  EXPECT_EQ(Ranges.size(), 1u);
+  EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0xff);
 
-  // Add one more range and check mapped values.
+  // Add second range and check values.
   Ranges.insert(AddressRange(0x4000, 0x5000), 0x0);
-  EXPECT_EQ(Ranges.size(), 3u);
-  EXPECT_EQ(Ranges[0].Value, 0xfe);
-  EXPECT_EQ(Ranges[1].Value, 0xfc);
-  EXPECT_EQ(Ranges[2].Value, 0x0);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0xfe);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x4000)->Value, 0x0);
+  EXPECT_EQ(Ranges.size(), 2u);
+  EXPECT_EQ(Ranges[0].second, 0xff);
+  EXPECT_EQ(Ranges[1].second, 0x0);
+  EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0xff);
+  EXPECT_EQ(Ranges.getRangeValueThatContains(0x4000)->second, 0x0);
 
-  // Add intersecting range and check mapped value.
+  // Add intersecting range and check value.
   Ranges.insert(AddressRange(0x0, 0x6000), 0x1);
-  EXPECT_EQ(Ranges.size(), 6u);
-  EXPECT_EQ(Ranges[0].Value, 0x1);
-  EXPECT_EQ(Ranges[1].Value, 0xfe);
-  EXPECT_EQ(Ranges[2].Value, 0xfc);
-  EXPECT_EQ(Ranges[3].Value, 0x1);
-  EXPECT_EQ(Ranges[4].Value, 0x0);
-  EXPECT_EQ(Ranges[5].Value, 0x1);
-  EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0xfe);
+  EXPECT_EQ(Ranges.size(), 1u);
+  EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0x1);
 
-  // Check that mapped values are correctly preserved for combined ranges.
+  // Check that values are correctly preserved for combined ranges.
   Ranges.clear();
   Ranges.insert(AddressRange(0x0, 0xff), 0x1);
   Ranges.insert(AddressRange(0x100, 0x1ff), 0x2);
   Ranges.insert(AddressRange(0x200, 0x2ff), 0x3);
   Ranges.insert(AddressRange(0x300, 0x3ff), 0x4);
-  Ranges.insert(AddressRange(0x500, 0x5ff), 0x6);
   Ranges.insert(AddressRange(0x400, 0x4ff), 0x5);
+  Ranges.insert(AddressRange(0x500, 0x5ff), 0x6);
   Ranges.insert(AddressRange(0x600, 0x6ff), 0x7);
-  EXPECT_EQ(Ranges.size(), 7u);
 
   Ranges.insert(AddressRange(0x150, 0x350), 0xff);
-  EXPECT_EQ(Ranges.size(), 9u);
-  EXPECT_EQ(Ranges[0].Range, AddressRange(0x0, 0xff));
-  EXPECT_EQ(Ranges[0].Value, 0x1);
-  EXPECT_EQ(Ranges[1].Range, AddressRange(0x100, 0x1ff));
-  EXPECT_EQ(Ranges[1].Value, 0x2);
-  EXPECT_EQ(Ranges[2].Range, AddressRange(0x1ff, 0x200));
-  EXPECT_EQ(Ranges[2].Value, 0xff);
-  EXPECT_EQ(Ranges[3].Range, AddressRange(0x200, 0x2ff));
-  EXPECT_EQ(Ranges[3].Value, 0x3);
-  EXPECT_EQ(Ranges[4].Range, AddressRange(0x2ff, 0x300));
-  EXPECT_EQ(Ranges[4].Value, 0xff);
-  EXPECT_EQ(Ranges[5].Range, AddressRange(0x300, 0x3ff));
-  EXPECT_EQ(Ranges[5].Value, 0x4);
-  EXPECT_EQ(Ranges[6].Range, AddressRange(0x400, 0x4ff));
-  EXPECT_EQ(Ranges[6].Value, 0x5);
-  EXPECT_EQ(Ranges[7].Range, AddressRange(0x500, 0x5ff));
-  EXPECT_EQ(Ranges[7].Value, 0x6);
-  EXPECT_EQ(Ranges[8].Range, AddressRange(0x600, 0x6ff));
-  EXPECT_EQ(Ranges[8].Value, 0x7);
+  EXPECT_EQ(Ranges.size(), 5u);
+  EXPECT_EQ(Ranges[0].first, AddressRange(0x0, 0xff));
+  EXPECT_EQ(Ranges[0].second, 0x1);
+  EXPECT_EQ(Ranges[1].first, AddressRange(0x100, 0x3ff));
+  EXPECT_EQ(Ranges[1].second, 0xff);
+  EXPECT_EQ(Ranges[2].first, AddressRange(0x400, 0x4ff));
+  EXPECT_EQ(Ranges[2].second, 0x5);
+  EXPECT_EQ(Ranges[3].first, AddressRange(0x500, 0x5ff));
+  EXPECT_EQ(Ranges[3].second, 0x6);
+  EXPECT_EQ(Ranges[4].first, AddressRange(0x600, 0x6ff));
+  EXPECT_EQ(Ranges[4].second, 0x7);
 
-  Ranges.insert(AddressRange(0x650, 0x700), 0x8);
   Ranges.insert(AddressRange(0x3ff, 0x400), 0x5);
-  Ranges.insert(AddressRange(0x0, 0x40), 0xee);
-  EXPECT_EQ(Ranges.size(), 11u);
-  EXPECT_EQ(Ranges[0].Range, AddressRange(0x0, 0xff));
-  EXPECT_EQ(Ranges[0].Value, 0x1);
-  EXPECT_EQ(Ranges[1].Range, AddressRange(0x100, 0x1ff));
-  EXPECT_EQ(Ranges[1].Value, 0x2);
-  EXPECT_EQ(Ranges[2].Range, AddressRange(0x1ff, 0x200));
-  EXPECT_EQ(Ranges[2].Value, 0xff);
-  EXPECT_EQ(Ranges[3].Range, AddressRange(0x200, 0x2ff));
-  EXPECT_EQ(Ranges[3].Value, 0x3);
-  EXPECT_EQ(Ranges[4].Range, AddressRange(0x2ff, 0x300));
-  EXPECT_EQ(Ranges[4].Value, 0xff);
-  EXPECT_EQ(Ranges[5].Range, AddressRange(0x300, 0x3ff));
-  EXPECT_EQ(Ranges[5].Value, 0x4);
-  EXPECT_EQ(Ranges[6].Range, AddressRange(0x3ff, 0x400));
-  EXPECT_EQ(Ranges[6].Value, 0x5);
-  EXPECT_EQ(Ranges[7].Range, AddressRange(0x400, 0x4ff));
-  EXPECT_EQ(Ranges[7].Value, 0x5);
-  EXPECT_EQ(Ranges[8].Range, AddressRange(0x500, 0x5ff));
-  EXPECT_EQ(Ranges[8].Value, 0x6);
-  EXPECT_EQ(Ranges[9].Range, AddressRange(0x600, 0x6ff));
-  EXPECT_EQ(Ranges[9].Value, 0x7);
-  EXPECT_EQ(Ranges[10].Range, AddressRange(0x6ff, 0x700));
-  EXPECT_EQ(Ranges[10].Value, 0x8);
-}
-
-TEST(AddressRangeTest, TestRangesMapRandom) {
-  AddressRangesMap Ranges;
-  size_t NumElements = 100;
-
-  std::srand(std::time(nullptr));
-
-  // Fill ranges. Use the same mapped value.
-  for (size_t Idx = 0; Idx < NumElements; Idx++) {
-    uint64_t Start = static_cast<uint64_t>(std::rand() % 1000);
-    uint64_t End = Start + static_cast<uint64_t>(std::rand() % 1000);
-    Ranges.insert({Start, End}, 0xffLL);
-  }
-
-  // Check ranges.
-  for (size_t Idx = 0; Idx + 1 < Ranges.size(); Idx++) {
-    // Check that ranges are not intersected.
-    EXPECT_FALSE(Ranges[Idx].Range.intersects(Ranges[Idx + 1].Range));
-
-    // Check that ranges are sorted and not adjusted.
-    EXPECT_TRUE(Ranges[Idx].Range.end() <= Ranges[Idx + 1].Range.start());
-  }
-
-  Ranges.clear();
-  // Fill ranges. Use the various mapped value.
-  for (size_t Idx = 0; Idx < NumElements; Idx++) {
-    uint64_t Start = static_cast<uint64_t>(std::rand() % 1000);
-    uint64_t End = Start + static_cast<uint64_t>(std::rand() % 1000);
-    int64_t Value = static_cast<int64_t>(std::rand() % 10);
-    Ranges.insert({Start, End}, Value);
-  }
-
-  // Check ranges.
-  for (size_t Idx = 0; Idx + 1 < Ranges.size(); Idx++) {
-    // Check that ranges are not intersected.
-    EXPECT_FALSE(Ranges[Idx].Range.intersects(Ranges[Idx + 1].Range));
-
-    // Check that ranges are sorted and not adjusted.
-    EXPECT_TRUE(Ranges[Idx].Range.end() <= Ranges[Idx + 1].Range.start());
-  }
+  EXPECT_EQ(Ranges.size(), 4u);
+  EXPECT_EQ(Ranges[0].first, AddressRange(0x0, 0xff));
+  EXPECT_EQ(Ranges[0].second, 0x1);
+  EXPECT_EQ(Ranges[1].first, AddressRange(0x100, 0x4ff));
+  EXPECT_EQ(Ranges[1].second, 0x5);
+  EXPECT_EQ(Ranges[2].first, AddressRange(0x500, 0x5ff));
+  EXPECT_EQ(Ranges[2].second, 0x6);
+  EXPECT_EQ(Ranges[3].first, AddressRange(0x600, 0x6ff));
+  EXPECT_EQ(Ranges[3].second, 0x7);
 }