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
34namespace mlir {
35namespace presburger {
36namespace detail {
37
38/// A polyhedron in H-representation is a set of inequalities
39/// in d variables with integer coefficients.
40using 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.
44using PolyhedronV = IntMatrix;
45
46/// A cone in either representation is a special case of
47/// a polyhedron in that representation.
48using ConeH = PolyhedronH;
49using ConeV = PolyhedronV;
50
51inline 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.
76DynamicAPInt 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.
82ConeV 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.
87ConeH getDual(ConeV cone);
88
89/// Compute the generating function for a unimodular cone.
90/// The input cone must be unimodular; it assert-fails otherwise.
91GeneratingFunction 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.
100std::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.
113std::vector<std::pair<PresburgerSet, GeneratingFunction>>
114computeChamberDecomposition(
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.
121std::vector<std::pair<PresburgerSet, GeneratingFunction>>
122computePolytopeGeneratingFunction(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.
128Point 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.
135QuasiPolynomial 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.
143QuasiPolynomial computeNumTerms(const GeneratingFunction &gf);
144
145} // namespace detail
146} // namespace presburger
147} // namespace mlir
148
149#endif // MLIR_ANALYSIS_PRESBURGER_BARVINOK_H
150