diff options
Diffstat (limited to 'llvm/lib/CodeGen/PBQP/Heuristics/Briggs.h')
| -rw-r--r-- | llvm/lib/CodeGen/PBQP/Heuristics/Briggs.h | 385 |
1 files changed, 385 insertions, 0 deletions
diff --git a/llvm/lib/CodeGen/PBQP/Heuristics/Briggs.h b/llvm/lib/CodeGen/PBQP/Heuristics/Briggs.h new file mode 100644 index 00000000000..fd37f5cbb32 --- /dev/null +++ b/llvm/lib/CodeGen/PBQP/Heuristics/Briggs.h @@ -0,0 +1,385 @@ +#ifndef LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H +#define LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H + +#include "../HeuristicSolver.h" + +#include <set> + +namespace PBQP { +namespace Heuristics { + +class Briggs { + public: + + class NodeData; + class EdgeData; + + private: + + typedef HeuristicSolverImpl<Briggs> Solver; + typedef HSITypes<NodeData, EdgeData> HSIT; + typedef HSIT::SolverGraph SolverGraph; + typedef HSIT::GraphNodeIterator GraphNodeIterator; + typedef HSIT::GraphEdgeIterator GraphEdgeIterator; + + class LinkDegreeComparator { + public: + LinkDegreeComparator() : g(0) {} + LinkDegreeComparator(SolverGraph *g) : g(g) {} + + bool operator()(const GraphNodeIterator &node1Itr, + const GraphNodeIterator &node2Itr) const { + assert((g != 0) && "Graph object not set, cannot access node data."); + unsigned n1Degree = g->getNodeData(node1Itr).getLinkDegree(), + n2Degree = g->getNodeData(node2Itr).getLinkDegree(); + if (n1Degree > n2Degree) { + return true; + } + else if (n1Degree < n2Degree) { + return false; + } + // else they're "equal" by degree, differentiate based on ID. + return g->getNodeID(node1Itr) < g->getNodeID(node2Itr); + } + + private: + SolverGraph *g; + }; + + class SpillPriorityComparator { + public: + SpillPriorityComparator() : g(0) {} + SpillPriorityComparator(SolverGraph *g) : g(g) {} + + bool operator()(const GraphNodeIterator &node1Itr, + const GraphNodeIterator &node2Itr) const { + assert((g != 0) && "Graph object not set, cannot access node data."); + PBQPNum cost1 = + g->getNodeCosts(node1Itr)[0] / + g->getNodeData(node1Itr).getLinkDegree(), + cost2 = + g->getNodeCosts(node2Itr)[0] / + g->getNodeData(node2Itr).getLinkDegree(); + + if (cost1 < cost2) { + return true; + } + else if (cost1 > cost2) { + return false; + } + // else they'er "equal" again, differentiate based on address again. + return g->getNodeID(node1Itr) < g->getNodeID(node2Itr); + } + + private: + SolverGraph *g; + }; + + typedef std::set<GraphNodeIterator, LinkDegreeComparator> + RNAllocableNodeList; + typedef RNAllocableNodeList::iterator RNAllocableNodeListIterator; + + typedef std::set<GraphNodeIterator, SpillPriorityComparator> + RNUnallocableNodeList; + typedef RNUnallocableNodeList::iterator RNUnallocableNodeListIterator; + + public: + + class NodeData { + private: + RNAllocableNodeListIterator rNAllocableNodeListItr; + RNUnallocableNodeListIterator rNUnallocableNodeListItr; + unsigned numRegOptions, numDenied, numSafe; + std::vector<unsigned> unsafeDegrees; + bool allocable; + + void addRemoveLink(SolverGraph &g, const GraphNodeIterator &nodeItr, + const GraphEdgeIterator &edgeItr, bool add) { + + //assume we're adding... + unsigned udTarget = 0, dir = 1; + + if (!add) { + udTarget = 1; + dir = -1; + } + + EdgeData &linkEdgeData = g.getEdgeData(edgeItr).getHeuristicData(); + + EdgeData::ConstUnsafeIterator edgeUnsafeBegin, edgeUnsafeEnd; + + if (nodeItr == g.getEdgeNode1Itr(edgeItr)) { + numDenied += (dir * linkEdgeData.getWorstDegree()); + edgeUnsafeBegin = linkEdgeData.unsafeBegin(); + edgeUnsafeEnd = linkEdgeData.unsafeEnd(); + } + else { + numDenied += (dir * linkEdgeData.getReverseWorstDegree()); + edgeUnsafeBegin = linkEdgeData.reverseUnsafeBegin(); + edgeUnsafeEnd = linkEdgeData.reverseUnsafeEnd(); + } + + assert((unsafeDegrees.size() == + static_cast<unsigned>( + std::distance(edgeUnsafeBegin, edgeUnsafeEnd))) + && "Unsafe array size mismatch."); + + std::vector<unsigned>::iterator unsafeDegreesItr = + unsafeDegrees.begin(); + + for (EdgeData::ConstUnsafeIterator edgeUnsafeItr = edgeUnsafeBegin; + edgeUnsafeItr != edgeUnsafeEnd; + ++edgeUnsafeItr, ++unsafeDegreesItr) { + + if ((*edgeUnsafeItr == 1) && (*unsafeDegreesItr == udTarget)) { + numSafe -= dir; + } + *unsafeDegreesItr += (dir * (*edgeUnsafeItr)); + } + + allocable = (numDenied < numRegOptions) || (numSafe > 0); + } + + public: + + void setup(SolverGraph &g, const GraphNodeIterator &nodeItr) { + + numRegOptions = g.getNodeCosts(nodeItr).getLength() - 1; + + numSafe = numRegOptions; // Optimistic, correct below. + numDenied = 0; // Also optimistic. + unsafeDegrees.resize(numRegOptions, 0); + + HSIT::NodeData &nodeData = g.getNodeData(nodeItr); + + for (HSIT::NodeData::AdjLinkIterator + adjLinkItr = nodeData.adjLinksBegin(), + adjLinkEnd = nodeData.adjLinksEnd(); + adjLinkItr != adjLinkEnd; ++adjLinkItr) { + + addRemoveLink(g, nodeItr, *adjLinkItr, true); + } + } + + bool isAllocable() const { return allocable; } + + void handleAddLink(SolverGraph &g, const GraphNodeIterator &nodeItr, + const GraphEdgeIterator &adjEdge) { + addRemoveLink(g, nodeItr, adjEdge, true); + } + + void handleRemoveLink(SolverGraph &g, const GraphNodeIterator &nodeItr, + const GraphEdgeIterator &adjEdge) { + addRemoveLink(g, nodeItr, adjEdge, false); + } + + void setRNAllocableNodeListItr( + const RNAllocableNodeListIterator &rNAllocableNodeListItr) { + + this->rNAllocableNodeListItr = rNAllocableNodeListItr; + } + + RNAllocableNodeListIterator getRNAllocableNodeListItr() const { + return rNAllocableNodeListItr; + } + + void setRNUnallocableNodeListItr( + const RNUnallocableNodeListIterator &rNUnallocableNodeListItr) { + + this->rNUnallocableNodeListItr = rNUnallocableNodeListItr; + } + + RNUnallocableNodeListIterator getRNUnallocableNodeListItr() const { + return rNUnallocableNodeListItr; + } + + + }; + + class EdgeData { + private: + + typedef std::vector<unsigned> UnsafeArray; + + unsigned worstDegree, + reverseWorstDegree; + UnsafeArray unsafe, reverseUnsafe; + + public: + + EdgeData() : worstDegree(0), reverseWorstDegree(0) {} + + typedef UnsafeArray::const_iterator ConstUnsafeIterator; + + void setup(SolverGraph &g, const GraphEdgeIterator &edgeItr) { + const Matrix &edgeCosts = g.getEdgeCosts(edgeItr); + unsigned numRegs = edgeCosts.getRows() - 1, + numReverseRegs = edgeCosts.getCols() - 1; + + unsafe.resize(numRegs, 0); + reverseUnsafe.resize(numReverseRegs, 0); + + std::vector<unsigned> rowInfCounts(numRegs, 0), + colInfCounts(numReverseRegs, 0); + + for (unsigned i = 0; i < numRegs; ++i) { + for (unsigned j = 0; j < numReverseRegs; ++j) { + if (edgeCosts[i + 1][j + 1] == + std::numeric_limits<PBQPNum>::infinity()) { + unsafe[i] = 1; + reverseUnsafe[j] = 1; + ++rowInfCounts[i]; + ++colInfCounts[j]; + + if (colInfCounts[j] > worstDegree) { + worstDegree = colInfCounts[j]; + } + + if (rowInfCounts[i] > reverseWorstDegree) { + reverseWorstDegree = rowInfCounts[i]; + } + } + } + } + } + + unsigned getWorstDegree() const { return worstDegree; } + unsigned getReverseWorstDegree() const { return reverseWorstDegree; } + ConstUnsafeIterator unsafeBegin() const { return unsafe.begin(); } + ConstUnsafeIterator unsafeEnd() const { return unsafe.end(); } + ConstUnsafeIterator reverseUnsafeBegin() const { + return reverseUnsafe.begin(); + } + ConstUnsafeIterator reverseUnsafeEnd() const { + return reverseUnsafe.end(); + } + }; + + void initialise(Solver &solver) { + this->s = &solver; + g = &s->getGraph(); + rNAllocableBucket = RNAllocableNodeList(LinkDegreeComparator(g)); + rNUnallocableBucket = + RNUnallocableNodeList(SpillPriorityComparator(g)); + + for (GraphEdgeIterator + edgeItr = g->edgesBegin(), edgeEnd = g->edgesEnd(); + edgeItr != edgeEnd; ++edgeItr) { + + g->getEdgeData(edgeItr).getHeuristicData().setup(*g, edgeItr); + } + + for (GraphNodeIterator + nodeItr = g->nodesBegin(), nodeEnd = g->nodesEnd(); + nodeItr != nodeEnd; ++nodeItr) { + + g->getNodeData(nodeItr).getHeuristicData().setup(*g, nodeItr); + } + } + + void addToRNBucket(const GraphNodeIterator &nodeItr) { + NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData(); + + if (nodeData.isAllocable()) { + nodeData.setRNAllocableNodeListItr( + rNAllocableBucket.insert(rNAllocableBucket.begin(), nodeItr)); + } + else { + nodeData.setRNUnallocableNodeListItr( + rNUnallocableBucket.insert(rNUnallocableBucket.begin(), nodeItr)); + } + } + + void removeFromRNBucket(const GraphNodeIterator &nodeItr) { + NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData(); + + if (nodeData.isAllocable()) { + rNAllocableBucket.erase(nodeData.getRNAllocableNodeListItr()); + } + else { + rNUnallocableBucket.erase(nodeData.getRNUnallocableNodeListItr()); + } + } + + void handleAddLink(const GraphEdgeIterator &edgeItr) { + // We assume that if we got here this edge is attached to at least + // one high degree node. + g->getEdgeData(edgeItr).getHeuristicData().setup(*g, edgeItr); + + GraphNodeIterator n1Itr = g->getEdgeNode1Itr(edgeItr), + n2Itr = g->getEdgeNode2Itr(edgeItr); + + HSIT::NodeData &n1Data = g->getNodeData(n1Itr), + &n2Data = g->getNodeData(n2Itr); + + if (n1Data.getLinkDegree() > 2) { + n1Data.getHeuristicData().handleAddLink(*g, n1Itr, edgeItr); + } + if (n2Data.getLinkDegree() > 2) { + n2Data.getHeuristicData().handleAddLink(*g, n2Itr, edgeItr); + } + } + + void handleRemoveLink(const GraphEdgeIterator &edgeItr, + const GraphNodeIterator &nodeItr) { + NodeData &nodeData = g->getNodeData(nodeItr).getHeuristicData(); + nodeData.handleRemoveLink(*g, nodeItr, edgeItr); + } + + void processRN() { + + /* + std::cerr << "processRN():\n" + << " rNAllocable = [ "; + for (RNAllocableNodeListIterator nItr = rNAllocableBucket.begin(), + nEnd = rNAllocableBucket.end(); + nItr != nEnd; ++nItr) { + std::cerr << g->getNodeID(*nItr) << " (" << g->getNodeData(*nItr).getLinkDegree() << ") "; + } + std::cerr << "]\n" + << " rNUnallocable = [ "; + for (RNUnallocableNodeListIterator nItr = rNUnallocableBucket.begin(), + nEnd = rNUnallocableBucket.end(); + nItr != nEnd; ++nItr) { + float bCost = g->getNodeCosts(*nItr)[0] / g->getNodeData(*nItr).getLinkDegree(); + std::cerr << g->getNodeID(*nItr) << " (" << bCost << ") "; + } + std::cerr << "]\n"; + */ + + if (!rNAllocableBucket.empty()) { + GraphNodeIterator selectedNodeItr = *rNAllocableBucket.begin(); + //std::cerr << "RN safely pushing " << g->getNodeID(selectedNodeItr) << "\n"; + rNAllocableBucket.erase(rNAllocableBucket.begin()); + s->pushStack(selectedNodeItr); + s->unlinkNode(selectedNodeItr); + } + else { + GraphNodeIterator selectedNodeItr = *rNUnallocableBucket.begin(); + //std::cerr << "RN optimistically pushing " << g->getNodeID(selectedNodeItr) << "\n"; + rNUnallocableBucket.erase(rNUnallocableBucket.begin()); + s->pushStack(selectedNodeItr); + s->unlinkNode(selectedNodeItr); + } + + } + + bool rNBucketEmpty() const { + return (rNAllocableBucket.empty() && rNUnallocableBucket.empty()); + } + +private: + + Solver *s; + SolverGraph *g; + RNAllocableNodeList rNAllocableBucket; + RNUnallocableNodeList rNUnallocableBucket; +}; + + + +} +} + + +#endif // LLVM_CODEGEN_PBQP_HEURISTICS_BRIGGS_H |
