1//===-- Coverage.cpp - Debug info coverage metrics ------------------------===//
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#include "llvm-dwarfdump.h"
10#include "llvm/ADT/SetOperations.h"
11#include "llvm/BinaryFormat/Dwarf.h"
12#include "llvm/DebugInfo/DIContext.h"
13#include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
14#include "llvm/DebugInfo/DWARF/DWARFCompileUnit.h"
15#include "llvm/DebugInfo/DWARF/DWARFContext.h"
16#include "llvm/IR/CFG.h"
17#include "llvm/IR/DebugInfoMetadata.h"
18#include "llvm/IR/DebugProgramInstruction.h"
19#include "llvm/IR/Instructions.h"
20#include "llvm/IR/Module.h"
21#include "llvm/IRReader/IRReader.h"
22#include "llvm/Object/ObjectFile.h"
23#include "llvm/Support/MemoryBuffer.h"
24#include "llvm/Support/SourceMgr.h"
25
26using namespace llvm;
27using namespace llvm::dwarf;
28using namespace llvm::object;
29
30/// Pair of file index and line number representing a source location.
31typedef std::pair<uint16_t, size_t> SourceLocation;
32
33/// Adds source locations to the line set that correspond to an address range.
34static void addLines(const DWARFDebugLine::LineTable *LineTable,
35 DenseSet<SourceLocation> &Lines, DWARFAddressRange Range) {
36 std::vector<uint32_t> Rows;
37 if (LineTable->lookupAddressRange(Address: {.Address: Range.LowPC, .SectionIndex: Range.SectionIndex},
38 Size: Range.HighPC - Range.LowPC, Result&: Rows)) {
39 for (const auto &RowI : Rows) {
40 const auto Row = LineTable->Rows[RowI];
41 // Lookup can return addresses below the LowPC - filter these out.
42 if (Row.Address.Address < Range.LowPC)
43 continue;
44
45 if (Row.Line) // Ignore zero lines.
46 Lines.insert(V: {Row.File, Row.Line});
47 }
48 }
49}
50
51// Converts the file index of each line in the set to use our own internal
52// file index. This is required for a reliable comparison as the DWARF index may
53// differ across compilations.
54static DenseSet<SourceLocation>
55convertFileIndices(DenseSet<SourceLocation> Lines,
56 const DWARFDebugLine::LineTable *const LineTable,
57 DenseMap<uint16_t, uint16_t> &FileIndexMap,
58 StringMap<uint16_t> &FileNameMap) {
59 DenseSet<SourceLocation> ResultLines;
60 for (const auto &L : Lines) {
61 uint16_t Index;
62 const auto IndexIt = FileIndexMap.find(Val: L.first);
63 if (IndexIt != FileIndexMap.end()) {
64 Index = IndexIt->second;
65 } else {
66 std::string Name;
67 [[maybe_unused]] bool ValidIndex = LineTable->getFileNameByIndex(
68 FileIndex: L.first, CompDir: "", Kind: DILineInfoSpecifier::FileLineInfoKind::RelativeFilePath,
69 Result&: Name);
70 assert(ValidIndex && "File index was not valid for its own line table");
71
72 auto NameIt = FileNameMap.find(Key: Name);
73 if (NameIt != FileNameMap.end()) {
74 Index = NameIt->second;
75 } else {
76 Index = FileNameMap.size();
77 FileNameMap.insert(KV: {Name, Index});
78 }
79
80 FileIndexMap.insert(KV: {L.first, Index});
81 }
82
83 ResultLines.insert(V: {Index, L.second});
84 }
85
86 return ResultLines;
87}
88
89/// Returns the set of source lines covered by a variable's debug information,
90/// computed by intersecting the variable's location ranges and the containing
91/// scope's address ranges.
92static DenseSet<SourceLocation>
93computeVariableCoverage(DWARFDie VariableDIE,
94 const DWARFDebugLine::LineTable *const LineTable,
95 DenseMap<uint16_t, uint16_t> &FileIndexMap,
96 StringMap<uint16_t> &FileNameMap) {
97 // The optionals below will be empty if no address ranges were found, and
98 // present (but containing an empty set) if ranges were found but contained no
99 // source locations, in order to distinguish the two cases.
100
101 auto Locations = VariableDIE.getLocations(Attr: DW_AT_location);
102 std::optional<DenseSet<SourceLocation>> Lines;
103 if (Locations) {
104 for (const auto &L : Locations.get()) {
105 if (L.Range) {
106 if (!Lines)
107 Lines = DenseSet<SourceLocation>();
108 addLines(LineTable, Lines&: *Lines, Range: L.Range.value());
109 }
110 }
111 } else {
112 // If the variable is optimized out and has no DW_AT_location, return an
113 // empty set instead of falling back to the parent scope's address ranges.
114 consumeError(Err: Locations.takeError());
115 return {};
116 }
117
118 // DW_AT_location attribute may contain overly broad address ranges, or none
119 // at all, so we also consider the parent scope's address ranges if present.
120 auto ParentRanges = VariableDIE.getParent().getAddressRanges();
121 std::optional<DenseSet<SourceLocation>> ParentLines;
122 if (ParentRanges) {
123 ParentLines = DenseSet<SourceLocation>();
124 for (const auto &R : ParentRanges.get())
125 addLines(LineTable, Lines&: *ParentLines, Range: R);
126 } else {
127 consumeError(Err: ParentRanges.takeError());
128 }
129
130 if (!Lines && ParentLines)
131 Lines = std::move(ParentLines);
132 else if (ParentLines)
133 set_intersect(S1&: *Lines, S2: *ParentLines);
134
135 if (!Lines)
136 return {};
137
138 return convertFileIndices(Lines: Lines.value_or(u: DenseSet<SourceLocation>()),
139 LineTable, FileIndexMap, FileNameMap);
140}
141
142/// Adds source locations to the line set that are within an inlined subroutine.
143static void getInlinedLines(DWARFDie SubroutineDIE,
144 DenseSet<SourceLocation> &Lines,
145 const DWARFDebugLine::LineTable *const LineTable) {
146 for (const auto &ChildDIE : SubroutineDIE.children()) {
147 if (ChildDIE.getTag() == DW_TAG_inlined_subroutine) {
148 auto Ranges = ChildDIE.getAddressRanges();
149 if (Ranges) {
150 for (const auto &R : Ranges.get())
151 addLines(LineTable, Lines, Range: R);
152 } else {
153 consumeError(Err: Ranges.takeError());
154 }
155 } else {
156 getInlinedLines(SubroutineDIE: ChildDIE, Lines, LineTable);
157 }
158 }
159}
160
161/// Returns the set of source lines present in the line table for a subroutine.
162static DenseSet<SourceLocation>
163computeSubroutineCoverage(DWARFDie SubroutineDIE,
164 const DWARFDebugLine::LineTable *const LineTable,
165 DenseMap<uint16_t, uint16_t> &FileIndexMap,
166 StringMap<uint16_t> &FileNameMap) {
167 auto Ranges = SubroutineDIE.getAddressRanges();
168 DenseSet<SourceLocation> Lines;
169 if (Ranges) {
170 for (const auto &R : Ranges.get())
171 addLines(LineTable, Lines, Range: R);
172 } else {
173 consumeError(Err: Ranges.takeError());
174 }
175
176 // Exclude lines from any subroutines inlined into this one.
177 DenseSet<SourceLocation> InlinedLines;
178 getInlinedLines(SubroutineDIE, Lines&: InlinedLines, LineTable);
179 set_subtract(S1&: Lines, S2: InlinedLines);
180
181 return convertFileIndices(Lines, LineTable, FileIndexMap, FileNameMap);
182}
183
184static const SmallVector<DWARFDie> getParentSubroutines(DWARFDie DIE) {
185 SmallVector<DWARFDie> Parents;
186 DWARFDie Parent = DIE;
187 do {
188 if (Parent.getTag() == DW_TAG_subprogram) {
189 Parents.push_back(Elt: Parent);
190 break;
191 }
192 if (Parent.getTag() == DW_TAG_inlined_subroutine)
193 Parents.push_back(Elt: Parent);
194 } while ((Parent = Parent.getParent()));
195 return Parents;
196}
197
198struct VarKey {
199 const char *const SubprogramName;
200 const char *const Name;
201 std::string DeclFile;
202 uint64_t DeclLine;
203
204 bool operator==(const VarKey &Other) const {
205 return DeclLine == Other.DeclLine &&
206 !strcmp(s1: SubprogramName, s2: Other.SubprogramName) &&
207 !strcmp(s1: Name, s2: Other.Name) && !DeclFile.compare(str: Other.DeclFile);
208 }
209
210 bool operator<(const VarKey &Other) const {
211 int A = strcmp(s1: SubprogramName, s2: Other.SubprogramName);
212 if (A)
213 return A < 0;
214 int B = strcmp(s1: Name, s2: Other.Name);
215 if (B)
216 return B < 0;
217 int C = DeclFile.compare(str: Other.DeclFile);
218 if (C)
219 return C < 0;
220 return DeclLine < Other.DeclLine;
221 }
222};
223
224struct VarCoverage {
225 SmallVector<DWARFDie> Parents;
226 size_t Cov;
227 size_t BaselineCov;
228 size_t LTCov;
229 size_t Missing;
230 size_t Instances;
231 bool MissingBaseline;
232};
233
234typedef std::multimap<VarKey, VarCoverage, std::less<>> VarMap;
235typedef std::map<VarKey, DenseSet<SourceLocation>, std::less<>> BaselineVarMap;
236
237static std::optional<const VarKey> getVarKey(DWARFDie VariableDIE,
238 DWARFDie SubroutineDIE) {
239 const auto *const VariableName = VariableDIE.getName(Kind: DINameKind::LinkageName);
240 const auto DeclFile = VariableDIE.getDeclFile(
241 Kind: DILineInfoSpecifier::FileLineInfoKind::RelativeFilePath);
242 const auto *const SubroutineName =
243 SubroutineDIE.getName(Kind: DINameKind::LinkageName);
244 if (!VariableName || !SubroutineName)
245 return std::nullopt;
246 return VarKey{.SubprogramName: SubroutineName, .Name: VariableName, .DeclFile: DeclFile,
247 .DeclLine: VariableDIE.getDeclLine()};
248}
249
250static void displayParents(SmallVector<DWARFDie> Parents, raw_ostream &OS) {
251 bool First = true;
252 for (const auto Parent : Parents) {
253 if (auto FormValue = Parent.find(Attr: DW_AT_call_file)) {
254 if (auto OptString = FormValue->getAsFile(
255 Kind: DILineInfoSpecifier::FileLineInfoKind::RelativeFilePath)) {
256 if (First)
257 First = false;
258 else
259 OS << ", ";
260 OS << *OptString << ":" << toUnsigned(V: Parent.find(Attr: DW_AT_call_line), Default: 0);
261 }
262 }
263 }
264}
265
266static void displayVariableCoverage(const VarKey &Key, const VarCoverage &Var,
267 bool CombineInstances, raw_ostream &OS) {
268 WithColor(OS, HighlightColor::String) << Key.SubprogramName;
269 OS << "\t";
270 if (CombineInstances)
271 OS << Var.Instances;
272 else if (Var.Parents.size())
273 // FIXME: This may overflow the terminal if the inlining chain is large.
274 displayParents(Parents: Var.Parents, OS);
275 OS << "\t";
276 WithColor(OS, HighlightColor::String) << Key.Name;
277 OS << "\t";
278 if (!Key.DeclFile.empty())
279 OS << Key.DeclFile << ":" << Key.DeclLine;
280 OS << "\t" << format(Fmt: "%.3g", Vals: ((float)Var.Cov / Var.Instances));
281 if (Var.BaselineCov)
282 OS << "\t" << format(Fmt: "%.3g", Vals: ((float)Var.BaselineCov / Var.Instances))
283 << "\t" << format(Fmt: "%.3g", Vals: ((float)Var.Cov / Var.BaselineCov)) << "\t"
284 << format(Fmt: "%.3g", Vals: ((float)Var.LTCov / Var.Instances)) << "\t"
285 << format(Fmt: "%.3g", Vals: ((float)Var.LTCov / Var.BaselineCov));
286 OS << "\n";
287 if (Var.MissingBaseline)
288 WithColor(errs(), HighlightColor::Warning).warning()
289 << "DIE not found in baseline\n";
290 if (Var.Missing)
291 WithColor(errs(), HighlightColor::Warning).warning()
292 << Var.Missing << " lines not found in baseline\n";
293}
294
295bool dwarfdump::showVariableCoverage(ObjectFile &Obj, DWARFContext &DICtx,
296 ObjectFile *BaselineObj,
297 DWARFContext *BaselineCtx,
298 bool CombineInstances, raw_ostream &OS) {
299 BaselineVarMap BaselineVars;
300 StringMap<uint16_t> FileNameMap;
301
302 if (BaselineCtx) {
303 for (const auto &U : BaselineCtx->info_section_units()) {
304 const auto *const LT = BaselineCtx->getLineTableForUnit(U: U.get());
305 DenseMap<uint16_t, uint16_t> FileIndexMap;
306 for (const auto &Entry : U->dies()) {
307 DWARFDie VariableDIE = {U.get(), &Entry};
308 if (VariableDIE.getTag() != DW_TAG_variable &&
309 VariableDIE.getTag() != DW_TAG_formal_parameter)
310 continue;
311
312 const auto Parents = getParentSubroutines(DIE: VariableDIE);
313 if (!Parents.size())
314 continue;
315 const auto SubroutineDIE = Parents.front();
316 auto Key = getVarKey(VariableDIE, SubroutineDIE);
317 if (!Key)
318 continue;
319
320 auto Cov =
321 computeVariableCoverage(VariableDIE, LineTable: LT, FileIndexMap, FileNameMap);
322 const auto SubroutineCov = computeSubroutineCoverage(
323 SubroutineDIE, LineTable: LT, FileIndexMap, FileNameMap);
324 set_intersect(S1&: Cov, S2: SubroutineCov);
325
326 auto Result = BaselineVars.insert(x: {*Key, Cov});
327 if (!Result.second)
328 Result.first->second.insert_range(R&: Cov);
329 }
330 }
331 }
332
333 VarMap Vars;
334
335 for (const auto &U : DICtx.info_section_units()) {
336 const auto *const LT = DICtx.getLineTableForUnit(U: U.get());
337 DenseMap<uint16_t, uint16_t> FileIndexMap;
338 for (const auto &Entry : U->dies()) {
339 DWARFDie VariableDIE = {U.get(), &Entry};
340 if (VariableDIE.getTag() != DW_TAG_variable &&
341 VariableDIE.getTag() != DW_TAG_formal_parameter)
342 continue;
343
344 const auto Parents = getParentSubroutines(DIE: VariableDIE);
345 if (!Parents.size())
346 continue;
347 const auto SubroutineDIE = Parents.front();
348 auto Key = getVarKey(VariableDIE, SubroutineDIE);
349 if (!Key)
350 continue;
351
352 auto Cov =
353 computeVariableCoverage(VariableDIE, LineTable: LT, FileIndexMap, FileNameMap);
354 const auto SubroutineCov = computeSubroutineCoverage(
355 SubroutineDIE, LineTable: LT, FileIndexMap, FileNameMap);
356 set_intersect(S1&: Cov, S2: SubroutineCov);
357
358 VarCoverage VarCov = {.Parents: Parents, .Cov: Cov.size(), .BaselineCov: 0, .LTCov: 0, .Missing: 0, .Instances: 1, .MissingBaseline: false};
359
360 if (BaselineCtx) {
361 BaselineVarMap::iterator Var = BaselineVars.find(x: *Key);
362
363 if (Var != BaselineVars.end()) {
364 const auto BCov = Var->second;
365 VarCov.BaselineCov = BCov.size();
366
367 for (const auto &L : Cov)
368 VarCov.Missing += (1 - BCov.count(V: L));
369
370 for (const auto &L : BCov)
371 VarCov.LTCov += SubroutineCov.count(V: L);
372 } else {
373 VarCov.MissingBaseline = true;
374 }
375 }
376
377 Vars.insert(x: {*Key, VarCov});
378 }
379 }
380
381 std::pair<VarMap::iterator, VarMap::iterator> Range;
382
383 OS << "\nVariable coverage statistics:\nFunction\t"
384 << (CombineInstances ? "InstanceCount" : "InlChain")
385 << "\tVariable\tDecl\tLinesCovered";
386 if (BaselineCtx)
387 OS << "\tBaseline\tCoveredRatio\tLinesPresent\tLinesPresentRatio";
388 OS << "\n";
389
390 if (CombineInstances) {
391 for (auto FirstVar = Vars.begin(); FirstVar != Vars.end();
392 FirstVar = Range.second) {
393 Range = Vars.equal_range(x: FirstVar->first);
394 VarCoverage CombinedCov = {.Parents: {}, .Cov: 0, .BaselineCov: 0, .LTCov: 0, .Missing: 0, .Instances: 0, .MissingBaseline: false};
395 for (auto Var = Range.first; Var != Range.second; ++Var) {
396 ++CombinedCov.Instances;
397 CombinedCov.Cov += Var->second.Cov;
398 CombinedCov.BaselineCov += Var->second.BaselineCov;
399 CombinedCov.LTCov += Var->second.LTCov;
400 CombinedCov.Missing += Var->second.Missing;
401 CombinedCov.MissingBaseline |= Var->second.MissingBaseline;
402 }
403 displayVariableCoverage(Key: FirstVar->first, Var: CombinedCov, CombineInstances: true, OS);
404 }
405 } else {
406 for (auto Var : Vars)
407 displayVariableCoverage(Key: Var.first, Var: Var.second, CombineInstances: false, OS);
408 }
409
410 return true;
411}
412