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