diff options
Diffstat (limited to 'lib/DebugInfo/GSYM/LineTable.cpp')
| -rw-r--r-- | lib/DebugInfo/GSYM/LineTable.cpp | 287 |
1 files changed, 287 insertions, 0 deletions
diff --git a/lib/DebugInfo/GSYM/LineTable.cpp b/lib/DebugInfo/GSYM/LineTable.cpp new file mode 100644 index 000000000000..824c0041be9f --- /dev/null +++ b/lib/DebugInfo/GSYM/LineTable.cpp @@ -0,0 +1,287 @@ +//===- LineTable.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/LineTable.h" +#include "llvm/DebugInfo/GSYM/FileWriter.h" +#include "llvm/Support/DataExtractor.h" + +using namespace llvm; +using namespace gsym; + +enum LineTableOpCode { + EndSequence = 0x00, ///< End of the line table. + SetFile = 0x01, ///< Set LineTableRow.file_idx, don't push a row. + AdvancePC = 0x02, ///< Increment LineTableRow.address, and push a row. + AdvanceLine = 0x03, ///< Set LineTableRow.file_line, don't push a row. + FirstSpecial = 0x04, ///< All special opcodes push a row. +}; + +struct DeltaInfo { + int64_t Delta; + uint32_t Count; + DeltaInfo(int64_t D, uint32_t C) : Delta(D), Count(C) {} +}; + +inline bool operator<(const DeltaInfo &LHS, int64_t Delta) { + return LHS.Delta < Delta; +} + +static bool encodeSpecial(int64_t MinLineDelta, int64_t MaxLineDelta, + int64_t LineDelta, uint64_t AddrDelta, + uint8_t &SpecialOp) { + if (LineDelta < MinLineDelta) + return false; + if (LineDelta > MaxLineDelta) + return false; + int64_t LineRange = MaxLineDelta - MinLineDelta + 1; + int64_t AdjustedOp = ((LineDelta - MinLineDelta) + AddrDelta * LineRange); + int64_t Op = AdjustedOp + FirstSpecial; + if (Op < 0) + return false; + if (Op > 255) + return false; + SpecialOp = (uint8_t)Op; + return true; +} + +typedef std::function<bool(const LineEntry &Row)> LineEntryCallback; + +static llvm::Error parse(DataExtractor &Data, uint64_t BaseAddr, + LineEntryCallback const &Callback) { + uint64_t Offset = 0; + if (!Data.isValidOffset(Offset)) + return createStringError(std::errc::io_error, + "0x%8.8" PRIx64 ": missing LineTable MinDelta", Offset); + int64_t MinDelta = Data.getSLEB128(&Offset); + if (!Data.isValidOffset(Offset)) + return createStringError(std::errc::io_error, + "0x%8.8" PRIx64 ": missing LineTable MaxDelta", Offset); + int64_t MaxDelta = Data.getSLEB128(&Offset); + int64_t LineRange = MaxDelta - MinDelta + 1; + if (!Data.isValidOffset(Offset)) + return createStringError(std::errc::io_error, + "0x%8.8" PRIx64 ": missing LineTable FirstLine", Offset); + const uint32_t FirstLine = (uint32_t)Data.getULEB128(&Offset); + LineEntry Row(BaseAddr, 1, FirstLine); + bool Done = false; + while (!Done) { + if (!Data.isValidOffset(Offset)) + return createStringError(std::errc::io_error, + "0x%8.8" PRIx64 ": EOF found before EndSequence", Offset); + uint8_t Op = Data.getU8(&Offset); + switch (Op) { + case EndSequence: + Done = true; + break; + case SetFile: + if (!Data.isValidOffset(Offset)) + return createStringError(std::errc::io_error, + "0x%8.8" PRIx64 ": EOF found before SetFile value", + Offset); + Row.File = (uint32_t)Data.getULEB128(&Offset); + break; + case AdvancePC: + if (!Data.isValidOffset(Offset)) + return createStringError(std::errc::io_error, + "0x%8.8" PRIx64 ": EOF found before AdvancePC value", + Offset); + Row.Addr += Data.getULEB128(&Offset); + // If the function callback returns false, we stop parsing. + if (Callback(Row) == false) + return Error::success(); + break; + case AdvanceLine: + if (!Data.isValidOffset(Offset)) + return createStringError(std::errc::io_error, + "0x%8.8" PRIx64 ": EOF found before AdvanceLine value", + Offset); + Row.Line += Data.getSLEB128(&Offset); + break; + default: { + // A byte that contains both address and line increment. + uint8_t AdjustedOp = Op - FirstSpecial; + int64_t LineDelta = MinDelta + (AdjustedOp % LineRange); + uint64_t AddrDelta = (AdjustedOp / LineRange); + Row.Line += LineDelta; + Row.Addr += AddrDelta; + // If the function callback returns false, we stop parsing. + if (Callback(Row) == false) + return Error::success(); + break; + } + } + } + return Error::success(); +} + +llvm::Error LineTable::encode(FileWriter &Out, uint64_t BaseAddr) const { + // Users must verify the LineTable is valid prior to calling this funtion. + // We don't want to emit any LineTable objects if they are not valid since + // it will waste space in the GSYM file. + if (!isValid()) + return createStringError(std::errc::invalid_argument, + "attempted to encode invalid LineTable object"); + + int64_t MinLineDelta = INT64_MAX; + int64_t MaxLineDelta = INT64_MIN; + std::vector<DeltaInfo> DeltaInfos; + if (Lines.size() == 1) { + MinLineDelta = 0; + MaxLineDelta = 0; + } else { + int64_t PrevLine = 1; + bool First = true; + for (const auto &line_entry : Lines) { + if (First) + First = false; + else { + int64_t LineDelta = (int64_t)line_entry.Line - PrevLine; + auto End = DeltaInfos.end(); + auto Pos = std::lower_bound(DeltaInfos.begin(), End, LineDelta); + if (Pos != End && Pos->Delta == LineDelta) + ++Pos->Count; + else + DeltaInfos.insert(Pos, DeltaInfo(LineDelta, 1)); + if (LineDelta < MinLineDelta) + MinLineDelta = LineDelta; + if (LineDelta > MaxLineDelta) + MaxLineDelta = LineDelta; + } + PrevLine = (int64_t)line_entry.Line; + } + assert(MinLineDelta <= MaxLineDelta); + } + // Set the min and max line delta intelligently based on the counts of + // the line deltas. if our range is too large. + const int64_t MaxLineRange = 14; + if (MaxLineDelta - MinLineDelta > MaxLineRange) { + uint32_t BestIndex = 0; + uint32_t BestEndIndex = 0; + uint32_t BestCount = 0; + const size_t NumDeltaInfos = DeltaInfos.size(); + for (uint32_t I = 0; I < NumDeltaInfos; ++I) { + const int64_t FirstDelta = DeltaInfos[I].Delta; + uint32_t CurrCount = 0; + uint32_t J; + for (J = I; J < NumDeltaInfos; ++J) { + auto LineRange = DeltaInfos[J].Delta - FirstDelta; + if (LineRange > MaxLineRange) + break; + CurrCount += DeltaInfos[J].Count; + } + if (CurrCount > BestCount) { + BestIndex = I; + BestEndIndex = J - 1; + BestCount = CurrCount; + } + } + MinLineDelta = DeltaInfos[BestIndex].Delta; + MaxLineDelta = DeltaInfos[BestEndIndex].Delta; + } + if (MinLineDelta == MaxLineDelta && MinLineDelta > 0 && + MinLineDelta < MaxLineRange) + MinLineDelta = 0; + assert(MinLineDelta <= MaxLineDelta); + + // Initialize the line entry state as a starting point. All line entries + // will be deltas from this. + LineEntry Prev(BaseAddr, 1, Lines.front().Line); + + // Write out the min and max line delta as signed LEB128. + Out.writeSLEB(MinLineDelta); + Out.writeSLEB(MaxLineDelta); + // Write out the starting line number as a unsigned LEB128. + Out.writeULEB(Prev.Line); + + for (const auto &Curr : Lines) { + if (Curr.Addr < BaseAddr) + return createStringError(std::errc::invalid_argument, + "LineEntry has address 0x%" PRIx64 " which is " + "less than the function start address 0x%" + PRIx64, Curr.Addr, BaseAddr); + if (Curr.Addr < Prev.Addr) + return createStringError(std::errc::invalid_argument, + "LineEntry in LineTable not in ascending order"); + const uint64_t AddrDelta = Curr.Addr - Prev.Addr; + int64_t LineDelta = 0; + if (Curr.Line > Prev.Line) + LineDelta = Curr.Line - Prev.Line; + else if (Prev.Line > Curr.Line) + LineDelta = -((int32_t)(Prev.Line - Curr.Line)); + + // Set the file if it doesn't match the current one. + if (Curr.File != Prev.File) { + Out.writeU8(SetFile); + Out.writeULEB(Curr.File); + } + + uint8_t SpecialOp; + if (encodeSpecial(MinLineDelta, MaxLineDelta, LineDelta, AddrDelta, + SpecialOp)) { + // Advance the PC and line and push a row. + Out.writeU8(SpecialOp); + } else { + // We can't encode the address delta and line delta into + // a single special opcode, we must do them separately. + + // Advance the line. + if (LineDelta != 0) { + Out.writeU8(AdvanceLine); + Out.writeSLEB(LineDelta); + } + + // Advance the PC and push a row. + Out.writeU8(AdvancePC); + Out.writeULEB(AddrDelta); + } + Prev = Curr; + } + Out.writeU8(EndSequence); + return Error::success(); +} + +// Parse all line table entries into the "LineTable" vector. We can +// cache the results of this if needed, or we can call LineTable::lookup() +// below. +llvm::Expected<LineTable> LineTable::decode(DataExtractor &Data, + uint64_t BaseAddr) { + LineTable LT; + llvm::Error Err = parse(Data, BaseAddr, [&](const LineEntry &Row) -> bool { + LT.Lines.push_back(Row); + return true; // Keep parsing by returning true. + }); + if (Err) + return std::move(Err); + return LT; +} +// Parse the line table on the fly and find the row we are looking for. +// We will need to determine if we need to cache the line table by calling +// LineTable::parseAllEntries(...) or just call this function each time. +// There is a CPU vs memory tradeoff we will need to determine. +LineEntry LineTable::lookup(DataExtractor &Data, uint64_t BaseAddr, uint64_t Addr) { + LineEntry Result; + llvm::Error Err = parse(Data, BaseAddr, + [Addr, &Result](const LineEntry &Row) -> bool { + if (Addr < Row.Addr) + return false; // Stop parsing, result contains the line table row! + Result = Row; + if (Addr == Row.Addr) { + // Stop parsing, this is the row we are looking for since the address + // matches. + return false; + } + return true; // Keep parsing till we find the right row. + }); + return Result; +} + +raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const LineTable <) { + for (const auto &LineEntry : LT) + OS << LineEntry << '\n'; + return OS; +} |