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 "llvm/ADT/Hashing.h"
  14 #include <algorithm>
  15 #include <cassert>
  16 #include <functional>
  17
  18 namespace llvm {
  19 namespace PBQP {
  20
  21 typedef float PBQPNum;
  22
  23 /// \brief PBQP Vector class.
  24 class Vector {
  25   friend hash_code hash_value(const Vector &);
  26 public:
  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
 136 private:
 137   unsigned Length;
 138   PBQPNum *Data;
 139 };
 140
 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));
 146 }
 147
 148 /// \brief Output a textual representation of the given vector on the given
 149 ///        output stream.
 150 template <typename OStream>
 151 OStream& 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
 163 class Matrix {
 164 private:
 165   friend hash_code hash_value(const Matrix &);
 166 public:
 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
 374 private:
 375   unsigned Rows, Cols;
 376   PBQPNum *Data;
 377 };
 378
 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));
 384 }
 385
 386 /// \brief Output a textual representation of the given matrix on the given
 387 ///        output stream.
 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";
 393   return OS;
 394 }
 395
 396 template <typename Metadata>
 397 class MDVector : public Vector {
 398 public:
 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; }
 402 private:
 403   Metadata md;
 404 };
 405
 406 template <typename Metadata>
 407 inline hash_code hash_value(const MDVector<Metadata> &V) {
 408   return hash_value(static_cast<const Vector&>(V));
 409 }
 410
 411 template <typename Metadata>
 412 class MDMatrix : public Matrix {
 413 public:
 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; }
 417 private:
 418   Metadata md;
 419 };
 420
 421 template <typename Metadata>
 422 inline 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