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/Support/IntegersSubset.h"
11#include "llvm/ADT/APInt.h"
12#include "llvm/Support/IntegersSubsetMapping.h"
13#include "gtest/gtest.h"
14#include <vector>
15
16using namespace llvm;
17
18namespace {
19
20  class Int : public APInt {
21  public:
22    Int() {}
23    Int(uint64_t V) : APInt(64, V) {}
24    Int(const APInt& Src) : APInt(Src) {}
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
181  typedef unsigned unsigned_pair[2];
182  typedef unsigned_pair unsigned_ranges[];
183
184  void TestDiff(
185      const unsigned_ranges LHS,
186      unsigned LSize,
187      const unsigned_ranges RHS,
188      unsigned RSize,
189      const unsigned_ranges ExcludeRes,
190      unsigned ExcludeResSize,
191      const unsigned_ranges IntersectRes,
192      unsigned IntersectResSize
193      ) {
194
195    Mapping::RangesCollection Ranges;
196
197    Mapping LHSMapping;
198    for (unsigned i = 0; i < LSize; ++i)
199      Ranges.push_back(Range(Int(LHS[i][0]), Int(LHS[i][1])));
200    LHSMapping.add(Ranges);
201
202    Ranges.clear();
203
204    Mapping RHSMapping;
205    for (unsigned i = 0; i < RSize; ++i)
206      Ranges.push_back(Range(Int(RHS[i][0]), Int(RHS[i][1])));
207    RHSMapping.add(Ranges);
208
209    Mapping LExclude, Intersection;
210
211    LHSMapping.diff(&LExclude, &Intersection, 0, RHSMapping);
212
213    if (ExcludeResSize) {
214      EXPECT_EQ(LExclude.size(), ExcludeResSize);
215
216      unsigned i = 0;
217      for (Mapping::RangeIterator rei = LExclude.begin(),
218           e = LExclude.end(); rei != e; ++rei, ++i)
219        EXPECT_EQ(rei->first, Range(ExcludeRes[i][0], ExcludeRes[i][1]));
220    } else
221      EXPECT_TRUE(LExclude.empty());
222
223    if (IntersectResSize) {
224      EXPECT_EQ(Intersection.size(), IntersectResSize);
225
226      unsigned i = 0;
227      for (Mapping::RangeIterator ii = Intersection.begin(),
228           e = Intersection.end(); ii != e; ++ii, ++i)
229        EXPECT_EQ(ii->first, Range(IntersectRes[i][0], IntersectRes[i][1]));
230    } else
231      EXPECT_TRUE(Intersection.empty());
232
233    LExclude.clear();
234    Intersection.clear();
235    RHSMapping.diff(0, &Intersection, &LExclude, LHSMapping);
236
237    // Check LExclude again.
238    if (ExcludeResSize) {
239      EXPECT_EQ(LExclude.size(), ExcludeResSize);
240
241      unsigned i = 0;
242      for (Mapping::RangeIterator rei = LExclude.begin(),
243           e = LExclude.end(); rei != e; ++rei, ++i)
244        EXPECT_EQ(rei->first, Range(ExcludeRes[i][0], ExcludeRes[i][1]));
245    } else
246      EXPECT_TRUE(LExclude.empty());
247  }
248
249  TEST(IntegersSubsetTest, DiffTest) {
250
251    static const unsigned NOT_A_NUMBER = 0xffff;
252
253    {
254      unsigned_ranges LHS = { { 0, 4 }, { 7, 10 }, { 13, 17 } };
255      unsigned_ranges RHS = { { 3, 14 } };
256      unsigned_ranges ExcludeRes = { { 0, 2 }, { 15, 17 } };
257      unsigned_ranges IntersectRes = { { 3, 4 }, { 7, 10 }, { 13, 14 } };
258
259      TestDiff(LHS, 3, RHS, 1, ExcludeRes, 2, IntersectRes, 3);
260    }
261
262    {
263      unsigned_ranges LHS = { { 0, 4 }, { 7, 10 }, { 13, 17 } };
264      unsigned_ranges RHS = { { 0, 4 }, { 13, 17 } };
265      unsigned_ranges ExcludeRes = { { 7, 10 } };
266      unsigned_ranges IntersectRes = { { 0, 4 }, { 13, 17 } };
267
268      TestDiff(LHS, 3, RHS, 2, ExcludeRes, 1, IntersectRes, 2);
269    }
270
271    {
272      unsigned_ranges LHS = { { 0, 17 } };
273      unsigned_ranges RHS = { { 1, 5 }, { 10, 12 }, { 15, 16 } };
274      unsigned_ranges ExcludeRes =
275          { { 0, 0 }, { 6, 9 }, { 13, 14 }, { 17, 17 } };
276      unsigned_ranges IntersectRes = { { 1, 5 }, { 10, 12 }, { 15, 16 } };
277
278      TestDiff(LHS, 1, RHS, 3, ExcludeRes, 4, IntersectRes, 3);
279    }
280
281    {
282      unsigned_ranges LHS = { { 2, 4 } };
283      unsigned_ranges RHS = { { 0, 5 } };
284      unsigned_ranges ExcludeRes = { {NOT_A_NUMBER, NOT_A_NUMBER} };
285      unsigned_ranges IntersectRes = { { 2, 4 } };
286
287      TestDiff(LHS, 1, RHS, 1, ExcludeRes, 0, IntersectRes, 1);
288    }
289
290    {
291      unsigned_ranges LHS = { { 2, 4 } };
292      unsigned_ranges RHS = { { 7, 8 } };
293      unsigned_ranges ExcludeRes = { { 2, 4 } };
294      unsigned_ranges IntersectRes = { {NOT_A_NUMBER, NOT_A_NUMBER} };
295
296      TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 0);
297    }
298
299    {
300      unsigned_ranges LHS = { { 3, 7 } };
301      unsigned_ranges RHS = { { 1, 4 } };
302      unsigned_ranges ExcludeRes = { { 5, 7 } };
303      unsigned_ranges IntersectRes = { { 3, 4 } };
304
305      TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 1);
306    }
307
308    {
309      unsigned_ranges LHS = { { 0, 7 } };
310      unsigned_ranges RHS = { { 0, 5 }, { 6, 9 } };
311      unsigned_ranges ExcludeRes = { {NOT_A_NUMBER, NOT_A_NUMBER} };
312      unsigned_ranges IntersectRes = { { 0, 5 }, {6, 7} };
313
314      TestDiff(LHS, 1, RHS, 2, ExcludeRes, 0, IntersectRes, 2);
315    }
316
317    {
318      unsigned_ranges LHS = { { 17, 17 } };
319      unsigned_ranges RHS = { { 4, 4 } };
320      unsigned_ranges ExcludeRes = { {17, 17} };
321      unsigned_ranges IntersectRes = { { NOT_A_NUMBER, NOT_A_NUMBER } };
322
323      TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 0);
324    }
325  }
326}
327