MLIR  18.0.0git
FlatLinearValueConstraints.h
Go to the documentation of this file.
1 //===- FlatLinearValueConstraints.h - Linear Constraints --------*- 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 #ifndef MLIR_ANALYSIS_FLATLINEARVALUECONSTRAINTS_H
10 #define MLIR_ANALYSIS_FLATLINEARVALUECONSTRAINTS_H
11 
14 #include "mlir/IR/AffineExpr.h"
15 #include "mlir/IR/OpDefinition.h"
17 #include <optional>
18 
19 namespace mlir {
20 
21 class AffineMap;
22 class IntegerSet;
23 class MLIRContext;
24 class Value;
25 class MemRefType;
26 struct MutableAffineMap;
27 
28 namespace presburger {
30 } // namespace presburger
31 
32 /// FlatLinearConstraints is an extension of IntegerPolyhedron. It provides an
33 /// AffineExpr-based API.
35 public:
36  /// Constructs a constraint system reserving memory for the specified number
37  /// of constraints and variables. `valArgs` are the optional SSA values
38  /// associated with each dimension/symbol. These must either be empty or match
39  /// the number of dimensions and symbols.
40  FlatLinearConstraints(unsigned numReservedInequalities,
41  unsigned numReservedEqualities,
42  unsigned numReservedCols, unsigned numDims,
43  unsigned numSymbols, unsigned numLocals)
44  : IntegerPolyhedron(numReservedInequalities, numReservedEqualities,
45  numReservedCols,
46  presburger::PresburgerSpace::getSetSpace(
47  numDims, numSymbols, numLocals)) {
48  assert(numReservedCols >= getNumVars() + 1);
49  }
50 
51  /// Constructs a constraint system with the specified number of dimensions
52  /// and symbols. `valArgs` are the optional SSA values associated with each
53  /// dimension/symbol. These must either be empty or match the number of
54  /// dimensions and symbols.
55  FlatLinearConstraints(unsigned numDims = 0, unsigned numSymbols = 0,
56  unsigned numLocals = 0)
57  : FlatLinearConstraints(/*numReservedInequalities=*/0,
58  /*numReservedEqualities=*/0,
59  /*numReservedCols=*/numDims + numSymbols +
60  numLocals + 1,
61  numDims, numSymbols, numLocals) {}
62 
64  : IntegerPolyhedron(fac) {}
65 
66  /// Return the kind of this object.
67  Kind getKind() const override { return Kind::FlatLinearConstraints; }
68 
69  /// Adds a bound for the variable at the specified position with constraints
70  /// being drawn from the specified bound map. In case of an EQ bound, the
71  /// bound map is expected to have exactly one result. In case of a LB/UB, the
72  /// bound map may have more than one result, for each of which an inequality
73  /// is added.
74  ///
75  /// The bound can be added as open or closed by specifying isClosedBound. In
76  /// case of a LB/UB, isClosedBound = false means the bound is added internally
77  /// as a closed bound by +1/-1 respectively. In case of an EQ bound, it can
78  /// only be added as a closed bound.
79  ///
80  /// Note: The dimensions/symbols of this FlatLinearConstraints must match the
81  /// dimensions/symbols of the affine map.
82  LogicalResult addBound(presburger::BoundType type, unsigned pos,
83  AffineMap boundMap, bool isClosedBound);
84 
85  /// Adds a bound for the variable at the specified position with constraints
86  /// being drawn from the specified bound map. In case of an EQ bound, the
87  /// bound map is expected to have exactly one result. In case of a LB/UB, the
88  /// bound map may have more than one result, for each of which an inequality
89  /// is added.
90  /// Note: The dimensions/symbols of this FlatLinearConstraints must match the
91  /// dimensions/symbols of the affine map. By default the lower bound is closed
92  /// and the upper bound is open.
93  LogicalResult addBound(presburger::BoundType type, unsigned pos,
94  AffineMap boundMap);
95 
96  /// The `addBound` overload above hides the inherited overloads by default, so
97  /// we explicitly introduce them here.
98  using IntegerPolyhedron::addBound;
99 
100  /// Returns the constraint system as an integer set. Returns a null integer
101  /// set if the system has no constraints, or if an integer set couldn't be
102  /// constructed as a result of a local variable's explicit representation not
103  /// being known and such a local variable appearing in any of the constraints.
104  IntegerSet getAsIntegerSet(MLIRContext *context) const;
105 
106  /// Computes the lower and upper bounds of the first `num` dimensional
107  /// variables (starting at `offset`) as an affine map of the remaining
108  /// variables (dimensional and symbolic). This method is able to detect
109  /// variables as floordiv's and mod's of affine expressions of other
110  /// variables with respect to (positive) constants. Sets bound map to a
111  /// null AffineMap if such a bound can't be found (or yet unimplemented).
112  ///
113  /// By default the returned lower bounds are closed and upper bounds are open.
114  /// If `closedUb` is true, the upper bound is closed.
115  void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context,
118  bool closedUB = false);
119 
120  /// Composes an affine map whose dimensions and symbols match one to one with
121  /// the dimensions and symbols of this FlatLinearConstraints. The results of
122  /// the map `other` are added as the leading dimensions of this constraint
123  /// system. Returns failure if `other` is a semi-affine map.
125 
126  /// Gets the lower and upper bound of the `offset` + `pos`th variable
127  /// treating [0, offset) U [offset + num, symStartPos) as dimensions and
128  /// [symStartPos, getNumDimAndSymbolVars) as symbols, and `pos` lies in
129  /// [0, num). The multi-dimensional maps in the returned pair represent the
130  /// max and min of potentially multiple affine expressions. `localExprs` holds
131  /// pre-computed AffineExpr's for all local variables in the system.
132  ///
133  /// By default the returned lower bounds are closed and upper bounds are open.
134  /// If `closedUb` is true, the upper bound is closed.
135  std::pair<AffineMap, AffineMap>
136  getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num,
137  unsigned symStartPos, ArrayRef<AffineExpr> localExprs,
138  MLIRContext *context, bool closedUB = false) const;
139 
140  /// Insert variables of the specified kind at position `pos`. Positions are
141  /// relative to the kind of variable. The coefficient columns corresponding
142  /// to the added variables are initialized to zero. `vals` are the Values
143  /// corresponding to the variables. Values should not be used with
144  /// VarKind::Local since values can only be attached to non-local variables.
145  /// Return the absolute column position (i.e., not relative to the kind of
146  /// variable) of the first added variable.
147  ///
148  /// Note: Empty Values are allowed in `vals`.
149  unsigned insertDimVar(unsigned pos, unsigned num = 1) {
150  return insertVar(VarKind::SetDim, pos, num);
151  }
152  unsigned insertSymbolVar(unsigned pos, unsigned num = 1) {
153  return insertVar(VarKind::Symbol, pos, num);
154  }
155  unsigned insertLocalVar(unsigned pos, unsigned num = 1) {
156  return insertVar(VarKind::Local, pos, num);
157  }
158 
159  /// Append variables of the specified kind after the last variable of that
160  /// kind. The coefficient columns corresponding to the added variables are
161  /// initialized to zero. `vals` are the Values corresponding to the
162  /// variables. Return the absolute column position (i.e., not relative to the
163  /// kind of variable) of the first appended variable.
164  ///
165  /// Note: Empty Values are allowed in `vals`.
166  unsigned appendDimVar(unsigned num = 1) {
167  return appendVar(VarKind::SetDim, num);
168  }
169  unsigned appendSymbolVar(unsigned num = 1) {
170  return appendVar(VarKind::Symbol, num);
171  }
172  unsigned appendLocalVar(unsigned num = 1) {
173  return appendVar(VarKind::Local, num);
174  }
175 
176 protected:
178 
179  /// Compute an explicit representation for local vars. For all systems coming
180  /// from MLIR integer sets, maps, or expressions where local vars were
181  /// introduced to model floordivs and mods, this always succeeds.
183  MLIRContext *context) const;
184 
185  /// Given an affine map that is aligned with this constraint system:
186  /// * Flatten the map.
187  /// * Add newly introduced local columns at the beginning of this constraint
188  /// system (local column pos 0).
189  /// * Add equalities that define the new local columns to this constraint
190  /// system.
191  /// * Return the flattened expressions via `flattenedExprs`.
192  ///
193  /// Note: This is a shared helper function of `addLowerOrUpperBound` and
194  /// `composeMatchingMap`.
196  AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs);
197 
198  /// Prints the number of constraints, dimensions, symbols and locals in the
199  /// FlatLinearConstraints. Also, prints for each variable whether there is
200  /// an SSA Value attached to it.
201  void printSpace(raw_ostream &os) const override;
202 };
203 
204 /// FlatLinearValueConstraints represents an extension of FlatLinearConstraints
205 /// where each non-local variable can have an SSA Value attached to it.
207 public:
208  /// Constructs a constraint system reserving memory for the specified number
209  /// of constraints and variables. `valArgs` are the optional SSA values
210  /// associated with each dimension/symbol. These must either be empty or match
211  /// the number of dimensions and symbols.
212  FlatLinearValueConstraints(unsigned numReservedInequalities,
213  unsigned numReservedEqualities,
214  unsigned numReservedCols, unsigned numDims,
215  unsigned numSymbols, unsigned numLocals,
216  ArrayRef<std::optional<Value>> valArgs)
217  : FlatLinearConstraints(numReservedInequalities, numReservedEqualities,
218  numReservedCols, numDims, numSymbols, numLocals) {
219  assert(valArgs.empty() || valArgs.size() == getNumDimAndSymbolVars());
220  values.reserve(numReservedCols);
221  if (valArgs.empty())
222  values.resize(getNumDimAndSymbolVars(), std::nullopt);
223  else
224  values.append(valArgs.begin(), valArgs.end());
225  }
226 
227  /// Constructs a constraint system reserving memory for the specified number
228  /// of constraints and variables. `valArgs` are the optional SSA values
229  /// associated with each dimension/symbol. These must either be empty or match
230  /// the number of dimensions and symbols.
231  FlatLinearValueConstraints(unsigned numReservedInequalities,
232  unsigned numReservedEqualities,
233  unsigned numReservedCols, unsigned numDims,
234  unsigned numSymbols, unsigned numLocals,
235  ArrayRef<Value> valArgs)
236  : FlatLinearConstraints(numReservedInequalities, numReservedEqualities,
237  numReservedCols, numDims, numSymbols, numLocals) {
238  assert(valArgs.empty() || valArgs.size() == getNumDimAndSymbolVars());
239  values.reserve(numReservedCols);
240  if (valArgs.empty())
241  values.resize(getNumDimAndSymbolVars(), std::nullopt);
242  else
243  values.append(valArgs.begin(), valArgs.end());
244  }
245 
246  /// Constructs a constraint system with the specified number of dimensions
247  /// and symbols. `valArgs` are the optional SSA values associated with each
248  /// dimension/symbol. These must either be empty or match the number of
249  /// dimensions and symbols.
250  FlatLinearValueConstraints(unsigned numDims, unsigned numSymbols,
251  unsigned numLocals,
252  ArrayRef<std::optional<Value>> valArgs)
253  : FlatLinearValueConstraints(/*numReservedInequalities=*/0,
254  /*numReservedEqualities=*/0,
255  /*numReservedCols=*/numDims + numSymbols +
256  numLocals + 1,
257  numDims, numSymbols, numLocals, valArgs) {}
258 
259  /// Constructs a constraint system with the specified number of dimensions
260  /// and symbols. `valArgs` are the optional SSA values associated with each
261  /// dimension/symbol. These must either be empty or match the number of
262  /// dimensions and symbols.
263  FlatLinearValueConstraints(unsigned numDims = 0, unsigned numSymbols = 0,
264  unsigned numLocals = 0,
265  ArrayRef<Value> valArgs = {})
266  : FlatLinearValueConstraints(/*numReservedInequalities=*/0,
267  /*numReservedEqualities=*/0,
268  /*numReservedCols=*/numDims + numSymbols +
269  numLocals + 1,
270  numDims, numSymbols, numLocals, valArgs) {}
271 
273  ArrayRef<std::optional<Value>> valArgs = {})
274  : FlatLinearConstraints(fac) {
275  assert(valArgs.empty() || valArgs.size() == getNumDimAndSymbolVars());
276  if (valArgs.empty())
277  values.resize(getNumDimAndSymbolVars(), std::nullopt);
278  else
279  values.append(valArgs.begin(), valArgs.end());
280  }
281 
282  /// Creates an affine constraint system from an IntegerSet.
283  explicit FlatLinearValueConstraints(IntegerSet set, ValueRange operands = {});
284 
285  /// Return the kind of this object.
286  Kind getKind() const override { return Kind::FlatLinearValueConstraints; }
287 
288  static bool classof(const IntegerRelation *cst) {
289  return cst->getKind() >= Kind::FlatLinearValueConstraints &&
290  cst->getKind() <= Kind::FlatAffineRelation;
291  }
292 
293  /// Replaces the contents of this FlatLinearValueConstraints with `other`.
294  void clearAndCopyFrom(const IntegerRelation &other) override;
295 
296  /// Adds a constant bound for the variable associated with the given Value.
297  void addBound(presburger::BoundType type, Value val, int64_t value);
299 
300  /// Returns the Value associated with the pos^th variable. Asserts if
301  /// no Value variable was associated.
302  inline Value getValue(unsigned pos) const {
303  assert(pos < getNumDimAndSymbolVars() && "Invalid position");
304  assert(hasValue(pos) && "variable's Value not set");
305  return *values[pos];
306  }
307 
308  /// Returns the Values associated with variables in range [start, end).
309  /// Asserts if no Value was associated with one of these variables.
310  inline void getValues(unsigned start, unsigned end,
312  assert(end <= getNumDimAndSymbolVars() && "invalid end position");
313  assert(start <= end && "invalid start position");
314  values->clear();
315  values->reserve(end - start);
316  for (unsigned i = start; i < end; i++)
317  values->push_back(getValue(i));
318  }
319 
321  return {values.data(), values.size()};
322  }
323 
326  assert(kind != VarKind::Local &&
327  "Local variables do not have any value attached to them.");
328  return {values.data() + getVarKindOffset(kind), getNumVarKind(kind)};
329  }
330 
331  /// Returns true if the pos^th variable has an associated Value.
332  inline bool hasValue(unsigned pos) const {
333  assert(pos < getNumDimAndSymbolVars() && "Invalid position");
334  return values[pos].has_value();
335  }
336 
337  unsigned appendDimVar(ValueRange vals);
339 
340  unsigned appendSymbolVar(ValueRange vals);
342 
343  unsigned insertDimVar(unsigned pos, ValueRange vals);
345 
346  unsigned insertSymbolVar(unsigned pos, ValueRange vals);
348 
349  unsigned insertVar(presburger::VarKind kind, unsigned pos,
350  unsigned num = 1) override;
351  unsigned insertVar(presburger::VarKind kind, unsigned pos, ValueRange vals);
352 
353  /// Removes variables in the column range [varStart, varLimit), and copies any
354  /// remaining valid data into place, updates member variables, and resizes
355  /// arrays as needed.
356  void removeVarRange(presburger::VarKind kind, unsigned varStart,
357  unsigned varLimit) override;
358  using IntegerPolyhedron::removeVarRange;
359 
360  /// Sets the Value associated with the pos^th variable.
361  inline void setValue(unsigned pos, Value val) {
362  assert(pos < getNumDimAndSymbolVars() && "invalid var position");
363  values[pos] = val;
364  }
365 
366  /// Sets the Values associated with the variables in the range [start, end).
367  /// The range must contain only dim and symbol variables.
368  void setValues(unsigned start, unsigned end, ArrayRef<Value> values) {
369  assert(end <= getNumVars() && "invalid end position");
370  assert(start <= end && "invalid start position");
371  assert(values.size() == end - start &&
372  "value should be provided for each variable in the range.");
373  for (unsigned i = start; i < end; ++i)
374  setValue(i, values[i - start]);
375  }
376 
377  /// Looks up the position of the variable with the specified Value starting
378  /// with variables at offset `offset`. Returns true if found (false
379  /// otherwise). `pos` is set to the (column) position of the variable.
380  bool findVar(Value val, unsigned *pos, unsigned offset = 0) const;
381 
382  /// Returns true if a variable with the specified Value exists, false
383  /// otherwise.
384  bool containsVar(Value val) const;
385 
386  /// Projects out the variable that is associate with Value.
387  void projectOut(Value val);
388  using IntegerPolyhedron::projectOut;
389 
390  /// Swap the posA^th variable with the posB^th variable.
391  void swapVar(unsigned posA, unsigned posB) override;
392 
393  /// Prints the number of constraints, dimensions, symbols and locals in the
394  /// FlatAffineValueConstraints. Also, prints for each variable whether there
395  /// is an SSA Value attached to it.
396  void printSpace(raw_ostream &os) const override;
397 
398  /// Align `map` with this constraint system based on `operands`. Each operand
399  /// must already have a corresponding dim/symbol in this constraint system.
400  AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const;
401 
402  /// Merge and align the variables of `this` and `other` starting at
403  /// `offset`, so that both constraint systems get the union of the contained
404  /// variables that is dimension-wise and symbol-wise unique; both
405  /// constraint systems are updated so that they have the union of all
406  /// variables, with `this`'s original variables appearing first followed
407  /// by any of `other`'s variables that didn't appear in `this`. Local
408  /// variables in `other` that have the same division representation as local
409  /// variables in `this` are merged into one.
410  // E.g.: Input: `this` has (%i, %j) [%M, %N]
411  // `other` has (%k, %j) [%P, %N, %M]
412  // Output: both `this`, `other` have (%i, %j, %k) [%M, %N, %P]
413  //
414  void mergeAndAlignVarsWithOther(unsigned offset,
416 
417  /// Merge and align symbols of `this` and `other` such that both get union of
418  /// of symbols that are unique. Symbols in `this` and `other` should be
419  /// unique. Symbols with Value as `None` are considered to be inequal to all
420  /// other symbols.
422 
423  /// Returns true if this constraint system and `other` are in the same
424  /// space, i.e., if they are associated with the same set of variables,
425  /// appearing in the same order. Returns false otherwise.
427 
428  /// Updates the constraints to be the smallest bounding (enclosing) box that
429  /// contains the points of `this` set and that of `other`, with the symbols
430  /// being treated specially. For each of the dimensions, the min of the lower
431  /// bounds (symbolic) and the max of the upper bounds (symbolic) is computed
432  /// to determine such a bounding box. `other` is expected to have the same
433  /// dimensional variables as this constraint system (in the same order).
434  ///
435  /// E.g.:
436  /// 1) this = {0 <= d0 <= 127},
437  /// other = {16 <= d0 <= 192},
438  /// output = {0 <= d0 <= 192}
439  /// 2) this = {s0 + 5 <= d0 <= s0 + 20},
440  /// other = {s0 + 1 <= d0 <= s0 + 9},
441  /// output = {s0 + 1 <= d0 <= s0 + 20}
442  /// 3) this = {0 <= d0 <= 5, 1 <= d1 <= 9}
443  /// other = {2 <= d0 <= 6, 5 <= d1 <= 15},
444  /// output = {0 <= d0 <= 6, 1 <= d1 <= 15}
446  using IntegerPolyhedron::unionBoundingBox;
447 
448 protected:
449  /// Eliminates the variable at the specified position using Fourier-Motzkin
450  /// variable elimination, but uses Gaussian elimination if there is an
451  /// equality involving that variable. If the result of the elimination is
452  /// integer exact, `*isResultIntegerExact` is set to true. If `darkShadow` is
453  /// set to true, a potential under approximation (subset) of the rational
454  /// shadow / exact integer shadow is computed.
455  // See implementation comments for more details.
456  void fourierMotzkinEliminate(unsigned pos, bool darkShadow = false,
457  bool *isResultIntegerExact = nullptr) override;
458 
459  /// Returns false if the fields corresponding to various variable counts, or
460  /// equality/inequality buffer sizes aren't consistent; true otherwise. This
461  /// is meant to be used within an assert internally.
462  bool hasConsistentState() const override;
463 
464  /// Values corresponding to the (column) non-local variables of this
465  /// constraint system appearing in the order the variables correspond to
466  /// columns. Variables that aren't associated with any Value are set to
467  /// std::nullopt.
469 };
470 
471 /// Flattens 'expr' into 'flattenedExpr', which contains the coefficients of the
472 /// dimensions, symbols, and additional variables that represent floor divisions
473 /// of dimensions, symbols, and in turn other floor divisions. Returns failure
474 /// if 'expr' could not be flattened (i.e., semi-affine is not yet handled).
475 /// 'cst' contains constraints that connect newly introduced local variables
476 /// to existing dimensional and symbolic variables. See documentation for
477 /// AffineExprFlattener on how mod's and div's are flattened.
478 LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims,
479  unsigned numSymbols,
480  SmallVectorImpl<int64_t> *flattenedExpr,
481  FlatLinearConstraints *cst = nullptr);
482 
483 /// Flattens the result expressions of the map to their corresponding flattened
484 /// forms and set in 'flattenedExprs'. Returns failure if any expression in the
485 /// map could not be flattened (i.e., semi-affine is not yet handled). 'cst'
486 /// contains constraints that connect newly introduced local variables to
487 /// existing dimensional and / symbolic variables. See documentation for
488 /// AffineExprFlattener on how mod's and div's are flattened. For all affine
489 /// expressions that share the same operands (like those of an affine map), this
490 /// method should be used instead of repeatedly calling getFlattenedAffineExpr
491 /// since local variables added to deal with div's and mod's will be reused
492 /// across expressions.
495  std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
496  FlatLinearConstraints *cst = nullptr);
499  std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
500  FlatLinearConstraints *cst = nullptr);
501 
505 
506 /// Re-indexes the dimensions and symbols of an affine map with given `operands`
507 /// values to align with `dims` and `syms` values.
508 ///
509 /// Each dimension/symbol of the map, bound to an operand `o`, is replaced with
510 /// dimension `i`, where `i` is the position of `o` within `dims`. If `o` is not
511 /// in `dims`, replace it with symbol `i`, where `i` is the position of `o`
512 /// within `syms`. If `o` is not in `syms` either, replace it with a new symbol.
513 ///
514 /// Note: If a value appears multiple times as a dimension/symbol (or both), all
515 /// corresponding dim/sym expressions are replaced with the first dimension
516 /// bound to that value (or first symbol if no such dimension exists).
517 ///
518 /// The resulting affine map has `dims.size()` many dimensions and at least
519 /// `syms.size()` many symbols.
520 ///
521 /// The SSA values of the symbols of the resulting map are optionally returned
522 /// via `newSyms`. This is a concatenation of `syms` with the SSA values of the
523 /// newly added symbols.
524 ///
525 /// Note: As part of this re-indexing, dimensions may turn into symbols, or vice
526 /// versa.
528  ValueRange dims, ValueRange syms,
529  SmallVector<Value> *newSyms = nullptr);
530 
531 } // namespace mlir
532 
533 #endif // MLIR_ANALYSIS_FLATLINEARVALUECONSTRAINTS_H
Base type for affine expression.
Definition: AffineExpr.h:68
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
Definition: AffineMap.h:47
FlatLinearConstraints is an extension of IntegerPolyhedron.
unsigned appendDimVar(unsigned num=1)
Append variables of the specified kind after the last variable of that kind.
IntegerSet getAsIntegerSet(MLIRContext *context) const
Returns the constraint system as an integer set.
FlatLinearConstraints(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals)
Constructs a constraint system reserving memory for the specified number of constraints and variables...
FlatLinearConstraints(unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0)
Constructs a constraint system with the specified number of dimensions and symbols.
unsigned insertSymbolVar(unsigned pos, unsigned num=1)
unsigned appendLocalVar(unsigned num=1)
LogicalResult flattenAlignedMapAndMergeLocals(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs)
Given an affine map that is aligned with this constraint system:
void printSpace(raw_ostream &os) const override
Prints the number of constraints, dimensions, symbols and locals in the FlatLinearConstraints.
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
FlatLinearConstraints(const IntegerPolyhedron &fac)
LogicalResult composeMatchingMap(AffineMap other)
Composes an affine map whose dimensions and symbols match one to one with the dimensions and symbols ...
unsigned appendSymbolVar(unsigned num=1)
void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context, SmallVectorImpl< AffineMap > *lbMaps, SmallVectorImpl< AffineMap > *ubMaps, bool closedUB=false)
Computes the lower and upper bounds of the first num dimensional variables (starting at offset) as an...
std::pair< AffineMap, AffineMap > getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num, unsigned symStartPos, ArrayRef< AffineExpr > localExprs, MLIRContext *context, bool closedUB=false) const
Gets the lower and upper bound of the offset + posth variable treating [0, offset) U [offset + num,...
unsigned insertLocalVar(unsigned pos, unsigned num=1)
LogicalResult computeLocalVars(SmallVectorImpl< AffineExpr > &memo, MLIRContext *context) const
Compute an explicit representation for local vars.
Kind getKind() const override
Return the kind of this object.
unsigned insertDimVar(unsigned pos, unsigned num=1)
Insert variables of the specified kind at position pos.
FlatLinearValueConstraints represents an extension of FlatLinearConstraints where each non-local vari...
unsigned appendDimVar(unsigned num=1)
Append variables of the specified kind after the last variable of that kind.
void clearAndCopyFrom(const IntegerRelation &other) override
Replaces the contents of this FlatLinearValueConstraints with other.
ArrayRef< std::optional< Value > > getMaybeValues(presburger::VarKind kind) const
void swapVar(unsigned posA, unsigned posB) override
Swap the posA^th variable with the posB^th variable.
FlatLinearValueConstraints(unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0, ArrayRef< Value > valArgs={})
Constructs a constraint system with the specified number of dimensions and symbols.
FlatLinearValueConstraints(unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef< std::optional< Value >> valArgs)
Constructs a constraint system with the specified number of dimensions and symbols.
LogicalResult unionBoundingBox(const FlatLinearValueConstraints &other)
Updates the constraints to be the smallest bounding (enclosing) box that contains the points of this ...
void mergeAndAlignVarsWithOther(unsigned offset, FlatLinearValueConstraints *other)
Merge and align the variables of this and other starting at offset, so that both constraint systems g...
unsigned insertSymbolVar(unsigned pos, unsigned num=1)
void fourierMotzkinEliminate(unsigned pos, bool darkShadow=false, bool *isResultIntegerExact=nullptr) override
Eliminates the variable at the specified position using Fourier-Motzkin variable elimination,...
SmallVector< std::optional< Value >, 8 > values
Values corresponding to the (column) non-local variables of this constraint system appearing in the o...
bool hasValue(unsigned pos) const
Returns true if the pos^th variable has an associated Value.
static bool classof(const IntegerRelation *cst)
FlatLinearValueConstraints(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef< Value > valArgs)
Constructs a constraint system reserving memory for the specified number of constraints and variables...
Value getValue(unsigned pos) const
Returns the Value associated with the pos^th variable.
void printSpace(raw_ostream &os) const override
Prints the number of constraints, dimensions, symbols and locals in the FlatAffineValueConstraints.
void mergeSymbolVars(FlatLinearValueConstraints &other)
Merge and align symbols of this and other such that both get union of of symbols that are unique.
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
FlatLinearValueConstraints(const IntegerPolyhedron &fac, ArrayRef< std::optional< Value >> valArgs={})
void projectOut(Value val)
Projects out the variable that is associate with Value.
bool containsVar(Value val) const
Returns true if a variable with the specified Value exists, false otherwise.
bool hasConsistentState() const override
Returns false if the fields corresponding to various variable counts, or equality/inequality buffer s...
void removeVarRange(presburger::VarKind kind, unsigned varStart, unsigned varLimit) override
Removes variables in the column range [varStart, varLimit), and copies any remaining valid data into ...
bool findVar(Value val, unsigned *pos, unsigned offset=0) const
Looks up the position of the variable with the specified Value starting with variables at offset offs...
ArrayRef< std::optional< Value > > getMaybeValues() const
bool areVarsAlignedWithOther(const FlatLinearConstraints &other)
Returns true if this constraint system and other are in the same space, i.e., if they are associated ...
AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const
Align map with this constraint system based on operands.
void getValues(unsigned start, unsigned end, SmallVectorImpl< Value > *values) const
Returns the Values associated with variables in range [start, end).
FlatLinearValueConstraints(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef< std::optional< Value >> valArgs)
Constructs a constraint system reserving memory for the specified number of constraints and variables...
void setValue(unsigned pos, Value val)
Sets the Value associated with the pos^th variable.
unsigned insertDimVar(unsigned pos, unsigned num=1)
Insert variables of the specified kind at position pos.
unsigned insertVar(presburger::VarKind kind, unsigned pos, unsigned num=1) override
Insert num variables of the specified kind at position pos.
Kind getKind() const override
Return the kind of this object.
void setValues(unsigned start, unsigned end, ArrayRef< Value > values)
Sets the Values associated with the variables in the range [start, end).
An integer set representing a conjunction of one or more affine equalities and inequalities.
Definition: IntegerSet.h:44
MLIRContext is the top-level object for a collection of MLIR operations.
Definition: MLIRContext.h:60
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:378
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
An IntegerPolyhedron represents the set of points from a PresburgerSpace that satisfy a list of affin...
unsigned insertVar(VarKind kind, unsigned pos, unsigned num=1) override
Insert num variables of the specified kind at position pos.
IntegerPolyhedron(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, const PresburgerSpace &space)
Constructs a set reserving memory for the specified number of constraints and variables.
Kind
All derived classes of IntegerRelation.
unsigned getNumVarKind(VarKind kind) const
Get the number of vars of the specified kind.
unsigned appendVar(VarKind kind, unsigned num=1)
Append num variables of the specified kind after the last variable of that kind.
IntegerRelation(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, const PresburgerSpace &space)
Constructs a relation reserving memory for the specified number of constraints and variables.
unsigned getVarKindOffset(VarKind kind) const
Return the index at which the specified kind of vars starts.
This class represents a multi-affine function with the domain as Z^d, where d is the number of domain...
Definition: PWMAFunction.h:41
BoundType
The type of bound: equal, lower bound or upper bound.
VarKind
Kind of variable.
Include the generated interface declarations.
AffineMap alignAffineMapWithValues(AffineMap map, ValueRange operands, ValueRange dims, ValueRange syms, SmallVector< Value > *newSyms=nullptr)
Re-indexes the dimensions and symbols of an affine map with given operands values to align with dims ...
LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols, SmallVectorImpl< int64_t > *flattenedExpr, FlatLinearConstraints *cst=nullptr)
Flattens 'expr' into 'flattenedExpr', which contains the coefficients of the dimensions,...
LogicalResult getFlattenedAffineExprs(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatLinearConstraints *cst=nullptr)
Flattens the result expressions of the map to their corresponding flattened forms and set in 'flatten...
LogicalResult getMultiAffineFunctionFromMap(AffineMap map, presburger::MultiAffineFunction &multiAff)
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26