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