+++ /dev/null
-//===-- AnnotatedGraph.h - Annotated PBQP Graph -----------------*- C++ -*-===//
-//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Annotated PBQP Graph class. This class is used internally by the PBQP solver
-// to cache information to speed up reduction.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H
-#define LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H
-
-#include "GraphBase.h"
-
-namespace PBQP {
-
-
-template <typename NodeData, typename EdgeData> class AnnotatedEdge;
-
-template <typename NodeData, typename EdgeData>
-class AnnotatedNode : public NodeBase<AnnotatedNode<NodeData, EdgeData>,
- AnnotatedEdge<NodeData, EdgeData> > {
-private:
-
- NodeData nodeData;
-
-public:
-
- AnnotatedNode(const Vector &costs, const NodeData &nodeData) :
- NodeBase<AnnotatedNode<NodeData, EdgeData>,
- AnnotatedEdge<NodeData, EdgeData> >(costs),
- nodeData(nodeData) {}
-
- NodeData& getNodeData() { return nodeData; }
- const NodeData& getNodeData() const { return nodeData; }
-
-};
-
-template <typename NodeData, typename EdgeData>
-class AnnotatedEdge : public EdgeBase<AnnotatedNode<NodeData, EdgeData>,
- AnnotatedEdge<NodeData, EdgeData> > {
-private:
-
- typedef typename GraphBase<AnnotatedNode<NodeData, EdgeData>,
- AnnotatedEdge<NodeData, EdgeData> >::NodeIterator
- NodeIterator;
-
- EdgeData edgeData;
-
-public:
-
-
- AnnotatedEdge(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
- const Matrix &costs, const EdgeData &edgeData) :
- EdgeBase<AnnotatedNode<NodeData, EdgeData>,
- AnnotatedEdge<NodeData, EdgeData> >(node1Itr, node2Itr, costs),
- edgeData(edgeData) {}
-
- EdgeData& getEdgeData() { return edgeData; }
- const EdgeData& getEdgeData() const { return edgeData; }
-
-};
-
-template <typename NodeData, typename EdgeData>
-class AnnotatedGraph : public GraphBase<AnnotatedNode<NodeData, EdgeData>,
- AnnotatedEdge<NodeData, EdgeData> > {
-private:
-
- typedef GraphBase<AnnotatedNode<NodeData, EdgeData>,
- AnnotatedEdge<NodeData, EdgeData> > PGraph;
-
- typedef AnnotatedNode<NodeData, EdgeData> NodeEntry;
- typedef AnnotatedEdge<NodeData, EdgeData> EdgeEntry;
-
-
- void copyFrom(const AnnotatedGraph &other) {
- if (!other.areNodeIDsValid()) {
- other.assignNodeIDs();
- }
- std::vector<NodeIterator> newNodeItrs(other.getNumNodes());
-
- for (ConstNodeIterator nItr = other.nodesBegin(), nEnd = other.nodesEnd();
- nItr != nEnd; ++nItr) {
- newNodeItrs[other.getNodeID(nItr)] = addNode(other.getNodeCosts(nItr));
- }
-
- for (ConstEdgeIterator eItr = other.edgesBegin(), eEnd = other.edgesEnd();
- eItr != eEnd; ++eItr) {
-
- unsigned node1ID = other.getNodeID(other.getEdgeNode1(eItr)),
- node2ID = other.getNodeID(other.getEdgeNode2(eItr));
-
- addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID],
- other.getEdgeCosts(eItr), other.getEdgeData(eItr));
- }
-
- }
-
-public:
-
- typedef typename PGraph::NodeIterator NodeIterator;
- typedef typename PGraph::ConstNodeIterator ConstNodeIterator;
- typedef typename PGraph::EdgeIterator EdgeIterator;
- typedef typename PGraph::ConstEdgeIterator ConstEdgeIterator;
-
- AnnotatedGraph() {}
-
- AnnotatedGraph(const AnnotatedGraph &other) {
- copyFrom(other);
- }
-
- AnnotatedGraph& operator=(const AnnotatedGraph &other) {
- PGraph::clear();
- copyFrom(other);
- return *this;
- }
-
- NodeIterator addNode(const Vector &costs, const NodeData &data) {
- return PGraph::addConstructedNode(NodeEntry(costs, data));
- }
-
- EdgeIterator addEdge(const NodeIterator &node1Itr,
- const NodeIterator &node2Itr,
- const Matrix &costs, const EdgeData &data) {
- return PGraph::addConstructedEdge(EdgeEntry(node1Itr, node2Itr,
- costs, data));
- }
-
- NodeData& getNodeData(const NodeIterator &nodeItr) {
- return PGraph::getNodeEntry(nodeItr).getNodeData();
- }
-
- const NodeData& getNodeData(const NodeIterator &nodeItr) const {
- return PGraph::getNodeEntry(nodeItr).getNodeData();
- }
-
- EdgeData& getEdgeData(const EdgeIterator &edgeItr) {
- return PGraph::getEdgeEntry(edgeItr).getEdgeData();
- }
-
- const EdgeEntry& getEdgeData(const EdgeIterator &edgeItr) const {
- return PGraph::getEdgeEntry(edgeItr).getEdgeData();
- }
-
- SimpleGraph toSimpleGraph() const {
- SimpleGraph g;
-
- if (!PGraph::areNodeIDsValid()) {
- PGraph::assignNodeIDs();
- }
- std::vector<SimpleGraph::NodeIterator> newNodeItrs(PGraph::getNumNodes());
-
- for (ConstNodeIterator nItr = PGraph::nodesBegin(),
- nEnd = PGraph::nodesEnd();
- nItr != nEnd; ++nItr) {
-
- newNodeItrs[getNodeID(nItr)] = g.addNode(getNodeCosts(nItr));
- }
-
- for (ConstEdgeIterator
- eItr = PGraph::edgesBegin(), eEnd = PGraph::edgesEnd();
- eItr != eEnd; ++eItr) {
-
- unsigned node1ID = getNodeID(getEdgeNode1(eItr)),
- node2ID = getNodeID(getEdgeNode2(eItr));
-
- g.addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID],
- getEdgeCosts(eItr));
- }
-
- return g;
- }
-
-};
-
-
-}
-
-#endif // LLVM_CODEGEN_PBQP_ANNOTATEDGRAPH_H
+++ /dev/null
-//===-- ExhaustiveSolver.h - Brute Force PBQP Solver ------------*- C++ -*-===//
-//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Uses a trivial brute force algorithm to solve a PBQP problem.
-// PBQP is NP-HARD - This solver should only be used for debugging small
-// problems.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H
-#define LLVM_CODEGEN_PBQP_EXHAUSTIVESOLVER_H
-
-#include "Solver.h"
-
-namespace PBQP {
-
-/// A brute force PBQP solver. This solver takes exponential time. It should
-/// only be used for debugging purposes.
-class ExhaustiveSolverImpl {
-private:
-
- const SimpleGraph &g;
-
- PBQPNum getSolutionCost(const Solution &solution) const {
- PBQPNum cost = 0.0;
-
- for (SimpleGraph::ConstNodeIterator
- nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
- nodeItr != nodeEnd; ++nodeItr) {
-
- unsigned nodeId = g.getNodeID(nodeItr);
-
- cost += g.getNodeCosts(nodeItr)[solution.getSelection(nodeId)];
- }
-
- for (SimpleGraph::ConstEdgeIterator
- edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
- edgeItr != edgeEnd; ++edgeItr) {
-
- SimpleGraph::ConstNodeIterator n1 = g.getEdgeNode1Itr(edgeItr),
- n2 = g.getEdgeNode2Itr(edgeItr);
- unsigned sol1 = solution.getSelection(g.getNodeID(n1)),
- sol2 = solution.getSelection(g.getNodeID(n2));
-
- cost += g.getEdgeCosts(edgeItr)[sol1][sol2];
- }
-
- return cost;
- }
-
-public:
-
- ExhaustiveSolverImpl(const SimpleGraph &g) : g(g) {}
-
- Solution solve() const {
- Solution current(g.getNumNodes(), true), optimal(current);
-
- PBQPNum bestCost = std::numeric_limits<PBQPNum>::infinity();
- bool finished = false;
-
- while (!finished) {
- PBQPNum currentCost = getSolutionCost(current);
-
- if (currentCost < bestCost) {
- optimal = current;
- bestCost = currentCost;
- }
-
- // assume we're done.
- finished = true;
-
- for (unsigned i = 0; i < g.getNumNodes(); ++i) {
- if (current.getSelection(i) ==
- (g.getNodeCosts(g.getNodeItr(i)).getLength() - 1)) {
- current.setSelection(i, 0);
- }
- else {
- current.setSelection(i, current.getSelection(i) + 1);
- finished = false;
- break;
- }
- }
-
- }
-
- optimal.setSolutionCost(bestCost);
-
- return optimal;
- }
-
-};
-
-class ExhaustiveSolver : public Solver {
-public:
- ~ExhaustiveSolver() {}
- Solution solve(const SimpleGraph &g) const {
- ExhaustiveSolverImpl solver(g);
- return solver.solve();
- }
-};
-
-}
-
-#endif // LLVM_CODGEN_PBQP_EXHAUSTIVESOLVER_HPP
--- /dev/null
+//===-------------------- Graph.h - PBQP Graph ------------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+//
+// PBQP Graph class.
+//
+//===----------------------------------------------------------------------===//
+
+
+#ifndef LLVM_CODEGEN_PBQP_GRAPH_H
+#define LLVM_CODEGEN_PBQP_GRAPH_H
+
+#include "Math.h"
+
+#include <list>
+#include <vector>
+
+namespace PBQP {
+
+ /// PBQP Graph class.
+ /// Instances of this class describe PBQP problems.
+ class Graph {
+ private:
+
+ // ----- TYPEDEFS -----
+ class NodeEntry;
+ class EdgeEntry;
+
+ typedef std::list<NodeEntry> NodeList;
+ typedef std::list<EdgeEntry> EdgeList;
+
+ public:
+
+ typedef NodeList::iterator NodeItr;
+ typedef EdgeList::iterator EdgeItr;
+
+ private:
+
+ typedef std::list<EdgeItr> AdjEdgeList;
+
+ public:
+
+ typedef AdjEdgeList::iterator AdjEdgeItr;
+
+ private:
+
+ class NodeEntry {
+ private:
+ Vector costs;
+ AdjEdgeList adjEdges;
+ unsigned degree;
+ void *data;
+ public:
+ NodeEntry(const Vector &costs) : costs(costs), degree(0) {}
+ Vector& getCosts() { return costs; }
+ unsigned getDegree() const { return degree; }
+ AdjEdgeItr edgesBegin() { return adjEdges.begin(); }
+ AdjEdgeItr edgesEnd() { return adjEdges.end(); }
+ AdjEdgeItr addEdge(EdgeItr e) {
+ ++degree;
+ return adjEdges.insert(adjEdges.end(), e);
+ }
+ void removeEdge(AdjEdgeItr ae) {
+ --degree;
+ adjEdges.erase(ae);
+ }
+ void setData(void *data) { this->data = data; }
+ void* getData() { return data; }
+ };
+
+ class EdgeEntry {
+ private:
+ NodeItr node1, node2;
+ Matrix costs;
+ AdjEdgeItr node1AEItr, node2AEItr;
+ void *data;
+ public:
+ EdgeEntry(NodeItr node1, NodeItr node2, const Matrix &costs)
+ : node1(node1), node2(node2), costs(costs) {}
+ NodeItr getNode1() const { return node1; }
+ NodeItr getNode2() const { return node2; }
+ Matrix& getCosts() { return costs; }
+ void setNode1AEItr(AdjEdgeItr ae) { node1AEItr = ae; }
+ AdjEdgeItr getNode1AEItr() { return node1AEItr; }
+ void setNode2AEItr(AdjEdgeItr ae) { node2AEItr = ae; }
+ AdjEdgeItr getNode2AEItr() { return node2AEItr; }
+ void setData(void *data) { this->data = data; }
+ void *getData() { return data; }
+ };
+
+ // ----- MEMBERS -----
+
+ NodeList nodes;
+ unsigned numNodes;
+
+ EdgeList edges;
+ unsigned numEdges;
+
+ // ----- INTERNAL METHODS -----
+
+ NodeEntry& getNode(NodeItr nItr) { return *nItr; }
+ const NodeEntry& getNode(NodeItr nItr) const { return *nItr; }
+ EdgeEntry& getEdge(EdgeItr eItr) { return *eItr; }
+ const EdgeEntry& getEdge(EdgeItr eItr) const { return *eItr; }
+
+ NodeItr addConstructedNode(const NodeEntry &n) {
+ ++numNodes;
+ return nodes.insert(nodes.end(), n);
+ }
+
+ EdgeItr addConstructedEdge(const EdgeEntry &e) {
+ assert(findEdge(e.getNode1(), e.getNode2()) == edges.end() &&
+ "Attempt to add duplicate edge.");
+ ++numEdges;
+ EdgeItr edgeItr = edges.insert(edges.end(), e);
+ EdgeEntry &ne = getEdge(edgeItr);
+ NodeEntry &n1 = getNode(ne.getNode1());
+ NodeEntry &n2 = getNode(ne.getNode2());
+ // Sanity check on matrix dimensions:
+ assert((n1.getCosts().getLength() == ne.getCosts().getRows()) &&
+ (n2.getCosts().getLength() == ne.getCosts().getCols()) &&
+ "Edge cost dimensions do not match node costs dimensions.");
+ ne.setNode1AEItr(n1.addEdge(edgeItr));
+ ne.setNode2AEItr(n2.addEdge(edgeItr));
+ return edgeItr;
+ }
+
+ public:
+
+ Graph() : numNodes(0), numEdges(0) {}
+
+ /// \brief Add a node with the given costs.
+ /// @param costs Cost vector for the new node.
+ /// @return Node iterator for the added node.
+ NodeItr addNode(const Vector &costs) {
+ return addConstructedNode(NodeEntry(costs));
+ }
+
+ /// \brief Add an edge between the given nodes with the given costs.
+ /// @param n1Itr First node.
+ /// @param n2Itr Second node.
+ /// @return Edge iterator for the added edge.
+ EdgeItr addEdge(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr,
+ const Matrix &costs) {
+ assert(getNodeCosts(n1Itr).getLength() == costs.getRows() &&
+ getNodeCosts(n2Itr).getLength() == costs.getCols() &&
+ "Matrix dimensions mismatch.");
+ return addConstructedEdge(EdgeEntry(n1Itr, n2Itr, costs));
+ }
+
+ /// \brief Get the number of nodes in the graph.
+ /// @return Number of nodes in the graph.
+ unsigned getNumNodes() const { return numNodes; }
+
+ /// \brief Get the number of edges in the graph.
+ /// @return Number of edges in the graph.
+ unsigned getNumEdges() const { return numEdges; }
+
+ /// \brief Get a node's cost vector.
+ /// @param nItr Node iterator.
+ /// @return Node cost vector.
+ Vector& getNodeCosts(NodeItr nItr) { return getNode(nItr).getCosts(); }
+
+ /// \brief Set a node's data pointer.
+ /// @param nItr Node iterator.
+ /// @param data Pointer to node data.
+ ///
+ /// Typically used by a PBQP solver to attach data to aid in solution.
+ void setNodeData(NodeItr nItr, void *data) { getNode(nItr).setData(data); }
+
+ /// \brief Get the node's data pointer.
+ /// @param nItr Node iterator.
+ /// @return Pointer to node data.
+ void* getNodeData(NodeItr nItr) { return getNode(nItr).getData(); }
+
+ /// \brief Get an edge's cost matrix.
+ /// @param eItr Edge iterator.
+ /// @return Edge cost matrix.
+ Matrix& getEdgeCosts(EdgeItr eItr) { return getEdge(eItr).getCosts(); }
+
+ /// \brief Set an edge's data pointer.
+ /// @param eItr Edge iterator.
+ /// @param data Pointer to edge data.
+ ///
+ /// Typically used by a PBQP solver to attach data to aid in solution.
+ void setEdgeData(EdgeItr eItr, void *data) { getEdge(eItr).setData(data); }
+
+ /// \brief Get an edge's data pointer.
+ /// @param eItr Edge iterator.
+ /// @return Pointer to edge data.
+ void* getEdgeData(EdgeItr eItr) { return getEdge(eItr).getData(); }
+
+ /// \brief Get a node's degree.
+ /// @param nItr Node iterator.
+ /// @return The degree of the node.
+ unsigned getNodeDegree(NodeItr nItr) const {
+ return getNode(nItr).getDegree();
+ }
+
+ /// \brief Begin iterator for node set.
+ NodeItr nodesBegin() { return nodes.begin(); }
+
+ /// \brief End iterator for node set.
+ NodeItr nodesEnd() { return nodes.end(); }
+
+ /// \brief Begin iterator for edge set.
+ EdgeItr edgesBegin() { return edges.begin(); }
+
+ /// \brief End iterator for edge set.
+ EdgeItr edgesEnd() { return edges.end(); }
+
+ /// \brief Get begin iterator for adjacent edge set.
+ /// @param nItr Node iterator.
+ /// @return Begin iterator for the set of edges connected to the given node.
+ AdjEdgeItr adjEdgesBegin(NodeItr nItr) {
+ return getNode(nItr).edgesBegin();
+ }
+
+ /// \brief Get end iterator for adjacent edge set.
+ /// @param nItr Node iterator.
+ /// @return End iterator for the set of edges connected to the given node.
+ AdjEdgeItr adjEdgesEnd(NodeItr nItr) {
+ return getNode(nItr).edgesEnd();
+ }
+
+ /// \brief Get the first node connected to this edge.
+ /// @param eItr Edge iterator.
+ /// @return The first node connected to the given edge.
+ NodeItr getEdgeNode1(EdgeItr eItr) {
+ return getEdge(eItr).getNode1();
+ }
+
+ /// \brief Get the second node connected to this edge.
+ /// @param eItr Edge iterator.
+ /// @return The second node connected to the given edge.
+ NodeItr getEdgeNode2(EdgeItr eItr) {
+ return getEdge(eItr).getNode2();
+ }
+
+ /// \brief Get the "other" node connected to this edge.
+ /// @param eItr Edge iterator.
+ /// @param nItr Node iterator for the "given" node.
+ /// @return The iterator for the "other" node connected to this edge.
+ NodeItr getEdgeOtherNode(EdgeItr eItr, NodeItr nItr) {
+ EdgeEntry &e = getEdge(eItr);
+ if (e.getNode1() == nItr) {
+ return e.getNode2();
+ } // else
+ return e.getNode1();
+ }
+
+ /// \brief Get the edge connecting two nodes.
+ /// @param n1Itr First node iterator.
+ /// @param n2Itr Second node iterator.
+ /// @return An iterator for edge (n1Itr, n2Itr) if such an edge exists,
+ /// otherwise returns edgesEnd().
+ EdgeItr findEdge(NodeItr n1Itr, NodeItr n2Itr) {
+ for (AdjEdgeItr aeItr = adjEdgesBegin(n1Itr), aeEnd = adjEdgesEnd(n1Itr);
+ aeItr != aeEnd; ++aeItr) {
+ if ((getEdgeNode1(*aeItr) == n2Itr) ||
+ (getEdgeNode2(*aeItr) == n2Itr)) {
+ return *aeItr;
+ }
+ }
+ return edges.end();
+ }
+
+ /// \brief Remove a node from the graph.
+ /// @param nItr Node iterator.
+ void removeNode(NodeItr nItr) {
+ NodeEntry &n = getNode(nItr);
+ for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end;) {
+ EdgeItr eItr = *itr;
+ ++itr;
+ removeEdge(eItr);
+ }
+ nodes.erase(nItr);
+ --numNodes;
+ }
+
+ /// \brief Remove an edge from the graph.
+ /// @param eItr Edge iterator.
+ void removeEdge(EdgeItr eItr) {
+ EdgeEntry &e = getEdge(eItr);
+ NodeEntry &n1 = getNode(e.getNode1());
+ NodeEntry &n2 = getNode(e.getNode2());
+ n1.removeEdge(e.getNode1AEItr());
+ n2.removeEdge(e.getNode2AEItr());
+ edges.erase(eItr);
+ --numEdges;
+ }
+
+ /// \brief Remove all nodes and edges from the graph.
+ void clear() {
+ nodes.clear();
+ edges.clear();
+ numNodes = numEdges = 0;
+ }
+
+ /// \brief Print a representation of this graph in DOT format.
+ /// @param os Output stream to print on.
+ template <typename OStream>
+ void printDot(OStream &os) {
+
+ os << "graph {\n";
+
+ for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd();
+ nodeItr != nodeEnd; ++nodeItr) {
+
+ os << " node" << nodeItr << " [ label=\""
+ << nodeItr << ": " << getNodeCosts(nodeItr) << "\" ]\n";
+ }
+
+ os << " edge [ len=" << getNumNodes() << " ]\n";
+
+ for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd();
+ edgeItr != edgeEnd; ++edgeItr) {
+
+ os << " node" << getEdgeNode1(edgeItr)
+ << " -- node" << getEdgeNode2(edgeItr)
+ << " [ label=\"";
+
+ const Matrix &edgeCosts = getEdgeCosts(edgeItr);
+
+ for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
+ os << edgeCosts.getRowAsVector(i) << "\\n";
+ }
+ os << "\" ]\n";
+ }
+ os << "}\n";
+ }
+
+ };
+
+ class NodeItrComparator {
+ public:
+ bool operator()(Graph::NodeItr n1, Graph::NodeItr n2) const {
+ return &*n1 < &*n2;
+ }
+ };
+
+ class EdgeItrCompartor {
+ public:
+ bool operator()(Graph::EdgeItr e1, Graph::EdgeItr e2) const {
+ return &*e1 < &*e2;
+ }
+ };
+
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_GRAPH_HPP
+++ /dev/null
-//===-- GraphBase.h - Abstract Base PBQP Graph ------------------*- C++ -*-===//
-//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Base class for PBQP Graphs.
-//
-//===----------------------------------------------------------------------===//
-
-
-#ifndef LLVM_CODEGEN_PBQP_GRAPHBASE_H
-#define LLVM_CODEGEN_PBQP_GRAPHBASE_H
-
-#include "PBQPMath.h"
-
-#include <list>
-#include <vector>
-
-namespace PBQP {
-
-// UGLY, but I'm not sure there's a good way around this: We need to be able to
-// look up a Node's "adjacent edge list" structure type before the Node type is
-// fully constructed. We can enable this by pushing the choice of data type
-// out into this traits class.
-template <typename Graph>
-class NodeBaseTraits {
- public:
- typedef std::list<typename Graph::EdgeIterator> AdjEdgeList;
- typedef typename AdjEdgeList::iterator AdjEdgeIterator;
- typedef typename AdjEdgeList::const_iterator ConstAdjEdgeIterator;
-};
-
-/// \brief Base for concrete graph classes. Provides a basic set of graph
-/// operations which are useful for PBQP solvers.
-template <typename NodeEntry, typename EdgeEntry>
-class GraphBase {
-private:
-
- typedef GraphBase<NodeEntry, EdgeEntry> ThisGraphT;
-
- typedef std::list<NodeEntry> NodeList;
- typedef std::list<EdgeEntry> EdgeList;
-
- NodeList nodeList;
- unsigned nodeListSize;
-
- EdgeList edgeList;
- unsigned edgeListSize;
-
- GraphBase(const ThisGraphT &other) { abort(); }
- void operator=(const ThisGraphT &other) { abort(); }
-
-public:
-
- /// \brief Iterates over the nodes of a graph.
- typedef typename NodeList::iterator NodeIterator;
- /// \brief Iterates over the nodes of a const graph.
- typedef typename NodeList::const_iterator ConstNodeIterator;
- /// \brief Iterates over the edges of a graph.
- typedef typename EdgeList::iterator EdgeIterator;
- /// \brief Iterates over the edges of a const graph.
- typedef typename EdgeList::const_iterator ConstEdgeIterator;
-
- /// \brief Iterates over the edges attached to a node.
- typedef typename NodeBaseTraits<ThisGraphT>::AdjEdgeIterator
- AdjEdgeIterator;
-
- /// \brief Iterates over the edges attached to a node in a const graph.
- typedef typename NodeBaseTraits<ThisGraphT>::ConstAdjEdgeIterator
- ConstAdjEdgeIterator;
-
-private:
-
- typedef std::vector<NodeIterator> IDToNodeMap;
-
- IDToNodeMap idToNodeMap;
- bool nodeIDsValid;
-
- void invalidateNodeIDs() {
- if (nodeIDsValid) {
- idToNodeMap.clear();
- nodeIDsValid = false;
- }
- }
-
- template <typename ItrT>
- bool iteratorInRange(ItrT itr, const ItrT &begin, const ItrT &end) {
- for (ItrT t = begin; t != end; ++t) {
- if (itr == t)
- return true;
- }
-
- return false;
- }
-
-protected:
-
- GraphBase() : nodeListSize(0), edgeListSize(0), nodeIDsValid(false) {}
-
- NodeEntry& getNodeEntry(const NodeIterator &nodeItr) { return *nodeItr; }
- const NodeEntry& getNodeEntry(const ConstNodeIterator &nodeItr) const {
- return *nodeItr;
- }
-
- EdgeEntry& getEdgeEntry(const EdgeIterator &edgeItr) { return *edgeItr; }
- const EdgeEntry& getEdgeEntry(const ConstEdgeIterator &edgeItr) const {
- return *edgeItr;
- }
-
- NodeIterator addConstructedNode(const NodeEntry &nodeEntry) {
- ++nodeListSize;
-
- invalidateNodeIDs();
-
- NodeIterator newNodeItr = nodeList.insert(nodeList.end(), nodeEntry);
-
- return newNodeItr;
- }
-
- EdgeIterator addConstructedEdge(const EdgeEntry &edgeEntry) {
-
- assert((findEdge(edgeEntry.getNode1Itr(), edgeEntry.getNode2Itr())
- == edgeList.end()) && "Attempt to add duplicate edge.");
-
- ++edgeListSize;
-
- // Add the edge to the graph.
- EdgeIterator edgeItr = edgeList.insert(edgeList.end(), edgeEntry);
-
- // Get a reference to the version in the graph.
- EdgeEntry &newEdgeEntry = getEdgeEntry(edgeItr);
-
- // Node entries:
- NodeEntry &node1Entry = getNodeEntry(newEdgeEntry.getNode1Itr()),
- &node2Entry = getNodeEntry(newEdgeEntry.getNode2Itr());
-
- // Sanity check on matrix dimensions.
- assert((node1Entry.getCosts().getLength() ==
- newEdgeEntry.getCosts().getRows()) &&
- (node2Entry.getCosts().getLength() ==
- newEdgeEntry.getCosts().getCols()) &&
- "Matrix dimensions do not match cost vector dimensions.");
-
- // Create links between nodes and edges.
- newEdgeEntry.setNode1ThisEdgeItr(
- node1Entry.addAdjEdge(edgeItr));
- newEdgeEntry.setNode2ThisEdgeItr(
- node2Entry.addAdjEdge(edgeItr));
-
- return edgeItr;
- }
-
-public:
-
- /// \brief Returns the number of nodes in this graph.
- unsigned getNumNodes() const { return nodeListSize; }
-
- /// \brief Returns the number of edges in this graph.
- unsigned getNumEdges() const { return edgeListSize; }
-
- /// \brief Return the cost vector for the given node.
- Vector& getNodeCosts(const NodeIterator &nodeItr) {
- return getNodeEntry(nodeItr).getCosts();
- }
-
- /// \brief Return the cost vector for the give node.
- const Vector& getNodeCosts(const ConstNodeIterator &nodeItr) const {
- return getNodeEntry(nodeItr).getCosts();
- }
-
- /// \brief Return the degree of the given node.
- unsigned getNodeDegree(const NodeIterator &nodeItr) const {
- return getNodeEntry(nodeItr).getDegree();
- }
-
- /// \brief Assigns sequential IDs to the nodes, starting at 0, which
- /// remain valid until the next addition or removal of a node.
- void assignNodeIDs() {
- unsigned curID = 0;
- idToNodeMap.resize(getNumNodes());
- for (NodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd();
- nodeItr != nodeEnd; ++nodeItr, ++curID) {
- getNodeEntry(nodeItr).setID(curID);
- idToNodeMap[curID] = nodeItr;
- }
- nodeIDsValid = true;
- }
-
- /// \brief Assigns sequential IDs to the nodes using the ordering of the
- /// given vector.
- void assignNodeIDs(const std::vector<NodeIterator> &nodeOrdering) {
- assert((getNumNodes() == nodeOrdering.size()) &&
- "Wrong number of nodes in node ordering.");
- idToNodeMap = nodeOrdering;
- for (unsigned nodeID = 0; nodeID < idToNodeMap.size(); ++nodeID) {
- getNodeEntry(idToNodeMap[nodeID]).setID(nodeID);
- }
- nodeIDsValid = true;
- }
-
- /// \brief Returns true if valid node IDs are assigned, false otherwise.
- bool areNodeIDsValid() const { return nodeIDsValid; }
-
- /// \brief Return the numeric ID of the given node.
- ///
- /// Calls to this method will result in an assertion failure if there have
- /// been any node additions or removals since the last call to
- /// assignNodeIDs().
- unsigned getNodeID(const ConstNodeIterator &nodeItr) const {
- assert(nodeIDsValid && "Attempt to retrieve invalid ID.");
- return getNodeEntry(nodeItr).getID();
- }
-
- /// \brief Returns the iterator associated with the given node ID.
- NodeIterator getNodeItr(unsigned nodeID) {
- assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID.");
- return idToNodeMap[nodeID];
- }
-
- /// \brief Returns the iterator associated with the given node ID.
- ConstNodeIterator getNodeItr(unsigned nodeID) const {
- assert(nodeIDsValid && "Attempt to retrieve iterator with invalid ID.");
- return idToNodeMap[nodeID];
- }
-
- /// \brief Removes the given node (and all attached edges) from the graph.
- void removeNode(const NodeIterator &nodeItr) {
- assert(iteratorInRange(nodeItr, nodeList.begin(), nodeList.end()) &&
- "Iterator does not belong to this graph!");
-
- invalidateNodeIDs();
-
- NodeEntry &nodeEntry = getNodeEntry(nodeItr);
-
- // We need to copy this out because it will be destroyed as the edges are
- // removed.
- typedef std::vector<EdgeIterator> AdjEdgeList;
- typedef typename AdjEdgeList::iterator AdjEdgeListItr;
-
- AdjEdgeList adjEdges;
- adjEdges.reserve(nodeEntry.getDegree());
- std::copy(nodeEntry.adjEdgesBegin(), nodeEntry.adjEdgesEnd(),
- std::back_inserter(adjEdges));
-
- // Iterate over the copied out edges and remove them from the graph.
- for (AdjEdgeListItr itr = adjEdges.begin(), end = adjEdges.end();
- itr != end; ++itr) {
- removeEdge(*itr);
- }
-
- // Erase the node from the nodelist.
- nodeList.erase(nodeItr);
- --nodeListSize;
- }
-
- NodeIterator nodesBegin() { return nodeList.begin(); }
- ConstNodeIterator nodesBegin() const { return nodeList.begin(); }
- NodeIterator nodesEnd() { return nodeList.end(); }
- ConstNodeIterator nodesEnd() const { return nodeList.end(); }
-
- AdjEdgeIterator adjEdgesBegin(const NodeIterator &nodeItr) {
- return getNodeEntry(nodeItr).adjEdgesBegin();
- }
-
- ConstAdjEdgeIterator adjEdgesBegin(const ConstNodeIterator &nodeItr) const {
- return getNodeEntry(nodeItr).adjEdgesBegin();
- }
-
- AdjEdgeIterator adjEdgesEnd(const NodeIterator &nodeItr) {
- return getNodeEntry(nodeItr).adjEdgesEnd();
- }
-
- ConstAdjEdgeIterator adjEdgesEnd(const ConstNodeIterator &nodeItr) const {
- getNodeEntry(nodeItr).adjEdgesEnd();
- }
-
- EdgeIterator findEdge(const NodeIterator &node1Itr,
- const NodeIterator &node2Itr) {
-
- for (AdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
- adjEdgeEnd = adjEdgesEnd(node1Itr);
- adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
- if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
- (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
- return *adjEdgeItr;
- }
- }
-
- return edgeList.end();
- }
-
- ConstEdgeIterator findEdge(const ConstNodeIterator &node1Itr,
- const ConstNodeIterator &node2Itr) const {
-
- for (ConstAdjEdgeIterator adjEdgeItr = adjEdgesBegin(node1Itr),
- adjEdgeEnd = adjEdgesEnd(node1Itr);
- adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
- if ((getEdgeNode1Itr(*adjEdgeItr) == node2Itr) ||
- (getEdgeNode2Itr(*adjEdgeItr) == node2Itr)) {
- return *adjEdgeItr;
- }
- }
-
- return edgeList.end();
- }
-
- Matrix& getEdgeCosts(const EdgeIterator &edgeItr) {
- return getEdgeEntry(edgeItr).getCosts();
- }
-
- const Matrix& getEdgeCosts(const ConstEdgeIterator &edgeItr) const {
- return getEdgeEntry(edgeItr).getCosts();
- }
-
- NodeIterator getEdgeNode1Itr(const EdgeIterator &edgeItr) {
- return getEdgeEntry(edgeItr).getNode1Itr();
- }
-
- ConstNodeIterator getEdgeNode1Itr(const ConstEdgeIterator &edgeItr) const {
- return getEdgeEntry(edgeItr).getNode1Itr();
- }
-
- NodeIterator getEdgeNode2Itr(const EdgeIterator &edgeItr) {
- return getEdgeEntry(edgeItr).getNode2Itr();
- }
-
- ConstNodeIterator getEdgeNode2Itr(const ConstEdgeIterator &edgeItr) const {
- return getEdgeEntry(edgeItr).getNode2Itr();
- }
-
- NodeIterator getEdgeOtherNode(const EdgeIterator &edgeItr,
- const NodeIterator &nodeItr) {
-
- EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
- if (nodeItr == edgeEntry.getNode1Itr()) {
- return edgeEntry.getNode2Itr();
- }
- //else
- return edgeEntry.getNode1Itr();
- }
-
- ConstNodeIterator getEdgeOtherNode(const ConstEdgeIterator &edgeItr,
- const ConstNodeIterator &nodeItr) const {
-
- const EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
- if (nodeItr == edgeEntry.getNode1Itr()) {
- return edgeEntry.getNode2Itr();
- }
- //else
- return edgeEntry.getNode1Itr();
- }
-
- void removeEdge(const EdgeIterator &edgeItr) {
- assert(iteratorInRange(edgeItr, edgeList.begin(), edgeList.end()) &&
- "Iterator does not belong to this graph!");
-
- --edgeListSize;
-
- // Get the edge entry.
- EdgeEntry &edgeEntry = getEdgeEntry(edgeItr);
-
- // Get the nodes entry.
- NodeEntry &node1Entry(getNodeEntry(edgeEntry.getNode1Itr())),
- &node2Entry(getNodeEntry(edgeEntry.getNode2Itr()));
-
- // Disconnect the edge from the nodes.
- node1Entry.removeAdjEdge(edgeEntry.getNode1ThisEdgeItr());
- node2Entry.removeAdjEdge(edgeEntry.getNode2ThisEdgeItr());
-
- // Remove the edge from the graph.
- edgeList.erase(edgeItr);
- }
-
- EdgeIterator edgesBegin() { return edgeList.begin(); }
- ConstEdgeIterator edgesBegin() const { return edgeList.begin(); }
- EdgeIterator edgesEnd() { return edgeList.end(); }
- ConstEdgeIterator edgesEnd() const { return edgeList.end(); }
-
- void clear() {
- nodeList.clear();
- nodeListSize = 0;
- edgeList.clear();
- edgeListSize = 0;
- idToNodeMap.clear();
- }
-
- template <typename OStream>
- void printDot(OStream &os) const {
-
- assert(areNodeIDsValid() &&
- "Cannot print a .dot of a graph unless IDs have been assigned.");
-
- os << "graph {\n";
-
- for (ConstNodeIterator nodeItr = nodesBegin(), nodeEnd = nodesEnd();
- nodeItr != nodeEnd; ++nodeItr) {
-
- os << " node" << getNodeID(nodeItr) << " [ label=\""
- << getNodeID(nodeItr) << ": " << getNodeCosts(nodeItr) << "\" ]\n";
- }
-
- os << " edge [ len=" << getNumNodes() << " ]\n";
-
- for (ConstEdgeIterator edgeItr = edgesBegin(), edgeEnd = edgesEnd();
- edgeItr != edgeEnd; ++edgeItr) {
-
- os << " node" << getNodeID(getEdgeNode1Itr(edgeItr))
- << " -- node" << getNodeID(getEdgeNode2Itr(edgeItr))
- << " [ label=\"";
-
- const Matrix &edgeCosts = getEdgeCosts(edgeItr);
-
- for (unsigned i = 0; i < edgeCosts.getRows(); ++i) {
- os << edgeCosts.getRowAsVector(i) << "\\n";
- }
-
- os << "\" ]\n";
- }
-
- os << "}\n";
- }
-
- template <typename OStream>
- void printDot(OStream &os) {
- if (!areNodeIDsValid()) {
- assignNodeIDs();
- }
-
- const_cast<const ThisGraphT*>(this)->printDot(os);
- }
-
- template <typename OStream>
- void dumpTo(OStream &os) const {
- typedef ConstNodeIterator ConstNodeID;
-
- assert(areNodeIDsValid() &&
- "Cannot dump a graph unless IDs have been assigned.");
-
- for (ConstNodeIterator nItr = nodesBegin(), nEnd = nodesEnd();
- nItr != nEnd; ++nItr) {
- os << getNodeID(nItr) << "\n";
- }
-
- unsigned edgeNumber = 1;
- for (ConstEdgeIterator eItr = edgesBegin(), eEnd = edgesEnd();
- eItr != eEnd; ++eItr) {
-
- os << edgeNumber++ << ": { "
- << getNodeID(getEdgeNode1Itr(eItr)) << ", "
- << getNodeID(getEdgeNode2Itr(eItr)) << " }\n";
- }
-
- }
-
- template <typename OStream>
- void dumpTo(OStream &os) {
- if (!areNodeIDsValid()) {
- assignNodeIDs();
- }
-
- const_cast<const ThisGraphT*>(this)->dumpTo(os);
- }
-
-};
-
-/// \brief Provides a base from which to derive nodes for GraphBase.
-template <typename NodeImpl, typename EdgeImpl>
-class NodeBase {
-private:
-
- typedef GraphBase<NodeImpl, EdgeImpl> GraphBaseT;
- typedef NodeBaseTraits<GraphBaseT> ThisNodeBaseTraits;
-
-public:
- typedef typename GraphBaseT::EdgeIterator EdgeIterator;
-
-private:
- typedef typename ThisNodeBaseTraits::AdjEdgeList AdjEdgeList;
-
- unsigned degree, id;
- Vector costs;
- AdjEdgeList adjEdges;
-
- void operator=(const NodeBase& other) {
- assert(false && "Can't assign NodeEntrys.");
- }
-
-public:
-
- typedef typename ThisNodeBaseTraits::AdjEdgeIterator AdjEdgeIterator;
- typedef typename ThisNodeBaseTraits::ConstAdjEdgeIterator
- ConstAdjEdgeIterator;
-
- NodeBase(const Vector &costs) : degree(0), costs(costs) {
- assert((costs.getLength() > 0) && "Can't have zero-length cost vector.");
- }
-
- Vector& getCosts() { return costs; }
- const Vector& getCosts() const { return costs; }
-
- unsigned getDegree() const { return degree; }
-
- void setID(unsigned id) { this->id = id; }
- unsigned getID() const { return id; }
-
- AdjEdgeIterator addAdjEdge(const EdgeIterator &edgeItr) {
- ++degree;
- return adjEdges.insert(adjEdges.end(), edgeItr);
- }
-
- void removeAdjEdge(const AdjEdgeIterator &adjEdgeItr) {
- --degree;
- adjEdges.erase(adjEdgeItr);
- }
-
- AdjEdgeIterator adjEdgesBegin() { return adjEdges.begin(); }
- ConstAdjEdgeIterator adjEdgesBegin() const { return adjEdges.begin(); }
- AdjEdgeIterator adjEdgesEnd() { return adjEdges.end(); }
- ConstAdjEdgeIterator adjEdgesEnd() const { return adjEdges.end(); }
-
-};
-
-template <typename NodeImpl, typename EdgeImpl>
-class EdgeBase {
-public:
- typedef typename GraphBase<NodeImpl, EdgeImpl>::NodeIterator NodeIterator;
- typedef typename GraphBase<NodeImpl, EdgeImpl>::EdgeIterator EdgeIterator;
-
- typedef typename NodeImpl::AdjEdgeIterator NodeAdjEdgeIterator;
-
-private:
-
- NodeIterator node1Itr, node2Itr;
- NodeAdjEdgeIterator node1ThisEdgeItr, node2ThisEdgeItr;
- Matrix costs;
-
- void operator=(const EdgeBase &other) {
- assert(false && "Can't assign EdgeEntrys.");
- }
-
-public:
-
- EdgeBase(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
- const Matrix &costs) :
- node1Itr(node1Itr), node2Itr(node2Itr), costs(costs) {
-
- assert((costs.getRows() > 0) && (costs.getCols() > 0) &&
- "Can't have zero-dimensioned cost matrices");
- }
-
- Matrix& getCosts() { return costs; }
- const Matrix& getCosts() const { return costs; }
-
- const NodeIterator& getNode1Itr() const { return node1Itr; }
- const NodeIterator& getNode2Itr() const { return node2Itr; }
-
- void setNode1ThisEdgeItr(const NodeAdjEdgeIterator &node1ThisEdgeItr) {
- this->node1ThisEdgeItr = node1ThisEdgeItr;
- }
-
- const NodeAdjEdgeIterator& getNode1ThisEdgeItr() const {
- return node1ThisEdgeItr;
- }
-
- void setNode2ThisEdgeItr(const NodeAdjEdgeIterator &node2ThisEdgeItr) {
- this->node2ThisEdgeItr = node2ThisEdgeItr;
- }
-
- const NodeAdjEdgeIterator& getNode2ThisEdgeItr() const {
- return node2ThisEdgeItr;
- }
-
-};
-
-
-}
-
-#endif // LLVM_CODEGEN_PBQP_GRAPHBASE_HPP
--- /dev/null
+//===-- HeuristcBase.h --- Heuristic base class for PBQP --------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_PBQP_HEURISTICBASE_H
+#define LLVM_CODEGEN_PBQP_HEURISTICBASE_H
+
+#include "HeuristicSolver.h"
+
+namespace PBQP {
+
+ /// \brief Abstract base class for heuristic implementations.
+ ///
+ /// This class provides a handy base for heuristic implementations with common
+ /// solver behaviour implemented for a number of methods.
+ ///
+ /// To implement your own heuristic using this class as a base you'll have to
+ /// implement, as a minimum, the following methods:
+ /// <ul>
+ /// <li> void addToHeuristicList(Graph::NodeItr) : Add a node to the
+ /// heuristic reduction list.
+ /// <li> void heuristicReduce() : Perform a single heuristic reduction.
+ /// <li> void preUpdateEdgeCosts(Graph::EdgeItr) : Handle the (imminent)
+ /// change to the cost matrix on the given edge (by R2).
+ /// <li> void postUpdateEdgeCostts(Graph::EdgeItr) : Handle the new
+ /// costs on the given edge.
+ /// <li> void handleAddEdge(Graph::EdgeItr) : Handle the addition of a new
+ /// edge into the PBQP graph (by R2).
+ /// <li> void handleRemoveEdge(Graph::EdgeItr, Graph::NodeItr) : Handle the
+ /// disconnection of the given edge from the given node.
+ /// <li> A constructor for your derived class : to pass back a reference to
+ /// the solver which is using this heuristic.
+ /// </ul>
+ ///
+ /// These methods are implemented in this class for documentation purposes,
+ /// but will assert if called.
+ ///
+ /// Note that this class uses the curiously recursive template idiom to
+ /// forward calls to the derived class. These methods need not be made
+ /// virtual, and indeed probably shouldn't for performance reasons.
+ ///
+ /// You'll also need to provide NodeData and EdgeData structs in your class.
+ /// These can be used to attach data relevant to your heuristic to each
+ /// node/edge in the PBQP graph.
+
+ template <typename HImpl>
+ class HeuristicBase {
+ private:
+
+ typedef std::list<Graph::NodeItr> OptimalList;
+
+ HeuristicSolverImpl<HImpl> &s;
+ Graph &g;
+ OptimalList optimalList;
+
+ // Return a reference to the derived heuristic.
+ HImpl& impl() { return static_cast<HImpl&>(*this); }
+
+ // Add the given node to the optimal reductions list. Keep an iterator to
+ // its location for fast removal.
+ void addToOptimalReductionList(Graph::NodeItr nItr) {
+ optimalList.insert(optimalList.end(), nItr);
+ }
+
+ public:
+
+ /// \brief Construct an instance with a reference to the given solver.
+ /// @param solver The solver which is using this heuristic instance.
+ HeuristicBase(HeuristicSolverImpl<HImpl> &solver)
+ : s(solver), g(s.getGraph()) { }
+
+ /// \brief Get the solver which is using this heuristic instance.
+ /// @return The solver which is using this heuristic instance.
+ ///
+ /// You can use this method to get access to the solver in your derived
+ /// heuristic implementation.
+ HeuristicSolverImpl<HImpl>& getSolver() { return s; }
+
+ /// \brief Get the graph representing the problem to be solved.
+ /// @return The graph representing the problem to be solved.
+ Graph& getGraph() { return g; }
+
+ /// \brief Tell the solver to simplify the graph before the reduction phase.
+ /// @return Whether or not the solver should run a simplification phase
+ /// prior to the main setup and reduction.
+ ///
+ /// HeuristicBase returns true from this method as it's a sensible default,
+ /// however you can over-ride it in your derived class if you want different
+ /// behaviour.
+ bool solverRunSimplify() const { return true; }
+
+ /// \brief Decide whether a node should be optimally or heuristically
+ /// reduced.
+ /// @return Whether or not the given node should be listed for optimal
+ /// reduction (via R0, R1 or R2).
+ ///
+ /// HeuristicBase returns true for any node with degree less than 3. This is
+ /// sane and sensible for many situations, but not all. You can over-ride
+ /// this method in your derived class if you want a different selection
+ /// criteria. Note however that your criteria for selecting optimal nodes
+ /// should be <i>at least</i> as strong as this. I.e. Nodes of degree 3 or
+ /// higher should not be selected under any circumstances.
+ bool shouldOptimallyReduce(Graph::NodeItr nItr) {
+ if (g.getNodeDegree(nItr) < 3)
+ return true;
+ // else
+ return false;
+ }
+
+ /// \brief Add the given node to the list of nodes to be optimally reduced.
+ /// @return nItr Node iterator to be added.
+ ///
+ /// You probably don't want to over-ride this, except perhaps to record
+ /// statistics before calling this implementation. HeuristicBase relies on
+ /// its behaviour.
+ void addToOptimalReduceList(Graph::NodeItr nItr) {
+ optimalList.push_back(nItr);
+ }
+
+ /// \brief Initialise the heuristic.
+ ///
+ /// HeuristicBase iterates over all nodes in the problem and adds them to
+ /// the appropriate list using addToOptimalReduceList or
+ /// addToHeuristicReduceList based on the result of shouldOptimallyReduce.
+ ///
+ /// This behaviour should be fine for most situations.
+ void setup() {
+ for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
+ nItr != nEnd; ++nItr) {
+ if (impl().shouldOptimallyReduce(nItr)) {
+ addToOptimalReduceList(nItr);
+ } else {
+ impl().addToHeuristicReduceList(nItr);
+ }
+ }
+ }
+
+ /// \brief Optimally reduce one of the nodes in the optimal reduce list.
+ /// @return True if a reduction takes place, false if the optimal reduce
+ /// list is empty.
+ ///
+ /// Selects a node from the optimal reduce list and removes it, applying
+ /// R0, R1 or R2 as appropriate based on the selected node's degree.
+ bool optimalReduce() {
+ if (optimalList.empty())
+ return false;
+
+ Graph::NodeItr nItr = optimalList.front();
+ optimalList.pop_front();
+
+ switch (s.getSolverDegree(nItr)) {
+ case 0: s.applyR0(nItr); break;
+ case 1: s.applyR1(nItr); break;
+ case 2: s.applyR2(nItr); break;
+ default: assert(false &&
+ "Optimal reductions of degree > 2 nodes is invalid.");
+ }
+
+ return true;
+ }
+
+ /// \brief Perform the PBQP reduction process.
+ ///
+ /// Reduces the problem to the empty graph by repeated application of the
+ /// reduction rules R0, R1, R2 and RN.
+ /// R0, R1 or R2 are always applied if possible before RN is used.
+ void reduce() {
+ bool finished = false;
+
+ while (!finished) {
+ if (!optimalReduce())
+ if (!impl().heuristicReduce())
+ finished = true;
+ }
+ }
+
+ /// \brief Add a node to the heuristic reduce list.
+ /// @param nItr Node iterator to add to the heuristic reduce list.
+ void addToHeuristicList(Graph::NodeItr nItr) {
+ assert(false && "Must be implemented in derived class.");
+ }
+
+ /// \brief Heuristically reduce one of the nodes in the heuristic
+ /// reduce list.
+ /// @return True if a reduction takes place, false if the heuristic reduce
+ /// list is empty.
+ void heuristicReduce() {
+ assert(false && "Must be implemented in derived class.");
+ }
+
+ /// \brief Prepare a change in the costs on the given edge.
+ /// @param eItr Edge iterator.
+ void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
+ assert(false && "Must be implemented in derived class.");
+ }
+
+ /// \brief Handle the change in the costs on the given edge.
+ /// @param eItr Edge iterator.
+ void postUpdateEdgeCostts(Graph::EdgeItr eItr) {
+ assert(false && "Must be implemented in derived class.");
+ }
+
+ /// \brief Handle the addition of a new edge into the PBQP graph.
+ /// @param eItr Edge iterator for the added edge.
+ void handleAddEdge(Graph::EdgeItr eItr) {
+ assert(false && "Must be implemented in derived class.");
+ }
+
+ /// \brief Handle disconnection of an edge from a node.
+ /// @param eItr Edge iterator for edge being disconnected.
+ /// @param nItr Node iterator for the node being disconnected from.
+ ///
+ /// Edges are frequently removed due to the removal of a node. This
+ /// method allows for the effect to be computed only for the remaining
+ /// node in the graph.
+ void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
+ assert(false && "Must be implemented in derived class.");
+ }
+
+ /// \brief Clean up any structures used by HeuristicBase.
+ ///
+ /// At present this just performs a sanity check: that the optimal reduce
+ /// list is empty now that reduction has completed.
+ ///
+ /// If your derived class has more complex structures which need tearing
+ /// down you should over-ride this method but include a call back to this
+ /// implementation.
+ void cleanup() {
+ assert(optimalList.empty() && "Nodes left over in optimal reduce list?");
+ }
+
+ };
+
+}
+
+
+#endif // LLVM_CODEGEN_PBQP_HEURISTICBASE_H
-//===-- HeuristicSolver.h - Heuristic PBQP Solver ---------------*- C++ -*-===//
+//===-- HeuristicSolver.h - Heuristic PBQP Solver --------------*- C++ -*-===//
//
// The LLVM Compiler Infrastructure
//
#ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
#define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H
-#include "Solver.h"
-#include "AnnotatedGraph.h"
+#include "Graph.h"
+#include "Solution.h"
#include "llvm/Support/raw_ostream.h"
+#include <vector>
#include <limits>
namespace PBQP {
-/// \brief Important types for the HeuristicSolverImpl.
-///
-/// Declared seperately to allow access to heuristic classes before the solver
-/// is fully constructed.
-template <typename HeuristicNodeData, typename HeuristicEdgeData>
-class HSITypes {
-public:
-
- class NodeData;
- class EdgeData;
-
- typedef AnnotatedGraph<NodeData, EdgeData> SolverGraph;
- typedef typename SolverGraph::NodeIterator GraphNodeIterator;
- typedef typename SolverGraph::EdgeIterator GraphEdgeIterator;
- typedef typename SolverGraph::AdjEdgeIterator GraphAdjEdgeIterator;
-
- typedef std::list<GraphNodeIterator> NodeList;
- typedef typename NodeList::iterator NodeListIterator;
-
- typedef std::vector<GraphNodeIterator> NodeStack;
- typedef typename NodeStack::iterator NodeStackIterator;
-
- class NodeData {
- friend class EdgeData;
-
+ /// \brief Heuristic PBQP solver implementation.
+ ///
+ /// This class should usually be created (and destroyed) indirectly via a call
+ /// to HeuristicSolver<HImpl>::solve(Graph&).
+ /// See the comments for HeuristicSolver.
+ ///
+ /// HeuristicSolverImpl provides the R0, R1 and R2 reduction rules,
+ /// backpropagation phase, and maintains the internal copy of the graph on
+ /// which the reduction is carried out (the original being kept to facilitate
+ /// backpropagation).
+ template <typename HImpl>
+ class HeuristicSolverImpl {
private:
- typedef std::list<GraphEdgeIterator> LinksList;
+ typedef typename HImpl::NodeData HeuristicNodeData;
+ typedef typename HImpl::EdgeData HeuristicEdgeData;
- unsigned numLinks;
- LinksList links, solvedLinks;
- NodeListIterator bucketItr;
- HeuristicNodeData heuristicData;
+ typedef std::list<Graph::EdgeItr> SolverEdges;
public:
-
- typedef typename LinksList::iterator AdjLinkIterator;
+
+ /// \brief Iterator type for edges in the solver graph.
+ typedef SolverEdges::iterator SolverEdgeItr;
private:
- AdjLinkIterator addLink(const GraphEdgeIterator &edgeItr) {
- ++numLinks;
- return links.insert(links.end(), edgeItr);
- }
+ class NodeData {
+ public:
+ NodeData() : solverDegree(0) {}
- void delLink(const AdjLinkIterator &adjLinkItr) {
- --numLinks;
- links.erase(adjLinkItr);
- }
+ HeuristicNodeData& getHeuristicData() { return hData; }
- public:
-
- NodeData() : numLinks(0) {}
-
- unsigned getLinkDegree() const { return numLinks; }
-
- HeuristicNodeData& getHeuristicData() { return heuristicData; }
- const HeuristicNodeData& getHeuristicData() const {
- return heuristicData;
- }
-
- void setBucketItr(const NodeListIterator &bucketItr) {
- this->bucketItr = bucketItr;
- }
+ SolverEdgeItr addSolverEdge(Graph::EdgeItr eItr) {
+ ++solverDegree;
+ return solverEdges.insert(solverEdges.end(), eItr);
+ }
- const NodeListIterator& getBucketItr() const {
- return bucketItr;
- }
+ void removeSolverEdge(SolverEdgeItr seItr) {
+ --solverDegree;
+ solverEdges.erase(seItr);
+ }
- AdjLinkIterator adjLinksBegin() {
- return links.begin();
- }
+ SolverEdgeItr solverEdgesBegin() { return solverEdges.begin(); }
+ SolverEdgeItr solverEdgesEnd() { return solverEdges.end(); }
+ unsigned getSolverDegree() const { return solverDegree; }
+ void clearSolverEdges() {
+ solverDegree = 0;
+ solverEdges.clear();
+ }
+
+ private:
+ HeuristicNodeData hData;
+ unsigned solverDegree;
+ SolverEdges solverEdges;
+ };
+
+ class EdgeData {
+ public:
+ HeuristicEdgeData& getHeuristicData() { return hData; }
+
+ void setN1SolverEdgeItr(SolverEdgeItr n1SolverEdgeItr) {
+ this->n1SolverEdgeItr = n1SolverEdgeItr;
+ }
- AdjLinkIterator adjLinksEnd() {
- return links.end();
- }
+ SolverEdgeItr getN1SolverEdgeItr() { return n1SolverEdgeItr; }
- void addSolvedLink(const GraphEdgeIterator &solvedLinkItr) {
- solvedLinks.push_back(solvedLinkItr);
- }
+ void setN2SolverEdgeItr(SolverEdgeItr n2SolverEdgeItr){
+ this->n2SolverEdgeItr = n2SolverEdgeItr;
+ }
- AdjLinkIterator solvedLinksBegin() {
- return solvedLinks.begin();
- }
+ SolverEdgeItr getN2SolverEdgeItr() { return n2SolverEdgeItr; }
- AdjLinkIterator solvedLinksEnd() {
- return solvedLinks.end();
- }
+ private:
- };
+ HeuristicEdgeData hData;
+ SolverEdgeItr n1SolverEdgeItr, n2SolverEdgeItr;
+ };
- class EdgeData {
- private:
+ Graph &g;
+ HImpl h;
+ Solution s;
+ std::vector<Graph::NodeItr> stack;
- SolverGraph &g;
- GraphNodeIterator node1Itr, node2Itr;
- HeuristicEdgeData heuristicData;
- typename NodeData::AdjLinkIterator node1ThisEdgeItr, node2ThisEdgeItr;
+ std::vector<NodeData> nodeData;
+ std::vector<EdgeData> edgeData;
public:
- EdgeData(SolverGraph &g) : g(g) {}
-
- HeuristicEdgeData& getHeuristicData() { return heuristicData; }
- const HeuristicEdgeData& getHeuristicData() const {
- return heuristicData;
- }
-
- void setup(const GraphEdgeIterator &thisEdgeItr) {
- node1Itr = g.getEdgeNode1Itr(thisEdgeItr);
- node2Itr = g.getEdgeNode2Itr(thisEdgeItr);
-
- node1ThisEdgeItr = g.getNodeData(node1Itr).addLink(thisEdgeItr);
- node2ThisEdgeItr = g.getNodeData(node2Itr).addLink(thisEdgeItr);
- }
-
- void unlink() {
- g.getNodeData(node1Itr).delLink(node1ThisEdgeItr);
- g.getNodeData(node2Itr).delLink(node2ThisEdgeItr);
- }
-
- };
-
-};
-
-template <typename Heuristic>
-class HeuristicSolverImpl {
-public:
- // Typedefs to make life easier:
- typedef HSITypes<typename Heuristic::NodeData,
- typename Heuristic::EdgeData> HSIT;
- typedef typename HSIT::SolverGraph SolverGraph;
- typedef typename HSIT::NodeData NodeData;
- typedef typename HSIT::EdgeData EdgeData;
- typedef typename HSIT::GraphNodeIterator GraphNodeIterator;
- typedef typename HSIT::GraphEdgeIterator GraphEdgeIterator;
- typedef typename HSIT::GraphAdjEdgeIterator GraphAdjEdgeIterator;
-
- typedef typename HSIT::NodeList NodeList;
- typedef typename HSIT::NodeListIterator NodeListIterator;
-
- typedef std::vector<GraphNodeIterator> NodeStack;
- typedef typename NodeStack::iterator NodeStackIterator;
-
- /// \brief Constructor, which performs all the actual solver work.
- HeuristicSolverImpl(const SimpleGraph &orig) :
- solution(orig.getNumNodes(), true)
- {
- copyGraph(orig);
- simplify();
- setup();
- computeSolution();
- computeSolutionCost(orig);
- }
-
- /// \brief Returns the graph for this solver.
- SolverGraph& getGraph() { return g; }
-
- /// \brief Return the solution found by this solver.
- const Solution& getSolution() const { return solution; }
-
-private:
-
- /// \brief Add the given node to the appropriate bucket for its link
- /// degree.
- void addToBucket(const GraphNodeIterator &nodeItr) {
- NodeData &nodeData = g.getNodeData(nodeItr);
-
- switch (nodeData.getLinkDegree()) {
- case 0: nodeData.setBucketItr(
- r0Bucket.insert(r0Bucket.end(), nodeItr));
- break;
- case 1: nodeData.setBucketItr(
- r1Bucket.insert(r1Bucket.end(), nodeItr));
- break;
- case 2: nodeData.setBucketItr(
- r2Bucket.insert(r2Bucket.end(), nodeItr));
- break;
- default: heuristic.addToRNBucket(nodeItr);
- break;
- }
- }
-
- /// \brief Remove the given node from the appropriate bucket for its link
- /// degree.
- void removeFromBucket(const GraphNodeIterator &nodeItr) {
- NodeData &nodeData = g.getNodeData(nodeItr);
-
- switch (nodeData.getLinkDegree()) {
- case 0: r0Bucket.erase(nodeData.getBucketItr()); break;
- case 1: r1Bucket.erase(nodeData.getBucketItr()); break;
- case 2: r2Bucket.erase(nodeData.getBucketItr()); break;
- default: heuristic.removeFromRNBucket(nodeItr); break;
- }
- }
-
-public:
-
- /// \brief Add a link.
- void addLink(const GraphEdgeIterator &edgeItr) {
- g.getEdgeData(edgeItr).setup(edgeItr);
-
- if ((g.getNodeData(g.getEdgeNode1Itr(edgeItr)).getLinkDegree() > 2) ||
- (g.getNodeData(g.getEdgeNode2Itr(edgeItr)).getLinkDegree() > 2)) {
- heuristic.handleAddLink(edgeItr);
- }
- }
-
- /// \brief Remove link, update info for node.
- ///
- /// Only updates information for the given node, since usually the other
- /// is about to be removed.
- void removeLink(const GraphEdgeIterator &edgeItr,
- const GraphNodeIterator &nodeItr) {
-
- if (g.getNodeData(nodeItr).getLinkDegree() > 2) {
- heuristic.handleRemoveLink(edgeItr, nodeItr);
- }
- g.getEdgeData(edgeItr).unlink();
- }
-
- /// \brief Remove link, update info for both nodes. Useful for R2 only.
- void removeLinkR2(const GraphEdgeIterator &edgeItr) {
- GraphNodeIterator node1Itr = g.getEdgeNode1Itr(edgeItr);
-
- if (g.getNodeData(node1Itr).getLinkDegree() > 2) {
- heuristic.handleRemoveLink(edgeItr, node1Itr);
+ /// \brief Construct a heuristic solver implementation to solve the given
+ /// graph.
+ /// @param g The graph representing the problem instance to be solved.
+ HeuristicSolverImpl(Graph &g) : g(g), h(*this) {}
+
+ /// \brief Get the graph being solved by this solver.
+ /// @return The graph representing the problem instance being solved by this
+ /// solver.
+ Graph& getGraph() { return g; }
+
+ /// \brief Get the heuristic data attached to the given node.
+ /// @param nItr Node iterator.
+ /// @return The heuristic data attached to the given node.
+ HeuristicNodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
+ return getSolverNodeData(nItr).getHeuristicData();
+ }
+
+ /// \brief Get the heuristic data attached to the given edge.
+ /// @param eItr Edge iterator.
+ /// @return The heuristic data attached to the given node.
+ HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
+ return getSolverEdgeData(eItr).getHeuristicData();
+ }
+
+ /// \brief Begin iterator for the set of edges adjacent to the given node in
+ /// the solver graph.
+ /// @param nItr Node iterator.
+ /// @return Begin iterator for the set of edges adjacent to the given node
+ /// in the solver graph.
+ SolverEdgeItr solverEdgesBegin(Graph::NodeItr nItr) {
+ return getSolverNodeData(nItr).solverEdgesBegin();
+ }
+
+ /// \brief End iterator for the set of edges adjacent to the given node in
+ /// the solver graph.
+ /// @param nItr Node iterator.
+ /// @return End iterator for the set of edges adjacent to the given node in
+ /// the solver graph.
+ SolverEdgeItr solverEdgesEnd(Graph::NodeItr nItr) {
+ return getSolverNodeData(nItr).solverEdgesEnd();
+ }
+
+ /// \brief Remove a node from the solver graph.
+ /// @param eItr Edge iterator for edge to be removed.
+ ///
+ /// Does <i>not</i> notify the heuristic of the removal. That should be
+ /// done manually if necessary.
+ void removeSolverEdge(Graph::EdgeItr eItr) {
+ EdgeData &eData = getSolverEdgeData(eItr);
+ NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
+ &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
+
+ n1Data.removeSolverEdge(eData.getN1SolverEdgeItr());
+ n2Data.removeSolverEdge(eData.getN2SolverEdgeItr());
+ }
+
+ /// \brief Compute a solution to the PBQP problem instance with which this
+ /// heuristic solver was constructed.
+ /// @return A solution to the PBQP problem.
+ ///
+ /// Performs the full PBQP heuristic solver algorithm, including setup,
+ /// calls to the heuristic (which will call back to the reduction rules in
+ /// this class), and cleanup.
+ Solution computeSolution() {
+ setup();
+ h.setup();
+ h.reduce();
+ backpropagate();
+ h.cleanup();
+ cleanup();
+ return s;
+ }
+
+ /// \brief Add to the end of the stack.
+ /// @param nItr Node iterator to add to the reduction stack.
+ void pushToStack(Graph::NodeItr nItr) {
+ getSolverNodeData(nItr).clearSolverEdges();
+ stack.push_back(nItr);
+ }
+
+ /// \brief Returns the solver degree of the given node.
+ /// @param nItr Node iterator for which degree is requested.
+ /// @return Node degree in the <i>solver</i> graph (not the original graph).
+ unsigned getSolverDegree(Graph::NodeItr nItr) {
+ return getSolverNodeData(nItr).getSolverDegree();
+ }
+
+ /// \brief Set the solution of the given node.
+ /// @param nItr Node iterator to set solution for.
+ /// @param selection Selection for node.
+ void setSolution(const Graph::NodeItr &nItr, unsigned selection) {
+ s.setSelection(nItr, selection);
+
+ for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
+ aeEnd = g.adjEdgesEnd(nItr);
+ aeItr != aeEnd; ++aeItr) {
+ Graph::EdgeItr eItr(*aeItr);
+ Graph::NodeItr anItr(g.getEdgeOtherNode(eItr, nItr));
+ getSolverNodeData(anItr).addSolverEdge(eItr);
+ }
}
- removeLink(edgeItr, g.getEdgeNode2Itr(edgeItr));
- }
-
- /// \brief Removes all links connected to the given node.
- void unlinkNode(const GraphNodeIterator &nodeItr) {
- NodeData &nodeData = g.getNodeData(nodeItr);
-
- typedef std::vector<GraphEdgeIterator> TempEdgeList;
-
- TempEdgeList edgesToUnlink;
- edgesToUnlink.reserve(nodeData.getLinkDegree());
- // Copy adj edges into a temp vector. We want to destroy them during
- // the unlink, and we can't do that while we're iterating over them.
- std::copy(nodeData.adjLinksBegin(), nodeData.adjLinksEnd(),
- std::back_inserter(edgesToUnlink));
+ /// \brief Apply rule R0.
+ /// @param nItr Node iterator for node to apply R0 to.
+ ///
+ /// Node will be automatically pushed to the solver stack.
+ void applyR0(Graph::NodeItr nItr) {
+ assert(getSolverNodeData(nItr).getSolverDegree() == 0 &&
+ "R0 applied to node with degree != 0.");
- for (typename TempEdgeList::iterator
- edgeItr = edgesToUnlink.begin(), edgeEnd = edgesToUnlink.end();
- edgeItr != edgeEnd; ++edgeItr) {
-
- GraphNodeIterator otherNode = g.getEdgeOtherNode(*edgeItr, nodeItr);
-
- removeFromBucket(otherNode);
- removeLink(*edgeItr, otherNode);
- addToBucket(otherNode);
- }
- }
-
- /// \brief Push the given node onto the stack to be solved with
- /// backpropagation.
- void pushStack(const GraphNodeIterator &nodeItr) {
- stack.push_back(nodeItr);
- }
-
- /// \brief Set the solution of the given node.
- void setSolution(const GraphNodeIterator &nodeItr, unsigned solIndex) {
- solution.setSelection(g.getNodeID(nodeItr), solIndex);
-
- for (GraphAdjEdgeIterator adjEdgeItr = g.adjEdgesBegin(nodeItr),
- adjEdgeEnd = g.adjEdgesEnd(nodeItr);
- adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
- GraphEdgeIterator edgeItr(*adjEdgeItr);
- GraphNodeIterator adjNodeItr(g.getEdgeOtherNode(edgeItr, nodeItr));
- g.getNodeData(adjNodeItr).addSolvedLink(edgeItr);
+ // Nothing to do. Just push the node onto the reduction stack.
+ pushToStack(nItr);
}
- }
-
-private:
-
- SolverGraph g;
- Heuristic heuristic;
- Solution solution;
- NodeList r0Bucket,
- r1Bucket,
- r2Bucket;
+ /// \brief Apply rule R1.
+ /// @param nItr Node iterator for node to apply R1 to.
+ ///
+ /// Node will be automatically pushed to the solver stack.
+ void applyR1(Graph::NodeItr xnItr) {
+ NodeData &nd = getSolverNodeData(xnItr);
+ assert(nd.getSolverDegree() == 1 &&
+ "R1 applied to node with degree != 1.");
- NodeStack stack;
+ Graph::EdgeItr eItr = *nd.solverEdgesBegin();
- // Copy the SimpleGraph into an annotated graph which we can use for reduction.
- void copyGraph(const SimpleGraph &orig) {
-
- assert((g.getNumEdges() == 0) && (g.getNumNodes() == 0) &&
- "Graph should be empty prior to solver setup.");
-
- assert(orig.areNodeIDsValid() &&
- "Cannot copy from a graph with invalid node IDs.");
-
- std::vector<GraphNodeIterator> newNodeItrs;
-
- for (unsigned nodeID = 0; nodeID < orig.getNumNodes(); ++nodeID) {
- newNodeItrs.push_back(
- g.addNode(orig.getNodeCosts(orig.getNodeItr(nodeID)), NodeData()));
+ const Matrix &eCosts = g.getEdgeCosts(eItr);
+ const Vector &xCosts = g.getNodeCosts(xnItr);
+
+ // Duplicate a little to avoid transposing matrices.
+ if (xnItr == g.getEdgeNode1(eItr)) {
+ Graph::NodeItr ynItr = g.getEdgeNode2(eItr);
+ Vector &yCosts = g.getNodeCosts(ynItr);
+ for (unsigned j = 0; j < yCosts.getLength(); ++j) {
+ PBQPNum min = eCosts[0][j] + xCosts[0];
+ for (unsigned i = 1; i < xCosts.getLength(); ++i) {
+ PBQPNum c = eCosts[i][j] + xCosts[i];
+ if (c < min)
+ min = c;
+ }
+ yCosts[j] += min;
+ }
+ h.handleRemoveEdge(eItr, ynItr);
+ } else {
+ Graph::NodeItr ynItr = g.getEdgeNode1(eItr);
+ Vector &yCosts = g.getNodeCosts(ynItr);
+ for (unsigned i = 0; i < yCosts.getLength(); ++i) {
+ PBQPNum min = eCosts[i][0] + xCosts[0];
+ for (unsigned j = 1; j < xCosts.getLength(); ++j) {
+ PBQPNum c = eCosts[i][j] + xCosts[j];
+ if (c < min)
+ min = c;
+ }
+ yCosts[i] += min;
+ }
+ h.handleRemoveEdge(eItr, ynItr);
+ }
+ removeSolverEdge(eItr);
+ assert(nd.getSolverDegree() == 0 &&
+ "Degree 1 with edge removed should be 0.");
+ pushToStack(xnItr);
}
- for (SimpleGraph::ConstEdgeIterator
- origEdgeItr = orig.edgesBegin(), origEdgeEnd = orig.edgesEnd();
- origEdgeItr != origEdgeEnd; ++origEdgeItr) {
+ /// \brief Apply rule R2.
+ /// @param nItr Node iterator for node to apply R2 to.
+ ///
+ /// Node will be automatically pushed to the solver stack.
+ void applyR2(Graph::NodeItr xnItr) {
+ assert(getSolverNodeData(xnItr).getSolverDegree() == 2 &&
+ "R2 applied to node with degree != 2.");
- unsigned id1 = orig.getNodeID(orig.getEdgeNode1Itr(origEdgeItr)),
- id2 = orig.getNodeID(orig.getEdgeNode2Itr(origEdgeItr));
+ NodeData &nd = getSolverNodeData(xnItr);
+ const Vector &xCosts = g.getNodeCosts(xnItr);
- g.addEdge(newNodeItrs[id1], newNodeItrs[id2],
- orig.getEdgeCosts(origEdgeItr), EdgeData(g));
- }
-
- // Assign IDs to the new nodes using the ordering from the old graph,
- // this will lead to nodes in the new graph getting the same ID as the
- // corresponding node in the old graph.
- g.assignNodeIDs(newNodeItrs);
- }
-
- // Simplify the annotated graph by eliminating independent edges and trivial
- // nodes.
- void simplify() {
- disconnectTrivialNodes();
- eliminateIndependentEdges();
- }
+ SolverEdgeItr aeItr = nd.solverEdgesBegin();
+ Graph::EdgeItr yxeItr = *aeItr,
+ zxeItr = *(++aeItr);
- // Eliminate trivial nodes.
- void disconnectTrivialNodes() {
- for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
- nodeItr != nodeEnd; ++nodeItr) {
+ Graph::NodeItr ynItr = g.getEdgeOtherNode(yxeItr, xnItr),
+ znItr = g.getEdgeOtherNode(zxeItr, xnItr);
- if (g.getNodeCosts(nodeItr).getLength() == 1) {
+ bool flipEdge1 = (g.getEdgeNode1(yxeItr) == xnItr),
+ flipEdge2 = (g.getEdgeNode1(zxeItr) == xnItr);
- std::vector<GraphEdgeIterator> edgesToRemove;
+ const Matrix *yxeCosts = flipEdge1 ?
+ new Matrix(g.getEdgeCosts(yxeItr).transpose()) :
+ &g.getEdgeCosts(yxeItr);
- for (GraphAdjEdgeIterator adjEdgeItr = g.adjEdgesBegin(nodeItr),
- adjEdgeEnd = g.adjEdgesEnd(nodeItr);
- adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) {
+ const Matrix *zxeCosts = flipEdge2 ?
+ new Matrix(g.getEdgeCosts(zxeItr).transpose()) :
+ &g.getEdgeCosts(zxeItr);
- GraphEdgeIterator edgeItr = *adjEdgeItr;
+ unsigned xLen = xCosts.getLength(),
+ yLen = yxeCosts->getRows(),
+ zLen = zxeCosts->getRows();
+
+ Matrix delta(yLen, zLen);
- if (g.getEdgeNode1Itr(edgeItr) == nodeItr) {
- GraphNodeIterator otherNodeItr = g.getEdgeNode2Itr(edgeItr);
- g.getNodeCosts(otherNodeItr) +=
- g.getEdgeCosts(edgeItr).getRowAsVector(0);
- }
- else {
- GraphNodeIterator otherNodeItr = g.getEdgeNode1Itr(edgeItr);
- g.getNodeCosts(otherNodeItr) +=
- g.getEdgeCosts(edgeItr).getColAsVector(0);
+ for (unsigned i = 0; i < yLen; ++i) {
+ for (unsigned j = 0; j < zLen; ++j) {
+ PBQPNum min = (*yxeCosts)[i][0] + (*zxeCosts)[j][0] + xCosts[0];
+ for (unsigned k = 1; k < xLen; ++k) {
+ PBQPNum c = (*yxeCosts)[i][k] + (*zxeCosts)[j][k] + xCosts[k];
+ if (c < min) {
+ min = c;
+ }
}
-
- edgesToRemove.push_back(edgeItr);
+ delta[i][j] = min;
}
+ }
- while (!edgesToRemove.empty()) {
- g.removeEdge(edgesToRemove.back());
- edgesToRemove.pop_back();
+ if (flipEdge1)
+ delete yxeCosts;
+
+ if (flipEdge2)
+ delete zxeCosts;
+
+ Graph::EdgeItr yzeItr = g.findEdge(ynItr, znItr);
+ bool addedEdge = false;
+
+ if (yzeItr == g.edgesEnd()) {
+ yzeItr = g.addEdge(ynItr, znItr, delta);
+ addedEdge = true;
+ } else {
+ Matrix &yzeCosts = g.getEdgeCosts(yzeItr);
+ h.preUpdateEdgeCosts(yzeItr);
+ if (ynItr == g.getEdgeNode1(yzeItr)) {
+ yzeCosts += delta;
+ } else {
+ yzeCosts += delta.transpose();
}
}
- }
- }
-
- void eliminateIndependentEdges() {
- std::vector<GraphEdgeIterator> edgesToProcess;
-
- for (GraphEdgeIterator edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
- edgeItr != edgeEnd; ++edgeItr) {
- edgesToProcess.push_back(edgeItr);
- }
-
- while (!edgesToProcess.empty()) {
- tryToEliminateEdge(edgesToProcess.back());
- edgesToProcess.pop_back();
- }
- }
-
- void tryToEliminateEdge(const GraphEdgeIterator &edgeItr) {
- if (tryNormaliseEdgeMatrix(edgeItr)) {
- g.removeEdge(edgeItr);
- }
- }
-
- bool tryNormaliseEdgeMatrix(const GraphEdgeIterator &edgeItr) {
- Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
- Vector &uCosts = g.getNodeCosts(g.getEdgeNode1Itr(edgeItr)),
- &vCosts = g.getNodeCosts(g.getEdgeNode2Itr(edgeItr));
+ bool nullCostEdge = tryNormaliseEdgeMatrix(yzeItr);
- for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
- PBQPNum rowMin = edgeCosts.getRowMin(r);
- uCosts[r] += rowMin;
- if (rowMin != std::numeric_limits<PBQPNum>::infinity()) {
- edgeCosts.subFromRow(r, rowMin);
+ if (!addedEdge) {
+ // If we modified the edge costs let the heuristic know.
+ h.postUpdateEdgeCosts(yzeItr);
}
- else {
- edgeCosts.setRow(r, 0);
+
+ if (nullCostEdge) {
+ // If this edge ended up null remove it.
+ if (!addedEdge) {
+ // We didn't just add it, so we need to notify the heuristic
+ // and remove it from the solver.
+ h.handleRemoveEdge(yzeItr, ynItr);
+ h.handleRemoveEdge(yzeItr, znItr);
+ removeSolverEdge(yzeItr);
+ }
+ g.removeEdge(yzeItr);
+ } else if (addedEdge) {
+ // If the edge was added, and non-null, finish setting it up, add it to
+ // the solver & notify heuristic.
+ edgeData.push_back(EdgeData());
+ g.setEdgeData(yzeItr, &edgeData.back());
+ addSolverEdge(yzeItr);
+ h.handleAddEdge(yzeItr);
}
- }
- for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
- PBQPNum colMin = edgeCosts.getColMin(c);
- vCosts[c] += colMin;
- if (colMin != std::numeric_limits<PBQPNum>::infinity()) {
- edgeCosts.subFromCol(c, colMin);
- }
- else {
- edgeCosts.setCol(c, 0);
- }
- }
+ h.handleRemoveEdge(yxeItr, ynItr);
+ removeSolverEdge(yxeItr);
+ h.handleRemoveEdge(zxeItr, znItr);
+ removeSolverEdge(zxeItr);
- return edgeCosts.isZero();
- }
+ pushToStack(xnItr);
+ }
- void setup() {
- setupLinks();
- heuristic.initialise(*this);
- setupBuckets();
- }
+ private:
- void setupLinks() {
- for (GraphEdgeIterator edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd();
- edgeItr != edgeEnd; ++edgeItr) {
- g.getEdgeData(edgeItr).setup(edgeItr);
+ NodeData& getSolverNodeData(Graph::NodeItr nItr) {
+ return *static_cast<NodeData*>(g.getNodeData(nItr));
}
- }
- void setupBuckets() {
- for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
- nodeItr != nodeEnd; ++nodeItr) {
- addToBucket(nodeItr);
- }
- }
-
- void computeSolution() {
- assert(g.areNodeIDsValid() &&
- "Nodes cannot be added/removed during reduction.");
-
- reduce();
- computeTrivialSolutions();
- backpropagate();
- }
-
- void printNode(const GraphNodeIterator &nodeItr) {
- llvm::errs() << "Node " << g.getNodeID(nodeItr) << " (" << &*nodeItr << "):\n"
- << " costs = " << g.getNodeCosts(nodeItr) << "\n"
- << " link degree = " << g.getNodeData(nodeItr).getLinkDegree() << "\n"
- << " links = [ ";
-
- for (typename HSIT::NodeData::AdjLinkIterator
- aeItr = g.getNodeData(nodeItr).adjLinksBegin(),
- aeEnd = g.getNodeData(nodeItr).adjLinksEnd();
- aeItr != aeEnd; ++aeItr) {
- llvm::errs() << "(" << g.getNodeID(g.getEdgeNode1Itr(*aeItr))
- << ", " << g.getNodeID(g.getEdgeNode2Itr(*aeItr))
- << ") ";
+ EdgeData& getSolverEdgeData(Graph::EdgeItr eItr) {
+ return *static_cast<EdgeData*>(g.getEdgeData(eItr));
}
- llvm::errs() << "]\n";
- }
- void dumpState() {
- llvm::errs() << "\n";
+ void addSolverEdge(Graph::EdgeItr eItr) {
+ EdgeData &eData = getSolverEdgeData(eItr);
+ NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eItr)),
+ &n2Data = getSolverNodeData(g.getEdgeNode2(eItr));
- for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd();
- nodeItr != nodeEnd; ++nodeItr) {
- printNode(nodeItr);
+ eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eItr));
+ eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eItr));
}
- NodeList* buckets[] = { &r0Bucket, &r1Bucket, &r2Bucket };
-
- for (unsigned b = 0; b < 3; ++b) {
- NodeList &bucket = *buckets[b];
-
- llvm::errs() << "Bucket " << b << ": [ ";
-
- for (NodeListIterator nItr = bucket.begin(), nEnd = bucket.end();
- nItr != nEnd; ++nItr) {
- llvm::errs() << g.getNodeID(*nItr) << " ";
+ void setup() {
+ if (h.solverRunSimplify()) {
+ simplify();
}
- llvm::errs() << "]\n";
- }
-
- llvm::errs() << "Stack: [ ";
- for (NodeStackIterator nsItr = stack.begin(), nsEnd = stack.end();
- nsItr != nsEnd; ++nsItr) {
- llvm::errs() << g.getNodeID(*nsItr) << " ";
- }
- llvm::errs() << "]\n";
- }
-
- void reduce() {
- bool reductionFinished = r1Bucket.empty() && r2Bucket.empty() &&
- heuristic.rNBucketEmpty();
-
- while (!reductionFinished) {
+ // Reserve space for the node and edge data.
+ nodeData.resize(g.getNumNodes());
+ edgeData.resize(g.getNumEdges());
- if (!r1Bucket.empty()) {
- processR1();
- }
- else if (!r2Bucket.empty()) {
- processR2();
+ // Create node data objects.
+ unsigned ndIndex = 0;
+ for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
+ nItr != nEnd; ++nItr, ++ndIndex) {
+ g.setNodeData(nItr, &nodeData[ndIndex]);
}
- else if (!heuristic.rNBucketEmpty()) {
- solution.setProvedOptimal(false);
- solution.incRNReductions();
- heuristic.processRN();
- }
- else reductionFinished = true;
- }
-
- }
-
- void processR1() {
-
- // Remove the first node in the R0 bucket:
- GraphNodeIterator xNodeItr = r1Bucket.front();
- r1Bucket.pop_front();
-
- solution.incR1Reductions();
-
- //llvm::errs() << "Applying R1 to " << g.getNodeID(xNodeItr) << "\n";
-
- assert((g.getNodeData(xNodeItr).getLinkDegree() == 1) &&
- "Node in R1 bucket has degree != 1");
-
- GraphEdgeIterator edgeItr = *g.getNodeData(xNodeItr).adjLinksBegin();
- const Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
-
- const Vector &xCosts = g.getNodeCosts(xNodeItr);
- unsigned xLen = xCosts.getLength();
-
- // Duplicate a little code to avoid transposing matrices:
- if (xNodeItr == g.getEdgeNode1Itr(edgeItr)) {
- GraphNodeIterator yNodeItr = g.getEdgeNode2Itr(edgeItr);
- Vector &yCosts = g.getNodeCosts(yNodeItr);
- unsigned yLen = yCosts.getLength();
-
- for (unsigned j = 0; j < yLen; ++j) {
- PBQPNum min = edgeCosts[0][j] + xCosts[0];
- for (unsigned i = 1; i < xLen; ++i) {
- PBQPNum c = edgeCosts[i][j] + xCosts[i];
- if (c < min)
- min = c;
- }
- yCosts[j] += min;
+ // Create edge data objects.
+ unsigned edIndex = 0;
+ for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
+ eItr != eEnd; ++eItr, ++edIndex) {
+ g.setEdgeData(eItr, &edgeData[edIndex]);
+ addSolverEdge(eItr);
}
}
- else {
- GraphNodeIterator yNodeItr = g.getEdgeNode1Itr(edgeItr);
- Vector &yCosts = g.getNodeCosts(yNodeItr);
- unsigned yLen = yCosts.getLength();
-
- for (unsigned i = 0; i < yLen; ++i) {
- PBQPNum min = edgeCosts[i][0] + xCosts[0];
- for (unsigned j = 1; j < xLen; ++j) {
- PBQPNum c = edgeCosts[i][j] + xCosts[j];
- if (c < min)
- min = c;
- }
- yCosts[i] += min;
- }
+ void simplify() {
+ disconnectTrivialNodes();
+ eliminateIndependentEdges();
}
- unlinkNode(xNodeItr);
- pushStack(xNodeItr);
- }
-
- void processR2() {
-
- GraphNodeIterator xNodeItr = r2Bucket.front();
- r2Bucket.pop_front();
+ // Eliminate trivial nodes.
+ void disconnectTrivialNodes() {
+ unsigned numDisconnected = 0;
- solution.incR2Reductions();
-
- // Unlink is unsafe here. At some point it may optimistically more a node
- // to a lower-degree list when its degree will later rise, or vice versa,
- // violating the assumption that node degrees monotonically decrease
- // during the reduction phase. Instead we'll bucket shuffle manually.
- pushStack(xNodeItr);
-
- assert((g.getNodeData(xNodeItr).getLinkDegree() == 2) &&
- "Node in R2 bucket has degree != 2");
-
- const Vector &xCosts = g.getNodeCosts(xNodeItr);
-
- typename NodeData::AdjLinkIterator tempItr =
- g.getNodeData(xNodeItr).adjLinksBegin();
-
- GraphEdgeIterator yxEdgeItr = *tempItr,
- zxEdgeItr = *(++tempItr);
+ for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd();
+ nItr != nEnd; ++nItr) {
- GraphNodeIterator yNodeItr = g.getEdgeOtherNode(yxEdgeItr, xNodeItr),
- zNodeItr = g.getEdgeOtherNode(zxEdgeItr, xNodeItr);
+ if (g.getNodeCosts(nItr).getLength() == 1) {
- removeFromBucket(yNodeItr);
- removeFromBucket(zNodeItr);
+ std::vector<Graph::EdgeItr> edgesToRemove;
- removeLink(yxEdgeItr, yNodeItr);
- removeLink(zxEdgeItr, zNodeItr);
+ for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nItr),
+ aeEnd = g.adjEdgesEnd(nItr);
+ aeItr != aeEnd; ++aeItr) {
- // Graph some of the costs:
- bool flipEdge1 = (g.getEdgeNode1Itr(yxEdgeItr) == xNodeItr),
- flipEdge2 = (g.getEdgeNode1Itr(zxEdgeItr) == xNodeItr);
+ Graph::EdgeItr eItr = *aeItr;
- const Matrix *yxCosts = flipEdge1 ?
- new Matrix(g.getEdgeCosts(yxEdgeItr).transpose()) :
- &g.getEdgeCosts(yxEdgeItr),
- *zxCosts = flipEdge2 ?
- new Matrix(g.getEdgeCosts(zxEdgeItr).transpose()) :
- &g.getEdgeCosts(zxEdgeItr);
+ if (g.getEdgeNode1(eItr) == nItr) {
+ Graph::NodeItr otherNodeItr = g.getEdgeNode2(eItr);
+ g.getNodeCosts(otherNodeItr) +=
+ g.getEdgeCosts(eItr).getRowAsVector(0);
+ }
+ else {
+ Graph::NodeItr otherNodeItr = g.getEdgeNode1(eItr);
+ g.getNodeCosts(otherNodeItr) +=
+ g.getEdgeCosts(eItr).getColAsVector(0);
+ }
- unsigned xLen = xCosts.getLength(),
- yLen = yxCosts->getRows(),
- zLen = zxCosts->getRows();
+ edgesToRemove.push_back(eItr);
+ }
- // Compute delta:
- Matrix delta(yLen, zLen);
+ if (!edgesToRemove.empty())
+ ++numDisconnected;
- for (unsigned i = 0; i < yLen; ++i) {
- for (unsigned j = 0; j < zLen; ++j) {
- PBQPNum min = (*yxCosts)[i][0] + (*zxCosts)[j][0] + xCosts[0];
- for (unsigned k = 1; k < xLen; ++k) {
- PBQPNum c = (*yxCosts)[i][k] + (*zxCosts)[j][k] + xCosts[k];
- if (c < min) {
- min = c;
+ while (!edgesToRemove.empty()) {
+ g.removeEdge(edgesToRemove.back());
+ edgesToRemove.pop_back();
}
}
- delta[i][j] = min;
}
}
- if (flipEdge1)
- delete yxCosts;
-
- if (flipEdge2)
- delete zxCosts;
-
- // Deal with the potentially induced yz edge.
- GraphEdgeIterator yzEdgeItr = g.findEdge(yNodeItr, zNodeItr);
- if (yzEdgeItr == g.edgesEnd()) {
- yzEdgeItr = g.addEdge(yNodeItr, zNodeItr, delta, EdgeData(g));
- }
- else {
- // There was an edge, but we're going to screw with it. Delete the old
- // link, update the costs. We'll re-link it later.
- removeLinkR2(yzEdgeItr);
- g.getEdgeCosts(yzEdgeItr) +=
- (yNodeItr == g.getEdgeNode1Itr(yzEdgeItr)) ?
- delta : delta.transpose();
- }
+ void eliminateIndependentEdges() {
+ std::vector<Graph::EdgeItr> edgesToProcess;
+ unsigned numEliminated = 0;
- bool nullCostEdge = tryNormaliseEdgeMatrix(yzEdgeItr);
+ for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd();
+ eItr != eEnd; ++eItr) {
+ edgesToProcess.push_back(eItr);
+ }
- // Nulled the edge, remove it entirely.
- if (nullCostEdge) {
- g.removeEdge(yzEdgeItr);
- }
- else {
- // Edge remains - re-link it.
- addLink(yzEdgeItr);
+ while (!edgesToProcess.empty()) {
+ if (tryToEliminateEdge(edgesToProcess.back()))
+ ++numEliminated;
+ edgesToProcess.pop_back();
+ }
}
- addToBucket(yNodeItr);
- addToBucket(zNodeItr);
+ bool tryToEliminateEdge(Graph::EdgeItr eItr) {
+ if (tryNormaliseEdgeMatrix(eItr)) {
+ g.removeEdge(eItr);
+ return true;
+ }
+ return false;
}
- void computeTrivialSolutions() {
+ bool tryNormaliseEdgeMatrix(Graph::EdgeItr &eItr) {
- for (NodeListIterator r0Itr = r0Bucket.begin(), r0End = r0Bucket.end();
- r0Itr != r0End; ++r0Itr) {
- GraphNodeIterator nodeItr = *r0Itr;
+ Matrix &edgeCosts = g.getEdgeCosts(eItr);
+ Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eItr)),
+ &vCosts = g.getNodeCosts(g.getEdgeNode2(eItr));
- solution.incR0Reductions();
- setSolution(nodeItr, g.getNodeCosts(nodeItr).minIndex());
- }
+ for (unsigned r = 0; r < edgeCosts.getRows(); ++r) {
+ PBQPNum rowMin = edgeCosts.getRowMin(r);
+ uCosts[r] += rowMin;
+ if (rowMin != std::numeric_limits<PBQPNum>::infinity()) {
+ edgeCosts.subFromRow(r, rowMin);
+ }
+ else {
+ edgeCosts.setRow(r, 0);
+ }
+ }
- }
+ for (unsigned c = 0; c < edgeCosts.getCols(); ++c) {
+ PBQPNum colMin = edgeCosts.getColMin(c);
+ vCosts[c] += colMin;
+ if (colMin != std::numeric_limits<PBQPNum>::infinity()) {
+ edgeCosts.subFromCol(c, colMin);
+ }
+ else {
+ edgeCosts.setCol(c, 0);
+ }
+ }
- void backpropagate() {
- while (!stack.empty()) {
- computeSolution(stack.back());
- stack.pop_back();
+ return edgeCosts.isZero();
}
- }
-
- void computeSolution(const GraphNodeIterator &nodeItr) {
-
- NodeData &nodeData = g.getNodeData(nodeItr);
-
- Vector v(g.getNodeCosts(nodeItr));
-
- // Solve based on existing links.
- for (typename NodeData::AdjLinkIterator
- solvedLinkItr = nodeData.solvedLinksBegin(),
- solvedLinkEnd = nodeData.solvedLinksEnd();
- solvedLinkItr != solvedLinkEnd; ++solvedLinkItr) {
- GraphEdgeIterator solvedEdgeItr(*solvedLinkItr);
- Matrix &edgeCosts = g.getEdgeCosts(solvedEdgeItr);
-
- if (nodeItr == g.getEdgeNode1Itr(solvedEdgeItr)) {
- GraphNodeIterator adjNode(g.getEdgeNode2Itr(solvedEdgeItr));
- unsigned adjSolution =
- solution.getSelection(g.getNodeID(adjNode));
- v += edgeCosts.getColAsVector(adjSolution);
- }
- else {
- GraphNodeIterator adjNode(g.getEdgeNode1Itr(solvedEdgeItr));
- unsigned adjSolution =
- solution.getSelection(g.getNodeID(adjNode));
- v += edgeCosts.getRowAsVector(adjSolution);
+ void backpropagate() {
+ while (!stack.empty()) {
+ computeSolution(stack.back());
+ stack.pop_back();
}
-
}
- setSolution(nodeItr, v.minIndex());
- }
+ void computeSolution(Graph::NodeItr nItr) {
- void computeSolutionCost(const SimpleGraph &orig) {
- PBQPNum cost = 0.0;
+ NodeData &nodeData = getSolverNodeData(nItr);
- for (SimpleGraph::ConstNodeIterator
- nodeItr = orig.nodesBegin(), nodeEnd = orig.nodesEnd();
- nodeItr != nodeEnd; ++nodeItr) {
+ Vector v(g.getNodeCosts(nItr));
- unsigned nodeId = orig.getNodeID(nodeItr);
+ // Solve based on existing solved edges.
+ for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(),
+ solvedEdgeEnd = nodeData.solverEdgesEnd();
+ solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) {
- cost += orig.getNodeCosts(nodeItr)[solution.getSelection(nodeId)];
- }
+ Graph::EdgeItr eItr(*solvedEdgeItr);
+ Matrix &edgeCosts = g.getEdgeCosts(eItr);
- for (SimpleGraph::ConstEdgeIterator
- edgeItr = orig.edgesBegin(), edgeEnd = orig.edgesEnd();
- edgeItr != edgeEnd; ++edgeItr) {
+ if (nItr == g.getEdgeNode1(eItr)) {
+ Graph::NodeItr adjNode(g.getEdgeNode2(eItr));
+ unsigned adjSolution = s.getSelection(adjNode);
+ v += edgeCosts.getColAsVector(adjSolution);
+ }
+ else {
+ Graph::NodeItr adjNode(g.getEdgeNode1(eItr));
+ unsigned adjSolution = s.getSelection(adjNode);
+ v += edgeCosts.getRowAsVector(adjSolution);
+ }
- SimpleGraph::ConstNodeIterator n1 = orig.getEdgeNode1Itr(edgeItr),
- n2 = orig.getEdgeNode2Itr(edgeItr);
- unsigned sol1 = solution.getSelection(orig.getNodeID(n1)),
- sol2 = solution.getSelection(orig.getNodeID(n2));
+ }
- cost += orig.getEdgeCosts(edgeItr)[sol1][sol2];
+ setSolution(nItr, v.minIndex());
}
- solution.setSolutionCost(cost);
- }
-
-};
+ void cleanup() {
+ h.cleanup();
+ nodeData.clear();
+ edgeData.clear();
+ }
+ };
-template <typename Heuristic>
-class HeuristicSolver : public Solver {
-public:
- Solution solve(const SimpleGraph &g) const {
- HeuristicSolverImpl<Heuristic> solverImpl(g);
- return solverImpl.getSolution();
- }
-};
+ /// \brief PBQP heuristic solver class.
+ ///
+ /// Given a PBQP Graph g representing a PBQP problem, you can find a solution
+ /// by calling
+ /// <tt>Solution s = HeuristicSolver<H>::solve(g);</tt>
+ ///
+ /// The choice of heuristic for the H parameter will affect both the solver
+ /// speed and solution quality. The heuristic should be chosen based on the
+ /// nature of the problem being solved.
+ /// Currently the only solver included with LLVM is the Briggs heuristic for
+ /// register allocation.
+ template <typename HImpl>
+ class HeuristicSolver {
+ public:
+ static Solution solve(Graph &g) {
+ HeuristicSolverImpl<HImpl> hs(g);
+ return hs.computeSolution();
+ }
+ };
}
#define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H
#include "../HeuristicSolver.h"
+#include "../HeuristicBase.h"
#include <set>
+#include <limits>
namespace PBQP {
-namespace Heuristics {
-
-class Briggs {
- public:
-
- class NodeData;
- class EdgeData;
-
- private:
-
- typedef HeuristicSolverImpl<Briggs> Solver;
- typedef HSITypes<NodeData, EdgeData> HSIT;
- typedef HSIT::SolverGraph SolverGraph;
- typedef HSIT::GraphNodeIterator GraphNodeIterator;
- typedef HSIT::GraphEdgeIterator GraphEdgeIterator;
-
- class LinkDegreeComparator {
+ namespace Heuristics {
+
+ /// \brief PBQP Heuristic which applies an allocability test based on
+ /// Briggs.
+ ///
+ /// This heuristic assumes that the elements of cost vectors in the PBQP
+ /// problem represent storage options, with the first being the spill
+ /// option and subsequent elements representing legal registers for the
+ /// corresponding node. Edge cost matrices are likewise assumed to represent
+ /// register constraints.
+ /// If one or more nodes can be proven allocable by this heuristic (by
+ /// inspection of their constraint matrices) then the allocable node of
+ /// highest degree is selected for the next reduction and pushed to the
+ /// solver stack. If no nodes can be proven allocable then the node with
+ /// the lowest estimated spill cost is selected and push to the solver stack
+ /// instead.
+ ///
+ /// This implementation is built on top of HeuristicBase.
+ class Briggs : public HeuristicBase<Briggs> {
+ private:
+
+ class LinkDegreeComparator {
public:
- LinkDegreeComparator() : g(0) {}
- LinkDegreeComparator(SolverGraph *g) : g(g) {}
-
- bool operator()(const GraphNodeIterator &node1Itr,
- const GraphNodeIterator &node2Itr) const {
- assert((g != 0) && "Graph object not set, cannot access node data.");
- unsigned n1Degree = g->getNodeData(node1Itr).getLinkDegree(),
- n2Degree = g->getNodeData(node2Itr).getLinkDegree();
- if (n1Degree > n2Degree) {
+ LinkDegreeComparator(HeuristicSolverImpl<Briggs> &s) : s(&s) {}
+ bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
+ if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr))
return true;
- }
- else if (n1Degree < n2Degree) {
+ if (s->getSolverDegree(n1Itr) < s->getSolverDegree(n2Itr))
return false;
- }
- // else they're "equal" by degree, differentiate based on ID.
- return g->getNodeID(node1Itr) < g->getNodeID(node2Itr);
+ return (&*n1Itr < &*n2Itr);
}
-
private:
- SolverGraph *g;
- };
+ HeuristicSolverImpl<Briggs> *s;
+ };
- class SpillPriorityComparator {
+ class SpillCostComparator {
public:
- SpillPriorityComparator() : g(0) {}
- SpillPriorityComparator(SolverGraph *g) : g(g) {}
-
- bool operator()(const GraphNodeIterator &node1Itr,
- const GraphNodeIterator &node2Itr) const {
- assert((g != 0) && "Graph object not set, cannot access node data.");
- PBQPNum cost1 =
- g->getNodeCosts(node1Itr)[0] /
- g->getNodeData(node1Itr).getLinkDegree(),
- cost2 =
- g->getNodeCosts(node2Itr)[0] /
- g->getNodeData(node2Itr).getLinkDegree();
-
- if (cost1 < cost2) {
+ SpillCostComparator(HeuristicSolverImpl<Briggs> &s)
+ : s(&s), g(&s.getGraph()) {}
+ bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
+ PBQPNum cost1 = g->getNodeCosts(n1Itr)[0] / s->getSolverDegree(n1Itr),
+ cost2 = g->getNodeCosts(n2Itr)[0] / s->getSolverDegree(n2Itr);
+ if (cost1 < cost2)
return true;
- }
- else if (cost1 > cost2) {
+ if (cost1 > cost2)
return false;
- }
- // else they'er "equal" again, differentiate based on address again.
- return g->getNodeID(node1Itr) < g->getNodeID(node2Itr);
+ return (&*n1Itr < &*n2Itr);
}
private:
- SolverGraph *g;
- };
-
- typedef std::set<GraphNodeIterator, LinkDegreeComparator>
- RNAllocableNodeList;
- typedef RNAllocableNodeList::iterator RNAllocableNodeListIterator;
-
- typedef std::set<GraphNodeIterator, SpillPriorityComparator>
- RNUnallocableNodeList;
- typedef RNUnallocableNodeList::iterator RNUnallocableNodeListIterator;
-
- public:
-
- class NodeData {
- private:
- RNAllocableNodeListIterator rNAllocableNodeListItr;
- RNUnallocableNodeListIterator rNUnallocableNodeListItr;
- unsigned numRegOptions, numDenied, numSafe;
- std::vector<unsigned> unsafeDegrees;
- bool allocable;
-
- void addRemoveLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
- const GraphEdgeIterator &edgeItr, bool add) {
+ HeuristicSolverImpl<Briggs> *s;
+ Graph *g;
+ };
- //assume we're adding...
- unsigned udTarget = 0, dir = 1;
+ typedef std::list<Graph::NodeItr> RNAllocableList;
+ typedef RNAllocableList::iterator RNAllocableListItr;
- if (!add) {
- udTarget = 1;
- dir = ~0;
- }
+ typedef std::list<Graph::NodeItr> RNUnallocableList;
+ typedef RNUnallocableList::iterator RNUnallocableListItr;
- EdgeData &linkEdgeData = g.getEdgeData(edgeItr).getHeuristicData();
+ public:
- EdgeData::ConstUnsafeIterator edgeUnsafeBegin, edgeUnsafeEnd;
+ struct NodeData {
+ typedef std::vector<unsigned> UnsafeDegreesArray;
+ bool isHeuristic, isAllocable, isInitialized;
+ unsigned numDenied, numSafe;
+ UnsafeDegreesArray unsafeDegrees;
+ RNAllocableListItr rnaItr;
+ RNUnallocableListItr rnuItr;
- if (nodeItr == g.getEdgeNode1Itr(edgeItr)) {
- numDenied += (dir * linkEdgeData.getWorstDegree());
- edgeUnsafeBegin = linkEdgeData.unsafeBegin();
- edgeUnsafeEnd = linkEdgeData.unsafeEnd();
- }
- else {
- numDenied += (dir * linkEdgeData.getReverseWorstDegree());
- edgeUnsafeBegin = linkEdgeData.reverseUnsafeBegin();
- edgeUnsafeEnd = linkEdgeData.reverseUnsafeEnd();
- }
+ NodeData()
+ : isHeuristic(false), isAllocable(false), isInitialized(false),
+ numDenied(0), numSafe(0) { }
+ };
- assert((unsafeDegrees.size() ==
- static_cast<unsigned>(
- std::distance(edgeUnsafeBegin, edgeUnsafeEnd)))
- && "Unsafe array size mismatch.");
-
- std::vector<unsigned>::iterator unsafeDegreesItr =
- unsafeDegrees.begin();
-
- for (EdgeData::ConstUnsafeIterator edgeUnsafeItr = edgeUnsafeBegin;
- edgeUnsafeItr != edgeUnsafeEnd;
- ++edgeUnsafeItr, ++unsafeDegreesItr) {
-
- if ((*edgeUnsafeItr == 1) && (*unsafeDegreesItr == udTarget)) {
- numSafe -= dir;
- }
- *unsafeDegreesItr += (dir * (*edgeUnsafeItr));
+ struct EdgeData {
+ typedef std::vector<unsigned> UnsafeArray;
+ unsigned worst, reverseWorst;
+ UnsafeArray unsafe, reverseUnsafe;
+ bool isUpToDate;
+
+ EdgeData() : worst(0), reverseWorst(0), isUpToDate(false) {}
+ };
+
+ /// \brief Construct an instance of the Briggs heuristic.
+ /// @param solver A reference to the solver which is using this heuristic.
+ Briggs(HeuristicSolverImpl<Briggs> &solver) :
+ HeuristicBase<Briggs>(solver) {}
+
+ /// \brief Determine whether a node should be reduced using optimal
+ /// reduction.
+ /// @param nItr Node iterator to be considered.
+ /// @return True if the given node should be optimally reduced, false
+ /// otherwise.
+ ///
+ /// Selects nodes of degree 0, 1 or 2 for optimal reduction, with one
+ /// exception. Nodes whose spill cost (element 0 of their cost vector) is
+ /// infinite are checked for allocability first. Allocable nodes may be
+ /// optimally reduced, but nodes whose allocability cannot be proven are
+ /// selected for heuristic reduction instead.
+ bool shouldOptimallyReduce(Graph::NodeItr nItr) {
+ if (getSolver().getSolverDegree(nItr) < 3) {
+ if (getGraph().getNodeCosts(nItr)[0] !=
+ std::numeric_limits<PBQPNum>::infinity()) {
+ return true;
}
-
- allocable = (numDenied < numRegOptions) || (numSafe > 0);
+ // Otherwise we have an infinite spill cost node.
+ initializeNode(nItr);
+ NodeData &nd = getHeuristicNodeData(nItr);
+ return nd.isAllocable;
}
-
- public:
-
- void setup(SolverGraph &g, const GraphNodeIterator &nodeItr) {
-
- numRegOptions = g.getNodeCosts(nodeItr).getLength() - 1;
-
- numSafe = numRegOptions; // Optimistic, correct below.
- numDenied = 0; // Also optimistic.
- unsafeDegrees.resize(numRegOptions, 0);
-
- HSIT::NodeData &nodeData = g.getNodeData(nodeItr);
-
- for (HSIT::NodeData::AdjLinkIterator
- adjLinkItr = nodeData.adjLinksBegin(),
- adjLinkEnd = nodeData.adjLinksEnd();
- adjLinkItr != adjLinkEnd; ++adjLinkItr) {
-
- addRemoveLink(g, nodeItr, *adjLinkItr, true);
- }
+ // else
+ return false;
+ }
+
+ /// \brief Add a node to the heuristic reduce list.
+ /// @param nItr Node iterator to add to the heuristic reduce list.
+ void addToHeuristicReduceList(Graph::NodeItr nItr) {
+ NodeData &nd = getHeuristicNodeData(nItr);
+ initializeNode(nItr);
+ nd.isHeuristic = true;
+ if (nd.isAllocable) {
+ nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
+ } else {
+ nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr);
}
-
- bool isAllocable() const { return allocable; }
-
- void handleAddLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
- const GraphEdgeIterator &adjEdge) {
- addRemoveLink(g, nodeItr, adjEdge, true);
+ }
+
+ /// \brief Heuristically reduce one of the nodes in the heuristic
+ /// reduce list.
+ /// @return True if a reduction takes place, false if the heuristic reduce
+ /// list is empty.
+ ///
+ /// If the list of allocable nodes is non-empty a node is selected
+ /// from it and pushed to the stack. Otherwise if the non-allocable list
+ /// is non-empty a node is selected from it and pushed to the stack.
+ /// If both lists are empty the method simply returns false with no action
+ /// taken.
+ bool heuristicReduce() {
+ if (!rnAllocableList.empty()) {
+ RNAllocableListItr rnaItr =
+ min_element(rnAllocableList.begin(), rnAllocableList.end(),
+ LinkDegreeComparator(getSolver()));
+ Graph::NodeItr nItr = *rnaItr;
+ rnAllocableList.erase(rnaItr);
+ handleRemoveNode(nItr);
+ getSolver().pushToStack(nItr);
+ return true;
+ } else if (!rnUnallocableList.empty()) {
+ RNUnallocableListItr rnuItr =
+ min_element(rnUnallocableList.begin(), rnUnallocableList.end(),
+ SpillCostComparator(getSolver()));
+ Graph::NodeItr nItr = *rnuItr;
+ rnUnallocableList.erase(rnuItr);
+ handleRemoveNode(nItr);
+ getSolver().pushToStack(nItr);
+ return true;
}
-
- void handleRemoveLink(SolverGraph &g, const GraphNodeIterator &nodeItr,
- const GraphEdgeIterator &adjEdge) {
- addRemoveLink(g, nodeItr, adjEdge, false);
- }
-
- void setRNAllocableNodeListItr(
- const RNAllocableNodeListIterator &rNAllocableNodeListItr) {
-
- this->rNAllocableNodeListItr = rNAllocableNodeListItr;
- }
-
- RNAllocableNodeListIterator getRNAllocableNodeListItr() const {
- return rNAllocableNodeListItr;
+ // else
+ return false;
+ }
+
+ /// \brief Prepare a change in the costs on the given edge.
+ /// @param eItr Edge iterator.
+ void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
+ Graph &g = getGraph();
+ Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
+ n2Itr = g.getEdgeNode2(eItr);
+ NodeData &n1 = getHeuristicNodeData(n1Itr),
+ &n2 = getHeuristicNodeData(n2Itr);
+
+ if (n1.isHeuristic)
+ subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr));
+ if (n2.isHeuristic)
+ subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr));
+
+ EdgeData &ed = getHeuristicEdgeData(eItr);
+ ed.isUpToDate = false;
+ }
+
+ /// \brief Handle the change in the costs on the given edge.
+ /// @param eItr Edge iterator.
+ void postUpdateEdgeCosts(Graph::EdgeItr eItr) {
+ // This is effectively the same as adding a new edge now, since
+ // we've factored out the costs of the old one.
+ handleAddEdge(eItr);
+ }
+
+ /// \brief Handle the addition of a new edge into the PBQP graph.
+ /// @param eItr Edge iterator for the added edge.
+ ///
+ /// Updates allocability of any nodes connected by this edge which are
+ /// being managed by the heuristic. If allocability changes they are
+ /// moved to the appropriate list.
+ void handleAddEdge(Graph::EdgeItr eItr) {
+ Graph &g = getGraph();
+ Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
+ n2Itr = g.getEdgeNode2(eItr);
+ NodeData &n1 = getHeuristicNodeData(n1Itr),
+ &n2 = getHeuristicNodeData(n2Itr);
+
+ // If neither node is managed by the heuristic there's nothing to be
+ // done.
+ if (!n1.isHeuristic && !n2.isHeuristic)
+ return;
+
+ // Ok - we need to update at least one node.
+ computeEdgeContributions(eItr);
+
+ // Update node 1 if it's managed by the heuristic.
+ if (n1.isHeuristic) {
+ bool n1WasAllocable = n1.isAllocable;
+ addEdgeContributions(eItr, n1Itr);
+ updateAllocability(n1Itr);
+ if (n1WasAllocable && !n1.isAllocable) {
+ rnAllocableList.erase(n1.rnaItr);
+ n1.rnuItr =
+ rnUnallocableList.insert(rnUnallocableList.end(), n1Itr);
+ }
}
- void setRNUnallocableNodeListItr(
- const RNUnallocableNodeListIterator &rNUnallocableNodeListItr) {
-
- this->rNUnallocableNodeListItr = rNUnallocableNodeListItr;
+ // Likewise for node 2.
+ if (n2.isHeuristic) {
+ bool n2WasAllocable = n2.isAllocable;
+ addEdgeContributions(eItr, n2Itr);
+ updateAllocability(n2Itr);
+ if (n2WasAllocable && !n2.isAllocable) {
+ rnAllocableList.erase(n2.rnaItr);
+ n2.rnuItr =
+ rnUnallocableList.insert(rnUnallocableList.end(), n2Itr);
+ }
}
-
- RNUnallocableNodeListIterator getRNUnallocableNodeListItr() const {
- return rNUnallocableNodeListItr;
+ }
+
+ /// \brief Handle disconnection of an edge from a node.
+ /// @param eItr Edge iterator for edge being disconnected.
+ /// @param nItr Node iterator for the node being disconnected from.
+ ///
+ /// Updates allocability of the given node and, if appropriate, moves the
+ /// node to a new list.
+ void handleRemoveEdge(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
+ NodeData &nd = getHeuristicNodeData(nItr);
+
+ // If the node is not managed by the heuristic there's nothing to be
+ // done.
+ if (!nd.isHeuristic)
+ return;
+
+ EdgeData &ed = getHeuristicEdgeData(eItr);
+
+ assert(ed.isUpToDate && "Edge data is not up to date.");
+
+ // Update node.
+ bool ndWasAllocable = nd.isAllocable;
+ subtractEdgeContributions(eItr, nItr);
+ updateAllocability(nItr);
+
+ // If the node has gone optimal...
+ if (shouldOptimallyReduce(nItr)) {
+ nd.isHeuristic = false;
+ addToOptimalReduceList(nItr);
+ if (ndWasAllocable) {
+ rnAllocableList.erase(nd.rnaItr);
+ } else {
+ rnUnallocableList.erase(nd.rnuItr);
+ }
+ } else {
+ // Node didn't go optimal, but we might have to move it
+ // from "unallocable" to "allocable".
+ if (!ndWasAllocable && nd.isAllocable) {
+ rnUnallocableList.erase(nd.rnuItr);
+ nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
+ }
}
+ }
+ private:
- };
+ NodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
+ return getSolver().getHeuristicNodeData(nItr);
+ }
- class EdgeData {
- private:
+ EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
+ return getSolver().getHeuristicEdgeData(eItr);
+ }
- typedef std::vector<unsigned> UnsafeArray;
+ // Work out what this edge will contribute to the allocability of the
+ // nodes connected to it.
+ void computeEdgeContributions(Graph::EdgeItr eItr) {
+ EdgeData &ed = getHeuristicEdgeData(eItr);
- unsigned worstDegree,
- reverseWorstDegree;
- UnsafeArray unsafe, reverseUnsafe;
+ if (ed.isUpToDate)
+ return; // Edge data is already up to date.
- public:
+ Matrix &eCosts = getGraph().getEdgeCosts(eItr);
- EdgeData() : worstDegree(0), reverseWorstDegree(0) {}
+ unsigned numRegs = eCosts.getRows() - 1,
+ numReverseRegs = eCosts.getCols() - 1;
- typedef UnsafeArray::const_iterator ConstUnsafeIterator;
+ std::vector<unsigned> rowInfCounts(numRegs, 0),
+ colInfCounts(numReverseRegs, 0);
- void setup(SolverGraph &g, const GraphEdgeIterator &edgeItr) {
- const Matrix &edgeCosts = g.getEdgeCosts(edgeItr);
- unsigned numRegs = edgeCosts.getRows() - 1,
- numReverseRegs = edgeCosts.getCols() - 1;
+ ed.worst = 0;
+ ed.reverseWorst = 0;
+ ed.unsafe.clear();
+ ed.unsafe.resize(numRegs, 0);
+ ed.reverseUnsafe.clear();
+ ed.reverseUnsafe.resize(numReverseRegs, 0);
- unsafe.resize(numRegs, 0);
- reverseUnsafe.resize(numReverseRegs, 0);
+ for (unsigned i = 0; i < numRegs; ++i) {
+ for (unsigned j = 0; j < numReverseRegs; ++j) {
+ if (eCosts[i + 1][j + 1] ==
+ std::numeric_limits<PBQPNum>::infinity()) {
+ ed.unsafe[i] = 1;
+ ed.reverseUnsafe[j] = 1;
+ ++rowInfCounts[i];
+ ++colInfCounts[j];
- std::vector<unsigned> rowInfCounts(numRegs, 0),
- colInfCounts(numReverseRegs, 0);
+ if (colInfCounts[j] > ed.worst) {
+ ed.worst = colInfCounts[j];
+ }
- for (unsigned i = 0; i < numRegs; ++i) {
- for (unsigned j = 0; j < numReverseRegs; ++j) {
- if (edgeCosts[i + 1][j + 1] ==
- std::numeric_limits<PBQPNum>::infinity()) {
- unsafe[i] = 1;
- reverseUnsafe[j] = 1;
- ++rowInfCounts[i];
- ++colInfCounts[j];
-
- if (colInfCounts[j] > worstDegree) {
- worstDegree = colInfCounts[j];
- }
-
- if (rowInfCounts[i] > reverseWorstDegree) {
- reverseWorstDegree = rowInfCounts[i];
- }
+ if (rowInfCounts[i] > ed.reverseWorst) {
+ ed.reverseWorst = rowInfCounts[i];
}
}
}
}
- unsigned getWorstDegree() const { return worstDegree; }
- unsigned getReverseWorstDegree() const { return reverseWorstDegree; }
- ConstUnsafeIterator unsafeBegin() const { return unsafe.begin(); }
- ConstUnsafeIterator unsafeEnd() const { return unsafe.end(); }
- ConstUnsafeIterator reverseUnsafeBegin() const {
- return reverseUnsafe.begin();
+ ed.isUpToDate = true;
+ }
+
+ // Add the contributions of the given edge to the given node's
+ // numDenied and safe members. No action is taken other than to update
+ // these member values. Once updated these numbers can be used by clients
+ // to update the node's allocability.
+ void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
+ EdgeData &ed = getHeuristicEdgeData(eItr);
+
+ assert(ed.isUpToDate && "Using out-of-date edge numbers.");
+
+ NodeData &nd = getHeuristicNodeData(nItr);
+ unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
+
+ bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
+ EdgeData::UnsafeArray &unsafe =
+ nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
+ nd.numDenied += nIsNode1 ? ed.worst : ed.reverseWorst;
+
+ for (unsigned r = 0; r < numRegs; ++r) {
+ if (unsafe[r]) {
+ if (nd.unsafeDegrees[r]==0) {
+ --nd.numSafe;
+ }
+ ++nd.unsafeDegrees[r];
+ }
}
- ConstUnsafeIterator reverseUnsafeEnd() const {
- return reverseUnsafe.end();
+ }
+
+ // Subtract the contributions of the given edge to the given node's
+ // numDenied and safe members. No action is taken other than to update
+ // these member values. Once updated these numbers can be used by clients
+ // to update the node's allocability.
+ void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
+ EdgeData &ed = getHeuristicEdgeData(eItr);
+
+ assert(ed.isUpToDate && "Using out-of-date edge numbers.");
+
+ NodeData &nd = getHeuristicNodeData(nItr);
+ unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
+
+ bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
+ EdgeData::UnsafeArray &unsafe =
+ nIsNode1 ? ed.unsafe : ed.reverseUnsafe;
+ nd.numDenied -= nIsNode1 ? ed.worst : ed.reverseWorst;
+
+ for (unsigned r = 0; r < numRegs; ++r) {
+ if (unsafe[r]) {
+ if (nd.unsafeDegrees[r] == 1) {
+ ++nd.numSafe;
+ }
+ --nd.unsafeDegrees[r];
+ }
}
- };
-
- void initialise(Solver &solver) {
- this->s = &solver;
- g = &s->getGraph();
- rNAllocableBucket = RNAllocableNodeList(LinkDegreeComparator(g));
- rNUnallocableBucket =
- RNUnallocableNodeList(SpillPriorityComparator(g));
-
- for (GraphEdgeIterator
- edgeItr = g->edgesBegin(), edgeEnd = g->edgesEnd();
- edgeItr != edgeEnd; ++edgeItr) {
-
- g->getEdgeData(edgeItr).getHeuristicData().setup(*g, edgeItr);
- }
-
- for (GraphNodeIterator
- nodeItr = g->nodesBegin(), nodeEnd = g->nodesEnd();
- nodeItr != nodeEnd; ++nodeItr) {
-
- g->getNodeData(nodeItr).getHeuristicData().setup(*g, nodeItr);
- }
- }
-
- void addToRNBucket(const GraphNodeIterator &nodeItr) {
- NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
-
- if (nodeData.isAllocable()) {
- nodeData.setRNAllocableNodeListItr(
- rNAllocableBucket.insert(rNAllocableBucket.begin(), nodeItr));
- }
- else {
- nodeData.setRNUnallocableNodeListItr(
- rNUnallocableBucket.insert(rNUnallocableBucket.begin(), nodeItr));
- }
- }
+ }
- void removeFromRNBucket(const GraphNodeIterator &nodeItr) {
- NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
-
- if (nodeData.isAllocable()) {
- rNAllocableBucket.erase(nodeData.getRNAllocableNodeListItr());
- }
- else {
- rNUnallocableBucket.erase(nodeData.getRNUnallocableNodeListItr());
- }
- }
+ void updateAllocability(Graph::NodeItr nItr) {
+ NodeData &nd = getHeuristicNodeData(nItr);
+ unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
+ nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0;
+ }
- void handleAddLink(const GraphEdgeIterator &edgeItr) {
- // We assume that if we got here this edge is attached to at least
- // one high degree node.
- g->getEdgeData(edgeItr).getHeuristicData().setup(*g, edgeItr);
-
- GraphNodeIterator n1Itr = g->getEdgeNode1Itr(edgeItr),
- n2Itr = g->getEdgeNode2Itr(edgeItr);
-
- HSIT::NodeData &n1Data = g->getNodeData(n1Itr),
- &n2Data = g->getNodeData(n2Itr);
-
- if (n1Data.getLinkDegree() > 2) {
- n1Data.getHeuristicData().handleAddLink(*g, n1Itr, edgeItr);
- }
- if (n2Data.getLinkDegree() > 2) {
- n2Data.getHeuristicData().handleAddLink(*g, n2Itr, edgeItr);
- }
- }
+ void initializeNode(Graph::NodeItr nItr) {
+ NodeData &nd = getHeuristicNodeData(nItr);
- void handleRemoveLink(const GraphEdgeIterator &edgeItr,
- const GraphNodeIterator &nodeItr) {
- NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData();
- nodeData.handleRemoveLink(*g, nodeItr, edgeItr);
- }
+ if (nd.isInitialized)
+ return; // Node data is already up to date.
- void processRN() {
-
- if (!rNAllocableBucket.empty()) {
- GraphNodeIterator selectedNodeItr = *rNAllocableBucket.begin();
- //std::cerr << "RN safely pushing " << g->getNodeID(selectedNodeItr) << "\n";
- rNAllocableBucket.erase(rNAllocableBucket.begin());
- s->pushStack(selectedNodeItr);
- s->unlinkNode(selectedNodeItr);
- }
- else {
- GraphNodeIterator selectedNodeItr = *rNUnallocableBucket.begin();
- //std::cerr << "RN optimistically pushing " << g->getNodeID(selectedNodeItr) << "\n";
- rNUnallocableBucket.erase(rNUnallocableBucket.begin());
- s->pushStack(selectedNodeItr);
- s->unlinkNode(selectedNodeItr);
- }
-
- }
+ unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
- bool rNBucketEmpty() const {
- return (rNAllocableBucket.empty() && rNUnallocableBucket.empty());
- }
+ nd.numDenied = 0;
+ nd.numSafe = numRegs;
+ nd.unsafeDegrees.resize(numRegs, 0);
-private:
+ typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
- Solver *s;
- SolverGraph *g;
- RNAllocableNodeList rNAllocableBucket;
- RNUnallocableNodeList rNUnallocableBucket;
-};
+ for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr),
+ aeEnd = getSolver().solverEdgesEnd(nItr);
+ aeItr != aeEnd; ++aeItr) {
+
+ Graph::EdgeItr eItr = *aeItr;
+ computeEdgeContributions(eItr);
+ addEdgeContributions(eItr, nItr);
+ }
+ updateAllocability(nItr);
+ nd.isInitialized = true;
+ }
+
+ void handleRemoveNode(Graph::NodeItr xnItr) {
+ typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
+ std::vector<Graph::EdgeItr> edgesToRemove;
+ for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr),
+ aeEnd = getSolver().solverEdgesEnd(xnItr);
+ aeItr != aeEnd; ++aeItr) {
+ Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr);
+ handleRemoveEdge(*aeItr, ynItr);
+ edgesToRemove.push_back(*aeItr);
+ }
+ while (!edgesToRemove.empty()) {
+ getSolver().removeSolverEdge(edgesToRemove.back());
+ edgesToRemove.pop_back();
+ }
+ }
+ RNAllocableList rnAllocableList;
+ RNUnallocableList rnUnallocableList;
+ };
-}
+ }
}
--- /dev/null
+//===------ Math.h - PBQP Vector and Matrix classes -------------*- C++ -*-===//
+//
+// The LLVM Compiler Infrastructure
+//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+//===----------------------------------------------------------------------===//
+
+#ifndef LLVM_CODEGEN_PBQP_MATH_H
+#define LLVM_CODEGEN_PBQP_MATH_H
+
+#include <cassert>
+#include <algorithm>
+#include <functional>
+
+namespace PBQP {
+
+typedef float PBQPNum;
+
+/// \brief PBQP Vector class.
+class Vector {
+ public:
+
+ /// \brief Construct a PBQP vector of the given size.
+ explicit Vector(unsigned length) :
+ length(length), data(new PBQPNum[length]) {
+ }
+
+ /// \brief Construct a PBQP vector with initializer.
+ Vector(unsigned length, PBQPNum initVal) :
+ length(length), data(new PBQPNum[length]) {
+ std::fill(data, data + length, initVal);
+ }
+
+ /// \brief Copy construct a PBQP vector.
+ Vector(const Vector &v) :
+ length(v.length), data(new PBQPNum[length]) {
+ std::copy(v.data, v.data + length, data);
+ }
+
+ /// \brief Destroy this vector, return its memory.
+ ~Vector() { delete[] data; }
+
+ /// \brief Assignment operator.
+ Vector& operator=(const Vector &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 {
+ return length;
+ }
+
+ /// \brief Element access.
+ PBQPNum& operator[](unsigned index) {
+ assert(index < length && "Vector element access out of bounds.");
+ return data[index];
+ }
+
+ /// \brief Const element access.
+ const PBQPNum& operator[](unsigned index) const {
+ assert(index < length && "Vector element access out of bounds.");
+ return data[index];
+ }
+
+ /// \brief Add another vector to this one.
+ Vector& operator+=(const Vector &v) {
+ assert(length == v.length && "Vector length mismatch.");
+ std::transform(data, data + length, v.data, data, std::plus<PBQPNum>());
+ return *this;
+ }
+
+ /// \brief Subtract another vector from this one.
+ Vector& operator-=(const Vector &v) {
+ assert(length == v.length && "Vector 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 Output a textual representation of the given vector on the given
+/// output stream.
+template <typename OStream>
+OStream& operator<<(OStream &os, const Vector &v) {
+ assert((v.getLength() != 0) && "Zero-length vector badness.");
+
+ os << "[ " << v[0];
+ for (unsigned i = 1; i < v.getLength(); ++i) {
+ os << ", " << v[i];
+ }
+ os << " ]";
+
+ return os;
+}
+
+
+/// \brief PBQP Matrix class
+class Matrix {
+ public:
+
+ /// \brief Construct a PBQP Matrix with the given dimensions.
+ Matrix(unsigned rows, unsigned cols) :
+ rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
+ }
+
+ /// \brief Construct a PBQP Matrix with the given dimensions and initial
+ /// value.
+ Matrix(unsigned rows, unsigned cols, PBQPNum initVal) :
+ rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
+ std::fill(data, data + (rows * cols), initVal);
+ }
+
+ /// \brief Copy construct a PBQP matrix.
+ Matrix(const Matrix &m) :
+ rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) {
+ std::copy(m.data, m.data + (rows * cols), data);
+ }
+
+ /// \brief Destroy this matrix, return its memory.
+ ~Matrix() { delete[] data; }
+
+ /// \brief Assignment operator.
+ Matrix& operator=(const Matrix &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 { return rows; }
+
+ /// \brief Return the number of cols in this matrix.
+ unsigned getCols() const { 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.
+ Vector getRowAsVector(unsigned r) const {
+ Vector v(cols);
+ for (unsigned c = 0; c < cols; ++c)
+ v[c] = (*this)[r][c];
+ return v;
+ }
+
+ /// \brief Returns the given column as a vector.
+ Vector getColAsVector(unsigned c) const {
+ Vector v(rows);
+ for (unsigned r = 0; r < rows; ++r)
+ v[r] = (*this)[r][c];
+ return v;
+ }
+
+ /// \brief Reset the matrix to the given value.
+ Matrix& 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.
+ Matrix& 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.
+ Matrix& 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.
+ Matrix transpose() const {
+ Matrix 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.
+ Vector diagonalize() const {
+ assert(rows == cols && "Attempt to diagonalize non-square matrix.");
+
+ Vector v(rows);
+ for (unsigned r = 0; r < rows; ++r)
+ v[r] = (*this)[r][r];
+ return v;
+ }
+
+ /// \brief Add the given matrix to this one.
+ Matrix& operator+=(const Matrix &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.
+ Matrix& 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.
+ Matrix& 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;
+};
+
+/// \brief Output a textual representation of the given matrix on the given
+/// output stream.
+template <typename OStream>
+OStream& operator<<(OStream &os, const Matrix &m) {
+
+ assert((m.getRows() != 0) && "Zero-row matrix badness.");
+
+ for (unsigned i = 0; i < m.getRows(); ++i) {
+ os << m.getRowAsVector(i);
+ }
+
+ return os;
+}
+
+}
+
+#endif // LLVM_CODEGEN_PBQP_MATH_H
+++ /dev/null
-//===-- PBQPMath.h - PBQP Vector and Matrix classes -------------*- C++ -*-===//
-//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_PBQP_PBQPMATH_H
-#define LLVM_CODEGEN_PBQP_PBQPMATH_H
-
-#include <cassert>
-#include <algorithm>
-#include <functional>
-
-namespace PBQP {
-
-typedef double PBQPNum;
-
-/// \brief PBQP Vector class.
-class Vector {
- public:
-
- /// \brief Construct a PBQP vector of the given size.
- explicit Vector(unsigned length) :
- length(length), data(new PBQPNum[length]) {
- }
-
- /// \brief Construct a PBQP vector with initializer.
- Vector(unsigned length, PBQPNum initVal) :
- length(length), data(new PBQPNum[length]) {
- std::fill(data, data + length, initVal);
- }
-
- /// \brief Copy construct a PBQP vector.
- Vector(const Vector &v) :
- length(v.length), data(new PBQPNum[length]) {
- std::copy(v.data, v.data + length, data);
- }
-
- /// \brief Destroy this vector, return its memory.
- ~Vector() { delete[] data; }
-
- /// \brief Assignment operator.
- Vector& operator=(const Vector &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 {
- return length;
- }
-
- /// \brief Element access.
- PBQPNum& operator[](unsigned index) {
- assert(index < length && "Vector element access out of bounds.");
- return data[index];
- }
-
- /// \brief Const element access.
- const PBQPNum& operator[](unsigned index) const {
- assert(index < length && "Vector element access out of bounds.");
- return data[index];
- }
-
- /// \brief Add another vector to this one.
- Vector& operator+=(const Vector &v) {
- assert(length == v.length && "Vector length mismatch.");
- std::transform(data, data + length, v.data, data, std::plus<PBQPNum>());
- return *this;
- }
-
- /// \brief Subtract another vector from this one.
- Vector& operator-=(const Vector &v) {
- assert(length == v.length && "Vector 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 Output a textual representation of the given vector on the given
-/// output stream.
-template <typename OStream>
-OStream& operator<<(OStream &os, const Vector &v) {
- assert((v.getLength() != 0) && "Zero-length vector badness.");
-
- os << "[ " << v[0];
- for (unsigned i = 1; i < v.getLength(); ++i) {
- os << ", " << v[i];
- }
- os << " ]";
-
- return os;
-}
-
-
-/// \brief PBQP Matrix class
-class Matrix {
- public:
-
- /// \brief Construct a PBQP Matrix with the given dimensions.
- Matrix(unsigned rows, unsigned cols) :
- rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
- }
-
- /// \brief Construct a PBQP Matrix with the given dimensions and initial
- /// value.
- Matrix(unsigned rows, unsigned cols, PBQPNum initVal) :
- rows(rows), cols(cols), data(new PBQPNum[rows * cols]) {
- std::fill(data, data + (rows * cols), initVal);
- }
-
- /// \brief Copy construct a PBQP matrix.
- Matrix(const Matrix &m) :
- rows(m.rows), cols(m.cols), data(new PBQPNum[rows * cols]) {
- std::copy(m.data, m.data + (rows * cols), data);
- }
-
- /// \brief Destroy this matrix, return its memory.
- ~Matrix() { delete[] data; }
-
- /// \brief Assignment operator.
- Matrix& operator=(const Matrix &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 { return rows; }
-
- /// \brief Return the number of cols in this matrix.
- unsigned getCols() const { 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.
- Vector getRowAsVector(unsigned r) const {
- Vector v(cols);
- for (unsigned c = 0; c < cols; ++c)
- v[c] = (*this)[r][c];
- return v;
- }
-
- /// \brief Returns the given column as a vector.
- Vector getColAsVector(unsigned c) const {
- Vector v(rows);
- for (unsigned r = 0; r < rows; ++r)
- v[r] = (*this)[r][c];
- return v;
- }
-
- /// \brief Reset the matrix to the given value.
- Matrix& 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.
- Matrix& 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.
- Matrix& 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.
- Matrix transpose() const {
- Matrix 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.
- Vector diagonalize() const {
- assert(rows == cols && "Attempt to diagonalize non-square matrix.");
-
- Vector v(rows);
- for (unsigned r = 0; r < rows; ++r)
- v[r] = (*this)[r][r];
- return v;
- }
-
- /// \brief Add the given matrix to this one.
- Matrix& operator+=(const Matrix &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.
- Matrix& 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.
- Matrix& 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;
-};
-
-/// \brief Output a textual representation of the given matrix on the given
-/// output stream.
-template <typename OStream>
-OStream& operator<<(OStream &os, const Matrix &m) {
-
- assert((m.getRows() != 0) && "Zero-row matrix badness.");
-
- for (unsigned i = 0; i < m.getRows(); ++i) {
- os << m.getRowAsVector(i);
- }
-
- return os;
-}
-
-}
-
-#endif // LLVM_CODEGEN_PBQP_PBQPMATH_HPP
+++ /dev/null
-//===-- SimpleGraph.h - Simple PBQP Graph -----------------------*- C++ -*-===//
-//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-//
-// Simple PBQP graph class representing a PBQP problem. Graphs of this type
-// can be passed to a PBQPSolver instance to solve the PBQP problem.
-//
-//===----------------------------------------------------------------------===//
-
-#ifndef LLVM_CODEGEN_PBQP_SIMPLEGRAPH_H
-#define LLVM_CODEGEN_PBQP_SIMPLEGRAPH_H
-
-#include "GraphBase.h"
-
-namespace PBQP {
-
-class SimpleEdge;
-
-class SimpleNode : public NodeBase<SimpleNode, SimpleEdge> {
-public:
- SimpleNode(const Vector &costs) :
- NodeBase<SimpleNode, SimpleEdge>(costs) {}
-};
-
-class SimpleEdge : public EdgeBase<SimpleNode, SimpleEdge> {
-public:
- SimpleEdge(const NodeIterator &node1Itr, const NodeIterator &node2Itr,
- const Matrix &costs) :
- EdgeBase<SimpleNode, SimpleEdge>(node1Itr, node2Itr, costs) {}
-};
-
-class SimpleGraph : public GraphBase<SimpleNode, SimpleEdge> {
-private:
-
- typedef GraphBase<SimpleNode, SimpleEdge> PGraph;
-
- void copyFrom(const SimpleGraph &other) {
- assert(other.areNodeIDsValid() &&
- "Cannot copy from another graph unless IDs have been assigned.");
-
- std::vector<NodeIterator> newNodeItrs(other.getNumNodes());
-
- for (ConstNodeIterator nItr = other.nodesBegin(), nEnd = other.nodesEnd();
- nItr != nEnd; ++nItr) {
- newNodeItrs[other.getNodeID(nItr)] = addNode(other.getNodeCosts(nItr));
- }
-
- for (ConstEdgeIterator eItr = other.edgesBegin(), eEnd = other.edgesEnd();
- eItr != eEnd; ++eItr) {
-
- unsigned node1ID = other.getNodeID(other.getEdgeNode1Itr(eItr)),
- node2ID = other.getNodeID(other.getEdgeNode2Itr(eItr));
-
- addEdge(newNodeItrs[node1ID], newNodeItrs[node2ID],
- other.getEdgeCosts(eItr));
- }
- }
-
- void copyFrom(SimpleGraph &other) {
- if (!other.areNodeIDsValid()) {
- other.assignNodeIDs();
- }
- copyFrom(const_cast<const SimpleGraph&>(other));
- }
-
-public:
-
- SimpleGraph() {}
-
-
- SimpleGraph(const SimpleGraph &other) : PGraph() {
- copyFrom(other);
- }
-
- SimpleGraph& operator=(const SimpleGraph &other) {
- clear();
- copyFrom(other);
- return *this;
- }
-
- NodeIterator addNode(const Vector &costs) {
- return PGraph::addConstructedNode(SimpleNode(costs));
- }
-
- EdgeIterator addEdge(const NodeIterator &node1Itr,
- const NodeIterator &node2Itr,
- const Matrix &costs) {
- return PGraph::addConstructedEdge(SimpleEdge(node1Itr, node2Itr, costs));
- }
-
-};
-
-}
-
-#endif // LLVM_CODEGEN_PBQP_SIMPLEGRAPH_H
//
//===----------------------------------------------------------------------===//
//
-// Annotated PBQP Graph class. This class is used internally by the PBQP solver
-// to cache information to speed up reduction.
+// PBQP Solution class.
//
//===----------------------------------------------------------------------===//
#ifndef LLVM_CODEGEN_PBQP_SOLUTION_H
#define LLVM_CODEGEN_PBQP_SOLUTION_H
-#include "PBQPMath.h"
+#include "Math.h"
+#include "Graph.h"
-namespace PBQP {
-
-class Solution {
-
- friend class SolverImplementation;
-
-private:
-
- std::vector<unsigned> selections;
- PBQPNum solutionCost;
- bool provedOptimal;
- unsigned r0Reductions, r1Reductions,
- r2Reductions, rNReductions;
-
-public:
-
- Solution() :
- solutionCost(0.0), provedOptimal(false),
- r0Reductions(0), r1Reductions(0), r2Reductions(0), rNReductions(0) {}
-
- Solution(unsigned length, bool assumeOptimal) :
- selections(length), solutionCost(0.0), provedOptimal(assumeOptimal),
- r0Reductions(0), r1Reductions(0), r2Reductions(0), rNReductions(0) {}
-
- void setProvedOptimal(bool provedOptimal) {
- this->provedOptimal = provedOptimal;
- }
-
- void setSelection(unsigned nodeID, unsigned selection) {
- selections[nodeID] = selection;
- }
+#include <map>
- void setSolutionCost(PBQPNum solutionCost) {
- this->solutionCost = solutionCost;
- }
-
- void incR0Reductions() { ++r0Reductions; }
- void incR1Reductions() { ++r1Reductions; }
- void incR2Reductions() { ++r2Reductions; }
- void incRNReductions() { ++rNReductions; }
-
- unsigned numNodes() const { return selections.size(); }
-
- unsigned getSelection(unsigned nodeID) const {
- return selections[nodeID];
- }
-
- PBQPNum getCost() const { return solutionCost; }
-
- bool isProvedOptimal() const { return provedOptimal; }
-
- unsigned getR0Reductions() const { return r0Reductions; }
- unsigned getR1Reductions() const { return r1Reductions; }
- unsigned getR2Reductions() const { return r2Reductions; }
- unsigned getRNReductions() const { return rNReductions; }
-
- bool operator==(const Solution &other) const {
- return (selections == other.selections);
- }
-
- bool operator!=(const Solution &other) const {
- return !(*this == other);
- }
+namespace PBQP {
-};
+ /// \brief Represents a solution to a PBQP problem.
+ ///
+ /// To get the selection for each node in the problem use the getSelection method.
+ class Solution {
+ private:
+ typedef std::map<Graph::NodeItr, unsigned, NodeItrComparator> SelectionsMap;
+ SelectionsMap selections;
+
+ public:
+
+ /// \brief Number of nodes for which selections have been made.
+ /// @return Number of nodes for which selections have been made.
+ unsigned numNodes() const { return selections.size(); }
+
+ /// \brief Set the selection for a given node.
+ /// @param nItr Node iterator.
+ /// @param selection Selection for nItr.
+ void setSelection(Graph::NodeItr nItr, unsigned selection) {
+ selections[nItr] = selection;
+ }
+
+ /// \brief Get a node's selection.
+ /// @param nItr Node iterator.
+ /// @return The selection for nItr;
+ unsigned getSelection(Graph::NodeItr nItr) const {
+ SelectionsMap::const_iterator sItr = selections.find(nItr);
+ assert(sItr != selections.end() && "No selection for node.");
+ return sItr->second;
+ }
+
+ };
}
+++ /dev/null
-//===-- Solver.h ------- PBQP solver interface ------------------*- C++ -*-===//
-//
-// The LLVM Compiler Infrastructure
-//
-// This file is distributed under the University of Illinois Open Source
-// License. See LICENSE.TXT for details.
-//
-//===----------------------------------------------------------------------===//
-
-
-#ifndef LLVM_CODEGEN_PBQP_SOLVER_H
-#define LLVM_CODEGEN_PBQP_SOLVER_H
-
-#include "SimpleGraph.h"
-#include "Solution.h"
-
-namespace PBQP {
-
-/// \brief Interface for solver classes.
-class Solver {
-public:
-
- virtual ~Solver() = 0;
- virtual Solution solve(const SimpleGraph &orig) const = 0;
-};
-
-Solver::~Solver() {}
-
-}
-
-#endif // LLVM_CODEGEN_PBQP_SOLVER_H
#define DEBUG_TYPE "regalloc"
#include "PBQP/HeuristicSolver.h"
-#include "PBQP/SimpleGraph.h"
+#include "PBQP/Graph.h"
#include "PBQP/Heuristics/Briggs.h"
#include "VirtRegMap.h"
#include "VirtRegRewriter.h"
static RegisterRegAlloc
registerPBQPRepAlloc("pbqp", "PBQP register allocator.",
- llvm::createPBQPRegisterAllocator);
+ llvm::createPBQPRegisterAllocator);
static cl::opt<bool>
pbqpCoalescing("pbqp-coalescing",
- cl::desc("Attempt coalescing during PBQP register allocation."),
- cl::init(false), cl::Hidden);
+ cl::desc("Attempt coalescing during PBQP register allocation."),
+ cl::init(false), cl::Hidden);
namespace {
typedef std::set<LiveInterval*> LiveIntervalSet;
+ typedef std::vector<PBQP::Graph::NodeItr> NodeVector;
+
MachineFunction *mf;
const TargetMachine *tm;
const TargetRegisterInfo *tri;
AllowedSetMap allowedSets;
LiveIntervalSet vregIntervalsToAlloc,
emptyVRegIntervals;
+ NodeVector problemNodes;
/// Builds a PBQP cost vector.
/// allocation problem for this function.
///
/// @return a PBQP solver object for the register allocation problem.
- PBQP::SimpleGraph constructPBQPProblem();
+ PBQP::Graph constructPBQPProblem();
/// \brief Adds a stack interval if the given live interval has been
/// spilled. Used to support stack slot coloring.
}
}
-PBQP::SimpleGraph PBQPRegAlloc::constructPBQPProblem() {
+PBQP::Graph PBQPRegAlloc::constructPBQPProblem() {
typedef std::vector<const LiveInterval*> LIVector;
typedef std::vector<unsigned> RegVector;
- typedef std::vector<PBQP::SimpleGraph::NodeIterator> NodeVector;
// This will store the physical intervals for easy reference.
LIVector physIntervals;
}
// Construct a PBQP solver for this problem
- PBQP::SimpleGraph problem;
- NodeVector problemNodes(vregIntervalsToAlloc.size());
+ PBQP::Graph problem;
+ problemNodes.resize(vregIntervalsToAlloc.size());
// Resize allowedSets container appropriately.
allowedSets.resize(vregIntervalsToAlloc.size());
}
}
- problem.assignNodeIDs();
-
assert(problem.getNumNodes() == allowedSets.size());
- for (unsigned i = 0; i < allowedSets.size(); ++i) {
- assert(problem.getNodeItr(i) == problemNodes[i]);
- }
/*
std::cerr << "Allocating for " << problem.getNumNodes() << " nodes, "
<< problem.getNumEdges() << " edges.\n";
bool PBQPRegAlloc::mapPBQPToRegAlloc(const PBQP::Solution &solution) {
- // Assert that this is a valid solution to the regalloc problem.
- assert(solution.getCost() != std::numeric_limits<PBQP::PBQPNum>::infinity() &&
- "Invalid (infinite cost) solution for PBQP problem.");
-
// Set to true if we have any spills
bool anotherRoundNeeded = false;
// Iterate over the nodes mapping the PBQP solution to a register assignment.
for (unsigned node = 0; node < node2LI.size(); ++node) {
unsigned virtReg = node2LI[node]->reg,
- allocSelection = solution.getSelection(node);
+ allocSelection = solution.getSelection(problemNodes[node]);
// If the PBQP solution is non-zero it's a physical register...
vrm = &getAnalysis<VirtRegMap>();
- DEBUG(dbgs() << "PBQP2 Register Allocating for " << mf->getFunction()->getName() << "\n");
+ DEBUG(dbgs() << "PBQP Register Allocating for " << mf->getFunction()->getName() << "\n");
// Allocator main loop:
//
while (!pbqpAllocComplete) {
DEBUG(dbgs() << " PBQP Regalloc round " << round << ":\n");
- PBQP::SimpleGraph problem = constructPBQPProblem();
- PBQP::HeuristicSolver<PBQP::Heuristics::Briggs> solver;
- problem.assignNodeIDs();
- PBQP::Solution solution = solver.solve(problem);
+ PBQP::Graph problem = constructPBQPProblem();
+ PBQP::Solution solution =
+ PBQP::HeuristicSolver<PBQP::Heuristics::Briggs>::solve(problem);
pbqpAllocComplete = mapPBQPToRegAlloc(solution);
li2Node.clear();
node2LI.clear();
allowedSets.clear();
+ problemNodes.clear();
DEBUG(dbgs() << "Post alloc VirtRegMap:\n" << *vrm << "\n");
projects / oota-llvm.git / commitdiff