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