[MLIR][Presburger][NFC] Cleanup PresburgerSet

[Groverkss]

Summary

This patch cleans up the interface to PresburgerSet. At a high level it does
the following changes:

• Move member functions around to have constructors at top and print/dump at end.
• Move a private function to be a static function instead.
• Change member functions of type "getAllIntegerPolyhedron" to "getAllPolys" instead.
• Improve documentation for PresburgerSet.

[bondhugula]

mlir/include/mlir/Analysis/Presburger/PresburgerSet.h

120

Avoid using polys as a plural term. You can spell it out.

mlir/lib/Analysis/Presburger/PresburgerSet.cpp

647

Can we emit a better name here?

[Groverkss]

• Address comments

[arjunp]

mlir/include/mlir/Analysis/Presburger/PresburgerSet.h

30

(another instance of "polys")

[Groverkss]

• Address Arjun's comment

mlir/include/mlir/Analysis/Presburger/PresburgerSet.h

 #ifndef MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H
 #define MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H
 
 #include "mlir/Analysis/Presburger/IntegerRelation.h"
 
 namespace mlir {
 namespace presburger {
 
-/// This class can represent a union of IntegerPolyhedrons, with support for
-/// union, intersection, subtraction and complement operations, as well as
-/// sampling.
+/// A PresburgerSet represents a union of IntegerPolyhedrons that live in the
+/// same PresburgerSpace with support for union, intersection, subtraction, and
+/// complement operations, as well as sampling.
 ///
-/// The IntegerPolyhedrons (Polys) are stored in a vector, and the set
-/// represents the union of these Polys. An empty list corresponds to the empty
-/// set.
+/// The IntegerPolyhedrons (polyhedrons) are stored in a vector, and the set
+/// represents the union of these polyhedrons. An empty list corresponds to the
+/// empty set.
 ///
-/// Note that there are no invariants guaranteed on the list of Poly other than
-/// that they are all in the same space, i.e., they all have the same number of
-/// dimensions and symbols. For example, the Polys may overlap each other.
+/// Note that there are no invariants guaranteed on the list of polyhedrons
+/// other than that they are all in the same PresburgerSpace, i.e., they all
+/// have the same number of dimensions and symbols. For example, the polyhedrons
+/// may overlap each other.
 class PresburgerSet : public PresburgerSpace {
 public:
+  /// Return a universe set of the specified type that contains all points.
+  static PresburgerSet getUniverse(unsigned numDims = 0,
+                                   unsigned numSymbols = 0);
+  /// Return an empty set of the specified type that contains no points.
+  static PresburgerSet getEmptySet(unsigned numDims = 0,
+                                   unsigned numSymbols = 0);
+
   explicit PresburgerSet(const IntegerPolyhedron &poly);
 
   /// Return the number of Polys in the union.
   unsigned getNumPolys() const;
 
   /// Return a reference to the list of IntegerPolyhedrons.
-  ArrayRef<IntegerPolyhedron> getAllIntegerPolyhedron() const;
+  ArrayRef<IntegerPolyhedron> getAllPolys() const;
 
   /// Return the IntegerPolyhedron at the specified index.
-  const IntegerPolyhedron &getIntegerPolyhedron(unsigned index) const;
+  const IntegerPolyhedron &getPoly(unsigned index) const;
 
   /// Mutate this set, turning it into the union of this set and the given
   /// IntegerPolyhedron.
-  void unionPolyInPlace(const IntegerPolyhedron &poly);
+  void unionInPlace(const IntegerPolyhedron &poly);
 
   /// Mutate this set, turning it into the union of this set and the given set.
-  void unionSetInPlace(const PresburgerSet &set);
+  void unionInPlace(const PresburgerSet &set);
 
   /// Return the union of this set and the given set.
   PresburgerSet unionSet(const PresburgerSet &set) const;
 
   /// Return the intersection of this set and the given set.
   PresburgerSet intersect(const PresburgerSet &set) const;
 
   /// Return true if the set contains the given point, and false otherwise.
   bool containsPoint(ArrayRef<int64_t> point) const;
 
-  /// Print the set's internal state.
-  void print(raw_ostream &os) const;
-  void dump() const;
-
   /// Return the complement of this set. All local variables in the set must
   /// correspond to floor divisions.
   PresburgerSet complement() const;
 
   /// Return the set difference of this set and the given set, i.e.,
   /// return `this \ set`. All local variables in `set` must correspond
   /// to floor divisions, but local variables in `this` need not correspond to
   /// divisions.
   PresburgerSet subtract(const PresburgerSet &set) const;
 
   /// Return true if this set is a subset of the given set, and false otherwise.
   bool isSubsetOf(const PresburgerSet &set) const;
 
   /// Return true if this set is equal to the given set, and false otherwise.
   /// All local variables in both sets must correspond to floor divisions.
   bool isEqual(const PresburgerSet &set) const;
 
-  /// Return a universe set of the specified type that contains all points.
-  static PresburgerSet getUniverse(unsigned numDims = 0,
-                                   unsigned numSymbols = 0);
-  /// Return an empty set of the specified type that contains no points.
-  static PresburgerSet getEmptySet(unsigned numDims = 0,
-                                   unsigned numSymbols = 0);
-
   /// Return true if all the sets in the union are known to be integer empty
   /// false otherwise.
   bool isIntegerEmpty() const;
 
   /// Find an integer sample from the given set. This should not be called if
-  /// any of the Polys in the union are unbounded.
+  /// any of the polyhedrons in the union are unbounded.
   bool findIntegerSample(SmallVectorImpl<int64_t> &sample);
 
   /// Compute an overapproximation of the number of integer points in the
   /// polyhedron. Symbol ids are currently not supported. If the computed
   /// overapproximation is infinite, an empty optional is returned.
   ///
   /// This currently just sums up the overapproximations of the volumes of the
   /// disjuncts, so the approximation might be far from the true volume in the
   /// case when there is a lot of overlap between disjuncts.
   Optional<uint64_t> computeVolume() const;
 
   /// Simplifies the representation of a PresburgerSet.
   ///
-  /// In particular, removes all Polys which are subsets of other Polys in the
-  /// union.
+  /// In particular, removes all polyhedrons which are subsets of other
+  /// polyhedrons in the union.
   PresburgerSet coalesce() const;
 
+  /// Print the set's internal state.
+  void print(raw_ostream &os) const;
+  void dump() const;
+
 private:
-  /// Construct an empty PresburgerSet.
+  /// Construct an empty PresburgerSet with the specified number of dimension
+  /// and symbols.
   PresburgerSet(unsigned numDims = 0, unsigned numSymbols = 0)
       : PresburgerSpace(numDims, numSymbols) {}
 
-  /// Return the set difference poly \ set.
-  static PresburgerSet getSetDifference(IntegerPolyhedron poly,
-                                        const PresburgerSet &set);
-
-  /// The list of integerPolyhedrons that this set is the union of.
+  /// The list of polyhedrons that this set is the union of.
   SmallVector<IntegerPolyhedron, 2> integerPolyhedrons;
 };
 
 } // namespace presburger
 } // namespace mlir
 
 #endif // MLIR_ANALYSIS_PRESBURGER_PRESBURGERSET_H

