Coverage Report

Created: 2018-07-12 09:57

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