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
41void buildStmtSeqOffsetToFirstRowIndex(
42 const DWARFDebugLine::LineTable &LT,
43 ArrayRef<uint64_t> SortedStmtSeqOffsets,
44 DenseMap<uint64_t, uint64_t> &SeqOffToFirstRow) {
45 // Use std::map for ordered iteration by input stmt-sequence offset.
46 std::map<uint64_t, uint64_t> LineTableMapping;
47 for (const DWARFDebugLine::Sequence &Seq : LT.Sequences)
48 LineTableMapping[Seq.StmtSeqOffset] = Seq.FirstRowIndex;
49
50 if (LT.Rows.empty()) {
51 for (const auto &[Off, Row] : LineTableMapping)
52 SeqOffToFirstRow[Off] = Row;
53 return;
54 }
55
56 // Row indices that look like sequence starts: row 0, plus every row
57 // immediately following an end_sequence marker.
58 SmallVector<uint64_t> SeqStartRows;
59 SeqStartRows.push_back(Elt: 0);
60 for (auto [I, Row] : llvm::enumerate(First: ArrayRef(LT.Rows).drop_back()))
61 if (Row.EndSequence)
62 SeqStartRows.push_back(Elt: I + 1);
63
64 ArrayRef<uint64_t> StmtAttrsRef(SortedStmtSeqOffsets);
65 ArrayRef<uint64_t> SeqStartRowsRef(SeqStartRows);
66
67 // While SeqOffToFirstRow parsed from LT could be the ground truth, e.g.
68 //
69 // SeqOff Row
70 // 0x08 9
71 // 0x14 15
72 //
73 // The StmtAttrs and SeqStartRows may not match perfectly, e.g.
74 //
75 // StmtAttrs SeqStartRows
76 // 0x04 3
77 // 0x08 5
78 // 0x10 9
79 // 0x12 11
80 // 0x14 15
81 //
82 // In this case, we don't want to assign 5 to 0x08, since we know 0x08
83 // maps to 9. If we do a dummy 1:1 mapping 0x10 will be mapped to 9
84 // which is incorrect. The expected behavior is ignore 5, realign the
85 // table based on the result from the line table:
86 //
87 // StmtAttrs SeqStartRows
88 // 0x04 3
89 // -- 5
90 // 0x08 9 <- LineTableMapping ground truth
91 // 0x10 11
92 // 0x12 --
93 // 0x14 15 <- LineTableMapping ground truth
94
95 // Dummy trailing anchor so both refs always drain before we run out
96 // of map entries to walk.
97 constexpr uint64_t DummyKey = std::numeric_limits<uint64_t>::max();
98 constexpr uint64_t DummyVal = std::numeric_limits<uint64_t>::max();
99 LineTableMapping[DummyKey] = DummyVal;
100
101 for (auto [NextSeqOff, NextRow] : LineTableMapping) {
102 auto StmtAttrSmallerThanNext = [N = NextSeqOff](uint64_t SA) {
103 return SA < N;
104 };
105 auto SeqStartSmallerThanNext = [N = NextRow](uint64_t Row) {
106 return Row < N;
107 };
108 // While both lists still point strictly before the next anchor,
109 // pair them up 1:1 — this captures sequences the parser missed.
110 while (!StmtAttrsRef.empty() && !SeqStartRowsRef.empty() &&
111 StmtAttrSmallerThanNext(StmtAttrsRef.front()) &&
112 SeqStartSmallerThanNext(SeqStartRowsRef.front())) {
113 SeqOffToFirstRow[StmtAttrsRef.consume_front()] =
114 SeqStartRowsRef.consume_front();
115 }
116 // Either list may now be ahead of or at the anchor: drop entries we
117 // can't safely pair, then use the parser's (NextSeqOff,NextRow)
118 // mapping as ground truth.
119 StmtAttrsRef = StmtAttrsRef.drop_while(Pred: StmtAttrSmallerThanNext);
120 SeqStartRowsRef = SeqStartRowsRef.drop_while(Pred: SeqStartSmallerThanNext);
121 if (NextSeqOff != DummyKey)
122 SeqOffToFirstRow[NextSeqOff] = NextRow;
123 // Advance each list past the anchor only if it was pointing exactly
124 // at it.
125 if (!StmtAttrsRef.empty() && StmtAttrsRef.front() == NextSeqOff)
126 StmtAttrsRef = StmtAttrsRef.drop_front();
127 if (!SeqStartRowsRef.empty() && SeqStartRowsRef.front() == NextRow)
128 SeqStartRowsRef = SeqStartRowsRef.drop_front();
129 }
130}
131
132} // namespace dwarf_linker
133} // namespace llvm
134