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/// Returns the set of source lines covered by a variable's debug information,
34/// computed by intersecting the variable's location ranges and the containing
35/// scope's address ranges.
36static DenseSet<SourceLocation>
37computeVariableCoverage(DWARFContext &DICtx, DWARFDie VariableDIE,
38 const DWARFDebugLine::LineTable *const LineTable) {
39 /// Adds source locations to the set that correspond to an address range.
40 auto addLines = [](const DWARFDebugLine::LineTable *LineTable,
41 DenseSet<SourceLocation> &Lines, DWARFAddressRange Range) {
42 std::vector<uint32_t> Rows;
43 if (LineTable->lookupAddressRange(Address: {.Address: Range.LowPC, .SectionIndex: Range.SectionIndex},
44 Size: Range.HighPC - Range.LowPC, Result&: Rows)) {
45 for (const auto &RowI : Rows) {
46 const auto Row = LineTable->Rows[RowI];
47 // Lookup can return addresses below the LowPC - filter these out.
48 if (Row.Address.Address < Range.LowPC)
49 continue;
50 const auto FileIndex = Row.File;
51
52 const auto Line = Row.Line;
53 if (Line) // Ignore zero lines.
54 Lines.insert(V: {FileIndex, Line});
55 }
56 }
57 };
58
59 // The optionals below will be empty if no address ranges were found, and
60 // present (but containing an empty set) if ranges were found but contained no
61 // source locations, in order to distinguish the two cases.
62
63 auto Locations = VariableDIE.getLocations(Attr: DW_AT_location);
64 std::optional<DenseSet<SourceLocation>> Lines;
65 if (Locations) {
66 for (const auto &L : Locations.get()) {
67 if (L.Range) {
68 if (!Lines)
69 Lines = DenseSet<SourceLocation>();
70 addLines(LineTable, *Lines, L.Range.value());
71 }
72 }
73 } else {
74 // If the variable is optimized out and has no DW_AT_location, return an
75 // empty set instead of falling back to the parent scope's address ranges.
76 consumeError(Err: Locations.takeError());
77 return {};
78 }
79
80 // DW_AT_location attribute may contain overly broad address ranges, or none
81 // at all, so we also consider the parent scope's address ranges if present.
82 auto ParentRanges = VariableDIE.getParent().getAddressRanges();
83 std::optional<DenseSet<SourceLocation>> ParentLines;
84 if (ParentRanges) {
85 ParentLines = DenseSet<SourceLocation>();
86 for (const auto &R : ParentRanges.get())
87 addLines(LineTable, *ParentLines, R);
88 } else {
89 consumeError(Err: ParentRanges.takeError());
90 }
91
92 if (!Lines && ParentLines)
93 Lines = ParentLines;
94 else if (ParentLines)
95 llvm::set_intersect(S1&: *Lines, S2: *ParentLines);
96
97 return Lines.value_or(u: DenseSet<SourceLocation>());
98}
99
100static const SmallVector<DWARFDie> getParentSubroutines(DWARFDie DIE) {
101 SmallVector<DWARFDie> Parents;
102 DWARFDie Parent = DIE;
103 do {
104 if (Parent.getTag() == DW_TAG_subprogram) {
105 Parents.push_back(Elt: Parent);
106 break;
107 }
108 if (Parent.getTag() == DW_TAG_inlined_subroutine)
109 Parents.push_back(Elt: Parent);
110 } while ((Parent = Parent.getParent()));
111 return Parents;
112}
113
114struct VarKey {
115 const char *const SubprogramName;
116 const char *const Name;
117 std::string DeclFile;
118 uint64_t DeclLine;
119
120 bool operator==(const VarKey &Other) const {
121 return DeclLine == Other.DeclLine &&
122 !strcmp(s1: SubprogramName, s2: Other.SubprogramName) &&
123 !strcmp(s1: Name, s2: Other.Name) && !DeclFile.compare(str: Other.DeclFile);
124 }
125
126 bool operator<(const VarKey &Other) const {
127 int A = strcmp(s1: SubprogramName, s2: Other.SubprogramName);
128 if (A)
129 return A < 0;
130 int B = strcmp(s1: Name, s2: Other.Name);
131 if (B)
132 return B < 0;
133 int C = DeclFile.compare(str: Other.DeclFile);
134 if (C)
135 return C < 0;
136 return DeclLine < Other.DeclLine;
137 }
138};
139
140struct VarCoverage {
141 SmallVector<DWARFDie> Parents;
142 size_t Cov;
143 size_t Instances;
144};
145
146typedef std::multimap<VarKey, VarCoverage, std::less<>> VarMap;
147
148static std::optional<const VarKey> getVarKey(DWARFDie Die, DWARFDie Parent) {
149 const auto *const DieName = Die.getName(Kind: DINameKind::LinkageName);
150 const auto DieFile =
151 Die.getDeclFile(Kind: DILineInfoSpecifier::FileLineInfoKind::RelativeFilePath);
152 const auto *const ParentName = Parent.getName(Kind: DINameKind::LinkageName);
153 if (!DieName || !ParentName)
154 return std::nullopt;
155 return VarKey{.SubprogramName: ParentName, .Name: DieName, .DeclFile: DieFile, .DeclLine: Die.getDeclLine()};
156}
157
158static void displayParents(SmallVector<DWARFDie> Parents, raw_ostream &OS) {
159 bool First = true;
160 for (const auto Parent : Parents) {
161 if (auto FormValue = Parent.find(Attr: DW_AT_call_file)) {
162 if (auto OptString = FormValue->getAsFile(
163 Kind: DILineInfoSpecifier::FileLineInfoKind::RelativeFilePath)) {
164 if (First)
165 First = false;
166 else
167 OS << ", ";
168 OS << *OptString << ":" << toUnsigned(V: Parent.find(Attr: DW_AT_call_line), Default: 0);
169 }
170 }
171 }
172}
173
174static void displayVariableCoverage(const VarKey &Key, const VarCoverage &Var,
175 bool CombineInstances, raw_ostream &OS) {
176 WithColor(OS, HighlightColor::String) << Key.SubprogramName;
177 OS << "\t";
178 if (CombineInstances)
179 OS << Var.Instances;
180 else if (Var.Parents.size())
181 // FIXME: This may overflow the terminal if the inlining chain is large.
182 displayParents(Parents: Var.Parents, OS);
183 OS << "\t";
184 WithColor(OS, HighlightColor::String) << Key.Name;
185 OS << "\t" << Key.DeclFile << ":" << Key.DeclLine;
186 OS << "\t" << format(Fmt: "%.3g", Vals: ((float)Var.Cov / Var.Instances));
187 OS << "\n";
188}
189
190bool dwarfdump::showVariableCoverage(ObjectFile &Obj, DWARFContext &DICtx,
191 bool CombineInstances, raw_ostream &OS) {
192 VarMap Vars;
193
194 for (const auto &U : DICtx.info_section_units()) {
195 const auto *const LT = DICtx.getLineTableForUnit(U: U.get());
196 for (const auto &Entry : U->dies()) {
197 DWARFDie Die = {U.get(), &Entry};
198 if (Die.getTag() != DW_TAG_variable &&
199 Die.getTag() != DW_TAG_formal_parameter)
200 continue;
201
202 const auto Parents = getParentSubroutines(DIE: Die);
203 if (!Parents.size())
204 continue;
205 const auto Parent = Parents.front();
206 auto Key = getVarKey(Die, Parent);
207 if (!Key)
208 continue;
209
210 const auto Cov = computeVariableCoverage(DICtx, VariableDIE: Die, LineTable: LT);
211
212 VarCoverage VarCov = {.Parents: Parents, .Cov: Cov.size(), .Instances: 1};
213
214 Vars.insert(x: {*Key, VarCov});
215 }
216 }
217
218 std::pair<VarMap::iterator, VarMap::iterator> Range;
219
220 OS << "\nVariable coverage statistics:\nFunction\t"
221 << (CombineInstances ? "InstanceCount" : "InlChain")
222 << "\tVariable\tDecl\tLinesCovered\n";
223
224 if (CombineInstances) {
225 for (auto FirstVar = Vars.begin(); FirstVar != Vars.end();
226 FirstVar = Range.second) {
227 Range = Vars.equal_range(x: FirstVar->first);
228 VarCoverage CombinedCov = {.Parents: {}, .Cov: 0, .Instances: 0};
229 for (auto Var = Range.first; Var != Range.second; ++Var) {
230 ++CombinedCov.Instances;
231 CombinedCov.Cov += Var->second.Cov;
232 }
233 displayVariableCoverage(Key: FirstVar->first, Var: CombinedCov, CombineInstances: true, OS);
234 }
235 } else {
236 for (auto Var : Vars)
237 displayVariableCoverage(Key: Var.first, Var: Var.second, CombineInstances: false, OS);
238 }
239
240 return true;
241}
242