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
24namespace mlir {
25namespace presburger {
26
27class 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.
34enum class OptimumKind { Empty, Unbounded, Bounded };
35template <typename T>
36class MaybeOptimum {
37public:
38private:
39 OptimumKind kind = OptimumKind::Empty;
40 T optimum;
41
42public:
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`.
91enum 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.
98struct 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.
118class DivisionRepr {
119public:
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
181private:
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.
208SmallVector<MPInt, 8> getDivUpperBound(ArrayRef<MPInt> dividend,
209 const MPInt &divisor,
210 unsigned localVarIdx);
211SmallVector<MPInt, 8> getDivLowerBound(ArrayRef<MPInt> dividend,
212 const MPInt &divisor,
213 unsigned localVarIdx);
214
215llvm::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.
223SmallVector<MPInt, 8> getMPIntVec(ArrayRef<int64_t> range);
224/// Return the given array as an array of int64_t.
225SmallVector<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.
232MaybeLocalRepr 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.
239MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst,
240 ArrayRef<bool> foundRepr, unsigned pos,
241 SmallVector<int64_t, 8> &dividend,
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.
256void mergeLocalVars(IntegerRelation &relA, IntegerRelation &relB,
257 llvm::function_ref<bool(unsigned i, unsigned j)> merge);
258
259/// Compute the gcd of the range.
260MPInt gcdRange(ArrayRef<MPInt> range);
261
262/// Divide the range by its gcd and return the gcd.
263MPInt 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.
268void normalizeDiv(MutableArrayRef<MPInt> num, MPInt &denom);
269
270/// Return `coeffs` with all the elements negated.
271SmallVector<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.
278SmallVector<MPInt, 8> getComplementIneq(ArrayRef<MPInt> ineq);
279
280/// Compute the dot product of two vectors.
281/// The vectors must have the same sizes.
282Fraction dotProduct(ArrayRef<Fraction> a, ArrayRef<Fraction> b);
283
284/// Find the product of two polynomials, each given by an array of
285/// coefficients.
286std::vector<Fraction> multiplyPolynomials(ArrayRef<Fraction> a,
287 ArrayRef<Fraction> b);
288
289bool isRangeZero(ArrayRef<Fraction> arr);
290
291} // namespace presburger
292} // namespace mlir
293
294#endif // MLIR_ANALYSIS_PRESBURGER_UTILS_H
295

source code of mlir/include/mlir/Analysis/Presburger/Utils.h