MLIR  19.0.0git
Public Member Functions | Static Public Member Functions | Protected Attributes | List of all members
mlir::presburger::Matrix< T > Class Template Reference

This is a class to represent a resizable matrix. More...

#include "mlir/Analysis/Presburger/Matrix.h"

+ Inheritance diagram for mlir::presburger::Matrix< T >:

Public Member Functions

 Matrix ()=delete
 
 Matrix (unsigned rows, unsigned columns, unsigned reservedRows=0, unsigned reservedColumns=0)
 Construct a matrix with the specified number of rows and columns. More...
 
T & at (unsigned row, unsigned column)
 Access the element at the specified row and column. More...
 
at (unsigned row, unsigned column) const
 
T & operator() (unsigned row, unsigned column)
 
operator() (unsigned row, unsigned column) const
 
bool operator== (const Matrix< T > &m) const
 We cannot use the default implementation of operator== as it compares fields like reservedColumns etc., which are not part of the data. More...
 
void swapColumns (unsigned column, unsigned otherColumn)
 Swap the given columns. More...
 
void swapRows (unsigned row, unsigned otherRow)
 Swap the given rows. More...
 
unsigned getNumRows () const
 
unsigned getNumColumns () const
 
unsigned getNumReservedRows () const
 Return the maximum number of rows/columns that can be added without incurring a reallocation. More...
 
unsigned getNumReservedColumns () const
 
void reserveRows (unsigned rows)
 Reserve enough space to resize to the specified number of rows without reallocations. More...
 
MutableArrayRef< T > getRow (unsigned row)
 Get a [Mutable]ArrayRef corresponding to the specified row. More...
 
ArrayRef< T > getRow (unsigned row) const
 
void setRow (unsigned row, ArrayRef< T > elems)
 Set the specified row to elems. More...
 
void insertColumns (unsigned pos, unsigned count)
 Insert columns having positions pos, pos + 1, ... More...
 
void insertColumn (unsigned pos)
 
void insertRows (unsigned pos, unsigned count)
 Insert rows having positions pos, pos + 1, ... More...
 
void insertRow (unsigned pos)
 
void removeColumns (unsigned pos, unsigned count)
 Remove the columns having positions pos, pos + 1, ... More...
 
void removeColumn (unsigned pos)
 
void removeRows (unsigned pos, unsigned count)
 Remove the rows having positions pos, pos + 1, ... More...
 
void removeRow (unsigned pos)
 
void copyRow (unsigned sourceRow, unsigned targetRow)
 
void fillRow (unsigned row, const T &value)
 
void fillRow (unsigned row, int64_t value)
 
void addToRow (unsigned sourceRow, unsigned targetRow, const T &scale)
 Add scale multiples of the source row to the target row. More...
 
void addToRow (unsigned sourceRow, unsigned targetRow, int64_t scale)
 
void addToRow (unsigned row, ArrayRef< T > rowVec, const T &scale)
 Add scale multiples of the rowVec row to the specified row. More...
 
void scaleRow (unsigned row, const T &scale)
 Multiply the specified row by a factor of scale. More...
 
void addToColumn (unsigned sourceColumn, unsigned targetColumn, const T &scale)
 Add scale multiples of the source column to the target column. More...
 
void addToColumn (unsigned sourceColumn, unsigned targetColumn, int64_t scale)
 
void negateColumn (unsigned column)
 Negate the specified column. More...
 
void negateRow (unsigned row)
 Negate the specified row. More...
 
void negateMatrix ()
 Negate the entire matrix. More...
 
SmallVector< T, 8 > preMultiplyWithRow (ArrayRef< T > rowVec) const
 The given vector is interpreted as a row vector v. More...
 
SmallVector< T, 8 > postMultiplyWithColumn (ArrayRef< T > colVec) const
 The given vector is interpreted as a column vector v. More...
 
void resize (unsigned newNRows, unsigned newNColumns)
 Resize the matrix to the specified dimensions. More...
 
void resizeHorizontally (unsigned newNColumns)
 
void resizeVertically (unsigned newNRows)
 
