LLVM 17.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 bool contains(uint64_t Addr) const { return Start <= Addr && Addr < End; }
32 bool intersects(const AddressRange &R) const {
33 return Start < R.End && R.Start < End;
34 }
35 bool operator==(const AddressRange &R) const {
36 return Start == R.Start && End == R.End;
37 }
38 bool operator!=(const AddressRange &R) const { return !(*this == R); }
39 bool operator<(const AddressRange &R) const {
40 return std::make_pair(Start, End) < std::make_pair(R.Start, R.End);
41 }
42
43private:
44 uint64_t Start = 0;
45 uint64_t End = 0;
46};
47
48/// The AddressRanges class helps normalize address range collections.
49/// This class keeps a sorted vector of AddressRange objects and can perform
50/// insertions and searches efficiently. The address ranges are always sorted
51/// and never contain any invalid or empty address ranges.
52/// Intersecting([100,200), [150,300)) and adjacent([100,200), [200,300))
53/// address ranges are combined during insertion.
55protected:
58
59public:
60 void clear() { Ranges.clear(); }
61 bool empty() const { return Ranges.empty(); }
62 bool contains(uint64_t Addr) const { return find(Addr) != Ranges.end(); }
63 bool contains(AddressRange Range) const {
64 return find(Range) != Ranges.end();
65 }
66 std::optional<AddressRange> getRangeThatContains(uint64_t Addr) const {
68 if (It == Ranges.end())
69 return std::nullopt;
70
71 return *It;
72 }
74 void reserve(size_t Capacity) { Ranges.reserve(Capacity); }
75 size_t size() const { return Ranges.size(); }
76 bool operator==(const AddressRanges &RHS) const {
77 return Ranges == RHS.Ranges;
78 }
79 const AddressRange &operator[](size_t i) const {
80 assert(i < Ranges.size());
81 return Ranges[i];
82 }
85
86protected:
89};
90
91/// AddressRangesMap class maps values to the address ranges.
92/// It keeps address ranges and corresponding values. If ranges
93/// are combined during insertion, then combined range keeps
94/// newly inserted value.
95template <typename T> class AddressRangesMap : protected AddressRanges {
96public:
97 void clear() {
98 Ranges.clear();
99 Values.clear();
100 }
101 bool empty() const { return AddressRanges::empty(); }
103 bool contains(AddressRange Range) const {
104 return AddressRanges::contains(Range);
105 }
106 void insert(AddressRange Range, T Value) {
107 size_t InputSize = Ranges.size();
109 if (RangesIt == Ranges.end())
110 return;
111
112 // make Values match to Ranges.
113 size_t Idx = RangesIt - Ranges.begin();
114 typename ValuesCollection::iterator ValuesIt = Values.begin() + Idx;
115 if (InputSize < Ranges.size())
116 Values.insert(ValuesIt, T());
117 else if (InputSize > Ranges.size())
118 Values.erase(ValuesIt, ValuesIt + InputSize - Ranges.size());
119 assert(Ranges.size() == Values.size());
120
121 // set value to the inserted or combined range.
122 Values[Idx] = Value;
123 }
124 size_t size() const {
125 assert(Ranges.size() == Values.size());
126 return AddressRanges::size();
127 }
128 std::optional<std::pair<AddressRange, T>>
131 if (It == Ranges.end())
132 return std::nullopt;
133
134 return std::make_pair(*It, Values[It - Ranges.begin()]);
135 }
136 std::pair<AddressRange, T> operator[](size_t Idx) const {
137 return std::make_pair(Ranges[Idx], Values[Idx]);
138 }
139
140protected:
143};
144
145} // namespace llvm
146
147#endif // LLVM_ADT_ADDRESSRANGES_H
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
Returns the sub type a function will return at a given Idx Should correspond to the result type of an ExtractValue instruction executed with just that one unsigned Idx
uint64_t Addr
#define T
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
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:39
uint64_t end() const
Definition: AddressRanges.h:29
bool intersects(const AddressRange &R) const
Definition: AddressRanges.h:32
bool operator!=(const AddressRange &R) const
Definition: AddressRanges.h:38
bool contains(uint64_t Addr) const
Definition: AddressRanges.h:31
bool operator==(const AddressRange &R) const
Definition: AddressRanges.h:35
uint64_t size() const
Definition: AddressRanges.h:30
AddressRangesMap class maps values to the address ranges.
Definition: AddressRanges.h:95
ValuesCollection Values
std::pair< AddressRange, T > operator[](size_t Idx) const
bool contains(AddressRange Range) const
bool contains(uint64_t Addr) const
SmallVector< T > ValuesCollection
void insert(AddressRange Range, T Value)
std::optional< std::pair< AddressRange, T > > getRangeValueThatContains(uint64_t Addr) const
The AddressRanges class helps normalize address range collections.
Definition: AddressRanges.h:54
bool contains(AddressRange Range) const
Definition: AddressRanges.h:63
Collection::const_iterator end() const
Definition: AddressRanges.h:84
bool operator==(const AddressRanges &RHS) const
Definition: AddressRanges.h:76
bool empty() const
Definition: AddressRanges.h:61
bool contains(uint64_t Addr) const
Definition: AddressRanges.h:62
size_t size() const
Definition: AddressRanges.h:75
std::optional< AddressRange > getRangeThatContains(uint64_t Addr) const
Definition: AddressRanges.h:66
const AddressRange & operator[](size_t i) const
Definition: AddressRanges.h:79
void reserve(size_t Capacity)
Definition: AddressRanges.h:74
Collection::const_iterator insert(AddressRange Range)
Collection::const_iterator begin() const
Definition: AddressRanges.h:83
Collection::const_iterator find(uint64_t Addr) const
bool empty() const
Definition: SmallVector.h:94
size_t size() const
Definition: SmallVector.h:91
void reserve(size_type N)
Definition: SmallVector.h:667
LLVM Value Representation.
Definition: Value.h:74
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18