LLVM 19.0.0git
AddressRanges.h
Go to the documentation of this file.
1//===- AddressRanges.h ------------------------------------------*- 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#ifndef LLVM_ADT_ADDRESSRANGES_H
10#define LLVM_ADT_ADDRESSRANGES_H
11
12#include "llvm/ADT/STLExtras.h"
14#include <cassert>
15#include <optional>
16#include <stdint.h>
17
18namespace llvm {
19
20/// A class that represents an address range. The range is specified using
21/// a start and an end address: [Start, End).
23public:
25 AddressRange(uint64_t S, uint64_t E) : Start(S), End(E) {
26 assert(Start <= End);
27 }
28 uint64_t start() const { return Start; }
29 uint64_t end() const { return End; }
30 uint64_t size() const { return End - Start; }
31 uint64_t empty() const { return size() == 0; }
32 bool contains(uint64_t Addr) const { return Start <= Addr && Addr < End; }
33 bool contains(const AddressRange &R) const {
34 return Start <= R.Start && R.End <= End;
35 }
36 bool intersects(const AddressRange &R) const {
37 return Start < R.End && R.Start < End;
38 }
39 bool operator==(const AddressRange &R) const {
40 return Start == R.Start && End == R.End;
41 }
42 bool operator!=(const AddressRange &R) const { return !(*this == R); }
43 bool operator<(const AddressRange &R) const {
44 return std::make_pair(Start, End) < std::make_pair(R.Start, R.End);
45 }
46
47private:
48 uint64_t Start = 0;
49 uint64_t End = 0;
50};
51
52/// The AddressRangesBase class presents the base functionality for the
53/// normalized address ranges collection. This class keeps a sorted vector
54/// of AddressRange-like objects and can perform searches efficiently.
55/// The address ranges are always sorted and never contain any invalid,
56/// empty or intersected address ranges.
57
58template <typename T> class AddressRangesBase {
59protected:
62
63public:
64 void clear() { Ranges.clear(); }
65 bool empty() const { return Ranges.empty(); }
66 bool contains(uint64_t Addr) const {
67 return find(Addr, Addr + 1) != Ranges.end();
68 }
69 bool contains(AddressRange Range) const {
70 return find(Range.start(), Range.end()) != Ranges.end();
71 }
72 void reserve(size_t Capacity) { Ranges.reserve(Capacity); }
73 size_t size() const { return Ranges.size(); }
74
75 std::optional<T> getRangeThatContains(uint64_t Addr) const {
76 typename Collection::const_iterator It = find(Addr, Addr + 1);
77 if (It == Ranges.end())
78 return std::nullopt;
79
80 return *It;
81 }
82
83 typename Collection::const_iterator begin() const { return Ranges.begin(); }
84 typename Collection::const_iterator end() const { return Ranges.end(); }
85
86 const T &operator[](size_t i) const {
87 assert(i < Ranges.size());
88 return Ranges[i];
89 }
90
91 bool operator==(const AddressRangesBase<T> &RHS) const {
92 return Ranges == RHS.Ranges;
93 }
94
95protected:
96 typename Collection::const_iterator find(uint64_t Start, uint64_t End) const {
97 if (Start >= End)
98 return Ranges.end();
99
100 auto It =
101 std::partition_point(Ranges.begin(), Ranges.end(), [=](const T &R) {
102 return AddressRange(R).start() <= Start;
103 });
104
105 if (It == Ranges.begin())
106 return Ranges.end();
107
108 --It;
109 if (End > AddressRange(*It).end())
110 return Ranges.end();
111
112 return It;
113 }
114};
115
116/// The AddressRanges class helps normalize address range collections.
117/// This class keeps a sorted vector of AddressRange objects and can perform
118/// insertions and searches efficiently. Intersecting([100,200), [150,300))
119/// and adjacent([100,200), [200,300)) address ranges are combined during
120/// insertion.
121class AddressRanges : public AddressRangesBase<AddressRange> {
122public:
124 if (Range.empty())
125 return Ranges.end();
126
127 auto It = llvm::upper_bound(Ranges, Range);
128 auto It2 = It;
129 while (It2 != Ranges.end() && It2->start() <= Range.end())
130 ++It2;
131 if (It != It2) {
132 Range = {Range.start(), std::max(Range.end(), std::prev(It2)->end())};
133 It = Ranges.erase(It, It2);
134 }
135 if (It != Ranges.begin() && Range.start() <= std::prev(It)->end()) {
136 --It;
137 *It = {It->start(), std::max(It->end(), Range.end())};
138 return It;
139 }
140
141 return Ranges.insert(It, Range);
142 }
143};
144
146public:
147 operator AddressRange() const { return Range; }
148
150 int64_t Value = 0;
151};
152
154 const AddressRangeValuePair &RHS) {
155 return LHS.Range == RHS.Range && LHS.Value == RHS.Value;
156}
157
158/// AddressRangesMap class maps values to the address ranges.
159/// It keeps normalized address ranges and corresponding values.
160/// This class keeps a sorted vector of AddressRangeValuePair objects
161/// and can perform insertions and searches efficiently.
162/// Intersecting([100,200), [150,300)) ranges splitted into non-conflicting
163/// parts([100,200), [200,300)). Adjacent([100,200), [200,300)) address
164/// ranges are not combined during insertion.
165class AddressRangesMap : public AddressRangesBase<AddressRangeValuePair> {
166public:
167 void insert(AddressRange Range, int64_t Value) {
168 if (Range.empty())
169 return;
170
171 // Search for range which is less than or equal incoming Range.
172 auto It = std::partition_point(Ranges.begin(), Ranges.end(),
173 [=](const AddressRangeValuePair &R) {
174 return R.Range.start() <= Range.start();
175 });
176
177 if (It != Ranges.begin())
178 It--;
179
180 while (!Range.empty()) {
181 // Inserted range does not overlap with any range.
182 // Store it into the Ranges collection.
183 if (It == Ranges.end() || Range.end() <= It->Range.start()) {
184 Ranges.insert(It, {Range, Value});
185 return;
186 }
187
188 // Inserted range partially overlaps with current range.
189 // Store not overlapped part of inserted range.
190 if (Range.start() < It->Range.start()) {
191 It = Ranges.insert(It, {{Range.start(), It->Range.start()}, Value});
192 It++;
193 Range = {It->Range.start(), Range.end()};
194 continue;
195 }
196
197 // Inserted range fully overlaps with current range.
198 if (Range.end() <= It->Range.end())
199 return;
200
201 // Inserted range partially overlaps with current range.
202 // Remove overlapped part from the inserted range.
203 if (Range.start() < It->Range.end())
204 Range = {It->Range.end(), Range.end()};
205
206 It++;
207 }
208 }
209};
210
211} // namespace llvm
212
213#endif // LLVM_ADT_ADDRESSRANGES_H
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
uint64_t Addr
bool End
Definition: ELF_riscv.cpp:480
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
This file contains some templates that are useful if you are working with the STL at all.
This file defines the SmallVector class.
Value * RHS
Value * LHS
A class that represents an address range.
Definition: AddressRanges.h:22
AddressRange(uint64_t S, uint64_t E)
Definition: AddressRanges.h:25
uint64_t start() const
Definition: AddressRanges.h:28
bool operator<(const AddressRange &R) const
Definition: AddressRanges.h:43
uint64_t empty() const
Definition: AddressRanges.h:31
uint64_t end() const
Definition: AddressRanges.h:29
bool contains(const AddressRange &R) const
Definition: AddressRanges.h:33
bool intersects(const AddressRange &R) const
Definition: AddressRanges.h:36
bool operator!=(const AddressRange &R) const
Definition: AddressRanges.h:42
bool contains(uint64_t Addr) const
Definition: AddressRanges.h:32
bool operator==(const AddressRange &R) const
Definition: AddressRanges.h:39
uint64_t size() const
Definition: AddressRanges.h:30
The AddressRangesBase class presents the base functionality for the normalized address ranges collect...
Definition: AddressRanges.h:58
const T & operator[](size_t i) const
Definition: AddressRanges.h:86
void reserve(size_t Capacity)
Definition: AddressRanges.h:72
bool contains(uint64_t Addr) const
Definition: AddressRanges.h:66
bool operator==(const AddressRangesBase< T > &RHS) const
Definition: AddressRanges.h:91
SmallVector< T > Collection
Definition: AddressRanges.h:60
Collection::const_iterator find(uint64_t Start, uint64_t End) const
Definition: AddressRanges.h:96
std::optional< T > getRangeThatContains(uint64_t Addr) const
Definition: AddressRanges.h:75
bool contains(AddressRange Range) const
Definition: AddressRanges.h:69
Collection::const_iterator end() const
Definition: AddressRanges.h:84
Collection::const_iterator begin() const
Definition: AddressRanges.h:83
AddressRangesMap class maps values to the address ranges.
void insert(AddressRange Range, int64_t Value)
The AddressRanges class helps normalize address range collections.
Collection::const_iterator insert(AddressRange Range)
iterator erase(const_iterator CI)
Definition: SmallVector.h:750
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:818
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1209
LLVM Value Representation.
Definition: Value.h:74
Value(Type *Ty, unsigned scid)
Definition: Value.cpp:53
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
auto upper_bound(R &&Range, T &&Value)
Provide wrappers to std::upper_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1963
bool operator==(const AddressRangeValuePair &LHS, const AddressRangeValuePair &RHS)