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. at(unsigned row,unsigned 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 at(unsigned row,unsigned column)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 operator()63 int64_t &operator()(unsigned row, unsigned column) { return at(row, column); } 64 operator()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 getNumRows()75 unsigned getNumRows() const { return nRows; } 76 getNumColumns()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; getNumReservedColumns()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. 150 SmallVector<int64_t, 8> preMultiplyWithRow(ArrayRef<int64_t> rowVec) const; 151 152 /// The given vector is interpreted as a column vector v. Pre-multiply v with 153 /// this matrix, say M, and return Mv. 154 SmallVector<int64_t, 8> 155 postMultiplyWithColumn(ArrayRef<int64_t> colVec) const; 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. 191 SmallVector<int64_t, 64> data; 192 }; 193 194 } // namespace presburger 195 } // namespace mlir 196 197 #endif // MLIR_ANALYSIS_PRESBURGER_MATRIX_H 198