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

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

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...

MPInt &	at (unsigned row, unsigned column)
	Access the element at the specified row and column. More...

MPInt	at (unsigned row, unsigned column) const

MPInt &	operator() (unsigned row, unsigned column)

MPInt	operator() (unsigned row, unsigned column) const

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< MPInt >	getRow (unsigned row)
	Get a [Mutable]ArrayRef corresponding to the specified row. More...

ArrayRef< MPInt >	getRow (unsigned row) const

void	setRow (unsigned row, ArrayRef< MPInt > 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 MPInt &value)

void	fillRow (unsigned row, int64_t value)

void	addToRow (unsigned sourceRow, unsigned targetRow, const MPInt &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< MPInt > rowVec, const MPInt &scale)
	Add `scale` multiples of the rowVec row to the specified row. More...

void	addToColumn (unsigned sourceColumn, unsigned targetColumn, const MPInt &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...

MPInt	normalizeRow (unsigned row, unsigned nCols)
	Divide the first `nCols` of the specified row by their GCD. More...

MPInt	normalizeRow (unsigned row)
	Divide the columns of the specified row by their GCD. More...

SmallVector< MPInt, 8 >	preMultiplyWithRow (ArrayRef< MPInt > rowVec) const
	The given vector is interpreted as a row vector v. More...

SmallVector< MPInt, 8 >	postMultiplyWithColumn (ArrayRef< MPInt > colVec) const
	The given vector is interpreted as a column vector v. More...

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 of M, i.e. 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< MPInt > elems)
	Same as above, but copy the given elements into the row. 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...

Static Public Member Functions
static Matrix	identity (unsigned dimension)
	Return the identity matrix of the specified dimension. More...

Detailed Description

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.

Definition at line 35 of file Matrix.h.

Constructor & Destructor Documentation

◆ Matrix() [1/2]

mlir::presburger::Matrix::Matrix ( )

delete

◆ Matrix() [2/2]

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 16 of file Matrix.cpp.

References max().

Member Function Documentation

◆ addToColumn() [1/2]

void Matrix::addToColumn	(	unsigned	sourceColumn,
		unsigned	targetColumn,
		const MPInt &	scale
	)

Add scale multiples of the source column to the target column.

Definition at line 207 of file Matrix.cpp.

References at(), and getNumRows().

Referenced by addToColumn(), mlir::presburger::IntegerRelation::eliminateRedundantLocalVar(), mlir::presburger::MultiAffineFunction::mergeDivs(), modEntryColumnOperation(), mlir::presburger::DivisionRepr::removeDuplicateDivs(), and mlir::presburger::IntegerRelation::setAndEliminate().

◆ addToColumn() [2/2]

void mlir::presburger::Matrix::addToColumn	(	unsigned	sourceColumn,
		unsigned	targetColumn,
		int64_t	scale
	)

inline

Definition at line 142 of file Matrix.h.

References addToColumn().

◆ addToRow() [1/3]

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

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

Definition at line 199 of file Matrix.cpp.

References at().

◆ addToRow() [2/3]

void Matrix::addToRow	(	unsigned	sourceRow,
		unsigned	targetRow,
		const MPInt &	scale
	)

Add scale multiples of the source row to the target row.

Definition at line 194 of file Matrix.cpp.

References getRow().

Referenced by addToRow(), and mlir::presburger::MultiAffineFunction::subtract().

◆ addToRow() [3/3]

void mlir::presburger::Matrix::addToRow	(	unsigned	sourceRow,
		unsigned	targetRow,
		int64_t	scale
	)

inline

Definition at line 133 of file Matrix.h.

References addToRow().

◆ appendExtraRow() [1/2]

unsigned Matrix::appendExtraRow ( )

Add an extra row at the bottom of the matrix and return its position.

Definition at line 39 of file Matrix.cpp.

References resizeVertically().

Referenced by mlir::presburger::IntegerRelation::addBound(), mlir::presburger::IntegerRelation::addEquality(), mlir::presburger::IntegerRelation::addInequality(), mlir::presburger::SimplexBase::addZeroRow(), appendExtraRow(), mlir::presburger::DivisionRepr::insertDiv(), and mlir::presburger::Simplex::makeProduct().

◆ appendExtraRow() [2/2]

