summaryrefslogtreecommitdiffstats
path: root/lib/CodeGen/PBQP.h
diff options
context:
space:
mode:
Diffstat (limited to 'lib/CodeGen/PBQP.h')
-rw-r--r--lib/CodeGen/PBQP.h284
1 files changed, 0 insertions, 284 deletions
diff --git a/lib/CodeGen/PBQP.h b/lib/CodeGen/PBQP.h
deleted file mode 100644
index 5fd2c06..0000000
--- a/lib/CodeGen/PBQP.h
+++ /dev/null
@@ -1,284 +0,0 @@
-//===---------------- 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 University 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
OpenPOWER on IntegriCloud