MLIR  16.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.
95  PresburgerSpace getDomainSpace() const;
96  PresburgerSpace getRangeSpace() const;
97 
98  unsigned getNumDomainVars() const { return numDomain; }
99  unsigned getNumRangeVars() const { return numRange; }
100  unsigned getNumSetDimVars() const { return numRange; }
101  unsigned getNumSymbolVars() const { return numSymbols; }
102  unsigned getNumLocalVars() const { return numLocals; }
103 
104  unsigned getNumDimVars() const { return numDomain + numRange; }
105  unsigned getNumDimAndSymbolVars() const {
106  return numDomain + numRange + numSymbols;
107  }
108  unsigned getNumVars() const {
109  return numDomain + numRange + numSymbols + numLocals;
110  }
111 
112  /// Get the number of vars of the specified kind.
113  unsigned getNumVarKind(VarKind kind) const;
114 
115  /// Return the index at which the specified kind of var starts.
116  unsigned getVarKindOffset(VarKind kind) const;
117 
118  /// Return the index at Which the specified kind of var ends.
119  unsigned getVarKindEnd(VarKind kind) const;
120 
121  /// Get the number of elements of the specified kind in the range
122  /// [varStart, varLimit).
123  unsigned getVarKindOverlap(VarKind kind, unsigned varStart,
124  unsigned varLimit) const;
125 
126  /// Return the VarKind of the var at the specified position.
127  VarKind getVarKindAt(unsigned pos) const;
128 
129  /// Insert `num` variables of the specified kind at position `pos`.
130  /// Positions are relative to the kind of variable. Return the absolute
131  /// column position (i.e., not relative to the kind of variable) of the
132  /// first added variable.
133  ///
134  /// If identifiers are being used, the newly added variables have no
135  /// identifiers.
136  unsigned insertVar(VarKind kind, unsigned pos, unsigned num = 1);
137 
138  /// Removes variables of the specified kind in the column range [varStart,
139  /// varLimit). The range is relative to the kind of variable.
140  void removeVarRange(VarKind kind, unsigned varStart, unsigned varLimit);
141 
142  /// Swaps the posA^th variable of kindA and posB^th variable of kindB.
143  void swapVar(VarKind kindA, VarKind kindB, unsigned posA, unsigned posB);
144 
145  /// Returns true if both the spaces are compatible i.e. if both spaces have
146  /// the same number of variables of each kind (excluding locals).
147  bool isCompatible(const PresburgerSpace &other) const;
148 
149  /// Returns true if both the spaces are equal including local variables i.e.
150  /// if both spaces have the same number of variables of each kind (including
151  /// locals).
152  bool isEqual(const PresburgerSpace &other) const;
153 
154  /// Changes the partition between dimensions and symbols. Depending on the new
155  /// symbol count, either a chunk of dimensional variables immediately before
156  /// the split become symbols, or some of the symbols immediately after the
157  /// split become dimensions.
158  void setVarSymbolSeperation(unsigned newSymbolCount);
159 
160  void print(llvm::raw_ostream &os) const;
161  void dump() const;
162 
163  //===--------------------------------------------------------------------===//
164  // Identifier Interactions
165  //===--------------------------------------------------------------------===//
166 
167  /// Set the identifier for `i^th` variable to `id`. `T` here should match the
168  /// type used to enable identifiers.
169  template <typename T>
170  void setId(VarKind kind, unsigned i, T id) {
171 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
172  assert(TypeID::get<T>() == idType && "Type mismatch");
173 #endif
174  atId(kind, i) = llvm::PointerLikeTypeTraits<T>::getAsVoidPointer(id);
175  }
176 
177  /// Get the identifier for `i^th` variable casted to type `T`. `T` here
178  /// should match the type used to enable identifiers.
179  template <typename T>
180  T getId(VarKind kind, unsigned i) const {
181 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
182  assert(TypeID::get<T>() == idType && "Type mismatch");
183 #endif
184  return llvm::PointerLikeTypeTraits<T>::getFromVoidPointer(atId(kind, i));
185  }
186 
187  /// Check if the i^th variable of the specified kind has a non-null
188  /// identifier.
189  bool hasId(VarKind kind, unsigned i) const {
190  return atId(kind, i) != nullptr;
191  }
192 
193  /// Check if the spaces are compatible, as well as have the same identifiers
194  /// for each variable.
195  bool isAligned(const PresburgerSpace &other) const;
196  /// Check if the number of variables of the specified kind match, and have
197  /// same identifiers with the other space.
198  bool isAligned(const PresburgerSpace &other, VarKind kind) const;
199 
200  /// Find the variable of the specified kind with identifier `id`.
201  /// Returns PresburgerSpace::kIdNotFound if identifier is not found.
202  template <typename T>
203  unsigned findId(VarKind kind, T id) const {
204  unsigned i = 0;
205  for (unsigned e = getNumVarKind(kind); i < e; ++i)
206  if (hasId(kind, i) && getId<T>(kind, i) == id)
207  return i;
208  return kIdNotFound;
209  }
210  static const unsigned kIdNotFound = UINT_MAX;
211 
212  /// Returns if identifiers are being used.
213  bool isUsingIds() const { return usingIds; }
214 
215  /// Reset the stored identifiers in the space. Enables `usingIds` if it was
216  /// `false` before.
217  template <typename T>
218  void resetIds() {
219  identifiers.clear();
220  identifiers.resize(getNumDimAndSymbolVars());
221 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
222  idType = TypeID::get<T>();
223 #endif
224 
225  usingIds = true;
226  }
227 
228  /// Disable identifiers being stored in space.
229  void disableIds() {
230  identifiers.clear();
231  usingIds = false;
232  }
233 
234 protected:
235  PresburgerSpace(unsigned numDomain = 0, unsigned numRange = 0,
236  unsigned numSymbols = 0, unsigned numLocals = 0)
237  : numDomain(numDomain), numRange(numRange), numSymbols(numSymbols),
238  numLocals(numLocals) {}
239 
240  void *&atId(VarKind kind, unsigned i) {
241  assert(usingIds && "Cannot access identifiers when `usingIds` is false.");
242  assert(kind != VarKind::Local &&
243  "Local variables cannot have identifiers.");
244  return identifiers[getVarKindOffset(kind) + i];
245  }
246 
247  void *atId(VarKind kind, unsigned i) const {
248  assert(usingIds && "Cannot access identifiers when `usingIds` is false.");
249  assert(kind != VarKind::Local &&
250  "Local variables cannot have identifiers.");
251  return identifiers[getVarKindOffset(kind) + i];
252  }
253 
254 private:
255  // Number of variables corresponding to domain variables.
256  unsigned numDomain;
257 
258  // Number of variables corresponding to range variables.
259  unsigned numRange;
260 
261  /// Number of variables corresponding to symbols (unknown but constant for
262  /// analysis).
263  unsigned numSymbols;
264 
265  /// Number of variables corresponding to locals (variables corresponding
266  /// to existentially quantified variables).
267  unsigned numLocals;
268 
269  /// Stores whether or not identifiers are being used in this space.
270  bool usingIds = false;
271 
272 #ifdef LLVM_ENABLE_ABI_BREAKING_CHECKS
273  /// TypeID of the identifiers in space. This should be used in asserts only.
274  TypeID idType;
275 #endif
276 
277  /// Stores an identifier for each non-local variable as a `void` pointer.
278  SmallVector<void *, 0> identifiers;
279 };
280 
281 } // namespace presburger
282 } // namespace mlir
283 
284 #endif // MLIR_ANALYSIS_PRESBURGER_PRESBURGERSPACE_H
Include the generated interface declarations.
bool hasId(VarKind kind, unsigned i) const
Check if the i^th variable of the specified kind has a non-null identifier.
T getId(VarKind kind, unsigned i) const
Get the identifier for i^th variable casted to type T.
void disableIds()
Disable identifiers being stored in space.
void resetIds()
Reset the stored identifiers in the space.
This class provides an efficient unique identifier for a specific C++ type.
Definition: TypeID.h:104
bool isUsingIds() const
Returns if identifiers are being used.
static void print(spirv::VerCapExtAttr triple, DialectAsmPrinter &printer)
VarKind
Kind of variable.
PresburgerSpace(unsigned numDomain=0, unsigned numRange=0, unsigned numSymbols=0, unsigned numLocals=0)
void setId(VarKind kind, unsigned i, T id)
Set the identifier for i^th variable to id.
unsigned findId(VarKind kind, T id) const
Find the variable of the specified kind with identifier id.
PresburgerSpace is the space of all possible values of a tuple of integer valued variables/variables...
void * atId(VarKind kind, unsigned i) const
void *& atId(VarKind kind, unsigned i)
static PresburgerSpace getRelationSpace(unsigned numDomain=0, unsigned numRange=0, unsigned numSymbols=0, unsigned numLocals=0)
static PresburgerSpace getSetSpace(unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0)