diff --git a/mlir/include/mlir/Analysis/AffineStructures.h b/mlir/include/mlir/Analysis/AffineStructures.h --- a/mlir/include/mlir/Analysis/AffineStructures.h +++ b/mlir/include/mlir/Analysis/AffineStructures.h @@ -13,6 +13,7 @@ #ifndef MLIR_ANALYSIS_AFFINESTRUCTURES_H #define MLIR_ANALYSIS_AFFINESTRUCTURES_H +#include "mlir/Analysis/Presburger/IntegerPolyhedron.h" #include "mlir/Analysis/Presburger/Matrix.h" #include "mlir/IR/AffineExpr.h" #include "mlir/IR/OpDefinition.h" @@ -56,36 +57,29 @@ /// that some floordiv combinations are converted to mod's by AffineExpr /// construction. /// -class FlatAffineConstraints { +class FlatAffineConstraints : public IntegerPolyhedron { public: /// All derived classes of FlatAffineConstraints. enum class Kind { FlatAffineConstraints, FlatAffineValueConstraints }; - /// Kind of identifier (column). - enum IdKind { Dimension, Symbol, Local }; - /// 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) - : numIds(numDims + numSymbols + numLocals), numDims(numDims), - numSymbols(numSymbols), - equalities(0, numIds + 1, numReservedEqualities, numReservedCols), - inequalities(0, numIds + 1, numReservedInequalities, numReservedCols) { - assert(numReservedCols >= numIds + 1); - } + : IntegerPolyhedron(numReservedInequalities, numReservedEqualities, + numReservedCols, numDims, numSymbols, numLocals) {} /// Constructs a constraint system with the specified number of /// dimensions and symbols. FlatAffineConstraints(unsigned numDims = 0, unsigned numSymbols = 0, unsigned numLocals = 0) - : FlatAffineConstraints(/*numReservedInequalities=*/0, - /*numReservedEqualities=*/0, - /*numReservedCols=*/numDims + numSymbols + - numLocals + 1, - numDims, numSymbols, numLocals) {} + : IntegerPolyhedron(/*numReservedInequalities=*/0, + /*numReservedEqualities=*/0, + /*numReservedCols=*/numDims + numSymbols + numLocals + + 1, + numDims, numSymbols, numLocals) {} /// Return a system with no constraints, i.e., one which is satisfied by all /// points. @@ -106,20 +100,6 @@ static bool classof(const FlatAffineConstraints *cst) { return true; } - /// Clears any existing data and reserves memory for the specified - /// constraints. - virtual void reset(unsigned numReservedInequalities, - unsigned numReservedEqualities, unsigned numReservedCols, - unsigned numDims, unsigned numSymbols, - unsigned numLocals = 0); - - void reset(unsigned numDims = 0, unsigned numSymbols = 0, - unsigned numLocals = 0); - - /// Appends constraints from `other` into `this`. This is equivalent to an - /// intersection with no simplification of any sort attempted. - void append(const FlatAffineConstraints &other); - /// 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 @@ -177,41 +157,6 @@ // Clones this object. std::unique_ptr clone() const; - /// Returns the value at the specified equality row and column. - inline int64_t atEq(unsigned i, unsigned j) const { return equalities(i, j); } - inline int64_t &atEq(unsigned i, unsigned j) { return equalities(i, j); } - - /// Returns the value at the specified inequality row and column. - inline int64_t atIneq(unsigned i, unsigned j) const { - return inequalities(i, j); - } - inline int64_t &atIneq(unsigned i, unsigned j) { return inequalities(i, j); } - - /// Returns the number of columns in the constraint system. - inline unsigned getNumCols() const { return numIds + 1; } - - inline unsigned getNumEqualities() const { return equalities.getNumRows(); } - - inline unsigned getNumInequalities() const { - return inequalities.getNumRows(); - } - - inline unsigned getNumReservedEqualities() const { - return equalities.getNumReservedRows(); - } - - inline unsigned getNumReservedInequalities() const { - return inequalities.getNumReservedRows(); - } - - inline ArrayRef getEquality(unsigned idx) const { - return equalities.getRow(idx); - } - - inline ArrayRef getInequality(unsigned idx) const { - return inequalities.getRow(idx); - } - /// The type of bound: equal, lower bound or upper bound. enum BoundType { EQ, LB, UB }; @@ -246,11 +191,6 @@ SmallVectorImpl *lbMaps, SmallVectorImpl *ubMaps); - /// Adds an inequality (>= 0) from the coefficients specified in `inEq`. - void addInequality(ArrayRef inEq); - /// Adds an equality from the coefficients specified in `eq`. - void addEquality(ArrayRef eq); - /// Adds a new local identifier as the floordiv of an affine function of other /// identifiers, the coefficients of which are provided in `dividend` and with /// respect to a positive constant `divisor`. Two constraints are added to the @@ -258,27 +198,6 @@ /// q = dividend floordiv c <=> c*q <= dividend <= c*q + c - 1. void addLocalFloorDiv(ArrayRef dividend, int64_t divisor); - /// Swap the posA^th identifier with the posB^th identifier. - virtual void swapId(unsigned posA, unsigned posB); - - /// Insert `num` identifiers of the specified kind at position `pos`. - /// Positions are relative to the kind of identifier. The coefficient columns - /// corresponding to the added identifiers are initialized to zero. Return the - /// absolute column position (i.e., not relative to the kind of identifier) - /// of the first added identifier. - unsigned insertDimId(unsigned pos, unsigned num = 1); - unsigned insertSymbolId(unsigned pos, unsigned num = 1); - unsigned insertLocalId(unsigned pos, unsigned num = 1); - virtual unsigned insertId(IdKind kind, unsigned pos, unsigned num = 1); - - /// Append `num` identifiers of the specified kind after the last identifier. - /// of that kind. Return the position of the first appended column. The - /// coefficient columns corresponding to the added identifiers are initialized - /// to zero. - unsigned appendDimId(unsigned num = 1); - unsigned appendSymbolId(unsigned num = 1); - unsigned appendLocalId(unsigned num = 1); - /// Composes an affine map whose dimensions and symbols match one to one with /// the dimensions and symbols of this FlatAffineConstraints. The results of /// the map `other` are added as the leading dimensions of this constraint @@ -293,22 +212,6 @@ void projectOut(unsigned pos, unsigned num); inline void projectOut(unsigned pos) { return projectOut(pos, 1); } - /// Removes identifiers of the specified kind with the specified pos (or - /// within the specified range) from the system. The specified location is - /// relative to the first identifier of the specified kind. - void removeId(IdKind kind, unsigned pos); - void removeIdRange(IdKind kind, unsigned idStart, unsigned idLimit); - - /// Removes the specified identifier from the system. - void removeId(unsigned pos); - - void removeEquality(unsigned pos); - void removeInequality(unsigned pos); - - /// Remove the (in)equalities at positions [start, end). - void removeEqualityRange(unsigned start, unsigned end); - void removeInequalityRange(unsigned start, unsigned end); - /// Sets the `values.size()` identifiers starting at `po`s to the specified /// values and removes them. void setAndEliminate(unsigned pos, ArrayRef values); @@ -347,17 +250,6 @@ /// output = {0 <= d0 <= 6, 1 <= d1 <= 15} LogicalResult unionBoundingBox(const FlatAffineConstraints &other); - unsigned getNumConstraints() const { - return getNumInequalities() + getNumEqualities(); - } - inline unsigned getNumIds() const { return numIds; } - inline unsigned getNumDimIds() const { return numDims; } - inline unsigned getNumSymbolIds() const { return numSymbols; } - inline unsigned getNumDimAndSymbolIds() const { return numDims + numSymbols; } - inline unsigned getNumLocalIds() const { - return numIds - numDims - numSymbols; - } - /// Replaces the contents of this FlatAffineConstraints with `other`. virtual void clearAndCopyFrom(const FlatAffineConstraints &other); @@ -453,19 +345,10 @@ /// match. void mergeLocalIds(FlatAffineConstraints &other); - /// Removes all equalities and inequalities. - void clearConstraints(); - void print(raw_ostream &os) const; void dump() const; protected: - /// Return the index at which the specified kind of id starts. - unsigned getIdKindOffset(IdKind kind) const; - - /// Assert that `value` is at most the number of ids of the specified kind. - void assertAtMostNumIdKind(unsigned value, IdKind kind) const; - /// Returns false if the fields corresponding to various identifier counts, or /// equality/inequality buffer sizes aren't consistent; true otherwise. This /// is meant to be used within an assert internally. @@ -536,27 +419,6 @@ /// Normalized each constraints by the GCD of its coefficients. void normalizeConstraintsByGCD(); - /// Removes identifiers in the column range [idStart, idLimit), and copies any - /// remaining valid data into place, updates member variables, and resizes - /// arrays as needed. - virtual void removeIdRange(unsigned idStart, unsigned idLimit); - - /// Total number of identifiers. - unsigned numIds; - - /// Number of identifiers corresponding to real dimensions. - unsigned numDims; - - /// Number of identifiers corresponding to symbols (unknown but constant for - /// analysis). - unsigned numSymbols; - - /// Coefficients of affine equalities (in == 0 form). - Matrix equalities; - - /// Coefficients of affine inequalities (in >= 0 form). - Matrix inequalities; - /// A parameter that controls detection of an unrealistic number of /// constraints. If the number of constraints is this many times the number of /// variables, we consider such a system out of line with the intended use diff --git a/mlir/include/mlir/Analysis/Presburger/IntegerPolyhedron.h b/mlir/include/mlir/Analysis/Presburger/IntegerPolyhedron.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Analysis/Presburger/IntegerPolyhedron.h @@ -0,0 +1,219 @@ +//===- IntegerPolyhedron.h - MLIR IntegerPolyhedron Class -----*- C++ -*---===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// A class to represent an integer polyhedra. +// +//===----------------------------------------------------------------------===// + +#ifndef MLIR_ANALYSIS_PRESBURGER_INTEGERPOLYHEDRON_H +#define MLIR_ANALYSIS_PRESBURGER_INTEGERPOLYHEDRON_H + +#include "mlir/Analysis/Presburger/Matrix.h" + +namespace mlir { + +/// An integer polyhedron is the set of solutions to a list of affine +/// constraints over n integer-valued variables/identifiers. Affine constraints +/// can be inequalities or equalities in the form: +/// +/// Inequality: c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} + c_n >= 0 +/// Equality : c_0*x_0 + c_1*x_1 + .... + c_{n-1}*x_{n-1} + c_n == 0 +/// +/// where c_0, c_1, ..., c_n are integers. +/// +/// Such a set corresponds to the set of integer points lying in a convex +/// polyhedron. For example, consider the set: (x, y) : (1 <= x <= 7, x = 2y). +/// This set contains the points (2, 1), (4, 2), and (6, 3). +/// +/// The integer-valued variables are distinguished into 3 types of: +/// +/// Dimension: Ordinary variables over which the set is represented. +/// +/// Symbol: Symbol variables correspond to fixed but unknown values. +/// Mathematically, an integer polyhedron with symbolic variables is like a +/// family of integer polyhedra indexed by the symbolic variables. +/// +/// Local: Local variables correspond to existentially quantified variables. For +/// example, consider the set: (x) : (exists q : 1 <= x <= 7, x = 2q). An +/// assignment to symbolic and dimension variables is valid if there exists some +/// assignment to the local variable `q` satisfying these constraints. For this +/// 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: + /// 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) + : numIds(numDims + numSymbols + numLocals), numDims(numDims), + numSymbols(numSymbols), + equalities(0, numIds + 1, numReservedEqualities, numReservedCols), + inequalities(0, numIds + 1, numReservedInequalities, numReservedCols) { + assert(numReservedCols >= numIds + 1); + } + + /// Constructs a constraint system with the specified number of + /// dimensions and symbols. + IntegerPolyhedron(unsigned numDims = 0, unsigned numSymbols = 0, + unsigned numLocals = 0) + : IntegerPolyhedron(/*numReservedInequalities=*/0, + /*numReservedEqualities=*/0, + /*numReservedCols=*/numDims + numSymbols + numLocals + + 1, + numDims, numSymbols, numLocals) {} + + virtual ~IntegerPolyhedron() = default; + + // Clones this object. + std::unique_ptr 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, + unsigned numLocals = 0); + + void reset(unsigned numDims = 0, unsigned numSymbols = 0, + unsigned numLocals = 0); + + /// Appends constraints from `other` into `this`. This is equivalent to an + /// intersection with no simplification of any sort attempted. + void append(const IntegerPolyhedron &other); + + /// Returns the value at the specified equality row and column. + inline int64_t atEq(unsigned i, unsigned j) const { return equalities(i, j); } + inline int64_t &atEq(unsigned i, unsigned j) { return equalities(i, j); } + + /// Returns the value at the specified inequality row and column. + inline int64_t atIneq(unsigned i, unsigned j) const { + return inequalities(i, j); + } + inline int64_t &atIneq(unsigned i, unsigned j) { return inequalities(i, j); } + + unsigned getNumConstraints() const { + return getNumInequalities() + getNumEqualities(); + } + inline unsigned getNumIds() const { return numIds; } + inline unsigned getNumDimIds() const { return numDims; } + inline unsigned getNumSymbolIds() const { return numSymbols; } + inline unsigned getNumDimAndSymbolIds() const { return numDims + numSymbols; } + inline unsigned getNumLocalIds() const { + return numIds - numDims - numSymbols; + } + + /// Returns the number of columns in the constraint system. + inline unsigned getNumCols() const { return numIds + 1; } + + inline unsigned getNumEqualities() const { return equalities.getNumRows(); } + + inline unsigned getNumInequalities() const { + return inequalities.getNumRows(); + } + + inline unsigned getNumReservedEqualities() const { + return equalities.getNumReservedRows(); + } + + inline unsigned getNumReservedInequalities() const { + return inequalities.getNumReservedRows(); + } + + inline ArrayRef getEquality(unsigned idx) const { + return equalities.getRow(idx); + } + + inline ArrayRef getInequality(unsigned idx) const { + return inequalities.getRow(idx); + } + + /// Insert `num` identifiers of the specified kind at position `pos`. + /// Positions are relative to the kind of identifier. The coefficient columns + /// corresponding to the added identifiers are initialized to zero. Return the + /// absolute column position (i.e., not relative to the kind of identifier) + /// of the first added identifier. + unsigned insertDimId(unsigned pos, unsigned num = 1); + unsigned insertSymbolId(unsigned pos, unsigned num = 1); + unsigned insertLocalId(unsigned pos, unsigned num = 1); + virtual unsigned insertId(IdKind kind, unsigned pos, unsigned num = 1); + + /// Append `num` identifiers of the specified kind after the last identifier. + /// of that kind. Return the position of the first appended column. The + /// coefficient columns corresponding to the added identifiers are initialized + /// to zero. + unsigned appendDimId(unsigned num = 1); + unsigned appendSymbolId(unsigned num = 1); + unsigned appendLocalId(unsigned num = 1); + + /// Adds an inequality (>= 0) from the coefficients specified in `inEq`. + void addInequality(ArrayRef inEq); + /// Adds an equality from the coefficients specified in `eq`. + void addEquality(ArrayRef eq); + + /// Removes identifiers of the specified kind with the specified pos (or + /// within the specified range) from the system. The specified location is + /// relative to the first identifier of the specified kind. + void removeId(IdKind kind, unsigned pos); + void removeIdRange(IdKind kind, unsigned idStart, unsigned idLimit); + + /// Removes the specified identifier from the system. + void removeId(unsigned pos); + + void removeEquality(unsigned pos); + void removeInequality(unsigned pos); + + /// Remove the (in)equalities at positions [start, end). + void removeEqualityRange(unsigned start, unsigned end); + void removeInequalityRange(unsigned start, unsigned end); + + /// Swap the posA^th identifier with the posB^th identifier. + virtual void swapId(unsigned posA, unsigned posB); + + /// Removes all equalities and inequalities. + void clearConstraints(); + +protected: + /// Return the index at which the specified kind of id starts. + unsigned getIdKindOffset(IdKind kind) const; + + /// Assert that `value` is at most the number of ids of the specified kind. + void assertAtMostNumIdKind(unsigned value, IdKind kind) const; + + /// Removes identifiers in the column range [idStart, idLimit), and copies any + /// remaining valid data into place, updates member variables, and resizes + /// arrays as needed. + virtual void removeIdRange(unsigned idStart, unsigned idLimit); + + /// Total number of identifiers. + unsigned numIds; + + /// Number of identifiers corresponding to real dimensions. + unsigned numDims; + + /// Number of identifiers corresponding to symbols (unknown but constant for + /// analysis). + unsigned numSymbols; + + /// Coefficients of affine equalities (in == 0 form). + Matrix equalities; + + /// Coefficients of affine inequalities (in >= 0 form). + Matrix inequalities; +}; + +} // namespace mlir + +#endif // MLIR_ANALYSIS_PRESBURGER_INTEGERPOLYHEDRON_H diff --git a/mlir/lib/Analysis/AffineStructures.cpp b/mlir/lib/Analysis/AffineStructures.cpp --- a/mlir/lib/Analysis/AffineStructures.cpp +++ b/mlir/lib/Analysis/AffineStructures.cpp @@ -157,10 +157,11 @@ // Construct from an IntegerSet. FlatAffineConstraints::FlatAffineConstraints(IntegerSet set) - : numIds(set.getNumDims() + set.getNumSymbols()), numDims(set.getNumDims()), - numSymbols(set.getNumSymbols()), - equalities(0, numIds + 1, set.getNumEqualities(), numIds + 1), - inequalities(0, numIds + 1, set.getNumInequalities(), numIds + 1) { + : IntegerPolyhedron(set.getNumInequalities(), set.getNumEqualities(), + set.getNumDims() + set.getNumSymbols() + 1, + set.getNumDims(), set.getNumSymbols(), + /*numLocals=*/0) { + // Flatten expressions and add them to the constraint system. std::vector> flatExprs; FlatAffineConstraints localVarCst; @@ -232,18 +233,6 @@ return res; } -void FlatAffineConstraints::reset(unsigned numReservedInequalities, - unsigned numReservedEqualities, - unsigned newNumReservedCols, - unsigned newNumDims, unsigned newNumSymbols, - unsigned newNumLocals) { - assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 && - "minimum 1 column"); - *this = FlatAffineConstraints(numReservedInequalities, numReservedEqualities, - newNumReservedCols, newNumDims, newNumSymbols, - newNumLocals); -} - void FlatAffineValueConstraints::reset(unsigned numReservedInequalities, unsigned numReservedEqualities, unsigned newNumReservedCols, @@ -269,12 +258,6 @@ newNumDims, newNumSymbols, newNumLocals, newVals); } -void FlatAffineConstraints::reset(unsigned newNumDims, unsigned newNumSymbols, - unsigned newNumLocals) { - reset(0, 0, newNumDims + newNumSymbols + newNumLocals + 1, newNumDims, - newNumSymbols, newNumLocals); -} - void FlatAffineValueConstraints::reset(unsigned newNumDims, unsigned newNumSymbols, unsigned newNumLocals, @@ -283,114 +266,28 @@ newNumSymbols, newNumLocals, valArgs); } -void FlatAffineConstraints::append(const FlatAffineConstraints &other) { - assert(other.getNumCols() == getNumCols()); - assert(other.getNumDimIds() == getNumDimIds()); - assert(other.getNumSymbolIds() == getNumSymbolIds()); - - inequalities.reserveRows(inequalities.getNumRows() + - other.getNumInequalities()); - equalities.reserveRows(equalities.getNumRows() + other.getNumEqualities()); - - for (unsigned r = 0, e = other.getNumInequalities(); r < e; r++) { - addInequality(other.getInequality(r)); - } - for (unsigned r = 0, e = other.getNumEqualities(); r < e; r++) { - addEquality(other.getEquality(r)); - } -} - -unsigned FlatAffineConstraints::appendDimId(unsigned num) { - unsigned pos = getNumDimIds(); - insertId(IdKind::Dimension, pos, num); - return pos; -} - unsigned FlatAffineValueConstraints::appendDimId(ValueRange vals) { unsigned pos = getNumDimIds(); insertId(IdKind::Dimension, pos, vals); return pos; } -unsigned FlatAffineConstraints::appendSymbolId(unsigned num) { - unsigned pos = getNumSymbolIds(); - insertId(IdKind::Symbol, pos, num); - return pos; -} - unsigned FlatAffineValueConstraints::appendSymbolId(ValueRange vals) { unsigned pos = getNumSymbolIds(); insertId(IdKind::Symbol, pos, vals); return pos; } -unsigned FlatAffineConstraints::appendLocalId(unsigned num) { - unsigned pos = getNumLocalIds(); - insertId(IdKind::Local, pos, num); - return pos; -} - -unsigned FlatAffineConstraints::insertDimId(unsigned pos, unsigned num) { - return insertId(IdKind::Dimension, pos, num); -} - unsigned FlatAffineValueConstraints::insertDimId(unsigned pos, ValueRange vals) { return insertId(IdKind::Dimension, pos, vals); } -unsigned FlatAffineConstraints::insertSymbolId(unsigned pos, unsigned num) { - return insertId(IdKind::Symbol, pos, num); -} - unsigned FlatAffineValueConstraints::insertSymbolId(unsigned pos, ValueRange vals) { return insertId(IdKind::Symbol, pos, vals); } -unsigned FlatAffineConstraints::insertLocalId(unsigned pos, unsigned num) { - return insertId(IdKind::Local, pos, num); -} - -unsigned FlatAffineConstraints::insertId(IdKind kind, unsigned pos, - unsigned num) { - assertAtMostNumIdKind(pos, kind); - - unsigned absolutePos = getIdKindOffset(kind) + pos; - if (kind == IdKind::Dimension) - numDims += num; - else if (kind == IdKind::Symbol) - numSymbols += num; - numIds += num; - - inequalities.insertColumns(absolutePos, num); - equalities.insertColumns(absolutePos, num); - - return absolutePos; -} - -void FlatAffineConstraints::assertAtMostNumIdKind(unsigned val, - IdKind kind) const { - if (kind == IdKind::Dimension) - assert(val <= getNumDimIds()); - else if (kind == IdKind::Symbol) - assert(val <= getNumSymbolIds()); - else if (kind == IdKind::Local) - assert(val <= getNumLocalIds()); - else - llvm_unreachable("IdKind expected to be Dimension, Symbol or Local!"); -} - -unsigned FlatAffineConstraints::getIdKindOffset(IdKind kind) const { - if (kind == IdKind::Dimension) - return 0; - if (kind == IdKind::Symbol) - return getNumDimIds(); - if (kind == IdKind::Local) - return getNumDimAndSymbolIds(); - llvm_unreachable("IdKind expected to be Dimension, Symbol or Local!"); -} - unsigned FlatAffineValueConstraints::insertId(IdKind kind, unsigned pos, unsigned num) { unsigned absolutePos = FlatAffineConstraints::insertId(kind, pos, num); @@ -420,17 +317,6 @@ }) != values.end(); } -void FlatAffineConstraints::removeId(IdKind kind, unsigned pos) { - removeIdRange(kind, pos, pos + 1); -} - -void FlatAffineConstraints::removeIdRange(IdKind kind, unsigned idStart, - unsigned idLimit) { - assertAtMostNumIdKind(idLimit, kind); - removeIdRange(getIdKindOffset(kind) + idStart, - getIdKindOffset(kind) + idLimit); -} - /// Checks if two constraint systems are in the same space, i.e., if they are /// associated with the same set of identifiers, appearing in the same order. static bool areIdsAligned(const FlatAffineValueConstraints &a, @@ -944,41 +830,6 @@ } } -void FlatAffineConstraints::removeIdRange(unsigned idStart, unsigned idLimit) { - assert(idLimit < getNumCols() && "invalid id limit"); - - if (idStart >= idLimit) - return; - - // We are going to be removing one or more identifiers from the range. - assert(idStart < numIds && "invalid idStart position"); - - // TODO: Make 'removeIdRange' a lambda called from here. - // Remove eliminated identifiers from the constraints.. - equalities.removeColumns(idStart, idLimit - idStart); - inequalities.removeColumns(idStart, idLimit - idStart); - - // Update members numDims, numSymbols and numIds. - unsigned numDimsEliminated = 0; - unsigned numLocalsEliminated = 0; - unsigned numColsEliminated = idLimit - idStart; - if (idStart < numDims) { - numDimsEliminated = std::min(numDims, idLimit) - idStart; - } - // Check how many local id's were removed. Note that our identifier order is - // [dims, symbols, locals]. Local id start at position numDims + numSymbols. - if (idLimit > numDims + numSymbols) { - numLocalsEliminated = std::min( - idLimit - std::max(idStart, numDims + numSymbols), getNumLocalIds()); - } - unsigned numSymbolsEliminated = - numColsEliminated - numDimsEliminated - numLocalsEliminated; - - numDims -= numDimsEliminated; - numSymbols -= numSymbolsEliminated; - numIds = numIds - numColsEliminated; -} - void FlatAffineValueConstraints::removeIdRange(unsigned idStart, unsigned idLimit) { FlatAffineConstraints::removeIdRange(idStart, idLimit); @@ -2516,20 +2367,6 @@ return success(); } -void FlatAffineConstraints::addEquality(ArrayRef eq) { - assert(eq.size() == getNumCols()); - unsigned row = equalities.appendExtraRow(); - for (unsigned i = 0, e = eq.size(); i < e; ++i) - equalities(row, i) = eq[i]; -} - -void FlatAffineConstraints::addInequality(ArrayRef inEq) { - assert(inEq.size() == getNumCols()); - unsigned row = inequalities.appendExtraRow(); - for (unsigned i = 0, e = inEq.size(); i < e; ++i) - inequalities(row, i) = inEq[i]; -} - void FlatAffineConstraints::addBound(BoundType type, unsigned pos, int64_t value) { assert(pos < getNumCols()); @@ -2603,19 +2440,6 @@ }); } -void FlatAffineConstraints::swapId(unsigned posA, unsigned posB) { - assert(posA < getNumIds() && "invalid position A"); - assert(posB < getNumIds() && "invalid position B"); - - if (posA == posB) - return; - - for (unsigned r = 0, e = getNumInequalities(); r < e; r++) - std::swap(atIneq(r, posA), atIneq(r, posB)); - for (unsigned r = 0, e = getNumEqualities(); r < e; r++) - std::swap(atEq(r, posA), atEq(r, posB)); -} - void FlatAffineValueConstraints::swapId(unsigned posA, unsigned posB) { FlatAffineConstraints::swapId(posA, posB); std::swap(values[posA], values[posB]); @@ -2637,27 +2461,6 @@ addBound(type, pos, value); } -void FlatAffineConstraints::removeEquality(unsigned pos) { - equalities.removeRow(pos); -} - -void FlatAffineConstraints::removeInequality(unsigned pos) { - inequalities.removeRow(pos); -} - -void FlatAffineConstraints::removeEqualityRange(unsigned begin, unsigned end) { - if (begin >= end) - return; - equalities.removeRows(begin, end - begin); -} - -void FlatAffineConstraints::removeInequalityRange(unsigned begin, - unsigned end) { - if (begin >= end) - return; - inequalities.removeRows(begin, end - begin); -} - /// Finds an equality that equates the specified identifier to a constant. /// Returns the position of the equality row. If 'symbolic' is set to true, /// symbols are also treated like a constant, i.e., an affine function of the @@ -3085,10 +2888,6 @@ } } -void FlatAffineConstraints::removeId(unsigned pos) { - removeIdRange(pos, pos + 1); -} - static std::pair getNewNumDimsSymbols(unsigned pos, const FlatAffineConstraints &cst) { unsigned numDims = cst.getNumDimIds(); @@ -3371,11 +3170,6 @@ fourierMotzkinEliminate(pos); } -void FlatAffineConstraints::clearConstraints() { - equalities.resizeVertically(0); - inequalities.resizeVertically(0); -} - namespace { enum BoundCmpResult { Greater, Less, Equal, Unknown }; diff --git a/mlir/lib/Analysis/Presburger/CMakeLists.txt b/mlir/lib/Analysis/Presburger/CMakeLists.txt --- a/mlir/lib/Analysis/Presburger/CMakeLists.txt +++ b/mlir/lib/Analysis/Presburger/CMakeLists.txt @@ -1,6 +1,7 @@ add_mlir_library(MLIRPresburger - Simplex.cpp + IntegerPolyhedron.cpp Matrix.cpp + Simplex.cpp DEPENDS MLIRBuiltinLocationAttributesIncGen diff --git a/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp b/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp new file mode 100644 --- /dev/null +++ b/mlir/lib/Analysis/Presburger/IntegerPolyhedron.cpp @@ -0,0 +1,220 @@ +//===- IntegerPolyhedron.cpp - MLIR IntegerPolyhedron Class ---------------===// +// +// 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 +// +//===----------------------------------------------------------------------===// +// +// A class to represent an integer polyhedron. +// +//===----------------------------------------------------------------------===// + +#include "mlir/Analysis/Presburger/IntegerPolyhedron.h" + +using namespace mlir; + +std::unique_ptr IntegerPolyhedron::clone() const { + return std::make_unique(*this); +} + +void IntegerPolyhedron::reset(unsigned numReservedInequalities, + unsigned numReservedEqualities, + unsigned newNumReservedCols, unsigned newNumDims, + unsigned newNumSymbols, unsigned newNumLocals) { + assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 && + "minimum 1 column"); + *this = IntegerPolyhedron(numReservedInequalities, numReservedEqualities, + newNumReservedCols, newNumDims, newNumSymbols, + newNumLocals); +} + +void IntegerPolyhedron::reset(unsigned newNumDims, unsigned newNumSymbols, + unsigned newNumLocals) { + reset(0, 0, newNumDims + newNumSymbols + newNumLocals + 1, newNumDims, + newNumSymbols, newNumLocals); +} + +void IntegerPolyhedron::append(const IntegerPolyhedron &other) { + assert(other.getNumCols() == getNumCols()); + assert(other.getNumDimIds() == getNumDimIds()); + assert(other.getNumSymbolIds() == getNumSymbolIds()); + + inequalities.reserveRows(inequalities.getNumRows() + + other.getNumInequalities()); + equalities.reserveRows(equalities.getNumRows() + other.getNumEqualities()); + + for (unsigned r = 0, e = other.getNumInequalities(); r < e; r++) { + addInequality(other.getInequality(r)); + } + for (unsigned r = 0, e = other.getNumEqualities(); r < e; r++) { + addEquality(other.getEquality(r)); + } +} + +unsigned IntegerPolyhedron::insertDimId(unsigned pos, unsigned num) { + return insertId(IdKind::Dimension, pos, num); +} + +unsigned IntegerPolyhedron::insertSymbolId(unsigned pos, unsigned num) { + return insertId(IdKind::Symbol, pos, num); +} + +unsigned IntegerPolyhedron::insertLocalId(unsigned pos, unsigned num) { + return insertId(IdKind::Local, pos, num); +} + +unsigned IntegerPolyhedron::insertId(IdKind kind, unsigned pos, unsigned num) { + assertAtMostNumIdKind(pos, kind); + + unsigned absolutePos = getIdKindOffset(kind) + pos; + if (kind == IdKind::Dimension) + numDims += num; + else if (kind == IdKind::Symbol) + numSymbols += num; + numIds += num; + + inequalities.insertColumns(absolutePos, num); + equalities.insertColumns(absolutePos, num); + + return absolutePos; +} + +unsigned IntegerPolyhedron::appendDimId(unsigned num) { + unsigned pos = getNumDimIds(); + insertId(IdKind::Dimension, pos, num); + return pos; +} + +unsigned IntegerPolyhedron::appendSymbolId(unsigned num) { + unsigned pos = getNumSymbolIds(); + insertId(IdKind::Symbol, pos, num); + return pos; +} + +unsigned IntegerPolyhedron::appendLocalId(unsigned num) { + unsigned pos = getNumLocalIds(); + insertId(IdKind::Local, pos, num); + return pos; +} + +void IntegerPolyhedron::addEquality(ArrayRef eq) { + assert(eq.size() == getNumCols()); + unsigned row = equalities.appendExtraRow(); + for (unsigned i = 0, e = eq.size(); i < e; ++i) + equalities(row, i) = eq[i]; +} + +void IntegerPolyhedron::addInequality(ArrayRef inEq) { + assert(inEq.size() == getNumCols()); + unsigned row = inequalities.appendExtraRow(); + for (unsigned i = 0, e = inEq.size(); i < e; ++i) + inequalities(row, i) = inEq[i]; +} + +void IntegerPolyhedron::removeId(IdKind kind, unsigned pos) { + removeIdRange(kind, pos, pos + 1); +} + +void IntegerPolyhedron::removeId(unsigned pos) { removeIdRange(pos, pos + 1); } + +void IntegerPolyhedron::removeIdRange(IdKind kind, unsigned idStart, + unsigned idLimit) { + assertAtMostNumIdKind(idLimit, kind); + removeIdRange(getIdKindOffset(kind) + idStart, + getIdKindOffset(kind) + idLimit); +} + +void IntegerPolyhedron::removeIdRange(unsigned idStart, unsigned idLimit) { + assert(idLimit < getNumCols() && "invalid id limit"); + + if (idStart >= idLimit) + return; + + // We are going to be removing one or more identifiers from the range. + assert(idStart < numIds && "invalid idStart position"); + + // TODO: Make 'removeIdRange' a lambda called from here. + // Remove eliminated identifiers from the constraints.. + equalities.removeColumns(idStart, idLimit - idStart); + inequalities.removeColumns(idStart, idLimit - idStart); + + // Update members numDims, numSymbols and numIds. + unsigned numDimsEliminated = 0; + unsigned numLocalsEliminated = 0; + unsigned numColsEliminated = idLimit - idStart; + if (idStart < numDims) { + numDimsEliminated = std::min(numDims, idLimit) - idStart; + } + // Check how many local id's were removed. Note that our identifier order is + // [dims, symbols, locals]. Local id start at position numDims + numSymbols. + if (idLimit > numDims + numSymbols) { + numLocalsEliminated = std::min( + idLimit - std::max(idStart, numDims + numSymbols), getNumLocalIds()); + } + unsigned numSymbolsEliminated = + numColsEliminated - numDimsEliminated - numLocalsEliminated; + + numDims -= numDimsEliminated; + numSymbols -= numSymbolsEliminated; + numIds = numIds - numColsEliminated; +} + +void IntegerPolyhedron::removeEquality(unsigned pos) { + equalities.removeRow(pos); +} + +void IntegerPolyhedron::removeInequality(unsigned pos) { + inequalities.removeRow(pos); +} + +void IntegerPolyhedron::removeEqualityRange(unsigned begin, unsigned end) { + if (begin >= end) + return; + equalities.removeRows(begin, end - begin); +} + +void IntegerPolyhedron::removeInequalityRange(unsigned begin, unsigned end) { + if (begin >= end) + return; + inequalities.removeRows(begin, end - begin); +} + +void IntegerPolyhedron::swapId(unsigned posA, unsigned posB) { + assert(posA < getNumIds() && "invalid position A"); + assert(posB < getNumIds() && "invalid position B"); + + if (posA == posB) + return; + + for (unsigned r = 0, e = getNumInequalities(); r < e; r++) + std::swap(atIneq(r, posA), atIneq(r, posB)); + for (unsigned r = 0, e = getNumEqualities(); r < e; r++) + std::swap(atEq(r, posA), atEq(r, posB)); +} + +unsigned IntegerPolyhedron::getIdKindOffset(IdKind kind) const { + if (kind == IdKind::Dimension) + return 0; + if (kind == IdKind::Symbol) + return getNumDimIds(); + if (kind == IdKind::Local) + return getNumDimAndSymbolIds(); + llvm_unreachable("IdKind expected to be Dimension, Symbol or Local!"); +} + +void IntegerPolyhedron::assertAtMostNumIdKind(unsigned val, IdKind kind) const { + if (kind == IdKind::Dimension) + assert(val <= getNumDimIds()); + else if (kind == IdKind::Symbol) + assert(val <= getNumSymbolIds()); + else if (kind == IdKind::Local) + assert(val <= getNumLocalIds()); + else + llvm_unreachable("IdKind expected to be Dimension, Symbol or Local!"); +} + +void IntegerPolyhedron::clearConstraints() { + equalities.resizeVertically(0); + inequalities.resizeVertically(0); +} diff --git a/mlir/unittests/Analysis/AffineStructuresTest.cpp b/mlir/unittests/Analysis/AffineStructuresTest.cpp --- a/mlir/unittests/Analysis/AffineStructuresTest.cpp +++ b/mlir/unittests/Analysis/AffineStructuresTest.cpp @@ -591,58 +591,6 @@ EXPECT_EQ(fac.atIneq(1, 2), 2); } -TEST(FlatAffineConstraintsTest, removeInequality) { - FlatAffineConstraints fac = - makeFACFromConstraints(1, {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}}, {}); - - fac.removeInequalityRange(0, 0); - EXPECT_EQ(fac.getNumInequalities(), 5u); - - fac.removeInequalityRange(1, 3); - EXPECT_EQ(fac.getNumInequalities(), 3u); - EXPECT_THAT(fac.getInequality(0), ElementsAre(0, 0)); - EXPECT_THAT(fac.getInequality(1), ElementsAre(3, 3)); - EXPECT_THAT(fac.getInequality(2), ElementsAre(4, 4)); - - fac.removeInequality(1); - EXPECT_EQ(fac.getNumInequalities(), 2u); - EXPECT_THAT(fac.getInequality(0), ElementsAre(0, 0)); - EXPECT_THAT(fac.getInequality(1), ElementsAre(4, 4)); -} - -TEST(FlatAffineConstraintsTest, removeEquality) { - FlatAffineConstraints fac = - makeFACFromConstraints(1, {}, {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}}); - - fac.removeEqualityRange(0, 0); - EXPECT_EQ(fac.getNumEqualities(), 5u); - - fac.removeEqualityRange(1, 3); - EXPECT_EQ(fac.getNumEqualities(), 3u); - EXPECT_THAT(fac.getEquality(0), ElementsAre(0, 0)); - EXPECT_THAT(fac.getEquality(1), ElementsAre(3, 3)); - EXPECT_THAT(fac.getEquality(2), ElementsAre(4, 4)); - - fac.removeEquality(1); - EXPECT_EQ(fac.getNumEqualities(), 2u); - EXPECT_THAT(fac.getEquality(0), ElementsAre(0, 0)); - EXPECT_THAT(fac.getEquality(1), ElementsAre(4, 4)); -} - -TEST(FlatAffineConstraintsTest, clearConstraints) { - FlatAffineConstraints fac = makeFACFromConstraints(1, {}, {}); - - fac.addInequality({1, 0}); - EXPECT_EQ(fac.atIneq(0, 0), 1); - EXPECT_EQ(fac.atIneq(0, 1), 0); - - fac.clearConstraints(); - - fac.addInequality({1, 0}); - EXPECT_EQ(fac.atIneq(0, 0), 1); - EXPECT_EQ(fac.atIneq(0, 1), 0); -} - /// Check if the expected division representation of local variables matches the /// computed representation. The expected division representation is given as /// a vector of expressions set in `expectedDividends` and the corressponding @@ -723,24 +671,6 @@ checkDivisionRepresentation(fac, divisions, denoms); } -TEST(FlatAffineConstraintsTest, removeIdRange) { - FlatAffineConstraints fac(3, 2, 1); - - fac.addInequality({10, 11, 12, 20, 21, 30, 40}); - fac.removeId(FlatAffineConstraints::IdKind::Symbol, 1); - EXPECT_THAT(fac.getInequality(0), - testing::ElementsAre(10, 11, 12, 20, 30, 40)); - - fac.removeIdRange(FlatAffineConstraints::IdKind::Dimension, 0, 2); - EXPECT_THAT(fac.getInequality(0), testing::ElementsAre(12, 20, 30, 40)); - - fac.removeIdRange(FlatAffineConstraints::IdKind::Local, 1, 1); - EXPECT_THAT(fac.getInequality(0), testing::ElementsAre(12, 20, 30, 40)); - - fac.removeIdRange(FlatAffineConstraints::IdKind::Local, 0, 1); - EXPECT_THAT(fac.getInequality(0), testing::ElementsAre(12, 20, 40)); -} - TEST(FlatAffineConstraintsTest, simplifyLocalsTest) { // (x) : (exists y: 2x + y = 1 and y = 2). FlatAffineConstraints fac(1, 0, 1); diff --git a/mlir/unittests/Analysis/Presburger/CMakeLists.txt b/mlir/unittests/Analysis/Presburger/CMakeLists.txt --- a/mlir/unittests/Analysis/Presburger/CMakeLists.txt +++ b/mlir/unittests/Analysis/Presburger/CMakeLists.txt @@ -1,4 +1,5 @@ add_mlir_unittest(MLIRPresburgerTests + IntegerPolyhedronTest.cpp MatrixTest.cpp SimplexTest.cpp ) diff --git a/mlir/unittests/Analysis/Presburger/IntegerPolyhedronTest.cpp b/mlir/unittests/Analysis/Presburger/IntegerPolyhedronTest.cpp new file mode 100644 --- /dev/null +++ b/mlir/unittests/Analysis/Presburger/IntegerPolyhedronTest.cpp @@ -0,0 +1,103 @@ +//===- IntegerPolyhedron.cpp - Tests for IntegerPolyhedron class ----------===// +// +// 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/IntegerPolyhedron.h" + +#include +#include + +namespace mlir { + +using testing::ElementsAre; + +/// Construct a IntegerPolyhedron from a set of inequality and +/// equality constraints. +static IntegerPolyhedron +makeSetFromConstraints(unsigned ids, ArrayRef> ineqs, + ArrayRef> eqs, + unsigned syms = 0) { + IntegerPolyhedron set(ineqs.size(), eqs.size(), ids + 1, ids - syms, syms, + /*numLocals=*/0); + for (const auto &eq : eqs) + set.addEquality(eq); + for (const auto &ineq : ineqs) + set.addInequality(ineq); + return set; +} + +TEST(IntegerPolyhedronTest, removeInequality) { + IntegerPolyhedron set = + makeSetFromConstraints(1, {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}}, {}); + + set.removeInequalityRange(0, 0); + EXPECT_EQ(set.getNumInequalities(), 5u); + + set.removeInequalityRange(1, 3); + EXPECT_EQ(set.getNumInequalities(), 3u); + EXPECT_THAT(set.getInequality(0), ElementsAre(0, 0)); + EXPECT_THAT(set.getInequality(1), ElementsAre(3, 3)); + EXPECT_THAT(set.getInequality(2), ElementsAre(4, 4)); + + set.removeInequality(1); + EXPECT_EQ(set.getNumInequalities(), 2u); + EXPECT_THAT(set.getInequality(0), ElementsAre(0, 0)); + EXPECT_THAT(set.getInequality(1), ElementsAre(4, 4)); +} + +TEST(IntegerPolyhedronTest, removeEquality) { + IntegerPolyhedron set = + makeSetFromConstraints(1, {}, {{0, 0}, {1, 1}, {2, 2}, {3, 3}, {4, 4}}); + + set.removeEqualityRange(0, 0); + EXPECT_EQ(set.getNumEqualities(), 5u); + + set.removeEqualityRange(1, 3); + EXPECT_EQ(set.getNumEqualities(), 3u); + EXPECT_THAT(set.getEquality(0), ElementsAre(0, 0)); + EXPECT_THAT(set.getEquality(1), ElementsAre(3, 3)); + EXPECT_THAT(set.getEquality(2), ElementsAre(4, 4)); + + set.removeEquality(1); + EXPECT_EQ(set.getNumEqualities(), 2u); + EXPECT_THAT(set.getEquality(0), ElementsAre(0, 0)); + EXPECT_THAT(set.getEquality(1), ElementsAre(4, 4)); +} + +TEST(IntegerPolyhedronTest, clearConstraints) { + IntegerPolyhedron set = makeSetFromConstraints(1, {}, {}); + + set.addInequality({1, 0}); + EXPECT_EQ(set.atIneq(0, 0), 1); + EXPECT_EQ(set.atIneq(0, 1), 0); + + set.clearConstraints(); + + set.addInequality({1, 0}); + EXPECT_EQ(set.atIneq(0, 0), 1); + EXPECT_EQ(set.atIneq(0, 1), 0); +} + +TEST(IntegerPolyhedronTest, removeIdRange) { + IntegerPolyhedron set(3, 2, 1); + + set.addInequality({10, 11, 12, 20, 21, 30, 40}); + set.removeId(IntegerPolyhedron::IdKind::Symbol, 1); + EXPECT_THAT(set.getInequality(0), + testing::ElementsAre(10, 11, 12, 20, 30, 40)); + + set.removeIdRange(IntegerPolyhedron::IdKind::Dimension, 0, 2); + EXPECT_THAT(set.getInequality(0), testing::ElementsAre(12, 20, 30, 40)); + + set.removeIdRange(IntegerPolyhedron::IdKind::Local, 1, 1); + EXPECT_THAT(set.getInequality(0), testing::ElementsAre(12, 20, 30, 40)); + + set.removeIdRange(IntegerPolyhedron::IdKind::Local, 0, 1); + EXPECT_THAT(set.getInequality(0), testing::ElementsAre(12, 20, 40)); +} + +} // namespace mlir