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