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 @@ -11,6 +11,7 @@ #include "llvm/CodeGen/AccelTable.h" #include "llvm/CodeGen/NonRelocatableStringpool.h" +#include "llvm/DWARFLinker/DWARFLinkerAddressRangesMap.h" #include "llvm/DWARFLinker/DWARFLinkerCompileUnit.h" #include "llvm/DebugInfo/DWARF/DWARFDebugLine.h" #include "llvm/DebugInfo/DWARF/DWARFDebugRangeList.h" @@ -37,24 +38,7 @@ 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; +using RangesTy = DwarfLinkerAddressRangesMap; /// AddressesMap represents information about valid addresses used /// by debug information. Valid addresses are those which points to @@ -142,7 +126,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/DWARFLinkerAddressRangesMap.h b/llvm/include/llvm/DWARFLinker/DWARFLinkerAddressRangesMap.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/DWARFLinker/DWARFLinkerAddressRangesMap.h @@ -0,0 +1,131 @@ +//===- DWARFLinkerAddressRangesMap.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_DWARFLINKERADDRESSRANGESMAP_H +#define LLVM_DWARFLINKER_DWARFLINKERADDRESSRANGESMAP_H + +#include "llvm/ADT/DenseMap.h" +#include "llvm/ADT/IntervalMap.h" +#include "llvm/ADT/Optional.h" +#include "llvm/ADT/STLFunctionalExtras.h" +#include "llvm/ADT/SmallVector.h" +#include + +namespace llvm { + +/// This structure contains description of the half open address range +/// [LowPC, HighPC) and the adjustment value which should be applied +/// to the final addresses. +struct DwarfLinkerAddressRange { + /// Range LowPC. + uint64_t LowPC = 0; + + /// Range HighPC. + uint64_t HighPC = 0; + + /// Offset to apply to the linked address. + /// should be 0 for not-linked object file. + int64_t Offset = 0; + + /// \returns true if specified \p Address is inside the range. + bool contains(uint64_t Address) { + return LowPC <= Address && Address < HighPC; + } +}; + +/// This class is used to accumulate address ranges. +class DwarfLinkerAddressRangesMap { +public: + DwarfLinkerAddressRangesMap() : Ranges(RangeAlloc) {} + + /// Add the new address range and the adjusment value to the map. While + /// adding, overlapped address ranges are combined into the single range. + void addRange(uint64_t LowPC, uint64_t HighPC, int64_t AdjOffset) { + // Don't add empty or invalid ranges to the interval map. They are + // a problem because the interval map expects half open intervals. + // This is safe because they are empty or invalid anyway. + if (LowPC >= HighPC) + return; + + AddressIntervals::iterator UpperRange = Ranges.find(LowPC); + + // Check if [LowPC, HighPC) overlaps with Ranges. + if (UpperRange == Ranges.end() || HighPC <= UpperRange.start()) { + Ranges.insert(LowPC, HighPC, AdjOffset); + return; + } + + // Accumulate new ranges in NewRanges and add them to the Ranges later. + SmallVector NewRanges; + + // Check if LowPC is before the upper range. + if (LowPC < UpperRange.start()) + NewRanges.push_back({LowPC, UpperRange.start(), AdjOffset}); + + while (HighPC > UpperRange.stop()) { + uint64_t NextLowPC = UpperRange.stop(); + UpperRange++; + + // Check if no more ranges. + if (UpperRange == Ranges.end()) { + NewRanges.push_back({NextLowPC, HighPC, AdjOffset}); + break; + } + + // Save part of new range which is before upper range. + uint64_t NextHighPC = std::min(HighPC, UpperRange.start()); + NewRanges.push_back({NextLowPC, NextHighPC, AdjOffset}); + } + + // Add new ranges. + for (const DwarfLinkerAddressRange &Range : NewRanges) + Ranges.insert(Range.LowPC, Range.HighPC, Range.Offset); + } + + // \returns address range for the specified \p Address. + Optional getRange(uint64_t Address) const { + AddressIntervals::const_iterator It = Ranges.find(Address); + + if (It == Ranges.end() || Address < It.start()) + return None; + + return DwarfLinkerAddressRange{It.start(), It.stop(), It.value()}; + } + + // Apply \p Handler to each keeping address range. + // Stop iterating if Handler returns false. + void forEach( + llvm::function_ref Handler) const { + for (AddressIntervals::const_iterator It = Ranges.begin(); + It != Ranges.end(); It++) { + if (!Handler(DwarfLinkerAddressRange{It.start(), It.stop(), It.value()})) + break; + } + } + + /// \returns true if the map is empty. + bool empty() { return Ranges.empty(); } + + /// Erase the map. + void clear() { Ranges.clear(); } + +protected: + template + using HalfOpenIntervalMap = + IntervalMap::LeafSize, + IntervalMapHalfOpenInfo>; + + using AddressIntervals = HalfOpenIntervalMap; + + AddressIntervals::Allocator RangeAlloc; + AddressIntervals Ranges; +}; + +} // end namespace llvm + +#endif // LLVM_DWARFLINKER_DWARFLINKERADDRESSRANGESMAP_H 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 @@ -12,6 +12,7 @@ #include "llvm/ADT/DenseMap.h" #include "llvm/ADT/IntervalMap.h" #include "llvm/CodeGen/DIE.h" +#include "llvm/DWARFLinker/DWARFLinkerAddressRangesMap.h" #include "llvm/DebugInfo/DWARF/DWARFUnit.h" namespace llvm { @@ -84,8 +85,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 +143,9 @@ return UnitRangeAttribute; } - const FunctionIntervals &getFunctionRanges() const { return Ranges; } + const DwarfLinkerAddressRangesMap &getFunctionRanges() const { + return Ranges; + } const std::vector &getRangesAttributes() const { return RangeAttributes; @@ -182,10 +184,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 +268,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; + DwarfLinkerAddressRangesMap 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 @@ -500,21 +500,8 @@ 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 - // workaround should be removed when good fix would be done. - if (Unit.overlapsWithFunctionRanges(*LowPc, *HighPc)) { - reportWarning( - formatv("Overlapping address range [{0:X}, {1:X}]. Range will " - "be discarded.\n", - *LowPc, *HighPc), - File, &DIE); - return Flags; - } - // Replace the debug map range with a more accurate one. - Ranges[*LowPc] = ObjFileAddressRange(*HighPc, MyInfo.AddrAdjust); + Ranges.addRange(*LowPc, *HighPc, MyInfo.AddrAdjust); Unit.addFunctionRange(*LowPc, *HighPc, MyInfo.AddrAdjust); return Flags; } @@ -1583,7 +1570,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 +1593,9 @@ 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->contains(First.StartAddress + OrigLowPc)) { + CurrRange = FunctionRanges.getRange(First.StartAddress + OrigLowPc); + if (!CurrRange) { reportWarning("no mapping for range.", File); continue; } @@ -1718,7 +1702,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 +1721,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->contains(Row.Address.Address) || + (Row.Address.Address == CurrRange->HighPC && !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->HighPC + CurrRange->Offset : -1ULL; + CurrRange = FunctionRanges.getRange(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 +1736,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.getRange(Row.Address.Address)) + StopAddress = Row.Address.Address + (*Range).Offset; } } if (StopAddress != -1ULL && !Seq.empty()) { @@ -1780,7 +1754,7 @@ insertLineSequence(Seq, NewRows); } - if (!CurrRangeValid) + if (!CurrRange) continue; } @@ -1789,7 +1763,7 @@ continue; // Relocate row address and add it to the current sequence. - Row.Address.Address += CurrRange.value(); + Row.Address.Address += CurrRange->Offset; Seq.emplace_back(Row); if (Row.EndSequence) @@ -1929,11 +1903,8 @@ // 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.getRange(Loc); + if (!Range) { // The +4 is to account for the size of the InitialLength field itself. InputOffset = EntryOffset + InitialLength + 4; continue; @@ -1961,7 +1932,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->Offset, 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.addRange(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->Offset + 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->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,12 @@ // 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())); + Unit.getFunctionRanges().forEach( + [&](const DwarfLinkerAddressRange &Range) -> bool { + Ranges.push_back(std::make_pair(Range.LowPC + Range.Offset, + Range.HighPC + Range.Offset)); + return true; + }); // The object addresses where sorted, but again, the linked // addresses might end up in a different order. 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.addRange( + *Mapping.ObjectAddress, *Mapping.ObjectAddress + Mapping.Size, int64_t(Mapping.BinaryAddress) - *Mapping.ObjectAddress); } } 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.addRange(StartAddr, StartAddr + Size, 0); } // 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.addRange(Range.LowPC, Range.HighPC, 0); } } } @@ -146,17 +146,12 @@ // 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.getRange(LowPC); - return false; + if (HighPC) + return Range.hasValue() && Range->HighPC >= *HighPC; + + return Range.hasValue(); } uint64_t isBFDDeadAddressRange(uint64_t LowPC, Optional HighPC, diff --git a/llvm/unittests/CMakeLists.txt b/llvm/unittests/CMakeLists.txt --- a/llvm/unittests/CMakeLists.txt +++ b/llvm/unittests/CMakeLists.txt @@ -24,6 +24,7 @@ add_subdirectory(DebugInfo) add_subdirectory(Debuginfod) add_subdirectory(Demangle) +add_subdirectory(DWARFLinker) add_subdirectory(ExecutionEngine) add_subdirectory(FileCheck) add_subdirectory(Frontend) diff --git a/llvm/unittests/DWARFLinker/CMakeLists.txt b/llvm/unittests/DWARFLinker/CMakeLists.txt new file mode 100644 --- /dev/null +++ b/llvm/unittests/DWARFLinker/CMakeLists.txt @@ -0,0 +1,11 @@ +set(LLVM_LINK_COMPONENTS + DebugInfoDWARF + DWARFLinker + Support + ) + +add_llvm_unittest(DWARFLinkerTests + DWARFLinkerAddressRangesMapTest.cpp + ) + +target_link_libraries(DWARFLinkerTests PRIVATE LLVMTestingSupport) diff --git a/llvm/unittests/DWARFLinker/DWARFLinkerAddressRangesMapTest.cpp b/llvm/unittests/DWARFLinker/DWARFLinkerAddressRangesMapTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/DWARFLinker/DWARFLinkerAddressRangesMapTest.cpp @@ -0,0 +1,175 @@ +//===- DWARFLinkerAddressRangesMapTest.cpp --------------------------------===// +// +// 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/DWARFLinker/DWARFLinkerAddressRangesMap.h" +#include "llvm/ADT/SmallString.h" +#include "llvm/Support/Error.h" +#include "llvm/Support/FileUtilities.h" +#include "llvm/Testing/Support/Error.h" +#include "gtest/gtest.h" +#include + +using namespace llvm; + +#define ASSERT_RANGE_EQ(Range, Start, End, Value) \ + ASSERT_TRUE((Range).LowPC == (Start) && (Range).HighPC == (End) && \ + (Range).Offset == (Value)); + +TEST(testDWARFLinkerRanges, AddSingleRange) { + DwarfLinkerAddressRangesMap RangesMap; + std::vector ResultRanges; + + // Add zero length range. + RangesMap.addRange(1100, 1100, 100); + ASSERT_TRUE(RangesMap.empty()); + + // Add invalid range. + RangesMap.addRange(1200, 1100, 100); + ASSERT_TRUE(RangesMap.empty()); + + // Add single range. + RangesMap.addRange(1000, 1100, 100); + ASSERT_FALSE(RangesMap.empty()); + + RangesMap.forEach([&](const DwarfLinkerAddressRange &Range) -> bool { + ResultRanges.push_back(Range); + return true; + }); + + ASSERT_TRUE(ResultRanges.size() == 1); + ASSERT_RANGE_EQ(ResultRanges[0], 1000, 1100, 100); + + // Check getRange() for added range. + Optional CurRange = RangesMap.getRange(1000); + ASSERT_TRUE(CurRange); + ASSERT_RANGE_EQ(*CurRange, 1000, 1100, 100); + + CurRange = RangesMap.getRange(1050); + ASSERT_TRUE(CurRange); + ASSERT_RANGE_EQ(*CurRange, 1000, 1100, 100); + + CurRange = RangesMap.getRange(1099); + ASSERT_TRUE(CurRange); + ASSERT_RANGE_EQ(*CurRange, 1000, 1100, 100); + + CurRange = RangesMap.getRange(0); + ASSERT_FALSE(CurRange); + + CurRange = RangesMap.getRange(1100); + ASSERT_FALSE(CurRange); +} + +TEST(testDWARFLinkerRanges, EraseSingleRange) { + DwarfLinkerAddressRangesMap RangesMap; + + RangesMap.addRange(0, 100, 3); + ASSERT_TRUE(!RangesMap.empty()); + + RangesMap.clear(); + ASSERT_TRUE(RangesMap.empty()); + RangesMap.forEach([&](const DwarfLinkerAddressRange &) -> bool { + EXPECT_TRUE(false); + return true; + }); +} + +TEST(testDWARFLinkerRanges, AddOverlappingRanges) { + DwarfLinkerAddressRangesMap RangesMap; + std::vector ResultRanges; + + // ..[-]...[-].... + RangesMap.addRange(1000, 1010, 0); + RangesMap.addRange(1030, 1040, 0); + + // ..[-]... + // ..[-]... + RangesMap.addRange(1050, 1060, 0); + RangesMap.addRange(1050, 1060, 0); + + // ..[---]... + // .....[---]... + RangesMap.addRange(1070, 1100, 0); + RangesMap.addRange(1090, 1110, 0); + + // .....[---]... + // ..[---]... + RangesMap.addRange(1200, 1230, 0); + RangesMap.addRange(1220, 1250, 0); + + // ..[-][-].... + RangesMap.addRange(1300, 1320, 0); + RangesMap.addRange(1320, 1350, 0); + + // ..[-].[-].... + RangesMap.addRange(1400, 1419, 0); + RangesMap.addRange(1420, 1450, 0); + + // ..[---]... + // ...[-].... + RangesMap.addRange(1510, 1560, 0); + RangesMap.addRange(1520, 1530, 0); + + // ...[-].... + // ..[---]... + RangesMap.addRange(1630, 1640, 0); + RangesMap.addRange(1610, 1700, 0); + + RangesMap.forEach([&](const DwarfLinkerAddressRange &Range) -> bool { + ResultRanges.push_back(Range); + return true; + }); + + ASSERT_TRUE(ResultRanges.size() == 10); + ASSERT_RANGE_EQ(ResultRanges[0], 1000, 1010, 0); + ASSERT_RANGE_EQ(ResultRanges[1], 1030, 1040, 0); + ASSERT_RANGE_EQ(ResultRanges[2], 1050, 1060, 0); + ASSERT_RANGE_EQ(ResultRanges[3], 1070, 1110, 0); + ASSERT_RANGE_EQ(ResultRanges[4], 1200, 1250, 0); + ASSERT_RANGE_EQ(ResultRanges[5], 1300, 1350, 0); + ASSERT_RANGE_EQ(ResultRanges[6], 1400, 1419, 0); + ASSERT_RANGE_EQ(ResultRanges[7], 1420, 1450, 0); + ASSERT_RANGE_EQ(ResultRanges[8], 1510, 1560, 0); + ASSERT_RANGE_EQ(ResultRanges[9], 1610, 1700, 0); + + RangesMap.addRange(0, 2000, 0); + + ResultRanges.clear(); + RangesMap.forEach([&](const DwarfLinkerAddressRange &Range) -> bool { + ResultRanges.push_back(Range); + return true; + }); + + ASSERT_TRUE(ResultRanges.size() == 1); + ASSERT_RANGE_EQ(ResultRanges[0], 0, 2000, 0); +} + +TEST(testDWARFLinkerRanges, GetRange) { + DwarfLinkerAddressRangesMap RangesMap; + std::vector ResultRanges; + + // ..[-]...[-].... + RangesMap.addRange(1000, 1010, 10); + RangesMap.addRange(1030, 1040, 20); + + Optional CurRange = RangesMap.getRange(0); + ASSERT_FALSE(CurRange); + + CurRange = RangesMap.getRange(1005); + ASSERT_TRUE(CurRange); + ASSERT_RANGE_EQ(*CurRange, 1000, 1010, 10); + + CurRange = RangesMap.getRange(1020); + ASSERT_FALSE(CurRange); + + CurRange = RangesMap.getRange(1035); + ASSERT_TRUE(CurRange); + ASSERT_RANGE_EQ(*CurRange, 1030, 1040, 20); + + CurRange = RangesMap.getRange(1100); + ASSERT_FALSE(CurRange); +}