unittests/Isl/IslTest.cpp

   1 //===- IslTest.cpp ----------------------------------------------------===//
   2 //
   3 //                     The LLVM Compiler Infrastructure
   4 //
   5 // This file is distributed under the University of Illinois Open Source
   6 // License. See LICENSE.TXT for details.
   7 //
   8 //===----------------------------------------------------------------------===//
   9
  10 #include "polly/Support/GICHelper.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 = give(isl_set_get_space(static_cast<isl_set *>(Obj.v)));
  26   else if (Obj.type == isl_obj_map)
  27     Result = give(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 } // namespace noexceptions
  78 } // namespace isl
  79
  80 namespace {
  81
  82 TEST(Isl, APIntToIslVal) {
  83   isl_ctx *IslCtx = isl_ctx_alloc();
  84
  85   {
  86     APInt APZero(1, 0, true);
  87     auto IslZero = valFromAPInt(IslCtx, APZero, true);
  88     EXPECT_TRUE(IslZero.is_zero());
  89   }
  90
  91   {
  92     APInt APNOne(1, -1, true);
  93     auto IslNOne = valFromAPInt(IslCtx, APNOne, true);
  94     EXPECT_TRUE(IslNOne.is_negone());
  95   }
  96
  97   {
  98     APInt APZero(1, 0, false);
  99     auto IslZero = valFromAPInt(IslCtx, APZero, false);
 100     EXPECT_TRUE(IslZero.is_zero());
 101   }
 102
 103   {
 104     APInt APOne(1, 1, false);
 105     auto IslOne = valFromAPInt(IslCtx, APOne, false);
 106     EXPECT_TRUE(IslOne.is_one());
 107   }
 108
 109   {
 110     APInt APNTwo(2, -2, true);
 111     auto IslNTwo = valFromAPInt(IslCtx, APNTwo, true);
 112     auto IslNTwoCmp = isl::val(IslCtx, -2);
 113     EXPECT_EQ(IslNTwo, IslNTwoCmp);
 114   }
 115
 116   {
 117     APInt APNOne(32, -1, true);
 118     auto IslNOne = valFromAPInt(IslCtx, APNOne, true);
 119     EXPECT_TRUE(IslNOne.is_negone());
 120   }
 121
 122   {
 123     APInt APZero(32, 0, false);
 124     auto IslZero = valFromAPInt(IslCtx, APZero, false);
 125     EXPECT_TRUE(IslZero.is_zero());
 126   }
 127
 128   {
 129     APInt APOne(32, 1, false);
 130     auto IslOne = valFromAPInt(IslCtx, APOne, false);
 131     EXPECT_TRUE(IslOne.is_one());
 132   }
 133
 134   {
 135     APInt APTwo(32, 2, false);
 136     auto IslTwo = valFromAPInt(IslCtx, APTwo, false);
 137     EXPECT_EQ(0, IslTwo.cmp_si(2));
 138   }
 139
 140   {
 141     APInt APNOne(32, (1ull << 32) - 1, false);
 142     auto IslNOne = valFromAPInt(IslCtx, APNOne, false);
 143     auto IslRef = isl::val(IslCtx, 32).two_exp().sub_ui(1);
 144     EXPECT_EQ(IslNOne, IslRef);
 145   }
 146
 147   {
 148     APInt APLarge(130, 2, false);
 149     APLarge = APLarge.shl(70);
 150     auto IslLarge = valFromAPInt(IslCtx, APLarge, false);
 151     auto IslRef = isl::val(IslCtx, 71);
 152     IslRef = IslRef.two_exp();
 153     EXPECT_EQ(IslLarge, IslRef);
 154   }
 155
 156   isl_ctx_free(IslCtx);
 157 }
 158
 159 TEST(Isl, IslValToAPInt) {
 160   isl_ctx *IslCtx = isl_ctx_alloc();
 161
 162   {
 163     auto IslNOne = isl::val(IslCtx, -1);
 164     auto APNOne = APIntFromVal(IslNOne);
 165     // Compare with the two's complement of -1 in a 1-bit integer.
 166     EXPECT_EQ(1, APNOne);
 167     EXPECT_EQ(1u, APNOne.getBitWidth());
 168   }
 169
 170   {
 171     auto IslNTwo = isl::val(IslCtx, -2);
 172     auto APNTwo = APIntFromVal(IslNTwo);
 173     // Compare with the two's complement of -2 in a 2-bit integer.
 174     EXPECT_EQ(2, APNTwo);
 175     EXPECT_EQ(2u, APNTwo.getBitWidth());
 176   }
 177
 178   {
 179     auto IslNThree = isl::val(IslCtx, -3);
 180     auto APNThree = APIntFromVal(IslNThree);
 181     // Compare with the two's complement of -3 in a 3-bit integer.
 182     EXPECT_EQ(5, APNThree);
 183     EXPECT_EQ(3u, APNThree.getBitWidth());
 184   }
 185
 186   {
 187     auto IslNFour = isl::val(IslCtx, -4);
 188     auto APNFour = APIntFromVal(IslNFour);
 189     // Compare with the two's complement of -4 in a 3-bit integer.
 190     EXPECT_EQ(4, APNFour);
 191     EXPECT_EQ(3u, APNFour.getBitWidth());
 192   }
 193
 194   {
 195     auto IslZero = isl::val(IslCtx, 0);
 196     auto APZero = APIntFromVal(IslZero);
 197     EXPECT_EQ(0, APZero);
 198     EXPECT_EQ(1u, APZero.getBitWidth());
 199   }
 200
 201   {
 202     auto IslOne = isl::val(IslCtx, 1);
 203     auto APOne = APIntFromVal(IslOne);
 204     EXPECT_EQ(1, APOne);
 205     EXPECT_EQ(2u, APOne.getBitWidth());
 206   }
 207
 208   {
 209     auto IslTwo = isl::val(IslCtx, 2);
 210     auto APTwo = APIntFromVal(IslTwo);
 211     EXPECT_EQ(2, APTwo);
 212     EXPECT_EQ(3u, APTwo.getBitWidth());
 213   }
 214
 215   {
 216     auto IslThree = isl::val(IslCtx, 3);
 217     auto APThree = APIntFromVal(IslThree);
 218     EXPECT_EQ(3, APThree);
 219     EXPECT_EQ(3u, APThree.getBitWidth());
 220   }
 221
 222   {
 223     auto IslFour = isl::val(IslCtx, 4);
 224     auto APFour = APIntFromVal(IslFour);
 225     EXPECT_EQ(4, APFour);
 226     EXPECT_EQ(4u, APFour.getBitWidth());
 227   }
 228
 229   {
 230     auto IslNOne = isl::val(IslCtx, 32).two_exp().sub_ui(1);
 231     auto APNOne = APIntFromVal(IslNOne);
 232     EXPECT_EQ((1ull << 32) - 1, APNOne);
 233     EXPECT_EQ(33u, APNOne.getBitWidth());
 234   }
 235
 236   {
 237     auto IslLargeNum = isl::val(IslCtx, 60);
 238     IslLargeNum = IslLargeNum.two_exp();
 239     IslLargeNum = IslLargeNum.sub_ui(1);
 240     auto APLargeNum = APIntFromVal(IslLargeNum);
 241     EXPECT_EQ((1ull << 60) - 1, APLargeNum);
 242     EXPECT_EQ(61u, APLargeNum.getBitWidth());
 243   }
 244
 245   {
 246     auto IslExp = isl::val(IslCtx, 500);
 247     auto IslLargePow2 = IslExp.two_exp();
 248     auto APLargePow2 = APIntFromVal(IslLargePow2);
 249     EXPECT_TRUE(APLargePow2.isPowerOf2());
 250     EXPECT_EQ(502u, APLargePow2.getBitWidth());
 251     EXPECT_EQ(502u, APLargePow2.getMinSignedBits());
 252   }
 253
 254   {
 255     auto IslExp = isl::val(IslCtx, 500);
 256     auto IslLargeNPow2 = IslExp.two_exp().neg();
 257     auto APLargeNPow2 = APIntFromVal(IslLargeNPow2);
 258     EXPECT_EQ(501u, APLargeNPow2.getBitWidth());
 259     EXPECT_EQ(501u, APLargeNPow2.getMinSignedBits());
 260     EXPECT_EQ(500, (-APLargeNPow2).exactLogBase2());
 261   }
 262
 263   {
 264     auto IslExp = isl::val(IslCtx, 512);
 265     auto IslLargePow2 = IslExp.two_exp();
 266     auto APLargePow2 = APIntFromVal(IslLargePow2);
 267     EXPECT_TRUE(APLargePow2.isPowerOf2());
 268     EXPECT_EQ(514u, APLargePow2.getBitWidth());
 269     EXPECT_EQ(514u, APLargePow2.getMinSignedBits());
 270   }
 271
 272   {
 273     auto IslExp = isl::val(IslCtx, 512);
 274     auto IslLargeNPow2 = IslExp.two_exp().neg();
 275     auto APLargeNPow2 = APIntFromVal(IslLargeNPow2);
 276     EXPECT_EQ(513u, APLargeNPow2.getBitWidth());
 277     EXPECT_EQ(513u, APLargeNPow2.getMinSignedBits());
 278     EXPECT_EQ(512, (-APLargeNPow2).exactLogBase2());
 279   }
 280
 281   isl_ctx_free(IslCtx);
 282 }
 283
 284 TEST(Isl, Foreach) {
 285   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 286                                                         &isl_ctx_free);
 287
 288   auto MapSpace = isl::space(Ctx.get(), 0, 1, 1);
 289   auto TestBMap = isl::basic_map::universe(MapSpace);
 290   TestBMap = TestBMap.fix_si(isl::dim::out, 0, 0);
 291   TestBMap = TestBMap.fix_si(isl::dim::out, 0, 0);
 292   isl::map TestMap = TestBMap;
 293   isl::union_map TestUMap = TestMap;
 294
 295   auto SetSpace = isl::space(Ctx.get(), 0, 1);
 296   isl::basic_set TestBSet = isl::point(SetSpace);
 297   isl::set TestSet = TestBSet;
 298   isl::union_set TestUSet = TestSet;
 299
 300   {
 301     auto NumBMaps = 0;
 302     TestMap.foreach_basic_map([&](isl::basic_map BMap) -> isl::stat {
 303       EXPECT_EQ(BMap, TestBMap);
 304       NumBMaps++;
 305       return isl::stat::ok;
 306     });
 307     EXPECT_EQ(1, NumBMaps);
 308   }
 309
 310   {
 311     auto NumBSets = 0;
 312     TestSet.foreach_basic_set([&](isl::basic_set BSet) -> isl::stat {
 313       EXPECT_EQ(BSet, TestBSet);
 314       NumBSets++;
 315       return isl::stat::ok;
 316     });
 317     EXPECT_EQ(1, NumBSets);
 318   }
 319
 320   {
 321     auto NumMaps = 0;
 322     TestUMap.foreach_map([&](isl::map Map) -> isl::stat {
 323       EXPECT_EQ(Map, TestMap);
 324       NumMaps++;
 325       return isl::stat::ok;
 326     });
 327     EXPECT_EQ(1, NumMaps);
 328   }
 329
 330   {
 331     auto NumSets = 0;
 332     TestUSet.foreach_set([&](isl::set Set) -> isl::stat {
 333       EXPECT_EQ(Set, TestSet);
 334       NumSets++;
 335       return isl::stat::ok;
 336     });
 337     EXPECT_EQ(1, NumSets);
 338   }
 339
 340   {
 341     auto UPwAff = isl::union_pw_aff(TestUSet, isl::val::zero(Ctx.get()));
 342     auto NumPwAffs = 0;
 343     UPwAff.foreach_pw_aff([&](isl::pw_aff PwAff) -> isl::stat {
 344       EXPECT_TRUE(PwAff.is_cst());
 345       NumPwAffs++;
 346       return isl::stat::ok;
 347     });
 348     EXPECT_EQ(1, NumPwAffs);
 349   }
 350
 351   {
 352     auto NumBMaps = 0;
 353     EXPECT_EQ(isl::stat::error,
 354               TestMap.foreach_basic_map([&](isl::basic_map BMap) -> isl::stat {
 355                 EXPECT_EQ(BMap, TestBMap);
 356                 NumBMaps++;
 357                 return isl::stat::error;
 358               }));
 359     EXPECT_EQ(1, NumBMaps);
 360   }
 361
 362   {
 363     auto NumMaps = 0;
 364     EXPECT_EQ(isl::stat::error,
 365               TestUMap.foreach_map([&](isl::map Map) -> isl::stat {
 366                 EXPECT_EQ(Map, TestMap);
 367                 NumMaps++;
 368                 return isl::stat::error;
 369               }));
 370     EXPECT_EQ(1, NumMaps);
 371   }
 372
 373   {
 374     auto TestPwAff = isl::pw_aff(TestSet, isl::val::zero(Ctx.get()));
 375     auto NumPieces = 0;
 376     TestPwAff.foreach_piece([&](isl::set Domain, isl::aff Aff) -> isl::stat {
 377       EXPECT_EQ(Domain, TestSet);
 378       EXPECT_TRUE(Aff.is_cst());
 379       NumPieces++;
 380       return isl::stat::error;
 381     });
 382     EXPECT_EQ(1, NumPieces);
 383   }
 384 }
 385
 386 TEST(ISLTools, beforeScatter) {
 387   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 388                                                         &isl_ctx_free);
 389
 390   // Basic usage with isl_map
 391   EXPECT_EQ(MAP("{ [] -> [i] : i <= 0 }"),
 392             beforeScatter(MAP("{ [] -> [0] }"), false));
 393   EXPECT_EQ(MAP("{ [] -> [i] : i < 0 }"),
 394             beforeScatter(MAP("{ [] -> [0] }"), true));
 395
 396   // Basic usage with isl_union_map
 397   EXPECT_EQ(UMAP("{ A[] -> [i] : i <= 0; B[] -> [i] : i <= 0 }"),
 398             beforeScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), false));
 399   EXPECT_EQ(UMAP("{ A[] -> [i] : i < 0; B[] -> [i] : i < 0 }"),
 400             beforeScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), true));
 401
 402   // More than one dimension
 403   EXPECT_EQ(UMAP("{ [] -> [i, j] : i < 0;  [] -> [i, j] : i = 0 and j <= 0 }"),
 404             beforeScatter(UMAP("{ [] -> [0, 0] }"), false));
 405   EXPECT_EQ(UMAP("{ [] -> [i, j] : i < 0;  [] -> [i, j] : i = 0 and j < 0 }"),
 406             beforeScatter(UMAP("{ [] -> [0, 0] }"), true));
 407
 408   // Functional
 409   EXPECT_EQ(UMAP("{ [i] -> [j] : j <= i }"),
 410             beforeScatter(UMAP("{ [i] -> [i] }"), false));
 411   EXPECT_EQ(UMAP("{ [i] -> [j] : j < i }"),
 412             beforeScatter(UMAP("{ [i] -> [i] }"), true));
 413
 414   // Parametrized
 415   EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j <= i }"),
 416             beforeScatter(UMAP("[i] -> { [] -> [i] }"), false));
 417   EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j < i }"),
 418             beforeScatter(UMAP("[i] -> { [] -> [i] }"), true));
 419
 420   // More than one range
 421   EXPECT_EQ(UMAP("{ [] -> [i] : i <= 10 }"),
 422             beforeScatter(UMAP("{ [] -> [0]; [] -> [10] }"), false));
 423   EXPECT_EQ(UMAP("{ [] -> [i] : i < 10 }"),
 424             beforeScatter(UMAP("{ [] -> [0]; [] -> [10] }"), true));
 425
 426   // Edge case: empty
 427   EXPECT_EQ(UMAP("{ [] -> [i] : 1 = 0 }"),
 428             beforeScatter(UMAP("{ [] -> [i] : 1 = 0 }"), false));
 429   EXPECT_EQ(UMAP("{ [] -> [i] : 1 = 0 }"),
 430             beforeScatter(UMAP("{ [] -> [i] : 1 = 0 }"), true));
 431 }
 432
 433 TEST(ISLTools, afterScatter) {
 434   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 435                                                         &isl_ctx_free);
 436
 437   // Basic usage with isl_map
 438   EXPECT_EQ(MAP("{ [] -> [i] : i >= 0 }"),
 439             afterScatter(MAP("{ [] -> [0] }"), false));
 440   EXPECT_EQ(MAP("{ [] -> [i] : i > 0 }"),
 441             afterScatter(MAP("{ [] -> [0] }"), true));
 442
 443   // Basic usage with isl_union_map
 444   EXPECT_EQ(UMAP("{ A[] -> [i] : i >= 0; B[] -> [i] : i >= 0 }"),
 445             afterScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), false));
 446   EXPECT_EQ(UMAP("{ A[] -> [i] : i > 0; B[] -> [i] : i > 0 }"),
 447             afterScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), true));
 448
 449   // More than one dimension
 450   EXPECT_EQ(UMAP("{ [] -> [i, j] : i > 0;  [] -> [i, j] : i = 0 and j >= 0 }"),
 451             afterScatter(UMAP("{ [] -> [0, 0] }"), false));
 452   EXPECT_EQ(UMAP("{ [] -> [i, j] : i > 0;  [] -> [i, j] : i = 0 and j > 0 }"),
 453             afterScatter(UMAP("{ [] -> [0, 0] }"), true));
 454
 455   // Functional
 456   EXPECT_EQ(UMAP("{ [i] -> [j] : j >= i }"),
 457             afterScatter(UMAP("{ [i] -> [i] }"), false));
 458   EXPECT_EQ(UMAP("{ [i] -> [j] : j > i }"),
 459             afterScatter(UMAP("{ [i] -> [i] }"), true));
 460
 461   // Parametrized
 462   EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j >= i }"),
 463             afterScatter(UMAP("[i] -> { [] -> [i] }"), false));
 464   EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j > i }"),
 465             afterScatter(UMAP("[i] -> { [] -> [i] }"), true));
 466
 467   // More than one range
 468   EXPECT_EQ(UMAP("{ [] -> [i] : i >= 0 }"),
 469             afterScatter(UMAP("{ [] -> [0]; [] -> [10] }"), false));
 470   EXPECT_EQ(UMAP("{ [] -> [i] : i > 0 }"),
 471             afterScatter(UMAP("{ [] -> [0]; [] -> [10] }"), true));
 472
 473   // Edge case: empty
 474   EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), false));
 475   EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), true));
 476 }
 477
 478 TEST(ISLTools, betweenScatter) {
 479   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 480                                                         &isl_ctx_free);
 481
 482   // Basic usage with isl_map
 483   EXPECT_EQ(MAP("{ [] -> [i] : 0 < i < 10 }"),
 484             betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false,
 485                            false));
 486   EXPECT_EQ(
 487       MAP("{ [] -> [i] : 0 <= i < 10 }"),
 488       betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, false));
 489   EXPECT_EQ(
 490       MAP("{ [] -> [i] : 0 < i <= 10 }"),
 491       betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false, true));
 492   EXPECT_EQ(
 493       MAP("{ [] -> [i] : 0 <= i <= 10 }"),
 494       betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, true));
 495
 496   // Basic usage with isl_union_map
 497   EXPECT_EQ(UMAP("{ A[] -> [i] : 0 < i < 10; B[] -> [i] : 0 < i < 10 }"),
 498             betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
 499                            UMAP("{ A[] -> [10]; B[] -> [10] }"), false, false));
 500   EXPECT_EQ(UMAP("{ A[] -> [i] : 0 <= i < 10; B[] -> [i] : 0 <= i < 10 }"),
 501             betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
 502                            UMAP("{ A[] -> [10]; B[] -> [10] }"), true, false));
 503   EXPECT_EQ(UMAP("{ A[] -> [i] : 0 < i <= 10; B[] -> [i] : 0 < i <= 10 }"),
 504             betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
 505                            UMAP("{ A[] -> [10]; B[] -> [10] }"), false, true));
 506   EXPECT_EQ(UMAP("{ A[] -> [i] : 0 <= i <= 10; B[] -> [i] : 0 <= i <= 10 }"),
 507             betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
 508                            UMAP("{ A[] -> [10]; B[] -> [10] }"), true, true));
 509 }
 510
 511 TEST(ISLTools, singleton) {
 512   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 513                                                         &isl_ctx_free);
 514
 515   // No element found
 516   EXPECT_EQ(SET("{ [] : 1 = 0 }"), singleton(USET("{ }"), SPACE("{ [] }")));
 517   EXPECT_EQ(MAP("{ [] -> [] : 1 = 0  }"),
 518             singleton(UMAP("{  }"), SPACE("{ [] -> [] }")));
 519
 520   // One element found
 521   EXPECT_EQ(SET("{ [] }"), singleton(USET("{ [] }"), SPACE("{ [] }")));
 522   EXPECT_EQ(MAP("{ [] -> [] }"),
 523             singleton(UMAP("{ [] -> [] }"), SPACE("{ [] -> [] }")));
 524
 525   // Many elements found
 526   EXPECT_EQ(SET("{ [i] : 0 <= i < 10 }"),
 527             singleton(USET("{ [i] : 0 <= i < 10 }"), SPACE("{ [i] }")));
 528   EXPECT_EQ(
 529       MAP("{ [i] -> [i] : 0 <= i < 10 }"),
 530       singleton(UMAP("{ [i] -> [i] : 0 <= i < 10 }"), SPACE("{ [i] -> [j] }")));
 531
 532   // Different parameters
 533   EXPECT_EQ(SET("[i] -> { [i] }"),
 534             singleton(USET("[i] -> { [i] }"), SPACE("{ [i] }")));
 535   EXPECT_EQ(MAP("[i] -> { [i] -> [i] }"),
 536             singleton(UMAP("[i] -> { [i] -> [i] }"), SPACE("{ [i] -> [j] }")));
 537 }
 538
 539 TEST(ISLTools, getNumScatterDims) {
 540   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 541                                                         &isl_ctx_free);
 542
 543   // Basic usage
 544   EXPECT_EQ(0u, getNumScatterDims(UMAP("{ [] -> [] }")));
 545   EXPECT_EQ(1u, getNumScatterDims(UMAP("{ [] -> [i] }")));
 546   EXPECT_EQ(2u, getNumScatterDims(UMAP("{ [] -> [i,j] }")));
 547   EXPECT_EQ(3u, getNumScatterDims(UMAP("{ [] -> [i,j,k] }")));
 548
 549   // Different scatter spaces
 550   EXPECT_EQ(0u, getNumScatterDims(UMAP("{ A[] -> []; [] -> []}")));
 551   EXPECT_EQ(1u, getNumScatterDims(UMAP("{ A[] -> []; [] -> [i] }")));
 552   EXPECT_EQ(2u, getNumScatterDims(UMAP("{ A[] -> [i]; [] -> [i,j] }")));
 553   EXPECT_EQ(3u, getNumScatterDims(UMAP("{ A[] -> [i]; [] -> [i,j,k] }")));
 554 }
 555
 556 TEST(ISLTools, getScatterSpace) {
 557   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 558                                                         &isl_ctx_free);
 559
 560   // Basic usage
 561   EXPECT_EQ(SPACE("{ [] }"), getScatterSpace(UMAP("{ [] -> [] }")));
 562   EXPECT_EQ(SPACE("{ [i] }"), getScatterSpace(UMAP("{ [] -> [i] }")));
 563   EXPECT_EQ(SPACE("{ [i,j] }"), getScatterSpace(UMAP("{ [] -> [i,j] }")));
 564   EXPECT_EQ(SPACE("{ [i,j,k] }"), getScatterSpace(UMAP("{ [] -> [i,j,k] }")));
 565
 566   // Different scatter spaces
 567   EXPECT_EQ(SPACE("{ [] }"), getScatterSpace(UMAP("{ A[] -> []; [] -> [] }")));
 568   EXPECT_EQ(SPACE("{ [i] }"),
 569             getScatterSpace(UMAP("{ A[] -> []; [] -> [i] }")));
 570   EXPECT_EQ(SPACE("{ [i,j] }"),
 571             getScatterSpace(UMAP("{ A[] -> [i]; [] -> [i,j] }")));
 572   EXPECT_EQ(SPACE("{ [i,j,k] }"),
 573             getScatterSpace(UMAP("{ A[] -> [i]; [] -> [i,j,k] }")));
 574 }
 575
 576 TEST(ISLTools, makeIdentityMap) {
 577   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 578                                                         &isl_ctx_free);
 579
 580   // Basic usage
 581   EXPECT_EQ(UMAP("{ [i] -> [i] }"), makeIdentityMap(USET("{ [0] }"), false));
 582   EXPECT_EQ(UMAP("{ [0] -> [0] }"), makeIdentityMap(USET("{ [0] }"), true));
 583
 584   // Multiple spaces
 585   EXPECT_EQ(UMAP("{ [] -> []; [i] -> [i] }"),
 586             makeIdentityMap(USET("{ []; [0] }"), false));
 587   EXPECT_EQ(UMAP("{ [] -> []; [0] -> [0] }"),
 588             makeIdentityMap(USET("{ []; [0] }"), true));
 589
 590   // Edge case: empty
 591   EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), false));
 592   EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), true));
 593 }
 594
 595 TEST(ISLTools, reverseDomain) {
 596   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 597                                                         &isl_ctx_free);
 598
 599   // Basic usage
 600   EXPECT_EQ(MAP("{ [B[] -> A[]] -> [] }"),
 601             reverseDomain(MAP("{ [A[] -> B[]] -> [] }")));
 602   EXPECT_EQ(UMAP("{ [B[] -> A[]] -> [] }"),
 603             reverseDomain(UMAP("{ [A[] -> B[]] -> [] }")));
 604 }
 605
 606 TEST(ISLTools, shiftDim) {
 607   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 608                                                         &isl_ctx_free);
 609
 610   // Basic usage
 611   EXPECT_EQ(SET("{ [1] }"), shiftDim(SET("{ [0] }"), 0, 1));
 612   EXPECT_EQ(USET("{ [1] }"), shiftDim(USET("{ [0] }"), 0, 1));
 613
 614   // From-end indexing
 615   EXPECT_EQ(USET("{ [0,0,1] }"), shiftDim(USET("{ [0,0,0] }"), -1, 1));
 616   EXPECT_EQ(USET("{ [0,1,0] }"), shiftDim(USET("{ [0,0,0] }"), -2, 1));
 617   EXPECT_EQ(USET("{ [1,0,0] }"), shiftDim(USET("{ [0,0,0] }"), -3, 1));
 618
 619   // Parametrized
 620   EXPECT_EQ(USET("[n] -> { [n+1] }"), shiftDim(USET("[n] -> { [n] }"), 0, 1));
 621
 622   // Union maps
 623   EXPECT_EQ(MAP("{ [1] -> [] }"),
 624             shiftDim(MAP("{ [0] -> [] }"), isl::dim::in, 0, 1));
 625   EXPECT_EQ(UMAP("{ [1] -> [] }"),
 626             shiftDim(UMAP("{ [0] -> [] }"), isl::dim::in, 0, 1));
 627   EXPECT_EQ(MAP("{ [] -> [1] }"),
 628             shiftDim(MAP("{ [] -> [0] }"), isl::dim::out, 0, 1));
 629   EXPECT_EQ(UMAP("{ [] -> [1] }"),
 630             shiftDim(UMAP("{ [] -> [0] }"), isl::dim::out, 0, 1));
 631 }
 632
 633 TEST(DeLICM, computeReachingWrite) {
 634   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 635                                                         &isl_ctx_free);
 636
 637   // Basic usage
 638   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"),
 639             computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
 640                                  UMAP("{ Dom[] -> Elt[] }"), false, false,
 641                                  false));
 642   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"),
 643             computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
 644                                  UMAP("{ Dom[] -> Elt[] }"), false, false,
 645                                  true));
 646   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"),
 647             computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
 648                                  UMAP("{ Dom[] -> Elt[] }"), false, true,
 649                                  false));
 650   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"),
 651             computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
 652                                  UMAP("{ Dom[] -> Elt[] }"), false, true,
 653                                  false));
 654
 655   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"),
 656             computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
 657                                  UMAP("{ Dom[] -> Elt[] }"), true, false,
 658                                  false));
 659   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] :  i <= 0 }"),
 660             computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
 661                                  UMAP("{ Dom[] -> Elt[] }"), true, false,
 662                                  true));
 663   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"),
 664             computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
 665                                  UMAP("{ Dom[] -> Elt[] }"), true, true,
 666                                  false));
 667   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"),
 668             computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
 669                                  UMAP("{ Dom[] -> Elt[] }"), true, true, true));
 670
 671   // Two writes
 672   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 < i < 10; [Elt[] -> [i]] -> "
 673                  "Dom2[] : 10 < i }"),
 674             computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
 675                                  UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
 676                                  false, false, false));
 677   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 <= i < 10; [Elt[] -> [i]] -> "
 678                  "Dom2[] : 10 <= i }"),
 679             computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
 680                                  UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
 681                                  false, true, false));
 682   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 < i <= 10; [Elt[] -> [i]] -> "
 683                  "Dom2[] : 10 < i }"),
 684             computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
 685                                  UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
 686                                  false, false, true));
 687   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 <= i <= 10; [Elt[] -> [i]] -> "
 688                  "Dom2[] : 10 <= i }"),
 689             computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
 690                                  UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
 691                                  false, true, true));
 692
 693   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i < 10; [Elt[] -> [i]] -> "
 694                  "Dom1[] : i < 0 }"),
 695             computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
 696                                  UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
 697                                  true, false, false));
 698   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 <= i < 10; [Elt[] -> [i]] -> "
 699                  "Dom1[] : i < 0 }"),
 700             computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
 701                                  UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
 702                                  true, true, false));
 703   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i <= 10; [Elt[] -> [i]] -> "
 704                  "Dom1[] : i <= 0 }"),
 705             computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
 706                                  UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
 707                                  true, false, true));
 708   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 <= i <= 10; [Elt[] -> [i]] -> "
 709                  "Dom1[] : i <= 0 }"),
 710             computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
 711                                  UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
 712                                  true, true, true));
 713
 714   // Domain in same space
 715   EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[1] : 0 < i <= 10; [Elt[] -> [i]] -> "
 716                  "Dom[2] : 10 < i }"),
 717             computeReachingWrite(UMAP("{ Dom[i] -> [10i - 10] }"),
 718                                  UMAP("{ Dom[1] -> Elt[]; Dom[2] -> Elt[] }"),
 719                                  false, false, true));
 720
 721   // Parametric
 722   EXPECT_EQ(UMAP("[p] -> { [Elt[] -> [i]] -> Dom[] : p < i }"),
 723             computeReachingWrite(UMAP("[p] -> { Dom[] -> [p] }"),
 724                                  UMAP("{ Dom[] -> Elt[] }"), false, false,
 725                                  false));
 726
 727   // More realistic example (from reduction_embedded.ll)
 728   EXPECT_EQ(
 729       UMAP("{ [Elt[] -> [i]] -> Dom[0] : 0 < i <= 3; [Elt[] -> [i]] -> Dom[1] "
 730            ": 3 < i <= 6; [Elt[] -> [i]] -> Dom[2] : 6 < i <= 9; [Elt[] -> "
 731            "[i]] -> Dom[3] : 9 < i <= 12; [Elt[] -> [i]] -> Dom[4] : 12 < i }"),
 732       computeReachingWrite(UMAP("{ Dom[i] -> [3i] : 0 <= i <= 4 }"),
 733                            UMAP("{ Dom[i] -> Elt[] : 0 <= i <= 4 }"), false,
 734                            false, true));
 735 }
 736
 737 TEST(DeLICM, computeArrayUnused) {
 738   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 739                                                         &isl_ctx_free);
 740
 741   // The ReadEltInSameInst parameter doesn't matter in simple cases. To also
 742   // cover the parameter without duplicating the tests, this loops runs over
 743   // other in both settings.
 744   for (bool ReadEltInSameInst = false, Done = false; !Done;
 745        Done = ReadEltInSameInst, ReadEltInSameInst = true) {
 746     // Basic usage: one read, one write
 747     EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i < 10 }"),
 748               computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
 749                                  UMAP("{ Write[] -> Elt[] }"),
 750                                  UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
 751                                  false, false));
 752     EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"),
 753               computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
 754                                  UMAP("{ Write[] -> Elt[] }"),
 755                                  UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
 756                                  false, true));
 757     EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 <= i < 10 }"),
 758               computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
 759                                  UMAP("{ Write[] -> Elt[] }"),
 760                                  UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
 761                                  true, false));
 762     EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 <= i <= 10 }"),
 763               computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
 764                                  UMAP("{ Write[] -> Elt[] }"),
 765                                  UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
 766                                  true, true));
 767
 768     // Two reads
 769     EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"),
 770               computeArrayUnused(
 771                   UMAP("{ Read[0] -> [-10]; Read[1] -> [0]; Write[] -> [10] }"),
 772                   UMAP("{ Write[] -> Elt[] }"), UMAP("{ Read[i] -> Elt[] }"),
 773                   ReadEltInSameInst, false, true));
 774
 775     // Corner case: no writes
 776     EXPECT_EQ(UMAP("{}"),
 777               computeArrayUnused(UMAP("{ Read[] -> [0] }"), UMAP("{}"),
 778                                  UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
 779                                  false, false));
 780
 781     // Corner case: no reads
 782     EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"),
 783               computeArrayUnused(UMAP("{ Write[] -> [0] }"),
 784                                  UMAP("{ Write[] -> Elt[] }"), UMAP("{}"),
 785                                  ReadEltInSameInst, false, true));
 786
 787     // read, write, write
 788     EXPECT_EQ(
 789         UMAP("{ Elt[] -> [i] : 0 < i <= 20 }"),
 790         computeArrayUnused(
 791             UMAP("{ Read[] -> [0]; WriteA[] -> [10];  WriteB[] -> [20] }"),
 792             UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"),
 793             UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, false, true));
 794   }
 795
 796   // Read and write in same statement
 797   EXPECT_EQ(UMAP("{ Elt[] -> [i] : i < 0 }"),
 798             computeArrayUnused(UMAP("{ RW[] -> [0] }"),
 799                                UMAP("{ RW[] -> Elt[] }"),
 800                                UMAP("{ RW[] -> Elt[] }"), true, false, false));
 801   EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"),
 802             computeArrayUnused(UMAP("{ RW[] -> [0] }"),
 803                                UMAP("{ RW[] -> Elt[] }"),
 804                                UMAP("{ RW[] -> Elt[] }"), true, false, true));
 805   EXPECT_EQ(UMAP("{ Elt[] -> [0] }"),
 806             computeArrayUnused(UMAP("{ RW[] -> [0] }"),
 807                                UMAP("{ RW[] -> Elt[] }"),
 808                                UMAP("{ RW[] -> Elt[] }"), false, true, true));
 809 }
 810
 811 TEST(DeLICM, convertZoneToTimepoints) {
 812   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 813                                                         &isl_ctx_free);
 814
 815   // Corner case: empty set
 816   EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), false, false));
 817   EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), true, false));
 818   EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), false, true));
 819   EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), true, true));
 820
 821   // Basic usage
 822   EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{ [1] }"), false, false));
 823   EXPECT_EQ(USET("{ [0] }"),
 824             convertZoneToTimepoints(USET("{ [1] }"), true, false));
 825   EXPECT_EQ(USET("{ [1] }"),
 826             convertZoneToTimepoints(USET("{ [1] }"), false, true));
 827   EXPECT_EQ(USET("{ [0]; [1] }"),
 828             convertZoneToTimepoints(USET("{ [1] }"), true, true));
 829
 830   // Non-adjacent ranges
 831   EXPECT_EQ(USET("{}"),
 832             convertZoneToTimepoints(USET("{ [1]; [11] }"), false, false));
 833   EXPECT_EQ(USET("{ [0]; [10] }"),
 834             convertZoneToTimepoints(USET("{ [1]; [11] }"), true, false));
 835   EXPECT_EQ(USET("{ [1]; [11] }"),
 836             convertZoneToTimepoints(USET("{ [1]; [11] }"), false, true));
 837   EXPECT_EQ(USET("{ [0]; [1]; [10]; [11] }"),
 838             convertZoneToTimepoints(USET("{ [1]; [11] }"), true, true));
 839
 840   // Adjacent unit ranges
 841   EXPECT_EQ(
 842       USET("{ [i] : 0 < i < 10 }"),
 843       convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, false));
 844   EXPECT_EQ(
 845       USET("{ [i] : 0 <= i < 10 }"),
 846       convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, false));
 847   EXPECT_EQ(
 848       USET("{ [i] : 0 < i <= 10 }"),
 849       convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, true));
 850   EXPECT_EQ(USET("{ [i] : 0 <= i <= 10 }"),
 851             convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, true));
 852
 853   // More than one dimension
 854   EXPECT_EQ(USET("{}"),
 855             convertZoneToTimepoints(USET("{ [0,1] }"), false, false));
 856   EXPECT_EQ(USET("{ [0,0] }"),
 857             convertZoneToTimepoints(USET("{ [0,1] }"), true, false));
 858   EXPECT_EQ(USET("{ [0,1] }"),
 859             convertZoneToTimepoints(USET("{ [0,1] }"), false, true));
 860   EXPECT_EQ(USET("{ [0,0]; [0,1] }"),
 861             convertZoneToTimepoints(USET("{ [0,1] }"), true, true));
 862
 863   // Map domains
 864   EXPECT_EQ(UMAP("{}"), convertZoneToTimepoints(UMAP("{ [1] -> [] }"),
 865                                                 isl::dim::in, false, false));
 866   EXPECT_EQ(UMAP("{ [0] -> [] }"),
 867             convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, true,
 868                                     false));
 869   EXPECT_EQ(UMAP("{ [1] -> [] }"),
 870             convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, false,
 871                                     true));
 872   EXPECT_EQ(
 873       UMAP("{ [0] -> []; [1] -> [] }"),
 874       convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, true, true));
 875
 876   // Map ranges
 877   EXPECT_EQ(UMAP("{}"), convertZoneToTimepoints(UMAP("{ [] -> [1] }"),
 878                                                 isl::dim::out, false, false));
 879   EXPECT_EQ(UMAP("{ [] -> [0] }"),
 880             convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, true,
 881                                     false));
 882   EXPECT_EQ(UMAP("{ [] -> [1] }"),
 883             convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, false,
 884                                     true));
 885   EXPECT_EQ(UMAP("{ [] -> [0]; [] -> [1] }"),
 886             convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, true,
 887                                     true));
 888 }
 889
 890 TEST(DeLICM, distribute) {
 891   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 892                                                         &isl_ctx_free);
 893
 894   // Basic usage
 895   EXPECT_EQ(MAP("{ [Domain[] -> Range1[]] -> [Domain[] -> Range2[]] }"),
 896             distributeDomain(MAP("{ Domain[] -> [Range1[] -> Range2[]] }")));
 897   EXPECT_EQ(
 898       MAP("{ [Domain[i,j] -> Range1[i,k]] -> [Domain[i,j] -> Range2[j,k]] }"),
 899       distributeDomain(MAP("{ Domain[i,j] -> [Range1[i,k] -> Range2[j,k]] }")));
 900
 901   // Union maps
 902   EXPECT_EQ(
 903       UMAP(
 904           "{ [DomainA[i,j] -> RangeA1[i,k]] -> [DomainA[i,j] -> RangeA2[j,k]];"
 905           "[DomainB[i,j] -> RangeB1[i,k]] -> [DomainB[i,j] -> RangeB2[j,k]] }"),
 906       distributeDomain(
 907           UMAP("{ DomainA[i,j] -> [RangeA1[i,k] -> RangeA2[j,k]];"
 908                "DomainB[i,j] -> [RangeB1[i,k] -> RangeB2[j,k]] }")));
 909 }
 910
 911 TEST(DeLICM, lift) {
 912   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 913                                                         &isl_ctx_free);
 914
 915   // Basic usage
 916   EXPECT_EQ(UMAP("{ [Factor[] -> Domain[]] -> [Factor[] -> Range[]] }"),
 917             liftDomains(UMAP("{ Domain[] -> Range[] }"), USET("{ Factor[] }")));
 918   EXPECT_EQ(UMAP("{ [Factor[l] -> Domain[i,k]] -> [Factor[l] -> Range[j,k]] }"),
 919             liftDomains(UMAP("{ Domain[i,k] -> Range[j,k] }"),
 920                         USET("{ Factor[l] }")));
 921
 922   // Multiple maps in union
 923   EXPECT_EQ(
 924       UMAP("{ [FactorA[] -> DomainA[]] -> [FactorA[] -> RangeA[]];"
 925            "[FactorB[] -> DomainA[]] -> [FactorB[] -> RangeA[]];"
 926            "[FactorA[] -> DomainB[]] -> [FactorA[] -> RangeB[]];"
 927            "[FactorB[] -> DomainB[]] -> [FactorB[] -> RangeB[]] }"),
 928       liftDomains(UMAP("{ DomainA[] -> RangeA[]; DomainB[] -> RangeB[] }"),
 929                   USET("{ FactorA[]; FactorB[] }")));
 930 }
 931
 932 TEST(DeLICM, apply) {
 933   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 934                                                         &isl_ctx_free);
 935
 936   // Basic usage
 937   EXPECT_EQ(
 938       UMAP("{ [DomainDomain[] -> NewDomainRange[]] -> Range[] }"),
 939       applyDomainRange(UMAP("{ [DomainDomain[] -> DomainRange[]] -> Range[] }"),
 940                        UMAP("{ DomainRange[] -> NewDomainRange[] }")));
 941   EXPECT_EQ(
 942       UMAP("{ [DomainDomain[i,k] -> NewDomainRange[j,k,l]] -> Range[i,j] }"),
 943       applyDomainRange(
 944           UMAP("{ [DomainDomain[i,k] -> DomainRange[j,k]] -> Range[i,j] }"),
 945           UMAP("{ DomainRange[j,k] -> NewDomainRange[j,k,l] }")));
 946
 947   // Multiple maps in union
 948   EXPECT_EQ(UMAP("{ [DomainDomainA[] -> NewDomainRangeA[]] -> RangeA[];"
 949                  "[DomainDomainB[] -> NewDomainRangeB[]] -> RangeB[] }"),
 950             applyDomainRange(
 951                 UMAP("{ [DomainDomainA[] -> DomainRangeA[]] -> RangeA[];"
 952                      "[DomainDomainB[] -> DomainRangeB[]] -> RangeB[] }"),
 953                 UMAP("{ DomainRangeA[] -> NewDomainRangeA[];"
 954                      "DomainRangeB[] -> NewDomainRangeB[] }")));
 955 }
 956
 957 } // anonymous namespace