1 //===- QuasiPolynomial.h - QuasiPolynomial 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 // Definition of the QuasiPolynomial class for Barvinok's algorithm, 10 // which represents a single-valued function on a set of parameters. 11 // It is an expression of the form 12 // f(x) = \sum_i c_i * \prod_j ⌊g_{ij}(x)⌋ 13 // where c_i \in Q and 14 // g_{ij} : Q^d -> Q are affine functionals over d parameters. 15 // 16 //===----------------------------------------------------------------------===// 17 18 #ifndef MLIR_ANALYSIS_PRESBURGER_QUASIPOLYNOMIAL_H 19 #define MLIR_ANALYSIS_PRESBURGER_QUASIPOLYNOMIAL_H 20 21 #include "mlir/Analysis/Presburger/Fraction.h" 22 #include "mlir/Analysis/Presburger/PresburgerSpace.h" 23 24 namespace mlir { 25 namespace presburger { 26 27 // A class to describe quasi-polynomials. 28 // A quasipolynomial consists of a set of terms. 29 // The ith term is a constant `coefficients[i]`, multiplied 30 // by the product of a set of affine functions on n parameters. 31 // Represents functions f : Q^n -> Q of the form 32 // 33 // f(x) = \sum_i c_i * \prod_j ⌊g_{ij}(x)⌋ 34 // 35 // where c_i \in Q and 36 // g_{ij} : Q^n -> Q are affine functionals. 37 class QuasiPolynomial : public PresburgerSpace { 38 public: 39 QuasiPolynomial(unsigned numVars, ArrayRef<Fraction> coeffs = {}, 40 ArrayRef<std::vector<SmallVector<Fraction>>> aff = {}); 41 42 QuasiPolynomial(unsigned numVars, const Fraction &constant); 43 44 // Find the number of inputs (numDomain) to the polynomial. 45 // numSymbols is set to zero. 46 unsigned getNumInputs() const { 47 return getNumDomainVars() + getNumSymbolVars(); 48 } 49 50 const SmallVector<Fraction> &getCoefficients() const { return coefficients; } 51 52 const std::vector<std::vector<SmallVector<Fraction>>> &getAffine() const { 53 return affine; 54 } 55 56 // Arithmetic operations. 57 QuasiPolynomial operator+(const QuasiPolynomial &x) const; 58 QuasiPolynomial operator-(const QuasiPolynomial &x) const; 59 QuasiPolynomial operator*(const QuasiPolynomial &x) const; 60 QuasiPolynomial operator/(const Fraction &x) const; 61 62 // Removes terms which evaluate to zero from the expression 63 // and folds affine functions which are constant into the 64 // constant coefficients. 65 QuasiPolynomial simplify(); 66 67 // Group together like terms in the expression. 68 QuasiPolynomial collectTerms(); 69 70 Fraction getConstantTerm(); 71 72 private: 73 SmallVector<Fraction> coefficients; 74 std::vector<std::vector<SmallVector<Fraction>>> affine; 75 }; 76 77 } // namespace presburger 78 } // namespace mlir 79 80 #endif // MLIR_ANALYSIS_PRESBURGER_QUASIPOLYNOMIAL_H 81