1 //===- Matrix.cpp - MLIR Matrix Class -------------------------------------===//
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 #include "mlir/Analysis/Presburger/Matrix.h"
10 #include "llvm/Support/MathExtras.h"
11 
12 using namespace mlir;
13 using namespace presburger;
14 
15 Matrix::Matrix(unsigned rows, unsigned columns, unsigned reservedRows,
16                unsigned reservedColumns)
17     : nRows(rows), nColumns(columns),
18       nReservedColumns(std::max(nColumns, reservedColumns)),
19       data(nRows * nReservedColumns) {
20   data.reserve(std::max(nRows, reservedRows) * nReservedColumns);
21 }
22 
23 Matrix Matrix::identity(unsigned dimension) {
24   Matrix matrix(dimension, dimension);
25   for (unsigned i = 0; i < dimension; ++i)
26     matrix(i, i) = 1;
27   return matrix;
28 }
29 
30 int64_t &Matrix::at(unsigned row, unsigned column) {
31   assert(row < nRows && "Row outside of range");
32   assert(column < nColumns && "Column outside of range");
33   return data[row * nReservedColumns + column];
34 }
35 
36 int64_t Matrix::at(unsigned row, unsigned column) const {
37   assert(row < nRows && "Row outside of range");
38   assert(column < nColumns && "Column outside of range");
39   return data[row * nReservedColumns + column];
40 }
41 
42 int64_t &Matrix::operator()(unsigned row, unsigned column) {
43   return at(row, column);
44 }
45 
46 int64_t Matrix::operator()(unsigned row, unsigned column) const {
47   return at(row, column);
48 }
49 
50 unsigned Matrix::getNumRows() const { return nRows; }
51 
52 unsigned Matrix::getNumColumns() const { return nColumns; }
53 
54 unsigned Matrix::getNumReservedColumns() const { return nReservedColumns; }
55 
56 unsigned Matrix::getNumReservedRows() const {
57   return data.capacity() / nReservedColumns;
58 }
59 
60 void Matrix::reserveRows(unsigned rows) {
61   data.reserve(rows * nReservedColumns);
62 }
63 
64 unsigned Matrix::appendExtraRow() {
65   resizeVertically(nRows + 1);
66   return nRows - 1;
67 }
68 
69 void Matrix::resizeHorizontally(unsigned newNColumns) {
70   if (newNColumns < nColumns)
71     removeColumns(newNColumns, nColumns - newNColumns);
72   if (newNColumns > nColumns)
73     insertColumns(nColumns, newNColumns - nColumns);
74 }
75 
76 void Matrix::resize(unsigned newNRows, unsigned newNColumns) {
77   resizeHorizontally(newNColumns);
78   resizeVertically(newNRows);
79 }
80 
81 void Matrix::resizeVertically(unsigned newNRows) {
82   nRows = newNRows;
83   data.resize(nRows * nReservedColumns);
84 }
85 
86 void Matrix::swapRows(unsigned row, unsigned otherRow) {
87   assert((row < getNumRows() && otherRow < getNumRows()) &&
88          "Given row out of bounds");
89   if (row == otherRow)
90     return;
91   for (unsigned col = 0; col < nColumns; col++)
92     std::swap(at(row, col), at(otherRow, col));
93 }
94 
95 void Matrix::swapColumns(unsigned column, unsigned otherColumn) {
96   assert((column < getNumColumns() && otherColumn < getNumColumns()) &&
97          "Given column out of bounds");
98   if (column == otherColumn)
99     return;
100   for (unsigned row = 0; row < nRows; row++)
101     std::swap(at(row, column), at(row, otherColumn));
102 }
103 
104 MutableArrayRef<int64_t> Matrix::getRow(unsigned row) {
105   return {&data[row * nReservedColumns], nColumns};
106 }
107 
108 ArrayRef<int64_t> Matrix::getRow(unsigned row) const {
109   return {&data[row * nReservedColumns], nColumns};
110 }
111 
112 void Matrix::insertColumn(unsigned pos) { insertColumns(pos, 1); }
113 void Matrix::insertColumns(unsigned pos, unsigned count) {
114   if (count == 0)
115     return;
116   assert(pos <= nColumns);
117   unsigned oldNReservedColumns = nReservedColumns;
118   if (nColumns + count > nReservedColumns) {
119     nReservedColumns = llvm::NextPowerOf2(nColumns + count);
120     data.resize(nRows * nReservedColumns);
121   }
122   nColumns += count;
123 
124   for (int ri = nRows - 1; ri >= 0; --ri) {
125     for (int ci = nReservedColumns - 1; ci >= 0; --ci) {
126       unsigned r = ri;
127       unsigned c = ci;
128       int64_t &dest = data[r * nReservedColumns + c];
129       if (c >= nColumns)
130         dest = 0;
131       else if (c >= pos + count)
132         dest = data[r * oldNReservedColumns + c - count];
133       else if (c >= pos)
134         dest = 0;
135       else
136         dest = data[r * oldNReservedColumns + c];
137     }
138   }
139 }
140 
141 void Matrix::removeColumn(unsigned pos) { removeColumns(pos, 1); }
142 void Matrix::removeColumns(unsigned pos, unsigned count) {
143   if (count == 0)
144     return;
145   assert(pos + count - 1 < nColumns);
146   for (unsigned r = 0; r < nRows; ++r) {
147     for (unsigned c = pos; c < nColumns - count; ++c)
148       at(r, c) = at(r, c + count);
149     for (unsigned c = nColumns - count; c < nColumns; ++c)
150       at(r, c) = 0;
151   }
152   nColumns -= count;
153 }
154 
155 void Matrix::insertRow(unsigned pos) { insertRows(pos, 1); }
156 void Matrix::insertRows(unsigned pos, unsigned count) {
157   if (count == 0)
158     return;
159 
160   assert(pos <= nRows);
161   resizeVertically(nRows + count);
162   for (int r = nRows - 1; r >= int(pos + count); --r)
163     copyRow(r - count, r);
164   for (int r = pos + count - 1; r >= int(pos); --r)
165     for (unsigned c = 0; c < nColumns; ++c)
166       at(r, c) = 0;
167 }
168 
169 void Matrix::removeRow(unsigned pos) { removeRows(pos, 1); }
170 void Matrix::removeRows(unsigned pos, unsigned count) {
171   if (count == 0)
172     return;
173   assert(pos + count - 1 <= nRows);
174   for (unsigned r = pos; r + count < nRows; ++r)
175     copyRow(r + count, r);
176   resizeVertically(nRows - count);
177 }
178 
179 void Matrix::copyRow(unsigned sourceRow, unsigned targetRow) {
180   if (sourceRow == targetRow)
181     return;
182   for (unsigned c = 0; c < nColumns; ++c)
183     at(targetRow, c) = at(sourceRow, c);
184 }
185 
186 void Matrix::fillRow(unsigned row, int64_t value) {
187   for (unsigned col = 0; col < nColumns; ++col)
188     at(row, col) = value;
189 }
190 
191 void Matrix::addToRow(unsigned sourceRow, unsigned targetRow, int64_t scale) {
192   if (scale == 0)
193     return;
194   for (unsigned col = 0; col < nColumns; ++col)
195     at(targetRow, col) += scale * at(sourceRow, col);
196 }
197 
198 void Matrix::addToColumn(unsigned sourceColumn, unsigned targetColumn,
199                          int64_t scale) {
200   if (scale == 0)
201     return;
202   for (unsigned row = 0, e = getNumRows(); row < e; ++row)
203     at(row, targetColumn) += scale * at(row, sourceColumn);
204 }
205 
206 void Matrix::negateColumn(unsigned column) {
207   for (unsigned row = 0, e = getNumRows(); row < e; ++row)
208     at(row, column) = -at(row, column);
209 }
210 
211 void Matrix::negateRow(unsigned row) {
212   for (unsigned column = 0, e = getNumColumns(); column < e; ++column)
213     at(row, column) = -at(row, column);
214 }
215 
216 uint64_t Matrix::normalizeRow(unsigned row, unsigned cols) {
217   if (cols == 0)
218     return 0;
219 
220   int64_t gcd = std::abs(at(row, 0));
221   for (unsigned j = 1, e = cols; j < e; ++j)
222     gcd = llvm::GreatestCommonDivisor64(gcd, std::abs(at(row, j)));
223 
224   if (gcd > 1)
225     for (unsigned j = 0, e = cols; j < e; ++j)
226       at(row, j) /= gcd;
227 
228   return gcd;
229 }
230 
231 uint64_t Matrix::normalizeRow(unsigned row) {
232   return normalizeRow(row, getNumColumns());
233 }
234 
235 SmallVector<int64_t, 8>
236 Matrix::preMultiplyWithRow(ArrayRef<int64_t> rowVec) const {
237   assert(rowVec.size() == getNumRows() && "Invalid row vector dimension!");
238 
239   SmallVector<int64_t, 8> result(getNumColumns(), 0);
240   for (unsigned col = 0, e = getNumColumns(); col < e; ++col)
241     for (unsigned i = 0, e = getNumRows(); i < e; ++i)
242       result[col] += rowVec[i] * at(i, col);
243   return result;
244 }
245 
246 SmallVector<int64_t, 8>
247 Matrix::postMultiplyWithColumn(ArrayRef<int64_t> colVec) const {
248   assert(getNumColumns() == colVec.size() &&
249          "Invalid column vector dimension!");
250 
251   SmallVector<int64_t, 8> result(getNumRows(), 0);
252   for (unsigned row = 0, e = getNumRows(); row < e; row++)
253     for (unsigned i = 0, e = getNumColumns(); i < e; i++)
254       result[row] += at(row, i) * colVec[i];
255   return result;
256 }
257 
258 void Matrix::print(raw_ostream &os) const {
259   for (unsigned row = 0; row < nRows; ++row) {
260     for (unsigned column = 0; column < nColumns; ++column)
261       os << at(row, column) << ' ';
262     os << '\n';
263   }
264 }
265 
266 void Matrix::dump() const { print(llvm::errs()); }
267 
268 bool Matrix::hasConsistentState() const {
269   if (data.size() != nRows * nReservedColumns)
270     return false;
271   if (nColumns > nReservedColumns)
272     return false;
273   for (unsigned r = 0; r < nRows; ++r)
274     for (unsigned c = nColumns; c < nReservedColumns; ++c)
275       if (data[r * nReservedColumns + c] != 0)
276         return false;
277   return true;
278 }
279