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/ISLTools.h"
12 #include "gtest/gtest.h"
13 #include "isl/stream.h"
17 using namespace polly
;
19 static isl::space
parseSpace(isl_ctx
*Ctx
, const char *Str
) {
20 isl_stream
*Stream
= isl_stream_new_str(Ctx
, Str
);
21 auto Obj
= isl_stream_read_obj(Stream
);
24 if (Obj
.type
== isl_obj_set
)
25 Result
= give(isl_set_get_space(static_cast<isl_set
*>(Obj
.v
)));
26 else if (Obj
.type
== isl_obj_map
)
27 Result
= give(isl_map_get_space(static_cast<isl_map
*>(Obj
.v
)));
29 isl_stream_free(Stream
);
31 Obj
.type
->free(Obj
.v
);
35 #define SPACE(Str) parseSpace(Ctx.get(), Str)
37 #define SET(Str) isl::set(Ctx.get(), Str)
38 #define MAP(Str) isl::map(Ctx.get(), Str)
40 #define USET(Str) isl::union_set(Ctx.get(), Str)
41 #define UMAP(Str) isl::union_map(Ctx.get(), Str)
44 inline namespace noexceptions
{
46 static bool operator==(const isl::space
&LHS
, const isl::space
&RHS
) {
47 return bool(LHS
.is_equal(RHS
));
50 static bool operator==(const isl::basic_set
&LHS
, const isl::basic_set
&RHS
) {
51 return bool(LHS
.is_equal(RHS
));
54 static bool operator==(const isl::set
&LHS
, const isl::set
&RHS
) {
55 return bool(LHS
.is_equal(RHS
));
58 static bool operator==(const isl::basic_map
&LHS
, const isl::basic_map
&RHS
) {
59 return bool(LHS
.is_equal(RHS
));
62 static bool operator==(const isl::map
&LHS
, const isl::map
&RHS
) {
63 return bool(LHS
.is_equal(RHS
));
66 static bool operator==(const isl::union_set
&LHS
, const isl::union_set
&RHS
) {
67 return bool(LHS
.is_equal(RHS
));
70 static bool operator==(const isl::union_map
&LHS
, const isl::union_map
&RHS
) {
71 return bool(LHS
.is_equal(RHS
));
74 static bool operator==(const isl::val
&LHS
, const isl::val
&RHS
) {
75 return bool(LHS
.eq(RHS
));
77 } // namespace noexceptions
82 TEST(Isl
, APIntToIslVal
) {
83 isl_ctx
*IslCtx
= isl_ctx_alloc();
86 APInt
APZero(1, 0, true);
87 auto IslZero
= valFromAPInt(IslCtx
, APZero
, true);
88 EXPECT_TRUE(IslZero
.is_zero());
92 APInt
APNOne(1, -1, true);
93 auto IslNOne
= valFromAPInt(IslCtx
, APNOne
, true);
94 EXPECT_TRUE(IslNOne
.is_negone());
98 APInt
APZero(1, 0, false);
99 auto IslZero
= valFromAPInt(IslCtx
, APZero
, false);
100 EXPECT_TRUE(IslZero
.is_zero());
104 APInt
APOne(1, 1, false);
105 auto IslOne
= valFromAPInt(IslCtx
, APOne
, false);
106 EXPECT_TRUE(IslOne
.is_one());
110 APInt
APNTwo(2, -2, true);
111 auto IslNTwo
= valFromAPInt(IslCtx
, APNTwo
, true);
112 auto IslNTwoCmp
= isl::val(IslCtx
, -2);
113 EXPECT_EQ(IslNTwo
, IslNTwoCmp
);
117 APInt
APNOne(32, -1, true);
118 auto IslNOne
= valFromAPInt(IslCtx
, APNOne
, true);
119 EXPECT_TRUE(IslNOne
.is_negone());
123 APInt
APZero(32, 0, false);
124 auto IslZero
= valFromAPInt(IslCtx
, APZero
, false);
125 EXPECT_TRUE(IslZero
.is_zero());
129 APInt
APOne(32, 1, false);
130 auto IslOne
= valFromAPInt(IslCtx
, APOne
, false);
131 EXPECT_TRUE(IslOne
.is_one());
135 APInt
APTwo(32, 2, false);
136 auto IslTwo
= valFromAPInt(IslCtx
, APTwo
, false);
137 EXPECT_EQ(0, IslTwo
.cmp_si(2));
141 APInt
APNOne(32, (1ull << 32) - 1, false);
142 auto IslNOne
= valFromAPInt(IslCtx
, APNOne
, false);
143 auto IslRef
= isl::val(IslCtx
, 32).two_exp().sub_ui(1);
144 EXPECT_EQ(IslNOne
, IslRef
);
148 APInt
APLarge(130, 2, false);
149 APLarge
= APLarge
.shl(70);
150 auto IslLarge
= valFromAPInt(IslCtx
, APLarge
, false);
151 auto IslRef
= isl::val(IslCtx
, 71);
152 IslRef
= IslRef
.two_exp();
153 EXPECT_EQ(IslLarge
, IslRef
);
156 isl_ctx_free(IslCtx
);
159 TEST(Isl
, IslValToAPInt
) {
160 isl_ctx
*IslCtx
= isl_ctx_alloc();
163 auto IslNOne
= isl::val(IslCtx
, -1);
164 auto APNOne
= APIntFromVal(IslNOne
);
165 // Compare with the two's complement of -1 in a 1-bit integer.
166 EXPECT_EQ(1, APNOne
);
167 EXPECT_EQ(1u, APNOne
.getBitWidth());
171 auto IslNTwo
= isl::val(IslCtx
, -2);
172 auto APNTwo
= APIntFromVal(IslNTwo
);
173 // Compare with the two's complement of -2 in a 2-bit integer.
174 EXPECT_EQ(2, APNTwo
);
175 EXPECT_EQ(2u, APNTwo
.getBitWidth());
179 auto IslNThree
= isl::val(IslCtx
, -3);
180 auto APNThree
= APIntFromVal(IslNThree
);
181 // Compare with the two's complement of -3 in a 3-bit integer.
182 EXPECT_EQ(5, APNThree
);
183 EXPECT_EQ(3u, APNThree
.getBitWidth());
187 auto IslNFour
= isl::val(IslCtx
, -4);
188 auto APNFour
= APIntFromVal(IslNFour
);
189 // Compare with the two's complement of -4 in a 3-bit integer.
190 EXPECT_EQ(4, APNFour
);
191 EXPECT_EQ(3u, APNFour
.getBitWidth());
195 auto IslZero
= isl::val(IslCtx
, 0);
196 auto APZero
= APIntFromVal(IslZero
);
197 EXPECT_EQ(0, APZero
);
198 EXPECT_EQ(1u, APZero
.getBitWidth());
202 auto IslOne
= isl::val(IslCtx
, 1);
203 auto APOne
= APIntFromVal(IslOne
);
205 EXPECT_EQ(2u, APOne
.getBitWidth());
209 auto IslTwo
= isl::val(IslCtx
, 2);
210 auto APTwo
= APIntFromVal(IslTwo
);
212 EXPECT_EQ(3u, APTwo
.getBitWidth());
216 auto IslThree
= isl::val(IslCtx
, 3);
217 auto APThree
= APIntFromVal(IslThree
);
218 EXPECT_EQ(3, APThree
);
219 EXPECT_EQ(3u, APThree
.getBitWidth());
223 auto IslFour
= isl::val(IslCtx
, 4);
224 auto APFour
= APIntFromVal(IslFour
);
225 EXPECT_EQ(4, APFour
);
226 EXPECT_EQ(4u, APFour
.getBitWidth());
230 auto IslNOne
= isl::val(IslCtx
, 32).two_exp().sub_ui(1);
231 auto APNOne
= APIntFromVal(IslNOne
);
232 EXPECT_EQ((1ull << 32) - 1, APNOne
);
233 EXPECT_EQ(33u, APNOne
.getBitWidth());
237 auto IslLargeNum
= isl::val(IslCtx
, 60);
238 IslLargeNum
= IslLargeNum
.two_exp();
239 IslLargeNum
= IslLargeNum
.sub_ui(1);
240 auto APLargeNum
= APIntFromVal(IslLargeNum
);
241 EXPECT_EQ((1ull << 60) - 1, APLargeNum
);
242 EXPECT_EQ(61u, APLargeNum
.getBitWidth());
246 auto IslExp
= isl::val(IslCtx
, 500);
247 auto IslLargePow2
= IslExp
.two_exp();
248 auto APLargePow2
= APIntFromVal(IslLargePow2
);
249 EXPECT_TRUE(APLargePow2
.isPowerOf2());
250 EXPECT_EQ(502u, APLargePow2
.getBitWidth());
251 EXPECT_EQ(502u, APLargePow2
.getMinSignedBits());
255 auto IslExp
= isl::val(IslCtx
, 500);
256 auto IslLargeNPow2
= IslExp
.two_exp().neg();
257 auto APLargeNPow2
= APIntFromVal(IslLargeNPow2
);
258 EXPECT_EQ(501u, APLargeNPow2
.getBitWidth());
259 EXPECT_EQ(501u, APLargeNPow2
.getMinSignedBits());
260 EXPECT_EQ(500, (-APLargeNPow2
).exactLogBase2());
264 auto IslExp
= isl::val(IslCtx
, 512);
265 auto IslLargePow2
= IslExp
.two_exp();
266 auto APLargePow2
= APIntFromVal(IslLargePow2
);
267 EXPECT_TRUE(APLargePow2
.isPowerOf2());
268 EXPECT_EQ(514u, APLargePow2
.getBitWidth());
269 EXPECT_EQ(514u, APLargePow2
.getMinSignedBits());
273 auto IslExp
= isl::val(IslCtx
, 512);
274 auto IslLargeNPow2
= IslExp
.two_exp().neg();
275 auto APLargeNPow2
= APIntFromVal(IslLargeNPow2
);
276 EXPECT_EQ(513u, APLargeNPow2
.getBitWidth());
277 EXPECT_EQ(513u, APLargeNPow2
.getMinSignedBits());
278 EXPECT_EQ(512, (-APLargeNPow2
).exactLogBase2());
281 isl_ctx_free(IslCtx
);
285 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
288 auto MapSpace
= isl::space(Ctx
.get(), 0, 1, 1);
289 auto TestBMap
= isl::basic_map::universe(MapSpace
);
290 TestBMap
= TestBMap
.fix_si(isl::dim::out
, 0, 0);
291 TestBMap
= TestBMap
.fix_si(isl::dim::out
, 0, 0);
292 isl::map TestMap
= TestBMap
;
293 isl::union_map TestUMap
= TestMap
;
295 auto SetSpace
= isl::space(Ctx
.get(), 0, 1);
296 isl::basic_set TestBSet
= isl::point(SetSpace
);
297 isl::set TestSet
= TestBSet
;
298 isl::union_set TestUSet
= TestSet
;
302 TestMap
.foreach_basic_map([&](isl::basic_map BMap
) -> isl::stat
{
303 EXPECT_EQ(BMap
, TestBMap
);
305 return isl::stat::ok
;
307 EXPECT_EQ(1, NumBMaps
);
312 TestSet
.foreach_basic_set([&](isl::basic_set BSet
) -> isl::stat
{
313 EXPECT_EQ(BSet
, TestBSet
);
315 return isl::stat::ok
;
317 EXPECT_EQ(1, NumBSets
);
322 TestUMap
.foreach_map([&](isl::map Map
) -> isl::stat
{
323 EXPECT_EQ(Map
, TestMap
);
325 return isl::stat::ok
;
327 EXPECT_EQ(1, NumMaps
);
332 TestUSet
.foreach_set([&](isl::set Set
) -> isl::stat
{
333 EXPECT_EQ(Set
, TestSet
);
335 return isl::stat::ok
;
337 EXPECT_EQ(1, NumSets
);
341 auto UPwAff
= isl::union_pw_aff(TestUSet
, isl::val::zero(Ctx
.get()));
343 UPwAff
.foreach_pw_aff([&](isl::pw_aff PwAff
) -> isl::stat
{
344 EXPECT_TRUE(PwAff
.is_cst());
346 return isl::stat::ok
;
348 EXPECT_EQ(1, NumPwAffs
);
353 EXPECT_EQ(isl::stat::error
,
354 TestMap
.foreach_basic_map([&](isl::basic_map BMap
) -> isl::stat
{
355 EXPECT_EQ(BMap
, TestBMap
);
357 return isl::stat::error
;
359 EXPECT_EQ(1, NumBMaps
);
364 EXPECT_EQ(isl::stat::error
,
365 TestUMap
.foreach_map([&](isl::map Map
) -> isl::stat
{
366 EXPECT_EQ(Map
, TestMap
);
368 return isl::stat::error
;
370 EXPECT_EQ(1, NumMaps
);
374 auto TestPwAff
= isl::pw_aff(TestSet
, isl::val::zero(Ctx
.get()));
376 TestPwAff
.foreach_piece([&](isl::set Domain
, isl::aff Aff
) -> isl::stat
{
377 EXPECT_EQ(Domain
, TestSet
);
378 EXPECT_TRUE(Aff
.is_cst());
380 return isl::stat::error
;
382 EXPECT_EQ(1, NumPieces
);
386 TEST(ISLTools
, beforeScatter
) {
387 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
390 // Basic usage with isl_map
391 EXPECT_EQ(MAP("{ [] -> [i] : i <= 0 }"),
392 beforeScatter(MAP("{ [] -> [0] }"), false));
393 EXPECT_EQ(MAP("{ [] -> [i] : i < 0 }"),
394 beforeScatter(MAP("{ [] -> [0] }"), true));
396 // Basic usage with isl_union_map
397 EXPECT_EQ(UMAP("{ A[] -> [i] : i <= 0; B[] -> [i] : i <= 0 }"),
398 beforeScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), false));
399 EXPECT_EQ(UMAP("{ A[] -> [i] : i < 0; B[] -> [i] : i < 0 }"),
400 beforeScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), true));
402 // More than one dimension
403 EXPECT_EQ(UMAP("{ [] -> [i, j] : i < 0; [] -> [i, j] : i = 0 and j <= 0 }"),
404 beforeScatter(UMAP("{ [] -> [0, 0] }"), false));
405 EXPECT_EQ(UMAP("{ [] -> [i, j] : i < 0; [] -> [i, j] : i = 0 and j < 0 }"),
406 beforeScatter(UMAP("{ [] -> [0, 0] }"), true));
409 EXPECT_EQ(UMAP("{ [i] -> [j] : j <= i }"),
410 beforeScatter(UMAP("{ [i] -> [i] }"), false));
411 EXPECT_EQ(UMAP("{ [i] -> [j] : j < i }"),
412 beforeScatter(UMAP("{ [i] -> [i] }"), true));
415 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j <= i }"),
416 beforeScatter(UMAP("[i] -> { [] -> [i] }"), false));
417 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j < i }"),
418 beforeScatter(UMAP("[i] -> { [] -> [i] }"), true));
420 // More than one range
421 EXPECT_EQ(UMAP("{ [] -> [i] : i <= 10 }"),
422 beforeScatter(UMAP("{ [] -> [0]; [] -> [10] }"), false));
423 EXPECT_EQ(UMAP("{ [] -> [i] : i < 10 }"),
424 beforeScatter(UMAP("{ [] -> [0]; [] -> [10] }"), true));
427 EXPECT_EQ(UMAP("{ [] -> [i] : 1 = 0 }"),
428 beforeScatter(UMAP("{ [] -> [i] : 1 = 0 }"), false));
429 EXPECT_EQ(UMAP("{ [] -> [i] : 1 = 0 }"),
430 beforeScatter(UMAP("{ [] -> [i] : 1 = 0 }"), true));
433 TEST(ISLTools
, afterScatter
) {
434 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
437 // Basic usage with isl_map
438 EXPECT_EQ(MAP("{ [] -> [i] : i >= 0 }"),
439 afterScatter(MAP("{ [] -> [0] }"), false));
440 EXPECT_EQ(MAP("{ [] -> [i] : i > 0 }"),
441 afterScatter(MAP("{ [] -> [0] }"), true));
443 // Basic usage with isl_union_map
444 EXPECT_EQ(UMAP("{ A[] -> [i] : i >= 0; B[] -> [i] : i >= 0 }"),
445 afterScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), false));
446 EXPECT_EQ(UMAP("{ A[] -> [i] : i > 0; B[] -> [i] : i > 0 }"),
447 afterScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"), true));
449 // More than one dimension
450 EXPECT_EQ(UMAP("{ [] -> [i, j] : i > 0; [] -> [i, j] : i = 0 and j >= 0 }"),
451 afterScatter(UMAP("{ [] -> [0, 0] }"), false));
452 EXPECT_EQ(UMAP("{ [] -> [i, j] : i > 0; [] -> [i, j] : i = 0 and j > 0 }"),
453 afterScatter(UMAP("{ [] -> [0, 0] }"), true));
456 EXPECT_EQ(UMAP("{ [i] -> [j] : j >= i }"),
457 afterScatter(UMAP("{ [i] -> [i] }"), false));
458 EXPECT_EQ(UMAP("{ [i] -> [j] : j > i }"),
459 afterScatter(UMAP("{ [i] -> [i] }"), true));
462 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j >= i }"),
463 afterScatter(UMAP("[i] -> { [] -> [i] }"), false));
464 EXPECT_EQ(UMAP("[i] -> { [] -> [j] : j > i }"),
465 afterScatter(UMAP("[i] -> { [] -> [i] }"), true));
467 // More than one range
468 EXPECT_EQ(UMAP("{ [] -> [i] : i >= 0 }"),
469 afterScatter(UMAP("{ [] -> [0]; [] -> [10] }"), false));
470 EXPECT_EQ(UMAP("{ [] -> [i] : i > 0 }"),
471 afterScatter(UMAP("{ [] -> [0]; [] -> [10] }"), true));
474 EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), false));
475 EXPECT_EQ(UMAP("{ }"), afterScatter(UMAP("{ }"), true));
478 TEST(ISLTools
, betweenScatter
) {
479 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
482 // Basic usage with isl_map
483 EXPECT_EQ(MAP("{ [] -> [i] : 0 < i < 10 }"),
484 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false,
487 MAP("{ [] -> [i] : 0 <= i < 10 }"),
488 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, false));
490 MAP("{ [] -> [i] : 0 < i <= 10 }"),
491 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), false, true));
493 MAP("{ [] -> [i] : 0 <= i <= 10 }"),
494 betweenScatter(MAP("{ [] -> [0] }"), MAP("{ [] -> [10] }"), true, true));
496 // Basic usage with isl_union_map
497 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 < i < 10; B[] -> [i] : 0 < i < 10 }"),
498 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
499 UMAP("{ A[] -> [10]; B[] -> [10] }"), false, false));
500 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 <= i < 10; B[] -> [i] : 0 <= i < 10 }"),
501 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
502 UMAP("{ A[] -> [10]; B[] -> [10] }"), true, false));
503 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 < i <= 10; B[] -> [i] : 0 < i <= 10 }"),
504 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
505 UMAP("{ A[] -> [10]; B[] -> [10] }"), false, true));
506 EXPECT_EQ(UMAP("{ A[] -> [i] : 0 <= i <= 10; B[] -> [i] : 0 <= i <= 10 }"),
507 betweenScatter(UMAP("{ A[] -> [0]; B[] -> [0] }"),
508 UMAP("{ A[] -> [10]; B[] -> [10] }"), true, true));
511 TEST(ISLTools
, singleton
) {
512 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
516 EXPECT_EQ(SET("{ [] : 1 = 0 }"), singleton(USET("{ }"), SPACE("{ [] }")));
517 EXPECT_EQ(MAP("{ [] -> [] : 1 = 0 }"),
518 singleton(UMAP("{ }"), SPACE("{ [] -> [] }")));
521 EXPECT_EQ(SET("{ [] }"), singleton(USET("{ [] }"), SPACE("{ [] }")));
522 EXPECT_EQ(MAP("{ [] -> [] }"),
523 singleton(UMAP("{ [] -> [] }"), SPACE("{ [] -> [] }")));
525 // Many elements found
526 EXPECT_EQ(SET("{ [i] : 0 <= i < 10 }"),
527 singleton(USET("{ [i] : 0 <= i < 10 }"), SPACE("{ [i] }")));
529 MAP("{ [i] -> [i] : 0 <= i < 10 }"),
530 singleton(UMAP("{ [i] -> [i] : 0 <= i < 10 }"), SPACE("{ [i] -> [j] }")));
532 // Different parameters
533 EXPECT_EQ(SET("[i] -> { [i] }"),
534 singleton(USET("[i] -> { [i] }"), SPACE("{ [i] }")));
535 EXPECT_EQ(MAP("[i] -> { [i] -> [i] }"),
536 singleton(UMAP("[i] -> { [i] -> [i] }"), SPACE("{ [i] -> [j] }")));
539 TEST(ISLTools
, getNumScatterDims
) {
540 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
544 EXPECT_EQ(0u, getNumScatterDims(UMAP("{ [] -> [] }")));
545 EXPECT_EQ(1u, getNumScatterDims(UMAP("{ [] -> [i] }")));
546 EXPECT_EQ(2u, getNumScatterDims(UMAP("{ [] -> [i,j] }")));
547 EXPECT_EQ(3u, getNumScatterDims(UMAP("{ [] -> [i,j,k] }")));
549 // Different scatter spaces
550 EXPECT_EQ(0u, getNumScatterDims(UMAP("{ A[] -> []; [] -> []}")));
551 EXPECT_EQ(1u, getNumScatterDims(UMAP("{ A[] -> []; [] -> [i] }")));
552 EXPECT_EQ(2u, getNumScatterDims(UMAP("{ A[] -> [i]; [] -> [i,j] }")));
553 EXPECT_EQ(3u, getNumScatterDims(UMAP("{ A[] -> [i]; [] -> [i,j,k] }")));
556 TEST(ISLTools
, getScatterSpace
) {
557 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
561 EXPECT_EQ(SPACE("{ [] }"), getScatterSpace(UMAP("{ [] -> [] }")));
562 EXPECT_EQ(SPACE("{ [i] }"), getScatterSpace(UMAP("{ [] -> [i] }")));
563 EXPECT_EQ(SPACE("{ [i,j] }"), getScatterSpace(UMAP("{ [] -> [i,j] }")));
564 EXPECT_EQ(SPACE("{ [i,j,k] }"), getScatterSpace(UMAP("{ [] -> [i,j,k] }")));
566 // Different scatter spaces
567 EXPECT_EQ(SPACE("{ [] }"), getScatterSpace(UMAP("{ A[] -> []; [] -> [] }")));
568 EXPECT_EQ(SPACE("{ [i] }"),
569 getScatterSpace(UMAP("{ A[] -> []; [] -> [i] }")));
570 EXPECT_EQ(SPACE("{ [i,j] }"),
571 getScatterSpace(UMAP("{ A[] -> [i]; [] -> [i,j] }")));
572 EXPECT_EQ(SPACE("{ [i,j,k] }"),
573 getScatterSpace(UMAP("{ A[] -> [i]; [] -> [i,j,k] }")));
576 TEST(ISLTools
, makeIdentityMap
) {
577 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
581 EXPECT_EQ(UMAP("{ [i] -> [i] }"), makeIdentityMap(USET("{ [0] }"), false));
582 EXPECT_EQ(UMAP("{ [0] -> [0] }"), makeIdentityMap(USET("{ [0] }"), true));
585 EXPECT_EQ(UMAP("{ [] -> []; [i] -> [i] }"),
586 makeIdentityMap(USET("{ []; [0] }"), false));
587 EXPECT_EQ(UMAP("{ [] -> []; [0] -> [0] }"),
588 makeIdentityMap(USET("{ []; [0] }"), true));
591 EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), false));
592 EXPECT_EQ(UMAP("{ }"), makeIdentityMap(USET("{ }"), true));
595 TEST(ISLTools
, reverseDomain
) {
596 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
600 EXPECT_EQ(MAP("{ [B[] -> A[]] -> [] }"),
601 reverseDomain(MAP("{ [A[] -> B[]] -> [] }")));
602 EXPECT_EQ(UMAP("{ [B[] -> A[]] -> [] }"),
603 reverseDomain(UMAP("{ [A[] -> B[]] -> [] }")));
606 TEST(ISLTools
, shiftDim
) {
607 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
611 EXPECT_EQ(SET("{ [1] }"), shiftDim(SET("{ [0] }"), 0, 1));
612 EXPECT_EQ(USET("{ [1] }"), shiftDim(USET("{ [0] }"), 0, 1));
615 EXPECT_EQ(USET("{ [0,0,1] }"), shiftDim(USET("{ [0,0,0] }"), -1, 1));
616 EXPECT_EQ(USET("{ [0,1,0] }"), shiftDim(USET("{ [0,0,0] }"), -2, 1));
617 EXPECT_EQ(USET("{ [1,0,0] }"), shiftDim(USET("{ [0,0,0] }"), -3, 1));
620 EXPECT_EQ(USET("[n] -> { [n+1] }"), shiftDim(USET("[n] -> { [n] }"), 0, 1));
623 EXPECT_EQ(MAP("{ [1] -> [] }"),
624 shiftDim(MAP("{ [0] -> [] }"), isl::dim::in
, 0, 1));
625 EXPECT_EQ(UMAP("{ [1] -> [] }"),
626 shiftDim(UMAP("{ [0] -> [] }"), isl::dim::in
, 0, 1));
627 EXPECT_EQ(MAP("{ [] -> [1] }"),
628 shiftDim(MAP("{ [] -> [0] }"), isl::dim::out
, 0, 1));
629 EXPECT_EQ(UMAP("{ [] -> [1] }"),
630 shiftDim(UMAP("{ [] -> [0] }"), isl::dim::out
, 0, 1));
633 TEST(DeLICM
, computeReachingWrite
) {
634 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
638 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"),
639 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
640 UMAP("{ Dom[] -> Elt[] }"), false, false,
642 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 < i }"),
643 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
644 UMAP("{ Dom[] -> Elt[] }"), false, false,
646 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"),
647 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
648 UMAP("{ Dom[] -> Elt[] }"), false, true,
650 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : 0 <= i }"),
651 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
652 UMAP("{ Dom[] -> Elt[] }"), false, true,
655 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"),
656 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
657 UMAP("{ Dom[] -> Elt[] }"), true, false,
659 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"),
660 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
661 UMAP("{ Dom[] -> Elt[] }"), true, false,
663 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i < 0 }"),
664 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
665 UMAP("{ Dom[] -> Elt[] }"), true, true,
667 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[] : i <= 0 }"),
668 computeReachingWrite(UMAP("{ Dom[] -> [0] }"),
669 UMAP("{ Dom[] -> Elt[] }"), true, true, true));
672 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 < i < 10; [Elt[] -> [i]] -> "
673 "Dom2[] : 10 < i }"),
674 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
675 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
676 false, false, false));
677 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 <= i < 10; [Elt[] -> [i]] -> "
678 "Dom2[] : 10 <= i }"),
679 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
680 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
681 false, true, false));
682 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 < i <= 10; [Elt[] -> [i]] -> "
683 "Dom2[] : 10 < i }"),
684 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
685 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
686 false, false, true));
687 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom1[] : 0 <= i <= 10; [Elt[] -> [i]] -> "
688 "Dom2[] : 10 <= i }"),
689 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
690 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
693 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i < 10; [Elt[] -> [i]] -> "
695 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
696 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
697 true, false, false));
698 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 <= i < 10; [Elt[] -> [i]] -> "
700 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
701 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
703 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 < i <= 10; [Elt[] -> [i]] -> "
704 "Dom1[] : i <= 0 }"),
705 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
706 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
708 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom2[] : 0 <= i <= 10; [Elt[] -> [i]] -> "
709 "Dom1[] : i <= 0 }"),
710 computeReachingWrite(UMAP("{ Dom1[] -> [0]; Dom2[] -> [10] }"),
711 UMAP("{ Dom1[] -> Elt[]; Dom2[] -> Elt[] }"),
714 // Domain in same space
715 EXPECT_EQ(UMAP("{ [Elt[] -> [i]] -> Dom[1] : 0 < i <= 10; [Elt[] -> [i]] -> "
716 "Dom[2] : 10 < i }"),
717 computeReachingWrite(UMAP("{ Dom[i] -> [10i - 10] }"),
718 UMAP("{ Dom[1] -> Elt[]; Dom[2] -> Elt[] }"),
719 false, false, true));
722 EXPECT_EQ(UMAP("[p] -> { [Elt[] -> [i]] -> Dom[] : p < i }"),
723 computeReachingWrite(UMAP("[p] -> { Dom[] -> [p] }"),
724 UMAP("{ Dom[] -> Elt[] }"), false, false,
727 // More realistic example (from reduction_embedded.ll)
729 UMAP("{ [Elt[] -> [i]] -> Dom[0] : 0 < i <= 3; [Elt[] -> [i]] -> Dom[1] "
730 ": 3 < i <= 6; [Elt[] -> [i]] -> Dom[2] : 6 < i <= 9; [Elt[] -> "
731 "[i]] -> Dom[3] : 9 < i <= 12; [Elt[] -> [i]] -> Dom[4] : 12 < i }"),
732 computeReachingWrite(UMAP("{ Dom[i] -> [3i] : 0 <= i <= 4 }"),
733 UMAP("{ Dom[i] -> Elt[] : 0 <= i <= 4 }"), false,
737 TEST(DeLICM
, computeArrayUnused
) {
738 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
741 // The ReadEltInSameInst parameter doesn't matter in simple cases. To also
742 // cover the parameter without duplicating the tests, this loops runs over
743 // other in both settings.
744 for (bool ReadEltInSameInst
= false, Done
= false; !Done
;
745 Done
= ReadEltInSameInst
, ReadEltInSameInst
= true) {
746 // Basic usage: one read, one write
747 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i < 10 }"),
748 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
749 UMAP("{ Write[] -> Elt[] }"),
750 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst
,
752 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"),
753 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
754 UMAP("{ Write[] -> Elt[] }"),
755 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst
,
757 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 <= i < 10 }"),
758 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
759 UMAP("{ Write[] -> Elt[] }"),
760 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst
,
762 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 <= i <= 10 }"),
763 computeArrayUnused(UMAP("{ Read[] -> [0]; Write[] -> [10] }"),
764 UMAP("{ Write[] -> Elt[] }"),
765 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst
,
769 EXPECT_EQ(UMAP("{ Elt[] -> [i] : 0 < i <= 10 }"),
771 UMAP("{ Read[0] -> [-10]; Read[1] -> [0]; Write[] -> [10] }"),
772 UMAP("{ Write[] -> Elt[] }"), UMAP("{ Read[i] -> Elt[] }"),
773 ReadEltInSameInst
, false, true));
775 // Corner case: no writes
776 EXPECT_EQ(UMAP("{}"),
777 computeArrayUnused(UMAP("{ Read[] -> [0] }"), UMAP("{}"),
778 UMAP("{ Read[] -> Elt[] }"), ReadEltInSameInst
,
781 // Corner case: no reads
782 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"),
783 computeArrayUnused(UMAP("{ Write[] -> [0] }"),
784 UMAP("{ Write[] -> Elt[] }"), UMAP("{}"),
785 ReadEltInSameInst
, false, true));
788 // Read and write in same statement
789 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i < 0 }"),
790 computeArrayUnused(UMAP("{ RW[] -> [0] }"),
791 UMAP("{ RW[] -> Elt[] }"),
792 UMAP("{ RW[] -> Elt[] }"), true, false, false));
793 EXPECT_EQ(UMAP("{ Elt[] -> [i] : i <= 0 }"),
794 computeArrayUnused(UMAP("{ RW[] -> [0] }"),
795 UMAP("{ RW[] -> Elt[] }"),
796 UMAP("{ RW[] -> Elt[] }"), true, false, true));
797 EXPECT_EQ(UMAP("{ Elt[] -> [0] }"),
798 computeArrayUnused(UMAP("{ RW[] -> [0] }"),
799 UMAP("{ RW[] -> Elt[] }"),
800 UMAP("{ RW[] -> Elt[] }"), false, true, true));
803 TEST(DeLICM
, convertZoneToTimepoints
) {
804 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
807 // Corner case: empty set
808 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), false, false));
809 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), true, false));
810 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), false, true));
811 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{}"), true, true));
814 EXPECT_EQ(USET("{}"), convertZoneToTimepoints(USET("{ [1] }"), false, false));
815 EXPECT_EQ(USET("{ [0] }"),
816 convertZoneToTimepoints(USET("{ [1] }"), true, false));
817 EXPECT_EQ(USET("{ [1] }"),
818 convertZoneToTimepoints(USET("{ [1] }"), false, true));
819 EXPECT_EQ(USET("{ [0]; [1] }"),
820 convertZoneToTimepoints(USET("{ [1] }"), true, true));
822 // Non-adjacent ranges
823 EXPECT_EQ(USET("{}"),
824 convertZoneToTimepoints(USET("{ [1]; [11] }"), false, false));
825 EXPECT_EQ(USET("{ [0]; [10] }"),
826 convertZoneToTimepoints(USET("{ [1]; [11] }"), true, false));
827 EXPECT_EQ(USET("{ [1]; [11] }"),
828 convertZoneToTimepoints(USET("{ [1]; [11] }"), false, true));
829 EXPECT_EQ(USET("{ [0]; [1]; [10]; [11] }"),
830 convertZoneToTimepoints(USET("{ [1]; [11] }"), true, true));
832 // Adjacent unit ranges
834 USET("{ [i] : 0 < i < 10 }"),
835 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, false));
837 USET("{ [i] : 0 <= i < 10 }"),
838 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, false));
840 USET("{ [i] : 0 < i <= 10 }"),
841 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), false, true));
842 EXPECT_EQ(USET("{ [i] : 0 <= i <= 10 }"),
843 convertZoneToTimepoints(USET("{ [i] : 0 < i <= 10 }"), true, true));
845 // More than one dimension
846 EXPECT_EQ(USET("{}"),
847 convertZoneToTimepoints(USET("{ [0,1] }"), false, false));
848 EXPECT_EQ(USET("{ [0,0] }"),
849 convertZoneToTimepoints(USET("{ [0,1] }"), true, false));
850 EXPECT_EQ(USET("{ [0,1] }"),
851 convertZoneToTimepoints(USET("{ [0,1] }"), false, true));
852 EXPECT_EQ(USET("{ [0,0]; [0,1] }"),
853 convertZoneToTimepoints(USET("{ [0,1] }"), true, true));
856 EXPECT_EQ(UMAP("{}"), convertZoneToTimepoints(UMAP("{ [1] -> [] }"),
857 isl::dim::in
, false, false));
858 EXPECT_EQ(UMAP("{ [0] -> [] }"),
859 convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in
, true,
861 EXPECT_EQ(UMAP("{ [1] -> [] }"),
862 convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in
, false,
865 UMAP("{ [0] -> []; [1] -> [] }"),
866 convertZoneToTimepoints(UMAP("{ [1] -> [] }"), isl::dim::in
, true, true));
869 EXPECT_EQ(UMAP("{}"), convertZoneToTimepoints(UMAP("{ [] -> [1] }"),
870 isl::dim::out
, false, false));
871 EXPECT_EQ(UMAP("{ [] -> [0] }"),
872 convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out
, true,
874 EXPECT_EQ(UMAP("{ [] -> [1] }"),
875 convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out
, false,
877 EXPECT_EQ(UMAP("{ [] -> [0]; [] -> [1] }"),
878 convertZoneToTimepoints(UMAP("{ [] -> [1] }"), isl::dim::out
, true,
882 TEST(DeLICM
, distribute
) {
883 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
887 EXPECT_EQ(MAP("{ [Domain[] -> Range1[]] -> [Domain[] -> Range2[]] }"),
888 distributeDomain(MAP("{ Domain[] -> [Range1[] -> Range2[]] }")));
890 MAP("{ [Domain[i,j] -> Range1[i,k]] -> [Domain[i,j] -> Range2[j,k]] }"),
891 distributeDomain(MAP("{ Domain[i,j] -> [Range1[i,k] -> Range2[j,k]] }")));
896 "{ [DomainA[i,j] -> RangeA1[i,k]] -> [DomainA[i,j] -> RangeA2[j,k]];"
897 "[DomainB[i,j] -> RangeB1[i,k]] -> [DomainB[i,j] -> RangeB2[j,k]] }"),
899 UMAP("{ DomainA[i,j] -> [RangeA1[i,k] -> RangeA2[j,k]];"
900 "DomainB[i,j] -> [RangeB1[i,k] -> RangeB2[j,k]] }")));
904 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
908 EXPECT_EQ(UMAP("{ [Factor[] -> Domain[]] -> [Factor[] -> Range[]] }"),
909 liftDomains(UMAP("{ Domain[] -> Range[] }"), USET("{ Factor[] }")));
910 EXPECT_EQ(UMAP("{ [Factor[l] -> Domain[i,k]] -> [Factor[l] -> Range[j,k]] }"),
911 liftDomains(UMAP("{ Domain[i,k] -> Range[j,k] }"),
912 USET("{ Factor[l] }")));
914 // Multiple maps in union
916 UMAP("{ [FactorA[] -> DomainA[]] -> [FactorA[] -> RangeA[]];"
917 "[FactorB[] -> DomainA[]] -> [FactorB[] -> RangeA[]];"
918 "[FactorA[] -> DomainB[]] -> [FactorA[] -> RangeB[]];"
919 "[FactorB[] -> DomainB[]] -> [FactorB[] -> RangeB[]] }"),
920 liftDomains(UMAP("{ DomainA[] -> RangeA[]; DomainB[] -> RangeB[] }"),
921 USET("{ FactorA[]; FactorB[] }")));
924 TEST(DeLICM
, apply
) {
925 std::unique_ptr
<isl_ctx
, decltype(&isl_ctx_free
)> Ctx(isl_ctx_alloc(),
930 UMAP("{ [DomainDomain[] -> NewDomainRange[]] -> Range[] }"),
931 applyDomainRange(UMAP("{ [DomainDomain[] -> DomainRange[]] -> Range[] }"),
932 UMAP("{ DomainRange[] -> NewDomainRange[] }")));
934 UMAP("{ [DomainDomain[i,k] -> NewDomainRange[j,k,l]] -> Range[i,j] }"),
936 UMAP("{ [DomainDomain[i,k] -> DomainRange[j,k]] -> Range[i,j] }"),
937 UMAP("{ DomainRange[j,k] -> NewDomainRange[j,k,l] }")));
939 // Multiple maps in union
940 EXPECT_EQ(UMAP("{ [DomainDomainA[] -> NewDomainRangeA[]] -> RangeA[];"
941 "[DomainDomainB[] -> NewDomainRangeB[]] -> RangeB[] }"),
943 UMAP("{ [DomainDomainA[] -> DomainRangeA[]] -> RangeA[];"
944 "[DomainDomainB[] -> DomainRangeB[]] -> RangeB[] }"),
945 UMAP("{ DomainRangeA[] -> NewDomainRangeA[];"
946 "DomainRangeB[] -> NewDomainRangeB[] }")));
949 } // anonymous namespace