MLIR  16.0.0git
AffineStructures.h
Go to the documentation of this file.
1 //===- AffineStructures.h - MLIR Affine Structures 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 // Structures for affine/polyhedral analysis of ML functions.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H
14 #define MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H
15 
18 #include "mlir/IR/AffineExpr.h"
19 #include "mlir/IR/OpDefinition.h"
21 
22 namespace mlir {
23 
24 class AffineCondition;
25 class AffineForOp;
26 class AffineIfOp;
27 class AffineMap;
28 class AffineValueMap;
29 class IntegerSet;
30 class MLIRContext;
31 class Value;
32 class MemRefType;
33 struct MutableAffineMap;
34 
35 /// FlatAffineValueConstraints represents an extension of IntegerPolyhedron
36 /// where each non-local variable can have an SSA Value attached to it.
38 public:
39  /// Constructs a constraint system reserving memory for the specified number
40  /// of constraints and variables.
41  FlatAffineValueConstraints(unsigned numReservedInequalities,
42  unsigned numReservedEqualities,
43  unsigned numReservedCols, unsigned numDims,
44  unsigned numSymbols, unsigned numLocals,
45  ArrayRef<Optional<Value>> valArgs = {})
46  : IntegerPolyhedron(numReservedInequalities, numReservedEqualities,
47  numReservedCols,
49  numDims, numSymbols, numLocals)) {
50  assert(numReservedCols >= getNumVars() + 1);
51  assert(valArgs.empty() || valArgs.size() == getNumDimAndSymbolVars());
52  values.reserve(numReservedCols);
53  if (valArgs.empty())
55  else
56  values.append(valArgs.begin(), valArgs.end());
57  }
58 
59  /// Constructs a constraint system with the specified number of
60  /// dimensions and symbols.
61  FlatAffineValueConstraints(unsigned numDims = 0, unsigned numSymbols = 0,
62  unsigned numLocals = 0,
63  ArrayRef<Optional<Value>> valArgs = {})
64  : FlatAffineValueConstraints(/*numReservedInequalities=*/0,
65  /*numReservedEqualities=*/0,
66  /*numReservedCols=*/numDims + numSymbols +
67  numLocals + 1,
68  numDims, numSymbols, numLocals, valArgs) {}
69 
71  ArrayRef<Optional<Value>> valArgs = {})
72  : IntegerPolyhedron(fac) {
73  assert(valArgs.empty() || valArgs.size() == getNumDimAndSymbolVars());
74  if (valArgs.empty())
76  else
77  values.append(valArgs.begin(), valArgs.end());
78  }
79 
80  /// Create a flat affine constraint system from an AffineValueMap or a list of
81  /// these. The constructed system will only include equalities.
82  explicit FlatAffineValueConstraints(const AffineValueMap &avm);
84 
85  /// Creates an affine constraint system from an IntegerSet.
87 
89  IntegerSet set);
90 
91  // Construct a hyperrectangular constraint set from ValueRanges that represent
92  // induction variables, lower and upper bounds. `ivs`, `lbs` and `ubs` are
93  // expected to match one to one. The order of variables and constraints is:
94  //
95  // ivs | lbs | ubs | eq/ineq
96  // ----+-----+-----+---------
97  // 1 -1 0 >= 0
98  // ----+-----+-----+---------
99  // -1 0 1 >= 0
100  //
101  // All dimensions as set as VarKind::SetDim.
104 
105  /// Return the kind of this FlatAffineConstraints.
106  Kind getKind() const override { return Kind::FlatAffineValueConstraints; }
107 
108  static bool classof(const IntegerRelation *cst) {
109  return cst->getKind() == Kind::FlatAffineValueConstraints;
110  }
111 
112  /// Clears any existing data and reserves memory for the specified
113  /// constraints.
114  void reset(unsigned numReservedInequalities, unsigned numReservedEqualities,
115  unsigned numReservedCols, unsigned numDims, unsigned numSymbols,
116  unsigned numLocals = 0);
117  void reset(unsigned numDims = 0, unsigned numSymbols = 0,
118  unsigned numLocals = 0);
119  void reset(unsigned numReservedInequalities, unsigned numReservedEqualities,
120  unsigned numReservedCols, unsigned numDims, unsigned numSymbols,
121  unsigned numLocals, ArrayRef<Value> valArgs);
122  void reset(unsigned numDims, unsigned numSymbols, unsigned numLocals,
123  ArrayRef<Value> valArgs);
124 
125  /// Clones this object.
126  std::unique_ptr<FlatAffineValueConstraints> clone() const;
127 
128  /// Adds constraints (lower and upper bounds) for the specified 'affine.for'
129  /// operation's Value using IR information stored in its bound maps. The
130  /// right variable is first looked up using `forOp`'s Value. Asserts if the
131  /// Value corresponding to the 'affine.for' operation isn't found in the
132  /// constraint system. Returns failure for the yet unimplemented/unsupported
133  /// cases. Any new variables that are found in the bound operands of the
134  /// 'affine.for' operation are added as trailing variables (either
135  /// dimensional or symbolic depending on whether the operand is a valid
136  /// symbol).
137  // TODO: add support for non-unit strides.
138  LogicalResult addAffineForOpDomain(AffineForOp forOp);
139 
140  /// Adds constraints (lower and upper bounds) for each loop in the loop nest
141  /// described by the bound maps `lbMaps` and `ubMaps` of a computation slice.
142  /// Every pair (`lbMaps[i]`, `ubMaps[i]`) describes the bounds of a loop in
143  /// the nest, sorted outer-to-inner. `operands` contains the bound operands
144  /// for a single bound map. All the bound maps will use the same bound
145  /// operands. Note that some loops described by a computation slice might not
146  /// exist yet in the IR so the Value attached to those dimension variables
147  /// might be empty. For that reason, this method doesn't perform Value
148  /// look-ups to retrieve the dimension variable positions. Instead, it
149  /// assumes the position of the dim variables in the constraint system is
150  /// the same as the position of the loop in the loop nest.
152  ArrayRef<AffineMap> ubMaps,
153  ArrayRef<Value> operands);
154 
155  /// Adds constraints imposed by the `affine.if` operation. These constraints
156  /// are collected from the IntegerSet attached to the given `affine.if`
157  /// instance argument (`ifOp`). It is asserted that:
158  /// 1) The IntegerSet of the given `affine.if` instance should not contain
159  /// semi-affine expressions,
160  /// 2) The columns of the constraint system created from `ifOp` should match
161  /// the columns in the current one regarding numbers and values.
162  void addAffineIfOpDomain(AffineIfOp ifOp);
163 
164  /// Adds a bound for the variable at the specified position with constraints
165  /// being drawn from the specified bound map. In case of an EQ bound, the
166  /// bound map is expected to have exactly one result. In case of a LB/UB, the
167  /// bound map may have more than one result, for each of which an inequality
168  /// is added.
169  ///
170  /// The bound can be added as open or closed by specifying isClosedBound. In
171  /// case of a LB/UB, isClosedBound = false means the bound is added internally
172  /// as a closed bound by +1/-1 respectively. In case of an EQ bound, it can
173  /// only be added as a closed bound.
174  ///
175  /// Note: The dimensions/symbols of this FlatAffineConstraints must match the
176  /// dimensions/symbols of the affine map.
177  LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap,
178  bool isClosedBound);
179 
180  /// Adds a bound for the variable at the specified position with constraints
181  /// being drawn from the specified bound map. In case of an EQ bound, the
182  /// bound map is expected to have exactly one result. In case of a LB/UB, the
183  /// bound map may have more than one result, for each of which an inequality
184  /// is added.
185  /// Note: The dimensions/symbols of this FlatAffineConstraints must match the
186  /// dimensions/symbols of the affine map. By default the lower bound is closed
187  /// and the upper bound is open.
188  LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap);
189 
190  /// Adds a bound for the variable at the specified position with constraints
191  /// being drawn from the specified bound map and operands. In case of an
192  /// EQ bound, the bound map is expected to have exactly one result. In case
193  /// of a LB/UB, the bound map may have more than one result, for each of which
194  /// an inequality is added.
195  LogicalResult addBound(BoundType type, unsigned pos, AffineMap boundMap,
196  ValueRange operands);
197 
198  /// Adds a constant bound for the variable associated with the given Value.
199  void addBound(BoundType type, Value val, int64_t value);
200 
201  /// The `addBound` overload above hides the inherited overloads by default, so
202  /// we explicitly introduce them here.
203  using IntegerPolyhedron::addBound;
204 
205  /// Returns the constraint system as an integer set. Returns a null integer
206  /// set if the system has no constraints, or if an integer set couldn't be
207  /// constructed as a result of a local variable's explicit representation not
208  /// being known and such a local variable appearing in any of the constraints.
209  IntegerSet getAsIntegerSet(MLIRContext *context) const;
210 
211  /// Computes the lower and upper bounds of the first `num` dimensional
212  /// variables (starting at `offset`) as an affine map of the remaining
213  /// variables (dimensional and symbolic). This method is able to detect
214  /// variables as floordiv's and mod's of affine expressions of other
215  /// variables with respect to (positive) constants. Sets bound map to a
216  /// null AffineMap if such a bound can't be found (or yet unimplemented).
217  ///
218  /// By default the returned lower bounds are closed and upper bounds are open.
219  /// This can be changed by getClosedUB.
220  void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context,
223  bool getClosedUB = false);
224 
225  /// Composes an affine map whose dimensions and symbols match one to one with
226  /// the dimensions and symbols of this FlatAffineConstraints. The results of
227  /// the map `other` are added as the leading dimensions of this constraint
228  /// system. Returns failure if `other` is a semi-affine map.
230 
231  /// Gets the lower and upper bound of the `offset` + `pos`th variable
232  /// treating [0, offset) U [offset + num, symStartPos) as dimensions and
233  /// [symStartPos, getNumDimAndSymbolVars) as symbols, and `pos` lies in
234  /// [0, num). The multi-dimensional maps in the returned pair represent the
235  /// max and min of potentially multiple affine expressions. The upper bound is
236  /// exclusive. `localExprs` holds pre-computed AffineExpr's for all local
237  /// variables in the system.
238  std::pair<AffineMap, AffineMap>
239  getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num,
240  unsigned symStartPos, ArrayRef<AffineExpr> localExprs,
241  MLIRContext *context) const;
242 
243  /// Returns the bound for the variable at `pos` from the inequality at
244  /// `ineqPos` as a 1-d affine value map (affine map + operands). The returned
245  /// affine value map can either be a lower bound or an upper bound depending
246  /// on the sign of atIneq(ineqPos, pos). Asserts if the row at `ineqPos` does
247  /// not involve the `pos`th variable.
248  void getIneqAsAffineValueMap(unsigned pos, unsigned ineqPos,
249  AffineValueMap &vmap,
250  MLIRContext *context) const;
251 
252  /// Adds slice lower bounds represented by lower bounds in `lbMaps` and upper
253  /// bounds in `ubMaps` to each variable in the constraint system which has
254  /// a value in `values`. Note that both lower/upper bounds share the same
255  /// operand list `operands`.
256  /// This function assumes `values.size` == `lbMaps.size` == `ubMaps.size`.
257  /// Note that both lower/upper bounds use operands from `operands`.
259  ArrayRef<AffineMap> lbMaps,
260  ArrayRef<AffineMap> ubMaps,
261  ArrayRef<Value> operands);
262 
263  /// Looks up the position of the variable with the specified Value. Returns
264  /// true if found (false otherwise). `pos` is set to the (column) position of
265  /// the variable.
266  bool findVar(Value val, unsigned *pos) const;
267 
268  /// Returns true if an variable with the specified Value exists, false
269  /// otherwise.
270  bool containsVar(Value mayBeVar) const;
271 
272  /// Swap the posA^th variable with the posB^th variable.
273  void swapVar(unsigned posA, unsigned posB) override;
274 
275  /// Insert variables of the specified kind at position `pos`. Positions are
276  /// relative to the kind of variable. The coefficient columns corresponding
277  /// to the added variables are initialized to zero. `vals` are the Values
278  /// corresponding to the variables. Values should not be used with
279  /// VarKind::Local since values can only be attached to non-local variables.
280  /// Return the absolute column position (i.e., not relative to the kind of
281  /// variable) of the first added variable.
282  ///
283  /// Note: Empty Values are allowed in `vals`.
284  unsigned insertDimVar(unsigned pos, unsigned num = 1) {
285  return insertVar(VarKind::SetDim, pos, num);
286  }
287  unsigned insertSymbolVar(unsigned pos, unsigned num = 1) {
288  return insertVar(VarKind::Symbol, pos, num);
289  }
290  unsigned insertLocalVar(unsigned pos, unsigned num = 1) {
291  return insertVar(VarKind::Local, pos, num);
292  }
293  unsigned insertDimVar(unsigned pos, ValueRange vals);
294  unsigned insertSymbolVar(unsigned pos, ValueRange vals);
295  unsigned insertVar(presburger::VarKind kind, unsigned pos,
296  unsigned num = 1) override;
297  unsigned insertVar(presburger::VarKind kind, unsigned pos, ValueRange vals);
298 
299  /// Append variables of the specified kind after the last variable of that
300  /// kind. The coefficient columns corresponding to the added variables are
301  /// initialized to zero. `vals` are the Values corresponding to the
302  /// variables. Return the position of the first added column.
303  ///
304  /// Note: Empty Values are allowed in `vals`.
305  unsigned appendDimVar(ValueRange vals);
306  unsigned appendSymbolVar(ValueRange vals);
307  unsigned appendDimVar(unsigned num = 1) {
308  return appendVar(VarKind::SetDim, num);
309  }
310  unsigned appendSymbolVar(unsigned num = 1) {
311  return appendVar(VarKind::Symbol, num);
312  }
313  unsigned appendLocalVar(unsigned num = 1) {
314  return appendVar(VarKind::Local, num);
315  }
316 
317  /// Removes variables in the column range [varStart, varLimit), and copies any
318  /// remaining valid data into place, updates member variables, and resizes
319  /// arrays as needed.
320  void removeVarRange(presburger::VarKind kind, unsigned varStart,
321  unsigned varLimit) override;
322  using IntegerPolyhedron::removeVarRange;
323 
324  /// Add the specified values as a dim or symbol var depending on its nature,
325  /// if it already doesn't exist in the system. `val` has to be either a
326  /// terminal symbol or a loop IV, i.e., it cannot be the result affine.apply
327  /// of any symbols or loop IVs. The variable is added to the end of the
328  /// existing dims or symbols. Additional information on the variable is
329  /// extracted from the IR and added to the constraint system.
331 
332  /// Align `map` with this constraint system based on `operands`. Each operand
333  /// must already have a corresponding dim/symbol in this constraint system.
334  AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const;
335 
336  /// Composes the affine value map with this FlatAffineValueConstrains, adding
337  /// the results of the map as dimensions at the front
338  /// [0, vMap->getNumResults()) and with the dimensions set to the equalities
339  /// specified by the value map.
340  ///
341  /// Returns failure if the composition fails (when vMap is a semi-affine map).
342  /// The vMap's operand Value's are used to look up the right positions in
343  /// the FlatAffineConstraints with which to associate. Every operand of vMap
344  /// should have a matching dim/symbol column in this constraint system (with
345  /// the same associated Value).
347 
348  /// Projects out the variable that is associate with Value.
349  void projectOut(Value val);
350  using IntegerPolyhedron::projectOut;
351 
352  /// Changes all symbol variables which are loop IVs to dim variables.
354 
355  /// Updates the constraints to be the smallest bounding (enclosing) box that
356  /// contains the points of `this` set and that of `other`, with the symbols
357  /// being treated specially. For each of the dimensions, the min of the lower
358  /// bounds (symbolic) and the max of the upper bounds (symbolic) is computed
359  /// to determine such a bounding box. `other` is expected to have the same
360  /// dimensional variables as this constraint system (in the same order).
361  ///
362  /// E.g.:
363  /// 1) this = {0 <= d0 <= 127},
364  /// other = {16 <= d0 <= 192},
365  /// output = {0 <= d0 <= 192}
366  /// 2) this = {s0 + 5 <= d0 <= s0 + 20},
367  /// other = {s0 + 1 <= d0 <= s0 + 9},
368  /// output = {s0 + 1 <= d0 <= s0 + 20}
369  /// 3) this = {0 <= d0 <= 5, 1 <= d1 <= 9}
370  /// other = {2 <= d0 <= 6, 5 <= d1 <= 15},
371  /// output = {0 <= d0 <= 6, 1 <= d1 <= 15}
373  using IntegerPolyhedron::unionBoundingBox;
374 
375  /// Merge and align the variables of `this` and `other` starting at
376  /// `offset`, so that both constraint systems get the union of the contained
377  /// variables that is dimension-wise and symbol-wise unique; both
378  /// constraint systems are updated so that they have the union of all
379  /// variables, with `this`'s original variables appearing first followed
380  /// by any of `other`'s variables that didn't appear in `this`. Local
381  /// variables in `other` that have the same division representation as local
382  /// variables in `this` are merged into one.
383  // E.g.: Input: `this` has (%i, %j) [%M, %N]
384  // `other` has (%k, %j) [%P, %N, %M]
385  // Output: both `this`, `other` have (%i, %j, %k) [%M, %N, %P]
386  //
387  void mergeAndAlignVarsWithOther(unsigned offset,
389 
390  /// Returns true if this constraint system and `other` are in the same
391  /// space, i.e., if they are associated with the same set of variables,
392  /// appearing in the same order. Returns false otherwise.
394 
395  /// Replaces the contents of this FlatAffineValueConstraints with `other`.
396  void clearAndCopyFrom(const IntegerRelation &other) override;
397 
398  /// Returns the Value associated with the pos^th variable. Asserts if
399  /// no Value variable was associated.
400  inline Value getValue(unsigned pos) const {
401  assert(pos < getNumDimAndSymbolVars() && "Invalid position");
402  assert(hasValue(pos) && "variable's Value not set");
403  return values[pos].value();
404  }
405 
406  /// Returns true if the pos^th variable has an associated Value.
407  inline bool hasValue(unsigned pos) const {
408  assert(pos < getNumDimAndSymbolVars() && "Invalid position");
409  return values[pos].has_value();
410  }
411 
412  /// Returns true if at least one variable has an associated Value.
413  bool hasValues() const;
414 
415  /// Returns the Values associated with variables in range [start, end).
416  /// Asserts if no Value was associated with one of these variables.
417  inline void getValues(unsigned start, unsigned end,
418  SmallVectorImpl<Value> *values) const {
419  assert(end <= getNumDimAndSymbolVars() && "invalid end position");
420  assert(start <= end && "invalid start position");
421  values->clear();
422  values->reserve(end - start);
423  for (unsigned i = start; i < end; i++)
424  values->push_back(getValue(i));
425  }
426  inline void getAllValues(SmallVectorImpl<Value> *values) const {
427  getValues(0, getNumDimAndSymbolVars(), values);
428  }
429 
431  return {values.data(), values.size()};
432  }
433 
436  assert(kind != VarKind::Local &&
437  "Local variables do not have any value attached to them.");
438  return {values.data() + getVarKindOffset(kind), getNumVarKind(kind)};
439  }
440 
441  /// Sets the Value associated with the pos^th variable.
442  inline void setValue(unsigned pos, Value val) {
443  assert(pos < getNumDimAndSymbolVars() && "invalid var position");
444  values[pos] = val;
445  }
446 
447  /// Sets the Values associated with the variables in the range [start, end).
448  /// The range must contain only dim and symbol variables.
449  void setValues(unsigned start, unsigned end, ArrayRef<Value> values) {
450  assert(end <= getNumVars() && "invalid end position");
451  assert(start <= end && "invalid start position");
452  assert(values.size() == end - start &&
453  "value should be provided for each variable in the range.");
454  for (unsigned i = start; i < end; ++i)
455  setValue(i, values[i - start]);
456  }
457 
458  /// Merge and align symbols of `this` and `other` such that both get union of
459  /// of symbols that are unique. Symbols in `this` and `other` should be
460  /// unique. Symbols with Value as `None` are considered to be inequal to all
461  /// other symbols.
463 
464 protected:
466 
467  /// Returns false if the fields corresponding to various variable counts, or
468  /// equality/inequality buffer sizes aren't consistent; true otherwise. This
469  /// is meant to be used within an assert internally.
470  bool hasConsistentState() const override;
471 
472  /// Given an affine map that is aligned with this constraint system:
473  /// * Flatten the map.
474  /// * Add newly introduced local columns at the beginning of this constraint
475  /// system (local column pos 0).
476  /// * Add equalities that define the new local columns to this constraint
477  /// system.
478  /// * Return the flattened expressions via `flattenedExprs`.
479  ///
480  /// Note: This is a shared helper function of `addLowerOrUpperBound` and
481  /// `composeMatchingMap`.
483  AffineMap map, std::vector<SmallVector<int64_t, 8>> *flattenedExprs);
484 
485  /// Eliminates the variable at the specified position using Fourier-Motzkin
486  /// variable elimination, but uses Gaussian elimination if there is an
487  /// equality involving that variable. If the result of the elimination is
488  /// integer exact, `*isResultIntegerExact` is set to true. If `darkShadow` is
489  /// set to true, a potential under approximation (subset) of the rational
490  /// shadow / exact integer shadow is computed.
491  // See implementation comments for more details.
492  void fourierMotzkinEliminate(unsigned pos, bool darkShadow = false,
493  bool *isResultIntegerExact = nullptr) override;
494 
495  /// Prints the number of constraints, dimensions, symbols and locals in the
496  /// FlatAffineConstraints. Also, prints for each variable whether there is
497  /// an SSA Value attached to it.
498  void printSpace(raw_ostream &os) const override;
499 
500  /// Values corresponding to the (column) non-local variables of this
501  /// constraint system appearing in the order the variables correspond to
502  /// columns. Variables that aren't associated with any Value are set to
503  /// None.
505 };
506 
507 /// A FlatAffineRelation represents a set of ordered pairs (domain -> range)
508 /// where "domain" and "range" are tuples of variables. The relation is
509 /// represented as a FlatAffineValueConstraints with separation of dimension
510 /// variables into domain and range. The variables are stored as:
511 /// [domainVars, rangeVars, symbolVars, localVars, constant].
513 public:
514  FlatAffineRelation(unsigned numReservedInequalities,
515  unsigned numReservedEqualities, unsigned numReservedCols,
516  unsigned numDomainDims, unsigned numRangeDims,
517  unsigned numSymbols, unsigned numLocals,
518  ArrayRef<Optional<Value>> valArgs = {})
520  numReservedInequalities, numReservedEqualities, numReservedCols,
521  numDomainDims + numRangeDims, numSymbols, numLocals, valArgs),
522  numDomainDims(numDomainDims), numRangeDims(numRangeDims) {}
523 
524  FlatAffineRelation(unsigned numDomainDims = 0, unsigned numRangeDims = 0,
525  unsigned numSymbols = 0, unsigned numLocals = 0)
526  : FlatAffineValueConstraints(numDomainDims + numRangeDims, numSymbols,
527  numLocals),
528  numDomainDims(numDomainDims), numRangeDims(numRangeDims) {}
529 
530  FlatAffineRelation(unsigned numDomainDims, unsigned numRangeDims,
532  : FlatAffineValueConstraints(fac), numDomainDims(numDomainDims),
533  numRangeDims(numRangeDims) {}
534 
535  FlatAffineRelation(unsigned numDomainDims, unsigned numRangeDims,
536  IntegerPolyhedron &fac)
537  : FlatAffineValueConstraints(fac), numDomainDims(numDomainDims),
538  numRangeDims(numRangeDims) {}
539 
540  /// Returns a set corresponding to the domain/range of the affine relation.
543 
544  /// Returns the number of variables corresponding to domain/range of
545  /// relation.
546  inline unsigned getNumDomainDims() const { return numDomainDims; }
547  inline unsigned getNumRangeDims() const { return numRangeDims; }
548 
549  /// Given affine relation `other: (domainOther -> rangeOther)`, this operation
550  /// takes the composition of `other` on `this: (domainThis -> rangeThis)`.
551  /// The resulting relation represents tuples of the form: `domainOther ->
552  /// rangeThis`.
553  void compose(const FlatAffineRelation &other);
554 
555  /// Swap domain and range of the relation.
556  /// `(domain -> range)` is converted to `(range -> domain)`.
557  void inverse();
558 
559  /// Insert `num` variables of the specified kind after the `pos` variable
560  /// of that kind. The coefficient columns corresponding to the added
561  /// variables are initialized to zero.
562  void insertDomainVar(unsigned pos, unsigned num = 1);
563  void insertRangeVar(unsigned pos, unsigned num = 1);
564 
565  /// Append `num` variables of the specified kind after the last variable
566  /// of that kind. The coefficient columns corresponding to the added
567  /// variables are initialized to zero.
568  void appendDomainVar(unsigned num = 1);
569  void appendRangeVar(unsigned num = 1);
570 
571  /// Removes variables in the column range [varStart, varLimit), and copies any
572  /// remaining valid data into place, updates member variables, and resizes
573  /// arrays as needed.
574  void removeVarRange(VarKind kind, unsigned varStart,
575  unsigned varLimit) override;
576  using IntegerRelation::removeVarRange;
577 
578 protected:
579  // Number of dimension variables corresponding to domain variables.
580  unsigned numDomainDims;
581 
582  // Number of dimension variables corresponding to range variables.
583  unsigned numRangeDims;
584 };
585 
586 /// Flattens 'expr' into 'flattenedExpr', which contains the coefficients of the
587 /// dimensions, symbols, and additional variables that represent floor divisions
588 /// of dimensions, symbols, and in turn other floor divisions. Returns failure
589 /// if 'expr' could not be flattened (i.e., semi-affine is not yet handled).
590 /// 'cst' contains constraints that connect newly introduced local variables
591 /// to existing dimensional and symbolic variables. See documentation for
592 /// AffineExprFlattener on how mod's and div's are flattened.
593 LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims,
594  unsigned numSymbols,
595  SmallVectorImpl<int64_t> *flattenedExpr,
596  FlatAffineValueConstraints *cst = nullptr);
597 
598 /// Flattens the result expressions of the map to their corresponding flattened
599 /// forms and set in 'flattenedExprs'. Returns failure if any expression in the
600 /// map could not be flattened (i.e., semi-affine is not yet handled). 'cst'
601 /// contains constraints that connect newly introduced local variables to
602 /// existing dimensional and / symbolic variables. See documentation for
603 /// AffineExprFlattener on how mod's and div's are flattened. For all affine
604 /// expressions that share the same operands (like those of an affine map), this
605 /// method should be used instead of repeatedly calling getFlattenedAffineExpr
606 /// since local variables added to deal with div's and mod's will be reused
607 /// across expressions.
610  std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
611  FlatAffineValueConstraints *cst = nullptr);
614  std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
615  FlatAffineValueConstraints *cst = nullptr);
616 
617 /// Re-indexes the dimensions and symbols of an affine map with given `operands`
618 /// values to align with `dims` and `syms` values.
619 ///
620 /// Each dimension/symbol of the map, bound to an operand `o`, is replaced with
621 /// dimension `i`, where `i` is the position of `o` within `dims`. If `o` is not
622 /// in `dims`, replace it with symbol `i`, where `i` is the position of `o`
623 /// within `syms`. If `o` is not in `syms` either, replace it with a new symbol.
624 ///
625 /// Note: If a value appears multiple times as a dimension/symbol (or both), all
626 /// corresponding dim/sym expressions are replaced with the first dimension
627 /// bound to that value (or first symbol if no such dimension exists).
628 ///
629 /// The resulting affine map has `dims.size()` many dimensions and at least
630 /// `syms.size()` many symbols.
631 ///
632 /// The SSA values of the symbols of the resulting map are optionally returned
633 /// via `newSyms`. This is a concatenation of `syms` with the SSA values of the
634 /// newly added symbols.
635 ///
636 /// Note: As part of this re-indexing, dimensions may turn into symbols, or vice
637 /// versa.
639  ValueRange dims, ValueRange syms,
640  SmallVector<Value> *newSyms = nullptr);
641 
642 /// Builds a relation from the given AffineMap/AffineValueMap `map`, containing
643 /// all pairs of the form `operands -> result` that satisfy `map`. `rel` is set
644 /// to the relation built. For example, give the AffineMap:
645 ///
646 /// (d0, d1)[s0] -> (d0 + s0, d0 - s0)
647 ///
648 /// the resulting relation formed is:
649 ///
650 /// (d0, d1) -> (r1, r2)
651 /// [d0 d1 r1 r2 s0 const]
652 /// 1 0 -1 0 1 0 = 0
653 /// 0 1 0 -1 -1 0 = 0
654 ///
655 /// For AffineValueMap, the domain and symbols have Value set corresponding to
656 /// the Value in `map`. Returns failure if the AffineMap could not be flattened
657 /// (i.e., semi-affine is not yet handled).
660  FlatAffineRelation &rel);
661 
662 } // namespace mlir.
663 
664 #endif // MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H
Include the generated interface declarations.
FlatAffineRelation(unsigned numDomainDims=0, unsigned numRangeDims=0, unsigned numSymbols=0, unsigned numLocals=0)
unsigned getNumDomainDims() const
Returns the number of variables corresponding to domain/range of relation.
unsigned appendSymbolVar(ValueRange vals)
void reset(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals=0)
Clears any existing data and reserves memory for the specified constraints.
unsigned appendVar(VarKind kind, unsigned num=1)
Append num variables of the specified kind after the last variable.
unsigned insertVar(presburger::VarKind kind, unsigned pos, unsigned num=1) override
Insert num variables of the specified kind at position pos.
void compose(const IntegerRelation &rel)
Let the relation this be R1, and the relation rel be R2.
LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims, unsigned numSymbols, SmallVectorImpl< int64_t > *flattenedExpr, FlatAffineValueConstraints *cst=nullptr)
Flattens &#39;expr&#39; into &#39;flattenedExpr&#39;, which contains the coefficients of the dimensions, symbols, and additional variables that represent floor divisions of dimensions, symbols, and in turn other floor divisions.
std::pair< AffineMap, AffineMap > getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num, unsigned symStartPos, ArrayRef< AffineExpr > localExprs, MLIRContext *context) const
Gets the lower and upper bound of the offset + posth variable treating [0, offset) U [offset + num...
A FlatAffineRelation represents a set of ordered pairs (domain -> range) where "domain" and "range" a...
bool hasValue(unsigned pos) const
Returns true if the pos^th variable has an associated Value.
void convertLoopIVSymbolsToDims()
Changes all symbol variables which are loop IVs to dim variables.
IntegerPolyhedron getRangeSet() const
Return a set corresponding to all points in the range of the relation.
bool hasValues() const
Returns true if at least one variable has an associated Value.
bool containsVar(Value mayBeVar) const
Returns true if an variable with the specified Value exists, false otherwise.
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 ...
void addAffineIfOpDomain(AffineIfOp ifOp)
Adds constraints imposed by the affine.if operation.
static FlatAffineValueConstraints getHyperrectangular(ValueRange ivs, ValueRange lbs, ValueRange ubs)
void getIneqAsAffineValueMap(unsigned pos, unsigned ineqPos, AffineValueMap &vmap, MLIRContext *context) const
Returns the bound for the variable at pos from the inequality at ineqPos as a 1-d affine value map (a...
unsigned getVarKindOffset(VarKind kind) const
Return the index at which the specified kind of vars starts.
void setValues(unsigned start, unsigned end, ArrayRef< Value > values)
Sets the Values associated with the variables in the range [start, end).
unsigned appendDimVar(ValueRange vals)
Append variables of the specified kind after the last variable of that kind.
LogicalResult flattenAlignedMapAndMergeLocals(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs)
Given an affine map that is aligned with this constraint system:
void mergeSymbolVars(FlatAffineValueConstraints &other)
Merge and align symbols of this and other such that both get union of of symbols that are unique...
LogicalResult getRelationFromMap(AffineMap &map, FlatAffineRelation &rel)
Builds a relation from the given AffineMap/AffineValueMap map, containing all pairs of the form opera...
An IntegerPolyhedron represents the set of points from a PresburgerSpace that satisfy a list of affin...
BoundType
The type of bound: equal, lower bound or upper bound.
void mergeAndAlignVarsWithOther(unsigned offset, FlatAffineValueConstraints *other)
Merge and align the variables of this and other starting at offset, so that both constraint systems g...
static constexpr const bool value
FlatAffineValueConstraints(unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0, ArrayRef< Optional< Value >> valArgs={})
Constructs a constraint system with the specified number of dimensions and symbols.
unsigned insertDimVar(unsigned pos, unsigned num=1)
Insert variables of the specified kind at position pos.
Kind
All derived classes of IntegerRelation.
LogicalResult addSliceBounds(ArrayRef< Value > values, ArrayRef< AffineMap > lbMaps, ArrayRef< AffineMap > ubMaps, ArrayRef< Value > operands)
Adds slice lower bounds represented by lower bounds in lbMaps and upper bounds in ubMaps to each vari...
This class represents an efficient way to signal success or failure.
Definition: LogicalResult.h:26
ArrayRef< Optional< Value > > getMaybeValues() const
void fourierMotzkinEliminate(unsigned pos, bool darkShadow=false, bool *isResultIntegerExact=nullptr) override
Eliminates the variable at the specified position using Fourier-Motzkin variable elimination, but uses Gaussian elimination if there is an equality involving that variable.
void swapVar(unsigned posA, unsigned posB) override
Swap the posA^th variable with the posB^th variable.
AffineMap computeAlignedMap(AffineMap map, ValueRange operands) const
Align map with this constraint system based on operands.
void inverse()
Invert the relation i.e., swap its domain and range.
unsigned appendDimVar(unsigned num=1)
void addInductionVarOrTerminalSymbol(Value val)
Add the specified values as a dim or symbol var depending on its nature, if it already doesn&#39;t exist ...
LogicalResult addDomainFromSliceMaps(ArrayRef< AffineMap > lbMaps, ArrayRef< AffineMap > ubMaps, ArrayRef< Value > operands)
Adds constraints (lower and upper bounds) for each loop in the loop nest described by the bound maps ...
Base type for affine expression.
Definition: AffineExpr.h:68
FlatAffineValueConstraints(const IntegerPolyhedron &fac, ArrayRef< Optional< Value >> valArgs={})
bool hasConsistentState() const override
Returns false if the fields corresponding to various variable counts, or equality/inequality buffer s...
VarKind
Kind of variable.
IntegerSet getAsIntegerSet(MLIRContext *context) const
Returns the constraint system as an integer set.
unsigned appendSymbolVar(unsigned num=1)
A multi-dimensional affine map Affine map&#39;s are immutable like Type&#39;s, and they are uniqued...
Definition: AffineMap.h:42
void printSpace(raw_ostream &os) const override
Prints the number of constraints, dimensions, symbols and locals in the FlatAffineConstraints.
IntegerRelation(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, const PresburgerSpace &space)
Constructs a relation reserving memory for the specified number of constraints and variables...
SmallVector< Optional< Value >, 8 > values
Values corresponding to the (column) non-local variables of this constraint system appearing in the o...
FlatAffineRelation(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDomainDims, unsigned numRangeDims, unsigned numSymbols, unsigned numLocals, ArrayRef< Optional< Value >> valArgs={})
bool findVar(Value val, unsigned *pos) const
Looks up the position of the variable with the specified Value.
void projectOut(Value val)
Projects out the variable that is associate with Value.
LogicalResult unionBoundingBox(const FlatAffineValueConstraints &other)
Updates the constraints to be the smallest bounding (enclosing) box that contains the points of this ...
static bool classof(const IntegerRelation *cst)
LogicalResult composeMap(const AffineValueMap *vMap)
Composes the affine value map with this FlatAffineValueConstrains, adding the results of the map as d...
unsigned insertLocalVar(unsigned pos, unsigned num=1)
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:85
ArrayRef< Optional< Value > > getMaybeValues(presburger::VarKind kind) const
void getAllValues(SmallVectorImpl< Value > *values) const
FlatAffineValueConstraints represents an extension of IntegerPolyhedron where each non-local variable...
FlatAffineRelation(unsigned numDomainDims, unsigned numRangeDims, IntegerPolyhedron &fac)
MLIRContext is the top-level object for a collection of MLIR operations.
Definition: MLIRContext.h:55
LogicalResult addAffineForOpDomain(AffineForOp forOp)
Adds constraints (lower and upper bounds) for the specified &#39;affine.for&#39; operation&#39;s Value using IR i...
FlatAffineRelation(unsigned numDomainDims, unsigned numRangeDims, FlatAffineValueConstraints &fac)
unsigned getNumVarKind(VarKind kind) const
Get the number of vars of the specified kind.
void setValue(unsigned pos, Value val)
Sets the Value associated with the pos^th variable.
unsigned getNumRangeDims() const
Value getValue(unsigned pos) const
Returns the Value associated with the pos^th variable.
An AffineValueMap is an affine map plus its ML value operands and results for analysis purposes...
IntegerPolyhedron getDomainSet() const
Return a set corresponding to all points in the domain of the relation.
LogicalResult composeMatchingMap(AffineMap other)
Composes an affine map whose dimensions and symbols match one to one with the dimensions and symbols ...
void clearAndCopyFrom(const IntegerRelation &other) override
Replaces the contents of this FlatAffineValueConstraints with other.
LogicalResult getFlattenedAffineExprs(AffineMap map, std::vector< SmallVector< int64_t, 8 >> *flattenedExprs, FlatAffineValueConstraints *cst=nullptr)
Flattens the result expressions of the map to their corresponding flattened forms and set in &#39;flatten...
std::unique_ptr< FlatAffineValueConstraints > clone() const
Clones this object.
bool areVarsAlignedWithOther(const FlatAffineValueConstraints &other)
Returns true if this constraint system and other are in the same space, i.e., if they are associated ...
void getValues(unsigned start, unsigned end, SmallVectorImpl< Value > *values) const
Returns the Values associated with variables in range [start, end).
This class provides an abstraction over the different types of ranges over Values.
Definition: ValueRange.h:345
FlatAffineValueConstraints(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDims, unsigned numSymbols, unsigned numLocals, ArrayRef< Optional< Value >> valArgs={})
Constructs a constraint system reserving memory for the specified number of constraints and variables...
unsigned appendLocalVar(unsigned num=1)
unsigned insertSymbolVar(unsigned pos, unsigned num=1)
Kind getKind() const override
Return the kind of this FlatAffineConstraints.
void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context, SmallVectorImpl< AffineMap > *lbMaps, SmallVectorImpl< AffineMap > *ubMaps, bool getClosedUB=false)
Computes the lower and upper bounds of the first num dimensional variables (starting at offset) as an...
static PresburgerSpace getSetSpace(unsigned numDims=0, unsigned numSymbols=0, unsigned numLocals=0)
LogicalResult addBound(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...
IntegerPolyhedron(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, const PresburgerSpace &space)
Constructs a set reserving memory for the specified number of constraints and variables.
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 ...
An integer set representing a conjunction of one or more affine equalities and inequalities.
Definition: IntegerSet.h:44