diff options
author | Abhinav271828 <71174780+Abhinav271828@users.noreply.github.com> | 2024-01-07 16:00:22 +0530 |
---|---|---|
committer | GitHub <noreply@github.com> | 2024-01-07 10:30:22 +0000 |
commit | 4c8dbb68138959477d9fccbae3669663260dfe31 (patch) | |
tree | 58895ec7531ec1f1b855421e7837b9a26aaced15 | |
parent | c82c54a1ef89ebd4903adfd977dabd34718a136e (diff) |
[MLIR][Presburger] Definitions for basic functions related to cones (#76650)
We add some basic type aliases and function definitions relating to
cones for Barvinok's algorithm.
These include functions to get the dual of a cone and find its index.
-rw-r--r-- | mlir/include/mlir/Analysis/Presburger/Barvinok.h | 84 | ||||
-rw-r--r-- | mlir/lib/Analysis/Presburger/Barvinok.cpp | 65 | ||||
-rw-r--r-- | mlir/lib/Analysis/Presburger/CMakeLists.txt | 1 | ||||
-rw-r--r-- | mlir/unittests/Analysis/Presburger/BarvinokTest.cpp | 48 | ||||
-rw-r--r-- | mlir/unittests/Analysis/Presburger/CMakeLists.txt | 1 |
5 files changed, 199 insertions, 0 deletions
diff --git a/mlir/include/mlir/Analysis/Presburger/Barvinok.h b/mlir/include/mlir/Analysis/Presburger/Barvinok.h new file mode 100644 index 000000000000..15e805860db2 --- /dev/null +++ b/mlir/include/mlir/Analysis/Presburger/Barvinok.h @@ -0,0 +1,84 @@ +//===- Barvinok.h - Barvinok's Algorithm ------------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// +// +// Implementation of Barvinok's algorithm and related utility functions. +// Currently a work in progress. +// These include functions to manipulate cones (define a cone object, get its +// dual, and find its index). +// +// The implementation is based on: +// 1. Barvinok, Alexander, and James E. Pommersheim. "An algorithmic theory of +// lattice points in polyhedra." New perspectives in algebraic combinatorics +// 38 (1999): 91-147. +// 2. Verdoolaege, Sven, et al. "Counting integer points in parametric +// polytopes using Barvinok's rational functions." Algorithmica 48 (2007): +// 37-66. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_ANALYSIS_PRESBURGER_BARVINOK_H +#define MLIR_ANALYSIS_PRESBURGER_BARVINOK_H + +#include "mlir/Analysis/Presburger/IntegerRelation.h" +#include "mlir/Analysis/Presburger/Matrix.h" +#include <optional> + +namespace mlir { +namespace presburger { +namespace detail { + +/// A polyhedron in H-representation is a set of inequalities +/// in d variables with integer coefficients. +using PolyhedronH = IntegerRelation; + +/// A polyhedron in V-representation is a set of rays and points, i.e., +/// vectors, stored as rows of a matrix. +using PolyhedronV = IntMatrix; + +/// A cone in either representation is a special case of +/// a polyhedron in that representation. +using ConeH = PolyhedronH; +using ConeV = PolyhedronV; + +inline ConeH defineHRep(int numVars) { + // We don't distinguish between domain and range variables, so + // we set the number of domain variables as 0 and the number of + // range variables as the number of actual variables. + // There are no symbols (we don't work with parametric cones) and no local + // (existentially quantified) variables. + // Once the cone is defined, we use `addInequality()` to set inequalities. + return ConeH(PresburgerSpace::getSetSpace(/*numDims=*/numVars, + /*numSymbols=*/0, + /*numLocals=*/0)); +} + +/// Get the index of a cone, i.e., the volume of the parallelepiped +/// spanned by its generators, which is equal to the number of integer +/// points in its fundamental parallelepiped. +/// If the index is 1, the cone is unimodular. +/// Barvinok, A., and J. E. Pommersheim. "An algorithmic theory of lattice +/// points in polyhedra." p. 107 If it has more rays than the dimension, return +/// 0. +MPInt getIndex(ConeV cone); + +/// Given a cone in H-representation, return its dual. The dual cone is in +/// V-representation. +/// This assumes that the input is pointed at the origin; it assert-fails +/// otherwise. +ConeV getDual(ConeH cone); + +/// Given a cone in V-representation, return its dual. The dual cone is in +/// H-representation. +/// The returned cone is pointed at the origin. +ConeH getDual(ConeV cone); + +} // namespace detail +} // namespace presburger +} // namespace mlir + +#endif // MLIR_ANALYSIS_PRESBURGER_BARVINOK_H diff --git a/mlir/lib/Analysis/Presburger/Barvinok.cpp b/mlir/lib/Analysis/Presburger/Barvinok.cpp new file mode 100644 index 000000000000..9152b66968a1 --- /dev/null +++ b/mlir/lib/Analysis/Presburger/Barvinok.cpp @@ -0,0 +1,65 @@ +//===- Barvinok.cpp - Barvinok's Algorithm ----------------------*- C++ -*-===// +// +// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. +// See https://llvm.org/LICENSE.txt for license information. +// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception +// +//===----------------------------------------------------------------------===// + +#include "mlir/Analysis/Presburger/Barvinok.h" + +using namespace mlir; +using namespace presburger; +using namespace mlir::presburger::detail; + +/// Assuming that the input cone is pointed at the origin, +/// converts it to its dual in V-representation. +/// Essentially we just remove the all-zeroes constant column. +ConeV mlir::presburger::detail::getDual(ConeH cone) { + unsigned numIneq = cone.getNumInequalities(); + unsigned numVar = cone.getNumCols() - 1; + ConeV dual(numIneq, numVar, 0, 0); + // Assuming that an inequality of the form + // a1*x1 + ... + an*xn + b ≥ 0 + // is represented as a row [a1, ..., an, b] + // and that b = 0. + + for (unsigned i = 0; i < numIneq; ++i) { + assert(cone.atIneq(i, numVar) == 0 && + "H-representation of cone is not centred at the origin!"); + for (unsigned j = 0; j < numVar; ++j) { + dual.at(i, j) = cone.atIneq(i, j); + } + } + + // Now dual is of the form [ [a1, ..., an] , ... ] + // which is the V-representation of the dual. + return dual; +} + +/// Converts a cone in V-representation to the H-representation +/// of its dual, pointed at the origin (not at the original vertex). +/// Essentially adds a column consisting only of zeroes to the end. +ConeH mlir::presburger::detail::getDual(ConeV cone) { + unsigned rows = cone.getNumRows(); + unsigned columns = cone.getNumColumns(); + ConeH dual = defineHRep(columns); + // Add a new column (for constants) at the end. + // This will be initialized to zero. + cone.insertColumn(columns); + + for (unsigned i = 0; i < rows; ++i) + dual.addInequality(cone.getRow(i)); + + // Now dual is of the form [ [a1, ..., an, 0] , ... ] + // which is the H-representation of the dual. + return dual; +} + +/// Find the index of a cone in V-representation. +MPInt mlir::presburger::detail::getIndex(ConeV cone) { + if (cone.getNumRows() > cone.getNumColumns()) + return MPInt(0); + + return cone.determinant(); +} diff --git a/mlir/lib/Analysis/Presburger/CMakeLists.txt b/mlir/lib/Analysis/Presburger/CMakeLists.txt index e77e1623dae1..83d0514c9e7d 100644 --- a/mlir/lib/Analysis/Presburger/CMakeLists.txt +++ b/mlir/lib/Analysis/Presburger/CMakeLists.txt @@ -1,4 +1,5 @@ add_mlir_library(MLIRPresburger + Barvinok.cpp IntegerRelation.cpp LinearTransform.cpp Matrix.cpp diff --git a/mlir/unittests/Analysis/Presburger/BarvinokTest.cpp b/mlir/unittests/Analysis/Presburger/BarvinokTest.cpp new file mode 100644 index 000000000000..b88baa6c6b48 --- /dev/null +++ b/mlir/unittests/Analysis/Presburger/BarvinokTest.cpp @@ -0,0 +1,48 @@ +#include "mlir/Analysis/Presburger/Barvinok.h" +#include "./Utils.h" +#include <gmock/gmock.h> +#include <gtest/gtest.h> + +using namespace mlir; +using namespace presburger; +using namespace mlir::presburger::detail; + +/// The following are 3 randomly generated vectors with 4 +/// entries each and define a cone's H-representation +/// using these numbers. We check that the dual contains +/// the same numbers. +/// We do the same in the reverse case. +TEST(BarvinokTest, getDual) { + ConeH cone1 = defineHRep(4); + cone1.addInequality({1, 2, 3, 4, 0}); + cone1.addInequality({3, 4, 2, 5, 0}); + cone1.addInequality({6, 2, 6, 1, 0}); + + ConeV dual1 = getDual(cone1); + + EXPECT_EQ_INT_MATRIX( + dual1, makeIntMatrix(3, 4, {{1, 2, 3, 4}, {3, 4, 2, 5}, {6, 2, 6, 1}})); + + ConeV cone2 = makeIntMatrix(3, 4, {{3, 6, 1, 5}, {3, 1, 7, 2}, {9, 3, 2, 7}}); + + ConeH dual2 = getDual(cone2); + + ConeH expected = defineHRep(4); + expected.addInequality({3, 6, 1, 5, 0}); + expected.addInequality({3, 1, 7, 2, 0}); + expected.addInequality({9, 3, 2, 7, 0}); + + EXPECT_TRUE(dual2.isEqual(expected)); +} + +/// We randomly generate a nxn matrix to use as a cone +/// with n inequalities in n variables and check for +/// the determinant being equal to the index. +TEST(BarvinokTest, getIndex) { + ConeV cone = makeIntMatrix(3, 3, {{4, 2, 1}, {5, 2, 7}, {4, 1, 6}}); + EXPECT_EQ(getIndex(cone), cone.determinant()); + + cone = makeIntMatrix( + 4, 4, {{4, 2, 5, 1}, {4, 1, 3, 6}, {8, 2, 5, 6}, {5, 2, 5, 7}}); + EXPECT_EQ(getIndex(cone), cone.determinant()); +} diff --git a/mlir/unittests/Analysis/Presburger/CMakeLists.txt b/mlir/unittests/Analysis/Presburger/CMakeLists.txt index 54a841726cd1..c98668f63fa5 100644 --- a/mlir/unittests/Analysis/Presburger/CMakeLists.txt +++ b/mlir/unittests/Analysis/Presburger/CMakeLists.txt @@ -1,4 +1,5 @@ add_mlir_unittest(MLIRPresburgerTests + BarvinokTest.cpp FractionTest.cpp GeneratingFunctionTest.cpp IntegerPolyhedronTest.cpp |