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 assert(getBitWidth() == NewRange.getBitWidth());
43 // Handle common cases.
44 if (empty() || Ranges.back().getUpper().slt(RHS: NewRange.getLower())) {
45 Ranges.push_back(Elt: NewRange);
46 return;
47 }
48 if (NewRange.getUpper().slt(RHS: Ranges.front().getLower())) {
49 Ranges.insert(I: Ranges.begin(), Elt: NewRange);
50 return;
51 }
52
53 auto LowerBound = lower_bound(
54 Range&: Ranges, Value: NewRange, C: [](const ConstantRange &a, const ConstantRange &b) {
55 return a.getLower().slt(RHS: b.getLower());
56 });
57 if (LowerBound != Ranges.end() && LowerBound->contains(CR: NewRange))
58 return;
59
60 // Slow insert.
61 SmallVector<ConstantRange, 2> ExistingTail(LowerBound, Ranges.end());
62 Ranges.erase(CS: LowerBound, CE: Ranges.end());
63 // Merge consecutive ranges.
64 if (!Ranges.empty() && NewRange.getLower().sle(RHS: Ranges.back().getUpper())) {
65 APInt NewLower = Ranges.back().getLower();
66 APInt NewUpper =
67 APIntOps::smax(A: NewRange.getUpper(), B: Ranges.back().getUpper());
68 Ranges.back() = ConstantRange(NewLower, NewUpper);
69 } else {
70 Ranges.push_back(Elt: NewRange);
71 }
72 for (auto Iter = ExistingTail.begin(); Iter != ExistingTail.end(); Iter++) {
73 if (Ranges.back().getUpper().slt(RHS: Iter->getLower())) {
74 Ranges.push_back(Elt: *Iter);
75 } else {
76 APInt NewLower = Ranges.back().getLower();
77 APInt NewUpper =
78 APIntOps::smax(A: Iter->getUpper(), B: Ranges.back().getUpper());
79 Ranges.back() = ConstantRange(NewLower, NewUpper);
80 }
81 }
82}
83
84void ConstantRangeList::subtract(const ConstantRange &SubRange) {
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(RHS: SubRange.getLower()))
92 return;
93 if (SubRange.getUpper().sle(RHS: Ranges.front().getLower()))
94 return;
95
96 SmallVector<ConstantRange, 2> Result;
97 auto AppendRangeIfNonEmpty = [&Result](APInt Start, APInt End) {
98 if (Start.slt(RHS: End))
99 Result.push_back(Elt: ConstantRange(Start, End));
100 };
101 for (auto &Range : Ranges) {
102 if (SubRange.getUpper().sle(RHS: Range.getLower()) ||
103 Range.getUpper().sle(RHS: 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(Elt: Range);
109 } else if (Range.getLower().sle(RHS: SubRange.getLower()) &&
110 SubRange.getUpper().sle(RHS: 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(RHS: Range.getLower()) &&
119 Range.getUpper().sle(RHS: SubRange.getUpper())) {
120 // "SubRange" contains "Range".
121 // L-U : Range
122 // L---U : SubRange
123 continue;
124 } else if (Range.getLower().sge(RHS: SubRange.getLower()) &&
125 Range.getLower().sle(RHS: 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
143ConstantRangeList
144ConstantRangeList::unionWith(const ConstantRangeList &CRL) const {
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(RHS: 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(RHS: CR.getLower())) {
171 Result.Ranges.push_back(Elt: PreviousRange);
172 PreviousRange = CR;
173 } else {
174 PreviousRange = ConstantRange(
175 PreviousRange.getLower(),
176 APIntOps::smax(A: PreviousRange.getUpper(), B: CR.getUpper()));
177 }
178 };
179 while (i < size() || j < CRL.size()) {
180 if (j == CRL.size() ||
181 (i < size() && Ranges[i].getLower().slt(RHS: 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(Elt: PreviousRange);
190 return Result;
191}
192
193ConstantRangeList
194ConstantRangeList::intersectWith(const ConstantRangeList &CRL) const {
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(A: Range.getLower(), B: OtherRange.getLower());
217 APInt End = APIntOps::smin(A: Range.getUpper(), B: OtherRange.getUpper());
218 if (Start.slt(RHS: End))
219 Result.Ranges.push_back(Elt: 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(RHS: OtherRange.getUpper()))
225 i++;
226 else
227 j++;
228 }
229 return Result;
230}
231
232void ConstantRangeList::print(raw_ostream &OS) const {
233 interleaveComma(c: Ranges, os&: OS, each_fn: [&](ConstantRange CR) {
234 OS << "(" << CR.getLower() << ", " << CR.getUpper() << ")";
235 });
236}
237
238#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
239LLVM_DUMP_METHOD void ConstantRangeList::dump() const {
240 print(dbgs());
241 dbgs() << '\n';
242}
243#endif
244