1 //===- IslTest.cpp ----------------------------------------------------===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
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"
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
);
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
);
32 Obj
.type
->free(Obj
.v
);
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)
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
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
);
210 EXPECT_EQ(2u, APOne
.getBitWidth());
214 auto IslTwo
= isl::val(IslCtx
, 2);
215 auto APTwo
= APIntFromVal(IslTwo
);
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(),
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
);
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
);
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
);
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
);
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
);
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
);
389 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
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
;
406 TestMap
.foreach_basic_map([&](isl::basic_map BMap
) -> isl::stat
{
407 EXPECT_EQ(BMap
, TestBMap
);
409 return isl::stat::ok
;
411 EXPECT_EQ(1, NumBMaps
);
416 TestSet
.foreach_basic_set([&](isl::basic_set BSet
) -> isl::stat
{
417 EXPECT_EQ(BSet
, TestBSet
);
419 return isl::stat::ok
;
421 EXPECT_EQ(1, NumBSets
);
426 TestUMap
.foreach_map([&](isl::map Map
) -> isl::stat
{
427 EXPECT_EQ(Map
, TestMap
);
429 return isl::stat::ok
;
431 EXPECT_EQ(1, NumMaps
);
436 TestUSet
.foreach_set([&](isl::set Set
) -> isl::stat
{
437 EXPECT_EQ(Set
, TestSet
);
439 return isl::stat::ok
;
441 EXPECT_EQ(1, NumSets
);
445 auto UPwAff
= isl::union_pw_aff(TestUSet
, isl::val::zero(Ctx
.get()));
447 UPwAff
.foreach_pw_aff([&](isl::pw_aff PwAff
) -> isl::stat
{
448 EXPECT_TRUE(PwAff
.is_cst());
450 return isl::stat::ok
;
452 EXPECT_EQ(1, NumPwAffs
);
457 EXPECT_EQ(isl::stat::error
,
458 TestMap
.foreach_basic_map([&](isl::basic_map BMap
) -> isl::stat
{
459 EXPECT_EQ(BMap
, TestBMap
);
461 return isl::stat::error
;
463 EXPECT_EQ(1, NumBMaps
);
468 EXPECT_EQ(isl::stat::error
,
469 TestUMap
.foreach_map([&](isl::map Map
) -> isl::stat
{
470 EXPECT_EQ(Map
, TestMap
);
472 return isl::stat::error
;
474 EXPECT_EQ(1, NumMaps
);
478 auto TestPwAff
= isl::pw_aff(TestSet
, isl::val::zero(Ctx
.get()));
480 TestPwAff
.foreach_piece([&](isl::set Domain
, isl::aff Aff
) -> isl::stat
{
481 EXPECT_EQ(Domain
, TestSet
);
482 EXPECT_TRUE(Aff
.is_cst());
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(),
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));
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));
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));
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(),
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));
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));
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));
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(),
586 // Basic usage with isl_map
587 EXPECT_EQ(MAP("{ [] -> [i] : 0 < i < 10 }"),
588 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false,
591 MAP("{ [] -> [i] : 0 <= i < 10 }"),
592 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, false));
594 MAP("{ [] -> [i] : 0 < i <= 10 }"),
595 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false, true));
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(),
620 EXPECT_EQ(SET("{ [] : 1 = 0 }"), singleton(USET("{ }"), SPACE("{ [] }")));
621 EXPECT_EQ(MAP("{ [] -> [] : 1 = 0 }"),
622 singleton(UMAP("{ }"), SPACE("{ [] -> [] }")));
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] }")));
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(),
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(),
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(),
685 EXPECT_EQ(UMAP("{ [i] -> [i] }"), makeIdentityMap(USET("{ [0] }"), false));
686 EXPECT_EQ(UMAP("{ [0] -> [0] }"), makeIdentityMap(USET("{ [0] }"), true));
689 EXPECT_EQ(UMAP("{ [] -> []; [i] -> [i] }"),
690 makeIdentityMap(USET("{ []; [0] }"), false));
691 EXPECT_EQ(UMAP("{ [] -> []; [0] -> [0] }"),
692 makeIdentityMap(USET("{ []; [0] }"), true));
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(),
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(),
715 EXPECT_EQ(SET("{ [1] }"), shiftDim(SET("{ [0] }"), 0, 1));
716 EXPECT_EQ(USET("{ [1] }"), shiftDim(USET("{ [0] }"), 0, 1));
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));
724 EXPECT_EQ(USET("[n] -> { [n+1] }"), shiftDim(USET("[n] -> { [n] }"), 0, 1));
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(),
742 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"),
743 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
744 UMAP("{ Dom[] -> Elt[] }"), false, false,
746 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"),
747 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
748 UMAP("{ Dom[] -> Elt[] }"), false, false,
750 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"),
751 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
752 UMAP("{ Dom[] -> Elt[] }"), false, true,
754 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"),
755 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
756 UMAP("{ Dom[] -> Elt[] }"), false, true,
759 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"),
760 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
761 UMAP("{ Dom[] -> Elt[] }"), true, false,
763 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"),
764 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
765 UMAP("{ Dom[] -> Elt[] }"), true, false,
767 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"),
768 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
769 UMAP("{ Dom[] -> Elt[] }"), true, true,
771 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"),
772 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
773 UMAP("{ Dom[] -> Elt[] }"), true, true, true));
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[] }"),
797 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i < 10; [Elt[] -> [i]] -> "
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]] -> "
804 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
805 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
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[] }"),
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[] }"),
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));
826 EXPECT_EQ(UMAP("[p] -> { [Elt[] -> [i]] -> Dom[] : p < i }"),
827 computeReachingWrite(UMAP("[p] -> { Dom[] -> [p] }"),
828 UMAP("{ Dom[] -> Elt[] }"), false, false,
831 // More realistic example (from reduction_embedded.ll)
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,
841 TEST(DeLICM
, computeArrayUnused
) {
842 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
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
,
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
,
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
,
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
,
873 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"),
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
,
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));
893 UMAP("{ Elt[] -> [i] : i <= 10 }"),
894 computeArrayUnused(UMAP("{ WriteA[] -> [0]; WriteB[] -> [10] }"),
895 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"),
896 UMAP("{}"), ReadEltInSameInst
, false, true));
899 // read,write,read,write
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));
910 UMAP("{ Elt[] -> [i] : i <= 10 }"),
912 UMAP("{ WriteA[] -> [0]; WriteB[] -> [10]; Read[] -> [20] }"),
913 UMAP("{ WriteA[] -> Elt[]; WriteB[] -> Elt[] }"),
914 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst
, false, true));
917 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"),
918 computeArrayUnused(UMAP("{ Write[] -> [0]; Read[] -> [10] }"),
919 UMAP("{ Write[] -> Elt[] }"),
920 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst
,
924 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"),
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
933 UMAP("{ Elt[] -> [i] : 0 < i <= 20 }"),
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
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(),
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));
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
995 USET("{ [i] : 0 < i < 10 }"),
996 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, false));
998 USET("{ [i] : 0 <= i < 10 }"),
999 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, false));
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));
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,
1022 EXPECT_EQ(UMAP("{ [1] -> [] }"),
1023 convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in
, false,
1026 UMAP("{ [0] -> []; [1] -> [] }"),
1027 convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in
, true, true));
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,
1035 EXPECT_EQ(UMAP("{ [] -> [1] }"),
1036 convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out
, false,
1038 EXPECT_EQ(UMAP("{ [] -> [0]; [] -> [1] }"),
1039 convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out
, true,
1043 TEST(DeLICM
, distribute
) {
1044 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
1048 EXPECT_EQ(MAP("{ [Domain[] -> Range1[]] -> [Domain[] -> Range2[]] }"),
1049 distributeDomain(MAP("{ Domain[] -> [Range1[] -> Range2[]] }")));
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]] }")));
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]] }"),
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(),
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
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(),
1091 UMAP("{ [DomainDomain[] -> NewDomainRange[]] -> Range[] }"),
1092 applyDomainRange(UMAP("{ [DomainDomain[] -> DomainRange[]] -> Range[] }"),
1093 UMAP("{ DomainRange[] -> NewDomainRange[] }")));
1095 UMAP("{ [DomainDomain[i,k] -> NewDomainRange[j,k,l]] -> Range[i,j] }"),
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[] }"),
1104 UMAP("{ [DomainDomainA[] -> DomainRangeA[]] -> RangeA[];"
1105 "[DomainDomainB[] -> DomainRangeB[]] -> RangeB[] }"),
1106 UMAP("{ DomainRangeA[] -> NewDomainRangeA[];"
1107 "DomainRangeB[] -> NewDomainRangeB[] }")));
1109 } // anonymous namespace