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::resizeVertically(unsigned newNRows) {
69   nRows = newNRows;
70   data.resize(nRows * nReservedColumns);
71 }
72 
73 void Matrix::swapRows(unsigned row, unsigned otherRow) {
74   assert((row < getNumRows() && otherRow < getNumRows()) &&
75          "Given row out of bounds");
76   if (row == otherRow)
77     return;
78   for (unsigned col = 0; col < nColumns; col++)
79     std::swap(at(row, col), at(otherRow, col));
80 }
81 
82 void Matrix::swapColumns(unsigned column, unsigned otherColumn) {
83   assert((column < getNumColumns() && otherColumn < getNumColumns()) &&
84          "Given column out of bounds");
85   if (column == otherColumn)
86     return;
87   for (unsigned row = 0; row < nRows; row++)
88     std::swap(at(row, column), at(row, otherColumn));
89 }
90 
91 ArrayRef<int64_t> Matrix::getRow(unsigned row) const {
92   return {&data[row * nReservedColumns], nColumns};
93 }
94 
95 void Matrix::insertColumn(unsigned pos) { insertColumns(pos, 1); }
96 void Matrix::insertColumns(unsigned pos, unsigned count) {
97   if (count == 0)
98     return;
99   assert(pos <= nColumns);
100   unsigned oldNReservedColumns = nReservedColumns;
101   if (nColumns + count > nReservedColumns) {
102     nReservedColumns = llvm::NextPowerOf2(nColumns + count);
103     data.resize(nRows * nReservedColumns);
104   }
105   nColumns += count;
106 
107   for (int ri = nRows - 1; ri >= 0; --ri) {
108     for (int ci = nReservedColumns - 1; ci >= 0; --ci) {
109       unsigned r = ri;
110       unsigned c = ci;
111       int64_t &dest = data[r * nReservedColumns + c];
112       if (c >= nColumns)
113         dest = 0;
114       else if (c >= pos + count)
115         dest = data[r * oldNReservedColumns + c - count];
116       else if (c >= pos)
117         dest = 0;
118       else
119         dest = data[r * oldNReservedColumns + c];
120     }
121   }
122 }
123 
124 void Matrix::removeColumn(unsigned pos) { removeColumns(pos, 1); }
125 void Matrix::removeColumns(unsigned pos, unsigned count) {
126   if (count == 0)
127     return;
128   assert(pos + count - 1 < nColumns);
129   for (unsigned r = 0; r < nRows; ++r) {
130     for (unsigned c = pos; c < nColumns - count; ++c)
131       at(r, c) = at(r, c + count);
132     for (unsigned c = nColumns - count; c < nColumns; ++c)
133       at(r, c) = 0;
134   }
135   nColumns -= count;
136 }
137 
138 void Matrix::insertRow(unsigned pos) { insertRows(pos, 1); }
139 void Matrix::insertRows(unsigned pos, unsigned count) {
140   if (count == 0)
141     return;
142 
143   assert(pos <= nRows);
144   resizeVertically(nRows + count);
145   for (int r = nRows - 1; r >= int(pos + count); --r)
146     copyRow(r - count, r);
147   for (int r = pos + count - 1; r >= int(pos); --r)
148     for (unsigned c = 0; c < nColumns; ++c)
149       at(r, c) = 0;
150 }
151 
152 void Matrix::removeRow(unsigned pos) { removeRows(pos, 1); }
153 void Matrix::removeRows(unsigned pos, unsigned count) {
154   if (count == 0)
155     return;
156   assert(pos + count - 1 <= nRows);
157   for (unsigned r = pos; r + count < nRows; ++r)
158     copyRow(r + count, r);
159   resizeVertically(nRows - count);
160 }
161 
162 void Matrix::copyRow(unsigned sourceRow, unsigned targetRow) {
163   if (sourceRow == targetRow)
164     return;
165   for (unsigned c = 0; c < nColumns; ++c)
166     at(targetRow, c) = at(sourceRow, c);
167 }
168 
169 void Matrix::addToRow(unsigned sourceRow, unsigned targetRow, int64_t scale) {
170   if (scale == 0)
171     return;
172   for (unsigned col = 0; col < nColumns; ++col)
173     at(targetRow, col) += scale * at(sourceRow, col);
174 }
175 
176 void Matrix::addToColumn(unsigned sourceColumn, unsigned targetColumn,
177                          int64_t scale) {
178   if (scale == 0)
179     return;
180   for (unsigned row = 0, e = getNumRows(); row < e; ++row)
181     at(row, targetColumn) += scale * at(row, sourceColumn);
182 }
183 
184 void Matrix::negateColumn(unsigned column) {
185   for (unsigned row = 0, e = getNumRows(); row < e; ++row)
186     at(row, column) = -at(row, column);
187 }
188 
189 void Matrix::print(raw_ostream &os) const {
190   for (unsigned row = 0; row < nRows; ++row) {
191     for (unsigned column = 0; column < nColumns; ++column)
192       os << at(row, column) << ' ';
193     os << '\n';
194   }
195 }
196 
197 void Matrix::dump() const { print(llvm::errs()); }
198 
199 bool Matrix::hasConsistentState() const {
200   if (data.size() != nRows * nReservedColumns)
201     return false;
202   if (nColumns > nReservedColumns)
203     return false;
204   for (unsigned r = 0; r < nRows; ++r)
205     for (unsigned c = nColumns; c < nReservedColumns; ++c)
206       if (data[r * nReservedColumns + c] != 0)
207         return false;
208   return true;
209 }
210 
211 } // namespace mlir
212