[MLIR][presburger] normalize divisionrepr

[gilsaia]

Summary

Added a simple normalize function to divisionrepr and added a simple unittest.
Added a normalizediv call to divisionrepr's removeDuplicateDivs function, which now eliminates divs that are consistent after gcd's normalize

[Groverkss]

Thank you for the patch! I added some comments to get started.

mlir/include/mlir/Analysis/Presburger/Utils.h

159

Please add documentation for this method.

mlir/lib/Analysis/Presburger/Utils.cpp

434

I don't think this solves this TODO. That is a separate issue. That TODO refers to cases when divisionA = divisionB + constant. I would not delete that TODO.

477

I prefer writing this loop like this:

for (unsigned i = 0, e = getNumDivs(); i < e; ++i)

That is the preferred method of writing loops when the end condition does not change throughout the loop

478

There is no need to put braces for this if condition: https://llvm.org/docs/CodingStandards.html#don-t-use-braces-on-simple-single-statement-bodies-of-if-else-loop-statements

483

You can drop the return here.

mlir/unittests/Analysis/Presburger/CMakeLists.txt

13

I would name this file UtilsTest.cpp maybe.

[gilsaia]

Add comments,change formatting and naming

[Groverkss]

mlir/include/mlir/Analysis/Presburger/Utils.h

160

I don't think you need to mention "other than 1". That just makes it confusing.

[gilsaia]

change comment

[Groverkss]

LGTM.

mlir/include/mlir/Analysis/Presburger/Utils.h

public:
 
   ArrayRef<MPInt> getDenoms() const { return denoms; }
 
   void setDiv(unsigned i, ArrayRef<MPInt> dividend, const MPInt &divisor) {
     dividends.setRow(i, dividend);
     denoms[i] = divisor;
   }
 
+  // Find the greatest common divisor (GCD) of the dividends and divisor for
+  // each valid division. Divide the dividends and divisor by the GCD to
+  // simplify the expression.
+  void normalizeDivs();
+
   void insertDiv(unsigned pos, ArrayRef<MPInt> dividend, const MPInt &divisor);
   void insertDiv(unsigned pos, unsigned num = 1);
 
   /// Removes duplicate divisions. On every possible duplicate division found,
   /// `merge(i, j)`, where `i`, `j` are current index of the duplicate
   /// divisions, is called and division at index `j` is merged into division at
   /// index `i`. If `merge(i, j)` returns `true`, the divisions are merged i.e.
   /// `j^th` division gets eliminated and it's each instance is replaced by

mlir/lib/Analysis/Presburger/Utils.cpp

