1//===- Utils.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
9#include "llvm/DWARFLinker/Utils.h"
10#include "llvm/ADT/STLExtras.h"
11#include "llvm/ADT/SmallPtrSet.h"
12#include "llvm/DebugInfo/DWARF/DWARFContext.h"
13#include "llvm/DebugInfo/DWARF/DWARFDie.h"
14#include "llvm/DebugInfo/DWARF/DWARFUnit.h"
15#include "llvm/DebugInfo/DWARF/LowLevel/DWARFExpression.h"
16#include "llvm/Support/DJB.h"
17#include <limits>
18#include <map>
19
20namespace llvm {
21namespace dwarf_linker {
22
23bool hasImplicitAddressLocation(const DWARFDie &Die) {
24 std::optional<DWARFFormValue> Location = Die.find(Attr: dwarf::DW_AT_location);
25 if (!Location)
26 return false;
27
28 std::optional<ArrayRef<uint8_t>> Block = Location->getAsBlock();
29 if (!Block)
30 return false;
31
32 DWARFUnit *U = Die.getDwarfUnit();
33 DataExtractor Data(*Block, U->getContext().isLittleEndian());
34 DWARFExpression Expression(Data, U->getAddressByteSize(),
35 U->getFormParams().Format);
36 return !Expression.isMemoryLocation() &&
37 any_of(Range&: Expression, P: [](const DWARFExpression::Operation &Op) {
38 return !Op.isError() && (Op.getCode() == dwarf::DW_OP_addr ||
39 Op.getCode() == dwarf::DW_OP_addrx);
40 });
41}
42
43bool isStaticDataMember(const DWARFDie &Die) {
44 assert(Die.getTag() == dwarf::DW_TAG_member && "expected a DW_TAG_member");
45
46 if (!dwarf::toUnsigned(V: Die.find(Attr: dwarf::DW_AT_declaration), Default: 0))
47 return false;
48
49 // A member that has a location occupies storage in the record regardless of
50 // how else it is marked, so it is the absence of a location that makes this a
51 // pure declaration. Zero is a valid offset, so only the attribute's presence
52 // matters, not its value.
53 return !Die.find(
54 Attrs: {dwarf::DW_AT_data_member_location, dwarf::DW_AT_data_bit_offset});
55}
56
57bool isIdentifiedByChildren(dwarf::Tag Tag) {
58 switch (Tag) {
59 case dwarf::DW_TAG_class_type:
60 case dwarf::DW_TAG_enumeration_type:
61 case dwarf::DW_TAG_interface_type:
62 case dwarf::DW_TAG_structure_type:
63 case dwarf::DW_TAG_union_type:
64 return true;
65 default:
66 return false;
67 }
68}
69
70bool isIdentifyingChild(const DWARFDie &Die) {
71 // Units disagree on implicit member functions and on how static data
72 // members are spelled.
73 switch (Die.getTag()) {
74 case dwarf::DW_TAG_member:
75 return !isStaticDataMember(Die);
76 case dwarf::DW_TAG_enumerator:
77 case dwarf::DW_TAG_inheritance:
78 return true;
79 default:
80 return false;
81 }
82}
83
84static uint32_t hashFullyQualifiedName(
85 DWARFDie Die,
86 function_ref<DWARFDie(const DWARFDie &, const DWARFFormValue &)> ResolveRef,
87 bool IsScope, SmallPtrSetImpl<const DWARFDebugInfoEntry *> &Visited) {
88 const char *Name = nullptr;
89 if (Error Err = finiteLoop(Iteration: [&]() -> Expected<bool> {
90 if (const char *CurrentName = Die.getName(Kind: DINameKind::ShortName))
91 Name = CurrentName;
92
93 std::optional<DWARFFormValue> Ref;
94 if (!(Ref = Die.find(Attr: dwarf::DW_AT_specification)) &&
95 !(Ref = Die.find(Attr: dwarf::DW_AT_abstract_origin)))
96 return false;
97
98 if (!Ref->isFormClass(FC: DWARFFormValue::FC_Reference))
99 return false;
100
101 DWARFDie RefDie = ResolveRef(Die, *Ref);
102 if (!RefDie)
103 return false;
104
105 Die = RefDie;
106 return true;
107 }))
108 consumeError(Err: std::move(Err));
109
110 if (!Name && Die.getTag() == dwarf::DW_TAG_namespace)
111 Name = "(anonymous namespace)";
112
113 // A reference can lead back to a DIE already hashed. End the name there
114 // instead of recursing forever.
115 DWARFDie Parent = Die.getParent();
116 if (!Parent || dwarf::isUnitType(T: Parent.getTag()) ||
117 Parent.getTag() == dwarf::DW_TAG_module ||
118 !Visited.insert(Ptr: Die.getDebugInfoEntry()).second)
119 return djbHash(Buffer: Name ? Name : "", H: djbHash(Buffer: IsScope ? "" : "::"));
120
121 return djbHash(Buffer: Name ? Name : "",
122 H: djbHash(Buffer: Name ? "::" : "",
123 H: hashFullyQualifiedName(Die: Parent, ResolveRef,
124 /*IsScope=*/true, Visited)));
125}
126
127uint32_t hashFullyQualifiedName(
128 DWARFDie Die,
129 function_ref<DWARFDie(const DWARFDie &, const DWARFFormValue &)>
130 ResolveRef) {
131 SmallPtrSet<const DWARFDebugInfoEntry *, 8> Visited;
132 return hashFullyQualifiedName(Die, ResolveRef, /*IsScope=*/false, Visited);
133}
134
135void buildStmtSeqOffsetToFirstRowIndex(
136 const DWARFDebugLine::LineTable &LT,
137 ArrayRef<uint64_t> SortedStmtSeqOffsets,
138 DenseMap<uint64_t, uint64_t> &SeqOffToFirstRow) {
139 // Use std::map for ordered iteration by input stmt-sequence offset.
140 std::map<uint64_t, uint64_t> LineTableMapping;
141 for (const DWARFDebugLine::Sequence &Seq : LT.Sequences)
142 LineTableMapping[Seq.StmtSeqOffset] = Seq.FirstRowIndex;
143
144 if (LT.Rows.empty()) {
145 for (const auto &[Off, Row] : LineTableMapping)
146 SeqOffToFirstRow[Off] = Row;
147 return;
148 }
149
150 // Row indices that look like sequence starts: row 0, plus every row
151 // immediately following an end_sequence marker.
152 SmallVector<uint64_t> SeqStartRows;
153 SeqStartRows.push_back(Elt: 0);
154 for (auto [I, Row] : llvm::enumerate(First: ArrayRef(LT.Rows).drop_back()))
155 if (Row.EndSequence)
156 SeqStartRows.push_back(Elt: I + 1);
157
158 ArrayRef<uint64_t> StmtAttrsRef(SortedStmtSeqOffsets);
159 ArrayRef<uint64_t> SeqStartRowsRef(SeqStartRows);
160
161 // While SeqOffToFirstRow parsed from LT could be the ground truth, e.g.
162 //
163 // SeqOff Row
164 // 0x08 9
165 // 0x14 15
166 //
167 // The StmtAttrs and SeqStartRows may not match perfectly, e.g.
168 //
169 // StmtAttrs SeqStartRows
170 // 0x04 3
171 // 0x08 5
172 // 0x10 9
173 // 0x12 11
174 // 0x14 15
175 //
176 // In this case, we don't want to assign 5 to 0x08, since we know 0x08
177 // maps to 9. If we do a dummy 1:1 mapping 0x10 will be mapped to 9
178 // which is incorrect. The expected behavior is ignore 5, realign the
179 // table based on the result from the line table:
180 //
181 // StmtAttrs SeqStartRows
182 // 0x04 3
183 // -- 5
184 // 0x08 9 <- LineTableMapping ground truth
185 // 0x10 11
186 // 0x12 --
187 // 0x14 15 <- LineTableMapping ground truth
188
189 // Dummy trailing anchor so both refs always drain before we run out
190 // of map entries to walk.
191 constexpr uint64_t DummyKey = std::numeric_limits<uint64_t>::max();
192 constexpr uint64_t DummyVal = std::numeric_limits<uint64_t>::max();
193 LineTableMapping[DummyKey] = DummyVal;
194
195 for (auto [NextSeqOff, NextRow] : LineTableMapping) {
196 auto StmtAttrSmallerThanNext = [N = NextSeqOff](uint64_t SA) {
197 return SA < N;
198 };
199 auto SeqStartSmallerThanNext = [N = NextRow](uint64_t Row) {
200 return Row < N;
201 };
202 // While both lists still point strictly before the next anchor,
203 // pair them up 1:1 — this captures sequences the parser missed.
204 while (!StmtAttrsRef.empty() && !SeqStartRowsRef.empty() &&
205 StmtAttrSmallerThanNext(StmtAttrsRef.front()) &&
206 SeqStartSmallerThanNext(SeqStartRowsRef.front())) {
207 SeqOffToFirstRow[StmtAttrsRef.consume_front()] =
208 SeqStartRowsRef.consume_front();
209 }
210 // Either list may now be ahead of or at the anchor: drop entries we
211 // can't safely pair, then use the parser's (NextSeqOff,NextRow)
212 // mapping as ground truth.
213 StmtAttrsRef = StmtAttrsRef.drop_while(Pred: StmtAttrSmallerThanNext);
214 SeqStartRowsRef = SeqStartRowsRef.drop_while(Pred: SeqStartSmallerThanNext);
215 if (NextSeqOff != DummyKey)
216 SeqOffToFirstRow[NextSeqOff] = NextRow;
217 // Advance each list past the anchor only if it was pointing exactly
218 // at it.
219 if (!StmtAttrsRef.empty() && StmtAttrsRef.front() == NextSeqOff)
220 StmtAttrsRef = StmtAttrsRef.drop_front();
221 if (!SeqStartRowsRef.empty() && SeqStartRowsRef.front() == NextRow)
222 SeqStartRowsRef = SeqStartRowsRef.drop_front();
223 }
224}
225
226} // namespace dwarf_linker
227} // namespace llvm
228