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