LLVM  16.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/Optional.h"
13 #include "llvm/ADT/STLExtras.h"
14 #include "llvm/ADT/SmallVector.h"
15 #include <cassert>
16 #include <stdint.h>
17 
18 namespace llvm {
19 
20 /// A class that represents an address range. The range is specified using
21 /// a start and an end address: [Start, End).
22 class AddressRange {
23 public:
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 
43 private:
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.
55 protected:
58 
59 public:
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  }
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  }
83  Collection::const_iterator begin() const { return Ranges.begin(); }
84  Collection::const_iterator end() const { return Ranges.end(); }
85 
86 protected:
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.
95 template <typename T> class AddressRangesMap : protected AddressRanges {
96 public:
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  }
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 
140 protected:
143 };
144 
145 } // namespace llvm
146 
147 #endif // LLVM_ADT_ADDRESSRANGES_H
i
i
Definition: README.txt:29
llvm::AddressRange::AddressRange
AddressRange()
Definition: AddressRanges.h:24
llvm
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
llvm::SmallVectorImpl::erase
iterator erase(const_iterator CI)
Definition: SmallVector.h:741
llvm::AddressRanges::contains
bool contains(uint64_t Addr) const
Definition: AddressRanges.h:62
llvm::AddressRanges::reserve
void reserve(size_t Capacity)
Definition: AddressRanges.h:74
Optional.h
llvm::SmallVector< AddressRange >
llvm::AddressRanges::begin
Collection::const_iterator begin() const
Definition: AddressRanges.h:83
llvm::Optional
Definition: APInt.h:33
T
#define T
Definition: Mips16ISelLowering.cpp:341
STLExtras.h
RHS
Value * RHS
Definition: X86PartialReduction.cpp:76
llvm::AddressRanges::operator==
bool operator==(const AddressRanges &RHS) const
Definition: AddressRanges.h:76
llvm::AddressRangesMap::insert
void insert(AddressRange Range, T Value)
Definition: AddressRanges.h:106
E
static GCRegistry::Add< CoreCLRGC > E("coreclr", "CoreCLR-compatible GC")
llvm::AddressRanges::empty
bool empty() const
Definition: AddressRanges.h:61
llvm::AddressRanges::find
Collection::const_iterator find(uint64_t Addr) const
Definition: AddressRanges.cpp:38
llvm::AddressRangesMap::contains
bool contains(uint64_t Addr) const
Definition: AddressRanges.h:102
llvm::AddressRangesMap::Values
ValuesCollection Values
Definition: AddressRanges.h:142
llvm::AddressRangesMap::size
size_t size() const
Definition: AddressRanges.h:124
llvm::AddressRangesMap::clear
void clear()
Definition: AddressRanges.h:97
llvm::AddressRange
A class that represents an address range.
Definition: AddressRanges.h:22
llvm::AddressRange::operator<
bool operator<(const AddressRange &R) const
Definition: AddressRanges.h:39
uint64_t
Addr
uint64_t Addr
Definition: ELFObjHandler.cpp:79
llvm::AddressRanges::operator[]
const AddressRange & operator[](size_t i) const
Definition: AddressRanges.h:79
llvm::AddressRangesMap
AddressRangesMap class maps values to the address ranges.
Definition: AddressRanges.h:95
llvm::SmallVectorImpl< AddressRange >::const_iterator
typename SuperClass::const_iterator const_iterator
Definition: SmallVector.h:582
assert
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
llvm::AddressRange::end
uint64_t end() const
Definition: AddressRanges.h:29
llvm::AddressRange::operator==
bool operator==(const AddressRange &R) const
Definition: AddressRanges.h:35
llvm::AddressRange::AddressRange
AddressRange(uint64_t S, uint64_t E)
Definition: AddressRanges.h:25
llvm::AddressRanges::clear
void clear()
Definition: AddressRanges.h:60
llvm::AddressRangesMap::empty
bool empty() const
Definition: AddressRanges.h:101
S
add sub stmia L5 ldr r0 bl L_printf $stub Instead of a and a wouldn t it be better to do three moves *Return an aggregate type is even return S
Definition: README.txt:210
llvm::AddressRange::intersects
bool intersects(const AddressRange &R) const
Definition: AddressRanges.h:32
llvm::AddressRangesMap::operator[]
std::pair< AddressRange, T > operator[](size_t Idx) const
Definition: AddressRanges.h:136
llvm::AddressRanges::insert
Collection::const_iterator insert(AddressRange Range)
Definition: AddressRanges.cpp:16
llvm::AddressRanges::getRangeThatContains
Optional< AddressRange > getRangeThatContains(uint64_t Addr) const
Definition: AddressRanges.h:66
llvm::AddressRange::operator!=
bool operator!=(const AddressRange &R) const
Definition: AddressRanges.h:38
llvm::AddressRanges::size
size_t size() const
Definition: AddressRanges.h:75
llvm::TargetStackID::Value
Value
Definition: TargetFrameLowering.h:27
llvm::SmallVectorImpl::clear
void clear()
Definition: SmallVector.h:614
llvm::AddressRange::size
uint64_t size() const
Definition: AddressRanges.h:30
llvm::AddressRangesMap::contains
bool contains(AddressRange Range) const
Definition: AddressRanges.h:103
SmallVector.h
llvm::AddressRanges::contains
bool contains(AddressRange Range) const
Definition: AddressRanges.h:63
llvm::SmallVectorImpl< int64_t >::iterator
typename SuperClass::iterator iterator
Definition: SmallVector.h:581
llvm::AddressRanges
The AddressRanges class helps normalize address range collections.
Definition: AddressRanges.h:54
llvm::AddressRanges::end
Collection::const_iterator end() const
Definition: AddressRanges.h:84
llvm::AddressRangesMap::getRangeValueThatContains
Optional< std::pair< AddressRange, T > > getRangeValueThatContains(uint64_t Addr) const
Definition: AddressRanges.h:129
llvm::AddressRanges::Ranges
Collection Ranges
Definition: AddressRanges.h:57
llvm::SmallVectorImpl::reserve
void reserve(size_type N)
Definition: SmallVector.h:667
llvm::AddressRange::start
uint64_t start() const
Definition: AddressRanges.h:28
llvm::Value
LLVM Value Representation.
Definition: Value.h:74
llvm::AddressRange::contains
bool contains(uint64_t Addr) const
Definition: AddressRanges.h:31
llvm::SmallVectorImpl::insert
iterator insert(iterator I, T &&Elt)
Definition: SmallVector.h:809