1 //===------ ISLTools.cpp ----------------------------------------*- C++ -*-===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // Tools, utilities, helpers and extensions useful in conjunction with the
11 // Integer Set Library (isl).
12 //
13 //===----------------------------------------------------------------------===//
14 
15 #include "polly/Support/ISLTools.h"
16 
17 using namespace polly;
18 
19 namespace {
20 /// Create a map that shifts one dimension by an offset.
21 ///
22 /// Example:
23 /// makeShiftDimAff({ [i0, i1] -> [o0, o1] }, 1, -2)
24 ///   = { [i0, i1] -> [i0, i1 - 1] }
25 ///
26 /// @param Space  The map space of the result. Must have equal number of in- and
27 ///               out-dimensions.
28 /// @param Pos    Position to shift.
29 /// @param Amount Value added to the shifted dimension.
30 ///
31 /// @return An isl_multi_aff for the map with this shifted dimension.
32 isl::multi_aff makeShiftDimAff(isl::space Space, int Pos, int Amount) {
33   auto Identity = give(isl_multi_aff_identity(Space.take()));
34   if (Amount == 0)
35     return Identity;
36   auto ShiftAff = give(isl_multi_aff_get_aff(Identity.keep(), Pos));
37   ShiftAff = give(isl_aff_set_constant_si(ShiftAff.take(), Amount));
38   return give(isl_multi_aff_set_aff(Identity.take(), Pos, ShiftAff.take()));
39 }
40 
41 /// Construct a map that swaps two nested tuples.
42 ///
43 /// @param FromSpace1 { Space1[] }
44 /// @param FromSpace2 { Space2[] }
45 ///
46 /// @return { [Space1[] -> Space2[]] -> [Space2[] -> Space1[]] }
47 isl::basic_map makeTupleSwapBasicMap(isl::space FromSpace1,
48                                      isl::space FromSpace2) {
49   assert(isl_space_is_set(FromSpace1.keep()) != isl_bool_false);
50   assert(isl_space_is_set(FromSpace2.keep()) != isl_bool_false);
51 
52   auto Dims1 = isl_space_dim(FromSpace1.keep(), isl_dim_set);
53   auto Dims2 = isl_space_dim(FromSpace2.keep(), isl_dim_set);
54   auto FromSpace = give(isl_space_wrap(isl_space_map_from_domain_and_range(
55       FromSpace1.copy(), FromSpace2.copy())));
56   auto ToSpace = give(isl_space_wrap(isl_space_map_from_domain_and_range(
57       FromSpace2.take(), FromSpace1.take())));
58   auto MapSpace = give(
59       isl_space_map_from_domain_and_range(FromSpace.take(), ToSpace.take()));
60 
61   auto Result = give(isl_basic_map_universe(MapSpace.take()));
62   for (auto i = Dims1 - Dims1; i < Dims1; i += 1) {
63     Result = give(isl_basic_map_equate(Result.take(), isl_dim_in, i,
64                                        isl_dim_out, Dims2 + i));
65   }
66   for (auto i = Dims2 - Dims2; i < Dims2; i += 1) {
67     Result = give(isl_basic_map_equate(Result.take(), isl_dim_in, Dims1 + i,
68                                        isl_dim_out, i));
69   }
70 
71   return Result;
72 }
73 
74 /// Like makeTupleSwapBasicMap(isl::space,isl::space), but returns
75 /// an isl_map.
76 isl::map makeTupleSwapMap(isl::space FromSpace1, isl::space FromSpace2) {
77   auto BMapResult =
78       makeTupleSwapBasicMap(std::move(FromSpace1), std::move(FromSpace2));
79   return give(isl_map_from_basic_map(BMapResult.take()));
80 }
81 } // anonymous namespace
82 
83 isl::map polly::beforeScatter(isl::map Map, bool Strict) {
84   auto RangeSpace = give(isl_space_range(isl_map_get_space(Map.keep())));
85   auto ScatterRel = give(Strict ? isl_map_lex_gt(RangeSpace.take())
86                                 : isl_map_lex_ge(RangeSpace.take()));
87   return give(isl_map_apply_range(Map.take(), ScatterRel.take()));
88 }
89 
90 isl::union_map polly::beforeScatter(isl::union_map UMap, bool Strict) {
91   auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
92   UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
93     auto After = beforeScatter(Map, Strict);
94     Result = give(isl_union_map_add_map(Result.take(), After.take()));
95     return isl::stat::ok;
96   });
97   return Result;
98 }
99 
100 isl::map polly::afterScatter(isl::map Map, bool Strict) {
101   auto RangeSpace = give(isl_space_range(isl_map_get_space(Map.keep())));
102   auto ScatterRel = give(Strict ? isl_map_lex_lt(RangeSpace.take())
103                                 : isl_map_lex_le(RangeSpace.take()));
104   return give(isl_map_apply_range(Map.take(), ScatterRel.take()));
105 }
106 
107 isl::union_map polly::afterScatter(const isl::union_map &UMap, bool Strict) {
108   auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
109   UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
110     auto After = afterScatter(Map, Strict);
111     Result = give(isl_union_map_add_map(Result.take(), After.take()));
112     return isl::stat::ok;
113   });
114   return Result;
115 }
116 
117 isl::map polly::betweenScatter(isl::map From, isl::map To, bool InclFrom,
118                                bool InclTo) {
119   auto AfterFrom = afterScatter(From, !InclFrom);
120   auto BeforeTo = beforeScatter(To, !InclTo);
121 
122   return give(isl_map_intersect(AfterFrom.take(), BeforeTo.take()));
123 }
124 
125 isl::union_map polly::betweenScatter(isl::union_map From, isl::union_map To,
126                                      bool InclFrom, bool InclTo) {
127   auto AfterFrom = afterScatter(From, !InclFrom);
128   auto BeforeTo = beforeScatter(To, !InclTo);
129 
130   return give(isl_union_map_intersect(AfterFrom.take(), BeforeTo.take()));
131 }
132 
133 isl::map polly::singleton(isl::union_map UMap, isl::space ExpectedSpace) {
134   if (!UMap)
135     return nullptr;
136 
137   if (isl_union_map_n_map(UMap.keep()) == 0)
138     return isl::map::empty(ExpectedSpace);
139 
140   isl::map Result = isl::map::from_union_map(UMap);
141   assert(!Result || Result.get_space().has_equal_tuples(ExpectedSpace));
142 
143   return Result;
144 }
145 
146 isl::set polly::singleton(isl::union_set USet, isl::space ExpectedSpace) {
147   if (!USet)
148     return nullptr;
149 
150   if (isl_union_set_n_set(USet.keep()) == 0)
151     return isl::set::empty(ExpectedSpace);
152 
153   isl::set Result(USet);
154   assert(!Result || Result.get_space().has_equal_tuples(ExpectedSpace));
155 
156   return Result;
157 }
158 
159 unsigned polly::getNumScatterDims(const isl::union_map &Schedule) {
160   unsigned Dims = 0;
161   Schedule.foreach_map([&Dims](isl::map Map) -> isl::stat {
162     Dims = std::max(Dims, isl_map_dim(Map.keep(), isl_dim_out));
163     return isl::stat::ok;
164   });
165   return Dims;
166 }
167 
168 isl::space polly::getScatterSpace(const isl::union_map &Schedule) {
169   if (!Schedule)
170     return nullptr;
171   auto Dims = getNumScatterDims(Schedule);
172   auto ScatterSpace =
173       give(isl_space_set_from_params(isl_union_map_get_space(Schedule.keep())));
174   return give(isl_space_add_dims(ScatterSpace.take(), isl_dim_set, Dims));
175 }
176 
177 isl::union_map polly::makeIdentityMap(const isl::union_set &USet,
178                                       bool RestrictDomain) {
179   auto Result = give(isl_union_map_empty(isl_union_set_get_space(USet.keep())));
180   USet.foreach_set([=, &Result](isl::set Set) -> isl::stat {
181     auto IdentityMap = give(isl_map_identity(
182         isl_space_map_from_set(isl_set_get_space(Set.keep()))));
183     if (RestrictDomain)
184       IdentityMap =
185           give(isl_map_intersect_domain(IdentityMap.take(), Set.take()));
186     Result = give(isl_union_map_add_map(Result.take(), IdentityMap.take()));
187     return isl::stat::ok;
188   });
189   return Result;
190 }
191 
192 isl::map polly::reverseDomain(isl::map Map) {
193   auto DomSpace =
194       give(isl_space_unwrap(isl_space_domain(isl_map_get_space(Map.keep()))));
195   auto Space1 = give(isl_space_domain(DomSpace.copy()));
196   auto Space2 = give(isl_space_range(DomSpace.take()));
197   auto Swap = makeTupleSwapMap(std::move(Space1), std::move(Space2));
198   return give(isl_map_apply_domain(Map.take(), Swap.take()));
199 }
200 
201 isl::union_map polly::reverseDomain(const isl::union_map &UMap) {
202   auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
203   UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
204     auto Reversed = reverseDomain(std::move(Map));
205     Result = give(isl_union_map_add_map(Result.take(), Reversed.take()));
206     return isl::stat::ok;
207   });
208   return Result;
209 }
210 
211 isl::set polly::shiftDim(isl::set Set, int Pos, int Amount) {
212   int NumDims = isl_set_dim(Set.keep(), isl_dim_set);
213   if (Pos < 0)
214     Pos = NumDims + Pos;
215   assert(Pos < NumDims && "Dimension index must be in range");
216   auto Space = give(isl_set_get_space(Set.keep()));
217   Space = give(isl_space_map_from_domain_and_range(Space.copy(), Space.copy()));
218   auto Translator = makeShiftDimAff(std::move(Space), Pos, Amount);
219   auto TranslatorMap = give(isl_map_from_multi_aff(Translator.take()));
220   return give(isl_set_apply(Set.take(), TranslatorMap.take()));
221 }
222 
223 isl::union_set polly::shiftDim(isl::union_set USet, int Pos, int Amount) {
224   auto Result = give(isl_union_set_empty(isl_union_set_get_space(USet.keep())));
225   USet.foreach_set([=, &Result](isl::set Set) -> isl::stat {
226     auto Shifted = shiftDim(Set, Pos, Amount);
227     Result = give(isl_union_set_add_set(Result.take(), Shifted.take()));
228     return isl::stat::ok;
229   });
230   return Result;
231 }
232 
233 isl::map polly::shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount) {
234   int NumDims = Map.dim(Dim);
235   if (Pos < 0)
236     Pos = NumDims + Pos;
237   assert(Pos < NumDims && "Dimension index must be in range");
238   auto Space = give(isl_map_get_space(Map.keep()));
239   switch (Dim) {
240   case isl::dim::in:
241     Space = std::move(Space).domain();
242     break;
243   case isl::dim::out:
244     Space = give(isl_space_range(Space.take()));
245     break;
246   default:
247     llvm_unreachable("Unsupported value for 'dim'");
248   }
249   Space = give(isl_space_map_from_domain_and_range(Space.copy(), Space.copy()));
250   auto Translator = makeShiftDimAff(std::move(Space), Pos, Amount);
251   auto TranslatorMap = give(isl_map_from_multi_aff(Translator.take()));
252   switch (Dim) {
253   case isl::dim::in:
254     return Map.apply_domain(TranslatorMap);
255   case isl::dim::out:
256     return Map.apply_range(TranslatorMap);
257   default:
258     llvm_unreachable("Unsupported value for 'dim'");
259   }
260 }
261 
262 isl::union_map polly::shiftDim(isl::union_map UMap, isl::dim Dim, int Pos,
263                                int Amount) {
264   auto Result = isl::union_map::empty(UMap.get_space());
265 
266   UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
267     auto Shifted = shiftDim(Map, Dim, Pos, Amount);
268     Result = std::move(Result).add_map(Shifted);
269     return isl::stat::ok;
270   });
271   return Result;
272 }
273 
274 void polly::simplify(isl::set &Set) {
275   Set = give(isl_set_compute_divs(Set.take()));
276   Set = give(isl_set_detect_equalities(Set.take()));
277   Set = give(isl_set_coalesce(Set.take()));
278 }
279 
280 void polly::simplify(isl::union_set &USet) {
281   USet = give(isl_union_set_compute_divs(USet.take()));
282   USet = give(isl_union_set_detect_equalities(USet.take()));
283   USet = give(isl_union_set_coalesce(USet.take()));
284 }
285 
286 void polly::simplify(isl::map &Map) {
287   Map = give(isl_map_compute_divs(Map.take()));
288   Map = give(isl_map_detect_equalities(Map.take()));
289   Map = give(isl_map_coalesce(Map.take()));
290 }
291 
292 void polly::simplify(isl::union_map &UMap) {
293   UMap = give(isl_union_map_compute_divs(UMap.take()));
294   UMap = give(isl_union_map_detect_equalities(UMap.take()));
295   UMap = give(isl_union_map_coalesce(UMap.take()));
296 }
297 
298 isl::union_map polly::computeReachingWrite(isl::union_map Schedule,
299                                            isl::union_map Writes, bool Reverse,
300                                            bool InclPrevDef, bool InclNextDef) {
301 
302   // { Scatter[] }
303   auto ScatterSpace = getScatterSpace(Schedule);
304 
305   // { ScatterRead[] -> ScatterWrite[] }
306   isl::map Relation;
307   if (Reverse)
308     Relation = give(InclPrevDef ? isl_map_lex_lt(ScatterSpace.take())
309                                 : isl_map_lex_le(ScatterSpace.take()));
310   else
311     Relation = give(InclNextDef ? isl_map_lex_gt(ScatterSpace.take())
312                                 : isl_map_lex_ge(ScatterSpace.take()));
313 
314   // { ScatterWrite[] -> [ScatterRead[] -> ScatterWrite[]] }
315   auto RelationMap = give(isl_map_reverse(isl_map_range_map(Relation.take())));
316 
317   // { Element[] -> ScatterWrite[] }
318   auto WriteAction =
319       give(isl_union_map_apply_domain(Schedule.copy(), Writes.take()));
320 
321   // { ScatterWrite[] -> Element[] }
322   auto WriteActionRev = give(isl_union_map_reverse(WriteAction.copy()));
323 
324   // { Element[] -> [ScatterUse[] -> ScatterWrite[]] }
325   auto DefSchedRelation = give(isl_union_map_apply_domain(
326       isl_union_map_from_map(RelationMap.take()), WriteActionRev.take()));
327 
328   // For each element, at every point in time, map to the times of previous
329   // definitions. { [Element[] -> ScatterRead[]] -> ScatterWrite[] }
330   auto ReachableWrites = give(isl_union_map_uncurry(DefSchedRelation.take()));
331   if (Reverse)
332     ReachableWrites = give(isl_union_map_lexmin(ReachableWrites.copy()));
333   else
334     ReachableWrites = give(isl_union_map_lexmax(ReachableWrites.copy()));
335 
336   // { [Element[] -> ScatterWrite[]] -> ScatterWrite[] }
337   auto SelfUse = give(isl_union_map_range_map(WriteAction.take()));
338 
339   if (InclPrevDef && InclNextDef) {
340     // Add the Def itself to the solution.
341     ReachableWrites =
342         give(isl_union_map_union(ReachableWrites.take(), SelfUse.take()));
343     ReachableWrites = give(isl_union_map_coalesce(ReachableWrites.take()));
344   } else if (!InclPrevDef && !InclNextDef) {
345     // Remove Def itself from the solution.
346     ReachableWrites =
347         give(isl_union_map_subtract(ReachableWrites.take(), SelfUse.take()));
348   }
349 
350   // { [Element[] -> ScatterRead[]] -> Domain[] }
351   auto ReachableWriteDomain = give(isl_union_map_apply_range(
352       ReachableWrites.take(), isl_union_map_reverse(Schedule.take())));
353 
354   return ReachableWriteDomain;
355 }
356 
357 isl::union_map
358 polly::computeArrayUnused(isl::union_map Schedule, isl::union_map Writes,
359                           isl::union_map Reads, bool ReadEltInSameInst,
360                           bool IncludeLastRead, bool IncludeWrite) {
361   // { Element[] -> Scatter[] }
362   auto ReadActions =
363       give(isl_union_map_apply_domain(Schedule.copy(), Reads.take()));
364   auto WriteActions =
365       give(isl_union_map_apply_domain(Schedule.copy(), Writes.copy()));
366 
367   // { [Element[] -> DomainWrite[]] -> Scatter[] }
368   auto EltDomWrites = give(isl_union_map_apply_range(
369       isl_union_map_range_map(isl_union_map_reverse(Writes.copy())),
370       Schedule.copy()));
371 
372   // { [Element[] -> Scatter[]] -> DomainWrite[] }
373   auto ReachingOverwrite = computeReachingWrite(
374       Schedule, Writes, true, ReadEltInSameInst, !ReadEltInSameInst);
375 
376   // { [Element[] -> Scatter[]] -> DomainWrite[] }
377   auto ReadsOverwritten = give(isl_union_map_intersect_domain(
378       ReachingOverwrite.take(), isl_union_map_wrap(ReadActions.take())));
379 
380   // { [Element[] -> DomainWrite[]] -> Scatter[] }
381   auto ReadsOverwrittenRotated = give(isl_union_map_reverse(
382       isl_union_map_curry(reverseDomain(ReadsOverwritten).take())));
383   auto LastOverwrittenRead =
384       give(isl_union_map_lexmax(ReadsOverwrittenRotated.copy()));
385 
386   // { [Element[] -> DomainWrite[]] -> Scatter[] }
387   auto BetweenLastReadOverwrite = betweenScatter(
388       LastOverwrittenRead, EltDomWrites, IncludeLastRead, IncludeWrite);
389 
390   // { [Element[] -> Scatter[]] -> DomainWrite[] }
391   isl::union_map ReachingOverwriteZone = computeReachingWrite(
392       Schedule, Writes, true, IncludeLastRead, IncludeWrite);
393 
394   // { [Element[] -> DomainWrite[]] -> Scatter[] }
395   isl::union_map ReachingOverwriteRotated =
396       reverseDomain(ReachingOverwriteZone).curry().reverse();
397 
398   // { [Element[] -> DomainWrite[]] -> Scatter[] }
399   isl::union_map WritesWithoutReads = ReachingOverwriteRotated.subtract_domain(
400       ReadsOverwrittenRotated.domain());
401 
402   return BetweenLastReadOverwrite.unite(WritesWithoutReads)
403       .domain_factor_domain();
404 }
405 
406 isl::union_set polly::convertZoneToTimepoints(isl::union_set Zone,
407                                               bool InclStart, bool InclEnd) {
408   if (!InclStart && InclEnd)
409     return Zone;
410 
411   auto ShiftedZone = shiftDim(Zone, -1, -1);
412   if (InclStart && !InclEnd)
413     return ShiftedZone;
414   else if (!InclStart && !InclEnd)
415     return give(isl_union_set_intersect(Zone.take(), ShiftedZone.take()));
416 
417   assert(InclStart && InclEnd);
418   return give(isl_union_set_union(Zone.take(), ShiftedZone.take()));
419 }
420 
421 isl::union_map polly::convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,
422                                               bool InclStart, bool InclEnd) {
423   if (!InclStart && InclEnd)
424     return Zone;
425 
426   auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
427   if (InclStart && !InclEnd)
428     return ShiftedZone;
429   else if (!InclStart && !InclEnd)
430     return give(isl_union_map_intersect(Zone.take(), ShiftedZone.take()));
431 
432   assert(InclStart && InclEnd);
433   return give(isl_union_map_union(Zone.take(), ShiftedZone.take()));
434 }
435 
436 isl::map polly::convertZoneToTimepoints(isl::map Zone, isl::dim Dim,
437                                         bool InclStart, bool InclEnd) {
438   if (!InclStart && InclEnd)
439     return Zone;
440 
441   auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
442   if (InclStart && !InclEnd)
443     return ShiftedZone;
444   else if (!InclStart && !InclEnd)
445     return give(isl_map_intersect(Zone.take(), ShiftedZone.take()));
446 
447   assert(InclStart && InclEnd);
448   return give(isl_map_union(Zone.take(), ShiftedZone.take()));
449 }
450 
451 isl::map polly::distributeDomain(isl::map Map) {
452   // Note that we cannot take Map apart into { Domain[] -> Range1[] } and {
453   // Domain[] -> Range2[] } and combine again. We would loose any relation
454   // between Range1[] and Range2[] that is not also a constraint to Domain[].
455 
456   auto Space = give(isl_map_get_space(Map.keep()));
457   auto DomainSpace = give(isl_space_domain(Space.copy()));
458   auto DomainDims = isl_space_dim(DomainSpace.keep(), isl_dim_set);
459   auto RangeSpace = give(isl_space_unwrap(isl_space_range(Space.copy())));
460   auto Range1Space = give(isl_space_domain(RangeSpace.copy()));
461   auto Range1Dims = isl_space_dim(Range1Space.keep(), isl_dim_set);
462   auto Range2Space = give(isl_space_range(RangeSpace.copy()));
463   auto Range2Dims = isl_space_dim(Range2Space.keep(), isl_dim_set);
464 
465   auto OutputSpace = give(isl_space_map_from_domain_and_range(
466       isl_space_wrap(isl_space_map_from_domain_and_range(DomainSpace.copy(),
467                                                          Range1Space.copy())),
468       isl_space_wrap(isl_space_map_from_domain_and_range(DomainSpace.copy(),
469                                                          Range2Space.copy()))));
470 
471   auto Translator =
472       give(isl_basic_map_universe(isl_space_map_from_domain_and_range(
473           isl_space_wrap(Space.copy()), isl_space_wrap(OutputSpace.copy()))));
474 
475   for (unsigned i = 0; i < DomainDims; i += 1) {
476     Translator = give(
477         isl_basic_map_equate(Translator.take(), isl_dim_in, i, isl_dim_out, i));
478     Translator =
479         give(isl_basic_map_equate(Translator.take(), isl_dim_in, i, isl_dim_out,
480                                   DomainDims + Range1Dims + i));
481   }
482   for (unsigned i = 0; i < Range1Dims; i += 1) {
483     Translator =
484         give(isl_basic_map_equate(Translator.take(), isl_dim_in, DomainDims + i,
485                                   isl_dim_out, DomainDims + i));
486   }
487   for (unsigned i = 0; i < Range2Dims; i += 1) {
488     Translator = give(isl_basic_map_equate(
489         Translator.take(), isl_dim_in, DomainDims + Range1Dims + i, isl_dim_out,
490         DomainDims + Range1Dims + DomainDims + i));
491   }
492 
493   return give(isl_set_unwrap(isl_set_apply(
494       isl_map_wrap(Map.copy()), isl_map_from_basic_map(Translator.copy()))));
495 }
496 
497 isl::union_map polly::distributeDomain(isl::union_map UMap) {
498   auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
499   isl::stat Success = UMap.foreach_map([=, &Result](isl::map Map) {
500     auto Distributed = distributeDomain(Map);
501     Result = give(isl_union_map_add_map(Result.take(), Distributed.copy()));
502     return isl::stat::ok;
503   });
504   if (Success != isl::stat::ok)
505     return {};
506   return Result;
507 }
508 
509 isl::union_map polly::liftDomains(isl::union_map UMap, isl::union_set Factor) {
510 
511   // { Factor[] -> Factor[] }
512   auto Factors = makeIdentityMap(std::move(Factor), true);
513 
514   return std::move(Factors).product(std::move(UMap));
515 }
516 
517 isl::union_map polly::applyDomainRange(isl::union_map UMap,
518                                        isl::union_map Func) {
519   // This implementation creates unnecessary cross products of the
520   // DomainDomain[] and Func. An alternative implementation could reverse
521   // domain+uncurry,apply Func to what now is the domain, then undo the
522   // preparing transformation. Another alternative implementation could create a
523   // translator map for each piece.
524 
525   // { DomainDomain[] }
526   auto DomainDomain = UMap.domain().unwrap().domain();
527 
528   // { [DomainDomain[] -> DomainRange[]] -> [DomainDomain[] -> NewDomainRange[]]
529   // }
530   auto LifetedFunc = liftDomains(std::move(Func), DomainDomain);
531 
532   return std::move(UMap).apply_domain(std::move(LifetedFunc));
533 }
534 
535 isl::map polly::intersectRange(isl::map Map, isl::union_set Range) {
536   isl::set RangeSet = Range.extract_set(Map.get_space().range());
537   return Map.intersect_range(RangeSet);
538 }
539