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
23namespace mlir {
24namespace 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.
29enum 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.
68class Identifier {
69public:
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
105private:
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.
159class PresburgerSpace {
160public:
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
314protected:
315 PresburgerSpace(unsigned numDomain, unsigned numRange, unsigned numSymbols,
316 unsigned numLocals)
317 : numDomain(numDomain), numRange(numRange), numSymbols(numSymbols),
318 numLocals(numLocals) {}
319
320private:
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

source code of mlir/include/mlir/Analysis/Presburger/PresburgerSpace.h