1//===- LineTable.h ----------------------------------------------*- C++ -*-===// 2// 3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4// See https://llvm.org/LICENSE.txt for license information. 5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6// 7//===----------------------------------------------------------------------===// 8 9#ifndef LLVM_DEBUGINFO_GSYM_LINETABLE_H 10#define LLVM_DEBUGINFO_GSYM_LINETABLE_H 11 12#include "llvm/DebugInfo/GSYM/LineEntry.h" 13#include "llvm/Support/Error.h" 14#include <cstdint> 15#include <vector> 16 17namespace llvm { 18namespace gsym { 19 20struct FunctionInfo; 21class FileWriter; 22 23/// LineTable class contains deserialized versions of line tables for each 24/// function's address ranges. 25/// 26/// When saved to disk, the line table is encoded using a modified version of 27/// the DWARF line tables that only tracks address to source file and line. 28/// 29/// ENCODING 30/// 31/// The line table starts with a small prolog that contains the following 32/// values: 33/// 34/// ENCODING NAME DESCRIPTION 35/// ======== =========== ==================================================== 36/// SLEB MinDelta The min line delta for special opcodes that advance 37/// the address and line number. 38/// SLEB MaxDelta The max line delta for single byte opcodes that 39/// advance the address and line number. 40/// ULEB FirstLine The value of the first source line number to 41/// initialize the LineEntry with. 42/// 43/// Once these prolog items are read, we initialize a LineEntry struct with 44/// the start address of the function from the FunctionInfo's address range, 45/// a default file index of 1, and the line number set to "FirstLine" from 46/// the prolog above: 47/// 48/// LineEntry Row(BaseAddr, 1, FirstLine); 49/// 50/// The line table state machine is now initialized and ready to be parsed. 51/// The stream that follows this encodes the line entries in a compact 52/// form. Some opcodes cause "Row" to be modified and some opcodes may also 53/// push "Row" onto the end of the "LineTable.Lines" vector. The end result 54/// is a vector of LineEntry structs that is sorted in ascending address 55/// order. 56/// 57/// NORMAL OPCODES 58/// 59/// The opcodes 0 through 3 are normal in opcodes. Their encoding and 60/// descriptions are listed below: 61/// 62/// ENCODING ENUMERATION VALUE DESCRIPTION 63/// ======== ================ ===== ======================================== 64/// LTOC_EndSequence 0x00 Parsing is done. 65/// ULEB LTOC_SetFile 0x01 Row.File = ULEB 66/// ULEB LTOC_AdvancePC 0x02 Row.Addr += ULEB, push "Row". 67/// SLEB LTOC_AdvanceLine 0x03 Row.Line += SLEB 68/// LTOC_FirstSpecial 0x04 First special opcode (see SPECIAL 69/// OPCODES below). 70/// 71/// SPECIAL OPCODES 72/// 73/// Opcodes LTOC_FirstSpecial through 255 are special opcodes that always 74/// increment both the Row.Addr and Row.Line and push "Row" onto the 75/// LineEntry.Lines array. They do this by using some of the bits to 76/// increment/decrement the source line number, and some of the bits to 77/// increment the address. Line numbers can go up or down when making line 78/// tables, where addresses always only increase since line tables are sorted 79/// by address. 80/// 81/// In order to calculate the amount to increment the line and address for 82/// these special opcodes, we calculate the number of values reserved for the 83/// line increment/decrement using the "MinDelta" and "MaxDelta" from the 84/// prolog: 85/// 86/// const int64_t LineRange = MaxDelta - MinDelta + 1; 87/// 88/// Then we can adjust the opcode to not include any of the normal opcodes: 89/// 90/// const uint8_t AdjustedOp = Opcode - LTOC_FirstSpecial; 91/// 92/// And we can calculate the line offset, and address offset: 93/// 94/// const int64_t LineDelta = MinDelta + (AdjustedOp % LineRange); 95/// const uint64_t AddrDelta = (AdjustedOp / LineRange); 96/// 97/// And use these to modify our "Row": 98/// 99/// Row.Line += LineDelta; 100/// Row.Addr += AddrDelta; 101/// 102/// And push a row onto the line table: 103/// 104/// Lines.push_back(Row); 105/// 106/// This is verify similar to the way that DWARF encodes its line tables. The 107/// only difference is the DWARF line tables have more normal opcodes and the 108/// "Row" contains more members, like source column number, bools for end of 109/// prologue, beginnging of epilogue, is statement and many others. There are 110/// also more complex rules that happen for the extra normal opcodes. By 111/// leaving these extra opcodes out, we leave more bits for the special 112/// opcodes that allows us to encode line tables in fewer bytes than standard 113/// DWARF encodings. 114/// 115/// Opcodes that will push "Row" onto the LineEntry.Lines include the 116/// LTOC_AdvancePC opcode and all special opcodes. All other opcodes 117/// only modify the current "Row", or cause the line table to end. 118class LineTable { 119 typedef std::vector<gsym::LineEntry> Collection; 120 Collection Lines; ///< All line entries in the line table. 121public: 122 /// Lookup a single address within a line table's data. 123 /// 124 /// Clients have the option to decode an entire line table using 125 /// LineTable::decode() or just find a single matching entry using this 126 /// function. The benefit of using this function is that parsed LineEntry 127 /// objects that do not match will not be stored in an array. This will avoid 128 /// memory allocation costs and parsing can stop once a match has been found. 129 /// 130 /// \param Data The binary stream to read the data from. This object must 131 /// have the data for the LineTable object starting at offset zero. The data 132 /// can contain more data than needed. 133 /// 134 /// \param BaseAddr The base address to use when decoding the line table. 135 /// This will be the FunctionInfo's start address and will be used to 136 /// initialize the line table row prior to parsing any opcodes. 137 /// 138 /// \returns An LineEntry object if a match is found, error otherwise. 139 static Expected<LineEntry> lookup(DataExtractor &Data, uint64_t BaseAddr, 140 uint64_t Addr); 141 142 /// Decode an LineTable object from a binary data stream. 143 /// 144 /// \param Data The binary stream to read the data from. This object must 145 /// have the data for the LineTable object starting at offset zero. The data 146 /// can contain more data than needed. 147 /// 148 /// \param BaseAddr The base address to use when decoding the line table. 149 /// This will be the FunctionInfo's start address and will be used to 150 /// initialize the line table row prior to parsing any opcodes. 151 /// 152 /// \returns An LineTable or an error describing the issue that was 153 /// encountered during decoding. 154 static llvm::Expected<LineTable> decode(DataExtractor &Data, 155 uint64_t BaseAddr); 156 /// Encode this LineTable object into FileWriter stream. 157 /// 158 /// \param O The binary stream to write the data to at the current file 159 /// position. 160 /// 161 /// \param BaseAddr The base address to use when decoding the line table. 162 /// This will be the FunctionInfo's start address. 163 /// 164 /// \returns An error object that indicates success or failure or the 165 /// encoding process. 166 llvm::Error encode(FileWriter &O, uint64_t BaseAddr) const; 167 bool empty() const { return Lines.empty(); } 168 void clear() { Lines.clear(); } 169 void push(const LineEntry &LE) { 170 Lines.push_back(LE); 171 } 172 size_t isValid() const { 173 return !Lines.empty(); 174 } 175 size_t size() const { 176 return Lines.size(); 177 } 178 LineEntry &get(size_t i) { 179 assert(i < Lines.size()); 180 return Lines[i]; 181 } 182 const LineEntry &get(size_t i) const { 183 assert(i < Lines.size()); 184 return Lines[i]; 185 } 186 LineEntry &operator[](size_t i) { 187 return get(i); 188 } 189 const LineEntry &operator[](size_t i) const { 190 return get(i); 191 } 192 bool operator==(const LineTable &RHS) const { 193 return Lines == RHS.Lines; 194 } 195 bool operator!=(const LineTable &RHS) const { 196 return Lines != RHS.Lines; 197 } 198 bool operator<(const LineTable &RHS) const { 199 const auto LHSSize = Lines.size(); 200 const auto RHSSize = RHS.Lines.size(); 201 if (LHSSize == RHSSize) 202 return Lines < RHS.Lines; 203 return LHSSize < RHSSize; 204 } 205 Collection::const_iterator begin() const { return Lines.begin(); } 206 Collection::const_iterator end() const { return Lines.end(); } 207 208}; 209 210raw_ostream &operator<<(raw_ostream &OS, const gsym::LineTable <); 211 212} // namespace gsym 213} // namespace llvm 214 215#endif // #ifndef LLVM_DEBUGINFO_GSYM_LINETABLE_H 216