MLIR  19.0.0git
PresburgerSpace.h
Go to the documentation of this file.
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.
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.
179 
180  /// Get the space without local variables.
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 the specified variable.
254  Identifier &getId(VarKind kind, unsigned pos) {
255  assert(kind != VarKind::Local && "Local variables have no identifiers");
256  return identifiers[getVarKindOffset(kind) + pos];
257  }
258  Identifier getId(VarKind kind, unsigned pos) const {
259  assert(kind != VarKind::Local && "Local variables have no identifiers");
260  return identifiers[getVarKindOffset(kind) + pos];
261  }
262 
264  assert(kind != VarKind::Local && "Local variables have no identifiers");
265  return {identifiers.data() + getVarKindOffset(kind), getNumVarKind(kind)};
266  }
267 
268  /// Returns if identifiers are being used.
269  bool isUsingIds() const { return usingIds; }
270 
271  /// Reset the stored identifiers in the space. Enables `usingIds` if it was
272  /// `false` before.
273  void resetIds() {
274  identifiers.clear();
275  identifiers.resize(getNumDimAndSymbolVars());
276  usingIds = true;
277  }
278 
279  /// Disable identifiers being stored in space.
280  void disableIds() {
281  identifiers.clear();
282  usingIds = false;
283  }
284 
285  /// Check if the spaces are compatible, and the non-local variables having
286  /// same identifiers are in the same positions. If the space is not using
287  /// Identifiers, this check is same as isCompatible.
288  bool isAligned(const PresburgerSpace &other) const;
289  /// Same as above but only check the specified VarKind. Useful to check if
290  /// the symbols in two spaces are aligned.
291  bool isAligned(const PresburgerSpace &other, VarKind kind) const;
292 
293  /// Merge and align symbol variables of `this` and `other` with respect to
294  /// identifiers. After this operation the symbol variables of both spaces have
295  /// the same identifiers in the same order.
297 
298  void print(llvm::raw_ostream &os) const;
299  void dump() const;
300 
301 protected:
302  PresburgerSpace(unsigned numDomain, unsigned numRange, unsigned numSymbols,
303  unsigned numLocals)
304  : numDomain(numDomain), numRange(numRange), numSymbols(numSymbols),
305  numLocals(numLocals) {}
306 
307 private:
308  // Number of variables corresponding to domain variables.
309  unsigned numDomain;
310 
311  // Number of variables corresponding to range variables.
312  unsigned numRange;
313 
314  /// Number of variables corresponding to symbols (unknown but constant for
315  /// analysis).
316  unsigned numSymbols;
317 
318  /// Number of variables corresponding to locals (variables corresponding
319  /// to existentially quantified variables).
320  unsigned numLocals;
321 
322  /// Stores whether or not identifiers are being used in this space.
323  bool usingIds = false;
324 
325  /// Stores an identifier for each non-local variable as a `void` pointer.
326  SmallVector<Identifier, 0> identifiers;
327 };
328 
329 } // namespace presburger
330 } // namespace mlir
331 
332 #endif // MLIR_ANALYSIS_PRESBURGER_PRESBURGERSPACE_H
This class provides an efficient unique identifier for a specific C++ type.
Definition: TypeID.h:104
An Identifier stores a pointer to an object, such as a Value or an Operation.
T getValue() const
Get the value of the identifier casted to type T.
bool operator!=(const Identifier &other) const
bool isEqual(const Identifier &other) const
Check if the two identifiers are equal.
void print(llvm::raw_ostream &os) const
bool operator==(const Identifier &other) const
PresburgerSpace is the space of all possible values of a tuple of integer valued variables/variables.
PresburgerSpace getRangeSpace() const
unsigned getNumVarKind(VarKind kind) const
Get the number of vars of the specified kind.
void resetIds()
Reset the stored identifiers in the space.
bool isEqual(const PresburgerSpace &other) const
Returns true if both the spaces are equal including local variables i.e.
PresburgerSpace getDomainSpace() const
Get the domain/range space of this space.
Identifier & getId(VarKind kind, unsigned pos)
Get the identifier of the specified variable.
void disableIds()
Disable identifiers being stored in space.
bool isUsingIds() const
Returns if identifiers are being used.
void convertVarKind(VarKind srcKind, unsigned srcPos, unsigned num, VarKind dstKind, unsigned dstPos)
Converts variables of the specified kind in the column range [srcPos, srcPos + num) to variables of t...
void removeVarRange(VarKind kind, unsigned varStart, unsigned varLimit)
Removes variables of the specified kind in the column range [varStart, varLimit).
unsigned getVarKindOffset(VarKind kind) const
Return the index at which the specified kind of var starts.
void setVarSymbolSeperation(unsigned newSymbolCount)
Changes the partition between dimensions and symbols.
unsigned getVarKindEnd(VarKind kind) const
Return the index at Which the specified kind of var ends.
Identifier getId(VarKind kind, unsigned pos) const
PresburgerSpace(unsigned numDomain, unsigned numRange, unsigned numSymbols, unsigned numLocals)
VarKind getVarKindAt(unsigned pos) const
Return the VarKind of the var at the specified position.
unsigned getVarKindOverlap(VarKind kind, unsigned varStart, unsigned varLimit) const
Get the number of elements of the specified kind in the range [varStart, varLimit).
static PresburgerSpace getSetSpace(unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0)
ArrayRef< Identifier > getIds(VarKind kind) const
bool isCompatible(const PresburgerSpace &other) const
Returns true if both the spaces are compatible i.e.
void print(llvm::raw_ostream &os) const
void mergeAndAlignSymbols(PresburgerSpace &other)
Merge and align symbol variables of this and other with respect to identifiers.
bool isAligned(const PresburgerSpace &other) const
Check if the spaces are compatible, and the non-local variables having same identifiers are in the sa...
PresburgerSpace getSpaceWithoutLocals() const
Get the space without local variables.
static PresburgerSpace getRelationSpace(unsigned numDomain=0, unsigned numRange=0, unsigned numSymbols=0, unsigned numLocals=0)
void swapVar(VarKind kindA, VarKind kindB, unsigned posA, unsigned posB)
Swaps the posA^th variable of kindA and posB^th variable of kindB.
unsigned insertVar(VarKind kind, unsigned pos, unsigned num=1)
Insert num variables of the specified kind at position pos.
Include the generated interface declarations.
Definition: CallGraph.h:229
VarKind
Kind of variable.
Include the generated interface declarations.
Represents a range (offset, size, and stride) where each element of the triple may be dynamic or stat...