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