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 | |
19 | static isl::space parseSpace(isl_ctx *Ctx, const char *Str) { |
20 | isl_stream *Stream = isl_stream_new_str(ctx: Ctx, str: Str); |
21 | auto Obj = isl_stream_read_obj(s: Stream); |
22 | |
23 | isl::space Result; |
24 | if (Obj.type == isl_obj_set) |
25 | Result = isl::manage(ptr: isl_set_get_space(set: static_cast<isl_set *>(Obj.v))); |
26 | else if (Obj.type == isl_obj_map) |
27 | Result = isl::manage(ptr: isl_map_get_space(map: static_cast<isl_map *>(Obj.v))); |
28 | |
29 | isl_stream_free(s: 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 | |
46 | static bool operator==(const isl::space &LHS, const isl::space &RHS) { |
47 | return bool(LHS.is_equal(space2: RHS)); |
48 | } |
49 | |
50 | static bool operator==(const isl::set &LHS, const isl::set &RHS) { |
51 | return bool(LHS.is_equal(set2: RHS)); |
52 | } |
53 | |
54 | static bool operator==(const isl::map &LHS, const isl::map &RHS) { |
55 | return bool(LHS.is_equal(map2: RHS)); |
56 | } |
57 | |
58 | static bool operator==(const isl::union_set &LHS, const isl::union_set &RHS) { |
59 | return bool(LHS.is_equal(uset2: RHS)); |
60 | } |
61 | |
62 | static bool operator==(const isl::union_map &LHS, const isl::union_map &RHS) { |
63 | return bool(LHS.is_equal(umap2: RHS)); |
64 | } |
65 | |
66 | static bool operator==(const isl::val &LHS, const isl::val &RHS) { |
67 | return bool(LHS.eq(v2: RHS)); |
68 | } |
69 | |
70 | static bool operator==(const isl::pw_aff &LHS, const isl::pw_aff &RHS) { |
71 | return bool(LHS.is_equal(pa2: RHS)); |
72 | } |
73 | } // namespace noexceptions |
74 | } // namespace isl |
75 | |
76 | namespace { |
77 | |
78 | TEST(Isl, APIntToIslVal) { |
79 | isl_ctx *IslCtx = isl_ctx_alloc(); |
80 | |
81 | { |
82 | APInt APZero(1, 0, true); |
83 | auto IslZero = valFromAPInt(Ctx: IslCtx, Int: APZero, IsSigned: true); |
84 | EXPECT_TRUE(IslZero.is_zero()); |
85 | } |
86 | |
87 | { |
88 | APInt APNOne(1, -1, true); |
89 | auto IslNOne = valFromAPInt(Ctx: IslCtx, Int: APNOne, IsSigned: true); |
90 | EXPECT_TRUE(IslNOne.is_negone()); |
91 | } |
92 | |
93 | { |
94 | APInt APZero(1, 0, false); |
95 | auto IslZero = valFromAPInt(Ctx: IslCtx, Int: APZero, IsSigned: false); |
96 | EXPECT_TRUE(IslZero.is_zero()); |
97 | } |
98 | |
99 | { |
100 | APInt APOne(1, 1, false); |
101 | auto IslOne = valFromAPInt(Ctx: IslCtx, Int: APOne, IsSigned: false); |
102 | EXPECT_TRUE(IslOne.is_one()); |
103 | } |
104 | |
105 | { |
106 | APInt APNTwo(2, -2, true); |
107 | auto IslNTwo = valFromAPInt(Ctx: IslCtx, Int: APNTwo, IsSigned: 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(Ctx: IslCtx, Int: APNOne, IsSigned: true); |
115 | EXPECT_TRUE(IslNOne.is_negone()); |
116 | } |
117 | |
118 | { |
119 | APInt APZero(32, 0, false); |
120 | auto IslZero = valFromAPInt(Ctx: IslCtx, Int: APZero, IsSigned: false); |
121 | EXPECT_TRUE(IslZero.is_zero()); |
122 | } |
123 | |
124 | { |
125 | APInt APOne(32, 1, false); |
126 | auto IslOne = valFromAPInt(Ctx: IslCtx, Int: APOne, IsSigned: false); |
127 | EXPECT_TRUE(IslOne.is_one()); |
128 | } |
129 | |
130 | { |
131 | APInt APTwo(32, 2, false); |
132 | auto IslTwo = valFromAPInt(Ctx: IslCtx, Int: APTwo, IsSigned: false); |
133 | EXPECT_EQ(0, IslTwo.cmp_si(2)); |
134 | } |
135 | |
136 | { |
137 | APInt APNOne(32, (1ull << 32) - 1, false); |
138 | auto IslNOne = valFromAPInt(Ctx: IslCtx, Int: APNOne, IsSigned: false); |
139 | auto IslRef = isl::val(IslCtx, 32).pow2().sub(v2: 1); |
140 | EXPECT_EQ(IslNOne, IslRef); |
141 | } |
142 | |
143 | { |
144 | APInt APLarge(130, 2, false); |
145 | APLarge = APLarge.shl(shiftAmt: 70); |
146 | auto IslLarge = valFromAPInt(Ctx: IslCtx, Int: APLarge, IsSigned: false); |
147 | auto IslRef = isl::val(IslCtx, 71); |
148 | IslRef = IslRef.pow2(); |
149 | EXPECT_EQ(IslLarge, IslRef); |
150 | } |
151 | |
152 | isl_ctx_free(ctx: IslCtx); |
153 | } |
154 | |
155 | TEST(Isl, IslValToAPInt) { |
156 | isl_ctx *IslCtx = isl_ctx_alloc(); |
157 | |
158 | { |
159 | auto IslNOne = isl::val(IslCtx, -1); |
160 | auto APNOne = APIntFromVal(V: 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(V: 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(V: 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(V: 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(V: 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(V: 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(V: 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(V: 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(V: IslFour); |
221 | EXPECT_EQ(4, APFour); |
222 | EXPECT_EQ(4u, APFour.getBitWidth()); |
223 | } |
224 | |
225 | { |
226 | auto IslNOne = isl::val(IslCtx, 32).pow2().sub(v2: 1); |
227 | auto APNOne = APIntFromVal(V: 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(v2: 1); |
236 | auto APLargeNum = APIntFromVal(V: 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(V: 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(V: 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(V: 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(V: 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(ctx: IslCtx); |
278 | } |
279 | |
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 | |
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(fn: [&](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(fn: [&](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(fn: [&](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(fn: [&](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: Ctx.get())); |
440 | auto NumPwAffs = 0; |
441 | isl::stat Stat = UPwAff.foreach_pw_aff(fn: [&](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: Ctx.get())); |
476 | auto NumPieces = 0; |
477 | isl::stat Stat = TestPwAff.foreach_piece( |
478 | fn: [&](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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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 | |
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: Ctx.get(), name: "A" , user: nullptr); |
1125 | isl::id::alloc(ctx: Ctx.get(), name: "B" , user: nullptr); |
1126 | ASSERT_TRUE(MaxOpGuard.hasQuotaExceeded()); |
1127 | |
1128 | // Check returned object after exceeded quota. |
1129 | isl::set Union = TestSet1.unite(set2: 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(fn: [](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(set2: 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(fn: [](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 | |