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 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 84 void 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(SubRange.getLower())) 92 return; 93 if (SubRange.getUpper().sle(Ranges.front().getLower())) 94 return; 95 96 SmallVector<ConstantRange, 2> Result; 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 143 ConstantRangeList 144 ConstantRangeList::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(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 193 ConstantRangeList 194 ConstantRangeList::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(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 232 void ConstantRangeList::print(raw_ostream &OS) const { 233 interleaveComma(Ranges, OS, [&](ConstantRange CR) { 234 OS << "(" << CR.getLower() << ", " << CR.getUpper() << ")"; 235 }); 236 } 237 238 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 239 LLVM_DUMP_METHOD void ConstantRangeList::dump() const { 240 print(dbgs()); 241 dbgs() << '\n'; 242 } 243 #endif 244