MLIR  21.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 
19 #include "mlir/IR/AffineExpr.h"
20 #include "mlir/IR/OpDefinition.h"
21 #include <optional>
22 
23 namespace mlir {
24 class AffineMap;
25 class IntegerSet;
26 class MemRefType;
27 class MLIRContext;
28 struct MutableAffineMap;
29 class Value;
30 
31 namespace presburger {
32 class MultiAffineFunction;
33 } // namespace presburger
34 
35 namespace affine {
36 class AffineCondition;
37 class AffineForOp;
38 class AffineIfOp;
39 class AffineParallelOp;
40 class AffineValueMap;
41 
42 /// FlatAffineValueConstraints is an extension of FlatLinearValueConstraints
43 /// with helper functions for Affine dialect ops.
45 public:
47 
48  /// Return the kind of this object.
49  Kind getKind() const override { return Kind::FlatAffineValueConstraints; }
50 
51  static bool classof(const IntegerRelation *cst) {
52  return cst->getKind() >= Kind::FlatAffineValueConstraints &&
53  cst->getKind() <= Kind::FlatAffineRelation;
54  }
55 
56  /// Adds constraints (lower and upper bounds) for the specified 'affine.for'
57  /// operation's Value using IR information stored in its bound maps. The
58  /// right variable is first looked up using `forOp`'s Value. Asserts if the
59  /// Value corresponding to the 'affine.for' operation isn't found in the
60  /// constraint system. Returns failure for the yet unimplemented/unsupported
61  /// cases. Any new variables that are found in the bound operands of the
62  /// 'affine.for' operation are added as trailing variables (either
63  /// dimensional or symbolic depending on whether the operand is a valid
64  /// symbol).
65  LogicalResult addAffineForOpDomain(AffineForOp forOp);
66 
67  /// Add constraints (lower and upper bounds) for the specified
68  /// 'affine.parallel' operation's Value using IR information stored in its
69  /// bound maps. Returns failure for the yet unimplemented/unsupported cases.
70  /// Asserts if the Value corresponding to the 'affine.parallel' operation
71  /// isn't found in the constraint system.
72  LogicalResult addAffineParallelOpDomain(AffineParallelOp parallelOp);
73 
74  /// Adds constraints (lower and upper bounds) for each loop in the loop nest
75  /// described by the bound maps `lbMaps` and `ubMaps` of a computation slice.
76  /// Every pair (`lbMaps[i]`, `ubMaps[i]`) describes the bounds of a loop in
77  /// the nest, sorted outer-to-inner. `operands` contains the bound operands
78  /// for a single bound map. All the bound maps will use the same bound
79  /// operands. Note that some loops described by a computation slice might not
80  /// exist yet in the IR so the Value attached to those dimension variables
81  /// might be empty. For that reason, this method doesn't perform Value
82  /// look-ups to retrieve the dimension variable positions. Instead, it
83  /// assumes the position of the dim variables in the constraint system is
84  /// the same as the position of the loop in the loop nest.
85  LogicalResult addDomainFromSliceMaps(ArrayRef<AffineMap> lbMaps,
86  ArrayRef<AffineMap> ubMaps,
87  ArrayRef<Value> operands);
88 
89  /// Adds constraints imposed by the `affine.if` operation. These constraints
90  /// are collected from the IntegerSet attached to the given `affine.if`
91  /// instance argument (`ifOp`). It is asserted that:
92  /// 1) The IntegerSet of the given `affine.if` instance should not contain
93  /// semi-affine expressions,
94  /// 2) The columns of the constraint system created from `ifOp` should match
95  /// the columns in the current one regarding numbers and values.
96  void addAffineIfOpDomain(AffineIfOp ifOp);
97 
98  /// Adds a bound for the variable at the specified position with constraints
99  /// being drawn from the specified bound map and operands. In case of an
100  /// EQ bound, the bound map is expected to have exactly one result. In case
101  /// of a LB/UB, the bound map may have more than one result, for each of which
102  /// an inequality is added.
103  LogicalResult addBound(presburger::BoundType type, unsigned pos,
104  AffineMap boundMap, ValueRange operands);
106 
107  /// Add the specified values as a dim or symbol var depending on its nature,
108  /// if it already doesn't exist in the system. `val` has to be either a
109  /// terminal symbol or a loop IV, i.e., it cannot be the result of an
110  /// affine.apply of any symbols or loop IVs. Return failure if the addition
111  /// wasn't possible due to the above conditions not being met. This method can
112  /// also fail if the addition of the domain of an affine IV fails. The
113  /// variable is added to the end of the existing dims or symbols. Additional
114  /// information on the variable is extracted from the IR and added to the
115  /// constraint system.
116  LogicalResult addInductionVarOrTerminalSymbol(Value val);
117 
118  /// Adds slice lower bounds represented by lower bounds in `lbMaps` and upper
119  /// bounds in `ubMaps` to each variable in the constraint system which has
120  /// a value in `values`. Note that both lower/upper bounds share the same
121  /// operand list `operands`.
122  /// This function assumes `values.size` == `lbMaps.size` == `ubMaps.size`.
123  /// Note that both lower/upper bounds use operands from `operands`.
124  LogicalResult addSliceBounds(ArrayRef<Value> values,
125  ArrayRef<AffineMap> lbMaps,
126  ArrayRef<AffineMap> ubMaps,
127  ArrayRef<Value> operands);
128 
129  /// Changes all symbol variables which are loop IVs to dim variables.
131 
132  /// Returns the bound for the variable at `pos` from the inequality at
133  /// `ineqPos` as a 1-d affine value map (affine map + operands). The returned
134  /// affine value map can either be a lower bound or an upper bound depending
135  /// on the sign of atIneq(ineqPos, pos). Asserts if the row at `ineqPos` does
136  /// not involve the `pos`th variable.
137  void getIneqAsAffineValueMap(unsigned pos, unsigned ineqPos,
138  AffineValueMap &vmap,
139  MLIRContext *context) const;
140 
141  /// Composes the affine value map with this FlatAffineValueConstrains, adding
142  /// the results of the map as dimensions at the front
143  /// [0, vMap->getNumResults()) and with the dimensions set to the equalities
144  /// specified by the value map.
145  ///
146  /// Returns failure if the composition fails (when vMap is a semi-affine map).
147  /// The vMap's operand Value's are used to look up the right positions in
148  /// the FlatAffineValueConstraints with which to associate. Every operand of
149  /// vMap should have a matching dim/symbol column in this constraint system
150  /// (with the same associated Value).
151  LogicalResult composeMap(const AffineValueMap *vMap);
152 };
153 
154 /// A FlatAffineRelation represents a set of ordered pairs (domain -> range)
155 /// where "domain" and "range" are tuples of variables. The relation is
156 /// represented as a FlatAffineValueConstraints with separation of dimension
157 /// variables into domain and range. The variables are stored as:
158 /// [domainVars, rangeVars, symbolVars, localVars, constant].
159 ///
160 /// Deprecated: use IntegerRelation and store SSA Values in the PresburgerSpace
161 /// of the relation using PresburgerSpace::identifiers. Note that
162 /// FlatAffineRelation::numDomainDims and FlatAffineRelation::numRangeDims are
163 /// independent of numDomain and numRange of the relation's space. In
164 /// particular, operations such as FlatAffineRelation::compose do not ensure
165 /// consistency between numDomainDims/numRangeDims and numDomain/numRange which
166 /// may lead to unexpected behaviour.
168 public:
169  FlatAffineRelation(unsigned numReservedInequalities,
170  unsigned numReservedEqualities, unsigned numReservedCols,
171  unsigned numDomainDims, unsigned numRangeDims,
172  unsigned numSymbols, unsigned numLocals,
173  ArrayRef<std::optional<Value>> valArgs = {})
175  numReservedInequalities, numReservedEqualities, numReservedCols,
176  numDomainDims + numRangeDims, numSymbols, numLocals, valArgs),
178 
179  FlatAffineRelation(unsigned numDomainDims = 0, unsigned numRangeDims = 0,
180  unsigned numSymbols = 0, unsigned numLocals = 0)
182  numLocals),
184 
189 
191  IntegerPolyhedron &fac)
194 
195  /// Return the kind of this object.
196  Kind getKind() const override { return Kind::FlatAffineRelation; }
197 
198  static bool classof(const IntegerRelation *cst) {
199  return cst->getKind() == Kind::FlatAffineRelation;
200  }
201 
202  /// Returns a set corresponding to the domain/range of the affine relation.
205 
206  /// Returns the number of variables corresponding to domain/range of
207  /// relation.
208  inline unsigned getNumDomainDims() const { return numDomainDims; }
209  inline unsigned getNumRangeDims() const { return numRangeDims; }
210 
211  /// Given affine relation `other: (domainOther -> rangeOther)`, this operation
212  /// takes the composition of `other` on `this: (domainThis -> rangeThis)`.
213  /// The resulting relation represents tuples of the form: `domainOther ->
214  /// rangeThis`.
215  void compose(const FlatAffineRelation &other);
216 
217  /// Swap domain and range of the relation.
218  /// `(domain -> range)` is converted to `(range -> domain)`.
219  void inverse();
220 
221  /// Insert `num` variables of the specified kind after the `pos` variable
222  /// of that kind. The coefficient columns corresponding to the added
223  /// variables are initialized to zero.
224  void insertDomainVar(unsigned pos, unsigned num = 1);
225  void insertRangeVar(unsigned pos, unsigned num = 1);
226 
227  /// Append `num` variables of the specified kind after the last variable
228  /// of that kind. The coefficient columns corresponding to the added
229  /// variables are initialized to zero.
230  void appendDomainVar(unsigned num = 1);
231  void appendRangeVar(unsigned num = 1);
232 
233  /// Removes variables in the column range [varStart, varLimit), and copies any
234  /// remaining valid data into place, updates member variables, and resizes
235  /// arrays as needed.
236  void removeVarRange(VarKind kind, unsigned varStart,
237  unsigned varLimit) override;
238  using IntegerRelation::removeVarRange;
239 
240 protected:
241  // Number of dimension variables corresponding to domain variables.
242  unsigned numDomainDims;
243 
244  // Number of dimension variables corresponding to range variables.
245  unsigned numRangeDims;
246 };
247 
248 /// Builds a relation from the given AffineMap/AffineValueMap `map`, containing
249 /// all pairs of the form `operands -> result` that satisfy `map`. `rel` is set
250 /// to the relation built. For example, give the AffineMap:
251 ///
252 /// (d0, d1)[s0] -> (d0 + s0, d0 - s0)
253 ///
254 /// the resulting relation formed is:
255 ///
256 /// (d0, d1) -> (r1, r2)
257 /// [d0 d1 r1 r2 s0 const]
258 /// 1 0 -1 0 1 0 = 0
259 /// 0 1 0 -1 -1 0 = 0
260 ///
261 /// For AffineValueMap, the domain and symbols have Value set corresponding to
262 /// the Value in `map`. Returns failure if the AffineMap could not be flattened
263 /// (i.e., semi-affine is not yet handled).
264 LogicalResult getRelationFromMap(AffineMap &map,
266 LogicalResult getRelationFromMap(const AffineValueMap &map,
268 
269 } // namespace affine
270 } // namespace mlir
271 
272 #endif // MLIR_DIALECT_AFFINE_ANALYSIS_AFFINESTRUCTURES_H
union mlir::linalg::@1198::ArityGroupAndKind::Kind kind
A multi-dimensional affine map Affine map's are immutable like Type's, and they are uniqued.
Definition: AffineMap.h:46
FlatLinearValueConstraints represents an extension of FlatLinearConstraints where each non-local vari...
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...
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...
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:387
This class represents an instance of an SSA value in the MLIR system, representing a computable value...
Definition: Value.h:96
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...
static bool classof(const IntegerRelation *cst)
void appendDomainVar(unsigned num=1)
Append num variables of the specified kind after the last variable of that kind.
FlatAffineRelation(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, unsigned numDomainDims, unsigned numRangeDims, unsigned numSymbols, unsigned numLocals, ArrayRef< std::optional< Value >> valArgs={})
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.
void inverse()
Swap domain and range of the relation.
FlatAffineValueConstraints getDomainSet() const
Returns a set corresponding to the domain/range of the affine relation.
FlatAffineRelation(unsigned numDomainDims=0, unsigned numRangeDims=0, unsigned numSymbols=0, unsigned numLocals=0)
Kind getKind() const override
Return the kind of this object.
void removeVarRange(VarKind kind, unsigned varStart, unsigned varLimit) override
Removes variables in the column range [varStart, varLimit), and copies any remaining valid data into ...
FlatAffineValueConstraints getRangeSet() const
void insertRangeVar(unsigned pos, unsigned num=1)
FlatAffineRelation(unsigned numDomainDims, unsigned numRangeDims, FlatAffineValueConstraints &fac)
FlatAffineRelation(unsigned numDomainDims, unsigned numRangeDims, IntegerPolyhedron &fac)
void insertDomainVar(unsigned pos, unsigned num=1)
Insert num variables of the specified kind after the pos variable of that kind.
FlatAffineValueConstraints is an extension of FlatLinearValueConstraints with helper functions for Af...
void addAffineIfOpDomain(AffineIfOp ifOp)
Adds constraints imposed by the affine.if operation.
void convertLoopIVSymbolsToDims()
Changes all symbol variables which are loop IVs to dim variables.
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 ...
LogicalResult addAffineParallelOpDomain(AffineParallelOp parallelOp)
Add constraints (lower and upper bounds) for the specified 'affine.parallel' operation's Value using ...
Kind getKind() const override
Return the kind of this object.
LogicalResult addAffineForOpDomain(AffineForOp forOp)
Adds constraints (lower and upper bounds) for the specified 'affine.for' operation's Value using IR i...
void addBound(presburger::BoundType type, Value val, int64_t value)
Adds a constant bound for the variable associated with the given Value.
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...
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...
LogicalResult addInductionVarOrTerminalSymbol(Value val)
Add the specified values as a dim or symbol var depending on its nature, if it already doesn't exist ...
static bool classof(const IntegerRelation *cst)
IntegerPolyhedron(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, const PresburgerSpace &space)
Constructs a set reserving memory for the specified number of constraints and variables.
An IntegerRelation represents the set of points from a PresburgerSpace that satisfy a list of affine ...
Kind
All derived classes of IntegerRelation.
IntegerRelation(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned numReservedCols, const PresburgerSpace &space)
Constructs a relation reserving memory for the specified number of constraints and variables.
LogicalResult getRelationFromMap(AffineMap &map, presburger::IntegerRelation &rel)
Builds a relation from the given AffineMap/AffineValueMap map, containing all pairs of the form opera...
BoundType
The type of bound: equal, lower bound or upper bound.
Include the generated interface declarations.