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