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 @@ -14,6 +14,7 @@ #define MLIR_ANALYSIS_AFFINESTRUCTURES_H #include "mlir/Analysis/Presburger/Matrix.h" +#include "mlir/Analysis/Presburger/PresburgerBasicSet.h" #include "mlir/IR/AffineExpr.h" #include "mlir/IR/OpDefinition.h" #include "mlir/Support/LogicalResult.h" @@ -56,36 +57,29 @@ /// that some floordiv combinations are converted to mod's by AffineExpr /// construction. /// -class FlatAffineConstraints { +class FlatAffineConstraints : public PresburgerBasicSet { 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); - } + : PresburgerBasicSet(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) {} + : PresburgerBasicSet(/*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); @@ -447,19 +339,10 @@ /// `this` and `other`. 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. @@ -530,27 +413,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/PresburgerBasicSet.h b/mlir/include/mlir/Analysis/Presburger/PresburgerBasicSet.h new file mode 100644 --- /dev/null +++ b/mlir/include/mlir/Analysis/Presburger/PresburgerBasicSet.h @@ -0,0 +1,216 @@ +//===- PresburgerBasicSet.h - MLIR PresburgerBasicSet 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_PRESBURGERBASICSET_H +#define MLIR_ANALYSIS_PRESBURGER_PRESBURGERBASICSET_H + +#include "mlir/Analysis/Presburger/Matrix.h" + +namespace mlir { + +/// A basic set 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 +/// polytope. 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, a basic set with symbolic variables is like a family of +/// basic sets indexed by the symbolic variables. +/// +/// Local: Local variables correspond to local/internal variables used to +/// represent existential quantification. For example, consider the set: (x) : +/// (exists q : 1 <= x <= 10, x = 3y). An assignment to symbolic and dimension +/// variables is valid if there exists some assignment to the existentially +/// quantified variables satisfying these constraints. For this example, the set +/// is equivalent to {3, 6, 9}. +/// +class PresburgerBasicSet { +public: + /// Kind of identifier (column). + enum IdKind { Dimension, Symbol, Local }; + + /// Constructs a constraint system reserving memory for the specified number + /// of constraints and identifiers. + PresburgerBasicSet(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. + PresburgerBasicSet(unsigned numDims = 0, unsigned numSymbols = 0, + unsigned numLocals = 0) + : PresburgerBasicSet(/*numReservedInequalities=*/0, + /*numReservedEqualities=*/0, + /*numReservedCols=*/numDims + numSymbols + + numLocals + 1, + numDims, numSymbols, numLocals) {} + + virtual ~PresburgerBasicSet() = 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 PresburgerBasicSet &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_PRESBURGERBASICSET_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) { + : PresburgerBasicSet(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); @@ -2426,20 +2277,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()); @@ -2513,19 +2350,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]); @@ -2547,27 +2371,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 @@ -2995,10 +2798,6 @@ } } -void FlatAffineConstraints::removeId(unsigned pos) { - removeIdRange(pos, pos + 1); -} - static std::pair getNewNumDimsSymbols(unsigned pos, const FlatAffineConstraints &cst) { unsigned numDims = cst.getNumDimIds(); @@ -3281,11 +3080,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 Matrix.cpp + PresburgerBasicSet.cpp DEPENDS MLIRBuiltinLocationAttributesIncGen diff --git a/mlir/lib/Analysis/Presburger/PresburgerBasicSet.cpp b/mlir/lib/Analysis/Presburger/PresburgerBasicSet.cpp new file mode 100644 --- /dev/null +++ b/mlir/lib/Analysis/Presburger/PresburgerBasicSet.cpp @@ -0,0 +1,223 @@ +//===- PresburgerBasicSet.h - MLIR PresburgerBasicSet 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. +// +//===----------------------------------------------------------------------===// + +#include "mlir/Analysis/Presburger/PresburgerBasicSet.h" + +namespace mlir { + +std::unique_ptr PresburgerBasicSet::clone() const { + return std::make_unique(*this); +} + +void PresburgerBasicSet::reset(unsigned numReservedInequalities, + unsigned numReservedEqualities, + unsigned newNumReservedCols, unsigned newNumDims, + unsigned newNumSymbols, unsigned newNumLocals) { + assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 && + "minimum 1 column"); + *this = PresburgerBasicSet(numReservedInequalities, numReservedEqualities, + newNumReservedCols, newNumDims, newNumSymbols, + newNumLocals); +} + +void PresburgerBasicSet::reset(unsigned newNumDims, unsigned newNumSymbols, + unsigned newNumLocals) { + reset(0, 0, newNumDims + newNumSymbols + newNumLocals + 1, newNumDims, + newNumSymbols, newNumLocals); +} + +void PresburgerBasicSet::append(const PresburgerBasicSet &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 PresburgerBasicSet::insertDimId(unsigned pos, unsigned num) { + return insertId(IdKind::Dimension, pos, num); +} + +unsigned PresburgerBasicSet::insertSymbolId(unsigned pos, unsigned num) { + return insertId(IdKind::Symbol, pos, num); +} + +unsigned PresburgerBasicSet::insertLocalId(unsigned pos, unsigned num) { + return insertId(IdKind::Local, pos, num); +} + +unsigned PresburgerBasicSet::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 PresburgerBasicSet::appendDimId(unsigned num) { + unsigned pos = getNumDimIds(); + insertId(IdKind::Dimension, pos, num); + return pos; +} + +unsigned PresburgerBasicSet::appendSymbolId(unsigned num) { + unsigned pos = getNumSymbolIds(); + insertId(IdKind::Symbol, pos, num); + return pos; +} + +unsigned PresburgerBasicSet::appendLocalId(unsigned num) { + unsigned pos = getNumLocalIds(); + insertId(IdKind::Local, pos, num); + return pos; +} + +void PresburgerBasicSet::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 PresburgerBasicSet::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 PresburgerBasicSet::removeId(IdKind kind, unsigned pos) { + removeIdRange(kind, pos, pos + 1); +} + +void PresburgerBasicSet::removeId(unsigned pos) { removeIdRange(pos, pos + 1); } + +void PresburgerBasicSet::removeIdRange(IdKind kind, unsigned idStart, + unsigned idLimit) { + assertAtMostNumIdKind(idLimit, kind); + removeIdRange(getIdKindOffset(kind) + idStart, + getIdKindOffset(kind) + idLimit); +} + +void PresburgerBasicSet::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 PresburgerBasicSet::removeEquality(unsigned pos) { + equalities.removeRow(pos); +} + +void PresburgerBasicSet::removeInequality(unsigned pos) { + inequalities.removeRow(pos); +} + +void PresburgerBasicSet::removeEqualityRange(unsigned begin, unsigned end) { + if (begin >= end) + return; + equalities.removeRows(begin, end - begin); +} + +void PresburgerBasicSet::removeInequalityRange(unsigned begin, unsigned end) { + if (begin >= end) + return; + inequalities.removeRows(begin, end - begin); +} + +void PresburgerBasicSet::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 PresburgerBasicSet::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 PresburgerBasicSet::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 PresburgerBasicSet::clearConstraints() { + equalities.resizeVertically(0); + inequalities.resizeVertically(0); +} + +} // namespace mlir