/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 */ |