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
17using namespace llvm;
18using namespace llvm::logicalview;
19
20#define DEBUG_TYPE "Range"
21
22void 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(Left: RangeEntry.lower(), Right: RangeEntry.upper(),
37 Value: 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.
52void LVRange::addEntry(LVScope *Scope, LVAddress LowerAddress,
53 LVAddress UpperAddress) {
54 // We assume the low <= high.
55 if (LowerAddress > UpperAddress)
56 std::swap(a&: LowerAddress, b&: 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(args&: LowerAddress, args&: UpperAddress, args&: Scope);
66}
67
68void 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(Low: LowPC, High: HighPC))
77 // Add the pair of addresses.
78 addEntry(Scope, LowerAddress: LowPC, UpperAddress: HighPC);
79 }
80}
81
82// Get the scope associated with the input address.
83LVScope *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(Point: 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.
109LVScope *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].
118bool 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.
127void 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 llvm::stable_sort(Range&: RangeEntries, C: CompareRangeEntry);
143}
144
145void 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(Fmt: "[0x%08x,0x%08x] ", Vals: RangeEntry.lower(), Vals: RangeEntry.upper())
154 << formattedKind(Kind: Scope->kind()) << " " << formattedName(Name: Scope->getName())
155 << "\n";
156 }
157 printExtra(OS, Full);
158}
159