mlir/lib/Analysis/Presburger/PWMAFunction.cpp

for (unsigned i = 0, e = vecA.size(); i < e; ++i)
     result.push_back(vecA[i] - vecB[i]);
   return result;
 }
 
 PresburgerSet PWMAFunction::getDomain() const {
   PresburgerSet domain =
       PresburgerSet::getEmptySet(getNumDimIds(), getNumSymbolIds());
   for (const MultiAffineFunction &piece : pieces)
-    domain.unionPolyInPlace(piece.getDomain());
+    domain.unionInPlace(piece.getDomain());
   return domain;
 }
 
 Optional<SmallVector<int64_t, 8>>
 MultiAffineFunction::valueAt(ArrayRef<int64_t> point) const {
   assert(getNumLocalIds() == 0 && "Local ids are not yet supported!");
   assert(point.size() == getNumIds() && "Point has incorrect dimensionality!");
 

mlir/lib/Analysis/Presburger/PresburgerSet.cpp

 #include "llvm/ADT/ScopeExit.h"
 #include "llvm/ADT/SmallBitVector.h"
 
 using namespace mlir;
 using namespace presburger;
 
 PresburgerSet::PresburgerSet(const IntegerPolyhedron &poly)
     : PresburgerSpace(poly) {
-  unionPolyInPlace(poly);
+  unionInPlace(poly);
 }
 
 unsigned PresburgerSet::getNumPolys() const {
   return integerPolyhedrons.size();
 }
 
-ArrayRef<IntegerPolyhedron> PresburgerSet::getAllIntegerPolyhedron() const {
+ArrayRef<IntegerPolyhedron> PresburgerSet::getAllPolys() const {
   return integerPolyhedrons;
 }
 
-const IntegerPolyhedron &
-PresburgerSet::getIntegerPolyhedron(unsigned index) const {
+const IntegerPolyhedron &PresburgerSet::getPoly(unsigned index) const {
   assert(index < integerPolyhedrons.size() && "index out of bounds!");
   return integerPolyhedrons[index];
 }
 
 /// Mutate this set, turning it into the union of this set and the given
 /// IntegerPolyhedron.
-void PresburgerSet::unionPolyInPlace(const IntegerPolyhedron &poly) {
+void PresburgerSet::unionInPlace(const IntegerPolyhedron &poly) {
   assert(PresburgerSpace::isEqual(poly) && "Spaces should match");
   integerPolyhedrons.push_back(poly);
 }
 
 /// Mutate this set, turning it into the union of this set and the given set.
 ///
-/// This is accomplished by simply adding all the Poly of the given set to this
-/// set.
-void PresburgerSet::unionSetInPlace(const PresburgerSet &set) {
+/// This is accomplished by simply adding all the polyhedrons of the given set
+/// to this set.
+void PresburgerSet::unionInPlace(const PresburgerSet &set) {
   assert(PresburgerSpace::isEqual(set) && "Spaces should match");
   for (const IntegerPolyhedron &poly : set.integerPolyhedrons)
-    unionPolyInPlace(poly);
+    unionInPlace(poly);
 }
 
 /// Return the union of this set and the given set.
 PresburgerSet PresburgerSet::unionSet(const PresburgerSet &set) const {
   assert(PresburgerSpace::isEqual(set) && "Spaces should match");
   PresburgerSet result = *this;
-  result.unionSetInPlace(set);
+  result.unionInPlace(set);
   return result;
 }
 
 /// A point is contained in the union iff any of the parts contain the point.
 bool PresburgerSet::containsPoint(ArrayRef<int64_t> point) const {
   return llvm::any_of(integerPolyhedrons, [&](const IntegerPolyhedron &poly) {
     return (poly.containsPoint(point));
   });
 }
 
 PresburgerSet PresburgerSet::getUniverse(unsigned numDims,
                                          unsigned numSymbols) {
   PresburgerSet result(numDims, numSymbols);
-  result.unionPolyInPlace(IntegerPolyhedron::getUniverse(numDims, numSymbols));
+  result.unionInPlace(IntegerPolyhedron::getUniverse(numDims, numSymbols));
   return result;
 }
 
 PresburgerSet PresburgerSet::getEmptySet(unsigned numDims,
                                          unsigned numSymbols) {
   return PresburgerSet(numDims, numSymbols);
 }
 
PresburgerSet PresburgerSet::intersect(const PresburgerSet &set) const {
 
   PresburgerSet result(getNumDimIds(), getNumSymbolIds());
   for (const IntegerPolyhedron &csA : integerPolyhedrons) {
     for (const IntegerPolyhedron &csB : set.integerPolyhedrons) {
       IntegerPolyhedron csACopy = csA, csBCopy = csB;
       csACopy.mergeLocalIds(csBCopy);
       csACopy.append(csBCopy);
       if (!csACopy.isEmpty())
-        result.unionPolyInPlace(csACopy);
+        result.unionInPlace(csACopy);
     }
   }
   return result;
 }
 
 /// Return `coeffs` with all the elements negated.
 static SmallVector<int64_t, 8> getNegatedCoeffs(ArrayRef<int64_t> coeffs) {
   SmallVector<int64_t, 8> negatedCoeffs;

 /// divisions present in both b and s_i. Therefore, we need to add the local
 /// division variables of both b and s_i to each part in the result. This means
 /// adding the local variables of both b and s_i, as well as the corresponding
 /// division inequalities to each part. Since the division inequalities are
 /// added to each part, we can skip the parts where the complement of any
 /// division inequality is added, as these parts will become empty anyway.
 ///
 /// As a heuristic, we try adding all the constraints and check if simplex
-/// says that the intersection is empty. If it is, then subtracting this Poly is
-/// a no-op and we just skip it. Also, in the process we find out that some
-/// constraints are redundant. These redundant constraints are ignored.
+/// says that the intersection is empty. If it is, then subtracting this
+/// polyhedrons is a no-op and we just skip it. Also, in the process we find out
+/// that some constraints are redundant. These redundant constraints are
+/// ignored.
 ///
 /// b and simplex are callee saved, i.e., their values on return are
 /// semantically equivalent to their values when the function is called.
 static void subtractRecursively(IntegerPolyhedron &b, Simplex &simplex,
                                 const PresburgerSet &s, unsigned i,
                                 PresburgerSet &result) {
   if (i == s.getNumPolys()) {
-    result.unionPolyInPlace(b);
+    result.unionInPlace(b);
     return;
   }
-  IntegerPolyhedron sI = s.getIntegerPolyhedron(i);
+  IntegerPolyhedron sI = s.getPoly(i);
 
   // Below, we append some additional constraints and ids to b. We want to
   // rollback b to its initial state before returning, which we will do by
   // removing all constraints beyond the original number of inequalities
   // and equalities, so we store these counts first.
   const unsigned bInitNumIneqs = b.getNumInequalities();
   const unsigned bInitNumEqs = b.getNumEqualities();
   const unsigned bInitNumLocals = b.getNumLocalIds();
if (!isMarkedRedundant[offset + 2 * j])
       processInequality(coeffs);
     if (!isMarkedRedundant[offset + 2 * j + 1])
       processInequality(getNegatedCoeffs(coeffs));
   }
 }
 
 /// Return the set difference poly \ set.
 ///
-/// The Poly here is modified in subtractRecursively, so it cannot be a const
-/// reference even though it is restored to its original state before returning
-/// from that function.
-PresburgerSet PresburgerSet::getSetDifference(IntegerPolyhedron poly,
-                                              const PresburgerSet &set) {
+/// The polyhedron here is modified in subtractRecursively, so it cannot be a
+/// const reference even though it is restored to its original state before
+/// returning from that function.
+static PresburgerSet getSetDifference(IntegerPolyhedron poly,
   assert(poly.PresburgerSpace::isEqual(set) && "Spaces should match");
   if (poly.isEmptyByGCDTest())
     return PresburgerSet::getEmptySet(poly.getNumDimIds(),
                                       poly.getNumSymbolIds());
 
-  PresburgerSet result(poly.getNumDimIds(), poly.getNumSymbolIds());
+  PresburgerSet result =
+      PresburgerSet::getEmptySet(poly.getNumDimIds(), poly.getNumSymbolIds());
   Simplex simplex(poly);
   subtractRecursively(poly, simplex, set, 0, result);
   return result;
 }
 
 /// Return the complement of this set.
 PresburgerSet PresburgerSet::complement() const {
   return getSetDifference(
       IntegerPolyhedron::getUniverse(getNumDimIds(), getNumSymbolIds()), *this);
 }
 
 /// Return the result of subtract the given set from this set, i.e.,
 /// return `this \ set`.
 PresburgerSet PresburgerSet::subtract(const PresburgerSet &set) const {
   assert(PresburgerSpace::isEqual(set) && "Spaces should match");
   PresburgerSet result(getNumDimIds(), getNumSymbolIds());
   // We compute (U_i t_i) \ (U_i set_i) as U_i (t_i \ V_i set_i).
   for (const IntegerPolyhedron &poly : integerPolyhedrons)
-    result.unionSetInPlace(getSetDifference(poly, set));
+    result.unionInPlace(getSetDifference(poly, set));
   return result;
 }
 
 /// T is a subset of S iff T \ S is empty, since if T \ S contains a
 /// point then this is a point that is contained in T but not S, and
 /// if T contains a point that is not in S, this also lies in T \ S.
 bool PresburgerSet::isSubsetOf(const PresburgerSet &set) const {
   return this->subtract(set).isIntegerEmpty();
for (unsigned i = 0; i < polyhedrons.size();) {
     // Only if the inner loop was not broken, i is incremented. This is
     // required as otherwise, if a coalescing occurs, the IntegerPolyhedron
     // now at position i is not compared.
     if (!broken)
       ++i;
   }
 
   for (unsigned i = 0, e = polyhedrons.size(); i < e; ++i)
-    newSet.unionPolyInPlace(polyhedrons[i]);
+    newSet.unionInPlace(polyhedrons[i]);
 
   return newSet;
 }
 
 void PresburgerSet::print(raw_ostream &os) const {
-  os << getNumPolys() << " IntegerPolyhedron:\n";
+  os << "Number of Polyhedrons: " << getNumPolys() << "\n";
   for (const IntegerPolyhedron &poly : integerPolyhedrons) {
     poly.print(os);
     os << '\n';
   }
 }
 
 void PresburgerSet::dump() const { print(llvm::errs()); }

mlir/unittests/Analysis/Presburger/PresburgerSetTest.cpp

 /// Parse a list of StringRefs to IntegerPolyhedron and combine them into a
 /// PresburgerSet be using the union operation. It is expected that the strings
 /// are all valid IntegerSet representation and that all of them have the same
 /// number of dimensions as is specified by the numDims argument.
 static PresburgerSet
 parsePresburgerSetFromPolyStrings(unsigned numDims, ArrayRef<StringRef> strs) {
   PresburgerSet set = PresburgerSet::getEmptySet(numDims);
   for (StringRef str : strs)
-    set.unionPolyInPlace(parsePoly(str));
+    set.unionInPlace(parsePoly(str));
   return set;
 }
 
 /// Compute the union of s and t, and check that each of the given points
 /// belongs to the union iff it belongs to at least one of s and t.
 static void testUnionAtPoints(const PresburgerSet &s, const PresburgerSet &t,
                               ArrayRef<SmallVector<int64_t, 4>> points) {
   PresburgerSet unionSet = s.unionSet(t);

 /// Construct a PresburgerSet having `numDims` dimensions and no symbols from
 /// the given list of IntegerPolyhedron. Each Poly in `polys` should also have
 /// `numDims` dimensions and no symbols, although it can have any number of
 /// local ids.
 static PresburgerSet makeSetFromPoly(unsigned numDims,
                                      ArrayRef<IntegerPolyhedron> polys) {
   PresburgerSet set = PresburgerSet::getEmptySet(numDims);
   for (const IntegerPolyhedron &poly : polys)
-    set.unionPolyInPlace(poly);
+    set.unionInPlace(poly);
   return set;
 }
 
 TEST(SetTest, containsPoint) {
   PresburgerSet setA = parsePresburgerSetFromPolyStrings(
       1,
       {"(x) : (x - 2 >= 0, -x + 8 >= 0)", "(x) : (x - 10 >= 0, -x + 20 >= 0)"});
   for (unsigned x = 0; x <= 21; ++x) {