1182 lines · cpp
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-exception6//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 16using namespace llvm;17using namespace polly;18 19static 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 43namespace isl {44inline namespace noexceptions {45 46static bool operator==(const isl::space &LHS, const isl::space &RHS) {47 return bool(LHS.is_equal(RHS));48}49 50static bool operator==(const isl::set &LHS, const isl::set &RHS) {51 return bool(LHS.is_equal(RHS));52}53 54static bool operator==(const isl::map &LHS, const isl::map &RHS) {55 return bool(LHS.is_equal(RHS));56}57 58static bool operator==(const isl::union_set &LHS, const isl::union_set &RHS) {59 return bool(LHS.is_equal(RHS));60}61 62static bool operator==(const isl::union_map &LHS, const isl::union_map &RHS) {63 return bool(LHS.is_equal(RHS));64}65 66static bool operator==(const isl::val &LHS, const isl::val &RHS) {67 return bool(LHS.eq(RHS));68}69 70static bool operator==(const isl::pw_aff &LHS, const isl::pw_aff &RHS) {71 return bool(LHS.is_equal(RHS));72}73} // namespace noexceptions74} // namespace isl75 76namespace {77 78TEST(Isl, APIntToIslVal) {79 isl_ctx *IslCtx = isl_ctx_alloc();80 81 {82 APInt APZero(1, 0, true);83 auto IslZero = valFromAPInt(IslCtx, APZero, true);84 EXPECT_TRUE(IslZero.is_zero());85 }86 87 {88 APInt APNOne(1, -1, true);89 auto IslNOne = valFromAPInt(IslCtx, APNOne, true);90 EXPECT_TRUE(IslNOne.is_negone());91 }92 93 {94 APInt APZero(1, 0, false);95 auto IslZero = valFromAPInt(IslCtx, APZero, false);96 EXPECT_TRUE(IslZero.is_zero());97 }98 99 {100 APInt APOne(1, 1, false);101 auto IslOne = valFromAPInt(IslCtx, APOne, false);102 EXPECT_TRUE(IslOne.is_one());103 }104 105 {106 APInt APNTwo(2, -2, true);107 auto IslNTwo = valFromAPInt(IslCtx, APNTwo, true);108 auto IslNTwoCmp = isl::val(IslCtx, -2);109 EXPECT_EQ(IslNTwo, IslNTwoCmp);110 }111 112 {113 APInt APNOne(32, -1, true);114 auto IslNOne = valFromAPInt(IslCtx, APNOne, true);115 EXPECT_TRUE(IslNOne.is_negone());116 }117 118 {119 APInt APZero(32, 0, false);120 auto IslZero = valFromAPInt(IslCtx, APZero, false);121 EXPECT_TRUE(IslZero.is_zero());122 }123 124 {125 APInt APOne(32, 1, false);126 auto IslOne = valFromAPInt(IslCtx, APOne, false);127 EXPECT_TRUE(IslOne.is_one());128 }129 130 {131 APInt APTwo(32, 2, false);132 auto IslTwo = valFromAPInt(IslCtx, APTwo, false);133 EXPECT_EQ(0, IslTwo.cmp_si(2));134 }135 136 {137 APInt APNOne(32, (1ull << 32) - 1, false);138 auto IslNOne = valFromAPInt(IslCtx, APNOne, false);139 auto IslRef = isl::val(IslCtx, 32).pow2().sub(1);140 EXPECT_EQ(IslNOne, IslRef);141 }142 143 {144 APInt APLarge(130, 2, false);145 APLarge = APLarge.shl(70);146 auto IslLarge = valFromAPInt(IslCtx, APLarge, false);147 auto IslRef = isl::val(IslCtx, 71);148 IslRef = IslRef.pow2();149 EXPECT_EQ(IslLarge, IslRef);150 }151 152 isl_ctx_free(IslCtx);153}154 155TEST(Isl, IslValToAPInt) {156 isl_ctx *IslCtx = isl_ctx_alloc();157 158 {159 auto IslNOne = isl::val(IslCtx, -1);160 auto APNOne = APIntFromVal(IslNOne);161 // Compare with the two's complement of -1 in a 1-bit integer.162 EXPECT_EQ(1, APNOne);163 EXPECT_EQ(1u, APNOne.getBitWidth());164 }165 166 {167 auto IslNTwo = isl::val(IslCtx, -2);168 auto APNTwo = APIntFromVal(IslNTwo);169 // Compare with the two's complement of -2 in a 2-bit integer.170 EXPECT_EQ(2, APNTwo);171 EXPECT_EQ(2u, APNTwo.getBitWidth());172 }173 174 {175 auto IslNThree = isl::val(IslCtx, -3);176 auto APNThree = APIntFromVal(IslNThree);177 // Compare with the two's complement of -3 in a 3-bit integer.178 EXPECT_EQ(5, APNThree);179 EXPECT_EQ(3u, APNThree.getBitWidth());180 }181 182 {183 auto IslNFour = isl::val(IslCtx, -4);184 auto APNFour = APIntFromVal(IslNFour);185 // Compare with the two's complement of -4 in a 3-bit integer.186 EXPECT_EQ(4, APNFour);187 EXPECT_EQ(3u, APNFour.getBitWidth());188 }189 190 {191 auto IslZero = isl::val(IslCtx, 0);192 auto APZero = APIntFromVal(IslZero);193 EXPECT_EQ(0, APZero);194 EXPECT_EQ(1u, APZero.getBitWidth());195 }196 197 {198 auto IslOne = isl::val(IslCtx, 1);199 auto APOne = APIntFromVal(IslOne);200 EXPECT_EQ(1, APOne);201 EXPECT_EQ(2u, APOne.getBitWidth());202 }203 204 {205 auto IslTwo = isl::val(IslCtx, 2);206 auto APTwo = APIntFromVal(IslTwo);207 EXPECT_EQ(2, APTwo);208 EXPECT_EQ(3u, APTwo.getBitWidth());209 }210 211 {212 auto IslThree = isl::val(IslCtx, 3);213 auto APThree = APIntFromVal(IslThree);214 EXPECT_EQ(3, APThree);215 EXPECT_EQ(3u, APThree.getBitWidth());216 }217 218 {219 auto IslFour = isl::val(IslCtx, 4);220 auto APFour = APIntFromVal(IslFour);221 EXPECT_EQ(4, APFour);222 EXPECT_EQ(4u, APFour.getBitWidth());223 }224 225 {226 auto IslNOne = isl::val(IslCtx, 32).pow2().sub(1);227 auto APNOne = APIntFromVal(IslNOne);228 EXPECT_EQ((1ull << 32) - 1, APNOne);229 EXPECT_EQ(33u, APNOne.getBitWidth());230 }231 232 {233 auto IslLargeNum = isl::val(IslCtx, 60);234 IslLargeNum = IslLargeNum.pow2();235 IslLargeNum = IslLargeNum.sub(1);236 auto APLargeNum = APIntFromVal(IslLargeNum);237 EXPECT_EQ((1ull << 60) - 1, APLargeNum);238 EXPECT_EQ(61u, APLargeNum.getBitWidth());239 }240 241 {242 auto IslExp = isl::val(IslCtx, 500);243 auto IslLargePow2 = IslExp.pow2();244 auto APLargePow2 = APIntFromVal(IslLargePow2);245 EXPECT_TRUE(APLargePow2.isPowerOf2());246 EXPECT_EQ(502u, APLargePow2.getBitWidth());247 EXPECT_EQ(502u, APLargePow2.getSignificantBits());248 }249 250 {251 auto IslExp = isl::val(IslCtx, 500);252 auto IslLargeNPow2 = IslExp.pow2().neg();253 auto APLargeNPow2 = APIntFromVal(IslLargeNPow2);254 EXPECT_EQ(501u, APLargeNPow2.getBitWidth());255 EXPECT_EQ(501u, APLargeNPow2.getSignificantBits());256 EXPECT_EQ(500, (-APLargeNPow2).exactLogBase2());257 }258 259 {260 auto IslExp = isl::val(IslCtx, 512);261 auto IslLargePow2 = IslExp.pow2();262 auto APLargePow2 = APIntFromVal(IslLargePow2);263 EXPECT_TRUE(APLargePow2.isPowerOf2());264 EXPECT_EQ(514u, APLargePow2.getBitWidth());265 EXPECT_EQ(514u, APLargePow2.getSignificantBits());266 }267 268 {269 auto IslExp = isl::val(IslCtx, 512);270 auto IslLargeNPow2 = IslExp.pow2().neg();271 auto APLargeNPow2 = APIntFromVal(IslLargeNPow2);272 EXPECT_EQ(513u, APLargeNPow2.getBitWidth());273 EXPECT_EQ(513u, APLargeNPow2.getSignificantBits());274 EXPECT_EQ(512, (-APLargeNPow2).exactLogBase2());275 }276 277 isl_ctx_free(IslCtx);278}279 280TEST(Isl, Operators) {281 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> IslCtx(isl_ctx_alloc(),282 &isl_ctx_free);283 284 isl::val ValOne = isl::val(IslCtx.get(), 1);285 isl::val ValTwo = isl::val(IslCtx.get(), 2);286 isl::val ValThree = isl::val(IslCtx.get(), 3);287 isl::val ValFour = isl::val(IslCtx.get(), 4);288 isl::val ValNegOne = isl::val(IslCtx.get(), -1);289 isl::val ValNegTwo = isl::val(IslCtx.get(), -2);290 isl::val ValNegThree = isl::val(IslCtx.get(), -3);291 isl::val ValNegFour = isl::val(IslCtx.get(), -4);292 293 isl::space Space = isl::space(IslCtx.get(), 0, 0);294 isl::local_space LS = isl::local_space(Space);295 296 isl::pw_aff AffOne = isl::aff(LS, ValOne);297 isl::pw_aff AffTwo = isl::aff(LS, ValTwo);298 isl::pw_aff AffThree = isl::aff(LS, ValThree);299 isl::pw_aff AffFour = isl::aff(LS, ValFour);300 isl::pw_aff AffNegOne = isl::aff(LS, ValNegOne);301 isl::pw_aff AffNegTwo = isl::aff(LS, ValNegTwo);302 isl::pw_aff AffNegThree = isl::aff(LS, ValNegThree);303 isl::pw_aff AffNegFour = isl::aff(LS, ValNegFour);304 305 // Addition306 {307 EXPECT_EQ(AffOne + AffOne, AffTwo);308 EXPECT_EQ(AffOne + 1, AffTwo);309 EXPECT_EQ(1 + AffOne, AffTwo);310 EXPECT_EQ(AffOne + ValOne, AffTwo);311 EXPECT_EQ(ValOne + AffOne, AffTwo);312 }313 314 // Multiplication315 {316 EXPECT_EQ(AffTwo * AffTwo, AffFour);317 EXPECT_EQ(AffTwo * 2, AffFour);318 EXPECT_EQ(2 * AffTwo, AffFour);319 EXPECT_EQ(AffTwo * ValTwo, AffFour);320 EXPECT_EQ(ValTwo * AffTwo, AffFour);321 }322 323 // Subtraction324 {325 EXPECT_EQ(AffTwo - AffOne, AffOne);326 EXPECT_EQ(AffTwo - 1, AffOne);327 EXPECT_EQ(2 - AffOne, AffOne);328 EXPECT_EQ(AffTwo - ValOne, AffOne);329 EXPECT_EQ(ValTwo - AffOne, AffOne);330 }331 332 // Division333 {334 EXPECT_EQ(AffFour / AffTwo, AffTwo);335 EXPECT_EQ(AffFour / 2, AffTwo);336 EXPECT_EQ(4 / AffTwo, AffTwo);337 EXPECT_EQ(AffFour / ValTwo, AffTwo);338 EXPECT_EQ(AffFour / 2, AffTwo);339 340 // Dividend is negative (should be rounded towards zero)341 EXPECT_EQ(AffNegFour / AffThree, AffNegOne);342 EXPECT_EQ(AffNegFour / 3, AffNegOne);343 EXPECT_EQ((-4) / AffThree, AffNegOne);344 EXPECT_EQ(AffNegFour / ValThree, AffNegOne);345 EXPECT_EQ(AffNegFour / 3, AffNegOne);346 347 // Divisor is negative (should be rounded towards zero)348 EXPECT_EQ(AffFour / AffNegThree, AffNegOne);349 EXPECT_EQ(AffFour / -3, AffNegOne);350 EXPECT_EQ(4 / AffNegThree, AffNegOne);351 EXPECT_EQ(AffFour / ValNegThree, AffNegOne);352 EXPECT_EQ(AffFour / -3, AffNegOne);353 }354 355 // Remainder356 {357 EXPECT_EQ(AffThree % AffTwo, AffOne);358 EXPECT_EQ(AffThree % 2, AffOne);359 EXPECT_EQ(3 % AffTwo, AffOne);360 EXPECT_EQ(AffThree % ValTwo, AffOne);361 EXPECT_EQ(ValThree % AffTwo, AffOne);362 363 // Dividend is negative (should be rounded towards zero)364 EXPECT_EQ(AffNegFour % AffThree, AffNegOne);365 EXPECT_EQ(AffNegFour % 3, AffNegOne);366 EXPECT_EQ((-4) % AffThree, AffNegOne);367 EXPECT_EQ(AffNegFour % ValThree, AffNegOne);368 EXPECT_EQ(AffNegFour % 3, AffNegOne);369 370 // Divisor is negative (should be rounded towards zero)371 EXPECT_EQ(AffFour % AffNegThree, AffOne);372 EXPECT_EQ(AffFour % -3, AffOne);373 EXPECT_EQ(4 % AffNegThree, AffOne);374 EXPECT_EQ(AffFour % ValNegThree, AffOne);375 EXPECT_EQ(AffFour % -3, AffOne);376 }377}378 379TEST(Isl, Foreach) {380 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),381 &isl_ctx_free);382 383 isl::map TestMap{Ctx.get(), "{ [2] -> [7]; [5] -> [7] }"};384 isl::union_map TestUMap{Ctx.get(), "{ A[i] -> [7]; B[i] -> [7] }"};385 386 isl::set TestSet{Ctx.get(), "{ [0,7]; [i,7]: i >= 2 }"};387 isl::union_set TestUSet{Ctx.get(), "{ A[0,7]; B[i,7] }"};388 389 isl::set Seven{Ctx.get(), "{ [7] }"};390 391 {392 auto NumBMaps = 0;393 isl::stat Stat =394 TestMap.foreach_basic_map([&](isl::basic_map BMap) -> isl::stat {395 EXPECT_EQ(BMap.range(), Seven);396 NumBMaps++;397 return isl::stat::ok();398 });399 400 EXPECT_TRUE(Stat.is_ok());401 EXPECT_EQ(2, NumBMaps);402 }403 404 {405 auto NumBSets = 0;406 isl::stat Stat =407 TestSet.foreach_basic_set([&](isl::basic_set BSet) -> isl::stat {408 EXPECT_EQ(BSet.project_out(isl::dim::set, 0, 1), Seven);409 NumBSets++;410 return isl::stat::ok();411 });412 EXPECT_TRUE(Stat.is_ok());413 EXPECT_EQ(2, NumBSets);414 }415 416 {417 auto NumMaps = 0;418 isl::stat Stat = TestUMap.foreach_map([&](isl::map Map) -> isl::stat {419 EXPECT_EQ(Map.range(), Seven);420 NumMaps++;421 return isl::stat::ok();422 });423 EXPECT_TRUE(Stat.is_ok());424 EXPECT_EQ(2, NumMaps);425 }426 427 {428 auto NumSets = 0;429 isl::stat Stat = TestUSet.foreach_set([&](isl::set Set) -> isl::stat {430 EXPECT_EQ(Set.project_out(isl::dim::set, 0, 1), Seven);431 NumSets++;432 return isl::stat::ok();433 });434 EXPECT_TRUE(Stat.is_ok());435 EXPECT_EQ(2, NumSets);436 }437 438 {439 auto UPwAff = isl::union_pw_aff(TestUSet, isl::val::zero(Ctx.get()));440 auto NumPwAffs = 0;441 isl::stat Stat = UPwAff.foreach_pw_aff([&](isl::pw_aff PwAff) -> isl::stat {442 EXPECT_TRUE(PwAff.is_cst());443 NumPwAffs++;444 return isl::stat::ok();445 });446 EXPECT_TRUE(Stat.is_ok());447 EXPECT_EQ(2, NumPwAffs);448 }449 450 {451 auto NumBMaps = 0;452 EXPECT_TRUE(TestMap453 .foreach_basic_map([&](isl::basic_map BMap) -> isl::stat {454 EXPECT_EQ(BMap.range(), Seven);455 NumBMaps++;456 return isl::stat::error();457 })458 .is_error());459 EXPECT_EQ(1, NumBMaps);460 }461 462 {463 auto NumMaps = 0;464 EXPECT_TRUE(TestUMap465 .foreach_map([&](isl::map Map) -> isl::stat {466 EXPECT_EQ(Map.range(), Seven);467 NumMaps++;468 return isl::stat::error();469 })470 .is_error());471 EXPECT_EQ(1, NumMaps);472 }473 474 {475 auto TestPwAff = isl::pw_aff(TestSet, isl::val::zero(Ctx.get()));476 auto NumPieces = 0;477 isl::stat Stat = TestPwAff.foreach_piece(478 [&](isl::set Domain, isl::aff Aff) -> isl::stat {479 EXPECT_EQ(Domain, TestSet);480 EXPECT_TRUE(Aff.is_cst());481 NumPieces++;482 return isl::stat::error();483 });484 EXPECT_TRUE(Stat.is_error());485 EXPECT_EQ(1, NumPieces);486 }487}488 489TEST(ISLTools, beforeScatter) {490 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),491 &isl_ctx_free);492 493 // Basic usage with isl_map494 EXPECT_EQ(MAP("{ [] -> [i] : i <= 0 }"),495 beforeScatter(MAP("{ [] -> [0] }"), false));496 EXPECT_EQ(MAP("{ [] -> [i] : i < 0 }"),497 beforeScatter(MAP("{ [] -> [0] }"), true));498 499 // Basic usage with isl_union_map500 EXPECT_EQ(UMAP("{ A[] -> [i] : i <= 0; B[] -> [i] : i <= 0 }"),501 beforeScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), false));502 EXPECT_EQ(UMAP("{ A[] -> [i] : i < 0; B[] -> [i] : i < 0 }"),503 beforeScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), true));504 505 // More than one dimension506 EXPECT_EQ(UMAP("{ [] -> [i, j] : i < 0; [] -> [i, j] : i = 0 and j <= 0 }"),507 beforeScatter(UMAP("{ [] -> [0, 0] }"), false));508 EXPECT_EQ(UMAP("{ [] -> [i, j] : i < 0; [] -> [i, j] : i = 0 and j < 0 }"),509 beforeScatter(UMAP("{ [] -> [0, 0] }"), true));510 511 // Functional512 EXPECT_EQ(UMAP("{ [i] -> [j] : j <= i }"),513 beforeScatter(UMAP("{ [i] -> [i] }"), false));514 EXPECT_EQ(UMAP("{ [i] -> [j] : j < i }"),515 beforeScatter(UMAP("{ [i] -> [i] }"), true));516 517 // Parametrized518 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j <= i }"),519 beforeScatter(UMAP("[i] -> { [] -> [i] }"), false));520 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j < i }"),521 beforeScatter(UMAP("[i] -> { [] -> [i] }"), true));522 523 // More than one range524 EXPECT_EQ(UMAP("{ [] -> [i] : i <= 10 }"),525 beforeScatter(UMAP("{ [] -> [0]; [] -> [10] }"), false));526 EXPECT_EQ(UMAP("{ [] -> [i] : i < 10 }"),527 beforeScatter(UMAP("{ [] -> [0]; [] -> [10] }"), true));528 529 // Edge case: empty530 EXPECT_EQ(UMAP("{ [] -> [i] : 1 = 0 }"),531 beforeScatter(UMAP("{ [] -> [i] : 1 = 0 }"), false));532 EXPECT_EQ(UMAP("{ [] -> [i] : 1 = 0 }"),533 beforeScatter(UMAP("{ [] -> [i] : 1 = 0 }"), true));534}535 536TEST(ISLTools, afterScatter) {537 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),538 &isl_ctx_free);539 540 // Basic usage with isl_map541 EXPECT_EQ(MAP("{ [] -> [i] : i >= 0 }"),542 afterScatter(MAP("{ [] -> [0] }"), false));543 EXPECT_EQ(MAP("{ [] -> [i] : i > 0 }"),544 afterScatter(MAP("{ [] -> [0] }"), true));545 546 // Basic usage with isl_union_map547 EXPECT_EQ(UMAP("{ A[] -> [i] : i >= 0; B[] -> [i] : i >= 0 }"),548 afterScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), false));549 EXPECT_EQ(UMAP("{ A[] -> [i] : i > 0; B[] -> [i] : i > 0 }"),550 afterScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), true));551 552 // More than one dimension553 EXPECT_EQ(UMAP("{ [] -> [i, j] : i > 0; [] -> [i, j] : i = 0 and j >= 0 }"),554 afterScatter(UMAP("{ [] -> [0, 0] }"), false));555 EXPECT_EQ(UMAP("{ [] -> [i, j] : i > 0; [] -> [i, j] : i = 0 and j > 0 }"),556 afterScatter(UMAP("{ [] -> [0, 0] }"), true));557 558 // Functional559 EXPECT_EQ(UMAP("{ [i] -> [j] : j >= i }"),560 afterScatter(UMAP("{ [i] -> [i] }"), false));561 EXPECT_EQ(UMAP("{ [i] -> [j] : j > i }"),562 afterScatter(UMAP("{ [i] -> [i] }"), true));563 564 // Parametrized565 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j >= i }"),566 afterScatter(UMAP("[i] -> { [] -> [i] }"), false));567 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j > i }"),568 afterScatter(UMAP("[i] -> { [] -> [i] }"), true));569 570 // More than one range571 EXPECT_EQ(UMAP("{ [] -> [i] : i >= 0 }"),572 afterScatter(UMAP("{ [] -> [0]; [] -> [10] }"), false));573 EXPECT_EQ(UMAP("{ [] -> [i] : i > 0 }"),574 afterScatter(UMAP("{ [] -> [0]; [] -> [10] }"), true));575 576 // Edge case: empty577 EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), false));578 EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), true));579}580 581TEST(ISLTools, betweenScatter) {582 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),583 &isl_ctx_free);584 585 // Basic usage with isl_map586 EXPECT_EQ(MAP("{ [] -> [i] : 0 < i < 10 }"),587 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false,588 false));589 EXPECT_EQ(590 MAP("{ [] -> [i] : 0 <= i < 10 }"),591 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, false));592 EXPECT_EQ(593 MAP("{ [] -> [i] : 0 < i <= 10 }"),594 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false, true));595 EXPECT_EQ(596 MAP("{ [] -> [i] : 0 <= i <= 10 }"),597 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, true));598 599 // Basic usage with isl_union_map600 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 < i < 10; B[] -> [i] : 0 < i < 10 }"),601 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),602 UMAP("{ A[] -> [10]; B[] -> [10] }"), false, false));603 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 <= i < 10; B[] -> [i] : 0 <= i < 10 }"),604 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),605 UMAP("{ A[] -> [10]; B[] -> [10] }"), true, false));606 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 < i <= 10; B[] -> [i] : 0 < i <= 10 }"),607 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),608 UMAP("{ A[] -> [10]; B[] -> [10] }"), false, true));609 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 <= i <= 10; B[] -> [i] : 0 <= i <= 10 }"),610 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),611 UMAP("{ A[] -> [10]; B[] -> [10] }"), true, true));612}613 614TEST(ISLTools, singleton) {615 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),616 &isl_ctx_free);617 618 // No element found619 EXPECT_EQ(SET("{ [] : 1 = 0 }"), singleton(USET("{ }"), SPACE("{ [] }")));620 EXPECT_EQ(MAP("{ [] -> [] : 1 = 0 }"),621 singleton(UMAP("{ }"), SPACE("{ [] -> [] }")));622 623 // One element found624 EXPECT_EQ(SET("{ [] }"), singleton(USET("{ [] }"), SPACE("{ [] }")));625 EXPECT_EQ(MAP("{ [] -> [] }"),626 singleton(UMAP("{ [] -> [] }"), SPACE("{ [] -> [] }")));627 628 // Many elements found629 EXPECT_EQ(SET("{ [i] : 0 <= i < 10 }"),630 singleton(USET("{ [i] : 0 <= i < 10 }"), SPACE("{ [i] }")));631 EXPECT_EQ(632 MAP("{ [i] -> [i] : 0 <= i < 10 }"),633 singleton(UMAP("{ [i] -> [i] : 0 <= i < 10 }"), SPACE("{ [i] -> [j] }")));634 635 // Different parameters636 EXPECT_EQ(SET("[i] -> { [i] }"),637 singleton(USET("[i] -> { [i] }"), SPACE("{ [i] }")));638 EXPECT_EQ(MAP("[i] -> { [i] -> [i] }"),639 singleton(UMAP("[i] -> { [i] -> [i] }"), SPACE("{ [i] -> [j] }")));640}641 642TEST(ISLTools, getNumScatterDims) {643 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),644 &isl_ctx_free);645 646 // Basic usage647 EXPECT_EQ(0u, getNumScatterDims(UMAP("{ [] -> [] }")));648 EXPECT_EQ(1u, getNumScatterDims(UMAP("{ [] -> [i] }")));649 EXPECT_EQ(2u, getNumScatterDims(UMAP("{ [] -> [i,j] }")));650 EXPECT_EQ(3u, getNumScatterDims(UMAP("{ [] -> [i,j,k] }")));651 652 // Different scatter spaces653 EXPECT_EQ(0u, getNumScatterDims(UMAP("{ A[] -> []; [] -> []}")));654 EXPECT_EQ(1u, getNumScatterDims(UMAP("{ A[] -> []; [] -> [i] }")));655 EXPECT_EQ(2u, getNumScatterDims(UMAP("{ A[] -> [i]; [] -> [i,j] }")));656 EXPECT_EQ(3u, getNumScatterDims(UMAP("{ A[] -> [i]; [] -> [i,j,k] }")));657}658 659TEST(ISLTools, getScatterSpace) {660 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),661 &isl_ctx_free);662 663 // Basic usage664 EXPECT_EQ(SPACE("{ [] }"), getScatterSpace(UMAP("{ [] -> [] }")));665 EXPECT_EQ(SPACE("{ [i] }"), getScatterSpace(UMAP("{ [] -> [i] }")));666 EXPECT_EQ(SPACE("{ [i,j] }"), getScatterSpace(UMAP("{ [] -> [i,j] }")));667 EXPECT_EQ(SPACE("{ [i,j,k] }"), getScatterSpace(UMAP("{ [] -> [i,j,k] }")));668 669 // Different scatter spaces670 EXPECT_EQ(SPACE("{ [] }"), getScatterSpace(UMAP("{ A[] -> []; [] -> [] }")));671 EXPECT_EQ(SPACE("{ [i] }"),672 getScatterSpace(UMAP("{ A[] -> []; [] -> [i] }")));673 EXPECT_EQ(SPACE("{ [i,j] }"),674 getScatterSpace(UMAP("{ A[] -> [i]; [] -> [i,j] }")));675 EXPECT_EQ(SPACE("{ [i,j,k] }"),676 getScatterSpace(UMAP("{ A[] -> [i]; [] -> [i,j,k] }")));677}678 679TEST(ISLTools, makeIdentityMap) {680 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),681 &isl_ctx_free);682 683 // Basic usage684 EXPECT_EQ(UMAP("{ [i] -> [i] }"), makeIdentityMap(USET("{ [0] }"), false));685 EXPECT_EQ(UMAP("{ [0] -> [0] }"), makeIdentityMap(USET("{ [0] }"), true));686 687 // Multiple spaces688 EXPECT_EQ(UMAP("{ [] -> []; [i] -> [i] }"),689 makeIdentityMap(USET("{ []; [0] }"), false));690 EXPECT_EQ(UMAP("{ [] -> []; [0] -> [0] }"),691 makeIdentityMap(USET("{ []; [0] }"), true));692 693 // Edge case: empty694 EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), false));695 EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), true));696}697 698TEST(ISLTools, reverseDomain) {699 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),700 &isl_ctx_free);701 702 // Basic usage703 EXPECT_EQ(MAP("{ [B[] -> A[]] -> [] }"),704 reverseDomain(MAP("{ [A[] -> B[]] -> [] }")));705 EXPECT_EQ(UMAP("{ [B[] -> A[]] -> [] }"),706 reverseDomain(UMAP("{ [A[] -> B[]] -> [] }")));707}708 709TEST(ISLTools, shiftDim) {710 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),711 &isl_ctx_free);712 713 // Basic usage714 EXPECT_EQ(SET("{ [1] }"), shiftDim(SET("{ [0] }"), 0, 1));715 EXPECT_EQ(USET("{ [1] }"), shiftDim(USET("{ [0] }"), 0, 1));716 717 // From-end indexing718 EXPECT_EQ(USET("{ [0,0,1] }"), shiftDim(USET("{ [0,0,0] }"), -1, 1));719 EXPECT_EQ(USET("{ [0,1,0] }"), shiftDim(USET("{ [0,0,0] }"), -2, 1));720 EXPECT_EQ(USET("{ [1,0,0] }"), shiftDim(USET("{ [0,0,0] }"), -3, 1));721 722 // Parametrized723 EXPECT_EQ(USET("[n] -> { [n+1] }"), shiftDim(USET("[n] -> { [n] }"), 0, 1));724 725 // Union maps726 EXPECT_EQ(MAP("{ [1] -> [] }"),727 shiftDim(MAP("{ [0] -> [] }"), isl::dim::in, 0, 1));728 EXPECT_EQ(UMAP("{ [1] -> [] }"),729 shiftDim(UMAP("{ [0] -> [] }"), isl::dim::in, 0, 1));730 EXPECT_EQ(MAP("{ [] -> [1] }"),731 shiftDim(MAP("{ [] -> [0] }"), isl::dim::out, 0, 1));732 EXPECT_EQ(UMAP("{ [] -> [1] }"),733 shiftDim(UMAP("{ [] -> [0] }"), isl::dim::out, 0, 1));734}735 736TEST(DeLICM, computeReachingWrite) {737 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),738 &isl_ctx_free);739 740 // Basic usage741 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"),742 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),743 UMAP("{ Dom[] -> Elt[] }"), false, false,744 false));745 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"),746 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),747 UMAP("{ Dom[] -> Elt[] }"), false, false,748 true));749 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"),750 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),751 UMAP("{ Dom[] -> Elt[] }"), false, true,752 false));753 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"),754 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),755 UMAP("{ Dom[] -> Elt[] }"), false, true,756 false));757 758 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"),759 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),760 UMAP("{ Dom[] -> Elt[] }"), true, false,761 false));762 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"),763 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),764 UMAP("{ Dom[] -> Elt[] }"), true, false,765 true));766 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"),767 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),768 UMAP("{ Dom[] -> Elt[] }"), true, true,769 false));770 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"),771 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),772 UMAP("{ Dom[] -> Elt[] }"), true, true, true));773 774 // Two writes775 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 < i < 10; [Elt[] -> [i]] -> "776 "Dom2[] : 10 < i }"),777 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),778 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),779 false, false, false));780 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 <= i < 10; [Elt[] -> [i]] -> "781 "Dom2[] : 10 <= i }"),782 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),783 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),784 false, true, false));785 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 < i <= 10; [Elt[] -> [i]] -> "786 "Dom2[] : 10 < i }"),787 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),788 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),789 false, false, true));790 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 <= i <= 10; [Elt[] -> [i]] -> "791 "Dom2[] : 10 <= i }"),792 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),793 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),794 false, true, true));795 796 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i < 10; [Elt[] -> [i]] -> "797 "Dom1[] : i < 0 }"),798 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),799 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),800 true, false, false));801 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 <= i < 10; [Elt[] -> [i]] -> "802 "Dom1[] : i < 0 }"),803 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),804 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),805 true, true, false));806 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i <= 10; [Elt[] -> [i]] -> "807 "Dom1[] : i <= 0 }"),808 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),809 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),810 true, false, true));811 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 <= i <= 10; [Elt[] -> [i]] -> "812 "Dom1[] : i <= 0 }"),813 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),814 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),815 true, true, true));816 817 // Domain in same space818 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[1] : 0 < i <= 10; [Elt[] -> [i]] -> "819 "Dom[2] : 10 < i }"),820 computeReachingWrite(UMAP("{ Dom[i] -> [10i - 10] }"),821 UMAP("{ Dom[1] -> Elt[]; Dom[2] -> Elt[] }"),822 false, false, true));823 824 // Parametric825 EXPECT_EQ(UMAP("[p] -> { [Elt[] -> [i]] -> Dom[] : p < i }"),826 computeReachingWrite(UMAP("[p] -> { Dom[] -> [p] }"),827 UMAP("{ Dom[] -> Elt[] }"), false, false,828 false));829 830 // More realistic example (from reduction_embedded.ll)831 EXPECT_EQ(832 UMAP("{ [Elt[] -> [i]] -> Dom[0] : 0 < i <= 3; [Elt[] -> [i]] -> Dom[1] "833 ": 3 < i <= 6; [Elt[] -> [i]] -> Dom[2] : 6 < i <= 9; [Elt[] -> "834 "[i]] -> Dom[3] : 9 < i <= 12; [Elt[] -> [i]] -> Dom[4] : 12 < i }"),835 computeReachingWrite(UMAP("{ Dom[i] -> [3i] : 0 <= i <= 4 }"),836 UMAP("{ Dom[i] -> Elt[] : 0 <= i <= 4 }"), false,837 false, true));838}839 840TEST(DeLICM, computeArrayUnused) {841 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),842 &isl_ctx_free);843 844 // The ReadEltInSameInst parameter doesn't matter in simple cases. To also845 // cover the parameter without duplicating the tests, this loops runs over846 // other in both settings.847 for (bool ReadEltInSameInst = false, Done = false; !Done;848 Done = ReadEltInSameInst, ReadEltInSameInst = true) {849 // Basic usage: one read, one write850 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i < 10 }"),851 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),852 UMAP("{ Write[] -> Elt[] }"),853 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,854 false, false));855 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"),856 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),857 UMAP("{ Write[] -> Elt[] }"),858 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,859 false, true));860 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 <= i < 10 }"),861 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),862 UMAP("{ Write[] -> Elt[] }"),863 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,864 true, false));865 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 <= i <= 10 }"),866 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),867 UMAP("{ Write[] -> Elt[] }"),868 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,869 true, true));870 871 // Two reads872 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"),873 computeArrayUnused(874 UMAP("{ Read[0] -> [-10]; Read[1] -> [0]; Write[] -> [10] }"),875 UMAP("{ Write[] -> Elt[] }"), UMAP("{ Read[i] -> Elt[] }"),876 ReadEltInSameInst, false, true));877 878 // Corner case: no writes879 EXPECT_EQ(UMAP("{}"),880 computeArrayUnused(UMAP("{ Read[] -> [0] }"), UMAP("{}"),881 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,882 false, false));883 884 // Corner case: no reads885 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"),886 computeArrayUnused(UMAP("{ Write[] -> [0] }"),887 UMAP("{ Write[] -> Elt[] }"), UMAP("{}"),888 ReadEltInSameInst, false, true));889 890 // Two writes891 EXPECT_EQ(892 UMAP("{ Elt[] -> [i] : i <= 10 }"),893 computeArrayUnused(UMAP("{ WriteA[] -> [0]; WriteB[] -> [10] }"),894 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"),895 UMAP("{}"), ReadEltInSameInst, false, true));896 897 // Two unused zones898 // read,write,read,write899 EXPECT_EQ(900 UMAP("{ Elt[] -> [i] : 0 < i <= 10; Elt[] -> [i] : 20 < i <= 30 }"),901 computeArrayUnused(UMAP("{ ReadA[] -> [0]; WriteA[] -> [10]; ReadB[] "902 "-> [20]; WriteB[] -> [30] }"),903 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"),904 UMAP("{ ReadA[] -> Elt[]; ReadB[] -> Elt[] }"),905 ReadEltInSameInst, false, true));906 907 // write, write908 EXPECT_EQ(909 UMAP("{ Elt[] -> [i] : i <= 10 }"),910 computeArrayUnused(911 UMAP("{ WriteA[] -> [0]; WriteB[] -> [10]; Read[] -> [20] }"),912 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"),913 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, false, true));914 915 // write, read916 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"),917 computeArrayUnused(UMAP("{ Write[] -> [0]; Read[] -> [10] }"),918 UMAP("{ Write[] -> Elt[] }"),919 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,920 false, true));921 922 // read, write, read923 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"),924 computeArrayUnused(925 UMAP("{ ReadA[] -> [0]; Write[] -> [10]; ReadB[] -> [20] }"),926 UMAP("{ Write[] -> Elt[] }"),927 UMAP("{ ReadA[] -> Elt[]; ReadB[] -> Elt[] }"),928 ReadEltInSameInst, false, true));929 930 // read, write, write931 EXPECT_EQ(932 UMAP("{ Elt[] -> [i] : 0 < i <= 20 }"),933 computeArrayUnused(934 UMAP("{ Read[] -> [0]; WriteA[] -> [10]; WriteB[] -> [20] }"),935 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"),936 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, false, true));937 938 // read, write, write, read939 EXPECT_EQ(940 UMAP("{ Elt[] -> [i] : 0 < i <= 20 }"),941 computeArrayUnused(UMAP("{ ReadA[] -> [0]; WriteA[] -> [10]; WriteB[] "942 "-> [20]; ReadB[] -> [30] }"),943 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"),944 UMAP("{ ReadA[] -> Elt[]; ReadB[] -> Elt[] }"),945 ReadEltInSameInst, false, true));946 }947 948 // Read and write in same statement949 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i < 0 }"),950 computeArrayUnused(UMAP("{ RW[] -> [0] }"),951 UMAP("{ RW[] -> Elt[] }"),952 UMAP("{ RW[] -> Elt[] }"), true, false, false));953 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"),954 computeArrayUnused(UMAP("{ RW[] -> [0] }"),955 UMAP("{ RW[] -> Elt[] }"),956 UMAP("{ RW[] -> Elt[] }"), true, false, true));957 EXPECT_EQ(UMAP("{ Elt[] -> [0] }"),958 computeArrayUnused(UMAP("{ RW[] -> [0] }"),959 UMAP("{ RW[] -> Elt[] }"),960 UMAP("{ RW[] -> Elt[] }"), false, true, true));961}962 963TEST(DeLICM, convertZoneToTimepoints) {964 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),965 &isl_ctx_free);966 967 // Corner case: empty set968 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), false, false));969 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), true, false));970 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), false, true));971 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), true, true));972 973 // Basic usage974 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{ [1] }"), false, false));975 EXPECT_EQ(USET("{ [0] }"),976 convertZoneToTimepoints(USET("{ [1] }"), true, false));977 EXPECT_EQ(USET("{ [1] }"),978 convertZoneToTimepoints(USET("{ [1] }"), false, true));979 EXPECT_EQ(USET("{ [0]; [1] }"),980 convertZoneToTimepoints(USET("{ [1] }"), true, true));981 982 // Non-adjacent ranges983 EXPECT_EQ(USET("{}"),984 convertZoneToTimepoints(USET("{ [1]; [11] }"), false, false));985 EXPECT_EQ(USET("{ [0]; [10] }"),986 convertZoneToTimepoints(USET("{ [1]; [11] }"), true, false));987 EXPECT_EQ(USET("{ [1]; [11] }"),988 convertZoneToTimepoints(USET("{ [1]; [11] }"), false, true));989 EXPECT_EQ(USET("{ [0]; [1]; [10]; [11] }"),990 convertZoneToTimepoints(USET("{ [1]; [11] }"), true, true));991 992 // Adjacent unit ranges993 EXPECT_EQ(994 USET("{ [i] : 0 < i < 10 }"),995 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, false));996 EXPECT_EQ(997 USET("{ [i] : 0 <= i < 10 }"),998 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, false));999 EXPECT_EQ(1000 USET("{ [i] : 0 < i <= 10 }"),1001 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, true));1002 EXPECT_EQ(USET("{ [i] : 0 <= i <= 10 }"),1003 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, true));1004 1005 // More than one dimension1006 EXPECT_EQ(USET("{}"),1007 convertZoneToTimepoints(USET("{ [0,1] }"), false, false));1008 EXPECT_EQ(USET("{ [0,0] }"),1009 convertZoneToTimepoints(USET("{ [0,1] }"), true, false));1010 EXPECT_EQ(USET("{ [0,1] }"),1011 convertZoneToTimepoints(USET("{ [0,1] }"), false, true));1012 EXPECT_EQ(USET("{ [0,0]; [0,1] }"),1013 convertZoneToTimepoints(USET("{ [0,1] }"), true, true));1014 1015 // Map domains1016 EXPECT_EQ(UMAP("{}"), convertZoneToTimepoints(UMAP("{ [1] -> [] }"),1017 isl::dim::in, false, false));1018 EXPECT_EQ(UMAP("{ [0] -> [] }"),1019 convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, true,1020 false));1021 EXPECT_EQ(UMAP("{ [1] -> [] }"),1022 convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, false,1023 true));1024 EXPECT_EQ(1025 UMAP("{ [0] -> []; [1] -> [] }"),1026 convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, true, true));1027 1028 // Map ranges1029 EXPECT_EQ(UMAP("{}"), convertZoneToTimepoints(UMAP("{ [] -> [1] }"),1030 isl::dim::out, false, false));1031 EXPECT_EQ(UMAP("{ [] -> [0] }"),1032 convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, true,1033 false));1034 EXPECT_EQ(UMAP("{ [] -> [1] }"),1035 convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, false,1036 true));1037 EXPECT_EQ(UMAP("{ [] -> [0]; [] -> [1] }"),1038 convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, true,1039 true));1040}1041 1042TEST(DeLICM, distribute) {1043 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),1044 &isl_ctx_free);1045 1046 // Basic usage1047 EXPECT_EQ(MAP("{ [Domain[] -> Range1[]] -> [Domain[] -> Range2[]] }"),1048 distributeDomain(MAP("{ Domain[] -> [Range1[] -> Range2[]] }")));1049 EXPECT_EQ(1050 MAP("{ [Domain[i,j] -> Range1[i,k]] -> [Domain[i,j] -> Range2[j,k]] }"),1051 distributeDomain(MAP("{ Domain[i,j] -> [Range1[i,k] -> Range2[j,k]] }")));1052 1053 // Union maps1054 EXPECT_EQ(1055 UMAP(1056 "{ [DomainA[i,j] -> RangeA1[i,k]] -> [DomainA[i,j] -> RangeA2[j,k]];"1057 "[DomainB[i,j] -> RangeB1[i,k]] -> [DomainB[i,j] -> RangeB2[j,k]] }"),1058 distributeDomain(1059 UMAP("{ DomainA[i,j] -> [RangeA1[i,k] -> RangeA2[j,k]];"1060 "DomainB[i,j] -> [RangeB1[i,k] -> RangeB2[j,k]] }")));1061}1062 1063TEST(DeLICM, lift) {1064 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),1065 &isl_ctx_free);1066 1067 // Basic usage1068 EXPECT_EQ(UMAP("{ [Factor[] -> Domain[]] -> [Factor[] -> Range[]] }"),1069 liftDomains(UMAP("{ Domain[] -> Range[] }"), USET("{ Factor[] }")));1070 EXPECT_EQ(UMAP("{ [Factor[l] -> Domain[i,k]] -> [Factor[l] -> Range[j,k]] }"),1071 liftDomains(UMAP("{ Domain[i,k] -> Range[j,k] }"),1072 USET("{ Factor[l] }")));1073 1074 // Multiple maps in union1075 EXPECT_EQ(1076 UMAP("{ [FactorA[] -> DomainA[]] -> [FactorA[] -> RangeA[]];"1077 "[FactorB[] -> DomainA[]] -> [FactorB[] -> RangeA[]];"1078 "[FactorA[] -> DomainB[]] -> [FactorA[] -> RangeB[]];"1079 "[FactorB[] -> DomainB[]] -> [FactorB[] -> RangeB[]] }"),1080 liftDomains(UMAP("{ DomainA[] -> RangeA[]; DomainB[] -> RangeB[] }"),1081 USET("{ FactorA[]; FactorB[] }")));1082}1083 1084TEST(DeLICM, apply) {1085 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),1086 &isl_ctx_free);1087 1088 // Basic usage1089 EXPECT_EQ(1090 UMAP("{ [DomainDomain[] -> NewDomainRange[]] -> Range[] }"),1091 applyDomainRange(UMAP("{ [DomainDomain[] -> DomainRange[]] -> Range[] }"),1092 UMAP("{ DomainRange[] -> NewDomainRange[] }")));1093 EXPECT_EQ(1094 UMAP("{ [DomainDomain[i,k] -> NewDomainRange[j,k,l]] -> Range[i,j] }"),1095 applyDomainRange(1096 UMAP("{ [DomainDomain[i,k] -> DomainRange[j,k]] -> Range[i,j] }"),1097 UMAP("{ DomainRange[j,k] -> NewDomainRange[j,k,l] }")));1098 1099 // Multiple maps in union1100 EXPECT_EQ(UMAP("{ [DomainDomainA[] -> NewDomainRangeA[]] -> RangeA[];"1101 "[DomainDomainB[] -> NewDomainRangeB[]] -> RangeB[] }"),1102 applyDomainRange(1103 UMAP("{ [DomainDomainA[] -> DomainRangeA[]] -> RangeA[];"1104 "[DomainDomainB[] -> DomainRangeB[]] -> RangeB[] }"),1105 UMAP("{ DomainRangeA[] -> NewDomainRangeA[];"1106 "DomainRangeB[] -> NewDomainRangeB[] }")));1107}1108 1109TEST(Isl, Quota) {1110 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),1111 &isl_ctx_free);1112 1113 isl::set TestSet1{Ctx.get(), "{ [0] }"};1114 isl::set TestSet2{Ctx.get(), "{ [i] : i > 0 }"};1115 1116 {1117 IslMaxOperationsGuard MaxOpGuard(Ctx.get(), 1);1118 ASSERT_EQ(isl_options_get_on_error(Ctx.get()), ISL_ON_ERROR_CONTINUE);1119 ASSERT_EQ(isl_ctx_get_max_operations(Ctx.get()), 1ul);1120 ASSERT_FALSE(MaxOpGuard.hasQuotaExceeded());1121 1122 // Intentionally exceed the quota. Each allocation will use at least one1123 // operation, guaranteed to exceed the max_operations of 1.1124 isl::id::alloc(Ctx.get(), "A", nullptr);1125 isl::id::alloc(Ctx.get(), "B", nullptr);1126 ASSERT_TRUE(MaxOpGuard.hasQuotaExceeded());1127 1128 // Check returned object after exceeded quota.1129 isl::set Union = TestSet1.unite(TestSet2);1130 EXPECT_TRUE(Union.is_null());1131 1132 // Check isl::boolean result after exceeded quota.1133 isl::boolean BoolResult = TestSet1.is_empty();1134 EXPECT_TRUE(BoolResult.is_error());1135 EXPECT_FALSE(BoolResult.is_false());1136 EXPECT_FALSE(BoolResult.is_true());1137 EXPECT_DEATH((void)(bool)BoolResult,1138 "IMPLEMENTATION ERROR: Unhandled error state");1139 EXPECT_DEATH((void)(bool)!BoolResult,1140 "IMPLEMENTATION ERROR: Unhandled error state");1141 EXPECT_DEATH(1142 {1143 if (BoolResult) {1144 }1145 },1146 "IMPLEMENTATION ERROR: Unhandled error state");1147 EXPECT_DEATH((void)(BoolResult == false),1148 "IMPLEMENTATION ERROR: Unhandled error state");1149 EXPECT_DEATH((void)(BoolResult == true),1150 "IMPLEMENTATION ERROR: Unhandled error state");1151 1152 // Check isl::stat result after exceeded quota.1153 isl::stat StatResult =1154 TestSet1.foreach_point([](isl::point) { return isl::stat::ok(); });1155 EXPECT_TRUE(StatResult.is_error());1156 EXPECT_FALSE(StatResult.is_ok());1157 }1158 ASSERT_EQ(isl_ctx_last_error(Ctx.get()), isl_error_quota);1159 ASSERT_EQ(isl_options_get_on_error(Ctx.get()), ISL_ON_ERROR_WARN);1160 ASSERT_EQ(isl_ctx_get_max_operations(Ctx.get()), 0ul);1161 1162 // Operations must work again after leaving the quota scope.1163 {1164 isl::set Union = TestSet1.unite(TestSet2);1165 EXPECT_FALSE(Union.is_null());1166 1167 isl::boolean BoolResult = TestSet1.is_empty();1168 EXPECT_FALSE(BoolResult.is_error());1169 EXPECT_TRUE(BoolResult.is_false());1170 EXPECT_FALSE(BoolResult.is_true());1171 EXPECT_FALSE(BoolResult);1172 EXPECT_TRUE(!BoolResult);1173 1174 isl::stat StatResult =1175 TestSet1.foreach_point([](isl::point) { return isl::stat::ok(); });1176 EXPECT_FALSE(StatResult.is_error());1177 EXPECT_TRUE(StatResult.is_ok());1178 }1179}1180 1181} // anonymous namespace1182