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 namespace mlir {
13 
14 Matrix::Matrix(unsigned rows, unsigned columns, unsigned reservedRows,
15                unsigned reservedColumns)
16     : nRows(rows), nColumns(columns),
17       nReservedColumns(std::max(nColumns, reservedColumns)),
18       data(nRows * nReservedColumns) {
19   data.reserve(std::max(nRows, reservedRows) * nReservedColumns);
20 }
21 
22 Matrix Matrix::identity(unsigned dimension) {
23   Matrix matrix(dimension, dimension);
24   for (unsigned i = 0; i < dimension; ++i)
25     matrix(i, i) = 1;
26   return matrix;
27 }
28 
29 int64_t &Matrix::at(unsigned row, unsigned column) {
30   assert(row < nRows && "Row outside of range");
31   assert(column < nColumns && "Column outside of range");
32   return data[row * nReservedColumns + column];
33 }
34 
35 int64_t Matrix::at(unsigned row, unsigned column) const {
36   assert(row < nRows && "Row outside of range");
37   assert(column < nColumns && "Column outside of range");
38   return data[row * nReservedColumns + column];
39 }
40 
41 int64_t &Matrix::operator()(unsigned row, unsigned column) {
42   return at(row, column);
43 }
44 
45 int64_t Matrix::operator()(unsigned row, unsigned column) const {
46   return at(row, column);
47 }
48 
49 unsigned Matrix::getNumRows() const { return nRows; }
50 
51 unsigned Matrix::getNumColumns() const { return nColumns; }
52 
53 unsigned Matrix::getNumReservedColumns() const { return nReservedColumns; }
54 
55 unsigned Matrix::getNumReservedRows() const {
56   return data.capacity() / nReservedColumns;
57 }
58 
59 void Matrix::reserveRows(unsigned rows) {
60   data.reserve(rows * nReservedColumns);
61 }
62 
63 unsigned Matrix::appendExtraRow() {
64   resizeVertically(nRows + 1);
65   return nRows - 1;
66 }
67 
68 void Matrix::resizeHorizontally(unsigned newNColumns) {
69   if (newNColumns < nColumns)
70     removeColumns(newNColumns, nColumns - newNColumns);
71   if (newNColumns > nColumns)
72     insertColumns(nColumns, newNColumns - nColumns);
73 }
74 
75 void Matrix::resize(unsigned newNRows, unsigned newNColumns) {
76   resizeHorizontally(newNColumns);
77   resizeVertically(newNRows);
78 }
79 
80 void Matrix::resizeVertically(unsigned newNRows) {
81   nRows = newNRows;
82   data.resize(nRows * nReservedColumns);
83 }
84 
85 void Matrix::swapRows(unsigned row, unsigned otherRow) {
86   assert((row < getNumRows() && otherRow < getNumRows()) &&
87          "Given row out of bounds");
88   if (row == otherRow)
89     return;
90   for (unsigned col = 0; col < nColumns; col++)
91     std::swap(at(row, col), at(otherRow, col));
92 }
93 
94 void Matrix::swapColumns(unsigned column, unsigned otherColumn) {
95   assert((column < getNumColumns() && otherColumn < getNumColumns()) &&
96          "Given column out of bounds");
97   if (column == otherColumn)
98     return;
99   for (unsigned row = 0; row < nRows; row++)
100     std::swap(at(row, column), at(row, otherColumn));
101 }
102 
103 ArrayRef<int64_t> Matrix::getRow(unsigned row) const {
104   return {&data[row * nReservedColumns], nColumns};
105 }
106 
107 void Matrix::insertColumn(unsigned pos) { insertColumns(pos, 1); }
108 void Matrix::insertColumns(unsigned pos, unsigned count) {
109   if (count == 0)
110     return;
111   assert(pos <= nColumns);
112   unsigned oldNReservedColumns = nReservedColumns;
113   if (nColumns + count > nReservedColumns) {
114     nReservedColumns = llvm::NextPowerOf2(nColumns + count);
115     data.resize(nRows * nReservedColumns);
116   }
117   nColumns += count;
118 
119   for (int ri = nRows - 1; ri >= 0; --ri) {
120     for (int ci = nReservedColumns - 1; ci >= 0; --ci) {
121       unsigned r = ri;
122       unsigned c = ci;
123       int64_t &dest = data[r * nReservedColumns + c];
124       if (c >= nColumns)
125         dest = 0;
126       else if (c >= pos + count)
127         dest = data[r * oldNReservedColumns + c - count];
128       else if (c >= pos)
129         dest = 0;
130       else
131         dest = data[r * oldNReservedColumns + c];
132     }
133   }
134 }
135 
136 void Matrix::removeColumn(unsigned pos) { removeColumns(pos, 1); }
137 void Matrix::removeColumns(unsigned pos, unsigned count) {
138   if (count == 0)
139     return;
140   assert(pos + count - 1 < nColumns);
141   for (unsigned r = 0; r < nRows; ++r) {
142     for (unsigned c = pos; c < nColumns - count; ++c)
143       at(r, c) = at(r, c + count);
144     for (unsigned c = nColumns - count; c < nColumns; ++c)
145       at(r, c) = 0;
146   }
147   nColumns -= count;
148 }
149 
150 void Matrix::insertRow(unsigned pos) { insertRows(pos, 1); }
151 void Matrix::insertRows(unsigned pos, unsigned count) {
152   if (count == 0)
153     return;
154 
155   assert(pos <= nRows);
156   resizeVertically(nRows + count);
157   for (int r = nRows - 1; r >= int(pos + count); --r)
158     copyRow(r - count, r);
159   for (int r = pos + count - 1; r >= int(pos); --r)
160     for (unsigned c = 0; c < nColumns; ++c)
161       at(r, c) = 0;
162 }
163 
164 void Matrix::removeRow(unsigned pos) { removeRows(pos, 1); }
165 void Matrix::removeRows(unsigned pos, unsigned count) {
166   if (count == 0)
167     return;
168   assert(pos + count - 1 <= nRows);
169   for (unsigned r = pos; r + count < nRows; ++r)
170     copyRow(r + count, r);
171   resizeVertically(nRows - count);
172 }
173 
174 void Matrix::copyRow(unsigned sourceRow, unsigned targetRow) {
175   if (sourceRow == targetRow)
176     return;
177   for (unsigned c = 0; c < nColumns; ++c)
178     at(targetRow, c) = at(sourceRow, c);
179 }
180 
181 void Matrix::addToRow(unsigned sourceRow, unsigned targetRow, int64_t scale) {
182   if (scale == 0)
183     return;
184   for (unsigned col = 0; col < nColumns; ++col)
185     at(targetRow, col) += scale * at(sourceRow, col);
186 }
187 
188 void Matrix::addToColumn(unsigned sourceColumn, unsigned targetColumn,
189                          int64_t scale) {
190   if (scale == 0)
191     return;
192   for (unsigned row = 0, e = getNumRows(); row < e; ++row)
193     at(row, targetColumn) += scale * at(row, sourceColumn);
194 }
195 
196 void Matrix::negateColumn(unsigned column) {
197   for (unsigned row = 0, e = getNumRows(); row < e; ++row)
198     at(row, column) = -at(row, column);
199 }
200 
201 void Matrix::print(raw_ostream &os) const {
202   for (unsigned row = 0; row < nRows; ++row) {
203     for (unsigned column = 0; column < nColumns; ++column)
204       os << at(row, column) << ' ';
205     os << '\n';
206   }
207 }
208 
209 void Matrix::dump() const { print(llvm::errs()); }
210 
211 bool Matrix::hasConsistentState() const {
212   if (data.size() != nRows * nReservedColumns)
213     return false;
214   if (nColumns > nReservedColumns)
215     return false;
216   for (unsigned r = 0; r < nRows; ++r)
217     for (unsigned c = nColumns; c < nReservedColumns; ++c)
218       if (data[r * nReservedColumns + c] != 0)
219         return false;
220   return true;
221 }
222 
223 } // namespace mlir
224