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 }