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
9#include "llvm/IR/ConstantRangeList.h"
10#include <cstddef>
11
12using namespace llvm;
13
14bool ConstantRangeList::isOrderedRanges(ArrayRef<ConstantRange> RangesRef) {
15 if (RangesRef.empty())
16 return true;
17 auto Range = RangesRef[0];
18 if (Range.getLower().sge(RHS: Range.getUpper()))
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(RHS: CurRange.getUpper()) ||
24 CurRange.getLower().sle(RHS: PreRange.getUpper()))
25 return false;
26 }
27 return true;
28}
29
30std::optional<ConstantRangeList>
31ConstantRangeList::getConstantRangeList(ArrayRef<ConstantRange> RangesRef) {
32 if (!isOrderedRanges(RangesRef))
33 return std::nullopt;
34 return ConstantRangeList(RangesRef);
35}
36
37void ConstantRangeList::insert(const ConstantRange &NewRange) {
38 if (NewRange.isEmptySet())
39 return;
40 assert(!NewRange.isFullSet() && "Do not support full set");
41 assert(NewRange.getLower().slt(NewRange.getUpper()));
42 // Handle common cases.
43 if (empty() || Ranges.back().getUpper().slt(RHS: NewRange.getLower())) {
44 Ranges.push_back(Elt: NewRange);
45 return;
46 }
47
48 assert(getBitWidth() == NewRange.getBitWidth());
49
50 if (NewRange.getUpper().slt(RHS: Ranges.front().getLower())) {
51 Ranges.insert(I: Ranges.begin(), Elt: NewRange);
52 return;
53 }
54
55 auto LowerBound = lower_bound(
56 Range&: Ranges, Value: NewRange, C: [](const ConstantRange &a, const ConstantRange &b) {
57 return a.getLower().slt(RHS: b.getLower());
58 });
59 if (LowerBound != Ranges.end() && LowerBound->contains(CR: NewRange))
60 return;
61
62 // Slow insert.
63 SmallVector<ConstantRange, 2> ExistingTail(LowerBound, Ranges.end());
64 Ranges.erase(CS: LowerBound, CE: Ranges.end());
65 // Merge consecutive ranges.
66 if (!Ranges.empty() && NewRange.getLower().sle(RHS: Ranges.back().getUpper())) {
67 APInt NewLower = Ranges.back().getLower();
68 APInt NewUpper =
69 APIntOps::smax(A: NewRange.getUpper(), B: Ranges.back().getUpper());
70 Ranges.back() = ConstantRange(NewLower, NewUpper);
71 } else {
72 Ranges.push_back(Elt: NewRange);
73 }
74 for (auto Iter = ExistingTail.begin(); Iter != ExistingTail.end(); Iter++) {
75 if (Ranges.back().getUpper().slt(RHS: Iter->getLower())) {
76 Ranges.push_back(Elt: *Iter);
77 } else {
78 APInt NewLower = Ranges.back().getLower();
79 APInt NewUpper =
80 APIntOps::smax(A: Iter->getUpper(), B: Ranges.back().getUpper());
81 Ranges.back() = ConstantRange(NewLower, NewUpper);
82 }
83 }
84}
85
86void ConstantRangeList::subtract(const ConstantRange &SubRange) {
87 if (SubRange.isEmptySet() || empty())
88 return;
89 assert(!SubRange.isFullSet() && "Do not support full set");
90 assert(SubRange.getLower().slt(SubRange.getUpper()));
91 assert(getBitWidth() == SubRange.getBitWidth());
92 // Handle common cases.
93 if (Ranges.back().getUpper().sle(RHS: SubRange.getLower()))
94 return;
95 if (SubRange.getUpper().sle(RHS: Ranges.front().getLower()))
96 return;
97
98 SmallVector<ConstantRange, 2> Result;
99 auto AppendRangeIfNonEmpty = [&Result](APInt Start, APInt End) {
100 if (Start.slt(RHS: End))
101 Result.push_back(Elt: ConstantRange(Start, End));
102 };
103 for (auto &Range : Ranges) {
104 if (SubRange.getUpper().sle(RHS: Range.getLower()) ||
105 Range.getUpper().sle(RHS: SubRange.getLower())) {
106 // "Range" and "SubRange" do not overlap.
107 // L---U : Range
108 // L---U : SubRange (Case1)
109 // L---U : SubRange (Case2)
110 Result.push_back(Elt: Range);
111 } else if (Range.getLower().sle(RHS: SubRange.getLower()) &&
112 SubRange.getUpper().sle(RHS: Range.getUpper())) {
113 // "Range" contains "SubRange".
114 // L---U : Range
115 // L-U : SubRange
116 // Note that ConstantRange::contains(ConstantRange) checks unsigned,
117 // but we need signed checking here.
118 AppendRangeIfNonEmpty(Range.getLower(), SubRange.getLower());
119 AppendRangeIfNonEmpty(SubRange.getUpper(), Range.getUpper());
120 } else if (SubRange.getLower().sle(RHS: Range.getLower()) &&
121 Range.getUpper().sle(RHS: SubRange.getUpper())) {
122 // "SubRange" contains "Range".
123 // L-U : Range
124 // L---U : SubRange
125 continue;
126 } else if (Range.getLower().sge(RHS: SubRange.getLower()) &&
127 Range.getLower().sle(RHS: SubRange.getUpper())) {
128 // "Range" and "SubRange" overlap at the left.
129 // L---U : Range
130 // L---U : SubRange
131 AppendRangeIfNonEmpty(SubRange.getUpper(), Range.getUpper());
132 } else {
133 // "Range" and "SubRange" overlap at the right.
134 // L---U : Range
135 // L---U : SubRange
136 assert(SubRange.getLower().sge(Range.getLower()) &&
137 SubRange.getLower().sle(Range.getUpper()));
138 AppendRangeIfNonEmpty(Range.getLower(), SubRange.getLower());
139 }
140 }
141
142 Ranges = Result;
143}
144
145ConstantRangeList
146ConstantRangeList::unionWith(const ConstantRangeList &CRL) const {
147 // Handle common cases.
148 if (empty())
149 return CRL;
150 if (CRL.empty())
151 return *this;
152
153 assert(getBitWidth() == CRL.getBitWidth() &&
154 "ConstantRangeList bitwidths don't agree!");
155
156 ConstantRangeList Result;
157 size_t i = 0, j = 0;
158 // "PreviousRange" tracks the lowest unioned range that is being processed.
159 // Its lower is fixed and the upper may be updated over iterations.
160 ConstantRange PreviousRange(getBitWidth(), false);
161 if (Ranges[i].getLower().slt(RHS: CRL.Ranges[j].getLower())) {
162 PreviousRange = Ranges[i++];
163 } else {
164 PreviousRange = CRL.Ranges[j++];
165 }
166
167 // Try to union "PreviousRange" and "CR". If they are disjoint, push
168 // "PreviousRange" to the result and assign it to "CR", a new union range.
169 // Otherwise, update the upper of "PreviousRange" to cover "CR". Note that,
170 // the lower of "PreviousRange" is always less or equal the lower of "CR".
171 auto UnionAndUpdateRange = [&PreviousRange,
172 &Result](const ConstantRange &CR) {
173 if (PreviousRange.getUpper().slt(RHS: CR.getLower())) {
174 Result.Ranges.push_back(Elt: PreviousRange);
175 PreviousRange = CR;
176 } else {
177 PreviousRange = ConstantRange(
178 PreviousRange.getLower(),
179 APIntOps::smax(A: PreviousRange.getUpper(), B: CR.getUpper()));
180 }
181 };
182 while (i < size() || j < CRL.size()) {
183 if (j == CRL.size() ||
184 (i < size() && Ranges[i].getLower().slt(RHS: CRL.Ranges[j].getLower()))) {
185 // Merge PreviousRange with this.
186 UnionAndUpdateRange(Ranges[i++]);
187 } else {
188 // Merge PreviousRange with CRL.
189 UnionAndUpdateRange(CRL.Ranges[j++]);
190 }
191 }
192 Result.Ranges.push_back(Elt: PreviousRange);
193 return Result;
194}
195
196ConstantRangeList
197ConstantRangeList::intersectWith(const ConstantRangeList &CRL) const {
198 // Handle common cases.
199 if (empty())
200 return *this;
201 if (CRL.empty())
202 return CRL;
203
204 assert(getBitWidth() == CRL.getBitWidth() &&
205 "ConstantRangeList bitwidths don't agree!");
206
207 ConstantRangeList Result;
208 size_t i = 0, j = 0;
209 while (i < size() && j < CRL.size()) {
210 auto &Range = this->Ranges[i];
211 auto &OtherRange = CRL.Ranges[j];
212
213 // The intersection of two Ranges is (max(lowers), min(uppers)), and it's
214 // possible that max(lowers) > min(uppers) if they don't have intersection.
215 // Add the intersection to result only if it's non-empty.
216 // To keep simple, we don't call ConstantRange::intersectWith() as it
217 // considers the complex upper wrapped case and may result two ranges,
218 // like (2, 8) && (6, 4) = {(2, 4), (6, 8)}.
219 APInt Start = APIntOps::smax(A: Range.getLower(), B: OtherRange.getLower());
220 APInt End = APIntOps::smin(A: Range.getUpper(), B: OtherRange.getUpper());
221 if (Start.slt(RHS: End))
222 Result.Ranges.push_back(Elt: ConstantRange(Start, End));
223
224 // Move to the next Range in one list determined by the uppers.
225 // For example: A = {(0, 2), (4, 8)}; B = {(-2, 5), (6, 10)}
226 // We need to intersect three pairs: A0 && B0; A1 && B0; A1 && B1.
227 if (Range.getUpper().slt(RHS: OtherRange.getUpper()))
228 i++;
229 else
230 j++;
231 }
232 return Result;
233}
234
235void ConstantRangeList::print(raw_ostream &OS) const {
236 interleaveComma(c: Ranges, os&: OS, each_fn: [&](ConstantRange CR) {
237 OS << "(" << CR.getLower() << ", " << CR.getUpper() << ")";
238 });
239}
240
241#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
242LLVM_DUMP_METHOD void ConstantRangeList::dump() const {
243 print(dbgs());
244 dbgs() << '\n';
245}
246#endif
247