unsigned appendExtraRow ()
 Add an extra row at the bottom of the matrix and return its position. More...
 
unsigned appendExtraRow (ArrayRef< T > elems)
 Same as above, but copy the given elements into the row. More...
 
Matrix< T > transpose () const
 
Matrix< T > getSubMatrix (unsigned fromRow, unsigned toRow, unsigned fromColumn, unsigned toColumn) const
 
std::pair< Matrix< T >, Matrix< T > > splitByBitset (ArrayRef< int > indicator)
 Split the rows of a matrix into two matrices according to which bits are 1 and which are 0 in a given bitset. More...
 
void print (raw_ostream &os) const
 Print the matrix. More...
 
void dump () const
 
bool hasConsistentState () const
 Return whether the Matrix is in a consistent state with all its invariants satisfied. More...
 
void moveColumns (unsigned srcPos, unsigned num, unsigned dstPos)
 Move the columns in the source range [srcPos, srcPos + num) to the specified destination [dstPos, dstPos + num), while moving the columns adjacent to the source range to the left/right of the shifted columns. More...
 

Static Public Member Functions

static Matrix identity (unsigned dimension)
 Return the identity matrix of the specified dimension. More...
 

Protected Attributes

unsigned nRows
 The current number of rows, columns, and reserved columns. More...
 
unsigned nColumns
 
unsigned nReservedColumns
 
SmallVector< T, 16 > data
 Stores the data. More...
 

Detailed Description

template<typename T>
class mlir::presburger::Matrix< T >

This is a class to represent a resizable matrix.

More columns and rows can be reserved than are currently used. The data is stored as a single 1D array, viewed as a 2D matrix with nRows rows and nReservedColumns columns, stored in row major form. Thus the element at (i, j) is stored at data[i*nReservedColumns + j]. The reserved but unused columns always have all zero values. The reserved rows are just reserved space in the underlying SmallVector's capacity. This class only works for the types DynamicAPInt and Fraction, since the method implementations are in the Matrix.cpp file. Only these two types have been explicitly instantiated there.

Definition at line 41 of file Matrix.h.

Constructor & Destructor Documentation

◆ Matrix() [1/2]

template<typename T >
mlir::presburger::Matrix< T >::Matrix ( )
delete

◆ Matrix() [2/2]

template<typename T >
Matrix::Matrix ( unsigned  rows,
unsigned  columns,
unsigned  reservedRows = 0,
unsigned  reservedColumns = 0 
)

Construct a matrix with the specified number of rows and 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.

Definition at line 23 of file Matrix.cpp.

References mlir::presburger::Matrix< T >::data, max(), mlir::presburger::Matrix< T >::nReservedColumns, and mlir::presburger::Matrix< T >::nRows.

Member Function Documentation

◆ addToColumn() [1/2]

template<typename T >
void Matrix::addToColumn ( unsigned  sourceColumn,
unsigned  targetColumn,
const T &  scale 
)

◆ addToColumn() [2/2]

template<typename T >
void mlir::presburger::Matrix< T >::addToColumn ( unsigned  sourceColumn,
unsigned  targetColumn,
int64_t  scale 
)
inline

Definition at line 154 of file Matrix.h.

References mlir::presburger::Matrix< T >::addToColumn().

◆ addToRow() [1/3]

template<typename T >
void Matrix::addToRow ( unsigned  row,
ArrayRef< T >  rowVec,
const T &  scale 
)

Add scale multiples of the rowVec row to the specified row.

Definition at line 306 of file Matrix.cpp.

◆ addToRow() [2/3]

template<typename T >
void Matrix::addToRow ( unsigned  sourceRow,
unsigned  targetRow,
const T &  scale 
)

◆ addToRow() [3/3]

template<typename T >
void mlir::presburger::Matrix< T >::addToRow ( unsigned  sourceRow,
unsigned  targetRow,
int64_t  scale 
)
inline

Definition at line 142 of file Matrix.h.

References mlir::presburger::Matrix< T >::addToRow().

◆ appendExtraRow() [1/2]

template<typename T >
unsigned Matrix::appendExtraRow

◆ appendExtraRow() [2/2]

