[RuntimeDebugBuilder] Do not break for 64 bit integers
[polly-mirror.git] / unittests / Isl / IslTest.cpp
blob9b6dac11c54f3fd4f3b8980ffb9f76528c99f7f2
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 //===----------------------------------------------------------------------===//
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"
17 using namespace llvm;
18 using namespace polly;
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);
24 isl::space Result;
25 if (Obj.type == isl_obj_set)
26 Result = give(isl_set_get_space(static_cast<isl_set *>(Obj.v)));
27 else if (Obj.type == isl_obj_map)
28 Result = give(isl_map_get_space(static_cast<isl_map *>(Obj.v)));
30 isl_stream_free(Stream);
31 if (Obj.type)
32 Obj.type->free(Obj.v);
33 return Result;
36 #define SPACE(Str) parseSpace(Ctx.get(), Str)
38 #define SET(Str) isl::set(Ctx.get(), Str)
39 #define MAP(Str) isl::map(Ctx.get(), Str)
41 #define USET(Str) isl::union_set(Ctx.get(), Str)
42 #define UMAP(Str) isl::union_map(Ctx.get(), Str)
44 namespace isl {
45 inline namespace noexceptions {
47 static bool operator==(const isl::space &LHS, const isl::space &RHS) {
48 return bool(LHS.is_equal(RHS));
51 static bool operator==(const isl::basic_set &LHS, const isl::basic_set &RHS) {
52 return bool(LHS.is_equal(RHS));
55 static bool operator==(const isl::set &LHS, const isl::set &RHS) {
56 return bool(LHS.is_equal(RHS));
59 static bool operator==(const isl::basic_map &LHS, const isl::basic_map &RHS) {
60 return bool(LHS.is_equal(RHS));
63 static bool operator==(const isl::map &LHS, const isl::map &RHS) {
64 return bool(LHS.is_equal(RHS));
67 static bool operator==(const isl::union_set &LHS, const isl::union_set &RHS) {
68 return bool(LHS.is_equal(RHS));
71 static bool operator==(const isl::union_map &LHS, const isl::union_map &RHS) {
72 return bool(LHS.is_equal(RHS));
75 static bool operator==(const isl::val &LHS, const isl::val &RHS) {
76 return bool(LHS.eq(RHS));
79 static bool operator==(const isl::pw_aff &LHS, const isl::pw_aff &RHS) {
80 return bool(LHS.is_equal(RHS));
82 } // namespace noexceptions
83 } // namespace isl
85 namespace {
87 TEST(Isl, APIntToIslVal) {
88 isl_ctx *IslCtx = isl_ctx_alloc();
91 APInt APZero(1, 0, true);
92 auto IslZero = valFromAPInt(IslCtx, APZero, true);
93 EXPECT_TRUE(IslZero.is_zero());
97 APInt APNOne(1, -1, true);
98 auto IslNOne = valFromAPInt(IslCtx, APNOne, true);
99 EXPECT_TRUE(IslNOne.is_negone());
103 APInt APZero(1, 0, false);
104 auto IslZero = valFromAPInt(IslCtx, APZero, false);
105 EXPECT_TRUE(IslZero.is_zero());
109 APInt APOne(1, 1, false);
110 auto IslOne = valFromAPInt(IslCtx, APOne, false);
111 EXPECT_TRUE(IslOne.is_one());
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);
122 APInt APNOne(32, -1, true);
123 auto IslNOne = valFromAPInt(IslCtx, APNOne, true);
124 EXPECT_TRUE(IslNOne.is_negone());
128 APInt APZero(32, 0, false);
129 auto IslZero = valFromAPInt(IslCtx, APZero, false);
130 EXPECT_TRUE(IslZero.is_zero());
134 APInt APOne(32, 1, false);
135 auto IslOne = valFromAPInt(IslCtx, APOne, false);
136 EXPECT_TRUE(IslOne.is_one());
140 APInt APTwo(32, 2, false);
141 auto IslTwo = valFromAPInt(IslCtx, APTwo, false);
142 EXPECT_EQ(0, IslTwo.cmp_si(2));
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);
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);
161 isl_ctx_free(IslCtx);
164 TEST(Isl, IslValToAPInt) {
165 isl_ctx *IslCtx = isl_ctx_alloc();
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());
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());
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());
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());
200 auto IslZero = isl::val(IslCtx, 0);
201 auto APZero = APIntFromVal(IslZero);
202 EXPECT_EQ(0, APZero);
203 EXPECT_EQ(1u, APZero.getBitWidth());
207 auto IslOne = isl::val(IslCtx, 1);
208 auto APOne = APIntFromVal(IslOne);
209 EXPECT_EQ(1, APOne);
210 EXPECT_EQ(2u, APOne.getBitWidth());
214 auto IslTwo = isl::val(IslCtx, 2);
215 auto APTwo = APIntFromVal(IslTwo);
216 EXPECT_EQ(2, APTwo);
217 EXPECT_EQ(3u, APTwo.getBitWidth());
221 auto IslThree = isl::val(IslCtx, 3);
222 auto APThree = APIntFromVal(IslThree);
223 EXPECT_EQ(3, APThree);
224 EXPECT_EQ(3u, APThree.getBitWidth());
228 auto IslFour = isl::val(IslCtx, 4);
229 auto APFour = APIntFromVal(IslFour);
230 EXPECT_EQ(4, APFour);
231 EXPECT_EQ(4u, APFour.getBitWidth());
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());
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());
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());
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());
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());
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());
286 isl_ctx_free(IslCtx);
289 TEST(Isl, Operators) {
290 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> IslCtx(isl_ctx_alloc(),
291 &isl_ctx_free);
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);
302 isl::space Space = isl::space(IslCtx.get(), 0, 0);
303 isl::local_space LS = isl::local_space(Space);
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);
314 // Addition
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);
323 // Multiplication
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);
332 // Subtraction
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);
341 // Division
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);
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);
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);
364 // Remainder
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);
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);
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);
388 TEST(Isl, Foreach) {
389 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
390 &isl_ctx_free);
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;
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;
405 auto NumBMaps = 0;
406 TestMap.foreach_basic_map([&](isl::basic_map BMap) -> isl::stat {
407 EXPECT_EQ(BMap, TestBMap);
408 NumBMaps++;
409 return isl::stat::ok;
411 EXPECT_EQ(1, NumBMaps);
415 auto NumBSets = 0;
416 TestSet.foreach_basic_set([&](isl::basic_set BSet) -> isl::stat {
417 EXPECT_EQ(BSet, TestBSet);
418 NumBSets++;
419 return isl::stat::ok;
421 EXPECT_EQ(1, NumBSets);
425 auto NumMaps = 0;
426 TestUMap.foreach_map([&](isl::map Map) -> isl::stat {
427 EXPECT_EQ(Map, TestMap);
428 NumMaps++;
429 return isl::stat::ok;
431 EXPECT_EQ(1, NumMaps);
435 auto NumSets = 0;
436 TestUSet.foreach_set([&](isl::set Set) -> isl::stat {
437 EXPECT_EQ(Set, TestSet);
438 NumSets++;
439 return isl::stat::ok;
441 EXPECT_EQ(1, NumSets);
445 auto UPwAff = isl::union_pw_aff(TestUSet, isl::val::zero(Ctx.get()));
446 auto NumPwAffs = 0;
447 UPwAff.foreach_pw_aff([&](isl::pw_aff PwAff) -> isl::stat {
448 EXPECT_TRUE(PwAff.is_cst());
449 NumPwAffs++;
450 return isl::stat::ok;
452 EXPECT_EQ(1, NumPwAffs);
456 auto NumBMaps = 0;
457 EXPECT_EQ(isl::stat::error,
458 TestMap.foreach_basic_map([&](isl::basic_map BMap) -> isl::stat {
459 EXPECT_EQ(BMap, TestBMap);
460 NumBMaps++;
461 return isl::stat::error;
462 }));
463 EXPECT_EQ(1, NumBMaps);
467 auto NumMaps = 0;
468 EXPECT_EQ(isl::stat::error,
469 TestUMap.foreach_map([&](isl::map Map) -> isl::stat {
470 EXPECT_EQ(Map, TestMap);
471 NumMaps++;
472 return isl::stat::error;
473 }));
474 EXPECT_EQ(1, NumMaps);
478 auto TestPwAff = isl::pw_aff(TestSet, isl::val::zero(Ctx.get()));
479 auto NumPieces = 0;
480 TestPwAff.foreach_piece([&](isl::set Domain, isl::aff Aff) -> isl::stat {
481 EXPECT_EQ(Domain, TestSet);
482 EXPECT_TRUE(Aff.is_cst());
483 NumPieces++;
484 return isl::stat::error;
486 EXPECT_EQ(1, NumPieces);
490 TEST(ISLTools, beforeScatter) {
491 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
492 &isl_ctx_free);
494 // Basic usage with isl_map
495 EXPECT_EQ(MAP("{ [] -> [i] : i <= 0 }"),
496 beforeScatter(MAP("{ [] -> [0] }"), false));
497 EXPECT_EQ(MAP("{ [] -> [i] : i < 0 }"),
498 beforeScatter(MAP("{ [] -> [0] }"), true));
500 // Basic usage with isl_union_map
501 EXPECT_EQ(UMAP("{ A[] -> [i] : i <= 0; B[] -> [i] : i <= 0 }"),
502 beforeScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), false));
503 EXPECT_EQ(UMAP("{ A[] -> [i] : i < 0; B[] -> [i] : i < 0 }"),
504 beforeScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), true));
506 // More than one dimension
507 EXPECT_EQ(UMAP("{ [] -> [i, j] : i < 0; [] -> [i, j] : i = 0 and j <= 0 }"),
508 beforeScatter(UMAP("{ [] -> [0, 0] }"), false));
509 EXPECT_EQ(UMAP("{ [] -> [i, j] : i < 0; [] -> [i, j] : i = 0 and j < 0 }"),
510 beforeScatter(UMAP("{ [] -> [0, 0] }"), true));
512 // Functional
513 EXPECT_EQ(UMAP("{ [i] -> [j] : j <= i }"),
514 beforeScatter(UMAP("{ [i] -> [i] }"), false));
515 EXPECT_EQ(UMAP("{ [i] -> [j] : j < i }"),
516 beforeScatter(UMAP("{ [i] -> [i] }"), true));
518 // Parametrized
519 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j <= i }"),
520 beforeScatter(UMAP("[i] -> { [] -> [i] }"), false));
521 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j < i }"),
522 beforeScatter(UMAP("[i] -> { [] -> [i] }"), true));
524 // More than one range
525 EXPECT_EQ(UMAP("{ [] -> [i] : i <= 10 }"),
526 beforeScatter(UMAP("{ [] -> [0]; [] -> [10] }"), false));
527 EXPECT_EQ(UMAP("{ [] -> [i] : i < 10 }"),
528 beforeScatter(UMAP("{ [] -> [0]; [] -> [10] }"), true));
530 // Edge case: empty
531 EXPECT_EQ(UMAP("{ [] -> [i] : 1 = 0 }"),
532 beforeScatter(UMAP("{ [] -> [i] : 1 = 0 }"), false));
533 EXPECT_EQ(UMAP("{ [] -> [i] : 1 = 0 }"),
534 beforeScatter(UMAP("{ [] -> [i] : 1 = 0 }"), true));
537 TEST(ISLTools, afterScatter) {
538 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
539 &isl_ctx_free);
541 // Basic usage with isl_map
542 EXPECT_EQ(MAP("{ [] -> [i] : i >= 0 }"),
543 afterScatter(MAP("{ [] -> [0] }"), false));
544 EXPECT_EQ(MAP("{ [] -> [i] : i > 0 }"),
545 afterScatter(MAP("{ [] -> [0] }"), true));
547 // Basic usage with isl_union_map
548 EXPECT_EQ(UMAP("{ A[] -> [i] : i >= 0; B[] -> [i] : i >= 0 }"),
549 afterScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), false));
550 EXPECT_EQ(UMAP("{ A[] -> [i] : i > 0; B[] -> [i] : i > 0 }"),
551 afterScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), true));
553 // More than one dimension
554 EXPECT_EQ(UMAP("{ [] -> [i, j] : i > 0; [] -> [i, j] : i = 0 and j >= 0 }"),
555 afterScatter(UMAP("{ [] -> [0, 0] }"), false));
556 EXPECT_EQ(UMAP("{ [] -> [i, j] : i > 0; [] -> [i, j] : i = 0 and j > 0 }"),
557 afterScatter(UMAP("{ [] -> [0, 0] }"), true));
559 // Functional
560 EXPECT_EQ(UMAP("{ [i] -> [j] : j >= i }"),
561 afterScatter(UMAP("{ [i] -> [i] }"), false));
562 EXPECT_EQ(UMAP("{ [i] -> [j] : j > i }"),
563 afterScatter(UMAP("{ [i] -> [i] }"), true));
565 // Parametrized
566 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j >= i }"),
567 afterScatter(UMAP("[i] -> { [] -> [i] }"), false));
568 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j > i }"),
569 afterScatter(UMAP("[i] -> { [] -> [i] }"), true));
571 // More than one range
572 EXPECT_EQ(UMAP("{ [] -> [i] : i >= 0 }"),
573 afterScatter(UMAP("{ [] -> [0]; [] -> [10] }"), false));
574 EXPECT_EQ(UMAP("{ [] -> [i] : i > 0 }"),
575 afterScatter(UMAP("{ [] -> [0]; [] -> [10] }"), true));
577 // Edge case: empty
578 EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), false));
579 EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), true));
582 TEST(ISLTools, betweenScatter) {
583 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
584 &isl_ctx_free);
586 // Basic usage with isl_map
587 EXPECT_EQ(MAP("{ [] -> [i] : 0 < i < 10 }"),
588 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false,
589 false));
590 EXPECT_EQ(
591 MAP("{ [] -> [i] : 0 <= i < 10 }"),
592 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, false));
593 EXPECT_EQ(
594 MAP("{ [] -> [i] : 0 < i <= 10 }"),
595 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false, true));
596 EXPECT_EQ(
597 MAP("{ [] -> [i] : 0 <= i <= 10 }"),
598 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, true));
600 // Basic usage with isl_union_map
601 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 < i < 10; B[] -> [i] : 0 < i < 10 }"),
602 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
603 UMAP("{ A[] -> [10]; B[] -> [10] }"), false, false));
604 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 <= i < 10; B[] -> [i] : 0 <= i < 10 }"),
605 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
606 UMAP("{ A[] -> [10]; B[] -> [10] }"), true, false));
607 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 < i <= 10; B[] -> [i] : 0 < i <= 10 }"),
608 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
609 UMAP("{ A[] -> [10]; B[] -> [10] }"), false, true));
610 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 <= i <= 10; B[] -> [i] : 0 <= i <= 10 }"),
611 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
612 UMAP("{ A[] -> [10]; B[] -> [10] }"), true, true));
615 TEST(ISLTools, singleton) {
616 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
617 &isl_ctx_free);
619 // No element found
620 EXPECT_EQ(SET("{ [] : 1 = 0 }"), singleton(USET("{ }"), SPACE("{ [] }")));
621 EXPECT_EQ(MAP("{ [] -> [] : 1 = 0 }"),
622 singleton(UMAP("{ }"), SPACE("{ [] -> [] }")));
624 // One element found
625 EXPECT_EQ(SET("{ [] }"), singleton(USET("{ [] }"), SPACE("{ [] }")));
626 EXPECT_EQ(MAP("{ [] -> [] }"),
627 singleton(UMAP("{ [] -> [] }"), SPACE("{ [] -> [] }")));
629 // Many elements found
630 EXPECT_EQ(SET("{ [i] : 0 <= i < 10 }"),
631 singleton(USET("{ [i] : 0 <= i < 10 }"), SPACE("{ [i] }")));
632 EXPECT_EQ(
633 MAP("{ [i] -> [i] : 0 <= i < 10 }"),
634 singleton(UMAP("{ [i] -> [i] : 0 <= i < 10 }"), SPACE("{ [i] -> [j] }")));
636 // Different parameters
637 EXPECT_EQ(SET("[i] -> { [i] }"),
638 singleton(USET("[i] -> { [i] }"), SPACE("{ [i] }")));
639 EXPECT_EQ(MAP("[i] -> { [i] -> [i] }"),
640 singleton(UMAP("[i] -> { [i] -> [i] }"), SPACE("{ [i] -> [j] }")));
643 TEST(ISLTools, getNumScatterDims) {
644 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
645 &isl_ctx_free);
647 // Basic usage
648 EXPECT_EQ(0u, getNumScatterDims(UMAP("{ [] -> [] }")));
649 EXPECT_EQ(1u, getNumScatterDims(UMAP("{ [] -> [i] }")));
650 EXPECT_EQ(2u, getNumScatterDims(UMAP("{ [] -> [i,j] }")));
651 EXPECT_EQ(3u, getNumScatterDims(UMAP("{ [] -> [i,j,k] }")));
653 // Different scatter spaces
654 EXPECT_EQ(0u, getNumScatterDims(UMAP("{ A[] -> []; [] -> []}")));
655 EXPECT_EQ(1u, getNumScatterDims(UMAP("{ A[] -> []; [] -> [i] }")));
656 EXPECT_EQ(2u, getNumScatterDims(UMAP("{ A[] -> [i]; [] -> [i,j] }")));
657 EXPECT_EQ(3u, getNumScatterDims(UMAP("{ A[] -> [i]; [] -> [i,j,k] }")));
660 TEST(ISLTools, getScatterSpace) {
661 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
662 &isl_ctx_free);
664 // Basic usage
665 EXPECT_EQ(SPACE("{ [] }"), getScatterSpace(UMAP("{ [] -> [] }")));
666 EXPECT_EQ(SPACE("{ [i] }"), getScatterSpace(UMAP("{ [] -> [i] }")));
667 EXPECT_EQ(SPACE("{ [i,j] }"), getScatterSpace(UMAP("{ [] -> [i,j] }")));
668 EXPECT_EQ(SPACE("{ [i,j,k] }"), getScatterSpace(UMAP("{ [] -> [i,j,k] }")));
670 // Different scatter spaces
671 EXPECT_EQ(SPACE("{ [] }"), getScatterSpace(UMAP("{ A[] -> []; [] -> [] }")));
672 EXPECT_EQ(SPACE("{ [i] }"),
673 getScatterSpace(UMAP("{ A[] -> []; [] -> [i] }")));
674 EXPECT_EQ(SPACE("{ [i,j] }"),
675 getScatterSpace(UMAP("{ A[] -> [i]; [] -> [i,j] }")));
676 EXPECT_EQ(SPACE("{ [i,j,k] }"),
677 getScatterSpace(UMAP("{ A[] -> [i]; [] -> [i,j,k] }")));
680 TEST(ISLTools, makeIdentityMap) {
681 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
682 &isl_ctx_free);
684 // Basic usage
685 EXPECT_EQ(UMAP("{ [i] -> [i] }"), makeIdentityMap(USET("{ [0] }"), false));
686 EXPECT_EQ(UMAP("{ [0] -> [0] }"), makeIdentityMap(USET("{ [0] }"), true));
688 // Multiple spaces
689 EXPECT_EQ(UMAP("{ [] -> []; [i] -> [i] }"),
690 makeIdentityMap(USET("{ []; [0] }"), false));
691 EXPECT_EQ(UMAP("{ [] -> []; [0] -> [0] }"),
692 makeIdentityMap(USET("{ []; [0] }"), true));
694 // Edge case: empty
695 EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), false));
696 EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), true));
699 TEST(ISLTools, reverseDomain) {
700 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
701 &isl_ctx_free);
703 // Basic usage
704 EXPECT_EQ(MAP("{ [B[] -> A[]] -> [] }"),
705 reverseDomain(MAP("{ [A[] -> B[]] -> [] }")));
706 EXPECT_EQ(UMAP("{ [B[] -> A[]] -> [] }"),
707 reverseDomain(UMAP("{ [A[] -> B[]] -> [] }")));
710 TEST(ISLTools, shiftDim) {
711 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
712 &isl_ctx_free);
714 // Basic usage
715 EXPECT_EQ(SET("{ [1] }"), shiftDim(SET("{ [0] }"), 0, 1));
716 EXPECT_EQ(USET("{ [1] }"), shiftDim(USET("{ [0] }"), 0, 1));
718 // From-end indexing
719 EXPECT_EQ(USET("{ [0,0,1] }"), shiftDim(USET("{ [0,0,0] }"), -1, 1));
720 EXPECT_EQ(USET("{ [0,1,0] }"), shiftDim(USET("{ [0,0,0] }"), -2, 1));
721 EXPECT_EQ(USET("{ [1,0,0] }"), shiftDim(USET("{ [0,0,0] }"), -3, 1));
723 // Parametrized
724 EXPECT_EQ(USET("[n] -> { [n+1] }"), shiftDim(USET("[n] -> { [n] }"), 0, 1));
726 // Union maps
727 EXPECT_EQ(MAP("{ [1] -> [] }"),
728 shiftDim(MAP("{ [0] -> [] }"), isl::dim::in, 0, 1));
729 EXPECT_EQ(UMAP("{ [1] -> [] }"),
730 shiftDim(UMAP("{ [0] -> [] }"), isl::dim::in, 0, 1));
731 EXPECT_EQ(MAP("{ [] -> [1] }"),
732 shiftDim(MAP("{ [] -> [0] }"), isl::dim::out, 0, 1));
733 EXPECT_EQ(UMAP("{ [] -> [1] }"),
734 shiftDim(UMAP("{ [] -> [0] }"), isl::dim::out, 0, 1));
737 TEST(DeLICM, computeReachingWrite) {
738 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
739 &isl_ctx_free);
741 // Basic usage
742 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"),
743 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
744 UMAP("{ Dom[] -> Elt[] }"), false, false,
745 false));
746 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"),
747 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
748 UMAP("{ Dom[] -> Elt[] }"), false, false,
749 true));
750 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"),
751 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
752 UMAP("{ Dom[] -> Elt[] }"), false, true,
753 false));
754 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"),
755 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
756 UMAP("{ Dom[] -> Elt[] }"), false, true,
757 false));
759 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"),
760 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
761 UMAP("{ Dom[] -> Elt[] }"), true, false,
762 false));
763 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"),
764 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
765 UMAP("{ Dom[] -> Elt[] }"), true, false,
766 true));
767 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"),
768 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
769 UMAP("{ Dom[] -> Elt[] }"), true, true,
770 false));
771 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"),
772 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
773 UMAP("{ Dom[] -> Elt[] }"), true, true, true));
775 // Two writes
776 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 < i < 10; [Elt[] -> [i]] -> "
777 "Dom2[] : 10 < i }"),
778 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
779 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
780 false, false, false));
781 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 <= i < 10; [Elt[] -> [i]] -> "
782 "Dom2[] : 10 <= i }"),
783 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
784 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
785 false, true, false));
786 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 < i <= 10; [Elt[] -> [i]] -> "
787 "Dom2[] : 10 < i }"),
788 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
789 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
790 false, false, true));
791 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 <= i <= 10; [Elt[] -> [i]] -> "
792 "Dom2[] : 10 <= i }"),
793 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
794 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
795 false, true, true));
797 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i < 10; [Elt[] -> [i]] -> "
798 "Dom1[] : i < 0 }"),
799 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
800 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
801 true, false, false));
802 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 <= i < 10; [Elt[] -> [i]] -> "
803 "Dom1[] : i < 0 }"),
804 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
805 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
806 true, true, false));
807 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i <= 10; [Elt[] -> [i]] -> "
808 "Dom1[] : i <= 0 }"),
809 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
810 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
811 true, false, true));
812 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 <= i <= 10; [Elt[] -> [i]] -> "
813 "Dom1[] : i <= 0 }"),
814 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
815 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
816 true, true, true));
818 // Domain in same space
819 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[1] : 0 < i <= 10; [Elt[] -> [i]] -> "
820 "Dom[2] : 10 < i }"),
821 computeReachingWrite(UMAP("{ Dom[i] -> [10i - 10] }"),
822 UMAP("{ Dom[1] -> Elt[]; Dom[2] -> Elt[] }"),
823 false, false, true));
825 // Parametric
826 EXPECT_EQ(UMAP("[p] -> { [Elt[] -> [i]] -> Dom[] : p < i }"),
827 computeReachingWrite(UMAP("[p] -> { Dom[] -> [p] }"),
828 UMAP("{ Dom[] -> Elt[] }"), false, false,
829 false));
831 // More realistic example (from reduction_embedded.ll)
832 EXPECT_EQ(
833 UMAP("{ [Elt[] -> [i]] -> Dom[0] : 0 < i <= 3; [Elt[] -> [i]] -> Dom[1] "
834 ": 3 < i <= 6; [Elt[] -> [i]] -> Dom[2] : 6 < i <= 9; [Elt[] -> "
835 "[i]] -> Dom[3] : 9 < i <= 12; [Elt[] -> [i]] -> Dom[4] : 12 < i }"),
836 computeReachingWrite(UMAP("{ Dom[i] -> [3i] : 0 <= i <= 4 }"),
837 UMAP("{ Dom[i] -> Elt[] : 0 <= i <= 4 }"), false,
838 false, true));
841 TEST(DeLICM, computeArrayUnused) {
842 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
843 &isl_ctx_free);
845 // The ReadEltInSameInst parameter doesn't matter in simple cases. To also
846 // cover the parameter without duplicating the tests, this loops runs over
847 // other in both settings.
848 for (bool ReadEltInSameInst = false, Done = false; !Done;
849 Done = ReadEltInSameInst, ReadEltInSameInst = true) {
850 // Basic usage: one read, one write
851 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i < 10 }"),
852 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
853 UMAP("{ Write[] -> Elt[] }"),
854 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
855 false, false));
856 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"),
857 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
858 UMAP("{ Write[] -> Elt[] }"),
859 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
860 false, true));
861 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 <= i < 10 }"),
862 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
863 UMAP("{ Write[] -> Elt[] }"),
864 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
865 true, false));
866 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 <= i <= 10 }"),
867 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
868 UMAP("{ Write[] -> Elt[] }"),
869 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
870 true, true));
872 // Two reads
873 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"),
874 computeArrayUnused(
875 UMAP("{ Read[0] -> [-10]; Read[1] -> [0]; Write[] -> [10] }"),
876 UMAP("{ Write[] -> Elt[] }"), UMAP("{ Read[i] -> Elt[] }"),
877 ReadEltInSameInst, false, true));
879 // Corner case: no writes
880 EXPECT_EQ(UMAP("{}"),
881 computeArrayUnused(UMAP("{ Read[] -> [0] }"), UMAP("{}"),
882 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
883 false, false));
885 // Corner case: no reads
886 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"),
887 computeArrayUnused(UMAP("{ Write[] -> [0] }"),
888 UMAP("{ Write[] -> Elt[] }"), UMAP("{}"),
889 ReadEltInSameInst, false, true));
891 // Two writes
892 EXPECT_EQ(
893 UMAP("{ Elt[] -> [i] : i <= 10 }"),
894 computeArrayUnused(UMAP("{ WriteA[] -> [0]; WriteB[] -> [10] }"),
895 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"),
896 UMAP("{}"), ReadEltInSameInst, false, true));
898 // Two unused zones
899 // read,write,read,write
900 EXPECT_EQ(
901 UMAP("{ Elt[] -> [i] : 0 < i <= 10; Elt[] -> [i] : 20 < i <= 30 }"),
902 computeArrayUnused(UMAP("{ ReadA[] -> [0]; WriteA[] -> [10]; ReadB[] "
903 "-> [20]; WriteB[] -> [30] }"),
904 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"),
905 UMAP("{ ReadA[] -> Elt[]; ReadB[] -> Elt[] }"),
906 ReadEltInSameInst, false, true));
908 // write, write
909 EXPECT_EQ(
910 UMAP("{ Elt[] -> [i] : i <= 10 }"),
911 computeArrayUnused(
912 UMAP("{ WriteA[] -> [0]; WriteB[] -> [10]; Read[] -> [20] }"),
913 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"),
914 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, false, true));
916 // write, read
917 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"),
918 computeArrayUnused(UMAP("{ Write[] -> [0]; Read[] -> [10] }"),
919 UMAP("{ Write[] -> Elt[] }"),
920 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst,
921 false, true));
923 // read, write, read
924 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"),
925 computeArrayUnused(
926 UMAP("{ ReadA[] -> [0]; Write[] -> [10]; ReadB[] -> [20] }"),
927 UMAP("{ Write[] -> Elt[] }"),
928 UMAP("{ ReadA[] -> Elt[]; ReadB[] -> Elt[] }"),
929 ReadEltInSameInst, false, true));
931 // read, write, write
932 EXPECT_EQ(
933 UMAP("{ Elt[] -> [i] : 0 < i <= 20 }"),
934 computeArrayUnused(
935 UMAP("{ Read[] -> [0]; WriteA[] -> [10]; WriteB[] -> [20] }"),
936 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"),
937 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst, false, true));
939 // read, write, write, read
940 EXPECT_EQ(
941 UMAP("{ Elt[] -> [i] : 0 < i <= 20 }"),
942 computeArrayUnused(UMAP("{ ReadA[] -> [0]; WriteA[] -> [10]; WriteB[] "
943 "-> [20]; ReadB[] -> [30] }"),
944 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"),
945 UMAP("{ ReadA[] -> Elt[]; ReadB[] -> Elt[] }"),
946 ReadEltInSameInst, false, true));
949 // Read and write in same statement
950 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i < 0 }"),
951 computeArrayUnused(UMAP("{ RW[] -> [0] }"),
952 UMAP("{ RW[] -> Elt[] }"),
953 UMAP("{ RW[] -> Elt[] }"), true, false, false));
954 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"),
955 computeArrayUnused(UMAP("{ RW[] -> [0] }"),
956 UMAP("{ RW[] -> Elt[] }"),
957 UMAP("{ RW[] -> Elt[] }"), true, false, true));
958 EXPECT_EQ(UMAP("{ Elt[] -> [0] }"),
959 computeArrayUnused(UMAP("{ RW[] -> [0] }"),
960 UMAP("{ RW[] -> Elt[] }"),
961 UMAP("{ RW[] -> Elt[] }"), false, true, true));
964 TEST(DeLICM, convertZoneToTimepoints) {
965 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
966 &isl_ctx_free);
968 // Corner case: empty set
969 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), false, false));
970 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), true, false));
971 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), false, true));
972 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), true, true));
974 // Basic usage
975 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{ [1] }"), false, false));
976 EXPECT_EQ(USET("{ [0] }"),
977 convertZoneToTimepoints(USET("{ [1] }"), true, false));
978 EXPECT_EQ(USET("{ [1] }"),
979 convertZoneToTimepoints(USET("{ [1] }"), false, true));
980 EXPECT_EQ(USET("{ [0]; [1] }"),
981 convertZoneToTimepoints(USET("{ [1] }"), true, true));
983 // Non-adjacent ranges
984 EXPECT_EQ(USET("{}"),
985 convertZoneToTimepoints(USET("{ [1]; [11] }"), false, false));
986 EXPECT_EQ(USET("{ [0]; [10] }"),
987 convertZoneToTimepoints(USET("{ [1]; [11] }"), true, false));
988 EXPECT_EQ(USET("{ [1]; [11] }"),
989 convertZoneToTimepoints(USET("{ [1]; [11] }"), false, true));
990 EXPECT_EQ(USET("{ [0]; [1]; [10]; [11] }"),
991 convertZoneToTimepoints(USET("{ [1]; [11] }"), true, true));
993 // Adjacent unit ranges
994 EXPECT_EQ(
995 USET("{ [i] : 0 < i < 10 }"),
996 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, false));
997 EXPECT_EQ(
998 USET("{ [i] : 0 <= i < 10 }"),
999 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, false));
1000 EXPECT_EQ(
1001 USET("{ [i] : 0 < i <= 10 }"),
1002 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, true));
1003 EXPECT_EQ(USET("{ [i] : 0 <= i <= 10 }"),
1004 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, true));
1006 // More than one dimension
1007 EXPECT_EQ(USET("{}"),
1008 convertZoneToTimepoints(USET("{ [0,1] }"), false, false));
1009 EXPECT_EQ(USET("{ [0,0] }"),
1010 convertZoneToTimepoints(USET("{ [0,1] }"), true, false));
1011 EXPECT_EQ(USET("{ [0,1] }"),
1012 convertZoneToTimepoints(USET("{ [0,1] }"), false, true));
1013 EXPECT_EQ(USET("{ [0,0]; [0,1] }"),
1014 convertZoneToTimepoints(USET("{ [0,1] }"), true, true));
1016 // Map domains
1017 EXPECT_EQ(UMAP("{}"), convertZoneToTimepoints(UMAP("{ [1] -> [] }"),
1018 isl::dim::in, false, false));
1019 EXPECT_EQ(UMAP("{ [0] -> [] }"),
1020 convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, true,
1021 false));
1022 EXPECT_EQ(UMAP("{ [1] -> [] }"),
1023 convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, false,
1024 true));
1025 EXPECT_EQ(
1026 UMAP("{ [0] -> []; [1] -> [] }"),
1027 convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in, true, true));
1029 // Map ranges
1030 EXPECT_EQ(UMAP("{}"), convertZoneToTimepoints(UMAP("{ [] -> [1] }"),
1031 isl::dim::out, false, false));
1032 EXPECT_EQ(UMAP("{ [] -> [0] }"),
1033 convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, true,
1034 false));
1035 EXPECT_EQ(UMAP("{ [] -> [1] }"),
1036 convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, false,
1037 true));
1038 EXPECT_EQ(UMAP("{ [] -> [0]; [] -> [1] }"),
1039 convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out, true,
1040 true));
1043 TEST(DeLICM, distribute) {
1044 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
1045 &isl_ctx_free);
1047 // Basic usage
1048 EXPECT_EQ(MAP("{ [Domain[] -> Range1[]] -> [Domain[] -> Range2[]] }"),
1049 distributeDomain(MAP("{ Domain[] -> [Range1[] -> Range2[]] }")));
1050 EXPECT_EQ(
1051 MAP("{ [Domain[i,j] -> Range1[i,k]] -> [Domain[i,j] -> Range2[j,k]] }"),
1052 distributeDomain(MAP("{ Domain[i,j] -> [Range1[i,k] -> Range2[j,k]] }")));
1054 // Union maps
1055 EXPECT_EQ(
1056 UMAP(
1057 "{ [DomainA[i,j] -> RangeA1[i,k]] -> [DomainA[i,j] -> RangeA2[j,k]];"
1058 "[DomainB[i,j] -> RangeB1[i,k]] -> [DomainB[i,j] -> RangeB2[j,k]] }"),
1059 distributeDomain(
1060 UMAP("{ DomainA[i,j] -> [RangeA1[i,k] -> RangeA2[j,k]];"
1061 "DomainB[i,j] -> [RangeB1[i,k] -> RangeB2[j,k]] }")));
1064 TEST(DeLICM, lift) {
1065 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
1066 &isl_ctx_free);
1068 // Basic usage
1069 EXPECT_EQ(UMAP("{ [Factor[] -> Domain[]] -> [Factor[] -> Range[]] }"),
1070 liftDomains(UMAP("{ Domain[] -> Range[] }"), USET("{ Factor[] }")));
1071 EXPECT_EQ(UMAP("{ [Factor[l] -> Domain[i,k]] -> [Factor[l] -> Range[j,k]] }"),
1072 liftDomains(UMAP("{ Domain[i,k] -> Range[j,k] }"),
1073 USET("{ Factor[l] }")));
1075 // Multiple maps in union
1076 EXPECT_EQ(
1077 UMAP("{ [FactorA[] -> DomainA[]] -> [FactorA[] -> RangeA[]];"
1078 "[FactorB[] -> DomainA[]] -> [FactorB[] -> RangeA[]];"
1079 "[FactorA[] -> DomainB[]] -> [FactorA[] -> RangeB[]];"
1080 "[FactorB[] -> DomainB[]] -> [FactorB[] -> RangeB[]] }"),
1081 liftDomains(UMAP("{ DomainA[] -> RangeA[]; DomainB[] -> RangeB[] }"),
1082 USET("{ FactorA[]; FactorB[] }")));
1085 TEST(DeLICM, apply) {
1086 std::unique_ptr<isl_ctx, decltype(&isl_ctx_free)> Ctx(isl_ctx_alloc(),
1087 &isl_ctx_free);
1089 // Basic usage
1090 EXPECT_EQ(
1091 UMAP("{ [DomainDomain[] -> NewDomainRange[]] -> Range[] }"),
1092 applyDomainRange(UMAP("{ [DomainDomain[] -> DomainRange[]] -> Range[] }"),
1093 UMAP("{ DomainRange[] -> NewDomainRange[] }")));
1094 EXPECT_EQ(
1095 UMAP("{ [DomainDomain[i,k] -> NewDomainRange[j,k,l]] -> Range[i,j] }"),
1096 applyDomainRange(
1097 UMAP("{ [DomainDomain[i,k] -> DomainRange[j,k]] -> Range[i,j] }"),
1098 UMAP("{ DomainRange[j,k] -> NewDomainRange[j,k,l] }")));
1100 // Multiple maps in union
1101 EXPECT_EQ(UMAP("{ [DomainDomainA[] -> NewDomainRangeA[]] -> RangeA[];"
1102 "[DomainDomainB[] -> NewDomainRangeB[]] -> RangeB[] }"),
1103 applyDomainRange(
1104 UMAP("{ [DomainDomainA[] -> DomainRangeA[]] -> RangeA[];"
1105 "[DomainDomainB[] -> DomainRangeB[]] -> RangeB[] }"),
1106 UMAP("{ DomainRangeA[] -> NewDomainRangeA[];"
1107 "DomainRangeB[] -> NewDomainRangeB[] }")));
1109 } // anonymous namespace