Add a LineTable class to GSYM and test it.

[clayborg]

Summary

The full GSYM patch started with: https://reviews.llvm.org/D53379

This patch adds the ability to create a gsym::LineTable object, populate it, encode and decode it and test all functionality.

The full format of the LineTable encoding is specified in the header file LineTable.h.

[clayborg]

Add full error handling to encoding and decoding in the same way that I did it in https://reviews.llvm.org/D66600.

[clayborg]

Does anyone have a chance to look at this? Full documentation on the line table encoding is in the LineTable.h header file in the comments.

[aprantl]

include/llvm/DebugInfo/GSYM/FunctionInfo.h

47

I know I'm asking this at every patch, but: Why isn't this an Optional<LineTable> and why does it have to have a clear() method?

lib/DebugInfo/GSYM/LineTable.cpp

6

Wrong license.

19

I think the LTOC_ prefix is redundant?

36

LLVM wants camel case

124

Could this return an Expected<LineTable> instead?

[clayborg]

include/llvm/DebugInfo/GSYM/FunctionInfo.h

47

If LineTable and Inline are optional is really complicated the operator == and operator < functions. Also we populate a FunctionInfo object from debug info so it is nice to just use the objects that are in the FunctionInfo and not have to make a temp and move it into the FunctionInfo object. So it was to keep the code simpler. If you really want the optionals here I can add them, but it does make the operator functions less readable and harder to implement.

lib/DebugInfo/GSYM/LineTable.cpp

19

will remove.

124

This is the encoding function. It takes an existing LineTable objects and encodes it. The decode function is static and does return a Expected<LineTable>. So we only need an error back if it fails to encode right?

[clayborg]

• Fixed license on LineTable.h/.cpp
• Fixed camel case on encode_special
• Remote LTOC_ prefix from LineTableOpCode enumerators

[aprantl]

include/llvm/DebugInfo/GSYM/FunctionInfo.h

47

If LineTable and Inline are optional is really complicated the operator == and operator < functions.

operator== should fall out automatically out of Optional's operator== implementation, same for operator<.

Also we populate a FunctionInfo object from debug info so it is nice to just use the objects that are in the FunctionInfo and not have to make a temp and move it into the FunctionInfo object.

Are you worried about an extra copy operation? Couldn't you still construct it in-place through RVO?

My meta point here is that we have an abstraction for things that may be invalid in LLVM (and C++17) and that is Optional. When classes roll their own implementation of Optional via isValid() methods then users of these objects need to know about it and will almost inevitably forget the check validity at some point in the future, whereas Optional forces them to think about this when they write code that uses the class.

[clayborg]

Switch LineTable and InlineInfo inside of FunctionInfo to be Optional<T>.

[aprantl]

Thanks!

include/llvm/DebugInfo/GSYM/FunctionInfo.h

70

Obviously it would be great if FunctionInfo itself could also be all-or-nothing (ie.. Optional).

lib/DebugInfo/GSYM/LineTable.cpp

226

.

230

.

232

. (etc)

[clayborg]

$ svn commit
Sending include/llvm/DebugInfo/GSYM/FunctionInfo.h
Adding include/llvm/DebugInfo/GSYM/LineTable.h
Sending lib/DebugInfo/GSYM/CMakeLists.txt
Sending lib/DebugInfo/GSYM/FunctionInfo.cpp
Adding lib/DebugInfo/GSYM/LineTable.cpp
Sending unittests/DebugInfo/GSYM/GSYMTest.cpp
Transmitting file data ......done
Committing transaction...
Committed revision 371657.

include/llvm/DebugInfo/GSYM/FunctionInfo.h

47

Sounds good. I will make the changes.

[loladiro]

This broke the build for me locally:

In file included from /home/keno/llvm-project/llvm/lib/DebugInfo/GSYM/FunctionInfo.cpp:10:0:
/home/keno/llvm-project/llvm/include/llvm/DebugInfo/GSYM/FunctionInfo.h:36:29: error: declaration of ‘llvm::Optional<llvm::gsym::LineTable> llvm::gsym::FunctionInfo::LineTable’ [-fpermissive]
   llvm::Optional<LineTable> LineTable;
                             ^~~~~~~~~
In file included from /home/keno/llvm-project/llvm/include/llvm/DebugInfo/GSYM/FunctionInfo.h:14:0,
                 from /home/keno/llvm-project/llvm/lib/DebugInfo/GSYM/FunctionInfo.cpp:10:
