LLVM 20.0.0git
ConstantRangeList.cpp
Go to the documentation of this file.
1//===- ConstantRangeList.cpp - ConstantRangeList implementation -----------===//
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
10#include <cstddef>
11
12using namespace llvm;
13
15 if (RangesRef.empty())
16 return true;
17 auto Range = RangesRef[0];
19 return false;
20 for (unsigned i = 1; i < RangesRef.size(); i++) {
21 auto CurRange = RangesRef[i];
22 auto PreRange = RangesRef[i - 1];
23 if (CurRange.getLower().sge(CurRange.getUpper()) ||
24 CurRange.getLower().sle(PreRange.getUpper()))
25 return false;
26 }
27 return true;
28}
29
30std::optional<ConstantRangeList>
32 if (!isOrderedRanges(RangesRef))
33 return std::nullopt;
34 return ConstantRangeList(RangesRef);
35}
36
38 if (NewRange.isEmptySet())
39 return;
40 assert(!NewRange.isFullSet() && "Do not support full set");
41 assert(NewRange.getLower().slt(NewRange.getUpper()));
42 assert(getBitWidth() == NewRange.getBitWidth());
43 // Handle common cases.
44 if (empty() || Ranges.back().getUpper().slt(NewRange.getLower())) {
45 Ranges.push_back(NewRange);
46 return;
47 }
48 if (NewRange.getUpper().slt(Ranges.front().getLower())) {
49 Ranges.insert(Ranges.begin(), NewRange);
50 return;
51 }
52
53 auto LowerBound = lower_bound(
54 Ranges, NewRange, [](const ConstantRange &a, const ConstantRange &b) {
55 return a.getLower().slt(b.getLower());
56 });
57 if (LowerBound != Ranges.end() && LowerBound->contains(NewRange))
58 return;
59
60 // Slow insert.
61 SmallVector<ConstantRange, 2> ExistingTail(LowerBound, Ranges.end());
62 Ranges.erase(LowerBound, Ranges.end());
63 // Merge consecutive ranges.
64 if (!Ranges.empty() && NewRange.getLower().sle(Ranges.back().getUpper())) {
65 APInt NewLower = Ranges.back().getLower();
66 APInt NewUpper =
67 APIntOps::smax(NewRange.getUpper(), Ranges.back().getUpper());
68 Ranges.back() = ConstantRange(NewLower, NewUpper);
69 } else {
70 Ranges.push_back(NewRange);
71 }
72 for (auto Iter = ExistingTail.begin(); Iter != ExistingTail.end(); Iter++) {
73 if (Ranges.back().getUpper().slt(Iter->getLower())) {
74 Ranges.push_back(*Iter);
75 } else {
76 APInt NewLower = Ranges.back().getLower();
77 APInt NewUpper =
78 APIntOps::smax(Iter->getUpper(), Ranges.back().getUpper());
79 Ranges.back() = ConstantRange(NewLower, NewUpper);
80 }
81 }
82}
83
85 if (SubRange.isEmptySet() || empty())
86 return;
87 assert(!SubRange.isFullSet() && "Do not support full set");
88 assert(SubRange.getLower().slt(SubRange.getUpper()));
89 assert(getBitWidth() == SubRange.getBitWidth());
90 // Handle common cases.
91 if (Ranges.back().getUpper().sle(SubRange.getLower()))
92 return;
93 if (SubRange.getUpper().sle(Ranges.front().getLower()))
94 return;
95
97 auto AppendRangeIfNonEmpty = [&Result](APInt Start, APInt End) {
98 if (Start.slt(End))
99 Result.push_back(ConstantRange(Start, End));
100 };
101 for (auto &Range : Ranges) {
102 if (SubRange.getUpper().sle(Range.getLower()) ||
103 Range.getUpper().sle(SubRange.getLower())) {
104 // "Range" and "SubRange" do not overlap.
105 // L---U : Range
106 // L---U : SubRange (Case1)
107 // L---U : SubRange (Case2)
108 Result.push_back(Range);
109 } else if (Range.getLower().sle(SubRange.getLower()) &&
110 SubRange.getUpper().sle(Range.getUpper())) {
111 // "Range" contains "SubRange".
112 // L---U : Range
113 // L-U : SubRange
114 // Note that ConstantRange::contains(ConstantRange) checks unsigned,
115 // but we need signed checking here.
116 AppendRangeIfNonEmpty(Range.getLower(), SubRange.getLower());
117 AppendRangeIfNonEmpty(SubRange.getUpper(), Range.getUpper());
118 } else if (SubRange.getLower().sle(Range.getLower()) &&
119 Range.getUpper().sle(SubRange.getUpper())) {
120 // "SubRange" contains "Range".
121 // L-U : Range
122 // L---U : SubRange
123 continue;
124 } else if (Range.getLower().sge(SubRange.getLower()) &&
125 Range.getLower().sle(SubRange.getUpper())) {
126 // "Range" and "SubRange" overlap at the left.
127 // L---U : Range
128 // L---U : SubRange
129 AppendRangeIfNonEmpty(SubRange.getUpper(), Range.getUpper());
130 } else {
131 // "Range" and "SubRange" overlap at the right.
132 // L---U : Range
133 // L---U : SubRange
134 assert(SubRange.getLower().sge(Range.getLower()) &&
135 SubRange.getLower().sle(Range.getUpper()));
136 AppendRangeIfNonEmpty(Range.getLower(), SubRange.getLower());
137 }
138 }
139
140 Ranges = Result;
141}
142
145 assert(getBitWidth() == CRL.getBitWidth() &&
146 "ConstantRangeList bitwidths don't agree!");
147 // Handle common cases.
148 if (empty())
149 return CRL;
150 if (CRL.empty())
151 return *this;
152
153 ConstantRangeList Result;
154 size_t i = 0, j = 0;
155 // "PreviousRange" tracks the lowest unioned range that is being processed.
156 // Its lower is fixed and the upper may be updated over iterations.
157 ConstantRange PreviousRange(getBitWidth(), false);
158 if (Ranges[i].getLower().slt(CRL.Ranges[j].getLower())) {
159 PreviousRange = Ranges[i++];
160 } else {
161 PreviousRange = CRL.Ranges[j++];
162 }
163
164 // Try to union "PreviousRange" and "CR". If they are disjoint, push
165 // "PreviousRange" to the result and assign it to "CR", a new union range.
166 // Otherwise, update the upper of "PreviousRange" to cover "CR". Note that,
167 // the lower of "PreviousRange" is always less or equal the lower of "CR".
168 auto UnionAndUpdateRange = [&PreviousRange,
169 &Result](const ConstantRange &CR) {
170 if (PreviousRange.getUpper().slt(CR.getLower())) {
171 Result.Ranges.push_back(PreviousRange);
172 PreviousRange = CR;
173 } else {
174 PreviousRange = ConstantRange(
175 PreviousRange.getLower(),
176 APIntOps::smax(PreviousRange.getUpper(), CR.getUpper()));
177 }
178 };
179 while (i < size() || j < CRL.size()) {
180 if (j == CRL.size() ||
181 (i < size() && Ranges[i].getLower().slt(CRL.Ranges[j].getLower()))) {
182 // Merge PreviousRange with this.
183 UnionAndUpdateRange(Ranges[i++]);
184 } else {
185 // Merge PreviousRange with CRL.
186 UnionAndUpdateRange(CRL.Ranges[j++]);
187 }
188 }
189 Result.Ranges.push_back(PreviousRange);
190 return Result;
191}
192
195 assert(getBitWidth() == CRL.getBitWidth() &&
196 "ConstantRangeList bitwidths don't agree!");
197
198 // Handle common cases.
199 if (empty())
200 return *this;
201 if (CRL.empty())
202 return CRL;
203
204 ConstantRangeList Result;
205 size_t i = 0, j = 0;
206 while (i < size() && j < CRL.size()) {
207 auto &Range = this->Ranges[i];
208 auto &OtherRange = CRL.Ranges[j];
209
210 // The intersection of two Ranges is (max(lowers), min(uppers)), and it's
211 // possible that max(lowers) > min(uppers) if they don't have intersection.
212 // Add the intersection to result only if it's non-empty.
213 // To keep simple, we don't call ConstantRange::intersectWith() as it
214 // considers the complex upper wrapped case and may result two ranges,
215 // like (2, 8) && (6, 4) = {(2, 4), (6, 8)}.
216 APInt Start = APIntOps::smax(Range.getLower(), OtherRange.getLower());
217 APInt End = APIntOps::smin(Range.getUpper(), OtherRange.getUpper());
218 if (Start.slt(End))
219 Result.Ranges.push_back(ConstantRange(Start, End));
220
221 // Move to the next Range in one list determined by the uppers.
222 // For example: A = {(0, 2), (4, 8)}; B = {(-2, 5), (6, 10)}
223 // We need to intersect three pairs: A0 && B0; A1 && B0; A1 && B1.
224 if (Range.getUpper().slt(OtherRange.getUpper()))
225 i++;
226 else
227 j++;
228 }
229 return Result;
230}
231
233 interleaveComma(Ranges, OS, [&](ConstantRange CR) {
234 OS << "(" << CR.getLower() << ", " << CR.getUpper() << ")";
235 });
236}
237
238#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
240 print(dbgs());
241 dbgs() << '\n';
242}
243#endif
#define LLVM_DUMP_METHOD
Mark debug helper function definitions like dump() that should not be stripped from debug builds.
Definition: Compiler.h:537
bool End
Definition: ELF_riscv.cpp:480
ConstantRange Range(APInt(BitWidth, Low), APInt(BitWidth, High))
assert(ImpDefSCC.getReg()==AMDGPU::SCC &&ImpDefSCC.isDef())
raw_pwrite_stream & OS
Class for arbitrary precision integers.
Definition: APInt.h:78
bool sle(const APInt &RHS) const
Signed less or equal comparison.
Definition: APInt.h:1146
bool slt(const APInt &RHS) const
Signed less than comparison.
Definition: APInt.h:1110
bool sge(const APInt &RHS) const
Signed greater or equal comparison.
Definition: APInt.h:1217
ArrayRef - Represent a constant reference to an array (0 or more elements consecutively in memory),...
Definition: ArrayRef.h:41
size_t size() const
size - Get the array size.
Definition: ArrayRef.h:165
bool empty() const
empty - Check if the array is empty.
Definition: ArrayRef.h:160
This class represents a list of constant ranges.
void subtract(const ConstantRange &SubRange)
uint32_t getBitWidth() const
Get the bit width of this ConstantRangeList.
void insert(const ConstantRange &NewRange)
Insert a new range to Ranges and keep the list ordered.
bool empty() const
Return true if this list contains no members.
void print(raw_ostream &OS) const
Print out the ranges to a stream.
static std::optional< ConstantRangeList > getConstantRangeList(ArrayRef< ConstantRange > RangesRef)
size_t size() const
Return the number of ranges in this ConstantRangeList.
ConstantRangeList intersectWith(const ConstantRangeList &CRL) const
Return the range list that results from the intersection of this ConstantRangeList with another Const...
ConstantRangeList unionWith(const ConstantRangeList &CRL) const
Return the range list that results from the union of this ConstantRangeList with another ConstantRang...
static bool isOrderedRanges(ArrayRef< ConstantRange > RangesRef)
This class represents a range of values.
Definition: ConstantRange.h:47
const APInt & getLower() const
Return the lower value for this range.
bool isFullSet() const
Return true if this set contains all of the elements possible for this data-type.
bool isEmptySet() const
Return true if this set contains no members.
const APInt & getUpper() const
Return the upper value for this range.
uint32_t getBitWidth() const
Get the bit width of this ConstantRange.
This is a 'vector' (really, a variable-sized array), optimized for the case when the array is small.
Definition: SmallVector.h:1210
This class implements an extremely fast bulk output stream that can only output to a stream.
Definition: raw_ostream.h:52
const APInt & smin(const APInt &A, const APInt &B)
Determine the smaller of two APInts considered to be signed.
Definition: APInt.h:2197
const APInt & smax(const APInt &A, const APInt &B)
Determine the larger of two APInts considered to be signed.
Definition: APInt.h:2202
This is an optimization pass for GlobalISel generic memory operations.
Definition: AddressRanges.h:18
void interleaveComma(const Container &c, StreamT &os, UnaryFunctor each_fn)
Definition: STLExtras.h:2165
raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
Definition: Debug.cpp:163
auto lower_bound(R &&Range, T &&Value)
Provide wrappers to std::lower_bound which take ranges instead of having to pass begin/end explicitly...
Definition: STLExtras.h:1954