[DebugInfo][llvm-dwarfutil] Combine overlapped address ranges.

[avl]

Summary

DWARF files may contain overlapping address ranges. f.e. it can happen if the two
copies of the function have identical instruction sequences and they end up sharing.
That looks incorrect from the point of view of DWARF spec. Current implementation
of DWARFLinker does not combine overlapped address ranges. It would be good if such
ranges would be handled in some useful way. Thus, this patch allows DWARFLinker
to combine overlapped ranges in a single one.

Depends on D86539

[avl]

corrected test comment.

[aprantl]

At first glance this looks fine to me. @JDevlieghere ?

llvm/include/llvm/DWARFLinker/DWARFLinkerAddressRangesMap.h

21 ↗

(On Diff #421808)

adjustment

47 ↗

(On Diff #421808)

Since this is completely independent, it might make sense to write a unit test for this class.

100 ↗

(On Diff #421808)

maybe call this forEach()?

[avl]

addressed comments.

[avl]

@JDevlieghere Jonas, Would you mind to check this review, please?

[dblaikie]

Do you have a small/standalone lto example of these overlapped ranges - to understand both why they happen, and why they're invalid?

[avl]

In D123469#3462423, @dblaikie wrote:

Do you have a small/standalone lto example of these overlapped ranges - to understand both why they happen, and why they're invalid?

I do not have at the moment. The issue was raised by @clayborg https://reviews.llvm.org/D86539#3428098 . But I will try to reproduce.
That is the explanation:

This can happen when you have LTO mess with the debug info as many functions might end up being combined. I have a command that dumps the ranges of DIEs and the problem looks like this:

DIE OFFSET RANGE                                     NAME
========== ========================================= ====================
0x0000e88e [0x0000000000028454 - 0x0000000000028474) freep
0x0000e8c2 [0x0000000000028454 - 0x0000000000028474) freep_aligned
0x00022cf4 [0x0000000000028454 - 0x0000000000028474) freep
0x00022d5d [0x0000000000028454 - 0x0000000000028474) freep_aligned

[clayborg]

Do you have a small/standalone lto example of these overlapped ranges - to understand both why they happen, and why they're invalid?

Just have LTO combine the contents of two functions with the same opcode bytes and you can end up with ranges within the same CU and across CUs that overlap. I don't consider these invalid, but if they are in the same CU, the verification using llvm-dwarfdump would emit errors.

I have also seen bad DWARF where you have two functions that don't share the exact same range and yet do overlap. This is mostly again in LTO binaries where the LTO linker tried to change the DWARF.

[clayborg]

There are so many places where we redo address range and address ranges code in LLVM and LLDB. Might be worth moving the GSYM "Range.h" file into a more accessible area to avoid all of the "intersects" and "overlaps" kind of computations we do on address ranges. The code is here: llvm/include/llvm/DebugInfo/GSYM/Range.h

llvm/include/llvm/DWARFLinker/DWARFLinker.h

57

Would we want to include the LowPC in the ObjFileAddressRange struct and then use a std::set<ObjFileAddressRange>?

llvm/include/llvm/DWARFLinker/DWARFLinkerAddressRangesMap.h

52 ↗

(On Diff #423119)

Might be worth watching out for invalid LowPC/HighPC combos by using >= instead of ==?

[clayborg]

llvm/include/llvm/DWARFLinker/DWARFLinkerAddressRangesMap.h

25–29 ↗

(On Diff #423119)

It would be great to use a ADT "AddressRange" class here instead like something from llvm/include/llvm/DebugInfo/GSYM/Range.h instead of doing things manually.

37 ↗

(On Diff #423119)

Might be a bit clearer as suggested, or if we use a AddressRange class it would be:

return Range.contains(Address);

102 ↗

(On Diff #423119)

If the "Handler" function returns a bool, you can stop early if it returns false, or keep iterating if it returns true. No need if you don't think it would be useful

llvm/unittests/DWARFLinker/DWARFLinkerAddressRangesMapTest.cpp

1 ↗

(On Diff #423119)

If we decode to possibly use something like the llvm/include/llvm/DebugInfo/GSYM/Range.h classes, those all have unit tests.

34 ↗

(On Diff #423119)

If we change the addRange function to check using <=, add test for that here

[avl]

llvm/include/llvm/DWARFLinker/DWARFLinker.h

57

That is already done, DWARFLinkerAddressRangesMap.h:

struct DwarfLinkerAddressRange {
  /// Range LowPC.
  uint64_t LowPC = 0;

  /// Range HighPC.
  uint64_t HighPC = 0;

  ...
}

llvm/include/llvm/DWARFLinker/DWARFLinkerAddressRangesMap.h

25–29 ↗

(On Diff #423119)

I agree that using an ADT is a good thing here and DebugInfo/GSYM/Range.h:AddressRange is a good candidate. But it could not be used as it is. It requires some refactoring. f.e. it should be refactored out of DebugInfo/GSYM. Another thing is that there should be removed dependency on "class FileWriter;", and probably on "DataExtractor". I am OK with doing such refactoring, but would prefer to do it separately from this review.

[avl]

addressed comments.

[dblaikie]

In D123469#3463313, @clayborg wrote:

Do you have a small/standalone lto example of these overlapped ranges - to understand both why they happen, and why they're invalid?

Just have LTO combine the contents of two functions with the same opcode bytes and you can end up with ranges within the same CU and across CUs that overlap. I don't consider these invalid, but if they are in the same CU, the verification using llvm-dwarfdump would emit errors.

This can/does happen without LTO - actually I think it's less likely to happen /with/ LTO than without, but in any case, here's a simple example with overlapping CU ranges that doesn't require LTO (using __attribute__((nodebug)) to omit unnecessary debug info, the issue still reproduces without it, just with more noise):
inl.h:

inline void f1() {
}
void a();

a.cpp:

#include "inl.h"
__attribute__((nodebug)) void a() {
  f1();
}

b.cpp:

#include "inl.h"
void a();
__attribute__((nodebug)) int main() {
  a();
  f1();
}

clang++ -g a.cpp b.cpp && llvm-dwarfdump a.out | grep "0x000000000\|DW_TAG\|DW_AT_name" | sed -e "s/^............//"`

DW_TAG_compile_unit
  DW_AT_name    ("a.cpp")
  DW_AT_low_pc  (0x0000000000401180)
  DW_AT_high_pc (0x0000000000401186)
  DW_TAG_subprogram
    DW_AT_low_pc        (0x0000000000401180)
    DW_AT_high_pc       (0x0000000000401186)
    DW_AT_name  ("f1")
DW_TAG_compile_unit
  DW_AT_name    ("b.cpp")
  DW_AT_low_pc  (0x0000000000401180)
  DW_AT_high_pc (0x0000000000401186)
  DW_TAG_subprogram
    DW_AT_low_pc        (0x0000000000401180)
    DW_AT_high_pc       (0x0000000000401186)
    DW_AT_name  ("f1")

(this doesn't always happen - only if the two copies of f1 have identical instruction sequences do they end up sharing - if they are optimized differently then whichever one is chosen gets the range, and the other one gets a zero/tombstone address - like a gc'd function definition (otherwise the DWARF would be bogus - could be describing the instruction stream totally incorrectly, etc))

I'd expect this to also happen with Identical Code Folding, but at least a simple case doesn't seem to reproduce that behavior:

void f1() { }
void f2() { }
__attribute__((nodebug)) int main() {
}

clang++ -O3 test.cpp -fno-addrsig -fuse-ld=lld -Wl,--icf=all -g -ffunction-sections &&  llvm-dwarfdump a.out | grep "0x000000000\|DW_TAG\|DW_AT_name" | sed -e "s/^............//"`

DW_TAG_compile_unit
  DW_AT_name    ("test.cpp")
  DW_AT_low_pc  (0x0000000000000000)
     [0x0000000000201720, 0x0000000000201721)
     [0x0000000000000000, 0x0000000000000001))
  DW_TAG_subprogram
    DW_AT_low_pc        (0x0000000000201720)
    DW_AT_high_pc       (0x0000000000201721)
    DW_AT_name  ("f1")
  DW_TAG_subprogram
    DW_AT_low_pc        (0x0000000000000000)
    DW_AT_high_pc       (0x0000000000000001)
    DW_AT_name  ("f2")

Actually LLVM's LTO seems least likely to produce overlapping ranges - its IR representation doesn't map one function to multiple DWARF subprograms (the mapping from IR function to subprogram is from the IR function to a single DISubprogram - it can't represent more than one subprogram associated with a given IR function). Though possibly GCC's LTO or the like might have different behavior in this regard.

I have also seen bad DWARF where you have two functions that don't share the exact same range and yet do overlap. This is mostly again in LTO binaries where the LTO linker tried to change the DWARF.

I'd be curious to hear more about that/see a reproduction if you've got one

[clayborg]

LGTM. I think either Adrian or Jonas should probably give the final accept as this is for dsymutil and I am not the code owner.

[aprantl]

llvm/include/llvm/DWARFLinker/DWARFLinkerAddressRangesMap.h

25–29 ↗

(On Diff #423119)

I am OK with doing such refactoring, but would prefer to do it separately from this review.

That would be awesome!

[dblaikie]

(be good to fix the patch description/commit message - this is actually less likely (no case that I know of) to happen due to (at least LLVM's) LTO, and isn't an error as such (well, isn't a /bug/ but someone might an argument that it's not valid according to the DWARF spec?) in the cases I know of that do happen)

[avl]

rebased on D124350

[avl]

@clayborg Could you mind to check changes for AddressRangess class, please?

I have changed the behavior so that it combines following kinds of ranges:

[0x100,0x200) and [0x200, 0x300) -> [0x100, 0x300)

It can affect llvm-gsymutil.

[avl]

@clayborg Greg, Could you check&accept this review directly, please?

After requested refactoring is done(https://reviews.llvm.org/D123469?id=423119#inline-1190512)
the AddressRanges class was changed. It combines the ranges like this:

[0x100,0x200) and [0x200, 0x300) -> [0x100, 0x300)

It can affect llvm-gsymutil. I think it should be OK to combine ranges like this. Please check that behavior.

[clayborg]

In D123469#3533876, @avl wrote:

@clayborg Greg, Could you check&accept this review directly, please?

After requested refactoring is done(https://reviews.llvm.org/D123469?id=423119#inline-1190512)
the AddressRanges class was changed. It combines the ranges like this:

[0x100,0x200) and [0x200, 0x300) -> [0x100, 0x300)

It can affect llvm-gsymutil. I think it should be OK to combine ranges like this. Please check that behavior.

Sorry, just verified that this will be ok for llvm-gsymutil. The main questions is if this is something that everyone will want from an AddressRanges class. Maybe it would be best to add a default bool argument? See inlined comment

llvm/include/llvm/ADT/AddressRanges.h

60

Does this default to having 1 contained address range when the size integer isn't specified? If so that is good. Might be nice to specify that in the using? Also, this shouldn't be public as uses can now get ahold of the "Collection::iterator" from the insert() and muck with our structure. See inline comment below.

73

No one should be playing with or know about the implementation within this class for the "Collection::iterator". I know you use this iterator in the AddressRangesMap class, maybe we can make a "Collection::iterator insert_impl(AddressRange Range);" that is protected so that the AddressRangesMap can use this, and then leave this function as it was with the possibility of adding a new bool to request that ranges be combined?

void insert(AddressRange Range, bool CombineAdjacent = true);

The idea would be we always combine overlapping address ranges, so CombineAdjacent would combine when they don't overlap but one of the boundaries matches. It would be also good to document this in the header doc as to what "insert" will do in all cases. Before this was a class only used by llvm-gsymutil, but now with wider adoption it would be good to document.

[avl]

Sorry, just verified that this will be ok for llvm-gsymutil. The main questions is if this is something that everyone will want from an AddressRanges class. Maybe it would be best to add a default bool argument? See inlined comment

It would probably be better to add such bool argument(or other mechanism) when the real case become clear. So that we implemented it in the most convenient way(bool argument to the constructor, bool argument to the insert method, or probably separate class). It looks like current usages do not want that functionality.

llvm/include/llvm/ADT/AddressRanges.h

60

Does this default to having 1 contained address range when the size integer isn't specified? If so that is good. Might be nice to specify that in the using?

not exactly one range. Following is the comment from SmallVector.h:

/// In the absence of a well-motivated choice for the number of inlined
/// elements \p N, it is recommended to use \c SmallVector<T> (that is,
/// omitting the \p N). This will choose a default number of inlined elements
/// reasonable for allocation on the stack (for example, trying to keep \c
/// sizeof(SmallVector<T>) around 64 bytes)

if you think it is better to specify SmallVector<T, 1> - will change it.

Also, this shouldn't be public as uses can now get ahold of the "Collection::iterator" from the insert() and muck with our structure. See inline comment below.

Ok, will hide it under "protected" clause.

73

No one should be playing with or know about the implementation within this class for the "Collection::iterator". I know you use this iterator in the AddressRangesMap class, maybe we can make a "Collection::iterator insert_impl(AddressRange Range);" that is protected so that the AddressRangesMap can use this, and then leave this function as it was with the possibility of adding a new bool to request that ranges be combined?

Ok, will make insert_impl protected.

void insert(AddressRange Range, bool CombineAdjacent = true);

The idea would be we always combine overlapping address ranges, so CombineAdjacent >would combine when they don't overlap but one of the boundaries matches. It would be >also good to document this in the header doc as to what "insert" will do in all cases. Before >this was a class only used by llvm-gsymutil, but now with wider adoption it would be good to >document.

I would suggest to not introduce CombineAdjacent at current moment. gsymutil and dwarfutil do not need that functionality. If it would be needed by some future code then we will add it in the most convenient way. if that is OK, will update a comment accordingly.

[clayborg]

Ok, if we just protect the Collection::iterator stuff in AddessRanges, this will be good to go.

llvm/include/llvm/ADT/AddressRanges.h

60

Ok, leave SmallVector<T> as is, I was unaware of this nice feature.

73

Fine to add it later, maybe add a comment letting users knows that any adjacent address ranges will be combined. I am not sure what people would expect here, but you are correct in that all usage of this wants adjacent ranges to be combined, so all good.

[avl]

addressed comments(changed returning value of insert() method:
Collection::iterator -> Collection::const_iterator as in begin()/end(),
updated header comment do describe behavior for adjacent ranges).

[clayborg]

address ranges look good to me.

[avl]

rebased.

llvm/include/llvm/ADT/AddressRanges.h

 //===- AddressRanges.h ------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_ADT_ADDRESSRANGES_H
 #define LLVM_ADT_ADDRESSRANGES_H
 
 #include "llvm/ADT/Optional.h"
+#include "llvm/ADT/STLExtras.h"
+#include "llvm/ADT/SmallVector.h"
 #include <cassert>
 #include <stdint.h>
-#include <vector>
 
 namespace llvm {
 
 /// A class that represents an address range. The range is specified using
 /// a start and an end address: [Start, End).
 class AddressRange {
 public:
   AddressRange() {}

 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
+/// 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 = std::vector<AddressRange>;
+  using Collection = SmallVector<AddressRange>;
   Collection Ranges;
 
 public:
   void clear() { Ranges.clear(); }
   bool empty() const { return Ranges.empty(); }
-  bool contains(uint64_t Addr) const;
-  bool contains(AddressRange Range) const;
-  Optional<AddressRange> getRangeThatContains(uint64_t Addr) const;
-  void insert(AddressRange Range);
+  bool contains(uint64_t Addr) const { return find(Addr) != Ranges.end(); }
+  bool contains(AddressRange Range) const {
+    return find(Range) != Ranges.end();
+  }
+  Optional<AddressRange> getRangeThatContains(uint64_t Addr) const {
+    Collection::const_iterator It = find(Addr);
+    if (It == Ranges.end())
+      return None;
+
+    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 {
     assert(i < Ranges.size());
     return Ranges[i];
   }
   Collection::const_iterator begin() const { return Ranges.begin(); }
   Collection::const_iterator end() const { return Ranges.end(); }
+
+protected:
+  Collection::const_iterator find(uint64_t Addr) const;
+  Collection::const_iterator find(AddressRange Range) const;
+};
+
+/// 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 {
+public:
+  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;
+
+    // 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();
+  }
+  Optional<std::pair<AddressRange, T>>
+  getRangeValueThatContains(uint64_t Addr) const {
+    Collection::const_iterator It = find(Addr);
+    if (It == Ranges.end())
+      return None;
+
+    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
 
 #endif // LLVM_ADT_ADDRESSRANGES_H

llvm/include/llvm/DWARFLinker/DWARFLinker.h

 //===- DWARFLinker.h --------------------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DWARFLINKER_DWARFLINKER_H
 #define LLVM_DWARFLINKER_DWARFLINKER_H
 
+#include "llvm/ADT/AddressRanges.h"
 #include "llvm/CodeGen/AccelTable.h"
 #include "llvm/CodeGen/NonRelocatableStringpool.h"
 #include "llvm/DWARFLinker/DWARFLinkerCompileUnit.h"
 #include "llvm/DebugInfo/DWARF/DWARFDebugLine.h"
 #include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h"
 #include "llvm/DebugInfo/DWARF/DWARFDie.h"
 #include <map>
 

 enum class DwarfLinkerAccelTableKind : uint8_t {
   None,
   Apple,   ///< .apple_names, .apple_namespaces, .apple_types, .apple_objc.
   Dwarf,   ///< DWARF v5 .debug_names.
   Default, ///< Dwarf for DWARF5 or later, Apple otherwise.
   Pub,     ///< .debug_pubnames, .debug_pubtypes
 };
 
-/// Partial address range. Besides an offset, only the
-/// HighPC is stored. The structure is stored in a map where the LowPC is the
-/// key.
-struct ObjFileAddressRange {
-  /// Function HighPC.
-  uint64_t HighPC;
-  /// Offset to apply to the linked address.
-  /// should be 0 for not-linked object file.
-  int64_t Offset;
-
-  ObjFileAddressRange(uint64_t EndPC, int64_t Offset)
-      : HighPC(EndPC), Offset(Offset) {}
-
-  ObjFileAddressRange() : HighPC(0), Offset(0) {}
-};
-
-/// Map LowPC to ObjFileAddressRange.
-using RangesTy = std::map<uint64_t, ObjFileAddressRange>;
-
 /// AddressesMap represents information about valid addresses used
 /// by debug information. Valid addresses are those which points to
 /// live code sections. i.e. relocations for these addresses point
 /// into sections which would be/are placed into resulting binary.
 class AddressesMap {
 public:
   virtual ~AddressesMap();
 
public:
   /// Emit Apple type accelerator table.
   virtual void
   emitAppleTypes(AccelTable<AppleAccelTableStaticTypeData> &Table) = 0;
 
   /// Emit .debug_ranges for \p FuncRange by translating the
   /// original \p Entries.
   virtual void emitRangesEntries(
       int64_t UnitPcOffset, uint64_t OrigLowPc,
-      const FunctionIntervals::const_iterator &FuncRange,
+      Optional<std::pair<AddressRange, int64_t>> FuncRange,
       const std::vector<DWARFDebugRangeList::RangeListEntry> &Entries,
       unsigned AddressSize) = 0;
 
   /// Emit .debug_aranges entries for \p Unit and if \p DoRangesSection is true,
   /// also emit the .debug_ranges entries for the DW_TAG_compile_unit's
   /// DW_AT_ranges attribute.
   virtual void emitUnitRangesEntries(CompileUnit &Unit,
                                      bool DoRangesSection) = 0;

llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h

 //===- DWARFLinkerCompileUnit.h ---------------------------------*- 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
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_DWARFLINKER_DWARFLINKERCOMPILEUNIT_H
 #define LLVM_DWARFLINKER_DWARFLINKERCOMPILEUNIT_H
 
+#include "llvm/ADT/AddressRanges.h"
 #include "llvm/ADT/DenseMap.h"
-#include "llvm/ADT/IntervalMap.h"
 #include "llvm/CodeGen/DIE.h"
 #include "llvm/DebugInfo/DWARF/DWARFUnit.h"
 
 namespace llvm {
 
 class DeclContext;
 
-template <typename KeyT, typename ValT>
-using HalfOpenIntervalMap =
-    IntervalMap<KeyT, ValT, IntervalMapImpl::NodeSizer<KeyT, ValT>::LeafSize,
-                IntervalMapHalfOpenInfo<KeyT>>;
-
-using FunctionIntervals = HalfOpenIntervalMap<uint64_t, int64_t>;
+/// Mapped value in the address map is the offset to apply to the
+/// linked address.
+using RangesTy = AddressRangesMap<int64_t>;
 
 // FIXME: Delete this structure.
 struct PatchLocation {
   DIE::value_iterator I;
 
   PatchLocation() = default;
   PatchLocation(DIE::value_iterator I) : I(I) {}
 
struct DIEInfo {
     bool InModuleScope : 1;
 
     /// Is ODR marking done?
     bool ODRMarkingDone : 1;
   };
 
   CompileUnit(DWARFUnit &OrigUnit, unsigned ID, bool CanUseODR,
               StringRef ClangModuleName)
-      : OrigUnit(OrigUnit), ID(ID), Ranges(RangeAlloc),
-        ClangModuleName(ClangModuleName) {
+      : OrigUnit(OrigUnit), ID(ID), ClangModuleName(ClangModuleName) {
     Info.resize(OrigUnit.getNumDIEs());
 
     auto CUDie = OrigUnit.getUnitDIE(false);
     if (!CUDie) {
       HasODR = false;
       return;
     }
     if (auto Lang = dwarf::toUnsigned(CUDie.find(dwarf::DW_AT_language)))
public:
   uint64_t getLowPc() const { return LowPc; }
   uint64_t getHighPc() const { return HighPc; }
   bool hasLabelAt(uint64_t Addr) const { return Labels.count(Addr); }
 
   Optional<PatchLocation> getUnitRangesAttribute() const {
     return UnitRangeAttribute;
   }
 
-  const FunctionIntervals &getFunctionRanges() const { return Ranges; }
+  const RangesTy &getFunctionRanges() const { return Ranges; }
 
   const std::vector<PatchLocation> &getRangesAttributes() const {
     return RangeAttributes;
   }
 
   const std::vector<std::pair<PatchLocation, int64_t>> &
   getLocationAttributes() const {
     return LocationAttributes;
public:
   /// Add the low_pc of a label that is relocated by applying
   /// offset \p PCOffset.
   void addLabelLowPc(uint64_t LabelLowPc, int64_t PcOffset);
 
   /// Add a function range [\p LowPC, \p HighPC) that is relocated by applying
   /// offset \p PCOffset.
   void addFunctionRange(uint64_t LowPC, uint64_t HighPC, int64_t PCOffset);
 
-  /// Check whether specified address range \p LowPC \p HighPC
-  /// overlaps with existing function ranges.
-  bool overlapsWithFunctionRanges(uint64_t LowPC, uint64_t HighPC);
-
   /// Keep track of a DW_AT_range attribute that we will need to patch up later.
   void noteRangeAttribute(const DIE &Die, PatchLocation Attr);
 
   /// Keep track of a location attribute pointing to a location list in the
   /// debug_loc section.
   void noteLocationAttribute(PatchLocation Attr, int64_t PcOffset);
 
   /// Add a name accelerator entry for \a Die with \a Name.
private:
   ///
   /// The offsets for the attributes in this array couldn't be set while
   /// cloning because for cross-cu forward references the target DIE's offset
   /// isn't known you emit the reference attribute.
   std::vector<
       std::tuple<DIE *, const CompileUnit *, DeclContext *, PatchLocation>>
       ForwardDIEReferences;
 
-  FunctionIntervals::Allocator RangeAlloc;
-
-  /// The ranges in that interval map are the PC ranges for
-  /// functions in this unit, associated with the PC offset to apply
-  /// to the addresses to get the linked address.
-  FunctionIntervals Ranges;
+  /// The ranges in that map are the PC ranges for functions in this unit,
+  /// associated with the PC offset to apply to the addresses to get
+  /// the linked address.
+  RangesTy Ranges;
 
   /// The DW_AT_low_pc of each DW_TAG_label.
   SmallDenseMap<uint64_t, uint64_t, 1> Labels;
 
   /// DW_AT_ranges attributes to patch after we have gathered
   /// all the unit's function addresses.
   /// @{
   std::vector<PatchLocation> RangeAttributes;

llvm/include/llvm/DWARFLinker/DWARFStreamer.h

public:
   void emitSwiftReflectionSection(
       llvm::binaryformat::Swift5ReflectionSectionKind ReflSectionKind,
       StringRef Buffer, uint32_t Alignment, uint32_t Size);
 
   /// Emit debug_ranges for \p FuncRange by translating the
   /// original \p Entries.
   void emitRangesEntries(
       int64_t UnitPcOffset, uint64_t OrigLowPc,
-      const FunctionIntervals::const_iterator &FuncRange,
+      Optional<std::pair<AddressRange, int64_t>> FuncRange,
       const std::vector<DWARFDebugRangeList::RangeListEntry> &Entries,
       unsigned AddressSize) override;
 
   /// Emit debug_aranges entries for \p Unit and if \p DoRangesSection is true,
   /// also emit the debug_ranges entries for the DW_TAG_compile_unit's
   /// DW_AT_ranges attribute.
   void emitUnitRangesEntries(CompileUnit &Unit, bool DoRangesSection) override;
 

llvm/lib/DWARFLinker/DWARFLinker.cpp

unsigned DWARFLinker::shouldKeepSubprogramDIE(
   Flags |= TF_Keep;
 
   Optional<uint64_t> HighPc = DIE.getHighPC(*LowPc);
   if (!HighPc) {
     reportWarning("Function without high_pc. Range will be discarded.\n", File,
                   &DIE);
     return Flags;
   }
-
-  // TODO: Following check is a workaround for overlapping address ranges.
-  //       ELF binaries built with LTO might contain overlapping address
-  //       ranges. The better fix would be to combine such ranges. Following
-  //       is a workaround that should be removed when a good fix is done.
-  if (Unit.overlapsWithFunctionRanges(*LowPc, *HighPc)) {
-    reportWarning(
-        formatv("Overlapping address range [{0:X}, {1:X}]. Range will "
-                "be discarded.\n",
-                *LowPc, *HighPc),
+  if (*LowPc > *HighPc) {
+    reportWarning("low_pc greater than high_pc. Range will be discarded.\n",
                   File, &DIE);
     return Flags;
   }
 
   // Replace the debug map range with a more accurate one.
-  Ranges[*LowPc] = ObjFileAddressRange(*HighPc, MyInfo.AddrAdjust);
+  Ranges.insert({*LowPc, *HighPc}, MyInfo.AddrAdjust);
   Unit.addFunctionRange(*LowPc, *HighPc, MyInfo.AddrAdjust);
   return Flags;
 }
 
 /// Check if a DIE should be kept.
 /// \returns updated TraversalFlags.
 unsigned DWARFLinker::shouldKeepDIE(AddressesMap &RelocMgr, RangesTy &Ranges,
                                     const DWARFDie &DIE, const DWARFFile &File,
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);
-  auto InvalidRange = FunctionRanges.end(), CurrRange = InvalidRange;
+  Optional<std::pair<AddressRange, int64_t>> CurrRange;
   DWARFUnit &OrigUnit = Unit.getOrigUnit();
   auto OrigUnitDie = OrigUnit.getUnitDIE(false);
   uint64_t OrigLowPc =
       dwarf::toAddress(OrigUnitDie.find(dwarf::DW_AT_low_pc), -1ULL);
   // Ranges addresses are based on the unit's low_pc. Compute the
   // offset we need to apply to adapt to the new unit's low_pc.
   int64_t UnitPcOffset = 0;
   if (OrigLowPc != -1ULL)
     UnitPcOffset = int64_t(OrigLowPc) - Unit.getLowPc();
 
   for (const auto &RangeAttribute : Unit.getRangesAttributes()) {
     uint64_t Offset = RangeAttribute.get();
     RangeAttribute.set(TheDwarfEmitter->getRangesSectionSize());
     if (Error E = RangeList.extract(RangeExtractor, &Offset)) {
       llvm::consumeError(std::move(E));
       reportWarning("invalid range list ignored.", File);
       RangeList.clear();
     }
     const auto &Entries = RangeList.getEntries();
     if (!Entries.empty()) {
       const DWARFDebugRangeList::RangeListEntry &First = Entries.front();
 
-      if (CurrRange == InvalidRange ||
-          First.StartAddress + OrigLowPc < CurrRange.start() ||
-          First.StartAddress + OrigLowPc >= CurrRange.stop()) {
-        CurrRange = FunctionRanges.find(First.StartAddress + OrigLowPc);
-        if (CurrRange == InvalidRange ||
-            CurrRange.start() > First.StartAddress + OrigLowPc) {
+      if (!CurrRange ||
+          !CurrRange->first.contains(First.StartAddress + OrigLowPc)) {
+        CurrRange = FunctionRanges.getRangeValueThatContains(
+            First.StartAddress + OrigLowPc);
+        if (!CurrRange) {
           reportWarning("no mapping for range.", File);
           continue;
         }
       }
     }
 
     TheDwarfEmitter->emitRangesEntries(UnitPcOffset, OrigLowPc, CurrRange,
                                        Entries, AddressSize);
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();
-  auto InvalidRange = FunctionRanges.end(), CurrRange = InvalidRange;
+  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
   // 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 == InvalidRange || Row.Address.Address < CurrRange.start() ||
-        Row.Address.Address > CurrRange.stop() ||
-        (Row.Address.Address == CurrRange.stop() && !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 != InvalidRange
-                                 ? CurrRange.stop() + CurrRange.value()
-                                 : -1ULL;
-      CurrRange = FunctionRanges.find(Row.Address.Address);
-      bool CurrRangeValid =
-          CurrRange != InvalidRange && CurrRange.start() <= Row.Address.Address;
-      if (!CurrRangeValid) {
-        CurrRange = InvalidRange;
+      uint64_t StopAddress =
+          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.
           // 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.
-          auto Range = Ranges.lower_bound(Row.Address.Address);
-          if (Range != Ranges.begin() && Range != Ranges.end())
-            --Range;
-
-          if (Range != Ranges.end() && Range->first <= Row.Address.Address &&
-              Range->second.HighPC >= Row.Address.Address) {
-            StopAddress = Row.Address.Address + Range->second.Offset;
-          }
+          if (Optional<std::pair<AddressRange, int64_t>> Range =
+                  Ranges.getRangeValueThatContains(Row.Address.Address))
+            StopAddress = Row.Address.Address + (*Range).second;
         }
       }
       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 (!CurrRangeValid)
+      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.value();
+    Row.Address.Address += CurrRange->second;
     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)) {
     }
 
     uint32_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.
-    auto Range = Ranges.upper_bound(Loc);
-    if (Range != Ranges.begin())
-      --Range;
-    if (Range == Ranges.end() || Range->first > Loc ||
-        Range->second.HighPC <= Loc) {
+    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;
       continue;
     }
 
     // This is an FDE, and we have a mapping.
     // Have we already emitted a corresponding CIE?
     StringRef CIEData = LocalCIES[CIEId];
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.Offset,
+                             Loc + Range->second,
                              FrameData.substr(InputOffset, FDERemainingBytes));
     InputOffset += FDERemainingBytes;
   }
 }
 
 uint32_t DWARFLinker::DIECloner::hashFullyQualifiedName(DWARFDie DIE,
                                                         CompileUnit &U,
                                                         const DWARFFile &File,

llvm/lib/DWARFLinker/DWARFLinkerCompileUnit.cpp

 }
 
 void CompileUnit::addLabelLowPc(uint64_t LabelLowPc, int64_t PcOffset) {
   Labels.insert({LabelLowPc, PcOffset});
 }
 
 void CompileUnit::addFunctionRange(uint64_t FuncLowPc, uint64_t FuncHighPc,
                                    int64_t PcOffset) {
-  //  Don't add empty ranges to the interval map.  They are a problem because
-  //  the interval map expects half open intervals. This is safe because they
-  //  are empty anyway.
-  if (FuncHighPc != FuncLowPc)
-    Ranges.insert(FuncLowPc, FuncHighPc, PcOffset);
+  Ranges.insert({FuncLowPc, FuncHighPc}, PcOffset);
   this->LowPc = std::min(LowPc, FuncLowPc + PcOffset);
   this->HighPc = std::max(HighPc, FuncHighPc + PcOffset);
 }
 
-bool CompileUnit::overlapsWithFunctionRanges(uint64_t LowPC, uint64_t HighPC) {
-  return Ranges.overlaps(LowPC, HighPC);
-}
-
 void CompileUnit::noteRangeAttribute(const DIE &Die, PatchLocation Attr) {
   if (Die.getTag() != dwarf::DW_TAG_compile_unit)
     RangeAttributes.push_back(Attr);
   else
     UnitRangeAttribute = Attr;
 }
 
 void CompileUnit::noteLocationAttribute(PatchLocation Attr, int64_t PcOffset) {

llvm/lib/DWARFLinker/DWARFStreamer.cpp

 }
 
 /// Emit the debug_range section contents for \p FuncRange by
 /// translating the original \p Entries. The debug_range section
 /// format is totally trivial, consisting just of pairs of address
 /// sized addresses describing the ranges.
 void DwarfStreamer::emitRangesEntries(
     int64_t UnitPcOffset, uint64_t OrigLowPc,
-    const FunctionIntervals::const_iterator &FuncRange,
+    Optional<std::pair<AddressRange, int64_t>> FuncRange,
     const std::vector<DWARFDebugRangeList::RangeListEntry> &Entries,
     unsigned AddressSize) {
   MS->switchSection(MC->getObjectFileInfo()->getDwarfRangesSection());
 
   // Offset each range by the right amount.
-  int64_t PcOffset = Entries.empty() ? 0 : FuncRange.value() + UnitPcOffset;
+  int64_t PcOffset =
+      (Entries.empty() || !FuncRange) ? 0 : FuncRange->second + UnitPcOffset;
   for (const auto &Range : Entries) {
     if (Range.isBaseAddressSelectionEntry(AddressSize)) {
       warn("unsupported base address selection operation",
            "emitting debug_ranges");
       break;
     }
     // Do not emit empty ranges.
     if (Range.StartAddress == Range.EndAddress)
       continue;
 
     // All range entries should lie in the function range.
-    if (!(Range.StartAddress + OrigLowPc >= FuncRange.start() &&
-          Range.EndAddress + OrigLowPc <= FuncRange.stop()))
+    if (!FuncRange->first.contains(Range.StartAddress + OrigLowPc))
       warn("inconsistent range data.", "emitting debug_ranges");
     MS->emitIntValue(Range.StartAddress + PcOffset, AddressSize);
     MS->emitIntValue(Range.EndAddress + PcOffset, AddressSize);
     RangesSectionSize += 2 * AddressSize;
   }
 
   // Add the terminator entry.
   MS->emitIntValue(0, AddressSize);
   MS->emitIntValue(0, AddressSize);
   RangesSectionSize += 2 * AddressSize;
 }
 
 /// Emit the debug_aranges contribution of a unit and
 /// if \p DoDebugRanges is true the debug_range contents for a
 /// compile_unit level DW_AT_ranges attribute (Which are basically the
 /// same thing with a different base address).
 /// Just aggregate all the ranges gathered inside that unit.
 void DwarfStreamer::emitUnitRangesEntries(CompileUnit &Unit,
                                           bool DoDebugRanges) {
   unsigned AddressSize = Unit.getOrigUnit().getAddressByteSize();
   // Gather the ranges in a vector, so that we can simplify them. The
   // IntervalMap will have coalesced the non-linked ranges, but here
   // we want to coalesce the linked addresses.
   std::vector<std::pair<uint64_t, uint64_t>> Ranges;
-  const auto &FunctionRanges = Unit.getFunctionRanges();
-  for (auto Range = FunctionRanges.begin(), End = FunctionRanges.end();
-       Range != End; ++Range)
-    Ranges.push_back(std::make_pair(Range.start() + Range.value(),
-                                    Range.stop() + Range.value()));
+  const RangesTy &FunctionRanges = Unit.getFunctionRanges();
+  for (size_t Idx = 0; Idx < FunctionRanges.size(); Idx++) {
+    std::pair<AddressRange, int64_t> CurRange = FunctionRanges[Idx];
+
+    Ranges.push_back(std::make_pair(CurRange.first.start() + CurRange.second,
+                                    CurRange.first.end() + CurRange.second));
+  }
 
   // The object addresses where sorted, but again, the linked
   // addresses might end up in a different order.
   llvm::sort(Ranges);
 
   if (!Ranges.empty()) {
     MS->switchSection(MC->getObjectFileInfo()->getDwarfARangesSection());
 

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;
 
-void AddressRanges::insert(AddressRange Range) {
+AddressRanges::Collection::const_iterator
+AddressRanges::insert(AddressRange Range) {
   if (Range.size() == 0)
-    return;
+    return Ranges.end();
 
   auto It = llvm::upper_bound(Ranges, Range);
   auto It2 = It;
-  while (It2 != Ranges.end() && It2->start() < Range.end())
+  while (It2 != Ranges.end() && It2->start() <= Range.end())
     ++It2;
   if (It != It2) {
-    Range = {Range.start(), std::max(Range.end(), It2[-1].end())};
+    Range = {Range.start(), std::max(Range.end(), std::prev(It2)->end())};
     It = Ranges.erase(It, It2);
   }
-  if (It != Ranges.begin() && Range.start() < It[-1].end())
-    It[-1] = {It[-1].start(), std::max(It[-1].end(), Range.end())};
-  else
-    Ranges.insert(It, Range);
+  if (It != Ranges.begin() && Range.start() <= std::prev(It)->end()) {
+    --It;
+    *It = {It->start(), std::max(It->end(), Range.end())};
+    return It;
   }
 
-bool AddressRanges::contains(uint64_t Addr) const {
+  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; });
-  return It != Ranges.begin() && Addr < It[-1].end();
+
+  if (It == Ranges.begin())
+    return Ranges.end();
+
+  --It;
+  if (Addr >= It->end())
+    return Ranges.end();
+
+  return It;
 }
 
-bool AddressRanges::contains(AddressRange Range) const {
+AddressRanges::Collection::const_iterator
+AddressRanges::find(AddressRange Range) const {
   if (Range.size() == 0)
-    return false;
+    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 false;
-  return Range.end() <= It[-1].end();
-}
+    return Ranges.end();
 
-Optional<AddressRange>
-AddressRanges::getRangeThatContains(uint64_t Addr) const {
-  auto It = std::partition_point(
-      Ranges.begin(), Ranges.end(),
-      [=](const AddressRange &R) { return R.start() <= Addr; });
-  if (It != Ranges.begin() && Addr < It[-1].end())
-    return It[-1];
-  return llvm::None;
+  --It;
+  if (Range.end() > It->end())
+    return Ranges.end();
+
+  return It;
 }

llvm/test/tools/llvm-dwarfutil/ELF/gc-func-overlapping-address-ranges.test

+## This test checks that overlapping function address ranges
+## are combined during --garbage-collection optimisation.
+
+# RUN: yaml2obj %s -o %t.o
+# RUN: llvm-dwarfutil --garbage-collection %t.o %t1
+# RUN: llvm-dwarfdump -a %t1 | FileCheck %s
+
+# CHECK: DW_TAG_compile_unit
+# CHECK: DW_AT_name{{.*}}"CU1"
+# CHECK: DW_AT_low_pc{{.*}}0000000000001000
+# CHECK: DW_AT_ranges
+# CHECK: [0x0000000000001000, 0x000000000000102d)
+# CHECK: [0x0000000000002002, 0x000000000000200d)
+# CHECK: [0x000000000000201b, 0x000000000000202a)
+# CHECK: [0x0000000000003002, 0x0000000000003007)
+# CHECK: [0x0000000000003012, 0x0000000000003017)
+# CHECK: [0x0000000000003018, 0x000000000000301a)
+# CHECK: [0x0000000000003022, 0x0000000000003027
+# CHECK: DW_TAG_class_type
+# CHECK: DW_AT_name{{.*}}"class1"
+# CHECK: DW_TAG_class_type
+# CHECK: "class2"
+# CHECK: DW_TAG_subprogram
+# CHECK: DW_AT_name{{.*}}"foo1"
+# CHECK: DW_AT_low_pc{{.*}}0x0000000000001000
+# CHECK: DW_AT_high_pc{{.*}}0x0000000000001010
+# CHECK: DW_AT_type{{.*}}"class1"
+# CHECK: DW_TAG_subprogram
+# CHECK: "foo2"
+# CHECK: DW_AT_low_pc{{.*}}0x0000000000001004
+# CHECK: DW_AT_high_pc{{.*}}0x0000000000001007
+# CHECK: DW_AT_type{{.*}}"class2"
+# CHECK: DW_TAG_subprogram
+# CHECK: "foo3"
+# CHECK: DW_AT_low_pc{{.*}}0x000000000000100d
+# CHECK: DW_AT_high_pc{{.*}}0x000000000000102d
+# CHECK: DW_TAG_subprogram
+# CHECK: "foo4"
+# CHECK: DW_AT_low_pc{{.*}}0x0000000000002002
+# CHECK: DW_AT_high_pc{{.*}}0x000000000000200d
+# CHECK: DW_TAG_subprogram
+# CHECK: "foo5"
+# CHECK: DW_AT_low_pc{{.*}}0x000000000000201b
+# CHECK: DW_AT_high_pc{{.*}}0x000000000000202a
+# CHECK: DW_TAG_subprogram
+# CHECK: "foo6"
+# CHECK: DW_AT_low_pc{{.*}}0x0000000000003002
+# CHECK: DW_AT_high_pc{{.*}}0x0000000000003007
+# CHECK: DW_TAG_subprogram
+# CHECK: "foo7"
+# CHECK: DW_AT_low_pc{{.*}}0x0000000000003012
+# CHECK: DW_AT_high_pc{{.*}}0x0000000000003017
+# CHECK: DW_TAG_subprogram
+# CHECK: "foo8"
+# CHECK: DW_AT_low_pc{{.*}}0x0000000000003022
+# CHECK: DW_AT_high_pc{{.*}}0x0000000000003027
+# CHECK: DW_TAG_subprogram
+# CHECK: "foo9"
+# CHECK: DW_AT_low_pc{{.*}}0x0000000000003012
+# CHECK: DW_AT_high_pc{{.*}}0x0000000000003017
+# CHECK: "foo10"
+# CHECK: DW_AT_low_pc{{.*}}0x0000000000003018
+# CHECK: DW_AT_high_pc{{.*}}0x000000000000301a
+
+--- !ELF
+FileHeader:
+  Class:    ELFCLASS64
+  Data:     ELFDATA2LSB
+  Type:     ET_REL
+  Machine:  EM_X86_64
+Sections:
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    Address:         0x1000
+    AddressAlign:    0x0000000000000010
+    Content:        "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
+  - Name:            .text2
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    Address:         0x2000
+    AddressAlign:    0x0000000000000010
+    Content:        "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
+  - Name:            .text3
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    Address:         0x3000
+    AddressAlign:    0x0000000000000010
+    Content:        "000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000"
+DWARF:
+  debug_abbrev:
+    - Table:
+      - Tag:      DW_TAG_compile_unit
+        Children: DW_CHILDREN_yes
+        Attributes:
+          - Attribute: DW_AT_producer
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_language
+            Form:      DW_FORM_data2
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_low_pc
+            Form:      DW_FORM_addr
+          - Attribute: DW_AT_ranges
+            Form:      DW_FORM_sec_offset
+      - Tag:      DW_TAG_subprogram
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_low_pc
+            Form:      DW_FORM_addr
+          - Attribute: DW_AT_high_pc
+            Form:      DW_FORM_data8
+          - Attribute: DW_AT_type
+            Form:      DW_FORM_ref4
+      - Tag:      DW_TAG_class_type
+        Children: DW_CHILDREN_yes
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+      - Tag:      DW_TAG_member
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_type
+            Form:      DW_FORM_ref4
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+      - Tag:      DW_TAG_class_type
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_declaration
+            Form:      DW_FORM_flag_present
+      - Tag:      DW_TAG_class_type
+        Children: DW_CHILDREN_yes
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_declaration
+            Form:      DW_FORM_flag_present
+      - Tag:      DW_TAG_template_type_parameter
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_type
+            Form:      DW_FORM_ref4
+      - Tag:      DW_TAG_base_type
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+  debug_info:
+    - Version: 4
+      Entries:
+        - AbbrCode: 1
+          Values:
+            - CStr: by_hand
+            - Value:  0x04
+            - CStr: CU1
+            - Value:  0x00
+            - Value:  0x00
+        - AbbrCode: 3
+          Values:
+            - CStr: class1
+        - AbbrCode: 4
+          Values:
+            - Value:  0x00000052
+            - CStr: member1
+        - AbbrCode: 0
+        - AbbrCode: 3
+          Values:
+            - CStr: class2
+        - AbbrCode: 4
+          Values:
+            - Value:  0x00000052
+            - CStr: member1
+        - AbbrCode: 0
+        - AbbrCode: 8
+          Values:
+            - CStr: int
+        - AbbrCode: 2
+          Values:
+            - CStr: foo1
+            - Value:  0x1000
+            - Value:  0x10
+            - Value:  0x00000026
+        - AbbrCode: 2
+          Values:
+            - CStr: foo2
+            - Value:  0x1004
+            - Value:  0x3
+            - Value:  0x0000003c
+        - AbbrCode: 2
+          Values:
+            - CStr: foo3
+            - Value:  0x100d
+            - Value:  0x20
+            - Value:  0x0000003c
+        - AbbrCode: 2
+          Values:
+            - CStr: foo4
+            - Value:  0x2002
+            - Value:  0xb
+            - Value:  0x0000003c
+        - AbbrCode: 2
+          Values:
+            - CStr: foo5
+            - Value:  0x201b
+            - Value:  0xf
+            - Value:  0x0000003c
+        - AbbrCode: 2
+          Values:
+            - CStr: foo6
+            - Value:  0x3002
+            - Value:  0x5
+            - Value:  0x0000003c
+        - AbbrCode: 2
+          Values:
+            - CStr: foo7
+            - Value:  0x3012
+            - Value:  0x5
+            - Value:  0x0000003c
+        - AbbrCode: 2
+          Values:
+            - CStr: foo8
+            - Value:  0x3022
+            - Value:  0x5
+            - Value:  0x0000003c
+        - AbbrCode: 2
+          Values:
+            - CStr: foo9
+            - Value:  0x3012
+            - Value:  0x5
+            - Value:  0x0000003c
+        - AbbrCode: 2
+          Values:
+            - CStr: foo10
+            - Value:  0x3018
+            - Value:  0x2
+            - Value:  0x0000003c
+        - AbbrCode: 0
+
+  debug_ranges:
+    - Offset:          0x00000000
+      AddrSize:        0x08
+      Entries:
+        - LowOffset:       0x0000000000001000
+          HighOffset:      0x000000000000102d
+        - LowOffset:       0x0000000000002000
+          HighOffset:      0x000000000000202d
+        - LowOffset:       0x0000000000000000
+          HighOffset:      0x0000000000000000
+...

llvm/test/tools/llvm-dwarfutil/ELF/gc-unit-overlapping-address-ranges.test

+## This test checks that overlapping compile unit address ranges
+## are ignored (i.e. left unchanged) by --garbage-collection
+## optimisation.
+
+# RUN: yaml2obj %s -o %t.o
+# RUN: llvm-dwarfutil --garbage-collection %t.o %t1
+# RUN: llvm-dwarfdump -a %t1 | FileCheck %s
+
+# CHECK: DW_TAG_compile_unit
+# CHECK: DW_AT_name{{.*}}"CU1"
+# CHECK: DW_TAG_class_type
+# CHECK: DW_AT_name{{.*}}"class1"
+# CHECK: DW_TAG_subprogram
+# CHECK: DW_AT_name{{.*}}"foo1"
+# CHECK: DW_AT_low_pc{{.*}}0x0000000000001000
+# CHECK: DW_AT_high_pc{{.*}}0x0000000000001010
+# CHECK: DW_TAG_subprogram
+# CHECK: DW_AT_name{{.*}}"foo2"
+# CHECK: DW_AT_low_pc{{.*}}0x0000000000001000
+# CHECK: DW_AT_high_pc{{.*}}0x0000000000001010
+# CHECK: DW_AT_type{{.*}}"class2"
+
+--- !ELF
+FileHeader:
+  Class:    ELFCLASS64
+  Data:     ELFDATA2LSB
+  Type:     ET_REL
+  Machine:  EM_X86_64
+Sections:
+  - Name:            .text
+    Type:            SHT_PROGBITS
+    Flags:           [ SHF_ALLOC, SHF_EXECINSTR ]
+    Address:         0x1000
+    AddressAlign:    0x0000000000000010
+    Content:        "FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF"
+DWARF:
+  debug_abbrev:
+    - Table:
+      - Tag:      DW_TAG_compile_unit
+        Children: DW_CHILDREN_yes
+        Attributes:
+          - Attribute: DW_AT_producer
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_language
+            Form:      DW_FORM_data2
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_low_pc
+            Form:      DW_FORM_addr
+          - Attribute: DW_AT_high_pc
+            Form:      DW_FORM_data8
+      - Tag:      DW_TAG_subprogram
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_low_pc
+            Form:      DW_FORM_addr
+          - Attribute: DW_AT_high_pc
+            Form:      DW_FORM_data8
+          - Attribute: DW_AT_type
+            Form:      DW_FORM_ref4
+      - Tag:      DW_TAG_class_type
+        Children: DW_CHILDREN_yes
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+      - Tag:      DW_TAG_member
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_type
+            Form:      DW_FORM_ref4
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+      - Tag:      DW_TAG_class_type
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_declaration
+            Form:      DW_FORM_flag_present
+      - Tag:      DW_TAG_class_type
+        Children: DW_CHILDREN_yes
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_declaration
+            Form:      DW_FORM_flag_present
+      - Tag:      DW_TAG_template_type_parameter
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_type
+            Form:      DW_FORM_ref4
+      - Tag:      DW_TAG_base_type
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+    - Table:
+      - Tag:      DW_TAG_compile_unit
+        Children: DW_CHILDREN_yes
+        Attributes:
+          - Attribute: DW_AT_producer
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_language
+            Form:      DW_FORM_data2
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_low_pc
+            Form:      DW_FORM_addr
+          - Attribute: DW_AT_high_pc
+            Form:      DW_FORM_data8
+      - Tag:      DW_TAG_subprogram
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_low_pc
+            Form:      DW_FORM_addr
+          - Attribute: DW_AT_high_pc
+            Form:      DW_FORM_data8
+          - Attribute: DW_AT_type
+            Form:      DW_FORM_ref4
+      - Tag:      DW_TAG_class_type
+        Children: DW_CHILDREN_yes
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+      - Tag:      DW_TAG_member
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_type
+            Form:      DW_FORM_ref4
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+      - Tag:      DW_TAG_class_type
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_declaration
+            Form:      DW_FORM_flag_present
+      - Tag:      DW_TAG_class_type
+        Children: DW_CHILDREN_yes
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+          - Attribute: DW_AT_declaration
+            Form:      DW_FORM_flag_present
+      - Tag:      DW_TAG_template_type_parameter
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_type
+            Form:      DW_FORM_ref4
+      - Tag:      DW_TAG_base_type
+        Children: DW_CHILDREN_no
+        Attributes:
+          - Attribute: DW_AT_name
+            Form:      DW_FORM_string
+  debug_info:
+    - Version: 4
+      Entries:
+        - AbbrCode: 1
+          Values:
+            - CStr: by_hand
+            - Value:  0x04
+            - CStr: CU1
+            - Value:  0x1000
+            - Value:  0x1b
+        - AbbrCode: 3
+          Values:
+            - CStr: class1
+        - AbbrCode: 4
+          Values:
+            - Value:  0x0000006c
+            - CStr: member1
+        - AbbrCode: 0
+        - AbbrCode: 3
+          Values:
+            - CStr: class2
+        - AbbrCode: 4
+          Values:
+            - Value:  0x0000006c
+            - CStr: member1
+        - AbbrCode: 0
+        - AbbrCode: 3
+          Values:
+            - CStr: class3
+        - AbbrCode: 4
+          Values:
+            - Value:  0x0000006c
+            - CStr: member1
+        - AbbrCode: 0
+        - AbbrCode: 8
+          Values:
+            - CStr: int
+        - AbbrCode: 2
+          Values:
+            - CStr: foo1
+            - Value:  0x1000
+            - Value:  0x10
+            - Value:  0x0000002a
+        - AbbrCode: 0
+    - Version: 4
+      Entries:
+        - AbbrCode: 1
+          Values:
+            - CStr: by_hand
+            - Value:  0x04
+            - CStr: CU1
+            - Value:  0x1000
+            - Value:  0x1b
+        - AbbrCode: 3
+          Values:
+            - CStr: class1
+        - AbbrCode: 4
+          Values:
+            - Value:  0x0000006c
+            - CStr: member1
+        - AbbrCode: 0
+        - AbbrCode: 3
+          Values:
+            - CStr: class2
+        - AbbrCode: 4
+          Values:
+            - Value:  0x0000006c
+            - CStr: member1
+        - AbbrCode: 0
+        - AbbrCode: 3
+          Values:
+            - CStr: class3
+        - AbbrCode: 4
+          Values:
+            - Value:  0x0000006c
+            - CStr: member1
+        - AbbrCode: 0
+        - AbbrCode: 8
+          Values:
+            - CStr: int
+        - AbbrCode: 2
+          Values:
+            - CStr: foo2
+            - Value:  0x1000
+            - Value:  0x10
+            - Value:  0x00000040
+        - AbbrCode: 0
+...

llvm/tools/dsymutil/DwarfLinkerForBinary.h

AddressManager(DwarfLinkerForBinary &Linker, const object::ObjectFile &Obj,
       // bugs that need to be investigated, but for now we need to reproduce
       // dsymutil's behavior.
       // FIXME: Once we understood exactly if that information is needed,
       // maybe totally remove this (or try to use it to do a real
       // -gline-tables-only on Darwin.
       for (const auto &Entry : DMO.symbols()) {
         const auto &Mapping = Entry.getValue();
         if (Mapping.Size && Mapping.ObjectAddress)
-          AddressRanges[*Mapping.ObjectAddress] = ObjFileAddressRange(
-              *Mapping.ObjectAddress + Mapping.Size,
+          AddressRanges.insert(
+              {*Mapping.ObjectAddress, *Mapping.ObjectAddress + Mapping.Size},
               int64_t(Mapping.BinaryAddress) - *Mapping.ObjectAddress);
       }
     }
     virtual ~AddressManager() override { clear(); }
 
     bool hasValidRelocs() override {
       return !ValidDebugInfoRelocs.empty() || !ValidDebugAddrRelocs.empty();
     }

llvm/tools/dsymutil/DwarfLinkerForBinary.cpp

 #include "dsymutil.h"
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/ADT/BitVector.h"
 #include "llvm/ADT/DenseMap.h"
 #include "llvm/ADT/DenseMapInfo.h"
 #include "llvm/ADT/DenseSet.h"
 #include "llvm/ADT/FoldingSet.h"
 #include "llvm/ADT/Hashing.h"
-#include "llvm/ADT/IntervalMap.h"
 #include "llvm/ADT/None.h"
 #include "llvm/ADT/Optional.h"
 #include "llvm/ADT/PointerIntPair.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringMap.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"

llvm/tools/llvm-dwarfutil/DebugInfoLinker.cpp

ObjFileAddressMap(DWARFContext &Context, const Options &Options,
     // Remember addresses of existing text sections.
     for (const object::SectionRef &Sect : ObjFile.sections()) {
       if (!Sect.isText())
         continue;
       const uint64_t Size = Sect.getSize();
       if (Size == 0)
         continue;
       const uint64_t StartAddr = Sect.getAddress();
-      TextAddressRanges[{StartAddr}] = {StartAddr + Size, 0};
+      TextAddressRanges.insert({StartAddr, StartAddr + Size});
     }
 
     // Check CU address ranges for tombstone value.
     for (std::unique_ptr<DWARFUnit> &CU : Context.compile_units()) {
       Expected<llvm::DWARFAddressRangesVector> ARanges =
           CU->getUnitDIE().getAddressRanges();
       if (ARanges) {
         for (auto &Range : *ARanges) {
           if (!isDeadAddressRange(Range.LowPC, Range.HighPC, CU->getVersion(),
                                   Options.Tombstone, CU->getAddressByteSize()))
-            DWARFAddressRanges[{Range.LowPC}] = {Range.HighPC, 0};
+            DWARFAddressRanges.insert({Range.LowPC, Range.HighPC}, 0);
         }
       }
     }
   }
 
   // should be renamed into has valid address ranges
   bool hasValidRelocs() override { return !DWARFAddressRanges.empty(); }
 
llvm::Expected<uint64_t> relocateIndexedAddr(uint64_t, uint64_t) override {
     return object::createError("no relocations in linked binary");
   }
 
 protected:
   // returns true if specified address range is inside address ranges
   // of executable sections.
   bool isInsideExecutableSectionsAddressRange(uint64_t LowPC,
                                               Optional<uint64_t> HighPC) {
-    auto Range = TextAddressRanges.lower_bound(LowPC);
-    if ((Range == TextAddressRanges.end() || Range->first != LowPC) &&
-        Range != TextAddressRanges.begin())
-      --Range;
-
-    if (Range != TextAddressRanges.end() && Range->first <= LowPC &&
-        (HighPC ? Range->second.HighPC >= HighPC
-                : Range->second.HighPC >= LowPC))
-      return true;
+    Optional<AddressRange> Range =
+        TextAddressRanges.getRangeThatContains(LowPC);
 
-    return false;
+    if (HighPC)
+      return Range.hasValue() && Range->end() >= *HighPC;
+
+    return Range.hasValue();
   }
 
   uint64_t isBFDDeadAddressRange(uint64_t LowPC, Optional<uint64_t> HighPC,
                                  uint16_t Version) {
     if (LowPC == 0)
       return true;
 
     if ((Version <= 4) && HighPC && (LowPC == 1 && *HighPC == 1))
protected:
 
   bool isDeadAddress(uint64_t LowPC, uint16_t Version, TombstoneKind Tombstone,
                      uint8_t AddressByteSize) {
     return isDeadAddressRange(LowPC, None, Version, Tombstone, AddressByteSize);
   }
 
 private:
   RangesTy DWARFAddressRanges;
-  RangesTy TextAddressRanges;
+  AddressRanges TextAddressRanges;
   const Options &Opts;
 };
 
 bool linkDebugInfo(object::ObjectFile &File, const Options &Options,
                    raw_pwrite_stream &OutStream) {
 
   auto ReportWarn = [&](const Twine &Message, StringRef Context,
                         const DWARFDie *Die) {

llvm/unittests/Support/AddressRangeTest.cpp

TEST(AddressRangeTest, TestRanges) {
   EXPECT_FALSE(Ranges.contains(0x5000 + 1));
   EXPECT_FALSE(Ranges.contains(UINT64_MAX));
 
   EXPECT_FALSE(Ranges.contains(AddressRange()));
   EXPECT_FALSE(Ranges.contains(AddressRange(0x1000 - 1, 0x1000)));
   EXPECT_FALSE(Ranges.contains(AddressRange(0x1000, 0x1000)));
   EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x1000 + 1)));
   EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x2000)));
-  EXPECT_FALSE(Ranges.contains(AddressRange(0x1000, 0x2001)));
+  EXPECT_TRUE(Ranges.contains(AddressRange(0x1000, 0x2001)));
   EXPECT_TRUE(Ranges.contains(AddressRange(0x2000, 0x3000)));
   EXPECT_FALSE(Ranges.contains(AddressRange(0x2000, 0x3001)));
   EXPECT_FALSE(Ranges.contains(AddressRange(0x3000, 0x3001)));
   EXPECT_FALSE(Ranges.contains(AddressRange(0x1500, 0x4500)));
   EXPECT_FALSE(Ranges.contains(AddressRange(0x5000, 0x5001)));
 
   // Verify that intersecting ranges get combined
   Ranges.clear();
   Ranges.insert(AddressRange(0x1100, 0x1F00));
   // Verify a wholy contained range that is added doesn't do anything.
   Ranges.insert(AddressRange(0x1500, 0x1F00));
   EXPECT_EQ(Ranges.size(), 1u);
   EXPECT_EQ(Ranges[0], AddressRange(0x1100, 0x1F00));
 
   // Verify a range that starts before and intersects gets combined.
   Ranges.insert(AddressRange(0x1000, Ranges[0].start() + 1));
   EXPECT_EQ(Ranges.size(), 1u);
   EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x1F00));
 
   // Verify a range that starts inside and extends ranges gets combined.
   Ranges.insert(AddressRange(Ranges[0].end() - 1, 0x2000));
   EXPECT_EQ(Ranges.size(), 1u);
   EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2000));
 
-  // Verify that adjacent ranges don't get combined
-  Ranges.insert(AddressRange(0x2000, 0x3000));
+  // Verify that adjacent ranges get combined
+  Ranges.insert(AddressRange(0x2000, 0x2fff));
+  EXPECT_EQ(Ranges.size(), 1u);
+  EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2fff));
+
+  // Verify that ranges having 1 byte gap do not get combined
+  Ranges.insert(AddressRange(0x3000, 0x4000));
   EXPECT_EQ(Ranges.size(), 2u);
-  EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2000));
-  EXPECT_EQ(Ranges[1], AddressRange(0x2000, 0x3000));
+  EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2fff));
+  EXPECT_EQ(Ranges[1], AddressRange(0x3000, 0x4000));
+
   // Verify if we add an address range that intersects two ranges
   // that they get combined
   Ranges.insert(AddressRange(Ranges[0].end() - 1, Ranges[1].start() + 1));
   EXPECT_EQ(Ranges.size(), 1u);
-  EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x3000));
+  EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x4000));
 
   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, TestRangesMap) {
+  AddressRangesMap<int> 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)));
+
+  // Clear ranges.
+  Ranges.clear();
+  EXPECT_EQ(Ranges.size(), 0u);
+  EXPECT_TRUE(Ranges.empty());
+
+  // Add range and check value.
+  Ranges.insert(AddressRange(0x1000, 0x2000), 0xfe);
+  EXPECT_EQ(Ranges.size(), 1u);
+  EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0xfe);
+
+  // Add adjacent range and check 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));
+
+  // 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 second range and check 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);
+
+  // Add intersecting range and check value.
+  Ranges.insert(AddressRange(0x0, 0x6000), 0x1);
+  EXPECT_EQ(Ranges.size(), 1u);
+  EXPECT_EQ(Ranges.getRangeValueThatContains(0x1000)->second, 0x1);
+
+  // 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(0x400, 0x4ff), 0x5);
+  Ranges.insert(AddressRange(0x500, 0x5ff), 0x6);
+  Ranges.insert(AddressRange(0x600, 0x6ff), 0x7);
+
+  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);
+
+  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);
+}