247 lines · cpp
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-exception6//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(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 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(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 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(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 : Range108 // 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 : Range115 // L-U : SubRange116 // 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 : Range124 // L---U : SubRange125 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 : Range130 // L---U : SubRange131 AppendRangeIfNonEmpty(SubRange.getUpper(), Range.getUpper());132 } else {133 // "Range" and "SubRange" overlap at the right.134 // L---U : Range135 // L---U : SubRange136 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 145ConstantRangeList146ConstantRangeList::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, push168 // "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 196ConstantRangeList197ConstantRangeList::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's214 // 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 it217 // 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 else230 j++;231 }232 return Result;233}234 235void 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)242LLVM_DUMP_METHOD void ConstantRangeList::dump() const {243 print(dbgs());244 dbgs() << '\n';245}246#endif247