1 //===------ Math.h - PBQP Vector and Matrix classes -------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 #ifndef LLVM_CODEGEN_PBQP_MATH_H
11 #define LLVM_CODEGEN_PBQP_MATH_H
13 #include "llvm/ADT/Hashing.h"
21 typedef float PBQPNum;
23 /// \brief PBQP Vector class.
25 friend hash_code hash_value(const Vector &);
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";
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);
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);
52 /// \brief Move construct a PBQP vector.
54 : Length(V.Length), Data(V.Data) {
59 /// \brief Destroy this vector, return its memory.
61 // llvm::dbgs() << "Deleting PBQP::Vector " << this << "\n";
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";
71 Data = new PBQPNum[Length];
72 std::copy(V.Data, V.Data + Length, Data);
76 /// \brief Move-assignment operator.
77 Vector& operator=(Vector &&V) {
86 /// \brief Comparison operator.
87 bool operator==(const Vector &V) const {
88 assert(Length != 0 && Data != nullptr && "Invalid vector");
89 if (Length != V.Length)
91 return std::equal(Data, Data + Length, V.Data);
94 /// \brief Return the length of the vector
95 unsigned getLength() const {
96 assert(Length != 0 && Data != nullptr && "Invalid vector");
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.");
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.");
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>());
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>());
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;
141 /// \brief Return a hash_value for the given vector.
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));
148 /// \brief Output a textual representation of the given vector on the given
150 template <typename OStream>
151 OStream& operator<<(OStream &OS, const Vector &V) {
152 assert((V.getLength() != 0) && "Zero-length vector badness.");
155 for (unsigned i = 1; i < V.getLength(); ++i)
162 /// \brief PBQP Matrix class
165 friend hash_code hash_value(const Matrix &);
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]) {
173 /// \brief Construct a PBQP Matrix with the given dimensions and initial
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);
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);
186 /// \brief Move construct a PBQP matrix.
188 : Rows(M.Rows), Cols(M.Cols), Data(M.Data) {
193 /// \brief Destroy this matrix, return its memory.
194 ~Matrix() { delete[] Data; }
196 /// \brief Copy-assignment operator.
197 Matrix& operator=(const Matrix &M) {
199 Rows = M.Rows; Cols = M.Cols;
200 Data = new PBQPNum[Rows * Cols];
201 std::copy(M.Data, M.Data + (Rows * Cols), Data);
205 /// \brief Move-assignment operator.
206 Matrix& operator=(Matrix &&M) {
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)
221 return std::equal(Data, Data + (Rows * Cols), M.Data);
224 /// \brief Return the number of rows in this matrix.
225 unsigned getRows() const {
226 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
230 /// \brief Return the number of cols in this matrix.
231 unsigned getCols() const {
232 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
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);
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);
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");
254 for (unsigned C = 0; C < Cols; ++C)
255 V[C] = (*this)[R][C];
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");
263 for (unsigned R = 0; R < Rows; ++R)
264 V[R] = (*this)[R][C];
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);
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);
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)
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];
302 /// \brief Returns the diagonal of the matrix as a vector.
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.");
309 for (unsigned r = 0; r < Rows; ++r)
310 V[r] = (*this)[r][r];
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>());
324 Matrix operator+(const Matrix &M) {
325 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
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));
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];
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),
354 std::bind2nd(std::minus<PBQPNum>(), Val));
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;
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);
379 /// \brief Return a hash_code for the given matrix.
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));
386 /// \brief Output a textual representation of the given matrix on the given
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";
396 template <typename Metadata>
397 class MDVector : public Vector {
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; }
406 template <typename Metadata>
407 inline hash_code hash_value(const MDVector<Metadata> &V) {
408 return hash_value(static_cast<const Vector&>(V));
411 template <typename Metadata>
412 class MDMatrix : public Matrix {
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; }
421 template <typename Metadata>
422 inline hash_code hash_value(const MDMatrix<Metadata> &M) {
423 return hash_value(static_cast<const Matrix&>(M));
429 #endif // LLVM_CODEGEN_PBQP_MATH_H