aboutsummaryrefslogtreecommitdiffstats
path: root/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
diff options
context:
space:
mode:
Diffstat (limited to 'include/llvm/CodeGen/PBQP/Heuristics/Briggs.h')
-rw-r--r--include/llvm/CodeGen/PBQP/Heuristics/Briggs.h210
1 files changed, 105 insertions, 105 deletions
diff --git a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
index 307d81e..c355c2c 100644
--- a/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
+++ b/include/llvm/CodeGen/PBQP/Heuristics/Briggs.h
@@ -27,7 +27,7 @@ namespace PBQP {
/// \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
@@ -39,16 +39,16 @@ namespace PBQP {
/// 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.
+ ///
+ /// 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::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
- if (s->getSolverDegree(n1Itr) > s->getSolverDegree(n2Itr))
+ bool operator()(Graph::NodeId n1Id, Graph::NodeId n2Id) const {
+ if (s->getSolverDegree(n1Id) > s->getSolverDegree(n2Id))
return true;
return false;
}
@@ -60,12 +60,12 @@ namespace PBQP {
public:
SpillCostComparator(HeuristicSolverImpl<Briggs> &s)
: s(&s), g(&s.getGraph()) {}
- bool operator()(Graph::NodeItr n1Itr, Graph::NodeItr n2Itr) const {
- const PBQP::Vector &cv1 = g->getNodeCosts(n1Itr);
- const PBQP::Vector &cv2 = g->getNodeCosts(n2Itr);
+ 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(n1Itr);
- PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Itr);
+ PBQPNum cost1 = cv1[0] / s->getSolverDegree(n1Id);
+ PBQPNum cost2 = cv2[0] / s->getSolverDegree(n2Id);
if (cost1 < cost2)
return true;
@@ -77,10 +77,10 @@ namespace PBQP {
Graph *g;
};
- typedef std::list<Graph::NodeItr> RNAllocableList;
+ typedef std::list<Graph::NodeId> RNAllocableList;
typedef RNAllocableList::iterator RNAllocableListItr;
- typedef std::list<Graph::NodeItr> RNUnallocableList;
+ typedef std::list<Graph::NodeId> RNUnallocableList;
typedef RNUnallocableList::iterator RNUnallocableListItr;
public:
@@ -114,7 +114,7 @@ namespace PBQP {
/// \brief Determine whether a node should be reduced using optimal
/// reduction.
- /// @param nItr Node iterator to be considered.
+ /// @param nId Node id to be considered.
/// @return True if the given node should be optimally reduced, false
/// otherwise.
///
@@ -123,8 +123,8 @@ namespace PBQP {
/// infinite are checked for allocability first. Allocable nodes may be
/// optimally reduced, but nodes whose allocability cannot be proven are
/// selected for heuristic reduction instead.
- bool shouldOptimallyReduce(Graph::NodeItr nItr) {
- if (getSolver().getSolverDegree(nItr) < 3) {
+ bool shouldOptimallyReduce(Graph::NodeId nId) {
+ if (getSolver().getSolverDegree(nId) < 3) {
return true;
}
// else
@@ -132,15 +132,15 @@ namespace PBQP {
}
/// \brief Add a node to the heuristic reduce list.
- /// @param nItr Node iterator to add to the heuristic reduce list.
- void addToHeuristicReduceList(Graph::NodeItr nItr) {
- NodeData &nd = getHeuristicNodeData(nItr);
- initializeNode(nItr);
+ /// @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(), nItr);
+ nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nId);
} else {
- nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nItr);
+ nd.rnuItr = rnUnallocableList.insert(rnUnallocableList.end(), nId);
}
}
@@ -159,19 +159,19 @@ namespace PBQP {
RNAllocableListItr rnaItr =
min_element(rnAllocableList.begin(), rnAllocableList.end(),
LinkDegreeComparator(getSolver()));
- Graph::NodeItr nItr = *rnaItr;
+ Graph::NodeId nId = *rnaItr;
rnAllocableList.erase(rnaItr);
- handleRemoveNode(nItr);
- getSolver().pushToStack(nItr);
+ handleRemoveNode(nId);
+ getSolver().pushToStack(nId);
return true;
} else if (!rnUnallocableList.empty()) {
RNUnallocableListItr rnuItr =
min_element(rnUnallocableList.begin(), rnUnallocableList.end(),
SpillCostComparator(getSolver()));
- Graph::NodeItr nItr = *rnuItr;
+ Graph::NodeId nId = *rnuItr;
rnUnallocableList.erase(rnuItr);
- handleRemoveNode(nItr);
- getSolver().pushToStack(nItr);
+ handleRemoveNode(nId);
+ getSolver().pushToStack(nId);
return true;
}
// else
@@ -179,43 +179,43 @@ namespace PBQP {
}
/// \brief Prepare a change in the costs on the given edge.
- /// @param eItr Edge iterator.
- void preUpdateEdgeCosts(Graph::EdgeItr eItr) {
+ /// @param eId Edge id.
+ void preUpdateEdgeCosts(Graph::EdgeId eId) {
Graph &g = getGraph();
- Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
- n2Itr = g.getEdgeNode2(eItr);
- NodeData &n1 = getHeuristicNodeData(n1Itr),
- &n2 = getHeuristicNodeData(n2Itr);
+ Graph::NodeId n1Id = g.getEdgeNode1(eId),
+ n2Id = g.getEdgeNode2(eId);
+ NodeData &n1 = getHeuristicNodeData(n1Id),
+ &n2 = getHeuristicNodeData(n2Id);
if (n1.isHeuristic)
- subtractEdgeContributions(eItr, getGraph().getEdgeNode1(eItr));
+ subtractEdgeContributions(eId, getGraph().getEdgeNode1(eId));
if (n2.isHeuristic)
- subtractEdgeContributions(eItr, getGraph().getEdgeNode2(eItr));
+ subtractEdgeContributions(eId, getGraph().getEdgeNode2(eId));
- EdgeData &ed = getHeuristicEdgeData(eItr);
+ EdgeData &ed = getHeuristicEdgeData(eId);
ed.isUpToDate = false;
}
/// \brief Handle the change in the costs on the given edge.
- /// @param eItr Edge iterator.
- void postUpdateEdgeCosts(Graph::EdgeItr eItr) {
+ /// @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(eItr);
+ handleAddEdge(eId);
}
/// \brief Handle the addition of a new edge into the PBQP graph.
- /// @param eItr Edge iterator for the added edge.
+ /// @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::EdgeItr eItr) {
+ void handleAddEdge(Graph::EdgeId eId) {
Graph &g = getGraph();
- Graph::NodeItr n1Itr = g.getEdgeNode1(eItr),
- n2Itr = g.getEdgeNode2(eItr);
- NodeData &n1 = getHeuristicNodeData(n1Itr),
- &n2 = getHeuristicNodeData(n2Itr);
+ 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.
@@ -223,60 +223,60 @@ namespace PBQP {
return;
// Ok - we need to update at least one node.
- computeEdgeContributions(eItr);
+ computeEdgeContributions(eId);
// Update node 1 if it's managed by the heuristic.
if (n1.isHeuristic) {
bool n1WasAllocable = n1.isAllocable;
- addEdgeContributions(eItr, n1Itr);
- updateAllocability(n1Itr);
+ addEdgeContributions(eId, n1Id);
+ updateAllocability(n1Id);
if (n1WasAllocable && !n1.isAllocable) {
rnAllocableList.erase(n1.rnaItr);
n1.rnuItr =
- rnUnallocableList.insert(rnUnallocableList.end(), n1Itr);
+ rnUnallocableList.insert(rnUnallocableList.end(), n1Id);
}
}
// Likewise for node 2.
if (n2.isHeuristic) {
bool n2WasAllocable = n2.isAllocable;
- addEdgeContributions(eItr, n2Itr);
- updateAllocability(n2Itr);
+ addEdgeContributions(eId, n2Id);
+ updateAllocability(n2Id);
if (n2WasAllocable && !n2.isAllocable) {
rnAllocableList.erase(n2.rnaItr);
n2.rnuItr =
- rnUnallocableList.insert(rnUnallocableList.end(), n2Itr);
+ rnUnallocableList.insert(rnUnallocableList.end(), n2Id);
}
}
}
/// \brief Handle disconnection of an edge from a node.
- /// @param eItr Edge iterator for edge being disconnected.
- /// @param nItr Node iterator for the node being disconnected from.
+ /// @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::EdgeItr eItr, Graph::NodeItr nItr) {
- NodeData &nd = getHeuristicNodeData(nItr);
+ 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(eItr);
+ EdgeData &ed = getHeuristicEdgeData(eId);
(void)ed;
assert(ed.isUpToDate && "Edge data is not up to date.");
// Update node.
bool ndWasAllocable = nd.isAllocable;
- subtractEdgeContributions(eItr, nItr);
- updateAllocability(nItr);
+ subtractEdgeContributions(eId, nId);
+ updateAllocability(nId);
// If the node has gone optimal...
- if (shouldOptimallyReduce(nItr)) {
+ if (shouldOptimallyReduce(nId)) {
nd.isHeuristic = false;
- addToOptimalReduceList(nItr);
+ addToOptimalReduceList(nId);
if (ndWasAllocable) {
rnAllocableList.erase(nd.rnaItr);
} else {
@@ -287,36 +287,36 @@ namespace PBQP {
// from "unallocable" to "allocable".
if (!ndWasAllocable && nd.isAllocable) {
rnUnallocableList.erase(nd.rnuItr);
- nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nItr);
+ nd.rnaItr = rnAllocableList.insert(rnAllocableList.end(), nId);
}
}
}
private:
- NodeData& getHeuristicNodeData(Graph::NodeItr nItr) {
- return getSolver().getHeuristicNodeData(nItr);
+ NodeData& getHeuristicNodeData(Graph::NodeId nId) {
+ return getSolver().getHeuristicNodeData(nId);
}
- EdgeData& getHeuristicEdgeData(Graph::EdgeItr eItr) {
- return getSolver().getHeuristicEdgeData(eItr);
+ 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::EdgeItr eItr) {
- EdgeData &ed = getHeuristicEdgeData(eItr);
+ void computeEdgeContributions(Graph::EdgeId eId) {
+ EdgeData &ed = getHeuristicEdgeData(eId);
if (ed.isUpToDate)
return; // Edge data is already up to date.
- Matrix &eCosts = getGraph().getEdgeCosts(eItr);
+ Matrix &eCosts = getGraph().getEdgeCosts(eId);
unsigned numRegs = eCosts.getRows() - 1,
numReverseRegs = eCosts.getCols() - 1;
std::vector<unsigned> rowInfCounts(numRegs, 0),
- colInfCounts(numReverseRegs, 0);
+ colInfCounts(numReverseRegs, 0);
ed.worst = 0;
ed.reverseWorst = 0;
@@ -348,19 +348,19 @@ namespace PBQP {
ed.isUpToDate = true;
}
- // Add the contributions of the given edge to the given node's
+ // Add the contributions of the given edge to the given node's
// numDenied and safe members. No action is taken other than to update
// these member values. Once updated these numbers can be used by clients
// to update the node's allocability.
- void addEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
- EdgeData &ed = getHeuristicEdgeData(eItr);
+ void addEdgeContributions(Graph::EdgeId eId, Graph::NodeId nId) {
+ EdgeData &ed = getHeuristicEdgeData(eId);
assert(ed.isUpToDate && "Using out-of-date edge numbers.");
- NodeData &nd = getHeuristicNodeData(nItr);
- unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
-
- bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
+ 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;
@@ -375,25 +375,25 @@ namespace PBQP {
}
}
- // Subtract the contributions of the given edge to the given node's
+ // Subtract the contributions of the given edge to the given node's
// numDenied and safe members. No action is taken other than to update
// these member values. Once updated these numbers can be used by clients
// to update the node's allocability.
- void subtractEdgeContributions(Graph::EdgeItr eItr, Graph::NodeItr nItr) {
- EdgeData &ed = getHeuristicEdgeData(eItr);
+ void subtractEdgeContributions(Graph::EdgeId eId, Graph::NodeId nId) {
+ EdgeData &ed = getHeuristicEdgeData(eId);
assert(ed.isUpToDate && "Using out-of-date edge numbers.");
- NodeData &nd = getHeuristicNodeData(nItr);
- unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
-
- bool nIsNode1 = nItr == getGraph().getEdgeNode1(eItr);
+ 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 (unsafe[r]) {
if (nd.unsafeDegrees[r] == 1) {
++nd.numSafe;
}
@@ -402,22 +402,22 @@ namespace PBQP {
}
}
- void updateAllocability(Graph::NodeItr nItr) {
- NodeData &nd = getHeuristicNodeData(nItr);
- unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
+ 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::NodeItr nItr) {
- NodeData &nd = getHeuristicNodeData(nItr);
+ void initializeNode(Graph::NodeId nId) {
+ NodeData &nd = getHeuristicNodeData(nId);
if (nd.isInitialized)
return; // Node data is already up to date.
- unsigned numRegs = getGraph().getNodeCosts(nItr).getLength() - 1;
+ unsigned numRegs = getGraph().getNodeCosts(nId).getLength() - 1;
nd.numDenied = 0;
- const Vector& nCosts = getGraph().getNodeCosts(nItr);
+ const Vector& nCosts = getGraph().getNodeCosts(nId);
for (unsigned i = 1; i < nCosts.getLength(); ++i) {
if (nCosts[i] == std::numeric_limits<PBQPNum>::infinity())
++nd.numDenied;
@@ -428,27 +428,27 @@ namespace PBQP {
typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
- for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nItr),
- aeEnd = getSolver().solverEdgesEnd(nItr);
+ for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(nId),
+ aeEnd = getSolver().solverEdgesEnd(nId);
aeItr != aeEnd; ++aeItr) {
-
- Graph::EdgeItr eItr = *aeItr;
- computeEdgeContributions(eItr);
- addEdgeContributions(eItr, nItr);
+
+ Graph::EdgeId eId = *aeItr;
+ computeEdgeContributions(eId);
+ addEdgeContributions(eId, nId);
}
- updateAllocability(nItr);
+ updateAllocability(nId);
nd.isInitialized = true;
}
- void handleRemoveNode(Graph::NodeItr xnItr) {
+ void handleRemoveNode(Graph::NodeId xnId) {
typedef HeuristicSolverImpl<Briggs>::SolverEdgeItr SolverEdgeItr;
- std::vector<Graph::EdgeItr> edgesToRemove;
- for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnItr),
- aeEnd = getSolver().solverEdgesEnd(xnItr);
+ std::vector<Graph::EdgeId> edgesToRemove;
+ for (SolverEdgeItr aeItr = getSolver().solverEdgesBegin(xnId),
+ aeEnd = getSolver().solverEdgesEnd(xnId);
aeItr != aeEnd; ++aeItr) {
- Graph::NodeItr ynItr = getGraph().getEdgeOtherNode(*aeItr, xnItr);
- handleRemoveEdge(*aeItr, ynItr);
+ Graph::NodeId ynId = getGraph().getEdgeOtherNode(*aeItr, xnId);
+ handleRemoveEdge(*aeItr, ynId);
edgesToRemove.push_back(*aeItr);
}
while (!edgesToRemove.empty()) {
generated by cgit v1.1 at 2024-06-08 00:03:13 +0000