1 //===------ Math.h - PBQP Vector and Matrix classes -------------*- C++ -*-===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9
10 #ifndef LLVM_CODEGEN_PBQP_MATH_H
11 #define LLVM_CODEGEN_PBQP_MATH_H
12
13 #include "llvm/ADT/Hashing.h"
14 #include <algorithm>
15 #include <cassert>
16 #include <functional>
17
18 namespace llvm {
19 namespace PBQP {
20
21 typedef float PBQPNum;
22
23 /// \brief PBQP Vector class.
24 class Vector {
25 friend hash_code hash_value(const Vector &);
26 public:
27
28 /// \brief Construct a PBQP vector of the given size.
Vector(unsigned Length)29 explicit Vector(unsigned Length)
30 : Length(Length), Data(new PBQPNum[Length]) {
31 // llvm::dbgs() << "Constructing PBQP::Vector "
32 // << this << " (length " << Length << ")\n";
33 }
34
35 /// \brief Construct a PBQP vector with initializer.
Vector(unsigned Length,PBQPNum InitVal)36 Vector(unsigned Length, PBQPNum InitVal)
37 : Length(Length), Data(new PBQPNum[Length]) {
38 // llvm::dbgs() << "Constructing PBQP::Vector "
39 // << this << " (length " << Length << ", fill "
40 // << InitVal << ")\n";
41 std::fill(Data, Data + Length, InitVal);
42 }
43
44 /// \brief Copy construct a PBQP vector.
Vector(const Vector & V)45 Vector(const Vector &V)
46 : Length(V.Length), Data(new PBQPNum[Length]) {
47 // llvm::dbgs() << "Copy-constructing PBQP::Vector " << this
48 // << " from PBQP::Vector " << &V << "\n";
49 std::copy(V.Data, V.Data + Length, Data);
50 }
51
52 /// \brief Move construct a PBQP vector.
Vector(Vector && V)53 Vector(Vector &&V)
54 : Length(V.Length), Data(V.Data) {
55 V.Length = 0;
56 V.Data = nullptr;
57 }
58
59 /// \brief Destroy this vector, return its memory.
~Vector()60 ~Vector() {
61 // llvm::dbgs() << "Deleting PBQP::Vector " << this << "\n";
62 delete[] Data;
63 }
64
65 /// \brief Copy-assignment operator.
66 Vector& operator=(const Vector &V) {
67 // llvm::dbgs() << "Assigning to PBQP::Vector " << this
68 // << " from PBQP::Vector " << &V << "\n";
69 delete[] Data;
70 Length = V.Length;
71 Data = new PBQPNum[Length];
72 std::copy(V.Data, V.Data + Length, Data);
73 return *this;
74 }
75
76 /// \brief Move-assignment operator.
77 Vector& operator=(Vector &&V) {
78 delete[] Data;
79 Length = V.Length;
80 Data = V.Data;
81 V.Length = 0;
82 V.Data = nullptr;
83 return *this;
84 }
85
86 /// \brief Comparison operator.
87 bool operator==(const Vector &V) const {
88 assert(Length != 0 && Data != nullptr && "Invalid vector");
89 if (Length != V.Length)
90 return false;
91 return std::equal(Data, Data + Length, V.Data);
92 }
93
94 /// \brief Return the length of the vector
getLength()95 unsigned getLength() const {
96 assert(Length != 0 && Data != nullptr && "Invalid vector");
97 return Length;
98 }
99
100 /// \brief Element access.
101 PBQPNum& operator[](unsigned Index) {
102 assert(Length != 0 && Data != nullptr && "Invalid vector");
103 assert(Index < Length && "Vector element access out of bounds.");
104 return Data[Index];
105 }
106
107 /// \brief Const element access.
108 const PBQPNum& operator[](unsigned Index) const {
109 assert(Length != 0 && Data != nullptr && "Invalid vector");
110 assert(Index < Length && "Vector element access out of bounds.");
111 return Data[Index];
112 }
113
114 /// \brief Add another vector to this one.
115 Vector& operator+=(const Vector &V) {
116 assert(Length != 0 && Data != nullptr && "Invalid vector");
117 assert(Length == V.Length && "Vector length mismatch.");
118 std::transform(Data, Data + Length, V.Data, Data, std::plus<PBQPNum>());
119 return *this;
120 }
121
122 /// \brief Subtract another vector from this one.
123 Vector& operator-=(const Vector &V) {
124 assert(Length != 0 && Data != nullptr && "Invalid vector");
125 assert(Length == V.Length && "Vector length mismatch.");
126 std::transform(Data, Data + Length, V.Data, Data, std::minus<PBQPNum>());
127 return *this;
128 }
129
130 /// \brief Returns the index of the minimum value in this vector
minIndex()131 unsigned minIndex() const {
132 assert(Length != 0 && Data != nullptr && "Invalid vector");
133 return std::min_element(Data, Data + Length) - Data;
134 }
135
136 private:
137 unsigned Length;
138 PBQPNum *Data;
139 };
140
141 /// \brief Return a hash_value for the given vector.
hash_value(const Vector & V)142 inline hash_code hash_value(const Vector &V) {
143 unsigned *VBegin = reinterpret_cast<unsigned*>(V.Data);
144 unsigned *VEnd = reinterpret_cast<unsigned*>(V.Data + V.Length);
145 return hash_combine(V.Length, hash_combine_range(VBegin, VEnd));
146 }
147
148 /// \brief Output a textual representation of the given vector on the given
149 /// output stream.
150 template <typename OStream>
151 OStream& operator<<(OStream &OS, const Vector &V) {
152 assert((V.getLength() != 0) && "Zero-length vector badness.");
153
154 OS << "[ " << V[0];
155 for (unsigned i = 1; i < V.getLength(); ++i)
156 OS << ", " << V[i];
157 OS << " ]";
158
159 return OS;
160 }
161
162 /// \brief PBQP Matrix class
163 class Matrix {
164 private:
165 friend hash_code hash_value(const Matrix &);
166 public:
167
168 /// \brief Construct a PBQP Matrix with the given dimensions.
Matrix(unsigned Rows,unsigned Cols)169 Matrix(unsigned Rows, unsigned Cols) :
170 Rows(Rows), Cols(Cols), Data(new PBQPNum[Rows * Cols]) {
171 }
172
173 /// \brief Construct a PBQP Matrix with the given dimensions and initial
174 /// value.
Matrix(unsigned Rows,unsigned Cols,PBQPNum InitVal)175 Matrix(unsigned Rows, unsigned Cols, PBQPNum InitVal)
176 : Rows(Rows), Cols(Cols), Data(new PBQPNum[Rows * Cols]) {
177 std::fill(Data, Data + (Rows * Cols), InitVal);
178 }
179
180 /// \brief Copy construct a PBQP matrix.
Matrix(const Matrix & M)181 Matrix(const Matrix &M)
182 : Rows(M.Rows), Cols(M.Cols), Data(new PBQPNum[Rows * Cols]) {
183 std::copy(M.Data, M.Data + (Rows * Cols), Data);
184 }
185
186 /// \brief Move construct a PBQP matrix.
Matrix(Matrix && M)187 Matrix(Matrix &&M)
188 : Rows(M.Rows), Cols(M.Cols), Data(M.Data) {
189 M.Rows = M.Cols = 0;
190 M.Data = nullptr;
191 }
192
193 /// \brief Destroy this matrix, return its memory.
~Matrix()194 ~Matrix() { delete[] Data; }
195
196 /// \brief Copy-assignment operator.
197 Matrix& operator=(const Matrix &M) {
198 delete[] Data;
199 Rows = M.Rows; Cols = M.Cols;
200 Data = new PBQPNum[Rows * Cols];
201 std::copy(M.Data, M.Data + (Rows * Cols), Data);
202 return *this;
203 }
204
205 /// \brief Move-assignment operator.
206 Matrix& operator=(Matrix &&M) {
207 delete[] Data;
208 Rows = M.Rows;
209 Cols = M.Cols;
210 Data = M.Data;
211 M.Rows = M.Cols = 0;
212 M.Data = nullptr;
213 return *this;
214 }
215
216 /// \brief Comparison operator.
217 bool operator==(const Matrix &M) const {
218 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
219 if (Rows != M.Rows || Cols != M.Cols)
220 return false;
221 return std::equal(Data, Data + (Rows * Cols), M.Data);
222 }
223
224 /// \brief Return the number of rows in this matrix.
getRows()225 unsigned getRows() const {
226 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
227 return Rows;
228 }
229
230 /// \brief Return the number of cols in this matrix.
getCols()231 unsigned getCols() const {
232 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
233 return Cols;
234 }
235
236 /// \brief Matrix element access.
237 PBQPNum* operator[](unsigned R) {
238 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
239 assert(R < Rows && "Row out of bounds.");
240 return Data + (R * Cols);
241 }
242
243 /// \brief Matrix element access.
244 const PBQPNum* operator[](unsigned R) const {
245 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
246 assert(R < Rows && "Row out of bounds.");
247 return Data + (R * Cols);
248 }
249
250 /// \brief Returns the given row as a vector.
getRowAsVector(unsigned R)251 Vector getRowAsVector(unsigned R) const {
252 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
253 Vector V(Cols);
254 for (unsigned C = 0; C < Cols; ++C)
255 V[C] = (*this)[R][C];
256 return V;
257 }
258
259 /// \brief Returns the given column as a vector.
getColAsVector(unsigned C)260 Vector getColAsVector(unsigned C) const {
261 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
262 Vector V(Rows);
263 for (unsigned R = 0; R < Rows; ++R)
264 V[R] = (*this)[R][C];
265 return V;
266 }
267
268 /// \brief Reset the matrix to the given value.
269 Matrix& reset(PBQPNum Val = 0) {
270 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
271 std::fill(Data, Data + (Rows * Cols), Val);
272 return *this;
273 }
274
275 /// \brief Set a single row of this matrix to the given value.
setRow(unsigned R,PBQPNum Val)276 Matrix& setRow(unsigned R, PBQPNum Val) {
277 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
278 assert(R < Rows && "Row out of bounds.");
279 std::fill(Data + (R * Cols), Data + ((R + 1) * Cols), Val);
280 return *this;
281 }
282
283 /// \brief Set a single column of this matrix to the given value.
setCol(unsigned C,PBQPNum Val)284 Matrix& setCol(unsigned C, PBQPNum Val) {
285 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
286 assert(C < Cols && "Column out of bounds.");
287 for (unsigned R = 0; R < Rows; ++R)
288 (*this)[R][C] = Val;
289 return *this;
290 }
291
292 /// \brief Matrix transpose.
transpose()293 Matrix transpose() const {
294 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
295 Matrix M(Cols, Rows);
296 for (unsigned r = 0; r < Rows; ++r)
297 for (unsigned c = 0; c < Cols; ++c)
298 M[c][r] = (*this)[r][c];
299 return M;
300 }
301
302 /// \brief Returns the diagonal of the matrix as a vector.
303 ///
304 /// Matrix must be square.
diagonalize()305 Vector diagonalize() const {
306 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
307 assert(Rows == Cols && "Attempt to diagonalize non-square matrix.");
308 Vector V(Rows);
309 for (unsigned r = 0; r < Rows; ++r)
310 V[r] = (*this)[r][r];
311 return V;
312 }
313
314 /// \brief Add the given matrix to this one.
315 Matrix& operator+=(const Matrix &M) {
316 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
317 assert(Rows == M.Rows && Cols == M.Cols &&
318 "Matrix dimensions mismatch.");
319 std::transform(Data, Data + (Rows * Cols), M.Data, Data,
320 std::plus<PBQPNum>());
321 return *this;
322 }
323
324 Matrix operator+(const Matrix &M) {
325 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
326 Matrix Tmp(*this);
327 Tmp += M;
328 return Tmp;
329 }
330
331 /// \brief Returns the minimum of the given row
getRowMin(unsigned R)332 PBQPNum getRowMin(unsigned R) const {
333 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
334 assert(R < Rows && "Row out of bounds");
335 return *std::min_element(Data + (R * Cols), Data + ((R + 1) * Cols));
336 }
337
338 /// \brief Returns the minimum of the given column
getColMin(unsigned C)339 PBQPNum getColMin(unsigned C) const {
340 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
341 PBQPNum MinElem = (*this)[0][C];
342 for (unsigned R = 1; R < Rows; ++R)
343 if ((*this)[R][C] < MinElem)
344 MinElem = (*this)[R][C];
345 return MinElem;
346 }
347
348 /// \brief Subtracts the given scalar from the elements of the given row.
subFromRow(unsigned R,PBQPNum Val)349 Matrix& subFromRow(unsigned R, PBQPNum Val) {
350 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
351 assert(R < Rows && "Row out of bounds");
352 std::transform(Data + (R * Cols), Data + ((R + 1) * Cols),
353 Data + (R * Cols),
354 std::bind2nd(std::minus<PBQPNum>(), Val));
355 return *this;
356 }
357
358 /// \brief Subtracts the given scalar from the elements of the given column.
subFromCol(unsigned C,PBQPNum Val)359 Matrix& subFromCol(unsigned C, PBQPNum Val) {
360 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
361 for (unsigned R = 0; R < Rows; ++R)
362 (*this)[R][C] -= Val;
363 return *this;
364 }
365
366 /// \brief Returns true if this is a zero matrix.
isZero()367 bool isZero() const {
368 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
369 return find_if(Data, Data + (Rows * Cols),
370 std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) ==
371 Data + (Rows * Cols);
372 }
373
374 private:
375 unsigned Rows, Cols;
376 PBQPNum *Data;
377 };
378
379 /// \brief Return a hash_code for the given matrix.
hash_value(const Matrix & M)380 inline hash_code hash_value(const Matrix &M) {
381 unsigned *MBegin = reinterpret_cast<unsigned*>(M.Data);
382 unsigned *MEnd = reinterpret_cast<unsigned*>(M.Data + (M.Rows * M.Cols));
383 return hash_combine(M.Rows, M.Cols, hash_combine_range(MBegin, MEnd));
384 }
385
386 /// \brief Output a textual representation of the given matrix on the given
387 /// output stream.
388 template <typename OStream>
389 OStream& operator<<(OStream &OS, const Matrix &M) {
390 assert((M.getRows() != 0) && "Zero-row matrix badness.");
391 for (unsigned i = 0; i < M.getRows(); ++i)
392 OS << M.getRowAsVector(i) << "\n";
393 return OS;
394 }
395
396 template <typename Metadata>
397 class MDVector : public Vector {
398 public:
MDVector(const Vector & v)399 MDVector(const Vector &v) : Vector(v), md(*this) { }
MDVector(Vector && v)400 MDVector(Vector &&v) : Vector(std::move(v)), md(*this) { }
getMetadata()401 const Metadata& getMetadata() const { return md; }
402 private:
403 Metadata md;
404 };
405
406 template <typename Metadata>
hash_value(const MDVector<Metadata> & V)407 inline hash_code hash_value(const MDVector<Metadata> &V) {
408 return hash_value(static_cast<const Vector&>(V));
409 }
410
411 template <typename Metadata>
412 class MDMatrix : public Matrix {
413 public:
MDMatrix(const Matrix & m)414 MDMatrix(const Matrix &m) : Matrix(m), md(*this) { }
MDMatrix(Matrix && m)415 MDMatrix(Matrix &&m) : Matrix(std::move(m)), md(*this) { }
getMetadata()416 const Metadata& getMetadata() const { return md; }
417 private:
418 Metadata md;
419 };
420
421 template <typename Metadata>
hash_value(const MDMatrix<Metadata> & M)422 inline hash_code hash_value(const MDMatrix<Metadata> &M) {
423 return hash_value(static_cast<const Matrix&>(M));
424 }
425
426 } // namespace PBQP
427 } // namespace llvm
428
429 #endif // LLVM_CODEGEN_PBQP_MATH_H
430