diff --git a/llvm/include/llvm/ADT/AddressRanges.h b/llvm/include/llvm/ADT/AddressRanges.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/ADT/AddressRanges.h @@ -0,0 +1,79 @@ +//===- 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 +#include +#include + +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() {} + AddressRange(uint64_t S, uint64_t E) : Start(S), End(E) { + assert(Start <= End); + } + uint64_t start() const { return Start; } + uint64_t end() const { return End; } + uint64_t size() const { return End - Start; } + bool contains(uint64_t Addr) const { return Start <= Addr && Addr < End; } + bool intersects(const AddressRange &R) const { + return Start < R.End && R.Start < End; + } + bool operator==(const AddressRange &R) const { + return Start == R.Start && End == R.End; + } + bool operator!=(const AddressRange &R) const { return !(*this == R); } + bool operator<(const AddressRange &R) const { + return std::make_pair(Start, End) < std::make_pair(R.Start, R.End); + } + +private: + uint64_t Start = 0; + uint64_t End = 0; +}; + +/// The AddressRanges class helps normalize address range collections. +/// This class keeps a sorted vector of AddressRange objects and can perform +/// insertions and searches efficiently. The address ranges are always sorted +/// and never contain any invalid or empty address ranges. Intersecting +/// address ranges are combined during insertion. +class AddressRanges { +protected: + using Collection = std::vector; + 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 getRangeThatContains(uint64_t Addr) const; + void 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(); } +}; + +} // namespace llvm + +#endif // LLVM_ADT_ADDRESSRANGES_H diff --git a/llvm/include/llvm/DebugInfo/GSYM/DwarfTransformer.h b/llvm/include/llvm/DebugInfo/GSYM/DwarfTransformer.h --- a/llvm/include/llvm/DebugInfo/GSYM/DwarfTransformer.h +++ b/llvm/include/llvm/DebugInfo/GSYM/DwarfTransformer.h @@ -10,7 +10,7 @@ #define LLVM_DEBUGINFO_GSYM_DWARFTRANSFORMER_H #include "llvm/ADT/StringRef.h" -#include "llvm/DebugInfo/GSYM/Range.h" +#include "llvm/DebugInfo/GSYM/ExtractRanges.h" #include "llvm/Support/Error.h" namespace llvm { diff --git a/llvm/include/llvm/DebugInfo/GSYM/ExtractRanges.h b/llvm/include/llvm/DebugInfo/GSYM/ExtractRanges.h new file mode 100644 --- /dev/null +++ b/llvm/include/llvm/DebugInfo/GSYM/ExtractRanges.h @@ -0,0 +1,81 @@ +//===- ExtractRanges.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_DEBUGINFO_GSYM_EXTRACTRANGES_H +#define LLVM_DEBUGINFO_GSYM_EXTRACTRANGES_H + +#include "llvm/ADT/AddressRanges.h" +#include "llvm/Support/Format.h" +#include "llvm/Support/raw_ostream.h" +#include +#include + +#define HEX8(v) llvm::format_hex(v, 4) +#define HEX16(v) llvm::format_hex(v, 6) +#define HEX32(v) llvm::format_hex(v, 10) +#define HEX64(v) llvm::format_hex(v, 18) + +namespace llvm { +class DataExtractor; +class raw_ostream; + +namespace gsym { + +class FileWriter; + +/// AddressRange objects are encoded and decoded to be relative to a base +/// address. This will be the FunctionInfo's start address if the AddressRange +/// is directly contained in a FunctionInfo, or a base address of the +/// containing parent AddressRange or AddressRanges. This allows address +/// ranges to be efficiently encoded using ULEB128 encodings as we encode the +/// offset and size of each range instead of full addresses. This also makes +/// encoded addresses easy to relocate as we just need to relocate one base +/// address. +/// @{ +AddressRange decodeRange(DataExtractor &Data, uint64_t BaseAddr, + uint64_t &Offset); +void encodeRange(const AddressRange &Range, FileWriter &O, uint64_t BaseAddr); +/// @} + +/// Skip an address range object in the specified data a the specified +/// offset. +/// +/// \param Data The binary stream to read the data from. +/// +/// \param Offset The byte offset within \a Data. +void skipRange(DataExtractor &Data, uint64_t &Offset); + +/// Address ranges are decoded and encoded to be relative to a base address. +/// See the AddressRange comment for the encode and decode methods for full +/// details. +/// @{ +void decodeRanges(AddressRanges &Ranges, DataExtractor &Data, uint64_t BaseAddr, + uint64_t &Offset); +void encodeRanges(const AddressRanges &Ranges, FileWriter &O, + uint64_t BaseAddr); +/// @} + +/// Skip an address range object in the specified data a the specified +/// offset. +/// +/// \param Data The binary stream to read the data from. +/// +/// \param Offset The byte offset within \a Data. +/// +/// \returns The number of address ranges that were skipped. +uint64_t skipRanges(DataExtractor &Data, uint64_t &Offset); + +} // namespace gsym + +raw_ostream &operator<<(raw_ostream &OS, const AddressRange &R); + +raw_ostream &operator<<(raw_ostream &OS, const AddressRanges &AR); + +} // namespace llvm + +#endif // LLVM_DEBUGINFO_GSYM_EXTRACTRANGES_H diff --git a/llvm/include/llvm/DebugInfo/GSYM/FunctionInfo.h b/llvm/include/llvm/DebugInfo/GSYM/FunctionInfo.h --- a/llvm/include/llvm/DebugInfo/GSYM/FunctionInfo.h +++ b/llvm/include/llvm/DebugInfo/GSYM/FunctionInfo.h @@ -10,10 +10,10 @@ #define LLVM_DEBUGINFO_GSYM_FUNCTIONINFO_H #include "llvm/ADT/Optional.h" +#include "llvm/DebugInfo/GSYM/ExtractRanges.h" #include "llvm/DebugInfo/GSYM/InlineInfo.h" #include "llvm/DebugInfo/GSYM/LineTable.h" #include "llvm/DebugInfo/GSYM/LookupResult.h" -#include "llvm/DebugInfo/GSYM/Range.h" #include "llvm/DebugInfo/GSYM/StringTable.h" #include #include @@ -170,12 +170,9 @@ uint64_t FuncAddr, uint64_t Addr); - uint64_t startAddress() const { return Range.Start; } - uint64_t endAddress() const { return Range.End; } + uint64_t startAddress() const { return Range.start(); } + uint64_t endAddress() const { return Range.end(); } uint64_t size() const { return Range.size(); } - void setStartAddress(uint64_t Addr) { Range.Start = Addr; } - void setEndAddress(uint64_t Addr) { Range.End = Addr; } - void setSize(uint64_t Size) { Range.End = Range.Start + Size; } void clear() { Range = {0, 0}; diff --git a/llvm/include/llvm/DebugInfo/GSYM/GsymCreator.h b/llvm/include/llvm/DebugInfo/GSYM/GsymCreator.h --- a/llvm/include/llvm/DebugInfo/GSYM/GsymCreator.h +++ b/llvm/include/llvm/DebugInfo/GSYM/GsymCreator.h @@ -16,9 +16,9 @@ #include "llvm/ADT/ArrayRef.h" #include "llvm/ADT/StringSet.h" +#include "llvm/DebugInfo/GSYM/ExtractRanges.h" #include "llvm/DebugInfo/GSYM/FileEntry.h" #include "llvm/DebugInfo/GSYM/FunctionInfo.h" -#include "llvm/DebugInfo/GSYM/Range.h" #include "llvm/MC/StringTableBuilder.h" #include "llvm/Support/Endian.h" #include "llvm/Support/Error.h" diff --git a/llvm/include/llvm/DebugInfo/GSYM/InlineInfo.h b/llvm/include/llvm/DebugInfo/GSYM/InlineInfo.h --- a/llvm/include/llvm/DebugInfo/GSYM/InlineInfo.h +++ b/llvm/include/llvm/DebugInfo/GSYM/InlineInfo.h @@ -10,14 +10,13 @@ #define LLVM_DEBUGINFO_GSYM_INLINEINFO_H #include "llvm/ADT/Optional.h" +#include "llvm/DebugInfo/GSYM/ExtractRanges.h" #include "llvm/DebugInfo/GSYM/LineEntry.h" #include "llvm/DebugInfo/GSYM/LookupResult.h" -#include "llvm/DebugInfo/GSYM/Range.h" #include "llvm/Support/Error.h" #include #include - namespace llvm { class raw_ostream; diff --git a/llvm/include/llvm/DebugInfo/GSYM/LineEntry.h b/llvm/include/llvm/DebugInfo/GSYM/LineEntry.h --- a/llvm/include/llvm/DebugInfo/GSYM/LineEntry.h +++ b/llvm/include/llvm/DebugInfo/GSYM/LineEntry.h @@ -9,7 +9,7 @@ #ifndef LLVM_DEBUGINFO_GSYM_LINEENTRY_H #define LLVM_DEBUGINFO_GSYM_LINEENTRY_H -#include "llvm/DebugInfo/GSYM/Range.h" +#include "llvm/DebugInfo/GSYM/ExtractRanges.h" namespace llvm { namespace gsym { diff --git a/llvm/include/llvm/DebugInfo/GSYM/LookupResult.h b/llvm/include/llvm/DebugInfo/GSYM/LookupResult.h --- a/llvm/include/llvm/DebugInfo/GSYM/LookupResult.h +++ b/llvm/include/llvm/DebugInfo/GSYM/LookupResult.h @@ -10,7 +10,7 @@ #define LLVM_DEBUGINFO_GSYM_LOOKUPRESULT_H #include "llvm/ADT/StringRef.h" -#include "llvm/DebugInfo/GSYM/Range.h" +#include "llvm/DebugInfo/GSYM/ExtractRanges.h" #include #include diff --git a/llvm/include/llvm/DebugInfo/GSYM/Range.h b/llvm/include/llvm/DebugInfo/GSYM/Range.h deleted file mode 100644 --- a/llvm/include/llvm/DebugInfo/GSYM/Range.h +++ /dev/null @@ -1,130 +0,0 @@ -//===- Range.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_DEBUGINFO_GSYM_RANGE_H -#define LLVM_DEBUGINFO_GSYM_RANGE_H - -#include "llvm/ADT/Optional.h" -#include "llvm/Support/Format.h" -#include "llvm/Support/raw_ostream.h" -#include -#include - -#define HEX8(v) llvm::format_hex(v, 4) -#define HEX16(v) llvm::format_hex(v, 6) -#define HEX32(v) llvm::format_hex(v, 10) -#define HEX64(v) llvm::format_hex(v, 18) - -namespace llvm { -class DataExtractor; -class raw_ostream; - -namespace gsym { - -class FileWriter; - -/// A class that represents an address range. The range is specified using -/// a start and an end address. -struct AddressRange { - uint64_t Start; - uint64_t End; - AddressRange() : Start(0), End(0) {} - AddressRange(uint64_t S, uint64_t E) : Start(S), End(E) {} - uint64_t size() const { return End - Start; } - bool contains(uint64_t Addr) const { return Start <= Addr && Addr < End; } - bool intersects(const AddressRange &R) const { - return Start < R.End && R.Start < End; - } - - bool operator==(const AddressRange &R) const { - return Start == R.Start && End == R.End; - } - bool operator!=(const AddressRange &R) const { - return !(*this == R); - } - bool operator<(const AddressRange &R) const { - return std::make_pair(Start, End) < std::make_pair(R.Start, R.End); - } - /// AddressRange objects are encoded and decoded to be relative to a base - /// address. This will be the FunctionInfo's start address if the AddressRange - /// is directly contained in a FunctionInfo, or a base address of the - /// containing parent AddressRange or AddressRanges. This allows address - /// ranges to be efficiently encoded using ULEB128 encodings as we encode the - /// offset and size of each range instead of full addresses. This also makes - /// encoded addresses easy to relocate as we just need to relocate one base - /// address. - /// @{ - void decode(DataExtractor &Data, uint64_t BaseAddr, uint64_t &Offset); - void encode(FileWriter &O, uint64_t BaseAddr) const; - /// @} - - /// Skip an address range object in the specified data a the specified - /// offset. - /// - /// \param Data The binary stream to read the data from. - /// - /// \param Offset The byte offset within \a Data. - static void skip(DataExtractor &Data, uint64_t &Offset); -}; - -raw_ostream &operator<<(raw_ostream &OS, const AddressRange &R); - -/// 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. This allows us to -/// emit address ranges into the GSYM file efficiently. Intersecting address -/// ranges are combined during insertion so that we can emit the most compact -/// representation for address ranges when writing to disk. -class AddressRanges { -protected: - using Collection = std::vector; - 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 getRangeThatContains(uint64_t Addr) const; - void insert(AddressRange Range); - 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(); } - - /// Address ranges are decoded and encoded to be relative to a base address. - /// See the AddressRange comment for the encode and decode methods for full - /// details. - /// @{ - void decode(DataExtractor &Data, uint64_t BaseAddr, uint64_t &Offset); - void encode(FileWriter &O, uint64_t BaseAddr) const; - /// @} - - /// Skip an address range object in the specified data a the specified - /// offset. - /// - /// \param Data The binary stream to read the data from. - /// - /// \param Offset The byte offset within \a Data. - /// - /// \returns The number of address ranges that were skipped. - static uint64_t skip(DataExtractor &Data, uint64_t &Offset); -}; - -raw_ostream &operator<<(raw_ostream &OS, const AddressRanges &AR); - -} // namespace gsym -} // namespace llvm - -#endif // LLVM_DEBUGINFO_GSYM_RANGE_H diff --git a/llvm/include/llvm/DebugInfo/GSYM/StringTable.h b/llvm/include/llvm/DebugInfo/GSYM/StringTable.h --- a/llvm/include/llvm/DebugInfo/GSYM/StringTable.h +++ b/llvm/include/llvm/DebugInfo/GSYM/StringTable.h @@ -10,7 +10,7 @@ #define LLVM_DEBUGINFO_GSYM_STRINGTABLE_H #include "llvm/ADT/StringRef.h" -#include "llvm/DebugInfo/GSYM/Range.h" +#include "llvm/DebugInfo/GSYM/ExtractRanges.h" #include namespace llvm { diff --git a/llvm/lib/DebugInfo/GSYM/CMakeLists.txt b/llvm/lib/DebugInfo/GSYM/CMakeLists.txt --- a/llvm/lib/DebugInfo/GSYM/CMakeLists.txt +++ b/llvm/lib/DebugInfo/GSYM/CMakeLists.txt @@ -9,7 +9,7 @@ LineTable.cpp LookupResult.cpp ObjectFileTransformer.cpp - Range.cpp + ExtractRanges.cpp ADDITIONAL_HEADER_DIRS ${LLVM_MAIN_INCLUDE_DIR}/llvm/DebugInfo/GSYM diff --git a/llvm/lib/DebugInfo/GSYM/DwarfTransformer.cpp b/llvm/lib/DebugInfo/GSYM/DwarfTransformer.cpp --- a/llvm/lib/DebugInfo/GSYM/DwarfTransformer.cpp +++ b/llvm/lib/DebugInfo/GSYM/DwarfTransformer.cpp @@ -288,12 +288,12 @@ // linker problems or LTO or other DWARF re-linking so it is worth emitting // an error, but not worth stopping the creation of the GSYM. if (!FI.Range.contains(RowAddress)) { - if (RowAddress < FI.Range.Start) { + if (RowAddress < FI.Range.start()) { Log << "error: DIE has a start address whose LowPC is between the " "line table Row[" << RowIndex << "] with address " << HEX64(RowAddress) << " and the next one.\n"; Die.dump(Log, 0, DIDumpOptions::getForSingleDIE()); - RowAddress = FI.Range.Start; + RowAddress = FI.Range.start(); } else { continue; } @@ -404,8 +404,7 @@ } FunctionInfo FI; - FI.setStartAddress(Range.LowPC); - FI.setEndAddress(Range.HighPC); + FI.Range = {Range.LowPC, Range.HighPC}; FI.Name = *NameIndex; if (CUI.LineTable) { convertFunctionLineTable(OS, CUI, Die, Gsym, FI); diff --git a/llvm/lib/DebugInfo/GSYM/ExtractRanges.cpp b/llvm/lib/DebugInfo/GSYM/ExtractRanges.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/DebugInfo/GSYM/ExtractRanges.cpp @@ -0,0 +1,79 @@ +//===- ExtractRanges.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/DebugInfo/GSYM/ExtractRanges.h" +#include "llvm/DebugInfo/GSYM/FileWriter.h" +#include "llvm/Support/DataExtractor.h" +#include +#include + +namespace llvm { +namespace gsym { + +void encodeRange(const AddressRange &Range, FileWriter &O, uint64_t BaseAddr) { + assert(Range.start() >= BaseAddr); + O.writeULEB(Range.start() - BaseAddr); + O.writeULEB(Range.size()); +} + +AddressRange decodeRange(DataExtractor &Data, uint64_t BaseAddr, + uint64_t &Offset) { + const uint64_t AddrOffset = Data.getULEB128(&Offset); + const uint64_t Size = Data.getULEB128(&Offset); + const uint64_t StartAddr = BaseAddr + AddrOffset; + + return {StartAddr, StartAddr + Size}; +} + +void encodeRanges(const AddressRanges &Ranges, FileWriter &O, + uint64_t BaseAddr) { + O.writeULEB(Ranges.size()); + if (Ranges.empty()) + return; + for (auto Range : Ranges) + encodeRange(Range, O, BaseAddr); +} + +void decodeRanges(AddressRanges &Ranges, DataExtractor &Data, uint64_t BaseAddr, + uint64_t &Offset) { + Ranges.clear(); + uint64_t NumRanges = Data.getULEB128(&Offset); + Ranges.reserve(NumRanges); + for (uint64_t RangeIdx = 0; RangeIdx < NumRanges; RangeIdx++) + Ranges.insert(decodeRange(Data, BaseAddr, Offset)); +} + +void skipRange(DataExtractor &Data, uint64_t &Offset) { + Data.getULEB128(&Offset); + Data.getULEB128(&Offset); +} + +uint64_t skipRanges(DataExtractor &Data, uint64_t &Offset) { + uint64_t NumRanges = Data.getULEB128(&Offset); + for (uint64_t I = 0; I < NumRanges; ++I) + skipRange(Data, Offset); + return NumRanges; +} + +} // namespace gsym + +raw_ostream &operator<<(raw_ostream &OS, const AddressRange &R) { + return OS << '[' << HEX64(R.start()) << " - " << HEX64(R.end()) << ")"; +} + +raw_ostream &operator<<(raw_ostream &OS, const AddressRanges &AR) { + size_t Size = AR.size(); + for (size_t I = 0; I < Size; ++I) { + if (I) + OS << ' '; + OS << AR[I]; + } + return OS; +} + +} // namespace llvm diff --git a/llvm/lib/DebugInfo/GSYM/FunctionInfo.cpp b/llvm/lib/DebugInfo/GSYM/FunctionInfo.cpp --- a/llvm/lib/DebugInfo/GSYM/FunctionInfo.cpp +++ b/llvm/lib/DebugInfo/GSYM/FunctionInfo.cpp @@ -36,12 +36,11 @@ llvm::Expected FunctionInfo::decode(DataExtractor &Data, uint64_t BaseAddr) { FunctionInfo FI; - FI.Range.Start = BaseAddr; uint64_t Offset = 0; if (!Data.isValidOffsetForDataOfSize(Offset, 4)) return createStringError(std::errc::io_error, "0x%8.8" PRIx64 ": missing FunctionInfo Size", Offset); - FI.Range.End = FI.Range.Start + Data.getU32(&Offset); + FI.Range = {BaseAddr, BaseAddr + Data.getU32(&Offset)}; if (!Data.isValidOffsetForDataOfSize(Offset, 4)) return createStringError(std::errc::io_error, "0x%8.8" PRIx64 ": missing FunctionInfo Name", Offset); @@ -115,7 +114,7 @@ // writing the LineTable out with the number of bytes that were written. O.writeU32(0); const auto StartOffset = O.tell(); - llvm::Error err = OptLineTable->encode(O, Range.Start); + llvm::Error err = OptLineTable->encode(O, Range.start()); if (err) return std::move(err); const auto Length = O.tell() - StartOffset; @@ -133,7 +132,7 @@ // writing the LineTable out with the number of bytes that were written. O.writeU32(0); const auto StartOffset = O.tell(); - llvm::Error err = Inline->encode(O, Range.Start); + llvm::Error err = Inline->encode(O, Range.start()); if (err) return std::move(err); const auto Length = O.tell() - StartOffset; @@ -157,9 +156,8 @@ uint64_t Addr) { LookupResult LR; LR.LookupAddr = Addr; - LR.FuncRange.Start = FuncAddr; uint64_t Offset = 0; - LR.FuncRange.End = FuncAddr + Data.getU32(&Offset); + LR.FuncRange = {FuncAddr, FuncAddr + Data.getU32(&Offset)}; uint32_t NameOffset = Data.getU32(&Offset); // The "lookup" functions doesn't report errors as accurately as the "decode" // function as it is meant to be fast. For more accurage errors we could call diff --git a/llvm/lib/DebugInfo/GSYM/GsymCreator.cpp b/llvm/lib/DebugInfo/GSYM/GsymCreator.cpp --- a/llvm/lib/DebugInfo/GSYM/GsymCreator.cpp +++ b/llvm/lib/DebugInfo/GSYM/GsymCreator.cpp @@ -271,7 +271,7 @@ } } } else if (Prev.Range.size() == 0 && - Curr.Range.contains(Prev.Range.Start)) { + Curr.Range.contains(Prev.Range.start())) { if (!Quiet) { OS << "warning: removing symbol:\n" << Prev << "\nKeeping:\n" @@ -291,8 +291,8 @@ // has no size when doing lookups. if (!Funcs.empty() && Funcs.back().Range.size() == 0 && ValidTextRanges) { if (auto Range = - ValidTextRanges->getRangeThatContains(Funcs.back().Range.Start)) { - Funcs.back().Range.End = Range->End; + ValidTextRanges->getRangeThatContains(Funcs.back().Range.start())) { + Funcs.back().Range = *Range; } } OS << "Pruned " << NumBefore - Funcs.size() << " functions, ended with " diff --git a/llvm/lib/DebugInfo/GSYM/InlineInfo.cpp b/llvm/lib/DebugInfo/GSYM/InlineInfo.cpp --- a/llvm/lib/DebugInfo/GSYM/InlineInfo.cpp +++ b/llvm/lib/DebugInfo/GSYM/InlineInfo.cpp @@ -75,7 +75,7 @@ static bool skip(DataExtractor &Data, uint64_t &Offset, bool SkippedRanges) { if (!SkippedRanges) { - if (AddressRanges::skip(Data, Offset) == 0) + if (skipRanges(Data, Offset) == 0) return false; } bool HasChildren = Data.getU8(&Offset) != 0; @@ -109,7 +109,7 @@ uint64_t BaseAddr, uint64_t Addr, SourceLocations &SrcLocs, llvm::Error &Err) { InlineInfo Inline; - Inline.Ranges.decode(Data, BaseAddr, Offset); + decodeRanges(Inline.Ranges, Data, BaseAddr, Offset); if (Inline.Ranges.empty()) return true; // Check if the address is contained within the inline information, and if @@ -128,7 +128,7 @@ if (HasChildren) { // Child address ranges are encoded relative to the first address in the // parent InlineInfo object. - const auto ChildBaseAddr = Inline.Ranges[0].Start; + const auto ChildBaseAddr = Inline.Ranges[0].start(); bool Done = false; while (!Done) Done = lookup(GR, Data, Offset, ChildBaseAddr, Addr, SrcLocs, Err); @@ -150,7 +150,7 @@ SrcLoc.Base = GR.getString(CallFile->Base); SrcLoc.Line = Inline.CallLine; SrcLocs.back().Name = GR.getString(Inline.Name); - SrcLocs.back().Offset = Addr - Inline.Ranges[0].Start; + SrcLocs.back().Offset = Addr - Inline.Ranges[0].start(); SrcLocs.push_back(SrcLoc); } return true; @@ -182,7 +182,7 @@ if (!Data.isValidOffset(Offset)) return createStringError(std::errc::io_error, "0x%8.8" PRIx64 ": missing InlineInfo address ranges data", Offset); - Inline.Ranges.decode(Data, BaseAddr, Offset); + decodeRanges(Inline.Ranges, Data, BaseAddr, Offset); if (Inline.Ranges.empty()) return Inline; if (!Data.isValidOffsetForDataOfSize(Offset, 1)) @@ -205,7 +205,7 @@ if (HasChildren) { // Child address ranges are encoded relative to the first address in the // parent InlineInfo object. - const auto ChildBaseAddr = Inline.Ranges[0].Start; + const auto ChildBaseAddr = Inline.Ranges[0].start(); while (true) { llvm::Expected Child = decode(Data, Offset, ChildBaseAddr); if (!Child) @@ -232,7 +232,7 @@ if (!isValid()) return createStringError(std::errc::invalid_argument, "attempted to encode invalid InlineInfo object"); - Ranges.encode(O, BaseAddr); + encodeRanges(Ranges, O, BaseAddr); bool HasChildren = !Children.empty(); O.writeU8(HasChildren); O.writeU32(Name); @@ -242,7 +242,7 @@ // Child address ranges are encoded as relative to the first // address in the Ranges for this object. This keeps the offsets // small and allows for efficient encoding using ULEB offsets. - const uint64_t ChildBaseAddr = Ranges[0].Start; + const uint64_t ChildBaseAddr = Ranges[0].start(); for (const auto &Child : Children) { // Make sure all child address ranges are contained in the parent address // ranges. diff --git a/llvm/lib/DebugInfo/GSYM/Range.cpp b/llvm/lib/DebugInfo/GSYM/Range.cpp deleted file mode 100644 --- a/llvm/lib/DebugInfo/GSYM/Range.cpp +++ /dev/null @@ -1,123 +0,0 @@ -//===- Range.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/DebugInfo/GSYM/Range.h" -#include "llvm/DebugInfo/GSYM/FileWriter.h" -#include "llvm/Support/DataExtractor.h" -#include -#include - -using namespace llvm; -using namespace gsym; - - -void AddressRanges::insert(AddressRange Range) { - if (Range.size() == 0) - return; - - auto It = llvm::upper_bound(Ranges, Range); - auto It2 = It; - while (It2 != Ranges.end() && It2->Start < Range.End) - ++It2; - if (It != It2) { - Range.End = std::max(Range.End, It2[-1].End); - It = Ranges.erase(It, It2); - } - if (It != Ranges.begin() && Range.Start < It[-1].End) - It[-1].End = std::max(It[-1].End, Range.End); - else - Ranges.insert(It, Range); -} - -bool AddressRanges::contains(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; -} - -bool AddressRanges::contains(AddressRange Range) const { - if (Range.size() == 0) - return false; - 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; -} - -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; -} - -raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const AddressRange &R) { - return OS << '[' << HEX64(R.Start) << " - " << HEX64(R.End) << ")"; -} - -raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const AddressRanges &AR) { - size_t Size = AR.size(); - for (size_t I = 0; I < Size; ++I) { - if (I) - OS << ' '; - OS << AR[I]; - } - return OS; -} - -void AddressRange::encode(FileWriter &O, uint64_t BaseAddr) const { - assert(Start >= BaseAddr); - O.writeULEB(Start - BaseAddr); - O.writeULEB(size()); -} - -void AddressRange::decode(DataExtractor &Data, uint64_t BaseAddr, - uint64_t &Offset) { - const uint64_t AddrOffset = Data.getULEB128(&Offset); - const uint64_t Size = Data.getULEB128(&Offset); - const uint64_t StartAddr = BaseAddr + AddrOffset; - Start = StartAddr; - End = StartAddr + Size; -} - -void AddressRanges::encode(FileWriter &O, uint64_t BaseAddr) const { - O.writeULEB(Ranges.size()); - if (Ranges.empty()) - return; - for (auto Range : Ranges) - Range.encode(O, BaseAddr); -} - -void AddressRanges::decode(DataExtractor &Data, uint64_t BaseAddr, - uint64_t &Offset) { - clear(); - uint64_t NumRanges = Data.getULEB128(&Offset); - if (NumRanges == 0) - return; - Ranges.resize(NumRanges); - for (auto &Range : Ranges) - Range.decode(Data, BaseAddr, Offset); -} - -void AddressRange::skip(DataExtractor &Data, uint64_t &Offset) { - Data.getULEB128(&Offset); - Data.getULEB128(&Offset); -} - -uint64_t AddressRanges::skip(DataExtractor &Data, uint64_t &Offset) { - uint64_t NumRanges = Data.getULEB128(&Offset); - for (uint64_t I=0; I + +using namespace llvm; + +void AddressRanges::insert(AddressRange Range) { + if (Range.size() == 0) + return; + + auto It = llvm::upper_bound(Ranges, Range); + auto It2 = It; + while (It2 != Ranges.end() && It2->start() < Range.end()) + ++It2; + if (It != It2) { + Range = {Range.start(), std::max(Range.end(), It2[-1].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); +} + +bool AddressRanges::contains(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(); +} + +bool AddressRanges::contains(AddressRange Range) const { + if (Range.size() == 0) + return false; + 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(); +} + +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; +} diff --git a/llvm/lib/Support/CMakeLists.txt b/llvm/lib/Support/CMakeLists.txt --- a/llvm/lib/Support/CMakeLists.txt +++ b/llvm/lib/Support/CMakeLists.txt @@ -104,6 +104,7 @@ add_subdirectory(BLAKE3) add_llvm_component_library(LLVMSupport + AddressRanges.cpp AArch64TargetParser.cpp ABIBreak.cpp ARMTargetParser.cpp diff --git a/llvm/unittests/DebugInfo/GSYM/GSYMTest.cpp b/llvm/unittests/DebugInfo/GSYM/GSYMTest.cpp --- a/llvm/unittests/DebugInfo/GSYM/GSYMTest.cpp +++ b/llvm/unittests/DebugInfo/GSYM/GSYMTest.cpp @@ -10,14 +10,14 @@ #include "llvm/ADT/SmallString.h" #include "llvm/DebugInfo/DWARF/DWARFContext.h" #include "llvm/DebugInfo/GSYM/DwarfTransformer.h" -#include "llvm/DebugInfo/GSYM/Header.h" +#include "llvm/DebugInfo/GSYM/ExtractRanges.h" #include "llvm/DebugInfo/GSYM/FileEntry.h" #include "llvm/DebugInfo/GSYM/FileWriter.h" #include "llvm/DebugInfo/GSYM/FunctionInfo.h" #include "llvm/DebugInfo/GSYM/GsymCreator.h" #include "llvm/DebugInfo/GSYM/GsymReader.h" +#include "llvm/DebugInfo/GSYM/Header.h" #include "llvm/DebugInfo/GSYM/InlineInfo.h" -#include "llvm/DebugInfo/GSYM/Range.h" #include "llvm/DebugInfo/GSYM/StringTable.h" #include "llvm/ObjectYAML/DWARFEmitter.h" #include "llvm/Support/DataExtractor.h" @@ -112,11 +112,11 @@ EXPECT_EQ(A1, A2); // Make sure things are not equal if they only differ by start address. B = A2; - B.setStartAddress(0x2000); + B.Range = {0x1001, B.endAddress()}; EXPECT_NE(B, A2); // Make sure things are not equal if they only differ by size. B = A2; - B.setSize(0x101); + B.Range = {B.startAddress(), B.startAddress() + 0x101}; EXPECT_NE(B, A2); // Make sure things are not equal if they only differ by name. B = A2; @@ -125,7 +125,7 @@ // Check < operator. // Check less than where address differs. B = A2; - B.setStartAddress(A2.startAddress() + 0x1000); + B.Range = {A2.startAddress() + 0x1000, A2.endAddress() + 0x1000}; EXPECT_LT(A1, B); // We use the < operator to take a variety of different FunctionInfo @@ -253,8 +253,8 @@ std::string Bytes(OutStrm.str()); uint8_t AddressSize = 4; DataExtractor Data(Bytes, ByteOrder == llvm::support::little, AddressSize); - llvm::Expected Decoded = FunctionInfo::decode(Data, - FI.Range.Start); + llvm::Expected Decoded = + FunctionInfo::decode(Data, FI.Range.start()); // Make sure decoding succeeded. ASSERT_TRUE((bool)Decoded); // Make sure decoded object is the same as the one we encoded. @@ -323,7 +323,7 @@ SmallString<512> Str; raw_svector_ostream OutStrm(Str); FileWriter FW(OutStrm, ByteOrder); - const uint64_t BaseAddr = Inline.Ranges[0].Start; + const uint64_t BaseAddr = Inline.Ranges[0].start(); llvm::Error Err = Inline.encode(FW, BaseAddr); ASSERT_FALSE(Err); std::string Bytes(OutStrm.str()); @@ -354,7 +354,8 @@ SmallString<512> Str; raw_svector_ostream OutStrm(Str); FileWriter FW(OutStrm, ByteOrder); - const uint64_t BaseAddr = Inline.Ranges.empty() ? 0 : Inline.Ranges[0].Start; + const uint64_t BaseAddr = + Inline.Ranges.empty() ? 0 : Inline.Ranges[0].start(); llvm::Error Err = Inline.encode(FW, BaseAddr); checkError(ExpectedErrorMsg, std::move(Err)); } @@ -407,33 +408,33 @@ EXPECT_FALSE(Root.getInlineStack(0x50)); // Verify that we get no inline stacks for addresses out of [0x100-0x200) - EXPECT_FALSE(Root.getInlineStack(Root.Ranges[0].Start - 1)); - EXPECT_FALSE(Root.getInlineStack(Root.Ranges[0].End)); + EXPECT_FALSE(Root.getInlineStack(Root.Ranges[0].start() - 1)); + EXPECT_FALSE(Root.getInlineStack(Root.Ranges[0].end())); // Verify we get no inline stack entries for addresses that are in // [0x100-0x200) but not in [0x150-0x160) - EXPECT_FALSE(Root.getInlineStack(Inline1.Ranges[0].Start - 1)); - EXPECT_FALSE(Root.getInlineStack(Inline1.Ranges[0].End)); + EXPECT_FALSE(Root.getInlineStack(Inline1.Ranges[0].start() - 1)); + EXPECT_FALSE(Root.getInlineStack(Inline1.Ranges[0].end())); // Verify we get one inline stack entry for addresses that are in // [[0x150-0x160)) but not in [0x152-0x155) or [0x157-0x158) - auto InlineInfos = Root.getInlineStack(Inline1.Ranges[0].Start); + auto InlineInfos = Root.getInlineStack(Inline1.Ranges[0].start()); ASSERT_TRUE(InlineInfos); ASSERT_EQ(InlineInfos->size(), 1u); ASSERT_EQ(*InlineInfos->at(0), Inline1); - InlineInfos = Root.getInlineStack(Inline1.Ranges[0].End - 1); + InlineInfos = Root.getInlineStack(Inline1.Ranges[0].end() - 1); EXPECT_TRUE(InlineInfos); ASSERT_EQ(InlineInfos->size(), 1u); ASSERT_EQ(*InlineInfos->at(0), Inline1); // Verify we get two inline stack entries for addresses that are in // [0x152-0x155) - InlineInfos = Root.getInlineStack(Inline1Sub1.Ranges[0].Start); + InlineInfos = Root.getInlineStack(Inline1Sub1.Ranges[0].start()); EXPECT_TRUE(InlineInfos); ASSERT_EQ(InlineInfos->size(), 2u); ASSERT_EQ(*InlineInfos->at(0), Inline1Sub1); ASSERT_EQ(*InlineInfos->at(1), Inline1); - InlineInfos = Root.getInlineStack(Inline1Sub1.Ranges[0].End - 1); + InlineInfos = Root.getInlineStack(Inline1Sub1.Ranges[0].end() - 1); EXPECT_TRUE(InlineInfos); ASSERT_EQ(InlineInfos->size(), 2u); ASSERT_EQ(*InlineInfos->at(0), Inline1Sub1); @@ -441,12 +442,12 @@ // Verify we get two inline stack entries for addresses that are in // [0x157-0x158) - InlineInfos = Root.getInlineStack(Inline1Sub2.Ranges[0].Start); + InlineInfos = Root.getInlineStack(Inline1Sub2.Ranges[0].start()); EXPECT_TRUE(InlineInfos); ASSERT_EQ(InlineInfos->size(), 2u); ASSERT_EQ(*InlineInfos->at(0), Inline1Sub2); ASSERT_EQ(*InlineInfos->at(1), Inline1); - InlineInfos = Root.getInlineStack(Inline1Sub2.Ranges[0].End - 1); + InlineInfos = Root.getInlineStack(Inline1Sub2.Ranges[0].end() - 1); EXPECT_TRUE(InlineInfos); ASSERT_EQ(InlineInfos->size(), 2u); ASSERT_EQ(*InlineInfos->at(0), Inline1Sub2); @@ -470,7 +471,7 @@ // Verify that we get an error trying to encode an InlineInfo object that has // a child InlineInfo that has no ranges. InlineInfo ContainsEmpty; - ContainsEmpty.Ranges.insert({0x100,200}); + ContainsEmpty.Ranges.insert({0x100, 0x200}); ContainsEmpty.Children.push_back(Empty); TestInlineInfoEncodeError(llvm::support::little, ContainsEmpty, EmptyErr); TestInlineInfoEncodeError(llvm::support::big, ContainsEmpty, EmptyErr); @@ -479,9 +480,9 @@ // a child whose address range is not contained in the parent address range. InlineInfo ChildNotContained; std::string ChildNotContainedErr("child range not contained in parent"); - ChildNotContained.Ranges.insert({0x100,200}); + ChildNotContained.Ranges.insert({0x100, 0x200}); InlineInfo ChildNotContainedChild; - ChildNotContainedChild.Ranges.insert({0x200,300}); + ChildNotContainedChild.Ranges.insert({0x200, 0x300}); ChildNotContained.Children.push_back(ChildNotContainedChild); TestInlineInfoEncodeError(llvm::support::little, ChildNotContained, ChildNotContainedErr); @@ -502,7 +503,7 @@ "0x00000000: missing InlineInfo address ranges data"); AddressRanges Ranges; Ranges.insert({BaseAddr, BaseAddr+0x100}); - Ranges.encode(FW, BaseAddr); + encodeRanges(Ranges, FW, BaseAddr); TestInlineInfoDecodeError(ByteOrder, OutStrm.str(), BaseAddr, "0x00000004: missing InlineInfo uint8_t indicating children"); FW.writeU8(0); @@ -542,134 +543,6 @@ EXPECT_LT(E1, DifferentAddr); } -TEST(GSYMTest, TestRanges) { - // test llvm::gsym::AddressRange. - const uint64_t StartAddr = 0x1000; - const uint64_t EndAddr = 0x2000; - // Verify constructor and API to ensure it takes start and end address. - const AddressRange Range(StartAddr, EndAddr); - EXPECT_EQ(Range.size(), EndAddr - StartAddr); - - // Verify llvm::gsym::AddressRange::contains(). - EXPECT_FALSE(Range.contains(0)); - EXPECT_FALSE(Range.contains(StartAddr - 1)); - EXPECT_TRUE(Range.contains(StartAddr)); - EXPECT_TRUE(Range.contains(EndAddr - 1)); - EXPECT_FALSE(Range.contains(EndAddr)); - EXPECT_FALSE(Range.contains(UINT64_MAX)); - - const AddressRange RangeSame(StartAddr, EndAddr); - const AddressRange RangeDifferentStart(StartAddr + 1, EndAddr); - const AddressRange RangeDifferentEnd(StartAddr, EndAddr + 1); - const AddressRange RangeDifferentStartEnd(StartAddr + 1, EndAddr + 1); - // Test == and != with values that are the same - EXPECT_EQ(Range, RangeSame); - EXPECT_FALSE(Range != RangeSame); - // Test == and != with values that are the different - EXPECT_NE(Range, RangeDifferentStart); - EXPECT_NE(Range, RangeDifferentEnd); - EXPECT_NE(Range, RangeDifferentStartEnd); - EXPECT_FALSE(Range == RangeDifferentStart); - EXPECT_FALSE(Range == RangeDifferentEnd); - EXPECT_FALSE(Range == RangeDifferentStartEnd); - - // Test "bool operator<(const AddressRange &, const AddressRange &)". - EXPECT_FALSE(Range < RangeSame); - EXPECT_FALSE(RangeSame < Range); - EXPECT_LT(Range, RangeDifferentStart); - EXPECT_LT(Range, RangeDifferentEnd); - EXPECT_LT(Range, RangeDifferentStartEnd); - // Test "bool operator<(const AddressRange &, uint64_t)" - EXPECT_LT(Range.Start, StartAddr + 1); - // Test "bool operator<(uint64_t, const AddressRange &)" - EXPECT_LT(StartAddr - 1, Range.Start); - - // Verify llvm::gsym::AddressRange::isContiguousWith() and - // llvm::gsym::AddressRange::intersects(). - const AddressRange EndsBeforeRangeStart(0, StartAddr - 1); - const AddressRange EndsAtRangeStart(0, StartAddr); - const AddressRange OverlapsRangeStart(StartAddr - 1, StartAddr + 1); - const AddressRange InsideRange(StartAddr + 1, EndAddr - 1); - const AddressRange OverlapsRangeEnd(EndAddr - 1, EndAddr + 1); - const AddressRange StartsAtRangeEnd(EndAddr, EndAddr + 0x100); - const AddressRange StartsAfterRangeEnd(EndAddr + 1, EndAddr + 0x100); - - EXPECT_FALSE(Range.intersects(EndsBeforeRangeStart)); - EXPECT_FALSE(Range.intersects(EndsAtRangeStart)); - EXPECT_TRUE(Range.intersects(OverlapsRangeStart)); - EXPECT_TRUE(Range.intersects(InsideRange)); - EXPECT_TRUE(Range.intersects(OverlapsRangeEnd)); - EXPECT_FALSE(Range.intersects(StartsAtRangeEnd)); - EXPECT_FALSE(Range.intersects(StartsAfterRangeEnd)); - - // Test the functions that maintain GSYM address ranges: - // "bool AddressRange::contains(uint64_t Addr) const;" - // "void AddressRanges::insert(const AddressRange &R);" - AddressRanges Ranges; - Ranges.insert(AddressRange(0x1000, 0x2000)); - Ranges.insert(AddressRange(0x2000, 0x3000)); - Ranges.insert(AddressRange(0x4000, 0x5000)); - - EXPECT_FALSE(Ranges.contains(0)); - EXPECT_FALSE(Ranges.contains(0x1000 - 1)); - EXPECT_TRUE(Ranges.contains(0x1000)); - EXPECT_TRUE(Ranges.contains(0x2000)); - EXPECT_TRUE(Ranges.contains(0x4000)); - EXPECT_TRUE(Ranges.contains(0x2000 - 1)); - EXPECT_TRUE(Ranges.contains(0x3000 - 1)); - EXPECT_FALSE(Ranges.contains(0x3000 + 1)); - EXPECT_TRUE(Ranges.contains(0x5000 - 1)); - 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(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)); - EXPECT_EQ(Ranges.size(), 2u); - EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2000)); - EXPECT_EQ(Ranges[1], AddressRange(0x2000, 0x3000)); - // 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)); - - 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(GSYMTest, TestStringTable) { StringTable StrTab(StringRef("\0Hello\0World\0", 13)); // Test extracting strings from a string table. @@ -745,16 +618,16 @@ const uint64_t BaseAddr = 0x1000; const AddressRange Range1(0x1000, 0x1010); const AddressRange Range2(0x1020, 0x1030); - Range1.encode(FW, BaseAddr); - Range2.encode(FW, BaseAddr); + encodeRange(Range1, FW, BaseAddr); + encodeRange(Range2, FW, BaseAddr); std::string Bytes(OutStrm.str()); uint8_t AddressSize = 4; DataExtractor Data(Bytes, ByteOrder == llvm::support::little, AddressSize); AddressRange DecodedRange1, DecodedRange2; uint64_t Offset = 0; - DecodedRange1.decode(Data, BaseAddr, Offset); - DecodedRange2.decode(Data, BaseAddr, Offset); + DecodedRange1 = decodeRange(Data, BaseAddr, Offset); + DecodedRange2 = decodeRange(Data, BaseAddr, Offset); EXPECT_EQ(Range1, DecodedRange1); EXPECT_EQ(Range2, DecodedRange2); } @@ -765,7 +638,7 @@ raw_svector_ostream OutStrm(Str); const auto ByteOrder = llvm::support::endian::system_endianness(); FileWriter FW(OutStrm, ByteOrder); - Ranges.encode(FW, BaseAddr); + encodeRanges(Ranges, FW, BaseAddr); std::string Bytes(OutStrm.str()); uint8_t AddressSize = 4; @@ -773,7 +646,7 @@ AddressRanges DecodedRanges; uint64_t Offset = 0; - DecodedRanges.decode(Data, BaseAddr, Offset); + decodeRanges(DecodedRanges, Data, BaseAddr, Offset); EXPECT_EQ(Ranges, DecodedRanges); } @@ -1119,7 +992,7 @@ // Verify that all of the data in a GsymCreator is correctly decoded from // a GsymReader. To do this, we iterator over GC.forEachFunctionInfo([&](const FunctionInfo &FI) -> bool { - auto DecodedFI = GR.getFunctionInfo(FI.Range.Start); + auto DecodedFI = GR.getFunctionInfo(FI.Range.start()); EXPECT_TRUE(bool(DecodedFI)); EXPECT_EQ(FI, *DecodedFI); return true; // Keep iterating over all FunctionInfo objects. diff --git a/llvm/unittests/Support/AddressRangeTest.cpp b/llvm/unittests/Support/AddressRangeTest.cpp new file mode 100644 --- /dev/null +++ b/llvm/unittests/Support/AddressRangeTest.cpp @@ -0,0 +1,144 @@ +//===- llvm/unittest/Support/AddresRangeTest.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/ADT/AddressRanges.h" +#include "llvm/Testing/Support/Error.h" + +#include "gmock/gmock.h" +#include "gtest/gtest.h" +#include + +using namespace llvm; + +TEST(AddressRangeTest, TestRanges) { + // test llvm::AddressRange. + const uint64_t StartAddr = 0x1000; + const uint64_t EndAddr = 0x2000; + // Verify constructor and API to ensure it takes start and end address. + const AddressRange Range(StartAddr, EndAddr); + EXPECT_EQ(Range.size(), EndAddr - StartAddr); + + // Verify llvm::AddressRange::contains(). + EXPECT_FALSE(Range.contains(0)); + EXPECT_FALSE(Range.contains(StartAddr - 1)); + EXPECT_TRUE(Range.contains(StartAddr)); + EXPECT_TRUE(Range.contains(EndAddr - 1)); + EXPECT_FALSE(Range.contains(EndAddr)); + EXPECT_FALSE(Range.contains(UINT64_MAX)); + + const AddressRange RangeSame(StartAddr, EndAddr); + const AddressRange RangeDifferentStart(StartAddr + 1, EndAddr); + const AddressRange RangeDifferentEnd(StartAddr, EndAddr + 1); + const AddressRange RangeDifferentStartEnd(StartAddr + 1, EndAddr + 1); + // Test == and != with values that are the same + EXPECT_EQ(Range, RangeSame); + EXPECT_FALSE(Range != RangeSame); + // Test == and != with values that are the different + EXPECT_NE(Range, RangeDifferentStart); + EXPECT_NE(Range, RangeDifferentEnd); + EXPECT_NE(Range, RangeDifferentStartEnd); + EXPECT_FALSE(Range == RangeDifferentStart); + EXPECT_FALSE(Range == RangeDifferentEnd); + EXPECT_FALSE(Range == RangeDifferentStartEnd); + + // Test "bool operator<(const AddressRange &, const AddressRange &)". + EXPECT_FALSE(Range < RangeSame); + EXPECT_FALSE(RangeSame < Range); + EXPECT_LT(Range, RangeDifferentStart); + EXPECT_LT(Range, RangeDifferentEnd); + EXPECT_LT(Range, RangeDifferentStartEnd); + // Test "bool operator<(const AddressRange &, uint64_t)" + EXPECT_LT(Range.start(), StartAddr + 1); + // Test "bool operator<(uint64_t, const AddressRange &)" + EXPECT_LT(StartAddr - 1, Range.start()); + + // Verify llvm::AddressRange::isContiguousWith() and + // llvm::AddressRange::intersects(). + const AddressRange EndsBeforeRangeStart(0, StartAddr - 1); + const AddressRange EndsAtRangeStart(0, StartAddr); + const AddressRange OverlapsRangeStart(StartAddr - 1, StartAddr + 1); + const AddressRange InsideRange(StartAddr + 1, EndAddr - 1); + const AddressRange OverlapsRangeEnd(EndAddr - 1, EndAddr + 1); + const AddressRange StartsAtRangeEnd(EndAddr, EndAddr + 0x100); + const AddressRange StartsAfterRangeEnd(EndAddr + 1, EndAddr + 0x100); + + EXPECT_FALSE(Range.intersects(EndsBeforeRangeStart)); + EXPECT_FALSE(Range.intersects(EndsAtRangeStart)); + EXPECT_TRUE(Range.intersects(OverlapsRangeStart)); + EXPECT_TRUE(Range.intersects(InsideRange)); + EXPECT_TRUE(Range.intersects(OverlapsRangeEnd)); + EXPECT_FALSE(Range.intersects(StartsAtRangeEnd)); + EXPECT_FALSE(Range.intersects(StartsAfterRangeEnd)); + + // Test the functions that maintain address ranges: + // "bool AddressRange::contains(uint64_t Addr) const;" + // "void AddressRanges::insert(const AddressRange &R);" + AddressRanges Ranges; + Ranges.insert(AddressRange(0x1000, 0x2000)); + Ranges.insert(AddressRange(0x2000, 0x3000)); + Ranges.insert(AddressRange(0x4000, 0x5000)); + + EXPECT_FALSE(Ranges.contains(0)); + EXPECT_FALSE(Ranges.contains(0x1000 - 1)); + EXPECT_TRUE(Ranges.contains(0x1000)); + EXPECT_TRUE(Ranges.contains(0x2000)); + EXPECT_TRUE(Ranges.contains(0x4000)); + EXPECT_TRUE(Ranges.contains(0x2000 - 1)); + EXPECT_TRUE(Ranges.contains(0x3000 - 1)); + EXPECT_FALSE(Ranges.contains(0x3000 + 1)); + EXPECT_TRUE(Ranges.contains(0x5000 - 1)); + 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(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)); + EXPECT_EQ(Ranges.size(), 2u); + EXPECT_EQ(Ranges[0], AddressRange(0x1000, 0x2000)); + EXPECT_EQ(Ranges[1], AddressRange(0x2000, 0x3000)); + // 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)); + + 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)); +} diff --git a/llvm/unittests/Support/CMakeLists.txt b/llvm/unittests/Support/CMakeLists.txt --- a/llvm/unittests/Support/CMakeLists.txt +++ b/llvm/unittests/Support/CMakeLists.txt @@ -3,6 +3,7 @@ ) add_llvm_unittest(SupportTests + AddressRangeTest.cpp AlignmentTest.cpp AlignOfTest.cpp AllocatorTest.cpp