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 @@ -67,13 +67,12 @@ unsigned numReservedCols, unsigned numDims = 0, unsigned numSymbols = 0, unsigned numLocals = 0, ArrayRef> idArgs = {}) - : numReservedCols(numReservedCols), numDims(numDims), - numSymbols(numSymbols) { - assert(numReservedCols >= numDims + numSymbols + 1); - assert(idArgs.empty() || idArgs.size() == numDims + numSymbols + numLocals); - equalities.reserve(numReservedCols * numReservedEqualities); - inequalities.reserve(numReservedCols * numReservedInequalities); - numIds = numDims + numSymbols + numLocals; + : numIds(numDims + numSymbols + numLocals), numDims(numDims), + numSymbols(numSymbols), + equalities(0, numIds + 1, numReservedEqualities, numReservedCols), + inequalities(0, numIds + 1, numReservedInequalities, numReservedCols) { + assert(numReservedCols >= numDims + numSymbols + numLocals + 1); + assert(idArgs.empty() || idArgs.size() == numIds); ids.reserve(numReservedCols); if (idArgs.empty()) ids.resize(numIds, None); @@ -86,17 +85,8 @@ FlatAffineConstraints(unsigned numDims = 0, unsigned numSymbols = 0, unsigned numLocals = 0, ArrayRef> idArgs = {}) - : numReservedCols(numDims + numSymbols + numLocals + 1), numDims(numDims), - numSymbols(numSymbols) { - assert(numReservedCols >= numDims + numSymbols + 1); - assert(idArgs.empty() || idArgs.size() == numDims + numSymbols + numLocals); - numIds = numDims + numSymbols + numLocals; - ids.reserve(numIds); - if (idArgs.empty()) - ids.resize(numIds, None); - else - ids.append(idArgs.begin(), idArgs.end()); - } + : FlatAffineConstraints(0, 0, numDims + numSymbols + numLocals + 1, + numDims, numSymbols, numLocals, idArgs) {} /// Return a system with no constraints, i.e., one which is satisfied by all /// points. @@ -113,8 +103,6 @@ /// Creates an affine constraint system from an IntegerSet. explicit FlatAffineConstraints(IntegerSet set); - FlatAffineConstraints(const FlatAffineConstraints &other); - FlatAffineConstraints(ArrayRef avmRef, IntegerSet set); @@ -173,51 +161,38 @@ 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 * numReservedCols + j]; - } - inline int64_t &atEq(unsigned i, unsigned j) { - return equalities[i * numReservedCols + j]; - } + 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); } inline int64_t atIneq(unsigned i, unsigned j) const { - return inequalities[i * numReservedCols + j]; + return inequalities(i, j); } - inline int64_t &atIneq(unsigned i, unsigned j) { - return inequalities[i * numReservedCols + 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 { - assert(equalities.size() % numReservedCols == 0 && - "inconsistent equality buffer size"); - return equalities.size() / numReservedCols; - } + inline unsigned getNumEqualities() const { return equalities.getNumRows(); } inline unsigned getNumInequalities() const { - assert(inequalities.size() % numReservedCols == 0 && - "inconsistent inequality buffer size"); - return inequalities.size() / numReservedCols; + return inequalities.getNumRows(); } inline unsigned getNumReservedEqualities() const { - return equalities.capacity() / numReservedCols; + return equalities.getNumReservedRows(); } inline unsigned getNumReservedInequalities() const { - return inequalities.capacity() / numReservedCols; + return inequalities.getNumReservedRows(); } inline ArrayRef getEquality(unsigned idx) const { - return ArrayRef(&equalities[idx * numReservedCols], getNumCols()); + return equalities.getRow(idx); } inline ArrayRef getInequality(unsigned idx) const { - return ArrayRef(&inequalities[idx * numReservedCols], - getNumCols()); + return inequalities.getRow(idx); } /// Adds constraints (lower and upper bounds) for the specified 'affine.for' @@ -649,16 +624,6 @@ /// arrays as needed. void removeIdRange(unsigned idStart, unsigned idLimit); - /// Coefficients of affine equalities (in == 0 form). - SmallVector equalities; - - /// Coefficients of affine inequalities (in >= 0 form). - SmallVector inequalities; - - /// Number of columns reserved. Actual ones in used are returned by - /// getNumCols(). - unsigned numReservedCols; - /// Total number of identifiers. unsigned numIds; @@ -669,6 +634,12 @@ /// analysis). unsigned numSymbols; + /// Coefficients of affine equalities (in == 0 form). + Matrix equalities; + + /// Coefficients of affine inequalities (in >= 0 form). + Matrix inequalities; + /// Values corresponding to the (column) identifiers of this constraint /// system appearing in the order the identifiers correspond to columns. /// Temporary ones or those that aren't associated to any Value are set to diff --git a/mlir/include/mlir/Analysis/Presburger/Matrix.h b/mlir/include/mlir/Analysis/Presburger/Matrix.h --- a/mlir/include/mlir/Analysis/Presburger/Matrix.h +++ b/mlir/include/mlir/Analysis/Presburger/Matrix.h @@ -22,16 +22,26 @@ namespace mlir { -/// This is a simple class to represent a resizable matrix. +/// This is a class to represent a resizable matrix. /// -/// The data is stored in the form of a vector of vectors. +/// More columns and rows can be reserved than are currently used. The data is +/// stored as a single 1D array. The reserved columns are actually present in +/// the array, but are just not used. So the element at (i, j) is stored at +/// data[i*nReservedColumns + j]. The reserved but unused columns have all zero +/// values. The reserved rows are just reserved space in the underlying +/// SmallVector's capacity. class Matrix { public: Matrix() = delete; /// Construct a matrix with the specified number of rows and columns. - /// Initially, the values are default initialized. - Matrix(unsigned rows, unsigned columns); + /// The number of reserved rows and columns will be at least the number + /// specified, and will always be sufficient to accomodate the number of rows + /// and columns specified. + /// + /// Initially, the entries are initialized to ero. + Matrix(unsigned rows, unsigned columns, unsigned reservedRows = 0, + unsigned reservedColumns = 0); /// Return the identity matrix of the specified dimension. static Matrix identity(unsigned dimension); @@ -52,9 +62,48 @@ unsigned getNumColumns() const; + unsigned getNumReservedColumns() const; + unsigned getNumReservedRows() const; + + // Reserve enough space to resize to the specified number of rows without + // reallocations. + void reserveRows(unsigned rows); + /// Get an ArrayRef corresponding to the specified row. ArrayRef getRow(unsigned row) const; + // Insert columns having positions pos, pos + 1, ... pos + count - 1. + // Columns that were at positions 0 to pos - 1 will stay where they are; + // columns that were at positions pos to nColumns - 1 will be pushed to the + // right. pos should be at most nColumns. + void insertColumns(unsigned pos, unsigned count); + void insertColumn(unsigned pos); + + // Insert rows having positions pos, pos + 1, ... pos + count - 1. + // Rows that were at positions 0 to pos - 1 will stay where they are; + // rows that were at positions pos to nColumns - 1 will be pushed to the + // right. pos should be at most nRows. + void insertRows(unsigned pos, unsigned count); + void insertRow(unsigned pos); + + // Remove the columns having positions pos, pos + 1, ... pos + count - 1. + // Rows that were at positions 0 to pos - 1 will stay where they are; + // columns that were at positions pos + count - 1 or later will be pushed to + // the right. The columns to be deleted must be valid rows: pos + count - 1 + // must be at most nColumns - 1. + void removeColumns(unsigned pos, unsigned count); + void removeColumn(unsigned pos); + + // Remove the rows having positions pos, pos + 1, ... pos + count - 1. + // Rows that were at positions 0 to pos - 1 will stay where they are; + // rows that were at positions pos + count - 1 or later will be pushed to the + // right. The rows to be deleted must be valid rows: pos + count - 1 must be + // at most nRows - 1. + void removeRows(unsigned pos, unsigned count); + void removeRow(unsigned pos); + + void copyRow(unsigned sourceRow, unsigned targetRow); + /// Add `scale` multiples of the source row to the target row. void addToRow(unsigned sourceRow, unsigned targetRow, int64_t scale); @@ -69,14 +118,23 @@ /// initialized. void resizeVertically(unsigned newNRows); + /// Clear the array. This sets the size to zero rows and zero columns. + void clear(); + + // Add an extra row at the bottom of the matrix and return its position. + unsigned appendExtraRow(); + /// Print the matrix. void print(raw_ostream &os) const; void dump() const; + bool hasConsistentState() const; + private: - unsigned nRows, nColumns; + unsigned nRows, nColumns, nReservedColumns; - /// Stores the data. data.size() is equal to nRows * nColumns. + /// Stores the data. data.size() is equal to nRows * nReservedColumns. + /// data.capacity() / nReservedColumns is the number of reserved rows. SmallVector data; }; 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 @@ -144,31 +144,7 @@ // FlatAffineConstraints. //===----------------------------------------------------------------------===// -// Copy constructor. -FlatAffineConstraints::FlatAffineConstraints( - const FlatAffineConstraints &other) { - numReservedCols = other.numReservedCols; - numDims = other.getNumDimIds(); - numSymbols = other.getNumSymbolIds(); - numIds = other.getNumIds(); - - auto otherIds = other.getIds(); - ids.reserve(numReservedCols); - ids.append(otherIds.begin(), otherIds.end()); - - unsigned numReservedEqualities = other.getNumReservedEqualities(); - unsigned numReservedInequalities = other.getNumReservedInequalities(); - - equalities.reserve(numReservedEqualities * numReservedCols); - inequalities.reserve(numReservedInequalities * numReservedCols); - - 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)); - } -} +// QUESTION: Is there a reason the default copy constructor was not used? // Clones this object. std::unique_ptr FlatAffineConstraints::clone() const { @@ -177,11 +153,10 @@ // Construct from an IntegerSet. FlatAffineConstraints::FlatAffineConstraints(IntegerSet set) - : numReservedCols(set.getNumInputs() + 1), - numIds(set.getNumDims() + set.getNumSymbols()), numDims(set.getNumDims()), - numSymbols(set.getNumSymbols()) { - equalities.reserve(set.getNumEqualities() * numReservedCols); - inequalities.reserve(set.getNumInequalities() * numReservedCols); + : 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) { ids.resize(numIds, None); // Flatten expressions and add them to the constraint system. @@ -217,22 +192,15 @@ ArrayRef idArgs) { assert(newNumReservedCols >= newNumDims + newNumSymbols + newNumLocals + 1 && "minimum 1 column"); - numReservedCols = newNumReservedCols; - numDims = newNumDims; - numSymbols = newNumSymbols; - numIds = numDims + numSymbols + newNumLocals; - assert(idArgs.empty() || idArgs.size() == numIds); + SmallVector, 8> newIds; + if (idArgs.empty()) + newIds.resize(numIds, None); + else + newIds.assign(idArgs.begin(), idArgs.end()); - clearConstraints(); - if (numReservedEqualities >= 1) - equalities.reserve(newNumReservedCols * numReservedEqualities); - if (numReservedInequalities >= 1) - inequalities.reserve(newNumReservedCols * numReservedInequalities); - if (idArgs.empty()) { - ids.resize(numIds, None); - } else { - ids.assign(idArgs.begin(), idArgs.end()); - } + *this = FlatAffineConstraints(numReservedInequalities, numReservedEqualities, + newNumReservedCols, newNumDims, newNumSymbols, + newNumLocals, newIds); } void FlatAffineConstraints::reset(unsigned newNumDims, unsigned newNumSymbols, @@ -247,10 +215,9 @@ assert(other.getNumDimIds() == getNumDimIds()); assert(other.getNumSymbolIds() == getNumSymbolIds()); - inequalities.reserve(inequalities.size() + - other.getNumInequalities() * numReservedCols); - equalities.reserve(equalities.size() + - other.getNumEqualities() * numReservedCols); + 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)); @@ -282,17 +249,7 @@ else assert(pos <= getNumLocalIds()); - unsigned oldNumReservedCols = numReservedCols; - - // Check if a resize is necessary. - if (getNumCols() + 1 > numReservedCols) { - equalities.resize(getNumEqualities() * (getNumCols() + 1)); - inequalities.resize(getNumInequalities() * (getNumCols() + 1)); - numReservedCols++; - } - int absolutePos; - if (kind == IdKind::Dimension) { absolutePos = pos; numDims++; @@ -304,35 +261,8 @@ } numIds++; - // Note that getNumCols() now will already return the new size, which will be - // at least one. - int numInequalities = static_cast(getNumInequalities()); - int numEqualities = static_cast(getNumEqualities()); - int numCols = static_cast(getNumCols()); - for (int r = numInequalities - 1; r >= 0; r--) { - for (int c = numCols - 2; c >= 0; c--) { - if (c < absolutePos) - atIneq(r, c) = inequalities[r * oldNumReservedCols + c]; - else - atIneq(r, c + 1) = inequalities[r * oldNumReservedCols + c]; - } - atIneq(r, absolutePos) = 0; - } - - for (int r = numEqualities - 1; r >= 0; r--) { - for (int c = numCols - 2; c >= 0; c--) { - // All values in column absolutePositions < absolutePos have the same - // coordinates in the 2-d view of the coefficient buffer. - if (c < absolutePos) - atEq(r, c) = equalities[r * oldNumReservedCols + c]; - else - // Those at absolutePosition >= absolutePos, get a shifted - // absolutePosition. - atEq(r, c + 1) = equalities[r * oldNumReservedCols + c]; - } - // Initialize added dimension to zero. - atEq(r, absolutePos) = 0; - } + inequalities.insertColumn(absolutePos); + equalities.insertColumn(absolutePos); // If an 'id' is provided, insert it; otherwise use None. if (id) @@ -840,9 +770,9 @@ } bool FlatAffineConstraints::hasConsistentState() const { - if (inequalities.size() != getNumInequalities() * numReservedCols) + if (!inequalities.hasConsistentState()) return false; - if (equalities.size() != getNumEqualities() * numReservedCols) + if (!equalities.hasConsistentState()) return false; if (ids.size() != getNumIds()) return false; @@ -923,31 +853,6 @@ } } -// Remove coefficients in column range [colStart, colLimit) in place. -// This removes in data in the specified column range, and copies any -// remaining valid data into place. -static void shiftColumnsToLeft(FlatAffineConstraints *constraints, - unsigned colStart, unsigned colLimit, - bool isEq) { - assert(colLimit <= constraints->getNumIds()); - if (colLimit <= colStart) - return; - - unsigned numCols = constraints->getNumCols(); - unsigned numRows = isEq ? constraints->getNumEqualities() - : constraints->getNumInequalities(); - unsigned numToEliminate = colLimit - colStart; - for (unsigned r = 0, e = numRows; r < e; ++r) { - for (unsigned c = colLimit; c < numCols; ++c) { - if (isEq) { - constraints->atEq(r, c - numToEliminate) = constraints->atEq(r, c); - } else { - constraints->atIneq(r, c - numToEliminate) = constraints->atIneq(r, c); - } - } - } -} - // Removes identifiers in column range [idStart, idLimit), and copies any // remaining valid data into place, and updates member variables. void FlatAffineConstraints::removeIdRange(unsigned idStart, unsigned idLimit) { @@ -960,11 +865,9 @@ assert(idStart < numIds && "invalid idStart position"); // TODO: Make 'removeIdRange' a lambda called from here. - // Remove eliminated identifiers from equalities. - shiftColumnsToLeft(this, idStart, idLimit, /*isEq=*/true); - - // Remove eliminated identifiers from inequalities. - shiftColumnsToLeft(this, idStart, idLimit, /*isEq=*/false); + // 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; @@ -987,8 +890,6 @@ numIds = numIds - numColsEliminated; ids.erase(ids.begin() + idStart, ids.begin() + idLimit); - - // No resize necessary. numReservedCols remains the same. } /// Returns the position of the identifier that has the minimum FlatAffineConstraints::getLowerAndUpperBound( @@ -2185,60 +2086,45 @@ void FlatAffineConstraints::addEquality(ArrayRef eq) { assert(eq.size() == getNumCols()); - unsigned offset = equalities.size(); - equalities.resize(equalities.size() + numReservedCols); - std::copy(eq.begin(), eq.end(), equalities.begin() + offset); + 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 offset = inequalities.size(); - inequalities.resize(inequalities.size() + numReservedCols); - std::copy(inEq.begin(), inEq.end(), inequalities.begin() + offset); + unsigned row = inequalities.appendExtraRow(); + for (unsigned i = 0, e = inEq.size(); i < e; ++i) + inequalities(row, i) = inEq[i]; } void FlatAffineConstraints::addConstantLowerBound(unsigned pos, int64_t lb) { assert(pos < getNumCols()); - unsigned offset = inequalities.size(); - inequalities.resize(inequalities.size() + numReservedCols); - std::fill(inequalities.begin() + offset, - inequalities.begin() + offset + getNumCols(), 0); - inequalities[offset + pos] = 1; - inequalities[offset + getNumCols() - 1] = -lb; + unsigned row = inequalities.appendExtraRow(); + inequalities(row, pos) = 1; + inequalities(row, getNumCols() - 1) = -lb; } void FlatAffineConstraints::addConstantUpperBound(unsigned pos, int64_t ub) { assert(pos < getNumCols()); - unsigned offset = inequalities.size(); - inequalities.resize(inequalities.size() + numReservedCols); - std::fill(inequalities.begin() + offset, - inequalities.begin() + offset + getNumCols(), 0); - inequalities[offset + pos] = -1; - inequalities[offset + getNumCols() - 1] = ub; + unsigned row = inequalities.appendExtraRow(); + inequalities(row, pos) = 1; + inequalities(row, getNumCols() - 1) = ub; } void FlatAffineConstraints::addConstantLowerBound(ArrayRef expr, int64_t lb) { - assert(expr.size() == getNumCols()); - unsigned offset = inequalities.size(); - inequalities.resize(inequalities.size() + numReservedCols); - std::fill(inequalities.begin() + offset, - inequalities.begin() + offset + getNumCols(), 0); - std::copy(expr.begin(), expr.end(), inequalities.begin() + offset); - inequalities[offset + getNumCols() - 1] += -lb; + addInequality(expr); + inequalities(inequalities.getNumRows() - 1, getNumCols() - 1) += -lb; } void FlatAffineConstraints::addConstantUpperBound(ArrayRef expr, int64_t ub) { assert(expr.size() == getNumCols()); - unsigned offset = inequalities.size(); - inequalities.resize(inequalities.size() + numReservedCols); - std::fill(inequalities.begin() + offset, - inequalities.begin() + offset + getNumCols(), 0); - for (unsigned i = 0, e = getNumCols(); i < e; i++) { - inequalities[offset + i] = -expr[i]; - } - inequalities[offset + getNumCols() - 1] += ub; + unsigned row = inequalities.appendExtraRow(); + for (unsigned i = 0, e = expr.size(); i < e; ++i) + inequalities(row, i) = -expr[i]; + inequalities(inequalities.getNumRows() - 1, getNumCols() - 1) += ub; } /// Adds a new local identifier as the floordiv of an affine function of other @@ -2311,12 +2197,10 @@ /// Sets the specified identifier to a constant value. void FlatAffineConstraints::setIdToConstant(unsigned pos, int64_t val) { - unsigned offset = equalities.size(); - equalities.resize(equalities.size() + numReservedCols); - std::fill(equalities.begin() + offset, - equalities.begin() + offset + getNumCols(), 0); - equalities[offset + pos] = 1; - equalities[offset + getNumCols() - 1] = -val; + equalities.resizeVertically(equalities.getNumRows() + 1); + unsigned row = equalities.getNumRows() - 1; + equalities(row, pos) = 1; + equalities(row, getNumCols() - 1) = -val; } /// Sets the specified identifier to a constant value; asserts if the id is not @@ -2330,29 +2214,11 @@ } void FlatAffineConstraints::removeEquality(unsigned pos) { - unsigned numEqualities = getNumEqualities(); - assert(pos < numEqualities); - unsigned outputIndex = pos * numReservedCols; - unsigned inputIndex = (pos + 1) * numReservedCols; - unsigned numElemsToCopy = (numEqualities - pos - 1) * numReservedCols; - std::copy(equalities.begin() + inputIndex, - equalities.begin() + inputIndex + numElemsToCopy, - equalities.begin() + outputIndex); - assert(equalities.size() >= numReservedCols); - equalities.resize(equalities.size() - numReservedCols); + equalities.removeRow(pos); } void FlatAffineConstraints::removeInequality(unsigned pos) { - unsigned numInequalities = getNumInequalities(); - assert(pos < numInequalities && "invalid position"); - unsigned outputIndex = pos * numReservedCols; - unsigned inputIndex = (pos + 1) * numReservedCols; - unsigned numElemsToCopy = (numInequalities - pos - 1) * numReservedCols; - std::copy(inequalities.begin() + inputIndex, - inequalities.begin() + inputIndex + numElemsToCopy, - inequalities.begin() + outputIndex); - assert(inequalities.size() >= numReservedCols); - inequalities.resize(inequalities.size() - numReservedCols); + inequalities.removeRow(pos); } /// Finds an equality that equates the specified identifier to a constant. @@ -2716,7 +2582,7 @@ // Detect and mark redundant constraints. SmallVector redunIneq(getNumInequalities(), false); for (unsigned r = 0, e = getNumInequalities(); r < e; r++) { - int64_t *rowStart = inequalities.data() + numReservedCols * r; + int64_t *rowStart = &inequalities(r, 0); auto row = ArrayRef(rowStart, getNumCols()); if (isTriviallyValid(r) || !rowSet.insert(row).second) { redunIneq[r] = true; @@ -2745,21 +2611,13 @@ } } - auto copyRow = [&](unsigned src, unsigned dest) { - if (src == dest) - return; - for (unsigned c = 0, e = getNumCols(); c < e; c++) { - atIneq(dest, c) = atIneq(src, c); - } - }; - // Scan to get rid of all rows marked redundant, in-place. unsigned pos = 0; - for (unsigned r = 0, e = getNumInequalities(); r < e; r++) { + for (unsigned r = 0, e = getNumInequalities(); r < e; r++) if (!redunIneq[r]) - copyRow(r, pos++); - } - inequalities.resize(numReservedCols * pos); + inequalities.copyRow(r, pos++); + + inequalities.resizeVertically(pos); // TODO: consider doing this for equalities as well, but probably not worth // the savings. diff --git a/mlir/lib/Analysis/Presburger/Matrix.cpp b/mlir/lib/Analysis/Presburger/Matrix.cpp --- a/mlir/lib/Analysis/Presburger/Matrix.cpp +++ b/mlir/lib/Analysis/Presburger/Matrix.cpp @@ -10,8 +10,14 @@ namespace mlir { -Matrix::Matrix(unsigned rows, unsigned columns) - : nRows(rows), nColumns(columns), data(nRows * nColumns) {} +Matrix::Matrix(unsigned rows, unsigned columns, unsigned reservedRows, + unsigned reservedColumns) + : nRows(rows), nColumns(columns), + nReservedColumns(std::max(nColumns, reservedColumns)), + data(nRows * nReservedColumns) { + // QUESTION: is there no way to reserve in the constructor? + data.reserve(std::max(nRows, reservedRows) * nReservedColumns); +} Matrix Matrix::identity(unsigned dimension) { Matrix matrix(dimension, dimension); @@ -21,15 +27,15 @@ } int64_t &Matrix::at(unsigned row, unsigned column) { - assert(row < getNumRows() && "Row outside of range"); - assert(column < getNumColumns() && "Column outside of range"); - return data[row * nColumns + column]; + assert(row < nRows && "Row outside of range"); + assert(column < nColumns && "Column outside of range"); + return data[row * nReservedColumns + column]; } int64_t Matrix::at(unsigned row, unsigned column) const { - assert(row < getNumRows() && "Row outside of range"); - assert(column < getNumColumns() && "Column outside of range"); - return data[row * nColumns + column]; + assert(row < nRows && "Row outside of range"); + assert(column < nColumns && "Column outside of range"); + return data[row * nReservedColumns + column]; } int64_t &Matrix::operator()(unsigned row, unsigned column) { @@ -44,9 +50,29 @@ unsigned Matrix::getNumColumns() const { return nColumns; } +unsigned Matrix::getNumReservedColumns() const { return nReservedColumns; } + +unsigned Matrix::getNumReservedRows() const { + return data.capacity() / nReservedColumns; +} + +void Matrix::reserveRows(unsigned rows) { + data.reserve(rows * nReservedColumns); +} + +unsigned Matrix::appendExtraRow() { + resizeVertically(nRows + 1); + return nRows - 1; +} + void Matrix::resizeVertically(unsigned newNRows) { nRows = newNRows; - data.resize(nRows * nColumns); + data.resize(nRows * nReservedColumns); +} + +void Matrix::clear() { + nRows = nColumns = 0; + data.clear(); } void Matrix::swapRows(unsigned row, unsigned otherRow) { @@ -68,7 +94,91 @@ } ArrayRef Matrix::getRow(unsigned row) const { - return {&data[row * nColumns], nColumns}; + return {&data[row * nReservedColumns], nColumns}; +} + +namespace { +unsigned nextPowOfTwo(unsigned x) { + unsigned y = 1; + while (y <= x) + y *= 2; + return y; +} +} // anonymous namespace + +void Matrix::insertColumn(unsigned pos) { insertColumns(pos, 1); } +void Matrix::insertColumns(unsigned pos, unsigned count) { + if (count == 0) + return; + assert(pos <= nColumns); + unsigned oldNReservedColumns = nReservedColumns; + if (nColumns + count > nReservedColumns) { + nReservedColumns = nextPowOfTwo(nColumns + count); + data.resize(nRows * nReservedColumns); + } + nColumns += count; + + for (int ri = nRows - 1; ri >= 0; --ri) { + for (int ci = nReservedColumns - 1; ci >= 0; --ci) { + unsigned r = ri; + unsigned c = ci; + int64_t &dest = data[r * nReservedColumns + c]; + if (c >= nColumns) + dest = 0; + else if (c >= pos + count) + dest = data[r * oldNReservedColumns + c - count]; + else if (c >= pos) + dest = 0; + else + dest = data[r * oldNReservedColumns + c]; + } + } +} + +void Matrix::removeColumn(unsigned pos) { removeColumns(pos, 1); } +void Matrix::removeColumns(unsigned pos, unsigned count) { + if (count == 0) + return; + assert(pos + count - 1 <= nColumns); + for (unsigned r = 0; r < nRows; ++r) { + for (unsigned c = pos; c + count < nColumns; ++c) + at(r, c) = at(r, c + count); + for (unsigned c = nColumns - count; c < nColumns; ++c) + at(r, c) = 0; + } + nColumns -= count; +} + +void Matrix::insertRow(unsigned pos) { insertRows(pos, 1); } +void Matrix::insertRows(unsigned pos, unsigned count) { + if (count == 0) + return; + + assert(pos <= nRows); + resizeVertically(nRows + count); + for (int r = nRows - 1; r >= int(pos); --r) + copyRow(r - count, r); + + for (unsigned r = pos; r < pos + count; ++r) + for (unsigned c = 0; c < nColumns; ++c) + at(r, c) = 0; +} + +void Matrix::removeRow(unsigned pos) { removeRows(pos, 1); } +void Matrix::removeRows(unsigned pos, unsigned count) { + if (count == 0) + return; + assert(pos + count - 1 <= nRows); + for (unsigned r = pos; r + count < nRows; ++r) + copyRow(r + count, r); + resizeVertically(nRows - count); +} + +void Matrix::copyRow(unsigned sourceRow, unsigned targetRow) { + if (sourceRow == targetRow) + return; + for (unsigned c = 0; c < nColumns; ++c) + at(targetRow, c) = at(sourceRow, c); } void Matrix::addToRow(unsigned sourceRow, unsigned targetRow, int64_t scale) { @@ -76,7 +186,6 @@ return; for (unsigned col = 0; col < nColumns; ++col) at(targetRow, col) += scale * at(sourceRow, col); - return; } void Matrix::addToColumn(unsigned sourceColumn, unsigned targetColumn, @@ -102,4 +211,18 @@ void Matrix::dump() const { print(llvm::errs()); } +bool Matrix::hasConsistentState() const { + if (data.size() % nReservedColumns != 0) + return false; + if (data.size() / nReservedColumns != nRows) + return false; + if (nColumns > nReservedColumns) + return false; + for (unsigned r = 0; r < nRows; ++r) + for (unsigned c = nColumns; c < nReservedColumns; ++c) + if (data[r * nReservedColumns + c] != 0) + return false; + return true; +} + } // namespace mlir diff --git a/mlir/unittests/Analysis/Presburger/MatrixTest.cpp b/mlir/unittests/Analysis/Presburger/MatrixTest.cpp --- a/mlir/unittests/Analysis/Presburger/MatrixTest.cpp +++ b/mlir/unittests/Analysis/Presburger/MatrixTest.cpp @@ -75,6 +75,7 @@ mat(row, col) = 10 * row + col; mat.resizeVertically(3); + ASSERT_TRUE(mat.hasConsistentState()); EXPECT_EQ(mat.getNumRows(), 3u); EXPECT_EQ(mat.getNumColumns(), 5u); for (unsigned row = 0; row < 3; ++row) @@ -82,6 +83,7 @@ EXPECT_EQ(mat(row, col), int(10 * row + col)); mat.resizeVertically(5); + ASSERT_TRUE(mat.hasConsistentState()); EXPECT_EQ(mat.getNumRows(), 5u); EXPECT_EQ(mat.getNumColumns(), 5u); for (unsigned row = 0; row < 5; ++row) @@ -89,4 +91,79 @@ EXPECT_EQ(mat(row, col), row >= 3 ? 0 : int(10 * row + col)); } +TEST(MatrixTest, insertColumns) { + Matrix mat(5, 5, 5, 10); + EXPECT_EQ(mat.getNumRows(), 5u); + EXPECT_EQ(mat.getNumColumns(), 5u); + for (unsigned row = 0; row < 5; ++row) + for (unsigned col = 0; col < 5; ++col) + mat(row, col) = 10 * row + col; + + mat.insertColumns(3, 2); + ASSERT_TRUE(mat.hasConsistentState()); + EXPECT_EQ(mat.getNumRows(), 5u); + EXPECT_EQ(mat.getNumColumns(), 7u); + for (unsigned row = 0; row < 5; ++row) { + for (unsigned col = 0; col < 7; ++col) { + if (col < 3) + EXPECT_EQ(mat(row, col), int(10 * row + col)); + else if (col == 3 || col == 4) + EXPECT_EQ(mat(row, col), 0); + else + EXPECT_EQ(mat(row, col), int(10 * row + col - 2)); + } + } + + mat.removeColumns(3, 2); + ASSERT_TRUE(mat.hasConsistentState()); + mat.insertColumns(0, 0); + ASSERT_TRUE(mat.hasConsistentState()); + mat.insertColumn(5); + ASSERT_TRUE(mat.hasConsistentState()); + + EXPECT_EQ(mat.getNumRows(), 5u); + EXPECT_EQ(mat.getNumColumns(), 6u); + for (unsigned row = 0; row < 5; ++row) + for (unsigned col = 0; col < 6; ++col) + EXPECT_EQ(mat(row, col), col == 5 ? 0 : 10 * row + col); +} + +TEST(MatrixTest, insertRows) { + Matrix mat(5, 5, 5, 10); + ASSERT_TRUE(mat.hasConsistentState()); + EXPECT_EQ(mat.getNumRows(), 5u); + EXPECT_EQ(mat.getNumColumns(), 5u); + for (unsigned row = 0; row < 5; ++row) + for (unsigned col = 0; col < 5; ++col) + mat(row, col) = 10 * row + col; + + mat.insertRows(3, 2); + ASSERT_TRUE(mat.hasConsistentState()); + EXPECT_EQ(mat.getNumRows(), 7u); + EXPECT_EQ(mat.getNumColumns(), 5u); + for (unsigned row = 0; row < 7; ++row) { + for (unsigned col = 0; col < 5; ++col) { + if (row < 3) + EXPECT_EQ(mat(row, col), int(10 * row + col)); + else if (row == 3 || row == 4) + EXPECT_EQ(mat(row, col), 0); + else + EXPECT_EQ(mat(row, col), int(10 * (row - 2) + col)); + } + } + + mat.removeRows(3, 2); + ASSERT_TRUE(mat.hasConsistentState()); + mat.insertRows(0, 0); + ASSERT_TRUE(mat.hasConsistentState()); + mat.insertRow(5); + ASSERT_TRUE(mat.hasConsistentState()); + + EXPECT_EQ(mat.getNumRows(), 6u); + EXPECT_EQ(mat.getNumColumns(), 5u); + for (unsigned row = 0; row < 6; ++row) + for (unsigned col = 0; col < 5; ++col) + EXPECT_EQ(mat(row, col), row == 5 ? 0 : 10 * row + col); +} + } // namespace mlir