1 //===- IslTest.cpp ----------------------------------------------------===// 2 // 3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4 // See https://llvm.org/LICENSE.txt for license information. 5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6 // 7 //===----------------------------------------------------------------------===// 8 9 #include "polly/Support/GICHelper.h" 10 #include "polly/Support/ISLOperators.h" 11 #include "polly/Support/ISLTools.h" 12 #include "gtest/gtest.h" 13 #include "isl/stream.h" 14 #include "isl/val.h" 15 16 using namespace llvm; 17 using namespace polly; 18 19 static isl::space parseSpace(isl_ctx *Ctx, const char *Str) { 20 isl_stream *Stream = isl_stream_new_str(Ctx, Str); 21 auto Obj = isl_stream_read_obj(Stream); 22 23 isl::space Result; 24 if (Obj.type == isl_obj_set) 25 Result = isl::manage(isl_set_get_space(static_cast<isl_set *>(Obj.v))); 26 else if (Obj.type == isl_obj_map) 27 Result = isl::manage(isl_map_get_space(static_cast<isl_map *>(Obj.v))); 28 29 isl_stream_free(Stream); 30 if (Obj.type) 31 Obj.type->free(Obj.v); 32 return Result; 33 } 34 35 #define SPACE(Str) parseSpace(Ctx.get(), Str) 36 37 #define SET(Str) isl::set(Ctx.get(), Str) 38 #define MAP(Str) isl::map(Ctx.get(), Str) 39 40 #define USET(Str) isl::union_set(Ctx.get(), Str) 41 #define UMAP(Str) isl::union_map(Ctx.get(), Str) 42 43 namespace isl { 44 inline namespace noexceptions { 45 46 static bool operator==(const isl::space &LHS, const isl::space &RHS) { 47 return bool(LHS.is_equal(RHS)); 48 } 49 50 static bool operator==(const isl::basic_set &LHS, const isl::basic_set &RHS) { 51 return bool(LHS.is_equal(RHS)); 52 } 53 54 static bool operator==(const isl::set &LHS, const isl::set &RHS) { 55 return bool(LHS.is_equal(RHS)); 56 } 57 58 static bool operator==(const isl::basic_map &LHS, const isl::basic_map &RHS) { 59 return bool(LHS.is_equal(RHS)); 60 } 61 62 static bool operator==(const isl::map &LHS, const isl::map &RHS) { 63 return bool(LHS.is_equal(RHS)); 64 } 65 66 static bool operator==(const isl::union_set &LHS, const isl::union_set &RHS) { 67 return bool(LHS.is_equal(RHS)); 68 } 69 70 static bool operator==(const isl::union_map &LHS, const isl::union_map &RHS) { 71 return bool(LHS.is_equal(RHS)); 72 } 73 74 static bool operator==(const isl::val &LHS, const isl::val &RHS) { 75 return bool(LHS.eq(RHS)); 76 } 77 78 static bool operator==(const isl::pw_aff &LHS, const isl::pw_aff &RHS) { 79 return bool(LHS.is_equal(RHS)); 80 } 81 } // namespace noexceptions 82 } // namespace isl 83 84 namespace { 85 86 TEST(Isl, APIntToIslVal) { 87 isl_ctx *IslCtx = isl_ctx_alloc(); 88 89 { 90 APInt APZero(1, 0, true); 91 auto IslZero = valFromAPInt(IslCtx, APZero, true); 92 EXPECT_TRUE(IslZero.is_zero()); 93 } 94 95 { 96 APInt APNOne(1, -1, true); 97 auto IslNOne = valFromAPInt(IslCtx, APNOne, true); 98 EXPECT_TRUE(IslNOne.is_negone()); 99 } 100 101 { 102 APInt APZero(1, 0, false); 103 auto IslZero = valFromAPInt(IslCtx, APZero, false); 104 EXPECT_TRUE(IslZero.is_zero()); 105 } 106 107 { 108 APInt APOne(1, 1, false); 109 auto IslOne = valFromAPInt(IslCtx, APOne, false); 110 EXPECT_TRUE(IslOne.is_one()); 111 } 112 113 { 114 APInt APNTwo(2, -2, true); 115 auto IslNTwo = valFromAPInt(IslCtx, APNTwo, true); 116 auto IslNTwoCmp = isl::val(IslCtx, -2); 117 EXPECT_EQ(IslNTwo, IslNTwoCmp); 118 } 119 120 { 121 APInt APNOne(32, -1, true); 122 auto IslNOne = valFromAPInt(IslCtx, APNOne, true); 123 EXPECT_TRUE(IslNOne.is_negone()); 124 } 125 126 { 127 APInt APZero(32, 0, false); 128 auto IslZero = valFromAPInt(IslCtx, APZero, false); 129 EXPECT_TRUE(IslZero.is_zero()); 130 } 131 132 { 133 APInt APOne(32, 1, false); 134 auto IslOne = valFromAPInt(IslCtx, APOne, false); 135 EXPECT_TRUE(IslOne.is_one()); 136 } 137 138 { 139 APInt APTwo(32, 2, false); 140 auto IslTwo = valFromAPInt(IslCtx, APTwo, false); 141 EXPECT_EQ(0, IslTwo.cmp_si(2)); 142 } 143 144 { 145 APInt APNOne(32, (1ull << 32) - 1, false); 146 auto IslNOne = valFromAPInt(IslCtx, APNOne, false); 147 auto IslRef = isl::val(IslCtx, 32).pow2().sub_ui(1); 148 EXPECT_EQ(IslNOne, IslRef); 149 } 150 151 { 152 APInt APLarge(130, 2, false); 153 APLarge = APLarge.shl(70); 154 auto IslLarge = valFromAPInt(IslCtx, APLarge, false); 155 auto IslRef = isl::val(IslCtx, 71); 156 IslRef = IslRef.pow2(); 157 EXPECT_EQ(IslLarge, IslRef); 158 } 159 160 isl_ctx_free(IslCtx); 161 } 162 163 TEST(Isl, IslValToAPInt) { 164 isl_ctx *IslCtx = isl_ctx_alloc(); 165 166 { 167 auto IslNOne = isl::val(IslCtx, -1); 168 auto APNOne = APIntFromVal(IslNOne); 169 // Compare with the two's complement of -1 in a 1-bit integer. 170 EXPECT_EQ(1, APNOne); 171 EXPECT_EQ(1u, APNOne.getBitWidth()); 172 } 173 174 { 175 auto IslNTwo = isl::val(IslCtx, -2); 176 auto APNTwo = APIntFromVal(IslNTwo); 177 // Compare with the two's complement of -2 in a 2-bit integer. 178 EXPECT_EQ(2, APNTwo); 179 EXPECT_EQ(2u, APNTwo.getBitWidth()); 180 } 181 182 { 183 auto IslNThree = isl::val(IslCtx, -3); 184 auto APNThree = APIntFromVal(IslNThree); 185 // Compare with the two's complement of -3 in a 3-bit integer. 186 EXPECT_EQ(5, APNThree); 187 EXPECT_EQ(3u, APNThree.getBitWidth()); 188 } 189 190 { 191 auto IslNFour = isl::val(IslCtx, -4); 192 auto APNFour = APIntFromVal(IslNFour); 193 // Compare with the two's complement of -4 in a 3-bit integer. 194 EXPECT_EQ(4, APNFour); 195 EXPECT_EQ(3u, APNFour.getBitWidth()); 196 } 197 198 { 199 auto IslZero = isl::val(IslCtx, 0); 200 auto APZero = APIntFromVal(IslZero); 201 EXPECT_EQ(0, APZero); 202 EXPECT_EQ(1u, APZero.getBitWidth()); 203 } 204 205 { 206 auto IslOne = isl::val(IslCtx, 1); 207 auto APOne = APIntFromVal(IslOne); 208 EXPECT_EQ(1, APOne); 209 EXPECT_EQ(2u, APOne.getBitWidth()); 210 } 211 212 { 213 auto IslTwo = isl::val(IslCtx, 2); 214 auto APTwo = APIntFromVal(IslTwo); 215 EXPECT_EQ(2, APTwo); 216 EXPECT_EQ(3u, APTwo.getBitWidth()); 217 } 218 219 { 220 auto IslThree = isl::val(IslCtx, 3); 221 auto APThree = APIntFromVal(IslThree); 222 EXPECT_EQ(3, APThree); 223 EXPECT_EQ(3u, APThree.getBitWidth()); 224 } 225 226 { 227 auto IslFour = isl::val(IslCtx, 4); 228 auto APFour = APIntFromVal(IslFour); 229 EXPECT_EQ(4, APFour); 230 EXPECT_EQ(4u, APFour.getBitWidth()); 231 } 232 233 { 234 auto IslNOne = isl::val(IslCtx, 32).pow2().sub_ui(1); 235 auto APNOne = APIntFromVal(IslNOne); 236 EXPECT_EQ((1ull << 32) - 1, APNOne); 237 EXPECT_EQ(33u, APNOne.getBitWidth()); 238 } 239 240 { 241 auto IslLargeNum = isl::val(IslCtx, 60); 242 IslLargeNum = IslLargeNum.pow2(); 243 IslLargeNum = IslLargeNum.sub_ui(1); 244 auto APLargeNum = APIntFromVal(IslLargeNum); 245 EXPECT_EQ((1ull << 60) - 1, APLargeNum); 246 EXPECT_EQ(61u, APLargeNum.getBitWidth()); 247 } 248 249 { 250 auto IslExp = isl::val(IslCtx, 500); 251 auto IslLargePow2 = IslExp.pow2(); 252 auto APLargePow2 = APIntFromVal(IslLargePow2); 253 EXPECT_TRUE(APLargePow2.isPowerOf2()); 254 EXPECT_EQ(502u, APLargePow2.getBitWidth()); 255 EXPECT_EQ(502u, APLargePow2.getMinSignedBits()); 256 } 257 258 { 259 auto IslExp = isl::val(IslCtx, 500); 260 auto IslLargeNPow2 = IslExp.pow2().neg(); 261 auto APLargeNPow2 = APIntFromVal(IslLargeNPow2); 262 EXPECT_EQ(501u, APLargeNPow2.getBitWidth()); 263 EXPECT_EQ(501u, APLargeNPow2.getMinSignedBits()); 264 EXPECT_EQ(500, (-APLargeNPow2).exactLogBase2()); 265 } 266 267 { 268 auto IslExp = isl::val(IslCtx, 512); 269 auto IslLargePow2 = IslExp.pow2(); 270 auto APLargePow2 = APIntFromVal(IslLargePow2); 271 EXPECT_TRUE(APLargePow2.isPowerOf2()); 272 EXPECT_EQ(514u, APLargePow2.getBitWidth()); 273 EXPECT_EQ(514u, APLargePow2.getMinSignedBits()); 274 } 275 276 { 277 auto IslExp = isl::val(IslCtx, 512); 278 auto IslLargeNPow2 = IslExp.pow2().neg(); 279 auto APLargeNPow2 = APIntFromVal(IslLargeNPow2); 280 EXPECT_EQ(513u, APLargeNPow2.getBitWidth()); 281 EXPECT_EQ(513u, APLargeNPow2.getMinSignedBits()); 282 EXPECT_EQ(512, (-APLargeNPow2).exactLogBase2()); 283 } 284 285 isl_ctx_free(IslCtx); 286 } 287 288 TEST(Isl, Operators) { 289 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> IslCtx(isl_ctx_alloc(), 290 &isl_ctx_free); 291 292 isl::val ValOne = isl::val(IslCtx.get(), 1); 293 isl::val ValTwo = isl::val(IslCtx.get(), 2); 294 isl::val ValThree = isl::val(IslCtx.get(), 3); 295 isl::val ValFour = isl::val(IslCtx.get(), 4); 296 isl::val ValNegOne = isl::val(IslCtx.get(), -1); 297 isl::val ValNegTwo = isl::val(IslCtx.get(), -2); 298 isl::val ValNegThree = isl::val(IslCtx.get(), -3); 299 isl::val ValNegFour = isl::val(IslCtx.get(), -4); 300 301 isl::space Space = isl::space(IslCtx.get(), 0, 0); 302 isl::local_space LS = isl::local_space(Space); 303 304 isl::pw_aff AffOne = isl::aff(LS, ValOne); 305 isl::pw_aff AffTwo = isl::aff(LS, ValTwo); 306 isl::pw_aff AffThree = isl::aff(LS, ValThree); 307 isl::pw_aff AffFour = isl::aff(LS, ValFour); 308 isl::pw_aff AffNegOne = isl::aff(LS, ValNegOne); 309 isl::pw_aff AffNegTwo = isl::aff(LS, ValNegTwo); 310 isl::pw_aff AffNegThree = isl::aff(LS, ValNegThree); 311 isl::pw_aff AffNegFour = isl::aff(LS, ValNegFour); 312 313 // Addition 314 { 315 EXPECT_EQ(AffOne + AffOne, AffTwo); 316 EXPECT_EQ(AffOne + 1, AffTwo); 317 EXPECT_EQ(1 + AffOne, AffTwo); 318 EXPECT_EQ(AffOne + ValOne, AffTwo); 319 EXPECT_EQ(ValOne + AffOne, AffTwo); 320 } 321 322 // Multiplication 323 { 324 EXPECT_EQ(AffTwo * AffTwo, AffFour); 325 EXPECT_EQ(AffTwo * 2, AffFour); 326 EXPECT_EQ(2 * AffTwo, AffFour); 327 EXPECT_EQ(AffTwo * ValTwo, AffFour); 328 EXPECT_EQ(ValTwo * AffTwo, AffFour); 329 } 330 331 // Subtraction 332 { 333 EXPECT_EQ(AffTwo - AffOne, AffOne); 334 EXPECT_EQ(AffTwo - 1, AffOne); 335 EXPECT_EQ(2 - AffOne, AffOne); 336 EXPECT_EQ(AffTwo - ValOne, AffOne); 337 EXPECT_EQ(ValTwo - AffOne, AffOne); 338 } 339 340 // Division 341 { 342 EXPECT_EQ(AffFour / AffTwo, AffTwo); 343 EXPECT_EQ(AffFour / 2, AffTwo); 344 EXPECT_EQ(4 / AffTwo, AffTwo); 345 EXPECT_EQ(AffFour / ValTwo, AffTwo); 346 EXPECT_EQ(AffFour / 2, AffTwo); 347 348 // Dividend is negative (should be rounded towards zero) 349 EXPECT_EQ(AffNegFour / AffThree, AffNegOne); 350 EXPECT_EQ(AffNegFour / 3, AffNegOne); 351 EXPECT_EQ((-4) / AffThree, AffNegOne); 352 EXPECT_EQ(AffNegFour / ValThree, AffNegOne); 353 EXPECT_EQ(AffNegFour / 3, AffNegOne); 354 355 // Divisor is negative (should be rounded towards zero) 356 EXPECT_EQ(AffFour / AffNegThree, AffNegOne); 357 EXPECT_EQ(AffFour / -3, AffNegOne); 358 EXPECT_EQ(4 / AffNegThree, AffNegOne); 359 EXPECT_EQ(AffFour / ValNegThree, AffNegOne); 360 EXPECT_EQ(AffFour / -3, AffNegOne); 361 } 362 363 // Remainder 364 { 365 EXPECT_EQ(AffThree % AffTwo, AffOne); 366 EXPECT_EQ(AffThree % 2, AffOne); 367 EXPECT_EQ(3 % AffTwo, AffOne); 368 EXPECT_EQ(AffThree % ValTwo, AffOne); 369 EXPECT_EQ(ValThree % AffTwo, AffOne); 370 371 // Dividend is negative (should be rounded towards zero) 372 EXPECT_EQ(AffNegFour % AffThree, AffNegOne); 373 EXPECT_EQ(AffNegFour % 3, AffNegOne); 374 EXPECT_EQ((-4) % AffThree, AffNegOne); 375 EXPECT_EQ(AffNegFour % ValThree, AffNegOne); 376 EXPECT_EQ(AffNegFour % 3, AffNegOne); 377 378 // Divisor is negative (should be rounded towards zero) 379 EXPECT_EQ(AffFour % AffNegThree, AffOne); 380 EXPECT_EQ(AffFour % -3, AffOne); 381 EXPECT_EQ(4 % AffNegThree, AffOne); 382 EXPECT_EQ(AffFour % ValNegThree, AffOne); 383 EXPECT_EQ(AffFour % -3, AffOne); 384 } 385 } 386 387 TEST(Isl, Foreach) { 388 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 389 &isl_ctx_free); 390 391 auto MapSpace = isl::space(Ctx.get(), 0, 1, 1); 392 auto TestBMap = isl::basic_map::universe(MapSpace); 393 TestBMap = TestBMap.fix_si(isl::dim::out, 0, 0); 394 TestBMap = TestBMap.fix_si(isl::dim::out, 0, 0); 395 isl::map TestMap = TestBMap; 396 isl::union_map TestUMap = TestMap; 397 398 auto SetSpace = isl::space(Ctx.get(), 0, 1); 399 isl::basic_set TestBSet = isl::point(SetSpace); 400 isl::set TestSet = TestBSet; 401 isl::union_set TestUSet = TestSet; 402 403 { 404 auto NumBMaps = 0; 405 isl::stat Stat = 406 TestMap.foreach_basic_map([&](isl::basic_map BMap) -> isl::stat { 407 EXPECT_EQ(BMap, TestBMap); 408 NumBMaps++; 409 return isl::stat::ok(); 410 }); 411 412 EXPECT_TRUE(Stat.is_ok()); 413 EXPECT_EQ(1, NumBMaps); 414 } 415 416 { 417 auto NumBSets = 0; 418 isl::stat Stat = 419 TestSet.foreach_basic_set([&](isl::basic_set BSet) -> isl::stat { 420 EXPECT_EQ(BSet, TestBSet); 421 NumBSets++; 422 return isl::stat::ok(); 423 }); 424 EXPECT_TRUE(Stat.is_ok()); 425 EXPECT_EQ(1, NumBSets); 426 } 427 428 { 429 auto NumMaps = 0; 430 isl::stat Stat = TestUMap.foreach_map([&](isl::map Map) -> isl::stat { 431 EXPECT_EQ(Map, TestMap); 432 NumMaps++; 433 return isl::stat::ok(); 434 }); 435 EXPECT_TRUE(Stat.is_ok()); 436 EXPECT_EQ(1, NumMaps); 437 } 438 439 { 440 auto NumSets = 0; 441 isl::stat Stat = TestUSet.foreach_set([&](isl::set Set) -> isl::stat { 442 EXPECT_EQ(Set, TestSet); 443 NumSets++; 444 return isl::stat::ok(); 445 }); 446 EXPECT_TRUE(Stat.is_ok()); 447 EXPECT_EQ(1, NumSets); 448 } 449 450 { 451 auto UPwAff = isl::union_pw_aff(TestUSet, isl::val::zero(Ctx.get())); 452 auto NumPwAffs = 0; 453 isl::stat Stat = UPwAff.foreach_pw_aff([&](isl::pw_aff PwAff) -> isl::stat { 454 EXPECT_TRUE(PwAff.is_cst()); 455 NumPwAffs++; 456 return isl::stat::ok(); 457 }); 458 EXPECT_TRUE(Stat.is_ok()); 459 EXPECT_EQ(1, NumPwAffs); 460 } 461 462 { 463 auto NumBMaps = 0; 464 EXPECT_TRUE(TestMap 465 .foreach_basic_map([&](isl::basic_map BMap) -> isl::stat { 466 EXPECT_EQ(BMap, TestBMap); 467 NumBMaps++; 468 return isl::stat::error(); 469 }) 470 .is_error()); 471 EXPECT_EQ(1, NumBMaps); 472 } 473 474 { 475 auto NumMaps = 0; 476 EXPECT_TRUE(TestUMap 477 .foreach_map([&](isl::map Map) -> isl::stat { 478 EXPECT_EQ(Map, TestMap); 479 NumMaps++; 480 return isl::stat::error(); 481 }) 482 .is_error()); 483 EXPECT_EQ(1, NumMaps); 484 } 485 486 { 487 auto TestPwAff = isl::pw_aff(TestSet, isl::val::zero(Ctx.get())); 488 auto NumPieces = 0; 489 isl::stat Stat = TestPwAff.foreach_piece( 490 [&](isl::set Domain, isl::aff Aff) -> isl::stat { 491 EXPECT_EQ(Domain, TestSet); 492 EXPECT_TRUE(Aff.is_cst()); 493 NumPieces++; 494 return isl::stat::error(); 495 }); 496 EXPECT_TRUE(Stat.is_error()); 497 EXPECT_EQ(1, NumPieces); 498 } 499 } 500 501 TEST(ISLTools, beforeScatter) { 502 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 503 &isl_ctx_free); 504 505 // Basic usage with isl_map 506 EXPECT_EQ(MAP("{ [] -> [i] : i <= 0 }"), 507 beforeScatter(MAP("{ [] -> [0] }"), false)); 508 EXPECT_EQ(MAP("{ [] -> [i] : i < 0 }"), 509 beforeScatter(MAP("{ [] -> [0] }"), true)); 510 511 // Basic usage with isl_union_map 512 EXPECT_EQ(UMAP("{ A[] -> [i] : i <= 0; B[] -> [i] : i <= 0 }"), 513 beforeScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), false)); 514 EXPECT_EQ(UMAP("{ A[] -> [i] : i < 0; B[] -> [i] : i < 0 }"), 515 beforeScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), true)); 516 517 // More than one dimension 518 EXPECT_EQ(UMAP("{ [] -> [i, j] : i < 0; [] -> [i, j] : i = 0 and j <= 0 }"), 519 beforeScatter(UMAP("{ [] -> [0, 0] }"), false)); 520 EXPECT_EQ(UMAP("{ [] -> [i, j] : i < 0; [] -> [i, j] : i = 0 and j < 0 }"), 521 beforeScatter(UMAP("{ [] -> [0, 0] }"), true)); 522 523 // Functional 524 EXPECT_EQ(UMAP("{ [i] -> [j] : j <= i }"), 525 beforeScatter(UMAP("{ [i] -> [i] }"), false)); 526 EXPECT_EQ(UMAP("{ [i] -> [j] : j < i }"), 527 beforeScatter(UMAP("{ [i] -> [i] }"), true)); 528 529 // Parametrized 530 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j <= i }"), 531 beforeScatter(UMAP("[i] -> { [] -> [i] }"), false)); 532 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j < i }"), 533 beforeScatter(UMAP("[i] -> { [] -> [i] }"), true)); 534 535 // More than one range 536 EXPECT_EQ(UMAP("{ [] -> [i] : i <= 10 }"), 537 beforeScatter(UMAP("{ [] -> [0]; [] -> [10] }"), false)); 538 EXPECT_EQ(UMAP("{ [] -> [i] : i < 10 }"), 539 beforeScatter(UMAP("{ [] -> [0]; [] -> [10] }"), true)); 540 541 // Edge case: empty 542 EXPECT_EQ(UMAP("{ [] -> [i] : 1 = 0 }"), 543 beforeScatter(UMAP("{ [] -> [i] : 1 = 0 }"), false)); 544 EXPECT_EQ(UMAP("{ [] -> [i] : 1 = 0 }"), 545 beforeScatter(UMAP("{ [] -> [i] : 1 = 0 }"), true)); 546 } 547 548 TEST(ISLTools, afterScatter) { 549 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 550 &isl_ctx_free); 551 552 // Basic usage with isl_map 553 EXPECT_EQ(MAP("{ [] -> [i] : i >= 0 }"), 554 afterScatter(MAP("{ [] -> [0] }"), false)); 555 EXPECT_EQ(MAP("{ [] -> [i] : i > 0 }"), 556 afterScatter(MAP("{ [] -> [0] }"), true)); 557 558 // Basic usage with isl_union_map 559 EXPECT_EQ(UMAP("{ A[] -> [i] : i >= 0; B[] -> [i] : i >= 0 }"), 560 afterScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), false)); 561 EXPECT_EQ(UMAP("{ A[] -> [i] : i > 0; B[] -> [i] : i > 0 }"), 562 afterScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), true)); 563 564 // More than one dimension 565 EXPECT_EQ(UMAP("{ [] -> [i, j] : i > 0; [] -> [i, j] : i = 0 and j >= 0 }"), 566 afterScatter(UMAP("{ [] -> [0, 0] }"), false)); 567 EXPECT_EQ(UMAP("{ [] -> [i, j] : i > 0; [] -> [i, j] : i = 0 and j > 0 }"), 568 afterScatter(UMAP("{ [] -> [0, 0] }"), true)); 569 570 // Functional 571 EXPECT_EQ(UMAP("{ [i] -> [j] : j >= i }"), 572 afterScatter(UMAP("{ [i] -> [i] }"), false)); 573 EXPECT_EQ(UMAP("{ [i] -> [j] : j > i }"), 574 afterScatter(UMAP("{ [i] -> [i] }"), true)); 575 576 // Parametrized 577 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j >= i }"), 578 afterScatter(UMAP("[i] -> { [] -> [i] }"), false)); 579 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j > i }"), 580 afterScatter(UMAP("[i] -> { [] -> [i] }"), true)); 581 582 // More than one range 583 EXPECT_EQ(UMAP("{ [] -> [i] : i >= 0 }"), 584 afterScatter(UMAP("{ [] -> [0]; [] -> [10] }"), false)); 585 EXPECT_EQ(UMAP("{ [] -> [i] : i > 0 }"), 586 afterScatter(UMAP("{ [] -> [0]; [] -> [10] }"), true)); 587 588 // Edge case: empty 589 EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), false)); 590 EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), true)); 591 } 592 593 TEST(ISLTools, betweenScatter) { 594 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 595 &isl_ctx_free); 596 597 // Basic usage with isl_map 598 EXPECT_EQ(MAP("{ [] -> [i] : 0 < i < 10 }"), 599 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false, 600 false)); 601 EXPECT_EQ( 602 MAP("{ [] -> [i] : 0 <= i < 10 }"), 603 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, false)); 604 EXPECT_EQ( 605 MAP("{ [] -> [i] : 0 < i <= 10 }"), 606 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false, true)); 607 EXPECT_EQ( 608 MAP("{ [] -> [i] : 0 <= i <= 10 }"), 609 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, true)); 610 611 // Basic usage with isl_union_map 612 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 < i < 10; B[] -> [i] : 0 < i < 10 }"), 613 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), 614 UMAP("{ A[] -> [10]; B[] -> [10] }"), false, false)); 615 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 <= i < 10; B[] -> [i] : 0 <= i < 10 }"), 616 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), 617 UMAP("{ A[] -> [10]; B[] -> [10] }"), true, false)); 618 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 < i <= 10; B[] -> [i] : 0 < i <= 10 }"), 619 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), 620 UMAP("{ A[] -> [10]; B[] -> [10] }"), false, true)); 621 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 <= i <= 10; B[] -> [i] : 0 <= i <= 10 }"), 622 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), 623 UMAP("{ A[] -> [10]; B[] -> [10] }"), true, true)); 624 } 625 626 TEST(ISLTools, singleton) { 627 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 628 &isl_ctx_free); 629 630 // No element found 631 EXPECT_EQ(SET("{ [] : 1 = 0 }"), singleton(USET("{ }"), SPACE("{ [] }"))); 632 EXPECT_EQ(MAP("{ [] -> [] : 1 = 0 }"), 633 singleton(UMAP("{ }"), SPACE("{ [] -> [] }"))); 634 635 // One element found 636 EXPECT_EQ(SET("{ [] }"), singleton(USET("{ [] }"), SPACE("{ [] }"))); 637 EXPECT_EQ(MAP("{ [] -> [] }"), 638 singleton(UMAP("{ [] -> [] }"), SPACE("{ [] -> [] }"))); 639 640 // Many elements found 641 EXPECT_EQ(SET("{ [i] : 0 <= i < 10 }"), 642 singleton(USET("{ [i] : 0 <= i < 10 }"), SPACE("{ [i] }"))); 643 EXPECT_EQ( 644 MAP("{ [i] -> [i] : 0 <= i < 10 }"), 645 singleton(UMAP("{ [i] -> [i] : 0 <= i < 10 }"), SPACE("{ [i] -> [j] }"))); 646 647 // Different parameters 648 EXPECT_EQ(SET("[i] -> { [i] }"), 649 singleton(USET("[i] -> { [i] }"), SPACE("{ [i] }"))); 650 EXPECT_EQ(MAP("[i] -> { [i] -> [i] }"), 651 singleton(UMAP("[i] -> { [i] -> [i] }"), SPACE("{ [i] -> [j] }"))); 652 } 653 654 TEST(ISLTools, getNumScatterDims) { 655 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 656 &isl_ctx_free); 657 658 // Basic usage 659 EXPECT_EQ(0, getNumScatterDims(UMAP("{ [] -> [] }"))); 660 EXPECT_EQ(1, getNumScatterDims(UMAP("{ [] -> [i] }"))); 661 EXPECT_EQ(2, getNumScatterDims(UMAP("{ [] -> [i,j] }"))); 662 EXPECT_EQ(3, getNumScatterDims(UMAP("{ [] -> [i,j,k] }"))); 663 664 // Different scatter spaces 665 EXPECT_EQ(0, getNumScatterDims(UMAP("{ A[] -> []; [] -> []}"))); 666 EXPECT_EQ(1, getNumScatterDims(UMAP("{ A[] -> []; [] -> [i] }"))); 667 EXPECT_EQ(2, getNumScatterDims(UMAP("{ A[] -> [i]; [] -> [i,j] }"))); 668 EXPECT_EQ(3, getNumScatterDims(UMAP("{ A[] -> [i]; [] -> [i,j,k] }"))); 669 } 670 671 TEST(ISLTools, getScatterSpace) { 672 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 673 &isl_ctx_free); 674 675 // Basic usage 676 EXPECT_EQ(SPACE("{ [] }"), getScatterSpace(UMAP("{ [] -> [] }"))); 677 EXPECT_EQ(SPACE("{ [i] }"), getScatterSpace(UMAP("{ [] -> [i] }"))); 678 EXPECT_EQ(SPACE("{ [i,j] }"), getScatterSpace(UMAP("{ [] -> [i,j] }"))); 679 EXPECT_EQ(SPACE("{ [i,j,k] }"), getScatterSpace(UMAP("{ [] -> [i,j,k] }"))); 680 681 // Different scatter spaces 682 EXPECT_EQ(SPACE("{ [] }"), getScatterSpace(UMAP("{ A[] -> []; [] -> [] }"))); 683 EXPECT_EQ(SPACE("{ [i] }"), 684 getScatterSpace(UMAP("{ A[] -> []; [] -> [i] }"))); 685 EXPECT_EQ(SPACE("{ [i,j] }"), 686 getScatterSpace(UMAP("{ A[] -> [i]; [] -> [i,j] }"))); 687 EXPECT_EQ(SPACE("{ [i,j,k] }"), 688 getScatterSpace(UMAP("{ A[] -> [i]; [] -> [i,j,k] }"))); 689 } 690 691 TEST(ISLTools, makeIdentityMap) { 692 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 693 &isl_ctx_free); 694 695 // Basic usage 696 EXPECT_EQ(UMAP("{ [i] -> [i] }"), makeIdentityMap(USET("{ [0] }"), false)); 697 EXPECT_EQ(UMAP("{ [0] -> [0] }"), makeIdentityMap(USET("{ [0] }"), true)); 698 699 // Multiple spaces 700 EXPECT_EQ(UMAP("{ [] -> []; [i] -> [i] }"), 701 makeIdentityMap(USET("{ []; [0] }"), false)); 702 EXPECT_EQ(UMAP("{ [] -> []; [0] -> [0] }"), 703 makeIdentityMap(USET("{ []; [0] }"), true)); 704 705 // Edge case: empty 706 EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), false)); 707 EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), true)); 708 } 709 710 TEST(ISLTools, reverseDomain) { 711 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 712 &isl_ctx_free); 713 714 // Basic usage 715 EXPECT_EQ(MAP("{ [B[] -> A[]] -> [] }"), 716 reverseDomain(MAP("{ [A[] -> B[]] -> [] }"))); 717 EXPECT_EQ(UMAP("{ [B[] -> A[]] -> [] }"), 718 reverseDomain(UMAP("{ [A[] -> B[]] -> [] }"))); 719 } 720 721 TEST(ISLTools, shiftDim) { 722 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 723 &isl_ctx_free); 724 725 // Basic usage 726 EXPECT_EQ(SET("{ [1] }"), shiftDim(SET("{ [0] }"), 0, 1)); 727 EXPECT_EQ(USET("{ [1] }"), shiftDim(USET("{ [0] }"), 0, 1)); 728 729 // From-end indexing 730 EXPECT_EQ(USET("{ [0,0,1] }"), shiftDim(USET("{ [0,0,0] }"), -1, 1)); 731 EXPECT_EQ(USET("{ [0,1,0] }"), shiftDim(USET("{ [0,0,0] }"), -2, 1)); 732 EXPECT_EQ(USET("{ [1,0,0] }"), shiftDim(USET("{ [0,0,0] }"), -3, 1)); 733 734 // Parametrized 735 EXPECT_EQ(USET("[n] -> { [n+1] }"), shiftDim(USET("[n] -> { [n] }"), 0, 1)); 736 737 // Union maps 738 EXPECT_EQ(MAP("{ [1] -> [] }"), 739 shiftDim(MAP("{ [0] -> [] }"), isl::dim::in, 0, 1)); 740 EXPECT_EQ(UMAP("{ [1] -> [] }"), 741 shiftDim(UMAP("{ [0] -> [] }"), isl::dim::in, 0, 1)); 742 EXPECT_EQ(MAP("{ [] -> [1] }"), 743 shiftDim(MAP("{ [] -> [0] }"), isl::dim::out, 0, 1)); 744 EXPECT_EQ(UMAP("{ [] -> [1] }"), 745 shiftDim(UMAP("{ [] -> [0] }"), isl::dim::out, 0, 1)); 746 } 747 748 TEST(DeLICM, computeReachingWrite) { 749 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 750 &isl_ctx_free); 751 752 // Basic usage 753 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"), 754 computeReachingWrite(UMAP("{ Dom[] -> [0] }"), 755 UMAP("{ Dom[] -> Elt[] }"), false, false, 756 false)); 757 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"), 758 computeReachingWrite(UMAP("{ Dom[] -> [0] }"), 759 UMAP("{ Dom[] -> Elt[] }"), false, false, 760 true)); 761 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"), 762 computeReachingWrite(UMAP("{ Dom[] -> [0] }"), 763 UMAP("{ Dom[] -> Elt[] }"), false, true, 764 false)); 765 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"), 766 computeReachingWrite(UMAP("{ Dom[] -> [0] }"), 767 UMAP("{ Dom[] -> Elt[] }"), false, true, 768 false)); 769 770 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"), 771 computeReachingWrite(UMAP("{ Dom[] -> [0] }"), 772 UMAP("{ Dom[] -> Elt[] }"), true, false, 773 false)); 774 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"), 775 computeReachingWrite(UMAP("{ Dom[] -> [0] }"), 776 UMAP("{ Dom[] -> Elt[] }"), true, false, 777 true)); 778 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"), 779 computeReachingWrite(UMAP("{ Dom[] -> [0] }"), 780 UMAP("{ Dom[] -> Elt[] }"), true, true, 781 false)); 782 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"), 783 computeReachingWrite(UMAP("{ Dom[] -> [0] }"), 784 UMAP("{ Dom[] -> Elt[] }"), true, true, true)); 785 786 // Two writes 787 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 < i < 10; [Elt[] -> [i]] -> " 788 "Dom2[] : 10 < i }"), 789 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), 790 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), 791 false, false, false)); 792 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 <= i < 10; [Elt[] -> [i]] -> " 793 "Dom2[] : 10 <= i }"), 794 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), 795 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), 796 false, true, false)); 797 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 < i <= 10; [Elt[] -> [i]] -> " 798 "Dom2[] : 10 < i }"), 799 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), 800 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), 801 false, false, true)); 802 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 <= i <= 10; [Elt[] -> [i]] -> " 803 "Dom2[] : 10 <= i }"), 804 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), 805 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), 806 false, true, true)); 807 808 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i < 10; [Elt[] -> [i]] -> " 809 "Dom1[] : i < 0 }"), 810 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), 811 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), 812 true, false, false)); 813 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 <= i < 10; [Elt[] -> [i]] -> " 814 "Dom1[] : i < 0 }"), 815 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), 816 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), 817 true, true, false)); 818 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i <= 10; [Elt[] -> [i]] -> " 819 "Dom1[] : i <= 0 }"), 820 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), 821 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), 822 true, false, true)); 823 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 <= i <= 10; [Elt[] -> [i]] -> " 824 "Dom1[] : i <= 0 }"), 825 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), 826 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), 827 true, true, true)); 828 829 // Domain in same space 830 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[1] : 0 < i <= 10; [Elt[] -> [i]] -> " 831 "Dom[2] : 10 < i }"), 832 computeReachingWrite(UMAP("{ Dom[i] -> [10i - 10] }"), 833 UMAP("{ Dom[1] -> Elt[]; Dom[2] -> Elt[] }"), 834 false, false, true)); 835 836 // Parametric 837 EXPECT_EQ(UMAP("[p] -> { [Elt[] -> [i]] -> Dom[] : p < i }"), 838 computeReachingWrite(UMAP("[p] -> { Dom[] -> [p] }"), 839 UMAP("{ Dom[] -> Elt[] }"), false, false, 840 false)); 841 842 // More realistic example (from reduction_embedded.ll) 843 EXPECT_EQ( 844 UMAP("{ [Elt[] -> [i]] -> Dom[0] : 0 < i <= 3; [Elt[] -> [i]] -> Dom[1] " 845 ": 3 < i <= 6; [Elt[] -> [i]] -> Dom[2] : 6 < i <= 9; [Elt[] -> " 846 "[i]] -> Dom[3] : 9 < i <= 12; [Elt[] -> [i]] -> Dom[4] : 12 < i }"), 847 computeReachingWrite(UMAP("{ Dom[i] -> [3i] : 0 <= i <= 4 }"), 848 UMAP("{ Dom[i] -> Elt[] : 0 <= i <= 4 }"), false, 849 false, true)); 850 } 851 852 TEST(DeLICM, computeArrayUnused) { 853 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 854 &isl_ctx_free); 855 856 // The ReadEltInSameInst parameter doesn't matter in simple cases. To also 857 // cover the parameter without duplicating the tests, this loops runs over 858 // other in both settings. 859 for (bool ReadEltInSameInst = false, Done = false; !Done; 860 Done = ReadEltInSameInst, ReadEltInSameInst = true) { 861 // Basic usage: one read, one write 862 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i < 10 }"), 863 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"), 864 UMAP("{ Write[] -> Elt[] }"), 865 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, 866 false, false)); 867 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"), 868 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"), 869 UMAP("{ Write[] -> Elt[] }"), 870 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, 871 false, true)); 872 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 <= i < 10 }"), 873 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"), 874 UMAP("{ Write[] -> Elt[] }"), 875 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, 876 true, false)); 877 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 <= i <= 10 }"), 878 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"), 879 UMAP("{ Write[] -> Elt[] }"), 880 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, 881 true, true)); 882 883 // Two reads 884 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"), 885 computeArrayUnused( 886 UMAP("{ Read[0] -> [-10]; Read[1] -> [0]; Write[] -> [10] }"), 887 UMAP("{ Write[] -> Elt[] }"), UMAP("{ Read[i] -> Elt[] }"), 888 ReadEltInSameInst, false, true)); 889 890 // Corner case: no writes 891 EXPECT_EQ(UMAP("{}"), 892 computeArrayUnused(UMAP("{ Read[] -> [0] }"), UMAP("{}"), 893 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, 894 false, false)); 895 896 // Corner case: no reads 897 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"), 898 computeArrayUnused(UMAP("{ Write[] -> [0] }"), 899 UMAP("{ Write[] -> Elt[] }"), UMAP("{}"), 900 ReadEltInSameInst, false, true)); 901 902 // Two writes 903 EXPECT_EQ( 904 UMAP("{ Elt[] -> [i] : i <= 10 }"), 905 computeArrayUnused(UMAP("{ WriteA[] -> [0]; WriteB[] -> [10] }"), 906 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"), 907 UMAP("{}"), ReadEltInSameInst, false, true)); 908 909 // Two unused zones 910 // read,write,read,write 911 EXPECT_EQ( 912 UMAP("{ Elt[] -> [i] : 0 < i <= 10; Elt[] -> [i] : 20 < i <= 30 }"), 913 computeArrayUnused(UMAP("{ ReadA[] -> [0]; WriteA[] -> [10]; ReadB[] " 914 "-> [20]; WriteB[] -> [30] }"), 915 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"), 916 UMAP("{ ReadA[] -> Elt[]; ReadB[] -> Elt[] }"), 917 ReadEltInSameInst, false, true)); 918 919 // write, write 920 EXPECT_EQ( 921 UMAP("{ Elt[] -> [i] : i <= 10 }"), 922 computeArrayUnused( 923 UMAP("{ WriteA[] -> [0]; WriteB[] -> [10]; Read[] -> [20] }"), 924 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"), 925 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, false, true)); 926 927 // write, read 928 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"), 929 computeArrayUnused(UMAP("{ Write[] -> [0]; Read[] -> [10] }"), 930 UMAP("{ Write[] -> Elt[] }"), 931 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, 932 false, true)); 933 934 // read, write, read 935 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"), 936 computeArrayUnused( 937 UMAP("{ ReadA[] -> [0]; Write[] -> [10]; ReadB[] -> [20] }"), 938 UMAP("{ Write[] -> Elt[] }"), 939 UMAP("{ ReadA[] -> Elt[]; ReadB[] -> Elt[] }"), 940 ReadEltInSameInst, false, true)); 941 942 // read, write, write 943 EXPECT_EQ( 944 UMAP("{ Elt[] -> [i] : 0 < i <= 20 }"), 945 computeArrayUnused( 946 UMAP("{ Read[] -> [0]; WriteA[] -> [10]; WriteB[] -> [20] }"), 947 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"), 948 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, false, true)); 949 950 // read, write, write, read 951 EXPECT_EQ( 952 UMAP("{ Elt[] -> [i] : 0 < i <= 20 }"), 953 computeArrayUnused(UMAP("{ ReadA[] -> [0]; WriteA[] -> [10]; WriteB[] " 954 "-> [20]; ReadB[] -> [30] }"), 955 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"), 956 UMAP("{ ReadA[] -> Elt[]; ReadB[] -> Elt[] }"), 957 ReadEltInSameInst, false, true)); 958 } 959 960 // Read and write in same statement 961 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i < 0 }"), 962 computeArrayUnused(UMAP("{ RW[] -> [0] }"), 963 UMAP("{ RW[] -> Elt[] }"), 964 UMAP("{ RW[] -> Elt[] }"), true, false, false)); 965 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"), 966 computeArrayUnused(UMAP("{ RW[] -> [0] }"), 967 UMAP("{ RW[] -> Elt[] }"), 968 UMAP("{ RW[] -> Elt[] }"), true, false, true)); 969 EXPECT_EQ(UMAP("{ Elt[] -> [0] }"), 970 computeArrayUnused(UMAP("{ RW[] -> [0] }"), 971 UMAP("{ RW[] -> Elt[] }"), 972 UMAP("{ RW[] -> Elt[] }"), false, true, true)); 973 } 974 975 TEST(DeLICM, convertZoneToTimepoints) { 976 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 977 &isl_ctx_free); 978 979 // Corner case: empty set 980 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), false, false)); 981 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), true, false)); 982 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), false, true)); 983 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), true, true)); 984 985 // Basic usage 986 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{ [1] }"), false, false)); 987 EXPECT_EQ(USET("{ [0] }"), 988 convertZoneToTimepoints(USET("{ [1] }"), true, false)); 989 EXPECT_EQ(USET("{ [1] }"), 990 convertZoneToTimepoints(USET("{ [1] }"), false, true)); 991 EXPECT_EQ(USET("{ [0]; [1] }"), 992 convertZoneToTimepoints(USET("{ [1] }"), true, true)); 993 994 // Non-adjacent ranges 995 EXPECT_EQ(USET("{}"), 996 convertZoneToTimepoints(USET("{ [1]; [11] }"), false, false)); 997 EXPECT_EQ(USET("{ [0]; [10] }"), 998 convertZoneToTimepoints(USET("{ [1]; [11] }"), true, false)); 999 EXPECT_EQ(USET("{ [1]; [11] }"), 1000 convertZoneToTimepoints(USET("{ [1]; [11] }"), false, true)); 1001 EXPECT_EQ(USET("{ [0]; [1]; [10]; [11] }"), 1002 convertZoneToTimepoints(USET("{ [1]; [11] }"), true, true)); 1003 1004 // Adjacent unit ranges 1005 EXPECT_EQ( 1006 USET("{ [i] : 0 < i < 10 }"), 1007 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, false)); 1008 EXPECT_EQ( 1009 USET("{ [i] : 0 <= i < 10 }"), 1010 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, false)); 1011 EXPECT_EQ( 1012 USET("{ [i] : 0 < i <= 10 }"), 1013 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, true)); 1014 EXPECT_EQ(USET("{ [i] : 0 <= i <= 10 }"), 1015 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, true)); 1016 1017 // More than one dimension 1018 EXPECT_EQ(USET("{}"), 1019 convertZoneToTimepoints(USET("{ [0,1] }"), false, false)); 1020 EXPECT_EQ(USET("{ [0,0] }"), 1021 convertZoneToTimepoints(USET("{ [0,1] }"), true, false)); 1022 EXPECT_EQ(USET("{ [0,1] }"), 1023 convertZoneToTimepoints(USET("{ [0,1] }"), false, true)); 1024 EXPECT_EQ(USET("{ [0,0]; [0,1] }"), 1025 convertZoneToTimepoints(USET("{ [0,1] }"), true, true)); 1026 1027 // Map domains 1028 EXPECT_EQ(UMAP("{}"), convertZoneToTimepoints(UMAP("{ [1] -> [] }"), 1029 isl::dim::in, false, false)); 1030 EXPECT_EQ(UMAP("{ [0] -> [] }"), 1031 convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, true, 1032 false)); 1033 EXPECT_EQ(UMAP("{ [1] -> [] }"), 1034 convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, false, 1035 true)); 1036 EXPECT_EQ( 1037 UMAP("{ [0] -> []; [1] -> [] }"), 1038 convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, true, true)); 1039 1040 // Map ranges 1041 EXPECT_EQ(UMAP("{}"), convertZoneToTimepoints(UMAP("{ [] -> [1] }"), 1042 isl::dim::out, false, false)); 1043 EXPECT_EQ(UMAP("{ [] -> [0] }"), 1044 convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, true, 1045 false)); 1046 EXPECT_EQ(UMAP("{ [] -> [1] }"), 1047 convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, false, 1048 true)); 1049 EXPECT_EQ(UMAP("{ [] -> [0]; [] -> [1] }"), 1050 convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, true, 1051 true)); 1052 } 1053 1054 TEST(DeLICM, distribute) { 1055 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 1056 &isl_ctx_free); 1057 1058 // Basic usage 1059 EXPECT_EQ(MAP("{ [Domain[] -> Range1[]] -> [Domain[] -> Range2[]] }"), 1060 distributeDomain(MAP("{ Domain[] -> [Range1[] -> Range2[]] }"))); 1061 EXPECT_EQ( 1062 MAP("{ [Domain[i,j] -> Range1[i,k]] -> [Domain[i,j] -> Range2[j,k]] }"), 1063 distributeDomain(MAP("{ Domain[i,j] -> [Range1[i,k] -> Range2[j,k]] }"))); 1064 1065 // Union maps 1066 EXPECT_EQ( 1067 UMAP( 1068 "{ [DomainA[i,j] -> RangeA1[i,k]] -> [DomainA[i,j] -> RangeA2[j,k]];" 1069 "[DomainB[i,j] -> RangeB1[i,k]] -> [DomainB[i,j] -> RangeB2[j,k]] }"), 1070 distributeDomain( 1071 UMAP("{ DomainA[i,j] -> [RangeA1[i,k] -> RangeA2[j,k]];" 1072 "DomainB[i,j] -> [RangeB1[i,k] -> RangeB2[j,k]] }"))); 1073 } 1074 1075 TEST(DeLICM, lift) { 1076 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 1077 &isl_ctx_free); 1078 1079 // Basic usage 1080 EXPECT_EQ(UMAP("{ [Factor[] -> Domain[]] -> [Factor[] -> Range[]] }"), 1081 liftDomains(UMAP("{ Domain[] -> Range[] }"), USET("{ Factor[] }"))); 1082 EXPECT_EQ(UMAP("{ [Factor[l] -> Domain[i,k]] -> [Factor[l] -> Range[j,k]] }"), 1083 liftDomains(UMAP("{ Domain[i,k] -> Range[j,k] }"), 1084 USET("{ Factor[l] }"))); 1085 1086 // Multiple maps in union 1087 EXPECT_EQ( 1088 UMAP("{ [FactorA[] -> DomainA[]] -> [FactorA[] -> RangeA[]];" 1089 "[FactorB[] -> DomainA[]] -> [FactorB[] -> RangeA[]];" 1090 "[FactorA[] -> DomainB[]] -> [FactorA[] -> RangeB[]];" 1091 "[FactorB[] -> DomainB[]] -> [FactorB[] -> RangeB[]] }"), 1092 liftDomains(UMAP("{ DomainA[] -> RangeA[]; DomainB[] -> RangeB[] }"), 1093 USET("{ FactorA[]; FactorB[] }"))); 1094 } 1095 1096 TEST(DeLICM, apply) { 1097 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), 1098 &isl_ctx_free); 1099 1100 // Basic usage 1101 EXPECT_EQ( 1102 UMAP("{ [DomainDomain[] -> NewDomainRange[]] -> Range[] }"), 1103 applyDomainRange(UMAP("{ [DomainDomain[] -> DomainRange[]] -> Range[] }"), 1104 UMAP("{ DomainRange[] -> NewDomainRange[] }"))); 1105 EXPECT_EQ( 1106 UMAP("{ [DomainDomain[i,k] -> NewDomainRange[j,k,l]] -> Range[i,j] }"), 1107 applyDomainRange( 1108 UMAP("{ [DomainDomain[i,k] -> DomainRange[j,k]] -> Range[i,j] }"), 1109 UMAP("{ DomainRange[j,k] -> NewDomainRange[j,k,l] }"))); 1110 1111 // Multiple maps in union 1112 EXPECT_EQ(UMAP("{ [DomainDomainA[] -> NewDomainRangeA[]] -> RangeA[];" 1113 "[DomainDomainB[] -> NewDomainRangeB[]] -> RangeB[] }"), 1114 applyDomainRange( 1115 UMAP("{ [DomainDomainA[] -> DomainRangeA[]] -> RangeA[];" 1116 "[DomainDomainB[] -> DomainRangeB[]] -> RangeB[] }"), 1117 UMAP("{ DomainRangeA[] -> NewDomainRangeA[];" 1118 "DomainRangeB[] -> NewDomainRangeB[] }"))); 1119 } 1120 } // anonymous namespace 1121