LLVM 20.0.0git
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
13using namespace llvm;
14using 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
24struct DeltaInfo {
25 int64_t Delta;
27 DeltaInfo(int64_t D, uint32_t C) : Delta(D), Count(C) {}
28};
29
30inline bool operator<(const DeltaInfo &LHS, int64_t Delta) {
31 return LHS.Delta < Delta;
32}
33
34static 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
52typedef std::function<bool(const LineEntry &Row)> LineEntryCallback;
53
54static 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
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 determined.
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 return true; // Keep parsing till we find the right row.
274 });
275 if (Err)
276 return std::move(Err);
277 if (Result.isValid())
278 return Result;
279 return createStringError(std::errc::invalid_argument,
280 "address 0x%" PRIx64 " is not in the line table",
281 Addr);
282}
283
285 for (const auto &LineEntry : LT)
286 OS << LineEntry << '\n';
287 return OS;
288}
static GCRegistry::Add< StatepointGC > D("statepoint-example", "an example strategy for statepoint")
uint64_t Addr
bool End
Definition: ELF_riscv.cpp:480
bool operator<(const DeltaInfo &LHS, int64_t Delta)
Definition: LineTable.cpp:30
LineTableOpCode
Definition: LineTable.cpp:16
@ SetFile
Set LineTableRow.file_idx, don't push a row.
Definition: LineTable.cpp:18
@ FirstSpecial
All special opcodes push a row.
Definition: LineTable.cpp:21
@ AdvanceLine
Set LineTableRow.file_line, don't push a row.
Definition: LineTable.cpp:20
@ EndSequence
End of the line table.
Definition: LineTable.cpp:17
@ AdvancePC
Increment LineTableRow.address, and push a row.
Definition: LineTable.cpp:19
static bool encodeSpecial(int64_t MinLineDelta, int64_t MaxLineDelta, int64_t LineDelta, uint64_t AddrDelta, uint8_t &SpecialOp)
Definition: LineTable.cpp:34
std::function< bool(const LineEntry &Row)> LineEntryCallback
Definition: LineTable.cpp:52
#define I(x, y, z)
Definition: MD5.cpp:58
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
Value * LHS
This class represents an Operation in the Expression.
Lightweight error class with error context and mandatory checking.
Definition: Error.h:160
static ErrorSuccess success()
Create a success value.
Definition: Error.h:337
Tagged union holding either a T or a Error.
Definition: Error.h:481
A simplified binary data writer class that doesn't require targets, target definitions,...
Definition: FileWriter.h:29
void writeULEB(uint64_t Value)
Write the value into the stream encoded using unsigned LEB128 at the current file position.
Definition: FileWriter.cpp:26
void writeSLEB(int64_t Value)
Write the value into the stream encoded using signed LEB128 at the current file position.
Definition: FileWriter.cpp:19
void writeU8(uint8_t Value)
Write a single uint8_t value into the stream at the current file position.
Definition: FileWriter.cpp:33
LineTable class contains deserialized versions of line tables for each function's address ranges.
Definition: LineTable.h:118
llvm::Error encode(FileWriter &O, uint64_t BaseAddr) const
Encode this LineTable object into FileWriter stream.
Definition: LineTable.cpp:122
static llvm::Expected< LineTable > decode(DataExtractor &Data, uint64_t BaseAddr)
Decode an LineTable object from a binary data stream.
Definition: LineTable.cpp:251
static Expected< LineEntry > lookup(DataExtractor &Data, uint64_t BaseAddr, uint64_t Addr)
Lookup a single address within a line table's data.
Definition: LineTable.cpp:266
size_t isValid() const
Definition: LineTable.h:190
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
#define INT64_MIN
Definition: DataTypes.h:74
#define INT64_MAX
Definition: DataTypes.h:71
@ C
The default llvm calling convention, compatible with C.
Definition: CallingConv.h:34
raw_ostream & operator<<(raw_ostream &OS, const FunctionInfo &R)
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
@ Offset
Definition: DWP.cpp:480
@ Done
Definition: Threading.h:61
Error createStringError(std::error_code EC, char const *Fmt, const Ts &... Vals)
Create formatted StringError object.
Definition: Error.h:1286
@ First
Helpers to iterate all locations in the MemoryEffectsBase class.
uint32_t Count
Definition: LineTable.cpp:26
DeltaInfo(int64_t D, uint32_t C)
Definition: LineTable.cpp:27
int64_t Delta
Definition: LineTable.cpp:25
Line entries are used to encode the line tables in FunctionInfo objects.
Definition: LineEntry.h:22
uint32_t File
1 based index of file in FileTable
Definition: LineEntry.h:24
uint32_t Line
Source line number.
Definition: LineEntry.h:25
uint64_t Addr
Start address of this line entry.
Definition: LineEntry.h:23
Definition: regcomp.c:192