1 //===-- LVRange.cpp -------------------------------------------------------===//
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 // This implements the LVRange class.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "llvm/DebugInfo/LogicalView/Core/LVRange.h"
14 #include "llvm/DebugInfo/LogicalView/Core/LVLocation.h"
15 #include "llvm/DebugInfo/LogicalView/Core/LVOptions.h"
16
17 using namespace llvm;
18 using namespace llvm::logicalview;
19
20 #define DEBUG_TYPE "Range"
21
startSearch()22 void LVRange::startSearch() {
23 RangesTree.clear();
24
25 LLVM_DEBUG({ dbgs() << "\nRanges Tree entries:\n"; });
26
27 // Traverse the ranges and store them into the interval tree.
28 for (LVRangeEntry &RangeEntry : RangeEntries) {
29 LLVM_DEBUG({
30 LVScope *Scope = RangeEntry.scope();
31 dbgs() << "Scope: " << format_decimal(Scope->getLevel(), 5) << " "
32 << "Range: [" << hexValue(RangeEntry.lower()) << ":"
33 << hexValue(RangeEntry.upper()) << "]\n";
34 });
35
36 RangesTree.insert(RangeEntry.lower(), RangeEntry.upper(),
37 RangeEntry.scope());
38 }
39
40 // Create the interval tree.
41 RangesTree.create();
42
43 LLVM_DEBUG({
44 dbgs() << "\nRanges Tree:\n";
45 RangesTree.print(dbgs());
46 });
47 }
48
49 // Add the pair in an ascending order, with the smallest ranges at the
50 // start; in that way, enclosing scopes ranges are at the end of the
51 // list; we assume that low <= high.
addEntry(LVScope * Scope,LVAddress LowerAddress,LVAddress UpperAddress)52 void LVRange::addEntry(LVScope *Scope, LVAddress LowerAddress,
53 LVAddress UpperAddress) {
54 // We assume the low <= high.
55 if (LowerAddress > UpperAddress)
56 std::swap(LowerAddress, UpperAddress);
57
58 // Record the lowest and highest seen addresses.
59 if (LowerAddress < Lower)
60 Lower = LowerAddress;
61 if (UpperAddress > Upper)
62 Upper = UpperAddress;
63
64 // Just add the scope and range pair, in no particular order.
65 RangeEntries.emplace_back(LowerAddress, UpperAddress, Scope);
66 }
67
addEntry(LVScope * Scope)68 void LVRange::addEntry(LVScope *Scope) {
69 assert(Scope && "Scope must not be nullptr");
70 // Traverse the ranges and update the ranges set only if the ranges
71 // values are not already recorded.
72 if (const LVLocations *Locations = Scope->getRanges())
73 for (const LVLocation *Location : *Locations) {
74 LVAddress LowPC = Location->getLowerAddress();
75 LVAddress HighPC = Location->getUpperAddress();
76 if (!hasEntry(LowPC, HighPC))
77 // Add the pair of addresses.
78 addEntry(Scope, LowPC, HighPC);
79 }
80 }
81
82 // Get the scope associated with the input address.
getEntry(LVAddress Address) const83 LVScope *LVRange::getEntry(LVAddress Address) const {
84 LLVM_DEBUG({ dbgs() << format("Searching: 0x%08x\nFound: ", Address); });
85
86 LVScope *Target = nullptr;
87 LVLevel TargetLevel = 0;
88 LVLevel Level = 0;
89 LVScope *Scope = nullptr;
90 for (LVRangesTree::find_iterator Iter = RangesTree.find(Address),
91 End = RangesTree.find_end();
92 Iter != End; ++Iter) {
93 LLVM_DEBUG(
94 { dbgs() << format("[0x%08x,0x%08x] ", Iter->left(), Iter->right()); });
95 Scope = Iter->value();
96 Level = Scope->getLevel();
97 if (Level > TargetLevel) {
98 TargetLevel = Level;
99 Target = Scope;
100 }
101 }
102
103 LLVM_DEBUG({ dbgs() << (Scope ? "\n" : "None\n"); });
104
105 return Target;
106 }
107
108 // Find the associated Scope for the given ranges values.
getEntry(LVAddress LowerAddress,LVAddress UpperAddress) const109 LVScope *LVRange::getEntry(LVAddress LowerAddress,
110 LVAddress UpperAddress) const {
111 for (const LVRangeEntry &RangeEntry : RangeEntries)
112 if (LowerAddress >= RangeEntry.lower() && UpperAddress < RangeEntry.upper())
113 return RangeEntry.scope();
114 return nullptr;
115 }
116
117 // True if the range addresses contain the pair [LowerAddress, UpperAddress].
hasEntry(LVAddress LowerAddress,LVAddress UpperAddress) const118 bool LVRange::hasEntry(LVAddress LowerAddress, LVAddress UpperAddress) const {
119 for (const LVRangeEntry &RangeEntry : RangeEntries)
120 if (LowerAddress == RangeEntry.lower() &&
121 UpperAddress == RangeEntry.upper())
122 return true;
123 return false;
124 }
125
126 // Sort the range elements for the whole Compile Unit.
sort()127 void LVRange::sort() {
128 auto CompareRangeEntry = [](const LVRangeEntry &lhs,
129 const LVRangeEntry &rhs) -> bool {
130 if (lhs.lower() < rhs.lower())
131 return true;
132
133 // If the lower address is the same, use the upper address value in
134 // order to put first the smallest interval.
135 if (lhs.lower() == rhs.lower())
136 return lhs.upper() < rhs.upper();
137
138 return false;
139 };
140
141 // Sort the ranges using low address and range size.
142 std::stable_sort(RangeEntries.begin(), RangeEntries.end(), CompareRangeEntry);
143 }
144
print(raw_ostream & OS,bool Full) const145 void LVRange::print(raw_ostream &OS, bool Full) const {
146 size_t Indentation = 0;
147 for (const LVRangeEntry &RangeEntry : RangeEntries) {
148 LVScope *Scope = RangeEntry.scope();
149 Scope->printAttributes(OS, Full);
150 Indentation = options().indentationSize();
151 if (Indentation)
152 OS << " ";
153 OS << format("[0x%08x,0x%08x] ", RangeEntry.lower(), RangeEntry.upper())
154 << formattedKind(Scope->kind()) << " " << formattedName(Scope->getName())
155 << "\n";
156 }
157 printExtra(OS, Full);
158 }
159