diff options
Diffstat (limited to 'lib/CodeGen/PBQP')
-rw-r--r-- | lib/CodeGen/PBQP/AnnotatedGraph.h | 184 | ||||
-rw-r--r-- | lib/CodeGen/PBQP/ExhaustiveSolver.h | 110 | ||||
-rw-r--r-- | lib/CodeGen/PBQP/GraphBase.h | 582 | ||||
-rw-r--r-- | lib/CodeGen/PBQP/HeuristicSolver.h | 789 | ||||
-rw-r--r-- | lib/CodeGen/PBQP/Heuristics/Briggs.h | 383 | ||||
-rw-r--r-- | lib/CodeGen/PBQP/PBQPMath.h | 288 | ||||
-rw-r--r-- | lib/CodeGen/PBQP/SimpleGraph.h | 100 | ||||
-rw-r--r-- | lib/CodeGen/PBQP/Solution.h | 88 | ||||
-rw-r--r-- | lib/CodeGen/PBQP/Solver.h | 31 |
9 files changed, 2555 insertions, 0 deletions
diff --git a/lib/CodeGen/PBQP/AnnotatedGraph.h b/lib/CodeGen/PBQP/AnnotatedGraph.h new file mode 100644 index 0000000..904061c --- /dev/null +++ b/lib/CodeGen/PBQP/AnnotatedGraph.h @@ -0,0 +1,184 @@ +//===-- 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 getNodeEntry(nodeItr).getNodeData(); + } + + const NodeData& getNodeData(const NodeIterator &nodeItr) const { + return getNodeEntry(nodeItr).getNodeData(); + } + + EdgeData& getEdgeData(const EdgeIterator &edgeItr) { + return getEdgeEntry(edgeItr).getEdgeData(); + } + + const EdgeEntry& getEdgeData(const EdgeIterator &edgeItr) const { + return 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 diff --git a/lib/CodeGen/PBQP/ExhaustiveSolver.h b/lib/CodeGen/PBQP/ExhaustiveSolver.h new file mode 100644 index 0000000..b2f2e6f --- /dev/null +++ b/lib/CodeGen/PBQP/ExhaustiveSolver.h @@ -0,0 +1,110 @@ +//===-- 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 diff --git a/lib/CodeGen/PBQP/GraphBase.h b/lib/CodeGen/PBQP/GraphBase.h new file mode 100644 index 0000000..cc3e017 --- /dev/null +++ b/lib/CodeGen/PBQP/GraphBase.h @@ -0,0 +1,582 @@ +//===-- 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 != adjEdgesEnd; ++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 diff --git a/lib/CodeGen/PBQP/HeuristicSolver.h b/lib/CodeGen/PBQP/HeuristicSolver.h new file mode 100644 index 0000000..e786246 --- /dev/null +++ b/lib/CodeGen/PBQP/HeuristicSolver.h @@ -0,0 +1,789 @@ +//===-- HeuristicSolver.h - Heuristic PBQP Solver --------------*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// Heuristic PBQP solver. This solver is able to perform optimal reductions for +// nodes of degree 0, 1 or 2. For nodes of degree >2 a plugable heuristic is +// used to to select a node for reduction. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H +#define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H + +#include "Solver.h" +#include "AnnotatedGraph.h" +#include "llvm/Support/raw_ostream.h" +#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; + + private: + + typedef std::list<GraphEdgeIterator> LinksList; + + unsigned numLinks; + LinksList links, solvedLinks; + NodeListIterator bucketItr; + HeuristicNodeData heuristicData; + + public: + + typedef typename LinksList::iterator AdjLinkIterator; + + private: + + AdjLinkIterator addLink(const GraphEdgeIterator &edgeItr) { + ++numLinks; + return links.insert(links.end(), edgeItr); + } + + void delLink(const AdjLinkIterator &adjLinkItr) { + --numLinks; + links.erase(adjLinkItr); + } + + 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; + } + + const NodeListIterator& getBucketItr() const { + return bucketItr; + } + + AdjLinkIterator adjLinksBegin() { + return links.begin(); + } + + AdjLinkIterator adjLinksEnd() { + return links.end(); + } + + void addSolvedLink(const GraphEdgeIterator &solvedLinkItr) { + solvedLinks.push_back(solvedLinkItr); + } + + AdjLinkIterator solvedLinksBegin() { + return solvedLinks.begin(); + } + + AdjLinkIterator solvedLinksEnd() { + return solvedLinks.end(); + } + + }; + + class EdgeData { + private: + + SolverGraph &g; + GraphNodeIterator node1Itr, node2Itr; + HeuristicEdgeData heuristicData; + typename NodeData::AdjLinkIterator node1ThisEdgeItr, node2ThisEdgeItr; + + 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); + } + 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)); + + 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); + } + } + +private: + + SolverGraph g; + Heuristic heuristic; + Solution solution; + + NodeList r0Bucket, + r1Bucket, + r2Bucket; + + NodeStack stack; + + // 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())); + } + + for (SimpleGraph::ConstEdgeIterator + origEdgeItr = orig.edgesBegin(), origEdgeEnd = orig.edgesEnd(); + origEdgeItr != origEdgeEnd; ++origEdgeItr) { + + unsigned id1 = orig.getNodeID(orig.getEdgeNode1Itr(origEdgeItr)), + id2 = orig.getNodeID(orig.getEdgeNode2Itr(origEdgeItr)); + + 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(); + } + + // Eliminate trivial nodes. + void disconnectTrivialNodes() { + for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd(); + nodeItr != nodeEnd; ++nodeItr) { + + if (g.getNodeCosts(nodeItr).getLength() == 1) { + + std::vector<GraphEdgeIterator> edgesToRemove; + + for (GraphAdjEdgeIterator adjEdgeItr = g.adjEdgesBegin(nodeItr), + adjEdgeEnd = g.adjEdgesEnd(nodeItr); + adjEdgeItr != adjEdgeEnd; ++adjEdgeItr) { + + GraphEdgeIterator edgeItr = *adjEdgeItr; + + 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); + } + + edgesToRemove.push_back(edgeItr); + } + + while (!edgesToRemove.empty()) { + g.removeEdge(edgesToRemove.back()); + edgesToRemove.pop_back(); + } + } + } + } + + 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)); + + 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); + } + } + + return edgeCosts.isZero(); + } + + void setup() { + setupLinks(); + heuristic.initialise(*this); + setupBuckets(); + } + + void setupLinks() { + for (GraphEdgeIterator edgeItr = g.edgesBegin(), edgeEnd = g.edgesEnd(); + edgeItr != edgeEnd; ++edgeItr) { + g.getEdgeData(edgeItr).setup(edgeItr); + } + } + + 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)) + << ") "; + } + llvm::errs() << "]\n"; + } + + void dumpState() { + llvm::errs() << "\n"; + + for (GraphNodeIterator nodeItr = g.nodesBegin(), nodeEnd = g.nodesEnd(); + nodeItr != nodeEnd; ++nodeItr) { + printNode(nodeItr); + } + + 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) << " "; + } + + 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) { + + if (!r1Bucket.empty()) { + processR1(); + } + else if (!r2Bucket.empty()) { + processR2(); + } + 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; + } + } + 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; + } + } + + unlinkNode(xNodeItr); + pushStack(xNodeItr); + } + + void processR2() { + + GraphNodeIterator xNodeItr = r2Bucket.front(); + r2Bucket.pop_front(); + + 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); + + GraphNodeIterator yNodeItr = g.getEdgeOtherNode(yxEdgeItr, xNodeItr), + zNodeItr = g.getEdgeOtherNode(zxEdgeItr, xNodeItr); + + removeFromBucket(yNodeItr); + removeFromBucket(zNodeItr); + + removeLink(yxEdgeItr, yNodeItr); + removeLink(zxEdgeItr, zNodeItr); + + // Graph some of the costs: + bool flipEdge1 = (g.getEdgeNode1Itr(yxEdgeItr) == xNodeItr), + flipEdge2 = (g.getEdgeNode1Itr(zxEdgeItr) == xNodeItr); + + const Matrix *yxCosts = flipEdge1 ? + new Matrix(g.getEdgeCosts(yxEdgeItr).transpose()) : + &g.getEdgeCosts(yxEdgeItr), + *zxCosts = flipEdge2 ? + new Matrix(g.getEdgeCosts(zxEdgeItr).transpose()) : + &g.getEdgeCosts(zxEdgeItr); + + unsigned xLen = xCosts.getLength(), + yLen = yxCosts->getRows(), + zLen = zxCosts->getRows(); + + // Compute delta: + Matrix delta(yLen, zLen); + + 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; + } + } + 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(); + } + + bool nullCostEdge = tryNormaliseEdgeMatrix(yzEdgeItr); + + // Nulled the edge, remove it entirely. + if (nullCostEdge) { + g.removeEdge(yzEdgeItr); + } + else { + // Edge remains - re-link it. + addLink(yzEdgeItr); + } + + addToBucket(yNodeItr); + addToBucket(zNodeItr); + } + + void computeTrivialSolutions() { + + for (NodeListIterator r0Itr = r0Bucket.begin(), r0End = r0Bucket.end(); + r0Itr != r0End; ++r0Itr) { + GraphNodeIterator nodeItr = *r0Itr; + + solution.incR0Reductions(); + setSolution(nodeItr, g.getNodeCosts(nodeItr).minIndex()); + } + + } + + void backpropagate() { + while (!stack.empty()) { + computeSolution(stack.back()); + stack.pop_back(); + } + } + + 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); + } + + } + + setSolution(nodeItr, v.minIndex()); + } + + void computeSolutionCost(const SimpleGraph &orig) { + PBQPNum cost = 0.0; + + for (SimpleGraph::ConstNodeIterator + nodeItr = orig.nodesBegin(), nodeEnd = orig.nodesEnd(); + nodeItr != nodeEnd; ++nodeItr) { + + unsigned nodeId = orig.getNodeID(nodeItr); + + cost += orig.getNodeCosts(nodeItr)[solution.getSelection(nodeId)]; + } + + for (SimpleGraph::ConstEdgeIterator + edgeItr = orig.edgesBegin(), edgeEnd = orig.edgesEnd(); + edgeItr != edgeEnd; ++edgeItr) { + + 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]; + } + + solution.setSolutionCost(cost); + } + +}; + +template <typename Heuristic> +class HeuristicSolver : public Solver { +public: + Solution solve(const SimpleGraph &g) const { + HeuristicSolverImpl<Heuristic> solverImpl(g); + return solverImpl.getSolution(); + } +}; + +} + +#endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H diff --git a/lib/CodeGen/PBQP/Heuristics/Briggs.h b/lib/CodeGen/PBQP/Heuristics/Briggs.h new file mode 100644 index 0000000..3ac9e70 --- /dev/null +++ b/lib/CodeGen/PBQP/Heuristics/Briggs.h @@ -0,0 +1,383 @@ +//===-- Briggs.h --- Briggs Heuristic for PBQP -----------------*- C++ --*-===// +// +// The LLVM Compiler Infrastructure +// +// This file is distributed under the University of Illinois Open Source +// License. See LICENSE.TXT for details. +// +//===----------------------------------------------------------------------===// +// +// This class implements the Briggs test for "allocability" of nodes in a +// PBQP graph representing a register allocation problem. Nodes which can be +// proven allocable (by a safe and relatively accurate test) are removed from +// the PBQP graph first. If no provably allocable node is present in the graph +// then the node with the minimal spill-cost to degree ratio is removed. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H +#define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H + +#include "../HeuristicSolver.h" + +#include <set> + +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 { + 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) { + return true; + } + else if (n1Degree < n2Degree) { + return false; + } + // else they're "equal" by degree, differentiate based on ID. + return g->getNodeID(node1Itr) < g->getNodeID(node2Itr); + } + + private: + SolverGraph *g; + }; + + class SpillPriorityComparator { + 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) { + return true; + } + else if (cost1 > cost2) { + return false; + } + // else they'er "equal" again, differentiate based on address again. + return g->getNodeID(node1Itr) < g->getNodeID(node2Itr); + } + + 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) { + + //assume we're adding... + unsigned udTarget = 0, dir = 1; + + if (!add) { + udTarget = 1; + dir = ~0; + } + + EdgeData &linkEdgeData = g.getEdgeData(edgeItr).getHeuristicData(); + + EdgeData::ConstUnsafeIterator edgeUnsafeBegin, edgeUnsafeEnd; + + 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(); + } + + 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)); + } + + allocable = (numDenied < numRegOptions) || (numSafe > 0); + } + + 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); + } + } + + bool isAllocable() const { return allocable; } + + void handleAddLink(SolverGraph &g, const GraphNodeIterator &nodeItr, + const GraphEdgeIterator &adjEdge) { + addRemoveLink(g, nodeItr, adjEdge, 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; + } + + void setRNUnallocableNodeListItr( + const RNUnallocableNodeListIterator &rNUnallocableNodeListItr) { + + this->rNUnallocableNodeListItr = rNUnallocableNodeListItr; + } + + RNUnallocableNodeListIterator getRNUnallocableNodeListItr() const { + return rNUnallocableNodeListItr; + } + + + }; + + class EdgeData { + private: + + typedef std::vector<unsigned> UnsafeArray; + + unsigned worstDegree, + reverseWorstDegree; + UnsafeArray unsafe, reverseUnsafe; + + public: + + EdgeData() : worstDegree(0), reverseWorstDegree(0) {} + + typedef UnsafeArray::const_iterator ConstUnsafeIterator; + + void setup(SolverGraph &g, const GraphEdgeIterator &edgeItr) { + const Matrix &edgeCosts = g.getEdgeCosts(edgeItr); + unsigned numRegs = edgeCosts.getRows() - 1, + numReverseRegs = edgeCosts.getCols() - 1; + + unsafe.resize(numRegs, 0); + reverseUnsafe.resize(numReverseRegs, 0); + + std::vector<unsigned> rowInfCounts(numRegs, 0), + colInfCounts(numReverseRegs, 0); + + 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]; + } + } + } + } + } + + 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(); + } + ConstUnsafeIterator reverseUnsafeEnd() const { + return reverseUnsafe.end(); + } + }; + + 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 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 handleRemoveLink(const GraphEdgeIterator &edgeItr, + const GraphNodeIterator &nodeItr) { + NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData(); + nodeData.handleRemoveLink(*g, nodeItr, edgeItr); + } + + 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); + } + + } + + bool rNBucketEmpty() const { + return (rNAllocableBucket.empty() && rNUnallocableBucket.empty()); + } + +private: + + Solver *s; + SolverGraph *g; + RNAllocableNodeList rNAllocableBucket; + RNUnallocableNodeList rNUnallocableBucket; +}; + + + +} +} + + +#endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H diff --git a/lib/CodeGen/PBQP/PBQPMath.h b/lib/CodeGen/PBQP/PBQPMath.h new file mode 100644 index 0000000..11f4b4b --- /dev/null +++ b/lib/CodeGen/PBQP/PBQPMath.h @@ -0,0 +1,288 @@ +//===-- 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 diff --git a/lib/CodeGen/PBQP/SimpleGraph.h b/lib/CodeGen/PBQP/SimpleGraph.h new file mode 100644 index 0000000..1ca9cae --- /dev/null +++ b/lib/CodeGen/PBQP/SimpleGraph.h @@ -0,0 +1,100 @@ +//===-- 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 diff --git a/lib/CodeGen/PBQP/Solution.h b/lib/CodeGen/PBQP/Solution.h new file mode 100644 index 0000000..c91e2fa --- /dev/null +++ b/lib/CodeGen/PBQP/Solution.h @@ -0,0 +1,88 @@ +//===-- Solution.h ------- PBQP Solution -----------------------*- 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_SOLUTION_H +#define LLVM_CODEGEN_PBQP_SOLUTION_H + +#include "PBQPMath.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; + } + + 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); + } + +}; + +} + +#endif // LLVM_CODEGEN_PBQP_SOLUTION_H diff --git a/lib/CodeGen/PBQP/Solver.h b/lib/CodeGen/PBQP/Solver.h new file mode 100644 index 0000000..a9c5f83 --- /dev/null +++ b/lib/CodeGen/PBQP/Solver.h @@ -0,0 +1,31 @@ +//===-- 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 |