Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/include/polly/Support/ISLTools.h
Line
Count
Source
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/iterator.h"
18
#include "isl/isl-noexceptions.h"
19
20
namespace isl {
21
inline namespace noexceptions {
22
23
template <typename ListT>
24
using list_element_type = decltype(std::declval<ListT>().get_at(0));
25
26
template <typename ListT>
27
struct isl_iterator
28
    : public llvm::iterator_facade_base<isl_iterator<ListT>,
29
                                        std::forward_iterator_tag,
30
                                        list_element_type<ListT>> {
31
32
  using ElementT = list_element_type<ListT>;
33
34
  explicit isl_iterator(const ListT &List)
35
9.49k
      : List(&List), Position(List.size()) {}
isl::noexceptions::isl_iterator<isl::noexceptions::set_list>::isl_iterator(isl::noexceptions::set_list const&)
Line
Count
Source
35
2.88k
      : List(&List), Position(List.size()) {}
isl::noexceptions::isl_iterator<isl::noexceptions::basic_set_list>::isl_iterator(isl::noexceptions::basic_set_list const&)
Line
Count
Source
35
2.11k
      : List(&List), Position(List.size()) {}
isl::noexceptions::isl_iterator<isl::noexceptions::ast_node_list>::isl_iterator(isl::noexceptions::ast_node_list const&)
Line
Count
Source
35
2
      : List(&List), Position(List.size()) {}
isl::noexceptions::isl_iterator<isl::noexceptions::map_list>::isl_iterator(isl::noexceptions::map_list const&)
Line
Count
Source
35
4.27k
      : List(&List), Position(List.size()) {}
isl::noexceptions::isl_iterator<isl::noexceptions::basic_map_list>::isl_iterator(isl::noexceptions::basic_map_list const&)
Line
Count
Source
35
216
      : List(&List), Position(List.size()) {}
36
  isl_iterator(const ListT &List, int Position)
37
9.49k
      : List(&List), Position(Position) {}
isl::noexceptions::isl_iterator<isl::noexceptions::set_list>::isl_iterator(isl::noexceptions::set_list const&, int)
Line
Count
Source
37
2.88k
      : List(&List), Position(Position) {}
isl::noexceptions::isl_iterator<isl::noexceptions::basic_set_list>::isl_iterator(isl::noexceptions::basic_set_list const&, int)
Line
Count
Source
37
2.11k
      : List(&List), Position(Position) {}
isl::noexceptions::isl_iterator<isl::noexceptions::ast_node_list>::isl_iterator(isl::noexceptions::ast_node_list const&, int)
Line
Count
Source
37
2
      : List(&List), Position(Position) {}
isl::noexceptions::isl_iterator<isl::noexceptions::map_list>::isl_iterator(isl::noexceptions::map_list const&, int)
Line
Count
Source
37
4.27k
      : List(&List), Position(Position) {}
isl::noexceptions::isl_iterator<isl::noexceptions::basic_map_list>::isl_iterator(isl::noexceptions::basic_map_list const&, int)
Line
Count
Source
37
216
      : List(&List), Position(Position) {}
38
  isl_iterator &operator=(const isl_iterator &R) = default;
39
40
24.0k
  bool operator==(const isl_iterator &O) const {
41
24.0k
    return List == O.List && Position == O.Position;
42
24.0k
  }
isl::noexceptions::isl_iterator<isl::noexceptions::set_list>::operator==(isl::noexceptions::isl_iterator<isl::noexceptions::set_list> const&) const
Line
Count
Source
40
6.88k
  bool operator==(const isl_iterator &O) const {
41
6.88k
    return List == O.List && Position == O.Position;
42
6.88k
  }
isl::noexceptions::isl_iterator<isl::noexceptions::basic_set_list>::operator==(isl::noexceptions::isl_iterator<isl::noexceptions::basic_set_list> const&) const
Line
Count
Source
40
4.90k
  bool operator==(const isl_iterator &O) const {
41
4.90k
    return List == O.List && Position == O.Position;
42
4.90k
  }
isl::noexceptions::isl_iterator<isl::noexceptions::ast_node_list>::operator==(isl::noexceptions::isl_iterator<isl::noexceptions::ast_node_list> const&) const
Line
Count
Source
40
4
  bool operator==(const isl_iterator &O) const {
41
4
    return List == O.List && Position == O.Position;
42
4
  }
isl::noexceptions::isl_iterator<isl::noexceptions::map_list>::operator==(isl::noexceptions::isl_iterator<isl::noexceptions::map_list> const&) const
Line
Count
Source
40
11.9k
  bool operator==(const isl_iterator &O) const {
41
11.9k
    return List == O.List && Position == O.Position;
42
11.9k
  }
isl::noexceptions::isl_iterator<isl::noexceptions::basic_map_list>::operator==(isl::noexceptions::isl_iterator<isl::noexceptions::basic_map_list> const&) const
Line
Count
Source
40
304
  bool operator==(const isl_iterator &O) const {
41
304
    return List == O.List && Position == O.Position;
42
304
  }
43
44
14.5k
  isl_iterator &operator++() {
45
14.5k
    ++Position;
46
14.5k
    return *this;
47
14.5k
  }
isl::noexceptions::isl_iterator<isl::noexceptions::set_list>::operator++()
Line
Count
Source
44
4.00k
  isl_iterator &operator++() {
45
4.00k
    ++Position;
46
4.00k
    return *this;
47
4.00k
  }
isl::noexceptions::isl_iterator<isl::noexceptions::basic_set_list>::operator++()
Line
Count
Source
44
2.79k
  isl_iterator &operator++() {
45
2.79k
    ++Position;
46
2.79k
    return *this;
47
2.79k
  }
isl::noexceptions::isl_iterator<isl::noexceptions::ast_node_list>::operator++()
Line
Count
Source
44
2
  isl_iterator &operator++() {
45
2
    ++Position;
46
2
    return *this;
47
2
  }
isl::noexceptions::isl_iterator<isl::noexceptions::map_list>::operator++()
Line
Count
Source
44
7.68k
  isl_iterator &operator++() {
45
7.68k
    ++Position;
46
7.68k
    return *this;
47
7.68k
  }
isl::noexceptions::isl_iterator<isl::noexceptions::basic_map_list>::operator++()
Line
Count
Source
44
88
  isl_iterator &operator++() {
45
88
    ++Position;
46
88
    return *this;
47
88
  }
48
49
  isl_iterator operator++(int) {
50
    isl_iterator Copy{*this};
51
    ++Position;
52
    return Copy;
53
  }
54
55
14.8k
  ElementT operator*() const { return List->get_at(this->Position); }
isl::noexceptions::isl_iterator<isl::noexceptions::set_list>::operator*() const
Line
Count
Source
55
4.00k
  ElementT operator*() const { return List->get_at(this->Position); }
isl::noexceptions::isl_iterator<isl::noexceptions::basic_set_list>::operator*() const
Line
Count
Source
55
2.79k
  ElementT operator*() const { return List->get_at(this->Position); }
isl::noexceptions::isl_iterator<isl::noexceptions::ast_node_list>::operator*() const
Line
Count
Source
55
3
  ElementT operator*() const { return List->get_at(this->Position); }
isl::noexceptions::isl_iterator<isl::noexceptions::map_list>::operator*() const
Line
Count
Source
55
7.80k
  ElementT operator*() const { return List->get_at(this->Position); }
isl::noexceptions::isl_iterator<isl::noexceptions::basic_map_list>::operator*() const
Line
Count
Source
55
234
  ElementT operator*() const { return List->get_at(this->Position); }
56
57
protected:
58
  const ListT *List;
59
  int Position = 0;
60
};
61
62
9.49k
template <typename T> isl_iterator<T> begin(const T &t) {
63
9.49k
  return isl_iterator<T>(t, 0);
64
9.49k
}
isl::noexceptions::isl_iterator<isl::noexceptions::set_list> isl::noexceptions::begin<isl::noexceptions::set_list>(isl::noexceptions::set_list const&)
Line
Count
Source
62
2.88k
template <typename T> isl_iterator<T> begin(const T &t) {
63
2.88k
  return isl_iterator<T>(t, 0);
64
2.88k
}
isl::noexceptions::isl_iterator<isl::noexceptions::basic_set_list> isl::noexceptions::begin<isl::noexceptions::basic_set_list>(isl::noexceptions::basic_set_list const&)
Line
Count
Source
62
2.11k
template <typename T> isl_iterator<T> begin(const T &t) {
63
2.11k
  return isl_iterator<T>(t, 0);
64
2.11k
}
isl::noexceptions::isl_iterator<isl::noexceptions::ast_node_list> isl::noexceptions::begin<isl::noexceptions::ast_node_list>(isl::noexceptions::ast_node_list const&)
Line
Count
Source
62
2
template <typename T> isl_iterator<T> begin(const T &t) {
63
2
  return isl_iterator<T>(t, 0);
64
2
}
isl::noexceptions::isl_iterator<isl::noexceptions::map_list> isl::noexceptions::begin<isl::noexceptions::map_list>(isl::noexceptions::map_list const&)
Line
Count
Source
62
4.27k
template <typename T> isl_iterator<T> begin(const T &t) {
63
4.27k
  return isl_iterator<T>(t, 0);
64
4.27k
}
isl::noexceptions::isl_iterator<isl::noexceptions::basic_map_list> isl::noexceptions::begin<isl::noexceptions::basic_map_list>(isl::noexceptions::basic_map_list const&)
Line
Count
Source
62
216
template <typename T> isl_iterator<T> begin(const T &t) {
63
216
  return isl_iterator<T>(t, 0);
64
216
}
65
9.49k
template <typename T> isl_iterator<T> end(const T &t) {
66
9.49k
  return isl_iterator<T>(t);
67
9.49k
}
isl::noexceptions::isl_iterator<isl::noexceptions::set_list> isl::noexceptions::end<isl::noexceptions::set_list>(isl::noexceptions::set_list const&)
Line
Count
Source
65
2.88k
template <typename T> isl_iterator<T> end(const T &t) {
66
2.88k
  return isl_iterator<T>(t);
67
2.88k
}
isl::noexceptions::isl_iterator<isl::noexceptions::basic_set_list> isl::noexceptions::end<isl::noexceptions::basic_set_list>(isl::noexceptions::basic_set_list const&)
Line
Count
Source
65
2.11k
template <typename T> isl_iterator<T> end(const T &t) {
66
2.11k
  return isl_iterator<T>(t);
67
2.11k
}
isl::noexceptions::isl_iterator<isl::noexceptions::ast_node_list> isl::noexceptions::end<isl::noexceptions::ast_node_list>(isl::noexceptions::ast_node_list const&)
Line
Count
Source
65
2
template <typename T> isl_iterator<T> end(const T &t) {
66
2
  return isl_iterator<T>(t);
67
2
}
isl::noexceptions::isl_iterator<isl::noexceptions::map_list> isl::noexceptions::end<isl::noexceptions::map_list>(isl::noexceptions::map_list const&)
Line
Count
Source
65
4.27k
template <typename T> isl_iterator<T> end(const T &t) {
66
4.27k
  return isl_iterator<T>(t);
67
4.27k
}
isl::noexceptions::isl_iterator<isl::noexceptions::basic_map_list> isl::noexceptions::end<isl::noexceptions::basic_map_list>(isl::noexceptions::basic_map_list const&)
Line
Count
Source
65
216
template <typename T> isl_iterator<T> end(const T &t) {
66
216
  return isl_iterator<T>(t);
67
216
}
68
69
} // namespace noexceptions
70
} // namespace isl
71
72
namespace polly {
73
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.
83
isl::map beforeScatter(isl::map Map, bool Strict);
84
85
/// Piecewise beforeScatter(isl::map,bool).
86
isl::union_map beforeScatter(isl::union_map UMap, bool Strict);
87
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.
97
isl::map afterScatter(isl::map Map, bool Strict);
98
99
/// Piecewise afterScatter(isl::map,bool).
100
isl::union_map afterScatter(const isl::union_map &UMap, bool Strict);
101
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.
128
isl::map betweenScatter(isl::map From, isl::map To, bool InclFrom, bool InclTo);
129
130
/// Piecewise betweenScatter(isl::map,isl::map,bool,bool).
131
isl::union_map betweenScatter(isl::union_map From, isl::union_map To,
132
                              bool InclFrom, bool InclTo);
133
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.
143
isl::map singleton(isl::union_map UMap, isl::space ExpectedSpace);
144
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.
154
isl::set singleton(isl::union_set USet, isl::space ExpectedSpace);
155
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.
164
unsigned getNumScatterDims(const isl::union_map &Schedule);
165
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.
170
isl::space getScatterSpace(const isl::union_map &Schedule);
171
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.
186
isl::union_map makeIdentityMap(const isl::union_set &USet, bool RestrictDomain);
187
188
/// Reverse the nested map tuple in @p Map's domain.
189
///
190
/// @param Map { [Space1[] -> Space2[]] -> Space3[] }
191
///
192
/// @return { [Space2[] -> Space1[]] -> Space3[] }
193
isl::map reverseDomain(isl::map Map);
194
195
/// Piecewise reverseDomain(isl::map).
196
isl::union_map reverseDomain(const isl::union_map &UMap);
197
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.
207
isl::set shiftDim(isl::set Set, int Pos, int Amount);
208
209
/// Piecewise shiftDim(isl::set,int,int).
210
isl::union_set shiftDim(isl::union_set USet, int Pos, int Amount);
211
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.
222
isl::map shiftDim(isl::map Map, isl::dim Dim, int Pos, int Amount);
223
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.
234
isl::union_map shiftDim(isl::union_map UMap, isl::dim Dim, int Pos, int Amount);
235
236
/// Simplify a set inplace.
237
void simplify(isl::set &Set);
238
239
/// Simplify a union set inplace.
240
void simplify(isl::union_set &USet);
241
242
/// Simplify a map inplace.
243
void simplify(isl::map &Map);
244
245
/// Simplify a union map inplace.
246
void simplify(isl::union_map &UMap);
247
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.
301
isl::union_map computeReachingWrite(isl::union_map Schedule,
302
                                    isl::union_map Writes, bool Reverse,
303
                                    bool InclPrevDef, bool InclNextDef);
304
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.
365
isl::union_map computeArrayUnused(isl::union_map Schedule,
366
                                  isl::union_map Writes, isl::union_map Reads,
367
                                  bool ReadEltInSameInst, bool InclLastRead,
368
                                  bool InclWrite);
369
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[] }
415
isl::union_set convertZoneToTimepoints(isl::union_set Zone, bool InclStart,
416
                                       bool InclEnd);
