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 PBQP {
  18
  19 typedef float PBQPNum;
  20
  21 /// \brief PBQP Vector class.
  22 class Vector {
  23   friend class VectorComparator;
  24 public:
  25
  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";
  31   }
  32
  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);
  40   }
  41
  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);
  48   }
  49
  50   /// \brief Move construct a PBQP vector.
  51   Vector(Vector &&V)
  52     : Length(V.Length), Data(V.Data) {
  53     V.Length = 0;
  54     V.Data = nullptr;
  55   }
  56
  57   /// \brief Destroy this vector, return its memory.
  58   ~Vector() {
  59     // llvm::dbgs() << "Deleting PBQP::Vector " << this << "\n";
  60     delete[] Data;
  61   }
  62
  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";
  67     delete[] Data;
  68     Length = V.Length;
  69     Data = new PBQPNum[Length];
  70     std::copy(V.Data, V.Data + Length, Data);
  71     return *this;
  72   }
  73
  74   /// \brief Move-assignment operator.
  75   Vector& operator=(Vector &&V) {
  76     delete[] Data;
  77     Length = V.Length;
  78     Data = V.Data;
  79     V.Length = 0;
  80     V.Data = nullptr;
  81     return *this;
  82   }
  83
  84   /// \brief Comparison operator.
  85   bool operator==(const Vector &V) const {
  86     assert(Length != 0 && Data != nullptr && "Invalid vector");
  87     if (Length != V.Length)
  88       return false;
  89     return std::equal(Data, Data + Length, V.Data);
  90   }
  91
  92   /// \brief Return the length of the vector
  93   unsigned getLength() const {
  94     assert(Length != 0 && Data != nullptr && "Invalid vector");
  95     return Length;
  96   }
  97
  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.");
 102     return Data[Index];
 103   }
 104
 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.");
 109     return Data[Index];
 110   }
 111
 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>());
 117     return *this;
 118   }
 119
 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>());
 125     return *this;
 126   }
 127
 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;
 132   }
 133
 134 private:
 135   unsigned Length;
 136   PBQPNum *Data;
 137 };
 138
 139 class VectorComparator {
 140 public:
 141   bool operator()(const Vector &A, const Vector &B) {
 142     if (A.Length < B.Length)
 143       return true;
 144     if (B.Length < A.Length)
 145       return false;
 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),
 150                                         BData,
 151                                         BData + A.Length * sizeof(PBQPNum));
 152   }
 153 };
 154
 155 /// \brief Output a textual representation of the given vector on the given
 156 ///        output stream.
 157 template <typename OStream>
 158 OStream& operator<<(OStream &OS, const Vector &V) {
 159   assert((V.getLength() != 0) && "Zero-length vector badness.");
 160
 161   OS << "[ " << V[0];
 162   for (unsigned i = 1; i < V.getLength(); ++i)
 163     OS << ", " << V[i];
 164   OS << " ]";
 165
 166   return OS;
 167 }
 168
 169
 170 /// \brief PBQP Matrix class
 171 class Matrix {
 172 private:
 173   friend class MatrixComparator;
 174 public:
 175
 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]) {
 179   }
 180
 181   /// \brief Construct a PBQP Matrix with the given dimensions and initial
 182   /// value.
 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);
 186   }
 187
 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);
 192   }
 193
 194   /// \brief Move construct a PBQP matrix.
 195   Matrix(Matrix &&M)
 196     : Rows(M.Rows), Cols(M.Cols), Data(M.Data) {
 197     M.Rows = M.Cols = 0;
 198     M.Data = nullptr;
 199   }
 200
 201   /// \brief Destroy this matrix, return its memory.
 202   ~Matrix() { delete[] Data; }
 203
 204   /// \brief Copy-assignment operator.
 205   Matrix& operator=(const Matrix &M) {
 206     delete[] Data;
 207     Rows = M.Rows; Cols = M.Cols;
 208     Data = new PBQPNum[Rows * Cols];
 209     std::copy(M.Data, M.Data + (Rows * Cols), Data);
 210     return *this;
 211   }
 212
 213   /// \brief Move-assignment operator.
 214   Matrix& operator=(Matrix &&M) {
 215     delete[] Data;
 216     Rows = M.Rows;
 217     Cols = M.Cols;
 218     Data = M.Data;
 219     M.Rows = M.Cols = 0;
 220     M.Data = nullptr;
 221     return *this;
 222   }
 223
 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)
 228       return false;
 229     return std::equal(Data, Data + (Rows * Cols), M.Data);
 230   }
 231
 232   /// \brief Return the number of rows in this matrix.
 233   unsigned getRows() const {
 234     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
 235     return Rows;
 236   }
 237
 238   /// \brief Return the number of cols in this matrix.
 239   unsigned getCols() const {
 240     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
 241     return Cols;
 242   }
 243
 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);
 249   }
 250
 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);
 256   }
 257
 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");
 261     Vector V(Cols);
 262     for (unsigned C = 0; C < Cols; ++C)
 263       V[C] = (*this)[R][C];
 264     return V;
 265   }
 266
 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");
 270     Vector V(Rows);
 271     for (unsigned R = 0; R < Rows; ++R)
 272       V[R] = (*this)[R][C];
 273     return V;
 274   }
 275
 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);
 280     return *this;
 281   }
 282
 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);
 288     return *this;
 289   }
 290
 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)
 296       (*this)[R][C] = Val;
 297     return *this;
 298   }
 299
 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];
 307     return M;
 308   }
 309
 310   /// \brief Returns the diagonal of the matrix as a vector.
 311   ///
 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.");
 316     Vector V(Rows);
 317     for (unsigned r = 0; r < Rows; ++r)
 318       V[r] = (*this)[r][r];
 319     return V;
 320   }
 321
 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>());
 329     return *this;
 330   }
 331
 332   Matrix operator+(const Matrix &M) {
 333     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
 334     Matrix Tmp(*this);
 335     Tmp += M;
 336     return Tmp;
 337   }
 338
 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));
 344   }
 345
 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];
 353     return MinElem;
 354   }
 355
 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),
 361                    Data + (R * Cols),
 362                    std::bind2nd(std::minus<PBQPNum>(), Val));
 363     return *this;
 364   }
 365
 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;
 371     return *this;
 372   }
 373
 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);
 380   }
 381
 382 private:
 383   unsigned Rows, Cols;
 384   PBQPNum *Data;
 385 };
 386
 387 class MatrixComparator {
 388 public:
 389   bool operator()(const Matrix &A, const Matrix &B) {
 390     if (A.Rows < B.Rows)
 391       return true;
 392     if (B.Rows < A.Rows)
 393       return false;
 394     if (A.Cols < B.Cols)
 395       return true;
 396     if (B.Cols < A.Cols)
 397       return false;
 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)));
 403   }
 404 };
 405
 406 /// \brief Output a textual representation of the given matrix on the given
 407 ///        output stream.
 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);
 413   return OS;
 414 }
 415
 416 template <typename Metadata>
 417 class MDVector : public Vector {
 418 public:
 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; }
 422 private:
 423   Metadata md;
 424 };
 425
 426 template <typename Metadata>
 427 class MDMatrix : public Matrix {
 428 public:
 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; }
 432 private:
 433   Metadata md;
 434 };
 435
 436 }
 437
 438 #endif // LLVM_CODEGEN_PBQP_MATH_H