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     bool operator < (const APInt& RHS) const { return ult(RHS); }
  26     bool operator > (const APInt& RHS) const { return ugt(RHS); }
  27     bool operator <= (const APInt& RHS) const { return ule(RHS); }
  28     bool operator >= (const APInt& RHS) const { return uge(RHS); }
  29   };
  30
  31   typedef IntRange<Int> Range;
  32   typedef IntegersSubsetGeneric<Int> Subset;
  33   typedef IntegersSubsetMapping<unsigned,Subset,Int> Mapping;
  34
  35   TEST(IntegersSubsetTest, GeneralTest) {
  36
  37     // Test construction.
  38
  39     std::vector<Range> Ranges;
  40     Ranges.reserve(3);
  41
  42     // Initialize Subset as union of three pairs:
  43     // { {0, 8}, {10, 18}, {20, 28} }
  44     for (unsigned i = 0; i < 3; ++i)
  45       Ranges.push_back(Range(Int(i*10), Int(i*10 + 8)));
  46
  47     Subset TheSubset(Ranges);
  48
  49     for (unsigned i = 0; i < 3; ++i) {
  50       EXPECT_EQ(TheSubset.getItem(i).getLow(), Int(i*10));
  51       EXPECT_EQ(TheSubset.getItem(i).getHigh(), Int(i*10 + 8));
  52     }
  53
  54     EXPECT_EQ(TheSubset.getNumItems(), 3ULL);
  55
  56     // Test belonging to range.
  57
  58     EXPECT_TRUE(TheSubset.isSatisfies(Int(5)));
  59     EXPECT_FALSE(TheSubset.isSatisfies(Int(9)));
  60
  61     // Test when subset contains the only item.
  62
  63     Ranges.clear();
  64     Ranges.push_back(Range(Int(10), Int(10)));
  65
  66     Subset TheSingleNumber(Ranges);
  67
  68     EXPECT_TRUE(TheSingleNumber.isSingleNumber());
  69
  70     Ranges.push_back(Range(Int(12), Int(15)));
  71
  72     Subset NotASingleNumber(Ranges);
  73
  74     EXPECT_FALSE(NotASingleNumber.isSingleNumber());
  75
  76     // Test when subset contains items that are not a ranges but
  77     // the single numbers.
  78
  79     Ranges.clear();
  80     Ranges.push_back(Range(Int(10), Int(10)));
  81     Ranges.push_back(Range(Int(15), Int(19)));
  82
  83     Subset WithSingleNumberItems(Ranges);
  84
  85     EXPECT_TRUE(WithSingleNumberItems.isSingleNumber(0));
  86     EXPECT_FALSE(WithSingleNumberItems.isSingleNumber(1));
  87
  88     // Test size of subset. Note subset itself may be not optimized (improper),
  89     // so it may contain duplicates, and the size of subset { {0, 9} {5, 9} }
  90     // will 15 instead of 10.
  91
  92     Ranges.clear();
  93     Ranges.push_back(Range(Int(0), Int(9)));
  94     Ranges.push_back(Range(Int(5), Int(9)));
  95
  96     Subset NotOptimizedSubset(Ranges);
  97
  98     EXPECT_EQ(NotOptimizedSubset.getSize(), 15ULL);
  99
 100     // Test access to a single value.
 101     // getSingleValue(idx) method represents subset as flat numbers collection,
 102     // so subset { {0, 3}, {8, 10} } will represented as array
 103     // { 0, 1, 2, 3, 8, 9, 10 }.
 104
 105     Ranges.clear();
 106     Ranges.push_back(Range(Int(0), Int(3)));
 107     Ranges.push_back(Range(Int(8), Int(10)));
 108
 109     Subset OneMoreSubset(Ranges);
 110
 111     EXPECT_EQ(OneMoreSubset.getSingleValue(5), Int(9));
 112   }
 113
 114   TEST(IntegersSubsetTest, MappingTest) {
 115
 116     Mapping::Cases TheCases;
 117
 118     unsigned Successors[3] = {0, 1, 2};
 119
 120     // Test construction.
 121
 122     Mapping TheMapping;
 123     for (unsigned i = 0; i < 3; ++i)
 124       TheMapping.add(Int(10*i), Int(10*i + 9), Successors + i);
 125     TheMapping.add(Int(111), Int(222), Successors);
 126     TheMapping.removeItem(--TheMapping.end());
 127
 128     TheMapping.getCases(TheCases);
 129
 130     EXPECT_EQ(TheCases.size(), 3ULL);
 131
 132     for (unsigned i = 0; i < 3; ++i) {
 133       Mapping::Cases::iterator CaseIt = TheCases.begin();
 134       std::advance(CaseIt, i);
 135       EXPECT_EQ(CaseIt->first, Successors + i);
 136       EXPECT_EQ(CaseIt->second.getNumItems(), 1ULL);
 137       EXPECT_EQ(CaseIt->second.getItem(0), Range(Int(10*i), Int(10*i + 9)));
 138     }
 139
 140     // Test verification.
 141
 142     Mapping ImproperMapping;
 143     ImproperMapping.add(Int(10), Int(11), Successors + 0);
 144     ImproperMapping.add(Int(11), Int(12), Successors + 1);
 145
 146     Mapping::RangeIterator ErrItem;
 147     EXPECT_FALSE(ImproperMapping.verify(ErrItem));
 148     EXPECT_EQ(ErrItem, --ImproperMapping.end());
 149
 150     Mapping ProperMapping;
 151     ProperMapping.add(Int(10), Int(11), Successors + 0);
 152     ProperMapping.add(Int(12), Int(13), Successors + 1);
 153
 154     EXPECT_TRUE(ProperMapping.verify(ErrItem));
 155
 156     // Test optimization.
 157
 158     Mapping ToBeOptimized;
 159
 160     for (unsigned i = 0; i < 3; ++i) {
 161       ToBeOptimized.add(Int(i * 10), Int(i * 10 + 1), Successors + i);
 162       ToBeOptimized.add(Int(i * 10 + 2), Int(i * 10 + 9), Successors + i);
 163     }
 164
 165     ToBeOptimized.optimize();
 166
 167     TheCases.clear();
 168     ToBeOptimized.getCases(TheCases);
 169
 170     EXPECT_EQ(TheCases.size(), 3ULL);
 171
 172     for (unsigned i = 0; i < 3; ++i) {
 173       Mapping::Cases::iterator CaseIt = TheCases.begin();
 174       std::advance(CaseIt, i);
 175       EXPECT_EQ(CaseIt->first, Successors + i);
 176       EXPECT_EQ(CaseIt->second.getNumItems(), 1ULL);
 177       EXPECT_EQ(CaseIt->second.getItem(0), Range(Int(i * 10), Int(i * 10 + 9)));
 178     }
 179   }
 180 }