unittests/Support/IntegersSubsetTest.cpp

   1 //===- llvm/unittest/Support/IntegersSubsetTest.cpp - IntegersSubset tests ===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "llvm/ADT/APInt.h"
  11 #include "llvm/Support/IntegersSubset.h"
  12 #include "llvm/Support/IntegersSubsetMapping.h"
  13
  14 #include "gtest/gtest.h"
  15
  16 #include <vector>
  17
  18 using namespace llvm;
  19
  20 namespace {
  21
  22   class Int : public APInt {
  23   public:
  24     Int(uint64_t V) : APInt(64, V) {}
  25     Int(const APInt& Src) : APInt(Src) {}
  26     bool operator < (const APInt& RHS) const { return ult(RHS); }
  27     bool operator > (const APInt& RHS) const { return ugt(RHS); }
  28     bool operator <= (const APInt& RHS) const { return ule(RHS); }
  29     bool operator >= (const APInt& RHS) const { return uge(RHS); }
  30   };
  31
  32   typedef IntRange<Int> Range;
  33   typedef IntegersSubsetGeneric<Int> Subset;
  34   typedef IntegersSubsetMapping<unsigned,Subset,Int> Mapping;
  35
  36   TEST(IntegersSubsetTest, GeneralTest) {
  37
  38     // Test construction.
  39
  40     std::vector<Range> Ranges;
  41     Ranges.reserve(3);
  42
  43     // Initialize Subset as union of three pairs:
  44     // { {0, 8}, {10, 18}, {20, 28} }
  45     for (unsigned i = 0; i < 3; ++i)
  46       Ranges.push_back(Range(Int(i*10), Int(i*10 + 8)));
  47
  48     Subset TheSubset(Ranges);
  49
  50     for (unsigned i = 0; i < 3; ++i) {
  51       EXPECT_EQ(TheSubset.getItem(i).getLow(), Int(i*10));
  52       EXPECT_EQ(TheSubset.getItem(i).getHigh(), Int(i*10 + 8));
  53     }
  54
  55     EXPECT_EQ(TheSubset.getNumItems(), 3ULL);
  56
  57     // Test belonging to range.
  58
  59     EXPECT_TRUE(TheSubset.isSatisfies(Int(5)));
  60     EXPECT_FALSE(TheSubset.isSatisfies(Int(9)));
  61
  62     // Test when subset contains the only item.
  63
  64     Ranges.clear();
  65     Ranges.push_back(Range(Int(10), Int(10)));
  66
  67     Subset TheSingleNumber(Ranges);
  68
  69     EXPECT_TRUE(TheSingleNumber.isSingleNumber());
  70
  71     Ranges.push_back(Range(Int(12), Int(15)));
  72
  73     Subset NotASingleNumber(Ranges);
  74
  75     EXPECT_FALSE(NotASingleNumber.isSingleNumber());
  76
  77     // Test when subset contains items that are not a ranges but
  78     // the single numbers.
  79
  80     Ranges.clear();
  81     Ranges.push_back(Range(Int(10), Int(10)));
  82     Ranges.push_back(Range(Int(15), Int(19)));
  83
  84     Subset WithSingleNumberItems(Ranges);
  85
  86     EXPECT_TRUE(WithSingleNumberItems.isSingleNumber(0));
  87     EXPECT_FALSE(WithSingleNumberItems.isSingleNumber(1));
  88
  89     // Test size of subset. Note subset itself may be not optimized (improper),
  90     // so it may contain duplicates, and the size of subset { {0, 9} {5, 9} }
  91     // will 15 instead of 10.
  92
  93     Ranges.clear();
  94     Ranges.push_back(Range(Int(0), Int(9)));
  95     Ranges.push_back(Range(Int(5), Int(9)));
  96
  97     Subset NotOptimizedSubset(Ranges);
  98
  99     EXPECT_EQ(NotOptimizedSubset.getSize(), 15ULL);
 100
 101     // Test access to a single value.
 102     // getSingleValue(idx) method represents subset as flat numbers collection,
 103     // so subset { {0, 3}, {8, 10} } will represented as array
 104     // { 0, 1, 2, 3, 8, 9, 10 }.
 105
 106     Ranges.clear();
 107     Ranges.push_back(Range(Int(0), Int(3)));
 108     Ranges.push_back(Range(Int(8), Int(10)));
 109
 110     Subset OneMoreSubset(Ranges);
 111
 112     EXPECT_EQ(OneMoreSubset.getSingleValue(5), Int(9));
 113   }
 114
 115   TEST(IntegersSubsetTest, MappingTest) {
 116
 117     Mapping::Cases TheCases;
 118
 119     unsigned Successors[3] = {0, 1, 2};
 120
 121     // Test construction.
 122
 123     Mapping TheMapping;
 124     for (unsigned i = 0; i < 3; ++i)
 125       TheMapping.add(Int(10*i), Int(10*i + 9), Successors + i);
 126     TheMapping.add(Int(111), Int(222), Successors);
 127     TheMapping.removeItem(--TheMapping.end());
 128
 129     TheMapping.getCases(TheCases);
 130
 131     EXPECT_EQ(TheCases.size(), 3ULL);
 132
 133     for (unsigned i = 0; i < 3; ++i) {
 134       Mapping::Cases::iterator CaseIt = TheCases.begin();
 135       std::advance(CaseIt, i);
 136       EXPECT_EQ(CaseIt->first, Successors + i);
 137       EXPECT_EQ(CaseIt->second.getNumItems(), 1ULL);
 138       EXPECT_EQ(CaseIt->second.getItem(0), Range(Int(10*i), Int(10*i + 9)));
 139     }
 140
 141     // Test verification.
 142
 143     Mapping ImproperMapping;
 144     ImproperMapping.add(Int(10), Int(11), Successors + 0);
 145     ImproperMapping.add(Int(11), Int(12), Successors + 1);
 146
 147     Mapping::RangeIterator ErrItem;
 148     EXPECT_FALSE(ImproperMapping.verify(ErrItem));
 149     EXPECT_EQ(ErrItem, --ImproperMapping.end());
 150
 151     Mapping ProperMapping;
 152     ProperMapping.add(Int(10), Int(11), Successors + 0);
 153     ProperMapping.add(Int(12), Int(13), Successors + 1);
 154
 155     EXPECT_TRUE(ProperMapping.verify(ErrItem));
 156
 157     // Test optimization.
 158
 159     Mapping ToBeOptimized;
 160
 161     for (unsigned i = 0; i < 3; ++i) {
 162       ToBeOptimized.add(Int(i * 10), Int(i * 10 + 1), Successors + i);
 163       ToBeOptimized.add(Int(i * 10 + 2), Int(i * 10 + 9), Successors + i);
 164     }
 165
 166     ToBeOptimized.optimize();
 167
 168     TheCases.clear();
 169     ToBeOptimized.getCases(TheCases);
 170
 171     EXPECT_EQ(TheCases.size(), 3ULL);
 172
 173     for (unsigned i = 0; i < 3; ++i) {
 174       Mapping::Cases::iterator CaseIt = TheCases.begin();
 175       std::advance(CaseIt, i);
 176       EXPECT_EQ(CaseIt->first, Successors + i);
 177       EXPECT_EQ(CaseIt->second.getNumItems(), 1ULL);
 178       EXPECT_EQ(CaseIt->second.getItem(0), Range(Int(i * 10), Int(i * 10 + 9)));
 179     }
 180   }
 181
 182   TEST(IntegersSubsetTest, ExcludeTest) {
 183     std::vector<Range> Ranges;
 184     Ranges.reserve(3);
 185
 186     Mapping TheMapping;
 187
 188     // Test case
 189     // { {0, 4}, {7, 10} {13, 17} }
 190     // sub
 191     // { {3, 14} }
 192     // =
 193     // { {0, 2}, {15, 17} }
 194
 195     Ranges.push_back(Range(Int(0), Int(4)));
 196     Ranges.push_back(Range(Int(7), Int(10)));
 197     Ranges.push_back(Range(Int(13), Int(17)));
 198
 199     Subset TheSubset(Ranges);
 200
 201     TheMapping.add(TheSubset);
 202
 203     Ranges.clear();
 204     Ranges.push_back(Range(Int(3), Int(14)));
 205     TheSubset = Subset(Ranges);
 206
 207     TheMapping.exclude(TheSubset);
 208
 209     TheSubset = TheMapping.getCase();
 210
 211     EXPECT_EQ(TheSubset.getNumItems(), 2ULL);
 212     EXPECT_EQ(TheSubset.getItem(0), Range(Int(0), Int(2)));
 213     EXPECT_EQ(TheSubset.getItem(1), Range(Int(15), Int(17)));
 214
 215     // Test case
 216     // { {0, 4}, {7, 10} {13, 17} }
 217     // sub
 218     // { {0, 4}, {13, 17} }
 219     // =
 220     // { {7, 10 }
 221
 222     Ranges.clear();
 223     Ranges.push_back(Range(Int(0), Int(4)));
 224     Ranges.push_back(Range(Int(7), Int(10)));
 225     Ranges.push_back(Range(Int(13), Int(17)));
 226
 227     TheSubset = Subset(Ranges);
 228
 229     TheMapping.clear();
 230     TheMapping.add(TheSubset);
 231
 232     Ranges.clear();
 233     Ranges.push_back(Range(Int(0), Int(4)));
 234     Ranges.push_back(Range(Int(13), Int(17)));
 235
 236     TheSubset = Subset(Ranges);
 237
 238     TheMapping.exclude(TheSubset);
 239
 240     TheSubset = TheMapping.getCase();
 241
 242     EXPECT_EQ(TheSubset.getNumItems(), 1ULL);
 243     EXPECT_EQ(TheSubset.getItem(0), Range(Int(7), Int(10)));
 244
 245     // Test case
 246     // { {0, 17} }
 247     // sub
 248     // { {1, 5}, {10, 12}, {15, 16} }
 249     // =
 250     // { {0}, {6, 9}, {13, 14}, {17} }
 251
 252     Ranges.clear();
 253     Ranges.push_back(Range(Int(0), Int(17)));
 254
 255     TheSubset = Subset(Ranges);
 256
 257     TheMapping.clear();
 258     TheMapping.add(TheSubset);
 259
 260     Ranges.clear();
 261     Ranges.push_back(Range(Int(1), Int(5)));
 262     Ranges.push_back(Range(Int(10), Int(12)));
 263     Ranges.push_back(Range(Int(15), Int(16)));
 264
 265     TheSubset = Subset(Ranges);
 266
 267     TheMapping.exclude(TheSubset);
 268
 269     TheSubset = TheMapping.getCase();
 270
 271     EXPECT_EQ(TheSubset.getNumItems(), 4ULL);
 272     EXPECT_EQ(TheSubset.getItem(0), Range(Int(0)));
 273     EXPECT_EQ(TheSubset.getItem(1), Range(Int(6), Int(9)));
 274     EXPECT_EQ(TheSubset.getItem(2), Range(Int(13), Int(14)));
 275     EXPECT_EQ(TheSubset.getItem(3), Range(Int(17)));
 276
 277     // Test case
 278     // { {2, 4} }
 279     // sub
 280     // { {0, 5} }
 281     // =
 282     // { empty }
 283
 284     Ranges.clear();
 285     Ranges.push_back(Range(Int(2), Int(4)));
 286
 287     TheSubset = Subset(Ranges);
 288
 289     TheMapping.clear();
 290     TheMapping.add(TheSubset);
 291
 292     Ranges.clear();
 293     Ranges.push_back(Range(Int(0), Int(5)));
 294
 295     TheSubset = Subset(Ranges);
 296
 297     TheMapping.exclude(TheSubset);
 298
 299     EXPECT_TRUE(TheMapping.empty());
 300
 301     // Test case
 302     // { {2, 4} }
 303     // sub
 304     // { {7, 8} }
 305     // =
 306     // { {2, 4} }
 307
 308     Ranges.clear();
 309     Ranges.push_back(Range(Int(2), Int(4)));
 310
 311     TheSubset = Subset(Ranges);
 312
 313     TheMapping.clear();
 314     TheMapping.add(TheSubset);
 315
 316     Ranges.clear();
 317     Ranges.push_back(Range(Int(7), Int(8)));
 318
 319     TheSubset = Subset(Ranges);
 320
 321     TheMapping.exclude(TheSubset);
 322
 323     TheSubset = TheMapping.getCase();
 324
 325     EXPECT_EQ(TheSubset.getNumItems(), 1ULL);
 326     EXPECT_EQ(TheSubset.getItem(0), Range(Int(2), Int(4)));
 327
 328     // Test case
 329     // { {3, 7} }
 330     // sub
 331     // { {1, 4} }
 332     // =
 333     // { {5, 7} }
 334
 335     Ranges.clear();
 336     Ranges.push_back(Range(Int(3), Int(7)));
 337
 338     TheSubset = Subset(Ranges);
 339
 340     TheMapping.clear();
 341     TheMapping.add(TheSubset);
 342
 343     Ranges.clear();
 344     Ranges.push_back(Range(Int(1), Int(4)));
 345
 346     TheSubset = Subset(Ranges);
 347
 348     TheMapping.exclude(TheSubset);
 349
 350     TheSubset = TheMapping.getCase();
 351
 352     EXPECT_EQ(TheSubset.getNumItems(), 1ULL);
 353     EXPECT_EQ(TheSubset.getItem(0), Range(Int(5), Int(7)));
 354   }
 355 }