DivisionRepr::divValuesAt(ArrayRef<MPInt> point) const {
 
   return divValues;
 }
 
 void DivisionRepr::removeDuplicateDivs(
     llvm::function_ref<bool(unsigned i, unsigned j)> merge) {
 
   // Find and merge duplicate divisions.
   // TODO: Add division normalization to support divisions that differ by
   // a constant.
   // TODO: Add division ordering such that a division representation for local
   // variable at position `i` only depends on local variables at position <
   // `i`. This would make sure that all divisions depending on other local
   // variables that can be merged, are merged.
+  normalizeDivs();
   for (unsigned i = 0; i < getNumDivs(); ++i) {
     // Check if a division representation exists for the `i^th` local var.
     if (denoms[i] == 0)
       continue;
     // Check if a division exists which is a duplicate of the division at `i`.
     for (unsigned j = i + 1; j < getNumDivs(); ++j) {
       // Check if a division representation exists for the `j^th` local var.
       if (denoms[j] == 0)
for (unsigned j = i + 1; j < getNumDivs(); ++j) {
       denoms.erase(denoms.begin() + j);
 
       // Since `j` can never be zero, we do not need to worry about overflows.
       --j;
     }
   }
 }
 
+void DivisionRepr::normalizeDivs() {
+  for (unsigned i = 0, e = getNumDivs(); i < e; ++i) {
+    if (getDenom(i) == 0 || getDividend(i).empty())
+      continue;
+    normalizeDiv(getDividend(i), getDenom(i));
+  }
+}
+
 void DivisionRepr::insertDiv(unsigned pos, ArrayRef<MPInt> dividend,
                              const MPInt &divisor) {
   assert(pos <= getNumDivs() && "Invalid insertion position");
   assert(dividend.size() == getNumVars() + 1 && "Incorrect dividend size");
 
   dividends.appendExtraRow(dividend);
   denoms.insert(denoms.begin() + pos, divisor);
   dividends.insertColumn(getDivOffset() + pos);

mlir/unittests/Analysis/Presburger/CMakeLists.txt

 add_mlir_unittest(MLIRPresburgerTests
   IntegerPolyhedronTest.cpp
   IntegerRelationTest.cpp
   LinearTransformTest.cpp
   MatrixTest.cpp
   MPIntTest.cpp
   Parser.h
   ParserTest.cpp
   PresburgerSetTest.cpp
   PresburgerSpaceTest.cpp
   PWMAFunctionTest.cpp
   SimplexTest.cpp
+  UtilsTest.cpp
 )
 
 target_link_libraries(MLIRPresburgerTests
   PRIVATE MLIRPresburger
   MLIRAffineAnalysis
   MLIRParser
   )

mlir/unittests/Analysis/Presburger/UtilsTest.cpp

+//===- Utils.cpp - Tests for Utils file ----------===//
+//
+// 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/Utils.h"
+
+#include <gmock/gmock.h>
+#include <gtest/gtest.h>
+
+using namespace mlir;
+using namespace presburger;
+
+static DivisionRepr parseDivisionRepr(unsigned numVars, unsigned numDivs,
+                                      ArrayRef<ArrayRef<MPInt>> dividends,
+                                      ArrayRef<MPInt> divisors) {
+  DivisionRepr repr(numVars, numDivs);
+  for (unsigned i = 0, rows = dividends.size(); i < rows; ++i)
+    repr.setDiv(i, dividends[i], divisors[i]);
+  return repr;
+}
+
+static void checkEqual(DivisionRepr &a, DivisionRepr &b) {
+  EXPECT_EQ(a.getNumVars(), b.getNumVars());
+  EXPECT_EQ(a.getNumDivs(), b.getNumDivs());
+  for (unsigned i = 0, rows = a.getNumDivs(); i < rows; ++i) {
+    EXPECT_EQ(a.hasRepr(i), b.hasRepr(i));
+    if (!a.hasRepr(i))
+      continue;
+    EXPECT_TRUE(a.getDenom(i) == b.getDenom(i));
+    EXPECT_TRUE(a.getDividend(i).equals(b.getDividend(i)));
+  }
+}
+
+TEST(UtilsTest, ParseAndCompareDivisionReprTest) {
+  auto merge = [this](unsigned i, unsigned j) -> bool { return true; };
+  DivisionRepr a = parseDivisionRepr(1, 1, {{MPInt(1), MPInt(2)}}, {MPInt(2)}),
+               b = parseDivisionRepr(1, 1, {{MPInt(1), MPInt(2)}}, {MPInt(2)}),
+               c = parseDivisionRepr(2, 2,
+                                     {{MPInt(0), MPInt(1), MPInt(2)},
+                                      {MPInt(0), MPInt(1), MPInt(2)}},
+                                     {MPInt(2), MPInt(2)});
+  c.removeDuplicateDivs(merge);
+  checkEqual(a, b);
+  checkEqual(a, c);
+}
+
+TEST(UtilsTest, DivisionReprNormalizeTest) {
+  auto merge = [this](unsigned i, unsigned j) -> bool { return true; };
+  DivisionRepr a = parseDivisionRepr(2, 1, {{MPInt(1), MPInt(2), MPInt(-1)}},
+                                     {MPInt(2)}),
+               b = parseDivisionRepr(2, 1, {{MPInt(16), MPInt(32), MPInt(-16)}},
+                                     {MPInt(32)}),
+               c = parseDivisionRepr(1, 1, {{MPInt(12), MPInt(-4)}},
+                                     {MPInt(8)}),
+               d = parseDivisionRepr(2, 2,
+                                     {{MPInt(1), MPInt(2), MPInt(-1)},
+                                      {MPInt(4), MPInt(8), MPInt(-4)}},
+                                     {MPInt(2), MPInt(8)});
+  b.removeDuplicateDivs(merge);
+  c.removeDuplicateDivs(merge);
+  d.removeDuplicateDivs(merge);
+  checkEqual(a, b);
+  checkEqual(c, d);
+}