417
418
/// Like convertZoneToTimepoints(isl::union_set,InclStart,InclEnd), but convert
419
/// either the domain or the range of a map.
420
isl::union_map convertZoneToTimepoints(isl::union_map Zone, isl::dim Dim,
421
                                       bool InclStart, bool InclEnd);
422
423
/// Overload of convertZoneToTimepoints(isl::map,InclStart,InclEnd) to process
424
/// only a single map.
425
isl::map convertZoneToTimepoints(isl::map Zone, isl::dim Dim, bool InclStart,
426
                                 bool InclEnd);
427
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[]] }
433
isl::map distributeDomain(isl::map Map);
434
435
/// Apply distributeDomain(isl::map) to each map in the union.
436
isl::union_map distributeDomain(isl::union_map UMap);
437
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[]] }
444
isl::union_map liftDomains(isl::union_map UMap, isl::union_set Factor);
445
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[] }
452
isl::union_map applyDomainRange(isl::union_map UMap, isl::union_map Func);
453
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[] }
464
isl::map intersectRange(isl::map Map, isl::union_set Range);
465
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.
479
isl::map subtractParams(isl::map Map, isl::set Params);
480
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.
484
isl::val getConstant(isl::pw_aff PwAff, bool Max, bool Min);
485
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
/// @{
537
void dumpPw(const isl::set &Set);
538
void dumpPw(const isl::map &Map);
539
void dumpPw(const isl::union_set &USet);
540
void dumpPw(const isl::union_map &UMap);
541
void dumpPw(__isl_keep isl_set *Set);
542
void dumpPw(__isl_keep isl_map *Map);
543
void dumpPw(__isl_keep isl_union_set *USet);
544
void dumpPw(__isl_keep isl_union_map *UMap);
545
/// @}
546
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
/// @{
583
void dumpExpanded(const isl::set &Set);
584
void dumpExpanded(const isl::map &Map);
585
void dumpExpanded(const isl::union_set &USet);
586
void dumpExpanded(const isl::union_map &UMap);
587
void dumpExpanded(__isl_keep isl_set *Set);
588
void dumpExpanded(__isl_keep isl_map *Map);
589
void dumpExpanded(__isl_keep isl_union_set *USet);
590
void dumpExpanded(__isl_keep isl_union_map *UMap);
591
/// @}
592
} // namespace polly
593
594
#endif /* POLLY_ISLTOOLS_H */