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=*/numVars, 65 /*numSymbols=*/numSymbols, 66 /*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