1 //===- llvm/unittest/Support/IntegersSubsetTest.cpp - IntegersSubset tests ===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #include "llvm/ADT/APInt.h"
11 #include "llvm/Support/IntegersSubset.h"
12 #include "llvm/Support/IntegersSubsetMapping.h"
14 #include "gtest/gtest.h"
22 class Int : public APInt {
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); }
32 typedef IntRange<Int> Range;
33 typedef IntegersSubsetGeneric<Int> Subset;
34 typedef IntegersSubsetMapping<unsigned,Subset,Int> Mapping;
36 TEST(IntegersSubsetTest, GeneralTest) {
40 std::vector<Range> Ranges;
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)));
48 Subset TheSubset(Ranges);
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));
55 EXPECT_EQ(TheSubset.getNumItems(), 3ULL);
57 // Test belonging to range.
59 EXPECT_TRUE(TheSubset.isSatisfies(Int(5)));
60 EXPECT_FALSE(TheSubset.isSatisfies(Int(9)));
62 // Test when subset contains the only item.
65 Ranges.push_back(Range(Int(10), Int(10)));
67 Subset TheSingleNumber(Ranges);
69 EXPECT_TRUE(TheSingleNumber.isSingleNumber());
71 Ranges.push_back(Range(Int(12), Int(15)));
73 Subset NotASingleNumber(Ranges);
75 EXPECT_FALSE(NotASingleNumber.isSingleNumber());
77 // Test when subset contains items that are not a ranges but
78 // the single numbers.
81 Ranges.push_back(Range(Int(10), Int(10)));
82 Ranges.push_back(Range(Int(15), Int(19)));
84 Subset WithSingleNumberItems(Ranges);
86 EXPECT_TRUE(WithSingleNumberItems.isSingleNumber(0));
87 EXPECT_FALSE(WithSingleNumberItems.isSingleNumber(1));
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.
94 Ranges.push_back(Range(Int(0), Int(9)));
95 Ranges.push_back(Range(Int(5), Int(9)));
97 Subset NotOptimizedSubset(Ranges);
99 EXPECT_EQ(NotOptimizedSubset.getSize(), 15ULL);
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 }.
107 Ranges.push_back(Range(Int(0), Int(3)));
108 Ranges.push_back(Range(Int(8), Int(10)));
110 Subset OneMoreSubset(Ranges);
112 EXPECT_EQ(OneMoreSubset.getSingleValue(5), Int(9));
115 TEST(IntegersSubsetTest, MappingTest) {
117 Mapping::Cases TheCases;
119 unsigned Successors[3] = {0, 1, 2};
121 // Test construction.
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());
129 TheMapping.getCases(TheCases);
131 EXPECT_EQ(TheCases.size(), 3ULL);
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)));
141 // Test verification.
143 Mapping ImproperMapping;
144 ImproperMapping.add(Int(10), Int(11), Successors + 0);
145 ImproperMapping.add(Int(11), Int(12), Successors + 1);
147 Mapping::RangeIterator ErrItem;
148 EXPECT_FALSE(ImproperMapping.verify(ErrItem));
149 EXPECT_EQ(ErrItem, --ImproperMapping.end());
151 Mapping ProperMapping;
152 ProperMapping.add(Int(10), Int(11), Successors + 0);
153 ProperMapping.add(Int(12), Int(13), Successors + 1);
155 EXPECT_TRUE(ProperMapping.verify(ErrItem));
157 // Test optimization.
159 Mapping ToBeOptimized;
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);
166 ToBeOptimized.optimize();
169 ToBeOptimized.getCases(TheCases);
171 EXPECT_EQ(TheCases.size(), 3ULL);
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)));
182 TEST(IntegersSubsetTest, ExcludeTest) {
183 std::vector<Range> Ranges;
189 // { {0, 4}, {7, 10} {13, 17} }
193 // { {0, 2}, {15, 17} }
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)));
199 Subset TheSubset(Ranges);
201 TheMapping.add(TheSubset);
204 Ranges.push_back(Range(Int(3), Int(14)));
205 TheSubset = Subset(Ranges);
207 TheMapping.exclude(TheSubset);
209 TheSubset = TheMapping.getCase();
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)));
216 // { {0, 4}, {7, 10} {13, 17} }
218 // { {0, 4}, {13, 17} }
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)));
227 TheSubset = Subset(Ranges);
230 TheMapping.add(TheSubset);
233 Ranges.push_back(Range(Int(0), Int(4)));
234 Ranges.push_back(Range(Int(13), Int(17)));
236 TheSubset = Subset(Ranges);
238 TheMapping.exclude(TheSubset);
240 TheSubset = TheMapping.getCase();
242 EXPECT_EQ(TheSubset.getNumItems(), 1ULL);
243 EXPECT_EQ(TheSubset.getItem(0), Range(Int(7), Int(10)));
248 // { {1, 5}, {10, 12}, {15, 16} }
250 // { {0}, {6, 9}, {13, 14}, {17} }
253 Ranges.push_back(Range(Int(0), Int(17)));
255 TheSubset = Subset(Ranges);
258 TheMapping.add(TheSubset);
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)));
265 TheSubset = Subset(Ranges);
267 TheMapping.exclude(TheSubset);
269 TheSubset = TheMapping.getCase();
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)));
285 Ranges.push_back(Range(Int(2), Int(4)));
287 TheSubset = Subset(Ranges);
290 TheMapping.add(TheSubset);
293 Ranges.push_back(Range(Int(0), Int(5)));
295 TheSubset = Subset(Ranges);
297 TheMapping.exclude(TheSubset);
299 EXPECT_TRUE(TheMapping.empty());
309 Ranges.push_back(Range(Int(2), Int(4)));
311 TheSubset = Subset(Ranges);
314 TheMapping.add(TheSubset);
317 Ranges.push_back(Range(Int(7), Int(8)));
319 TheSubset = Subset(Ranges);
321 TheMapping.exclude(TheSubset);
323 TheSubset = TheMapping.getCase();
325 EXPECT_EQ(TheSubset.getNumItems(), 1ULL);
326 EXPECT_EQ(TheSubset.getItem(0), Range(Int(2), Int(4)));
336 Ranges.push_back(Range(Int(3), Int(7)));
338 TheSubset = Subset(Ranges);
341 TheMapping.add(TheSubset);
344 Ranges.push_back(Range(Int(1), Int(4)));
346 TheSubset = Subset(Ranges);
348 TheMapping.exclude(TheSubset);
350 TheSubset = TheMapping.getCase();
352 EXPECT_EQ(TheSubset.getNumItems(), 1ULL);
353 EXPECT_EQ(TheSubset.getItem(0), Range(Int(5), Int(7)));