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   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