xref: /llvm-project/llvm/lib/IR/ConstantRangeList.cpp (revision 4028bb10c3a396023b877d025c5776d207f29f91) 
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 
12 using namespace llvm;
13 
14 bool ConstantRangeList::isOrderedRanges(ArrayRef<ConstantRange> RangesRef) {
15   if (RangesRef.empty())
16     return true;
17   auto Range = RangesRef[0];
18   if (Range.getLower().sge(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(CurRange.getUpper()) ||
24         CurRange.getLower().sle(PreRange.getUpper()))
25       return false;
26   }
27   return true;
28 }
29 
30 std::optional<ConstantRangeList>
31 ConstantRangeList::getConstantRangeList(ArrayRef<ConstantRange> RangesRef) {
32   if (!isOrderedRanges(RangesRef))
33     return std::nullopt;
34   return ConstantRangeList(RangesRef);
35 }
36 
37 void 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(NewRange.getLower())) {
44     Ranges.push_back(NewRange);
45     return;
46   }
47 
48   assert(getBitWidth() == NewRange.getBitWidth());
49 
50   if (NewRange.getUpper().slt(Ranges.front().getLower())) {
51     Ranges.insert(Ranges.begin(), NewRange);
52     return;
53   }
54 
55   auto LowerBound = lower_bound(
56       Ranges, NewRange, [](const ConstantRange &a, const ConstantRange &b) {
57         return a.getLower().slt(b.getLower());
58       });
59   if (LowerBound != Ranges.end() && LowerBound->contains(NewRange))
60     return;
61 
62   // Slow insert.
63   SmallVector<ConstantRange, 2> ExistingTail(LowerBound, Ranges.end());
64   Ranges.erase(LowerBound, Ranges.end());
65   // Merge consecutive ranges.
66   if (!Ranges.empty() && NewRange.getLower().sle(Ranges.back().getUpper())) {
67     APInt NewLower = Ranges.back().getLower();
68     APInt NewUpper =
69         APIntOps::smax(NewRange.getUpper(), Ranges.back().getUpper());
70     Ranges.back() = ConstantRange(NewLower, NewUpper);
71   } else {
72     Ranges.push_back(NewRange);
73   }
74   for (auto Iter = ExistingTail.begin(); Iter != ExistingTail.end(); Iter++) {
75     if (Ranges.back().getUpper().slt(Iter->getLower())) {
76       Ranges.push_back(*Iter);
77     } else {
78       APInt NewLower = Ranges.back().getLower();
79       APInt NewUpper =
80           APIntOps::smax(Iter->getUpper(), Ranges.back().getUpper());
81       Ranges.back() = ConstantRange(NewLower, NewUpper);
82     }
83   }
84 }
85 
86 void 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(SubRange.getLower()))
94     return;
95   if (SubRange.getUpper().sle(Ranges.front().getLower()))
96     return;
97 
98   SmallVector<ConstantRange, 2> Result;
99   auto AppendRangeIfNonEmpty = [&Result](APInt Start, APInt End) {
100     if (Start.slt(End))
101       Result.push_back(ConstantRange(Start, End));
102   };
103   for (auto &Range : Ranges) {
104     if (SubRange.getUpper().sle(Range.getLower()) ||
105         Range.getUpper().sle(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(Range);
111     } else if (Range.getLower().sle(SubRange.getLower()) &&
112                SubRange.getUpper().sle(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(Range.getLower()) &&
121                Range.getUpper().sle(SubRange.getUpper())) {
122       // "SubRange" contains "Range".
123       //        L-U        : Range
124       //       L---U       : SubRange
125       continue;
126     } else if (Range.getLower().sge(SubRange.getLower()) &&
127                Range.getLower().sle(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 
145 ConstantRangeList
146 ConstantRangeList::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(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(CR.getLower())) {
174       Result.Ranges.push_back(PreviousRange);
175       PreviousRange = CR;
176     } else {
177       PreviousRange = ConstantRange(
178           PreviousRange.getLower(),
179           APIntOps::smax(PreviousRange.getUpper(), CR.getUpper()));
180     }
181   };
182   while (i < size() || j < CRL.size()) {
183     if (j == CRL.size() ||
184         (i < size() && Ranges[i].getLower().slt(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(PreviousRange);
193   return Result;
194 }
195 
196 ConstantRangeList
197 ConstantRangeList::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(Range.getLower(), OtherRange.getLower());
220     APInt End = APIntOps::smin(Range.getUpper(), OtherRange.getUpper());
221     if (Start.slt(End))
222       Result.Ranges.push_back(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(OtherRange.getUpper()))
228       i++;
229     else
230       j++;
231   }
232   return Result;
233 }
234 
235 void ConstantRangeList::print(raw_ostream &OS) const {
236   interleaveComma(Ranges, OS, [&](ConstantRange CR) {
237     OS << "(" << CR.getLower() << ", " << CR.getUpper() << ")";
238   });
239 }
240 
241 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
242 LLVM_DUMP_METHOD void ConstantRangeList::dump() const {
243   print(dbgs());
244   dbgs() << '\n';
245 }
246 #endif
247