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
19 typedef float PBQPNum;
21 /// \brief PBQP Vector class.
23 friend class VectorComparator;
26 /// \brief Construct a PBQP vector of the given size.
27 explicit Vector(unsigned Length)
28 : Length(Length), Data(new PBQPNum[Length]) {
29 // llvm::dbgs() << "Constructing PBQP::Vector "
30 // << this << " (length " << Length << ")\n";
33 /// \brief Construct a PBQP vector with initializer.
34 Vector(unsigned Length, PBQPNum InitVal)
35 : Length(Length), Data(new PBQPNum[Length]) {
36 // llvm::dbgs() << "Constructing PBQP::Vector "
37 // << this << " (length " << Length << ", fill "
38 // << InitVal << ")\n";
39 std::fill(Data, Data + Length, InitVal);
42 /// \brief Copy construct a PBQP vector.
43 Vector(const Vector &V)
44 : Length(V.Length), Data(new PBQPNum[Length]) {
45 // llvm::dbgs() << "Copy-constructing PBQP::Vector " << this
46 // << " from PBQP::Vector " << &V << "\n";
47 std::copy(V.Data, V.Data + Length, Data);
50 /// \brief Move construct a PBQP vector.
52 : Length(V.Length), Data(V.Data) {
57 /// \brief Destroy this vector, return its memory.
59 // llvm::dbgs() << "Deleting PBQP::Vector " << this << "\n";
63 /// \brief Copy-assignment operator.
64 Vector& operator=(const Vector &V) {
65 // llvm::dbgs() << "Assigning to PBQP::Vector " << this
66 // << " from PBQP::Vector " << &V << "\n";
69 Data = new PBQPNum[Length];
70 std::copy(V.Data, V.Data + Length, Data);
74 /// \brief Move-assignment operator.
75 Vector& operator=(Vector &&V) {
84 /// \brief Comparison operator.
85 bool operator==(const Vector &V) const {
86 assert(Length != 0 && Data != nullptr && "Invalid vector");
87 if (Length != V.Length)
89 return std::equal(Data, Data + Length, V.Data);
92 /// \brief Return the length of the vector
93 unsigned getLength() const {
94 assert(Length != 0 && Data != nullptr && "Invalid vector");
98 /// \brief Element access.
99 PBQPNum& operator[](unsigned Index) {
100 assert(Length != 0 && Data != nullptr && "Invalid vector");
101 assert(Index < Length && "Vector element access out of bounds.");
105 /// \brief Const element access.
106 const PBQPNum& operator[](unsigned Index) const {
107 assert(Length != 0 && Data != nullptr && "Invalid vector");
108 assert(Index < Length && "Vector element access out of bounds.");
112 /// \brief Add another vector to this one.
113 Vector& operator+=(const Vector &V) {
114 assert(Length != 0 && Data != nullptr && "Invalid vector");
115 assert(Length == V.Length && "Vector length mismatch.");
116 std::transform(Data, Data + Length, V.Data, Data, std::plus<PBQPNum>());
120 /// \brief Subtract another vector from this one.
121 Vector& operator-=(const Vector &V) {
122 assert(Length != 0 && Data != nullptr && "Invalid vector");
123 assert(Length == V.Length && "Vector length mismatch.");
124 std::transform(Data, Data + Length, V.Data, Data, std::minus<PBQPNum>());
128 /// \brief Returns the index of the minimum value in this vector
129 unsigned minIndex() const {
130 assert(Length != 0 && Data != nullptr && "Invalid vector");
131 return std::min_element(Data, Data + Length) - Data;
139 class VectorComparator {
141 bool operator()(const Vector &A, const Vector &B) {
142 if (A.Length < B.Length)
144 if (B.Length < A.Length)
146 char *AData = reinterpret_cast<char*>(A.Data);
147 char *BData = reinterpret_cast<char*>(B.Data);
148 return std::lexicographical_compare(AData,
149 AData + A.Length * sizeof(PBQPNum),
151 BData + A.Length * sizeof(PBQPNum));
155 /// \brief Output a textual representation of the given vector on the given
157 template <typename OStream>
158 OStream& operator<<(OStream &OS, const Vector &V) {
159 assert((V.getLength() != 0) && "Zero-length vector badness.");
162 for (unsigned i = 1; i < V.getLength(); ++i)
170 /// \brief PBQP Matrix class
173 friend class MatrixComparator;
176 /// \brief Construct a PBQP Matrix with the given dimensions.
177 Matrix(unsigned Rows, unsigned Cols) :
178 Rows(Rows), Cols(Cols), Data(new PBQPNum[Rows * Cols]) {
181 /// \brief Construct a PBQP Matrix with the given dimensions and initial
183 Matrix(unsigned Rows, unsigned Cols, PBQPNum InitVal)
184 : Rows(Rows), Cols(Cols), Data(new PBQPNum[Rows * Cols]) {
185 std::fill(Data, Data + (Rows * Cols), InitVal);
188 /// \brief Copy construct a PBQP matrix.
189 Matrix(const Matrix &M)
190 : Rows(M.Rows), Cols(M.Cols), Data(new PBQPNum[Rows * Cols]) {
191 std::copy(M.Data, M.Data + (Rows * Cols), Data);
194 /// \brief Move construct a PBQP matrix.
196 : Rows(M.Rows), Cols(M.Cols), Data(M.Data) {
201 /// \brief Destroy this matrix, return its memory.
202 ~Matrix() { delete[] Data; }
204 /// \brief Copy-assignment operator.
205 Matrix& operator=(const Matrix &M) {
207 Rows = M.Rows; Cols = M.Cols;
208 Data = new PBQPNum[Rows * Cols];
209 std::copy(M.Data, M.Data + (Rows * Cols), Data);
213 /// \brief Move-assignment operator.
214 Matrix& operator=(Matrix &&M) {
224 /// \brief Comparison operator.
225 bool operator==(const Matrix &M) const {
226 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
227 if (Rows != M.Rows || Cols != M.Cols)
229 return std::equal(Data, Data + (Rows * Cols), M.Data);
232 /// \brief Return the number of rows in this matrix.
233 unsigned getRows() const {
234 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
238 /// \brief Return the number of cols in this matrix.
239 unsigned getCols() const {
240 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
244 /// \brief Matrix element access.
245 PBQPNum* operator[](unsigned R) {
246 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
247 assert(R < Rows && "Row out of bounds.");
248 return Data + (R * Cols);
251 /// \brief Matrix element access.
252 const PBQPNum* operator[](unsigned R) const {
253 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
254 assert(R < Rows && "Row out of bounds.");
255 return Data + (R * Cols);
258 /// \brief Returns the given row as a vector.
259 Vector getRowAsVector(unsigned R) const {
260 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
262 for (unsigned C = 0; C < Cols; ++C)
263 V[C] = (*this)[R][C];
267 /// \brief Returns the given column as a vector.
268 Vector getColAsVector(unsigned C) const {
269 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
271 for (unsigned R = 0; R < Rows; ++R)
272 V[R] = (*this)[R][C];
276 /// \brief Reset the matrix to the given value.
277 Matrix& reset(PBQPNum Val = 0) {
278 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
279 std::fill(Data, Data + (Rows * Cols), Val);
283 /// \brief Set a single row of this matrix to the given value.
284 Matrix& setRow(unsigned R, PBQPNum Val) {
285 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
286 assert(R < Rows && "Row out of bounds.");
287 std::fill(Data + (R * Cols), Data + ((R + 1) * Cols), Val);
291 /// \brief Set a single column of this matrix to the given value.
292 Matrix& setCol(unsigned C, PBQPNum Val) {
293 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
294 assert(C < Cols && "Column out of bounds.");
295 for (unsigned R = 0; R < Rows; ++R)
300 /// \brief Matrix transpose.
301 Matrix transpose() const {
302 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
303 Matrix M(Cols, Rows);
304 for (unsigned r = 0; r < Rows; ++r)
305 for (unsigned c = 0; c < Cols; ++c)
306 M[c][r] = (*this)[r][c];
310 /// \brief Returns the diagonal of the matrix as a vector.
312 /// Matrix must be square.
313 Vector diagonalize() const {
314 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
315 assert(Rows == Cols && "Attempt to diagonalize non-square matrix.");
317 for (unsigned r = 0; r < Rows; ++r)
318 V[r] = (*this)[r][r];
322 /// \brief Add the given matrix to this one.
323 Matrix& operator+=(const Matrix &M) {
324 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
325 assert(Rows == M.Rows && Cols == M.Cols &&
326 "Matrix dimensions mismatch.");
327 std::transform(Data, Data + (Rows * Cols), M.Data, Data,
328 std::plus<PBQPNum>());
332 Matrix operator+(const Matrix &M) {
333 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
339 /// \brief Returns the minimum of the given row
340 PBQPNum getRowMin(unsigned R) const {
341 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
342 assert(R < Rows && "Row out of bounds");
343 return *std::min_element(Data + (R * Cols), Data + ((R + 1) * Cols));
346 /// \brief Returns the minimum of the given column
347 PBQPNum getColMin(unsigned C) const {
348 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
349 PBQPNum MinElem = (*this)[0][C];
350 for (unsigned R = 1; R < Rows; ++R)
351 if ((*this)[R][C] < MinElem)
352 MinElem = (*this)[R][C];
356 /// \brief Subtracts the given scalar from the elements of the given row.
357 Matrix& subFromRow(unsigned R, PBQPNum Val) {
358 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
359 assert(R < Rows && "Row out of bounds");
360 std::transform(Data + (R * Cols), Data + ((R + 1) * Cols),
362 std::bind2nd(std::minus<PBQPNum>(), Val));
366 /// \brief Subtracts the given scalar from the elements of the given column.
367 Matrix& subFromCol(unsigned C, PBQPNum Val) {
368 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
369 for (unsigned R = 0; R < Rows; ++R)
370 (*this)[R][C] -= Val;
374 /// \brief Returns true if this is a zero matrix.
375 bool isZero() const {
376 assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
377 return find_if(Data, Data + (Rows * Cols),
378 std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) ==
379 Data + (Rows * Cols);
387 class MatrixComparator {
389 bool operator()(const Matrix &A, const Matrix &B) {
398 char *AData = reinterpret_cast<char*>(A.Data);
399 char *BData = reinterpret_cast<char*>(B.Data);
400 return std::lexicographical_compare(
401 AData, AData + (A.Rows * A.Cols * sizeof(PBQPNum)),
402 BData, BData + (A.Rows * A.Cols * sizeof(PBQPNum)));
406 /// \brief Output a textual representation of the given matrix on the given
408 template <typename OStream>
409 OStream& operator<<(OStream &OS, const Matrix &M) {
410 assert((M.getRows() != 0) && "Zero-row matrix badness.");
411 for (unsigned i = 0; i < M.getRows(); ++i)
412 OS << M.getRowAsVector(i);
416 template <typename Metadata>
417 class MDVector : public Vector {
419 MDVector(const Vector &v) : Vector(v), md(*this) { }
420 MDVector(Vector &&v) : Vector(std::move(v)), md(*this) { }
421 const Metadata& getMetadata() const { return md; }
426 template <typename Metadata>
427 class MDMatrix : public Matrix {
429 MDMatrix(const Matrix &m) : Matrix(m), md(*this) { }
430 MDMatrix(Matrix &&m) : Matrix(std::move(m)), md(*this) { }
431 const Metadata& getMetadata() const { return md; }
438 #endif // LLVM_CODEGEN_PBQP_MATH_H