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

[avl]

Summary

This patch fixes #60307 issue. The 8bb4451 introduces the possibility
to unite overlapped or adjacent address ranges to keep address ranges
in an unambiguous state. The AddressRangesMap is used to normalize
address ranges. The AddressRangesMap keeps address ranges and the value
of the relocated address. For intersected range, it creates a united
range that keeps the last inserted mapping value. The same for adjusted ranges.
While it is OK to use the last inserted mapping value for intersected ranges
(as there is no way how to resolve ambiguity) It is not OK to use the
last inserted value for adjacent address ranges. Currently, two following
address ranges are united into a single one:

{0,24,17e685c} {24,d8,55afe20} -> {0,d8,55afe20}

To avoid the problem, the AddressRangesMap should not unite adjacent address ranges
with different relocated addresses. Instead, it should leave adjacent address ranges
as separate ranges. So, the ranges should look like this:

{0,24,17e685c} {24,d8,55afe20}

[avl]

https://github.com/llvm/llvm-project/issues/60307

[avl]

simplified AddressRangesMap::insert().

[JDevlieghere]

I didn't check the insertion logic in detail but I'm fairly confident it's correct given the test coverage. LGTM.

llvm/include/llvm/ADT/AddressRanges.h

124

llvm/include/llvm/ADT/AddressRanges.h

 public:
   AddressRange() {}
   AddressRange(uint64_t S, uint64_t E) : Start(S), End(E) {
     assert(Start <= End);
   }
   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;
   }
   bool operator==(const AddressRange &R) const {
     return Start == R.Start && End == R.End;
   }
   bool operator!=(const AddressRange &R) const { return !(*this == R); }
   bool operator<(const AddressRange &R) const {
     return std::make_pair(Start, End) < std::make_pair(R.Start, R.End);
   }
 
 private:
   uint64_t Start = 0;
   uint64_t End = 0;
 };
 
-/// 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 {
+/// 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 {
 protected:
-  using Collection = SmallVector<AddressRange>;
+  using Collection = SmallVector<T>;
   Collection Ranges;
 
 public:
   void clear() { Ranges.clear(); }
   bool empty() const { return Ranges.empty(); }
-  bool contains(uint64_t Addr) const { return find(Addr) != Ranges.end(); }
+  bool contains(uint64_t Addr) const {
+    return find(Addr, Addr + 1) != Ranges.end();
+  }
   bool contains(AddressRange Range) const {
-    return find(Range) != Ranges.end();
+    return find(Range.start(), Range.end()) != Ranges.end();
   }
-  std::optional<AddressRange> getRangeThatContains(uint64_t Addr) const {
-    Collection::const_iterator It = find(Addr);
+  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);
     if (It == Ranges.end())
       return std::nullopt;
 
     return *It;
   }
-  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 {
+
+  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 {
     assert(i < Ranges.size());
     return Ranges[i];
   }
-  Collection::const_iterator begin() const { return Ranges.begin(); }
-  Collection::const_iterator end() const { return Ranges.end(); }
+
+  bool operator==(const AddressRangesBase<T> &RHS) const {
+    return Ranges == RHS.Ranges;
+  }
 
 protected:
-  Collection::const_iterator find(uint64_t Addr) const;
-  Collection::const_iterator find(AddressRange Range) const;
+  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;
+  }
 };
 
+/// 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.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);
+  }
+};
+
+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 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 {
+/// 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> {
 public:
-  void clear() {
-    Ranges.clear();
-    Values.clear();
+  void insert(AddressRange Range, int64_t Value) {
+    if (Range.empty())
+      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;
       }
-  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);
+
+      // 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;
       }
-  void insert(AddressRange Range, T Value) {
-    size_t InputSize = Ranges.size();
-    Collection::const_iterator RangesIt = AddressRanges::insert(Range);
-    if (RangesIt == Ranges.end())
+
+      // Inserted range fully overlaps with current range.
+      if (Range.end() <= It->Range.end())
         return;
 
-    // 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;
+      // 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()};
 
-    return std::make_pair(*It, Values[It - Ranges.begin()]);
+      It++;
     }
-  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
 
 #endif // LLVM_ADT_ADDRESSRANGES_H

llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h

 #include <optional>
 
 namespace llvm {
 
 class DeclContext;
 
 /// Mapped value in the address map is the offset to apply to the
 /// linked address.
-using RangesTy = AddressRangesMap<int64_t>;
+using RangesTy = AddressRangesMap;
 
 // FIXME: Delete this structure.
 struct PatchLocation {
   DIE::value_iterator I;
 
   PatchLocation() = default;
   PatchLocation(DIE::value_iterator I) : I(I) {}
 

llvm/lib/DWARFLinker/DWARFLinker.cpp

void DWARFLinker::patchRangesForUnit(const CompileUnit &Unit,
                                      DWARFContext &OrigDwarf,
                                      const DWARFFile &File) const {
   DWARFDebugRangeList RangeList;
   const auto &FunctionRanges = Unit.getFunctionRanges();
   unsigned AddressSize = Unit.getOrigUnit().getAddressByteSize();
   DWARFDataExtractor RangeExtractor(OrigDwarf.getDWARFObj(),
                                     OrigDwarf.getDWARFObj().getRangesSection(),
                                     OrigDwarf.isLittleEndian(), AddressSize);
-  std::optional<std::pair<AddressRange, int64_t>> CachedRange;
+  std::optional<AddressRangeValuePair> CachedRange;
   DWARFUnit &OrigUnit = Unit.getOrigUnit();
   auto OrigUnitDie = OrigUnit.getUnitDIE(false);
   uint64_t UnitBaseAddress =
       dwarf::toAddress(OrigUnitDie.find(dwarf::DW_AT_low_pc), 0);
 
   for (const auto &RangeAttribute : Unit.getRangesAttributes()) {
     uint64_t Offset = RangeAttribute.get();
     RangeAttribute.set(TheDwarfEmitter->getRangesSectionSize());
if (!Entries.empty()) {
       for (const auto &Range : Entries) {
         if (Range.isBaseAddressSelectionEntry(
                 Unit.getOrigUnit().getAddressByteSize())) {
           BaseAddress = Range.EndAddress;
           continue;
         }
 
         if (!CachedRange ||
-            !CachedRange->first.contains(Range.StartAddress + BaseAddress))
-          CachedRange = FunctionRanges.getRangeValueThatContains(
-              Range.StartAddress + BaseAddress);
+            !CachedRange->Range.contains(Range.StartAddress + BaseAddress))
+          CachedRange = FunctionRanges.getRangeThatContains(Range.StartAddress +
+                                                            BaseAddress);
 
         // All range entries should lie in the function range.
         if (!CachedRange) {
           reportWarning("inconsistent range data.", File);
           continue;
         }
 
         LinkedRanges.insert(
-            {Range.StartAddress + BaseAddress + CachedRange->second,
-             Range.EndAddress + BaseAddress + CachedRange->second});
+            {Range.StartAddress + BaseAddress + CachedRange->Value,
+             Range.EndAddress + BaseAddress + CachedRange->Value});
       }
     }
 
     TheDwarfEmitter->emitDwarfDebugRangesTableFragment(Unit, LinkedRanges);
   }
 }
 
 /// Generate the debug_aranges entries for \p Unit and if the
