MLIR  21.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"
16 #include <optional>
17 
18 namespace mlir {
19 
20 class AffineMap;
21 class IntegerSet;
22 class MLIRContext;
23 class Value;
24 class MemRefType;
25 struct MutableAffineMap;
26 
27 namespace presburger {
29 } // namespace presburger
30 
31 /// FlatLinearConstraints is an extension of IntegerPolyhedron. It provides an
32 /// AffineExpr-based API.
34 public:
35  /// Constructs a constraint system reserving memory for the specified number
36  /// of constraints and variables. `valArgs` are the optional SSA values
37  /// associated with each dimension/symbol. These must either be empty or match
38  /// the number of dimensions and symbols.
39  FlatLinearConstraints(unsigned numReservedInequalities,
40  unsigned numReservedEqualities,
41  unsigned numReservedCols, unsigned numDims,
42  unsigned numSymbols, unsigned numLocals)
43  : IntegerPolyhedron(numReservedInequalities, numReservedEqualities,
44  numReservedCols,
45  presburger::PresburgerSpace::getSetSpace(
46  numDims, numSymbols, numLocals)) {
47  assert(numReservedCols >= getNumVars() + 1);
48  }
49 
50  /// Constructs a constraint system with the specified number of dimensions
51  /// and symbols. `valArgs` are the optional SSA values associated with each
52  /// dimension/symbol. These must either be empty or match the number of
53  /// dimensions and symbols.
54  FlatLinearConstraints(unsigned numDims = 0, unsigned numSymbols = 0,
55  unsigned numLocals = 0)
56  : FlatLinearConstraints(/*numReservedInequalities=*/0,
57  /*numReservedEqualities=*/0,
58  /*numReservedCols=*/numDims + numSymbols +
59  numLocals + 1,
60  numDims, numSymbols, numLocals) {}
61 
63  : IntegerPolyhedron(fac) {}
64 
65  /// Return the kind of this object.
66  Kind getKind() const override { return Kind::FlatLinearConstraints; }
67 
68  /// Flag to control if conservative semi-affine bounds should be added in
69  /// `addBound()`.
70  enum class AddConservativeSemiAffineBounds { No = 0, Yes };
71 
72  /// Adds a bound for the variable at the specified position with constraints
73  /// being drawn from the specified bound map. In case of an EQ bound, the
74  /// bound map is expected to have exactly one result. In case of a LB/UB, the
75  /// bound map may have more than one result, for each of which an inequality
76  /// is added.
77  ///
78  /// The bound can be added as open or closed by specifying isClosedBound. In
79  /// case of a LB/UB, isClosedBound = false means the bound is added internally
80  /// as a closed bound by +1/-1 respectively. In case of an EQ bound, it can
81  /// only be added as a closed bound.
82  ///
83  /// Conservative bounds for semi-affine expressions will be added if
84  /// `AddConservativeSemiAffineBounds` is set to `Yes`. This currently only
85  /// covers semi-affine `mod` expressions, so `addBound()` will still fail if
86  /// it encounters a semi-affine `floordiv`, `ceildiv`, or `mul`. Note: If
87  /// enabled it is possible for the resulting constraint set to become empty if
88  /// a precondition of a conservative bound is found not to hold.
89  ///
90  /// Note: The dimensions/symbols of this FlatLinearConstraints must match the
91  /// dimensions/symbols of the affine map.
92  LogicalResult addBound(
93  presburger::BoundType type, unsigned pos, AffineMap boundMap,
94  bool isClosedBound,
96 
97  /// Adds a bound for the variable at the specified position with constraints
98  /// being drawn from the specified bound map. In case of an EQ bound, the
99  /// bound map is expected to have exactly one result. In case of a LB/UB, the
100  /// bound map may have more than one result, for each of which an inequality
101  /// is added.
102  ///
103  /// Conservative bounds for semi-affine expressions will be added if
104  /// `AddConservativeSemiAffineBounds` is set to `Yes`. This currently only
105  /// covers semi-affine `mod` expressions, so `addBound()` will still fail if
106  /// it encounters a semi-affine `floordiv`, `ceildiv`, or `mul`. Note: If
107  /// enabled it is possible for the resulting constraint set to become empty if
108  /// a precondition of a conservative bound is found not to hold.
109  ///
110  /// Note: The dimensions/symbols of this FlatLinearConstraints must match the
111  /// dimensions/symbols of the affine map. By default the lower bound is closed
112  /// and the upper bound is open.
113  LogicalResult addBound(
114  presburger::BoundType type, unsigned pos, AffineMap boundMap,
116 
117  /// The `addBound` overload above hides the inherited overloads by default, so
118  /// we explicitly introduce them here.
119  using IntegerPolyhedron::addBound;
120 
121  /// Returns a non-negative constant bound on the extent (upper bound - lower
122  /// bound) of the specified variable if it is found to be a constant; returns
123  /// std::nullopt if it's not a constant. This method treats symbolic
124  /// variables specially, i.e., it looks for constant differences between
125  /// affine expressions involving only the symbolic variables. 'lb', if
126  /// provided, is set to the lower bound map associated with the constant
127  /// difference, and similarly, `ub` to the upper bound. Note that 'lb', 'ub'
128  /// are purely symbolic and will correspond to the symbolic variables of the
129  /// constaint set.
130  // Egs: 0 <= i <= 15, return 16.
131  // s0 + 2 <= i <= s0 + 17, returns 16. (s0 has to be a symbol)
132  // s0 + s1 + 16 <= d0 <= s0 + s1 + 31, returns 16.
133  // s0 - 7 <= 8*j <= s0 returns 1 with lb = s0, lbDivisor = 8 (since lb =
134  // ceil(s0 - 7 / 8) = floor(s0 / 8)).
135  /// The difference between this method and
136  /// IntegerRelation::getConstantBoundOnDimSize is that unlike the latter, this
137  /// makes use of affine expressions and maps in its inference and provides
138  /// output with affine maps; it thus handles local variables by detecting them
139  /// as affine functions of the symbols when possible.
140  std::optional<int64_t>
141  getConstantBoundOnDimSize(MLIRContext *context, unsigned pos,
142  AffineMap *lb = nullptr, AffineMap *ub = nullptr,
143  unsigned *minLbPos = nullptr,
144  unsigned *minUbPos = nullptr) const;
145 
146  /// Returns the constraint system as an integer set. Returns a null integer
147  /// set if the system has no constraints, or if an integer set couldn't be
148  /// constructed as a result of a local variable's explicit representation not
149  /// being known and such a local variable appearing in any of the constraints.
150  IntegerSet getAsIntegerSet(MLIRContext *context) const;
151 
152  /// Computes the lower and upper bounds of the first `num` dimensional
153  /// variables (starting at `offset`) as an affine map of the remaining
154  /// variables (dimensional and symbolic). This method is able to detect
155  /// variables as floordiv's and mod's of affine expressions of other
156  /// variables with respect to (positive) constants. Sets bound map to a
157  /// null AffineMap if such a bound can't be found (or yet unimplemented).
158  ///
159  /// By default the returned lower bounds are closed and upper bounds are open.
160  /// If `closedUb` is true, the upper bound is closed.
161  void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context,
164  bool closedUB = false);
165 
166  /// Composes an affine map whose dimensions and symbols match one to one with
167  /// the dimensions and symbols of this FlatLinearConstraints. The results of
168  /// the map `other` are added as the leading dimensions of this constraint
169  /// system. Returns failure if `other` is a semi-affine map.
170  LogicalResult composeMatchingMap(AffineMap other);
171 
172  /// Gets the lower and upper bound of the `offset` + `pos`th variable
173  /// treating [0, offset) U [offset + num, symStartPos) as dimensions and
174  /// [symStartPos, getNumDimAndSymbolVars) as symbols, and `pos` lies in
175  /// [0, num). The multi-dimensional maps in the returned pair represent the
176  /// max and min of potentially multiple affine expressions. `localExprs` holds
177  /// pre-computed AffineExpr's for all local variables in the system.
178  ///
179  /// By default the returned lower bounds are closed and upper bounds are open.
180  /// If `closedUb` is true, the upper bound is closed.
181  std::pair<AffineMap, AffineMap>
182  getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num,
183  unsigned symStartPos, ArrayRef<AffineExpr> localExprs,
184  MLIRContext *context, bool closedUB = false) const;
185 
186  /// Insert variables of the specified kind at position `pos`. Positions are
187  /// relative to the kind of variable. The coefficient columns corresponding
188  /// to the added variables are initialized to zero. `vals` are the Values
189  /// corresponding to the variables. Values should not be used with
190  /// VarKind::Local since values can only be attached to non-local variables.
191  /// Return the absolute column position (i.e., not relative to the kind of
192  /// variable) of the first added variable.
193  ///
194  /// Note: Empty Values are allowed in `vals`.
195  unsigned insertDimVar(unsigned pos, unsigned num = 1) {
196  return insertVar(VarKind::SetDim, pos, num);
197  }
198  unsigned insertSymbolVar(unsigned pos, unsigned num = 1) {
199  return insertVar(VarKind::Symbol, pos, num);
200  }
201  unsigned insertLocalVar(unsigned pos, unsigned num = 1) {
202  return insertVar(VarKind::Local, pos, num);
203  }
204 
205  /// Append variables of the specified kind after the last variable of that
206  /// kind. The coefficient columns corresponding to the added variables are
207  /// initialized to zero. `vals` are the Values corresponding to the
208  /// variables. Return the absolute column position (i.e., not relative to the
209  /// kind of variable) of the first appended variable.
210  ///
211  /// Note: Empty Values are allowed in `vals`.
212  unsigned appendDimVar(unsigned num = 1) {
213  return appendVar(VarKind::SetDim, num);
214  }
215  unsigned appendSymbolVar(unsigned num = 1) {
216  return appendVar(VarKind::Symbol, num);
217  }
218  unsigned appendLocalVar(unsigned num = 1) {
219  return appendVar(VarKind::Local, num);
220  }
221 
222  /// A more human-readable version of dump().
223  void dumpPretty() const;
224  /// An easier to read dump of a `row` of the same width as the number of
225  /// columns. `fixedColWidth` ensure that even with a zero coefficient, we
226  /// print spaces so that variables are aligned.
227  void dumpRow(ArrayRef<int64_t> row, bool fixedColWidth = true) const;
228 
229 protected:
231 
232  /// Compute an explicit representation for local vars. For all systems coming
233  /// from MLIR integer sets, maps, or expressions where local vars were
234  /// introduced to model floordivs and mods, this always succeeds.
235  LogicalResult computeLocalVars(SmallVectorImpl<AffineExpr> &memo,
236  MLIRContext *context) const;
237 
238  /// Given an affine map that is aligned with this constraint system:
239  /// * Flatten the map.
240  /// * Add newly introduced local columns at the beginning of this constraint
241  /// system (local column pos 0).
242  /// * Add equalities that define the new local columns to this constraint
243  /// system.
244  /// * Return the flattened expressions via `flattenedExprs`.
245  ///
246  /// Note: This is a shared helper function of `addLowerOrUpperBound` and
247  /// `composeMatchingMap`.
248  LogicalResult flattenAlignedMapAndMergeLocals(
249  AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
250  bool addConservativeSemiAffineBounds = false);
251 
252  /// Prints the number of constraints, dimensions, symbols and locals in the
253  /// FlatLinearConstraints. Also, prints for each variable whether there is
254  /// an SSA Value attached to it.
255  void printSpace(raw_ostream &os) const override;
256 };
257 
258 /// FlatLinearValueConstraints represents an extension of FlatLinearConstraints
259 /// where each non-local variable can have an SSA Value attached to it.
261 public:
262  /// The SSA Values attached to each non-local variable are stored as
263  /// identifiers in the constraint system's space.
265 
266  /// Constructs a constraint system reserving memory for the specified number
267  /// of constraints and variables. `valArgs` are the optional SSA values
268  /// associated with each dimension/symbol. These must either be empty or match
269  /// the number of dimensions and symbols.
270  FlatLinearValueConstraints(unsigned numReservedInequalities,
271  unsigned numReservedEqualities,
272  unsigned numReservedCols, unsigned numDims,
273  unsigned numSymbols, unsigned numLocals,
274  ArrayRef<std::optional<Value>> valArgs)
275  : FlatLinearConstraints(numReservedInequalities, numReservedEqualities,
276  numReservedCols, numDims, numSymbols, numLocals) {
277  assert(valArgs.empty() || valArgs.size() == getNumDimAndSymbolVars());
278  for (unsigned i = 0, e = valArgs.size(); i < e; ++i)
279  if (valArgs[i])
280  setValue(i, *valArgs[i]);
281  }
282 
283  /// Constructs a constraint system reserving memory for the specified number
284  /// of constraints and variables. `valArgs` are the optional SSA values
285  /// associated with each dimension/symbol. These must either be empty or match
286  /// the number of dimensions and symbols.
287  FlatLinearValueConstraints(unsigned numReservedInequalities,
288  unsigned numReservedEqualities,
289  unsigned numReservedCols, unsigned numDims,
290  unsigned numSymbols, unsigned numLocals,
291  ArrayRef<Value> valArgs)
292  : FlatLinearConstraints(numReservedInequalities, numReservedEqualities,
293  numReservedCols, numDims, numSymbols, numLocals) {
294  assert(valArgs.empty() || valArgs.size() == getNumDimAndSymbolVars());
295  for (unsigned i = 0, e = valArgs.size(); i < e; ++i)
296  if (valArgs[i])
297  setValue(i, valArgs[i]);
298  }
299 
300  /// Constructs a constraint system with the specified number of dimensions
301  /// and symbols. `valArgs` are the optional SSA values associated with each
302  /// dimension/symbol. These must either be empty or match the number of
303  /// dimensions and symbols.
304  FlatLinearValueConstraints(unsigned numDims, unsigned numSymbols,
305  unsigned numLocals,
306  ArrayRef<std::optional<Value>> valArgs)
307  : FlatLinearValueConstraints(/*numReservedInequalities=*/0,
308  /*numReservedEqualities=*/0,
309  /*numReservedCols=*/numDims + numSymbols +
310  numLocals + 1,
311  numDims, numSymbols, numLocals, valArgs) {}
312 
313  /// Constructs a constraint system with the specified number of dimensions
314  /// and symbols. `valArgs` are the optional SSA values associated with each
315  /// dimension/symbol. These must either be empty or match the number of
316  /// dimensions and symbols.
317  FlatLinearValueConstraints(unsigned numDims = 0, unsigned numSymbols = 0,
318  unsigned numLocals = 0,
319  ArrayRef<Value> valArgs = {})
320  : FlatLinearValueConstraints(/*numReservedInequalities=*/0,
321  /*numReservedEqualities=*/0,
322  /*numReservedCols=*/numDims + numSymbols +
323  numLocals + 1,
324  numDims, numSymbols, numLocals, valArgs) {}
325 
327  ArrayRef<std::optional<Value>> valArgs = {})
328  : FlatLinearConstraints(fac) {
329  if (valArgs.empty())
330  return;
331  assert(valArgs.size() == getNumDimAndSymbolVars());
332  for (unsigned i = 0, e = valArgs.size(); i < e; ++i)
333  if (valArgs[i])
334  setValue(i, *valArgs[i]);
335  }
336 
337  /// Creates an affine constraint system from an IntegerSet.
338  explicit FlatLinearValueConstraints(IntegerSet set, ValueRange operands = {});
339 
340  /// Return the kind of this object.
341  Kind getKind() const override { return Kind::FlatLinearValueConstraints; }
342 
343  static bool classof(const IntegerRelation *cst) {
344  return cst->getKind() >= Kind::FlatLinearValueConstraints &&
345  cst->getKind() <= Kind::FlatAffineRelation;
346  }
347 
348  /// Adds a constant bound for the variable associated with the given Value.
349  void addBound(presburger::BoundType type, Value val, int64_t value);
351 
352  /// Returns the Value associated with the pos^th variable. Asserts if
353  /// no Value variable was associated.
354  inline Value getValue(unsigned pos) const {
355  assert(pos < getNumDimAndSymbolVars() && "Invalid position");
356  assert(hasValue(pos) && "variable's Value not set");
357  VarKind kind = getVarKindAt(pos);
358  unsigned relativePos = pos - getVarKindOffset(kind);
359  return space.getId(kind, relativePos).getValue<Value>();
360  }
361 
362  /// Returns the Values associated with variables in range [start, end).
363  /// Asserts if no Value was associated with one of these variables.
364  inline void getValues(unsigned start, unsigned end,
365  SmallVectorImpl<Value> *values) const {
366  assert(end <= getNumDimAndSymbolVars() && "invalid end position");
367  assert(start <= end && "invalid start position");
368  values->clear();
369  values->reserve(end - start);
370  for (unsigned i = start; i < end; ++i)
371  values->push_back(getValue(i));
372  }
373 
376  maybeValues.reserve(getNumDimAndSymbolVars());
377  for (unsigned i = 0, e = getNumDimAndSymbolVars(); i < e; ++i)
378  if (hasValue(i)) {
379  maybeValues.push_back(getValue(i));
380  } else {
381  maybeValues.push_back(std::nullopt);
382  }
383  return maybeValues;
384  }
385 
388  assert(kind != VarKind::Local &&
389  "Local variables do not have any value attached to them.");
391  maybeValues.reserve(getNumVarKind(kind));
392  const unsigned offset = space.getVarKindOffset(kind);
393  for (unsigned i = 0, e = getNumVarKind(kind); i < e; ++i) {
394  if (hasValue(offset + i))
395  maybeValues.push_back(getValue(offset + i));
396  else
397  maybeValues.push_back(std::nullopt);
398  }
399  return maybeValues;
400  }
401 
402  /// Returns true if the pos^th variable has an associated Value.
403  inline bool hasValue(unsigned pos) const {
404  assert(pos < getNumDimAndSymbolVars() && "Invalid position");
405  VarKind kind = getVarKindAt(pos);
406  unsigned relativePos = pos - getVarKindOffset(kind);
407  return space.getId(kind, relativePos).hasValue();
408  }
409 
410  unsigned appendDimVar(ValueRange vals);
412 
413  unsigned appendSymbolVar(ValueRange vals);
415 
416  unsigned insertDimVar(unsigned pos, ValueRange vals);
418 
419  unsigned insertSymbolVar(unsigned pos, ValueRange vals);
421 
422  unsigned insertVar(presburger::VarKind kind, unsigned pos,
423  unsigned num = 1) override;
424  unsigned insertVar(presburger::VarKind kind, unsigned pos, ValueRange vals);
425 
426  /// Removes variables in the column range [varStart, varLimit), and copies any
427  /// remaining valid data into place, updates member variables, and resizes
428  /// arrays as needed.
429  void removeVarRange(presburger::VarKind kind, unsigned varStart,
430  unsigned varLimit) override;
431  using IntegerPolyhedron::removeVarRange;
432 
433  /// Sets the Value associated with the pos^th variable.
434  /// Stores the Value in the space's identifiers.
435  inline void setValue(unsigned pos, Value val) {
436  assert(pos < getNumDimAndSymbolVars() && "invalid var position");
437  VarKind kind = getVarKindAt(pos);
438  unsigned relativePos = pos - getVarKindOffset(kind);
439  space.setId(kind, relativePos, presburger::Identifier(val));
440  }
441 
442  /// Sets the Values associated with the variables in the range [start, end).
443  /// The range must contain only dim and symbol variables.
444  void setValues(unsigned start, unsigned end, ArrayRef<Value> values) {
445  assert(end <= getNumVars() && "invalid end position");
446  assert(start <= end && "invalid start position");
447  assert(values.size() == end - start &&
448  "value should be provided for each variable in the range.");
449  for (unsigned i = start; i < end; ++i)
450  setValue(i, values[i - start]);
451  }
452 
453  /// Looks up the position of the variable with the specified Value starting
454  /// with variables at offset `offset`. Returns true if found (false
455  /// otherwise). `pos` is set to the (column) position of the variable.
456  bool findVar(Value val, unsigned *pos, unsigned offset = 0) const;
457 
458  /// Returns true if a variable with the specified Value exists, false
459  /// otherwise.
460  bool containsVar(Value val) const;
461 
462  /// Projects out the variable that is associate with Value.
463  void projectOut(Value val);
464  using IntegerPolyhedron::projectOut;
465 
466  /// Prints the number of constraints, dimensions, symbols and locals in the
467  /// FlatAffineValueConstraints. Also, prints for each variable whether there
468  /// is an SSA Value attached to it.
469  void printSpace(raw_ostream &os) const override;
470 
471  /// Align `map` with this constraint system based on `operands`. Each operand
472  /// must already have a corresponding dim/symbol in this constraint system.
473  AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const;
474 
475  /// Merge and align the variables of `this` and `other` starting at
476  /// `offset`, so that both constraint systems get the union of the contained
477  /// variables that is dimension-wise and symbol-wise unique; both
478  /// constraint systems are updated so that they have the union of all
479  /// variables, with `this`'s original variables appearing first followed
480  /// by any of `other`'s variables that didn't appear in `this`. Local
481  /// variables in `other` that have the same division representation as local
482  /// variables in `this` are merged into one.
483  // E.g.: Input: `this` has (%i, %j) [%M, %N]
484  // `other` has (%k, %j) [%P, %N, %M]
485  // Output: both `this`, `other` have (%i, %j, %k) [%M, %N, %P]
486  //
487  void mergeAndAlignVarsWithOther(unsigned offset,
489 
490  /// Merge and align symbols of `this` and `other` such that both get union of
491  /// of symbols that are unique. Symbols in `this` and `other` should be
492  /// unique. Symbols with Value as `None` are considered to be inequal to all
493  /// other symbols.
495 
496  /// Returns true if this constraint system and `other` are in the same
497  /// space, i.e., if they are associated with the same set of variables,
498  /// appearing in the same order. Returns false otherwise.
500 
501  /// Updates the constraints to be the smallest bounding (enclosing) box that
502  /// contains the points of `this` set and that of `other`, with the symbols
503  /// being treated specially. For each of the dimensions, the min of the lower
504  /// bounds (symbolic) and the max of the upper bounds (symbolic) is computed
505  /// to determine such a bounding box. `other` is expected to have the same
506  /// dimensional variables as this constraint system (in the same order).
507  ///
508  /// E.g.:
509  /// 1) this = {0 <= d0 <= 127},
510  /// other = {16 <= d0 <= 192},
511  /// output = {0 <= d0 <= 192}
512  /// 2) this = {s0 + 5 <= d0 <= s0 + 20},
513  /// other = {s0 + 1 <= d0 <= s0 + 9},
514  /// output = {s0 + 1 <= d0 <= s0 + 20}
515  /// 3) this = {0 <= d0 <= 5, 1 <= d1 <= 9}
516  /// other = {2 <= d0 <= 6, 5 <= d1 <= 15},
517  /// output = {0 <= d0 <= 6, 1 <= d1 <= 15}
518  LogicalResult unionBoundingBox(const FlatLinearValueConstraints &other);
519  using IntegerPolyhedron::unionBoundingBox;
520 };
521 
522 /// Flattens 'expr' into 'flattenedExpr', which contains the coefficients of the
523 /// dimensions, symbols, and additional variables that represent floor divisions
524 /// of dimensions, symbols, and in turn other floor divisions. Returns failure
525 /// if 'expr' could not be flattened (i.e., an unhandled semi-affine was found).
526 /// 'cst' contains constraints that connect newly introduced local variables
527 /// to existing dimensional and symbolic variables. See documentation for
528 /// AffineExprFlattener on how mod's and div's are flattened.
529 LogicalResult
530 getFlattenedAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols,
531  SmallVectorImpl<int64_t> *flattenedExpr,
532  FlatLinearConstraints *cst = nullptr,
533  bool addConservativeSemiAffineBounds = false);
534 
535 /// Flattens the result expressions of the map to their corresponding flattened
536 /// forms and set in 'flattenedExprs'. Returns failure if any expression in the
537 /// map could not be flattened (i.e., an unhandled semi-affine was found). 'cst'
538 /// contains constraints that connect newly introduced local variables to
539 /// existing dimensional and / symbolic variables. See documentation for
540 /// AffineExprFlattener on how mod's and div's are flattened. For all affine
541 /// expressions that share the same operands (like those of an affine map), this
542 /// method should be used instead of repeatedly calling getFlattenedAffineExpr
543 /// since local variables added to deal with div's and mod's will be reused
544 /// across expressions.
545 LogicalResult
546 getFlattenedAffineExprs(AffineMap map,
547  std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
548  FlatLinearConstraints *cst = nullptr,
549  bool addConservativeSemiAffineBounds = false);
550 LogicalResult
551 getFlattenedAffineExprs(IntegerSet set,
552  std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
553  FlatLinearConstraints *cst = nullptr);
554 
555 LogicalResult
556 getMultiAffineFunctionFromMap(AffineMap map,
557  presburger::MultiAffineFunction &multiAff);
558 
559 /// Re-indexes the dimensions and symbols of an affine map with given `operands`
560 /// values to align with `dims` and `syms` values.
561 ///
562 /// Each dimension/symbol of the map, bound to an operand `o`, is replaced with
563 /// dimension `i`, where `i` is the position of `o` within `dims`. If `o` is not
564 /// in `dims`, replace it with symbol `i`, where `i` is the position of `o`
565 /// within `syms`. If `o` is not in `syms` either, replace it with a new symbol.
566 ///
567 /// Note: If a value appears multiple times as a dimension/symbol (or both), all
568 /// corresponding dim/sym expressions are replaced with the first dimension
569 /// bound to that value (or first symbol if no such dimension exists).
570 ///
571 /// The resulting affine map has `dims.size()` many dimensions and at least
572 /// `syms.size()` many symbols.
573 ///
574 /// The SSA values of the symbols of the resulting map are optionally returned
575 /// via `newSyms`. This is a concatenation of `syms` with the SSA values of the
576 /// newly added symbols.
577 ///
578 /// Note: As part of this re-indexing, dimensions may turn into symbols, or vice
579 /// versa.
580 AffineMap alignAffineMapWithValues(AffineMap map, ValueRange operands,
581  ValueRange dims, ValueRange syms,
582  SmallVector<Value> *newSyms = nullptr);
583 
584 } // namespace mlir
585 
586 #endif // MLIR_ANALYSIS_FLATLINEARVALUECONSTRAINTS_H
union mlir::linalg::@1183::ArityGroupAndKind::Kind kind
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
Definition: AffineMap.h:46
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.
LogicalResult flattenAlignedMapAndMergeLocals(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, bool addConservativeSemiAffineBounds=false)
Given an affine map that is aligned with this constraint system:
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)
void printSpace(raw_ostream &os) const override
Prints the number of constraints, dimensions, symbols and locals in the FlatLinearConstraints.
void dumpRow(ArrayRef< int64_t > row, bool fixedColWidth=true) const
An easier to read dump of a row of the same width as the number of columns.
FlatLinearConstraints(const IntegerPolyhedron &fac)
void dumpPretty() const
A more human-readable version of dump().
AddConservativeSemiAffineBounds
Flag to control if conservative semi-affine bounds should be added in addBound().
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...
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound, AddConservativeSemiAffineBounds=AddConservativeSemiAffineBounds::No)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
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.
std::optional< int64_t > getConstantBoundOnDimSize(MLIRContext *context, unsigned pos, AffineMap *lb=nullptr, AffineMap *ub=nullptr, unsigned *minLbPos=nullptr, unsigned *minUbPos=nullptr) const
Returns a non-negative constant bound on the extent (upper bound - lower bound) of the specified vari...
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.
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...
SmallVector< std::optional< Value > > getMaybeValues() const
unsigned insertSymbolVar(unsigned pos, unsigned num=1)
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.
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.
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...
LogicalResult addBound(presburger::BoundType type, unsigned pos, AffineMap boundMap, bool isClosedBound, AddConservativeSemiAffineBounds=AddConservativeSemiAffineBounds::No)
Adds a bound for the variable at the specified position with constraints being drawn from the specifi...
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.
SmallVector< std::optional< Value > > getMaybeValues(presburger::VarKind kind) const
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:381
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
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.
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.
VarKind getVarKindAt(unsigned pos) const
Return the VarKind of the var at the specified position.
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
void setId(VarKind kind, unsigned pos, Identifier id)
Set the identifier of pos^th variable of the specified kind.
unsigned getVarKindOffset(VarKind kind) const
Return the index at which the specified kind of var starts.
Identifier getId(VarKind kind, unsigned pos) const
Get the identifier of pos^th variable of the specified kind.
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, bool addConservativeSemiAffineBounds=false)
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, bool addConservativeSemiAffineBounds=false)
Flattens the result expressions of the map to their corresponding flattened forms and set in 'flatten...
LogicalResult getMultiAffineFunctionFromMap(AffineMap map, presburger::MultiAffineFunction &multiAff)