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