| blob | eb57bf581f45630bfe03a456415dfd95a3f0b933 |
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 //===----------------------------------------------------------------------===//
14 #ifndef POLLY_ISLTOOLS_H
15 #define POLLY_ISLTOOLS_H
27 struct isl_iterator
42 }
47 }
53 }
60 };
64 }
67 }
74 /// Return the range elements that are lexicographically smaller.
75 ///
76 /// @param Map { Space[] -> Scatter[] }
77 /// @param Strict True for strictly lexicographically smaller elements (exclude
78 /// same timepoints from the result).
79 ///
80 /// @return { Space[] -> Scatter[] }
81 /// A map to all timepoints that happen before the timepoints the input
82 /// mapped to.
85 /// Piecewise beforeScatter(isl::map,bool).
88 /// Return the range elements that are lexicographically larger.
89 ///
90 /// @param Map { Space[] -> Scatter[] }
91 /// @param Strict True for strictly lexicographically larger elements (exclude
92 /// same timepoints from the result).
93 ///
94 /// @return { Space[] -> Scatter[] }
95 /// A map to all timepoints that happen after the timepoints the input
96 /// map originally mapped to.
99 /// Piecewise afterScatter(isl::map,bool).
102 /// Construct a range of timepoints between two timepoints.
103 ///
104 /// Example:
105 /// From := { A[] -> [0]; B[] -> [0] }
106 /// To := { B[] -> [10]; C[] -> [20] }
107 ///
108 /// Result:
109 /// { B[] -> [i] : 0 < i < 10 }
110 ///
111 /// Note that A[] and C[] are not in the result because they do not have a start
112 /// or end timepoint. If a start (or end) timepoint is not unique, the first
113 /// (respectively last) is chosen.
114 ///
115 /// @param From { Space[] -> Scatter[] }
116 /// Map to start timepoints.
117 /// @param To { Space[] -> Scatter[] }
118 /// Map to end timepoints.
119 /// @param InclFrom Whether to include the start timepoints in the result. In
120 /// the example, this would add { B[] -> [0] }
121 /// @param InclTo Whether to include the end timepoints in the result. In this
122 /// example, this would add { B[] -> [10] }
123 ///
124 /// @return { Space[] -> Scatter[] }
125 /// A map for each domain element of timepoints between two extreme
126 /// points, or nullptr if @p From or @p To is nullptr, or the isl max
127 /// operations is exceeded.
130 /// Piecewise betweenScatter(isl::map,isl::map,bool,bool).
134 /// If by construction a union map is known to contain only a single map, return
135 /// it.
136 ///
137 /// This function combines isl_map_from_union_map() and
138 /// isl_union_map_extract_map(). isl_map_from_union_map() fails if the map is
139 /// empty because it does not know which space it would be in.
140 /// isl_union_map_extract_map() on the other hand does not check whether there
141 /// is (at most) one isl_map in the union, i.e. how it has been constructed is
142 /// probably wrong.
145 /// If by construction an isl_union_set is known to contain only a single
146 /// isl_set, return it.
147 ///
148 /// This function combines isl_set_from_union_set() and
149 /// isl_union_set_extract_set(). isl_map_from_union_set() fails if the set is
150 /// empty because it does not know which space it would be in.
151 /// isl_union_set_extract_set() on the other hand does not check whether there
152 /// is (at most) one isl_set in the union, i.e. how it has been constructed is
153 /// probably wrong.
156 /// Determine how many dimensions the scatter space of @p Schedule has.
157 ///
158 /// The schedule must not be empty and have equal number of dimensions of any
159 /// subspace it contains.
160 ///
161 /// The implementation currently returns the maximum number of dimensions it
162 /// encounters, if different, and 0 if none is encountered. However, most other
163 /// code will most likely fail if one of these happen.
166 /// Return the scatter space of a @p Schedule.
167 ///
168 /// This is basically the range space of the schedule map, but harder to
169 /// determine because it is an isl_union_map.
172 /// Construct an identity map for the given domain values.
173 ///
174 /// There is no type resembling isl_union_space, hence we have to pass an
175 /// isl_union_set as the map's domain and range space.
176 ///
177 /// @param USet { Space[] }
178 /// The returned map's domain and range.
179 /// @param RestrictDomain If true, the returned map only maps elements contained
180 /// in @p USet and no other. If false, it returns an
181 /// overapproximation with the identity maps of any space
182 /// in @p USet, not just the elements in it.
183 ///
184 /// @return { Space[] -> Space[] }
185 /// A map that maps each value of @p USet to itself.
188 /// Reverse the nested map tuple in @p Map's domain.
189 ///
190 /// @param Map { [Space1[] -> Space2[]] -> Space3[] }
191 ///
192 /// @return { [Space2[] -> Space1[]] -> Space3[] }
195 /// Piecewise reverseDomain(isl::map).
198 /// Add a constant to one dimension of a set.
199 ///
200 /// @param Map The set to shift a dimension in.
201 /// @param Pos The dimension to shift. If negative, the dimensions are
202 /// counted from the end instead from the beginning. E.g. -1 is
203 /// the last dimension in the tuple.
204 /// @param Amount The offset to add to the specified dimension.
205 ///
206 /// @return The modified set.
209 /// Piecewise shiftDim(isl::set,int,int).
212 /// Add a constant to one dimension of a map.
213 ///
214 /// @param Map The map to shift a dimension in.
215 /// @param Type A tuple of @p Map which contains the dimension to shift.
216 /// @param Pos The dimension to shift. If negative, the dimensions are
217 /// counted from the end instead from the beginning. Eg. -1 is the last
218 /// dimension in the tuple.
219 /// @param Amount The offset to add to the specified dimension.
220 ///
221 /// @return The modified map.
224 /// Add a constant to one dimension of a each map in a union map.
225 ///
226 /// @param UMap The maps to shift a dimension in.
227 /// @param Type The tuple which contains the dimension to shift.
228 /// @param Pos The dimension to shift. If negative, the dimensions are
229 /// counted from the ends of each map of union instead from their
230 /// beginning. E.g. -1 is the last dimension of any map.
231 /// @param Amount The offset to add to the specified dimension.
232 ///
233 /// @return The union of all modified maps.
236 /// Simplify a set inplace.
239 /// Simplify a union set inplace.
242 /// Simplify a map inplace.
245 /// Simplify a union map inplace.
248 /// Compute the reaching definition statement or the next overwrite for each
249 /// definition of an array element.
250 ///
251 /// The reaching definition of an array element at a specific timepoint is the
252 /// statement instance that has written the current element's content.
253 /// Alternatively, this function determines for each timepoint and element which
254 /// write is going to overwrite an element at a future timepoint. This can be
255 /// seen as "reaching definition in reverse" where definitions are found in the
256 /// past.
257 ///
258 /// For example:
259 ///
260 /// Schedule := { Write[] -> [0]; Overwrite[] -> [10] }
261 /// Defs := { Write[] -> A[5]; Overwrite[] -> A[5] }
262 ///
263 /// If index 5 of array A is written at timepoint 0 and 10, the resulting
264 /// reaching definitions are:
265 ///
266 /// { [A[5] -> [i]] -> Write[] : 0 < i < 10;
267 /// [A[5] -> [i]] -> Overwrite[] : 10 < i }
268 ///
269 /// Between timepoint 0 (Write[]) and timepoint 10 (Overwrite[]), the
270 /// content of A[5] is written by statement instance Write[] and after
271 /// timepoint 10 by Overwrite[]. Values not defined in the map have no known
272 /// definition. This includes the statement instance timepoints themselves,
273 /// because reads at those timepoints could either read the old or the new
274 /// value, defined only by the statement itself. But this can be changed by @p
275 /// InclPrevDef and @p InclNextDef. InclPrevDef=false and InclNextDef=true
276 /// returns a zone. Unless @p InclPrevDef and @p InclNextDef are both true,
277 /// there is only one unique definition per element and timepoint.
278 ///
279 /// @param Schedule { DomainWrite[] -> Scatter[] }
280 /// Schedule of (at least) all array writes. Instances not in
281 /// @p Writes are ignored.
282 /// @param Writes { DomainWrite[] -> Element[] }
283 /// Elements written to by the statement instances.
284 /// @param Reverse If true, look for definitions in the future. That is,
285 /// find the write that is overwrites the current value.
286 /// @param InclPrevDef Include the definition's timepoint to the set of
287 /// well-defined elements (any load at that timepoint happen
288 /// at the writes). In the example, enabling this option adds
289 /// {[A[5] -> [0]] -> Write[]; [A[5] -> [10]] -> Overwrite[]}
290 /// to the result.
291 /// @param InclNextDef Whether to assume that at the timepoint where an element
292 /// is overwritten, it still contains the old value (any load
293 /// at that timepoint would happen before the overwrite). In
294 /// this example, enabling this adds
295 /// { [A[] -> [10]] -> Write[] } to the result.
296 ///
297 /// @return { [Element[] -> Scatter[]] -> DomainWrite[] }
298 /// The reaching definitions or future overwrite as described above, or
299 /// nullptr if either @p Schedule or @p Writes is nullptr, or the isl
300 /// max operations count has exceeded.
305 /// Compute the timepoints where the contents of an array element are not used.
306 ///
307 /// An element is unused at a timepoint when the element is overwritten in
308 /// the future, but it is not read in between. Another way to express this: the
309 /// time from when the element is written, to the most recent read before it, or
310 /// infinitely into the past if there is no read before. Such unused elements
311 /// can be overwritten by any value without changing the scop's semantics. An
312 /// example:
313 ///
314 /// Schedule := { Read[] -> [0]; Write[] -> [10]; Def[] -> [20] }
315 /// Writes := { Write[] -> A[5]; Def[] -> A[6] }
316 /// Reads := { Read[] -> A[5] }
317 ///
318 /// The result is:
319 ///
320 /// { A[5] -> [i] : 0 < i < 10;
321 /// A[6] -> [i] : i < 20 }
322 ///
323 /// That is, A[5] is unused between timepoint 0 (the read) and timepoint 10 (the
324 /// write). A[6] is unused before timepoint 20, but might be used after the
325 /// scop's execution (A[5] and any other A[i] as well). Use InclLastRead=false
326 /// and InclWrite=true to interpret the result as zone.
327 ///
328 /// @param Schedule { Domain[] -> Scatter[] }
329 /// The schedule of (at least) all statement instances
330 /// occurring in @p Writes or @p Reads. All other
331 /// instances are ignored.
332 /// @param Writes { DomainWrite[] -> Element[] }
333 /// Elements written to by the statement instances.
334 /// @param Reads { DomainRead[] -> Element[] }
335 /// Elements read from by the statement instances.
336 /// @param ReadEltInSameInst Whether a load reads the value from a write
337 /// that is scheduled at the same timepoint (Writes
338 /// happen before reads). Otherwise, loads use the
339 /// value of an element that it had before the
340 /// timepoint (Reads before writes). For example:
341 /// { Read[] -> [0]; Write[] -> [0] }
342 /// With ReadEltInSameInst=false it is assumed that the
343 /// read happens before the write, such that the
344 /// element is never unused, or just at timepoint 0,
345 /// depending on InclLastRead/InclWrite.
346 /// With ReadEltInSameInst=false it assumes that the
347 /// value just written is used. Anything before
348 /// timepoint 0 is considered unused.
349 /// @param InclLastRead Whether a timepoint where an element is last read
350 /// counts as unused (the read happens at the beginning
351 /// of its timepoint, and nothing (else) can use it
352 /// during the timepoint). In the example, this option
353 /// adds { A[5] -> [0] } to the result.
354 /// @param InclWrite Whether the timepoint where an element is written
355 /// itself counts as unused (the write happens at the
356 /// end of its timepoint; no (other) operations uses
357 /// the element during the timepoint). In this example,
358 /// this adds
359 /// { A[5] -> [10]; A[6] -> [20] } to the result.
360 ///
361 /// @return { Element[] -> Scatter[] }
362 /// The unused timepoints as defined above, or nullptr if either @p
363 /// Schedule, @p Writes are @p Reads is nullptr, or the ISL max
364 /// operations count is exceeded.
370 /// Convert a zone (range between timepoints) to timepoints.
371 ///
372 /// A zone represents the time between (integer) timepoints, but not the
373 /// timepoints themselves. This function can be used to determine whether a
374 /// timepoint lies within a zone.
375 ///
376 /// For instance, the range (1,3), representing the time between 1 and 3, is
377 /// represented by the zone
378 ///
379 /// { [i] : 1 < i <= 3 }
380 ///
381 /// The set of timepoints that lie completely within this range is
382 ///
383 /// { [i] : 1 < i < 3 }
384 ///
385 /// A typical use-case is the range in which a value written by a store is
386 /// available until it is overwritten by another value. If the write is at
387 /// timepoint 1 and its value is overwritten by another value at timepoint 3,
388 /// the value is available between those timepoints: timepoint 2 in this
389 /// example.
390 ///
391 ///
392 /// When InclStart is true, the range is interpreted left-inclusive, i.e. adds
393 /// the timepoint 1 to the result:
394 ///
395 /// { [i] : 1 <= i < 3 }
396 ///
397 /// In the use-case mentioned above that means that the value written at
398 /// timepoint 1 is already available in timepoint 1 (write takes place before
399 /// any read of it even if executed at the same timepoint)
400 ///
401 /// When InclEnd is true, the range is interpreted right-inclusive, i.e. adds
402 /// the timepoint 3 to the result:
403 ///
404 /// { [i] : 1 < i <= 3 }
405 ///
406 /// In the use-case mentioned above that means that although the value is
407 /// overwritten in timepoint 3, the old value is still available at timepoint 3
408 /// (write takes place after any read even if executed at the same timepoint)
409 ///
410 /// @param Zone { Zone[] }
411 /// @param InclStart Include timepoints adjacent to the beginning of a zone.
412 /// @param InclEnd Include timepoints adjacent to the ending of a zone.
413 ///
414 /// @return { Scatter[] }
418 /// Like convertZoneToTimepoints(isl::union_set,InclStart,InclEnd), but convert
419 /// either the domain or the range of a map.
423 /// Overload of convertZoneToTimepoints(isl::map,InclStart,InclEnd) to process
424 /// only a single map.
428 /// Distribute the domain to the tuples of a wrapped range map.
429 ///
430 /// @param Map { Domain[] -> [Range1[] -> Range2[]] }
431 ///
432 /// @return { [Domain[] -> Range1[]] -> [Domain[] -> Range2[]] }
435 /// Apply distributeDomain(isl::map) to each map in the union.
438 /// Prepend a space to the tuples of a map.
439 ///
440 /// @param UMap { Domain[] -> Range[] }
441 /// @param Factor { Factor[] }
442 ///
443 /// @return { [Factor[] -> Domain[]] -> [Factor[] -> Range[]] }
446 /// Apply a map to the 'middle' of another relation.
447 ///
448 /// @param UMap { [DomainDomain[] -> DomainRange[]] -> Range[] }
449 /// @param Func { DomainRange[] -> NewDomainRange[] }
450 ///
451 /// @return { [DomainDomain[] -> NewDomainRange[]] -> Range[] }
454 /// Intersect the range of @p Map with @p Range.
455 ///
456 /// Since @p Map is an isl::map, the result will be a single space, even though
457 /// @p Range is an isl::union_set. This is the only difference to
458 /// isl::map::intersect_range and isl::union_map::interset_range.
459 ///
460 /// @param Map { Domain[] -> Range[] }
461 /// @param Range { Range[] }
462 ///
463 /// @return { Domain[] -> Range[] }
466 /// Subtract the parameter space @p Params from @p Map.
467 /// This is akin to isl::map::intersect_params.
468 ///
469 /// Example:
470 /// subtractParams(
471 /// { [i] -> [i] },
472 /// [x] -> { : x < 0 }
473 /// ) = [x] -> { [i] -> [i] : x >= 0 }
474 ///
475 /// @param Map Remove the conditions of @p Params from this map.
476 /// @param Params Parameter set to subtract.
477 ///
478 /// @param The map with the parameter conditions removed.
481 /// If @p PwAff maps to a constant, return said constant. If @p Max/@p Min, it
482 /// can also be a piecewise constant and it would return the minimum/maximum
483 /// value. Otherwise, return NaN.
486 /// Dump a description of the argument to llvm::errs().
487 ///
488 /// In contrast to isl's dump function, there are a few differences:
489 /// - Each polyhedron (pieces) is written on its own line.
490 /// - Spaces are sorted by structure. E.g. maps with same domain space are
491 /// grouped. Isl sorts them according to the space's hash function.
492 /// - Pieces of the same space are sorted using their lower bound.
493 /// - A more compact to_str representation is used instead of Isl's dump
494 /// functions that try to show the internal representation.
495 ///
496 /// The goal is to get a better understandable representation that is also
497 /// useful to compare two sets. As all dump() functions, its intended use is to
498 /// be called in a debugger only.
499 ///
500 /// isl_map_dump example:
501 /// [p_0, p_1, p_2] -> { Stmt0[i0] -> [o0, o1] : (o0 = i0 and o1 = 0 and i0 > 0
502 /// and i0 <= 5 - p_2) or (i0 = 0 and o0 = 0 and o1 = 0); Stmt3[i0] -> [o0, o1]
503 /// : (o0 = i0 and o1 = 3 and i0 > 0 and i0 <= 5 - p_2) or (i0 = 0 and o0 = 0
504 /// and o1 = 3); Stmt2[i0] -> [o0, o1] : (o0 = i0 and o1 = 1 and i0 >= 3 + p_0 -
505 /// p_1 and i0 > 0 and i0 <= 5 - p_2) or (o0 = i0 and o1 = 1 and i0 > 0 and i0
506 /// <= 5 - p_2 and i0 < p_0 - p_1) or (i0 = 0 and o0 = 0 and o1 = 1 and p_1 >= 3
507 /// + p_0) or (i0 = 0 and o0 = 0 and o1 = 1 and p_1 < p_0) or (p_0 = 0 and i0 =
508 /// 2 - p_1 and o0 = 2 - p_1 and o1 = 1 and p_2 <= 3 + p_1 and p_1 <= 1) or (p_1
509 /// = 1 + p_0 and i0 = 0 and o0 = 0 and o1 = 1) or (p_0 = 0 and p_1 = 2 and i0 =
510 /// 0 and o0 = 0 and o1 = 1) or (p_0 = -1 and p_1 = -1 and i0 = 0 and o0 = 0 and
511 /// o1 = 1); Stmt1[i0] -> [o0, o1] : (p_0 = -1 and i0 = 1 - p_1 and o0 = 1 - p_1
512 /// and o1 = 2 and p_2 <= 4 + p_1 and p_1 <= 0) or (p_0 = 0 and i0 = -p_1 and o0
513 /// = -p_1 and o1 = 2 and p_2 <= 5 + p_1 and p_1 < 0) or (p_0 = -1 and p_1 = 1
514 /// and i0 = 0 and o0 = 0 and o1 = 2) or (p_0 = 0 and p_1 = 0 and i0 = 0 and o0
515 /// = 0 and o1 = 2) }
516 ///
517 /// dumpPw example (same set):
518 /// [p_0, p_1, p_2] -> {
519 /// Stmt0[0] -> [0, 0];
520 /// Stmt0[i0] -> [i0, 0] : 0 < i0 <= 5 - p_2;
521 /// Stmt1[0] -> [0, 2] : p_1 = 1 and p_0 = -1;
522 /// Stmt1[0] -> [0, 2] : p_1 = 0 and p_0 = 0;
523 /// Stmt1[1 - p_1] -> [1 - p_1, 2] : p_0 = -1 and p_1 <= 0 and p_2 <= 4 + p_1;
524 /// Stmt1[-p_1] -> [-p_1, 2] : p_0 = 0 and p_1 < 0 and p_2 <= 5 + p_1;
525 /// Stmt2[0] -> [0, 1] : p_1 >= 3 + p_0;
526 /// Stmt2[0] -> [0, 1] : p_1 < p_0;
527 /// Stmt2[0] -> [0, 1] : p_1 = 1 + p_0;
528 /// Stmt2[0] -> [0, 1] : p_1 = 2 and p_0 = 0;
529 /// Stmt2[0] -> [0, 1] : p_1 = -1 and p_0 = -1;
530 /// Stmt2[i0] -> [i0, 1] : i0 >= 3 + p_0 - p_1 and 0 < i0 <= 5 - p_2;
531 /// Stmt2[i0] -> [i0, 1] : 0 < i0 <= 5 - p_2 and i0 < p_0 - p_1;
532 /// Stmt2[2 - p_1] -> [2 - p_1, 1] : p_0 = 0 and p_1 <= 1 and p_2 <= 3 + p_1;
533 /// Stmt3[0] -> [0, 3];
534 /// Stmt3[i0] -> [i0, 3] : 0 < i0 <= 5 - p_2
535 /// }
536 /// @{
545 /// @}
547 /// Dump all points of the argument to llvm::errs().
548 ///
549 /// Before being printed by dumpPw(), the argument's pieces are expanded to
550 /// contain only single points. If a dimension is unbounded, it keeps its
551 /// representation.
552 ///
553 /// This is useful for debugging reduced cases where parameters are set to
554 /// constants to keep the example simple. Such sets can still contain
555 /// existential dimensions which makes the polyhedral hard to compare.
556 ///
557 /// Example:
558 /// { [MemRef_A[i0] -> [i1]] : (exists (e0 = floor((1 + i1)/3): i0 = 1 and 3e0
559 /// <= i1 and 3e0 >= -1 + i1 and i1 >= 15 and i1 <= 25)) or (exists (e0 =
560 /// floor((i1)/3): i0 = 0 and 3e0 < i1 and 3e0 >= -2 + i1 and i1 > 0 and i1 <=
561 /// 11)) }
562 ///
563 /// dumpExpanded:
564 /// {
565 /// [MemRef_A[0] ->[1]];
566 /// [MemRef_A[0] ->[2]];
567 /// [MemRef_A[0] ->[4]];
568 /// [MemRef_A[0] ->[5]];
569 /// [MemRef_A[0] ->[7]];
570 /// [MemRef_A[0] ->[8]];
571 /// [MemRef_A[0] ->[10]];
572 /// [MemRef_A[0] ->[11]];
573 /// [MemRef_A[1] ->[15]];
574 /// [MemRef_A[1] ->[16]];
575 /// [MemRef_A[1] ->[18]];
576 /// [MemRef_A[1] ->[19]];
577 /// [MemRef_A[1] ->[21]];
578 /// [MemRef_A[1] ->[22]];
579 /// [MemRef_A[1] ->[24]];
580 /// [MemRef_A[1] ->[25]]
581 /// }
582 /// @{
591 /// @}