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