Revert "[MLIR][Presburger] Use `SmallVector` instead of `std::vector` in `getLocalRepr`"

[pashu123]

Summary

This reverts commit 3cc544772848682bc77ff63db659a5aa4b3d4e6b.
SmallVector inside SmallVector are not optimized.

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

public:
   /// variable can be computed. The indices of the constraints are stored in
   /// `MaybeLocalRepr` struct. If no such pair can be found, the kind attribute
   /// in `MaybeLocalRepr` is set to None.
   ///
   /// The dividends of the explicit representations are stored in `dividends`
   /// and the denominators in `denominators`. If no explicit representation
   /// could be found for the `i^th` local identifier, `denominators[i]` is set
   /// to 0.
-  void
-  getLocalReprs(SmallVectorImpl<SmallVector<int64_t, 8>> &dividends,
-                SmallVectorImpl<unsigned> &denominators,
-                SmallVectorImpl<presburger_utils::MaybeLocalRepr> &repr) const;
-  void
-  getLocalReprs(SmallVectorImpl<presburger_utils::MaybeLocalRepr> &repr) const;
-  void getLocalReprs(SmallVectorImpl<SmallVector<int64_t, 8>> &dividends,
-                     SmallVectorImpl<unsigned> &denominators) const;
+  void getLocalReprs(std::vector<SmallVector<int64_t, 8>> &dividends,
+                     SmallVector<unsigned, 4> &denominators,
+                     std::vector<presburger_utils::MaybeLocalRepr> &repr) const;
+  void getLocalReprs(std::vector<presburger_utils::MaybeLocalRepr> &repr) const;
+  void getLocalReprs(std::vector<SmallVector<int64_t, 8>> &dividends,
+                     SmallVector<unsigned, 4> &denominators) const;
 
   /// The type of bound: equal, lower bound or upper bound.
   enum BoundType { EQ, LB, UB };
 
   /// Adds a constant bound for the specified identifier.
   void addBound(BoundType type, unsigned pos, int64_t value);
 
   /// Adds a constant bound for the specified expression.

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

 /// 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 `i^th` division. If it returns `false`,
 /// the divisions are not merged. `merge` can also do side effects, For example
 /// it can merge the local identifiers in IntegerPolyhedron.
 void removeDuplicateDivs(
-    SmallVectorImpl<SmallVector<int64_t, 8>> &divs,
+    std::vector<SmallVector<int64_t, 8>> &divs,
     SmallVectorImpl<unsigned> &denoms, unsigned localOffset,
     llvm::function_ref<bool(unsigned i, unsigned j)> merge);
 
 } // namespace presburger_utils
 } // namespace mlir
 
 #endif // MLIR_ANALYSIS_PRESBURGER_UTILS_H

mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp

bool IntegerPolyhedron::containsPoint(ArrayRef<int64_t> point) const {
   }
   for (unsigned i = 0, e = getNumInequalities(); i < e; ++i) {
     if (valueAt(getInequality(i), point) < 0)
       return false;
   }
   return true;
 }
 
