11 #include "llvm/Support/MathExtras.h"
14 using namespace presburger;
17 unsigned reservedColumns)
18 : nRows(rows), nColumns(columns),
19 nReservedColumns(std::
max(nColumns, reservedColumns)),
20 data(nRows * nReservedColumns) {
21 data.reserve(
std::max(nRows, reservedRows) * nReservedColumns);
25 Matrix matrix(dimension, dimension);
26 for (
unsigned i = 0; i < dimension; ++i)
32 return data.capacity() / nReservedColumns;
36 data.reserve(rows * nReservedColumns);
45 assert(elems.size() == nColumns &&
"elems must match row length!");
47 for (
unsigned col = 0; col < nColumns; ++col)
48 at(row, col) = elems[col];
53 if (newNColumns < nColumns)
55 if (newNColumns > nColumns)
66 data.resize(nRows * nReservedColumns);
71 "Given row out of bounds");
74 for (
unsigned col = 0; col < nColumns; col++)
75 std::swap(
at(row, col),
at(otherRow, col));
80 "Given column out of bounds");
81 if (column == otherColumn)
83 for (
unsigned row = 0; row < nRows; row++)
84 std::swap(
at(row, column),
at(row, otherColumn));
88 return {&data[row * nReservedColumns], nColumns};
92 return {&data[row * nReservedColumns], nColumns};
97 "elems size must match row length!");
99 at(row, i) = elems[i];
106 assert(pos <= nColumns);
107 unsigned oldNReservedColumns = nReservedColumns;
108 if (nColumns + count > nReservedColumns) {
109 nReservedColumns = llvm::NextPowerOf2(nColumns + count);
110 data.resize(nRows * nReservedColumns);
114 for (
int ri = nRows - 1; ri >= 0; --ri) {
115 for (
int ci = nReservedColumns - 1; ci >= 0; --ci) {
118 MPInt &dest = data[r * nReservedColumns + c];
126 }
else if (c >= pos + count) {
128 dest = data[r * oldNReservedColumns + c - count];
129 }
else if (c >= pos) {
136 if (nReservedColumns == oldNReservedColumns)
138 dest = data[r * oldNReservedColumns + c];
148 assert(pos + count - 1 < nColumns);
149 for (
unsigned r = 0; r < nRows; ++r) {
150 for (
unsigned c = pos; c < nColumns - count; ++c)
151 at(r, c) =
at(r, c + count);
152 for (
unsigned c = nColumns - count; c < nColumns; ++c)
163 assert(pos <= nRows);
165 for (
int r = nRows - 1; r >= int(pos + count); --r)
167 for (
int r = pos + count - 1; r >= int(pos); --r)
168 for (
unsigned c = 0; c < nColumns; ++c)
176 assert(pos + count - 1 <= nRows);
177 for (
unsigned r = pos; r + count < nRows; ++r)
183 if (sourceRow == targetRow)
185 for (
unsigned c = 0; c < nColumns; ++c)
186 at(targetRow, c) =
at(sourceRow, c);
190 for (
unsigned col = 0; col < nColumns; ++col)
191 at(row, col) = value;
195 const MPInt &scale) {
200 const MPInt &scale) {
203 for (
unsigned col = 0; col < nColumns; ++col)
204 at(row, col) += scale * rowVec[col];
208 const MPInt &scale) {
211 for (
unsigned row = 0, e =
getNumRows(); row < e; ++row)
212 at(row, targetColumn) += scale *
at(row, sourceColumn);
216 for (
unsigned row = 0, e =
getNumRows(); row < e; ++row)
217 at(row, column) = -
at(row, column);
221 for (
unsigned column = 0, e =
getNumColumns(); column < e; ++column)
222 at(row, column) = -
at(row, column);
234 assert(rowVec.size() ==
getNumRows() &&
"Invalid row vector dimension!");
238 for (
unsigned i = 0, e =
getNumRows(); i < e; ++i)
239 result[col] += rowVec[i] *
at(i, col);
246 "Invalid column vector dimension!");
249 for (
unsigned row = 0, e =
getNumRows(); row < e; row++)
251 result[row] +=
at(row, i) * colVec[i];
261 unsigned targetCol,
Matrix &otherMatrix) {
262 assert(m(row, sourceCol) != 0 &&
"Cannot divide by zero!");
263 assert(m(row, sourceCol) > 0 &&
"Source must be positive!");
264 MPInt ratio = -
floorDiv(m(row, targetCol), m(row, sourceCol));
266 otherMatrix.
addToColumn(sourceCol, targetCol, ratio);
276 unsigned echelonCol = 0;
281 for (
unsigned row = 0; row < h.
getNumRows(); ++row) {
283 unsigned nonZeroCol = echelonCol;
284 for (
unsigned e = h.
getNumColumns(); nonZeroCol < e; ++nonZeroCol) {
285 if (h(row, nonZeroCol) == 0)
297 if (nonZeroCol != echelonCol) {
303 if (h(row, echelonCol) < 0) {
309 for (
unsigned i = echelonCol + 1, e = h.
getNumColumns(); i < e; ++i) {
319 unsigned targetCol = i, sourceCol = echelonCol;
331 while (h(row, targetCol) != 0 && h(row, sourceCol) != 0) {
333 std::swap(targetCol, sourceCol);
338 if (h(row, echelonCol) == 0) {
346 for (
unsigned i = 0; i < echelonCol; ++i)
356 for (
unsigned row = 0; row < nRows; ++row) {
357 for (
unsigned column = 0; column < nColumns; ++column)
358 os <<
at(row, column) <<
' ';
366 if (data.size() != nRows * nReservedColumns)
368 if (nColumns > nReservedColumns)
370 #ifdef EXPENSIVE_CHECKS
371 for (
unsigned r = 0; r < nRows; ++r)
372 for (
unsigned c = nColumns; c < nReservedColumns; ++c)
373 if (data[r * nReservedColumns + c] != 0)
static void modEntryColumnOperation(Matrix &m, unsigned row, unsigned sourceCol, unsigned targetCol, Matrix &otherMatrix)
Set M(row, targetCol) to its remainder on division by M(row, sourceCol) by subtracting from column ta...
static Value max(ImplicitLocOpBuilder &builder, Value value, Value bound)
This class provides support for multi-precision arithmetic.
This is a class to represent a resizable matrix.
bool hasConsistentState() const
Return whether the Matrix is in a consistent state with all its invariants satisfied.
void insertRows(unsigned pos, unsigned count)
Insert rows having positions pos, pos + 1, ...
void swapColumns(unsigned column, unsigned otherColumn)
Swap the given columns.
void removeColumn(unsigned pos)
unsigned appendExtraRow()
Add an extra row at the bottom of the matrix and return its position.
void print(raw_ostream &os) const
Print the matrix.
void copyRow(unsigned sourceRow, unsigned targetRow)
void insertColumn(unsigned pos)
SmallVector< MPInt, 8 > postMultiplyWithColumn(ArrayRef< MPInt > colVec) const
The given vector is interpreted as a column vector v.
static Matrix identity(unsigned dimension)
Return the identity matrix of the specified dimension.
void removeColumns(unsigned pos, unsigned count)
Remove the columns having positions pos, pos + 1, ...
void insertColumns(unsigned pos, unsigned count)
Insert columns having positions pos, pos + 1, ...
MPInt normalizeRow(unsigned row, unsigned nCols)
Divide the first nCols of the specified row by their GCD.
MPInt & at(unsigned row, unsigned column)
Access the element at the specified row and column.
SmallVector< MPInt, 8 > preMultiplyWithRow(ArrayRef< MPInt > rowVec) const
The given vector is interpreted as a row vector v.
void removeRow(unsigned pos)
void resizeVertically(unsigned newNRows)
void setRow(unsigned row, ArrayRef< MPInt > elems)
Set the specified row to elems.
unsigned getNumReservedRows() const
Return the maximum number of rows/columns that can be added without incurring a reallocation.
unsigned getNumColumns() const
void fillRow(unsigned row, const MPInt &value)
unsigned getNumRows() const
void addToColumn(unsigned sourceColumn, unsigned targetColumn, const MPInt &scale)
Add scale multiples of the source column to the target column.
void insertRow(unsigned pos)
void swapRows(unsigned row, unsigned otherRow)
Swap the given rows.
void resizeHorizontally(unsigned newNColumns)
void addToRow(unsigned sourceRow, unsigned targetRow, const MPInt &scale)
Add scale multiples of the source row to the target row.
std::pair< Matrix, Matrix > computeHermiteNormalForm() const
Given the current matrix M, returns the matrices H, U such that H is the column hermite normal form o...
void reserveRows(unsigned rows)
Reserve enough space to resize to the specified number of rows without reallocations.
void negateColumn(unsigned column)
Negate the specified column.
void resize(unsigned newNRows, unsigned newNColumns)
Resize the matrix to the specified dimensions.
MutableArrayRef< MPInt > getRow(unsigned row)
Get a [Mutable]ArrayRef corresponding to the specified row.
void negateRow(unsigned row)
Negate the specified row.
void removeRows(unsigned pos, unsigned count)
Remove the rows having positions pos, pos + 1, ...
MPInt normalizeRange(MutableArrayRef< MPInt > range)
Divide the range by its gcd and return the gcd.
LLVM_ATTRIBUTE_ALWAYS_INLINE MPInt floorDiv(const MPInt &lhs, const MPInt &rhs)
This header declares functions that assist transformations in the MemRef dialect.