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
18using namespace llvm;
19
20namespace {
21
22  class Int : public APInt {
23  public:
24    Int() {}
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); }
31  };
32
33  typedef IntRange<Int> Range;
34  typedef IntegersSubsetGeneric<Int> Subset;
35  typedef IntegersSubsetMapping<unsigned,Subset,Int> Mapping;
36
37  TEST(IntegersSubsetTest, GeneralTest) {
38
39    // Test construction.
40
41    std::vector<Range> Ranges;
42    Ranges.reserve(3);
43
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)));
48
49    Subset TheSubset(Ranges);
50
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));
54    }
55
56    EXPECT_EQ(TheSubset.getNumItems(), 3ULL);
57
58    // Test belonging to range.
59
60    EXPECT_TRUE(TheSubset.isSatisfies(Int(5)));
61    EXPECT_FALSE(TheSubset.isSatisfies(Int(9)));
62
63    // Test when subset contains the only item.
64
65    Ranges.clear();
66    Ranges.push_back(Range(Int(10), Int(10)));
67
68    Subset TheSingleNumber(Ranges);
69
70    EXPECT_TRUE(TheSingleNumber.isSingleNumber());
71
72    Ranges.push_back(Range(Int(12), Int(15)));
73
74    Subset NotASingleNumber(Ranges);
75
76    EXPECT_FALSE(NotASingleNumber.isSingleNumber());
77
78    // Test when subset contains items that are not a ranges but
79    // the single numbers.
80
81    Ranges.clear();
82    Ranges.push_back(Range(Int(10), Int(10)));
83    Ranges.push_back(Range(Int(15), Int(19)));
84
85    Subset WithSingleNumberItems(Ranges);
86
87    EXPECT_TRUE(WithSingleNumberItems.isSingleNumber(0));
88    EXPECT_FALSE(WithSingleNumberItems.isSingleNumber(1));
89
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.
93
94    Ranges.clear();
95    Ranges.push_back(Range(Int(0), Int(9)));
96    Ranges.push_back(Range(Int(5), Int(9)));
97
98    Subset NotOptimizedSubset(Ranges);
99
100    EXPECT_EQ(NotOptimizedSubset.getSize(), 15ULL);
101
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 }.
106
107    Ranges.clear();
108    Ranges.push_back(Range(Int(0), Int(3)));
109    Ranges.push_back(Range(Int(8), Int(10)));
110
111    Subset OneMoreSubset(Ranges);
112
113    EXPECT_EQ(OneMoreSubset.getSingleValue(5), Int(9));
114  }
115
116  TEST(IntegersSubsetTest, MappingTest) {
117
118    Mapping::Cases TheCases;
119
120    unsigned Successors[3] = {0, 1, 2};
121
122    // Test construction.
123
124    Mapping TheMapping;
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());
129
130    TheMapping.getCases(TheCases);
131
132    EXPECT_EQ(TheCases.size(), 3ULL);
133
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)));
140    }
141
142    // Test verification.
143
144    Mapping ImproperMapping;
145    ImproperMapping.add(Int(10), Int(11), Successors + 0);
146    ImproperMapping.add(Int(11), Int(12), Successors + 1);
147
148    Mapping::RangeIterator ErrItem;
149    EXPECT_FALSE(ImproperMapping.verify(ErrItem));
150    EXPECT_EQ(ErrItem, --ImproperMapping.end());
151
152    Mapping ProperMapping;
153    ProperMapping.add(Int(10), Int(11), Successors + 0);
154    ProperMapping.add(Int(12), Int(13), Successors + 1);
155
156    EXPECT_TRUE(ProperMapping.verify(ErrItem));
157
158    // Test optimization.
159
160    Mapping ToBeOptimized;
161
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);
165    }
166
167    ToBeOptimized.optimize();
168
169    TheCases.clear();
170    ToBeOptimized.getCases(TheCases);
171
172    EXPECT_EQ(TheCases.size(), 3ULL);
173
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)));
180    }
181  }
182
183  typedef unsigned unsigned_pair[2];
184  typedef unsigned_pair unsigned_ranges[];
185
186  void TestDiff(
187      const unsigned_ranges LHS,
188      unsigned LSize,
189      const unsigned_ranges RHS,
190      unsigned RSize,
191      const unsigned_ranges ExcludeRes,
192      unsigned ExcludeResSize,
193      const unsigned_ranges IntersectRes,
194      unsigned IntersectResSize
195      ) {
196
197    Mapping::RangesCollection Ranges;
198
199    Mapping LHSMapping;
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);
203
204    Ranges.clear();
205
206    Mapping RHSMapping;
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);
210
211    Mapping LExclude, Intersection;
212
213    LHSMapping.diff(&LExclude, &Intersection, 0, RHSMapping);
214
215    if (ExcludeResSize) {
216      EXPECT_EQ(LExclude.size(), ExcludeResSize);
217
218      unsigned i = 0;
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]));
222    } else
223      EXPECT_TRUE(LExclude.empty());
224
225    if (IntersectResSize) {
226      EXPECT_EQ(Intersection.size(), IntersectResSize);
227
228      unsigned i = 0;
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]));
232    } else
233      EXPECT_TRUE(Intersection.empty());
234
235    LExclude.clear();
236    Intersection.clear();
237    RHSMapping.diff(0, &Intersection, &LExclude, LHSMapping);
238
239    // Check LExclude again.
240    if (ExcludeResSize) {
241      EXPECT_EQ(LExclude.size(), ExcludeResSize);
242
243      unsigned i = 0;
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]));
247    } else
248      EXPECT_TRUE(LExclude.empty());
249  }
250
251  TEST(IntegersSubsetTest, DiffTest) {
252
253    static const unsigned NOT_A_NUMBER = 0xffff;
254
255    {
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 } };
260
261      TestDiff(LHS, 3, RHS, 1, ExcludeRes, 2, IntersectRes, 3);
262    }
263
264    {
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 } };
269
270      TestDiff(LHS, 3, RHS, 2, ExcludeRes, 1, IntersectRes, 2);
271    }
272
273    {
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 } };
279
280      TestDiff(LHS, 1, RHS, 3, ExcludeRes, 4, IntersectRes, 3);
281    }
282
283    {
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 } };
288
289      TestDiff(LHS, 1, RHS, 1, ExcludeRes, 0, IntersectRes, 1);
290    }
291
292    {
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} };
297
298      TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 0);
299    }
300
301    {
302      unsigned_ranges LHS = { { 3, 7 } };
303      unsigned_ranges RHS = { { 1, 4 } };
304      unsigned_ranges ExcludeRes = { { 5, 7 } };
305      unsigned_ranges IntersectRes = { { 3, 4 } };
306
307      TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 1);
308    }
309
310    {
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} };
315
316      TestDiff(LHS, 1, RHS, 2, ExcludeRes, 0, IntersectRes, 2);
317    }
318
319    {
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 } };
324
325      TestDiff(LHS, 1, RHS, 1, ExcludeRes, 1, IntersectRes, 0);
326    }
327  }
328}
329