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 16 using namespace llvm; 17 18 namespace { 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
