CodeGen/PBQP/Math.h

0001 //===- Math.h - PBQP Vector and Matrix classes ------------------*- C++ -*-===//
0002 //
0003 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
0004 // See https://llvm.org/LICENSE.txt for license information.
0005 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
0006 //
0007 //===----------------------------------------------------------------------===//
0008
0009 #ifndef LLVM_CODEGEN_PBQP_MATH_H
0010 #define LLVM_CODEGEN_PBQP_MATH_H
0011
0012 #include "llvm/ADT/Hashing.h"
0013 #include "llvm/ADT/STLExtras.h"
0014 #include <algorithm>
0015 #include <cassert>
0016 #include <functional>
0017 #include <memory>
0018
0019 namespace llvm {
0020 namespace PBQP {
0021
0022 using PBQPNum = float;
0023
0024 /// PBQP Vector class.
0025 class Vector {
0026   friend hash_code hash_value(const Vector &);
0027
0028 public:
0029   /// Construct a PBQP vector of the given size.
0030   explicit Vector(unsigned Length)
0031     : Length(Length), Data(std::make_unique<PBQPNum []>(Length)) {}
0032
0033   /// Construct a PBQP vector with initializer.
0034   Vector(unsigned Length, PBQPNum InitVal)
0035     : Length(Length), Data(std::make_unique<PBQPNum []>(Length)) {
0036     std::fill(Data.get(), Data.get() + Length, InitVal);
0037   }
0038
0039   /// Copy construct a PBQP vector.
0040   Vector(const Vector &V)
0041     : Length(V.Length), Data(std::make_unique<PBQPNum []>(Length)) {
0042     std::copy(V.Data.get(), V.Data.get() + Length, Data.get());
0043   }
0044
0045   /// Move construct a PBQP vector.
0046   Vector(Vector &&V)
0047     : Length(V.Length), Data(std::move(V.Data)) {
0048     V.Length = 0;
0049   }
0050
0051   /// Comparison operator.
0052   bool operator==(const Vector &V) const {
0053     assert(Length != 0 && Data && "Invalid vector");
0054     if (Length != V.Length)
0055       return false;
0056     return std::equal(Data.get(), Data.get() + Length, V.Data.get());
0057   }
0058
0059   /// Return the length of the vector
0060   unsigned getLength() const {
0061     assert(Length != 0 && Data && "Invalid vector");
0062     return Length;
0063   }
0064
0065   /// Element access.
0066   PBQPNum& operator[](unsigned Index) {
0067     assert(Length != 0 && Data && "Invalid vector");
0068     assert(Index < Length && "Vector element access out of bounds.");
0069     return Data[Index];
0070   }
0071
0072   /// Const element access.
0073   const PBQPNum& operator[](unsigned Index) const {
0074     assert(Length != 0 && Data && "Invalid vector");
0075     assert(Index < Length && "Vector element access out of bounds.");
0076     return Data[Index];
0077   }
0078
0079   /// Add another vector to this one.
0080   Vector& operator+=(const Vector &V) {
0081     assert(Length != 0 && Data && "Invalid vector");
0082     assert(Length == V.Length && "Vector length mismatch.");
0083     std::transform(Data.get(), Data.get() + Length, V.Data.get(), Data.get(),
0084                    std::plus<PBQPNum>());
0085     return *this;
0086   }
0087
0088   /// Returns the index of the minimum value in this vector
0089   unsigned minIndex() const {
0090     assert(Length != 0 && Data && "Invalid vector");
0091     return std::min_element(Data.get(), Data.get() + Length) - Data.get();
0092   }
0093
0094 private:
0095   unsigned Length;
0096   std::unique_ptr<PBQPNum []> Data;
0097 };
0098
0099 /// Return a hash_value for the given vector.
0100 inline hash_code hash_value(const Vector &V) {
0101   unsigned *VBegin = reinterpret_cast<unsigned*>(V.Data.get());
0102   unsigned *VEnd = reinterpret_cast<unsigned*>(V.Data.get() + V.Length);
0103   return hash_combine(V.Length, hash_combine_range(VBegin, VEnd));
0104 }
0105
0106 /// Output a textual representation of the given vector on the given
0107 ///        output stream.
0108 template <typename OStream>
0109 OStream& operator<<(OStream &OS, const Vector &V) {
0110   assert((V.getLength() != 0) && "Zero-length vector badness.");
0111
0112   OS << "[ " << V[0];
0113   for (unsigned i = 1; i < V.getLength(); ++i)
0114     OS << ", " << V[i];
0115   OS << " ]";
0116
0117   return OS;
0118 }
0119
0120 /// PBQP Matrix class
0121 class Matrix {
0122 private:
0123   friend hash_code hash_value(const Matrix &);
0124
0125 public:
0126   /// Construct a PBQP Matrix with the given dimensions.
0127   Matrix(unsigned Rows, unsigned Cols) :
0128     Rows(Rows), Cols(Cols), Data(std::make_unique<PBQPNum []>(Rows * Cols)) {
0129   }
0130
0131   /// Construct a PBQP Matrix with the given dimensions and initial
0132   /// value.
0133   Matrix(unsigned Rows, unsigned Cols, PBQPNum InitVal)
0134     : Rows(Rows), Cols(Cols),
0135       Data(std::make_unique<PBQPNum []>(Rows * Cols)) {
0136     std::fill(Data.get(), Data.get() + (Rows * Cols), InitVal);
0137   }
0138
0139   /// Copy construct a PBQP matrix.
0140   Matrix(const Matrix &M)
0141     : Rows(M.Rows), Cols(M.Cols),
0142       Data(std::make_unique<PBQPNum []>(Rows * Cols)) {
0143     std::copy(M.Data.get(), M.Data.get() + (Rows * Cols), Data.get());
0144   }
0145
0146   /// Move construct a PBQP matrix.
0147   Matrix(Matrix &&M)
0148     : Rows(M.Rows), Cols(M.Cols), Data(std::move(M.Data)) {
0149     M.Rows = M.Cols = 0;
0150   }
0151
0152   /// Comparison operator.
0153   bool operator==(const Matrix &M) const {
0154     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
0155     if (Rows != M.Rows || Cols != M.Cols)
0156       return false;
0157     return std::equal(Data.get(), Data.get() + (Rows * Cols), M.Data.get());
0158   }
0159
0160   /// Return the number of rows in this matrix.
0161   unsigned getRows() const {
0162     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
0163     return Rows;
0164   }
0165
0166   /// Return the number of cols in this matrix.
0167   unsigned getCols() const {
0168     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
0169     return Cols;
0170   }
0171
0172   /// Matrix element access.
0173   PBQPNum* operator[](unsigned R) {
0174     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
0175     assert(R < Rows && "Row out of bounds.");
0176     return Data.get() + (R * Cols);
0177   }
0178
0179   /// Matrix element access.
0180   const PBQPNum* operator[](unsigned R) const {
0181     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
0182     assert(R < Rows && "Row out of bounds.");
0183     return Data.get() + (R * Cols);
0184   }
0185
0186   /// Returns the given row as a vector.
0187   Vector getRowAsVector(unsigned R) const {
0188     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
0189     Vector V(Cols);
0190     for (unsigned C = 0; C < Cols; ++C)
0191       V[C] = (*this)[R][C];
0192     return V;
0193   }
0194
0195   /// Returns the given column as a vector.
0196   Vector getColAsVector(unsigned C) const {
0197     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
0198     Vector V(Rows);
0199     for (unsigned R = 0; R < Rows; ++R)
0200       V[R] = (*this)[R][C];
0201     return V;
0202   }
0203
0204   /// Matrix transpose.
0205   Matrix transpose() const {
0206     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
0207     Matrix M(Cols, Rows);
0208     for (unsigned r = 0; r < Rows; ++r)
0209       for (unsigned c = 0; c < Cols; ++c)
0210         M[c][r] = (*this)[r][c];
0211     return M;
0212   }
0213
0214   /// Add the given matrix to this one.
0215   Matrix& operator+=(const Matrix &M) {
0216     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
0217     assert(Rows == M.Rows && Cols == M.Cols &&
0218            "Matrix dimensions mismatch.");
0219     std::transform(Data.get(), Data.get() + (Rows * Cols), M.Data.get(),
0220                    Data.get(), std::plus<PBQPNum>());
0221     return *this;
0222   }
0223
0224   Matrix operator+(const Matrix &M) {
0225     assert(Rows != 0 && Cols != 0 && Data && "Invalid matrix");
0226     Matrix Tmp(*this);
0227     Tmp += M;
0228     return Tmp;
0229   }
0230
0231 private:
0232   unsigned Rows, Cols;
0233   std::unique_ptr<PBQPNum []> Data;
0234 };
0235
0236 /// Return a hash_code for the given matrix.
0237 inline hash_code hash_value(const Matrix &M) {
0238   unsigned *MBegin = reinterpret_cast<unsigned*>(M.Data.get());
0239   unsigned *MEnd =
0240     reinterpret_cast<unsigned*>(M.Data.get() + (M.Rows * M.Cols));
0241   return hash_combine(M.Rows, M.Cols, hash_combine_range(MBegin, MEnd));
0242 }
0243
0244 /// Output a textual representation of the given matrix on the given
0245 ///        output stream.
0246 template <typename OStream>
0247 OStream& operator<<(OStream &OS, const Matrix &M) {
0248   assert((M.getRows() != 0) && "Zero-row matrix badness.");
0249   for (unsigned i = 0; i < M.getRows(); ++i)
0250     OS << M.getRowAsVector(i) << "\n";
0251   return OS;
0252 }
0253
0254 template <typename Metadata>
0255 class MDVector : public Vector {
0256 public:
0257   MDVector(const Vector &v) : Vector(v), md(*this) {}
0258   MDVector(Vector &&v) : Vector(std::move(v)), md(*this) { }
0259
0260   const Metadata& getMetadata() const { return md; }
0261
0262 private:
0263   Metadata md;
0264 };
0265
0266 template <typename Metadata>
0267 inline hash_code hash_value(const MDVector<Metadata> &V) {
0268   return hash_value(static_cast<const Vector&>(V));
0269 }
0270
0271 template <typename Metadata>
0272 class MDMatrix : public Matrix {
0273 public:
0274   MDMatrix(const Matrix &m) : Matrix(m), md(*this) {}
0275   MDMatrix(Matrix &&m) : Matrix(std::move(m)), md(*this) { }
0276
0277   const Metadata& getMetadata() const { return md; }
0278
0279 private:
0280   Metadata md;
0281 };
0282
0283 template <typename Metadata>
0284 inline hash_code hash_value(const MDMatrix<Metadata> &M) {
0285   return hash_value(static_cast<const Matrix&>(M));
0286 }
0287
0288 } // end namespace PBQP
0289 } // end namespace llvm
0290
0291 #endif // LLVM_CODEGEN_PBQP_MATH_H