MLIR  17.0.0git
Matrix.h
Go to the documentation of this file.
1 //===- Matrix.h - MLIR Matrix Class -----------------------------*- C++ -*-===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This is a simple 2D matrix class that supports reading, writing, resizing,
10 // swapping rows, and swapping columns.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #ifndef MLIR_ANALYSIS_PRESBURGER_MATRIX_H
15 #define MLIR_ANALYSIS_PRESBURGER_MATRIX_H
16 
18 #include "mlir/Support/LLVM.h"
19 #include "llvm/ADT/ArrayRef.h"
20 #include "llvm/Support/raw_ostream.h"
21 
22 #include <cassert>
23 
24 namespace mlir {
25 namespace presburger {
26 
27 /// This is a class to represent a resizable matrix.
28 ///
29 /// More columns and rows can be reserved than are currently used. The data is
30 /// stored as a single 1D array, viewed as a 2D matrix with nRows rows and
31 /// nReservedColumns columns, stored in row major form. Thus the element at
32 /// (i, j) is stored at data[i*nReservedColumns + j]. The reserved but unused
33 /// columns always have all zero values. The reserved rows are just reserved
34 /// space in the underlying SmallVector's capacity.
35 class Matrix {
36 public:
37  Matrix() = delete;
38 
39  /// Construct a matrix with the specified number of rows and columns.
40  /// The number of reserved rows and columns will be at least the number
41  /// specified, and will always be sufficient to accomodate the number of rows
42  /// and columns specified.
43  ///
44  /// Initially, the entries are initialized to ero.
45  Matrix(unsigned rows, unsigned columns, unsigned reservedRows = 0,
46  unsigned reservedColumns = 0);
47 
48  /// Return the identity matrix of the specified dimension.
49  static Matrix identity(unsigned dimension);
50 
51  /// Access the element at the specified row and column.
52  MPInt &at(unsigned row, unsigned column) {
53  assert(row < nRows && "Row outside of range");
54  assert(column < nColumns && "Column outside of range");
55  return data[row * nReservedColumns + column];
56  }
57 
58  MPInt at(unsigned row, unsigned column) const {
59  assert(row < nRows && "Row outside of range");
60  assert(column < nColumns && "Column outside of range");
61  return data[row * nReservedColumns + column];
62  }
63 
64  MPInt &operator()(unsigned row, unsigned column) { return at(row, column); }
65 
66  MPInt operator()(unsigned row, unsigned column) const {
67  return at(row, column);
68  }
69 
70  /// Swap the given columns.
71  void swapColumns(unsigned column, unsigned otherColumn);
72 
73  /// Swap the given rows.
74  void swapRows(unsigned row, unsigned otherRow);
75 
76  unsigned getNumRows() const { return nRows; }
77 
78  unsigned getNumColumns() const { return nColumns; }
79 
80  /// Return the maximum number of rows/columns that can be added without
81  /// incurring a reallocation.
82  unsigned getNumReservedRows() const;
83  unsigned getNumReservedColumns() const { return nReservedColumns; }
84 
85  /// Reserve enough space to resize to the specified number of rows without
86  /// reallocations.
87  void reserveRows(unsigned rows);
88 
89  /// Get a [Mutable]ArrayRef corresponding to the specified row.
90  MutableArrayRef<MPInt> getRow(unsigned row);
91  ArrayRef<MPInt> getRow(unsigned row) const;
92 
93  /// Set the specified row to `elems`.
94  void setRow(unsigned row, ArrayRef<MPInt> elems);
95 
96  /// Insert columns having positions pos, pos + 1, ... pos + count - 1.
97  /// Columns that were at positions 0 to pos - 1 will stay where they are;
98  /// columns that were at positions pos to nColumns - 1 will be pushed to the
99  /// right. pos should be at most nColumns.
100  void insertColumns(unsigned pos, unsigned count);
101  void insertColumn(unsigned pos);
102 
103  /// Insert rows having positions pos, pos + 1, ... pos + count - 1.
104  /// Rows that were at positions 0 to pos - 1 will stay where they are;
105  /// rows that were at positions pos to nColumns - 1 will be pushed to the
106  /// right. pos should be at most nRows.
107  void insertRows(unsigned pos, unsigned count);
108  void insertRow(unsigned pos);
109 
110  /// Remove the columns having positions pos, pos + 1, ... pos + count - 1.
111  /// Rows that were at positions 0 to pos - 1 will stay where they are;
112  /// columns that were at positions pos + count - 1 or later will be pushed to
113  /// the right. The columns to be deleted must be valid rows: pos + count - 1
114  /// must be at most nColumns - 1.
115  void removeColumns(unsigned pos, unsigned count);
116  void removeColumn(unsigned pos);
117 
118  /// Remove the rows having positions pos, pos + 1, ... pos + count - 1.
119  /// Rows that were at positions 0 to pos - 1 will stay where they are;
120  /// rows that were at positions pos + count - 1 or later will be pushed to the
121  /// right. The rows to be deleted must be valid rows: pos + count - 1 must be
122  /// at most nRows - 1.
123  void removeRows(unsigned pos, unsigned count);
124  void removeRow(unsigned pos);
125 
126  void copyRow(unsigned sourceRow, unsigned targetRow);
127 
128  void fillRow(unsigned row, const MPInt &value);
129  void fillRow(unsigned row, int64_t value) { fillRow(row, MPInt(value)); }
130 
131  /// Add `scale` multiples of the source row to the target row.
132  void addToRow(unsigned sourceRow, unsigned targetRow, const MPInt &scale);
133  void addToRow(unsigned sourceRow, unsigned targetRow, int64_t scale) {
134  addToRow(sourceRow, targetRow, MPInt(scale));
135  }
136  /// Add `scale` multiples of the rowVec row to the specified row.
137  void addToRow(unsigned row, ArrayRef<MPInt> rowVec, const MPInt &scale);
138 
139  /// Add `scale` multiples of the source column to the target column.
140  void addToColumn(unsigned sourceColumn, unsigned targetColumn,
141  const MPInt &scale);
142  void addToColumn(unsigned sourceColumn, unsigned targetColumn,
143  int64_t scale) {
144  addToColumn(sourceColumn, targetColumn, MPInt(scale));
145  }
146 
147  /// Negate the specified column.
148  void negateColumn(unsigned column);
149 
150  /// Negate the specified row.
151  void negateRow(unsigned row);
152 
153  /// Divide the first `nCols` of the specified row by their GCD.
154  /// Returns the GCD of the first `nCols` of the specified row.
155  MPInt normalizeRow(unsigned row, unsigned nCols);
156  /// Divide the columns of the specified row by their GCD.
157  /// Returns the GCD of the columns of the specified row.
158  MPInt normalizeRow(unsigned row);
159 
160  /// The given vector is interpreted as a row vector v. Post-multiply v with
161  /// this matrix, say M, and return vM.
163 
164  /// The given vector is interpreted as a column vector v. Pre-multiply v with
165  /// this matrix, say M, and return Mv.
167 
168  /// Given the current matrix M, returns the matrices H, U such that H is the
169  /// column hermite normal form of M, i.e. H = M * U, where U is unimodular and
170  /// the matrix H has the following restrictions:
171  /// - H is lower triangular.
172  /// - The leading coefficient (the first non-zero entry from the top, called
173  /// the pivot) of a non-zero column is always strictly below of the leading
174  /// coefficient of the column before it; moreover, it is positive.
175  /// - The elements to the right of the pivots are zero and the elements to
176  /// the left of the pivots are nonnegative and strictly smaller than the
177  /// pivot.
178  std::pair<Matrix, Matrix> computeHermiteNormalForm() const;
179 
180  /// Resize the matrix to the specified dimensions. If a dimension is smaller,
181  /// the values are truncated; if it is bigger, the new values are initialized
182  /// to zero.
183  ///
184  /// Due to the representation of the matrix, resizing vertically (adding rows)
185  /// is less expensive than increasing the number of columns beyond
186  /// nReservedColumns.
187  void resize(unsigned newNRows, unsigned newNColumns);
188  void resizeHorizontally(unsigned newNColumns);
189  void resizeVertically(unsigned newNRows);
190 
191  /// Add an extra row at the bottom of the matrix and return its position.
192  unsigned appendExtraRow();
193  /// Same as above, but copy the given elements into the row. The length of
194  /// `elems` must be equal to the number of columns.
195  unsigned appendExtraRow(ArrayRef<MPInt> elems);
196 
197  /// Print the matrix.
198  void print(raw_ostream &os) const;
199  void dump() const;
200 
201  /// Return whether the Matrix is in a consistent state with all its
202  /// invariants satisfied.
203  bool hasConsistentState() const;
204 
205 private:
206  /// The current number of rows, columns, and reserved columns. The underlying
207  /// data vector is viewed as an nRows x nReservedColumns matrix, of which the
208  /// first nColumns columns are currently in use, and the remaining are
209  /// reserved columns filled with zeros.
210  unsigned nRows, nColumns, nReservedColumns;
211 
212  /// Stores the data. data.size() is equal to nRows * nReservedColumns.
213  /// data.capacity() / nReservedColumns is the number of reserved rows.
215 };
216 
217 } // namespace presburger
218 } // namespace mlir
219 
220 #endif // MLIR_ANALYSIS_PRESBURGER_MATRIX_H
This class provides support for multi-precision arithmetic.
Definition: MPInt.h:87
This is a class to represent a resizable matrix.
Definition: Matrix.h:35
void addToColumn(unsigned sourceColumn, unsigned targetColumn, int64_t scale)
Definition: Matrix.h:142
bool hasConsistentState() const
Return whether the Matrix is in a consistent state with all its invariants satisfied.
Definition: Matrix.cpp:365
void insertRows(unsigned pos, unsigned count)
Insert rows having positions pos, pos + 1, ...
Definition: Matrix.cpp:159
void swapColumns(unsigned column, unsigned otherColumn)
Swap the given columns.
Definition: Matrix.cpp:78
MPInt & operator()(unsigned row, unsigned column)
Definition: Matrix.h:64
void removeColumn(unsigned pos)
Definition: Matrix.cpp:144
unsigned appendExtraRow()
Add an extra row at the bottom of the matrix and return its position.
Definition: Matrix.cpp:39
unsigned getNumReservedColumns() const
Definition: Matrix.h:83
void print(raw_ostream &os) const
Print the matrix.
Definition: Matrix.cpp:355
void copyRow(unsigned sourceRow, unsigned targetRow)
Definition: Matrix.cpp:182
void addToRow(unsigned sourceRow, unsigned targetRow, int64_t scale)
Definition: Matrix.h:133
void insertColumn(unsigned pos)
Definition: Matrix.cpp:102
SmallVector< MPInt, 8 > postMultiplyWithColumn(ArrayRef< MPInt > colVec) const
The given vector is interpreted as a column vector v.
Definition: Matrix.cpp:244
static Matrix identity(unsigned dimension)
Return the identity matrix of the specified dimension.
Definition: Matrix.cpp:24
void removeColumns(unsigned pos, unsigned count)
Remove the columns having positions pos, pos + 1, ...
Definition: Matrix.cpp:145
void insertColumns(unsigned pos, unsigned count)
Insert columns having positions pos, pos + 1, ...
Definition: Matrix.cpp:103
MPInt normalizeRow(unsigned row, unsigned nCols)
Divide the first nCols of the specified row by their GCD.
Definition: Matrix.cpp:225
MPInt & at(unsigned row, unsigned column)
Access the element at the specified row and column.
Definition: Matrix.h:52
SmallVector< MPInt, 8 > preMultiplyWithRow(ArrayRef< MPInt > rowVec) const
The given vector is interpreted as a row vector v.
Definition: Matrix.cpp:233
void removeRow(unsigned pos)
Definition: Matrix.cpp:172
MPInt operator()(unsigned row, unsigned column) const
Definition: Matrix.h:66
void resizeVertically(unsigned newNRows)
Definition: Matrix.cpp:64
void setRow(unsigned row, ArrayRef< MPInt > elems)
Set the specified row to elems.
Definition: Matrix.cpp:95
unsigned getNumReservedRows() const
Return the maximum number of rows/columns that can be added without incurring a reallocation.
Definition: Matrix.cpp:31
unsigned getNumColumns() const
Definition: Matrix.h:78
void fillRow(unsigned row, int64_t value)
Definition: Matrix.h:129
void fillRow(unsigned row, const MPInt &value)
Definition: Matrix.cpp:189
unsigned getNumRows() const
Definition: Matrix.h:76
void addToColumn(unsigned sourceColumn, unsigned targetColumn, const MPInt &scale)
Add scale multiples of the source column to the target column.
Definition: Matrix.cpp:207
void insertRow(unsigned pos)
Definition: Matrix.cpp:158
MPInt at(unsigned row, unsigned column) const
Definition: Matrix.h:58
void swapRows(unsigned row, unsigned otherRow)
Swap the given rows.
Definition: Matrix.cpp:69
void resizeHorizontally(unsigned newNColumns)
Definition: Matrix.cpp:52
void addToRow(unsigned sourceRow, unsigned targetRow, const MPInt &scale)
Add scale multiples of the source row to the target row.
Definition: Matrix.cpp:194
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...
Definition: Matrix.cpp:269
void reserveRows(unsigned rows)
Reserve enough space to resize to the specified number of rows without reallocations.
Definition: Matrix.cpp:35
void negateColumn(unsigned column)
Negate the specified column.
Definition: Matrix.cpp:215
void resize(unsigned newNRows, unsigned newNColumns)
Resize the matrix to the specified dimensions.
Definition: Matrix.cpp:59
MutableArrayRef< MPInt > getRow(unsigned row)
Get a [Mutable]ArrayRef corresponding to the specified row.
Definition: Matrix.cpp:87
void negateRow(unsigned row)
Negate the specified row.
Definition: Matrix.cpp:220
void removeRows(unsigned pos, unsigned count)
Remove the rows having positions pos, pos + 1, ...
Definition: Matrix.cpp:173
Include the generated interface declarations.