unsigned Matrix::appendExtraRow ( ArrayRef< MPInt > 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 44 of file Matrix.cpp.

References appendExtraRow(), and at().

◆ at() [1/2]

MPInt& mlir::presburger::Matrix::at	(	unsigned	row,
		unsigned	column
	)

inline

Access the element at the specified row and column.

Definition at line 52 of file Matrix.h.

Referenced by addToColumn(), addToRow(), appendExtraRow(), copyRow(), fillRow(), insertRows(), negateColumn(), negateRow(), operator()(), postMultiplyWithColumn(), preMultiplyWithRow(), print(), removeColumns(), setRow(), swapColumns(), and swapRows().

◆ at() [2/2]

MPInt mlir::presburger::Matrix::at	(	unsigned	row,
		unsigned	column
	)		const

inline

Definition at line 58 of file Matrix.h.

◆ computeHermiteNormalForm()

std::pair< Matrix, Matrix > Matrix::computeHermiteNormalForm ( ) const

Given the current matrix M, returns the matrices H, U such that H is the column hermite normal form of M, i.e.

H = M * U, where U is unimodular and the matrix H has the following restrictions:

H is lower triangular.
The leading coefficient (the first non-zero entry from the top, called the pivot) of a non-zero column is always strictly below of the leading coefficient of the column before it; moreover, it is positive.
The elements to the right of the pivots are zero and the elements to the left of the pivots are nonnegative and strictly smaller than the pivot.

Definition at line 269 of file Matrix.cpp.

References getNumColumns(), getNumRows(), identity(), modEntryColumnOperation(), negateColumn(), and swapColumns().

Referenced by mlir::presburger::LinearTransform::makeTransformToColumnEchelon().

◆ copyRow()

void Matrix::copyRow	(	unsigned	sourceRow,
		unsigned	targetRow
	)

Definition at line 182 of file Matrix.cpp.

References at().

Referenced by insertRows(), mlir::presburger::IntegerRelation::removeRedundantConstraints(), mlir::presburger::IntegerRelation::removeRedundantInequalities(), removeRows(), and mlir::presburger::IntegerRelation::removeTrivialRedundancy().

◆ dump()

void Matrix::dump ( ) const

Definition at line 363 of file Matrix.cpp.

References print().

◆ fillRow() [1/2]

void Matrix::fillRow	(	unsigned	row,
		const MPInt &	value
	)

Definition at line 189 of file Matrix.cpp.

References at().

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

◆ fillRow() [2/2]

void mlir::presburger::Matrix::fillRow	(	unsigned	row,
		int64_t	value
	)

inline

Definition at line 129 of file Matrix.h.

References fillRow().

Referenced by fillRow().

◆ getNumColumns()

unsigned mlir::presburger::Matrix::getNumColumns ( ) const

inline

Definition at line 78 of file Matrix.h.

Referenced by computeHermiteNormalForm(), mlir::presburger::SimplexBase::getNumColumns(), mlir::presburger::DivisionRepr::getNumVars(), mlir::presburger::LinearTransform::makeTransformToColumnEchelon(), negateRow(), normalizeRow(), postMultiplyWithColumn(), preMultiplyWithRow(), setRow(), and swapColumns().

◆ getNumReservedColumns()

unsigned mlir::presburger::Matrix::getNumReservedColumns ( ) const

inline

Definition at line 83 of file Matrix.h.

◆ getNumReservedRows()

unsigned Matrix::getNumReservedRows ( ) const

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

Definition at line 31 of file Matrix.cpp.

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

◆ getNumRows()

unsigned mlir::presburger::Matrix::getNumRows ( ) const

inline

Definition at line 76 of file Matrix.h.

Referenced by mlir::presburger::IntegerRelation::addBound(), addToColumn(), mlir::presburger::IntegerRelation::append(), computeHermiteNormalForm(), mlir::presburger::Simplex::findIntegerSample(), mlir::presburger::DivisionRepr::getNumDivs(), mlir::presburger::IntegerRelation::getNumEqualities(), mlir::presburger::IntegerRelation::getNumInequalities(), mlir::presburger::SimplexBase::getNumRows(), mlir::presburger::LinearTransform::makeTransformToColumnEchelon(), negateColumn(), postMultiplyWithColumn(), preMultiplyWithRow(), and swapRows().

◆ getRow() [1/2]

MutableArrayRef< MPInt > Matrix::getRow ( unsigned row )

Get a [Mutable]ArrayRef corresponding to the specified row.

Definition at line 87 of file Matrix.cpp.

Referenced by addToRow(), mlir::presburger::Simplex::findIntegerSample(), mlir::presburger::DivisionRepr::getDividend(), mlir::presburger::IntegerRelation::getEquality(), mlir::presburger::IntegerRelation::getEquality64(), mlir::presburger::IntegerRelation::getInequality(), mlir::presburger::IntegerRelation::getInequality64(), mlir::presburger::MultiAffineFunction::getOutputExpr(), normalizeRow(), and mlir::presburger::DivisionRepr::removeDuplicateDivs().

◆ getRow() [2/2]

ArrayRef< MPInt > Matrix::getRow ( unsigned row ) const

Definition at line 91 of file Matrix.cpp.

◆ hasConsistentState()

bool Matrix::hasConsistentState ( ) const

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

Definition at line 365 of file Matrix.cpp.

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

◆ identity()

Matrix Matrix::identity ( unsigned dimension )

static

Return the identity matrix of the specified dimension.

Definition at line 24 of file Matrix.cpp.

Referenced by computeHermiteNormalForm(), and mlir::presburger::Simplex::findIntegerSample().

◆ insertColumn()

void Matrix::insertColumn ( unsigned pos )

Definition at line 102 of file Matrix.cpp.

References insertColumns().

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

◆ insertColumns()

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 103 of file Matrix.cpp.

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

◆ insertRow()

void Matrix::insertRow ( unsigned pos )

Definition at line 158 of file Matrix.cpp.

References insertRows().

◆ insertRows()

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 159 of file Matrix.cpp.

References at(), copyRow(), and resizeVertically().

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

◆ negateColumn()

void Matrix::negateColumn ( unsigned column )

Negate the specified column.

Definition at line 215 of file Matrix.cpp.

References at(), and getNumRows().

Referenced by computeHermiteNormalForm().

◆ negateRow()

void Matrix::negateRow ( unsigned row )

Negate the specified row.

Definition at line 220 of file Matrix.cpp.

References at(), and getNumColumns().

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

◆ normalizeRow() [1/2]

MPInt Matrix::normalizeRow ( unsigned row )

Divide the columns of the specified row by their GCD.

Returns the GCD of the columns of the specified row.

Definition at line 229 of file Matrix.cpp.

References getNumColumns(), and normalizeRow().

◆ normalizeRow() [2/2]

MPInt Matrix::normalizeRow	(	unsigned	row,
		unsigned	nCols
	)

Divide the first nCols of the specified row by their GCD.

Returns the GCD of the first nCols of the specified row.

Definition at line 225 of file Matrix.cpp.

References getRow(), and mlir::presburger::normalizeRange().

Referenced by mlir::presburger::SimplexBase::addRow(), mlir::presburger::IntegerRelation::gaussianEliminateVars(), mlir::presburger::IntegerRelation::gcdTightenInequalities(), mlir::presburger::IntegerRelation::normalizeConstraintsByGCD(), normalizeRow(), mlir::presburger::SimplexBase::pivot(), and mlir::presburger::IntegerRelation::removeRedundantLocalVars().

◆ operator()() [1/2]

MPInt& mlir::presburger::Matrix::operator()	(	unsigned	row,
		unsigned	column
	)

inline

Definition at line 64 of file Matrix.h.

References at().

◆ operator()() [2/2]

MPInt mlir::presburger::Matrix::operator()	(	unsigned	row,
		unsigned	column
	)		const

inline

Definition at line 66 of file Matrix.h.

References at().

◆ postMultiplyWithColumn()

SmallVector< MPInt, 8 > Matrix::postMultiplyWithColumn ( ArrayRef< MPInt > 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 244 of file Matrix.cpp.

References at(), getNumColumns(), and getNumRows().

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

◆ preMultiplyWithRow()

SmallVector< MPInt, 8 > Matrix::preMultiplyWithRow ( ArrayRef< MPInt > 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 233 of file Matrix.cpp.

References at(), getNumColumns(), and getNumRows().

Referenced by mlir::presburger::LinearTransform::preMultiplyWithRow().

◆ print()

void Matrix::print ( raw_ostream & os ) const

Print the matrix.

Definition at line 355 of file Matrix.cpp.

References at().

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

◆ removeColumn()

void Matrix::removeColumn ( unsigned pos )

Definition at line 144 of file Matrix.cpp.

References removeColumns().

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

◆ removeColumns()

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 145 of file Matrix.cpp.

References at().

Referenced by removeColumn(), and resizeHorizontally().

◆ removeRow()

void Matrix::removeRow ( unsigned pos )

Definition at line 172 of file Matrix.cpp.

References removeRows().

Referenced by mlir::presburger::DivisionRepr::removeDuplicateDivs(), mlir::presburger::IntegerRelation::removeEquality(), and mlir::presburger::IntegerRelation::removeInequality().

◆ removeRows()

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 173 of file Matrix.cpp.

References copyRow(), and resizeVertically().

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

◆ reserveRows()

void Matrix::reserveRows ( unsigned rows )

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

Definition at line 35 of file Matrix.cpp.

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

◆ resize()

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 59 of file Matrix.cpp.

References resizeHorizontally(), and resizeVertically().

◆ resizeHorizontally()

void Matrix::resizeHorizontally ( unsigned newNColumns )

Definition at line 52 of file Matrix.cpp.

References insertColumns(), and removeColumns().

Referenced by mlir::presburger::SimplexBase::appendVariable(), resize(), and mlir::presburger::SimplexBase::undo().

◆ resizeVertically()

void Matrix::resizeVertically ( unsigned newNRows )

Definition at line 64 of file Matrix.cpp.

Referenced by appendExtraRow(), mlir::presburger::IntegerRelation::clearConstraints(), insertRows(), mlir::presburger::SimplexBase::removeLastConstraintRowOrientation(), mlir::presburger::IntegerRelation::removeRedundantConstraints(), mlir::presburger::IntegerRelation::removeRedundantInequalities(), removeRows(), mlir::presburger::IntegerRelation::removeTrivialRedundancy(), and resize().

◆ setRow()

void Matrix::setRow	(	unsigned	row,
		ArrayRef< MPInt >	elems
	)

Set the specified row to elems.

Definition at line 95 of file Matrix.cpp.

References at(), and getNumColumns().

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

◆ swapColumns()

void Matrix::swapColumns	(	unsigned	column,
		unsigned	otherColumn
	)

Swap the given columns.

Definition at line 78 of file Matrix.cpp.

References at(), and getNumColumns().

Referenced by computeHermiteNormalForm(), mlir::presburger::SimplexBase::swapColumns(), and mlir::presburger::IntegerRelation::swapVar().

◆ swapRows()

void Matrix::swapRows	(	unsigned	row,
		unsigned	otherRow
	)

Swap the given rows.

Definition at line 69 of file Matrix.cpp.

References at(), and getNumRows().

Referenced by mlir::presburger::SimplexBase::swapRows().

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

include/mlir/Analysis/Presburger/Matrix.h
lib/Analysis/Presburger/Matrix.cpp

Public Member Functions

Static Public Member Functions

Detailed Description

Constructor & Destructor Documentation

◆ Matrix() [1/2]

◆ Matrix() [2/2]

Member Function Documentation

◆ addToColumn() [1/2]

◆ addToColumn() [2/2]

◆ addToRow() [1/3]

◆ addToRow() [2/3]

◆ addToRow() [3/3]

◆ appendExtraRow() [1/2]

◆ appendExtraRow() [2/2]

◆ at() [1/2]

◆ at() [2/2]

◆ computeHermiteNormalForm()

◆ copyRow()

◆ dump()

◆ fillRow() [1/2]

◆ fillRow() [2/2]

◆ getNumColumns()

◆ getNumReservedColumns()

◆ getNumReservedRows()

◆ getNumRows()

◆ getRow() [1/2]

◆ getRow() [2/2]

◆ hasConsistentState()

◆ identity()

◆ insertColumn()

◆ insertColumns()

◆ insertRow()

◆ insertRows()

◆ negateColumn()

◆ negateRow()

◆ normalizeRow() [1/2]

◆ normalizeRow() [2/2]

◆ operator()() [1/2]

◆ operator()() [2/2]

◆ postMultiplyWithColumn()

◆ preMultiplyWithRow()

◆ print()

◆ removeColumn()

◆ removeColumns()

◆ removeRow()

◆ removeRows()

◆ reserveRows()

◆ resize()

◆ resizeHorizontally()

◆ resizeVertically()

◆ setRow()

◆ swapColumns()

◆ swapRows()