diff options
Diffstat (limited to 'include/llvm/CodeGen/PBQP/Heuristics/Briggs.h')
| -rw-r--r-- | include/llvm/CodeGen/PBQP/Heuristics/Briggs.h | 468 |
1 files changed, 0 insertions, 468 deletions
diff --git a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h deleted file mode 100644 index c355c2c..0000000 --- a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h +++ /dev/null @@ -1,468 +0,0 @@ -//===-- 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 <limits> - -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<Briggs> { - private: - - class LinkDegreeComparator { - public: - LinkDegreeComparator(HeuristicSolverImpl<Briggs> &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<Briggs> *s; - }; - - class SpillCostComparator { - public: - SpillCostComparator(HeuristicSolverImpl<Briggs> &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<Briggs> *s; - Graph *g; - }; - - typedef std::list<Graph::NodeId> RNAllocableList; - typedef RNAllocableList::iterator RNAllocableListItr; - - typedef std::list<Graph::NodeId> RNUnallocableList; - typedef RNUnallocableList::iterator RNUnallocableListItr; - - public: - - struct NodeData { - typedef std::vector<unsigned> 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<unsigned> UnsafeArray; - unsigned worst, reverseWorst; - UnsafeArray unsafe, reverseUnsafe; - bool isUpToDate; - - EdgeData() : worst(0), reverseWorst(0), isUpToDate(false) {} - }; - - /// \brief Construct an instance of the Briggs heuristic. - /// @param solver A reference to the solver which is using this heuristic. - Briggs(HeuristicSolverImpl<Briggs> &solver) : - HeuristicBase<Briggs>(solver) {} - - /// \brief Determine whether a node should be reduced using optimal - /// reduction. - /// @param 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<unsigned> 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<PBQPNum>::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<PBQPNum>::infinity()) - ++nd.numDenied; - } - - nd.numSafe = numRegs; - nd.unsafeDegrees.resize(numRegs, 0); - - typedef HeuristicSolverImpl<Briggs>::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<Briggs>::SolverEdgeItr SolverEdgeItr; - std::vector<Graph::EdgeId> 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 |