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
18namespace llvm {
19namespace PBQP {
20
21typedef float PBQPNum;
22
23/// \brief PBQP Vector class.
24class Vector {
25  friend hash_code hash_value(const Vector &);
26public:
27
28  /// \brief Construct a PBQP vector of the given size.
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.
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.
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.
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.
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
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
131  unsigned minIndex() const {
132    assert(Length != 0 && Data != nullptr && "Invalid vector");
133    return std::min_element(Data, Data + Length) - Data;
134  }
135
136private:
137  unsigned Length;
138  PBQPNum *Data;
139};
140
141/// \brief Return a hash_value for the given vector.
142inline 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.
150template <typename OStream>
151OStream& 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
163class Matrix {
164private:
165  friend hash_code hash_value(const Matrix &);
166public:
167
168  /// \brief Construct a PBQP Matrix with the given dimensions.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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.
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
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
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.
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.
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.
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
374private:
375  unsigned Rows, Cols;
376  PBQPNum *Data;
377};
378
379/// \brief Return a hash_code for the given matrix.
380inline 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.
388template <typename OStream>
389OStream& 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
396template <typename Metadata>
397class MDVector : public Vector {
398public:
399  MDVector(const Vector &v) : Vector(v), md(*this) { }
400  MDVector(Vector &&v) : Vector(std::move(v)), md(*this) { }
401  const Metadata& getMetadata() const { return md; }
402private:
403  Metadata md;
404};
405
406template <typename Metadata>
407inline hash_code hash_value(const MDVector<Metadata> &V) {
408  return hash_value(static_cast<const Vector&>(V));
409}
410
411template <typename Metadata>
412class MDMatrix : public Matrix {
413public:
414  MDMatrix(const Matrix &m) : Matrix(m), md(*this) { }
415  MDMatrix(Matrix &&m) : Matrix(std::move(m)), md(*this) { }
416  const Metadata& getMetadata() const { return md; }
417private:
418  Metadata md;
419};
420
421template <typename Metadata>
422inline 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