/home/keno/llvm-project/llvm/include/llvm/DebugInfo/GSYM/LineTable.h:118:7: error: changes meaning of ‘LineTable’ from ‘class llvm::gsym::LineTable’ [-fpermissive]
 class LineTable {
       ^~~~~~~~~
[720/3364] Building CXX object lib/Analysis/CMakeFiles/LLVMAnalysis.dir/ScalarEvolution.cpp.o

include/llvm/DebugInfo/GSYM/FunctionInfo.h

 //===- FunctionInfo.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_FUNCTIONINFO_H
 #define LLVM_DEBUGINFO_GSYM_FUNCTIONINFO_H
 
+#include "llvm/ADT/Optional.h"
 #include "llvm/DebugInfo/GSYM/InlineInfo.h"
-#include "llvm/DebugInfo/GSYM/LineEntry.h"
+#include "llvm/DebugInfo/GSYM/LineTable.h"
 #include "llvm/DebugInfo/GSYM/Range.h"
 #include "llvm/DebugInfo/GSYM/StringTable.h"
 #include <tuple>
 #include <vector>
 
 namespace llvm {
 class raw_ostream;
 namespace gsym {
 
 /// Function information in GSYM files encodes information for one
 /// contiguous address range. The name of the function is encoded as
 /// a string table offset and allows multiple functions with the same
 /// name to share the name string in the string table. Line tables are
 /// stored in a sorted vector of gsym::LineEntry objects and are split
 /// into line tables for each function. If a function has a discontiguous
 /// range, it will be split into two gsym::FunctionInfo objects. If the
 /// function has inline functions, the information will be encoded in
 /// the "Inline" member, see gsym::InlineInfo for more information.
 struct FunctionInfo {
   AddressRange Range;
   uint32_t Name; ///< String table offset in the string table.
-  std::vector<gsym::LineEntry> Lines;
-  InlineInfo Inline;
+  llvm::Optional<LineTable> LineTable;
+  llvm::Optional<InlineInfo> Inline;
 
   FunctionInfo(uint64_t Addr = 0, uint64_t Size = 0, uint32_t N = 0)
       : Range(Addr, Addr + Size), Name(N) {}
 
   bool hasRichInfo() const {
     /// Returns whether we have something else than range and name. When
     /// converting information from a symbol table and from debug info, we
     /// might end up with multiple FunctionInfo objects for the same range
     /// and we need to be able to tell which one is the better object to use.
-    return !Lines.empty() || Inline.isValid();
+    return LineTable.hasValue() || Inline.hasValue();
   }
 
   bool isValid() const {
     /// Address and size can be zero and there can be no line entries for a
     /// symbol so the only indication this entry is valid is if the name is
     /// not zero. This can happen when extracting information from symbol
     /// tables that do not encode symbol sizes. In that case only the
     /// address and name will be filled in.
     return Name != 0;
   }
 
   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};
     Name = 0;
-    Lines.clear();
-    Inline.clear();
+    LineTable = llvm::None;
+    Inline = llvm::None;
   }
 };
 
 inline bool operator==(const FunctionInfo &LHS, const FunctionInfo &RHS) {
   return LHS.Range == RHS.Range && LHS.Name == RHS.Name &&
-         LHS.Lines == RHS.Lines && LHS.Inline == RHS.Inline;
+         LHS.LineTable == RHS.LineTable && LHS.Inline == RHS.Inline;
 }
 inline bool operator!=(const FunctionInfo &LHS, const FunctionInfo &RHS) {
   return !(LHS == RHS);
 }
 /// This sorting will order things consistently by address range first, but then
 /// followed by inlining being valid and line tables. We might end up with a
 /// FunctionInfo from debug info that will have the same range as one from the
 /// symbol table, but we want to quickly be able to sort and use the best version
 /// when creating the final GSYM file.
 inline bool operator<(const FunctionInfo &LHS, const FunctionInfo &RHS) {
   // First sort by address range
   if (LHS.Range != RHS.Range)
     return LHS.Range < RHS.Range;
 
   // Then sort by inline
-  if (LHS.Inline.isValid() != RHS.Inline.isValid())
-    return RHS.Inline.isValid();
+  if (LHS.Inline.hasValue() != RHS.Inline.hasValue())
+    return RHS.Inline.hasValue();
 
-  // If the number of lines is the same, then compare line table entries
-  if (LHS.Lines.size() == RHS.Lines.size())
-    return LHS.Lines < RHS.Lines;
-  // Then sort by number of line table entries (more is better)
-  return LHS.Lines.size() < RHS.Lines.size();
+  return LHS.LineTable < RHS.LineTable;
 }
 
 raw_ostream &operator<<(raw_ostream &OS, const FunctionInfo &R);
 
 } // namespace gsym
 } // namespace llvm
 
 #endif // #ifndef LLVM_DEBUGINFO_GSYM_FUNCTIONINFO_H

