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 give(isl_map_empty(ExpectedSpace.take()));
139 
140   auto Result = give(isl_map_from_union_map(UMap.take()));
141   assert(!Result || isl_space_has_equal_tuples(
142                         give(isl_map_get_space(Result.keep())).keep(),
143                         ExpectedSpace.keep()) == isl_bool_true);
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.keep()) == 0)
152     return give(isl_set_empty(ExpectedSpace.copy()));
153 
154   auto Result = give(isl_set_from_union_set(USet.take()));
155   assert(!Result || isl_space_has_equal_tuples(
156                         give(isl_set_get_space(Result.keep())).keep(),
157                         ExpectedSpace.keep()) == isl_bool_true);
158   return Result;
159 }
160 
161 unsigned polly::getNumScatterDims(const isl::union_map &Schedule) {
162   unsigned Dims = 0;
163   Schedule.foreach_map([&Dims](isl::map Map) -> isl::stat {
164     Dims = std::max(Dims, isl_map_dim(Map.keep(), isl_dim_out));
165     return isl::stat::ok;
166   });
167   return Dims;
168 }
169 
170 isl::space polly::getScatterSpace(const isl::union_map &Schedule) {
171   if (!Schedule)
172     return nullptr;
173   auto Dims = getNumScatterDims(Schedule);
174   auto ScatterSpace =
175       give(isl_space_set_from_params(isl_union_map_get_space(Schedule.keep())));
176   return give(isl_space_add_dims(ScatterSpace.take(), isl_dim_set, Dims));
177 }
178 
179 isl::union_map polly::makeIdentityMap(const isl::union_set &USet,
180                                       bool RestrictDomain) {
181   auto Result = give(isl_union_map_empty(isl_union_set_get_space(USet.keep())));
182   USet.foreach_set([=, &Result](isl::set Set) -> isl::stat {
183     auto IdentityMap = give(isl_map_identity(
184         isl_space_map_from_set(isl_set_get_space(Set.keep()))));
185     if (RestrictDomain)
186       IdentityMap =
187           give(isl_map_intersect_domain(IdentityMap.take(), Set.take()));
188     Result = give(isl_union_map_add_map(Result.take(), IdentityMap.take()));
189     return isl::stat::ok;
190   });
191   return Result;
192 }
193 
194 isl::map polly::reverseDomain(isl::map Map) {
195   auto DomSpace =
196       give(isl_space_unwrap(isl_space_domain(isl_map_get_space(Map.keep()))));
197   auto Space1 = give(isl_space_domain(DomSpace.copy()));
198   auto Space2 = give(isl_space_range(DomSpace.take()));
199   auto Swap = makeTupleSwapMap(std::move(Space1), std::move(Space2));
200   return give(isl_map_apply_domain(Map.take(), Swap.take()));
201 }
202 
203 isl::union_map polly::reverseDomain(const isl::union_map &UMap) {
204   auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
205   UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
206     auto Reversed = reverseDomain(std::move(Map));
207     Result = give(isl_union_map_add_map(Result.take(), Reversed.take()));
208     return isl::stat::ok;
209   });
210   return Result;
211 }
212 
213 isl::set polly::shiftDim(isl::set Set, int Pos, int Amount) {
214   int NumDims = isl_set_dim(Set.keep(), isl_dim_set);
215   if (Pos < 0)
216     Pos = NumDims + Pos;
217   assert(Pos < NumDims && "Dimension index must be in range");
218   auto Space = give(isl_set_get_space(Set.keep()));
219   Space = give(isl_space_map_from_domain_and_range(Space.copy(), Space.copy()));
220   auto Translator = makeShiftDimAff(std::move(Space), Pos, Amount);
221   auto TranslatorMap = give(isl_map_from_multi_aff(Translator.take()));
222   return give(isl_set_apply(Set.take(), TranslatorMap.take()));
223 }
224 
225 isl::union_set polly::shiftDim(isl::union_set USet, int Pos, int Amount) {
226   auto Result = give(isl_union_set_empty(isl_union_set_get_space(USet.keep())));
227   USet.foreach_set([=, &Result](isl::set Set) -> isl::stat {
228     auto Shifted = shiftDim(Set, Pos, Amount);
229     Result = give(isl_union_set_add_set(Result.take(), Shifted.take()));
230     return isl::stat::ok;
231   });
232   return Result;
233 }
234 
235 isl::map polly::shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount) {
236   int NumDims = Map.dim(Dim);
237   if (Pos < 0)
238     Pos = NumDims + Pos;
239   assert(Pos < NumDims && "Dimension index must be in range");
240   auto Space = give(isl_map_get_space(Map.keep()));
241   switch (Dim) {
242   case isl::dim::in:
243     Space = std::move(Space).domain();
244     break;
245   case isl::dim::out:
246     Space = give(isl_space_range(Space.take()));
247     break;
248   default:
249     llvm_unreachable("Unsupported value for 'dim'");
250   }
251   Space = give(isl_space_map_from_domain_and_range(Space.copy(), Space.copy()));
252   auto Translator = makeShiftDimAff(std::move(Space), Pos, Amount);
253   auto TranslatorMap = give(isl_map_from_multi_aff(Translator.take()));
254   switch (Dim) {
255   case isl::dim::in:
256     return Map.apply_domain(TranslatorMap);
257   case isl::dim::out:
258     return Map.apply_range(TranslatorMap);
259   default:
260     llvm_unreachable("Unsupported value for 'dim'");
261   }
262 }
263 
264 isl::union_map polly::shiftDim(isl::union_map UMap, isl::dim Dim, int Pos,
265                                int Amount) {
266   auto Result = isl::union_map::empty(UMap.get_space());
267 
268   UMap.foreach_map([=, &Result](isl::map Map) -> isl::stat {
269     auto Shifted = shiftDim(Map, Dim, Pos, Amount);
270     Result = std::move(Result).add_map(Shifted);
271     return isl::stat::ok;
272   });
273   return Result;
274 }
275 
276 void polly::simplify(isl::set &Set) {
277   Set = give(isl_set_compute_divs(Set.take()));
278   Set = give(isl_set_detect_equalities(Set.take()));
279   Set = give(isl_set_coalesce(Set.take()));
280 }
281 
282 void polly::simplify(isl::union_set &USet) {
283   USet = give(isl_union_set_compute_divs(USet.take()));
284   USet = give(isl_union_set_detect_equalities(USet.take()));
285   USet = give(isl_union_set_coalesce(USet.take()));
286 }
287 
288 void polly::simplify(isl::map &Map) {
289   Map = give(isl_map_compute_divs(Map.take()));
290   Map = give(isl_map_detect_equalities(Map.take()));
291   Map = give(isl_map_coalesce(Map.take()));
292 }
293 
294 void polly::simplify(isl::union_map &UMap) {
295   UMap = give(isl_union_map_compute_divs(UMap.take()));
296   UMap = give(isl_union_map_detect_equalities(UMap.take()));
297   UMap = give(isl_union_map_coalesce(UMap.take()));
298 }
299 
300 isl::union_map polly::computeReachingWrite(isl::union_map Schedule,
301                                            isl::union_map Writes, bool Reverse,
302                                            bool InclPrevDef, bool InclNextDef) {
303 
304   // { Scatter[] }
305   auto ScatterSpace = getScatterSpace(Schedule);
306 
307   // { ScatterRead[] -> ScatterWrite[] }
308   isl::map Relation;
309   if (Reverse)
310     Relation = give(InclPrevDef ? isl_map_lex_lt(ScatterSpace.take())
311                                 : isl_map_lex_le(ScatterSpace.take()));
312   else
313     Relation = give(InclNextDef ? isl_map_lex_gt(ScatterSpace.take())
314                                 : isl_map_lex_ge(ScatterSpace.take()));
315 
316   // { ScatterWrite[] -> [ScatterRead[] -> ScatterWrite[]] }
317   auto RelationMap = give(isl_map_reverse(isl_map_range_map(Relation.take())));
318 
319   // { Element[] -> ScatterWrite[] }
320   auto WriteAction =
321       give(isl_union_map_apply_domain(Schedule.copy(), Writes.take()));
322 
323   // { ScatterWrite[] -> Element[] }
324   auto WriteActionRev = give(isl_union_map_reverse(WriteAction.copy()));
325 
326   // { Element[] -> [ScatterUse[] -> ScatterWrite[]] }
327   auto DefSchedRelation = give(isl_union_map_apply_domain(
328       isl_union_map_from_map(RelationMap.take()), WriteActionRev.take()));
329 
330   // For each element, at every point in time, map to the times of previous
331   // definitions. { [Element[] -> ScatterRead[]] -> ScatterWrite[] }
332   auto ReachableWrites = give(isl_union_map_uncurry(DefSchedRelation.take()));
333   if (Reverse)
334     ReachableWrites = give(isl_union_map_lexmin(ReachableWrites.copy()));
335   else
336     ReachableWrites = give(isl_union_map_lexmax(ReachableWrites.copy()));
337 
338   // { [Element[] -> ScatterWrite[]] -> ScatterWrite[] }
339   auto SelfUse = give(isl_union_map_range_map(WriteAction.take()));
340 
341   if (InclPrevDef && InclNextDef) {
342     // Add the Def itself to the solution.
343     ReachableWrites =
344         give(isl_union_map_union(ReachableWrites.take(), SelfUse.take()));
345     ReachableWrites = give(isl_union_map_coalesce(ReachableWrites.take()));
346   } else if (!InclPrevDef && !InclNextDef) {
347     // Remove Def itself from the solution.
348     ReachableWrites =
349         give(isl_union_map_subtract(ReachableWrites.take(), SelfUse.take()));
350   }
351 
352   // { [Element[] -> ScatterRead[]] -> Domain[] }
353   auto ReachableWriteDomain = give(isl_union_map_apply_range(
354       ReachableWrites.take(), isl_union_map_reverse(Schedule.take())));
355 
356   return ReachableWriteDomain;
357 }
358 
359 isl::union_map
360 polly::computeArrayUnused(isl::union_map Schedule, isl::union_map Writes,
361                           isl::union_map Reads, bool ReadEltInSameInst,
362                           bool IncludeLastRead, bool IncludeWrite) {
363   // { Element[] -> Scatter[] }
364   auto ReadActions =
365       give(isl_union_map_apply_domain(Schedule.copy(), Reads.take()));
366   auto WriteActions =
367       give(isl_union_map_apply_domain(Schedule.copy(), Writes.copy()));
368 
369   // { [Element[] -> Scatter[] }
370   auto AfterReads = afterScatter(ReadActions, ReadEltInSameInst);
371   auto WritesBeforeAnyReads =
372       give(isl_union_map_subtract(WriteActions.take(), AfterReads.take()));
373   auto BeforeWritesBeforeAnyReads =
374       beforeScatter(WritesBeforeAnyReads, !IncludeWrite);
375 
376   // { [Element[] -> DomainWrite[]] -> Scatter[] }
377   auto EltDomWrites = give(isl_union_map_apply_range(
378       isl_union_map_range_map(isl_union_map_reverse(Writes.copy())),
379       Schedule.copy()));
380 
381   // { [Element[] -> Scatter[]] -> DomainWrite[] }
382   auto ReachingOverwrite = computeReachingWrite(
383       Schedule, Writes, true, ReadEltInSameInst, !ReadEltInSameInst);
384 
385   // { [Element[] -> Scatter[]] -> DomainWrite[] }
386   auto ReadsOverwritten = give(isl_union_map_intersect_domain(
387       ReachingOverwrite.take(), isl_union_map_wrap(ReadActions.take())));
388 
389   // { [Element[] -> DomainWrite[]] -> Scatter[] }
390   auto ReadsOverwrittenRotated = give(isl_union_map_reverse(
391       isl_union_map_curry(reverseDomain(ReadsOverwritten).take())));
392   auto LastOverwrittenRead =
393       give(isl_union_map_lexmax(ReadsOverwrittenRotated.take()));
394 
395   // { [Element[] -> DomainWrite[]] -> Scatter[] }
396   auto BetweenLastReadOverwrite = betweenScatter(
397       LastOverwrittenRead, EltDomWrites, IncludeLastRead, IncludeWrite);
398 
399   return give(isl_union_map_union(
400       BeforeWritesBeforeAnyReads.take(),
401       isl_union_map_domain_factor_domain(BetweenLastReadOverwrite.take())));
402 }
403 
404 isl::union_set polly::convertZoneToTimepoints(isl::union_set Zone,
405                                               bool InclStart, bool InclEnd) {
406   if (!InclStart && InclEnd)
407     return Zone;
408 
409   auto ShiftedZone = shiftDim(Zone, -1, -1);
410   if (InclStart && !InclEnd)
411     return ShiftedZone;
412   else if (!InclStart && !InclEnd)
413     return give(isl_union_set_intersect(Zone.take(), ShiftedZone.take()));
414 
415   assert(InclStart && InclEnd);
416   return give(isl_union_set_union(Zone.take(), ShiftedZone.take()));
417 }
418 
419 isl::union_map polly::convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,
420                                               bool InclStart, bool InclEnd) {
421   if (!InclStart && InclEnd)
422     return Zone;
423 
424   auto ShiftedZone = shiftDim(Zone, Dim, -1, -1);
425   if (InclStart && !InclEnd)
426     return ShiftedZone;
427   else if (!InclStart && !InclEnd)
428     return give(isl_union_map_intersect(Zone.take(), ShiftedZone.take()));
429 
430   assert(InclStart && InclEnd);
431   return give(isl_union_map_union(Zone.take(), ShiftedZone.take()));
432 }
433 
434 isl::map polly::distributeDomain(isl::map Map) {
435   // Note that we cannot take Map apart into { Domain[] -> Range1[] } and {
436   // Domain[] -> Range2[] } and combine again. We would loose any relation
437   // between Range1[] and Range2[] that is not also a constraint to Domain[].
438 
439   auto Space = give(isl_map_get_space(Map.keep()));
440   auto DomainSpace = give(isl_space_domain(Space.copy()));
441   assert(DomainSpace);
442   auto DomainDims = isl_space_dim(DomainSpace.keep(), isl_dim_set);
443   auto RangeSpace = give(isl_space_unwrap(isl_space_range(Space.copy())));
444   auto Range1Space = give(isl_space_domain(RangeSpace.copy()));
445   assert(Range1Space);
446   auto Range1Dims = isl_space_dim(Range1Space.keep(), isl_dim_set);
447   auto Range2Space = give(isl_space_range(RangeSpace.copy()));
448   assert(Range2Space);
449   auto Range2Dims = isl_space_dim(Range2Space.keep(), isl_dim_set);
450 
451   auto OutputSpace = give(isl_space_map_from_domain_and_range(
452       isl_space_wrap(isl_space_map_from_domain_and_range(DomainSpace.copy(),
453                                                          Range1Space.copy())),
454       isl_space_wrap(isl_space_map_from_domain_and_range(DomainSpace.copy(),
455                                                          Range2Space.copy()))));
456 
457   auto Translator =
458       give(isl_basic_map_universe(isl_space_map_from_domain_and_range(
459           isl_space_wrap(Space.copy()), isl_space_wrap(OutputSpace.copy()))));
460 
461   for (unsigned i = 0; i < DomainDims; i += 1) {
462     Translator = give(
463         isl_basic_map_equate(Translator.take(), isl_dim_in, i, isl_dim_out, i));
464     Translator =
465         give(isl_basic_map_equate(Translator.take(), isl_dim_in, i, isl_dim_out,
466                                   DomainDims + Range1Dims + i));
467   }
468   for (unsigned i = 0; i < Range1Dims; i += 1) {
469     Translator =
470         give(isl_basic_map_equate(Translator.take(), isl_dim_in, DomainDims + i,
471                                   isl_dim_out, DomainDims + i));
472   }
473   for (unsigned i = 0; i < Range2Dims; i += 1) {
474     Translator = give(isl_basic_map_equate(
475         Translator.take(), isl_dim_in, DomainDims + Range1Dims + i, isl_dim_out,
476         DomainDims + Range1Dims + DomainDims + i));
477   }
478 
479   return give(isl_set_unwrap(isl_set_apply(
480       isl_map_wrap(Map.copy()), isl_map_from_basic_map(Translator.copy()))));
481 }
482 
483 isl::union_map polly::distributeDomain(isl::union_map UMap) {
484   auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
485   UMap.foreach_map([=, &Result](isl::map Map) {
486     auto Distributed = distributeDomain(Map);
487     Result = give(isl_union_map_add_map(Result.take(), Distributed.copy()));
488     return isl::stat::ok;
489   });
490   return Result;
491 }
492 
493 isl::union_map polly::liftDomains(isl::union_map UMap, isl::union_set Factor) {
494 
495   // { Factor[] -> Factor[] }
496   auto Factors = makeIdentityMap(std::move(Factor), true);
497 
498   return std::move(Factors).product(std::move(UMap));
499 }
500 
501 isl::union_map polly::applyDomainRange(isl::union_map UMap,
502                                        isl::union_map Func) {
503   // This implementation creates unnecessary cross products of the
504   // DomainDomain[] and Func. An alternative implementation could reverse
505   // domain+uncurry,apply Func to what now is the domain, then undo the
506   // preparing transformation. Another alternative implementation could create a
507   // translator map for each piece.
508 
509   // { DomainDomain[] }
510   auto DomainDomain = UMap.domain().unwrap().domain();
511 
512   // { [DomainDomain[] -> DomainRange[]] -> [DomainDomain[] -> NewDomainRange[]]
513   // }
514   auto LifetedFunc = liftDomains(std::move(Func), DomainDomain);
515 
516   return std::move(UMap).apply_domain(std::move(LifetedFunc));
517 }
518