From ba34beb600f1dbb1e71cb1c5ab3e3c7e9bfa9643 Mon Sep 17 00:00:00 2001 From: Lang Hames Date: Fri, 28 Feb 2014 22:44:44 +0000 Subject: [PATCH] Jumped the gun with r202551 and broke some bots that weren't yet C++11ified. Reverting until the C++11 switch is complete. git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@202554 91177308-0d34-0410-b5e6-96231b3b80d8 --- include/llvm/CodeGen/PBQP/CostAllocator.h | 147 ---- include/llvm/CodeGen/PBQP/Graph.h | 678 ++++++++---------- include/llvm/CodeGen/PBQP/HeuristicBase.h | 247 +++++++ include/llvm/CodeGen/PBQP/HeuristicSolver.h | 618 ++++++++++++++++ include/llvm/CodeGen/PBQP/Heuristics/Briggs.h | 468 ++++++++++++ include/llvm/CodeGen/PBQP/Math.h | 638 +++++++--------- include/llvm/CodeGen/PBQP/ReductionRules.h | 194 ----- include/llvm/CodeGen/PBQP/RegAllocSolver.h | 359 ---------- include/llvm/CodeGen/PBQP/Solution.h | 6 +- include/llvm/CodeGen/RegAllocPBQP.h | 33 +- lib/CodeGen/RegAllocPBQP.cpp | 76 +- 11 files changed, 1928 insertions(+), 1536 deletions(-) delete mode 100644 include/llvm/CodeGen/PBQP/CostAllocator.h create mode 100644 include/llvm/CodeGen/PBQP/HeuristicBase.h create mode 100644 include/llvm/CodeGen/PBQP/HeuristicSolver.h create mode 100644 include/llvm/CodeGen/PBQP/Heuristics/Briggs.h delete mode 100644 include/llvm/CodeGen/PBQP/ReductionRules.h delete mode 100644 include/llvm/CodeGen/PBQP/RegAllocSolver.h diff --git a/include/llvm/CodeGen/PBQP/CostAllocator.h b/include/llvm/CodeGen/PBQP/CostAllocator.h deleted file mode 100644 index 164633453e9..00000000000 --- a/include/llvm/CodeGen/PBQP/CostAllocator.h +++ /dev/null @@ -1,147 +0,0 @@ -//===---------- CostAllocator.h - PBQP Cost Allocator -----------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Defines classes conforming to the PBQP cost value manager concept. -// -// Cost value managers are memory managers for PBQP cost values (vectors and -// matrices). Since PBQP graphs can grow very large (E.g. hundreds of thousands -// of edges on the largest function in SPEC2006). -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_COSTALLOCATOR_H -#define LLVM_COSTALLOCATOR_H - -#include -#include - -namespace PBQP { - -template -class CostPool { -public: - - class PoolEntry { - public: - template - PoolEntry(CostPool &pool, CostKeyT cost) - : pool(pool), cost(std::move(cost)), refCount(0) {} - ~PoolEntry() { pool.removeEntry(this); } - void incRef() { ++refCount; } - bool decRef() { --refCount; return (refCount == 0); } - CostT& getCost() { return cost; } - const CostT& getCost() const { return cost; } - private: - CostPool &pool; - CostT cost; - std::size_t refCount; - }; - - class PoolRef { - public: - PoolRef(PoolEntry *entry) : entry(entry) { - this->entry->incRef(); - } - PoolRef(const PoolRef &r) { - entry = r.entry; - entry->incRef(); - } - PoolRef& operator=(const PoolRef &r) { - assert(entry != 0 && "entry should not be null."); - PoolEntry *temp = r.entry; - temp->incRef(); - entry->decRef(); - entry = temp; - return *this; - } - - ~PoolRef() { - if (entry->decRef()) - delete entry; - } - void reset(PoolEntry *entry) { - entry->incRef(); - this->entry->decRef(); - this->entry = entry; - } - CostT& operator*() { return entry->getCost(); } - const CostT& operator*() const { return entry->getCost(); } - CostT* operator->() { return &entry->getCost(); } - const CostT* operator->() const { return &entry->getCost(); } - private: - PoolEntry *entry; - }; - -private: - class EntryComparator { - public: - template - typename std::enable_if< - !std::is_same::type>::value, - bool>::type - operator()(const PoolEntry* a, const CostKeyT &b) { - return compare(a->getCost(), b); - } - bool operator()(const PoolEntry* a, const PoolEntry* b) { - return compare(a->getCost(), b->getCost()); - } - private: - CostKeyTComparator compare; - }; - - typedef std::set EntrySet; - - EntrySet entrySet; - - void removeEntry(PoolEntry *p) { entrySet.erase(p); } - -public: - - template - PoolRef getCost(CostKeyT costKey) { - typename EntrySet::iterator itr = - std::lower_bound(entrySet.begin(), entrySet.end(), costKey, - EntryComparator()); - - if (itr != entrySet.end() && costKey == (*itr)->getCost()) - return PoolRef(*itr); - - PoolEntry *p = new PoolEntry(*this, std::move(costKey)); - entrySet.insert(itr, p); - return PoolRef(p); - } -}; - -template -class PoolCostAllocator { -private: - typedef CostPool VectorCostPool; - typedef CostPool MatrixCostPool; -public: - typedef VectorT Vector; - typedef MatrixT Matrix; - typedef typename VectorCostPool::PoolRef VectorPtr; - typedef typename MatrixCostPool::PoolRef MatrixPtr; - - template - VectorPtr getVector(VectorKeyT v) { return vectorPool.getCost(std::move(v)); } - - template - MatrixPtr getMatrix(MatrixKeyT m) { return matrixPool.getCost(std::move(m)); } -private: - VectorCostPool vectorPool; - MatrixCostPool matrixPool; -}; - -} - -#endif // LLVM_COSTALLOCATOR_H diff --git a/include/llvm/CodeGen/PBQP/Graph.h b/include/llvm/CodeGen/PBQP/Graph.h index 7ce95c7e73e..07371439249 100644 --- a/include/llvm/CodeGen/PBQP/Graph.h +++ b/include/llvm/CodeGen/PBQP/Graph.h @@ -15,526 +15,414 @@ #ifndef LLVM_CODEGEN_PBQP_GRAPH_H #define LLVM_CODEGEN_PBQP_GRAPH_H +#include "Math.h" #include "llvm/ADT/ilist.h" #include "llvm/ADT/ilist_node.h" -#include "llvm/Support/Compiler.h" #include #include #include namespace PBQP { - class GraphBase { + /// PBQP Graph class. + /// Instances of this class describe PBQP problems. + class Graph { public: + typedef unsigned NodeId; typedef unsigned EdgeId; - }; - /// PBQP Graph class. - /// Instances of this class describe PBQP problems. - /// - template - class Graph : public GraphBase { private: - typedef typename SolverT::CostAllocator CostAllocator; + + typedef std::set AdjEdgeList; + public: - typedef typename SolverT::RawVector RawVector; - typedef typename SolverT::RawMatrix RawMatrix; - typedef typename SolverT::Vector Vector; - typedef typename SolverT::Matrix Matrix; - typedef typename CostAllocator::VectorPtr VectorPtr; - typedef typename CostAllocator::MatrixPtr MatrixPtr; - typedef typename SolverT::NodeMetadata NodeMetadata; - typedef typename SolverT::EdgeMetadata EdgeMetadata; + + typedef AdjEdgeList::iterator AdjEdgeItr; private: class NodeEntry { + private: + Vector costs; + AdjEdgeList adjEdges; + void *data; + NodeEntry() : costs(0, 0) {} public: - typedef std::set AdjEdgeList; - typedef AdjEdgeList::const_iterator AdjEdgeItr; - NodeEntry(VectorPtr Costs) : Costs(Costs) {} - - VectorPtr Costs; - NodeMetadata Metadata; - AdjEdgeList AdjEdgeIds; + NodeEntry(const Vector &costs) : costs(costs), data(0) {} + Vector& getCosts() { return costs; } + const Vector& getCosts() const { return costs; } + unsigned getDegree() const { return adjEdges.size(); } + AdjEdgeItr edgesBegin() { return adjEdges.begin(); } + AdjEdgeItr edgesEnd() { return adjEdges.end(); } + AdjEdgeItr addEdge(EdgeId e) { + return adjEdges.insert(adjEdges.end(), e); + } + void removeEdge(AdjEdgeItr ae) { + adjEdges.erase(ae); + } + void setData(void *data) { this->data = data; } + void* getData() { return data; } }; class EdgeEntry { - public: - EdgeEntry(NodeId N1Id, NodeId N2Id, MatrixPtr Costs) - : Costs(Costs), N1Id(N1Id), N2Id(N2Id) {} - void invalidate() { - N1Id = N2Id = Graph::invalidNodeId(); - Costs = nullptr; - } - NodeId getN1Id() const { return N1Id; } - NodeId getN2Id() const { return N2Id; } - MatrixPtr Costs; - EdgeMetadata Metadata; private: - NodeId N1Id, N2Id; + NodeId node1, node2; + Matrix costs; + AdjEdgeItr node1AEItr, node2AEItr; + void *data; + EdgeEntry() : costs(0, 0, 0), data(0) {} + public: + EdgeEntry(NodeId node1, NodeId node2, const Matrix &costs) + : node1(node1), node2(node2), costs(costs) {} + NodeId getNode1() const { return node1; } + NodeId getNode2() const { return node2; } + Matrix& getCosts() { return costs; } + const Matrix& getCosts() const { 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 ----- - CostAllocator CostAlloc; - SolverT *Solver; - typedef std::vector NodeVector; typedef std::vector FreeNodeVector; - NodeVector Nodes; - FreeNodeVector FreeNodeIds; + NodeVector nodes; + FreeNodeVector freeNodes; typedef std::vector EdgeVector; typedef std::vector FreeEdgeVector; - EdgeVector Edges; - FreeEdgeVector FreeEdgeIds; + EdgeVector edges; + FreeEdgeVector freeEdges; // ----- INTERNAL METHODS ----- - NodeEntry& getNode(NodeId NId) { return Nodes[NId]; } - const NodeEntry& getNode(NodeId NId) const { return Nodes[NId]; } + NodeEntry& getNode(NodeId nId) { return nodes[nId]; } + const NodeEntry& getNode(NodeId nId) const { return nodes[nId]; } - EdgeEntry& getEdge(EdgeId EId) { return Edges[EId]; } - const EdgeEntry& getEdge(EdgeId EId) const { return Edges[EId]; } + EdgeEntry& getEdge(EdgeId eId) { return edges[eId]; } + const EdgeEntry& getEdge(EdgeId eId) const { return edges[eId]; } - NodeId addConstructedNode(const NodeEntry &N) { - NodeId NId = 0; - if (!FreeNodeIds.empty()) { - NId = FreeNodeIds.back(); - FreeNodeIds.pop_back(); - Nodes[NId] = std::move(N); + NodeId addConstructedNode(const NodeEntry &n) { + NodeId nodeId = 0; + if (!freeNodes.empty()) { + nodeId = freeNodes.back(); + freeNodes.pop_back(); + nodes[nodeId] = n; } else { - NId = Nodes.size(); - Nodes.push_back(std::move(N)); + nodeId = nodes.size(); + nodes.push_back(n); } - return NId; + return nodeId; } - EdgeId addConstructedEdge(const EdgeEntry &E) { - assert(findEdge(E.getN1Id(), E.getN2Id()) == invalidEdgeId() && + EdgeId addConstructedEdge(const EdgeEntry &e) { + assert(findEdge(e.getNode1(), e.getNode2()) == invalidEdgeId() && "Attempt to add duplicate edge."); - EdgeId EId = 0; - if (!FreeEdgeIds.empty()) { - EId = FreeEdgeIds.back(); - FreeEdgeIds.pop_back(); - Edges[EId] = std::move(E); + EdgeId edgeId = 0; + if (!freeEdges.empty()) { + edgeId = freeEdges.back(); + freeEdges.pop_back(); + edges[edgeId] = e; } else { - EId = Edges.size(); - Edges.push_back(std::move(E)); + edgeId = edges.size(); + edges.push_back(e); } - EdgeEntry &NE = getEdge(EId); - NodeEntry &N1 = getNode(NE.getN1Id()); - NodeEntry &N2 = getNode(NE.getN2Id()); + EdgeEntry &ne = getEdge(edgeId); + NodeEntry &n1 = getNode(ne.getNode1()); + NodeEntry &n2 = getNode(ne.getNode2()); // Sanity check on matrix dimensions: - assert((N1.Costs->getLength() == NE.Costs->getRows()) && - (N2.Costs->getLength() == NE.Costs->getCols()) && + assert((n1.getCosts().getLength() == ne.getCosts().getRows()) && + (n2.getCosts().getLength() == ne.getCosts().getCols()) && "Edge cost dimensions do not match node costs dimensions."); - N1.AdjEdgeIds.insert(EId); - N2.AdjEdgeIds.insert(EId); - return EId; + ne.setNode1AEItr(n1.addEdge(edgeId)); + ne.setNode2AEItr(n2.addEdge(edgeId)); + return edgeId; } - Graph(const Graph &Other) {} - void operator=(const Graph &Other) {} + Graph(const Graph &other) {} + void operator=(const Graph &other) {} public: - typedef typename NodeEntry::AdjEdgeItr AdjEdgeItr; - class NodeItr { public: - NodeItr(NodeId CurNId, const Graph &G) - : CurNId(CurNId), EndNId(G.Nodes.size()), FreeNodeIds(G.FreeNodeIds) { - this->CurNId = findNextInUse(CurNId); // Move to first in-use node id + NodeItr(NodeId nodeId, const Graph &g) + : nodeId(nodeId), endNodeId(g.nodes.size()), freeNodes(g.freeNodes) { + this->nodeId = findNextInUse(nodeId); // Move to the first in-use nodeId } - bool operator==(const NodeItr &O) const { return CurNId == O.CurNId; } - bool operator!=(const NodeItr &O) const { return !(*this == O); } - NodeItr& operator++() { CurNId = findNextInUse(++CurNId); return *this; } - NodeId operator*() const { return CurNId; } + bool operator==(const NodeItr& n) const { return nodeId == n.nodeId; } + bool operator!=(const NodeItr& n) const { return !(*this == n); } + NodeItr& operator++() { nodeId = findNextInUse(++nodeId); return *this; } + NodeId operator*() const { return nodeId; } private: - NodeId findNextInUse(NodeId NId) const { - while (NId < EndNId && - std::find(FreeNodeIds.begin(), FreeNodeIds.end(), NId) != - FreeNodeIds.end()) { - ++NId; + NodeId findNextInUse(NodeId n) const { + while (n < endNodeId && + std::find(freeNodes.begin(), freeNodes.end(), n) != + freeNodes.end()) { + ++n; } - return NId; + return n; } - NodeId CurNId, EndNId; - const FreeNodeVector &FreeNodeIds; + NodeId nodeId, endNodeId; + const FreeNodeVector& freeNodes; }; class EdgeItr { public: - EdgeItr(EdgeId CurEId, const Graph &G) - : CurEId(CurEId), EndEId(G.Edges.size()), FreeEdgeIds(G.FreeEdgeIds) { - this->CurEId = findNextInUse(CurEId); // Move to first in-use edge id + EdgeItr(EdgeId edgeId, const Graph &g) + : edgeId(edgeId), endEdgeId(g.edges.size()), freeEdges(g.freeEdges) { + this->edgeId = findNextInUse(edgeId); // Move to the first in-use edgeId } - bool operator==(const EdgeItr &O) const { return CurEId == O.CurEId; } - bool operator!=(const EdgeItr &O) const { return !(*this == O); } - EdgeItr& operator++() { CurEId = findNextInUse(++CurEId); return *this; } - EdgeId operator*() const { return CurEId; } + bool operator==(const EdgeItr& n) const { return edgeId == n.edgeId; } + bool operator!=(const EdgeItr& n) const { return !(*this == n); } + EdgeItr& operator++() { edgeId = findNextInUse(++edgeId); return *this; } + EdgeId operator*() const { return edgeId; } private: - EdgeId findNextInUse(EdgeId EId) const { - while (EId < EndEId && - std::find(FreeEdgeIds.begin(), FreeEdgeIds.end(), EId) != - FreeEdgeIds.end()) { - ++EId; + EdgeId findNextInUse(EdgeId n) const { + while (n < endEdgeId && + std::find(freeEdges.begin(), freeEdges.end(), n) != + freeEdges.end()) { + ++n; } - return EId; + return n; } - EdgeId CurEId, EndEId; - const FreeEdgeVector &FreeEdgeIds; - }; - - class NodeIdSet { - public: - NodeIdSet(const Graph &G) : G(G) { } - NodeItr begin() const { return NodeItr(0, G); } - NodeItr end() const { return NodeItr(G.Nodes.size(), G); } - bool empty() const { return G.Nodes.empty(); } - typename NodeVector::size_type size() const { - return G.Nodes.size() - G.FreeNodeIds.size(); - } - private: - const Graph& G; - }; - - class EdgeIdSet { - public: - EdgeIdSet(const Graph &G) : G(G) { } - EdgeItr begin() const { return EdgeItr(0, G); } - EdgeItr end() const { return EdgeItr(G.Edges.size(), G); } - bool empty() const { return G.Edges.empty(); } - typename NodeVector::size_type size() const { - return G.Edges.size() - G.FreeEdgeIds.size(); - } - private: - const Graph& G; - }; - - class AdjEdgeIdSet { - public: - AdjEdgeIdSet(const NodeEntry &NE) : NE(NE) { } - typename NodeEntry::AdjEdgeItr begin() const { - return NE.AdjEdgeIds.begin(); - } - typename NodeEntry::AdjEdgeItr end() const { - return NE.AdjEdgeIds.end(); - } - bool empty() const { return NE.AdjEdges.empty(); } - typename NodeEntry::AdjEdgeList::size_type size() const { - return NE.AdjEdgeIds.size(); - } - private: - const NodeEntry &NE; + EdgeId edgeId, endEdgeId; + const FreeEdgeVector& freeEdges; }; /// \brief Construct an empty PBQP graph. - Graph() : Solver(nullptr) { } - - /// \brief Lock this graph to the given solver instance in preparation - /// for running the solver. This method will call solver.handleAddNode for - /// each node in the graph, and handleAddEdge for each edge, to give the - /// solver an opportunity to set up any requried metadata. - void setSolver(SolverT &S) { - assert(Solver == nullptr && "Solver already set. Call unsetSolver()."); - Solver = &S; - for (auto NId : nodeIds()) - Solver->handleAddNode(NId); - for (auto EId : edgeIds()) - Solver->handleAddEdge(EId); - } - - /// \brief Release from solver instance. - void unsetSolver() { - assert(Solver != nullptr && "Solver not set."); - Solver = nullptr; - } + Graph() {} /// \brief Add a node with the given costs. - /// @param Costs Cost vector for the new node. + /// @param costs Cost vector for the new node. /// @return Node iterator for the added node. - template - NodeId addNode(OtherVectorT Costs) { - // Get cost vector from the problem domain - VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs)); - NodeId NId = addConstructedNode(NodeEntry(AllocatedCosts)); - if (Solver) - Solver->handleAddNode(NId); - return NId; + NodeId addNode(const Vector &costs) { + return addConstructedNode(NodeEntry(costs)); } /// \brief Add an edge between the given nodes with the given costs. - /// @param N1Id First node. - /// @param N2Id Second node. + /// @param n1Id First node. + /// @param n2Id Second node. /// @return Edge iterator for the added edge. - template - EdgeId addEdge(NodeId N1Id, NodeId N2Id, OtherVectorT Costs) { - assert(getNodeCosts(N1Id).getLength() == Costs.getRows() && - getNodeCosts(N2Id).getLength() == Costs.getCols() && + EdgeId addEdge(NodeId n1Id, NodeId n2Id, const Matrix &costs) { + assert(getNodeCosts(n1Id).getLength() == costs.getRows() && + getNodeCosts(n2Id).getLength() == costs.getCols() && "Matrix dimensions mismatch."); - // Get cost matrix from the problem domain. - MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs)); - EdgeId EId = addConstructedEdge(EdgeEntry(N1Id, N2Id, AllocatedCosts)); - if (Solver) - Solver->handleAddEdge(EId); - return EId; + return addConstructedEdge(EdgeEntry(n1Id, n2Id, costs)); } - /// \brief Returns true if the graph is empty. - bool empty() const { return NodeIdSet(*this).empty(); } - - NodeIdSet nodeIds() const { return NodeIdSet(*this); } - EdgeIdSet edgeIds() const { return EdgeIdSet(*this); } - - AdjEdgeIdSet adjEdgeIds(NodeId NId) { return AdjEdgeIdSet(getNode(NId)); } - /// \brief Get the number of nodes in the graph. /// @return Number of nodes in the graph. - unsigned getNumNodes() const { return NodeIdSet(*this).size(); } + unsigned getNumNodes() const { return nodes.size() - freeNodes.size(); } /// \brief Get the number of edges in the graph. /// @return Number of edges in the graph. - unsigned getNumEdges() const { return EdgeIdSet(*this).size(); } + unsigned getNumEdges() const { return edges.size() - freeEdges.size(); } - /// \brief Set a node's cost vector. - /// @param NId Node to update. - /// @param Costs New costs to set. + /// \brief Get a node's cost vector. + /// @param nId Node id. /// @return Node cost vector. - template - void setNodeCosts(NodeId NId, OtherVectorT Costs) { - VectorPtr AllocatedCosts = CostAlloc.getVector(std::move(Costs)); - if (Solver) - Solver->handleSetNodeCosts(NId, *AllocatedCosts); - getNode(NId).Costs = AllocatedCosts; - } + Vector& getNodeCosts(NodeId nId) { return getNode(nId).getCosts(); } /// \brief Get a node's cost vector (const version). - /// @param NId Node id. + /// @param nId Node id. /// @return Node cost vector. - const Vector& getNodeCosts(NodeId NId) const { - return *getNode(NId).Costs; + const Vector& getNodeCosts(NodeId nId) const { + return getNode(nId).getCosts(); } - NodeMetadata& getNodeMetadata(NodeId NId) { - return getNode(NId).Metadata; - } + /// \brief Set a node's data pointer. + /// @param nId Node id. + /// @param data Pointer to node data. + /// + /// Typically used by a PBQP solver to attach data to aid in solution. + void setNodeData(NodeId nId, void *data) { getNode(nId).setData(data); } - const NodeMetadata& getNodeMetadata(NodeId NId) const { - return getNode(NId).Metadata; - } + /// \brief Get the node's data pointer. + /// @param nId Node id. + /// @return Pointer to node data. + void* getNodeData(NodeId nId) { return getNode(nId).getData(); } + + /// \brief Get an edge's cost matrix. + /// @param eId Edge id. + /// @return Edge cost matrix. + Matrix& getEdgeCosts(EdgeId eId) { return getEdge(eId).getCosts(); } - typename NodeEntry::AdjEdgeList::size_type getNodeDegree(NodeId NId) const { - return getNode(NId).AdjEdgeIds.size(); + /// \brief Get an edge's cost matrix (const version). + /// @param eId Edge id. + /// @return Edge cost matrix. + const Matrix& getEdgeCosts(EdgeId eId) const { + return getEdge(eId).getCosts(); } - /// \brief Set an edge's cost matrix. - /// @param EId Edge id. - /// @param Costs New cost matrix. - template - void setEdgeCosts(EdgeId EId, OtherMatrixT Costs) { - MatrixPtr AllocatedCosts = CostAlloc.getMatrix(std::move(Costs)); - if (Solver) - Solver->handleSetEdgeCosts(EId, *AllocatedCosts); - getEdge(EId).Costs = AllocatedCosts; + /// \brief Set an edge's data pointer. + /// @param eId Edge id. + /// @param data Pointer to edge data. + /// + /// Typically used by a PBQP solver to attach data to aid in solution. + void setEdgeData(EdgeId eId, void *data) { getEdge(eId).setData(data); } + + /// \brief Get an edge's data pointer. + /// @param eId Edge id. + /// @return Pointer to edge data. + void* getEdgeData(EdgeId eId) { return getEdge(eId).getData(); } + + /// \brief Get a node's degree. + /// @param nId Node id. + /// @return The degree of the node. + unsigned getNodeDegree(NodeId nId) const { + return getNode(nId).getDegree(); } - /// \brief Get an edge's cost matrix (const version). - /// @param EId Edge id. - /// @return Edge cost matrix. - const Matrix& getEdgeCosts(EdgeId EId) const { return *getEdge(EId).Costs; } + /// \brief Begin iterator for node set. + NodeItr nodesBegin() const { return NodeItr(0, *this); } + + /// \brief End iterator for node set. + NodeItr nodesEnd() const { return NodeItr(nodes.size(), *this); } + + /// \brief Begin iterator for edge set. + EdgeItr edgesBegin() const { return EdgeItr(0, *this); } - EdgeMetadata& getEdgeMetadata(EdgeId NId) { - return getEdge(NId).Metadata; + /// \brief End iterator for edge set. + EdgeItr edgesEnd() const { return EdgeItr(edges.size(), *this); } + + /// \brief Get begin iterator for adjacent edge set. + /// @param nId Node id. + /// @return Begin iterator for the set of edges connected to the given node. + AdjEdgeItr adjEdgesBegin(NodeId nId) { + return getNode(nId).edgesBegin(); } - const EdgeMetadata& getEdgeMetadata(EdgeId NId) const { - return getEdge(NId).Metadata; + /// \brief Get end iterator for adjacent edge set. + /// @param nId Node id. + /// @return End iterator for the set of edges connected to the given node. + AdjEdgeItr adjEdgesEnd(NodeId nId) { + return getNode(nId).edgesEnd(); } /// \brief Get the first node connected to this edge. - /// @param EId Edge id. + /// @param eId Edge id. /// @return The first node connected to the given edge. - NodeId getEdgeNode1Id(EdgeId EId) { - return getEdge(EId).getN1Id(); + NodeId getEdgeNode1(EdgeId eId) { + return getEdge(eId).getNode1(); } /// \brief Get the second node connected to this edge. - /// @param EId Edge id. + /// @param eId Edge id. /// @return The second node connected to the given edge. - NodeId getEdgeNode2Id(EdgeId EId) { - return getEdge(EId).getN2Id(); + NodeId getEdgeNode2(EdgeId eId) { + return getEdge(eId).getNode2(); } /// \brief Get the "other" node connected to this edge. - /// @param EId Edge id. - /// @param NId Node id for the "given" node. + /// @param eId Edge id. + /// @param nId Node id for the "given" node. /// @return The iterator for the "other" node connected to this edge. - NodeId getEdgeOtherNodeId(EdgeId EId, NodeId NId) { - EdgeEntry &E = getEdge(EId); - if (E.getN1Id() == NId) { - return E.getN2Id(); + NodeId getEdgeOtherNode(EdgeId eId, NodeId nId) { + EdgeEntry &e = getEdge(eId); + if (e.getNode1() == nId) { + return e.getNode2(); } // else - return E.getN1Id(); - } - - /// \brief Returns a value representing an invalid (non-existant) node. - static NodeId invalidNodeId() { - return std::numeric_limits::max(); + return e.getNode1(); } - /// \brief Returns a value representing an invalid (non-existant) edge. - static EdgeId invalidEdgeId() { + EdgeId invalidEdgeId() const { return std::numeric_limits::max(); } /// \brief Get the edge connecting two nodes. - /// @param N1Id First node id. - /// @param N2Id Second node id. - /// @return An id for edge (N1Id, N2Id) if such an edge exists, + /// @param n1Id First node id. + /// @param n2Id Second node id. + /// @return An id for edge (n1Id, n2Id) if such an edge exists, /// otherwise returns an invalid edge id. - EdgeId findEdge(NodeId N1Id, NodeId N2Id) { - for (auto AEId : adjEdgeIds(N1Id)) { - if ((getEdgeNode1Id(AEId) == N2Id) || - (getEdgeNode2Id(AEId) == N2Id)) { - return AEId; + EdgeId findEdge(NodeId n1Id, NodeId n2Id) { + for (AdjEdgeItr aeItr = adjEdgesBegin(n1Id), aeEnd = adjEdgesEnd(n1Id); + aeItr != aeEnd; ++aeItr) { + if ((getEdgeNode1(*aeItr) == n2Id) || + (getEdgeNode2(*aeItr) == n2Id)) { + return *aeItr; } } return invalidEdgeId(); } /// \brief Remove a node from the graph. - /// @param NId Node id. - void removeNode(NodeId NId) { - if (Solver) - Solver->handleRemoveNode(NId); - NodeEntry &N = getNode(NId); - // TODO: Can this be for-each'd? - for (AdjEdgeItr AEItr = N.adjEdgesBegin(), - AEEnd = N.adjEdgesEnd(); - AEItr != AEEnd;) { - EdgeId EId = *AEItr; - ++AEItr; - removeEdge(EId); + /// @param nId Node id. + void removeNode(NodeId nId) { + NodeEntry &n = getNode(nId); + for (AdjEdgeItr itr = n.edgesBegin(), end = n.edgesEnd(); itr != end; ++itr) { + EdgeId eId = *itr; + removeEdge(eId); } - FreeNodeIds.push_back(NId); - } - - /// \brief Disconnect an edge from the given node. - /// - /// Removes the given edge from the adjacency list of the given node. - /// This operation leaves the edge in an 'asymmetric' state: It will no - /// longer appear in an iteration over the given node's (NId's) edges, but - /// will appear in an iteration over the 'other', unnamed node's edges. - /// - /// This does not correspond to any normal graph operation, but exists to - /// support efficient PBQP graph-reduction based solvers. It is used to - /// 'effectively' remove the unnamed node from the graph while the solver - /// is performing the reduction. The solver will later call reconnectNode - /// to restore the edge in the named node's adjacency list. - /// - /// Since the degree of a node is the number of connected edges, - /// disconnecting an edge from a node 'u' will cause the degree of 'u' to - /// drop by 1. - /// - /// A disconnected edge WILL still appear in an iteration over the graph - /// edges. - /// - /// A disconnected edge should not be removed from the graph, it should be - /// reconnected first. - /// - /// A disconnected edge can be reconnected by calling the reconnectEdge - /// method. - void disconnectEdge(EdgeId EId, NodeId NId) { - if (Solver) - Solver->handleDisconnectEdge(EId, NId); - NodeEntry &N = getNode(NId); - N.AdjEdgeIds.erase(EId); - } - - /// \brief Convenience method to disconnect all neighbours from the given - /// node. - void disconnectAllNeighborsFromNode(NodeId NId) { - for (auto AEId : adjEdgeIds(NId)) - disconnectEdge(AEId, getEdgeOtherNodeId(AEId, NId)); - } - - /// \brief Re-attach an edge to its nodes. - /// - /// Adds an edge that had been previously disconnected back into the - /// adjacency set of the nodes that the edge connects. - void reconnectEdge(EdgeId EId, NodeId NId) { - NodeEntry &N = getNode(NId); - N.addAdjEdge(EId); - if (Solver) - Solver->handleReconnectEdge(EId, NId); + freeNodes.push_back(nId); } /// \brief Remove an edge from the graph. - /// @param EId Edge id. - void removeEdge(EdgeId EId) { - if (Solver) - Solver->handleRemoveEdge(EId); - EdgeEntry &E = getEdge(EId); - NodeEntry &N1 = getNode(E.getNode1()); - NodeEntry &N2 = getNode(E.getNode2()); - N1.removeEdge(EId); - N2.removeEdge(EId); - FreeEdgeIds.push_back(EId); - Edges[EId].invalidate(); + /// @param eId Edge id. + void removeEdge(EdgeId eId) { + EdgeEntry &e = getEdge(eId); + NodeEntry &n1 = getNode(e.getNode1()); + NodeEntry &n2 = getNode(e.getNode2()); + n1.removeEdge(e.getNode1AEItr()); + n2.removeEdge(e.getNode2AEItr()); + freeEdges.push_back(eId); } /// \brief Remove all nodes and edges from the graph. void clear() { - Nodes.clear(); - FreeNodeIds.clear(); - Edges.clear(); - FreeEdgeIds.clear(); + nodes.clear(); + freeNodes.clear(); + edges.clear(); + freeEdges.clear(); } /// \brief Dump a graph to an output stream. template - void dump(OStream &OS) { - OS << nodeIds().size() << " " << edgeIds().size() << "\n"; - - for (auto NId : nodeIds()) { - const Vector& V = getNodeCosts(NId); - OS << "\n" << V.getLength() << "\n"; - assert(V.getLength() != 0 && "Empty vector in graph."); - OS << V[0]; - for (unsigned i = 1; i < V.getLength(); ++i) { - OS << " " << V[i]; + void dump(OStream &os) { + os << getNumNodes() << " " << getNumEdges() << "\n"; + + for (NodeItr nodeItr = nodesBegin(), nodeEnd = nodesEnd(); + nodeItr != nodeEnd; ++nodeItr) { + const Vector& v = getNodeCosts(*nodeItr); + os << "\n" << v.getLength() << "\n"; + assert(v.getLength() != 0 && "Empty vector in graph."); + os << v[0]; + for (unsigned i = 1; i < v.getLength(); ++i) { + os << " " << v[i]; } - OS << "\n"; + os << "\n"; } - for (auto EId : edgeIds()) { - NodeId N1Id = getEdgeNode1Id(EId); - NodeId N2Id = getEdgeNode2Id(EId); - assert(N1Id != N2Id && "PBQP graphs shound not have self-edges."); - const Matrix& M = getEdgeCosts(EId); - OS << "\n" << N1Id << " " << N2Id << "\n" - << M.getRows() << " " << M.getCols() << "\n"; - assert(M.getRows() != 0 && "No rows in matrix."); - assert(M.getCols() != 0 && "No cols in matrix."); - for (unsigned i = 0; i < M.getRows(); ++i) { - OS << M[i][0]; - for (unsigned j = 1; j < M.getCols(); ++j) { - OS << " " << M[i][j]; + for (EdgeItr edgeItr = edgesBegin(), edgeEnd = edgesEnd(); + edgeItr != edgeEnd; ++edgeItr) { + NodeId n1 = getEdgeNode1(*edgeItr); + NodeId n2 = getEdgeNode2(*edgeItr); + assert(n1 != n2 && "PBQP graphs shound not have self-edges."); + const Matrix& m = getEdgeCosts(*edgeItr); + os << "\n" << n1 << " " << n2 << "\n" + << m.getRows() << " " << m.getCols() << "\n"; + assert(m.getRows() != 0 && "No rows in matrix."); + assert(m.getCols() != 0 && "No cols in matrix."); + for (unsigned i = 0; i < m.getRows(); ++i) { + os << m[i][0]; + for (unsigned j = 1; j < m.getCols(); ++j) { + os << " " << m[i][j]; } - OS << "\n"; + os << "\n"; } } } @@ -542,27 +430,49 @@ namespace PBQP { /// \brief Print a representation of this graph in DOT format. /// @param os Output stream to print on. template - void printDot(OStream &OS) { - OS << "graph {\n"; - for (auto NId : nodeIds()) { - OS << " node" << NId << " [ label=\"" - << NId << ": " << getNodeCosts(NId) << "\" ]\n"; + 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=" << nodeIds().size() << " ]\n"; - for (auto EId : edgeIds()) { - OS << " node" << getEdgeNode1Id(EId) - << " -- node" << getEdgeNode2Id(EId) + + 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(EId); - for (unsigned i = 0; i < EdgeCosts.getRows(); ++i) { - OS << EdgeCosts.getRowAsVector(i) << "\\n"; + + const Matrix &edgeCosts = getEdgeCosts(*edgeItr); + + for (unsigned i = 0; i < edgeCosts.getRows(); ++i) { + os << edgeCosts.getRowAsVector(i) << "\\n"; } - OS << "\" ]\n"; + os << "\" ]\n"; } - OS << "}\n"; + os << "}\n"; } + }; +// void Graph::copyFrom(const Graph &other) { +// std::map nodeMap; + +// for (Graph::ConstNodeItr nItr = other.nodesBegin(), +// nEnd = other.nodesEnd(); +// nItr != nEnd; ++nItr) { +// nodeMap[nItr] = addNode(other.getNodeCosts(nItr)); +// } +// } + } #endif // LLVM_CODEGEN_PBQP_GRAPH_HPP diff --git a/include/llvm/CodeGen/PBQP/HeuristicBase.h b/include/llvm/CodeGen/PBQP/HeuristicBase.h new file mode 100644 index 00000000000..8bcbb9ed1d6 --- /dev/null +++ b/include/llvm/CodeGen/PBQP/HeuristicBase.h @@ -0,0 +1,247 @@ +//===-- 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: + ///
    + ///
  • void addToHeuristicList(Graph::NodeItr) : Add a node to the + /// heuristic reduction list. + ///
  • void heuristicReduce() : Perform a single heuristic reduction. + ///
  • void preUpdateEdgeCosts(Graph::EdgeItr) : Handle the (imminent) + /// change to the cost matrix on the given edge (by R2). + ///
  • void postUpdateEdgeCostts(Graph::EdgeItr) : Handle the new + /// costs on the given edge. + ///
  • void handleAddEdge(Graph::EdgeItr) : Handle the addition of a new + /// edge into the PBQP graph (by R2). + ///
  • void handleRemoveEdge(Graph::EdgeItr, Graph::NodeItr) : Handle the + /// disconnection of the given edge from the given node. + ///
  • A constructor for your derived class : to pass back a reference to + /// the solver which is using this heuristic. + ///