include/llvm/DebugInfo/GSYM/LineTable.h

+//===- LineTable.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_LINETABLE_H
+#define LLVM_DEBUGINFO_GSYM_LINETABLE_H
+
+#include "llvm/DebugInfo/GSYM/LineEntry.h"
+#include "llvm/Support/Error.h"
+#include <cstdint>
+#include <vector>
+
+namespace llvm {
+namespace gsym {
+
+struct FunctionInfo;
+class FileWriter;
+
+/// LineTable class contains deserialized versions of line tables for each
+/// function's address ranges.
+///
+/// When saved to disk, the line table is encoded using a modified version of
+/// the DWARF line tables that only tracks address to source file and line.
+///
+/// ENCODING
+///
+/// The line table starts with a small prolog that contains the following
+/// values:
+///
+/// ENCODING NAME        DESCRIPTION
+/// ======== =========== ====================================================
+/// SLEB     MinDelta    The min line delta for special opcodes that  advance
+///                      the address and line number.
+/// SLEB     MaxDelta    The max line delta for single byte opcodes that
+///                      advance the address and line number.
+/// ULEB     FirstLine   The value of the first source line number to
+///                      initialize the LineEntry with.
+///
+/// Once these prolog items are read, we initialize a LineEntry struct with
+/// the start address of the function from the FunctionInfo's address range,
+/// a default file index of 1, and the line number set to "FirstLine" from
+/// the prolog above:
+///
+///   LineEntry Row(BaseAddr, 1, FirstLine);
+///
+/// The line table state machine is now initialized and ready to be parsed.
+/// The stream that follows this encodes the line entries in a compact
+/// form. Some opcodes cause "Row" to be modified and some opcodes may also
+/// push "Row" onto the end of the "LineTable.Lines" vector. The end result
+/// is a vector of LineEntry structs that is sorted in ascending address
+/// order.
+///
+/// NORMAL OPCODES
+///
+/// The opcodes 0 through 3 are normal in opcodes. Their encoding and
+/// descriptions are listed below:
+///
+/// ENCODING ENUMERATION       VALUE DESCRIPTION
+/// ======== ================  ===== ========================================
+///          LTOC_EndSequence  0x00  Parsing is done.
+/// ULEB     LTOC_SetFile      0x01  Row.File = ULEB
+/// ULEB     LTOC_AdvancePC    0x02  Row.Addr += ULEB, push "Row".
+/// SLEB     LTOC_AdvanceLine  0x03  Row.Line += SLEB
+///          LTOC_FirstSpecial 0x04  First special opcode (see SPECIAL
+///                                  OPCODES below).
+///
+/// SPECIAL OPCODES
+///
+/// Opcodes LTOC_FirstSpecial through 255 are special opcodes that always
+/// increment both the Row.Addr and Row.Line and push "Row" onto the
+/// LineEntry.Lines array. They do this by using some of the bits to
+/// increment/decrement the source line number, and some of the bits to
+/// increment the address. Line numbers can go up or down when making line
+/// tables, where addresses always only increase since line tables are sorted
+/// by address.
+///
+/// In order to calculate the amount to increment the line and address for
+/// these special opcodes, we calculate the number of values reserved for the
+/// line increment/decrement using the "MinDelta" and "MaxDelta" from the
+/// prolog:
+///
+///     const int64_t LineRange = MaxDelta - MinDelta + 1;
+///
+/// Then we can adjust the opcode to not include any of the normal opcodes:
+///
+///     const uint8_t AdjustedOp = Opcode - LTOC_FirstSpecial;
+///
+/// And we can calculate the line offset, and address offset:
+///
+///     const int64_t LineDelta = MinDelta + (AdjustedOp % LineRange);
+///     const uint64_t AddrDelta = (AdjustedOp / LineRange);
+///
+/// And use these to modify our "Row":
+///
+///     Row.Line += LineDelta;
+///     Row.Addr += AddrDelta;
+///
+/// And push a row onto the line table:
+///
+///     Lines.push_back(Row);
+///
+/// This is verify similar to the way that DWARF encodes its line tables. The
+/// only difference is the DWARF line tables have more normal opcodes and the
+/// "Row" contains more members, like source column number, bools for end of
+/// prologue, beginnging of epilogue, is statement and many others. There are
+/// also more complex rules that happen for the extra normal opcodes. By
+/// leaving these extra opcodes out, we leave more bits for the special
+/// opcodes that allows us to encode line tables in fewer bytes than standard
+/// DWARF encodings.
+///
+/// Opcodes that will push "Row" onto the LineEntry.Lines include the
+/// LTOC_AdvancePC opcode and all special opcodes. All other opcodes
+/// only modify the current "Row", or cause the line table to end.
+class LineTable {
+  typedef std::vector<gsym::LineEntry> Collection;
+  Collection Lines; ///< All line entries in the line table.
+public:
+  static LineEntry lookup(DataExtractor &Data, uint64_t BaseAddr,
+                          uint64_t Addr);
+
+  /// Decode an LineTable object from a binary data stream.
+  ///
+  /// \param Data The binary stream to read the data from. This object must
+  /// have the data for the LineTable object starting at offset zero. The data
+  /// can contain more data than needed.
+  ///
+  /// \param BaseAddr The base address to use when decoding the line table.
+  /// This will be the FunctionInfo's start address and will be used to
+  /// initialize the line table row prior to parsing any opcodes.
+  ///
+  /// \returns An LineTable or an error describing the issue that was
+  /// encountered during decoding.
+  static llvm::Expected<LineTable> decode(DataExtractor &Data,
+                                          uint64_t BaseAddr);
+  /// Encode this LineTable object into FileWriter stream.
+  ///
+  /// \param O The binary stream to write the data to at the current file
+  /// position.
+  ///
+  /// \param BaseAddr The base address to use when decoding the line table.
+  /// This will be the FunctionInfo's start address.
+  ///
+  /// \returns An error object that indicates success or failure or the
+  /// encoding process.
+  llvm::Error encode(FileWriter &O, uint64_t BaseAddr) const;
+  bool empty() const { return Lines.empty(); }
+  void clear() { Lines.clear(); }
+  void push(const LineEntry &LE) {
+    Lines.push_back(LE);
+  }
+  size_t isValid() const {
+    return !Lines.empty();
+  }
+  size_t size() const {
+    return Lines.size();
+  }
+  LineEntry &get(size_t i) {
+    assert(i < Lines.size());
+    return Lines[i];
+  }
+  const LineEntry &get(size_t i) const {
+    assert(i < Lines.size());
+    return Lines[i];
+  }
+  LineEntry &operator[](size_t i) {
+    return get(i);
+  }
+  const LineEntry &operator[](size_t i) const {
+    return get(i);
+  }
+  bool operator==(const LineTable &RHS) const {
+    return Lines == RHS.Lines;
+  }
+  bool operator!=(const LineTable &RHS) const {
+    return Lines != RHS.Lines;
+  }
+  bool operator<(const LineTable &RHS) const {
+    const auto LHSSize = Lines.size();
+    const auto RHSSize = RHS.Lines.size();
+    if (LHSSize == RHSSize)
+      return Lines < RHS.Lines;
+    return LHSSize < RHSSize;
+  }
+  Collection::const_iterator begin() const { return Lines.begin(); }
+  Collection::const_iterator end() const { return Lines.end(); }
+
+};
+
+raw_ostream &operator<<(raw_ostream &OS, const gsym::LineTable &LT);
+
+} // namespace gsym
+} // namespace llvm
+
+#endif // #ifndef LLVM_DEBUGINFO_GSYM_LINETABLE_H

