MLIR  16.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 
17 #include "mlir/Support/LLVM.h"
18 #include "llvm/ADT/ArrayRef.h"
19 #include "llvm/Support/raw_ostream.h"
20 
21 #include <cassert>
22 
23 namespace mlir {
24 namespace presburger {
25 
26 /// This is a class to represent a resizable matrix.
27 ///
28 /// More columns and rows can be reserved than are currently used. The data is
29 /// stored as a single 1D array, viewed as a 2D matrix with nRows rows and
30 /// nReservedColumns columns, stored in row major form. Thus the element at
31 /// (i, j) is stored at data[i*nReservedColumns + j]. The reserved but unused
32 /// columns always have all zero values. The reserved rows are just reserved
33 /// space in the underlying SmallVector's capacity.
34 class Matrix {
35 public:
36  Matrix() = delete;
37 
38  /// Construct a matrix with the specified number of rows and columns.
39  /// The number of reserved rows and columns will be at least the number
40  /// specified, and will always be sufficient to accomodate the number of rows
41  /// and columns specified.
42  ///
43  /// Initially, the entries are initialized to ero.
44  Matrix(unsigned rows, unsigned columns, unsigned reservedRows = 0,
45  unsigned reservedColumns = 0);
46 
47  /// Return the identity matrix of the specified dimension.
48  static Matrix identity(unsigned dimension);
49 
50  /// Access the element at the specified row and column.
51  int64_t &at(unsigned row, unsigned column) {
52  assert(row < nRows && "Row outside of range");
53  assert(column < nColumns && "Column outside of range");
54  return data[row * nReservedColumns + column];
55  }
56 
57  int64_t at(unsigned row, unsigned column) const {
58  assert(row < nRows && "Row outside of range");
59  assert(column < nColumns && "Column outside of range");
60  return data[row * nReservedColumns + column];
61  }
62 
63  int64_t &operator()(unsigned row, unsigned column) { return at(row, column); }
64 
65  int64_t operator()(unsigned row, unsigned column) const {
66  return at(row, column);
67  }
68 
69  /// Swap the given columns.
70  void swapColumns(unsigned column, unsigned otherColumn);
71 
72  /// Swap the given rows.
73  void swapRows(unsigned row, unsigned otherRow);
74 
75  unsigned getNumRows() const { return nRows; }
76 
77  unsigned getNumColumns() const { return nColumns; }
78 
79  /// Return the maximum number of rows/columns that can be added without
80  /// incurring a reallocation.
81  unsigned getNumReservedRows() const;
82  unsigned getNumReservedColumns() const { return nReservedColumns; }
83 
84  /// Reserve enough space to resize to the specified number of rows without
85  /// reallocations.
86  void reserveRows(unsigned rows);
87 
88  /// Get a [Mutable]ArrayRef corresponding to the specified row.
89  MutableArrayRef<int64_t> getRow(unsigned row);
90  ArrayRef<int64_t> getRow(unsigned row) const;
91 
92  /// Set the specified row to `elems`.
93  void setRow(unsigned row, ArrayRef<int64_t> elems);
94 
95  /// Insert columns having positions pos, pos + 1, ... pos + count - 1.
96  /// Columns that were at positions 0 to pos - 1 will stay where they are;
97  /// columns that were at positions pos to nColumns - 1 will be pushed to the
98  /// right. pos should be at most nColumns.
99  void insertColumns(unsigned pos, unsigned count);
100  void insertColumn(unsigned pos);
101 
102  /// Insert rows having positions pos, pos + 1, ... pos + count - 1.
103  /// Rows that were at positions 0 to pos - 1 will stay where they are;
104  /// rows that were at positions pos to nColumns - 1 will be pushed to the
105  /// right. pos should be at most nRows.
106  void insertRows(unsigned pos, unsigned count);
107  void insertRow(unsigned pos);
108 
109  /// Remove the columns having positions pos, pos + 1, ... pos + count - 1.
110  /// Rows that were at positions 0 to pos - 1 will stay where they are;
111  /// columns that were at positions pos + count - 1 or later will be pushed to
112  /// the right. The columns to be deleted must be valid rows: pos + count - 1
113  /// must be at most nColumns - 1.
114  void removeColumns(unsigned pos, unsigned count);
115  void removeColumn(unsigned pos);
116 
117  /// Remove the rows having positions pos, pos + 1, ... pos + count - 1.
118  /// Rows that were at positions 0 to pos - 1 will stay where they are;
119  /// rows that were at positions pos + count - 1 or later will be pushed to the
120  /// right. The rows to be deleted must be valid rows: pos + count - 1 must be
121  /// at most nRows - 1.
122  void removeRows(unsigned pos, unsigned count);
123  void removeRow(unsigned pos);
124 
125  void copyRow(unsigned sourceRow, unsigned targetRow);
126 
127  void fillRow(unsigned row, int64_t value);
128 
129  /// Add `scale` multiples of the source row to the target row.
130  void addToRow(unsigned sourceRow, unsigned targetRow, int64_t scale);
131 
132  /// Add `scale` multiples of the source column to the target column.
133  void addToColumn(unsigned sourceColumn, unsigned targetColumn, int64_t scale);
134 
135  /// Negate the specified column.
136  void negateColumn(unsigned column);
137 
138  /// Negate the specified row.
139  void negateRow(unsigned row);
140 
141  /// Divide the first `nCols` of the specified row by their GCD.
142  /// Returns the GCD of the first `nCols` of the specified row.
143  int64_t normalizeRow(unsigned row, unsigned nCols);
144  /// Divide the columns of the specified row by their GCD.
145  /// Returns the GCD of the columns of the specified row.
146  int64_t normalizeRow(unsigned row);
147 
148  /// The given vector is interpreted as a row vector v. Post-multiply v with
149  /// this matrix, say M, and return vM.
151 
152  /// The given vector is interpreted as a column vector v. Pre-multiply v with
153  /// this matrix, say M, and return Mv.
156 
157  /// Resize the matrix to the specified dimensions. If a dimension is smaller,
158  /// the values are truncated; if it is bigger, the new values are initialized
159  /// to zero.
160  ///
161  /// Due to the representation of the matrix, resizing vertically (adding rows)
162  /// is less expensive than increasing the number of columns beyond
163  /// nReservedColumns.
164  void resize(unsigned newNRows, unsigned newNColumns);
165  void resizeHorizontally(unsigned newNColumns);
166  void resizeVertically(unsigned newNRows);
167 
168  /// Add an extra row at the bottom of the matrix and return its position.
169  unsigned appendExtraRow();
170  /// Same as above, but copy the given elements into the row. The length of
171  /// `elems` must be equal to the number of columns.
172  unsigned appendExtraRow(ArrayRef<int64_t> elems);
173 
174  /// Print the matrix.
175  void print(raw_ostream &os) const;
176  void dump() const;
177 
178  /// Return whether the Matrix is in a consistent state with all its
179  /// invariants satisfied.
180  bool hasConsistentState() const;
181 
182 private:
183  /// The current number of rows, columns, and reserved columns. The underlying
184  /// data vector is viewed as an nRows x nReservedColumns matrix, of which the
185  /// first nColumns columns are currently in use, and the remaining are
186  /// reserved columns filled with zeros.
187  unsigned nRows, nColumns, nReservedColumns;
188 
189  /// Stores the data. data.size() is equal to nRows * nReservedColumns.
190  /// data.capacity() / nReservedColumns is the number of reserved rows.
192 };
193 
194 } // namespace presburger
195 } // namespace mlir
196 
197 #endif // MLIR_ANALYSIS_PRESBURGER_MATRIX_H
int64_t normalizeRow(unsigned row, unsigned nCols)
Divide the first nCols of the specified row by their GCD.
Definition: Matrix.cpp:219
Include the generated interface declarations.
void insertColumn(unsigned pos)
Definition: Matrix.cpp:102
bool hasConsistentState() const
Return whether the Matrix is in a consistent state with all its invariants satisfied.
Definition: Matrix.cpp:260
void resizeHorizontally(unsigned newNColumns)
Definition: Matrix.cpp:52
void removeRows(unsigned pos, unsigned count)
Remove the rows having positions pos, pos + 1, ...
Definition: Matrix.cpp:173
unsigned getNumRows() const
Definition: Matrix.h:75
void insertRows(unsigned pos, unsigned count)
Insert rows having positions pos, pos + 1, ...
Definition: Matrix.cpp:159
void fillRow(unsigned row, int64_t value)
Definition: Matrix.cpp:189
void addToColumn(unsigned sourceColumn, unsigned targetColumn, int64_t scale)
Add scale multiples of the source column to the target column.
Definition: Matrix.cpp:201
void removeColumn(unsigned pos)
Definition: Matrix.cpp:144
This is a class to represent a resizable matrix.
Definition: Matrix.h:34
void reserveRows(unsigned rows)
Reserve enough space to resize to the specified number of rows without reallocations.
Definition: Matrix.cpp:35
static Matrix identity(unsigned dimension)
Return the identity matrix of the specified dimension.
Definition: Matrix.cpp:24
static constexpr const bool value
void swapColumns(unsigned column, unsigned otherColumn)
Swap the given columns.
Definition: Matrix.cpp:78
void copyRow(unsigned sourceRow, unsigned targetRow)
Definition: Matrix.cpp:182
void insertColumns(unsigned pos, unsigned count)
Insert columns having positions pos, pos + 1, ...
Definition: Matrix.cpp:103
void removeRow(unsigned pos)
Definition: Matrix.cpp:172
int64_t operator()(unsigned row, unsigned column) const
Definition: Matrix.h:65
unsigned getNumReservedRows() const
Return the maximum number of rows/columns that can be added without incurring a reallocation.
Definition: Matrix.cpp:31
void addToRow(unsigned sourceRow, unsigned targetRow, int64_t scale)
Add scale multiples of the source row to the target row.
Definition: Matrix.cpp:194
unsigned appendExtraRow()
Add an extra row at the bottom of the matrix and return its position.
Definition: Matrix.cpp:39
SmallVector< int64_t, 8 > postMultiplyWithColumn(ArrayRef< int64_t > colVec) const
The given vector is interpreted as a column vector v.
Definition: Matrix.cpp:239
void negateRow(unsigned row)
Negate the specified row.
Definition: Matrix.cpp:214
void resizeVertically(unsigned newNRows)
Definition: Matrix.cpp:64
void setRow(unsigned row, ArrayRef< int64_t > elems)
Set the specified row to elems.
Definition: Matrix.cpp:95
unsigned getNumColumns() const
Definition: Matrix.h:77
int64_t & at(unsigned row, unsigned column)
Access the element at the specified row and column.
Definition: Matrix.h:51
MutableArrayRef< int64_t > getRow(unsigned row)
Get a [Mutable]ArrayRef corresponding to the specified row.
Definition: Matrix.cpp:87
void resize(unsigned newNRows, unsigned newNColumns)
Resize the matrix to the specified dimensions.
Definition: Matrix.cpp:59
void swapRows(unsigned row, unsigned otherRow)
Swap the given rows.
Definition: Matrix.cpp:69
void insertRow(unsigned pos)
Definition: Matrix.cpp:158
int64_t at(unsigned row, unsigned column) const
Definition: Matrix.h:57
int64_t & operator()(unsigned row, unsigned column)
Definition: Matrix.h:63
SmallVector< int64_t, 8 > preMultiplyWithRow(ArrayRef< int64_t > rowVec) const
The given vector is interpreted as a row vector v.
Definition: Matrix.cpp:228
void print(raw_ostream &os) const
Print the matrix.
Definition: Matrix.cpp:250
unsigned getNumReservedColumns() const
Definition: Matrix.h:82
void negateColumn(unsigned column)
Negate the specified column.
Definition: Matrix.cpp:209
void removeColumns(unsigned pos, unsigned count)
Remove the columns having positions pos, pos + 1, ...
Definition: Matrix.cpp:145