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 {
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); }
33 typedef IntRange<Int> Range;
34 typedef IntegersSubsetGeneric<Int> Subset;
35 typedef IntegersSubsetMapping<unsigned,Subset,Int> Mapping;
37 TEST(IntegersSubsetTest, GeneralTest) {
41 std::vector<Range> Ranges;
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)));
49 Subset TheSubset(Ranges);
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));
56 EXPECT_EQ(TheSubset.getNumItems(), 3ULL);
58 // Test belonging to range.
60 EXPECT_TRUE(TheSubset.isSatisfies(Int(5)));
61 EXPECT_FALSE(TheSubset.isSatisfies(Int(9)));
63 // Test when subset contains the only item.
66 Ranges.push_back(Range(Int(10), Int(10)));
68 Subset TheSingleNumber(Ranges);
70 EXPECT_TRUE(TheSingleNumber.isSingleNumber());
72 Ranges.push_back(Range(Int(12), Int(15)));
74 Subset NotASingleNumber(Ranges);
76 EXPECT_FALSE(NotASingleNumber.isSingleNumber());
78 // Test when subset contains items that are not a ranges but
79 // the single numbers.
82 Ranges.push_back(Range(Int(10), Int(10)));
83 Ranges.push_back(Range(Int(15), Int(19)));
85 Subset WithSingleNumberItems(Ranges);
87 EXPECT_TRUE(WithSingleNumberItems.isSingleNumber(0));
88 EXPECT_FALSE(WithSingleNumberItems.isSingleNumber(1));
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.
95 Ranges.push_back(Range(Int(0), Int(9)));
96 Ranges.push_back(Range(Int(5), Int(9)));
98 Subset NotOptimizedSubset(Ranges);
100 EXPECT_EQ(NotOptimizedSubset.getSize(), 15ULL);
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 }.
108 Ranges.push_back(Range(Int(0), Int(3)));
109 Ranges.push_back(Range(Int(8), Int(10)));
111 Subset OneMoreSubset(Ranges);
113 EXPECT_EQ(OneMoreSubset.getSingleValue(5), Int(9));
116 TEST(IntegersSubsetTest, MappingTest) {
118 Mapping::Cases TheCases;
120 unsigned Successors[3] = {0, 1, 2};
122 // Test construction.
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());
130 TheMapping.getCases(TheCases);
132 EXPECT_EQ(TheCases.size(), 3ULL);
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)));
142 // Test verification.
144 Mapping ImproperMapping;
145 ImproperMapping.add(Int(10), Int(11), Successors + 0);
146 ImproperMapping.add(Int(11), Int(12), Successors + 1);
148 Mapping::RangeIterator ErrItem;
149 EXPECT_FALSE(ImproperMapping.verify(ErrItem));
150 EXPECT_EQ(ErrItem, --ImproperMapping.end());
152 Mapping ProperMapping;
153 ProperMapping.add(Int(10), Int(11), Successors + 0);
154 ProperMapping.add(Int(12), Int(13), Successors + 1);
156 EXPECT_TRUE(ProperMapping.verify(ErrItem));
158 // Test optimization.
160 Mapping ToBeOptimized;
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);
167 ToBeOptimized.optimize();
170 ToBeOptimized.getCases(TheCases);
172 EXPECT_EQ(TheCases.size(), 3ULL);
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)));
183 typedef unsigned unsigned_pair[2];
184 typedef unsigned_pair unsigned_ranges[];
187 const unsigned_ranges LHS,
189 const unsigned_ranges RHS,
191 const unsigned_ranges ExcludeRes,
192 unsigned ExcludeResSize,
193 const unsigned_ranges IntersectRes,
194 unsigned IntersectResSize
197 Mapping::RangesCollection Ranges;
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);
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);
211 Mapping LExclude, Intersection;
213 LHSMapping.diff(&LExclude, &Intersection, 0, RHSMapping);
215 if (ExcludeResSize) {
216 EXPECT_EQ(LExclude.size(), ExcludeResSize);
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]));
223 EXPECT_TRUE(LExclude.empty());
225 if (IntersectResSize) {
226 EXPECT_EQ(Intersection.size(), IntersectResSize);
229 for (Mapping::RangeIterator ii = Intersection.begin(),
230 e = Intersection.end(); ii != e; ++ii, ++i)
231 EXPECT_EQ(ii->first, Range(IntersectRes[i][0], IntersectRes[i][1]));
233 EXPECT_TRUE(Intersection.empty());
236 Intersection.clear();
237 RHSMapping.diff(0, &Intersection, &LExclude, LHSMapping);
239 // Check LExclude again.
240 if (ExcludeResSize) {
241 EXPECT_EQ(LExclude.size(), ExcludeResSize);
244 for (Mapping::RangeIterator rei = LExclude.begin(),
245 e = LExclude.end(); rei != e; ++rei, ++i)
246 EXPECT_EQ(rei->first, Range(ExcludeRes[i][0], ExcludeRes[i][1]));
248 EXPECT_TRUE(LExclude.empty());
251 TEST(IntegersSubsetTest, DiffTest) {
253 static const unsigned NOT_A_NUMBER = 0xffff;
256 unsigned_ranges LHS = { { 0, 4 }, { 7, 10 }, { 13, 17 } };
257 unsigned_ranges RHS = { { 3, 14 } };
258 unsigned_ranges ExcludeRes = { { 0, 2 }, { 15, 17 } };
259 unsigned_ranges IntersectRes = { { 3, 4 }, { 7, 10 }, { 13, 14 } };
261 TestDiff(LHS, 3, RHS, 1, ExcludeRes, 2, IntersectRes, 3);
265 unsigned_ranges LHS = { { 0, 4 }, { 7, 10 }, { 13, 17 } };
266 unsigned_ranges RHS = { { 0, 4 }, { 13, 17 } };
267 unsigned_ranges ExcludeRes = { { 7, 10 } };
268 unsigned_ranges IntersectRes = { { 0, 4 }, { 13, 17 } };
270 TestDiff(LHS, 3, RHS, 2, ExcludeRes, 1, IntersectRes, 2);
274 unsigned_ranges LHS = { { 0, 17 } };
275 unsigned_ranges RHS = { { 1, 5 }, { 10, 12 }, { 15, 16 } };
276 unsigned_ranges ExcludeRes =
277 { { 0, 0 }, { 6, 9 }, { 13, 14 }, { 17, 17 } };
278 unsigned_ranges IntersectRes = { { 1, 5 }, { 10, 12 }, { 15, 16 } };
280 TestDiff(LHS, 1, RHS, 3, ExcludeRes, 4, IntersectRes, 3);
284 unsigned_ranges LHS = { { 2, 4 } };
285 unsigned_ranges RHS = { { 0, 5 } };
286 unsigned_ranges ExcludeRes = { {NOT_A_NUMBER, NOT_A_NUMBER} };
287 unsigned_ranges IntersectRes = { { 2, 4 } };
289 TestDiff(LHS, 1, RHS, 1, ExcludeRes, 0, IntersectRes, 1);
293 unsigned_ranges LHS = { { 2, 4 } };
294 unsigned_ranges RHS = { { 7, 8 } };
295 unsigned_ranges ExcludeRes = { { 2, 4 } };
296 unsigned_ranges IntersectRes = { {NOT_A_NUMBER, NOT_A_NUMBER} };
298 TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 0);
302 unsigned_ranges LHS = { { 3, 7 } };
303 unsigned_ranges RHS = { { 1, 4 } };
304 unsigned_ranges ExcludeRes = { { 5, 7 } };
305 unsigned_ranges IntersectRes = { { 3, 4 } };
307 TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 1);
311 unsigned_ranges LHS = { { 0, 7 } };
312 unsigned_ranges RHS = { { 0, 5 }, { 6, 9 } };
313 unsigned_ranges ExcludeRes = { {NOT_A_NUMBER, NOT_A_NUMBER} };
314 unsigned_ranges IntersectRes = { { 0, 5 }, {6, 7} };
316 TestDiff(LHS, 1, RHS, 2, ExcludeRes, 0, IntersectRes, 2);
320 unsigned_ranges LHS = { { 17, 17 } };
321 unsigned_ranges RHS = { { 4, 4 } };
322 unsigned_ranges ExcludeRes = { {17, 17} };
323 unsigned_ranges IntersectRes = { { NOT_A_NUMBER, NOT_A_NUMBER } };
325 TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 0);