diff --git a/llvm/include/llvm/ADT/AddressRanges.h b/llvm/include/llvm/ADT/AddressRanges.h --- a/llvm/include/llvm/ADT/AddressRanges.h +++ b/llvm/include/llvm/ADT/AddressRanges.h @@ -10,9 +10,10 @@ #define LLVM_ADT_ADDRESSRANGES_H #include "llvm/ADT/Optional.h" +#include "llvm/ADT/STLExtras.h" +#include "llvm/ADT/SmallVector.h" #include #include -#include namespace llvm { @@ -50,17 +51,23 @@ /// and never contain any invalid or empty address ranges. Intersecting /// address ranges are combined during insertion. class AddressRanges { -protected: - using Collection = std::vector; - Collection Ranges; - public: + using Collection = SmallVector; + void clear() { Ranges.clear(); } bool empty() const { return Ranges.empty(); } - bool contains(uint64_t Addr) const; - bool contains(AddressRange Range) const; - Optional 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 getRangeThatContains(uint64_t Addr) const { + Collection::const_iterator It = find(Addr); + if (It == Ranges.end()) + return None; + + return *It; + } + Collection::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 { @@ -72,6 +79,64 @@ } 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; + + Collection Ranges; +}; + +/// 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 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::iterator RangesIt = AddressRanges::insert(Range); + if (RangesIt == Ranges.end()) + return; + + 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()); + + Values[Idx] = Value; + } + size_t size() const { + assert(Ranges.size() == Values.size()); + return AddressRanges::size(); + } + Optional> + 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 operator[](size_t Idx) const { + return std::make_pair(Ranges[Idx], Values[Idx]); + } + +protected: + using ValuesCollection = SmallVector; + ValuesCollection Values; }; } // namespace llvm diff --git a/llvm/include/llvm/DWARFLinker/DWARFLinker.h b/llvm/include/llvm/DWARFLinker/DWARFLinker.h --- a/llvm/include/llvm/DWARFLinker/DWARFLinker.h +++ b/llvm/include/llvm/DWARFLinker/DWARFLinker.h @@ -9,6 +9,7 @@ #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" @@ -37,25 +38,6 @@ 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; - /// 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 @@ -142,7 +124,7 @@ /// original \p Entries. virtual void emitRangesEntries( int64_t UnitPcOffset, uint64_t OrigLowPc, - const FunctionIntervals::const_iterator &FuncRange, + Optional> FuncRange, const std::vector &Entries, unsigned AddressSize) = 0; diff --git a/llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h b/llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h --- a/llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h +++ b/llvm/include/llvm/DWARFLinker/DWARFLinkerCompileUnit.h @@ -9,8 +9,8 @@ #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" @@ -18,12 +18,9 @@ class DeclContext; -template -using HalfOpenIntervalMap = - IntervalMap::LeafSize, - IntervalMapHalfOpenInfo>; - -using FunctionIntervals = HalfOpenIntervalMap; +/// Mapped value in the address map is the offset to apply to the +/// linked address. +using RangesTy = AddressRangesMap; // FIXME: Delete this structure. struct PatchLocation { @@ -84,8 +81,7 @@ 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); @@ -143,7 +139,7 @@ return UnitRangeAttribute; } - const FunctionIntervals &getFunctionRanges() const { return Ranges; } + const RangesTy &getFunctionRanges() const { return Ranges; } const std::vector &getRangesAttributes() const { return RangeAttributes; @@ -182,10 +178,6 @@ /// 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); @@ -270,12 +262,10 @@ std::tuple> 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 Labels; diff --git a/llvm/include/llvm/DWARFLinker/DWARFStreamer.h b/llvm/include/llvm/DWARFLinker/DWARFStreamer.h --- a/llvm/include/llvm/DWARFLinker/DWARFStreamer.h +++ b/llvm/include/llvm/DWARFLinker/DWARFStreamer.h @@ -96,7 +96,7 @@ /// original \p Entries. void emitRangesEntries( int64_t UnitPcOffset, uint64_t OrigLowPc, - const FunctionIntervals::const_iterator &FuncRange, + Optional> FuncRange, const std::vector &Entries, unsigned AddressSize) override; diff --git a/llvm/lib/DWARFLinker/DWARFLinker.cpp b/llvm/lib/DWARFLinker/DWARFLinker.cpp --- a/llvm/lib/DWARFLinker/DWARFLinker.cpp +++ b/llvm/lib/DWARFLinker/DWARFLinker.cpp @@ -499,22 +499,14 @@ &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), - File, &DIE); + 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; } @@ -1583,7 +1575,7 @@ DWARFDataExtractor RangeExtractor(OrigDwarf.getDWARFObj(), OrigDwarf.getDWARFObj().getRangesSection(), OrigDwarf.isLittleEndian(), AddressSize); - auto InvalidRange = FunctionRanges.end(), CurrRange = InvalidRange; + Optional> CurrRange; DWARFUnit &OrigUnit = Unit.getOrigUnit(); auto OrigUnitDie = OrigUnit.getUnitDIE(false); uint64_t OrigLowPc = @@ -1606,12 +1598,11 @@ 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; } @@ -1718,7 +1709,7 @@ // in NewRows. std::vector Seq; const auto &FunctionRanges = Unit.getFunctionRanges(); - auto InvalidRange = FunctionRanges.end(), CurrRange = InvalidRange; + Optional> 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 @@ -1737,19 +1728,14 @@ // 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 @@ -1757,14 +1743,9 @@ // 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> Range = + Ranges.getRangeValueThatContains(Row.Address.Address)) + StopAddress = Row.Address.Address + (*Range).second; } } if (StopAddress != -1ULL && !Seq.empty()) { @@ -1780,7 +1761,7 @@ insertLineSequence(Seq, NewRows); } - if (!CurrRangeValid) + if (!CurrRange) continue; } @@ -1789,7 +1770,7 @@ 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) @@ -1929,11 +1910,9 @@ // 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> Range = + Ranges.getRangeValueThatContains(Loc); + if (!Range) { // The +4 is to account for the size of the InitialLength field itself. InputOffset = EntryOffset + InitialLength + 4; continue; @@ -1961,7 +1940,7 @@ // 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; } diff --git a/llvm/lib/DWARFLinker/DWARFLinkerCompileUnit.cpp b/llvm/lib/DWARFLinker/DWARFLinkerCompileUnit.cpp --- a/llvm/lib/DWARFLinker/DWARFLinkerCompileUnit.cpp +++ b/llvm/lib/DWARFLinker/DWARFLinkerCompileUnit.cpp @@ -106,19 +106,11 @@ 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); diff --git a/llvm/lib/DWARFLinker/DWARFStreamer.cpp b/llvm/lib/DWARFLinker/DWARFStreamer.cpp --- a/llvm/lib/DWARFLinker/DWARFStreamer.cpp +++ b/llvm/lib/DWARFLinker/DWARFStreamer.cpp @@ -321,13 +321,14 @@ /// sized addresses describing the ranges. void DwarfStreamer::emitRangesEntries( int64_t UnitPcOffset, uint64_t OrigLowPc, - const FunctionIntervals::const_iterator &FuncRange, + Optional> FuncRange, const std::vector &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", @@ -339,8 +340,7 @@ 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); @@ -365,11 +365,13 @@ // IntervalMap will have coalesced the non-linked ranges, but here // we want to coalesce the linked addresses. std::vector> 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 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. diff --git a/llvm/lib/Support/AddressRanges.cpp b/llvm/lib/Support/AddressRanges.cpp --- a/llvm/lib/Support/AddressRanges.cpp +++ b/llvm/lib/Support/AddressRanges.cpp @@ -12,48 +12,55 @@ using namespace llvm; -void AddressRanges::insert(AddressRange Range) { +AddressRanges::Collection::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())}; It = Ranges.erase(It, It2); } - if (It != Ranges.begin() && Range.start() < It[-1].end()) + 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); + return It - 1; + } + + return Ranges.insert(It, Range); } -bool AddressRanges::contains(uint64_t Addr) const { +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(); + + if (Addr >= It[-1].end()) + return Ranges.end(); + + return It - 1; } -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 -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; + if (Range.end() > It[-1].end()) + return Ranges.end(); + + return It - 1; } diff --git a/llvm/test/tools/llvm-dwarfutil/ELF/gc-func-overlapping-address-ranges.test b/llvm/test/tools/llvm-dwarfutil/ELF/gc-func-overlapping-address-ranges.test new file mode 100644 --- /dev/null +++ b/llvm/test/tools/llvm-dwarfutil/ELF/gc-func-overlapping-address-ranges.test @@ -0,0 +1,254 @@ +## 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 +... diff --git a/llvm/test/tools/llvm-dwarfutil/ELF/gc-unit-overlapping-address-ranges.test b/llvm/test/tools/llvm-dwarfutil/ELF/gc-unit-overlapping-address-ranges.test new file mode 100644 --- /dev/null +++ b/llvm/test/tools/llvm-dwarfutil/ELF/gc-unit-overlapping-address-ranges.test @@ -0,0 +1,247 @@ +## 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 +... diff --git a/llvm/tools/dsymutil/DwarfLinkerForBinary.h b/llvm/tools/dsymutil/DwarfLinkerForBinary.h --- a/llvm/tools/dsymutil/DwarfLinkerForBinary.h +++ b/llvm/tools/dsymutil/DwarfLinkerForBinary.h @@ -132,8 +132,8 @@ 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); } } diff --git a/llvm/tools/dsymutil/DwarfLinkerForBinary.cpp b/llvm/tools/dsymutil/DwarfLinkerForBinary.cpp --- a/llvm/tools/dsymutil/DwarfLinkerForBinary.cpp +++ b/llvm/tools/dsymutil/DwarfLinkerForBinary.cpp @@ -18,7 +18,6 @@ #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" diff --git a/llvm/tools/llvm-dwarfutil/DebugInfoLinker.cpp b/llvm/tools/llvm-dwarfutil/DebugInfoLinker.cpp --- a/llvm/tools/llvm-dwarfutil/DebugInfoLinker.cpp +++ b/llvm/tools/llvm-dwarfutil/DebugInfoLinker.cpp @@ -48,7 +48,7 @@ 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. @@ -59,7 +59,7 @@ 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); } } } @@ -146,17 +146,13 @@ // of executable sections. bool isInsideExecutableSectionsAddressRange(uint64_t LowPC, Optional 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 Range = + TextAddressRanges.getRangeThatContains(LowPC); - return false; + if (HighPC) + return Range.hasValue() && Range->end() >= *HighPC; + + return Range.hasValue(); } uint64_t isBFDDeadAddressRange(uint64_t LowPC, Optional HighPC, @@ -210,7 +206,7 @@ private: RangesTy DWARFAddressRanges; - RangesTy TextAddressRanges; + AddressRanges TextAddressRanges; const Options &Opts; }; diff --git a/llvm/unittests/Support/AddressRangeTest.cpp b/llvm/unittests/Support/AddressRangeTest.cpp --- a/llvm/unittests/Support/AddressRangeTest.cpp +++ b/llvm/unittests/Support/AddressRangeTest.cpp @@ -100,7 +100,7 @@ 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))); @@ -125,16 +125,22 @@ 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)); @@ -142,3 +148,87 @@ EXPECT_EQ(Ranges.size(), 1u); EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x5000)); } + +TEST(AddressRangeTest, TestRangesMap) { + 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))); + + // 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); +}