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