template<typename T >
unsigned Matrix::appendExtraRow ( ArrayRef< T >  elems)

Same as above, but copy the given elements into the row.

The length of elems must be equal to the number of columns.

Definition at line 72 of file Matrix.cpp.

◆ at() [1/2]

template<typename T >
T& mlir::presburger::Matrix< T >::at ( unsigned  row,
unsigned  column 
)
inline

◆ at() [2/2]

template<typename T >
T mlir::presburger::Matrix< T >::at ( unsigned  row,
unsigned  column 
) const
inline

◆ copyRow()

template<typename T >
void Matrix::copyRow ( unsigned  sourceRow,
unsigned  targetRow 
)

◆ dump()

template<typename T >
void Matrix::dump

Definition at line 425 of file Matrix.cpp.

References print().

◆ fillRow() [1/2]

template<typename T >
void Matrix::fillRow ( unsigned  row,
const T &  value 
)

◆ fillRow() [2/2]

template<typename T >
void mlir::presburger::Matrix< T >::fillRow ( unsigned  row,
int64_t  value 
)
inline

◆ getNumColumns()

template<typename T >
unsigned mlir::presburger::Matrix< T >::getNumColumns ( ) const
inline

◆ getNumReservedColumns()

template<typename T >
unsigned mlir::presburger::Matrix< T >::getNumReservedColumns ( ) const
inline

Definition at line 92 of file Matrix.h.

References mlir::presburger::Matrix< T >::nReservedColumns.

◆ getNumReservedRows()

template<typename T >
unsigned Matrix::getNumReservedRows

Return the maximum number of rows/columns that can be added without incurring a reallocation.

Definition at line 56 of file Matrix.cpp.

Referenced by mlir::presburger::IntegerRelation::getNumReservedEqualities(), and mlir::presburger::IntegerRelation::getNumReservedInequalities().

◆ getNumRows()

template<typename T >
unsigned mlir::presburger::Matrix< T >::getNumRows ( ) const
inline

◆ getRow() [1/2]

template<typename T >
MutableArrayRef< T > Matrix::getRow ( unsigned  row)

◆ getRow() [2/2]

template<typename T >
ArrayRef< T > Matrix::getRow ( unsigned  row) const

Definition at line 136 of file Matrix.cpp.

◆ getSubMatrix()

template<typename T >
Matrix< T > Matrix::getSubMatrix ( unsigned  fromRow,
unsigned  toRow,
unsigned  fromColumn,
unsigned  toColumn 
) const

Definition at line 385 of file Matrix.cpp.

Referenced by mlir::presburger::detail::solveParametricEquations().

◆ hasConsistentState()

template<typename T >
bool Matrix::hasConsistentState

Return whether the Matrix is in a consistent state with all its invariants satisfied.

Definition at line 430 of file Matrix.cpp.

Referenced by mlir::presburger::IntegerRelation::hasConsistentState().

◆ identity()

template<typename T >
Matrix< T > Matrix::identity ( unsigned  dimension)
static

Return the identity matrix of the specified dimension.

Definition at line 48 of file Matrix.cpp.

Referenced by mlir::presburger::FracMatrix::identity().

◆ insertColumn()

template<typename T >
void Matrix::insertColumn ( unsigned  pos)

◆ insertColumns()

template<typename T >
void Matrix::insertColumns ( unsigned  pos,
unsigned  count 
)

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.

Definition at line 153 of file Matrix.cpp.

Referenced by mlir::presburger::DivisionRepr::insertDiv(), and mlir::presburger::MultiAffineFunction::mergeDivs().

◆ insertRow()

template<typename T >
void Matrix::insertRow ( unsigned  pos)

Definition at line 213 of file Matrix.cpp.

◆ insertRows()

template<typename T >
void Matrix::insertRows ( unsigned  pos,
unsigned  count 
)

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.

Definition at line 217 of file Matrix.cpp.

Referenced by mlir::presburger::DivisionRepr::insertDiv().

◆ moveColumns()

template<typename T >
void Matrix::moveColumns ( unsigned  srcPos,
unsigned  num,
unsigned  dstPos 
)

