[MLIR][Presburger] Add inverse to IntegerRelation

[Groverkss]

Summary

This patch adds support for obtaining inverse of a relation.

[ftynse]

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h

508

Nit: I would rather phrase this as "Invert the relation, i.e., swap its domain and range." "Get" implies the new relation is returned.

[Groverkss]

• Update documentation for IntegerRelation::inverse

mlir/include/mlir/Analysis/Presburger/IntegerRelation.h

public:
   }
 
   /// Return a set corresponding to all points in the domain of the relation.
   IntegerPolyhedron getDomainSet() const;
 
   /// Return a set corresponding to all points in the range of the relation.
   IntegerPolyhedron getRangeSet() const;
 
+  /// Invert the relation i.e., swap it's domain and range.
+  ///
+  /// Formally, let the relation `this` be R: A -> B, then this operation
+  /// modifies R to be B -> A.
+  void inverse();
+
   void print(raw_ostream &os) const;
   void dump() const;
 
 protected:
   /// Checks all rows of equality/inequality constraints for trivial
   /// contradictions (for example: 1 == 0, 0 >= 1), which may have surfaced
   /// after elimination. Returns true if an invalid constraint is found;
   /// false otherwise.

mlir/lib/Analysis/Presburger/IntegerRelation.cpp

copyRel.convertIdKind(IdKind::Domain, 0, getNumIdKind(IdKind::Domain),
                         IdKind::Local);
 
   // We do not need to do anything to Range variables since they are already in
   // SetDim position.
 
   return IntegerPolyhedron(std::move(copyRel));
 }
 
+void IntegerRelation::inverse() {
+  unsigned numRangeIds = getNumIdKind(IdKind::Range);
+  convertIdKind(IdKind::Domain, 0, getIdKindEnd(IdKind::Domain), IdKind::Range);
+  convertIdKind(IdKind::Range, 0, numRangeIds, IdKind::Domain);
+}
+
 void IntegerRelation::printSpace(raw_ostream &os) const {
   space.print(os);
   os << getNumConstraints() << " constraints\n";
 }
 
 void IntegerRelation::print(raw_ostream &os) const {
   assert(hasConsistentState());
   printSpace(os);

mlir/unittests/Analysis/Presburger/IntegerRelationTest.cpp

TEST(IntegerRelationTest, getDomainAndRangeSet) {
 
   IntegerPolyhedron rangeSet = rel.getRangeSet();
 
   IntegerPolyhedron expectedRangeSet =
       parsePoly("(x)[N] : (x >= 0, N - x >= 0)");
 
   EXPECT_TRUE(rangeSet.isEqual(expectedRangeSet));
 }
+
+TEST(IntegerRelationTest, inverse) {
+  IntegerRelation rel =
+      parseRelationFromSet("(x, y, z)[N, M] : (z - x - y == 0, x >= 0, N - x "
+                           ">= 0, y >= 0, M - y >= 0)",
+                           2);
+
+  IntegerRelation inverseRel =
+      parseRelationFromSet("(z, x, y)[N, M]  : (x >= 0, N - x >= 0, y >= 0, M "
+                           "- y >= 0, x + y - z == 0)",
+                           1);
+
+  rel.inverse();
+
+  EXPECT_TRUE(rel.isEqual(inverseRel));
+}