polly/unittests/Isl/IslTest.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-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "polly/Support/GICHelper.h"
  10 #include "polly/Support/ISLOperators.h"
  11 #include "polly/Support/ISLTools.h"
  12 #include "gtest/gtest.h"
  13 #include "isl/stream.h"
  14 #include "isl/val.h"
  15
  16 using namespace llvm;
  17 using namespace polly;
  18
  19 static isl::space parseSpace(isl_ctx *Ctx, const char *Str) {
  20   isl_stream *Stream = isl_stream_new_str(Ctx, Str);
  21   auto Obj = isl_stream_read_obj(Stream);
  22
  23   isl::space Result;
  24   if (Obj.type == isl_obj_set)
  25     Result = isl::manage(isl_set_get_space(static_cast<isl_set *>(Obj.v)));
  26   else if (Obj.type == isl_obj_map)
  27     Result = isl::manage(isl_map_get_space(static_cast<isl_map *>(Obj.v)));
  28
  29   isl_stream_free(Stream);
  30   if (Obj.type)
  31     Obj.type->free(Obj.v);
  32   return Result;
  33 }
  34
  35 #define SPACE(Str) parseSpace(Ctx.get(), Str)
  36
  37 #define SET(Str) isl::set(Ctx.get(), Str)
  38 #define MAP(Str) isl::map(Ctx.get(), Str)
  39
  40 #define USET(Str) isl::union_set(Ctx.get(), Str)
  41 #define UMAP(Str) isl::union_map(Ctx.get(), Str)
  42
  43 namespace isl {
  44 inline namespace noexceptions {
  45
  46 static bool operator==(const isl::space &LHS, const isl::space &RHS) {
  47   return bool(LHS.is_equal(RHS));
  48 }
  49
  50 static bool operator==(const isl::set &LHS, const isl::set &RHS) {
  51   return bool(LHS.is_equal(RHS));
  52 }
  53
  54 static bool operator==(const isl::map &LHS, const isl::map &RHS) {
  55   return bool(LHS.is_equal(RHS));
  56 }
  57
  58 static bool operator==(const isl::union_set &LHS, const isl::union_set &RHS) {
  59   return bool(LHS.is_equal(RHS));
  60 }
  61
  62 static bool operator==(const isl::union_map &LHS, const isl::union_map &RHS) {
  63   return bool(LHS.is_equal(RHS));
  64 }
  65
  66 static bool operator==(const isl::val &LHS, const isl::val &RHS) {
  67   return bool(LHS.eq(RHS));
  68 }
  69
  70 static bool operator==(const isl::pw_aff &LHS, const isl::pw_aff &RHS) {
  71   return bool(LHS.is_equal(RHS));
  72 }
  73 } // namespace noexceptions
  74 } // namespace isl
  75
  76 namespace {
  77
  78 TEST(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
 155 TEST(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
 280 TEST(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   // Addition
 306   {
 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   // Multiplication
 315   {
 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   // Subtraction
 324   {
 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   // Division
 333   {
 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   // Remainder
 356   {
 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
 379 TEST(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(TestMap
 453                     .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(TestUMap
 465                     .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
 489 TEST(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_map
 494   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_map
 500   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 dimension
 506   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   // Functional
 512   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   // Parametrized
 518   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 range
 524   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: empty
 530   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
 536 TEST(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_map
 541   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_map
 547   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 dimension
 553   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   // Functional
 559   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   // Parametrized
 565   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 range
 571   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: empty
 577   EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), false));
 578   EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), true));
 579 }
 580
 581 TEST(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_map
 586   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_map
 600   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
 614 TEST(ISLTools, singleton) {
 615   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 616                                                         &isl_ctx_free);
 617
 618   // No element found
 619   EXPECT_EQ(SET("{ [] : 1 = 0 }"), singleton(USET("{ }"), SPACE("{ [] }")));
 620   EXPECT_EQ(MAP("{ [] -> [] : 1 = 0  }"),
 621             singleton(UMAP("{  }"), SPACE("{ [] -> [] }")));
 622
 623   // One element found
 624   EXPECT_EQ(SET("{ [] }"), singleton(USET("{ [] }"), SPACE("{ [] }")));
 625   EXPECT_EQ(MAP("{ [] -> [] }"),
 626             singleton(UMAP("{ [] -> [] }"), SPACE("{ [] -> [] }")));
 627
 628   // Many elements found
 629   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 parameters
 636   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
 642 TEST(ISLTools, getNumScatterDims) {
 643   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 644                                                         &isl_ctx_free);
 645
 646   // Basic usage
 647   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 spaces
 653   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
 659 TEST(ISLTools, getScatterSpace) {
 660   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 661                                                         &isl_ctx_free);
 662
 663   // Basic usage
 664   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 spaces
 670   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
 679 TEST(ISLTools, makeIdentityMap) {
 680   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 681                                                         &isl_ctx_free);
 682
 683   // Basic usage
 684   EXPECT_EQ(UMAP("{ [i] -> [i] }"), makeIdentityMap(USET("{ [0] }"), false));
 685   EXPECT_EQ(UMAP("{ [0] -> [0] }"), makeIdentityMap(USET("{ [0] }"), true));
 686
 687   // Multiple spaces
 688   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: empty
 694   EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), false));
 695   EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), true));
 696 }
 697
 698 TEST(ISLTools, reverseDomain) {
 699   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 700                                                         &isl_ctx_free);
 701
 702   // Basic usage
 703   EXPECT_EQ(MAP("{ [B[] -> A[]] -> [] }"),
 704             reverseDomain(MAP("{ [A[] -> B[]] -> [] }")));
 705   EXPECT_EQ(UMAP("{ [B[] -> A[]] -> [] }"),
 706             reverseDomain(UMAP("{ [A[] -> B[]] -> [] }")));
 707 }
 708
 709 TEST(ISLTools, shiftDim) {
 710   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 711                                                         &isl_ctx_free);
 712
 713   // Basic usage
 714   EXPECT_EQ(SET("{ [1] }"), shiftDim(SET("{ [0] }"), 0, 1));
 715   EXPECT_EQ(USET("{ [1] }"), shiftDim(USET("{ [0] }"), 0, 1));
 716
 717   // From-end indexing
 718   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   // Parametrized
 723   EXPECT_EQ(USET("[n] -> { [n+1] }"), shiftDim(USET("[n] -> { [n] }"), 0, 1));
 724
 725   // Union maps
 726   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
 736 TEST(DeLICM, computeReachingWrite) {
 737   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
 738                                                         &isl_ctx_free);
 739
 740   // Basic usage
 741   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 writes
 775   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 space
 818   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   // Parametric
 825   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
 840 TEST(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 also
 845   // cover the parameter without duplicating the tests, this loops runs over
 846   // other in both settings.
 847   for (bool ReadEltInSameInst = false, Done = false; !Done;
 848        Done = ReadEltInSameInst, ReadEltInSameInst = true) {
 849     // Basic usage: one read, one write
 850     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 reads
 872     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 writes
 879     EXPECT_EQ(UMAP("{}"),
 880               computeArrayUnused(UMAP("{ Read[] -> [0] }"), UMAP("{}"),
 881                                  UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
 882                                  false, false));
 883
 884     // Corner case: no reads
 885     EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"),
 886               computeArrayUnused(UMAP("{ Write[] -> [0] }"),
 887                                  UMAP("{ Write[] -> Elt[] }"), UMAP("{}"),
 888                                  ReadEltInSameInst, false, true));
 889
 890     // Two writes
 891     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 zones
 898     // read,write,read,write
 899     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, write
 908     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, read
 916     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, read
 923     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, write
 931     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, read
 939     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 statement
 949   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
 963 TEST(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 set
 968   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 usage
 974   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 ranges
 983   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 ranges
 993   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 dimension
1006   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 domains
1016   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 ranges
1029   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
1042 TEST(DeLICM, distribute) {
1043   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
1044                                                         &isl_ctx_free);
1045
1046   // Basic usage
1047   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 maps
1054   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
1063 TEST(DeLICM, lift) {
1064   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
1065                                                         &isl_ctx_free);
1066
1067   // Basic usage
1068   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 union
1075   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
1084 TEST(DeLICM, apply) {
1085   std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
1086                                                         &isl_ctx_free);
1087
1088   // Basic usage
1089   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 union
1100   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
1109 TEST(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 one
1123     // 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 namespace