Move the columns in the source range [srcPos, srcPos + num) to the specified destination [dstPos, dstPos + num), while moving the columns adjacent to the source range to the left/right of the shifted columns.

When moving the source columns right (i.e. dstPos > srcPos), columns that were at positions [0, srcPos) and [dstPos + num, nCols) will stay where they are; columns that were at positions [srcPos, srcPos + num) will be moved to [dstPos, dstPos + num); and columns that were at positions [srcPos + num, dstPos + num) will be moved to [srcPos, dstPos). Equivalently, the columns [srcPos + num, dstPos + num) are interchanged with [srcPos, srcPos + num). For example, if m = |0 1 2 3 4 5| then: m.moveColumns(1, 3, 2) will result in m = |0 4 1 2 3 5|; or m.moveColumns(1, 2, 4) will result in m = |0 3 4 5 1 2|.

The left shift operation (i.e. dstPos < srcPos) works in a similar way.

Definition at line 267 of file Matrix.cpp.

Referenced by mlir::presburger::IntegerRelation::convertVarKind().

◆ negateColumn()

template<typename T >
void Matrix::negateColumn ( unsigned  column)

Negate the specified column.

Definition at line 329 of file Matrix.cpp.

Referenced by mlir::presburger::IntMatrix::computeHermiteNormalForm().

◆ negateMatrix()

template<typename T >
void Matrix::negateMatrix

Negate the entire matrix.

Definition at line 341 of file Matrix.cpp.

Referenced by mlir::presburger::detail::solveParametricEquations().

◆ negateRow()

template<typename T >
void Matrix::negateRow ( unsigned  row)

◆ operator()() [1/2]

template<typename T >
T& mlir::presburger::Matrix< T >::operator() ( unsigned  row,
unsigned  column 
)
inline

Definition at line 73 of file Matrix.h.

References mlir::presburger::Matrix< T >::at().

◆ operator()() [2/2]

template<typename T >
T mlir::presburger::Matrix< T >::operator() ( unsigned  row,
unsigned  column 
) const
inline

Definition at line 75 of file Matrix.h.

References mlir::presburger::Matrix< T >::at().

◆ operator==()

template<typename T >
bool Matrix::operator== ( const Matrix< T > &  m) const

We cannot use the default implementation of operator== as it compares fields like reservedColumns etc., which are not part of the data.

Definition at line 34 of file Matrix.cpp.

References mlir::presburger::Matrix< T >::getNumColumns(), mlir::presburger::Matrix< T >::getNumRows(), and mlir::presburger::Matrix< T >::getRow().

◆ postMultiplyWithColumn()

template<typename T >
SmallVector< T, 8 > Matrix::postMultiplyWithColumn ( ArrayRef< T >  colVec) const

The given vector is interpreted as a column vector v.

Pre-multiply v with this matrix, say M, and return Mv.

Definition at line 358 of file Matrix.cpp.

Referenced by mlir::presburger::LinearTransform::postMultiplyWithColumn(), and mlir::presburger::MultiAffineFunction::valueAt().

◆ preMultiplyWithRow()

template<typename T >
SmallVector< T, 8 > Matrix::preMultiplyWithRow ( ArrayRef< T >  rowVec) const

The given vector is interpreted as a row vector v.

Post-multiply v with this matrix, say M, and return vM.

Definition at line 347 of file Matrix.cpp.

Referenced by mlir::presburger::detail::computeUnimodularConeGeneratingFunction(), and mlir::presburger::LinearTransform::preMultiplyWithRow().

◆ print()

template<typename T >
void Matrix::print ( raw_ostream &  os) const

Print the matrix.

Definition at line 401 of file Matrix.cpp.

Referenced by mlir::presburger::MultiAffineFunction::print(), and mlir::presburger::DivisionRepr::print().

◆ removeColumn()

template<typename T >
void Matrix::removeColumn ( unsigned  pos)

◆ removeColumns()

template<typename T >
void Matrix::removeColumns ( unsigned  pos,
unsigned  count 
)

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.

Definition at line 199 of file Matrix.cpp.

