llvm/unittests/IR/ConstantRangeListTest.cpp

   1 //===- ConstantRangeListTest.cpp - ConstantRangeList tests ----------------===//
   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 "gtest/gtest.h"
  11
  12 using namespace llvm;
  13
  14 namespace {
  15
  16 using ConstantRangeListTest = ::testing::Test;
  17
  18 TEST_F(ConstantRangeListTest, Basics) {
  19   ConstantRangeList CRL1a;
  20   CRL1a.insert(0, 12);
  21   EXPECT_FALSE(CRL1a.empty());
  22
  23   ConstantRangeList CRL1b;
  24   CRL1b.insert(0, 4);
  25   CRL1b.insert(4, 8);
  26   CRL1b.insert(8, 12);
  27   EXPECT_TRUE(CRL1a == CRL1b);
  28
  29   ConstantRangeList CRL1c;
  30   CRL1c.insert(0, 4);
  31   CRL1c.insert(8, 12);
  32   CRL1c.insert(4, 8);
  33   EXPECT_TRUE(CRL1a == CRL1c);
  34
  35   ConstantRangeList CRL2;
  36   CRL2.insert(-4, 0);
  37   CRL2.insert(8, 12);
  38   EXPECT_TRUE(CRL1a != CRL2);
  39 }
  40
  41 TEST_F(ConstantRangeListTest, getConstantRangeList) {
  42   SmallVector<ConstantRange, 2> Empty;
  43   EXPECT_TRUE(ConstantRangeList::getConstantRangeList(Empty).has_value());
  44
  45   SmallVector<ConstantRange, 2> Valid;
  46   Valid.push_back(ConstantRange(APInt(64, 0, true), APInt(64, 4, true)));
  47   Valid.push_back(ConstantRange(APInt(64, 8, true), APInt(64, 12, true)));
  48   EXPECT_TRUE(ConstantRangeList::getConstantRangeList(Valid).has_value());
  49
  50   SmallVector<ConstantRange, 2> Invalid1;
  51   Invalid1.push_back(ConstantRange(APInt(64, 4, true), APInt(64, 0, true)));
  52   EXPECT_EQ(ConstantRangeList::getConstantRangeList(Invalid1), std::nullopt);
  53
  54   SmallVector<ConstantRange, 2> Invalid2;
  55   Invalid2.push_back(ConstantRange(APInt(64, 0, true), APInt(64, 4, true)));
  56   Invalid2.push_back(ConstantRange(APInt(64, 12, true), APInt(64, 8, true)));
  57   EXPECT_EQ(ConstantRangeList::getConstantRangeList(Invalid2), std::nullopt);
  58
  59   SmallVector<ConstantRange, 2> Invalid3;
  60   Invalid3.push_back(ConstantRange(APInt(64, 0, true), APInt(64, 4, true)));
  61   Invalid3.push_back(ConstantRange(APInt(64, 4, true), APInt(64, 8, true)));
  62   EXPECT_EQ(ConstantRangeList::getConstantRangeList(Invalid3), std::nullopt);
  63
  64   SmallVector<ConstantRange, 2> Invalid4;
  65   Invalid4.push_back(ConstantRange(APInt(64, 0, true), APInt(64, 12, true)));
  66   Invalid4.push_back(ConstantRange(APInt(64, 8, true), APInt(64, 16, true)));
  67   EXPECT_EQ(ConstantRangeList::getConstantRangeList(Invalid4), std::nullopt);
  68 }
  69
  70 TEST_F(ConstantRangeListTest, Insert) {
  71   ConstantRangeList CRL;
  72   CRL.insert(0, 4);
  73   CRL.insert(8, 12);
  74   // No overlap, left
  75   CRL.insert(-8, -4);
  76   // No overlap, right
  77   CRL.insert(16, 20);
  78   // No overlap, middle
  79   CRL.insert(13, 15);
  80   // Overlap with left
  81   CRL.insert(-6, -2);
  82   // Overlap with right
  83   CRL.insert(5, 9);
  84   // Overlap with left and right
  85   CRL.insert(14, 18);
  86   // Overlap cross ranges
  87   CRL.insert(2, 14);
  88   // An existing range
  89   CRL.insert(0, 20);
  90
  91   ConstantRangeList Expected;
  92   Expected.insert(-8, -2);
  93   Expected.insert(0, 20);
  94   EXPECT_TRUE(CRL == Expected);
  95 }
  96
  97 ConstantRangeList GetCRL(ArrayRef<std::pair<APInt, APInt>> Pairs) {
  98   SmallVector<ConstantRange, 2> Ranges;
  99   for (auto &[Start, End] : Pairs)
 100     Ranges.push_back(ConstantRange(Start, End));
 101   return ConstantRangeList(Ranges);
 102 }
 103
 104 TEST_F(ConstantRangeListTest, Subtract) {
 105   APInt AP0 = APInt(64, 0, /*isSigned=*/true);
 106   APInt AP2 = APInt(64, 2, /*isSigned=*/true);
 107   APInt AP3 = APInt(64, 3, /*isSigned=*/true);
 108   APInt AP4 = APInt(64, 4, /*isSigned=*/true);
 109   APInt AP8 = APInt(64, 8, /*isSigned=*/true);
 110   APInt AP10 = APInt(64, 10, /*isSigned=*/true);
 111   APInt AP11 = APInt(64, 11, /*isSigned=*/true);
 112   APInt AP12 = APInt(64, 12, /*isSigned=*/true);
 113   ConstantRangeList CRL = GetCRL({{AP0, AP4}, {AP8, AP12}});
 114
 115   // Execute ConstantRangeList::subtract(ConstantRange) and check the result
 116   // is expected. Pass "CRL" by value so that subtract() does not affect the
 117   // argument in caller.
 118   auto SubtractAndCheck = [](ConstantRangeList CRL,
 119                              const std::pair<int64_t, int64_t> &Range,
 120                              const ConstantRangeList &ExpectedCRL) {
 121     CRL.subtract(ConstantRange(APInt(64, Range.first, /*isSigned=*/true),
 122                                APInt(64, Range.second, /*isSigned=*/true)));
 123     EXPECT_EQ(CRL, ExpectedCRL);
 124   };
 125
 126   // No overlap
 127   SubtractAndCheck(CRL, {-4, 0}, CRL);
 128   SubtractAndCheck(CRL, {4, 8}, CRL);
 129   SubtractAndCheck(CRL, {12, 16}, CRL);
 130
 131   // Overlap (left, right, or both)
 132   SubtractAndCheck(CRL, {-4, 2}, GetCRL({{AP2, AP4}, {AP8, AP12}}));
 133   SubtractAndCheck(CRL, {-4, 4}, GetCRL({{AP8, AP12}}));
 134   SubtractAndCheck(CRL, {-4, 8}, GetCRL({{AP8, AP12}}));
 135   SubtractAndCheck(CRL, {0, 2}, GetCRL({{AP2, AP4}, {AP8, AP12}}));
 136   SubtractAndCheck(CRL, {0, 4}, GetCRL({{AP8, AP12}}));
 137   SubtractAndCheck(CRL, {0, 8}, GetCRL({{AP8, AP12}}));
 138   SubtractAndCheck(CRL, {10, 12}, GetCRL({{AP0, AP4}, {AP8, AP10}}));
 139   SubtractAndCheck(CRL, {8, 12}, GetCRL({{AP0, AP4}}));
 140   SubtractAndCheck(CRL, {6, 12}, GetCRL({{AP0, AP4}}));
 141   SubtractAndCheck(CRL, {10, 16}, GetCRL({{AP0, AP4}, {AP8, AP10}}));
 142   SubtractAndCheck(CRL, {8, 16}, GetCRL({{AP0, AP4}}));
 143   SubtractAndCheck(CRL, {6, 16}, GetCRL({{AP0, AP4}}));
 144   SubtractAndCheck(CRL, {2, 10}, GetCRL({{AP0, AP2}, {AP10, AP12}}));
 145
 146   // Subset
 147   SubtractAndCheck(CRL, {2, 3}, GetCRL({{AP0, AP2}, {AP3, AP4}, {AP8, AP12}}));
 148   SubtractAndCheck(CRL, {10, 11},
 149                    GetCRL({{AP0, AP4}, {AP8, AP10}, {AP11, AP12}}));
 150
 151   // Superset
 152   SubtractAndCheck(CRL, {0, 12}, GetCRL({}));
 153   SubtractAndCheck(CRL, {-4, 16}, GetCRL({}));
 154 }
 155
 156 TEST_F(ConstantRangeListTest, Union) {
 157   APInt APN4 = APInt(64, -4, /*isSigned=*/true);
 158   APInt APN2 = APInt(64, -2, /*isSigned=*/true);
 159   APInt AP0 = APInt(64, 0, /*isSigned=*/true);
 160   APInt AP2 = APInt(64, 2, /*isSigned=*/true);
 161   APInt AP4 = APInt(64, 4, /*isSigned=*/true);
 162   APInt AP6 = APInt(64, 6, /*isSigned=*/true);
 163   APInt AP7 = APInt(64, 7, /*isSigned=*/true);
 164   APInt AP8 = APInt(64, 8, /*isSigned=*/true);
 165   APInt AP10 = APInt(64, 10, /*isSigned=*/true);
 166   APInt AP11 = APInt(64, 11, /*isSigned=*/true);
 167   APInt AP12 = APInt(64, 12, /*isSigned=*/true);
 168   APInt AP16 = APInt(64, 16, /*isSigned=*/true);
 169   APInt AP18 = APInt(64, 18, /*isSigned=*/true);
 170   ConstantRangeList CRL = GetCRL({{AP0, AP4}, {AP8, AP12}});
 171
 172   // Union with a subset.
 173   ConstantRangeList Empty;
 174   EXPECT_EQ(CRL.unionWith(Empty), CRL);
 175   EXPECT_EQ(Empty.unionWith(CRL), CRL);
 176
 177   EXPECT_EQ(CRL.unionWith(GetCRL({{AP0, AP2}})), CRL);
 178   EXPECT_EQ(CRL.unionWith(GetCRL({{AP10, AP12}})), CRL);
 179
 180   EXPECT_EQ(CRL.unionWith(GetCRL({{AP0, AP2}, {AP8, AP10}})), CRL);
 181   EXPECT_EQ(CRL.unionWith(GetCRL({{AP0, AP2}, {AP10, AP12}})), CRL);
 182   EXPECT_EQ(CRL.unionWith(GetCRL({{AP2, AP4}, {AP8, AP10}})), CRL);
 183   EXPECT_EQ(CRL.unionWith(GetCRL({{AP2, AP4}, {AP10, AP12}})), CRL);
 184
 185   EXPECT_EQ(CRL.unionWith(GetCRL({{AP0, AP4}, {AP8, AP10}, {AP11, AP12}})),
 186             CRL);
 187
 188   EXPECT_EQ(CRL.unionWith(CRL), CRL);
 189
 190   // Union with new ranges.
 191   EXPECT_EQ(CRL.unionWith(GetCRL({{APN4, APN2}})),
 192             GetCRL({{APN4, APN2}, {AP0, AP4}, {AP8, AP12}}));
 193   EXPECT_EQ(CRL.unionWith(GetCRL({{AP6, AP7}})),
 194             GetCRL({{AP0, AP4}, {AP6, AP7}, {AP8, AP12}}));
 195   EXPECT_EQ(CRL.unionWith(GetCRL({{AP16, AP18}})),
 196             GetCRL({{AP0, AP4}, {AP8, AP12}, {AP16, AP18}}));
 197
 198   EXPECT_EQ(CRL.unionWith(GetCRL({{APN2, AP2}})),
 199             GetCRL({{APN2, AP4}, {AP8, AP12}}));
 200   EXPECT_EQ(CRL.unionWith(GetCRL({{AP2, AP6}})),
 201             GetCRL({{AP0, AP6}, {AP8, AP12}}));
 202   EXPECT_EQ(CRL.unionWith(GetCRL({{AP10, AP16}})),
 203             GetCRL({{AP0, AP4}, {AP8, AP16}}));
 204
 205   EXPECT_EQ(CRL.unionWith(GetCRL({{APN2, AP10}})), GetCRL({{APN2, AP12}}));
 206   EXPECT_EQ(CRL.unionWith(GetCRL({{AP2, AP10}})), GetCRL({{AP0, AP12}}));
 207   EXPECT_EQ(CRL.unionWith(GetCRL({{AP4, AP16}})), GetCRL({{AP0, AP16}}));
 208   EXPECT_EQ(CRL.unionWith(GetCRL({{APN2, AP16}})), GetCRL({{APN2, AP16}}));
 209 }
 210
 211 TEST_F(ConstantRangeListTest, Intersect) {
 212   APInt APN2 = APInt(64, -2, /*isSigned=*/true);
 213   APInt AP0 = APInt(64, 0, /*isSigned=*/true);
 214   APInt AP2 = APInt(64, 2, /*isSigned=*/true);
 215   APInt AP4 = APInt(64, 4, /*isSigned=*/true);
 216   APInt AP6 = APInt(64, 6, /*isSigned=*/true);
 217   APInt AP7 = APInt(64, 7, /*isSigned=*/true);
 218   APInt AP8 = APInt(64, 8, /*isSigned=*/true);
 219   APInt AP10 = APInt(64, 10, /*isSigned=*/true);
 220   APInt AP11 = APInt(64, 11, /*isSigned=*/true);
 221   APInt AP12 = APInt(64, 12, /*isSigned=*/true);
 222   APInt AP16 = APInt(64, 16, /*isSigned=*/true);
 223   ConstantRangeList CRL = GetCRL({{AP0, AP4}, {AP8, AP12}});
 224
 225   // No intersection.
 226   ConstantRangeList Empty;
 227   EXPECT_EQ(CRL.intersectWith(Empty), Empty);
 228   EXPECT_EQ(Empty.intersectWith(CRL), Empty);
 229
 230   EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP0}})), Empty);
 231   EXPECT_EQ(CRL.intersectWith(GetCRL({{AP6, AP8}})), Empty);
 232   EXPECT_EQ(CRL.intersectWith(GetCRL({{AP12, AP16}})), Empty);
 233
 234   // Single intersect range.
 235   EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP2}})), GetCRL({{AP0, AP2}}));
 236   EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP6}})), GetCRL({{AP0, AP4}}));
 237   EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP4}})), GetCRL({{AP2, AP4}}));
 238   EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP6}})), GetCRL({{AP2, AP4}}));
 239   EXPECT_EQ(CRL.intersectWith(GetCRL({{AP6, AP10}})), GetCRL({{AP8, AP10}}));
 240   EXPECT_EQ(CRL.intersectWith(GetCRL({{AP6, AP16}})), GetCRL({{AP8, AP12}}));
 241   EXPECT_EQ(CRL.intersectWith(GetCRL({{AP10, AP12}})), GetCRL({{AP10, AP12}}));
 242   EXPECT_EQ(CRL.intersectWith(GetCRL({{AP10, AP16}})), GetCRL({{AP10, AP12}}));
 243
 244   // Multiple intersect ranges.
 245   EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP10}})),
 246             GetCRL({{AP0, AP4}, {AP8, AP10}}));
 247   EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP16}})), CRL);
 248   EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP10}})),
 249             GetCRL({{AP2, AP4}, {AP8, AP10}}));
 250   EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP16}})),
 251             GetCRL({{AP2, AP4}, {AP8, AP12}}));
 252   EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP2}, {AP6, AP10}})),
 253             GetCRL({{AP0, AP2}, {AP8, AP10}}));
 254   EXPECT_EQ(CRL.intersectWith(GetCRL({{AP2, AP6}, {AP10, AP16}})),
 255             GetCRL({{AP2, AP4}, {AP10, AP12}}));
 256   EXPECT_EQ(CRL.intersectWith(GetCRL({{APN2, AP2}, {AP7, AP10}, {AP11, AP16}})),
 257             GetCRL({{AP0, AP2}, {AP8, AP10}, {AP11, AP12}}));
 258   EXPECT_EQ(CRL.intersectWith(CRL), CRL);
 259 }
 260
 261 } // anonymous namespace