1 //===------ ISLTools.cpp ----------------------------------------*- C++ -*-===//
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 // Tools, utilities, helpers and extensions useful in conjunction with the
10 // Integer Set Library (isl).
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "polly/Support/ISLTools.h"
15 #include "polly/Support/GICHelper.h"
16 #include "llvm/Support/raw_ostream.h"
17 #include <cassert>
18 #include <vector>
19
20 using namespace polly;
21
22 namespace {
23 /// Create a map that shifts one dimension by an offset.
24 ///
25 /// Example:
26 /// makeShiftDimAff({ [i0, i1] -> [o0, o1] }, 1, -2)
27 /// = { [i0, i1] -> [i0, i1 - 1] }
28 ///
grn_mrb_options_get_static(mrb_state * mrb,mrb_value mrb_options,const char * key,size_t key_size)29 /// @param Space The map space of the result. Must have equal number of in- and
30 /// out-dimensions.
31 /// @param Pos Position to shift.
32 /// @param Amount Value added to the shifted dimension.
33 ///
34 /// @return An isl_multi_aff for the map with this shifted dimension.
35 isl::multi_aff makeShiftDimAff(isl::space Space, int Pos, int Amount) {
36 auto Identity = isl::multi_aff::identity(Space);
37 if (Amount == 0)
38 return Identity;
39 auto ShiftAff = Identity.get_aff(Pos);
40 ShiftAff = ShiftAff.set_constant_si(Amount);
41 return Identity.set_aff(Pos, ShiftAff);
42 }
43
44 /// Construct a map that swaps two nested tuples.
45 ///
46 /// @param FromSpace1 { Space1[] }
47 /// @param FromSpace2 { Space2[] }
48 ///
49 /// @return { [Space1[] -> Space2[]] -> [Space2[] -> Space1[]] }
50 isl::basic_map makeTupleSwapBasicMap(isl::space FromSpace1,
51 isl::space FromSpace2) {
52 // Fast-path on out-of-quota.
53 if (FromSpace1.is_null() || FromSpace2.is_null())
54 return {};
55
56 assert(FromSpace1.is_set());
57 assert(FromSpace2.is_set());
58
59 unsigned Dims1 = FromSpace1.dim(isl::dim::set);
60 unsigned Dims2 = FromSpace2.dim(isl::dim::set);
61
62 isl::space FromSpace =
63 FromSpace1.map_from_domain_and_range(FromSpace2).wrap();
64 isl::space ToSpace = FromSpace2.map_from_domain_and_range(FromSpace1).wrap();
65 isl::space MapSpace = FromSpace.map_from_domain_and_range(ToSpace);
66
67 isl::basic_map Result = isl::basic_map::universe(MapSpace);
68 for (unsigned i = 0u; i < Dims1; i += 1)
69 Result = Result.equate(isl::dim::in, i, isl::dim::out, Dims2 + i);
70 for (unsigned i = 0u; i < Dims2; i += 1) {
71 Result = Result.equate(isl::dim::in, Dims1 + i, isl::dim::out, i);
72 }
73
74 return Result;
75 }
76
77 /// Like makeTupleSwapBasicMap(isl::space,isl::space), but returns
78 /// an isl_map.
79 isl::map makeTupleSwapMap(isl::space FromSpace1, isl::space FromSpace2) {
80 isl::basic_map BMapResult = makeTupleSwapBasicMap(FromSpace1, FromSpace2);
81 return isl::map(BMapResult);
82 }
83 } // anonymous namespace
84
85 isl::map polly::beforeScatter(isl::map Map, bool Strict) {
86 isl::space RangeSpace = Map.get_space().range();
87 isl::map ScatterRel =
88 Strict ? isl::map::lex_gt(RangeSpace) : isl::map::lex_ge(RangeSpace);
89 return Map.apply_range(ScatterRel);
90 }
91
92 isl::union_map polly::beforeScatter(isl::union_map UMap, bool Strict) {
93 isl::union_map Result = isl::union_map::empty(UMap.ctx());
94
95 for (isl::map Map : UMap.get_map_list()) {
96 isl::map After = beforeScatter(Map, Strict);
97 Result = Result.unite(After);
98 }
99
100 return Result;
101 }
102
103 isl::map polly::afterScatter(isl::map Map, bool Strict) {
104 isl::space RangeSpace = Map.get_space().range();
105 isl::map ScatterRel =
106 Strict ? isl::map::lex_lt(RangeSpace) : isl::map::lex_le(RangeSpace);
107 return Map.apply_range(ScatterRel);
108 }
109
110 isl::union_map polly::afterScatter(const isl::union_map &UMap, bool Strict) {
111 isl::union_map Result = isl::union_map::empty(UMap.ctx());
112 for (isl::map Map : UMap.get_map_list()) {
113 isl::map After = afterScatter(Map, Strict);
114 Result = Result.unite(After);
115 }
116 return Result;
117 }
118
119 isl::map polly::betweenScatter(isl::map From, isl::map To, bool InclFrom,
120 bool InclTo) {
121 isl::map AfterFrom = afterScatter(From, !InclFrom);
122 isl::map BeforeTo = beforeScatter(To, !InclTo);
123
124 return AfterFrom.intersect(BeforeTo);
125 }
126
127 isl::union_map polly::betweenScatter(isl::union_map From, isl::union_map To,
128 bool InclFrom, bool InclTo) {
129 isl::union_map AfterFrom = afterScatter(From, !InclFrom);
130 isl::union_map BeforeTo = beforeScatter(To, !InclTo);
131
132 return AfterFrom.intersect(BeforeTo);
133 }
134
135 isl::map polly::singleton(isl::union_map UMap, isl::space ExpectedSpace) {
136 if (UMap.is_null())
137 return {};
138
139 if (isl_union_map_n_map(UMap.get()) == 0)
140 return isl::map::empty(ExpectedSpace);
141
142 isl::map Result = isl::map::from_union_map(UMap);
143 assert(Result.is_null() ||
144 Result.get_space().has_equal_tuples(ExpectedSpace));
145
146 return Result;
147 }
148
149 isl::set polly::singleton(isl::union_set USet, isl::space ExpectedSpace) {
150 if (USet.is_null())
151 return {};
152
153 if (isl_union_set_n_set(USet.get()) == 0)
154 return isl::set::empty(ExpectedSpace);
155
156 isl::set Result(USet);
157 assert(Result.is_null() ||
158 Result.get_space().has_equal_tuples(ExpectedSpace));
159
160 return Result;
161 }
162
163 isl_size polly::getNumScatterDims(const isl::union_map &Schedule) {
164 isl_size Dims = 0;
165 for (isl::map Map : Schedule.get_map_list()) {
166 if (Map.is_null())
167 continue;
168
169 Dims = std::max(Dims, Map.range_tuple_dim());
170 }
171 return Dims;
172 }
173
174 isl::space polly::getScatterSpace(const isl::union_map &Schedule) {
175 if (Schedule.is_null())
176 return {};
177 unsigned Dims = getNumScatterDims(Schedule);
178 isl::space ScatterSpace = Schedule.get_space().set_from_params();
179 return ScatterSpace.add_dims(isl::dim::set, Dims);
180 }
181
182 isl::map polly::makeIdentityMap(const isl::set &Set, bool RestrictDomain) {
183 isl::map Result = isl::map::identity(Set.get_space().map_from_set());
184 if (RestrictDomain)
185 Result = Result.intersect_domain(Set);
186 return Result;
187 }
188
189 isl::union_map polly::makeIdentityMap(const isl::union_set &USet,
190 bool RestrictDomain) {
191 isl::union_map Result = isl::union_map::empty(USet.ctx());
192 for (isl::set Set : USet.get_set_list()) {
193 isl::map IdentityMap = makeIdentityMap(Set, RestrictDomain);
194 Result = Result.unite(IdentityMap);
195 }
196 return Result;
197 }
198
199 isl::map polly::reverseDomain(isl::map Map) {
200 isl::space DomSpace = Map.get_space().domain().unwrap();
201 isl::space Space1 = DomSpace.domain();
202 isl::space Space2 = DomSpace.range();
203 isl::map Swap = makeTupleSwapMap(Space1, Space2);
204 return Map.apply_domain(Swap);
205 }
206
207 isl::union_map polly::reverseDomain(const isl::union_map &UMap) {
208 isl::union_map Result = isl::union_map::empty(UMap.ctx());
209 for (isl::map Map : UMap.get_map_list()) {
210 auto Reversed = reverseDomain(std::move(Map));
211 Result = Result.unite(Reversed);
212 }
213 return Result;
214 }
215
216 isl::set polly::shiftDim(isl::set Set, int Pos, int Amount) {
217 int NumDims = Set.tuple_dim();
218 if (Pos < 0)
219 Pos = NumDims + Pos;
220 assert(Pos < NumDims && "Dimension index must be in range");
221 isl::space Space = Set.get_space();
222 Space = Space.map_from_domain_and_range(Space);
223 isl::multi_aff Translator = makeShiftDimAff(Space, Pos, Amount);
224 isl::map TranslatorMap = isl::map::from_multi_aff(Translator);
225 return Set.apply(TranslatorMap);
226 }
227
228 isl::union_set polly::shiftDim(isl::union_set USet, int Pos, int Amount) {
229 isl::union_set Result = isl::union_set::empty(USet.ctx());
230 for (isl::set Set : USet.get_set_list()) {
231 isl::set Shifted = shiftDim(Set, Pos, Amount);
232 Result = Result.unite(Shifted);
233 }
234 return Result;
235 }
236
237 isl::map polly::shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount) {
238 int NumDims = Map.dim(Dim);
239 if (Pos < 0)
240 Pos = NumDims + Pos;
241 assert(Pos < NumDims && "Dimension index must be in range");
242 isl::space Space = Map.get_space();
243 switch (Dim) {
244 case isl::dim::in:
245 Space = Space.domain();
246 break;
247 case isl::dim::out:
248 Space = Space.range();
249 break;
250 default:
251 llvm_unreachable("Unsupported value for 'dim'");
252 }
253 Space = Space.map_from_domain_and_range(Space);
254 isl::multi_aff Translator = makeShiftDimAff(Space, Pos, Amount);
255 isl::map TranslatorMap = isl::map::from_multi_aff(Translator);
256 switch (Dim) {
257 case isl::dim::in:
258 return Map.apply_domain(TranslatorMap);
259 case isl::dim::out:
260 return Map.apply_range(TranslatorMap);
261 default:
262 llvm_unreachable("Unsupported value for 'dim'");
263 }
264 }
265
266 isl::union_map polly::shiftDim(isl::union_map UMap, isl::dim Dim, int Pos,
267 int Amount) {
268 isl::union_map Result = isl::union_map::empty(UMap.ctx());
269
270 for (isl::map Map : UMap.get_map_list()) {
271 isl::map Shifted = shiftDim(Map, Dim, Pos, Amount);
272 Result = Result.unite(Shifted);
273 }
274 return Result;
275 }
276
277 void polly::simplify(isl::set &Set) {
278 Set = isl::manage(isl_set_compute_divs(Set.copy()));
279 Set = Set.detect_equalities();
280 Set = Set.coalesce();
281 }
282
283 void polly::simplify(isl::union_set &USet) {
284 USet = isl::manage(isl_union_set_compute_divs(USet.copy()));
285 USet = USet.detect_equalities();
286 USet = USet.coalesce();
287 }
288
289 void polly::simplify(isl::map &Map) {
290 Map = isl::manage(isl_map_compute_divs(Map.copy()));
291 Map = Map.detect_equalities();
292 Map = Map.coalesce();
293 }
294
295 void polly::simplify(isl::union_map &UMap) {
296 UMap = isl::manage(isl_union_map_compute_divs(UMap.copy()));
297 UMap = UMap.detect_equalities();
298 UMap = UMap.coalesce();
299 }
300
301 isl::union_map polly::computeReachingWrite(isl::union_map Schedule,
302 isl::union_map Writes, bool Reverse,
303 bool InclPrevDef, bool InclNextDef) {
304
305 // { Scatter[] }
306 isl::space ScatterSpace = getScatterSpace(Schedule);
307
308 // { ScatterRead[] -> ScatterWrite[] }
309 isl::map Relation;
310 if (Reverse)
311 Relation = InclPrevDef ? isl::map::lex_lt(ScatterSpace)
312 : isl::map::lex_le(ScatterSpace);
313 else
314 Relation = InclNextDef ? isl::map::lex_gt(ScatterSpace)
315 : isl::map::lex_ge(ScatterSpace);
316
317 // { ScatterWrite[] -> [ScatterRead[] -> ScatterWrite[]] }
318 isl::map RelationMap = Relation.range_map().reverse();
319
320 // { Element[] -> ScatterWrite[] }
321 isl::union_map WriteAction = Schedule.apply_domain(Writes);
322
323 // { ScatterWrite[] -> Element[] }
324 isl::union_map WriteActionRev = WriteAction.reverse();
325
326 // { Element[] -> [ScatterUse[] -> ScatterWrite[]] }
327 isl::union_map DefSchedRelation =
328 isl::union_map(RelationMap).apply_domain(WriteActionRev);
329
330 // For each element, at every point in time, map to the times of previous
331 // definitions. { [Element[] -> ScatterRead[]] -> ScatterWrite[] }
332 isl::union_map ReachableWrites = DefSchedRelation.uncurry();
333 if (Reverse)
334 ReachableWrites = ReachableWrites.lexmin();
335 else
336 ReachableWrites = ReachableWrites.lexmax();
337
338 // { [Element[] -> ScatterWrite[]] -> ScatterWrite[] }
339 isl::union_map SelfUse = WriteAction.range_map();
340
341 if (InclPrevDef && InclNextDef) {
342 // Add the Def itself to the solution.
343 ReachableWrites = ReachableWrites.unite(SelfUse).coalesce();
344 } else if (!InclPrevDef && !InclNextDef) {
345 // Remove Def itself from the solution.
346 ReachableWrites = ReachableWrites.subtract(SelfUse);
347 }
348
349 // { [Element[] -> ScatterRead[]] -> Domain[] }
350 return ReachableWrites.apply_range(Schedule.reverse());
351 }
352
353 isl::union_map
354 polly::computeArrayUnused(isl::union_map Schedule, isl::union_map Writes,
355 isl::union_map Reads, bool ReadEltInSameInst,
356 bool IncludeLastRead, bool IncludeWrite) {
357 // { Element[] -> Scatter[] }
358 isl::union_map ReadActions = Schedule.apply_domain(Reads);
359 isl::union_map WriteActions = Schedule.apply_domain(Writes);
360
361 // { [Element[] -> DomainWrite[]] -> Scatter[] }
362 isl::union_map EltDomWrites =
363 Writes.reverse().range_map().apply_range(Schedule);
364
365 // { [Element[] -> Scatter[]] -> DomainWrite[] }
366 isl::union_map ReachingOverwrite = computeReachingWrite(
367 Schedule, Writes, true, ReadEltInSameInst, !ReadEltInSameInst);
368
369 // { [Element[] -> Scatter[]] -> DomainWrite[] }
370 isl::union_map ReadsOverwritten =
371 ReachingOverwrite.intersect_domain(ReadActions.wrap());
372
373 // { [Element[] -> DomainWrite[]] -> Scatter[] }
374 isl::union_map ReadsOverwrittenRotated =
375 reverseDomain(ReadsOverwritten).curry().reverse();
376 isl::union_map LastOverwrittenRead = ReadsOverwrittenRotated.lexmax();
377
378 // { [Element[] -> DomainWrite[]] -> Scatter[] }
379 isl::union_map BetweenLastReadOverwrite = betweenScatter(
380 LastOverwrittenRead, EltDomWrites, IncludeLastRead, IncludeWrite);
381
382 // { [Element[] -> Scatter[]] -> DomainWrite[] }
383 isl::union_map ReachingOverwriteZone = computeReachingWrite(
384 Schedule, Writes, true, IncludeLastRead, IncludeWrite);
385
386 // { [Element[] -> DomainWrite[]] -> Scatter[] }
387 isl::union_map ReachingOverwriteRotated =
388 reverseDomain(ReachingOverwriteZone).curry().reverse();
389
390 // { [Element[] -> DomainWrite[]] -> Scatter[] }
391 isl::union_map WritesWithoutReads = ReachingOverwriteRotated.subtract_domain(
392 ReadsOverwrittenRotated.domain());
393
394 return BetweenLastReadOverwrite.unite(WritesWithoutReads)
395 .domain_factor_domain();
396 }
397
398 isl::union_set polly::convertZoneToTimepoints(isl::union_set Zone,
399 bool InclStart, bool InclEnd) {
400 if (!InclStart && InclEnd)
401 return Zone;
402
403 auto ShiftedZone = shiftDim(Zone, -1, -1);
404 if (InclStart && !InclEnd)
405 return ShiftedZone;
406 else if (!InclStart && !InclEnd)
407 return Zone.intersect(ShiftedZone);
408
409 assert(InclStart && InclEnd);
410 return Zone.unite(ShiftedZone);
411 }
412
413 isl::union_map polly::convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,
414 bool InclStart, bool InclEnd) {
415 if (!InclStart && InclEnd)
416 return Zone;
417
418 auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
419 if (InclStart && !InclEnd)
420 return ShiftedZone;
421 else if (!InclStart && !InclEnd)
422 return Zone.intersect(ShiftedZone);
423
424 assert(InclStart && InclEnd);
425 return Zone.unite(ShiftedZone);
426 }
427
428 isl::map polly::convertZoneToTimepoints(isl::map Zone, isl::dim Dim,
429 bool InclStart, bool InclEnd) {
430 if (!InclStart && InclEnd)
431 return Zone;
432
433 auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
434 if (InclStart && !InclEnd)
435 return ShiftedZone;
436 else if (!InclStart && !InclEnd)
437 return Zone.intersect(ShiftedZone);
438
439 assert(InclStart && InclEnd);
440 return Zone.unite(ShiftedZone);
441 }
442
443 isl::map polly::distributeDomain(isl::map Map) {
444 // Note that we cannot take Map apart into { Domain[] -> Range1[] } and {
445 // Domain[] -> Range2[] } and combine again. We would loose any relation
446 // between Range1[] and Range2[] that is not also a constraint to Domain[].
447
448 isl::space Space = Map.get_space();
449 isl::space DomainSpace = Space.domain();
450 if (DomainSpace.is_null())
451 return {};
452 unsigned DomainDims = DomainSpace.dim(isl::dim::set);
453 isl::space RangeSpace = Space.range().unwrap();
454 isl::space Range1Space = RangeSpace.domain();
455 if (Range1Space.is_null())
456 return {};
457 unsigned Range1Dims = Range1Space.dim(isl::dim::set);
458 isl::space Range2Space = RangeSpace.range();
459 if (Range2Space.is_null())
460 return {};
461 unsigned Range2Dims = Range2Space.dim(isl::dim::set);
462
463 isl::space OutputSpace =
464 DomainSpace.map_from_domain_and_range(Range1Space)
465 .wrap()
466 .map_from_domain_and_range(
467 DomainSpace.map_from_domain_and_range(Range2Space).wrap());
468
469 isl::basic_map Translator = isl::basic_map::universe(
470 Space.wrap().map_from_domain_and_range(OutputSpace.wrap()));
471
472 for (unsigned i = 0; i < DomainDims; i += 1) {
473 Translator = Translator.equate(isl::dim::in, i, isl::dim::out, i);
474 Translator = Translator.equate(isl::dim::in, i, isl::dim::out,
475 DomainDims + Range1Dims + i);
476 }
477 for (unsigned i = 0; i < Range1Dims; i += 1)
478 Translator = Translator.equate(isl::dim::in, DomainDims + i, isl::dim::out,
479 DomainDims + i);
480 for (unsigned i = 0; i < Range2Dims; i += 1)
481 Translator = Translator.equate(isl::dim::in, DomainDims + Range1Dims + i,
482 isl::dim::out,
483 DomainDims + Range1Dims + DomainDims + i);
484
485 return Map.wrap().apply(Translator).unwrap();
486 }
487
488 isl::union_map polly::distributeDomain(isl::union_map UMap) {
489 isl::union_map Result = isl::union_map::empty(UMap.ctx());
490 for (isl::map Map : UMap.get_map_list()) {
491 auto Distributed = distributeDomain(Map);
492 Result = Result.unite(Distributed);
493 }
494 return Result;
495 }
496
497 isl::union_map polly::liftDomains(isl::union_map UMap, isl::union_set Factor) {
498
499 // { Factor[] -> Factor[] }
500 isl::union_map Factors = makeIdentityMap(Factor, true);
501
502 return Factors.product(UMap);
503 }
504
505 isl::union_map polly::applyDomainRange(isl::union_map UMap,
506 isl::union_map Func) {
507 // This implementation creates unnecessary cross products of the
508 // DomainDomain[] and Func. An alternative implementation could reverse
509 // domain+uncurry,apply Func to what now is the domain, then undo the
510 // preparing transformation. Another alternative implementation could create a
511 // translator map for each piece.
512
513 // { DomainDomain[] }
514 isl::union_set DomainDomain = UMap.domain().unwrap().domain();
515
516 // { [DomainDomain[] -> DomainRange[]] -> [DomainDomain[] -> NewDomainRange[]]
517 // }
518 isl::union_map LifetedFunc = liftDomains(std::move(Func), DomainDomain);
519
520 return UMap.apply_domain(LifetedFunc);
521 }
522
523 isl::map polly::intersectRange(isl::map Map, isl::union_set Range) {
524 isl::set RangeSet = Range.extract_set(Map.get_space().range());
525 return Map.intersect_range(RangeSet);
526 }
527
528 isl::map polly::subtractParams(isl::map Map, isl::set Params) {
529 auto MapSpace = Map.get_space();
530 auto ParamsMap = isl::map::universe(MapSpace).intersect_params(Params);
531 return Map.subtract(ParamsMap);
532 }
533
534 isl::set polly::subtractParams(isl::set Set, isl::set Params) {
535 isl::space SetSpace = Set.get_space();
536 isl::set ParamsSet = isl::set::universe(SetSpace).intersect_params(Params);
537 return Set.subtract(ParamsSet);
538 }
539
540 isl::val polly::getConstant(isl::pw_aff PwAff, bool Max, bool Min) {
541 assert(!Max || !Min); // Cannot return min and max at the same time.
542 isl::val Result;
543 isl::stat Stat = PwAff.foreach_piece(
544 [=, &Result](isl::set Set, isl::aff Aff) -> isl::stat {
545 if (!Result.is_null() && Result.is_nan())
546 return isl::stat::ok();
547
548 // TODO: If Min/Max, we can also determine a minimum/maximum value if
549 // Set is constant-bounded.
550 if (!Aff.is_cst()) {
551 Result = isl::val::nan(Aff.ctx());
552 return isl::stat::error();
553 }
554
555 isl::val ThisVal = Aff.get_constant_val();
556 if (Result.is_null()) {
557 Result = ThisVal;
558 return isl::stat::ok();
559 }
560
561 if (Result.eq(ThisVal))
562 return isl::stat::ok();
563
564 if (Max && ThisVal.gt(Result)) {
565 Result = ThisVal;
566 return isl::stat::ok();
567 }
568
569 if (Min && ThisVal.lt(Result)) {
570 Result = ThisVal;
571 return isl::stat::ok();
572 }
573
574 // Not compatible
575 Result = isl::val::nan(Aff.ctx());
576 return isl::stat::error();
577 });
578
579 if (Stat.is_error())
580 return {};
581
582 return Result;
583 }
584
585 #if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
586 static void foreachPoint(const isl::set &Set,
587 const std::function<void(isl::point P)> &F) {
588 Set.foreach_point([&](isl::point P) -> isl::stat {
589 F(P);
590 return isl::stat::ok();
591 });
592 }
593
594 static void foreachPoint(isl::basic_set BSet,
595 const std::function<void(isl::point P)> &F) {
596 foreachPoint(isl::set(BSet), F);
597 }
598
599 /// Determine the sorting order of the sets @p A and @p B without considering
600 /// the space structure.
601 ///
602 /// Ordering is based on the lower bounds of the set's dimensions. First
603 /// dimensions are considered first.
604 static int flatCompare(const isl::basic_set &A, const isl::basic_set &B) {
605 // Quick bail-out on out-of-quota.
606 if (A.is_null() || B.is_null())
607 return 0;
608
609 unsigned ALen = A.dim(isl::dim::set);
610 unsigned BLen = B.dim(isl::dim::set);
611 unsigned Len = std::min(ALen, BLen);
612
613 for (unsigned i = 0; i < Len; i += 1) {
614 isl::basic_set ADim =
615 A.project_out(isl::dim::param, 0, A.dim(isl::dim::param))
616 .project_out(isl::dim::set, i + 1, ALen - i - 1)
617 .project_out(isl::dim::set, 0, i);
618 isl::basic_set BDim =
619 B.project_out(isl::dim::param, 0, B.dim(isl::dim::param))
620 .project_out(isl::dim::set, i + 1, BLen - i - 1)
621 .project_out(isl::dim::set, 0, i);
622
623 isl::basic_set AHull = isl::set(ADim).convex_hull();
624 isl::basic_set BHull = isl::set(BDim).convex_hull();
625
626 bool ALowerBounded =
627 bool(isl::set(AHull).dim_has_any_lower_bound(isl::dim::set, 0));
628 bool BLowerBounded =
629 bool(isl::set(BHull).dim_has_any_lower_bound(isl::dim::set, 0));
630
631 int BoundedCompare = BLowerBounded - ALowerBounded;
632 if (BoundedCompare != 0)
633 return BoundedCompare;
634
635 if (!ALowerBounded || !BLowerBounded)
636 continue;
637
638 isl::pw_aff AMin = isl::set(ADim).dim_min(0);
639 isl::pw_aff BMin = isl::set(BDim).dim_min(0);
640
641 isl::val AMinVal = polly::getConstant(AMin, false, true);
642 isl::val BMinVal = polly::getConstant(BMin, false, true);
643
644 int MinCompare = AMinVal.sub(BMinVal).sgn();
645 if (MinCompare != 0)
646 return MinCompare;
647 }
648
649 // If all the dimensions' lower bounds are equal or incomparable, sort based
650 // on the number of dimensions.
651 return ALen - BLen;
652 }
653
654 /// Compare the sets @p A and @p B according to their nested space structure.
655 /// Returns 0 if the structure is considered equal.
656 /// If @p ConsiderTupleLen is false, the number of dimensions in a tuple are
657 /// ignored, i.e. a tuple with the same name but different number of dimensions
658 /// are considered equal.
659 static int structureCompare(const isl::space &ASpace, const isl::space &BSpace,
660 bool ConsiderTupleLen) {
661 int WrappingCompare = bool(ASpace.is_wrapping()) - bool(BSpace.is_wrapping());
662 if (WrappingCompare != 0)
663 return WrappingCompare;
664
665 if (ASpace.is_wrapping() && BSpace.is_wrapping()) {
666 isl::space AMap = ASpace.unwrap();
667 isl::space BMap = BSpace.unwrap();
668
669 int FirstResult =
670 structureCompare(AMap.domain(), BMap.domain(), ConsiderTupleLen);
671 if (FirstResult != 0)
672 return FirstResult;
673
674 return structureCompare(AMap.range(), BMap.range(), ConsiderTupleLen);
675 }
676
677 std::string AName;
678 if (!ASpace.is_params() && ASpace.has_tuple_name(isl::dim::set))
679 AName = ASpace.get_tuple_name(isl::dim::set);
680
681 std::string BName;
682 if (!BSpace.is_params() && BSpace.has_tuple_name(isl::dim::set))
683 BName = BSpace.get_tuple_name(isl::dim::set);
684
685 int NameCompare = AName.compare(BName);
686 if (NameCompare != 0)
687 return NameCompare;
688
689 if (ConsiderTupleLen) {
690 int LenCompare = BSpace.dim(isl::dim::set) - ASpace.dim(isl::dim::set);
691 if (LenCompare != 0)
692 return LenCompare;
693 }
694
695 return 0;
696 }
697
698 /// Compare the sets @p A and @p B according to their nested space structure. If
699 /// the structure is the same, sort using the dimension lower bounds.
700 /// Returns an std::sort compatible bool.
701 static bool orderComparer(const isl::basic_set &A, const isl::basic_set &B) {
702 isl::space ASpace = A.get_space();
703 isl::space BSpace = B.get_space();
704
705 // Ignoring number of dimensions first ensures that structures with same tuple
706 // names, but different number of dimensions are still sorted close together.
707 int TupleNestingCompare = structureCompare(ASpace, BSpace, false);
708 if (TupleNestingCompare != 0)
709 return TupleNestingCompare < 0;
710
711 int TupleCompare = structureCompare(ASpace, BSpace, true);
712 if (TupleCompare != 0)
713 return TupleCompare < 0;
714
715 return flatCompare(A, B) < 0;
716 }
717
718 /// Print a string representation of @p USet to @p OS.
719 ///
720 /// The pieces of @p USet are printed in a sorted order. Spaces with equal or
721 /// similar nesting structure are printed together. Compared to isl's own
722 /// printing function the uses the structure itself as base of the sorting, not
723 /// a hash of it. It ensures that e.g. maps spaces with same domain structure
724 /// are printed together. Set pieces with same structure are printed in order of
725 /// their lower bounds.
726 ///
727 /// @param USet Polyhedra to print.
728 /// @param OS Target stream.
729 /// @param Simplify Whether to simplify the polyhedron before printing.
730 /// @param IsMap Whether @p USet is a wrapped map. If true, sets are
731 /// unwrapped before printing to again appear as a map.
732 static void printSortedPolyhedra(isl::union_set USet, llvm::raw_ostream &OS,
733 bool Simplify, bool IsMap) {
734 if (USet.is_null()) {
735 OS << "<null>\n";
736 return;
737 }
738
739 if (Simplify)
740 simplify(USet);
741
742 // Get all the polyhedra.
743 std::vector<isl::basic_set> BSets;
744
745 for (isl::set Set : USet.get_set_list()) {
746 for (isl::basic_set BSet : Set.get_basic_set_list()) {
747 BSets.push_back(BSet);
748 }
749 }
750
751 if (BSets.empty()) {
752 OS << "{\n}\n";
753 return;
754 }
755
756 // Sort the polyhedra.
757 llvm::sort(BSets, orderComparer);
758
759 // Print the polyhedra.
760 bool First = true;
761 for (const isl::basic_set &BSet : BSets) {
762 std::string Str;
763 if (IsMap)
764 Str = stringFromIslObj(isl::map(BSet.unwrap()));
765 else
766 Str = stringFromIslObj(isl::set(BSet));
767 size_t OpenPos = Str.find_first_of('{');
768 assert(OpenPos != std::string::npos);
769 size_t ClosePos = Str.find_last_of('}');
770 assert(ClosePos != std::string::npos);
771
772 if (First)
773 OS << llvm::StringRef(Str).substr(0, OpenPos + 1) << "\n ";
774 else
775 OS << ";\n ";
776
777 OS << llvm::StringRef(Str).substr(OpenPos + 1, ClosePos - OpenPos - 2);
778 First = false;
779 }
780 assert(!First);
781 OS << "\n}\n";
782 }
783
784 static void recursiveExpand(isl::basic_set BSet, int Dim, isl::set &Expanded) {
785 int Dims = BSet.dim(isl::dim::set);
786 if (Dim >= Dims) {
787 Expanded = Expanded.unite(BSet);
788 return;
789 }
790
791 isl::basic_set DimOnly =
792 BSet.project_out(isl::dim::param, 0, BSet.dim(isl::dim::param))
793 .project_out(isl::dim::set, Dim + 1, Dims - Dim - 1)
794 .project_out(isl::dim::set, 0, Dim);
795 if (!DimOnly.is_bounded()) {
796 recursiveExpand(BSet, Dim + 1, Expanded);
797 return;
798 }
799
800 foreachPoint(DimOnly, [&, Dim](isl::point P) {
801 isl::val Val = P.get_coordinate_val(isl::dim::set, 0);
802 isl::basic_set FixBSet = BSet.fix_val(isl::dim::set, Dim, Val);
803 recursiveExpand(FixBSet, Dim + 1, Expanded);
804 });
805 }
806
807 /// Make each point of a set explicit.
808 ///
809 /// "Expanding" makes each point a set contains explicit. That is, the result is
810 /// a set of singleton polyhedra. Unbounded dimensions are not expanded.
811 ///
812 /// Example:
813 /// { [i] : 0 <= i < 2 }
814 /// is expanded to:
815 /// { [0]; [1] }
816 static isl::set expand(const isl::set &Set) {
817 isl::set Expanded = isl::set::empty(Set.get_space());
818 for (isl::basic_set BSet : Set.get_basic_set_list())
819 recursiveExpand(BSet, 0, Expanded);
820 return Expanded;
821 }
822
823 /// Expand all points of a union set explicit.
824 ///
825 /// @see expand(const isl::set)
826 static isl::union_set expand(const isl::union_set &USet) {
827 isl::union_set Expanded = isl::union_set::empty(USet.ctx());
828 for (isl::set Set : USet.get_set_list()) {
829 isl::set SetExpanded = expand(Set);
830 Expanded = Expanded.unite(SetExpanded);
831 }
832 return Expanded;
833 }
834
835 LLVM_DUMP_METHOD void polly::dumpPw(const isl::set &Set) {
836 printSortedPolyhedra(Set, llvm::errs(), true, false);
837 }
838
839 LLVM_DUMP_METHOD void polly::dumpPw(const isl::map &Map) {
840 printSortedPolyhedra(Map.wrap(), llvm::errs(), true, true);
841 }
842
843 LLVM_DUMP_METHOD void polly::dumpPw(const isl::union_set &USet) {
844 printSortedPolyhedra(USet, llvm::errs(), true, false);
845 }
846
847 LLVM_DUMP_METHOD void polly::dumpPw(const isl::union_map &UMap) {
848 printSortedPolyhedra(UMap.wrap(), llvm::errs(), true, true);
849 }
850
851 LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_set *Set) {
852 dumpPw(isl::manage_copy(Set));
853 }
854
855 LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_map *Map) {
856 dumpPw(isl::manage_copy(Map));
857 }
858
859 LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_union_set *USet) {
860 dumpPw(isl::manage_copy(USet));
861 }
862
863 LLVM_DUMP_METHOD void polly::dumpPw(__isl_keep isl_union_map *UMap) {
864 dumpPw(isl::manage_copy(UMap));
865 }
866
867 LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::set &Set) {
868 printSortedPolyhedra(expand(Set), llvm::errs(), false, false);
869 }
870
871 LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::map &Map) {
872 printSortedPolyhedra(expand(Map.wrap()), llvm::errs(), false, true);
873 }
874
875 LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::union_set &USet) {
876 printSortedPolyhedra(expand(USet), llvm::errs(), false, false);
877 }
878
879 LLVM_DUMP_METHOD void polly::dumpExpanded(const isl::union_map &UMap) {
880 printSortedPolyhedra(expand(UMap.wrap()), llvm::errs(), false, true);
881 }
882
883 LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_set *Set) {
884 dumpExpanded(isl::manage_copy(Set));
885 }
886
887 LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_map *Map) {
888 dumpExpanded(isl::manage_copy(Map));
889 }
890
891 LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_union_set *USet) {
892 dumpExpanded(isl::manage_copy(USet));
893 }
894
895 LLVM_DUMP_METHOD void polly::dumpExpanded(__isl_keep isl_union_map *UMap) {
896 dumpExpanded(isl::manage_copy(UMap));
897 }
898 #endif
899