diff options
Diffstat (limited to 'mlir/lib/Analysis/Presburger/Barvinok.cpp')
-rw-r--r-- | mlir/lib/Analysis/Presburger/Barvinok.cpp | 65 |
1 files changed, 65 insertions, 0 deletions
diff --git a/mlir/lib/Analysis/Presburger/Barvinok.cpp b/mlir/lib/Analysis/Presburger/Barvinok.cpp new file mode 100644 index 0000000..9152b66 --- /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(); +} |