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 IslPtr<isl_multi_aff> makeShiftDimAff(IslPtr<isl_space> Space, int Pos,
33                                       int Amount) {
34   auto Identity = give(isl_multi_aff_identity(Space.take()));
35   if (Amount == 0)
36     return Identity;
37   auto ShiftAff = give(isl_multi_aff_get_aff(Identity.keep(), Pos));
38   ShiftAff = give(isl_aff_set_constant_si(ShiftAff.take(), Amount));
39   return give(isl_multi_aff_set_aff(Identity.take(), Pos, ShiftAff.take()));
40 }
41 
42 /// Construct a map that swaps two nested tuples.
43 ///
44 /// @param FromSpace1 { Space1[] }
45 /// @param FromSpace2 { Space2[] }
46 ///
47 /// @return { [Space1[] -> Space2[]] -> [Space2[] -> Space1[]] }
48 IslPtr<isl_basic_map> makeTupleSwapBasicMap(IslPtr<isl_space> FromSpace1,
49                                             IslPtr<isl_space> FromSpace2) {
50   assert(isl_space_is_set(FromSpace1.keep()) != isl_bool_false);
51   assert(isl_space_is_set(FromSpace2.keep()) != isl_bool_false);
52 
53   auto Dims1 = isl_space_dim(FromSpace1.keep(), isl_dim_set);
54   auto Dims2 = isl_space_dim(FromSpace2.keep(), isl_dim_set);
55   auto FromSpace = give(isl_space_wrap(isl_space_map_from_domain_and_range(
56       FromSpace1.copy(), FromSpace2.copy())));
57   auto ToSpace = give(isl_space_wrap(isl_space_map_from_domain_and_range(
58       FromSpace2.take(), FromSpace1.take())));
59   auto MapSpace = give(
60       isl_space_map_from_domain_and_range(FromSpace.take(), ToSpace.take()));
61 
62   auto Result = give(isl_basic_map_universe(MapSpace.take()));
63   for (auto i = Dims1 - Dims1; i < Dims1; i += 1) {
64     Result = give(isl_basic_map_equate(Result.take(), isl_dim_in, i,
65                                        isl_dim_out, Dims2 + i));
66   }
67   for (auto i = Dims2 - Dims2; i < Dims2; i += 1) {
68     Result = give(isl_basic_map_equate(Result.take(), isl_dim_in, Dims1 + i,
69                                        isl_dim_out, i));
70   }
71 
72   return Result;
73 }
74 
75 /// Like makeTupleSwapBasicMap(IslPtr<isl_space>,IslPtr<isl_space>), but returns
76 /// an isl_map.
77 IslPtr<isl_map> makeTupleSwapMap(IslPtr<isl_space> FromSpace1,
78                                  IslPtr<isl_space> FromSpace2) {
79   auto BMapResult =
80       makeTupleSwapBasicMap(std::move(FromSpace1), std::move(FromSpace2));
81   return give(isl_map_from_basic_map(BMapResult.take()));
82 }
83 } // anonymous namespace
84 
85 IslPtr<isl_map> polly::beforeScatter(IslPtr<isl_map> Map, bool Strict) {
86   auto RangeSpace = give(isl_space_range(isl_map_get_space(Map.keep())));
87   auto ScatterRel = give(Strict ? isl_map_lex_gt(RangeSpace.take())
88                                 : isl_map_lex_ge(RangeSpace.take()));
89   return give(isl_map_apply_range(Map.take(), ScatterRel.take()));
90 }
91 
92 IslPtr<isl_union_map> polly::beforeScatter(IslPtr<isl_union_map> UMap,
93                                            bool Strict) {
94   auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
95   foreachElt(UMap, [=, &Result](IslPtr<isl_map> Map) {
96     auto After = beforeScatter(Map, Strict);
97     Result = give(isl_union_map_add_map(Result.take(), After.take()));
98   });
99   return Result;
100 }
101 
102 IslPtr<isl_map> polly::afterScatter(IslPtr<isl_map> Map, bool Strict) {
103   auto RangeSpace = give(isl_space_range(isl_map_get_space(Map.keep())));
104   auto ScatterRel = give(Strict ? isl_map_lex_lt(RangeSpace.take())
105                                 : isl_map_lex_le(RangeSpace.take()));
106   return give(isl_map_apply_range(Map.take(), ScatterRel.take()));
107 }
108 
109 IslPtr<isl_union_map> polly::afterScatter(NonowningIslPtr<isl_union_map> UMap,
110                                           bool Strict) {
111   auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
112   foreachElt(UMap, [=, &Result](IslPtr<isl_map> Map) {
113     auto After = afterScatter(Map, Strict);
114     Result = give(isl_union_map_add_map(Result.take(), After.take()));
115   });
116   return Result;
117 }
118 
119 IslPtr<isl_map> polly::betweenScatter(IslPtr<isl_map> From, IslPtr<isl_map> To,
120                                       bool InclFrom, bool InclTo) {
121   auto AfterFrom = afterScatter(From, !InclFrom);
122   auto BeforeTo = beforeScatter(To, !InclTo);
123 
124   return give(isl_map_intersect(AfterFrom.take(), BeforeTo.take()));
125 }
126 
127 IslPtr<isl_union_map> polly::betweenScatter(IslPtr<isl_union_map> From,
128                                             IslPtr<isl_union_map> To,
129                                             bool InclFrom, bool InclTo) {
130   auto AfterFrom = afterScatter(From, !InclFrom);
131   auto BeforeTo = beforeScatter(To, !InclTo);
132 
133   return give(isl_union_map_intersect(AfterFrom.take(), BeforeTo.take()));
134 }
135 
136 IslPtr<isl_map> polly::singleton(IslPtr<isl_union_map> UMap,
137                                  IslPtr<isl_space> ExpectedSpace) {
138   if (!UMap)
139     return nullptr;
140 
141   if (isl_union_map_n_map(UMap.keep()) == 0)
142     return give(isl_map_empty(ExpectedSpace.take()));
143 
144   auto Result = give(isl_map_from_union_map(UMap.take()));
145   assert(!Result || isl_space_has_equal_tuples(
146                         give(isl_map_get_space(Result.keep())).keep(),
147                         ExpectedSpace.keep()) == isl_bool_true);
148   return Result;
149 }
150 
151 IslPtr<isl_set> polly::singleton(IslPtr<isl_union_set> USet,
152                                  IslPtr<isl_space> ExpectedSpace) {
153   if (!USet)
154     return nullptr;
155 
156   if (isl_union_set_n_set(USet.keep()) == 0)
157     return give(isl_set_empty(ExpectedSpace.copy()));
158 
159   auto Result = give(isl_set_from_union_set(USet.take()));
160   assert(!Result || isl_space_has_equal_tuples(
161                         give(isl_set_get_space(Result.keep())).keep(),
162                         ExpectedSpace.keep()) == isl_bool_true);
163   return Result;
164 }
165 
166 unsigned polly::getNumScatterDims(NonowningIslPtr<isl_union_map> Schedule) {
167   unsigned Dims = 0;
168   foreachElt(Schedule, [&Dims](IslPtr<isl_map> Map) {
169     Dims = std::max(Dims, isl_map_dim(Map.keep(), isl_dim_out));
170   });
171   return Dims;
172 }
173 
174 IslPtr<isl_space>
175 polly::getScatterSpace(NonowningIslPtr<isl_union_map> Schedule) {
176   if (!Schedule)
177     return nullptr;
178   auto Dims = getNumScatterDims(Schedule);
179   auto ScatterSpace =
180       give(isl_space_set_from_params(isl_union_map_get_space(Schedule.keep())));
181   return give(isl_space_add_dims(ScatterSpace.take(), isl_dim_set, Dims));
182 }
183 
184 IslPtr<isl_union_map>
185 polly::makeIdentityMap(NonowningIslPtr<isl_union_set> USet,
186                        bool RestrictDomain) {
187   auto Result = give(isl_union_map_empty(isl_union_set_get_space(USet.keep())));
188   foreachElt(USet, [=, &Result](IslPtr<isl_set> Set) {
189     auto IdentityMap = give(isl_map_identity(
190         isl_space_map_from_set(isl_set_get_space(Set.keep()))));
191     if (RestrictDomain)
192       IdentityMap =
193           give(isl_map_intersect_domain(IdentityMap.take(), Set.take()));
194     Result = give(isl_union_map_add_map(Result.take(), IdentityMap.take()));
195   });
196   return Result;
197 }
198 
199 IslPtr<isl_map> polly::reverseDomain(IslPtr<isl_map> Map) {
200   auto DomSpace =
201       give(isl_space_unwrap(isl_space_domain(isl_map_get_space(Map.keep()))));
202   auto Space1 = give(isl_space_domain(DomSpace.copy()));
203   auto Space2 = give(isl_space_range(DomSpace.take()));
204   auto Swap = makeTupleSwapMap(std::move(Space1), std::move(Space2));
205   return give(isl_map_apply_domain(Map.take(), Swap.take()));
206 }
207 
208 IslPtr<isl_union_map>
209 polly::reverseDomain(NonowningIslPtr<isl_union_map> UMap) {
210   auto Result = give(isl_union_map_empty(isl_union_map_get_space(UMap.keep())));
211   foreachElt(UMap, [=, &Result](IslPtr<isl_map> Map) {
212     auto Reversed = reverseDomain(std::move(Map));
213     Result = give(isl_union_map_add_map(Result.take(), Reversed.take()));
214   });
215   return Result;
216 }
217 
218 IslPtr<isl_set> polly::shiftDim(IslPtr<isl_set> Set, int Pos, int Amount) {
219   int NumDims = isl_set_dim(Set.keep(), isl_dim_set);
220   if (Pos < 0)
221     Pos = NumDims + Pos;
222   assert(Pos < NumDims && "Dimension index must be in range");
223   auto Space = give(isl_set_get_space(Set.keep()));
224   Space = give(isl_space_map_from_domain_and_range(Space.copy(), Space.copy()));
225   auto Translator = makeShiftDimAff(std::move(Space), Pos, Amount);
226   auto TranslatorMap = give(isl_map_from_multi_aff(Translator.take()));
227   return give(isl_set_apply(Set.take(), TranslatorMap.take()));
228 }
229 
230 IslPtr<isl_union_set> polly::shiftDim(IslPtr<isl_union_set> USet, int Pos,
231                                       int Amount) {
232   auto Result = give(isl_union_set_empty(isl_union_set_get_space(USet.keep())));
233   foreachElt(USet, [=, &Result](IslPtr<isl_set> Set) {
234     auto Shifted = shiftDim(Set, Pos, Amount);
235     Result = give(isl_union_set_add_set(Result.take(), Shifted.take()));
236   });
237   return Result;
238 }
239 
240 void polly::simplify(IslPtr<isl_set> &Set) {
241   Set = give(isl_set_compute_divs(Set.take()));
242   Set = give(isl_set_detect_equalities(Set.take()));
243   Set = give(isl_set_coalesce(Set.take()));
244 }
245 
246 void polly::simplify(IslPtr<isl_union_set> &USet) {
247   USet = give(isl_union_set_compute_divs(USet.take()));
248   USet = give(isl_union_set_detect_equalities(USet.take()));
249   USet = give(isl_union_set_coalesce(USet.take()));
250 }
251 
252 void polly::simplify(IslPtr<isl_map> &Map) {
253   Map = give(isl_map_compute_divs(Map.take()));
254   Map = give(isl_map_detect_equalities(Map.take()));
255   Map = give(isl_map_coalesce(Map.take()));
256 }
257 
258 void polly::simplify(IslPtr<isl_union_map> &UMap) {
259   UMap = give(isl_union_map_compute_divs(UMap.take()));
260   UMap = give(isl_union_map_detect_equalities(UMap.take()));
261   UMap = give(isl_union_map_coalesce(UMap.take()));
262 }
263 
264 IslPtr<isl_union_map>
265 polly::computeReachingWrite(IslPtr<isl_union_map> Schedule,
266                             IslPtr<isl_union_map> Writes, bool Reverse,
267                             bool InclPrevDef, bool InclNextDef) {
268 
269   // { Scatter[] }
270   auto ScatterSpace = getScatterSpace(Schedule);
271 
272   // { ScatterRead[] -> ScatterWrite[] }
273   IslPtr<isl_map> Relation;
274   if (Reverse)
275     Relation = give(InclPrevDef ? isl_map_lex_lt(ScatterSpace.take())
276                                 : isl_map_lex_le(ScatterSpace.take()));
277   else
278     Relation = give(InclNextDef ? isl_map_lex_gt(ScatterSpace.take())
279                                 : isl_map_lex_ge(ScatterSpace.take()));
280 
281   // { ScatterWrite[] -> [ScatterRead[] -> ScatterWrite[]] }
282   auto RelationMap = give(isl_map_reverse(isl_map_range_map(Relation.take())));
283 
284   // { Element[] -> ScatterWrite[] }
285   auto WriteAction =
286       give(isl_union_map_apply_domain(Schedule.copy(), Writes.take()));
287 
288   // { ScatterWrite[] -> Element[] }
289   auto WriteActionRev = give(isl_union_map_reverse(WriteAction.copy()));
290 
291   // { Element[] -> [ScatterUse[] -> ScatterWrite[]] }
292   auto DefSchedRelation = give(isl_union_map_apply_domain(
293       isl_union_map_from_map(RelationMap.take()), WriteActionRev.take()));
294 
295   // For each element, at every point in time, map to the times of previous
296   // definitions. { [Element[] -> ScatterRead[]] -> ScatterWrite[] }
297   auto ReachableWrites = give(isl_union_map_uncurry(DefSchedRelation.take()));
298   if (Reverse)
299     ReachableWrites = give(isl_union_map_lexmin(ReachableWrites.copy()));
300   else
301     ReachableWrites = give(isl_union_map_lexmax(ReachableWrites.copy()));
302 
303   // { [Element[] -> ScatterWrite[]] -> ScatterWrite[] }
304   auto SelfUse = give(isl_union_map_range_map(WriteAction.take()));
305 
306   if (InclPrevDef && InclNextDef) {
307     // Add the Def itself to the solution.
308     ReachableWrites =
309         give(isl_union_map_union(ReachableWrites.take(), SelfUse.take()));
310     ReachableWrites = give(isl_union_map_coalesce(ReachableWrites.take()));
311   } else if (!InclPrevDef && !InclNextDef) {
312     // Remove Def itself from the solution.
313     ReachableWrites =
314         give(isl_union_map_subtract(ReachableWrites.take(), SelfUse.take()));
315   }
316 
317   // { [Element[] -> ScatterRead[]] -> Domain[] }
318   auto ReachableWriteDomain = give(isl_union_map_apply_range(
319       ReachableWrites.take(), isl_union_map_reverse(Schedule.take())));
320 
321   return ReachableWriteDomain;
322 }
323 
324 IslPtr<isl_union_map> polly::computeArrayUnused(IslPtr<isl_union_map> Schedule,
325                                                 IslPtr<isl_union_map> Writes,
326                                                 IslPtr<isl_union_map> Reads,
327                                                 bool ReadEltInSameInst,
328                                                 bool IncludeLastRead,
329                                                 bool IncludeWrite) {
330   // { Element[] -> Scatter[] }
331   auto ReadActions =
332       give(isl_union_map_apply_domain(Schedule.copy(), Reads.take()));
333   auto WriteActions =
334       give(isl_union_map_apply_domain(Schedule.copy(), Writes.copy()));
335 
336   // { [Element[] -> Scatter[] }
337   auto AfterReads = afterScatter(ReadActions, ReadEltInSameInst);
338   auto WritesBeforeAnyReads =
339       give(isl_union_map_subtract(WriteActions.take(), AfterReads.take()));
340   auto BeforeWritesBeforeAnyReads =
341       beforeScatter(WritesBeforeAnyReads, !IncludeWrite);
342 
343   // { [Element[] -> DomainWrite[]] -> Scatter[] }
344   auto EltDomWrites = give(isl_union_map_apply_range(
345       isl_union_map_range_map(isl_union_map_reverse(Writes.copy())),
346       Schedule.copy()));
347 
348   // { [Element[] -> Scatter[]] -> DomainWrite[] }
349   auto ReachingOverwrite = computeReachingWrite(
350       Schedule, Writes, true, ReadEltInSameInst, !ReadEltInSameInst);
351 
352   // { [Element[] -> Scatter[]] -> DomainWrite[] }
353   auto ReadsOverwritten = give(isl_union_map_intersect_domain(
354       ReachingOverwrite.take(), isl_union_map_wrap(ReadActions.take())));
355 
356   // { [Element[] -> DomainWrite[]] -> Scatter[] }
357   auto ReadsOverwrittenRotated = give(isl_union_map_reverse(
358       isl_union_map_curry(reverseDomain(ReadsOverwritten).take())));
359   auto LastOverwrittenRead =
360       give(isl_union_map_lexmax(ReadsOverwrittenRotated.take()));
361 
362   // { [Element[] -> DomainWrite[]] -> Scatter[] }
363   auto BetweenLastReadOverwrite = betweenScatter(
364       LastOverwrittenRead, EltDomWrites, IncludeLastRead, IncludeWrite);
365 
366   return give(isl_union_map_union(
367       BeforeWritesBeforeAnyReads.take(),
368       isl_union_map_domain_factor_domain(BetweenLastReadOverwrite.take())));
369 }
370 
371 IslPtr<isl_union_set> polly::convertZoneToTimepoints(IslPtr<isl_union_set> Zone,
372                                                      bool InclStart,
373                                                      bool InclEnd) {
374   if (!InclStart && InclEnd)
375     return Zone;
376 
377   auto ShiftedZone = shiftDim(Zone, -1, -1);
378   if (InclStart && !InclEnd)
379     return ShiftedZone;
380   else if (!InclStart && !InclEnd)
381     return give(isl_union_set_intersect(Zone.take(), ShiftedZone.take()));
382 
383   assert(InclStart && InclEnd);
384   return give(isl_union_set_union(Zone.take(), ShiftedZone.take()));
385 }
386