llvm/lib/IR/ConstantRangeList.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-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