-void IntegerPolyhedron::getLocalReprs(
-    SmallVectorImpl<MaybeLocalRepr> &repr) const {
-  SmallVector<SmallVector<int64_t, 8>> dividends(getNumLocalIds());
+void IntegerPolyhedron::getLocalReprs(std::vector<MaybeLocalRepr> &repr) const {
+  std::vector<SmallVector<int64_t, 8>> dividends(getNumLocalIds());
   SmallVector<unsigned, 4> denominators(getNumLocalIds());
   getLocalReprs(dividends, denominators, repr);
 }
 
 void IntegerPolyhedron::getLocalReprs(
-    SmallVectorImpl<SmallVector<int64_t, 8>> &dividends,
-    SmallVectorImpl<unsigned> &denominators) const {
-  SmallVector<MaybeLocalRepr> repr(getNumLocalIds());
+    std::vector<SmallVector<int64_t, 8>> &dividends,
+    SmallVector<unsigned, 4> &denominators) const {
+  std::vector<MaybeLocalRepr> repr(getNumLocalIds());
   getLocalReprs(dividends, denominators, repr);
 }
 
 void IntegerPolyhedron::getLocalReprs(
-    SmallVectorImpl<SmallVector<int64_t, 8>> &dividends,
-    SmallVectorImpl<unsigned> &denominators,
-    SmallVectorImpl<MaybeLocalRepr> &repr) const {
+    std::vector<SmallVector<int64_t, 8>> &dividends,
+    SmallVector<unsigned, 4> &denominators,
+    std::vector<MaybeLocalRepr> &repr) const {
 
   repr.resize(getNumLocalIds());
   dividends.resize(getNumLocalIds());
   denominators.resize(getNumLocalIds());
 
   SmallVector<bool, 8> foundRepr(getNumIds(), false);
   for (unsigned i = 0, e = getNumDimAndSymbolIds(); i < e; ++i)
     foundRepr[i] = true;
void IntegerPolyhedron::mergeLocalIds(IntegerPolyhedron &other) {
   // Merge local ids of polyA and polyB without using division information,
   // i.e. append local ids of `polyB` to `polyA` and insert local ids of `polyA`
   // to `polyB` at start of its local ids.
   unsigned initLocals = polyA.getNumLocalIds();
   insertLocalId(polyA.getNumLocalIds(), polyB.getNumLocalIds());
   polyB.insertLocalId(0, initLocals);
 
   // Get division representations from each poly.
-  SmallVector<SmallVector<int64_t, 8>> divsA, divsB;
+  std::vector<SmallVector<int64_t, 8>> divsA, divsB;
   SmallVector<unsigned, 4> denomsA, denomsB;
   polyA.getLocalReprs(divsA, denomsA);
   polyB.getLocalReprs(divsB, denomsB);
 
   // Copy division information for polyB into `divsA` and `denomsA`, so that
   // these have the combined division information of both polys. Since newly
   // added local variables in polyA and polyB have no constraints, they will not
   // have any division representation.

mlir/lib/Analysis/Presburger/PresburgerSet.cpp

b.removeIdRange(IntegerPolyhedron::IdKind::Local, bInitNumLocals,
                     b.getNumLocalIds());
     b.removeInequalityRange(bInitNumIneqs, b.getNumInequalities());
     b.removeEqualityRange(bInitNumEqs, b.getNumEqualities());
     simplex.rollback(initialSnapshot);
   };
 
   // Find out which inequalities of sI correspond to division inequalities for
   // the local variables of sI.
-  SmallVector<MaybeLocalRepr> repr(sI.getNumLocalIds());
+  std::vector<MaybeLocalRepr> repr(sI.getNumLocalIds());
   sI.getLocalReprs(repr);
 
   // Add sI's locals to b, after b's locals. Also add b's locals to sI, before
   // sI's locals.
   b.mergeLocalIds(sI);
 
   // Mark which inequalities of sI are division inequalities and add all such
   // inequalities to b.

mlir/lib/Analysis/Presburger/Utils.cpp

static LogicalResult getDivRepr(const IntegerPolyhedron &cst, unsigned pos,
                                 unsigned eqInd, SmallVector<int64_t, 8> &expr,
                                 unsigned &divisor) {
 
   assert(pos <= cst.getNumIds() && "Invalid identifier position");
   assert(eqInd <= cst.getNumEqualities() && "Invalid equality position");
 
   // Extract divisor, the divisor can be negative and hence its sign information
   // is stored in `signDiv` to reverse the sign of dividend's coefficients.
-  // Equality must involve the pos-th variable and hence `tempDiv` != 0.
-  int64_t tempDiv = cst.atEq(eqInd, pos);
-  if (tempDiv == 0)
+  // Equality must involve the pos-th variable and hence `temp_div` != 0.
+  int64_t temp_div = cst.atEq(eqInd, pos);
+  if (temp_div == 0)
     return failure();
-  int64_t signDiv = tempDiv < 0 ? -1 : 1;
+  int64_t signDiv = temp_div < 0 ? -1 : 1;
 
   // The divisor is always a positive integer.
-  divisor = tempDiv * signDiv;
+  divisor = temp_div * signDiv;
 
   expr.resize(cst.getNumCols(), 0);
   for (unsigned i = 0, e = cst.getNumIds(); i < e; ++i)
     if (i != pos)
       expr[i] = signDiv * cst.atEq(eqInd, i);
 
   expr.back() = signDiv * cst.atEq(eqInd, cst.getNumCols() - 1);
   normalizeDivisionByGCD(expr, divisor);
for (unsigned eqPos : eqIndices) {
     repr.kind = ReprKind::Equality;
     repr.repr.equalityIdx = eqPos;
     return repr;
   }
   return repr;
 }
 
 void presburger_utils::removeDuplicateDivs(
-    SmallVectorImpl<SmallVector<int64_t, 8>> &divs,
+    std::vector<SmallVector<int64_t, 8>> &divs,
     SmallVectorImpl<unsigned> &denoms, unsigned localOffset,
     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
   // identifier at position `i` only depends on local identifiers at position <

mlir/unittests/Analysis/Presburger/IntegerPolyhedronTest.cpp

 /// denominator in `expectedDenominators`. The `denominators` and `dividends`
 /// obtained through `getLocalRepr` function is verified against the
 /// `expectedDenominators` and `expectedDividends` respectively.
 static void checkDivisionRepresentation(
     IntegerPolyhedron &poly,
     const std::vector<SmallVector<int64_t, 8>> &expectedDividends,
     const SmallVectorImpl<unsigned> &expectedDenominators) {
 
-  SmallVector<SmallVector<int64_t, 8>> dividends;
+  std::vector<SmallVector<int64_t, 8>> dividends;
   SmallVector<unsigned, 4> denominators;
 
   poly.getLocalReprs(dividends, denominators);
 
   // Check that the `denominators` and `expectedDenominators` match.
   EXPECT_TRUE(expectedDenominators == denominators);
 
   // Check that the `dividends` and `expectedDividends` match. If the