lib/DebugInfo/GSYM/CMakeLists.txt

 add_llvm_library(LLVMDebugInfoGSYM
   FileWriter.cpp
   FunctionInfo.cpp
   InlineInfo.cpp
+  LineTable.cpp
   Range.cpp
 
   ADDITIONAL_HEADER_DIRS
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/DebugInfo/GSYM
   ${LLVM_MAIN_INCLUDE_DIR}/llvm/DebugInfo
   )

lib/DebugInfo/GSYM/FunctionInfo.cpp

 //===- FunctionInfo.cpp -----------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/DebugInfo/GSYM/FunctionInfo.h"
 
 using namespace llvm;
 using namespace gsym;
 
 raw_ostream &llvm::gsym::operator<<(raw_ostream &OS, const FunctionInfo &FI) {
   OS << '[' << HEX64(FI.Range.Start) << '-' << HEX64(FI.Range.End) << "): "
-     << "Name=" << HEX32(FI.Name) << '\n';
-  for (const auto &Line : FI.Lines)
-    OS << Line << '\n';
-  OS << FI.Inline;
+     << "Name=" << HEX32(FI.Name) << '\n' << FI.LineTable << FI.Inline;
   return OS;
 }

lib/DebugInfo/GSYM/LineTable.cpp

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

unittests/DebugInfo/GSYM/GSYMTest.cpp

