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