1 | //===- PresburgerSpace.h - MLIR PresburgerSpace Class -----------*- 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 | // Classes representing space information like number of variables and kind of |
10 | // variables. |
11 | // |
12 | //===----------------------------------------------------------------------===// |
13 | |
14 | #ifndef MLIR_ANALYSIS_PRESBURGER_PRESBURGERSPACE_H |
15 | #define MLIR_ANALYSIS_PRESBURGER_PRESBURGERSPACE_H |
16 | |
17 | #include "mlir/Support/TypeID.h" |
18 | #include "llvm/ADT/ArrayRef.h" |
19 | #include "llvm/Support/ErrorHandling.h" |
20 | #include "llvm/Support/PointerLikeTypeTraits.h" |
21 | #include "llvm/Support/raw_ostream.h" |
22 | |
23 | namespace mlir { |
24 | namespace presburger { |
25 | |
26 | /// Kind of variable. Implementation wise SetDims are treated as Range |
27 | /// vars, and spaces with no distinction between dimension vars are treated |
28 | /// as relations with zero domain vars. |
29 | enum class VarKind { Symbol, Local, Domain, Range, SetDim = Range }; |
30 | |
31 | /// An Identifier stores a pointer to an object, such as a Value or an |
32 | /// Operation. Identifiers are intended to be attached to a variable in a |
33 | /// PresburgerSpace and can be used to check if two variables correspond to the |
34 | /// same object. |
35 | /// |
36 | /// Take for example the following code: |
37 | /// |
38 | /// for i = 0 to 100 |
39 | /// for j = 0 to 100 |
40 | /// S0: A[j] = 0 |
41 | /// for k = 0 to 100 |
42 | /// S1: A[k] = 1 |
43 | /// |
44 | /// If we represent the space of iteration variables surrounding S0, S1 we have: |
45 | /// space(S0): {d0, d1} |
46 | /// space(S1): {d0, d1} |
47 | /// |
48 | /// Since the variables are in different spaces, without an identifier, there |
49 | /// is no way to distinguish if the variables in the two spaces correspond to |
50 | /// different SSA values in the program. So, we attach an Identifier |
51 | /// corresponding to the loop iteration variable to them. Now, |
52 | /// |
53 | /// space(S0) = {d0(id = i), d1(id = j)} |
54 | /// space(S1) = {d0(id = i), d1(id = k)}. |
55 | /// |
56 | /// Using the identifier, we can check that the first iteration variable in |
57 | /// both the spaces correspond to the same variable in the program, while they |
58 | /// are different for second iteration variable. |
59 | /// |
60 | /// The equality of Identifiers is checked by comparing the stored pointers. |
61 | /// Checking equality asserts that the type of the equal identifiers is same. |
62 | /// Identifiers storing null pointers are treated as having no attachment and |
63 | /// are considered unequal to any other identifier, including other identifiers |
64 | /// with no attachments. |
65 | /// |
66 | /// The type of the pointer stored must have an `llvm::PointerLikeTypeTraits` |
67 | /// specialization. |
68 | class Identifier { |
69 | public: |
70 | Identifier() = default; |
71 | |
72 | // Create an identifier from a pointer. |
73 | template <typename T> |
74 | explicit Identifier(T value) |
75 | : value(llvm::PointerLikeTypeTraits<T>::getAsVoidPointer(value)) { |
76 | #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS |
77 | idType = TypeID::get<T>(); |
78 | #endif |
79 | } |
80 | |
81 | /// Get the value of the identifier casted to type `T`. `T` here should match |
82 | /// the type of the identifier used to create it. |
83 | template <typename T> |
84 | T getValue() const { |
85 | #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS |
86 | assert(TypeID::get<T>() == idType && |
87 | "Identifier was initialized with a different type than the one used " |
88 | "to retrieve it." ); |
89 | #endif |
90 | return llvm::PointerLikeTypeTraits<T>::getFromVoidPointer(value); |
91 | } |
92 | |
93 | bool hasValue() const { return value != nullptr; } |
94 | |
95 | /// Check if the two identifiers are equal. Null identifiers are considered |
96 | /// not equal. Asserts if two identifiers are equal but their types are not. |
97 | bool isEqual(const Identifier &other) const; |
98 | |
99 | bool operator==(const Identifier &other) const { return isEqual(other); } |
100 | bool operator!=(const Identifier &other) const { return !isEqual(other); } |
101 | |
102 | void print(llvm::raw_ostream &os) const; |
103 | void dump() const; |
104 | |
105 | private: |
106 | /// The value of the identifier. |
107 | void *value = nullptr; |
108 | |
109 | #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS |
110 | /// TypeID of the identifiers in space. This should be used in asserts only. |
111 | TypeID idType = TypeID::get<void>(); |
112 | #endif |
113 | }; |
114 | |
115 | /// PresburgerSpace is the space of all possible values of a tuple of integer |
116 | /// valued variables/variables. Each variable has one of the three types: |
117 | /// |
118 | /// Dimension: Ordinary variables over which the space is represented. |
119 | /// |
120 | /// Symbol: Symbol variables correspond to fixed but unknown values. |
121 | /// Mathematically, a space with symbolic variables is like a |
122 | /// family of spaces indexed by the symbolic variables. |
123 | /// |
124 | /// Local: Local variables correspond to existentially quantified variables. |
125 | /// For example, consider the space: `(x, exists q)` where x is a dimension |
126 | /// variable and q is a local variable. Let us put the constraints: |
127 | /// `1 <= x <= 7, x = 2q` |
128 | /// on this space to get the set: |
129 | /// `(x) : (exists q : q <= x <= 7, x = 2q)`. |
130 | /// An assignment to symbolic and dimension variables is valid if there |
131 | /// exists some assignment to the local variable `q` satisfying these |
132 | /// constraints. For this example, the set is equivalent to {2, 4, 6}. |
133 | /// Mathematically, existential quantification can be thought of as the result |
134 | /// of projection. In this example, `q` is existentially quantified. This can be |
135 | /// thought of as the result of projecting out `q` from the previous example, |
136 | /// i.e. we obtained {2, 4, 6} by projecting out the second dimension from |
137 | /// {(2, 1), (4, 2), (6, 2)}. |
138 | /// |
139 | /// Dimension variables are further divided into Domain and Range variables |
140 | /// to support building relations. |
141 | /// |
142 | /// Variables are stored in the following order: |
143 | /// [Domain, Range, Symbols, Locals] |
144 | /// |
145 | /// A space with no distinction between types of dimension variables can |
146 | /// be implemented as a space with zero domain. VarKind::SetDim should be used |
147 | /// to refer to dimensions in such spaces. |
148 | /// |
149 | /// Compatibility of two spaces implies that number of variables of each kind |
150 | /// other than Locals are equal. Equality of two spaces implies that number of |
151 | /// variables of each kind are equal. |
152 | /// |
153 | /// PresburgerSpace optionally also supports attaching an Identifier with each |
154 | /// non-local variable in the space. This is disabled by default. `resetIds` is |
155 | /// used to enable/reset these identifiers. The user can identify each variable |
156 | /// in the space as corresponding to some Identifier. Some example use cases |
157 | /// are described in the `Identifier` documentation above. The type attached to |
158 | /// the Identifier can be different for different variables in the space. |
159 | class PresburgerSpace { |
160 | public: |
161 | static PresburgerSpace getRelationSpace(unsigned numDomain = 0, |
162 | unsigned numRange = 0, |
163 | unsigned numSymbols = 0, |
164 | unsigned numLocals = 0) { |
165 | return PresburgerSpace(numDomain, numRange, numSymbols, numLocals); |
166 | } |
167 | |
168 | static PresburgerSpace getSetSpace(unsigned numDims = 0, |
169 | unsigned numSymbols = 0, |
170 | unsigned numLocals = 0) { |
171 | return PresburgerSpace(/*numDomain=*/0, /*numRange=*/numDims, numSymbols, |
172 | numLocals); |
173 | } |
174 | |
175 | /// Get the domain/range space of this space. The returned space is a set |
176 | /// space. |
177 | PresburgerSpace getDomainSpace() const; |
178 | PresburgerSpace getRangeSpace() const; |
179 | |
180 | /// Get the space without local variables. |
181 | PresburgerSpace getSpaceWithoutLocals() const; |
182 | |
183 | unsigned getNumDomainVars() const { return numDomain; } |
184 | unsigned getNumRangeVars() const { return numRange; } |
185 | unsigned getNumSetDimVars() const { return numRange; } |
186 | unsigned getNumSymbolVars() const { return numSymbols; } |
187 | unsigned getNumLocalVars() const { return numLocals; } |
188 | |
189 | unsigned getNumDimVars() const { return numDomain + numRange; } |
190 | unsigned getNumDimAndSymbolVars() const { |
191 | return numDomain + numRange + numSymbols; |
192 | } |
193 | unsigned getNumVars() const { |
194 | return numDomain + numRange + numSymbols + numLocals; |
195 | } |
196 | |
197 | /// Get the number of vars of the specified kind. |
198 | unsigned getNumVarKind(VarKind kind) const; |
199 | |
200 | /// Return the index at which the specified kind of var starts. |
201 | unsigned getVarKindOffset(VarKind kind) const; |
202 | |
203 | /// Return the index at Which the specified kind of var ends. |
204 | unsigned getVarKindEnd(VarKind kind) const; |
205 | |
206 | /// Get the number of elements of the specified kind in the range |
207 | /// [varStart, varLimit). |
208 | unsigned getVarKindOverlap(VarKind kind, unsigned varStart, |
209 | unsigned varLimit) const; |
210 | |
211 | /// Return the VarKind of the var at the specified position. |
212 | VarKind getVarKindAt(unsigned pos) const; |
213 | |
214 | /// Insert `num` variables of the specified kind at position `pos`. |
215 | /// Positions are relative to the kind of variable. Return the absolute |
216 | /// column position (i.e., not relative to the kind of variable) of the |
217 | /// first added variable. |
218 | /// |
219 | /// If identifiers are being used, the newly added variables have no |
220 | /// identifiers. |
221 | unsigned insertVar(VarKind kind, unsigned pos, unsigned num = 1); |
222 | |
223 | /// Removes variables of the specified kind in the column range [varStart, |
224 | /// varLimit). The range is relative to the kind of variable. |
225 | void removeVarRange(VarKind kind, unsigned varStart, unsigned varLimit); |
226 | |
227 | /// Converts variables of the specified kind in the column range [srcPos, |
228 | /// srcPos + num) to variables of the specified kind at position dstPos. The |
229 | /// ranges are relative to the kind of variable. |
230 | /// |
231 | /// srcKind and dstKind must be different. |
232 | void convertVarKind(VarKind srcKind, unsigned srcPos, unsigned num, |
233 | VarKind dstKind, unsigned dstPos); |
234 | |
235 | /// Changes the partition between dimensions and symbols. Depending on the new |
236 | /// symbol count, either a chunk of dimensional variables immediately before |
237 | /// the split become symbols, or some of the symbols immediately after the |
238 | /// split become dimensions. |
239 | void setVarSymbolSeperation(unsigned newSymbolCount); |
240 | |
241 | /// Swaps the posA^th variable of kindA and posB^th variable of kindB. |
242 | void swapVar(VarKind kindA, VarKind kindB, unsigned posA, unsigned posB); |
243 | |
244 | /// Returns true if both the spaces are compatible i.e. if both spaces have |
245 | /// the same number of variables of each kind (excluding locals). |
246 | bool isCompatible(const PresburgerSpace &other) const; |
247 | |
248 | /// Returns true if both the spaces are equal including local variables i.e. |
249 | /// if both spaces have the same number of variables of each kind (including |
250 | /// locals). |
251 | bool isEqual(const PresburgerSpace &other) const; |
252 | |
253 | /// Get the identifier of pos^th variable of the specified kind. |
254 | Identifier getId(VarKind kind, unsigned pos) const { |
255 | assert(kind != VarKind::Local && "Local variables have no identifiers" ); |
256 | if (!usingIds) |
257 | return Identifier(); |
258 | return identifiers[getVarKindOffset(kind) + pos]; |
259 | } |
260 | |
261 | ArrayRef<Identifier> getIds(VarKind kind) const { |
262 | assert(kind != VarKind::Local && "Local variables have no identifiers" ); |
263 | assert(usingIds && "Identifiers not enabled for space" ); |
264 | return {identifiers.data() + getVarKindOffset(kind), getNumVarKind(kind)}; |
265 | } |
266 | |
267 | ArrayRef<Identifier> getIds() const { |
268 | assert(usingIds && "Identifiers not enabled for space" ); |
269 | return identifiers; |
270 | } |
271 | |
272 | /// Set the identifier of pos^th variable of the specified kind. Calls |
273 | /// resetIds if identifiers are not enabled. |
274 | void setId(VarKind kind, unsigned pos, Identifier id) { |
275 | assert(kind != VarKind::Local && "Local variables have no identifiers" ); |
276 | if (!usingIds) |
277 | resetIds(); |
278 | identifiers[getVarKindOffset(kind) + pos] = id; |
279 | } |
280 | |
281 | /// Returns if identifiers are being used. |
282 | bool isUsingIds() const { return usingIds; } |
283 | |
284 | /// Reset the stored identifiers in the space. Enables `usingIds` if it was |
285 | /// `false` before. |
286 | void resetIds() { |
287 | identifiers.clear(); |
288 | identifiers.resize(N: getNumDimAndSymbolVars()); |
289 | usingIds = true; |
290 | } |
291 | |
292 | /// Disable identifiers being stored in space. |
293 | void disableIds() { |
294 | identifiers.clear(); |
295 | usingIds = false; |
296 | } |
297 | |
298 | /// Check if the spaces are compatible, and the non-local variables having |
299 | /// same identifiers are in the same positions. If the space is not using |
300 | /// Identifiers, this check is same as isCompatible. |
301 | bool isAligned(const PresburgerSpace &other) const; |
302 | /// Same as above but only check the specified VarKind. Useful to check if |
303 | /// the symbols in two spaces are aligned. |
304 | bool isAligned(const PresburgerSpace &other, VarKind kind) const; |
305 | |
306 | /// Merge and align symbol variables of `this` and `other` with respect to |
307 | /// identifiers. After this operation the symbol variables of both spaces have |
308 | /// the same identifiers in the same order. |
309 | void mergeAndAlignSymbols(PresburgerSpace &other); |
310 | |
311 | void print(llvm::raw_ostream &os) const; |
312 | void dump() const; |
313 | |
314 | protected: |
315 | PresburgerSpace(unsigned numDomain, unsigned numRange, unsigned numSymbols, |
316 | unsigned numLocals) |
317 | : numDomain(numDomain), numRange(numRange), numSymbols(numSymbols), |
318 | numLocals(numLocals) {} |
319 | |
320 | private: |
321 | // Number of variables corresponding to domain variables. |
322 | unsigned numDomain; |
323 | |
324 | // Number of variables corresponding to range variables. |
325 | unsigned numRange; |
326 | |
327 | /// Number of variables corresponding to symbols (unknown but constant for |
328 | /// analysis). |
329 | unsigned numSymbols; |
330 | |
331 | /// Number of variables corresponding to locals (variables corresponding |
332 | /// to existentially quantified variables). |
333 | unsigned numLocals; |
334 | |
335 | /// Stores whether or not identifiers are being used in this space. |
336 | bool usingIds = false; |
337 | |
338 | /// Stores an identifier for each non-local variable as a `void` pointer. |
339 | SmallVector<Identifier, 0> identifiers; |
340 | }; |
341 | |
342 | } // namespace presburger |
343 | } // namespace mlir |
344 | |
345 | #endif // MLIR_ANALYSIS_PRESBURGER_PRESBURGERSPACE_H |
346 | |