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