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 18 using namespace llvm; 19 20 namespace { 21 22 class Int : public APInt { 23 public: Int()24 Int() {} Int(uint64_t V)25 Int(uint64_t V) : APInt(64, V) {} Int(const APInt & Src)26 Int(const APInt& Src) : APInt(Src) {} operator <(const APInt & RHS) const27 bool operator < (const APInt& RHS) const { return ult(RHS); } operator >(const APInt & RHS) const28 bool operator > (const APInt& RHS) const { return ugt(RHS); } operator <=(const APInt & RHS) const29 bool operator <= (const APInt& RHS) const { return ule(RHS); } operator >=(const APInt & RHS) const30 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 TEST(IntegersSubsetTest,GeneralTest)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 TEST(IntegersSubsetTest,MappingTest)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 TestDiff(const unsigned_ranges LHS,unsigned LSize,const unsigned_ranges RHS,unsigned RSize,const unsigned_ranges ExcludeRes,unsigned ExcludeResSize,const unsigned_ranges IntersectRes,unsigned IntersectResSize)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 TEST(IntegersSubsetTest,DiffTest)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