include/llvm/CodeGen/PBQP/Math.h

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