LLVM API Documentation

Math.h
Go to the documentation of this file.
00001 //===------ Math.h - PBQP Vector and Matrix classes -------------*- C++ -*-===//
00002 //
00003 //                     The LLVM Compiler Infrastructure
00004 //
00005 // This file is distributed under the University of Illinois Open Source
00006 // License. See LICENSE.TXT for details.
00007 //
00008 //===----------------------------------------------------------------------===//
00009 
00010 #ifndef LLVM_CODEGEN_PBQP_MATH_H
00011 #define LLVM_CODEGEN_PBQP_MATH_H
00012 
00013 #include "llvm/ADT/Hashing.h"
00014 #include <algorithm>
00015 #include <cassert>
00016 #include <functional>
00017 
00018 namespace llvm {
00019 namespace PBQP {
00020 
00021 typedef float PBQPNum;
00022 
00023 /// \brief PBQP Vector class.
00024 class Vector {
00025   friend hash_code hash_value(const Vector &);
00026 public:
00027 
00028   /// \brief Construct a PBQP vector of the given size.
00029   explicit Vector(unsigned Length)
00030     : Length(Length), Data(new PBQPNum[Length]) {
00031     // llvm::dbgs() << "Constructing PBQP::Vector "
00032     //              << this << " (length " << Length << ")\n";
00033   }
00034 
00035   /// \brief Construct a PBQP vector with initializer.
00036   Vector(unsigned Length, PBQPNum InitVal)
00037     : Length(Length), Data(new PBQPNum[Length]) {
00038     // llvm::dbgs() << "Constructing PBQP::Vector "
00039     //              << this << " (length " << Length << ", fill "
00040     //              << InitVal << ")\n";
00041     std::fill(Data, Data + Length, InitVal);
00042   }
00043 
00044   /// \brief Copy construct a PBQP vector.
00045   Vector(const Vector &V)
00046     : Length(V.Length), Data(new PBQPNum[Length]) {
00047     // llvm::dbgs() << "Copy-constructing PBQP::Vector " << this
00048     //              << " from PBQP::Vector " << &V << "\n";
00049     std::copy(V.Data, V.Data + Length, Data);
00050   }
00051 
00052   /// \brief Move construct a PBQP vector.
00053   Vector(Vector &&V)
00054     : Length(V.Length), Data(V.Data) {
00055     V.Length = 0;
00056     V.Data = nullptr;
00057   }
00058 
00059   /// \brief Destroy this vector, return its memory.
00060   ~Vector() {
00061     // llvm::dbgs() << "Deleting PBQP::Vector " << this << "\n";
00062     delete[] Data;
00063   }
00064 
00065   /// \brief Copy-assignment operator.
00066   Vector& operator=(const Vector &V) {
00067     // llvm::dbgs() << "Assigning to PBQP::Vector " << this
00068     //              << " from PBQP::Vector " << &V << "\n";
00069     delete[] Data;
00070     Length = V.Length;
00071     Data = new PBQPNum[Length];
00072     std::copy(V.Data, V.Data + Length, Data);
00073     return *this;
00074   }
00075 
00076   /// \brief Move-assignment operator.
00077   Vector& operator=(Vector &&V) {
00078     delete[] Data;
00079     Length = V.Length;
00080     Data = V.Data;
00081     V.Length = 0;
00082     V.Data = nullptr;
00083     return *this;
00084   }
00085 
00086   /// \brief Comparison operator.
00087   bool operator==(const Vector &V) const {
00088     assert(Length != 0 && Data != nullptr && "Invalid vector");
00089     if (Length != V.Length)
00090       return false;
00091     return std::equal(Data, Data + Length, V.Data);
00092   }
00093 
00094   /// \brief Return the length of the vector
00095   unsigned getLength() const {
00096     assert(Length != 0 && Data != nullptr && "Invalid vector");
00097     return Length;
00098   }
00099 
00100   /// \brief Element access.
00101   PBQPNum& operator[](unsigned Index) {
00102     assert(Length != 0 && Data != nullptr && "Invalid vector");
00103     assert(Index < Length && "Vector element access out of bounds.");
00104     return Data[Index];
00105   }
00106 
00107   /// \brief Const element access.
00108   const PBQPNum& operator[](unsigned Index) const {
00109     assert(Length != 0 && Data != nullptr && "Invalid vector");
00110     assert(Index < Length && "Vector element access out of bounds.");
00111     return Data[Index];
00112   }
00113 
00114   /// \brief Add another vector to this one.
00115   Vector& operator+=(const Vector &V) {
00116     assert(Length != 0 && Data != nullptr && "Invalid vector");
00117     assert(Length == V.Length && "Vector length mismatch.");
00118     std::transform(Data, Data + Length, V.Data, Data, std::plus<PBQPNum>());
00119     return *this;
00120   }
00121 
00122   /// \brief Subtract another vector from this one.
00123   Vector& operator-=(const Vector &V) {
00124     assert(Length != 0 && Data != nullptr && "Invalid vector");
00125     assert(Length == V.Length && "Vector length mismatch.");
00126     std::transform(Data, Data + Length, V.Data, Data, std::minus<PBQPNum>());
00127     return *this;
00128   }
00129 
00130   /// \brief Returns the index of the minimum value in this vector
00131   unsigned minIndex() const {
00132     assert(Length != 0 && Data != nullptr && "Invalid vector");
00133     return std::min_element(Data, Data + Length) - Data;
00134   }
00135 
00136 private:
00137   unsigned Length;
00138   PBQPNum *Data;
00139 };
00140 
00141 /// \brief Return a hash_value for the given vector.
00142 inline hash_code hash_value(const Vector &V) {
00143   unsigned *VBegin = reinterpret_cast<unsigned*>(V.Data);
00144   unsigned *VEnd = reinterpret_cast<unsigned*>(V.Data + V.Length);
00145   return hash_combine(V.Length, hash_combine_range(VBegin, VEnd));
00146 }
00147 
00148 /// \brief Output a textual representation of the given vector on the given
00149 ///        output stream.
00150 template <typename OStream>
00151 OStream& operator<<(OStream &OS, const Vector &V) {
00152   assert((V.getLength() != 0) && "Zero-length vector badness.");
00153 
00154   OS << "[ " << V[0];
00155   for (unsigned i = 1; i < V.getLength(); ++i)
00156     OS << ", " << V[i];
00157   OS << " ]";
00158 
00159   return OS;
00160 }
00161 
00162 /// \brief PBQP Matrix class
00163 class Matrix {
00164 private:
00165   friend hash_code hash_value(const Matrix &);
00166 public:
00167 
00168   /// \brief Construct a PBQP Matrix with the given dimensions.
00169   Matrix(unsigned Rows, unsigned Cols) :
00170     Rows(Rows), Cols(Cols), Data(new PBQPNum[Rows * Cols]) {
00171   }
00172 
00173   /// \brief Construct a PBQP Matrix with the given dimensions and initial
00174   /// value.
00175   Matrix(unsigned Rows, unsigned Cols, PBQPNum InitVal)
00176     : Rows(Rows), Cols(Cols), Data(new PBQPNum[Rows * Cols]) {
00177     std::fill(Data, Data + (Rows * Cols), InitVal);
00178   }
00179 
00180   /// \brief Copy construct a PBQP matrix.
00181   Matrix(const Matrix &M)
00182     : Rows(M.Rows), Cols(M.Cols), Data(new PBQPNum[Rows * Cols]) {
00183     std::copy(M.Data, M.Data + (Rows * Cols), Data);
00184   }
00185 
00186   /// \brief Move construct a PBQP matrix.
00187   Matrix(Matrix &&M)
00188     : Rows(M.Rows), Cols(M.Cols), Data(M.Data) {
00189     M.Rows = M.Cols = 0;
00190     M.Data = nullptr;
00191   }
00192 
00193   /// \brief Destroy this matrix, return its memory.
00194   ~Matrix() { delete[] Data; }
00195 
00196   /// \brief Copy-assignment operator.
00197   Matrix& operator=(const Matrix &M) {
00198     delete[] Data;
00199     Rows = M.Rows; Cols = M.Cols;
00200     Data = new PBQPNum[Rows * Cols];
00201     std::copy(M.Data, M.Data + (Rows * Cols), Data);
00202     return *this;
00203   }
00204 
00205   /// \brief Move-assignment operator.
00206   Matrix& operator=(Matrix &&M) {
00207     delete[] Data;
00208     Rows = M.Rows;
00209     Cols = M.Cols;
00210     Data = M.Data;
00211     M.Rows = M.Cols = 0;
00212     M.Data = nullptr;
00213     return *this;
00214   }
00215 
00216   /// \brief Comparison operator.
00217   bool operator==(const Matrix &M) const {
00218     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00219     if (Rows != M.Rows || Cols != M.Cols)
00220       return false;
00221     return std::equal(Data, Data + (Rows * Cols), M.Data);
00222   }
00223 
00224   /// \brief Return the number of rows in this matrix.
00225   unsigned getRows() const {
00226     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00227     return Rows;
00228   }
00229 
00230   /// \brief Return the number of cols in this matrix.
00231   unsigned getCols() const {
00232     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00233     return Cols;
00234   }
00235 
00236   /// \brief Matrix element access.
00237   PBQPNum* operator[](unsigned R) {
00238     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00239     assert(R < Rows && "Row out of bounds.");
00240     return Data + (R * Cols);
00241   }
00242 
00243   /// \brief Matrix element access.
00244   const PBQPNum* operator[](unsigned R) const {
00245     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00246     assert(R < Rows && "Row out of bounds.");
00247     return Data + (R * Cols);
00248   }
00249 
00250   /// \brief Returns the given row as a vector.
00251   Vector getRowAsVector(unsigned R) const {
00252     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00253     Vector V(Cols);
00254     for (unsigned C = 0; C < Cols; ++C)
00255       V[C] = (*this)[R][C];
00256     return V;
00257   }
00258 
00259   /// \brief Returns the given column as a vector.
00260   Vector getColAsVector(unsigned C) const {
00261     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00262     Vector V(Rows);
00263     for (unsigned R = 0; R < Rows; ++R)
00264       V[R] = (*this)[R][C];
00265     return V;
00266   }
00267 
00268   /// \brief Reset the matrix to the given value.
00269   Matrix& reset(PBQPNum Val = 0) {
00270     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00271     std::fill(Data, Data + (Rows * Cols), Val);
00272     return *this;
00273   }
00274 
00275   /// \brief Set a single row of this matrix to the given value.
00276   Matrix& setRow(unsigned R, PBQPNum Val) {
00277     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00278     assert(R < Rows && "Row out of bounds.");
00279     std::fill(Data + (R * Cols), Data + ((R + 1) * Cols), Val);
00280     return *this;
00281   }
00282 
00283   /// \brief Set a single column of this matrix to the given value.
00284   Matrix& setCol(unsigned C, PBQPNum Val) {
00285     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00286     assert(C < Cols && "Column out of bounds.");
00287     for (unsigned R = 0; R < Rows; ++R)
00288       (*this)[R][C] = Val;
00289     return *this;
00290   }
00291 
00292   /// \brief Matrix transpose.
00293   Matrix transpose() const {
00294     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00295     Matrix M(Cols, Rows);
00296     for (unsigned r = 0; r < Rows; ++r)
00297       for (unsigned c = 0; c < Cols; ++c)
00298         M[c][r] = (*this)[r][c];
00299     return M;
00300   }
00301 
00302   /// \brief Returns the diagonal of the matrix as a vector.
00303   ///
00304   /// Matrix must be square.
00305   Vector diagonalize() const {
00306     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00307     assert(Rows == Cols && "Attempt to diagonalize non-square matrix.");
00308     Vector V(Rows);
00309     for (unsigned r = 0; r < Rows; ++r)
00310       V[r] = (*this)[r][r];
00311     return V;
00312   }
00313 
00314   /// \brief Add the given matrix to this one.
00315   Matrix& operator+=(const Matrix &M) {
00316     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00317     assert(Rows == M.Rows && Cols == M.Cols &&
00318            "Matrix dimensions mismatch.");
00319     std::transform(Data, Data + (Rows * Cols), M.Data, Data,
00320                    std::plus<PBQPNum>());
00321     return *this;
00322   }
00323 
00324   Matrix operator+(const Matrix &M) {
00325     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00326     Matrix Tmp(*this);
00327     Tmp += M;
00328     return Tmp;
00329   }
00330 
00331   /// \brief Returns the minimum of the given row
00332   PBQPNum getRowMin(unsigned R) const {
00333     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00334     assert(R < Rows && "Row out of bounds");
00335     return *std::min_element(Data + (R * Cols), Data + ((R + 1) * Cols));
00336   }
00337 
00338   /// \brief Returns the minimum of the given column
00339   PBQPNum getColMin(unsigned C) const {
00340     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00341     PBQPNum MinElem = (*this)[0][C];
00342     for (unsigned R = 1; R < Rows; ++R)
00343       if ((*this)[R][C] < MinElem)
00344         MinElem = (*this)[R][C];
00345     return MinElem;
00346   }
00347 
00348   /// \brief Subtracts the given scalar from the elements of the given row.
00349   Matrix& subFromRow(unsigned R, PBQPNum Val) {
00350     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00351     assert(R < Rows && "Row out of bounds");
00352     std::transform(Data + (R * Cols), Data + ((R + 1) * Cols),
00353                    Data + (R * Cols),
00354                    std::bind2nd(std::minus<PBQPNum>(), Val));
00355     return *this;
00356   }
00357 
00358   /// \brief Subtracts the given scalar from the elements of the given column.
00359   Matrix& subFromCol(unsigned C, PBQPNum Val) {
00360     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00361     for (unsigned R = 0; R < Rows; ++R)
00362       (*this)[R][C] -= Val;
00363     return *this;
00364   }
00365 
00366   /// \brief Returns true if this is a zero matrix.
00367   bool isZero() const {
00368     assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix");
00369     return find_if(Data, Data + (Rows * Cols),
00370                    std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) ==
00371       Data + (Rows * Cols);
00372   }
00373 
00374 private:
00375   unsigned Rows, Cols;
00376   PBQPNum *Data;
00377 };
00378 
00379 /// \brief Return a hash_code for the given matrix.
00380 inline hash_code hash_value(const Matrix &M) {
00381   unsigned *MBegin = reinterpret_cast<unsigned*>(M.Data);
00382   unsigned *MEnd = reinterpret_cast<unsigned*>(M.Data + (M.Rows * M.Cols));
00383   return hash_combine(M.Rows, M.Cols, hash_combine_range(MBegin, MEnd));
00384 }
00385 
00386 /// \brief Output a textual representation of the given matrix on the given
00387 ///        output stream.
00388 template <typename OStream>
00389 OStream& operator<<(OStream &OS, const Matrix &M) {
00390   assert((M.getRows() != 0) && "Zero-row matrix badness.");
00391   for (unsigned i = 0; i < M.getRows(); ++i)
00392     OS << M.getRowAsVector(i) << "\n";
00393   return OS;
00394 }
00395 
00396 template <typename Metadata>
00397 class MDVector : public Vector {
00398 public:
00399   MDVector(const Vector &v) : Vector(v), md(*this) { }
00400   MDVector(Vector &&v) : Vector(std::move(v)), md(*this) { }
00401   const Metadata& getMetadata() const { return md; }
00402 private:
00403   Metadata md;
00404 };
00405 
00406 template <typename Metadata>
00407 inline hash_code hash_value(const MDVector<Metadata> &V) {
00408   return hash_value(static_cast<const Vector&>(V));
00409 }
00410 
00411 template <typename Metadata>
00412 class MDMatrix : public Matrix {
00413 public:
00414   MDMatrix(const Matrix &m) : Matrix(m), md(*this) { }
00415   MDMatrix(Matrix &&m) : Matrix(std::move(m)), md(*this) { }
00416   const Metadata& getMetadata() const { return md; }
00417 private:
00418   Metadata md;
00419 };
00420 
00421 template <typename Metadata>
00422 inline hash_code hash_value(const MDMatrix<Metadata> &M) {
00423   return hash_value(static_cast<const Matrix&>(M));
00424 }
00425 
00426 } // namespace PBQP
00427 } // namespace llvm
00428 
00429 #endif // LLVM_CODEGEN_PBQP_MATH_H