contrib/llvm/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(llvm::make_unique<PBQPNum []>(Length)) {}
  31
  32   /// \brief Construct a PBQP vector with initializer.
  33   Vector(unsigned Length, PBQPNum InitVal)
  34     : Length(Length), Data(llvm::make_unique<PBQPNum []>(Length)) {
  35     std::fill(Data.get(), Data.get() + Length, InitVal);
  36   }
  37
  38   /// \brief Copy construct a PBQP vector.
  39   Vector(const Vector &V)
  40     : Length(V.Length), Data(llvm::make_unique<PBQPNum []>(Length)) {
  41     std::copy(V.Data.get(), V.Data.get() + Length, Data.get());
  42   }
  43
  44   /// \brief Move construct a PBQP vector.
  45   Vector(Vector &&V)
  46     : Length(V.Length), Data(std::move(V.Data)) {
  47     V.Length = 0;
  48   }
  49
  50   /// \brief Comparison operator.
  51   bool operator==(const Vector &V) const {
  52     assert(Length != 0 && Data && "Invalid vector");
  53     if (Length != V.Length)
  54       return false;
  55     return std::equal(Data.get(), Data.get() + Length, V.Data.get());
  56   }
  57
  58   /// \brief Return the length of the vector
  59   unsigned getLength() const {
  60     assert(Length != 0 && Data && "Invalid vector");
  61     return Length;
  62   }
  63
  64   /// \brief Element access.
  65   PBQPNum& operator[](unsigned Index) {
  66     assert(Length != 0 && Data && "Invalid vector");
  67     assert(Index < Length && "Vector element access out of bounds.");
  68     return Data[Index];
  69   }
  70
  71   /// \brief Const element access.
  72   const PBQPNum& operator[](unsigned Index) const {
  73     assert(Length != 0 && Data && "Invalid vector");
  74     assert(Index < Length && "Vector element access out of bounds.");
  75     return Data[Index];
  76   }
  77
  78   /// \brief Add another vector to this one.
  79   Vector& operator+=(const Vector &V) {
  80     assert(Length != 0 && Data && "Invalid vector");
  81     assert(Length == V.Length && "Vector length mismatch.");
  82     std::transform(Data.get(), Data.get() + Length, V.Data.get(), Data.get(),
  83                    std::plus<PBQPNum>());
  84     return *this;
  85   }
  86
  87   /// \brief Returns the index of the minimum value in this vector
  88   unsigned minIndex() const {
  89     assert(Length != 0 && Data && "Invalid vector");
  90     return std::min_element(Data.get(), Data.get() + Length) - Data.get();
  91   }
  92
  93 private:
  94   unsigned Length;
  95   std::unique_ptr<PBQPNum []> Data;
  96 };
  97
  98 /// \brief Return a hash_value for the given vector.
  99 inline hash_code hash_value(const Vector &V) {
 100   unsigned *VBegin = reinterpret_cast<unsigned*>(V.Data.get());
 101   unsigned *VEnd = reinterpret_cast<unsigned*>(V.Data.get() + V.Length);
 102   return hash_combine(V.Length, hash_combine_range(VBegin, VEnd));
 103 }
 104
 105 /// \brief Output a textual representation of the given vector on the given
 106 ///        output stream.
 107 template <typename OStream>
 108 OStream& operator<<(OStream &OS, const Vector &V) {
 109   assert((V.getLength() != 0) && "Zero-length vector badness.");
 110
 111   OS << "[ " << V[0];
 112   for (unsigned i = 1; i < V.getLength(); ++i)
 113     OS << ", " << V[i];
 114   OS << " ]";
 115
 116   return OS;
 117 }
 118
 119 /// \brief PBQP Matrix class
 120 class Matrix {
 121 private:
 122   friend hash_code hash_value(const Matrix &);
 123 public:
 124
 125   /// \brief Construct a PBQP Matrix with the given dimensions.
 126   Matrix(unsigned Rows, unsigned Cols) :
 127     Rows(Rows), Cols(Cols), Data(llvm::make_unique<PBQPNum []>(Rows * Cols)) {
 128   }
 129
 130   /// \brief Construct a PBQP Matrix with the given dimensions and initial
 131   /// value.
 132   Matrix(unsigned Rows, unsigned Cols, PBQPNum InitVal)
 133     : Rows(Rows), Cols(Cols),
 134       Data(llvm::make_unique<PBQPNum []>(Rows * Cols)) {
 135     std::fill(Data.get(), Data.get() + (Rows * Cols), InitVal);
 136   }
 137
 138   /// \brief Copy construct a PBQP matrix.
 139   Matrix(const Matrix &M)
 140     : Rows(M.Rows), Cols(M.Cols),
 141       Data(llvm::make_unique<PBQPNum []>(Rows * Cols)) {
 142     std::copy(M.Data.get(), M.Data.get() + (Rows * Cols), Data.get());
 143   }
 144
 145   /// \brief Move construct a PBQP matrix.
 146   Matrix(Matrix &&M)
 147     : Rows(M.Rows), Cols(M.Cols), Data(std::move(M.Data)) {
 148     M.Rows = M.Cols = 0;
 149   }
 150
 151   /// \brief Comparison operator.
 152   bool operator==(const Matrix &M) const {
 153     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
 154     if (Rows != M.Rows || Cols != M.Cols)
 155       return false;
 156     return std::equal(Data.get(), Data.get() + (Rows * Cols), M.Data.get());
 157   }
 158
 159   /// \brief Return the number of rows in this matrix.
 160   unsigned getRows() const {
 161     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
 162     return Rows;
 163   }
 164
 165   /// \brief Return the number of cols in this matrix.
 166   unsigned getCols() const {
 167     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
 168     return Cols;
 169   }
 170
 171   /// \brief Matrix element access.
 172   PBQPNum* operator[](unsigned R) {
 173     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
 174     assert(R < Rows && "Row out of bounds.");
 175     return Data.get() + (R * Cols);
 176   }
 177
 178   /// \brief Matrix element access.
 179   const PBQPNum* operator[](unsigned R) const {
 180     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
 181     assert(R < Rows && "Row out of bounds.");
 182     return Data.get() + (R * Cols);
 183   }
 184
 185   /// \brief Returns the given row as a vector.
 186   Vector getRowAsVector(unsigned R) const {
 187     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
 188     Vector V(Cols);
 189     for (unsigned C = 0; C < Cols; ++C)
 190       V[C] = (*this)[R][C];
 191     return V;
 192   }
 193
 194   /// \brief Returns the given column as a vector.
 195   Vector getColAsVector(unsigned C) const {
 196     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
 197     Vector V(Rows);
 198     for (unsigned R = 0; R < Rows; ++R)
 199       V[R] = (*this)[R][C];
 200     return V;
 201   }
 202
 203   /// \brief Matrix transpose.
 204   Matrix transpose() const {
 205     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
 206     Matrix M(Cols, Rows);
 207     for (unsigned r = 0; r < Rows; ++r)
 208       for (unsigned c = 0; c < Cols; ++c)
 209         M[c][r] = (*this)[r][c];
 210     return M;
 211   }
 212
 213   /// \brief Add the given matrix to this one.
 214   Matrix& operator+=(const Matrix &M) {
 215     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
 216     assert(Rows == M.Rows && Cols == M.Cols &&
 217            "Matrix dimensions mismatch.");
 218     std::transform(Data.get(), Data.get() + (Rows * Cols), M.Data.get(),
 219                    Data.get(), std::plus<PBQPNum>());
 220     return *this;
 221   }
 222
 223   Matrix operator+(const Matrix &M) {
 224     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
 225     Matrix Tmp(*this);
 226     Tmp += M;
 227     return Tmp;
 228   }
 229
 230 private:
 231   unsigned Rows, Cols;
 232   std::unique_ptr<PBQPNum []> Data;
 233 };
 234
 235 /// \brief Return a hash_code for the given matrix.
 236 inline hash_code hash_value(const Matrix &M) {
 237   unsigned *MBegin = reinterpret_cast<unsigned*>(M.Data.get());
 238   unsigned *MEnd =
 239     reinterpret_cast<unsigned*>(M.Data.get() + (M.Rows * M.Cols));
 240   return hash_combine(M.Rows, M.Cols, hash_combine_range(MBegin, MEnd));
 241 }
 242
 243 /// \brief Output a textual representation of the given matrix on the given
 244 ///        output stream.
 245 template <typename OStream>
 246 OStream& operator<<(OStream &OS, const Matrix &M) {
 247   assert((M.getRows() != 0) && "Zero-row matrix badness.");
 248   for (unsigned i = 0; i < M.getRows(); ++i)
 249     OS << M.getRowAsVector(i) << "\n";
 250   return OS;
 251 }
 252
 253 template <typename Metadata>
 254 class MDVector : public Vector {
 255 public:
 256   MDVector(const Vector &v) : Vector(v), md(*this) { }
 257   MDVector(Vector &&v) : Vector(std::move(v)), md(*this) { }
 258   const Metadata& getMetadata() const { return md; }
 259 private:
 260   Metadata md;
 261 };
 262
 263 template <typename Metadata>
 264 inline hash_code hash_value(const MDVector<Metadata> &V) {
 265   return hash_value(static_cast<const Vector&>(V));
 266 }
 267
 268 template <typename Metadata>
 269 class MDMatrix : public Matrix {
 270 public:
 271   MDMatrix(const Matrix &m) : Matrix(m), md(*this) { }
 272   MDMatrix(Matrix &&m) : Matrix(std::move(m)), md(*this) { }
 273   const Metadata& getMetadata() const { return md; }
 274 private:
 275   Metadata md;
 276 };
 277
 278 template <typename Metadata>
 279 inline hash_code hash_value(const MDMatrix<Metadata> &M) {
 280   return hash_value(static_cast<const Matrix&>(M));
 281 }
 282
 283 } // namespace PBQP
 284 } // namespace llvm
 285
 286 #endif // LLVM_CODEGEN_PBQP_MATH_H