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