LLVM 20.0.0git
LVRange.cpp
Go to the documentation of this file.
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
16
17using namespace llvm;
18using namespace llvm::logicalview;
19
20#define DEBUG_TYPE "Range"
21
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) {
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
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(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
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.
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) {
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.
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.
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
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();
150 Indentation = options().indentationSize();
151 if (Indentation)
152 OS << " ";
153 OS << format("[0x%08x,0x%08x] ", RangeEntry.lower(), RangeEntry.upper())
155 << "\n";
156 }
158}
#define LLVM_DEBUG(X)
Definition: Debug.h:101
bool End
Definition: ELF_riscv.cpp:480
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
void clear()
Remove all entries.
Definition: IntervalTree.h:599
void print(raw_ostream &OS, bool HexFormat=true)
Print the interval tree.
Definition: IntervalTree.h:641
void insert(PointType Left, PointType Right, ValueType Value)
Add a mapping of [Left;Right] to Value.
Definition: IntervalTree.h:609
find_iterator find_end() const
Iterator to end find operation.
Definition: IntervalTree.h:687
void create()
Create the interval tree.
Definition: IntervalTree.h:646
find_iterator find(PointType Point) const
Iterator to start a find operation; it returns find_end() if the tree has not been built.
Definition: IntervalTree.h:680
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
Target - Wrapper for Target specific information.
StringRef getName() const override
Definition: LVElement.h:184
void printAttributes(raw_ostream &OS, bool Full=true) const
Definition: LVObject.cpp:139
LVLevel getLevel() const
Definition: LVObject.h:242
size_t indentationSize() const
Definition: LVOptions.h:312
RangeType lower() const
Definition: LVRange.h:37
RangeType upper() const
Definition: LVRange.h:38
LVScope * getEntry(LVAddress Address) const
Definition: LVRange.cpp:83
bool hasEntry(LVAddress Low, LVAddress High) const
Definition: LVRange.cpp:118
void printExtra(raw_ostream &OS, bool Full=true) const override
Definition: LVRange.h:88
void print(raw_ostream &OS, bool Full=true) const override
Definition: LVRange.cpp:145
void addEntry(LVScope *Scope, LVAddress LowerAddress, LVAddress UpperAddress)
Definition: LVRange.cpp:52
const char * kind() const override
Definition: LVScope.cpp:49
const LVLocations * getRanges() const
Definition: LVScope.h:206
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
FormattedNumber hexValue(uint64_t N, unsigned Width=HEX_WIDTH, bool Upper=false)
Definition: LVSupport.h:103
std::string formattedKind(StringRef Kind)
Definition: LVSupport.h:216
std::string formattedName(StringRef Name)
Definition: LVSupport.h:220
LVOptions & options()
Definition: LVOptions.h:445
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
FormattedNumber format_decimal(int64_t N, unsigned Width)
format_decimal - Output N as a right justified, fixed-width decimal.
Definition: Format.h:212
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
format_object< Ts... > format(const char *Fmt, const Ts &... Vals)
These are helper functions used to produce formatted output.
Definition: Format.h:125
void swap(llvm::BitVector &LHS, llvm::BitVector &RHS)
Implement std::swap in terms of BitVector swap.
Definition: BitVector.h:860