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

source code of polly/lib/Support/ISLTools.cpp