[MLIR] Add clearAndCopyFrom to IntegerPolyhedron

[Groverkss]

Summary

This patch adds clearAndCopyFrom to IntegerPolyhedron. This requires moving
LLVM-style RTTI from FlatAffineConstraints to IntegerPolyhedron.

This patch is part of a series of patches to move presburger math to Presburger
directory.

[bondhugula]

mlir/include/mlir/Analysis/Presburger/IntegerPolyhedron.h

53

The comment here is misleading: all derived classes of IntegerPolyhedron?

87

Copy-pasted but missing update?

[Groverkss]

• Fix doc comments.

[arjunp]

mlir/lib/Analysis/AffineStructures.cpp

2646

Even though it currently doesn't make a difference, I think for maintainability it's better if you consider the FAC case as well.

2664–2665

Same here.

[Groverkss]

• Address Arjun's comments

[arjunp]

mlir/lib/Analysis/AffineStructures.cpp

2665–2675

You can deduplicate setting the values

[grosser]

mlir/lib/Analysis/AffineStructures.cpp

2665–2675

Also, maybe use return to avoid this if-else chain?

[Groverkss]

• Address Arjun's comments

mlir/include/mlir/Analysis/AffineStructures.h

 /// other local identifiers, in a non-mutually recursive way. Hence, every local
 /// identifier can ultimately always be recovered as an affine function of
 /// dimensional and symbolic identifiers (involving floordiv's); note however
 /// that some floordiv combinations are converted to mod's by AffineExpr
 /// construction.
 ///
 class FlatAffineConstraints : public IntegerPolyhedron {
 public:
-  /// All derived classes of FlatAffineConstraints.
-  enum class Kind { FlatAffineConstraints, FlatAffineValueConstraints };
-
   /// Constructs a constraint system reserving memory for the specified number
   /// of constraints and identifiers.
   FlatAffineConstraints(unsigned numReservedInequalities,
                         unsigned numReservedEqualities,
                         unsigned numReservedCols, unsigned numDims,
                         unsigned numSymbols, unsigned numLocals)
       : IntegerPolyhedron(numReservedInequalities, numReservedEqualities,
                           numReservedCols, numDims, numSymbols, numLocals) {}
public:
   /// Creates an affine constraint system from an IntegerSet.
   explicit FlatAffineConstraints(IntegerSet set);
 
   FlatAffineConstraints(const MutableAffineMap &map);
 
   virtual ~FlatAffineConstraints() = default;
 
   /// Return the kind of this FlatAffineConstraints.
-  virtual Kind getKind() const { return Kind::FlatAffineConstraints; }
+  Kind getKind() const override { return Kind::FlatAffineConstraints; }
 
-  static bool classof(const FlatAffineConstraints *cst) { return true; }
+  static bool classof(const IntegerPolyhedron *cst) {
+    return cst->getKind() == Kind::FlatAffineConstraints;
+  }
 
   /// Checks for emptiness by performing variable elimination on all
   /// identifiers, running the GCD test on each equality constraint, and
   /// checking for invalid constraints. Returns true if the GCD test fails for
   /// any equality, or if any invalid constraints are discovered on any row.
   /// Returns false otherwise.
   bool isEmpty() const;
 
public:
   ///    other  = {s0 + 1 <= d0 <= s0 + 9},
   ///    output = {s0 + 1 <= d0 <= s0 + 20}
   /// 3) this   = {0 <= d0 <= 5, 1 <= d1 <= 9}
   ///    other  = {2 <= d0 <= 6, 5 <= d1 <= 15},
   ///    output = {0 <= d0 <= 6, 1 <= d1 <= 15}
   LogicalResult unionBoundingBox(const FlatAffineConstraints &other);
 
   /// Replaces the contents of this FlatAffineConstraints with `other`.
-  virtual void clearAndCopyFrom(const FlatAffineConstraints &other);
+  void clearAndCopyFrom(const IntegerPolyhedron &other) override;
 
   /// Returns the smallest known constant bound for the extent of the specified
   /// identifier (pos^th), i.e., the smallest known constant that is greater
   /// than or equal to 'exclusive upper bound' - 'lower bound' of the
   /// identifier. This constant bound is guaranteed to be non-negative. Returns
   /// None if it's not a constant. This method employs trivial (low complexity /
   /// cost) checks and detection. Symbolic identifiers are treated specially,
   /// i.e., it looks for constant differences between affine expressions
public:
   //
   // All dimensions as set as DimId.
   static FlatAffineValueConstraints
   getHyperrectangular(ValueRange ivs, ValueRange lbs, ValueRange ubs);
 
   /// Return the kind of this FlatAffineConstraints.
   Kind getKind() const override { return Kind::FlatAffineValueConstraints; }
 
-  static bool classof(const FlatAffineConstraints *cst) {
+  static bool classof(const IntegerPolyhedron *cst) {
     return cst->getKind() == Kind::FlatAffineValueConstraints;
   }
 
   /// Clears any existing data and reserves memory for the specified
   /// constraints.
   void reset(unsigned numReservedInequalities, unsigned numReservedEqualities,
              unsigned numReservedCols, unsigned numDims, unsigned numSymbols,
              unsigned numLocals = 0) override;
void mergeAndAlignIdsWithOther(unsigned offset,
                                  FlatAffineValueConstraints *other);
 
   /// Returns true if this constraint system and `other` are in the same
   /// space, i.e., if they are associated with the same set of identifiers,
   /// appearing in the same order. Returns false otherwise.
   bool areIdsAlignedWithOther(const FlatAffineValueConstraints &other);
 
   /// Replaces the contents of this FlatAffineValueConstraints with `other`.
-  void clearAndCopyFrom(const FlatAffineConstraints &other) override;
+  void clearAndCopyFrom(const IntegerPolyhedron &other) override;
 
   /// Returns the Value associated with the pos^th identifier. Asserts if
   /// no Value identifier was associated.
   inline Value getValue(unsigned pos) const {
     assert(hasValue(pos) && "identifier's Value not set");
     return values[pos].getValue();
   }
 

mlir/include/mlir/Analysis/Presburger/IntegerPolyhedron.h

 /// example, the set is equivalent to {2, 4, 6}. Mathematically, existential
 /// quantification can be thought of as the result of projection. In this
 /// example, `q` is existentially quantified. This can be thought of as the
 /// result of projecting out `q` from the previous example, i.e. we obtained {2,
 /// 4, 6} by projecting out the second dimension from {(2, 1), (4, 2), (6, 2)}.
 ///
 class IntegerPolyhedron {
 public:
+  /// All derived classes of IntegerPolyhedron.
+  enum class Kind {
+    FlatAffineConstraints,
+    FlatAffineValueConstraints,
+    IntegerPolyhedron
+  };
+
   /// Kind of identifier (column).
   enum IdKind { Dimension, Symbol, Local };
 
   /// Constructs a constraint system reserving memory for the specified number
   /// of constraints and identifiers.
   IntegerPolyhedron(unsigned numReservedInequalities,
                     unsigned numReservedEqualities, unsigned numReservedCols,
                     unsigned numDims, unsigned numSymbols, unsigned numLocals)
IntegerPolyhedron(unsigned numDims = 0, unsigned numSymbols = 0,
       : IntegerPolyhedron(/*numReservedInequalities=*/0,
                           /*numReservedEqualities=*/0,
                           /*numReservedCols=*/numDims + numSymbols + numLocals +
                               1,
                           numDims, numSymbols, numLocals) {}
 
   virtual ~IntegerPolyhedron() = default;
 
+  /// Return the kind of this IntegerPolyhedron.
+  virtual Kind getKind() const { return Kind::IntegerPolyhedron; }
+
+  static bool classof(const IntegerPolyhedron *cst) { return true; }
+
   // Clones this object.
   std::unique_ptr<IntegerPolyhedron> clone() const;
 
   /// Clears any existing data and reserves memory for the specified
   /// constraints.
   virtual void reset(unsigned numReservedInequalities,
                      unsigned numReservedEqualities, unsigned numReservedCols,
                      unsigned numDims, unsigned numSymbols,
public:
 
   /// Removes all equalities and inequalities.
   void clearConstraints();
 
   /// Sets the `values.size()` identifiers starting at `po`s to the specified
   /// values and removes them.
   void setAndEliminate(unsigned pos, ArrayRef<int64_t> values);
 
+  /// Replaces the contents of this IntegerPolyhedron with `other`.
+  virtual void clearAndCopyFrom(const IntegerPolyhedron &other);
+
   /// Gather positions of all lower and upper bounds of the identifier at `pos`,
   /// and optionally any equalities on it. In addition, the bounds are to be
   /// independent of identifiers in position range [`offset`, `offset` + `num`).
   void
   getLowerAndUpperBoundIndices(unsigned pos,
                                SmallVectorImpl<unsigned> *lbIndices,
                                SmallVectorImpl<unsigned> *ubIndices,
                                SmallVectorImpl<unsigned> *eqIndices = nullptr,

mlir/lib/Analysis/AffineStructures.cpp

if (!redunIneq[r])
       inequalities.copyRow(r, pos++);
 
   inequalities.resizeVertically(pos);
 
   // TODO: consider doing this for equalities as well, but probably not worth
   // the savings.
 }
 
-void FlatAffineConstraints::clearAndCopyFrom(
-    const FlatAffineConstraints &other) {
+void FlatAffineConstraints::clearAndCopyFrom(const IntegerPolyhedron &other) {
   if (auto *otherValueSet = dyn_cast<const FlatAffineValueConstraints>(&other))
     assert(!otherValueSet->hasValues() &&
            "cannot copy associated Values into FlatAffineConstraints");
-  // Note: Assigment operator does not vtable pointer, so kind does not change.
-  *this = other;
+
+  // Note: Assigment operator does not vtable pointer, so kind does not
+  // change.
+  if (auto *otherValueSet = dyn_cast<const FlatAffineConstraints>(&other))
+    *this = *otherValueSet;
+  else
+    *static_cast<IntegerPolyhedron *>(this) = other;
 }
 
 void FlatAffineValueConstraints::clearAndCopyFrom(
-    const FlatAffineConstraints &other) {
+    const IntegerPolyhedron &other) {
+
   if (auto *otherValueSet =
           dyn_cast<const FlatAffineValueConstraints>(&other)) {
     *this = *otherValueSet;
-  } else {
-    *static_cast<FlatAffineConstraints *>(this) = other;
-    values.clear();
-    values.resize(numIds, None);
-  }
-}
+    return;
+  }
+
+  if (auto *otherValueSet = dyn_cast<const FlatAffineValueConstraints>(&other))
+    *static_cast<FlatAffineConstraints *>(this) = *otherValueSet;
+  else
+    *static_cast<IntegerPolyhedron *>(this) = other;
+
 
 static std::pair<unsigned, unsigned>
 getNewNumDimsSymbols(unsigned pos, const FlatAffineConstraints &cst) {
   unsigned numDims = cst.getNumDimIds();
   unsigned numSymbols = cst.getNumSymbolIds();
   unsigned newNumDims, newNumSymbols;
   if (pos < numDims) {
     newNumDims = numDims - 1;

mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp

for (unsigned r = 0, e = getNumInequalities(); r < e; r++)
     for (unsigned i = 0, numVals = values.size(); i < numVals; ++i)
       atIneq(r, getNumCols() - 1) += atIneq(r, pos + i) * values[i];
   for (unsigned r = 0, e = getNumEqualities(); r < e; r++)
     for (unsigned i = 0, numVals = values.size(); i < numVals; ++i)
       atEq(r, getNumCols() - 1) += atEq(r, pos + i) * values[i];
   removeIdRange(pos, pos + values.size());
 }
 
+void IntegerPolyhedron::clearAndCopyFrom(const IntegerPolyhedron &other) {
+  *this = other;
+}
+
 void IntegerPolyhedron::printSpace(raw_ostream &os) const {
   os << "\nConstraints (" << getNumDimIds() << " dims, " << getNumSymbolIds()
      << " symbols, " << getNumLocalIds() << " locals), (" << getNumConstraints()
      << " constraints)\n";
 }
 
 void IntegerPolyhedron::print(raw_ostream &os) const {
   assert(hasConsistentState());