+ /// + /// 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 + class HeuristicBase { + private: + + typedef std::list OptimalList; + + HeuristicSolverImpl &s; + Graph &g; + OptimalList optimalList; + + // Return a reference to the derived heuristic. + HImpl& impl() { return static_cast(*this); } + + // Add the given node to the optimal reductions list. Keep an iterator to + // its location for fast removal. + void addToOptimalReductionList(Graph::NodeId nId) { + optimalList.insert(optimalList.end(), nId); + } + + public: + + /// \brief Construct an instance with a reference to the given solver. + /// @param solver The solver which is using this heuristic instance. + HeuristicBase(HeuristicSolverImpl &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& 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 at least as strong as this. I.e. Nodes of degree 3 or + /// higher should not be selected under any circumstances. + bool shouldOptimallyReduce(Graph::NodeId nId) { + if (g.getNodeDegree(nId) < 3) + return true; + // else + return false; + } + + /// \brief Add the given node to the list of nodes to be optimally reduced. + /// @param nId Node id 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::NodeId nId) { + optimalList.push_back(nId); + } + + /// \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::NodeId nId = optimalList.front(); + optimalList.pop_front(); + + switch (s.getSolverDegree(nId)) { + case 0: s.applyR0(nId); break; + case 1: s.applyR1(nId); break; + case 2: s.applyR2(nId); break; + default: llvm_unreachable( + "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()) { + getSolver().recordRN(); + } else { + finished = true; + } + } + } + } + + /// \brief Add a node to the heuristic reduce list. + /// @param nId Node id to add to the heuristic reduce list. + void addToHeuristicList(Graph::NodeId nId) { + llvm_unreachable("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. + bool heuristicReduce() { + llvm_unreachable("Must be implemented in derived class."); + return false; + } + + /// \brief Prepare a change in the costs on the given edge. + /// @param eId Edge id. + void preUpdateEdgeCosts(Graph::EdgeId eId) { + llvm_unreachable("Must be implemented in derived class."); + } + + /// \brief Handle the change in the costs on the given edge. + /// @param eId Edge id. + void postUpdateEdgeCostts(Graph::EdgeId eId) { + llvm_unreachable("Must be implemented in derived class."); + } + + /// \brief Handle the addition of a new edge into the PBQP graph. + /// @param eId Edge id for the added edge. + void handleAddEdge(Graph::EdgeId eId) { + llvm_unreachable("Must be implemented in derived class."); + } + + /// \brief Handle disconnection of an edge from a node. + /// @param eId Edge id for edge being disconnected. + /// @param nId Node id 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::EdgeId eId, Graph::NodeId nId) { + llvm_unreachable("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 diff --git a/include/llvm/CodeGen/PBQP/HeuristicSolver.h b/include/llvm/CodeGen/PBQP/HeuristicSolver.h new file mode 100644 index 00000000000..e26ca02fff7 --- /dev/null +++ b/include/llvm/CodeGen/PBQP/HeuristicSolver.h @@ -0,0 +1,618 @@ +//===-- 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 select a node for reduction. +// +//===----------------------------------------------------------------------===// + +#ifndef LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H +#define LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H + +#include "Graph.h" +#include "Solution.h" +#include +#include + +namespace PBQP { + + /// \brief Heuristic PBQP solver implementation. + /// + /// This class should usually be created (and destroyed) indirectly via a call + /// to HeuristicSolver::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 + class HeuristicSolverImpl { + private: + + typedef typename HImpl::NodeData HeuristicNodeData; + typedef typename HImpl::EdgeData HeuristicEdgeData; + + typedef std::list SolverEdges; + + public: + + /// \brief Iterator type for edges in the solver graph. + typedef SolverEdges::iterator SolverEdgeItr; + + private: + + class NodeData { + public: + NodeData() : solverDegree(0) {} + + HeuristicNodeData& getHeuristicData() { return hData; } + + SolverEdgeItr addSolverEdge(Graph::EdgeId eId) { + ++solverDegree; + return solverEdges.insert(solverEdges.end(), eId); + } + + void removeSolverEdge(SolverEdgeItr seItr) { + --solverDegree; + solverEdges.erase(seItr); + } + + 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; + } + + SolverEdgeItr getN1SolverEdgeItr() { return n1SolverEdgeItr; } + + void setN2SolverEdgeItr(SolverEdgeItr n2SolverEdgeItr){ + this->n2SolverEdgeItr = n2SolverEdgeItr; + } + + SolverEdgeItr getN2SolverEdgeItr() { return n2SolverEdgeItr; } + + private: + + HeuristicEdgeData hData; + SolverEdgeItr n1SolverEdgeItr, n2SolverEdgeItr; + }; + + Graph &g; + HImpl h; + Solution s; + std::vector stack; + + typedef std::list NodeDataList; + NodeDataList nodeDataList; + + typedef std::list EdgeDataList; + EdgeDataList edgeDataList; + + public: + + /// \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 nId Node id. + /// @return The heuristic data attached to the given node. + HeuristicNodeData& getHeuristicNodeData(Graph::NodeId nId) { + return getSolverNodeData(nId).getHeuristicData(); + } + + /// \brief Get the heuristic data attached to the given edge. + /// @param eId Edge id. + /// @return The heuristic data attached to the given node. + HeuristicEdgeData& getHeuristicEdgeData(Graph::EdgeId eId) { + return getSolverEdgeData(eId).getHeuristicData(); + } + + /// \brief Begin iterator for the set of edges adjacent to the given node in + /// the solver graph. + /// @param nId Node id. + /// @return Begin iterator for the set of edges adjacent to the given node + /// in the solver graph. + SolverEdgeItr solverEdgesBegin(Graph::NodeId nId) { + return getSolverNodeData(nId).solverEdgesBegin(); + } + + /// \brief End iterator for the set of edges adjacent to the given node in + /// the solver graph. + /// @param nId Node id. + /// @return End iterator for the set of edges adjacent to the given node in + /// the solver graph. + SolverEdgeItr solverEdgesEnd(Graph::NodeId nId) { + return getSolverNodeData(nId).solverEdgesEnd(); + } + + /// \brief Remove a node from the solver graph. + /// @param eId Edge id for edge to be removed. + /// + /// Does not notify the heuristic of the removal. That should be + /// done manually if necessary. + void removeSolverEdge(Graph::EdgeId eId) { + EdgeData &eData = getSolverEdgeData(eId); + NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eId)), + &n2Data = getSolverNodeData(g.getEdgeNode2(eId)); + + 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 nId Node id to add to the reduction stack. + void pushToStack(Graph::NodeId nId) { + getSolverNodeData(nId).clearSolverEdges(); + stack.push_back(nId); + } + + /// \brief Returns the solver degree of the given node. + /// @param nId Node id for which degree is requested. + /// @return Node degree in the solver graph (not the original graph). + unsigned getSolverDegree(Graph::NodeId nId) { + return getSolverNodeData(nId).getSolverDegree(); + } + + /// \brief Set the solution of the given node. + /// @param nId Node id to set solution for. + /// @param selection Selection for node. + void setSolution(const Graph::NodeId &nId, unsigned selection) { + s.setSelection(nId, selection); + + for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nId), + aeEnd = g.adjEdgesEnd(nId); + aeItr != aeEnd; ++aeItr) { + Graph::EdgeId eId(*aeItr); + Graph::NodeId anId(g.getEdgeOtherNode(eId, nId)); + getSolverNodeData(anId).addSolverEdge(eId); + } + } + + /// \brief Apply rule R0. + /// @param nId Node id for node to apply R0 to. + /// + /// Node will be automatically pushed to the solver stack. + void applyR0(Graph::NodeId nId) { + assert(getSolverNodeData(nId).getSolverDegree() == 0 && + "R0 applied to node with degree != 0."); + + // Nothing to do. Just push the node onto the reduction stack. + pushToStack(nId); + + s.recordR0(); + } + + /// \brief Apply rule R1. + /// @param xnId Node id for node to apply R1 to. + /// + /// Node will be automatically pushed to the solver stack. + void applyR1(Graph::NodeId xnId) { + NodeData &nd = getSolverNodeData(xnId); + assert(nd.getSolverDegree() == 1 && + "R1 applied to node with degree != 1."); + + Graph::EdgeId eId = *nd.solverEdgesBegin(); + + const Matrix &eCosts = g.getEdgeCosts(eId); + const Vector &xCosts = g.getNodeCosts(xnId); + + // Duplicate a little to avoid transposing matrices. + if (xnId == g.getEdgeNode1(eId)) { + Graph::NodeId ynId = g.getEdgeNode2(eId); + Vector &yCosts = g.getNodeCosts(ynId); + 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(eId, ynId); + } else { + Graph::NodeId ynId = g.getEdgeNode1(eId); + Vector &yCosts = g.getNodeCosts(ynId); + 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(eId, ynId); + } + removeSolverEdge(eId); + assert(nd.getSolverDegree() == 0 && + "Degree 1 with edge removed should be 0."); + pushToStack(xnId); + s.recordR1(); + } + + /// \brief Apply rule R2. + /// @param xnId Node id for node to apply R2 to. + /// + /// Node will be automatically pushed to the solver stack. + void applyR2(Graph::NodeId xnId) { + assert(getSolverNodeData(xnId).getSolverDegree() == 2 && + "R2 applied to node with degree != 2."); + + NodeData &nd = getSolverNodeData(xnId); + const Vector &xCosts = g.getNodeCosts(xnId); + + SolverEdgeItr aeItr = nd.solverEdgesBegin(); + Graph::EdgeId yxeId = *aeItr, + zxeId = *(++aeItr); + + Graph::NodeId ynId = g.getEdgeOtherNode(yxeId, xnId), + znId = g.getEdgeOtherNode(zxeId, xnId); + + bool flipEdge1 = (g.getEdgeNode1(yxeId) == xnId), + flipEdge2 = (g.getEdgeNode1(zxeId) == xnId); + + const Matrix *yxeCosts = flipEdge1 ? + new Matrix(g.getEdgeCosts(yxeId).transpose()) : + &g.getEdgeCosts(yxeId); + + const Matrix *zxeCosts = flipEdge2 ? + new Matrix(g.getEdgeCosts(zxeId).transpose()) : + &g.getEdgeCosts(zxeId); + + unsigned xLen = xCosts.getLength(), + yLen = yxeCosts->getRows(), + zLen = zxeCosts->getRows(); + + Matrix delta(yLen, zLen); + + 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; + } + } + delta[i][j] = min; + } + } + + if (flipEdge1) + delete yxeCosts; + + if (flipEdge2) + delete zxeCosts; + + Graph::EdgeId yzeId = g.findEdge(ynId, znId); + bool addedEdge = false; + + if (yzeId == g.invalidEdgeId()) { + yzeId = g.addEdge(ynId, znId, delta); + addedEdge = true; + } else { + Matrix &yzeCosts = g.getEdgeCosts(yzeId); + h.preUpdateEdgeCosts(yzeId); + if (ynId == g.getEdgeNode1(yzeId)) { + yzeCosts += delta; + } else { + yzeCosts += delta.transpose(); + } + } + + bool nullCostEdge = tryNormaliseEdgeMatrix(yzeId); + + if (!addedEdge) { + // If we modified the edge costs let the heuristic know. + h.postUpdateEdgeCosts(yzeId); + } + + 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(yzeId, ynId); + h.handleRemoveEdge(yzeId, znId); + removeSolverEdge(yzeId); + } + g.removeEdge(yzeId); + } else if (addedEdge) { + // If the edge was added, and non-null, finish setting it up, add it to + // the solver & notify heuristic. + edgeDataList.push_back(EdgeData()); + g.setEdgeData(yzeId, &edgeDataList.back()); + addSolverEdge(yzeId); + h.handleAddEdge(yzeId); + } + + h.handleRemoveEdge(yxeId, ynId); + removeSolverEdge(yxeId); + h.handleRemoveEdge(zxeId, znId); + removeSolverEdge(zxeId); + + pushToStack(xnId); + s.recordR2(); + } + + /// \brief Record an application of the RN rule. + /// + /// For use by the HeuristicBase. + void recordRN() { s.recordRN(); } + + private: + + NodeData& getSolverNodeData(Graph::NodeId nId) { + return *static_cast(g.getNodeData(nId)); + } + + EdgeData& getSolverEdgeData(Graph::EdgeId eId) { + return *static_cast(g.getEdgeData(eId)); + } + + void addSolverEdge(Graph::EdgeId eId) { + EdgeData &eData = getSolverEdgeData(eId); + NodeData &n1Data = getSolverNodeData(g.getEdgeNode1(eId)), + &n2Data = getSolverNodeData(g.getEdgeNode2(eId)); + + eData.setN1SolverEdgeItr(n1Data.addSolverEdge(eId)); + eData.setN2SolverEdgeItr(n2Data.addSolverEdge(eId)); + } + + void setup() { + if (h.solverRunSimplify()) { + simplify(); + } + + // Create node data objects. + for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); + nItr != nEnd; ++nItr) { + nodeDataList.push_back(NodeData()); + g.setNodeData(*nItr, &nodeDataList.back()); + } + + // Create edge data objects. + for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd(); + eItr != eEnd; ++eItr) { + edgeDataList.push_back(EdgeData()); + g.setEdgeData(*eItr, &edgeDataList.back()); + addSolverEdge(*eItr); + } + } + + void simplify() { + disconnectTrivialNodes(); + eliminateIndependentEdges(); + } + + // Eliminate trivial nodes. + void disconnectTrivialNodes() { + unsigned numDisconnected = 0; + + for (Graph::NodeItr nItr = g.nodesBegin(), nEnd = g.nodesEnd(); + nItr != nEnd; ++nItr) { + + Graph::NodeId nId = *nItr; + + if (g.getNodeCosts(nId).getLength() == 1) { + + std::vector edgesToRemove; + + for (Graph::AdjEdgeItr aeItr = g.adjEdgesBegin(nId), + aeEnd = g.adjEdgesEnd(nId); + aeItr != aeEnd; ++aeItr) { + + Graph::EdgeId eId = *aeItr; + + if (g.getEdgeNode1(eId) == nId) { + Graph::NodeId otherNodeId = g.getEdgeNode2(eId); + g.getNodeCosts(otherNodeId) += + g.getEdgeCosts(eId).getRowAsVector(0); + } + else { + Graph::NodeId otherNodeId = g.getEdgeNode1(eId); + g.getNodeCosts(otherNodeId) += + g.getEdgeCosts(eId).getColAsVector(0); + } + + edgesToRemove.push_back(eId); + } + + if (!edgesToRemove.empty()) + ++numDisconnected; + + while (!edgesToRemove.empty()) { + g.removeEdge(edgesToRemove.back()); + edgesToRemove.pop_back(); + } + } + } + } + + void eliminateIndependentEdges() { + std::vector edgesToProcess; + unsigned numEliminated = 0; + + for (Graph::EdgeItr eItr = g.edgesBegin(), eEnd = g.edgesEnd(); + eItr != eEnd; ++eItr) { + edgesToProcess.push_back(*eItr); + } + + while (!edgesToProcess.empty()) { + if (tryToEliminateEdge(edgesToProcess.back())) + ++numEliminated; + edgesToProcess.pop_back(); + } + } + + bool tryToEliminateEdge(Graph::EdgeId eId) { + if (tryNormaliseEdgeMatrix(eId)) { + g.removeEdge(eId); + return true; + } + return false; + } + + bool tryNormaliseEdgeMatrix(Graph::EdgeId &eId) { + + const PBQPNum infinity = std::numeric_limits::infinity(); + + Matrix &edgeCosts = g.getEdgeCosts(eId); + Vector &uCosts = g.getNodeCosts(g.getEdgeNode1(eId)), + &vCosts = g.getNodeCosts(g.getEdgeNode2(eId)); + + for (unsigned r = 0; r < edgeCosts.getRows(); ++r) { + PBQPNum rowMin = infinity; + + for (unsigned c = 0; c < edgeCosts.getCols(); ++c) { + if (vCosts[c] != infinity && edgeCosts[r][c] < rowMin) + rowMin = edgeCosts[r][c]; + } + + uCosts[r] += rowMin; + + if (rowMin != infinity) { + edgeCosts.subFromRow(r, rowMin); + } + else { + edgeCosts.setRow(r, 0); + } + } + + for (unsigned c = 0; c < edgeCosts.getCols(); ++c) { + PBQPNum colMin = infinity; + + for (unsigned r = 0; r < edgeCosts.getRows(); ++r) { + if (uCosts[r] != infinity && edgeCosts[r][c] < colMin) + colMin = edgeCosts[r][c]; + } + + vCosts[c] += colMin; + + if (colMin != infinity) { + edgeCosts.subFromCol(c, colMin); + } + else { + edgeCosts.setCol(c, 0); + } + } + + return edgeCosts.isZero(); + } + + void backpropagate() { + while (!stack.empty()) { + computeSolution(stack.back()); + stack.pop_back(); + } + } + + void computeSolution(Graph::NodeId nId) { + + NodeData &nodeData = getSolverNodeData(nId); + + Vector v(g.getNodeCosts(nId)); + + // Solve based on existing solved edges. + for (SolverEdgeItr solvedEdgeItr = nodeData.solverEdgesBegin(), + solvedEdgeEnd = nodeData.solverEdgesEnd(); + solvedEdgeItr != solvedEdgeEnd; ++solvedEdgeItr) { + + Graph::EdgeId eId(*solvedEdgeItr); + Matrix &edgeCosts = g.getEdgeCosts(eId); + + if (nId == g.getEdgeNode1(eId)) { + Graph::NodeId adjNode(g.getEdgeNode2(eId)); + unsigned adjSolution = s.getSelection(adjNode); + v += edgeCosts.getColAsVector(adjSolution); + } + else { + Graph::NodeId adjNode(g.getEdgeNode1(eId)); + unsigned adjSolution = s.getSelection(adjNode); + v += edgeCosts.getRowAsVector(adjSolution); + } + + } + + setSolution(nId, v.minIndex()); + } + + void cleanup() { + h.cleanup(); + nodeDataList.clear(); + edgeDataList.clear(); + } + }; + + /// \brief PBQP heuristic solver class. + /// + /// Given a PBQP Graph g representing a PBQP problem, you can find a solution + /// by calling + /// Solution s = HeuristicSolver::solve(g); + /// + /// 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 + class HeuristicSolver { + public: + static Solution solve(Graph &g) { + HeuristicSolverImpl hs(g); + return hs.computeSolution(); + } + }; + +} + +#endif // LLVM_CODEGEN_PBQP_HEURISTICSOLVER_H diff --git a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h new file mode 100644 index 00000000000..c355c2c2f81 --- /dev/null +++ b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h @@ -0,0 +1,468 @@ +//===-- 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 "../HeuristicBase.h" +#include "../HeuristicSolver.h" +#include + +namespace PBQP { + 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 { + private: + + class LinkDegreeComparator { + public: + LinkDegreeComparator(HeuristicSolverImpl &s) : s(&s) {} + bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const { + if (s->getSolverDegree(n1Id) > s->getSolverDegree(n2Id)) + return true; + return false; + } + private: + HeuristicSolverImpl *s; + }; + + class SpillCostComparator { + public: + SpillCostComparator(HeuristicSolverImpl &s) + : s(&s), g(&s.getGraph()) {} + bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const { + const PBQP::Vector &cv1 = g->getNodeCosts(n1Id); + const PBQP::Vector &cv2 = g->getNodeCosts(n2Id); + + PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Id); + PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Id); + + if (cost1 < cost2) + return true; + return false; + } + + private: + HeuristicSolverImpl *s; + Graph *g; + }; + + typedef std::list RNAllocableList; + typedef RNAllocableList::iterator RNAllocableListItr; + + typedef std::list RNUnallocableList; + typedef RNUnallocableList::iterator RNUnallocableListItr; + + public: + + struct NodeData { + typedef std::vector UnsafeDegreesArray; + bool isHeuristic, isAllocable, isInitialized; + unsigned numDenied, numSafe; + UnsafeDegreesArray unsafeDegrees; + RNAllocableListItr rnaItr; + RNUnallocableListItr rnuItr; + + NodeData() + : isHeuristic(false), isAllocable(false), isInitialized(false), + numDenied(0), numSafe(0) { } + }; + + struct EdgeData { + typedef std::vector 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 &solver) : + HeuristicBase(solver) {} + + /// \brief Determine whether a node should be reduced using optimal + /// reduction. + /// @param nId Node id 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::NodeId nId) { + if (getSolver().getSolverDegree(nId) < 3) { + return true; + } + // else + return false; + } + + /// \brief Add a node to the heuristic reduce list. + /// @param nId Node id to add to the heuristic reduce list. + void addToHeuristicReduceList(Graph::NodeId nId) { + NodeData &nd = getHeuristicNodeData(nId); + initializeNode(nId); + nd.isHeuristic = true; + if (nd.isAllocable) { + nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nId); + } else { + nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nId); + } + } + + /// \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::NodeId nId = *rnaItr; + rnAllocableList.erase(rnaItr); + handleRemoveNode(nId); + getSolver().pushToStack(nId); + return true; + } else if (!rnUnallocableList.empty()) { + RNUnallocableListItr rnuItr = + min_element(rnUnallocableList.begin(), rnUnallocableList.end(), + SpillCostComparator(getSolver())); + Graph::NodeId nId = *rnuItr; + rnUnallocableList.erase(rnuItr); + handleRemoveNode(nId); + getSolver().pushToStack(nId); + return true; + } + // else + return false; + } + + /// \brief Prepare a change in the costs on the given edge. + /// @param eId Edge id. + void preUpdateEdgeCosts(Graph::EdgeId eId) { + Graph &g = getGraph(); + Graph::NodeId n1Id = g.getEdgeNode1(eId), + n2Id = g.getEdgeNode2(eId); + NodeData &n1 = getHeuristicNodeData(n1Id), + &n2 = getHeuristicNodeData(n2Id); + + if (n1.isHeuristic) + subtractEdgeContributions(eId, getGraph().getEdgeNode1(eId)); + if (n2.isHeuristic) + subtractEdgeContributions(eId, getGraph().getEdgeNode2(eId)); + + EdgeData &ed = getHeuristicEdgeData(eId); + ed.isUpToDate = false; + } + + /// \brief Handle the change in the costs on the given edge. + /// @param eId Edge id. + void postUpdateEdgeCosts(Graph::EdgeId eId) { + // This is effectively the same as adding a new edge now, since + // we've factored out the costs of the old one. + handleAddEdge(eId); + } + + /// \brief Handle the addition of a new edge into the PBQP graph. + /// @param eId Edge id 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::EdgeId eId) { + Graph &g = getGraph(); + Graph::NodeId n1Id = g.getEdgeNode1(eId), + n2Id = g.getEdgeNode2(eId); + NodeData &n1 = getHeuristicNodeData(n1Id), + &n2 = getHeuristicNodeData(n2Id); + + // 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(eId); + + // Update node 1 if it's managed by the heuristic. + if (n1.isHeuristic) { + bool n1WasAllocable = n1.isAllocable; + addEdgeContributions(eId, n1Id); + updateAllocability(n1Id); + if (n1WasAllocable && !n1.isAllocable) { + rnAllocableList.erase(n1.rnaItr); + n1.rnuItr = + rnUnallocableList.insert(rnUnallocableList.end(), n1Id); + } + } + + // Likewise for node 2. + if (n2.isHeuristic) { + bool n2WasAllocable = n2.isAllocable; + addEdgeContributions(eId, n2Id); + updateAllocability(n2Id); + if (n2WasAllocable && !n2.isAllocable) { + rnAllocableList.erase(n2.rnaItr); + n2.rnuItr = + rnUnallocableList.insert(rnUnallocableList.end(), n2Id); + } + } + } + + /// \brief Handle disconnection of an edge from a node. + /// @param eId Edge id for edge being disconnected. + /// @param nId Node id 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::EdgeId eId, Graph::NodeId nId) { + NodeData &nd =getHeuristicNodeData(nId); + + // If the node is not managed by the heuristic there's nothing to be + // done. + if (!nd.isHeuristic) + return; + + EdgeData &ed = getHeuristicEdgeData(eId); + (void)ed; + assert(ed.isUpToDate && "Edge data is not up to date."); + + // Update node. + bool ndWasAllocable = nd.isAllocable; + subtractEdgeContributions(eId, nId); + updateAllocability(nId); + + // If the node has gone optimal... + if (shouldOptimallyReduce(nId)) { + nd.isHeuristic = false; + addToOptimalReduceList(nId); + 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(), nId); + } + } + } + + private: + + NodeData& getHeuristicNodeData(Graph::NodeId nId) { + return getSolver().getHeuristicNodeData(nId); + } + + EdgeData& getHeuristicEdgeData(Graph::EdgeId eId) { + return getSolver().getHeuristicEdgeData(eId); + } + + // Work out what this edge will contribute to the allocability of the + // nodes connected to it. + void computeEdgeContributions(Graph::EdgeId eId) { + EdgeData &ed = getHeuristicEdgeData(eId); + + if (ed.isUpToDate) + return; // Edge data is already up to date. + + Matrix &eCosts = getGraph().getEdgeCosts(eId); + + unsigned numRegs = eCosts.getRows() - 1, + numReverseRegs = eCosts.getCols() - 1; + + std::vector rowInfCounts(numRegs, 0), + colInfCounts(numReverseRegs, 0); + + ed.worst = 0; + ed.reverseWorst = 0; + ed.unsafe.clear(); + ed.unsafe.resize(numRegs, 0); + ed.reverseUnsafe.clear(); + ed.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::infinity()) { + ed.unsafe[i] = 1; + ed.reverseUnsafe[j] = 1; + ++rowInfCounts[i]; + ++colInfCounts[j]; + + if (colInfCounts[j] > ed.worst) { + ed.worst = colInfCounts[j]; + } + + if (rowInfCounts[i] > ed.reverseWorst) { + ed.reverseWorst = rowInfCounts[i]; + } + } + } + } + + 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::EdgeId eId, Graph::NodeId nId) { + EdgeData &ed = getHeuristicEdgeData(eId); + + assert(ed.isUpToDate && "Using out-of-date edge numbers."); + + NodeData &nd = getHeuristicNodeData(nId); + unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1; + + bool nIsNode1 = nId == getGraph().getEdgeNode1(eId); + 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]; + } + } + } + + // 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::EdgeId eId, Graph::NodeId nId) { + EdgeData &ed = getHeuristicEdgeData(eId); + + assert(ed.isUpToDate && "Using out-of-date edge numbers."); + + NodeData &nd = getHeuristicNodeData(nId); + unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1; + + bool nIsNode1 = nId == getGraph().getEdgeNode1(eId); + 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 updateAllocability(Graph::NodeId nId) { + NodeData &nd = getHeuristicNodeData(nId); + unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1; + nd.isAllocable = nd.numDenied < numRegs || nd.numSafe > 0; + } + + void initializeNode(Graph::NodeId nId) { + NodeData &nd = getHeuristicNodeData(nId); + + if (nd.isInitialized) + return; // Node data is already up to date. + + unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1; + + nd.numDenied = 0; + const Vector& nCosts = getGraph().getNodeCosts(nId); + for (unsigned i = 1; i < nCosts.getLength(); ++i) { + if (nCosts[i] == std::numeric_limits::infinity()) + ++nd.numDenied; + } + + nd.numSafe = numRegs; + nd.unsafeDegrees.resize(numRegs, 0); + + typedef HeuristicSolverImpl::SolverEdgeItr SolverEdgeItr; + + for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nId), + aeEnd = getSolver().solverEdgesEnd(nId); + aeItr != aeEnd; ++aeItr) { + + Graph::EdgeId eId = *aeItr; + computeEdgeContributions(eId); + addEdgeContributions(eId, nId); + } + + updateAllocability(nId); + nd.isInitialized = true; + } + + void handleRemoveNode(Graph::NodeId xnId) { + typedef HeuristicSolverImpl::SolverEdgeItr SolverEdgeItr; + std::vector edgesToRemove; + for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnId), + aeEnd = getSolver().solverEdgesEnd(xnId); + aeItr != aeEnd; ++aeItr) { + Graph::NodeId ynId = getGraph().getEdgeOtherNode(*aeItr, xnId); + handleRemoveEdge(*aeItr, ynId); + edgesToRemove.push_back(*aeItr); + } + while (!edgesToRemove.empty()) { + getSolver().removeSolverEdge(edgesToRemove.back()); + edgesToRemove.pop_back(); + } + } + + RNAllocableList rnAllocableList; + RNUnallocableList rnUnallocableList; + }; + + } +} + + +#endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H diff --git a/include/llvm/CodeGen/PBQP/Math.h b/include/llvm/CodeGen/PBQP/Math.h index 69a9d83cc09..08f8b981ae2 100644 --- a/include/llvm/CodeGen/PBQP/Math.h +++ b/include/llvm/CodeGen/PBQP/Math.h @@ -20,418 +20,268 @@ typedef float PBQPNum; /// \brief PBQP Vector class. class Vector { - friend class VectorComparator; -public: - - /// \brief Construct a PBQP vector of the given size. - explicit Vector(unsigned Length) - : Length(Length), Data(new PBQPNum[Length]) { - // llvm::dbgs() << "Constructing PBQP::Vector " - // << this << " (length " << Length << ")\n"; - } - - /// \brief Construct a PBQP vector with initializer. - Vector(unsigned Length, PBQPNum InitVal) - : Length(Length), Data(new PBQPNum[Length]) { - // llvm::dbgs() << "Constructing PBQP::Vector " - // << this << " (length " << Length << ", fill " - // << InitVal << ")\n"; - std::fill(Data, Data + Length, InitVal); - } - - /// \brief Copy construct a PBQP vector. - Vector(const Vector &V) - : Length(V.Length), Data(new PBQPNum[Length]) { - // llvm::dbgs() << "Copy-constructing PBQP::Vector " << this - // << " from PBQP::Vector " << &V << "\n"; - std::copy(V.Data, V.Data + Length, Data); - } - - /// \brief Move construct a PBQP vector. - Vector(Vector &&V) - : Length(V.Length), Data(V.Data) { - V.Length = 0; - V.Data = nullptr; - } - - /// \brief Destroy this vector, return its memory. - ~Vector() { - // llvm::dbgs() << "Deleting PBQP::Vector " << this << "\n"; - delete[] Data; - } - - /// \brief Copy-assignment operator. - Vector& operator=(const Vector &V) { - // llvm::dbgs() << "Assigning to PBQP::Vector " << this - // << " from PBQP::Vector " << &V << "\n"; - delete[] Data; - Length = V.Length; - Data = new PBQPNum[Length]; - std::copy(V.Data, V.Data + Length, Data); - return *this; - } - - /// \brief Move-assignment operator. - Vector& operator=(Vector &&V) { - delete[] Data; - Length = V.Length; - Data = V.Data; - V.Length = 0; - V.Data = nullptr; - return *this; - } - - /// \brief Comparison operator. - bool operator==(const Vector &V) const { - assert(Length != 0 && Data != nullptr && "Invalid vector"); - if (Length != V.Length) - return false; - return std::equal(Data, Data + Length, V.Data); - } - - /// \brief Return the length of the vector - unsigned getLength() const { - assert(Length != 0 && Data != nullptr && "Invalid vector"); - return Length; - } - - /// \brief Element access. - PBQPNum& operator[](unsigned Index) { - assert(Length != 0 && Data != nullptr && "Invalid vector"); - assert(Index < Length && "Vector element access out of bounds."); - return Data[Index]; - } - - /// \brief Const element access. - const PBQPNum& operator[](unsigned Index) const { - assert(Length != 0 && Data != nullptr && "Invalid vector"); - 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 != 0 && Data != nullptr && "Invalid vector"); - assert(Length == V.Length && "Vector length mismatch."); - std::transform(Data, Data + Length, V.Data, Data, std::plus()); - return *this; - } - - /// \brief Subtract another vector from this one. - Vector& operator-=(const Vector &V) { - assert(Length != 0 && Data != nullptr && "Invalid vector"); - assert(Length == V.Length && "Vector length mismatch."); - std::transform(Data, Data + Length, V.Data, Data, std::minus()); - return *this; - } - - /// \brief Returns the index of the minimum value in this vector - unsigned minIndex() const { - assert(Length != 0 && Data != nullptr && "Invalid vector"); - return std::min_element(Data, Data + Length) - Data; - } - -private: - unsigned Length; - PBQPNum *Data; -}; - -class VectorComparator { -public: - bool operator()(const Vector &A, const Vector &B) { - if (A.Length < B.Length) - return true; - if (B.Length < A.Length) - return false; - char *AData = reinterpret_cast(A.Data); - char *BData = reinterpret_cast(B.Data); - return std::lexicographical_compare(AData, - AData + A.Length * sizeof(PBQPNum), - BData, - BData + A.Length * sizeof(PBQPNum)); - } + 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()); + 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()); + 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 -OStream& operator<<(OStream &OS, const Vector &V) { - assert((V.getLength() != 0) && "Zero-length vector badness."); +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 << " ]"; + os << "[ " << v[0]; + for (unsigned i = 1; i < v.getLength(); ++i) { + os << ", " << v[i]; + } + os << " ]"; - return OS; -} + return os; +} /// \brief PBQP Matrix class class Matrix { -private: - friend class MatrixComparator; -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 Move construct a PBQP matrix. - Matrix(Matrix &&M) - : Rows(M.Rows), Cols(M.Cols), Data(M.Data) { - M.Rows = M.Cols = 0; - M.Data = nullptr; - } - - /// \brief Destroy this matrix, return its memory. - ~Matrix() { delete[] Data; } - - /// \brief Copy-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 Move-assignment operator. - Matrix& operator=(Matrix &&M) { - delete[] Data; - Rows = M.Rows; - Cols = M.Cols; - Data = M.Data; - M.Rows = M.Cols = 0; - M.Data = nullptr; - return *this; - } - - /// \brief Comparison operator. - bool operator==(const Matrix &M) const { - assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - if (Rows != M.Rows || Cols != M.Cols) - return false; - return std::equal(Data, Data + (Rows * Cols), M.Data); - } - - /// \brief Return the number of rows in this matrix. - unsigned getRows() const { - assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - return Rows; - } - - /// \brief Return the number of cols in this matrix. - unsigned getCols() const { - assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - return Cols; - } - - /// \brief Matrix element access. - PBQPNum* operator[](unsigned R) { - assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - assert(R < Rows && "Row out of bounds."); - return Data + (R * Cols); - } - - /// \brief Matrix element access. - const PBQPNum* operator[](unsigned R) const { - assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - assert(R < Rows && "Row out of bounds."); - return Data + (R * Cols); - } - - /// \brief Returns the given row as a vector. - Vector getRowAsVector(unsigned R) const { - assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - 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 { - assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - 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) { - assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - 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(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - 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(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - 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 { - assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - 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 != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - 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 != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - assert(Rows == M.Rows && Cols == M.Cols && - "Matrix dimensions mismatch."); - std::transform(Data, Data + (Rows * Cols), M.Data, Data, - std::plus()); - return *this; - } - - Matrix operator+(const Matrix &M) { - assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - Matrix Tmp(*this); - Tmp += M; - return Tmp; - } - - /// \brief Returns the minimum of the given row - PBQPNum getRowMin(unsigned R) const { - assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - 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 { - assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - 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(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - assert(R < Rows && "Row out of bounds"); - std::transform(Data + (R * Cols), Data + ((R + 1) * Cols), - Data + (R * Cols), - std::bind2nd(std::minus(), Val)); - return *this; - } - - /// \brief Subtracts the given scalar from the elements of the given column. - Matrix& subFromCol(unsigned C, PBQPNum Val) { - assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - 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 { - assert(Rows != 0 && Cols != 0 && Data != nullptr && "Invalid matrix"); - return find_if(Data, Data + (Rows * Cols), - std::bind2nd(std::not_equal_to(), 0)) == - Data + (Rows * Cols); - } - -private: - unsigned Rows, Cols; - PBQPNum *Data; -}; - -class MatrixComparator { -public: - bool operator()(const Matrix &A, const Matrix &B) { - if (A.Rows < B.Rows) - return true; - if (B.Rows < A.Rows) - return false; - if (A.Cols < B.Cols) - return true; - if (B.Cols < A.Cols) - return false; - char *AData = reinterpret_cast(A.Data); - char *BData = reinterpret_cast(B.Data); - return std::lexicographical_compare( - AData, AData + (A.Rows * A.Cols * sizeof(PBQPNum)), - BData, BData + (A.Rows * A.Cols * sizeof(PBQPNum))); - } + 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()); + 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(), 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(), 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 -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; -} +OStream& operator<<(OStream &os, const Matrix &m) { -template -class MDVector : public Vector { -public: - MDVector(const Vector &v) : Vector(v), md(*this) { } - MDVector(Vector &&v) : Vector(std::move(v)), md(*this) { } - const Metadata& getMetadata() const { return md; } -private: - Metadata md; -}; + assert((m.getRows() != 0) && "Zero-row matrix badness."); -template -class MDMatrix : public Matrix { -public: - MDMatrix(const Matrix &m) : Matrix(m), md(*this) { } - MDMatrix(Matrix &&m) : Matrix(std::move(m)), md(*this) { } - const Metadata& getMetadata() const { return md; } -private: - Metadata md; -}; + for (unsigned i = 0; i < m.getRows(); ++i) { + os << m.getRowAsVector(i); + } + + return os; +} } diff --git a/include/llvm/CodeGen/PBQP/ReductionRules.h b/include/llvm/CodeGen/PBQP/ReductionRules.h deleted file mode 100644 index a259c853279..00000000000 --- a/include/llvm/CodeGen/PBQP/ReductionRules.h +++ /dev/null @@ -1,194 +0,0 @@ -//===----------- ReductionRules.h - Reduction Rules -------------*- C++ -*-===// -// -// The LLVM Compiler Infrastructure -// -// This file is distributed under the University of Illinois Open Source -// License. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// -// -// Reduction Rules. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_REDUCTIONRULES_H -#define LLVM_REDUCTIONRULES_H - -#include "Graph.h" -#include "Math.h" -#include "Solution.h" - -namespace PBQP { - - /// \brief Reduce a node of degree one. - /// - /// Propagate costs from the given node, which must be of degree one, to its - /// neighbor. Notify the problem domain. - template - void applyR1(GraphT &G, typename GraphT::NodeId NId) { - typedef typename GraphT::NodeId NodeId; - typedef typename GraphT::EdgeId EdgeId; - typedef typename GraphT::Vector Vector; - typedef typename GraphT::Matrix Matrix; - typedef typename GraphT::RawVector RawVector; - - assert(G.getNodeDegree(NId) == 1 && - "R1 applied to node with degree != 1."); - - EdgeId EId = *G.adjEdgeIds(NId).begin(); - NodeId MId = G.getEdgeOtherNodeId(EId, NId); - - const Matrix &ECosts = G.getEdgeCosts(EId); - const Vector &XCosts = G.getNodeCosts(NId); - RawVector YCosts = G.getNodeCosts(MId); - - // Duplicate a little to avoid transposing matrices. - if (NId == G.getEdgeNode1Id(EId)) { - 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; - } - } else { - 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; - } - } - G.setNodeCosts(MId, YCosts); - G.disconnectEdge(EId, MId); - } - - template - void applyR2(GraphT &G, typename GraphT::NodeId NId) { - typedef typename GraphT::NodeId NodeId; - typedef typename GraphT::EdgeId EdgeId; - typedef typename GraphT::Vector Vector; - typedef typename GraphT::Matrix Matrix; - typedef typename GraphT::RawMatrix RawMatrix; - - assert(G.getNodeDegree(NId) == 2 && - "R2 applied to node with degree != 2."); - - const Vector &XCosts = G.getNodeCosts(NId); - - typename GraphT::AdjEdgeItr AEItr = G.adjEdgeIds(NId).begin(); - EdgeId YXEId = *AEItr, - ZXEId = *(++AEItr); - - NodeId YNId = G.getEdgeOtherNodeId(YXEId, NId), - ZNId = G.getEdgeOtherNodeId(ZXEId, NId); - - bool FlipEdge1 = (G.getEdgeNode1Id(YXEId) == NId), - FlipEdge2 = (G.getEdgeNode1Id(ZXEId) == NId); - - const Matrix *YXECosts = FlipEdge1 ? - new Matrix(G.getEdgeCosts(YXEId).transpose()) : - &G.getEdgeCosts(YXEId); - - const Matrix *ZXECosts = FlipEdge2 ? - new Matrix(G.getEdgeCosts(ZXEId).transpose()) : - &G.getEdgeCosts(ZXEId); - - unsigned XLen = XCosts.getLength(), - YLen = YXECosts->getRows(), - ZLen = ZXECosts->getRows(); - - RawMatrix Delta(YLen, ZLen); - - 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; - } - } - Delta[i][j] = Min; - } - } - - if (FlipEdge1) - delete YXECosts; - - if (FlipEdge2) - delete ZXECosts; - - EdgeId YZEId = G.findEdge(YNId, ZNId); - bool AddedEdge = false; - - if (YZEId == G.invalidEdgeId()) { - YZEId = G.addEdge(YNId, ZNId, Delta); - AddedEdge = true; - } else { - const Matrix &YZECosts = G.getEdgeCosts(YZEId); - if (YNId == G.getEdgeNode1Id(YZEId)) { - G.setEdgeCosts(YZEId, Delta + YZECosts); - } else { - G.setEdgeCosts(YZEId, Delta.transpose() + YZECosts); - } - } - - G.disconnectEdge(YXEId, YNId); - G.disconnectEdge(ZXEId, ZNId); - - // TODO: Try to normalize newly added/modified edge. - } - - - // \brief Find a solution to a fully reduced graph by backpropagation. - // - // Given a graph and a reduction order, pop each node from the reduction - // order and greedily compute a minimum solution based on the node costs, and - // the dependent costs due to previously solved nodes. - // - // Note - This does not return the graph to its original (pre-reduction) - // state: the existing solvers destructively alter the node and edge - // costs. Given that, the backpropagate function doesn't attempt to - // replace the edges either, but leaves the graph in its reduced - // state. - template - Solution backpropagate(GraphT& G, StackT stack) { - typedef GraphBase::NodeId NodeId; - typedef GraphBase::EdgeId EdgeId; - typedef typename GraphT::Matrix Matrix; - typedef typename GraphT::RawVector RawVector; - - Solution s; - - while (!stack.empty()) { - NodeId NId = stack.back(); - stack.pop_back(); - - RawVector v = G.getNodeCosts(NId); - - for (auto EId : G.adjEdgeIds(NId)) { - const Matrix& edgeCosts = G.getEdgeCosts(EId); - if (NId == G.getEdgeNode1Id(EId)) { - NodeId mId = G.getEdgeNode2Id(EId); - v += edgeCosts.getColAsVector(s.getSelection(mId)); - } else { - NodeId mId = G.getEdgeNode1Id(EId); - v += edgeCosts.getRowAsVector(s.getSelection(mId)); - } - } - - s.setSelection(NId, v.minIndex()); - } - - return s; - } - -} - -#endif // LLVM_REDUCTIONRULES_H diff --git a/include/llvm/CodeGen/PBQP/RegAllocSolver.h b/include/llvm/CodeGen/PBQP/RegAllocSolver.h deleted file mode 100644 index 80eba31b8c0..00000000000 --- a/include/llvm/CodeGen/PBQP/RegAllocSolver.h +++ /dev/null @@ -1,359 +0,0 @@ -//===-- RegAllocSolver.h - Heuristic PBQP Solver for reg alloc --*- 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 for register allocation problems. This solver uses a -// graph reduction approach. Nodes of degree 0, 1 and 2 are eliminated with -// optimality-preserving rules (see ReductionRules.h). When no low-degree (<3) -// nodes are present, a heuristic derived from Brigg's graph coloring approach -// is used. -// -//===----------------------------------------------------------------------===// - -#ifndef LLVM_CODEGEN_PBQP_REGALLOCSOLVER_H -#define LLVM_CODEGEN_PBQP_REGALLOCSOLVER_H - -#include "CostAllocator.h" -#include "Graph.h" -#include "ReductionRules.h" -#include "Solution.h" -#include "llvm/Support/ErrorHandling.h" -#include -#include - -namespace PBQP { - - namespace RegAlloc { - - /// \brief Metadata to speed allocatability test. - /// - /// Keeps track of the number of infinities in each row and column. - class MatrixMetadata { - private: - MatrixMetadata(const MatrixMetadata&); - void operator=(const MatrixMetadata&); - public: - MatrixMetadata(const PBQP::Matrix& m) - : worstRow(0), worstCol(0), - unsafeRows(new bool[m.getRows() - 1]()), - unsafeCols(new bool[m.getCols() - 1]()) { - - unsigned* colCounts = new unsigned[m.getCols() - 1](); - - for (unsigned i = 1; i < m.getRows(); ++i) { - unsigned rowCount = 0; - for (unsigned j = 1; j < m.getCols(); ++j) { - if (m[i][j] == std::numeric_limits::infinity()) { - ++rowCount; - ++colCounts[j - 1]; - unsafeRows[i - 1] = true; - unsafeCols[j - 1] = true; - } - } - worstRow = std::max(worstRow, rowCount); - } - unsigned worstColCountForCurRow = - *std::max_element(colCounts, colCounts + m.getCols() - 1); - worstCol = std::max(worstCol, worstColCountForCurRow); - delete[] colCounts; - } - - ~MatrixMetadata() { - delete[] unsafeRows; - delete[] unsafeCols; - } - - unsigned getWorstRow() const { return worstRow; } - unsigned getWorstCol() const { return worstCol; } - const bool* getUnsafeRows() const { return unsafeRows; } - const bool* getUnsafeCols() const { return unsafeCols; } - - private: - unsigned worstRow, worstCol; - bool* unsafeRows; - bool* unsafeCols; - }; - - class NodeMetadata { - public: - typedef enum { Unprocessed, - OptimallyReducible, - ConservativelyAllocatable, - NotProvablyAllocatable } ReductionState; - - NodeMetadata() : rs(Unprocessed), deniedOpts(0), optUnsafeEdges(0) {} - ~NodeMetadata() { delete[] optUnsafeEdges; } - - void setup(const Vector& costs) { - numOpts = costs.getLength() - 1; - optUnsafeEdges = new unsigned[numOpts](); - } - - ReductionState getReductionState() const { return rs; } - void setReductionState(ReductionState rs) { this->rs = rs; } - - void handleAddEdge(const MatrixMetadata& md, bool transpose) { - deniedOpts += transpose ? md.getWorstCol() : md.getWorstRow(); - const bool* unsafeOpts = - transpose ? md.getUnsafeCols() : md.getUnsafeRows(); - for (unsigned i = 0; i < numOpts; ++i) - optUnsafeEdges[i] += unsafeOpts[i]; - } - - void handleRemoveEdge(const MatrixMetadata& md, bool transpose) { - deniedOpts -= transpose ? md.getWorstCol() : md.getWorstRow(); - const bool* unsafeOpts = - transpose ? md.getUnsafeCols() : md.getUnsafeRows(); - for (unsigned i = 0; i < numOpts; ++i) - optUnsafeEdges[i] -= unsafeOpts[i]; - } - - bool isConservativelyAllocatable() const { - return (deniedOpts < numOpts) || - (std::find(optUnsafeEdges, optUnsafeEdges + numOpts, 0) != - optUnsafeEdges + numOpts); - } - - private: - ReductionState rs; - unsigned numOpts; - unsigned deniedOpts; - unsigned* optUnsafeEdges; - }; - - class RegAllocSolverImpl { - private: - typedef PBQP::MDMatrix RAMatrix; - public: - typedef PBQP::Vector RawVector; - typedef PBQP::Matrix RawMatrix; - typedef PBQP::Vector Vector; - typedef RAMatrix Matrix; - typedef PBQP::PoolCostAllocator< - Vector, PBQP::VectorComparator, - Matrix, PBQP::MatrixComparator> CostAllocator; - - typedef PBQP::GraphBase::NodeId NodeId; - typedef PBQP::GraphBase::EdgeId EdgeId; - - typedef RegAlloc::NodeMetadata NodeMetadata; - - struct EdgeMetadata { }; - - typedef PBQP::Graph Graph; - - RegAllocSolverImpl(Graph &G) : G(G) {} - - Solution solve() { - G.setSolver(*this); - Solution S; - setup(); - S = backpropagate(G, reduce()); - G.unsetSolver(); - return S; - } - - void handleAddNode(NodeId NId) { - G.getNodeMetadata(NId).setup(G.getNodeCosts(NId)); - } - void handleRemoveNode(NodeId NId) {} - void handleSetNodeCosts(NodeId NId, const Vector& newCosts) {} - - void handleAddEdge(EdgeId EId) { - handleReconnectEdge(EId, G.getEdgeNode1Id(EId)); - handleReconnectEdge(EId, G.getEdgeNode2Id(EId)); - } - - void handleRemoveEdge(EdgeId EId) { - handleDisconnectEdge(EId, G.getEdgeNode1Id(EId)); - handleDisconnectEdge(EId, G.getEdgeNode2Id(EId)); - } - - void handleDisconnectEdge(EdgeId EId, NodeId NId) { - NodeMetadata& nMd = G.getNodeMetadata(NId); - const MatrixMetadata& mMd = G.getEdgeCosts(EId).getMetadata(); - nMd.handleRemoveEdge(mMd, NId == G.getEdgeNode2Id(EId)); - if (G.getNodeDegree(NId) == 3) { - // This node is becoming optimally reducible. - moveToOptimallyReducibleNodes(NId); - } else if (nMd.getReductionState() == - NodeMetadata::NotProvablyAllocatable && - nMd.isConservativelyAllocatable()) { - // This node just became conservatively allocatable. - moveToConservativelyAllocatableNodes(NId); - } - } - - void handleReconnectEdge(EdgeId EId, NodeId NId) { - NodeMetadata& nMd = G.getNodeMetadata(NId); - const MatrixMetadata& mMd = G.getEdgeCosts(EId).getMetadata(); - nMd.handleAddEdge(mMd, NId == G.getEdgeNode2Id(EId)); - } - - void handleSetEdgeCosts(EdgeId EId, const Matrix& NewCosts) { - handleRemoveEdge(EId); - - NodeId n1Id = G.getEdgeNode1Id(EId); - NodeId n2Id = G.getEdgeNode2Id(EId); - NodeMetadata& n1Md = G.getNodeMetadata(n1Id); - NodeMetadata& n2Md = G.getNodeMetadata(n2Id); - const MatrixMetadata& mMd = NewCosts.getMetadata(); - n1Md.handleAddEdge(mMd, n1Id != G.getEdgeNode1Id(EId)); - n2Md.handleAddEdge(mMd, n2Id != G.getEdgeNode1Id(EId)); - } - - private: - - void removeFromCurrentSet(NodeId NId) { - switch (G.getNodeMetadata(NId).getReductionState()) { - case NodeMetadata::Unprocessed: break; - case NodeMetadata::OptimallyReducible: - assert(OptimallyReducibleNodes.find(NId) != - OptimallyReducibleNodes.end() && - "Node not in optimally reducible set."); - OptimallyReducibleNodes.erase(NId); - break; - case NodeMetadata::ConservativelyAllocatable: - assert(ConservativelyAllocatableNodes.find(NId) != - ConservativelyAllocatableNodes.end() && - "Node not in conservatively allocatable set."); - ConservativelyAllocatableNodes.erase(NId); - break; - case NodeMetadata::NotProvablyAllocatable: - assert(NotProvablyAllocatableNodes.find(NId) != - NotProvablyAllocatableNodes.end() && - "Node not in not-provably-allocatable set."); - NotProvablyAllocatableNodes.erase(NId); - break; - } - } - - void moveToOptimallyReducibleNodes(NodeId NId) { - removeFromCurrentSet(NId); - OptimallyReducibleNodes.insert(NId); - G.getNodeMetadata(NId).setReductionState( - NodeMetadata::OptimallyReducible); - } - - void moveToConservativelyAllocatableNodes(NodeId NId) { - removeFromCurrentSet(NId); - ConservativelyAllocatableNodes.insert(NId); - G.getNodeMetadata(NId).setReductionState( - NodeMetadata::ConservativelyAllocatable); - } - - void moveToNotProvablyAllocatableNodes(NodeId NId) { - removeFromCurrentSet(NId); - NotProvablyAllocatableNodes.insert(NId); - G.getNodeMetadata(NId).setReductionState( - NodeMetadata::NotProvablyAllocatable); - } - - void setup() { - // Set up worklists. - for (auto NId : G.nodeIds()) { - if (G.getNodeDegree(NId) < 3) - moveToOptimallyReducibleNodes(NId); - else if (G.getNodeMetadata(NId).isConservativelyAllocatable()) - moveToConservativelyAllocatableNodes(NId); - else - moveToNotProvablyAllocatableNodes(NId); - } - } - - // Compute a reduction order for the graph by iteratively applying PBQP - // reduction rules. Locally optimal rules are applied whenever possible (R0, - // R1, R2). If no locally-optimal rules apply then any conservatively - // allocatable node is reduced. Finally, if no conservatively allocatable - // node exists then the node with the lowest spill-cost:degree ratio is - // selected. - std::vector reduce() { - assert(!G.empty() && "Cannot reduce empty graph."); - - typedef GraphBase::NodeId NodeId; - std::vector NodeStack; - - // Consume worklists. - while (true) { - if (!OptimallyReducibleNodes.empty()) { - NodeSet::iterator nItr = OptimallyReducibleNodes.begin(); - NodeId NId = *nItr; - OptimallyReducibleNodes.erase(nItr); - NodeStack.push_back(NId); - switch (G.getNodeDegree(NId)) { - case 0: - break; - case 1: - applyR1(G, NId); - break; - case 2: - applyR2(G, NId); - break; - default: llvm_unreachable("Not an optimally reducible node."); - } - } else if (!ConservativelyAllocatableNodes.empty()) { - // Conservatively allocatable nodes will never spill. For now just - // take the first node in the set and push it on the stack. When we - // start optimizing more heavily for register preferencing, it may - // would be better to push nodes with lower 'expected' or worst-case - // register costs first (since early nodes are the most - // constrained). - NodeSet::iterator nItr = ConservativelyAllocatableNodes.begin(); - NodeId NId = *nItr; - ConservativelyAllocatableNodes.erase(nItr); - NodeStack.push_back(NId); - G.disconnectAllNeighborsFromNode(NId); - - } else if (!NotProvablyAllocatableNodes.empty()) { - NodeSet::iterator nItr = - std::min_element(NotProvablyAllocatableNodes.begin(), - NotProvablyAllocatableNodes.end(), - SpillCostComparator(G)); - NodeId NId = *nItr; - NotProvablyAllocatableNodes.erase(nItr); - NodeStack.push_back(NId); - G.disconnectAllNeighborsFromNode(NId); - } else - break; - } - - return NodeStack; - } - - class SpillCostComparator { - public: - SpillCostComparator(const Graph& G) : G(G) {} - bool operator()(NodeId N1Id, NodeId N2Id) { - PBQPNum N1SC = G.getNodeCosts(N1Id)[0] / G.getNodeDegree(N1Id); - PBQPNum N2SC = G.getNodeCosts(N2Id)[0] / G.getNodeDegree(N2Id); - return N1SC < N2SC; - } - private: - const Graph& G; - }; - - Graph& G; - typedef std::set NodeSet; - NodeSet OptimallyReducibleNodes; - NodeSet ConservativelyAllocatableNodes; - NodeSet NotProvablyAllocatableNodes; - }; - - typedef Graph Graph; - - Solution solve(Graph& G) { - if (G.empty()) - return Solution(); - RegAllocSolverImpl RegAllocSolver(G); - return RegAllocSolver.solve(); - } - - } -} - -#endif // LLVM_CODEGEN_PBQP_REGALLOCSOLVER_H diff --git a/include/llvm/CodeGen/PBQP/Solution.h b/include/llvm/CodeGen/PBQP/Solution.h index 3556e60f396..091805d00f3 100644 --- a/include/llvm/CodeGen/PBQP/Solution.h +++ b/include/llvm/CodeGen/PBQP/Solution.h @@ -26,7 +26,7 @@ namespace PBQP { class Solution { private: - typedef std::map SelectionsMap; + typedef std::map SelectionsMap; SelectionsMap selections; unsigned r0Reductions, r1Reductions, r2Reductions, rNReductions; @@ -72,14 +72,14 @@ namespace PBQP { /// \brief Set the selection for a given node. /// @param nodeId Node id. /// @param selection Selection for nodeId. - void setSelection(GraphBase::NodeId nodeId, unsigned selection) { + void setSelection(Graph::NodeId nodeId, unsigned selection) { selections[nodeId] = selection; } /// \brief Get a node's selection. /// @param nodeId Node id. /// @return The selection for nodeId; - unsigned getSelection(GraphBase::NodeId nodeId) const { + unsigned getSelection(Graph::NodeId nodeId) const { SelectionsMap::const_iterator sItr = selections.find(nodeId); assert(sItr != selections.end() && "No selection for node."); return sItr->second; diff --git a/include/llvm/CodeGen/RegAllocPBQP.h b/include/llvm/CodeGen/RegAllocPBQP.h index 40539dcab28..7472e5a62d6 100644 --- a/include/llvm/CodeGen/RegAllocPBQP.h +++ b/include/llvm/CodeGen/RegAllocPBQP.h @@ -17,9 +17,9 @@ #define LLVM_CODEGEN_REGALLOCPBQP_H #include "llvm/ADT/DenseMap.h" -#include "llvm/ADT/SmallVector.h" #include "llvm/CodeGen/MachineFunctionPass.h" -#include "llvm/CodeGen/PBQP/RegAllocSolver.h" +#include "llvm/CodeGen/PBQP/Graph.h" +#include "llvm/CodeGen/PBQP/Solution.h" #include #include @@ -31,29 +31,28 @@ namespace llvm { class TargetRegisterInfo; template class OwningPtr; - typedef PBQP::RegAlloc::Graph PBQPRAGraph; - /// This class wraps up a PBQP instance representing a register allocation /// problem, plus the structures necessary to map back from the PBQP solution /// to a register allocation solution. (i.e. The PBQP-node <--> vreg map, /// and the PBQP option <--> storage location map). + class PBQPRAProblem { public: typedef SmallVector AllowedSet; - PBQPRAGraph& getGraph() { return graph; } + PBQP::Graph& getGraph() { return graph; } - const PBQPRAGraph& getGraph() const { return graph; } + const PBQP::Graph& getGraph() const { return graph; } /// Record the mapping between the given virtual register and PBQP node, /// and the set of allowed pregs for the vreg. /// /// If you are extending /// PBQPBuilder you are unlikely to need this: Nodes and options for all - /// vregs will already have been set up for you by the base class. + /// vregs will already have been set up for you by the base class. template - void recordVReg(unsigned vreg, PBQPRAGraph::NodeId nodeId, + void recordVReg(unsigned vreg, PBQP::Graph::NodeId nodeId, AllowedRegsItr arBegin, AllowedRegsItr arEnd) { assert(node2VReg.find(nodeId) == node2VReg.end() && "Re-mapping node."); assert(vreg2Node.find(vreg) == vreg2Node.end() && "Re-mapping vreg."); @@ -65,10 +64,10 @@ namespace llvm { } /// Get the virtual register corresponding to the given PBQP node. - unsigned getVRegForNode(PBQPRAGraph::NodeId nodeId) const; + unsigned getVRegForNode(PBQP::Graph::NodeId nodeId) const; /// Get the PBQP node corresponding to the given virtual register. - PBQPRAGraph::NodeId getNodeForVReg(unsigned vreg) const; + PBQP::Graph::NodeId getNodeForVReg(unsigned vreg) const; /// Returns true if the given PBQP option represents a physical register, /// false otherwise. @@ -93,16 +92,16 @@ namespace llvm { private: - typedef std::map Node2VReg; - typedef DenseMap VReg2Node; + typedef std::map Node2VReg; + typedef DenseMap VReg2Node; typedef DenseMap AllowedSetMap; - PBQPRAGraph graph; + PBQP::Graph graph; Node2VReg node2VReg; VReg2Node vreg2Node; AllowedSetMap allowedSets; - + }; /// Builds PBQP instances to represent register allocation problems. Includes @@ -115,7 +114,7 @@ namespace llvm { public: typedef std::set RegSet; - + /// Default constructor. PBQPBuilder() {} @@ -140,12 +139,12 @@ namespace llvm { /// Extended builder which adds coalescing constraints to a problem. class PBQPBuilderWithCoalescing : public PBQPBuilder { public: - + /// Build a PBQP instance to represent the register allocation problem for /// the given MachineFunction. virtual PBQPRAProblem *build(MachineFunction *mf, const LiveIntervals *lis, const MachineBlockFrequencyInfo *mbfi, - const RegSet &vregs); + const RegSet &vregs); private: diff --git a/lib/CodeGen/RegAllocPBQP.cpp b/lib/CodeGen/RegAllocPBQP.cpp index dafd1b08a86..347329591b5 100644 --- a/lib/CodeGen/RegAllocPBQP.cpp +++ b/lib/CodeGen/RegAllocPBQP.cpp @@ -45,6 +45,9 @@ #include "llvm/CodeGen/MachineFunctionPass.h" #include "llvm/CodeGen/MachineLoopInfo.h" #include "llvm/CodeGen/MachineRegisterInfo.h" +#include "llvm/CodeGen/PBQP/Graph.h" +#include "llvm/CodeGen/PBQP/HeuristicSolver.h" +#include "llvm/CodeGen/PBQP/Heuristics/Briggs.h" #include "llvm/CodeGen/RegAllocRegistry.h" #include "llvm/CodeGen/VirtRegMap.h" #include "llvm/IR/Module.h" @@ -154,13 +157,13 @@ char RegAllocPBQP::ID = 0; } // End anonymous namespace. -unsigned PBQPRAProblem::getVRegForNode(PBQPRAGraph::NodeId node) const { +unsigned PBQPRAProblem::getVRegForNode(PBQP::Graph::NodeId node) const { Node2VReg::const_iterator vregItr = node2VReg.find(node); assert(vregItr != node2VReg.end() && "No vreg for node."); return vregItr->second; } -PBQPRAGraph::NodeId PBQPRAProblem::getNodeForVReg(unsigned vreg) const { +PBQP::Graph::NodeId PBQPRAProblem::getNodeForVReg(unsigned vreg) const { VReg2Node::const_iterator nodeItr = vreg2Node.find(vreg); assert(nodeItr != vreg2Node.end() && "No node for vreg."); return nodeItr->second; @@ -192,7 +195,7 @@ PBQPRAProblem *PBQPBuilder::build(MachineFunction *mf, const LiveIntervals *lis, const TargetRegisterInfo *tri = mf->getTarget().getRegisterInfo(); OwningPtr p(new PBQPRAProblem()); - PBQPRAGraph &g = p->getGraph(); + PBQP::Graph &g = p->getGraph(); RegSet pregs; // Collect the set of preg intervals, record that they're used in the MF. @@ -242,19 +245,17 @@ PBQPRAProblem *PBQPBuilder::build(MachineFunction *mf, const LiveIntervals *lis, vrAllowed.push_back(preg); } - PBQP::Vector nodeCosts(vrAllowed.size() + 1, 0); - - PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ? - vregLI->weight : std::numeric_limits::min(); - - addSpillCosts(nodeCosts, spillCost); - // Construct the node. - PBQPRAGraph::NodeId nId = g.addNode(std::move(nodeCosts)); + PBQP::Graph::NodeId node = + g.addNode(PBQP::Vector(vrAllowed.size() + 1, 0)); // Record the mapping and allowed set in the problem. - p->recordVReg(vreg, nId, vrAllowed.begin(), vrAllowed.end()); + p->recordVReg(vreg, node, vrAllowed.begin(), vrAllowed.end()); + PBQP::PBQPNum spillCost = (vregLI->weight != 0.0) ? + vregLI->weight : std::numeric_limits::min(); + + addSpillCosts(g.getNodeCosts(node), spillCost); } for (RegSet::const_iterator vr1Itr = vregs.begin(), vrEnd = vregs.end(); @@ -271,11 +272,11 @@ PBQPRAProblem *PBQPBuilder::build(MachineFunction *mf, const LiveIntervals *lis, assert(!l2.empty() && "Empty interval in vreg set?"); if (l1.overlaps(l2)) { - PBQP::Matrix edgeCosts(vr1Allowed.size()+1, vr2Allowed.size()+1, 0); - addInterferenceCosts(edgeCosts, vr1Allowed, vr2Allowed, tri); + PBQP::Graph::EdgeId edge = + g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2), + PBQP::Matrix(vr1Allowed.size()+1, vr2Allowed.size()+1, 0)); - g.addEdge(p->getNodeForVReg(vr1), p->getNodeForVReg(vr2), - std::move(edgeCosts)); + addInterferenceCosts(g.getEdgeCosts(edge), vr1Allowed, vr2Allowed, tri); } } } @@ -315,7 +316,7 @@ PBQPRAProblem *PBQPBuilderWithCoalescing::build(MachineFunction *mf, const RegSet &vregs) { OwningPtr p(PBQPBuilder::build(mf, lis, mbfi, vregs)); - PBQPRAGraph &g = p->getGraph(); + PBQP::Graph &g = p->getGraph(); const TargetMachine &tm = mf->getTarget(); CoalescerPair cp(*tm.getRegisterInfo()); @@ -361,32 +362,28 @@ PBQPRAProblem *PBQPBuilderWithCoalescing::build(MachineFunction *mf, } if (pregOpt < allowed.size()) { ++pregOpt; // +1 to account for spill option. - PBQPRAGraph::NodeId node = p->getNodeForVReg(src); - llvm::dbgs() << "Reading node costs for node " << node << "\n"; - llvm::dbgs() << "Source node: " << &g.getNodeCosts(node) << "\n"; - PBQP::Vector newCosts(g.getNodeCosts(node)); - addPhysRegCoalesce(newCosts, pregOpt, cBenefit); - g.setNodeCosts(node, newCosts); + PBQP::Graph::NodeId node = p->getNodeForVReg(src); + addPhysRegCoalesce(g.getNodeCosts(node), pregOpt, cBenefit); } } else { const PBQPRAProblem::AllowedSet *allowed1 = &p->getAllowedSet(dst); const PBQPRAProblem::AllowedSet *allowed2 = &p->getAllowedSet(src); - PBQPRAGraph::NodeId node1 = p->getNodeForVReg(dst); - PBQPRAGraph::NodeId node2 = p->getNodeForVReg(src); - PBQPRAGraph::EdgeId edge = g.findEdge(node1, node2); + PBQP::Graph::NodeId node1 = p->getNodeForVReg(dst); + PBQP::Graph::NodeId node2 = p->getNodeForVReg(src); + PBQP::Graph::EdgeId edge = g.findEdge(node1, node2); if (edge == g.invalidEdgeId()) { - PBQP::Matrix costs(allowed1->size() + 1, allowed2->size() + 1, 0); - addVirtRegCoalesce(costs, *allowed1, *allowed2, cBenefit); - g.addEdge(node1, node2, costs); + edge = g.addEdge(node1, node2, PBQP::Matrix(allowed1->size() + 1, + allowed2->size() + 1, + 0)); } else { - if (g.getEdgeNode1Id(edge) == node2) { + if (g.getEdgeNode1(edge) == node2) { std::swap(node1, node2); std::swap(allowed1, allowed2); } - PBQP::Matrix costs(g.getEdgeCosts(edge)); - addVirtRegCoalesce(costs, *allowed1, *allowed2, cBenefit); - g.setEdgeCosts(edge, costs); } + + addVirtRegCoalesce(g.getEdgeCosts(edge), *allowed1, *allowed2, + cBenefit); } } } @@ -474,12 +471,14 @@ bool RegAllocPBQP::mapPBQPToRegAlloc(const PBQPRAProblem &problem, // Clear the existing allocation. vrm->clearAllVirt(); - const PBQPRAGraph &g = problem.getGraph(); + const PBQP::Graph &g = problem.getGraph(); // Iterate over the nodes mapping the PBQP solution to a register // assignment. - for (auto NId : g.nodeIds()) { - unsigned vreg = problem.getVRegForNode(NId); - unsigned alloc = solution.getSelection(NId); + for (PBQP::Graph::NodeItr nodeItr = g.nodesBegin(), + nodeEnd = g.nodesEnd(); + nodeItr != nodeEnd; ++nodeItr) { + unsigned vreg = problem.getVRegForNode(*nodeItr); + unsigned alloc = solution.getSelection(*nodeItr); if (problem.isPRegOption(vreg, alloc)) { unsigned preg = problem.getPRegForOption(vreg, alloc); @@ -604,7 +603,8 @@ bool RegAllocPBQP::runOnMachineFunction(MachineFunction &MF) { #endif PBQP::Solution solution = - PBQP::RegAlloc::solve(problem->getGraph()); + PBQP::HeuristicSolver::solve( + problem->getGraph()); pbqpAllocComplete = mapPBQPToRegAlloc(*problem, solution); -- 2.34.1