1 #include "mlir/Dialect/SparseTensor/Utils/Merger.h" 2 #include "gmock/gmock.h" 3 #include "gtest/gtest.h" 4 #include <memory> 5 6 using namespace mlir; 7 using namespace mlir::sparse_tensor; 8 9 namespace { 10 11 /// 12 /// Defines macros to iterate binary and the combination of binary operations. 13 /// 14 15 #define FOREVERY_BINOP(DO) \ 16 DO(mulf, Kind::kMulF) \ 17 DO(mulc, Kind::kMulC) \ 18 DO(muli, Kind::kMulI) \ 19 DO(addf, Kind::kAddF) \ 20 DO(addc, Kind::kAddC) \ 21 DO(addi, Kind::kAddI) \ 22 DO(subf, Kind::kSubF) \ 23 DO(subc, Kind::kSubC) \ 24 DO(subi, Kind::kSubI) \ 25 DO(andi, Kind::kAndI) \ 26 DO(xori, Kind::kXorI) \ 27 DO(ori, Kind::kOrI) 28 29 // TODO: Disjunctive binary operations that need special handling are not 30 // included, e.g., Division are not tested (for now) as it need a constant 31 // non-zero dividend. 32 // ##__VA_ARGS__ handles cases when __VA_ARGS__ is empty. 33 #define FOREVERY_COMMON_DISJ_BINOP(TEST, ...) \ 34 TEST(addf, ##__VA_ARGS__) \ 35 TEST(addc, ##__VA_ARGS__) \ 36 TEST(addi, ##__VA_ARGS__) \ 37 TEST(xori, ##__VA_ARGS__) \ 38 TEST(ori, ##__VA_ARGS__) 39 40 // TODO: Conjunctive binary operations that need special handling are not 41 // included, e.g., substraction yields a different pattern as it is mapped to 42 // negate operation. 43 #define FOREVERY_COMMON_CONJ_BINOP(TEST, ...) \ 44 TEST(mulf, ##__VA_ARGS__) \ 45 TEST(mulc, ##__VA_ARGS__) \ 46 TEST(muli, ##__VA_ARGS__) \ 47 TEST(andi, ##__VA_ARGS__) 48 49 #define FOREVERY_PAIR_OF_COMMON_CONJ_DISJ_BINOP(TEST) \ 50 FOREVERY_COMMON_CONJ_BINOP(TEST, addf) \ 51 FOREVERY_COMMON_CONJ_BINOP(TEST, addc) \ 52 FOREVERY_COMMON_CONJ_BINOP(TEST, addi) \ 53 FOREVERY_COMMON_CONJ_BINOP(TEST, xori) \ 54 FOREVERY_COMMON_CONJ_BINOP(TEST, ori) 55 56 #define FOREVERY_PAIR_OF_COMMON_CONJ_CONJ_BINOP(TEST) \ 57 FOREVERY_COMMON_CONJ_BINOP(TEST, mulf) \ 58 FOREVERY_COMMON_CONJ_BINOP(TEST, mulc) \ 59 FOREVERY_COMMON_CONJ_BINOP(TEST, muli) \ 60 FOREVERY_COMMON_CONJ_BINOP(TEST, andi) 61 62 #define FOREVERY_PAIR_OF_COMMON_DISJ_DISJ_BINOP(TEST) \ 63 FOREVERY_COMMON_DISJ_BINOP(TEST, addf) \ 64 FOREVERY_COMMON_DISJ_BINOP(TEST, addc) \ 65 FOREVERY_COMMON_DISJ_BINOP(TEST, addi) \ 66 FOREVERY_COMMON_DISJ_BINOP(TEST, ori) \ 67 FOREVERY_COMMON_DISJ_BINOP(TEST, xori) 68 69 /// 70 /// Helper classes/functions for testing Merger. 71 /// 72 73 /// Simple recursive data structure used to match expressions in Mergers. 74 struct Pattern { 75 Kind kind; 76 77 /// Expressions representing tensors simply have a tensor number. 78 unsigned tensorNum; 79 80 /// Tensor operations point to their children. 81 std::shared_ptr<Pattern> e0; 82 std::shared_ptr<Pattern> e1; 83 84 /// Constructors. 85 /// Rather than using these, please use the readable helper constructor 86 /// functions below to make tests more readable. 87 Pattern(unsigned tensorNum) : kind(Kind::kTensor), tensorNum(tensorNum) {} 88 Pattern(Kind kind, const std::shared_ptr<Pattern> &e0, 89 const std::shared_ptr<Pattern> &e1) 90 : kind(kind), e0(e0), e1(e1) { 91 assert(kind >= Kind::kMulF); 92 assert(e0 && e1); 93 } 94 }; 95 96 /// 97 /// Readable Pattern builder functions. 98 /// These should be preferred over the actual constructors. 99 /// 100 101 static std::shared_ptr<Pattern> tensorPattern(unsigned tensorNum) { 102 return std::make_shared<Pattern>(tensorNum); 103 } 104 105 #define IMPL_BINOP_PATTERN(OP, KIND) \ 106 static std::shared_ptr<Pattern> OP##Pattern( \ 107 const std::shared_ptr<Pattern> &e0, \ 108 const std::shared_ptr<Pattern> &e1) { \ 109 return std::make_shared<Pattern>(KIND, e0, e1); \ 110 } 111 112 FOREVERY_BINOP(IMPL_BINOP_PATTERN) 113 114 #undef IMPL_BINOP_PATTERN 115 116 class MergerTestBase : public ::testing::Test { 117 protected: 118 MergerTestBase(unsigned numTensors, unsigned numLoops) 119 : numTensors(numTensors), numLoops(numLoops), 120 merger(numTensors, numLoops) {} 121 122 /// 123 /// Expression construction helpers. 124 /// 125 126 unsigned tensor(unsigned tensor) { 127 return merger.addExp(Kind::kTensor, tensor); 128 } 129 130 #define IMPL_BINOP_EXPR(OP, KIND) \ 131 unsigned OP##Expr(unsigned e0, unsigned e1) { \ 132 return merger.addExp(KIND, e0, e1); \ 133 } 134 135 FOREVERY_BINOP(IMPL_BINOP_EXPR) 136 137 #undef IMPL_BINOP_EXPR 138 139 /// 140 /// Comparison helpers. 141 /// 142 143 /// For readability of tests. 144 unsigned lat(unsigned lat) { return lat; } 145 146 /// Returns true if a lattice point with an expression matching the given 147 /// pattern and bits matching the given bits is present in lattice points 148 /// [p, p+n) of lattice set s. This is useful for testing partial ordering 149 /// constraints between lattice points. We generally know how contiguous 150 /// groups of lattice points should be ordered with respect to other groups, 151 /// but there is no required ordering within groups. 152 /// If simple is true, then compare the lat.simple field instead to test the 153 /// result after optimization 154 bool latPointWithinRange(unsigned s, unsigned p, unsigned n, 155 const std::shared_ptr<Pattern> &pattern, 156 const BitVector &bits, bool simple) { 157 for (unsigned i = p; i < p + n; ++i) { 158 if (compareExpression(merger.lat(merger.set(s)[i]).exp, pattern) && 159 compareBits(s, i, bits, simple)) 160 return true; 161 } 162 return false; 163 } 164 165 /// Wrapper over latPointWithinRange for readability of tests. 166 void expectLatPointWithinRange(unsigned s, unsigned p, unsigned n, 167 const std::shared_ptr<Pattern> &pattern, 168 const BitVector &bits, bool simple = false) { 169 EXPECT_TRUE(latPointWithinRange(s, p, n, pattern, bits, simple)); 170 } 171 172 /// Wrapper over expectLatPointWithinRange for a single lat point. 173 void expectLatPoint(unsigned s, unsigned p, 174 const std::shared_ptr<Pattern> &pattern, 175 const BitVector &bits, bool simple = false) { 176 EXPECT_TRUE(latPointWithinRange(s, p, 1, pattern, bits, simple)); 177 } 178 179 /// Converts a vector of (loop, tensor) pairs to a bitvector with the 180 /// corresponding bits set. 181 BitVector 182 loopsToBits(const std::vector<std::pair<unsigned, unsigned>> &loops) { 183 BitVector testBits = BitVector(numTensors + 1, false); 184 for (auto l : loops) { 185 auto loop = std::get<0>(l); 186 auto tensor = std::get<1>(l); 187 testBits.set(numTensors * loop + tensor); 188 } 189 return testBits; 190 } 191 192 /// Returns true if the bits of lattice point p in set s match the given bits. 193 /// If simple is true, then compare the lat.simple field instead to test the 194 /// result after optimization 195 bool compareBits(unsigned s, unsigned p, const BitVector &bits, bool simple) { 196 if (simple) 197 return merger.lat(merger.set(s)[p]).simple == bits; 198 return merger.lat(merger.set(s)[p]).bits == bits; 199 } 200 201 /// Check that there are n lattice points in set s. 202 void expectNumLatPoints(unsigned s, unsigned n) { 203 EXPECT_THAT(merger.set(s).size(), n); 204 } 205 206 /// Compares expressions for equality. Equality is defined recursively as: 207 /// - Operations are equal if they have the same kind and children. 208 /// - Leaf tensors are equal if they refer to the same tensor. 209 bool compareExpression(unsigned e, const std::shared_ptr<Pattern> &pattern) { 210 auto tensorExp = merger.exp(e); 211 if (tensorExp.kind != pattern->kind) 212 return false; 213 switch (tensorExp.kind) { 214 // Leaf. 215 case kTensor: 216 return tensorExp.tensor == pattern->tensorNum; 217 case kInvariant: 218 case kIndex: 219 llvm_unreachable("invariant not handled yet"); 220 // Unary operations. 221 case kAbsF: 222 case kAbsC: 223 case kCeilF: 224 case kFloorF: 225 case kSqrtF: 226 case kSqrtC: 227 case kExpm1F: 228 case kExpm1C: 229 case kLog1pF: 230 case kLog1pC: 231 case kSinF: 232 case kSinC: 233 case kTanhF: 234 case kTanhC: 235 case kNegF: 236 case kNegC: 237 case kNegI: 238 case kTruncF: 239 case kExtF: 240 case kCastFS: 241 case kCastFU: 242 case kCastSF: 243 case kCastUF: 244 case kCastS: 245 case kCastU: 246 case kCastIdx: 247 case kTruncI: 248 case kCIm: 249 case kCRe: 250 case kBitCast: 251 case kBinaryBranch: 252 case kUnary: 253 case kShlI: 254 case kBinary: 255 return compareExpression(tensorExp.children.e0, pattern->e0); 256 // Binary operations. 257 case kMulF: 258 case kMulC: 259 case kMulI: 260 case kDivF: 261 case kDivC: 262 case kDivS: 263 case kDivU: 264 case kAddF: 265 case kAddC: 266 case kAddI: 267 case kSubF: 268 case kSubC: 269 case kSubI: 270 case kAndI: 271 case kOrI: 272 case kXorI: 273 case kShrS: 274 case kShrU: 275 return compareExpression(tensorExp.children.e0, pattern->e0) && 276 compareExpression(tensorExp.children.e1, pattern->e1); 277 } 278 llvm_unreachable("unexpected kind"); 279 } 280 281 unsigned numTensors; 282 unsigned numLoops; 283 Merger merger; 284 }; 285 286 /// 287 /// Tests with all sparse inputs. 288 /// 289 290 class MergerTest3T1L : public MergerTestBase { 291 protected: 292 // Our three tensors (two inputs, one output). 293 const unsigned t0 = 0, t1 = 1, t2 = 2; 294 295 // Our single loop. 296 const unsigned l0 = 0; 297 298 MergerTest3T1L() : MergerTestBase(3, 1) { 299 // Tensor 0: sparse input vector. 300 merger.addExp(Kind::kTensor, t0, -1u); 301 merger.setDim(t0, l0, Dim::kSparse); 302 303 // Tensor 1: sparse input vector. 304 merger.addExp(Kind::kTensor, t1, -1u); 305 merger.setDim(t1, l0, Dim::kSparse); 306 307 // Tensor 2: dense output vector. 308 merger.addExp(Kind::kTensor, t2, -1u); 309 merger.setDim(t2, l0, Dim::kDense); 310 } 311 }; 312 313 class MergerTest4T1L : public MergerTestBase { 314 protected: 315 // Our four tensors (three inputs, one output). 316 const unsigned t0 = 0, t1 = 1, t2 = 2, t3 = 3; 317 318 // Our single loop. 319 const unsigned l0 = 0; 320 321 MergerTest4T1L() : MergerTestBase(4, 1) { 322 // Tensor 0: sparse input vector. 323 merger.addExp(Kind::kTensor, t0, -1u); 324 merger.setDim(t0, l0, Dim::kSparse); 325 326 // Tensor 1: sparse input vector. 327 merger.addExp(Kind::kTensor, t1, -1u); 328 merger.setDim(t1, l0, Dim::kSparse); 329 330 // Tensor 2: sparse input vector 331 merger.addExp(Kind::kTensor, t2, -1u); 332 merger.setDim(t2, l0, Dim::kSparse); 333 334 // Tensor 3: dense output vector 335 merger.addExp(Kind::kTensor, t3, -1u); 336 merger.setDim(t3, l0, Dim::kDense); 337 } 338 }; 339 340 /// 341 /// Tests with both sparse and dense input. 342 /// 343 344 class MergerTest3T1LD : public MergerTestBase { 345 protected: 346 // Our three tensors (two inputs, one output). 347 const unsigned t0 = 0, t1 = 1, t2 = 2; 348 349 // Our single loop. 350 const unsigned l0 = 0; 351 352 MergerTest3T1LD() : MergerTestBase(3, 1) { 353 // Tensor 0: sparse input vector. 354 merger.addExp(Kind::kTensor, t0, -1u); 355 merger.setDim(t0, l0, Dim::kSparse); 356 357 // Tensor 1: dense input vector. 358 merger.addExp(Kind::kTensor, t1, -1u); 359 merger.setDim(t1, l0, Dim::kDense); 360 361 // Tensor 2: dense output vector. 362 merger.addExp(Kind::kTensor, t2, -1u); 363 merger.setDim(t2, l0, Dim::kDense); 364 } 365 }; 366 367 } // namespace 368 369 /// Vector addition (disjunction) of 2 vectors. i.e.; 370 /// a(i) = b(i) + c(i) 371 /// which should form the 3 lattice points 372 /// { 373 /// lat( i_00 i_01 / (tensor_0 + tensor_1) ) 374 /// lat( i_00 / tensor_0 ) 375 /// lat( i_01 / tensor_1 ) 376 /// } 377 /// and after optimization, the lattice points do not change (as there is no 378 /// duplicated point and all input vectors are sparse vector). 379 /// { 380 /// lat( i_00 i_01 / (tensor_0 + tensor_1) ) 381 /// lat( i_00 / tensor_0 ) 382 /// lat( i_01 / tensor_1 ) 383 /// } 384 #define IMPL_MERGER_TEST_DISJ(OP) \ 385 TEST_F(MergerTest3T1L, vector_##OP) { \ 386 auto e = OP##Expr(tensor(t0), tensor(t1)); \ 387 auto p0 = tensorPattern(t0); \ 388 auto p1 = tensorPattern(t1); \ 389 auto s = merger.buildLattices(e, l0); \ 390 \ 391 expectNumLatPoints(s, 3); \ 392 expectLatPoint(s, lat(0), OP##Pattern(p0, p1), \ 393 loopsToBits({{l0, t0}, {l0, t1}})); \ 394 expectLatPointWithinRange(s, lat(1), 2, p0, loopsToBits({{l0, t0}})); \ 395 expectLatPointWithinRange(s, lat(1), 2, p1, loopsToBits({{l0, t1}})); \ 396 \ 397 s = merger.optimizeSet(s); \ 398 expectNumLatPoints(s, 3); \ 399 expectLatPoint(s, lat(0), OP##Pattern(p0, p1), \ 400 loopsToBits({{l0, t0}, {l0, t1}}), true); \ 401 expectLatPointWithinRange(s, lat(1), 2, p0, loopsToBits({{l0, t0}}), \ 402 true); \ 403 expectLatPointWithinRange(s, lat(1), 2, p1, loopsToBits({{l0, t1}}), \ 404 true); \ 405 } 406 407 FOREVERY_COMMON_DISJ_BINOP(IMPL_MERGER_TEST_DISJ) 408 409 #undef IMPL_MERGER_TEST_DISJ 410 411 /// Vector multiplication (conjunction) of 2 vectors, i.e.; 412 /// a(i) = b(i) * c(i) 413 /// which should form the single lattice point 414 /// { 415 /// lat( i_00 i_01 / (tensor_0 * tensor_1) ) 416 /// } 417 #define IMPL_MERGER_TEST_CONJ(OP) \ 418 TEST_F(MergerTest3T1L, vector_##OP) { \ 419 auto e = OP##Expr(t0, t1); \ 420 auto p0 = tensorPattern(t0); \ 421 auto p1 = tensorPattern(t1); \ 422 auto s = merger.buildLattices(e, l0); \ 423 \ 424 expectNumLatPoints(s, 1); \ 425 expectLatPoint(s, lat(0), OP##Pattern(p0, p1), \ 426 loopsToBits({{l0, t0}, {l0, t1}})); \ 427 \ 428 s = merger.optimizeSet(s); \ 429 expectNumLatPoints(s, 1); \ 430 expectLatPoint(s, lat(0), OP##Pattern(p0, p1), \ 431 loopsToBits({{l0, t0}, {l0, t1}}), true); \ 432 } 433 434 FOREVERY_COMMON_CONJ_BINOP(IMPL_MERGER_TEST_CONJ) 435 436 #undef IMPL_MERGER_TEST_CONJ 437 438 /// Vector multiplication (conjunction) then addition (disjunction), i.e.; 439 /// a(i) = b(i) * c(i) + d(i); 440 /// which should form 441 /// { 442 /// lat( i_00 i_01 i_02 / (tensor_0 * tensor_1) + tensor_2 ) 443 /// lat( i_00 i_01 / tensor_0 * tensor_1 444 /// lat( i_02 / tensor_2 ) 445 /// } 446 #define IMPL_MERGER_TEST_CONJ_DISJ(CONJ, DISJ) \ 447 TEST_F(MergerTest4T1L, vector_##CONJ##_##DISJ) { \ 448 auto em = CONJ##Expr(t0, t1); \ 449 auto e = DISJ##Expr(em, t2); \ 450 auto p0 = tensorPattern(t0); \ 451 auto p1 = tensorPattern(t1); \ 452 auto p2 = tensorPattern(t2); \ 453 auto s = merger.buildLattices(e, l0); \ 454 \ 455 expectNumLatPoints(s, 3); \ 456 expectLatPoint(s, lat(0), DISJ##Pattern(CONJ##Pattern(p0, p1), p2), \ 457 loopsToBits({{l0, t0}, {l0, t1}, {l0, t2}})); \ 458 expectLatPointWithinRange(s, lat(1), 2, CONJ##Pattern(p0, p1), \ 459 loopsToBits({{l0, t0}, {l0, t1}})); \ 460 expectLatPointWithinRange(s, lat(1), 2, p2, loopsToBits({{l0, t2}})); \ 461 \ 462 s = merger.optimizeSet(s); \ 463 expectNumLatPoints(s, 3); \ 464 expectLatPoint(s, lat(0), DISJ##Pattern(CONJ##Pattern(p0, p1), p2), \ 465 loopsToBits({{l0, t0}, {l0, t1}, {l0, t2}})); \ 466 expectLatPointWithinRange(s, lat(1), 2, CONJ##Pattern(p0, p1), \ 467 loopsToBits({{l0, t0}, {l0, t1}})); \ 468 expectLatPointWithinRange(s, lat(1), 2, p2, loopsToBits({{l0, t2}})); \ 469 } 470 471 FOREVERY_PAIR_OF_COMMON_CONJ_DISJ_BINOP(IMPL_MERGER_TEST_CONJ_DISJ) 472 473 #undef IMPL_MERGER_TEST_CONJ_DISJ 474 475 /// Vector addition (disjunction) then addition (disjunction), i.e.; 476 /// a(i) = b(i) + c(i) + d(i) 477 /// which should form 478 /// { 479 /// lat( i_00 i_01 i_02 / (tensor_0 + tensor_1) + tensor_2 ) 480 /// lat( i_02 i_01 / tensor_2 + tensor_1 ) 481 /// lat( i_02 i_00 / tensor_2 + tensor_0 ) 482 /// lat( i_01 i_00 / tensor_1 + tensor_0 ) 483 /// lat( i_02 / tensor_2 ) 484 /// lat( i_01 / tensor_1 ) 485 /// lat( i_00 / tensor_0 ) 486 /// } 487 #define IMPL_MERGER_TEST_DISJ_DISJ(DISJ1, DISJ2) \ 488 TEST_F(MergerTest4T1L, Vector_##DISJ1##_##DISJ2) { \ 489 auto em = DISJ1##Expr(t0, t1); \ 490 auto e = DISJ2##Expr(em, t2); \ 491 auto p0 = tensorPattern(t0); \ 492 auto p1 = tensorPattern(t1); \ 493 auto p2 = tensorPattern(t2); \ 494 auto s = merger.buildLattices(e, l0); \ 495 \ 496 expectNumLatPoints(s, 7); \ 497 expectLatPoint(s, lat(0), DISJ2##Pattern(DISJ1##Pattern(p0, p1), p2), \ 498 loopsToBits({{l0, t0}, {l0, t1}, {l0, t2}})); \ 499 expectLatPointWithinRange(s, lat(1), 6, DISJ2##Pattern(p1, p2), \ 500 loopsToBits({{l0, t1}, {l0, t2}})); \ 501 expectLatPointWithinRange(s, lat(1), 6, DISJ2##Pattern(p0, p2), \ 502 loopsToBits({{l0, t0}, {l0, t2}})); \ 503 expectLatPointWithinRange(s, lat(1), 6, DISJ1##Pattern(p0, p1), \ 504 loopsToBits({{l0, t0}, {l0, t1}})); \ 505 expectLatPointWithinRange(s, lat(1), 6, p2, loopsToBits({{l0, t2}})); \ 506 expectLatPointWithinRange(s, lat(1), 6, p1, loopsToBits({{l0, t1}})); \ 507 expectLatPointWithinRange(s, lat(1), 6, p0, loopsToBits({{l0, t0}})); \ 508 \ 509 s = merger.optimizeSet(s); \ 510 expectNumLatPoints(s, 7); \ 511 expectLatPoint(s, lat(0), DISJ2##Pattern(DISJ1##Pattern(p0, p1), p2), \ 512 loopsToBits({{l0, t0}, {l0, t1}, {l0, t2}})); \ 513 expectLatPointWithinRange(s, lat(1), 6, DISJ2##Pattern(p1, p2), \ 514 loopsToBits({{l0, t1}, {l0, t2}})); \ 515 expectLatPointWithinRange(s, lat(1), 6, DISJ2##Pattern(p0, p2), \ 516 loopsToBits({{l0, t0}, {l0, t2}})); \ 517 expectLatPointWithinRange(s, lat(1), 6, DISJ1##Pattern(p0, p1), \ 518 loopsToBits({{l0, t0}, {l0, t1}})); \ 519 expectLatPointWithinRange(s, lat(1), 6, p2, loopsToBits({{l0, t2}})); \ 520 expectLatPointWithinRange(s, lat(1), 6, p1, loopsToBits({{l0, t1}})); \ 521 expectLatPointWithinRange(s, lat(1), 6, p0, loopsToBits({{l0, t0}})); \ 522 } 523 524 FOREVERY_PAIR_OF_COMMON_DISJ_DISJ_BINOP(IMPL_MERGER_TEST_DISJ_DISJ) 525 526 #undef IMPL_MERGER_TEST_DISJ_DISJ 527 528 /// Vector multiplication (conjunction) then multiplication (conjunction), i.e.; 529 /// a(i) = b(i) * c(i) * d(i); 530 /// which should form 531 /// { 532 /// lat( i_00 i_01 i_02 / tensor_0 * tensor_1 * tensor_2 ) 533 /// } 534 #define IMPL_MERGER_TEST_CONJ_CONJ(CONJ1, CONJ2) \ 535 TEST_F(MergerTest4T1L, vector_##CONJ1##_##CONJ2) { \ 536 auto em = CONJ1##Expr(t0, t1); \ 537 auto e = CONJ2##Expr(em, t2); \ 538 auto p0 = tensorPattern(t0); \ 539 auto p1 = tensorPattern(t1); \ 540 auto p2 = tensorPattern(t2); \ 541 auto s = merger.buildLattices(e, l0); \ 542 expectNumLatPoints(s, 1); \ 543 expectLatPoint(s, lat(0), CONJ2##Pattern(CONJ1##Pattern(p0, p1), p2), \ 544 loopsToBits({{l0, t0}, {l0, t1}, {l0, t2}})); \ 545 s = merger.optimizeSet(s); \ 546 expectNumLatPoints(s, 1); \ 547 expectLatPoint(s, lat(0), CONJ2##Pattern(CONJ1##Pattern(p0, p1), p2), \ 548 loopsToBits({{l0, t0}, {l0, t1}, {l0, t2}}), true); \ 549 } 550 551 FOREVERY_PAIR_OF_COMMON_CONJ_CONJ_BINOP(IMPL_MERGER_TEST_CONJ_CONJ) 552 553 #undef IMPL_MERGER_TEST_CONJ_CONJ 554 555 /// Vector addition (disjunction) of 2 vectors, i.e.; 556 /// a(i) = b(i) + c(i) 557 /// which should form the 3 lattice points 558 /// { 559 /// lat( i_00 i_01 / (sparse_tensor_0 + dense_tensor_1) ) 560 /// lat( i_00 / sparse_tensor_0 ) 561 /// lat( i_01 / dense_tensor_1 ) 562 /// } 563 /// which should be optimized to 564 /// { 565 /// lat( i_00 i_01 / (sparse_tensor_0 + dense_tensor_1) ) (not singleton) 566 /// lat( i_01 / dense_tensor_0 ) (no sparse dimension) 567 /// } 568 /// 569 /// lat( i_00 / sparse_tensor_0 ) should be opted out as it only has dense diff 570 /// with lat( i_00 i_01 / (sparse_tensor_0 + dense_tensor_1) ). 571 #define IMPL_MERGER_TEST_OPTIMIZED_DISJ(OP) \ 572 TEST_F(MergerTest3T1LD, vector_opted_##OP) { \ 573 auto e = OP##Expr(tensor(t0), tensor(t1)); \ 574 auto p0 = tensorPattern(t0); \ 575 auto p1 = tensorPattern(t1); \ 576 auto s = merger.buildLattices(e, l0); \ 577 \ 578 expectNumLatPoints(s, 3); \ 579 expectLatPoint(s, lat(0), OP##Pattern(p0, p1), \ 580 loopsToBits({{l0, t0}, {l0, t1}})); \ 581 expectLatPointWithinRange(s, lat(1), 2, p0, loopsToBits({{l0, t0}})); \ 582 expectLatPointWithinRange(s, lat(1), 2, p1, loopsToBits({{l0, t1}})); \ 583 \ 584 s = merger.optimizeSet(s); \ 585 expectNumLatPoints(s, 2); \ 586 expectLatPoint(s, lat(0), OP##Pattern(p0, p1), \ 587 loopsToBits({{l0, t0}, {l0, t1}}), true); \ 588 expectLatPoint(s, lat(1), p1, loopsToBits({{l0, t1}}), true); \ 589 } 590 591 FOREVERY_COMMON_DISJ_BINOP(IMPL_MERGER_TEST_OPTIMIZED_DISJ) 592 593 #undef IMPL_MERGER_TEST_OPTIMIZED_CONJ 594 595 /// Vector multiplication (conjunction) of 2 vectors, i.e.: 596 /// a(i) = b(i) * c(i) 597 /// which should form the single lattice point 598 /// { 599 /// lat( i_00 i_01 / (sparse_tensor_0 * dense_tensor_1) ) 600 /// } 601 /// it should be optimized to 602 /// { 603 /// lat( i_00 / (sparse_tensor_0 * dense_tensor_1) ) 604 /// } 605 /// since i_01 is a dense dimension. 606 #define IMPL_MERGER_TEST_OPTIMIZED_CONJ(OP) \ 607 TEST_F(MergerTest3T1LD, vector_opted_##OP) { \ 608 auto e = OP##Expr(t0, t1); \ 609 auto p0 = tensorPattern(t0); \ 610 auto p1 = tensorPattern(t1); \ 611 auto s = merger.buildLattices(e, l0); \ 612 \ 613 expectNumLatPoints(s, 1); \ 614 expectLatPoint(s, lat(0), OP##Pattern(p0, p1), \ 615 loopsToBits({{l0, t0}, {l0, t1}})); \ 616 \ 617 s = merger.optimizeSet(s); \ 618 expectNumLatPoints(s, 1); \ 619 expectLatPoint(s, lat(0), OP##Pattern(p0, p1), loopsToBits({{l0, t0}}), \ 620 true); \ 621 } 622 623 FOREVERY_COMMON_CONJ_BINOP(IMPL_MERGER_TEST_OPTIMIZED_CONJ) 624 625 #undef IMPL_MERGER_TEST_OPTIMIZED_CONJ 626 627 // TODO: mult-dim tests 628