1 | //===------ ISLTools.h ------------------------------------------*- 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 | #ifndef POLLY_ISLTOOLS_H |
15 | #define POLLY_ISLTOOLS_H |
16 | |
17 | #include "llvm/ADT/Sequence.h" |
18 | #include "llvm/ADT/iterator.h" |
19 | #include "isl/isl-noexceptions.h" |
20 | #include <algorithm> |
21 | #include <cassert> |
22 | |
23 | /// In debug builds assert that the @p Size is valid, in non-debug builds |
24 | /// disable the mandatory state checking but do not enforce the error checking. |
25 | inline void islAssert(const isl::size &Size) { |
26 | #ifdef NDEBUG |
27 | // Calling is_error() marks that the error status has been checked which |
28 | // disables the error-status-not-checked errors that would otherwise occur |
29 | // when using the value. |
30 | (void)Size.is_error(); |
31 | #else |
32 | // Assert on error in debug builds. |
33 | assert(!Size.is_error()); |
34 | #endif |
35 | } |
36 | |
37 | /// Check that @p Size is valid (only on debug builds) and cast it to unsigned. |
38 | /// Cast the @p Size to unsigned. If the @p Size is not valid (Size.is_error() |
39 | /// == true) then an assert and an abort are triggered. |
40 | inline unsigned unsignedFromIslSize(const isl::size &Size) { |
41 | islAssert(Size); |
42 | return static_cast<unsigned>(Size); |
43 | } |
44 | |
45 | namespace isl { |
46 | inline namespace noexceptions { |
47 | |
48 | template <typename ListT> |
49 | using list_element_type = decltype(std::declval<ListT>().get_at(0)); |
50 | |
51 | template <typename ListT> |
52 | class isl_iterator |
53 | : public llvm::iterator_facade_base<isl_iterator<ListT>, |
54 | std::forward_iterator_tag, |
55 | list_element_type<ListT>> { |
56 | public: |
57 | using ElementT = list_element_type<ListT>; |
58 | |
59 | explicit isl_iterator(const ListT &List) |
60 | : List(&List), Position(std::max(List.size().release(), 0)) {} |
61 | isl_iterator(const ListT &List, int Position) |
62 | : List(&List), Position(Position) {} |
63 | |
64 | bool operator==(const isl_iterator &O) const { |
65 | return List == O.List && Position == O.Position; |
66 | } |
67 | |
68 | isl_iterator &operator++() { |
69 | ++Position; |
70 | return *this; |
71 | } |
72 | |
73 | isl_iterator operator++(int) { |
74 | isl_iterator Copy{*this}; |
75 | ++Position; |
76 | return Copy; |
77 | } |
78 | |
79 | ElementT operator*() const { return List->get_at(this->Position); } |
80 | |
81 | protected: |
82 | const ListT *List; |
83 | int Position = 0; |
84 | }; |
85 | |
86 | template <typename T> isl_iterator<T> begin(const T &t) { |
87 | return isl_iterator<T>(t, 0); |
88 | } |
89 | template <typename T> isl_iterator<T> end(const T &t) { |
90 | return isl_iterator<T>(t); |
91 | } |
92 | |
93 | } // namespace noexceptions |
94 | } // namespace isl |
95 | |
96 | namespace polly { |
97 | |
98 | /// Return the range elements that are lexicographically smaller. |
99 | /// |
100 | /// @param Map { Space[] -> Scatter[] } |
101 | /// @param Strict True for strictly lexicographically smaller elements (exclude |
102 | /// same timepoints from the result). |
103 | /// |
104 | /// @return { Space[] -> Scatter[] } |
105 | /// A map to all timepoints that happen before the timepoints the input |
106 | /// mapped to. |
107 | isl::map beforeScatter(isl::map Map, bool Strict); |
108 | |
109 | /// Piecewise beforeScatter(isl::map,bool). |
110 | isl::union_map beforeScatter(isl::union_map UMap, bool Strict); |
111 | |
112 | /// Return the range elements that are lexicographically larger. |
113 | /// |
114 | /// @param Map { Space[] -> Scatter[] } |
115 | /// @param Strict True for strictly lexicographically larger elements (exclude |
116 | /// same timepoints from the result). |
117 | /// |
118 | /// @return { Space[] -> Scatter[] } |
119 | /// A map to all timepoints that happen after the timepoints the input |
120 | /// map originally mapped to. |
121 | isl::map afterScatter(isl::map Map, bool Strict); |
122 | |
123 | /// Piecewise afterScatter(isl::map,bool). |
124 | isl::union_map afterScatter(const isl::union_map &UMap, bool Strict); |
125 | |
126 | /// Construct a range of timepoints between two timepoints. |
127 | /// |
128 | /// Example: |
129 | /// From := { A[] -> [0]; B[] -> [0] } |
130 | /// To := { B[] -> [10]; C[] -> [20] } |
131 | /// |
132 | /// Result: |
133 | /// { B[] -> [i] : 0 < i < 10 } |
134 | /// |
135 | /// Note that A[] and C[] are not in the result because they do not have a start |
136 | /// or end timepoint. If a start (or end) timepoint is not unique, the first |
137 | /// (respectively last) is chosen. |
138 | /// |
139 | /// @param From { Space[] -> Scatter[] } |
140 | /// Map to start timepoints. |
141 | /// @param To { Space[] -> Scatter[] } |
142 | /// Map to end timepoints. |
143 | /// @param InclFrom Whether to include the start timepoints in the result. In |
144 | /// the example, this would add { B[] -> [0] } |
145 | /// @param InclTo Whether to include the end timepoints in the result. In this |
146 | /// example, this would add { B[] -> [10] } |
147 | /// |
148 | /// @return { Space[] -> Scatter[] } |
149 | /// A map for each domain element of timepoints between two extreme |
150 | /// points, or nullptr if @p From or @p To is nullptr, or the isl max |
151 | /// operations is exceeded. |
152 | isl::map betweenScatter(isl::map From, isl::map To, bool InclFrom, bool InclTo); |
153 | |
154 | /// Piecewise betweenScatter(isl::map,isl::map,bool,bool). |
155 | isl::union_map betweenScatter(isl::union_map From, isl::union_map To, |
156 | bool InclFrom, bool InclTo); |
157 | |
158 | /// If by construction a union map is known to contain only a single map, return |
159 | /// it. |
160 | /// |
161 | /// This function combines isl_map_from_union_map() and |
162 | /// isl_union_map_extract_map(). isl_map_from_union_map() fails if the map is |
163 | /// empty because it does not know which space it would be in. |
164 | /// isl_union_map_extract_map() on the other hand does not check whether there |
165 | /// is (at most) one isl_map in the union, i.e. how it has been constructed is |
166 | /// probably wrong. |
167 | isl::map singleton(isl::union_map UMap, isl::space ExpectedSpace); |
168 | |
169 | /// If by construction an isl_union_set is known to contain only a single |
170 | /// isl_set, return it. |
171 | /// |
172 | /// This function combines isl_set_from_union_set() and |
173 | /// isl_union_set_extract_set(). isl_map_from_union_set() fails if the set is |
174 | /// empty because it does not know which space it would be in. |
175 | /// isl_union_set_extract_set() on the other hand does not check whether there |
176 | /// is (at most) one isl_set in the union, i.e. how it has been constructed is |
177 | /// probably wrong. |
178 | isl::set singleton(isl::union_set USet, isl::space ExpectedSpace); |
179 | |
180 | /// Determine how many dimensions the scatter space of @p Schedule has. |
181 | /// |
182 | /// The schedule must not be empty and have equal number of dimensions of any |
183 | /// subspace it contains. |
184 | /// |
185 | /// The implementation currently returns the maximum number of dimensions it |
186 | /// encounters, if different, and 0 if none is encountered. However, most other |
187 | /// code will most likely fail if one of these happen. |
188 | unsigned getNumScatterDims(const isl::union_map &Schedule); |
189 | |
190 | /// Return the scatter space of a @p Schedule. |
191 | /// |
192 | /// This is basically the range space of the schedule map, but harder to |
193 | /// determine because it is an isl_union_map. |
194 | isl::space getScatterSpace(const isl::union_map &Schedule); |
195 | |
196 | /// Construct an identity map for the given domain values. |
197 | /// |
198 | /// @param USet { Space[] } |
199 | /// The returned map's domain and range. |
200 | /// @param RestrictDomain If true, the returned map only maps elements contained |
201 | /// in @p Set and no other. If false, it returns an |
202 | /// overapproximation with the identity maps of any space |
203 | /// in @p Set, not just the elements in it. |
204 | /// |
205 | /// @return { Space[] -> Space[] } |
206 | /// A map that maps each value of @p Set to itself. |
207 | isl::map makeIdentityMap(const isl::set &Set, bool RestrictDomain); |
208 | |
209 | /// Construct an identity map for the given domain values. |
210 | /// |
211 | /// There is no type resembling isl_union_space, hence we have to pass an |
212 | /// isl_union_set as the map's domain and range space. |
213 | /// |
214 | /// @param USet { Space[] } |
215 | /// The returned map's domain and range. |
216 | /// @param RestrictDomain If true, the returned map only maps elements contained |
217 | /// in @p USet and no other. If false, it returns an |
218 | /// overapproximation with the identity maps of any space |
219 | /// in @p USet, not just the elements in it. |
220 | /// |
221 | /// @return { Space[] -> Space[] } |
222 | /// A map that maps each value of @p USet to itself. |
223 | isl::union_map makeIdentityMap(const isl::union_set &USet, bool RestrictDomain); |
224 | |
225 | /// Reverse the nested map tuple in @p Map's domain. |
226 | /// |
227 | /// @param Map { [Space1[] -> Space2[]] -> Space3[] } |
228 | /// |
229 | /// @return { [Space2[] -> Space1[]] -> Space3[] } |
230 | isl::map reverseDomain(isl::map Map); |
231 | |
232 | /// Piecewise reverseDomain(isl::map). |
233 | isl::union_map reverseDomain(const isl::union_map &UMap); |
234 | |
235 | /// Add a constant to one dimension of a set. |
236 | /// |
237 | /// @param Map The set to shift a dimension in. |
238 | /// @param Pos The dimension to shift. If negative, the dimensions are |
239 | /// counted from the end instead from the beginning. E.g. -1 is |
240 | /// the last dimension in the tuple. |
241 | /// @param Amount The offset to add to the specified dimension. |
242 | /// |
243 | /// @return The modified set. |
244 | isl::set shiftDim(isl::set Set, int Pos, int Amount); |
245 | |
246 | /// Piecewise shiftDim(isl::set,int,int). |
247 | isl::union_set shiftDim(isl::union_set USet, int Pos, int Amount); |
248 | |
249 | /// Add a constant to one dimension of a map. |
250 | /// |
251 | /// @param Map The map to shift a dimension in. |
252 | /// @param Type A tuple of @p Map which contains the dimension to shift. |
253 | /// @param Pos The dimension to shift. If negative, the dimensions are |
254 | /// counted from the end instead from the beginning. Eg. -1 is the last |
255 | /// dimension in the tuple. |
256 | /// @param Amount The offset to add to the specified dimension. |
257 | /// |
258 | /// @return The modified map. |
259 | isl::map shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount); |
260 | |
261 | /// Add a constant to one dimension of a each map in a union map. |
262 | /// |
263 | /// @param UMap The maps to shift a dimension in. |
264 | /// @param Type The tuple which contains the dimension to shift. |
265 | /// @param Pos The dimension to shift. If negative, the dimensions are |
266 | /// counted from the ends of each map of union instead from their |
267 | /// beginning. E.g. -1 is the last dimension of any map. |
268 | /// @param Amount The offset to add to the specified dimension. |
269 | /// |
270 | /// @return The union of all modified maps. |
271 | isl::union_map shiftDim(isl::union_map UMap, isl::dim Dim, int Pos, int Amount); |
272 | |
273 | /// Simplify a set inplace. |
274 | void simplify(isl::set &Set); |
275 | |
276 | /// Simplify a union set inplace. |
277 | void simplify(isl::union_set &USet); |
278 | |
279 | /// Simplify a map inplace. |
280 | void simplify(isl::map &Map); |
281 | |
282 | /// Simplify a union map inplace. |
283 | void simplify(isl::union_map &UMap); |
284 | |
285 | /// Compute the reaching definition statement or the next overwrite for each |
286 | /// definition of an array element. |
287 | /// |
288 | /// The reaching definition of an array element at a specific timepoint is the |
289 | /// statement instance that has written the current element's content. |
290 | /// Alternatively, this function determines for each timepoint and element which |
291 | /// write is going to overwrite an element at a future timepoint. This can be |
292 | /// seen as "reaching definition in reverse" where definitions are found in the |
293 | /// past. |
294 | /// |
295 | /// For example: |
296 | /// |
297 | /// Schedule := { Write[] -> [0]; Overwrite[] -> [10] } |
298 | /// Defs := { Write[] -> A[5]; Overwrite[] -> A[5] } |
299 | /// |
300 | /// If index 5 of array A is written at timepoint 0 and 10, the resulting |
301 | /// reaching definitions are: |
302 | /// |
303 | /// { [A[5] -> [i]] -> Write[] : 0 < i < 10; |
304 | /// [A[5] -> [i]] -> Overwrite[] : 10 < i } |
305 | /// |
306 | /// Between timepoint 0 (Write[]) and timepoint 10 (Overwrite[]), the |
307 | /// content of A[5] is written by statement instance Write[] and after |
308 | /// timepoint 10 by Overwrite[]. Values not defined in the map have no known |
309 | /// definition. This includes the statement instance timepoints themselves, |
310 | /// because reads at those timepoints could either read the old or the new |
311 | /// value, defined only by the statement itself. But this can be changed by @p |
312 | /// InclPrevDef and @p InclNextDef. InclPrevDef=false and InclNextDef=true |
313 | /// returns a zone. Unless @p InclPrevDef and @p InclNextDef are both true, |
314 | /// there is only one unique definition per element and timepoint. |
315 | /// |
316 | /// @param Schedule { DomainWrite[] -> Scatter[] } |
317 | /// Schedule of (at least) all array writes. Instances not in |
318 | /// @p Writes are ignored. |
319 | /// @param Writes { DomainWrite[] -> Element[] } |
320 | /// Elements written to by the statement instances. |
321 | /// @param Reverse If true, look for definitions in the future. That is, |
322 | /// find the write that is overwrites the current value. |
323 | /// @param InclPrevDef Include the definition's timepoint to the set of |
324 | /// well-defined elements (any load at that timepoint happen |
325 | /// at the writes). In the example, enabling this option adds |
326 | /// {[A[5] -> [0]] -> Write[]; [A[5] -> [10]] -> Overwrite[]} |
327 | /// to the result. |
328 | /// @param InclNextDef Whether to assume that at the timepoint where an element |
329 | /// is overwritten, it still contains the old value (any load |
330 | /// at that timepoint would happen before the overwrite). In |
331 | /// this example, enabling this adds |
332 | /// { [A[] -> [10]] -> Write[] } to the result. |
333 | /// |
334 | /// @return { [Element[] -> Scatter[]] -> DomainWrite[] } |
335 | /// The reaching definitions or future overwrite as described above, or |
336 | /// nullptr if either @p Schedule or @p Writes is nullptr, or the isl |
337 | /// max operations count has exceeded. |
338 | isl::union_map computeReachingWrite(isl::union_map Schedule, |
339 | isl::union_map Writes, bool Reverse, |
340 | bool InclPrevDef, bool InclNextDef); |
341 | |
342 | /// Compute the timepoints where the contents of an array element are not used. |
343 | /// |
344 | /// An element is unused at a timepoint when the element is overwritten in |
345 | /// the future, but it is not read in between. Another way to express this: the |
346 | /// time from when the element is written, to the most recent read before it, or |
347 | /// infinitely into the past if there is no read before. Such unused elements |
348 | /// can be overwritten by any value without changing the scop's semantics. An |
349 | /// example: |
350 | /// |
351 | /// Schedule := { Read[] -> [0]; Write[] -> [10]; Def[] -> [20] } |
352 | /// Writes := { Write[] -> A[5]; Def[] -> A[6] } |
353 | /// Reads := { Read[] -> A[5] } |
354 | /// |
355 | /// The result is: |
356 | /// |
357 | /// { A[5] -> [i] : 0 < i < 10; |
358 | /// A[6] -> [i] : i < 20 } |
359 | /// |
360 | /// That is, A[5] is unused between timepoint 0 (the read) and timepoint 10 (the |
361 | /// write). A[6] is unused before timepoint 20, but might be used after the |
362 | /// scop's execution (A[5] and any other A[i] as well). Use InclLastRead=false |
363 | /// and InclWrite=true to interpret the result as zone. |
364 | /// |
365 | /// @param Schedule { Domain[] -> Scatter[] } |
366 | /// The schedule of (at least) all statement instances |
367 | /// occurring in @p Writes or @p Reads. All other |
368 | /// instances are ignored. |
369 | /// @param Writes { DomainWrite[] -> Element[] } |
370 | /// Elements written to by the statement instances. |
371 | /// @param Reads { DomainRead[] -> Element[] } |
372 | /// Elements read from by the statement instances. |
373 | /// @param ReadEltInSameInst Whether a load reads the value from a write |
374 | /// that is scheduled at the same timepoint (Writes |
375 | /// happen before reads). Otherwise, loads use the |
376 | /// value of an element that it had before the |
377 | /// timepoint (Reads before writes). For example: |
378 | /// { Read[] -> [0]; Write[] -> [0] } |
379 | /// With ReadEltInSameInst=false it is assumed that the |
380 | /// read happens before the write, such that the |
381 | /// element is never unused, or just at timepoint 0, |
382 | /// depending on InclLastRead/InclWrite. |
383 | /// With ReadEltInSameInst=false it assumes that the |
384 | /// value just written is used. Anything before |
385 | /// timepoint 0 is considered unused. |
386 | /// @param InclLastRead Whether a timepoint where an element is last read |
387 | /// counts as unused (the read happens at the beginning |
388 | /// of its timepoint, and nothing (else) can use it |
389 | /// during the timepoint). In the example, this option |
390 | /// adds { A[5] -> [0] } to the result. |
391 | /// @param InclWrite Whether the timepoint where an element is written |
392 | /// itself counts as unused (the write happens at the |
393 | /// end of its timepoint; no (other) operations uses |
394 | /// the element during the timepoint). In this example, |
395 | /// this adds |
396 | /// { A[5] -> [10]; A[6] -> [20] } to the result. |
397 | /// |
398 | /// @return { Element[] -> Scatter[] } |
399 | /// The unused timepoints as defined above, or nullptr if either @p |
400 | /// Schedule, @p Writes are @p Reads is nullptr, or the ISL max |
401 | /// operations count is exceeded. |
402 | isl::union_map computeArrayUnused(isl::union_map Schedule, |
403 | isl::union_map Writes, isl::union_map Reads, |
404 | bool ReadEltInSameInst, bool InclLastRead, |
405 | bool InclWrite); |
406 | |
407 | /// Convert a zone (range between timepoints) to timepoints. |
408 | /// |
409 | /// A zone represents the time between (integer) timepoints, but not the |
410 | /// timepoints themselves. This function can be used to determine whether a |
411 | /// timepoint lies within a zone. |
412 | /// |
413 | /// For instance, the range (1,3), representing the time between 1 and 3, is |
414 | /// represented by the zone |
415 | /// |
416 | /// { [i] : 1 < i <= 3 } |
417 | /// |
418 | /// The set of timepoints that lie completely within this range is |
419 | /// |
420 | /// { [i] : 1 < i < 3 } |
421 | /// |
422 | /// A typical use-case is the range in which a value written by a store is |
423 | /// available until it is overwritten by another value. If the write is at |
424 | /// timepoint 1 and its value is overwritten by another value at timepoint 3, |
425 | /// the value is available between those timepoints: timepoint 2 in this |
426 | /// example. |
427 | /// |
428 | /// |
429 | /// When InclStart is true, the range is interpreted left-inclusive, i.e. adds |
430 | /// the timepoint 1 to the result: |
431 | /// |
432 | /// { [i] : 1 <= i < 3 } |
433 | /// |
434 | /// In the use-case mentioned above that means that the value written at |
435 | /// timepoint 1 is already available in timepoint 1 (write takes place before |
436 | /// any read of it even if executed at the same timepoint) |
437 | /// |
438 | /// When InclEnd is true, the range is interpreted right-inclusive, i.e. adds |
439 | /// the timepoint 3 to the result: |
440 | /// |
441 | /// { [i] : 1 < i <= 3 } |
442 | /// |
443 | /// In the use-case mentioned above that means that although the value is |
444 | /// overwritten in timepoint 3, the old value is still available at timepoint 3 |
445 | /// (write takes place after any read even if executed at the same timepoint) |
446 | /// |
447 | /// @param Zone { Zone[] } |
448 | /// @param InclStart Include timepoints adjacent to the beginning of a zone. |
449 | /// @param InclEnd Include timepoints adjacent to the ending of a zone. |
450 | /// |
451 | /// @return { Scatter[] } |
452 | isl::union_set convertZoneToTimepoints(isl::union_set Zone, bool InclStart, |
453 | bool InclEnd); |
454 | |
455 | /// Like convertZoneToTimepoints(isl::union_set,InclStart,InclEnd), but convert |
456 | /// either the domain or the range of a map. |
457 | isl::union_map convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim, |
458 | bool InclStart, bool InclEnd); |
459 | |
460 | /// Overload of convertZoneToTimepoints(isl::map,InclStart,InclEnd) to process |
461 | /// only a single map. |
462 | isl::map convertZoneToTimepoints(isl::map Zone, isl::dim Dim, bool InclStart, |
463 | bool InclEnd); |
464 | |
465 | /// Distribute the domain to the tuples of a wrapped range map. |
466 | /// |
467 | /// @param Map { Domain[] -> [Range1[] -> Range2[]] } |
468 | /// |
469 | /// @return { [Domain[] -> Range1[]] -> [Domain[] -> Range2[]] } |
470 | isl::map distributeDomain(isl::map Map); |
471 | |
472 | /// Apply distributeDomain(isl::map) to each map in the union. |
473 | isl::union_map distributeDomain(isl::union_map UMap); |
474 | |
475 | /// Prepend a space to the tuples of a map. |
476 | /// |
477 | /// @param UMap { Domain[] -> Range[] } |
478 | /// @param Factor { Factor[] } |
479 | /// |
480 | /// @return { [Factor[] -> Domain[]] -> [Factor[] -> Range[]] } |
481 | isl::union_map liftDomains(isl::union_map UMap, isl::union_set Factor); |
482 | |
483 | /// Apply a map to the 'middle' of another relation. |
484 | /// |
485 | /// @param UMap { [DomainDomain[] -> DomainRange[]] -> Range[] } |
486 | /// @param Func { DomainRange[] -> NewDomainRange[] } |
487 | /// |
488 | /// @return { [DomainDomain[] -> NewDomainRange[]] -> Range[] } |
489 | isl::union_map applyDomainRange(isl::union_map UMap, isl::union_map Func); |
490 | |
491 | /// Intersect the range of @p Map with @p Range. |
492 | /// |
493 | /// Since @p Map is an isl::map, the result will be a single space, even though |
494 | /// @p Range is an isl::union_set. This is the only difference to |
495 | /// isl::map::intersect_range and isl::union_map::interset_range. |
496 | /// |
497 | /// @param Map { Domain[] -> Range[] } |
498 | /// @param Range { Range[] } |
499 | /// |
500 | /// @return { Domain[] -> Range[] } |
501 | isl::map intersectRange(isl::map Map, isl::union_set Range); |
502 | |
503 | /// Subtract the parameter space @p Params from @p Map. |
504 | /// This is akin to isl::map::intersect_params. |
505 | /// |
506 | /// Example: |
507 | /// subtractParams( |
508 | /// { [i] -> [i] }, |
509 | /// [x] -> { : x < 0 } |
510 | /// ) = [x] -> { [i] -> [i] : x >= 0 } |
511 | /// |
512 | /// @param Map Remove the conditions of @p Params from this map. |
513 | /// @param Params Parameter set to subtract. |
514 | /// |
515 | /// @param The map with the parameter conditions removed. |
516 | isl::map subtractParams(isl::map Map, isl::set Params); |
517 | |
518 | /// Subtract the parameter space @p Params from @p Set. |
519 | isl::set subtractParams(isl::set Set, isl::set Params); |
520 | |
521 | /// If @p PwAff maps to a constant, return said constant. If @p Max/@p Min, it |
522 | /// can also be a piecewise constant and it would return the minimum/maximum |
523 | /// value. Otherwise, return NaN. |
524 | isl::val getConstant(isl::pw_aff PwAff, bool Max, bool Min); |
525 | |
526 | /// If the relation @p PwAff lies on a hyperplane where the given |
527 | /// dimension @p Pos with the type @p Dim has a fixed value, then |
528 | /// return that value. Otherwise return NaN. |
529 | isl::val getConstant(isl::map Map, isl::dim Dim, int Pos); |
530 | |
531 | /// Check that @p End is valid and return an iterator from @p Begin to @p End |
532 | /// |
533 | /// Use case example: |
534 | /// for (unsigned i : rangeIslSize(0, Map.domain_tuple_dim())) |
535 | /// // do stuff |
536 | llvm::iota_range<unsigned> rangeIslSize(unsigned Begin, isl::size End); |
537 | |
538 | /// Dump a description of the argument to llvm::errs(). |
539 | /// |
540 | /// In contrast to isl's dump function, there are a few differences: |
541 | /// - Each polyhedron (pieces) is written on its own line. |
542 | /// - Spaces are sorted by structure. E.g. maps with same domain space are |
543 | /// grouped. Isl sorts them according to the space's hash function. |
544 | /// - Pieces of the same space are sorted using their lower bound. |
545 | /// - A more compact to_str representation is used instead of Isl's dump |
546 | /// functions that try to show the internal representation. |
547 | /// |
548 | /// The goal is to get a better understandable representation that is also |
549 | /// useful to compare two sets. As all dump() functions, its intended use is to |
550 | /// be called in a debugger only. |
551 | /// |
552 | /// isl_map_dump example: |
553 | /// [p_0, p_1, p_2] -> { Stmt0[i0] -> [o0, o1] : (o0 = i0 and o1 = 0 and i0 > 0 |
554 | /// and i0 <= 5 - p_2) or (i0 = 0 and o0 = 0 and o1 = 0); Stmt3[i0] -> [o0, o1] |
555 | /// : (o0 = i0 and o1 = 3 and i0 > 0 and i0 <= 5 - p_2) or (i0 = 0 and o0 = 0 |
556 | /// and o1 = 3); Stmt2[i0] -> [o0, o1] : (o0 = i0 and o1 = 1 and i0 >= 3 + p_0 - |
557 | /// p_1 and i0 > 0 and i0 <= 5 - p_2) or (o0 = i0 and o1 = 1 and i0 > 0 and i0 |
558 | /// <= 5 - p_2 and i0 < p_0 - p_1) or (i0 = 0 and o0 = 0 and o1 = 1 and p_1 >= 3 |
559 | /// + p_0) or (i0 = 0 and o0 = 0 and o1 = 1 and p_1 < p_0) or (p_0 = 0 and i0 = |
560 | /// 2 - p_1 and o0 = 2 - p_1 and o1 = 1 and p_2 <= 3 + p_1 and p_1 <= 1) or (p_1 |
561 | /// = 1 + p_0 and i0 = 0 and o0 = 0 and o1 = 1) or (p_0 = 0 and p_1 = 2 and i0 = |
562 | /// 0 and o0 = 0 and o1 = 1) or (p_0 = -1 and p_1 = -1 and i0 = 0 and o0 = 0 and |
563 | /// o1 = 1); Stmt1[i0] -> [o0, o1] : (p_0 = -1 and i0 = 1 - p_1 and o0 = 1 - p_1 |
564 | /// and o1 = 2 and p_2 <= 4 + p_1 and p_1 <= 0) or (p_0 = 0 and i0 = -p_1 and o0 |
565 | /// = -p_1 and o1 = 2 and p_2 <= 5 + p_1 and p_1 < 0) or (p_0 = -1 and p_1 = 1 |
566 | /// and i0 = 0 and o0 = 0 and o1 = 2) or (p_0 = 0 and p_1 = 0 and i0 = 0 and o0 |
567 | /// = 0 and o1 = 2) } |
568 | /// |
569 | /// dumpPw example (same set): |
570 | /// [p_0, p_1, p_2] -> { |
571 | /// Stmt0[0] -> [0, 0]; |
572 | /// Stmt0[i0] -> [i0, 0] : 0 < i0 <= 5 - p_2; |
573 | /// Stmt1[0] -> [0, 2] : p_1 = 1 and p_0 = -1; |
574 | /// Stmt1[0] -> [0, 2] : p_1 = 0 and p_0 = 0; |
575 | /// Stmt1[1 - p_1] -> [1 - p_1, 2] : p_0 = -1 and p_1 <= 0 and p_2 <= 4 + p_1; |
576 | /// Stmt1[-p_1] -> [-p_1, 2] : p_0 = 0 and p_1 < 0 and p_2 <= 5 + p_1; |
577 | /// Stmt2[0] -> [0, 1] : p_1 >= 3 + p_0; |
578 | /// Stmt2[0] -> [0, 1] : p_1 < p_0; |
579 | /// Stmt2[0] -> [0, 1] : p_1 = 1 + p_0; |
580 | /// Stmt2[0] -> [0, 1] : p_1 = 2 and p_0 = 0; |
581 | /// Stmt2[0] -> [0, 1] : p_1 = -1 and p_0 = -1; |
582 | /// Stmt2[i0] -> [i0, 1] : i0 >= 3 + p_0 - p_1 and 0 < i0 <= 5 - p_2; |
583 | /// Stmt2[i0] -> [i0, 1] : 0 < i0 <= 5 - p_2 and i0 < p_0 - p_1; |
584 | /// Stmt2[2 - p_1] -> [2 - p_1, 1] : p_0 = 0 and p_1 <= 1 and p_2 <= 3 + p_1; |
585 | /// Stmt3[0] -> [0, 3]; |
586 | /// Stmt3[i0] -> [i0, 3] : 0 < i0 <= 5 - p_2 |
587 | /// } |
588 | /// @{ |
589 | void dumpPw(const isl::set &Set); |
590 | void dumpPw(const isl::map &Map); |
591 | void dumpPw(const isl::union_set &USet); |
592 | void dumpPw(const isl::union_map &UMap); |
593 | void dumpPw(__isl_keep isl_set *Set); |
594 | void dumpPw(__isl_keep isl_map *Map); |
595 | void dumpPw(__isl_keep isl_union_set *USet); |
596 | void dumpPw(__isl_keep isl_union_map *UMap); |
597 | /// @} |
598 | |
599 | /// Dump all points of the argument to llvm::errs(). |
600 | /// |
601 | /// Before being printed by dumpPw(), the argument's pieces are expanded to |
602 | /// contain only single points. If a dimension is unbounded, it keeps its |
603 | /// representation. |
604 | /// |
605 | /// This is useful for debugging reduced cases where parameters are set to |
606 | /// constants to keep the example simple. Such sets can still contain |
607 | /// existential dimensions which makes the polyhedral hard to compare. |
608 | /// |
609 | /// Example: |
610 | /// { [MemRef_A[i0] -> [i1]] : (exists (e0 = floor((1 + i1)/3): i0 = 1 and 3e0 |
611 | /// <= i1 and 3e0 >= -1 + i1 and i1 >= 15 and i1 <= 25)) or (exists (e0 = |
612 | /// floor((i1)/3): i0 = 0 and 3e0 < i1 and 3e0 >= -2 + i1 and i1 > 0 and i1 <= |
613 | /// 11)) } |
614 | /// |
615 | /// dumpExpanded: |
616 | /// { |
617 | /// [MemRef_A[0] ->[1]]; |
618 | /// [MemRef_A[0] ->[2]]; |
619 | /// [MemRef_A[0] ->[4]]; |
620 | /// [MemRef_A[0] ->[5]]; |
621 | /// [MemRef_A[0] ->[7]]; |
622 | /// [MemRef_A[0] ->[8]]; |
623 | /// [MemRef_A[0] ->[10]]; |
624 | /// [MemRef_A[0] ->[11]]; |
625 | /// [MemRef_A[1] ->[15]]; |
626 | /// [MemRef_A[1] ->[16]]; |
627 | /// [MemRef_A[1] ->[18]]; |
628 | /// [MemRef_A[1] ->[19]]; |
629 | /// [MemRef_A[1] ->[21]]; |
630 | /// [MemRef_A[1] ->[22]]; |
631 | /// [MemRef_A[1] ->[24]]; |
632 | /// [MemRef_A[1] ->[25]] |
633 | /// } |
634 | /// @{ |
635 | void dumpExpanded(const isl::set &Set); |
636 | void dumpExpanded(const isl::map &Map); |
637 | void dumpExpanded(const isl::union_set &USet); |
638 | void dumpExpanded(const isl::union_map &UMap); |
639 | void dumpExpanded(__isl_keep isl_set *Set); |
640 | void dumpExpanded(__isl_keep isl_map *Map); |
641 | void dumpExpanded(__isl_keep isl_union_set *USet); |
642 | void dumpExpanded(__isl_keep isl_union_map *UMap); |
643 | /// @} |
644 | } // namespace polly |
645 | |
646 | #endif /* POLLY_ISLTOOLS_H */ |
647 | |