A Partitioned Boolean Quadratic Programming (PBQP) based register allocator.

Contributed by Lang Hames.


git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@56959 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 284 insertions, 0 deletions

diff --git a/lib/CodeGen/PBQP.h b/lib/CodeGen/PBQP.h
new file mode 100644
index 0000000..e31ccc4
--- /dev/null
+++ b/lib/CodeGen/PBQP.h
@@ -0,0 +1,284 @@
+//===---------------- PBQP.cpp --------- PBQP Solver ------------*- C++ -*-===//
+//
+//                     The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// Developed by:                   Bernhard Scholz
+//                             The Univesity of Sydney
+//                         http://www.it.usyd.edu.au/~scholz
+//===----------------------------------------------------------------------===//
+
+// TODO:
+//
+//  * Default to null costs on vector initialisation?
+//  * C++-ify the rest of the solver.
+
+#ifndef LLVM_CODEGEN_PBQPSOLVER_H
+#define LLVM_CODEGEN_PBQPSOLVER_H
+
+#include <cassert>
+#include <algorithm>
+#include <functional>
+
+namespace llvm {
+
+//! \brief Floating point type to use in PBQP solver.
+typedef double PBQPNum;
+
+//! \brief PBQP Vector class.
+class PBQPVector {
+public:
+
+  //! \brief Construct a PBQP vector of the given size.
+  explicit PBQPVector(unsigned length) :
+    length(length), data(new PBQPNum[length]) {
+    std::fill(data, data + length, 0);
+  }
+
+  //! \brief Copy construct a PBQP vector.
+  PBQPVector(const PBQPVector &v) :
+    length(v.length), data(new PBQPNum[length]) {
+    std::copy(v.data, v.data + length, data);
+  }
+
+  ~PBQPVector() { delete[] data; }
+
+  //! \brief Assignment operator.
+  PBQPVector& operator=(const PBQPVector &v) {
+    delete[] data;
+    length = v.length;
+    data = new PBQPNum[length];
+    std::copy(v.data, v.data + length, data);
+    return *this;
+  }
+
+  //! \brief Return the length of the vector
+  unsigned getLength() const throw () {
+    return length;
+  }
+
+  //! \brief Element access.
+  PBQPNum& operator[](unsigned index) {
+    assert(index < length && "PBQPVector element access out of bounds.");
+    return data[index];
+  }
+
+  //! \brief Const element access.
+  const PBQPNum& operator[](unsigned index) const {
+    assert(index < length && "PBQPVector element access out of bounds.");
+    return data[index];
+  }
+
+  //! \brief Add another vector to this one.
+  PBQPVector& operator+=(const PBQPVector &v) {
+    assert(length == v.length && "PBQPVector length mismatch.");
+    std::transform(data, data + length, v.data, data, std::plus<PBQPNum>()); 
+    return *this;
+  }
+
+  //! \brief Subtract another vector from this one.
+  PBQPVector& operator-=(const PBQPVector &v) {
+    assert(length == v.length && "PBQPVector length mismatch.");
+    std::transform(data, data + length, v.data, data, std::minus<PBQPNum>()); 
+    return *this;
+  }
+
+  //! \brief Returns the index of the minimum value in this vector
+  unsigned minIndex() const {
+    return std::min_element(data, data + length) - data;
+  }
+
+private:
+  unsigned length;
+  PBQPNum *data;
+};
+
+
+//! \brief PBQP Matrix class
+class PBQPMatrix {
+public:
+
+  //! \brief Construct a PBQP Matrix with the given dimensions.
+  PBQPMatrix(unsigned rows, unsigned cols) :
+    rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
+    std::fill(data, data + (rows * cols), 0);
+  }
+
+  //! \brief Copy construct a PBQP matrix.
+  PBQPMatrix(const PBQPMatrix &m) :
+    rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) {
+    std::copy(m.data, m.data + (rows * cols), data);  
+  }
+
+  ~PBQPMatrix() { delete[] data; }
+
+  //! \brief Assignment operator.
+  PBQPMatrix& operator=(const PBQPMatrix &m) {
+    delete[] data;
+    rows = m.rows; cols = m.cols;
+    data = new PBQPNum[rows * cols];
+    std::copy(m.data, m.data + (rows * cols), data);
+    return *this;
+  }
+
+  //! \brief Return the number of rows in this matrix.
+  unsigned getRows() const throw () { return rows; }
+
+  //! \brief Return the number of cols in this matrix.
+  unsigned getCols() const throw () { return cols; }
+
+  //! \brief Matrix element access.
+  PBQPNum* operator[](unsigned r) {
+    assert(r < rows && "Row out of bounds.");
+    return data + (r * cols);
+  }
+
+  //! \brief Matrix element access.
+  const PBQPNum* operator[](unsigned r) const {
+    assert(r < rows && "Row out of bounds.");
+    return data + (r * cols);
+  }
+
+  //! \brief Returns the given row as a vector.
+  PBQPVector getRowAsVector(unsigned r) const {
+    PBQPVector v(cols);
+    for (unsigned c = 0; c < cols; ++c)
+      v[c] = (*this)[r][c];
+    return v; 
+  }
+
+  //! \brief Reset the matrix to the given value.
+  PBQPMatrix& reset(PBQPNum val = 0) {
+    std::fill(data, data + (rows * cols), val);
+    return *this;
+  }
+
+  //! \brief Set a single row of this matrix to the given value.
+  PBQPMatrix& setRow(unsigned r, PBQPNum val) {
+    assert(r < rows && "Row out of bounds.");
+    std::fill(data + (r * cols), data + ((r + 1) * cols), val);
+    return *this;
+  }
+
+  //! \brief Set a single column of this matrix to the given value.
+  PBQPMatrix& setCol(unsigned c, PBQPNum val) {
+    assert(c < cols && "Column out of bounds.");
+    for (unsigned r = 0; r < rows; ++r)
+      (*this)[r][c] = val;
+    return *this;
+  }
+
+  //! \brief Matrix transpose.
+  PBQPMatrix transpose() const {
+    PBQPMatrix m(cols, rows);
+    for (unsigned r = 0; r < rows; ++r)
+      for (unsigned c = 0; c < cols; ++c)
+        m[c][r] = (*this)[r][c];
+    return m;
+  }
+
+  //! \brief Returns the diagonal of the matrix as a vector.
+  //!
+  //! Matrix must be square.
+  PBQPVector diagonalize() const {
+    assert(rows == cols && "Attempt to diagonalize non-square matrix.");
+
+    PBQPVector v(rows);
+    for (unsigned r = 0; r < rows; ++r)
+      v[r] = (*this)[r][r];
+    return v;
+  } 
+
+  //! \brief Add the given matrix to this one.
+  PBQPMatrix& operator+=(const PBQPMatrix &m) {
+    assert(rows == m.rows && cols == m.cols &&
+           "Matrix dimensions mismatch.");
+    std::transform(data, data + (rows * cols), m.data, data,
+                   std::plus<PBQPNum>());
+    return *this;
+  }
+
+  //! \brief Returns the minimum of the given row
+  PBQPNum getRowMin(unsigned r) const {
+    assert(r < rows && "Row out of bounds");
+    return *std::min_element(data + (r * cols), data + ((r + 1) * cols));
+  }
+
+  //! \brief Returns the minimum of the given column
+  PBQPNum getColMin(unsigned c) const {
+    PBQPNum minElem = (*this)[0][c];
+    for (unsigned r = 1; r < rows; ++r)
+      if ((*this)[r][c] < minElem) minElem = (*this)[r][c];
+    return minElem;
+  }
+
+  //! \brief Subtracts the given scalar from the elements of the given row.
+  PBQPMatrix& subFromRow(unsigned r, PBQPNum val) {
+    assert(r < rows && "Row out of bounds");
+    std::transform(data + (r * cols), data + ((r + 1) * cols),
+                   data + (r * cols),
+                   std::bind2nd(std::minus<PBQPNum>(), val));
+    return *this;
+  }
+
+  //! \brief Subtracts the given scalar from the elements of the given column.
+  PBQPMatrix& subFromCol(unsigned c, PBQPNum val) {
+    for (unsigned r = 0; r < rows; ++r)
+      (*this)[r][c] -= val;
+    return *this;
+  }
+
+  //! \brief Returns true if this is a zero matrix.
+  bool isZero() const {
+    return find_if(data, data + (rows * cols),
+                   std::bind2nd(std::not_equal_to<PBQPNum>(), 0)) ==
+                     data + (rows * cols);
+  }
+
+private:
+  unsigned rows, cols;
+  PBQPNum *data;
+};
+
+#define EPS (1E-8)
+
+#ifndef PBQP_TYPE
+#define PBQP_TYPE
+struct pbqp;
+typedef struct pbqp pbqp;
+#endif
+
+/*****************
+ * PBQP routines *
+ *****************/
+
+/* allocate pbqp problem */
+pbqp *alloc_pbqp(int num);
+
+/* add node costs */
+void add_pbqp_nodecosts(pbqp *this_,int u, PBQPVector *costs);
+
+/* add edge mat */
+void add_pbqp_edgecosts(pbqp *this_,int u,int v,PBQPMatrix *costs);
+
+/* solve PBQP problem */
+void solve_pbqp(pbqp *this_);
+
+/* get solution of a node */
+int get_pbqp_solution(pbqp *this_,int u);
+
+/* alloc PBQP */
+pbqp *alloc_pbqp(int num);
+
+/* free PBQP */
+void free_pbqp(pbqp *this_);
+
+/* is optimal */
+bool is_pbqp_optimal(pbqp *this_);
+
+}
+#endif