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 17 namespace llvm { 18 namespace gsym { 19 20 struct FunctionInfo; 21 class 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. 118 class LineTable { 119 typedef std::vector<gsym::LineEntry> Collection; 120 Collection Lines; ///< All line entries in the line table. 121 public: 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 210 raw_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