| 1 | //===- Barvinok.h - Barvinok's Algorithm ------------------------*- 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 | // Implementation of Barvinok's algorithm and related utility functions. |
| 10 | // Currently a work in progress. |
| 11 | // These include functions to manipulate cones (define a cone object, get its |
| 12 | // dual, and find its index). |
| 13 | // |
| 14 | // The implementation is based on: |
| 15 | // 1. Barvinok, Alexander, and James E. Pommersheim. "An algorithmic theory of |
| 16 | // lattice points in polyhedra." New perspectives in algebraic combinatorics |
| 17 | // 38 (1999): 91-147. |
| 18 | // 2. Verdoolaege, Sven, et al. "Counting integer points in parametric |
| 19 | // polytopes using Barvinok's rational functions." Algorithmica 48 (2007): |
| 20 | // 37-66. |
| 21 | // |
| 22 | //===----------------------------------------------------------------------===// |
| 23 | |
| 24 | #ifndef MLIR_ANALYSIS_PRESBURGER_BARVINOK_H |
| 25 | #define MLIR_ANALYSIS_PRESBURGER_BARVINOK_H |
| 26 | |
| 27 | #include "mlir/Analysis/Presburger/GeneratingFunction.h" |
| 28 | #include "mlir/Analysis/Presburger/IntegerRelation.h" |
| 29 | #include "mlir/Analysis/Presburger/Matrix.h" |
| 30 | #include "mlir/Analysis/Presburger/PresburgerRelation.h" |
| 31 | #include "mlir/Analysis/Presburger/QuasiPolynomial.h" |
| 32 | #include <optional> |
| 33 | |
| 34 | namespace mlir { |
| 35 | namespace presburger { |
| 36 | namespace detail { |
| 37 | |
| 38 | /// A polyhedron in H-representation is a set of inequalities |
| 39 | /// in d variables with integer coefficients. |
| 40 | using PolyhedronH = IntegerRelation; |
| 41 | |
| 42 | /// A polyhedron in V-representation is a set of rays and points, i.e., |
| 43 | /// vectors, stored as rows of a matrix. |
| 44 | using PolyhedronV = IntMatrix; |
| 45 | |
| 46 | /// A cone in either representation is a special case of |
| 47 | /// a polyhedron in that representation. |
| 48 | using ConeH = PolyhedronH; |
| 49 | using ConeV = PolyhedronV; |
| 50 | |
| 51 | inline PolyhedronH defineHRep(int numVars, int numSymbols = 0) { |
| 52 | // We don't distinguish between domain and range variables, so |
| 53 | // we set the number of domain variables as 0 and the number of |
| 54 | // range variables as the number of actual variables. |
| 55 | // |
| 56 | // numSymbols is the number of parameters. |
| 57 | // |
| 58 | // There are no local (existentially quantified) variables. |
| 59 | // |
| 60 | // The number of symbols is the number of parameters. By default, we consider |
| 61 | // nonparametric polyhedra. |
| 62 | // |
| 63 | // Once the cone is defined, we use `addInequality()` to set inequalities. |
| 64 | return PolyhedronH(PresburgerSpace::getSetSpace(/*numDims=*/numDims: numVars, |
| 65 | /*numSymbols=*/numSymbols, |
| 66 | /*numLocals=*/numLocals: 0)); |
| 67 | } |
| 68 | |
| 69 | /// Get the index of a cone, i.e., the volume of the parallelepiped |
| 70 | /// spanned by its generators, which is equal to the number of integer |
| 71 | /// points in its fundamental parallelepiped. |
| 72 | /// If the index is 1, the cone is unimodular. |
| 73 | /// Barvinok, A., and J. E. Pommersheim. "An algorithmic theory of lattice |
| 74 | /// points in polyhedra." p. 107 If it has more rays than the dimension, return |
| 75 | /// 0. |
| 76 | DynamicAPInt getIndex(const ConeV &cone); |
| 77 | |
| 78 | /// Given a cone in H-representation, return its dual. The dual cone is in |
| 79 | /// V-representation. |
| 80 | /// This assumes that the input is pointed at the origin; it assert-fails |
| 81 | /// otherwise. |
| 82 | ConeV getDual(ConeH cone); |
| 83 | |
| 84 | /// Given a cone in V-representation, return its dual. The dual cone is in |
| 85 | /// H-representation. |
| 86 | /// The returned cone is pointed at the origin. |
| 87 | ConeH getDual(ConeV cone); |
| 88 | |
| 89 | /// Compute the generating function for a unimodular cone. |
| 90 | /// The input cone must be unimodular; it assert-fails otherwise. |
| 91 | GeneratingFunction computeUnimodularConeGeneratingFunction(ParamPoint vertex, |
| 92 | int sign, |
| 93 | const ConeH &cone); |
| 94 | |
| 95 | /// Find the solution of a set of equations that express affine constraints |
| 96 | /// between a set of variables and a set of parameters. The solution expresses |
| 97 | /// each variable as an affine function of the parameters. |
| 98 | /// |
| 99 | /// If there is no solution, return null. |
| 100 | std::optional<ParamPoint> solveParametricEquations(FracMatrix equations); |
| 101 | |
| 102 | /// Given a list of possibly intersecting regions (PresburgerSet) and the |
| 103 | /// generating functions active in each region, produce a pairwise disjoint |
| 104 | /// list of regions (chambers) and identify the generating function of the |
| 105 | /// polytope in each chamber. |
| 106 | /// |
| 107 | /// "Disjoint" here means that the intersection of two chambers is no full- |
| 108 | /// dimensional. |
| 109 | /// |
| 110 | /// The returned list partitions the universe into parts depending on which |
| 111 | /// subset of GFs is active there, and gives the sum of active GFs for each |
| 112 | /// part. |
| 113 | std::vector<std::pair<PresburgerSet, GeneratingFunction>> |
| 114 | computeChamberDecomposition( |
| 115 | unsigned numSymbols, ArrayRef<std::pair<PresburgerSet, GeneratingFunction>> |
| 116 | regionsAndGeneratingFunctions); |
| 117 | |
| 118 | /// Compute the generating function corresponding to a polytope. |
| 119 | /// |
| 120 | /// All tangent cones of the polytope must be unimodular. |
| 121 | std::vector<std::pair<PresburgerSet, GeneratingFunction>> |
| 122 | computePolytopeGeneratingFunction(const PolyhedronH &poly); |
| 123 | |
| 124 | /// Find a vector that is not orthogonal to any of the given vectors, |
| 125 | /// i.e., has nonzero dot product with those of the given vectors |
| 126 | /// that are not null. |
| 127 | /// If any of the vectors is null, it is ignored. |
| 128 | Point getNonOrthogonalVector(ArrayRef<Point> vectors); |
| 129 | |
| 130 | /// Find the coefficient of a given power of s in a rational function |
| 131 | /// given by P(s)/Q(s), where |
| 132 | /// P is a polynomial, in which the coefficients are QuasiPolynomials |
| 133 | /// over d parameters (distinct from s), and |
| 134 | /// and Q is a polynomial with Fraction coefficients. |
| 135 | QuasiPolynomial getCoefficientInRationalFunction(unsigned power, |
| 136 | ArrayRef<QuasiPolynomial> num, |
| 137 | ArrayRef<Fraction> den); |
| 138 | |
| 139 | /// Find the number of terms in a generating function, as |
| 140 | /// a quasipolynomial in the parameter space of the input function. |
| 141 | /// The generating function must be such that for all values of the |
| 142 | /// parameters, the number of terms is finite. |
| 143 | QuasiPolynomial computeNumTerms(const GeneratingFunction &gf); |
| 144 | |
| 145 | } // namespace detail |
| 146 | } // namespace presburger |
| 147 | } // namespace mlir |
| 148 | |
| 149 | #endif // MLIR_ANALYSIS_PRESBURGER_BARVINOK_H |
| 150 | |