| //===- 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; |
| } |
