lib/CodeGen/PBQP.h

   1 //===---------------- PBQP.cpp --------- PBQP Solver ------------*- 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 // Developed by:                   Bernhard Scholz
  11 //                             The University of Sydney
  12 //                         http://www.it.usyd.edu.au/~scholz
  13 //===----------------------------------------------------------------------===//
  14
  15 // TODO:
  16 //
  17 //  * Default to null costs on vector initialisation?
  18 //  * C++-ify the rest of the solver.
  19
  20 #ifndef LLVM_CODEGEN_PBQPSOLVER_H
  21 #define LLVM_CODEGEN_PBQPSOLVER_H
  22
  23 #include <cassert>
  24 #include <algorithm>
  25 #include <functional>
  26
  27 namespace llvm {
  28
  29 //! \brief Floating point type to use in PBQP solver.
  30 typedef double PBQPNum;
  31
  32 //! \brief PBQP Vector class.
  33 class PBQPVector {
  34 public:
  35
  36   //! \brief Construct a PBQP vector of the given size.
  37   explicit PBQPVector(unsigned length) :
  38     length(length), data(new PBQPNum[length]) {
  39     std::fill(data, data + length, 0);
  40   }
  41
  42   //! \brief Copy construct a PBQP vector.
  43   PBQPVector(const PBQPVector &v) :
  44     length(v.length), data(new PBQPNum[length]) {
  45     std::copy(v.data, v.data + length, data);
  46   }
  47
  48   ~PBQPVector() { delete[] data; }
  49
  50   //! \brief Assignment operator.
  51   PBQPVector& operator=(const PBQPVector &v) {
  52     delete[] data;
  53     length = v.length;
  54     data = new PBQPNum[length];
  55     std::copy(v.data, v.data + length, data);
  56     return *this;
  57   }
  58
  59   //! \brief Return the length of the vector
  60   unsigned getLength() const throw () {
  61     return length;
  62   }
  63
  64   //! \brief Element access.
  65   PBQPNum& operator[](unsigned index) {
  66     assert(index < length && "PBQPVector element access out of bounds.");
  67     return data[index];
  68   }
  69
  70   //! \brief Const element access.
  71   const PBQPNum& operator[](unsigned index) const {
  72     assert(index < length && "PBQPVector element access out of bounds.");
  73     return data[index];
  74   }
  75
  76   //! \brief Add another vector to this one.
  77   PBQPVector& operator+=(const PBQPVector &v) {
  78     assert(length == v.length && "PBQPVector length mismatch.");
  79     std::transform(data, data + length, v.data, data, std::plus<PBQPNum>());
  80     return *this;
  81   }
  82
  83   //! \brief Subtract another vector from this one.
  84   PBQPVector& operator-=(const PBQPVector &v) {
  85     assert(length == v.length && "PBQPVector length mismatch.");
  86     std::transform(data, data + length, v.data, data, std::minus<PBQPNum>());
  87     return *this;
  88   }
  89
  90   //! \brief Returns the index of the minimum value in this vector
  91   unsigned minIndex() const {
  92     return std::min_element(data, data + length) - data;
  93   }
  94
  95 private:
  96   unsigned length;
  97   PBQPNum *data;
  98 };
  99
 100
 101 //! \brief PBQP Matrix class
 102 class PBQPMatrix {
 103 public:
 104
 105   //! \brief Construct a PBQP Matrix with the given dimensions.
 106   PBQPMatrix(unsigned rows, unsigned cols) :
 107     rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
 108     std::fill(data, data + (rows * cols), 0);
 109   }
 110
 111   //! \brief Copy construct a PBQP matrix.
 112   PBQPMatrix(const PBQPMatrix &m) :
 113     rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) {
 114     std::copy(m.data, m.data + (rows * cols), data);
 115   }
 116
 117   ~PBQPMatrix() { delete[] data; }
 118
 119   //! \brief Assignment operator.
 120   PBQPMatrix& operator=(const PBQPMatrix &m) {
 121     delete[] data;
 122     rows = m.rows; cols = m.cols;
 123     data = new PBQPNum[rows * cols];
 124     std::copy(m.data, m.data + (rows * cols), data);
 125     return *this;
 126   }
 127
 128   //! \brief Return the number of rows in this matrix.
 129   unsigned getRows() const throw () { return rows; }
 130
 131   //! \brief Return the number of cols in this matrix.
 132   unsigned getCols() const throw () { return cols; }
 133
 134   //! \brief Matrix element access.
 135   PBQPNum* operator[](unsigned r) {
 136     assert(r < rows && "Row out of bounds.");
 137     return data + (r * cols);
 138   }
 139
 140   //! \brief Matrix element access.
 141   const PBQPNum* operator[](unsigned r) const {
 142     assert(r < rows && "Row out of bounds.");
 143     return data + (r * cols);
 144   }
 145
 146   //! \brief Returns the given row as a vector.
 147   PBQPVector getRowAsVector(unsigned r) const {
 148     PBQPVector v(cols);
 149     for (unsigned c = 0; c < cols; ++c)
 150       v[c] = (*this)[r][c];
 151     return v;
 152   }
 153
 154   //! \brief Reset the matrix to the given value.
 155   PBQPMatrix& reset(PBQPNum val = 0) {
 156     std::fill(data, data + (rows * cols), val);
 157     return *this;
 158   }
 159
 160   //! \brief Set a single row of this matrix to the given value.
 161   PBQPMatrix& setRow(unsigned r, PBQPNum val) {
 162     assert(r < rows && "Row out of bounds.");
 163     std::fill(data + (r * cols), data + ((r + 1) * cols), val);
 164     return *this;
 165   }
 166
 167   //! \brief Set a single column of this matrix to the given value.
 168   PBQPMatrix& setCol(unsigned c, PBQPNum val) {
 169     assert(c < cols && "Column out of bounds.");
 170     for (unsigned r = 0; r < rows; ++r)
 171       (*this)[r][c] = val;
 172     return *this;
 173   }
 174
 175   //! \brief Matrix transpose.
 176   PBQPMatrix transpose() const {
 177     PBQPMatrix m(cols, rows);
 178     for (unsigned r = 0; r < rows; ++r)
 179       for (unsigned c = 0; c < cols; ++c)
 180         m[c][r] = (*this)[r][c];
 181     return m;
 182   }
 183
 184   //! \brief Returns the diagonal of the matrix as a vector.
 185   //!
 186   //! Matrix must be square.
 187   PBQPVector diagonalize() const {
 188     assert(rows == cols && "Attempt to diagonalize non-square matrix.");
 189
 190     PBQPVector v(rows);
 191     for (unsigned r = 0; r < rows; ++r)
 192       v[r] = (*this)[r][r];
 193     return v;
 194   }
 195
 196   //! \brief Add the given matrix to this one.
 197   PBQPMatrix& operator+=(const PBQPMatrix &m) {
 198     assert(rows == m.rows && cols == m.cols &&
 199            "Matrix dimensions mismatch.");
 200     std::transform(data, data + (rows * cols), m.data, data,
 201                    std::plus<PBQPNum>());
 202     return *this;
 203   }
 204
 205   //! \brief Returns the minimum of the given row
 206   PBQPNum getRowMin(unsigned r) const {
 207     assert(r < rows && "Row out of bounds");
 208     return *std::min_element(data + (r * cols), data + ((r + 1) * cols));
 209   }
 210
 211   //! \brief Returns the minimum of the given column
 212   PBQPNum getColMin(unsigned c) const {
 213     PBQPNum minElem = (*this)[0][c];
 214     for (unsigned r = 1; r < rows; ++r)
 215       if ((*this)[r][c] < minElem) minElem = (*this)[r][c];
 216     return minElem;
 217   }
 218
 219   //! \brief Subtracts the given scalar from the elements of the given row.
 220   PBQPMatrix& subFromRow(unsigned r, PBQPNum val) {
 221     assert(r < rows && "Row out of bounds");
 222     std::transform(data + (r * cols), data + ((r + 1) * cols),
 223                    data + (r * cols),
 224                    std::bind2nd(std::minus<PBQPNum>(), val));
 225     return *this;
 226   }
 227
 228   //! \brief Subtracts the given scalar from the elements of the given column.
 229   PBQPMatrix& subFromCol(unsigned c, PBQPNum val) {
 230     for (unsigned r = 0; r < rows; ++r)
 231       (*this)[r][c] -= val;
 232     return *this;
 233   }
 234
 235   //! \brief Returns true if this is a zero matrix.
 236   bool isZero() const {
 237     return find_if(data, data + (rows * cols),
 238                    std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) ==
 239                      data + (rows * cols);
 240   }
 241
 242 private:
 243   unsigned rows, cols;
 244   PBQPNum *data;
 245 };
 246
 247 #define EPS (1E-8)
 248
 249 #ifndef PBQP_TYPE
 250 #define PBQP_TYPE
 251 struct pbqp;
 252 typedef struct pbqp pbqp;
 253 #endif
 254
 255 /*****************
 256  * PBQP routines *
 257  *****************/
 258
 259 /* allocate pbqp problem */
 260 pbqp *alloc_pbqp(int num);
 261
 262 /* add node costs */
 263 void add_pbqp_nodecosts(pbqp *this_,int u, PBQPVector *costs);
 264
 265 /* add edge mat */
 266 void add_pbqp_edgecosts(pbqp *this_,int u,int v,PBQPMatrix *costs);
 267
 268 /* solve PBQP problem */
 269 void solve_pbqp(pbqp *this_);
 270
 271 /* get solution of a node */
 272 int get_pbqp_solution(pbqp *this_,int u);
 273
 274 /* alloc PBQP */
 275 pbqp *alloc_pbqp(int num);
 276
 277 /* free PBQP */
 278 void free_pbqp(pbqp *this_);
 279
 280 /* is optimal */
 281 bool is_pbqp_optimal(pbqp *this_);
 282
 283 }
 284 #endif