◆ removeRow()

template<typename T >
void Matrix::removeRow ( unsigned  pos)

◆ removeRows()

template<typename T >
void Matrix::removeRows ( unsigned  pos,
unsigned  count 
)

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.

Definition at line 235 of file Matrix.cpp.

Referenced by mlir::presburger::IntegerRelation::removeEqualityRange(), mlir::presburger::IntegerRelation::removeInequalityRange(), and mlir::presburger::MultiAffineFunction::removeOutputs().

◆ reserveRows()

template<typename T >
void Matrix::reserveRows ( unsigned  rows)

Reserve enough space to resize to the specified number of rows without reallocations.

Definition at line 61 of file Matrix.cpp.

Referenced by mlir::presburger::IntegerRelation::append(), and mlir::presburger::Simplex::makeProduct().

◆ resize()

template<typename T >
void Matrix::resize ( unsigned  newNRows,
unsigned  newNColumns 
)

Resize the matrix to the specified dimensions.

If a dimension is smaller, the values are truncated; if it is bigger, the new values are initialized to zero.

Due to the representation of the matrix, resizing vertically (adding rows) is less expensive than increasing the number of columns beyond nReservedColumns.

Definition at line 99 of file Matrix.cpp.

◆ resizeHorizontally()

template<typename T >
void Matrix::resizeHorizontally ( unsigned  newNColumns)

◆ resizeVertically()

template<typename T >
void Matrix::resizeVertically ( unsigned  newNRows)

◆ scaleRow()

template<typename T >
void Matrix::scaleRow ( unsigned  row,
const T &  scale 
)

Multiply the specified row by a factor of scale.

Definition at line 314 of file Matrix.cpp.

Referenced by mlir::presburger::detail::solveParametricEquations().

◆ setRow()

template<typename T >
void Matrix::setRow ( unsigned  row,
ArrayRef< T >  elems 
)

◆ splitByBitset()

template<typename T >
std::pair< Matrix< T >, Matrix< T > > Matrix::splitByBitset ( ArrayRef< int >  indicator)

Split the rows of a matrix into two matrices according to which bits are 1 and which are 0 in a given bitset.

We iterate over the indicator bitset, checking each bit.

The first matrix returned has the rows corresponding to 1 and the second corresponding to 2.

If a bit is 1, we append it to one matrix, and if it is zero, we append it to the other.

Definition at line 413 of file Matrix.cpp.

References mlir::presburger::Matrix< T >::appendExtraRow().

Referenced by mlir::presburger::detail::computePolytopeGeneratingFunction().

◆ swapColumns()

template<typename T >
void Matrix::swapColumns ( unsigned  column,
unsigned  otherColumn 
)

◆ swapRows()

template<typename T >
void Matrix::swapRows ( unsigned  row,
unsigned  otherRow 
)

◆ transpose()

template<typename T >
Matrix< T > Matrix::transpose

Member Data Documentation

◆ data

template<typename T >
SmallVector<T, 16> mlir::presburger::Matrix< T >::data
protected

Stores the data.

data.size() is equal to nRows * nReservedColumns. data.capacity() / nReservedColumns is the number of reserved rows.

Definition at line 244 of file Matrix.h.

Referenced by mlir::presburger::Matrix< T >::at(), and mlir::presburger::Matrix< T >::Matrix().

◆ nColumns

template<typename T >
unsigned mlir::presburger::Matrix< T >::nColumns
protected

◆ nReservedColumns

template<typename T >
unsigned mlir::presburger::Matrix< T >::nReservedColumns
protected

◆ nRows

template<typename T >
unsigned mlir::presburger::Matrix< T >::nRows
protected

The current number of rows, columns, and reserved columns.

The underlying data vector is viewed as an nRows x nReservedColumns matrix, of which the first nColumns columns are currently in use, and the remaining are reserved columns filled with zeros.

Definition at line 240 of file Matrix.h.

Referenced by mlir::presburger::Matrix< T >::at(), mlir::presburger::Matrix< T >::getNumRows(), and mlir::presburger::Matrix< T >::Matrix().


The documentation for this class was generated from the following files: