1353940Sdim//===- LineTable.h ----------------------------------------------*- C++ -*-===// 2353940Sdim// 3353940Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353940Sdim// See https://llvm.org/LICENSE.txt for license information. 5353940Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6353940Sdim// 7353940Sdim//===----------------------------------------------------------------------===// 8353940Sdim 9353940Sdim#ifndef LLVM_DEBUGINFO_GSYM_LINETABLE_H 10353940Sdim#define LLVM_DEBUGINFO_GSYM_LINETABLE_H 11353940Sdim 12353940Sdim#include "llvm/DebugInfo/GSYM/LineEntry.h" 13353940Sdim#include "llvm/Support/Error.h" 14353940Sdim#include <cstdint> 15353940Sdim#include <vector> 16353940Sdim 17353940Sdimnamespace llvm { 18353940Sdimnamespace gsym { 19353940Sdim 20353940Sdimstruct FunctionInfo; 21353940Sdimclass FileWriter; 22353940Sdim 23353940Sdim/// LineTable class contains deserialized versions of line tables for each 24353940Sdim/// function's address ranges. 25353940Sdim/// 26353940Sdim/// When saved to disk, the line table is encoded using a modified version of 27353940Sdim/// the DWARF line tables that only tracks address to source file and line. 28353940Sdim/// 29353940Sdim/// ENCODING 30353940Sdim/// 31353940Sdim/// The line table starts with a small prolog that contains the following 32353940Sdim/// values: 33353940Sdim/// 34353940Sdim/// ENCODING NAME DESCRIPTION 35353940Sdim/// ======== =========== ==================================================== 36353940Sdim/// SLEB MinDelta The min line delta for special opcodes that advance 37353940Sdim/// the address and line number. 38353940Sdim/// SLEB MaxDelta The max line delta for single byte opcodes that 39353940Sdim/// advance the address and line number. 40353940Sdim/// ULEB FirstLine The value of the first source line number to 41353940Sdim/// initialize the LineEntry with. 42353940Sdim/// 43353940Sdim/// Once these prolog items are read, we initialize a LineEntry struct with 44353940Sdim/// the start address of the function from the FunctionInfo's address range, 45353940Sdim/// a default file index of 1, and the line number set to "FirstLine" from 46353940Sdim/// the prolog above: 47353940Sdim/// 48353940Sdim/// LineEntry Row(BaseAddr, 1, FirstLine); 49353940Sdim/// 50353940Sdim/// The line table state machine is now initialized and ready to be parsed. 51353940Sdim/// The stream that follows this encodes the line entries in a compact 52353940Sdim/// form. Some opcodes cause "Row" to be modified and some opcodes may also 53353940Sdim/// push "Row" onto the end of the "LineTable.Lines" vector. The end result 54353940Sdim/// is a vector of LineEntry structs that is sorted in ascending address 55353940Sdim/// order. 56353940Sdim/// 57353940Sdim/// NORMAL OPCODES 58353940Sdim/// 59353940Sdim/// The opcodes 0 through 3 are normal in opcodes. Their encoding and 60353940Sdim/// descriptions are listed below: 61353940Sdim/// 62353940Sdim/// ENCODING ENUMERATION VALUE DESCRIPTION 63353940Sdim/// ======== ================ ===== ======================================== 64353940Sdim/// LTOC_EndSequence 0x00 Parsing is done. 65353940Sdim/// ULEB LTOC_SetFile 0x01 Row.File = ULEB 66353940Sdim/// ULEB LTOC_AdvancePC 0x02 Row.Addr += ULEB, push "Row". 67353940Sdim/// SLEB LTOC_AdvanceLine 0x03 Row.Line += SLEB 68353940Sdim/// LTOC_FirstSpecial 0x04 First special opcode (see SPECIAL 69353940Sdim/// OPCODES below). 70353940Sdim/// 71353940Sdim/// SPECIAL OPCODES 72353940Sdim/// 73353940Sdim/// Opcodes LTOC_FirstSpecial through 255 are special opcodes that always 74353940Sdim/// increment both the Row.Addr and Row.Line and push "Row" onto the 75353940Sdim/// LineEntry.Lines array. They do this by using some of the bits to 76353940Sdim/// increment/decrement the source line number, and some of the bits to 77353940Sdim/// increment the address. Line numbers can go up or down when making line 78353940Sdim/// tables, where addresses always only increase since line tables are sorted 79353940Sdim/// by address. 80353940Sdim/// 81353940Sdim/// In order to calculate the amount to increment the line and address for 82353940Sdim/// these special opcodes, we calculate the number of values reserved for the 83353940Sdim/// line increment/decrement using the "MinDelta" and "MaxDelta" from the 84353940Sdim/// prolog: 85353940Sdim/// 86353940Sdim/// const int64_t LineRange = MaxDelta - MinDelta + 1; 87353940Sdim/// 88353940Sdim/// Then we can adjust the opcode to not include any of the normal opcodes: 89353940Sdim/// 90353940Sdim/// const uint8_t AdjustedOp = Opcode - LTOC_FirstSpecial; 91353940Sdim/// 92353940Sdim/// And we can calculate the line offset, and address offset: 93353940Sdim/// 94353940Sdim/// const int64_t LineDelta = MinDelta + (AdjustedOp % LineRange); 95353940Sdim/// const uint64_t AddrDelta = (AdjustedOp / LineRange); 96353940Sdim/// 97353940Sdim/// And use these to modify our "Row": 98353940Sdim/// 99353940Sdim/// Row.Line += LineDelta; 100353940Sdim/// Row.Addr += AddrDelta; 101353940Sdim/// 102353940Sdim/// And push a row onto the line table: 103353940Sdim/// 104353940Sdim/// Lines.push_back(Row); 105353940Sdim/// 106353940Sdim/// This is verify similar to the way that DWARF encodes its line tables. The 107353940Sdim/// only difference is the DWARF line tables have more normal opcodes and the 108353940Sdim/// "Row" contains more members, like source column number, bools for end of 109353940Sdim/// prologue, beginnging of epilogue, is statement and many others. There are 110353940Sdim/// also more complex rules that happen for the extra normal opcodes. By 111353940Sdim/// leaving these extra opcodes out, we leave more bits for the special 112353940Sdim/// opcodes that allows us to encode line tables in fewer bytes than standard 113353940Sdim/// DWARF encodings. 114353940Sdim/// 115353940Sdim/// Opcodes that will push "Row" onto the LineEntry.Lines include the 116353940Sdim/// LTOC_AdvancePC opcode and all special opcodes. All other opcodes 117353940Sdim/// only modify the current "Row", or cause the line table to end. 118353940Sdimclass LineTable { 119353940Sdim typedef std::vector<gsym::LineEntry> Collection; 120353940Sdim Collection Lines; ///< All line entries in the line table. 121353940Sdimpublic: 122357095Sdim /// Lookup a single address within a line table's data. 123357095Sdim /// 124357095Sdim /// Clients have the option to decode an entire line table using 125357095Sdim /// LineTable::decode() or just find a single matching entry using this 126357095Sdim /// function. The benefit of using this function is that parsed LineEntry 127357095Sdim /// objects that do not match will not be stored in an array. This will avoid 128357095Sdim /// memory allocation costs and parsing can stop once a match has been found. 129357095Sdim /// 130357095Sdim /// \param Data The binary stream to read the data from. This object must 131357095Sdim /// have the data for the LineTable object starting at offset zero. The data 132357095Sdim /// can contain more data than needed. 133357095Sdim /// 134357095Sdim /// \param BaseAddr The base address to use when decoding the line table. 135357095Sdim /// This will be the FunctionInfo's start address and will be used to 136357095Sdim /// initialize the line table row prior to parsing any opcodes. 137357095Sdim /// 138357095Sdim /// \returns An LineEntry object if a match is found, error otherwise. 139357095Sdim static Expected<LineEntry> lookup(DataExtractor &Data, uint64_t BaseAddr, 140357095Sdim uint64_t Addr); 141353940Sdim 142353940Sdim /// Decode an LineTable object from a binary data stream. 143353940Sdim /// 144353940Sdim /// \param Data The binary stream to read the data from. This object must 145353940Sdim /// have the data for the LineTable object starting at offset zero. The data 146353940Sdim /// can contain more data than needed. 147353940Sdim /// 148353940Sdim /// \param BaseAddr The base address to use when decoding the line table. 149353940Sdim /// This will be the FunctionInfo's start address and will be used to 150353940Sdim /// initialize the line table row prior to parsing any opcodes. 151353940Sdim /// 152353940Sdim /// \returns An LineTable or an error describing the issue that was 153353940Sdim /// encountered during decoding. 154353940Sdim static llvm::Expected<LineTable> decode(DataExtractor &Data, 155353940Sdim uint64_t BaseAddr); 156353940Sdim /// Encode this LineTable object into FileWriter stream. 157353940Sdim /// 158353940Sdim /// \param O The binary stream to write the data to at the current file 159353940Sdim /// position. 160353940Sdim /// 161353940Sdim /// \param BaseAddr The base address to use when decoding the line table. 162353940Sdim /// This will be the FunctionInfo's start address. 163353940Sdim /// 164353940Sdim /// \returns An error object that indicates success or failure or the 165353940Sdim /// encoding process. 166353940Sdim llvm::Error encode(FileWriter &O, uint64_t BaseAddr) const; 167353940Sdim bool empty() const { return Lines.empty(); } 168353940Sdim void clear() { Lines.clear(); } 169353940Sdim void push(const LineEntry &LE) { 170353940Sdim Lines.push_back(LE); 171353940Sdim } 172353940Sdim size_t isValid() const { 173353940Sdim return !Lines.empty(); 174353940Sdim } 175353940Sdim size_t size() const { 176353940Sdim return Lines.size(); 177353940Sdim } 178353940Sdim LineEntry &get(size_t i) { 179353940Sdim assert(i < Lines.size()); 180353940Sdim return Lines[i]; 181353940Sdim } 182353940Sdim const LineEntry &get(size_t i) const { 183353940Sdim assert(i < Lines.size()); 184353940Sdim return Lines[i]; 185353940Sdim } 186353940Sdim LineEntry &operator[](size_t i) { 187353940Sdim return get(i); 188353940Sdim } 189353940Sdim const LineEntry &operator[](size_t i) const { 190353940Sdim return get(i); 191353940Sdim } 192353940Sdim bool operator==(const LineTable &RHS) const { 193353940Sdim return Lines == RHS.Lines; 194353940Sdim } 195353940Sdim bool operator!=(const LineTable &RHS) const { 196353940Sdim return Lines != RHS.Lines; 197353940Sdim } 198353940Sdim bool operator<(const LineTable &RHS) const { 199353940Sdim const auto LHSSize = Lines.size(); 200353940Sdim const auto RHSSize = RHS.Lines.size(); 201353940Sdim if (LHSSize == RHSSize) 202353940Sdim return Lines < RHS.Lines; 203353940Sdim return LHSSize < RHSSize; 204353940Sdim } 205353940Sdim Collection::const_iterator begin() const { return Lines.begin(); } 206353940Sdim Collection::const_iterator end() const { return Lines.end(); } 207353940Sdim 208353940Sdim}; 209353940Sdim 210353940Sdimraw_ostream &operator<<(raw_ostream &OS, const gsym::LineTable <); 211353940Sdim 212353940Sdim} // namespace gsym 213353940Sdim} // namespace llvm 214353940Sdim 215353940Sdim#endif // #ifndef LLVM_DEBUGINFO_GSYM_LINETABLE_H 216