LLVM  10.0.0svn
LineTable.cpp
Go to the documentation of this file.
1 //===- LineTable.cpp --------------------------------------------*- 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 
12 
13 using namespace llvm;
14 using namespace gsym;
15 
17  EndSequence = 0x00, ///< End of the line table.
18  SetFile = 0x01, ///< Set LineTableRow.file_idx, don't push a row.
19  AdvancePC = 0x02, ///< Increment LineTableRow.address, and push a row.
20  AdvanceLine = 0x03, ///< Set LineTableRow.file_line, don't push a row.
21  FirstSpecial = 0x04, ///< All special opcodes push a row.
22 };
23 
24 struct DeltaInfo {
25  int64_t Delta;
27  DeltaInfo(int64_t D, uint32_t C) : Delta(D), Count(C) {}
28 };
29 
30 inline bool operator<(const DeltaInfo &LHS, int64_t Delta) {
31  return LHS.Delta < Delta;
32 }
33 
34 static bool encodeSpecial(int64_t MinLineDelta, int64_t MaxLineDelta,
35  int64_t LineDelta, uint64_t AddrDelta,
36  uint8_t &SpecialOp) {
37  if (LineDelta < MinLineDelta)
38  return false;
39  if (LineDelta > MaxLineDelta)
40  return false;
41  int64_t LineRange = MaxLineDelta - MinLineDelta + 1;
42  int64_t AdjustedOp = ((LineDelta - MinLineDelta) + AddrDelta * LineRange);
43  int64_t Op = AdjustedOp + FirstSpecial;
44  if (Op < 0)
45  return false;
46  if (Op > 255)
47  return false;
48  SpecialOp = (uint8_t)Op;
49  return true;
50 }
51 
52 typedef std::function<bool(const LineEntry &Row)> LineEntryCallback;
53 
54 static llvm::Error parse(DataExtractor &Data, uint64_t BaseAddr,
55  LineEntryCallback const &Callback) {
56  uint64_t Offset = 0;
57  if (!Data.isValidOffset(Offset))
58  return createStringError(std::errc::io_error,
59  "0x%8.8" PRIx64 ": missing LineTable MinDelta", Offset);
60  int64_t MinDelta = Data.getSLEB128(&Offset);
61  if (!Data.isValidOffset(Offset))
62  return createStringError(std::errc::io_error,
63  "0x%8.8" PRIx64 ": missing LineTable MaxDelta", Offset);
64  int64_t MaxDelta = Data.getSLEB128(&Offset);
65  int64_t LineRange = MaxDelta - MinDelta + 1;
66  if (!Data.isValidOffset(Offset))
67  return createStringError(std::errc::io_error,
68  "0x%8.8" PRIx64 ": missing LineTable FirstLine", Offset);
69  const uint32_t FirstLine = (uint32_t)Data.getULEB128(&Offset);
70  LineEntry Row(BaseAddr, 1, FirstLine);
71  bool Done = false;
72  while (!Done) {
73  if (!Data.isValidOffset(Offset))
74  return createStringError(std::errc::io_error,
75  "0x%8.8" PRIx64 ": EOF found before EndSequence", Offset);
76  uint8_t Op = Data.getU8(&Offset);
77  switch (Op) {
78  case EndSequence:
79  Done = true;
80  break;
81  case SetFile:
82  if (!Data.isValidOffset(Offset))
83  return createStringError(std::errc::io_error,
84  "0x%8.8" PRIx64 ": EOF found before SetFile value",
85  Offset);
86  Row.File = (uint32_t)Data.getULEB128(&Offset);
87  break;
88  case AdvancePC:
89  if (!Data.isValidOffset(Offset))
90  return createStringError(std::errc::io_error,
91  "0x%8.8" PRIx64 ": EOF found before AdvancePC value",
92  Offset);
93  Row.Addr += Data.getULEB128(&Offset);
94  // If the function callback returns false, we stop parsing.
95  if (Callback(Row) == false)
96  return Error::success();
97  break;
98  case AdvanceLine:
99  if (!Data.isValidOffset(Offset))
100  return createStringError(std::errc::io_error,
101  "0x%8.8" PRIx64 ": EOF found before AdvanceLine value",
102  Offset);
103  Row.Line += Data.getSLEB128(&Offset);
104  break;
105  default: {
106  // A byte that contains both address and line increment.
107  uint8_t AdjustedOp = Op - FirstSpecial;
108  int64_t LineDelta = MinDelta + (AdjustedOp % LineRange);
109  uint64_t AddrDelta = (AdjustedOp / LineRange);
110  Row.Line += LineDelta;
111  Row.Addr += AddrDelta;
112  // If the function callback returns false, we stop parsing.
113  if (Callback(Row) == false)
114  return Error::success();
115  break;
116  }
117  }
118  }
119  return Error::success();
120 }
121 
122 llvm::Error LineTable::encode(FileWriter &Out, uint64_t BaseAddr) const {
123  // Users must verify the LineTable is valid prior to calling this funtion.
124  // We don't want to emit any LineTable objects if they are not valid since
125  // it will waste space in the GSYM file.
126  if (!isValid())
127  return createStringError(std::errc::invalid_argument,
128  "attempted to encode invalid LineTable object");
129 
130  int64_t MinLineDelta = INT64_MAX;
131  int64_t MaxLineDelta = INT64_MIN;
132  std::vector<DeltaInfo> DeltaInfos;
133  if (Lines.size() == 1) {
134  MinLineDelta = 0;
135  MaxLineDelta = 0;
136  } else {
137  int64_t PrevLine = 1;
138  bool First = true;
139  for (const auto &line_entry : Lines) {
140  if (First)
141  First = false;
142  else {
143  int64_t LineDelta = (int64_t)line_entry.Line - PrevLine;
144  auto End = DeltaInfos.end();
145  auto Pos = std::lower_bound(DeltaInfos.begin(), End, LineDelta);
146  if (Pos != End && Pos->Delta == LineDelta)
147  ++Pos->Count;
148  else
149  DeltaInfos.insert(Pos, DeltaInfo(LineDelta, 1));
150  if (LineDelta < MinLineDelta)
151  MinLineDelta = LineDelta;
152  if (LineDelta > MaxLineDelta)
153  MaxLineDelta = LineDelta;
154  }
155  PrevLine = (int64_t)line_entry.Line;
156  }
157  assert(MinLineDelta <= MaxLineDelta);
158  }
159  // Set the min and max line delta intelligently based on the counts of
160  // the line deltas. if our range is too large.
161  const int64_t MaxLineRange = 14;
162  if (MaxLineDelta - MinLineDelta > MaxLineRange) {
163  uint32_t BestIndex = 0;
164  uint32_t BestEndIndex = 0;
165  uint32_t BestCount = 0;
166  const size_t NumDeltaInfos = DeltaInfos.size();
167  for (uint32_t I = 0; I < NumDeltaInfos; ++I) {
168  const int64_t FirstDelta = DeltaInfos[I].Delta;
169  uint32_t CurrCount = 0;
170  uint32_t J;
171  for (J = I; J < NumDeltaInfos; ++J) {
172  auto LineRange = DeltaInfos[J].Delta - FirstDelta;
173  if (LineRange > MaxLineRange)
174  break;
175  CurrCount += DeltaInfos[J].Count;
176  }
177  if (CurrCount > BestCount) {
178  BestIndex = I;
179  BestEndIndex = J - 1;
180  BestCount = CurrCount;
181  }
182  }
183  MinLineDelta = DeltaInfos[BestIndex].Delta;
184  MaxLineDelta = DeltaInfos[BestEndIndex].Delta;
185  }
186  if (MinLineDelta == MaxLineDelta && MinLineDelta > 0 &&
187  MinLineDelta < MaxLineRange)
188  MinLineDelta = 0;
189  assert(MinLineDelta <= MaxLineDelta);
190 
191  // Initialize the line entry state as a starting point. All line entries
192  // will be deltas from this.
193  LineEntry Prev(BaseAddr, 1, Lines.front().Line);
194 
195  // Write out the min and max line delta as signed LEB128.
196  Out.writeSLEB(MinLineDelta);
197  Out.writeSLEB(MaxLineDelta);
198  // Write out the starting line number as a unsigned LEB128.
199  Out.writeULEB(Prev.Line);
200 
201  for (const auto &Curr : Lines) {
202  if (Curr.Addr < BaseAddr)
203  return createStringError(std::errc::invalid_argument,
204  "LineEntry has address 0x%" PRIx64 " which is "
205  "less than the function start address 0x%"
206  PRIx64, Curr.Addr, BaseAddr);
207  if (Curr.Addr < Prev.Addr)
208  return createStringError(std::errc::invalid_argument,
209  "LineEntry in LineTable not in ascending order");
210  const uint64_t AddrDelta = Curr.Addr - Prev.Addr;
211  int64_t LineDelta = 0;
212  if (Curr.Line > Prev.Line)
213  LineDelta = Curr.Line - Prev.Line;
214  else if (Prev.Line > Curr.Line)
215  LineDelta = -((int32_t)(Prev.Line - Curr.Line));
216 
217  // Set the file if it doesn't match the current one.
218  if (Curr.File != Prev.File) {
219  Out.writeU8(SetFile);
220  Out.writeULEB(Curr.File);
221  }
222 
223  uint8_t SpecialOp;
224  if (encodeSpecial(MinLineDelta, MaxLineDelta, LineDelta, AddrDelta,
225  SpecialOp)) {
226  // Advance the PC and line and push a row.
227  Out.writeU8(SpecialOp);
228  } else {
229  // We can't encode the address delta and line delta into
230  // a single special opcode, we must do them separately.
231 
232  // Advance the line.
233  if (LineDelta != 0) {
234  Out.writeU8(AdvanceLine);
235  Out.writeSLEB(LineDelta);
236  }
237 
238  // Advance the PC and push a row.
239  Out.writeU8(AdvancePC);
240  Out.writeULEB(AddrDelta);
241  }
242  Prev = Curr;
243  }
244  Out.writeU8(EndSequence);
245  return Error::success();
246 }
247 
248 // Parse all line table entries into the "LineTable" vector. We can
249 // cache the results of this if needed, or we can call LineTable::lookup()
250 // below.
252  uint64_t BaseAddr) {
253  LineTable LT;
254  llvm::Error Err = parse(Data, BaseAddr, [&](const LineEntry &Row) -> bool {
255  LT.Lines.push_back(Row);
256  return true; // Keep parsing by returning true.
257  });
258  if (Err)
259  return std::move(Err);
260  return LT;
261 }
262 // Parse the line table on the fly and find the row we are looking for.
263 // We will need to determine if we need to cache the line table by calling
264 // LineTable::parseAllEntries(...) or just call this function each time.
265 // There is a CPU vs memory tradeoff we will need to determine.
266 LineEntry LineTable::lookup(DataExtractor &Data, uint64_t BaseAddr, uint64_t Addr) {
267  LineEntry Result;
268  llvm::Error Err = parse(Data, BaseAddr,
269  [Addr, &Result](const LineEntry &Row) -> bool {
270  if (Addr < Row.Addr)
271  return false; // Stop parsing, result contains the line table row!
272  Result = Row;
273  if (Addr == Row.Addr) {
274  // Stop parsing, this is the row we are looking for since the address
275  // matches.
276  return false;
277  }
278  return true; // Keep parsing till we find the right row.
279  });
280  return Result;
281 }
282 
284  for (const auto &LineEntry : LT)
285  OS << LineEntry << '\n';
286  return OS;
287 }
auto lower_bound(R &&Range, T &&Value) -> decltype(adl_begin(Range))
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1261
uint64_t CallInst * C
uint8_t getU8(uint64_t *offset_ptr, Error *Err=nullptr) const
Extract a uint8_t value from *offset_ptr.
This class represents lattice values for constants.
Definition: AllocatorList.h:23
void writeU8(uint8_t Value)
Write a single uint8_t value into the stream at the current file position.
Definition: FileWriter.cpp:34
void writeULEB(uint64_t Value)
Write the value into the stream encoded using unsigned LEB128 at the current file position...
Definition: FileWriter.cpp:27
uint64_t Addr
Start address of this line entry.
Definition: LineEntry.h:23
Line entries are used to encode the line tables in FunctionInfo objects.
Definition: LineEntry.h:22
DeltaInfo(int64_t D, uint32_t C)
Definition: LineTable.cpp:27
int64_t Delta
Definition: LineTable.cpp:25
int64_t getSLEB128(uint64_t *offset_ptr) const
Extract a signed LEB128 value from *offset_ptr.
bool operator<(const FunctionInfo &LHS, const FunctionInfo &RHS)
This sorting will order things consistently by address range first, but then followed by inlining bei...
Definition: FunctionInfo.h:170
#define INT64_MIN
Definition: DataTypes.h:80
#define INT64_MAX
Definition: DataTypes.h:77
Tagged union holding either a T or a Error.
Definition: yaml2obj.h:21
uint32_t Count
Definition: LineTable.cpp:26
uint32_t File
1 based index of file in FileTable
Definition: LineEntry.h:24
LineTableOpCode
Definition: LineTable.cpp:16
* if(!EatIfPresent(lltok::kw_thread_local)) return false
ParseOptionalThreadLocal := /*empty.
void writeSLEB(int64_t Value)
Write the value into the stream encoded using signed LEB128 at the current file position.
Definition: FileWriter.cpp:20
LineTable class contains deserialized versions of line tables for each function&#39;s address ranges...
Definition: LineTable.h:118
A simplified binary data writer class that doesn&#39;t require targets, target definitions, architectures, or require any other optional compile time libraries to be enabled via the build process.
Definition: FileWriter.h:29
uint64_t getULEB128(uint64_t *offset_ptr, llvm::Error *Err=nullptr) const
Extract a unsigned LEB128 value from *offset_ptr.
static llvm::Expected< LineTable > decode(DataExtractor &Data, uint64_t BaseAddr)
Decode an LineTable object from a binary data stream.
Definition: LineTable.cpp:251
llvm::Error encode(FileWriter &O, uint64_t BaseAddr) const
Encode this LineTable object into FileWriter stream.
Definition: LineTable.cpp:122
static ErrorSuccess success()
Create a success value.
Definition: Error.h:326
static bool encodeSpecial(int64_t MinLineDelta, int64_t MaxLineDelta, int64_t LineDelta, uint64_t AddrDelta, uint8_t &SpecialOp)
Definition: LineTable.cpp:34
End of the line table.
Definition: LineTable.cpp:17
Set LineTableRow.file_line, don&#39;t push a row.
Definition: LineTable.cpp:20
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
bool isValidOffset(uint64_t offset) const
Test the validity of offset.
Increment LineTableRow.address, and push a row.
Definition: LineTable.cpp:19
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
Lightweight error class with error context and mandatory checking.
Definition: Error.h:157
This class implements an extremely fast bulk output stream that can only output to a stream...
Definition: raw_ostream.h:45
static LineEntry lookup(DataExtractor &Data, uint64_t BaseAddr, uint64_t Addr)
Definition: LineTable.cpp:266
std::function< bool(const LineEntry &Row)> LineEntryCallback
Definition: LineTable.cpp:52
uint32_t Line
Source line number.
Definition: LineEntry.h:25
static llvm::Error parse(DataExtractor &Data, uint64_t BaseAddr, LineEntryCallback const &Callback)
Definition: LineTable.cpp:54
raw_ostream & operator<<(raw_ostream &OS, const FunctionInfo &R)
Set LineTableRow.file_idx, don&#39;t push a row.
Definition: LineTable.cpp:18
All special opcodes push a row.
Definition: LineTable.cpp:21
Error createStringError(std::error_code EC, char const *Fmt, const Ts &... Vals)
Create formatted StringError object.
Definition: Error.h:1197