| //===- IslTest.cpp ----------------------------------------------------===// |
| // |
| // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. |
| // See https://llvm.org/LICENSE.txt for license information. |
| // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception |
| // |
| //===----------------------------------------------------------------------===// |
| |
| #include "polly/Support/GICHelper.h" |
| #include "polly/Support/ISLOperators.h" |
| #include "polly/Support/ISLTools.h" |
| #include "gtest/gtest.h" |
| #include "isl/stream.h" |
| #include "isl/val.h" |
| |
| using namespace llvm; |
| using namespace polly; |
| |
| static isl::space parseSpace(isl_ctx *Ctx, const char *Str) { |
| isl_stream *Stream = isl_stream_new_str(Ctx, Str); |
| auto Obj = isl_stream_read_obj(Stream); |
| |
| isl::space Result; |
| if (Obj.type == isl_obj_set) |
| Result = isl::manage(isl_set_get_space(static_cast<isl_set *>(Obj.v))); |
| else if (Obj.type == isl_obj_map) |
| Result = isl::manage(isl_map_get_space(static_cast<isl_map *>(Obj.v))); |
| |
| isl_stream_free(Stream); |
| if (Obj.type) |
| Obj.type->free(Obj.v); |
| return Result; |
| } |
| |
| #define SPACE(Str) parseSpace(Ctx.get(), Str) |
| |
| #define SET(Str) isl::set(Ctx.get(), Str) |
| #define MAP(Str) isl::map(Ctx.get(), Str) |
| |
| #define USET(Str) isl::union_set(Ctx.get(), Str) |
| #define UMAP(Str) isl::union_map(Ctx.get(), Str) |
| |
| namespace isl { |
| inline namespace noexceptions { |
| |
| static bool operator==(const isl::space &LHS, const isl::space &RHS) { |
| return bool(LHS.is_equal(RHS)); |
| } |
| |
| static bool operator==(const isl::set &LHS, const isl::set &RHS) { |
| return bool(LHS.is_equal(RHS)); |
| } |
| |
| static bool operator==(const isl::map &LHS, const isl::map &RHS) { |
| return bool(LHS.is_equal(RHS)); |
| } |
| |
| static bool operator==(const isl::union_set &LHS, const isl::union_set &RHS) { |
| return bool(LHS.is_equal(RHS)); |
| } |
| |
| static bool operator==(const isl::union_map &LHS, const isl::union_map &RHS) { |
| return bool(LHS.is_equal(RHS)); |
| } |
| |
| static bool operator==(const isl::val &LHS, const isl::val &RHS) { |
| return bool(LHS.eq(RHS)); |
| } |
| |
| static bool operator==(const isl::pw_aff &LHS, const isl::pw_aff &RHS) { |
| return bool(LHS.is_equal(RHS)); |
| } |
| } // namespace noexceptions |
| } // namespace isl |
| |
| namespace { |
| |
| TEST(Isl, APIntToIslVal) { |
| isl_ctx *IslCtx = isl_ctx_alloc(); |
| |
| { |
| APInt APZero(1, 0, true); |
| auto IslZero = valFromAPInt(IslCtx, APZero, true); |
| EXPECT_TRUE(IslZero.is_zero()); |
| } |
| |
| { |
| APInt APNOne(1, -1, true); |
| auto IslNOne = valFromAPInt(IslCtx, APNOne, true); |
| EXPECT_TRUE(IslNOne.is_negone()); |
| } |
| |
| { |
| APInt APZero(1, 0, false); |
| auto IslZero = valFromAPInt(IslCtx, APZero, false); |
| EXPECT_TRUE(IslZero.is_zero()); |
| } |
| |
| { |
| APInt APOne(1, 1, false); |
| auto IslOne = valFromAPInt(IslCtx, APOne, false); |
| EXPECT_TRUE(IslOne.is_one()); |
| } |
| |
| { |
| APInt APNTwo(2, -2, true); |
| auto IslNTwo = valFromAPInt(IslCtx, APNTwo, true); |
| auto IslNTwoCmp = isl::val(IslCtx, -2); |
| EXPECT_EQ(IslNTwo, IslNTwoCmp); |
| } |
| |
| { |
| APInt APNOne(32, -1, true); |
| auto IslNOne = valFromAPInt(IslCtx, APNOne, true); |
| EXPECT_TRUE(IslNOne.is_negone()); |
| } |
| |
| { |
| APInt APZero(32, 0, false); |
| auto IslZero = valFromAPInt(IslCtx, APZero, false); |
| EXPECT_TRUE(IslZero.is_zero()); |
| } |
| |
| { |
| APInt APOne(32, 1, false); |
| auto IslOne = valFromAPInt(IslCtx, APOne, false); |
| EXPECT_TRUE(IslOne.is_one()); |
| } |
| |
| { |
| APInt APTwo(32, 2, false); |
| auto IslTwo = valFromAPInt(IslCtx, APTwo, false); |
| EXPECT_EQ(0, IslTwo.cmp_si(2)); |
| } |
| |
| { |
| APInt APNOne(32, (1ull << 32) - 1, false); |
| auto IslNOne = valFromAPInt(IslCtx, APNOne, false); |
| auto IslRef = isl::val(IslCtx, 32).pow2().sub(1); |
| EXPECT_EQ(IslNOne, IslRef); |
| } |
| |
| { |
| APInt APLarge(130, 2, false); |
| APLarge = APLarge.shl(70); |
| auto IslLarge = valFromAPInt(IslCtx, APLarge, false); |
| auto IslRef = isl::val(IslCtx, 71); |
| IslRef = IslRef.pow2(); |
| EXPECT_EQ(IslLarge, IslRef); |
| } |
| |
| isl_ctx_free(IslCtx); |
| } |
| |
| TEST(Isl, IslValToAPInt) { |
| isl_ctx *IslCtx = isl_ctx_alloc(); |
| |
| { |
| auto IslNOne = isl::val(IslCtx, -1); |
| auto APNOne = APIntFromVal(IslNOne); |
| // Compare with the two's complement of -1 in a 1-bit integer. |
| EXPECT_EQ(1, APNOne); |
| EXPECT_EQ(1u, APNOne.getBitWidth()); |
| } |
| |
| { |
| auto IslNTwo = isl::val(IslCtx, -2); |
| auto APNTwo = APIntFromVal(IslNTwo); |
| // Compare with the two's complement of -2 in a 2-bit integer. |
| EXPECT_EQ(2, APNTwo); |
| EXPECT_EQ(2u, APNTwo.getBitWidth()); |
| } |
| |
| { |
| auto IslNThree = isl::val(IslCtx, -3); |
| auto APNThree = APIntFromVal(IslNThree); |
| // Compare with the two's complement of -3 in a 3-bit integer. |
| EXPECT_EQ(5, APNThree); |
| EXPECT_EQ(3u, APNThree.getBitWidth()); |
| } |
| |
| { |
| auto IslNFour = isl::val(IslCtx, -4); |
| auto APNFour = APIntFromVal(IslNFour); |
| // Compare with the two's complement of -4 in a 3-bit integer. |
| EXPECT_EQ(4, APNFour); |
| EXPECT_EQ(3u, APNFour.getBitWidth()); |
| } |
| |
| { |
| auto IslZero = isl::val(IslCtx, 0); |
| auto APZero = APIntFromVal(IslZero); |
| EXPECT_EQ(0, APZero); |
| EXPECT_EQ(1u, APZero.getBitWidth()); |
| } |
| |
| { |
| auto IslOne = isl::val(IslCtx, 1); |
| auto APOne = APIntFromVal(IslOne); |
| EXPECT_EQ(1, APOne); |
| EXPECT_EQ(2u, APOne.getBitWidth()); |
| } |
| |
| { |
| auto IslTwo = isl::val(IslCtx, 2); |
| auto APTwo = APIntFromVal(IslTwo); |
| EXPECT_EQ(2, APTwo); |
| EXPECT_EQ(3u, APTwo.getBitWidth()); |
| } |
| |
| { |
| auto IslThree = isl::val(IslCtx, 3); |
| auto APThree = APIntFromVal(IslThree); |
| EXPECT_EQ(3, APThree); |
| EXPECT_EQ(3u, APThree.getBitWidth()); |
| } |
| |
| { |
| auto IslFour = isl::val(IslCtx, 4); |
| auto APFour = APIntFromVal(IslFour); |
| EXPECT_EQ(4, APFour); |
| EXPECT_EQ(4u, APFour.getBitWidth()); |
| } |
| |
| { |
| auto IslNOne = isl::val(IslCtx, 32).pow2().sub(1); |
| auto APNOne = APIntFromVal(IslNOne); |
| EXPECT_EQ((1ull << 32) - 1, APNOne); |
| EXPECT_EQ(33u, APNOne.getBitWidth()); |
| } |
| |
| { |
| auto IslLargeNum = isl::val(IslCtx, 60); |
| IslLargeNum = IslLargeNum.pow2(); |
| IslLargeNum = IslLargeNum.sub(1); |
| auto APLargeNum = APIntFromVal(IslLargeNum); |
| EXPECT_EQ((1ull << 60) - 1, APLargeNum); |
| EXPECT_EQ(61u, APLargeNum.getBitWidth()); |
| } |
| |
| { |
| auto IslExp = isl::val(IslCtx, 500); |
| auto IslLargePow2 = IslExp.pow2(); |
| auto APLargePow2 = APIntFromVal(IslLargePow2); |
| EXPECT_TRUE(APLargePow2.isPowerOf2()); |
| EXPECT_EQ(502u, APLargePow2.getBitWidth()); |
| EXPECT_EQ(502u, APLargePow2.getMinSignedBits()); |
| } |
| |
| { |
| auto IslExp = isl::val(IslCtx, 500); |
| auto IslLargeNPow2 = IslExp.pow2().neg(); |
| auto APLargeNPow2 = APIntFromVal(IslLargeNPow2); |
| EXPECT_EQ(501u, APLargeNPow2.getBitWidth()); |
| EXPECT_EQ(501u, APLargeNPow2.getMinSignedBits()); |
| EXPECT_EQ(500, (-APLargeNPow2).exactLogBase2()); |
| } |
| |
| { |
| auto IslExp = isl::val(IslCtx, 512); |
| auto IslLargePow2 = IslExp.pow2(); |
| auto APLargePow2 = APIntFromVal(IslLargePow2); |
| EXPECT_TRUE(APLargePow2.isPowerOf2()); |
| EXPECT_EQ(514u, APLargePow2.getBitWidth()); |
| EXPECT_EQ(514u, APLargePow2.getMinSignedBits()); |
| } |
| |
| { |
| auto IslExp = isl::val(IslCtx, 512); |
| auto IslLargeNPow2 = IslExp.pow2().neg(); |
| auto APLargeNPow2 = APIntFromVal(IslLargeNPow2); |
| EXPECT_EQ(513u, APLargeNPow2.getBitWidth()); |
| EXPECT_EQ(513u, APLargeNPow2.getMinSignedBits()); |
| EXPECT_EQ(512, (-APLargeNPow2).exactLogBase2()); |
| } |
| |
| isl_ctx_free(IslCtx); |
| } |
| |
| TEST(Isl, Operators) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> IslCtx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| isl::val ValOne = isl::val(IslCtx.get(), 1); |
| isl::val ValTwo = isl::val(IslCtx.get(), 2); |
| isl::val ValThree = isl::val(IslCtx.get(), 3); |
| isl::val ValFour = isl::val(IslCtx.get(), 4); |
| isl::val ValNegOne = isl::val(IslCtx.get(), -1); |
| isl::val ValNegTwo = isl::val(IslCtx.get(), -2); |
| isl::val ValNegThree = isl::val(IslCtx.get(), -3); |
| isl::val ValNegFour = isl::val(IslCtx.get(), -4); |
| |
| isl::space Space = isl::space(IslCtx.get(), 0, 0); |
| isl::local_space LS = isl::local_space(Space); |
| |
| isl::pw_aff AffOne = isl::aff(LS, ValOne); |
| isl::pw_aff AffTwo = isl::aff(LS, ValTwo); |
| isl::pw_aff AffThree = isl::aff(LS, ValThree); |
| isl::pw_aff AffFour = isl::aff(LS, ValFour); |
| isl::pw_aff AffNegOne = isl::aff(LS, ValNegOne); |
| isl::pw_aff AffNegTwo = isl::aff(LS, ValNegTwo); |
| isl::pw_aff AffNegThree = isl::aff(LS, ValNegThree); |
| isl::pw_aff AffNegFour = isl::aff(LS, ValNegFour); |
| |
| // Addition |
| { |
| EXPECT_EQ(AffOne + AffOne, AffTwo); |
| EXPECT_EQ(AffOne + 1, AffTwo); |
| EXPECT_EQ(1 + AffOne, AffTwo); |
| EXPECT_EQ(AffOne + ValOne, AffTwo); |
| EXPECT_EQ(ValOne + AffOne, AffTwo); |
| } |
| |
| // Multiplication |
| { |
| EXPECT_EQ(AffTwo * AffTwo, AffFour); |
| EXPECT_EQ(AffTwo * 2, AffFour); |
| EXPECT_EQ(2 * AffTwo, AffFour); |
| EXPECT_EQ(AffTwo * ValTwo, AffFour); |
| EXPECT_EQ(ValTwo * AffTwo, AffFour); |
| } |
| |
| // Subtraction |
| { |
| EXPECT_EQ(AffTwo - AffOne, AffOne); |
| EXPECT_EQ(AffTwo - 1, AffOne); |
| EXPECT_EQ(2 - AffOne, AffOne); |
| EXPECT_EQ(AffTwo - ValOne, AffOne); |
| EXPECT_EQ(ValTwo - AffOne, AffOne); |
| } |
| |
| // Division |
| { |
| EXPECT_EQ(AffFour / AffTwo, AffTwo); |
| EXPECT_EQ(AffFour / 2, AffTwo); |
| EXPECT_EQ(4 / AffTwo, AffTwo); |
| EXPECT_EQ(AffFour / ValTwo, AffTwo); |
| EXPECT_EQ(AffFour / 2, AffTwo); |
| |
| // Dividend is negative (should be rounded towards zero) |
| EXPECT_EQ(AffNegFour / AffThree, AffNegOne); |
| EXPECT_EQ(AffNegFour / 3, AffNegOne); |
| EXPECT_EQ((-4) / AffThree, AffNegOne); |
| EXPECT_EQ(AffNegFour / ValThree, AffNegOne); |
| EXPECT_EQ(AffNegFour / 3, AffNegOne); |
| |
| // Divisor is negative (should be rounded towards zero) |
| EXPECT_EQ(AffFour / AffNegThree, AffNegOne); |
| EXPECT_EQ(AffFour / -3, AffNegOne); |
| EXPECT_EQ(4 / AffNegThree, AffNegOne); |
| EXPECT_EQ(AffFour / ValNegThree, AffNegOne); |
| EXPECT_EQ(AffFour / -3, AffNegOne); |
| } |
| |
| // Remainder |
| { |
| EXPECT_EQ(AffThree % AffTwo, AffOne); |
| EXPECT_EQ(AffThree % 2, AffOne); |
| EXPECT_EQ(3 % AffTwo, AffOne); |
| EXPECT_EQ(AffThree % ValTwo, AffOne); |
| EXPECT_EQ(ValThree % AffTwo, AffOne); |
| |
| // Dividend is negative (should be rounded towards zero) |
| EXPECT_EQ(AffNegFour % AffThree, AffNegOne); |
| EXPECT_EQ(AffNegFour % 3, AffNegOne); |
| EXPECT_EQ((-4) % AffThree, AffNegOne); |
| EXPECT_EQ(AffNegFour % ValThree, AffNegOne); |
| EXPECT_EQ(AffNegFour % 3, AffNegOne); |
| |
| // Divisor is negative (should be rounded towards zero) |
| EXPECT_EQ(AffFour % AffNegThree, AffOne); |
| EXPECT_EQ(AffFour % -3, AffOne); |
| EXPECT_EQ(4 % AffNegThree, AffOne); |
| EXPECT_EQ(AffFour % ValNegThree, AffOne); |
| EXPECT_EQ(AffFour % -3, AffOne); |
| } |
| } |
| |
| TEST(Isl, Foreach) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| isl::map TestMap{Ctx.get(), "{ [2] -> [7]; [5] -> [7] }"}; |
| isl::union_map TestUMap{Ctx.get(), "{ A[i] -> [7]; B[i] -> [7] }"}; |
| |
| isl::set TestSet{Ctx.get(), "{ [0,7]; [i,7]: i >= 2 }"}; |
| isl::union_set TestUSet{Ctx.get(), "{ A[0,7]; B[i,7] }"}; |
| |
| isl::set Seven{Ctx.get(), "{ [7] }"}; |
| |
| { |
| auto NumBMaps = 0; |
| isl::stat Stat = |
| TestMap.foreach_basic_map([&](isl::basic_map BMap) -> isl::stat { |
| EXPECT_EQ(BMap.range(), Seven); |
| NumBMaps++; |
| return isl::stat::ok(); |
| }); |
| |
| EXPECT_TRUE(Stat.is_ok()); |
| EXPECT_EQ(2, NumBMaps); |
| } |
| |
| { |
| auto NumBSets = 0; |
| isl::stat Stat = |
| TestSet.foreach_basic_set([&](isl::basic_set BSet) -> isl::stat { |
| EXPECT_EQ(BSet.project_out(isl::dim::set, 0, 1), Seven); |
| NumBSets++; |
| return isl::stat::ok(); |
| }); |
| EXPECT_TRUE(Stat.is_ok()); |
| EXPECT_EQ(2, NumBSets); |
| } |
| |
| { |
| auto NumMaps = 0; |
| isl::stat Stat = TestUMap.foreach_map([&](isl::map Map) -> isl::stat { |
| EXPECT_EQ(Map.range(), Seven); |
| NumMaps++; |
| return isl::stat::ok(); |
| }); |
| EXPECT_TRUE(Stat.is_ok()); |
| EXPECT_EQ(2, NumMaps); |
| } |
| |
| { |
| auto NumSets = 0; |
| isl::stat Stat = TestUSet.foreach_set([&](isl::set Set) -> isl::stat { |
| EXPECT_EQ(Set.project_out(isl::dim::set, 0, 1), Seven); |
| NumSets++; |
| return isl::stat::ok(); |
| }); |
| EXPECT_TRUE(Stat.is_ok()); |
| EXPECT_EQ(2, NumSets); |
| } |
| |
| { |
| auto UPwAff = isl::union_pw_aff(TestUSet, isl::val::zero(Ctx.get())); |
| auto NumPwAffs = 0; |
| isl::stat Stat = UPwAff.foreach_pw_aff([&](isl::pw_aff PwAff) -> isl::stat { |
| EXPECT_TRUE(PwAff.is_cst()); |
| NumPwAffs++; |
| return isl::stat::ok(); |
| }); |
| EXPECT_TRUE(Stat.is_ok()); |
| EXPECT_EQ(2, NumPwAffs); |
| } |
| |
| { |
| auto NumBMaps = 0; |
| EXPECT_TRUE(TestMap |
| .foreach_basic_map([&](isl::basic_map BMap) -> isl::stat { |
| EXPECT_EQ(BMap.range(), Seven); |
| NumBMaps++; |
| return isl::stat::error(); |
| }) |
| .is_error()); |
| EXPECT_EQ(1, NumBMaps); |
| } |
| |
| { |
| auto NumMaps = 0; |
| EXPECT_TRUE(TestUMap |
| .foreach_map([&](isl::map Map) -> isl::stat { |
| EXPECT_EQ(Map.range(), Seven); |
| NumMaps++; |
| return isl::stat::error(); |
| }) |
| .is_error()); |
| EXPECT_EQ(1, NumMaps); |
| } |
| |
| { |
| auto TestPwAff = isl::pw_aff(TestSet, isl::val::zero(Ctx.get())); |
| auto NumPieces = 0; |
| isl::stat Stat = TestPwAff.foreach_piece( |
| [&](isl::set Domain, isl::aff Aff) -> isl::stat { |
| EXPECT_EQ(Domain, TestSet); |
| EXPECT_TRUE(Aff.is_cst()); |
| NumPieces++; |
| return isl::stat::error(); |
| }); |
| EXPECT_TRUE(Stat.is_error()); |
| EXPECT_EQ(1, NumPieces); |
| } |
| } |
| |
| TEST(ISLTools, beforeScatter) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // Basic usage with isl_map |
| EXPECT_EQ(MAP("{ [] -> [i] : i <= 0 }"), |
| beforeScatter(MAP("{ [] -> [0] }"), false)); |
| EXPECT_EQ(MAP("{ [] -> [i] : i < 0 }"), |
| beforeScatter(MAP("{ [] -> [0] }"), true)); |
| |
| // Basic usage with isl_union_map |
| EXPECT_EQ(UMAP("{ A[] -> [i] : i <= 0; B[] -> [i] : i <= 0 }"), |
| beforeScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), false)); |
| EXPECT_EQ(UMAP("{ A[] -> [i] : i < 0; B[] -> [i] : i < 0 }"), |
| beforeScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), true)); |
| |
| // More than one dimension |
| EXPECT_EQ(UMAP("{ [] -> [i, j] : i < 0; [] -> [i, j] : i = 0 and j <= 0 }"), |
| beforeScatter(UMAP("{ [] -> [0, 0] }"), false)); |
| EXPECT_EQ(UMAP("{ [] -> [i, j] : i < 0; [] -> [i, j] : i = 0 and j < 0 }"), |
| beforeScatter(UMAP("{ [] -> [0, 0] }"), true)); |
| |
| // Functional |
| EXPECT_EQ(UMAP("{ [i] -> [j] : j <= i }"), |
| beforeScatter(UMAP("{ [i] -> [i] }"), false)); |
| EXPECT_EQ(UMAP("{ [i] -> [j] : j < i }"), |
| beforeScatter(UMAP("{ [i] -> [i] }"), true)); |
| |
| // Parametrized |
| EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j <= i }"), |
| beforeScatter(UMAP("[i] -> { [] -> [i] }"), false)); |
| EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j < i }"), |
| beforeScatter(UMAP("[i] -> { [] -> [i] }"), true)); |
| |
| // More than one range |
| EXPECT_EQ(UMAP("{ [] -> [i] : i <= 10 }"), |
| beforeScatter(UMAP("{ [] -> [0]; [] -> [10] }"), false)); |
| EXPECT_EQ(UMAP("{ [] -> [i] : i < 10 }"), |
| beforeScatter(UMAP("{ [] -> [0]; [] -> [10] }"), true)); |
| |
| // Edge case: empty |
| EXPECT_EQ(UMAP("{ [] -> [i] : 1 = 0 }"), |
| beforeScatter(UMAP("{ [] -> [i] : 1 = 0 }"), false)); |
| EXPECT_EQ(UMAP("{ [] -> [i] : 1 = 0 }"), |
| beforeScatter(UMAP("{ [] -> [i] : 1 = 0 }"), true)); |
| } |
| |
| TEST(ISLTools, afterScatter) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // Basic usage with isl_map |
| EXPECT_EQ(MAP("{ [] -> [i] : i >= 0 }"), |
| afterScatter(MAP("{ [] -> [0] }"), false)); |
| EXPECT_EQ(MAP("{ [] -> [i] : i > 0 }"), |
| afterScatter(MAP("{ [] -> [0] }"), true)); |
| |
| // Basic usage with isl_union_map |
| EXPECT_EQ(UMAP("{ A[] -> [i] : i >= 0; B[] -> [i] : i >= 0 }"), |
| afterScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), false)); |
| EXPECT_EQ(UMAP("{ A[] -> [i] : i > 0; B[] -> [i] : i > 0 }"), |
| afterScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), true)); |
| |
| // More than one dimension |
| EXPECT_EQ(UMAP("{ [] -> [i, j] : i > 0; [] -> [i, j] : i = 0 and j >= 0 }"), |
| afterScatter(UMAP("{ [] -> [0, 0] }"), false)); |
| EXPECT_EQ(UMAP("{ [] -> [i, j] : i > 0; [] -> [i, j] : i = 0 and j > 0 }"), |
| afterScatter(UMAP("{ [] -> [0, 0] }"), true)); |
| |
| // Functional |
| EXPECT_EQ(UMAP("{ [i] -> [j] : j >= i }"), |
| afterScatter(UMAP("{ [i] -> [i] }"), false)); |
| EXPECT_EQ(UMAP("{ [i] -> [j] : j > i }"), |
| afterScatter(UMAP("{ [i] -> [i] }"), true)); |
| |
| // Parametrized |
| EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j >= i }"), |
| afterScatter(UMAP("[i] -> { [] -> [i] }"), false)); |
| EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j > i }"), |
| afterScatter(UMAP("[i] -> { [] -> [i] }"), true)); |
| |
| // More than one range |
| EXPECT_EQ(UMAP("{ [] -> [i] : i >= 0 }"), |
| afterScatter(UMAP("{ [] -> [0]; [] -> [10] }"), false)); |
| EXPECT_EQ(UMAP("{ [] -> [i] : i > 0 }"), |
| afterScatter(UMAP("{ [] -> [0]; [] -> [10] }"), true)); |
| |
| // Edge case: empty |
| EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), false)); |
| EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), true)); |
| } |
| |
| TEST(ISLTools, betweenScatter) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // Basic usage with isl_map |
| EXPECT_EQ(MAP("{ [] -> [i] : 0 < i < 10 }"), |
| betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false, |
| false)); |
| EXPECT_EQ( |
| MAP("{ [] -> [i] : 0 <= i < 10 }"), |
| betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, false)); |
| EXPECT_EQ( |
| MAP("{ [] -> [i] : 0 < i <= 10 }"), |
| betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false, true)); |
| EXPECT_EQ( |
| MAP("{ [] -> [i] : 0 <= i <= 10 }"), |
| betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, true)); |
| |
| // Basic usage with isl_union_map |
| EXPECT_EQ(UMAP("{ A[] -> [i] : 0 < i < 10; B[] -> [i] : 0 < i < 10 }"), |
| betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), |
| UMAP("{ A[] -> [10]; B[] -> [10] }"), false, false)); |
| EXPECT_EQ(UMAP("{ A[] -> [i] : 0 <= i < 10; B[] -> [i] : 0 <= i < 10 }"), |
| betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), |
| UMAP("{ A[] -> [10]; B[] -> [10] }"), true, false)); |
| EXPECT_EQ(UMAP("{ A[] -> [i] : 0 < i <= 10; B[] -> [i] : 0 < i <= 10 }"), |
| betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), |
| UMAP("{ A[] -> [10]; B[] -> [10] }"), false, true)); |
| EXPECT_EQ(UMAP("{ A[] -> [i] : 0 <= i <= 10; B[] -> [i] : 0 <= i <= 10 }"), |
| betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), |
| UMAP("{ A[] -> [10]; B[] -> [10] }"), true, true)); |
| } |
| |
| TEST(ISLTools, singleton) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // No element found |
| EXPECT_EQ(SET("{ [] : 1 = 0 }"), singleton(USET("{ }"), SPACE("{ [] }"))); |
| EXPECT_EQ(MAP("{ [] -> [] : 1 = 0 }"), |
| singleton(UMAP("{ }"), SPACE("{ [] -> [] }"))); |
| |
| // One element found |
| EXPECT_EQ(SET("{ [] }"), singleton(USET("{ [] }"), SPACE("{ [] }"))); |
| EXPECT_EQ(MAP("{ [] -> [] }"), |
| singleton(UMAP("{ [] -> [] }"), SPACE("{ [] -> [] }"))); |
| |
| // Many elements found |
| EXPECT_EQ(SET("{ [i] : 0 <= i < 10 }"), |
| singleton(USET("{ [i] : 0 <= i < 10 }"), SPACE("{ [i] }"))); |
| EXPECT_EQ( |
| MAP("{ [i] -> [i] : 0 <= i < 10 }"), |
| singleton(UMAP("{ [i] -> [i] : 0 <= i < 10 }"), SPACE("{ [i] -> [j] }"))); |
| |
| // Different parameters |
| EXPECT_EQ(SET("[i] -> { [i] }"), |
| singleton(USET("[i] -> { [i] }"), SPACE("{ [i] }"))); |
| EXPECT_EQ(MAP("[i] -> { [i] -> [i] }"), |
| singleton(UMAP("[i] -> { [i] -> [i] }"), SPACE("{ [i] -> [j] }"))); |
| } |
| |
| TEST(ISLTools, getNumScatterDims) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // Basic usage |
| EXPECT_EQ(0u, getNumScatterDims(UMAP("{ [] -> [] }"))); |
| EXPECT_EQ(1u, getNumScatterDims(UMAP("{ [] -> [i] }"))); |
| EXPECT_EQ(2u, getNumScatterDims(UMAP("{ [] -> [i,j] }"))); |
| EXPECT_EQ(3u, getNumScatterDims(UMAP("{ [] -> [i,j,k] }"))); |
| |
| // Different scatter spaces |
| EXPECT_EQ(0u, getNumScatterDims(UMAP("{ A[] -> []; [] -> []}"))); |
| EXPECT_EQ(1u, getNumScatterDims(UMAP("{ A[] -> []; [] -> [i] }"))); |
| EXPECT_EQ(2u, getNumScatterDims(UMAP("{ A[] -> [i]; [] -> [i,j] }"))); |
| EXPECT_EQ(3u, getNumScatterDims(UMAP("{ A[] -> [i]; [] -> [i,j,k] }"))); |
| } |
| |
| TEST(ISLTools, getScatterSpace) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // Basic usage |
| EXPECT_EQ(SPACE("{ [] }"), getScatterSpace(UMAP("{ [] -> [] }"))); |
| EXPECT_EQ(SPACE("{ [i] }"), getScatterSpace(UMAP("{ [] -> [i] }"))); |
| EXPECT_EQ(SPACE("{ [i,j] }"), getScatterSpace(UMAP("{ [] -> [i,j] }"))); |
| EXPECT_EQ(SPACE("{ [i,j,k] }"), getScatterSpace(UMAP("{ [] -> [i,j,k] }"))); |
| |
| // Different scatter spaces |
| EXPECT_EQ(SPACE("{ [] }"), getScatterSpace(UMAP("{ A[] -> []; [] -> [] }"))); |
| EXPECT_EQ(SPACE("{ [i] }"), |
| getScatterSpace(UMAP("{ A[] -> []; [] -> [i] }"))); |
| EXPECT_EQ(SPACE("{ [i,j] }"), |
| getScatterSpace(UMAP("{ A[] -> [i]; [] -> [i,j] }"))); |
| EXPECT_EQ(SPACE("{ [i,j,k] }"), |
| getScatterSpace(UMAP("{ A[] -> [i]; [] -> [i,j,k] }"))); |
| } |
| |
| TEST(ISLTools, makeIdentityMap) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // Basic usage |
| EXPECT_EQ(UMAP("{ [i] -> [i] }"), makeIdentityMap(USET("{ [0] }"), false)); |
| EXPECT_EQ(UMAP("{ [0] -> [0] }"), makeIdentityMap(USET("{ [0] }"), true)); |
| |
| // Multiple spaces |
| EXPECT_EQ(UMAP("{ [] -> []; [i] -> [i] }"), |
| makeIdentityMap(USET("{ []; [0] }"), false)); |
| EXPECT_EQ(UMAP("{ [] -> []; [0] -> [0] }"), |
| makeIdentityMap(USET("{ []; [0] }"), true)); |
| |
| // Edge case: empty |
| EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), false)); |
| EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), true)); |
| } |
| |
| TEST(ISLTools, reverseDomain) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // Basic usage |
| EXPECT_EQ(MAP("{ [B[] -> A[]] -> [] }"), |
| reverseDomain(MAP("{ [A[] -> B[]] -> [] }"))); |
| EXPECT_EQ(UMAP("{ [B[] -> A[]] -> [] }"), |
| reverseDomain(UMAP("{ [A[] -> B[]] -> [] }"))); |
| } |
| |
| TEST(ISLTools, shiftDim) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // Basic usage |
| EXPECT_EQ(SET("{ [1] }"), shiftDim(SET("{ [0] }"), 0, 1)); |
| EXPECT_EQ(USET("{ [1] }"), shiftDim(USET("{ [0] }"), 0, 1)); |
| |
| // From-end indexing |
| EXPECT_EQ(USET("{ [0,0,1] }"), shiftDim(USET("{ [0,0,0] }"), -1, 1)); |
| EXPECT_EQ(USET("{ [0,1,0] }"), shiftDim(USET("{ [0,0,0] }"), -2, 1)); |
| EXPECT_EQ(USET("{ [1,0,0] }"), shiftDim(USET("{ [0,0,0] }"), -3, 1)); |
| |
| // Parametrized |
| EXPECT_EQ(USET("[n] -> { [n+1] }"), shiftDim(USET("[n] -> { [n] }"), 0, 1)); |
| |
| // Union maps |
| EXPECT_EQ(MAP("{ [1] -> [] }"), |
| shiftDim(MAP("{ [0] -> [] }"), isl::dim::in, 0, 1)); |
| EXPECT_EQ(UMAP("{ [1] -> [] }"), |
| shiftDim(UMAP("{ [0] -> [] }"), isl::dim::in, 0, 1)); |
| EXPECT_EQ(MAP("{ [] -> [1] }"), |
| shiftDim(MAP("{ [] -> [0] }"), isl::dim::out, 0, 1)); |
| EXPECT_EQ(UMAP("{ [] -> [1] }"), |
| shiftDim(UMAP("{ [] -> [0] }"), isl::dim::out, 0, 1)); |
| } |
| |
| TEST(DeLICM, computeReachingWrite) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // Basic usage |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"), |
| computeReachingWrite(UMAP("{ Dom[] -> [0] }"), |
| UMAP("{ Dom[] -> Elt[] }"), false, false, |
| false)); |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"), |
| computeReachingWrite(UMAP("{ Dom[] -> [0] }"), |
| UMAP("{ Dom[] -> Elt[] }"), false, false, |
| true)); |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"), |
| computeReachingWrite(UMAP("{ Dom[] -> [0] }"), |
| UMAP("{ Dom[] -> Elt[] }"), false, true, |
| false)); |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"), |
| computeReachingWrite(UMAP("{ Dom[] -> [0] }"), |
| UMAP("{ Dom[] -> Elt[] }"), false, true, |
| false)); |
| |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"), |
| computeReachingWrite(UMAP("{ Dom[] -> [0] }"), |
| UMAP("{ Dom[] -> Elt[] }"), true, false, |
| false)); |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"), |
| computeReachingWrite(UMAP("{ Dom[] -> [0] }"), |
| UMAP("{ Dom[] -> Elt[] }"), true, false, |
| true)); |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"), |
| computeReachingWrite(UMAP("{ Dom[] -> [0] }"), |
| UMAP("{ Dom[] -> Elt[] }"), true, true, |
| false)); |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"), |
| computeReachingWrite(UMAP("{ Dom[] -> [0] }"), |
| UMAP("{ Dom[] -> Elt[] }"), true, true, true)); |
| |
| // Two writes |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 < i < 10; [Elt[] -> [i]] -> " |
| "Dom2[] : 10 < i }"), |
| computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), |
| UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), |
| false, false, false)); |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 <= i < 10; [Elt[] -> [i]] -> " |
| "Dom2[] : 10 <= i }"), |
| computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), |
| UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), |
| false, true, false)); |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 < i <= 10; [Elt[] -> [i]] -> " |
| "Dom2[] : 10 < i }"), |
| computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), |
| UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), |
| false, false, true)); |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 <= i <= 10; [Elt[] -> [i]] -> " |
| "Dom2[] : 10 <= i }"), |
| computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), |
| UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), |
| false, true, true)); |
| |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i < 10; [Elt[] -> [i]] -> " |
| "Dom1[] : i < 0 }"), |
| computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), |
| UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), |
| true, false, false)); |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 <= i < 10; [Elt[] -> [i]] -> " |
| "Dom1[] : i < 0 }"), |
| computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), |
| UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), |
| true, true, false)); |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i <= 10; [Elt[] -> [i]] -> " |
| "Dom1[] : i <= 0 }"), |
| computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), |
| UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), |
| true, false, true)); |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 <= i <= 10; [Elt[] -> [i]] -> " |
| "Dom1[] : i <= 0 }"), |
| computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"), |
| UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"), |
| true, true, true)); |
| |
| // Domain in same space |
| EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[1] : 0 < i <= 10; [Elt[] -> [i]] -> " |
| "Dom[2] : 10 < i }"), |
| computeReachingWrite(UMAP("{ Dom[i] -> [10i - 10] }"), |
| UMAP("{ Dom[1] -> Elt[]; Dom[2] -> Elt[] }"), |
| false, false, true)); |
| |
| // Parametric |
| EXPECT_EQ(UMAP("[p] -> { [Elt[] -> [i]] -> Dom[] : p < i }"), |
| computeReachingWrite(UMAP("[p] -> { Dom[] -> [p] }"), |
| UMAP("{ Dom[] -> Elt[] }"), false, false, |
| false)); |
| |
| // More realistic example (from reduction_embedded.ll) |
| EXPECT_EQ( |
| UMAP("{ [Elt[] -> [i]] -> Dom[0] : 0 < i <= 3; [Elt[] -> [i]] -> Dom[1] " |
| ": 3 < i <= 6; [Elt[] -> [i]] -> Dom[2] : 6 < i <= 9; [Elt[] -> " |
| "[i]] -> Dom[3] : 9 < i <= 12; [Elt[] -> [i]] -> Dom[4] : 12 < i }"), |
| computeReachingWrite(UMAP("{ Dom[i] -> [3i] : 0 <= i <= 4 }"), |
| UMAP("{ Dom[i] -> Elt[] : 0 <= i <= 4 }"), false, |
| false, true)); |
| } |
| |
| TEST(DeLICM, computeArrayUnused) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // The ReadEltInSameInst parameter doesn't matter in simple cases. To also |
| // cover the parameter without duplicating the tests, this loops runs over |
| // other in both settings. |
| for (bool ReadEltInSameInst = false, Done = false; !Done; |
| Done = ReadEltInSameInst, ReadEltInSameInst = true) { |
| // Basic usage: one read, one write |
| EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i < 10 }"), |
| computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"), |
| UMAP("{ Write[] -> Elt[] }"), |
| UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, |
| false, false)); |
| EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"), |
| computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"), |
| UMAP("{ Write[] -> Elt[] }"), |
| UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, |
| false, true)); |
| EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 <= i < 10 }"), |
| computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"), |
| UMAP("{ Write[] -> Elt[] }"), |
| UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, |
| true, false)); |
| EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 <= i <= 10 }"), |
| computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"), |
| UMAP("{ Write[] -> Elt[] }"), |
| UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, |
| true, true)); |
| |
| // Two reads |
| EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"), |
| computeArrayUnused( |
| UMAP("{ Read[0] -> [-10]; Read[1] -> [0]; Write[] -> [10] }"), |
| UMAP("{ Write[] -> Elt[] }"), UMAP("{ Read[i] -> Elt[] }"), |
| ReadEltInSameInst, false, true)); |
| |
| // Corner case: no writes |
| EXPECT_EQ(UMAP("{}"), |
| computeArrayUnused(UMAP("{ Read[] -> [0] }"), UMAP("{}"), |
| UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, |
| false, false)); |
| |
| // Corner case: no reads |
| EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"), |
| computeArrayUnused(UMAP("{ Write[] -> [0] }"), |
| UMAP("{ Write[] -> Elt[] }"), UMAP("{}"), |
| ReadEltInSameInst, false, true)); |
| |
| // Two writes |
| EXPECT_EQ( |
| UMAP("{ Elt[] -> [i] : i <= 10 }"), |
| computeArrayUnused(UMAP("{ WriteA[] -> [0]; WriteB[] -> [10] }"), |
| UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"), |
| UMAP("{}"), ReadEltInSameInst, false, true)); |
| |
| // Two unused zones |
| // read,write,read,write |
| EXPECT_EQ( |
| UMAP("{ Elt[] -> [i] : 0 < i <= 10; Elt[] -> [i] : 20 < i <= 30 }"), |
| computeArrayUnused(UMAP("{ ReadA[] -> [0]; WriteA[] -> [10]; ReadB[] " |
| "-> [20]; WriteB[] -> [30] }"), |
| UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"), |
| UMAP("{ ReadA[] -> Elt[]; ReadB[] -> Elt[] }"), |
| ReadEltInSameInst, false, true)); |
| |
| // write, write |
| EXPECT_EQ( |
| UMAP("{ Elt[] -> [i] : i <= 10 }"), |
| computeArrayUnused( |
| UMAP("{ WriteA[] -> [0]; WriteB[] -> [10]; Read[] -> [20] }"), |
| UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"), |
| UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, false, true)); |
| |
| // write, read |
| EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"), |
| computeArrayUnused(UMAP("{ Write[] -> [0]; Read[] -> [10] }"), |
| UMAP("{ Write[] -> Elt[] }"), |
| UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, |
| false, true)); |
| |
| // read, write, read |
| EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"), |
| computeArrayUnused( |
| UMAP("{ ReadA[] -> [0]; Write[] -> [10]; ReadB[] -> [20] }"), |
| UMAP("{ Write[] -> Elt[] }"), |
| UMAP("{ ReadA[] -> Elt[]; ReadB[] -> Elt[] }"), |
| ReadEltInSameInst, false, true)); |
| |
| // read, write, write |
| EXPECT_EQ( |
| UMAP("{ Elt[] -> [i] : 0 < i <= 20 }"), |
| computeArrayUnused( |
| UMAP("{ Read[] -> [0]; WriteA[] -> [10]; WriteB[] -> [20] }"), |
| UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"), |
| UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, false, true)); |
| |
| // read, write, write, read |
| EXPECT_EQ( |
| UMAP("{ Elt[] -> [i] : 0 < i <= 20 }"), |
| computeArrayUnused(UMAP("{ ReadA[] -> [0]; WriteA[] -> [10]; WriteB[] " |
| "-> [20]; ReadB[] -> [30] }"), |
| UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"), |
| UMAP("{ ReadA[] -> Elt[]; ReadB[] -> Elt[] }"), |
| ReadEltInSameInst, false, true)); |
| } |
| |
| // Read and write in same statement |
| EXPECT_EQ(UMAP("{ Elt[] -> [i] : i < 0 }"), |
| computeArrayUnused(UMAP("{ RW[] -> [0] }"), |
| UMAP("{ RW[] -> Elt[] }"), |
| UMAP("{ RW[] -> Elt[] }"), true, false, false)); |
| EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"), |
| computeArrayUnused(UMAP("{ RW[] -> [0] }"), |
| UMAP("{ RW[] -> Elt[] }"), |
| UMAP("{ RW[] -> Elt[] }"), true, false, true)); |
| EXPECT_EQ(UMAP("{ Elt[] -> [0] }"), |
| computeArrayUnused(UMAP("{ RW[] -> [0] }"), |
| UMAP("{ RW[] -> Elt[] }"), |
| UMAP("{ RW[] -> Elt[] }"), false, true, true)); |
| } |
| |
| TEST(DeLICM, convertZoneToTimepoints) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // Corner case: empty set |
| EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), false, false)); |
| EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), true, false)); |
| EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), false, true)); |
| EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), true, true)); |
| |
| // Basic usage |
| EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{ [1] }"), false, false)); |
| EXPECT_EQ(USET("{ [0] }"), |
| convertZoneToTimepoints(USET("{ [1] }"), true, false)); |
| EXPECT_EQ(USET("{ [1] }"), |
| convertZoneToTimepoints(USET("{ [1] }"), false, true)); |
| EXPECT_EQ(USET("{ [0]; [1] }"), |
| convertZoneToTimepoints(USET("{ [1] }"), true, true)); |
| |
| // Non-adjacent ranges |
| EXPECT_EQ(USET("{}"), |
| convertZoneToTimepoints(USET("{ [1]; [11] }"), false, false)); |
| EXPECT_EQ(USET("{ [0]; [10] }"), |
| convertZoneToTimepoints(USET("{ [1]; [11] }"), true, false)); |
| EXPECT_EQ(USET("{ [1]; [11] }"), |
| convertZoneToTimepoints(USET("{ [1]; [11] }"), false, true)); |
| EXPECT_EQ(USET("{ [0]; [1]; [10]; [11] }"), |
| convertZoneToTimepoints(USET("{ [1]; [11] }"), true, true)); |
| |
| // Adjacent unit ranges |
| EXPECT_EQ( |
| USET("{ [i] : 0 < i < 10 }"), |
| convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, false)); |
| EXPECT_EQ( |
| USET("{ [i] : 0 <= i < 10 }"), |
| convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, false)); |
| EXPECT_EQ( |
| USET("{ [i] : 0 < i <= 10 }"), |
| convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, true)); |
| EXPECT_EQ(USET("{ [i] : 0 <= i <= 10 }"), |
| convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, true)); |
| |
| // More than one dimension |
| EXPECT_EQ(USET("{}"), |
| convertZoneToTimepoints(USET("{ [0,1] }"), false, false)); |
| EXPECT_EQ(USET("{ [0,0] }"), |
| convertZoneToTimepoints(USET("{ [0,1] }"), true, false)); |
| EXPECT_EQ(USET("{ [0,1] }"), |
| convertZoneToTimepoints(USET("{ [0,1] }"), false, true)); |
| EXPECT_EQ(USET("{ [0,0]; [0,1] }"), |
| convertZoneToTimepoints(USET("{ [0,1] }"), true, true)); |
| |
| // Map domains |
| EXPECT_EQ(UMAP("{}"), convertZoneToTimepoints(UMAP("{ [1] -> [] }"), |
| isl::dim::in, false, false)); |
| EXPECT_EQ(UMAP("{ [0] -> [] }"), |
| convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, true, |
| false)); |
| EXPECT_EQ(UMAP("{ [1] -> [] }"), |
| convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, false, |
| true)); |
| EXPECT_EQ( |
| UMAP("{ [0] -> []; [1] -> [] }"), |
| convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, true, true)); |
| |
| // Map ranges |
| EXPECT_EQ(UMAP("{}"), convertZoneToTimepoints(UMAP("{ [] -> [1] }"), |
| isl::dim::out, false, false)); |
| EXPECT_EQ(UMAP("{ [] -> [0] }"), |
| convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, true, |
| false)); |
| EXPECT_EQ(UMAP("{ [] -> [1] }"), |
| convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, false, |
| true)); |
| EXPECT_EQ(UMAP("{ [] -> [0]; [] -> [1] }"), |
| convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, true, |
| true)); |
| } |
| |
| TEST(DeLICM, distribute) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // Basic usage |
| EXPECT_EQ(MAP("{ [Domain[] -> Range1[]] -> [Domain[] -> Range2[]] }"), |
| distributeDomain(MAP("{ Domain[] -> [Range1[] -> Range2[]] }"))); |
| EXPECT_EQ( |
| MAP("{ [Domain[i,j] -> Range1[i,k]] -> [Domain[i,j] -> Range2[j,k]] }"), |
| distributeDomain(MAP("{ Domain[i,j] -> [Range1[i,k] -> Range2[j,k]] }"))); |
| |
| // Union maps |
| EXPECT_EQ( |
| UMAP( |
| "{ [DomainA[i,j] -> RangeA1[i,k]] -> [DomainA[i,j] -> RangeA2[j,k]];" |
| "[DomainB[i,j] -> RangeB1[i,k]] -> [DomainB[i,j] -> RangeB2[j,k]] }"), |
| distributeDomain( |
| UMAP("{ DomainA[i,j] -> [RangeA1[i,k] -> RangeA2[j,k]];" |
| "DomainB[i,j] -> [RangeB1[i,k] -> RangeB2[j,k]] }"))); |
| } |
| |
| TEST(DeLICM, lift) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // Basic usage |
| EXPECT_EQ(UMAP("{ [Factor[] -> Domain[]] -> [Factor[] -> Range[]] }"), |
| liftDomains(UMAP("{ Domain[] -> Range[] }"), USET("{ Factor[] }"))); |
| EXPECT_EQ(UMAP("{ [Factor[l] -> Domain[i,k]] -> [Factor[l] -> Range[j,k]] }"), |
| liftDomains(UMAP("{ Domain[i,k] -> Range[j,k] }"), |
| USET("{ Factor[l] }"))); |
| |
| // Multiple maps in union |
| EXPECT_EQ( |
| UMAP("{ [FactorA[] -> DomainA[]] -> [FactorA[] -> RangeA[]];" |
| "[FactorB[] -> DomainA[]] -> [FactorB[] -> RangeA[]];" |
| "[FactorA[] -> DomainB[]] -> [FactorA[] -> RangeB[]];" |
| "[FactorB[] -> DomainB[]] -> [FactorB[] -> RangeB[]] }"), |
| liftDomains(UMAP("{ DomainA[] -> RangeA[]; DomainB[] -> RangeB[] }"), |
| USET("{ FactorA[]; FactorB[] }"))); |
| } |
| |
| TEST(DeLICM, apply) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| // Basic usage |
| EXPECT_EQ( |
| UMAP("{ [DomainDomain[] -> NewDomainRange[]] -> Range[] }"), |
| applyDomainRange(UMAP("{ [DomainDomain[] -> DomainRange[]] -> Range[] }"), |
| UMAP("{ DomainRange[] -> NewDomainRange[] }"))); |
| EXPECT_EQ( |
| UMAP("{ [DomainDomain[i,k] -> NewDomainRange[j,k,l]] -> Range[i,j] }"), |
| applyDomainRange( |
| UMAP("{ [DomainDomain[i,k] -> DomainRange[j,k]] -> Range[i,j] }"), |
| UMAP("{ DomainRange[j,k] -> NewDomainRange[j,k,l] }"))); |
| |
| // Multiple maps in union |
| EXPECT_EQ(UMAP("{ [DomainDomainA[] -> NewDomainRangeA[]] -> RangeA[];" |
| "[DomainDomainB[] -> NewDomainRangeB[]] -> RangeB[] }"), |
| applyDomainRange( |
| UMAP("{ [DomainDomainA[] -> DomainRangeA[]] -> RangeA[];" |
| "[DomainDomainB[] -> DomainRangeB[]] -> RangeB[] }"), |
| UMAP("{ DomainRangeA[] -> NewDomainRangeA[];" |
| "DomainRangeB[] -> NewDomainRangeB[] }"))); |
| } |
| |
| TEST(Isl, Quota) { |
| std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(), |
| &isl_ctx_free); |
| |
| isl::set TestSet1{Ctx.get(), "{ [0] }"}; |
| isl::set TestSet2{Ctx.get(), "{ [i] : i > 0 }"}; |
| |
| { |
| IslMaxOperationsGuard MaxOpGuard(Ctx.get(), 1); |
| ASSERT_EQ(isl_options_get_on_error(Ctx.get()), ISL_ON_ERROR_CONTINUE); |
| ASSERT_EQ(isl_ctx_get_max_operations(Ctx.get()), 1ul); |
| ASSERT_FALSE(MaxOpGuard.hasQuotaExceeded()); |
| |
| // Intentionally exceed the quota. Each allocation will use at least one |
| // operation, guaranteed to exceed the max_operations of 1. |
| isl::id::alloc(Ctx.get(), "A", nullptr); |
| isl::id::alloc(Ctx.get(), "B", nullptr); |
| ASSERT_TRUE(MaxOpGuard.hasQuotaExceeded()); |
| |
| // Check returned object after exceeded quota. |
| isl::set Union = TestSet1.unite(TestSet2); |
| EXPECT_TRUE(Union.is_null()); |
| |
| // Check isl::boolean result after exceeded quota. |
| isl::boolean BoolResult = TestSet1.is_empty(); |
| EXPECT_TRUE(BoolResult.is_error()); |
| EXPECT_FALSE(BoolResult.is_false()); |
| EXPECT_FALSE(BoolResult.is_true()); |
| EXPECT_DEATH((void)(bool)BoolResult, |
| "IMPLEMENTATION ERROR: Unhandled error state"); |
| EXPECT_DEATH((void)(bool)!BoolResult, |
| "IMPLEMENTATION ERROR: Unhandled error state"); |
| EXPECT_DEATH( |
| { |
| if (BoolResult) { |
| } |
| }, |
| "IMPLEMENTATION ERROR: Unhandled error state"); |
| EXPECT_DEATH((void)(BoolResult == false), |
| "IMPLEMENTATION ERROR: Unhandled error state"); |
| EXPECT_DEATH((void)(BoolResult == true), |
| "IMPLEMENTATION ERROR: Unhandled error state"); |
| |
| // Check isl::stat result after exceeded quota. |
| isl::stat StatResult = |
| TestSet1.foreach_point([](isl::point) { return isl::stat::ok(); }); |
| EXPECT_TRUE(StatResult.is_error()); |
| EXPECT_FALSE(StatResult.is_ok()); |
| } |
| ASSERT_EQ(isl_ctx_last_error(Ctx.get()), isl_error_quota); |
| ASSERT_EQ(isl_options_get_on_error(Ctx.get()), ISL_ON_ERROR_WARN); |
| ASSERT_EQ(isl_ctx_get_max_operations(Ctx.get()), 0ul); |
| |
| // Operations must work again after leaving the quota scope. |
| { |
| isl::set Union = TestSet1.unite(TestSet2); |
| EXPECT_FALSE(Union.is_null()); |
| |
| isl::boolean BoolResult = TestSet1.is_empty(); |
| EXPECT_FALSE(BoolResult.is_error()); |
| EXPECT_TRUE(BoolResult.is_false()); |
| EXPECT_FALSE(BoolResult.is_true()); |
| EXPECT_FALSE(BoolResult); |
| EXPECT_TRUE(!BoolResult); |
| |
| isl::stat StatResult = |
| TestSet1.foreach_point([](isl::point) { return isl::stat::ok(); }); |
| EXPECT_FALSE(StatResult.is_error()); |
| EXPECT_TRUE(StatResult.is_ok()); |
| } |
| } |
| |
| } // anonymous namespace |
