1 | //===- Utils.h - General utilities for Presburger library ------*- 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 | // Utility functions required by the Presburger Library. |
10 | // |
11 | //===----------------------------------------------------------------------===// |
12 | |
13 | #ifndef MLIR_ANALYSIS_PRESBURGER_UTILS_H |
14 | #define MLIR_ANALYSIS_PRESBURGER_UTILS_H |
15 | |
16 | #include "mlir/Analysis/Presburger/MPInt.h" |
17 | #include "mlir/Support/LLVM.h" |
18 | #include "llvm/ADT/STLExtras.h" |
19 | #include "llvm/ADT/SmallBitVector.h" |
20 | |
21 | #include "mlir/Analysis/Presburger/Matrix.h" |
22 | #include <optional> |
23 | |
24 | namespace mlir { |
25 | namespace presburger { |
26 | |
27 | class IntegerRelation; |
28 | |
29 | /// This class represents the result of operations optimizing something subject |
30 | /// to some constraints. If the constraints were not satisfiable the, kind will |
31 | /// be Empty. If the optimum is unbounded, the kind is Unbounded, and if the |
32 | /// optimum is bounded, the kind will be Bounded and `optimum` holds the optimal |
33 | /// value. |
34 | enum class OptimumKind { Empty, Unbounded, Bounded }; |
35 | template <typename T> |
36 | class MaybeOptimum { |
37 | public: |
38 | private: |
39 | OptimumKind kind = OptimumKind::Empty; |
40 | T optimum; |
41 | |
42 | public: |
43 | MaybeOptimum() = default; |
44 | MaybeOptimum(OptimumKind kind) : kind(kind) { |
45 | assert(kind != OptimumKind::Bounded && |
46 | "Bounded optima should be constructed by specifying the optimum!" ); |
47 | } |
48 | MaybeOptimum(const T &optimum) |
49 | : kind(OptimumKind::Bounded), optimum(optimum) {} |
50 | |
51 | OptimumKind getKind() const { return kind; } |
52 | bool isBounded() const { return kind == OptimumKind::Bounded; } |
53 | bool isUnbounded() const { return kind == OptimumKind::Unbounded; } |
54 | bool isEmpty() const { return kind == OptimumKind::Empty; } |
55 | |
56 | std::optional<T> getOptimumIfBounded() const { return optimum; } |
57 | const T &getBoundedOptimum() const { |
58 | assert(kind == OptimumKind::Bounded && |
59 | "This should be called only for bounded optima" ); |
60 | return optimum; |
61 | } |
62 | T &getBoundedOptimum() { |
63 | assert(kind == OptimumKind::Bounded && |
64 | "This should be called only for bounded optima" ); |
65 | return optimum; |
66 | } |
67 | const T &operator*() const { return getBoundedOptimum(); } |
68 | T &operator*() { return getBoundedOptimum(); } |
69 | const T *operator->() const { return &getBoundedOptimum(); } |
70 | T *operator->() { return &getBoundedOptimum(); } |
71 | bool operator==(const MaybeOptimum<T> &other) const { |
72 | if (kind != other.kind) |
73 | return false; |
74 | if (kind != OptimumKind::Bounded) |
75 | return true; |
76 | return optimum == other.optimum; |
77 | } |
78 | |
79 | // Given f that takes a T and returns a U, convert this `MaybeOptimum<T>` to |
80 | // a `MaybeOptimum<U>` by applying `f` to the bounded optimum if it exists, or |
81 | // returning a MaybeOptimum of the same kind otherwise. |
82 | template <class Function> |
83 | auto map(const Function &f) const & -> MaybeOptimum<decltype(f(optimum))> { |
84 | if (kind == OptimumKind::Bounded) |
85 | return f(optimum); |
86 | return kind; |
87 | } |
88 | }; |
89 | |
90 | /// `ReprKind` enum is used to set the constraint type in `MaybeLocalRepr`. |
91 | enum class ReprKind { Inequality, Equality, None }; |
92 | |
93 | /// `MaybeLocalRepr` contains the indices of the constraints that can be |
94 | /// expressed as a floordiv of an affine function. If it's an `equality` |
95 | /// constraint, `equalityIdx` is set, in case of `inequality` the |
96 | /// `lowerBoundIdx` and `upperBoundIdx` is set. By default the kind attribute is |
97 | /// set to None. |
98 | struct MaybeLocalRepr { |
99 | ReprKind kind = ReprKind::None; |
100 | explicit operator bool() const { return kind != ReprKind::None; } |
101 | union { |
102 | unsigned equalityIdx; |
103 | struct { |
104 | unsigned lowerBoundIdx, upperBoundIdx; |
105 | } inequalityPair; |
106 | } repr; |
107 | }; |
108 | |
109 | /// Class storing division representation of local variables of a constraint |
110 | /// system. The coefficients of the dividends are stored in order: |
111 | /// [nonLocalVars, localVars, constant]. Each local variable may or may not have |
112 | /// a representation. If the local does not have a representation, the dividend |
113 | /// of the division has no meaning and the denominator is zero. If it has a |
114 | /// representation, the denominator will be positive. |
115 | /// |
116 | /// The i^th division here, represents the division representation of the |
117 | /// variable at position `divOffset + i` in the constraint system. |
118 | class DivisionRepr { |
119 | public: |
120 | DivisionRepr(unsigned numVars, unsigned numDivs) |
121 | : dividends(numDivs, numVars + 1), denoms(numDivs, MPInt(0)) {} |
122 | |
123 | DivisionRepr(unsigned numVars) : dividends(0, numVars + 1) {} |
124 | |
125 | unsigned getNumVars() const { return dividends.getNumColumns() - 1; } |
126 | unsigned getNumDivs() const { return dividends.getNumRows(); } |
127 | unsigned getNumNonDivs() const { return getNumVars() - getNumDivs(); } |
128 | // Get the offset from where division variables start. |
129 | unsigned getDivOffset() const { return getNumVars() - getNumDivs(); } |
130 | |
131 | // Check whether the `i^th` division has a division representation or not. |
132 | bool hasRepr(unsigned i) const { return denoms[i] != 0; } |
133 | // Check whether all the divisions have a division representation or not. |
134 | bool hasAllReprs() const { return !llvm::is_contained(Range: denoms, Element: 0); } |
135 | |
136 | // Clear the division representation of the i^th local variable. |
137 | void clearRepr(unsigned i) { denoms[i] = 0; } |
138 | |
139 | // Get the dividend of the `i^th` division. |
140 | MutableArrayRef<MPInt> getDividend(unsigned i) { return dividends.getRow(row: i); } |
141 | ArrayRef<MPInt> getDividend(unsigned i) const { return dividends.getRow(row: i); } |
142 | |
143 | // For a given point containing values for each variable other than the |
144 | // division variables, try to find the values for each division variable from |
145 | // their division representation. |
146 | SmallVector<std::optional<MPInt>, 4> divValuesAt(ArrayRef<MPInt> point) const; |
147 | |
148 | // Get the `i^th` denominator. |
149 | MPInt &getDenom(unsigned i) { return denoms[i]; } |
150 | MPInt getDenom(unsigned i) const { return denoms[i]; } |
151 | |
152 | ArrayRef<MPInt> getDenoms() const { return denoms; } |
153 | |
154 | void setDiv(unsigned i, ArrayRef<MPInt> dividend, const MPInt &divisor) { |
155 | dividends.setRow(row: i, elems: dividend); |
156 | denoms[i] = divisor; |
157 | } |
158 | |
159 | // Find the greatest common divisor (GCD) of the dividends and divisor for |
160 | // each valid division. Divide the dividends and divisor by the GCD to |
161 | // simplify the expression. |
162 | void normalizeDivs(); |
163 | |
164 | void insertDiv(unsigned pos, ArrayRef<MPInt> dividend, const MPInt &divisor); |
165 | void insertDiv(unsigned pos, unsigned num = 1); |
166 | |
167 | /// Removes duplicate divisions. On every possible duplicate division found, |
168 | /// `merge(i, j)`, where `i`, `j` are current index of the duplicate |
169 | /// divisions, is called and division at index `j` is merged into division at |
170 | /// index `i`. If `merge(i, j)` returns `true`, the divisions are merged i.e. |
171 | /// `j^th` division gets eliminated and it's each instance is replaced by |
172 | /// `i^th` division. If it returns `false`, the divisions are not merged. |
173 | /// `merge` can also do side effects, For example it can merge the local |
174 | /// variables in IntegerRelation. |
175 | void |
176 | removeDuplicateDivs(llvm::function_ref<bool(unsigned i, unsigned j)> merge); |
177 | |
178 | void print(raw_ostream &os) const; |
179 | void dump() const; |
180 | |
181 | private: |
182 | /// Each row of the Matrix represents a single division dividend. The |
183 | /// `i^th` row represents the dividend of the variable at `divOffset + i` |
184 | /// in the constraint system (and the `i^th` local variable). |
185 | IntMatrix dividends; |
186 | |
187 | /// Denominators of each division. If a denominator of a division is `0`, the |
188 | /// division variable is considered to not have a division representation. |
189 | /// Otherwise, the denominator is positive. |
190 | SmallVector<MPInt, 4> denoms; |
191 | }; |
192 | |
193 | /// If `q` is defined to be equal to `expr floordiv d`, this equivalent to |
194 | /// saying that `q` is an integer and `q` is subject to the inequalities |
195 | /// `0 <= expr - d*q <= c - 1` (quotient remainder theorem). |
196 | /// |
197 | /// Rearranging, we get the bounds on `q`: d*q <= expr <= d*q + d - 1. |
198 | /// |
199 | /// `getDivUpperBound` returns `d*q <= expr`, and |
200 | /// `getDivLowerBound` returns `expr <= d*q + d - 1`. |
201 | /// |
202 | /// The parameter `dividend` corresponds to `expr` above, `divisor` to `d`, and |
203 | /// `localVarIdx` to the position of `q` in the coefficient list. |
204 | /// |
205 | /// The coefficient of `q` in `dividend` must be zero, as it is not allowed for |
206 | /// local variable to be a floor division of an expression involving itself. |
207 | /// The divisor must be positive. |
208 | SmallVector<MPInt, 8> getDivUpperBound(ArrayRef<MPInt> dividend, |
209 | const MPInt &divisor, |
210 | unsigned localVarIdx); |
211 | SmallVector<MPInt, 8> getDivLowerBound(ArrayRef<MPInt> dividend, |
212 | const MPInt &divisor, |
213 | unsigned localVarIdx); |
214 | |
215 | llvm::SmallBitVector getSubrangeBitVector(unsigned len, unsigned setOffset, |
216 | unsigned numSet); |
217 | |
218 | /// Check if the pos^th variable can be expressed as a floordiv of an affine |
219 | /// function of other variables (where the divisor is a positive constant). |
220 | /// `foundRepr` contains a boolean for each variable indicating if the |
221 | /// explicit representation for that variable has already been computed. |
222 | /// Return the given array as an array of MPInts. |
223 | SmallVector<MPInt, 8> getMPIntVec(ArrayRef<int64_t> range); |
224 | /// Return the given array as an array of int64_t. |
225 | SmallVector<int64_t, 8> getInt64Vec(ArrayRef<MPInt> range); |
226 | |
227 | /// Returns the `MaybeLocalRepr` struct which contains the indices of the |
228 | /// constraints that can be expressed as a floordiv of an affine function. If |
229 | /// the representation could be computed, `dividend` and `divisor` are set, |
230 | /// in which case, denominator will be positive. If the representation could |
231 | /// not be computed, the kind attribute in `MaybeLocalRepr` is set to None. |
232 | MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst, |
233 | ArrayRef<bool> foundRepr, unsigned pos, |
234 | MutableArrayRef<MPInt> dividend, |
235 | MPInt &divisor); |
236 | |
237 | /// The following overload using int64_t is required for a callsite in |
238 | /// AffineStructures.h. |
239 | MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst, |
240 | ArrayRef<bool> foundRepr, unsigned pos, |
241 | SmallVector<int64_t, 8> ÷nd, |
242 | unsigned &divisor); |
243 | |
244 | /// Given two relations, A and B, add additional local vars to the sets such |
245 | /// that both have the union of the local vars in each set, without changing |
246 | /// the set of points that lie in A and B. |
247 | /// |
248 | /// While taking union, if a local var in any set has a division representation |
249 | /// which is a duplicate of division representation, of another local var in any |
250 | /// set, it is not added to the final union of local vars and is instead merged. |
251 | /// |
252 | /// On every possible merge, `merge(i, j)` is called. `i`, `j` are position |
253 | /// of local variables in both sets which are being merged. If `merge(i, j)` |
254 | /// returns true, the divisions are merged, otherwise the divisions are not |
255 | /// merged. |
256 | void mergeLocalVars(IntegerRelation &relA, IntegerRelation &relB, |
257 | llvm::function_ref<bool(unsigned i, unsigned j)> merge); |
258 | |
259 | /// Compute the gcd of the range. |
260 | MPInt gcdRange(ArrayRef<MPInt> range); |
261 | |
262 | /// Divide the range by its gcd and return the gcd. |
263 | MPInt normalizeRange(MutableArrayRef<MPInt> range); |
264 | |
265 | /// Normalize the given (numerator, denominator) pair by dividing out the |
266 | /// common factors between them. The numerator here is an affine expression |
267 | /// with integer coefficients. The denominator must be positive. |
268 | void normalizeDiv(MutableArrayRef<MPInt> num, MPInt &denom); |
269 | |
270 | /// Return `coeffs` with all the elements negated. |
271 | SmallVector<MPInt, 8> getNegatedCoeffs(ArrayRef<MPInt> coeffs); |
272 | |
273 | /// Return the complement of the given inequality. |
274 | /// |
275 | /// The complement of a_1 x_1 + ... + a_n x_ + c >= 0 is |
276 | /// a_1 x_1 + ... + a_n x_ + c < 0, i.e., -a_1 x_1 - ... - a_n x_ - c - 1 >= 0, |
277 | /// since all the variables are constrained to be integers. |
278 | SmallVector<MPInt, 8> getComplementIneq(ArrayRef<MPInt> ineq); |
279 | |
280 | /// Compute the dot product of two vectors. |
281 | /// The vectors must have the same sizes. |
282 | Fraction dotProduct(ArrayRef<Fraction> a, ArrayRef<Fraction> b); |
283 | |
284 | /// Find the product of two polynomials, each given by an array of |
285 | /// coefficients. |
286 | std::vector<Fraction> multiplyPolynomials(ArrayRef<Fraction> a, |
287 | ArrayRef<Fraction> b); |
288 | |
289 | bool isRangeZero(ArrayRef<Fraction> arr); |
290 | |
291 | } // namespace presburger |
292 | } // namespace mlir |
293 | |
294 | #endif // MLIR_ANALYSIS_PRESBURGER_UTILS_H |
295 | |