MLIR  17.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 /// PresburgerSpace is the space of all possible values of a tuple of integer
32 /// valued variables/variables. Each variable has one of the three types:
33 ///
34 /// Dimension: Ordinary variables over which the space is represented.
35 ///
36 /// Symbol: Symbol variables correspond to fixed but unknown values.
37 /// Mathematically, a space with symbolic variables is like a
38 /// family of spaces indexed by the symbolic variables.
39 ///
40 /// Local: Local variables correspond to existentially quantified variables.
41 /// For example, consider the space: `(x, exists q)` where x is a dimension
42 /// variable and q is a local variable. Let us put the constraints:
43 /// `1 <= x <= 7, x = 2q`
44 /// on this space to get the set:
45 /// `(x) : (exists q : q <= x <= 7, x = 2q)`.
46 /// An assignment to symbolic and dimension variables is valid if there
47 /// exists some assignment to the local variable `q` satisfying these
48 /// constraints. For this example, the set is equivalent to {2, 4, 6}.
49 /// Mathematically, existential quantification can be thought of as the result
50 /// of projection. In this example, `q` is existentially quantified. This can be
51 /// thought of as the result of projecting out `q` from the previous example,
52 /// i.e. we obtained {2, 4, 6} by projecting out the second dimension from
53 /// {(2, 1), (4, 2), (6, 2)}.
54 ///
55 /// Dimension variables are further divided into Domain and Range variables
56 /// to support building relations.
57 ///
58 /// Variables are stored in the following order:
59 /// [Domain, Range, Symbols, Locals]
60 ///
61 /// A space with no distinction between types of dimension variables can
62 /// be implemented as a space with zero domain. VarKind::SetDim should be used
63 /// to refer to dimensions in such spaces.
64 ///
65 /// Compatibility of two spaces implies that number of variables of each kind
66 /// other than Locals are equal. Equality of two spaces implies that number of
67 /// variables of each kind are equal.
68 ///
69 /// PresburgerSpace optionally also supports attaching some information to each
70 /// variable in space, called "identifier" of that variable. `resetIds<IdType>`
71 /// is used to enable/reset these identifiers. All identifiers must be of the
72 /// same type, `IdType`. `IdType` must have a `llvm::PointerLikeTypeTraits`
73 /// specialization available and should be supported via `mlir::TypeID`.
74 ///
75 /// These identifiers can be used to check if two variables in two different
76 /// spaces are actually same variable.
78 public:
79  static PresburgerSpace getRelationSpace(unsigned numDomain = 0,
80  unsigned numRange = 0,
81  unsigned numSymbols = 0,
82  unsigned numLocals = 0) {
83  return PresburgerSpace(numDomain, numRange, numSymbols, numLocals);
84  }
85 
86  static PresburgerSpace getSetSpace(unsigned numDims = 0,
87  unsigned numSymbols = 0,
88  unsigned numLocals = 0) {
89  return PresburgerSpace(/*numDomain=*/0, /*numRange=*/numDims, numSymbols,
90  numLocals);
91  }
92 
93  /// Get the domain/range space of this space. The returned space is a set
94  /// space.
97 
98  /// Get the space without local variables.
100 
101  unsigned getNumDomainVars() const { return numDomain; }
102  unsigned getNumRangeVars() const { return numRange; }
103  unsigned getNumSetDimVars() const { return numRange; }
104  unsigned getNumSymbolVars() const { return numSymbols; }
105  unsigned getNumLocalVars() const { return numLocals; }
106 
107  unsigned getNumDimVars() const { return numDomain + numRange; }
108  unsigned getNumDimAndSymbolVars() const {
109  return numDomain + numRange + numSymbols;
110  }
111  unsigned getNumVars() const {
112  return numDomain + numRange + numSymbols + numLocals;
113  }
114 
115  /// Get the number of vars of the specified kind.
116  unsigned getNumVarKind(VarKind kind) const;
117 
118  /// Return the index at which the specified kind of var starts.
119  unsigned getVarKindOffset(VarKind kind) const;
120 
121  /// Return the index at Which the specified kind of var ends.
122  unsigned getVarKindEnd(VarKind kind) const;
123 
124  /// Get the number of elements of the specified kind in the range
125  /// [varStart, varLimit).
126  unsigned getVarKindOverlap(VarKind kind, unsigned varStart,
127  unsigned varLimit) const;
128 
129  /// Return the VarKind of the var at the specified position.
130  VarKind getVarKindAt(unsigned pos) const;
131 
132  /// Insert `num` variables of the specified kind at position `pos`.
133  /// Positions are relative to the kind of variable. Return the absolute
134  /// column position (i.e., not relative to the kind of variable) of the
135  /// first added variable.
136  ///
137  /// If identifiers are being used, the newly added variables have no
138  /// identifiers.
139  unsigned insertVar(VarKind kind, unsigned pos, unsigned num = 1);
140 
141  /// Removes variables of the specified kind in the column range [varStart,
142  /// varLimit). The range is relative to the kind of variable.
143  void removeVarRange(VarKind kind, unsigned varStart, unsigned varLimit);
144 
145  /// Swaps the posA^th variable of kindA and posB^th variable of kindB.
146  void swapVar(VarKind kindA, VarKind kindB, unsigned posA, unsigned posB);
147 
148  /// Returns true if both the spaces are compatible i.e. if both spaces have
149  /// the same number of variables of each kind (excluding locals).
150  bool isCompatible(const PresburgerSpace &other) const;
151 
152  /// Returns true if both the spaces are equal including local variables i.e.
153  /// if both spaces have the same number of variables of each kind (including
154  /// locals).
155  bool isEqual(const PresburgerSpace &other) const;
156 
157  /// Changes the partition between dimensions and symbols. Depending on the new
158  /// symbol count, either a chunk of dimensional variables immediately before
159  /// the split become symbols, or some of the symbols immediately after the
160  /// split become dimensions.
161  void setVarSymbolSeperation(unsigned newSymbolCount);
162 
163  void print(llvm::raw_ostream &os) const;
164  void dump() const;
165 
166  //===--------------------------------------------------------------------===//
167  // Identifier Interactions
168  //===--------------------------------------------------------------------===//
169 
170  /// Set the identifier for `i^th` variable to `id`. `T` here should match the
171  /// type used to enable identifiers.
172  template <typename T>
173  void setId(VarKind kind, unsigned i, T id) {
174 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
175  assert(TypeID::get<T>() == idType && "Type mismatch");
176 #endif
177  atId(kind, i) = llvm::PointerLikeTypeTraits<T>::getAsVoidPointer(id);
178  }
179 
180  /// Get the identifier for `i^th` variable casted to type `T`. `T` here
181  /// should match the type used to enable identifiers.
182  template <typename T>
183  T getId(VarKind kind, unsigned i) const {
184 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
185  assert(TypeID::get<T>() == idType && "Type mismatch");
186 #endif
187  return llvm::PointerLikeTypeTraits<T>::getFromVoidPointer(atId(kind, i));
188  }
189 
190  /// Check if the i^th variable of the specified kind has a non-null
191  /// identifier.
192  bool hasId(VarKind kind, unsigned i) const {
193  return atId(kind, i) != nullptr;
194  }
195 
196  /// Check if the spaces are compatible, as well as have the same identifiers
197  /// for each variable.
198  bool isAligned(const PresburgerSpace &other) const;
199  /// Check if the number of variables of the specified kind match, and have
200  /// same identifiers with the other space.
201  bool isAligned(const PresburgerSpace &other, VarKind kind) const;
202 
203  /// Find the variable of the specified kind with identifier `id`.
204  /// Returns PresburgerSpace::kIdNotFound if identifier is not found.
205  template <typename T>
206  unsigned findId(VarKind kind, T id) const {
207  unsigned i = 0;
208  for (unsigned e = getNumVarKind(kind); i < e; ++i)
209  if (hasId(kind, i) && getId<T>(kind, i) == id)
210  return i;
211  return kIdNotFound;
212  }
213  static const unsigned kIdNotFound = UINT_MAX;
214 
215  /// Returns if identifiers are being used.
216  bool isUsingIds() const { return usingIds; }
217 
218  /// Reset the stored identifiers in the space. Enables `usingIds` if it was
219  /// `false` before.
220  template <typename T>
221  void resetIds() {
222  identifiers.clear();
223  identifiers.resize(getNumDimAndSymbolVars());
224 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
225  idType = TypeID::get<T>();
226 #endif
227 
228  usingIds = true;
229  }
230 
231  /// Disable identifiers being stored in space.
232  void disableIds() {
233  identifiers.clear();
234  usingIds = false;
235  }
236 
237 protected:
238  PresburgerSpace(unsigned numDomain = 0, unsigned numRange = 0,
239  unsigned numSymbols = 0, unsigned numLocals = 0)
240  : numDomain(numDomain), numRange(numRange), numSymbols(numSymbols),
241  numLocals(numLocals) {}
242 
243  void *&atId(VarKind kind, unsigned i) {
244  assert(usingIds && "Cannot access identifiers when `usingIds` is false.");
245  assert(kind != VarKind::Local &&
246  "Local variables cannot have identifiers.");
247  return identifiers[getVarKindOffset(kind) + i];
248  }
249 
250  void *atId(VarKind kind, unsigned i) const {
251  assert(usingIds && "Cannot access identifiers when `usingIds` is false.");
252  assert(kind != VarKind::Local &&
253  "Local variables cannot have identifiers.");
254  return identifiers[getVarKindOffset(kind) + i];
255  }
256 
257 private:
258  // Number of variables corresponding to domain variables.
259  unsigned numDomain;
260 
261  // Number of variables corresponding to range variables.
262  unsigned numRange;
263 
264  /// Number of variables corresponding to symbols (unknown but constant for
265  /// analysis).
266  unsigned numSymbols;
267 
268  /// Number of variables corresponding to locals (variables corresponding
269  /// to existentially quantified variables).
270  unsigned numLocals;
271 
272  /// Stores whether or not identifiers are being used in this space.
273  bool usingIds = false;
274 
275 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
276  /// TypeID of the identifiers in space. This should be used in asserts only.
277  TypeID idType;
278 #endif
279 
280  /// Stores an identifier for each non-local variable as a `void` pointer.
281  SmallVector<void *, 0> identifiers;
282 };
283 
284 } // namespace presburger
285 } // namespace mlir
286 
287 #endif // MLIR_ANALYSIS_PRESBURGER_PRESBURGERSPACE_H
This class provides an efficient unique identifier for a specific C++ type.
Definition: TypeID.h:104
PresburgerSpace is the space of all possible values of a tuple of integer valued variables/variables.
PresburgerSpace getRangeSpace() const
void resetIds()
Reset the stored identifiers in the space.
void setId(VarKind kind, unsigned i, T id)
Set the identifier for i^th variable to id.
unsigned getNumVarKind(VarKind kind) const
Get the number of vars of the specified kind.
void * atId(VarKind kind, unsigned i) const
PresburgerSpace(unsigned numDomain=0, unsigned numRange=0, unsigned numSymbols=0, unsigned numLocals=0)
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.
void disableIds()
Disable identifiers being stored in space.
bool isUsingIds() const
Returns if identifiers are being used.
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.
VarKind getVarKindAt(unsigned pos) const
Return the VarKind of the var at the specified position.
unsigned findId(VarKind kind, T id) const
Find the variable of the specified kind with identifier id.
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)
bool isCompatible(const PresburgerSpace &other) const
Returns true if both the spaces are compatible i.e.
void print(llvm::raw_ostream &os) const
bool isAligned(const PresburgerSpace &other) const
Check if the spaces are compatible, as well as have the same identifiers for each variable.
PresburgerSpace getSpaceWithoutLocals() const
Get the space without local variables.
void *& atId(VarKind kind, unsigned i)
static const unsigned kIdNotFound
static PresburgerSpace getRelationSpace(unsigned numDomain=0, unsigned numRange=0, unsigned numSymbols=0, unsigned numLocals=0)
T getId(VarKind kind, unsigned i) const
Get the identifier for i^th variable casted to type T.
bool hasId(VarKind kind, unsigned i) const
Check if the i^th variable of the specified kind has a non-null identifier.
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.
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...