TEST(GSYMTest, TestFunctionInfo) {
   FunctionInfo FI(StartAddr, Size, NameOffset);
   EXPECT_TRUE(FI.isValid());
   EXPECT_FALSE(FI.hasRichInfo());
   EXPECT_EQ(FI.startAddress(), StartAddr);
   EXPECT_EQ(FI.endAddress(), EndAddr);
   EXPECT_EQ(FI.size(), Size);
   const uint32_t FileIdx = 1;
   const uint32_t Line = 12;
-  FI.Lines.push_back(LineEntry(StartAddr, FileIdx, Line));
+  FI.LineTable = LineTable();
+  FI.LineTable->push(LineEntry(StartAddr,FileIdx,Line));
   EXPECT_TRUE(FI.hasRichInfo());
   FI.clear();
   EXPECT_FALSE(FI.isValid());
   EXPECT_FALSE(FI.hasRichInfo());
 
   FunctionInfo A1(0x1000, 0x100, NameOffset);
   FunctionInfo A2(0x1000, 0x100, NameOffset);
   FunctionInfo B;
TEST(GSYMTest, TestFunctionInfo) {
   EXPECT_LT(A1, B);
 
   // We use the < operator to take a variety of different FunctionInfo
   // structs from a variety of sources: symtab, debug info, runtime info
   // and we sort them and want the sorting to allow us to quickly get the
   // best version of a function info.
   FunctionInfo FISymtab(StartAddr, Size, NameOffset);
   FunctionInfo FIWithLines(StartAddr, Size, NameOffset);
-  FIWithLines.Lines.push_back(LineEntry(StartAddr, FileIdx, Line));
+  FIWithLines.LineTable = LineTable();
+  FIWithLines.LineTable->push(LineEntry(StartAddr,FileIdx,Line));
   // Test that a FunctionInfo with just a name and size is less than one
   // that has name, size and any number of line table entries
   EXPECT_LT(FISymtab, FIWithLines);
 
   FunctionInfo FIWithLinesAndInline = FIWithLines;
-  FIWithLinesAndInline.Inline.Ranges.insert(
+  FIWithLinesAndInline.Inline = InlineInfo();
+  FIWithLinesAndInline.Inline->Ranges.insert(
       AddressRange(StartAddr, StartAddr + 0x10));
   // Test that a FunctionInfo with name, size, and line entries is less than
   // the same one with valid inline info
   EXPECT_LT(FIWithLines, FIWithLinesAndInline);
 
   // Test if we have an entry with lines and one with more lines for the same
   // range, the ones with more lines is greater than the one with less.
   FunctionInfo FIWithMoreLines = FIWithLines;
-  FIWithMoreLines.Lines.push_back(LineEntry(StartAddr, FileIdx, Line + 5));
+  FIWithMoreLines.LineTable->push(LineEntry(StartAddr,FileIdx,Line+5));
   EXPECT_LT(FIWithLines, FIWithMoreLines);
 
   // Test that if we have the same number of lines we compare the line entries
-  // in the FunctionInfo.Lines vector.
+  // in the FunctionInfo.LineTable.Lines vector.
   FunctionInfo FIWithLinesWithHigherAddress = FIWithLines;
-  FIWithLinesWithHigherAddress.Lines[0].Addr += 0x10;
+  FIWithLinesWithHigherAddress.LineTable->get(0).Addr += 0x10;
   EXPECT_LT(FIWithLines, FIWithLinesWithHigherAddress);
 }
 
 void checkError(ArrayRef<std::string> ExpectedMsgs, Error Err) {
   ASSERT_TRUE(Err.operator bool());
   size_t WhichMsg = 0;
   Error Remaining =
       handleErrors(std::move(Err), [&](const ErrorInfoBase &Actual) {
TEST(GSYMTest, TestAddressRangesEncodeDecode) {
   Ranges.insert(AddressRange(0x1000, 0x1010));
   TestAddressRangeEncodeDecodeHelper(Ranges, BaseAddr);
 
   // Test encoding and decoding with multiple ranges.
   Ranges.insert(AddressRange(0x1020, 0x1030));
   Ranges.insert(AddressRange(0x1050, 0x1070));
   TestAddressRangeEncodeDecodeHelper(Ranges, BaseAddr);
 }
+
+static void TestLineTableHelper(llvm::support::endianness ByteOrder,
+                                const LineTable &LT) {
+  SmallString<512> Str;
+  raw_svector_ostream OutStrm(Str);
+  FileWriter FW(OutStrm, ByteOrder);
+  const uint64_t BaseAddr = LT[0].Addr;
+  llvm::Error Err = LT.encode(FW, BaseAddr);
+  ASSERT_FALSE(Err);
+  std::string Bytes(OutStrm.str());
+  uint8_t AddressSize = 4;
+  DataExtractor Data(Bytes, ByteOrder == llvm::support::little, AddressSize);
+  llvm::Expected<LineTable> Decoded = LineTable::decode(Data, BaseAddr);
+  // Make sure decoding succeeded.
+  ASSERT_TRUE((bool)Decoded);
+  // Make sure decoded object is the same as the one we encoded.
+  EXPECT_EQ(LT, Decoded.get());
+}
+
+TEST(GSYMTest, TestLineTable) {
+  const uint64_t StartAddr = 0x1000;
+  const uint32_t FileIdx = 1;
+  LineTable LT;
+  LineEntry Line0(StartAddr+0x000, FileIdx, 10);
+  LineEntry Line1(StartAddr+0x010, FileIdx, 11);
+  LineEntry Line2(StartAddr+0x100, FileIdx, 1000);
+  ASSERT_TRUE(LT.empty());
+  ASSERT_EQ(LT.size(), (size_t)0);
+  LT.push(Line0);
+  ASSERT_EQ(LT.size(), (size_t)1);
+  LT.push(Line1);
+  LT.push(Line2);
+  LT.push(LineEntry(StartAddr+0x120, FileIdx, 900));
+  LT.push(LineEntry(StartAddr+0x120, FileIdx, 2000));
+  LT.push(LineEntry(StartAddr+0x121, FileIdx, 2001));
+  LT.push(LineEntry(StartAddr+0x122, FileIdx, 2002));
+  LT.push(LineEntry(StartAddr+0x123, FileIdx, 2003));
+  ASSERT_FALSE(LT.empty());
+  ASSERT_EQ(LT.size(), (size_t)8);
+  // Test operator[].
+  ASSERT_EQ(LT[0], Line0);
+  ASSERT_EQ(LT[1], Line1);
+  ASSERT_EQ(LT[2], Line2);
+
+  // Test encoding and decoding line tables.
+  TestLineTableHelper(llvm::support::little, LT);
+  TestLineTableHelper(llvm::support::big, LT);
+
+  // Verify the clear method works as expected.
+  LT.clear();
+  ASSERT_TRUE(LT.empty());
+  ASSERT_EQ(LT.size(), (size_t)0);
+
+  LineTable LT1;
+  LineTable LT2;
+
+  // Test that two empty line tables are equal and neither are less than
+  // each other.
+  ASSERT_EQ(LT1, LT2);
+  ASSERT_FALSE(LT1 < LT2);
+  ASSERT_FALSE(LT2 < LT2);
+
+  // Test that a line table with less number of line entries is less than a
+  // line table with more line entries and that they are not equal.
+  LT2.push(Line0);
+  ASSERT_LT(LT1, LT2);
+  ASSERT_NE(LT1, LT2);
+
+  // Test that two line tables with the same entries are equal.
+  LT1.push(Line0);
+  ASSERT_EQ(LT1, LT2);
+  ASSERT_FALSE(LT1 < LT2);
+  ASSERT_FALSE(LT2 < LT2);
+}
+
+static void TestLineTableDecodeError(llvm::support::endianness ByteOrder,
+                                     std::string Bytes,
+                                     const uint64_t BaseAddr,
+                                     std::string ExpectedErrorMsg) {
+  uint8_t AddressSize = 4;
+  DataExtractor Data(Bytes, ByteOrder == llvm::support::little, AddressSize);
+  llvm::Expected<LineTable> Decoded = LineTable::decode(Data, BaseAddr);
+  // Make sure decoding fails.
+  ASSERT_FALSE((bool)Decoded);
+  // Make sure decoded object is the same as the one we encoded.
+  checkError(ExpectedErrorMsg, Decoded.takeError());
+}
+
+TEST(GSYMTest, TestLineTableDecodeErrors) {
+  // Test decoding InlineInfo objects that ensure we report an appropriate
+  // error message.
+  const llvm::support::endianness ByteOrder = llvm::support::little;
+  SmallString<512> Str;
+  raw_svector_ostream OutStrm(Str);
+  FileWriter FW(OutStrm, ByteOrder);
+  const uint64_t BaseAddr = 0x100;
+  TestLineTableDecodeError(ByteOrder, OutStrm.str(), BaseAddr,
+      "0x00000000: missing LineTable MinDelta");
+  FW.writeU8(1); // MinDelta (ULEB)
+  TestLineTableDecodeError(ByteOrder, OutStrm.str(), BaseAddr,
+      "0x00000001: missing LineTable MaxDelta");
+  FW.writeU8(10); // MaxDelta (ULEB)
+  TestLineTableDecodeError(ByteOrder, OutStrm.str(), BaseAddr,
+      "0x00000002: missing LineTable FirstLine");
+  FW.writeU8(20); // FirstLine (ULEB)
+  TestLineTableDecodeError(ByteOrder, OutStrm.str(), BaseAddr,
+      "0x00000003: EOF found before EndSequence");
+  // Test a SetFile with the argument missing from the stream
+  FW.writeU8(1); // SetFile opcode (uint8_t)
+  TestLineTableDecodeError(ByteOrder, OutStrm.str(), BaseAddr,
+      "0x00000004: EOF found before SetFile value");
+  FW.writeU8(5); // SetFile value as index (ULEB)
+  // Test a AdvancePC with the argument missing from the stream
+  FW.writeU8(2); // AdvancePC opcode (uint8_t)
+  TestLineTableDecodeError(ByteOrder, OutStrm.str(), BaseAddr,
+      "0x00000006: EOF found before AdvancePC value");
+  FW.writeU8(20); // AdvancePC value as offset (ULEB)
+  // Test a AdvancePC with the argument missing from the stream
+  FW.writeU8(3); // AdvanceLine opcode (uint8_t)
+  TestLineTableDecodeError(ByteOrder, OutStrm.str(), BaseAddr,
+      "0x00000008: EOF found before AdvanceLine value");
+  FW.writeU8(20); // AdvanceLine value as offset (LLEB)
+}
+
+TEST(GSYMTest, TestLineTableEncodeErrors) {
+  const uint64_t BaseAddr = 0x1000;
+  const uint32_t FileIdx = 1;
+  const llvm::support::endianness ByteOrder = llvm::support::little;
+  SmallString<512> Str;
+  raw_svector_ostream OutStrm(Str);
+  FileWriter FW(OutStrm, ByteOrder);
+  LineTable LT;
+  checkError("attempted to encode invalid LineTable object",
+             LT.encode(FW, BaseAddr));
+
+  // Try to encode a line table where a line entry has an address that is less
+  // than BaseAddr and verify we get an appropriate error.
+  LineEntry Line0(BaseAddr+0x000, FileIdx, 10);
+  LineEntry Line1(BaseAddr+0x010, FileIdx, 11);
+  LT.push(Line0);
+  LT.push(Line1);
+  checkError("LineEntry has address 0x1000 which is less than the function "
+             "start address 0x1010", LT.encode(FW, BaseAddr+0x10));
+  LT.clear();
+
+  // Try to encode a line table where a line entries  has an address that is less
+  // than BaseAddr and verify we get an appropriate error.
+  LT.push(Line1);
+  LT.push(Line0);
+  checkError("LineEntry in LineTable not in ascending order",
+             LT.encode(FW, BaseAddr));
+  LT.clear();
+}