1 files changed, 287 insertions, 0 deletions
diff --git a/llvm/lib/DebugInfo/GSYM/LineTable.cpp b/llvm/lib/DebugInfo/GSYM/LineTable.cpp
new file mode 100644
index 0000000000000..824c0041be9fb
--- /dev/null
+++ b/llvm/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 &LT) {
+  for (const auto &LineEntry : LT)
+    OS << LineEntry << '\n';
+  return OS;
+}