void DWARFLinker::patchLineTableForUnit(CompileUnit &Unit,
   // This vector is the output line table.
   std::vector<DWARFDebugLine::Row> NewRows;
   NewRows.reserve(LineTable.Rows.size());
 
   // Current sequence of rows being extracted, before being inserted
   // in NewRows.
   std::vector<DWARFDebugLine::Row> Seq;
   const auto &FunctionRanges = Unit.getFunctionRanges();
-  std::optional<std::pair<AddressRange, int64_t>> CurrRange;
+  std::optional<AddressRangeValuePair> 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
   // by simply putting all the relocated line info in NewRows and simply
   // sorting NewRows before passing it to emitLineTableForUnit. This
   // should be correct as sequences for a function should stay
   // together in the sorted output. There are a few corner cases that
   // look suspicious though, and that required to implement the logic
   // this way. Revisit that once initial validation is finished.
 
   // Iterate over the object file line info and extract the sequences
   // that correspond to linked functions.
   for (auto &Row : LineTable.Rows) {
     // Check whether we stepped out of the range. The range is
     // half-open, but consider accept the end address of the range if
     // 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->first.contains(Row.Address.Address) ||
-        (Row.Address.Address == CurrRange->first.end() && !Row.EndSequence)) {
+    if (!CurrRange || !CurrRange->Range.contains(Row.Address.Address) ||
+        (Row.Address.Address == CurrRange->Range.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->first.end() + CurrRange->second : -1ULL;
-      CurrRange = FunctionRanges.getRangeValueThatContains(Row.Address.Address);
+          CurrRange ? CurrRange->Range.end() + CurrRange->Value : -1ULL;
+      CurrRange = FunctionRanges.getRangeThatContains(Row.Address.Address);
       if (!CurrRange) {
         if (StopAddress != -1ULL) {
           // Try harder by looking in the Address ranges map.
           // There are corner cases where this finds a
           // valid entry. It's unclear if this is right or wrong, but
           // for now do as dsymutil.
           // FIXME: Understand exactly what cases this addresses and
           // potentially remove it along with the Ranges map.
-          if (std::optional<std::pair<AddressRange, int64_t>> Range =
-                  Ranges.getRangeValueThatContains(Row.Address.Address))
-            StopAddress = Row.Address.Address + (*Range).second;
+          if (std::optional<AddressRangeValuePair> Range =
+                  Ranges.getRangeThatContains(Row.Address.Address))
+            StopAddress = Row.Address.Address + (*Range).Value;
         }
       }
       if (StopAddress != -1ULL && !Seq.empty()) {
         // Insert end sequence row with the computed end address, but
         // the same line as the previous one.
         auto NextLine = Seq.back();
         NextLine.Address.Address = StopAddress;
         NextLine.EndSequence = 1;
         NextLine.PrologueEnd = 0;
         NextLine.BasicBlock = 0;
         NextLine.EpilogueBegin = 0;
         Seq.push_back(NextLine);
         insertLineSequence(Seq, NewRows);
       }
 
       if (!CurrRange)
         continue;
     }
 
     // Ignore empty sequences.
     if (Row.EndSequence && Seq.empty())
       continue;
 
     // Relocate row address and add it to the current sequence.
-    Row.Address.Address += CurrRange->second;
+    Row.Address.Address += CurrRange->Value;
     Seq.emplace_back(Row);
 
     if (Row.EndSequence)
       insertLineSequence(Seq, NewRows);
   }
 
   // Finished extracting, now emit the line tables.
   // FIXME: LLVM hard-codes its prologue values. We just copy the
while (Data.isValidOffset(InputOffset)) {
     }
 
     uint64_t Loc = Data.getUnsigned(&InputOffset, AddrSize);
 
     // Some compilers seem to emit frame info that doesn't start at
     // 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<std::pair<AddressRange, int64_t>> Range =
-        Ranges.getRangeValueThatContains(Loc);
+    std::optional<AddressRangeValuePair> Range =
+        Ranges.getRangeThatContains(Loc);
     if (!Range) {
       // The +4 is to account for the size of the InitialLength field itself.
       InputOffset = EntryOffset + InitialLength + 4;
       continue;
     }
 
     // This is an FDE, and we have a mapping.
     // Have we already emitted a corresponding CIE?
if (IteratorInserted.second) {
       TheDwarfEmitter->emitCIE(CIEData);
     }
 
     // Emit the FDE with updated address and CIE pointer.
     // (4 + AddrSize) is the size of the CIEId + initial_location
     // fields that will get reconstructed by emitFDE().
     unsigned FDERemainingBytes = InitialLength - (4 + AddrSize);
     TheDwarfEmitter->emitFDE(IteratorInserted.first->getValue(), AddrSize,
-                             Loc + Range->second,
+                             Loc + Range->Value,
                              FrameData.substr(InputOffset, FDERemainingBytes));
     InputOffset += FDERemainingBytes;
   }
 }
 
 uint32_t DWARFLinker::DIECloner::hashFullyQualifiedName(DWARFDie DIE,
                                                         CompileUnit &U,
                                                         const DWARFFile &File,

llvm/lib/DWARFLinker/DWARFStreamer.cpp

 /// Just aggregate all the ranges gathered inside that unit.
 void DwarfStreamer::emitUnitRangesEntries(CompileUnit &Unit,
                                           bool DoDebugRanges) {
   const RangesTy &FunctionRanges = Unit.getFunctionRanges();
 
   // Linked addresses might end up in a different order.
   // Build linked address ranges.
   AddressRanges LinkedRanges;
-  for (size_t Idx = 0; Idx < FunctionRanges.size(); Idx++)
+  for (const AddressRangeValuePair &Range : FunctionRanges)
     LinkedRanges.insert(
-        {FunctionRanges[Idx].first.start() + FunctionRanges[Idx].second,
-         FunctionRanges[Idx].first.end() + FunctionRanges[Idx].second});
+        {Range.Range.start() + Range.Value, Range.Range.end() + Range.Value});
 
   if (!FunctionRanges.empty())
     emitDwarfDebugArangesTable(Unit, LinkedRanges);
 
   if (DoDebugRanges)
     emitDwarfDebugRangesTableFragment(Unit, LinkedRanges);
 }
 

