From b1290a6cc40f7caa0351450ce7021a0d48b5f2c0 Mon Sep 17 00:00:00 2001 From: Evan Cheng Date: Thu, 2 Oct 2008 18:29:27 +0000 Subject: 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 --- lib/CodeGen/PBQP.h | 284 +++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 284 insertions(+) create mode 100644 lib/CodeGen/PBQP.h (limited to 'lib/CodeGen/PBQP.h') 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 +#include +#include + +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()); + 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()); + 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()); + 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(), 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(), 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 -- cgit v1.1