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