llvm/lib/Support/AddressRanges.cpp

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

llvm/lib/Support/CMakeLists.txt

elseif(LLVM_INTEGRATED_CRT_ALLOC MATCHES "mimalloc$")
     endif()
     set(system_libs ${system_libs} "${MIMALLOC_LIB}" "-INCLUDE:malloc")
   endif()
 endif()
 
 add_subdirectory(BLAKE3)
 
 add_llvm_component_library(LLVMSupport
-  AddressRanges.cpp
   ABIBreak.cpp
   AMDGPUMetadata.cpp
   APFixedPoint.cpp
   APFloat.cpp
   APInt.cpp
   APSInt.cpp
   ARMBuildAttrs.cpp
   ARMAttributeParser.cpp

llvm/unittests/Support/AddressRangeTest.cpp

TEST(AddressRangeTest, TestRanges) {
 
   Ranges.insert(AddressRange(0x3000, 0x4000));
   Ranges.insert(AddressRange(0x4000, 0x5000));
   Ranges.insert(AddressRange(0x2000, 0x4500));
   EXPECT_EQ(Ranges.size(), 1u);
   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<int> Ranges;
+  AddressRangesMap Ranges;
 
   EXPECT_EQ(Ranges.size(), 0u);
   EXPECT_TRUE(Ranges.empty());
 
   // Add single range.
   Ranges.insert(AddressRange(0x1000, 0x2000), 0xfe);
   EXPECT_EQ(Ranges.size(), 1u);
   EXPECT_FALSE(Ranges.empty());
   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 value.
+  // 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.
   Ranges.insert(AddressRange(0x1000, 0x2000), 0xfe);
   EXPECT_EQ(Ranges.size(), 1u);
-  EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0xfe);
+  EXPECT_EQ(Ranges.getRangeThatContains(0x1000)->Value, 0xfe);
 
-  // Add adjacent range and check value.
+  // Add adjacent range and check mapped value.
   Ranges.insert(AddressRange(0x2000, 0x3000), 0xfc);
-  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));
+  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));
 
-  // 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 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 second range and check values.
+  // Add one more range and check mapped values.
   Ranges.insert(AddressRange(0x4000, 0x5000), 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);
+  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);
 
-  // Add intersecting range and check value.
+  // Add intersecting range and check mapped value.
   Ranges.insert(AddressRange(0x0, 0x6000), 0x1);
-  EXPECT_EQ(Ranges.size(), 1u);
-  EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 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);
 
-  // Check that values are correctly preserved for combined ranges.
+  // Check that mapped 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(0x400, 0x4ff), 0x5);
   Ranges.insert(AddressRange(0x500, 0x5ff), 0x6);
+  Ranges.insert(AddressRange(0x400, 0x4ff), 0x5);
   Ranges.insert(AddressRange(0x600, 0x6ff), 0x7);
+  EXPECT_EQ(Ranges.size(), 7u);
 
   Ranges.insert(AddressRange(0x150, 0x350), 0xff);
-  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);
+  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);
 
+  Ranges.insert(AddressRange(0x650, 0x700), 0x8);
   Ranges.insert(AddressRange(0x3ff, 0x400), 0x5);
-  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);
+  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());
+  }
 }