MLIR  17.0.0git
Utils.h
Go to the documentation of this file.
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 
17 #include "mlir/Support/LLVM.h"
18 #include "llvm/ADT/STLExtras.h"
19 #include "llvm/ADT/SmallBitVector.h"
20 
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.
35 template <typename T>
36 class MaybeOptimum {
37 public:
38 private:
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  }
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.
100  explicit operator bool() const { return kind != ReprKind::None; }
101  union {
102  unsigned equalityIdx;
103  struct {
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.
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(denoms, 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(i); }
141  ArrayRef<MPInt> getDividend(unsigned i) const { return dividends.getRow(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.
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(i, dividend);
156  denoms[i] = divisor;
157  }
158 
159  void insertDiv(unsigned pos, ArrayRef<MPInt> dividend, const MPInt &divisor);
160  void insertDiv(unsigned pos, unsigned num = 1);
161 
162  /// Removes duplicate divisions. On every possible duplicate division found,
163  /// `merge(i, j)`, where `i`, `j` are current index of the duplicate
164  /// divisions, is called and division at index `j` is merged into division at
165  /// index `i`. If `merge(i, j)` returns `true`, the divisions are merged i.e.
166  /// `j^th` division gets eliminated and it's each instance is replaced by
167  /// `i^th` division. If it returns `false`, the divisions are not merged.
168  /// `merge` can also do side effects, For example it can merge the local
169  /// variables in IntegerRelation.
170  void
171  removeDuplicateDivs(llvm::function_ref<bool(unsigned i, unsigned j)> merge);
172 
173  void print(raw_ostream &os) const;
174  void dump() const;
175 
176 private:
177  /// Each row of the Matrix represents a single division dividend. The
178  /// `i^th` row represents the dividend of the variable at `divOffset + i`
179  /// in the constraint system (and the `i^th` local variable).
180  Matrix dividends;
181 
182  /// Denominators of each division. If a denominator of a division is `0`, the
183  /// division variable is considered to not have a division representation.
184  /// Otherwise, the denominator is positive.
185  SmallVector<MPInt, 4> denoms;
186 };
187 
188 /// If `q` is defined to be equal to `expr floordiv d`, this equivalent to
189 /// saying that `q` is an integer and `q` is subject to the inequalities
190 /// `0 <= expr - d*q <= c - 1` (quotient remainder theorem).
191 ///
192 /// Rearranging, we get the bounds on `q`: d*q <= expr <= d*q + d - 1.
193 ///
194 /// `getDivUpperBound` returns `d*q <= expr`, and
195 /// `getDivLowerBound` returns `expr <= d*q + d - 1`.
196 ///
197 /// The parameter `dividend` corresponds to `expr` above, `divisor` to `d`, and
198 /// `localVarIdx` to the position of `q` in the coefficient list.
199 ///
200 /// The coefficient of `q` in `dividend` must be zero, as it is not allowed for
201 /// local variable to be a floor division of an expression involving itself.
202 /// The divisor must be positive.
204  const MPInt &divisor,
205  unsigned localVarIdx);
207  const MPInt &divisor,
208  unsigned localVarIdx);
209 
210 llvm::SmallBitVector getSubrangeBitVector(unsigned len, unsigned setOffset,
211  unsigned numSet);
212 
213 /// Check if the pos^th variable can be expressed as a floordiv of an affine
214 /// function of other variables (where the divisor is a positive constant).
215 /// `foundRepr` contains a boolean for each variable indicating if the
216 /// explicit representation for that variable has already been computed.
217 /// Return the given array as an array of MPInts.
219 /// Return the given array as an array of int64_t.
221 
222 /// Returns the `MaybeLocalRepr` struct which contains the indices of the
223 /// constraints that can be expressed as a floordiv of an affine function. If
224 /// the representation could be computed, `dividend` and `divisor` are set,
225 /// in which case, denominator will be positive. If the representation could
226 /// not be computed, the kind attribute in `MaybeLocalRepr` is set to None.
227 MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst,
228  ArrayRef<bool> foundRepr, unsigned pos,
229  MutableArrayRef<MPInt> dividend,
230  MPInt &divisor);
231 
232 /// The following overload using int64_t is required for a callsite in
233 /// AffineStructures.h.
234 MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst,
235  ArrayRef<bool> foundRepr, unsigned pos,
236  SmallVector<int64_t, 8> &dividend,
237  unsigned &divisor);
238 
239 /// Given two relations, A and B, add additional local vars to the sets such
240 /// that both have the union of the local vars in each set, without changing
241 /// the set of points that lie in A and B.
242 ///
243 /// While taking union, if a local var in any set has a division representation
244 /// which is a duplicate of division representation, of another local var in any
245 /// set, it is not added to the final union of local vars and is instead merged.
246 ///
247 /// On every possible merge, `merge(i, j)` is called. `i`, `j` are position
248 /// of local variables in both sets which are being merged. If `merge(i, j)`
249 /// returns true, the divisions are merged, otherwise the divisions are not
250 /// merged.
251 void mergeLocalVars(IntegerRelation &relA, IntegerRelation &relB,
252  llvm::function_ref<bool(unsigned i, unsigned j)> merge);
253 
254 /// Compute the gcd of the range.
255 MPInt gcdRange(ArrayRef<MPInt> range);
256 
257 /// Divide the range by its gcd and return the gcd.
259 
260 /// Normalize the given (numerator, denominator) pair by dividing out the
261 /// common factors between them. The numerator here is an affine expression
262 /// with integer coefficients. The denominator must be positive.
263 void normalizeDiv(MutableArrayRef<MPInt> num, MPInt &denom);
264 
265 /// Return `coeffs` with all the elements negated.
267 
268 /// Return the complement of the given inequality.
269 ///
270 /// The complement of a_1 x_1 + ... + a_n x_ + c >= 0 is
271 /// a_1 x_1 + ... + a_n x_ + c < 0, i.e., -a_1 x_1 - ... - a_n x_ - c - 1 >= 0,
272 /// since all the variables are constrained to be integers.
274 } // namespace presburger
275 } // namespace mlir
276 
277 #endif // MLIR_ANALYSIS_PRESBURGER_UTILS_H
Class storing division representation of local variables of a constraint system.
Definition: Utils.h:118
void removeDuplicateDivs(llvm::function_ref< bool(unsigned i, unsigned j)> merge)
Removes duplicate divisions.
Definition: Utils.cpp:430
MPInt & getDenom(unsigned i)
Definition: Utils.h:149
bool hasAllReprs() const
Definition: Utils.h:134
void clearRepr(unsigned i)
Definition: Utils.h:137
unsigned getNumNonDivs() const
Definition: Utils.h:127
unsigned getNumVars() const
Definition: Utils.h:125
DivisionRepr(unsigned numVars)
Definition: Utils.h:123
SmallVector< std::optional< MPInt >, 4 > divValuesAt(ArrayRef< MPInt > point) const
Definition: Utils.cpp:382
unsigned getDivOffset() const
Definition: Utils.h:129
void print(raw_ostream &os) const
Definition: Utils.cpp:492
unsigned getNumDivs() const
Definition: Utils.h:126
bool hasRepr(unsigned i) const
Definition: Utils.h:132
ArrayRef< MPInt > getDividend(unsigned i) const
Definition: Utils.h:141
DivisionRepr(unsigned numVars, unsigned numDivs)
Definition: Utils.h:120
void insertDiv(unsigned pos, ArrayRef< MPInt > dividend, const MPInt &divisor)
Definition: Utils.cpp:475
void setDiv(unsigned i, ArrayRef< MPInt > dividend, const MPInt &divisor)
Definition: Utils.h:154
MPInt getDenom(unsigned i) const
Definition: Utils.h:150
MutableArrayRef< MPInt > getDividend(unsigned i)
Definition: Utils.h:140
ArrayRef< MPInt > getDenoms() const
Definition: Utils.h:152
This class provides support for multi-precision arithmetic.
Definition: MPInt.h:87
This is a class to represent a resizable matrix.
Definition: Matrix.h:35
void setRow(unsigned row, ArrayRef< MPInt > elems)
Set the specified row to elems.
Definition: Matrix.cpp:95
unsigned getNumColumns() const
Definition: Matrix.h:78
unsigned getNumRows() const
Definition: Matrix.h:76
MutableArrayRef< MPInt > getRow(unsigned row)
Get a [Mutable]ArrayRef corresponding to the specified row.
Definition: Matrix.cpp:87
const T & getBoundedOptimum() const
Definition: Utils.h:57
bool operator==(const MaybeOptimum< T > &other) const
Definition: Utils.h:71
bool isBounded() const
Definition: Utils.h:52
MaybeOptimum(const T &optimum)
Definition: Utils.h:48
MaybeOptimum(OptimumKind kind)
Definition: Utils.h:44
OptimumKind getKind() const
Definition: Utils.h:51
bool isUnbounded() const
Definition: Utils.h:53
std::optional< T > getOptimumIfBounded() const
Definition: Utils.h:56
const T * operator->() const
Definition: Utils.h:69
auto map(const Function &f) const &-> MaybeOptimum< decltype(f(optimum))>
Definition: Utils.h:83
const T & operator*() const
Definition: Utils.h:67
ReprKind
ReprKind enum is used to set the constraint type in MaybeLocalRepr.
Definition: Utils.h:91
SmallVector< MPInt, 8 > getDivLowerBound(ArrayRef< MPInt > dividend, const MPInt &divisor, unsigned localVarIdx)
Definition: Utils.cpp:323
SmallVector< MPInt, 8 > getDivUpperBound(ArrayRef< MPInt > dividend, const MPInt &divisor, unsigned localVarIdx)
If q is defined to be equal to expr floordiv d, this equivalent to saying that q is an integer and q ...
Definition: Utils.cpp:312
void mergeLocalVars(IntegerRelation &relA, IntegerRelation &relB, llvm::function_ref< bool(unsigned i, unsigned j)> merge)
Given two relations, A and B, add additional local vars to the sets such that both have the union of ...
Definition: Utils.cpp:286
OptimumKind
This class represents the result of operations optimizing something subject to some constraints.
Definition: Utils.h:34
MPInt gcdRange(ArrayRef< MPInt > range)
Compute the gcd of the range.
Definition: Utils.cpp:337
void normalizeDiv(MutableArrayRef< MPInt > num, MPInt &denom)
Normalize the given (numerator, denominator) pair by dividing out the common factors between them.
Definition: Utils.cpp:356
MaybeLocalRepr computeSingleVarRepr(const IntegerRelation &cst, ArrayRef< bool > foundRepr, unsigned pos, MutableArrayRef< MPInt > dividend, MPInt &divisor)
Returns the MaybeLocalRepr struct which contains the indices of the constraints that can be expressed...
Definition: Utils.cpp:223
SmallVector< MPInt, 8 > getMPIntVec(ArrayRef< int64_t > range)
Check if the pos^th variable can be expressed as a floordiv of an affine function of other variables ...
Definition: Utils.cpp:503
SmallVector< MPInt, 8 > getNegatedCoeffs(ArrayRef< MPInt > coeffs)
Return coeffs with all the elements negated.
Definition: Utils.cpp:364
MPInt normalizeRange(MutableArrayRef< MPInt > range)
Divide the range by its gcd and return the gcd.
Definition: Utils.cpp:347
SmallVector< int64_t, 8 > getInt64Vec(ArrayRef< MPInt > range)
Return the given array as an array of int64_t.
Definition: Utils.cpp:509
llvm::SmallBitVector getSubrangeBitVector(unsigned len, unsigned setOffset, unsigned numSet)
Definition: Utils.cpp:278
SmallVector< MPInt, 8 > getComplementIneq(ArrayRef< MPInt > ineq)
Return the complement of the given inequality.
Definition: Utils.cpp:372
Include the generated interface declarations.
MaybeLocalRepr contains the indices of the constraints that can be expressed as a floordiv of an affi...
Definition: Utils.h:98
union mlir::presburger::MaybeLocalRepr::@2 repr
struct mlir::presburger::MaybeLocalRepr::@2::@3 inequalityPair
Eliminates variable at the specified position using Fourier-Motzkin variable elimination.