893d4ea4ff46fe2a726cc2d2b0ada9b7af9c45fb
[lldb.git] / mlir / include / mlir / Analysis / AffineStructures.h
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_ANALYSIS_AFFINE_STRUCTURES_H
14 #define MLIR_ANALYSIS_AFFINE_STRUCTURES_H
15
16 #include "mlir/Analysis/Presburger/Matrix.h"
17 #include "mlir/IR/AffineExpr.h"
18 #include "mlir/IR/OpDefinition.h"
19 #include "mlir/Support/LogicalResult.h"
20
21 namespace mlir {
22
23 class AffineCondition;
24 class AffineForOp;
25 class AffineIfOp;
26 class AffineMap;
27 class AffineValueMap;
28 class IntegerSet;
29 class MLIRContext;
30 class Value;
31 class MemRefType;
32 struct MutableAffineMap;
33
34 /// A flat list of affine equalities and inequalities in the form.
35 /// Inequality: c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} >= 0
36 /// Equality: c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} == 0
37 ///
38 /// FlatAffineConstraints stores coefficients in a contiguous buffer (one buffer
39 /// for equalities and one for inequalities). The size of each buffer is
40 /// numReservedCols * number of inequalities (or equalities). The reserved size
41 /// is numReservedCols * numReservedInequalities (or numReservedEqualities). A
42 /// coefficient (r, c) lives at the location numReservedCols * r + c in the
43 /// buffer. The extra space between getNumCols() and numReservedCols exists to
44 /// prevent frequent movement of data when adding columns, especially at the
45 /// end.
46 ///
47 /// The identifiers x_0, x_1, ... appear in the order: dimensional identifiers,
48 /// symbolic identifiers, and local identifiers.  The local identifiers
49 /// correspond to local/internal variables created when converting from
50 /// AffineExpr's containing mod's and div's; they are thus needed to increase
51 /// representational power. Each local identifier is always (by construction) a
52 /// floordiv of a pure add/mul affine function of dimensional, symbolic, and
53 /// other local identifiers, in a non-mutually recursive way. Hence, every local
54 /// identifier can ultimately always be recovered as an affine function of
55 /// dimensional and symbolic identifiers (involving floordiv's); note however
56 /// that some floordiv combinations are converted to mod's by AffineExpr
57 /// construction.
58 ///
59 class FlatAffineConstraints {
60 public:
61   enum IdKind { Dimension, Symbol, Local };
62
63   /// Constructs a constraint system reserving memory for the specified number
64   /// of constraints and identifiers..
65   FlatAffineConstraints(unsigned numReservedInequalities,
66                         unsigned numReservedEqualities,
67                         unsigned numReservedCols, unsigned numDims = 0,
68                         unsigned numSymbols = 0, unsigned numLocals = 0,
69                         ArrayRef<Optional<Value>> idArgs = {})
70       : numReservedCols(numReservedCols), numDims(numDims),
71         numSymbols(numSymbols) {
72     assert(numReservedCols >= numDims + numSymbols + 1);
73     assert(idArgs.empty() || idArgs.size() == numDims + numSymbols + numLocals);
74     equalities.reserve(numReservedCols * numReservedEqualities);
75     inequalities.reserve(numReservedCols * numReservedInequalities);
76     numIds = numDims + numSymbols + numLocals;
77     ids.reserve(numReservedCols);
78     if (idArgs.empty())
79       ids.resize(numIds, None);
80     else
81       ids.append(idArgs.begin(), idArgs.end());
82   }
83
84   /// Constructs a constraint system with the specified number of
85   /// dimensions and symbols.
86   FlatAffineConstraints(unsigned numDims = 0, unsigned numSymbols = 0,
87                         unsigned numLocals = 0,
88                         ArrayRef<Optional<Value>> idArgs = {})
89       : numReservedCols(numDims + numSymbols + numLocals + 1), numDims(numDims),
90         numSymbols(numSymbols) {
91     assert(numReservedCols >= numDims + numSymbols + 1);
92     assert(idArgs.empty() || idArgs.size() == numDims + numSymbols + numLocals);
93     numIds = numDims + numSymbols + numLocals;
94     ids.reserve(numIds);
95     if (idArgs.empty())
96       ids.resize(numIds, None);
97     else
98       ids.append(idArgs.begin(), idArgs.end());
99   }
100
101   /// Return a system with no constraints, i.e., one which is satisfied by all
102   /// points.
103   static FlatAffineConstraints getUniverse(unsigned numDims = 0,
104                                            unsigned numSymbols = 0) {
105     return FlatAffineConstraints(numDims, numSymbols);
106   }
107
108   /// Create a flat affine constraint system from an AffineValueMap or a list of
109   /// these. The constructed system will only include equalities.
110   explicit FlatAffineConstraints(const AffineValueMap &avm);
111   explicit FlatAffineConstraints(ArrayRef<const AffineValueMap *> avmRef);
112
113   /// Creates an affine constraint system from an IntegerSet.
114   explicit FlatAffineConstraints(IntegerSet set);
115
116   FlatAffineConstraints(const FlatAffineConstraints &other);
117
118   FlatAffineConstraints(ArrayRef<const AffineValueMap *> avmRef,
119                         IntegerSet set);
120
121   FlatAffineConstraints(const MutableAffineMap &map);
122
123   ~FlatAffineConstraints() {}
124
125   // Clears any existing data and reserves memory for the specified constraints.
126   void reset(unsigned numReservedInequalities, unsigned numReservedEqualities,
127              unsigned numReservedCols, unsigned numDims, unsigned numSymbols,
128              unsigned numLocals = 0, ArrayRef<Value> idArgs = {});
129
130   void reset(unsigned numDims = 0, unsigned numSymbols = 0,
131              unsigned numLocals = 0, ArrayRef<Value> idArgs = {});
132
133   /// Appends constraints from 'other' into this. This is equivalent to an
134   /// intersection with no simplification of any sort attempted.
135   void append(const FlatAffineConstraints &other);
136
137   /// Checks for emptiness by performing variable elimination on all
138   /// identifiers, running the GCD test on each equality constraint, and
139   /// checking for invalid constraints. Returns true if the GCD test fails for
140   /// any equality, or if any invalid constraints are discovered on any row.
141   /// Returns false otherwise.
142   bool isEmpty() const;
143
144   /// Runs the GCD test on all equality constraints. Returns 'true' if this test
145   /// fails on any equality. Returns 'false' otherwise.
146   /// This test can be used to disprove the existence of a solution. If it
147   /// returns true, no integer solution to the equality constraints can exist.
148   bool isEmptyByGCDTest() const;
149
150   /// Runs the GCD test heuristic. If it proves inconclusive, falls back to
151   /// generalized basis reduction if the set is bounded.
152   ///
153   /// Returns true if the set of constraints is found to have no solution,
154   /// false if a solution exists or all tests were inconclusive.
155   bool isIntegerEmpty() const;
156
157   // Returns a matrix where each row is a vector along which the polytope is
158   // bounded. The span of the returned vectors is guaranteed to contain all
159   // such vectors. The returned vectors are NOT guaranteed to be linearly
160   // independent. This function should not be called on empty sets.
161   Matrix getBoundedDirections() const;
162
163   /// Find a sample point satisfying the constraints. This uses a branch and
164   /// bound algorithm with generalized basis reduction, which always works if
165   /// the set is bounded. This should not be called for unbounded sets.
166   ///
167   /// Returns such a point if one exists, or an empty Optional otherwise.
168   Optional<SmallVector<int64_t, 8>> findIntegerSample() const;
169
170   /// Returns true if the given point satisfies the constraints, or false
171   /// otherwise.
172   bool containsPoint(ArrayRef<int64_t> point) const;
173
174   // Clones this object.
175   std::unique_ptr<FlatAffineConstraints> clone() const;
176
177   /// Returns the value at the specified equality row and column.
178   inline int64_t atEq(unsigned i, unsigned j) const {
179     return equalities[i * numReservedCols + j];
180   }
181   inline int64_t &atEq(unsigned i, unsigned j) {
182     return equalities[i * numReservedCols + j];
183   }
184
185   inline int64_t atIneq(unsigned i, unsigned j) const {
186     return inequalities[i * numReservedCols + j];
187   }
188
189   inline int64_t &atIneq(unsigned i, unsigned j) {
190     return inequalities[i * numReservedCols + j];
191   }
192
193   /// Returns the number of columns in the constraint system.
194   inline unsigned getNumCols() const { return numIds + 1; }
195
196   inline unsigned getNumEqualities() const {
197     assert(equalities.size() % numReservedCols == 0 &&
198            "inconsistent equality buffer size");
199     return equalities.size() / numReservedCols;
200   }
201
202   inline unsigned getNumInequalities() const {
203     assert(inequalities.size() % numReservedCols == 0 &&
204            "inconsistent inequality buffer size");
205     return inequalities.size() / numReservedCols;
206   }
207
208   inline unsigned getNumReservedEqualities() const {
209     return equalities.capacity() / numReservedCols;
210   }
211
212   inline unsigned getNumReservedInequalities() const {
213     return inequalities.capacity() / numReservedCols;
214   }
215
216   inline ArrayRef<int64_t> getEquality(unsigned idx) const {
217     return ArrayRef<int64_t>(&equalities[idx * numReservedCols], getNumCols());
218   }
219
220   inline ArrayRef<int64_t> getInequality(unsigned idx) const {
221     return ArrayRef<int64_t>(&inequalities[idx * numReservedCols],
222                              getNumCols());
223   }
224
225   /// Adds constraints (lower and upper bounds) for the specified 'affine.for'
226   /// operation's Value using IR information stored in its bound maps. The
227   /// right identifier is first looked up using forOp's Value. Asserts if the
228   /// Value corresponding to the 'affine.for' operation isn't found in the
229   /// constraint system. Returns failure for the yet unimplemented/unsupported
230   /// cases.  Any new identifiers that are found in the bound operands of the
231   /// 'affine.for' operation are added as trailing identifiers (either
232   /// dimensional or symbolic depending on whether the operand is a valid
233   /// symbol).
234   //  TODO: add support for non-unit strides.
235   LogicalResult addAffineForOpDomain(AffineForOp forOp);
236
237   /// Adds constraints (lower and upper bounds) for each loop in the loop nest
238   /// described by the bound maps 'lbMaps' and 'ubMaps' of a computation slice.
239   /// Every pair ('lbMaps[i]', 'ubMaps[i]') describes the bounds of a loop in
240   /// the nest, sorted outer-to-inner. 'operands' contains the bound operands
241   /// for a single bound map. All the bound maps will use the same bound
242   /// operands. Note that some loops described by a computation slice might not
243   /// exist yet in the IR so the Value attached to those dimension identifiers
244   /// might be empty. For that reason, this method doesn't perform Value
245   /// look-ups to retrieve the dimension identifier positions. Instead, it
246   /// assumes the position of the dim identifiers in the constraint system is
247   /// the same as the position of the loop in the loop nest.
248   LogicalResult addDomainFromSliceMaps(ArrayRef<AffineMap> lbMaps,
249                                        ArrayRef<AffineMap> ubMaps,
250                                        ArrayRef<Value> operands);
251
252   /// Adds constraints imposed by the `affine.if` operation. These constraints
253   /// are collected from the IntegerSet attached to the given `affine.if`
254   /// instance argument (`ifOp`). It is asserted that:
255   /// 1) The IntegerSet of the given `affine.if` instance should not contain
256   /// semi-affine expressions,
257   /// 2) The columns of the constraint system created from `ifOp` should match
258   /// the columns in the current one regarding numbers and values.
259   void addAffineIfOpDomain(AffineIfOp ifOp);
260
261   /// Adds a lower or an upper bound for the identifier at the specified
262   /// position with constraints being drawn from the specified bound map and
263   /// operands. If `eq` is true, add a single equality equal to the bound map's
264   /// first result expr.
265   LogicalResult addLowerOrUpperBound(unsigned pos, AffineMap boundMap,
266                                      ValueRange operands, bool eq,
267                                      bool lower = true);
268
269   /// Returns the bound for the identifier at `pos` from the inequality at
270   /// `ineqPos` as a 1-d affine value map (affine map + operands). The returned
271   /// affine value map can either be a lower bound or an upper bound depending
272   /// on the sign of atIneq(ineqPos, pos). Asserts if the row at `ineqPos` does
273   /// not involve the `pos`th identifier.
274   void getIneqAsAffineValueMap(unsigned pos, unsigned ineqPos,
275                                AffineValueMap &vmap,
276                                MLIRContext *context) const;
277
278   /// Returns the constraint system as an integer set. Returns a null integer
279   /// set if the system has no constraints, or if an integer set couldn't be
280   /// constructed as a result of a local variable's explicit representation not
281   /// being known and such a local variable appearing in any of the constraints.
282   IntegerSet getAsIntegerSet(MLIRContext *context) const;
283
284   /// Computes the lower and upper bounds of the first 'num' dimensional
285   /// identifiers (starting at 'offset') as an affine map of the remaining
286   /// identifiers (dimensional and symbolic). This method is able to detect
287   /// identifiers as floordiv's and mod's of affine expressions of other
288   /// identifiers with respect to (positive) constants. Sets bound map to a
289   /// null AffineMap if such a bound can't be found (or yet unimplemented).
290   void getSliceBounds(unsigned offset, unsigned num, MLIRContext *context,
291                       SmallVectorImpl<AffineMap> *lbMaps,
292                       SmallVectorImpl<AffineMap> *ubMaps);
293
294   /// Adds slice lower bounds represented by lower bounds in 'lbMaps' and upper
295   /// bounds in 'ubMaps' to each identifier in the constraint system which has
296   /// a value in 'values'. Note that both lower/upper bounds share the same
297   /// operand list 'operands'.
298   /// This function assumes 'values.size' == 'lbMaps.size' == 'ubMaps.size'.
299   /// Note that both lower/upper bounds use operands from 'operands'.
300   LogicalResult addSliceBounds(ArrayRef<Value> values,
301                                ArrayRef<AffineMap> lbMaps,
302                                ArrayRef<AffineMap> ubMaps,
303                                ArrayRef<Value> operands);
304
305   // Adds an inequality (>= 0) from the coefficients specified in inEq.
306   void addInequality(ArrayRef<int64_t> inEq);
307   // Adds an equality from the coefficients specified in eq.
308   void addEquality(ArrayRef<int64_t> eq);
309
310   /// Adds a constant lower bound constraint for the specified identifier.
311   void addConstantLowerBound(unsigned pos, int64_t lb);
312   /// Adds a constant upper bound constraint for the specified identifier.
313   void addConstantUpperBound(unsigned pos, int64_t ub);
314
315   /// Adds a new local identifier as the floordiv of an affine function of other
316   /// identifiers, the coefficients of which are provided in 'dividend' and with
317   /// respect to a positive constant 'divisor'. Two constraints are added to the
318   /// system to capture equivalence with the floordiv:
319   /// q = dividend floordiv c    <=>   c*q <= dividend <= c*q + c - 1.
320   void addLocalFloorDiv(ArrayRef<int64_t> dividend, int64_t divisor);
321
322   /// Adds a constant lower bound constraint for the specified expression.
323   void addConstantLowerBound(ArrayRef<int64_t> expr, int64_t lb);
324   /// Adds a constant upper bound constraint for the specified expression.
325   void addConstantUpperBound(ArrayRef<int64_t> expr, int64_t ub);
326
327   /// Sets the identifier at the specified position to a constant.
328   void setIdToConstant(unsigned pos, int64_t val);
329
330   /// Sets the identifier corresponding to the specified Value id to a
331   /// constant. Asserts if the 'id' is not found.
332   void setIdToConstant(Value id, int64_t val);
333
334   /// Looks up the position of the identifier with the specified Value. Returns
335   /// true if found (false otherwise). `pos' is set to the (column) position of
336   /// the identifier.
337   bool findId(Value id, unsigned *pos) const;
338
339   /// Returns true if an identifier with the specified Value exists, false
340   /// otherwise.
341   bool containsId(Value id) const;
342
343   /// Swap the posA^th identifier with the posB^th identifier.
344   void swapId(unsigned posA, unsigned posB);
345
346   // Add identifiers of the specified kind - specified positions are relative to
347   // the kind of identifier. The coefficient column corresponding to the added
348   // identifier is initialized to zero. 'id' is the Value corresponding to the
349   // identifier that can optionally be provided.
350   void addDimId(unsigned pos, Value id = nullptr);
351   void addSymbolId(unsigned pos, Value id = nullptr);
352   void addLocalId(unsigned pos);
353   void addId(IdKind kind, unsigned pos, Value id = nullptr);
354
355   /// Add the specified values as a dim or symbol id depending on its nature, if
356   /// it already doesn't exist in the system. `id' has to be either a terminal
357   /// symbol or a loop IV, i.e., it cannot be the result affine.apply of any
358   /// symbols or loop IVs. The identifier is added to the end of the existing
359   /// dims or symbols. Additional information on the identifier is extracted
360   /// from the IR and added to the constraint system.
361   void addInductionVarOrTerminalSymbol(Value id);
362
363   /// Composes the affine value map with this FlatAffineConstrains, adding the
364   /// results of the map as dimensions at the front [0, vMap->getNumResults())
365   /// and with the dimensions set to the equalities specified by the value map.
366   /// Returns failure if the composition fails (when vMap is a semi-affine map).
367   /// The vMap's operand Value's are used to look up the right positions in
368   /// the FlatAffineConstraints with which to associate. The dimensional and
369   /// symbolic operands of vMap should match 1:1 (in the same order) with those
370   /// of this constraint system, but the latter could have additional trailing
371   /// operands.
372   LogicalResult composeMap(const AffineValueMap *vMap);
373
374   /// Composes an affine map whose dimensions match one to one to the
375   /// dimensions of this FlatAffineConstraints. The results of the map 'other'
376   /// are added as the leading dimensions of this constraint system. Returns
377   /// failure if 'other' is a semi-affine map.
378   LogicalResult composeMatchingMap(AffineMap other);
379
380   /// Projects out (aka eliminates) 'num' identifiers starting at position
381   /// 'pos'. The resulting constraint system is the shadow along the dimensions
382   /// that still exist. This method may not always be integer exact.
383   // TODO: deal with integer exactness when necessary - can return a value to
384   // mark exactness for example.
385   void projectOut(unsigned pos, unsigned num);
386   inline void projectOut(unsigned pos) { return projectOut(pos, 1); }
387
388   /// Projects out the identifier that is associate with Value .
389   void projectOut(Value id);
390
391   /// Removes the specified identifier from the system.
392   void removeId(unsigned pos);
393
394   void removeEquality(unsigned pos);
395   void removeInequality(unsigned pos);
396
397   /// Changes the partition between dimensions and symbols. Depending on the new
398   /// symbol count, either a chunk of trailing dimensional identifiers becomes
399   /// symbols, or some of the leading symbols become dimensions.
400   void setDimSymbolSeparation(unsigned newSymbolCount);
401
402   /// Changes all symbol identifiers which are loop IVs to dim identifiers.
403   void convertLoopIVSymbolsToDims();
404
405   /// Sets the specified identifier to a constant and removes it.
406   void setAndEliminate(unsigned pos, int64_t constVal);
407
408   /// Tries to fold the specified identifier to a constant using a trivial
409   /// equality detection; if successful, the constant is substituted for the
410   /// identifier everywhere in the constraint system and then removed from the
411   /// system.
412   LogicalResult constantFoldId(unsigned pos);
413
414   /// This method calls constantFoldId for the specified range of identifiers,
415   /// 'num' identifiers starting at position 'pos'.
416   void constantFoldIdRange(unsigned pos, unsigned num);
417
418   /// Updates the constraints to be the smallest bounding (enclosing) box that
419   /// contains the points of 'this' set and that of 'other', with the symbols
420   /// being treated specially. For each of the dimensions, the min of the lower
421   /// bounds (symbolic) and the max of the upper bounds (symbolic) is computed
422   /// to determine such a bounding box. `other' is expected to have the same
423   /// dimensional identifiers as this constraint system (in the same order).
424   ///
425   /// Eg: if 'this' is {0 <= d0 <= 127}, 'other' is {16 <= d0 <= 192}, the
426   ///      output is {0 <= d0 <= 192}.
427   /// 2) 'this' = {s0 + 5 <= d0 <= s0 + 20}, 'other' is {s0 + 1 <= d0 <= s0 +
428   ///     9}, output = {s0 + 1 <= d0 <= s0 + 20}.
429   /// 3) 'this' = {0 <= d0 <= 5, 1 <= d1 <= 9}, 'other' = {2 <= d0 <= 6, 5 <= d1
430   ///     <= 15}, output = {0 <= d0 <= 6, 1 <= d1 <= 15}.
431   LogicalResult unionBoundingBox(const FlatAffineConstraints &other);
432
433   /// Returns 'true' if this constraint system and 'other' are in the same
434   /// space, i.e., if they are associated with the same set of identifiers,
435   /// appearing in the same order. Returns 'false' otherwise.
436   bool areIdsAlignedWithOther(const FlatAffineConstraints &other);
437
438   /// Merge and align the identifiers of 'this' and 'other' starting at
439   /// 'offset', so that both constraint systems get the union of the contained
440   /// identifiers that is dimension-wise and symbol-wise unique; both
441   /// constraint systems are updated so that they have the union of all
442   /// identifiers, with this's original identifiers appearing first followed by
443   /// any of other's identifiers that didn't appear in 'this'. Local
444   /// identifiers of each system are by design separate/local and are placed
445   /// one after other (this's followed by other's).
446   //  Eg: Input: 'this'  has ((%i %j) [%M %N])
447   //             'other' has (%k, %j) [%P, %N, %M])
448   //      Output: both 'this', 'other' have (%i, %j, %k) [%M, %N, %P]
449   //
450   void mergeAndAlignIdsWithOther(unsigned offset, FlatAffineConstraints *other);
451
452   unsigned getNumConstraints() const {
453     return getNumInequalities() + getNumEqualities();
454   }
455   inline unsigned getNumIds() const { return numIds; }
456   inline unsigned getNumDimIds() const { return numDims; }
457   inline unsigned getNumSymbolIds() const { return numSymbols; }
458   inline unsigned getNumDimAndSymbolIds() const { return numDims + numSymbols; }
459   inline unsigned getNumLocalIds() const {
460     return numIds - numDims - numSymbols;
461   }
462
463   inline ArrayRef<Optional<Value>> getIds() const {
464     return {ids.data(), ids.size()};
465   }
466   inline MutableArrayRef<Optional<Value>> getIds() {
467     return {ids.data(), ids.size()};
468   }
469
470   /// Returns the optional Value corresponding to the pos^th identifier.
471   inline Optional<Value> getId(unsigned pos) const { return ids[pos]; }
472   inline Optional<Value> &getId(unsigned pos) { return ids[pos]; }
473
474   /// Returns the Value associated with the pos^th identifier. Asserts if
475   /// no Value identifier was associated.
476   inline Value getIdValue(unsigned pos) const {
477     assert(ids[pos].hasValue() && "identifier's Value not set");
478     return ids[pos].getValue();
479   }
480
481   /// Returns the Values associated with identifiers in range [start, end).
482   /// Asserts if no Value was associated with one of these identifiers.
483   void getIdValues(unsigned start, unsigned end,
484                    SmallVectorImpl<Value> *values) const {
485     assert((start < numIds || start == end) && "invalid start position");
486     assert(end <= numIds && "invalid end position");
487     values->clear();
488     values->reserve(end - start);
489     for (unsigned i = start; i < end; i++) {
490       values->push_back(getIdValue(i));
491     }
492   }
493   inline void getAllIdValues(SmallVectorImpl<Value> *values) const {
494     getIdValues(0, numIds, values);
495   }
496
497   /// Sets Value associated with the pos^th identifier.
498   inline void setIdValue(unsigned pos, Value val) {
499     assert(pos < numIds && "invalid id position");
500     ids[pos] = val;
501   }
502   /// Sets Values associated with identifiers in the range [start, end).
503   void setIdValues(unsigned start, unsigned end, ArrayRef<Value> values) {
504     assert((start < numIds || end == start) && "invalid start position");
505     assert(end <= numIds && "invalid end position");
506     assert(values.size() == end - start);
507     for (unsigned i = start; i < end; ++i)
508       ids[i] = values[i - start];
509   }
510
511   /// Clears this list of constraints and copies other into it.
512   void clearAndCopyFrom(const FlatAffineConstraints &other);
513
514   /// Returns the smallest known constant bound for the extent of the specified
515   /// identifier (pos^th), i.e., the smallest known constant that is greater
516   /// than or equal to 'exclusive upper bound' - 'lower bound' of the
517   /// identifier. Returns None if it's not a constant. This method employs
518   /// trivial (low complexity / cost) checks and detection. Symbolic identifiers
519   /// are treated specially, i.e., it looks for constant differences between
520   /// affine expressions involving only the symbolic identifiers. `lb` and
521   /// `ub` (along with the `boundFloorDivisor`) are set to represent the lower
522   /// and upper bound associated with the constant difference: `lb`, `ub` have
523   /// the coefficients, and boundFloorDivisor, their divisor. `minLbPos` and
524   /// `minUbPos` if non-null are set to the position of the constant lower bound
525   /// and upper bound respectively (to the same if they are from an equality).
526   /// Ex: if the lower bound is [(s0 + s2 - 1) floordiv 32] for a system with
527   /// three symbolic identifiers, *lb = [1, 0, 1], lbDivisor = 32. See comments
528   /// at function definition for examples.
529   Optional<int64_t> getConstantBoundOnDimSize(
530       unsigned pos, SmallVectorImpl<int64_t> *lb = nullptr,
531       int64_t *boundFloorDivisor = nullptr,
532       SmallVectorImpl<int64_t> *ub = nullptr, unsigned *minLbPos = nullptr,
533       unsigned *minUbPos = nullptr) const;
534
535   /// Returns the constant lower bound for the pos^th identifier if there is
536   /// one; None otherwise.
537   Optional<int64_t> getConstantLowerBound(unsigned pos) const;
538
539   /// Returns the constant upper bound for the pos^th identifier if there is
540   /// one; None otherwise.
541   Optional<int64_t> getConstantUpperBound(unsigned pos) const;
542
543   /// Gets the lower and upper bound of the `offset` + `pos`th identifier
544   /// treating [0, offset) U [offset + num, symStartPos) as dimensions and
545   /// [symStartPos, getNumDimAndSymbolIds) as symbols, and `pos` lies in
546   /// [0, num). The multi-dimensional maps in the returned pair represent the
547   /// max and min of potentially multiple affine expressions. The upper bound is
548   /// exclusive. `localExprs` holds pre-computed AffineExpr's for all local
549   /// identifiers in the system.
550   std::pair<AffineMap, AffineMap>
551   getLowerAndUpperBound(unsigned pos, unsigned offset, unsigned num,
552                         unsigned symStartPos, ArrayRef<AffineExpr> localExprs,
553                         MLIRContext *context) const;
554
555   /// Gather positions of all lower and upper bounds of the identifier at `pos`,
556   /// and optionally any equalities on it. In addition, the bounds are to be
557   /// independent of identifiers in position range [`offset`, `offset` + `num`).
558   void
559   getLowerAndUpperBoundIndices(unsigned pos,
560                                SmallVectorImpl<unsigned> *lbIndices,
561                                SmallVectorImpl<unsigned> *ubIndices,
562                                SmallVectorImpl<unsigned> *eqIndices = nullptr,
563                                unsigned offset = 0, unsigned num = 0) const;
564
565   /// Removes constraints that are independent of (i.e., do not have a
566   /// coefficient for) for identifiers in the range [pos, pos + num).
567   void removeIndependentConstraints(unsigned pos, unsigned num);
568
569   /// Returns true if the set can be trivially detected as being
570   /// hyper-rectangular on the specified contiguous set of identifiers.
571   bool isHyperRectangular(unsigned pos, unsigned num) const;
572
573   /// Removes duplicate constraints, trivially true constraints, and constraints
574   /// that can be detected as redundant as a result of differing only in their
575   /// constant term part. A constraint of the form <non-negative constant> >= 0
576   /// is considered trivially true. This method is a linear time method on the
577   /// constraints, does a single scan, and updates in place. It also normalizes
578   /// constraints by their GCD and performs GCD tightening on inequalities.
579   void removeTrivialRedundancy();
580
581   /// A more expensive check to detect redundant inequalities thatn
582   /// removeTrivialRedundancy.
583   void removeRedundantInequalities();
584
585   /// Removes redundant constraints using Simplex. Although the algorithm can
586   /// theoretically take exponential time in the worst case (rare), it is known
587   /// to perform much better in the average case. If V is the number of vertices
588   /// in the polytope and C is the number of constraints, the algorithm takes
589   /// O(VC) time.
590   void removeRedundantConstraints();
591
592   // Removes all equalities and inequalities.
593   void clearConstraints();
594
595   void print(raw_ostream &os) const;
596   void dump() const;
597
598 private:
599   /// Returns false if the fields corresponding to various identifier counts, or
600   /// equality/inequality buffer sizes aren't consistent; true otherwise. This
601   /// is meant to be used within an assert internally.
602   bool hasConsistentState() const;
603
604   /// Checks all rows of equality/inequality constraints for trivial
605   /// contradictions (for example: 1 == 0, 0 >= 1), which may have surfaced
606   /// after elimination. Returns 'true' if an invalid constraint is found;
607   /// 'false'otherwise.
608   bool hasInvalidConstraint() const;
609
610   /// Returns the constant lower bound bound if isLower is true, and the upper
611   /// bound if isLower is false.
612   template <bool isLower>
613   Optional<int64_t> computeConstantLowerOrUpperBound(unsigned pos);
614
615   // Eliminates a single identifier at 'position' from equality and inequality
616   // constraints. Returns 'success' if the identifier was eliminated, and
617   // 'failure' otherwise.
618   inline LogicalResult gaussianEliminateId(unsigned position) {
619     return success(gaussianEliminateIds(position, position + 1) == 1);
620   }
621
622   // Eliminates identifiers from equality and inequality constraints
623   // in column range [posStart, posLimit).
624   // Returns the number of variables eliminated.
625   unsigned gaussianEliminateIds(unsigned posStart, unsigned posLimit);
626
627   /// Eliminates identifier at the specified position using Fourier-Motzkin
628   /// variable elimination, but uses Gaussian elimination if there is an
629   /// equality involving that identifier. If the result of the elimination is
630   /// integer exact, *isResultIntegerExact is set to true. If 'darkShadow' is
631   /// set to true, a potential under approximation (subset) of the rational
632   /// shadow / exact integer shadow is computed.
633   // See implementation comments for more details.
634   void FourierMotzkinEliminate(unsigned pos, bool darkShadow = false,
635                                bool *isResultIntegerExact = nullptr);
636
637   /// Tightens inequalities given that we are dealing with integer spaces. This
638   /// is similar to the GCD test but applied to inequalities. The constant term
639   /// can be reduced to the preceding multiple of the GCD of the coefficients,
640   /// i.e.,
641   ///  64*i - 100 >= 0  =>  64*i - 128 >= 0 (since 'i' is an integer). This is a
642   /// fast method (linear in the number of coefficients).
643   void GCDTightenInequalities();
644
645   /// Normalized each constraints by the GCD of its coefficients.
646   void normalizeConstraintsByGCD();
647
648   /// Removes identifiers in the column range [idStart, idLimit), and copies any
649   /// remaining valid data into place, updates member variables, and resizes
650   /// arrays as needed.
651   void removeIdRange(unsigned idStart, unsigned idLimit);
652
653   /// Coefficients of affine equalities (in == 0 form).
654   SmallVector<int64_t, 64> equalities;
655
656   /// Coefficients of affine inequalities (in >= 0 form).
657   SmallVector<int64_t, 64> inequalities;
658
659   /// Number of columns reserved. Actual ones in used are returned by
660   /// getNumCols().
661   unsigned numReservedCols;
662
663   /// Total number of identifiers.
664   unsigned numIds;
665
666   /// Number of identifiers corresponding to real dimensions.
667   unsigned numDims;
668
669   /// Number of identifiers corresponding to symbols (unknown but constant for
670   /// analysis).
671   unsigned numSymbols;
672
673   /// Values corresponding to the (column) identifiers of this constraint
674   /// system appearing in the order the identifiers correspond to columns.
675   /// Temporary ones or those that aren't associated to any Value are set to
676   /// None.
677   SmallVector<Optional<Value>, 8> ids;
678
679   /// A parameter that controls detection of an unrealistic number of
680   /// constraints. If the number of constraints is this many times the number of
681   /// variables, we consider such a system out of line with the intended use
682   /// case of FlatAffineConstraints.
683   // The rationale for 32 is that in the typical simplest of cases, an
684   // identifier is expected to have one lower bound and one upper bound
685   // constraint. With a level of tiling or a connection to another identifier
686   // through a div or mod, an extra pair of bounds gets added. As a limit, we
687   // don't expect an identifier to have more than 32 lower/upper/equality
688   // constraints. This is conservatively set low and can be raised if needed.
689   constexpr static unsigned kExplosionFactor = 32;
690 };
691
692 /// Flattens 'expr' into 'flattenedExpr', which contains the coefficients of the
693 /// dimensions, symbols, and additional variables that represent floor divisions
694 /// of dimensions, symbols, and in turn other floor divisions.  Returns failure
695 /// if 'expr' could not be flattened (i.e., semi-affine is not yet handled).
696 /// 'cst' contains constraints that connect newly introduced local identifiers
697 /// to existing dimensional and symbolic identifiers. See documentation for
698 /// AffineExprFlattener on how mod's and div's are flattened.
699 LogicalResult getFlattenedAffineExpr(AffineExpr expr, unsigned numDims,
700                                      unsigned numSymbols,
701                                      SmallVectorImpl<int64_t> *flattenedExpr,
702                                      FlatAffineConstraints *cst = nullptr);
703
704 /// Flattens the result expressions of the map to their corresponding flattened
705 /// forms and set in 'flattenedExprs'. Returns failure if any expression in the
706 /// map could not be flattened (i.e., semi-affine is not yet handled). 'cst'
707 /// contains constraints that connect newly introduced local identifiers to
708 /// existing dimensional and / symbolic identifiers. See documentation for
709 /// AffineExprFlattener on how mod's and div's are flattened. For all affine
710 /// expressions that share the same operands (like those of an affine map), this
711 /// method should be used instead of repeatedly calling getFlattenedAffineExpr
712 /// since local variables added to deal with div's and mod's will be reused
713 /// across expressions.
714 LogicalResult
715 getFlattenedAffineExprs(AffineMap map,
716                         std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
717                         FlatAffineConstraints *cst = nullptr);
718 LogicalResult
719 getFlattenedAffineExprs(IntegerSet set,
720                         std::vector<SmallVector<int64_t, 8>> *flattenedExprs,
721                         FlatAffineConstraints *cst = nullptr);
722
723 } // end namespace mlir.
724
725 #endif // MLIR_ANALYSIS_AFFINE_STRUCTURES_H