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();
+}